Problems for Chapter 4

Section 4.5 Problems for Chapter 4

The simplex pivoter may be found here:

Hint.

Exercises Exercises

1.

For each problem in Exercise 2.6.5, if the problem has an optimal solution, identify the bounding hyperplanes that the solution lies on, then state the normal vector for the objective plane in terms of the normal vectors of the bounding hyperplanes.

🔗

2.

Suppose that a company is painting figurines, 4 colors $C_1, C_2, C_3, C_4\text{.}$ The colors are mixed from red, green and blue paint.

🔗

$C_1$ takes 2 oz of red, 2 oz green and 1 oz blue. $C_2$ takes 3 oz of red, 1 oz green and 1 oz blue. $C_3$ takes 1 oz of red, 2 oz green and 2 oz blue. $C_4$ takes 1 oz of red and 4 oz blue.

🔗

Figurines with color $C_1, C_3$ sell for $20, $C_2$ colored figures sell for $25 dollars and $C_4$ colored figurines sell for $30. The company has many figurines to paint and 100 oz each of red, green and blue paint. How many of each colored figurine should be painted to maximize revenue?

🔗

(a)

Solve the above canonical maximization problem and restate the objective function in terms of the $t_i\text{.}$

🔗

(b)

If we had 110 oz red, 100 oz green, and 100 oz blue paint, without resolving the problem, what would the optimal revenue be?

🔗

(c)

If we had 95 oz red, 100 oz green, and 100 oz blue paint, without resolving the problem, what would the optimal revenue be?

🔗

(d)

If we had 100 oz red, 110 oz green, and 100 oz blue paint, without resolving the problem, what would the optimal revenue be?

🔗

(e)

If we had 100 oz red, 100 oz green, and 95 oz blue paint, without resolving the problem, what would the optimal revenue be?

🔗

3.

An office worker is eating in their work cafeteria and they are recently put on a low cholesterol diet. Their usual choices are pasta, fried tofu and chicken sandwiches. The pasta has 6 g of protein, 60 g of carbohydrates, 2 mg of vitamin C, and 60 mg of cholesterol. The fried tofu has 10 g of protein, 40 g of carbohydrates, 2 mg of vitamin C, and 50 mg of cholesterol. The chicken sandwich has 18 g of protein, 40 g of carbohydrates, 2 mg of vitamin C, and 60 mg of cholesterol.

🔗

They need 200 g of protein, 960 g of carbohydrates and 40 mg of vitamin C in a month, and wishes to minimize cholesterol. How many of each meal should they eat?

🔗

(a)

Find the optimal solution to the above problem.

🔗

(b)

Suppose they needed to increase their protein consumption to 220 g a month. Without recomputing the solution, what would the new minimum cholesterol be?

🔗

(c)

Suppose instead that they needed to decrease their carbohydrate consumption to 190 g a month. Without recomputing the solution, what would the new minimum cholesterol be?

🔗

(d)

Suppose instead that they needed to increase their vitamin C consumption to 45 g a month. Without recomputing the solution, what would the new minimum cholesterol be?

🔗

4.

Suppose the maximum value of the objective function $f(\x)=c_1x_1+\cdots +c_{m+n}x_{m+n}$ of a linear optimization problem is attained at the point $\x^*$ with the first $m$ variables as decision variables. Determine if the following are TRUE or FALSE:

🔗

If we increase $x_i, 1\leq i\leq m\text{,}$ the value of the objective function is still $f(\x^*)\text{.}$
🔗

🔗
If we increase $x_i, m+1\leq i\leq m+n\text{,}$ the value of the objective function is still $f(\x^*)\text{.}$
🔗

🔗

🔗

5.

Consider Corollary 9.4.8.

🔗

(a)

Prove that if the primal problem is infeasible, and the dual problem is feasible, then the dual problem is unbounded below. (Use Corollary 9.4.8.)

🔗

(b)

Prove that if the dual problem is infeasible, and the primal problem is feasible, then the primal problem is unbounded above. (Use $\textbf{(a)}\text{.}$)

🔗

(c)

Prove that if the primal (dual) problem is feasible and unbounded above (below), then the dual (primal) problem is infeasible.

🔗

(d)

Find a primal-dual linear problem where both the primal and dual problems are infeasible.

🔗

6.

Consider the canonical maximization linear optimization problem below:

🔗

\begin{align*} \textbf{Maximize: } f(x,y) \amp = x+y\\ \textbf{subject to: } x+2y\amp \leq 4\\ 3x+y\amp \leq 6\\ x,y\amp \geq 0. \end{align*}

🔗

(a)

State the dual canonical minimization linear optimization problem.

🔗

(b)

Sketch the constraint sets for both problems above.

🔗

(c)

Solve both problems above by applying the simplex algorithm to a dual tableau. Indicate the movement in both constraint set diagrams exhibited by the basic solutions of successive tableaus.

🔗

(d)

Is complementary slackness exhibited in the solutions above? Why or why not?

🔗

7.

For each problem in Exercise 2.6.5, state the dual problem and find its solution.

🔗

8.

For each of the following, solve the canonical dual minimization problem. If there are infinitely many solutions, classify them all.

🔗

(a)

	$x_1$	$x_2$	$-1$
$y_1$	$1$	$-2$	$-2$	$=-t_1$
$y_2$	$1$	$-1$	$-1$	$=-t_2$
$-1$	$1$	$-2$	$0$	$=f$
	$=s_1$	$=s_2$	$=g$

🔗

(b)

	$x_1$	$x_2$	$-1$
$y_1$	$-2$	$1$	$-1$	$=-t_1$
$y_2$	$1$	$-1$	$-1$	$=-t_2$
$-1$	$2$	$1$	$0$	$=f$
	$=s_1$	$=s_2$	$=g$

🔗

(c)

	$x_1$	$x_2$	$-1$
$y_1$	$2$	$-2$	$2$	$=-t_1$
$y_2$	$-1$	$1$	$-1$	$=-t_2$
$-1$	$1$	$1$	$0$	$=f$
	$=s_1$	$=s_2$	$=g$

🔗

(d)

	$x_1$	$x_2$	$-1$
$y_1$	$6$	$-1$	$0$	$=-t_1$
$y_2$	$3$	$1$	$1$	$=-t_2$
$y_3$	$3$	$1$	$0$	$=-t_3$
$-1$	$2$	$2$	$0$	$=f$
	$=s_1$	$=s_2$	$=g$

🔗

(e)

	$x_1$	$x_2$	$x_3$	$-1$
$y_1$	$1$	$-1$	$1$	$-2$	$=-t_1$
$y_2$	$-1$	$1$	$1$	$1$	$=-t_2$
$-1$	$0$	$-1$	$1$	$0$	$=f$
	$=s_1$	$=s_2$	$=s_3$	$=g$

🔗

(f)

	$x_1$	$x_2$	$-1$
$y_1$	$-1$	$0$	$-1$	$=-t_1$
$y_2$	$-1$	$1$	$1$	$=-t_2$
$y_3$	$-1$	$-1$	$-1$	$=-t_3$
$-1$	$1$	$-1$	$0$	$=f$
	$=s_1$	$=s_2$	$=g$

🔗

9.

Consider the following tableau:

🔗

	$x_1$	$x_2$	$-1$
$y_1$	$2$	$0$	$c_1$	$=-t_1$
$y_2$	$0$	$3$	$c_2$	$=-t_2$
$-1$	$b_1$	$b_2$	$0$	$=f$
	$=s_1$	$=s_2$	$=g$

🔗

(a)

Find $b_1, b_2, c_1, c_2$ so that the basic solutions of the above tableau are optimal, and both problems have infinitely many solutions.

🔗

(b)

Classify the choices for $b_1, b_2, c_1, c_2$ for which the conditions of part a hold.

🔗

10.

Consider a two variable, two constraint primal maximization problem.

	$x_1$	$x_2$	$-1$
$y_1$	$a_{11}$	$a_{12}$	$b_1$	$=-t_1$
$y_2$	$a_{21}$	$a_{22}$	$b_2$	$=-t_2$
$-1$	$c_1$	$c_2$	$f$	$=f$
	$=s_1$	$=s_2$	$=g$

🔗

Recall Weak Duality Proposition 4.2.3, and Complementary Slackness, Definition 4.2.8. Suppose we found a pair of primal-dual solutions which satisfied main constraints, but failed one or more nonnegativity constraints.

🔗

(a)

Must the Weak Duality still hold? Prove or find a counterexample.

🔗

(b)

Suppose there were a pair of such solutions so that $f=g\text{,}$ must complementary slackness still hold? Prove or find a counterexample.

🔗

11.

Prove that for a canonical problem, feasible solutions $\x, \y\text{,}$ with slack variables $\vs, \vt$ exhibit complementary slackness if and only if $\x, \y$ are optimal.

🔗

(This fact is commonly known as the Complementary Slackness Theorem.)

🔗

12.

Solve the following noncanonical primal-dual problems:

🔗

(a)

	$\ec{x_1}$	$x_2$	$-1$
$\ec{y_1}$	$1$	$1$	$2$	$=0$
$y_2$	$-1$	$-1$	$-2$	$=-t_2$
$-1$	$-1$	$-2$	$0$	$=f$
	$=0$	$=s_2$	$=g$

🔗

(b)

	$\ec{x_1}$	$x_2$	$-1$
$\ec{y_1}$	$2$	$-2$	$-2$	$=0$
$y_2$	$-1$	$2$	$-2$	$=-t_2$
$-1$	$-1$	$-2$	$0$	$=f$
	$=0$	$=s_2$	$=g$

🔗

(c)

	$\ec{x_1}$	$x_2$	$-1$
$\ec{y_1}$	$1$	$-1$	$-1$	$=0$
$y_2$	$-1$	$1$	$-1$	$=-t_2$
$-1$	$0$	$1$	$0$	$=f$
	$=0$	$=s_2$	$=g$

🔗

(d)

	$\ec{x_1}$	$\ec{x_2}$	$x_3$	$-1$
$\ec{y_1}$	$1$	$-1$	$1$	$-1$	$=0$
$y_2$	$-1$	$-1$	$1$	$1$	$=-t_2$
$y_3$	$-1$	$1$	$1$	$1$	$=-t_3$
$-1$	$1$	$1$	$-1$	$0$	$=f$
	$=0$	$=0$	$=s_3$	$=g$

🔗

Prev Top Next

	\(x_1\)	\(x_2\)	\(-1\)
\(y_1\)	\(1\)	\(-2\)	\(-2\)	\(=-t_1\)
\(y_2\)	\(1\)	\(-1\)	\(-1\)	\(=-t_2\)
\(-1\)	\(1\)	\(-2\)	\(0\)	\(=f\)
	\(=s_1\)	\(=s_2\)	\(=g\)

	\(x_1\)	\(x_2\)	\(-1\)
\(y_1\)	\(-2\)	\(1\)	\(-1\)	\(=-t_1\)
\(y_2\)	\(1\)	\(-1\)	\(-1\)	\(=-t_2\)
\(-1\)	\(2\)	\(1\)	\(0\)	\(=f\)
	\(=s_1\)	\(=s_2\)	\(=g\)

	\(x_1\)	\(x_2\)	\(-1\)
\(y_1\)	\(2\)	\(-2\)	\(2\)	\(=-t_1\)
\(y_2\)	\(-1\)	\(1\)	\(-1\)	\(=-t_2\)
\(-1\)	\(1\)	\(1\)	\(0\)	\(=f\)
	\(=s_1\)	\(=s_2\)	\(=g\)

	\(x_1\)	\(x_2\)	\(-1\)
\(y_1\)	\(6\)	\(-1\)	\(0\)	\(=-t_1\)
\(y_2\)	\(3\)	\(1\)	\(1\)	\(=-t_2\)
\(y_3\)	\(3\)	\(1\)	\(0\)	\(=-t_3\)
\(-1\)	\(2\)	\(2\)	\(0\)	\(=f\)
	\(=s_1\)	\(=s_2\)	\(=g\)

	\(x_1\)	\(x_2\)	\(x_3\)	\(-1\)
\(y_1\)	\(1\)	\(-1\)	\(1\)	\(-2\)	\(=-t_1\)
\(y_2\)	\(-1\)	\(1\)	\(1\)	\(1\)	\(=-t_2\)
\(-1\)	\(0\)	\(-1\)	\(1\)	\(0\)	\(=f\)
	\(=s_1\)	\(=s_2\)	\(=s_3\)	\(=g\)

	\(\ec{x_1}\)	\(x_2\)	\(-1\)
\(\ec{y_1}\)	\(1\)	\(1\)	\(2\)	\(=0\)
\(y_2\)	\(-1\)	\(-1\)	\(-2\)	\(=-t_2\)
\(-1\)	\(-1\)	\(-2\)	\(0\)	\(=f\)
	\(=0\)	\(=s_2\)	\(=g\)

	\(\ec{x_1}\)	\(\ec{x_2}\)	\(x_3\)	\(-1\)
\(\ec{y_1}\)	\(1\)	\(-1\)	\(1\)	\(-1\)	\(=0\)
\(y_2\)	\(-1\)	\(-1\)	\(1\)	\(1\)	\(=-t_2\)
\(y_3\)	\(-1\)	\(1\)	\(1\)	\(1\)	\(=-t_3\)
\(-1\)	\(1\)	\(1\)	\(-1\)	\(0\)	\(=f\)
	\(=0\)	\(=0\)	\(=s_3\)	\(=g\)