Příklady aplikací celočíselného lineárního programování

V úlohách lineárního programování, až na nutnost splnit předepsané omezující podmínky úlohy, mohou proměnné veličiny nabývat libovolných reálných hodnot. V úlohách celočíselného lineárního programování, jejichž příklady následují, se požaduje, aby (některé) neznámé veličiny, kromě nutnosti splnit omezující podmínky, nabývaly pouze celočíselných hodnot. Oproti úlohám (spojitého) lineárního programování jsou úlohy celočíselného lineárního programování výrazně těžší. Najít optimální řešení větší celočíselné úlohy může být nadlidský úkol (i přes pomoc soudobých počítačů). Pro velký praktický význam probíhá v této oblasti specializovaný teoretický výzkum. S pomocí důmyslných teoretických výsledků se pak daří řešit i relativně velké (tedy praktické) speciální instance těchto problémů.

Problém obchodního cestujícího (Travelling Salesman Problem)

Klasická formulace. Obchodní cestující má navštívit n měst, neboť v každém z nich má obchodní jednání. Každé město má navštívit právě jednou. Vzdálenost města i od města j je c_ij pro i, j = 1, 2, …, n. Cílem je určit, v jakém pořadí má obchodní cestující města navštívit tak, aby jeho celkové cestovní výlohy byly minimální.

Dopravní formulace. Firma má rozvézt zboží / zásilková firma má doručit zásilky n zákazníkům / adresátům. (Poštovní služba zajišťuje pravidelné vybírání poštovních schránek či pravidelnou přepravu zásilek z poštovních úřadů ve městě. Svozová firma zajišťuje pravidelný odvoz odpadu z kontejnerů, které jsou umístěny na n místech. Atd.) Vzdálenost mezi místy i a j, která je třeba obsloužit, je c_ij pro i, j = 1, 2, …, n. Úkolem je stanovit optimální trasu tak, aby její délka byla minimální.

Průmyslová aplikace. Podnik vyrábí desky (např. desky elektronických tištěných spojů). Do desek je třeba vyvrtat otvory, do nichž budou později zasunuty součástky. Podle technického výkresu můžeme určit vzdálenost c_ij mezi i-tým a j-tým otvorem, které je třeba vyvrtat, pro i, j = 1, 2, …, n. Desky bude automatizovaně obrábět číslicově řízený (CNC) stroj. Úkolem je stanovit optimální dráhu vrtačky tak, aby její délka (a tudíž doba obrábění jedné desky) byla minimální.

Problém čínského pošťáka (Chinese Postman Problem)

Úlohu lze formulovat následovně. Automobil provádějící údržbu má v zimním období ošetřit posypem (v letním období pokropit, během noci zamést) předepsanou síť (jednosměrných a obousměrných) silnic a ulic. Úkolem je stanovit optimální trasu automobilu tak, aby všechny silnice a ulice byly ošetřeny a celková délka trasy byla minimální.

Uvedená úloha je snadno řešitelná – jestliže síť obsahuje jednosměrné i obousměrné silnice a každá obousměrná silnice má být ošetřena v každém směru zvlášť (tj. dohromady dvakrát) nebo jestliže síť obsahuje pouze obousměrné silnice, které stačí ošetřit pouze jednou (z kterékoliv strany).

Pokud však síť obsahuje obousměrné silnice, které stačí ošetřit pouze jednou (z kterékoliv strany), i silnice jednosměrné, úloha přechází v obtížný smíšený problém čínského pošťáka.

Problém dělení materiálu (Cutting Stock Problem)

Klasická (jednorozměrná) formulace. Stavební firma pro vyztužení konstrukce potřebuje tyče o délkách ℓ₁, ℓ₂, …, ℓ_m. Firma potřebuje b₁ kusů tyčí délky ℓ₁, dále potřebuje b₂ kusů tyčí délky ℓ₂, …, potřebuje b_m kusů tyčí délky ℓ_m. Hutní závody dodávají tyče v několika málo standardizovaných délkách L₁, L₂, …, L_n. Jedna tyč délky L_j stojí c_j peněz pro j = 1, 2, …, n. Úkolem je určit, kolik tyčí je třeba z hutních závodů objednat a jak je potom rozřezat tak, aby konstrukci bylo možné vyztužit a cena za nákup tyčí byla minimální.

Poznámka. Problém dělení materiálů má celou řadu variant. Kromě výše uvedené jednorozměrné zmiňme alespoň dvourozměrnou: plech v klempířství / list papíru v papírnách je třeba rozdělit na menší obdélníkové části. Další varianta: z daného obdélníkového plechu potřebujeme vyřezat (vyseknout) co největší počet stejných výrobků (polotovarů).

Poznámka. Souvisejícím typem úloh jsou tzv. pakovací problémy (Packing Problems), například: na obdélníkovou plochu skladiště rozmístit co největší počet palet různých rozměrů (tj. nalézt rozmístění palet tak, aby na danou plochu se jich vešlo co nejvíce). Trojrozměrná varianta: do úložného prostoru automobilu (přepravního kontejneru apod.) umístit co největší počet zásilek (balíků) různých rozměrů.

Přiřazovací problémy (Assignment Problems)

Je celá řada přiřazovacích problémů. Níže uvádíme klasickou formulaci (která je snadno řešitelná, v podstatě jde o variantu dopravního problému, a tedy úlohu spojitého lineárního programování). Dále pak uvádíme příklady dvou obtížnějších variant, zahrnující další omezující podmínky reálné aplikace.

Klasická formulace. Firma má n pracovních čet (dílen apod.) a současně potřebuje zajistit vykonání stejného počtu n prací. Stupeň kvalifikace i-té pracovní čety k provedení j-té práce je c_ij pro i, j = 1, 2, …, n. Firma hledá optimální přiřazení pracovních čet k provedení prací – každá četa má být přiřazena k provedení právě jedné práce – tak, aby celkový součet kvalifikací byl maximální.

Varianta 1. V přírodě (na horách) pořádáme školení (seminář). Seminář sestává z několika dopoledních a odpoledních kursů, z nichž některé probíhají paralelně vedle sebe. Každý kurs má omezenou kapacitu (kapacita místnosti). Účastníci udávají preference pro jednotlivé kursy. Úkolem je přiřadit účastníky do jednotlivých kursů tak, aby kapacita kursů nebyla překročena, v jeden čas se účastník účastnil pouze jednoho kursu a celková spokojenost účastníků byla maximální.

Varianta 2. Rozvrhář fakulty (univerzity) na základě studijních plánů – doporučených a předpokládaných specializací, a tedy průchodů studiem – sestavil centrální rozvrh hodin. Daný předmět může probíhat ve více skupinách; každá skupina probíhá v některém čase v některé místnosti. Nyní si studenti (také s ohledem na doporučené studijní plány) vybírají, které předměty chtějí v daném semestru studovat; když si předmět vyberou, uvedou také preference pro jednotlivé skupiny daného předmětu (tj., kterou by chtěli navštěvovat nejraději apod.). Úkolem je sestavit osobní rozvrh každého studenta, tj., přiřadit studenty do skupin tak, aby každý student mohl studovat vybrané předměty (primární cíl), vyhovělo se preferencím studentů (sekundární cíl), aby studenti neměli v rozvrzích kolize a kapacita skupin (místností) nebyla překročena.

Poznámka. Otázka sestavení školního rozvrhu hodin (plánu výroby, jízdního řádu apod.) je další třídou optimalizačních úloh.

[Zpátky na téma Optimalizace a operační výzkum.]

Zveřejněno / aktualizováno: 15. 06. 2017