Simplex Metode for Lineær Programmering

Simplex Metode for Lineær Programmering!

Ethvert lineært programmeringsproblem, der involverer to variabler, kan let løses ved hjælp af grafisk metode, da det er lettere at håndtere todimensionelle grafer. Alle mulige løsninger i grafisk metode ligger inden for det mulige område på grafen, og vi plejede at teste hjørnepunkterne i det mulige område for den optimale løsning, dvs. et af hjørnepunkterne i det anvendelige område var den optimale løsning. Vi plejede at teste alle hjørnepunkterne ved at sætte disse værdier i objektiv funktion.

Men hvis antallet af variabler stiger fra to, bliver det meget svært at løse problemet ved at tegne sin graf, da problemet bliver for komplekst. Simplex metode blev udviklet af GB Dantzig, en amerikansk matematiker.

Denne metode er matematisk behandling af den grafiske metode. Her testes også forskellige hjørnepunkter i det gennemførlige område for optimitet. Men det er ikke muligt at teste alle hjørnepunkterne, da antallet af hjørnepunkter øger manifolds, idet antallet af ligninger og variabler øges. Maksimalt antal af disse punkter, der skal testes, kan være

m + nm = m + 1! / m! n!

hvor m er antal og n er antal variabler.

I simplex-metoden er antallet af hjørnepunkter, der skal testes, reduceret betydeligt ved at bruge en meget effektiv algoritme, som fører os til det optimale løsningshørpunkt i kun få iterationer. Lad os tage et eksempel og gå trin for trin.

Målfunktionen er at maksimere Z = 12x ₁ + 15x ₂ + 14x ₃

Under forbehold af betingelser

Trin 1:

(a) Højre side af alle begrænsningerne skal være enten nul eller + ve. Hvis de er - da skal de laves + ve ved at gange begge sider ved (-1) og tegn på ulighed vil blive vendt om. I dette eksempel er RHS allerede + ve eller nul.

(b) Alle ulighederne omdannes til ligeværdier ved at tilføje eller subtrahere slap eller overskudsvariabler. Disse slap eller overskudsvariabler indføres, fordi det er lettere at behandle ligevægt end uligheder i matematisk behandling.

Hvis begrænsning er ≤ type, tilføjes slapvariablerne, hvis begrænsning er ≥ type, og overskudsvariabler trækkes fra. Her slack variabler s, s ₂ og s ₃ er tilføjet i tre i lige muligheder (i), (ii) og (iii), vi får.

Og objektiv funktion bliver

Maksimere Z = 12x ₁ + 15x ₂ + 14x ₃ + os ₁ + os ₂ + os ₃

Trin 2:

Find den grundlæggende grundlæggende mulige løsning:

Vi starter med en gennemførlig løsning og derefter bevæger os mod optimal løsning i næste iterationer. Den første mulige løsning vælges fortrinsvis til at være oprindelsen, dvs. hvor de regulære variabler, f.eks. I dette tilfælde x _v x ₂, x ₃ antager nulværdier. dvs. x ₁ x ₂, x ₃ = 0

og vi får s ₁ = 0, s ₂ = 0 og s ₃ = 100 fra uligheder (i), (ii) og (iii)

Grundvariabler er de variabler, der for tiden findes i løsningen, f.eks. S _v S ₂ og S ₃ er de grundlæggende variabler i den oprindelige løsning.

Ikke-basale variabler er variablerne, der er lig med nul og ikke er i den nuværende løsning, f.eks. X ₁ og x ₂ og x ₃ er de ikke-basale variabler i den oprindelige løsning.

Ovenstående oplysninger kan udtrykkes i tabel 1

I tabellen repræsenterer første række koefficienter af objektiv funktion, anden række repræsenterer forskellige variabler (første regelmæssige variabler og derefter slap / overskudsvariabler). Tredje fjerde og femte række repræsenterer variable af variable i alle begrænsninger.

Første kolonne repræsenterer koefficienter af basisvariabler (nuværende løsningsvariabler) i objektiv (e _i ) anden kolonne repræsenterer basisvariabler (nuværende løsning variabler) og sidste kolonne repræsenterer, højre side af begrænsningerne i standardform. Dvs. efter overbelastning af alle uligheder i ligeværdier, i en hvilken som helst tabel, er aktuelle værdier af de nuværende løsningsvariabler (basisvariabler) givet af RHS

I tabel 1 er den nuværende løsning:

S1 = 0, S2 = 0, S3 = 100

Selvfølgelig vil de ikke-basale variabler X _v X ₂ og X ₃ også være nul

Degeneracy, når en grundlæggende variabel antager nulværdier, siges den nuværende løsning som degenereret som i det nuværende problem S1 = 0 og S2 = 0 kan problemet løses yderligere ved at erstatte S1 = t og S2 = t hvor t er meget lille + ve nummer.

Trin 3:

Optimaltest.

Optimaltest kan udføres for at finde ud af om den aktuelle løsning er optimal eller ej. For denne første skriv sidste række i form af (E _j ) hvor

Ej = Σ _ei. En _ij.

Hvor en _ij repræsenterer koefficienter i kropsidentitetsmatrixen for ith række & jth kolonne, dvs. repræsenterer første kolonne i tabellen. I den sidste række skriver du værdien af (Cj - Ej) hvor c _; repræsenterer værdierne for første række og E _j repræsenterer værdierne for sidste række. (Cj - Ej) repræsenterer fordelen ved at bringe en ikke-grundlæggende variabel til den nuværende løsning, dvs. ved at gøre den grundlæggende.

I tabel 2 er værdierne for Cj-Ej 12, 15 og 14 for Xv X2 og X3. Hvis nogen af værdierne for Cj - Ej er + ve betyder det, at de fleste positive værdier repræsenterer variablen, der bringes i den aktuelle løsning, ville øge objektivfunktionen i maksimal omfang. I nærværende tilfælde er X ₂ den potentielle variabel at komme ind i opløsningen til næste iteration. Hvis alle værdierne i (Cj - Ej) rækken er negative, betyder det, at optimal løsning er nået.

Trin 4:

Iterat mod Optimal løsning:

Maksimum værdien af Cj - Ej giver Key coloumn som markeret i tabellen

Derfor er X ₂ indtastningsvariabelen, dvs. det bliver grundlæggende og vil komme ind i løsningen. Ud af den eksisterende ikke-grundlæggende variabel, og man skal gå ud og blive ikke-grundlæggende. For at finde ud af hvilken variabel der skal uddrives, opdeler jeg koefficienterne i RHS kolonne med de tilsvarende koefficienter i nøglesøjlen for at få Ratio Column. Se nu efter den mindst positive værdi i forholdskolonnen, og det ville give nøgleordet. I nuværende problem har vi tre værdier, dvs. t, μ og 100 og ud af disse er t den mindste + ve. Derfor er række, der svarer til t i Ratio-kolonnen, nøgleordet. Og S., ville være den forlader variabel. Element ved skæringspunktet mellem nøgle række og nøgle kolonne er nøgleelementet.

Nu skal alle elementerne i nøglekolonnen undtagen nøgleelementet laves nul, og nøgleelementet skal laves enhed. Dette gøres ved hjælp af rækkeoperationer som færdig er matricerne. Her er nøgleelementet allerede enhed, og andet element i nøgle kolonne bliver nul ved at tilføje -1 gange første række i sin tredje række og få næste tabel.

Derfor bliver anden mulige løsning

X1 = 0, X2 = t og X3 = 0 der ved z = 15t

I ny tabel s er ₁ erstattet af X ₂ i de grundlæggende variabler, og tilsvarende er ei kolonne også blevet ændret.

Trin 5:

Når vi ser på Cj -Ej værdier i tabel 3, finder vi, at x ₁ har de fleste + ve-værdier på 27, hvilket indikerer at løsningen kan forbedres yderligere ved at bringe x ₁ ind i løsningen, dvs. ved at gøre den grundlæggende. Derfor er x ₁ kolonne nøglesøjle, finder også nøgle række som forklaret tidligere og udfyld tabel 5.

Nøgleelementet i Tabel 5 kommer ud til at være 2, og det er skabt enhed, og alle andre elementer i nøglekolonnen bliver nul ved hjælp af rækkeoperationer og endelig får vi tabel 6. Første nøgleelement er skabt enhed ved at dividere den pågældende række ved 2. Derefter ved at tilføje passende multipler af den pågældende række i en anden række, får vi tabel 6.

Det fremgår af tabel 6, at løsningen stadig ikke er optimal, da Cj-Ej stadig er + ve-værdier er 1/2 dette giver er nøgle kolonne og tilsvarende nøgle række er fundet, nøgleelementet er lavet som angivet i tabel 7

Nu ved hjælp af passende rækkeoperationer gør vi andre elementer i nøgle kolonne er nul som vist i tabel 8.

Det kan ses, at da alle værdier i Cj-Ej-rækken er enten -ve eller nul, er den optimale løsning blevet nået.

Endelig løsning er x ₁ = 40 tons

x ₂ = 40 tons

x ₃ = 20 tons

da t er meget lille, er det forsømt.

Eksempel 1:

Løs følgende problem ved simplex-metoden

Maksimere Z = 5x ₁ + 4x ₂

Underlagt 6x ₁ + 4x ₂ ≤ 24

x ₁ + 2x ₂ ≤ 6

-x ₁ + x ₂ ≤ 1

x ₂ ≤ 2

og x ₁ x ₂ ≥0

Opløsning:

Tilføj slackvariabler S ₁, S ₂, S ₃, S ₄ i de fire begrænsninger for at fjerne uligheder.

Vi får 6x ₁ + 4x ₂ + s ₁ = 24

x ₁ + 2x ₂ + s ₂ = 6

-x ₁ + x ₂ + s ₃ = 1

x ₂ + s ₄ = 2

Underlagt x ₁, x ₂, s ₁, s ₂, s ₃ og s ₄ > 0

Målfunktionen bliver

Maksimere Z = 5x ₁ + 4x ₂ 0s ₁ + 0s ₂ + 0s ₃ + 0s ₄

Tabel 1, der dannes, er angivet nedenfor. Det kan ses, at X ₁ er indtastningsvariablen, og S, er forladervariablen. Nøgleelement i tabel 1 er lavet enhed, og alt andet element i den kolonne er lavet nul.

Det kan fremgå af tabel 2, at X ₂ er indtastningsvariablen, og S ₂ er den forløbende variabel.

Det fremgår af tabel 5, at alle værdierne for Cj-Ej-rækken er enten -ve eller nul. Derfor er optimal opløsning opnået.

Løsningen er x ₁ = 3, x ₂ = 3/2

Z _max = 5x ₃ + 4x = 3/2

= 15 + 6 = 21 Ans.

Big M-Method

Lad os tage følgende problem for at illustrere Big M-Method.

Minimer Z = 2y ₁ + 3y ₂

underlagt begrænsninger y ₁ + y ₂ ≥ 5

y ₁ + 2y ₂ ≥ 6

y ₁, y ₂ ≥ 0

Konvertering til standardformular:

Maksimere Z = -2y ₁ - 3y ₂ + Os, + 0s ₂

dvs. Minimeringsproblemet konverteres til maksimeringsproblem ved at multiplicere RHS med objektiv funktion med -1.

Begrænsninger y ₁ + y ₂ - s ₁ = 6 ... (i)

y, + y ₂ - s ₂ = 6 ... (ii)

y ₁ y ₂, s ₁ s ₂ ≥ 0

Her overskudsvariabler s1, s2 og subtraheres fra begrænsningerne (i) og (ii).

Nu y ₁, y ₂ kan tages som ikke-basiske variabler og sætte lig med nul for at få s _v s ₂ som grundlæggende variabler hvor s ₁ = -5, s ₂ = -6.

Dette er umulig løsning som overskudsvariabler s ₁ og s ₂ har få -ve værdier. For at overvinde dette problem tilføjer vi kunstige variabler A ₁ og A ₂ i eqn. (i) og (ii) henholdsvis at få

y ₁ + y ₂ -s ₁ + A ₁ = 5 ... (iii)

y ₁ + 2y ₂ - s ₂ + A ₂ = 6 ... (iv)

Hvor y ₁ y ₂, s ₁, s ₂, A ₁, A ₂ ≥ 0

og objektiv funktion bliver

Maksimere Z ¹ = -2y ₁ - 3y ₂ + 0s ₁ + 0s ₂ - MA ₁ - MA ₂

Det kan bemærkes, at vi med bevidst har anvendt meget store straffe på kunstige variabler i objektivfunktionen i form af -MA1 og MA2, hvor M er et meget stort + ve-nummer. Formålet med det er, at de kunstige variabler oprindeligt forekommer i den basale basale løsning.

Fordi kunstige variabler formindsker objektivfunktionen i høj grad, er der sanktioner, simplex algoritmen driver de kunstige variabler ud af løsningen i de indledende iterationer, og derfor er de kunstige variabler, som vi introducerede for at løse problemet yderligere, ikke vist i den endelige opløsning. Kunstige variabler er kun en beregningsenhed. De holder start-ligningerne i balance og giver et matematisk trick for at få en startløsning.

Indledende tabel bliver

Da Cj-Ej er + ve under nogle kolonner, er opløsningen givet ved tabel 1 ikke optimal. Det kan ses, at ud af -2 + 2M og -3 + 3M, -3 + 3M er mest + ve, da M er et meget stort + ve-nummer. Nøgleelementet findes som vist i tabel 1, og det er lavet enhed, og alle andre elementer i denne kolonne laves nul. Vi får tabel 2.

Fra tabel 2 kan det ses, at den optimale løsning stadig ikke nås, og at der findes en bedre løsning. Y ₁ er den indkommende variabel, og A ₁ er den udgående variabel. Vi får tabel 3.

Det fremgår af tabel 3, at den optimale løsning har nået og løsningen er

Y1 = 4, Y2 = 1

Mindste værdi af Z = 2x ₄ + 3x ₁ = 11 enheder Ans.

Ubundet løsning:

Et lineært programmeringsproblem siges at have ubundet løsning, når vi i forholdskolonnen får alle indtastninger enten -ve eller nul, og der er ingen + ve-indtastning. Dette indikerer, at værdien af indkommende variabel valgt fra nøglekolonnen kan være så stor som vi kan lide uden at krænke den mulige tilstand, og problemet siges at have ubundet løsning.

Uendelig Antal Løsninger:

Et lineært programmeringsproblem siges at have et uendeligt antal løsninger, hvis vi under enhver iteration, i Cj-Ej-rækken, har alle værdierne nul eller -ve. Det viser, at optimal værdi er nået. Men da en af de regelmæssige variabler har nulværdi i Cj-Ej række, kan det konkluderes, at der findes en alternativ optimal løsning.

Eksempel på denne type bord er angivet nedenfor.

Det kan ses, at den optimale løsning er nået, da alle værdier i Cj-Ej-rækken er nul eller -ve. Men X ₁ er ikke-grundlæggende variabel, og den har nulværdi i Cj-Ej-rækken, det indikerer at X kan bringes i løsning, men det vil ikke øge værdien af objektiv funktion og alternativ optimale eksisterer.

Case of No. Mulig løsning:

I nogle LPP'er kan det ses, at når man løser problemet med kunstige variabler, viser Cj-Ej række at optimal løsning er nået, mens vi stadig har kunstig variabel i den nuværende løsning med en vis + vp-værdi. I sådanne situationer kan det konkluderes, at problemet overhovedet ikke har nogen mulig løsning.

Eksempel 2:

Opløsning:

For at løse problemet skal kunstige variabler tilføjes i LHS for at få den første grundlæggende mulige løsning. Lad os introducere kunstige variabler A _1, A ₂, A ₃, ovenstående begrænsninger kan skrives som.

Nu, hvis disse kunstige variabler fremkommer i den endelige løsning ved at have nogle + ve-værdier, bliver ligestillingen af ligningen enten (i), (ii) eller (iii) forstyrret. Derfor vil vi have, at kunstige variabler ikke skal vises i den endelige løsning, og derfor anvender vi stor straf i objektivfunktionen, som kan skrives som.

Maksimere Z = Y, + 2Y ₂ + 3Y ₃ - Y ₄ - MA, - MA ₂ - MA ₃

Nu, hvis vi tager y ₁ Y ₂, y ₃ og y ₄ som ikke-basale variabler og sætter Y ₁ = Y ₂ = y ₄ = 0 får vi den første løsning som A ₁ = 15, A ₂ = 20 & A ₃ = 10 og A _1, A ₂, A ₃ og A ₄ er basisvariabler (variabler i nuværende løsning) til at begynde med. Ovennævnte oplysninger kan anføres i tabel 1.