X hits on this document

483 views

0 shares

22 / 63

# 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:

x1 + s2 = 20 The completely transformed linear programming problem is as follows: maximize Z = 400x1 + 200x2 + 0s1 + 0s2 - MA1 - MA2

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 A-21. Notice that the basic solution variables are a mix of artificial and slack variables. Note also that the third-row 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 A-22, A-23, and A-24.

-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

x2

s1

s2

A1

A2

400 x1

Table A-21 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 x1

Quantity

Basic Variables

Table A-22 The Second Simplex Tableau

c j

• -

M

200 0

200 x2

0 s1

0 1 0

1/8 - 1/8 0

200

-25 - M/8

0

25 + M/8

0

-M

s2

A1

0

1

0

0

1

0

0

-M

0

0

 Document views 483 Page views 483 Page last viewed Tue Jan 17 22:18:54 UTC 2017 Pages 63 Paragraphs 3770 Words 30893