Optimizacija 1

Ko tudi učitelj ne more pomagati...
Odgovori
delta
Prispevkov: 422
Pridružen: 19.8.2009 14:16

Optimizacija 1

Odgovor Napisal/-a delta »

Zanima me, če zna kdo rešiti nalogo:
Neko gradbeno podjetje ima na različnih lokacijah po Sloveniji 4 bagre. V danem trenutku imajo gradbena dela na 4 različnih gradbiščih in na vsakem bi rabili natanko bager. Stroški transporta bagrov na gradbišče so zajeti v spodnji tabeli:
\(\begin{matrix}
A&B&C&D\\
90&75&75&80\\
35&85&55&65\\
125&95&90&105\\
45&110&95&115\\
\end{matrix}\)

Določi, kako naj firma porazdeli po gradbiščih, da bo cena njihovega transporta najmanjša! Koliko znaša minimalna cena transporta bagrov?

Lepo prosim za pomoč, potrebovala bi do jutri. Hvala :)

derik
Prispevkov: 2044
Pridružen: 6.3.2010 9:04

Re: Optimizacija 1

Odgovor Napisal/-a derik »

Izračunaj stroške za vse možne varijante in izberi tisto, ki je najcenejša..

maxwell
Prispevkov: 100
Pridružen: 16.11.2011 19:10

Re: Optimizacija 1

Odgovor Napisal/-a maxwell »

Ali pa kakšen genetski algoritem.

Kakšne metode pa še obstajajo za reševanje podobnih nalog (kjer iščemo min/max neke kombinacije podanih vrednosti)?

derik
Prispevkov: 2044
Pridružen: 6.3.2010 9:04

Re: Optimizacija 1

Odgovor Napisal/-a derik »

Je več metod, algoritmov in orodij (https://en.wikipedia.org/wiki/Vehicle_routing_problem). Ampak v vsakem primeru bodisi iščeš do sprejemljivega nivoja stroškov, ali pa moraš preveriti res vse možnosti (kar ta naloga tudi zahteva). Če bi morali računati stroške prevoza vsakega vozila, bi bilo bolj zahtevno, tako pa so že podani in jih je treba le sešteti za vseh 24 možnosti.

Zajc
Prispevkov: 1099
Pridružen: 26.6.2008 19:15

Re: Optimizacija 1

Odgovor Napisal/-a Zajc »

Gre za problem najcenejšega popolnega prirejanja. Standardni postopek reševanja je t.i. madžarska metoda z utežmi (MMU). Koraki te metode so naslednji:

Ves čas delamo z matriko cen povezav C, ki je velikosti n×n.

Postopek:
1. Od elementov vsake vrstice matrike C odštejemo najmanjši element tiste vrstice. Od elementov vsakega stolpca matrike C odštejemo najmanjši element tistega stolpca.
2. Če v matriki C najdemo n ničel, tako da je v vsaki vrstici in v vsakem stolpcu natanko ena, končamo (najdene ničle določajo najcenejše popolno prirejanje). Sicer poiščemo množico vrstic in stolpcev (skupaj manj kot n), ki pokrijejo vse ničle v matriki C.
3. Naj bo ε najmanjši nepokriti element C. Vse nepokrite elemente zmanjšamo za ε. Vse dvakrat pokrite elemente povečamo za ε. Ostale elemente pustimo nespremenjene. Vrnemo se na korak 2.


Vir: http://studentski.net/gradivo/ulj_fmf_f ... oki_01?r=1

delta
Prispevkov: 422
Pridružen: 19.8.2009 14:16

Re: Optimizacija 1

Odgovor Napisal/-a delta »

Hvala za odgovore. :)
Pretoki:
Kaj pomeni zapis: Kirchhoffovega pogoja: \(\sum_{j \in V}f(i,j)=0\) za vse \(i \in V|\{s,t\}\). \(i\) je začetno vozlišče, \(j\) končno vozlišče? zakaj takšna vsota? Lp :)

Odgovori