Page 394 - A Course in Linear Algebra with Applications

378 Chapter Ten: Linear Programming

variables, and replace the ith constraint anXi+- • -+ai nx n < bi
by the new constraint

1
2
for i = 1, ,..., m, together with X{ +n > 0, i — ,..., m.
The effect is totransform the problem to an equivalent linear
programming problem incanonical form:

maximize: z = C\X\ + • • • + c nx n

subject to:

•
h
x n+i
{ a lxxi + • • • • • + + a 2nXn + + Xn+2 = b 2
a lnx n
=
a 2\Xi
+
Q"ml%l r " ' ' T arnn£n ~r X n-\- m
Xi > 0, i = 1,2,..., n + m.
Combining this observation with 10.1.1, we obtain:

Theorem 10.1.2 Every linear programmingproblem is
equivalent to one in canonical form.

Exercises 10.1
1. A publishing house plans to issue three types of pamphlets
Pi) ?2) ?3- Each pamphlet has to be printed and bound.
The times in hours required to print and to bind one copy
of pamphlet Pj are Ui and Vi respectively. The printing and
binding machines can run for maximum times s and t hours
per day respectively. The profit made on one pamphlet of
type Pi is pi. Let xi,x 2,X3 be thenumbers of pamphlets
of the three types to be produced per day. Set up a linear
program in xi,x 2,x 3 which maximizes the profitp per day