Основные шаги графического метода

1. Составляется задача линейного программирования в общем виде.

2. От ограничений - неравенств переходят к ограничениям - равенствам.

3. Строят графики прямых, соответствующих полученным уравнениям.

4. Выделяют полуплоскости, удовлетворяющие каждому неравенству-ограничению, и общую часть (пересечение) полуплоскостей, удовлетворяющую всем неравенствам системы, то есть область (многоугольник) допустимых решений (ОДР).

5. Строят прямую, соответствующую функции цели Z.

6. Перемещают прямую, соответствующую функции цели, параллельно самой себе до положения, когда прямая и область допустимых решений будут иметь одну общую точку или сторону ОДР. Это будет экстремумом целевой функции.

7. Определяют координаты точки экстремума, решая систему уравнений прямых, пересекающихся в этой точке.

8. Подставляют найденные координаты точки в функцию цели и находят ее оптимальное значение.

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

Задача 1 (Производственная задача)

Предприятие производит продукцию двух видов А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида 16, 8 и 5 кг соответственно, а для единицы изделия В - 4, 7 и 9 кг. Производство обеспечено сырьем каждого вида в количестве 784 кг, 552 кг и 567 кг соответственно. Стоимость единицы изделия А составляет 4 руб., единицы изделия В - 6 руб.

Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость готовой продукции. Решить исходную задачу геометрически.