Simplex Method for Linear Programming - Operations Research

Chapter 4 Simplex Method for Linear Programming. Shi-Shang Jang Chemical Engineering Department National Tsing-Hua University. Example 1: Inspector Problem.

1. Chapter 4 Simplex Method for
Linear Programming
Shi-Shang Jang
Chemical Engineering Department
National Tsing-Hua University

2. Example 1: Inspector Problem
Assume that it is desired to hire some inspectors for monitoring
a production line. A total amount of 1800 species of products
are manufactured every day (8 working hours), while two
grades of inspectors can be found. Maximum, 8 grade A
inspector and 10 grade B inspector are available from the job
market. Grade A inspectors can check 25 species/hour, with
an accuracy of 98 percent. Grade B inspectors can check 15
species/hour, with an accuracy of 95 percent. Note that each
error costs $2.00/piece. The wage of a grade A inspector is
$4.00/hour, and the wage of a grade B inspector is $3.00/hour.
What is the optimum policy for hiring the inspectors?

3. Problem Formulation

Assume that the x
1 grade A inspectors x
2 grade B inspects are
hired, then
total cost to be minimized

48 x
1 +38  x
2 +2580.022 x
1 +1580.052  x
2
=40 x
1 +36 x
2
manufacturing constraint

258 x
1 +158 x
2 1,800 200 x
1 +120 x
2 1,800
no. of inspectors available:

0 x
1 8

0 x
2 10

4. The Graphical Solution
X
2
=10
X
1
=
8
B(8,10)
(8,5/3)
C(3,10)
15
10
5
5 10

5. Theorem
Property: If there exists an optimal solution
to a LP, then at least one of the corner point
of the feasible region will always qualify to be
an optimal solution.

6. Special Cases
Alternate Solutions (non-unique solutions)
Max x
1+2x
2
s.t. x
1+2x
210
 x
1+ x
21
 x
2
4
 x
10, x
20
X
1
+
2
X
2
=
1
0
X
1
+
2
X
2
=
6
X
1
+
2
X
2
=
2
X
1
+
X
2
=
1
5
4
106
X
2
=4
X
2
X
1

7. Special Cases - continued
Unbounded Optima : A system has a feasible
region with open boundaries such that the
optima may appear at the infinity.
Example: For the previous example, in case
the constraint x
1+2x
210 is not given, then
moving far away from the origin increases
the objective function x
1
+2x
2
, and the maxim
Z would be +

8. Unbounded Optima
0 1 2 3 4 5 6 7 8 9 10
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
x1
x
2
x
1+x
2=1
x
2
=4
x
1+2x
2=2
x1+2x2=6
x1+2x2=10
x
1
+2x
2
=15

9. Example 2: Student Fab
The RIT student-run microelectronic
fabrication facility is taking orders for four
indigenously developed ASIC chips that can
be used in (1) touch sensors ($6, s4hr, m1hr,
v30), (2)LCD($10,s9hr, m1hr, v40), (3)
pressure sensors($9, s7hr, m3hr, v20), and
(4) controllers($20, s10hr, m8hr, v10).
Constraints : Student hr 600, machine
≦
hr 420, space 800
≦ ≦

10. The LP Problem
80010204030
42083
60010794..
209106max
4321
4321
4321
4321




xxxx
xxxx
xxxxts
xxxx
x

11. 4-2 The Basic Approach
Standard Form of Linear Programming
mnbbbxxx
bxaxaxa
bxaxaxa
bxaxaxats
xcxcxcy
mn
mnmnmm
nn
nn
nn
xxx
n





,0,,, ,0,,,



..
min
2121
2211
22222121
11212111
2211
,,,
21








12. Handling of in-equality Constraints
Case 1: Slack Variable:
x
1
+2x
2
+3 x
3
+4x
4
25
–Modified to
x
1
+2x
2
+3x
3+4x
4+ x
5=25
x50 is a slack variable.
Case 2: Surplus Variable:
2 x
1
+ x
2
-3 x
3
12
–Modified to
2 x
1
+ x
2
-3 x
3
- x
4
=12
x
40 is a surplus variable.

13. Handling of Equality Constraints
If s is unrestricted, i.e., s can be positive or
negative, then we set
s=s
+
-s
-
such that s
+
0, s
-
0.

14. Example
0,
533
2
7 ..
32max
21
321
321
321
321





xx
xxx
xxx
xxxts
xxxz
Modify to
0,,,,,
5333
2
7 ..
332max
765421
5421
75421
65421
5421





xxxxxx
xxxx
xxxxx
xxxxxts
xxxxz

15. Definitions
Definition: A feasible region, denoted by S is the set of all
feasible solution. Mathematically, .

Definition: An optimal solution is a vector x*S, s.t. z
0=c
T
x* is
maximum or minimum in where Z is termed by the optimal
value.
Definition: Alternate optimal solution is a set XS, s.t. all xX
has the same objective value z
0 and for all xS, and z=c
T
x, z
z
0.
Definition: If the solution set of LP contains only one element, it
is termed the unique optimum.
Definition: If the optimum value z approaches to infinity, then
the LP is said to have unbounded optimum.
 0, xbAxxS

16. 4-3 The Simplex Method
sconstraint for theApproach Variable Artificial
andn EliminatioJordan Gauss
0,,,



..
min
21
2211
22222121
11212111
2211
,,,
21






n
mnmnmm
nn
nn
nn
xxx
xxx
bxaxaxa
bxaxaxa
bxaxaxats
xcxcxcy
n







mnmnsmsmmmm
nnssmm
nnssmm
bxaxaxax
bxaxaxax
bxaxaxax










11,
22211,22
11111,11


Form Canonical

17. Definitions
Definition: A pivot operation is sequence of elementary row
operations that reduce the coefficients of a specified variable to
unity in one of the equation and zero elsewhere.

Definition: In the above canonical form, x
1,,x
m are termed the
basic variables or dependent variables, x
m+1, ,x
n are called
nonbasic variables or the independent variables.
Definition: The solution obtained from a canonical form is by
setting the nonbasic variable or independent variable to zero is
called a basic solution.
Definition: A basic feasible solution is a basic solution in which
the basic or dependent variables are non-negative.

18. Property
 Remark:
)!(!
!
solutions basic of no.
mnm
n
m
n











where nmjxnonbasicmibxbasic
iii ,,1,0 ,,,1,  
 Definition:    
mBmB
ccxx ,,,,,
11
  cx
Property: A feasible basic solution is a simplex of the feasible region.
Note: Given a canonical form and feasible basic solution,
then the objective function:



m
i
iiB
T
B
bcz
1
bc
where x
B
is a basic variable.

19. Approach (Simplex Method):
Start with an initial basic feasible solution in
canonical form.
Improve the solution by finding another basic
feasible solution if possible.
When a particular basic feasible solution is found,
and cannot be improved by finding new basic
feasible solution, the optimality is reached.
Definition: An adjacent basic solution differs from a basic
solution is exactly one basic variable.
Question: If one wants to find an adjacent feasible basic
solution from one feasible basic solution (i.e., switch to
another simplex), which adjacent basic solution gives lowest
objective function?

20. Derivation of Inner Product Rule
msmsm
ss
ss
bxax
bxax
bxax






222
111



Supposing, one wants to replace one of the original basic variable with
nonbasic variable x
s
, we firstly, increase xs from zero to one,
then for all i=1,,m,
1

s
isii
x
abx
and, for all j=m+1, ,n, js. x
j=0

21. Theorem 1 (Inner Product Rule)
 
s
m
i
isiinew
cabcz 
1
Relative cost, 


m
i
isisnew acczzz
1
(inner product rule)
More: (1) In a minimization problem, a basic feasible solution is optimal
if the relative costs of its all nonbasic variable are all positive or zero.
(2) One should choose an adjacent basic solution from which the relative
cost is the minimum.
Corollary: The alternate optima exists if z=0.

22. Theorem 2: (The Minimum Ratio Rule )
Given a nonbasic variable x
s
is change into
the basic variable set, then one of the basic
variable x
r should leave from the basic
variable set, such that:
i
a
b
x
is
i
a
s
is








,minmax
0
The above minimum happens at i=r.
Corollary: The above rule fails if there exist unbounded optima.

23. Example: The LP Problem
80010204030
42083
60010794..
209106max
4321
4321
4321
4321




xxxx
xxxx
xxxxts
xxxx
x

24. The Standard Form
80010204030
42083
60010794..
209106max
743213
643212
543211
4321




xxxxxg
xxxxxg
xxxxxgts
xxxxf

25. Table 1(s=4,r=6,rc=2)
Basic={5 6 7};Nonbasic={1 2 3 4}
　 6 10 9 20 0 0 0
C
B
Basis x
1
x
2
x
3
x
4
x
5
x
6
x
7
constraints
0 x
5
4 9 7 10 1 0 0 600 (600/10=60)
0 x
6
1 1 3 8 0 1 0 420(420/8=52.5)
0 x
7
30 40 20 10 0 0 1 800(800/10=80)
Z 6 10 9 20 - - - Z=0

26. Table 2(s=2,r=7,rc=3)
Basic={5 4 7};Nonbasic={1 2 3 6}
　 6 10 9 20 0 0 0
C
B
Basis x
1
x
2
x
3
x
4
x
5
x
6
x
7
constraints
0 x
5
2.75 7.75 3.25 0 1 -1.25 0 75(75/7.75=
9.6774)
20 x
4
0.125 0.125 0.375 1 0 0.125 0 52.5(52.5/0.125=4
20)
0 x
7
28.75 38.75 16.25 0 0 -1.25 1 275(275/38.75=
7.0798)
Z 3.5 7.5 1.5 - - -2.5 - Z=1050

27. Table 3
Basic={5 4 2};Nonbasic={1 7 3 6}
　 6 10 9 20 0 0 0
C
B
Basis x
1
x
2
x
3
x
4
x
5
x
6
x
7
constraints
0 x
5
-3 0 0 0 1 -1 -0.2 20
20 x
4
0.0323 0 0.3226 1 0 0.129 -0.0032 51.6129
10 x
2
0.7419 1 0.4194 0 0 -0.0323 0.0258 7.0968
Z -2.0645 - -0.1935 - - -1.6452 -2.2581 Z=1103.226

28. 2. The Two Phase Simplex Method-
Example
0,,
12
334
112..
3min
321
31
321
321
321





xxx
xx
xxx
xxxts
xxx

29. The Standard Form
0,,,,
12
324
112 ..
3min
54321
31
5321
4321
321





xxxxx
xx
xxxx
xxxxts
xxx

30. Two Phase Approach-Phase I
12
324
112..
min
731
65321
4321
76




xxx
xxxxx
xxxxts
xx

31. Two Phase Approach-Phase I
Table 1
　  0 0 0 0 0 1 1 
CB Basis x1 x2 x3 x4 x5 x6 x7 constraints
0 x4 1 -2 1 1 0 0 0 11(11/1=11)
1 x6 -4 1 2 0 -1 1 0 3(3/2=1.5)
1 x7 -2 0 1 0 0 0 1 1(1/1=1)
Z  6 -1 -3 - 1 - - Z=4

32. Two Phase Approach-Phase I
Final
　  0 0 0 0 0 1 1 
CB Basis x1 x2 x3 x4 x5 x6 x7 constraints
0 x4 3 0 0 1 -2 2 -5 12
0 x2 0 1 0 0 -1 1 -2 1
0 x3 -2 0 1 0 0 0 -1 1
Z  - - - - - - - Z=0

33. Two Phase Approach-Phase II
Table 1
　  -3 1 1 0 0 
CB Basis x1 x2 x3 x4 x5 constraints
0 x4 3 0 0 1 -2 12(12/3=4)
1 x2 0 1 0 0 -1 1(1/0=)
1 x3 -2 0 1 0 0 1(1/-2<0)
Z  -1 - - - 5 Z=2

34. Two Phase Approach-Phase II
Final
　  -3 1 1 0 0 
CB Basis x1 x2 x3 x4 x5 constraints
-3 x1 1 0 0 0.3333 -0.667 4
1 x2 0 1 0 0 -1 1
1 x3 0 0 1 0.6667 -1.333 9
Z  - - - - - Z=-2

35. Example: Multi-Products
Manufacturing
A company manufactures three products: A, B, and
C. Each unit of product A requires 1 hr of
engineering service, 10 hr of direct labor, and 3lb of
material. To produce one unit of product B requires
2hr of engineering, 4hr of direct labor, and 2lb of
material. In case of product C, it requires 1hr of
engineering, 5hr of direct labor, and 1lb of material.
There are 100 hr of engineering, 700 hr of labor, and
400 lb of material available. Since the company
offers discounts for bulk purchases, the profit figures
are as shown in the next slide:

36. Example- Continued
Formulate a linear program to determine the most profitable product mix.
Product A Product B Product C
Sales unitsUnit profitvariable
s
Sales unitsUnit profitvariablesSales unitsUnit profitvariables
0-40 10 X
1
0-50 6 X
5 0-100 5 X
8
40-100 9 X
2
50-100 4 X
6
Over 1004 X
9
100-150 8 X
3
Over 100 3 X
7
Over 150 7 X
4

37. Problem Formulation
Let’s denote the variables as shown in the table, then
we have the following:
0
600
400
400)(1)(2)(3
700)(5)(4)(10
100)(1)(2)(1..
4534678910max
9
2
1
987654321
987654321
987654321
987654321
,,
101







X
X
X
XXXXXXXXX
XXXXXXXXX
XXXXXXXXXts
XXXXXXXXX
XX



38. MATLAB PROGRAM
f=[-10 -9 -8 -7 -6 -4 -3 -5 -4]';
A=[1 1 1 1 2 2 2 1 1; 10 10 10 10 4 4 4 5 5;3 3 3 3 2
2 2 1 1];
b=[100;700;400];
Aeq=[];beq=[];
LB=[0 0 0 0 0 0 0 0 0];
UB=[40 60 50 Inf 50 50 Inf 100 Inf];
[X,FVAL,EXITFLAG,OUTPUT,LAMBDA]=LINPROG(
f,A,b,Aeq,beq,LB,UB)

39. Solution
X’= 40.0000 22.5000 0.0000 0.0000 18.7500 0.0000 0.0000 0.0000
0.0000
FVAL =-715.0000
EXITFLAG =1
OUTPUT =
 iterations: 7
 cgiterations: 0
 algorithm: 'lipsol'
LAMBDA =
 ineqlin: [3x1 double]
 eqlin: [0x1 double]
 upper: [9x1 double]
 lower: [9x1 double]

40. 3. Sensitivity Analysis
Shadow Prices: To evaluate net impact in
the maximum profit if additional units of
certain resources can be obtained.
Opportunity Costs: To measure the negative
impact of producing some products that are
zero at the optimum.
The range on the objective function
coefficients and the range on the RHS row.

41. Example
A factory manufactures three products, which
require three resources – labor, materials
and administration. The unit profits on these
products are $10, $6 and $4 respectively.
There are 100 hr of labor, 600 lb of material,
and 300hr of administration available per
day. In order to determine the optimal
product mix, the following LP model is
formulated and solve:

42. Basic LP Problem
0,,
ation)(administr 300622
(material) 6005410
(labor) 100..
4610max
321
321
321
321
321





xxx
xxx
xxx
xxxts
xxxZ

43. Optimal Solution and Sensitivity
Analysis
x1=33.33, x2=66.67,x3=0,Z=733.33
Shadow prices for row 1=3.33, row 2=0.67,
row 3=0
Opportunity Costs for x3=2.67
Ranges on the objective function coefficients:
6 c
≦
1(10) 15, 4 c
≦ ≦
2(6) 10,
≦
-∞ c
≦
3
(4) 6.67
≦

44. Optimal Solution and Sensitivity
Analysis- Continued
60 b
≦
1
(100) 150, 400 b
≦ ≦
2
(600) 1000,
≦
200 b
≦
3(300) ∞
≦

45. 100% Rules
100% rule for objective function coefficients
100% rule for RHS constants
%100


j j
j
c
c
%100


j j
j
b
b

46. Examples
Unit profit on product 1 decrease by $1, but increases by $1
for products 2 and 3, will the optimum change?(δc
1=-1, Δc
1=-
4, δc
2=1, Δc
2=4, δc
3=1, Δc
3=2.67)
Simultaneous variation of 10 hr decrease on labor 100 lb
increase in material and 50hr decrease on administration
1875.0
67.2
1
4
1
4
1



1
100
50
400
100
40
10





