To fase metoder til problemløsning i lineær programmering: første og anden fase

I denne metode løses problemet i to faser som angivet nedenfor.

Første fase:

(a) Alle vilkårene for RHS bør være ikke-negative. Hvis nogle er - så skal de laves + ve som forklaret tidligere.

(b) Ekspresbegrænsninger i standardformular.

d) Formulere en ny objektivfunktion W, som bestod af summen af alle de kunstige variabler

W = A ₁ + A ₂ + ........................ + A _m

Funktion (W) er kendt som infeasibilitetsform.

(e) Funktion W skal minimeres under forbehold af det oprindelige problem, og den optimale grundlæggende mulige løsning opnås.

Nogle af følgende tre tilfælde kan opstå:

(jeg er med. W> 0 og mindst en kunstig variabel vises i kolonne "Grundlæggende variabler" på Positiv niveau. I så fald eksisterer der ingen mulig løsning for den oprindelige LPP, og proceduren er stoppet.

(ii) Min. W = 0 og mindst en kunstig variabel vises i kolonne "Basic Variables" på nulniveau. I et sådant tilfælde kan den optimale, grundlæggende gennemførlige løsning på infeasibilitetsformen muligvis ikke være en grundlæggende mulig løsning til den givne (originale) LPP. For at opnå en grundlæggende gennemførlig løsning fortsætter vi fase I og forsøger at køre alle kunstige variabler ud af grundlaget og derefter gå videre til fase II.

(iii) Min. W = 0 og ingen kunstig variabel vises i kolonnen "Grundlæggende variabler" nuværende løsning ". I så fald er der fundet en grundlæggende gennemførlig løsning til den oprindelige LPP. Fortsæt til fase II.

Anden fase:

Brug han den optimale, grundlæggende gennemførlige løsning af fase I som udgangsopløsning til den oprindelige LPP Brug simplex-metoden til at gøre iterationer til en optimal, grundlæggende gennemførlig løsning, for den opnås.

Det kan bemærkes, at den nye objektivfunktion W altid er af minimeringstype, uanset om den givne (originale) LPP er af maksimering eller minimeringstype. Lad os tage følgende eksempel.

Eksempel 1 (Two-fase simplex Metode):

Brug to-fase simplex Metode til

Minimere Z = -3X-2Y-2Z

Underlagt 5X + 7Y + 4Z <7

-4X + 7Y + 5Z> -2

3X + 4 V - 6Z> 29/7

X, Y, Z> 0

Opløsning:

Første fase

Den består af følgende trin.

(a) I anden begrænsning er RHS -ve, for det er det gjort + ve ved at multiplicere med minustegn på begge sider

4X - 7Y - 5Z <2

(b) Tilføjelse af slakkevariabler i begrænsningerne

5X + 7Y + 4Z + S1 = 7

4X - 7Y - 5Z + S2 = 2

3X + 4Y - 6Z - S ₃ = 29/7

hvor X, Y, Z, S1, S2, S3> 0

(c) Sæt X = Y = Z = 0, vi får S1 = 7, S2 = 2, S3 = -29/7. som indledende opløsning. Men serie S ₃ er -ve, vi vil tilføje kunstig variabel A, dvs.

3X + 4Y-6Z-S3 + A1 = 29/7

(d) Målfunktion, som er minimeringstype, er lavet maksimeringstype dvs.

Maksimere Z = 3X + 2Y + 2Z

(e) Vi introducerer ny objektiv funktion W = A ₁ til den første fase, som skal minimeres.

(f) Ved at erstatte X = Y = Z = S ₃ = 0 i de begrænsninger, vi får S ₁ = 7, S ₂ = 2, / A ₁ = 29/7 som første basale gennemførlige løsning Tabel 1 hvis dannet.

Preformed optimality test

Da Cj-Ej er negativ under samme kolonner (minimeringsproblem), kan den nuværende grundlæggende gennemførlige løsning forbedres.

Iterate mod og optimal løsning:

Udføre iterationer for at få en optimal løsning.

Udskift S ₁ ved X ₂ . dette er vist i nedenstående tabel

I tabel er der slips for nøglerækken X-kolonne er nøglekolonnen og y-kolonnen er den første kolonne af identiteten. Efter metoden til slipsbrud finder vi, at y-søjlen ikke bryder slipset. Den næste kolonne af identiteten, dvs S _2- kolonne giver A ₁ -row som nøglerække. Således (1/7) er nøgleelementet skabt enhed i tabel

Udskift A ₁ med X som vist i nedenstående tabel

Tabel 5 giver optimal opløsning. Også siden minimum W = 0, og der er ingen kunstig variabel i basisvariablerne, dvs. i den nuværende løsning, giver Table5 grundlæggende mulige løsninger til fase-ll

Anden fase:

Den oprindelige objektivfunktion er

Maksimere Z = 3x + 2y + 2Z + OS, + 0S2 + 0S3

Det skal maksimeres ved hjælp af originale begrænsninger. Ved hjælp af opløsning af fase I som udgangsløsning til fase II og udførelse af beregning ved hjælp af simplexalgoritmen, får vi tabel 6