a. Solve using simplex method. b. For each table you computed, check the formula For example, how to get the jth column

[answerhappygod]

a. Solve using simplex method.
b. For each table you computed, check the formula For example, how to get the jth column of the new table from the jth column of the initial table, and vice versa.
c. For the last table, check the optimality condition is satisfied by checking that z_j - c_j are non-negative for all j.
d. Set up and solve the dual problem. Then verify Theorem 3.7.
You should use example 1 on page 170 or the lecture notes as reference.
Please solve a,b,c,d for 6,7
6. Minimize z = 4x + 6y subject to x + 3y 2 5 2x + y 23 x 20, y = 0.

7. Maximize 2 = 8x, + 9x2 + 3x3 subject to *1 + x2 + 2x3 s 2 2x1 + 3x2 + 4x3 3 3x, + 3x2 + x3 34 A, 20. j = 1,2,3 *

THEOREM 3.7 (DUALITY THEOREM). (a) If either the primal or dual problem has a feasible solution with a finite optimal objective value, then the other problem has a feasible solution with the same objective value. (b) If the primal (13) and dual (14) problems have feasible solutions, then (b) the primal problem has an optimal solution-say, Xo; (ü) the dual problem has an optimal solution--say, Wo; and (iii) exo =bTwo Proof. (a) We convert the primal problem given in (13) to canonical form by introducing the vector of slack variables x' and writing, Maximize 2 = 10:02"[31] subject to = b В x 20 x 20. Let & be an optimal solution to this problem. Then there is a corre- sponding invertible matrix B that gives the values of the basic variables of * as B = B-'b (see Equation (5)). The objective function value at the optimal solution is then z = g = B-b. We let w = (B-1), and thus wT - CB-,

3.2 The Duality Theorem 175 and by substitution we obtain z = włb. Since z is a number, 2 =wb-(wb)" - btw. Thus, the objective function value for the dual problem, namely, btw, agrees with the objective function value for the primal problem. We now show that w is a feasible solution to the dual problem given by (14) From (7) we have t; - cB-'[A1], and from (8) we have 2, - t = !B-[A1], The optimality criterion of the simplex algorithm implies that 2-920. which can be written in vector form as 1- [co] - B-'[A1] - [60] 20. Multiplying in the previous equation and separating the partitioned matrix, we have CLB ' AC" and B-' 20. Using the definition of w, these inequalities can be written as WTA T W 20 or Aw2c W 20 Hence, w is a feasible solution to the dual problem given by (14) and yields the same value for the objective function of the dual problem as does the optimal solution x for the objective function of the primal problem. (b) Let x be a feasible solution to (13) and w be a feasible solution to (14). By Theorem 3.4 c'x s b'w. Since the objective function of the primal problem is bounded by b'w and the set of feasible solutions is not cmpty, there is a finite optimal solution

This equation shows that the entries in the objective row of a tableau are simply 2-4 = c - . (12) We may restate the optimality criterion for the simplex method: a tableau represents an optimal solution if and only if, for all j, z; -92 0. EXAMPLE 1. Consider the linear programming problem in canonical form from Section 2.1, Example 2. Maximize z = 8x: + 9x2 + 5xz subject to x + x2 + 2xy + x4 2 2x, + 3x2 + 4x, 3 6x, + 6x2 + 2x, x, 20, j = 1,2,...,6, where + X5 0 +x - 8 1 2 1 0 A= 2 3 4 0 1 0 6 2 0 0 9 - نہ دیا ت 3 and c- OOOO 6 After the first iteration of the simplex method we obtained Tableau 3.2 as a tableau representing the basic feasible solution in which 4 - 4 12 -2, and i, -6, and thus 01-0 7

3.2 The Dudlin Theorens 171 Tableau 3.1 11 ܕܐ 13 Is 16 0 + 24 X2 16 1 a 1 0 0 0 0 1 2 -6 -2 -2 0 7 0 3 0 We also have c-Ice cc] - [09 OJ. The problem in matrix form Ax=b can be written as A *1 + A2+2 + ... + Ag*- b or Since the tableau represents x, Xy, and x, as basic variables in this order, we may rearrange the previous equation as ---- 5+4)*6" ---- +0+ X + x + the entries being the coefficients of the basic variables in the objective function. Thus, 1 1 0 B- 0 3 0 0 6 1 and - 0 B-1 = 3 0 -2 Then - 3 0 $0 -2 1 which agrees with the right-hand side of the tableau. Furthermore, t; - B-, or -1 -6 хавь. ON

172 Chapter 3 Further Topics in Linear Programming The rest of the columns can be checked in the same manner. Finally, the entries in the objective row are 2, - c;, where z; - col. We have 2, = [090] . NWNW 6, and the first entry in the objective row is 2, - - 6 - 8 - -2. The other entries can be checked in the same manner. Δ Relations between the Solutions to the Primal and Dual Problems Problems We saw in Chapter 2 that there are three possible outcomes when attempting to solve a linear programming problem. 1. No feasible solutions exist. 2. There is a finite optimal solution. 3. Feasible solutions exist, but the objective function is unbounded. Since the dual problem is a linear programming problem, attempting to solve it also leads to these three possible outcomes. Consequently in considering relationships between solutions to the primal and dual prob- lems there are nine alternatives for the pair of solutions. We now present theorems that show which of these alternatives actually can occur. a