Page 387 - A Course in Linear Algebra with Applications

10.1: Introduction to Linear Programming 371

Suppose the company decides to produce Xj units of prod-
uct Fj. Then the profit on marketing the products will be
z — p\Xi + P2X2. On the other hand, the production process
a
will use n^i +012X2 units of ingredient I± and 021^2 + 022^2
units of ingredient 72- Therefore X\ and x 2 must satisfy the
constraints

auxi + CL12X2 < mi and a 2 i£i + a 22^2 < ™2-

Also x\ and x 2 cannot be negative.
We therefore have to solve the following linear program-
ming problem:

maximize : z = p\X\ + P2X2
{ auxi + ai 2x 2 < < mi

+
022^2
?™2
0^21^1
x\,x 2 > 0
Example 10.1.2 (A transportationproblem)
A company has m factories F±,..., F m and n warehouses
Wi,..., W n. Factory Fj can produce at most r^ units of a
certain product per week and warehouse Wj must be able to
supply at least Sj units per week. The cost of shipping one
unit from factory Fi to warehouse Wj is Cij. How many units
should be shipped from each factory to each warehouse per
week in order to minimize the total transportation cost and
yet still satisfy the requirements on the factories and ware-
houses?
Let Xij be the number of units to be shipped from factory
Fi to warehouse Wj per week. Then the total transportation
cost for the week is

m n

i=l j=X