We will now look at a problem that is more general than solving linear systems of the form .
Linear programs are of the form:
Note that linear programs have a linear objective () and linear constraints (). We can easily see how to reduce solving a linear system to a linear program, which would look like
Let’s take a look at a few examples of linear programs.
Example 1. (Max Flow)
Let be a graph with directed edges and capacities . Let vertices be the source and the sink respectively. Our goal is to find flows such that and . We want to maximize our net flow, which is the total flow out of source , so out linear program is
Example 2. (Low-cost Diet)
We need 180 units of protein, 100 units of carbs, and 20 units of fat. We can get sushi for 9 units of cost, tomato soup for 2 units of cost, and chicken massaman for 6 units of cost. A single unit of sushi gives 15 protein, 20 carbs, and 5 fat; tomato soup gives 5 protein, 30 carbs, 15 fat; chicken massaman gives 40 protein, 10 carb, 8 fat. What is the minimum cost satisfactory diet? Let’s assign the following variables:
Then, we get the following linear program,
Let’s note the costs of some solutions to the above program.
Is there a better solution? If not, how can we show that there is no better solution? Let’s work towards a lower bound for , the value of the optimal solution to the above program.
We will first try taking a multiple of one of our constraints,
So, . Can we tighten this lower bound?
We will explore this question on another example. Consider the following LP,
Let be the value of the optimal solution. Again, let’s try some solutions and note the values
How can we tell if this is optimal?
We can try another linear combination of constraints
What is the best possible upper bound? We would like to choose multipliers for constraints . Then, we get
So we’d like,
Then, this gives a valid upper bound on .
More generally the solution to the linear program
gives an upper bound for the linear program
or more concisely,
Theorem 1. (Weak Duality)