Параллельное программирование



              

Принцип внешней точки - часть 2


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

А именно, выделим множество

\{q_{i_j} \}
тех плоскостей в (6.2), которые являются действительными гранями многогранника R и для которых в точке O выполняются ограничения задачи (6.1). Дополним это множество плоскостей n координатными плоскостями. Назовем образованную поверхность верхней поверхностью Qверхн

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

Аналогично, остальные плоскости (грани), для которых в точке O не выполняются ограничения (6.1), дополненные координатными плоскостями, образуют нижнюю поверхность Qнижн многогранника R.

Очевидно, если сумма коэффициентов целевой функции положительна, то есть Z растет, удаляясь от точки O, то решение задачи ЛП следует искать среди вершин многогранника R на его верхней поверхности. В противном случае — на нижней поверхности.

Проследим на приведенном в лекции 4 курса "Архитектура параллельных вычислительных систем" примере рассматриваемые здесь построения. Для этого повторим постановку и дополним графическую интерпретацию представленной там задачи.

Задача формулировалась следующим образом:

Z = 26x + 20y + 21z

max

при ограничениях

q1 = 2x + 7y - 76z + 222

0

q2 = -8x + 9y - 8z + 64

0

q3 = -8x + 13y - 24z +96

0 (6.5)

q4 = -x - 6y - z + 70

0

q5 = -2x - 7y - 2z + 90

0

q6 = 33x + 3y + 22z - 165

0

и при условии неотрицательности переменных, о чем в дальнейшем можно не упоминать.

Так как сумма коэффициентов целевой функции положительна, то нас будет интересовать верхняя поверхность многогранника R допустимых решений. При x = y = z = 0 справедливы неравенства для q1

,... , q5. Следовательно,

Qверхн = {q1, q2, q3, q4, q5, q7, q8, q9}. (6.6)

На рис. 6.3 3 ребра верхней поверхности выделены. Координаты точек выбраны при построении примера и приведены для контроля. Считаем их неизвестными; их необходимо получить.

Многогранник допустимых решений с выделенными рёбрами

Рис. 6.3.  Многогранник допустимых решений с выделенными рёбрами

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




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