АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Типовой пример

Читайте также:
  1. I. 1.1. Пример разработки модели задачи технического контроля
  2. IV. ТИПОВОЙ ПРИМЕР РАСЧЕТОВ.
  3. X. примерный перечень вопросов к итоговой аттестации
  4. Административно- типовой период (1956г.)
  5. Б2. Пример №2
  6. БОРЬБА СО ЗЛОМ, КАК ТИПОВОЙ ПРИЕМ ЕГО УТВЕРЖДЕНИЯ
  7. Буду на работе с драконом примерно до 21:00.
  8. Булевы функции. Способы задания. Примеры.
  9. В нашем примере каждый доллар первоначального депозита обеспечил 5 дол. средств на банковских счетах.
  10. В некоторых странах, например в США, президента заменяет вице-
  11. В примере
  12. В странах Востока (на примере Индии и Китая)

Решить задачу выпуклого программирования


Здесь 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, т.е. найдем положительные кор­ни уравнений


 


=12;

наша задача запишется так. max{Л -Л 16*

Дальнейший процесс решения приведен в таблице.

 

  С       --------- _ j      
  С р R А, Аг Аз Аа As Аь t
              -1      
    At         -1      
          -1        
    As             -1  
    Аз         -1      
                     

Итак, задача решена за две итерации симплекс-метода и най­ден ее оптимальный план 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
при ограничениях ft(X) = x, +x2'<5; /2(Х)=0,5х22 <4,5;
0<х, <3,5; 0<х2<4,5.

5. Найти минимум функции /0 (Z) = х,2 + 4х2 - 10х, - 16х2 + 41
при ограничениях fl{X) = x'-4x] + х2 <1; /2(Х) = х,2 -4х, -
-Зх2<-3;0<х, <3,5;0<х2<4.

6. Найти минимум функции /0 (X) = х2 + 4х2 - 8х, -16х2 + 32
при ограничениях / (X) = -х, + х2 < 1; /2 (Х)= 2х] - 4х, - х2 < -1;
0<х, <3;0<х2<3.

7. Найти минимум функции /0 (X) = х\ + 9х22 - 10х, - 36х2 + 61
при ограничениях f\X) = x] -4x, +4х2<12; /2р) = Зх12 -7х2 <
<27;0<х, <3,5;0<х2<3,5.

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м минимизи­рующей последовательности Определяется из соотношения

(3.23)

f(XM) = mm {/[¥') | YJeR, 1 <j < s},

т.е. рабочий шаг выполняется в направлении наилучшей про­бы. Все остальные операции - те же, что и в предыдущем алго­ритме.

Величины 5 > 1 и а > 0 являются параметрами данного алгоритма, выбором которых можно улучшить его сходимость.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.009 сек.)