§ 2. Общая схема метода

2.1. Опишем прежде всего процесс формирования плана. Будем исходить из задачи определяемой условиями (1.8) — (1.11). Рассмотрим некоторое подмножество множества индексов и обозначим через задачу, определяемую условиями (1.8), (1.9), (1.11) и

Будем считать, что значению отвечает пустое

множество Таким образом, представляет собой обычную задачу линейного программирования

Рассмотрим эту задачу Очевидно, что вектор является псевдопланом задачи (в силу неотрицательности всех Соответствующий ему базис описывается единичной матрицей Выберем некоторое для которого и по определенным правилам найдем такой столбец что этим столбцом следовало бы заменить в базисе единичный вектор Но вместо этого к задаче добавляется ограничение в несколько видоизмененной форме — где искусственная переменная. Тем самым совершен переход к задаче определяемой условиями (1.8), (1.9), (1.10), (1.11) и дополнительным ограничением

Ясно, что набор образует псевдоплан задачи единичный вектор в базисе расширенной задачи отвечает переменной Вместо в базис вводятся так что принимает значение 1. Переменная обращающаяся при этом в нуль, не играет уже никакой роли и поэтому в дальнейшей записи может быть опущена.

Благодаря простоте дополнительного ограничения, шаг симплекс-метода здесь сводится к выполнению алгебраического сложения векторов: , (направляющий элемент равен —1). Поэтому пробный план задачи можно записать в виде

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

ограничение Это дает задачу определяемую условиями (1.8), (1.9), (1.10), (1.11) и условием

Как и выше, вводя искусственную переменную и сразу исключая ее из рассмотрения, приходим к пробному плану задачи

Повторяем это до получения неотрицательного вектора

2.2. Очевидно, что неотрицательный вектор является оптимальным планом задачи Разумеется, он не обязан быть оптимальным планом задачи хотя всегда будет планом этой задачи.

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

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

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