Introduction to Operations Research

Introduction to Operations Research Unit 1: Linear Programming – Terminology and formulations . LP through an example . ... A company makes two produc...

6 downloads 385 Views 412KB Size
Introduction to Operations Research Unit 1: Linear Programming – Terminology and formulations LP through an example Terminology Additional Example 1 Additional example 2 A shop can make two types of sweets (A and B). They use two resources – flour and sugar. To make one packet of A, they need 2 kg of flour and 5 kg of sugar. To make one packet of B, they need 3 kg of flour and 3 kg of sugar. They have 25 kg of flour and 28 kg of sugar. These sweets are sold at Rs 800 and 900 per packet respectively. Find the best product mix. 1. (a) (b) (c) 2. 3.

An appropriate objective function for this problem is to Maximize total revenue Minimize total cost Maximize the total units of products produced. Ans = A The number of decision variables is _____________ (2) The number of constraints is _________________ (2)

Let X 1 be the packets of sweet A made. Let X 2 be the number of packets of sweet B made. Objective is to Maximize 800X 1 + 900X 2 Constraints are 2X 1 + 3X 2 ≤ 25 (constraint on flour availability) 5X 1 + 3X 2 ≤ 28 (constraint on sugar availability) X 1 , X 2 ≥ 0 (non negativity constraints) A company makes two products (A and B) and both require processing on 2 machines. Product A takes 10 and 15 minutes on the two machines per unit and product B takes 22 and 18 minutes per unit on the two machines. Both the machines are available for 2640 minutes per week. The products are sold for Rs 200 and Rs 175 respectively per unit. Formulate a LP to maximize revenue? The market can take a maximum of 150 units of product 1. 4. a) b) c) 5. 6.

An appropriate objective function for this problem is to Maximize total revenue Minimize total cost Maximize the total units of products produced. (A) The number of decision variables is _____________ (2) The number of constraints is _________________ (2)

Let X 1 be the units of product A made. Let X 2 be the number of units of product B made. Objective is to Maximize 200X 1 + 175X 2 Constraints are 10X 1 + 22X 2 ≤ 2640 (constraint on time availability on machine 1)

15X 1 + 18X 2 ≤ 2640 (constraint on time availability on machine 2) X 1 ≤ 150 (maximum quantity of product A made) X 1 , X 2 ≥ 0 (non negativity constraints) Consider the manpower requirement problem discussed in class. The day is divided into 24 one hour slots requirement for each hour is given. A person can start work at the beginning of any slot and works for 8 consecutive hours. 7. 8. 9. 10.

The objective function has _________ terms (24) The number of decision variables is __________ (24) The number of constraints is __________ (24) Each constraint has ____________ terms (8)

There will be 24 decision variables X 1 to X 24 that represent the number of people starting work at the beginning of each hour of the day. The objective function is to minimize the total number of people working. This will be to Minimize X 1 + X 2 + … + X 24 and will have 24 terms. There will be 24 constraints. Each constraint will be to meet the requirement of each hour. Each constraint will have 8 terms. For example, the requirement of hour 1 can be met by people starting work in hours 18 to 24 and 1 of the day. This is because each person works for 8 consecutive hours

Consider the media selection problem with n possible things to invest in. Examples could be TV, radio, newspaper etc. There is a total budget restriction and limit on investment in each. 11. The objective function has _________ terms (n) 12. The number of decision variables is __________ (n) 13. The number of constraints is __________ (n+1) The objective function tries to maximize the reach. It is of the form Maximize Σ C j X j where C j is the reach through vehicle j. There will be n terms in the objective function. There are n decision variables. X j is the amount invested in vehicle j. There is a limit on the investment on each vehicle. There are n constraints. In addition there is a total budget constraint. There will be n+1 constraints. Consider the napkins problem where the requirement is for 20 days. There are two types of laundries – fast and slow. The fast laundry takes 2 days (napkins sent at the end of day 1 can be used on day 3) and the slow laundry takes 3 days (napkins sent at the end of day 1 can be used on day 4). The costs of the new napkins and the two laundries are known. 14. The objective function has ___________ terms (55) 15. The total number of variables in the formulation is __________ (55)

16. The total number of constraints relating to the laundries is ___________ (18) 17. The constraint to meet the demand of day 10 will have __________ terms (25) The objective function Minimizes the sum of costs of new napkins, cost of laundry (slow and fast). There are three sets of decision variables, the number of new napkins used to meet the demand of day j, the number of napkins that have been received from slow laundry (includes earlier days and that day) used to meet the demand of day j and the the number of napkins that have been received from fast laundry (includes earlier days and that day) used to meet the demand of day j. The first set has 20 variables, one for each day. The variables corresponding to slow laundry are 17 (used from day 4, sent on days 1 to 17). The variables corresponding to fast laundry are 18 (used from day 3, sent on days 1 to 18). There are 20 + 17 + 18 = 55 variables. The objective function minimizes the cost corresponding to these 55 variables and has 55 terms. Since napkins are sent to fast laundry from days 1 to 18 and to slow laundry from days 1 to 17, the total number of days they are sent is 18. There are 18 constraints. The constraint to meet the demand of day 10 (on simplification) will have the ten variables for new napkins, 8 variables for fast laundry (sent from days 1 to 8) and 7 variables for the slow laundry (sent on days 1 to 7). There will be 10 + 8 + 7 = 25 terms

Consider the maximum flow problem with n nodes and m arcs. You are writing a formulation with f as the maximum flow. 18. The objective function has __________ terms (1) 19. The total number of variables is __________ (m+1) 20. The total number of constraints is ___________ (m+n) The objective function maximizes f, the flow. There is 1 term. There are as many variables as the number of arcs (m) and the variable f. There are m + 1 variables There are n node balance constraints and m arc capacity constraints. There are m + n constraints. Assignment 2 An investor has Rs 20 lakhs with her and considers three schemes to invest the money for one year. The expected returns are 10%, 12% and 15% for the three schemes per year. The third scheme accepts only up to 10 lakhs. The investor wants to invest more money in scheme 1 than in scheme 2. The investor assesses the risk associated with the three schemes as 0 units, 10 units and 20 units per lakh invested and does not want her risk to exceed 500 units. 1. Which of the following is the correct decision variable a) Amount of money invested in each scheme b) Amount of revenue obtained from each scheme c) Amount of risk through investment in each scheme

d) Total amount that can be obtained from the investments (A) 2. How many decision variables are in your formulation? (3) a) 1 b) 2 c) 3 d) 4 3. How many constraints are in your formulation? (4) a) 2 b) 3 c) 4 d) 5 4. How many greater than or equal to constraints are in your formulation. (To answer this question you should write your constraints such that the right hand side value is non negative) (1) a) 1 b) 2 c) 3 Let X 1 , X 2 , X 3 be the amount in lakhs invested in the three schemes. The objective is to maximize the total return – Maximize 10X 1 + 12X 2 + 15X 3 . The constraints are X 1 + X 2 X 3 ≤ 20 (Budget constraint) X 3 ≤ 10 (Limit on third scheme) X 1 ≥ X 3 (More money in scheme 1 than in scheme 2) 10X 2 + 20X 3 ≤ 500 (Risk constraint). Note that risk on scheme 1 is zero) X 1 , X 2 , X 3 ≥ 0 (non negativity) Two tasks have to be completed and require 10 hours and 12 hours of work if one person does the tasks. If n people do task 1, the time to complete the task becomes 10/n and so on. Similarly if n people do task 2, the time becomes 12/n and so on. We have 5 people and they have to be assigned to the two tasks. We cannot assign more than three to task 1. Find the earliest time that both tasks are completed if they start at the same time. (Use ideas from the bicycle problem to write your objective function. At some point you may have to define a variable to represent the reciprocal of another variable). Formulate an LP problem and answer the following: 5. The final objective function is a) Maximization problem with one term in the objective function (a) b) Minimization problem with one term in the objective function c) Maximization problem with two terms in the objective function d) Minimization problem with two terms in the objective function 6. The total number of constraints in the final formulation is (c) a) 1 b) 2 c) 3 d) 4

Let X 1 and X 2 be the number of people assigned to the two tasks. X 1 + X 2 ≤ 5 (limit on number of people) The times required are 10/X 1 and 12/X 2 . We wish to minimize the maximum of these two. Let u be the maximum of these two. The objective is to Minimize u subject to u ≥ 10/X 1 ; u ≥ 12/X 2 . These are rewritten as X 1 ≥ 10/u and X 2 ≥ 12/u. Put v = 1/u to get Minimize 1/v subject to X 1 + X 2 ≤ 5; X 1 ≥ 10v; X 2 ≥ 12v. Change the objective function to Maximize v so that we have an LP formulation. Add X 1 , X 2 ≥ 0.

TV sets are to be transported from three factories to three retail stores. The available quantities are 300, 400 and 500 respectively in the three factories and the requirements are 250, 350 and 500 in the three stores. They are first transported from the factories to warehouses and then sent to the retail stores. There are two warehouses and their capacities are 600 and 700 units. The unit costs of transportation from the factories to warehouses and from the warehouses to retail stores are known. Formulate an LP and answer the following questions: 7. The objective function (c) a) Maximizes the total cost of transportation between factories and warehouses and between warehouses and retail stores b) Maximizes the total quantity transported between factories and warehouses and between warehouses and retail stores c) Minimizes the total cost of transportation between factories and warehouses and between warehouses and retail stores d) Minimizes the total quantity transported between factories and warehouses and between warehouses and retail stores 8. The number of terms in the objective function is (c) a) 6 b) 8 c) 12 d) 18 9. The number of decision variables in the formulation is (c) a) 8 b) 10 c) 12 d) 18 10. The number of constraints in the formulation is (c) a) 6 b) 8 c) 10 d) 12

TVs are transported from three factories to two warehouses and from there to three retail stores. Let X ij be the quantity transported from factory i to warehouse j. There are six variables. Let Y ij be the quantity transported from warehouse j to store k. There are six variables. There are twelve decision variables. The objective function minimizes the transportation cost between the factories and warehouses as well as between warehouses and stores. There are 12 terms in the objective function corresponding to the 12 decision variables. There are 3 supply constraints for the factories. There are three demand constraints for the stores. There are 2 capacity constraints for the 2 warehouses. There are 2 quantity balance constraints for the two warehouses. There are 10 constraints. Thousand answer papers have to be totaled in four hours. There are 10 regular teachers, 5 staff and 4 retired teachers who can do the job. Regular teachers can total 20 papers in an hour; staff can do 15 per hour while retired teachers can do 18 per hour. The regular teachers total the papers correctly 98% of the times while this number is 94% and 96% for staff and retired teachers. We have to use the services of at least one staff. You can assume that any person can work for a fraction of an hour also. Formulate a relevant LP problem and answer the following questions. 11. Which of the following is a correct decision variable for this problem (b) a) Number of answer papers given to teachers 1 to 10 b) Total number of answer papers given to regular teachers c) Number of papers correctly totaled by regular teachers d) Number of papers incorrectly totaled by the regular teachers 12. A relevant objective function would be to a) Maximize the papers totaled by all of them in four hours b) Minimize the papers totaled by staff and retired teachers c) Minimize the number of papers correctly totaled by all of them d) Minimize the number of papers incorrectly totaled by all of them (d) 13. The number of decision variables in an efficient formulation is (a) a) 3 b) 4 c) 9 d) 19 14. The number of constraints in the formulation is (a) a) 5 b) 10 c) 19 d) 20 Let X 1 be the number of answer papers totaled by regular teachers, X 2 by staff and X 3 by retired teachers. The objective is to minimize the total number of incorrectly totaled papers. This would be to Minimize 2X 1 + 6X 2 + 4X 3 . The constraints are X 1 + X 2 + X 3 = 1000 (number of papers; this can also be a ≥ inequality) X 1 ≤ 800 (capacity of regular teachers, 20 x 4 x 10 = 800)

X 2 ≤ 300 (capacity of staff, 15 x 4 x 5 = 300) X 3 ≤ 300 (capacity of staff, 18 x 4 x 4 = 288) X 2 ≥ 75 (capacity of 1 staff) X 1 , X 2 , X 3 ≥ 0 (non negativity) A person is in the business of buying and selling items. He has 10 units in stock and plans for the next three periods. He can buy the item at the rate of Rs 50, 55 and 58 at the beginning of periods 1, 2 and 3 and can sell them at Rs 60, 64 and 66 at the end of the three periods. He can use the money earned by selling at the end of the period to buy items at the beginning of the next period. He can buy a maximum of 200 per period. He can borrow money at the rate of 2% per period at the beginning of each period. He can borrow a maximum of Rs 8000 per period and he cannot borrow more than Rs 20000 in total. He has to pay back all the loans with interest at the end of the third period. 15. What is the correct objective function for this problem? (c) a) Maximize the total money available at the end of the third period b) Maximize the total money at the end of the third period less total money borrowed c) Maximize the total money at the end of the third period less total money paid back including interest d) Maximize the number of items sold at the end of the third period 16. How many decision variables are in the formulation (c) a) 3 b) 6 c) 9 d) 10 17. How many constraints are in the formulation (d) a) 6 b) 9 c) 12 d) 13 Let X 1 , X 2 , X 3 be the number of items bought at the beginning of the three months. Let Y 1 to Y 3 be the number of items sold at the end of three months. Let Z 1 to Z 3 represent the amount of money borrowed at the beginning of three months The constraints are: X 1 ≤ 200; 50X 1 ≤ Z 1 ; Z 1 ≤ 8000. He sells Y 1 and realizes 60Y 1 . The relevant constraints are Y 1 ≤ X 1 + 10; He buys X 2 and borrows Z 2 . The constraints are X 2 ≤ 200, Z 2 ≤ 8000; 55X 2 ≤ 60Y 1 + Z 2 ; He sells Y 2 at the end of period 2 and realizes 64Y 2 . The constraint for Y 2 is Y 2 ≤ X 1 + 10 – Y 1 + X 2 (he can also sell items available at the end of period 1). He buys X 3 and borrows Z 3 . The constraints are X 3 ≤ 200; Z 3 ≤ 8000 and 58X 3 ≤ 60Y 1 + Z 2 – 55X 2 + 64Y 2 + Z 3 (He can also spend some unused money at the end of periods 1 and 2) Y 3 ≤ X 1 + 10 – Y 1 + X 2 – Y 2 There is a limit to the total money borrowed. This is given by Z 1 + Z 2 + Z 3 ≤ 20000. Also X 1 , X 2 , X 3 ≥ 0.

A food stall sells idlis, dosas and poories. A plate of idli has 2 pieces, a plate of dosa has 1 piece while a plate of poori has 2 pieces. They also sell a “combo” which has 2 idlis and 2 poories. A kg of batter costs Rs 60 and contains twelve spoons of batter. Each piece of idli requires 1 spoon of batter and each dosa requires 1.5 spoons of batter. Each poori piece requires 1 ball of wheat dough and a kg of wheat dough that costs Rs 60 can make 20 balls of dough. The selling prices of the items are Rs 40, 60, 60 and 90 per plate respectively. The owner has Rs 800 with her and estimates the demand for the four items (in plates) as 50, 30, 20 and 10 respectively. There is a penalty cost of Rs 10 for any unmet plate of demand of an item. Idli being the most commonly consumed item, the owner wishes to meet at least 80% of the demand. Formulate an LP problem and answer the following questions: 18. What is the most suitable objective function for this problem? (b) a) Maximize the total money earned by sale b) Maximize the total money earned by sale less the cost of items bought c) Maximize the total plates made of all the items d) Minimize the unmet demand 19. How many decision variables are in the formulation (4) a) 3 b) 4 c) 5 d) 8 20. How many constraints are in the formulation (d) a) 3 b) 4 c) 5 d) 6 Let X 1 to X 3 represent the number of plates of idlis, dosas and poories sold and let Y 1 be the number of plates of combo sold. There are 4 decision variables. The objective function is to maximize the total money earned by the sale less the cost of items purchased. The constraints are on total money available, limit on production quantities for four items and meeting minimum requirement of idlis. There are 6 constraints.

Unit 2: Graphical and Algebraic solutions Graphical solution Graphical solution – Example 2 Algebraic Solution Understanding the methods together 1. Consider the LP problem: Maximize 7X 1 + 6X 2 subject to X 1 + X 2 ≤ 4; 2X 1 + X 2 ≤ 6, X 1 , X 2 ≥ 0. The objective function corresponding to the optimum solution is _______ (26) The four corner points are (0, 0), (3, 0), (0, 4) and (2, 2). The best value is for (2, 2) which is 26 2. Consider the LP problem: Maximize 5X 1 + 8X 2 subject to 3X 1 + 4X 2 ≤ 12; 5X 1 + 2X 2 ≤ 20, X 1 , X 2 ≥ 0. The objective function corresponding to the optimum solution is _______ (24) The three corner points are (0, 0), (4, 0), (0, 3). The best value is for (0,3) and the value is 24. 3. Consider the LP problem: Maximize 5X 1 + 8X 2 subject to 4X 1 + 5X 2 ≤ 20; 3X 1 + 2X 2 ≤ 12, X 1 + 2X 2 ≥ 3, X 1 , X 2 ≥ 0. The number of corner points in the graphical solution is _______ (5) The corner points are (3, 0), (4, 0), (20/7, 12/7), (0, 4) and (0,3/2) 4. Consider the LP problem: Maximize 5X 1 + 8X 2 subject to 3X 1 + 4X 2 ≤ 16; 5X 1 + 2X 2 ≤ 12, X 1 , X 2 ≥ 0. The corner point obtained by solving 3X 1 + 4X 2 = 16 and 5X 1 + 2X 2 = 12 is: (Ans = 8/7, 22/7) 3X 1 + 4X 2 = 16; 10X 1 + 4X 2 = 24. Solving, 7X 1 = 8; X 1 = 8/7 and X 2 = 22/7) 5. Consider the LP problem: Maximize 5X 1 + 8X 2 subject to 2X 1 + 3X 2 ≤ 8; 2X 1 + 3X 2 ≥ 1, X 1 , X 2 ≥ 0. The corner point that gives the optimum solution is: (Ans = 0,8/3) The corner points are (0, 0), (4, 0) and (0, 8/3). The best value of 64/3 is obtained for (0, 8/3) 6. Consider the LP problem: Maximize 7X 1 + 6X 2 subject to X 1 ≤ 4; X 1 - X 2 ≥ 0, X 1 , X 2 ≥ 0. The objective function corresponding to the optimum solution is _______ (52) The corner points are (0, 0), (4, 0) and (4, 4). The best value is for (4, 4) = 52

7. Consider the LP problem: Maximize 5X 1 + 8X 2 subject to 2X 1 + 3X 2 ≤ 8; 2X 1 + 3X 2 ≤ 1, X 1 , X 2 ≥ 0. Which of the following is true (b) a) The LP is unbounded b) The LP is infeasible c) The corner point (0,0) is optimum d) The corner point (4,0) is optimum The LP is infeasible 8. Consider the LP problem: Maximize 5X 1 + 8X 2 subject to X 1 ≤ 4; X 1 - 3X 2 ≤ 0, X 1 , X 2 ≥ 0. Which of the following is true (a) a) The LP is unbounded b) The LP is infeasible c) The corner point (0,0) is optimum d) The corner point (4,0) is optimum The LP is unbounded 9. Consider the LP problem: Minimize 5X 1 + 8X 2 subject to X 1 + X 2 ≤ 6; X 1 + X 2 ≥ 2; X 1 X 2 ≤ 2, X 1 - X 2 ≥ -2 X 1 , X 2 ≥ 0. The objective function value at optimum is ____ (10) The corner points are (2, 0), (4, 2), (2, 4) and (0, 2). The best value of 10 (minimum) is at (2, 0). 10. Consider the LP problem: Minimize 2X 1 - 3X 2 subject to X 1 + X 2 ≤ 4; 2X 1 + X 2 ≥ 2; X 1 + 2X 2 ≤ 6, X 1 , X 2 ≥ 0. The objective function value at optimum is ____ (-9) The corner points are (1, 0), (4, 0), (2, 2), (0, 3). The best value is -9 and is for (0, 3) Assignment 2 Consider the LP problem: Maximize 7X 1 + 6X 2 subject to X 1 + X 2 ≤ 4; 2X 1 + X 2 ≤ 6, X 1 , X 2 ≥ 0. Solve by algebraic method and answer the following: 1. The number of basic solutions is _______ (6) 2. The number of basic feasible solutions is _______ (4) 3. If we solve for X 1 and X 3 as basic and the other variables as non basic, the value of X 2 is __________ (0) 4. If we solve for X 2 and X 3 as basic and the other variables as non basic, the value of X 3 is __________ (-2) There are 4 variables and 2 constraints. There are 4C 2 = 6 basic solutions. The four corner points (0, 0), (3, 0), (0, 4) and (2, 2) are the four basic feasible solutions. When we solve for X 1 and X 3 , X 2 is non basic and has value zero. We solve for X 2 and X 3 . The equations are X 2 + X 3 = 4 and X 2 = 6. This gives X 3 = -2

Consider the LP problem: Maximize 7X 1 + 6X 2 + 4X 3 subject to X 1 + X 2 + X 3 ≤ 5; 2X 1 + X 2 + 3X 3 ≤ 10, X 1 , X 2 , X 3 ≥ 0. Solve by algebraic method and answer the following: 5. The number of basic solutions is _______ (10) 6. The number of basic infeasible solutions is _______ (2) 7. If we solve for X 2 and X 3 as basic and the other variables as non basic, the value of X 3 is __________ (5/2 or 2.5) 8. The number of unique basic feasible solutions is __________ (5) 9. The optimum solution has X 1 = _______ (5) 10. The value of the objective function at optimum is ________ (35) There are 2 constraints resulting in two slack variables. The number of variables is 5 and the number of constraints is 2. There are 5C 2 = 10 basic solutions. The ten basic solutions are X 1 = 5, X 2 = 0; X 1 = 5, X 3 = 0; X 1 = 5, X 4 = 0; X 1 = 5, X 5 = 0; X 2 = 5/2, X 3 = 5/2; X 2 = 10, X 4 = -5; X 2 = 5, X 5 = 5; X 3 = 10/3, X 4 = 5/3; X 3 = 5, X 5 = - 5 and X 4 = 5, X 5 = 10; Out of these two are infeasible. When we solve for X 2 and X 3 , the solution is X 2 = 5/2, X 3 = 5/2. Out of the 8 basic feasible solutions, five are unique. Three solutions repeat. The optimum solution is when X 1 = 5 and Z = 35 Consider the LP problem: Minimize 6X 1 + 5X 2 subject to X 1 + X 2 ≥ 3; 2X 1 + X 2 ≥ 5, X 1 , X 2 ≥ 0. Solve by algebraic method and answer the following: 11. The number of basic solutions is _______ (6) 12. The number of basic feasible solutions is _______ (3) 13. If we solve for X 1 and X 3 as basic and the other variables as non basic, the value of X 1 is __________ (5/2 or 2.5) 14. The optimum solution has X 1 = ______ (2) 15. The value of objective function at optimum is ________ (17) There are two constraints resulting in two negative slack variables. There are 4 variables in total and 2 constraints resulting in 4C 2 = 6 basic solutions. The six solutions are X 1 = 2, X 2 = 1; X 1 = 5/2, X 3 = -1/2; X 1 = 3, X 4 = 1; X 2 = 5, X 3 = 2; X 2 = 3, X 4 = -2; X 3 = -3, X 4 = -5; Three solutions are basic feasible. When we solve for X 1 , X 3 , we have the equations X 1 – X 3 = 3; 2X 1 = 5, which gives the solution X 1 = 5/2, X 3 = -1/2. The value of X 1 = 5/2. The optimum solution is X 1 = 2, X 2 = 1 with Z = 17.

Unit 3: Simplex Algorithm Algebraic form of simplex Tabular form of simplex Minimization problems Types of LPs and simplex solutions Matrix method for simplex 1. Consider the LP problem Maximize 3X 1 + 8X 2 subject to 3X 1 + 5X 2 ≤ 16; 5X 1 + 3X 2 ≤ 12, X 1 , X 2 ≥ 0. In the simplex algorithm, the variables that enters first is ___ and this variable replaces variable ____(Ans = X 2 , X 3 ) In the first table, C 1 – Z 1 = 3; C 2 – Z 2 = 8. Variable X 2 with the highest C j – Z j enters. The ratios are 16/5 and 4. Variable X 3 with minimum ratio leaves. 2. Consider the LP problem Minimize 3X 1 + 8X 2 subject to 3X 1 + 5X 2 ≥ 16; 5X 1 + 3X 2 ≥ 12, X 1 , X 2 ≥ 0. The number of artificial variables required to initialize the simplex table is ___ (Ans = 2) Both the constraints are of the ≥ type and require artificial variables. We require two artificial variables 3. Consider the LP problem Minimize 3X 1 + 8X 2 + 3X 3 +7X 4 subject to 3X 1 + 5X 2 + X 3 ≥ 16; 5X 1 + 3X 2 – X 4 ≥ 12, X 1 , X 2 , X 3 , X 4 ≥ 0. The number of artificial variables required to initialize the simplex table is ___ (Ans = 1) The first constraint is of the ≥ type. Since X 3 has a +1 coefficient in the first constraint and is not in the second constraint, we do not need an artificial variable here. We require an artificial variable to initialize the second constraint which is also of ≥ type. 4. Consider the LP problem Minimize 3X 1 + 8X 2 subject to 3X 1 + 5X 2 ≥ 16; 5X 1 + 3X 2 ≥ 12, X 1 , X 2 ≥ 0. The number of variables in the simplex table for this problem is ____. (Ans = 6) Both the constraints are of the ≥ type. We will have two negative slack variables and two artificial variables. There are 6 variables in the simplex table. Consider the LP problem: Maximize 7X 1 + 6X 2 subject to X 1 + X 2 ≤ 4; 2X 1 + X 2 ≤ 6, X 1 , X 2 ≥ 0. Solve using the algebraic form of the simplex algorithm and answer the following: 5. At the end of the first iteration, the objective function coefficient for X 2 is ____ (5/2 or 2.5) 6. When X 2 enters the solution, the value it takes is ______ (2) 7. At the optimum, the coefficient of variable X 3 in the objective function is ______ (-5)

At the end of first iteration, the equations are X 1 = 3 – X 2 /2 – X 4 /2. X 3 = 1 – X 2 /2 – X 4 /2 and Z = 21 + 5X 2 /2 -7X 4 /2. The coefficient of X 2 is 5/2. X 2 enters the solution. The ratios are 6 and 2. The minimum value is 2 and X 2 = 2. The equations are X 2 = 2 – 2X 3 + X 4 ; X 1 = 2 + X 3 – X 4 ; Z = 26 – 5X 3 – X 4 . Solve the LP problem Maximize 3X 1 + 8X 2 subject to 3X 1 + 5X 2 ≤ 16; 5X 1 + 3X 2 ≤ 12, X 1 , X 2 ≥ 0 using the simplex algorithm. 8. The number of iterations taken by simplex algorithm is ________ (2) 9. The optimum solution has X 2 = _____ (16/5 or 3.2) 10. The value of objective function at optimum is _______ (128/5 or 25.6) The initial basic variables are X 3 and X 4 . The solution is X 3 = 16, X 4 = 12. Variable X 2 enters and replaces X 3 . The solution is X 2 = 16/5, X 4 = 12/5 with Z = 128/5. Simplex takes 2 iterations.

Assignment 2 Solve the LP problem Maximize 4X 1 + 3X 2 + 5X 3 subject to X 1 + X 2 + X 3 ≤ 10; 2X 1 + X 2 + 3X 3 ≤ 20, 3X 1 + 2X 2 + 4X 3 ≤ 30 X 1 , X 2 , X 3 ≥ 0 using the simplex algorithm and answer the following questions. If you have a tie to decide a leaving variable, break the tie arbitrarily. 1. 2. 3. 4. 5.

What is the value of the objective function at the optimum (40) How many variables are there in the initial Simplex table (6) How many iterations, after the initial table did you take to reach the optimum (2) How many basic variables have a positive value at the optimum (2) How many C j – Z j values are zero at the optimum (4)

The three ≤ constraints result in three slack variables. There are 6 variables in the simplex table including the three decision variables and 3 slack variables. After the initial table, there were two iterations to reach the optimum. The optimum solution (solution after two iterations) has X 2 = X 3 = 5 and X 6 = 0. Two basic variables have positive value. The value of objective function is 40. At the optimum C 1 – Z 1 = C 2 – Z 2 = C 3 – Z 3 = C 6 - Z 6 = 0. C 4 – Z 4 = -2 and C 5 – Z 5 = -1. Four variables have C j – Z j = 0.

In the optimum table, you would observe that a non basic variable has a zero value of C j – Z j while others have negative values. So far all non basic variables C j – Z j values were negative at the optimum. Try and enter this variable and continue with the simplex iteration.

6. What is the value of the objective function after the iteration? (40) 7. How many basic variables have a zero value? (2) 8. Is there a non basic variable with zero value for C j – Z j (a) a) Yes b) No Since optimum is reached and non basic variable X 1 has C 1 – Z 1 = 0, we enter X 1 . There ia a tie between X 2 and X 3 for the leaving variable. We break it arbitrarily by choosing X 2 . The solution now is X 1 = 10; X 3 = X 6 = 0 with Z = 40. We also have C 1 – Z 1 = C 2 – Z 2 = C 3 – Z 3 = C 6 Z 6 = 0. C 4 – Z 4 = -2 and C 5 – Z 5 = -1.

Solve the LP problem Maximize 9X 1 + 3X 2 + 5X 3 subject to 4X 1 + X 2 + X 3 ≤ 12; 2X 1 + 4X 2 + 3X 3 ≤ 22, 5X 1 + 2X 2 + 4X 3 ≤ 34 X 1 , X 2 , X 3 ≥ 0 using the simplex algorithm and answer the following questions. 9. The value of the objective function at the optimum is _____ (223/5 or 44.6) 10. The number of iterations taken by simplex (after the initial table) to reach the optimum is _____ (2) 11. The set of basic variables at the optimum is (c) a) X 1 X 2 X 6 b) X 1 X 3 X 5 c) X 1 X 3 X 6 d) X 2 X 3 X 6 The initial solution is X 4 = 12, X 5 = 22 and X 6 = 34. Variable X 1 with C 1 – Z 1 = 9 enters and replaces variable X 4 . After an iteration, the solution is X 1 = 3, X 5 = 16 and X 6 = 19 with Z = 27. Variable X 3 with C 3 – Z 3 = 11/4 enters replacing variable X 5 with minimum ratio = 32/5. The optimum solution is found with X 1 = 7/5, X 3 = 32/5, X 6 = 7/5 with Z = 223/5. Solve the LP problem using Simplex algorithm Minimize 9X 1 + 3X 2 subject to 4X 1 + X 2 ≥ 12; 2X 1 + 4X 2 ≥ 22, 5X 1 + 2X 2 ≤ 34; X 1 , X 2 , X 3 ≥ 0 using the simplex algorithm and answer the following questions. 12. The value of the objective function at the optimum is (c) a) 27 b) 33/2 c) 213/7 d) 216/7 13. The set of basic variables at the optimum is (c) a) X 1 X 2 X 3 b) X 1 X 3 X 5 c) X 1 X 2 X 5 d) X 2 X 3 X 5

We add two artificial variables to the two ≥ constraints. There are 3 slack variables and there is a total of 7 variables in the simplex table. The initial solution is a 1 = 12, a 2 = 22 and X 5 = 34. Variable X 1 with C j – Z j = 6M-5 enters and replaces a 1 with a minimum ratio of 3. The new solution is X 1 = 3, a 2 = 16, X 5 = 19. Variable X 2 with C 2 – Z 2 = 7M/2 – ¾ enters and replaces variable a 2 with minimum ratio = 32/7. The optimum solution is X 1 = 13/7, X 2 = 32/7, X 5 = 109/7 with Z = 213/7 for the minimization problem.

Solve the LP problem using Simplex algorithm Minimize 9X 1 + 3X 2 subject to 4X 1 + X 2 ≥ 12; 7X 1 + 4X 2 ≤ 16; X 1 , X 2 ≥ 0 using the simplex algorithm. 14. Which of the following is the correct answer a) The optimum solution is (0, 4) b) The problem is unbounded c) The problem is infeasible with simplex showing artificial variable a 1 = 20/7 at optimum d) The problem is infeasible with simplex showing artificial variable a 1 = 3 at optimum We introduce artificial variable a 1 in the first constraint. The initial table has a 1 = 12, X 4 = 16. Variable X 1 with C j – Z j = 4M – 9 enters and replaces X 4 with minimum ratio of 16/7. The solution now is a 1 = 20/7, X 1 = 16/7 and the optimality condition is satisfied. The solution to the LP is infeasible with a 1 = 20/7 Solve the LP problem using Simplex algorithm Minimize 2X 1 + 3X 2 subject to X 1 + X 2 ≥ 4; X 1 ≤ 1; X 1 , X 2 ≥ 0 using the simplex algorithm. 15. The value of the objective function at the optimum is _____ (11) 16. The value of X 2 at the optimum is ____ (3) 17. If we add the constraint 2X 1 + 3X 2 ≤ 11 (a) a) The optimum solution remains the same b) The problem becomes infeasible c) The problem becomes unbounded d) The optimum solution changes We introduce artificial variable a 1 in the first constraint. The initial table has a 1 = 4, X 4 = 1. Variable X 1 with C j – Z j = M – 2 enters and replaces X 4 with minimum ratio of 1. The solution now is a 1 = 3, X 1 = 1. Variable X 2 enters the solution with C 2 – Z 2 = M – 3 and replaces a 1 . The optimum solution X 2 = 3, X 1 = 1 with Z = 11 (minimization) is reached at this stage. The constraint 2X 1 + 3X 2 ≤ 11 is satisfied by the present solution. Therefore the optimum solution remains the same.

Solve the LP problem using Simplex algorithm Minimize 2X 1 + 3X 2 subject to X 1 + X 2 ≥ 4; 2X 1 +4X 2 ≥ 10; X 1 , X 2 ≥ 0 using the simplex algorithm. 18. The value of the objective function at the optimum is ____ (9) 19. The value of X 2 at the optimum is ___ (1) We add two artificial variables to the two ≥ constraints. There are 2 slack variables and there is a total of 6 variables in the simplex table. The initial solution is a 1 = 4, a 2 = 10. Variable X 2 with C j – Z j = 5M-3 enters and replaces a 2 with a minimum ratio of 5/2. The new solution is a 1 = 3/2, X 2 = 5/2,. Variable X 1 with C 1 – Z 1 = M/2 – 2 enters and replaces variable a 1 with minimum ratio = 3. The optimum solution is X 1 = 3, X 2 = 1, with Z = 9 for the minimization problem. Solve the LP problem using Simplex algorithm Minimize X 1 - X 2 subject to X 1 + X 2 ≥ 7; X 1 ≤ 10; X 1 , X 2 ≥ 0 using the simplex algorithm. 20. Which of the following is TRUE (b) a) The problem is infeasible b) The problem is unbounded c) X 1 = 7 is the optimum solution d) X 2 = 0 is optimum We introduce artificial variable a 1 in the first constraint. The initial table has a 1 = 7, X 4 = 10. Variable X 2 with C j – Z j = M + 1 enters and replaces a 1 with minimum ratio of 7. The solution now is X 2 = 7, X 4 = 10 with Z = 7. Variable X 3 with C 3 – Z 3 = 1 can enter but there is no leaving variable. The problem therefore is unbounded.

Unit 4: Duality Dual of an LP Writing the dual Duality Results Complimentary slackness theorem 1. The dual of the dual is the ________ Ans: Primal 2. The primal has m constraints and n variables. The dual has ___ constraints and ___ variables Ans: n and m 3. If a primal constraint is an equation, the corresponding dual variable is Ans: unrestricted 4. Every feasible solution to the dual (minimization problem) has an objective function greater than or equal to that of every feasible solution to the primal. This theorem is called the (a) Weak duality theorem (b) Optimality criterion theorem (c ) Main duality theorem (d) Complimentary slackness theorem Ans = a 5. In the optimum solution, if a primal constraint is satisfied as an equation, the value of the corresponding dual variable is ___ Ans: 0 6. In the optimum solution, if a primal variable is basic then the corresponding dual slack value is ___ Ans: 0 7. If the kth variable in a minimization (primal) is ≥ 0, the kth constraint in the dual is an inequality of the ___ type Ans: ≥ 8. If the primal (maximization) is unbounded the corresponding dual is _______ Ans: infeasible 9. If the primal (maximization) has an objective function value of 100 at the optimum, which of the following is TRUE

(a) (b) (c) (d)

Dual has an objective function value greater than 100 at optimum Dual has an objective function value lesser than 100 at optimum Dual has an objective function value equal to 100 at optimum Dual’s objective function value at optimum does not depend on the objective function value of the primal Ans = c 10. Consider the LP Maximize 9X 1 + 3X 2 subject to 4X 1 + X 2 ≤ 12; 2X 1 + 4X 2 ≤ 22, X 1 , X 2 ≥ 0. Solve the primal using the graphical method. Is a dual solution Y 1 = 15/7, Y 2 = 3/14 optimum? a) It is not optimum to the dual because it is not feasible to the dual b) The dual solution is feasible but not optimum because the objective function value is different from that of the primal c) It is optimum using the optimality criterion theorem d) Weak duality theorem is violated. The optimum solution to the primal is X 1 = 13/7, X 2 = 32/7, Z = 231/7. The given solution to the dual is feasible and has an objective function value of 213/7. It is optimum to the dual based on the optimality criterion theorem. 11. Consider the LP Maximize 7X 1 + X 2 subject to X 1 + X 2 ≤ 3; X 1 + X 2 ≥ 2, X 1 , X 2 ≥ 0. Solve this primal. Use ideas from complimentary slackness and indicate which of the following is TRUE (d) a) The dual will have an objective function not greater than 20 at the optimum b) The dual is unbounded or infeasible c) Y 1 and Y 2 are basic at the optimum for the dual d) Y 2 = 0 at the optimum for the dual The optimum solution to the primal is X 1 = 3 with Z = 21. Options a and b are not true. The second primal constraint is satisfied as an inequality. Therefore Y 2 = 0 at optimum. Ans = d 12. Consider the LP Maximize 7X 1 + X 2 subject to X 1 + X 2 ≤ 3; X 1 + X 2 ≥ 2, X 2 ≥ 0, X 1 unrestricted. Which of the following is NOT TRUE about the dual (b) a) The first constraint is an equation b) The second constraint is an equation c) The second variable is of ≤ type d) The dual has two variables and two constraints The dual is Minimize 3Y 1 + 2Y 2 subject to Y 1 + Y 2 = 7; Y 1 + Y 2 ≥ 3; Y 1 ≥ 0, Y 2 ≤ 0. All except b are true. Ans = b

Given the LP problem Maximize 3X 1 + 5X 2 + 9X 3 subject to X 1 + X 2 + 2X 3 ≤ 6; 2X 1 + 3X 2 + X 3 ≤ 8, X 1 , X 2 , X 3 ≥ 0 13. The dual has ___________ variables (2) 14. The solution X 3 = 3 X 5 = 5 is optimum to the primal (Apply complimentary slackness) a) True b) False 15. The solution X 1 = 2, X 2 = 1, X 3 = 1 is optimum (b) a) TRUE b) FALSE 16. The solution X 2 = X 3 = 2 is optimum to the primal. (Apply complimentary slackness) (a) a) TRUE b) FALSE The dual is Minimize 6Y 1 + 8Y 2 subject to Y 1 + 2Y 2 ≥ 3, Y 1 + 3Y 2 ≥ 5, 2Y 1 + Y 2 ≥ 9, Y 1 , Y 2 ≥ 0. The optimum solution to the dual is Y 1 = 22/5, Y 2 = 1/5 with W = 28. By complimentary slackness theorem, variables X 2 and X 3 are in the primal optimum solution because the second and third dual constraints are satisfied as equation. We get X 2 + 2X 3 = 6; 3X 2 + X 3 = 8 which gives X 2 = X 3 = 2 at the optimum with Z = 28.

Unit 5: Understanding the dual Significance of the dual Interpretation of the dual Dual problem and the simplex table Dual Simplex algorithm 1. The dual variable is also called the _____ of the resource at the optimum Ans: shadow price, marginal value . 2. Consider the LP problem: Maximize 5X 1 + 8X 2 subject to 3X 1 + 4X 2 ≤ 16; 5X 1 + 2X 2 ≤ 12, X 1 , X 2 ≥ 0. The optimum solution is the corner point on the y axis. The value of the objective function is: (Ans = 32) Since the optimum solution is a corner point on the y axis, X 1 = 0. The corner point is (0, 4) with Z = 32

3. Consider the LP problem: Maximize 3X 1 + 8X 2 subject to 3X 1 + 4X 2 ≤ 16; 5X 1 + 2X 2 ≤ 12, X 1 , X 2 ≥ 0. The optimum solution to this problem is (0,4). The value of the first dual variable y 1 at optimum is_____. (Ans = 2)

The optimum solution to primal is (0,4). The first constraint is satisfied as an equation and the second as inequality. Y 1 is in the solution and Y 2 = 0. The dual is Minimize 16Y 1 + 12Y 2 subject to 3Y 1 + 12Y 2 ≥ 3; 4Y 1 + 2Y 2 ≥ 8; Y 1 , Y 2 ≥ 0; This gives Y 1 = 2. 4. Consider the LP problem: Maximize 3X 1 + 8X 2 subject to 3X 1 + 4X 2 ≤ 16; 5X 1 + 2X 2 ≤ 12, 5X 1 + 9X 2 ≤ 25, X 1 , X 2 ≥ 0. The optimum solution is given by (0, 25/9). Only one resource has a positive value of shadow price. Which one? (Ans = third) There are three resources. Substituting (0, 25/9), we have the first two constraints satisfied as inequality and the third as equation. This means that the first two resources have a shadow price of zero and the third alone has a positive value. 5. Consider the LP problem: Maximize 3X 1 + 8X 2 subject to 3X 1 + 4X 2 ≤ 16; 5X 1 + 2X 2 ≤ 12, 5X 1 + 9X 2 ≤ 25, X 1 , X 2 ≥ 0. The optimum solution is given by (0, 25/9). Is the solution (0, 0, 6) optimum to the dual? (Ans = No) The objective function value at optimum of primal is 200/9. The dual is given by Minimize 16Y 1 + 12Y 2 + 25Y 3 subject to 3Y 1 + 5Y 2 + 5Y 3 ≥ 3; 4Y 1 + 2Y 2 + 9Y 3 ≥ 8, Y 1 , Y 2 , Y 3 ≥ 0. The solution (0, 0, 6) is feasible and has objective function value = 150. Since the objective function values are not equal, it is not optimum to dual. 6. Consider a primal (maximization) with 2 variables and three constraints (inequalities). At least ____ resource(s) will have a shadow price of zero. (Ans = 1) Since there are three constraints and two variables, at least one slack variable has to be in the optimum solution. Therefore at least one dual variable will have value zero at optimum. 7. The dual simplex algorithm indicates infeasibility by a) There is no leaving variable b) There is a leaving variable and no entering variable c) There is an entering variable and no leaving variable Ans = b 8. You are given an LP problem with three variables and two constraints. You have to find the value of the objective function at the optimum. Which of the following is the best way to do it using hand calculations? (b) a) It is possible to write the dual and solve it using graphical method. The value of the objective function at the dual is the same as that of the primal b) Write the dual and solve it by graphical method. Apply complimentary slackness to find the primal solution and then evaluate the objective function. c) Solve the given primal by simplex algorithm d) Use algebraic method.

Ans = a. This is the best of the four ways. All four methods can be used. Write the LP dual to the problem. Minimize 2X 1 + 3X 2 subject to X 1 + X 2 ≥ 4; 2X 1 +4X 2 ≥ 10; X 1 , X 2 ≥ 0. 9. The shadow price of the first resource is___________ (1) 10. The shadow price of the second resource is ___________ (1/2 or 0.5) The dual is Maximize 4Y 1 + 10Y 2 subject to Y 1 + 2Y 2 ≤ 2; Y 1 + 4Y 2 ≤ 3; Y 1 , Y 2 ≥ 0. The optimum solution is Y 1 = 1, Y 2 = ½.

Assignment 2 Consider the LP Maximize 2X 1 + 3X 2 + 4X 3 + X 4 subject to X 1 + 2X 2 +5X 3 + X 4 ≤ 12. X j ≥ 0. Solve the dual and find the optimum solution to the primal. 1. The value of the objective function at the optimum is ____ (24) 2. Which of the statements is TRUE? (Ans = d) a) A single constrained LP can have more than one variable taking non zero value at the optimum b) The variable with the largest coefficient in the objective function is the only variable with a non zero value in the optimum solution. c) The variable with the smallest coefficient in the constraint is the only variable with a non zero value in the optimum solution. d) The variable with the largest ratio of the objective function coefficient to constraint coefficient is the only variable with a non zero value in the optimum solution. 3. Only 11 units of the resource is available. The value of the objective function at optimum is ___________ (22) 4. The shadow price of the resource is _____ (2) 5. If 100 units of the resource are available, the value of the objective function at optimum is _______ (200) The dual has only one variable. The dual is Minimize 12Y 1 subject to Y 1 ≥ 2; 2Y 1 ≥ 3; 5Y 1 ≥ 4; Y 1 ≥ 1; Y 1 ≥ 0; The optimum solution is Y 1 = 2 with W = 24. The value of objective function of the primal at optimum is 24. A single constrained LP will have only one variable in the solution. This is the variable with the largest ratio of C j /a j .

When 11 units of resource is available dual objective is 11Y 1 . Value of objective function is 22. Shadow price is the value of the dual = 2. If 100 units of resources are available, the objective function becomes 100Y 1 and the value is 200 Consider the LP problem: Maximize 5X 1 + 12X 2 subject to 2X 1 + 5X 2 ≤ 13; 7X 1 + 11X 2 ≤ 31, X 1 , X 2 ≥ 0. Solve this problem using Simplex algorithm and answer the following: 6. The objective function value after first iteration is ____ (31.2 or 156/5). 7. Which of the following is NOT TRUE (d) a) This solution is not optimum because a variable can enter the basis and increase the objective function further b) The solution is not optimum because the corresponding dual solution after applying complimentary slackness conditions is infeasible c) The variable y 1 is in the solution when the dual is solved after applying complimentary slackness d) The variable y 2 is in the solution when the dual is solved after applying complimentary slackness 8. At the optimum, which of the following is NOT TRUE (Multiple choices may be the correct answer) (c and d) a) The value of the objective function is 408/13 b) Variables X 1 and X 2 are in the basis c) The dual has variables Y 1 and Y 3 in the basis d) The shadow price of the first primal resource is zero. We start simplex table with X 3 = 13, X 4 = 31 and Z = 0. Variable X 2 enters and replaces X 3 with minimum ratio = 13/5. The solution is X 2 = 13/5, X 4 = 12/5 and Z = 156/5. Variable X 1 enters with C j – Z j = 1/5 and replaces X 4 with minimum ratio 12/13. The optimum solution is X 2 = 29/13, X 1 = 12/13 with Z = 408/13. At the end of the first iteration, Y 1 = 12/5, Y 2 = 0. Therefore d is NOT TRUE. In the optimum iteration, Y 1 = 29/13, Y 2 = 1/13. C and d are NOT TRUE. Consider a two variable LP problem with a minimization objective function and three constraints all of the ≥ type. The first constraint cuts the X 1 and X 2 axes at 2 and 7 respectively. The second constraint cuts the two axes at 3 and 5 respectively and the third constraint at 4 and 4 respectively. The objective function is 3X 1 + 2X 2 . 9. Which of the following is not a valid constraint for this problem (b) a) 7X 1 + 2X 2 ≥ 14 b) 4X 1 + 5X 2 ≥ 20 c) 5X 1 + 3X 2 ≥ 15 d) X 1 + X 2 ≥ 4

10. Which of the following is not a corner point for the feasible region (a) a) (0,0) b) (4,0) c) (12/11, 35/11) d) (3/2, 5/2) 11. The optimum solution to the primal is (d) a) (4, 0) b) (0, 7) c) (12/11, 35/11) d) (3/2, 5/2) 12. The dual has _________ variables (3) 13. The optimum solution to the dual is (c) a) Y 1 = Y 2 = 0 b) Y 1 = 2, Y 2 = 0, Y 3 = 0 c) Y 2 = Y 3 = ½ d) Y 1 = 1/5, Y 3 = 8/5 From the points given, the three constraints are 7X 1 + 2X 2 ≥ 14; 5X 1 + 3X 2 ≥ 15 and X 1 + X 2 ≥4. The incorrect constraint is 4X 1 + 5X 2 ≥ 20. There are 4 corner points. These are (4, 0), (0, 7), (3/2, 5/2) and (12/11, 35/11). The point (0,0) is not a feasible corner point. The optimum solution is (3/2, 5/2) with Z = 19/2 (minimization). Since the primal has 3 constraints, the dual has three variables. The dual is Maximize 14Y 1 + 15Y 2 + 4Y 3 ; subject to 7Y 1 + 5Y 2 + Y 3 ≤ 3; 2Y 1 + 3Y 2 + Y 3 ≤ 2; Y 1 , Y 2 , Y 3 ≥ 0; The optimum solution to the dual is Y 2 = Y 3 = ½ with W = 19/2. Solve the LP problem using Dual Simplex algorithm without artificial variables Minimize 9X 1 + 3X 2 subject to 4X 1 + X 2 ≥ 12; 2X 1 + 4X 2 ≥ 22, 5X 1 + 2X 2 ≤ 34; X 1 , X 2 , X 3 ≥ 0 . 14. The first variable to leave the basis is (b) a) X 3 b) X 4 c) X 5 d) X 1 15. The first entering variable and the corresponding minimum ratio are: (d) a) X 1 with 9/4 b) X 1 with 9/2 c) X 2 with 3

d) X 2 with ¾ 16. The value of X 5 at the optimum is (b) a) 0 b) 109/7 c) 100/7 d) 12/7 17. The value of C 3 – Z 3 at the optimum table is (c) a) 0 b) 3/14 c) 15/7 d) 12/7 We apply the dual simplex algorithm. The initial solution is X 3 = -12, X 4 = -22 and X 5 = 34. Variable X 4 leaves the basis and variable X 2 enters with ratio ¾. The solution is X 3 = -13/2, X 2 = 11/2 and X 5 = 23. Variable X 3 with a negative value leaves the basis and is replaced by X 1 with ratio 15/7. The optimum solution is X 1 = 13/7, X 2 = 32/7 and X 5 = 109/7 and Z = 213/7. The value of C 3 – Z 3 at optimum is 15/7. Solve the LP problem using Dual Simplex algorithm without artificial variables Minimize X 1 + X 2 subject to X 1 + 3X 2 ≥ 7; 7X 1 + 2X 2 ≥ 12, X 1 , X 2 , X 3 ≥ 0 . 18. The first entering variable is (a) a) X 1 b) X 2 c) X 3 d) X 4 19. The second variable to enter the basis and the corresponding ratio are (d) a) X 1 with 1 b) X 1 with 10/19 c) X 2 with 2 d) X 2 with 5/19 20. The dual solution at the optimum is (a) a) Y 1 = 5/19, Y 2 = 2/19 b) Y 1 = 2/19, Y 2 = 5/19 c) Y 1 = 0, Y 2 = 1/7 d) Y 1 = 1/7, Y 2 = 0

The initial solution is X 3 = -7, X 4 = -12. Variable X 4 leaves the solution and variable X 1 enters with ratio 1/7. The solution is X 3 = -37/7, X 1 = 12/7. Variable

X 3 leaves the solution and is replaced by X 2 with ratio 5/19. The optimum solution is reached with X 1 = 22/19, X 2 = 37/19 and Z = 59/19. The dual values from the C j – Z j at optimum are Y 1 = 5/19, Y 2 = 2/19.

Unit 6: Transportation problem Balanced transportation problem Starting solutions Vogel’s approximation method Optimization Modified Distribution method Dual of the transportation problem Additional points and interpretation Solving the transportation problem using solver 1. Consider a transportation problem with 3 supply points and 4 demand points. The number of variables in the formulation is (a) 3 (b) 4 (c) 7 (d) 12 Ans = d 2. Consider a transportation problem with 3 supply points and 4 demand points. The number of constraints in the formulation is (a) 3 (b) 4 (c) 7 (d) 12 Ans = c 3. In a m x n balanced transportation problem the number of allocations in a non degenerate basic feasible solution is (a) m (b) n (c) mn (d) m+n-1 Ans = d 4. Which of the following methods provides guarantees the optimum solution to the transportation problem? (a) Northwest corner rule (b) Least cost method (b) Stepping stone method (d) Vogel’s approximation method Ans = b 5. Consider the following balanced TP with 2 supplies and 3 destinations. The solution is found using NWC rule. The cost is 5

6

3

50

7

5

8

40

30

25

35

Ans = 575 The allocations are X 11 = 30, X 12 = 20, X 22 = 5 and X 23 = 35. The cost is 30 x 5 + 20 x 6 + 5 x 5 + 35 x 8 = 575 6. Consider the following balanced TP with 2 supplies and 3 destinations. The solution is found using Minimum cost method. The cost is 5

6

3

50

7

5

8

40

30 25 Ans = 410

35

The allocations are X 13 = 35, X 11 = 15, X 22 = 25, X 21 = 15. The cost is 15 x 5 + 35 x 3 + 15 x 7 + 25 x 5 = 410 7. Consider the following balanced TP with 2 supplies and 3 destinations. The solution is found using Vogel’s approximation method. The cost is 5

6

3

50

7

5

8

40

30 25 Ans = 410

35

The row penalties are 2 and 2. Column penalties are 2, 1, 5. First allocation is X 13 = 35. Row penalties are 1, 2. Column penalties are 2, 1. We choose X 11 = 15. The other allocations are X 21 = 15 and X 22 = 25 with cost = 410 8. Start with NWC solution. The optimum cost using MODI method is 5

6

3

50

7

5

8

40

30 25 Ans = 410

35

The NWC solution is X 11 = 30, X 12 = 20, X 22 = 5 and X 23 = 35 with cost = 575. We initialize u 1 = 0, and get v 1 = 5, v 2 = 6, u 2 = -1, v 3 = 9. We compute C 13 – (u 1 + v 3 ) = 3 – (0 + 9) = -6. X 13 comes into the solution. The revised allocations are X 11 = 30, X 13 = 20, X 22 = 25 and X 23 = 15 with cost = 455. We initialize u 1 = 0 and compute v 1 = 5, v 3 = 3, u 2 = 5 and v 2 = 0. We compute C 21 – (u 2 + v 1 ) = -3. Variable X 21 enters the solution. The new solution is X 11 = 15, X 13 = 35, X 21 = 15 and X 22 = 25 with cost = 410. We initialize u 1 = 0 from which v 1 = 5, v 3 = 3,

u 2 = 2 and v 2 = 3. All C ij – (u i + v j ) are positive for non basic positions. The solution is optimal.

9. A TP has 2 supply points and 3 destination points. The dummy is added to ___ and the quantity is ____ 5

6

3

40

7

5

8

40

30 (a) (b) (c) (d)

25 Row, 10 Column, 10 Row, 20 Column, 20

35

The total supply is 80 and the total demand is 90. We balance the problem by adding a dummy row with quantity = 10. Ans = a 10. Consider the TP. The optimum solution has an objective function value of _____ 5

6

3

45

7

5

8

40

25 25 35 Ans = 385 The initial solution using VAM has the allocations (in the order) X 13 = 35, X 22 = 25, X 21 = 15 and X 11 = 10. The stepping stone method shows that this solution is optimum because allocating in non basic cells increases the cost. The cost is 10 x 5 + 35 x 3 + 15 x 7 + 25 x 5 = 385 11. If u i and v j represent the dual variables in the assignment formulation, the constraint set is given by a) u i + v j = C ij b) u i + v j ≥ C ij c) u i + v j ≤ C ij Ans = c 12. In the dual to the transportation problem, the dual variables are a) ≥ 0 b) ≤ 0

c) Unrestricted Ans = c In a balanced transportation problem, the primal constraints are equations. Hence the dual variables are unrestricted. 13. Consider the TP. You are given the allocations X 11 = 20, X 13 = 30, X 21 = 10, X 22 = 25 and X 23 = 5. 5

6

3

50

7

5

8

40

30 25 35 The above solution is a) Basic feasible and optimum b) Not basic feasible but optimum c) Basic feasible but not optimum d) Not basic feasible and not optimum Ans d. The problem is balanced. There are five allocations. A basic feasible solution will have a maximum of m+n-1 = 4. Hence the solution is not basic feasible. There is a loop and breaking it can decrease cost. It is therefore not optimum. 14. A TP has 2 supply points and 3 destination points. The demand not fully met is for a) Destination 1 b) Destination 2 c) Destination 3 5

6

3

40

7

5

8

40

30 25 35 Ans = a We add a dummy supply with quantity 10. The optimum solution is X 11 = 5, X 13 = 35, X 21 = 15, X 22 = 25, X 31 = 10. Destination 1 gets supply from the dummy and therefore its demand is not fully met.

15. Consider the following balanced TP with 2 supplies and 3 destinations. The solution to the maximization transportation problem has profit = 5

6

3

50

7

5

8

40

30 25 35 Ans = 590 The problem is balanced. Combination of VAM and stepping stone method is used to get the solution for the maximization problem by considering the negative of the costs and solving a minimization problem. The solution is X 23 = 35, X 21 = 5, X 11 = 25, X 12 = 25. The profit is 25 x 5 + 25 x 6 + 5 x 7 + 35 x 8 = 590 16. A TP has 2 supply points and 3 destination points. 5

6

3

50

7

5

8

60

30

25

35

Which of the following is TRUE a) The above transportation problem has total demand exceeding total supply b) To balance this problem we have to add a dummy supply c) To balance this problem we have to add a dummy demand d) The given problem is balanced Ans = C. Total supply is 110 and total demand is 90. We have to add a dummy supply. 17. A TP has 2 supply points and 3 destination points. 5

6

3

50

7

5

8

60

30

25

35

Since supply exceeds demand, destination 1 is willing to accept up to additional 10 and destination 3 is willing to accept an additional 20. The minimum number of constraints that are equations in LP formulation to this problem is _______ Ans = 3 Let X ij be the quantity transported from supply i to demand j. We observe that if we meet only the minimum demand, we observe that total supply exceeds total demand. Since the excess can also be transported and there are takers, we send all the quantities available. Therefore the supply constraints become

equations. There are three equations. The demand for destination 2 can also be modeled as an equation. The minimum equations is therefore three.

18. A TP has 3 supply points and 2 destination points. 5

6

50

7

5

60

4

6

30

80

100

Balance the problem by adding a dummy source or destination and write the dual. The number of constraints in the dual is ________ (Ans = 8) The total supply is 140 and total demand is 180. We add a dummy supply with 40. There are 4 supply points and 2 demand points. The primal has 8 variables. The dual will have 8 constraints. 19. Consider the TP. The objective function is to maximize the profits that are given in the problem. The optimum solution has an objective function value of _____ 5

6

3

50

7

5

8

80

50 45 35 Ans = 650 Initial solution is found using VAM. The allocations (in the order) are X 13 = 35, X 11 = 15, X 21 = 35, X 22 = 45. This solution is optimum with profit = 5 x 15 + 3 x 35 + 7 x 35 + 5 x 45 = 650 20. Consider the TP. The objective function is to maximize the profits that are given in the problem. The profit x indicates that we cannot transport in this position. The optimum solution has an objective function value of _____ 9

6

3

50

7

5

x

40

30 25 Ans = 470

35

The maximization problem is converted to a minimization problem by multiplying with -1. Initial solution is found using VAM. The allocations (in the order) are X 13 = 35, X 11 = 15, X 21 = 15, X 22 = 25. This solution is optimum with profit = 9 x 15 + 3 x 35 + 7 x 15 + 5 x 25 = 470

Unit 8: Assignment problem Balanced Assignment problem The Hungarian algorithm Dual of the assignment problem Additional points and interpretation Solving the assignment problem using solver 1. How many feasible solutions does a 5 x 5 assignment problem have? Ans = 5! or 120 2. How many variables does the formulation of 5 x 5 assignment problem have? Ans = 25 For a n x n assignment problem there are n2 variables 3. How many constraints does a 5 x 5 assignment problem have? Ans = 10 For a n x n assignment problem there are n supply constraints and n demand constraints. There are 2n constraints. 4. In a 4 x 4 assignment problem where 4 jobs are assigned to 4 machines, job 1 is assigned to M2, job 2 to M4, Job 3 to M3. What is the fourth assignment? Ans = Job 4 to M1 The unassigned job is J4 and the unassigned machine is M1. 5. How many variables does the dual of 5 x 5 assignment problem have? Ans = 10 An n x n assignment problem, there are n2 variables and 2n constraints. A 5 x 5 problem has 25 variables and 10 constraints. Its dual will have 25 constraints and 10 variables 6. How many constraints does the dual of the 5 x 5 assignment problem have? Ans = 25 An n x n assignment problem, there are n2 variables and 2n constraints. A 5 x 5 problem has 25 variables and 10 constraints. Its dual will have 25 constraints and 10 variables

7. The minimum cost for the following 3 x 3 assignment problem is 1 1 4 6 7 2 8 4 3 Ans = 7 The problem is a minimization problem. We do row minimum and column subtraction. The initial assignments are X 23 and X 11 . There are 2 assignments. Lines are drawn through row 1 and column 3. Minimum θ = 1. The new allocations are X 11 = X 23 = X 32 = 1 with cost = 1 + 2 + 4 = 7 8. Consider the assignment problem with 4 jobs and 3 machines. The job that is not assigned to any machine is 1 1 4 6 7 2 8 4 3 5 6 7 Ans = Job 4 The problem is unbalanced and we add an extra column with zero costs. Initial assignments are X 34 = X 11 = X 23 = 1. We draw lines through rows 1, 2 and column 4. Minimum θ = 1. The assignments are again X 34 = X 11 = X 23 = 1. We draw lines through row 1 and columns 3 and 4. Minimum θ = 2. The assignments are X 23 = X 44 = X 11 = X 32 = 1. Job 4 is assigned to the dummy column and does not get a machine. 9. Which of the following is not a step in Hungarian algorithm? (a)Subtract row minimum from every row (b) Subtract column minimum from every column (c ) Draw lines through ticked rows and unticked columns (e) Tick unassigned rows Ans = C In Hungarian algorithm, we draw lines through unticked rows and ticked columns. 10. Solve the 4 x 4 maximization assignment problem. The maximum profit is 1 1 4 8 6 7 2 7 8 4 3 6 5 6 7 8 Ans = 30 The given problem is converted to minimization by multiplying with -1. The allocations after row and column subtraction are X 11 = X 22 = X 31 = X 43 = 1 with profit = 8 + 7 + 8 + 7 = 30 11. Consider the 3 job 4 machine assignment problem:

1 3 5 6 7 6 2 4 3 7 8 9 The machine that does not get a job in the optimum assignment is ___. The objective function value at the optimum is _____ Ans = 4, 11 The problem is balanced by adding a dummy column (job) with zero values. We do column minimum subtraction. The initial assignments are X 24 , X 33 and X 11 . We draw lines through rows 1, 3 and column 4. Minimum θ = 3. The assignments in the new matrix are X 33 , X 44 , X 11 . We draw lines through row 1 and columns 3 and 4. Minimum θ = 1. The assignments in the new matrix are X 44 , X 11 , X 22 and X 33 . There is alternate optima but X 44 = 1 is in all the alternate solutions. Machine 4 is assigned to the dummy job and does not get a job. The cost = 1 + 7 + 3 + 0 = 11

12. Which of the following statements is not TRUE about the Assignment problem: a) It is a transportation problem b) The LP formulation will give binary solutions c) When solving, the cost matrix is square d) LP can give non integer solution sometimes Ans = d The LP solution to the assignment problem always gives a binary solution 13. Find the minimum cost corresponding to the 4 x 4 assignment problem: 20 17 22 16 32 29 33 26 26 27 29 28 40 30 35 37 Ans = 104 The initial assignments are X 14 , X 42 and X 31 . We draw lines through rows 3, 4 and column 1. Minimum θ = 1. The assignments in the new matrix are X 24 , X 42 , X 31 . We draw lines through row 3 and columns 2 and 4. Minimum θ = 2. The assignments in the new matrix are X 24 , X 31 , X 43 and X 12 . The cost = 17 + 26 + 26 + 35 = 104 14. Consider the following assignment problem. When you solve it by hand, the number of assignments that you get in the first iterations is ____. Ans = 3 20 17 22 16 32 29 33 26 26 27 29 28

40 30 35 37 Ans = 3. The initial assignments are X 14 , X 42 and X 31 . 15. If u i and v j represent the dual variables in the assignment formulation, the constraint set is given by a) u i + v j = C ij b) u i + v j ≥ C ij c) u i + v j ≤ C ij Ans = c 16. In the dual to the assignment problem, the dual variables are a) ≥ 0 b) ≤ 0 c) Unrestricted Ans = c. The primal constraints are equations. The dual variables are unrestricted in sign. 17. The maximum profit for the following 3 x 3 assignment problem is 1 1 4 6 7 2 8 4 3 Ans = 19 The problem is solved as minimization by multiplying with -1. The assignments are X 13 = X 22 = X 31 = 1 with profit = 4 + 7 + 8 = 19 18. The maximum profit for the following 4x 3 assignment problem is 1 1 4 6 7 2 8 4 3 6 3 7 Ans = 22 The problem is first balanced by adding a fourth column with profit zero in all elements. It is then solved as minimization by multiplying with -1. The assignments are X 14 = X 22 = X 31 = X 43 = 1 with profit = 0 + 7 + 8 + 7 = 22 19. The minimum cost for the following 5x 5 assignment problem is 1 1 4 3 2 10 7 8 6 7 8 4 6 3 9 6 6 7 8 9 12 10 11 13 12 Ans = 28

The row minimum and column minimum are subtracted. The assignments are X 34 , X 25 , X 11 , X 42 = X 52 = 1 with cost = 1 + 7 + 3 + 6 + 11 = 28. There is alternate optima but X 34 = X 25 = 1 in all the solutions.

20. The maximum profit for the following 4x 3 assignment problem is 1 1 4 10 7 2 x 4 6 6 3 7 Ans = 21 The problem is first balanced by adding a fourth column with profit zero in all elements. It is then solved as minimization by multiplying with -1. The assignments are X 21 = X 43 = X 14 = X 32 = 1 with profit = 10 + 7 + 0 + 4 = 21

Unit 8: Solving LPs using Solver Revisiting the formulation examples Three types of LPs Dual solution Sensitivity analysis Assignment 1 1. Maximize 7X 1 + 15X 2 + 3X 3 + 14X 4 Subject to 6X 1 + 4X 2 + 5X 3 + 10X 4 ≤ 30 16X 1 + 14X 2 + 15X 3 + 10X 4 ≤ 50 8X 1 + 10X 2 + 9X 3 + 11X 4 ≤ 40 2X 1 + X 2 + 3X 3 + 8X 4 ≥ 10 Xj ≥ 0 Find the objective function value at the optimum? Find the value of the dual variable Y 2 at optimum? Ans: 515/9 or 57.222; 25/54 or 0.462963 The optimum solution is given by X 2 = 25/9 or 2.777, X 4 = 10/9 or 1.111 with Z = 515/9 or 57.222. The optimum solution to the dual is Y 2 = 25/54 or 0.462963; Y 3 = 23/27 or 0.851852 with W = 515/9. You are directly read the dual solution from the solver. If you are writing the dual and solving it, note that variable Y 4 becomes ≤ 0 and has to be replaced by –Y 5 with Y 5 ≥ 0. Also the solver will give fractional solution. How do you get 25/54 from 0.462963? 2. Minimize 5X 1 + 4X 2 + 13X 3 + 4X 4 Subject to 6X 1 + 4X 2 + 5X 3 + 10X 4 ≥ 30 16X 1 + 14X 2 + 15X 3 + 10X 4 ≥ 50 8X 1 + 10X 2 + 9X 3 + 11X 4 ≤ 40 12X 1 +3X 2 + 9X 3 + 18X 4 ≥ 30 X j ≥ 0. Find the value of the objective function at the optimum? Find the value of dual variable Y 3 at optimum? Ans: 17, -1/21 or -0.047619 The optimum solution is given by X 1 = 1, X 2 = 1, X 4 = 2 with Z = 17. If you are writing the dual and solving it, note that variable Y 3 becomes ≤ 0 and has to be replaced by –Y 5 with Y 5 ≥ 0. The optimum solution to the dual is Y 1 = 0.1857 or 13/70, Y 2 = 0.2667 or 4/15 and Y 5 = 0.047619 or 1/21. Therefore Y 3 = -1/21. The objective function value is W = 30 x 13/70 + 50 x 4/15 – 40 /21 = 357/21 = 17.

You are directly read the dual solution from the solver. Observe the solution.

3. Maximize 7X 1 + 5X 2 + 3X 3 + 14X 4 Subject to 6X 1 + 4X 2 + 5X 3 + 10X 4 ≤ 15 16X 1 + 14X 2 + 15X 3 + 10X 4 ≥ 60 Xj ≥ 0 a) The solver gives an optimum solution b) The problem is unbounded c) The problem is infeasible Ans = c The problem is infeasible 4. Maximize 7X 1 - 5X 2 + 3X 3 + 14X 4 Subject to 6X 1 - 4X 2 + 5X 3 + 10X 4 ≤ 30 16X 1 - 14X 2 + 15X 3 + 10X 4 <= 50 Xj ≥ 0 a) The solver gives an optimum solution b) The problem is unbounded c) The problem is infeasible Ans = b The problem is unbounded. Solver says that cell values do not converge 5. Solve the following 4 supply 5 demand transportation problem where the supply quantities are 80, 100, 90, 60. The demand quantities are 70, 75, 55, 65, 65. The transportation costs are given in the table. Find the minimum cost of transportation? 7 10 9 6 9 12 14 16 13 11 20 18 22 24 19 5 4 6 8 5 Ans: 3635 X 11 = 15; X 14 = 65, X 21 = 35, X 25 = 65, X 31 = 15, X 32 = 75, x 41 = 5, X 43 = 55 with cost = 3635

6. Solve the following 5 x 5 assignment problem. Find the least cost solution and the second least cost solution. Also find the profit for the original problem with maximization objective? (Hint: Solve the minimization problem first. There will be 5 assignments. Solve 5 problems by taking each of the assignments and putting a large cost (M or use 1000 as value) for this assignment. The minimum among the five solutions gives the second best minimum cost) 10 16 18 13 15 28 24 22 27 19 33 36 31 28 36 8 7 11 8 10 25 24 23 27 19 Ans: 86, 87, 119 The optimum solution for the minimization problem is given by X 11 = X 23 = X 34 = X 42 = X 55 = 1 with objective function = 86 Setting C 11 to 1000, we get the solution X 12 = X 23 = X 34 = X 41 = X 55 = 1 with cost = 92 Setting C 23 to 1000, we get X 11 = X 25 = X 34 = X 42 = X 53 = 1 with Z = 87. The other three costs are 92, 92 and 87. The second minimum is 87. The maximization problem is solved by simply changing the objective to maximization. The solution is X 13 = X 21 = X 32 = X 45 = X 54 = 1 with profit = 119 7. Solve the following 4 supply 5 demand transportation problem where the supply quantities are 100, 100, 90, 80. The demand quantities are 70, 75, 55, 65, 65. The transportation costs are given in the table. 17 12 10 5

10 14 15 14

19 16 12 6

16 13 14 8

9 11 9 15

In this problem there is an excess supply of 40. Demand point 1 would like to take up to an extra 20, while demand point 4 would like to take as much extra as given. The company would like to meet as much of the demand as possible. Find the total cost of transportation. How much extra does demand 4 get? Ans = 3240, 35 Since all supply quantities are sent, the four supply constraints are equations. Demand 2, 3 and 5 are equations since they will get exactly 75, 55 and 65 respectively. Demand 1 will get between 70 and 90 and there will be 2 constraints – one with ≥ 70 and the other with ≤ 90. Demand 4 is willing to take as much as given. They can take all the extra 40 if given. They get between 65 and 105. Again there are 2 constraints. The formulation has 11 constraints. The optimum solution is X 14 = 100,

X 21 = 25, x 22 = 75, X 31 = 25, X 35 = 65, x 41 = 25, X 43 = 55 with cost = 3240. Demand 1 gets extra 5 and demand 4 gets extra 35.

8.

Consider the following assignment problem with four persons and 5 jobs. 10 16 18 13 28 24 22 27 33 36 31 28 8 7 11 8 25 24 23 27 One person gets two jobs. Solve an assignment like problem to find the minimum cost? Person number ___ gets two jobs. Ans = 90, 3 There are 5 jobs and 4 people. Each job goes to only one person. There are 5 constraints. We do not know which person gets the second job. All persons should get at least one job. There are 4 constraints where each person gets at least one job. These are ≥ 1 constraints. There are 4 constraints where each person gets less than or equal to 2 jobs. There are 13 constraints. The optimum solution is X 11 = X 23 = X 34 = X 42 = X 53 = 1 with cost = 90

9. Consider the caterer problem where demand for 8 days. The demands are 200, 80, 140, 90, 100, 150, 80 and 180. The cost of new napkin is Rs 100. There are two types of laundries – fast and slow. Fast laundry takes 2 days (napkins put at end of day 1 can be used from day 3 onwards) and costs Rs 25. Slow laundry takes 3 days (napkins put at end of day 1 can be used from day 4 onwards) and costs Rs 15. Solve an LP to minimize total cost? Ans = 4370. Let X j be the new napkins used to meet the demand of day j. Let Y j be the napkins sent to fast laundry at the end of day j. Let Z j be the napkins sent to slow laundry at the end of day j. There are 8 X j variables, 6 Y j (up to day 6) variables and 5 Z j variables (up to day 5). The demand constraints are written by also considering the two types of laundry. The first two days we will have only X j . The third day we will have the constraint X 1 + X 2 + X 3 + Y 1 ≥ 420. The fourth day constraint will be X 1 + X 2 + X 3 + X 4 + Y 1 + Y 2 + Z 1 ≥ 510 and so on. There are 8 demand constraints. The eighth constraint will involve X 1 to X 8, Y 1 to Y 6 , Z 1 to Z 5 and will have RHS = 1020. There are six constraints for putting the used napkins to laundries. The first day constraint will be Y 1 + Z 1 ≤ 200. The fifth day constraint will be Y 5 + Z 5 ≤ 100. The sixth day constraint will be Y 6 ≤ 150. There are 14 constraints and 19 variables. The optimum solution is X 1 = 280, Y 1 = 140, Z 1 = 60, Y 2 = 30, Z 2 = 50, Y 3 = 50, Z 3 = 90, Y 4 = 60, Z 4 = 30, Y 5 = 50, Z 5 = 50, Y 6 = 130 with cost = 4370.

10. Consider a bin packing problem with 8 items whose lengths are 31, 29, 23, 19, 17, 13, 11 and 7. The bin length is 40. Verify whether 4 bins are enough? If two bins are of lengths 40 and the other two are of length 36, can we accommodate the lengths in 4 bins? If we have only three bins, what is the minimum bin size to accommodate these lengths? Ans = Yes, Yes, 51 We solve the bin packing problem with 4 bins. The formulation has 8 constraints for the items and 4 for the bins. There are 32 X ij variables and 4 Y j variables. There are 36 variables and 12 constraints. The optimum solution uses 4 bins and the allocations are X 31 = X 51 = X 22 = X 72 = X 43 = X 63 = X 14 = X 84 = 1. The problem is solved with bins 1 and 2 having size 40 and bins 3 and 4 having size = 36. Again, the optimum solution uses 4 bins. The solution is X 33 = X 54 = X 22 = X 72 = X 44 = X 63 = X 11 = X 81 = 1. In the case of 3 bins, there is no Y j variable. Let y be the minimum bin size. The objective is to minimize y. There are 8 constraints for the items and 3 for the bins. The bin constraints are modified such that the sum of the lengths of the items attached to a bin is ≤ y. For bin 1, the constraint is 31X 11 + 29X 21 + 23X 31 + 19X 41 + 17X 51 + 13X 61 + 11X 71 + 7x 81 ≤ y. The optimum solution gives y = 51. The allocations are X 31 = X 51 = X 23 = X 71 = X 43 = X 62 = X 12 = X 82 = 1. Assignment 2 1. TV sets are to be transported from three factories to three retail stores. The available quantities are 300, 400 and 500 respectively in the three factories and the requirements are 250, 350 and 500 in the three stores. They are first transported from the factories to warehouses and then sent to the retail stores. There are two warehouses and their capacities are 600 and 700 units. The unit costs of transportation from the factories to warehouses are 2, 3, 2.5, 3, 4, 5 respectively and from the warehouses to retail stores are 6, 5, 7, 6,5, 8, 7.5 respectively. What is the minimum cost at the optimum? Ans = 10825 Let X ij be the quantity transported from factory i to warehouse j. Let Y jk be th quantity transported from warehouse j to retail store k. Minimize 2X 11 + 3X 21 + 2.5X 31 + 3X 12 + 4X 22 + 5X 32 + 6Y 11 + 5Y 21 + 7Y 12 + 6.5Y 22 + 8Y 13 + 7.5Y 23 subject to X 11 + X 12 ≤ 300 X 21 + X 22 ≤ 400 X 31 + X 32 ≤ 500

X 11 + X 21 + X 31 ≤ 600 X 12 + X 22 + X 32 ≤ 700 Y 11 + Y 21 ≥ 250 Y 12 + Y 22 ≥ 350 Y 13 + Y 23 ≥ 500 X 11 + X 21 + X 31 - Y 11 - Y 12 - Y 13 ≥ 0 X 12 + X 22 + X 32 - Y 21 - Y 22 - Y 23 ≥ 0 X ij , Y jk ≥ 0. The last two constraints ensure that the quantity that leaves the warehouse does not exceed the quantity entering it. The optimum solution is given by X 21 = 100, X 31 = 500, X 12 = 300, X 22 = 200, Y 21 = 250, Y 12 = 350, Y 13 = 250, Y 23 = 250 with cost = 10825 2. A person is in the business of buying and selling items. He has 10 units in stock and plans for the next three periods. He can buy the item at the rate of Rs 50, 55 and 58 at the beginning of periods 1, 2 and 3 and can sell them at Rs 60, 64 and 66 at the end of the three periods. He can use the money earned by selling at the end of the period to buy items at the beginning of the next period. He can buy a maximum of 200 per period. He can borrow money at the rate of 2% per period at the beginning of each period. He can borrow a maximum of Rs 8000 per period and he cannot borrow more than Rs 20000 in total. He has to pay back all the loans with interest at the end of the third period. Solve an LP problem and find the maximum gain? Ans = 602.5 Let X j be the quantity bought at the beginning of month j. Let Y j be the quantity sold at the end of month j. Let Z j be the amount taken on loan at the beginning of month j. Maximize 66Y 3 -1.06Z 1 -1.04Z 2 -1.02Z 3 subject to Y 1 - X 1 ≤ 10 Y 1 + Y 2 -X 1 -X 2 ≤ 10 Y 1 + Y 2 + Y 3 –X 1 - X 2 -X 3 ≤ 10 50X 1 - Z 1 ≤ 0 55X 2 - 60Y 1 - Z 2 ≤ 0 58X 3 - 64Y 2 - Z 3 ≤ 0 X 1 ≤ 200 X 2 ≤ 200 X 3 ≤ 200 Z 1 ≤ 8000 Z 2 ≤ 8000

Z 3 ≤ 8000 Z 1 + Z 2 + Z 3 ≤ 20000 X 1 , X 2 , X 3 , Y 1 , Y 2 , Y 3 , Z 1 , Z 2 , Z 3 ≥ 0. The first three constraints limit the items that can be sold at the end of the month. The next three constraints limit the quantities purchased based on the money available. The next three constraints limit the quantity to 200. The next four constraints are the borrowing limits. The objective function is the money left at the end of the third period after paying the loans with interest. The optimum solution is given by Z 1 = 8000, Z 2 = 8000, Z 3 = 4000, X 1 = 160, X 2 = 200, X 3 = 200, Y 1 = 50, Y 2 = 118.75, Y 3 = 401.25 with gain = 5602.5 3. A food stall sells idlis, dosas and poories. A plate of idli has 2 pieces, a plate of dosa has 1 piece while a plate of poori has 2 pieces. They also sell a “combo” which has 2 idlis and 2 poories. A kg of batter costs Rs 60 and twelve spoons of batter. Each piece of idli requires 1 spoon of batter and each dosa requires 1.5 spoons of batter. Each poori piece requires 1 ball of wheat dough and a kg of wheat dough that costs Rs 60 can make 20 balls of dough. The selling prices of the items are Rs 40, 60, 60 and 90 per plate respectively. The owner has Rs 800 with her and estimates the demand for the four items (in plates) as 50, 30, 20 and 10 respectively. There is a penalty cost of Rs 10 for any unmet plate of demand of an item. Idli being the most commonly consumed item, the owner wishes to meet at least 80% of the demand. Solve an LP problem to find the maximum net profit? Ans = 3943.75 Let X 1 be the number of plates of idlis sold, Let X 2 be the number of dosas sold, Let X 3 be the number of poories sold. Let Y 1 be the number of combos sold. Maximize 40X 1 + 62.5X 2 + 64X 3 + 84Y 1 subject to X 1 ≤ 50 X 2 ≤ 30 X 3 ≤ 20 y 1 ≤ 10 X 1 ≥ 40 10X 1 + 7.5X 2 + 6X 3 + 16Y 1 ≤ 800 X 1 , X 2 , X 3 , Y 1 ≥ 0. The first four constraints are the maximum demand for the items. The fifth constraint is the minimum quantity to be made of item 1. The amount of poories is 2X 3 + 2Y 1 . The quantity of wheat required is (2X 3 + 2Y 1 )/20 kg. The cost of wheat is 60 x (2X 3 + 2Y 1 )/20 = 6X 3 +6Y 1 .

The amount of rice batter required is 2X 1 + 1.5X 2 + 2Y 1 spoons. The quantity in kg is (2X 1 + 1.5X 2 + 2Y 1 )/12. The cost of rice batter is 60 x (2X 1 + 1.5X 2 + 2Y 1 )/12 = 10X 1 +7.5X 2 + 10Y 1 . The budget constraint is 6X 3 + 6Y 1 + 10X 1 + 7.5X 2 + 10Y 1 ≤ 800 which on simplification gives 10X 1 + 7.5X 2 + 6X 3 + 16Y 1 ≤ 800 The objective function is the money earned less penalty less cost of material. This is given by 40X 1 + 60X 2 + 60X 3 + 90Y 1 – 10(50 – X 1 + 30 – X 2 + 20 – X 3 + 10 – Y 1 ) – (10X 1 + 7.5X 2 + 6X 3 + 16Y 1 ). This on simplification gives Maximize 40X 1 + 62.5X 2 + 64X 3 + 84Y 1 – 1100. The optimum solution is X 1 = 40, X 2 = 30, X 3 = 20, Y 1 = 3.4375 with net gain = 5043.75 – 1100 = 3943.75

4. Consider the following network with 7 nodes and the following arcs. The cost of unit transportation across the arcs are given. The supplies in nodes 1, 2 and 3 are 100, 40 and 60 and the demands are nodes 5, 6 and 7 are 50, 30 and 120. Arc 4-5 cannot transport more than 150 units. Find the minimum cost of transportation? Arc Cost Arc Cost Arc Cost 1-2 10 3-4 7 5-7 11 1-3 6 3-6 12 6-7 12 1-4 8 4-5 4 2-4 9 4-6 5 Ans = 4270 Let X ij be the quantity transported in arc i-j. Minimize10X 11 + 6X 13 + 8X 14 + 9X 24 + 7X 34 + 12X 36 + 4X 45 + 5X 46 + 11X 57 + 12X 67 Subject to X 12 + X 13 + X 14 = 200 -X 12 +X 24 = 40 -X 13 + X 34 + X 36 = 60 -X 14 – X 24 – X 34 + X 45 + X 46 = 0 -X 45 +X 57 = -50 -X 36 – X 46 + X 67 = -30 -X 57 – X 67 = -120 X 45 ≤ 150 X ij ≥ 0 The objective function minimizes the cost of transportation. The first seven constraints are the node balance constraints (what enters a node flows out) and the last constraint limits the quantity on arc 4-5. The optimum solution is given by X 13 = 100, X 24 = 40, X 34 = 110, X 36 = 50, X 45 = 150, X 57 = 100, X 67 = 20 with cost = 4270.

5. Three students are preparing for an examination in Operations Research and they have access to important course material for 10 days. If the first student uses the material for X 1 days, his expected mark is 60 + 8X 1 . If the second student uses the material for X 2 days, his expected mark is 70 + 5X 2 . If the third student uses the material for X 3 days, his expected mark is 75 + 4X 3 . The material can be with only one student at a time. How many days does each student use the material so that the minimum of the three marks is maximized? What is the maximum value of the minimum mark? Ans = 87.39 Let X j be the number of days student j uses the material X 1 + X 2 + X 3 ≤ 10. The marks are 60 + 8X 1 , 70 + 5X 2 and 75 + 4X 3 . Let the minimum be u. The objective is to Maximize u such that 60 + 8X 1 ≥ u, 70 + 5X 2 ≥ u, 75 + 4X 3 ≥ u. X 1 , X 2 , X 3 , u ≥ 0. The optimum solution is given by X 1 = 3.424, X 2 = 3.478, X 3 = 3.098 with the maximum value of the minimum mark = 87.39