226 Linear Programming II: Additional Topics and Extensions
subject to3 x 1 +x 2 − 2 x 3 = 3
5 x 1 − 2 x 2 = 2
xi≥ 0 , i= 1 , 2 , 3SOLUTION It can be seen thatd= {2 3 0}T,[α]=[
3 1 − 2
5 −2 0
]
,b={
3
2
}
,andX=
x 1
x 2
x 3
We define the integersmandnasn=6 andm=3 and chooseβ=10 so thatz=1
10
z 1
z 2
z 3
Noting thate= { 1 , 1 , 1 }T, Eqs. (4.66) can be expressed asMinimize{20 30 0 0 0 M}zsubject to
[
3 1 − 2
5 −2 0
] {
0
0
}
−
6
10
{
3
2
}
×
6
10
{
3
2
}
−
[
3 1 − 2
5 −2 0
]
1
1
1
z= 0{−{1 1 1} −1 5 − 1 }z= 0
z 1 +z 2 +z 3 +z 4 +z 5 +z 6 = 1
z={z 1 z 2 z 3 z 4 z 5 z 6 }T ≥ 0whereMis a very large number. These equations can be seen to be in the desired
form.4.7.3 Algorithm
Starting from an interior feasible pointX(^1 ), Karmarkar’s method finds a sequence of
pointsX(^2 ),X(^3 ), · ·· using the following iterative procedure:
1.Initialize the iterative process. Begin with the center point of the simplex as the
initial feasible pointX(^1 )={
1
n1
n· · ·
1
n}T
.
Set the iteration number ask=1.