4. seminář: Úlohy celočíselného programování, formulace problému, metoda větví a mezí, heuristiky pro okružní dopravní problém Příklad 1: Sestavte matematický model úlohy celočíselného programování a pomocí Řešitele nalezněte optimální řešení (nezapomeňte v Omezujících podmínkách přidat podmínky celočíselnosti): a) Úloha o bramborách Potravinářská firma se zabývá zpracováním brambor. Jejími produkty jsou bramborové lupínky, které prodává po 120 Kč/kg, a hranolky po 76 Kč/kg. Na výrobu 1 kg lupínků se spotřebuje 2 kg brambor a 0,4 1 oleje a na výrobu 1 kg hranolků 1,5 kg brambor a 0,2 1 oleje. Navrhněte výrobní program tak, aby byl při nákupních cenách surovin 12 Kč/kg brambor a 40 Kč/l oleje maximální ZISK (zanedbáme náklady na práci, energii, apod.) a přitom nebyla překročena kapacita dodavatele (100 kg brambor a 16 1 oleje). Jak se změní optimální řešení, je-li odběratel ochoten odebírat zboží pouze v baleních (lupínky á 3kg a hranolky á 15kg)? b) Úloha o řezném plánu Firma vyrábějící kovové součástky nakupuje v libovolném množství trubky o délce 65 cm. K výrobě součástek potřebuje alespoň 1200 ks trubek o délce 20 cm a alespoň 900 ks trubek o délce 15 cm. Jakým způsobem má firma rozřezat nakoupené trubky tak, aby spotřeba nakoupeného materiálu byla minimální? c) Úloha o dopravě Dopravní společnost v městě S zásobuje paletovaným zbožím 4 stejně vzdálená sousední města A, B, C a D. Dnes má rozvézt 110 palet do města A, 70 do B, 58 do C a 62 do D. Má dva typy nákladních aut s fixními cenami jízdy: 6 malých aut s kapacitou 33 palet a cenou jízdy 120 Kč a 4 velká auta s kapacitou 60 palet a cenou jízdy 190 Kč. Každé auto stihne za den jen jednu cestu. Která auta mají kam jet, aby cena dopravy byla minimální? d) Úloha o pracovním rozvrhu služeb Správa sbírkového fondu a provozní potřeba galerie vyžadují, aby v jednotlivých dnech byly v galerii ve službě tyto počty osob: PO UT ST CT PA SO NE 22 17 13 14 15 18 24 Pracující nastupují do zaměstnání tak, že odpracují vždy 5 po sobě jdoucích dní, po kterých následují dva dny volna. Nástupy se mohou uskutečnit kterýkoliv den v týdnu. Úkolem je stanovit co nej menší počet zaměstnanců a rozvrhnout jejich nástupy do 5-denních pracovních cyklů tak, aby byly každý den v týdnu pokryty provozní potřeby. e) Úloha o zakázkách Podnik může převzít 6 různých zakázek, které se liší spotřebou času výrobního zařízení. Je znám zisk z jednotlivých zakázek a materiálová spotřeba. Zásoba materiálu a času je omezená. Parametry zakázek jsou shrnuty v tabulce: č. zakázky 1 2 3 4 5 6 disponibilní kapacita zisk 11 63 9 5 4 8 —> max. spotřeba času směny] 1 7 1 1 1 5 15 směn spotřeba materiálu [kg] 15 70 10 5 3 2 lOOkg Navrhněte, které zakázky má podnik realizovat, aby byl jeho zisk maximální. Příklad 2: Dealer, sídlící ve městě A, má za úkol během dne nabízet zboží ve městech B, C, D, E, jejichž vzájemné vzdálenosti jsou uvedeny v tabulce. A B C D E A X 50 70 40 60 B 50 X 40 30 80 C 70 40 X 40 60 D 40 30 40 X 50 E 60 80 60 50 X V jakém pořadí má tato města navštívit, aby ujel co nejméně kilometrů? Navrhněte trasu metodou nej bližšího souseda (začátek volte postupně ve všech městech). Porovnejte nalezené řešení s řešením získaným metodou výhodnostních čísel. Příklad 3: Aplikujte ručně metodu větví a mezí na následující modifikaci úlohy o batohu (použijte bivalentní proměnné a relaxace dílčích podúloh řešte bez pomoci simplexové metody): Máme k dispozici sklad o celkové skladovací ploše 8400m2. O pronájem skladu má zájem 5 zájemců s různými požadavky na skladovou plochu a různými nabídkami za pronájem této plochy. Požadavky musí být splněny buď v plné výši nebo vůbec. V tabulce jsou uvedeny požadavky na plochu Pí a ceny za pronájem uvedené plochy q od každého zájemce i = 1,..., 5. i 1 2 3 4 5 5000 1600 2800 6200 2200 Ci[Kč] 39000 9000 33000 63000 18000 Rozhodněte, kterým zájemcům poskytneme skladovací plochu, aby příjem z pronájmu byl co nejvyšší.