3.3. Частные случаи использования графического метода
В рассмотренном в предыдущем вопросе примере множество решений задачи линейного программирования являлось замкнутым многогранником, система ограничений была совместимая и линейно независима, а оптимальное решение единственное. Однако на практике имеют место случаи, при которых эти условия не выполняются.
При применении графического метода решения задач линейного программирования возможны следующие частные случаи:
1 . Целевая функция достигает максимального (минимального) значения не в одной точке, а на некотором отрезке (например AB), который является границей многогранника области допустимых решений и расположен параллельно к линиям уровня целевой функции (рис. 3.3а).
2 . Задача не имеет оптимальных планов (рис. 3.2б – значение целевой функции равно бесконечности; рис. 3.2г – система ограничений задачи несовместима).
3. Задача имеет оптимальный план при неограниченной (незамкнутой) области допустимых решений (рис. 3.2в).
Рис. 3.3. Графическое представление некоторых частных случаев в задачах линейной оптимизации
3.4. Общий алгоритм графического метода
Составим алгоритм графического метода решения задач линейных оптимизационных задач:
Этап 1. Строим прямые линии, уравнения которых получаем заменой в ограничениях-неравенствах знаков неравенств на знаки равенств.
Этап 2. Определяем полуплоскости, соответствующие заданным ограничениям.
Этап 3. Находим многогранник области допустимых решений как область, где пересекаются все полу плоскости.
Примечание.Если такая область не существует, значит данная система ограничений несовместима и задача не имеет решений.
Этап
4. Строим вектор нормали
,
задающий направление роста значений
целевой функции.
Этап
5. Строим линию уровня – прямую
(т.е.
,
перпендикулярной (под прямым углом) к
вектору
и проходящей
через начало координат.
Этап
6. Перемещаем линию уровня в направлении
вектора
для задачи
максимизации целевой функции или в
противоположном направлении для задачи
минимизации. Последняя вершина
многогранник области допустимых решений
через которую пройдет линия уровня и
будет точкой, в которой целевая функция
достигает экстремального значения.
Примечание 1.В случае поиска максимума, если область
допустимых решений не является замкнутым
пространством точек в направлении
вектора
значение целевой функции будет
равно бесконечности.
Примечание 2.В случае поиска минимума, если область
допустимых решений не является замкнутым
пространством точек в направлении
противоположному вектору
значение целевой функции будет
равно минус бесконечности.
Этап 7. Определяем координаты вершины многогранника области допустимых решений, определенной на предыдущем этапе, путем решения системы уравнений, на пересечении которых она находится.
Этап 8. Вычисляем экстремальное значение целевой функции в оптимальной точке.
Глава 4. Симплексный метод ршения задач линейной оптимизации
4.1. Каноническая форма задачи линейного программирования
4.2. Пример использования симплекс-метода в общем случае
4.3. Частные случаи использования симплекс-метода