This file contains the exercises, hints, and solutions for Chapter 10 of the
book ”Introduction to the Design and Analysis of Algorithms,” 2nd edition, by
A. Levitin. The problems that might be challenging for at least some students
are marked by ; those that might be difficult for a majority of students are
marked by .
Exercises 10.1
1. Solve the following linear programming problems geometrically.
(a)
maximize 3x + y
subject to −x + y ≤ 1
2x + y ≤ 4
x ≥ 0,y≥ 0
(b)
maximize x +2y
subject to 4x ≥ y
y ≤ 3+x
x ≥ 0,y≥ 0
2. Consider the linear programming problem
minimize c
1
x + c
2
y
subject to x + y ≥ 4
x +3y ≥ 6
x ≥ 0,y≥ 0
where c
1
and c
2
aresomerealnumbersnotbothequaltozero.
(a) Give an example of the co efficient values c
1
and c
2
for which the
problem has a unique optimal solution.
(b) Give an example of the coefficient values c
1
and c
2
for which the
problem has infinitely many optimal solutions.
(c) Give an example of the coefficient values c
1
and c
2
for which the
problem does not ha ve an optimal solution.
3. Would the solution to problem (10.2) be different if its inequality con-
straints were strict, i.e., x + y<4 and x +3y<6, respectively?
4. Trace the simplex method on
(a) the problem of Exercise 1a.
(b) the problem of Exercise 1b.
5. Trace the simplex method on the problem of Example 1 in Section 6.6
1
