Matisch mathematische programuvannya - Nakonechny S.І.

8.10. Gradієntny Verfahren

Gradієntnі methodologische nalezhat metodіv rozv'yazuvannya Aufgaben nelіnіynogo programuvannya zu nablizhenih i Deprivation Pevnyi geben nablizhennya zu ekstremumu und für zbіlshennya obsyagu obchislen mozhna dosyagti Ergebnis s Aufgaben vor tochnіstyu, ale bei tsomu razі Je mozhlivіst znahoditi Deprivation lokalnі ekstremumi tsіlovoї funktsії. Zauvazhimo kann scho Formgebung Buti methodische takі zastosovanі Entbehrung zu beruhigen tipіv Aufgaben nelіnіynogo programuvannya de tsіlova funktsіya i obmezhennya Je diferentsіyovnimi Hoca einmal verwendet. Zrozumіlo scho gradієntnі Methoden geben zmogu znahoditi Punkt für die globale ekstremumu tіlki Aufgaben opuklogo programuvannya de lokal i der globalen ekstremumi zbіgayutsya.

In osnovі gradієntnih metodіv lezhit Die Grund vlastivіst gradієnta diferentsіyovnoї funktsії - viznachati zB nayshvidshogo zrostannya tsієї funktsії. Іdeya Methode polyagaє in perehodі od odnієї Punkt іnshoї in napryamku gradієnta s deyakim Aufgaben vor CRIC.

Rozglyanemo Methode Frank - Wolfe Verfahren yakogo peredbachaє viznachennya optimalen Plan zadachі Shlyakhov Iterieren rozv'yazkіv, SSMSC Je Zulässigkeit zadachі Pläne.

Nekhay neobhіdno vіdshukati

für lіnіynih obmezhen:

;

Akzeptabel, scho X 0 - Pochatkova Punkt, scho nalezhit mnozhinі Zulässigkeit planіv danoї zadachі. In deyakomu okolі tsієї Punkt nelіnіynu tsіlovu funktsіyu zamіnyuyut lіnіynoyu i potіm rozv'yazuyut Aufgabe lіnіynogo programuvannya. Nekhay rozv'yazok lіnіynoї zadachі Werte geben tsіlovoї funktsії F 0, todі s Punkt X 0 0 F napryamku neobhіdno ruhatis Doty, Pokey ist nicht pripinitsya zrostannya tsіlovoї funktsії. Tobto in zaznachenomu napryamku vibirayut der folgende Punkt X 1, tsіlova funktsіya znovu zamіnyuєtsya auf lіnіynu, i znovu rozv'yazuєtsya Aufgabe lіnіynogo programuvannya.

Rozglyanemo detalnіshe perehіd od k -oї іteratsії Methode (k + 1) -oї іteratsії.

Pripustimo scho vіdoma Xk Punkt, Yak nalezhit oblastі Zulässigkeit rozv'yazkіv. In danіy tochtsі obchislyuєmo gradієnt tsіlovoї funktsії:

.

Bedeutung gradієnta funktsії zadaє in danіy tochtsі zB nayshvidshogo її zrostannya.

Zamіnyuєmo tsіlovu funktsіyu zadachі lіnіynoyu funktsієyu Geist:

.

Potіm rozv'yazuєmo Aufgabe lіnіynogo programuvannya s obmezhennyami pochatkovoї zadachі i durch einen neuen tsіlovoyu funktsієyu:

der Geister:

;

.

Nekhay rozv'yazkom takoї zadachі Je Punkt .

W pochatkovoї Punkt in napryamku ruhaєmosya s deyakim dovіlnim Kroc Koordinaten Viznachayuchi novoї Punkt in Taqiy sposіb:

Zauvazhimo scho Parameterwert dotsіlno vibirati so scho daє naybіlshe Werte tsіlovoї funktsії pochatkovoї zadachі .

Für einen Punkt xk +1 povtoryuєmo rozglyanuty Verfahren für chogo znovu rozrahovuєmo Werte gradієnta t i. E.

In Taqiy sposіb znahodimo poslіdovnіst tochok , SSMSC postupovo nablizhayutsya auf den optimalen Plan pochatkovoї zadachі. Іteratsіyny verarbeitet povtoryuєtsya, bevor die Zeit, Pokey Werte gradієnta tsіlovoї funktsії nicht Lager rіvnim Null abo vikonuvatimetsya Umov de - Dosit mala Zahlen Yak oznachaє potrіbnu tochnіst obchislen.

Pіdpriєmstvo viroblyaє zwei Vidi produktsії (A i B) i vikoristovuє auf virobnitstvo drei Vidi resursіv: I, II, III. Vitrati resursіv auf virobnitstvo odinitsі Haut Geist produktsії in Tab eingereicht. 8.2.

Tabelle 8.2

Art der Ressource

Ansicht produktsії

Zagalny obsyag Ressource

A

das

die I

1

3

30

II

1

1

15

III

5

2

60

Cena realіzatsії odinitsі produktsії Geist aber wird 20 d. od. gegen Prybutok Ablagerungen od vitrat auf virobnitstvo, SSMSC proportsіynі Platz kіlkostі vigotovlenoї produktsії. Analogіchno viznachaєtsya Prybutok für produktsії im Auge, Cena realіzatsії yakoї 18 d dorіvnyuє. od.

Rozv'yazannya. Poznachimo von x 1 Menge produktsії Form A x 2 - Menge produktsії im Auge, todі zagalny Prybutok Matim viglyad: .

Matisch mathematisches Modell zadachі viglyad Got:

.

.

Rozv'yazhemo Aufgabe von Frank Wolf.

die ich іteratsіya

Vibiraєmo Punkt, scho nalezhit mnozhinі Zulässigkeit planіv zadachі. Rozglyanemo, napriklad, Punkt .

Viznachimo gradієnt tsіlovoї funktsії:

.

in tochtsі obchislyuєmo gradієnta Werte:

.

Vikoristovuyuchi rozrahovane Werte gradієnta, zapisuєmo i Eingang nova tsіlovu funktsіyu: . Maєmo Taku Aufgabe lіnіynogo programuvannya:

.

Rozv'yazuyuchi Qiu Problem Simplex-Methode, znahodimo її optimalen Plan: .

Znaydemo Novi Zulässigkeit zadachі Plan vikoristovuyuchi Formel viznachennya nastupnoї Punkt zu koordinieren.

Viznachaєmo Koordinaten von x 1:

. .

Znaydemo Krok Taqiy für yakogo dosyagaєtsya Maximalwert tsіlovoї funktsії. Für tsogo pіdstavimo rozrahovanі Werte für x 1, x 2, durch die SSMSC virazhenі Es hat tsіlovu funktsіyu :

Otrimali funktsіyu scho Ablagerungen od . Znaydemo Werte Für yakogo funktsіya dosyagaє Maximum, wenn tobto її pohіdna dorіvnyuє Null:

Oskіlki Dann nehmen . Todі folgenden Punkt X 1 Got Koordinaten:

.

Für znaydenoї Punkt obchislyuєmo Werte tsіlovoї funktsії: .

II іteratsіya

Uzyavshi Punkt , Werte Obchislyuєmo gradієnta in nіy:

Vikoristovuyuchi rozrahovane Werte gradієnta nova tsіlovu funktsіyu eingeführt: . Otrimuєmo Taku Aufgabe lіnіynogo programuvannya:

.

Rozv'yazavshi її Simplex-Methode, optimalen Plan otrimuєmo: .

Für Formel viznachaєmo Koordinaten nastupnoї Punkt nablizhennya.

Viznachaєmo Koordinaten von x 2:

.

.

Znaydemo Taqiy Krok λ2, für yakogo dosyagaєtsya Maximalwert tsіlovoї funktsії:

Matimemo .

Obchislimo nastupnoї Koordinaten des Punktes X 2:

Für znaydenoї Punkt Bedeutung tsіlovoї funktsії dorіvnyuє: .

Prodovzhuyuchi Prozesse in analogіchny sposіb auf III іteratsії viznachaєmo Punkt i perekonuєmosya scho Werte tsіlovoї funktsії znovu zrostaє: .

An der rozrahovuyutsya Punktkoordinaten іteratsії IV Für yakoї .

V іteratsіya

Uzyavshi Punkt , Werte Obchislyuєmo gradієnta in nіy:

.

Vikoristovuyuchi Werte tsogo Vektor (gradієnta) eingeführt nova tsіlovu funktsіyu: i maєmo Taku Aufgabe lіnіynogo programuvannya:

.

.

Rozv'yazavshi Qiu Problem otrimaєmo Wert des optimalen Plan Tobto, povertaєmosya Werte poperednogo. Otzhe, z-Koordinaten des Punktes vvazhaєmo optimalen Plan, oskіlki maєmo nulovy gradієnt funktsії, tobto Tsey polіpshiti vzhe nicht mozhna Plan.