Next: , Up: Introduction   [Contents]

1.1 Linear programming problem

In MathProg it is assumed that the linear programming (LP) problem has the following statement:

minimize (or maximize) $$\begin{equation}z=c_1x_1+c_2x_2+\dots+c_nx_n+c_0\tag{1}\end{equation}$$ subject to linear constraints $$\begin{equation}\matrix{ L_1\leq a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n\leq U_1\cr L_2\leq a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n\leq U_2\cr .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\cr L_m\leq a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n\leq U_m\cr }\tag{2}\end{equation}$$ and bounds of variables $$\begin{equation}\matrix{ l_1\leq x_1\leq u_1\cr l_2\leq x_2\leq u_2\cr .\ \ .\ \ .\ \ .\cr l_n\leq x_n\leq u_n\cr }\tag{3}\end{equation}$$


$x_1, x_2, \dots, x_n$are variables;
$z$is the objective function;
$c_1, c_2, \dots, c_n$are coefficients of the objective function;
$c_0$is the constant term (“shift”) of the objective function;
$a_{11}, a_{12}, \dots, a_{mn}$are constraint coefficients;
$L_1, L_2, \dots, L_m$are lower constraint bounds;
$U_1, U_2, \dots, U_m$are upper constraint bounds;
$l_1, l_2, \dots, l_n$are lower bounds of variables;
$u_1, u_2, \dots, u_n$are upper bounds of variables.

Bounds of variables and constraint bounds can be finite as well as infinite. Besides, lower bounds can be equal to corresponding upper bounds. Thus, the following types of variables and constraints are allowed:

$-\infty<x<+\infty$Free (unbounded) variable
$x\geq l$Variable with lower bound
$x\leq u$Variable with upper bound
$l\leq x\leq u$Double-bounded variable
$x=l\ (=u)$Fixed variable
$-\infty<\sum a_jx_j<+\infty$Free (unbounded) linear form
$\sum a_jx_j\geq L$Inequality constraint “greater than or equal to”
$\sum a_jx_j\leq U$Inequality constraint “less than or equal to”
$L\leq\sum a_jx_j\leq U$Double-bounded inequality constraint
$\sum a_jx_j=L\ (=U)$Equality constraint

In addition to pure LP problems MathProg allows mixed integer linear programming (MIP) problems, where some (or all) structural variables are restricted to be integer.

Next: , Up: Introduction   [Contents]