Нелинейного программирования с ограничениями

Известно, что для ЗЛП существует область допустимых решений (ОДР) в виде выпуклого многоугольника или многогранника (в том числе и в гиперпространстве) и оптимальное решение находится в одной из вершин этой области (но никогда – внутри ОДР). Для ЗНП с ограничениями также существует область допустимых решений, но, в отличие от ЗЛП, она не всегда является выпуклой. Если ОДР определена, то нахождение решения задачи сводится к определению такой точки, принадлежащей этой области, через которую проходит гиперповерхность наивысшего (или наинизшего) уровня, описываемая функцией цели . Указанная точка может находиться как на границе ОДР, так и внутри нее. Этими особенностями ЗНП существенно отличаются от ЗЛП.

Процесс нахождения решения ЗНП с ограничениями с использованием геометрической интерпретации включает следующие этапы:

- находят область допустимых решений задачи;

- строят гиперповерхность на основании функции цели ;

- определяют гиперповерхность наивысшего (наинизшего) уровня;

- находят точку ОДР, через которую проходит гиперповерхность и опреде-

ляют для нее значения переменных и функции цели.

З а д а ч а 23. Найти максимальное значение функции

при условиях ,

,

,

,

.

Р е ш е н и е. Так как целевая функция нелинейная, то это ЗНП. Воспользовавшись методами линейного программирования, описанными выше, и тем, что задача имеет всего две переменные, в двухкоординатной системе построим область допустимых решений (рис.14, линии ограничений пронумерованы в порядке их записи в тексте). Это будет многоугольник ОАВС.

Рис.14. К нахождению решения задачи 23

Следуя приведенному выше алгоритму, для нахождения решения задачи нужно определить такую точку многоугольника ОАВС, в которой функция цели примет максимальное значение. С этой целью построим линию уровня

,

где h – некоторая постоянная, задаваемая произвольно.

Проанализируем поведение линии уровня при различных значениях h. Будем исследовать функцию такого вида:

,

при условии .

Это будет парабола со смещенным центром, направленная вверх. Смещение найдем, продифференцировав исследуемую функцию и приравняв производную нулю:

,

откуда .

Вторая производная

говорит о том, что в точке х₁=5 функция имеет минимум. Следовательно, смещение линии уровня, которое должно раскладываться на горизонтальное и вертикальное, будет таким: смещение по горизонтали (т.е. вдоль оси ОХ) будет равно х₁=5=const, а по вертикали (т.е. по оси OY) определится из соотношения

.

Очевидно, что с изменением h будет изменяться и х₂ (т.е. смещение линии уровня). Иначе, парабола при различных значениях h может смещаться вверх или вниз, скользя точкой своего минимума по вертикали NN (рис.14). Если взять любую точку в ОДР, одновременно лежащую на параболе, то она определит значения как переменных х₁, х₂, так и функции цели F=h. Тогда минимальное значение функции цели будет при h=15 (и соответственно F=15) при следующих параметрах: х₁=5; х₂=0. Ниже оси абсцисс параболу смещать нельзя, так как она выйдет из ОДР с нарушением требования неотрицательности параметров.

Если далее увеличивать величину параметра х₂, т.е. перемещать параболу вверх, очевидно увеличение как h, так и соответственно функции цели F. Максимального значения она достигнет в точке D, т.е. когда парабола точкой минимума коснется линии АВ (и при дальнейшем перемещении вообще покинет ОДР). Это и будет точка оптимального решения задачи. Ее координаты: ; . Для нее значение функции цели F^* =29.

Видно, что решение задачи хотя и лежит на границе ОДР (как и в ЗЛП), но не в вершине многоугольника ОАВС (что обязательно для ЗЛП).

З а д а ч а 24. Найти максимальное и минимальное значения функции

при условиях ,

,

,

.

Р е ш е н и е. Областью допустимых решений задачи является треугольник АВС, рис.15.

Полагая значение целевой функции равным некоторому числу h, получаем уравнение линии уровня:

.

Это уравнение окружности с радиусом и с центром в точке Е(4; 3). С увеличением (уменьшением) числа h соответственно увеличиваются (уменьшаются) значения функции F. Однако очевидно, что точка Е (а соответственно h=F=0) – это не решение задачи, так как точка Е не принадлежит ОДР. Проводя из точки Е окружности разных радиусов, видим, что первый

Рис.15. Геометрическая трактовка задачи 24

контакт с ОДР будет иметь окружность с радиусом R₁ и произойдет это касание в точке D. Следовательно, координаты этой точки и будут определять минимальное значение функции цели. Найдем их, заметив, что линия ограничений будет касательной к окружности (линии уровня) в точке D.

Продифференцировав уравнение окружности как неявную функцию переменной х₁, получим

,

откуда .

Теперь перепишем уравнение ограничений

.

Очевидно, что угловой коэффициент этой прямой равен k=10. Тогда можем записать

или .

Добавив уравнение ограничений, получаем систему уравнений

,

.

Ее решением будут координаты точки D, соответственно и ЗНП:

; ; .

Продолжая дальше увеличивать радиус проводимых окружностей (линий уровня), видим, что они начинают пересекать ОДР и этот процесс закончится, когда последняя окружность с радиусом R₂ пройдет через точку С. Дальнейшее увеличение радиуса приведет к нарушению ограничений задачи. Координаты точки С можно определить решением системы уравнений:

,

.

Получаем второе решение ЗНП:

; ; .

З а д а ч а 25. Найти максимальное и минимальное значения функции

при условиях ,

,

,

.

Р е ш е н и е. Областью допустимых решений для сформулированной задачи будет многоугольник ABCDE, рис. 16, а линиями уровня – окружности

с центром в точке К(4; 3) и радиусом .

Рис.16. Геометрическая трактовка задачи 25

Характерно, что в данной задаче центр линий уровня находится внутри ОДР. Очевидно, что функция цели (что одно и то же – величина h) примет минимальное (неотрицательное) решение в точке К, так как именно для нее h=0. Тогда имеем первое решение:

; ; .

Максимальное значение функция цели будет иметь в точке С - наиболее удаленной от центра и в которой будет наблюдаться последний контакт линии уровня с ОДР. Очевидно, координаты этой точки найдем, решив систему уравнений:

,

.

Решение следующее: ; ; .

З а д а ч а 26. Найти минимальное и максимальное значение функции

при условиях ,

,

.

Р е ш е н и е. В отличие от ранее рассмотренных задач видим, что в данном случае функция цели - линейная, а неравенства ограничений – нелинейные. Построим область допустимых решений. Первое неравенство – дуга окружности АВ с центром в начале координат и с радиусом R=5. Второе неравенство геометрически представляет гиперболу вида

,

которая в виде кривой CD совместно с дугой окружности АВ образует ОДР, рис.17.

Рис. 17 Геометрическая трактовка задачи 26

Линия уровня – это прямая, имеющая уравнение . Решения задачи получим, если линию уровня будем параллельно самой себе перемещать в направлении ОДР. Там, где она в первый раз коснется ограничительной линии ОДР, будет находиться точка, определяющая минимум функции цели (т.к. переменные в функции цели имеют плюсовые множители). Там же, где линия уровня выйдет из ОДР, т.е. в точке касания с другой ограничительной линией, будет находиться решение на максимум функции цели. В первом случае это точка Е, во втором случае это точка N.

Для нахождения первого решения продифференцируем уравнение гиперболы как функции в неявном виде и получим:

.

Так как это угловой коэффициент касательной к гиперболе, то действительно равенство:

,

откуда получаем

и соответственно , .

Теперь продифференцируем уравнение окружности и получим:

,

откуда .

Очевидно также, что .

Получаем второе решение: ; ; .

Поиск по сайту: