A22
Module A
The Simplex Solution Method
initial solution at the origin, its existence in the final solution would render the solution meaningless. To prevent this from happening, we must give the artificial variable a large cost contribution, or M.
An artificial variable in a maximization problem is given a large cost contribution to drive it
out of the problem.
The constraint for leather is a Ú inequality. It is converted to equation form by subtract ing a surplus variable and adding an artificial variable:
2 x 1 + 8 x 2  s 1 + A 2 = 8 0
As in the equality constraint, the artificial variable in this constraint must be assigned an objective function coefficient of M. The final constraint is a … inequality and is transformed by adding a slack variable:
x_{1 }+ s_{2 }= 20 The completely transformed linear programming problem is as follows: maximize Z = 400x_{1 }+ 200x_{2 }+ 0s_{1 }+ 0s_{2 } MA_{1 } MA_{2 }
subject to
x 1 , x 2 , s 1 , s 2 , A 1 , A 2 Ú 0 x 1 + s 2 = 2 0 2 x 1 + 8 x 2  s 1 + A 2 = 8 0 x 1 + x 2 + A 1 = 3 0
The initial simplex tableau for this model is shown in Table A21. Notice that the basic solution variables are a mix of artificial and slack variables. Note also that the thirdrow quotient for determining the pivot row (20 , 0) is an undefined value, or q. Therefore, this row would never be considered as a candidate for the pivot row. The second, third, and optimal tableaus for this problem are shown in Tables A22, A23, and A24.
M M 0
A A s
1 2 2
30 80 20
1 2 1
1 8 0
0 1 0
0 0 1
1 0 0
0 1 0
z
j
110M
3M
9M
M
0
M
M
c j  z j
400 + 3M
200 + 9M

M
0
0
0
200
0
0
M
M
x_{2 }
s_{1 }
s_{2 }
A_{1 }
A_{2 }
400 x_{1 }
Table A21 The Initial Simplex Tableau
c j
Basic Variables
Quantity
A x s
1 2 2
20 10 20
3/4 1/4 1
z
j
2,000  20M
50  3M/4
j
c z
j
350 + 3M/4
400 x_{1 }
Quantity
Basic Variables
Table A22 The Second Simplex Tableau
c j

M
200 0
200 x_{2 }
0 s_{1 }
0 1 0
1/8  1/8 0
200
25  M/8
0
25 + M/8
0
M
s_{2 }
A_{1 }
0
1
0
0
1
0
0
M
0
0