Tabelweergave van de PPP. Simplex - tafels.

SIMPLEX-METHODE VOOR HET OPLOSSEN VAN ZLP

3.1. Algemene kenmerken en de belangrijkste fasen van de simplexmethode

De grondleggers van de simplexmethode zijn de Sovjetwiskundige L.V. Kantorovich en de Amerikaanse wiskundige J. Dantzig.

Met behulp van de simplexmethode kunt u elk probleem oplossen of de onoplosbaarheid ervan ontdekken. Veel speciale klassen van problemen kunnen worden opgelost met andere methoden die voor deze klassen effectiever zijn. Het voordeel van de simplexmethode is echter de veelzijdigheid ervan. Bijna alle computers zijn ontwikkeld standaard programma's oplossen ZLP-simplex- methode.

Laten we beschrijven algemeen idee simplex methode.

Wij zijn van mening dat de ZLP in canonieke vorm is geschreven en dat de objectieve functie moet worden geminimaliseerd. Zoals we al weten, moet het optimale plan worden gezocht tussen de basisplannen van de ZLP. De simplexmethode doorloopt niet alle referentieplannen (wat vaak onmogelijk zou zijn vanwege hun enorme aantal), maar gaat, beginnend bij een initieel referentieplan, sequentieel over naar andere referentieplannen met afnemende objectieve functie. De simplexmethode stopt met werken wanneer het optimale referentieplan is gevonden of de onoplosbaarheid van het probleem is vastgesteld.

Bij het beslissen ZLP met behulp van de simplex-methode De volgende fasen zijn te onderscheiden:

1) het PAP brengen canonieke vorm;

2) een systeem van lineaire vergelijkingen naar de Jordan-vorm brengen met niet-negatieve rechterkanten, terwijl tegelijkertijd wordt gecontroleerd op de onoplosbaarheid van de ZLP vanwege de inconsistentie van het systeem lineaire beperkingen;

3) studie van het referentieplan op optimaliteit;

4) onderzoek van de ZLP voor onbeslisbaarheid vanwege de onbegrensdheid van onderaf op de ODD van de objectieve functie;

5) transitie naar een nieuw, “beter” referentieplan.

Om records te verkleinen en te ordenen bij het oplossen van een probleem met behulp van de simplex-methode, worden zogenaamde simplex-tabellen gebruikt. Om een ​​simplextabel te gebruiken, moet de ZLP worden teruggebracht tot tabelvorm. Het is zo gedaan.

Laat de ZLP in canonieke vorm worden geschreven (2.3-2.5). Om de ZLP terug te brengen tot een tabelvorm, moet systeem (2.4) eerst worden gereduceerd tot de Jordan-vorm met niet-negatieve rechterkanten. Laten we aannemen dat deze Jordan-vorm de vorm (2.6) heeft. Laten we vanuit (2.6) de basisvariabelen uitdrukken in termen van vrije variabelen:

Door hun uitdrukkingen via vrije variabelen volgens formules (3.1) te vervangen door de objectieve functie (2.3) in plaats van de basisvariabelen, sluiten we daarmee de basisvariabelen uit van de objectieve functie. De doelfunctie zal de vorm aannemen:

IN tabelvorm de doelfunctie wordt als volgt geschreven:

Waar .

Opmerking volgende kenmerken tabelvorm van de PPP:

a) het systeem van lineaire vergelijkingen wordt teruggebracht tot de Jordan-vorm met niet-negatieve rechterkanten;

b) de basisvariabelen zijn uitgesloten van de doelfunctie en deze is geschreven in de vorm (3.3).

Laten we nu verder gaan met de beschrijving van de simplextabel. Laat de ZLP in tabelvorm worden geschreven:

(3.4)

Dan ziet de voltooide simplextabel er zo uit.

Simplexmethode voor het oplossen van problemen lineaire programmering

De simplexmethode is analytische methode ZLP-oplossingen die het algoritme implementeren grafische methode analytisch, zonder een tekening te maken.

Het punt is dus simplex methode bestaat uit een gerichte zoektocht naar haalbare oplossingen, waarbij de waarde van de doelfunctie bij elke stap beter is dan bij de vorige. Het proces wordt herhaald totdat een oplossing is verkregen die optimaal is in termen van de waarde van de doelfunctie.

De simplexmethode kan worden gebruikt om PLP's met een willekeurig aantal onbekenden op te lossen.

De technische implementatie van de simplex-methode houdt verband met het oplossen van systemen van lineaire vergelijkingen, waarvoor de Gauss-methode wordt gebruikt, tabelvormen en regels voor het converteren van simplex-tabellen zijn ontwikkeld.

Simplexmethode op natuurlijke basis is van toepassing als de bijsluiter is gespecificeerd in canonieke vorm records, en de matrix in de KZLP bevat een eenheidssubmatrix van grootte m'm. Laten we voor de zekerheid aannemen dat het eerste het geval is M De vectormatrices van het stelsel vergelijkingen vormen de identiteitsmatrix. Vervolgens wordt het initiële plan als volgt gekozen:

De optimaliteit van het referentieplan wordt gecontroleerd met behulp van het optimaliteitsteken; de overgang naar een ander plan wordt uitgevoerd met behulp van de Jordan-Gauss-transformatie met behulp van het wiskundige optimaliteitsteken. Het resulterende referentieplan wordt opnieuw gecontroleerd op optimaliteit, etc.

Het wiskundige criterium voor optimaliteit bestaat uit de volgende twee stellingen:

1. Indien voor alle vectoren A 1 , A 2 , … , Een n Waar is aan de voorwaarde voldaan , dan is het resulterende referentieplan optimaal. Totaal zelf te bepalen Z j deelnemen M termen, dat wil zeggen dat niet alle coëfficiënten van de objectieve functie eraan deelnemen c j, maar alleen met getallen die overeenkomen met de getallen van de huidige basisvectoren Een ik, waarvan het aantal gelijk is M .

2. Als voor een vector die niet in de basis is opgenomen, aan de voorwaarde is voldaan , dan moet u op zoek gaan naar een nieuw referentieplan waarvan de CF-waarde groter is dan die van het huidige. In dit geval zijn er twee gevallen mogelijk:

a) als alle componenten van de vector Een k, die in de basis moeten worden ingevoerd, zijn niet positief, dan heeft het LLP geen oplossing (er is geen eindoptimum);

b) als de vector ten minste één positieve component heeft Een k, in de basis op te nemen, dan kan een nieuw referentieplan worden verkregen.

Op basis van het optimaliteitscriterium wordt een vector in de basis geïntroduceerd Een k, wat de minimale negatieve waarde van het simplexverschil opleverde:

Om aan de voorwaarde van niet-negativiteit van de waarden van het referentieplan te voldoen, wordt de vector afgeleid van de basis Een r, wat de minimale positieve evaluatieratio oplevert

Lijn Een r, waarin de oude basisvector zich bevond, wordt de gidskolom genoemd Een k en element een rk- gidsen.

De elementen van de richtlijn in de nieuwe simplextabel worden berekend met behulp van de formules:

en eventuele andere elementen i e regel - volgens de formules:

De waarden van het nieuwe referentieplan worden berekend met behulp van vergelijkbare formules:

,

Het proces gaat door totdat een optimaal plan is verkregen of totdat de TF onbeperkt is. Als tussen de verschillen Δj, j=1, 2, …, n van het optimale plan zijn alleen de verschillen die overeenkomen met de basisvectoren nul, wat het unieke karakter van het optimale plan aangeeft. Als de nulschatting overeenkomt met een vector die niet in de basis is opgenomen, betekent dit in het algemene geval dat het optimale plan niet uniek is.

Voorbeeld. Los de ZLP op met behulp van het model:

vinden ,

onder beperkingen

Deze ZLP wordt teruggebracht tot een canonieke vorm door aanvullende variabelen te introduceren x 3 En x 4:

KZLP heeft het vereiste aantal (twee) nulkolommen x 3 En x 4, dat wil zeggen, het heeft een duidelijke initiaal referentieplan (0,0,300,150).

De oplossing wordt uitgevoerd met behulp van de simplexmethode op natuurlijke basis, waarbij de berekeningen zijn opgemaakt in simplextabellen:

Simplex tafelnummer	Basis	met j	met j					Q
B	Een 1	Een 2	Een 3	Een 4
	←Een 3
Een 4
Δ	-		-2	-3			-
I	→Een 2			1/3		1/3
←Een 4			2/3		-1/3
Δ	-		-1				-
II	Een 2					1/2	-1/2	-
→Een 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Laten we dieper ingaan op het invullen van simplextabellen en dienovereenkomstig het verkrijgen van een oplossing voor de KZLP.

IN bovenste regel coëfficiënten opgenomen in de algemene tabel cj, j=1, 2, 3, 4 met variabelen in de CF. De eerste twee rijen van de nul-simplextabel bevatten kolomvectoren B, A1, A2, A3, A4, overeenkomend met de vectorvorm van het KZLP-record. Omdat de initiële basis een paar vectoren is Een 3, een 4, zijn ze opgenomen in de kolom met de naam “Base” van de nul-simplextabel. Tegelijkertijd, Een 3 is opgenomen in de eerste rij, die wordt bepaald door de eenheid die het eerste element van deze vector is, en de vector Een 4- naar de tweede regel, voor deze vector staat de eenheid op de tweede regel. In de kolom genaamd “ c ik”de coëfficiënten van de objectieve functie die overeenkomen met de basisvectoren worden geïntroduceerd Een 3, een 4, dat wil zeggen c3, c4. Ze zijn beide gelijk aan nul. Vervolgens worden de waarden van de verschillen Δ voor de vectoren berekend B, A1, A2, A3, A4 en worden ingevoerd in de derde rij van de nultabel. Voor vectoren Een 1:

voor vector:

Insgelijks, .

Voor vectoren B het berekenen van het verschil is enigszins vereenvoudigd omdat er geen overeenkomstige coëfficiënt is cj, j=1, 2, 3, 4 in CF:

Niet voor alle vectoren Een 1, een 2, een 3, een 4 de resulterende verschillen zijn niet negatief, dus het door ons gekozen referentieplan is niet optimaal. We moeten op zoek gaan naar een nieuw referentieplan en hiervoor moeten we een van de vectoren in de basis vervangen Een 3, een 4.

Om te bepalen welke vector we moeten invoeren, zoeken we naar de vector waarvoor de verschilwaarde minimaal is. Dit is de vector Een 2, komt ermee overeen minimale waarde verschil: -3. Namelijk de index k uit formule (8.4) is gelijk aan 2. Om de vector te bepalen die we uit de basis moeten afleiden, berekenen we de waarden Q voor elke regel volgens formule (8.5) en voer ze in de laatste kolom in. IN in dit geval in elke regel hebben we de waarde van het vectorelement nodig B delen door de grootte van het vectorelement Een 2. In de eerste regel krijgen we 300/3=100, in de tweede: 150/1=150. De verhouding in de eerste rij was kleiner; de basisvector kwam ermee overeen Een 3 dus de index R in formule (8.5) is gelijk aan 1, een rk=3 (in de tabel gemarkeerd met een kader), en we zullen de vector uit de basis afleiden Een 3(aangegeven door een pijl in de tabel).

Sinds een van de elementen van de vector Een 2, die in de basis moeten worden opgenomen, zijn er positieve, dan kan een nieuw referentieplan worden verkregen en moet de oplossing worden voortgezet.

Hierna wordt de tweede simplextabel ingevuld. Om vectorelementen opnieuw te berekenen B, A1, A2, A3, A4 formules (8.6)-(8.8) worden gebruikt. Ze zijn enigszins verschillend voor het definiëren van de elementen van de hulplijn (in ons geval de eerste) en voor het definiëren van de elementen van andere lijnen. Laten we de berekeningen van verschillende elementen opschrijven:

Andere elementen van de eerste simplextabel worden op dezelfde manier berekend als voor de nultabel. Omdat niet alle verschillen in de eerste simplextabel niet-negatief zijn, wordt het noodzakelijk om door te gaan met de berekeningen.

Zoals we zien, als resultaat van berekeningen in de tweede simplextabel met basisvectoren Een 2, een 1 alle verschillen bleken niet-negatief, wat betekent dat het optimale plan werd bereikt (75; 75; 0; 0). Simplexverschil voor een vector IN gelijk aan de gewenste maximale waarde CF-375.

Stelling (over de eindigheid van het simplexalgoritme).Als er een optimaal is PPP-besluit, dan is er een fundamentele optimale oplossing. Dit laatste kan altijd worden verkregen met behulp van de simplexmethode, en u kunt vanaf elke initiële basis beginnen.

Een van de meest voorkomende en populaire optimalisatieproblemen in de logistiek is transport probleem . IN klassieke uitstraling het gaat om het vinden van het optimale ( die. geassocieerd met minimale kosten ) vrachtvervoerplan.

We hebben bijvoorbeeld een winkelketen die een bepaalde hoeveelheid goederen nodig heeft. Daarnaast zijn er een aantal leveranciersmagazijnen waar de benodigde goederen zijn opgeslagen. Bovendien heeft elk magazijn een andere hoeveelheid voorraad van deze goederen. Bovendien kennen we de tarieven: de kosten voor het transport van 1 product van elk magazijn naar elke winkel.

Er moet een transportplan worden ontwikkeld, zodat winkels de benodigde hoeveelheid goederen ontvangen tegen de laagste transportkosten. Juist in dergelijke gevallen (en in vele andere) moet het transportprobleem worden opgelost.

Theoretisch materiaal over het transportprobleem

(Monge-Kantorovich-probleem) - wiskunde probleem lineaire programmering speciaal soort over zoeken optimale verdeling homogene objecten van de batterij naar de ontvangers terwijl de reiskosten worden geminimaliseerd.

Voor het gemak van begrip wordt het beschouwd als een probleem met betrekking tot het optimale plan voor het transporteren van goederen vanaf de vertrekpunten ( bijvoorbeeld magazijnen) naar verbruikspunten ( bijvoorbeeld winkels), met minimale totale transportkosten.

Heeft de volgende vorm:

Waar: Z- kosten van het vervoeren van goederen;
X- vrachtvolume;
C- kosten (tarief) voor het vervoeren van een vrachteenheid;
A- leveranciersvoorraad;
B- verzoek van de consument;
M- aantal leveranciers;
N- aantal consumenten.

Algemeen plan voor het oplossen van een transportprobleem met behulp van de potentiële methode

Het transportprobleem kan worden opgelost verschillende methoden, beginnend bij de simplexmethode en eenvoudige opsomming, en eindigend met de . Een van de meest gebruikte en geschikte methoden voor de meeste gevallen is iteratieve verbetering van het transportplan.

De essentie ervan is als volgt: we vinden een bepaald referentieplan en controleren dit optimaliteit (Z → min). Als het plan optimaal is, is er een oplossing gevonden. Als dat niet het geval is, wordt het plan zo vaak als nodig verbeterd totdat het optimale plan is gevonden.

Hieronder staat algoritme voor het oplossen van een transportprobleem in de meest algemene vorm:

1. Een transporttafel bouwen.
2. Het probleem controleren op sluiting.
3. Het opstellen van een basisplan.
4. Controle van het ondersteuningsplan op degeneratie.
5. Berekening van de mogelijkheden voor het transportplan.
6. Controleren van het referentieplan op optimaliteit.
7. Herverdeling van voorraden.
8. Als de optimale oplossing gevonden is, ga dan naar stap 9, zo niet, ga dan naar stap 5.
9. Berekening van de totale kosten van het transport van goederen.
10. Constructie van een transportgrafiek.

Gedetailleerde instructies voor het oplossen van een transportprobleem

1. Een transporttafel bouwen

We bouwen een tabel waarin we de voorraden materialen weergeven die beschikbaar zijn in de magazijnen van leveranciers ( Ai), en de behoeften van fabrieken ( Bj) in deze materialen.

In de rechter benedenhoek van de tabelcellen voeren we de waarde in van de tarieven voor vrachtvervoer ( Cij).

2. Het probleem controleren op afsluiting

Laten we de totale vrachtvoorraad van alle leveranciers aanduiden met het symbool A, en de totale vraag naar vracht voor alle consumenten wordt gesymboliseerd B.

Het transportprobleem wordt genoemd gesloten, Als A=B. Als EEN ≠ B, dan wordt het transportprobleem genoemd open. In het geval dat gesloten probleem Alle vrachtleveringen zullen van leveranciers worden verwijderd en aan alle verzoeken van consumenten zal worden voldaan. In het geval dat openstaande taak Om dit op te lossen zul je fictieve leveranciers of consumenten moeten introduceren.

Laten we de taak controleren op afsluiting:

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, daarom is dit transportprobleem gesloten.

3. Opstellen van een referentieplan

Stelt voorlopig samen ( ondersteunen) transportplan. Het hoeft niet optimaal te zijn. Dit is slechts een soort “concept”, “schets”, waarmee we geleidelijk aan tot het optimale plan zullen komen.

Er zijn verschillende methoden voor het vinden van een referentieplan. De meest voorkomende zijn de volgende:

a) Noordwestelijke hoekmethode. Show

De essentie van de methode is eenvoudig: de cellen van de transporttabel worden opeenvolgend gevuld met de maximaal mogelijke verkeersvolumes in de richting van boven naar beneden En van links naar rechts. Dat wil zeggen dat de cel linksboven als eerste wordt gevuld ( cel "noordwest".), dan de volgende aan de rechterkant, enz. Ga dan naar nieuwe lijn en vul hem opnieuw van links naar rechts. En zo verder totdat de tafel helemaal gevuld is.

Een gedetailleerde beschrijving van de methode en een voorbeeld vindt u.

b) Minimumelementenmethode. Show

De methode is dat u, om de cellen van de transporttabel te vullen, een cel selecteert met minimaal tariefwaarde. Vervolgens wordt de volgende cel met het laagste tarief geselecteerd, enzovoort totdat de tabel gevuld is ( alle voorraden en behoeften worden op nul gezet).

c) Vogel-benadering. Show

De basis van de methode is vinden verschillen(modulo) tussen een paar minimumtarieven in elke rij en kolom. Vervolgens in de rij of kolom met grootste het verschil vult de cel de kleinste tarief. Vervolgens worden al deze acties nogmaals herhaald, alleen worden in dit geval geen rekening meer gehouden met de gevulde cellen.
Een gedetailleerde beschrijving van de Vogel-benadering en een voorbeeld zijn te vinden

d) Dubbele voorkeursmethode. Show

De essentie van de methode is dat de cellen met het laagste tarief in rijen en vervolgens in kolommen worden gemarkeerd. Vervolgens worden de cellen in de volgende volgorde gevuld: eerst de cellen met twee merken, dan met één, eindelijk zonder merktekens.
Een gedetailleerde beschrijving van de methode en een voorbeeld vindt u

4. Controle van het ondersteuningsplan op degeneratie

De cellen van de tabel waarin andere transporten dan nul zijn geregistreerd, worden opgeroepen eenvoudig, en de rest (leeg) - vrij.

Het plan wordt genoemd ontaarden, als het aantal basiscellen daarin kleiner is dan m + n -1. Als tijdens de oplossing van het probleem een ​​gedegenereerd plan wordt verkregen, moet dit worden aangevuld door nul transport in het ontbrekende aantal cellen in te voegen en daardoor deze cellen in basiscellen te veranderen ( het algehele saldo en de totale transportkosten van het plan zullen niet veranderen). Het is echter onmogelijk om het plan aan te vullen door willekeurig cellen te kiezen. Het plan moet acyclisch zijn!

Een plan wordt acyclisch genoemd als de basiscellen ervan geen cycli bevatten. Cyclus in de transporttabel zijn er verschillende cellen verbonden door een gesloten polylijn, zodat twee aangrenzende hoekpunten van de polylijn zich in dezelfde rij of in dezelfde kolom bevinden. Hieronder staat lus voorbeeld:

Een onderbroken lijn kan zelf-snijpunten hebben, maar niet in de cellen van de cyclus.

Aantal basiscellen = 5

m + n – 1 = 3 + 3 – 1 = 5

Bijgevolg is het oorspronkelijke transportplan niet gedegenereerd.

5. Berekening van de mogelijkheden voor het transportplan

Om de resulterende plannen en hun daaropvolgende verbetering te analyseren, is het handig om binnen te komen aanvullende kenmerken punten van oorsprong en bestemming, genaamd potentiëlen.

Deze methode om transportplannen te verbeteren wordt genoemd potentiële methode . Er zijn andere methoden om het transportplan iteratief te verbeteren, maar die zullen we hier niet bespreken.

Laten we dus elke leverancier Ai en elke consument Bj vergelijken met de waarden Ui En vj dienovereenkomstig, zodat voor alle basiscellen van het plan aan de volgende relatie wordt voldaan:

Ui + Vj = Cij

Voeg toe aan de transporttabel extra lijn en een kolom voor Ui en Vj.

Laten we aannemen dat U1 = 0.

Dan kunnen we V3 = C13 – U1 = 1 – 0 = 1 vinden.

Als we V3 kennen, kunnen we nu U3 vinden:

Naar analogie berekenen we alle resterende potentiëlen:

6. Het plan controleren op optimaliteit met behulp van de potentiële methode

Voor elke vrije cel van het plan berekenen we de verschillen

ΔCij = Cij – (Ui + Vj)

en schrijf de resulterende waarden in de linkerbenedenhoek van de overeenkomstige cellen.

Het plan is optimaal, als alle verschillen ΔCij ≥ 0.

In dit geval is het plan suboptimaal(AC22< 0), и его следует улучшить путем перераспределения поставок.

7. Herverdeling van voorraden

Laten we de cel met de grootste vinden absolute waarde negatief verschil ΔCij en construeer een cyclus waarin, behalve deze cel, alle andere basisch zijn. Zo'n cyclus bestaat altijd en is uniek.

Laten we de cel met een negatief verschil ΔCij markeren met een “+” teken, de volgende met een “-” teken, enzovoort, één voor één.

Vervolgens vinden we de minimale waarde van de belasting in de cellen van de cyclus met het teken “-” (hier is het 5) en voeren deze in de vrije cel in met het teken “+”. Vervolgens doorlopen we achtereenvolgens alle cellen van de cyclus, waarbij we afwisselend de minimumwaarde aftrekken en optellen (in overeenstemming met de tekens waarmee deze cellen zijn gemarkeerd: waar min wordt afgetrokken, waar plus wordt opgeteld).

Wij krijgen nieuw referentieplan vervoer:

Omdat er meer basiscellen zijn dan m+n – 1, is er sprake van een basiscel nul waarde maak het gratis:

We berekenen opnieuw de potentiële waarden en het verschil ΔCij:

Deze keer zijn alle verschillen ΔCij van de cellen positief, daarom optimale oplossing gevonden.

8. Als de optimale oplossing gevonden is, ga dan naar stap 9, zo niet, ga dan naar stap 5.

We hebben de optimale oplossing gevonden, dus ga verder met punt 9.

9. Berekening van de totale kosten van het transport van goederen

Laten we berekenen totale verzendkosten vracht ( Z), overeenkomend met het optimale plan dat we hebben gevonden, volgens de formule:

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 den. eenheden

Totale verzendkosten voor alle producten, bijv optimale oplossing, make-up 110 den. eenheden

10. Constructie van een transportgrafiek

Nadat we het optimale transportplan hebben gevonden, zullen we bouwen. De hoekpunten van de grafiek zijn “magazijnen” en “winkels”. Bij de hoekpunten geven we de overeenkomstige volumes aan reserves en behoeften aan. Bogen die de hoekpunten van de grafiek verbinden, komen overeen met transporten die niet nul zijn. We zullen elke dergelijke boog ondertekenen, waarbij het volume van de vervoerde vracht wordt aangegeven.

Het resultaat is een grafiek die lijkt op de onderstaande grafiek:

Dat is alles, het transportprobleem is opgelost. Gefeliciteerd!

Praktische toepassing van het transportprobleem

In veel gevallen wordt gebruik gemaakt van het transportprobleem. Dit is het optimaliseren van de aanvoer van grondstoffen en benodigdheden productiebedrijven. Dit is de optimalisatie van de levering van goederen van magazijnen naar winkels. Dit is de optimalisatie van het passagiersvervoer, en nog veel, veel meer.

Galjautdinov R.R.

© Het kopiëren van materiaal is alleen toegestaan ​​als er een directe hyperlink naar is

Teken van optimaliteit van het referentieplan

Als in een simplextabel die een bepaald ondersteuningsplan bevat, alle elementen van de f-rij (behalve de vrije term) niet-negatief zijn, dan is dit ondersteuningsplan optimaal. Laat de f-rij van de tabel binnen. 2.b 0j > (i=1, ..., n·m). In het referentieplan x 0 in deze tabel zijn de waarden van alle vrije variabelen x m+j gelijk aan nul en f(x 0) =b 00. Als je één van de vrije variabelen x m+ j vergroot, dan zal, zoals blijkt uit gelijkheid (2.5), vanwege de niet-negativiteit van b 0j, de waarde van f(x) beginnen af ​​te nemen. Bijgevolg bereikt bij x o de functie f(x) zijn grootste waarde, wat betekent dat x 0 inderdaad het optimale referentieplan is.

Mogelijkheid om van het ene referentieplan naar het andere te gaan

Zoals hierboven vermeld, is de essentie van de simplexmethode het proces van het bewijzen van het volgende criterium: als er in de f-rij van een simplextabel die een referentieplan bevat, er minstens één negatief element is (de vrije term niet meegerekend), dat overeenkomt met een kolom met minstens één positief element, dan kunt u, door de basis te transformeren, overstappen naar een ander referentieplan met een grotere waarde van de doelfunctie.

Laten we dit teken bewijzen. Laten we de regels vaststellen voor het selecteren van variabelen voor een dergelijke transformatie van de initiële basis Bo met een referentieplan x 0 inch nieuwe basis B 1 met een referentieplan x 1 waarin; de waarde van de functie f neemt toe, d.w.z. f(x i)>f(x 0). Vervolgens transformeren we ze, volgens de regel voor het herberekenen van elementen uit de simplextabel, naar een nieuwe basis, waardoor we de componenten van het nieuwe referentieplan kunnen vinden.

Laten we dat in de tabel aannemen. 2.1, bijvoorbeeld b 0s<0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) welke van de variabelen uit de vorige basis moet worden verwijderd om ruimte te maken voor de variabele x m+s;

2) welke waarde moet de nieuwe basisvariabele x m+s aannemen in het nieuwe referentieplan.

Om de gestelde vragen op te lossen, nemen we aan dat in gelijkheden (2.4) alle x m+j, behalve x m+s, gelijk zijn aan nul. Dan

x ik = b io -b is x m+s (i=l, ..., m)

Uit deze gelijkheden blijkt duidelijk dat bij toenemende x m+s de waarden van die basisvariabelen x i waarvoor de coëfficiënten b zijn<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. Naarmate x m+s toeneemt, zullen de waarden van deze variabelen beginnen af ​​te nemen, en er zal een moment komen waarop ze negatieve waarden zullen aannemen en aan voorwaarde (2.3) niet langer zal worden voldaan. Dit kan niet worden toegestaan. Laten we daarom uitzoeken tot welke grenswaarde x m+s kan worden verhoogd zonder de voorwaarde van niet-negativiteit van de basisvariabelen te schenden. Voor dit doel schrijven we uit systeem (2.6) die gelijkheden uit waarin b >0 is. Laten we aannemen dat het om gelijkheden gaat met getallen i=d,…,k,…,p:

x d =b doen -- b ds x m+s ,

…………………..

x k =b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

De basisvariabelen x d, ..., x k, ..., x p blijven niet-negatief zolang x m+s voldoet aan het systeem van ongelijkheden

b do - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 of x m+s< b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s< b po /b ps

d.w.z. bij x m+s

Laat de kleinste van de breuken b io /b overeenkomen met i = k, d.w.z.

min ( b io /b is )= b k0 /b ks .

Dan kunnen we zeggen dat zolang x m+s de waarde b k0 /b ks niet overschrijdt, d.w.z. x m+s 0, dan wordt de variabele x k gelijk aan het opsommingsteken: x k = b k0 -- b ks b ko /b ks =0, en daardoor wordt de basis getransformeerd B o = (x 1 ; ...; x k ; . ..; x m ) naar een nieuwe basis, waarin de variabele x m+s van de vrije groep naar de basis gaat, en de variabele x k de plaats inneemt van x m+s in de vrije groep. Tegelijkertijd zijn alle andere vrije variabelen nog steeds gelijk aan nul en zijn de overige basisvariabelen nog steeds positief. Bijgevolg zal het basisplan x 1 in de nieuwe basis B 1 = (x 1 ; ...; x m+s ; ...; x m ) m positieve componenten hebben en m-n nul. In het x 1-plan kunnen sommige basisvariabelen in twee gevallen nulwaarden aannemen:

1) wanneer er in plan x 0 basisvariabelen gelijk aan nul zijn;

2) wanneer de kleinste van de breuken b io /b is zal overeenkomen met twee of meer getallen i. In ons geval komt dit alleen overeen met i = k.

De in de basis op te nemen variabele wordt bepaald door het negatieve element van de f-string. Uit de gelijkheid f =boo - b os x m+s blijkt dat wanneer b 0s<0 и фиксированном x m+s >0, de waarde van f(x) hangt af van de absolute waarde van de coëfficiënt b 0s: hoe groter |b 0s |, hoe groter de waarde f(x) zal krijgen in de nieuwe basis. Maar uit deze gelijkheid wordt ook duidelijk dat de waarde van de doelfunctie in de nieuwe basis ook afhangt van de waarde die wordt aangenomen door de nieuwe basisvariabele x m+s. We zullen een variabele kiezen die in de basis wordt geïntroduceerd, waarbij we ons alleen concentreren op de negatieve elementen van de f-rij. Als er meerdere negatieve elementen in de f-rij voorkomen, zullen we daarom in de basis de variabele x m+j introduceren die overeenkomt met het negatieve element met de grootste absolute waarde. De kolom met coëfficiënten voor een variabele die in de basis is opgenomen, wordt oplossen genoemd. Door dus een variabele te kiezen die in de basis wordt geïntroduceerd (of een oplossende kolom te kiezen) op basis van het negatieve element van de f-rij, zorgen we ervoor dat de functie f toeneemt.

Het is iets moeilijker om te bepalen welke variabele moet worden uitgesloten van de basis. Om dit te doen, stellen ze de verhoudingen samen van vrije termen tot de positieve elementen van de oplossende kolom (dergelijke relaties worden simplex genoemd) en vinden ze de kleinste daarvan, die de rij (oplossen) bepaalt die de uitgesloten variabele bevat. De keuze van een variabele die is uitgesloten van de basis (of de keuze van een ontbindende lijn) volgens de minimale simplexrelatie garandeert de positiviteit van de basiscomponenten in het nieuwe referentieplan.

We hebben dus bewezen dat het onder de voorwaarden gespecificeerd in het bord inderdaad mogelijk is om van het ene referentieplan naar het andere te gaan met een grote waarde van de doelfunctie f(x).

Merk op dat we de waarde van de nieuwe basisvariabele x m+s in het nieuwe referentieplan al kennen: deze is gelijk aan b ko /b ks . Wat betreft de numerieke waarden van de resterende basisvariabelen in het nieuwe referentieplan en de overeenkomstige waarde van f(x), deze kunnen pas worden gevonden na het gewijzigde systeem van basisvariabelen x 1;..., x m+s ; ...,x m wordt uitgedrukt via een aangepast systeem van vrije variabelen x m+1,…,x k,…, x n. Om dit te doen, stellen we in; regels waarmee de voorwaarden van een probleem van de ene basis naar de andere worden getransformeerd.

De coëfficiënt b ks = 0 bij x m+s in deze vergelijking wordt het oplossende element genoemd. In gelijkheid (2.7) wordt de nieuwe basisvariabele x m+s uitgedrukt in termen van vrije variabelen, waaronder de voormalige basisvariabele x k zich nu bevindt. De variabelen x m+s en x k wisselden dus van rol.

Laten we op dezelfde manier de resterende basisvariabelen uitdrukken via een nieuwe reeks vrije variabelen. Voor dit doel vervangen we de waarde x m+s door de resterende gelijkheden (we geven f aan met x 0, dan wordt de gelijkheid in het systeem opgenomen bij i = 0)

Een systeem naar een nieuwe basis brengen wordt een simplextransformatie genoemd. Als de simplextransformatie wordt beschouwd als een formele algebraïsche operatie, kunnen we opmerken dat als gevolg van deze operatie de rollen worden herverdeeld tussen twee variabelen die deel uitmaken van een bepaald systeem van lineaire functies: de ene variabele gaat van afhankelijk naar onafhankelijk, en de andere , integendeel, van onafhankelijk naar afhankelijk. Deze bewerking staat in de algebra bekend als de Jordan-eliminatiestap.

123 pagina's (Word-bestand)

Bekijk alle pagina's

Fragment van de tekst van het werk

Overgang van het ene referentieplan naar het andere, waarbij de waarde van de doelfunctie groter is dan in het vorige.

3. Het controleren van de optimaliteit van het resulterende plan, zodat u direct kunt stoppen met zoeken naar referentieplannen of tot de conclusie kunt komen dat er geen optimaal plan bestaat.

De simplexmethode is gebaseerd op de volgende stellingen, die zonder bewijs worden gegeven.

Stelling 1.2 (over het bestaan ​​van een steunplan)

Als een lineaire vorm van bovenaf wordt begrensd op een niet-lege verzameling D, dan is de LLP oplosbaar, dat wil zeggen dat er een punt bestaat zodat .

Stelling 1.3 (toets voor de optimaliteit van het ondersteuningsplan)

Basisplan probleem (1.18) is optimaal als voor alle j , is voldaan, waarbij de hoeveelheid

(1.21)

genaamd simplex - verschil of onderzoek.

Stelling 1.4 (test op de afwezigheid van een optimaal plan)

Als er voor sommige k en onder de getallen geen positieve zijn, d.w.z. Alles bij elkaar is de objectieve functie van het probleem niet beperkt tot de reeks haalbare oplossingen en kent het geen definitieve oplossing.

Stelling 1.5 (test voor het bestaan ​​van een beter ondersteuningsplan)

Als het referentieplan probleem (1.18) is niet gedegenereerd voor sommige k, maar onder de getallen is er minstens één positief, d.w.z. niet alles, dan is er een referentieplan , waarin de doelfunctie een waarde aanneemt die niet minder is dan in het vorige plan: .

Simplex-methode-algoritme

1. Het probleem moet worden teruggebracht tot een canonieke vorm. Het systeem van beperkingen wordt teruggebracht tot een eenheidsbasis, d.w.z. wordt opgelost met betrekking tot enkele basisvariabelen (zonder verlies van algemeenheid, nemen we aan met betrekking tot de eerste m variabelen) met behulp van de Jordan-Gauss-methode (systeem (1.19)). De overeenkomstige initiële referentieoplossing wordt verkregen.

2. Voor het gemak van de berekeningen schrijven we alles in een simplextabel (Tabel 1.1). De Basiskolom bevat een lijst met basisvariabelen; de volgende kolom “c j basis” bevat de coëfficiënten van de doelfunctie voor de basisvariabelen; de volgende kolommen bevatten de coëfficiënten van het restrictiesysteem voor de overeenkomstige variabelen; kolom “b i” is een kolom met vrije leden van het systeem van beperkingen. De laatste regel bevat de simplex - verschillen berekend met formule (1.21) en de laatste cel bevat de waarde van de doelfunctie =. Merk op dat de simplex – de verschillen tussen de basisvariabelen – altijd gelijk is aan nul.

Tabel 1.1

		c j-basis

3. Als alles simplex is, zijn de verschillen niet-negatief, d.w.z. , dan is het referentieplan optimaal.

4. Als ten minste één simplex-verschil negatief is, en er geen positieve elementen in de overeenkomstige kolom staan, dan heeft het probleem geen optimale oplossing, d.w.z. .

5. Als ten minste één simplexverschil negatief is, en in elke kolom die een negatieve score heeft, is er ten minste één positief element aanwezig, dan kan het resulterende referentieplan worden verbeterd.

6. Kies kolom inschakelen“p”, wat overeenkomt met de kleinste negatieve score.

7. Kies toestemmingsreeks“k”, wat overeenkomt met de kleinste verhouding van de rechterkant tot de overeenkomstige positieve elementen van de resolutiekolom. Het element op het snijpunt van de resolutiekolom en de resolutierij wordt aangeroepen tolerant element.

8. We gaan verder met een nieuwe simplextabel, waarin er een nieuwe basis komt: de basisvariabele op de “k”-plaats in de oude basis wordt gewijzigd in een nieuwe variabele. De corresponderende vector van de nieuwe basisvariabele moet worden omgezet in een eenheid. Om dit te doen deelt u de resolutielijn door zodat er een eenheid verschijnt in plaats van het resolutie-element. Door de resolutielijn met geschikte getallen te vermenigvuldigen en deze op te tellen bij de rest van de lijnen, krijgen we nullen in de resolutiekolom. Hierna schrijven we een nieuw referentieplan uit en herberekenen we de schattingslijn. Laten we verder gaan met punt 3.

Een opmerking over het alternatieve plan.

Als alle schattingen van vrije variabelen in de laatste simplextabel strikt groter dan nul blijken te zijn, dan is het optimale plan uniek. Als ten minste één schatting voor een vrije variabele gelijk is aan nul, dan is er een alternatief optimum (een reeks optimale plannen). Om een ​​alternatieve oplossing te vinden, is het noodzakelijk om één stap van de simplexmethode te nemen, waarbij u de oplossingskolom van de vrije variabele kiest, wat overeenkomt met een nulscore.

In dit geval kan de verzameling van alle optimale plannen worden weergegeven als een convexe lineaire combinatie van ondersteunende optimale plannen: , Waar .

Voorbeeld 5. Los de ZLP op met behulp van de simplexmethode:

(1.22)

We reduceren het systeem van lineaire ongelijkheden (1.22) tot een canonieke vorm door een extra niet-negatieve variabele in elke ongelijkheid te introduceren. We verkrijgen een systeem van lineaire vergelijkingen:

(1.23)

De doelfunctie heeft de vorm

Laten we een simplextabel maken:

Tabel 1.2

		c j-basis

Basisplan is niet optimaal, omdat in de beoordelingsregel zijn er negatieve elementen = - 3 en = - 2. We selecteren de oplossingskolom - de eerste, omdat het komt overeen met het minimum aan negatieve schattingen = - 3. Voor alle positieve elementen van de eerste kolom berekenen we de verhouding . We vinden het minimum van deze verhoudingen: . Het komt overeen met de tweede regel en is daarom tolerant. Het oplossende element laat dus zien dat de variabele x 4 is afgeleid van de basis, en dat er in plaats daarvan een variabele x 1 in de basis zal zitten. We vullen een nieuwe simplextabel in (Tabel 1.3). Om dit te doen, veranderen we de eerste kolom in een enkele kolom. We vermenigvuldigen de tweede regel met (-1/2) en tellen deze op bij de eerste, schrijven het resultaat in de eerste regel van de nieuwe simplextabel; vermenigvuldig op dezelfde manier de tweede regel met (1/2) en tel deze op bij de derde; deel de resolutielijn door 2; We herschrijven de vierde zonder wijzigingen.