Практикум по решению линейных задач математического программирования (стр. 4 из 11)
Пример. Для данной задачи линейного программирования найти начальный опорный план (базисное решение).
max 
Решение. Изменим знаки второго и третьего неравенств на противоположные, умножив каждое из них на –1. Система ограничений теперь будет такой:
В каждом ограничении слева добавим положительную переменную
, соответственно запишем канонический вид задачи: max 
.Переменные
базисные. Приравниваем их к правым частям ограничений: 
Все остальные переменные – свободные, приравниваем их к нулю: 
Запишем теперь начальный опорный план
(0; 0; 0; 0; 16; 4; 0).2) Составление симплексных таблиц. Критерий оптимальности.
Симплексный метод удобно применять, используя построение симплексных таблиц. Первая симплексная таблица, соответствующая начальному плану, имеет вид:
| Базис |  | В |  |  | … |  |  |
 |  | … |  | ||||
 |  |  |  |  | … |  | |
 |  |  |  |  | … |  | |
| … | … | … | … | … | … | … | |
 |  |  |  |  | … |  | |
 |  |  |  | … |  | ||
Здесь приняты следующие обозначения.
Столбец «Базис» – это базисные переменные.
Столбец «
» – это коэффициенты при базисных переменных в целевой функции.Столбец «В» – правые части ограничений;
– коэффициенты при переменных в ограничениях; 
– коэффициенты при переменных в целевой функции.Последняя строка в таблице (
) – это проверочная или оценочная строка. 
– значение целевой функции, соответствующее построенному начальному плану. Его находят так: каждый элемент столбца умножают на соответствующий элемент столбца В и произведения складывают, т.е. 
.
– называют оценками или симплексными разностями и находят так: элементы столбца умножают на соответствующие элементы столбца 
, складывают результаты и вычитают .Например,
.Оценки (
) базисных переменных всегда равны нулю.Признак оптимальности опорного плана состоит в следующем:
Опорный план будет оптимальным тогда и только тогда, когда все оценки
для задачи на max и 
для задачи на min.Если критерии оптимальности не выполняются, то нужно перейти к нехудшему опорному плану, т.е. исключить из базиса некоторую переменную и ввести вместо нее новую из числа свободных переменных.
Переменная, которую нужно ввести в базис, соответствует той оценке
, которая не удовлетворяет условию оптимальности. Если таких оценок несколько, то среди них выбирают наибольшую по абсолютной величине и соответствующую ей переменную вводят в базис. Столбец с этой переменной называют разрешающим.Для определения переменной, которую нужно вывести из базиса, поступают так: элементы столбца В делят только на положительные элементы разрешающего столбца и находят симплексные отношения
. Выбирают из 
наименьшее. Оно называет ту переменную, которую нужно ввести в базис. Соответствующая строка таблицы называется разрешающей.На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.
Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере.
Пример. Решить симплексным методом задачу линейного программирования.
max 
Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства.
max 
2) Определяем базисные переменные – это
. 
3) Заполняем первую таблицу | Базис |  | В | 2 | 3 | 0 | 0 | 0 | 0 |  |
 |  |  |  |  |  | ||||
| | 0 | 18 | 1 | 3 | 1 | 0 | 0 | 0 |  |
| | 0 | 16 | 2 | 1 | 0 | 1 | 0 | 0 |  |
| | 0 | 5 | 0 | 1 | 0 | 0 | 1 | 0 |  |
| | 0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | – |
 |  0 |  –2 |   –3 |  0 |  0 |  0 |  0 | ||
Здесь
и не удовлетворяют условию оптимальности, т. к. они меньше нуля. Выбираем среди них большее по модулю. Это . Следовательно, столбец переменной – разрешающий. Значит, в новый базис нужно ввести переменную .