X hits on this document

490 views

0 shares

19 / 63

Simplex Solution of a Minimization Problem

A-19

The cj - zj row is changed to zj - cj in the simplex tableau for a minimization problem.

The Simplex Tableau for a Minimization Problem The initial simplex tableau for a minimization model is developed the same way as one for a maximization model, except for one small difference. Rather than computing c - z in the bottom row of the tableau, we compute z - c , which represents the net per unit decrease in cost, and the largest positive value is selected as the entering variable and pivot column. (An alternative would be to leave the bottom row as c - z and select the largest negative value as the pivot column. However, to maintain a consistent rule for selecting the pivot column, we will use z - c .)

j

j

j

j

j

j

j

j

Artificial variables are always included as part of the initial basic feasible solution when they exist.

The initial simplex tableau for this model is shown in Table A-17. Notice that A1 and A2 form the initial solution at the origin, because that was the reason for inserting them in the first place — to get a solution at the origin. This is not a basic feasible solution, since the origin is not in the feasible solution area, as shown in Figure A-4. As indicated previously, it is an artificially created solution. However, the simplex process will move toward feasibility in subsequent tableaus. Note that across the top the decision variables are listed first, then surplus variables, and finally artificial variables.

Table A-17 The Initial Simplex Tableau

c j

# M

M

Basic Variables

A1 A z j - c 2 j z j

6

Quantity

x1

16

2

24

4

40M

6M

6M - 6

7M - 3

3 x2

4

3

7M

0

0

M

M

s1

s2

A1

A2

-1

0

1

0

0

-1

0

1

-M

-M

M

M

-M

-M

0

0

Once an artificial variable is selected as the leaving variable, it will never reenter the tableau, so it can be eliminated.

In Table A-17 the x2 column was selected as the pivot column because 7M - 3 is the l a r g e s t p o s i t i v e v a l u e i n t h e r o w . w a s s e l e c t e d a s t h e l e a v i n g b a s i c v a r i a b l e ( a n d A 1 z j - pivot row) because the quotient of 4 for this row was the minimum positive row value. c j

The second simplex tableau is developed using the simplex formulas presented earlier. It is shown in Table A-18. Notice that the A1 column has been eliminated in the second sim- plex tableau. Once an artificial variable leaves the basic feasible solution, it will never return because of its high cost, M. Thus, like the booster rocket, it can be eliminated from the tableau. However, artificial variables are the only variables that can be treated this way.

Table A-18 The Second Simplex Tableau

x2

4

1/2

1

-1>4

0

0

A2

12

5/2

0

3/4

-1

1

j z

12M + 12

5M>2 + 3>2

3

-3>4 + 3M>4

-M

M

j j z -c

5M>2 - 9>2

0

-3>4 + 3M>4

-M

0

T h e t h i r d s i m p l e x t a b l e a u , w i t h r e p l a c i n g i s s h o w n i n T a b l e A - 1 9 . B o t h t h e a n d c o l u m n s h a v e b e e n e l i m i n a t e d b e c a u s e b o t h v a r i a b l e s h a v e l e f t t h e s o l u t i o n . T h e r o w x 1 A 2 A 1 A 2 , x 1

Basic

6

3

0

0

M

j c

Variables

Quantity

x1

x2

s1

s2

A2

3

# M

 Document views 490 Page views 490 Page last viewed Wed Jan 18 14:48:26 UTC 2017 Pages 63 Paragraphs 3770 Words 30893