---
tags: vaje, om, mmu
hackmd: https://hackmd.io/0gJbP9LIRgexJuTNLABU2w
plugins: mathjax
---
# Optimizacijske metode - vaje 17.4.2020

---

## Madžarska metoda z utežmi

### Naloga 1

Na podlagi rezultatov plavalcev bi radi sestavili štafeto:

| | A | B | C | D |
| ------ | -- | -- | -- | -- |
| delfin | 58 | 60 | 57 | 60 |
| hrbtno | 66 | 68 | 65 | 66 |
| prsno | 56 | 57 | 55 | 54 |
| prosto | 51 | 52 | 53 | 51 |

Kako naj sestavimo štafeto, da bo dosegala čim boljše rezultate?

---

### Naloga 2

Poišči najcenejše popolno prirejanje za sledečo matriko uteži:

$$
C = \begin{pmatrix}
17 & 9 & 14 & 2 & 15 & 8 \\
13 & 17 & 9 & 9 & 2 & 11 \\
4 & 11 & 4 & 7 & 2 & 8 \\
19 & 4 & 16 & 11 & 17 & 19 \\
9 & 7 & 11 & 11 & 18 & 13 \\
13 & 11 & 16 & 12 & 5 & 18
\end{pmatrix}
$$

Povečujoče poti poišči na pomožnem neuteženem grafu s pomočjo madžarske metode.

---

### Naloga 3

Marjetka opremlja stanovanje. S pridnim nabiranjem kupončkov in točk zvestobe si je v petih različnih trgovinah priborila ekskluzivni popust na en artikel. Cene, po katerih lahko kupi želene artikle, so zbrane v naslednji tabeli.

| | televizor | hladilnik | pralni stroj | klimatska naprava |
| ------------- | --- | --- | --- | --- |
| Mercator | 300 | 230 | 130 | 450 |
| Spar | 320 | 210 | 140 | 420 |
| Tuš | 260 | 240 | 110 | 480 |
| Big Bang | 260 | 250 | 120 | 440 |
| Harvey Norman | 270 | 220 | 150 | 500 |

V katerih trgovinah naj kupi želene artikle, da bo skupna cena čim nižja? V vsaki trgovini lahko kupi samo en artikel, saj so cene brez popusta previsoke. Napiši tudi skupni strošek.

---

### Naloga 4

Teroristična skupina Kal Ajde je sklenila napasti Haloški Tribunal, tebi kot ekspertu za optimizacijske metode pa so zaupali razdelitev nalog med izvajalce napada. Ker pa si v resnici tajni agent Sove, je tvoja naloga ta, da poskrbiš za to, da bi za napad porabili kar se da veliko časa.

Za izvedbo napada so bili določeni Alojz, Božo in Cvetko. Čas v minutah, ki ga porabijo za vsako nalogo, je zbran v naslednji tabeli.

| | vlamljanje v sodišče | dezaktivacija alarma | kraja sodnih spisov | postavitev bombe | vzpostavitev prvotnega stanja |
| ----- | -- | -- | -- | -- | -- |
| Alojz | 14 | 15 | 30 | 16 | 26 |
| Božo | 16 | 16 | 26 | 17 | 34 |
| Cvetko | 17 | 18 | 28 | 15 | 32 |

Alojz bo izvedel dve nalogi, Božo in Cvetko pa vsak vsaj eno. Kako naj si razdelijo naloge, da bo napad trajal čim dalj (predpostavi, da se naloge izvajajo zaporedno)?
Izračunaj tudi skupno trajanje napada!

**Namig:** ena od vrstic matrike bo vsebovala primerno izbrane Božove in Cvetkove čase.

---

### Naloga 5

Slovenska policija je sklenila prenoviti svoj komunikacijski sistem. Prenovo bodo izvedli trije izvajalci, katerih imena so zaradi državne varnosti zamenjana s tajnimi šiframi. Zaradi preprečevanja korupcije sme posamezen izvajalec izvesti samo dve nalogi. V spodnji tabeli so navedene cene (v milijonih evrov), ki jih izvajalci računajo za izvedbo naloge.

| | CIA | KGB | MI6 |
| -------------------------------------- | --- | --- | --- |
| postavitev baznih postaj | 45 | 42 | 51 |
| nabava mobilnih terminalov | 37 | 36 | 41 |
| nastavitev enkripcije | 25 | 24 | 21 |
| prenova računalniškega omrežja | 32 | 29 | 31 |
| vzpostavitev prisluškovalnih kapacitet | 29 | 27 | 28 |
| izobraževanje odgovornih | 17 | 22 | 19 |

Kako naj dodelimo naloge izvajalcem, da bo skupna cena čim nižja? Izračunaj tudi skupno ceno prenove.

---

### Naloga 6

Slovenija se je kot gostoljubna država zavezala k temu,
da sprejme čim večje število prebežnikov. Iz štirih držav z največ prebežniki bo tako sprejela pet skupin prebežnikov, pri čemer mora iz vsake države sprejeti vsaj eno skupino, sprejeti pa mora natanko po eno skupino za vsako narodnost. V spodnji tabeli so naštete velikosti skupin posamezne narodnosti, ki jih lahko sprejme iz posamezne države.

| | Grčija | Italija | Nemčija | Švedska |
| ------------ | --- | -- | --- | --- |
| Afganistanci | 67 | 52 | 131 | 97 |
| Iračani | 102 | 47 | 142 | 103 |
| Kurdi | 87 | 66 | 114 | 127 |
| Libijci | 81 | 97 | 86 | 77 |
| Sirci | 117 | 83 | 145 | 132 |

Katere skupine naj sprejme, da bo sprejela čim več prebežnikov? Napiši tudi skupno število sprejetih prebežnikov.

**Namig:** matriko na zvit način dopolni do kvadratne.