PPP tabelivaade. Simplex - tabelid.

LIHTNE MEETOD ZLP LAHENDAMISEKS

3.1. üldised omadused ja simpleksmeetodi põhietapid

Simpleksmeetodi rajajad on nõukogude matemaatik L.V. Kantorovich ja Ameerika matemaatik J. Dantzig.

Simpleksmeetodi abil saate lahendada mis tahes probleemi või avastada selle lahendamatuse. Paljusid eriülesannete klasse saab lahendada teiste meetoditega, mis on nende klasside jaoks tõhusamad. Simpleksmeetodi eeliseks on aga selle mitmekülgsus. Peaaegu kõik arvutid on välja töötatud standardprogrammid lahenduste jaoks ZLP simplex- meetod.

Kirjeldame üldine idee simpleks meetod.

Usume, et ZLP on kirjutatud kanoonilises vormis ja eesmärgifunktsiooni tuleb minimeerida. Nagu me juba teame, tuleks optimaalset plaani otsida ZLP põhiplaanide hulgast. Simpleksmeetod ei läbi kõiki võrdlusplaane (mis oleks nende tohutu arvu tõttu sageli võimatu), vaid liigub alates mõnest esialgsest võrdlusplaanist järjest kahaneva arvuga teiste võrdlusplaanide juurde. objektiivne funktsioon. Simpleksmeetod lakkab töötamast, kui leitakse optimaalne võrdlusplaan või tuvastatakse probleemi lahendamatus.

Otsustades ZLP, kasutades simpleksmeetodit Eristada saab järgmisi etappe:

1) PAP-i toomine kanooniline vorm;

2) mittenegatiivsete parempoolsete külgedega lineaarsete võrrandite süsteemi toomine Jordani vormi, kontrollides samal ajal ZLP lahendamatust süsteemi ebakõla tõttu. lineaarsed piirangud;

3) optimaalsuse võrdlusplaani uurimine;

4) ZLP uurimine eesmärgifunktsiooni ODD altpoolt piiramatuse tõttu otsustamatuse osas;

5) üleminek uuele, “paremale” referentsplaanile.

Kirjete vähendamiseks ja korrastamiseks ülesande lahendamisel simpleksmeetodil kasutatakse nn simplekstabeleid. Simplekstabeli kasutamiseks tuleb ZLP taandada tabelikujuliseks. Seda tehakse nii.

Olgu ZLP kirjutatud kanoonilises vormis (2.3-2.5). ZLP taandamiseks tabelikujuliseks tuleks süsteem (2.4) esmalt taandada Jordani kujule, millel on mittenegatiivsed parempoolsed küljed. Oletame, et sellel Jordani kujul on vorm (2.6). Avaldame (2.6) põhimuutujad vabade kujul:

Asendades sihtfunktsiooni (2.3) põhimuutujate asemel nende avaldised vabade muutujate kaudu valemite (3.1) järgi, jätame seega põhimuutujad sihtfunktsioonist välja. Eesmärgifunktsioon on järgmisel kujul:

IN tabelivorm eesmärgifunktsioon on kirjutatud järgmiselt:

Kus .

Märge järgmisi funktsioone PPP tabelivorm:

a) lineaarvõrrandisüsteem taandatakse Jordani kujule, millel on mittenegatiivsed parempoolsed küljed;

b) põhimuutujad jäetakse sihtfunktsioonist välja ja see kirjutatakse kujul (3.3).

Liigume nüüd edasi simplekstabeli kirjelduse juurde. Olgu ZLP kirjutatud tabeli kujul:

(3.4)

Siis näeb valmis simplekstabel välja selline.

Lihtne meetod probleemide lahendamiseks lineaarne programmeerimine

Lihtne meetod on analüütiline meetod Algoritmi rakendavad ZLP lahendused graafiline meetod analüütiliselt, ilma joonist joonistamata.

Nii et point on selles simpleks meetod koosneb teostatavate lahenduste suunatud otsimisest, mille puhul on sihtfunktsiooni väärtus igal sammul parem kui eelmisel. Protsessi korratakse, kuni saadakse sihtfunktsiooni väärtuse poolest optimaalne lahendus.

Simpleksmeetodit saab kasutada mis tahes arvu tundmatute PLP-de lahendamiseks.

Simpleksmeetodi tehniline teostus on seotud lineaarvõrrandisüsteemide lahendamisega, mille jaoks kasutatakse Gaussi meetodit, on välja töötatud tabelivormid ja reeglid simplekstabelite teisendamiseks.

Looduslikul alusel lihtne meetod kehtib juhul, kui PIL on märgitud kanooniline vorm kirjed ja KZLP maatriks sisaldab suuruse ühiku alammaatriksit ma olen. Kindluse mõttes oletame, et esimene m Võrrandisüsteemi vektormaatriksid moodustavad identsusmaatriksi. Seejärel valitakse esialgne plaan järgmiselt:

Võrdlusplaani optimaalsust kontrollitakse optimaalsuse märgi abil, üleminek teisele plaanile toimub Jordani-Gaussi teisenduse abil, kasutades matemaatilist optimaalsusmärki. Saadud võrdlusplaani optimaalsust kontrollitakse uuesti jne.

Optimaalsuse matemaatiline kriteerium koosneb kahest järgmisest teoreemist:

1. Kui kõigi vektorite puhul A 1 , A 2 , … , A n tingimus on täidetud kus , siis on saadud võrdlusplaan optimaalne. Kokku määrata Z j osaleda m terminid, see tähendab, et selles ei osale kõik sihtfunktsiooni koefitsiendid c j, kuid ainult arvudega, mis vastavad praeguste baasvektorite arvudele A i, mille arv on võrdne m .

2. Kui mõne baasi mittekuuluva vektori puhul on tingimus täidetud , siis peaksite otsima uut võrdlusplaani, mille CF väärtus on suurem kui praegusel. Sel juhul on võimalikud kaks juhtumit:

a) kui kõik vektori komponendid A k alusesse sisestatavad , on mittepositiivsed, siis elukestva õppe programmil lahendus puudub (lõplik optimum puudub);

b) kui vektoril on vähemalt üks positiivne komponent A k, alusesse sisestada, siis saab uue võrdlusplaani.

Optimaalsuse kriteeriumi alusel viiakse baasi vektor A k, mis andis simpleksi erinevuse minimaalse negatiivse väärtuse:

Et võrdlusplaani väärtuste mittenegatiivsuse tingimus oleks täidetud, tuletatakse vektor baasist A r, mis annab minimaalse positiivse hinnangu suhte

Liin A r, milles asus vana baasvektor, nimetatakse juhendiks, veeruks A k ja element a rk- juhendid.

Uues simplekstabelis olevad juhtjoone elemendid arvutatakse valemite abil:

ja mis tahes muud elemendid i rida - vastavalt valemitele:

Uue võrdlusplaani väärtused arvutatakse sarnaste valemite abil:

,

Protsess jätkub kuni optimaalse plaani saavutamiseni või seni, kuni TF on piiramatu. Kui erinevuste hulgas Δj, j=1, 2, …, n optimaalsest plaanist on nulliks ainult baasvektoritele vastavad erinevused, see näitab optimaalse plaani unikaalsust. Kui nullhinnang vastab baasi mittekuuluvale vektorile, siis üldjuhul tähendab see, et optimaalne plaan ei ole unikaalne.

Näide. Lahendage ZLP mudeli abil:

leida ,

piirangute all

See ZLP taandatakse kanooniliseks vormiks, lisades täiendavaid muutujaid x 3 Ja x 4:

KZLP-l on vajalik arv (kaks) nulli veerge at x 3 Ja x 4, see tähendab, et sellel on ilmne algustäht võrdlusplaan (0,0,300,150).

Lahendus tehakse loomulikul alusel simpleksmeetodil, kusjuures arvutused on vormindatud simplekstabelites:

Simplex tabeli number	Alus	koos j-ga	koos j-ga					K
B	A 1	A 2	A 3	A 4
	←A 3
A 4
Δ	-		-2	-3			-
I	→A 2			1/3		1/3
←A 4			2/3		-1/3
Δ	-		-1				-
II	A 2					1/2	-1/2	-
→A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Vaatleme üksikasjalikumalt simplekstabelite täitmist ja vastavalt KZLP-le lahenduse saamist.

IN ülemine rida koefitsiendid sisalduvad üldtabelis c j , j = 1, 2, 3, 4 digitaalfunktsiooni muutujatega. Null-simplekstabeli kaks esimest rida sisaldavad veeruvektoreid B, A 1, A 2, A 3, A 4, mis vastab KZLP kirje vektorkujule. Kuna esialgne alus on vektorite paar A 3, A 4, sisalduvad need null-simplekstabeli veerus „Alus”. kus, A 3 on kaasatud esimesse ritta, mille määrab selle vektori esimene element, ja vektor A 4- teisele reale, selle vektori jaoks on ühik teisel real. Veerus nimega " c i” tuuakse sisse baasvektoritele vastavad sihtfunktsiooni koefitsiendid A 3, A 4, see on c 3, c 4. Mõlemad on võrdsed nulliga. Järgmisena arvutatakse vektorite erinevuste Δ väärtused B, A 1, A 2, A 3, A 4 ja sisestatakse nulltabeli kolmandale reale. Vektori jaoks A 1:

vektori jaoks:

Samamoodi,.

Vektori jaoks B erinevuse arvutamine on mõnevõrra lihtsustatud, kuna puudub vastav koefitsient c j , j = 1, 2, 3, 4 CF-is:

Mitte kõigi vektorite jaoks A 1, A 2, A 3, A 4 sellest tulenevad erinevused ei ole negatiivsed, seega pole meie valitud võrdlusplaan optimaalne. Peame otsima uue võrdlusplaani ja selleks peame asendama ühe baasis sisalduva vektori A 3, A 4.

Sisestatava vektori määramiseks otsime vektorit, mille erinevuse väärtus on minimaalne. See on vektor A 2, vastab sellele minimaalne väärtus erinevus: -3. See tähendab, indeks k valemist (8.4) on võrdne 2-ga. Vektori määramiseks, mille peame baasist tuletama, arvutame väärtused K iga rea ​​jaoks vastavalt valemile (8.5) ja sisestage need viimasesse veergu. IN sel juhul igal real vajame vektorelemendi väärtust B jagage vektorelemendi suurusega A 2. Esimesel real saame 300/3=100, teisel: 150/1=150. Esimese rea suhe oli väiksem, sellele vastas baasvektor A 3, seega indeks r valemis (8.5) on võrdne 1-ga, a rk=3 (tabelis raamiga esile tõstetud) ja tuletame vektori baasist A 3(tähistatud tabelis noolega).

Kuna vektori elementide hulgas A 2, mis tuleb baasi sisestada, on positiivseid, siis saab uue võrdlusplaani ja lahendusega tuleks jätkata.

Pärast seda täidetakse teine ​​simplekstabel. Vektorelementide ümberarvutamiseks B, A 1, A 2, A 3, A 4 kasutatakse valemeid (8.6)-(8.8). Need on veidi erinevad juhtjoone (meie puhul esimese) elementide määratlemisel ja teiste joonte elementide määratlemisel. Kirjutame üles mitme elemendi arvutused:

Teised esimese simplekstabeli elemendid arvutatakse samamoodi nagu nulltabeli puhul. Kuna kõik erinevused esimeses simplekstabelis pole mittenegatiivsed, on vaja arvutusi jätkata.

Nagu näeme, arvutuste tulemusena teises simplekstabelis baasvektoritega A 2, A 1 kõik erinevused osutusid mittenegatiivseteks, mis tähendab optimaalse plaani saavutamist (75; 75; 0; 0). Simplekserinevus vektori jaoks IN võrdne soovitud maksimaalne väärtus CF - 375.

Teoreem (simpleksalgoritmi lõplikkuse kohta).Kui on optimaalne PPP otsus, siis on olemas põhiline optimaalne lahendus. Viimast saab alati saada simpleksmeetodil ja alustada võib mis tahes algsest alusest.

Üks levinumaid ja populaarsemaid optimeerimisprobleeme logistikas on transpordi probleem . IN klassikaline välimus see hõlmab optimaalse ( need. seostatud minimaalsed kulud ) kaubaveo plaan.

Näiteks on meil jaekaupluste kett, mis nõuavad teatud koguse kaupa. Samuti on hulk tarnijate ladusid, kus hoitakse vajalikku kaupa. Pealegi on igas laos nende kaupade laoseisu erinev kogus. Lisaks on meil teada tariifid - igast laost igasse poodi 1 toote transpordikulud.

Vaja on välja töötada transpordiplaan, et kauplused saaksid vajaliku koguse kaupa madalaima transpordikuluga. Just sellistel puhkudel (ja paljudel teistelgi) tuleb transpordiprobleem lahendada.

Teoreetiline materjal transpordiprobleemist

(Monge-Kantorovitši probleem) - matemaatika ülesanne lineaarne programmeerimine eritüüp otsingu kohta optimaalne jaotus homogeensed objektid akust vastuvõtjateni, vähendades samal ajal reisikulusid.

Arusaadavuse hõlbustamiseks peetakse seda probleemiks optimaalse plaani osas kaupade transportimisel lähtepunktidest ( näiteks laod) tarbimiskohtadesse ( näiteks poed), minimaalsete transpordikuludega.

Sellel on järgmine vorm:

Kus: Z- kauba transpordikulud;
X- lastimaht;
C- kaubaühiku transpordi maksumus (tariif);
A- tarnija laos;
B- tarbija soov;
m- tarnijate arv;
n- tarbijate arv.

Transpordiprobleemi lahendamise üldplaan potentsiaalse meetodiga

Transpordiprobleemi saab lahendada erinevaid meetodeid, alustades simpleksmeetodist ja lihtsast loendusest ning lõpetades . Üks enim kasutatavaid ja enamikul juhtudel sobivaid meetodeid on transpordiplaani iteratiivne täiustamine.

Selle olemus on järgmine: leiame kindla võrdlusplaani ja kontrollime seda optimaalsus (Z → min). Kui plaan on optimaalne, on lahendus leitud. Kui ei, siis parandab see plaani nii mitu korda kui vaja, kuni optimaalne plaan leitakse.

Allpool on transpordiprobleemi lahendamise algoritm kõige üldisemal kujul:

1. Transpordilaua ehitamine.
2. Probleemi kontrollimine sulgemiseks.
3. Põhiplaani koostamine.
4. Tugiplaani kontrollimine degeneratsiooni suhtes.
5. Transpordiplaani potentsiaalide arvutamine.
6. Võrdlusplaani optimaalsuse kontrollimine.
7. Varude ümberjagamine.
8. Kui optimaalne lahendus on leitud, jätkake sammuga 9, kui ei, siis jätkake sammuga 5.
9. Kauba transpordi kogukulude arvutamine.
10. Transpordigraafiku koostamine.

Üksikasjalikud juhised transpordiprobleemi lahendamiseks

1. Transpordilaua ehitamine

Koostame tabeli, kuhu märgime tarnijate ladudes olevad materjalivarud ( Ai) ja tehaste vajadused ( Bj) nendes materjalides.

Tabeli lahtrite alumisse paremasse nurka sisestame kaubaveo tariifide väärtuse ( Cij).

2. Probleemi kontrollimine sulgemiseks

Tähistagem tähisega kõigi tarnijate veoste koguvaru A, ja sümboliseeritakse kõigi tarbijate kogunõudlust lasti järele B.

Transpordiprobleemi nimetatakse suletud, Kui A=B. Kui A ≠ B, siis nimetatakse transpordiprobleemi avatud. Millal suletud probleem Tarnijatelt eemaldatakse kõik kaubavarud ja kõik tarbijate soovid rahuldatakse. Millal avatud ülesanne Selle lahendamiseks peate tutvustama fiktiivseid tarnijaid või tarbijaid.

Kontrollime ülesande sulgemist:

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, seega on see transpordiprobleem suletud.

3. Referentsplaani koostamine

Koostab esialgse ( toetades) transpordiplaan. See ei pea olema optimaalne. See on lihtsalt omamoodi "mustand", "visand", mida täiustades jõuame järk-järgult optimaalse plaanini.

Neid on erinevaid meetodid võrdlusplaani leidmiseks. Kõige levinumad on järgmised:

a) Loodenurga meetod. Näita

Meetodi olemus on lihtne - transporditabeli lahtrid täidetakse järjestikku maksimaalse võimaliku liiklusmahuga suunal ülevalt alla Ja vasakult paremale. See tähendab, et esimesena täidetakse ülemine vasak lahter ( "loode" rakk), siis järgmine paremal jne. Seejärel minge aadressile uus rida ja täitke see uuesti vasakult paremale. Ja nii edasi, kuni laud on täielikult täidetud.

Meetodi üksikasjalik kirjeldus ja näide leiate.

b) Minimaalse elemendi meetod. Näita

Meetod seisneb selles, et transporditabeli lahtrite täitmiseks valige lahter, millega minimaalne tariifiväärtus. Seejärel valitakse järgmine madalaima tariifiga lahter ja nii edasi, kuni tabel on täidetud ( kõik varud ja vajadused nullitakse).

c) Vogeli lähendus. Näita

Meetodi aluseks on leidmine erinevusi(moodul) paari vahel minimaalsed tariifid igas reas ja veerus. Seejärel reas või veerus koos suurim erinevus täidab lahtri kõige väiksem tariif. Seejärel korratakse kõiki neid toiminguid uuesti, ainult sel juhul ei võeta täidetud lahtreid enam arvesse.
Vogeli lähenduse üksikasjalik kirjeldus ja näide leiate

d) Topelteelistuse meetod. Näita

Meetodi olemus seisneb selles, et madalaima tariifiga rakud märgitakse ridadesse ja seejärel veergudesse. Seejärel täidetakse lahtrid järgmises järjekorras: kõigepealt lahtrid koos kaks marka, siis ühega, lõpuks ilma märkideta.
Meetodi üksikasjalik kirjeldus ja näide leiate

4. Tugiplaani kontrollimine degeneratsiooni suhtes

Kutsutakse välja tabeli lahtrid, milles on registreeritud nullist erinevad transpordid põhilised, ja ülejäänud (tühjad) - tasuta.

Plaani nimetatakse degenereerunud, kui põhirakkude arv selles on väiksem kui m + n -1. Kui ülesande lahendamise käigus saadakse degenereerunud plaan, siis tuleb seda täiendada, sisestades puuduvasse arvu lahtritesse nulltransport ja muutes need lahtriteks põhilisteks ( plaani üldine bilanss ja transpordi kogumaksumus ei muutu). Plaani on aga võimatu täiendada, valides lahtreid juhuslikult. Plaan peab olema atsükliline!

Plaani nimetatakse atsükliliseks, kui selle alusrakud ei sisalda tsükleid. Tsükkel transporditabelis on mitu lahtrit, mis on ühendatud suletud polüliiniga nii, et polüliini kaks kõrvuti asetsevat tippu asuvad kas samas reas või samas veerus. Allpool on silmuse näide:

Katkendjoonel võivad olla iselõikumispunktid, kuid mitte tsükli rakkudes.

Põhilahtrite arv = 5

m + n - 1 = 3 + 3 - 1 = 5

Järelikult ei ole esialgne transpordiplaan degenereerunud.

5. Transpordiplaani potentsiaalide arvutamine

Saadud plaanide ja nende hilisema täiustamise analüüsimiseks on mugav siseneda lisaomadused lähte- ja sihtpunktid, mida nimetatakse potentsiaalideks.

Seda transpordiplaanide täiustamise meetodit nimetatakse potentsiaalne meetod . Transpordiplaani iteratiivseks täiustamiseks on ka teisi meetodeid, kuid me neid siin ei käsitle.

Seega võrdleme iga tarnijat Ai ja iga tarbija Bj väärtustega Ui Ja Vj vastavalt, nii et plaani kõigi põhilahtrite puhul on täidetud järgmine seos:

Ui + Vj = Cij

Lisa transporditabelisse lisarida ning veerg Ui ja Vj jaoks.

Oletame, et U1 = 0.

Siis leiame V3 = C13 – U1 = 1 – 0 = 1.

Teades V3, leiame nüüd U3:

Analoogia põhjal arvutame kõik ülejäänud potentsiaalid:

6. Plaani optimaalsuse kontrollimine potentsiaalimeetodi abil

Plaani iga vaba lahtri jaoks arvutame erinevused

ΔCij = Cij – (Ui + Vj)

ja kirjutage saadud väärtused vastavate lahtrite vasakpoolsesse alumisse nurka.

Plaan on optimaalne, kui kõik erinevused ΔCij ≥ 0.

Sel juhul on plaan suboptimaalne(ΔC22< 0), и его следует улучшить путем перераспределения поставок.

7. Varude ümberjagamine

Leiame suurima lahtri absoluutväärtus negatiivne erinevus ΔCij ja konstrueerida tsükkel, milles peale selle lahtri on kõik teised aluselised. Selline tsükkel on alati olemas ja ainulaadne.

Märgime negatiivse erinevusega lahtri ΔCij “+” märgiga, järgmise “-” märgiga ja nii edasi ükshaaval.

Seejärel leiame tsükli lahtrites koormuse minimaalse väärtuse märgiga “-” (siin on see 5) ja sisestame selle vabasse lahtrisse märgiga “+”. Seejärel läbime järjestikku kõik tsükli lahtrid, vaheldumisi lahutades ja lisades neile minimaalse väärtuse (vastavalt märkidele, millega need lahtrid on tähistatud: kus miinus lahutatakse, kus pluss lisatakse).

Saame uus võrdlusplaan transport:

Kuna põhilahtreid on rohkem kui m + n – 1, siis põhirakk koos nullväärtus tehke see tasuta:

Arvutame uuesti potentsiaalsed väärtused ja erinevuse ΔCij:

Seekord on kõik rakkude erinevused ΔCij positiivsed, seega leitud optimaalne lahendus.

8. Kui optimaalne lahendus on leitud, jätkake sammuga 9, kui ei, siis jätkake sammuga 5.

Oleme leidnud optimaalse lahenduse, seega liikuge edasi punkti 9 juurde.

9. Kauba transpordi kogukulude arvutamine

Arvutame saatmiskulud kokku lasti ( Z), mis vastab meie leitud optimaalsele plaanile vastavalt valemile:

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 den. ühikut

Kõikide toodete saatmiskulud kokku optimaalne lahendus, meik 110 den. ühikut

10. Transpordigraafiku koostamine

Olles leidnud optimaalse transpordiplaani, hakkame ehitama. Graafiku tipud on "laod" ja "poed". Tipudes märgime vastavad reservide mahud ja vajadused. Graafi tippe ühendavad kaared vastavad nullist erinevale transpordile. Igale sellisele kaarele kirjutame allkirja, näidates ära veetava kauba mahu.

Tulemuseks on allolevale sarnane graafik:

See on kõik, transpordiprobleem on lahendatud. Palju õnne!

Transpordiprobleemi praktiline rakendamine

Transpordiprobleemi kasutatakse paljudel juhtudel. See on tooraine ja tarnete optimeerimine tootmisettevõtted. See on kaupade tarnimise optimeerimine ladudest jaekauplustesse. See on reisijateveo optimeerimine ja palju-palju muud.

Galyautdinov R.R.

© Materjali kopeerimine on lubatud ainult siis, kui sellel on otsene hüperlink

Võrdlusplaani optimaalsuse märk

Kui kindlat tugiplaani sisaldavas simplekstabelis on kõik f-rea elemendid (v.a vaba liige) mittenegatiivsed, siis on see tugiplaan optimaalne.. Laske tabeli f-rida sisse. 2.b 0j > (i=1, ..., n m). Selles tabelis sisalduvas võrdlusplaanis x 0 on kõigi vabade muutujate x m+j väärtused võrdsed nulliga ja f(x 0) =b 00. Kui suurendada mõnd vaba muutujat x m+ j, siis, nagu on näha võrrandist (2.5), hakkab b 0j mittenegatiivsuse tõttu f(x) väärtus vähenema. Järelikult saavutab funktsioon f(x) punktis x o oma suurima väärtuse, mis tähendab, et x 0 on tõepoolest optimaalne võrdlusplaan.

Võimalus liikuda ühelt võrdlusplaanilt teisele

Nagu eelpool mainitud, seisneb simpleksmeetodi olemuses järgmise kriteeriumi tõestamise protsess: kui mingit võrdlusplaani sisaldava simplekstabeli f-real on vähemalt üks negatiivne element (vaba liiget arvestamata), mis vastab veerule, millel on vähemalt üks positiivne element, siis saab aluse teisendamisega liikuda teisele võrdlusplaanile, mille sihtfunktsiooni väärtus on suurem.

Tõestame seda märki. Kehtestame reeglid muutujate valimiseks selliseks algaluse B o teisenduseks võrdlusplaaniga x 0 in uus alus B 1 võrdlusplaaniga x 1, milles; funktsiooni f väärtus suureneb, st f(x i)>f(x 0). Seejärel teisendame vastavalt simplekstabelist elementide ümberarvutamise reeglile need uuele alusele, mis võimaldab leida uue võrdlusplaani komponendid.

Oletame, et tabelis. 2.1, näiteks b 0s<0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) millised muutujatest tuleks eelmisest baasist eemaldada, et muutujale x m+s ruumi teha;

2) millise väärtuse peaks uues võrdlusplaanis saama uus põhimuutuja x m+s.

Esitatud küsimuste lahendamiseks oletame, et võrratustes (2.4) on kõik x m+j, välja arvatud x m+s, võrdsed nulliga. Siis

x i = b io -b on x m+s (i=l, ..., m)

Nendest võrdustest on selge, et x m+s suurenemisega on nende põhimuutujate x i väärtused, mille koefitsiendid b on<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. Kui x m+s suureneb, hakkavad nende muutujate väärtused kahanema ja saabub hetk, mille järel nad omandavad negatiivsed väärtused ja tingimus (2.3) ei ole enam täidetud. Seda ei saa lubada. Seetõttu uurime välja, millise piirväärtuseni x m+s saab suurendada põhimuutujate mittenegatiivsuse tingimust rikkumata. Selleks kirjutame süsteemist (2.6) välja need võrrandid, milles b on >0. Oletame, et see puudutab võrdusi arvudega i=d,…,k,…,p:

x d = b do -- b ds x m+s ,

…………………..

x k = b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

Põhimuutujad x d, ..., x k, ..., x p jäävad mittenegatiivseteks seni, kuni x m+s rahuldab võrratuste süsteemi

b do - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 või x m+s< b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s< b po /b ps

st x m+s juures

Olgu väikseim murdudest b io /b vastab i = k, s.o.

min ( b io /b on )= b k0 /b ks .

Siis võime öelda, et seni kuni x m+s ei ületa väärtust b k0 /b ks , st x m+s 0, siis muutub muutuja x k võrdseks täpiga: x k = b k0 -- b ks b ko /b ks =0 ja seeläbi teisendatakse alus B o = (x 1 ; ...; x k ; . ..; x m ) uude baasi, milles muutuja x m+s läheb vabast rühmast põhilistesse ja muutuja x k asendab x m+s vabas rühmas. Samal ajal on kõik muud vabad muutujad endiselt võrdsed nulliga ja ülejäänud põhimuutujad on endiselt positiivsed. Järelikult on põhiplaanil x 1 uues baasis B 1 = (x 1 ; ...; x m+s ; ...; x m ) m positiivset komponenti ja m-n nulli. Kavas x 1 võivad mõned põhimuutujad omandada nullväärtused kahel juhul:

1) kui plaanis x 0 on nulliga võrdsed põhimuutujad;

2) kui väikseim murdudest b io /b on vastab kahele või enamale arvule i. Meie puhul vastab see ainult i = k.

Alusesse kaasatav muutuja määratakse f-stringi negatiivse elemendiga. Võrdusest f =b oo - b os x m+s on selge, et kui b 0s<0 и фиксированном x m+s >0, sõltub f(x) väärtus koefitsiendi b 0s absoluutväärtusest: mida suurem |b 0s |, seda suurema väärtuse f(x) uues baasis saab. Aga sellest võrdsusest selgub ka, et uue baasmuutuja poolt võetud väärtusest sõltub ka sihtfunktsiooni väärtus uues baasis x m+s. Valime baasi sisestatud muutuja, keskendudes ainult f-rea negatiivsetele elementidele. Seega, kui f-real on mitu negatiivset elementi, siis sisestame baasi suurima absoluutväärtusega negatiivsele elemendile vastava muutuja x m+j. Aluses sisalduva muutuja koefitsientide veergu nimetatakse lahendamiseks. Seega, valides f-rea negatiivse elemendi alusel baasi sisestatud muutuja (või valides lahendava veeru), tagame funktsiooni f suurenemise.

Baasist välja jäetava muutuja määramine on veidi keerulisem. Selleks koostavad nad vabade liikmete suhted lahendava veeru positiivsete elementide vahel (sellisi seoseid nimetatakse simpleksiks) ja leiavad nende hulgast väikseima, mis määrab välistatud muutujat sisaldava rea ​​(lahutav). Alusest välja jäetud muutuja valik (või lahutusrea valik) minimaalse simpleksseotuse järgi tagab baaskomponentide positiivsuse uues võrdlusplaanis.

Seega oleme tõestanud, et märgis määratud tingimustel on tõepoolest võimalik suure sihtfunktsiooni f(x) väärtusega ühelt võrdlusplaanilt teisele liikuda.

Pange tähele, et uue baasmuutuja x m+s väärtust teame juba uues võrdlusplaanis: see on võrdne b ko /b ks . Mis puudutab uue võrdlusplaani ülejäänud põhimuutujate arvväärtusi ja vastavat f(x) väärtust, siis need on leitavad alles pärast muudetud põhimuutujate süsteemi x 1 ;..., x m+s ; ...,x m väljendatakse vabade muutujate x m+1,…,x k,…, x n muudetud süsteemi kaudu. Selleks seadistame; reeglid, mille järgi probleemi tingimused muudetakse ühelt aluselt teisele.

Selles võrrandis olevat koefitsienti b ks = 0 x m+s nimetatakse lahutuselemendiks. Võrdsuses (2.7) väljendub uus põhimuutuja x m+s vabade muutujatena, mille hulgas nüüd asub endine põhimuutuja x k. Seega vahetusid muutujad x m+s ja x k rollid.

Samamoodi väljendame ülejäänud põhimuutujaid uue vabade muutujate komplekti kaudu. Selleks asendame ülejäänud võrdsustest väärtuse x m+s (tähistame f väärtusega x 0, siis võetakse võrdsus süsteemi i = 0 juures)

Süsteemi viimist uuele alusele nimetatakse simpleksteisenduseks. Kui vaadelda simpleksteisendust kui formaalset algebralist tehtet, siis võib märgata, et selle toimingu tulemusena jaotuvad rollid ümber kahe muutuja vahel, mis kuuluvad teatud lineaarsete funktsioonide süsteemi: üks muutuja muutub sõltuvast sõltumatuks ja teine. , vastupidi, sõltumatust ülalpeetavaks . Seda operatsiooni tuntakse algebras kui Jordani eliminatsioonietappi.

123 lehekülge (Word-fail)

Vaata kõiki lehti

Fragment teose tekstist

Üleminek ühelt võrdlusplaanilt teisele, mille sihtfunktsiooni väärtus on suurem kui eelmises.

3. Saadud plaani optimaalsuse kontrollimine, mis võimaldab viivitamatult peatada võrdlusplaanide otsimise või teha järelduse, et optimaalset plaani ei ole.

Simpleksmeetod põhineb järgmistel teoreemidel, mis on antud ilma tõestuseta.

Teoreem 1.2 (toetusplaani olemasolu kohta)

Kui lineaarvorm on ülalt piiratud mittetühja hulgaga D, siis on LLP lahendatav, see tähendab, et on olemas selline punkt, .

Teoreem 1.3 (tugiplaani optimaalsuse test)

Põhiplaan ülesanne (1.18) on optimaalne, kui kõigi j puhul , on rahul, kus kogus

(1.21)

helistas simplex – erinevus või hindamine.

Teoreem 1.4 (optimaalse plaani puudumise test)

Kui mõne k puhul ja arvude hulgas pole positiivseid, s.t. Kõik, probleemi objektiivne funktsioon ei piirdu teostatavate lahenduste kogumiga ega oma lõplikku lahendust.

Teoreem 1.5 (testige parema tugiplaani olemasolu)

Kui võrdlusplaan ülesanne (1.18) ei ole mõne k puhul degenereerunud, kuid arvude hulgas on vähemalt üks positiivne, s.t. mitte kõike, siis on olemas referentsplaan , milles sihtfunktsioon ei saa vähem väärtust kui eelmises plaanis: .

Simpleksmeetodi algoritm

1. Probleem tuleb taandada kanoonilisele vormile. Piirangute süsteem taandatakse ühikupõhisele, s.o. lahendatakse mõne põhimuutuja suhtes (üldsust kaotamata eeldame, et esimese m muutuja puhul) Jordani-Gaussi meetodil (süsteem (1.19)). Saadakse vastav esialgne võrdluslahus.

2. Arvutuste hõlbustamiseks kirjutame kõik simplekstabelisse (tabel 1.1). Veerg Basis sisaldab baasmuutujate loendit; järgmine veerg “c j base” sisaldab sihtfunktsiooni koefitsiente baasmuutujate jaoks; järgmistes veergudes on vastavate muutujate piirangute süsteemi koefitsiendid; veerg “b i” on piirangute süsteemi vabaliikmete veerg. Viimasel real on lihteks – valemi (1.21) abil arvutatud erinevused ja viimane lahter sisaldab sihtfunktsiooni = väärtust. Pange tähele, et simpleks – põhimuutujate erinevused – on alati võrdne nulliga.

Tabel 1.1

		c j alusel

3. Kui kõik on simpleks, on erinevused mittenegatiivsed, st. , siis on võrdlusplaan optimaalne.

4. Kui vähemalt üks simpleks - erinevus on negatiivne, , ja vastavas veerus pole positiivseid elemente, siis ei ole ülesandel optimaalset lahendust, s.t. .

5. Kui vähemalt üks simpleks-erinevus on negatiivne, ja igas negatiivse hindega veerus on vähemalt üks positiivne element, siis saab saadud võrdlusplaani parandada.

6. Valige luba veerg"p", mis vastab väikseimale negatiivsele skoorile.

7. Valige loa string“k”, mis vastab eraldusvõime veeru paremate külgede ja vastavate positiivsete elementide väikseimale suhtele. Nimetatakse elementi, mis asub eraldusvõime veeru ja resolutsioonirea ristumiskohas lubav element.

8. Liigume edasi uue simplekstabeli juurde, milles tuleb uus alus: vanas aluse “k” kohas olev põhimuutuja muudetakse uueks muutujaks. Uue baasmuutuja vastav vektor tuleb muuta ühikuliseks. Selleks jagage eraldusvõime rida nii, et eraldusvõime elemendi asemele ilmuks ühik. Korrutades lahutusjoone sobivate arvudega ja liites selle ülejäänud ridadega, saame eraldusvõime veerus nullid. Pärast seda kirjutame välja uue võrdlusplaani ja arvutame hinnangute rea ümber. Liigume edasi punkti 3 juurde.

Märkus alternatiivse plaani kohta.

Kui kõik vabade muutujate hinnangud viimases simplekstabelis osutuvad nullist rangelt suuremaks, siis on optimaalne plaan ainulaadne. Kui vähemalt üks vaba muutuja hinnang on võrdne nulliga, siis on olemas alternatiivne optimum (optimaalsete plaanide kogum). Alternatiivse lahenduse leidmiseks on vaja teha üks samm simpleksmeetodist, valides lahutusveeruks vaba muutuja, mis vastab nullpunktile.

Sel juhul saab kõigi optimaalsete plaanide komplekti kujutada toetavate optimaalsete plaanide kumera lineaarse kombinatsioonina: , Kus .

Näide 5. Lahendage ZLP, kasutades simpleksmeetodit:

(1.22)

Lineaarsete võrratuste süsteemi (1.22) taandame kanooniliseks vormiks, lisades igasse võrratusse täiendava mittenegatiivse muutuja. Saame lineaarvõrrandisüsteemi:

(1.23)

Sihtfunktsioonil on vorm

Koostame simplekstabeli:

Tabel 1.2

		c j alusel

Põhiplaan ei ole optimaalne, sest reitingute real on negatiivsed elemendid = - 3 ja = - 2. Valime lahendava veeru - esimese, kuna see vastab negatiivsete hinnangute miinimumile = - 3. Esimese veeru kõigi positiivsete elementide jaoks arvutame suhte . Leiame nende suhete miinimumi: . See vastab teisele reale, seega on see lubatav. Seega näitab lahutuselement, et muutuja x 4 on tuletatud baasist ja selle asemel on aluses muutuja x 1. Täidame uue simplekstabeli (tabel 1.3). Selleks muudame esimese veeru üheks veeruks. Korrutame teise rea (-1/2) ja liidame esimesega, kirjutame tulemuse uue simplekstabeli esimesele reale; samamoodi korrutage teine ​​rida (1/2) ja lisage see kolmandale; jaga eraldusvõime joon 2-ga; Neljanda kirjutame ümber ilma muudatusteta.