Laten we eens overwegen universele methode oplossingen voor het canonieke probleem lineaire programmering
Met N variabelen en M gelijkheidsbeperkingen, bekend als de simplexmethode.
De reeks plannen voor een canoniek probleem is een convexe veelvlakkige reeks met een eindig aantal hoekpunten. En als dit probleem een optimale oplossing heeft, dan wordt deze op zijn minst op één hoekpunt bereikt.
Elk hoekpunt wordt geassocieerd met een basisplan van het probleem, waarin de variabelen gelijk zijn aan nul, en de overige variabelen overeenkomen met lineair onafhankelijke kolommen van de conditiematrix. Deze lineair onafhankelijke kolommen vormen een niet-singuliere basismatrix.
Het herhalen van alle hoekpunten is rekentechnisch duur en daarom ineffectief. In 1947 stelde J. Dantzig een ordelijke procedure voor voor het opsommen van hoekpunten, waarbij het voldoende is om slechts een klein deel ervan te onderzoeken om de optimale oplossing te vinden. Deze procedure heet simplex methode.
J. Danzig stelde voor om slechts één vector in de basismatrix te vervangen bij het verplaatsen van het ene uiterste punt naar het andere. Dit betekent dat we tijdens een dergelijke transitie een van de basisvariabelen moeten uitsluiten: maak deze niet-basaal ( gelijk aan nul), en in plaats daarvan een nieuwe variabele introduceren uit de niet-basisvariabelen (nul) - maak deze basaal (positief).
Het blijkt dat geometrisch een dergelijke vervanging leidt tot een overgang van het ene hoekpunt naar een aangrenzend (naburig) hoekpunt dat verband houdt met vorig punt gemeenschappelijke rand.
Van alle aangrenzende punten wordt het punt geselecteerd waarop de objectieffunctie het meest toeneemt. Omdat het aantal hoekpunten eindig is, wordt via een eindig aantal overgangen het hoekpunt bereikt hoogste waarde de objectieve functie, of de grenzeloosheid van de objectieve functie zal worden vastgesteld op basis van een onbeperkte reeks plannen.
Het algemene schema van de simplexmethode bestaat uit de volgende hoofdstappen.
· stap 0. Bepaling van de initiële basis en het bijbehorende initiële hoekpunt (baseline).
· stap 1. Het controleren van de huidige basislijn op optimaliteit . Als aan het optimaliteitscriterium is voldaan, Dat het plan is optimaal en de oplossing compleet. Anders ga naar stap 2.
· stap 2. Het vinden van de variabele die in de basisvariabelen is geïntroduceerd. (Vanuit de voorwaarde van het vergroten van de objectieve functie).
· stap 3. Een variabele vinden die is uitgesloten van de basisvariabelen (van de voorwaarde dat de beperkingen van het probleem behouden blijven).
· stap 4 . Het vinden van de coördinaten van de nieuwe basislijn (aangrenzend hoekpunt). Ga naar stap 1.
Herhaalde stappen 1-4 vormen één iteratie van de simplexmethode.
Uit dit diagram volgt dat je, om de simplexmethode te starten, ten eerste een soort hoekpunt nodig hebt - een eerste basisplan, en ten tweede dat je het huidige hoekpunt op optimaliteit moet kunnen onderzoeken zonder alle aangrenzende hoeken te berekenen. hoekpunten. Deze problemen kunnen gemakkelijk worden opgelost als het canonieke LP-probleem een speciale vorm heeft.
Definitie. We zullen zeggen dat het canonieke LP-probleem een “voorkeursvorm” heeft als
1. rechterzijden van de vergelijkingen, .
2. de conditiematrix bevat een eenheidssubmatrix van grootte
Met andere woorden: in elke vergelijking is er een variabele met een coëfficiënt gelijk aan één, die in de andere vergelijkingen ontbreekt. De eerste voorwaarde is niet lastig, omdat het in het geval van een negatieve rechterkant van een vergelijking voldoende is om deze met (-1) te vermenigvuldigen. Bij een probleem van het voorkeurstype is het vinden van de initiële basislijn heel eenvoudig.
Voorbeeld 2.1.
Conditiematrix A en de vector van de rechterkant van de beperkingen B eruit zien
en doelvector c = (1, -3, 0, 4, 2).
Eén basismatrix is meteen duidelijk: met eenheidsvectoren van voorwaarden.
Daarom kiezen als basisvariabelen X 1 , X 3 ,X 5 , en het invoeren van het systeem van vergelijkingen X 2 = x 4 = 0 (niet-basisvariabelen) , wij vinden het meteen X 1 = 10,X 3 = 20,X 5 = 8, dus de initiële basislijn X 0 = (10, 0, 20, 0, 8). We zien dat de waarden van de basisvariabelen gelijk zijn aan de rechterkant van de beperkingen. Hieruit blijkt duidelijk dat de rechterkant positief moet zijn B i .
In de toekomst zullen we de basisvariabelen combineren in een vector X B.
Dus, binnen canoniek probleem van de voorkeursvorm wordt de eenheidsubmatrix als initiële basismatrix genomen A B = E, en de overeenkomstige basisvariabelen zijn gelijk aan de rechterkant van de beperkingen:
X B = B.
Voor een dergelijk basisplan kan een optimaliteitscriterium worden geformuleerd dat voldoende eenvoudig te testen is. Laten we de hoeveelheden introduceren
? J = < с B , A J > - c J , j = 1,...,n,(2.1)
Waar Met B- vector van coëfficiënten van de objectieve functie voor basisvariabelen X B , A J -J- e voorwaarde matrixkolom, C J -J- e coëfficiënt van de objectieve functie. Verschillen ? J worden simplexverschillen of simplexschattingen genoemd.
Optimaliteitscriterium voor het basisplan. Als het om een basisplan met een eenheid gaat basismatrix alle simplexschattingen niet-negatief zijn, dan is dit plan optimaal.
Laten we dit criterium toepassen om de optimaliteit van het basisplan te controleren X 0 = (10, 0, 20, 0, 8) uit voorbeeld 2.1.
Omdat in dit opzicht de vector van basisvariabelen X B =(X 1 , X 3 ,X 5 ), Dat Met B = (C 1 , C 3 ,C 5 ) = (1, 0, 2).
Vandaar,
? 1 = < с B , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,
2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,
? 3 = < с B , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,
? 4 = < с B , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,
? 5 = < с B , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.
Sinds de beoordeling ? 4 < 0, то базисный план X 0 niet optimaal. Merk op dat de simplexschattingen die overeenkomen met de basisvariabelen altijd gelijk zijn aan nul, dus het is voldoende om alleen de niet-basisschattingen te controleren.
De simplexmethode bestaat uit het vinden en testen van een hoekpunt (hoek) dat een oplossing is voor het LP-probleem. In elke fase selecteert de methode een hoekpunt en de bijbehorende variabelen, die beweging naar het minimum (maximum) garanderen met hoogste snelheid. De geselecteerde variabele vervangt de andere, meest beperkende. Met de simplexmethode kunt u ook bepalen of er een oplossing bestaat. Het algoritme dat de simplexmethode implementeert, kan worden geschreven als:
Stap 1. Er wordt een bepaald hoekpunt in de ODR bepaald, overeenkomend met de toelaatbare basisoplossingen (variabelen) gevonden door extractie uit de matrix T- lineair onafhankelijke kolommen en het instellen van alle andere variabelen die overeenkomen met andere kolommen van de matrix op nul.
Stap 2. Geselecteerd uit alle mogelijke resterende p - t randen die overeenkomen met niet-basisvariabelen, een rand (variabele) die, wanneer je erlangs beweegt, leidt tot de snelste afname van de doelfunctie.
Stap 3. Het is alsof er een beweging wordt uitgevoerd vanaf het initiële hoekpunt langs de geselecteerde rand naar een ander hoekpunt, wat een nieuwe oplossing oplevert met een lagere CF-waarde. Een nieuw hoekpunt wordt gevormd door de basisvariabele (rand) te vervangen door een nieuwe basisvariabele (rand).
De kolommen en elementen van vectoren worden meestal geordend en geschreven in de vorm van een simplextabel, waarvan de vorming hieronder zal worden getoond.
De simplexmethode lost het LP-probleem op standaard formulier.
Minimaliseer (maximaliseer) de functie onder de voorwaarden x > 0; Bijl = b.
Matrix A is echt en heeft de dimensie T x "en rang T.
Het geformuleerde LP-probleem kan ook in de vorm worden geschreven
Gebaseerd op de registratie van het LP-probleem in de vorm (8Л), kunnen we zeggen dat de uitgebreide matrix
afmetingen (t+ 1) (n+ 2) komt overeen met oplossingen[x/] t.
Laten we matrix A voorstellen als een reeks kolommen
Omdat matrix A rang heeft T, dan zal er zijn T lineair onafhankelijke kolommen van de matrix A, bijvoorbeeld (a U1 ,...,a U/u Beschouw een vector x° > 0, zodat al zijn p - t elementen zijn 0 en Ax° = b. Laat dit elementen met cijfers zijn..., ik n _ m . Laten we ook aannemen dat de locatie aw van lineair onafhankelijke kolommen van matrix A overeenkomt met de locatie van niet-nul elementen in de vectoren 0. Geometrisch betekent dit volgens Verklaring 3 van § 7.6 dat x° het hoekpunt (de hoek) van de ODR is en bovendien aan de gegeven voorwaarden voldoet. Deze oplossing heet toelaatbare basisoplossing. De hoeken van de toegestane set zijn toelaatbare basisoplossingen.
Bedenk dat de reeks basisoplossingen alle informatie bevat die nodig is voor de optimale oplossing van het LP-probleem. Voor het tweedimensionale geval dat in § 7.6 wordt besproken, zijn de basisoplossingen alle 6 punten, en zijn de toelaatbare basisoplossingen de punten L, V, Si 0.
Elke vector x die lijkt op x° kan dus worden geschreven als
Waar x-in- een vector waarvan de elementen overeenkomen met lineair onafhankelijke kolommen van matrix A; xF - vector met nul elementen.
Laten we op dezelfde manier de vectoren definiëren
Variabelen die elementen van een vector zijn x binnen, worden genoemd fundamentele variabelen en de variabelen die elementen van de vector zijn x F worden genoemd vrij (niet-basisvariabelen.
Omdat x° F=0, dan zal de waarde van de objectieve functie voor de initiële vector x° gelijk zijn aan
waarbij /° de waarde is van / op punt x°.
Oplossing (8.1) van de vorm [x°/°]t voor x > 0 wordt aangeroepen voor de hand liggende (expliciete) oplossing. Als we dus niet-basisvariabelen gelijk stellen aan nul, krijgen we een voor de hand liggende oplossing.
Laten we het voor het gemak herschikken T lineair onafhankelijke kolommen van matrix A in linkerkant en schrijf de matrix in het formulier
Hier komt matrix B overeen T lineair onafhankelijke kolommen 
heeft dimensie tx t en rang T, en de matrix F
is tx (p - t) matrix. Omdat matrix B uit lineair onafhankelijke kolommen bestaat, heeft deze een inverse B -1 en detB φ 0. Merk op dat je voor het vormen van matrix B elke willekeurige kunt kiezen T lineair onafhankelijke kolommen van matrix A.
Laten we probleem (8.1) weergeven, rekening houdend met de geïntroduceerde notatie
Deze representatie komt overeen met de uitgebreide matrix. Laten we dat aannemen
vanwaar volgt
Als vector x V zal een oplossing zijn voor het systeem Bx d = b, dan zal het de basisoplossing zijn. Als de ongelijkheid blijft bestaan V= B -1 b > O, dus x-in zal een aanvaardbare oplossing zijn.
Dus, huidige oplossing voldoet aan de volgende vergelijking:
Laten we matrix (8.4) bekijken. Basisvariabelen zullen worden gepresenteerd in uitdrukkelijk, als we matrix B vervangen door de identiteitsmatrix I. Als we de eerste rij van matrix (8.4) aan de linkerkant vermenigvuldigen met B ~ 1, krijgen we
waarbij B_1 b > O, d.w.z. T bovenste elementen in de rechterkolom zijn niet-negatief en vertegenwoordigen de huidige waarde van de variabelen.
Aan de linkerkant bovenste regel Het resultaat is een eenheidsmatrix: B -1 B = I. Deze presentatie erg handig, want bij vermenigvuldigen met een vector x-in elke variabele staat op een aparte regel.
De basisoplossing, die we als toelaatbaar beschouwen en overeenkomt met basis B, is dus x m = [x in 0], waarbij x-in == B_1 b. De basisoplossing vloeit voort uit de veronderstelling dat x F = 0. Echter, als xF* 0, dan kan x^ worden berekend als x 5 = = B~"b - B^"Fx/r. Deze uitdrukking vervangen door doelfunctie(kostenfunctie), krijgen we
Omdat het noodzakelijk is om de afhankelijkheid van de kosten te bepalen van niet-basisvariabelen, waarvan er dan één wordt opgenomen in de basisvariabelen, zou de onderste regel onder matrix I nul moeten zijn. Om dit te doen, vermenigvuldigen we in (8.7) de eerste rij (van de matrix) met van tot en voeg het toe met de tweede
waar is de waarde van de objectieve functie voor de eerste eeuw
torus x 0 uit (8.3).
Matrix (8.8) wordt genoemd simplex tafel. Ik breng haar naar deze soort is beginfase simplex algoritme. Tijdens de uitvoering van het algoritme wordt er van de ene tabel naar de andere overgegaan totdat het element rechtsonder van de tabel het maximum of minimum wordt.
Met behulp van een simplextabel is het gemakkelijk om een geldige oplossing te zien. Variabelen X F komt overeen met de nul-submatrix, variabelen x-in- eenheidsmatrix:
Laten we aannemen dat het LP-probleem is teruggebracht tot de standaardvorm, dat de simplextabel is berekend en dat de initiële basisoplossing die overeenkomt met het hoekpunt van het oplossingsveelvlak is geselecteerd.
Dan 
- oplossing voor probleem (8.1). Dus
zoals b > Oh, dit is een in principe toelaatbare oplossing.
Laten we matrix (8.9) in een handiger vorm presenteren, waarbij we de basisnotatie behouden:
Laten we de problemen van maximalisatie en minimalisatie afzonderlijk bekijken.
Het vinden van het optimale plan. Deze methode is universeel; het maakt het mogelijk lineaire programmeerproblemen van elke dimensie op te lossen in een algemene formulering. Deze methode vereist echter dat het oorspronkelijke probleem wordt teruggebracht tot een canonieke vorm.
Het belangrijkste idee van de simplexmethode is om van het ene hoekpunt van de ODR naar het andere te gaan, zodat bij elke overgang de waarde van de CF afneemt. Zo kun je van elk hoekpunt naar het optimale punt komen en het optimale plan krijgen.
Bijvoorbeeld: laat het referentieplan X =(x1,x2,…,xm,0,0,…,0) en het bijbehorende stelsel van lineair onafhankelijke vectoren: A1,A2,…,Am bekend zijn, dan voor dit referentieplan je kunt de waarde CF Z=(c1x1+c2x2+…+cmxm) berekenen en de beperkingsvoorwaarden opschrijven in het volgende formulier x1A1+x2A2+…+xmAm=b
Omdat de vectoren A1, A2,…, Am lineair onafhankelijk zijn, kan elke vector Aj worden uitgebreid tot deze vectoren: Aj=x1jA1+x2jA2+…+xmjAm (*) Laten we de waarden Zj Zj=x1jc1+x2jc2+…+ introduceren xmjcm, waarbij xij de coëfficiënt is die overeenkomt met Ai in de expansievector Aj door basisvectoren
Stelling 1: Verbetering van het referentieplan
Als voor een bepaalde index j aan de voorwaarde Zj-Cj>0 is voldaan, kan de waarde van de CF worden verlaagd en:
· als de CF van onderaf beperkt is, dan is het mogelijk om een referentieplan op te stellen met een kleinere CF-waarde, dezelfde als voorheen
· als de TF niet van onderaf wordt beperkt, is het mogelijk een plan te construeren dat overeenkomt met een willekeurig kleine waarde van de TF
Stelling 2: optimaliteitscriterium voor het referentieplan
Als voor bepaalde index j in het referentieplan de ongelijkheid Zj-Cj0. Wordt dit minimum gehaald voor de vector Ak, dan is het deze vector die uit de basis moet worden afgeleid. De lijn die overeenkomt met deze vector wordt een gids genoemd en wordt aangegeven met “à”.
4. Nadat u de kolom- en rijhulplijnen hebt gedefinieerd, vult u een nieuwe simplextabel in. In zo'n tabel verschijnt Ai in plaats van de hulplijn. Vulling nieuwe tafel begint met een richtlijn. Als onderdeel van het referentieplan wordt daar de waarde Ԩ0 X'l=Ԩ0=Xk/Xkl geschreven, de overige elementen van deze lijn worden bepaald door de formule X'lj X'lj=Xkj/Xkl waarbij Xkl het element is gelegen op de kruising van de rij- en kolomhulplijnen, met name daarop zijn alle voormalige elementen van de hulplijn verdeeld en verschijnt er automatisch een eenheid op de plaats van het voormalige Xkl-element. Algemene regel om de hulplijn opnieuw te berekenen, kunt u deze als volgt schrijven: Ak (nieuw element van de hulplijn) = (oud element van de hulplijn)/(element dat zich op het snijpunt van de hulplijn en de rij bevindt)
5. Alle elementen van de resterende rijen van de tabel worden opnieuw berekend, inclusief de extra onderste regel. Herberekening wordt uitgevoerd volgens de formules
· voor onderdelen van het referentieplan X’i=Xi-Ԩ0Xil=Xi-(Xk/Xkl)*Xil
· voor componenten uitgebreid over de basis X’ij=Xij-(Xkj/Xkl)*Xil
· Voor extra lijn Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)
Al deze formules zijn opgebouwd volgens één regel:
(nieuw e-mailadres)=(oud e-mailadres)-(nieuwe rijrichting-e-mail)*(richting-e-mail voor de kolom in de overeenkomstige rij)
Na het invullen van de nieuwe simplextabel vindt de overgang naar de tweede fase van het algoritme plaats.
Methoden van natuurlijke en kunstmatige basis. Basisconcepten, algoritmen van methoden.
Voor de meeste lineaire programmeerproblemen doen zich problemen voor bij het oplossen ervan die verband houden met het bepalen van het initiële referentieplan en de initiële simplextabel van waaruit alle iteraties beginnen. Dit komt door het feit dat er bij echte problemen tussen de vectoren Ai geen vectoren zijn die slechts één niet-nul component bevatten, dat wil zeggen vectoren van de vorm (0,0,0,…,0,1,0,…,0) of hun aantal is niet voldoende om een basis te vormen. Dat wil zeggen, het is niet mogelijk om een natuurlijke basis te vormen.
De kunstmatige basismethode is gebaseerd op kunstmatige introductie V wiskundig model problemen van dergelijke vectoren.
Laat het gegeven worden ZLP canoniek vormen
F: C1X1=C2X2+…+CnXnàmin
a11x1+a21x2+…+an1xn=b1
a12x1+a22x2+…+an2xn=b2
…………………………
a1mx1+a2mx2+…+anmxn=bm
Vervolgens wordt het omgezet naar het formulier
F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin
a11x1+a21x2+…+an1xn+xn+1=b1
a12x1+a22x2+…+an2xn+xn+2=b2
……………………………….
a1mx1+a2mx2+…+anmxn+xn+m=bm
Waar M oneindig is grote cijfers. In het resulterende probleem is de initiële basis onmiddellijk zichtbaar; de vectoren met de kunstmatig geïntroduceerde variabelen xn+1, xn+2,…, xn+m moeten als zodanig worden beschouwd. Omdat deze vectoren de vorm zullen hebben: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Het getransformeerde probleem wordt vervolgens opgelost met behulp van het simplexmethode-algoritme. Het initiële referentieplan van het getransformeerde probleem heeft de vorm (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, bm). De originele simplextabel ziet er als volgt uit:
| Basis | coëfficiënt CF | Plan | C1 | C2 | … | Cn | M | M | … | M |
| A1 | A2 | … | Een | Een+1 | Een+2 | … | Een+m | |||
| Een+1 | M | b1 | een11 | een21 | … | an1 | 1 | 0 | … | 0 |
| Een+2 | M | b2 | een12 | een22 | … | een2 | 0 | 1 | … | 0 |
| … | … | … | … | … | … | … | … | … | … | … |
| Een+m | M | bm | a1m | a2m | … | om | 0 | 0 | … | 1 |
| Z0 | ||||||||||
We bepalen de elementen van de extra lijn met behulp van de formules Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi
Om de verschillen te bepalen Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n
Zj-Cj=M∑mj=1aij-Cj
Na ontvangst van de originele simplextabel wordt deze getransformeerd, waarbij wordt geprobeerd uit de basisvectoren af te leiden die overeenkomen met de geïntroduceerde aanvullende variabelen.
Omdat M erg is groot aantal, dan zullen er onder de verschillen Zj-Cj veel positieve getallen zijn. Dat wil zeggen dat er veel kandidaten zullen zijn voor opname in de basis onder de vectoren A1,A2,…,An
Als een vector overeenkomt met de kunstmatig geïntroduceerde variabelen xn+1,xn+2,…,xn+m, dan wordt de overeenkomstige vector afgeleid van de basis, en wordt de simplexkolom van de tabel met deze vector doorgestreept en niet geretourneerd er weer naar toe. Aan het einde van de simplex-tabeltransformatie zijn twee opties mogelijk:
· alle vectoren die overeenkomen met kunstmatige variabelen zijn afgeleid van de basis, in dit geval zullen alle kolommen van de simplextabel die overeenkomen met aanvullende variabelen verdwijnen, en zal de oplossing zijn origineel probleem
· het resulterende optimale plan zal nog steeds een extra variabele bevatten, dit betekent dat de ODD van het oorspronkelijke probleem leeg is, dat wil zeggen dat de beperkingen ervan tegenstrijdig zijn, en daarom heeft het oorspronkelijke probleem helemaal geen oplossingen.
Dubbele lineaire programmeerproblemen. Verklaring van problemen, hun eigenschappen.
Symmetrische dubbele problemen:
Eerste standaardformulier
f(x)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+…+an1xn>=b1
a12x1+a22x2+…+an2xn>=b2
…………………………………………..
a1mx1+a2mx2+…+anmxn>=bm
Dubbel probleem
d(y)=b1y1+b2y2+…+bmijnmàmax
a11y1+a12y2+…+a1mym=0, V j=1,m
Niet-zevenvoudig paar dubbele problemen
Het oorspronkelijke probleem in canonieke vorm
f(x)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+..+an1xn=b1
a12x1+a22x2+..+an2xn=b2
…………………………..
2. Introductie van natuurlijke basisvariabelen. Constructie van een simplextafel. Definitie van het nulplan.
Simplex-methode. Algoritme van de simplexmethode.
Simplex-methode- een algoritme voor het oplossen van een optimalisatieprobleem van lineaire programmering door de hoekpunten van een convex veelvlak in een multidimensionale ruimte op te sommen. De methode werd in 1947 ontwikkeld door de Amerikaanse wiskundige George Danzig.
Het idee van de simplexmethode is dat het gestelde beschrijvende probleem wordt vertaald in wiskundige vorm. De wiskundige formulering van het probleem bevat de vergelijking van de objectieve functie die het gewenste resultaat aangeeft - het bepalen van het minimum of maximum van de objectieve functie; systemen lineaire beperkingen, gegeven door gelijkheden of ongelijkheden. De resulterende wiskundige beschrijving leidt tot matrixvorm. Vervolgens wordt de matrixbeschrijving van het probleem teruggebracht tot een canonieke vorm. Na het systeem lineaire vergelijkingen teruggebracht tot een canonieke vorm, beginnen we het lineaire programmeringsprobleem op te lossen. Het algoritme voor het oplossen van dit probleem bestaat uit een reeks construerende matrices. Elke stap van de oplossing brengt u dichter bij het verkrijgen van het gewenste resultaat.
In het rekenschema van de simplexmethode wordt een geordend proces geïmplementeerd waarin, beginnend bij een initieel toelaatbaar hoekpunt (meestal de oorsprong), opeenvolgende overgangen worden gemaakt van het ene toelaatbare uiterste punt naar het andere totdat een punt dat overeenkomt met de optimale oplossing wordt gevonden. gevonden.
Simplex-methode-algoritme
1. We brengen het systeem van beperkingen naar een canonieke vorm (wanneer het systeem beperkt is). Bovendien kan er één basis in het systeem worden geïdentificeerd.
2. Zoek het origineel referentieplan(niet-negatieve basisoplossingen van het KZLP-systeem van vergelijkingen). Elk van de referentieplannen wordt bepaald door een systeem van m lineair onafhankelijke vectoren, vervat in een gegeven systeem van n vectoren A 1 , A 2 ,…, Een. De bovengrens voor het aantal referentieplannen in een gegeven opgave wordt bepaald door het aantal combinaties Met nm);
3. Wij bouwen simplex tafel (simplex tafel een matrix die dient als middel om toelaatbare basisoplossingen van een (niet-gedegenereerd) lineair programmeerprobleem op te sommen bij het oplossen ervan met behulp van de simplexmethode. Het is gevormd uit een matrix van coëfficiënten van een systeem van lineaire programmeervergelijkingen teruggebracht tot canonieke vorm. De sequentiële transformatie ervan volgens het zogenaamde simplex-algoritme maakt een beperkt aantal stappen (iteraties) mogelijk om het gewenste resultaat te verkrijgen - een plan dat voorziet in; een extreme waarde van de objectieve functie).
4. B simplex tafel we controleren de vectoren op negativiteit, d.w.z. beoordelingen Zj – Сj geschreven in de regel moet ≤ 0 zijn (minimaal), Zj – Сj ≥ 0(tot het maximum). Als de schattingen aan de optimaliteitsvoorwaarden voldoen, is het probleem opgelost.
5. Als voor sommige vectoren de optimaliteitsvoorwaarden worden geschonden, dan is het noodzakelijk om in de basis een vector te introduceren die overeenkomt met:
max[θ 0 j (Zj – Сj)] ; min[θ 0 j (Zj – Сj)] ; θ 0 j = min, Waar x ik> 0
Vectorelement θ j wat overeenkomt θ 0 j tolerant genoemd; de rij en kolom waarin deze zich bevindt, worden de gidsvector genoemd in de gidsrij verlaat de basis;
6. Laten we de uitzettingscoëfficiënt voor alle vectoren in de nieuwe basis vinden. Laten we de Giordano Gauss-methode toepassen
Laten we eens kijken naar het optimale referentieplan. Als de schatting aan de optimaliteitsvoorwaarden voldoet, wordt het probleem opgelost; zo niet, dan worden stappen 5-7 uitgevoerd.
2. Introductie van natuurlijke basisvariabelen. Constructie van een simplextafel. Definitie van het nulplan.
De simplexmethode is het meest effectief bij het oplossen van complexe problemen en vertegenwoordigt een iteratief (stapsgewijs) proces dat begint met nul(referentie) oplossing (vertex N-dimensionaal veelvlak). Volgende op zoek optimale optie Het plan gaat uit van beweging langs de hoekpunten (hoekpunten van het veelvlak) totdat de waarde van de doelfunctie de maximale (minimale) waarde bereikt. Laten we het algoritme van de simplexmethode bekijken aan de hand van het voorbeeld van een omzetplanningsprobleem beperkte middelen grondstoffen.
Het bedrijf verkoopt N productgroepen, hebben M beperkte materiële en monetaire middelen B ik ≥0 (1 ≤ i≤ m). De resourcekosten van iedereen zijn bekend i- type productie en verkoop van een eenheid goederen van elke groep, gepresenteerd in de vorm van een matrix ( A ij) en de winst die de onderneming ontvangt uit de verkoop van een eenheid goederen J-groep opgenomen in de objectieve functie Z(X). De lineaire programmeermethode verschilt niet van systeem (1) - (2):
Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)
a 11 X 1 + a 12 X 2 +…a 1n X n ≤ b 1,
a 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)
a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,
X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0
De stadia van het oplossen van het probleem met behulp van de simplexmethode zijn onder meer:
1) Opstellen van een nulreferentieplan. We introduceren nieuwe niet-negatieve (basis) variabelen, waardoor het systeem van ongelijkheden (2) een systeem van vergelijkingen wordt:
a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1
a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)
……………………………………..
a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,
Als we de invoervariabelen als kolomvectoren nemen, vertegenwoordigen ze enkel (eenvoudig) vectoren. Merk op dat de basisvariabelen een eenvoudige waarde hebben fysieke betekenis- Dit rest specifieke resource in het magazijn voor een bepaald productieplan, daarom wordt deze basis genoemd natuurlijk. We lossen systeem (3) op met betrekking tot de basisvariabelen:
X n+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n
X n+2 = b 2 - een 21 X 1 - een 22 X 2 -…a 2n X n (4)
………………………………………..
X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n
We herschrijven de objectieve functie in de vorm
Z(X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -…-с n Х n) (5)
Aangenomen dat de vereiste hoofdvariabelen X 1 = X 2 = X 3 = ... = X n = 0, verkrijgen we een nulreferentieplan X = (0, 0, ...0, b 1, b 2, b 3 ... b m), waarbij Z(X) = 0 (alle grondstoffen op voorraad, niets geproduceerd). We voeren het plan in een simplextabel in.
| Plan | Basis | C ik /C j | Betekenis X ik | X 1 | X2 | Xn | Xn+1 | Xn+2 | X n+ 3 | Q min |
| Xn+1 | b1 | een 11 | een 12 | een 13 | b1/a 12 | |||||
| Xn+2 | b2 | een 21 | een 22 | een 23 | b2 / een22 | |||||
| Xn+3 | b3 | een 31 | een 32 | een 33 | b3 / een 32 | |||||
| Z(X) = 0 | -C1 | -C2 | - C3 | Index. lijn |
2) Selecteer uit de negatieve coëfficiënten van de indexlijn de grootste absolute waarde, die de leidende kolom bepaalt en laat zien welke variabele bij de volgende iteratie (stap) van de hoofdkolom (gratis) naar de basis verplaatst (in feite wordt er een productgroep geselecteerd waarvan de verkoop maximaal inkomen). Vervolgens delen we de grondstoffenvoorraden bi door de overeenkomstige kostencoëfficiënten, voeren de resultaten in een tabel in en bepalen de minimumwaarde Qmin (de hulpbron waarvan de reserve de output van de geselecteerde productgroep het sterkst beperkt, wordt geselecteerd). Deze waarde selecteert de leidende lijn en de variabele Xi, die bij de volgende stap (iteratie) de basis zal verlaten en vrij zal komen.
3) De overgang naar een nieuw plan wordt uitgevoerd als resultaat van de herberekening van de simplextabel met behulp van de Jordan-Gauss-methode. Eerst vervangen we X j in de basis door X i van de leidende kolom. Laten we alle elementen van de leidende lijn delen door het oplossende element (RE), waardoor de plaats van de RE in de leidende lijn 1 zal zijn. Omdat X i basaal is geworden, moeten de resterende coëfficiënten gelijk zijn aan 0. Nieuwe elementen van dit plan worden gevonden volgens de rechthoekregel
NO=SE – (A*B)/RE (6)
Het resulterende plan wordt geëvalueerd met behulp van de coëfficiënten van de indexlijn: als ze allemaal positief zijn, is het plan optimaal. Zo niet, dan kan het plan worden verbeterd door de volgende iteratie (stap) uit te voeren.
Voorbeeld. Er werd 20 duizend roebel toegewezen voor de aankoop van apparatuur voor de productielocatie. De apparatuur kan worden geplaatst op een oppervlakte van maximaal 72 m². U kunt apparatuur van twee typen bestellen: type A, waarvoor een productieoppervlak van 6 m² nodig is en 6.000 eenheden worden geleverd. producten per ploeg (prijs 5.000 roebel) en type B, waarvoor een oppervlakte van 12 m² nodig is, waarbij 3.000 eenheden worden geproduceerd (prijs 2.000 roebel). Wat is het optimale aanschafplan voor apparatuur om te garanderen maximale prestaties verhaallijn?
Laten we de hoeveelheid gekochte apparatuur van het type A en B aangeven met respectievelijk X 1 en X 2.
Locatieproductiviteit (objectieve functie): Z(X) =6Х 1 +3Х 2.
De belangrijkste beperkingen houden verband met elkaar
met contant geld: 5Х 1 +2Х 2 ≤ 20,
met oppervlakte productielocatie: 6Х 1 +12Х 2 ≤ 72.
We introduceren nieuwe basisvariabelen X 3 (rest contant geld na aanschaf van apparatuur) en X 4 (resterend gebied na plaatsing van apparatuur) en herschrijf de beperkingen in de vorm van een systeem van vergelijkingen:
5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)
6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)
In dit geval is de doelfunctie: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .
We maken een referentieplan (0e): X = (0, 0, 20, 72), d.w.z. Er is nog niets gekocht (er is geen geld uitgegeven, de ruimte is leeg). Een simplextafel maken
| Plan | Basis | C ik /C j | Betekenis X ik | X 1 | X2 | X3 | X4 | Q min | |||
| X3 | 20/5=4 | ||||||||||
| X4 | 72/6=12 | ||||||||||
| Z(X) = 0 | - 6 | - 3 | Indexlijn | ||||||||
| →X 1 | 0,4 | 0,2 | 4/0,4=10 | ||||||||
| X4 | 9,6 | -1,2 | 48/9,6=5 | ||||||||
| Z(X) = 6*4=24 | -0,6 | 1,2 | Indexlijn | ||||||||
| X 1 | 0,25 | -1/24 | - | ||||||||
| →X 2 | -1/8 | 5/48 | - | ||||||||
| Z(X) =6*2+3*5=27 | 9/8 | 1/16 | Indexlijn | ||||||||
Het is duidelijk dat de leidende kolom overeenkomt met X 1, omdat deze de grootste index 6 heeft. We vinden de minimumwaarde van Q min = 4 (de zwaarste beperking van de middelen) door een leidende rij te definiëren die laat zien dat X 3 is afgeleid van de basisvariabelen , en X wordt ingevoerd in plaats van 1. We herberekenen de elementen van de leidende lijn, delen ze door 5, en met behulp van formule (6) bepalen we de elementen van de tweede en indexlijnen. De doelfunctie voor het eerste plan is gelijk aan Z(X) = 6*4+3*0 = 24.
Eén van de coëfficiënten van de indexrij voor kolom X2 blijft daarom echter negatief -0,6 dit plan is niet optimaal en er is nog een iteratie (stap) nodig om dit te verbeteren. Selecteer de 2e kolom als leidend en minimale waarde Q min = 5 we definiëren de leidende lijn met de basisvariabele X 4. Nadat we dezelfde transformaties hebben uitgevoerd, verkrijgen we het tweede plan, dat optimaal zal zijn, aangezien alle indexcoëfficiënten positief zijn.
Laten we de verkregen resultaten analyseren. Bij optimale oplossing de objectieve functie heeft maximale waarde 27 duizend roebel, terwijl beide middelen uit de basis worden verwijderd en dus volledig worden uitgegeven.
Laten we hier zeker van zijn: 5*2+2*5 = 20 duizend roebel, 6*2+12*5=72 m². De vereiste oplossing is X = (2; 5;0;0). Dit gebeurt niet altijd.
Lezing nr. 10
Onderwerp: Simplexmethode voor problemen met een kunstmatige basis
De simplex-oplossingsmethode is gebaseerd op de introductie van aanvullende (basis)variabelen die het mogelijk maken een eenheidsmatrix te vormen. Als de probleembeperkingen worden gepresenteerd in de vorm van ongelijkheden:
a i1 X 1 + a i2 X 2 +…a in X n ≥ b ik (1)
of vergelijkingen:
a i1 X 1 + a i2 X 2 +…a in X n = b ik (1*),
dan is het onmogelijk om het referentieplan in de gewenste vorm te verkrijgen. In dit geval introduceren we om te voldoen aan gelijkheden (1*). kunstmatige basis Y i , en kunstmatige variabelen houden niet direct verband met de inhoud van de taak, maar maken het mogelijk een referentie- (start)plan op te stellen:
a i1 X 1 + a i2 X 2 +…a in X n +Y ik = b ik (2)
De objectieve functie bij het maximaal oplossen van het probleem wordt in de vorm geschreven:
Z(X) =∑C j X j +(-M)∑Y ik (3),
bij het oplossen van een soortgelijk probleem op zijn minst:
Z(X)=∑C j X j +(M)∑Y i (3*),
waarbij M erg groot is positief getal, een soort straf voor het gebruik van kunstmatige variabelen.
In het geval van ongelijkheden (1) introduceren we in eerste instantie extra variabelen X n + i met een minteken. Hun matrix zal niet unitair zijn, daarom introduceren we in elke ongelijkheid van systeem (1) kunstmatige variabelen У i:
a i1 X 1 +a i2 X 2 +…a in X n –X n+i +Y ik =b ik (4)
De objectieve functie is in dit geval Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (om het maximum te vinden). Het gebruik van een kunstmatige basis geeft de simplexmethode meer flexibiliteit en maakt het mogelijk deze voor een breed scala aan problemen te gebruiken.
Voorbeeld . Bepaal de maximale en minimale winstwaarden voor de productie van twee soorten producten A en B, als de productiekosten en winstgevendheid uit de verkoop van een producteenheid in de tabel worden gegeven. De belangrijkste voorwaarde is volledige werkgelegenheid van werknemers in de onderneming.
Wiskundig gezien zullen de productie-outputbeperkingen worden geschreven in de vorm van een gemengd systeem:
1X 1 + 1X 2 ≤ 6,
2X 1 + 1X 2 =8.
Laten we de basisvariabele X 3 introduceren voor de eerste ongelijkheid, en de kunstmatige variabele Y 1 voor de tweede vergelijking:
1X 1 + 1X 2 + X 3 = 6,
2X 1 + 1X 2 +Y 1 =8.
Laten we X 3 en Y 1 uitdrukken uit het resulterende stelsel vergelijkingen en, om het maximum te bepalen, de objectieve functie voorstellen:
Z(X)= 3X 1 + 2X 2 +0X 3 –MJ 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=
3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M
Voor het referentieplan - X=(0,0,6,8). Laten we een simplextabel bouwen:
| Plan | Basis | C ik /C j | Betekenis X ik | X 1 | X2 | X3 | J 1 | Q min |
| X3 | 6/1=6 | |||||||
| J 1 | -M | 8/2=4 | ||||||
| Z(X) = -8M | -2M-3 | -M-2 | Indexlijn | |||||
| X3 | 0,5 | -0,5 | 2/0,5=4 | |||||
| →X 1 | 0,5 | 0,5 | 4/0,5=8 | |||||
| Z(X) = 3*4=12 | - 0,5 | M+1,5 | Indexlijn | |||||
| →X 2 | -1 | - | ||||||
| X 1 | -1 | - | ||||||
| Z(X) =3*2+2*4=14 | M+1 | Indexlijn |
In de regel begint de verbetering van het referentieplan met het verwijderen van de kunstmatige variabele Y 1 uit de basis. Het optimale plan X = (2,4,0,0) werd verkregen in de tweede iteratie, met een maximaal inkomen van 14. duizend. wrijven. , en de coëfficiënten van de indexrij zijn niet-negatief. Het is gemakkelijk om te verifiëren dat bij deze taak, met een optimaal plan, de middelen volledig worden gebruikt (2*1+4*1=6; 2*2+1*4=8).
Bij het vinden van de minimale winstgevendheid formuleren we de doelfunctie anders (+MY 1 wordt ingevoerd als term:
Z(X)= 3X 1 + 2X 2 +0X 3 +MIJN 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=
3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M
Basisplan hetzelfde, maar de indexrijcoëfficiënten in de simplextabel zijn verschillend. De leidende kolom wordt, net als voorheen, geselecteerd door de grootste absolute waarde positieve coëfficiënt voor X 1, de leidende rij wordt bepaald door de minimumwaarde van Q min = 4. Bij de eerste iteratie wordt de kunstmatige variabele Y 1 afgeleid van de basis.
| Plan | Basis | C ik /C j | Betekenis X ik | X 1 | X2 | X3 | J 1 | Q min | ||
| X3 | 6/1=6 | |||||||||
| J 1 | M | 8/2=4 | ||||||||
| Z(X) = 8M | 2M-3 | M-2 | Indexlijn | |||||||
| X3 | 0,5 | -0,5 | 2/0,5=4 | |||||||
| →X 1 | 0,5 | 0,5 | 4/0,5=8 | |||||||
| Z(X) = 3*4=12 | - 0,5 | -M+1,5 | Indexlijn | |||||||
De resulterende negatieve waarden van de coëfficiënten in de indexregel Xi geven de optimaliteit van het eerste plan aan, met een minimuminkomen van 12 duizend roebel.
Het wordt alleen geleverd door de output van product A (product B wordt niet geproduceerd), de grondstoffen worden niet volledig gebruikt (de rest X 3 = 2t), terwijl aan de belangrijkste voorwaarde is voldaan: de werknemers zijn volledig werkzaam in de productie.
Lezing nr. 11
Onderwerp: Gesloten transportprobleem
1. Wiskundige formulering van gesloten transport probleem. Bepalen van het benodigde aantal onbekenden.
2. Fasen bij het bepalen van een plan voor het oplossen van een transportprobleem.
