Линейная оптимизация симплекс-методом.

[murzei64]

Вот такая вот задача.
Прошу объяснить мне — правильно ли я её решаю.
Заранее благодарен.

Условие
Решить задачу линейной оптимизации симплекс-методом.

Линейная целевая функция $f(x)$
$f(x) = -2x_{1}-x_{2}+4x_{3}-x_{4}-x_{5} \to \min$ \enqo(1.1)

Линейные ограничения на переменные $x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$, $x_{5}$ следующие:
$\begin{cases} x_{2}+2x_{4}-x_{5}=1;\\ x_{1}-x_{4}-x_{5}=1;\\ 2x_{2}+x_{3}+2x_{5}=4; \end{cases} \enqo(1.2)$

Кроме того, по условию задачи переменные неотрицательны:
$x_{j}\leqslant 0; j=1 ... 5$ \enqo(1.3)

Также задан опорный план:
$x^{(0)} = (1;1;2;0;0) \qquad \enqo(1.4)$

Решение
Проверим данное по условию решение — (1.4) подставим в (1.2):
$\begin{cases} 1+2 \cdot 0-0=1;\\ 1-0-0=1;\\ 2 \cdot 1+2+2 \cdot 0=4; \end{cases}$

Далее. Так как опорный план задан, то полагаем основными переменными $x_{1}$, $x_{2}$ и $x_{3}$, а неосновоными — $x_{4}$ и $x_{5}$. Переменная $x_{1}$ встречается только во втором уравнении с коэффициентом 1, переменная $x_{3}$ - только в третьем с коэффициентом 1. Переменная $x_{2}$ - помимо первого уравнения - где она фигурирует с коэффициентом 1 - также встречается в третьем уравнении.
Вычтем из первого уравнения системы (1.2) третье - умножив его на два:

$\begin{cases} x_{2}+2x_{4}-x_{5}=1;\\ x_{1}-x_{4}-x_{5}=1;\\ 2x_{2}+x_{3}+2x_{5} - 2(x_{2}+2x_{4}-x_{5})=4; \end{cases}$

$\begin{cases} x_{2}+2x_{4}-x_{5}=1;\\ x_{1}-x_{4}-x_{5}=1;\\ 2x_{2}+x_{3}+2x_{5} - 2x_{2}-4x_{4}+2x_{5}=4; \end{cases}$

Заодно переставим местами первое и второе уравнение, и обозначим полученную систему как (2.1):

$\begin{cases} x_{1}-x_{4}-x_{5}=1;\\ x_{2}+2x_{4}-x_{5}=1;\\ x_{3}-4x_{4}+4x_{5}=4; \end{cases} \enqo(2.1)$

Для нахождения оптимального решения составляем симплекс-таблицу:
$ \begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline \text{Базис}\;X_{Bz i}&C_{Bz i}&b& x_{1} & x_{2} &x_{3} &x_{4} &$\color{red}{x_{5}}$&\theta_{i}\\ \hline $\color{blue}{X_{1}}$&$\color{blue}{-2}$&$\color{blue}{1}$&$\color{blue}{1}$&$\color{blue}{0}$&$\color{blue}{0}$&$\color{blue}{-1}$&$\color{green}{-1}$&$\color{blue}{-1 \gets} $\\ \hline $X_{2}$&-1&1&0&1&0&2&$\color{red}{-1}$&-1\\ \hline $X_{3}$&4&4&0&0&1&-4&$\color{red}{4}$&1\\ \hline \multicolumn{2}{|c|}{C_{j}}&0&-2&-1&4&-1&$\color{red}{-1}$&{-}\\ \hline \multicolumn{2}{|c|}{\Delta_{j}}&13&0&0&0&-15&$\color{red}{20 \uparrow}$&{-}\\ \hline \multicolumn{9}{|c|}{\text{Таблица 1. Симплекс-таблица} }\\ \hline \end{tabular} $

Таблицу заполняем следующим образом.
1. В столбец $\text{Базис}\;X_{Bz i}$ записываем базисные переменные - $x_{1}$, $x_{2}$ и $x_{3}$.
2. Каждому уравнению системы (2.1) ставим в соответствие по одной из строк базисной переменной $x_{1}$, $x_{2}$ и $x_{3}$. Уравнению ставится в соответствии та строка, которая подписана встречающейся в уравнении базисной переменной.
3. В столбец $C_{Bz i}$ записываем коэффициенты из целевой функции (1.1), стоящие при соответствующих базисных переменных.
4. Каждую колонку $X_{j}$ отводим одной из переменных. В ячейку на пересечении столбца переменной $X_{j}$ и строки $i$-го уравнения, заносим коэффициент $a_{ij}$ из системы (2.1).
5. На пересечении столбца $b$ и строки $i$-го уравнения заносим свободный член $i$-го уравнения.
6. Строку $C_{j}$ заполняем коэффициентами целевой функции, стоящими в целевой функции возле переменных $x_{j}$

Далее - ищем разрешающий столбец. Для этого вычисляем оценки (иначе называемые симплекс-разницами) $Delta_{j}$. Вычисляем их по формулам (2.2) и (2.3):
$\Delta_{0} = $С_{BZ 1} \cdot b_{1} + С_{BZ 2} \cdot b_{2}+ ... +С_{BZ i} \cdot b_{i} \enqo(2.2)
$\Delta_{j} = $С_{BZ 1} \cdot a_{1j} + С_{BZ 2} \cdot a_{2j}+ ... +С_{BZ i} \cdot a_{ij} \enqo(2.3)

Для оптимального плана выполняется условие:
Все $\Delta_{j}\leqslant 0$ - для задачи на максимизацию.
Все $\Delta_{j}\geqslant 0$ - для задачи на минимизацию.

Если критерий оптимальности не выполняется, то необходимо перейти к другому опорному плану. То есть - исключить из базиса некоторую переменную — и ввести вместо неё другую. Вводить в базис следует ту переменную, для которой оценка не удовлетворяет условию (2.3.8). Если таких переменных несколько, то выбираем ту, для которой оценка имеет наибольшее по модулю значение. Столбец с переменной, вносимый в базис, называется разрешающим.
Переменная, которую будем добавлять в базис — $x_{5}$. Её оценка $\Delta_{5}=20$. В таблице (2.3.1) она отмечена стрелкой, а столбец — красным цветом.
Выбрав переменную, которую будем добавлять в базис, рассчитываем последний столбец — по формуле (2.3.9).
$\theta_{i}= \frac{b_{i}}{a_{ij}} \enqo(2.3.9)$
Где $j$ – номер переменной, которую добавляем в базис. В данном случае $j=5$.
Итак, заполняем последний столбец. Из $\theta_{i}$ выбирают наименьшую. Она соответствует той переменной, которую из базиса необходимо убрать. Строка этой переменной называется разрешающей.

В рассматриваемом случае $\min(\theta_{i})=-1$, но $\theta_{1}=\theta_{2}=-1$. Выбираем любую из них — например, $\theta_{1}$. Соответствующая строка в таблице 2.3.1 отмечена стрелкой и голубым цветом. А на пересечении разрешающего столбца и строки находится разрешающий элемент $a_{РАЗР}=a_{kl}$ (выделен зелёным) - для $k$-й разрешающей строки и $l$-го разрешающего столбца.
Разрешающий элемент — $a_{15}$.
Итак, получаем новый базис - $x_{5}$, $x_{2}$, $x_{3}$.

Составляем новую таблицу — таблица 2.3.2. Вместо базисного элемента $x_{1}$ записываем $x_{5}$. Заполняем новую таблицу следующим образом:
а) На месте разрешающего элемента ставим $1$.
б) Все элементы разрешающего столбца — кроме разрешающего элемента и элемента строки $C_{j}$ - равны $0$.
в) Все элементы разрешающей строки — кроме разрешающего элемента и элемента столбца $C_{BZi}$ — высчитываем поделив старое значение на разрешающий элемент.
г) Значения столбца $C_{BZi}$ переписываем так, чтобы они соответствовали новому базису.
д) Значения строки $C_{j}$ переписываем без изменений.
e) Значения других базисных столбцов оставляем неизменными
ж) Остальные элементы $b_{k}$ и $a_{kl}$ — кроме оценок $\Delta_{j}$ и $\theta_{i}$ - высчитываем по правилу прямоугольника – см. формулы (2.3.10), (2.3.11):
$b_{iNEW} = \frac{b_{i} \cdot a_{kl РАЗР} — b_{k} \cdot a_{il}}{a_{kl РАЗР}} \enqo(2.3.10)$

$a_{ij NEW} = \frac{a_{ij} \cdot a_{kl РАЗР} — a_{kj} \cdot a_{il}}{a_{РАЗР kl}} \enqo(2.3.11)$
Получаем таблицу 2

$ \begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline \text{Базис}\;X_{Bz i}&C_{Bz i}&b& x_{1} & x_{2} &x_{3} &x_{4} &x_{5}&\theta_{i}\\ \hline $X_{5}$&-1&-1&-1&0&0&1&1&{}\\ \hline $X_{2}$&-1&0&-1&1&0&3&0&{}\\ \hline $X_{3}$&4&8&4&0&1&-8&0&{}\\ \hline \multicolumn{2}{|c|}{C_{j}}&0&-2&-1&4&-1&-1&{}\\ \hline \multicolumn{2}{|c|}{\Delta_{j}}&33&20&0&0&-35&0&{}\\ \hline \multicolumn{9}{|c|}{\text{Таблица 2. Симплекс-таблица на втором шаге} }\\ \hline \end{tabular} $

Собственно вопрос
В данном случае получаем максимальное значение симплекс-разницы - $\Delta_{j}$ для переменной $b$:
$\Delta_{0} = 33$
По идее — разрешающий столбец — столбец переменной $b$.

Следует игнорировать этот факт, и добавлять в базис переменную со второй максимальной оценкой — то есть переменную $x_{1}$ - с оценкой $\Delta_{1} = 20$ - соответственно, разрешающим назначать столбец с переменной $x_{1}$? Или таки следует назначить разрешающим столбец с переменной $b$?

Или я допустил ошибку где-то раньше?

[iifat]

просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов)

[murzei64]

В системе (2.1) в третьем уравнении ошибка.
Должно быть:

$x_{3}-4x_{4}+4x_{5}=2;$

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

Короче, поискал — нашёл немного другой способ решения подобных задач (вероятно, первый попавшийся мне был ошибочным).

В ближайшее время оформлю правильное решение, и выложу сюда.

iifat в сообщении #873848 писал(а):

просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов)

Спасибо, изучу материал по ссылке.

[iifat]

murzei64 в сообщении #873859 писал(а):

В системе (2.1) в третьем уравнении ошибка

Не, арифметику проверять — увольте.

murzei64 в сообщении #873859 писал(а):

Но проблема та же оставалась

Какая — та же? На ту же я вам уже ответил: просматриваются коэффициенты кроме столбца свободных членов.

murzei64 в сообщении #873859 писал(а):

изучу материал по ссылке

На всякий случай: ссылку я дал на четвёртый, что ли, результат поиска в гугле. Не имею в виду, что это какой-то особо заслуживающий доверия источник. Кстати, гугл дал на первой же странице несколько онлайновых сервисов — попробуйте, по идее, они распишут всё решение пошагово.