TORBON RAYY: Standarzation of linear programming

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

Standarzation of linear programming

Example

Augmented form (slack form)

Example

No comments:

Post a Comment