LP exampleSlide 2Example FormulationFeasible RegionSlide 5Geometric SolutionLP Solution (Production Planning)Example (Revisited)Example 2 Product-Mix ProblemExample 2 - contdSlide 11Slide 12Slide 13Slide 14Example 1 - contdSlide 16Example 3Slide 18An LP Formulation Example: Minimum Cost FlowAn LP Formulation Example: Minimum Cost Flow - Contd.Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30An Application to Network DesignAn Application to Network Design – contd.Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44LP example•Production planning: a producer of furniture has to make the decision about the production planning for 2 of its products: work desks and lunch tables. There are 2 resources available for production which these products are using: lumber and carpentry. 20 units of each resource is available. Here is the table containing the data for the problem:Desk TableSelling Price $15 $20Desk Table AvailabilityLumber 1 2 20Carpentry 2 1 20LP example•First table shows the selling prices of each product, and second table show the amount of each resource that is used to produce one unit of product as well as resource availability. The question is how many of each product should be produced in order to maximize the revenue?•To model this problem as a linear programming formulation we should define our decision variables:Example Formulation•Defining the decision variables of the problem, the formulation will be:•(1) is the total revenue generated by producing x1 desks and x2 tables.•(2) is the constraint for the total number of lumbers that exists.•(3) is the constraint for the total carpentry hours available.•(4) is the non-negativity constraints, saying that production can not be negative.Feasible Region•Feasible region is defined by the set of constraints of the problem, which is all the possible points that satisfy the all the constraints.•In production planning problem, the feasible set defined by the constraints looks like this plot:Feasible Region•The red line represents the line for (2)•The green line represents the line for (3)•The region with blue line represents entire feasible region of the problem.Geometric Solution•To find the solution of LP problems, the line for objective function should be plotted and the point in feasible region which maximize (minimize) the function is the solution.•Dashed parallel lines are representing the objective function line for 2 different values.LP Solution (Production Planning)•For the production planning example the solutions are:•Since the number of desks and tables can not be fractional, we might be able to round the solution down to get our integer solution, with a revenue of 210.•Does rounding the solution yield the optimal solution to integer problem?X1 X2 Revenue0 0 010 0 1500 10 2006.66 6.66 233.33Example (Revisited)•Remember we got 210 as our objective function by rounding down the LP solutions.•If we solve the same problem as an IP the optimal solution will be:Example 2 Product-Mix ProblemThe Handy-Dandy Company wishes to schedule the production of a kitchen appliance which requires two resources – labor and material. The company is considering three different models of this appliance and its engineering department has furnished the following data:Example 2 - contdThe supply of raw materials is restricted to 200 pounds per day. The daily availability of manpower is 150 hours. Formulate a linear programming model to determine the daily production rate of the various models of appliances in order to maximize the total profit.Example 2 - contdStep IIdentify the Decision Variables. The unknown activities to be determined are the daily rate of production for the three models (A, B, C) in order to maximize the total profit. Representing them by algebraic symbols,xA= daily production of model AxB= daily production of model B xC= daily production of model CExample 2 - contdStep IIIdentify the Constraints. In this problem the constraints are the limited availability of the two resources (labor and material).Model A requires 7 hours of labor for each unit, and its production quantity is xA. Hence, the requirement of manpower for model A alone will be 7xA hours (assuming a linear relationship).Example 2 - contdSimilarly, models B and C will require 3xB and 6xC hours, respectively. Thus, the total requirement of labor will be 7xA + 3xB + 6xC, which should not exceed the available 150 hours. So the labor constraint becomes:7xA + 3xB + 6xC 150Example 2 - contdSimilarly, the raw material constraint is given by4xA + 4xB + 5xC 200In addition, we restrict the variables to have non-negative values. This is called the non-negativity constraint, which the variables must satisfyxA, xB and xC 0.Example 1 - contdStep IIIIdentifying the Objective. The objective is to maximize the total profit from the sales. Assuming that perfect market exists for the product such that all that is produced can be sold, the total profit from sales becomesZ = 4xA + 2xB + 3XC.Example 2 - contdThus, the linear programming model for our product mix problem is:Find numbers xA, xB, xC which will maximizeZ = 4xA + 2xB + 3XCsubject to the constrains7xA + 3xB + 6xC 1504xA + 4xB + 5xC 200xA 0, xB 0, xC 0Example 3schedule that minimizes the cost, such that in each month the demand is satisfied.Example 3•Ri = regular production in month i•Oi = Overtime production in month i•Di = Demand in month i•Cost = Ri * b + Oi * c + (Ri + Oi – Di ) *s•S.t. c > b• Ri + Oi + ∑j=1toi-1 (Rj+Oj – Dj ) >= Di– The third factor accounts for items in store from previous monthsAn LP Formulation Example:Minimum Cost Flow•The Minimum Cost Flow (MCF) problem is a frequently used mode. It can be described in our context as follows:–Given a network with N nodes and M links among them. We would like to transport some entity among nodes (for example, data), so that it flows along the links. The goal is to determine the optimal flow, that is, how much flow is put on each link, according to the conditions discussed below.An LP Formulation Example:Minimum Cost Flow - Contd.•Input data:–The link from node i to j has a given capacity Cij >= 0.–Each node i is associated with a given number bi, the source rate of the node. If bi > 0; the node is called a source, if bi < 0; the node is a sink. If bi = 0, the node is
View Full Document
Unlocking...