Primer 5.1. Rešite naslednji problem linearnega programiranja z uporabo simpleksne metode:

rešitev:

jaz ponovitev:

x3, x4, x5, x6 x1,x2... Izrazimo osnovne spremenljivke v terminih prostih:

Ciljno funkcijo privedemo do naslednje oblike:

Na podlagi pridobljene težave bomo oblikovali začetno tabelo simpleksa:

Tabela 5.3

Originalna simplex miza

Po definiciji osnovne rešitve so proste spremenljivke enake nič, vrednosti osnovnih spremenljivk pa enake ustreznim vrednostim prostih števil, tj:

3. faza: preverjanje združljivosti omejevalnega sistema LPP.

Pri tej ponovitvi (v tabeli 5.3) znak nezdružljivosti sistema omejitev (znak 1) ni bil identificiran (tj. ni vrstice z negativnim prostim številom (razen vrstice ciljna funkcija), v katerem ne bi bilo vsaj enega negativnega elementa (tj. negativnega koeficienta pri prosti spremenljivki)).

Pri tej ponovitvi (v tabeli 5.3) predznak neomejenosti ciljne funkcije (znak 2) ni bil identificiran (tj. v vrstici ciljne funkcije ni stolpca z negativnim elementom (razen stolpca prostih številke), v katerih ne bi bilo vsaj enega pozitivnega elementa) ...

Ker najdena osnovna rešitev ne vsebuje negativnih komponent, je dopustna.

6. faza: preverjanje optimalnosti.

Najdena osnovna rešitev ni optimalna, saj glede na kriterij optimalnosti (značilnost 4) v vrstici ciljne funkcije ne bi smelo biti negativnih elementov (prosto število te vrstice se pri upoštevanju te lastnosti ne upošteva). Zato po algoritmu simpleksne metode preidemo na 8. stopnjo.

Ker je najdena osnovna rešitev dopustna, bo iskanje ločljivega stolpca potekalo po naslednji shemi: v vrstici ciljne funkcije (razen stolpca prostih števil) določimo stolpce z negativnimi elementi. V skladu s tabelo 5.3 obstajata dva taka stolpca: stolpec " x1"In kolona" x2". Iz takšnih stolpcev se izbere tisti, ki vsebuje najmanjši element v vrstici ciljne funkcije. Ona bo reševala. zvočnik " x2"Vsebuje najmanjši element (–3) v primerjavi s stolpcem" x1

Za določitev ločljive črte najdemo pozitivna ocenjena razmerja prostih števil do elementov dovoljenega stolpca, za dovoljeno se vzame črta, ki ustreza najmanjšemu pozitivnemu ocenjenemu razmerju.

Tabela 5.4

Originalna simplex miza

V tabeli 5.4 najmanjše pozitivno ocenjeno razmerje ustreza vrstici " x5« Zato bo dovoljeno.

Element, ki se nahaja na stičišču dovolilnega stebra in dovolilnice, je sprejet kot dovoljen. V našem primeru je to element, ki se nahaja na presečišču črte " x5"In stolpci" x2».

Element za razrešitev prikazuje eno osnovno in eno prosto spremenljivko, ki ju je treba zamenjati v simpleksni tabeli, da se premaknete na novo "izboljšano" osnovno rešitev. V ta primer to so spremenljivke x5 in x2, v novi simpleks tabeli (tabela 5.5) jih zamenjamo.

9.1. Preoblikovanje elementa ločljivosti.

Permisivni element tabele 5.4 se preoblikuje na naslednji način:

Dobljeni rezultat vnesemo v podobno celico v preglednico 5.5.

9.2. Pretvorba niza ločljivosti.

Elemente ločljive vrstice tabele 5.4 delimo z ločljivim elementom te simpleksne tabele, rezultati pa se prilegajo podobnim celicam nove tabele simpleksa (tabela 5.5). Transformacije elementov ločljivosti so podane v tabeli 5.5.

9.3. Pretvorba stolpca ločljivosti.

Elemente ločljivega stolpca tabele 5.4 delimo z ločljivim elementom dane simpleksne tabele, rezultat pa se vzame z nasprotnim predznakom. Dobljeni rezultati se prilegajo podobnim celicam nove tabele simpleksa (tabela 5.5). Transformacije elementov ločljivega stolpca so prikazane v tabeli 5.5.

9.4. Pretvorite preostale elemente simpleksne tabele.

Transformacija preostalih elementov simpleksne tabele (tj. elementov, ki se ne nahajajo v ločevalni vrstici in ločljivem stolpcu) se izvede po pravilu "pravokotnik".

Na primer, razmislite o preoblikovanju elementa, ki se nahaja na presečišču niza " x3"In stolpec" ", ga bomo konvencionalno označili kot" x3". V tabeli 5.4 miselno narišite pravokotnik, katerega eno oglišče se nahaja v celici, katere vrednost transformiramo (tj. v celici " x3»), drugi (diagonalno vrh) pa je v celici z ločevalnim elementom. Drugi dve točki (druga diagonala) sta enolično določeni. Nato transformirana vrednost celice " x3"Bo enaka prejšnji vrednosti te celice minus ulomek, v imenovalcu katerega je ločljivi element (iz tabele 5.4), v števcu pa produkt dveh drugih neuporabljenih vozlišč, tj:

« x3»: .

Podobno se preoblikujejo vrednosti drugih celic:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Kot rezultat teh transformacij je nastala nova simpleksna tabela (tabela 5.5).

II ponovitev:

1. faza: sestavljanje simpleksne tabele.

Tabela 5.5

Simpleksna mizaII ponovitev

2. faza: določitev osnovne rešitve.

Kot rezultat simpleksnih transformacij je bila pridobljena nova osnovna rešitev (tabela 5.5):

Kot lahko vidite, je pri tej osnovni rešitvi vrednost ciljne funkcije = 15, kar je več kot pri prejšnji osnovni rešitvi.

Neskladnost sistema omejitev v skladu z atributom 1 v tabeli 5.5 ni bila ugotovljena.

4. faza: preverjanje omejenosti ciljne funkcije.

Neomejenost ciljne funkcije v skladu z značilnostjo 2 v tabeli 5.5 ni bila razkrita.

5. faza: preverjanje dopustnosti najdene osnovne rešitve.

Najdena osnovna rešitev v skladu s funkcijo 4 ni optimalna, saj vrstica ciljne funkcije simpleksne tabele (tabela 5.5) vsebuje negativni element: –2 (prosto število te vrstice se pri upoštevanju tega ne upošteva funkcija). Zato gremo na stopnjo 8.

Faza 8: določitev ločljivega elementa.

8.1. Opredelitev stolpca ločljivosti.

Najdena osnovna rešitev je dopustna, stolpce z negativnimi elementi definiramo v vrstici ciljne funkcije (razen stolpca prostih števil). V skladu s tabelo 5.5 je samo en stolpec tak stolpec: " x1". Zato ga sprejemamo kot dovoljeno.

8.2. Določitev niza dovoljenj.

Glede na dobljene vrednosti pozitivnih ocenjevalnih razmerij v tabeli 5.6 je minimalno razmerje, ki ustreza vrstici " x3". Zato ga sprejemamo kot dovoljeno.

Tabela 5.6

Simpleksna mizaII ponovitev

Faza 9: transformacija tabele simpleksa.

Simpleksne transformacije tabel (tabele 5.6) se izvedejo na enak način kot v prejšnji iteraciji. Rezultati transformacij elementov simpleksne tabele so prikazani v tabeli 5.7.

III ponovitev

Na podlagi rezultatov simpleksnih transformacij prejšnje iteracije sestavimo novo tabelo simpleksa:

Tabela 5.7

Simpleksna mizaIII ponovitev

2. faza: določitev osnovne rešitve.

Kot rezultat simpleksnih transformacij je bila pridobljena nova osnovna rešitev (tabela 5.7):

3. faza: preverjanje doslednosti sistema omejitev.

Neskladnost sistema omejitev v skladu z atributom 1 v tabeli 5.7 ni bila razkrita.

4. faza: preverjanje omejenosti ciljne funkcije.

Neomejenost ciljne funkcije v skladu z atributom 2 v tabeli 5.7 ni bila razkrita.

5. faza: preverjanje dopustnosti najdene osnovne rešitve.

Najdena osnovna rešitev po atributu 3 je dopustna, saj ne vsebuje negativnih komponent.

6. faza: preverjanje optimalnosti najdene osnovne rešitve.

Najdena osnovna rešitev v skladu s funkcijo 4 ni optimalna, saj vrstica ciljne funkcije simpleksne tabele (tabela 5.7) vsebuje negativni element: –3 (prosto število te vrstice se pri upoštevanju tega ne upošteva funkcija). Zato gremo na stopnjo 8.

Faza 8: določitev ločljivega elementa.

8.1. Opredelitev stolpca ločljivosti.

Najdena osnovna rešitev je dopustna, stolpce z negativnimi elementi definiramo v vrstici ciljne funkcije (razen stolpca prostih števil). V skladu s tabelo 5.7 je samo en stolpec tak stolpec: " x5". Zato ga sprejemamo kot dovoljeno.

8.2. Določitev niza dovoljenj.

Glede na dobljene vrednosti pozitivnih ocenjevalnih razmerij v tabeli 5.8 je minimalno razmerje, ki ustreza vrstici " x4". Zato ga sprejemamo kot dovoljeno.

Tabela 5.8

Simpleksna mizaIII ponovitev

Faza 9: transformacija tabele simpleksa.

Simpleksne transformacije tabel (tabela 5.8) se izvedejo na enak način kot v prejšnji iteraciji. Rezultati transformacij elementov simpleksne tabele so prikazani v tabeli 5.9.

IV ponovitev

1. faza: izdelava nove simpleksne mize.

Na podlagi rezultatov simpleksnih transformacij prejšnje iteracije sestavimo novo tabelo simpleksa:

Tabela 5.9

Simpleksna mizaIV ponovitev

2. faza: določitev osnovne rešitve.

Kot rezultat simpleksnih transformacij je bila pridobljena nova osnovna rešitev, v skladu s tabelo 5.9 je rešitev naslednja:

3. faza: preverjanje doslednosti sistema omejitev.

Neskladnost sistema omejitev v skladu z atributom 1 v tabeli 5.9 ni bila razkrita.

4. faza: preverjanje omejenosti ciljne funkcije.

Neomejenost ciljne funkcije v skladu z značilnostjo 2 v tabeli 5.9 ni bila razkrita.

5. faza: preverjanje dopustnosti najdene osnovne rešitve.

Najdena osnovna rešitev po atributu 3 je dopustna, saj ne vsebuje negativnih komponent.

6. faza: preverjanje optimalnosti najdene osnovne rešitve.

Najdena osnovna rešitev v skladu s funkcijo 4 je optimalna, saj v vrstici ciljne funkcije simpleksne tabele (tabela 5.9) ni negativnih elementov (pri upoštevanju te lastnosti se prosto število te vrstice ne upošteva) .

7. faza: preverjanje alternative rešitve.

Najdena rešitev je edina, saj v vrstici ciljne funkcije ni elementov nič (tabela 5.9) (prosto število te vrstice se pri upoštevanju te lastnosti ne upošteva).

odgovor: optimalna vrednost ciljna funkcija obravnavanega problema = 24, kar je doseženo pri.

Primer 5.2. Rešite zgornji problem linearnega programiranja pod pogojem, da je ciljna funkcija minimizirana:

rešitev:

jaz ponovitev:

1. faza: oblikovanje začetne tabele simpleksa.

Prvotni problem linearnega programiranja je podan v standardni obliki. Privedemo jo do njene kanonske oblike tako, da v vsako od omejitev neenakosti vnesemo dodatno nenegativno spremenljivko, t.j.

V dobljenem sistemu enačb vzamemo za dovoljene (osnovne) spremenljivke x3, x4, x5, x6, potem bodo proste spremenljivke x1,x2... Izrazimo osnovne spremenljivke v terminih prostih.

Kratka teorija

Za reševanje problemov linearnega programiranja je bilo predlaganih veliko različnih metod. Vendar se je metoda simpleksa izkazala za najbolj učinkovito in univerzalno med njimi. Treba je opozoriti, da so pri reševanju nekaterih težav druge metode lahko učinkovitejše. Na primer, v primeru LPP z dvema spremenljivkama je optimalna metoda, v primeru rešitve pa metoda potencialov. Simpleksna metoda je osnovna in uporabna za kateri koli ZPL v kanonski obliki.

V povezavi z glavnim izrekom linearnega programiranja se seveda pojavi ideja o naslednjem načinu reševanja LPP s poljubnim številom spremenljivk. Poiščite na nek način vse skrajne točke načrtovalnega poliedra (ni več kot) in primerjajte vrednosti ciljne funkcije v njih. Ta način reševanja je tudi z relativno majhnim številom spremenljivk in omejitev praktično neuresničljiv, saj je proces iskanja skrajnih točk po težavnosti primerljiv z rešitvijo prvotnega problema, poleg tega pa lahko število skrajnih točk planskega poliedra se izkaže za zelo veliko. V zvezi s temi težavami se je pojavil problem racionalnega naštevanja skrajnih točk.

Bistvo simpleksne metode je naslednje. Če sta neka skrajna točka in vrednost ciljne funkcije v njej znani, potem so vse skrajne točke, na katerih ciljna funkcija zavzame najslabšo vrednost, očitno nepotrebne. Zato je naravno, da si prizadevamo najti pot od dane skrajne točke do boljše sosednje ob robu, od nje do še boljše (ne slabše) točke itd. Če želite to narediti, morate imeti znak, da boljših skrajnih točk od te skrajne točke sploh ni. To je splošna ideja trenutno najbolj razširjena simpleks metoda (metoda zaporednega izboljševanja načrta) za reševanje LPP. Torej, v algebrskem smislu, simpleks metoda predpostavlja:

1. sposobnost iskanja začetnega referenčnega načrta;
2. prisotnost znaka optimalnosti referenčnega načrta;
3. možnost prehoda na osnovni načrt, ki ni slab.

Primer reševanja problema

Naloga

Za prodajo treh skupin blaga ima gospodarsko podjetje tri vrste omejenih materialnih in denarnih sredstev v višini,,, enot. Hkrati za prodajo 1 skupine blaga za 1 tisoč rubljev. promet se porabi za vir prve vrste v številu enot, vir druge vrste v številu enot, vir tretje vrste v številu enot. Za prodajo 2 in 3 skupin blaga za 1 tisoč rubljev. promet se porabi, oziroma vir prve vrste v količini, enote, viri druge vrste v količini, enote, viri tretje vrste v količini, enote. Dobiček od prodaje treh skupin blaga za 1 tisoč rubljev. promet je torej tisoč rubljev.

• Določite načrtovani obseg in strukturo prometa, tako da je dobiček trgovskega podjetja največji.
• K neposrednemu problemu načrtovanja prometa, ki ga rešujemo s simpleksno metodo, oblikujte dvojni problem linearnega programiranja.
• Vzpostavite konjugirane pare spremenljivk neposrednega in dvojnega problema.
• Glede na konjugirane pare spremenljivk iz rešitve direktnega problema dobimo rešitev dvojnega problema, v kateri se ocenijo sredstva, porabljena za prodajo blaga.

Če je vaš sprejem na sejo odvisen od rešitve bloka težav in nimate ne časa ne želje, da bi se usedli za izračune - uporabite zmožnosti spletnega mesta. Naročanje opravil je nekaj minut. Več podrobnosti (kako pustiti povpraševanje, cene, pogoji, načini plačila) si lahko preberete na strani za reševanje problemov z linearnim programiranjem Kupite ...

Rešitev problema

Gradnja modela

Skozi označimo promet 1., 2. in tretje vrste blaga.

Potem je ciljna funkcija, ki izraža dobiček:

Omejitve materialnih in denarnih sredstev:

Poleg tega v smislu problema

Dobimo naslednji problem linearnega programiranja:

Približevanje kanonične oblike ZLP

Pripeljemo problem v kanonično obliko. Za preoblikovanje neenakosti v enakosti uvedemo dodatne spremenljivke. Spremenljivke so vključene v omejitve s koeficientom 1. Vse dodatne spremenljivke vnesemo v ciljno funkcijo s koeficientom enakim nič.

Omejitev ima prednostno obliko, če, če je desna stran nenegativna, leva stran ima spremenljivko, ki vstopa s koeficientom, enakim ena, in ostale omejitve enakosti - s koeficientom enakim nič. V našem primeru imajo 1., 2., 3. omejitve prednostno obliko z ustreznimi osnovnimi spremenljivkami.

Enostavna rešitev

Izpolnimo simpleksno tabelo 0. iteracije.

Ker rešimo največji problem, prisotnost negativnih števil v indeksni vrstici pri reševanju največjega problema kaže, da nismo dobili optimalne rešitve in da je treba preiti iz tabele 0. iteracije na naslednjo.

Prehod na naslednjo ponovitev se izvede na naslednji način:

Vodilni stolpec se ujema.

Ključna vrstica je določena z minimalnim razmerjem prostih članov in članov vodilnega stolpca (simplex relacije):

Na presečišču ključnega stolpca in ključne vrstice najdemo ločevalni element, to je 7.

Zdaj pa začnimo s prevajanjem 1. ponovitve. Namesto enotnega vektorja uvedemo vektor.

V novi tabeli namesto ločljivega elementa zapišemo 1, vsi ostali elementi ključnega stolpca so ničelni. Ključni linijski elementi so razdeljeni na dovolilniški element. Vsi ostali elementi tabele so izračunani po pravilu pravokotnika.

Dobimo tabelo 1. ponovitve:

Ključni stolpec za ujemanja 1. ponovitve.

Najdemo ključni niz, za to definiramo:

Na presečišču ključnega stolpca in ključne črte najdemo ločevalni element, t.j. 31/7.

Vektor se izpelje iz osnove in vektor se uvede.

Dobimo tabelo 2. ponovitve:

Vsi izrazi v indeksni vrstici so nenegativni, zato dobimo naslednjo rešitev problema linearnega programiranja (zapišemo jo iz stolpca prostih izrazov):

Tako je treba prodati 7,1 tisoč rubljev. blago 1. vrste in 45,2 tisoč rubljev. blago 3. vrste. Nedonosno je prodajati blago 2. vrste. V tem primeru bo dobiček največji in znaša 237,4 tisoč rubljev. Z izvajanjem optimalnega načrta bo preostanek vira 3. tipa 701 enota.

Problem dvojnega LP

Zapišimo model dvojnega problema.

Če želite zgraditi dvojni problem, morate uporabiti naslednja pravila:

1) če je neposredni problem rešen na maksimum, potem je dvojni rešen na minimum in obratno;

2) v problemu maksimuma imajo omejitve neenakosti pomen ≤, v problemu minimizacije pa pomen ≥;

3) vsaka omejitev direktnega problema ustreza spremenljivki dvojnega problema in obratno, vsaka omejitev dvojnega problema ustreza spremenljivki neposrednega problema;

4) matriko sistema omejitev dvojnega problema dobimo iz matrike sistema omejitev izvirnega problema s transpozicijo;

5) prosti členi sistema omejitev direktnega problema so koeficienti za ustrezne spremenljivke ciljne funkcije dvojnega problema in obratno;

6) če je pogoj nenegativnosti naložen spremenljivki direktnega problema, potem se ustrezna omejitev dvojnega problema zapiše kot omejitev neenakosti, če ne, pa kot omejitev enakosti;

7) če je katera koli omejitev direktnega problema zapisana kot enakost, potem pogoj nenegativnosti ni naložen ustrezni spremenljivki dvojnega problema.

Transponiramo matriko prvotne težave:

Pripeljemo problem v kanonično obliko. Uvedemo dodatne spremenljivke. V ciljno funkcijo vnesemo vse dodatne spremenljivke s koeficientom enakim nič. Na levi strani omejitev dodamo dodatne spremenljivke, ki nimajo želene oblike, in dobimo enakosti.

Rešitev problema dvojnega LP

Korespondenca med spremenljivkami izvirnega in dvojnega problema:

Na podlagi tabele simpleksa smo dobili naslednjo rešitev problema dvojnega linearnega programiranja (zapišemo jo iz spodnje vrstice):

Tako je najbolj redek vir prva vrsta. Njegova ocena je največja in enaka. Vir tretje vrste je pretiran - njegova dvojna ocena je nič. Vsaka dodatno prodana enota blaga 2. skupine bo zmanjšala optimalni dobiček za
Obravnavana je grafična metoda za reševanje problema linearnega programiranja (LPP) z dvema spremenljivkama. Primer naloge kaže natančen opis izdelava risbe in iskanje rešitve.

Rešitev transportnega problema
Podrobno je obravnavan transportni problem, njegov matematični model in metode reševanja – iskanje referenčnega načrta z metodo minimalnih elementov in iskanje optimalne rešitve z metodo potenciala.

Odločanje v negotovosti
Obravnavana je rešitev statistične matrične igre v pogojih negotovosti po kriterijih Walda, Savagea, Hurwitza, Laplacea, Bayesa. Na primeru naloge je podrobno prikazana gradnja plačilne matrike in matrike tveganja.

Potrebno je rešiti problem linearnega programiranja.

Ciljna funkcija:

2x 1 + 5x 2 + 3x 3 + 8x 4 → min

Omejitveni pogoji:

3x 1 + 6x 2 -4x 3 + x 4 ≤12
4x 1 -13x 2 + 10x 3 + 5x 4 ≥6
3x 1 + 7x 2 + x 3 ≥1

Sistem omejitev spravimo v kanonično obliko, za to je treba preiti z neenakosti na enakosti, z dodatkom dodatnih spremenljivk.

Ker je naša naloga naloga minimizacije, jo moramo preoblikovati v maksimalno iskalno nalogo. V ta namen spremenimo predznake koeficientov ciljne funkcije v nasprotne. Elemente prve neenakosti zapišemo nespremenjene tako, da ji dodamo dodatno spremenljivko x 5 in spremenimo predznak »≤« v »=". Ker imata druga in tretja neenakost predznaka "≥", je treba predznake njunih koeficientov spremeniti v nasprotne in dodati dodatne spremenljivke x 6 oziroma x 7. Kot rezultat dobimo enakovreden problem:

3x 1 + 6x 2 -4x 3 + x 4 + x 5 = 12
-4x 1 + 13x 2 -10x 3 -5x 4 + x 6 = -6
-3x 1 -7x 2 -x 3 + x 7 = -1

Preidemo na oblikovanje originalne tabele simpleksa. Vrstica F tabele vsebuje koeficiente ciljne funkcije s nasprotno znamenje.

Ker v stolpcu prostih členov ni negativnih elementov, je bila najdena dopustna rešitev, v vrstici F pa negativni elementi, kar pomeni, da dobljena rešitev ni optimalna. Določimo vodilni stolpec. Če želite to narediti, poiščite v vrstici F največji negativni element v absolutni vrednosti - to je -1, 988. Vodilna vrstica bo tista, pri kateri je razmerje prostega člana do ustreznega elementa vodilnega stolpca minimalno. Vodilna črta je X2, vodilna postavka pa 0,313.

Ker v vrstici F ni negativnih elementov, se najde optimalna rešitev... Ker je bil prvotni problem najti minimum, bo optimalna rešitev prosti člen niza F, vzet z nasprotnim predznakom. F = 1,924
z enakimi vrednostmi spremenljivk: x 3 = 0,539, x 1 = 0,153. Spremenljivki x 2 in x 4 nista vključeni v osnovo, zato je x 2 = 0 x 4 = 0.

Tukaj je ročna (ne programska) rešitev dveh problemov po simpleks metodi (podobna rešitvi s programčkom) s podrobnimi razlagami, da bi razumeli algoritem za reševanje problemov s simpleksno metodo. Prvi problem vsebuje znake neenakosti samo "≤" (problem z začetno osnovo), drugi lahko vsebuje znake "≥", "≤" ali "=" (problem z umetno osnovo), rešujejo se na različne načine .

Simpleksna metoda, reševanje problema z začetno osnovo

1)Simpleksna metoda za problem z začetno osnovo (vsi znaki neenakosti-omejitve "≤").

Zapišimo nalogo kanonično oblika, tj. omejitve neenakosti lahko prepišemo kot enakosti z dodajanjem bilanca stanja spremenljivke:

Ta sistem je sistem z bazo (osnova s ​​1, s 2, s 3, vsaka od njih je vključena v samo eno enačbo sistema s koeficientom 1), x 1 in x 2 sta prosti spremenljivki. Problemi, pri reševanju katerih se uporablja simpleks metoda, morajo imeti naslednji dve lastnosti: - sistem omejitev mora biti sistem enačb z bazo; - prosti členi vseh enačb v sistemu morajo biti nenegativni.

Nastali sistem je sistem z osnovo in njegovi prosti pogoji niso negativni, zato lahko uporabimo simpleks metoda... Sestavimo prvo simpleksno tabelo (Iteracija 0) za rešitev problema simpleks metoda, tj. tabela koeficientov ciljne funkcije in sistem enačb za ustrezne spremenljivke. Tukaj "BP" pomeni stolpec osnovnih spremenljivk, "Rešitev" - stolpec desnih strani enačb sistema. Rešitev ni optimalna, ker v vrstici z so negativni koeficienti.

iteracija simpleksne metode 0

Za izboljšanje rešitve pojdimo na naslednjo ponovitev simpleks metoda, dobimo naslednjo tabelo simpleksa. Če želite to narediti, morate izbrati permisivni stolpec, tj. spremenljivka, ki bo vključena v osnovo pri naslednji iteraciji simpleksne metode. Izbere se z največjim negativnim absolutnim koeficientom v z-vrstici (v največjem problemu) - v začetni iteraciji simpleksne metode je to stolpec x 2 (koeficient -6).

Nato je izbrana dovoljeni niz, tj. spremenljivka, ki bo zapustila osnovo pri naslednji iteraciji simpleksne metode. Izbere se z najmanjšim razmerjem stolpca "Odločitev" do ustreznih pozitivnih elementov ločljivega stolpca (stolpec "Razio") - v začetni iteraciji je to vrstica s 3 (koeficient 20).

Permisivni element se nahaja na presečišču ločljivega stolpca in ločljive vrstice, njena celica je označena, je enaka 1. Zato bo pri naslednji iteraciji simpleks metode spremenljivka x 2 zamenjana v bazi s 1. Upoštevajte, da se relacija ne išče v z-vrstici; tam je postavljen pomišljaj "-". Če obstajajo enaka minimalna razmerja, se izbere katera koli od njih. Če so v stolpcu za reševanje vsi koeficienti manjši ali enaki 0, je rešitev problema neskončna.

Izpolnimo naslednjo tabelo "Iteracija 1". Dobili ga bomo iz tabele "Iteracija 0". Cilj nadaljnjih transformacij je spremeniti ločljivi stolpec x 2 v enoto (z eno namesto ločljivega elementa in ničlami ​​namesto drugih elementov).

1) Izračun vrstice x 2 tabele "Iteracija 1". Najprej razdelimo vse člane ločljive vrstice s 3 tabele "Iteracija 0" z ločljivim elementom (v tem primeru je enak 1) te tabele, v tabeli Iteracije 1 dobimo vrstico x 2. Ker ločevalni element je v tem primeru enak 1, potem bo vrstica s 3 tabele "Iteracija 0" sovpadala z vrstico x 2 tabele "Iteracija 1". Prejeli smo vrstico x 2 tabele "Iteracija 1" 0 1 0 0 1 20, preostale vrstice tabele "Iteracija 1" bodo pridobljene iz te vrstice in vrstice tabele "Iteracija 0" na naslednji način:

2) Izračun z-vrstice tabele "Iteracija 1". Namesto -6 v prvi vrstici (z-vrstica) v stolpcu x 2 tabele Iteracije 0 mora biti 0 v prvi vrstici tabele Iteracije 1. Da bi to naredili, pomnožimo vse elemente vrstice x 2 tabele "Iteracija 1" 0 1 0 0 1 20 s 6, dobimo 0 6 0 0 6 120 in to vrstico dodamo s prvo vrstico (z - vrstico) tabela "Iteracija 0" -4 -6 0 0 0 0, dobimo -4 0 0 0 6 120. V stolpcu x 2 se pojavi nič 0, cilj je dosežen. Elementi dovoljenega stolpca x 2 so označeni z rdečo.

3) Izračun vrstice s 1 tabele "Iteracija 1". Na mestu 1 v s 1 vrstici tabele "Iteracija 0" mora biti 0 v tabeli "Iteracija 1". Da bi to naredili, pomnožimo vse elemente vrstice x 2 tabele "Iteracija 1" 0 1 0 0 1 20 z -1, dobimo 0 -1 0 0 -1 -20 in to vrstico dodamo s s 1 - vrstica tabele "Iteracija 0" 2 1 1 0 0 64, dobimo vrstico 2 0 1 0 -1 44. V stolpcu x 2 dobimo zahtevano 0.

4) Izračun vrstice s 2 tabele "Iteracija 1". Na mestu 3 v vrstici s 2 tabele "Iteracija 0" mora biti 0 v tabeli "Iteracija 1". Da bi to naredili, pomnožimo vse elemente vrstice x 2 tabele "Iteracija 1" 0 1 0 0 1 20 z -3, dobimo 0 -3 0 0 -3 -60 in to vrstico dodamo s s 1 - vrstica tabele "Iteracija 0" 1 3 0 1 0 72, dobimo vrstico 1 0 0 1 -3 12. V stolpcu x 2 dobimo želeno 0. Stolpec x 2 v tabeli "Iteracija 1" je postal ena , vsebuje eno 1, ostalo pa 0.

Vrstice tabele "Iteracija 1" se pridobijo po naslednjem pravilu:

Nova vrstica = stara vrstica - (faktor stolpca ločljivosti stare vrstice) * (nova vrstica ločljivosti).

Na primer, za z-vrstico imamo:

Stara z-vrstica (-4 -6 0 0 0 0) - (- 6) * Nova ločljiva črta - (0 -6 0 0 -6 -120) = Nova z-vrstica (-4 0 0 0 6 120).

Za naslednje tabele se preračun elementov tabele izvede na enak način, zato ga izpustimo.

iteracija simpleksne metode 1

Dovolite stolpec x 1, razrešite vrstico s 2, s 2 zapusti osnovo, x 1 vstopi v osnovo. Na popolnoma enak način dobimo preostale simpleksne tabele, dokler ne dobimo tabele z vsemi pozitivnimi koeficienti v vrstici z. To je znak optimalne mize.

iteracija simpleksne metode 2

Rešilni stolpec s 3, ločljiva vrstica s 1, s 1 zapusti osnovo, s 3 vstopi v osnovo.

iteracija simpleksne metode 3

V vrstici z so vsi koeficienti nenegativni, zato je optimalna rešitev x 1 = 24, x 2 = 16, z max = 192.

11.4. DVOJNA SIMPLEKSNA METODA

Iz rezultatov prejšnjih odstavkov sledi, da lahko za rešitev izvirnega problema preidemo na dual in z uporabo ocen njegovega optimalnega načrta določimo optimalno rešitev prvotnega problema.

Prehod na dvojni problem ni potreben, saj če upoštevamo prvo simpleksno tabelo z eno samo dodatno osnovo, potem je enostavno videti, da je prvotni problem zapisan v stolpce, dvojni pa v vrstice.

Kot je bilo prikazano, je pri reševanju neposrednega problema pri kateri koli iteraciji razlika, tj. velikost - koeficient pri spremenljivki, je enak razliki med desno in levo stranjo ustrezne omejitve dvojnega problema. Če pri reševanju neposrednega problema z maksimirano ciljno funkcijo iteracija ne pripelje do optimalne rešitve, potem za vsaj eno spremenljivko in le za optimalno za vse Razlika.

Če upoštevamo ta pogoj z upoštevanjem dvojnosti, lahko zapišemo

.

Torej če, potem . To pomeni, da če je rešitev neposrednega problema neoptimalna, je rešitev dvojnega problema nedopustna. Na drugi strani pri . Iz tega sledi, da optimalna rešitev direktnega problema ustreza dopustni rešitvi dvojnega problema.

To je omogočilo razvoj nove metode za reševanje problemov linearnega programiranja, pri uporabi katere se sprva dobi nesprejemljiva, a "boljša od optimalne" rešitev (pri običajni simpleks metodi se najprej najde dovoljeno, ampak podoptimalno rešitev). Nova metoda imenovani dvojni simpleks metoda, zagotavlja izpolnjevanje pogoja optimalnosti rešitve in njeno sistematično "približevanje" območju izvedljivih rešitev. Ko se izkaže, da je dobljena rešitev dopustna, se iterativni proces izračunov konča, saj je tudi ta rešitev optimalna.

Metoda dvojnega simpleksa omogoča reševanje problemov linearnega programiranja, katerih sistemi omejitev s pozitivno osnovo vsebujejo proste pogoje katerega koli predznaka. Ta metoda vam omogoča, da zmanjšate število transformacij sistema omejitev, pa tudi velikost tabele simpleksa. Razmislimo o uporabi metode dvojnega simpleksa na primeru.

Primer... Poiščite minimum funkcije

z omejitvami

.

Pojdimo na kanonično obliko:

z omejitvami

Začetna simpleksna tabela je

Začetna osnovna rešitevoptimalno, ni pa sprejemljivo.

Tako kot običajna simpleksna metoda, obravnavana metoda rešitve temelji na uporabi pogojev dopustnosti in optimalnosti.

Pogoj dopustnosti... Največja spremenljivka je izbrana kot izključena spremenljivka. absolutna vrednost negativna bazna spremenljivka (v prisotnosti alternativ je izbira narejena poljubno). Če so vse osnovne spremenljivke nenegativne, se računski proces zaključi, saj je dobljena rešitev izvedljiva in optimalna.

Stanje optimalnost... Spremenljivka, vključena v osnovo, je izbrana izmed neosnovnih spremenljivk, kot sledi. Izračunajo se razmerja koeficientov leve strani-enačbe na ustrezne koeficiente enačbe, povezane z izključeno spremenljivko. Odnosi s pozitivnimi oz nič vrednosti imenovalci so prezrti. Pri problemu minimiziranja uvedene spremenljivke mora ustrezati najmanjše od navedenih razmerij, pri problemu maksimizacije pa razmerje najmanjšega po absolutni vrednosti (ob prisotnosti alternativ se izbira poljubno). Če so imenovalci vseh razmerij enaki nič ali pozitivni, problem nima izvedljivih rešitev.

Po izbiri spremenljivk, ki jih je treba vključiti v osnovo in izključiti za pridobitev naslednje rešitve, se izvede običajna operacija preoblikovanja vrstic simpleksne tabele.

V tem primeru je izključena spremenljivka... Razmerja, izračunana za določitev nove osnovne spremenljivke, so prikazana v naslednji tabeli:

Vključena spremenljivka je izbrana x 2. Naknadna pretvorba nizov povzroči novo tabelo simpleksa:

Nova rešitev tudi optimalno, vendar še vedno ni veljavno. Kot novo izključeno spremenljivko izberite (poljubno) x 3. Definirajmo vključeno spremenljivko.