Пример 4. Предположим, что недельная продажа ограничена 450 полками

Предположим, что недельная продажа ограничена 450 полками. Тогда должно быть включено дополнительное ограничение x₁+x2≤.450.

В виде уравнения оно записывается как x₁+x₂+x₅=450, где x₅ ≥. 0 – дополнительная переменная.

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

Поэтому уравнение x₁+x₂+x₅=450 после исключения х₁ и x₂ принимает вид

Последняя таблица будет иметь следующий вид (изменения - только вид дополнительного ограничения):

Здесь возникают определенные трудности. В этой канонической форме для базиса х₁, х₂, х₅ целевая функция имеет такой же вид, как оптимальная, однако базис не допустим. Переменная х₅ отрицательна. Существует ли, несмотря на это, способ сохранить результаты проделанной к этому моменту полезной работы? Да, и соответствующая процедура носит название двойственного симплекс-метода.

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

В нашей задаче базисная переменная x₅ отрицательна и является кандидатом на удаление из базиса. Какая переменная должна ее заменить? В строке x₅ таблицы ищется отрицательный ведущий элемент, такой, что при последующих преобразованиях коэффициенты целевой функции будут оставаться положительными.

Посмотрим, как они выполняются в нашей задаче. В строке x₅ имеется только один отрицательный коэффициент – коэффициент при x₃, равный -3/7. Если мы разделим уравнение на -3/7, чтобы включить в базисные переменные переменную x₃ (с коэффициентом 1), то получим уравнение

т. е. значение x₃ станет положительным. Следующим шагом мы должны исключить переменную x₃ из остальных ограничений и из целевой функции. Это достигается простыми симплексными вычислениями результаты, как показано ниже, могут быть сведены в таблицу. Ведущий элемент (отрицательное значение -3/7) отмечен звездочкой.

В конечной таблице приведено оптимальное решение новой задачи:

Поскольку в этом решении x₃ - базисная переменная, имеется избыток сырья, и в результате количество заказанных досок может быть сокращено.