Принцип внешней точки
Итак, поставлена задача ЛП
Z = c1x1 + c2x2 + ... + cnxn
при ограничениях
q1 = a11x1 + ... + a1nxn
... qm = am1x1 + ... + amnxn
и при условии
x1
Если в ограничениях заменить знак "
Таким образом, грани многогранника R формируются на основе множества m действительных и n возможных границ:
q1 & = a11x1 + ... + a1n xn - b1 = 0
...
qm = am1x1 + ... + amnxn - bm = 0 (6.2)
qm+1 = x1 = 0
...
qm+n = xn = 0.
Здесь обозначение qi используется для названия соответствующих плоскостей и ограничений.
Тогда принципиально возможен выбор комбинаций по n уравнений из (6.2) и их совместное решение. Если решение существует, оно не отрицательно и удовлетворяет всем не использованным при этом ограничениям (6.1), то это решение определяет координаты одной из вершин многогранника R. Однако, как говорилось выше, нет гарантированных оценок времени получения первой вершины, а полный перебор Cnm + n систем n уравнений обладает экспоненциальной сложностью.
Локализуем поиск вершины многогранника R, освободившись от некоторых "лишних" уравнений из (6.2).
Установим направление роста целевой функции, записав ее дифференциал:
dZ = c1dx1 + c2dx2 + ... + cndxn.
Сообщив одинаковое положительное приращение dx всем переменным, получим
dZ = (c1 + c2 + ... + cn )dx.
Следовательно, сумма коэффициентов целевой функции (в отличие от более точной оценки с помощью градиента) определяет направление ее роста: если
 |
(6.3) |
Z растет, удаляясь от начала координат, если
 |
(6.4) |
Z растет, приближаясь к началу координат.
Случай
Выберем точку начала координат O (0, 0, ... , 0). Если все ограничения (6.1) в ней выполняются, эта точка является вершиной многогранника R, и наш поиск хотя бы одной вершины может быть успешно закончен.
В противном случае будем считать эту точку внешней точкой, удобной для рассмотрения многогранника R "со стороны".
А именно, выделим множество
выпуклого многогранника R допустимых решений задачи ЛП. Координатные плоскости включаются в рассмотрение, для того чтобы можно было исследовать вершины R, принадлежащие этим плоскостям.
Аналогично, остальные плоскости (грани), для которых в точке O не выполняются ограничения (6.1), дополненные координатными плоскостями, образуют нижнюю поверхность Qнижн многогранника R.
Очевидно, если сумма коэффициентов целевой функции положительна, то есть Z растет, удаляясь от точки O, то решение задачи ЛП следует искать среди вершин многогранника R на его верхней поверхности. В противном случае — на нижней поверхности.
Проследим на приведенном в лекции 4 курса "Архитектура параллельных вычислительных систем" примере рассматриваемые здесь построения. Для этого повторим постановку и дополним графическую интерпретацию представленной там задачи.
Задача формулировалась следующим образом:
Z = 26x + 20y + 21z
при ограничениях
q1 = 2x + 7y - 76z + 222
q2 = -8x + 9y - 8z + 64
q3 = -8x + 13y - 24z +96
q4 = -x - 6y - z + 70
q5 = -2x - 7y - 2z + 90
q6 = 33x + 3y + 22z - 165
и при условии неотрицательности переменных, о чем в дальнейшем можно не упоминать.
Так как сумма коэффициентов целевой функции положительна, то нас будет интересовать верхняя поверхность многогранника R допустимых решений. При x = y = z = 0 справедливы неравенства для q1
,... , q5. Следовательно,
Qверхн = {q1, q2, q3, q4, q5, q7, q8, q9}. (6.6)
На рис. 6.3 3 ребра верхней поверхности выделены. Координаты точек выбраны при построении примера и приведены для контроля. Считаем их неизвестными; их необходимо получить.
Рис. 6.3. Многогранник допустимых решений с выделенными рёбрами
В данном случае мы получили малый выигрыш, исключив из рассмотрения единственную грань с образуемыми ею вершинами. Однако в произвольном случае форма R может быть разнообразной, и подобное сокращение рассматриваемых ограничений, то есть связанных с ними граней, может быть существенным. Да и сейчас мы видим, что число вершин, среди которых необходим поиск, весьма сократилось — до шести отмеченных на рисунке.
