Графическое решение задач математического программирования
Самыми наглядными методами решения задач математического программирования являются графические, но они приемлемы только для функций двух и иногда трех переменных.
Рассмотрим пример: минимизировать
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55383.png)
при ограничениях
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55384.png)
Таким образом, имеем задачу нелинейного математического программирования. Прежде всего построим по условиям ограничениям допустимую область — множество точек
, удовлетворяющих ограничениям задачи. Ограничение
определяет область
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55388.png)
внутри параболы (рис. 1.9); ограничение
— окружность единичного радиуса с центром в начале координат. Допустимая область
этой задачи — дуга окружности
. Чтобы найти точку, в которой функция
принимает минимальное значение на допустимой области
, построим линии уровня
—штриховые линии. В точке (2.2)
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55393.png)
линии уровня образуют квадраты. Градиент функции направлен в сторону дуги
, и функция
будет иметь минимальное значение в точке касания линии уровня к дуге
. Так как линии уровня отсекают от осей
и
равные отрезки, то координаты точки касания равны
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55397.png)
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55398.png)
Решение задачи:
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55399.png)
Нетрудно видеть, что то же решение будет и в том случае, если вместо взять
. Тогда допустимая область
будет заключена между дугами
и
(см. рис. 1.9). Но минимальное значение функции
в области Сбудет достигнуто в точках
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55404.png)
Рассмотрим второй пример: Пусть в задаче о питании (см. разд. 1.1)
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55405.png)
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55408.png)
Получили задачу линейного программирования: минимизировать
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55407.png)
при ограничениях:
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/03/image-55409.png)
Построим области, определяемые неравенствами в ограничениях задачи (рис. 1.10). Сначала строим прямую по двум точкам: пусть
, тогда
; при
. Нанесем точки (0, 2) и (10, 0) на график и проведем прямую
. Чтобы установить, какая часть плоскости определяется неравенством
подставим в него координаты точки (0, 0). Получим противоречие, т. е. неравенство определяет полуплоскость, не содержащую точку (0, 0). Стрелки на прямой
указывают эту полуплоскость. Аналогично строим области, соответствующие другим неравенствам. Неравенство
можно сразу исключить, так как оно «поглощается» неравенством
. Допустимая область
— заштрихованная выпуклая неограниченная многоугольная область. Чтобы найти оптимальную точку, построим одну из линий уровня целевой функции и ее градиент. Пусть
, т.е.
(штриховая линия), а градиент
имеет координаты (2,3). Так как требуется определить минимальное значение
на области допустимых значений, то перемешаем линию уровня параллельно самой себе в направлении антиградиента до тех пор, пока она будет находиться в допустимой области. Точка «выхода» линии уровня из допустимой области и будет точкой, где
примет минимальное значение:
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-14.png)
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-15.png)
На рис. 1.10 видно, что задачи математического программирования могут не иметь решения либо иметь бесчисленное множество решений. Если бы при тех же ограничениях, какие были заданы в условии задачи, потребовалось максимизировать целевую функцию , то линию уровня пришлось бы перемещать в
![Графическое решение задач математического программирования](https://lfirmal.com/wp-content/uploads/2020/04/image-16.png)
направлении градиента . Очевидно, в этом случае решения не существует — множество
не ограничено.
Теперь заменим целевую функцию задачи. Пусть требуется минимизировать функцию . Очевидно, что линии уровня будут параллельны прямой 2, т. е. линия уровня «выйдет» из допустимой области по отрезку прямой
: все точки отрезка будут являться решениями задачи (бесчисленное множество).
При решении задачи линейного программирования может оказаться, что ограничения противоречивы. Например, если ограничение 4 записать в виде , то это неравенство будет описывать полуплоскость, включающую точку (0, 0), не имеющую общих точек с другими полуплоскостями (с решением неравенств 1, 2, 3). Решения в данном случае не существует.
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны: