Stap 0. Voorbereidende fase.
We reduceren het LP-probleem tot een speciale vorm (15).
Stap 1. Compileren simplex tafel, overeenkomend met het speciale formulier:
|
|
|
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
Merk op dat deze tabel overeenkomt met een toelaatbare basisoplossing 
problemen (15). De waarde van de objectieve functie voor deze oplossing 
Stap 2. Optimaliteitscontrole
Als er onder de elementen van de indexrij simplextabellen zijn 
er is dan geen enkel positief element 
, is de optimale oplossing voor het LP-probleem gevonden: Het algoritme eindigt.
Stap 3. Controle van de onbeslisbaarheid
Als tussen 
er zit een positief element in 
en in de bijbehorende kolom 
er is geen enkel positief element 
, dan de objectieve functie L is van onderaf onbegrensd op de toelaatbare set. In dit geval bestaat er geen optimale oplossing. Het algoritme eindigt.
Stap 4. Een leidende kolom selecteren Q
Tussen de elementen 
kies het maximale positieve element 
.We verklaren dat deze kolom de leidende (toegeeflijke) kolom is.
Stap 5. Selectie van leadlijnen P
Een van de positieve elementen van de column 
vind het element 
, waarvoor de gelijkheid geldt
.
Snaar P Wij verklaren dat dit leidend is (vergunning). Element 
Wij verklaren dat het de leider is (toestaat).
Stap 6. Simplex tabelconversie
We maken een nieuwe simplextabel waarin:
a) in plaats van de basisvariabele 
schrijf op 
, in plaats van een niet-basisvariabele 
schrijf op 
;
b) het leidende element wordt vervangen door de inverse waarde 
;
c) alle elementen van de leidende kolom (behalve 
) vermenigvuldigen met 
;
d) alle elementen van de leidende lijn (behalve 
) vermenigvuldigen met 
;
e) de overige elementen van de simplextabel worden getransformeerd volgens het volgende "rechthoek"-schema.
Het product van drie factoren wordt afgetrokken van het element:
de eerste is het overeenkomstige element van de leidende kolom;
de tweede is het overeenkomstige element van de leidende lijn;
de derde is het omgekeerde van het leidende element 
.
Het getransformeerde element en de drie ermee corresponderende factoren zijn precies de hoekpunten van de “rechthoek”.
Stap 7 De overgang naar de volgende iteratie wordt uitgevoerd door terug te keren naar stap 2.
2.3. Simplex-methode-algoritme voor het maximale probleem
Het simplexmethode-algoritme voor het maximale probleem verschilt alleen van het algoritme voor het minimale probleem in de tekens van de indexlijn van de coëfficiënten in de objectieve functie 
, namelijk:
In stap 2:
:
Bij stap 3
. De objectieve functie is van bovenaf onbegrensd op de toelaatbare verzameling.
Bij stap 4:
.
2.4. Een voorbeeld van het oplossen van een probleem met behulp van de simplexmethode
Los het probleem op dat in de vorm (15) is geschreven.
Laten we een simplextabel maken:
|
|
|
|
|
|
| |||
|
|
|
Omdat de coëfficiënten van de lijn van de objectieve functie niet-negatief zijn, is de initiële basisoplossing niet optimaal. De waarde van de doelfunctie voor deze basis L=0.
Selecteer de leidende kolom - dit is de kolom die overeenkomt met de variabele 
.
Selecteer de leidende lijn. Om dit te doen vinden we 
. Daarom komt de leidende lijn overeen met de variabele 
.
We transformeren de simplextabel door een variabele te introduceren 
in de basis en voert de variabele uit 
vanuit de basis. We krijgen de tabel:
|
|
|
|
|
|
|
| ||
|
|
|
Eén iteratie van de methode is voltooid. Laten we verder gaan met een nieuwe iteratie. De resulterende tabel is niet optimaal. De basisoplossing die overeenkomt met de tabel heeft de vorm . De waarde van de objectieve functie op deze basis L= -2.
De leidende kolom hier is de kolom die overeenkomt met de variabele 
. Leading line – de lijn die overeenkomt met de variabele 
. Na het uitvoeren van de transformaties verkrijgen we een simplextabel:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Weer een iteratie voltooid. Laten we verder gaan met een nieuwe iteratie.
De lijn van de doelfunctie bevat geen positieve waarden, wat betekent dat de overeenkomstige basisoplossing optimaal is en dat het algoritme eindigt.
Dubbele simplex-methode is gebaseerd op de theorie van dualiteit (zie oplossing van het duale probleem) en wordt gebruikt om lineaire programmeerproblemen op te lossen, waarvan de vrije termen b i elke waarde kunnen aannemen, en het systeem van beperkingen wordt gespecificeerd door ongelijkheden in de betekenis “≤”, “≥” of de gelijkheid “=”.Doel van de dienst. Online rekenmachine die wordt gebruikt om lineaire programmeerproblemen op te lossen P-methode in de volgende registratievormen: de basisregistratievorm van de simplexmethode, in de vorm van een simplextabel, in de gewijzigde simplexmethode.
Instructies voor het oplossen van problemen dubbele simplex-methode. Selecteer het aantal variabelen en het aantal rijen (aantal beperkingen), klik op Volgende. De resulterende oplossing wordt opgeslagen in een Word-bestand (zie voorbeeld van een oplossing met behulp van de dual simplex-methode).
Tegelijkertijd zijn er beperkingen zoals x ik ≥ 0 hou er geen rekening mee.Het volgende wordt ook gebruikt met deze rekenmachine:
Grafische methode voor het oplossen van ZLP
Oplossing van het transportprobleem
Een matrixspel oplossen
Met behulp van de online service kunt u de prijs van een matrixspel bepalen (onder- en bovengrens), controleren op de aanwezigheid van een zadelpunt, een oplossing vinden voor een gemengde strategie met behulp van de volgende methoden: minimax, simplex-methode, grafisch (geometrisch ) methode, Brown's methode.
Extremum van een functie van twee variabelen
Dynamische programmeerproblemen
Verdeel 5 homogene partijen goederen over drie markten om een maximaal inkomen uit de verkoop ervan te verkrijgen. De inkomsten uit verkopen in elke markt G(X) zijn afhankelijk van het aantal verkochte partijen van product X en worden weergegeven in de tabel.
| Productvolume X (in partijen) | Inkomen G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Bij de P-methode wordt het optimale plan verkregen door langs pseudoplannen te bewegen. Pseudovlak- een plan waarin aan de optimaliteitsvoorwaarden is voldaan, en onder de waarden van de basisvariabelen x i bevinden zich negatieve getallen. Algoritme voor de dual simplex-methode omvat de volgende stappen:
- Het opstellen van een pseudo-plan. Het systeem van beperkingen van het oorspronkelijke probleem leidt tot een systeem van ongelijkheden met de betekenis “≤”.
- Het controleren van het plan op optimaliteit. Als in het resulterende referentieplan niet aan de optimaliteitsvoorwaarde wordt voldaan, wordt het probleem opgelost met behulp van de simplexmethode.
- Eerste rij en kolom selecteren. Van de negatieve waarden van de basisvariabelen worden de grootste in absolute waarde geselecteerd. De lijn die met deze waarde correspondeert, is de leidende.
- Berekening van een nieuw referentieplan. Het nieuwe plan wordt verkregen door de simplextabel opnieuw te berekenen met behulp van de Jordan-Gauss-methode. Ga vervolgens verder met fase 2.
Voorbeeld. De onderneming moet A1-eenheden, A2-eenheden en A3-eenheden produceren volgens het productieplan. Elk type product kan op twee machines worden geproduceerd.
Hoe kan het werk van machines worden verdeeld, zodat de totale tijd die aan het uitvoeren van het plan wordt besteed minimaal is? De kostenmatrix en de tijdbron van elke machine worden gegeven. Schrijf het model van de onderzochte operatie op in een vorm die het gebruik van de P-methode mogelijk maakt.
Het is bekend dat het gehalte aan n voedingsstoffen A, B en C in de voeding minimaal respectievelijk m1, m2 en m3 eenheden moet zijn. Drie soorten voedsel bevatten deze voedingsstoffen. Het gehalte aan voedingseenheden in één kilogram van elk type product wordt weergegeven in de tabel. Bepaal een dagelijks dieet dat de benodigde hoeveelheid voedingsstoffen levert tegen minimale kosten.
Taak: Los het probleem op met behulp van het dual-simplex-methode-algoritme.
Laten we het systeem van beperkingen reduceren tot het systeem van betekenisongelijkheid ≤ door de overeenkomstige regels te vermenigvuldigen met (-1).
Laten we de minimumwaarde van de objectieve functie F(X) = 4x 1 + 2x 2 + x 3 bepalen onder de volgende beperkingsvoorwaarden.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Om het eerste referentieplan te construeren, reduceren we het systeem van ongelijkheden tot een systeem van vergelijkingen door aanvullende variabelen te introduceren (overgang naar de canonieke vorm).
In de eerste betekenisongelijkheid (≤) introduceren we de basisvariabele x 4 . In de tweede betekenisongelijkheid (≤) introduceren we de basisvariabele x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
De coëfficiëntenmatrix A = a(ij) van dit stelsel vergelijkingen heeft de vorm:
| EEN= |
|
x4, x5,
Ervan uitgaande dat de vrije variabelen gelijk zijn aan nul, verkrijgen we het eerste referentieontwerp:
X1 = (0,0,0,-10,8)
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Iteratie #1
Plan 0 in een simplextabel is een pseudo-plan, dus we bepalen de leidende rij en kolom.
De leidende lijn is de eerste lijn en de variabele x 4 moet worden afgeleid van de basis.
3. Definitie van een nieuwe basisvariabele. De minimumwaarde van θ komt overeen met de 2e kolom, d.w.z. de variabele x 2 moet in de basis worden ingevoerd.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Herberekening van de simplextabel. We voeren transformaties van de simplextabel uit met behulp van de Jordano-Gauss-methode.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Laten we de berekening van elk element in de vorm van een tabel weergeven:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Iteratie #2
1. Controle van het optimaliteitscriterium.
Plan 1 in een simplextabel is een pseudo-plan, dus we bepalen de leidende rij en kolom.
2. Definitie van een nieuwe vrije variabele.
Onder de negatieve waarden van de basisvariabelen selecteren we de grootste in absolute waarde.
De tweede regel is leidend en de variabele x 5 moet worden afgeleid van de basis.
3. Definitie van een nieuwe basisvariabele. De minimumwaarde van θ komt overeen met de derde kolom, d.w.z. de variabele x 3 moet in de basis worden ingevoerd.
Op het snijpunt van de leidende rij en kolom bevindt zich een oplossend element (RE) gelijk aan (-1).
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Herberekening van de simplextabel. Wij voeren transformaties uit.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
In de basiskolom zijn alle elementen positief. Laten we verder gaan met het hoofdalgoritme van de simplexmethode.
Iteratie #3
1. Controle van het optimaliteitscriterium.
Er zijn geen positieve waarden onder de indextekenreekswaarden. Daarom bepaalt deze tabel het optimale plan voor het probleem.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Het optimale plan kan als volgt worden geschreven: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
Een van de methoden voor het oplossen van optimalisatieproblemen ( meestal geassocieerd met het vinden van het minimum of maximum) lineaire programmering wordt genoemd. Simplex-methode omvat een hele groep algoritmen en methoden voor het oplossen van lineaire programmeerproblemen. Een van deze methoden, waarbij de brongegevens worden vastgelegd en opnieuw worden berekend in een speciale tabel, wordt genoemd tabellarische simplexmethode.
Laten we het algoritme van de tabellarische simplex-methode bekijken met behulp van het voorbeeld van de oplossing productie taak, wat neerkomt op het vinden van een productieplan dat maximale winst garandeert.
Invoergegevens voor het simplexmethodeprobleem
Het bedrijf produceert 4 soorten producten en verwerkt deze op 3 machines.
Tijdnormen (min./stuk) voor het verwerken van producten op machines worden gespecificeerd door matrix A:
Het machinelooptijdfonds (min.) wordt gespecificeerd in matrix B:
De winst uit de verkoop van elke eenheid product (RUB/stuk) wordt gegeven door matrix C:
Doel van de productietaak
Stel een productieplan op dat de winst van de onderneming maximaliseert.
Het probleem oplossen met behulp van de tabellaire simplexmethode
(1) Laten we met X1, X2, X3, X4 het geplande aantal producten van elk type aangeven. Dan het gewenste plan: ( X1, X2, X3, X4)
(2) Laten we de planbeperkingen opschrijven in de vorm van een systeem van vergelijkingen:
(3) De beoogde winst is dan:
Dat wil zeggen dat de winst uit het vervullen van het productieplan maximaal moet zijn.
(4) Om het resulterende conditionele extremumprobleem op te lossen, vervangen we het systeem van ongelijkheden door een systeem van lineaire vergelijkingen door er aanvullende niet-negatieve variabelen in te introduceren ( X5, X6, X7).
(5) Laten we het volgende accepteren referentieplan:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Laten we de gegevens invoeren simplex tafel:
In de laatste regel voeren we de coëfficiënten van de objectieve functie en de waarde ervan zelf in met het tegenovergestelde teken;
(7) Selecteer op de laatste regel grootste (modulair) is een negatief getal.
Laten we berekenen b = N / Items_van_de_geselecteerde_kolom
Onder de berekende waarden van b kiezen we minst.
Het snijpunt van de geselecteerde kolom en rij geeft ons het oplossende element. We veranderen de basis in een variabele die overeenkomt met het oplossende element ( X5 tot X1).
- Het oplossende element zelf wordt 1.
- Voor elementen van de resolutielijn – a ij (*) = a ij / RE ( dat wil zeggen, we delen elk element door de waarde van het oplossende element en verkrijgen nieuwe gegevens).
- Voor elementen van de resolutiekolom worden deze eenvoudigweg op nul gezet.
- We herberekenen de resterende elementen van de tabel met behulp van de rechthoekregel.
a ij (*) = a ij – (A * B / RE)
Zoals u kunt zien, nemen we de huidige cel die opnieuw wordt berekend en de cel met het oplossende element. Ze vormen tegenoverliggende hoeken van de rechthoek. Vervolgens vermenigvuldigen we de waarden uit de cellen van de andere 2 hoeken van deze rechthoek. Dit werk ( A * B) delen door het oplossende element ( MET BETREKKING TOT). En trek af van de huidige cel die opnieuw wordt berekend ( een IJ) wat is er gebeurd. We krijgen een nieuwe waarde - een ij (*).
(9) Controleer de laatste regel opnieuw ( C) op aanwezigheid van negatieve getallen. Als ze er niet zijn, is het optimale plan gevonden; we gaan door naar de laatste fase van het oplossen van het probleem. Als dat zo is, is het plan nog niet optimaal en moet de simplextabel opnieuw worden berekend.
Omdat we opnieuw negatieve getallen in de laatste regel hebben, beginnen we met een nieuwe iteratie van berekeningen.
(10) Omdat er in de laatste regel geen negatieve elementen voorkomen, betekent dit dat we het optimale productieplan hebben gevonden! Namelijk: we zullen die producten produceren die naar de kolom "Basis" zijn verplaatst - X1 en X2. We kennen de winst uit de productie van elke eenheid output ( matrix C). Het blijft nodig om de gevonden productievolumes van producten 1 en 2 te vermenigvuldigen met de winst per 1 stuk, we krijgen de finale ( maximaal! ) winst voor een bepaald productieplan.
ANTWOORD:
X1 = 32 stuks, X2 = 20 stuks, X3 = 0 stuks, X4 = 0 stuks
P = 48 * 32 + 33 * 20 = 2.196 wrijven.
Galjautdinov R.R.
© Het kopiëren van materiaal is alleen toegestaan als er een directe hyperlink naar is
. 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 objectieve functie terugbrengen tot de volgende vorm:
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). minstens éé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 (het vrije getal van deze lijn wordt niet in aanmerking genomen bij het overwegen van dit criterium). 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 genomen met het 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 werd een nieuwe simplextabel verkregen (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, omdat er geen negatieve elementen zijn in de lijn van de objectieve functie van de simplextabel (Tabel 5.9) (het vrije nummer 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 er geen nulelementen in de lijn van de doelfunctie voorkomen (Tabel 5.9) (het vrije getal van deze lijn 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, op voorwaarde dat de doelfunctie wordt geminimaliseerd:
Oplossing:
I iteratie:
Fase 1: vorming van de initiële simplextabel.
Het oorspronkelijke lineaire programmeerprobleem wordt in standaardvorm gegeven. 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.
Laten we eens overwegen simplex methode voor het oplossen van lineaire programmeerproblemen (LP). Het is gebaseerd op de overgang van het ene referentieplan naar het andere, waarbij de waarde van de doelfunctie toeneemt.
Het simplexmethode-algoritme is als volgt:
- We transformeren het oorspronkelijke probleem in een canonieke vorm door aanvullende variabelen te introduceren. Voor ongelijkheden van de vorm ≤ worden aanvullende variabelen geïntroduceerd met een teken (+), maar als ze de vorm ≥ hebben, dan met een teken (-). Extra variabelen worden in de doelfunctie geïntroduceerd met overeenkomstige tekens met een coëfficiënt gelijk aan 0 , omdat de doelfunctie mag de economische betekenis ervan niet veranderen.
- Vectoren zijn uitgeschreven P ik uit de coëfficiënten van de variabelen en de kolom met vrije termen. Deze actie bepaalt het aantal eenheidsvectoren. De regel is dat er net zoveel eenheidsvectoren moeten zijn als er ongelijkheden zijn in het systeem van beperkingen.
- Hierna worden de brongegevens in een simplextabel ingevoerd. Eenheidsvectoren worden in de basis geïntroduceerd en door ze uit de basis uit te sluiten, wordt de optimale oplossing gevonden. De coëfficiënten van de doelfunctie worden met het tegenovergestelde teken geschreven.
- Een optimaliteitsteken voor een LP-probleem is dat de oplossing optimaal is als deze aanwezig is F– in de rij zijn alle coëfficiënten positief. Regel voor het vinden van de activeringskolom - bekeken F– een string en uit de negatieve elementen wordt de kleinste geselecteerd. Vector P ik het bevatten ervan wordt tolerant. De regel voor het selecteren van een oplossend element - de verhoudingen van de positieve elementen van de oplossende kolom tot de elementen van de vector worden samengesteld P0 en het getal dat de kleinste verhouding oplevert, wordt het oplossende element ten opzichte waarvan de simplextabel opnieuw zal worden berekend. De regel die dit element bevat, wordt de enable-regel genoemd. Als er geen positieve elementen in de resolutiekolom staan, heeft het probleem geen oplossing. Nadat ze het oplossende element hebben bepaald, gaan ze over tot de herberekening van een nieuwe simplextabel.
- Regels voor het invullen van een nieuwe simplextabel. Eenheid wordt in plaats van het oplossende element geplaatst en er wordt aangenomen dat andere elementen gelijk zijn 0 . De oplossende vector wordt toegevoegd aan de basis, waarvan de overeenkomstige nulvector wordt uitgesloten, en de resterende basisvectoren worden zonder wijzigingen geschreven. De elementen van de resolutiereeks worden gedeeld door het resolutie-element, en de overige elementen worden opnieuw berekend volgens de rechthoekregel.
- Dit wordt gedaan tot F– alle elementen van de string worden niet positief.
Laten we overwegen het probleem op te lossen met behulp van het hierboven besproken algoritme.
Gegeven:
We brengen het probleem naar een canonieke vorm:
We stellen de vectoren samen:
Vul de simplextabel in:
:
Laten we het eerste element van de vector opnieuw berekenen P0, waarvoor we een rechthoek van getallen maken: en we krijgen: 
.
We voeren soortgelijke berekeningen uit voor alle andere elementen van de simplextabel:
In het ontvangen plan F– de lijn bevat één negatief element – (-5/3), vector P1. Het bevat in zijn kolom één enkel positief element, dat het faciliterende element zal zijn. Laten we de tabel met betrekking tot dit element opnieuw berekenen:
Geen negatieve elementen erin F– lijn betekent gevonden optimaal plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov SA Lineaire programmering, M: Nauka, 1998,
- Ventzel E.S. Operations Research, M: Sovjet-radio, 2001,
- Kuznetsov Yu.N., Kuzubov VI, Voloshenko AB Wiskundig programmeren, M: Higher School, 1986.
Aangepaste lineaire programmeeroplossing
Op onze website kunt u alle opdrachten in dit vakgebied bestellen. U kunt bestanden bijvoegen en deadlines opgeven op
