Simplex-methode Voorbeeldoplossing voor dummies. Oplossing van de productietaak in een tabulaire simplex-methode

Het idee van het symbool van de werkwijze is om van de ene grond naar de andere te gaan, die de waarde van de functie ontvangt, met een minimum, niet minder dan de bestaande (elke basis overeenkomt met de enige waarde van de functie).
Uiteraard is het aantal allerlei soorten bases voor elke taak het aantal finale (en niet erg groot).
Daarom zal het antwoord vroeg of laat worden verkregen.

Hoe is de overgang van de ene basis naar de andere?
De oplossing is handiger om op te nemen in de vorm van tabellen. Elke regel is gelijk aan de systeemvergelijking. De geselecteerde reeks bestaat uit functiecoëfficiënten (vergelijk uzelf). Dit maakt het mogelijk om de variabelen niet te herschrijven telkens wanneer dat de tijd aanzienlijk bespaart.
B Geselecteerde rij Selecteer de grootste positieve coëfficiënt. Dit is nodig om de waarde van een functie ten minste niet minder dan de bestaande functie te krijgen.
Geselecteerde kolom.
Voor de positieve coëfficiënten van de geselecteerde kolom beschouwen we de verhouding θ en kiezen wij de kleinste waarde. Dit is noodzakelijk, zodat na de transformatie de kolom met vrije leden positief bleef.
Een tekenreeks is geselecteerd.
Daarom wordt een element gedefinieerd, dat basic is. Vervolgens beschouwen we.

Als er in de voorwaarde van het probleem beperkingen zijn met een bord ≥, kunnen ze worden gegeven aan de vorm σa ji b j, vermenigvuldigen beide delen van ongelijkheid op -1. We introduceren M extra variabelen x N + J ≥0 (J \u003d 1, M) en wij transformeren de beperkingen tot het type vergelijkingen

(2)

Stel dat alle originele variabelen van de taak x 1, x 2, ..., x n niet-spek zijn. Dan zullen extra variabelen eenvoudig zijn en heeft de specifieke oplossing van het restrictiesysteem het formulier

x 1 \u003d x 2 \u003d ... \u003d x n \u003d 0, x n + j \u003d b j, j \u003d 1, m. (3)

Sinds de waarde van de functiefunctie F 0 \u003d 0, kan F (X) als volgt worden ingediend:

F (x) \u003d σc i x i + f 0 \u003d 0 (4)

De eerste SIMPLEX-tabel (SIMPLEX-tabel. 1) is samengesteld op basis van vergelijkingen (2) en (4). Als vóór aanvullende variabelen X N + J is, is er een teken "+", zoals in (2), dan worden alle coëfficiënten vóór de variabelen X I en het vrije lid B J zonder verandering opgenomen in de Simplex-tabel. De coëfficiënten van de doelfunctie wanneer deze wordt gemaximaliseerd, worden ingevoerd in de onderste regel van de Simplex-tabel met tegenovergestelde tekenen. Gratis leden in de Simplex-tabel bepalen de oplossing van het probleem.

Het probleemoplossende algoritme is als volgt:

1e stap. We worden elementen van de kolom met vrije leden bekeken. Als ze allemaal positief zijn, wordt de toelaatbare basisoplossing gevonden en gaan naar stap 5 van het algoritme die overeenkomt met de optimale oplossing. Als er negatieve vrije leden zijn in de eerste Simplex-tabel, is de oplossing niet toegestaan \u200b\u200ben gaat u naar stap 2.

2e stap. Om een \u200b\u200btoegestane oplossing te vinden, is het noodzakelijk om te beslissen welke van niet-ontkoppelde variabelen op basis van de basis en welke variabele zich van de basis terugtrekt.

Tafel 1.

Om dit te doen, kiest u een van de negatieve elementen van een kolom met vrije leden (laat het B 2 leiden, of toegestaan. Als er geen negatieve elementen op een rij zijn met een negatief vrij lid, is het systeem van beperkingen onbegrijpelijk De taak heeft geen oplossing.

Tegelijkertijd wordt de variabele geëlimineerd van BP, die de eerste is die het bord verandert met een toename van de geselecteerde NP X L. Het zal x n + r zijn, waarvan de index R wordt bepaald uit de voorwaarde

die. De variabele die overeenkomt met de kleinste verhouding van een vrij lid naar het element van de geselecteerde loodkolom. Deze relatie wordt genoemd simplex-houding. Alleen positieve simplex-relaties moeten worden overwogen.

De string die overeenkomt met de variabele X N + R wordt genoemd leiden, of het toelaat. Het element van de SIMPLEX-tabel A RL, permanent bij de kruising van de hostreeks en de hoofdkolom, wordt een toonaangevend of toegestane element genoemd. Het vinden van het hoofdelement eindigt met elke volgende Simplex-tabel.

3e stap. De nieuwe Simplex-tabel wordt berekend, waarvan de elementen worden herberekend uit de elementen van de Simplex-tabel van de vorige stap en gemarkeerd met een beroerte, d.w.z. B "J, een" JI, C "I, F" 0. Herberekening van elementen wordt gemaakt volgens de volgende formules:

Ten eerste is de nieuwe Simplex-tabel gevuld met een string en kolom, die in de vorige Simplex-tabel leidde. De expressie (5) betekent dat het element A "RL op de site van de master gelijk is aan de inverse omvang van het element van de vorige Simplex-tabel. De elementen van de RI-rij zijn verdeeld in het hoofdelement en de elementen van De kolom van een JL is ook verdeeld in een toonaangevend element, maar worden genomen met het tegenovergestelde teken. Elementen B "R en C" L wordt berekend door hetzelfde principe.

De resterende formules zijn gemakkelijk om mee te registreren.

De rechthoek is op zodanige wijze gebouwd volgens de oude Simplex-tabel die een van de diagonalen vormt, opnieuw berekende (A-ji) en de lood (een RL) -elementen (fig. 1). De tweede diagonaal wordt uniek gedefinieerd. Om een \u200b\u200bnieuw element een "JI uit het JI-element te vinden, wordt het in mindering gebracht (het" - "teken van de cel is hiervoor aangegeven) het product van de elementen van de tegenovergestelde diagonaal gedeeld door het hoofdelement. Evenzo, elementen B" J, (J ≠ R) en C "I, (I ≠ L).

4e stap. Een analyse van de nieuwe Simplex-tafel begint met de 1e stap van het algoritme. De actie gaat door totdat een geldige basisoplossing is gevonden, d.w.z. Alle elementen van de kolom met vrije leden moeten positief zijn.

5e stap. Wij zijn van mening dat de toelaatbare basisoplossing wordt gevonden. We bekijken de rijcoëfficiënten F (X) -functie. Een teken van de optimaliteit van de Simplex-tabel is niet-negativiteit van coëfficiënten met niet-losse variabelen in de F-lijn.

Fig. 1. Regel van rechthoek

Als er negatief is (met uitzondering van een vrij lid) van de F-rij-coëfficiënten), moet u naar een andere basisoplossing gaan. Bij het maximaliseren van de doelfunctie omvat de basis dat van niet-bindende variabelen (bijvoorbeeld x L), waarvan de kolom overeenkomt met de maximale absolute waarde van de negatieve coëfficiënt C L aan de onderste lijn van de Simplex-tabel. Hiermee kunt u die variabele kiezen, de toename waarin leidt tot een verbetering van de functiefunctie. Een kolom die overeenkomt met de variabele X L wordt de leidende naam genoemd. Tegelijkertijd is de variabele X N + R uitgesloten van de basis, waarvan de index R wordt bepaald door de minimale SIMPLEX-ratio:

De string die overeenkomt met X N + R wordt de Master genoemd en het element van de Simplex-tabel A RL, die zich bij de kruising van de hostreeks bevindt en de hostkolom, wordt genoemd het leidende element.

6e stap. Volgens de regels uiteengezet op de 3e stap. De procedure gaat door totdat de optimale oplossing wordt gevonden of er wordt geconcludeerd dat het niet bestaat.

Als in het proces van het optimaliseren van de oplossing in de hoofdkolom, zijn alle elementen niet-positief, dan kan de leidende regel niet worden geselecteerd. In dit geval is de functie op het gebied van toelaatbare oplossingen van het probleem niet beperkt van boven en f max -\u003e & ∞.

Als bij de volgende stap van het zoeken naar extreme, wordt een van de basisvariabelen nul, dan wordt de overeenkomstige basisoplossing gedegenereerd genoemd. In dit geval treedt de zogenaamde lus op, gekenmerkt door het feit dat met een bepaalde frequentie dezelfde combinatie van BP begint te herhalen (de functie van de functie F is bewaard) en het is onmogelijk om naar een nieuwe toegestane basis te gaan oplossing. De lus is een van de belangrijkste tekortkomingen van de Simplex-methode, maar het is relatief zeldzaam. In de praktijk weigert in dergelijke gevallen meestal de variabele op de basis in te voeren, waarvan de kolom overeenkomt met de maximale absolute waarde van de negatieve coëfficiënt in de functiefunctie en een willekeurige selectie van een nieuwe basisoplossing.

Voorbeeld 1. Los de taak op

max (f (x) \u003d -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Simplex-methode en geef de geometrische interpretatie van het oplossingsproces.

De grafische interpretatie van de oplossing van het probleem wordt gepresenteerd in FIG. 2. De maximale waarde van de doelfunctie wordt bereikt aan de bovenkant van de OTWP met coördinaten. We zullen de taak oplossen met Simplex-tabellen. Ik zal de tweede limiet op (-1) vermenigvuldigen en we introduceren extra variabelen, zodat ongelijkheden tot het type vergelijkingen leiden, dan

De initiële variabelen x 1 en x 2 worden genomen als niet-misbruik en extra x 3, x 4 en x 5 beschouwen de basis en vormen een Simplex-tabel (SIMPLEX-tabel. 2). De oplossing die overeenkomt met de Simplex-tabel. 2 is niet toegestaan; Het aandrijfelement wordt omcirkeld met een circuit en geselecteerd in overeenstemming met de stap 2 van het eerder gegeven algoritme. Volgende simplex tafel. 3 Bepaalt een toelaatbare basisoplossing, het komt overeen met de vertex van OCP in FIG. 2 Het leidende element wordt omcirkeld met een circuit en geselecteerd in overeenstemming met de 5e stap van het probleemoplossend algoritme. Tafel. 4 komt overeen met de optimale oplossing van het probleem, daarom: x 1 \u003d x 5 \u003d 0; x 2 \u003d 4; x 3 \u003d 3; x 4 \u003d 8; F max \u003d 20.

Fig. 2. Grafisch oplossingsprobleem

Benoeming van de service\u200b Een online calculator wordt gebruikt om lineaire programmeerproblemen op te lossen. P-methode In de volgende opnamevormen: de basisvorm van de registratiemethode van het symbool, in de vorm van een Simplex-tabel, een gewijzigde SIMPLEX-methode.

Instructies voor het oplossen van problemen dual Simplex-methode\u200b Selecteer het aantal variabelen en het aantal snaren (aantal beperkingen), klik op Volgende. De verkregen oplossing wordt opgeslagen in het Word-bestand (zie voorbeeld van het oplossen van een DUAL SIMPLEX-methode).

Samen met deze rekenmachine gebruikt u ook het volgende:
Grafische methode voor het oplossen van ZLP
Oplossing van de transporttaak
Matrix-spel oplossen
Met behulp van de service in de online-modus kunt u de prijs van het Matrix-spel (onderste en bovenste grenzen) bepalen, de aanwezigheid van een zadelpoint controleren, een oplossing vinden voor een MIXED-strategiemethoden: Minimax, Simplex-methode, afbeelding (geometrische) methode, bruine methode.
Extreme functie van twee variabelen

Dynamische programmeertaken
Distribueer 5 homogene veel goederen tussen drie markten om het maximale inkomen uit hun verkoop te krijgen. De inkomsten uit de verkoop op elke G (X) -markt is afhankelijk van het aantal verkochte goederen en wordt in de tabel gepresenteerd.

In de P-methode wordt het optimale plan verkregen als gevolg van de beweging op pseudooplanes. Pseudoplan - een plan waarbij de optimaliteitsomstandigheden zijn voldaan, en bij de waarden van de basisvariabelen X I zijn er negatieve getallen. Algoritme van de DUAL SIMPLEX-modus Inclusief de volgende stappen:

1. Compilatie van pseudooplane\u200b Het systeem van beperkingen van het eerste probleem leidt tot het systeem van ongelijkheid van betekenis "≤".
2. Controleer de optimaliteit van het plan\u200b Als de optimaliteitstoestand niet is voldaan in het resulterende referentieplan, wordt de taak opgelost door de SIMPLEX-methode.
3. Selecteer toonaangevende snaren en kolommen\u200b Onder de negatieve waarden van de basisvariabelen worden de grootste in absolute waarde geselecteerd. Een string die overeenkomt met deze waarde is de leiding.
4. Berekening van een nieuw referentieplan\u200b Het nieuwe plan wordt verkregen door de Simplex-tabel te herculeren door de Jordan-Gauss-methode. Ga vervolgens naar stap 2.

Voorbeeld. Het bedrijf moet worden vrijgegeven volgens het plan van producten A1-eenheden, A2-eenheden, A3-eenheden. Elk type product kan op twee machines worden geproduceerd.
Hoe het werk van de machines te verspreiden, zodat de totale kosten voor de uitvoering van het plan minimaal zijn geweest? Dana kosten matrix en tijdbron van elke machine. Schrijf het model van de onderzochte bediening in het formulier dat het gebruik van de P-methode kan toestaan.

Het is bekend dat de inhoud van N-voedingsstoffen A, B en C in het dieet ten minste M1, M2, M3-eenheden, respectievelijk moet zijn. Deze voedingsstoffen bevatten drie soorten producten. Het gehalte aan voedingseenheden in één kilogram van elk van de soorten product wordt gegeven in de tabel. Bepaal het dagelijkse dieet dat het vereiste aantal voedingsstoffen verkrijgt met minimale geldkosten.

Taak: Los de taak op met behulp van het algoritme van de DUAL SIMPLEX-methode.
We geven een systeem van beperkingen aan het systeem van ongelijkheid van betekenis ≤, en vermenigvuldigt de overeenkomstige lijnen op (-1).
We definiëren de minimumwaarde van de doelfunctie F (x) \u003d 4x 1 + 2x 2 + x 3 onder de volgende limietomstandigheden.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Om het eerste referentieplan te construeren, presenteren we het ongelijkheidssysteem dat we aan het systeem van vergelijkingen presenteren door extra variabelen in te voeren (overgang naar canonische vorm).
In de eerste ongelijkheid van betekenis (≤) gaan we de basisvariabele X 4 in. In de tweede ongelijkheid van de betekenis (≤) gaan we de basisvariabele x 5 in.
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 \u003d -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 \u003d 8
De coëfficiënt matrix A \u003d A (IJ) van dit systeem van vergelijkingen is:

Iteratie nummer 1.

Plan 0 in de Simplex-tabel is pseudo-vlak, dus bepalen we de toonaangevende string en kolom.


De master is de eerste regel en de variabele X 4 moet van de basis worden afgeleid.
3. Definitie van een nieuwe basisvariabele. De minimale waarde van θ komt overeen met de 2e kolom, d.w.z. De variabele X2 moet in de basis worden ingevoerd.

Iteratie nummer 2.
1. Controleer het optimaliteitscriterium.
Plan 1 in de Simplex-tabel is pseudo-vlak, dus bepalen we de toonaangevende string en kolom.
2. Bepaling van een nieuwe vrije variabele.
Onder de negatieve waarden van de basisvariabelen kiezen we de grootste module.
De leiding is de tweede regel en de variabele X 5 moet van de basis worden afgeleid.
3. Definitie van een nieuwe basisvariabele. De minimumwaarde θ komt overeen met de derde kolom, d.w.z. De variabele X 3 moet in de basis worden ingevoerd.
Op de kruising van toonaangevende snaren en kolom is er een resolutie-element (RE), gelijk aan (-1).

Iteratie nummer 3.
1. Controleer het optimaliteitscriterium.
Onder de waarden van de indexregel zijn niet positief. Daarom bepaalt deze tabel het optimale taakplan.

Korte theorie

Om lineaire programmeertaken op te lossen, zijn er veel verschillende methoden. Het meest efficiënte en universele onder hen was echter de Simplex-methode. Opgemerkt moet worden dat bij het oplossen van sommige taken, andere methoden efficiënter kunnen zijn. Wanneer de ZLP bijvoorbeeld met twee variabelen optimaal is en bij het oplossen van - de potentiële methode. De SIMPLEX-methode is de belangrijkste en van toepassing op elk SAP in Canonical Form.

In verband met de belangrijkste lineaire programmeringstheorie, het idee van de volgende manier om de ZLP op te lossen met een willekeurig aantal variabelen. Om alle extreme punten van de polyhedron-plannen (hun niet meer dan) te vinden en de waarden van de doelfunctie in hen te vergelijken. Een dergelijke manier van oplossen, zelfs met een relatief klein aantal variabelen en beperkingen, praktisch onmogelijk, omdat het proces van het vinden van extreme punten vergelijkbaar is door moeilijkheden met het oplossen van de initiële taak, bovendien, het aantal extreme punten van de polyhedron-plannen, erg groot. In verband met deze moeilijkheden ontstond de taak van rationele integratie van extreme punten.

De essentie van de Simplex-methode is als volgt. Als een extreempunt bekend is en de waarde erin is een doelfunctie, dan is alle extreme punten waarin de doelfunctie de slechtste waarde is, niet noodzakelijk nodig. Vandaar dat van nature de wens om een \u200b\u200bmanier te vinden om van dit uiterste punt naar het best aangrenzende aan de rand te overgaan, van het tot nog beter (niet slechter), enz. Om dit te doen, is het noodzakelijk om een \u200b\u200bteken te hebben dat de beste extreme punten dan dit extreme punt is helemaal niet. Dit is het algemene idee van de meest gebruikte eenvoud-methode (methode van consistent verbeteringsplan) om de ZLL op te lossen. Dus, in algebraïsche voorwaarden, suggereert de Simplex-methode:

1. het vermogen om het eerste referentieplan te vinden;
2. de aanwezigheid van een teken van optimaliteit van het referentieplan;
3. het vermogen om naar een niet-referentieplan te gaan.

Een voorbeeld van het oplossen van het probleem

De taak

Voor de implementatie van drie groepen goederen heeft een commerciële onderneming drie soorten beperkt materiaal en geldmiddelen in kwantiteit ,, eenheden. Tegelijkertijd, voor de verkoop van 1 groep goederen per duizend roebel. De omzet wordt verbruikt door de bron van de eerste soort in het aantal eenheden, de bron van het tweede type in het aantal eenheden, de derde speciesbron in het aantal eenheden. Te koop 2 en 3 groepen goederen per duizend roebel. De omzet wordt verbruikt volgens de bron van de eerste soort in het bedrag, eenheden, de middelen van het tweede type in het bedrag, eenheden, derde-type bronnen in het bedrag, eenheden. Winst uit de verkoop van drie groepen goederen per duizend roebel. Commodity is respectievelijk, duizend roebel.

• Bepaal het geplande volume en de omzetstructuur, zodat de winst van de handelsonderneming maximum is.
• De directe taak van het plannen van de omzet, opgelost door de Simplex-methode, is een dubbele taak van lineaire programmering.
• Installeer de conjugaatparen van variabele directe en dubbele taken.
• Volgens conjugaatvariabele paren van het oplossen van een directe taak om een \u200b\u200boplossing voor een dubbele taak te verkrijgen, die een beoordeling maakt van de bronnen die zijn uitgegeven aan de verkoop van goederen.

Als uw toelating tot de sessie afhangt van de oplossing van de taakeenheid, en u geen tijd hebt, noch de wens om te zitten voor de berekeningen - gebruik dan de site-site. Taakvolgorde is een kwestie van minuten. Details (hoe een aanvraag, prijzen, deadlines, betaalmethoden) te laten, kunnen op de pagina worden gelezen om oplossingen te kopen voor taken voor lineaire programmering ...

De oplossing van het probleem

Bouwmodel

Via de omzet van respectievelijk de 1e, 2e en derde type goederen.

Dan drukt de doelfunctie de resulterende winst uit:

Beperkingen op materiaal en monetaire bronnen:

Bovendien, in de zin van het probleem

We krijgen de volgende lineaire programmeertaak:

Naar het canonieke type ZLP

We geven de taak aan canonieke vorm. Om ongelijkheden in gelijkheid te converteren, introduceren we extra variabelen. Variabelen zijn in beperkingen met de coëfficiënt 1. in de doelfunctie, invoegen alle extra variabelen met een coëfficiënt gelijk aan nul.

De beperking heeft een voorkeursvorm indien, met niet-negativiteit van het rechterdeel, het linkerdeel een variabele heeft omvat met de coëfficiënt die gelijk is aan één, en de resterende gelijkheidsbeperkingen - met een coëfficiënt gelijk aan nul. In ons geval hebben de 1e, 2e, de 3e beperkingen een voorkeursvorm met de bijbehorende basisvariabelen.

Oplossing symptoom

Vul de Simplex-tabel van de 0e iteratie in.

Aangezien we de taak op maximaal oplossen - de aanwezigheid in de indexregel van negatieve nummers bij het oplossen van het probleem op maximaal, geeft aan dat we de optimale oplossing niet hebben ontvangen en die van de tabel van de 0e iteratie die u naar de volgende moet gaan .

De overgang naar de volgende iteratie is als volgt:

De kolom van de presentator komt overeen met.

De sleutellijn wordt bepaald op een minimum van de verhoudingen van vrije leden en leden van de loodkolom (SIMPLEX-relaties):

Op de kruising van de sleutelkolom en de sleutellijn vinden we het toestaan \u200b\u200bvan element, d.w.z.7.

Ga nu verder met de voorbereiding van de 1e iteratie. In plaats van een enkele vector betreden we de vector.

In de nieuwe tabel op de site van het resolutie-element schrijven we 1, alle andere elementen van de sleutelkolom -n. De belangrijkste lijnelementen zijn onderverdeeld in een resolutie-element. Alle andere elementen van de tafel worden berekend op basis van de regel van de rechthoek.

We ontvangen een tabel van de 1e iteratie:

De belangrijkste kolom voor de 1e iteratie komt overeen.

We vinden een sleutelstring, hiervoor bepalen we:

Op het kruispunt van de sleutelkolom en de sleutellijn vinden we het toestaan \u200b\u200bvan het item, d.w.z. 31/7.

De vector wordt van de basis weergegeven en voer de vector in.

We ontvangen een tabel met de 2e iteratie:

In de indexregel zijn alle leden niet-negatief, dus de volgende oplossing van het lineaire programmeerprobleem wordt verkregen (we schrijven uit de kolom met vrije leden):

Het is dus noodzakelijk om 7,1 duizend roebel te verkopen. Producten van het 1e type en 45.2 duizend roebel Goederen van de 3e weergave. Het product van het 2e type verkoop is onrendabel. Tegelijkertijd zal de winst maximaal zijn en is 237.4 duizend roebel. Bij het implementeren van het optimale plan is het residu van de 3e weergave 701 eenheden.

Dual Task LP

We schrijven het model van de dubbele taak.

Om een \u200b\u200bdubbele taak te bouwen, moet u de volgende regels gebruiken:

1) Als de directe taak maximaal is opgelost, dan dual - tenminste, en vice versa;

2) In het probleem bij de maximale limiet van ongelijkheid, is het logisch ≤ en in het probleem van minimalisatie - wat betekent ≥;

3) Elke beperking van een direct probleem komt overeen met een variabele van het dubbele probleem, en vice versa, elke beperking van het dubbele probleem komt overeen met een directe taakvariabele;

4) De matrix van het systeem van beperkingen van het dubbele probleem wordt verkregen uit de matrix van het restrictiesysteem van het eerste probleem met de omzetting;

5) De vrije leden van het directe probleembewerkingssysteem zijn coëfficiënten met de overeenkomstige variabelen van de doelfunctie van de dubbele taak en vice versa;

6) Indien de variabele van de directe taak wordt gesuperponeerd met niet-negativiteitstoestand, wordt de overeenkomstige beperking van het dubbele probleem geschreven als een beperking-ongelijkheid, zo niet, als de gelijkheidslimiet;

7) Indien een beperking van de directe taak als gelijkheid wordt geregistreerd, wordt de relevante variabele van het dubbele probleem niet opgelegd.

Transpoin-matrijzen van de brontaak:

We geven de taak aan canonieke vorm. We introduceren extra variabelen. In de doelfunctie, alle extra variabelen die we introduceren met een coëfficiënt gelijk aan nul. Extra variabelen worden toegevoegd aan de linker delen van beperkingen die niet de voorkeurssoorten hebben en gelijk worden.

Oplossing van de dubbele taak van LP

Naleving tussen de variabelen van de originele en dubbele taak:

Op basis van de Simplex-tabel wordt de volgende oplossing van de dubbele lineaire programmeertaak verkregen (afvoer van de onderste regel):

De bron van het eerste type is dus het meeste tekort. De schatting is maximaal en gelijk. De derde vormresource is een overbodige dubbele score gelijk aan nul. Elke aanvullend verkochte eenheid van goederen van de 2e groep zal de optimale winsten verminderen
De grafische methode voor het oplossen van een lineair programmeerprobleem (ZLP) met twee variabelen wordt overwogen. In het voorbeeld van de taak wordt een gedetailleerde beschrijving van de constructie van de tekening en het vinden van een oplossing gegeven.

Oplossing van de transporttaak
Het transportprobleem wordt in detail beschouwd, zijn wiskundige model- en oplossingmethoden - het vinden van het referentieplan door de werkwijze van het minimumelement en het zoeken naar de optimale oplossing door de methode van potentialen.

Besluitvorming in onzekerheid
De beslissing van het statistische matrixspel in de omstandigheden van onzekerheid met behulp van Wald-criteria, wilde, Gurvitsa, Laplas, Bayes wordt overwogen. Met behulp van het taakvoorbeeld, wordt de constructie van een betalingsmatrix en risicomatrix in detail weergegeven.

Hier wordt handleiding (geen applet) gegeven aan de oplossing van twee taken met een Simplex-methode (vergelijkbare appletoplossing) met gedetailleerde uitleg om het probleem op te lossen die algoritme simplex-methode oplossen. De eerste taak bevat ongelijkheid alleen "≤" (taak met de eerste basis), de tweede kan tekenen "≥", "≤" of "\u003d" (taak met een kunstbasis) bevatten, ze zijn op verschillende manieren opgelost.

Simplex-methode, het oplossen van de taak met de eerste basis

1)Simplex-methodevoor een taak met een eerste basis (alle tekenen van ongelijkheid-beperkingen "≤").

We schrijven de taak B. canoniek vorm, d.w.z. Beperkingen van ongelijkheden zullen herschrijven in de vorm van gelijkheden door toe te voegen balans Variabelen:

Dit systeem is een systeem met een basis (basis S 1, S2, S3, elk van hen komt slechts één vergelijking van het systeem binnen met een coëfficiënt 1), x 1 en x 2 - gratis variabelen. Taken, bij het oplossen van welke de Simplex-methode wordt toegepast, moeten de volgende twee eigenschappen hebben: - Beperkingensysteem moet een systeem van vergelijkingen zijn met een basis; - Ondersteunde voorwaarden van alle vergelijkingen in het systeem moeten niet-negatief zijn.

Het resulterende systeem - het systeem met een basis en de vrije leden zijn niet-negatief, dus u kunt solliciteren simplex-methode\u200b Vormen de eerste Simplex-tabel (iteratie 0) om het probleem op te lossen Simplex-methode\u200b Tabel met doelfunctiecoëfficiënten en systeem van vergelijkingen met geschikte variabelen. Hier betekent "BP" een kolom met standaardvariabelen, "Oplossing" - een kolom van de juiste delen van de systeemvergelijkingen. De beslissing is niet optimaal, omdat In z - lijn zijn er negatieve coëfficiënten.

simplex-methode iteratie 0

Om de oplossing te verbeteren, wenden we ons tot de volgende iteratie simplex-methode, We krijgen de volgende simplex-tabel. Om dit te doen, moet je kiezen toegandanke kolom\u200b Een variabele die de basis zal invoeren in de volgende iteratie van de Simplex-methode. Het wordt geselecteerd op de grootste module tot de negatieve coëfficiënt in de Z-rij (in een maximumprobleem) - in de initiële iteratie van de SIMPLEX-methode, deze kolom x 2 (coëfficiënt -6).

Vervolgens geselecteerd resolutie reeks\u200b Een variabele die zal worden vrijgegeven vanaf de basis in de volgende iteratie van de Simplex-methode. Het wordt gekozen door de kleinste houding van de kolom "Oplossing" naar de overeenkomstige positieve elementen van de kolom (de kolom "verhouding") - in de initiële iteratie is het een tekenreeks S3 (coëfficiënt 20).

Het toelaten van element Het is op het kruispunt van de resolutiekolom en de resolutie, de cel wordt geïsoleerd door kleur, het is. Daarom wordt in de volgende iteratie van de Simplex-methode de variabele X2 vervangen in de basis S 1. Merk op dat in de Z-Row de houding niet wordt doorzocht, er is een dashboard "-". In het geval dat er dezelfde minimumverhouding zijn, is er een van hen geselecteerd. Als alle coëfficiënten kleiner zijn dan of gelijk zijn in de kolom Resolutie, is het probleemoplossing oneindig.

Vul de volgende tabel "iteratie 1" in. We krijgen het van de tafel "iteratie 0". Het doel van verdere transformaties is om de resolutiekolom x 2 in één te transformeren (met een eenheid in plaats van het resolutieelement en nullen in plaats van de andere elementen).

1) Berekening van de string x 2 tafel "iteratie 1". Eerst delen we alle leden van de resolutie S 3-tabel "iteratie 0" naar het resolutie-element (het is 1 in dit geval) van deze tabel, we verkrijgen de string x 2 in de tafel "iteratie 1". Omdat Het oplossende element in dit geval is 1, dan zal de lijn S 3 van de tabel "iteratie 0" samenvallen met de lijn x 2 van de tafel "iteratie 1". Lijn x 2 tafels "iteratie 1" We hebben 0 1 0 0 1 20, de resterende rijen van de "iteratie 1" -tabel worden verkregen van deze regel en de snaren van de "iteratie 0" -tafel als volgt:

2) Berekening van de Z-rij-tabel "iteratie 1". In plaats --6 in de eerste regel (Z-rij) in de kolom x 2 van de tabel "iteratie 0" moet 0 zijn in de eerste regel van de "iteratie 1" -tabel. Om dit te doen, alle elementen van de string x 2 tafel "iteratie 1" 0 1 0 0 1 20 Vermenigvuldig met 6, we verkrijgen 0 6 0 0 6 120 en leggen deze string met de eerste regel (Z - Line) tabel "iteratie 0 "-4 -6 0 0 0 0, we verkrijgen -4 0 0 0 6 120. In kolom x 2 verscheen nul 0, het doel wordt bereikt. De elementen van de kolom van de resolutie X2 worden rood gemarkeerd.

3) Berekening van de snaar S 1 tafel "iteratie 1". Op zijn plaats moet 1 in S 1-lijn van de tabel "iteratie 0" 0 in de tabel "iteratie 1" zijn. Hiervoor alle elementen van de string x 2 tafel "iteratie 1" 0 1 0 0 1 20 Vermenigvuldig op -1, verkrijgen we 0 -1 0 -1 -1 -20 en leggen deze string met S 1 - lijn van de tabel "Iteratie 0" 2 1 1 0 0 64, wij verkrijgen een string 2 0 1 0 -1 44. In de kolom X2 wordt de vereiste 0 verkregen.

4) Berekening van de tekenreeks S 2 tabel "iteratie 1". Op zijn plaats 3 in S 2 rij van de "iteratie 0" -tabel moet 0 zijn in de tabel "iteratie 1". Om dit te doen, alle elementen van de string x 2 tafel "iteratie 1" 0 1 0 0 1 20 vermenigvuldigen met -3, we verkrijgen 0 -3 0 0 -3 -60 en leggen deze string met S 1 - lijn van de tabel "Iteratie 0" 1 3 0 1 0 72, wij verkrijgen een reeks van 1 0 0 1 -3 12. In de kolom X2 wordt de gewenste 0 verkregen. De kolom x 2 in de tafel "iteratie 1" werd single, Het bevat één 1 en de resterende 0.

Rijen van de "iteratie 1" -tabel worden verkregen volgens de volgende regel:

De nieuwe regel \u003d de oude string - (de coëfficiënt van de toegestane kolom van de oude regel) * (nieuw toestaan \u200b\u200bvan string).

Bijvoorbeeld voor z-rij hebben we:

Oude Z-ROW (-4 -6 0 0 0 0) - (- 6) * NIEUW TOEPASSING STRING - (0 -6 0 0 -6 -120) \u003d Nieuwe Z-LINE (-4 0 0 6 120).

Voor de volgende tabellen wordt de herberekening van de elementen van de tafel op dezelfde manier gemaakt, dus we laten het weg.

simplex-methode iteratie 1

De resolutiekolom x 1, het oplossen van de S2-string, S2 verlaat de basis, X 1 komt de basis in. Volledig vergelijkbaar met de andere Simplex-tabellen, totdat een tabel wordt verkregen met alle positieve coëfficiënten in de Z-rij. Dit is een teken van een optimale tafel.

simplex-methode iteratie 2

De resolutiekolom S 3, het oplossen van de snaar S 1, S 1 verlaat de basis, S 3 komt de basis in.

simplex-methode iteratie 3

In de Z-rij zijn alle coëfficiënten niet-negatief, daarom werd de optimale oplossing x 1 \u003d 24, x 2 \u003d 16, z max \u003d 192 verkregen.