Simplex-methode− dit is een methode voor het ordelijk opsommen van referentieplannen (de orde wordt verzekerd door een monotone verandering in de waarde van de doelfunctie bij het overgaan naar het volgende plan). In dit geval is het noodzakelijk om het principe in acht te nemen: elke volgende stap moet de waarde van de objectieve functie verbeteren of, in extreme gevallen, niet verslechteren.
Om de ZLP op te lossen simplex methode het wordt in canonieke vorm gebracht, d.w.z. Van beperkingen - ongelijkheden - het is noodzakelijk om beperkingen te maken - gelijkheid. Om dit te doen, wordt in elke beperking een extra niet-negatieve factor geïntroduceerd balans variabele met een “+” teken als het ongelijkheidsteken “£” is, en met een “–” teken als het ongelijkheidsteken “³” is.
In de objectieve functie worden deze extra variabelen opgenomen met nulcoëfficiënten, d.w.z. de invoer van de doelfunctie verandert niet. Elke variabele die niet onderworpen is aan de niet-negativiteitsvoorwaarde kan worden weergegeven als het verschil tussen twee niet-negatieve variabelen: .
Als taakbeperkingen de beschikbaarheid en het verbruik van hulpbronnen weerspiegelen, dan is de numerieke waarde van de extra variabele in het taakplan, geschreven in canonieke vorm, gelijk aan de hoeveelheid ongebruikte hulpbronnen.
Om het probleem op te lossen met behulp van de simplexmethode die we zullen gebruiken verkorte simplextabellen met systemen van lineaire vergelijkingen en de gewijzigde Jordan-eliminatiemethode.
1. Het maken van het eerste referentieplan
De taak blijft hetzelfde. Laten we de standaardvorm van het stelsel van ongelijkheden (1) in de canonieke vorm van het stelsel van vergelijkingen brengen door extra evenwichtsvariabelen te introduceren X 3 , X 4 , X 5 ,X 6 .
of 
In economische zin zijn dit de waarden van aanvullende variabelen X 3 , X 4 , X 5 bepalen de resterende grondstoffen na de verkoop van producten.
De matrix van het resulterende stelsel vergelijkingen heeft de vorm:
Dat is te zien in de matrix A de basisminor van de 4e orde is een determinant die bestaat uit eenheidscoëfficiënten voor aanvullende variabelen X 3 , X 4 , X 5 ,X 6, omdat deze verschillend is van nul en gelijk is aan 1. Dit betekent dat de kolomvectoren voor deze variabelen lineair onafhankelijk zijn, d.w.z. formulier basis en de bijbehorende variabelen X 3 , X 4 , X 5 ,X 6 zijn eenvoudig(voornaamst). Variabelen X 1 , X Er wordt 2 gebeld vrij(niet-kern).
Als vrije variabelen X 1 en X Als we verschillende waarden instellen, krijgen we, door het systeem op te lossen met betrekking tot de basisvariabelen, een oneindig aantal deeloplossingen. Als vrije variabelen slechts nulwaarden krijgen, kan men uit de oneindige reeks specifieke oplossingen selecteren basisoplossingen- basisplannen.
Om erachter te komen of variabelen basaal kunnen zijn, is het noodzakelijk om een determinant te berekenen die bestaat uit de coëfficiënten van deze variabelen. Als deze determinant niet gelijk is aan nul, kunnen deze variabelen basaal zijn.
Het aantal basisoplossingen en het overeenkomstige aantal groepen basisvariabelen kan niet meer bedragen dan , waarbij N– totaal aantal variabelen, R– aantal basisvariabelen, R≤ M≤ N.
Voor onze taak R = 4; N= 6. Dan 
, d.w.z. Er zijn 15 groepen van 4 basisvariabelen (of 15 basisoplossingen) mogelijk.
Laten we het systeem van vergelijkingen voor de basisvariabelen oplossen X 3 , X 4 , X 5 ,X 6:
Ervan uitgaande dat vrije variabelen X 1 = 0, X 2 = 0, we verkrijgen de waarden van de basisvariabelen: X 3 = 312; X 4 = 15; X 5 = 24;X 6 = –10, d.w.z. de basisoplossing is = (0; 0; 312; 15; 24; –10).
Deze basisoplossing is onaanvaardbaar, omdat X 6 = –10 ≤ 0, en volgens de voorwaarden van de beperkingen X 6 ≥ 0. Daarom in plaats van de variabele X Als basis moet men een andere variabele uit de vrije variabelen nemen X 1 of X 2 .
We zullen de verdere oplossing uitvoeren met behulp van verkorte simplex-tabellen, waarbij we de rijen van de eerste tabel als volgt vullen met de systeemcoëfficiënten (tabel 1):
tafel 1
F-de lijn wordt gebeld inhoudsopgave. Het is gevuld met coëfficiënten van de objectieve functie genomen met tegengestelde tekens, aangezien de vergelijking van de functie in de vorm kan worden weergegeven F = 0 – (– 4X 1 – 3X 2).
In de kolom gratis leden b ik er is een negatief element B 4 = –10, d.w.z. De systeemoplossing is ongeldig. Om een haalbare oplossing te verkrijgen (referentieplan), moet het element B 4 moet niet-negatief worden gemaakt.
Kiezen X 6-string met een negatieve vrije term. Deze regel bevat negatieve elementen. Selecteer een van deze, bijvoorbeeld “–1” in X 1 -kolom, en X Kolom 1 wordt genomen als resolutie kolom(het zal bepalen dat de variabele X 1 gaat van gratis naar basic).
Wij verdelen vrije leden b ik naar de overeenkomstige elementen een is resolutiekolom, krijgen we evaluatieve relatiesΘ i= = (24, 15, 12, 10). Hiervan kiezen we het kleinste positieve (minΘ i=10), wat overeenkomt toestemming lijn. De enable string definieert de variabele x j, die bij de volgende stap uit de basis steekt en vrij wordt. Daarom X De 6-regel is de activeringsregel en het “–1”-element is dat tolerant element. Laten we het omcirkelen. Variabelen X 1 en X 6 zijn verwisseld.
Geschatte verhoudingen Θ i in elke regel worden bepaald volgens de regels:
1) Θ i= als b ik En een is hebben verschillende tekens;
2) Θ i= ∞, als b ik= 0 en een is < 0;
3) Θ i= ∞, als een is = 0;
4) Θ i= 0 als b ik= 0 en een is > 0;
5) Θ i= als b ik En een is hebben dezelfde tekenen.
We voeren een stap van gemodificeerde Jordan-eliminatie (JEME) uit met een oplossend element en stellen een nieuwe tabel samen (tabel 2) volgens de volgende regel:
1) in plaats van het oplossende element (RE), wordt een waarde ingesteld die het omgekeerde is, d.w.z. ;
2) de elementen van de activeringsreeks zijn verdeeld in RE;
3) de elementen van de resolutiekolom zijn verdeeld in RE en het teken verandert;
4) de overige elementen bevinden zich volgens de rechthoekregel:
Van de tafel 2 Het is duidelijk dat de vrije termen in b ik-kolom zijn niet-negatief, daarom wordt de aanvankelijk haalbare oplossing verkregen - eerste referentieplan= (10; 0; 182; 5; 4; 0). In dit geval de waarde van de functie F() = 40. Geometrisch komt dit overeen met de bovenkant F(10; 0) oplossingspolygoon (Fig. 1).
tafel 2
2. Wij controleren het plan op optimaliteit. Het referentieplan is niet optimaal, aangezien in F-line heeft een negatieve coëfficiënt “–4”. Wij verbeteren het plan.
3. Een nieuw referentieplan zoeken
We selecteren het toegestane element volgens de regel:
We kiezen de kleinste negatieve coëfficiënt in F-regel “–4”, die de resolutiekolom definieert – X 6; variabel X 6 zijn omgezet naar basisch;
We vinden de relaties Θ i, onder hen selecteren we de kleinste positieve die overeenkomt met de resolutielijn:
min Θ i = min(14, 5, 2, ∞) = 2, dus X 5-regelig – inschakelend, variabel X 5 worden geconverteerd naar gratis (variabelen X 5 en X 6 zijn verwisseld).
Op het snijpunt van de oplossende rij en kolom bevindt zich een oplossend element “2”;
We voeren de SMGI-stap uit en bouwen een tafel. 3 volgens de bovenstaande regel en we krijgen een nieuw referentieplan = (12; 0; 156; 3; 0; 2).
tafel 3
4. Controleren van het nieuwe referentieplan op optimaliteit
Ook het referentieplan is niet optimaal, aangezien in F-line heeft een negatieve coëfficiënt “–1”. Functiewaarde F() = 48, wat geometrisch overeenkomt met het hoekpunt E(12; 0) oplossingspolygoon (Fig. 1). Wij verbeteren het plan.
5. Een nieuw referentieplan zoeken
X Kolom 2 is tolerant, aangezien in F-line, de kleinste negatieve coëfficiënt “–1” is binnen X 2-koloms (Δ 2 = –1). We vinden de kleinste Θ i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, dus X 4-regelig – toestaan. Resolutie-element "1/2". Wissel variabelen uit X 2 en X 4. We voeren de SMGI-stap uit en bouwen een tafel. 4, we krijgen een nieuw referentieplan = (9; 6; 51; 0; 0; 5).
6. Controleren van het referentieplan op optimaliteit
IN F-line, alle coëfficiënten zijn niet-negatief, daarom is het referentieplan optimaal. Komt geometrisch overeen met een punt D(9;6) (zie afb. 1). Het optimale plan geeft de maximale waarde van de objectieve functie 
c.u.
Hier is een handmatige (geen applet) oplossing van twee problemen met behulp van de simplex-methode (vergelijkbaar met de applet-oplossing) met gedetailleerde uitleg om het algoritme te begrijpen voor het oplossen van problemen met behulp van de simplex-methode. Het eerste probleem bevat alleen ongelijkheidstekens “≤” (probleem met een initiële basis), het tweede kan tekens “≥”, “≤” of “=” bevatten (probleem met een kunstmatige basis), ze worden op een andere manier opgelost.
Simplexmethode, een probleem oplossen met een initiële basis
1)Simplex-methode voor een probleem met een initiële basis (alle tekenen van ongelijkheidsbeperkingen " ≤ ").
Laten we het probleem opschrijven canoniek vorm, d.w.z. we herschrijven de ongelijkheidsbeperkingen in de vorm van gelijkheid, en voegen eraan toe balans variabelen:
Dit systeem is een systeem met een basis (basis s 1, s 2, s 3, elk ervan is opgenomen in slechts één vergelijking van het systeem met een coëfficiënt van 1), x 1 en x 2 zijn vrije variabelen. Problemen die met de simplexmethode moeten worden opgelost, moeten de volgende twee eigenschappen hebben: - het stelsel van beperkingen moet een stelsel van vergelijkingen met een basis zijn; -vrije termen van alle vergelijkingen in het systeem moeten niet-negatief zijn.
Het resulterende systeem is een systeem met een basis en de vrije termen ervan zijn niet-negatief, dus we kunnen het toepassen simplex methode. Laten we de eerste simplextabel (Iteratie 0) maken om het probleem op te lossen simplex methode, d.w.z. een tabel met coëfficiënten van de objectieve functie en een systeem van vergelijkingen voor de overeenkomstige variabelen. Hier betekent “BP” de kolom met basisvariabelen, “Oplossing” betekent de kolom met de rechterkant van de systeemvergelijkingen. De oplossing is niet optimaal, omdat er zijn negatieve coëfficiënten in de z-rij.
simplex-methode iteratie 0
|
Houding |
|||||||
Om de oplossing te verbeteren, gaan we verder met de volgende iteratie simplex methode, krijgen we de volgende simplextabel. Om dit te doen, moet u selecteren kolom inschakelen, d.w.z. een variabele die in de basis zal worden opgenomen bij de volgende iteratie van de simplexmethode. Het wordt geselecteerd op basis van de grootste absoluut negatieve coëfficiënt in de z-rij (in het maximale probleem) - in de initiële iteratie van de simplexmethode is dit kolom x 2 (coëfficiënt -6).
Selecteer vervolgens tekenreeks inschakelen, d.w.z. een variabele die de basis zal verlaten bij de volgende iteratie van de simplexmethode. Het wordt geselecteerd door de kleinste verhouding van de kolom "Besluit" tot de overeenkomstige positieve elementen van de resolutiekolom (kolom "Ratio") - in de initiële iteratie is dit rij s 3 (coëfficiënt 20).
Permissief element bevindt zich op het snijpunt van de oplossingskolom en de oplossingsrij, de cel is in kleur gemarkeerd en is gelijk aan 1. Daarom zal bij de volgende iteratie van de simplexmethode de variabele x 2 s 1 in de basis vervangen. Merk op dat er niet naar de relatie wordt gezocht in de z-string; daar wordt een streepje “-” geplaatst. Als er identieke minimale relaties zijn, wordt een van deze relaties geselecteerd. Als alle coëfficiënten in de resolutiekolom kleiner dan of gelijk aan 0 zijn, is de oplossing voor het probleem oneindig.
Laten we de volgende tabel “Iteratie 1” invullen. We halen het uit de tabel "Iteratie 0". Het doel van verdere transformaties is om van de x2-resolutiekolom een eenheidskolom te maken (met een één in plaats van het resolutie-element en nullen in plaats van de overige elementen).
1) Bereken rij x 2 van de tabel “Iteratie 1”. Eerst delen we alle leden van de oplossende rij s 3 van de tabel "Iteratie 0" door het oplossende element (in dit geval is dit gelijk aan 1) van deze tabel, we krijgen rij x 2 in de tabel "Iteratie 1" . Omdat het oplossende element is in dit geval gelijk aan 1, dan zal rij s 3 van de tabel “Iteratie 0” samenvallen met rij x 2 van de tabel “Iteratie 1”. Rij x 2 van de Iteratie 1-tabel hebben we 0 1 0 0 1 20, de resterende rijen van de Iteratie 1-tabel worden als volgt uit deze rij en de rijen van de Iteratie 0-tabel gehaald:
2) Berekening van de z-rij van de tabel “Iteratie 1”. In plaats van -6 in de eerste rij (z-rij) in de x2-kolom van de Iteratie 0-tabel, moet er een 0 staan in de eerste rij van de Iteratie 1-tabel. Om dit te doen, vermenigvuldigt u alle elementen van de rij x 2 van de tabel "Iteratie 1" 0 1 0 0 1 20 met 6, we krijgen 0 6 0 0 6 120 en voegen deze rij toe aan de eerste rij (z - rij) van de tabel "Iteratie 0" -4 -6 0 0 0 0, krijgen we -4 0 0 0 6 120. Er verschijnt een nul 0 in de x 2 kolom, het doel is bereikt. Elementen van de resolutiekolom x 2 zijn rood gemarkeerd.
3) Berekening van rij s 1 van de tabel “Iteratie 1”. In plaats van 1 in s 1 rij van de tabel “Iteratie 0” zou er een 0 moeten staan in de tabel “Iteratie 1”. Om dit te doen, vermenigvuldigt u alle elementen van rij x 2 van de tabel "Iteratie 1" 0 1 0 0 1 20 met -1, krijgt u 0 -1 0 0 -1 -20 en voegt u deze rij toe met s 1 - rij van de tabel "Iteratie 0" 2 1 1 0 0 64, we krijgen de rij 2 0 1 0 -1 44. In de x 2 kolom krijgen we de vereiste 0.
4) Bereken rij s 2 van de tabel “Iteratie 1”. Op plaats 3 in rij s 2 van de tabel "Iteratie 0" moet er 0 staan in de tabel "Iteratie 1". Om dit te doen, vermenigvuldigt u alle elementen van rij x 2 van de tabel "Iteratie 1" 0 1 0 0 1 20 met -3, we krijgen 0 -3 0 0 -3 -60 en voegen deze rij toe met s 1 - rij van de tabel "Iteratie 0" 1 3 0 1 0 72, we krijgen de rij 1 0 0 1 -3 12. In de x 2-kolom wordt de vereiste 0-kolom in de tabel "Iteratie 1" verkregen een eenheid, deze bevat één 1 en de rest 0.
De rijen van de tabel “Iteratie 1” worden verkregen volgens de volgende regel:
Nieuwe rij = Oude rij – (Kolomcoëfficiënt oude rijresolutie)*(Nieuwe resolutierij).
Voor een z-string hebben we bijvoorbeeld:
Oude z-string (-4 -6 0 0 0 0) -(-6)*Nieuwe oplossingsstring -(0 -6 0 0 -6 -120) =Nieuwe z-string (-4 0 0 0 6 120).
Voor de volgende tabellen gebeurt de herberekening van tabelelementen op een vergelijkbare manier, dus laten we dit achterwege.
simplex-methode iteratie 1
|
Houding |
|||||||
Kolom x 1 oplossen, rij s 2 oplossen, s 2 verlaat de basis, x 1 komt de basis binnen. Op precies dezelfde manier verkrijgen we de resterende simplextabellen totdat we een tabel verkrijgen met alle positieve coëfficiënten in de z-rij. Dit is een teken van een optimale tafel.
simplex-methode iteratie 2
|
Houding |
|||||||
Het oplossen van kolom s 3, het oplossen van rij s 1, s 1 verlaat de basis, s 3 komt de basis binnen.
simplex-methode-iteratie 3
|
Houding |
|||||||
In de z-rij zijn alle coëfficiënten niet-negatief, daarom wordt de optimale oplossing x 1 = 24, x 2 = 16, z max = 192 verkregen.
| - | 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 | + | R1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S2 = 15 S3 = 4 R1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | 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 | + | 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 | 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 |
Doel van de dienst. De service is ontworpen voor het online oplossen van lineaire programmeerproblemen (LPP) met behulp van de simplex-methode in de volgende notatievormen:
- in de vorm van een simplextabel (Jordaanse transformatiemethode); basisregistratieformulier;
- gemodificeerde simplex-methode; in kolomvorm; in lijnvorm.
Instructies. Selecteer het aantal variabelen en het aantal rijen (aantal beperkingen). De resulterende oplossing wordt opgeslagen in een Word- en Excel-bestand.
Houd in dit geval geen rekening met beperkingen zoals x i ≥ 0. Als er voor bepaalde x i geen beperkingen in de taak zijn, moet de ZLP worden geconverteerd naar de KZLP of deze service gebruiken. Bij het oplossen wordt automatisch het verbruik bepaald M-methode(simplexmethode met kunstmatige basis) en tweetraps simplexmethode.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 |
Simplex-methode-algoritme omvat de volgende stappen:
- Opstellen van het eerste basisplan. Overgang naar de canonieke vorm van het lineaire programmeringsprobleem door niet-negatieve aanvullende balansvariabelen te introduceren.
- Het controleren van het plan op optimaliteit. Als er ten minste één indexlijncoëfficiënt kleiner is dan nul, is het plan niet optimaal en moet het worden verbeterd.
- Bepalen van de leidende kolom en rij. Uit de negatieve coëfficiënten van de indexlijn wordt de grootste in absolute waarde geselecteerd. Vervolgens worden de elementen van de vrije ledenkolom van de simplextabel verdeeld in elementen van hetzelfde teken van de leidende kolom.
- Het bouwen van een nieuw referentieplan. De overgang naar een nieuw plan wordt uitgevoerd als resultaat van de herberekening van de simplextabel met behulp van de Jordan-Gauss-methode.
Als het nodig is om het uiterste van de doelfunctie te vinden, dan hebben we het over het vinden van de minimumwaarde (F(x) → min, zie het voorbeeld van een oplossing voor het minimaliseren van een functie) en de maximumwaarde ((F(x) ) → max, zie het voorbeeld van een oplossing voor het maximaliseren van een functie)
Een extreme oplossing wordt bereikt op de grens van het gebied van haalbare oplossingen op een van de hoekpunten van de hoekpunten van de veelhoek, of op het segment tussen twee aangrenzende hoekpunten.
Fundamentele stelling van lineaire programmering. Als de ZLP-doelfunctie op een bepaald punt in de regio van haalbare oplossingen een extreme waarde bereikt, dan neemt deze deze waarde op het hoekpunt. Als de ZLP-doelfunctie op meer dan één hoekpunt een extreme waarde bereikt, neemt deze dezelfde waarde aan op elk van de convexe lineaire combinaties van deze punten.
De essentie van de simplexmethode. Verplaatsing naar het optimale punt wordt uitgevoerd door van het ene hoekpunt naar het aangrenzende punt te gaan, wat X opt dichterbij en sneller brengt. Een dergelijk schema voor het opsommen van punten, de simplexmethode genoemd, voorgesteld door R. Danzig.
Hoekpunten worden gekenmerkt door m basisvariabelen, dus de overgang van het ene hoekpunt naar een aangrenzend hoekpunt kan worden bereikt door slechts één basisvariabele in de basis te veranderen in een variabele van een niet-basis.
De implementatie van de simplexmethode kent, vanwege verschillende kenmerken en formuleringen van LP-problemen, verschillende wijzigingen.
De constructie van simplextafels gaat door totdat de optimale oplossing is verkregen. Hoe kun je een simplextabel gebruiken om te bepalen dat de oplossing voor een lineair programmeerprobleem optimaal is?
Als de laatste regel (waarden van de doelfunctie) geen negatieve elementen bevat, zal deze het optimale plan vinden.
Opmerking 1. Als een van de basisvariabelen gelijk is aan nul, dan is het uiterste punt dat overeenkomt met zo'n basisoplossing gedegenereerd. Er is sprake van degeneratie als er onduidelijkheid bestaat over de keuze van de richtlijn. Het kan zijn dat u de ontaarding van het probleem helemaal niet opmerkt als u een andere lijn als leidraad kiest. In geval van onduidelijkheid moet de rij met de laagste index worden geselecteerd om herhaling te voorkomen.
Opmerking 2. Laat op een bepaald extreem punt alle simplexverschillen niet-negatief zijn D k ³ 0 (k = 1..n+m), d.w.z. er wordt een optimale oplossing verkregen en er bestaat A k - een niet-basisvector waarvoor D k = 0. Dan wordt het maximum op minstens twee punten bereikt, d.w.z. er is een alternatief optimaal. Als we deze variabele x k in de basis introduceren, verandert de waarde van de doelfunctie niet.
Opmerking 3. De oplossing voor het duale probleem staat in de laatste simplextabel. De laatste m componenten van de vector van simplexverschillen (in de kolommen met balansvariabelen) zijn de optimale oplossing voor het dubbele probleem. De waarden van de objectieve functies van de directe en dubbele problemen op optimale punten vallen samen.
Opmerking 4. Bij het oplossen van het minimalisatieprobleem wordt de vector met het grootste positieve simplexverschil in de basis geïntroduceerd. Vervolgens wordt hetzelfde algoritme toegepast als voor het maximalisatieprobleem.
Als de voorwaarde ‘Het is noodzakelijk dat grondstoffen van type III volledig worden verbruikt’ is gespecificeerd, dan is de overeenkomstige voorwaarde een gelijkheid.
