Reference no: EM131739568

Exercises 1

Question 1. Consider the linear programming problem: Find y₁ and y₂ to minimize y₁ + y₂ subject to the constraints,

y₁ + 2y₂ ≥ 3
y₁ + y₂ ≥ 5
y₂ ≥ 0.

Graph the constraint set and solve.

Question 2. Find x₁ and x₂ to maximize ax₁ + x₂ 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 x₁, x₂, x₃, x₄ to maximize x₁ + 2x₂ + 3x₃ + 4x₄ +5 subject to the constraints,

4x₁ + 3x₂ + 2x₃ + x₄ ≤ 10
x₁ - x₃ + 2x₄ = 2
x₁ + x₂ + x₃ + x₄ ≥ 1 ,

and

x₁ ≥ 0, x₃ ≥ 0, x₄ ≥ 0.

Exercises 2

Question 1. Find the dual to the following standard minimum problem. Find y₁, y₂ and y₃ to minimize y₁ + 2y₂ + y₃, subject to the constraints, y_i ≥ 0 for all i, and

y₁ - 2y₂ + y₃ ≥ 2
-y₁ + y₂ + y₃ ≥ 4
y₁ + y₃ ≥ 6
y₁ + y₂ + y₃ ≥ 2

Question 2. Consider the problem of Exercise 1. Show that (y₁, y₂, y₃) = (2/3, 0, 14/3) is optimal for this problem, and that (x₁, x₂, x₃, x4) = (0, 1/3, 2/3, 0) is optimal for the dual.

Question 3. Consider the problem: Maximize 3x₁ +2x₂+x₃ subject to x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0,

x₁ - x₂ + x₃ ≤ 4
x₁ + x₂ + 3x₃ ≤ 6
-x₁ + 2x₃ ≤ 3
x₁ + x₂ + x₃ ≤ 8.

(a) State the dual minimum problem.
(b) Suppose you suspect that the vector (x₁, x₂, x₃) = (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 y^TA = s^T,

for y₁ , y₂ , y₃ and y₄, 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 x₁ - 2x₂ - 3x₃ - x₄ subject to the constraints x_j ≥ 0 for all j and
x₁ - x₂ - 2x₃ - x₄ ≤ 4
x₁ + x₃ - 4x₄ ≤ 2
-2x₁ + x₂ + x₄ ≤ 1.

2. Minimize 3y₁ - y₂ + 2y₃ subject to the constraints y_i ≥ 0 for all i and
2y₁ - y₂ + y₃ ≥ -1
y₁ + 2y₃ ≥ 2
-7y₁ + 4y₂ - 6y₃ ≥ 1 .

3. Maximize -x1 - x2 + 2x3 subject to the constraints x_j ≥ 0 for all j and

-3x₁ + 3x₂ + x₃ ≤ 3
2x₁ - x₂ - 2x₃ ≤ 1
-x₁ + x₃ ≤ 1

4. Minimize 5y₁ - 2y₂ - y₃ subject to the constraints y_i ≥ 0 for all i and
-2y₁ + 3y₃ ≥ -1
2y₁ - y₂ + y₃ ≥ 1
3y₁ + 2y₂ - y₃ ≥ 0 .

5. Minimize -2y₂ + y₃ subject to the constraints y_i ≥ 0 for all i and
-4y₁ - 2y₂ ≥ -3
y₁ - 3y₂ + y₃ ≥ -5.

6. Maximize 3x₁ + 4x₂ + 5x₃ subject to the constraints x_j ≥ 0 for all j and
x₁ + 2x₂ + 2x₃ ≤ 1
-3x₁ + x₃ ≤ -1
-2x₁ - x₂ ≤ -1 .

Exercises 5.

1. (a) Transform the general maximum problem to standard form by (1) replacing each equality constraint, Σ_j a_ijx_j = b_i the two inequality constraints, Σ_ja_ijx_j ≤ b_i and Σ_j(-a_ij)x_j ≤ - b_i, and (2) replacing each unrestricted x'_j - x_j'', and x"_j are restricted to be nonnegative.

(b) Transform the general minimum problem to standard form by (1) replacing each equality Σ_i y_ija_ij = c_j by the two inequality constraints, ∑_iy_ia_ij ≥ c_j and ∑_iy_j(-a_ij) ≥ - cj and (2) replacing each unrestricted y_i 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,

y_i* = 0 for all i for which Σⁿ_j=1n a_ijx*_j < b_j

and

xj* = 0 for all j for which Σ^m_i=1n y_i*a_ij > c_j

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 y₁. Then pivot to interchange µ and x₂, and continue.

Exercises 6

Exercises.
1. (a) Set up the simplex tableau for Example 1.
(b) Pivot as follows.
1. Interchange x₁ and y₁ .
2. Interchange x₂ and y₂ .
3. Interchange x₃ and x₁ .
4. Interchange x₄ and x₂ .
5. Interchange y₁ and x₃ .
6. Interchange y₂ and x₄ .
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 b₁ = 12 , a₁₁ = 2 , a₁₂ = 3 and a₁₃ = 4 , N₁ = 2 , N₂ = 1 , and N₃ = 1 , and let the c_ij 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 y₁ and y₂ to minimize |y₁ + y₂ - 1| + |2y₁ - y₂ + 1| + |y₁ - y₂ - 2| subject to the constraints y₁ ≥ 0 and y₂ ≥ 0.

(a) Set up the simplex tableau of the associated linear program.

(b) Solve.

Question 3. Find a Chebyshev point (unnormalized) for the system

ψ₁(y₁, y₂) = y₁ + y₂ - 1

ψ₂(y₁, y₂) = 2y₁ - y₂ +1

ψ₃(y₁, y₂) = y₁ - y₂ - 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.