Dantzig G., Thapa M. Linear programming. Vol.1. Introduction
Подождите немного. Документ загружается.
102 THE SIMPLEX METHOD
(b) Use the DTZG Simplex Primal software option on the problem.
3.10 Use the DTZG Simplex Primal software option to demonstrate that the following
system of inequalities in nonnegative variables is infeasible.
4x
1
+ x
3
− x
4
≥ 4
4x
1
+4x
2
+4x
3
+5x
4
≤ 4
5x
1
+3x
2
+ x
3
+2x
4
≤ 9
x
j
≥ 0,j=1,...,4.
3.11 As we shall see later (see Chapter 5)
Maximize 4y
1
− 4y
2
− 5y
3
= v
subject to 4y
1
− 4y
2
− 5y
3
≤ 0
4y
2
− 3y
3
≤ 0
y
1
− 4y
2
− y
3
≤ 0
y
1
− 5y
2
− 2y
3
≤ 0
y
j
≥ 0,j=1,...,3
is the dual of the system in Problem 3.10, assuming it has a zero coefficient
objective. Use the DTZG Simplex Primal software option to demonstrate that
it is unbounded. How could you have deduced that it is unbounded simply by
looking at it.
3.12 Solve the following linear program by hand and also by the DTZG Simplex
Primal software option to demonstrate that it is unbounded.
Minimize 1x
1
− 2x
2
+ x
3
+3x
4
= z
subject to 2x
1
− x
2
+ x
3
− x
4
≤ 10
−5x
1
+2x
2
− 2x
3
+ x
4
≤ 20
3x
1
− 4x
2
+4x
3
− 2x
4
≤ 30
x
j
≥ 0,j=1,...,4.
Write down the class of feasible solutions that cause z →−∞.
3.13 Consider the following linear program.
Minimize −x
1
− 2x
2
+ x
3
+2x
4
+3x
5
= z
subject to 2x
1
− x
2
− x
3
− x
4
+2x
5
=0
2x
1
− x
2
+2x
3
− x
4
+ x
5
=0
x
1
+ x
2
+ x
3
+ x
4
+ x
5
=0
x
j
≥ 0,j=1,...,5.
(a) Apply Phase I of the Simplex Method to obtain a feasible solution to the
linear program.
(b) At the end of Phase I, use each of the three methods of handling artificials
in the basis and proceed to Phase II.
3.14 Kuhn’s Example of Cycling.
Minimize −2x
1
− 3x
2
+ x
3
+12x
4
= z
subject to −2x
1
− 9x
2
+ x
3
+9x
4
≤ 0
1
3
x
1
+ x
2
−
1
3
x
3
− 2x
4
≤ 0
and x
1
≥ 0,x
2
≥ 0,x
3
≥ 0,x
4
≥ 0.
3.7 PROBLEMS 103
Add slack variables x
5
and x
6
and let the starting feasible basis contain x
5
and
x
6
. Assume that
• the index s of the incoming variable is chosen as the nonbasic variable with
the most negative reduced cost;
• the index j
r
of the outgoing variable is determined by looking at all ¯a
is
> 0
as specified in the Simplex Algorithm and choosing r = i as the smallest
index such that ¯a
is
> 0.
(a) Solve the problem by hand and show that it cycles after iteration 6.
(b) Re-solve the problem applying Bland’s rule to show that the Simplex Al-
gorithm converges to an optimal solution.
(c) Re-solve the problem using the Random Choice Rule to show that the
Simplex Algorithm converges to an optimal solution. (For example use dice
to make your selections.)
3.15 Beale’s Example of Cycling.
Minimize −3x
1
/4 + 150x
2
− x
3
/50 + 6x
4
= z
subject to x
1
/4 − 60x
2
− x
3
/25 + 9x
4
≤ 0
x
1
/2 − 90x
2
− x
3
/50 + 3x
4
≤ 0
x
3
≤ 1
and x
1
≥ 0,x
2
≥ 0,x
3
≥ 0,x
4
≥ 0.
Add slack variables x
5
, x
6
, and x
7
and let the starting feasible basis contain x
5
,
x
6
, and x
7
. Assume that
• the index s of the incoming variable is chosen as the nonbasic variable with
the most negative reduced cost;
• the index j
r
of the outgoing variable is determined by looking at all ¯a
is
> 0
as specified in the Simplex Algorithm and choosing r = i as the smallest
index such that ¯a
is
> 0.
(a) Solve the problem by hand and show that it cycles.
(b) Re-solve the problem applying Bland’s rule to show that the Simplex Al-
gorithm converges to an optimal solution.
(c) Re-solve the problem using the Random Choice Rule to show that the
Simplex Algorithm converges to an optimal solution. (For example use dice
to make your selections.)
3.16 Consider the following 2-equation, 5-variable linear program.
Minimize x
1
+7x
2
+5x
3
+ x
4
+6x
5
= z
subject to 1x
1
+2x
2
+2x
3
+5x
4
+4x
5
=10
3x
1
+6x
2
− 2x
3
+ x
4
− x
5
=30
x
j
≥ 0,j=1,...,5.
(a) Apply Phase I of the Simplex Method to obtain a feasible solution to the
linear program.
104 THE SIMPLEX METHOD
(b) If any artificials remain in the basis at the end of Phase I, use each of the
three methods of handling artificials in the basis.
(c) Apply Phase II to obtain an optimal solution.
3.17 Consider the following 3-equation, 5-variable linear program.
Minimize 2x
1
+3x
2
+4x
3
+ x
4
+ x
5
= z
subject to 2x
1
+ x
2
+ x
3
+ x
4
+ x
5
=10
2x
1
+3x
3
+2x
4
=6
x
2
− 2x
3
− x
4
+ x
5
=4
x
j
≥ 0,j=1,...,5.
(a) Apply Phase I of the Simplex Method to obtain a feasible solution to the
linear program.
(b) Show that an artificial remains in the basis at the end of Phase I because
the constraints are redundant.
(c) Apply Phase II to obtain an optimal solution.
3.18 Consider the following 3-equation, 4-variable linear program.
Maximize x
1
= z
subject to x
1
+3x
2
+4x
3
+ x
4
=20
2x
1
+ x
3
=5
−7x
1
+3x
2
+ x
4
=0
x
j
≥ 0,j=1,...,4.
(a) Apply Phase I of the Simplex Method to obtain a feasible solution to the
linear program.
(b) Show that an artificial remains in the basis at the end of Phase I because
the constraints are redundant.
(c) Apply Phase II to solve the problem.
3.19 Consider the following two variable linear program.
Maximize x
1
+ x
2
= z
subject to x
1
− x
2
≥ 1
x
1
+ x
2
≤ 3
2x
1
− x
2
≤ 3
x
1
≥ 0,x
2
≥ 0.
(a) Plot the feasible region.
(b) Solve the problem graphically.
(c) Show graphically that the optimal solution is degenerate.
(d) On the figure, indicate which constraint can be dropped to obtain a non-
degenerate optimal solution.
3.7 PROBLEMS 105
3.20 The purpose of this exercise is to examine the effect of changes to an optimal
solution as a result of changes to data.
Minimize 4x
1
+3x
2
+2x
3
+1x
4
= z
subject to 2x
1
− 3x
2
+ x
3
+2x
4
=10
1x
1
+4x
2
− 2x
3
+3x
4
≥ 16
x
j
≥ 0,j=1,...,4.
(a) Solve the linear program using the DTZG Simplex Primal software option.
(b) Change the cost on x
4
from 1 to 4 and re-solve the problem. Change it to
8 and re-solve the problem. How does the solution change in each case?
(c) Change the coefficient of x
2
in the second equation from a
22
=4toa
22
=5
and re-solve the problem. How does the solution change?
(d) Decrease the right hand side b
1
= 10 on the first equation to 8 and re-solve
the problem. Next increase it to b
1
= 12 and re-solve. Finally, increase it
to b
1
= 20 and re-solve. Examine how the solution changes in each case.
(e) Add a new activity 5 with level x
5
≥ 0 to the problem with c
5
= −1,
a
15
= −2, a
25
= −3. Re-solve the problem and indicate how the solution
changes. How could you have predicted this based on your original run?
(f) Add a new activity 6 with level x
6
≥ 0 to the problem with c
6
= −2,
a
16
=2,a
16
= 3. Re-solve the problem and indicate how the solution
changes. How could you have predicted this based on your original run?
(g) Add in turn the following rows to the original problem and examine how
the solution changes:
• x
1
+ x
2
+ x
3
+ x
4
≥ 4.
• 2x
1
+2x
2
+4x
3
+ x
4
≤ 8.
• x
1
+ x
2
+ x
3
+ x
4
=6.
3.21 Consider the linear program
Minimize 2x
1
+ x
2
+3x
3
= z
subject to x
1
+2x
2
+ x
3
≤ 6
2x
1
+ x
3
≤ 4
x
j
≥ 0,j=1,...,3.
(a) Add slack variables x
4
and x
5
to the inequality constraints. Starting with
x
4
and x
5
as basic variables, solve the linear program by hand using the
Revised Simplex Method.
(b) Multiply the second constraint by 2 and re-solve the problem. What is
the effect on the multipliers π
1
and π
2
? What is the effect on the optimal
solution?
3.22 Solve the following linear program by the Revised Simplex Method by hand,
starting with a full artificial basis.
Minimize x
1
− 3x
2
+ x
3
= z
subject to 2x
1
+ x
2
+ x
3
=6
x
1
+ x
2
− x
3
=2
x
j
≥ 0,j=1,...,3.
106 THE SIMPLEX METHOD
Change the first inequality to be a ‘≤’ inequality. Re-solve the problem; this
time add a slack variable x
4
to the first constraint and an artificial variable x
5
to the second constraint and minimize w = x
6
.
3.23 Consider the following bounded variable linear program:
Minimize 4x
1
+2x
2
+3x
3
= z
subject to x
1
+3x
2
+ x
3
=5
2x
1
− x
3
=1
0 ≤ x
1
≤ 1, 0 ≤ x
2
≤∞, 1 ≤ x
3
≤∞.
(a) Solve the problem by hand.
(b) Solve it using the DTZG Simplex Primal software option to verify your so-
lution.
3.24 Consider the following bounded 2-equation, 4-variable linear program:
Minimize 2x
1
+ x
2
+3x
3
+2x
4
= z
subject to x
1
+ x
2
+3x
3
− x
4
=7
x
1
+2x
2
+2x
3
+ x
4
=5
x
1
+ x
3
=3
0 ≤ x
1
≤ 2, 0 ≤ x
2
≤∞, 1 ≤ x
3
≤ 4, −4 ≤ x
4
≤−1.
(a) Solve the problem by hand.
(b) Solve it using the DTZG Simplex Primal software option to verify your so-
lution.
3.25 Apply Phase I of the Simplex Method by hand to show that the following linear
program is infeasible:
Maximize x
1
− 3x
2
+2x
3
= z
subject to x
1
+2x
2
+3x
3
≤ 5
2x
1
+3x
2
+2x
3
≤ 4
2 ≤ x
1
≤ 4, −∞ ≤ x
2
≤−1, 3 ≤ x
3
≤ 8.
3.26 Consider the following bounded variable linear program:
Minimize x
1
− 3x
2
+2x
3
= z
subject to x
1
+2x
2
+ x
3
≤ 2
2x
1
+ x
2
+4x
3
≤ 4
0 ≤ x
1
≤ 2, −∞ ≤ x
2
≤ 0, −2 ≤ x
3
≤ 2.
(a) Solve the problem by hand and show that it has a class of solutions that
cause the objective function to go to −∞.
(b) Solve it using the DTZG Simplex Primal software option to verify your so-
lution.
3.27 Consider the following 2-equation, 4-variable linear program.
Minimize 9x
1
+2x
2
+4x
3
+8x
4
= z
subject to 2x
1
+ x
2
+ x
3
+3x
4
≥ 20
3x
1
− x
2
+ x
3
− x
4
≥ 10
x
j
≥ 0,j=1,...,4.
3.7 PROBLEMS 107
(a) Solve the problem by hand or by the DTZG Simplex Primal software option.
(b) Show that the linear program has multiple optimal solutions.
(c) Find every basic feasible optimal solution.
3.28 Big-M Method. Suppose that we are trying to find the solution to the following
linear program:
Minimize −2x
1
− 3x
2
= z
subject to x
1
+2x
2
≤ 4
x
1
+ x
2
=3
x
1
≥ 0,x
2
≥ 0.
To initiate the Simplex Method we add a slack x
3
≥ 0 to the first constraint
and an artificial variable x
4
≥ 0 to the second constraint and then construct a
Phase I objective w = x
4
and minimize w. With the Big-M method we solve
the linear program in one pass by solving the problem:
Minimize −2x
1
− 3x
2
+0x
3
+ Mx
4
= z
subject to x
1
+2x
2
+ x
3
=4
x
1
+ x
2
+ x
4
=3
x
1
≥ 0,x
2
≥ 0,x
3
≥ 0,x
4
≥ 0,
where M is a large, prespecified positive number, and (x
3
,x
4
) are chosen to
form the starting basic feasible solution.
(a) Solve the above linear program with M = 100.
(b) Plot the steps of the algorithm in (x
1
,x
2
) space.
(c) Re-solve the original problem using the Phase I/Phase II approach.
(d) Plot the steps of the Phase I/Phase II algorithm in (x
1
,x
2
) space and
compare with the Big-M method.
3.29 Consider the following linear program:
Minimize x
1
+ x
2
= z
subject to 2x
1
+ x
2
=4
3x
1
+2x
2
≥ 5
x
1
≥ 0,x
2
≥ 0.
(a) Solve the above linear program by the Big-M method of Problem 3.28 with
M = 100.
(b) Plot the steps of the algorithm in (x
1
,x
2
) space.
3.30 Solve the following linear program by the Big-M method described in Prob-
lem 3.28
Minimize −x
1
− 2x
2
+3x
3
= z
subject to 2x
1
− x
2
+4x
3
=5
3x
1
+2x
2
− x
3
≤ 4
x
1
≥ 0,x
2
≥ 0,x
3
≥ 0.
108 THE SIMPLEX METHOD
3.31 Using the Big-M method described in Problem 3.28 show that the following
linear program is infeasible.
Minimize −2x
1
+3x
2
− 3x
3
= z
subject to 4x
1
+ x
2
+ x
3
=5
x
1
+ x
2
+ x
3
≥ 6
x
1
≥ 1
x
1
≥ 0,x
2
≥ 0,x
3
≥ 0.
3.32 Suppose that you apply the Big-M method to solve a linear program and ob-
tain an unbounded solution. Does this imply that the original problem has an
unbounded solution?
3.33 Suppose that the following LP problem is feasible:
Minimize c
T
x
subject to Ax ≥ b, A : m × n,
x ≥ 0.
Show that z
∗
→−∞if and only if there exists an ¯x = 0 such that ¯x ≥ 0,
A¯x ≥ 0, c
T
¯x<0.
3.34 Show that the system of equations
x
1
+ x
2
− x
3
+ x
4
=1
− 4x
2
+ x
3
+ x
5
=2
− 3x
2
+ x
3
+ x
6
=3
has an unbounded solution.
3.35 Given a linear program Ax = b, x ≥ 0, and c
T
x = min. Prove that you can
(a) add a set of the columns to produce new columns with new nonnegative
variables, and
(b) add or subtract equations
without affecting the optimal solution.
3.36 Show that a one-equation linear program can be solved in at most one iteration.
Specifically, show how to choose the entering variable. What are your conclu-
sions on different cases that might arise. You can assume that the problem is
given in canonical form with respect to the variable x
1
as follows:
Minimize c
2
x
2
+ c
3
x
3
+ ··· + c
n
x
n
= z
subject to x
1
+ a
2
x
2
+ a
3
x
3
+ ··· + a
n
x
n
= b,
where b>0.
3.37 Dantzig [1963]. Show, by changing units of any activity k whose ¯c
k
< 0, that x
k
can be chosen by the rule of ¯c
s
= min ¯c
j
to be the candidate to enter the next
basic set. Can you suggest another selection rule that might be better; does it
involve more work?
3.38 Consider an LP in canonical form (3.11).
(a) The standard Simplex Method determines the incoming column by selecting
the column that maximizes the decrease in the objective function per unit
increase of the incoming variable. In terms of the given canonical form,
indicate how the standard Simplex Method determines the pivot row and
pivot column.
3.7 PROBLEMS 109
(b) A pivoting method is scale-invariant if the selection of pivot row and col-
umn remains unchanged under any positive scaling of some (or all) of the
variables. A positive scaling of a variable x
j
is of the form x
j
= d
j
x
j
where
d
j
> 0. Is the standard Simplex Method scale-invariant? Justify your
answer.
(c) An alternative pivoting method is to choose the pivot row and column so as
to maximize the decrease in the objective function at each pivot step while
maintaining feasibility. In terms of the canonical form, describe how this
method determines the pivot row and pivot column.
(d) Is the method in (c) scale-invariant? Justify your answer.
3.39 Suppose that Phase I of the Simplex Method is applied to the system Ax = b,
x ≥ 0, and the procedure results in infeasibility. Show that the method has gen-
erated infeasibility multipliers. How can we derive the infeasibility multipliers
from the final tableau?
3.40 Suppose that for an LP in standard form, the system Ax = b has rank r<m,
i.e., it has m − r redundant equations.
(a) Show that there will be at least k = m − r artificial variables left in the
tableau at the end of Phase I.
(b) Show that if these k artificial variables are dropped from the tableau, then
the subsystem of equations associated with these artificial variables also has
m −r redundant equations and that if k = m −r, then the associated m−r
equations are vacuous.
3.41 T. Robacker in Dantzig [1963]. In some applications it often happens that
many variables initially in the basic set for some starting canonical form remain
until the final canonical form, so that their corresponding rows in the successive
tableaux of the Simplex Method, though continuously modified, have never
been used for pivoting. Devise a technique for generating rows only as needed
for pivoting and thereby avoiding needless work.
3.42 Bazarra, Jarvis, & Sherali [1990]. Consider the following two problems where
Ax = b, x ≥ 0 form a bounded region.
Minimize x
n
= z
subject to Ax = b, A : m × n,
x ≥ 0,
and
Maximize x
n
= z
subject to Ax = b, A : m × n,
x ≥ 0.
Let the optimal objective values of the two problems be x
n
and x
n
respectively.
If x
n
is a number in the interval [x
n
,x
n
], show that there exists a feasible point
whose nth component is equal to x
n
.
3.43 Suppose that one equation of a linear program in standard form has one positive
coefficient, say that of x
k
, while all remaining coefficients of the equation are
nonpositive and the constant b is positive. This implies that x
k
> 0 for any
solution, whatever the values of the remaining x
j
≥ 0. Pivot on any nonzero
term in x
k
to eliminate x
k
from the remaining equations and set aside the one
110 THE SIMPLEX METHOD
equation involving x
k
. Prove that the resulting linear program in one fewer
equation and one fewer variable can be solved to find the optimal solution of
the original problem.
3.44 If it is known in advance that a solution cannot be optimal unless it involves a
variable x
k
at positive value, show that this variable can be eliminated and the
reduced system with one fewer equation and variable solved in its place.
3.45 Suppose that we assume that x
1
, which has a nonzero coefficient in row 1, is in
the optimal solution of a linear program and eliminate it from rows 2,...,m and
from the objective function. Next we solve the linear program without row 1
to obtain an optimal solution. Then we substitute the values of x
2
,x
3
,... ,x
m
into the original row 1 to obtain the value of x
1
. Show that
(a) If x
1
≥ 0 then the solution x
1
,x
2
,... ,x
m
is optimal.
(b) If x
1
< 0 then its value must be zero in an optimal solution.
3.46 Show that if a linear program is feasible and the set of feasible solutions is
bounded, the linear program cannot have a homogeneous solution.
3.47 Suppose that the linear program
Minimize c
T
x
subject to Ax = b, A : m × n,
x ≥ 0
has a finite optimal solution. Show that if the right-hand side is changed from
b to some b
, the resulting linear program is either infeasible or has a finite
optimal feasible solution. Thus, by changing the right-hand side, we cannot
make a linear program, with a finite optimal solution, into a linear program
that is unbounded below.
3.48 Ph.D. Comprehensive Exam, June 13, 1968, at Stanford. In a Leontief substi-
tution model, there are m items that can be produced within the system. Let
the constant b
i
, i =1,...,m, denote the annual amount to be delivered by the
system to satisfy external demands.
Each process produces one and only one item j for j =1,...,m. Let the index
j
k
identify the kth alternative process for producing item j, and let the unknown
x
j
k
denote the number of units of item j produced annually by process k, where
k =1,...,n. In order to produce one unit of item j by process k, it requires a
ij
k
units of input of item i, and a cost of c
j
k
is incurred. The coefficients a
ij
k
≥ 0,
and for each j
k
pair
m
i=1
a
ij
k
< 1.
(a) Formulate the linear programming model as one of meeting the annual
delivery requirements at minimum cost.
(b) Suppose that b
i
> 0, for i =1,...,m. Prove that in any basic feasible
solution to the linear programming problem formulated in part (a), exactly
one of the k alternative processes for item j will be operated at positive
intensity.
(c) Suppose that b
i
≥ 0, for i =1,...,m. Prove that there exists a basic
feasible linear programming solution.
3.7 PROBLEMS 111
(d) Prove that if we have an optimal solution with shadow prices (multipliers)
π
o
i
for a particular set of delivery requirements b
o
i
, the same shadow prices
will also be optimal for any set of delivery requirements such that b
i
≥ 0.
3.49 Ph.D. Comprehensive Exam, November 1995, at Stanford. Consider the linear
program:
Minimize
n
j=1
c
j
x
j
= z
subject to
n
j=1
P
j
x
j
= b, P
j
∈
m
x
j
≥ 0, for j =1,...,n.
Suppose that z = z
∗
, x
j
= x
∗
j
for j =1,...,n is a nondegenerate optimal basic
feasible solution. A new activity vector is being considered for augmenting the
problem to
Minimize
n
j=1
c
j
x
j
+ c
n+1
x
n+1
= z
subject to
n
j=1
P
j
x
j
+ P
n+1
x
n+1
= b, P
j
∈
m
x
j
≥ 0, for j =1,...,n.
(a) How would you test whether the column n + 1 is a candidate for improving
the solution?
(b) Assume that column n + 1 passes the test and x
n+1
enters the basic set,
displacing x
r
. Let z =ˆz, x
j
=ˆx
j
for j =1,...,n+ 1 be the updated basic
feasible solution. Prove that it is a strict improvement, i.e., ˆz<z
∗
.
(c) Suppose the augmented problem is now iterated to a new optimal solution.
Prove that x
n+1
, once in, never leaves the basic set.