|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Типовой примерРешить задачу выпуклого программирования Здесь 5=(s]Vs2) - искомый вектор; о-вспомогательная переменная; fo (X°),fx (Х°)- градиенты соответствующих функций в точке А"°,т.е. векторы /о'(дг°) = (2х, -10; 2л, -б)|д.0 = (-6;-6); Итак, получили задачу в виде: max{a|-6i, -6s2 +a<0; -s2+g<0;s2 >0;5, <1;.v2 <l}. Решим ее симплекс-методом. Вначале с целью уменьшения числа строк последующей симплекс-таблицы перейдем к новым переменным по формулам: l чи к канонической форме введем Определим длину шага а в этом направлении. Для этого найдем вначале то значение а', при котором луч Да) пересекает границу допустимой области R, т.е. найдем положительные корни уравнений
наша задача запишется так. max{Л -Л 16* Дальнейший процесс решения приведен в таблице.
Итак, задача решена за две итерации симплекс-метода и найден ее оптимальный план Y'=(0; 0; 1; 0; 11; 0), из которого получаем у] -0,у2= 0. Тогда значения компонентов вектора, указывающего наилучшее подходящее направление, вычисляются так: Таким образом, в результате решения задачи выбора подходящего направления в точке Х°=(2; 0) найден вектор 5°= (1;1). тора "°СТРОИМ луч' исх°Дятий из точки Г по направлению век- а именно, уравнений (2 + а)2-4(2 + а)-а + 4 = 0; -(2 + а)+2а-1 = 0; 2 + а = 3; 0 + а = 2 или а2-а = 0;а-3 = 0;2 + а = 3;а = 2. Отсюда найдутся корни а, = 0; а, = 1; а3 = 3; а4 = 1; а5 = 2. Таким образом, величина a' =min{l;3;l;2} =1. Далее, опре- делим значение а", при котором функция /„(^(а)) достигает минимума по а. Для этого приравняем к нулю производную этой функции по а и найдем корень полученного уравнения: 2(2 + a-5) + 2(a-3) = 0. Отсюда получим а" = 3. Следовательно, искомое значение длины шага a0 =min{a', a"} = mm {l;3} =1. Завершая итерацию, находим новую точку 1 Первая итерация полностью выполнена. Задания для лабораторной работы Решить задачи выпуклого программирования: 1. Найти минимум функции fo(X) = xf+x:-4xt-2x2+5 при ограничениях J\(X) = -xi +2х2 <1; f1(X)=0,25xl +x2 _, 0<х, <0,5; 0<х,<1. 2 Найти минимум функции /0 (X) - *, 2 Wj^-2x2-12x, +9х2<27;. при ограничениях f№)-lx\ ' -16*2-80<0; 0<x,<4,5;0<x2<4. ' 3 Найти минимум функции /0 (X) = *,2 + х22 - Их, - 4х2 + 53 при ограничениях /(*) = tf +25х2 <125; /2(Х)=х,2 -2х, --4х2<3; 0<х, <4; 0<х2<5. 4. Найти минимум функции fo(X)--=xt +9x2 -10x, -18x2 +34 5. Найти минимум функции /0 (Z) = х,2 + 4х2 - 10х, - 16х2 + 41 6. Найти минимум функции /0 (X) = х2 + 4х2 - 8х, -16х2 + 32 7. Найти минимум функции /0 (X) = х\ + 9х22 - 10х, - 36х2 + 61 3.3. Метод случайного поиска Рассмотрим задачу условной оптимизации =R), (3.18) допустимая область. Решить >вии неноепыинпй дифференцируемое™ фун-_>афных функций или одним ер, методом условного градиен- та или методом проекции градиента. Однако на практике когда определение градиента функции/С*) затруднительно или велика размерность задачи («и т - большие числа), предпочтение стда-ется методу случайного поиска. Под названием метода случайного поиска объединяется большая группа поисковых методов, в которых для решения задачи (3.18) строится минимизирующая последовательность {X*} из Е" по правилу *W = **+a£\* = 0,l,2>..., (3.i9) где ак > 0 - величина шага в случайном направлении £*; £ = (si. • • •' \„) - какая-либо реализация л-мерного случайного вектора Е, с известным законом распределения. Рекомендуется в качестве координат ^ случайного вектора £, выбирать независимые случайные величины, распределенные равномерно на отрезке Н;1]. Таким образом, метод случайного поиска предполагает наличие датчика случайных чисел, обращаясь к которому можно получить реализацию случайного вектора \ с заданным законом распределения. Изучим основные, наиболее употребительные варианты ме-' тода случайного поиска минимума функции f{X) на множестве RczE". 3.3.1. Поиск с возвратом при неудачном шаге Этот алгоритм является простейшей реализацией метода случайного поиска. Смысл его заключается в следующем. Пусть задано некоторое начальное приближение X eR. Допустим, что нам уже известна точка Jf4e/U*0. С помощью датчика случайных чисел получим какую-либо реализацию случайного вектора £,к и в этом направлении по правилу (3.19) найдем точ^ку где a > 0 - некоторое заданное начальное значение шага Полученная точка X в общем случае может не удовлетворять ограни-
—Гу» rZxl Формуле (,20> „р„ г. „лоЦ1«ю процедуру дробления шага повто-новом значении а. Описанную процедуру af рять до тех пор, пока не выполнится условие XeR. Если же э гого добиться не удается вплоть до малого значения ак< в, то выбранное случайное направление %к следует считать неудачным. Также неудачным считается шаг, если условие XeR выполняется но значение функции при этом не уменьшается, т.е./(А) >) (X У^отт следует возвратиться в исходное состояние, положив X -X и совершить новый шаг во вновь сформированном направлении. Если окажется, что количество неудачных шагов из точки Х\ не приводящих к уменьшению минимизируемой функции f(X), достаточно велико, то «неулучшаемая» точка л" может быть принята в качестве точки минимума функции/(АГ) в R, т.е. критерием прекращения поиска может служить выполнение соотношений ^=Xi+1=...=^+w (3.21) при достаточно большом N. Если сделанный из точки Хк шаг удачен, т.е. если найденная по формуле (3.20) точка XeR и при этом выполняется условие /(A) <f(X), то полученная точка ^принимается за очередную точку минимизирующей последовательности, т.е. полагаем Хкн = X и переходим к выполнению следующего этапа поиска, повторяя описанные операции в новой точке А"*+|. Для улучшения сходимости итерационного процесса рекомендуется уменьшать начальное значение величины шага в каждой итерации по правилу сс^^-сс, 0 < у < 1. В описанном варианте метода случайного поиска величины ос0, р, у являются параметрами алгоритма, удачный выбор которых существенно влияет на его эффективность. некоторое заданное количество s реализаций Ц» вектора t, и вычисляются значения функции {{Х)ъл точках **+<, =!,..,, (3,2) которые принадлежат допустимой области R. Если все эти точки оказываются вне области R, то пробы повторяются с уменьшенным значением а. В качестве очередного (JH-l)-ro приближения выбирается пробная точка, в которой значение функции оказа лось наименьшим. Таким образом, (Ж)-я точка Xм минимизирующей последовательности Определяется из соотношения
f(XM) = mm {/[¥') | YJeR, 1 <j < s}, т.е. рабочий шаг выполняется в направлении наилучшей пробы. Все остальные операции - те же, что и в предыдущем алгоритме. Величины 5 > 1 и а > 0 являются параметрами данного алгоритма, выбором которых можно улучшить его сходимость. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.) |