Радиоэлектронные системы Основы построения и теория. Справочник . Под ред. Я.Д. Ширмана (2007) (1151789), страница 103
Текст из файла (страница 103)
ниже). Прн линейности оптимизируемых Рне. 14.6 б) Утолщенные части окружностей без штриховки и с центром в начале координат соответствуют линиям постоянного уровня функции г(а). Показаны антнградненты г„= -аг !«(а, нормальные этим линиям и орнентнрованные в направлении убывания функции г(а). В отсутствие ограничений минимум функции соответствует началу координат О. Области, допускаемые ограничениями, выделены на рнс. 14.6,а,б внутренней штриховкой и начала координат не включают. В качестве такой области на рнс.
!4.6,а показана круговая область, на рнс. !4.6,б— общая часть двух перекрывающнхся кругов. Минимуму в обоих случаях соответствует точка А области, допускаемой ограничениями я(а), прннадлежа- и г(а) = -г„тк = ~ г а,, г=! (14.19) 4 -1 — 1 4 — ! -2 (! 4.2! ) -а!+4а2 — 4>0, -а! — 2а2 + 8 > О. (14.22) Л!с! =О, Лгсг =О, а! -Л!(а! -2)-Лга! =О, а2-Л!аг-Л2(а2-2) =О, (а, -2) +а, +с, -Ь =О, г г г г а! +(аг — 2) маг — Ь =О. 2 2 2 2 с~=сг=О, агчаг=1!2 221 щая одновременно линии минимального для этой области уровня функции г(а ).На рис. 14.6,а эта линия касается границы области, допускаемой ограничениями, а на рис.
14.6,б проходит через угловую точку А ее границы. 14.5.3. Добавочные переменные в задачах с ограничениями в виде неравенств Ограничения в виде неравенств 8(а ) > 0 удобно заменять модифицированными ограниченияии в виде равенств 8,'(а ) = 8(а ) — с, = О, вводя вещественные добавочные переменные с,. Область, допускаемая ограничением в виде неравенства (площадь на рис. 14.6,а,б), заменяется, по существу, ограничениями меньшей размерности в виде равенств (плотно упакованными линиями), из которых следует отобрать одну или несколько областей (линий). Добавочные переменные с, можно определять так же, как и основные переменные, исходя из экстремума функции Лагранжа, отбрасывая затем решения, в которых с, не являются вещественными. 14.5.4.
Пример аналитической оптимизации при ограничениях в виде неравенств Для аналитической оптимизации выбран случай, графически представленный на рис. 14.6,6. Требуется минимизировать функцию (14.18) в пределах общей части двух кругов одинакового радиуса Ь = г/5 ! 2, описываемых уравнениями (а1 — 2)'+ аг' = Ь' и а ~'+ (аз - 2)' = Ь'.
Ограничения, модифицированные с учетом добавочных переменных, принимают вид 8~'(ц ) = Ь вЂ” (а,— 2) — а, — с, = О, г г яг'(а) =Ь вЂ” аг — (аг — 2) -сг =О. г г г г Соответственно изменяется и функция Лагранжа (! 4.14) Ц а, Л, с„сг) = а, + аз + Л, [Ь вЂ” (ц, — 2) — а — с, ! + г г г г г г + Л,[Ь вЂ” а, — (аг — 2) — сг ). г г Необходимые условия экстремума (!4.15), модифицированные с учетом добавочных переменных, принимают вид дг, дг. дЕ дг. дЕ М дс, дс2 да, да, д2, д22 Это приводит к системе шести уравнений с шестью неизвестными Решение системы уравнений (точка А на рис. 14.6,6) действительно соответствует экстремуму, причем в виде искомого минимума.
Решение (точка В на рис. 14.6,б), не являющееся вещественным, также соответствует экстремуму, но в виде максимума, и по условию задачи отбрасывается. О других приложениях метода добавочных переменных см. разд. 14.6.2 и 18.! 3.3. 14.6. Элементы линейного программирования К области линейного программирования относят задачи, в которых и целевая функция, и ограничения описываются линейными зависимостями. Будем пользоваться следующими обозначениями; ° переменные он где ! = 1, 2, ..., пг (до разд. 14.6.4 переменные считаем неотрицательными а, > 0); ° вектор переменных а = [12,[[ ° целевая функция потерь ° линейные отРаничениЯ 8г(гх) > О, где г' = 1, 2, ..., и; ° вектор ограничений 8(а) = [[8(ст)[[ или 8(,)=С( )+!г( )= ~'О,а +Ь, .
(!420) Здесь г„=[[~ '[[ — т-мерный вектор-антитрадиент целевой функции потерь; О = [[тг,[[ — матрица ограничений основных переменных размера и н ш; )г = (~Ь,)~ — и-мерный вектор. 14.6.1. Графическое пояснение задач линейного программирования Пояснение проводится при следующем выборе век- торно-матричных параметров ограничений В скалярной форме ограничения определяются тогда неравенствами 4а! -аг — 4 > О, Области, допускаемые ограничениями (14.22), легко поясняется графически, поскольку число скалярных переменных и = 2.
На рис. !4.7 прямые, ограничивающие эти области, выделены штриховкой. Уравнения ограничивающих прямых определяются после перехода в (14.22) к равенствам (уравнениям). Координаты угловых точек (вершин) находятся при этом путем совместного решения попарно взятых уравнений. На рис. !4.7 они развиваются для регулярного отучая оптимизации. Минимизируется функция г(аьа,) =а~+от (14.23) в области, допускаемой ограничениями. Утолщением выделены линии уровня.
Нормально к одной из них Рнс. 14.8 -а! +4а2 -а4 -4 = О, (14.24) -а! -2а2 -аз +8 = О. Система скалярных ограничений в виде равенств может бьггь заменена матричным ограничением Оса+ в =О, 222 оэ проведен вектор-антигра- 4 диент г„= -дг/'са, ори- ентированный в направз ленин убывания функции г(аьаз) Перемещая ли- 2 нню уровня в направлении антиградиента, можно достичь угловой точки (вершины), в данном случае точки а~ = аг = 4/3, в которой н достигается минимум Рнс.
14.7 г,„= (а1 + аз),„= 8/3. На рис. 14.8 поясняется одна из возможных аномалий описанной процедуры. В данном случае минимизируется другая функция г(аьаз) = -сс~+ 4аз в области, допускаемой теми же ограничениями. Минимум достигается не только в одной угловой точке, но и на отрезке прямой, соединяющей две угловые точки.
На рис. 14.9 поясняется еще одна возможная аномалия. В области, допускаемой ограничеРне. 14.9 пнями, минимизируется функция г(а,,аз) = -а, — Заз Однако здесь выпало одно из ограничений, а анти- градиент функции направлен в сторону от единственной угловой точки. Поэтому минимум не достигается ни в одной из точек с конечными координатами. 14.б.2.
Добавочные переменные, опорные решения, метод их полково перебора Введение добавочных переменных по числу ограничений позволяет, как н в разд. !4.5, переходить от ограничений-неравенств к ограничениям-равенствам. На добавочные переменные, как и на основные, накладывают условие неотрицательности. Пример введения добавочных переменных. Продолжим использование иллюстративных данных (14.2!).
По числу ограничений введем добавочные переменные аз й О, а4 й О, а, й О. Это позволяет от системы скалярных ограничений в виде неравенств (1422) перейти к системе скалярных ограничениям в виде равенств 4а! -а2 -аэ -4 = О, в котором матрица Ов имеет размерность пх/г, где и— число скалярных ограничений, а /г = т+ и — общее число переменных с учетом добавочных. Для иллюстративного примера (14.21) 4 -1 -1 0 -140!0 -! -2 0 0 -1 Опорные решения и метод полного их перебора.
Как было выяснено, регулярное решение задачи (14.22) свелось к определению координат одной из угловых точек (вершин). Целевая функция потерь (!4.19) и ее антиградиент г„определяют затем вершину, на которую выпадет экстремум. В методе полного перебора вначале отыскивают только опорные решения (вершины, угловые точки, опорные азины), для которых можно ожидать экстремума. Их строят, приравнивая к нулю /г — п = т поочередно выбранных переменных (включая добавочные переменные). Приравниваемые нулю переменные называются небазисными переменными.
Оставшиеся и переменных, называемые базисными (базисом) переменными, определяются из системы п линейных уравнений с и неизвестными и допускаются в состав опорного решения после проверки на отсутствие аномалий и неотрицательность. Так, выбирая в рассматриваемом иллюстрационном примере аз, аз в качестве небазисных переменных, можно прийти к базису аь а,, а4. Полагая аз = аз = О, от уравнения (14.23) переходим к системе базисных уравнений 4а! - 2-4=0, -а! + 4а2 -а4 -4 = О, (14.25) -а ! -2а2 + 8 = О. Опорное решение 16 28 20 а! = —, а2 = —,а4 = —,аз = а; = 0 (14 26) 9 9 3 позволяет найти значение минимизируемой функции, в частности для функции (14.23) находим (14.27) г(аьа,) =а, +аз=44/9.
Перебирая полностью все опорные решения, для каждого из них можно найти значение минимизируемой функции г(а). Это позволяет, в отсутствие аномалий, найти оптимальное опорное решение в виде глобального минимума г,„. 14.б.З. Симплекс-метод (метод последоеателъноао улучшения решений) Отыскание и сопоставление всех без исключения опорных решений сложно в большинстве применений. Поэтому часто ограничиваются отысканием всего одного опорного решения, с тем чтобы перейти затем к лучшему опорному решению.
Последнее соответствует в общем случае произвольному выбору вершины многогранника ограничений и переходу от нее к некоторой другой вершине с меньшим значением минимизируемой функции. Далее можно снова перейти к еще более лучшему решению и т.д. В этом и состоит метод последовательного улучшения решений — симплекс-метод линейного программирования. Поясним, как именно следует улучшать решения и когда следует остановиться. За основу возьмем иллюстращюнный пример, рассмотренный с помощью соотношений (14.21)-(! 4.27) и рис. 14.7. Как и в методе полного перебора, в симплекс— методе вводят добавочные переменные, выбирают базисные и небазисные переменные, сопоставляют соответствующие этому выбору решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
