P 416 Operačná analýza 1

• Janáček, J.: Matematické programování. EDIS, ŽU-Žilina, 1999, 225 s.
• Janáček, J.: Operační analýza I, VŠDS, Žilina, 1995, 232 s. (druhé vydanie 1997)
• Janáček, J.: Řešení úloh matematického programování na osobních počítačích, VŠDS, Žilina, 1993, 128 s.
• Plesník J., Dupačová J., Vlach M.: Lineárne programovanie, Alfa, Bratislava, 1990, 320 s.

1. Modely základných úloh, podmienky prípustnosti, účelová funkcia, klasifikácia úloh podľa charakteristík modelov [1] s. 11-18, [2] s. 5-19.
2. Formulácia modelov úloh lineárneho programovania (LP) [1] s.19-27, [2] s. 20-36:
   • plánovanie výroby
   • zmiešavacia úloha
   • dopravná úloha
3. Formuácie úloh a ich grafická reprezentácia úloh LP [2] s. 51-62. Krajný bod, konvexnosť [1] s. 45-50, [2] s. 63-66.
4. Kanonický tvar úloh LP. Doplnkové a umelé premenné [1]s. 53, 65, [2] s. 67-70, 88. Bázické prípustné riešenie [1] s. 54-55, [2] s. 70-71. Existenčná veta LP[1] s. 51, [2] s. 66.
5. Princíp algoritmu simplexovej metódy a jeho realizácia [1] s. 62-66, [2] s. 73-99.
6. Prehľad variantných metód riešenia úloh LP [1] s. 67-71, [2] s. 101-111.
7. Postoptimalizačná analýza, parametrické programovanie [2] s. 113-132.
8. Formulácia úloh diskrétneho programovania
   • úloha o batohu [1] s. 24
   • obchodný cestujúci [1] s. 37-39, [2] s. 160-163
   • rozmiestnenie dopravnej flotily [1] s. 29-30, [2] s. 145-146
   • prideľovanie dopravných prostriedkov [1] s. 30-31, [2] s.147-149
   • optimalizácia pracovnej čaty [2] s. 191-197
9. Princíp metódy vetiev a hraníc a jej použitie pre riešeniea úloh celočíselného lin. programovania (CLP) [1] s. 135-146, [2] s. 171-177. Kolesárov algoritmus [1] s. 146-148, [2] s. 183-186.
10. Land-Doigova metóda riešenia úloh zmiešaného CLP [1] s. 121-125, [2] s.177-182.
11. Matematická formulácia úloh nelineárneho programovania a ich klasifikácia [1] s. 41-43, 169-174, [2] s. 199-212, [3] 81-91. Metóda zlatého rezu [2] s. 214-215 a princíp gradientovej metódy [2] 217-218. Varianty gradientových metód [2] 219-224.
12. Metódy druhého rádu pre riešenie nelineárnych úloh [2] s. 224-226. Riešenie nelineárnych úloh s obmedzeným definičným oborom [2] s. 226-230.

1. Formulácia matematických modelov (toky v sieťach [2] s. 36-42, [3] s. 28-38, dopravná [1] s. 19-24, [2] s. 24-36, [3] s. 18-21 a priraďovacia úloha[1] s. 26)
2. Zoznámenie sa so systémom MOR [3] s. 5-13, 115-123.
3. Výpočet rozkladových koeficientov. Formulácia mat. modelov (plánovanie výroby[3] s. 5- 18, rezná úloha [1] s. 18-19, [2] s. 20-22, zmiešavacia úloha[2] s. 22-24)
4. Vytváranie modelov úloh LP v systéme MOR a ich grafické zobrazenie [3] s. 11-12.
5. Zostavovanie zložitejších lineárnych modelov.
6. Vytváranie modelov úloh LP v systéme MOR a ich riešenie. Použitie systému XPRESS pre úlohy LP.
7. Precvičovanie algoritmu simplexovej metódy.
8. Riešenie úloh parametrického programovania a citlivosti [3] s. 45-48.
9. Formulácia úloh celočíselného lineárneho programovania(rozmiestnenei dopravnej flotily, prideľovanie dopravných prostriedkov).
10. Land- Doigova metóda, precvičovanie meódy vetiev a hraníc. Modelovanie v systéme XPRESS.
11. Test ! (25 min.)Formulácia úloh nelineárneho programovania, precvičovanie gradientovej metódy.
12. Gradientové metódy - dokončenie [3] s. 81-91.

1. Řešitel vytvoří pomocí určeného programového vybavení model zadané silniční sítě a předloží výsledek zadavateli ke kontrole.
2. Po ověření správnosti modelu sítě mu bude jeho cvičícím v předmětu P416 (P410) Operační analýza 1 zadána konkrétní úloha včetně specifikace množiny J a jiných konkrétních uzlů.
3. Řešitel vytvoří vlastní programové vybavení v Pascalu, kterým z modelu sítě vypočítá potřebné konstanty pro zadanou úlohu a ve formátu vyžadovaném systémem XPRESS je uloží do svých souborů.
4. Řešitel sestaví model konkrétní úlohy, zapíše ho symbolicky v modeleru systému XPRESS a vyřeší úlohu na určeném počítači (vyřeší i varianty vyplývající z potřeby řešit citlivost).
5. Řešitel ověří přípustnost optimálního řešení a zpracuje celou práci včetně grafického výstupu.

1. pro zadaná místa A, B, C a množinu obcí J a pro zadané parametry, vypočítat optimální přidělení vozidel obcím,
2. vyšetřit citlivost získaného řešení na změnu jednotkových nákladů na jeden km jízdy v intervalu <10,60> Sk pro vozidla umístěná v A,
3. znázornit výsledek úlohy z 1) graficky na mapě a provést kontrolu přípustnosti optimálního řešení z 1).

1. pro zadané místo A a množinu obcí J a pro zadané parametry, vypočítat optimální soustavu tras autobusů,
2. vyšetřit citlivost hodnoty účelové funkce na maximální povolený počet obcí v trase autobusu, stačí to vyšetřit pro počet obcí 1, 2, 3.
3. znázornit výsledek úlohy z 1) graficky na mapě a provést kontrolu přípustnosti optimálního řešení z 1).

Nalezněte optimální umístění p středisek rychlé pomoci v obcích z množiny J tak, aby byla minimalizována největší vzdálenost mezi obcí jJ a jí nejbližším střediskem (úloha o p-centrech). Vaší úlohou je

1. pro zadanou množinu obcí J a pro p= 4 , vypočítat optimální umístění středisek,
2. vyšetřit citlivost hodnoty účelové funkce na změnu parametru p, stačí to vyšetřit pro hodnoty 1,2,3,4,5.
3. znázornit výsledek úlohy z 1) graficky na mapě a provést kontrolu přípustnosti optimálního řešení z 1).

Firma buduje dvoustupňový distribuční systém, kterým bude uspokojovat požadavky obyvatel v obcích z množiny J. Primárním zdrojem distribučního systému je obec A. Z této obce je zboží zákazníkům dopravováno buď přímo s náklady 3 Sk na kilometr vzdálenosti a jednotku zboží a nebo přes mezisklad. Náklady na přepravu jedné jednotky zboží na jeden kilometr na trase primární zdroj - mezisklad jsou 1 Sk a na trase mezisklad - obec 3 Sk. Požadavky jednotlivých obcí v plánovacím období jsou číselně shodné s počtem jejich obyvatel b_j, jJ. Vybudování meziskladu stojí v přepočtu na plánovací období 100000 Sk. Je třeba zjistit, zda mají být budované mezisklady, pokud ano, tak kolik a v kterých obcích.
Vaší úlohou je

1. pro zadané místo A a množinu obcí J a pro zadané parametry, vypočítat optimální strukturu (umístění meziskladů a příslušné atrakční obvody) distribučního systému,
2. vyšetřit citlivost optimálního počtu středisek na fixních nákladech na vybudování střediska v rozmezí 10000-500000,
3. znázornit výsledek úlohy z 1) graficky na mapě a provést kontrolu přípustnosti optimálního řešení z 1).

V obcích A, B, C, D jsou umístěné sklady, které mají pořadě kapacity 0.5q, 0.4q, 0.3q a 0.2q. Z uvedených skladů jsou zabezpečované požadavky obcí z množiny J, kde požadavek obce je 0.1b_j, kde b_j je počet obyvatel obce j. Požadavky jsou uspokojovány vozidly o kapacitách 500 jednotek a vozidla provádějí zásobování výhradně kyvadlovými jízdami sklad - obec - sklad. Náklady na jeden kilometr jízdy vozidla bez ohledu na jeho vytížení jsou 30 Sk. Vypočítejte nejlevnější zásobovací plán pro obce s respektováním skladových kapacit, když
.
Vaší úlohou je

1. pro zadaná místa A, B, C, D a množinu obcí J a pro zadané parametry, vypočítat optimální zásobovací plán obcí z množiny J,
2. vyšetřit citlivost optimálního řešení na kapacitu skladu v místě D v rozsahu 0-q,
3. znázornit výsledek úlohy z 1) graficky na mapě a provést kontrolu přípustnosti optimálního řešení z 1).

1. Poznať vzťah medzi modelom a skutočnosťou a vedieť klasifikovať rôzne typy úloh a modelov. Vedieť formulovať úlohy :
   
   • o max. toku v sieti
   • plánovaní výroby
   • zmiešavacie
   • priraďovacie
   • dopravné
   • rezné
2. Poznať základné pojmy lin. programovania :
   
   • krajný bod
   • konvexnosť
   • konvexný polyéder
   • bázické prípustné riešenie
   • doplnkové premenné
   • umelé premenné
3. Poznať simplexovú metódu a maticové vzťahy medzi tabulkami, poznať vetu o existencii riešenia úlohy LP.
4. Vedieť použiť systém MOR a XPRESS pre riešenie úloh LP.
5. Vedieť vyšetriť citlivosť riešní úloh LP vzhľadom ku zmene koeficientov b a c, vedieť riešiť úlohy parametrického programovania (ručne i pomocou XPRESS).
6. Vedieť formulovať úlohy diskrétneho programovania :
   
   • rozmiestnenia dopravnej flotily
   • o batohu
   • obchodného cestujúceho
   • priraďovania dopravnych prostriedkov
   • dopravnej úlohy s fixnou sadzbou
   • úlohy s logickými podmienkami
7. Poznať princíp metódy vetiev a hraníc a vedieť ju použiť.
8. Vediť použiť systém MOR a XPRESS pre riešenie úloh CLP.
9. Poznať princíp metódy zlatého rezu, gradientových metód a metód druhého rádu. Vedieť vyšetrovať vlastnosti funkcií viac premenných a definitnosť kvadratických foriem.
10. Poznať metódu projekcie a metódu pokutových funkcií.
11. Vedieť riešiť úlohy nelineárneho programovania pomocou programového systému MOR.

0 - 12 bodov       nevyhovel
13 - 16 bodov      dobre
17 - 20 bodov      veľmi dobre
21 a viac          výborne

	S1	S2	S3	S4
Z1	4	8	9	5
Z2	7	6	6	4
Z3	8	6	9	6

Príklad 1 :

Zostavte model pre vyššie uvedenú úlohu a rešpektujte dodatočnú podmienku, že zo zdroja 2 k spotrebiteľovi 3 môžete prevážať najviac 50 jednotiek tovaru.

Príklad 2 :

Zostavte model pre vyššie uvedenú úlohu a rešpektujte dodatočnú podmienku, že keď zo zdroja 1 k spotrebiteľovi 2 poveziete nejaký tovar, musíte jednorázové do komunikácie investovať 2000.

Príklad 3 :

Zostavte model pre vyššie uvedenú úlohu a rešpektujte dodatočnú podmienku, že zo zdroja 1 k spotrebiteľovi 2 môžete prevážať najviac 50 jednotiek tovaru, a keď tento objem prekročíte, musíte jednorázovo do komunikácie investovať 2000.

Príklad 4 :

Zostavte model pre vyššie uvedenú úlohu a rešpektujte dodatočnú podmienku, že zo zdroja 1 k spotrebiteľovi 2 môžete prevážať najviac 30 jednotiek tovaru, a keď tento objem poekročíte, musíte jednorázovo do komunikácie investovať 2000. Pokiaľ ale prekročíte objem 50, musíte investovať ďalších 1000.

Príklad 5 :

Zostavte model pre vyššie uvedenú úlohu a rešpektujte dodatočnú podmienku, že pre prepravu sú k dispozícii len kontajnery s obsahom 50 jednotiek tovaru, a že za prepravu jedného kontajneru zo zdroja k spotrebiteľovi zaplatíme bez ohľadu na vyťaženie poplatok daný tabuľkou.

40	80	90	50
70	60	60	40
80	60	90	60

Príklad 6 :

Zostavte model pre úlohu 5 a rešpektujte dodatočnú podmienku, že keď použijeme pre prepravu viac než 4 kontajnery zaplatíme dodatočný poplatok 1000.

Príklad 7 :

ako sa zmení model pôvodnej úlohy a význam premenných, keď na jednotlivých smeroch bude dochádzať k stratám daným v % z naloženého množstva nasledujúcou tabuľkou.

5	1	2	3
4	2	1	4
7	6	3	2

Príklad 8 :

Ako sa zmení model pôvodnej úlohy, keď úlohou bude minimalizovať najväčší tok tovaru medzi zdrojom a odberateľom.

Príklad 9 :

Ako sa zmení model pôvodnej úlohy, keď úlohou bude maximalizovať najmenší tok tovaru medzi zdrojom a odberateľom.

Príklad 10 :

Ako sa zmení model pôvodnej úlohy, keď úlohou bude maximalizovať najmenší nenulový tok tovaru medzi zdrojom a odberateľom.

Príklad 1 :

Nech K E_n je konvexná množina. Dokážte, že množina Q={y/y=ß.x, xK} je tiež konvexná. Pozn. Q získate tak, že každý prvok množiny K vynásobíte reálnym číslom ß.

Príklad 2 :

Minkovského súčet dvoch podmnožín K, Q z euklidovského priestoru E_n je definovaný takto: K+Q={z/z=x+y, x K, y Q}. Rozhodnite, či Minkovského súčet dvoch konvexných množín z E_n je alebo nie je konvexná množina. Dokážte!

Príklad 3 :

Pre množinové operácie U, , - (zjednotenie, prienik, rozdiel dvoch množín) rozhodnite, či a za akých okolností je pre konvexné množiny Q a K výsledok operácií Q U K, Q K, Q-K konvexná.

Príklad 4 :

Ktorá z nasledujúcich množín v E₃ je konvexná a ktorá je dokonca konvexný polyéder?

1. |x₁| 1, |x₂| 1, |x₃| 1
2. |x₁| +|x₂|+|x₃| 1
3. -1 x₁ x₂ x₃
4. |x₁+x₂+x₃| 1
5. |x₁+x₂+x₃| 1, |x₁| 2, |x₂| 2, |x₃| 2
6. |x₁| |x₂| |x₃|
7. |x₁| |x₂| |x₃| 1
8. x₁+x₂+x₃ 1, x₁ 0, x₂ 0, x₃ 0

Príklad 5 :

Pre konvexné polyédre z 4. nájdite všetky krajné body a vyjadrite príslušné množiny ako ich konvexnú kombináciu.

Príklad 6 :

Zobrazte si množiny a)-h) z úlohy 4. v E₃.

Príklad 7 :

Vyjadrite množinu 0 x₁ x₂ x₃ ako nezápornú kombináciu troch bodov.

Príklad 1 :

Dokážte, že bod z = <3; 1,25> je konvexnou kombináciou bodov x=<2; 1> a y=<6, 2>

Príklad 2 :

Dokážte, že bod z=<0; 0,5> je lineárnou kombináciou bodov x=<2; 1> a y=<6, 2> a nie je ich konvexnou kombináciou.

Príklad 3 :

Dokážte, že bod z=<2; 2> nie je ani lineárnou kombináciou ani konvexnou kombináciou bodov x=<2; 1> a y=<6, 2>

Príklad 4 :

Dokážte, že množina všetkých bodov z E₂ vyhovujúce nerovnosti x₁² + x₂² <= 4 JE KONVEXNÁ.
Návod: Využite to, že dĺžka vektora je definovaná |x|=(x₁²+x₂²)^1/2 a toho, že pre skalárny súčin vektorov x a y platí x.y=|x||y|cos(ß), kde ß je uhol zvieraný x a y.

Príklad 5 :

Dokážte, že množina všetkých bodov z E₂ vyhovujúcich nerovnostiam 1/x₁ <= X₂ A x₁ + x₂ <= 2 NIE JE KONVEXNÝ.
Návod : využite nerovnosti x₁y₂ + x₂y₁ >= (x₁x₂y₁y₂)^1/2

Príklad 6 :

Preveďte všetky modely z OA1, ktoré ste doteraz vytvorili na kanonický tvar a vysvetlite význam všetkých doplnkových premenných vo všetkých podmienkach, kde ste ich zaviedli.

Príklad 7 :

Ktorý z uvedených vektorov je

1. prípustným riešením
2. bázickým prípustným riešením nasledujúcej sústavy :

x1 + 2x2 + 4x3 = 8       vektory : <1, 1, 1>
      x2 + 6x3 = 12                <0, 2, 1>
 x1 >= 0, x2 >= 0, x3 >= 0         <0, 4, 0>
                                  <0,-1, 2>

Príklad 8 :

Nájdite všetky bázické prípustné riešenia sústavy :

x1 + x2 + 2x3 + x4 + 2x5 = 4       
     x2 + x3 + 2x4 + 2x5 + x6= 4       
xj >= 0 pre j=1,..,6 .

Viackomoditná dopravná úloha :

Firma zásobuje svoje tri predajne z dvoch veľkoskladov zdrojov tovarom dvoch druhov. Pre doplnenie zásob je potrebné do predajní 1, 2 a 3 doviezť 30, 20 a 60 jednotiek tovaru prvého druhu a 40, 20 a 15 jednotie tovaru druhého druhu. Zásoby jednotlivých druhov tovarov v skladoch 1 a 2 sú 100 a 50 jednotiek prvého druhu a 50 a 40 jednotiek tovaru druhého druhu. Jednotkové dopravné náklady , tj. náklady na dopravu jednej jednotky tovaru prvého druhu zo sklady i do predajne j sú dané v tisícoch Sk maticou koeficientov uvedenou v tabuľke 11 a jednotkové náklady na dopravu tovaru druhého druhu sú v tabuľke 12.

Tab. 11	Jednotkové náklady na dopravu tovaru 1. druhu		Tab. 12	Jednotkové náklady na dopravu tovaru 2. druhu
	i \ j 1 2 3 1 4 8 9 2 7 6 6			i \ j 1 2 3 1 3 4 4 2 1 2 3

Jedna jednotka tovaru 1. druhu má hmotnosť 500 kg a jedna jednotka tovaru 2. druhu má hmotnosť 600 kg po jednotlivých trasách od skladov k predajniam je možné prevážať len obmedzené množstvá tovarov. Kapacitu týchto úsekov udáva v kg tabuľka 13.

Tab. 13	Kapacity úsekov dopravnej siete [ kg ]
	i \ j 1 2 3 1 22 000 16 000 20 000 2 22 000 16 000 20 000

Je potrebné určiť čo najmenej nákladný zásobovací program firmy.

Príklad 1 :

Preveďte pomocou pivotovej transformácie sústavu

x1 +3x2 - x3      + 2x5      = 0
  -2x2  + 4x3  + x4           =12
  -4x2  + 3x3      +8x5 + x6 =10  

na taký tvar, aby obsahovala susedné bázické prípustné riešnie so stĺpcom A₃ v novej ortonormálnej bázy, a aby z báze vypadol stĺpec A₁.

Príklad 2 :

Ukážte, že množina prípustných riešení obsahuje polpriamku a teda nie je konvexný polyéder.

3x1    +x3+ 2x4    -x6    = 5
-x1 +x2    +3x4    -2Xx6  = 0
2x1          +4x4 +x5      = 3
-x1           -x4    -6x6+x7 = 4 
     xj >=0 pre j= 1..7

Príklad 3 :

Preveďte nasledujúcu úlohu na kanonický tvar a konštruujte podľa vyššie uvedeného postupu polopriamku, ktorá leží celá v množine prípustných riešení úlohy. Znázornite na nákrese množinu prípustných riešení aj s konštruovanou polopriamkou.

-x1 +2x2  <= 4
-2X1 +x2  <= 24
X1 , x2 >= 0

Príklad 4 :

Nájdite pomocou simplexovej metódy riešenie úlohy :

Maximalizujte f = x1  + x2 
za podm  2x1  + 3x2 <= 6
         4X1 + 2x2 <= 8
          X1 + x2 >=1
   x1 , x2  >= 0

Príklad 5 :

Nájdite pomocou simplexovej metódy riešenie úlohy : Minimalizujte f = x₁ + 2x₂ za vyššie uvedených podmienok.

Príklad 6 :

Pokúste sa nájsť pomocou simplexovej metódy riešnie úlohy :

Maximalizujte f = x1  + x2 
za podm  2x1  + 3x2 >= 6
         4x1 + 2x2 >= 8
          x1 , x2  >= 0

Príklad 7 :

Pokúste sa nájsť pomocou simplexovej metódy riešenie úlohy :

Maximalizujte f = 4x1  + 5x2 
za podm  3x1 + 6x2 <= 2100
         2X1 + x2 >= 800
           x1 , x2  >= 0

Výsledky porovnajte s riešením úloh pomocou geometrického prístupu.

Úloha návrhu logistického systému

Koncern porýva dopyt po dvoch druhoch výrobkov A a B, ktorými zásobuje sklady S1, S2 a S3 s požiadavkami v tauľke 27. Výrobky typu A a B môžu byť vyrábané v továrni T1 a T2, pričom jednotkové dopravné náklady, na jednu tonu výrobku, z týchto dvoch skladov sú v tisícoch Sk uvedené v tabuľke 28.

Tab. 27			Tab. 28
	S1 S2 S3 A [t] 50 60 20 B [t] 30 30 40			S1 S2 S3 T1 0.1 0.8 1 T2 1 0.7 0.3

Na výrobu jednej jednotky (tony) sú potrebné tri tony plechov a 0,5 jednotiek (ton) polotovarov vyrábaných v továrni T3. Na výrobu jednej jednotky výrobku B sú potrebné dve tony plechov a 0,8 ton polotovarov z továrni T3. Výrobky sú vyrábané na výrobných linkách, z ktorých linka na výrobky A má hmotnosť 2 t, obstarávaciu cenu 500 tis. Sk a za plánovacie obdobie vyprodukuje 5 t výrobkov. Linka na výrobky B má hmotnosť 1 t, cenu 300 tis. Sk a za plánovacie obdobie vyprodukuje 4 t výrobkov. V súčasnosti vlastní koncern 10 liniek na výrobky a umiestnených v T1 a 30 liniek na výrobu výrobkov B umiestnených v T2. KOncern môže za uvedenú cenu linky oboch typov prikúpiť a môže tiež linky, ktoré už vlastní premiestňovať medzi továrňami T1 a T2 s nákladmi 3 tis. Sk na presun jednej tony výrobného zariadenia.
V továrni T3, ktorá tiež patrí koncernu, sú vyrábané polotovary pre výrobu výrobkov A a B. Pre výrobu 1 t polotovarov je potrebné 0,8 t plechov. Plech, ako pre výrobu polotovarov, tak aj pre výrobu výrobkov A a B odoberá koncern zo železiarní Z1 a Z2 za cenu 7 a 8 tis. Sk za 1 tonu. Jednotkové dopravné náklady na 1 t v tisísoch Sk zo železiarní do tovární T1, T2 a T3 udáva tabuľka 29.

Tab. 29
	T1 T2 T3 Z1 1,5 2,1 0.9 Z2 0.2 1.1 0.2 Z3 0.8 0.7 0

Kapacity sú oveľa väčšie než možné požiadavky koncernu.
Navrhnite také rozmiestnenie výroby do tovární T1 aT2 a taký zásobovací plán, aby celý systém zabezpečil s minimálnymi celkovými nákladmi požiadavky skladov S1, S2 a S3.

ZOSTAVTE LINEÁRNY MODEL VYŠŠIE UVEDENEJ ÚLOHY

Príklad 1 :

Preveďte nasledujúce dva modely na kanonický tvar, zostavte príslušné tabulky, určite súradnice východzieho bázického riešenia a vypočítajte pomocný riadok simplexovej tabulky. Zobrazte množinu prípustných riešení v E₂.

minimize f=-3x1-2x2	minimize f=-x1-2x2

subject to		subject to
	3x1+x2<12		-X1+2X2>2
	5x1+x2<15		-X1+X2<7
	X1+2X2<20		10X1+X2>30
				x1+2x2>12
      x1, x2>0		   x1, x2>0

Príklad 2 :

Kde bude v tabulke 1. pivot pri použití obyčajného stĺpcového pravidla?

Príklad 3 :

Formulujte také stĺpcové pravidlo, aby jednou pivotovou transformáciou klesla účelová funkcia čo najviac. Použite to pravidlo na Tab. 1.

	    C:      -3.00   -2.00
Tab. 1      B       X1      X2      Slack1  Slack2  Slack3  |  b
         ===================================================|========
           Slack1   3.00    1.00    1.00    0.00    0.00    |  12.00
           Slack2   5.00    1.00    0.00    1.00    0.00    |  15.00
           Slack3   1.00    2.00    0.00    0.00    1.00    |  20.00
         ------------------------------------------------------------
                    3.00    2.00    0.00    0.00    0.00    |   0.00
         ------------------------------------------------------------

Príklad 4 :

Formulujte stĺpcové pravidlo pre maximalizáciu a aplikujte ho na Tab 2.

Tab. 2      B       X1      X2      Slack1  Slack2  Slack3  |  b
         ===================================================|========
             X2     0.00    1.00    2.50   -1.50    0.00    |   7.50
             X1     1.00    0.00   -0.50    0.50    0.00    |   1.50
           Slack3   0.00    0.00   -4.50    2.50    1.00    |   3.50
         ------------------------------------------------------------
                    0.00    0.00   -3.50    1.50    0.00    | -19.50
         ------------------------------------------------------------

Príklad 5 :

Vyhodnoťte Tab. 3 z hľadiska ďalšieho kroku simplexovej metódy.

Príklad 6 :

Pokúste sa zrekonštruovať polopriamku (parametricky), ktorá bude celá ležať v množine prípustných riešní úlohy z Tab. 3.

Tab. 3      B       X1     X2   Surpl1 Slack2 Surpl3 Surpl4 | b
         ===================================================|========
             X2     0.00   1.00   0.00   0.91  -0.09   0.00 |  9.09
           Surpl4   0.00   0.00   0.00   1.73  -0.27   1.00 |  8.27
             X1     1.00   0.00   0.00  -0.09  -0.09   0.00 |  2.09
           Surpl1   0.00   0.00   1.00   1.91  -0.09   0.00 | 14.09
         ------------------------------------------------------------
                    0.00   0.00   0.00  -1.73   0.27   0.00 |-20.27
         ------------------------------------------------------------

Príklad 7 :

Pri minimalizácii funkcie g = Artif1 +Artif2, kde Artif1 označuje umelú premennú, ste získali Tab. 4, prevďte transformáciu pomocou ktorej prejdete k bázy bez umelých premenných a dopočítajte nový pomocný riadok pre pôvodné koeficienty účelovej funkcie (viď riadok C).

	    C:      2.00   3.00   4.00
Tab. 4      B       X1     X2   Surpl1 Artif1 Slack2 Surpl3 Artif2 Surpl4 | b
         =================================================================|=====
             X2     0.00   1.00   0.00   0.00   0.00   0.05  -0.05  -0.53 |4.74
           Slack2   0.00   0.00   0.00   0.00   1.00  -0.16   0.16   0.58 |4.79
             X1     1.00   0.00   0.00   0.00   0.00  -0.11   0.11   0.05 |2.53
           Artif1   0.00   0.00  -2.00   1.00   0.00  -0.21   0.21   1.11 |0.00
         -----------------------------------------------------------------------
                    0.00   0.00   0.00   0.00   0.00   0.00   0.00   0.00 |      
         -----------------------------------------------------------------------

Príklad 8 :

Preveďte krok simplexovej metódy s tabuľkou 5 a uršte o aký prípad množiny prípustných riešení sa jedná.

Príklad 9 :

Určte maticu D¹², tak aby platilo D¹²*Tab1=TAb2.

Príklad 10 :

Určte maticu D²¹,tak aby platilo D²¹*Tab2=TAb1.

Príklad 11 :

Do podmienok prvého modelu zaveďte premennú z= -3x1 - 2x2 a miesto minimalizácie f, minimalizujte g = z a pre nový model zostavte tabuľku simplexovej metódy, kde v riadku bázickej premennej z, pripustíme záporné hodnoty v stĺpci b.

Príklad 12 :

Upravte stĺpcové pravidlo tak, že z riadku premennej z nebudete hodnoty v pomocnom riadku a v riadku premennej z !

Príklad 13 :

Je tabuľka 6 lexikograficky kladná ?

Príklad 14 :

Aplikujte na tabuľku 14 výber pivota podľa metódy, ktorá zabráni zacykleniu.

Príklad 1 :

Určte interval, v ktorom sa môže meniť druhý z koeficientov účelovej funkcie, tj. c₂ = -3 v úlohe (4)-(6), aby riešenie x = <4, 2, 0, 0>zostalo optimálne.

Príklad 2 :

V tabuľke 63 je optimálna matica A_v pre úlohu s obmedzujúcimi podmienkami (5), (6) a s účelovou funkciou x₀= -2x₁ - 3x₂ určte postupne intervali pre c₁ = -2 a c₂= -3, v ktorých sa tieto koeficienty môžu meniť (vždy len jeden z nich zatiaľ čo druhý má pôvodnú hodnotu), aby riešenie x = <0, 6, 0, 4> zostalo optimálne.

Tab. 63    BASIS   X0     X1     X2     X3     X4    SOL.     
         ===================================================
             X0     1.00  -1.00   0.00  -3.00   0.00 -18.00 
         ---------------------------------------------------
             X2     0.00   1.00   1.00   1.00   0.00   6.00 
             X4     0.00   1.00   0.00  -2.00   1.00   4.00 
         ---------------------------------------------------

Príklad 3 :

Určte interval, v ktorom sa môže meniť koeficient b₂ = 16 úlohy (4)-(6), bez toho aby sa menila báza jej optimálneho riešenia.

Príklad 4 :

Určte intervali, v ktorých sa postupne môžu meniť koeficienty b₁ a b₂ úlohy s podmienkami (5) a (6) a s účelovou funkciou x₀= -2x₁ - 3x₂ s optimálnou maticou uvedenou v tauľke 63.

Príklad 5 :

Riešte pomocou citlivosti úlohu lineárneho parametrického programovaia zadanú modelom :

minimalizujte  x0= -4.3x1 - 3x2      (1)
za podmienok        x1 + x2  6     (2)
                   3x1 + 2x2 16    (3)
             xj0  pre j=1..4

Príklad 1 :

Nájdite pomocou metódy vetiev a hraníc optimálne bivalentné riešenie úlohy (1)-(2), použite schému prehľadávania do hĺbky a hranicu vypočítajte pomocou LP relaxácie.

Príklad 2 :

Nájdite pomocou metódy vetiev a hraníc optimálne bivalentné riešenie úlohy (1)-(2), použite usmernenú schému prehľadávania a hranicu vypočítajte pomocou LP relaxácie.

Príklad 3 :

Nájdite pomocou metódy vetiev a hraníc optimálne celočíselné riešenie úlohy (1)-(2), použite schému prehľadávania do hĺbky a hranicu vypočítajte pomocou LP

Príklad 4 :

Nájdite pomocou metódy vetiev a hraníc optimálne celočíselné riešenie úlohy (1)-(2), použite usmernenú schému prehľadávania a hranicu vypočítajte pomocou LP relaxácie.

Príklad 5 :

Predpokladajte, že tab.1 je matica najkratších vzdialeností v úplnom grafe (sieti) . Riešte pomocou metódy vetiev a hraníc v tejto sieti úlohu obchodného cestujúceho.
Tab 1.

0	4	5	6	7
5	0	7	6	8
6	6	0	7	7
4	4	5	0	5
3	3	3	4	0

Príklad 6 :

Napíšte konkrétny model vyššie uvedenej úlohy,

Príklad 7 :

Predpokladajte, že v tab1. zodpovodajú riadky jednotlivým opravám a stĺpce jednotlivým remeslám, ktoré sú k oprave potrebné. Jednotlivé koficienty tabuľky udávajú koľko remeselníkov daného remesla je potrebných k vykonaniu dane opravy. Riešte pomocou metódy vetiev a hraníc úlohu vybratia dvoch opráv s minimálnym celkovým počtom remeselníkov.

Príklad 1 :

Dokážte z definície konvexnosti resp. z definície ostrej kvázikonvexnosti (nájdite konkrétny protipríklad), že

1. funkcia cos(x) na intervale < 0, 2¶ > nie je konvexná
2. funkcia sin(x) na intervale < 0, 2¶ > nie je ostro kvázikonvexná

Príklad 2 :

Pomocou viet o deriváciách funkcií reálnej premennej

1. nájdite podintervaly intervalu < 0, 2¶ >, kde je funkcia cos(x) konvexná
2. nájdite podintervaly intervalu < 0, 2¶ >, kde je funkcia cos(x) ostro kvázikonvexná
3. dokážte, že na intervale < 0, 2¶ > je funkcia cos(x) ostro kvázikonvexná
4. nájdite podintervaly intervalu < 0, 2¶ >, kde je funkcia sin(x) konvexná
5. nájdite podintervaly intervalu < 0, 2¶ >, kde je funkcia sin(x) ostro kvázikonvexná
6. overte konvexnosť v okolí bodu 0 funkcií x⁴ a x³.

Príklad 3 :

Na funkciách a intervaloch nájdených v 2c) a 2e) nájdite minimá metódou zlatého rezu.

Príklad 4 :

Aplikujte metódu zlatého rezu (po určení vhodného intervalu) na nájdenie minima funkcie f(x)=(x+1/3)^1/2+(x+1/3)²+2(x+1/3) na intervale
x < 0,  >.

Príklad 5 :

Vyšetrite konvexnosť resp. ostrú konvexnosť nasledujúcich funkcií definovaných na E₃:

1. f(x)= x₁²+2x₂+x₃²
2. f(x)= x₁²+x₂+0x₃²
3. f(x)= x₁²+x₂+x₃² + 4x₂x₃

Príklad 6 :

Určte definitnosť kvadratických foriem daných maticami :

a)		b)		c)		d)
	1 0 0 0 1 1 0 1 1		1 1 0 1 0 0 0 0 1		1 0 0 1 1 0 1 1 1		1 2 0 2 1 0 0 0 0

Príklad 7 :

Určte vlastnosti (konvexnosť, resp. ostrú konvexnosť, konkávnosť, resp. ostrú konkávnosť ) v okolí bodu ^T funkcií :

1. f(x)= x₁⁴ + x₂²
2. f(x)= x₁sin(x₂)
3. f(x)= exp(x₁ + x₂)

Príklad 8 :

Riešte úlohu min { 2x₁² + x₂² : x E₂} z počatočného bodu x = <3, 3>^T s prestnosťou = 0.1

1. gradientovou metódou s konštantým krokom dĺžky 0,5
2. gradientovou metódou najväčšieho poklesu
3. Fletcher-Reevesovou metódou združených smerov
4. Powellovou metódou

Príklad 9 :

Riešte úlohu min { (2x₁² + x₂²)² : x E₂} z počatočného bodu x = <2, 2>^T s prestnosťou = 0.1

1. Newtonovou metódou
2. Davidon-Fletcher-Powellovou metódou 2. rádu

Príklad 10 :

Riešte úlohu min { x₁² + x₂² : x E₂, (x₁-2)² + (x₂ - 3 )² <= 1} Z POČIATOČNÉHO BODU X = <2, 3>^T metódou pokutových funkcií.

Príklad 11 :

Konštruujte postupnosť pokutových funkcií pre množiny U z E₂

1. U = {x E₂ : x₁ <-1,3> }
2. U = {x E₂ : x₁ - x₂ <=1, X₁ - x₂ >= -1}
3. U = {x E₂ : x₁² + x₂² <=1, (X₁ - 1)² + x₂² <= 1}
4. U = {x E₂ : x₁ >= 0, x₂>= 0, x₁ + x₂ <= 2}
5. U = {x E₂ : x patrí do konvexného obalu <1, 1>, <2, 1>, <1, 2>}
6. U = {x E₂ : x₁ <-1, 1>, x₂ <0, 2>}

Príklad 12 :

Zostavte model nasledujúcej úlohy a vyriešte ho niektorou z iteračných metód :
Na obrazovku počítača chceme nakresliť závislosti
y(x) = 2[ (x²+ |x| - 6) / (x²+ |x| +2) + (36 -x²)^1/2] / 3
z(x) = 2[ ((x²+ |x| - 6) / (x²+ |x| +2) - (36 -x²)^1/2] / 3
pre x <-4, 3>tak, aby obrázok bol čo najväčší a pritom aby na obrazovke boli obe krivky celé. Určte optimálny zobrazovací rozsah na zvislej osi.

Príklad 13 :

Zostavte model nasledujúcej úlohy a vyriešte ho niektorou z iteračných metód :
V priestore vymedzenom kruhom o polomere 30 km a so strdom danom súradnicami <70, 80> v km máme umiestniť zásobovacie stredisko vybavené vrtuľníkom a nosnoťou 1 t. Z tohto srediska je potrebné zásobovať tri pracoviská s požiadavkami 3, 8 a 12 t za plánovacie obdobie. Pracoviská majú súradnice <10, 20>, <150, 30> a <20, 160> . Stredisko má byť umiestnené tak, aby spotreba pohonných hmôt pre vrtuľník bola minimálna.

A 601 Matematické programovanie

1. Formulácia duálnych úloh, význam dálnych premenných.(str. 72-74)
2. Slabá a silná veta o dualite, veta o komplementárnosti doplnkových premenných (str. 77-80).
3. Duálna lexikografická metóda (str. 85-89).
4. Špeciálne metódy riešenia dopravnej a priraďovacej úlohy, algoritmus MODI (str. 90-105), metódy získavania východzieho riešenia.
5. Maďarská meóda (str. 106-116).
6. Úlohy diskrétneho programovania, princíp metódy rezov, Gomoryho algoritmus I. (cvičenie str. 134-135).
7. Crowdler-Padbergova metóda, princíp redukcie (str. 155-157).
8. Lagrangeova relaxácia a jej aplikácie v metóde vetiev a hraníc (str. 163).
9. Úloha kvadratického programovania a Kuhn-Tuckerove podmienky (str. 169 a 175) .
10. Wolfeova metóda riešenia úlohy kvadratického programovania (str. 178, 184 cvičenie 187).
11. Formulácia úloh dynamického programovania, Bellmanova funkcia a rovnica, stav systému a zákon optimálneho riadenia (str. 193 cvičení na str. 205-207)
12. Aplikácia dynamického programovania na riešenia úlohy riadenia skladu a úlohy optimalizácie rozraďovania vlakov (str. 208-213, cvičenie str. 213-216).

1. - 2.
   Sem. cv.: Zostavovanie modelov zo slovných úloh (úlohy celočíselného programovania) a opakovanie prvkov tabulky simplexovej metódy, zostavenie tabuľky duálnej lexikografickej metódy.
   Výp. cv.: Práca so systémom MOR a XPRESS zameraná na získavanie hodnôt duálnych premenných z tabuľky simplexovej metódy.
3. - 4.
   Sem. cv.: Formulácia modelov duálnych úloh k základným úlohám lineárneho programovania. Duálna lexikografická metóda
   Výp. cv.: Riešenie duálnych úloh a riešenie úloh celočíselného programovania metódou rezov pomocou systému MOR.
5. - 6.
   Sem. cv.: Riešenie dopravnej úlohy metódov MODI a riešenie priraďovacej úlohy maďarskou metódou. Zadanie lokačnej úlohy pre seminárnu prácu.
   Výp. cv.: Riešenie úloh celočíselného programovania metódou rezov v systéme MOR.
7. - 8.
   Sem. cv.: TEST! (30 minút). Precvičenie metódy rezov a metódy vetiev a hraníc.
   Výp. cv.: Riešenie lokačnej úlohy pomocou programového vybavenia.
9. - 10.
   Sem. cv.: TEST! (30 minút).Formulácia modelov úloh kvadratického programovania a Kuhn-Tuckerových podmienok.
   Výp. cv.: Formulácia modelov úloh dynamického programovania pomocou rekurzívnych funkcií systému MOR.
11. - 12.
    Sem. cv.: Formulácia úloh dynamického programovania (riadenia skladu, úloha o batohu).
    Výp. cv.: TEST! (30 minút). Riešenie úloh dynamického programovania pomocou rekurzívnych funkcí systému MOR.

• Janáček, J.: Matematické programování. EDIS, ŽU-Žilina, 1999, 225 s.
• Plesník J., Dupačová J., Vlach M.: Lineárne programovanie, Alfa, Bratislava, 1990, 320 s.
• Janáček, J.: Řešení úloh matematického programování na osobních počítačích, VŠDS, Žilina, 1993, 128 s.

Téma 1 :

Formulácia mat. modelu úl. celočíselného prog. a jeho riešenie pomocou systému XPRESS a vyšetrovanie vlastností modelu.

Téma 2 :

Formulácia úl. dynamického programovania a jeho riešenie pomocou systému MOR.

Téma 3 :

Zostavenie programu pre riešenie lokačnej úlohy metódou vetiev a hraníc.

1. Vediť klasifikovať rôzne typy úloh a modelov celočíselného,zmiešaného kvadratického, separovaného a dynamického programovania. Vedieť formulovať mat. model úlohy lokačnej, obchodného cestujúceho, okružných jázd, rozmiestňovania spojov, radenie vlakov.
2. Vedieť vety o dualite a vedieť formulovať duálne úlohy.
3. Poznať metódu rezov a príslušné algoritmy (Gomory 1 a 3) vrátane podminok konečnosti.
4. Poznať metódu MODI a maďarskú metódu
5. Poznať Lagrangeovu relaxáciu a jej použitie v metóde vetiev a hraníc. Poznať princíp redukcie.
6. Vediť formulovať Kuhn-Tuckerove podmienky pre úlohu kvadratického programovania a vedieť ich pomocou lineárneho programovania riešiť (Wolfeova metóda). Vedieť oferiť podmienky Wolfeovej vety.
7. Poznať základné pojmy dynamického programovania ako Bellmanov princíp optimality, Bellmanovu rovnicu, Bellmanovu funkciu, stav systému, prechodovú rovnicu.
8. Vedieť formulovať a riešiť úlohy dynamického prograamovania.
9. Vedieť formulovať a riešiť úlohy dynamisňckého programovania pomocou programových prostriedkov systému MOR.
10. Vedieť riešiť úlohu separovaného matematického programovania.

 0 - 12 bodov          nevyhovel
13 - 16 bodov          dobre
17 - 20 bodov          veľmi dobre
21 a viac             výborne

Príklad 1 :

Zostavujeme čo najlacnejší jedálny lístok (zmiešavacia úloha), ktoý by obsahoval aspoň 1kg uhľohydrátov a 0,3kg bielkovín. Ceny potravín, obsah uhľohydrátov a bielkovýn v kilogramovom množstve sú v tabuľke. Zostavte model, zostavte model duálnej úlohy a pokúste sa nájsť interpretáciu duálnych premenných a ekonom. interpretáciu duálneho modelu.

Sk/kg	20	40	70	50	30
kg/kg	0.2	0.3	0.2	0.4	0.1
kg/kg	0.5	0.6	0.4	0.2	0.3

---

Príklad 2 :

Toto je model úlohy lokačnej úlohy, nahraďte podmienku
y _i, x_ij { 0, 1}podmienkami nezápornosti a tam, kde je potrebné y_i<=1 A ZOSTAVTE DUÁLNU ÚLOHU. ( ČO INTERPRETÁCIA DUÁLNYCH PREMENNÝCH ?)

Príklad 3 :

min 2x₁ + x₂ + 3x₃
zp :  x₁ + x₂ + x₃ = 4
       x₁ + x₂ + 3x₃ <= 6
       x₁ - x₂ - x₃ >= 1
        x_j>=0

Nájdite k tejto úlohe úlohu duálnu, knej opäť duálnu a pporovnajte výsledok s pôvodným modelom.
Sú ekvivalentné ?

---

Príklad 4 :

Úloha

          max    2x1 + 3x2
          zp     5x1 + 2x2 <= 10 
                  X1       <=1         
                        X2 <= 3
                    Xj>= 0

má optimálne riešenie <4/5 ; 3> f (x)= 53/5

1. Nájdite optimálnu tab. primárnej metódy bez toho, aby ste robili simplexovu metódu.
2. Nájdite z opt. tabuľky primárnej metódy duálne optimálne riešenie.
3. Určte aký najväčší úplatok sa vám oplatí dať za jednotku suriviny v prvej podmienke, aby sa vám zvýšená výroba ešte oplatila.
4. Koľko suroviny sa vám oplatí takto zaobstarať ?

---

Príklad 5 :

Riešte úlohu 4 duálnou lexikografickou metódou a zakreslite si získané bázické riešenia do roviny x₁, x₂.

---

Príklad 6 :

Pridajte k úlohe 4 požiadavku celočíselnosti (úl. plánovania výroby s nedeliteľnosťou) a riešte 1. GA. Rezy si nakreslite do obrázku.

---

Príklad 7 :

Riešte úlohu 4 s požiadavkami na celočíselnosť 3. GA a opäť si znázornite rezy aj zistené bázické riešenia v rovine x₁, x₂.

---

Príklad 8 :

Riešte priraďovaciu úlohu pre minimalizáciu metódou MODI (Dautzigova metóda)

	1	1	1
1	3	4	5
1	3	3	7
1	1	3	9

1. Každú získanú bázu znázornite v bipartitnom grafe a vyznačte pomocou ohodnotenia vrcholov príslušné duálne neprípustné riešenie (u_i, v_j)
2. Vyznačte hrany bázy s hodnotou 1 (mali by tvoriť úplné párovanie)
3. Vyznačte do toho istého grafu hrany, ktoré nespĺňajú podm. duálnej prípustnosti, tj. u_i + v_j >= c_ij
4. Premyslite si interpretáciu duálnych premenných v priraďovacej úlohe s minimalizáciou a maximalizáciou.
5. Riešte priraďovaciu úlohu pomocou maďarskej metódy.
6. Zobraste si na každom kroku graf hrán vyhovujúcich podmienkam duálnej prípustnosti (u_i + v_j >= c_ij)
7. Čo platí o podgrafe zloženom z hrán, pre ktoré u_i + v_j = c_ij ?
8. Aký graf (resp. párovací podgraf ) bude odpovedať primárnemu prístupnému riešeniu ?

---

Príklad 9 :

Riešte algoritmom MODI dopravnú úlohu o 3 zdrojoch a 4 odberateľoch s tým, že prvé riešenie získate pomocou metódy severozápadného rohu.

kap\pož	20	20	30	25
40	8	7	9	6
35	5	8	8	5
20	8	9	7	7

---

Príklad 10 :

Riešte príklad 9 s použitím frekvenčnej metódy pre získanie prvého riešnie.

---

Príklad 11 :

Riešte príklad 9 s použitím metódy indexovej (minimálneho prvku).
Pozn. V 10. a 11. príklade je potrebné upraviť kapacity a požiadavky pomocou E-metódy.

---

Príklad 12 :

Riešte metódou MODI priraďovaciu úlohu s maticou

6	4	5
3	3	4
4	5	6

a pre každé bázické prípustné riešenie zostavte graf (bipartitný) odpovedajúci báze a prípadne ho doplňte o hrany splňujúce u_i + v_j = c_ij .

---

Príklad 13 :

V bipartitných grafoch s hranami splňujúcimi podmienku u_i + v_j = c_ij z úlohy 12 doplňte o :

1. hrany splňujúce podmienku optimality u_i + v_j <= C_ij
2. hrany, ktorých zavedením kesne hodnota úč. fcie u_i + v_j >c_ij

---

Príklad 14 :

Riešte úlohu 12 pomocou maďarskej metódy a v jednotlivých krokoch zostavujte grafy požadované v príkladoch 12 a 13.

---

Príklad 15 :

Riešte úlohu maximálneho párovania v bipartitnom grafe

   a v grafe  .

---

A701 Optimalizácia na dopr. sieťach

1. Forulácie modelov úloh v distribučných systémoch, spracovanie údajov o dopravnej sieti.
2. Zostavenie siete distribučného systému so zadaním úloh :
   
   • lokačnej
   • odberných dní
   • trasovacej
3. Zostavenie počítačového modelu siete distribučného systému.
4. Riešenie diskrétnej lokačnej úlohy pomocou programových prostriedkov.
5. Precvičenie Ross-Solandovej metódy.
6. Programovanie heuristík na riešenie úloh obchodného cestujúceho.
7. Test ! (20 min.) Testovanie heuristík na modeli dopravnej siete.
8. Spracovanie modelu úlohy optimalizácie odberných dní.
9. Transformácia úl. čínskeho poštára na dopravnú úlohau a najlacnejšieho párenia. Riešenie úlohy čínskeho poštára (pomocou vlastného programu pre riešenie Eulerovho ťahu)
10. Vytvorenie rozvozných sietí pre jednotlivé dni a zostavenie programu alg. "sweep". Riešenie úloh trasovania pomocou programového vybavenia.
11. Test ! (30 min.) Využitie algoritmu heuristiky pre riešenie úlohy obchodného cestujúceho v algoritme "sweep" pre riešenie úloh trasovania.
12. Výpočet obehov vozidiel.

1. téma: Riešenie lokačnej úlohy diskrétnej
2. téma: Návrh trás vozidiel (pomocou pmg OVOJ)
3. téma: Riešenie lokačnej úlohy spojitej
4. téma: Návrh liniek (model a riešenie) pomocou lin. pgm

1. Vedieť zostaviť matematický model úloh riešených v rámci predmetu.
2. Poznať rozdelenie prepravných a rozvozných úloh.
3. Vedieť riešit zobecnenú priraďovaciu úlohu Ross-Solandovým algoritmom a lokačnú úlohu Erlenkotterovým algoritmom.
4. Poznať princípy heuristických algoritmov, riešenie úlohy obchodného cestujúceho.
5. Poznať princípy heuristických riešení prostých úloh trasovania.
6. Vedieť riešiť úlohy čínskeho poštára (s tým, že úlohu najcennejšieho párovania riešite ako úlohu CLP)
7. Vedieť formulovať úlohy optimalizácie odberných dní.
8. Vedieť formulovať a riešiť úlohy obehu vozidiel a vedieť príslušnú klasifikáciu úloh.

 0-12 bodov      nevyhovel
 13-16 bodov     dobre
 17-20 bodov     veľmi dobre
 21 a viac       výborne

• Černý, J., Kluvánek, P.: Základy matematickej teórie dopravy. Veda, Bratislava, 1991
• Cenek, P., Klima, V., Janáček, J.: Optimalizace dopravních a spojových systémú. VŠDS, Žilina, 1994
• Janáček, J: Optimalizace na dopravních sítích. EDIS, Žilina, v tlači.
• Janáček, J.: Matematické programování. EDIS, Žilina, 1999.

Príklad 1 :

Zostavte konkrétny model rozmiestňovacej úlohy z obrázku, kde umiestnenie strediska stojí a) 10, b) 50, c) 100 jednotiek, a kde jednotkové náklady na prepravu jednej jednotky požiadavky medzi uzlami sú vyznačené pri jednotlivých úsekoch grafu dopravnej siete, v ktorom čierne krúžky zodpovedajú odberateľom, čísla v nich ich požiadavkam , a kde bielymi krúžkami sú vyznačené možné umiestnenia stredísk.

Príklad 2 :

Vyriešte úlohu a), b), c) zo zadania 1. pomocou MOR a tiež XPRESS, pričom vyskúšajte obe možnosti, ako zabezpečiť to, že keď odberateľ j je priradený miestu i, tak stredisko musí byť vybudované.

Príklad 3 :

Zistite pre aké hodnoty fixných nákladov bude optimálne riešenie úlohy z 1. príkladu obsahovať 1, 2 a 3 strediská.

Príklad 4 :

Zostavte konkrétny model úlohy rajonizácie pre dopravnú sieť z nasledujúceho obrázku, kde čierne krúžky vyznačujú spotrebiteľa a číslo vnútri, jeho požiadavku. Pri úsekoch siete sú uvedené nákladdy na prepravu jednej jednotky tovaru po úseku , a kde biele krúžky zodpovedajú zdrojom s vyznačenou kapacitou.

Príklad 5 :

Zostavte model úlohy okružných jázd pre úlohu na nasledujúcom obrázku, kde nie je požadovaná podmienka časovej dostupnosti odberateľov, ale je požadované, aby doba jazdy žiadnej jazdy netrvala dlhšie než 1000 minút. Doby presunov po úsekoch sú vyznačené v obrázku. Naviac zloženie jednoj jednotky nákladu si vyžiada 1 minútu a náklady na jednu minútu jazdy sú 1 Sk. Náklady na manipuláciu s materiálom zanedbajte. Stredisko je umistnené b uzle vyznačenom prázdnym krúžkom, odberatelia čiernym krúžkom a ich požiadavky číslom v nich. Číslovanie uzlov je vedľa krúžku. Kapacita vozidiel je 100 jedniek.

Príklad 6 :

Napíšte pascalovskú procedúru, ktorej vstupom je matica vzdialeností c_ij uzlov v sieti s n - 1 zákazníkov a so strediskom umiestneným v uzle 1. Výstupom procedúry je pole, v ktorom sú uložené indexy uzlov v poradí v akom majú byť navštevované, začínajúc uzlom 1. Táto postupnosť má byť získaná metódou najbližšieho suseda.

Príklad 7 :

Riešte úlohu 5 metódou využívajúcou matematického programovania, kde východziu neprípustnú trasu určíte metódou najbližšieho suseda a tú rozdelíte na okružné jazdy modelu matematického programovania (napíšte konkrétny model)

Príklad 8 :

Riešte ručne úlohu 5 metódou sweep, ak majú jednotlivé uzly 1,..,6 nasledujúce súradnice x, y.

uzol	1	2	3	4	5	6
x	0	0	20	30	50	50
y	0	20	40	10	20	50

Príklad 9 :

Zostavte pascalovskú procedúru, kde vstupom sú polia x a y obsahujúce súradnice uzlov, n počet uzlov, kde uzol 1 je stredisko, pole požiadaviek b a kapacitu K vozidla. Výstupom je počet zhlukov m a pole u, kde u[i] je číslo zhluku, do ktorého bol zaradený odberateľ i. Procedúra má zodpovedaľ metóde sweep.

Príklad 10 :

Zostavte iteračný algoritmus (naprogramujte v pascale) pre umiestnenie jedného strediska v ploche, pre obsluhu zákazníkov 2,..6 z úlohy 5, kde náklady na prepravu jednej jednotky požiadavku na jednotkovú vzdialenosť sú rovné jednej.

Príklad 11 :

Zostavte konkrétny model (stačí aj nelineárny) úlohy rozmiestňovania zadaný v 1, ale s neaditívnym kritériom, kde uvažujete, že dopravné náklady budú priamo úmerné s konštantou c súčtu ohodnotení jednotlivých zhlukov(množiny uzlov obsluhovaných z jedného strediska).Zhluk je pritom ohodnotený súčtom ohodnotení všetkých úsekov, ktorých oba konce sú v ohodnocovanom zhluku.

Príklad 12 :

Zostavte obecný model úlohy rajonizácie s neaditívnou odhadovou funkciou popísanou v 11.

Príklad 13 :

Zostavt konkrétny model rozmiestňovacej úlohy z 1, kde ale náklady na uspokojenie odberateľov budú dané súčtom dĺžok trás vozidiel, ktoré ich obsluhujú. Pre zjednodušenie uvažujte, že v jednom stredisku môžu byť umiestnené najviac tri vozidlá s kapacitou 15.

Príklad 14 :

Zostavte obecný model úlohy rajonizácie, kde účelovou funkciou bude súčet dĺžok trás vozidiel obsluhujúcich zákazníkov. V každom zdroji i uvažujte najviac P_i vozidiel s kapacitou K.

Príklad 15 :

Definujme reťazec ako postupnosť zákazníkov (obsluhovaných uzlov siete), ktorí v danom poradí po sebe nasledujú v danej okružnej jazde. Reťazec bude úplne určený indexom predchodcu p (posledný uzol vrátane strediska, predchádzajúci reťazcu) a nasledovníka n (prvý uzol jazdy za reťazcom). Pokiaľ je reťazec neprázdny, rozlišujeme ešte počiatočný krajný uzol reťazca v a koncový uzol reťazca k.
Nech d_ij je ohodnotenie úseku (i,j) v dopravnej sieti.

1. Vyčíslite úsporu (resp. stratu), ktorá vznikne pokiaľ na reťazec v zadanej jazde preveďte operáciu inverzie (uzly reťazca neprejdite v pôvodnom smere od v do k, ale opačne).
2. Vyčíslite úsporu (resp. stratu), ktorá vznikne pokiaľ reťazec 1, v₁, k₁, n₁ > jednej jazdy vymeníte za prázdny reťazec 2, n₂ > inej jazdy.
3. Vyčíslite úsporu (resp. stratu), ktorá vznikne pokiaľ reťazec 1, v₁, k₁, n₁ > jednej jazdy vymeníte za reťazec 2,v₂, k₂, n₂ > inej jazdy.

Príklad 16 :

Dĺžkou reťazca budeme rozumieť počet uzlov reťazca vrátane v a k. Prázdny reťazec má teda dĺžku 0.

1. Určte na akých reťazcoch, resp. dvojiciach reťazcov v prípadoch a), b), c) zadania 15 možno alebo má zmysel robiť vyššie uvedené operácie inverzie a výmeny reťazcov.
2. Určte podmienky, za ktorých je možné robiť operácie výmeny reťazcov, ak sa jedná o reťazce z rovnakej jazdy.

Príklad 17 :

Je zadaná nasledujúca zobecnená priraďovacia úloha :

rij	1	2	3	4	5	6	7	8		ai		cij	1	2	3	4	5	6	7	8
1	6	8	8	7	6	6	5	7		30		1	2	3	2	4	3	5	6	7
2	5	6	6	6	7	3	6	6		20		2	4	6	5	4	4	4	7	8
3	7	7	8	9	6	9	6	6		30		3	8	8	8	6	6	5	5	5
4	8	8	9	9	8	8	7	5		30		4	8	9	7	7	7	6	9	9

riešte ju Ross-Solandovou metódou tak, že úlohu pre každé vetvenie (pre výpočet dolnej hranice ) zostavíte ručne, ale potrebnú "obrátenú úlohu o batohu " vyriešite pomocou systému MOR.