Графический метод решения задач линейного программирования

В этом случае система ограничений должна быть задана только в виде неравенств.

Решение начинается с построения многоугольника допустимых решений, который строится в декартовой системе координат. Стороны этого многоугольника располагаются на прямых, уравнения которых получаются, если в системе неравенств знаки неравенств заменить на точное равенство. Сам многоугольник есть пересечение полуплоскостей, на которые делит плоскость каждая из указанных прямых.

Чтобы определить нужную полуплоскость, подставляют координаты какой- либо точки (чаще всего начало координат) в левую часть неравенства. Если условие неравенства выполняется, то область решения задачи включает выбранную точку , в противном случае , искомая полуплоскость располагается по другую сторону граничной прямой.

Любая точка этого многоугольника, как внутри его, так и по контуру ,будет удовлетворять заданной системе ограничений, т.е имеем бесчисленное множество допустимых решений. Очевидно, оптимальное решение задачи будет в одной из вершин многоугольника допустимых решений.

Чтобы определить оптимальное решение, необходимо:

- построить вектор целевой функции. Его начало лежит в начале координат, а конец определяется коэффициентами целевой функции;

- провести прямую, перпендикулярную вектору и проходящую через начало координат (линию наклона целевой функции);

- переместить линию наклона целевой функции параллельно самой себе в направлении вектора, если требуется найти max, и в противоположном направлении, если требуется найти min, до тех пор, пока она не сместится в область недопустимых значений (пока она не будет пересекать многоугольник) и определить точку оптимума.

- выяснить, на пересечении каких прямых лежит эта точка, составить из них систему уравнений, решить её и найти координаты точки оптимума, а затем подставить их в целевую функцию и вычислить ее оптимальное значение

Рассмотрим порядок решения на конкретном примере:

F=3x₁+2x₂→max при ограничениях:

 

 

 

В нашем примере точкой оптимума будет точка Д. Она образована пересечением прямых (1) и (2) . Из уравнений этих прямых составим систему и решим ее:

х₁ = х₂ =

Таким образом, Х* = ()- оптимальное решение задачи.

F*=3×10/3+2×4/3=12 2/3 – оптимальное значение целевой функции