Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 31

Duality is an essential notion in linear programming. The duality operation associates any so-called primal linear programming problem with another such problem, known as the dual, that is defined solely in terms of the data of the primal problem.

Duality is interesting for two reasons:

 – the dual problem has an important economic interpretation that offers another perspective of the primal problem;

 – there are straightforward and powerful mathematical relations between the primal and dual problems; this will allow us to develop new algorithms that will be more efficient in many situations.

Suppose that we have the following primal program:

Its dual program is as follows:

REMARK.– The primal and dual programs satisfy the following relations:

 – m = number of constraints of (P) = number of variables of (D),

 – n = number of variables of (P) = number of constraints of (D).

If (P) has two constraints, (D) has two variables and can be solved graphically, regardless of the number of variables of (P).

So, what is the form of (D) when (P) is not in canonical form?

In such a case, we can determine (D) by reducing (P) to canonical form, as shown in the following example.

EXAMPLE 1.10.– Consider the LP:

By the above definition, the dual of (P) is given by

Setting y = u − v gives

(D) min w(y) = yb s.t. yA ≥ c, y with no sign restriction (denoted (y)).

In general, we have:

THEOREM 1.8.– The dual of the dual is the primal.