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

Ically mathematical programuvannya - Nakonechny S.І.

3.7. the parame- programuvannya

In paragrafі 3.5 Bulo rozglyanuto, yak zmіnyuєtsya optimal plan zadachі lіnіynogo programuvannya, Yakscho zmіnyuyutsya koefіtsієnti tsіlovoї funktsії chi obmezhen vector components. However doslіdzhennya stosuvalisya deprivation viznachennya dіapazonu for Change, in furrows yakogo structure of the optimal plan zalishalas tієyu samoyu before Well skin once rozglyadali vpliv zmіni deprivation odnієї skladovoї.

However praktitsі traplyayutsya vipadki, if koefіtsієnti tsіlovoї funktsії chi vector components obmezhen stale od yakogos one chinnika, napriklad hour, i know potrіbno rozv'yazok zadachі of whether yakoї zmіni tsogo pokaznika, yaky nazivayut zadachі parameter.

The parame- programuvannya - tse method viznachennya zalezhnostі Change log rozv'yazku zadachі od zmіni vector koefіtsієntіv tsіlovoї funktsії chi vector obmezhen.

3.7.1. Parametrichnі zmіni vector obmezhen

Rozglyanemo task lіnіynogo programuvannya in razі lіnіynoї zalezhnostі Components Connection obmezhen od vector parameter t. Nekhay:

. . . (3.65)

Todі task lіnіynogo programuvannya sformulyuєmo in viglyadі:

(3.66)

(3.67)

. (3.68)

Obviously, for scho cutaneous fіksovanogo values problem (3.66) - (3.68) Je zvichaynoyu tasks lіnіynogo programuvannya i Mauger Buti rozv'yazana simplex method.

In razі viznachennya rozv'yazku zadachі, pridatnogo for dovіlnogo mozhlivogo parameter value , Potrіbnі rozv'yazki іnodі vdaєtsya znahoditi for Relief descho vidozmіnenogo algorithm simplex method.

Nekhay . Todі zgіdno s Persha theorem dvoїstostі optimal plan pryamoї zadachі (yak i Leather threading support program) may be taxes in viglyadі:

(3.69)

de D - Matrix, scho s stock component vektorіv ostannogo basis; - Optimal zadachі plan (3.66) - (3.68); In - vector scho skladaєtsya s vіlnih chlenіv Sistemi obmezhen in ostannіy simpleksnіy tablitsі.

Otzhe, Yakscho zmіnyuyutsya components of the vector V, the value of the vector zmіnyuyutsya takozh . In vektornіy formі (3.65) Got viglyad:

(3.70)

In de - vector s components bi, and the vector P skladaєtsya s virazu component PI (3.65). Vikoristovuyuchi (3.69), maєmo:

. (3.71)

Dobutkom bude vector, through yaky poznachimo And the result of multiplication on - vector , Todі:

. (3.72)

Acceptable, scho problem (3.66) - (3.68) rozv'yazano, i'll stay simplex tableau Got views:

table 3.5

Table mіstit two dodatkovih stovpchiki scho daє zmogu stezhiti for peretvorennyami values pіslya zdіysnenih іteratsіy.

Oskіlki mіstit Table 3.5 Assumptions for optimal plan zadachі (3.66) - (3.68) Then Got vikonuvatisya Umov nevіd'єmnostі vsіh components of (3.72), otzhe,

(3.73)

Acceptable Teper scho at formulі (3.73) parameter t0 not fіksovany and Mauger nabuvati dovіlnih values on the job іntervalі [a; b]. Yakscho for vsіh Tsikh nerіvnostі parameter value (3.73) zadovolnyayutsya, tobto

(3.74)

it tse oznachaє scho znaydeny plan optimal for vsіh values Yea i rozv'yazkom parametrichnoї zadachі (3.66) - (3.68). Prote in zagalnomu vipadku let them for Pevnyi values nerіvnostі (3.73) does not zadovolnyayutsya i plan bude not optimal. Tom neobhіdno viyaviti mnozhinu vsіh values (de promіzhok [a0; b0] Mensch, nіzh [a; b]), for yakih znaydeny Je plan optimally, i, s viklyuchivshi її away rozglyadu, znahoditi optimal plan for Druha mnozhini tochok s іntervalu t i. e. Otzhe, processes rozv'yazannya parametrichnoї zadachі peredbachaє poslіdovny podіl tasks promіzhku zmіni parameter t on the number of such pіdpromіzhkіv, dwellers for vsіh values the very pіdpromіzhku optimum tsіlovoї funktsії dosyagavsya in odnіy tochtsі (vershinі) bagatogrannika planіv zadachі, ale dwellers cutaneous pіdpromіzhku zmіni parameter vіdpovіdav okremy optimal plan.

Otzhe, rozv'yazuvannya parametrichnoї zadachі (3.66) - (3.68) pochinayut s deyakogo values i zapisuyut problem (3.66) - (3.68) in viglyadі pochatkovoї simpleksnoї tablitsі, scho Got viglyad, analogіchny tablitsі 3.5. Znahodyat simplex method optimal plan zadachі (Yakscho vіn іsnuє) for danogo values ​​(Table 3.5). Zaznachimo scho value of the component in the optimum plan podaєtsya viglyadі dvoh dodankіv scho mіstyatsya in dvoh dodatkovih stovpchikah that . Zagalnі values ​​tsіlovoї funktsії optimal plan rozrahovuyut dodavannyam to sumi stovptsya sumi stovptsya , On pomnozhenoї (S zgіdno 3.72). Otzhe magnitude Je lіnіynoyu funktsієyu parameter t.

Viznachimo granitsі value of the parameter, t, for yakih vector bude optimal plan. For tsogo s ostatochnoї tablitsі 3.5 de , I skladaєmo rozv'yazuєmo nerіvnostey system (3.74). In razі іsnuvannya optimal plan when zadachі nerіvnostey system (3.74) is obviously sumіsna, oskіlki іsnuє Hoca used one її rozv'yazok. Zrozumіlo takozh, scho obov'yazkovo deyakі h , More іnakshe parametrichnoї zadachі not Bulo b. Slіd rozrіznyati two vipadki at rozv'yazannі Sistemi nerіvnostey (3.74):

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

(3.75)

scho daє bottom border Shukanov іntervalu, yak Mauger dorіvnyuvati and abo Buti Mensch for neї: a0 a.

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

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

. (3.76)

In this razі rozv'yazok Sistemi nerіvnostey daє 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 razі task rozv'yazana povnіstyu, oskіlki

.

Otzhe for verhnoї granitsі Shukanov іntervalu dіstaєmo formula:

(3.77)

Analogіchna formula for nizhnoї granitsі Got viglyad:

(3.78)

For naymenshogo vihodu value of t for mezhі viznachenogo іntervalu [a 0; b 0] to a new optimal plan bude vіd'єmnim (porushuvatimutsya minds Sistemi nerіvnostey (3.74)).

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

Dali rozglyadayut znovu nerіvnostey system (3.74). For of the formula (3.77) viznachayut upper boundary Meaning quiet, t, for yakih vіdshukany plan bude optimally. Taku procedure povtoryuyut Doty, Pokey is not otrimayut values ​​verhnoї granitsі chergovogo іntervalu, scho abo dorіvnyuє perevischuє upper boundary assignments іntervalu mozhlivih values t, tobto

. (3.79)

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

Otzhe, promіzhok jobs [a; b] podіlyayut a number іntervalіv [a; b0], [b 1; b 2], ... [bs- 1; b], for the skin s yakih maximum tsіlovoї funktsії dosyagaєtsya for vіdpovіdnogo Yomou one optimal plan.