Page 414 - A Course in Linear Algebra with Applications

398 Chapter Ten: Linear Programming

There are four basic feasible solutions, i.e., extreme points.
The one that produces the largest value of,zis:r = 0,y = 10,
giving z = 20. Thus x = 0, y = 10 is an optimal solution.

Exercises 10.3

In each of the following linear programming problems,
transform the problem to canonical form and determine all the
basic solutions. Classify these as infeasible or basic feasible,
and then find the optimal solutions.

1.
maximize: z = 3x — y
( x + 3y < 6
subject to: < x — y < 2
{ x,y>0
2.
maximize: z = 2x + 3y
( 2x-y < 6
subject to: < 2x + y < 10
[x,y>0
3.
maximize: z = X\ + x-i + X3
{ 4xi + - 2x 2 + 4x 3 < < 12
x 2+
2x x
4
5x3
> 0
xi,x 2,x 3
4. A linear programming problem in standard form has m
constraints and n variables. Prove that the number of extreme
n
points is at most YlT=o (™^ ) •