Simplexmethode voor het oplossen van problemen. Dubbele simplex-methode

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 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 voorwaarden 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 rij x 2 van de tabel "Iteratie 1" 0 1 0 0 1 20 met 6, krijgt u 0 6 0 0 6 120 en voegt u deze rij toe aan de eerste rij (z - rij) van de tabel "Iteratie 0" -4 -6 0 0 0 0, we krijgen -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, krijgt u 0 -3 0 0 -3 -60 en voegt u 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” een eenheid geworden , het 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.

Als u een lineair programmeerprobleem moet oplossen met behulp van simplextabellen, dan kan onze online service u uitstekend helpen. De simplexmethode omvat het opeenvolgend doorzoeken van alle hoekpunten van het bereik van aanvaardbare 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 wordt verbeterd. Deze oplossing wordt basisch genoemd. Hier is de volgorde van acties bij het oplossen van een lineair programmeerprobleem met behulp van de simplexmethode:

Eerste stap.

Tweede stap.

Bij de tweede stap is het noodzakelijk om te beslissen welke variabele uit de basis moet worden uitgesloten en welke moet worden opgenomen om de simplextabel opnieuw te berekenen. Om dit te doen, bladeren we door de kolom met vrije termen en vinden er een negatief element in. De lijn met een negatief element wordt leidend genoemd. Daarin vinden we het maximale negatieve element in modulus, de overeenkomstige kolom is de slaaf. Als er negatieve waarden zijn tussen de vrije termen, maar niet in de overeenkomstige rij, dan heeft zo'n tabel geen oplossingen. De variabele in de leidende rij in de kolom met vrije termen wordt uitgesloten van de basis, en de variabele die overeenkomt met de leidende kolom wordt opgenomen in de basis.

Tabel 1.	fundamentele variabelen	Gratis leden onder beperkingen
Tabel 1.	fundamentele variabelen	Niet-basisvariabelen	x 1	...	x 2	...	x l
x n	xn+1	b1	een 11	...	een 12	...	een 1l
een 1n	xn+2	b2	een 21	...	een 22	...	een 2l
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
een 2n	xn+r	b2	een r1	...	een r2	...	een r
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
arn	x n+m	b m	een m1	...	een m2	...	een ml
een mn	F(x)max	F 0	-c 1	...	F 0	...	-c 2

-c n

Derde stap.

In de derde stap herberekenen we de hele simplextabel met behulp van speciale formules; deze formules kunnen worden gebruikt.

Vierde stap.

Als er na herberekening negatieve elementen over zijn in de kolom met vrije termen, ga dan naar de eerste stap, als er geen dergelijke elementen zijn, dan naar de vijfde.

Vijfde stap.

Als je de vijfde stap hebt bereikt, heb je een oplossing gevonden die acceptabel is. Dit betekent echter niet dat het optimaal is. Het zal alleen optimaal zijn als alle elementen in de F-snaar positief zijn. Als dit niet het geval is, is het noodzakelijk om de oplossing te verbeteren, waarvoor we de leidende rij en kolom vinden voor de volgende herberekening met behulp van het volgende algoritme. In eerste instantie vinden we het minimale negatieve getal in de string F, exclusief de functiewaarde. De kolom met dit nummer is de leidende kolom. Om de leidende rij te vinden, vinden we de verhouding tussen de overeenkomstige vrije term en het element uit de leidende kolom, op voorwaarde dat ze positief zijn. Met de minimale verhouding kunt u de leidende lijn bepalen. We herberekenen de tabel opnieuw met behulp van de formules, d.w.z. ga naar stap 3.

Het is noodzakelijk om een lineair programmeerprobleem op te lossen.
Doelfunctie:
2x 1 +5x 2 +3x 3 +8x 4 →min

Randvoorwaarden:

Omdat ons probleem een minimalisatieprobleem is, moeten we het omzetten in een maximaal zoekprobleem. Om dit te doen, veranderen we de tekens van de coëfficiënten van de objectieve functie in de tegenovergestelde. We schrijven de elementen van de eerste ongelijkheid ongewijzigd, voegen een extra variabele x 5 toe en veranderen het teken “≤” in “=”. Omdat de tweede en derde ongelijkheid "≥"-tekens hebben, is het noodzakelijk om de tekens van hun coëfficiënten in de tegenovergestelde te veranderen en er respectievelijk extra variabelen x 6 en x 7 in te introduceren. Als resultaat krijgen we een gelijkwaardig probleem:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

We gaan verder met het vormen van de initiële simplextabel. De coëfficiënten van de doelfunctie met het tegengestelde teken worden ingevoerd in rij F van de tabel.

					Gratis lid
F
X5
X6
X7

In de tabel die we hebben samengesteld, zijn er negatieve elementen in de kolom met vrije termen, we vinden onder hen het maximum in modulus - dit is het element: -6, het stelt de leidende rij in - X6. In deze regel vinden we ook het maximale negatieve element in modulus: -10, het bevindt zich in kolom X3, wat de leidende kolom zal zijn. De variabele in de leidende rij wordt uitgesloten van de basis, en de variabele die overeenkomt met de leidende kolom wordt opgenomen in de basis. Laten we de simplextabel opnieuw berekenen:

	X1	X2	X6	X4	Gratis lid
F	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

In de tabel die we hebben samengesteld, zijn er negatieve elementen in de kolom met vrije termen, we vinden onder hen het maximum in modulus - dit is het element: -0,4, het stelt de leidende rij in - X7. In deze regel vinden we ook het maximale negatieve element in modulus: -8,3. Het bevindt zich in kolom X2, wat de leidende kolom zal zijn. De variabele in de leidende rij wordt uitgesloten van de basis, en de variabele die overeenkomt met de leidende kolom wordt opgenomen in de basis. Laten we de simplextabel opnieuw berekenen:

	X1	X7	X6	X4	Gratis lid
F	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

Omdat er geen negatieve elementen in de kolom met vrije termen voorkomen, is er een toelaatbare oplossing gevonden die negatieve elementen bevat, wat betekent dat de resulterende oplossing niet optimaal is. Laten we de leidende kolom definiëren. Om dit te doen, zullen we in rij F het negatieve element met de maximale modulus vinden - dit is -1,988. De leidende rij zal degene zijn waarvoor de verhouding van de vrije term tot het overeenkomstige element van de leidende kolom minimaal is. De leidende rij is X2 en het leidende element is: 0,313.

	X2	X7	X6	X4	Gratis lid
F	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

Omdat er geen negatieve elementen in de string F voorkomen, is de optimale oplossing gevonden. Omdat het de oorspronkelijke taak was om het minimum te vinden, zal de optimale oplossing de vrije term van de string F zijn, genomen met het tegenovergestelde teken. F=1,924
met variabele waarden gelijk: x 3 =0,539, x 1 =0,153. De variabelen x 2 en x 4 zijn niet meegenomen in de basis, dus x 2 =0 x 4 =0.

Om twee soorten producten A en B te produceren, worden drie soorten technologische apparatuur gebruikt. Om een eenheid van product A te produceren, wordt apparatuur van het eerste type gedurende 1 uur gebruikt, apparatuur van het tweede type – 3 uur, apparatuur van het derde type – 3 uur.

Om een eenheid van product B te produceren, wordt apparatuur van het eerste type gedurende 2 uur gebruikt, apparatuur van het tweede type – 3 uur, apparatuur van het derde type – 1 uur.
Om alle producten te vervaardigen, kan een onderneming apparatuur van het eerste type maximaal 32 uur gebruiken, apparatuur van het tweede type - 60 uur, apparatuur van het derde type - 50 uur.

De winst uit de verkoop van een eenheid eindproduct A bedraagt 4 monetaire eenheden, en product B bedraagt 2 monetaire eenheden.

Stel een productieplan op voor producten A en B dat maximale winst uit de verkoop garandeert.
1) Creëer een wiskundig model van het probleem

2) Grafisch oplossen

3) Los op met behulp van de simplexmethode door simplextabellen te transformeren

Oplossing

Voor ons ligt een klassiek lineair programmeerprobleem. Een productieplan wordt opgevat als het antwoord op een eenvoudige vraag: hoeveel producten A en hoeveel producten B moeten worden geproduceerd om de winst te maximaliseren.
De winst wordt berekend met behulp van de formule: .

Laten we het wiskundige model van het probleem opschrijven:

Om het gebruik van de simplexmethode voor het oplossen van dit probleem te illustreren, gaan we het grafisch oplossen.
Om dit te doen, construeren we op de vlakke gebieden die worden beschreven door ongelijkheidsbeperkingen en een rechte lijn, die de objectieve functie wordt genoemd.

De drie hierboven geschreven ongelijkheden begrenzen een veelhoek op het vlak (in rood weergegeven), links en onder begrensd door de coördinaatassen (aangezien het vereiste aantal producten positief is).

De grafiek van de objectieve functie (in blauw weergegeven) beweegt in de richting aangegeven door de pijl (wetenschappelijk gezien in de richting van de gradiënt) totdat hij het grenspunt van de veelhoek bereikt - in ons geval is dit het punt - (15 ; 5). Op dit punt zal de doelfunctie zijn maximum bereiken.

Laten we dit probleem nu oplossen met behulp van de simplexmethode. Om dit te doen, gaan we van ongelijkheidsbeperkingen naar gelijkheidsbeperkingen door aanvullende variabelen te introduceren.

De simplextabel is als volgt samengesteld:
In de kolom Basis worden vectoren van variabelen geschreven die als basis worden beschouwd. In de eerste fase zijn dit A3, A4, A5. De basisvariabelen zijn de variabelen die elk in slechts één vergelijking van het systeem zijn opgenomen, en er is geen vergelijking die niet ten minste één van de basisvariabelen omvat.
De volgende kolom registreert de coëfficiënten van de doelfunctie die overeenkomt met elke variabele. Kolom IN - kolom voor gratis leden. Hierna volgen de kolommen met coëfficiënten Аi voor de i-de variabele.

Opgemerkt moet worden dat de schattingen voor de basisvectoren altijd nul zijn.

De simplextabel wordt als volgt geconverteerd:

Stap 1: Het optimaliteitscriterium wordt gecontroleerd, waarvan de essentie is dat alle schattingen niet-negatief mogen zijn. In ons geval wordt niet aan dit criterium voldaan, dus gaan we verder met de tweede stap.

Stap 2: Bij negatieve schattingen worden de volgende waarden berekend:

Uit deze elementen wordt degene geselecteerd waarvoor het berekende product minimaal is, in ons geval minimaal, daarom wordt het derde element van de eerste kolom, 3 (gemarkeerd in de tabel), geselecteerd als het zogenaamde oplossende element.

Stap 3: De derde rij van de tabel wordt gedeeld door 3 en afgetrokken van de eerste en tweede rij. In wezen wordt een methode gebruikt om onbekenden te elimineren, bekend als de Jordan-Gauss-methode.
Zo worden A3, A4 en A1 de nieuwe basisvariabelen.

We keren terug naar stap 1 en herhalen het hele proces.
De initiële schatting staat onder de kolom gratis leden

De overige schattingen worden onder de kolommen van de overeenkomstige vectoren geschreven.

Opgemerkt moet worden dat de schattingen voor de basisvectoren altijd nul zijn.

De antwoorden die met verschillende methoden worden verkregen, zijn hetzelfde.

Draad, knopen en stof worden gebruikt om drie soorten overhemden te maken. Voorraden draad, knopen en stof, de normen voor hun verbruik voor het naaien van één shirt staan in de tabel. Vind de maximale winst en het optimale productproductieplan dat hiervoor zorgt (vinden).

overhemd 1

overhemd 2

overhemd 3

Reserveringen

draden (m.)

knoppen (st.)

640

textiel (

Winst (r.)

Probleem oplossing

Modelbouw

Door en het aantal shirts van het 1e, 2e en 3e type dat bestemd is voor uitgifte.

Dan zien de resourcebeperkingen er als volgt uit:

Bovendien, afhankelijk van de betekenis van de taak

Doelfunctie die de ontvangen winst uitdrukt:

We krijgen het volgende lineaire programmeerprobleem:

Het reduceren van een lineair programmeerprobleem tot een canonieke vorm

Laten we het probleem terugbrengen tot een canonieke vorm. Laten we aanvullende variabelen introduceren. We introduceren alle aanvullende variabelen in de objectieve functie met een coëfficiënt gelijk aan nul. We voegen extra variabelen toe aan de linkerkant van de beperkingen die geen voorkeursvorm hebben, en we verkrijgen gelijkheden.

Het probleem oplossen met behulp van de simplexmethode

Vul de simplextabel in:

Omdat we het probleem maximaal oplossen, geeft de aanwezigheid van negatieve getallen in de indexregel bij het maximaal oplossen van het probleem aan dat we niet de optimale oplossing hebben verkregen en dat het nodig is om van de tabel van de 0e iteratie naar te gaan de volgende.

We gaan als volgt verder met de volgende iteratie:

hoofdkolom komt overeen

De sleutelrij wordt bepaald door de minimale verhouding tussen vrije leden en leden van de leidende kolom (simplexrelaties):

Op het snijpunt van de sleutelkolom en de sleutelrij vinden we het activeringselement, d.w.z. 9.

Nu gaan we verder met het compileren van de eerste iteratie: in plaats van een eenheidsvector introduceren we de vector .

In de nieuwe tabel schrijven we in plaats van het activeringselement 1, alle andere elementen van de sleutelkolom zijn nullen. De sleutelreekselementen zijn onderverdeeld in het enable-element. Alle andere elementen van de tabel worden berekend met behulp van de rechthoekregel.

De sleutelkolom voor de eerste iteratie komt overeen met

Het oplossende element is het getal 4/3. We leiden de vector af van de basis en introduceren in plaats daarvan de vector. We krijgen de tabel van de 2e iteratie.

De sleutelkolom voor de 2e iteratie komt overeen met

We vinden de sleutellijn, hiervoor definiëren we:

Het oplossende element is het getal 10/3. We leiden de vector af van de basis en introduceren in plaats daarvan de vector. We krijgen de tabel van de derde iteratie.

№

c B

Een o

x 1

x 2

x 3

x 4

x 5

x 6

Eenvoudig

relatie

x 4

32/3

x 5

640

x 6

F j - c j

-2

-5

-4

x 2

32/3

1/9

1/3

1/9

x 5

1600/3

170/9

80/3

-10/9

x 6

68/3

7/9

4/3

-2/9

F j - c j

160/3

-13/9

-7/3

5/9

x 2

-1/12

1/6

-1/4

x 5

10/3

-20

x 3

7/12

-1/6

3/4

204/7

F j - c j

-1/12

1/6

7/4

x 2

1/4

1/40

-3/4

x 1

3/10

-6

x 3

-3/4

-7/40

17/4

F j - c j

1/4

1/40

5/4

In de indexrij zijn alle termen niet-negatief, dus de volgende oplossing voor het lineaire programmeerprobleem wordt verkregen (we schrijven deze uit de kolom met vrije termen):

Het is noodzakelijk om 24 overhemden van het 1e type, 7 overhemden van het 2e type en 3 overhemden van het 3e type te naaien. In dit geval is de ontvangen winst maximaal en bedraagt deze 95 roebel.

U kunt hulp vinden bij het oplossen van uw problemen over dit onderwerp door een bericht te sturen op VKontakte, Viber of door het formulier in te vullen. De kosten voor het oplossen van huiswerk beginnen vanaf 7 BYR. per taak (200 Russische roebel), maar niet minder dan 10 Wit-Russische roebel. (RUB 300) voor de gehele bestelling. Gedetailleerd ontwerp. De kosten voor online examenassistentie (in dit geval is 100% vooruitbetaling vereist) bedragen vanaf 30 BYR. (1000 Russische roebel) voor het oplossen van het ticket.