home Other disciplines books Ically mathematical programuvannya - Nakonechny S.І.

Ically mathematical programuvannya - Nakonechny S.І.

8.8.2. Method rozv'yazuvannya tasks quadratic programuvannya

Zaznachimo scho vіdomim s teorії analіzu funktsіy Je TAKE tverdzhennya: vіd'єmno signified quadratic form Je ugnutoyu and dodatno signified - opukloyu.

Rozglyanemo vipadok vіd'єmno oznachenoї kvadratichnoї form, scho to enter in tsіlovu funktsіyu zadachі quadratic programuvannya.

max (8.42)

; (8.43)

. (8.44)

Oskіlki tsіlova funktsіya zadachі Je opukloyu and obmezhennya - lіnіynі, tobto viznachayut opuklu mnozhinu rozv'yazkіv admissibility, the tsya nalezhit task to task opuklogo programuvannya for yakih spravdzhuєtsya tverdzhennya, scho whether yaky local maxima of global Yea i. Otzhe, vikoristovuyuchi minds theorem of Kuhn - Tucker to zadachі (8.42) - (8.44) otrimaєmo neobhіdnі that dostatnі minds optimalnostі plan in viglyadі takoї theorem.

Theorem 8.6. The vector X * Je optimally rozv'yazkom zadachі quadratic programuvannya todі, i tіlki todі, if іsnuyut takі m -vimіrnі vectors i n -vimіrny vector Scho vikonuyutsya minds:

(I) . ; (8.45)

(II) . ; (8.46)

(III) . ; (8.47)

(IV) . . (8.48)

BROUGHT. Zapishemo Lagrange funktsіyu for zadachі quadratic programuvannya (8.42) - (8.44):

+ . (8.49)

Nekhay - Sіdlova funktsії Lagrange point tobto yak viznachaє optimal plan zadachі quadratic programuvannya. Zastosuєmo Theorem 8.4 to virazu (8.49). For the theorem for the dwellers point viznachala optimal plan, neobhіdno i dostatno vikonannya drain (8.38) - (8.41):

for Got vikonuvatis Umov:

. (8.50)

and takozh (8.51)

and for Got vikonuvatis Umov:

. (8.52)

and takozh . (8.53)

Vіzmemo two vectors that , The component will be yakih vvedenі yak dodatkovі zmіnnі in rіvnyannya (8.50) that (8.52). For tsogo viberemo , Yakscho i , Yakscho . Analogіchno viberemo , Yakscho i , Yakscho . Teper dodamo vector components from (8.50) i vіdnіmemo vector components od (8.52). Vrahovuyuchi rules Vibor component vektorіv, matimemo to (8.50):

. .

Zvіdsi: , That for (8.51) maєmo:

.

Analogіchno for Druha groupies obmezhen:

. .

Zvіdki , to .

Theorem brought.

Guidance theory can be vikoristati for pobudovi efektivnosti method rozv'yazuvannya problems on quadratic programuvannya osnovі algorithm simplex method.

Minds (8.45) - (8.49) utvoryuyut stosovno zmіnnih system (n + m) rіvnyan of 2 (n + m) nevіdomimi.

Minds (8.47) that (8.48) oznachayut scho zmіnnі not mozhut odnochasno mother dodatnі value tobto vhoditi in time basis. Yakscho deyakі k vector components dodatnі then vіdpovіdnі їm components of the vector V i dorіvnyuyut zero deprivation (n - k) vіdmіnnі od component zero (dodatnі). Otzhe, again Mother will not bіlsh nіzh n dodatnih component. W analogіchnih mіrkuvan schodo rіvnostі (8.48) viplivaє scho s once bude n + m od vіdmіnnih zero component tobto Tse Mauger Buti the basal rozv'yazok system scho utvorena Minds (8.45) that (8.47). For this znahodzhennya rozv'yazku mozhna zastosuvati simplex method.

Yakscho zaznachena system rіvnyan Got feasible plan (vіn bude єdinim), then the optimal plan vіdpovіdnoї zadachі quadratic programuvannya takozh іsnuє.

Rozv'yazuєmo rіvnyan system (8.45) i (8.47) simplex method. Yak vіdomo, spochatku neobhіdno obmezhen bring the system to the introduction of kanonіchnogo mind potrіbnoї kіlkostі dodatkovih she boxed zmіnnih. For the system to the Institution kanonіchnoї FORMS that viznachennya Pochatkova support program administered shtuchnі zmіnnі rіvnyannya in the form (8.45), will be of basis for SSMSC Perche reference plan, and zmіnnі - At grupu rіvnyan (8.47), SSMSC takozh give bazisnі zmіnnі for Pochatkova plan. Potіm for znahodzhennya base rozv'yazku the system (8.45) (8.47) rozv'yazuєmo simplex method Taku task lіnіynogo programuvannya:

max (8.54)

of minds:

(8.55)

. (8.56)

Yakscho in protsesі rozv'yazuvannya zadachі (8.54) - (8.56) OAO All shtuchnі zmіnnі will vivedenі s basis once i s CIM values ​​for znaydenih zmіnnih vikonuyutsya Minds (8.46), (8.48), then znaydeny rozv'yazok Je optimal plan zadachі quadratic programuvannya (8.42) - (8.44).

Rozv'yazati problem of quadratic programuvannya:

of minds:

Rozv'yazannya. Oskіlki tsіlova funktsіya Virage sumoyu lіnіynoї funktsії that kvadratichnoї FORMS And the system obmezhen lіnіynoyu Yea, the problem of quadratic maєmo programuvannya.

Viznachimo view kvadratichnoї FORMS For chogo vіdshukaєmo korenі the characteristic rіvnyannya scho vіdpovіdaє matritsі, skladenіy s koefіtsієntіv at zmіnnih danoї funktsії:

.

The characteristic rіvnyannyam for matritsі With Bude:

Oskіlki obidva korenі rіvnyannya vіd'єmnі the characteristic, then the quadratic form Je vіd'єmno aforesaid and otzhe, opukloyu.

Zapishemo Lagrange funktsіyu for tsієї zadachі:

.

Skoristaєmosya Theorem 8.4. Neobhіdnі minds іsnuvannya ekstremumu matimut viglyad:

, and ;

, and ;

, and .

de - Coordinates sіdlovoї point.

Obmezhennya scho vіdpovіdayut nerіvnostyam, zapishemo in viglyadі:

Input for dodatkovі zmіnnі Institution nerіvnostey to rіvnyan:

For Institution zadachі to kanonіchnoї FORMS pomnozhimo cutaneous rіvnyannya (-1):

Obviously, scho in danomu razі shtuchnі zmіnnі neobhіdno vvoditi in Pershi two rіvnyannya. One-third of the basal rіvnyannі zmіnnoyu Bude . Maєmo Taku task lіnіynogo programuvannya:

.

.

Rozv'yazavshi її simplex method, otrimaєmo:

Neobhіdno perevіriti vikonannya minds:

;

;

.

OAO All minds vikonuyutsya, otzhe, Je sіdlovoyu funktsії Lagrange point for zadachі quadratic programuvannya and - Optimal plan zadachі for yakogo values ​​funktsіonala dorіvnyuє:

.