Принцип внешней точки
Итак, поставлена задача ЛП
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, и наш поиск хотя бы одной вершины может быть успешно закончен.
