Exercises 1
Question 1. Consider the linear programming problem: Find y1 and y2 to minimize y1 + y2 subject to the constraints,
y1 + 2y2 ≥ 3
y1 + y2 ≥ 5
y2 ≥ 0.
Graph the constraint set and solve.
Question 2. Find x1 and x2 to maximize ax1 + x2 subject to the constraints in the numerical example of Figure 1. Find the value as a function of a .
Question 3. Write out the matrix A for the transportation problem in standard form.
Question 4. Put the following linear programming problem into standard form. Find x1, x2, x3, x4 to maximize x1 + 2x2 + 3x3 + 4x4 +5 subject to the constraints,
4x1 + 3x2 + 2x3 + x4 ≤ 10
x1 - x3 + 2x4 = 2
x1 + x2 + x3 + x4 ≥ 1 ,
and
x1 ≥ 0, x3 ≥ 0, x4 ≥ 0.
Exercises 2
Question 1. Find the dual to the following standard minimum problem. Find y1, y2 and y3 to minimize y1 + 2y2 + y3, subject to the constraints, yi ≥ 0 for all i, and
y1 - 2y2 + y3 ≥ 2
-y1 + y2 + y3 ≥ 4
y1 + y3 ≥ 6
y1 + y2 + y3 ≥ 2
Question 2. Consider the problem of Exercise 1. Show that (y1, y2, y3) = (2/3, 0, 14/3) is optimal for this problem, and that (x1, x2, x3, x4) = (0, 1/3, 2/3, 0) is optimal for the dual.
Question 3. Consider the problem: Maximize 3x1 +2x2+x3 subject to x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,
x1 - x2 + x3 ≤ 4
x1 + x2 + 3x3 ≤ 6
-x1 + 2x3 ≤ 3
x1 + x2 + x3 ≤ 8.
(a) State the dual minimum problem.
(b) Suppose you suspect that the vector (x1, x2, x3) = (0, 6, 0) is optimal for the maximum problem. Use the Equilibrium Theorem to solve the dual problem, and then show that your suspicion is correct.
Question 4. (a) State the dual to the transportation problem.
(b) Give an interpretation to the dual of the transportation problem.
Exercises 3
Solve the system of equations yTA = sT,
for y1 , y2 , y3 and y4, by pivoting, in order, about the entries
(1) first row, first column (circled)
(2) second row, third column (the pivot is 1)
(3) fourth row, second column (the pivot turns out to be 1)
(4) third row, fourth column (the pivot turns out to be 3).
Rearrange rows and columns to find A-1 , and check that the product with A gives the identity matrix.
Exercises 4
For the linear programming problems below, state the dual problem, solve by the simplex (or dual simplex) method, and state the solutions to both problems.
1. Maximize x1 - 2x2 - 3x3 - x4 subject to the constraints xj ≥ 0 for all j and
x1 - x2 - 2x3 - x4 ≤ 4
x1 + x3 - 4x4 ≤ 2
-2x1 + x2 + x4 ≤ 1.
2. Minimize 3y1 - y2 + 2y3 subject to the constraints yi ≥ 0 for all i and
2y1 - y2 + y3 ≥ -1
y1 + 2y3 ≥ 2
-7y1 + 4y2 - 6y3 ≥ 1 .
3. Maximize -x1 - x2 + 2x3 subject to the constraints xj ≥ 0 for all j and
-3x1 + 3x2 + x3 ≤ 3
2x1 - x2 - 2x3 ≤ 1
-x1 + x3 ≤ 1
4. Minimize 5y1 - 2y2 - y3 subject to the constraints yi ≥ 0 for all i and
-2y1 + 3y3 ≥ -1
2y1 - y2 + y3 ≥ 1
3y1 + 2y2 - y3 ≥ 0 .
5. Minimize -2y2 + y3 subject to the constraints yi ≥ 0 for all i and
-4y1 - 2y2 ≥ -3
y1 - 3y2 + y3 ≥ -5.
6. Maximize 3x1 + 4x2 + 5x3 subject to the constraints xj ≥ 0 for all j and
x1 + 2x2 + 2x3 ≤ 1
-3x1 + x3 ≤ -1
-2x1 - x2 ≤ -1 .
Exercises 5.
1. (a) Transform the general maximum problem to standard form by (1) replacing each equality constraint, Σj aijxj = bi the two inequality constraints, Σjaijxj ≤ bi and Σj(-aij)xj ≤ - bi, and (2) replacing each unrestricted x'j - xj'', and x"j are restricted to be nonnegative.
(b) Transform the general minimum problem to standard form by (1) replacing each equality Σi yijaij = cj by the two inequality constraints, ∑iyiaij ≥ cj and ∑iyj(-aij) ≥ - cj and (2) replacing each unrestricted yi by y'i -y''i, where y''i are restricted to be nonnegative.
(c) Show that the standard programs (a) and (b) are duals.
2. Let x* and y* be feasible vectors for a general maximum problem and its dual respectively. Assuming the Duality Theorem for the general problems, show that x* and y* are optimal if, and only if,
yi* = 0 for all i for which Σnj=1n aijx*j < bj
and
xj* = 0 for all j for which Σmi=1n yi*aij > cj
3. (a) State the dual for the problem of Example 1.
(b) Find the solution of the dual of the problem of Example 1.
4. Solve the game with matrix, change 
. First pivot to interchange λ and y1. Then pivot to interchange µ and x2, and continue.
Exercises 6
Exercises.
1. (a) Set up the simplex tableau for Example 1.
(b) Pivot as follows.
1. Interchange x1 and y1 .
2. Interchange x2 and y2 .
3. Interchange x3 and x1 .
4. Interchange x4 and x2 .
5. Interchange y1 and x3 .
6. Interchange y2 and x4 .
Now, note you are back where you started.
2. Solve the problem of Example 1 by pivoting according to the modi?ed simplex rule.
3. Solve the problem of Example 1 by pivoting according to the smallest subscript rule.
Exercises 7
Question 1. In the general production planning problem, suppose there are 3 activities, 1 resource and 3 parts. Let b1 = 12 , a11 = 2 , a12 = 3 and a13 = 4 , N1 = 2 , N2 = 1 , and N3 = 1 , and let the cij be as given in the matrix below.
(a) Set up the simplex tableau of the associated linear program.
(b) Solve.
Question 2. Consider the problem of finding y1 and y2 to minimize |y1 + y2 - 1| + |2y1 - y2 + 1| + |y1 - y2 - 2| subject to the constraints y1 ≥ 0 and y2 ≥ 0.
(a) Set up the simplex tableau of the associated linear program.
(b) Solve.
Question 3. Find a Chebyshev point (unnormalized) for the system
ψ1(y1, y2) = y1 + y2 - 1
ψ2(y1, y2) = 2y1 - y2 +1
ψ3(y1, y2) = y1 - y2 - 2
by (a) setting up the associated linear program, and (b) solving.
Question 4. There are two activities and two resources. There are 2 units of R1 and 3 units of R2 available. Activity A1 operated at unit intensity requires 1 unit of R1 and 3 units of R2 , yields a return of 2, and uses up 1 time unit. Activity A2 operated at unit intensity requires 3 units of R1 and 2 units of R2 , yields a return of 3, and uses up 2 time units. It requires 1 time unit to get the whole procedure started at no return. (a) Set up the simplex tableau of the associated linear program. (b) Find the intensities that maximize the rate of return. (Ans. A1 at intensity 5/7, A2 at intensity 3/7, maximal rate = 19/18.)
Exercises 8
1. Solve the transportation problems with the following arrays.
