VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ FAKULTA ELEKTROTECHNIKY A KOMUNIKAČNÍCH TECHNOLOGIÍ ÚAMT
PROJEKT
SEMESTRÁLNÍ PROJEKT Z PŘEDMĚTU SYSTÉMOVÁ ANALÝZA
Strategie obrany Spojené federace planet proti armádě Romulanské říše
Tomáš Kreuzwieser
[email protected]
1. Úvod Mé zadání má číslo 14. Zde jsou uvedeny konstanty mého zadání. CenaFer CenaUpr Penez CasSroc UcFer UcUpr VzdA VzdB
1360 34 5000 50 20 30 110 260
u1 u2 u2 u4 u5 u6 u7 u8 u9
210 90 150 70 80 50 200 160 40
u10 u11 u12 u13 u14 u15 u16 u17 u18
150 160 160 150 40 130 150 30 180
u19 u20 u21 u22 u23 u24 u25 u26 u27
110 130 40 120 160 30 200 200 90
Tabulka 1 Podrobněji viz. zadání na emailu
[email protected].
2. Optimalizace 2.1
Nalezení nejkratší cesty od planety Romulus k Zemi
Plán útoku Romulanské říše proti Zemi
Obrázek 2 Z grafu je patrné, že nejkratší cesta z planety Romulus na Zem vede po červeně vyznačené trase a celkově trvá 400 dnů. Řešení je možné provést graficky pomocí postupného zanášení nejkratších tras mezi planetami při postupu směrem od Země, nebo pomocí programu Matlab s použitím funkcí “celo” nebo „linprog“. První jmenovaná je pro celočíselné řešení, druhá pro reálné. V tomto případě můžeme použít libovolnou z nich se stejným výsledkem. V tomto textu se zaměřím pouze na řešení v programu Matlab, protože je univerzálnější.
2.1.1 Řešení první časti v programu Matlab Omezují podmínky mezi jednotlivými planetami: x(1)<=u(1);
x(2)<=u(2); x(3)<=u(3); x(7)<=u(4); x(4)<=u(5); -x(1)+x(5)<=u(6); -x(1)+x(6)<=u(7); -x(2)+x(5)<=u(8); -x(2)+x(6)<=u(9); -x(2)+x(7)<=u(10); -x(3)+x(6)<=u(11); -x(4)+x(6)<=u(12); -x(3)+x(7)<=u(13); -x(4)+x(7)<=u(17); -x(5)+x(8)<=u(15); -x(6)+x(8)<=u(16); -x(6)+x(9)<=u(17); -x(7)+x(9)<=u(18); -x(8)+x(10)<=u(19); -x(8)+x(11)<=u(20); -x(9)+x(11)<=u(21); -x(8)+x(12)<=u(22); -x(9)+x(12)<=u(23); -x(10)+x(13)<=u(24); -x(11)+x(13)<=u(25); -x(12)+x(13)<=u(26); -x(6)+x(10)<=u(27); a navíc musí být splněno, že x(i)>=0 pro i=1:13 Legenda:
x(i) jsou jednotlivé uzly, čili planety (jsou červeně vyznačeny na Obr.1) u(i) jsou vzdálenosti mezi nimi (Obr. 1)
Kriteriální funkce pro je f=x(13). Po provedení výpočtu pomocí funkce linprog jsem si ověřil, že optimální cesta skutečně vede přes planety 2,6,9 a 11 a trvá 400 dnů. 2.2
Nalezení nejlepší strategie nákupu a oprav lodí Je třeba rozhodnout, kolik se nakoupí lodí od Ferengů a kolik lodí se upraví (jedna upravená loď má účinnost dvou neupravených). Opět je nejlepší řešit problém jak úvahou, tak univerzálně pomocí programu Matlab. Z úvahy plyne, že nejlepší optimalizací na čas je takový případ, kdy co nejvíce lodí koupíme od Ferengů a během cesty, která trvá 100 dní se pokusíme upravit co nejvíce našich lodí. Čili v ideálním případě nakoupíme 21 lodí a 9 lodí mezitím upravíme. Bohužel ale nemáme tolik peněz. Proto musíme nakoupit pouze tolik lodí, na kolik nám vyjdou peníze a zároveň musíme dbát na to, aby nám zůstal dostatek peněz na
úpravy dalších lodí. V mém případě je nejlepší 27 lodí upravit a 3 nakoupit. To mi zabere nejmenší možný čas (280 dnů) a utratím většinu peněz (4998 z 5000).
2.1.2 Řešení druhé časti v programu Matlab Optimalizační rovnice: x(1)+x(2)<=30 -x(1)-x(2)<=-30, z toho plyne x(1)+x(2)=30 CenaFer+CenaUpr<=Penez Kriteriální funkce je f=x(1) Legenda:
x(1) je počet upravených lodí x(2) je počet nakoupených lodí x(i) nemá nic společného s x(i) z předešlého bodu
Výsledky jsou samozřejmě totožné s logickou úvahou. 2.3
Nalezení nejlepší strategie přípravy na boj Cílem třetího úkolu je zjistit, jak dlouho mi bude trvat, než dám dohromady potřebný počet lodí a kde (nebo zda) má cenu se vůbec bránit. Je třeba nakreslit orientovaný graf a v něm najít nejdelší možnou cestu. (pokud dva procesy běží paralelně, tak beru ten co trvá déle) Časová posloupnost akcí a doby trvání jednotlivých akcí: 1] Sroceni flotily - proces začíná ihned (CasSroc dnů) 2] Příprava úpravny lodí – ihned (10 dnů) 3] Úprava zatím přilétlých lodí - po 2] (10 dnů) 4] Úprava zbytku - po 2] a 1] (10 dnů) 5] Let na nákupy k ferengum – ihned (50 dnů) 6] Let zpět - po 5] (50 dnů) 7] Domlouváni obchodu – ihned (trvá 10 dní a dá se stihnout během letu k Ferengům) 8] Zaučení na ferengijské lodi - po 4] a po 6] (UcFer dnů) 9] Zaučení na upravené lodi - po 4] a po 6] (UcUpr dnů) 10] Cesta k planetě - po 4] a po 6] 11] Koncový stav, přílet na planetu - po 8] po 9] a po 10]
Obrázek 2 Graf jsem nakreslil po několika konzultacích s kolegy takto, protože si myslím že nejlépe vystihuje danou situaci. Přesto bych si netroufl tvrdit, že je absolutně správně, jelikož úloha nebyla zadána zcela jasně a dovoluje několik možných výkladů zadání. 0: start 1: lodě sroceny 2: dokončena příprava úpravny lodí 3: doletěly jsme na planetu Ferengů 4: vyjednání obchodu 5: trojuzel, dokončena úprava lodí, máme nakoupené lodě a zbytek neupravovaných lodí je srocen 6: posádka upravených lodí umí ovládat svá plavidla 7: posádka nakoupených lodí umí ovládat svá plavidla (tato větev zde bude jen v případě, že jsme nějaké lodě nakoupili, jinak nemá cenu čekat na to než se posádka naučí na lodě, které stejně nemáme) 8: flotila lodí je bojeschopná a připravená na určeném místě na boj
2.1.3 Řešení druhé časti v programu Matlab Rovnice popisující časy mezi jednotlivými uzly (planety). PocLodiKtereUpravujeme=x(1) z předchozího bodu
x(1)<=CasSroc; x(2)<=10; x(3)<=50; x(3)-x(4)<=10; x(4)<=0; -x(1)+x(5)<=0; -x(2)+x(5)<= PocLodiKtereUpravujeme*10; -x(3)+x(5)<=50; -x(5)+x(6)<=UcUpr; -x(5)+x(7)<=UcFer; -x(6)+x(8)<=0; -x(7)+x(8)<=0; Kriteriální funkce f=x(8) Legenda:
x(i) je vzdálenost mezi planetami x(i) nemá nic společného s x(i) z předešlých bodů
Z toho plyne, že příprava na boj mi zabere 310 dnů. Vzhledem k tomu, že Romulané na Zem poletí 400 dnů, tak mam rezervu 90 dní nato, abych vyrazil bránit další planety federace. To nám nevystačí na cestu k obraně žádné z planet v dráze letu Romulanů.
3
Závěr Z předešlých výsledků je patrné, že Spojená federace planet měla Romulus zničit dříve než by dosáhli stupně technického pokroku na kterém jsou dnes, v roce 2403. Takhle se bohužel budeme muset bránit v blízkosti planety Země a přijdeme o dvě z méně významných planet federace a o část Tachyonového deštníku Země. Do budoucna bych doporučil včasnější odhalení nepřátelských úmyslů zlepšením systému špionáže a nebo postupné obsazení planet s nerostným bohatstvím. To by Spojené federaci planet pomohlo financovat nákup a vývoj lodí a případné zaplacení ochrany od mocnějších civilizací, podobně jako mnohdy v minulosti při válkách na Zemi. Například v roce 1990.
