232 CHAPTER 11. LINEAR PROGRAMMING
F1 F2 F3 F4
iron 1 2 1 3protein 5 3 2 1folic acid 1 2 2 1copper 2 1 1 1calcium 1 1 1 1
This information is available to a pig farmer and Fi denotes a particular feed. Thenumbers in the table contain the number of units of a particular nutrient contained in onepound of the given feed. Thus F2 has 2 units of iron in one pound. Now suppose the cost ofeach feed in cents per pound is given in the following table.
F1 F2 F3 F4
2 3 2 3A typical pig needs 5 units of iron, 8 of protein, 6 of folic acid, 7 of copper and 4 of
calcium. (The units may change from nutrient to nutrient.) How many pounds of each feedper pig should the pig farmer use in order to minimize his cost?
His problem is to minimize C ≡ 2x1 +3x2 +2x3 +3x4 subject to the constraints
x1 +2x2 + x3 +3x4 ≥ 5,5x1 +3x2 +2x3 + x4 ≥ 8,
x1 +2x2 +2x3 + x4 ≥ 6,2x1 + x2 + x3 + x4 ≥ 7,
x1 + x2 + x3 + x4 ≥ 4.
where each xi ≥ 0. Add in the slack variables,
x1 +2x2 + x3 +3x4− x5 = 55x1 +3x2 +2x3 + x4− x6 = 8x1 +2x2 +2x3 + x4− x7 = 6
2x1 + x2 + x3 + x4− x8 = 7x1 + x2 + x3 + x4− x9 = 4
The augmented matrix for this system is1 2 1 3 −1 0 0 0 0 55 3 2 1 0 −1 0 0 0 81 2 2 1 0 0 −1 0 0 62 1 1 1 0 0 0 −1 0 71 1 1 1 0 0 0 0 −1 4
How in the world can you find a basic feasible solution? Remember the simplex algorithmis designed to keep the entries in the right column nonnegative so you use this algorithm afew times till the obvious solution is a basic feasible solution.
Consider the first column. The pivot is the 5. Using the row operations described in thealgorithm, you get