Many optimization problems may be formulated as a linear program. Given matrix and vectors , , we seek some vector that satisfies

and maximizes

where elements in are nonnegative. We call the objective function, and are known as the constraints.

Flow Networks as Linear Programs

Pushing flow through a network reduces to linear programming!

objective:

capacity constraints:

flow preservation:

Decision Problem Formulation

Note that linear programs can be formulated as a decision problem. Given some , does there exist some such that

and

If YES, then simple provide the vector to be verified. If NO, we need some polynomial certificate to verify there exists no such vector. This is where the notion of a ‘dual’ program comes in. But first, perhaps an example is appropriate

Diet Problem

Suppose you are given the following meal choices: burger at $9, yogurt at $6, and ramen at $2. You also want to satisfy some dietary needs: you require at least 180 calories of protein, 100 calories of carbohydrates, and 20 calories of fat.

Given the above caloric breakdown of each meal, how can you satisfy your requirements while spending as little as possible? Let us formulate our problem as a linear program. Let be the units of burgers, yogurts, and ramen we purchase. Note that we have the following constraints

where we want to minimize our objective . Note that this is a minimization linear program, and to convert it to standard form, all we need to do is negate the objective and constraints, which yields the following linear program

objective:

constraints:

Another Problem

Consider following linear program

objective:

constraints:

(1)

(2)

(3)

Let us assign variable to constraint inequality (j), ensuring . Note that

Adding each inequality together and grouping by yields

For each , constrain multiplicative term to be greater than or equal to , yielding following constraints

These constraints ensure that . As such, this is the dual program for original linear program with objective that we seek to minimize and constraints given above.

Dual Programs

Let be matrix and , be vectors.

Given linear program with following objective and constraints

objective:

constraint :

Dual program is given as follows

objective:

constraint :

where , . Weak duality states

Linear Programing Duality Theorem

Given primal program , dual program , there exist four possibilities

- P is infeasible, which implies D is unbounded
- P is unbounded, which implies D is infeasible
- P, D are both infeasible
- P, D are feasible

Linear program is infeasible if there exists no solution that satisfies all constraints, and is unbounded if objective function may be incremented towards positive or negative infinity. We shall demonstrate that in case (4), P, D have the same optimal value. We will need the following lemma to do this

Farkas’ Lemma

For any matrix , vector , exactly one of the following holds

- There exists such that

and

- There exists such that

and