Engineering Optimization: Theory and Practice, Fourth Edition

156 Linear Programming I: Simplex Method

Step 4At this stage we notice that the present basic feasible solution does not contain

any of the artificial variablesy 1 andy 2 , and also the value ofwis reduced to

0. This indicates that phase I is completed.
   Step 5Now we start phase II computations by dropping thewrow from further
   consideration. The results of phase II are again shown in tableau form:

Basic Original variables Constant Value ofb

′′

i/a

′′

isfor

variables x 1 x 2 x 3 x 4 x 5 b′′i ais′′> 0

x (^41160117111211662)
x 2 − 117 1 −^10110115
Pivot
element
4
11
4
5 ←Smaller value
(x 2 drops from
next basis)
−f^98220118220 − 224 − 116
↑
Most negativec′′i(x 5 enters next basis)
Result of pivoting:
x 4 45 −^2511025
x 5 −^75115 − (^20145)
−f^21525500 −^25
Now, since allc′′iare nonnegative, phase II is completed. The (unique) optimal
solution is given by
x 1 =x 2 =x 3 = 0 (nonbasic variables)
x 4 =^25 , x 5 =^45 ( asic variablesb )
fmin=^25

3.11 MATLAB Solution of LP Problems

The solution of linear programming problems, using simplex method, can be found as

illustrated by the following example.

Example 3.8 Find the solution of the following linear programming problem using

MATLAB (simplex method):

Minimizef= −x 1 − 2 x 2 −x 3

subject to

2 x 1 +x 2 −x 3 ≤ 2

2 x 1 −x 2 + 5 x 3 ≤ 6