Deze methode is een methode om doelbewust referentieoplossingen voor het probleem op te sommen lineaire programmering. Het maakt het mogelijk om in een eindig aantal stappen een optimale oplossing te vinden, of vast te stellen dat er geen optimale oplossing bestaat.
De belangrijkste inhoud van de simplexmethode is als volgt:- Geef een methode aan om de optimale referentieoplossing te vinden
- Geef de overgangsmethode aan van de ene referentieoplossing naar de andere, waarbij de waarde van de objectieve functie dichter bij de optimale zal liggen, d.w.z. geven een manier aan om de referentieoplossing te verbeteren
- Stel criteria op waarmee u direct kunt stoppen met zoeken naar ondersteunende oplossingen bij de optimale oplossing of een conclusie kunt trekken over het ontbreken van een optimale oplossing.
Algoritme van de simplexmethode voor het oplossen van lineaire programmeerproblemen
Om het probleem op te lossen simplex methode je moet het volgende doen:- Breng de taak naar canonieke vorm
- Vind de initiële ondersteuningsoplossing met een “eenheidsbasis” (als er geen ondersteuningsoplossing is, heeft het probleem geen oplossing vanwege de incompatibiliteit van het systeem van beperkingen)
- Bereken schattingen van vectorontledingen op basis van de referentieoplossing en vul de tabel van de simplexmethode in
- Als aan het criterium voor de uniciteit van de optimale oplossing is voldaan, eindigt de oplossing van het probleem
- Als aan de voorwaarde voor het bestaan van een reeks optimale oplossingen is voldaan, worden alle optimale oplossingen gevonden door eenvoudige opsomming
Een voorbeeld van het oplossen van een probleem met behulp van de simplexmethode
Voorbeeld 26.1Los het probleem op met behulp van de simplexmethode:
Oplossing:
We brengen het probleem naar een canonieke vorm.
Voor dit doel in linkerkant Voor de eerste ongelijkheidsbeperking introduceren we een extra variabele x 6 met een coëfficiënt van +1. De variabele x 6 is opgenomen in de objectieve functie met een coëfficiënt van nul (d.w.z. hij is niet inbegrepen).
Wij krijgen:
We vinden de initiële ondersteuningsoplossing. Om dit te doen, stellen we vrije (onopgeloste) variabelen gelijk aan nul x1 = x2 = x3 = 0.
Wij krijgen referentie oplossing X1 = (0,0,0,24,30,6) met eenheidsbasis B1 = (A4, A5, A6).
Wij berekenen schattingen van vectorontledingen omstandigheden op basis van de referentieoplossing volgens de formule:
Δ k = C b X k - c k
- C b = (c 1, c 2, ..., cm) - vector van coëfficiënten van de objectieve functie voor de basisvariabelen
- X k = (x 1k, x 2k, ..., x mk) - uitbreidingsvector van de overeenkomstige vector A k volgens de basis van de referentieoplossing
- C k is de coëfficiënt van de objectieve functie voor de variabele x k.
De schattingen van de in de basis opgenomen vectoren zijn altijd gelijk aan nul. De referentieoplossing, uitbreidingscoëfficiënten en schattingen van uitbreidingen van vectoren van omstandigheden op basis van de referentieoplossing zijn geschreven in simplex tafel:
Voor het gemak van het berekenen van schattingen worden bovenaan de tabel de coëfficiënten van de objectieve functie geschreven. In de eerste kolom "B" worden de vectoren geschreven die deel uitmaken van de basis van de referentieoplossing. De volgorde waarin deze vectoren worden geschreven komt overeen met het aantal toegestane onbekenden in de beperkingsvergelijkingen. In de tweede kolom van de tabel "C b" worden de coëfficiënten van de doelfunctie voor de basisvariabelen in dezelfde volgorde geschreven. Bij juiste locatie De coëfficiënten van de objectieve functie in de kolom "C b" van de schatting van de eenheidsvectoren die in de basis zijn opgenomen, zijn altijd gelijk aan nul.
In de laatste rij van de tabel met schattingen van Δ k in de kolom "A 0" worden de waarden van de objectieve functie op de referentieoplossing Z(X 1) geschreven.
De initiële ondersteuningsoplossing is niet optimaal, omdat in het maximale probleem de schattingen Δ 1 = -2, Δ 3 = -9 voor de vectoren A 1 en A 3 negatief zijn.
Volgens de stelling over het verbeteren van de ondersteuningsoplossing kun je, als in een maximumprobleem ten minste één vector een negatieve schatting heeft, een nieuwe ondersteuningsoplossing vinden waarop de waarde van de doelfunctie groter zal zijn.
Laten we bepalen welke van de twee vectoren zal leiden tot een grotere toename in de objectieve functie.
De toename van de doelfunctie wordt gevonden door de formule: .
We berekenen de waarden van de parameter θ 01 voor de eerste en derde kolom met behulp van de formule:
We verkrijgen θ 01 = 6 voor l = 1, θ 03 = 3 voor l = 1 (Tabel 26.1).
We vinden de toename van de objectieve functie bij het introduceren in de basis van de eerste vector ΔZ 1 = - 6*(- 2) = 12, en de derde vector ΔZ 3 = - 3*(- 9) = 27.
Daarom, voor een snellere aanpak optimale oplossing het is noodzakelijk om vector A3 in de basis van de referentieoplossing te introduceren in plaats van de eerste vector van basis A6, aangezien het minimum van parameter θ 03 wordt bereikt in de eerste rij (l = 1).
We voeren de Jordan-transformatie uit met het element X13 = 2, we verkrijgen de tweede referentieoplossing X2 = (0,0,3,21,42,0) met als basis B2 = (A3, A4, A5). (Tabel 26.2)
Deze oplossing is niet optimaal, aangezien vector A2 een negatieve schatting heeft Δ2 = - 6. Om de oplossing te verbeteren is het noodzakelijk om vector A2 in de basis van de referentieoplossing te introduceren.
We bepalen het nummer van de vector afgeleid van de basis. Om dit te doen, berekenen we de parameter θ 02 voor de tweede kolom, deze is gelijk aan 7 voor l = 2. Daarom leiden we de tweede basisvector A4 af van de basis. We voeren de Jordan-transformatie uit met het element x 22 = 3, we verkrijgen de derde referentieoplossing X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabel 26.3).
Deze oplossing is de enige optimale, aangezien voor alle vectoren die niet in de basis zijn opgenomen de schattingen positief zijn
Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.
Antwoord: max Z(X) = 201 bij X = (0,7,10,0,63).
Lineaire programmeermethode in economische analyse
Lineaire programmeermethode maakt het mogelijk om het meest optimale te rechtvaardigen economische beslissing onder omstandigheden van ernstige beperkingen met betrekking tot de middelen die bij de productie worden gebruikt (vaste activa, materialen, arbeidsmiddelen). Het gebruik van deze methode bij economische analyse maakt het mogelijk problemen op te lossen die voornamelijk verband houden met het plannen van de activiteiten van een organisatie. Deze methode helpt bij het bepalen van de optimale uitvoerniveaus, evenals de richtingen daarvoor effectief gebruik productiemiddelen waarover de organisatie beschikt.
Met behulp van deze methode worden de zogenaamde extreme problemen opgelost, die bestaan uit het vinden van extreme waarden, dat wil zeggen het maximum en minimum aan functies variabelen.
Deze periode is gebaseerd op de oplossing van het systeem lineaire vergelijkingen in gevallen waarin de geanalyseerde economische verschijnselen lineair en strikt met elkaar verbonden zijn functionele afhankelijkheid. De lineaire programmeermethode wordt gebruikt om variabelen te analyseren in de aanwezigheid van bepaalde beperkende factoren.
Een veel voorkomende oplossing is de zogenaamde transport probleem met behulp van de lineaire programmeermethode. De inhoud van deze taak is het minimaliseren van de kosten die worden gemaakt in verband met het gebruik van voertuigen onder bestaande beperkingen met betrekking tot het aantal voertuigen, hun laadvermogen, de duur van hun gebruik, als er behoefte is aan onderhoud maximale hoeveelheid klanten.
Daarnaast deze methode wordt veel gebruikt bij het oplossen van planningsproblemen. Deze taak bestaat uit een zodanige verdeling van de werktijd voor het personeel van een bepaalde organisatie, die het meest aanvaardbaar is, zowel voor de leden van dit personeel als voor de klanten van de organisatie.
Deze taak is het maximaliseren van het aantal cliënten dat wordt bediend onder omstandigheden van beperkingen op het aantal beschikbare personeelsleden en op het werktijdfonds.
De lineaire programmeermethode is dus vrij gebruikelijk bij plaatsings- en gebruiksanalyse. verschillende soorten middelen, maar ook bij het plannen en voorspellen van de activiteiten van organisaties.
Niettemin kan wiskundig programmeren ook worden toegepast op die economische verschijnselen waarvan de relatie niet lineair is. Voor dit doel kunnen niet-lineaire, dynamische en convexe programmeermethoden worden gebruikt.
Niet-lineaire programmering is afhankelijk van de niet-lineaire aard van de objectieve functie of beperkingen, of beide. De vormen van de objectieve functie en de ongelijkheid van beperkingen in deze omstandigheden kunnen verschillend zijn.
Niet-lineaire programmering wordt gebruikt in economische analyses, met name bij het vaststellen van de relatie tussen indicatoren die de efficiëntie van de activiteiten van een organisatie uitdrukken en het volume van deze activiteit, de structuur van de productiekosten, de marktomstandigheden, enz.
Dynamisch programmeren is gebaseerd op het construeren van een beslisboom. Elke laag van deze boom dient als podium voor het bepalen van de gevolgen eerdere beslissing en om ineffectieve opties voor deze oplossing te elimineren. Dus, dynamische programmering heeft een meerstaps- en meertrapskarakter. Dit type programmering wordt gebruikt om economische analyses te vinden optimale opties ontwikkeling van de organisatie, nu en in de toekomst.
Convex programmeren is een vorm van niet-lineair programmeren. Dit type programmering drukt de niet-lineaire aard uit van de relatie tussen de resultaten van de activiteiten van een organisatie en haar kosten. Convexe (ook wel concave) programmering analyseert convexe objectieve functies en convexe beperkingssystemen (punten aanvaardbare waarden). Convexe programmering wordt gebruikt bij de analyse van economische activiteiten met als doel de kosten te minimaliseren, en concave programmering met als doel het maximaliseren van de inkomsten onder bestaande beperkingen op de werking van factoren die de geanalyseerde indicatoren op de tegenovergestelde manier beïnvloeden. Bijgevolg worden, met de typen programmering die worden overwogen, convexe objectieve functies geminimaliseerd en worden concave objectieve functies gemaximaliseerd.
Lineaire programmeerproblemen. Het bevindt zich in een sequentiële constructie die het beschouwde proces karakteriseert. De oplossing is verdeeld in drie hoofdfasen: selectie van variabelen, constructie van een systeem van beperkingen en zoeken naar een objectieve functie.
Op basis van deze indeling kan de probleemvoorwaarde als volgt worden geherformuleerd: extremum van de doelfunctie Z(X) = f(x1, x2, … ,xn) → max (min) en de bijbehorende variabelen, als bekend is dat ze voldoen aan het systeem van beperkingen: Φ_i ( x1, x2, … ,xn) = 0 voor i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 voor i = k+1, k+ 2, …, m.
Het systeem van beperkingen moet in een canonieke vorm worden gebracht, d.w.z. naar een systeem van lineaire vergelijkingen, waarbij het aantal variabelen meer nummer vergelijkingen (m > k). In dit systeem zullen er zeker variabelen zijn die via andere variabelen kunnen worden uitgedrukt, en als dit niet het geval is, kunnen ze kunstmatig worden geïntroduceerd. In dit geval worden de eersten basis of genoemd kunstmatige basis, en de tweede zijn gratis.
Het is handiger om de simplex-methode te overwegen specifiek voorbeeld. Laat het gegeven worden lineaire functie f(x) = 6x1 + 5x2 + 9x3 en het systeem van beperkingen: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; maximale waarde functies f(x).
Oplossing Specificeer in de eerste fase op absoluut willekeurige wijze de initiële (referentie)oplossing van het stelsel vergelijkingen, die aan het gegeven stelsel van beperkingen moet voldoen. IN in dit geval de introductie van kunstmatige is vereist, d.w.z. basisvariabelen x4, x5 en x6 als volgt: 5x1 + 2x2 + 3x3 + x4 = 25;
Zoals je kunt zien, zijn de ongelijkheden omgezet in gelijkheden dankzij de toegevoegde variabelen x4, x5, x6, die niet-negatieve grootheden zijn. Zo heb je het systeem naar zijn canonieke vorm gebracht. De variabele x4 is opgenomen in de eerste vergelijking met een coëfficiënt van 1, en in de tweede vergelijking met een coëfficiënt van 0 geldt hetzelfde voor de variabelen x5, x6 en de bijbehorende vergelijkingen, wat overeenkomt met de definitie van de basis.
U hebt het systeem voorbereid en de initiële referentieoplossing gevonden – X0 = (0, 0, 0, 25, 20, 18). Presenteer nu de coëfficiënten van de variabelen en de vrije termen van de vergelijkingen (de getallen rechts van het “=” teken) in de vorm van een tabel om verdere berekeningen te optimaliseren (zie figuur).
De essentie van de simplexmethode is om deze tabel in een vorm te brengen waarin alle getallen in rij L niet-negatieve waarden zijn. Als blijkt dat dit niet mogelijk is, heeft het systeem helemaal geen optimale oplossing. Kies om te beginnen het meeste minimaal onderdeel van deze lijn is het -9. Het nummer staat in de derde kolom. Converteer de overeenkomstige x3-variabele naar een basisvariabele. Om dit te doen, deelt u de lijn door 3, zodat de cel op 1 uitkomt.
Nu heb je de cellen nodig en ga je naar 0. Om dit te doen, trek je 3 af van de overeenkomstige getallen van de derde rij. Van de elementen van de tweede rij - de elementen van de derde, vermenigvuldigd met 2. En ten slotte van de elementen van de L-rij - vermenigvuldigd met (-9). Je hebt de tweede referentieoplossing verkregen: f(x) = L = 54 met x1 = (0, 0, 6, 7, 8, 0).
Als de probleemstelling beperkingen met het ≥-teken bevat, kunnen deze worden herleid tot de vorm ∑a ji b j door beide zijden van de ongelijkheid met -1 te vermenigvuldigen. Laten we m extra variabelen x n+j ≥0(j =1,m) introduceren en de beperkingen transformeren naar de vorm van gelijkheden
(2)
Laten we aannemen dat alles initieel is taakvariabelen x 1 , x 2 ,..., x n – niet-basis. Dan zullen de aanvullende variabelen basaal zijn, en een specifieke oplossing voor het systeem van beperkingen heeft de vorm
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)
Omdat in dit geval de waarde van de doelfunctie F 0 = 0, kunnen we F(x) als volgt weergeven:
F(x)=∑c ik x ik +F 0 =0 (4)
De initiële simplextabel (simplextabel 1) wordt samengesteld op basis van vergelijkingen (2) en (4). Als de extra variabelen x n+j worden voorafgegaan door een “+” teken, zoals in (2), dan worden alle coëfficiënten vóór de variabelen x i en de vrije term b j zonder wijzigingen in de simplextabel ingevoerd. Bij het maximaliseren van de doelfunctie worden de coëfficiënten met tegengestelde tekens in de onderste rij van de simplextabel ingevoerd. De vrije termen in de simplextabel bepalen de oplossing voor het probleem.
Het algoritme voor het oplossen van het probleem is als volgt:
1e stap.
De leden van de kolom vrije leden worden bekeken. Als ze allemaal positief zijn, is er een toelaatbare basisoplossing gevonden en moet men doorgaan naar stap 5 van het algoritme, die overeenkomt met het vinden van de optimale oplossing. Als de initiële simplextabel negatieve vrije termen bevat, is de oplossing niet geldig en moet u naar stap 2 gaan.
2e stap.
| Om een aanvaardbare oplossing te vinden, wordt deze uitgevoerd en moet worden besloten welke van de niet-basisvariabelen in de basis moet worden opgenomen en welke variabele uit de basis moet worden verwijderd. | Tabel 1. | fundamentele variabelen | |||||
| Gratis leden onder beperkingen | Niet-basisvariabelen | ... | x 1 | ... | x 2|||
| x l | x n | xn+1 | b1 | ... | een 11 | ... | een 12 |
| een 1l | een 1n | xn+2 | b2 | ... | een 21 | ... | een 22 |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| een 2l | een 2n | xn+r | b2 | ... | een r1 | ... | een r2 |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| een r | arn | x n+m | b m | ... | een m1 | ... | een m2 |
| een ml | een mn | F(x)max | F0 | ... | F(x)max | ... | -c 1 |
-c 2
-c n
Om dit te doen, selecteert u een van de negatieve elementen van de kolom met vrije termen (laat het b 2 leidend of oplossend zijn). Als er geen negatieve elementen in de rij zijn met een negatieve vrije term, dan is het systeem van beperkingen inconsistent en het probleem heeft geen oplossing. Tegelijkertijd wordt de variabele die als eerste van teken verandert wanneer de geselecteerde NP x l toeneemt, uitgesloten van de BP. Dit zal x n+r zijn, waarvan de index r wordt bepaald uit de voorwaarde
De lijn die overeenkomt met de variabele x n+r wordt aangeroepen leiden of toestaan. Het element van de simplextabel arl, gelegen op het snijpunt van de leidende rij en de leidende kolom, wordt het leidende of oplossende element genoemd. Het vinden van het leidende element beëindigt het werk met elke reguliere simplextafel.
3e stap.
Er wordt een nieuwe simplextabel berekend, waarvan de elementen opnieuw worden berekend op basis van de elementen van de simplextabel van de vorige stap en worden gemarkeerd met een priemgetal, d.w.z. b" j, a" ji, c" ik, F" 0 . De elementen worden opnieuw berekend met behulp van de volgende formules:
Eerst vult de nieuwe simplextabel de rij en kolom in die in de vorige simplextabel aan het begin stonden. Uitdrukking (5) betekent dat het element a" rl in plaats van het leidende element gelijk is aan het omgekeerde van het element van de vorige simplextabel. De elementen van de rij a ri worden gedeeld door het leidende element, en de elementen van de kolom a jl wordt ook gedeeld door het leidende element, maar wordt genomen met het tegenovergestelde teken. De elementen b" r en c" l worden volgens hetzelfde principe berekend.
De rest van de formules kunnen eenvoudig worden geschreven met .
De rechthoek is zo geconstrueerd volgens de oude simplextabel dat een van de diagonalen wordt gevormd door de herberekende (a ji) en leidende (a rl) elementen (Fig. 1). De tweede diagonaal wordt uniek bepaald. Om een nieuw element a" ji te vinden, wordt het product van de elementen van de tegenovergestelde diagonaal gedeeld door het leidende element afgetrokken van element a" ji (dit wordt aangegeven door het “-” teken naast de cel). Elementen b" j, (j≠r) en c" i worden op dezelfde manier herberekend. (i≠l).
4e stap.
De analyse van de nieuwe simplextabel begint met de eerste stap van het algoritme. De actie gaat door totdat een haalbare basisoplossing is gevonden, d.w.z. alle elementen van de float-kolom moeten positief zijn.
5e stap. Wij zijn van mening dat er een aanvaardbare basisoplossing is gevonden. We kijken naar de coëfficiënten van de lijn van de doelfunctie F(x) . Een teken van de optimaliteit van een simplextabel is de niet-negativiteit van de coëfficiënten voor niet-basisvariabelen in de F-rij. Rijst. 1. Rechthoekregel Als er onder de coëfficiënten van de F-rij negatieve zijn (met uitzondering van de vrije term), dan moet je doorgaan naar een andere basisoplossing. Bij het maximaliseren van de objectieve functie bevat de basis een van de niet-basisvariabelen (bijvoorbeeld x l), waarvan de kolom overeenkomt met het maximum simplex tafels. Hiermee kunt u de variabele selecteren waarvan de toename leidt tot een verbetering van de doelfunctie. De kolom die overeenkomt met de variabele xl wordt de leidende kolom genoemd. Tegelijkertijd wordt die variabele x n+r uitgesloten van de basis, waarvan de index r wordt bepaald door de minimale simplexrelatie:
De rij die overeenkomt met x n+r wordt leidend genoemd, en het element van de simplextabel a rl, dat op het snijpunt van de leidende rij en de leidende kolom staat, wordt genoemd leidend element.
6e stap.
volgens de regels beschreven in stap 3. De procedure gaat door totdat er een optimale oplossing is gevonden of tot de conclusie komt dat deze niet bestaat.
Als tijdens de oplossingsoptimalisatie alle elementen in de leidende kolom niet-positief zijn, kan de leidende rij niet worden geselecteerd. In dit geval is de functie in het gebied van haalbare oplossingen voor het probleem niet begrensd boven en F max ->&∞. Als bij de volgende stap van het zoeken naar een extremum een van de basisvariabelen wordt gelijk aan nul , dan wordt de overeenkomstige basisoplossing gedegenereerd genoemd. In dit geval vindt er een zogenaamde cyclus plaats, gekenmerkt door het feit dat dezelfde combinatie van BP's zich met een bepaalde frequentie begint te herhalen (de waarde van de functie F blijft behouden) en het onmogelijk is om naar een nieuwe haalbare basisoplossing te gaan. . Looping is een van de belangrijkste nadelen van de simplexmethode, maar komt relatief zelden voor. In de praktijk weigeren ze in dergelijke gevallen gewoonlijk de variabele waarvan de kolom overeenkomt met de maximale absolute waarde van de negatieve coëfficiënt in de doelfunctie in de basis op te nemen, en produceren ze willekeurige selectie
nieuwe basisoplossing.
Voorbeeld 1. Los het probleem op
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Gebruik de simplexmethode en geef een geometrische interpretatie van het oplossingsproces.
We nemen de initiële variabelen x 1 en x 2 als niet-basisvariabelen, en beschouwen de extra x 3, x 4 en x 5 als basisvariabelen en stellen een simplextabel samen (simplextabel 2). De oplossing die overeenkomt met de simplextabel. 2, is niet geldig; het leidende element wordt geschetst en geselecteerd in overeenstemming met stap 2 van het vorige algoritme. De volgende simplextabel. 3 definieert een toelaatbare basisoplossing; het hoekpunt van de ODZP in figuur 1 komt ermee overeen. 2 Het leidende element wordt geschetst en geselecteerd in overeenstemming met de 5e stap van het probleemoplossende algoritme. Tafel 4 komt overeen met de optimale oplossing voor het probleem, dus: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; Fmax = 20.
Rijst. 2. Grafische oplossing taken
. Simplex-methode-algoritme
Voorbeeld 5.1. Los het volgende lineaire programmeerprobleem op met behulp van de simplexmethode:
Oplossing:
I iteratie:
x3, x4, x5, x6 x1,x2. Laten we de basisvariabelen uitdrukken in termen van vrije variabelen:
Laten we de doelfunctie reduceren tot volgende weergave:
Op basis van het verkregen probleem zullen we de initiële simplextabel vormen:
Tabel 5.3
Originele simplex tafel
Evaluatieve relaties |
||||
Volgens de definitie van de basisoplossing zijn de vrije variabelen gelijk aan nul en zijn de waarden van de basisvariabelen gelijk aan de overeenkomstige waarden van de vrije getallen, d.w.z.:
Fase 3: controle van de compatibiliteit van het PAP-beperkingssysteem.
Bij deze iteratie (in Tabel 5.3) wordt het teken van inconsistentie van het beperkingssysteem (teken 1) niet geïdentificeerd (d.w.z. er is geen lijn met een negatief vrij getal (behalve de lijn van de objectieve functie) waarin er geen lijn zou zijn met een negatief vrij getal (behalve de lijn van de objectieve functie). ten minste één negatief element zijn (d.w.z. negatieve coëfficiënt voor een vrije variabele)).
Bij deze iteratie (in Tabel 5.3) werd het teken van onbegrensdheid van de objectieve functie (teken 2) niet geïdentificeerd (dat wil zeggen, er is geen kolom met een negatief element in de rij van de objectieve functie (behalve de kolom met vrije getallen ) waarin er niet minstens één positief element zou zijn).
Omdat de gevonden basisoplossing geen negatieve componenten bevat, is deze toelaatbaar.
Fase 6: optimaliteitscontrole.
De gevonden basisoplossing is niet optimaal, aangezien er volgens het optimaliteitscriterium (teken 4) geen negatieve elementen in de lijn van de objectieve functie mogen voorkomen ( gratis nummer deze lijn wordt niet in aanmerking genomen bij het overwegen van dit kenmerk). Daarom gaan we, volgens het simplexmethode-algoritme, verder naar fase 8.
Omdat de gevonden basisoplossing toelaatbaar is, zullen we de oplossende kolom zoeken volgens het volgende schema: we bepalen de kolommen met negatieve elementen in de rij van de doelfunctie (behalve de kolom met vrije getallen). Volgens Tabel 5.3 zijn er twee van dergelijke kolommen: kolom “ x1" en kolom " x2" Uit dergelijke kolommen wordt degene geselecteerd die het kleinste element in de rij van de doelfunctie bevat. Zij zal de toegeeflijke zijn. Kolom " x2" bevat het kleinste element (–3) vergeleken met de kolom " x1
Om de oplossingslijn te bepalen, vinden we de positief geschatte verhoudingen van vrije getallen tot de elementen van de oplossingskolom; de lijn die overeenkomt met de kleinste positieve evaluatieverhouding wordt als opgelost geaccepteerd.
Tabel 5.4
Originele simplex tafel
In Tabel 5.4 komt het kleinste positieve evaluatieve verband overeen met de lijn “ x5"Daarom zal het tolerant zijn.
Het element dat zich op de kruising van de activeringskolom en de activeringsrij bevindt, wordt als activering geaccepteerd. In ons voorbeeld is dit het element dat zich op het snijpunt van de lijn “ x5"en kolommen" x2».
Het oplossende element toont één basisvariabele en één vrije variabele die in de simplextabel moeten worden verwisseld om naar een nieuwe “verbeterde” basisoplossing te gaan. In dit geval zijn dit variabelen x5 En x2, in de nieuwe simplextabel (tabel 5.5) wisselen we ze om.
9.1. Transformatie van het oplossende element.
Het resolutie-element van Tabel 5.4 wordt als volgt omgezet:
We voeren het resulterende resultaat in een soortgelijke cel in Tabel 5.5 in.
9.2. Resolutiereeksconversie.
We delen de elementen van de oplossende rij van tabel 5.4 door het oplossende element van deze simplextabel, de resultaten passen in vergelijkbare cellen van de nieuwe simplextabel (tabel 5.5). Transformaties van resolutiereekselementen worden gegeven in Tabel 5.5.
9.3. Conversie van de resolutiekolom.
We delen de elementen van de resolutiekolom van tabel 5.4 door het resolutie-element van deze simplextabel, en het resultaat wordt overgenomen uit tegenovergestelde teken. De verkregen resultaten passen in vergelijkbare cellen van de nieuwe simplextabel (Tabel 5.5). Transformaties van de elementen van de resolutiekolom worden gegeven in Tabel 5.5.
9.4. Transformatie van de resterende elementen van de simplextabel.
De transformatie van de overige elementen van de simplextabel (d.w.z. elementen die zich niet in de oplossingsrij en de oplossingskolom bevinden) wordt uitgevoerd volgens de "rechthoek"-regel.
Overweeg bijvoorbeeld om een element te transformeren dat zich op het snijpunt van de lijn bevindt " x3" en kolommen "", we zullen het voorwaardelijk aanduiden " x3" In Tabel 5.4 tekenen we mentaal een rechthoek, waarvan één hoekpunt zich in de cel bevindt waarvan we de waarde transformeren (d.w.z. in de cel “ x3"), en de andere (diagonaal hoekpunt) bevindt zich in een cel met een oplossend element. De andere twee hoekpunten (van de tweede diagonaal) zijn uniek bepaald. Vervolgens de getransformeerde waarde van de cel " x3" zal gelijk zijn aan de vorige waarde van deze cel minus de breuk, waarvan de noemer het oplossende element is (uit Tabel 5.4), en in de teller het product is van twee andere ongebruikte hoekpunten, d.w.z.:
« x3»: .
De waarden van andere cellen worden op dezelfde manier geconverteerd:
« x3 x1»: ;
« x4»: 
;
« x4x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Als resultaat van deze transformaties hebben we een nieuwe ontvangen simplex tafel(Tabel 5.5).
II iteratie:
Fase 1: een simplextabel opstellen.
Tabel 5.5
Simplex tafelII iteraties
Geschat relatie |
||||
| ||||
|
|
Fase 2: bepaling van de basisoplossing.
Als resultaat van de simplextransformaties werd een nieuwe basisoplossing verkregen (Tabel 5.5):
Zoals je kunt zien is bij deze basisoplossing de waarde van de doelfunctie = 15, wat groter is dan bij de vorige basisoplossing.
De inconsistentie van het systeem van beperkingen volgens kenmerk 1 in Tabel 5.5 is niet vastgesteld.
Fase 4: controle van de begrensdheid van de doelfunctie.
De onbegrensdheid van de doelfunctie volgens criterium 2 in Tabel 5.5 komt niet naar voren.
Fase 5: controle van de ontvankelijkheid van de gevonden basisoplossing.
De gevonden basisoplossing volgens criterium 4 is niet optimaal, aangezien de lijn van de doelfunctie van de simplextabel (Tabel 5.5) een negatief element bevat: –2 (het vrije getal van deze lijn wordt bij de beoordeling hiervan niet in aanmerking genomen). karakteristiek). Daarom gaan we door naar fase 8.
Fase 8: bepaling van het oplossende element.
8.1. Definitie van de resolutiekolom.
De gevonden basisoplossing is acceptabel; we bepalen de kolommen met negatieve elementen in de rij van de doelfunctie (behalve de kolom met vrije getallen). Volgens Tabel 5.5 is er slechts één zo’n kolom: “ x1" Daarom accepteren wij het als toegestaan.
8.2. Definitie van een enable-string.
Volgens de verkregen waarden van positieve evaluatieve relaties in Tabel 5.6 is het minimum de relatie die overeenkomt met de regel “ x3" Daarom accepteren wij het als toegestaan.
Tabel 5.6
Simplex tafelII iteraties
Geschat relatie |
||||
3/1=3 – min |
||||
Fase 9: transformatie van de simplextabel.
Transformaties van de simplextabel (Tabel 5.6) worden op dezelfde manier uitgevoerd als in de vorige iteratie. De resultaten van transformaties van elementen van de simplextabel worden gegeven in Tabel 5.7.
III iteratie
Gebaseerd op de resultaten van simplextransformaties van de vorige iteratie, stellen we een nieuwe simplextabel samen:
Tabel 5.7
Simplex tafelIII iteraties
Geschat relatie |
||||
| ||||
|
|
Fase 2: bepaling van de basisoplossing.
Als resultaat van de simplextransformaties werd een nieuwe basisoplossing verkregen (Tabel 5.7):
Fase 3: controle van de verenigbaarheid van het systeem van beperkingen.
De inconsistentie van het systeem van beperkingen volgens kenmerk 1 in Tabel 5.7 is niet vastgesteld.
Fase 4: controle van de begrensdheid van de doelfunctie.
De onbegrensdheid van de doelfunctie volgens criterium 2 in Tabel 5.7 komt niet naar voren.
Fase 5: controle van de ontvankelijkheid van de gevonden basisoplossing.
De gevonden basisoplossing volgens criterium 3 is acceptabel, omdat deze geen negatieve componenten bevat.
Fase 6: controle van de optimaliteit van de gevonden basisoplossing.
De gevonden basisoplossing volgens criterium 4 is niet optimaal, aangezien de lijn van de doelfunctie van de simplextabel (Tabel 5.7) een negatief element bevat: –3 (het vrije getal van deze lijn wordt bij de beoordeling hiervan niet in aanmerking genomen). karakteristiek). Daarom gaan we door naar fase 8.
Fase 8: bepaling van het oplossende element.
8.1. Definitie van de resolutiekolom.
De gevonden basisoplossing is acceptabel; we bepalen de kolommen met negatieve elementen in de rij van de doelfunctie (behalve de kolom met vrije getallen). Volgens Tabel 5.7 is er slechts één zo’n kolom: “ x5" Daarom accepteren wij het als toegestaan.
8.2. Definitie van een enable-string.
Volgens de verkregen waarden van positieve evaluatieve relaties in Tabel 5.8 is het minimum de relatie die overeenkomt met de regel “ x4" Daarom accepteren wij het als toegestaan.
Tabel 5.8
Simplex tafelIII iteraties
Geschat relatie |
||||
5/5=1 – min |
||||
Fase 9: transformatie van de simplextabel.
Transformaties van de simplextabel (Tabel 5.8) worden op dezelfde manier uitgevoerd als in de vorige iteratie. De resultaten van transformaties van elementen van de simplextabel worden gegeven in Tabel 5.9.
IV iteratie
Fase 1: constructie van een nieuwe simplextafel.
Gebaseerd op de resultaten van simplextransformaties van de vorige iteratie, stellen we een nieuwe simplextabel samen:
Tabel 5.9
Simplex tafelIV iteraties
Geschat relatie |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Fase 2: bepaling van de basisoplossing.
Als resultaat van de simplextransformaties werd een nieuwe basisoplossing verkregen volgens Tabel 5.9, de oplossing is als volgt:
Fase 3: controle van de verenigbaarheid van het systeem van beperkingen.
De inconsistentie van het systeem van beperkingen volgens kenmerk 1 in Tabel 5.9 is niet vastgesteld.
Fase 4: controle van de begrensdheid van de doelfunctie.
De onbegrensdheid van de doelfunctie volgens criterium 2 in Tabel 5.9 komt niet naar voren.
Fase 5: controle van de ontvankelijkheid van de gevonden basisoplossing.
De gevonden basisoplossing volgens criterium 3 is acceptabel, omdat deze geen negatieve componenten bevat.
Fase 6: controle van de optimaliteit van de gevonden basisoplossing.
De gevonden basisoplossing in overeenstemming met kenmerk 4 is optimaal, aangezien er geen negatieve elementen zijn in de lijn van de objectieve functie van de simplextabel (Tabel 5.9) (het vrije getal van deze lijn wordt niet in aanmerking genomen bij het overwegen van dit kenmerk) .
Fase 7: controleren of de oplossing alternatief is.
De gevonden oplossing is uniek, aangezien de lijn van de doelfunctie (Tabel 5.9) deze niet bevat nul elementen(bij het overwegen van dit kenmerk wordt geen rekening gehouden met het vrije nummer van deze lijn).
Antwoord: optimale waarde objectieve functie van het probleem in kwestie =24, wat wordt bereikt op.
Voorbeeld 5.2. Los het bovenstaande lineaire programmeerprobleem op, op voorwaarde dat objectieve functie wordt geminimaliseerd:
Oplossing:
I iteratie:
Fase 1: vorming van de initiële simplextabel.
Oorspronkelijk probleem lineaire programmering is gespecificeerd in standaard formulier. Laten we het in een canonieke vorm brengen door een extra niet-negatieve variabele in elk van de ongelijkheidsbeperkingen te introduceren, d.w.z.
In het resulterende stelsel van vergelijkingen nemen we als toegestane (basis)variabelen x3, x4, x5, x6, dan zullen de vrije variabelen zijn x1,x2. Laten we de basisvariabelen uitdrukken in termen van vrije variabelen.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | Daarom is bepaald welk element de basis zal vormen. Vervolgens tellen wij. | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| R1 x 1 = 0 x 2 = 0 S 1 = 0 |
S2 = 15 S3 = 4 R1 = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Daarom is bepaald welk element de basis zal vormen. Vervolgens tellen wij. | Stap 1 | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | St. lid | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W-1 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Stap 1 | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | W-0 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | W-0 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F-1 |
| F-13 S1 = 0 S2 = 0 |
x 1 = 3 x 2 = 4 S 3 = 6 |
