Reference no: EM131909866

EXERCISES

Question 1. Given:

x₁ + 2x₄ = 8,

x₂ + 3x₄ = 6,

x₃ + 8x₄ = 24,

-z + 10x₄ = -32,

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

a) What is the optimal solution of this problem?

b) Change the coefficient of x4 in the z-equation to -3. What is the optimal solution now?

c) Change the signs on all x4 coefficients to be negative. What is the optimal solution now?

Question 2. Consider the linear program:

Maximize z = 9x₂ + x₃ - 2x₅ - x₆,

subject to:

5x₂ + 50x₃ + x₄ + x₅ = 10,

x₁ - 15x₂ + 2x₃ = 2,

x₂ + x₃ + x₅ + x₆ = 6,
x_j ≥ 0  ( j = 1, 2, . . . , 6).

a) Find an initial basic feasible solution, specify values of the decision variables, and tell which are basic.

b) Transform the system of equations to the canonical form for carrying out the simplex routine.

c) Is your initial basic feasible solution optimal? Why?

d) How would you select a column in which to pivot in carrying out the simplex algorithm?

e) Having chosen a pivot column, now select a row in which to pivot and describe the selection rule. How does this rule guarantee that the new basic solution is feasible? Is it possible that no row meets the criterion of your rule? If this happens, what does this indicate about the original problem?

f) Without carrying out the pivot operation, compute the new basic feasible solution.

g) Perform the pivot operation indicated by (d) and (e) and check your answer to (f). Substitute your basic feasible solution in the original equations as an additional check.

h) Is your solution optimal now? Why?

Question 3. a) Reduce the following system to canonical form. Identify slack, surplus, and artificial variables.

-2x₁ + x₂ ≤ 4 (1)

3x₁ + 4x₂ ≥ 2 (2)

5x₁ + 9x₂ = 8 (3)

x₁ + x₂ ≥ 0 (4)

2x₁ + x₂ ≥ -3 (5)

-3x₁ - x₂ ≤ -2 (6)

3x₁ + 2x₂ ≤ 10 (7)

x₁ ≥ 0, x₂ ≥ 0.

b) Formulate phase I objective functions for the following systems with x₁ ≥ 0 and x₂ ≥ 0:

i) expressions 2 and 3 above.

ii) expressions 1 and 7 above.

iii) expressions 4 and 5 above.

Question 4. Consider the linear program

Maximize z = x₁,

subject to:

-x₁ + x₂ ≤ 2,
x₁ + x₂ ≤ 8,
-x₁ + x₂ ≥ -4,
x₁ ≥ 0, x₂ ≥ 0.

a) State the above in canonical form.

b) Solve by the simplex method.

c) Solve geometrically and also trace the simplex procedure steps graphically.

d) Suppose that the objective function is changed to z = x₁ + cx₂. Graphically determine the values of c for which the solution found in parts (b) and (c) remains optimal.

e) Graphically determine the shadow price corresponding to the third constraint.

Question 5. The bartender of your local pub has asked you to assist him in finding the combination of mixed drinks that will maximize his revenue. He has the following bottles available:

1 quart (32 oz.) Old Cambridge (a fine whiskey-cost $8/quart) 1 quart Joy Juice (another fine whiskey-cost $10/quart)
1 quart Ma's Wicked Vermouth ($10/quart) 2 quarts Gil-boy's Gin ($6/quart)
Since he is new to the business, his knowledge is limited to the following drinks:

Whiskey Sour	2 oz. whiskey	Price $1
Manhattan	2 oz. whiskey 1 oz. vermouth	$2
Martini	2 oz. gin 1 oz. vermouth	$2
Pub Special	2 oz. gin 2 oz. whiskey	$3

Use the simplex method to maximize the bar's profit. (Is the cost of the liquor relevant in this formulation?)

Question 6. A company makes three lines of tires. Its four-ply biased tires produce $6 in profit per tire, its fiberglass belted line $4 a tire, and its radials $8 a tire. Each type of tire passes through three manufacturing stages as a part of the entire production process.

Each of the three process centers has the following hours of available production time per day:

	Process	Hours
1	Molding	12
2	Curing	9
3	Assembly	16

The time required in each process to produce one hundred tires of each line is as follows:

Tire	Hours per 100 units
	Molding	Curing	Assembly
Four-ply	2	3	2
Fiberglass	2	2	1
Radial	2	1	3

Determine the optimum product mix for each day's production, assuming all tires are sold.

Question 7. An electronics firm manufactures printed circuit boards and specialized electronics devices. Final assembly oper- ations are completed by a small group of trained workers who labor simultaneously on the products. Because of limited space available in the plant, no more then ten assemblers can be employed. The standard operating budget in this functional department allows a maximum of $9000 per month as salaries for the workers.

The existing wage structure in the community requires that workers with two or more years of experience receive $1000 per month, while recent trade-school graduates will work for only $800. Previous studies have shown that experienced assemblers produce $2000 in ‘‘value added" per month while new-hires add only $1800. In order to maximize the value added by the group, how many persons from each group should be employed? Solve graphically and by the simplex method.

Question 8. The processing division of the Sunrise Breakfast Company must produce one ton (2000 pounds) of breakfast flakes per day to meet the demand for its Sugar Sweets cereal. Cost per pound of the three ingredients is:

Ingredient A $4 per pound

Ingredient B $3 per pound

Ingredient C $2 per pound

Government regulations require that the mix contain at least 10% ingredient A and 20% ingredient B. Use of more than 800 pounds per ton of ingredient C produces an unacceptable taste.

Determine the minimum-cost mixture that satisfies the daily demand for Sugar Sweets. Can the bounded- variable simplex method be used to solve this problem?

Question 9. Solve the following problem using the two phases of the simplex method: Maximize z = 2x₁ + x₂ + x₃,

subject to:

2x₁ + 3x₂ - x₃ ≤ 9,
2x₂ + x₃ ≥ 4,
x₁ + x₃ = 6,
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0.

Is the optimal solution unique?

Question 10. Consider the linear program:

Maximize z = -3x₁ + 6x₂,

subject to:

5x₁ + 7x₂ ≤ 35,
-x₁ + 2x₂ ≤ 2,
x₁ ≥ 0, x₂ ≥ 0.

a) Solve this problem by the simplex method. Are there alternative optimal solutions? How can this be determined at the final simplex iteration?

b) Solve the problem graphically to verify your answer to part (a).

Question 11. Solve the following problem using the simplex method:

Minimize z = x₁ - 2x₂ - 4x₃ + 2x₄,

subject to:

x₁ - 2x₃ ≤ 4,
x₂ - x₄ ≤ 8,
-2x₁ + x₂ + 8x₃ + x₄ ≤ 12,
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0.

Question 12.

a) Set up a linear program that will determine a feasible solution to the following system of equations and inequalities if one exists. Do not solve the linear program.

x₁ - 6x₂ + x₃ - x₄ = 5,

-2x₂ + 2x₃ - 3x₄ ≥ 3,

3x₁ - 2x₃ + 4x₄ = -1,

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

b) Formulate a phase I linear program to find a feasible solution to the system:

3x₁ + 2x₂ - x₃ ≤ -3,
-x₁ - x₂ + 2x₃ ≤ -1,
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0.

Show, from the phase I objective function, that the system contains no feasible solution (no pivoting calculations are required).

Question 13. The tableau given below corresponds to a maximization problem in decision variables x_j ≥ 0 ( j = 1, 2, . . . , 5):

Basic variables	Current values	x1	x2	x3	x4	x5
x3 x4 x5	4 1 b	-1 a2 a3	a1 -4 3	1	1	1
(-z)	-10	c	-2

State conditions on all five unknowns a₁, a₂, a₃, b, and c, such that the following statements are true.
a) The current solution is optimal. There are multiple optimal solutions.
b) The problem is unbounded.
c) The problem is infeasible.
d) The current solution is not optimal (assume that b 0). Indicate the variable that enters the basis, the variable that leaves the basis, and what the total change in profit would be for one iteration of the simplex method for all values of the unknowns that are not optimal.

Question 14. Consider the linear program:

Maximize z = αx₁ + 2x₂ + x₃ - 4x₄,

subject to:

x₁ + x₂ - x₄ = 4 + 2O (1)
2x₁ - x₂ + 3x₃ - 2x₄ = 5 + 7O (2)
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0,

where α and Δ are viewed as parameters.

a) Form two new constraints as (1') = (1) + (2) and (2') = 2(1) + (2). Solve for x₁ and x₂ from (1') and (2'), and substitute their values in the objective function. Use these transformations to express the problem in canonical form with x₁ and x₂ as basic variables.

b) Assume Δ = 0 (constant). For what values of α are x₁ and x₂ optimal basic variables in the problem?

c) Assume α = 3. For what values of Δ do x₁ and x₂ form an optimal basic feasible solution?

Question 15.

Let

(-ω) + d₁x₁ + d₂x₂ + ...... + d_mx_m = 0   (∗)

be the phase I objective function when phase I terminates for maximizing ω. Discuss the following two procedures for making the phase I to II transition when an artificial variable remains in the basis at value zero. Show, using either procedure, that every basic solution determined during phase II will be feasible for the original problem formulation.

a) Multiply each coefficient in (*) by -1. Initiate phase II with the original objective function, but maintain (*) in the tableau as a new constraint with (ω) as the basic variable.

b) Eliminate (*) from the tableau and at the same time eliminate from the problem any variable x_j with d_j < 0. Any artificial variable in the optimal phase I basis is now treated as though it were a variable from the original problem.

Question 16. In our discussion of reduction to canonical form, we have replaced variables unconstrained in sign by the difference between two nonnegative variables. This exercise considers an alternative transformation that does not introduce as many new variables, and also a simplex-like procedure for treating free variables directly without any substitutions. For concreteness, suppose that y₁, y₂, and y₃ are the only unconstrained variables in a linear program.

a) Substitute for y₁, y₂, and y₃ in the model by:
y₁ = x₁ - x₀,

y₂ = x₂ - x₀,

y₃ = x₃ - x₀,

with x₀ ≥ 0, x₁ ≥ 0, x₂ ≥ 0, and x₃ ≥ 0. Show that the models are equivalent before and after these substitutions.

b) Apply the simplex method directly with y₁, y₂, and y₃. When are these variables introduced into the basis
at positive levels? At negative levels? If y₁ is basic, will it ever be removed from the basis? Is the equation containing y₁ as a basic variable used in the ratio test? Would the simplex method be altered in any other way?

Question 17. Apply the phase I simplex method to find a feasible solution to the problem:

x₁ - 2x₂ + x₃ = 2,

-x₁ - 3x₂ + x₃ = 1,

2x₁ - 3x₂ + 4x₃ = 7,

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0.
Does the termination of phase I show that the system contains a redundant equation? How?

Question 18. Frequently, linear programs are formulated with interval constraints of the form:

5 ≤ 6x₁ - x₂ + 3x₃ ≤ 8.

a) Show that this constraint is equivalent to the constraints

6x₁ - x₂ + 3x₃ + x₄ = 8,
0 ≤ x₄ ≤ 3.

b) Indicate how the general interval linear program

Maximize z = Σⁿ_j=1 c_jx_j,

subject to:

b'_ij ≤ j = Σⁿ_j=1 a_ijx_j ≤ b_i (i = 1, 2, . . . , m),

x_j ≥ 0 ( j = 1, 2, . . . , n),

can be formulated as a bounded-variable linear program with m equality constraints.

Question 19. a) What is the solution to the linear-programming problem:

Maximize z = c₁x₁ + c₂x₂ + ... + c_n x_n,

subject to:

a₁x₁ + a₂x₂ + ... + a_n x_n ≤ b,

0 ≤ x _j ≤ u _j ( j = 1, 2, . . . , n),

with bounded variables and one additional constraint? Assume that the constants c_j , a_j , and u_j for j
1, 2, . . . , n, and b are all positive and that the problem has been formulated so that:

c₁/a₁ ≥ c₂/a₂ ≥ .... ≥ c_n/a_n

b) What will be the steps of the simplex method for bounded variables when applied to this problem (in what order do the variables enter and leave the basis)?

Question 20. a) Graphically determine the steps of the simplex method for the problem:

Maximize 8x₁ + 6x₂,

subject to:

3x₁ + 2x₂ ≤ 28,
5x₁ + 2x₂ ≤ 42,
x₁ ≤ 8,
x₂ ≤ 8,
x₁ ≥ 0, x₂ ≥ 0.

Indicate on the sketch the basic variables at each iteration of the simplex algorithm in terms of the given variables and the slack variables for the four less-than-or-equal-to constraints.

b) Suppose that the bounded-variable simplex method is applied to this problem. Specify how the iterations in the solution to part (a) correspond to the bounded-variable simplex method. Which variables from x₁, x₂, and the slack variable for the first two constraints, are basic at each iteration? Which nonbasic variables are at their upper bounds?

c) Solve the problem algebraically, using the simplex algorithm for bounded variables.