Графический метод решения ЗЛП. Возможности его применения.
Пусть система отграничений задана в виде неравенств.
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 — область допустимых решений ЗЛП — которая задана системой неравенств.
Если область не пустая, переходим к поиску оптимального решения:
Строим целевой вектор и двигаем перпендикулярную ему линию уровня по направлению, указывающему либо возрастание, либо убывание функции, находим максимум или минимум.
Возможности графического метода ограничены, так как он позволяет решать лишь сравнительно простые ЗЛП. В частности, наиболее удобно применение метода в двухмерном пространстве. В трехмерном пространстве графический способ идет тяжело, а четырехмерном и далее пространствах — не возможен. Тем не менее, возможно применение способа и для ЗЛП более чем с тремя переменными, что мы и проделывали не раз.
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 — область допустимых решений ЗЛП — которая задана системой неравенств.
Если область не пустая, переходим к поиску оптимального решения:
Строим целевой вектор и двигаем перпендикулярную ему линию уровня по направлению, указывающему либо возрастание, либо убывание функции, находим максимум или минимум.
Возможности графического метода ограничены, так как он позволяет решать лишь сравнительно простые ЗЛП. В частности, наиболее удобно применение метода в двухмерном пространстве. В трехмерном пространстве графический способ идет тяжело, а четырехмерном и далее пространствах — не возможен. Тем не менее, возможно применение способа и для ЗЛП более чем с тремя переменными, что мы и проделывали не раз.