Программирования

Пусть задача линейного программирования содержит две переменные, и . Графический метод ее решения состоит в следующем.

В системе координат строим многоугольник, который определяется системой ограничений. Целевая линейная функция при фиксированном значении является уравнением прямой , называемой опорной прямой.

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

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

Пример. Решить графическим методом задачу линейного программирования: найти максимальное значение функции при ограничениях

,

;

,.

Решение. В системе координат на плоскости строим прямую по двум точкам с координатами и в первой четверти, так как . Прямая делит плоскость на две полуплоскости, из которых нужно выбрать одну, удовлетворяющую первому неравенству в системе. Для этого возьмем точку и подставим в неравенство. Если неравенство выполняется, то нужно заштриховать ту полуплоскость, в которой находится точка . Аналогично поступают с прямой .

Строим опорную прямую , определяем вершину выхода – точку В.

Находим координаты точки В, для этого решаем систему уравнений:

Найденные координаты точки подставляем в целевую функцию, и определяем максимальное значение:

.

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