Linear Programming Formulation Practice Sets
These practice sets cover various linear programming problems such as optimal product mix management, farmer's crop planting decision, and marketing exposure optimization. It includes formulation of problems, decision variables, constraints, and objective functions, offering a comprehensive understanding and solution to each scenario.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
LP Formulation Practice Set 1
Problem 1. Optimal Product Mix Management is considering devoting some excess capacity to one or more of three products. The hours required from each resource for each unit of product, the available capacity (hours per week) of the three resources, as well as the profit of each unit of product are given below. Total hours avialable Product1 Product2 Product3 9 3 5 500 5 4 0 350 3 0 2 150 $50 $20 $25 Profit Hours used per unit Sales department indicates that the sales potentials for products 1 and 2 exceeds maximum production rate, but the sales potential for product 3 is 20 units per week. Formulate the problem and solve it using excel LP-Formulation Ardavan Asef-Vaziri 2
Problem 1. Formulation Decision Variables x1: volume of product 1 x2: volume of product 2 x3: volume of product 3 Objective Function Max Z = 50 x1 +20 x2 +25 x3 Constraints Resources 9 x1 +3 x2 +5 x3 500 5 x1 +4 x2 + 350 3 x1 + +2 x3 150 Market x3 20 Nonnegativity x1 0, x2 0 , x3 0 R1 R2 R3 M Z 9 5 3 3 4 5 500 350 500 350 150 20 2 1 25 20 118.5714 20 2904.762 50 20 26.19048 54.7619 LP-Formulation Ardavan Asef-Vaziri 3
Problem 2 A farmer has 10 acres to plant in wheat and rye. He has to plant at least 7 acres. However, he has only $1200 to spend and each acre of wheat costs $200 to plant and each acre of rye costs $100 to plant. Moreover, the farmer has to get the planting done in 12 hours and it takes an hour to plant an acre of wheat and 2 hours to plant an acre of rye. If the profit is $500 per acre of wheat and $300 per acre of rye, how many acres of each should be planted to maximize profits? State the decision variables. x = the number of acres of wheat to plant y = the number of acres of rye to plant Write the objective function. maximize 500x +300y LP-Formulation Ardavan Asef-Vaziri 4
Problem 2. Formulation Write the constraints. x+y 10 x+y 7 200x + 100y 1200 x + 2y 12 x 0, y 0 (max acreage) (min acreage) (cost) (time) (non-negativity) x 1 1 y 1 1 RHS 10 7 1200 12 MaxAcr MinAcr Bud Time Profit 8 8 200 1 500 4 100 2 300 4 1200 12 3200 LP-Formulation Ardavan Asef-Vaziri 5
Problem 3. Marketing : narrative A department store want to maximize exposure. There are 3 media; TV, Radio, Newspaper each ad will have the following impact Media Exposure (people / ad) TV 20000 Radio 12000 News paper 9000 Additional information 1-Total budget is $100,000. 2-The maximum number of ads in T, R, and N are limited to 4, 10, 7 ads respectively. 3-The total number of ads is limited to 15. Cost 15000 6000 4000 LP-Formulation Ardavan Asef-Vaziri 6
Problem 3. Marketing : formulation Decision variables x1 = Number of ads in TV x2 = Number of ads in R x3 = Number of ads in N XT 15 1 XR 6 XN 4 LHS 100 RHS 100 4 10 7 15 Bud MT MR MN MToT 1.818182 10 3.181818 15 185 1 1 1 9 1 20 1 12 1.818182 10 3.181818 XT 15 1 XR 6 XN 4 LHS 100 2 9 4 15 184 RHS 100 4 10 7 15 Bud MT MR MN MToT 1 Max Z = 20 x1 +12x2 +9x3 1 1 9 4 1 20 2 1 12 9 15x1 +6x2 + 4x3 100 x1 4 x2 10 x3 7 x1 +x2 + x3 15 P1 XT 15 20 2 4 P2 XR 6 12 9 10 P3 XN 4 9 4 7 LHS ` Bud LHS 100 184 15 15 RHS 100 LHS RHS x1,x2, x3 0 LP-Formulation Ardavan Asef-Vaziri 7
Problem 4. ( From Hillier and Hillier) Men, women, and children gloves. Material and labor requirements for each type and the corresponding profit are given below. Glove Material (sq-feet) Labor (hrs) Contribution Margin Men 2 Women 1.5 Children 1 Total available material is 5000 sq-feet. We can have full time and part time workers. Full time workers work 40 hrs/w and are paid $13/hr Part time workers work 20 hrs/w and are paid $10/hr We should have at least 20 full time workers. The number of full time workers must be at least twice of that of part times. Labor is considered fixed cost not variable. 0.5 0.75 0.67 8 10 6 LP-Formulation Ardavan Asef-Vaziri 8
Problem 4. Decision variables X1 : Volume of production of Men s gloves X2 : Volume of production of Women s gloves X3 : Volume of production of Children s gloves Y1 : Number of full time employees Y2 : Number of part time employees LP-Formulation Ardavan Asef-Vaziri 9
Problem 4. Constraints Row material constraint 2X1 + 1.5X2 + X3 5000 Full time employees Y1 20 Relationship between the number of Full and Part time employees Y1 2 Y2 Labor Required .5X1 + .75X2 + .67X3 40 Y1 + 20Y2 Objective Function Max Z = 8X1 + 10X2 + 6X3 - 520 Y1 - 200 Y2 Non-negativity X1 , X2 , X3 , Y1 , Y2 0 LP-Formulation Ardavan Asef-Vaziri 10
Problem 4. Excel Solution 2 1.5 1 0 0 0 0 0 <= >= >= <= 5000 20 0 0 1 1 -2 -20 -200 0.5 8 0.75 10 0.67 6 -40 -520 X1 X2 X3 Y1 Y2 2 1.5 1 5000 25 0 0 4500 <= >= >= <= 5000 20 0 0 1 1 -2 -20 -200 12.5 Y2 0.5 8 2500 X1 0.75 10 0 X2 0.67 6 0 X3 -40 -520 25 Y1 LP-Formulation Ardavan Asef-Vaziri 11
Problem 5. From Hillier and Hillier Strawberry shake production Several ingredients can be used in this product. Ingredient calories from fat Total calories Vitamin Thickener Cost ( per tbsp) (per tbsp) (mg/tbsp) (mg/tbsp) ( c/tbsp) Strawberry flavoring 1 50 20 3 10 Cream 75 100 0 8 8 Vitamin supplement 0 0 50 1 25 Artificial sweetener 0 120 0 2 15 Thickening agent 30 80 2 2.5 6 This beverage has the following requirements Total calories between 380 and 420. No more than 20% of total calories from fat. At least 50 mg vitamin. At least 2 tbsp of strawberry flavoring for each 1 tbsp of artificial sweetener. Exactly 15 mg thickeners. Formulate the problem to minimize costs. LP-Formulation Ardavan Asef-Vaziri 12
Decision variables Decision Variables X1 : tbsp of strawberry X2 : tbsp of cream X3 : tbsp of vitamin X4 : tbsp of Artificial sweetener X5 : tbsp of thickening LP-Formulation Ardavan Asef-Vaziri 13
Constraints Objective Function Min Z = 10X1 + 8X2 + 25X3 +15X4 + 6X5 Calories 50X1 + 100 X2 + 120 X4 + 80 X5 380 50X1 + 100 X2 + 120 X4 + 80 X5 420 Calories from fat X1 + 75 X2 + 30 X5 0.2(50X1 + 100 X2 + 120 X4 + 80 X5) Vitamin 20X1 + 50 X3 + 2 X5 50 Strawberry and sweetener X1 2 X4 Thickeners 3X1 + 8X2 + X3 +2X4 + 2.5X5 = 15 Non-negativity X1 , X2 , X3 , X4 , X5 0 LP-Formulation Ardavan Asef-Vaziri 14
Constraints Objective Function Min Z = 10X1 + 8X2 + 25X3 +15X4 + 6X5 Calories 50X1 + 100 X2 + 120 X4 + 80 X5 380 50X1 + 100 X2 + 120 X4 + 80 X5 420 Calories from fat -9X1 + 55 X2 -24X4 +14X5 0 Vitamin 20X1 + 50 X3 + 2 X5 50 Strawberry and sweetener X1 -2 X4 0 Thickeners 3X1 + 8X2 + X3 +2X4 + 2.5X5 = 15 Non-negativity X1 , X2 , X3 , X4 , X5 0 LP-Formulation Ardavan Asef-Vaziri 15
Constraints X1 10 50 50 -9 20 1 3 X2 8 100 100 55 X3 25 X4 15 120 120 -24 X5 6 80 80 14 2 Cost Calory 1 Calory 2 CaloryFat Vitamin 47.61948 380 380 7.11E-15 <= 50 0.794906 >= 15 >= <= 380 420 0 50 0 15 50 >= -2 2 8 1 2.5 = 2.312262 0.231551 0 0.758678 1.877381 LP-Formulation Ardavan Asef-Vaziri 16
Problem 6. Make / buy decision : Narrative representation Electro-Poly is a leading maker of slip-rings. A new order has just been received. Model 1 3,000 2 1 $50 $61 Model 2 2,000 1.5 2 $83 $97 Model 3 900 3 1 $130 $145 Number ordered Hours of wiring/unit Hours of harnessing/unit Cost to Make Cost to Buy The company has 10,000 hours of wiring capacity and 5,000 hours of harnessing capacity. LP-Formulation Ardavan Asef-Vaziri 17
Problem 6. Make / buy decision : decision variables x1 = Number of model 1 slip rings to make x2 = Number of model 2 slip rings to make x3 = Number of model 3 slip rings to make y1 = Number of model 1 slip rings to buy y2 = Number of model 2 slip rings to buy y3 = Number of model 3 slip rings to buy The Objective Function Minimize the total cost of filling the order. MIN: 50x1 + 83x2 + 130x3 + 61y1 + 97y2 + 145y3 LP-Formulation Ardavan Asef-Vaziri 18
Problem 6. Make / buy decision : Constraints Cost Table 83 97 Decision Table 1 2 0 0 0 0 2 1.5 1 2 3000 2000 Demand Constraints x1 + y1 = 3,000 x2 + y2 = 2,000 x3 + y3 = 900 Resource Constraints 2x1 + 1.5x2 + 3x3 <= 10,000 } wiring 1x1 + 2.0x2 + 1x3 <= 5,000 } harnessing Nonnegativity Conditions x1, x2, x3, y1, y2, y3 >= 0 50 61 130 145 } model 1 } model 2 } model 3 3 X Y 0 0 0 0 0 3 1 900 0 0 0 10000 5000 LP-Formulation Ardavan Asef-Vaziri 19
Problem 6. Make / buy decision : Excel Model 1 Model 2 Model 3 50 83 61 97 Model 1 Model 2 Model 3 3000 550 0 1450 3000 2000 3000 2000 Make Buy 130 145 Make Buy Produced Required 900 0 900 900 453300 Capacity Wiring Harnessing Required Available 9525 5000 2 1 1.5 2 3 1 10000 5000 LP-Formulation Ardavan Asef-Vaziri 20
Problem 6. Make / buy decision : Constraints Do we really need 6 variables? x1 + y1 = 3,000 ===> y1 = 3,000 - x1 x2 + y2 = 2,000 ===> y2 = 2,000 - x2 x3 + y3 = 900 ===> y3 = 900 - x3 The objective function was MIN: 50x1 + 83x2 + 130x3 + 61y1 + 97y2 + 145y3 Just replace the values MIN: 50x1 + 83x2 + 130x3 + 61 (3,000 - x1 ) + 97 ( 2,000 - x2) + 145 (900 - x3 ) MIN: 507500 - 11x1 -14x2 -15x3 We can even forget 507500, and change the the O.F. into MIN - 11x1 -14x2 -15x3 or MAX + 11x1 +14x2 +15x3 LP-Formulation Ardavan Asef-Vaziri 21
Problem 6. Make / buy decision : Constraints MAX + 11x1 +14x2 +15x3 Resource Constraints 2x1 + 1.5x2 + 3x3 <= 10,000 } wiring 1x1 + 2.0x2 + 1x3 <= 5,000 } harnessing Demand Constraints x1 <= 3,000 x2 <= 2,000 x3 <= 900 } model 1 } model 2 } model 3 Nonnegativity Conditions x1, x2, x3 >= 0 LP-Formulation Ardavan Asef-Vaziri 22
Problem 6. Make / buy decision : Constraints y1 = 3,000- x1 y2 = 2,000-x2 y3 = 900-x3 MIN: 50x1 + 83x2 + 130x3 + 61y1 + 97y2 + 145y3 Demand Constraints x1 + y1 = 3,000 x2 + y2 = 2,000 x3 + y3 = 900 Resource Constraints 2x1 + 1.5x2 + 3x3 <= 10,000 } wiring 1x1 + 2.0x2 + 1x3 <= 5,000 } harnessing Nonnegativity Conditions x1, x2, x3, y1, y2, y3 >= 0 MIN: 50x1 + 83x2 + 130x3 + 61(3,000- x1) + 97(2,000-x2) + 145(900-x3) } model 1 } model 2 } model 3 y1 = 3,000- x1>=0 y2 = 2,000-x2>=0 y3 = 900-x3>=0 x1 <= 3,000 x2 <= 2,000 x3 <= 900 LP-Formulation Ardavan Asef-Vaziri 23
Problem 6. Make / buy decision : Constraints Model1 2 1 11 3000 3000 Model2 1.5 2 14 2000 550 Model3 3 1 15 900 900 Wiring Harnessing Marginal Profit Demand 9525 5000 54200 10000 5000 453300 LP-Formulation Ardavan Asef-Vaziri 24
Problem 7 You are given the following linear programming model in algebraic form, where, X1 and X2 are the decision variables and Z is the value of the overall measure of performance. Maximize Z = X1 +2 X2 Subject to Constraints on resource 1: X1 + X2 5 (amount available) Constraints on resource 2: X1 + 3X2 9 (amount available) And X1 , X2 0 LP-Formulation Ardavan Asef-Vaziri 25
Problem 7 Identify the objective function, the functional constraints, and the non-negativity constraints in this model. Objective Function Maximize Z = X1 +2 X2 Functional constraints X1 + X2 5, X1 + 3X2 9 Is (X1 ,X2) = (3,1) a feasible solution? 3 + 1 5, 3 + 3(1) 9 yes; it satisfies both constraints. Is (X1 ,X2) = (1,3) a feasible solution? 1 + 3 5, 1 + 3(9) > 9 no; it violates the second constraint. LP-Formulation Ardavan Asef-Vaziri 26
Problem 8 You are given the following linear programming model in algebraic form, where, X1 and X2 are the decision variables and Z is the value of the overall measure of performance. Maximize Z = 3X1 +2 X2 Subject to Constraints on resource 1: 3X1 + X2 9 (amount available) Constraints on resource 2: X1 + 2X2 8 (amount available) And X1 , X2 0 LP-Formulation Ardavan Asef-Vaziri 27
Problem 8 Identify the objective function, Maximize Z = 3X1 +2 X2 the functional constraints, 3X1 + X2 9 and X1 + 2X2 8 the non-negativity constraints X1 , X2 0 Is (X1 ,X2) = (2,1) a feasible solution? 3(2) + 1 9 and 2 + 2(1) 8 yes; it satisfies both constraints Is (X1 ,X2) = (2,3) a feasible solution? 3(2) + 3 9 and 2 + 2(3) 8 yes; it satisfies both constraints Is (X1 ,X2) = (0,5) a feasible solution? 3(0) + 5 9 and 0 + 2(5) > 8 no; it violates the second constraint LP-Formulation Ardavan Asef-Vaziri 28
