GROUP 9_Assignment1_Optimization

University of Windsor MECH8290-38: Optimization Assignment #1 Group 9 Information Name Student Number Chukwuebuka Bakwenye 103957780 Abhishek Dilip Patil 110100747 Aditya Kumar 110092110 Dinesh Kumar Miryala 110094365

QUESTION 1 A feedlot yard seeks to minimize the total daily cost of the feed mix that contains corn and soybean. The price of corn ( 𝑥 1) is $0.2/lb and the price of soybean ( 𝑥 2) is $0.7/lb. The amount of protein in each pound of corn and soybean is 0.08 lb and 0.56 lb, respectively. The total amount of protein should equal at least 40% of the total feed mix. The amount of fiber in each pound of corn and soybean is 0.03 lb and 0.11 lb, respectively. The total amount of fiber should be at most 10% of the total feed mix. The farm requires at least 600 lb of total feed mix every day. a) What would be the objective function and mathematical equations of constraints? b) Use the graphical method and show the feasible solution area. c) Determine the optimal solution using a graphical method. SOLUTION: 1(a) Protein Fiber Profit X1 0.08 0.03 0.2 X2 0.56 0.11 0.7 Z = $0.2 x1 + $0.7 x2 0.08x1 + 0.56x2 > 0.4(x1 + x2); (Constraint 1) 0.03x1 + 0.11x2 < 0.1(x1 + x2); (Constraint 2) x1 + x2 > 600; (Constraint 3) x1, x2 > 0. (Non-negativity constraint) OR 0.32x1 – 0.16x2 ≤ 0; (Constraint 1) -0.07x1 +0.01x2 ≤ 0; (Constraint 2) x1 + x2 ≥ 600; (Constraint 3) x1, x2 > 0. (Non-negativity constraint) 1(b) The graph below shows the feasible solution area (shaded in blue).

QUESTION 2 a) Write down the augmented equations to be used in the simplex table. b) Fill the simplex table (identify the basic variables, artificial variables, and ratio column). c) Illustrate the simplex table at the end of iteration 1. d) Continue the solution step by step and find the optimal solution. e) Determine the unused material(s). SOLUTION: Minimize: Z = 0.2x1 +0.7x2 0.32x1 – 0.16x2 ≤ 0; (Constraint 1) -0.07x1 +0.01x2 ≤ 0; (Constraint 2) x1 + x2 ≥ 600; (Constraint 3) x1, x2 > 0. (Non-negativity constraint) 2a) To create the augmented equations, we need to introduce two slack variables to infer unusedresources in constraints 1 and 2, we need to introduce one surplus variable as well as an artificial variable in constraint 3 (due to its greater than inequality). Then we get rid of the x6 variable from equation (0) by subtracting [M*equation (3)] from equation (0). This will give us the final augmented equations. Note, we multiplied the objective function by -1 to turn it from a minimize objective function to a maximize objective function. The final augmented equations can be seen below: Maximize: -Z + (-M+0.2) x1+(-M+0.7) x2 + Mx5 = -600M …… . …… (0) 0.32 x1 - 0.16x2 + x3 = 0 …… . ………… ..(1) -0.07x1 + 0.01x2 + x4 = 0 …… . ………… ..(2) x1 + x2 - x5 + x6 =600 ……………… (3) 2(b) ITERATION 0 Basic Variables Eq. Z x1 x2 x3 x4 x5 𝑥 6 RHS Ratio Z (0) -1 -M+0.2 -M+0.7 0 0 M 0 -600M ----- x3 (1) 0 0.32 -0.16 1 0 0 0 0 0 x4 (2) 0 -0.07 0.01 0 1 0 0 0 ------ 𝑥 6 (3) 0 1 1 0 0 -1 1 600 600 x1 and x2 are non-basic variables, x3 and x4 are slack variables, x5 is a surplus variable, and x6 is an artificial variable.

2(c) The simplex table at the end of iteration 1 can be seen below: ITERATION 1 Basic Variables Eq. Z x1 x2 x3 x4 x5 𝑥 6 RHS Ratio Z (0) -1 0 -(3M/8) +8/10 (25/8M) -(5/8) 0 M 0 -600M ----- x3 (1) 0 1 -0.5 25/8 0 0 0 0 ------ x4 (2) 0 0 -1/40 7/32 1 0 0 0 ------ 𝑥 6 (3) 00 0 3/2 -25/8 0 -1 1 600 600 From this table, we can see that x1 = 0, x2 =0, x3 = 0, x4 = 0, x5 = 0, and x6 = 600. The artificial variable being 600 after this iteration means that the solution is NOT feasible. Additionally, this iteration fails the optimality test because -(3M/8) +8/10 is a negative number. Hence more iterations are needed to solve this problem . 2(d) This solution in iteration 1 fails the optimality test (because there are negative values in Z row); hence we need one or more iterations to determine the optimal solution. Iteration 2 can be seen below. ITERATION 2 (OPTIMAL SOLUTION) Basic Variables Eq. Z x1 x2 x3 x4 x5 𝑥 6 RHS Ratio Z (0) -1 0 0 15/8 0 8/15 M - (8/15) -320 ------- x1 (1) 0 1 0 25/12 0 -0.33 0.33 200 ------- x4 (2) 0 0 0 1/16 1 -1/60 1/60 10 ------- x2 (3) 0 0 0 -25/12 0 -2/3 -2/3 400 ------- This solution passes the optimality test (because M is a very large POSITIVE number; hence M – 8/15 is positive) From this table, we can see that x1 = 200, x2 = 400, and x4 = 10; furthermore, x3, x5 and 𝑥6 are equal to Zero. The artificial variable being 0 after this iteration means that the solution is feasible. Hence, from our graph in question 1, this solution is on Point A (200,400) with -Z = - 320 (i.e: Z = $320). Therefore, the simplex method confirms the graphical solution ’ s answer. 2(e) From the solution values above, we see that x4 = 10. Recall: x4 was added as a slack variable for fiber (i.e: unused fiber resources). This means that 10 lbs of fiber were unused during the operations.

3(b). To create the augmented, we need to introduce two slack variables to infer unused resources in constraints 1 and 2, we need to introduce one surplus variable as well as an artificial variable in constraint 3 (due to its greater than inequality). Maximize: Z - 4x1 - 7x2 + 0x3 + 0x4 + 0x5 + M x6 = 0 …… .. …..equation (0) Subject to: x1 + 2x2 + x3 = 9 ……… . …equation (1) 5x1 + 6x2 +x4 = 30 ……… ...equation (2) 3x1 + 2x2 -x5 + x6 = 16 ……… ...equation (3) x1, x2 ≥ 0 (non -negativity) Now we must remove the artificial variable from equation (0). We do this by subtracting [M*equation (3)] from equation (0). Therefore, the final Augmented equations would be: Z - (3M+4)x1 – (2M+7)x2 + Mx5 = - 16M ………..equation (0) Subject to: x1 + 2x2 + x3 = 9 ………… . …equation (1) 5x1 + 6x2 +x4 =30 …………… equation (2) 3x1 + 2x2 -x5 + x6 = 16 …………… equation (3) x1, x2 ≥ 0 (non -negativity) 3(c). The simplex table at Iteration 0 is: ITERATION 0 Basic Variables Eq. Z x1 x2 x3 x4 x5 𝑥6 RHS Ratio Z (0) 1 -3M-4 -2M-7 0 0 M 0 -16M ----- x3 (1) 0 1 2 1 0 0 0 9 9 x4 (2) 0 5 6 0 1 0 0 30 6 𝑥6 (3) 0 3 2 0 0 -1 1 16 5.33

3(d). The simplex table at the end of iteration 1 is seen below: ITERATION 1 Basic Variables Eq. Z x1 x2 x3 x4 x5 𝑥6 RHS Ratio Z (0) 1 0 -4.33 0 0 -1.33 M+1.33 21.33 ----- x3 (1) 0 0 1.33 1 0 0.33 -0.33 3.667 2.75 x4 (2) 0 0 2.67 0 1 1.67 -1.67 3.33 1.25 x1 (3) 0 1 0.67 0 0 -0.33 0.33 5.33 8 From this table, we can see that x1 = 5.33, x3 = 3.667, and x4 = 3.33; furthermore, x2, x5 and 𝑥6 are equal to Zero. The artificial variable being 0 after this iteration means that the solution is feasible. Hence, from our graph above, this solution is on point C (5, 0) with Z = 21.33. 3(e). This solution in iteration 1 fails the optimality test (because there are negative values in Z row); hence we need one or more iterations to determine the optimal solution. ITERATION 2 Basic Variables Eq. Z x1 x2 x3 x4 x5 𝑥6 RHS Ratio Z (0) 1 0 0 0 1.625 1.375 M-1.375 26.75 ------- x3 (1) 0 2 0 1 -0.5 -0.5 0.5 2 ------- x2 (2) 0 0 1 0 0.375 0.625 -0.625 1.25 ------- x1 (3) 0 1 0 0 -0.25 -0.75 0.75 4.5 ------- From this table, we can see that x1 = 4.5, x2 = 1.25, and x3 = 2; furthermore, x4, x5 and 𝑥6 are equal to Zero. The artificial variable being 0 after this iteration means that the solution is feasible. Hence, from our graph above, this solution is on point A (4.5, 1.25) with Z = 26.75. This solution passes the optimality test (because M is a very large POSITIVE number; hence M - 1.375 is positive). Therefore, the Simplex Method confirms that the optimal solution is on Point A on the graph above: x1 = 4.5, x2 = 1.25, and Z = 26.75.

Therefore, the equation for Z shows that: • A unit change in available resource 1 (±1 Kg) changes Z by $1.5k (= $3/2k). • A unit change in available resource 2 (±1 Kg) changes Z by $0. • A unit change in available resource 3 (±1 Kg) changes Z by $1k. This means that the corresponding dual prices are 3/2k, 0, and 1k ($/Kg) for available resources: 1, 2, and 3, respectively. 4(c) x1 = 6 + 3 D1 + 0 D2 - 2 D3  0 x4 = 4 + 1/5 D1 + 1 D2 - 4/3 D3  0 x2 = 3 + 3/4 D1 + 0 D2 + 1 D3  0 x1 = 6 + 3 D1 + - 2 D3  0 x4 = 4 + 1/5 D1 +1 D2 - 4/3 D3  0 x2 = 3 + 3/4 D1 + + 1 D3  0 Feasibility Range for Resource 1: For obtaining the feasibility range of D1, the Dual Price of Plant-1, D2 and D3 will be assumed to be ZERO. x1 = 6 + 3 D1 + - 2 D3  0 x4 = 4 + 1/5 D1 +1 D2 - 4/3 D3  0 x2 = 3 + 3/4 D1 + + 1 D3  0 D2=D3=0 x1 = 6 + 3 D1  0 D1  -2 ( i) x4 = 4 + 1/5 D1  0 D1  -20 ( ii) x2 = 3 + 3/4 D1  0 D1  -4 ( iii) • (i), (ii), (iii): D1  -2 • This means that the Dual Price for resource 1 is valid in the feasibility range D1  -2.

Feasibility Range for Resource 2: For obtaining the feasibility range of D2, the Dual Price of Plant-2, D1 and D3 will be assumed to be ZERO. x1 = 6 + 3 D1 + - 2 D3  0 x4 = 4 + 1/5 D1 +1 D2 - 4/3 D3  0 x2 = 3 + 3/4 D1 + + 1 D3  0 D1=D3=0 x1 = 6  0 6  0 ( i) x4 = 4 + 1 D2  0 D2  -4 ( ii) x2 = 3  0 3  0 ( iii) • (i), (ii), (iii): D 2  -4 • This means that the Dual Price for resource 2 is valid in the feasibility range D2  -4. Feasibility Range for Resource 3: For obtaining the feasibility range of D3, the Dual Price of Plant-3, D1 and D2 will be assumed to be ZERO. x1 = 6 + 3 D1 + - 2 D3  0 x4 = 4 + 1/5 D1 +1 D2 - 4/3 D3  0 x2 = 3 + 3/4 D1 + + 1 D3  0 D1=D2=0 x1 = 6 - 2D3  0 D3  3 ( i) x4 = 4 – 4/3 D3  0 D3  3 ( ii) x2 = 3 + 1D3  0 D3  -3 ( iii)