Transcript Document

THE TWO-POHASE METHOD
&
THE BIG-M METHOD
IENG511 Optimization Theory
Introduction
THE TWO-POHASE METHOD
SUMMARY OF THE TWO-POHASE METHOD & THE BIG-M METHOD
THE TWO-POHASE METHOD & THE BIG-M METHOD
Phase 1: (to find the extreme point)
1-change to standard format.
2-Add numbers to table and add the Artificial values if
necessary.
3-Try to do the row operation in order to change the
artificial values to zero.
x0
XB
x0
1
0
XB
0
I
XN
0
-1
B N
Xa
-1
B-1
RHS
0
B-1b
4-Change all number in the “ x0 “ row to non-positive
by using the row operation.
Phase 2: (takes us from feasible region to the optimal
point)
5-Remove artificial values from the table and rewrite
the table with using the C=(C1 , C2 , …) but with reverse
sign.
6-Change all number in the “ z “ row to non-positive by
using the row operation.
THE BIG-M METHOD
The Big-M Method steps are exactly like
the Tow-phase method:
1-change to standard format.
2-Add numbers to table and add the
Artificial values if necessary.
3-Try to do the row operation in order to
change the artificial values to zero.
4-Change all number in the “ z “ row to
non-positive by using the row operation.
x0
XB
x0
1
0
XB
0
I
XN
0
-1
B N
Xa
-M
B-1
RHS
0
B-1b
Example of
THE TWO-POHASE METHOD
Example of
THE TWO-POHASE METHOD
Example of
THE TWO-POHASE METHOD
Example of
THE TWO-POHASE METHOD
Example of
THE TWO-POHASE METHOD
.
Example of
THE TWO-POHASE METHOD
Example of
THE TWO-POHASE METHOD
Example of
THE TWO-POHASE METHOD
Example of
THE TWO-POHASE METHOD
Phase II
5
4
3
Phase I
Feasible point
2
1
Example of
THE BIG-M METHOD
Example of
THE BIG-M METHOD
Example of
THE BIG-M METHOD
Example of
THE BIG-M METHOD
Example of
THE BIG-M METHOD
Example of
THE BIG-M METHOD
Example of
THE BIG-M METHOD
5
4
2
1
3
Thanks for your attention