Метод на Данциг. Проблем от транспортен тип е частен случай на проблем с линейно програмиране

1. Кои твърдения са неверни? Данциг метод

Отговор: може да се припише на групата на градиента

2. Кои от следните твърдения са верни:

Отговор: Проблем с LP с непоследователна система от ограничения се нарича отворен проблем.

3. Кои от следните методи не са активни

Отговор: златно сечение

4. Кои от следните твърдения са верни:

Отговор: задачата от транспортния тип е частен случай на задачата линейно програмиране

5. Кои от следните твърдения са верни: Метод на най-малките квадрати

Отговор: се свежда до решаване на системата n линейни уравненияпри апроксимиране на резултатите с полиноми от n-ти ред

6. Кои от следните методи не са градиентни

Отговор: симплексен метод (метод на Nelder-Mead)

7. Кои от посочените методи позволяват намирането на глобалния екстремум на полимодална функция

Отговор: сканиране

8. Кои методи от изброените са методи за координатно търсене

Отговор: допирателна

9. Отбележете правилните твърдения

Отговор: простият метод на изброяване не може да се използва за намиране на екстремума според процедурата на Гаус-Зайдел.

10. Посочете вярното твърдение

Отговор: Планът е всеки приемливо решениезадачи

11. Посочете грешното твърдение

Отговор: равнина, съдържаща поне една ъглова точка изпъкнал многостенсе нарича референтна равнина на този полиедър

12. Посочете номерата на верните твърдения

Отговор: проблемите от транспортен тип не могат да бъдат решени по метода на Данциг, тъй като те са свързани с проблеми с дискретно програмиране (1). оригинален планв симплексния метод получаваме равно на нула на всички основни променливи (3)

13. Посочете правилното твърдение?

Отговор: основното решение на задачата LP е изродено, ако поне една от свободните променливи е равна на нула

14. Кое от следните е неправилно:

Отговор: всяка точка на права е изпъкнала линейна комбинация от две точки, през които е начертана тази права.

15. Кое от твърденията по-долу е вярно?

Отговор: Проблемът с пътуващия търговец принадлежи към областта на дискретното програмиране.

16. Кое от следните е вярно:

Отговор: един от основните проблеми на оптимизацията е „проблемът с размерите“

17. Какво не е наред в горните твърдения?

Отговор: ако целевата функция на задачата LP достигне екстремум в няколко точки, тогава тя достига същата стойност във всяка точка, която е изпъкнала линейна комбинация от тези точки.

18. Кое от следните твърдения е невярно?

Отговор: Проблемът с LP може да бъде решен чрез процедурата на подреден преход от един план към друг.

19. Кое от следните е вярно

Отговор: вътре в областта на допустимите решения на задачата LP не може да има екстремум

20. Кое от следните е невярно?

Отговор: За намиране на екстремума на линейна целева функцияизползвайки симплексния метод, е необходимо да се извършат n-m итерации, n е броят на неизвестните на проблема, m е броят на общите ограничения

градиентни методитърсенето на оптималната целева функция се основава на използването на две основни свойствафункционален градиент.

1. Градиентът на функция е вектор, който във всяка точка от областта на дефиницията на функцията
е насочена по нормалата към нивелираната повърхност, минаваща през тази точка.

Градиентни проекции
по координатната ос са равни на частните производни на функцията
за съответните променливи, т.е.

. (2.4)

Градиентните методи включват: метод на релаксация, градиент, най-стръмно спускане и редица други.

Помислете за някои от градиентните методи.

градиентен метод

При този метод спускането се извършва по посока на най-бързото изменение на целевата функция, което естествено ускорява търсенето на оптимума.

Търсенето на оптимума се извършва на два етапа. На първия етап се намират стойностите на частичните производни по отношение на всички независими променливи, които определят посоката на градиента в разглежданата точка. На втория етап се прави стъпка в посока, обратна на посоката на градиента (при търсене на минимума на целевата функция).

Когато се изпълни дадена стъпка, стойностите на всички независими променливи се променят едновременно. Всеки от тях получава увеличение, пропорционално на съответния компонент на градиента по дадената ос.

Формулата на алгоритъма може да изглежда така:

,
. (2.5)

В този случай размерът на стъпката
при постоянна стойност на параметъра h се променя автоматично с промяна на стойността на градиента и намалява, когато се приближи до оптималното.

Друг формулен запис на алгоритъма е:

,
. (2.6)

Този алгоритъм използва нормализиран вектор на градиента, който показва само посоката на най-бързата промяна в целевата функция, но не показва скоростта на промяна в тази посока.

В стратегията за промяна на терена
в този случай се използва, че градиентите
и
се различават по посока. Стъпката на търсене се променя в съответствие с правилото:

(2.7)

където
е ъгълът на завъртане на градиента на k-тата стъпка, определен от израза

,

,
са допустимите граници на ъгъла на завъртане на градиента.

Характерът на търсенето на оптимума в градиентния метод е показан на фиг. 2.1.

Моментът, в който търсенето приключва, може да бъде намерен чрез проверка на всяка стъпка от релацията

,

където е дадената изчислителна грешка.

Ориз. 2.1. Характерът на движението към оптимума в градиентния метод с голям размер на стъпката

Недостатъкът на градиентния метод е, че при използването му може да се намери само локалният минимум на целевата функция. За да се намерят други локални минимуми на функцията, е необходимо да се търси от други начални точки.

Друг недостатък на този метод е значителното количество изчисления, тъй като на всяка стъпка се определят стойностите на всички частични производни на функцията, която се оптимизира по отношение на всички независими променливи.

Метод на най-стръмното спускане

При прилагане на градиентния метод на всяка стъпка е необходимо да се определят стойностите на частните производни на функцията, която се оптимизира по отношение на всички независими променливи. Ако броят на независимите променливи е значителен, тогава обемът на изчисленията се увеличава значително и времето за търсене на оптимума се увеличава.

Намаляването на обема на изчисленията може да бъде постигнато чрез метода на най-стръмното спускане.

Същността на метода е следната. След като в началната точка се намери градиентът на оптимизираната функция и по този начин се определи посоката на най-бързото му намаляване в зададената точка, се прави стъпка на спускане в тази посока (фиг. 2.2).

Ако стойността на функцията е намаляла в резултат на тази стъпка, следващата стъпка се предприема в същата посока и така нататък, докато се намери минимум в тази посока, след което се изчислява градиентът и се определя нова посока на най-бързия определя се намаляване на целевата функция.

Ориз. 2.2. Характерът на движението към оптимума при метода на най-стръмното спускане (–) и метода на градиента (∙∙∙∙)

В сравнение с градиентния метод, методът на най-стръмното спускане е по-изгоден поради намаляването на обема на изчисленията.

Важна особеност на метода за най-стръмно спускане е, че при неговото прилагане всяка нова посока на движение към оптимума е ортогонална на предишната. Това е така, защото движението в една посока се извършва, докато посоката на движение е допирателна към която и да е линия с постоянно ниво.

Като критерий за прекратяване на търсенето може да се използва същото условие като в горния метод.

Освен това може да се приеме и условието за прекратяване на търсенето под формата на релацията

,

където
и
са координатите на началната и крайната точка на последния сегмент от спускането. Същият критерий може да се използва в комбинация с контрола на стойностите на целевата функция в точки
и

.

Съвместното прилагане на условията за прекратяване на търсенето е оправдано в случаите, когато оптимизираната функция е с изразен минимум.

Ориз. 2.3. Към дефиницията на края на търсенето по метода на най-стръмното спускане

Като стратегия за промяна на стъпката на спускане можете да използвате методите, описани по-горе (2.7).

Нека разгледаме проблема за безусловното минимизиране на диференцируема функция на няколко променливи.Нека стойността на градиента в точка се доближава до минимум. При разглеждания по-долу градиентен метод посоката на слизане от точката се избира директно.Така според градиентния метод

Съществуват различни начиниизбор на стъпка, всяка от които задава определен вариантградиентен метод.

1. Метод на най-стръмното спускане.

Помислете за функция на една скаларна променлива и изберете като стойност, за която равенството

Този метод, предложен през 1845 г. от О. Коши, сега се нарича метод на най-стръмното спускане.

На фиг. 10.5 показва геометрична илюстрация на този метод за минимизиране на функция от две променливи. От началната точка, перпендикулярно на линията на нивото в посоката, спускането продължава до достигане на минималната стойност на функцията по лъча. В намерената точка този лъч се допира до линията на нивото.След това се прави спускане от точката в посока, перпендикулярна на линията на нивото, докато съответният лъч докосне линията на нивото, минаваща през тази точка в точката и т.н.

Отбелязваме, че при всяка итерация изборът на стъпка предполага решението на едномерния проблем за минимизиране (10.23). Понякога тази операция може да се извърши аналитично, например за квадратична функция.

Прилагаме метода на най-стръмното спускане, за да минимизираме квадратичната функция

със симетрична положително определена матрица A.

Следователно съгласно формула (10.8) в този случай формула (10.22) изглежда така:

забележи това

Тази функция е квадратична функция на параметъра a и достига минимум при такава стойност, за която

Така, както се прилага към минимизирането на квадратното

функция (10.24), методът на най-стръмното спускане е еквивалентен на изчислението по формула (10.25), където

Забележка 1. Тъй като минималната точка на функцията (10.24) съвпада с решението на системата, методът на най-стръмното спускане (10.25), (10.26) също може да се използва като итеративен методрешения на линейни системи алгебрични уравнениясъс симетрични положително определени матрици.

Забележка 2. Забележете, че къде е отношението на Рейли (вижте § 8.1).

Пример 10.1. Прилагаме метода на най-стръмното спускане, за да минимизираме квадратичната функция

Имайте предвид, че следователно точната стойност на минималната точка ни е известна предварително. Нека запишем тази функциявъв формата (10.24), където матрицата и векторът Както е лесно да се види,

Вземаме първоначалното приближение и ще извършим изчисления по формули (10.25), (10.26).

I итерация.

II итерация.

Може да се покаже, че за всички на итерацията ще бъдат получени стойностите

Имайте предвид, че с Така,

последователността, получена чрез метода на най-стръмното спускане, се сближава със скорост геометрична прогресия, чийто знаменател

На фиг. 10.5 показва точно траекторията на спускане, получена в този пример.

За случая на минимизиране на квадратична функция е вярно следното общ резултат.

Теорема 10.1. Нека A е симетрична положително определена матрица и нека квадратичната функция (10.24) е минимизирана. Тогава, за всеки избор на първоначалното приближение, методът на най-стръмното спускане (10.25), (10.26) се събира и следната оценка на грешката е вярна:

Тук и Lado са минималните и максималните собствени стойности на матрицата A.

Имайте предвид, че този метод се сближава със скоростта на геометрична прогресия, чийто знаменател, освен това, ако са близки, тогава той е малък и методът се сближава доста бързо. Например, в Пример 10.1 имаме и, следователно, Ако Asch, тогава 1, и трябва да очакваме методът на най-стръмното спускане да се сближава бавно.

Пример 10.2. Прилагането на метода на най-стръмното спускане за минимизиране на квадратичната функция при първоначалното приближение дава последователност от приближения, където траекторията на спускане е показана на фиг. 10.6.

Последователността се събира тук със скоростта на геометрична прогресия, чийто знаменател е, т.е. много по-бавен,

отколкото в предишния пример. Тъй като тук полученият резултат е в пълно съответствие с оценката (10.27).

Забележка 1. Формулирахме теорема за сходимостта на метода на най-стръмното спускане в случай, когато целевата функция е квадратична. AT общ случай, ако функцията, която се минимизира, е строго изпъкнала и има минимална точка x, тогава също, независимо от избора на първоначалното приближение, последователността, получена чрез този метод, се сближава към x при . В този случай, след попадане в достатъчно малка околност на минималната точка, конвергенцията става линейна и знаменателят на съответната геометрична прогресия се оценява отгоре чрез стойността и където както минимумът, така и максимумът собствени стойностиХесиански матрици

Забележка 2. За квадратичната целева функция (10.24) решението на задачата за едномерна минимизация (10.23) може да бъде намерено под формата на проста изрична формула (10.26). Въпреки това, за повечето други нелинейни функциитова не може да се направи и за изчисляване по метода на най-стръмното спускане трябва да се приложи числени методиедномерни минимизации от типа, разгледан в предишната глава.

2. Проблемът с "дерета".

От дискусията по-горе следва, че градиентният метод се сближава сравнително бързо, ако повърхностите на нивото за минимизираната функция са близки до сфери (когато линиите на нивото са близо до кръгове). За такива функции и 1. Теорема 10.1, Забележка 1 и резултатът от Пример 10.2 показват, че скоростта на сходимост намалява рязко със стойността на . В двумерния случай релефът на съответната повърхност прилича на терена с дере (фиг. 10.7). Следователно такива функции обикновено се наричат ​​дерета. По направленията, характеризиращи „дъното на дерето”, функцията на дерето се променя незначително, докато в другите посоки, характеризиращи „наклона на дерето”, настъпва рязка промяна на функцията.

Ако началната точка попада на "наклона на дерето", тогава посоката на градиентното спускане се оказва почти перпендикулярна на "дъното на дерето" и следващото приближение попада на противоположния "склон на дерето". Следващата стъпка към "дъното на дерето" връща подхода към първоначалния "наклон на дерето". В резултат на това, вместо да се движи по „дъното на дерето“ към минималната точка, траекторията на спускане прави зигзагообразни скокове през „дерето“, почти не приближавайки целта (фиг. 10.7).

За да се ускори конвергенцията на градиентния метод, като същевременно се минимизират функциите на дере, са разработени редица специални методи за "дере". Нека да дадем представа за един от най-простите методи. От две близки изходни точки се прави градиентно спускане до „дъното на дерето”. През намерените точки се изчертава права линия, по която се прави голяма стъпка "дере" (фиг. 10.8). От така намерената точка отново се прави едно стъпало на градиентно спускане до точката.След това се прави втората стъпка „дере“ по правата, минаваща през точките . В резултат на това движението по "дъното на дерето" до минималната точка се ускорява значително.

| Повече ▼ подробна информацияотносно проблема с методите "дерета" и "дера" може да се намери например в , .

3. Други подходи за определяне на стъпката на спускане.

Както е лесно да се разбере, при всяка итерация би било желателно да се избере посока на спускане, близка до посоката, по която движението води от точка до точка x. За съжаление, антиградиентът (като правило е неуспешна посока на спускане. Това е особено изразено за функциите на оврага. Следователно има съмнение относно целесъобразността на задълбочено търсене на решение на проблема с едномерната минимизация (10.23) и има желание да се направи само такава стъпка в посоката, която би осигурила "значително намаляване" на функцията. Освен това на практика понякога човек се задоволява с дефинирането на стойност, която просто осигурява намаляване на стойността на целта функция.

Метод на Гаус-Зайдел

Методът се състои в последователно намиране на частични екстремуми на целевата функция за всеки фактор. В същото време на всеки етап (k-1) факторите се стабилизират и само един i-ти фактор варира

Процедура за изчисление: в локалната област на факторното пространство, въз основа на предварителни експерименти, се избира точка, съответстваща на най-добър резултатпроцес и оттам започват да се движат към оптимума. Стъпката на движение за всеки фактор се задава от изследователя. Първо, всички фактори се фиксират на едно и също ниво и един фактор се променя, докато има увеличение (намаляване) на функцията на отговор (Y), след това другият фактор се променя, докато другите се стабилизират и т.н., докато получат желан резултат(Y). Основното нещо е да изберете правилната стъпка за всеки фактор.

Този метод е най-простият, най-илюстративният, но движението към оптимума е дълго и методът рядко води до оптималната точка. Понастоящем понякога се използва в машинен експеримент.

Тези методи осигуряват движение към оптимума по права линия, перпендикулярна на линиите на равен отговор, т.е. в посоката на градиента на функцията на отговор.

Градиентните методи имат няколко разновидности, които се различават по правилата за избор на вариационни стъпки и работни стъпки на всеки етап от движението към екстремума.

Същността на всички методи е следната: първоначално, въз основа на предварителни експерименти, базова точка. След това на всеки етап се организират пробни експерименти около следващата базова точка, резултатите от които оценяват новата посока на градиента, след което се прави една работна стъпка в тази посока.

Методът на градиента (нормален) се извършва съгласно следната схема:

а) изберете базова точка;

б) изберете стъпки на движение за всеки фактор;

в) определяне на координатите на тестовите точки;

г) провеждане на експерименти в тестови точки. В резултат на това във всяка точка се получават стойностите на параметъра за оптимизация (Y).

д) въз основа на резултатите от експериментите се изчисляват оценки на компонентите на градиентния вектор в точка М за всеки i-ти фактор:

където H i е стъпката на движение по X i.

X i – координати на предишната работна точка.

g) координатите на тази работна точка се приемат като нова базова точка, около която се провеждат експерименти в тестови точки. Градиентът се изчислява и така нататък, докато се достигне желания параметър за оптимизация (Y). След всяка стъпка се прави корекция на посоката на движение.

Предимства на метода: простота, по-висока скорост на движение до оптималната.

Недостатъци: висока чувствителност към смущения. Ако кривата има сложна форма, методът може да не доведе до оптимума. Ако кривата на отговор е плоска, методът е неефективен. Методът не дава информация за взаимодействието на факторите.

а) Метод на стръмно изкачване (Box-Wilson).

б) Вземане на решение след стръмно изкачване.

в) Метод на симплексна оптимизация.

г) Предимства и недостатъци на методите.

5.7.3 Метод на стръмно изкачване (Box-Wilson)

Този метод е синтез най-добри характеристикиградиентни методи, методът на Гаус-Зайдел и методите PFE и DFE - като средство за получаване на математически модел на процеса. Решаването на задачата за оптимизация по този метод се извършва така, че стъпковото движение да се извършва в посока на най-бързото увеличение (намаляване) на параметъра за оптимизация. Корекцията на посоката на движение (за разлика от градиентните методи) се извършва не след всяка стъпка, а при достигане на конкретен екстремум на целевата функция. Освен това, в точките на частичен екстремум, се поставя нов факторен експеримент, нов математически модели отново стръмното изкачване се повтаря до достигане на глобалния оптимум. Движението по градиента започва от нулевата точка (центъра на плана).

Методът на стръмно изкачване включва движение към оптимума по наклон.

Където i,j,k-единични векторипо посока на съответните координатни оси.

Процедура за изчисление.

Първоначалните данни са математически модел на процеса, получен по произволен метод (PFE, DFE и др.).

Изчисленията се извършват в следния ред:

а) по-добре е регресионното уравнение да се преведе в естествена форма, като се използват формулите за кодиране на променливи:

където х i -кодирана стойност на променлива x i ;

X i - естествена стойност на променливата x i ;

X i C - централното ниво на фактора в неговата естествена форма;

l i - интервалът на изменение на фактора x i в естествена форма.

б) изчислете стъпките на движение до оптималното за всеки фактор.

За да направите това, изчислете продуктите на коефициентите на регресионното уравнение в естествена форма със съответните интервали на вариация

B i *.l I ,

След това от получените продукти се избира максималният модул и коефициентът, съответстващ на този продукт, се приема като основен фактор (B a l a). За основния фактор трябва да зададете стъпката на движение, която се препоръчва да бъде зададена по-малка или равен на интервалавариация на базовия фактор

Знакът на стъпката на движение l a ’ трябва да съвпада със знака на коефициента на регресионното уравнение, съответстващо на основния фактор (B a). Стойността на стъпките за други фактори се изчислява пропорционално на базовата по формулата:

Знаците на стъпките на движение също трябва да съвпадат със знаците на съответните коефициенти на регресионното уравнение.

в) функцията за реакция се изчислява в центъра на плана, т.е. със стойностите на факторите, равни на централното ниво на факторите, тъй като движението към оптимума започва от центъра на плана.

След това се изчислява параметърът за оптимизация, като се увеличават стойностите на факторите със стойността на съответната стъпка на движение, ако искате да получите Y max . В противен случай, ако е необходимо да се получи Y min , стойностите на факторите се намаляват със стойността на стъпката на движение.

Процедурата се повтаря, като последователно се увеличава броят на стъпките до достигане на желаната стойност на оптимизационния параметър (Y). Всеки от факторите след жстъпките ще имат значение:

Ако Y®max X i \u003d X i c + gl i ` ’

ако Y® мин. X i \u003d X i c -gl i `.(5.36)

Градиентният метод и неговите разновидности са сред най-разпространените методи за намиране на екстремума на функции на няколко променливи. Идеята на градиентния метод е да се движи всеки път в посока на най-голямото увеличение на целевата функция в процеса на търсене на екстремум (за определяне на максимума).

Методът на градиента включва изчисляване на първите производни на целевата функция по отношение на нейните аргументи. Той, подобно на предишните, се отнася до приблизителни методи и позволява, като правило, да не се достига оптималната точка, а само да се приближи до нея за крайно числостъпки.

Ориз. 4.11.

Ориз. 4.12.

(двуизмерен случай)

Първо изберете началната точка, ако в едномерния случай (вижте подраздел 4.2.6) от нея е възможно

се движат само наляво или надясно (виж фиг. 4.9), то в многомерния случай броят на възможните посоки на движение е безкрайно голям. На фиг. 4.11, илюстриращ случая на две променливи, стрелки, излизащи от началната точка НО,показва различни възможни посоки. В същото време движението по някои от тях дава увеличение на стойността на целевата функция по отношение на точката НО(например указания 1-3), и в други посоки води до намаляването му (посоки 5-8). Като се има предвид, че позицията на оптималната точка е неизвестна, посоката, в която целевата функция нараства най-бързо, се счита за най-добра. Тази посока се нарича градиентфункции. Имайте предвид, че във всяка точка координатна равнинапосоката на градиента е перпендикулярна на допирателната към линията на нивото, прекарана през същата точка.

AT математически анализдоказано е, че компонентите на градиентния вектор на функцията при =/(*, х 2, ..., x n)са неговите частни производни по отношение на аргументите, т.е.

&ad/(x 1,x 2 ,.= (du / dhu, dy / dx 2, ..., dy / dx p). (4.20)

Така при търсене на максимума по метода на градиента, при първата итерация се изчисляват компонентите на градиента по формули (4.20) за началната точка и се предприема работна стъпка в намерената посока, т.е. се извършва преход към нова точка -0)

Y" с координати:

1§газ1/(x (0)),

или във векторна форма

където Х-постоянно или променлив параметър, което определя дължината на работната стъпка, ?i>0. При втората итерация изчислете отново

градиентният вектор вече е за нова точка Y, след което аналогично

формула отидете до точката x^ > и т.н. (фиг. 4.12). За произволни да се-та итерация, която имаме

Ако се търси не максимумът, а минимумът на целевата функция, то при всяка итерация се прави стъпка в посока, обратна на посоката на градиента. Нарича се антиградиентна посока. Вместо формула (4.22), в този случай ще бъде

Има много разновидности на градиентния метод, които се различават по избора на работната стъпка. Възможно е например да отидете на всяка следваща точка в постоянна стойност х,и тогава

дължината на работната стъпка е разстоянието между съседни точки x^

техният 1 "- ще бъде пропорционален на модула на градиентния вектор. Можете, напротив, при всяка итерация да изберете хтака че дължината на работната стъпка да остане постоянна.

Пример.Изисква се да се намери максимумът на функцията

y \u003d 110-2 (lg, -4) 2 -3 (* 2 -5) 2.

Разбира се, използвайки необходимо условиеекстремум, веднага получаваме желаното решение: Х ] - 4; х 2= 5. Въпреки това, на това прост примерудобно е да се демонстрира алгоритъмът на градиентния метод. Нека изчислим градиента на целевата функция:

град y \u003d (du / dx-, dy / dx 2) \u003d(4(4 - *,); 6(5 - x 2)) и изберете началната точка

А*» = (х)°> = 0; 4°> = О).

Стойността на целевата функция за тази точка, както е лесно да се изчисли, е равна на y[x^ j = 3. Нека х= const = 0,1. Стойност на градиента в точка

3c (0) е равно на grad y|x^j = (16; 30). След това на първата итерация по формули (4.21) получаваме координатите на точката

x 1)= 0 + 0,1 16 = 1,6; x^ = 0 + 0,1 30 = 3.

y (x (1)) \u003d 110 - 2 (1,6 - 4) 2 - 3 (3 - 5) 2 \u003d 86,48.

Както можете да видите, тя е значително по-голяма от предишната стойност. При втората итерация имаме по формули (4.22):

• 1,6 + 0,1 4(4 - 1,6) = 2,56;