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

Ically mathematical programuvannya - Nakonechny S.І.

3.3.1. Persha theorem dvoїstostі

Theorem (Persha dvoїstostі theorem). Yakscho s one bet conjugation problems Got an optimal plan, the second another task takozh Got rozv'yazok, and for optimal values ​​rozv'yazkіv tsіlovih funktsіy oboh tasks zbіgayutsya, tobto

.

Yakscho tsіlova funktsіya odnієї іz neobmezhena tasks, the task spryazhena takozh not Got rozv'yazku * 1.

* 1: {Zauvazhimo, scho if one іz tasks not permitted Got rozv'yazku then dvoїsta to neї task takozh Mauger not permissible rozv'yazku mother, tobto zvorotne tverdzhennya schodo Druha Chastain theorem in zagalnomu vipadku not vikonuєtsya.}

BROUGHT. Acceptable, scho Pochatkova problem (3.1) - (3.3) Got an optimal plan, yaky otrimany simplex method. Not porushuyuchi zagalnostі can vvazhati scho ostannіy basis skladaєtsya s Persha m vektorіv . Stop simplex tableau Got viglyad:

table 3.1

Poznachimo by D matrix, scho s utvorena vektorіv component A1, A2, ..., A m ostannogo basis in pershіy simpleksnіy tablitsі.

For optimal plan otrimaєmo:

(3.12)

de , In - vector scho skladaєtsya s vіlnih chlenіv Sistemi obmezhen.

Zvіdsi:

(3.13)

Simplex Table 3.1 mіstit koefіtsієnti rozkladu vektorіv pochatkovoї Sistemi obmezhen zadachі of basis vectors, vector tobto dermal s Sistemi obmezhen zadachі (3.1) - (3.3) A j vіdpovіdaє in simpleksnіy tablitsі vector , Taqiy scho

(3.14)

Poznachimo through Matrix, scho s skladaєtsya koefіtsієntіv rozkladu vektorіv . Todі bude spravdzhuvatisya rіvnіst:

.

zvіdki

. (3.15)

Vrahovuyuchi (3.13), the value of the optimal plan danoї zadachі znahoditsya in viglyadі:

de , and

.

tobto OAO All components of the vector Je otsіnkami zadachі optimal plan (3.1) - (3.3), and to

. (3.16)

Oskіlki optimal plan pochatkovoї zadachі filed in viglyadі Then the rules pobudovi dvoїstoї zadachі mozhna dopustiti scho її optimal plan matim viglyad:

. (3.17)

Dovedemo scho dіysno Je optimal plan dvoїstoї zadachі.

System obmezhen dvoїstoї zadachі in vector-matrichnіy formі matim viglyad:

.

Pіdstavimo in qiu nerіvnіst values . Todі, vrahovuyuchi (3.15), (3.16) that (3.17), otrimaєmo:

.

Zvіdki: . Otzhe, zadovolnyaє obmezhen system (3.5) dvoїstoї zadachі, that Je zadachі admissible plans (3.4) - (3.6).

For danogo plan values ​​funktsіonala dorіvnyuvatime:

(3.18)

de . Pіdstavimo in (3.18) values h (3.17) one vrahovuyuchi (3.13), matimemo:

. (3.19)

Bring scho zbіgaєtsya Zi value of the optimal plan pochatkovoї zadachі.

Otzhe for lemoyu 3.2 (dostatnya Umov optimalnostі plan zadachі lіnіynogo programuvannya) Plan Je optimal plan dvoїstoї zadachі (3.4) - (3.6).

Analogіchno communicated, scho if dvoїsta task Got rozv'yazok then Pochatkova takozh Got rozv'yazok i vikonuєtsya rіvnіst:

.

To bring Druha Chastain theorem acceptable scho lіnіyna funktsіya pochatkovoї zadachі neobmezhena zverhu. Todі s nerіvnostі maєmo scho Scho not Got zmіstu. Otzhe, dvoїsta task danomu razі not Got rozv'yazkіv.

Bring theorem daє zmogu in protsesі rozv'yazuvannya odnієї zadachі vodnochase znahoditi Druha plan.

Ekonomіchny zmіst pershoї dvoїstostі theorem. Maximum Prybutok (Fmax) pіdpriєmstvo otrimuє of minds virobnitstva produktsії zgіdno s optimal plan But very Taku bag of pennies ( ) Vono Mauger mother, realіzuvavshi resources optimally for tsіnami . Over the minds vikoristannya іnshih planіv on pіdstavі osnovnoї nerіvnostі teorії dvoїstostі mozhna stverdzhuvati scho pributki od realіzatsії produktsії zavzhdi menshі, nіzh vitrati on її virobnitstvo.