Метод полного исключения. Табличный симплекс – метод. Геометрическая интерпретация задач линейного программирования

2. Табличный симплекс - метод

Основная идея симплекс-метода состоит в переходе от одного допустимого базисного решения к другому таким образом, что значения целевой функции при этом непрерывно возрастают (для задач максимизации).

Предположим, что ограничения задачи сведены к такому виду, что в матрице А имеется единичная подматрица и все свободные члены положительные. Иными словами, пусть матрица ограничений имеет вид

A1x1+...+Anxn+e1xn+e1xn+1+...+emxn+m=A0=[ai0],

где$$e_1 = \left[ \begin{gathered} 1 \\ 0 \\ \ldots \\ 0 \end{gathered} \right] , . , e_m = \left[ \begin{gathered} 0 \\ 0 \\ \ldots \\ 1 \end{gathered} \right] - \text{единичный базис}, \; a_{i0} \geq 0$$ для всех i = 1, 2,., n.

Применим одну итерацию метода полного исключения к расширенной матрице ограничений Ap=[A1, ..., An, e1, ..., em, A0].

Пусть aij - направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (1.10) получим новые значения свободных членов:$$\begin{align*} a_{i0}^{(k+1)} = a_{i0}^{(k)} - \frac{a_{i0}^{(k)} a_{lj}^{(k)}}{a_{ij}^{(k)}}, l \neq i, \; l=1,2,\ldots,m, \\ a_{i0}^{(k+1)} = \frac{a_{i0}^{(k)}}{a_{ij}^{(k)}}. \end{align*}$$

Исследуем выражения (2.1) и выясним условия, при которых $$a_{l0}^{(k+1)} > 0$$ для всех l, то есть новое базисное решение будет также допустимым.

По предположению $$a_{l0}^{(k)} > 0; l=1,.,m, a_{ij}^{(k)} > 0$$, тогда$$a_{i0}^{(k+1)} = \frac{a_{i0}^{(k)}}{a_{ij}^{(k)}} \geq 0 .$$

Если $$a_{lj}^{(k)} < 0$$, тогда $$a_{l0}^{(k+1)} > 0$$, поскольку $$a_{i0}^{(k)} > 0, \; a_{ij}^{(k)} > 0$$.

Если $$a_{lj}^{(k)} > 0$$, то$$a_{i0}^{(k+1)} = a_{lj}^{(k)} \left( \frac{a_{l0}^{(k)}}{a_{lj}^{(k)}} - \frac{a_{i0}^{(k)}}{a_{ij}^{(k)}} \right),$$ будет больше нуля при всех l=1, 2, ..., m тогда и только тогда, когда$$\frac{a_{i0}^{(k)}}{a_{ij}^{(k)}} = \min_l \left. \left\{ \frac{a_{l0}^{(k)}}{a_{lj}^{(k)}} \right| a_{ij}^{(k)} > 0 \right\} .$$

Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;

б) направляющую строку i выбирают так, чтобы отношение $$\frac{a_{i0}^{(k)}}{a_{ij}^{(k)}}$$ было минимально при условии, что aij>0.

При таком преобразовании в базис вводится вектор Aj и выводится вектор Аi. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов $$\Delta_j$$:$$\Delta_j = \sum_{i \in I_{\delta}} c_i x_{ij} - c_j = a_{0j}, \; j \notin I_{\delta}$$ где $$I-{\delta}$$ - множество индексов базисных векторов; xij - определяют из условия$$\sum_{i \in I_{\delta}} A_i x_{ij} = A_j ,$$

Величины $$\{ \Delta_j \}$$ равны симплекс-разницам для переменных {xj} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец Аj с наибольшей по модулю отрицательной оценкой, то есть$$\Delta_j = a_{0j} = \min_k \{ a_{0k} | a_{0k} < 0 \} .$$

Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 2.1.

Последняя строка таблицы - индексная - служит для определения направляющего столбца. Ее элементы $$\Delta_j$$ определяют по формуле (2.3). Очевидно, для всех базисных векторов {Ai} i=1,.,m оценки $$\Delta_u = a_{u0} = 0$$.

Значение целевой функции a00 определяется из соотношения$$a_00 = \sum_{i=1}^m c_i x_i^{(k)} .$$

В столбце Bx записываем базисные переменные {xi} i= 1, ..., m. Их значения определяются столбиком свободных членов ai0, то есть

Xi=ai0, i=1,2,.,m.

Направляющие строка Ai и столбец Aj указываются стрелками. Если в качестве направляющего элемента выбран aij, то переход от данной симплекс-таблицы к следующей определяется соотношениями (1.8) - (1.10).

Итак, алгоритм решения задачи ЛП табличным симплекс-методом состоит из этапов.

1. Рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.

2. В качестве направляющего столбца выбирают Aj, для которого$$\Delta_j = a_{0k} = \min_k \{ a_{0k} | a_{0k} < 0 \}$$

3. Направляющая строка Aі выбирают из условия$$\frac{a_{i0}^{(k)}}{a_{ij}^{(k)}} = \min_{l \leq r \leq m} \left. \left\{ \frac{a_{r0}^{(k)}}{a_{rj}^{(k)}} \right| a_{rj}^{(k)} > 0 \right\} .$$

4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом aij, для чего используют соотношения (1.8) - (1.10). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой$$a_{00}^{(k+1)} = a_{00}^{(k)} - \frac{a_{i0}^{(k)} a_{0j}^{(k)}}{a_{ij}^{(k)}} , \; a_{0l}^{(k+1)} = a_{0l}^{(k)} - \frac{a_{il}^{(k)} a_{0j}^{(k)}}{a_{ij}^{(k)}} , \; l = 1, 2, \ldots, n .$$ Правильность вычислений контролируют по формулам непосредственного счета:$$a_{00}^{(k+1)} = \sum_{i \in I_{\delta}^{(k+1)}} c_i a_{i0}^{(k+1)} ;$$ $$a_{0l}^{(k+1)} = \sum_{i \in I_{\delta}^{(k+1)}} c_i a_{il}^{(k+1)} -c_l .$$ В столбце Bx новой таблицы заменяют xi на xj, а в столбце С ci на cj.

5. Если все $$a_{0l}^{(k+1)} \geq 0, \quad l=1,.,n$$, то новое базисное решение $$x_i= a_{i0}^{(k+1)}, \quad i \in I_{\delta}^{(k+1)}$$ - оптимально. В противном случае переходят к этапу 2 и выполняют очередную итерацию.

6. Второй, третий и четвертый этапы повторяют до тех пор, пока одна из итераций не закончится одним из двух исходов:

а) все $$a_{0l} \geq 0$$. Это признак (критерий) оптимальности базисного решения последней симплекс-таблицы ;

б) найдется такой $$a_{0j}=\Delta_j < 0$$, что все элементы этого столбца $$a_{rj} \leq 0 , \quad r = 1, ., m$$. Это признак неограниченности целевой функции $$z=\sum_i c_j x_j$$ на множестве допустимых решений задачи.

Назовем некоторые особенности применения табличного симплекс-метода.

Если в качестве начального базиса выбирают базис из свободных переменных, для которых ci=0, то оценки для всех небазисных переменных равны $$\Delta_j = a_{0j} = -c_j$$, а соответствующее значение целевой функции$$a_{00} = \sum_i c_i x_i = 0, \quad i \in I_{\delta}.$$

Отсутствие векторов с отрицательными оценками при решении задач максимизации является признаком оптимальности соответствующего базисного решения.

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

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

3. Геометрическая интерпретация задач линейного программирования

Рассмотрим такой пример:$$\text{максимизировать} \; (4Х_1 + 3Х_2 ) = Z$$ при условиях$$X_1 \leq 4000; \; X_2 \leq 6000; \; X_1 + 2/3X_2 \leq 6000; \; X_1, X_2 \geq 0$$

Каждое из этих неравенств определяет полуплоскости, пересечение которых дает многоугольник, заштрихованый на рис. 4.1. Этот многоугольник (выпуклый многогранник) и представляет собой допустимое множество решений R(x1, x2) задачи ЛП. Теперь рассмотрим целевую функцию

f(x1,x2)=4x1+3x2,

пусть ее значения

f(x1,x2)=12000=Z1.

График уравнения 4х1+3х2=12000 - прямая с отрезками на осях x1=3000; x2=4000.$$\frac{4x_1}{12000} + \frac{3x_2}{12000} = \frac{x_1}{3000} + \frac{x_2}{4000}$$ При f(x1,x2)=24000 получим прямую z2.

Прямая z2 параллельная прямой z1, но расположена выше от нее. Передвигая прямую z вверх параллельно самой себе, приходим к такому ее положению, когда прямая и множество R будут иметь только одну общую точку А.

Очевидно, что точка А (x1=2000; x2=6000) - оптимальное решение, так как она лежит на прямой с максимально возможным значением $$z_{\max}$$. Заметим, что эта точка оказалась крайней точкой множества R.

При векторной форме ограничения задачи ЛП записываются так:$$A_1 x_1 + A_2 x_2 + . + A_n x_n \leq b,$$ где$$A_1 = \left[ \begin{gathered} a_{11} \\ a_{12} \\ \ldots \\ a_{m1} \end{gathered} \right] , \; A_2 = \left[ \begin{gathered} a_{21} \\ a_{22} \\ \ldots \\ a_{m2} \end{gathered} \right] , \; . , \; A_n = \left[ \begin{gathered} a_{21} \\ a_{22} \\ \ldots \\ a_{mn} \end{gathered} \right] .$$

Рассмотрим допустимое множество A1, A2,.,An в пространстве данных векторов. Поскольку в формуле (3.1) $$х_і \geq 0, \; i = 1,2, ..., n$$, то все положительные комбинации векторов A1,A2,.,An образуют конус. Поэтому вопрос о существовании допустимых решений равнозначен вопросу о принадлежности вектора b этому конусу. Поскольку A1,A2,.,An m -мерные векторы (n > m), то среди них всегда обнаружится m линейно-независимых векторов, образующих базис m -мерного пространства и содержащих конус, образованный векторами A1,A2,.,An...

Поэтому справедливо следующее утверждение. Если задача ЛП содержит n переменных и m ограничений, записанных в форме неравенств (n > m), не считая ограничений неотрицательности переменных $$x_i \geq 0$$, то в оптимальное решение входит не более чем m ненулевых компонент вектора x.

Расширенная форма задачи ЛП. Для решения задач ЛП необходимо переходить от ограничений - неравенств к ограничениям в форме уравнений. Для этого в каждое неравенство вводят по одной свободной переменной $$x_{n+1} \geq 0, x_{n+2} \geq 0,.,x_{n+m} \geq 0$$, чтобы превратить его в равенство. В таком виде задачу ЛП называют расширенной и записывают так:$$\begin{multiple} \text{максимизировать}\\ f(x_1, x_2, ., x_n) = c_1 x_1 + c_2 x_2 + \ldots + c_n x_n + 0x_{n+m} \end{multiple}$$ при ограничениях

a11x1+a12x2+.+a1nxn+1xn+1+0xn+2+...+0xn+m=b1;
a21x1+a22x2+.+a2nxn+0xn+1+1xn+2+...+0xn+m=b2;
........................................
am1x1+am2x2+.+amnxn+0xn+1+0xn+2+...+1xn+m=bm ...

В матричной форме эта задача имеет следующий вид:$$\text{максимизировать} \; c^T x$$ при ограничениях$$A^{m \times n} x_1 + E^{m \times m} x_2 = b;$$ где$$E^{m \times m} = \begin{pmatrix} 1 0 \ldots 0 \\ 0 1 \ldots 0 \\ \ldots \ldots \ldots \ldots \\ 0 0 \ldots 1 \end{pmatrix}, \quad x_2 = \begin{pmatrix} x_{n+1} \\ x_{n+2} \\ \ldots \\ x_{n+m} \end{pmatrix}$$

Наконец, векторная форма записи расширенной задачи ЛП:$$\text{максимизировать} \; c^T x$$ при ограничениях$$A_1 x_1 + A_2 x_2 + \ldots + A_n x_n + A_{n+1} x_{n+1} +\ldots+ A_{n+n} x_{n+m} = b.$$

Пусть R и R1 - допустимые множества решений исходной и расширенной задач соответственно. Тогда любой точке допустимого множества решений R1 соответствует единственная точка множества R, и наоборот.

Установим отношение между элементами R и R1:$$\begin{align*} \text{исходная задача} \text{расширенная задача} \\ x_1 + x_2 \leq 500 x_1 + x_2 + x_3 = 500 \end{align*}$$

На рис. 4.2 и 4.3 изображены допустимые множества решений обеих задач. Очевидно, что треугольник ОСА (рис. 4.2) - допустимое множество R - есть проекция допустимого множества R1 (рис.4.3) на подпространство $$x_1 \cup x_2$$.

В общем случае допустимое множество решений исходной задачи R есть проекция допустимого множества решений расширенной задачи R1 на подпространство исходных переменных $$x_1 \cup x_2$$.