Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 54


Отметим на рис. 9.5 стрелками, поставленными у опорной прямой, то направление, в котором L'

возрастает. На рис. 9.5 это оказалось направление «направо — вверх», но могло быть и наоборот: все зависит от коэффициентов

. Теперь изобразим опорную прямую и ОДР на одном чертеже (рис. 9.6). Давайте будем мысленно двигать опорную прямую параллельно самой себе в направлении стрелок (возрастания L’) Когда

L’ достигнет максимума? Очевидно, в точке А (крайней точке ОДР в направлении стрелок). В этой точке свободные переменные принимают оптимальные значения

 a из них можно по формулам (9.3) найти и оптимальные значения всех остальных (базисных) переменных
 1). Заметим, что максимум L’ достигается в одной из вершин ОДР, где, по крайней мере, две из базисных переменных (в нашем случае это х3 и х5) обращаются в нуль. Могло бы обращаться в нуль и больше базисных переменных, если бы через точку А проходило более двух прямых хi = 0.

А может ли оказаться, что оптимального решения не существует? Да, может, если в ОДР функция L’ (а значит и L) не ограничена сверху. Пример такого ненормального случая показан на рис. 9.7 (в разумно поставленных задачах обычно такого недоразумения не возникает).

На рис. 9.6 оптимальное решение существовало и было единственным. А сейчас рассмотрим случай, когда

оптимальное решение существует, но не единственно (их бесконечное множество).

1) Если бы стрелки были направлены иначе («налево — вниз»), то крайней точкой ОДР в направлении стрелок была бы точка В.

Это случай, когда максимум L’ достигается не в одной точке А, а на целом отрезке АВ,

параллельном опорной прямой (рис. 9.8). Такой случай встречается на практике, но нас он

не должен волновать. Все равно и в этом случае максимум U достигается в какой-то из вершин ОДР (4 или В —

безразлично), и в поисках оптимального решения можно ограничиться вершинами ОДР.

Итак, мы рассмотрели в геометрической интерпретации случай п - т = k=2 и убедились в следующем: оптимальное решение (если оно существует) всегда достигается в одной из вершин ОДР, в точке, где по крайней мере две из переменных х1, х2,..., хn равны нулю.




Содержание  Назад  Вперед