Optimization Methods - Recitation 4 - Solutions

Example Solutions 4 Exerise 5.7 BT Solve the problem with b1 = 300, 000, b2 = 240, 000, and b3 = 30, 000. Solution The normal formulation for this problem is as follows: x1: number of 1-pad packs produced, x2: number of 5-pad packs produced, and x3: number of 20pad packs produced. The formulation is s.t. x1 + 7x2 + 23x3 ≤ b1 min −0.2x1 − 0.7x2 − 4.7x3 x1 + 6.75x2 + 22.5x3 ≤ b2 x2 + 3x3 ≤ b3 x1 , x2 , x3 ≥ 0 Introducing three slack variables and we have the initial tableau 0 −0.2 −0.7 −4.7 0 0 0 1 7 23 1 0 0 x4 = 300 1 6.75 22.5 0 1 0 x5 = 240 0 1 3 0 0 1 x6 = 30 The final tableau is 50 x1 = 15 x3 = 10 x4 = 55 0 2.15/3 0 0 0.2 0.2/3 1 −0.75 0 0 1 −7.5 0 1/3 1 0 0 1/3 0 0.25/3 0 1 −1 −0.5/3 The formulation we developed in the class is as follows: x1 : number of pads produced, x2 : number of small notebooks produced, and x3 : number of large notebooks produced. The formulation is then min s.t. −0.2x1 + 0.1x2 − 0.7x3 x1 + 2x2 + 3x3 ≤ b1 x1 + 1.75x2 + 2.5x3 ≤ b2 x2 + 3x3 ≤ b3 −x1 + 5x2 + 20x3 ≤ 0 x1 , x2 , x3 ≥ 0 1 Introducing four slack variables and we have the initial tableau 0 −0.2 0.1 −0.7 0 0 0 0 1 2 3 1 0 0 0 x4 = 300 1 1.75 2.5 0 1 0 0 x5 = 240 0 1 3 0 0 1 0 x6 = 30 −1 5 20 0 0 0 1 x7 = 0 The final tableau is 50 x1 = 215 x3 = 10 x4 = 55 x7 = 15 0 1.55/3 0 0 0.2 0.2/3 0 1 2.75/3 0 0 1 −2.5/3 0 0 1/3 1 0 0 1/3 0 0 0.25/3 0 1 −1 −0.5/3 0 0 −0.75 0 0 1 −7.5 1 The third formulation is using the fact that the objective function can be written as −0.1x1 + 1.4x2 + 6.7x3 + 0.3x7 , where x7 is the surplus variable in the second formulation or the number of 1-pad packs. The formulation is then min 0.1x1 − 1.4x2 − 6.7x3 − 0.3x7 s.t. x1 + 2x2 + 3x3 ≤ b1 x1 + 1.75x2 + 2.5x3 ≤ b2 x2 + 3x3 ≤ b3 −x1 + 5x2 + 20x3 + x7 = 0 x1 , x2 , x3 , x7 ≥ 0 Introducing four slack variables and we have the initial tableau 0 −0.2 0.1 −0.7 0 0 0 0 1 2 3 1 0 0 0 x4 = 300 1 1.75 2.5 0 1 0 0 x5 = 240 0 1 3 0 0 1 0 x6 = 30 x7 = 0 −1 5 20 0 0 0 1 The final tableau is 50 x1 = 215 x3 = 10 x4 = 55 x7 = 15 0 1.55/3 0 0 0.2 0.2/3 0 1 2.75/3 0 0 1 −2.5/3 0 0 1/3 1 0 0 1/3 0 0 0.25/3 0 1 −1 −0.5/3 0 0 −0.75 0 0 1 −7.5 1 You can see that the third and second final tableaux are the same. However, what changed here are the dual variables (which ones and why?). With this development, please check to see which formulation can be used to answer which questions from the exercise. In addition, from this example, you can also see that it is not necessary that in the initial tableau, the reduced costs are the same as the objective coefficients. Please remember to use definitions to check everytime you write down a tableau. 2