SHPORA.net :: PDA

[ Back ]

Пусть система отграничений задана в виде неравенств.

aijXij  0

Z = или Z = c1X1 + c2X2 + … + cnXn + c0.

Пусть — область решений ЗЛП.

Пусть Z = a, тогда

c1X1 + c2X2 + … + cnXn + c0 = а — уравнение гиперплосткости.

При этом целевая функция принимает в этой гиперплоскости некоторое фиксированное значение а, а (с1, с2, …, сn) проходит к этой плоскости перпендикулярно и показывает направление возрастания целевой функции.

Так как в этой гиперплоскости целевая функция принимает одно и то же значение а, то она (плоскость) называется гиперплоскостью уровня. Данная гиперплоскость разбивает все пространство Rn на два полупространства, при этом в одном из этих полупространств (G’) Z принимает значения большие либо равные а (Z ??0), а в другом G'' — меньшие, либо равные а. (Z ? a).

Если существует точка X*, в которой Z достигает своего максимума то X*G’’, а если минимума — то X*G’.

Для того чтобы решить ЗЛП графическим способом в пространстве Rn необходимо:

Построить множество X — область допустимых решений ЗЛП — которая задана системой неравенств.

Если область не пустая, переходим к поиску оптимального решения:

Строим целевой вектор и двигаем перпендикулярную ему линию уровня по направлению, указывающему либо возрастание, либо убывание функции, находим максимум или минимум.

Возможности графического метода ограничены, так как он позволяет решать лишь сравнительно простые ЗЛП. В частности, наиболее удобно применение метода в двухмерном пространстве. В трехмерном пространстве графический способ идет тяжело, а четырехмерном и далее пространствах — не возможен. Тем не менее, возможно применение способа и для ЗЛП более чем с тремя переменными, что мы и проделывали не раз.