Paprastųjų lygčių sprendimas pavyzdiniu metodu. Gamybos uždavinio sprendimas lentelių simplekso metodu. Rezoliucijos eilutės konvertavimas

Paprastas metodas− tai tvarkingo etaloninių planų surašymo metodas (tvarkingumą užtikrina monotoniškas tikslo funkcijos reikšmės pokytis pereinant prie kito plano). Šiuo atveju būtina laikytis principo: kiekvienas kitas žingsnis turi pagerinti arba, kraštutiniais atvejais, nepabloginti tikslo funkcijos vertės.

Norėdami išspręsti ZLP simplekso metodas ji perkeliama į kanoninę formą, t.y. Iš apribojimų – nelygybių – reikia daryti apribojimus – lygybę. Norėdami tai padaryti, į kiekvieną apribojimą įvedamas papildomas neneigiamas veiksnys balanso kintamasis su „+“ ženklu, jei nelygybės ženklas yra „£“, ir su „–“ ženklu, jei nelygybės ženklas yra „³“.

Tikslinėje funkcijoje šie papildomi kintamieji įtraukiami su nuliniais koeficientais, t.y. tikslo funkcijos įrašas nepasikeis. Kiekvienas kintamasis, kuriam netaikoma neneigiamumo sąlyga, gali būti pavaizduotas kaip dviejų neneigiamų kintamųjų skirtumas: .

Jei užduoties apribojimai atspindi išteklių prieinamumą ir suvartojimą, tai papildomo kintamojo skaitinė reikšmė užduoties plane, įrašyta kanonine forma, yra lygi nepanaudotų išteklių kiekiui.

Norėdami išspręsti problemą naudodami simplekso metodą, naudosime sutrumpintos tiesinių lygčių sistemų simpleksinės lentelės ir modifikuotas Jordano eliminacijos metodas.

1. Pirmojo orientacinio plano sudarymas

Užduotis išlieka ta pati. Įveskime standartinę nelygybių sistemos formą (1) į kanoninę lygčių sistemos formą, įvesdami papildomus balanso kintamuosius x 3 , x 4 , x 5 ,x 6 .

Ekonomine prasme papildomų kintamųjų reikšmės x 3 , x 4 , x 5 nustatyti likusias žaliavas pardavus produkciją.

Gautos lygčių sistemos matrica yra tokia:

Tai matyti matricoje A 4 eilės bazinis minoras yra determinantas, sudarytas iš papildomų kintamųjų vienetų koeficientų x 3 , x 4 , x 5 ,x 6, nes jis skiriasi nuo nulio ir lygus 1. Tai reiškia, kad šių kintamųjų stulpelių vektoriai yra tiesiškai nepriklausomi, t.y. forma pagrindu, ir atitinkamus kintamuosius x 3 , x 4 , x 5 ,x 6 yra pagrindinis(pagrindinis). Kintamieji x 1 , x 2 bus iškviestas nemokamai(nepagrindinis).

Jei laisvi kintamieji x 1 ir x 2 nustatykite skirtingas reikšmes, tada, išspręsdami sistemą pagrindinių kintamųjų atžvilgiu, gauname begalinį dalinių sprendinių skaičių. Jei laisviesiems kintamiesiems suteikiamos tik nulio reikšmės, tada galima pasirinkti iš begalinės konkrečių sprendimų aibės pagrindiniai sprendimai– pagrindiniai planai.

Norint išsiaiškinti, ar kintamieji gali būti pagrindiniai, reikia apskaičiuoti determinantą, susidedantį iš šių kintamųjų koeficientų. Jei šis determinantas nėra lygus nuliui, šie kintamieji gali būti pagrindiniai.

Pagrindinių sprendinių skaičius ir atitinkamas pagrindinių kintamųjų grupių skaičius gali būti ne didesnis kaip , kur n– bendras kintamųjų skaičius, r– pagrindinių kintamųjų skaičius, r≤ m≤ n.

Dėl mūsų užduoties r = 4; n= 6. Tada , t.y. Galima 15 grupių po 4 pagrindinius kintamuosius (arba 15 pagrindinių sprendinių).

Išspręskime pagrindinių kintamųjų lygčių sistemą x 3 , x 4 , x 5 ,x 6:

Darant prielaidą, kad laisvieji kintamieji x 1 = 0, x 2 = 0, gauname pagrindinių kintamųjų reikšmes: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = –10, t.y. pagrindinis sprendinys bus = (0; 0; 312; 15; 24; –10).

Šis pagrindinis sprendimas yra nepriimtina, nes x 6 = –10 ≤ 0, ir pagal apribojimų sąlygas x 6 ≥ 0. Todėl vietoj kintamojo x 6 kaip pagrindą reikia paimti kitą kintamąjį iš laisvųjų x 1 arba x 2 .

Tolesnį sprendimą atliksime sutrumpintomis simpleksinėmis lentelėmis, pirmosios lentelės eilutes užpildydami sistemos koeficientais (1 lentelė):

1 lentelė

F- vadinama linija indeksas. Jis užpildytas tikslo funkcijos koeficientais, paimtais priešingais ženklais, nes funkcijos lygtis gali būti pavaizduota forma F = 0 – (– 4x 1 – 3x 2).

Nemokamų narių stulpelyje b i yra neigiamas elementas b 4 = –10, t.y. Sistemos sprendimas netinkamas. Norint gauti įmanomą sprendimą (orientacinį planą), elementas b 4 turi būti neneigiamas.

Pasirinkite x 6 eilutė su neigiamu laisvuoju terminu. Šioje eilutėje yra neigiamų elementų. Pasirinkite bet kurį iš jų, pavyzdžiui, „–1“. x 1 -stulpelis ir x 1 stulpelis laikomas kaip rezoliucijos stulpelis(jis nustatys, kad kintamasis x 1 pereis iš nemokamos į paprastą).

Mes skirstome laisvus narius b iį atitinkamus elementus a yra rezoliucijos stulpelį, gauname vertinamieji santykiaiΘ i= = (24, 15, 12, 10). Iš jų pasirenkame mažiausią teigiamą (minΘ i=10), kuris atitiks leidimo eilutė. Įgalinimo eilutė apibrėžia kintamąjį x j, kuri kitame žingsnyje išsikiša iš pagrindo ir tampa laisva. Štai kodėl x 6 eilutės yra įgalinimo eilutė, o elementas „–1“ yra leistinas elementas. Apveskime jį ratu. Kintamieji x 1 ir x 6 yra sukeisti.

Apskaičiuoti santykiai Θ i kiekvienoje eilutėje nustatomos pagal taisykles:

1) Θ i= jei b i Ir a yra turėti skirtingus ženklus;

2) Θ i= ∞, jei b i= 0 ir a yra < 0;

3) Θ i= ∞, jei a yra = 0;

4) Θ i= 0, jei b i= 0 ir a yra > 0;

5)Θ i= jei b i Ir a yra turi tuos pačius ženklus.

Atliekame modifikuoto Jordano pašalinimo (JEME) žingsnį su skiriamuoju elementu ir sudarome naują lentelę (2 lentelė) pagal šią taisyklę:

1) vietoje skiriamojo elemento (RE) nustatoma reikšmė, kuri yra atvirkštinė, t.y. ;

2) įgalinančios eilutės elementai skirstomi į RE;

3) rezoliucijos stulpelio elementai skirstomi į RE ir keičiasi ženklas;

4) likę elementai randami pagal stačiakampio taisyklę:

Nuo stalo 2 aišku, kad nemokamos sąlygos b i-stulpeliai yra neneigiami, todėl gaunamas pradinis galimas sprendimas - pirmasis orientacinis planas= (10; 0; 182; 5; 4; 0). Šiuo atveju funkcijos reikšmė F() = 40. Geometriškai tai atitinka viršų F(10; 0) sprendinio daugiakampis (1 pav.).

2 lentelė

2. Patikriname plano optimalumą. Referencinis planas nėra optimalus, nes m F-eilutė turi neigiamą koeficientą „–4“. Patobuliname planą.

3. Naujo orientacinio plano radimas

Mes pasirenkame leidžiantį elementą pagal taisyklę:

Mes pasirenkame mažiausią neigiamą koeficientą in F- eilutė „–4“, kuri apibrėžia įgalinimo stulpelį – x 6; kintamasis x 6 konvertuojami į pagrindinius;

Ryšių Θ radimas i, tarp jų pasirenkame mažiausią teigiamą, atitinkantį skiriamąją gebą:

min Θ i = min(14, 5, 2, ∞) = 2, todėl x 5 eilučių – įgalinantis, kintamasis x 5 konvertuojami į nemokamus (kintamieji x 5 ir x 6 yra sukeisti).

Skiriamosios eilutės ir stulpelio sankirtoje yra skiriamasis elementas „2“;

Atliekame SMGI žingsnį ir pastatome stalą. 3 pagal aukščiau pateiktą taisyklę ir gauname naują atskaitos planą = (12; 0; 156; 3; 0; 2).

3 lentelė

4. Naujo orientacinio plano optimalumo patikrinimas

Referencinis planas taip pat nėra optimalus, nes m F-eilutė turi neigiamą koeficientą „–1“. Funkcijos reikšmė F() = 48, kuris geometriškai atitinka viršūnę E(12; 0) sprendinio daugiakampis (1 pav.). Patobuliname planą.

5. Naujo orientacinio plano radimas

x 2 stulpelis yra leistinas, nes F-eilutė, mažiausias neigiamas koeficientas „–1“. x 2 stulpelis (Δ 2 = –1). Randame mažiausią Θ i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, todėl x 4 eilučių – leistinas. Rezoliucijos elementas "1/2". Keisti kintamuosius x 2 ir x 4. Atliekame SMGI žingsnį ir pastatome stalą. 4, gauname naują atskaitos planą = (9; 6; 51; 0; 0; 5).

6. Referencinio plano optimalumo tikrinimas

IN F-linija, visi koeficientai neneigiami, todėl atskaitos planas optimalus. Geometriškai atitinka tašką D(9;6) (žr. 1 pav.). Optimalus planas suteikia maksimalią tikslo funkcijos reikšmę c.u.

Simplex metodas linijinio programavimo uždaviniams spręsti

1. Įvadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 puslapis

2. Simpleksinis metodas linijinio programavimo uždaviniams spręsti. . . 4-10 puslapių

3. Simpleksinio metodo algoritmas tiesinio programavimo uždaviniams spręsti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 puslapis

4. Uždavinio sprendimo simplekso metodu pavyzdys. . . . . . . . . . . . . . . . . . 11-15 puslapių

5. Išvada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16psl

6.Naudotų nuorodų sąrašas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17psl

1. Įvadas

Darbas skirtas dažniausiai pasitaikančiam linijinio programavimo uždavinio sprendimo būdui (simpleksiniam metodui). Simpleksinis metodas yra klasikinis ir labiausiai išvystytas linijinio programavimo metodas. Tai leidžia per ribotą skaičių žingsnių arba rasti optimalų sprendimą, arba nustatyti, kad optimalaus sprendimo nėra.

Suformuluotas uždavinio sprendimo algoritmas ir iliustruojamas pavyzdžiu.

1. Nurodykite optimalaus pamatinio sprendimo būdą

2. Nurodykite perėjimo nuo vieno pamatinio sprendinio prie kito metodą, kuriam esant tikslo funkcijos reikšmė bus arčiau optimalios, t.y. nurodyti būdą, kaip patobulinti pamatinį sprendimą

3. Nustatyti kriterijus, kurie leistų operatyviai nutraukti pagalbinių sprendimų paiešką prie optimalaus sprendimo arba padaryti išvadą apie optimalaus sprendimo nebuvimą.

2. Simpleksinis metodas linijinio programavimo uždaviniams spręsti aš

Simpleksinis metodas linijinio programavimo uždaviniams spręsti (simplex metodas) yra skaičiavimo procedūra, pagrįsta nuoseklaus sprendinių tobulinimo principu – perėjimu iš vieno bazinio taško į kitą, kurio tikslo funkcijos reikšmė yra didesnė (šios operacijos fiksuojamos simplekso lentelę).

Šis metodas yra kryptingo linijinio programavimo uždavinio pamatinių sprendimų surašymo metodas. Tai leidžia per ribotą skaičių žingsnių arba rasti optimalų sprendimą, arba nustatyti, kad optimalaus sprendimo nėra. Įrodyta, kad jei yra optimalus sprendimas, tai jis tikrai bus rastas po baigtinio žingsnių skaičiaus (išskyrus vadinamąją išsigimusią problemą, kurioje galimas „važinėjimo dviračiu“ fenomenas, t. y. pasikartojantis grįžimas į ta pati padėtis).

Simpleksinis metodas yra pagrindinis linijinio programavimo metodas. Problemos sprendimas pradedamas nagrinėjant vieną iš sąlygų daugiakampio viršūnių. Jei tiriama viršūnė neatitinka maksimumo (minimumo), tada jie pereina į gretimą, padidindami tikslo funkcijos reikšmę sprendžiant uždavinį maksimaliai ir sumažindami sprendžiant užduotį už minimumą. Taigi, perėjimas iš vienos viršūnės į kitą pagerina tikslo funkcijos reikšmę. Kadangi daugiakampio viršūnių skaičius yra ribotas, baigtiniu žingsnių skaičiumi garantuojama rasti optimalią reikšmę arba nustatyti faktą, kad problema yra neišsprendžiama.

Šis metodas yra universalus, taikomas bet kokiai linijinio programavimo problemai kanonine forma. Apribojimų sistema čia yra tiesinių lygčių sistema, kurioje nežinomųjų skaičius yra didesnis už lygčių skaičių. Jei sistemos rangas yra r, tai galime pasirinkti r nežinomųjų, kuriuos išreiškiame likusiais nežinomaisiais. Tikslumui darome prielaidą, kad pasirenkami pirmieji iš eilės nežinomieji X1, X2, ..., Xr. Tada mūsų lygčių sistemą galima parašyti kaip

Bet kuri nuosekli sistema gali būti sumažinta iki šios formos, pavyzdžiui, naudojant Gauso metodą. Tiesa, ne visada tai įmanoma išreikšti likusiais pirmaisiais r nežinomaisiais (tai padarėme dėl žymėjimo apibrėžtumo). Tačiau tokių nežinomųjų tikrai bus. Šie nežinomieji (kintamieji) vadinami pagrindiniais, likusieji yra nemokami.

Priskirdami tam tikras reikšmes laisviesiems kintamiesiems ir apskaičiavę pagrindinių (išreikštų laisvaisiais) reikšmes, gausime skirtingus savo apribojimų sistemos sprendimus. Taigi galima gauti bet kokį sprendimą. Mus domina specialūs sprendimai, gauti tuo atveju, kai laisvieji kintamieji lygūs nuliui. Tokie sprendimai vadinami baziniais, jų yra tiek, kiek yra skirtingų pagrindinių tam tikros apribojimų sistemos tipų. Pagrindinis sprendimas vadinamas leistinu baziniu sprendimu arba pamatiniu sprendimu, jei jo kintamųjų reikšmės yra neneigiamos. Jei kintamieji X1, X2, ..., Xr yra pagrindiniai, tada sprendinys (b1, b2,..., br, 0, ..., 0) bus atskaitos taškas, jei b1, b2,... , br ≥ 0.

Simplekso metodas pagrįstas teorema, vadinama pagrindine simplekso metodo teorema. Tarp optimalių kanoninės formos linijinio programavimo problemos planų būtinai yra jos apribojimų sistemos pamatinis sprendimas. Jei optimalus problemos planas yra unikalus, tai jis sutampa su kokiu nors etaloniniu sprendimu. Yra ribotas skaičius skirtingų suvaržymų sistemos palaikančių sprendimų. Todėl problemos sprendimo kanonine forma galima būtų ieškoti ieškant pamatinių sprendimų ir iš jų pasirenkant tą, kurio F reikšmė yra didžiausia. Bet, pirma, visi pamatiniai sprendimai yra nežinomi ir juos reikia rasti, antra, realiose problemose šių sprendimų yra daug ir tiesioginė paieška sunkiai įmanoma. Simpleksinis metodas yra tam tikra kryptingo pagalbinių sprendimų surašymo procedūra. Remdamiesi tam tikru pamatiniu sprendimu, iš anksto surastu naudojant tam tikrą simplekso metodo algoritmą, apskaičiuojame naują etaloninį sprendimą, kuriame tikslo funkcijos F reikšmė yra ne mažesnė nei senosios. Atlikę keletą veiksmų, pasiekiame pamatinį sprendimą, kuris yra optimalus planas.

Taigi simplekso metodas įveda tam tikrą tvarką tiek ieškant pirmojo (pradinio) pagrindinio sprendimo, tiek pereinant prie kitų pagrindinių sprendinių.

Uždavinio sprendimo simplekso metodu įgyvendinimas aiškiai parodytas blokinėje schemoje (1 pav.).

Taigi simpleksinio metodo taikymas skirstomas į du etapus: leistino pagrindinio apribojimų sistemos sprendimo suradimas arba jo nesuderinamumo fakto nustatymas; rasti optimalų sprendimą. Be to, kiekvienas etapas gali apimti kelis etapus, atitinkančius vieną ar kitą pagrindinį sprendimą. Tačiau kadangi pagrindinių sprendimų skaičius visada yra ribotas, simpleksinio metodo žingsnių skaičius taip pat yra ribotas.

Pateiktoje simplekso metodo diagramoje aiškiai išreiškiamas jo algoritminis pobūdis (aiškios instrukcijos dėl nuoseklių operacijų vykdymo pobūdis), leidžianti sėkmingai programuoti ir įdiegti šį metodą kompiuteryje. Problemas, susijusias su nedideliu kintamųjų ir apribojimų skaičiumi, galima išspręsti rankiniu būdu, naudojant simplekso metodą.

Apibūdinkime jo skaičiavimo pusę. Skaičiavimai, naudojant simplekso metodą, yra suskirstyti į simplex lenteles, kurios yra sutrumpintas linijinio programavimo problemos vaizdas kanonine forma. Prieš sudarant simpleksinę lentelę, uždavinys turi būti transformuotas, suvaržymų sistema perkeliama į priimtiną pagrindinę formą, kurios pagalba pagrindiniai kintamieji turi būti pašalinti iš tikslo funkcijos. Šių preliminarių transformacijų klausimą nagrinėsime toliau. Dabar manysime, kad jie jau buvo atlikti, o užduoties forma yra tokia:

Čia, siekiant žymėjimo apibrėžtumo, daroma prielaida, kad kintamieji X1, X2, ..., Xr gali būti laikomi pagrindiniais kintamaisiais ir kad b1, b2,..., br ≥ 0 (atitinkamas pagrindinis sprendimas yra nuoroda).

Norint sudaryti simpleksinę lentelę visose uždavinio teiginio lygybėse, terminai, turintys kintamuosius, perkeliami į kairę pusę, laisvieji paliekami dešinėje, t.y. problema parašyta lygybių sistemos forma:

Pastaba. Pagrindinių kintamųjų pavadinimai čia paimti tik dėl aiškumo ir tikrojoje lentelėje gali atrodyti kitaip.

Darbo su simpleksine lentele procedūra. Pirmoji simpleksinė lentelė patiria transformaciją, kurios esmė yra perėjimas prie naujo pamatinio sprendimo.

Perėjimo prie kitos lentelės algoritmas yra toks:

peržvelgiama paskutinė lentelės eilutė (indeksas) ir tarp šios eilutės koeficientų (išskyrus laisvųjų terminų stulpelį) pasirenkamas mažiausias neigiamas skaičius ieškant max, arba didžiausias teigiamas skaičius ieškant min. Jei jo nėra, tada originalus pagrindinis sprendimas yra optimalus ir ši lentelė yra paskutinė;

peržiūrimas lentelės stulpelis, atitinkantis pasirinktą neigiamą (teigiamą) koeficientą paskutinėje eilutėje - raktinis stulpelis, ir šiame stulpelyje pasirenkami teigiami koeficientai. Jei jų nėra, tai tikslinė funkcija yra neribota leistinų kintamųjų reikšmių diapazone ir problema neturi sprendimų;

Iš pasirinktų stulpelio koeficientų pasirenkamas tas, kuriam atitinkamo laisvojo nario (esančio laisvųjų terminų stulpelyje) santykio su šiuo elementu absoliuti reikšmė yra minimali. Šis koeficientas vadinamas skiriamuoju koeficientu, o eilutė, kurioje jis yra, yra pagrindinė;

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Įspėjimas

Išvalyti visas ląsteles?

Uždaryti Išvalyti

Duomenų įvedimo instrukcijos. Skaičiai įvedami kaip sveikieji skaičiai (pavyzdžiai: 487, 5, -7623 ir tt), dešimtainiai (pvz., 67., 102,54 ir kt.) arba trupmenos. Trupmena turi būti įvedama a/b forma, kur a ir b (b>0) yra sveikieji arba dešimtainiai skaičiai. Pavyzdžiai 45/5, 6.6/76.4, -7/6.7 ir kt.

Paprastas metodas

ZLP sprendimo pavyzdžiai naudojant simplekso metodą

1 pavyzdys. Išspręskite šią linijinio programavimo problemą:

Dešinė lygčių sistemos apribojimų pusė yra tokia:

Užsirašykime dabartinį atskaitos planą:

Šis atskaitos planas nėra optimalus, nes paskutinėje eilutėje yra neigiamų elementų. Didžiausias neigiamas modulio elementas yra (-3), todėl vektorius įtraukiamas į bazę x adresu . min(40:6, 28:2)=20/3 atitinka 1 eilutę. Vektorius atsiranda iš pagrindo x 3. Atlikime stulpelio Gauso eliminavimą x 2, atsižvelgiant į tai, kad pirmaujantis elementas atitinka 1 eilutę. Iš naujo nustatykime visus šio stulpelio elementus, išskyrus pradinį elementą. Norėdami tai padaryti, pridėkite 2, 3, 4 eilutės eilutes su 1 eilute, padaugintą atitinkamai iš -1/3, 1/6, 1/2. Toliau liniją su pagrindiniu elementu padalijame iš pagrindinio elemento.

Šis atskaitos planas nėra optimalus, nes paskutinėje eilutėje yra neigiamas elementas (-3), todėl į bazę įtrauktas vektorius x 1. Mes nustatome, kuris vektorius išeina iš pagrindo. Norėdami tai padaryti, mes apskaičiuojame adresu . min(44/3:11/3, 62/3:5/3)=4 atitinka 2 eilutę. Vektorius atsiranda iš pagrindo x 4. Atlikime stulpelio Gauso eliminavimą x 1, atsižvelgiant į tai, kad pirmaujantis elementas atitinka 2 eilutę. Iš naujo nustatykime visus šio stulpelio elementus, išskyrus pradinį elementą. Norėdami tai padaryti, pridėkite 1, 3, 4 eilutes su 2 eilute, padauginta atitinkamai iš 1/11, -5/11, 9/11. Toliau liniją su pirmaujančiu elementu padalijame iš pagrindinio elemento.

Paprastoji lentelė bus tokia:

Dabartinis atskaitos planas yra optimalus, nes 4 eilutėse po kintamaisiais neigiamų elementų nėra.

Sprendimą galima parašyti taip: .

Tikslo funkcijos reikšmė šiuo tašku: F(X)=.

2 pavyzdys. Raskite funkcijos maksimumą

Sprendimas.

Baziniai vektoriai x 4 , x 3, todėl visi elementai stulpeliuose x 4 , x 3 žemiau horizontalios linijos turi būti lygus nuliui.

Iš naujo nustatyti visus stulpelio elementus į nulį x 4, išskyrus pagrindinį elementą. Norėdami tai padaryti, pridėkite 3 eilutę su 1 eilute, padauginta iš 4. Iš naujo nustatykite visus stulpelio elementus į nulį x 3, išskyrus pagrindinį elementą. Norėdami tai padaryti, pridėkite 3 eilutę su 2 eilute, padauginta iš 1.

Paprastoji lentelė bus tokia:

Šis atskaitos planas nėra optimalus, nes paskutinėje eilutėje yra neigiamas elementas (-11), todėl į bazę įtrauktas vektorius x 2. Mes nustatome, kuris vektorius išeina iš pagrindo. Norėdami tai padaryti, apskaičiuojame adresu . Todėl tikslo funkcija yra neapribota iš viršaus. Tie. linijinio programavimo problema yra neišsprendžiama.

ZLP sprendimo pavyzdžiai naudojant dirbtinio pagrindo metodą

1 pavyzdys. Raskite funkcijos maksimumą

Sprendimas Kadangi bazinių vektorių skaičius turi būti 3, pridedame dirbtinį kintamąjį, o prie tikslo funkcijos pridedame šį kintamąjį, padaugintą iš −M, kur M yra labai didelis skaičius:

Lygčių sistemos koeficientų matrica yra tokia:

Baziniai vektoriai todėl visi elementai stulpeliuose žemiau horizontalios linijos turi būti lygūs nuliui.

Iš naujo nustatykime visus stulpelio elementus, išskyrus pagrindinį elementą. Norėdami tai padaryti, pridėkite 5 eilutę su 3 eilute, padauginta iš -1.

Paprastoji lentelė bus tokia:

Šis atskaitos planas nėra optimalus, nes paskutinėje eilutėje yra neigiamų elementų. Didžiausias absoliutus neigiamas elementas yra (-5), todėl vektorius įtraukiamas į bazę. Nustatome, kuris vektorius išeina iš pagrindo. Norėdami tai padaryti, apskaičiuojame adresu atitinka 3 eilutę. Iš pagrindo išeina vektorius. Padarykime Gauso išimtį stulpeliui, atsižvelgiant į tai, kad pirmaujantis elementas atitinka 3 eilutę. Iš naujo nustatykime visus šio stulpelio elementus, išskyrus pirmaujantį elementą. Norėdami tai padaryti, pridėkite 5 eilutes su 3 eilute, padauginta iš 1. Tada padalykite eilutę su pirmuoju elementu iš pirmaujančio elemento.

Paprastoji lentelė bus tokia:

Šis atskaitos planas nėra optimalus, nes paskutinėje eilutėje yra neigiamų elementų. Didžiausias absoliutus neigiamas elementas yra (-3), todėl vektorius įtraukiamas į bazę. Nustatome, kuris vektorius išeina iš pagrindo. Norėdami tai padaryti, apskaičiuojame adresu atitinka 1 eilutę. Vektorius atsiranda iš pagrindo x 2. Atlikime stulpelio Gauso eliminavimą x 1 , atsižvelgiant į tai, kad pirmaujantis elementas atitinka 1 eilutę. Iš naujo nustatykime visus šio stulpelio elementus, išskyrus pagrindinį elementą. Norėdami tai padaryti, pridėkite 2, 3, 4 eilutės eilutes su 1 eilute, padaugintą atitinkamai iš 3/2, -1/10, 3/2. Toliau liniją su pagrindiniu elementu padalijame iš pagrindinio elemento.

Paprastoji lentelė bus tokia:

Šis atskaitos planas nėra optimalus, nes paskutinėje eilutėje yra neigiamų elementų. Didžiausias neigiamas modulio elementas (-13/2), todėl į bazę įeina vektorius x 3. Mes nustatome, kuris vektorius išeina iš pagrindo. Norėdami tai padaryti, apskaičiuojame adresu atitinka eilutę 3. Vektorius atsiranda iš pagrindo x 5. Atlikime stulpelio Gauso eliminavimą x 3, atsižvelgiant į tai, kad pirmaujantis elementas atitinka 3 eilutę. Iš naujo nustatykime visus šio stulpelio elementus, išskyrus pradinį elementą. Norėdami tai padaryti, pridėkite 1, 2, 4 eilutės eilutes su 3 eilute, padaugintą atitinkamai iš 5/3, 25/9, 65/9. Toliau liniją su pirmaujančiu elementu padalijame iš pagrindinio elemento.

Paprastoji lentelė bus tokia:

Dabartinis atskaitos planas yra optimalus, nes po kintamaisiais 4–5 eilutėse nėra neigiamų elementų.

Pradinės problemos sprendimas gali būti parašytas taip:

2 pavyzdys. Raskite optimalų linijinio programavimo uždavinio planą:

Lygčių sistemos koeficientų matrica yra tokia:

Baziniai vektoriai x 4 , x 5 , x 6, todėl visi elementai stulpeliuose x 4 , x 5 , x 6, žemiau horizontalios linijos turi būti nulis.

Iš naujo nustatyti visus stulpelio elementus į nulį x 4, išskyrus pagrindinį elementą. Norėdami tai padaryti, pridėkite 4 eilutę su 1 eilute, padauginta iš -1. Iš naujo nustatyti visus stulpelio elementus į nulį x 5, išskyrus pagrindinį elementą. Norėdami tai padaryti, pridėkite 5 eilutę su 2 eilute, padauginta iš -1. Iš naujo nustatyti visus stulpelio elementus į nulį x 6, išskyrus pagrindinį elementą. Norėdami tai padaryti, pridėkite 5 eilutę su 3 eilute, padauginta iš -1.

Paprastoji lentelė bus tokia:

5 eilutėje kintamuosius atitinkantys elementai x 1 , x 2 , x 3 , x 4 , x 5 , x 6 yra ne neigiami, o skaičius yra nurodytos eilutės ir stulpelio sankirtoje x 0 yra neigiamas. Tada pradinė problema neturi atskaitos plano. Todėl neapsisprendžiama.

Nagrinėjamas uždavinio sprendimo simplekso metodu pavyzdys, taip pat dvigubos problemos sprendimo pavyzdys.

Turinys

Probleminė būklė

Trims prekių grupėms parduoti komercinė įmonė turi trijų rūšių ribotus materialinius ir piniginius išteklius, kurių suma yra b 1 = 240, b 2 = 200, b 3 = 160 vnt. Tuo pačiu metu už 1 prekių grupės pardavimą už 1 tūkst. prekių apyvarta, pirmosios rūšies ištekliai sunaudojami a 11 = 2 vnt., antrojo tipo ištekliai a 21 = 4 vnt., trečio tipo ištekliai sunaudojami 31 = 4 vienetai. 2 ir 3 prekių grupių pardavimas už 1 tūkst. apyvarta sunaudojama pagal pirmojo tipo išteklius a 12 = 3, a 13 = 6 vnt., antrojo tipo išteklius - a 22 = 2, a 23 = 4 vnt., išteklius trečiasis tipas a 32 = 6, a 33 = 8 vienetai . Pelnas iš trijų prekių grupių pardavimo už 1 tūkst. apyvarta yra atitinkamai c 1 = 4, c 2 = 5, c 3 = 4 (tūkstantis rublių). Nustatyti planuojamą prekybos apyvartos apimtį ir struktūrą taip, kad prekybos įmonės pelnas būtų maksimalus.

Į tiesioginę apyvartos planavimo problemą, išspręsta simplekso metodu, sudaryti dviguba problema linijinis programavimas.
Įdiegti konjuguotos kintamųjų poros tiesioginės ir dvejopos problemos.
Pagal konjuguotas kintamųjų poras iš tiesioginės problemos sprendimo gauname dvigubos problemos sprendimas, kurioje jis gaminamas išteklių vertinimas, išleista prekėms parduoti.

Problemos sprendimas naudojant simplekso metodą

Tegul x 1, x 2, x 3 yra parduotų prekių skaičius tūkstančiais rublių, atitinkamai 1, 2, 3 grupėse. Tada problemos matematinis modelis turi tokią formą:

F = 4 x 1 + 5 x 2 + 4 x 3 ->maks

0)))(~)" title="delim(lbrace)(matrica(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Mes išsprendžiame simplekso metodą.

Įvedame papildomus kintamuosius x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, kad nelygybes paverstume lygybėmis.

Paimkime x 4 = 240 kaip pagrindą; x 5 = 200; x 6 = 160.

Įvedame duomenis į simplex stalas

Simplex lentelė Nr.1

Objektyvi funkcija:

0 240 + 0 200 + 0 160 = 0

Skaičiuojame pagal formulę:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Kadangi yra neigiamų įvertinimų, planas nėra optimalus. Žemiausias balas:

Įvedame kintamąjį x 2 į pagrindą.

Mes apibrėžiame kintamąjį, atsirandantį iš pagrindo. Norėdami tai padaryti, randame mažiausią neneigiamą x2 stulpelio santykį.

= 26.667

Mažiausias neneigiamas: Q 3 = 26,667. Kintamąjį x 6 išvedame iš pagrindo

Padalinkite 3 eilutę iš 6.
Iš 1 eilutės atimkite 3 eilutę, padaugintą iš 3
Iš 2 eilutės atimkite 3 eilutę, padaugintą iš 2

Skaičiuojame:

Gauname naują lentelę:

Simplex lentelė Nr.2

Objektyvi funkcija:

0 160 + 0 440/3 + 5 80/3 = 400/3

Skaičiuojame pagal formulę:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Kadangi yra neigiamas įvertinimas Δ 1 = - 2/3, planas nėra optimalus.

Į bazę įvedame kintamąjį x 1.

Mes apibrėžiame kintamąjį, atsirandantį iš pagrindo. Norėdami tai padaryti, randame mažiausią neneigiamą stulpelio x 1 santykį.

Mažiausias neneigiamas: Q 3 = 40. Kintamąjį x 2 išvedame iš pagrindo

Padalinkite 3 eilutę iš 2/3.
Iš 2 eilutės atimkite 3 eilutę, padaugintą iš 8/3

Skaičiuojame:

Gauname naują lentelę:

Simplex lentelė Nr.3

Objektyvi funkcija:

0 160 + 0 40 + 4 40 = 160

Skaičiuojame pagal formulę:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 = 1

Kadangi nėra neigiamų įvertinimų, planas yra optimalus.

Problemos sprendimas:

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

Tai yra, būtina parduoti pirmos rūšies prekes už 40 tūkstančių rublių. Nereikia parduoti 2 ir 3 rūšių prekių. Šiuo atveju didžiausias pelnas bus F max = 160 tūkstančių rublių.

Dvigubos problemos sprendimas

Dviguba problema turi tokią formą:

Z = 240 y 1 + 200 y 2 + 160 y 3 -> min

Title="delim(lbrace)(matrica(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Įvedame papildomus kintamuosius y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, kad nelygybes paverstume lygybėmis.

Tiesioginės ir dvigubos problemos konjuguotos kintamųjų poros turi tokią formą:

Iš paskutinės tiesioginės problemos simpleksinės lentelės Nr. 3 randame dvigubos problemos sprendimą:

Z min = F max = 160;
y1 = Δ4 = 0; y2 = Δ5 = 0; y3 = Δ6 = 1; y4 = Δ1 = 0; y5 = Δ2 = 1; y6 = Δ3 = 4;

Y1 = 0; y2 = 0; y 3 = 1; Z min = 160;

Simpleksinis metodas yra vienas iš efektyviausių LP uždavinių skaitinio sprendimo būdų. Sąvokos „simplex“ esmė yra tokia. Kūno k-dimensinėje erdvėje simpleksas yra aibė, susidedanti iš k + 1 šio kūno viršūnių. Taigi, jei k = 2, t.y. plokštumoje simpleksas bus trikampio viršūnės; kai k = 3, simpleksas yra tetraedro viršūnės, pavyzdžiui, tetraedras ir kt. Šis metodas buvo suteiktas dėl to, kad jis pagrįstas nuoseklia ODZP viršūnių paieška, siekiant nustatyti viršūnės, kurioje tikslo funkcija turi kraštutinę reikšmę, koordinates.

Jis suskirstytas į du pagrindinius etapus. Pirmajame etape randamas vienas iš sprendimų, atitinkančių apribojimų sistemą. Sistemos, kuriose kintamųjų yra daugiau nei apribojimų N > m, vadinamos neapibrėžtomis. Jie redukuojami į tam tikras sistemas (N = m), N-m bet kokius kintamuosius prilyginant nuliui. Tai palieka m lygčių sistemą su m nežinomųjų, kuri turi sprendimą, jei sistemos determinantas yra nulis. Simpleksinis metodas įveda pagrindinių kintamųjų arba pagrindo sąvoką. Pagrindas yra bet koks m kintamųjų rinkinys, kurio determinantas, sudarytas iš šių kintamųjų koeficientų m apribojimuose, yra nulis. Likę N-m kintamieji vadinami nepagrindiniais arba laisvaisiais kintamaisiais. Jei darysime prielaidą, kad visi nepagrindiniai kintamieji lygūs nuliui ir išspręstume pagrindinių kintamųjų apribojimų sistemą, gautume pagrindinį sprendimą.

M lygčių sistemoje su N nežinomųjų bendras pagrindinių sprendinių skaičius N > m nustatomas pagal derinių skaičių

Vadinamas pagrindinis sprendinys, kuriame visi x i 0, i = 1,m leistinas pagrindinis sprendimas. Taigi pirmasis sprendimo etapas, naudojant simplekso metodą, baigiasi randant priimtiną pagrindinį sprendimą, net jei jis ir nesėkmingas.

Antrajame etape rastas sprendimas nuosekliai tobulinamas.Šiuo atveju pereinama nuo vieno įmanomo pagrindinio sprendimo prie kito taip, kad pagerėtų tikslo funkcijos reikšmė. Sprendimo procesas, naudojant simplekso metodą, tęsiamas tol, kol pasiekiama mažiausia (arba didžiausia) tikslo funkcijos reikšmė. Geometriškai tai reiškia judėjimą išilgai kraštų nuo vienos leistinų reikšmių daugiakampio viršūnės į kitą link tos, kurioje tikslo funkcijos reikšmė pasiekia kraštutinumą. Simpleksinis metodas suteikia optimalią pagrindinių sprendinių surašymo procedūrą ir užtikrina konvergenciją iki kraštutinio taško atliekant baigtinį žingsnių skaičių. Naudojant simplekso metodą, skaičiavimai antrame etape atliekami pagal šią schemą:

1) pagrindiniai kintamieji ir tikslo funkcija išreiškiami nepagrindiniais kintamaisiais;

2) pagal tam tikrą taisyklę pasirenkamas vienas iš nepagrindinių kintamųjų, kurio reikšmę pakeitus galima pagerinti F(x) reikšmę, ir jis įvedamas į bazę;

3) nustatoma, kuris iš pagrindinių kintamųjų turi būti išvestas iš pagrindo, o kiekviename žingsnyje suformuotas naujas pagrindinių kintamųjų rinkinys skiriasi nuo ankstesnio tik vienu kintamuoju;

4) pagrindiniai kintamieji ir tikslo funkcija išreiškiami naujais nepagrindiniais kintamaisiais, o operacijos 2) ir 3) kartojamos.

Jei tam tikru simplekso metodo žingsniu paaiškėja, kad pakeitus bet kurio nepagrindinio kintamojo reikšmes nepavyksta pagerinti F(x), tada paskutinis pagrindinis sprendimas pasirodo optimalus.

Panagrinėkime pavyzdį, susijusį su organizacinio ir ekonominio valdymo uždaviniais ir padedantį suprasti simpleksinio metodo turinį.

1 pavyzdys. Naujos aikštelės įrangai įsigyti buvo skirta 20 tūkst. Įranga turi būti pastatyta ne didesniame kaip 72 m2 plote. Galima užsakyti dviejų tipų įrangą: 1) 5 tūkst. kainuojančią įrangą, užimančią 6 m 2 plotą ir pagaminančią 8 tūkst. vnt. produktai per pamainą; 2) 2 tūkst. vertės įranga, užimanti 12 m2 plotą ir pagaminanti 4 tūkst. vnt. per pamainą. produktų. Raskite optimalų variantą įsigyti įrangą, kuri užtikrina maksimalų bendrą svetainės produktyvumą naudojant simplekso metodą.

Nežinomą pirmojo ir antrojo tipo įrangos kiekį pažymėkime x 1 ir x 2. Tikslo funkciją galima užrašyti taip: F(x) = 8x 1 + 4x 2 (max). Teritorijos apribojimai: 6x 1 +12x 2 ≤72; išlaidų apribojimai: 5x 1 + 2x 2 ≤20 ; kintamųjų x 1 ≥0 ženklo apribojimai; x 2 ≥0.

Pirmojo apribojimo koeficientus padalinkime iš 6 ir sumažinkime apribojimus iki lygybių formos, įvesdami papildomus kintamuosius x 3 ir x 4:

x 1 + 2x 2 + x 3 =12, (1)

5x 1 + 2x 2 + x 4 = 20. (2)

Taigi uždavinio apribojimai , redukuojami į dviejų algebrinių lygčių sistemą su keturiais nežinomaisiais. Problemos sprendimo procedūra yra tokia:

1 žingsnis.

Norėdami išspręsti simplekso metodą, kaip pagrindinius kintamuosius (BP) pasirenkame x 2 ir x 4, nes determinantas, sudarytas iš šių kintamųjų koeficientų uždavinio apribojimuose, skiriasi nuo nulio.

(3)

Tada x 1 ir x 3 bus nepagrindiniai kintamieji (NP). Išreikškime pagrindinius kintamuosius ir F(x) nebaziniais kintamaisiais.

Iš antrojo apribojimo išplaukia, kad

x 4 = 20 - 2x 2 - 5x 1. (4)

Atsižvelgdami į aukščiau pateiktą išraišką, gauname

x 4 = 8 - 4x 1 + x 3. (5)

Tada

F(x) = 8x 1 + 4x 2 = 24 + 6x 1 - 2x 3. (6)

Kiekviename žingsnyje NP yra lygūs nuliui, todėl BP ir F(x) bus lygūs laisviesiems terminams atitinkamose išraiškose:

x 1 = 0, x 3 = 0, x 2 = 6, x 4 = 8, F(x) = 24.

Šis sprendimas atitinka ODZP viršūnės A koordinates Fig. 1. Sprendimo optimalumas tikrinamas naudojant tikslo funkcijos išraišką F(x). Kintamasis x 3 įveda šią išraišką su neigiamu koeficientu; jei kitame žingsnyje į bazę įvesite x 3, tada ji įgis teigiamą reikšmę, o iš skaičiaus 24 bus atimta tam tikra reikšmė, t.y. F(x) reikšmė sumažės. Jeigu kitame žingsnyje į bazę įvesite x 1, tai tikslo funkcijos reikšmė padidės, t.y. pagerės.

Taikant simplekso metodą, kintamasis, kuris pirmą kartą patenka į nulį, kai įvedamas į bazę x 1, iš pagrindo neįtraukiamas. Analizuodami (3) ir (5) nustatome, kad x 4 turėtų būti neįtrauktas į pagrindą. Kitame žingsnyje kintamieji x 1 ir x 4 bus sukeisti.

2-asis simplekso metodo žingsnis. x 1 ir x 2 yra pagrindiniai kintamieji, x 3 ir x 4 yra ne pagrindiniai kintamieji. Išreikškime pagrindinius kintamuosius ir F(x) nebaziniais kintamaisiais. Iš (5) išplaukia

x 1 = 2 + (1/4) x 3 -(1/4) x 4 (7)

Ryžiai. 1. Grafinis 1 pavyzdžio aiškinimas naudojant simplekso metodą.

Pakeitę (7) į (3), gauname

x 2 =5-(5/8)x3 +(1/8)x4

Taigi, naudojant simplekso metodą, nustatėme, kad maksimalus svetainės produktyvumas yra 36 tūkst. prekės per pamainą bus teikiamos perkant 2 vnt. pirmojo tipo įranga ir 5 vnt. antrojo tipo įranga. Papildomi kintamieji x 3 ir x 4 turi nepanaudotų išteklių reikšmę. Šiame pavyzdyje visi ištekliai pagal plotą ir kainą yra visiškai išnaudoti (x 3 = x 4 = 0).