Графо-аналитический метод решения задач линейного программирования
Геометрическая интерпретация задач линейного программирования даёт возможность наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств. Задачи с двумя переменными всегда можно решить графически. Однако уже в трёхмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трёх, графическое решение невозможно.
Пусть дана задача максимизации целевой функции Z
,
при ограничениях
,
и условии неотрицательности переменных
.
Каждое из ограничений и задаёт на координатной плоскости 
некоторую полуплоскость (рис. 2.1). Полуплоскость – выпуклое множество. Пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи есть выпуклое множество.
Пусть область допустимых решений – непустое множество, например, многоугольник A1A2A3A4A5.
Рис. 2.1. Схема поиска решения задачи
графо-аналитическим методом
Выберем произвольное значение целевой функции Z = Z0. Получим с1х1 + с2х2 = Z0. Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение Z0. Считая в равенстве Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).
|
|
|
Найдём частные производные целевой функции по х1 и х2:
, 
.
Частные производные и функции показывают скорость её возрастания вдоль соответствующих осей. Следовательно, с1 и с2 – скорости возрастания Z вдоль осей O х1 и O х2. Вектор с = (с1, с2) называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:
.
Вектор с = (с1, с2) перпендикулярен к прямым Z = const семейства с1х1 + с2х2 = Z.
Вектор (– с) указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.
Из геометрической интерпретации элементов задачи вытекает общий порядок её графического решения:
1) с учётом системы ограничений строится область допустимых решений;
2) определяется вектор с = (с1, с2) наискорейшего возрастания целевой функции, т. е. вектор градиентного направления;
3) проводится произвольная линия уровня Z = Z0;
4) при решении задачи на максимум линия уровня перемещается Z = Z0 в направлении вектора 
так, чтобы она касалась области допустимых решений в её крайнем положении (крайней точке). В случае решения задачи на минимум линия уровня Z = Z0 перемещается в антиградиентном направлении;
|
|
|
5) определяется оптимальное решение х* = (х1*, х2*) и экстремальное значение целевой функции Z* = z(x*).
Дата добавления: 2018-11-24; просмотров: 491; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!