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

Ically mathematical programuvannya - Nakonechny S.І.

3.7.2. Parametrichnі zmіni vector koefіtsієntіv tsіlovoї funktsії

Rozglyanemo vipadok lіnіynoї zalezhnostі koefіtsієntіv tsіlovoї funktsії od parameter values mozhlivі yakogo zadanі neperervnim numeric іntervalom, tobto in zadachі lіnіynogo programuvannya

(3.80)

(3.81)

(3.82)

permissible scho

. (3.83)

Well Usі INSHI koefіtsієnti i vіlnі The members of zalishayutsya steel quantities.

Zapishemo the parame- this problem in mind zagalnіy formі:

(3.84)

(3.85)

. (3.86)

For deyakogo fіksovanogo values problem (3.84) - (3.86) in peretvoryuєtsya zvichaynu task lіnіynogo programuvannya. Zmіni koefіtsієntіv tsіlovoї funktsії in protsesі realіzatsії simplex method to the value vplivatimut otsіnkovogo row ( ).

For optimal plan zadachі lіnіynogo programuvannya in postanovtsі (3.36) - (3.38), yak vіdomo s § 2.7.4, otsіnki vektorіv rozrahovuyut as follows:

.

Yakscho tsіlova funktsіya Got viglyad (3.84), then otsіnki vektorіv rozrahovuvatimutsya of the formula:

Poznachimo peretvorenі method Povny viklyuchen Jordan-Gauss protsesі pererahunku pochatkovoї simpleksnoї tablitsі across , analogіchno - yak . Stop simplex tableau Naboodah such viglyadu:

table 3.6

Table (analogіchno vipadku parametrichnoї zmіni vector obmezhen -tabl. 3.5) mіstit dodatkovih two rows, scho daє zmogu stezhiti for peretvorennyami values pіslya kozhnoї іteratsії.

Obviously, scho problem parametrichnoї zmіni vector obmezhen Je dvoїstoyu to parametrichnoї zmіni vector koefіtsієntіv tsіlovoї funktsії, this can be skoristatis algorithm rozv'yazuvannya parametrichnoї zadachі scho imposed in poperednomu paragrafі.

1. Slіd zafіksuvati deyake values i rozv'yazati problem (3.84) - (3.86) yak zvichaynu task lіnіynogo programuvannya simplex method.

2. optimal plan s ostannoї simpleksnoї tablitsі 3.6 Je sumoyu dvoh dodankіv, yakih znahodyatsya values ​​in rows that , And Got vikonuvatisya Umov nevіd'єmnostі vsіh vector component scho Yea otsіnkami parametrіv ostannoї simpleksnoї tablitsі, tobto

.

3. Vstanovlyuєmo granitsі value of the parameter, t, for yakih vector zalishatimetsya optimal plan. For tsogo s ostannoї simpleksnoї tablitsі skladaєmo nerіvnostey system

. (3.87)

a) Yakscho іsnuyut takі values j, for yakih , Todі rozv'yazkami vіdpovіdnih nerіvnostey will:

. (3.88)

In Taqiy sposіb viznachayut bottom border Shukanov іntervalu, yak Mauger dorіvnyuvati and abo Buti Mensch for neї: .

Yakscho Absent , OOO All tobto , The value, t, for yakih znaydeny bude optimally znizu not obmezhenі, tobto .

b) Yakscho іsnuyut takі values i for yakih Then rozv'yazkami vіdpovіdnih nerіvnostey will:

. (3.89)

W Tsikh rozv'yazkіv viznachayut upper boundary Shukanov іntervalu, yak Mauger Buti dorіvnyuvati abo bіlshoyu for and ( ). Yakscho Absent , OOO All tobto Then sukupnіst values, t, for yakih znaydeny plan bude optimally zverhu neobmezhena ( ) I in tsomu ostannomu vipadku task rozv'yazana povnіstyu, oskіlki

.

4. The system (3.74) viznachaє vector yaky neobhіdno Vivest s basis. Pripustimo, scho for deyakogo de , Mіnіmalne value in (3.89), yak viznachaє upper boundary іntervalu , For dosyagaєtsya . Otzhe, porushuєtsya k -ta nerіvnіst іz (3.87), i s the basis neobhіdno vivoditi vector scho vіdpovіdaє zmіnnіy . Tom at neobhіdno spend zamіnu basis for chogo vikonuyut one Krok dvoїstogo simplex method rozglyanutogo in § 3.6, i viznachayut basis of values .

5. Rozglyadaєmo znovu nerіvnostey system (3.87). For of the formula (3.77) viznachaєmo upper boundary Meaning quiet, t, for yakih vіdshukany plan bude optimally.

6. The procedure povtoryuєmo Doty, Pokey is not otrimaєmo values ​​verhnoї granitsі chergovogo іntervalu, scho abo dorіvnyuє perevischuє upper boundary assignments іntervalu mozhlivih values t, tobto

. (3.90)

Spіvvіdnoshennya (3.90) i Je Find our order, scho problem rozv'yazano.

Otzhe, promіzhok jobs podіlyayut a number іntervalіv For skin s yakih maximum tsіlovoї funktsії dosyagaєtsya for vіdpovіdnogo Yomou one optimal plan.

Rozv'yazati the parame- task

Nekhay . Rozv'yazhemo task modifіkovanim simplex method, vikoristovuyuchi table s EYAD dodatkovimi rows.

Stop simplex tableau mіstit Purshia optimally plan zadachі

The upper boundary of Perche promіzhku zgіdno s (3.89) dorіvnyuє . Otzhe on іntervalі plan bude Optimally, the optimal value tsіlovoї funktsії bude with such a lіnіynoyu funktsієyu parameter t:

when i .

Oskіlki at yelement m + 2 row that p'yatoї bude column nulovim, take p'yatu rozv'yazuvalnu column for i, m + 2 vіdkinuvshi row, zdіysnyuєmo one іteratsіyu. Otrimaєmo taku table:

The m + 3 rows tsієї tablitsі Absent vіd'єmnih elementіv and to zgіdno s formula (3.89) znaydeny plan bude optimal for vsіh values t, scho lie on іntervalі . Optimal value tsіlovoї funktsії Je lіnіynoyu funktsієyu with such a parameter t:

.

at .

Otzhe task rozv'yazana povnіstyu.