4.7 Karmarkar’s Interior Method 225We now define a new vectorzas
z=
z
zn− 2
zn− 1
zn
andsolve the following related problem instead of the problem in Eqs. (4.64):
Minimize{βdT 0 0 M}zsubjectto
[α]^0 −
n
βb(
n
βb−[α]e)
0 0 n 0
z={
0
1
}
eTz+zn− 2 +zn− 1 +zn= 1
z≥ 0(4.65)
whereeis an (m−1)-component vector whose elements are all equal to 1,zn− 2 is a
slack variable that absorbs the difference between 1 and the sum of other variables,
zn− 1 is constrained to have a value of 1/n,andMis given a large value (corresponding
to the artificial variablezn) to forceznto zero when the problem stated in Eqs. (4.61)
has a feasible solution. Equations (4.65) are developed such that ifzis a solution to
these equations,X=βzwill be a solution to Eqs. (4.61) if Eqs. (4.61) have a feasible
solution. Also, it can be verified that the interior pointz=( 1 /n)eis a feasible solution
to Eqs. (4.65). Equations (4.65) can be seen to be the desired form of Eqs. (4.61) except
for a 1 on the right-hand side. This can be eliminated by subtracting the last constraint
from the next-to-last constraint, to obtain the required form:
Minimize{βdT 0 0 M}zsubjectto
[α]^0 −
n
βb(
n
βb−[α]e)
−eT − 1 (n− 1 ) − 1
z={
0
0
}
eTz+zn− 2 +zn− 1 +zn= 1z≥ 0(4.66)
Note:When Eqs. (4.66) are solved, if the value of the artificial variablezn> 0 ,
the original problem in Eqs. (4.61) is infeasible. On the other hand, if the value
of the slack variablezn− 2 = , the solution of the problem given by Eqs. (4.61) is 0
unbounded.
Example 4.12 Transform the following LP problem into a form required by Kar-
markar’s method:
Minimize 2x 1 + 3 x 2