Задачи Линейного Программирования Графический Метод

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

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

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

Рассмотрим следующий простой пример решения задачи линейного программирования (ЗЛП) графическим методом.

Математическая модель:

2Х1+3Х2≤60;
3Х1+2Х2≤60;
4Х1+20Х2≤200;
Х1≥0; Х2≥0;
F=40Х1+30Х2→Мах.

Перейдем от неравенств к равенствам:

2Х1+3Х2=60;
3Х1+2Х2=60;
4Х1+20Х2=200.

Это уравнения прямых линий, которые могут быть легко построены по двум точкам:

для первого ограничения –

Х1=0; Х2=20;
Х2=0; Х1=30.

для второго ограничения –

Х1=0; Х2=30;
Х2=0; Х1=20.

для третьего ограничения –

Х1=0; Х2=10;
Х2=0; Х1=50.

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

Линия уровня целевой функции перпендикулярна градиенту.

Графическое решение данной задачи приведено на рисунке 6.1.

Рис. 6.1. Графическое решение задачи

• Линейное Программирование Графический Метод Онлайн
• Линейное Программирование Графический Метод
• Решить Задачу Линейного Программирования Графическим Методом