Page 395 - A Course in Linear Algebra with Applications

10.1: Introduction to Linear Programming 379

and takes into account the times for which the machines are
available.
2. A nutritionist is planning a lunch menu with two food types
A and B. One ounce of A provides a c units of carbohydrate,
a/ units of fat and a p units of protein: for B the figures are
b c, bf, b p, respectively. The costs of one unit of A and one
unit of B are p and q respectively. The meal must provide at
least m c units of carbohydrate, m/ units of fat and m p units
of protein. Set up a linear program to determine how many
ounces of A and B should be provided in the meal in order to
minimize the cost e, while satisfying the dietary requirements.
3. Write the following linear programming problem in stan-
dard form:

minimize: z = 2x\ — x 2 — £3 4- £4
{ xi + + 2x 2 — x £3 - £4 < 4
£4
> 5
+
3^1
3
£2
+
xi,x 2 > 0
4. Write the linear programming problem in Exercise 10.4.3
in canonical form.
5. Consider the following linear programming problem in
£1, X2, • • •, x n with n constraints:

T
maximize: z = C X
AX = B
subject to:
X>0
where A is an n x n matrix with rank n.
(a) Show that there is a feasible solution if and only if
X
A~ B>Q.
(b) Show that if a feasible solution exists, it must be
optimal.
(c) If an optimal solution exists, what is the maximum
value of zl