| Prev | Next | Top | TwoPhase |
maximize z = 3*x1 + x2
subject to s1 = - x1 + x2 - 1
s2 = x1 + x2 - 3
s3 = - 2*x1 - x2 + 4
x1, x2, s1, s2, s3 >= 0
Note that the basic solution corresponding to this dictionary
x1 = 0, x2 = 0, s1 = -1, s2 = -3, s3 = 4, z = 0
is not feasible
because s1 and s2 are less than zero.
maximize y = - x0
subject to s1 = x0 - x1 + x2 - 1
s2 = x0 + x1 + x2 - 3
s3 = x0 - 2*x1 - x2 + 4
x0, x1, x2, s1, s2, s3 >= 0
Note that in the basic solution, s2 has the smallest
(most negative) value.
Thus, if we pivot on the pair of variables (x0, s2),
the resulting basic solution will be feasible.
x0 = -x1 - x2 + s2 + 3
We replace all occurrences of x0 with the right hand side and obtain:
maximize y = - (-x1 - x2 + s2 + 3)
subject to s1 = (-x1 - x2 + s2 + 3) - x1 + x2 - 1
x0 = -x1 - x2 + s2 + 3
s3 = (-x1 - x2 + s2 + 3) - 2*x1 - x2 + 4
x0, x1, x2, s1, s2, s3 >= 0
maximize y = x1 + x2 - s2 - 3
subject to s1 = - 2*x1 + s2 + 2
x0 = - x1 - x2 + s2 + 3
s3 = - 3*x1 - 2*x2 + s2 + 7
x0, x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x0 = 3, x1 = 0, x2 = 0, s1 = 2, s2 = 0, s3 = 7, y = -3
x2 in the
auxiliary objective y is positive.
The corresponding feasibility constraint is
x2 = min( 3/1, 7/2 ) = 3
The corresponding pivot pair is (x2, x0).
The corresponding equation for x2 is
x2 = - x1 - x0 + s2 + 3
The corresponding dictionary is
maximize y = x1 - (x1 + x0 - s2 - 3) - s2 - 3
subject to s1 = - 2*x1 + s2 + 2
x2 = - x1 - x0 + s2 + 3
s3 = - 3*x1 + 2*(x1 + x0 - s2 - 3) + s2 + 7
x0, x1, x2, s1, s2, s3 >= 0
maximize y = - x0
subject to s1 = - 2*x1 + s2 + 2
x2 = - x0 - x1 + s2 + 3
s3 = 2*x0 - x1 - s2 + 1
x0, x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x0 = 0, x1 = 0, x2 = 3, s1 = 2, s2 = 0, s3 = 1, y = 0
We note that x0 is zero.
Hence this must be an optimal value for the auxiliary problem
and a feasible point for the original problem.
x0 = 0,
are equivalent to the constraints in the original problem.
Thus the following problem is equivalent to the original problem.
maximize z = 3*x1 + x2
subject to s1 = - 2*x1 + s2 + 2
x2 = - x1 + s2 + 3
s3 = - x1 - s2 + 1
x1, x2, s1, s2, s3 >= 0
Now we use the constraint equations to replace the
basic variables in the objective; i.e.,
z = 3*x1 + (- x1 + s2 + 3)
The resulting feasible dictionary representation is
maximize z = 2*x1 + s2 + 3
subject to s1 = - 2*x1 + s2 + 2
x2 = - x1 + s2 + 3
s3 = - x1 - s2 + 1
x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x1 = 0, x2 = 3, s1 = 2, s2 = 0, s3 = 1, z = 3
s2 for our next pivot column.
The corresponding feasibility constraint is
s2 = 1
The corresponding pivot pair is (s2, s3).
The corresponding equation for s2 is
s2 = - x1 - s3 + 1
The corresponding dictionary is
maximize z = 2*x1 + (- x1 - s3 + 1) + 3
subject to s1 = - 2*x1 + (- x1 - s3 + 1) + 2
x2 = - x1 + (- x1 - s3 + 1) + 3
s2 = - x1 - s3 + 1
x1, x2, s1, s2, s3 >= 0
maximize z = x1 - s3 + 4
subject to s1 = - 3*x1 - s3 + 3
x2 = - 2*x1 - s3 + 4
s2 = - x1 - s3 + 1
x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x1 = 0, x2 = 4, s1 = 3, s2 = 1, s3 = 0, z = 4
x1 for our next pivot column.
The corresponding feasibility constraint is
x1 = min(3/3, 4/2, 1/1) = 1
We choose (x1, s2) for the corresponding pivot pair
(we could have chosen (x1, s1)).
The corresponding equation for x1 is
x1 = - s2 - s3 + 1
The corresponding dictionary is
maximize z = (- s2 - s3 + 1) - s3 + 4
subject to s1 = - 3*(- s2 - s3 + 1) - s3 + 3
x2 = - 2*(- s2 - s3 + 1) - s3 + 4
x1 = - s2 - s3 + 1
x1, x2, s1, s2, s3 >= 0
maximize z = - s2 - 2*s3 + 5
subject to s1 = 3*s2 + 2*s3 + 0
x2 = 2*s2 + s3 + 2
x1 = - s2 - s3 + 1
x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x1 = 1, x2 = 2, s1 = 0, s2 = 0, s3 = 0, z = 5