[es] - Zasto ne radi Solver problem

Blue82
dipl. ecc.

Član broj: 165981
Poruke: 838
*.static.isp.telekom.rs.

+322 Profil

^{27.10.2014. u 06:35 - pre 115 meseci}

Pokusavam da nateram Solver da mi reši jedna problem.
Imam spisak 2 banke sa trenutnim stanjem na banci. Cilj je da se dobije optimalno rešenje, sa koje banke se uplaćuje koji iznos, tako da troškovi bankarske naknade budu najmanji.

Pojašnjenje kako sam zamislio problem:
Deo obeležen plavim predstavljaju iznosi koje je tog dana potrebno uplatiti različitim dobavljačima.
Deo obeležen žutim, postavio sam kao binarni podatak. Ukoliko solver u njega ubaci 1 onda se taj iznos upisuje u gornju tabelu "Pregled plaćanja" kod banke UniCredit ili Societe što znači da je taj iznos izabran. Čim se iznos upiše u izabranu tabelu u tabeli trošak se pomoću makroa izračunava bankarska naknada za plaćanje sa te banke izabranog iznosa. Da se isti iznos ne bi mogao 2x izabrati jednom za jednu a drugi put za drugu banku, U delu obeleženom narandžastim stavim ograničenje da on može biti samo <2 tj iznos može biti samo 1 izabran.
Na kraju stavim ograničenje da ukupan zbir plaćenog treba da bude jednak zbiru svih faktura koje su tog dana određene za plaćanje (zbiru faktura obeleženih plavim).
Funkcija je MIN ukupan trošak.

Iz nekog razloga Solver mi pronađe rešenje ali ono nije najoptimalnije pošto ja ručno pronađem bolje rešenje.

Evo i slike kakvo je rešenje našao Solver.

_{[Ovu poruku je menjao Blue82 dana 27.10.2014. u 07:52 GMT+1]}

Prikačeni fajlovi

Slika1.jpg - 356.03k

Copy of Proba solver (2).xlsm - 17.97k

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Zasto ne radi Solver problem

^{27.10.2014. u 08:42 - pre 115 meseci}

Solver ne pronalazi uvek optimalno rešenje, što on i sam napiše na kraju proračuna.

Ako promeniš metodu, recimo na "Evolutionary", ili promeniš broj koraka iteracije, ili promeniš maksimalno dozvoljeno vreme, u ovom konkretnom slučaju solver će pronaći bolje rešenje. A možda i neće. Meni je našao.

Odgovor na temu

Blue82
dipl. ecc.

Član broj: 165981
Poruke: 838
*.static.isp.telekom.rs.

+322 Profil

Re: Zasto ne radi Solver problem

^{27.10.2014. u 09:51 - pre 115 meseci}

Izeš ga onda.
Ja sam mislio da on uvek pronalazi najbolje rešenje. Odokativno ili po logici i ja mogu da nađem ručno, približno rešenje.
A sem toga hteo sam još da ga zakomplikujem, ovo je samo bio ogledni primer :)

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Zasto ne radi Solver problem

^{27.10.2014. u 10:07 - pre 115 meseci}

Moraš da razumeš da Solver ima svojih ograničenja:

1.Solver dobro radi ako su funkcije "glatke" (u matematičkom smislu). Dakle funkcije cilja koje su polinomi, eksponenti itd. nisu neki problem za solver. Tebi je potrebno rešenje KOMBINATORNOG problema sa funkcijama koje si ti definisao, a koje solver uopšte ne razume. Uopšte, problemi sa celobrojnim koeficijentima su i za matematičara tvrd orah, a kamoli za program.

2. Lokalni minimumi. Ako solver naleti na rešenje koje je bolje od prethodnih, a malim varijacijama ulaznog vektora ne postiže poboljšanje, solver će odustati i prikazati neoptimalno rešenje.

3. Početni uslovi. Ako su početni uslovi koje zadaš "blizu" optimalnog rešenja, solver će verovatno naći bolje rešenje.

4. Algoritam. Ako se ne koristi heuristika, kao kod evolucionog algoritma, onda se solver često zakuca na neoptimalnom rešenju. Heuristika mu dozvoljava da malo eksperimentiše sa neoptimalnim rešenjima. U principu, kod evolucionog algoritma, solver na odbacuje neoptimalna rešenja, nego namerno dozvoljava da se rešenje traži (u nekoj okolini) neoptimalnog rešenja, nadajući se da će ga taj postupak "izvući" iz lokalnog minimuma u koji ga mogu zakucati druge metode.

Odgovor na temu

Blue82
dipl. ecc.

Član broj: 165981
Poruke: 838
*.static.isp.telekom.rs.

+322 Profil

Re: Zasto ne radi Solver problem

^{27.10.2014. u 10:47 - pre 115 meseci}

Razumem, sad je malo jasnije.
Ubiti uopšte nisam znao na koji način on razmišlja, osim da verovatno lupeta brojeve npr o 0,000001 do nekog broja i gleda da li mu traženi rezultat raste, opada i sl.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Zasto ne radi Solver problem

^{27.10.2014. u 11:21 - pre 115 meseci}

Imaš more primera na netu zašto solver ne radi dobro kada se uvede ograničenje da su neke varijable celobrojne:

Citat:

Integer constraints have many important applications, but the presence of even one such constraint in a Solver model makes the problem an integer programming problem, which may be much more difficult to solve than a similar problem without the integer constraint.

http://www.solver.com/content/...ent-constraints-affect-solving

Citat:

It is possible to solve nonlinear integer problems with the Excel Solver, but users should be aware of the intrinsic limitations of this process. On a linear problem, the simplex method can conclusively determine whether each sub-problem is feasible and, if so, return the globally optimal solution to that sub-problem. On nonlinear integer problems, the GRG algorithm (or any gradient-based method) may fail to find a feasible solution for a sub-problem even though one exists, or it may return a local optimum that is not global. This also means that the best bound used by the branch and bound algorithm will be based on local optima found by GRG2 and this may not be the global optimum. Because of this, the branch and bound algorithm is not guaranteed to find the true integer optimum for nonlinear problems, although it will often succeed in finding a "good" integer solution.

https://www.utexas.edu/courses/lasdon/design3.htm

Odgovor na temu

dragancesu
subotica

Član broj: 38340
Poruke: 2189
*.dynamic.isp.telekom.rs.

+73 Profil

Re: Zasto ne radi Solver problem

^{28.10.2014. u 10:47 - pre 115 meseci}

Mislim da ovo nije bas pravi problem za solver, ne vidim da trebaju iteracije

Tvoj cilj je da smanjis trosak koji banka naplacuje za transakcije, to je skoro linearni problem

Od cega to zavisi:

iznosa (imas skalu),
gde je racun (ako je ista banka manja provizija)
hitnost (brzina se placa)

ako si u uniCredit banci onda ti vazi http://www.unicreditbank.rs/do...%20korporativni%20klijenti.pdf i to je na drugoj strani

Ono sto nisam napisao gore je da treba voditi i racuna o vremenu placanja

I na prvi pogleda neko treba da se potrudi da nalozi budu dati sto ranije, po mogucnosti da partner ima racun u istoj banci

Pomozite Micro$oftu u borbi protiv piraterije, poklonite prijatelju Linux

Odgovor na temu

Blue82
dipl. ecc.

Član broj: 165981
Poruke: 838
*.adsl-a-1.sezampro.rs.

+322 Profil

Re: Zasto ne radi Solver problem

^{28.10.2014. u 19:20 - pre 115 meseci}

Jasan je meni tarifarnik banke. Mi smo veliko preduzece i kao vip klijent imamo potpuno drugacije tarife od prikazanih. Problem je malo drugaciji. Imamo jedno 15-tak racuna u razlicitim bankama i svaka banka ima neke svoje pogodnosti u odnosu na iznos ili vreme pustanja naloga i sl, pa sam pokusao da napravim da Excel sam odredi uz pomoc Solvera koja kombinacija naloga daje najmanju bankarsku proviziju. Ovo sto je prikaceno je vrlo jednostavna primer koji sam zamisljao da razvijem preko ovog nivoa ali posto nije upotpunosti uspelo ni sa 2 banke i jednostavnim makroima, odustao sam od daljeg produbljavanja problema.

Odgovor na temu