Като цяло, при градиентни методи разбират методи, при които посоката на движение на точката на оптимална функция съвпада с посоката на наклона на функцията. Градиент методи са приблизителни методи за решаване на нелинейни програмни проблеми. Като цяло, те осигуряват оптимални решения чрез безкраен процес на последователни приближения. Въпреки това, в някои случаи, процесът може да приключи след определен брой повторения.
Градиент методи могат да се прилагат и да е нелинейна програмен проблем, в резултат на което само местни, а не глобален екстремум. Поради това, те са по-ефективни при решаването на проблемите изпъкнало програмиране, където всеки местен екстремум е едновременно глобален.
Общият състав на проблема, съответства на (5.1) и (5.2). Въпреки това, без загуба на общоприложимост, тя може да се превърне формата
Математически метод стратегия градиент е както следва. Избира произволна точка осъществимо. За да се придвижват повторения, произтичащи от точка до точка, в посока, определена. до достатъчно малък лъч бе допустим регион. Това е следващата точка на итеративния процес се определя от формулата:
Методите за разлика градиент се състои в метод за определяне на посоката и параметър.
1. Ако - вътрешна точка на домейна на изпълними решения, а след това
е наклона на функцията на точка. Стратегии, изразена чрез връзката (5.57) определя движение с променлива стъпка, като стойността на стъпка зависи от стойността на градиент. Тъй като градиент намалява близо до оптималната стойност, тогава някои области ще бъдат малки стъпки, които се простират време за търсене. От този недостатък може да се премахне с помощта на стратегия градиент с постоянна стъпка. В този случай, векторът градиент се заменя с указанията на векторни градиент:
2. не принадлежи към зоната за изпълнение. Това може да се случи, ако точката се движи по посока на най-голямото увеличение на функцията аз -s нарушил ограничение (5.54). Като наказание за нарушаването на аз-ти граници фактор са Ri и vspomogatelnuyu обективна функция.
Ако целта функция, за да се разбере приходи на предприятието, не е нищо друго, освен доходите на санкции на предприятие минус.
В най-простия случай Ri е избран, както следва:
Броят на R трябва да бъде достатъчно голям, за да направи точка да се движи в допустимата зона. Посоката на движение на точка в този случай се дава с вектора
Недостатъкът на тази стратегия е, че точността на изчислението зависи от избора на R. Ако това не е изборът на броя на R повтарящ се процес ще се характеризира с резки колебания в точката, в близост до границата.
Този недостатък може да се избегне, ако приемем, че глобата трябва да бъде по-малък, толкова по-малко смущение може да се случи, това е, че е препоръчително да се предположи, че
1) Задаване на броя на постоянно на всички повторения. Колкото по-ниска броя. по-точно изчисление. Съответно се увеличава търсенето време и оптимално;
2) Параметър избрани при всеки етап на условията мин # 955; " # 955; "> където # 955; "- стойността, при която лъча + # 955; (К) S (к) пресича ТСС; # 955; "- е валидна стойност # 955;. където функция е (+ # 955; (к) S (к)) достига максимум на лъча. Тази стратегия позволява да бъде най-DHS и оптимизиране на броя на повторенията. Въпреки това, когато нелинейни и нелинейни ограничения изчисление обективна функция # 955; " # 955; "може да отнеме доста време.
За илюстрация на метода на градиент избираме следната стратегия: # 955; - Броят на редовно; стойността на глобата е пропорционална на нарушението на ограничение; посока съвпада с посоката на точка на градиента. Този така наречен метод градиент Arrow-Hurwitz. Ако ограниченията на знаците (5.55) не, координатите на новата точка може да се изчисляват в съответствие с (5.56) (5.60) по формулата:
Като се вземат предвид условията на неотрицателност (5.55), изразът (5.62) ще изглежда така:
В изразите (5,62) и (5,63) наказание функция се изчислява съгласно формулата (5.61).
Пример 5.3 е необходимо да се увеличи функция
нека # 955; = 0.1; R1 (0) = 2; x1 (0) = 3; x2 (0) = 1.5, което е, ние избираме отправна точка, очевидно не принадлежи на зоната за изпълнение.
Уравнения (5.62) са както следва:
Уравнения (5.61) са както следва:
Второ повторение: Въпросът е вече вътре в допустимия регион, обаче, е фактор. макар и по-малък. но и различен от 0 и границата продължава да "избута" движеща се точка във вътрешността на допустимата площ (този етап все още е на "опасно разстояние" от границата):
По същия начин, този процес може да продължи и нататък. С увеличаването на броя на повторенията момента, в който състоянието на изпъкналост на целевата функция е ангажиран с тази задача.
Списъкът на препоръчителна четене
1. AV Kuznetsov, II студено. Математическо програмиране. - Минск: "High School". 984-221.
4. Zaichenko YP Изследване на операциите: Proc. надбавка за студенти. - 2-ро издание. Ревизираната. и вътр. - Киев: Vishcha училище. Основната издателство, 1979. 392 стр.
5. IA Akulich. Математически примери за програмиране и проблеми. - М., "High School", 1986.- 319 с.
9. S. Gass. Линейно програмиране. - М., "Наука", 1961.-303 с.
10. Sakovich VA Изследване на операциите (детерминирани методи и модели): справочник. - Mn. Вашият. седм. 1984-256s.
11. Таха З. Въведение в Изследване на операциите: в две книги. Kn.1,2 Пере. от английски език. - Мир 1985.
Свързани статии