TORBON RAYY: 2016

Every linear programming problem, referred to as a primal problem, can be converted into a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the primal problem as:

Maximize c^Tx subject to Ax ≤ b, x ≥ 0;

with the corresponding symmetric dual problem,

Minimize b^Ty subject to A^Ty ≥ c, y ≥ 0.

An alternative primal formulation is:

Maximize c^Tx subject to Ax ≤ b;

with the corresponding asymmetric dual problem,

Minimize b^Ty subject to A^Ty = c, y ≥ 0.

There are two ideas fundamental to duality theory. One is the fact that (for the symmetric dual) the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual. The weak duality theorem states that the objective function value of the dual at any feasible solution is always greater than or equal to the objective function value of the primal at any feasible solution. The strong duality theorem states that if the primal has an optimal solution, x^*, then the dual also has an optimal solution, y^*, and c^Tx^*=b^Ty^*.
A linear program can also be unbounded or infeasible. Duality theory tells us that if the primal is unbounded then the dual is infeasible by the weak duality theorem. Likewise, if the dual is unbounded, then the primal must be infeasible. However, it is possible for both the dual and the primal to be infeasible. As an example, consider the linear program:

Maximize: $2x_1 -x_2$
Subject to:	$x_1 -x_2 \le 1$
	$-x_1 +x_2 \le -2$
	$x_1, x_2 \geq 0$ .

Example

Revisit the above example of the farmer who may grow wheat and barley with the set provision of some L land, F fertilizer and P pesticide. Assume now that y unit prices for each of these means of production (inputs) are set by a planning board. The planning board's job is to minimize the total cost of procuring the set amounts of inputs while providing the farmer with a floor on the unit price of each of his crops (outputs), S₁ for wheat and S₂ for barley. This corresponds to the following linear programming problem:

Minimize: $L\cdot y_L + F\cdot y_F + P\cdot y_P$		(minimize the total cost of the means of production as the "objective function")
subject to:	$y_L+F_1\cdot y_F+P_1\cdot y_P\geq S_1$	(the farmer must receive no less than S₁ for his wheat)
	$y_L+F_2\cdot y_F+P_2\cdot y_P\geq S_2$	(the farmer must receive no less than S₂ for his barley)
	$y_L, y_F, y_P\geq 0$	(prices cannot be negative).

In matrix form this becomes:

Minimize:

\begin{bmatrix} L & F & P \end{bmatrix} \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix}

subject to:

\begin{bmatrix} 1 & F_1 & P_1 \\ 1 & F_2 & P_2 \end{bmatrix} \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} \ge \begin{bmatrix} S_1 \\ S_2 \end{bmatrix}, \, \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} \ge 0.

The primal problem deals with physical quantities. With all inputs available in limited quantities, and assuming the unit prices of all outputs is known, what quantities of outputs to produce so as to maximize total revenue? The dual problem deals with economic values. With floor guarantees on all output unit prices, and assuming the available quantity of all inputs is known, what input unit pricing scheme to set so as to minimize total expenditure?
To each variable in the primal space corresponds an inequality to satisfy in the dual space, both indexed by output type. To each inequality to satisfy in the primal space corresponds a variable in the dual space, both indexed by input type.
The coefficients that bound the inequalities in the primal space are used to compute the objective in the dual space, input quantities in this example. The coefficients used to compute the objective in the primal space bound the inequalities in the dual space, output unit prices in this example.
Both the primal and the dual problems make use of the same matrix. In the primal space, this matrix expresses the consumption of physical quantities of inputs necessary to produce set quantities of outputs. In the dual space, it expresses the creation of the economic values associated with the outputs from set input unit prices.
Since each inequality can be replaced by an equality and a slack variable, this means each primal variable corresponds to a dual slack variable, and each dual variable corresponds to a primal slack variable. This relation allows us to speak about complementary slackness.

Another example

Sometimes, one may find it more intuitive to obtain the dual program without looking at the program matrix. Consider the following linear program:

Minimize	$\sum_{i=1}^m{c_i x_i} + \sum_{j=1}^n{d_j t_j}$
subject to	$\sum_{i=1}^m{a_{ij} x_i} + e_j t_j \ge g_j$	,	$1 \le j \le n$
	$f_i x_i + \sum_{j=1}^n{b_{ij} t_j} \ge h_i$	,	$1 \le i \le m$
	$x_i \ge 0,\, t_j \ge 0$	,	$1 \le i \le m, 1 \le j \le n$

We have m + n conditions and all variables are non-negative. We shall define m + n dual variables: y_j and s_i. We get:

Minimize	$\sum_{i=1}^m{c_i x_i} + \sum_{j=1}^n{d_j t_j}$
subject to	$\sum_{i=1}^m{a_{ij} x_i} \cdot y_j + e_j t_j \cdot y_j \ge g_j \cdot y_j$	,	$1 \le j \le n$
	$f_i x_i \cdot s_i + \sum_{j=1}^n{b_{ij} t_j} \cdot s_i \ge h_i \cdot s_i$	,	$1 \le i \le m$
	$x_i \ge 0,\, t_j \ge 0$	,	$1 \le i \le m, 1 \le j \le n$
	$y_j \ge 0,\, s_i \ge 0$	,	$1 \le j \le n, 1 \le i \le m$

Since this is a minimization problem, we would like to obtain a dual program that is a lower bound of the primal. In other words, we would like the sum of all right hand side of the constraints to be the maximal under the condition that for each primal variable the sum of its coefficients do not exceed its coefficient in the linear function. For example, x₁ appears in n + 1 constraints. If we sum its constraints' coefficients we get a_1,1y₁ + a_1,2y₂ + ... + a_1,ny_n + f₁s₁. This sum must be at most c₁. As a result, we get:

Maximize	$\sum_{j=1}^n{g_j y_j} + \sum_{i=1}^m{h_i s_i}$
subject to	$\sum_{j=1}^n{a_{ij} y_j} + f_i s_i \le c_i$	,	$1 \le i \le m$
	$e_j y_j + \sum_{i=1}^m{b_{ij} s_i} \le d_j$	,	$1 \le j \le n$
	$y_j \ge 0,\, s_i \ge 0$	,	$1 \le j \le n, 1 \le i \le m$

Note that we assume in our calculations steps that the program is in standard form. However, any linear program may be transformed to standard form and it is therefore not a limiting factor.

Covering/packing dualities

A covering LP is a linear program of the form:

Minimize: b^Ty,

subject to: A^Ty ≥ c, y ≥ 0,

such that the matrix A and the vectors b and c are non-negative.
The dual of a covering LP is a packing LP, a linear program of the form:

Maximize: c^Tx,

subject to: Ax ≤ b, x ≥ 0,

such that the matrix A and the vectors b and c are non-negative.

Examples

Covering and packing LPs commonly arise as a linear programming relaxation of a combinatorial problem and are important in the study of approximation algorithms.^[4] For example, the LP relaxations of the set packing problem, the independent set problem, and the matching problem are packing LPs. The LP relaxations of the set cover problem, the vertex cover problem, and the dominating set problem are also covering LPs.
Finding a fractional coloring of a graph is another example of a covering LP. In this case, there is one constraint for each vertex of the graph and one variable for each independent set of the graph

Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts:

A linear function to be maximized

e.g.

f(x_{1},x_{2}) = c_1 x_1 + c_2 x_2

Problem constraints of the following form

e.g.

\begin{matrix} a_{11} x_1 + a_{12} x_2 &\leq b_1 \\ a_{21} x_1 + a_{22} x_2 &\leq b_2 \\ a_{31} x_1 + a_{32} x_2 &\leq b_3 \\ \end{matrix}

Non-negative variables

e.g.

\begin{matrix} x_1 \geq 0 \\ x_2 \geq 0 \end{matrix}

The problem is usually expressed in matrix form, and then becomes:

\max \{ \mathbf{c}^\mathrm{T} \mathbf{x} \;|\; A \mathbf{x} \leq \mathbf{b} \and \mathbf{x} \geq 0 \}

Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an equivalent problem in standard form.

Example

Suppose that a farmer has a piece of farm land, say L km², to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and insecticide, P kilograms. Every square kilometer of wheat requires F₁ kilograms of fertilizer and P₁ kilograms of insecticide, while every square kilometer of barley requires F₂ kilograms of fertilizer and P₂ kilograms of insecticide. Let S₁ be the selling price of wheat per square kilometer, and S₂ be the selling price of barley. If we denote the area of land planted with wheat and barley by x₁ and x₂ respectively, then profit can be maximized by choosing optimal values for x₁ and x₂. This problem can be expressed with the following linear programming problem in the standard form:

Maximize: $S_1\cdot x_1+S_2\cdot x_2$		(maximize the revenue—revenue is the "objective function")
Subject to:	$x_1 + x_2\leq L$	(limit on total area)
	$F_1\cdot x_1+F_2\cdot x_2\leq F$	(limit on fertilizer)
	$P_1\cdot x_1 + P_2\cdot x_2\leq P$	(limit on insecticide)
	$x_1\geq 0, x_2\geq 0$	(cannot plant a negative area).

Which in matrix form becomes:

maximize

\begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}

subject to

\begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}.

Augmented form (slack form)

Linear programming problems can be converted into an augmented form in order to apply the common form of the simplex algorithm. This form introduces non-negative slack variables to replace inequalities with equalities in the constraints. The problems can then be written in the following block matrix form:

Maximize

z

\begin{bmatrix} 1 & -\mathbf{c}^T & 0 \\ 0 & \mathbf{A} & \mathbf{I} \end{bmatrix} \begin{bmatrix} z \\ \mathbf{x} \\ \mathbf{s} \end{bmatrix} = \begin{bmatrix} 0 \\ \mathbf{b} \end{bmatrix}

\mathbf{x} \ge 0, \mathbf{s} \ge 0

where

\mathbf{s}

are the newly introduced slack variables, and

z

is the variable to be maximized.

Example

The example above is converted into the following augmented form:

Maximize: $S_1\cdot x_1+S_2\cdot x_2$		(objective function)
subject to:	$x_1 + x_2 + x_3 = L$	(augmented constraint)
	$F_1\cdot x_1+F_2\cdot x_2 + x_4 = F$	(augmented constraint)
	$P_1\cdot x_1 + P_2\cdot x_2 + x_5 = P$	(augmented constraint)
	$x_1,x_2,x_3,x_4,x_5 \ge 0$ .

where

x_3, x_4, x_5

are (non-negative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused insecticide.
In matrix form this becomes:

Maximize

z

\begin{bmatrix} 1 & -S_1 & -S_2 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & F_1 & F_2 & 0 & 1 & 0 \\ 0 & P_1 & P_2 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} \ge 0.

TORBON RAYY

Pages

Sunday, 7 February 2016

Duality of linear programming

Example

Another example

Covering/packing dualities

Examples

Standarzation of linear programming

Example

Augmented form (slack form)

Example