242 CHAPTER 11. LINEAR PROGRAMMING
Proof: Since the solution to A.) is basic and feasible, there exists a simplex tableau like11.23 such that x′ can be split into xB and xF such that xF = 0 and xB = B−1b. Now since itis a minimizer, it follows cBB−1F−cF ≤ 0 and the minimum value for cx is cBB−1b. Stat-ing this again, cx = cBB−1b. Is it possible you can take y = cBB−1? From Lemma 11.5.1this will be so if cBB−1 solves the constraints of problem B.). Is cBB−1≥ 0? Is cBB−1A≤ c?These two conditions are satisfied if and only if cBB−1
(A −I
)≤(
c 0). Refer-
ring to the process of permuting the columns of the first augmented matrix of 11.21 to get11.22 and doing the same permutations on the columns of
(A −I
)and
(c 0
), the
desired inequality holds if and only if cBB−1(
B F)≤(
cB cF
)which is equiva-
lent to saying(
cB cBB−1F)≤(
cB cF
)and this is true because cBB−1F− cF ≤ 0
due to the assumption that x is a minimizer. The simple formula is just
y = cBB−1. ■
The proof of the following corollary is similar.
Corollary 11.5.3 Suppose there exists a solution, y to B.) where y is a basic feasible solu-tion of the inequalities of B.). Then there exists a solution, x to A.) and cx = by. It is alsopossible to find x from y using a simple formula. In this case, and referring to 11.23, thesimple formula is x = B−T
1 bB1 .
As an example, consider the pig farmers problem. The main difficulty in this problemwas finding an initial simplex tableau. Now consider the following example and marvel athow all the difficulties disappear.
Example 11.5.4 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.
Here the dual problem is to maximize w = 5y1 + 8y2 + 6y3 + 7y4 + 4y5 subject to theconstraints
1 5 1 2 12 3 2 1 11 2 2 1 13 1 1 1 1
y1
y2
y3
y4
y5
≤
2323
.
Adding in slack variables, these inequalities are equivalent to the system of equations