Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

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

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

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

Рассмотрим алгоритм решения задачи следующего вида: c1x1 c2 x2 max(min)

4.2.1. Построение допустимого множества

Каждое ограничение задачи определяет некоторую полуплоскость (в случае неравенства) или прямую (в случае равенства). Допустимым множеством будет пересечение всех полуплоскостей и прямых, заданных условиями задачи. Таким образом, необходимо выполнить следующую последовательность действий:

а) для каждого i-го ограничения нарисовать прямую,

то определить полуплоскость, задаваемую данным неравенством. Это легко сделать, подставив в него координаты точки, не расположенной на соответствующей прямой. Если неравенство оказывается справедливым, то выбрать полуплоскость, содержащую данную точку, в противном случае - выбрать противоположную полуплоскость;

в) найти пересечение полученных полуплоскостей и прямых.

88

4.2.2. Графическое отыскание решений задачи

Пусть допустимое множество оказалось не пустым.

а) выбрать два произвольных числа d1 и d2 . Пусть для определенности d1 d2 . Нарисовать линии уровня целевой функции, соответствующие выбранным

б) зафиксировать направление увеличения значений целевой функции от прямой с правой частью, равной d2 , к прямой с правой частью, равной d1 ;

в) передвигать прямую c1x1 c2 x2 d параллельно самой

себе по допустимому множеству в обозначенном направлении до получения максимального(минимального)

значения d * ;

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

д) выписать ответ.

При построении допустимого множества могут возникнуть три различные ситуации:

а) допустимое множество пусто. Вывод: задача решений не имеет - нет ни одной допустимой точки;

б) допустимое множество ограничено (является многогранником). В этом случае возможны два различных ответа:

б.1) решение единственно: на графике зафиксирована единственная точка, являющаяся пересечением некоторых прямых. Необходимо выписать соответствующие уравнения прямых и, решив полученную систему уравнений, найти

89

точку - решение задачи.

б.2) решений бесчисленное множество: на графике помечен отрезок прямой, все точки которого обеспечивают максимальное значение целевой функции. Среди этих точек есть вершины многогранника. Координаты вершин отыскиваются аналогично предыдущему случаю

в) допустимое множество не ограничено. Здесь возможны две ситуации, описанные в пункте б); решение ищется аналогично. Кроме этого, возможен случай отсутствия решений из-за неограниченности значений целевой функции на допустимом множестве.

Пример 1. Решить графически следующую задачу линейного программирования:

x1 x2 max x1 2x2 8,

2x1 x2 4, x1 3x2 9,

x1, x2 0.

Следуя приведѐнному алгоритму, строим область допустимых решений. Получим выпуклый многоугольник, представленный на рис. 4.2.1

90

Далее, при параллельном перемещении линии уровня в направлении возрастания целевой функции устанавливаем, что такое перемещение можно производить неограниченно. Следовательно,

целевая функция неограничена сверху, т.е. zmax , а сама

неразрешима. Заметим, что если при тех же исходных данных целевую функцию требовалось бы минимизировать, то получили бы

x1

Рисунок 4.2.3 – Пустое допустимое множество

Поэтому данная задача неразрешима.

92