Пупков К.В. Методы классической и современной теории автоматического управления. Том 2 (2000) (1095389), страница 128
Текст из файла (страница 128)
Далее, движение по границе области д происходит под воздействзием управления и(г), которое вычисляется из условия Р,(х(г),и(г)) = О. Если система имеет второй порядок, то синтез оптимальною управления (см. !5!) существенно упрощается. б78 П нложення ПРИЛОЖЕНИЕ 2. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (ОСНОВНЫЕ ПОЛОЖЕНИЯ) ФОРМУЛИРОВКА ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Задача математического программирования содержит некую целевую функцию, оптимум которой следует определить, и систему равенств и неравенств, описывающих условия-ограничения задачи.
Общая задача математического программирования состоит в определении вектора х* с координатами х,,хз,...,х„, который является решением задачи; оптимизировать 7 (хнхз,...,х„) (П2.1) при ограничениях я, (х,, хз,..., х„) > 0; дз (х,,хз,...,х„) > 0; (П2.2) 8„(х,,хы...,х„) > 0; Ь, (х,,хз,...,х„) = 0; Ьз (хнхз,...,х„) = 0; (П2.3) 6 (х,, хз,..., х„) = О. Используем понятие вектора как упорядоченной совокупности и действительных чисел х =(х,,хз,...,х„). Тогда выражение (П2.1) — (П2.3) можно записать в более компактной форме: оптимизировать 7 (х), прн ограничениях д,(х)>0; 1=!,т; 6 (х)=0; 1=1,р.
Текущие индексы 1 и у пробегают все целочисленные значения от ! соответственно дои ир. Координаты вектора х часто необходимо записывать не в виде строки, а в виде столбца: хз т (х,,хз,...,х„) хп П уложение 2. Математическое п ог амму рвание основные положения) 679 Общая задача математического программирования разбивается на задачи, названия которых определяются видом функций, которые необходимо оптимизировать и которые входят в условия-ограничения, типом переменных задач, алгоритмом решения. Если функции г" (х), я, (х), и (х) в выражениях (П2.1) — (П2.3) линейны, то полученную задачу называют задачей пикейного программирования.
Если хотя бы одна из функций г'(х), я, (х), й (х) нглинейна, то (П2.1) — (П2.3) называют задачей нелинейного программирования. Многие задачи, в свою очередь, разбивают на подмножества. Так, если 7 (х) является квадратичной функцией, а ограничения линейны, то получаем задачу квадратичного программирования (более точно г" (х) должна быть квазиопределенной квадратичной формой). В сепарабвльнам программировании целевая функция /'(х) представляет собой сумму функций, различных для каждой переменной. Условия-ограничения здесь могут быть как линейными, так и нелинейными, но все недиагональные элементы матрицы, состоящей из вторых частных производных любой функции задачи, равны нулю. Если координаты искомого вектора х являются толька целыми числачи, то получаем задачу целочисленного программирования (линейного или нелинейного).
В задачах математического программирования требуется найти так называемый условный экстремум (максимум или минимум) функции при наличии ограничений. Рассмотрим задачу математического программирования, в которой есть только ограничения в виде равенств. Пусть целевая функция задачи является функцией двух переменных; г = Дх) = г'(х,,хз) . Ее аргументы связаны уравнением ф(х,,хз) = О (ограничения в виде неравенств отсутствуют). Если функции г = 7'(х„хз) поставить в соответствие некоторую поверхность, то в данной задаче необходимо найти следующие точки; а) принадлежащие линии пересечения поверхности г=Д(хпхз) и цилиндра с образующей, параллельной оси Ое, и с направляющей р(х,,хз ) = О; б) в которых функция г = 7'(х,,хз) принимает экстремальные значения (рис.
П2.1). Как видно из рис. П2.1, точки условного экстремума А и В не совпадают с наибольшим или наименьшим значением функции г = Дх,,х, ) — с безусловным экстремумом функции г'(хцхз). Если из уравнения связи у(л;,хг) = О можно выразить в явном виде одну переменную через другую, например хз —- у(х,), то г= 7(хпхз)=у~хну(х,)] становится функцией одной переменной х, и ее безусловный экстремум отыскивается традиционными методами (приравниваем первую производную от Г (х,,ц~(х,)~ по х, нУлю). БезУсловный экстРемУм фУнкции 7" ( хна(х, )~ ЯвлЯетсЯ Условным экстремумом для функции Д(хмхз ) при ограничениях д(х,, хг ) = О . Однако выразить в явном виде из условий-ограничений необходимую часть переменных, как правило, не удаегся.
Лагранж предложил метод нахождения условного экстремума функции (метод носит его имя). Пусть требуется решить следующую задачу: минимизировать 7'(х„хз,...,х„) при ограничениях п,(хпхг,...,х„) =О; /=1,р. По условию задачи составляется функция Лагранжа 630 П иложения Г (ХО»2,...,»н) = / (Х,,»2,...,»„) О ~1 Ь, (ХЫ»2,...,»а). зы Здесь Х, — неизвестные постоянные множители, подлежашне определению Гмножители Лагранжа), т.е. требуется найти п неизвестных х,,х,,,.,,хо и р множителей Лагранжа Х,, Х„..., Х р . Рпс.
П2Л. Геометрическая ннгерпретапна л|етода Лагранжа х Рнс. П2.2. Область допустимых значения х, и .с, Для рассматриваемого примера Р(х,,»2) = з (»,,»2)+2ф(хы»2). Точки, в которых возможен экстремум, находятся как решение системы алгебраических уравнений, полученной приравниванием нулю частных производных от функции Лагранжа по искомым переменным ( п уравнений) и включением в эту систел~у р ограничении-равенств. Метод Лагранжа сводит задачу отыскания условного экстремума функции з(х) к задаче отыскания безусловного экстремума функции г (х,Х).
Ограничения-неравенства еше более усложняют задачу. Дело в том, что ограничения-неравенства задают область допустимых значений переменных. Например, пусть требуется оптимизировать некоторую функцию Т(х) при ограничениях Я1(х) =х~ — хз >О, П уложение 2. Математическое п о амму рвание основные положения 681 82(х)=1-х~ -хз 20. 2 2 Область допустимых значений переменных х, и хз в этой задаче есть пересечение области, лежащей «внутри» параболы х! = хз с кругом единичного радиуса, уравне- 2 ние окружности которого имеет вид хз+хг =1 (рис. П2.2). Пересечение цилиндра, направляющей которого является граница полученной области .О, с поверхностью г = у'(х) может давать самые разнообразные варианты. На рис. П2.3, а — в показаны поверхности, полученные в результате пересечения цилиндра, направляющей которого служит граница области допустимых значений переменных х, и хз, и поверхности, соответствующей целевой функции г = 1 (х,,хз) .
На рис. П2.3, а точка М безусловного экстремума функции г = !'(хыхз) является и точкой условного экстремума задачи. На рис. П2.3, б точка М является уже граничной и в ней целевая функция достигает своего наибольшего значения. На рис. П2.3, в точка М не принадлежит области допустимых значений переменных, а целевая функция имеет равные наибольшие значения по линиям АВВ и АКВ (т.е. неясно, что же брать за решение задачи). Эти неоднозначные результаты получены даже в случае, когда поверхность целевой функции г = у (х) достаточно проста и обладает единственным (глобальным) максимумом. Рис. П2.3. Точка экстремума ЯП а — фуннчии /(хихз) и задачи; б — стала граничной, е — не принадлежит области допустимом зночений и и хз Наиболее полные резулыпаты в задачах математического программирования получены для выпуклых целевых функций, когда область допустимых значений является выпуклым множеством.
Множество точек 13 называют выпуклым, если для любых точек М| и Мз, принадлежащих области 13, отрезок М,М2 принадлежит множеству (области) В (рис. П2АЧ а). Другими словами, любая точки ~)чМ~+(1 — й)М21 682 П уложении принадлежит областиОдлллюбого Х, Ой)с<1, идлялюбых точек М) и Мз, принадлежацих области .О.
Причем пересечение конечного числа выпуклых множеств выпукло. На рис. П2.4, б показаны невыпуклые множества. Функцию !'(М) называюпе выпуклой на непустом выпуклом множестве О, если для любых двух точек М~ и М,, принадлежал(их области О, и для любого числа Х, 0 < )с < 1, справедливо неравенство М, Ъ Рвс. П2.4. Выпуклые (л) и вевывуклые (В) области (мвожества) Функцию !'(М) называют строго выпуклой, если для О < Х <1 и М~ е Мз выполни- ется строгое неравенство з ()М1 +(1 )")Мз ) < Хз (М) )+(! )")( (Мз) .
Геометрически выпуклая функция лежит над своими касательными. Примером выпуклой функции является парабола. Сумма выпуклых на множестве О функций есть также выпуклая на 0 функция. Функцию 1(х) называют вогнутой на выпуклом множестве О, если функция -('(х) выпукла на Р. Ограничения я, (х) > 0; ! = 1, т образуеа выпуклое множество 0 (выпуклую область О), если все функции я, (х) вогнуты.
В математическом программировании выделяется важный класс задач — задачи выпуклого программирования: минимизировать ! (х), при ограничениях я, ( х) > 0; ! = 1, т, где ! (х) — выпуклая функция; а все функции д, (х) — вогнуты, т.е, рассматривают выпуклые функции на выпуклых множествах. Задачи выпуклого программирования обладают важным положительным свойством: локальные минимумы целевых функций являются одновременно глобальными (единственными).
Очевидно, что решить подобную задачу проще, чем в случае, когда целевая функция !'(х) и область 0 будут общего вида. П вложение 2. Математическое п о амму рвание основные положения 683 НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ ОПТИМУМА В ЗАДАЧАХ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ В общем случае в задачах математического программирования ставится вопрос об отыскании локального минимума (максимума) целевой функции, т.е, такого значения х, что для значений х, принадлежащих некоторой окрестности этого значения х, выполняются неравенства у'(х ) ~(х) для строгого минимума (максимума) и г'(х )>Г'(х) для нестрогого минимума (максимума).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
