Simplex-methode van lineaire programmering
Simplex-methode van lineaire programmering!
Elk lineair programmeringsprobleem met twee variabelen kan eenvoudig worden opgelost met behulp van de grafische methode, omdat het gemakkelijker is om met tweedimensionale grafieken om te gaan. Alle haalbare oplossingen in grafische methode liggen binnen het haalbare gebied in de grafiek en we testten de hoekpunten van het haalbare gebied voor de optimale oplossing, dat wil zeggen dat een van de hoekpunten van het haalbare gebied de optimale oplossing was. We testten alle hoekpunten door deze waarde in objectieve functie te plaatsen.
Maar als het aantal variabelen van twee toeneemt, wordt het erg moeilijk om het probleem op te lossen door de grafiek ervan te tekenen, omdat het probleem te ingewikkeld wordt. Simplex-methode is ontwikkeld door GB Dantzig, een Amerikaanse wiskundige.
Deze methode is een wiskundige behandeling van de grafische methode. Hier worden ook verschillende hoekpunten van het haalbare gebied op optimaliteit getest. Maar het is niet mogelijk om alle hoekpunten te testen omdat het aantal hoekpunten de variëteiten vergroot als het aantal vergelijkingen en variabelen toeneemt. Het maximale aantal te testen punten zou kunnen zijn
m + n m = m + 1! / m! n!
waar m het aantal is en n het aantal variabelen.
In de simplex-methode wordt het aantal te testen hoekpunten dus aanzienlijk verminderd door een zeer effectief algoritme te gebruiken dat ons in slechts enkele iteraties naar een optimaal oplossingshoekpunt leidt. Laten we een voorbeeld nemen en stap voor stap verder gaan.
Objectieve functie is om Z = 12x 1 + 15x 2 + 14x 3 te maximaliseren
Afhankelijk van de voorwaarden
Stap 1:
(a) De rechterkant van alle beperkingen moet nul of + ve zijn. Als ze -ve zijn, moeten ze + worden gemaakt door beide te vermenigvuldigen met (-1) en het teken van ongelijkheid wordt omgekeerd. In dit voorbeeld is RHS al + ve of nul.
(b) Alle ongelijkheden worden omgezet in gelijkheden door het toevoegen of aftrekken van slappe of overtollige variabelen. Deze slappe of overtollige variabelen worden geïntroduceerd omdat het gemakkelijker is om met gelijkheden om te gaan dan ongelijkheden in wiskundige behandeling.
Als constraint ≤ type is, worden de slack-variabelen toegevoegd als constraint ≥ type is, waarna de surplus-variabele wordt afgetrokken. Hier worden slappe variabelen s,, s 2 en s 3 toegevoegd in drie in gelijkheden (i), (ii) en (iii), die we krijgen.
En objectieve functie wordt
Maximaliseer Z = 12x 1 + 15x 2 + 14x 3 + os 1 + os 2 + os 3
Stap 2:
Vind de eerste Basic Feasible Solution:
We beginnen met een haalbare oplossing en gaan vervolgens naar optimale oplossing in volgende iteraties. De aanvankelijk haalbare oplossing wordt bij voorkeur gekozen om de oorsprong te zijn, dwz waar de reguliere variabelen, bijvoorbeeld in dit geval x v x 2, x 3 uitgaan van nulwaarden. dat wil zeggen x 1 x 2, x 3 = 0
en we krijgen s 1 = 0, s 2 = 0 en s 3 = 100 van ongelijkheden (i), (ii) en (iii)
Basisvariabelen zijn de variabelen die zich momenteel in de oplossing bevinden, bijv. S v S 2 en S 3 zijn de basisvariabelen in de initiële oplossing.
Niet-basisvariabelen zijn de variabelen die gelijk zijn aan nul en die niet in de huidige oplossing zijn, bijvoorbeeld x 1 en x 2 en x 3 zijn de niet-basisvariabelen in de initiële oplossing.
De bovenstaande informatie kan worden uitgedrukt in tabel 1
In de tabel geeft de eerste rij coëfficiënten van de objectieve functie weer, de tweede rij staat voor verschillende variabelen (eerste reguliere variabelen dan speling / overschotvariabelen). De derde vierde en vijfde rij vertegenwoordigen variabelencoëfficiënten in alle beperkingen.
Eerste kolom vertegenwoordigt coëfficiënten van basisvariabelen (huidige oplossingsvariabelen) in de objectieve (e i ) tweede kolom vertegenwoordigen basisvariabelen (huidige oplossingsvariabelen) en laatste kolom vertegenwoordigt, rechterzijde van de beperkingen in standaardvorm. Dwz na het congestie van alle ongelijkheden in gelijkheden, in elke tabel, wordt de huidige waarde van de huidige oplossingsvariabelen (basisvariabelen) gegeven door RHS
In tabel 1 is de huidige oplossing:
S 1 = 0, S 2 = 0, S 3 = 100
Natuurlijk zullen de niet-basisvariabelen X v X 2 en X 3 ook nul zijn
Degeneratie wanneer een basisvariabele nulwaarden aanneemt, de huidige oplossing is gedegenereerd zoals in het huidige probleem S 1 = 0 en S 2 = 0 het probleem kan verder worden opgelost door S 1 = t te vervangen en S 2 = t waar t is heel klein + ve-nummer.
Stap 3:
Optimaliteitstest.
Optimaliteitstest kan worden uitgevoerd om te bepalen of de huidige oplossing optimaal is of niet. Schrijf voor deze eerste laatste rij in de vorm van (E j ) waar
Ej = Σ ei. A ij.
Wanneer een ij coëfficiënten vertegenwoordigt in de identiteitsmatrix van het lichaam voor de rij & jde kolom, dat wil zeggen, staat voor de eerste kolom van de tabel. Schrijf in de laatste rij de waarde van (Cj - Ej) waar c ; vertegenwoordigt de waarden van de eerste rij en Ej vertegenwoordigt de waarden van de laatste rij. (Cj - Ej) vertegenwoordigt het voordeel van het brengen van een niet-basisvariabele in de huidige oplossing, dwz door het basaal te maken.
In tabel 2 zijn de waarden van Cj - Ej 12, 15 en 14 voor X v X 2 en X 3 . Als een van de waarden van Cj - Ej + is, betekent dit dat de meeste positieve waarden de variabele vertegenwoordigen die in de huidige oplossing wordt gebracht om de doelfunctie maximaal te vergroten. In het huidige geval is X2 de potentiële variabele om in de oplossing voor de volgende iteratie te komen. Als alle waarden in de rij (Cj - Ej) negatief zijn, betekent dit dat de optimale oplossing is bereikt.
Stap 4:
Itereren naar optimale oplossing:
Maximum de waarde van Cj - Ej geeft toetskleur zoals aangegeven in de tabel
Daarom is X 2 de invoervariabele, dwz het zou basaal worden en de oplossing zou binnendringen. Uit de bestaande niet-basisvariabele, en iemand moet uitgaan en niet-fundamenteel worden. Om te achterhalen welke variabele moet worden verdreven, deel ik de coëfficiënten in de RHS-kolom door de bijbehorende coëfficiënten in de sleutelkolom om de kolom Verhoudingen te krijgen. Zoek nu naar de minst positieve waarde in de kolom Verhouding en die geeft de toetsenrij. In het huidige probleem hebben we drie waarden, dwz t, μ en 100 en hiervan is t de minste + ve. Daarom is rij die overeenkomt met de kolom t in Verhouding de sleutelrij. En S., zou de vertrekkende variabele zijn. Element op het snijpunt van toetsenrij en toetskleur is het belangrijkste element.
Nu moeten alle elementen in de toets, behalve het sleutelelement, nul worden gemaakt en moet het sleutelelement eenheid worden. Dit gebeurt met behulp van rijbewerkingen zoals gedaan is de matrices. Hier is het sleutelelement al een eenheid en een ander element in de toetskleur wordt nul gemaakt door -1 keer de eerste rij in de derde rij toe te voegen en de volgende tafel te krijgen.
Daarom wordt een tweede haalbare oplossing
X 1 = 0, X 2 = t en X 3 = 0 daar met z = 15t
In de nieuwe tabel is s 1 vervangen door X 2 in de basisvariabelen en dienovereenkomstig is ook ei coloumn gewijzigd.
Stap 5:
Bij het bekijken van de Cj-E-waarden in Tabel 3, vinden we dat xl de meeste + ve-waarden van 27 heeft, waarmee wordt aangegeven dat de oplossing verder kan worden verbeterd door x 1 in de oplossing te brengen, dwz door het basaal te maken. Daarom is x 1 coloumn de belangrijkste kolom, vind ook de sleutelrij zoals eerder uitgelegd en voltooi tabel 5.
Het sleutelelement in Tabel 5 is 2 en het is eenheid en alle andere elementen in de sorteerkolom zijn nul gemaakt met behulp van rijbewerkingen en uiteindelijk krijgen we Tabel 6. Het eerste belangrijke element is eenheid door die rij te delen door 2. Vervolgens wordt door het toevoegen van geschikte veelvouden van die rij in een andere rij tabel 6 verkregen.
Uit tabel 6 is te zien dat de oplossing nog steeds niet optimaal is, omdat Cj-Ej nog steeds is + ve-waarden is 1/2, dit geeft de codekolom en de bijbehorende sleutellijst is gevonden, het belangrijkste element is gemaakt zoals weergegeven in Tabel 7
Door geschikte rijbewerkingen maken we andere elementen in de toetskleur nul, zoals weergegeven in Tabel 8.
Zoals te zien is, omdat alle waarden in Cj-Ej rij ofwel -ve of nul zijn, is een optimale oplossing bereikt.
De uiteindelijke oplossing is x 1 = 40 ton
x 2 = 40 ton
x 3 = 20 ton
aangezien t erg klein is, wordt het verwaarloosd.
Voorbeeld 1:
Los het volgende probleem op met de simplex-methode
Maximaliseer Z = 5x 1 + 4x 2
Onderworpen aan 6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
-x 1 + x 2 ≤ 1
x 2 ≤ 2
en x 1 x 2 ≥0
Oplossing:
Voeg slappe variabelen S 1, S 2, S 3, S 4 in de vier beperkingen toe om ongelijkheden te verwijderen.
We krijgen 6x 1 + 4x 2 + s 1 = 24
x 1 + 2x 2 + s 2 = 6
-x 1 + x 2 + s 3 = 1
x 2 + s 4 = 2
Onderworpen aan x 1, x 2, s 1, s 2, s 3 & s 4 > 0
Objectieve functie wordt
Maximaliseren Z = 5x 1 + 4x 2 0s 1 + 0s 2 + 0s 3 + 0s 4
Tabel 1 die wordt gevormd, wordt hieronder gegeven. Men ziet dat X 1 de invoervariabele is en S, de vertrekkende variabele. Sleutelelement in Tabel 1 is eenheid en al het andere element in die kleur is nul gemaakt.
Uit tabel 2 kan het zijn dat X2 de invoervariabele is en S2 de vertrekkende variabele.
Uit tabel 5 is te zien dat alle waarden van Cj-Ej rij ofwel -ve of nul zijn. Daarom is een optimale oplossing verkregen.
Oplossing is x 1 = 3, x 2 = 3/2
Z max = 5x 3 + 4x = 3/2
= 15 + 6 = 21 Ans.
Grote M-methode
Laten we het volgende probleem nemen om de Big M-methode te illustreren.
Minimaliseren Z = 2y 1 + 3y 2
onderhevig aan beperkingen y 1 + y 2 ≥ 5
y 1 + 2y 2 ≥ 6
y 1, y 2 ≥ 0
Converteren naar standaardformulier:
Maximaliseren Z = -2y 1 - 3y 2 + Os, + 0s 2
maw het probleem van minimalisatie wordt geconverteerd naar maximalisatieprobleem door RHS van objectieve functie te vermenigvuldigen met -1.
Beperkingen y 1 + y 2 - s 1 = 6 ... (i)
y, + y 2 - s 2 = 6 ... (ii)
y 1 y 2, s 1 s 2 ≥ 0
Hier overtollige variabelen sl, s2 en afgetrokken van respectievelijk de beperkingen (i) en (ii).
Nu kan y 1, y 2 als niet-basisvariabelen worden genomen en gelijk aan nul worden gezet om s v s 2 te krijgen als basisvariabelen waarbij s 1 = -5, s 2 = -6.
Dit is een onhaalbare oplossing omdat de overschotvariabelen s 1 en s 2 get -ve-waarden hebben. Om dit probleem te verhelpen, voegen we kunstmatige variabelen A 1 en A 2 in eqn toe. (i) en (ii) respectievelijk te krijgen
y 1 + y 2 -s 1 + A 1 = 5 ... (iii)
y 1 + 2y 2 - s 2 + A 2 = 6 ... (iv)
Waar y 1 y 2, s 1, s 2, A 1, A 2 ≥ 0
en de objectieve functie wordt
Maximaliseren Z 1 = -2y 1 - 3y 2 + 0s 1 + 0s 2 - MA 1 - MA 2
Er kan worden opgemerkt dat we met opzet zeer zware straffen hebben toegepast op kunstmatige variabelen in de objectieve functie in de vorm van -MA1 en MA2, waarbij M een zeer groot + ve-getal is. Het doel hiervan is dat de kunstmatige variabelen aanvankelijk in de startende basisoplossing verschijnen.
Omdat kunstmatige variabelen de objectieve functie in grote mate verminderen in het geval van straffen, drijft simplex-algoritme de kunstmatige variabelen uit de oplossing in de initiële iteraties en daarom verschijnen de kunstmatige variabelen die we hebben geïntroduceerd om het probleem verder op te lossen niet in de finale oplossing. Kunstmatige variabelen zijn slechts een computationeel apparaat. Ze houden de startvergelijkingen in evenwicht en bieden een wiskundige truc om een startoplossing te krijgen.
De begintabel wordt
Omdat Cj-Ej + is onder sommige kolommen, is oplossing gegeven door Tabel 1 niet optimaal. Het is duidelijk dat van -2 + 2M en -3 + 3M, -3 + 3M het meest + ve is, omdat M een zeer groot + ve-getal is. Het sleutelelement is gevonden zoals weergegeven in tabel 1 en het is gemaakt als eenheid en alle andere elementen in deze kolom zijn nul gemaakt. We krijgen tabel 2.
Uit Tabel 2 kan worden afgeleid dat de optimale oplossing nog steeds niet wordt bereikt en dat er een betere oplossing bestaat. Y 1 is de binnenkomende variabele en A 1 is de uitgaande variabele. We krijgen tabel 3.
Uit tabel 3 is te zien dat de optimale oplossing is bereikt en de oplossing is
Y 1 = 4, Y 2 = 1
Minimale waarde van Z = 2x 4 + 3x 1 = 11 eenheden Ans.
Ongebonden oplossing:
Een Lineair Programmeringsprobleem zou een onbegrensde oplossing hebben als we in de verhoudingskolom alle ingangen -ve of nul krijgen en er is geen + ve-invoer. Dit geeft aan dat de waarde van de inkomende variabele die is geselecteerd uit de sleutelcollectie zo groot kan zijn als we willen zonder de haalbare situatie te schenden en het probleem zou onbegrensde oplossing zijn.
Oneindig aantal oplossingen:
Een Lineair Programmeringsprobleem heeft naar verluidt een oneindig aantal oplossingen als tijdens elke iteratie, in de Cj-Ej rij, we alle waarden nul of -ve hebben. Het laat zien dat de optimale waarde is bereikt. Maar aangezien een van de reguliere variabelen een nulwaarde heeft in de Cj-Ej rij, kan worden geconcludeerd dat er een alternatieve optimale oplossing bestaat.
Een voorbeeld van dit type tabel wordt hieronder gegeven.
Het is duidelijk dat de optimale oplossing is bereikt, omdat alle waarden in de rij Cj-Ej nul of -ve zijn. Maar X 1 is een niet-basisvariabele en deze heeft een nulwaarde in de Cj-Ej-rij, het geeft aan dat X kan worden ingevoerd oplossing, maar het verhoogt de waarde van de objectieve functie niet en er bestaat een alternatief optimum.
Case of No. Feasible Solution:
In sommige LPP is te zien dat tijdens het oplossen van problemen met kunstmatige variabelen, de rij Cj-Ej aantoont dat de optimale oplossing is bereikt, terwijl we nog steeds een kunstmatige variabele in de huidige oplossing hebben met een + vp-waarde. In dergelijke situaties kan worden geconcludeerd dat het probleem helemaal geen haalbare oplossing biedt.
Voorbeeld 2:
Oplossing:
Om het probleem op te lossen, moeten kunstmatige variabelen in LHS worden toegevoegd om de eerste, voor de basis haalbare oplossing te krijgen. Laten we kunstmatige variabelen A 1, A 2, A 3 introduceren, de bovenstaande beperkingen kunnen worden geschreven als.
Als deze kunstmatige variabelen nu verschijnen in de uiteindelijke oplossing door enkele + ve-waarden te hebben, raakt de gelijkheid van vergelijking (i), (ii) of (iii) gestoord. Daarom willen we dat kunstmatige variabelen niet in de definitieve oplossing worden weergegeven en daarom hanteren we een grote straf in de objectieve functie, die kan worden geschreven als.
Maximaliseren Z = Y, + 2Y 2 + 3Y 3 - Y 4 - MA, - MA 2 - MA 3
Als we nu y 1 Y 2, y 3 en y 4 als niet-basisvariabelen nemen en Y 1 = Y 2 = y 4 = 0 dan krijgen we de initiële oplossing als A 1 = 15, A 2 = 20 & A 3 = 10 en A 1, A 2, A 3 en A 4 zijn basisvariabelen (variabelen in huidige oplossing) om mee te beginnen. De bovenstaande informatie kan in tabel 1 worden gezet.
AS Cj-Ej is positief, de huidige oplossing is niet optimaal en daarom is er een betere oplossing.
Ga op zoek naar een optimale oplossing
Herhalingen uitvoeren om een optimale oplossing te krijgen, zoals weergegeven in de onderstaande tabel
Omdat Cj-Ej nul of negatief is onder alle kolommen, is de optimale basisaanvaardbare oplossing verkregen. Optimale waarden zijn
Y 1 = 5/2, Y 2 = 5/2, Y 3 = 5/2, Y4 = 0
Ook A 1 = A 2 = 0 en Z max = 15 Ans.
