For each problem in Exercise 2.5.5, sketch the feasible region and label the extreme points traversed by the Simplex Algorithm in order.
7.
Solve the following using the Simplex Algorithm.
(a)
A firm produces a rare blend of scotch whiskey. The blend must contain at least 42% alcohol, at least 25% Highland blend, and no more than 15% malt. Three distillery products can be combined for the blend.
Product A costs $12 a gallon, is 46% alcohol, 30% Highland blend and 10% malt. Product B costs $8 a gallon, is 40% alcohol, 20% Highland blend and 5% malt. Product C costs $14 a gallon, is 45% alcohol, 25% Highland blend and 2% malt.
How much of each product should be used to produce 100 gallons of blend at minimal cost?
(b)
A company produces three types of tires for the SUV market. In their manufacture, the tires are processed on two machines, a molder and a capper. Tire type A takes 8 hours in the molder, 4 on the capper and sells for $45. Tire type B takes 10 hours in the molder, 7 on the capper and sells for $50. Tire type C takes 5 hours in the molder, 6 on the capper and sells for $40. At least 75 of each type of tire needs to be made each week to fulfill current contracts. If 3000 hours are available each week for molders and 2700 for cappers, how many of each type of tire should be made each week to maximize revenue?
8.
The canonical optimization problem below potentially cycles (due to H.W. Kuhn.). Solve the problem by using the Simplex Algorithm with Bland anti-cycling rules.
\(x_1\)
\(x_2\)
\(x_3\)
\(x_4\)
\(-1\)
\(-2\)
\(-9\)
\(1\)
\(9\)
\(0\)
\(=-t_1\)
\(1/3\)
\(1\)
\(-1/3\)
\(-2\)
\(0\)
\(=-t_2\)
\(2\)
\(3\)
\(-1\)
\(-12\)
\(2\)
\(=-t_3\)
\(2\)
\(3\)
\(-1\)
\(-12\)
\(0\)
\(=f\)
9.
Consider a tableau whose basic solution is feasible and optimal. Suppose each \(b_i > 0\text{.}\) Prove that this is the unique optimal solution if and only if each \(c_j < 0\text{.}\)
10.
The following have multiple optimal solutions, use the Simplex Algorithm and then pivots to classify all the optimal solutions.
(a)
\(x_1\)
\(x_2\)
\(x_3\)
\(x_4\)
\(-1\)
\(0\)
\(1\)
\(1\)
\(-1\)
\(3\)
\(=-t_1\)
\(1\)
\(1\)
\(1\)
\(-1\)
\(3\)
\(=-t_2\)
\(1\)
\(2\)
\(2\)
\(-4\)
\(0\)
\(=f\)
(b)
\(y_1\)
\(-1\)
\(-1\)
\(-1\)
\(y_2\)
\(-1\)
\(1\)
\(-1\)
\(-1\)
\(-2\)
\(1\)
\(0\)
\(=s_1\)
\(=s_2\)
\(=g\)
11.
Consider a square tableau:
\(x_1\)
\(x_2\)
\(\cdots\)
\(x_n\)
\(-1\)
\(a_{11}\)
\(a_{12}\)
\(\cdots\)
\(a_{1n}\)
\(0\)
\(=-t_1\)
\(a_{21}\)
\(a_{22}\)
\(\cdots\)
\(a_{2n}\)
\(0\)
\(=-t_2\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{n1}\)
\(a_{n2}\)
\(\cdots\)
\(a_{nn}\)
\(0\)
\(=-t_n\)
\(0\)
\(0\)
\(\cdots\)
\(0\)
\(0\)
Suppose we perform pivots so we achieve a tableau of the form:
\(t_1\)
\(t_2\)
\(\cdots\)
\(t_n\)
\(-1\)
\(a'_{11}\)
\(a'_{12}\)
\(\cdots\)
\(a'_{1n}\)
\(0\)
\(=-x_1\)
\(a'_{21}\)
\(a'_{22}\)
\(\cdots\)
\(a'_{2n}\)
\(0\)
\(=-x_2\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a'_{n1}\)
\(a'_{n2}\)
\(\cdots\)
\(a'_{nn}\)
\(0\)
\(=-x_n\)
\(0\)
\(0\)
\(\cdots\)
\(0\)
\(0\)
Let \(A=[a_{ij}]_{n\times n}\) and \(A'=[a'_{ij}]_{n\times n}\text{.}\) For each of the following matrices \(A\) perform appropriate pivots to achieve \(A'\) and confirm \(A'=A^{-1}\text{.}\)
Explain why in Exercise 2.5.11 that \(A'=A^{-1}\) in general.
13.
(a)
Find neccesary and sufficient conditions for the minimization tableau
\(y_1\)
\(a_{11}\)
\(\cdots\)
\(a_{1m}\)
\(b_1\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(y_n\)
\(a_{n1}\)
\(\cdots\)
\(a_{nm}\)
\(b_n\)
\(-1\)
\(c_1\)
\(\cdots\)
\(c_m\)
\(d\)
\(=s_1\)
\(\cdots\)
\(=s_m\)
\(=g\)
to have a feasible basic solution.
(b)
If a minimization tableau as depicted above has a feasible basic solution, must it also have a feasible basic maximum solution? Prove or find a counterexample.
(c)
Find neccesary and sufficient conditions for
\(x_1\)
\(\cdots\)
\(x_m\)
\(-1\)
\(y_1\)
\(a_{11}\)
\(\cdots\)
\(a_{1m}\)
\(b_1\)
\(=-t_1\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(y_n\)
\(a_{n1}\)
\(\cdots\)
\(a_{nm}\)
\(b_n\)
\(=-t_n\)
\(-1\)
\(c_1\)
\(\cdots\)
\(c_m\)
\(d\)
\(=f\)
\(=s_1\)
\(\cdots\)
\(=s_m\)
\(=g\)
to encode feasible basic solutions for both it’s maximization and minimization problems.
14.
Prove that each tableau always encodes a unique basic solution by first showing that the default starting basic solution is unique, and then proving that each pivot preserves the uniqueness of the basic solution.
Hint.
Note that each basic solution is the intersection of \(m\) hyperplanes. What would it take for this to be empty or contain multiple points? Think in terms of linear (in)dependence and solving linear systems.
