Nagu teada, on Jordani-Gaussi meetod, tuntud ka kui tundmatute järjestikuse elimineerimise meetod, Gaussi meetodi modifikatsioon lineaarsete algebraliste võrrandite (SLAE) lahendamiseks.
Meetod põhineb elementaarsed teisendused(süsteemi tõlkimine samaväärseks), mis hõlmavad järgmist:
- süsteemi võrrandi mõlemale poolele teise sama süsteemi võrrandi lisamine, mis on korrutatud nullist erineva arvuga;
- võrrandite ümberkorraldamine süsteemis;
- eemaldamine võrrandisüsteemist kujul 0 = 0.
Erinevalt Gaussi meetodist elimineeritakse igas etapis üks muutuja kõigist võrranditest peale ühe.
Meetodi samm on järgmine:
- vali järgmises võrrandis tundmatu nullist erineva koefitsiendiga (lahutav element);
- jaga valitud võrrand lahendava elemendiga;
- kasutades valitud võrrandit, jätke lahendaval elemendil tundmatu kõigist teistest võrranditest välja;
- järgmises etapis jäetakse teine tundmatu samamoodi välja kõigist võrranditest, välja arvatud üks;
- protsess jätkub seni, kuni kõik võrrandid on kasutatud.
Saate seda algoritmiseerida järgmiselt:
SLAU jaoks in maatriksvorm A*x=b (maatriks A mõõtmega m*n, mitte tingimata ruut), koostatakse järgmine tabel:
Tabelis valitakse lahutuselement a r,s ≠0, siis r on lahutusrida, s on lahutusveerg.
Üleminek järgmisele tabelile toimub vastavalt reeglitele:
1. arvutatakse lahutusrea elemendid: a" r,j =a r,j /a r,s - see tähendab, et tabeli r-rida jagatakse lahutuselemendiga;
2. eraldusvõime veeru kõik elemendid, välja arvatud a r,s võrdne ühega, muutuvad võrdseks nulliga;
3. Lubatud reast ja veerust väljapoole jäävad elemendid arvutatakse alloleva valemi abil.
Segadust on lihtne vältida, kui näete, et selle valemi lugeja sarnaneb 2x2 maatriksi determinandi arvutamisega.
4. Käsitsi arvutamisel võrreldakse viimase kontrollveeru väärtust summaga varasemad elemendid read. Kui väärtused ei ühti, tuleks sellelt realt vigu otsida. Automaatarvutuste puhul võib juhtveeru ära jätta.
Võimalikud on järgmised juhtumid:
1. Eliminatsioonide protsessis vasak pool süsteemi võrrand muutub 0-ks ja parem käsi b≠0, siis pole süsteemil lahendust.
2. Saadud identsus 0 = 0 – võrrand on lineaarne kombinatsioonülejäänu ja nullide jada saab süsteemist kustutada.
3. Pärast kõigi võrrandite kasutamist tundmatute kõrvaldamiseks sisaldab tabel soovitud lahendust või näitab piirangute süsteemi ebaühtlust.
Programmeerime meetodi Excelis ühe valemi abil, mille muutmine ei tohiks olla liiga keeruline. Näiteks SLAE lahendamiseks
Täidame lehe lahtrid vahemikus A1 kuni D4 (kaasa arvatud) süsteemi koefitsientidega, valime lahutuselemendiks a 1,1 =1 ja teeme meetodi esimese sammu lahtrisse A6, kuhu sisestame “universaalse” valemi. Jordani-Gaussi teisendus:
IF(RIDA($A$1)=RIDA(A1);A1/$A$1;
IF(VEerg($A$1)=VEerg(A1),0,(A1*$A$1-
KUDNE(ADDRESS(RIDA(A1),VEerg($A$1)))*
KAUDNE(ADDRESS(RIDA($A$1),VEerg(A1)))/$A$1))
Järgmises etapis võib lahutuselemendiks olla näiteks 2,2 =1 (lahter B7). Kõik, mida me tegema peame, on kopeerida valem A6-st A11-sse (by tühi rida jätke meetodi sammud visuaalselt eraldama), sisenege valemi redigeerimisrežiimi ( topeltklõps lahtri järgi või valige see ja vajutage klahvi F2) ja parandage (lohistage hiirt ettevaatlikult väljaspool piiri) kõik kinnitatud lingid lahtrist A1 lahtrisse B7.
Muidugi võite valemis igal pool kinnitatud viite $A$1 asendada konstruktsiooniga kujul INDIRECT(CELL) , moodustades dünaamiline aadress lingid. Oletame, et INDIRECT(F8) ja lahtris F8 genereerib lahutuselemendi lahtri aadress automaatselt kasutaja määratud rea ja veeru number. Seejärel peate nende ridade ja veergude numbrite jaoks esitama eraldi lahtrid, näiteks järgmiselt:
Paraku ei anna see kõik midagi – $A$1 asemel peame valemis lihtsalt parandama INDIRECT($F$8) ja seejärel valemit kopeerides lohistama sama palju linke. Lisaks tuleb kontrollida ka “käsitsi” sisestatud rea- ja veerunumbrite kehtivust (vähemalt nagu joonisel), nii et üksusi me korrutama ei hakka.
Meetodit näete manustatud dokumendi kahel esimesel lehel Exceli fail(2 erinevat näidet).
See põhineb ka Jordani-Gaussi teisendusel universaalne meetod lahendusi lineaarsed probleemid optimeerimine, kuidas simpleks meetod. Selle kirjeldused on tavaliselt hirmutavad, pikad ja teoreemidest ülekoormatud. Proovime teha lihtsa kirjelduse ja töötada välja Excelis arvutamiseks sobiva algoritmi. Tegelikult on simpleksmeetod juba sisse ehitatud standardne lisand Analüüsipakett ja seda pole vaja “käsitsi programmeerida”, seega on meie koodil pigem hariv väärtus.
Esiteks, minimaalselt teooriat.
Kui SLAE veeruvektorid on lineaarselt sõltumatud, on vastavad muutujad põhilised ja ülejäänud - tasuta. Näiteks SLAU-s
muutujad x 2 ja x 4 on põhilised ning x 1 ja x 3 on vabad. Põhimuutujad on üksteisest sõltumatud ja vabadest saab teha näiteks nullid ja saada ( x 2 =2, x 4 =1) – põhilahendus süsteemid.
Erinevaid lahutuselemente valides on võimalik saada erinevate alustega SLAE lahendusi. Kutsutakse SLAE mis tahes mittenegatiivset põhilahendust toetades.
Simpleksmeetod võimaldab üleminekut ühelt etalonlahenduselt teisele kuni selle saavutamiseni optimaalne lahendus, mis annab minimaalse eesmärgifunktsiooni.
Simpleksmeetodi algoritm on järgmine:
1. LP probleem teisendatakse kanooniliseks vormiks:
Seda saab alati teha järgmiselt: standardvormistuses kirjutatud probleemile
lisatakse täiendavaid bilansi muutujad, mille arv vastab ebavõrdsuse piirangute arvule m (tundmatute väärtuste mittenegatiivsuse piiranguid ei võeta arvesse). Pärast seda muutuvad ebavõrdsused märgiga “≤” võrdsusteks, näiteks vormi piirangute süsteem
2*x 1 +3*x 2 ≤20
3*x 1 +x 2 ≤15
4*x 1 ≤16
3*x 2 ≤12
x 1, x 2 ≥0
võtab vormi
2*x 1 +3*x 2 +x 3 =20
3*x 1 +x 2 +x 4 =15
4*x 1 +x 5 =16
3*x 2 +x 6 =12
x 1,x2,...,x6 ≥0
See tähendab, et bilansimuutujate "majanduslik" tähendus on väga lihtne - need on igat tüüpi kasutamata ressursside "jäägid".
Kui algülesandes ei otsitud miinimumi, vaid maksimumi, asendatakse sihtfunktsioon Z väärtusega Z 1 = -Z. Ülesannete lahendused langevad kokku, min Z = - max Z 1 . Näiteks eesmärk
Z(x 1, x 2) = 2*x 1 +5*x 2 (max)
ümber kirjutatud kui
Z 1 (x 1, x 2) = -2 * x 1 -5 * x 2 (min)
Kui algülesandes olid ebavõrdsusvõrrandid "≤" asemel märkidega "≥", korrutatakse iga sellise võrratuse mõlemad pooled -1-ga ja ebavõrdsuse märk pööratakse näiteks ümber.
3*x 1 +x 2 +x 4 ≥15
muutub
3*x1-x2-x4 ≤15
Mudeli kanooniline vorm saadakse ja selle jaoks kirjutame simpleks laud:
Põhimuutujad (BP) kirjutatakse vasakpoolsesse veergu, kui need pole veel valitud, on see tühi.
2. Jordani–Gaussi samme kasutades otsitakse esialgne võrdlusplaan, s.o. SLAE taandatakse põhivormile mittenegatiivsete vabade terminitega b i >0. Sel juhul tuleks sihtfunktsiooni Z väljendada ainult vabade tundmatute kaudu (Z-rea nullkoefitsiendid on ainult baasis olevate muutujate x i all). Lahutuselemendi a r,s valimisel kirjutame BP veeru r reale üles muutuja x s, kui seal oli juba muutuja, kriipsutame selle maha (eemaldame alusest);
3. Veergude x i alla kirjutame üles võrdlusplaani X *: vabade muutujate alla - nullid, põhimuutujate alla - põhimuutujale vastavad koefitsiendid veerust b.
Allpool kirjutame välja vektori R reegli järgi: põhimuutujate all on nullid, vabade all R i =Z i .
Kui kõik R i ≥0, leitakse optimaalne lahendus X * ja eesmärgi väärtus Z min = -q, vastasel juhul vajame uus plaan, kas teil on see, seltsimees Žjukov? (punkt 4).
4. Lahutava veeru s valimiseks vali vektori R maksimaalne absoluutne negatiivne komponent, valitud on lahutusveerg s. Seejärel analüüsime piirangute süsteemi maatriksi snda veeru koefitsiente. Kui kõik a i,s ≤0, ei ole lahendust ja Z min kipub miinuslõpmatusse, vastasel juhul jätkake sammuga 5.
5. Lahutava stringi r valimiseks koostame mittenegatiivsed seosed b i /A i,s ≥0, i=1,2,...,m ja valime nende hulgast väikseima. Kui mitme rea puhul on saavutatud miinimum, võib ükskõik millist neist võtta lahendavana ja uues võrdlusplaanis saavad mõne põhimuutuja väärtused võrdseks 0-ga, st saame degenereerunud võrdlusplaani.
6. Teostame Jordani-Gaussi teisenduse lahutuselemendiga a r,s ja jätkame sammuga 3
Geomeetriliselt vastab simpleksmeetod n-mõõtmelise kumera hulktahuka tippude lühimale läbimisele, mis moodustab ülesande teostatavate lahenduste piirkonna:
Siit liigume edasi võrdlusplaan C, mis on üks mitmemõõtmelise hulknurga tippudest, kuni optimaalne plaan E = X * .
Selle kõige programmeerimine Excelis pole lihtne, kuid võimalik. Lisatud dokument sisaldab 3 näidet, mis teostavad ülesannete lahendamist simpleksmeetodil. Tõsi, toimingu sooritamisel peate juba muutma 3 valemit esimese näite lehel simpleksmeetodi jaoks, need on kollasega esile tõstetud: lahtris I2 lahutusrea valimise seoste arvutamine, veeru BP täitmine; rakus A12, Jordani-Gaussi transformatsiooni etapp rakus B12. Nagu Jordani-Gaussi teisenduse näites, seostatakse valemite muutmist vaid vajadusega viidata uus rida, mis sisaldab lubava elemendiga lahtri aadressi (esimese sammu jaoks - lahter C9).
. Simpleksmeetodi algoritm
Näide 5.1. Lahendage järgmine probleem lineaarne programmeerimine simpleks meetod:
Lahendus:
I iteratsioon:
x3, x4, x5, x6 x1,x2. Väljendame põhimuutujaid vabadena:
Vähendame sihtfunktsiooni väärtuseks järgmine vaade:
Saadud ülesande põhjal moodustame esialgse simplekstabeli:
Tabel 5.3
Originaal simplekslaud
Hindavad suhted |
||||
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) ei tuvastata piirangusüsteemi mittevastavuse märki (märk 1) (st ei ole negatiivse vaba arvuga rida (v.a sihtfunktsiooni rida), milles seda poleks olema vähemalt üks negatiivne element (st vaba muutuja negatiivne koefitsient)).
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 ( tasuta number seda joont ei võeta selle tunnuse arvestamisel arvesse). 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“, seega 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 sel 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 vastupidine märk. 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 ümberkujundamiste tulemusena saime uue simpleks laud(Tabel 5.5).
II iteratsioon:
1. etapp: simplekstabeli koostamine.
Tabel 5.5
Simplex tabelII iteratsioonid
Hinnanguline suhe |
||||
| ||||
|
|
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. Lubamisstringi 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
Hinnanguline suhe |
||||
3/1=3 – min |
||||
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
Hinnanguline suhe |
||||
| ||||
|
|
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.
Leitud põhilahend vastavalt kriteeriumile 4 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. Lubamisstringi 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
Hinnanguline suhe |
||||
5/5=1 – min |
||||
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
Hinnanguline suhe |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
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 rida (tabel 5.9) ei sisalda null elementi(selle tunnuse arvestamisel selle rea vaba numbrit ei võeta arvesse).
Vastus: vaadeldava ülesande sihtfunktsiooni optimaalne väärtus =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 probleem on antud standardvorm. 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.
Loe ka:
|
Teoreem (lahutuselemendi valiku kohta)
Kui z-nda rea mitmes veerus on negatiivsed elemendid, tuleb lahutusveeruks valida maksimaalse korrutisega veerg absoluutväärtus koefitsient z-ndas reas ja minimaalne simplekssuhe see veerg.
Tõestus:
Olgu element lubav element. Modifitseeritud Jordani elimineerimisetapi tulemusena on z-rea vaba liige arv, mis on võrdne alates ja , on selle avaldise sulg alati positiivne. Ja kuna funktsionaali väärtus on alati võrdne vaba liikmega, kujutab see sulg funktsionaalsele lisandumist, mis saadakse astutud sammu tulemusena.
Mida suurema juurdekasvu funktsionaalsus igal etapil saab, seda vähem on optimaalse tulemuse saavutamiseks vaja samme (st arvutusi). Selle juurdekasvu suurus sõltub koefitsiendi absoluutväärtusest ja väikseima simplekssuhte väärtusest. See tähendab, et lahendav veerg on veerg, millel on selle toote maksimum.
Näide: lineaarne programmeerimine:
Leiame funktsiooni maksimumi
piirangute all
Lahendus: loome Jordani tabeli.
Kuna selle tasuta tingimused on positiivsed, on plaan toetav. Kuid see ei ole optimaalne, kuna z-rea koefitsiendid on negatiivsed. Valime nende hulgast suurima absoluutväärtusega korrutise ja väikseima simplekssuhtega. Kolmas veerg loetakse lahendatavaks, kuna sellel on suurim absoluutväärtus 8 ja simpleksseosed: vastavalt ( , seega lahendab kolmanda veeru element 1). Teeme modifitseeritud Jordani kõrvaldamise sammu ja jõuame järgmise tabelini.
Z-rea koefitsientide järgi otsustades ei ole saadud tabel saavutanud optimaalset lahendust. Lahendavaks võtame teise veeru negatiivse koefitsiendiga z-reas (ainult esimene saab olla lahutusrida). Kui element 5 on leitud, astume järgmise sammu.
Z-reas on kõik koefitsiendid positiivsed, ülemiste muutujate nulliga ja külgmuutujate võrdsustamine vabaliikmetega on optimaalne. Kirjutame tabelist välja peamiste tundmatute väärtused: Maksimaalne väärtus Funktsionaalsuse arvutame tabeli viimases lahtris:
Lõpptabelis on kõik determinandid mittenegatiivsed. See viitab sellele, et tundmatute väärtuste korral saavutab funktsionaalsus maksimumi
Tavaliselt eeldatakse, et ülesannete plaanide komplektis pole punkte, mille korral sihtfunktsiooni nimetaja on võrdne nulliga. Üldisust kaotamata võime eeldada, et .
Murdlineaarse programmeerimise ülesandes saavutatakse sihtfunktsiooni ekstreemum lahenduse hulktahuka tipus. See sarnasus lineaarse programmeerimisega võimaldab Stiefeli meetodi abil lahendada murdosalisi lineaarülesandeid.
Arvutused on esitatud Jordani tabelite kujul. Sel juhul eraldatakse funktsionaalsusele kaks alumist rida: esimesse neist kirjutame lugeja koefitsiendid ja teisele nimetaja. Algne ülesanne vastab tabelile 1:
| –x 1 | –x 2 | … | –x j | … | –x n | ||
| y 1 | a 11 | a 12 | … | a 1 j | … | a 1 n | a 1 |
| … | ……………………………………… | … | |||||
| y i | a i 1 | a i 2 | … | a ij | … | a sisse | a i |
| … | ……………………………………… | … | |||||
| a m | olen 1 | olen 2 | … | a mj | … | a mn | olen |
| z 1 | –lk 1 | –lk 2 | … | –p j | … | –p n | |
| z 2 | –q 1 | –q 2 | … | –q j | … | –qn |
Läbi y i piirangute süsteemi parema ja vasakpoolse osa erinevused on näidatud:
y i= a i–a i 1 x 1 – a i 2 x 2 –a i 3 x 3 – … – a in x n ³ 0.
Vabadeks muutujateks nimetame muutujaid, mis asuvad Jordani tabeli ülemisel tiitlireal. Määrates vabadele muutujatele nullväärtused, saame esialgse põhilahenduse: . See vektor ei saa olla võrdlusplaan, sest sellel oleva objektiivse funktsiooni nimetaja on võrdne nulliga ( z 2 = 0). Seetõttu piirangute süsteemi vabade liikmete hulgas a 1 ,…, olen peavad olema negatiivsed arvud (muidu oleks põhilahendus referentsplaan).
Modifitseeritud Jordani elimineerimise etappide abil, samamoodi nagu lineaarse programmeerimisülesande lahendamisel (vt.), leiame ülesande algse plaani. Tulemusena k sammud jõuame tabeli 2 juurde:
| –y 1 | … | –x j | … | –x n | ||
| x 1 | b 11 | … | b 1 j | … | b 1 n | b 1 |
| .… | ……………………………………… | |||||
| y i | b i 1 | … | b ij | … | b sisse | b i |
| …. | ……………………………………. | |||||
| a m | b m 1 | … | b mj | … | b mn | b m |
| z 1 | f 1 | … | f j | … | fn | F |
| z 2 | g 1 | … | g j | … | g n | G |
Tabelis 2 kõik vabad liikmed b i on mittenegatiivsed, mis tagab alusmuutujate mittenegatiivsuse x 1 ,…, a m. Lisaks (sihtfunktsiooni positiivse nimetaja tõttu z 2 võrdlusplaanide komplekti kohta). Esialgne võrdlusplaan on vektor koordinaatidega . Sihtfunktsiooni väärtus algsel võrdlusplaanil on .
Pange tähele, et kui ühel Jordaania eliminatsioonietapil on mõni tasuta tingimus b olen negatiivne ja kõik muud elemendid i rida ei ole negatiivsed, siis ei ole probleemil plaanide puudumise tõttu lahendust.
Vaatame, kuidas muutub eesmärgifunktsioon ülesande ühelt võrdlusplaanilt teisele liikumisel. Selgub, et funktsiooni uue ja vana väärtuse erinevuse märk langeb kokku determinandi märgiga. Kui. Sest Kuna lahenduspolühedron sisaldab vaid lõplikku arvu tugiplaane, siis lõpliku arvu sammudega jõuame optimaalse tugiplaanini.
Seda protsessi saab takistada vaid lahuste hulktahuka piiramatus. Sel juhul võib sihtfunktsioonil olla nn asümptootiline ekstreemum (antud juhul maksimum). Lineaarse murdosalise programmeerimise ülesande asümptootiline maksimum on plaanide kogumi eesmärkfunktsiooni täpne ülempiir, mida ei saavutata ühelgi plaanil. Kui probleemil on asümptootiline maksimum, on plaanide alal alati võimalik leida plaan (mitte võrdlusplaan), millel sihtfunktsioon võtab suvaliselt asümptootilise maksimumi lähedase väärtuse.
Stiefeli meetod võimaldab leida murdosa lineaarse programmeerimise ülesande mitte ainult maksimumi, vaid ka asümptootilist maksimumi. Vaatame lähemalt üleminekut plaanilt plaanile ja saame teada. Lahutava elemendi valimine sisse j veerus, peame juhinduma minimaalse simpleksseose põhimõttest. Need. elemendi sisselülitamine j-th veerg peab asuma reas, mille simpleksseos on positiivne ja minimaalne.
Sest pärast esialgse võrdlusplaani leidmist kõik parempoolsed küljed b i muutuda mittenegatiivseks, siis lahutuselemendiks j Kolmas veerg võib olla üks selle positiivsetest elementidest (). Kui optimaalse võrdlusplaani otsinguetapi igas etapis on valitud eraldusvõime veerus (vähemalt üks) positiivne element, siis on sellisel probleemil maksimum (võimalik, et rohkem kui üks).
Kui aga ühes etapis mõni hinnang on väiksem kui null, ja kõik elemendid j veerus. Siis ei saa selles veerus, juhindudes minimaalse simpleksseose põhimõttest, lahutuselementi valida. Vaba muutuja väärtuste suurendamine x j 0 kuni (vt tabel 2), jääme kogu aeg plaanide piirkonda. See on tingitud asjaolust, et muutuja suurenemine x j ei põhjusta ühegi põhimuutuja märgi muutumist miinusesse.
Tähistagem poolt M piir, milleni monotoonselt kasvades sihtfunktsioon kaldub: . See arv on asümptootiline maksimum.
| 2 |
Gaussi-Jordani meetod on mõeldud lineaarsete algebraliste võrrandite (SLAE) lahendamiseks. See on Gaussi meetodi modifikatsioon. Kui Gaussi meetod viiakse läbi kahes etapis (edasi ja tagasi), siis Gaussi-Jordani meetod võimaldab teil süsteemi lahendada ühes etapis. Gaussi-Jordani meetodi üksikasju ja otsest rakendamist kirjeldatakse näidetes.
Kõikides näidetes tähistab $A$ süsteemimaatriksit, $\widetilde(A)$ laiendatud süsteemimaatriksit. Saate lugeda SLAE salvestamise maatriksvormi kohta.
Näide nr 1
Lahenda SLAE $ \left\( \begin(joonatud) & 4x_1-7x_2+8x_3=-23;\\ & 2x_1-4x_2+5x_3=-13;\\ & -3x_1+11x_2+x_3=16. \end(joondatud) ) \right.$ Gaussi-Jordani meetodil.
Liigume viimaselt saadud maatriksilt süsteemi:
$$ \left\( \begin( joondatud) & 0\cdot x_1+1\cdot x_2+0\cdot x_3=1;\\ & 1\cdot x_1+0\cdot x_2+0\cdot x_3=-2; \\ & 0\cdot x_1+0\cdot x_2+1\cdot x_3=-1 \end (joondatud) \parem $$.
Saadud süsteemi lihtsustamisel on meil:
$$ \left\( \begin (joondatud) & x_2=1;\\ & x_1=-2;\\ & x_3=-1. \end(joondatud) \right. $$
Täielik lahendus ilma selgituseta näeb see välja selline:
Kuigi selline lahutuselementide valimise meetod on üsna vastuvõetav, on eelistatav valida lahutuselementideks süsteemimaatriksi diagonaalsed elemendid. Vaatleme seda meetodit allpool.
Lahutuselementide valik süsteemimaatriksi põhidiagonaalil.
Kuna see lahendusmeetod on eelmisega täielikult sarnane (v.a lubavate elementide valik), jätame üksikasjalikud selgitused vahele. Lubavate elementide valimise põhimõte on lihtne: esimeses veerus valime esimese rea elemendi, teises veerus võtame teise rea elemendi, kolmandas veerus kolmanda rea elemendi ja nii peal.
Esimene samm
Esimeses veerus vali esimese rea element, st. meil on lahutuselemendiks element 4. Saan aru, et eelistatavam tundub number 2, kuna see arv on ikkagi väiksem kui 4. Selleks, et number 2 esimeses veerus liiguks esimesele kohale, vahetame esimese. ja teised read:
$$ \left(\begin(massiivi) (ccc|c) 4 & -7 & 8 & -23\\ 2 & -4& 5 & -13 \\ -3 & 11 & 1 & 16 \end(massiivi) \ parem)\paremnool \left(\begin(massiivi) (ccc|c) 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end(massiiv ) \paremal) $$
Niisiis, lubavat elementi tähistab number 2. Jagage esimene rida samamoodi nagu varem 2-ga ja seejärel lähtestage esimese veeru elemendid nulliks:
$$ \left(\begin(massiivi) (ccc|c) 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end(massiivi) \ right) \begin(massiivi) (l) I:2 \\\phantom(0) \\ \phantom(0) \end(massiivi) \rightarrow \left(\begin(massiivi) (ccc|c) 1 & - 2& 5/2 & -13/2 \\4 & -7 & 8 & -23\\ -3 & 11 & 1 & 16 \end(massiivi) \right) \begin(massiivi) (l) \phantom(0 ) \\ II-4\cdot I\\ III+3\cdot I \end(massiivi) \rightarrow \left(\begin(massiivi) (ccc|c) 1 & -2& 5/2 & -13/2\ \0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end(massiivi) \right). $$
Teine samm
Teine samm nõuab teise veeru elementide nullimist. Lahutavaks elemendiks valime teise rea elemendi, st. 1. Lahutav element on juba võrdne ühega, seega me ei vaheta ühtegi rida. Muide, kui sooviksime ridu vahetada, siis me esimest rida ei puudutaks, kuna seda kasutati juba esimeses etapis. Kuid teist ja kolmandat rida saab hõlpsasti vahetada. Kuid kordan, selles olukorras pole vaja ridu vahetada, sest lahutuselement on juba optimaalne - see on võrdne ühega.
$$ \left(\begin(massiivi) (ccc|c) 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/ 2 \end(massiivi) \right) \begin(massiivi) (l) I+2\cdot II \\ \phantom(0)\\ III-5\cdot II \end(massiivi) \rightarrow \left(\begin (massiiv) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end(massiivi) \õige). $$
Teine etapp on lõpetatud. Liigume edasi kolmanda sammu juurde.
Kolmas samm
Kolmas samm nõuab kolmanda veeru elementide nullimist. Lahutava elemendina valime kolmanda rea elemendi, s.o. 37/2. Jagage kolmanda rea elemendid 37/2-ga (nii et lahutuselement oleks võrdne 1-ga) ja seejärel lähtestage kolmanda veeru vastavad elemendid nulliks:
$$ \left(\begin(massiivi) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37 /2 \end(massiivi) \right) \begin(massiivi) (l) \phantom(0)\\ \phantom(0)\\ III:\frac(37)(2) \end(massiivi) \paremnool \ left(\begin(massiivi) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 1 & -1 \end(massiivi) \right) \begin(massiivi) (l) I+2\cdot III\\II+3/2\cdot III\\ \phantom(0) \end(massiiv) \paremnool \left(\begin(massiivi) ( ccc|c) 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & -1 \end(massiivi) \right). $$
Saadud vastus: $x_1=-2$, $x_2=1$, $x_3=-1$. Täielik lahendus ilma selgitusteta näeb välja selline:
Kõik teised sellel lehel olevad näited lahendatakse täpselt teisel viisil: lahutavateks valime süsteemimaatriksi diagonaalsed elemendid.
Vastus: $x_1=-2$, $x_2=1$, $x_3=-1$.
Näide nr 2
Lahendage SLAE $ \left\( \begin(joonatud) & 3x_1+x_2+2x_3+5x_4=-6;\\ & 3x_1+x_2+2x_4=-10;\\ & 6x_1+4x_2+11x_3+11x_4=-27; \\ & -3x_1-2x_2-2x_3-10x_4=1 \end(joondatud) \right.$ Gaussi-Jordani meetodil.
Kirjutame selle süsteemi laiendatud maatriksi: $\widetilde(A)=\left(\begin(massiivi) (cccc|c) 3 & 1 & 2 & 5 & -6\\ 3 & 1& 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \end(massiivi) \right)$.
Lahutuselementideks valime süsteemimaatriksi diagonaalsed elemendid: esimeses etapis võtame esimese rea elemendi, teises etapis teise rea elemendi jne.
Esimene samm
Peame lähtestama esimese veeru vastavad elemendid. Lahustavaks elemendiks võtame esimese rea elemendi, st. 3. Vastavalt sellele tuleb esimene rida jagada 3-ga, nii et lahutuselement oleks võrdne ühega. Seejärel lähtestage kõik esimese veeru elemendid, välja arvatud lubav:
$$ \left(\begin(massiivi)(cccc|c) 3 & 1 & 2 & 5 & -6\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\ \ -3 & -2 & -2 & -10 & 1\end(massiivi)\right) \begin(massiivi) (l) I:3\\ \phantom(0)\\\phantom(0)\\\ phantom(0)\end(massiivi) \rightarrow \left(\begin(massiivi)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end(massiivi)\right) \begin(massiivi) (l) \phantom(0) \\ II-3\cdot I\\III-6\cdot I\\IV+3\cdot I\end(massiivi) \rightarrow\\ \rightarrow\left(\begin(massiivi)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & - 5 & -5\end(massiiv)\paremale). $$
Teine samm
Jätkame teise veeru vastavate elementide nullimisega. Leppisime kokku, et võtame lahendava elemendina teise rea elemendi, kuid me ei saa seda teha, kuna vajalik element on võrdne nulliga. Järeldus: vahetame read. Esimest rida ei saa puudutada, kuna seda kasutati juba esimeses etapis. Valik pole rikkalik: kas vahetame teise ja kolmanda rea või vahetame neljanda ja teise. Kuna neljas rida sisaldab (-1), siis las neljas rida osaleb "vahetuses". Niisiis, vahetage teine ja neljas rida:
$$ \left(\begin(massiivi)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end(massiivi)\right)\paremnool \left(\begin(massiivi)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4 \end(massiivi)\right) $$
Nüüd on kõik normaalne: eraldusvõime element on võrdne (-1). Juhtub, muide, joonte asukohtade muutmine on võimatu, kuid sellest räägime järgmises näites nr 3. Praegu jagame teise rea (-1-ga) ja lähtestame seejärel teise veeru elemendid. Pange tähele, et teises veerus on neljandas reas asuv element juba võrdne nulliga, nii et me ei puuduta neljandat rida.
$$ \left(\begin(massiiv)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end(massiivi)\right) \begin(massiivi) (l) \phantom(0)\\II:(-1) \\\phantom(0)\\\phantom(0)\end(massiivi) \rightarrow \left(\begin(massiivi)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 1 & 0 & 5 & 5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end(massiivi)\right) \begin(massiivi) (l) I-1/3\cdot II\\ \phantom(0) \\III-2\cdot II\\\phantom(0)\end(massiivi) \rightarrow\\ \rightarrow\left(\begin( massiiv)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end(massiivi)\right). $$
Kolmas samm
Alustame kolmanda veeru töötlemist. Leppisime kokku, et võtame lahendava elemendina süsteemi maatriksi diagonaalelemendid. Kolmanda sammu jaoks tähendab see kolmandal real asuva elemendi valimist. Kui aga võtta lahutuselemendiks lihtsalt element 7, siis tuleb kogu kolmas rida jagada 7-ga. Mulle tundub, et (-2)-ga jagamine on lihtsam. Seetõttu vahetame kolmanda ja neljanda rea ning seejärel saab lahutuselemendiks (-2):
$$ \left(\begin(massiivi)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end(massiivi)\right) \rightarrow \left(\begin(massiivi)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end(massiivi)\parem) $$
Eraldusvõime element - (-2). Jagage kolmas rida (-2)-ga ja lähtestage kolmanda veeru vastavad elemendid:
$$ \left(\begin(massiivi)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & - 3 & -4\\ 0 & 0 & 7 & -9 & -25\end(massiivi)\right) \begin(massiivi) (l) \phantom(0)\\ \phantom(0) \\III:( -2)\\\phantom(0)\end(massiiv)\paremnool \left(\begin(massiivi)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 7 & -9 & -25\end(massiivi)\right) \begin(massiivi) (l) I-2 /3\cdot III\\ \phantom(0) \\ \phantom(0)\\IV-7\cdot III\end(massiivi)\rightarrow\\ \rightarrow\left(\begin(massiivi)(cccc|c ) 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & - 39\end(massiiv)\paremale). $$
Neljas samm
Liigume edasi neljanda veeru nullimisele. Lahutav element asub neljandal real ja on võrdne arvuga $-\frac(39)(2)$.
$$ \left(\begin(massiivi)(cccc|c) 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & -39/2 & -39\end(massiivi)\right) \begin(massiivi) (l) \phantom(0)\\ \phantom(0) \\ \phantom(0) \\IV:\left(-\frac(39)(2)\right) \end(massiiv)\paremnool \left(\begin(massiivi)(cccc|c) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & 1 & 2\end(massiivi)\right) \begin(massiivi) (l ) I+IV\\ II-5\cdot IV \\ III-3/2\cdot IV \\ \phantom(0) \end(massiivi)\rightarrow\\ \rightarrow\left(\begin(massiivi)(cccc |c) 1 & 0 & 0 & 0 & -3\\ 0 & 1 & 0 & 0 & -5\\ 0 & 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 1 & 2\end (massiiv)\paremale). $$
Otsus on lõppenud. Vastus on: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$. Täislahendus ilma selgitusteta:
Vastus: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$.
Näide nr 3
Lahendage SLAE $\left\(\begin(joonatud) & x_1-2x_2+3x_3+4x_5=-5;\\ & 2x_1+x_2+5x_3+2x_4+9x_5=-3;\\ & 3x_1+4x_2+7x_3+4x_4 +14x_5=-1;\\ & 2x_1-4x_2+6x_3+11x_5=2;\\ & -2x_1+14x_2-8x_3+4x_4-7x_5=20;\\ & -4x_1-7x_2-9x_3-6x_5-21 9. \end(joondatud)\right.$ Gaussi-Jordani meetodil Kui süsteem on ebakindel, märkige põhilahendus.
Sarnaseid näiteid käsitletakse teemas “SLAE üld- ja põhilahendused”. Mainitud teema teises osas see näide lahendatakse Gaussi meetodil. Lahendame selle Gaussi-Jordani meetodil. Me ei hakka lahendust samm-sammult jaotama, kuna seda on juba varasemates näidetes tehtud.
$$ \left(\begin(massiivi)(ccccc|c) 1 & -2 & 3 & 0 & 4 & -5\\ 2 & 1 & 5 & 2 & 9 & -3\\ 3 & 4 & 7 & 4 & 14 & -1\\ 2 & -4 & 6 & 0 & 11 & 2\\ -2 & 14 & -8 & 4 & -7 & 20\\ -4 & -7 & -9 & -6 & -21 & -9 \end(massiivi)\right) \begin(massiivi) (l) \fantoom(0) \\ II-2\cdot I\\ III-3\cdot I\\ IV-2\cdot I \\ V+2\cdot I\\VI+4\cdot I \end(massiivi) \rightarrow \left(\begin(massiivi)(ccccc|c) 1 & -2 & 3 & 0 & 4 & -5\ \\ 0 & 5 & -1 & 2 & 1 & 7\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end(massiivi)\right) \begin(massiivi) (l) \phantom(0) \\ II:5 \\ \ phantom(0)\\ \phantom(0)\\ \phantom(0) \\ \phantom(0)\end(massiiv) \rightarrow \\ \left(\begin(massiiv)(ccccc|c) 1 & - 2 & 3 & 0 & 4 & -5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end(massiivi)\right) \ algus (massiiv) (l) I+2\cdot II \\ \phantom(0)\\ III-10\cdot II\\ IV:3\\ V-10\cdot II\\VI+15\cdot II \ lõpp (massiivi) \rightarrow \left(\begin(massiivi)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2 /5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & -1 & - 4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(massiivi)\right). $$
Usun, et üks tehtud teisendustest vajab veel selgitust: $IV:3$. Kõik neljanda rea elemendid jagavad täielikult kolmega, seega jagasime lihtsuse huvides kõik selle rea elemendid kolmeks. Teisendatud maatriksi kolmas rida muutus nulliks. Kustutame nullrea:
$$ \left(\begin(massiiv)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(massiivi)\right) $$
Meil on aeg liikuda edasi kolmanda sammu juurde, mille käigus tuleks kolmanda veeru elemendid lähtestada. Diagonaalelement (kolmas rida) on aga null. Ja joonte positsioonide muutmine ei tee midagi. Oleme esimest ja teist rida juba kasutanud, nii et me ei saa neid puudutada. Kuid neljandat ja viiendat rida pole mõtet puudutada, sest nulliga võrdse eraldusvõime elemendi probleem ei kao kuhugi.
Sellises olukorras saab probleemi lahendada äärmiselt lihtsal viisil. Kas me ei saa kolmanda veeruga hakkama? Olgu, liigume edasi numbri nelja juurde. Võib-olla ei võrdu neljandas veerus kolmanda rea element nulliga. Neljandat veergu kannatab aga sama probleem, mis kolmandat. Neljanda veeru kolmanda rea element on null. Ja joonte kohtade uuesti muutmine ei anna midagi. Kas me ei saa ka neljandat veergu töödelda? Olgu, liigume edasi numbri viie juurde. Kuid viiendas veerus ei ole kolmanda rea element isegi null. See on võrdne ühega, mis on päris hea. Seega on viienda veeru lahutuselement võrdne 1-ga. Lahutav element on valitud, seega viime läbi Gaussi-Jordani meetodi edasised teisendused:
$$ \left(\begin(massiiv)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(massiivi)\right) \begin(massiivi) (l) I-22/5\cdot III \\ II-1/5\cdot III \\ \phantom(0)\\ IV+III\\ V+ 2 \cdot III \end(massiivi) \rightarrow \left(\begin(massiivi)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1 / 5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end(massiivi)\right) \rightarrow \\ \rightarrow\left|\text(Eemalda null rida)\right|\rightarrow \left(\begin(massiivi)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end(massiivi)\ parem )$$
Oleme taandanud süsteemimaatriksi ja laiendatud süsteemimaatriksi astmelisele kujule. Mõlema maatriksi auastmed on võrdsed $r=3$, s.o. peate valima 3 põhimuutujat. Tundmatute arv on $n=5$, seega peame valima $n-r=2$ vabad muutujad. Kuna $r< n$, то согласно следствию из теоремы Кронекера-Капелли see süsteem on ebakindel (st sellel on lõpmatu arv lahendusi). Süsteemile lahenduste leidmiseks loome “sammud”:
“Sammudel” on elemendid veergudest nr 1, nr 2, nr 5. Järelikult on põhimuutujad $x_1$, $x_2$, $x_5$. Vabad muutujad on vastavalt $x_3$, $x_4$. Viime vabadele muutujatele vastavad veerud nr 3 ja nr 4 reast kaugemale, unustamata seejuures muidugi ka nende märke muuta.
$$ \left(\begin(massiiv)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end(massiivi)\right)\paremnool \left(\begin(massiivi)(ccc|ccc) 1 & 0 & 0 & -99/5 & -13/5 & -4/5\\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5\\ 0 & 0 & 1 & 4 & 0 & 0\end(massiivi)\parem) . $$
Viimasest maatriksist saame üldlahenduse: $\left\(\begin(joondatud) & x_1=-\frac(99)(5)-\frac(13)(5)x_3-\frac(4)(5 )x_4 \\ & x_2=\frac(3)(5)+\frac(1)(5)x_3-\frac(2)(5)x_4;\\ & x_3 \in R;\\ & x_4\; in R \\ & x_5=4 \end(joondatud)\right.$ Leiame vabad muutujad. võrdne nulliga, st. $x_3=0$, $x_4=0$:
$$ \left\(\begin(joondatud) & x_1=-\frac(99)(5);\\ & x_2=\frac(3)(5);\\ & x_3=0;\\ & x_4= 0;\\ & x_5=4 \end(joondatud)\paremale.
Probleem on lahendatud, jääb üle vaid vastus kirja panna.
Vastus: Ühine otsus: $\left\(\begin(joondatud) & x_1=-\frac(99)(5)-\frac(13)(5)x_3-\frac(4)(5)x_4;\\ & x_2=\ frac(3)(5)+\frac(1)(5)x_3-\frac(2)(5)x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4 .\end(joondatud)\right.$, põhilahendus: $\left\(\begin(joondatud) & x_1=-\frac(99)(5);\\ & x_2=\frac(3)(5) ;\\ & x_3=0;\\ & x_4=0;\\ & x_5=4 \end(joondatud)\right.$.
Kell graafiline meetod LP-ülesannete lahendamiseks valisime tegelikult võrratuste süsteemi lahendite hulga piirile kuuluvate tippude hulgast tipu, mille juures sihtfunktsiooni väärtus saavutas maksimumi (miinimum). Kahe muutuja puhul on see meetod täiesti intuitiivne ja võimaldab probleemile kiiresti lahenduse leida.
Kui ülesandes on kolm või enam muutujat, ja tegelikkuses majanduslikud ülesanded Just sellises olukorras on piirangute süsteemi lahendusala raske ette kujutada. Sellised probleemid lahendatakse kasutades simpleks meetod või järjestikuste parenduste meetodil. Meetodi idee on lihtne ja on järgmine.
Teatud reegli järgi leitakse esialgne võrdlusplaan (piirangala mingi tipp). See kontrollib, kas plaan on optimaalne. Kui jah, siis on probleem lahendatud. Kui ei, siis liigume edasi teise täiustatud plaani juurde – teise tippu. sihtfunktsiooni väärtus sellel tasapinnal (sellel tipul) on ilmselgelt parem kui eelmises. Üleminekualgoritm viiakse läbi teatud arvutusastme abil, mis on mugavalt kirjutatud tabelite kujul nn. simplex tabelid . Kuna tippe on lõplik arv, siis lõpliku arvu sammudega jõuame optimaalse lahenduseni.
Mõelgem simpleks meetod peal konkreetne näideülesanded plaani koostamise kohta.
Märgime veel kord, et lahendamiseks saab kasutada simpleksmeetodit kanoonilised probleemid LP-d on taandatud erikujule, st millel on alus, positiivsed paremad küljed ja sihtfunktsioon, mida väljendatakse mittepõhimuutujate kaudu. Kui probleemi ei vähendata erivormiks, siis vajate täiendavad sammud, millest räägime hiljem.
Vaatleme tootmisplaani probleemi, olles eelnevalt konstrueerinud mudeli ja viinud selle erikujule.
Ülesanne.
Toodete valmistamiseks A Ja IN Ladu suudab tarnida mitte rohkem kui 80 ühikut toorainet. Veelgi enam, toote valmistamiseks A tarbitakse kaks ühikut ja tooted IN- üks ühik toorainet. Tootmist on vaja planeerida nii, et toodete puhul oleks tagatud suurim kasum A on vaja toota mitte rohkem kui 50 tükki ja tooteid IN- mitte rohkem kui 40 tk. Pealegi ühe toote müügist saadav kasum A- 5 rubla ja alates IN- 3 hõõruda.
Ehitame matemaatiline mudel, mis tähistab X 1 kogus tooteid A plaanis, eest X 2 - toodete arv IN. siis näeb piirangute süsteem välja selline:
Toome probleemi kanoonilisele kujule, lisades täiendavad muutujad:
(3.10)
F = -5x 1 - 3x 2 → min.
Sellel ülesandel on eritüüp(alusega, parempoolsed küljed ei ole negatiivsed). Seda saab lahendada simpleksmeetodi abil.
Ietapp.Ülesande salvestamine simplekstabelisse. Ülesande (3.10) piirangute süsteemi ja simplekstabeli vahel on üks-ühele vastavus. Tabelis on nii palju ridu, kui palju on piirangute süsteemis võrdusi ja sama palju veerge, kui palju on vabu muutujaid. Põhimuutujad täidavad esimese veeru, vabad - ülemine rida tabelid. Alumine joon nimetatakse indeksiks, sinna kirjutatakse sihtfunktsiooni muutujate koefitsiendid. Parempoolsesse alumisse nurka kirjutatakse algselt 0, kui funktsioonis pole vaba liiget; kui on, siis kirjuta see vastupidise märgiga. Selles kohas (alumises paremas nurgas) on sihtfunktsiooni väärtus, mis peaks ühest tabelist teise liikudes absoluutväärtuses suurenema. Seega vastab tabel 3.4 meie piirangute süsteemile ja saame liikuda lahenduse II etapi juurde.
Tabel 3.4
|
põhilised |
tasuta |
||
IIetapp. Võrdlusplaani optimaalsuse kontrollimine.
See tabel 3.4 vastab järgmisele võrdlusplaanile:
(X 1 , X 2 , X 3 , X 4 , X 5) = (0, 0, 50, 40, 80).
Vabad muutujad X 1 , X 2 võrdub 0; X 1 = 0, X 2 = 0. Ja põhimuutujad X 3 , X 4 , X 5 võta väärtusi X 3 = 50, X 4 = 40, X 5 = 80 - vabade terminite veerust. Objektiivse funktsiooni väärtus:
-F = - 5X 1 - 3X 2 = -5 0 - 3 0 = 0.
Meie ülesanne on kontrollida, kas antud võrdlusplaan on optimaalne. Selleks peate vaatama indeksi rida - sihtfunktsiooni rida F.
Võimalikud on erinevad olukorrad.
1. Indeksis F- stringis pole negatiivseid elemente. See tähendab, et plaan on optimaalne ja probleemile saab lahenduse kirja panna. Objektiivne funktsioon saavutas oma eesmärgi optimaalne väärtus, võrdne alumises paremas nurgas oleva numbriga, mis on võetud vastupidise märgiga. Liigume edasi IV etapi juurde.
2. Indeksireal on vähemalt üks negatiivne element, mille veerus pole positiivseid elemente. Siis järeldame, et eesmärkfunktsioon F→∞ väheneb piiramatult.
3. Indeksireal on negatiivne element, mille veerus on vähemalt üks positiivne element. Seejärel liigume järgmise III etapi juurde. Arvutame tabeli ümber, parandades võrdlusplaani.
IIIetapp. Võrdlusplaani täiustamine.
Indeksi negatiivsetest elementidest F-ridad, valige suurima mooduliga, kutsuge vastav veerg lahendama ja märkige see "-ga".
Lahutava rea valimiseks on vaja arvutada vabade terminite veeru elementide suhted ainult To positiivne eraldusvõime veeru elemendid. Valige saadud seoste hulgast minimaalne. Vastavat elementi, mille juures miinimum saavutatakse, nimetatakse lahendamiseks. Tõstame selle esile ruuduga.
Meie näites 
, element 2 on lubatav. Sellele elemendile vastavat rida nimetatakse ka lahendamiseks (tabel 3.5).
Tabel 3.5
Olles valinud lubava elemendi, arvutame tabeli ümber vastavalt reeglitele:
1. Uues varasemaga sama suurusega tabelis vahetatakse lahutusrea ja veeru muutujad, mis vastab uuele alusele üleminekule. Meie näites: X 1 sisaldub selle asemel aluses X 5, mis lahkub baasist ja on nüüd tasuta (tabel 3.6).
Tabel 3.6
|
põhilised |
tasuta |
||
2. Lahutuselemendi 2 asemele kirjutada selle pöördarv.
3. Jagame eraldusjoone elemendid eraldusvõime elemendiga.
4. Jagame eraldusvõime veeru elemendid eraldusvõime elemendiga ja kirjutame need vastasmärgiga.
5. Tabeli 3.6 ülejäänud elementide täitmiseks arvutame ümber ristkülikureegli abil. Oletame, et tahame lugeda elemendi positsioonil 50.
Ühendame mõtteliselt selle elemendi lahendavaga, leiame korrutise, lahutame saadud ristküliku teisel diagonaalil asuvate elementide korrutise. Jagame erinevuse lahendava elemendiga.
Niisiis, . Kirjutame 10 kohta, kus oli 50. Samamoodi :
, 
, , 
.
Tabel 3.7
Meil on uus laud 3.7, põhimuutujad on nüüd muutujad (x 3,x 4,x 1). Sihtfunktsiooni väärtus võrdus -200-ga, s.t see vähenes. Selle põhilahenduse optimaalsuse kontrollimiseks peame uuesti minema II etapi juurde. Protsess on ilmselgelt piiratud, peatumiskriteeriumiks on II etapi punktid 1 ja 2.
Lõpetame ülesande lahenduse. Selleks kontrollime indeksi rida ja nähes selles negatiivset elementi, kutsume vastava veeru lahendama ja arvutame vastavalt III etapile tabeli ümber. Olles koostanud seosed ja valinud nende hulgast minimaalse = 40, määrasime lahutuselemendi 1. Nüüd teostame ümberarvutuse vastavalt reeglitele 2-5.
Tabel 3.8
|
põhilised |
tasuta |
||
|
x 3 = 30, X 2 = 40, X 1 = 20. Vabad muutujad on 0, X 5 = 0, X 4 = 0. Sihtfunktsioon võtab vabade terminite veeru viimase elemendi väärtuse vastupidise märgiga: - F = -220 F = 220, meie näites uuriti funktsiooni min juures ja algselt F max, nii et märk muutus tegelikult kaks korda. Niisiis, X* = (20, 40, 30, 0, 0), F* = 220. Vastus ülesandele: Tootmisplaani on vaja lisada 20 sellist tüüpi toodet A, 40 B-tüüpi toodet, samas kui kasum on maksimaalne ja võrdub 220 rublaga. Selle jaotise lõpus esitame simpleksmeetodi algoritmi vooskeemi, mis täpselt kordab samme, kuid võib-olla on mõne lugeja jaoks seda mugavam kasutada, kuna nooled näitavad tegevuste selget suunda. Vooskeemis kastide kohal olevad lingid näitavad, millisesse etappi või alampunkti vastav teisenduste rühm kuulub. esialgse võrdlusplaani leidmise reegel sõnastatakse punktis 3.7.
Küsimused enesekontrolliks 1. Kuidas konstrueeritakse simplekstabel? 2. Kuidas kajastub baasi muutus tabelis? 3. Sõnastage simpleksmeetodi peatamiskriteerium. 4. Kuidas korraldada tabeli ümberarvestust? 5. Millise reaga on mugav alustada tabeli ümberarvutamist? |
