Глава 6. Экс -математические методы распределения ресурсов 137
Имеется доказательство того, что в случае
оптимальности полу
чанного плана все 5,- становятся равными нулю или меньше нуля.
Включению в базис подлежит та переменная, для которой 8,- пригни
мает наибольшее положительное значение. В нашем примере это:
3"l Г 16"|
+ с4а45-0=-^х -d
+ х. +
5 = Cjflj 5 + с2а25 + с3а3.
10
13 .
56 = х. — - —х0 +— х 2 - — х. (-Л
-0 =
6 10 4 10
10 10 V
' 5
Таким образом, мы приходим к тому же
заключению о небо
ходимости включения в базис переменной Х5, для которой Крите
рий имеет наибольшее положительное значение.
Далее необходимо установить, какая переменная
должна быть
выведена из базиса при введении в него переменной Х5. Чтобы от
светить на этот вопрос, будем рассуждать так.
Очевидно, следует переместиться по стороне АВ
как можно
дальше от точки А, чтобы как можно больше уменьшить целевую
функцию. Стало быть, можно взять в качестве координаты х.,- точки
В ее максимальное возможное значение, допускаемое системой
уравнений (6.5), соответствующей матрице (6.15), т. е. такое, при
котором ни одна из переменных не становится отрицательной.
Можно показать, что это достигается в том
случае, если вывеси
ти из базиса переменную, которой соответствует минимальное по
ложительное значение отношения свободного члена уравнения к
коэффициенту при х5 в соответствующем столбце матрицы (6.15).
Поэтому избирается четвертая строка матрицы и
соответст
вено переменная Х4, подлежащая исключению из базиса.
Теперь необходимо получить в четвертой строке
значение ко
эффициента при новой базисной величине Х5, равного единице, а
все остальные коэффициенты этого столбца обратить в нуль. Для
этого проверяем вычислительную процедуру полного исключения.
Получаем
0 0 0 0
0 1
о о
0 0 0 -
-