Editing Linear programming (section)

== Standard form ==
''Standard form'' is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts:
* A '''linear (or affine) function to be maximized'''
: e.g. <math> f(x_{1},x_{2}) = c_1 x_1 + c_2 x_2</math>
* '''Problem constraints''' of the following form
: e.g.
:: <math>\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}</math>
* '''Non-negative variables'''
: e.g.
:: <math>\begin{matrix}
 x_1 \geq 0 \\
 x_2 \geq 0
\end{matrix}</math>

The problem is usually expressed in ''[[Matrix (mathematics)|matrix]] form'', and then becomes:
: <math>\max \{\, \mathbf{c}^\mathsf{T} \mathbf{x} \mid \mathbf{x}\in\mathbb{R}^n\land A \mathbf{x} \leq \mathbf{b} \land \mathbf{x} \geq 0 \,\}</math>

Other forms, such as minimization problems, problems with constraints on alternative forms, and problems involving negative [[variable (programming)|variables]] can always be rewritten into an equivalent problem in standard form.

=== Example ===
[[File:linear_programming_feasible_region_farmer_example.svg|thumb|Graphical solution to the farmer example &ndash; after shading regions violating the conditions, the vertex of the unshaded region with the dashed line farthest from the origin gives the optimal combination (its lying on the land and pesticide lines implies that revenue is limited by land and pesticide, not fertilizer)]]
Suppose that a farmer has a piece of farm land, say ''L'' [[hectare]]s, to be planted with either wheat or barley or some combination of the two. The farmer has ''F'' kilograms of fertilizer and ''P'' kilograms of pesticide. Every hectare of wheat requires ''F''<sub>1</sub> kilograms of fertilizer and ''P''<sub>1</sub> kilograms of pesticide, while every hectare of barley requires ''F''<sub>2</sub> kilograms of fertilizer and ''P''<sub>2</sub> kilograms of pesticide. Let S<sub>1</sub> be the selling price of wheat and S<sub>2</sub> be the selling price of barley, per hectare. If we denote the area of land planted with wheat and barley by ''x''<sub>1</sub> and ''x''<sub>2</sub> respectively, then profit can be maximized by choosing optimal values for ''x''<sub>1</sub> and ''x''<sub>2</sub>. This problem can be expressed with the following linear programming problem in the standard form:
{|
|-
| valign="top"|Maximize:
| valign="top"|<math>S_1\cdot x_1+S_2\cdot x_2</math>
| (maximize the revenue (the total wheat sales plus the total barley sales) – revenue is the "objective function")
|-
| {{nowrap|Subject to:}}
| <math>x_1 + x_2\leq L</math>
| (limit on total area)
|-
|
| <math>F_1\cdot x_1+F_2\cdot x_2\leq F</math>
| (limit on fertilizer)
|-
|
| <math>P_1\cdot x_1 + P_2\cdot x_2\leq P</math>
| (limit on pesticide)
|-
|
| <math>x_1\geq 0, x_2\geq 0</math>
| (cannot plant a negative area).
|}

In matrix form this becomes:
: maximize <math>\begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} </math>
: subject to <math>\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}. </math>