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

Пусть область допустимых значений ЗЛП – непустое множество, например, многоугольник (рисунок 1).

Рисунок 1

Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках прямой NM целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

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

Частная производная функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и − скорость возрастания соответственно вдоль осей и . Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции: .

Вектор указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор перпендикулярен к прямым семейства .

Из геометрической интерпретации элементов задачи линейного программирования вытекает следующий порядок ее графического решения.

1. С учетом системы ограничений строим область допустимых решений .

2. Строим вектор наискорейшего возрастания целевой функции – вектор градиентного направления.

3. Проводим произвольную линию уровня (проще всего провести линию , перпендикулярную к вектору ).

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

5. Определяем оптимальный план и экстремальное значение целевой функции .

Дата добавления: 2015-04-24