20. Задача линейного программирования

1. Определение

Задача линейного программирования — это задача нахождения максимального или минимального значения линейной функции нескольких переменных при линейных ограничениях в виде равенств и неравенств.

Линейная функция, значение которой требуется оптимизировать, называется целевой функцией:

$$z=c_1x_1+c_2x_2+\ldots+c_nx_n.$$

Здесь $x_1,\ldots,x_n$ — переменные задачи, а $c_1,\ldots,c_n$ — заданные коэффициенты.

Ограничения имеют вид

$$a_{i1}x_1+a_{i2}x_2+\ldots+a_{in}x_n \leqslant b_i,$$ $$a_{i1}x_1+a_{i2}x_2+\ldots+a_{in}x_n \geqslant b_i$$

или

$$a_{i1}x_1+a_{i2}x_2+\ldots+a_{in}x_n=b_i.$$

На некоторые или на все переменные могут накладываться ограничения на знак, например $x_j\geqslant 0$.

2. Задача максимизации

Стандартную задачу максимизации можно записать в виде

$$\max z=\max\left(c_1x_1+\ldots+c_nx_n\right)$$

при условиях

$$\begin{cases} a_{i1}x_1+\ldots+a_{in}x_n\leqslant b_i, & i=1,\ldots,k,\\ a_{i1}x_1+\ldots+a_{in}x_n=b_i, & i=k+1,\ldots,m,\\ x_j\geqslant 0, & j=1,\ldots,p. \end{cases}$$

Переменные $x_{p+1},\ldots,x_n$ могут не иметь ограничений на знак.

В матричной форме целевая функция записывается как

$$z=c^{T}x.$$

3. Задача минимизации

Стандартную задачу минимизации можно представить в виде

$$\min z=\min\left(c_1x_1+\ldots+c_nx_n\right)$$

при условиях

$$\begin{cases} a_{i1}x_1+\ldots+a_{in}x_n\geqslant b_i, & i=1,\ldots,k,\\ a_{i1}x_1+\ldots+a_{in}x_n=b_i, & i=k+1,\ldots,m,\\ x_j\geqslant 0, & j=1,\ldots,p. \end{cases}$$

4. Допустимые и оптимальные решения

Вектор

$$x=(x_1,\ldots,x_n),$$

удовлетворяющий всем ограничениям задачи, называется допустимым решением, или допустимым планом.

Множество всех допустимых решений обозначим через $M$:

$$M\subseteq\mathbb{R}^n.$$

Поскольку все ограничения линейны, множество $M$ является выпуклым многогранным множеством.

Допустимое решение

$$x^*=(x_1^*,\ldots,x_n^*)$$

называется оптимальным, если на нём целевая функция достигает наибольшего или наименьшего значения среди всех допустимых решений.

Для задачи максимизации:

$$c^{T}x^*=\max_{x\in M}c^{T}x.$$

Для задачи минимизации:

$$c^{T}x^*=\min_{x\in M}c^{T}x.$$

Число

$$z^*=c^{T}x^*$$

называется оптимальным значением целевой функции.

5. Возможные случаи

При решении задачи линейного программирования возможны следующие ситуации:

1. Множество $M$ пусто — задача не имеет допустимых решений.
2. Целевая функция не ограничена на $M$ — конечного оптимального значения нет.
3. Оптимальное решение существует и является единственным.
4. Существует несколько оптимальных решений. В этом случае оптимальными являются все точки некоторой грани допустимого множества.

Если оптимальное значение достигается, то в стандартной задаче линейного программирования существует оптимальное решение, являющееся вершиной допустимого многогранника.

6. Приведение задач к эквивалентным формам

Задачу минимизации можно свести к максимизации:

$$\min f(x)=-\max\bigl(-f(x)\bigr).$$

Неравенство со знаком $\geqslant$ преобразуется в неравенство со знаком $\leqslant$ умножением обеих частей на $-1$.

Переменную без ограничения на знак можно представить как

$$x_j=x_j^+-x_j^-, \qquad x_j^+\geqslant 0,\quad x_j^-\geqslant 0.$$

Неравенства можно преобразовать в равенства введением дополнительных неотрицательных переменных. Поэтому различные формы записи задачи линейного программирования эквивалентны друг другу.