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



              

Принцип внешней точки


Итак, поставлена задача ЛП

Z = c1x1 + c2x2 + ... + cnxn

max

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

q1 = a11x1 + ... + a1nxn

b1 (6.1)

... qm = am1x1 + ... + amnxn

bm

и при условии

x1

0, ... ,xn
0.

Если в ограничениях заменить знак "

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

Таким образом, грани многогранника 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.

Следовательно, сумма коэффициентов целевой функции (в отличие от более точной оценки с помощью градиента) определяет направление ее роста: если

 \begin{equation} \sum\limits_i {c_i } > 0, \end{equation}

(6.3)

Z растет, удаляясь от начала координат, если

 \begin{equation} \sum\limits_i {c_i } < 0, \end{equation}

(6.4)

Z растет, приближаясь к началу координат.

Случай

\sum\limits_i {c_i } = 0
может быть причислен как к (6.3), так и к (6.4).

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


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