Основы исследования операций том 1 - Вагнер Г

11U ГЛАВА 3

при условии

Как правило (хотя вовсе не обязательно), в (5) имеет место неравенство п~> т.

3.4.ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

Вгл. 4 и 5 будет показано, что нахождение решений и количе^- ственныи анализ задач линейного программирования возможны лишь в том случае, если определена алгебраическая структура соответ-

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

Существуют два вида геометрических представлений линейных оптимизационных моделей. Одно из этих представлений реализуется в так называемом пространстве решений. Именно такое представление рассматривается в данном разделе. Другое из них, известное под названием представление в пространстве условий *), для тех, кто только начинает знакомиться с линейным программированием, представляет меньший интерес. Его изложению отведен отдельный (повышенной трудности) разд. 3.6.

Представление в пространстве решений; двумерная задача. Такого рода представление уже встречалось в гл. 1 при рассмотрении проблемы «двух картошек». Желающим освежить в памяти некоторые детали, связанные с упомянутой проблемой, рекомендуется

*) Иногда используется термин «представление в пространстве ограничений».— Прим. перев.

ПРЕДСТАВЛЕНИЯ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ Щ

Эта задача графически представлена на рис. 3.1. Заметим, чтоограничения (2) и (3) изображены графически (прямые линии) как уравнения, полученные заменой фигурирующих в (2) и (3) неравенств на равенства. Соответствующие же неравенства изображены стрелками, направленными в сторону допустимых значений Xi и xz~

Р и с . 3.1. Пространство решений.

Поскольку ни одна из этих переменных не может принимать отрицательных значений, область допустимых значений х\, и х2 ограничена, кроме того, осями координат. Таким образом, многоуголь-

ник ОаЪс содержит в себе область значений х^ нх2, удовлетворяющих всем имеющимся ограничениям.["Множество точек, принадлежащих

области, ограниченной Oabc (вместе с граничными точками), называется множеством решений. Это множество является выпуклым, т. е„ любой отрезок, соединяющий две произвольным образом выбранные точки данного множества, лежит внутри или проходит вдоль границы

Oabc (другими словами, принадлежит упомянутому множеству). Вершины О, а, Ъ и с носят название экстремальных точек — они не могут принадлежать внутренней части ни одного из отрезков, соединяющих две различные точки рассматриваемого множества.!

Параллельные прямые на рис. 3.1 являются графическим изображением различных значений целевой функции. Стрелка, пересекающая эти прямые, направлена в сторону возрастающих значений целевой функции. Оптимальное решение определяется экстремальной точкой Ь, для которой Xi = 15/7, х2 = 8/7, 12^1 -+- 15ж2 = 300/7-

Альтернативные оптимальные решения^ Если в выражении для целевой функции изменить коэффициенты (при этом на рис. 3.1 угол наклона параллельных линий по отношению к оси абсцисс

ное решение, может, естественно, переместиться. Однако всегда существует оптимальное решение, определяемое некоторой экстремальной точкой. Продемонстрируем справедливость этого утверждения на одном конкретном примере. Пусть имеет место некоторое

Р и с. 3.2. Альтернативные оптимальные решения.

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

ных решений. При этом оптимальное значение целевой функции равняется 20.

Неограниченные оптимальные решения. В примере, графически

Легко убедиться графически (рис. 3.4), что данная задача не имеет ни одного допустимого решения.

Заключение. Результаты геометрического рассмотрения приведенных выше задач иллюстративного характера можно резюмировать следующим образом:

1.Если множество решений является непустым, то оно выпукло

иможет быть либо ограниченным, либо неограниченным.

2.Если множество решении является непустым, то оптимальное значение целевой функции может быть либо конечным, либо неогра-

ниченно большим. В случае когда оптимальное значение целевой функции конечно, оно соответствует экстремальной точке.

3.5. ПРЕДСТАВЛЕНИЕ В ПРОСТРАНСТВЕ РЕШЕНИЙ БОЛЬШЕГО ЧИСЛА ИЗМЕРЕНИЙ

В данном разделе мы познакомимся с терминологией, используемой в случае геометрического представления пространства решений

Рассмотрим теперь «-мерное евклидово пространство, т. е. множество точек, каждая из которых задается с помощью п координат (xi, xz, ••• , жп). Поскольку Xj ~^- 0, рассмотрению подлежит только соответствующая область n-мерного евклидова пространства.

Каждому уравнению

3=1

соответствует гиперплоскость, которая делит рассматриваемое га-мер- ное пространство на два полупространства. Переходом от (4) к неравенству (2) при каждом значении i определяется направление, указывающее, какое из двух полупространств содержит точки, удовлетворяющие соответствующему неравенству (2). Пересечение т гиперповерхностей, соответствующих полному набору уравнений (4), определяет множество допустимых решений. В случае когда это множество оказывается непустым, оно является выпуклым и поли-

ПРЕДСТАВЛЕНИЯ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ Ц5

эдральным. При этом грани полиэдра лежат на гиперплоскостях (4), а ребра и вершины — на пересечениях последних. Для простоты предположим, что полученное таким образом выпуклое полиэдральное множество га-мерно.

Целевую функцию можно также представить с помощью гиперплоскости в пространстве решений. Точнее выражаясь, множество всех точек га-мерного евклидова пространства, в которых линейная целевая функция принимает некоторое заданное значение, представляет собой гиперплоскость. Гиперплоскости, соответствующие различным значениям целевой функции, параллельны друг другу. Отсюда следует, что никакой точке, лежащей строго внутри множества решений, не может соответствовать оптимальное решение, так как всегда найдутся точки, которые лежат на гиперплоскостях, соответствующих большим значениям целевой функции. Следовательно, если значение целевой функции для оптимального решения является конечным, то оптимальное решение должно задаваться экстремальной точкой полиэдра, определяющего область допустимых решений. Если же га (га ^ 2) экстремальных точек являются оптимальными, то оптимальными являются также все точки, лежащие на ребрах и гранях, соединяющих эти экстремальные точки.

3.6. ПРЕДСТАВЛЕНИЕ В ПРОСТРАНСТВЕ УСЛОВИЙ

Перейдем теперь к рассмотрению другого возможного геометрического представления задач линейного программирования. Любая линейная модель может быть изображена графически в пг-мерном пространстве условий, где т равно числу ограничений (не считая, условий неотрицательности переменных). Для этого запишем ограничения в виде одного векторного неравенства. Это всегда можно сделать, если учесть, что набор коэффициентов при любой переменной Xj (так же как и набор констант в правых частях ограничений) определяет вектор в тте-мерном пространстве. Рассмотрим множество точек, получаемое перебором всех возможных сумм таких векторов, а также их произведений на произвольные неотрицательные числа. Это множество образует в пространстве условий выпуклый поли-

эдральный конус.

Модель допускает хотя бы одно решение, если вектор, заданный набором чисел, фигурирующих в правых частях ограничений, не выходит за пределы этого конуса. Задача оптимизации может быть сформулирована следующим образом: требуется найти векторы, которые: а) лежат внутри упомянутого конуса; б) дают в сумме вектор, определяемый набором констант, фигурирующих в правых частях ограничений; в) максимизируют (минимизируют) значение целевой функции. Идеи, которые легли в основу данного геометрического представления, иллюстрируются ниже на примерах, рассмотренных в разд. 3.4.

Чтобы сделать набор управляемых переменных модели полным,

X) >0 (j = 1, 2, 3, 4).

За счет переменных х3 и х4 появляются два новых вектора, лежащих вдоль осей координат.

странство условий становится тождественным полному неотрица-

ПРЕДСТАВЛЕНИЯ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ Ц7

тор (12, 10):

и другие комбинации слагаемых: вектор (1, 0), умноженный на некоторое положительное число, с вектором (3, 5) или с вектором (О,1); вектор (4, 2), умноженный на некоторое положительное число, с вектором (О, 1). Легко убедиться, что ни одна из этих комбинаций не может дать в сумме вектор (12, 10).

Альтернативные оптимальные решения. Пусть при тех же ограничениях (2), (3) и (4) требуется

максимизировать 4;ri -|- iOxz,

что приводит к альтернативным оптимальным решениям. Представление модели в пространстве условий выглядит так же, как и в предыдущем случае (рис. 3.5).

Неограниченные оптимальные решения. Рассмотрим снова задачу:

(—0,2, —0,8) сложить с вектором 1,8-(—1, 1), то получим вектор (-2,1):

— 2

Вектор, получаемый в результате операции сложения в этом случае, обозначен на рис. 3.6 буквой Ъ. Существует бесконечное множество комбинаций векторов, коллинеарных векторам (—1, —1), (1, 0),

Р и с . 3.6. Неограниченное оптимальное решение.

(—1, 1), сумма которых равна (—2, .1). При этом чем больше (в рассматриваемой комбинации) множитель при (—1, 1), тем большее значение принимает линейная форма (—2xi -f- Qx2).

Оптимизация. Графики, с помощью которых демонстрировалось представление линейных моделей в пространстве условий, не содержат никакой информации относительно целевой функции, точнее, относительно того, какие векторы следует выбрать, чтобы одновременно удовлетворить имеющимся ограничениям и оптимизировать значение целевой функции. Эту информацию можно представить графически путем введения в рассмотрение дополнительного измерения. Вернемся к задаче, сформулированной с помощью (1) — (4) (см. рис. 3.5). В этом случае третье (дополнительное) измерение возникает за счет присоединения к системе ограничений (2), (3) соот-

в трехмерном пространстве полиэдральный конус. Ограничивающий

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

КОНТРОЛЬНЫЕ УПРАЖНЕНИЯ И УПРАЖНЕНИЯ НА РАЗВИТИЕ ВЫЧИСЛИТЕЛЬНЫХ НАВЫКОВ

1. Объясните смысл следующих терминов:

переход от максимизации к минимизации; эквивалентная система неравенств; остаточная переменная; избыточная переменная;

переменная, значение которой ограничено снизу; каноническая форма;