Stran 1 od 1

Optimizacija 1

Objavljeno: 8.2.2016 20:31
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 :)

Re: Optimizacija 1

Objavljeno: 9.2.2016 17:39
Napisal/-a derik
Izračunaj stroške za vse možne varijante in izberi tisto, ki je najcenejša..

Re: Optimizacija 1

Objavljeno: 10.2.2016 14:27
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)?

Re: Optimizacija 1

Objavljeno: 10.2.2016 15:44
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.

Re: Optimizacija 1

Objavljeno: 11.2.2016 7:31
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

Re: Optimizacija 1

Objavljeno: 21.2.2016 16:40
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 :)