Príklad riešenia úlohy metódou lp simplex. Príklad riešenia priamych a duálnych úloh simplexovou metódou

Ak problém obsahuje obmedzenia so znamienkom ≥, potom ich možno zredukovať na tvar ∑a ji b j vynásobením oboch strán nerovnosti -1. Zavedieme m prídavných premenných x n + j ≥0 (j = 1, m) a transformujeme obmedzenia do tvaru rovnosti

(2)

Predpokladajme, že všetky počiatočné premenné úlohy x 1, x 2, ..., x n sú nebázické. Potom budú dodatočné premenné základné a konkrétne riešenie systému obmedzení bude mať formu

x 1 = x 2 = ... = x n = 0, x n + j = b j, j = 1, m. (3)

Keďže v tomto prípade je hodnota cieľovej funkcie F 0 = 0, môžeme F (x) znázorniť takto:

F (x) = ∑c i x i + F 0 = 0 (4)

Počiatočná simplexná tabuľka (simplexná tabuľka 1) je zostavená na základe rovníc (2) a (4). Ak pred dodatočnými premennými x n + j je znamienko "+", ako v (2), potom sa všetky koeficienty pred premennými x i a voľným členom b j zapíšu do simplexnej tabuľky nezmenené. Keď je cieľová funkcia maximalizovaná, koeficienty cieľovej funkcie sa zadávajú do spodného riadku simplexnej tabuľky s opačnými znamienkami. Voľné výrazy v simplexnej tabuľke určujú riešenie problému.

Algoritmus na vyriešenie problému je nasledujúci:

1. krok. Prvky stĺpca voľného člena sa posúvajú. Ak sú všetky kladné, potom sa našlo uskutočniteľné základné riešenie a treba prejsť na krok 5 algoritmu, ktorý zodpovedá nájdeniu optimálneho riešenia. Ak má počiatočná simplexová tabuľka záporné voľné podmienky, riešenie nie je platné a mali by ste prejsť na krok 2.

2. krok. Na nájdenie realizovateľného riešenia sa vykonáva, pričom je potrebné rozhodnúť, ktorú z nezákladných premenných zaradiť do základu a ktorú premennú zo základu odvodiť.

Stôl 1.

x n

základné premenné	Voľní členovia v obmedzeniach	Nezákladné premenné
		x 1	x 2	...	x l	...
x n + 1	b 1	11	12	...	a 1l	...	a 1n
x n + 2	b 2	21	22	...	a 2l	...	a 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + r	b2	a r1	a r2	...	a rl	...	a rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + m	b m	m1	m2	...	ml	...	a mn
F (x) max	F 0	-c 1	-c 2	...	-c 1	...	-c n

Ak to chcete urobiť, vyberte ľubovoľný zo záporných prvkov stĺpca voľného člena (nech je b 2 vedúci alebo rozlišovací. Ak v rade so záporným voľným členom nie sú žiadne záporné prvky, potom je systém obmedzení nekompatibilný a problém nemá riešenie.

Zároveň sa z BP vylúči premenná, ktorá ako prvá zmení znamienko so zvýšením zvoleného NP x l. Bude to x n + r, ktorého index r je určený z podmienky

tie. premenná zodpovedajúca najmenšiemu pomeru voľného člena k členovi zvoleného otočného stĺpca. Tento vzťah sa nazýva simplexný vzťah. Mali by sa brať do úvahy iba pozitívne simplexné vzťahy.

Zavolá sa reťazec zodpovedajúci premennej x n + r vedúci, alebo povoľujúci. Prvok simplexnej tabuľky a rl, ktorý stojí na priesečníku vodiaceho riadku a vodiaceho stĺpca, sa nazýva vodiaci alebo rozlišovací prvok. Nájdenie prvku pivot končí prácou s každou následnou simplexnou tabuľkou.

3. krok. Vypočíta sa nová simplexová tabuľka, ktorej prvky sa prepočítajú z prvkov simplexovej tabuľky predchádzajúceho kroku a označia sa prvočíslom, t.j. b "j, a" ji, c "i, F" 0. Prvky sa prepočítavajú podľa nasledujúcich vzorcov:

Najprv nová simplexná tabuľka vyplní riadok a stĺpec, ktoré viedli v predchádzajúcej simplexnej tabuľke. Výraz (5) znamená, že prvok a "rl na mieste vedúceho prvku sa rovná recipročnej hodnote prvku predchádzajúcej simplexovej tabuľky. Prvky riadku a ri sú delené vodiacim prvkom a prvky stĺpec a jl je tiež delený vodiacim prvkom, ale s opačným znamienkom Prvky b "r a c" l sa vypočítajú rovnakým spôsobom.

Ostatné vzorce sa dajú ľahko napísať.

Obdĺžnik je zostrojený podľa starej simplexovej tabuľky tak, že jednu z jeho uhlopriečok tvoria prepočítaný (a ji) a vodiaci (a rl) prvok (obr. 1). Druhá uhlopriečka je jednoznačne určená. Ak chcete nájsť nový prvok a "ji, súčin prvkov opačnej uhlopriečky delený vodiacim prvkom sa odpočíta od prvku a ji (ako je označené znamienkom" - "v blízkosti bunky). Prvky b" j, (j ≠ r) a c"i, (i ≠ l).

4. krok. Analýza novej simplexovej tabuľky začína 1. krokom algoritmu. Akcia pokračuje dovtedy, kým sa nenájde uskutočniteľné základné riešenie, t.j. všetci členovia stĺpca voľných členov musia byť kladní.

5. krok. Veríme, že sa našlo uskutočniteľné základné riešenie. Pozeráme sa na koeficienty priamky cieľovej funkcie F (x). Kritériom optimálnosti simplexnej tabuľky je nezápornosť koeficientov pre nebázické premenné v F-riadku.

Ryža. 1. Pravidlo obdĺžnika

Ak sú medzi koeficientmi radu F záporné (s výnimkou priesečníka), musíte prejsť na iné základné riešenie. Pri maximalizácii cieľovej funkcie sa do základu započítavajú aj nebázické premenné (napríklad x l), ktorých stĺpec zodpovedá maximálnej absolútnej hodnote záporného koeficientu cl v spodnom riadku simplexnej tabuľky. To vám umožní vybrať premennú, ktorej zvýšenie vedie k zlepšeniu cieľovej funkcie. Stĺpec zodpovedajúci premennej x l sa nazýva vedúci stĺpec. Zároveň je zo základu vylúčená premenná x n + r, ktorej index r je určený minimálnym simplexným vzťahom:

Riadok zodpovedajúci x n + r sa nazýva vodiaci prvok a prvok simplexnej tabuľky a rl, ktorý stojí na priesečníku vodiaceho riadku a vodiaceho stĺpca, sa nazýva vedúci prvok.

6. krok. podľa pravidiel uvedených v kroku 3. Postup pokračuje, kým sa nenájde optimálne riešenie alebo sa nedospeje k záveru, že neexistuje.

Ak sú počas optimalizácie riešenia vo vodiacom stĺpci všetky prvky nekladné, potom nie je možné vybrať vodiaci riadok. V tomto prípade funkcia v obore realizovateľných riešení úlohy nie je ohraničená vyššie a F max -> & ∞.

Ak sa v ďalšom kroku pri hľadaní extrému jedna zo základných premenných rovná nule, potom sa zodpovedajúce základné riešenie nazýva degenerované. V tomto prípade dochádza k tzv. loopingu, ktorý sa vyznačuje tým, že s určitou frekvenciou sa začne opakovať rovnaká kombinácia BP (hodnota funkcie F je zachovaná) a nie je možné prejsť na nové prípustné základné riešenie. Looping je jednou z hlavných nevýhod simplexovej metódy, ale je pomerne zriedkavý. V praxi v takýchto prípadoch väčšinou odmietajú zadať do základu premennú, ktorej stĺpec zodpovedá maximálnej absolútnej hodnote záporného koeficientu v cieľovej funkcii a náhodne vyberú nové základné riešenie.

Príklad 1. Vyriešte úlohu

max (F (x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Simplexová metóda a poskytnúť geometrickú interpretáciu procesu riešenia.

Grafická interpretácia riešenia úlohy je na obr. 2. Maximálna hodnota cieľovej funkcie sa dosiahne v hornej časti ODZP so súradnicami. Vyriešme problém pomocou simplexných tabuliek. Druhé obmedzenie vynásobíme (-1) a zavedieme ďalšie premenné, aby sa nerovnosti dostali do formy rovnosti, potom

Počiatočné premenné x 1 a x 2 sú brané ako nezákladné a dodatočné x 3, x 4 a x 5 sú považované za základné a zostavujeme simplexnú tabuľku (simplexnú tabuľku 2). Riešenie zodpovedajúce simplexnej tabuľke. 2 neplatí; otočný prvok je načrtnutý a vybraný podľa kroku 2 predchádzajúceho algoritmu. Ďalšia simplexná tabuľka. 3 určuje prípustné základné riešenie, ktoré zodpovedá vrcholu ODZP na obr. 2 Prvok pivot je načrtnutý a vybraný v súlade s 5. krokom algoritmu na riešenie problému. Tab. 4 zodpovedá optimálnemu riešeniu úlohy, preto: x 1 = x 5 = 0; x2 = 4; x 3 = 3; x4 = 8; Fmax = 20.

Ryža. 2. Grafické riešenie úlohy

Problémy lineárneho programovania. Je v sekvenčnej štruktúre, ktorá charakterizuje posudzovaný proces. Riešenie je rozdelené do troch hlavných etáp: výber premenných, konštrukcia systému obmedzení a hľadanie cieľovej funkcie.

Na základe tohto delenia je možné problémovú podmienku preformulovať takto: extrém účelovej funkcie Z (X) = f (x1, x2, ..., xn) → max (min) a príslušné premenné, ak je známe, že spĺňajú systém obmedzení: Φ_i ( x1, x2,…, xn) = 0 pre i = 1, 2,…, k; Φ_i (x1, x2,…, xn)) 0 pre i = k + 1 , k + 2,…, m.

Systém obmedzení treba doviesť do kánonickej podoby, t.j. na sústavu lineárnych rovníc, kde počet premenných je väčší ako počet rovníc (m> k). V tomto systéme určite budú existovať premenné, ktoré sa dajú vyjadriť inými premennými, a ak to tak nie je, potom ich možno zaviesť umelo. V tomto prípade sa prvé nazývajú základ alebo umelý základ a druhé sa nazývajú voľné.

Je vhodnejšie zvážiť simplexnú metódu pomocou konkrétneho príkladu. Nech je daná lineárna funkcia f (x) = 6x1 + 5x2 + 9x3 a systém obmedzení: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 4x1 + 3x3 ≤ 18. Je potrebné nájsť maximálna hodnota funkcie f (x).

Riešenie V prvej fáze špecifikujte počiatočné (podporné) riešenie sústavy rovníc absolútne ľubovoľným spôsobom, ktoré musí spĺňať daný systém obmedzení. V tomto prípade je potrebné zavedenie umelého, t.j. základné premenné x4, x5 a x6 takto: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.

Ako môžete vidieť, nerovnosti boli prevedené na rovnosti vďaka pridaným premenným x4, x5, x6, čo sú nezáporné hodnoty. Takto ste systém priviedli do kanonickej podoby. Premenná x4 sa objavuje v prvej rovnici s koeficientom 1 a v dvoch - s koeficientom 0, to isté platí pre premenné x5, x6 a zodpovedajúce rovnice, čo zodpovedá definícii základu.

Pripravili ste systém a našli počiatočné riešenie podpory - X0 = (0, 0, 0, 25, 20, 18). Teraz prezentujte koeficienty premenných a voľné členy rovníc (čísla napravo od znamienka "=") vo forme tabuľky na optimalizáciu ďalších výpočtov (pozri obr.).

Podstatou simplexovej metódy je uviesť túto tabuľku do takej podoby, v ktorej všetky číslice v riadku L budú nezáporné hodnoty. Ak sa ukáže, že to nie je možné, tak systém vôbec nemá optimálne riešenie. Najprv vyberte najmenší prvok tohto riadku, je to -9. Číslo je v treťom stĺpci. Preveďte príslušnú premennú x3 na základnú. Ak to chcete urobiť, vydeľte riadok 3, aby ste dostali 1 v bunke.

Teraz je potrebné, aby sa bunky zmenili na 0. Ak to chcete urobiť, odpočítajte od zodpovedajúcich číslic tretieho riadku 3. Od prvkov druhého riadku - prvky tretieho, vynásobte 2. A nakoniec od prvky línie L - vynásobené (-9). Získali ste druhé referenčné riešenie: f (x) = L = 54 pri x1 = (0, 0, 6, 7, 8, 0).

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Varovanie

Vymazať všetky bunky?

Zavrieť Vymazať

Pokyny na zadávanie údajov.Čísla sa zadávajú ako celé čísla (príklady: 487, 5, -7623 atď.), desatinné čísla (napr. 67., 102,54 atď.) alebo zlomky. Zlomok musí byť zadaný v tvare a / b, kde a a b (b> 0) sú celé čísla alebo desatinné čísla. Príklady 45/5, 6,6 / 76,4, -7 / 6,7 atď.

Simplexná metóda

Príklady riešenia simplexnej metódy LPP

Príklad 1. Vyriešte nasledujúci problém lineárneho programovania:

Pravá strana obmedzení sústavy rovníc je nasledovná:

Zapíšme si aktuálny základný plán:

Tento základný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v absolútnej hodnote (-3), preto základ zahŕňa vektor X pri . min(40: 6, 28: 2) = 20/3 zodpovedá riadku 1. Vektor vychádza zo základu X 3. Urobme pre stĺpec Gaussovu elimináciu X 2, berúc do úvahy, že pivot zodpovedá riadku 1. Vynulujme všetky prvky tohto stĺpca okrem pivota. Ak to chcete urobiť, pridajte riadky 2, 3, 4 s riadkom 1 vynásobeným -1/3, 1/6, 1/2. Ďalej čiaru s pivotom rozdelíme pivotom.

Tento základný plán nie je optimálny, pretože posledný riadok obsahuje záporný prvok (-3), preto základ zahŕňa vektor X 1. Určte, ktorý vektor opúšťa základ. Aby sme to dosiahli, vypočítame pri ... min (44/3: 11/3, 62/3: 5/3) = 4 zodpovedá riadku 2. Zo zákl. X 4. Urobme pre stĺpec Gaussovu elimináciu X 1, za predpokladu, že pivot zodpovedá riadku 2. Vynulujte všetky prvky v tomto stĺpci, okrem pivota. Za týmto účelom pridajte riadky 1, 3, 4 s riadkom 2 vynásobeným 1/11, -5/11, 9/11. Ďalej čiaru s pivotom rozdelíme pivotom.

Simplexná tabuľka bude vyzerať takto:

Aktuálny základný plán je optimálny ako v riadkoch 4 pod premennými žiadne negatívne prvky.

Riešenie možno napísať takto: .

Hodnota účelovej funkcie v danom bode: F(X)=.

Príklad 2. Nájdite maximum funkcie

Riešenie.

Základné vektory X 4 , X 3, teda všetky položky v stĺpcoch X 4 , X 3, pod vodorovnou čiarou by mala byť nula.

Nastavte všetky prvky stĺpca na nulu X 4, s výnimkou otočného prvku. Ak to chcete urobiť, pridajte riadok 3 s riadkom 1 vynásobeným 4. Vynulujte všetky prvky stĺpca X 3, s výnimkou otočného prvku. Za týmto účelom pridajte riadok 3 k riadku 2 krát 1.

Simplexná tabuľka bude mať tvar:

Tento základný plán nie je optimálny, pretože posledný riadok obsahuje záporný prvok (-11), preto základ zahŕňa vektor X 2. Určte, ktorý vektor opúšťa základ. Aby sme to dosiahli, vypočítame pri ... Preto je účelová funkcia zhora neobmedzená. Tie. problém lineárneho programovania je neriešiteľný.

Príklady riešenia LPP metódou umelej bázy

Príklad 1. Nájdite maximum funkcie

Riešenie. Keďže počet bázových vektorov by mal byť 3, pridáme umelú premennú a túto premennú pripočítame vynásobenú −M k účelovej funkcii, kde M je veľmi veľké číslo:

Matica koeficientov sústavy rovníc má tvar:

Bázové vektory, preto všetky prvky v stĺpcoch pod vodorovnou čiarou musia byť nulové.

Vynulujte všetky prvky v stĺpci okrem pivota. Ak to chcete urobiť, pridajte riadok 5 s riadkom 3 vynásobeným -1.

Simplexná tabuľka bude mať tvar:

Tento základný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v absolútnej hodnote (-5), preto vektor vstupuje do bázy. Určte, ktorý vektor opúšťa bázu. Aby sme to dosiahli, vypočítame pri zodpovedá riadku 3. Vektor opúšťa základ Urobme pre stĺpec Gaussovu elimináciu, berúc do úvahy, že prvok pivot zodpovedá riadku 3. Vynulujte všetky prvky tohto stĺpca okrem pivotu. Ak to chcete urobiť, pridajte riadky riadok 5 s riadkom 3 vynásobeným 1. Ďalej rozdeľte riadok s pivotom pivotom.

Simplexná tabuľka bude vyzerať takto:

Tento základný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v absolútnej hodnote (-3), preto vektor vstupuje do základu. Určte, ktorý vektor opúšťa základ. Aby sme to dosiahli, vypočítame pri zodpovedá riadku 1. Vektor vychádza zo základu X 2. Urobme pre stĺpec Gaussovu elimináciu X 1, za predpokladu, že pivot zodpovedá riadku 1. Vynulujte všetky prvky v tomto stĺpci okrem pivota. Za týmto účelom pridajte riadky 2, 3, 4 s riadkom 1 vynásobeným 3/2, -1/10, 3/2. Ďalej čiaru s pivotom rozdelíme pivotom.

Simplexná tabuľka bude vyzerať takto:

Tento základný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v absolútnej hodnote (-13/2), preto základ zahŕňa vektor X 3. Určte, ktorý vektor opúšťa základ. Aby sme to dosiahli, vypočítame pri zodpovedá riadku 3. Vektor vychádza zo základu X 5. Urobme pre stĺpec Gaussovu elimináciu X 3, berúc do úvahy, že pivot zodpovedá riadku 3. Vynulujme všetky prvky tohto stĺpca okrem pivota. Ak to chcete urobiť, pridajte riadky 1, 2, 4 s riadkom 3 vynásobeným 5/3, 25/9, 65/9. Ďalej čiaru s pivotom rozdelíme pivotom.

Simplexná tabuľka bude vyzerať takto:

Aktuálny východiskový plán je optimálny, pretože pod premennými v riadkoch 4-5 nie sú žiadne záporné položky.

Riešenie pôvodného problému možno napísať takto:

Príklad 2. Nájdite optimálny plán pre problém lineárneho programovania:

Matica koeficientov sústavy rovníc má tvar:

Základné vektory X 4 , X 5 , X 6, teda všetky položky v stĺpcoch X 4 , X 5 , X 6, pod vodorovnou čiarou by mala byť nula.

Nastavte všetky prvky stĺpca na nulu X 4, s výnimkou otočného prvku. Ak to chcete urobiť, pridajte riadok 4 k riadku 1 vynásobenému -1. Nastavte všetky prvky stĺpca na nulu X 5, s výnimkou otočného prvku. Ak to chcete urobiť, pridajte riadok 5 k riadku 2 vynásobenému -1. Nastavte všetky prvky stĺpca na nulu X 6, s výnimkou otočného prvku. Ak to chcete urobiť, pridajte riadok 5 s riadkom 3 vynásobeným -1.

Simplexná tabuľka bude mať tvar:

Na riadku 5 prvky zodpovedajúce premenným X 1 , X 2 , X 3 , X 4 , X 5 , X 6 sú nezáporné a číslo na priesečníku daného riadka a stĺpca X 0 je záporné. Potom pôvodný problém nemá základnú líniu. Preto je nerozpustný.

Stručná teória

Na riešenie problémov lineárneho programovania bolo navrhnutých mnoho rôznych metód. Simplexová metóda sa však medzi nimi ukázala ako najefektívnejšia a najuniverzálnejšia. Treba poznamenať, že pri riešení niektorých problémov môžu byť efektívnejšie iné metódy. Napríklad v prípade LPP s dvoma premennými je optimálna metóda a v prípade riešenia metóda potenciálov. Simplexová metóda je základná a použiteľná pre každý ZPL v jeho kanonickej forme.

V súvislosti s hlavnou teorémou lineárneho programovania sa prirodzene vynára myšlienka nasledujúceho spôsobu riešenia LPP s ľubovoľným počtom premenných. Nájdite nejakým spôsobom všetky extrémne body konštrukčného mnohostenu (nie je viac ako) a porovnajte v nich hodnoty cieľovej funkcie. Tento spôsob riešenia aj pri relatívne malom počte premenných a obmedzení je prakticky nerealizovateľný, keďže proces hľadania krajných bodov je náročnosťou porovnateľný s riešením pôvodnej úlohy, navyše počet krajných bodov pôdorysného mnohostenu môže ukáže byť veľmi veľký. V súvislosti s týmito ťažkosťami vyvstal problém racionálneho vymenovania krajných bodov.

Podstata simplexovej metódy je nasledovná. Ak je známy nejaký extrémny bod a hodnota účelovej funkcie v ňom, potom sú všetky extrémne body, v ktorých má účelová funkcia najhoršiu hodnotu, zjavne zbytočné. Preto je prirodzené snažiť sa nájsť spôsob, ako prejsť z daného krajného bodu do lepšieho bodu susediaceho pozdĺž okraja, z neho do ešte lepšieho (nie horšieho) bodu atď. Aby ste to dosiahli, musíte mať znamenie, že neexistujú lepšie extrémne body ako tento extrémny bod. Toto je všeobecná myšlienka v súčasnosti najpoužívanejšej simplexnej metódy (metóda postupného zlepšovania plánu) na riešenie LPP. Z algebraického hľadiska teda simplexná metóda predpokladá:

1. schopnosť nájsť počiatočný referenčný plán;
2. prítomnosť znaku optimálnosti referenčného plánu;
3. schopnosť prejsť na základný plán, ktorý nie je zlý.

Príklad riešenia problému

Úloha

Na predaj troch skupín tovarov má obchodný podnik tri druhy obmedzených vecných a peňažných prostriedkov vo výške,,, jednotiek. Zároveň na predaj 1 skupiny tovaru za 1 000 rubľov. obrat sa vynakladá na zdroj prvého typu v počte jednotiek, zdroj druhého typu v počte jednotiek, zdroj tretieho typu v počte jednotiek. Na predaj 2 a 3 skupín tovaru za 1 000 rubľov. obrat sa vynakladá na zdroj prvého typu v množstve, jednotky, zdroje druhého typu v množstve, jednotky, zdroje tretieho typu v množstve, jednotky. Zisk z predaja troch skupín tovaru za 1 000 rubľov. obrat je tisíc rubľov.

• Stanovte plánovaný objem a štruktúru obratu tak, aby zisk obchodného podniku bol maximálny.
• K priamemu problému plánovania obratu, riešeného simplexovou metódou, tvorí duálny problém lineárneho programovania.
• Vytvorte konjugované páry premenných priamych a duálnych problémov.
• Podľa konjugovaných párov premenných získajte z riešenia priameho problému riešenie duálneho problému, v ktorom sa odhadujú zdroje vynaložené na predaj tovaru.

Ak váš vstup na reláciu závisí od vyriešenia bloku problémov a nemáte čas ani chuť sadnúť si k výpočtom, využite možnosti stránky. Objednávanie úloh je otázkou niekoľkých minút. Viac podrobností (ako zanechať požiadavku, ceny, podmienky, spôsoby platby) si môžete prečítať na stránke riešenia problémov s lineárnym programovaním ...

Riešenie problému

Stavba modelu

Prostredníctvom označujú obrat 1., 2. a tretieho druhu tovaru, resp.

Potom je účelová funkcia vyjadrujúca zisk:

Obmedzenia materiálnych a peňažných prostriedkov:

Navyše v zmysle problému

Dostaneme nasledujúci problém lineárneho programovania:

Uvedenie do kanonickej podoby ZLP

Prenesme problém do kanonickej podoby. Na transformáciu nerovností na rovnosti zavádzame ďalšie premenné. Premenné sú zahrnuté do obmedzení s koeficientom 1. Do účelovej funkcie zavedieme všetky dodatočné premenné s koeficientom rovným nule.

Obmedzenie má výhodnejšiu formu, ak je pravá strana nezáporná, ľavá strana má premennú vstupujúcu s koeficientom rovným jednej a zostávajúce obmedzenia rovnosti s koeficientom rovným nule. V našom prípade má 1., 2., 3. obmedzenie preferovanú formu so zodpovedajúcimi základnými premennými.

Simplexné riešenie

Vyplníme simplexnú tabuľku 0. iterácie.

BP

Simplexné vzťah

8

6

4

0

0

0

0

520

16

18

9

1

0

0

65/2

0

140

7

7

2

0

1

0

20

0

810

9

2

1

0

0

1

90

0

-8

-6

-4

0

0

0

Keďže riešime maximálny problém, prítomnosť záporných čísel v riadku indexu pri riešení maximálneho problému naznačuje, že sme nezískali optimálne riešenie a že je potrebné prejsť z tabuľky 0. iterácie na ďalšiu.

Prechod na ďalšiu iteráciu sa vykonáva takto:

Vedúci stĺpec sa zhoduje.

Kľúčový riadok je určený minimálnym pomerom voľných členov a členov vedúceho stĺpca (jednoduché vzťahy):

Na priesečníku kľúčového stĺpca a kľúčového radu nájdeme rozlišovací prvok, teda 7.

Teraz začneme zostavovať 1. iteráciu. Namiesto jednotkového vektora zavedieme vektor.

V novej tabuľke na miesto rozlišovacieho prvku napíšeme 1, všetky ostatné prvky kľúčového stĺpca sa vynulujú. Kľúčové prvky línie sú rozdelené na povoľujúce prvky. Všetky ostatné prvky tabuľky sa vypočítajú podľa pravidla obdĺžnika.

Dostaneme tabuľku 1. iterácie:

BP

Simplexné vzťah

8

6

4

0

0

0

0

200

0

2

31/7

1

-16/7

0

1400/31

8

20

1

1

2/7

0

1/7

0

70

0

630

0

-7

-11/7

0

-9/7

1

-

160

0

2

-12/7

0

8/7

0

Kľúčový stĺpec pre zhody 1. iterácie.

Nájdeme reťazec kľúčov, na tento účel definujeme:

Na priesečníku kľúčového stĺpca a kľúčového radu nájdeme rozlišovací prvok, t.j. 31/7.

Vektor sa odvodí zo základu a vektor sa zavedie.

Dostaneme tabuľku 2. iterácie:

BP

Simplexné vzťah

8

6

4

0

0

0

4

1400/31

0

14/31

1

7/31

-16/31

0

8

220/31

1

27/31

0

-2/31

9/31

0

0

21730/31

0

-195/31

0

11/31

-65/31

1

7360/31

0

86/31

0

12/31

8/31

0

Všetky výrazy v riadku indexu sú nezáporné, takže sa získa nasledovné riešenie problému lineárneho programovania (vypíšeme ho zo stĺpca voľných výrazov):

Preto je potrebné predať 7,1 tisíc rubľov. tovar 1. druhu a 45,2 tisíc rubľov. tovar 3. druhu. Predávať tovar 2. druhu je nerentabilné. V tomto prípade bude zisk maximálny a bude 237,4 tisíc rubľov. Pri implementácii optimálneho plánu bude zvyšok zdroja 3. typu 701 jednotiek.

Problém s dvojitým LP

Zapíšme si model duálneho problému.

Ak chcete vytvoriť dvojitý problém, musíte použiť nasledujúce pravidlá:

1) ak je priamy problém vyriešený na maximum, potom je vyriešený duálny problém na minimum a naopak;

2) v maximálnom probléme majú obmedzenia nerovnosti význam ≤ a v probléme minimalizácie význam ≥;

3) každé obmedzenie priameho problému zodpovedá premennej duálneho problému a naopak, každé obmedzenie duálneho problému zodpovedá premennej priameho problému;

4) maticu systému obmedzení duálneho problému získame z matice systému obmedzení pôvodného problému transpozíciou;

5) voľné členy systému obmedzení priameho problému sú koeficienty pre zodpovedajúce premenné objektívnej funkcie duálneho problému a naopak;

6) ak je podmienka nezápornosti uložená na premennú priameho problému, potom sa zodpovedajúce obmedzenie duálneho problému zapíše ako obmedzenie nerovnosti, ak nie, potom ako obmedzenie rovnosti;

7) ak je akékoľvek obmedzenie priameho problému napísané ako rovnosť, potom podmienka nezápornosti nie je uložená na zodpovedajúcu premennú duálneho problému.

Transponujeme maticu pôvodného problému:

Prenesme problém do kanonickej podoby. Predstavme si ďalšie premenné. Všetky dodatočné premenné zavedieme do účelovej funkcie s koeficientom rovným nule. Na ľavú stranu obmedzení pridáme ďalšie premenné, ktoré nemajú preferovaný tvar, a získame rovnosti.

Riešenie problému duálneho LP

Korešpondencia medzi premennými pôvodného a duálneho problému:

Na základe simplexnej tabuľky sme získali nasledujúce riešenie problému duálneho lineárneho programovania (vypisujeme ho od spodného riadku):

Najvzácnejším zdrojom je teda prvý typ. Jeho odhad je maximálny a rovnaký. Zdroj tretieho typu je nadmerný - jeho duálny odhad je nulový. Každá dodatočne predaná jednotka tovaru 2. skupiny zníži optimálny zisk o
Uvažuje sa o grafickej metóde riešenia úlohy lineárneho programovania (LPP) s dvoma premennými. Na príklade úlohy je uvedený podrobný popis konštrukcie výkresu a nájdenia riešenia.

Riešenie dopravných problémov
Podrobne sa zvažuje dopravný problém, jeho matematický model a metódy riešenia - nájdenie referenčného plánu metódou minimálneho prvku a nájdenie optimálneho riešenia metódou potenciálu.

Rozhodovanie v neistote
Uvažuje sa o riešení štatistickej maticovej hry v podmienkach neurčitosti pomocou kritérií Wald, Savage, Hurwitz, Laplace, Bayes. Na príklade úlohy je podrobne znázornená konštrukcia platobnej matice a matice rizík.

Jedna z metód riešenia optimalizačných problémov ( zvyčajne spojené s hľadaním minima alebo maxima) sa nazýva lineárne programovanie. Simplexná metóda zahŕňa celú skupinu algoritmov a metód na riešenie problémov lineárneho programovania. Jedna z takýchto metód, zahŕňajúca zaznamenávanie počiatočných údajov a ich prepočítanie do špeciálnej tabuľky, sa nazýva tabuľková simplexová metóda.

Zvážte algoritmus tabuľkovej simplexovej metódy na príklade riešenia výrobná úloha, ktorá sa scvrkáva na nájdenie výrobného plánu, ktorý poskytuje maximálny zisk.

Počiatočné údaje problému pre simplexnú metódu

Podnik vyrába 4 druhy výrobkov, spracováva ich na 3 strojoch.

Časové sadzby (min./kus.) Pre spracovanie produktov na strojoch, nastavené maticou A:

Časový fond chodu stroja (min.) je špecifikovaný v matici B:

Zisk z predaja každej jednotky produktu (rubľov / kus) je daný maticou C:

Účel výrobnej úlohy

Vypracujte plán výroby, v ktorom bude zisk podniku maximálny.

Riešenie úlohy tabuľkovou simplexovou metódou

(1) Označme X1, X2, X3, X4 plánované množstvo produktov každého typu. Potom požadovaný plán: ( X1, X2, X3, X4)

(2) Zapíšme si obmedzenia plánu vo forme sústavy rovníc:

(3) Potom cieľový zisk:

To znamená, že zisk z plnenia plánu výroby by mal byť maximalizovaný.

(4) Na vyriešenie výsledného problému pre podmienený extrém nahradíme systém nerovníc systémom lineárnych rovníc tak, že do neho vložíme ďalšie nezáporné premenné ( X5, X6, X7).

(5) Zoberme si nasledovné základný plán:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Zadáme údaje do simplexný stôl:

V poslednom riadku zadáme koeficienty účelovej funkcie a jej samotnú hodnotu s opačným znamienkom;

(7) Vyberáme v poslednom riadku najväčší (modulo) záporné číslo.

Poďme počítať b = N / Selected_Column_Elements

Medzi vypočítanými hodnotami b vyberte najmenej.

Priesečník vybraného stĺpca a riadku nám poskytne povoľujúci prvok. Základ zmeníme na premennú zodpovedajúcu rozlišovaciemu prvku ( X5 až X1).

• Samotným rozlišovacím prvkom sa stáva 1.
• Pre prvky rozlišovacej čiary - a ij (*) = a ij / RE ( to znamená, že každý prvok sa vydelí hodnotou rozlišovacieho prvku a získame nové údaje).
• Pre permisívne stĺpcové prvky sa jednoducho vynulujú.
• Ostatné prvky tabuľky sa prepočítajú podľa pravidla obdĺžnika.

a ij (*) = a ij - (A * B / RE)

Ako vidíte, berieme aktuálnu bunku na prepočet a bunku s prvkom rozlíšenia. Tvoria protiľahlé rohy obdĺžnika. Ďalej vynásobíme hodnoty z buniek ostatných 2 rohov tohto obdĺžnika. Táto práca ( A * B) sa delí rozlišovacím prvkom ( RE). A odpočítajte od aktuálne prepočítanej bunky ( a ij) čo sa stalo. Získame novú hodnotu - a ij (*).

(9) Znova skontrolujte posledný riadok ( c) zapnuté prítomnosť záporných čísel... Ak tam nie sú, našiel sa optimálny plán, pokračujeme do poslednej fázy riešenia problému. Ak existuje, plán ešte nie je optimálny a simplexnú tabuľku je potrebné znova prepočítať.

Keďže v poslednom riadku máme opäť záporné čísla, spustíme novú iteráciu výpočtov.

(10) Keďže v poslednom riadku nie sú žiadne negatívne prvky, znamená to, že sme našli optimálny plán výroby! Totiž: vyrobíme tie produkty, ktoré sa presunuli do stĺpca Základ - X1 a X2. Poznáme zisk z produkcie každej jednotky produkcie ( matica C). Zostáva vynásobiť zistené objemy výroby výrobkov 1 a 2 so ziskom o 1 kus, dostaneme konečný ( maximálne! ) zisk pre daný plán výroby.

ODPOVEĎ:

X1 = 32 ks, X2 = 20 ks, X3 = 0 ks, X4 = 0 ks.

P = 48 * 32 + 33 * 20 = 2 196 rubľov.

Galyautdinov R.R.

© Kopírovanie materiálu je povolené len vtedy, ak existuje priamy hypertextový odkaz na