Näide 5.1. Lahendage simpleksmeetodi abil järgmine lineaarse programmeerimise probleem:

Lahendus:

I iteratsioon:

x3, x4, x5, x6 x1,x2. Väljendame põhimuutujaid vabadena:

Redigeerime eesmärgifunktsiooni järgmisele kujule:

Saadud ülesande põhjal moodustame esialgse simplekstabeli:

Tabel 5.3

Originaal simplekslaud

Põhilahenduse definitsiooni kohaselt on vabad muutujad võrdsed nulliga ja põhimuutujate väärtused on võrdsed vabade arvude vastavate väärtustega, st:

3. etapp: PAP piirangute süsteemi ühilduvuse kontrollimine.

Sellel iteratsioonil (tabelis 5.3) piirangusüsteemi mitteühilduvuse märki (märk 1) ei tuvastata (st ei ole negatiivse vaba arvuga rida (v.a rida). objektiivne funktsioon), milles ei oleks vähemalt ühte negatiivset elementi (st vaba muutuja negatiivset koefitsienti)).

Sellel iteratsioonil (tabelis 5.3) sihtfunktsiooni piiramatuse märki (märk 2) ei tuvastatud (st sihtfunktsiooni real ei ole negatiivse elemendiga veergu (v.a vabade arvude veerg). ), milles poleks vähemalt üht positiivset elementi) .

Kuna leitud põhilahendus ei sisalda negatiivseid komponente, on see lubatav.

6. etapp: optimaalsuse kontroll.

Leitud põhilahendus ei ole optimaalne, kuna optimaalsuse kriteeriumi (märk 4) järgi ei tohiks sihtfunktsiooni real olla negatiivseid elemente (selle kriteeriumi arvestamisel ei võeta arvesse selle rea vaba arvu). Seetõttu liigume vastavalt simpleksmeetodi algoritmile 8. etappi.

Kuna leitud põhilahend on lubatav, siis otsime lahendavat veergu järgmise skeemi järgi: määrame sihtfunktsiooni real negatiivsete elementidega veerud (v.a vabade arvude veerg). Tabeli 5.3 kohaselt on kaks sellist veergu: veerg “ x1" ja veerg " x2" Sellistest veergudest valitakse see, mis sisaldab sihtfunktsiooni rea väikseimat elementi. Temast saab lubaja. veerg " x2" sisaldab väikseimat elementi (–3) võrreldes veeruga " x1

Lahutusjoone määramiseks leiame vabade arvude positiivsed hinnangulised suhted lahutusveeru elementidega, mis võetakse lahendatuks.

Tabel 5.4

Originaal simplekslaud

Tabelis 5.4 vastab väikseim positiivne hinnanguline seos reale “ x5"Seepärast on see lubatav.

Lubava veeru ja lubamisrea ristumiskohas asuv element loetakse lubavaks. Meie näites on see element, mis asub joone " ristumiskohas x5" ja veerud " x2».

Lahenduselement näitab ühte alust ja ühte vaba muutujat, mis tuleb simplekstabelis vahetada, et liikuda uuele "täiustatud" baaslahendusele. IN antud juhul need on muutujad x5 Ja x2, uues simplekstabelis (tabel 5.5) vahetame need ära.

9.1. Lahutava elemendi transformatsioon.

Tabeli 5.4 eraldusvõime element teisendatakse järgmiselt:

Saadud tulemuse sisestame sarnasesse lahtrisse tabelis 5.5.

9.2. Eraldusvõime stringi teisendamine.

Jagame tabeli 5.4 lahutusrea elemendid selle simplekstabeli lahutuselemendiga, tulemused mahuvad uue simplekstabeli (tabel 5.5) sarnastesse lahtritesse. Resolutsioonistringi elementide teisendused on toodud tabelis 5.5.

9.3. Eraldusvõime veeru teisendamine.

Jagame tabeli 5.4 eraldusvõime veeru elemendid selle simplekstabeli eraldusvõime elemendiga ja tulemus võetakse vastupidise märgiga. Saadud tulemused sobivad uue simplekstabeli sarnastesse lahtritesse (tabel 5.5). Eraldusvõime veeru elementide teisendused on toodud tabelis 5.5.

9.4. Simplekstabeli ülejäänud elementide teisendus.

Ülejäänud simplekstabeli elementide (st elemendid, mis ei asu lahutusreas ja lahutusveerus) teisendamine toimub ristküliku reegli järgi.

Näiteks kaaluge joone ristumiskohas asuva elemendi teisendamist x3" ja veerud "", tähistame seda tingimuslikult " x3" Tabelis 5.4 joonistame mõtteliselt ristküliku, mille üks tipp asub lahtris, mille väärtust me teisendame (st lahtris " x3") ja teine ​​(diagonaaltipp) on lahutuselemendiga lahtris. Ülejäänud kaks tippu (teise diagonaali) on üheselt määratud. Seejärel lahtri teisendatud väärtus " x3" on võrdne selle lahtri eelmise väärtusega, millest on lahutatud murdosa, mille nimetajas on lahutuselement (tabelist 5.4) ja lugejas on kahe teise kasutamata tipu korrutis, st:

« x3»: .

Teiste lahtrite väärtused teisendatakse sarnaselt:

« x 3 x 1»: ;

« x4»: ;

« x4x1»: ;

« x6»: ;

« x 6 x 1»: ;

«»: ;

« x1»: .

Nende teisenduste tulemusena saadi uus simplekstabel (tabel 5.5).

II iteratsioon:

1. etapp: simplekstabeli koostamine.

Tabel 5.5

Simplex tabelII iteratsioonid

2. etapp: põhilahuse määramine.

Simpleksteisenduste tulemusena saadi uus aluseline lahendus (tabel 5.5):

Nagu näete, on selle põhilahenduse korral sihtfunktsiooni väärtus 15, mis on suurem kui eelmise põhilahenduse puhul.

Tabeli 5.5 tunnuse 1 kohase piirangute süsteemi vastuolu ei ole tuvastatud.

4. etapp: sihtfunktsiooni piirituse kontrollimine.

Tabeli 5.5 kriteeriumi 2 kohase sihtfunktsiooni piiramatust ei selgu.

5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.

Kriteeriumile 4 vastav leitud põhilahend ei ole optimaalne, kuna simplekstabeli (tabel 5.5) eesmärkfunktsiooni rida sisaldab negatiivset elementi: –2 (selle rea vaba arvu selle arvestamisel arvesse ei võeta iseloomulik). Seetõttu liigume edasi 8. etapi juurde.

8. etapp: lahutuselemendi määramine.

8.1. Eraldusvõime veeru määratlus.

Leitud põhilahendus on vastuvõetav, määrame sihtfunktsiooni real negatiivsete elementidega veerud (va vabade arvude veerg). Tabeli 5.5 kohaselt on ainult üks selline veerg: “ x1" Seetõttu aktsepteerime seda lubatud kujul.

8.2. Loa stringi definitsioon.

Tabelis 5.6 saadud positiivsete hindamissuhete väärtuste järgi on miinimumiks reale " vastav seos. x3" Seetõttu aktsepteerime seda lubatud kujul.

Tabel 5.6

Simplex tabelII iteratsioonid

9. etapp: simplekstabeli teisendus.

Simplekstabeli (tabel 5.6) teisendused sooritatakse samamoodi nagu eelmises iteratsioonis. Simplekstabeli elementide teisenduste tulemused on toodud tabelis 5.7.

III iteratsioon

Eelmise iteratsiooni simpleksteisenduste tulemuste põhjal koostame uue simplekstabeli:

Tabel 5.7

Simplex tabelIII iteratsioonid

2. etapp: põhilahuse määramine.

Simpleksteisenduste tulemusena saadi uus aluseline lahendus (tabel 5.7):

3. etapp: piirangute süsteemi ühilduvuse kontrollimine.

Tabeli 5.7 tunnuse 1 kohase piirangute süsteemi vastuolu ei ole tuvastatud.

4. etapp: sihtfunktsiooni piirituse kontrollimine.

Tabeli 5.7 kriteeriumi 2 kohase sihtfunktsiooni piiramatust ei selgu.

5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.

Leitud põhilahendus vastavalt kriteeriumile 3 on vastuvõetav, kuna see ei sisalda negatiivseid komponente.

6. etapp: leitud põhilahenduse optimaalsuse kontrollimine.

Kriteeriumile 4 vastav leitud põhilahend ei ole optimaalne, kuna simplekstabeli (tabel 5.7) sihtfunktsiooni rida sisaldab negatiivset elementi: –3 (selle rea vaba arvu selle arvestamisel arvesse ei võeta iseloomulik). Seetõttu liigume edasi 8. etapi juurde.

8. etapp: lahutuselemendi määramine.

8.1. Eraldusvõime veeru määratlus.

Leitud põhilahendus on vastuvõetav, määrame sihtfunktsiooni real negatiivsete elementidega veerud (va vabade arvude veerg). Tabeli 5.7 kohaselt on ainult üks selline veerg: “ x5" Seetõttu aktsepteerime seda lubatud kujul.

8.2. Loa stringi definitsioon.

Vastavalt tabelis 5.8 saadud positiivsete hindamissuhete väärtustele on miinimumiks reale " vastav seos. x4" Seetõttu aktsepteerime seda lubatud kujul.

Tabel 5.8

Simplex tabelIII iteratsioonid

9. etapp: simplekstabeli teisendus.

Simplekstabeli (tabel 5.8) teisendused sooritatakse samamoodi nagu eelmises iteratsioonis. Simplekstabeli elementide teisenduste tulemused on toodud tabelis 5.9.

IV iteratsioon

1. etapp: uue simplekslaua ehitamine.

Eelmise iteratsiooni simpleksteisenduste tulemuste põhjal koostame uue simplekstabeli:

Tabel 5.9

Simplex tabelIV iteratsioonid

2. etapp: põhilahuse määramine.

Simpleksteisenduste tulemusena saadi uus põhilahend vastavalt tabelile 5.9, lahend on järgmine:

3. etapp: piirangute süsteemi ühilduvuse kontrollimine.

Tabeli 5.9 tunnuse 1 kohase piirangute süsteemi vastuolu ei ole tuvastatud.

4. etapp: sihtfunktsiooni piirituse kontrollimine.

Tabeli 5.9 kriteeriumi 2 kohase sihtfunktsiooni piiramatust ei selgu.

5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.

Leitud põhilahendus vastavalt kriteeriumile 3 on vastuvõetav, kuna see ei sisalda negatiivseid komponente.

6. etapp: leitud põhilahenduse optimaalsuse kontrollimine.

Leitud põhilahendus vastavalt tunnusele 4 on optimaalne, kuna simplekstabeli (tabel 5.9) sihtfunktsiooni real ei ole negatiivseid elemente (selle tunnuse arvestamisel selle rea vaba arvu ei võeta arvesse) .

7. etapp: lahenduse alternatiivsuse kontrollimine.

Leitud lahendus on unikaalne, kuna sihtfunktsiooni real (tabel 5.9) nullelemente ei ole (selle tunnuse arvestamisel selle rea vaba arvu ei võeta arvesse).

Vastus: optimaalne väärtus vaadeldava probleemi eesmärkfunktsioon =24, mis saavutatakse juures.

Näide 5.2. Lahendage ülaltoodud lineaarse programmeerimise probleem tingimusel, et sihtfunktsioon on minimeeritud:

Lahendus:

I iteratsioon:

1. etapp: algse simplekstabeli moodustamine.

Algne lineaarse programmeerimise ülesanne on antud standardkujul. Viime selle kanoonilisele kujule, lisades igasse ebavõrdsuse piirangusse täiendava mittenegatiivse muutuja, st.

Saadud võrrandisüsteemis võtame lubatud (põhi)muutujad x3, x4, x5, x6, siis on vabad muutujad x1,x2. Väljendame põhimuutujaid vabadena.

Lühike teooria

Lineaarse programmeerimise probleemide lahendamiseks on välja pakutud palju erinevaid meetodeid. Kõige tõhusamaks ja universaalsemaks nende seas osutus aga simpleksmeetod. Tuleb märkida, et mõne probleemi lahendamisel võivad teised meetodid olla tõhusamad. Näiteks kahe muutujaga ZLP puhul on optimaalne meetod ja selle lahendamiseks kasutatakse potentsiaalimeetodit. Simpleksmeetod on põhiline ja rakendatav iga kanoonilise vormi PPL-i puhul.

Seoses lineaarse programmeerimise põhiteoreemiga tekib loomulikult mõte, kuidas lahendada elukestva õppe programm suvalise arvu muutujatega. Leidke mingil moel kõik plaanide hulktahuka äärmised punktid (neid pole rohkem kui ) ja võrrelge nendes sihtfunktsiooni väärtusi. Selline lahendus isegi suhteliselt väikese arvu muutujate ja piirangute korral on praktiliselt võimatu, kuna äärmuslike punktide leidmise protsess on raskustes võrreldav algse ülesande lahendamisega ning pealegi võib plaanide hulktahuka äärmuslike punktide arv. osutuvad väga suureks. Nende raskustega seoses kerkis esile äärmuslike punktide ratsionaalse loendamise probleem.

Simpleksmeetodi olemus on järgmine. Kui on teada mõni äärmuspunkt ja sihtfunktsiooni väärtus selles, siis pole ilmselgelt vaja kõiki äärmuspunkte, kus sihtfunktsioon saab halvima väärtuse. Seega on loomulik soov leida viis, kuidas liikuda antud äärmisest punktist paremasse, mis külgneb servaga, sealt veelgi paremasse (mitte halvemasse) jne. Selleks peab teil olema märk, et pole paremaid äärmuspunkte kui antud äärmuspunkt. See on mis üldine idee praegu kõige laialdasemalt kasutatav simpleksmeetod (plaani järjestikuse täiustamise meetod) ZLP lahendamiseks. Niisiis, algebralises mõttes eeldab simpleksmeetod:

1. oskus leida esialgne võrdlusplaan;
2. võrdlusplaani optimaalsuse märgi olemasolu;
3. võimalus liikuda mitte-halvima võrdlusplaani juurde.

Näide probleemi lahendamisest

Probleemne seisund

Kolme kaubagrupi müümiseks on äriettevõttel kolme liiki piiratud materiaalseid ja rahalisi ressursse summas , , , ühikut. Samal ajal 1 kaubagrupi müügiks 1000 rubla eest. kaubakäive tarbib ühikute arvult esimest tüüpi ressurssi, ühikute arvult teist tüüpi ressurssi, ühikute arvult kolmandat tüüpi ressurssi. 2 ja 3 kaubagrupi müügiks 1000 rubla eest. kaubakäivet kulutatakse vastavalt esimest tüüpi ressursile summas , ühikut, teise liigi ressursse summas , ühikuid, kolmanda liigi ressursse summas , ühikut. Kasum kolme kaubagrupi müügist 1 tuhande rubla eest. käive on vastavalt , tuhat rubla.

• Määrake kaubanduskäibe kavandatav maht ja struktuur selliselt, et kaubandusettevõtte kasum oleks maksimaalne.
• Käibe planeerimise otsese probleemi jaoks, mis on lahendatud simpleksmeetodil, loo duaalne lineaarne programmeerimisülesanne.
• Määrake otse- ja duaalprobleemide muutujate konjugeeritud paarid.
• Konjugeeritud muutujapaaride järgi saadakse otsese ülesande lahendusest lahendus duaalülesandele, milles hinnatakse kaupade müümiseks kulutatud ressursse.

Kui teie seansile pääsemine sõltub probleemide ploki lahendamisest ja teil pole aega ega soovi arvutuste tegemiseks maha istuda, kasutage veebisaidi võimalusi. Ülesannete tellimine võtab vaid mõne minuti. Täpsemalt (kuidas taotlust esitada, hinnad, tingimused, makseviisid) saad lugeda lehelt Osta lahendusi lineaarse programmeerimise probleemidele...

Probleemi lahendus

Mudeli ehitamine

Tähistagem vastavalt 1., 2. ja kolmanda kaubaliigi käivet.

Seejärel saadud kasumit väljendav sihtfunktsioon:

Materiaalsete ja rahaliste ressursside piirangud:

Lisaks vastavalt ülesande tähendusele

Saame järgmise lineaarse programmeerimise probleemi:

Redutseerimine ZLP kanoonilisele vormile

Taandagem probleem kanooniliseks vormiks. Ebavõrdsuse muutmiseks võrdsusteks võtame kasutusele täiendavad muutujad. Muutujad sisalduvad piirangutes koefitsiendiga 1. Kõik lisamuutujad sisestame sihtfunktsiooni koefitsiendiga, mis on võrdne nulliga.

Piirangul on eelistatav vorm, kui parem pool on mittenegatiivne vasak pool sisaldab muutujat, mille koefitsient on võrdne ühega, ja ülejäänud võrdsuse piirangud - koefitsiendiga, mis on võrdne nulliga. Meie puhul on 1., 2., 3. piirangul eelistatud vorm koos vastavate põhimuutujatega.

Lahendus simpleksmeetodil

Täidame 0. iteratsiooni simplekstabeli.

Kuna lahendame ülesande maksimaalselt, siis negatiivsete arvude olemasolu indeksreal ülesande maksimaalsel lahendamisel viitab sellele, et me ei ole saanud optimaalset lahendust ja on vaja liikuda edasi 0. iteratsiooni tabelist järgmisele.

Jätkame järgmise iteratsiooniga järgmiselt:

Juhtveerg vastab .

Võtmerea määrab vabade liikmete ja juhtiva veeru liikmete minimaalne suhe (simplekssuhted):

Võtme veeru ja võtmerea ristumiskohast leiame lubava elemendi, st 7.

Nüüd hakkame koostama esimest iteratsiooni. Ühikvektori asemel võtame kasutusele vektori .

Uues tabelis kirjutame lubava elemendi asemele 1, kõik muud võtme veeru elemendid on nullid. Võtmestringi elemendid on jagatud lubamiselemendiks. Kõik ülejäänud tabeli elemendid arvutatakse ristkülikureegli abil.

Saame 1. iteratsiooni tabeli:

1. iteratsiooni võtmeveerg vastab .

Leiame võtmerea, selleks määratleme:

Võtme veeru ja võtmerea ristumiskohast leiame lubava elemendi, s.o. 31/7.

Vektor tuletatakse baasist ja sisestatakse vektor.

Saame 2. iteratsiooni tabeli:

Indeksireas on kõik terminid mittenegatiivsed, seega saadakse järgmine lineaarse programmeerimise ülesande lahendus (kirjutame selle välja vabade terminite veerust):

Seega on vaja müüa 7,1 tuhat rubla. 1. tüüpi kaubad ja 45,2 tuhat rubla. 3. tüüpi kaubad. 2. tüüpi toodet ei ole tasuv müüa. Sel juhul on kasum maksimaalne ja ulatub 237,4 tuhande rublani. Optimaalse plaani elluviimisel on 3. tüüpi järelejäänud ressurss 701 ühikut.

Kahe LP probleem

Kirjutame üles kaksikülesande mudeli.

Topeltprobleemi koostamiseks peate järgima järgmisi reegleid:

1) kui otseülesanne on lahendatud maksimaalselt, siis duaalülesanne on lahendatud minimaalselt ja vastupidi;

2) maksimumülesandes on ebavõrdsuse piirangute tähendus ≤ ja minimeerimisülesandes ≥;

3) igale otseülesande piirangule vastab duaalülesande muutuja ja vastupidi, igale duaalülesande piirangule vastab otseülesande muutuja;

4) duaalülesande piirangute süsteemi maatriks saadakse algülesande piirangute süsteemi maatriksist transponeerimise teel;

5) otseülesande piirangute süsteemi vabaliikmed on duaalülesande sihtfunktsiooni vastavate muutujate koefitsiendid ja vastupidi;

6) kui otseülesande muutujale on peale pandud mittenegatiivsustingimus, siis duaalülesande vastav piirang kirjutatakse ebavõrdsuspiiranguks, kui mitte, siis võrduspiiranguks;

7) kui võrdsusena kirjutatakse mõni otseülesande kitsendus, siis duaalülesande vastavale muutujale mittenegatiivsustingimust peale ei panda.

Transponeerime algse probleemi maatriksi:

Taandagem probleem kanooniliseks vormiks. Tutvustame täiendavaid muutujaid. Kõik lisamuutujad sisestame sihtfunktsiooni koefitsiendiga, mis on võrdne nulliga. Lisame piirangute vasakule küljele täiendavad muutujad, millel ei ole eelistatud vormi, ja saame võrdsused.

Kahe LP probleemi lahendus

Algse ja duaalse probleemi muutujate vaheline vastavus:

Simplekstabeli põhjal saadi topeltlineaarse programmeerimise probleemile järgmine lahendus (kirjutame selle välja alumiselt realt):

Seega on esimest tüüpi ressurss kõige napim. Selle skoor on maksimaalne ja võrdne . Kolmanda tüübi ressurss on üleliigne - selle kahekordne väärtus on null. Iga müüdud täiendav 2. rühma kaubaühik vähendab optimaalset kasumit võrra
Vaadeldakse graafilist meetodit kahe muutujaga lineaarse programmeerimisülesande (LPP) lahendamiseks. Ülesande näide on toodud üksikasjalik kirjeldus joonise konstrueerimine ja lahenduse leidmine.

Transpordiprobleemi lahendus
Täpsemalt käsitletakse transpordiprobleemi, selle matemaatilist mudelit ja lahendusviise - võrdlusplaani leidmine miinimumelemendi meetodil ja optimaalse lahenduse otsimine potentsiaalimeetodil.

Otsuste tegemine ebakindluse tingimustes
Statistilise maatriksmängu lahendamist määramatuse tingimustes kaalutakse Waldi, Savage'i, Hurwitzi, Laplace'i ja Bayesi kriteeriumide abil. Kasutades näiteprobleemi, on üksikasjalikult näidatud maksemaatriksi ja riskimaatriksi konstrueerimine.

On vaja lahendada lineaarse programmeerimise ülesanne.

Objektiivne funktsioon:

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

Piirtingimused:

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

Viime piirangute süsteemi kanoonilisele kujule, selleks on vaja liikuda ebavõrdsustelt võrdsustele, lisades sellele täiendavad muutujad.

Kuna meie probleem on minimeerimisprobleem, peame selle muutma maksimaalse otsingu probleemiks. Selleks muudame sihtfunktsiooni kordajate märgid vastupidisteks. Kirjutame esimese võrratuse elemendid muutmata, lisades täiendava muutuja x 5 ja muutes märgi “≤” väärtuseks “=". Kuna teisel ja kolmandal võrratusel on märgid “≥”, on vaja muuta nende kordajate märgid vastupidisteks ja sisestada neisse vastavalt täiendavad muutujad x 6 ja x 7. Selle tulemusena saame samaväärse probleemi:

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

Jätkame esialgse simplekstabeli moodustamisega. Tabeli rida F sisaldab sihtfunktsiooni koefitsiente koos vastupidine märk.

Kuna vabade terminite veerus ei ole negatiivseid elemente, on leitud lubatav lahendus rida F, mis tähendab, et saadud lahendus ei ole optimaalne. Määratleme juhtiva veeru. Selleks leiame realt F maksimaalse mooduliga negatiivse elemendi - see on -1,988 Juhtreaks saab see, mille vaba liikme ja juhtiva veeru vastava elemendi suhe on minimaalne. Juhtrida on X2 ja juhtelement on: 0,313.

Kuna stringis F pole negatiivseid elemente, leidsime optimaalne lahendus. Kuna algne ülesanne oli leida miinimum, siis optimaalseks lahenduseks saab stringi F vaba liige, mis on võetud vastupidise märgiga. F = 1,924
muutuvate väärtustega, mis on võrdsed: x 3 = 0,539, x 1 = 0,153. Muutujad x 2 ja x 4 ei sisaldu baasis, seega x 2 =0 x 4 =0.

Siin on kahe ülesande käsitsi (mitte apleti) lahendus, kasutades simpleksmeetodit (sarnaselt apleti lahendusele) koos üksikasjalike selgitustega, et mõista ülesannete lahendamise algoritmi simpleksmeetodil. Esimene ülesanne sisaldab ainult ebavõrdsusmärke “≤” (probleem algalusega), teine ​​võib sisaldada märke “≥”, “≤” või “=” (tehisliku alusega probleem), neid lahendatakse erinevalt.

Simpleksmeetod, ülesande lahendamine esialgsel alusel

1)Lihtne meetod esialgse alusega ülesande jaoks (kõik ebavõrdsuse piirangute märgid " ≤ ").

Kirjutame probleemi sisse kanooniline vorm, s.t. kirjutame ebavõrdsuse piirangud ümber võrduste kujul, lisades bilanss muutujad:

See süsteem on baasiga süsteem (baas s 1, s 2, s 3, igaüks neist sisaldub ainult ühes süsteemi võrrandis koefitsiendiga 1), x 1 ja x 2 on vabad muutujad. Simpleksmeetodil lahendatavatel ülesannetel peab olema kaks järgmist omadust: - piirangute süsteem peab olema alusega võrrandisüsteem; -süsteemi kõigi võrrandite vabad liikmed peavad olema mittenegatiivsed.

Saadud süsteem on alusega süsteem ja selle vabad tingimused on mittenegatiivsed, seega saame rakendada simpleks meetod. Loome ülesande lahendamiseks esimese simplekstabeli (iteratsioon 0). simpleks meetod, st. sihtfunktsiooni koefitsientide tabel ja võrrandisüsteem vastavate muutujate jaoks. Siin tähendab "BP" põhimuutujate veergu, "Lahendus" tähendab süsteemi võrrandite parempoolsete külgede veergu. Lahendus pole optimaalne, sest z-reas on negatiivsed koefitsiendid.

simpleksmeetodi iteratsioon 0

Lahenduse parandamiseks liigume järgmise iteratsiooni juurde simpleks meetod, saame järgmise simplekstabeli. Selleks peate valima luba veerg, st. muutuja, mis kaasatakse lihtmeetodi järgmisel iteratsioonil baasi. See valitakse z-rea suurima absoluutse negatiivse koefitsiendiga (maksimaalses ülesandes) - simpleksmeetodi algses iteratsioonis on see veerg x 2 (koefitsient -6).

Seejärel valige luba string, st. muutuja, mis lahkub baasist simpleksmeetodi järgmisel iteratsioonil. See valitakse veeru „Otsus” väikseima suhte järgi eraldusvõime veeru vastavate positiivsete elementide vahel (veerg „Suhe”) - algses iteratsioonis on see rida s 3 (koefitsient 20).

Lubav element on lahendava veeru ja lahutusrea ristumiskohas, selle lahter on värviliselt esile tõstetud, see võrdub 1-ga. Seetõttu asendab simpleksmeetodi järgmisel iteratsioonil muutuja x 2 baasis s 1. Pange tähele, et z-stringist seost ei otsita, sinna pannakse kriips “-”. Kui minimaalsed seosed on identsed, valitakse neist ükskõik milline. Kui kõik eraldusvõime veerus olevad koefitsiendid on 0-st väiksemad või sellega võrdsed, on ülesande lahendus lõpmatu.

Täidame järgmise tabeli “Iteratsioon 1”. Saame selle tabelist "Iteratsioon 0". Edasiste teisenduste eesmärk on muuta x2 eraldusvõime veerg ühikveeruks (eraldusvõime elemendi asemel on üks ja ülejäänud elementide asemel nullid).

1) Arvutage tabeli “Iteratsioon 1” rida x 2. Esiteks jagame tabeli “Iteratsioon 0” lahendava rea ​​s 3 kõik liikmed selle tabeli lahutuselemendiga (antud juhul on see 1), saame tabelis “Iteratsioon 1” rea x 2. . Sest Lahutuselement on sel juhul võrdne 1-ga, siis tabeli "Iteratsioon 0" rida s 3 langeb kokku tabeli "Iteratsioon 1" reaga x 2. Tabeli Iteratsioon 1 rida x 2 saime 0 1 0 0 1 20, ülejäänud iteratsiooni 1 tabeli read saadakse sellest reast ja tabeli iteratsioon 0 read järgmiselt:

2) Tabeli “Iteratsioon 1” z-rea arvutamine. Tabeli iteratsioon 0 veerus x2 esimese rea (z-rida) -6 asemel peaks tabeli iteratsioon 1 esimeses reas olema 0. Selleks korrutage kõik tabeli "Iteratsioon 1" rea x 2 elemendid 0 1 0 0 1 20 6-ga, saage 0 6 0 0 6 120 ja lisage see rida tabeli esimese reaga (z - rida). tabel "Iteratsioon 0" -4 -6 0 0 0 0, saame -4 0 0 0 6 120. x 2 veergu ilmub null 0, eesmärk on saavutatud. Eraldusvõime veeru x 2 elemendid on punasega esile tõstetud.

3) Tabeli “Iteratsioon 1” rea s 1 arvutamine. Tabeli „Iteratsioon 0” reas 1 asemel 1 peaks tabelis „Iteratsioon 1” olema 0. Selleks korrutage kõik tabeli "Iteratsioon 1" rea x 2 elemendid 0 1 0 0 1 20 -1-ga, saage 0 -1 0 0 -1 -20 ja lisage see rida s 1 - reaga. tabel "Iteratsioon 0" 2 1 1 0 0 64, saame rea 2 0 1 0 -1 44. Veerus x 2 saame vajaliku 0.

4) Arvutage tabeli “Iteratsioon 1” rida s 2. Tabeli "Iteratsioon 0" rea s 2 kohas 3 peaks tabelis "Iteratsioon 1" olema 0. Selleks korrutage kõik tabeli "Iteratsioon 1" rea x 2 elemendid 0 1 0 0 1 20 -3-ga, saame 0 -3 0 0 -3 -60 ja lisage see rida s 1 - rida tabel "Iteratsioon 0" 1 3 0 1 0 72, saame rea 1 0 0 1 -3 12. Veerus x 2 saadakse vajalik 0. Tabelis "Iteratsioon 1" on saanud veerg x 2 ühik, see sisaldab ühte 1 ja ülejäänud 0.

Tabeli “Iteratsioon 1” read saadakse järgmise reegli järgi:

Uus rida = vana rida – (vana rea ​​eraldusvõime veeru koefitsient)* (uus eraldusvõime rida).

Näiteks z-stringi jaoks on meil:

Vana z-string (-4 -6 0 0 0 0) -(-6)*Uus lahendav string -(0 -6 0 0 -6 -120) =Uus z-string (-4 0 0 0 6 120).

Järgmiste tabelite puhul tehakse tabelielementide ümberarvutamine sarnaselt, seega jätame selle ära.

simpleksmeetodi iteratsioon 1

Lahendades veeru x 1, lahendades rea s 2, s 2 lahkub baasist, x 1 läheb alusesse. Täpselt samamoodi saame ülejäänud simplekstabelid, kuni saame tabeli, kus on kõik positiivsed koefitsiendid z-reas. See on optimaalse laua märk.

simpleksmeetodi iteratsioon 2

Lahendades veeru s 3, lahendades rida s 1, s 1 lahkub baasist, s 3 siseneb alusele.

simpleksmeetodi iteratsioon 3

Z-reas on kõik koefitsiendid mittenegatiivsed, seetõttu saadakse optimaalne lahendus x 1 = 24, x 2 = 16, z max = 192.

11.4. KAHELINE LIHTNE MEETOD

Eelnevate lõikude tulemustest järeldub, et esialgsele probleemile lahenduse saamiseks võib minna kahele ja selle optimaalse plaani hinnanguid kasutades määrata algsele probleemile optimaalne lahendus.

Duaalülesandele üleminek ei ole vajalik, sest kui arvestada esimest ühikulise lisabaasiga simplekstabelit, siis on lihtne märgata, et algülesanne on kirjutatud veergudesse ja duaalülesanne ridadesse.

Nagu näidatud, on vahetu probleemi lahendamisel mis tahes iteratsioonil erinevus, st. suurusjärk -muutuja koefitsient, on võrdne duaalülesande vastava piirangu parema ja vasaku külje erinevusega. Kui otsese probleemi lahendamisel maksimeeritud sihtfunktsiooniga ei vii iteratsioon optimaalse lahenduseni, siis vähemalt ühe muutuja jaoks ja ainult optimaalsel juhul kõigi jaoks erinevus .

Arvestades seda tingimust, võttes arvesse duaalsust, võime kirjutada

.

Seega, kui, See. See tähendab, et kui otsese probleemi lahendus on ebaoptimaalne, ei ole topeltprobleemi lahendus teostatav. Teisel pool aadressil . Sellest järeldub, et otsese probleemi optimaalne lahendus vastab duaalse probleemi lubatavale lahendusele.

See võimaldas välja töötada uue meetodi lineaarse programmeerimise ülesannete lahendamiseks, mis annab esmalt vastuvõetamatu, kuid "optimaalsest parema" lahenduse (tavalises simpleksmeetodis leitakse kõigepealt vastuvõetav, Aga suboptimaalne lahendus). Uus meetod, kutsus dual simplex meetod, tagab lahenduse optimaalsuse tingimuste täitmise ja selle süstemaatilise “lähendamise” teostatavate lahenduste piirkonnale. Kui saadud lahendus osutub teostatavaks, siis iteratiivne arvutusprotsess lõpeb, kuna ka see lahendus on optimaalne.

Dual simplex meetod võimaldab lahendada lineaarse programmeerimise ülesandeid, mille piirangusüsteemid sisaldavad positiivsel alusel mis tahes märgiga vabu tingimusi. See meetod võimaldab vähendada piirangusüsteemi teisenduste arvu ja ka simplekstabeli suurust. Vaatleme näite abil dual simplex meetodi rakendamist.

Näide. Leia funktsiooni miinimum

piirangute all

.

Liigume edasi kanoonilise vormi juurde:

piirangute all

Algsel simplekstabelil on vorm

Esialgne baaslahendusoptimaalne, kuid mitte vastuvõetav.

Nagu tavaline simpleksmeetod, põhineb ka vaadeldav lahendusmeetod lubatavuse ja optimaalsuse tingimuste kasutamisel.

Vastuvõetavuse tingimus. Suurim muutuja valitakse välistatud muutujaks. absoluutväärtus negatiivne põhimuutuja (alternatiivide olemasolul tehakse valik meelevaldselt). Kui kõik põhimuutujad on mittenegatiivsed, siis arvutusprotsess lõpeb, kuna saadud lahendus on teostatav ja optimaalne.

Seisund optimaalsus. Alusesse kuuluv muutuja valitakse mittepõhimuutujate hulgast järgmiselt. Arvutatakse vasaku külje koefitsientide suhted-võrrandid välistatud muutujaga seotud võrrandi vastavatele kordajatele. Suhted positiivse või nullväärtus nimetajaid ei võeta arvesse. Minimeerimisülesandes peab sisendmuutuja vastama määratud suhtarvudest väikseimale, maksimeerimisülesandes aga absoluutväärtuselt väikseimale suhtele (alternatiivide olemasolul tehakse valik suvaliselt). Kui kõigi suhtarvude nimetajad on nullid või positiivsed, pole probleemil võimalikke lahendusi.

Pärast baasi kaasatavate ja välistatavate muutujate valimist viiakse järgmise lahenduse saamiseks läbi tavaline simplekstabeli ridade teisendamise operatsioon.

Selles näites on välistatud muutuja. Uue baasmuutuja määramiseks arvutatud suhtarvud on toodud järgmises tabelis:

Valitakse kaasatud muutuja x 2. Järgneva stringi teisendamise tulemuseks on uus simplekstabel:

Uus lahendus samuti optimaalne, kuid siiski vastuvõetamatu. Uue välistatud muutujana valime (suvaliselt) x 3. Määratleme kaasatava muutuja.