Als u een lineair programmeerprobleem moet oplossen met behulp van simplex-tabellen, dan zal onze online service u enorm helpen. De simplex-methode houdt een sequentiële opsomming in van alle hoekpunten van het bereik van acceptabele waarden om het hoekpunt te vinden waar de functie een extreme waarde aanneemt. In de eerste fase wordt een oplossing gevonden, die bij elke volgende stap verbetert. Een dergelijke oplossing wordt basis genoemd. Hier is een reeks acties bij het oplossen van een lineair programmeerprobleem met behulp van de simplex-methode:
Eerste stap. In de samengestelde tabel moet u allereerst naar de kolom met gratis leden kijken. Als het negatieve elementen bevat, moet u doorgaan naar de tweede stap, zo niet, dan naar de vijfde.
Tweede stap. Bij de tweede stap is het noodzakelijk om te beslissen welke variabele van de basis moet worden uitgesloten en welke moet worden opgenomen om de simplex-tabel opnieuw te berekenen. Hiervoor kijken we naar de kolom met gratis leden en vinden daarin een negatief element. Een regel met een negatief element wordt de leidende genoemd. Daarin vinden we het maximale negatieve element in absolute waarde, de kolom die ermee overeenkomt is de volger. Als er negatieve waarden zijn onder de gratis leden, maar niet in de bijbehorende rij, dan heeft zo'n tabel geen oplossingen. De variabele in de leidende rij, die in de kolom met vrije leden staat, wordt uitgesloten van de basis en de variabele die overeenkomt met de leidende kolom wordt opgenomen in de basis.
Tafel 1.
| basisvariabelen | Gratis leden met beperkingen | Niet-basisvariabelen | |||||
| x 1 | x2 | ... | x l | ... | x nee | ||
| xn+1 | b 1 | een 11 | een 12 | ... | een 1l | ... | een 1n |
| xn+2 | b 2 | een 21 | een 22 | ... | een 2l | ... | een 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | een r1 | een r2 | ... | een rl | ... | een rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | een m1 | een m2 | ... | een ml | ... | amn |
| F(x)max | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Derde stap. Bij de derde stap herberekenen we de hele simplex-tabel met behulp van speciale formules, deze formules kunnen worden bekeken met .
Vierde stap. Als er na herberekening negatieve elementen in de kolom met gratis leden blijven, ga dan naar de eerste stap, als er geen zijn, ga dan naar de vijfde.
Vijfde stap. Als je de vijfde stap hebt bereikt, dan heb je een oplossing gevonden die acceptabel is. Dit betekent echter niet dat het optimaal is. Het is alleen optimaal als alle elementen in de F-rij positief zijn. Als dit niet het geval is, dan is het noodzakelijk om de oplossing te verbeteren, waarvoor we de leidende rij en kolom vinden voor de volgende herberekening volgens het volgende algoritme. Aanvankelijk vinden we het minimale negatieve getal in rij F, exclusief de waarde van de functie. De kolom met dit nummer is de leidende. Om de leidende rij te vinden, vinden we de verhouding van het corresponderende vrije lid en het element uit de leidende kolom, op voorwaarde dat ze positief zijn. De minimale verhouding bepaalt de leidende lijn. We herberekenen de tabel volgens de formules, d.w.z. ga naar stap 3.
Een voorbeeld van het oplossen van het probleem met de simplex-methode wordt beschouwd, evenals een voorbeeld van het oplossen van het dubbele probleem.
De taak
Voor de implementatie van drie groepen goederen heeft een handelsonderneming drie soorten beperkte materiële en monetaire middelen ter grootte van b 1 = 240, b 2 = 200, b 3 = 160 eenheden. Tegelijkertijd, voor de verkoop van 1 groep goederen voor 1000 roebel. omzet, een hulpbron van het eerste type wordt verbruikt in de hoeveelheid van a 11 = 2 eenheden, een hulpbron van het tweede type in de hoeveelheid van a 21 = 4 eenheden, een hulpbron van het derde type in de hoeveelheid van a 31 = 4 eenheden. Voor de verkoop van 2 en 3 groepen goederen voor 1000 roebel. omzet wordt besteed, respectievelijk de bron van het eerste type in het bedrag van een 12 = 3, een 13 = 6 eenheden, de bron van het tweede type in het bedrag van een 22 = 2, een 23 = 4 eenheden, de bron van het derde type in de hoeveelheid van a 32 = 6, a 33 = 8 eenheden . Profiteer van de verkoop van drie groepen goederen voor duizend roebel. omzet is respectievelijk c 1 \u003d 4, c 2 \u003d 5, c 3 \u003d 4 (duizend roebel). Bepaal het geplande volume en de structuur van de handelsomzet zodat de winst van de handelsonderneming wordt gemaximaliseerd.
Op het directe probleem van de planning van de goederencirculatie, oplosbare simplex methode, componeren dubbel probleem lineair programmeren.
Installeren geconjugeerde paren van variabelen directe en dubbele problemen.
Volgens geconjugeerde paren van variabelen, uit de oplossing van het directe probleem, verkrijgen oplossing voor twee problemen, waarin schatting van de middelen besteed aan de verkoop van goederen.
Oplossing van het simplex-probleem door de methode
Laat x 1, x 2, x 3 - het aantal verkochte goederen, in duizend roebel, respectievelijk 1, 2, 3 groepen. Dan heeft het wiskundige model van het probleem de vorm:F = 4 x 1 + 5 x 2 + 4 x 3 ->max
0)))(~)" title="(!LANG:delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}
We lossen de simplex op met de methode.
We introduceren extra variabelen x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 om de ongelijkheden om te zetten in gelijkheden.
Als basis nemen we x 4 \u003d 240; x5 = 200; x6 = 160.
Gegevens worden ingevuld simplex tafel
Simplex tafel nummer 1
Doelfunctie:
0 240 + 0 200 + 0 160 = 0
We berekenen de scores volgens de formule:
Δ 1 \u003d 0 2 + 0 4 + 0 4 - 4 \u003d - 4
Δ 2 \u003d 0 3 + 0 2 + 0 6 - 5 \u003d - 5
Δ 3 \u003d 0 6 + 0 4 + 0 8 - 4 \u003d - 4
Δ 4 \u003d 0 1 + 0 0 + 0 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 0 0 - 0 \u003d 0
Δ 6 \u003d 0 0 + 0 0 + 0 1 - 0 \u003d 0
Omdat er negatieve schattingen zijn, is het plan niet optimaal. Laagste beoordeling:
We introduceren de variabele x 2 in de basis.
We definiëren een variabele die de basis verlaat. Om dit te doen, vinden we de kleinste niet-negatieve verhouding voor de kolom x 2 .
= 26.667
De kleinste niet-negatieve: Q 3 = 26,667. We leiden de variabele x 6 af van de basis
Verdeel lijn 3 door 6.
Trek van de 1e rij de 3e rij af vermenigvuldigd met 3
Trek van de 2e rij de 3e rij af vermenigvuldigd met 2
Wij berekenen:
We krijgen een nieuwe tabel:
Simplex tafel nummer 2
Doelfunctie:
0 160 + 0 440/3 + 5 80/3 = 400/3
We berekenen de scores volgens de formule:
Δ 1 \u003d 0 0 + 0 8/3 + 5 2/3 - 4 \u003d - 2/3
Δ 2 \u003d 0 0 + 0 0 + 5 1 - 5 \u003d 0
Δ 3 \u003d 0 2 + 0 4/3 + 5 4/3 - 4 \u003d 8/3
Δ 4 \u003d 0 1 + 0 0 + 5 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 5 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 \u003d 5/6
Aangezien er een negatieve schatting is Δ 1 = - 2/3, is het plan niet optimaal.
We introduceren de variabele x 1 in de basis.
We definiëren een variabele die de basis verlaat. Om dit te doen, vinden we de kleinste niet-negatieve verhouding voor kolom x 1 .
De kleinste niet-negatieve: Q 3 \u003d 40. We leiden de variabele x 2 af van de basis
Deel de 3e rij door 2/3.
Trek van de 2e rij de 3e rij af vermenigvuldigd met 8/3
Wij berekenen:
We krijgen een nieuwe tabel:
Simplex tafel nummer 3
Doelfunctie:
0 160 + 0 40 + 4 40 = 160
We berekenen de scores volgens de formule:
Δ 1 \u003d 0 0 + 0 0 + 4 1 - 4 \u003d 0
Δ 2 \u003d 0 0 + 0 (-4) + 4 3/2 - 5 \u003d 1
Δ 3 \u003d 0 2 + 0 (-4) + 4 2 - 4 \u003d 4
Δ 4 \u003d 0 1 + 0 0 + 4 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 4 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 \u003d 1
Aangezien er geen negatieve schattingen zijn, is het plan optimaal.
De oplossing van het probleem:
Antwoord
x1 = 40; x2 = 0; x 3 \u003d 0; x4 = 160; x5 = 40; x6 = 0; Fmax = 160Dat wil zeggen, het is noodzakelijk om goederen van het eerste type te verkopen voor een bedrag van 40 duizend roebel. Goederen van het 2e en 3e type hoeven niet te worden verkocht. In dit geval is de maximale winst F max = 160 duizend roebel.
Het dubbele probleem oplossen
Het dubbele probleem ziet er als volgt uit:
Z = 240 jaar 1 + 200 jaar 2 + 160 jaar 3 ->min
Title="(!LANG:delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}
We introduceren extra variabelen y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 om de ongelijkheden om te zetten in gelijkheden.
Geconjugeerde paren variabelen van de directe en dubbele problemen hebben de vorm:
Uit de laatste simplextabel nr. 3 van het directe probleem vinden we de oplossing van het dubbele probleem:
Zmin = Fmax = 160;
y 1 \u003d Δ 4 \u003d 0; y 2 \u003d Δ 5 \u003d 0; y 3 \u003d Δ 6 \u003d 1; y 4 \u003d Δ 1 \u003d 0; y 5 \u003d Δ 2 \u003d 1; y 6 \u003d Δ 3 \u003d 4;
Leuk gevonden? Bladwijzer
Problemen oplossen met de simplex-methode: voorbeelden online
Taak 1. Het bedrijf produceert badkamerplanken in twee maten, A en B. Verkoopagenten schatten dat er tot 550 planken per week op de markt kunnen worden verkocht. Elke plank van type A vereist 2 m2 materiaal en plank van type B vereist 3 m2 materiaal. Het bedrijf kan tot 1200 m2 materiaal per week ontvangen. Voor de vervaardiging van één schap van het type A zijn 12 minuten machinetijd nodig en voor de vervaardiging van één schap van het type B - 30 minuten; de machine is 160 uur per week inzetbaar. Als de winst uit de verkoop van planken van het type A 3 geldeenheden is, en van de planken van het type B - 4 den. eenheden, hoeveel planken van elk type moeten er per week worden geproduceerd?
Taak 2. Los een lineair programmeerprobleem op met behulp van de simplex-methode. 
Taak 3. Het bedrijf produceert 3 soorten producten: A1, A2, A3, met behulp van twee soorten grondstoffen. De kosten van grondstoffen van elk type per productie-eenheid, voorraden grondstoffen voor de geplande periode, evenals de winst per productie-eenheid van elk type zijn bekend.
- Hoeveel producten van elk type moeten worden geproduceerd om de winst te maximaliseren?
- Bepaal de status van elk type grondstof en de specifieke waarde ervan.
- Bepaal het maximale interval voor het wijzigen van de voorraden van elk type grondstof, waarbinnen de structuur van het optimale plan, d.w.z. release nomenclatuur zal niet veranderen.
- Bepaal de hoeveelheid output en de winst uit output wanneer de voorraad van een van de schaarse soorten grondstoffen wordt verhoogd tot de maximaal mogelijke waarde (binnen de gegeven nomenclatuur van output).
- Bepaal de intervallen van verandering in winst van een productie-eenheid van elk type, waarbij het resulterende optimale plan niet zal veranderen.
Taak 4. Los het lineaire programmeerprobleem op met behulp van de simplex-methode: 
Opdracht 5. Los het lineaire programmeerprobleem op met behulp van de simplex-methode: 
Taak 6. Los het probleem op met behulp van de simplex-methode, waarbij u als het oorspronkelijke referentieplan het plan in de voorwaarde beschouwt: 
Taak 7. Los het probleem op met de gewijzigde simplex-methode.
Voor de productie van twee soorten producten A en B worden drie soorten technologische apparatuur gebruikt. Voor de productie van een eenheid van product A wordt de uitrusting van het eerste type gebruikt a1=4 uur, de uitrusting van het tweede type is a2=8 uur en de uitrusting van het derde type is a3=9 uur. Voor de productie van een eenheid van product B wordt apparatuur van het eerste type gebruikt b1 = 7 uur, apparatuur van het tweede type b2 = 3 uur en apparatuur van het derde type b3 = 5 uur.
Voor de vervaardiging van deze producten mag apparatuur van het eerste type niet meer dan t1=49 uur werken, apparatuur van het tweede type niet meer dan t2=51 uur, apparatuur van het derde type niet meer dan t3=45 uur.
Winst uit de verkoop van een eenheid afgewerkt product A is ALPHA = 6 roebel en product B - BETTA = 5 roebel.
Stel een plan op voor de productie van producten A en B, zodat de maximale winst uit hun verkoop wordt gehaald.
Taak 8. Vind de optimale oplossing met de dual simplex-methode 
| - | x 1 | + | x2 | - | S1 | = | 1 | ||||||||||
| x 1 | +3 | x2 | + | S2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x2 | + | S3 | = | 4 |
| - | x 1 | + | x2 | - | S1 | + | R1 | = | 1 | |||||||||||
| x 1 | +3 | x2 | + | S2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x2 | + | S3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=>W=1 |
| x 1 | x2 | S1 | S2 | S3 | R1 | St. lid | Θ |
| -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 | W - 1 | |
| -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 - 0 |
| - | x 1 | + | x2 | - | S1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S1 | + | S2 | = | 12 | |||||||||
| - | x 1 | + | S1 | + | S3 | = | 3 |
| x 1 | x2 | S1 | S2 | S3 | St. lid | Θ |
| -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 | F-1 | |
| -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 | F-1 | |
| 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-13 |
| S1 = 0 S2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
. Simplex Methode Algoritme
Voorbeeld 5.1. Los het volgende lineaire programmeerprobleem op met behulp van de simplex-methode:
Oplossing:
l iteratie:
x3, x4, x5, x6 x1,x2. We drukken de basisvariabelen uit in termen van de vrije:
We brengen de objectieve functie in de volgende vorm:
Op basis van het verkregen probleem zullen we de eerste simplex-tabel vormen:
Tabel 5.3
Eerste simplex-tabel
geschatte 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: controleren van de verenigbaarheid van het systeem van beperkingen van het LLP.
Bij deze iteratie (in tabel 5.3) werd het teken van inconsistentie van het beperkingssysteem (kenmerk 1) niet onthuld (dwz er is geen regel met een negatief vrij getal (behalve de objectieve functieregel) die niet ten minste één negatief element (dwz .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 onthuld (dwz er is geen kolom met een negatief element in de lijn van de objectieve functie (behalve de kolom met vrije getallen) waarin er ten minste één positief element zou zijn).
Aangezien de gevonden basisoplossing geen negatieve componenten bevat, is deze toelaatbaar.
Fase 6: optimaliteitscontrole.
De gevonden basisoplossing is niet optimaal, aangezien er volgens het criterium van optimaliteit (teken 4) geen negatieve elementen in de lijn van de doelfunctie mogen voorkomen (het vrije getal van deze lijn wordt niet in aanmerking genomen bij het beschouwen van dit teken ). Daarom gaan we, volgens het algoritme van de simplex-methode, naar de 8e fase.
Aangezien de gevonden basisoplossing toelaatbaar is, zoeken we de oplossende kolom volgens het volgende schema: we bepalen de kolommen met negatieve elementen in de regel van de doelfunctie (behalve de kolom met vrije getallen). Volgens tabel 5.3 zijn er twee van dergelijke kolommen: de kolom " x1" en kolom " x2". Uit dergelijke kolommen wordt degene geselecteerd die het kleinste element in de regel van de doelfunctie bevat. Ze zal oplossen. Kolom " x2' bevat het kleinste element (-3) vergeleken met de kolom ' x1
Om de permissieve string te bepalen, vinden we de positief geschatte verhoudingen van vrije getallen tot de elementen van de permissieve kolom, de string, die overeenkomt met de kleinste positief geschatte verhouding, wordt geaccepteerd als toegestaan.
Tabel 5.4
Eerste simplex-tabel
In tabel 5.4 komt de kleinste positieve evaluatieratio overeen met de regel " x5', daarom zal het oplossen.
Het element dat zich op het snijpunt van de activeringskolom en de activeringslijn bevindt, wordt als activerend geaccepteerd. In ons voorbeeld is dit het element dat zich op het snijpunt van de lijn bevindt " x5» en kolommen « x2».
Het oplossende element toont één basis- en één vrije variabele die in de simplex-tabel moet worden verwisseld om naar de nieuwe "verbeterde" basisoplossing te gaan. In dit geval zijn dit variabelen. x5 En x2, in de nieuwe simplex-tabel (tabel 5.5) wisselen we ze om.
9.1. Sta elementtransformatie toe.
Het permissieve element van tabel 5.4 wordt als volgt getransformeerd:
Het resultaat dat we in een vergelijkbare cel hebben verkregen, voeren we in tabel 5.5 in.
9.2. Tekenreeksconversie toestaan.
De elementen van de permissieve regel van tabel 5.4 worden gedeeld door het permissieve element van deze simplextabel, de resultaten passen in vergelijkbare cellen van de nieuwe simplextabel (tabel 5.5). De transformaties van de elementen van de enable-string worden gegeven in Tabel 5.5.
9.3. Permissieve kolomtransformatie.
De elementen van de oplossende kolom van tabel 5.4 worden gedeeld door het oplossende element van deze simplextabel, en het resultaat wordt genomen met het tegenovergestelde teken. De verkregen resultaten passen in vergelijkbare cellen van de nieuwe simplex-tabel (tabellen 5.5). Transformaties van elementen van de oplossende kolom worden gegeven in Tabel 5.5.
9.4. Transformatie van de overige elementen van de simplex-tabel.
De transformatie van andere elementen van de simplex-tabel (d.w.z. elementen die zich niet in de oplossende rij en de oplossende kolom bevinden) wordt uitgevoerd volgens de "rechthoek" -regel.
Beschouw bijvoorbeeld de transformatie van een element dat zich op de kruising van de string bevindt " x3” en kolommen “”, geven het voorwaardelijk aan als “ x3". In tabel 5.4 tekenen we mentaal een rechthoek, waarvan één hoekpunt zich in de cel bevindt, waarvan de waarde wordt getransformeerd (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. Dan de getransformeerde waarde van de cel " x3"is gelijk aan de vorige waarde van deze cel minus een breuk, waarvan de noemer het oplossende element is (uit tabel 5.4), en in de teller het product van twee andere ongebruikte hoekpunten, d.w.z.:
« x3»: .
De waarden van andere cellen worden op dezelfde manier geconverteerd:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Als resultaat van deze transformaties werd een nieuwe simplextabel verkregen (tabel 5.5).
II iteratie:
Fase 1: het samenstellen van een simplex-tabel.
Tabel 5.5
Simplex tafelII iteraties
Geschatte relaties |
||||
| ||||
|
|
Stap 2: bepaling van de basisoplossing.
Als resultaat van de simplex-transformaties werd een nieuwe basisoplossing verkregen (tabel 5.5):
Zoals je kunt zien, is met deze basisoplossing de waarde van de doelfunctie =15, wat meer is dan bij de vorige basisoplossing.
Inconsistentie van het stelsel van beperkingen volgens teken 1 in tabel 5.5 is niet geconstateerd.
Fase 4: controle van de begrensdheid van de doelfunctie.
De onbegrensdheid van de objectieve functie volgens teken 2 in tabel 5.5 werd niet onthuld.
Stap 5: toetsing van de ontvankelijkheid van de gevonden basisoplossing.
De gevonden basisoplossing volgens kenmerk 4 is niet optimaal, aangezien de regel van de objectieve functie van de simplextabel (Tabel 5.5) een negatief element bevat: -2 (het vrije getal van deze regel wordt hierbij buiten beschouwing gelaten voorzien zijn van). Dus laten we verder gaan met stap 8.
Fase 8: definitie van het activerende element.
8.1. Definitie van een resolutiekolom.
De gevonden basisoplossing is toelaatbaar, we bepalen de kolommen met negatieve elementen in de lijn van de doelfunctie (behalve de kolom met vrije getallen). Volgens tabel 5.5 is er maar één zo'n kolom: " x1". Daarom accepteren we het zoals toegestaan.
8.2. Permissieve tekenreeksdefinitie.
Volgens de verkregen waarden van positief geschatte verhoudingen in tabel 5.6, is het minimum de verhouding die overeenkomt met de regel " x3". Daarom accepteren we het zoals toegestaan.
Tabel 5.6
Simplex tafelII iteraties
Geschatte relaties |
||||
3/1=3 – min |
||||
Fase 9: transformatie van de simplex-tabel.
De transformaties van de simplex-tabel (Tabel 5.6) worden op dezelfde manier uitgevoerd als in de vorige iteratie. De resultaten van transformaties van elementen van de simplextabel zijn weergegeven in tabel 5.7.
III iteratie
Op basis van de resultaten van de simplex-transformaties van de vorige iteratie, stellen we een nieuwe simplex-tabel samen:
Tabel 5.7
Simplex tafelIII iteraties
Geschatte relaties |
||||
| ||||
|
|
Stap 2: bepaling van de basisoplossing.
Als resultaat van de simplex-transformaties werd een nieuwe basisoplossing verkregen (tabel 5.7):
Fase 3: controle van de compatibiliteit van het systeem van beperkingen.
Inconsistentie van het stelsel van beperkingen volgens teken 1 in tabel 5.7 is niet geconstateerd.
Fase 4: controle van de begrensdheid van de doelfunctie.
De onbegrensdheid van de objectieve functie volgens teken 2 in tabel 5.7 werd niet onthuld.
Stap 5: toetsing van de ontvankelijkheid van de gevonden basisoplossing.
De gevonden basisoplossing volgens criterium 3 is toelaatbaar, aangezien deze geen negatieve componenten bevat.
Stap 6: het controleren van de optimaliteit van de gevonden basisoplossing.
De gevonden basisoplossing volgens kenmerk 4 is niet optimaal, aangezien de regel van de objectieve functie van de simplextabel (Tabel 5.7) een negatief element bevat: -3 (het vrije getal van deze regel wordt hierbij niet meegerekend voorzien zijn van). Dus laten we verder gaan met stap 8.
Fase 8: definitie van het activerende element.
8.1. Definitie van een resolutiekolom.
De gevonden basisoplossing is toelaatbaar, we bepalen de kolommen met negatieve elementen in de lijn van de doelfunctie (behalve de kolom met vrije getallen). Volgens tabel 5.7 is er maar één zo'n kolom: " x5". Daarom accepteren we het zoals toegestaan.
8.2. Permissieve tekenreeksdefinitie.
Volgens de verkregen waarden van positief geschatte verhoudingen in tabel 5.8, is het minimum de verhouding die overeenkomt met de regel " x4". Daarom accepteren we het zoals toegestaan.
Tabel 5.8
Simplex tafelIII iteraties
Geschatte relaties |
||||
5/5=1 – min |
||||
Fase 9: transformatie van de simplex-tabel.
De transformaties van de simplex-tabel (tabel 5.8) worden op dezelfde manier uitgevoerd als in de vorige iteratie. De resultaten van transformaties van de elementen van de simplextabel zijn weergegeven in Tabel 5.9.
IV iteratie
Fase 1: constructie van een nieuwe simplex tafel.
Op basis van de resultaten van de simplex-transformaties van de vorige iteratie, stellen we een nieuwe simplex-tabel samen:
Tabel 5.9
Simplex tafelIV iteraties
Geschatte relaties |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Stap 2: bepaling van de basisoplossing.
Als resultaat van de simplex-transformaties werd een nieuwe basisoplossing verkregen, volgens tabel 5.9 is de oplossing als volgt:
Fase 3: controle van de compatibiliteit van het systeem van beperkingen.
Inconsistentie van het stelsel van beperkingen volgens kenmerk 1 in tabel 5.9 is niet aan het licht gekomen.
Fase 4: controle van de begrensdheid van de doelfunctie.
De onbegrensdheid van de objectieve functie volgens teken 2 in tabel 5.9 werd niet onthuld.
Stap 5: toetsing van de ontvankelijkheid van de gevonden basisoplossing.
De gevonden basisoplossing volgens criterium 3 is toelaatbaar, aangezien deze geen negatieve componenten bevat.
Stap 6: het controleren van de optimaliteit van de gevonden basisoplossing.
De basisoplossing gevonden in overeenstemming met kenmerk 4 is optimaal, aangezien er geen negatieve elementen in de rij van de objectieve functie van de simplex-tabel zijn (tabel 5.9) (het vrije nummer van deze rij wordt niet in aanmerking genomen bij het overwegen van dit kenmerk) .
Stap 7: het controleren van de alternatieve oplossing.
De gevonden oplossing is de enige, aangezien er geen nul-elementen in de regel van de doelfunctie zijn (Tabel 5.9) (het vrije getal van deze regel wordt niet in aanmerking genomen bij het beschouwen van dit kenmerk).
Antwoord: de optimale waarde van de objectieve functie van het beschouwde probleem =24, die wordt bereikt bij.
Voorbeeld 5.2. Los het bovenstaande lineaire programmeerprobleem op, ervan uitgaande dat de doelfunctie is geminimaliseerd:
Oplossing:
l iteratie:
Fase 1: vorming van de eerste simplex-tabel.
Het oorspronkelijke lineaire programmeerprobleem wordt in standaardvorm gegeven. Laten we het naar de canonieke vorm brengen door een extra niet-negatieve variabele in elk van de ongelijkheidsbeperkingen te introduceren, d.w.z.
In het resulterende systeem van vergelijkingen nemen we als toegestane (basis)variabelen x3, x4, x5, x6, dan zijn de vrije variabelen x1,x2. We drukken de basisvariabelen uit in termen van de vrije.
