# A-32

# Module A

# The Simplex Solution Method

Figure A-9 The primal–dual relationships

Primal

Dual

maximize Z_{p }= 160

2 0 0 x 1 + x 2

minimize Z_{d }=

40

y 1 +

216

y_{2 }+

240

y 3

200 160 0

x x s

2 1 3

8 4 48

0 1 0

1 0 0

1/2 -1>2 6

-1>18 1/9 -2

0 0 1

z c -z

j

j

j

2,240

160 0

200 0

20 - 20

20/3 -20>3

0 0

T h i s o p t i m a l p r i m a l t a b l e a u a l s o c o n t a i n s i n f o r m a t i o n a b o u t t h e d u a l . I n t h e r o w o f c j - Table A-32, the negative values -20 and -20>3 under the s_{1 }and s_{2 }columns indicate that if one unit of either s_{1 }or s_{2 }was entered into the solution, profit would decrease by $20 or $6.67 (i.e., 20/3), respectively. z j

Recall that s_{1 }represents unused labor and s_{2 }represents unused wood. In the present solution s_{1 }and s_{2 }are not basic variables, so they both equal zero. This means that all the material and labor are being used to make tables and chairs, and there are no excess (slack) labor hours or board feet of material left over. Thus, if we enter s_{1 }or s_{2 }into the solution, then s_{1 }or s_{2 }no longer equals zero, and the use of labor or wood is decreased. If, for exam- ple, one unit of s_{1 }is entered into the solution, then one unit of labor previously used is not used, and profit is reduced by $20.

Let us assume that one unit of s_{1 }has been entered into the solution, so that we have one hour of unused labor (s_{1 }= 1). Now let us remove this unused hour of labor from the solu- tion so that all labor is again being used. We previously noted that profit was decreased by $20 by entering one hour of unused labor; thus, it can be expected that if we take this hour back (and use it again), profit will be increased by $20. This is analogous to saying that if we could get one more hour of labor, we could increase profit by $20. Therefore, if we could

0 s_{3 }

2

1 x+

4

2 x≤

40

18

1 x+

18

x_{2 }≤

216

24

1 x+

12

x_{2 }≤

240

0 s_{2 }

subject to:

Basic

160

200

0

Variables

Quantity

x_{1 }

x_{2 }

s_{1 }

Table A-32

x 1 , x 2 ≥ 0

1 2y + 18y_{2 }+ 24y_{3 }

≥

160

1 4y + 18y_{2 }+ 12y_{3 }

≥

200

The Optimal Simplex Solution for the Primal Model

c j

c_{j }

y_{1}, y_{2}, y_{3 }≥ 0

subject to:

q_{i }