Luku 7

Diskreettiä optimointia

7.1 Bellmanin optimaalisuusperiaate

Tarkastellaan epätyhjää joukkoa X paikkoja, joita yhdistää verkko teitä, rautateitä, laiva- ja lentoreittejä. Merkitään järjestettyä monikkoa (x_{0}, x_{1}, …, x_{n}) ∈ X^{n+1}, n ∈ IN, lyhyesti x_{0}, x_{1}, …, x_{n}, ja sanotaan sitä poluksi, joka alkaa pisteestä x_{0} ja joka kulkee pisteiden x_{1}, …, x_{n−1} kautta pisteeseen x_{n}. Olkoot kuvaukset

c, K: X × X →] − ∞, ∞].

Luku c(x, y) esittää matkan pisteestä x ∈ X pisteeseen y ∈ X aiheuttamia kustannuksia. Jos c(x, y) < 0, niin matka tuottaa enemmän kuin maksaa (maisemien katselu antaa mielihyvää, matkalla kerätään marjoja tai otetaan talteen yliajetut rusakot). Jos pisteestä x ei pääse pisteeseen y, asetetaan c(x, y) = ∞. Aika on tässä mallissa diskreetti ja parametri n viittaa ajanhetkeen. Tällöin c(x, y) = ∞ pitää sisällään sen, että yhdellä ajan askeleella ei ehditä matkustaa paikasta x paikkaan y. Paikallaan olemisesta ei tule kustannuksia, jos

c(x, x) = 0, K(x, x) = 0 kaikilla x ∈ X.  (7.1)

Matkan kokonaiskustannuksia pitkin polkua x_{0}, x_{1}, …, x_{n}, n = 1, 2, …, esittää

C(x_{0}, x_{1}, …, x_{n}; y) = ∑_{i=1}^{n} c(x_{i−1}, x_{i}) + K(x_{n}, y),  (7.2)

missä K(x, y) esittää sakkoa, joka tulee siitä, että paikkaan y ∈ X ei saavuttu. Asetetaan

C(x_{0}, y) = K(x_{0}, y).  (7.3)

Jos K(x, y) ≡ 0, ei ole väliä, mihin pisteeseen matka päättyy. Jos

K(x, y) = \{ \begin{matrix}∞, & jos x ≠ y, \\ 0, & jos x = y, \end{matrix}  (7.4)

niin kokonaiskustannus (7.2) on äärellinen vain jos x_{n} = y eli sakko (7.4) pakottaa saapumaan pisteeseen y ∈ X. Toisaalta (7.1) sallii saapua pisteeseen y vähemmällä kuin n:llä askeleella ilman että kokonaiskustannukset siitä kasvavat. Luonteva optimointitehtävä on siis seuraaava:

(P_{∞}) Olkoot x, y ∈ X annettuja. Hae sellaiset n ∈ IN ja (x_{0}, x_{1}, …, x_{n}) ∈ X^{n+1}, joille

C(x_{0}, x_{1}, …, x_{n}; y) = inf {C(z_{0}, z_{1}, …, z_{m}; y) |
m ∈ IN, (z_{0}, z_{1}, …, z_{m}) ∈ X^{m+1}, z_{0} = x}. (7.5)

Tässä optimointitehtävässä ajan askelten määrää ei ole kiinnitetty. Jos se kiinnitetään, niin saadaan seuraava tehtävä:

(P_{n}) Olkoot n ∈ IN ja x, y ∈ X annettuja. Hae sellainen (x_{0}, x_{1}, …, x_{n}) ∈ X^{n+1}, jolle

C(x_{0}, x_{1}, …, x_{n}; y) = inf {C(z_{0}, z_{1}, …, z_{n}; y) |
(z_{0}, z_{1}, …, z_{n}) ∈ X^{n+1}, z_{0} = x}.  (7.6)

Huomaamme, että jos joukko X on äärellinen, niin infimumia haetaan äärellisen monen reaaliluvun ja luvun ∞ joukosta ja siten se saavutetaan. Tehtävällä (P_{n}) on tällöin ratkaisu.

Määritellään kuvaukset F_{n}, F_{∞}: X × X → [−∞, ∞], n ∈ IN,

F_{n}(x, y) = inf {C(z_{0}, z_{1}, …, z_{n}; y) | z_{0}, z_{1}, …, z_{n} ∈ X^{n+1}, z_{0} = x},
F_{∞}(x, y) = inf {C(z_{0}, z_{1}, …, z_{m}; y) |
m ∈ IN, z_{0}, z_{1}, …, z_{m} ∈ X^{m+1}, z_{0} = x},

Lause 7.1.1 Olkoot x, y ∈ X ja c(x, x) = 0. Tällöin lukujono (F_{n}(x, y)) on vähenevä ja

F_{∞}(x, y) = inf{F_{n}(x, y) | n ∈ IN}.

Todistus. Harjoitustehtävä. m.o.t.

Seuraava lause on Bellmanin optimaalisuusperiaate.

Lause 7.1.2 Olkoot x, y ∈ X ja n ∈ IN. Tällöin pätee

F_{0}(x, y) = K(x, y),  (7.7)
F_{m}(x, y) = inf{c(x, x′) + F_{m−1}(x′, y) | x′ ∈ X}, m = 1, 2, …, n. (7.8)

Todistus. Ensimmäinen yhtälö seuraa suoraan C(x_{0}):n määritelmästä. Kaksi infimumia saadaan ottaa missä järjestyksessä hyvänsä tai yhtäaikaa. Siksi

F_{m}(x, y) = inf { ∑_{j=1}^{m} c(z_{j−1}, z_{j}) + K(z_{m}, y) | z_{1}, …, z_{m} ∈ X^{m}, z_{0} = x}

= inf_{z_{1}∈X} inf {c(x, z_{1}) + ∑_{j=2}^{m} c(z_{j−1}, z_{j}) + K(z_{m}, y) | z_{2}, …, z_{m} ∈ X^{m−1}}

= inf_{z_{1}∈X}{c(x, z_{1}) + F_{m−1}(z_{1}, y)}.

m.o.t.

Huomaa, että Bellmanin optimaalisuusperiaate mahdollistaa optimointitehtävän rekursiivisen ratkaisemisen.

7.2 Optimaalisuusyhtälö ja säätöteoriaa

Tarkastelemme tässä jaksossa diskreettejä säätöteoreettisia optimointiongelmia, jollainen on esimerkiksi talon lämmityksen säätäminen niin, että lämpötilajakauma talon sisällä on mahdollisimman lähellä haluttua ja lämmityskustannukset jäävät samalla mahdollisimman pieniksi. Tällöin tunnistetaan kaksi eri muuttujaa: säätö (lämmittimen teho) ja tila (lämpötila). Edellisen arvoa ajanhetkellä t merkitään tavallisesti u(t) ja jälkimmäisen x(t). Aika on yhä diskreetti, joten merkitsemme lyhyesti u_{n} ja x_{n} pidempien ilmaisujen u(t_{n}) ja x(t_{n}) sijasta.

Yleistetään hieman Bellmanin optimaalisuusperiaatetta. Olkoot epätyhjät joukot U_{0}, U_{1}, …, U_{n−1}, n ∈ IN, sekä

G: U_{0} × U_{1} × … × U_{n−1} → [−∞, ∞].  (7.9)

Määritellään kuvaukset

G_{j}: U_{0} × U_{1} × … × U_{j−1} → [−∞, ∞], G_{j}(u_{0}, u_{1}, …, u_{j−1})

= inf {G(u_{0}, u_{1}, …, u_{n−1}) | u_{k} ∈ U_{k}, k = j, j + 1, …, n − 1}.

Lause 7.2.1 (Optimaalisuusyhtälö). Jokaiselle j = 0, 1, …, n − 1 on voimassa

G_{j}(u_{0}, u_{1}, …, u_{j−1}) = inf_{u_{j}∈U_{j}} G_{j+1}(u_{0}, u_{1}, …, u_{j}),  (7.10)
G_{n}(u_{0}, u_{1}, …, u_{n−1}) = G(u_{0}, u_{1}, …, u_{n−1}).  (7.11)

Todistus. Tämä todistetaan samoin kuin lause 7.1.2. m.o.t.

Olkoon n ∈ IN ja epätyhjät joukot U_{0}, U_{1}, …, U_{n−1}. Sanomme kuvausta j ↦ u_{j} ∈ U_{j}, j ∈ {0, 1, …, n − 1} säätömuuttujaksi. Olkoon X epätyhjä joukko; sanomme sitä tila-avaruudeksi. Kuvausta j ↦ ω_{j}, j ∈ {0, 1, …, n}, sanotaan säätömuuttujaan u liittyväksi tilamuuttujaksi, jos

(i) optimaalinen u_{j} riippuu vain olioista ω_{j} ja j kaikilla j = 0, 1, …, n,

(ii) ω_{j+1} riippuu vain olioista ω_{j}, j ja u_{j} kaikilla j = 0, 1, …, n − 1,

(iii) sekä ω_{j} ∈ X kaikilla j = 0, 1, …, n.

Olkoot kuvaukset a_{j}: X × U_{j} → X , g_{j}: X × U_{j} →] − ∞, ∞] ja K: X →] − ∞, ∞], j = 0, 1, …, n. Oletamme, että kuvaus j ↦ x_{j} toteuttaa

x_{j+1} = a_{j}(x_{j}, u_{j}), j = 0, 1, …, n − 1.  (7.12)

Tämä vastaa talon lämmittämisen tapauksessa lämpöyhtälöä, joka määrää, miten lämpotila x muuttuu kullakin lämmitysteholla u_{j}. Mekaniikan piiriin kuuluvissa sovellutuksissa yhtälöä (7.12) sanotaan liikeyhtälöksi; sanomme sitä yleisesti tilayhtälöksi. Minimoimme lauseketta

C = ∑_{j=0}^{n−1} g_{j}(x_{j}, u_{j}) + K(x_{n})  (7.13)

säätömuuttujan j ↦ u_{j} suhteen. Merkitään

F_{j}(x_{j}) = F_{j}(x_{0}, x_{1}, …, x_{j}, u_{0}, u_{1}, …, u_{j−1}) =  (7.14)

= inf { ∑_{k=j}^{n−1} g_{k}(x_{k}, u_{k}) + K(x_{n}) | u_{k} ∈ U_{k}, k = j, j + 1, …, n − 1}.

Tämä on on pienin mahdolinen tuleva kustannus, kun takana on säätö- ja tilamuuttujien historia hetkestä k = 0 hetkeen k = j.

Lause 7.2.2 Olkoot n ∈ IN, epätyhjät joukot U_{0}, U_{1}, …, U_{n−1} ja X sekä x_{0} ∈ X. Olkoon tilayhtälö (7.12) voimassa ja säätömuuttujan u optimaalisuuden määrätköön kaavan (7.13) kustannusfunktio. Tällöin pätee:

(i) Optimaalinen u_{j} riippuu vain olioista j ja x_{j}.

(ii) j ↦ x_{j}, {0, 1, …, n} → X, on säätömuuttujan j ↦ u_{j} tilamuuttuja.

(iii) Lausekkeet F_{j}(x_{j}) riippuvat vain olioista j ja x_{j} eli

F_{j}: X → [−∞, ∞], j = 0, 1, …, n.

(iv) Kaikilla j = 0, 1, …, n − 1

F_{j}(x_{j}) = inf_{v∈U_{j}} (g_{j}(x_{j}, v) + F_{j+1}(a_{j}(x_{j}, v))),  (7.15)
F_{n}(x_{n}) = K(x_{n}).  (7.16)

Todistus. Todistus on induktiivinen. Määritelmän (7.14) mukaan F_{n}(x_{n}) = K(x_{n}) eli (7.16) pätee. Samalla pätee, että F_{n}(x_{0}, …, x_{n}, u_{0}, …, u_{n−1}) pelkistyy vain oliosta x_{n} riippuvaksi. Olkoon tämä pelkistyminen voimassa oliolle F_{k+1}(x_{0}, …, x_{k+1}, u_{0}, … u_{k}), kun k ∈ {0, 1, …, j − 1}, missä j ≤ n. Optimaalisuusyhtälö (7.10) sanoo, että

F_{k}(x_{k}) = inf_{u_{k}∈U_{k}} (g_{k}(x_{k}, u_{k}) + F_{k+1}(a_{k}(x_{k}, u_{k}))).  (7.17)

Lauseke, josta infimum otetaan, riippuu vain olioista x_{k}, u_{k} ja k. Siten infimum riippuu vain olioista x_{k} ja k. Näin tämä pelkistyminen toteutuu myös oliolle F_{k}(x_{0}, …, x_{k}, u_{0}, …, u_{k−1}). Induktioperiaatteen nojalla se pätee kaikille k = n, n − 1, …, 0. Täten (iii) ja (iv) pätevät. Yhtälöstä (7.17) nähdään, että optimaalinen u_{k} riippuu vain olioista x_{k} ja k eli (i) pätee. Tilayhtälön nojalla x_{k+1} ∈ X riippuu vain olioista x_{k}, u_{k} ja k, joten k ↦ x_{k} on tilamuuttuja eli (ii) pätee. m.o.t.

7.3 Harjoitustehtäviä

1. Olkoon X = {a, b, c}. Määrittele sellaiset c, K: X × X →] − ∞, ∞], että

(a) F_{∞}(a, c) = −∞,

(b) F_{∞}(a, c) = ∞,

(c) F_{∞}(a, c) = 10 ja F_{∞}(c, a) = 1.

2. Todista lause 7.1.1.

3. Olkoon X = {α, β, δ, γ} ja c, K: X × X →] − ∞, ∞],

(c(η, ξ)) = ( \begin{matrix}0 & 1 & 3 & 20 \\ 2 & 0 & 5 & 7 \\ 1 & 5 & 0 & 2 \\ 2 & 7 & 1 & 0 \end{matrix} ) , K(η, ξ) = \{ \begin{matrix}∞, & jos η ≠ ξ, \\ 0, & jos η = ξ. \end{matrix}

Selitä, miksi matriisi (c(η, ξ)) voi olla epäsymmetrinen. Hae Bellmanin optimaalisuusperiaatteen avulla optimaalinen polku pisteestä α pisteeseen γ.

4. Olkoon n ∈ IN ja tilayhtälö muotoa

x_{k+1} = a_{k}(x_{k}, x_{k−1}, u_{k}), k = 1, 2, …, n,

missä a_{k}: IR^{3} → IR. Osoita, että k ↦ (x_{k}, x_{k−1}) on tilamuuttuja, kun optimaalisuuden määrää kaavan (7.13) kustannusfunktio.

7.3.1 Diskonttaus

Olkoon β > 0. Tarkastellaan diskontattua^{1} kustannusfunktiota

C = ∑_{j=0}^{n−1} β^{j}g_{j}(x_{j}, u_{j}) + β^{n}K(x_{n}).  (7.18)

Määritellään oliot F_{j}(x_{j}), j = 0, 1, …, n, uudestaan:

F_{j}(x_{j}) = F_{j}(x_{0}, x_{1}, …, x_{j}, u_{0}, u_{1}, …, u_{j−1}) =  (7.19)

= inf { ∑_{k=j}^{n−1} β^{k−j}g_{k}(x_{k}, u_{k}) + β^{n−j}K(x_{n}) | u_{k} ∈ U_{k}, k = j, j + 1, …, n − 1}.

Tämä on on pienin mahdollinen tuleva diskontattu kustannus, kun takana on säätö- ja tilamuuttujien historia hetkestä k = 0 hetkeen k = j. Huomaa, että jos β = 1, niin tilanne on sama kuin lauseen 7.2.2 tapauksessa.

Lause 7.3.1 Olkoot n ∈ IN, β > 0, epätyhjät joukot U_{0}, U_{1}, …, U_{n} ja X sekä x_{0} ∈ X. Olkoon tilayhtälö (7.12) voimassa ja säätömuuttujan u optimaalisuuden määrätköön kaavan (7.18) kustannusfunktio. Tällöin pätee:

(i) Optimaalinen u_{j} riippuu vain olioista j ja x_{j}.

(ii) j ↦ x_{j}, {0, 1, …, n} → X, on säätömuuttujan j ↦ u_{j} tilamuuttuja.

(iii) Lausekkeet F_{j}(x_{j}) riippuvat vain olioista j ja x_{j} eli

F_{j}: X → [−∞, ∞], j = 0, 1, …, n.

(iv) Kaikilla j = 0, 1, …, n − 1

F_{j}(x_{j}) = inf_{v∈U_{j}} (g_{j}(x_{j}, v) + βF_{j+1}(a_{j}(x_{j}, v))),  (7.20)
F_{n}(x_{n}) = K(x_{n}).  (7.21)

Todistus. Harjoitustehtävä. m.o.t.

7.4 Optimaalinen kuluttaminen ja sijoittaminen

Tarkastellaan tapausta, jossa yksi henkilö voi kuluttaa tai sijoittaa rahansa. Kuluttaminen tuottaa mielihyvää, sijoitus korkotuloja, joilla voidaan kuluttaa. Henkilön tavoitteena on maksimoida diskontattu mielihyvänsä. Olkoot n ∈ IN, ν ∈]0, 1[ ja α, β > 0. Tila-avaruus olkoon IR ja tilamuuttuja j ↦ x_{j}; sen arvo x_{j} esittää henkilön rahavarojen määrää hetkellä t_{j}. Aika on siis jälleen diskreetti. Säätömuuttuja on j ↦ u_{j} ∈ U_{j} ja sen arvo u_{j} esittää hetkellä t_{j} kulutetun rahan määrää. Kuluttaa ei voi velaksi, joten u_{j} ≤ x_{j}. Toisaalta tuottaminenkaan ei käy päinsä, joten u_{j} ≥ 0. Täten U_{j} = [0, x_{j}]. Raha on sijoitettu pankkitilille, jonka korko^{2} on α − 1, joten tilayhtälö on

x_{j+1} = α(x_{j} − u_{j}), j = 0, 1, …, n.  (7.22)

1Diskontto on lainan ennakkokorko, joka maksetaan ennen lainan erääntymistä ns. diskonttauspäivänä ja jonka laskemisessa korko lasketaan diskonttaus- ja erääntymispäivän väliseltä ajalta. Esimerkki: 10 000 markan laina, jonka vuosikorko on 10 %, otetaan vuodeksi 1.1., koronmaksu- ja diskonttauspäivä ovat 30.6. Tällöin 30.6 maksetaan korko 1000 mk, josta 500 mk on taannehtivasti maksettava alkuvuoden korko ja loput 500 mk on ennakoiden (diskontaten) maksettava loppuvuoden korko.

2Kyseessä on reaalikorko, jolloin inflaatio voi tehdä siitä negatiivisen.

Kuluttajan mielihyvää hetkellä t_{j} esittää g(u_{j}). Oletamme, että

g : [0, ∞[→ IR, g(r) = r^{1−ν}.  (7.23)

Tällöin mielihyväfunktio on alenevan rajamielihyvän lain mukaisesti kovera. Hetkellisten mielihyvien summan sijasta maksimoidaan diskontanttujen mielihyvien summaa

∑_{j=0}^{n−1} β^{j}g(u_{j}) + β^{n}K(x_{n}),  (7.24)

missä K(x_{n}) esittää mielihyvää loppuhetkellä olevasta rahamäärästä. Alenevan rajamielihyvän lain vuoksi — ja laskujen helpottamiseksi — oletamme, että

K: [0, ∞[→ IR, K(r) = A_{n}r^{1−ν},  (7.25)

missä A_{n} > 0 on vakio. Meillä on maksimointitehtävä. Mutta koska kustannusfunktiossa kaikki yhteenlaskettavat ovat äärellisiä, niin yhtäpitävä minimointitehtävä on hakea olion

−( ∑_{j=0}^{n−1} β^{j}g(u_{j}) + β^{n}K(x_{n})) = ∑_{j=0}^{n−1} β^{j}( − g(u_{j})) + β^{n}( − K(x_{n})) (7.26)

minimiä. Koska jokaiselle reaalilukujoukolle B pätee sup B = − inf −B, niin lauseen 7.3.1 nojalla optimaalisuusyhtälöt ovat

−F_{j}(x_{j}) = sup_{0≤v≤x_{j}} (v^{1−ν} − βF_{j+1}(α(x_{j} − v))), j = 0, …, n − 1, (7.27)
−F_{n}(x_{n}) = K(x_{n}),  (7.28)

missä jokaiselle j = 0, 1, …, n

−F_{j}(x_{j}) = −F_{j}(x_{0}, x_{1}, …, x_{j}, u_{0}, u_{1}, …, u_{j−1}) =  (7.29)

= − inf { ∑_{k=j}^{n−1} −β^{k−j}g(u_{k}) − β^{n−j}K(x_{n}) | u_{k} ∈ U_{k}, k = j, j + 1, …, n − 1}

= sup { ∑_{k=j}^{n−1} β^{k−j}g(u_{k}) + β^{n−j}K(x_{n}) | 0 ≤ u_{k} ≤ x_{k}, k = j, …, n − 1}.

Optimaalisuusyhtälöiden ratkaisuna saadaan (harjoitustehtävä), että

−F_{j}(x_{j}) = A_{j}x_{j}^{1−ν}, u_{j} = \frac{x_{j}}{A_{j}^{1/ν}} , j = n, n − 1, …, 0,  (7.30)
A_{j}^{1/ν} = 1 + γA_{j+1}^{1/ν}, j = 0, 1, …, n − 1,  (7.31)
γ = (βα^{1−ν})^{1/ν}.  (7.32)

Tällöin pätee

A_{n−j}^{1/ν} = A_{n}^{1/ν}γ^{n−j} + \frac{1 − γ^{n−j}}{1 − γ} , j = 0, 1, …, n − 1.  (7.33)

Tarkastellaan lopuksi likimääräsesti tapausta, jossa edessä on runsaasti aikaa eli n − j on suuri. Jos γ > 1, niin A_{n−j}^{1/ν} ≈ (A^{1/ν} − 1)γ^{n−j}, jolloin

−F_{n−j}(x_{n−j}) = A_{n−j}x_{n−j}^{1−ν} ≈ M_{1}γ^{ν(n−j)}x^{1−ν}, u_{n−j} ≈ M_{2} \frac{x}{γ^{n−j}} ,  (7.34)

missä M_{1} ja M_{2} ovat positiivisia vakioita. Jälkimmäinen näistä yhtälöistä kertoo, että kulutusta kannattaa myöhentää. Jos γ < 1 on suuri, niin A_{n−j}^{1/ν} ≈ 1/(1 − γ), jolloin

−F_{n−j}(x_{n−j}) ≈ \frac{x_{n−j}^{1−ν}}{(1 − γ)^{ν}} , u_{n−j} ≈ (1 − γ)x_{n−j}.  (7.35)

Tällöin rahoista kulutetaan vakio-osa kullakin ajan askeleella.