Operacijske raziskave

« nazaj

Operacijske raziskave - vaje 28.3.2022

Dinamično programiranje

Naloga 1

Podjetje bo kmalu uvedlo nov izdelek na zelo konkurenčen trg, zato trenutno pripravlja marketinško strategijo. Odločili so se, da bodo izdelek uvedli v treh fazah. V prvi fazi bodo pripravili posebno začetno ponudbo z močno znižano ceno, da bi privabili zgodnje kupce. Druga faza bo vključevala intenzivno oglaševalsko kampanjo, da bi zgodnje kupce prepričali, naj izdelek še vedno kupujejo po redni ceni. Znano je, da bo ob koncu druge faze konkurenčno podjetje predstavilo svoj izdelek. Zato bo v tretji fazi okrepljeno oglaševanje z namenom, da bi preprečili beg strank h konkurenci.

Podjetje ima za oglaševanje na voljo $4$ milijone evrov, ki jih želimo čim bolj učinkovito porabiti. Naj bo $m$ tržni delež v procentih, pridobljen v prvi fazi, ${f_2}$ delež, ohranjen po drugi fazi, in ${f_3}$ delež, ohranjen po tretji fazi. Maksimizirati želimo končni tržni delež, torej količino $m {f_2} {f_3}$.

\[\begin{aligned} p_3(x) &= f_3(x) & \text{$x$ namenimo tretji fazi} \\ p_2(x) &= \max\{f_2(y) p_3(x-y) \mid 0 \le y \le x\} & \text{$x$ namenimo drugi in tretji fazi} \\ p_1(x) &= \max\{m(y) p_2(x-y) \mid 0 \le y \le x\} & \text{$x$ namenimo celotnemu projektu} \\ p^* &= p_1(4) \end{aligned}\]

  1. Denimo, da želimo v vsaki fazi porabiti nek večkratnik milijona evrov, pri čemer bomo pri prvi fazi porabili vsaj milijon evrov. V spodnji tabeli so zbrani vplivi porabljenih količin na vrednosti $m$, ${f_2}$ in ${f_3}$.

    M€ $m$ ${f_2}$ ${f_3}$
    0 - 0.2 0.3
    1 20 0.4 0.5
    2 30 0.5 0.6
    3 40 0.6 0.7
    4 50 - -

    Kako naj razdelimo sredstva?

\[\begin{aligned} p_2(0) &= 0.2 \cdot 0.3 &&= 0.06 \\ p_2(1) &= \max\{0.2 \cdot 0.5, 0.4 \cdot 0.3\} &&= 0.12 \\ p_2(2) &= \max\{0.2 \cdot 0.6, \underline{0.4 \cdot 0.5}, 0.5 \cdot 0.3\} &&= 0.2 \\ p_2(3) &= \max\{0.2 \cdot 0.7, 0.4 \cdot 0.6, 0.5 \cdot 0.5, 0.6 \cdot 0.3\} &&= 0.25 \\ p^* = p_1(4) &= \max\{20 \cdot 0.25, \underline{30 \cdot 0.2}, 40 \cdot 0.12, 50 \cdot 0.06\} &&= 6 \end{aligned}\]

Optimalna rešitev:

Dosežemo tržni delež 6%.

  1. Denimo sedaj, da lahko v vsaki fazi porabimo poljubno pozitivno količino denarja (seveda glede na omejitev skupne porabe). Naj bodo torej ${x_1}$, ${x_2}$ in ${x_3}$ količine denarja v milijonih evrov, ki jih porabimo v prvi, drugi in tretji fazi. Vpliv na tržni delež je podan s formulami

    \[m = x_1 (10 - x_1), \quad f_2 = 0.4 + 0.1 x_2, \quad \text{in} \quad f_3 = 0.6 + 0.07 x_3 .\]

    Kako naj sedaj razdelimo sredstva?

\[\begin{aligned} p_3(x) &= 0.6 + 0.07 x \\ p_2(x) &= \max\{(0.4 + 0.1 y) (0.6 + 0.07 (x-y)) \mid 0 \le y \le x\} \\ &= \max\{-0.007 y^2 + (0.032 + 0.007 x) y + 0.24 + 0.028 x \mid 0 \le y \le x\} \\ 0 &= -14 y + 32 + 7 x \\ 0 \le y &= {32 + 7x \over 14} = {16 \over 7} + {1 \over 2} x \le x \\ p_2(x) &= 0.24 + 0.06 x \\ p^* = p_1(4) &= \max\{m(y) p_2(4-y) \mid 0 \le y \le x\} \\ &= \max\{(y (10 - y)) (0.24 + 0.06 (4-y)) \mid 0 \le y \le 4\} \\ &= \max\{(y (10 - y)) (0.48 - 0.06 y) \mid 0 \le y \le 4\} \\ &= \max\{0.06 y^3 - 1.08 y^2 + 4.8 y \mid 0 \le y \le 4\} \\ 0 &= 0.18 y^2 - 2.16 y + 4.8 \\ y &= {2.16 - \sqrt{4.6656 - 3.456} \over 0.36} \approx 2.94 \\ p^* &\approx 6.30 \end{aligned}\]

Optimalna rešitev:

Naloga 2

Dan je sledeči nelinearni program.

\[\begin{aligned} \max &\quad 2x_1^2 + 2x_2 + 4x_3 - x_3^2 \\[1ex] 2x_1 + x_2 + x_3 &\le 4 \\ x_1, x_2, x_3 &\ge 0 \end{aligned}\]

Reši ga s pomočjo dinamičnega programiranja.

Naloga 3

Igralec na srečo bo odigral tri partije s svojimi prijatelji, pri čemer lahko vsakič stavi na svojo zmago. Stavi lahko katerokoli vsoto denarja, ki jo ima na voljo - če izgubi partijo, zastavljeno vsoto izgubi, sicer pa tako vsoto pridobi. Pri vsaki partiji sta verjetnosti zmage in poraza enaki $1/2$. Na začetku ima $75 €$, na koncu pa želi imeti $100 €$ (ker igra s prijatelji, noče imeti več kot toliko).

Z dinamičnim programiranjem poišči strategijo stavljenja, ki maksimizira verjetnost, da bo na koncu imel natanko $100 €$.

Teorija odločanja

Naloga 4

Na ulici nas ustavi neznanec in nam predlaga met kovanca. Če pade grb, nam izplača $250000 €$, če pade glava, pa mi njemu $100000 €$. Ali naj sprejmemo ponudbo?

Naloga 5

Janez želi naložiti vsoto $1000 €$ v banko za dobo petih let. Odloča se med tem, da bi jo vezal za pet let (obrestna mera $5\%$) ali pa petkrat zaporedoma po eno leto (obrestna mera $4\%$). Če denar veže za pet let, vmes pa varčevanje prekine, mu pripada le obrestna mera $3\%$. Ocenjuje, da lahko v naslednjih petih letih pride do naslednjih situacij:

Opiši, kako naj se odloči glede na posamezne kriterije (optimist, pesimist, Laplace, Savage). Določi vrednosti parametera $\alpha$, pri katerih je po Hurwiczevem kriteriju možnih več enakovrednih odločitev.

shema nespremenjena povečana zmanjšana prekinitev
5 let 250 € 250 € 250 € /
3 leta + 2x 1 leto 170 € 194 € 154 € /
3 leta 90 € 90 € 90 € 90 €
5x 1 leto 200 € 224 € 184 € /
3x 1 leto 120 € 120 € 120 € 120 €

Dobimo odločitveno tabelo:

začetna shema nespremenjena povečana zmanjšana prekinitev
5 let 250 € 250 € 250 € 90 €
5x 1 leto 200 € 224 € 184 € 120 €

Naloga 6

Trgovina pri pekarni kupuje žemlje po $0.2 €$ in jih prodaja po $0.4 €$. Skozi leta poslovanja so izračunali naslednjo porazdelitev za prodajo žemljic.

Prodaja $50$ $60$ $70$ $80$ $90$ $100$
Verjetnost $0.1$ $0.15$ $0.3$ $0.2$ $0.15$ $0.1$

Če žemelj zmanjka, naročijo pri pekarni razliko, pri čemer jih žemlja tedaj stane $0.3 €$. Ob koncu dneva jim pekarna odkupi presežek po $0.15 €$ na žemljo. Koliko žemelj se trgovini splača kupiti?

\[\begin{aligned} E(Y \mid X = 70) &= -70 \cdot 0.2 € + 0.1 \cdot (50 \cdot 0.4 € + 20 \cdot 0.15 €) + 0.15 \cdot (60 \cdot 0.4 € + 10 \cdot 0.15 €) \\ &+ 0.3 \cdot 70 \cdot 0.4 € + 0.2 \cdot (80 \cdot 0.4 € - 10 \cdot 0.3 €) + 0.15 \cdot (90 \cdot 0.4 € - 20 \cdot 0.3 €) \\ &+ 0.1 \cdot (100 \cdot 0.4 € - 30 \cdot 0.3 €) = 13.925 € \end{aligned}\]
Ta stran je odprtokodna. Izboljšaj to stran.
Ta zapisek je dostopen tudi na HackMD.