DOPRAVNÍ ÚLOHA (klasický dopravní problém) PRIMÁRNÍ A DUÁLNÍ ÚLOHA Máme skladišť (dodavatelů) číslo s jedním druhem zboží. Skladiště číslo obsahuje jednotek zboží pro . Dále máme spotřebitelů (zákazníků, odběratelů) číslo . Spotřebitel číslo požaduje dodat jednotek zboží pro . Cena přepravy jedné jednotky zboží od dodavatele ke spotřebiteli činí peněz pro a pro . Úkolem je stanovit plán přepravy zboží od dodavatelů ke spotřebitelům tak, aby kapacity skladišť nebyly překročeny, požadavky zákazníků byly uspokojeny a celkové přepravní náklady byly minimální. Úlohu formulujeme jako úlohu lineárního programování. Účelem je stanovit optimální plán přepravy. Jako označme plánované množství zboží, které bude přepraveno od dodavatele ke spotřebiteli pro a pro . Primární úloha, která vyjadřuje (tj. modeluje) zadanou dopravní úlohu, je následující: za podmínek Duální úloha je následující: za podmínek kde a jsou proměnné. Příklad: Následující tabulka shrnuje zadání klasické dopravní úlohy s dodavateli a odběrateli. Levý sloupeček zachycuje kapacity skladišť ( ), první řádek zachycuje požadavky zákazníků ( ) a ostatní buňky tabulky zachycují jednotkové přepravní náklady ( ): Primární úloha vypadá v tomto případě následovně: za podmínek Ekvivalentně lze primární úlohu zapsat následovně: za podmínek a Duální úloha vypadá tudíž následovně: za podmínek a Ekvivalentní, stručný zápis duální úlohy je zřejmý: za podmínek a PŘÍKLAD DOPRAVNÍ ÚLOHA TERÉNNÍ ÚPRAVY – VYROVNÁNÍ TERÉNU úroveň terénu stávající úroveň terénu požadovaná kopec = terén nad požadovanou úrovní = „dodavatel / zdroj“ údolí = terén pod požadovanou úrovní = „odběratel / spotřebitel“ = cena za přepravu jedné jednotky zeminy z do = podle vzdálenosti