Mezi nejtypičtější úlohy lineárního programování patří tzv. distribuční úlohy lineárního programování. Z distribučních úloh v této kapitole podrobněji rozebereme dopravní problém a z formulačního hlediska se zmíníme o dalších úlohách jako je přiřazovací problém, okružní dopravní problém a obecný distribuční problém.

V dopravním problému se typickém případě jedná o rozvržení rozvozu nějakého zboží či materiálu z dodavatelských míst (zdroje) odběratelům (cílová místa) tak, aby byly minimalizovány celkové náklady související s tímto rozvozem. V dopravním problému je definováno m-zdrojů (dodavatelů) D₁, D₂, …, D_m s omezenými kapacitami a₁, a₂, …, a_m (množství, které je dodavatel schopen v uvažovaném období dodat ) a n-cílových míst (odběratelů) O₁, O₂, …, O_n se stanovenými požadavky b₁, b₂, …, b_n (množství, které odběratel v uvažovaném období požaduje). Vztah každé dvojice zdroj-cílové místo je nějakým způsobem oceněn. Tímto oceněním mohou být například vykalkulované náklady na přepravu jedné jednotky zboží mezi zdrojem a cílovým místem nebo kilometrová vzdálenost mezi zdrojem a cílovým místem. Kvantifikované ocenění vztahu zdrojů a cílových míst označím c_ij, i = 1, 2, …, m, j = 1, 2, …, n. Cílem řešení dopravního problému je naplánovat přepravu mezi zdroji a cílovými místy, tzn. stanovit objem přepravy mezi každou dvojici zdroj-cílové místo tak, aby nebyly překročeny kapacity zdrojů a aby byly uspokojeny požadavky cílových míst. Z hlediska matematického modelu je tedy třeba stanovit hodnoty proměnných x_ij, i = 1, 2, …, m, j = 1, 2, …, n, které vyjadřují objem přepravy mezi i-tým zdrojem a j-tým cílovým místem.

Výše uvedený popis lze považovat za typickou formulaci ekonomického modelu dopravního problému. Tuto formulaci lze přehledně vyjádřit ve formě tabulky (tabulka 1).

Tab. 1 – Formulace ekonomického modelu dopravního problému.

Při řešení dopravního problému je třeba uvažovat vztah celkové kapacity všech zdrojů å _i a_i (součet všech dílčích kapacit) a všech požadavků cílových míst å _j b_j (součet požadavků). Pouze ve speciálním případě bude patrně platit

å _i a_i = å _j b_j .

Takový dopravní problém budeme označovat jako vyrovnaný dopravní problém. V tomto případě platí, že všechny požadavky budou přesně uspokojeny a všechny kapacity budou vyčerpány. Dopravní problém, ve kterém

å _i a_{i ¹} å _j b_j

budeme označovat jako nevyrovnaný dopravní problém. Při převisu na straně nabídky zůstane část kapacity nevyužita a podobně při převisu na straně poptávky nebudou uspokojeny všechny požadavky.

My se v dalším textu budeme zabývat pouze vyrovnaným dopravním problémem, neboť nevyrovnaný problém lze na vyrovnaný snadno převést. Tento převod se realizuje tak, že

Ř při převisu nabídky k modelu doplníme tzv. fiktivní cílové místo O_F (fiktivní odběratel), jehož požadavek bude roven å _i a_i - å _j b_j , tj. rozdílu mezi celkovými kapacitami a požadavky – tabulka 1 bude tedy rozšířena o nový sloupec,

Ř při převisu poptávky k modelu doplníme tzv. fiktivní zdroj D_F (fiktivní dodavatel), jehož kapacita bude rovna å _j b_j - å _i a_i , tj. rozdílu mezi sumou požadavků a kapacit – tabulka 1 bude tedy rozšířena o nový řádek.

Zbývá poznamenat, že ocenění vztahu mezi zdroji a cílovými místy cij je u fiktivních činitelů nulové.

Při formulaci matematického modelu vyrovnaného dopravního problému si je třeba uvědomit, že model bude obsahovat m.n proměnných x_ij vyjadřujících objem přepravy mezi i-tým zdrojem a j-tým cílovým místem a dále bude obsahovat (m+n) vlastních omezení. Omezení jsou přitom dvojího druhu. Prvních m představuje bilanci pro jednotlivé zdroje – součet dodávek ze zdrojů cílovým místům nesmí přesáhnout kapacitu jednotlivých zdrojů (vzhledem k vyrovnanosti dopravního problému bude roven této kapacitě). Řádkové součty proměnných v tabulce 1 se tedy rovnají příslušným kapacitám. Zbývajících n omezení přísluší jednotlivým cílovým místům. Součet dodávek do jednotlivých cílových míst by se měl rovnat, opět vzhledem k vyrovnanosti dopravního problému, jednotlivým požadavkům. Matematický model vyrovnaného dopravního problému vypadá proto následovně:

minimalizovat

za podmínek

x₁₁ + x₁₂ + … + x_1n = a₁ u₁

x₂₁ + x₂₂ + … + x_2n = a₂ u₂

. . .

. . .

. . .

x_m1 + x_m2 + … + x_mn = a_m u_m

x₁₁ + x₂₁ . . . + x_m1 = b₁ v₁

x₁₂ + x₂₁ . . . + x_m2 = b₂ v₂

. . . . .

. . . . .

. . . . .

+ x_1n + x_2n . . . + x_mn = b_n v_n

x_ij ³ 0, i = 1, 2, … , m, j = 1, 2, …, n.

Koeficienty c_ij budeme v matematickém modelu označovat jako cenové koeficienty.

Současně s formulaci matematického modelu budeme formulovat i model k němu duálně sdružený. Ve výše uvedené formulaci jsme označili symboly u₁, u₂, …, u_m duální proměnné příslušející kapacitnímu omezením a pro odlišení symboly v₁, v₂, …, v_n duální proměnné pro omezení jednotlivých požadavků. Duální model bude vypadat následovně:

maximalizovat

za podmínek

u₁ + v₁ £ c₁₁,

u₂ + v₂ £ c₁₂,

.

.

u_m + v_n £ c_mn.

Vlastní omezení duální úlohy lze přehledně zapsat v následující podobě:

x_ij ³ 0 u_i + v_j £ c_{i j.}, i = 1, 2, …, m, j = 1, 2, …, n.

Nebo lze zapsat takto:

minimalizovat

z = c_ijx_ij

za podmínek

x_ij = a_i, i = 1, 2, …, m,

x_ij = b_j, j = 1, 2, …, n,

x_ij ³ 0, i = 1, 2, …, m, j = 1, 2, …, n.

Množina přípustných řešení vyrovnaného dopravního problému je určená soustavou (m+n) lineárních rovnic, které obsahují m.n proměnných, a podmínkami nezápornosti. Je však možné poměrně snadno ukázat, že hodnost rozšířené matice uvedené soustavy lineárních rovnic

není zrovna m+n, ale pouze m+n-1, že libovolný řádek uvedené matice lze získat jako lineární kombinaci všech řádků ostatních. Důsledkem toho je, že v základním řešení vyrovnaného dopravního problému je pouze m+n-1 základních proměnných.

Společnost Multicomp, s.r.o. má v ČR 3 střediska (Plzeň, Pardubice, Olomouc), ve kterých montuje osobní počítače. Kapacita těchto středisek je 330, 150 a 220 ks počítačů měsíčně. Tyto počítače jsou distribuovány smluvním odběratelům v Brně, Praze, Ostravě a Liberci. Podle smluv dodá Multicomp jednotlivým odběratelům postupně 180, 250, 160 a 110 ks počítačů. Distribuční náklady mezi středisky a odběrateli byly vykalkulovány na 1 ks počítače ve výši, která je zřejmá z tabulky 2 – údaj v pravém horním rohu každého pole (uvedené hodnoty jsou ve stovkách Kč).

 

	Brno	Praha	Ostrava	Liberec	Kapacity
Plzeň	11 x11	4 x12	17 x13	9 x14	330
Pardubice	6 x21	7 x22	10 x23	8 x24	150
Olomouc	3 x31	9 x32	5 x33	12 x34	220
Požadavky	180	250	160	110	700

Tab. 2 – Dopravní problém – formulace ekonomického modelu.

Formulace matematický modelu našeho vyrovnaného dopravního problému následnovně:

minimalizovat

za podmínek

x₂₁ + x₂₂ + x₂₃ + x₂₄ = 150

x₃₁ + x₃₂ + x₃₃ + x₃₄ = 220

x₁₂ + x₂₂ + x₃₂ = 250

x₁₃ + x₂₃ + x₃₃ = 160

x₁₄ + x₂₄ + x₃₄ = 110

x_ij ³ 0, i = 1, 2, 3, j = 1, 2, 3, 4.

 nahoru

Při výpočtu základního řešení se zde vlastně jedná pouze o to, doplnit do tabulky 1 hodnoty proměnných tak, aby jejich řádkové součty byly rovny kapacitám a sloupcové součty byly rovny požadavkům, a aby počet nenulových proměnných nebyl vyšší než m+n-1. Pro výpočet je možno použít tří metod: metoda severozápadního rohu, indexní metoda (metoda maticového minima) a metoda VAM.

Tato metoda umístí v prvním kroku přepravu do pole s proměnnou x₁₁, které je v tabulce vlevo nahoře tedy na „severozápadě“. V našem případě představuje toto pole přepravu mezi Brnem a Plzní, která bude ve výši 180 ks a tím je požadavek Brna plně uspokojen a je třeba zredukovat kapacitu Plzně z původních 330 ks na 330 – 180 = 150 ks. Dále pokračujeme stejným způsobem.

 

	Brno	Praha	Ostrava	Liberec	Kapacity
Plzeň	11 180	4 150	17	9	330
Pardubice	6	7 100	10 50	8	150
Olomouc	3	9	5 110	12 110	220
Požadavky	180	250	160	110	700

Tab. 3 – Dopravní problém – metoda severozápadního rohu.

 

Základní proměnná (přeprava odkud – kam)	Objem přepravy	Jednotkové náklady	Podíl na celk. náklady
x11 (Plzeň – Brno)	180	1 100	198 000
x12 (Plzeň – Ostrava)	150	400	60 000
x21 (Pardubice – Praha)	100	700	70 000
x22 (Pardubice – Ostrava)	50	1 000	50 000
x33 (Olomouc – Ostrava)	110	500	55 000
x34 (Olomouc – Liberec)	110	1 200	132 000
Náklady celkem	xxx	xxx	565 000

Tab. 4 – Výpočet hodnoty účelové funkce.

Z tabulky 4 je vidět, že celkové náklady přepravy pro řešení získané metodou severozápadního roku jsou 565 000 Kč.

Pozn.: Tato metoda poskytuje v typickém případě velmi špatné řešení, nebere totiž při obsazování přepravy v úvahu vůbec náklady přepravy. Proto se tato metoda nedoporučuje používat.

Tato metoda jako první umístí přepravu do pole s minimálními jednotkovými přepravními náklady, v našem případě jde o pole Olomouc-Brno. Umisťujeme stejně jako v předešlé metodě.

 

	Brno	Praha	Ostrava	Liberec	Kapacity
Plzeň	11	4 250	17 80	9	330
Pardubice	6	7	10 40	8 110	150
Olomouc	3 180	9	5 40	12	220
Požadavky	180	250	160	110	700

Tab. 4.8 – Dopravní problém – indexní metoda

Hodnota účelové funkce tohoto řešení je 438 000 Kč, což je lepší výsledek než v předchozí metodě.

 

Základní proměnná (přeprava odkud – kam)	Objem přepravy	Jednotkové náklady	Podíl na celk. náklady
x11 (Plzeň – Praha)	250	400	100000
x12 (Plzeň – Ostrava)	80	1700	136000
x21 (Pardubice – Ostrava)	40	1000	40000
x22 (Pardubice – Liberec)	110	800	88000
x33 (Olomouc – Brno)	180	300	54000
x34 (Olomouc – Ostrava)	40	500	20000
Náklady celkem	xxx	Xxx	438000

Indexní metoda poskytuje v typickém případě lepší řešení než metoda severozápadního rohu. Tuto skutečnost však nelze brát jako pravidlo. Negativním rysem indexní metody je, že sice zpočátku obsazuje přepravu do nejvýhodnějších polí, ale může se snadno stát, ze nakonec je třeba obsadit pole s nejméně výhodnými cenovými koeficienty.

Výpočet metodou VAM budeme ilustrovat na stejném příkladu. Tabulka 6 obsahuje 5 kroků výpočtu optimálního řešení. Tato metoda vychází z toho, že se pro každý řádek a sloupec dopravního problému vypočítají tzv. DIFERENCE, což je rozdíl mezi nejmenšími cenovými koeficienty v daném řádku či sloupci.. Vybere se pole, které má nejnižší cenový koeficient v řádku nebo sloupci s maximální diferencí. Může nastat situace, kdy existuje více řádků a sloupců se stejnou maximální diferencí. Pak vybereme pole, které má nejnižší sazbu z těch polí, které leží v řádcích a sloupcích s těmito maximálními diferencemi.Po obsazení pole dojde k vyloučení řádku a sloupce. Přepočítáme diference a postup zopakujeme.

Tab. 6 – Dopravní problém – metoda VAM (1. – 5. krok).

Hodnota účelové funkce tohoto řešení je 366000 Kč a je tedy výrazně lepší než řešení získané předchozími metodami.

 

Základní proměnná (přeprava odkud – kam)	Objem přepravy	Jednotkové náklady	Podíl na celk. náklady
x11 (Plzeň – Praha)	250	400	100000
x12 (Plzeň – Liberec)	80	900	72000
x21 (Pardubice – Brno)	120	600	72000
x22 (Pardubice – Liberec)	30	800	24000
x33 (Olomouc – Brno)	60	300	18000
x34 (Olomouc – Ostrava)	160	500	80000
Náklady celkem	xxx	xxx	366000

Metoda VAM poskytuje v typickém případě nejlepší řešení.

Po nalezení výchozího základního řešení je třeba provést test optimality, který spočívá ve výpočtu redukovaných cenových koeficientů z_ij

z_ij = u_i + v_j – c_ij, i = 1, 2, …, m, j = 1, 2, …, n.

Pro každou základní proměnnou x_ij, která je v typickém případě kladná, platí podle této věty z_ij = u_i + v_j – c_ij = 0, tedy u_i + v_j = c_ij. Aby řešení, jehož optimalitu testujeme, bylo řešením optimálním, musí platit pro všechny nezákladní proměnné, že jsou jejich redukované ceny nekladné. Dostáváme tedy dvě podmínky optimality:

Výpočetní realizace testu optimality:

1. Pro každé obsazené pole sestavíme rovnici u_i + v_j = c_ij. Dostáváme tedy soustavu m+n-1 rovnic pro m+n neznámých. Tato soustava má jeden stupeň volnosti a proto libovolně jednu z neznámých položíme rovnu nule a ostatní dopoč2. ítáme.

3. Duální proměnné vypoč4. tené v prvním kroku použijeme pro ověření druhé podmínky optimality, která udává, že redukované ceny z_ij pro nezákladní proměnné musí být nekladné. Pokud tomu tak je, je testované základní řešení řešením optimálním.

 

Test optimality ukážeme na výchozím základním řešení našeho příkladu, tabulka 5.

Základní proměnné s jejich hodnotou a jim odpovídající rovnice u_i + v_j = c_ij uvádíme v následujícím přehledu:

x₁₂ = 250 Þ u₁ + v₂ = 4 ,

x₁₂ = 80 Þ u₁ + v₃ = 17 ,

x₁₂ = 40 Þ u₂ + v₃ = 10 ,

x₁₂ = 110 Þ u₂ + v₄ = 8 ,

x₁₂ = 180 Þ u₃ + v₁ = 3 ,

x₁₂ = 40 Þ u₃ + v₃ = 5 .

Položíme-li například neznámou v₃ = 0, potom pro ostatní duální proměnné dostáváme již snadno – u₁ = 17, u₂ = 10, u₃ = 5, v₁ = -2, v₂ = - 13 a v₄ = -2. Pro nezákladní proměnné vypočteme redukované ceny:

x₁₁ = 0 Þ z₁₁ = u₁ + v₁ – c₁₁ = 17 – 2 – 11 = 4 ,

x₁₄ = 0 Þ z₁₄ = u₁ + v₄ – c₁₄ = 17 – 2 – 9 = 6 ,

x₂₁ = 0 Þ z₂₁ = u₂ + v₁ – c₂₁ = 10 – 2 – 6 = 2 ,

x₂₂ = 0 Þ z₂₂ = u₂ + v₂ – c₂₂ = 10 – 13 – 7 = -10 ,

x₃₂ = 0 Þ z₃₂ = u₃ + v₂ – c₃₂ = 5 – 13 – 9 = -17 ,

x₃₄ = 0 Þ z₃₄ = u₃ + v₄ – c₃₄ = 5 – 2 – 12 = -9 .

Z uvedeného přitom plyne, že testované řešení není optimální, protože je zde test optimality porušen u proměnných x₁₁, x₁₄ a x₂₁, u kterých jsou redukované ceny kladné.

Provádí se stejně jako u simplexovy metody. Zvolí se ta proměnná, která nejvíce porušuje test optimality. Volí se tedy podle maximálního kladného redukovaného cenového koeficientu.

Z_rs = max (z_ij )

z_{ij >} 0

Pokud toto určení není jednoznačné, zvolí se vstupující proměnná libovolně z proměnných, které přicházejí v úvahu. Vstupující proměnná určuje klíčové pole. V našem případě je vstupující proměnná x₁₄ , protože redukovaná cena u této proměnné je 6, a porušuje tak nejvíce test optimality.

Je třeba nejdříve zkonstruovat tzv. uzavřený kruh. Je to posloupnost obsazených polí, která začíná a současně končí v klíčovém poli. Tento kruh je určen jednoznačně. Po určení uzavřeného kruhu označíme jeho prvky střídavě symbolem +t a –t. V klíčovém poli je přitom symbol +t. Vystupující proměnná je určená minimální hodnotou x_ij , které jsou označeny symbolem –t. Pokud je polí s touto minimální hodnotou více, zvolí se vstupující proměnná libovolně z nich. Hodnota t určuje současně hodnotu nově vstupující proměnné. V našem případě vychází jako vystupující proměnná x₁₃ a hodnota t =80.

K polím označeným +t se jednoduše hodnota t přičte a naopak od polí označených –t se odečte. Ostatní pole zůstanou beze změny. V každém kroku výpočtu musí zůstat zachován počet základních proměnných m+n-1. Změnu hodnoty účelové funkce pro vstupující proměnnou x_rs lze vypočítat podle vztahu ∆z(x_rs) = -t* Z_rs . V našem případě dostáváme ∆z(x₁₄ ) = -80*6 = -480 – hodnota účelové funkce se sníží o 48000 Kč.

V našem případě je vstupující proměnou tedy x₁₄ . Klíčové pole a prvky uzavřeného kruhu jsou v tabulce zvýrazněny. Vystupující proměnná je zřejmě x₁₃ –hodnota t = min (80,110) = 80. Hodnota účelové funkce se v prvním kroku snížila z hodnoty 438000 Kč o 48000 Kč a její nová hodnota je 390000 Kč.

V novém řešení opět realizujeme test optimality. V našem případě je porušen pouze u proměnné x₂₁ , jejíž cenový koeficient je roven 2 (má být záporný). Je to teda nová vstupující proměnná. Vystupující proměnnou je x₂₃ – hodnota t = min(120,180) = 120. Změna hodnoty účelové funkce nového řešení je rovna

∆z(x₂₁ )= -120*2 = -240 – nová výše nákladů je tedy 390000 – 24000 = 366000 Kč.

Přepočteme-li znovu tabulku dosáhneme již optimálního řešení, protože všechny nezákladní proměnné již budou záporné. Všimněte si, že se jedná o řešení, které je shodné s výchozím základním řešením vypočteným metodou VAM.

Optimální řešení může být přitom buď jediné nebo alternativní. Jediné řešení má dopravní problém v případě, že jsou všechny redukované cenové koeficienty u nezákladních proměnných záporné. Pokud je alespoň jeden z těchto koeficientů roven nule má dopravní problém alternativní řešení.