Operacijske raziskave

« nazaj

Operacijske raziskave - vaje 31.5.2021

Modeliranje z linearnim programom

Naloga 1

Gradbinec in samooklicani arhitekt Brezzobec se je odločil, da bo postavil zelo posebno hišo. Gradnja bo imela sedem glavnih faz:

faza opis trajanje pogoj min. trajanje cena za dan manj
A gradnja kleti 10 dni / 7 dni 200
B gradnja pritličja 6 dni A 5 dni 100
C gradnja prvega nadstropja 7 dni B, F 5 dni 150
D gradnja strehe 8 dni C, E 6 dni 160
E gradnja desnega podpornega stebra 13 dni A 9 dni 250
F gradnja glavnega podpornega stebra 14 dni / 11 dni 240
G gradnja baročnega stolpa pred hišo 30 dni / 25 dni 300
  1. Kdaj je lahko hiša najhitreje zgrajena? Katere faze so kritične?
  2. Koliko je kritičnih poti in katere so?
  3. Katero opravilo je najmanj kritično? Najmanj kritično je opravilo, katerega trajanje lahko največ podaljšamo, ne da bi vplivali na trajanje gradnje.
  4. Brezzobčev brat je ponudil pomoč pri največ eni fazi gradnje. Slovi po tem, da pri fazi, pri kateri pomaga, zmanjša čas izvajanja za $10\%$. Pri kateri fazi naj pomaga, da bo čas gradnje čim krajši?
  5. Brezzobčev bratranec ima podjetje, ki lahko pomaga pri gradnji, vendar za vsak dan krajšanja posamezne faze zahteva ustrezno plačilo (glej zadnja dva stolpca). Brezzobca zanima način, kako bi s čim manjšimi stroški čas gradnje zmanjšal na $27$ dni. Zapiši linearni program za ta problem.
  1. graph LR
   
S == 0 ==> A
S -- 0 --> F
S -- 0 --> G
A == 10 ==> B
A == 10 ==> E
B == 6 ==> C
F -- 14 --> C
C == 7 ==> D
E == 13 ==> D
D == 8 ==> T
G -- 30 --> T

    Topološka ureditev: S, A, B, F, C, E, D, G, T

    opravilo S A B F C E D G T
    najprej 0 0/S 10/A 0/S 16/B 10/A 23/CE 0/S 31/D
    najkasneje 0/A 0/BE 10/C 2/C 16/D 10/D 23/T 1/T 31
    razlike 0 0 0 2 0 0 0 1 0
    • Kritična opravila: A, B, C, E, D
    • Kritična pot 1: S - A - B - C - D - T
    • Kritična pot 2: S - A - E - D - T

  3. Najmanj kritično opravilo je F.

  4. Krajšamo opravilo A (najdaljše opravilo na vseh kritičnih poteh) - skrajšamo ga za 1 dan, tako da projekt končamo v 30 dneh.

    • ${x_i}$ … trajanje faze $i$
    • ${y_i}$ … začetni čas faze $i$
    • podatki:
      • ${t_i}$ … osnovno trajanje faze $i$ (brez krajšanja)
      • ${m_i}$ … najmanjše trajanje faze $i$
      • ${c_i}$ … cena krajšanja faze $i$ za en dan
      • ${P_i}$ … množica predhodnih opravil za fazo $i$
      • $T$ … želeni čas končanja
    \[\begin{alignedat}{2} && \min & \sum_i c_i (t_i - x_i) \\ \forall i: &\ & m_i \le x_i &\le t_i \\ \forall i: &\ & 0 \le y_i &\le T - x_i \\ \forall i \ \forall j \in P_i: &\ & y_i &\le y_j + x_j \end{alignedat}\] \[\begin{gathered} \max 200 x_A + 100 x_B + 150 x_C + 160 x_D + 250 x_E + 240 x_F + 300 x_G \\ \begin{alignedat}{2} 7 \le x_A &\le 10 \\ 5 \le x_B &\le 6 \\ 5 \le x_C &\le 7 \\ 6 \le x_D &\le 8 \\ 9 \le x_E &\le 13 \\ 11 \le x_F &\le 14 \\ 25 \le x_G &\le 30 \\ y_A &\ge 0 \\ y_F &\ge 0 \\ y_G &\ge 0 \\ y_B &\ge y_A + x_A \\ y_C &\ge y_B + x_B \\ y_C &\ge y_F + x_F \\ y_D &\ge y_C + x_C \\ y_D &\ge y_E + x_E \\ y_E &\ge y_A + x_A \\ y_D + x_D &\le 27 \\ y_G + x_G &\le 27 \end{alignedat} \end{gathered}\]

Metoda PERT

Naloga 2

Pri gradbenem podjetju razmišljajo, da bi se prijavili na razpis za prenovo avtocestnega viadukta. Identificirali so pet nalog:

naloga najkrajše trajanje najbolj verjetno trajanje najdaljše trajanje predhodna opravila
A 3 tedni 4 tedni 5 tednov /
B 2 tedna 2 tedna 2 tedna A
C 3 tedni 5 tednov 6 tednov B
D 1 teden 3 tedni 5 tednov A
E 2 tedna 3 tedni 5 tednov B, D

Če bodo izbrani za izvedbo del, si obetajo zaslužek v višini $250.000 €$. Če del ne bodo končali v roku $11$ tednov, bodo morali plačati pogodbeno kazen v višini $500.000 €$.

  1. Topološko uredi ustrezni graf in ga nariši.
  2. Za vsako opravilo določi pričakovano trajanje in varianco.
  3. Določi pričakovano kritično pot ter trajanje izvedbe.
  4. Oceni verjetnost, da se bo projekt zaključil v $11$ tednih. Naj se podjetje prijavi na razpis? Pomagaj si s tabelo standardne normalne porazdelitve.
graph LR

S == 0 ==> A
A == 4 ==> B
A -- 4 --> D
B == 2 ==> C
B -- 2 --> E
D -- 3 --> E
C == 4.83 ==> T
E -- 3.17 --> T

Topološka ureditev: S, A, B, C, D, E, T

opravilo S A B C D E T
pričakovano trajanje 0 4 2 4.83 3 3.17 0
varianca 0 0.11 0 0.25 0.44 0.25 0
najprej 0 0/S 4/A 6/B 4/A 7/D 10.83/C
najkasneje 0/A 0/B 4/C 6/T 4.67/E 7.67/T 10.83
razlika 0 0 0 0 0.67 0.67 0

Verjetnost pravočasnega končanja:

\[P(X \le 11) = \phi\left({11 - \mu \over \sigma}\right) \approx \phi(0.277) \approx 0.6103\]

Pričakovani dobiček:

\[250\,000 € - (0.3897 \cdot 500\,000 €) = 55\,150 €\]

Se jim izplača prijaviti!

Naloga 3

Izdelati želimo terminski plan za organizacijo konference. V spodnji tabeli so zbrana opravila pri organizaciji.

Naloga Opravilo Pogoji Minimalno trajanje Najbolj verjetno trajanje Maksimalno trajanje
A Izbira lokacije / 10 dni 13 dni 22 dni
B Rezervacija sob za goste F 13 dni 22 dni 25 dni
C Dogovarjanje za cene hotelskih sob A 3 dni 6 dni 9 dni
D Naročilo hrane in pijače A 6 dni 15 dni 21 dni
E Priprava letakov C, J 5 dni 8 dni 11 dni
F Pošiljanje letakov E 4 dni 4 dni 4 dni
G Priprava zbornika s povzetki D, J 22 dni 28 dni 31 dni
H Določitev glavnega govorca / 5 dni 8 dni 14 dni
I Planiranje poti za glavnega govorca A, H 11 dni 14 dni 17 dni
J Določitev ostalih govorcev H 12 dni 15 dni 21 dni
K Planiranje poti za ostale govorce A, J 9 dni 12 dni 18 dni
  1. Topološko uredi ustrezni graf in ga nariši. Za trajanja opravil vzemi pričakovana trajanja po modelu PERT.
  2. Določi pričakovano kritično pot in čas izdelave.
  3. Katero opravilo je (ob zgornjih predpostavkah) najmanj kritično? Najmanj kritično je opravilo, katerega trajanje lahko najbolj podaljšamo, ne da bi vplivali na celotno trajanje izvedbe.
  4. Določi variance trajanj opravil in oceni verjetnost, da bo izvedba trajala manj kot $55$ dni.
graph LR

S -- 0 --> A
S -- 0 --> H
A -- 14 --> C
A -- 14 --> D
A -- 14 --> I
H -- 8.5 --> I
H -- 8.5 --> J
C -- 6 --> E
J -- 15.5 --> E
D -- 14.5 --> G
J -- 15.5 --> G
A -- 14 --> K
J -- 15.5 --> K
E -- 8 --> F
F -- 4 --> B
B -- 21 --> T
G -- 27.5 --> T
I -- 14 --> T
K -- 12.5 --> T
Ta stran je odprtokodna. Izboljšaj to stran.
Ta zapisek je dostopen tudi na HackMD.