Page 258 -

238 CHAPTER 5 LINEAR PROGRAMMING: THE SIMPLEX METHOD

Min 2x 1 þ 3x 2
s:t:
1x 1 125 Demand for product A
1x 1 þ 1x 2 350 Total production
2x 1 þ 1x 2 600 Processing time
x 1 ; x 2 0

We convert a To solve this problem using the Simplex method, we first multiply the objective
minimization problem to function by 1 to convert the minimization problem into the following equivalent
a maximization problem
by multiplying the maximization problem:
objective function by 1.
Max 2x 1 þ 3x 2
s:t:
1x 1 125 Demand for product A
1x 1 þ 1x 2 350 Total production
2x 1 þ 1x 2 600 Processing time
x 1 ; x 2 0

The tableau form for this problem is as follows:

Max 2x 1 3x 2 þ 0s 1 þ 0s 2 þ 0s 3 Ma 1 Ma 2
s:t:
¼ 125
1x 1 1s 1 þ 1a 1
1x 1 þ 1x 2 1s 2 þ 1a 2 ¼ 350
2x 1 þ 1x 2 þ 1s 3 ¼ 600
x 1 ; x 2 ; s 1 ; s 2 ; s 3 ; a 1 ; a 2 0

The initial simplex tableau is shown here:

x 1 x 2 s 1 s 2 s 3 a 1 a 2
Basis c B 2 3 0 0 0 M M
M *1 0 1 0 0 1 0 125
a 1
M 1 1 0 1 0 0 1 350
a 2
0 2 1 0 0 1 0 0 600
s 3
2M M M M 0 M M 475M
z j
2+ 2M 3+ M M M 0 0 0
c j – z j

At the first iteration, x 1 is brought into the basis and a 1 is removed. After
dropping the a 1 column from the tableau, the result of the first iteration is as follows:

x 1 x 2 s 1 s 2 s 3 a 2
Basis c B 2 3 0 0 0 M

2 1 0 1 0 0 0 125
x 1
M 0 1 1 1 0 1 225
a 2
0 0 1 *2 0 1 0 350
s 3
z j 2 M 2 M M 0 M 250 225M
c j – z j 0 3+ M 2+ M M 0 0

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.