EXERCISES
Question 1. Given:
x1 + 2x4 = 8,
x2 + 3x4 = 6,
x3 + 8x4 = 24,
-z + 10x4 = -32,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 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 = 9x2 + x3 - 2x5 - x6,
subject to:
5x2 + 50x3 + x4 + x5 = 10,
x1 - 15x2 + 2x3 = 2,
x2 + x3 + x5 + x6 = 6,
xj ≥ 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.
-2x1 + x2 ≤ 4 (1)
3x1 + 4x2 ≥ 2 (2)
5x1 + 9x2 = 8 (3)
x1 + x2 ≥ 0 (4)
2x1 + x2 ≥ -3 (5)
-3x1 - x2 ≤ -2 (6)
3x1 + 2x2 ≤ 10 (7)
x1 ≥ 0, x2 ≥ 0.
b) Formulate phase I objective functions for the following systems with x1 ≥ 0 and x2 ≥ 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 = x1,
subject to:
-x1 + x2 ≤ 2,
x1 + x2 ≤ 8,
-x1 + x2 ≥ -4,
x1 ≥ 0, x2 ≥ 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 = x1 + cx2. 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 = 2x1 + x2 + x3,
subject to:
2x1 + 3x2 - x3 ≤ 9,
2x2 + x3 ≥ 4,
x1 + x3 = 6,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Is the optimal solution unique?
Question 10. Consider the linear program:
Maximize z = -3x1 + 6x2,
subject to:
5x1 + 7x2 ≤ 35,
-x1 + 2x2 ≤ 2,
x1 ≥ 0, x2 ≥ 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 = x1 - 2x2 - 4x3 + 2x4,
subject to:
x1 - 2x3 ≤ 4,
x2 - x4 ≤ 8,
-2x1 + x2 + 8x3 + x4 ≤ 12,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 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.
x1 - 6x2 + x3 - x4 = 5,
-2x2 + 2x3 - 3x4 ≥ 3,
3x1 - 2x3 + 4x4 = -1,
x1 ≥ 0, x3 ≥ 0, x4 ≥ 0.
b) Formulate a phase I linear program to find a feasible solution to the system:
3x1 + 2x2 - x3 ≤ -3,
-x1 - x2 + 2x3 ≤ -1,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 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 xj ≥ 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 a1, a2, a3, 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 = αx1 + 2x2 + x3 - 4x4,
subject to:
x1 + x2 - x4 = 4 + 2O (1)
2x1 - x2 + 3x3 - 2x4 = 5 + 7O (2)
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,
where α and Δ are viewed as parameters.
a) Form two new constraints as (1') = (1) + (2) and (2') = 2(1) + (2). Solve for x1 and x2 from (1') and (2'), and substitute their values in the objective function. Use these transformations to express the problem in canonical form with x1 and x2 as basic variables.
b) Assume Δ = 0 (constant). For what values of α are x1 and x2 optimal basic variables in the problem?
c) Assume α = 3. For what values of Δ do x1 and x2 form an optimal basic feasible solution?
Question 15.
Let
(-ω) + d1x1 + d2x2 + ...... + dmxm = 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 xj with dj < 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 y1, y2, and y3 are the only unconstrained variables in a linear program.
a) Substitute for y1, y2, and y3 in the model by:
y1 = x1 - x0,
y2 = x2 - x0,
y3 = x3 - x0,
with x0 ≥ 0, x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0. Show that the models are equivalent before and after these substitutions.
b) Apply the simplex method directly with y1, y2, and y3. When are these variables introduced into the basis
at positive levels? At negative levels? If y1 is basic, will it ever be removed from the basis? Is the equation containing y1 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:
x1 - 2x2 + x3 = 2,
-x1 - 3x2 + x3 = 1,
2x1 - 3x2 + 4x3 = 7,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 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 ≤ 6x1 - x2 + 3x3 ≤ 8.
a) Show that this constraint is equivalent to the constraints
6x1 - x2 + 3x3 + x4 = 8,
0 ≤ x4 ≤ 3.
b) Indicate how the general interval linear program
Maximize z = Σnj=1 cjxj,
subject to:
b'ij ≤ j = Σnj=1 aijxj ≤ bi (i = 1, 2, . . . , m),
xj ≥ 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 = c1x1 + c2x2 + ... + cn xn,
subject to:
a1x1 + a2x2 + ... + an xn ≤ b,
0 ≤ x j ≤ u j ( j = 1, 2, . . . , n),
with bounded variables and one additional constraint? Assume that the constants cj , aj , and uj for j
1, 2, . . . , n, and b are all positive and that the problem has been formulated so that:
c1/a1 ≥ c2/a2 ≥ .... ≥ cn/an
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 8x1 + 6x2,
subject to:
3x1 + 2x2 ≤ 28,
5x1 + 2x2 ≤ 42,
x1 ≤ 8,
x2 ≤ 8,
x1 ≥ 0, x2 ≥ 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 x1, x2, 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.