Zobecněná simplexová metoda. Velká encyklopedie ropy a plynu. Příklad řešení přímé a duální úlohy simplexovou metodou

11.4. METODA DUAL SIMPLEX

Z výsledků předchozích odstavců vyplývá, že k získání řešení původní problém můžeme přejít k duálu a pomocí jeho odhadů optimální plán, definovat optimální řešení původní úkol.

Přechod na duální úlohu není nutný, protože pokud vezmeme v úvahu první simplexovou tabulku s jednotkovým dodatečným základem, snadno si všimneme, že původní úloha je zapsána do sloupců a duální do řádků.

Jak se ukázalo, při řešení přímého problému v jakékoli iteraci je rozdíl, tj. velikost -koeficient proměnné, se rovná rozdílu mezi pravou a levou stranou odpovídajícího omezení duální problém. Pokud při řešení přímé úlohy s maximalizovanou účelovou funkcí iterace nevede k optimálnímu řešení, pak alespoň pro jednu proměnnou a pouze při optimu pro všechny rozdíl .

S ohledem na tuto podmínku s přihlédnutím k dualitě můžeme psát

.

Pokud tedy, To . To znamená, že když je řešení přímého problému suboptimální, řešení duálního problému není proveditelné. Na druhé straně v . Z toho vyplývá, že optimálnímu řešení přímé úlohy odpovídá přípustné řešení duální úlohy.

To umožnilo vyvinout novou metodu řešení problémů lineární programování, při použití se nejprve získá nepřijatelné, ale „lepší než optimální“ řešení (při obvyklé simplexové metodě se nejprve zjistí přijatelný, Ale suboptimálnířešení). Nová metoda, volal duální simplexová metoda, zajišťuje splnění podmínek optimálnosti řešení a jeho systematické „přibližování“ regionu přípustná řešení. Když se výsledné řešení ukáže jako proveditelné, iterační proces výpočtů končí, protože i toto řešení je optimální.

Duální simplexová metoda umožňuje řešit problémy lineárního programování, jejichž omezovací systémy s kladným základem obsahují volné členy libovolného znaménka. Tato metoda umožňuje snížit počet transformací systému omezení a také velikost simplexní stůl. Uvažujme na příkladu použití duální simplexové metody.

Příklad. Najděte minimum funkce

pod omezeními

.

Přejděme ke kanonické podobě:

pod omezeními

Počáteční simplexní tabulka má tvar

Základní proměnné	x 1	x 2	x 3	x 4	x 5	Řešení
x 3 x 4 x 5	–3 –4	–1 –3				–3 –6
	–2	–1

Prvotní základní řešeníoptimální, ale nepřijatelné.

Stejně jako obvyklá simplexová metoda je uvažovaná metoda řešení založena na použití podmínek přípustnosti a optimality.

Podmínka přípustnosti. Jako vyloučená proměnná je vybrána největší záporná základní proměnná v absolutní hodnotě (pokud existují alternativy, výběr se provádí libovolně). Pokud jsou všechny základní proměnné nezáporné, proces výpočtu končí, protože výsledné řešení je proveditelné a optimální.

Stav optimalita. Proměnná zahrnutá do základu je vybrána z nebázických proměnných následovně. Vypočítají se poměry koeficientů levé strany-rovnice na odpovídající koeficienty rovnice spojené s vyloučenou proměnnou. Vztahy s pozitivními popř nulová hodnota jmenovatelé se neberou v úvahu. V problému minimalizace musí vstupní proměnná odpovídat nejmenší z specifikované vztahy, a v úloze maximalizace - poměr, který je nejmenší v absolutní hodnotě (pokud existují alternativy, výběr se provádí libovolně). Pokud jsou jmenovatele všech poměrů nulové nebo kladné, problém nemá žádná proveditelná řešení.

Po výběru proměnných, které mají být zahrnuty do základu a vyloučeny k získání další rozhodnutí provádí se obvyklá operace převodu řádků simplexní tabulky.

V tomto příkladu je vyloučená proměnná. Poměry vypočtené pro určení nové základní proměnné jsou uvedeny v následující tabulce:

Proměnné	x 1	x 2	x 3	x 4	x 5
Rovnice x 4 - rovnice	–2 –4	–1 –3
Postoj

Je vybrána zahrnutá proměnná x 2. Výsledkem následné konverze řetězců je nová simplexní tabulka:

Základní proměnné	x 1	x 2	x 3	x 4	x 5	Řešení
x 3 x 2 x 5						–1 –1

Nové řešení také optimální, ale stále nepřijatelné. Jako novou vyloučenou proměnnou zvolíme (libovolně) x 3. Pojďme definovat proměnnou, která má být zahrnuta.

Proměnné	x 1	x 2	x 3	x 4	x 5
Rovnice x 4 - rovnice
postoj

Uvažujme simplexní metoda pro řešení problémů lineárního programování (LP). Je založen na přechodu z jednoho referenčního plánu do druhého, při kterém se zvyšuje hodnota účelové funkce.

Algoritmus simplexové metody je následující:

1. Přeložíme původní problém do kanonický pohled zavedením dalších proměnných. Pro nerovnice tvaru ≤ se uvádějí další proměnné se znaménkem (+), ale pokud jsou ve tvaru ≥, pak se znaménkem (-). Do účelové funkce jsou zavedeny další proměnné s odpovídajícími znaménky s koeficientem rovným 0 , protože cílová funkce by neměla měnit svůj ekonomický význam.
2. Vektory jsou vypsány P i z koeficientů proměnných a sloupce volných členů. Tato akce určuje počet jednotkových vektorů. Platí pravidlo, že jednotkových vektorů by mělo být tolik, kolik je nerovností v systému omezení.
3. Poté jsou zdrojová data vložena do simplexní tabulky. Do základu se zavedou jednotkové vektory a jejich vyloučením ze základu se najde optimální řešení. Koeficienty účelové funkce se zapisují s opačným znaménkem.
4. Znakem optimality pro problém LP je, že řešení je optimální, pokud je v F– v řádku jsou všechny koeficienty kladné. Pravidlo pro vyhledání aktivačního sloupce - prohlíženo F– řetězec a mezi jeho negativními prvky je vybrán ten nejmenší. Vektor P i jeho obsah se stává permisivním. Pravidlo pro výběr rozlišovacího prvku - sestaví se poměry kladných prvků rozlišovacího sloupce k prvkům vektoru P 0 a číslo, které dává nejmenší poměr se stane rozlišovacím prvkem, vůči kterému bude simplexní tabulka přepočítána. Řádek obsahující tento prvek se nazývá povolený řádek. Pokud ve sloupci rozlišení nejsou žádné kladné prvky, problém nemá řešení. Po určení rozlišovacího prvku přistoupí k přepočtu nové simplexní tabulky.
5. Pravidla pro vyplňování nové simplexní tabulky. Jednotka se umístí na místo rozlišovacího prvku a ostatní prvky se považují za stejné 0 . Rozlišovací vektor je přidán k bázi, ze které je vyloučen odpovídající nulový vektor, a zbývající základní vektory jsou zapsány beze změn. Prvky rozlišovací čáry jsou rozděleny prvkem rozlišení a zbývající prvky jsou přepočítány podle pravidla obdélníku.
6. To se provádí do F– všechny prvky řetězce se nestanou pozitivními.

Zvažme řešení problému pomocí výše uvedeného algoritmu.
Vzhledem k tomu:

Převedeme problém do kanonické podoby:

Skládáme vektory:

Vyplňte simplexní tabulku:

:
Pojďme přepočítat první prvek vektoru P 0, pro který uděláme obdélník čísel: a dostaneme: .

Podobné výpočty provedeme pro všechny ostatní prvky simplexní tabulky:

V přijatém plánu F– řádek obsahuje jeden záporný prvek – ​​(-5/3), vektor P 1. Obsahuje ve svém sloupci jediné pozitivní prvek, který bude řešitelským prvkem. Přepočítejme tabulku týkající se tohoto prvku:

Žádné negativní prvky F– řádek znamená nalezený optimální plán:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Lineární programování, M: Nauka, 1998,
• Ventzel E.S. Operační výzkum, M: Sovětský rozhlas, 2001,
• Kuzněcov Yu.N., Kuzubov V.I., Voloshenko A.B. Matematické programování, M: postgraduální škola, 1986

Vlastní řešení lineárního programování

Jakékoliv zadání v této disciplíně si můžete objednat na našem webu. Můžete připojit soubory a určit termíny na

Duální simplexová metoda

Duální simplexová metoda se stejně jako simplexová metoda používá k nalezení řešení úlohy lineárního programování zapsané ve formě hlavní úlohy, pro kterou mezi vektory Pi složenými z koeficientů pro neznámé v soustavě rovnic existuje m singl. Duální simplexovou metodu lze zároveň použít při řešení úlohy lineárního programování, jejíž volné členy soustavy rovnic lze jakákoli čísla(při řešení úlohy simplexovou metodou se předpokládalo, že tato čísla jsou nezáporná). Nyní budeme uvažovat takový problém, když jsme dříve předpokládali, že vektory jsou jednotkové, tj. budeme uvažovat problém spočívající v určení maximální hodnoty funkce.

za podmínek

a mezi čísly jsou i záporná.

V v tomto případě existuje řešení systému lineární rovnice(55). Toto řešení však není plánem úlohy (54) - (56), protože mezi jejími součástmi jsou záporná čísla.

Protože vektory jsou jednotkové vektory, každý z vektorů může být reprezentován jako lineární kombinace těchto vektorů a koeficienty rozkladu vektorů na vektory jsou čísla

Tak lze najít:

Na základě počátečních dat se sestaví simplexní tabulka, ve které jsou některé prvky vektorového sloupce záporná čísla. Pokud taková čísla neexistují, pak se optimální plán úlohy (54) - (56) zapíše do simplexové tabulky, protože podle předpokladu je vše. Proto, abychom určili optimální plán problému, za předpokladu, že existuje, je třeba provést uspořádaný přechod z jedné simplexní tabulky do druhé, dokud nebudou negativní prvky vyloučeny ze sloupce vektoru P0. V tomto případě musí všechny prvky zůstat po celou dobu nezáporné ( T+1) řádek, tzn. pro kohokoli

Po sestavení simplexní tabulky tedy zkontrolují, zda jsou ve sloupci vektoru Po záporná čísla. Pokud žádné neexistují, je nalezen optimální plán pro původní problém. Pokud existují (což předpokládáme), vyberte záporné číslo, které je největší v absolutní hodnotě. V případě, že existuje několik takových čísel, vezměte jedno z nich: nechte toto číslo b l . Volba tohoto čísla určuje vektor vyloučený z báze, tj. v tomto případě je vektor odvozen od báze P l . Abychom určili, který vektor by měl být zadán do základu, najdeme

Nech to být minimální hodnota je přijat v j=r, pak je vektor zaveden do báze R r . Číslo je rozlišovacím prvkem. Přechod na nový simplexní stůl je proveden o normální pravidla simplexní metoda. Iterační proces pokračuje až do sloupce vektoru R 0 již nebudou záporná čísla. V tomto případě je nalezen optimální plán původního problému, a tedy duálního. Pokud se to v nějakém kroku ukáže iřádek simplexní tabulky ve vektorovém sloupci R 0 je záporné číslo b i a mezi zbývajícími prvky této řady nejsou žádné negativní prvky, pak původní problém nemá řešení.

Nalezení řešení problému pomocí metody dual simplex tedy zahrnuje následující kroky:

• 1. Najděte pseudoplán problému.
• 2. Zkontrolujte optimalitu tohoto pseudoplánu. Pokud je pseudoplán optimální, pak bylo nalezeno řešení problému. V opačném případě buď zjistí neřešitelnost problému, nebo přejdou na nový pseudoplán.
• 3. Vyberte čáru rozlišení určením největší v absolutní hodnotě záporné číslo sloupcový vektor R 0 a rozlišovací sloupec nalezením nejmenšího poměru prvků absolutní hodnoty ( m+1)-a čáry k odpovídajícím záporným prvkům čáry rozlišení.
• 4. Najděte nový pseudoplán a opakujte všechny akce počínaje fází 2.

Nalézt maximální hodnota funkcí

za podmínek:

Řešení. Zapišme původní problém lineárního programování ve formě hlavního problému: najděte maximum funkce za podmínek

Vytvořme duální problém pro poslední problém. Jedná se o problém, jehož řešení vyžaduje nalezení minimální hodnoty funkce

Sestavíme simplexní tabulku:

Iterace 0:

Podmínka přípustnosti je splněna, protože všechny hodnoty ve sloupci „Řešení“ jsou kladné, ale podmínka optimality není splněna, protože řádek obsahuje záporný koeficient

Iterace 1:

.
Redukujme systém omezení na systém významových nerovností ≤ vynásobením odpovídajících řádků (-1).
Určeme minimální hodnotu účelové funkce F(X) = x 1 + x 2 za následujících omezujících podmínek.
- 5x 1 - 6x 2 ≤-1
- 15x 1 ≤-1
- 7x 1 - 12x 2 ≤-1
Abychom sestavili první referenční plán, redukujeme systém nerovností na systém rovnic zavedením dalších proměnných ( přechod na kanonickou formu).
V 1. významové nerovnosti (≤) zavedeme základní proměnnou x 3 . Ve 2. významové nerovnosti (≤) zavedeme základní proměnnou x 4 . Ve 3. významové nerovnosti (≤) zavedeme základní proměnnou x 5 .
-5x 1 -6x 2 + 1x 3 + 0x 4 + 0x 5 = -1
-15x 1 + 0x 2 + 0x 3 + 1x 4 + 0x 5 = -1
-7x 1 -12x 2 + 0x 3 + 0x 4 + 1x 5 = -1
Koeficientová matice A = a(ij) této soustavy rovnic má tvar:

A=	-5	-6	1	0	0
	-15	0	0	1	0
	-7	-12	0	0	1

Základní proměnné Jedná se o proměnné, které jsou obsaženy pouze v jedné rovnici systému omezení a navíc s jednotkovým koeficientem.
Pojďme řešit soustavu rovnic pro základní proměnné:
x 3, x 4, x 5,
Věřit tomu volné proměnné jsou rovny 0, dostaneme první referenční plán:
X1 = (0,0,-1,-1,-1)
Základní řešení se nazývá přípustné, pokud není záporné.

	B	x 1	x 2	x 3	x 4	x 5
	-1	-5	-6	1	0	0
	-1	-15	0	0	1	0
	-1	-7	-12	0	0	1
	0	-1	-1	0	0	0

.
Plán 0 v simplexní tabulce je pseudoplán, takže určujeme úvodní řádek a sloupec.
.

Vedoucí řádek bude 1. řádek a proměnná x 3 by měla být odvozena ze základu.
.
Minimální hodnota θ odpovídá 2. sloupci, tzn. do základu je třeba zadat proměnnou x 2.
V průsečíku úvodního řádku a sloupce je rozlišovací prvek (RE) rovný (-6).

	B	x 1	x 2	x 3	x 4	x 5
	-1	-5	-6	1	0	0
	-1	-15	0	0	1	0
	-1	-7	-12	0	0	1
	0	-1	-1	0	0	0
	0	-1: (-5) = 1 / 5	-1: (-6) = 1 / 6	-	-	-

4. Přepočet simplexní tabulky.

	B	x 1	x 2	x 3	x 4	x 5
	1 / 6	5 / 6	1	-1 / 6	0	0
	-1	-15	0	0	1	0
	1	3	0	-2	0	1
	1 / 6	-1 / 6	0	-1 / 6	0	0

	x 1	x 2	x 3	x 4	x 5
	5 / 6: 1	1: 1	-1 / 6: 1	0: 1	0: 1
1-(1 / 6 0):1	-15-(5 / 6 0):1	0-(1 0):1	0-(-1 / 6 0):1	1-(0 0):1	0-(0 0):1
	3-(5 / 6 0):1	0-(1 0):1	-2-(-1 / 6 0):1	0-(0 0):1	1-(0 0):1
1 / 6 -(1 / 6 0):1	-1 / 6 -(5 / 6 0):1	0-(1 0):1	-1 / 6 -(-1 / 6 0):1	0-(0 0):1	0-(0 0):1

1. Kontrola kritéria optimality.
Plán 1 v simplexní tabulce je pseudoplán, takže určujeme úvodní řádek a sloupec.
2. Definice nové volné proměnné.
Mezi záporné hodnoty bázových proměnných volíme největší modulo.
Vedoucí řádek bude 2. řádek a proměnná x 4 by měla být odvozena ze základu.
3. Definice nové základní proměnné.
Minimální hodnota θ odpovídá 1. sloupci, tzn. proměnná x 1 musí být zadána do základu.
V průsečíku úvodního řádku a sloupce je rozlišovací prvek (RE) rovný (-15).

	B	x 1	x 2	x 3	x 4	x 5
	1 / 6	5 / 6	1	-1 / 6	0	0
	-1	-15	0	0	1	0
	1	3	0	-2	0	1
	1 / 6	-1 / 6	0	-1 / 6	0	0
	0	-1 / 6: (-15) = 1 / 90	-	-	-	-

4. Přepočet simplexní tabulky.
Transformace simplexové tabulky provádíme Jordano-Gaussovou metodou.

	B	x 1	x 2	x 3	x 4	x 5
	1 / 9	0	1	-1 / 6	1 / 18	0
	1 / 15	1	0	0	-1 / 15	0
	4 / 5	0	0	-2	1 / 5	1
	8 / 45	0	0	-1 / 6	-1 / 90	0

Ukažme si výpočet každého prvku ve formě tabulky:

	x 1	x 2	x 3	x 4	x 5
1 / 9 -(1 / 15 0):1	0-(1 0):1	1-(0 0):1	-1 / 6 -(0 0):1	1 / 18 -(-1 / 15 0):1	0-(0 0):1
	1: 1	0: 1	0: 1	-1 / 15: 1	0: 1
4 / 5 -(1 / 15 0):1	0-(1 0):1	0-(0 0):1	-2-(0 0):1	1 / 5 -(-1 / 15 0):1	1-(0 0):1
8 / 45 -(1 / 15 0):1	0-(1 0):1	0-(0 0):1	-1 / 6 -(0 0):1	-1 / 90 -(-1 / 15 0):1	0-(0 0):1

Ve sloupci základ jsou všechny prvky kladné.
Přejděme k hlavnímu algoritmu simplexové metody.
1. Kontrola kritéria optimality.
Mezi hodnotami indexového řetězce nejsou žádné kladné hodnoty. Proto tato tabulka určuje optimální plán řešení problému.
Finální verze simplexní tabulky:

	B	x 1	x 2	x 3	x 4	x 5
	1 / 9	0	1	-1 / 6	1 / 18	0
	1 / 15	1	0	0	-1 / 15	0
	4 / 5	0	0	-2	1 / 5	1
	8 / 45	0	0	-1 / 6	-1 / 90	0

Optimální plán lze napsat takto:
x 1 = 1/15
x 2 = 1/9
F(X) = 1 1/9 + 1 1/15 = 8/45

Protože existují tři jednotkové vektory, pak
referenční plán si můžete rovnou zapsat
X=(0,0,0,360,192,180).
Vytvořme nulovou simplexní tabulku

Výsledný referenční plán kontrolujeme
pro optimalitu.
Vypočteme hodnotu účelové funkce a
simplexní rozdíly.
F0 c P0 0 360 0 192 0 180 0,
1 z1 c1 c P1 c1 9,
2 z2 c2 cP2 c2 10,...

Jak je vidět z 0. tabulky, nenulové
jsou proměnné x4 , x5 , x6 a x , x , x
1
2
3
se rovnají nule, protože Nejsou základní, ale zdarma.
Další proměnné x4 , x5 , x6
brát jejich hodnoty podle toho
omezení.
Tyto hodnoty proměnných tomu odpovídají
„plán“, podle kterého se nic nevyrábí, suroviny
se nepoužívá a hodnota účelové funkce je
nulové, tedy náklady na vyrobené produkty
nepřítomný.
Tento plán samozřejmě není optimální.
To je vidět i ze 4. řádku tabulky, ve kterém
jsou tři negativní skóre -9, -16 a -10.

10.

Záporná čísla nejsou jen
naznačují možnost zvýšení
celkové náklady na vyrobené produkty (v
sloupce nad negativním hodnocením
jsou kladná čísla), ale také
ukázat, o kolik se tato částka zvýší
při zavádění jednotky toho či onoho do plánu
druh produktu.
Takže číslo -9 znamená, že když je zapnuto
výrobní plán pro jeden výrobek A
poskytuje zvýšení nákladů
produkty pro 9 jednotek

11.

Pokud zahrnete do plánu výroby pro
jeden produkt B a C, pak celkové náklady
vyrobených produktů bude přibývat
respektive o 10 a 16 jednotek. Proto s
ekonomický bod zobrazit vhodné
je zařazení produktů C do plánu.
Od tohoto bodu je třeba udělat totéž
že -16 je nejmenší
negativní hodnocení. Takže k základu
uveďme vektor P3.

12.

Najdeme číslo Q.
360 192 180
Q min
;
;
min 30; 24;60
3
12 8
Zadáme jej do posledního sloupce tabulky.
Číslo 24 odpovídá vektoru P5.
192/8=24 z ekonomického hlediska
znamená, kolik produktů C
podnik může vyrábět s přihlédnutím
míry spotřeby a dostupné objemy surovin
každý typ.

13.

Protože jsou k dispozici suroviny každého druhu
respektive 360, 192 a 180 kg a pro jednoho
produkt C vyžaduje vynaložení surovin na každý
typy 12, 8 a 3 kg, pak maximální počet
produkty C, které lze vyrobit
podnik rovná se
min(360/12,192/8,180/3)=192/8=24, tzn.
limitujícím faktorem pro výrobu
produkty C je dostupný objem surovin
2. typ. S přihlédnutím k jeho podniku může
vyrobit 24 výrobků C. V tomto případě budou zcela využity suroviny 2. druhu a
to znamená, že vektor podléhá vyloučení z
P5
základ.

14.

Vytvořme si následující tabulku. V něm
druhý řádek je povolený,
a rozlišovací sloupec je třetí. Na
jejich průsečík obsahuje prvek 8.
Vydělte druhý řádek 8 a pak
nula pomocí Jordan-Gaussovy metody
nebo podle vzorců trojúhelníku třetí
sloupec.

15.

16.

Spočítejme simplexní rozdíly a vyplňte 4. řádek tabulky.
S tímto výrobním plánem
Vyrobí se a zůstane 24 položek C
nespotřebovaných 72 kg surovin 1. a 108 kg
suroviny 3. druhu. 2. druh použité suroviny
plně. Cena všech produktů v
v tomto ohledu je 384 CU. Upřesněno
čísla jsou zapsána ve sloupci Plán. Je to znovu
parametry úkolu, ale prošly
změny. Změnila se i data ostatních
sloupců. Jejich ekonomický obsah
se stala ještě složitější.

17.

Je zde jedno negativní hodnocení -2.
Plán lze vylepšit. Pojďme se uvést do základu
vektor P2. Pojďme počítat
72 24 108
Q min;
;
min 8; 48;728.
9 1/ 2 3 / 2
.
Vycházíme ze základu P4.

18.

Permisivní linie budou 1. a 2. linie
sloupec. Permisivní prvek 9.
Vydělte 1. řádek 9, vyplňte
1. řádek nový stůl, pak
Obnovíme 2. sloupec. Za tohle
vynásobte 1. řádek (-1/2) a
přičti k 2. a pak vynásob 1
řádek po (-3/2) a přidejte ke 3. řádku.
Vyplníme tabulku 2.

19.

20.

Jsme o tom přesvědčeni
výpočet simplexních rozdílů
1 cP1 c1 10 1 16 0,25 9 5,
2 cP2 c2 10 1 16 0 10 0,
3 cP3 c3 10 0 16 1 0 0 16 0,
4 cP4 c4 10 1/ 9 16 1/ 8 0 (1/ 6) 2/9,
5 cP5-c5=10 (-1/6)+16 5/24+0(-1/2)=5/3,
6 0.

21.

Optimální plán výroby není
předpokládá se výroba výrobků A Úvod do
výrobní plán pro výrobky typu A by vedl k
snížení uvedených celkových nákladů.
To je vidět ze 4. řádku sloupce, kde je číslo 5
ukazuje, že s tímto plánem inkluze
vede k němu výstup jednotky produktu A
pouze ke snížení celkové hodnoty
hodnotu o 5 jednotek
Plán tedy počítá s vydáním 8 produktů
B a 20 výrobků C. Suroviny typu 1 a 2
je zcela použit a typ 3 ponechává 96 kg nevyužitých.

22. PROBLÉMY DUÁLNÍHO LINEÁRNÍHO PROGRAMOVÁNÍ

Každý ZLP lze spárovat
problém nazvaný duální k původnímu
úkol.
Zvažte problém používání
zdroje. Předpokládejme, že podnik A
vyrábí n druhů výrobků, hodnota
jehož uvolňování je určeno proměnnými
x1, x2, ..., xn
.
Ve výrobě m různé
druhy zdrojů, jejichž objem je omezený
hodnoty b1, b2, ..., mld.

23.

Nákladové sazby každého zdroje na jednotku jsou známé
každý typ produktu tvoří matrici,
a11
a21
A
...
am1
a12
a22
...
jsem 2
...a1n
... a2 n
... ...
...amn
stejně jako náklady na jednotku výroby každého typu
c1, c2, ..., cn
Je potřeba organizovat výrobu tak, že
podniku A bylo poskytnuto max
zisk.

24.

Úkolem je najít
nezáporné proměnné
x1, x2, ..., xn,
ve kterých není spotřeba zdrojů
překročí jejich stanovený počet a
náklady na všechny produkty dosáhnou
maximum.

25.

V matematické podobě problém
se píše v následujícím tvaru:
F c1 x1 c2 x2 ... c j x j ... cn xn max
za podmínek
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a21 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
.
...............................................................,
a x a x ... a x ... a x b
mj j
mn
m
m1 1 m 2 2
x j 0, j 1, n.

26.

Na základě stejných počátečních údajů může být
byl formulován další úkol.
Předpokládejme, že se podnik B rozhodne koupit
všechny zdroje dostupné podniku A. B
V tomto případě musí podnik B založit
optimální ceny za tyto zdroje na základě
následující podmínky:
celkové náklady na zdroje pro podnik B
měla by být minimální;
pro každý typ zdroje podnik A potřebuje
zaplatit alespoň částku, kterou zaplatí
podnik může přijímat během zpracování
tohoto typu zdroje do hotových výrobků.

27.

Je-li označeno y1 , y2 , ..., yn
ceny, za které podnik B
nakupuje zdroje od podniku A
úkol se scvrkává na následující: najít
takové hodnoty proměnných y1, y2, ..., yn,
při které jsou náklady na zdroje,
vynaložené na jednotku jakéhokoli typu
produkty nejsou nižší než zisk (ceny)
pro tuto jednotku produkce a celkem
náklady na zdroje dosahují
minimální,

28.

tj. jaké by mělo být hodnocení jednotky
každý ze zdrojů y1, y2, ..., yn,
takže pro dané objemy
dostupné zdroje bi , dané
náklady c j (j 1, n) jednotek
produkty a nákladové standardy aij
minimalizovat celkové hodnocení náklady
pro všechny produkty.

29. Mat. model se dvěma problémy

V matematické podobě problém
se píše jako:
*
F b1 y1 b2 y2 ... bm ym min
pod omezeními
a11 y1 a21 y2 ... am1 ym c1 ,
a y a y ... a y c ,
m2 m
2
12 1 22 2
..................................................
a y a y ... a y c ,
mn m
n
1n 1 2 n 2
yi 0, i 1, 2,..., m.

30. Ekonomický význam proměnných duálního problému

Proměnné yi duálního problému v literatuře
může mít různé názvy: účetní, implicitní,
stínová, objektivně stanovená hodnocení,
duální hodnocení nebo „ceny“ zdrojů.
Tyto dva problémy tvoří vzájemně pár
duální problémy, z nichž každý může
považovat za originální. Řešení na jedničku
úkoly dává optimální plán výroby
produktů, a řešení je jiné – optimální
systém hodnocení surovin používaných pro
výroby těchto produktů.

31.

Duální úlohy lineární
se nazývá programování
symetrické, pokud vyhovují
následující vlastnosti:
počet proměnných v duálním problému
se rovná počtu omezení původního problému a
počet omezení duálního problému
rovno číslu rovnému počtu proměnných v
originál;
v jednom problému se hledá maximum cíle
funkce, ve druhém – minimum;
koeficienty pro proměnné v cíli
funkce jednoho úkolu jsou zdarma
členy omezovacího systému jiného úkolu;

32.

v každém problému je specifikován systém omezení
ve formě nerovností a v problému hledání
maximum, všechny nerovnosti tvaru „≤“ a v úloze dál
nalezení minima, všech nerovností tvaru „≥“;
matice koeficientů omezovacího systému
jeden se získá z druhého transpozicí;
každé omezení jednoho problému odpovídá
proměnná jiné úlohy, proměnná číslo
odpovídá číslu omezení;
podmínky pro nezápornost proměnných
jsou uloženy v obou úlohách;

33. Řešení symetrických duálních úloh

První věta o dualitě.
Pokud jeden z duálních problémů
má tedy optimální řešení
jiný má optimální řešení
úkol, zatímco cílové hodnoty
funkce úkolů jsou si navzájem rovnocenné.
Pokud je cílová funkce jednou z
úkoly nejsou omezeny, pak další úkol
nemá vůbec řešení

34. Ekonomický obsah první věty o dualitě

Pokud problém se stanovením optimálního plánu,
o maximalizaci výstupu je tedy rozhodnout
Problém stanovení odhadů zdrojů je také řešitelný.
Navíc cena produktu získaného jako výsledek
realizace optimálního plánu se shoduje s
celkové hodnocení zdrojů.
Hodnota se shoduje cílové funkce Pro
odpovídající řešení dvojice duálních problémů
stačí k tomu, aby tato rozhodnutí byla
optimální.
Rozhodování ZLP simplexovou metodou, jsme zároveň
Řešíme původní i duální problémy.

35. Metoda pro současné řešení dvojice duálních úloh

Původní problém: Duální problém:
F c1x1 c2 x2 ... c j x j ... F * b1 y1 b2 y2 ...
cn xn max
a11 x1 a12 x2 ... a1n xn xn 1 b1 ,
a21 x1 a22 x2 ... a2 n xn xn 2 b2 ,
..........................................................
a x a x ... a x x b,
mn
n m
m
m1 1 m 2 2
x j 0, j 1, 2,..., n m.
bm ym min,
a11 y1 a21 y2 ... am1 ym ym 1 c1 ,
a y a y ... a y y c ,
m2 m
m 2
2
12 1 22 2
.............................................................
a y a y ... a y y c ,
mn m
m n
n
1n 1 2 n 2
yi 0, i 1, 2,..., m n.

36.

Počet proměnných v problémech je stejný
a rovná se m + n. V původním problému
základní proměnné jsou

proměnné xn 1 , xn 2 , ..., xn m
,
a v duálním problému –
pomocné nezáporné
proměnné yn 1, yn 2, ..., yn m.
Základní proměnné jednoho problému
volné proměnné odpovídají
jiný úkol a naopak.

37.

38.

Na rozhodnutí PPP pomocí tabulkové simplexové metody k řešení duálního problému
obsažené v posledním řádku tabulky.
Toto je j.
Navíc hlavní proměnné duálu

odpovídající dodatečné
proměnné původního problému a
další proměnné duálu
úkoly jsou obsaženy ve sloupcích,
odpovídající hlavnímu
(původní) počáteční proměnné
úkoly.

39. Příklad.

Zformulujme model duálu problému
k problému z příkladu 2 (začátek přednášky):
Najděte maximum funkce

40.

41.

Proměnné původního problému x1, x2, x3 jsou množství výrobky A, B a C. Dovolte nám představit
duální problémové proměnné y1, y2, y3
Najděte minimum funkce
F * 360 y1 192 y2 180 y3 min
pod omezeními
18 y1 6 y2 5 y3 9,
15 y1 4 y2 3 y3 10,
12 r 8 r 3 r 16,
2
3
1
y1, y2, y3 0.

42. Zvažte poslední tabulku původního problému

43.

Hodnota y1 v posledním řádku sloupce P4,
těch. y12;
9 let 5
hodnota 2 3 v posledním řádku sloupce P5,
hodnotu y3 0 v posledním řádku sloupce P6.
Zbývající hodnoty jsou uvedeny ve sloupcích 1,2,3.
2 5
Y (; ;0;5;0;0)
9 3
Ve stejnou dobu
2
5
F 360 192 180 0 0 5 0 0 0 0 400
9
3
*
-Tento minimální náklady pro všechny produkty.
2/9 a 5/3 jsou stínové ceny surovin 1. a 2
druhy resp.