Linear Programming Basics

Tags: ,

Linear Programming

Linear programming is the problem of optimizing a linear function subject to linear inequality constraints.

\begin{array}{llll}\textit{minimize } & \sum_j c_j x_j & &\\\textit{subject to } & \sum a_{ij}x_{ij} & \geq b_i & i=1 \ldots m \\ & x_j \geq 0 & &\end{array}

For example:

\begin{array}{lll}\textit{minimize } & 7x_1 + x_2 + 5x_3 & \\\textit{subject to } & x_1 - x_2 + 3x_3 & \geq 10 \\ & 5x_1 + 2x_2 - x_3 & \geq 6 \\ & x_1, x_2 , x_3 \geq 0\end{array}

Standard form of an LP: All the constraints are =-type.
\begin{array}{llll}\textit{minimize } & \sum_j c_j x_j & &\\\textit{subject to } & \sum a_{ij}x_{ij} & = b_i & i=1 \ldots m \\ & x_j \geq 0 & &\end{array}

Canonical Form of an LP: All the constraints are \geq-type for a minimization problem and \leq-type for a maximization problem.
\begin{array}{llll}\textit{minimize } & \sum_j c_j x_j & & \\\textit{subject to } & \sum a_{ij}x_{ij} & \geq b_i & i=1 \ldots m \\ & x_j \geq 0 & &\end{array}

It is possible to transform any LP to standard/canonical form.

Constraints

Suppose we have the following constraint:

x_1 + 3 x_2 \leq 3

We can transform it to the standard form by adding a slack variable as follows:

x_1 + 3 x_2 + x_3 = 3

where x_3 \geq 0.

Now consider the following constraint.
2 x_1 + 5 x_2 \geq 4

We can transform it to the standard form by adding a surplus variable as follows:

2 x_1 + 5 x_2 - x_3 = 4

where x_3 \geq 0.

Finally, an equality-type constraint

x_1 + x_2 = 1

can be transformed to the canonical form by introducing two constraints.

x_1 + x_2 \leq 1 \\x_1 + x_2 \geq 1

Variables

In some cases variables can be negative. In that case we introduce new variables in order to make them positive as follows:

x_1 \leq 0 \\x_1^{'} = - x_1 \\x_1^{'} \geq 0

In other cases some variables can be unrestricted. In such a case we introduce two new variables for each unrestricted variable as follows:

x_1
x_1 = x_1^+ - x_1^-

where x_1^+ \geq 0 and x_1^- \geq 0

Finally suppose that there is some bound restriction on a variable.

x_1 \geq 5

We can introduce a new variable x_1^{'} such that x_1^{'} \geq 0 :

x_1^{'} = x_1 - 5

A feasible solution is a setting of variables that satisfies all constraints. It can be shown that an optimal solution will be on one the corner, in other words intersection of some constraints.

The standard algorithm to solve linear programs is Simplex algorithm.

Dual Program

The idea behind is placing a lower bound is that we are founding suitable nonnegative multipliers for the constraints so that we take their sum, the coefficient of each x_i in the sum is dominated by the coefficient in the objective function. In the example below, the constraints are multiplied with 1.

(x_1 - x_2 + 3x_3) + (5x_1 + 2x_2 - x_3) = (6x1 + x_2 + 2x_3) \geq 16
7x_1 + x_2 + 5x_3 \geq 6x1 + x_2 + 2x_3 \geq 16

The problem of finding the best lower bound can be formulated as a linear program and called dual program.
\begin{array}{lll}\textit{minimize } & 10y_1 + 6y_2 & \\\textit{subject to } & y_1 + 5y_2 & \leq 7 \\ & -y_1 + 2y_2 & \leq 1 \\ & 3y_1 - y_2 & \leq 5 \\ & y_1, y_2 \geq 0\end{array}

LP-duality Theorems

Strong Duality Theorem Primal finite optimum value is equal to the dual finite optimum value.
z_P^{\star} \geq z_D^{\star}

Weak Duality Theorem z_P \geq z_D

proof:
\sum_j c_j x_j \geq \sum_i b_i y_i
\sum_j c_j x_j \geq \sum_j (\sum_i a_{ij} y_i) x_j
\sum_j (\sum_i a_{ij} y_i) x_j = \sum_i (\sum_j a_{ij} x_j) y_i
\sum_i (\sum_j a_{ij} x_j) y_i \geq \sum_i b_i y_i

Complementary Slackness Conditions

if x_j \neq 0 then \sum_i a_{ij}y_i = c_j
if y_i \neq 0 then \sum_j a_{ij}x_j = b_i

A solution is optimum when primal and dual feasible and complementary slackness conditions are satisfied.
By construction every feasible solution to the dual program gives a lower bound on the optimum solution.

Comments are closed.