Пример решения задачи в специальной форме
Симплекс-методом
Решить задачу, записанную в виде:
Составим симплексную таблицу:
![]() | ![]() | ![]() | |
L | |||
![]() | |||
![]() | ![]() |
Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базиса L=0.
Выбираем ведущий столбец – это столбец, соответствующий переменной . Выбираем ведущую строку. Для этого находим
. Следовательно, ведущая строка соответствует переменной
.
Проводим преобразование симплексной таблицы, вводя переменную в базис и выводя переменную
из базиса. Получим таблицу:
![]() | ![]() | ![]() | |
L | -2 | -2 | |
![]() | ![]() | -1 | |
![]() | ![]() |
Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисе
L= -2.
Ведущий столбец здесь – столбец, соответствующий переменной . Ведущая строка – строка, соответствующая переменной
. После проведения преобразований получим симплексную таблицу:
![]() | ![]() | ![]() | |
L | ![]() | -4/3 | -2/3 |
![]() | 4/3 | 2/3 | -2/3 |
![]() | 5/4 | 1/3 | 2/3 |
Еще одна итерация завершена. Переходим к новой итерации.
Строка целевой функции не содержит положительных значений, значит, соответствующее базисное решение
,
является оптимальным и алгоритм завершает работу.
Пример решения задачи методом искусственного
Базиса
Выделить допустимое базисное решение для задачи ЛП.
Приведем задачу к канонической форме на минимум с неотрицательными правыми частями.
Заметим, что переменные и
можно использовать для введения в исходный базис, поэтому в первую и третью строку ограничений можно не вводить искусственные переменные.
Во вторую строку ограничений вводим искусственную переменную z, потому что в этой строке нет переменной, которую можно взять базисной, не проводя при этом дополнительных преобразований всей системы ограничений.
Полученная вспомогательная задача имеет вид
Приведем задачу к виду (16):
Выпишем соответствующую симплексную таблицу:
B | ![]() | ![]() | ![]() | |
![]() | -1 | |||
![]() | -2 | |||
![]() | -1 | |||
![]() |
Ведущий столбец рекомендуется выбирать не по максимальному положительному элементу строки целевой функции, а так, чтобы из базиса выводилась искусственная базисная переменная (соответствующая ведущая строка должна быть строкой искусственной переменной). Так, выбрав ведущим столбцом столбец переменной , получим ведущую строку – строку с переменной z (выбирая ведущим столбцом
, получили бы ведущую строку
и из базиса выводилась бы переменная
).
Итак, искусственная переменная z выйдет из базиса, а переменная введется в базис.
Симплексная таблица преобразуется к виду
B | ![]() | ![]() | ![]() | |
![]() | -1 | |||
![]() | 11/2 | 1/2 | -1/2 | |
![]() | 5/2 | 5/4 | 1/4 | -1/4 |
![]() | 5/2 | 3/4 | -1/4 | 1/4 |
Так как значение , то полученный базис
является начальным допустимым базисом для исходной задачи ЛП. Чтобы выразить целевую функцию
через небазисные переменные
, подставим значение базисной переменной
в целевую функцию. В результате получим
Тогда исходная задача будет иметь вид специальной формы задачи ЛП:
что и требовалось получить в результате решения вспомогательной задачи.