přednášky

c Txs * (( j - cj
Test optima má 3 funkce:
v každém interakčním kroku analyzuje zda nalezené řešení ji již optimální, či nikoliv (zda budeme ve výpočtu pokračovat, či zde o finální stav)
určuje nově zařzené proměnné, proměnné, které vstoupí v příštím kroku do báze
př.: Z2 – C2 – jednotná změna účelové funkce v souvislosti se vstupem proměnné do báze (stanovení změny)
naplnění těchto funkcí:
otázka: jsme v optimu?
Musím rozlišit:
maximalizační úloha – pokud v indexu, klíči, kritériu, kompračním řešení je alespoň 1 záporná hodnota (úloha dosud není v optimu), lze nalézt lepší s vyšší hodnotou účelové funkce (-(Zj-cj))
minimalizační úloha – existuje alespoň 1 Zj kladné a ( než 0, potom lze hodnotu účelové funkce snížit ( řešení není dosud optimální)
!! u nebazických proměnných se může stát, že Zj-cj=0, potom vzniká tzv. alternativní optimální řešení – řešení, které má jinou strukturu proměnných, ale má stejnou hodnotu účelové funkce
kterou proměnnou zařadíme do báze?
Max (-(Zj-cj)) – vyberu největší proměn. v absolutní hodnotě
(Z= -Xj (Zj-cj) – říká nám, jaká účelová funkce je násobkem rozsahu nově zařazené proměnné a její sazby (hodnoty) Zj-cj – používá se u maximalizace
Zmax k+1 = Zk – xj (Zj – cj)
1. interační krok
hodnota účelové fce v příštím kroku
hodnota účelové fce předchozího kroku
rozhodli jsme, že proměnná vstoupí do nové bazé( test optima nám určuje nově zařazenou proměnnou, my však musíme nějakou proměn. z báze odstranit
(test přípustnosti (kmin:
má také 3 funkce:
v algoritmu zajišťuje, aby nově nalezeně řešení zůstalo primárně přípustné (tzn., aby platina podm. Nezápornosti pro všechny proměnné (x (0
určuje nově vyřazenou proměnnou
(kmin = (i / (ik pro všechna (ik ( 0př.: (b : 10 = 10 ,… =9, …=18, …=30
x1 1x2 x3 x4
(kmin – proměnná toho ř. půjde z báze a jednička se přesune místo x1
2 stejné hodnoty – záleží zda budou mít stejnou sazbu
- dojde ke stejné transformaci matice
určuje max možný interval zařazení nové promsěnné do báze : 0 ( x1 ( H
v každém iteračním kroku dochází k vyřazení některé původní proměnné a zařazení nové proměnné do báze, tento cyklus se opakuje dokud nám krit. řádek signalizuje, že ještě lze zlepšit hodnotu účelové funkce
po konečném počtu kroků dostáváme konečné řešení, pokud úloha ovšem řešení má
zacyklování121…vyřazení
2…zařazení
Tento krok nastane, jestliže matice A není regulární, některé řady představují lin. kombinaci ostatních řad.
degenerace úlohy = degenerace řešení
takové řešení, jestliže v bázi je zařazena 1 nebo více proměn. a nulovou hodnotou (proměn. v řešení je, ale její rozsah je 0)
problém degenerace i v dalších úlohách
v praxi testujeme jednotlivé vrcholi polyedru
simplex – testovaní vrcholů konvexní polyedrické množiny
dulální úloha - je ze struktury podm. úlohy původní
- dualita = specifická vlastnost ekonomicko-mat. modelů
1. úloha
1. kvadrant (podm. nezápornosti), 3 fce, které nám vymezují prostor,
hledám Zmax ( Cjxj za podmínky, že A(x ( (b a platí podm prim. přípust. (x ( 0
x2
(
X1
úloha je maximální, podm. kapacitního typu (omezení ze zhora)
matice A typu(m,n( , úlohu řeším ve Vm
schéma řešení úlohy: (R
max
máme omezené zdroje a hledáme takový výrobní program, abychom max. zisk
2. úloha
množin možných řešení je otevřená ( nevyčerpatelné zdroje
hledám takové řešení, kde fce nabývá minimálního nevyužití zdrojů
soustava podmínek je požadavková – pro jednotlivé faktory nám zobrazují spodní hranice požadavků

(
x
(
Ymin
Návod: otoč všechno co lze otočit, mat A je maticí transponovanou
schéma řešení úlohy: (R
(x ( (m) y (n)
požadavková podm.
max min
vektor cen převedeme jako vekt. omezení
(z původního omez jsou sazby procesů)
zrušení prim. proměn. ( místo nich vyrobíme duální proměn. y, která se vztahuje k původní omez. zdrojům
UFmin = (yT(b - skalární součin duál. proměn. y a (b, za podm AT( (c (vekt cen), (y je libovolný
vztahy: jedná se o simetrie duality
duální proměn. mohou být libovolné a mohou nabývat i záporných hodnot
mat. úlohy je transponovanou z původního tvaru A(m,n( na A(n,m(
zmizel vektor původních proměnných
objevuje se vektor duálních proměnných
vektor původních sazeb se mění na vektor omezení
účelová fce je v duální úloze minimalizační
použití duality:
k formálním důkazům – z teoretického hlediska
ke konstrukci DSA (duálně simplexový algoritmus)
spouštěn automaticky programem pokud se při výpočtu objeví prim. nepřípustné řešení
určí vylučovanou proměnou, a pak nově zařazenou proměn a provee transfomaci
kroky se opakují tak dlouho, pokud trvá nepřípustné řešení
jakmile se odstraní záporné hodnoty u proměnných (je nastolena přim. příp. úlohy) nastupuje opět prim. simpl. algoritmus
simplexový algoritmus
extremální
řízený přechod mezi bázemi
využívá transponované matice
zajištěn testem optima X testem přípustnosti
zda jsme dospěli do koneč. řeš (kmin
dualita – je základem duálně simplexového algoritmu
asymetrická
obecná
5. PŘEDNÁŠKA
Při rekonstrukci modelů se vyhýbáme rovnici, protože podmínka rovnice nám něco determinuje
Rovnice redukují prostor možného řešení na přímku

x3 120
V lineárních modelech používáme 6 omezujících podmínek:
P = (rovnice)
> kapacitní podmínka….
< požadavkové
Bilanční
Pomocné
Poměrově přípustkové

 EMBED Equation.3 -horní hranice

(
CXB  EMBED Equation.3 c1c2cn  EMBED Equation.3  EMBED Equation.3 x
 EMBED Equation.3 x1x2…..xjxnC1
.
.
.
Cm(1
.
.
.
(naij
a2j
a3j

amj(
(
(
(Zj - cj


Vm


 EMBED Equation.3
 EMBED Equation.3 - reálné
- 0 EMBED Equation.3
- + - M x P



Proměnná = předem neznámý rozsah j-tého procesu, jestliže jde o pomocnou proměnnou matice A nám prezentuje umělou bázi.
vektory záporné fiktivní proměnné nám rozbrazují možné překročení minimálně stanoveného požadavku,
kladné fiktivní proměnné nám říkají nevyčerpání provozní (disponibilní) kapacity,
xj – vlastní proměnná – rozměr proměnné
- vektor koeficientu, který vymezuje – kvalifikuje – zobrazuje vztah konkrétního procesu
xj k soustavě omezení (tzn. k systému jako celku)
CÍL – nalezení optimální kombinace – maxima nebo minima
-možné pojetí čtyřmi způsoby
je to jednotkové změnové zobratení j-tého procesu
musím zvolit jednotku – volba jednotky je složitá ∆xj
problém: homogenita koeficientu matice aij, kdy při jednotkovém rozbrazení jednotky
volím jednotky tak, aby byl rozdíl koeficientu minimální (řádkové příbuzné)
máme 3 různé typy koeficientru aij
j-tý proces nepotřebuje i-tý zdroj
matice A je soustava přímých faktorových toků, vztažených k j-tému procesu
každý vektor proměnné je m-dimenzionální lineární produkční funkce
nekonečné mmožství míry susbstituce (=záměna faktorů)
1ha
---
aij
0,185
t/ha
aij=0
jednotková vazba proměnné procesu na systém jako celek
co se statne se systémem jako celkem, jestliže změním rozměr j-tého procesu o jednotku ∆
jestliže koeficient aij jsou směrnice dílčí lineární faktorové funkce
faktor osivo v t
aij = 0,2t/ha
- je tvořen koeficienty aij, které jsou směrnice faktorových toků na jednotku j-tého procesu
Předpoklady modelu
všechny parametry modelu se mohou měnit
přidávání nových procesů
přidávání různých typů omezujících podmínek
různé podmínky můžeme disagreagovat (rozčlenit) na libovolný konečný počet dílších podmínek
Závěr
můžou se měnit podmínky (vektor pravých stran) a sazby (koef. účelové funkce), koeficienty funkce aij (zvětšit, zmenšit)
matice by měla být nejpravdivější, nejpodobnější skutečnosti
zkouška: testování logické konzistence modelu, tzn., že sestavíme matici A a násobím vektorem proměnných zjistím nároky
A *.3
β1
.
.nároky jednotlivých faktorů
.
Βn
Test logické konzistence
zda tam jsou chyby
chování procesů, podmínek a modelu jako celku
je to nezastupitelné – autor se musí s modelem zžít
pouze násobení matic
6. PŘEDNÁŠKA
Senzitivní analýza
- opačné chování
- náhodné procesy vtěsnat do matematické soustavy
- vznikne nová proměnná X1 – kolik zboží dovezeme od prvního dodavatele ke spotřebiteli
10
15
25Xj – přiřazení odběrateli
50
Vyškrtnu posl.řádek
8
3
6
7
9
10
6
7
3
9
8
6
10
3
6
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
X11
X12
X13
X14
X15
1
1
1
1
1
<
═
10
1
1
1
1
1
<
═
15
1
1
1
1
1
<
═
25
1
1
1
═
8
1
1
1
═
12
1
1

1
═
15
1
1
1
═
5
1
1
1
═
10
Xj = m x n reálných vazeb – máme mxn proměnných
Problém: ! 1.) matice modelu je singulární – obsahuje lineární závislost hodnot < m
║
- simplexová tabulka obsahuje m x n proměnných a m + n podmínek (omezovacích)
║
2.) simplexovou tabulku převedeme ze singulárního tvaru na regulární matici
- může se vyskytnout otázka:Jak převedeme matici singulární na regulární?
Řešení: vyškrtneme poslední podmínku
3.) nacházíme se ve vektorovém prostoru dim (m+n-1)
= báze (řešení) bude obsahovat 7 procesů z (15) = řešení základní (7 nenulových vektorů)
- může se stát – řešení méně vektoru – v tom případě je degenerované (pokud by bylo méně než m+ n – 1 degenerované řešení)
Řešení:
= pakliže hledám řešení minimální – může se stát, že některá proměnná je zakázaná -není přímý spoj mezi i –tým zdrojem a j-tým spotřebitelem - prohibitivní sazby (velká,kladná)- obvykle volím 99, 999….)
- maximalizujeme- viz. Sadba brambor dáváme zápornou prohibitivní sazbu( znemožní,aby konkrétní proměnná vstoupila do báze ( - 99,999…)
-úloha maximalizační, hodnoty jsou kladné
- žádná proměnná neustoupila do báze v nulovém rozsahu = NENÍ DEGENEROVÁ
Xj: proces, který nevstoupila do řešení
Zkm = Zk – Xj x(Zj – Cj)
=komplexní systémové ocenění změn, které nastanou v systému, jestliže zařadíme do řešení 1 jednotku – nedojde ke změně i-tého faktoru
7. PŘEDNÁŠKA
Duality:
Symetrická
Asymetrická
Obecná
Význam duality:
1.úroveň – k odvozování matematický vět (struktury axiomů, predikátů, hypotéz, teorémů)
x2 + 1 = 0
x2 = -1
x = √-1
x1 > 5
x1 < 5
při určení bodu není použita rovnice, ale omezující podmínky
hodnoty v případě rovnic nejsou omezeny co do znaménka
2.úroveň – duální simplexový algoritmus, který umožňuje řešit úlohy, které jsou primárně formálně nepřípustné
3.úroveň – umožňuje transpozici úlohy dle požadovaného rozsahu úlohy
- duální proměnná „y“ může být libovolná (kladná i záporná)
- záleží na výchozích podmínkách modelu
4.úroveň – dualita je využívána ve speciálních úlohách při konstrukci tzv. okrajových duálních proměnných, které mi kriteriálně hodnotí vlastnosti zkoumané soustavy.
Ui = řádková duální proměnná
Vj = sloupcová duální proměnná
Wk = kubická duální proměnná
Existují úlohy, kde použití simplexové metody je těžkopádné. Vedlo by k rozsáhlým úlohám.
Setkáme se s těmito úlohami:
jednostupňová dopravní úloha – JDÚ (přímá)
vícestupňová d. ú. (dvoustupňová) – VDÚ – 2DÚ
přiřazovací problém – PP
zobecněný distribuční problém – ZDP
okružní dopravní problém (okružák) – ODP
alokační problémy – AP (prostorová alokace)
My si ukážeme v tomto semestru první tři.
Mějme libovolný konečný počet dodavatelů D1-Dm.
Disponibilní provozní kapacity dodavatelů (zdroje) a1-am.
Mějme libovolný konečný počet spotřebitelů (odběratelů).
Požadavky spotřebitele b1-bn.
3 možné varianty:
m = n- čtvercová matice
m < n - obdélníková matice
m > n- obdélníková matice
Mezi dodavateli a odběrateli existují spoje, hrany, cesty… (systém cestní sítě).
Je ale možné, že je rozbitý třeba most a trasa neexistuje. Trasu obsadíme M při minimalizaci (prohibitivní sazbou). Tabulka může být i s neúplnou cestní sítí.
Rozdíl mezi tímto a simplexem
U simplexu může nastat žádné řešení, kdežto tyto úlohy mají řešení vždy.
CO (co povezeme)
KOLIK (kolik povezeme)
KDY
ODKUD (od kterého dodavatele)
KAM
ČÍM
JAK (jak rychle)
ZA KOLIK
JAKÁ OMEZENÍ
Není takový algoritmus, který by současně dokázal vyřešit všechny otázky. Každá z metod to řeší z určitého dílčího počtu omezeného počtu kritérií.
Vycházíme ze základní formy:
hledáme min. účelové funkce Zmin = ∑ ∑ cij xij
(ta první suma je od i=1 do m a druhá od j=1 do n)
xij = množství přepravy od i-tého dodavatele k i-tému spotřebiteli, může se nacházet v intervalu 0 – horní hranice
0 ≤ xij ≥
min [aij bj]
x22 < 5
∑ bj >=< ∑ ai (pod první sumou je j, pod druhou i)
Je soustava omezení, které vymezují náš přepravní prostor.
bj = požadavky spotřebitele
ai = celkové disponibilní zdroje
cij = hodnotící kritérium cesty, trasy, spoje
za cij si můžeme zvolit reálnou sazbu
Lij – vzdálenost v km
Tij - doba
Qij – kvalita vozovky, míra opotřebení auta
Nij – náklad
Kij – míra průchodnosti
xij - nezáporné!!!
V případě, že kapacita dodavatele a požadavky spotřebitele jsou tzv. nevyvážené používáme techniku tzv. fiktivního dodavatele (požadavky odběratele jsou větší než kapacita dodavatele) a nebo naopak pokud jsou větší zdroje… používáme fiktivního spotřebitele.
Problém vyvážené úlohy – fiktivní dodavatel a spotřebitel mají nulovou sazbu cij
U fiktivního dodavatele = nevyrobené, neprodané množství materiálu
U fiktivního spotřebitele = neodebrané, nerealizované množství materiálu
Úloha musí splňovat:
homogenita úlohy – připravovaný substrát je homogenní
je lhostejné, který dodavatel zásobuje kterého spotřebitele
pravidlo homogenity nemusí platit vždy a všude pro praktické úlohy
při odlišných substrátech – dekompozice úlohy na submatice, které specifikují možnosti zásobování
Tabulka - matice dopravní úlohy
řešení probíhá cyklem několika kroků
výchozí řešení úlohy (není zde pojem „přípustné“, řešení úlohy musí být základní, bazické, nedegenerované), obsahuje m+n-1 polí
i/j
S1
S2
S3
S4
S5
ai
D1
5 3
5
8
2
1
5
D2
6
2 7
5 5
2
8
7
D3
7
4
5
8 9
7 2
15
D4
3
7
4
8
4 2
4
bj
5
2
5
8
11
31/31
∑ aj = ∑ bi
Existuje několik metod, jak nalézt výchozí základní řešení:
metoda severozápadního rohu (NWC)
indexová metoda – vzestupná, sestupná, kombinovaná
habrova frekvenční – aproximat. metoda, která rychle konverguje do řešení v blízkosti optima
VAM – přibližná řešení, která nejsou špatná
a další…
my si ukážeme 1,2,4
m+n-1 = 5+4-1
účelová funkce: 5*3 + 2*7 + 5*5 + 8*9 + 4*2 = 63
8. PŘEDNÁŠKA
Indexová metoda – vzestupná
S 1
S 2
S 3
S 4
S 5
ai
D 1
3
20
7
20
5
3
8
27
2
15
85
D 2
4
7
2
72
8
5
72
D 3
4
3
45
8
7
6
45
D 4
2
35
5
8
6
4
35
DF 5
0
0
0
0
63
0
63
bj
55
65
75
90
15
237
∑ ai > ∑ bj ……. Úloha je nevyvážená
DF5 je fiktivní dodavatel (zdroj), který má nulové sazby cij
Cij (DF5) = 0
obsazení políčka fiktivního dodavatele = nedodané zboží
( fiktivní spotřebitel = neodebrané zboží, také by měl nulové sazby Cij )
Ekonomické hledisko severo-západního rohu spočívá v uspořádání sazeb systému Cij
Tento problém řeší indexová metoda:
vychází z postupného obsazování políček od min. sazby Cij
Zmin = ∑i ∑j a i j x i j …..základní řešení (určitá nevýhoda simplex. metody)
Indexová metoda sestupná
z řešení ( tabulky) nejprve vyřadíme vhodně zvolený počet nejvyšších vazeb a pak přiřazujeme
Indexová metoda kombinovaná
kombinace metody vzestupné a sestupné
Metoda VAM
princip řádkových a sloupcových diferencí ∆ i a ∆j
nemůžeme obsadit nejvýhodnější , ale 2. nejvýhodnější pole v dané situaci
diference = rozdíly dvou nejnižších sazeb v řadě (řádku, sloupci)
Postup:
určíme řadu s max. diferencí
vybereme políčko s min. sazbou
obsadíme max. možnou hodnotou
při vyřazení kapacity zdroje či kapacity odběratele – řadu vyřadíme a přepočítáme diference
Pozn. Tabulka která je zde uvedena početně neodpovídá, je v ní chyba
S1
S2
S3
S4
S5
ai
∆i
∆i
D1
3
7
5
5
8
2
15
20
1
5
D2
4
7
2
30
8
5
30
2
X
D3
4
3
40
8
7
6
40
1
3
D4
2
45
5
15
8
6
4
60
2
1
bj
45
55
35
34
26
∆j
1
2
3
1
2
Severozápadní roh
S1
S2
S3
S4
S5
ai
uj
D1
3
45
-1 7
6
6 5
11
1 8
9
5 2
7
45
3
D2
4
17
7
33
-
10 2
12 +
2 8
10
3 5
8
50
4
D3
-4 4
0
3
38
+
8
17
-
-1 7
6
-2 6
4
55
0
D4
-2 2
0
-2 5
3
8
26
6
20
4
19
65
0
bj
62
71
43
20
19
215
vj
0
3
8
6
4
Jak je řešení vzdálené od optima zjistíme pomocí modifikované metody – duální sazby ui a vj
Metoda MODI – Dantzig.
Postup:
vybereme řadu, kde je největší počet obsazených polí duální hodnotu ui, vj, dosadíme nulovou hodnotu
ui + vj = Cij ( Xij > 0)
Pro všechna obsazená pole vypočítáme ostat. duál