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

Ically mathematical programuvannya - Nakonechny S.І.

2.8.6. The method of block basis

In poperednіh paragraphs rozglyadavsya vipadok, if the system obmezhen zadachі lіnіynogo programuvannya mіstila odinichnu matrix of order m. Prote bіlshіst tasks not mozhna zvesti to potrіbnogo viglyadu. In this method razі zastosovuєtsya piece basis.

Rozglyanemo task lіnіynogo programuvannya:

(2.60)

(2.61)

(2.62)

The challenge filed kanonіchnomu viglyadі i obmezhen system (2.61) is not mіstit odinichnoї matritsі. Otrimati odinichnu matrix can, Yakscho to skin rіvnyannya in sistemі obmezhen zadachі Add your one zmіnnu . Takі zmіnnі nazivayut boxed. (Not obov'yazkovo Quantity introduction of boxed zmіnnih Got dorіvnyuvati m. Їh neobhіdno vvoditi deprivation in Ti rіvnyannya Sistemi obmezhen, SSMSC not rozv'yazanі vіdnosno the basal zmіnnih.) Is permissible, scho rіvnyan system (2.61) is not mіstit zhodnogo odinichnogo vector todі boxed zmіnnu introducing in cutaneous rіvnyannya:

(2.63)

In rezultatі dodavannya zmіnnih rіvnyannya in the system (2.61), the range of permissible rozv'yazkіv zadachі rozshirilas. Task s system obmezhen (2.63) nazivayut rozshirenoyu, abo M tasks. Rozv'yazok rozshirenoї zadachі zbіgatimetsya s rozv'yazkom pochatkovoї deprivation of minds, scho OAO All vvedenі shtuchnі zmіnnі in optimal planі zadachі will vivedenі s basis, tobto dorіvnyuvatimut nulevі. Todі obmezhen system (2.63) Naboodah viglyadu (2.61) (not boxed mіstitime zmіnnih) and rozv'yazok rozshirenoї zadachі bude i rozv'yazkom zadachі (2.60) - (2.62).

Zgіdno s simplex method before introducing zmіnnі basis, SSMSC pokraschuyut values ​​tsіlovoї funktsії. For danoї zadachі to maximum stench yogo zbіlshuvati toil. Otzhe, for dwellers in rezultatі procedures Simplex peretvoren viklyuchalisya s basis shtuchnі zmіnnі, potrіbno enter їh in tsіlovu funktsіyu s vіd'єmnimi koefіtsієntami. Tobto tsіlova funktsіya Naboodah viglyadu:

(In razі rozv'yazannya zadachі on vіdshukannya mіnіmalnogo values ​​tsіlovoї funktsії introducing koefіtsієnti, SSMSC Je dosit great numbers Tsіlova funktsіya todі Got viglyad.: ).

Pripuskaєtsya scho value of M Je dosit great number. Todі yakogo used small value not nabuvala vіdpovіdna koefіtsієntu unit-load zmіnna , Values ​​tsіlovoї funktsії bude vіd'єmnim zadachі to a maximum that dodatnim for zadachі on mіnіmum i vodnochase digit of the module. Tom procedure simplex method odrazu viluchaє vіdpovіdnі basis zmіnnі s i zabezpechuє znahodzhennya plan Where Money Does OAO All shtuchnі zmіnnі .

Yakscho in optimal planі rozshirenoї zadachі іsnuє Hoch b odne values Then oznachaє Tse, scho not Got Pochatkova task rozv'yazku, tobto obmezhen nesumіsna system.

For rozv'yazannya rozshirenoї zadachі for Relief simplex tableau zruchno vikoristovuvati tablitsі, otsіnkovі rows yakih podіlenі on Dvi Chastain-rows. Todі in the (m + 2) th row zapisuyut koefіtsієnti h M, and (m + 1) th - Ti, SSMSC not mіstyat M. Vector, yaky pіdlyagaє on until basis, viznachayut for the (m + 2) th row. Іteratsіyny processes for the (m + 2) th row to the conductive Povny viklyuchennya vsіh boxed zmіnnih s basis, potіm processes viznachennya prodovzhuyut optimal plan for (m + 1) -im row.

Vzaєmozv'yazok mіzh rozv'yazkami pochatkovoї that rozshirenoї tasks lіnіynogo programuvannya not Yea i viznachaєtsya Obviously with such a theorem.

Theorem 2.8. Yakscho in optimal planі rozshirenoї zadachі shtuchnі zmіnnі , The plan Je optimal plan pochatkovoї zadachі.

BROUGHT. Zaznachimo, scho if plan Je optimal plan rozshirenoї zadachі, the plan - Plan pochatkovoї zadachі. When tsomu

.

Dovedemo scho plan - Optimal plan pochatkovoї zadachі. Acceptable, scho Yea not optimal plan. Todі іsnuє Taqiy optimal plan For yakogo . Zvіdsi for vector Scho Yea plan rozshirenoї zadachі, maєmo:

.

tobto

.

Otzhe plan Je rozshirenoї zadachі not optimal, scho superechit umovі theorem and assumptions that zroblene schodo neoptimalnostі plan Je wrong.

Otzhe, zagalom algorithm rozv'yazuvannya zadachі lіnіynogo programuvannya simplex method skladaєtsya s p'yati etapіv:

1. Viznachennya Pochatkova support plan zadachі lіnіynogo programuvannya.
2. Pobudova simpleksnoї tablitsі.
3. Perevіrka support plan for optimalnіst for Relief otsіnok . Yakscho OAO All otsіnki zadovolnyayut optimalnostі minds, the basic plan viznacheny Je zadachі optimal plan. Yakscho Hoch b a s otsіnok not zadovolnyaє optimalnostі minds, then transitioning to the new support plan vstanovlyuyut abo scho optimal plan zadachі not іsnuє.
4. Perehіd to the new support plan zadachі zdіysnyuєtsya viznachennyam rozv'yazuvalnogo Elements that rozrahunkami elementіv novoї simpleksnoї tablitsі.
5. Repetition Act reasonably, pochinayuchi s n. 3.

Dali іteratsіyny processes povtoryuyut, docks not bude viznacheno zadachі optimally plan.

In razі zastosuvannya simplex method for rozv'yazuvannya tasks lіnіynogo programuvannya mozhlivі takі vipadki.

1. Yakscho in otsіnkovomu row ostannoї simpleksnoї tablitsі otsіnka vіdpovіdaє vіlnіy (nebazisnіy) zmіnnіy then oznachaє Tse, scho problem lіnіynogo programuvannya Got alternative optimal plans. Otrimati yogo possible, vibrat rozv'yazuvalny yelement in zaznachenomu stovpchiku tablitsі that zdіysnivshi one Krok simplex method.

2. Yakscho at perehodі in simplex metodі od a reference to the plan zadachі іnshogo in napryamnomu stovpchiku Absent dodatnih elementіv , Tobto nemozhlivo vibrato zmіnnu, yak Got Booty vivedena s basis, the tse oznachaє scho tsіlova funktsіya zadachі lіnіynogo programuvannya Je neobmezhenoyu th optimally planіv not іsnuє.

3. Yakscho to support the plan zadachі lіnіynogo programuvannya OAO All otsіnki zadovolnyayut minds optimalnostі, ale at tsomu Hoch used a unit-load of basis zmіnna Yea i Got dodatne value, oznachaє Tse, scho system obmezhen zadachі nesumіsna th optimally planіv takoї zadachі not іsnuє.

Rozv'yazati problem s butt 2.10 іz dodatkovoyu minds: With Produkciya Got vigotovlyatisya obsyagom not Mensch yak 9 odinits.

Rozv'yazannya. Ically mathematical model sformulovanoї zadachі zapishemo as follows:

Zastosovuyuchi for rozv'yazuvannya postavlenoї zadachі simplex method, spochatku zapishemo obmezhen system in kanonіchnіy formі:

Zauvazhimo scho nerіvnіst type "≥" peretvoryuєmo in rіvnyannya administration in lіvu Chastain obmezhennya dodatkovoї zmіnnoї Zi sign "-".

mіstit deprivation System odinichnі two vectors - that And the basis in trivimіrnomu prostorі Got skladatisya s troh odinichnih vektorіv. Sche one odinichny vectors can dіstati, uvіvshi in tretє obmezhennya koefіtsієntom s + 1 PIECE zmіnnu x 8 yakіy vіdpovіdatime odinichny vector .

Now we can rozglyanuti rozshirenu task lіnіynogo programuvannya:

of minds:

On vіdmіnu od dodatkovih zmіnnih unit-load zmіnna x 8 Got in tsіlovіy funktsії koefіtsієnt Z + M (for zadachі to min) abo - M (for zadachі on max), de M - dosit bike dodatne number.

At the basal rozshirenіy zadachі zmіnnimi Je x 5, x 6, 8 x and Rasht zmіnnih vіlnі. Pochatkova support program zadachі Taqiy:

Sklademo Perche simplex tableau tsієї zadachі:

Rozrahovuyuchi otsіnki Perche support plan dіstaєmo: Z 0 = -9 M; Z 1 - c1 = -8; Z 2 - c2 = -10, Z 3 - c3 = - M i, etc. Otzhe, mi otrimuєmo otsіnki dvoh vidіv:.. Odnі s them mіstyat M and INSHI Je zvichaynimi numbers. Tom for zruchnostі rozdіlimo otsіnkovy row two. We'll Purshia otsіnkovy row zapisuvati zvichaynі number, and in the other - the number of h koefіtsієntom M.

Otsіnki Perche plan not zadovolnyayut optimalnostі minds, that i vіn Je suboptimal. Zgіdno s algorithm rozglyanutim in zadachі 2.41 vikonuєmo perehіd to the following reference zadachі plan. Pіslya pershoї іteratsії s unit-load basis vivedena zmіnna x 8. Further rozv'yazuvannya prodovzhuєmo of the simplex algorithm.

Nastupnі sketch rozv'yazuvannya zadachі navedenі in zagalnіy tablitsі:

Optimal plan zadachі Je vector:

X * = (57; 100; 9; 0; 0; 0; 0)

Otzhe optimally Je virobnitstvo 57 odinits produktsії A 100 odinits produktsії The i 9 odinits produktsії S. Todі Prybutok bude i naybіlshim stanovitime 1456 UAH.

Fіnansovі resources fіrmi mozhut vikoristovuvatisya vkladennya to have two projects. During the project іnvestuvannya A garantuєtsya otrimannya through Year pributku in rozmіrі 60 kopecks. on skin vkladenu hryvnia, and the project in vkladennya daє zmogu otrimati dohіd in rozmіrі UAH 2 on skin іnvestovanu hryvnia, ale two prophets. For fіnansuvannya project in perіod іnvestuvannya Got Booty multiples EYAD. Viznachiti, yak potrіbno rozporyaditisya kapіtalom sumі at 100 000 UAH, dwellers maksimіzuvati zagalny penny dohіd, yaky mozhna otrimati three prophets pіslya іnvestuvannya cob.

Rozv'yazannya. Nekhay xij - rozmіr vkladenih koshtіv at i-th rotsі in project j (i = ; j = 1, 2). Pobuduєmo umovnu scheme rozpodіlu penny koshtіv protyagom troh rokіv.

Zgіdno s guidance scheme can zapisati ically mathematical model zadachі.

Tsіlova funktsіya: Penny dohіd fіrmi pіslya troh rokіv іnvestitsіy

.

Obmezhennya modelі sformulyuєmo zgіdno minds with such a s: rozmіr koshtіv, іnvestovanih in inline rotsі not Mauger perevischuvati sumi zalishku koshtіv passed rock that income for Gone Year:

for the 1st rock ;

for the 2nd rock ;

for the 3rd rock .

Vikonavshi elementarnі peretvorennya, dіstanemo obmezhen system:

Otzhe, ekonomіko-ically mathematical model sformulovanoї zadachі Got Taqiy viglyad:

of minds:

Obviously, scho tsya problem Je tasks lіnіynogo programuvannya i її mozhna rozv'yazati simplex method. Zgіdno s algorithm neobhіdno zvesti system obmezhen zadachі to kanonіchnoї form. Tse vikonuєtsya for Relief dodatkovih zmіnnih x 1, x 2, x 3 that, SSMSC vvedemo Zi "+" sign to lіvoї Chastain vsіh vіdpovіdnih obmezhen. In tsіlovіy funktsії zadachі tsі zmіnnі toil koefіtsієnt scho dorіvnyuє zero.

Rozv'yazuvannya zadachі imposed in viglyadі simpleksnoї tablitsі:

Optimally Je Taqiy plan:

For this plan іnvestuvan

Ale task Got ot the optimal plan, yaky mozhna dіstati, vibrat rozv'yazuvalny yelement in stovpchiku "x 12" ostannoї simpleksnoї tablitsі. Tse Mauger Buti abo number 1, abo 1.6. Vіzmemo yak rozv'yazuvalny yelement 1. Vikonavshi one Krok peretvoren simplex method, dіstanemo Taku friend kіntsevu simplex tableau:

Zvіdsi:

Zobrazimo vikoristannya penny koshtіv fіrmi Perche for the optimal plan at zadachі viglyadі scheme:

Zgіdno s rozglyanutoyu Purshia the scheme of the optimal plan іnvestuvannya peredbachaє on Purshia Year usі Costa obsyagom 100,000 USD vklasti in project A, scho will give zmogu win a Prybutok obsyagom 60 000 USD, and in som zagalna kіntsі rock stanovitime 160 thousand UAH. On the other usі Year in Costa rozmіrі 160,000 USD peredbachaєtsya vitratiti fіnansuvannya on project B. Naprikіntsі another rock FIRMA pributku not otrimaє. On tretіy Year fіnansuvannya proektіv not peredbachaєtsya, ale in kіntsі rock Prybutok fіrmi od minulorіchnih іnvestitsіy project in stanovitime 320,000 USD, and zagalny penny dohіd - 480 000 UAH.

Taqiy same maximum dohіd mozhna mother, provіvshi іnvestitsії of scheme:

Zgіdno s other optimal plans at Perche rotsі FIRMA spryamovuє all kapіtal in rozmіrі 100,000 USD for the project fіnansuvannya B. Tse umozhlivit obsession trumpery income deprivation naprikіntsі another rock obsyagom 300 thousand UAH, SSMSC on tretіy Year povnіstyu іnvestuyutsya in the project A. Zagalny penny dohіd fіrmi three prophets dіyalnostі for CIM varіantom takozh stanovitime 480 thousand UAH.

Yakscho yak rozv'yazuvalny yelement in ostannіy simpleksnіy tablitsі take the number 1.6, the matimemo tretіy optimal plan:

Produkciya factory vipuskaєtsya in viglyadі paperovih rulonіv standartnoї width - 2 m. For spetsіalnim of order spozhivachіv factory postachaє takozh rolls іnshih rozmіrіv, rozrіzuyuchi standartnі.

Tipovі of order on the roll of non-standard rozmіrіv imposed in the Table. 2.9.

table 2.9

Of order on a roll Paper the

Neobhіdno viznachiti optimally varіant rozkroyu rulonіv the standard for yakogo spetsіalnі of order, scho nadhodyat, zadovolnyayut povnіstyu s mіnіmalnimi vіdhodami Papero.

Rozv'yazannya. Abi vikonati spetsіalnі of order, SSMSC nadіyshli, rozglyanemo p'yat mozhlivih varіantіv rozrіzuvannya STANDARD rulonіv, scho shaping can vikoristovuvatisya in rіznih kombіnatsіyah. Varіanti rozkroyu imposed in the Table. 2.10.

table 2.10

MOZHLIVІ VARІANTI ROZRІZUVANNYA STANDARD RULONІV Paper the

Nekhay xj - Quantity of standard rulonіv Papero, SSMSC bude rozrіzano j-way, .

Obmezhennya zadachі pov'yazanі s obov'yazkovoyu vimogoyu Povny zabezpechennya neobhіdnoї kіlkostі Precarious rulonіv for spetsіalnimi of order. Yakscho Braty to uwagi OAO All podanі in tablitsі Method rozkroyu then dіstanemo takі Minds (obmezhennya) danoї zadachі:

1. schodo kіlkostі rulonіv width of 0.8 m:

2 x 1 + x 2 + x 3 = 150.

2. schodo kіlkostі rulonіv 1 m width:

x 2 + 3 x 4 = 200.

3. Stosovno kіlkostі rulonіv width of 1.2 m:

x 2 + x 5 = 300.

Tsіlova funktsіya zadachі - tse mіnіmalnі zagalnі vtrati Paper the pid hour rozrіzuvannya STANDARD rulonіv nestandartnoї on roll width. Ically mathematical Won Got Taqiy viglyad:

.

Ically mathematical model zadachі zagalom zapisuєtsya as follows:

of minds:

For rozv'yazuvannya tsієї zadachі zastosuєmo algorithm simplex method. Oskіlki task sformulovano in kanonіchnіy formі, zapishemo її vіdrazu in vektornіy formі:

de

In sistemі vektorіv maєmo deprivation one odinichny vector . Tom Pershe in that other obmezhennya vvedemo shtuchnі zmіnnі x 6 x 7 Rozshirena that task matim viglyad:

of minds:

Process rozv'yazannya zadachі simplex method filed in viglyadі tablitsі:

Zgіdno s ostannoyu simplex tableau zapishemo zadachі optimally plan:

X * = (0, 150, 0, 100, 150), min Z = 120.

Viznacheny peredbachaє optimally plan: dwellers have Povny obsyazі vikonati spetsіalnі of order, SSMSC nadhodyat on paperovu factory neobhіdno rozrіzati 150 standard rulonіv other way rulonіv 100 - 150 of the fourth i - p'yatim. For this optimal varіanta rozkroyu obsyag vіdhodіv Paper the Buda naymenshim stanovitime i 120 m.