I

Dynamisk Programmering (D. P.) år en matematisk metod, som utvecklats fråmst av Richard Bellman, Rand Corporation, Californien, och som har visat sig vårdefull i vissa av de beslutssituationer som kan mota ett foretag. Som namnet antyder år det fråmst i s. k. „dynamiska⁴" situationer som D. P. år anvåndbar. En beslutssituation kailas dynamisk om beslut vid en tid påverkar beslutsunderlaget for efterfoljande beslut. Så till exempel år ett lagerproblem dynamiskt om inkop under forstå månaden t. ex. genom kvarvarande lager påverkar beslut om inkopskvantitet i den andra månaden (ordertillfålle antages foreligga endast en gang i månaden).

En del situationer har emellertid liknande struktur fastån de inte år i denna mening (tids-)dynamiska. Om det exempelvis galler att fordela en given (knapp) investeringsbudget på konkurrerande projekt år det tydligt att anslag till ett projekt påverkar besluten om anslag till de återstående. I detta fall motsvaras tidsperioderna (månaderna) av antalet investeringsprojekt och det kan dårfor vara låmpligt att anvånda ordet „steg" for dessa och andra motsvarande „uppdelningar" av en situation. D. P. år tillåmpbar på sådana fler-stegs beslutproblem, dock med den praktiska begrånsningen att antalet påverkande samband mellan stegen inte år alltfor stort.

Låt oss forst konstatera att eftersom ett visst beslut påverkar forutsåttningarnafor
andra beslut kan man i allmånhet inte nå basta totalbeslutgenom

1) Civilekonom, Foretagsekonomiska Forskningsinstitutet, Handelshogskolan i Stockholm.

beslutgenomatt helt enkelt fatta basta beslut med avseende på varje enskilt steg. Ett traditioneilt angreppssått for sådana fler-stegs problemår då att samtidigt se problemet i hela dess vidd, d. v. s. med hånsyntill alia steg (månader, investeringsprojekt . . „). Man får alltså en hel uppsåttning beslutsvariabler och val jer samtidigt basta varden for hela uppsåttningen. Ar det ett komplicerat problem kan ett sådant forfaringssåttvara praktiskt ogenomforbart. D. P. erbjuder hår ett annat angreppssått som dessutom kan ge vårdeful sidoinformation.

Grunden for D. P. år en mycket enkel men betydelsefull observation som jag skulle vil ja illustrera med ett enkelt exempel. Låt figur 1 symbolisera en tåvling dår det galler att i fem „dagsetapper" gå från start till mål. Delstråckans långd (mil) anges av motsvarande siffra och om alia år lika besvårliga ur andra synpunkter finns det all anledning att fundera en stund over hur man skall vålja for att nå den kortaste totalstråckan.

Om man varje dag traf far sitt val endast med hånsyn till den etapp som år nårmast forestående har man uppenbarligen ingen garanti for att nå basta totala resultat. I vart exempel skulle en sådan politik ge avståndet 25, (1-1-8 +3+s+ 8). En sådan politik skulle vara rationeli under fb'rutsåttning att man inte kånner till mer ån just den nårmast forestående „dagen". I figuren har vi i stållet en annan extrem situation; all relevant information år given.

1 detta avseende skulle vi få storre likheter med de beslutssituationer som moter foretagen genom att antaga någon mer mellanliggande informationsgrad t. ex. de nårmaste alternativen år kånda och betråffande tiden långre bort har man vissa forestållningar men inte fullståndig kunskap. Ett realistiskt inslag skulle också kunna vara att det går att skaffa information men endast med viss uppoffring.

Låt oss emellertid anvånda exemplet som det år och undersoka vad nytta vi kan ha av vår fullståndiga information. Jag foreslår att låsaren stannar någrå minuter och funderar forst over vilket som år den kortaste vågen i figur 1 och dårefter over sitt eget sått att angripa problemet.

Låt mig dårefter presentera fig. 2, som år ett forslag till losning. Jag vill också infora vissa symboler, som kanske forefaller tillkrånglade for det aktuella exemplet men som vi kan ha viss nytta av i fortsåttningen. Vi har tidigare talat om steg och i figuren menas med steg en forflyttning i horisontalled, det finns således i exemplet fem steg. For varje steg finns det olika nivåer, t. ex. efter start kan man nå nivå 1

genom att ta den overstå vågen (3 mil), nivå 2 genom den nåst overstå
vågen (1 mil) och så vidare. Dessa nivåer hånfor sig alia till samma steg.

Vi kan nu rulla upp problemet „bakifrån"²). Antag att vi endast har ett steg till målet. Beroende på från vilken nivå vi startar denna enstegsprocess blir det då 6, 5, 8, 10, 7, 9, 2 eller 5 mil till målet. I detta fall år det hela tåmligen sjålvklart men låt oss åndå infora en symbol for det kortaste avståndet till målet. Detta avstånd beror på, år en funktion av, nivån (dvs. utgångslåget) så vi tecknar fi(l) for det kortaste avståndet i ett en-stegsproblem, når man startar från nivå 1 (dvs. den overstå nivån). I exemplet ser vi alltså att fi(l) =5 och på motsvarande sått fi(2) =8, fi(3) =7 och fi(4) =2.

Det hår kan ju tyckas som onodigt trassel men vi kan i alia fall ha lite nytta av det, om vi fortsåtter analysen och antar att vi år två steg från målet, alltså i någon av de tre nivåer, varifrån vågarna 7, 5, 4, 3, 8, 3, 7, 12 utgår. Antag att vi år på den andra nivån och att vi vill ha tag på den kortaste vågen till målet, dvs. vi sokar f2(2). For att ta oss till steg 1 har vi nu fyra vågar att vålja mellan på 4, 3, 8 resp. 3 mil. Det år emellertid inte alldeles uppenbart, att vi skall gå någon af 3 mill vågarna, det beror ju en del på vad som kommer senare. Ett systematiskt tillvågagångssått vore att beråkna avståndet efter alia tånkbara vågar ånda fram till målet. Detta år emellertid onodigt besvar, kommer vi till steg 1, nivå 1, så vet vi sedan tidigare att minsta avståndet dårifrån till målet år fi(l)=s. For att vålja den basta vågen från steg 2, nivå 2, jåmfor vi alltså endast [4 + fi(l)], [3 + fi(2)L [8 + fi(3)] och [3 + fi(4)] dvs. [4 + s], [3 + B], [8 +7] och [3 + 2]. Den lågsta summen år 5, dvs. f2(2) =5, och vi skall alltså vålja den nedersta vågen. På motsvarande sått erhålles f2(1)f₂(1) =12 och fa(3) = 14.

Om vi nu betraktar en trestegsprocess kan vi ha nytta av våra olika fa( )-varden. Från steg 3, nivå 3, kan vi gå på två sått till steg 2. Antingen går vi på 3 mil till nivå 1 eller på 6 mil til nivå 2. Den kortaste vågen år den kortaste av (3 + fa(l)) och (6 + f2(2)) eller med annat uttryckssått fs(3) = min[3 + f2(l), 6+ f2(2)], dvs. fs(3) = min [15, 11] = 11.

På detta sått beråknar vi samtliga f3( )-varden och i steb 4 anvånder
vi dem for att erhålla f4( )-varden, vilka i sin tur anvåndes i steg 5,
det sista steget.

I figuren kan låsaren sjålv verifiera att ovriga f ( )-varden har beråknatspå

---

2) Man kan också tånkasig att med en likartad metod borja „framifrån". Detta kommer att diskuteras senare i uppsatsen.

råknatspådet sått som angivits ovan. VI har nu systematiskt lost
exemplet och kan kånna oss tåmligen såkra på att den kortaste vågen
verkligen år 20 mil (I+B +6+3+ 2).

Det hår exemplet år avsett att betona det naturliga och nåstan sjålvklara
i den „optimalitetsprincip", som dr. Bellman formulerat och som
år grundlåggande for dynamisk programmering.

„En optimal politik har den egenskapen att oavsett utgångslåget och
utgångsbeslut maste de f6l jånde besluten vara optimala med avseende
på det låge som uppkommit efter tidigare beslut".

Detta år naturligtvis att fatta som en nodvåndig men ej tillråcklig definition på optimal politik. For att återgå till exemplet. Om vi på ett eller annat sått hamnat i steg 3, nivå 4 (vart nårmaste val står alltså mellan vågarna 7 och 1 mil) så sager optinulitetsprincipen att den enda våg som kan tånkas ingå i en optimal våg (politik) från start till mål år den som ger avståndet f3(4) dvs. 12 mil från steg 3 nivå 4 till målet. Dåremot år det inte alls såkert att denna våg kommer att ingå i den kortaste vågen från start till mål for det år kanske over huvud inte lonsamt att passera steg 3, nivå 4. Kommer vi emellertid dit behover vi alltså inte fundera over alia de 12 tånkbara sått att gå dårifrån till målet, utan behover endast ta hånsyn till den våg som ger h(^).

Ett hånsynstagande till denna optimalitetsprincip kan alltså våsentligt
forminska problemets dimensioner. Från startpunkten och ånda fram till
målet finns det inte mindre an 84 olika vågar att ta hånsyn till.

Med de skisserade angreppssåtten år det i stållet endast fyra vågar aktuella 3+ f4(l), l+ f4(2) och 6+ f4(3).f₄(3). Visserligen kraves for beråkning av U( ) en tidigare beråkning av h( ), som i sin tur bygger på fa( ) och fi( ) men det sammanlagda antalet vågar som man maste ta hånsyn till år åndå inte fler an 34, och varje sådan jåmforelse omfatter endast en vågstråcka plus ett f( )-varde. Vi skulle kunna uttrycka det så, att dimensionen i problemet har reducerats, vilket visserligen medfort flera delproblem men som dock tillsammantagna blir våsentligt enklare ån det stora totalproblemet.

Det exempel som vi hittilis diskuterat var konstruerat for att visa hur naturlig en tillåmpning av optimalitetsprincipen år. Andra exempel skall i fortsåttningen behandlas, dår man inte lika lått av sig sjålv „kommer på" detta betraktelsesått och dår alltså D. P. verkligen kommer med något nytt.

Det har tidigare nåmnts att D. P. skulle ge sidoinformation. Tillåmpatpå
vart exempel år meningen med detta yttrande att sedan man har
lost problemet på det hår diskuterade såttet kånner man forutom den

basta vågen från start till mål också den basta vågen från varje etappandpunktoch till målet. Om man alltså skulla råka hamna i steg 4, nivå I, behovs inga nya funderingar for att finna den kortaste vågen dårifrån och till målet. Detta kanske inte syns sårdeles betydelsefullt eftersom vi ha antagit att vi helt och hållet kan kontrollera fården. I stållet for den hår genomforda baklångsråkningen hade vi kunnat genomfora ett liknande resonemang framifrån. Såsom sidoinformation hade man då fått reda på de kortaste avstånden från starten och till alia etappåndpunkter.Vilket tillvågagångssått som år bast beror på det praktiska råknandetoch vilken slags sidoinformation man år intresserad av.

Jag har valt att gå bakifrån dels dårfor att det mojligen år mindre intuitivt klart och dårfor fordrar omsorgsfullare behandling men framfor allt dårfor att det år detta angreppssått man vanligen moter i litteraturen om D. P. Detta år nog i sin tur till stor del beroende på att man ofta sysslar med stokastiska processer dår man alltså inte med såkerhet vet foljden av ett beslut och dår således det år mycket vårdefullt att som sidoinformation få den optimala politiken for varje tånkbart låge.

Innan vi går vidare låt mig endast saga att D. P. som matematisk teori naturligtvis inte sysselsåtter sig med ett evigt upprepande av denna princip. Våsentliga teoretiska frågor ror grånsvårdet av f_n( ) når antalet steg (n) går mot oåndligheten och vidare vissa strukturegenskaper hos losningen. Man kommer hår in på variationskalkylens område och for en i matematiskt hånseende otrånad låsare år det svårforcerad terrång.

Standardverket inom området år „Dynamic Programming" av Richard Bellman³) och tillsammans med Stuart Dreyfus kommer Bellman småningom också att publicera en annan framstållning mer låmpad for lekmån.

II

I detta avsnitt skall ett mycket enkelt lagerproblem angripas med den metod som presenterats i foregående avsnitt. Diskussionen av detta exempel år endast avsett som en ytterligare illustration till hur D. P. kan anvåndas, och exemplet presenteras utan andra anspråk.

Vi antar att ett foretag har tillfålle att placera order for en viss produkt endast den forstå dagen varje kvartal och att man nu står infor problemet att beståmma sin inkopspolitik under det nårmaste året. Lagret år tomt vid årets bor jan och man 6'nskar inte heller ha något kvar vid årets slut.

---

3) Richard Bellman: „Dynamic Programming", Princeton University Press, 1957.

Behovet under de kommande fyra kvartalen år kant. Alia leveranser
(såvål in som ut) antages ske omedelbart, alltså den forstå dagen varje
kvartal.

Vi infor nu foljande symboler:

x antalet produktenheter i lager innan annu den nya ordern inkommit.

y antalet produktenheter i lager sedan den nya ordern inkommit,
men innan uttag skett for innevarande kvartal.

s behovet under innevarande kvartal
(5, 7, 4 och 6 enheter under forsta, andra, tredje resp fjarde
kvartalen).

p priset per enhet. Kvalitetsrabatt erhålles på foljande sått: Vid samtidigt kop av 1-4 enheter år priset = 100 Vid samtidigt kop av 5-8 enheter år priset = 95 Vid samtidigt kop av 9- enheter år priset — 90

c kostnad att placera en order, c == 10

k lagerkostnad per enhet f kvartal, k = 10.
k „verkar" på kvantiteten (y-s-s).

fn(x) kostnader for en n-stegsprocess med utgångslager =xom optimal
inkopspolitik kommer till anvåndning.

I exemplet galler vidare att behov av produktion maste motas, lagerkapaciteten
år begrånsad till 12 enheter (12^y^s) samt (y^x).

Vi far nu foljande samband (med de restriktioner som framgar ovan)
ri\ min r/ > . ,1/ \-i varvid sista termen blir noil efterfi(x)
= "un Lp(y-^x) +c+ k(y—s)], „
* som lagret vid arets slut ar noil
fn(x) =f» [p(y—x) +c+ k(y—s) + fn-i (y~s)]
for n = 2

Dessa samband kan utlåsas så att den lågsta kostnaden for en en-stegsprocess år summan av inkopskostnad, orderkostnad och lagerkostnad når utgångslagret, y„ har faststållts optimalt. For en n-stegprocess tillkommer utover motsvarande kostnader for den omedelbart forestående perioden åven den optimala kostnaden for en (n-l)- med utgångslagret (y_—s) vilket alltså blir beståmt i och med att y faststålles.

I ett sådant system av ekvationer kan man inte losa fn(x) direkt eftersomden

somdeninte år uttryckt i explicit form utan innehåller en term fn-i(x) vilken i sin tur år ett minimum av en funktion av x oc'h y. Man får i stållet borja med att losa det y-vårde for vilket parantesen i uttrycket for fi(x) når sitt minimum. Detta gor det mojligt att uttrycka fi(x) i explicit form och detta uttryck såtter man så in i den parantes som forekommer i uttrycketfor fs(x). Minimivårdet med avseende på y i denna parantes loses vilket ger fs(x) i explicit form som man alltså kan såtta in i parantesen for f3(x) O.S.V.

Detta år i princip det råknesått som vi anvånde oss av i foregående exempel når vi for varje steg råknade upp alia tånkbara alternativ och valde det kortaste. I andra problem kan man med analytiska metoder losa de successiva funktionerna ft(x), f2(x) o.s.v. Aven i foljande exempel skall vi emellertid anvånda oss av uppråkning vilket forutom pedagogiska fordelar i just detta exempel dessutom torde vara enklast ur råkneteknisk synpunkt.

Vi anvander oss av de foljande fyra tabellerna och borjar som tidigare bakifran med att berakna vilka kostnader vi har i fjarde kvartalet for olika lagersituationer (varden pa x). Eftersom vi maste mota kvartalets behov maste y vara minst 6 och uppenbarligen vill vi inte heller overstiga denna kvantitet. Darfor kan det uppenbarligen inte vara lonsamt med v>6, vi tabulerar darfor kostnaderna i fjarda kvartalet for y -= 6" och x = 0, 1, 2 6.

I nasta tabell noterar vi motsvarande kostnader for de tva sista kvartalen.Denna
tabell utfores for y = 4, 5 .... 10 och x = 0, 1 .... 5,

---

4) f}(x) år enligt ovanstående den lågsta kostnaden vid givet x-varde, y år det varde på y som ger fj(x). I denna tabeli år dessa kolumner tåinligen onodiga, men de med(ages for likformighet med ovriga tabeller.

(behov maste motas, lagerkapaciteten tillåter ej att mer an (12-7) fores over från foregående kvartal). For att underlåtta en overblick over tabellenhar två kostnader skrivits i varje cell. Den ovre år summan av de tre forstå termerna i nedanstående uttryck, den undre år totalsumman alltså inkluderande fi(y-s), dår alltså den sista termen erhålles från tabell 1. Den lågsta kostnaden for varje x-varde år f2(x) och har i tabellen markeratsoch utforts i sårskild kolum.

Tabellen visar nu att om vi exempelvis har 1 enhet i lager vid bor jan av tredje kvartalet år det billigast att beordra 9 nya enheter som då råcker for både tredje och fjårde kvartalen. Ar lagret dåremot på 2 enheter (x = 2) blir det billigast att kopa 2 enheter till tredje kvartalet och f6l jaktligen 6 enheter till sista kvartalet.

I foljande tabell for vi pa raotsvarande satt fram berakningarna att
omfatta de tre sista kvartalen. Aktuella varden pa x och y for denna
tabell ar: x = 0, 1 7, y = 7, 8 12.

Vi har nu underlag for att uppråtta den sista tabellen omfattande samtliga fyra kvartal. Eftersom man inte hade några produkter i lager vid årets borjan behover vi nu endast beråkna kostnaderna forenade med \ = 0 och y-varden från 5 t.o.m. 12.

Av tabellen ser vi alltså, att den billigaste inkopspolitiken medfor en kostnad av 2.105 och innebår att en order på 5 enheter placeras for forstå kvartalet. Detta leder till att vi inte har några produkter i lager vid andra kvartalet (x = 0), och i tabell 3 ser vi att det i ett sådant fall år billigast att kopa 11 nya enheter. Kvartalets behov år endast 7 enheter,

och av tabell 2 framgår att med 4 som in gående lager i tredje kvartalet
år det fordelaktigast att inte placera någon ny order. Detta leder till
att vi i fjårde kvartalet får kopa de 6 enheter som då behovs (tabell 1).

Enligt exemplets antaganden startade man processen med tomma lager, och exemplet har losts for detta fall. En fordel med vart s att att attackera problemet bakifrån år emellertid, att vi nu mycket lått kan bygga ut tabell 4 och se den optimala lagerpolitiken som en funktion av ingående lager. Låsaren kan sjålv verifiera, att med en enhet i lager den lågsta kostnaden for de fyra kvartalen år 2.025. Vilken inkopspolitik svarar mot denna kostnad?

Det kan också vara vart att påpeka att den inkopspolitik man planerar att fol ja under året kan modificeras, om en forandring skett i de forutsåttningar beråkningen baserats på. Om man inte behover binda sig for mer ån ett kvartal, kan en sådan anpassning ske snabbt. Vi har nu nytta av den sidoinformation, som vår beklångesgång givit upphov till. Har till exempel endast 2 enheter behovts under forstå kvartalet, år det alltså 3 enheter kvar i lager. Vi kan nu direkt se från tabell 3, att i denna nya situation kan de tre f6l j_ånde kvartalen klaras till en lågsta kostnad av 1.365 om vi koper 9 nya enheter andra kvartalet. Under detta kvartal behovs 7 enheter, och det blir alltså 5 over till tredje kvartalet, då ingen ny order placeras, utan i sista kvartalet inkopes så många enheter att behovet tillfredsstålles. På detta sått har losningen en stor flexibilitet, och detta år naturligtvis en mycket vårdefull egenskap.

III

Det har tidigare antytts att D.P. kan vara en anvåndbar metod också i sådana dynamiska problem som har slumpmåssig (stokastisk) karaktår. Det år lått att konstruera en stokastisk variant av exemplet i foregående avsnitt men for att inte forlånga framstållningen skall jag i stållet endast ange och kommentera en D.P.-formulering av en stokastisk lagermodel l⁵). Forutom tidigare anvånda beteckningar introducera vi nu:

<p(s) ds = sannolikheten att behovet ligger mellan s och s+ds

k(z) = kostnaden for en regnljar order pa z enheter

p(z) = kostnaden for en expressorder pa z enheter, dvs. bristkostnaden.

fn(x) = matematisk forvantan av de totala kostnaderna for en
n-stegs process som startar med x enheter i lager och under
forutsattning av optimal orderpolitik.

---

5) Formuleringen ar håmtad från Bellmann „Dynamic Programming", s. 154.

Vi erhåller nu f6l jånde rekursiva samband:

och

for n = 2, 3

Som synes galler det att i en en-stegs process soka den lagerstorlek, y, som minimerar summan av (1) kostnaderna for periodens inkop, (y-x) enheter, och (2) den forvåntade bristkostnaden. Denna sista kostnad får vi genom att våga kostnaden for varje tånkbar bristsituation, s>y, med sin sannolikhet och summera dessa vågda tal. Denna summering år vid kontinuerlig fordelingsfunktion for behovet uttryckt genom integralen i uttrycket for fi(x).

fn(x) ar den lagsta, med avseende pa y, summan av fyra termer. De tva forsta ar identiska med de for en enstegs process och uttrycker kostnaderna for den omedelbart forestaende perioden. Dartill kommer den forvantade kostnaden for en (n—l)-stegs process med optimal orderpolitik.

00
Med sannolikheten ) (s)ds kommer efterfragan under den omedely

bart forestaende perioden att overstiga lagret, y, och alltsa lamnas lagret
tomt till foljande perioder. Den beraknade kostnaden for en sadan
situation ar fn-i(0)fn-i(0) och denna kostnad ar alltsa i tredje termen vagd med
sannolikheten att den skall uppkomma. I fjarde termen ar slutligen den
forvantade kostnaden for de fall da orman gar in i (n-l)- processen
med ett faktiskt lager.

Rekursiva samband av ovanstående typ kan losas genom att man loser
fi(x) i explicit form, dårefter f2(x) osv.

For vissa fall år det också mojligt att direkt losa det grånsvårde f(x)
mot vilket fn(x) går då n-*-«?

Dynamisk programmering har ett stort tillåmpningsområdc i många av de problem som uppstår i ett foretags ekonomiska verksamhet. Som ovan illustrerats med ett enkelt exempel kan vissa inkops- och lagerproblemattackeras med denna teknik. Vid Rand Corporation har man programmerat en computer, IBM 704, for en speciell lagermodell. Investeringsproblem,anskaffning

steringsproblem,anskaffningav utrustning, har också formulerats med D.P. liksom åven problem då det galler att fordela knappa resurser mellan konkurrerande åndamål. Produ'ktionsproblem av den typ som kan angripasmed linjår programmering kan behandlas med D.P. i de fall då antalet steg, produktionsplaneringsperioder, år stort och restriktionerna inom varje steg år relativt få. Bellman har åven formulerat flerstegs „games" med D.P.

Bland praktiska tillåmpningar kan nårnnas ett produktionsplaneringsproblem vid en avdelning av Lockheed Aircraft Corporation⁶). Det gållde att for skiftande produktionsvolym anpassa anstållning, permittering, forflyttning mellan avdelningar, overtidsarbete och legoproduktion, så att produktionsplanen kunde uppfyllas till lågsta kostnad. De dynamiska aspekterna kommer in dår igenom att beslut om t. ex. nyanstållning under en period påverkar mojligheterna till reguljår produktion under foljande perioder.

Inkops- och lagerproblem har också i praktiken behandlats med D.P. Ett OR-team från Case Institute of Technology har formulerat beslutsregler for ett foretag som hade att kopa råvaror i en marknad med kraftigt fluktuerande priser₇).

Att låmna litteraturreferenser inom detta område år lått. Bellman's „Dynamic Programming" år den fullståndiga dominerande framstållningen. Under de senare åren har det också forekommit en hel del uppsatser i facktidskrifter. Detta år inte platsen att presentera en forteckning over dessa utan den intresserade låsaren rekommenderas att titta igenom i forstå hand Management Sciences, Operations Research och Naval Logistics Quarterly.

---

6) Marvin Luther „Minimum-Risk Dynamic Programming of Industrial Manpower Load", presenterad vid ORSA:s mote i Boston 19.58.

7) Rapporterat i stencilform av M. W. Sasieni, Case Institute of Technology, 1958.