RAC UNALNI STVO Linearni problem prevoza Dragana Božovič in Andrej Taranenko -> Tovarna čokolad skladišči svoje izdelke na različnih lokacijah v Sloveniji, te izdelke pa želijo dostaviti v več trgovin, prav tako na različnih lokacijah. V času krize želijo pri razvozu svojih izdelkov čim več prihraniti. Kako naj tovarna dostavi svoje izdelke trgovinam tako, da bo vsaka trgovina prejela vsaj naročeno število izdelkov, da bo skupno število razvoženih izdelkov največ enako zalogi le-teh in da bo tovarno razvoz izdelkov iz skladišč v trgovine stal čim manj? Na ta vprašanja bomo odgovorili v tem članku. Linearno programiranje in problem prevoza Problemi linearnega programiranja so optimizacijski problemi, v katerih želimo optimizirati določeno ciljno funkcijo, pri čemer moramo zadoščati podanim pogojem oziroma omejitvam. V tovrstnih problemih so pogoji in ciljna funkcija vedno linearne funkcije optimizacijskih spremenljivk. Pobližje bomo spoznali problem prevoza, znan tudi pod imenom transportni problem. Problem prevoza je optimizacijski problem, v katerem najveckrat želimo minimizirati stroške prevoza. Za lažjo predstavo vzemimo našo tovarno cokolad. Recimo, da ima ta tovarna na razlicnih lokacijah po Sloveniji m skladišc in n trgovin. Posamezni izdelek lahko iz nekega skladišca dostavimo do vsake trgovine. V vsakem skladišcu imamo natancno doloceno kolicino oziroma zalogo izdelkov, ki so v danem casu skladi-šceni (torej, na voljo). Vsaka trgovina v danem casu naroci tocno doloceno kolicino izdelkov (povpraševanje trgovine). Še vec, za vsako skladišce je znano, koliko stane prevoz enote izdelka do vsake izmed trgovin. Cena je obicajno odvisna od razdalje med skladišcem in trgovino ter od prevoznega sredstva, ki ga uporabimo. Predpostavimo, da so cene prevoza posamezne enote izdelka (npr. karton cokolad) od skladišca do trgovine znane in so celoštevilske. Oznacimo omenjene kolicine na naslednji nacin: ■ Število si predstavlja zalogo (enot) izdelka v skla-dišcu i, kjer je i = 1, 2,...,m. ■ Število dj predstavlja, koliko enot izdelka naroca trgovina j, kjer je j = 1 , 2, . . . , n. ■ S številom cij oznacimo, koliko stane prevoz ene enote izdelka iz skladišca i v trgovino j, za i = 1, 2,... ,m in j = 1, 2,...,n. S številom xij oznacimo, koliko enot izdelka peljemo iz skladišca i do trgovine j, za i = 1, 2,..., m in j = 1 , 2 , . . . , n. Cilj je dolociti, kako razvoziti izdelke med skla-dišci in trgovinami tako, da bo razvoz ustrezal zalogam (ponudbam) in povpraševanjem, pri cemer bodo skupni stroški najmanjši možni. Opišimo zastavljeni problem še matematicno. S ciljno funkcijo zapišimo skupne stroške, ki jih želimo minimizirati. Ceno prevoza iz skladišca i do trgovine j lahko torej izracunamo kot cij ■ xi j. Skupno ceno razvoza iz vseh skladišc do vseh trgovin dobimo tako, da seštejemo stroške za vse možne pare vrednosti števil i in j. Naša ciljna funkcija z je torej (linearna) funkcija: z = I i=1j=1 K< i ,j xi j)- Seveda želimo dolociti vrednosti xi,j tako, da bo funkcija z imela za te vrednosti cim manjšo vrednost (želimo minimizirati z). Opišimo še omejitve, ki se v problemu prevoza naravno pojavijo. Iz skladišca i lahko pošljemo izdelke v razlicne trgovine. Število vseh enot izdelkov, ki jih iz skladišca i pošljemo, je torej enako vsoti vseh ko-licin, ki smo jih iz tega skladišca razvozili do vseh trgovin, torej od kolicine enot iz skladišca i, ki jo peljemo do trgovine 1 (xi,1), do trgovine 2 (xi,2), in tako naprej, vse do trgovine n (xi n). Zapisano drugace, iz skladišca i razvozimo skupno xi, 1 + xi,2 + ... + xi,n enot izdelka. Zapisano s simbolom za vsoto, je to 24 PRESEK 41 (2013/2014) 2 RAČUNALNIŠ TVO S 1 xi,j ■ Ker ima (vsako) skladišče i omejeno za- logo si, iz tega skladišča ne moremo poslati več izdelkov, kot jih je na zalogi. To omejitev lahko za vsako skladišče i = l,...,m izrazimo na naslednji način: xi j=i i,j < Si Poglejmo še trgovino j. V to trgovino prispejo izdelki iz vseh skladišč (količina je lahko tudi 0, kar pomeni, da iz skladišča v to trgovino nismo poslali izdelka). Torej je skupna količina enot izdelka, ki jo trgovina prejme, enaka x1 j +x2 j + .. .+xm j. Znova, zapisano krajše, je ta količina Xm=i xi j. Ker je skupno povpraševanje trgovine j enako dj, potem čelotna količina dostavljenih izdelkov ne sme biti manjša od dj (lahko pa trgovina skupno prejme več, kot je naročila). Ta pogoj lahko za vsako trgovino j = i, ...,n zapišemo kot X xi j ^ dj■ i=1 Ker lahko iz skladišča do trgovine pošljemo 0 ali več enot izdelkov, morajo biti vsi xi j nenegativna čela števila (enot ne moremo še bolj razdrobiti). Problem prevoza lahko sedaj formalno zapišemo na naslednji način [2]: minimiziraj pri pogojih: n X xi j ^ si j=1 m X xi j * dj i1 mn z = X X Ci jXi- ci jxi j (1) i=1 j=1 za i = 1, ...,m za j = 1, ...,n xij * 0 za i = 1,...,m in j = 1,...,n Kadar je skupna količina zaloge vseh skladišč enaka skupni količini povpraševanj vseh trgovin, pravimo, da je problem prevoza uravnotežen. Zapisano drugače, problem prevoza je uravnotežen, če velja m n ]Lsi = X dj. Poglejmo si zadevo še na konkretnem primeru, ki je povzet po [1]. Naša tovarna čokolad ima v Sloveniji tri različna skladišča. Mesečno s svojimi izdelki oskrbuje štiri trgovine, ki se nahajajo v različnih krajih. Poznamo zalogo skladišč, povpraševanje trgovin in transportne stroške na enoto izdelka iz vsakega skladišča do vsake trgovine. Kako naj tovarna razvozi svoje izdelke iz skladišč do trgovin tako, da bodo transportni stroški najmanjši možni? Podatki tega problema so prikazani v tabeli 1. Števila, zapisana s krepko, predstavljajo transportne stroške. Tako vidimo, da je čena prevoza enote izdelka iz skladišča 1 do trgovine 1 enaka 10, prevoz iz skladišča 2 do trgovine 3 stane na enoto 9, strošek prevoza ene enote izdelka iz skladišča 3 do trgovine 1 pa je brezplačen (enak 0). Opazimo lahko tudi, da je ta problem prevoza uravnotežen. Problem bomo rešili s pomočjo programa (reševalnika) za reševanje problemov linearnega programiranja, za to pa moramo spoznati jezik AMPL, s katerim opišemo naš primer. trgovine skladišče 1 2 3 4 zaloga skladišča 1 10 0 20 11 20 2 12 7 9 20 25 3 0 14 16 18 15 povpraševanje 10 15 15 20 TABELA 1. Podatki za razvoz. i1 j=1 Jezik AMPL Problem bomo rešili s pomočjo jezika AMPL (angl. A Mathematical Programming Language)■ AMPL je jezik za modeliranje v matematični optimizaciji. Uporabljamo ga za opisovanje in reševanje problemov z veliko zahtevnostjo ter obsežnim matematičnim računanjem. Razvili so ga Robert Fourer, David Gay and Brian Kernighan v Bell Laboratories. AMPL podpira desetine različnih reševalnikov problemov, ki so tako odprto-kodni kot komerčialni. Posebna prednost jezika AMPL je podobnost njegove sintakse z matematičnim zapisom optimizačij-skih problemov. Ta prednost omogoča zelo čitljivo in jedrnato opredelitev problemov na področju opti- PRESEK 41 (2013/2014) 2 25 RAČUNALNIŠ TVO mizacije. Mnogi sodobni reševalniki, ki so dostopni na strežniku NEOS1, sprejemajo za vhod probleme, zapisane v jeziku AMPL. Glede na statistike strežnika NEOS je AMPL najbolj priljubljen format za predstavitev problemov matematičnega programiranja [3]. Preden problem rešimo, ga moramo zapisati v ustrezni obliki, ki predstavlja vhod (vhodne podatke) za reševalnik. Vhod je v AMPL-u sestavljen iz treh datotek, in sicer .mod, .dat in .txt. Ko pričnemo s programiranjem, najprej ustvarimo datoteko .mod, v kateri podamo ciljno funkcijo in omejitve našega problema. Na zacetku datoteke najprej definiramo množice, ki so potrebne za reševanje problema. Množico, vkljucno z njenimi elementi, zapišemo na naslednji nacin, pri cemer v zavitih oklepajih podamo elemente množice: ■ set A := {a1,a2,...,ak}; Definiramo lahko parametre, ki predstavljajo podatke, podane na zacetku reševanja problema. Parameter definiramo kot ■ param Ime {A}; Pri tem A predstavlja množico, na katero se sam parameter navezuje. Parameter se lahko navezuje tudi na vec množic (vecdimenzionalni parameter), ki jih podamo v zavitem oklepaju ter jih locimo z vejico. Naslednji korak je definicija spremenljivk našega problema. Spremenljivko definiramo kot ■ var Ime {a in A}; Tudi spremenljivka se lahko navezuje na vec množic, ki jih zapišemo v zavitih oklepajih ter locimo z vejico. Ciljno funkcijo in želeno optimizacijo podamo kot ■ minimize/maximize Ime: funkcija; Omejitve problema pa zapišemo kot ■ subject to Ime: omejitev; Ce se omejitev navezuje na doloceno množico, to zapišemo kot ■ subject to Ime {a in A}: omejitev; 1 Seznam najdemo na naslovu http://www.neos-server, org/neos/solvers/index.html, preverjeno 3. 10. 2013 Problem iz našega primera bi zapisali na nacin, kot je prikazan v izpisu datoteke 1. Najprej definiramo množici M = {1, 2, 3} in N = {1, 2, 3,4}. Nato napovemo, da bomo imeli tri parametre: parameter c bo matrika dimenzije 3x4 (indeksi so vzeti iz množic M in N) in predstavlja matriko cen, parameter 5 predstavlja vektor zalog skladišč, d pa vektor povpraševanj trgovin. Vrstica var x {i in M,j in N} >= 0; deklarira optimizacijske spremenljivke xtj in pove, da morajo biti nenegativne. Zadnje tri vrstice podajo ciljno funkcijo, ki jo minimiziramo, ter omejitve optimizacije. Izpis datoteke 1 AMPL model (.mod) set M := {1..3}; set N := {1..4}; param c {M,N}; param s {i in M}; param d {j in N}; var x {i in M,j in N} >= 0; minimize sudoku: sum {i in M, j in N} c [i,j]*x[i,j]; subject to izvori {i in M}: sum {j in N} x[i,j] <= s[i]; subject to povpraševanje {j in N}: sum {i in M} x[i,j] >= d[j]; V podatkovni datoteki . dat moramo dolociti vrednosti parametrov, ki smo jih napovedali v modelu. Parametre, ki predstavljajo vektorje, zapišemo na naslednji nacin: ■ param imeParametra := indeksi vrednosti indeks2 vrednost2 ...; Ce parameter predstavlja matriko, pa pred := in za parametrom zapišemo indekse stolpcev, za tem simbolom pa zapišemo indeks vrstice in naštejemo vse elemente, locene s presledkom. Na koncu zadnje vrstice ne smemo pozabiti na podpicje. Pozorni moramo biti tudi na to, da indekse iz množice, ki smo jo v deklaraciji parametra podali kot prvo, damo v vrstice, elemente druge množice pa v stolpce. Datoteka s podatki za naš primer je prikazana v izpisu datoteke 2. Najprej definiramo parametra 5 in d. Kot že vemo, 5 predstavlja vektor zalog skladišc, d pa vektor povpraševanj trgovin. Zapišemo ju tako, da najprej podamo indeks v vektorju, takoj za njim pa vrednost, ki je na tem mestu v vektorju. To storimo za vse koordinate vektorja. Vse to zapišemo v 26 PRESEK 41 (2013/2014) 2 26 RAČUNALNIŠ TVO eni vrstici, pri cemer številke locimo s presledki. V prvi vrstici za vektor 5 vidimo, da je vrednost na prvi koordinati je 20, na drugi 25 in na tretji 15. Podobno velja za vektor d. Nato definiramo še parameter c oziroma matriko cen, ki je dimenzij 3 x 4. Najprej je treba zapisati indekse vseh stolpcev, v našem primeru naravna števila od ena do štiri (kot je zapisano v četrti vrstici). Nato zapišemo vrstice. Najprej zapišemo številko vrstice, nato naštejemo vrednosti, ki se v tej vrstici nahajajo. To storimo za vse vrstice, ki jih imamo, pri cemer številke locimo s presledki. Torej najprej za prvo vrstico (1 10 0 20 11), nato drugo (2 12 7 9 20) in na koncu še tretjo vrstico (3 0 14 16 18). Izpis datoteke 2 AMPL model (.dat) param s := 1 20 2 25 3 15; param d := 1 10 2 15 3 15 4 20; param c: 12 3 4:= 1 10 0 20 11 2 12 7 9 20 3 0 14 16 18; Reševalniku moramo podati tudi ukaze, kaj naj z modelom in podatki stori. S stavkom sol ve; mu povemo, naj problem reši, s stavkom display x; pa, da naj izpiše rezultat, torej koncne vrednosti optimi-zacijskih spremenljivk x (matriko). Ukazna datoteka je prikazana v izpisu datoteke 3. Izpis datoteke 3 AMPL model (.txt) solve; di splay x; Nato naložimo vse tri datoteke in počakamo na rešitev optimizacijske naloge [4]. NEOS reševalnik (Mixed Integer Linear Programming - scip[AMPL Input]) izpiše naslednji rezultat: x 1 1 0 1 2 5 1 3 0 1 4 15 2 1 0 2 2 10 2 3 15 2 4 0 3 1 10 3 2 0 3 3 0 3 4 5 To rešitev lahko predstavimo z naslednjo tabelo, pri cemer prva vrstica predstavlja oznake trgovin, prvi stolpec pa oznake skladišc. 1 2 3 Torej so stroški prevoza našega problema najmanjši v primeru, ko imamo naslednje vrednosti optimiza-cijskih spremenljivk: x1j2 = 5, x1j4 = 15, x2,2 = 10, x2,3 = 15, x3j1 = 10, x3,4 = 15, vse ostale vrednosti xtj, ki jih tukaj nismo našteli, imajo vrednost 0. Najmanjši stroški prevoza za naš primer znašajo ■ 5 ■ 0 + 15 ■ 11 + 10 ■ 7 + 15 ■ 9 + 10 ■ 0 + 5 ■ 18 = 460. Literatura [1] J. F. Rayman, Transportation Problems (online), 3. 10. 2013. http://personal.maths.surrey.ac.uk/st/ J.F/chapter7.pdf [2] The Transportation Problem: LP Formulations (online), 3. 10. 2013. http://www.utdallas.edu/~scniu/ OPRE-6201/documents/TP1-Formulati on. pdf [3] Wikipedia: AMPL (online), 3. 10. 2013. http://en.wiki pedi a.org/wi ki/AMPL [4] AMPL (online), 3. 10. 2013. http://um.fnm.uni-mb.si/ti ki-download_ wi ki_attachment.php?attId=241&page=02. 11.2011\%3A\%20Linearni\%20program.\% 20Dual.\%20Si mpleksna\%20metoda _XXX 1 2 3 4 0 5 0 15 0 10 15 0 10 0 0 5 PRESEK 41 (2013/2014) 2 27