Problems for Chapter 1

A rancher has a herd to feed who requires 54, 48, and 72 units of the nutritional elements A, B, and C, respectively, per day. Feed 1 costs 10 cents a pound and contains 8, 4 and 3 units of elements A, B, C respectively. Feed 2 costs 8 cents a pound and contains 2, 4 and 6 units of elements A, B, C respectively. How much of each feed should the rancher purchase to cover the herds nutritional needs while minimizing cost?

🔗

(g)

A drug company sells three different formulations of vitamin complex and mineral complex. The first formulation consists entirely of vitamin complex and sells for $1 per unit. The second formulation consists of 3/4 of a unit of vitamin complex and 1/4 of a unit of mineral complex and sells for $2 per unit. The third formulation consists of 1/2 of a unit of each of the complexes and sells for $3 per unit. If the company has 100 units of vitamin complex and 75 units of mineral complex available, how many units of each formulation should the company produce so as to maximize sales revenue?

🔗

(h)

\begin{aligned} Maximize: f (x, y) = & 5 x + 6 y \\ subject to: 2 x + 3 y & \geq 12 \\ - 3 x + 2 y & \leq 14 \\ x + y & \leq 12 \\ x, y & \geq 0. \end{aligned}

🔗

3.

For each of the following, sketch the feasible region

R,

and find the optimal solution by identifying the extreme points of

R

and evaluating.

🔗

(a)

\begin{aligned} Maximize: f (x, y) = & 2 x + y \\ subject to: x + 4 y & \leq 11 \\ 6 x + 2 y & \leq 22 \\ x, y & \geq 0. \end{aligned}

🔗

(b)

\begin{aligned} Minimize: f (x, y) = & 2 x + y \\ subject to: x + 4 y & \geq 11 \\ 6 x + 2 y & \geq 22 \\ x, y & \geq 0. \end{aligned}

🔗

4.

Prove that Exercise 1.5.3 (H) has infinitely many optimal solutions, two of which lie on extreme points. Identify these points on the plot of the feasible region done in Exercise 1.5.3.

🔗

5.

Prove that if

x, x^{'}

are distinct optimal solutions of a canonical linear optimization problem, then all points on the line segment between

x, x^{'}

are also optimal solutions of the problem.

🔗

Conclude that a canonical linear optimization problem can have 0, 1 or infinitely many optimal solutions and no other possibilities.

🔗

6.

Consider the canonical linear optimization problem

🔗

\begin{aligned} Maximize: f (x, y, z, w) = 3 x - 2 y + 5 z - w \\ subject to: - x + 2 y - 3 z + 6 w & \leq 12 \\ x, y, z, w & \geq 0. \end{aligned}

🔗

Find the

(\binom{5}{4})

potential intersections of bounding hyperplanes, determine which are feasible, and which of those are optimal.

🔗

7.

Consider the canonical linear optimization problem

🔗

\begin{aligned} Minimize: g (x, y, z, w) = 2 x - y - 3 z + 4 w \\ subject to: x + 2 y + 2 z + 4 y & \geq 8 \\ 4 x - y & \geq 6 \\ x, y, z, w & \geq 0. \end{aligned}

🔗

Find the

(\binom{6}{4})

potential intersections of bounding hyperplanes, determine which are feasible, and which of those are optimal. (It is recommended that you use some technological tools to solve for the resulting linear systems.)

xxxxxxxxxx
 
A=matrix([
[1,0,0,0,0],
[0,1,0,0,0], 
[0,0,1,0,0],
[0,0,0,1,0]])
print(A)
print(" ")
print(A.rref())

🔗

8.

Express

(\binom{k + 4}{4})

as a polynomial in terms of

k .

How does this relate to Exercise 1.5.6, Exercise 1.5.7?

🔗

9.

Show that

🔗

\begin{aligned} Maximize: f (x, y) = & x - y \\ subject to: x + y & \geq 5 \\ x - 5 y & \leq 0 \\ y - 2 x & \leq 1 \\ x, y & \geq 0. \end{aligned}

is unbounded. (Hint: sketch the feasible region and consider feasible points on the line

x = 5 y .

)

🔗

10.

Show that

🔗

\begin{aligned} Minimize: g (x, y) = & 5 x + 3 y \\ subject to: y - 5 x & \geq 1 \\ x - 5 y & \geq 0 \\ x, y & \geq 0. \end{aligned}

is infeasible.

🔗

11.

For each of the following, determine whether or not the statement is TRUE or FALSE. If TRUE, provide a proof, if FALSE, provide a counterexample.

🔗

(a)

If a canonical feasible linear optimization problem is unbounded, then it’s feasible region is unbounded.

🔗

(b)

If a canonical feasible linear optimization problem has unbounded feasible region, then it is unbounded.

🔗

Prev Top Next