Linear programming

From Supply Chain Management Encyclopedia

Revision as of 17:44, 1 September 2015 by Zyatchin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Linear programming is a part of general theory of mathematical programming. Mathematical programming is implemented in decision making problems, which could be formalized as a problem to find a maximum (or minimum) value of nonlinear objective function of many variables subject to given system of restrictions.

In linear programming one tends to find an optimal plan regardless of the nature of the problem to be solved. It could be a problem to find an optimal production, purchasing, building, investing plan etc.

A linear programming problem

To formalize linear programming problem \textit{decision variables} should be defined. A couple of such variable defines a certain plan. The criterion of optimality should be defined to find an optimal plan. Such criterion is a quantitative characteristic of object to be achieved and is called an \textit{objective function}. In common case the object of optimization is to find a plan which brings the maximum or minimum value to the objective function.

The third element of the linear programming problem to be defined is a system of restrictions. Linear optimization is always implemented subject to restrictions to variables. They could depend on a volume of inventory, budget, market demand etc. As a result, to set a linear programming problem the following should be defined:

variables

objective function

restrictions

Definition 1. Linear programming problem is a problem to of finding maximum or minimum value of a linear function with many variables subject to linear restrictions in form of equalities or inequalities, when variables have/ have no restriction to its sign.

The linearity of the function is defined by the following:

left hand side of restrictions are proportional to the variables

additivity of variables -- the effect of all variables in objective functions and in the left hand side of restrictions is a sum of all the variables.

A mathematical statement of linear programming problem

In a common case mathematical statement of linear programming problem for maximization has the following form:

$\, \max z=\max (c_{1} x_{1} +\ldots +c_{n} x_{n} )$

subject to

$\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} \le b_{i} ,\, \, \, \, i=1,2,\ldots ,r} \\ {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=r+1,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,r,\, \, \, \, r\le n} \end{array}\right.$

where

$\,x_{j}$ -- decision variables,

$\,z=c_{1} x_{1} +\ldots +c_{n} x_{n}$ -- objective function,

$\,c_{j} ,\, \, a_{ij} ,\, \, b_{i}$ -- given parameters of the problem.

Mathematical statement of linear programming problem for minimization has the following form:

$\, \min z=\min (c_{1} x_{1} +\ldots +c_{n} x_{n} )$

Subject to

$\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} \ge b_{i} ,\, \, \, \, i=1,2,\ldots ,r} \\ {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=r+1,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,r,\, \, \, r\le n} \end{array}\right.$

There are to special cases for linear programming problem: standard and canonical form.

Standard form of linear programming problem.

Assume that for the linear programming problem for maximization the following conditions are true:

All restrictions are inequalities of the form $\, \le$

All variables have restriction to its sign: $\, \ge 0$

then such a problem is standard maximization linear programming problem. In other words, it is to find

$\, \max z=\max (c_{1} x_{1} +\ldots +c_{n} x_{n} )$

subject to

$\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} \le b_{i} ,\, \, \, \, i=1,2,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,n} \end{array}\right.$

Now consider linear programming problem for minimization. Assume the following conditions are true:

All restrictions are inequalities of the form $\,\ge$

All variables have restriction to its sign: $\,\ge 0$

then such a problem is standard minimization linear programming problem. In other words, it is to find

$\, \min z=\min (c_{1} x_{1} +\ldots +c_{n} x_{n} )$

subject to

$\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} \ge b_{i} ,\, \, \, \, i=1,2,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,n} \end{array}\right.$

Canonical form of linear programming problem.

Canonical form of linear programming problem is the one, for which the following conditions are true:

All the restrictions are equalities;

All variables have restriction to its sign: $\,\ge 0$

Canonical form of linear programming problem for maximization:

$\, \max z=\max (c_{1} x_{1} +\ldots +c_{n} x_{n} )$

$\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=1,2,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,n} \end{array}\right.$

Canonical form of linear programming problem for minimizations:

$\, \min z=\min (c_{1} x_{1} +\ldots +c_{n} x_{n} )$

$\, \left\{\begin{array}{l} {a_{i1} x_{1} +a_{i2} x_{2} +\ldots +a_{in} x_{n} =b_{i} ,\, \, \, \, i=1,2,\ldots ,m} \\ {x_{j} \ge 0,\, \, \, j=1,2,\ldots ,n} \end{array}\right.$

Any linear programming problem with elementary operations could be transformed to one of the special forms.

Denote $\, x=(x_{1} ,x_{2} ,\ldots ,x_{n} )$ . Linear programming problem for maximization consists in determining such values $x_{1}^{*} ,x_{2}^{*} ,\ldots ,x_{n}^{*} </math> , that

$\, c_{1} x_{1}^{*} +c_{2} x_{2}^{*} +\ldots +c_{n} x_{n}^{*} =\mathop{\max }\limits_{x\in M} \left(c_{1} x_{1}^{} +c_{2} x_{2}^{} +\ldots +c_{n} x_{n}^{} \right),$

where $\, M$ -- a set of values for $\, x$ , which satisfy the system of restrictions for linear programming problem.

Definition 2. A collection $\, x=(x_{1} ,x_{2} ,\ldots ,x_{n} )$ , which satisfy the system of restrictions for linear programming problem, is called feasible solution. A set of all feasible solutions for linear programming problem denote $\, M$ .

Definition 3. A feasible solutions $\, x^{*} =(x_{1}^{*} ,x_{2}^{*} ,\ldots ,x_{n}^{*} )$ for linear programming problem, for which an objective functions takes its maximum (minimum) value, is called optimal solution to the linear programming problem.