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




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


Таким образом, мы построили п

прямых: две оси координат {Ox1

и Ox2) и п — 2 прямых х3 =

0, х4 = 0,..., хn = 0. Каждая из них определяет «допустимую» полуплоскость, где может лежать решение. Часть первого координатного угла, принадлежащая одновременно всем этим полуплоскостям, и есть ОДР. На рис. 9.3 показан случай, когда ОДР существует, т. е. система уравнений (9.3) имеет неотрицательные решения, Заметим, что этих решении— бесконечное множество, так как любая пара значений свободных переменных, взятая из ОДР, «годится», а из х1 и х2

могут быть определены и базисные переменные.

Может оказаться, что область допустимых решений не существует, и значит, уравнения (9.3) несовместны в области неотрицательных значений. Такой случай показан на рис. 9.4, где нет области, лежащей одновременно по «нужную» сторону от всех прямых. Значит, ОЗЛП не имеет решения.

Предположим, что область допустимых решений существует, и мы ее построили. Как же теперь найти среди них оптимальное?

Для этого дадим геометрическую интерпретацию условию (9.2)

L => max. Подставив выражения (9.3) в формулу (9.2), выразим L через свободные переменные х1, x2. После приведения подобных членов получим:

L=

,               (9.4)

где

,
 — какие-то коэффициенты,
 — свободный член, которого в первоначальном виде у функции L не было; теперь, при переходе к переменным х1,

х2, он мог и появиться. Однако мы его тут же и отбросим: ведь максимум линейной функции L достигается при тех же значениях х1, х2, что и максимум линейной однородной функции (без свободного члена):

L’ =

.                  (9.5)

Посмотрим, как изобразить геометрически условие L’ =>

шах. Положим сначала L’ = 0, т.е.

 и построим на - плоскости х1Ох2

прямую с таким уравнением; очевидно, он проходит через начало координат (рис. 9.5). Назовем ее «опорной прямой». Если мы будем придавать L’ какие-то значения С1, С2, С3,...,

прямая будет перемещаться параллельно самой себе; при перемещении в одну сторону L’ будет возрастать, в другую — убывать.


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