Ryt=R,?+ Ps R,‘= (0, 0,-0.8, 1, 0.6, 4) R/‘=Ro+1.67 ! R,= (0, 1, 0,0, 1,0, 10) Rf =R3s-1.33R¢ R?+93.33R,¢ replacing row = pivot row = pivot R,*= (0, 0, -1.33, 1.67, 1, 0, 6.67) + 1.67 remaining row = previous row — (intersectional element x replacing row) R= (0, 1, 1.83, -1.67, 0, 0, 8.33) + (1.67) (0, 0, -0.8, 1, 0.6, 4) R,*= (0, 1, 1.33, -1.67, 0, 0, 3.33) + (0, 0, -1.33, 1.67, 1, 0, 6.67) R,*= (1, 0, -0.67, 1.33, 0, 0, 13.33) - (1.33) (0, 0, -0.8, 1, 0.6, 4) R,= (1, 0, -0.67, 1.33, 0, 0, 13.33) (0, 0, -1.05, 1.33, 0.80, 0, 6.3) R,*= (1, 0, 0.39, 0, -0.80, 0, 8) (0, 0, 86.67, -33.33, 0, 0, 2,466.67) + (33.33) (0, 0, -0.8, 1, 0.6, 4) R,‘= (0, 0, 86.67, -33.33, 0, 0, 2,466.67) + (0, 0, -26.54, 33.33, 20, 0, 133.12) R,‘= (0, 0, 60, 0, 20, 0, 2,600) Enter new values in Tableau 4. BVA noe (ee, A PO iy 0 | 039 Ss, o [08 p_[o|o | 6 Lot 60 MANAGEMENT SCIENCE The last aiready the op e decision is son 6.3: LP Minimizati the applic: anges: 1. Sel fun 2. Ad toc 3. Pre ele Api 5. Re rov RH Sample Probl Happy C is, Brand A atial ingre quirements Compute for tThe last row does not have negative elements. This means that the table is already the optimal. The decision is: x, = 8, x, = 10 in order to get a profit of P2,600. Lesson 6.: LP Minimization Model Using Simplex For the application of simplex technique to minimization problems, there are a few changes: 4. Set the LP problem by determining the unknown variables, objective function, and constraints. Add the necessary slack variables. Slack variables are variables added to constraints in order to translate them into linear form, Prepare the initial tableau. Put an asterisk in all rows, with negative elements. Apply the test ratio in the first row with an asterisk. Repeat step 4 until the asterisks are removed in all rows or when the last row or objective function does not have any negative entry (except the RHS). Sample Problem: Happy Chicken Co. is trying to determine the correct mix of two types of chicken is, Brand A and Brand B, which cost P45 and P12 per Kilogram, respectively. Two essential ingredients are contained in the feed. Below shows the minimum dally uirements of each ingredient: [ingredient | Percent per | Percent per | Minimum Number | Kilogram | Kilogram Daily Requirement (kg) 1 1 300, 3 0 250 BrandA | Brand B Compute for the least-cost daily blend for each brand CHAPTER 6 LINEAR PROGRAMMING PART 2Solution: The Decision Variables. The decision variables are: x, = thé number of kg of Brand A the number of kg of Brand B The Objective Function The cost for Brand Ais 45x, The cost for Brand B is 12x, The total cost is, therefore, Minimum C = 45x, + 12x, The Requirements Ingredient 1 1x, + 1x,2 300 Ingredient 2 y 3x, + Ox, 250 1, The objective function and the constraints. Minimize C = 45x,+ 12x, | Subject to: 1x, + 1x,2300 3x, + Ox,2 250 Convert the LP problem to linear equations, The surplus variables are to be subtracted to the constraints in order to convert them to equations. Let us add S, as the surplus variables: 1x, + 1x,- 8, =300 1st requirement 8x, + Ox,~ S, = 250 2nd requirement 45x, + 12x, +P =0 Objective function ttcan also be written as: 1x, + 1x,-S,+ 0S, + OP = 300 1st requirement 3x, +0x,+0S,—S,+0P =250 2nd requirement 45x,+12x,+08,+08,+P=0 Objective function 62 MANAGEMENT SCIENCE Set up the | BV 6 pest 28 LP dees |. hae. 4. Select the positive ele Find the pi lowest tes negative e EI = a: le3. Set up the initial tableau, Tableau 1 x |S Ss, | P | RHS 14 ate 0 | 0 | 300 ist requirement sfolof-a | ofo 250 2nd requirement ol4 45 | 12[ 0] 0 0 Objective function 4. Select the pivot column. For minimization, the pivot column is the highest Positive element in the bottom row. In this example, it is 45. Tableau 1 Ss, a oO 0 12 | Pivot Column 5. Find the pivot row using the test ratio (RHS + IE). The pivot row is the row with lowest test ratio. The RHS values must be divided by the nonzero and non- negative elements in the pivot column. Tableau 1 S, [P| RHS| Test Ratio 300 0 | 250 |250=3 ee eck 4 0 Tableau 1 renal, 5 7 [josmrs; | P| Rus | . ES Ps EO Eh ES eet 1 o | 4fo 250 | <— R, o 0 1 o |+ RF CHAPTER 6 LINEAR PROGRAMMING PART2 636. Calculate the replacing row and remaining rows. Tableau 2 s, 1 | 0.33 Ag=R—-1 Re alolx o | -0.33 o | 15 RZ=A,)- 452 The solution is already optimal because the objective function or last row does, not contain a negative entry. Tableau 2 x olslo Sins =1_| 0.33 0 | -033 o | 15 The decision is x, Review Questions MANAGEMENT SCIENCE Linear programming (LP) problems with more than two unknown variables should utilize the simplex method because such problems are geometrically difficult to plot in a graph. Describe the logic of the simplex method. . Discuss the structure of the simplex tableau. Demonstrate the difference in the algorithm between maximization and minimization using the simplex method. 16.67. The total cost is P6,350. Case Problems 1. Ming's Tea Ho ion. The cer rant offers demand. Lé Vari 1 a 3 4 Available n 2 Menu Master projected t The compe odel’s capital 2 Prepare al ctive and co a. Achiev b. Produ: ©. Produc Seve using the :Case Problems 1. Ming's Tea House is a Chinese Restaurant hat has eight branches all over the Bicol Region. The central commissary is located at Legazpi City. Among other things, the restaurant offers a dimsum set in all its restaurants; each having its own profitability and demand. Let us call them variants 1-4 Variant | Profit per | Daily Demand Machine set | Capacity 70 200 setsiday | 500 sets/day P84 | 100setsiday | 400 seisiday | 75 500 setsiday | 600 sets/day P100 50 setsiday | 200 setsiday 4 Available machine capacity is 300,000 sets per day. The management of Ming's would like to determine the optimal combination of dimsum that would maximize its profits. Use the simplex method to find the solution. ? 2. Menu Masters is considering producing five models of cooking gas stoves that were projected to yield the following unit profits: Model [ A | 8 | C¢ D [et prof | 15600 | 00 | 1,000 | 4.000 | 2.500 The company is investing P10 million capital and 1,500 working days. Each model's capital and labor requirements are as follows Required | Required Working Capital per Unit | _Days per Unit 800 20 300 12 600 15 3,200 10 1,500 7 Prepare a linear program to find the best production plan based on the following objective and constraints. a. Achieye the maximum profit. b. Produce a maximum of 50 units per model ¢. Produce a minimum of 20 units per model. Solve using the simplex method. CHAPTER LINEAR PROGRAMMING PART 2. 65Further Readings + hhttp:/www.phpsimplex.com/en/simplex_method_example.htm + https:/www.sciencedirect.com/science/article/pil/S1110016818302126 Distribu Part1 Topics Characteris Assumptio ransporta 2 Stricture o Transport ‘Transportat 4 Obtaining Solution Optimal Fe Solution Learning Outco Define a tra problem ani assumption Formulate 1 in a transpo matrix. Demonstrat find the iit solution Apply the st method and method. 66 MANAGEMENT SCIENCE