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

Пусть требуется найти max решение

Предположим, что система ограничений совместна, тогда любое неравенство определяет полуплоскость с границей , где . В результате на координатной плоскости должен получаться многоугольник.

X₁

В С

А D

n E

X₂

Целевая функция при фиксированных значениях Х₁ и Х₂ обращается в прямую линию. Изобразим эту линию для случая F(x)=0, т.е. проходящую через начало координат. Другим значениям F(x) будут соответствовать прямые, параллельные данной прямой. Прямая, полученная из уравнения целевой функции при равенстве её постоянной величине называется линией уровня. Из аналитической геометрии известно, что координаты при переменных в уравнении прямой n=(c₁, c₂) являются координатами её нормального вектора. Если перемещать линию уровня параллельно её начальному положению в направлении вектора ; то последней точкой a, когда она коснётся области допустимых решений, окажется точка С. Линия уровня, имеющая общие точки с областью допустимых решений таким образом, что область допустимых решений находится в одной полуплоскости относительно этой прямой, называется опорной прямой.

Задача.

X₁

B

F(x) ® max

4 A C

1 D

0 1 2 3 4 5 6 X₂

_{f(x) = 0}

Дата добавления: 2014-01-11