principal D' autres disciplines livres Matiquement programuvannya mathématique - Nakonechny S.І.

Matiquement programuvannya mathématique - Nakonechny S.І.

8.10. méthode Gradієntny

Gradієntnі nalezhat méthodologique à nablizhenih metodіv tâches rozv'yazuvannya nelіnіynogo programuvannya je donne la privation Pevnyi nablizhennya à ekstremumu, et zbіlshennya obsyagu obchislen mozhna dosyagti tâches résultat de l' avant tochnіstyu, ale au tsomu razі Je mozhlivіst privation znahoditi lokalnі ekstremumi tsіlovoї funktsії. Zauvazhimo, mise en forme de scho peut la privation de Buti takі méthodique pour calmer tipіv tâches nelіnіynogo programuvannya de tsіlova funktsіya i obmezhennya Je diferentsіyovnimi Hoca utilisé une fois. Zrozumіlo méthodes gradієntnі scho donnent zmogu point de znahoditi pour les tâches de tіlki de ekstremumu mondiale opuklogo programuvannya de localement i la zbіgayutsya mondiale ekstremumi.

Dans osnovі gradієntnih metodіv lezhit La base vlastivіst gradієnta diferentsіyovnoї funktsії - viznachati par exemple nayshvidshogo zrostannya tsієї funktsії. méthode Іdeya polyagaє en perehodі od odnієї point à іnshoї dans napryamku gradієnta s deyakim tâches à venir CRIC.

méthode Rozglyanemo Frank - Procédure Wolfe yakogo peredbachaє viznachennya de rozv'yazkіv Shlyakhov itérer de plan optimal, SSMSC Je recevabilité zadachі plans.

Nekhay neobhіdno vіdshukati

pour obmezhen lіnіynih:

;

Acceptable, scho X 0 - point Pochatkova, scho nalezhit mnozhinі recevabilité planіv danoї zadachі. Dans deyakomu okolі tsієї Point nelіnіynu tsіlovu funktsіyu zamіnyuyut lіnіynoyu i potіm rozv'yazuyut tâche lіnіynogo programuvannya. Nekhay rozv'yazok lіnіynoї zadachі donnant des valeurs tsіlovoї funktsії F 0, le point de X de todі 0 0 F napryamku neobhіdno ruhatis Doty, Pokey est pas pripinitsya zrostannya tsіlovoї funktsії. Tobto dans zaznachenomu napryamku vibirayut point X 1 suivant, tsіlova funktsіya znovu zamіnyuєtsya sur lіnіynu, i znovu tâche rozv'yazuєtsya lіnіynogo programuvannya.

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

Pripustimo point Xk scho vіdoma, yak nalezhit oblastі recevabilité rozv'yazkіv. Dans danіy tochtsі obchislyuєmo gradієnt tsіlovoї funktsії:

.

Signification gradієnta funktsії zadaє dans danіy tochtsі par exemple nayshvidshogo її zrostannya.

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

.

La tâche Potіm de lіnіynogo programuvannya s obmezhennyami pochatkovoї zadachі i par un nouveau funktsієyu de tsіlovoyu:

des esprits:

;

.

Nekhay rozv'yazkom takoї zadachі Point Je .

W Point pochatkovoї en napryamku ruhaєmosya s deyakim dovіlnim Kroc , Viznachayuchi coordonnées du point novoї en Taqiy sposіb:

Zauvazhimo scho valeur de paramètre dotsіlno vibirati ces daє scho naybіlshe valeurs tsіlovoї funktsії pochatkovoї zadachі .

Pour un point Xk processus rozglyanuty +1 povtoryuєmo pour Chogo znovu rozrahovuєmo valeurs gradієnta t i. E.

Dans Taqiy sposіb znahodimo poslіdovnіst tochok , SSMSC de la nablizhayutsya à l'optimal régime pochatkovoї zadachі. Іteratsіyny traite povtoryuєtsya avant l'heure, Pokey valeurs gradієnta tsіlovoї funktsії pas camper rіvnim zéro abo vikonuvatimetsya Umov de - Numéros Dosit mala yak oznachaє potrіbnu tochnіst obchislen.

deux produktsії Vidi de Pіdpriєmstvo (A i B) i vikoristovuє sur virobnitstvo trois Vidi resursіv: I, II, III. resursіv vitrati sur virobnitstvo odinitsі peau esprit produktsії présenté dans l'onglet. 8.2.

tableau 8.2

Cena realіzatsії odinitsі produktsії esprit, mais devient 20 d. od. contre la vitrat de dépôts Prybutok sur virobnitstvo, la place SSMSC de kіlkostі vigotovlenoї produktsії. Analogіchno viznachaєtsya Prybutok pour produktsії à l'esprit, Cena realіzatsії yakoї dorіvnyuє 18 d. od.

Rozv'yazannya. Poznachimo par x 1 Quantité forme produktsії A x 2 - Quantité produktsії à l' esprit, todі zagalny Prybutok matim viglyad: .

modèle mathématique matiquement zadachі Got viglyad:

.

.

Rozv'yazhemo tâche par Frank Wolf.

I іteratsіya

Point Vibiraєmo, recevabilité scho nalezhit mnozhinі planіv zadachі. Rozglyanemo, napríklad, le point .

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

.

Dans tochtsі obchislyuєmo gradієnta valeurs:

.

Vikoristovuyuchi valeurs rozrahovane gradієnta, entrée zapisuєmo i nova tsіlovu funktsіyu: . Maєmo Taku tâche lіnіynogo programuvannya:

.

Rozv'yazuyuchi méthode simplex problème qiu, znahodimo régime її optimal: .

Znaydemo Novi recevabilité zadachі formule plan de vikoristovuyuchi pour coordonner viznachennya nastupnoї points.

Coordonnées Viznachaєmo de x 1:

. .

Znaydemo Krok Taqiy pour yakogo dosyagaєtsya valeur maximale tsіlovoї funktsії. Pour les valeurs Tsogo pіdstavimo de rozrahovanі pour x 1, x 2, à travers le virazhenі de SSMSC Il a tsіlovu funktsіyu :

funktsіyu Otrimali dépôts scho od . valeurs Znaydemo Pour yakogo funktsіya dosyagaє maximale, si tobto її pohіdna dorіvnyuє zéro:

Oskіlki Ensuite, prendre . Todі le Got point suivant X 1 Coordonnées:

.

Pour le point znaydenoї obchislyuєmo valeurs tsіlovoї funktsії: .

II іteratsіya

Point Uzyavshi , Obchislyuєmo valeurs gradієnta en nіy:

valeurs rozrahovane Vikoristovuyuchi gradієnta introduits nova tsіlovu funktsіyu: . Otrimuєmo Taku tâche lіnіynogo programuvannya:

.

méthode simplex de Rozv'yazavshi, plan optimal otrimuєmo: .

Pour la formule viznachaєmo coordonnées nastupnoї points nablizhennya.

Coordonnées Viznachaєmo de x 2:

.

.

Znaydemo Taqiy Krok λ2, pour yakogo dosyagaєtsya valeur maximale tsіlovoї funktsії:

Matimemo .

Les coordonnées du point de Obchislimo X 2:

Pour le point znaydenoї Signification tsіlovoї funktsії dorіvnyuє: .

processus Prodovzhuyuchi dans analogіchny sposіb sur III іteratsії viznachaєmo Point i perekonuєmosya valeurs scho tsіlovoї funktsії znovu zrostaє: .

A rozrahovuyutsya points les coordonnées du IV Pour yakoї .

V іteratsіya

Point Uzyavshi , Obchislyuєmo valeurs gradієnta en nіy:

.

Vikoristovuyuchi valeurs vecteur Tsogo (gradієnta) introduit nova tsіlovu funktsіyu: i maєmo Taku tâche lіnіynogo programuvannya:

.

.

problème de qiu Rozv'yazavshi otrimaєmo valeur du plan optimal , Tobto povertaєmosya à poperednogo valeurs. Otzhe, z les coordonnées du point vvazhaєmo plan optimal, oskіlki maєmo nulovy gradієnt funktsії, tobto Tsey polіpshiti vzhe pas le plan mozhna.