VÍCESTUPŇOVÉ DOPRAVNÍ MODELY A JEJICH PROGRAMOVÁ REALIZACE

multilevel transshipment problems and software realization

Tomáš Šubrt

Adresa autora:

Dr. Ing. Tomáš Šubrt, katedra operační a systémové analýzy, PEF

Česká zemědělská univerzita v Praze, 165 21 Praha 6 - Suchdol

Anotace:

Příspěvek souvisí se zajímavou možností převodu obecné vícestupňové dvourozměrné optimalizační dopravní úlohy na úlohu jednostupňovou. První část příspěvku se týká teoretického rozboru této problematiky, neboť převod je možný jen za specifických podmínek. Druhá část je věnována možnostem automatizovaného výpočtu. Programová realizace vícestupňové úlohy není autorovi známa, ovšem po převodu lze takovouto úlohu spočítat a analyzovat standardními algoritmy. O možnost takového převodu byl rozšířen modul Dumkosa.xla. Vlastní výpočet a rozbor výsledků lze poté provést za využití optimalizačních algoritmů tohoto modulu, umožňujícího jinak pouze řešení úloh jednostupňových.

Summary:

The paper deals with problematic of conversion of multilevel transshipment problem on a standard optimization transportation problem. This conversion is possible only under specific conditions. In the firs part of this article a mathematical model of multilevel transshipment problem is defined. Consequently some principles of its conversion to a standard transportation problem are described too. The second part of the paer is oriented in software realization of such conversion. For this purpose the add in module for solving transportation problems Dumkosa was selected and extended. Due to this extension this module can be used for solving and solution analyzing of multilevel transshipment models.

Klíčová slova:

Vícestupňové dopravní úlohy, vícerozměrné dopravní úlohy, optimalizační dopravní model, tabulkový procesor, doplněk Excelu, Dumkosa.xla

Keywords:

Multilevel transshipment problems, multiindex transportation problems, transportation optimization models, spreadsheet, Add In module for Excel, Dumkosa.xla

Problematika optimalizačních dopravních úloh byla rozvíjena především v 60. letech tohoto století a navázala tak na rychlý rozvoj obecných metod lineárního programování z let čtyřicátých a padesátých. Především oblast vícestupňových a vícerozměrných (víceindexních) úloh, principiálně odvozených od úloh jednostupňových a dvourozměrných, doznala díky sílícímu uplatnění výpočetní techniky jistého rozvoje. Z hlediska pojmového dochází u složitějších typů optimalizačních dopravních úloh často k nepřesnostem, proto zde uvedu jen velmi stručně rozdíl, mezi vícerozměrnou a vícestupňovou úlohou. Počtem stupňů úlohy rozumějme počet dopravních uzlů, kterými musí materiál projít na cestě od primárního dodavatele k finálnímu spotřebiteli. Je-li přeprava realizována přímo, jedná se o úlohy jednostupňové, je-li nutno realizovat transport přes mezisklad, jedná se o úlohy dvoustupňové atd. Rozměrností úlohy naopak rozumějme míru složitosti přepravy mezi dvěma souslednými stupni úlohy. Nesledujeme-li nic jiného, než výchozí a cílové body mezi těmito stupni, jedná se o úlohu dvourozměrnou (výchozí stupeň: dodavatel, cílový stupeň: spotřebitel). Sledujeme-li navíc technologii přepravy resp. použité dopravní prostředky, jedná se o úlohu třírozměrnou (odkud, kam, čím). Čtvrtým rozměrem mohou být např. časové intervaly přepravy atd. Stupně a rozměry úlohy se často zaměňují a mezi sebou chybně převádějí - třístupňová a třírozměrná úloha však vedou ke dvěma různým úlohám matematického programování. Ve veškerém dalším textu se budu zabývat pouze úlohami vícestupňovými a dvourozměrnými (dvouindexními). Problematika řešení vícerozměrných úloh je řešena např. v [2].

Za optimální řešení každé minimalizační dopravní úlohy (dále uvažujme pouze tento typ, neboť u klasických modelů jednoznačně převažuje nad maximalizačními) lze považovat přepravní plán (strukturu přepravy) od primárních dodavatelů k finálním spotřebitelům s minimálními náklady resp. minimálním množstvím ujetých kilometrů. U vícestupňových modelů musí být navíc splněn předpoklad vyprázdnění všech meziskladů po realizaci přepravy. Matematický model minimalizační dvourozměrné r stupňové dopravní úlohy je tedy možno definovat takto:

kde: r ….. počet stupňů úlohy k ….. aktuální stupeň uzlu nk ….. počet uzlů k -tého stupně ik ….. indexy uzlů k -tého stupně ….. kapacita i -tého uzlu k -tého stupně ….. jednotkové přepravní náklady po trase mezi uzly sousl. stupňů (k, k+1) ….. přepravené množství mezi uzly sousledných stupňů (k, k+1) ….. nevyužitý objem i -tého uzlu k -tého stupně

Každá vícestupňová úloha je převoditelná na obecnou úlohu lineárního programování, nicméně tento převod je poměrně složitý a již malé úlohy vedou k rozsáhlým soustavám omezujících podmínek. Dvoustupňové úlohy je možno řešit speciální metodou, principiálně obdobnou algoritmům úlohy jednostupňové (metoda Modi), nicméně již úloha třístupňová tímto principem řešitelná není. Opomeneme-li metody aproximativní, je jen velmi obtížné optimalizovat dopravní modely, kde při transportu mezi primárním dodavatelem a finálním spotřebitelem je nutno zboží přeložit ve více než jednom meziskladu. Jistou cestou k řešení takovýchto modelů je zobecnění algoritmu převodu úlohy dvoustupňové i pro úlohy tří a vícestupňové. Podmínkou úspěšného převodu je však dostatečná kapacita jednotlivých meziskladů (poslední podmínka v matematickém modelu uvedeném výše), nutnost uspokojení finálních spotřebitelů je zaměnitelná za nutnost úplného vyčerpání primárních dodavatelů. Poslední podmínka modelu by potom měla tvar

.

Podstatou převodu je zavedení doplňkových proměnných s preferenčními (obvykle nulovými) sazbami reprezentujícími nevyužití meziskladů jednotlivých stupňů. Toto nevyužití je modelováno jako “transport” v rámci jediného uzlu s obvykle nulovými náklady. Nenulové sazby by mohly reprezentovat např. náklady na skladování či naopak v záporné formě výnos s pronájmu skladu v případě jeho nevyužívání. Klasický model však předpokládá vždy sazby nulové. Dále jsou do modelu zavedeny proměnné fiktivní se sazbami prohibitivními představující zakázané trasy (zkratky bez vykládky v jednotlivých stupních resp. transporty mezi různými uzly stejného stupně navzájem). Fakticky se tak do základní matice sazeb jednostupňového systému zavedou submatice prohibitivních a preferenčních sazeb. První stupeň převedeného problému (dodavatelé) představují všechny výchozí stupně problému původního, druhý stupeň převedeného problému (spotřebitelé) potom všechny cílové stupně problému původního. Převod obecné dvourozměrné r stupňové dopravní úlohy na jednostupňovou je možno matematicky formulovat takto:

kde ….. počet dodavatelů ….. počet spotřebitelů a = (a0, a1, …, ak-1, …, ar-1)….. kapacity dodavatelů b = (a1, a2, …, ak, …, ar) ….. požadavky spotřebitelů cij ….. jednotkové přepravní náklady po trase mezi i-tým dodavatelem a j-tým spotřebitelem xij ….. přepravené množství po trase mezi i-tým dodavatelem a j-tým spotřebitelem

Uspořádáme-li sazby cij do matice C = (cij) o rozměrech m x a, je možno dekompozici zavedením submatic s prohibitivními a preferenčními sazbami vyjádřit schématem:

kde

submatice prohibitivních sazeb P = (pls); pls = p; p … prohibitivní sazba

submatice preferenčních sazeb F = (fls); fls = p; pro l ą s;

fls = f; pro l = s; f … preferenční sazba (resp. nulová sazba)

Ze schématu dekompozice matice sazeb vyplývá, že s rostoucím počtem stupňů úlohy exponenciálně narůstá počet fiktivních proměnných v modelu. S touto vlastností se lze poměrně těžko vyrovnat v případě ručních výpočtů, jakož i v případě ručního zadávání pro automatizované zpracování. Uvažujeme-li matematické modelování v tabulkových procesorech, je však možné tuto dekompozici elegantním způsobem zpřehlednit a jistou formou i zautomatizovat. Dekompozici matice cen v tabulkové formě je opět možno vyjádřit schématem, kde názvy dodavatelů (T0, T1, …, Tk-1, …, Tr-1) odpovídají názvům výchozích stupňů vícestupňového problému (od primárních dodavatelů po mezisklady poslední úrovně) a názvy spotřebitelů (T1, T2, …, Tk, …, Tr) odpovídají názvům cílových stupňů vícestupňového problému (od meziskladů první úrovně po finální spotřebitele).

Softwarová realizace řešení jednostupňové dvourozměrné dopravní úlohy v Excelu 5.0 resp. 97 s využitím modulu Dumkosa.xla byla publikována např. v [1] a [4]. Základem všech řešení s využitím těchto doplňků (ADD In modulů) je vždy kvantifikovaný model rozvržený na listu tabulkového procesoru. Pro usnadnění této kvantifikace pro následné řešení úloh vícestupňových bylo nutno Dumkosu rozšířit o automatizovanou dekompozici matice cen s napevno zadanými prohibitivními a preferenčními sazbami (dle uživatelské volby). Po spuštění modulu má tedy uživatel možnost nechat si připravit odpovídající schéma a ručně zadává reálné jen sazby mezi sousedními stupni úlohy a kapacity uzlů jednotlivých stupňů - viz Obrázek 1 a Obrázek 2.

Obrázek 1: Nový vstupní dialog modulu Dumkosa

Obrázek 2: Zadávání základních parametrů vícestupňové úlohy

Výsledkem volby “Příprava listu” a zadání parametrů je schéma úlohy na listu tabulkového procesoru připravené pro zadávání reálných sazeb mezi jednotlivými stupni - viz Obrázek 3.

Obrázek 3 : Schéma čtyřstupňové úlohy na listu Excelu připravené ke kvantifikaci

Spuštěním vlastního výpočtu se tak vícestupňový problém vyřeší s využitím algoritmu pro řešení problému jednostupňového a výsledky se opět formálně upraví tak, aby odpovídaly výchozí vícestupňové úloze - viz Obrázek 4.

Obrázek 4: Optimální řešení čtyřstupňové úlohy vypočtené modulem Dumkosa

Závěr

Vícestupňové dopravní úlohy byly dlouhou dobu opomíjené v důsledku nedostatečného softwarového zabezpečení jejich řešení. Díky zobecnění principu převodu dvoustupňových dopravních úloh na jednostupňové i pro úlohy s více úrovněmi meziskladů je možno využívat i existující software z oblasti jednostupňových modelů. Využití excelovského doplňku Dumkosa a jeho rozšíření o možnost automatického převodu vícestupňových úloh představuje novou kvalitu v chápání a řešení těchto složitých optimalizačních dopravních modelů.

Literatura

[1] Brožová, H., Šubrt, T.: Moduly pro matematické modelování v prostředí Excel, In: Sborník přednášek a programů konference Pedagogický software 97, České Budějovice 1997

[2] Havlíček, J.: Optimalizace vícerozměrných dopravních systémů. Habilitační práce. VŠZ Praha 1991

[3] Černý, J.:, Kluvánek, P.: Základy matematickej teórie dopravy. Veda Bratislava 1989

[4] Šubrt, T., Růžička, M., Brožová, H., Krechler, J.: Simulační a dopravní moduly pro prostředí Excel. Závěrečná zpráva grantového úkolu, ČZU Praha 1996.