LinearProgramming < OpsRes

%BEGINLATEXPREAMBLE% \usepackage{amsmath} 
%ENDLATEXPREAMBLE%
---+ Linear Programming

The simplest type of mathematical programme is a _linear programme_.

For your mathematical programme to be a linear programme you need the following conditions to be true:
   1. The decision variables must be real variables; 
   2. The objective constraint must be a linear expression; 
   3. The constraints must be linear expressions. 

Linear expressions are any expression of the form

%BEGINLATEX% \begin{equation*} a_1 x_1 + a_2 x_2 + ... + a_n x_n \left\{ \begin{matrix} \leq \\ = \\ \geq \end{matrix} \right\} b \end{equation*} 
%ENDLATEX%

where %$a_1, a_2, \ldots, a_n$% and %$b$% are known quantities and %$x_1, x_2, \ldots, x_n$% are variables.

The general form of a linear programme is 
%BEGINLATEX%
\[
\begin{array}{rr@{}l}
\min & c^\top & x \\
\text{subject to} & A & x \left\{ \begin{matrix} \leq \\ = \\ \geq \end{matrix} \right\} b
\end{array}
\] 
%ENDLATEX%

The process of solving a linear programme is called _linear programming_. Linear programming is done via the [[https://en.wikipedia.org/wiki/Simplex_algorithm#Revised_simplex_algorithm][Revised Simplex Method]] (also known as the Primal Simplex Method), the [[https://www.egwald.com/operationsresearch/lpdualsimplex.php][Dual Simplex Method]] or an [[https://en.wikipedia.org/wiki/Interior_point_method][interior point method]]. Some software packages, such as [[https://www.cplex.com][CPLEX]], allow you to specify which method you use, but we won't go into further detail here.

To see linear programming in action, check out some of the linear programming case studies:

%SEARCH{search="LinearProgramming +\"Case Study:\"" type="keyword" casesensitive="on" nosearch="on" nosummary="on" excludetopic="%TOPIC%"}%

-- Main.MichaelOSullivan - 16 Feb 2008
This topic: OpsRes > WebHome > MathematicalProgramming > LinearProgramming
Topic revision: r3 - 2008-02-20 - TWikiAdminUser