optymalizacja sciezki excel-solver
CosmoUN
obliczyc tzw problem traveling salesman problem czyli przejscie po
najkrotszej drodze przez wszystkie punkty (kazdy odwiedzajac tylko raz) i
powrocic do poczatku - nie wiem jak to ustawic w solverze :(
Sprawa jest bardzo pilna
Pozdrawiam
WuKa
news:cqlsvg$pru$2...@atlantis.news.tpi.pl...
>nie wiem jak to ustawic w solverze :(
>
wprowadzić tam wzór, którego minimalizacja, maksymalizacja lub chęć
uzyskania z góry określonej wartości będzie realizowana przez solver. W
pasku komórek zmienianych dajesz te wielkości, od których zależy wartość
powyższej formuły. W polu ograniczenia podajesz ich ograniczenia z wyboru
proponowanych możłiwości (<=, >=, int itd)
WuKa
CosmoUN
Użytkownik "WuKa" <wlk...@op.pl> napisał w wiadomości
news:cqltkt$a3r$1...@opal.futuro.pl...
No oki ale jaka musi byc formula w powyzszym zadaniu? mam tylko macierz
odleglosci :(
CosmoUN
Użytkownik "CosmoUN" <cosm...@poczta.nospam.onet.pl> napisał w wiadomości
news:cqlsvg$pru$2...@atlantis.news.tpi.pl...
help
WuKa
>
> naprawde nie wiecie jak to rozgryzc ??
>
można go potraktowac wieloma metodami (dokładnymi, heurystycznymi,
iterarcyjnymi itp.). W szczególności można doszukać się bezpłatnych i
płatnych programów dla tego typu zagadnienia. Jest również coś w Excelu,
jako dołączana biblioteka .xla. Nie licz jednak, że ktoś zechce
"entuzjastycznie" zająć się Twoim problemem i za Ciebie rozwiązać.
WuKa
CosmoUN
to se zapusc google i sprobuj znalezc rozwiazanie tego problemu - smialo ..
ile potrzebujesz czasu? ...i nie jakimkolwiek programem tylko solverem i to
w wersji podstawowej a nie premium
Zbigniew Daleczko
Z metod pamiętam metodę Vogla (VAM), metodę potencjałów, metodę
Forda-Fulkersona, algorytmem czynników rozwiązujących. Każda z tych
metod ma swoje wady i zalety. Można zagadnienie rozwiązać zwykłą
symulacją na komputerze. Wydaje mi się, iż google da efekt w postaci
programu rozwiązujacego to zagadnienie transportowe według Twoich wymagań.
Pozdrawiam
Zbigniew Daleczko
CosmoUN
Użytkownik "Zbigniew Daleczko" <Zbig...@Daleczko.com> napisał w wiadomości
news:cqpq99$425$1...@walbrzych.wlb.vectranet.pl...
zadanie ma byc niestety rozwiazane w solverze - chyba ze gosciu
przeszarzowal
i sam nie wie czy jest to wykonywalne (chyba ze uzywa premium solver)
PFG
> Użytkownik "CosmoUN" <cosm...@poczta.nospam.onet.pl> napisał w wiadomości
> news:cqlsvg$pru$2...@atlantis.news.tpi.pl...
>
>>Witam - na razie w arkuszu excela mam tylko macierz odleglosci a musze
>>obliczyc tzw problem traveling salesman problem
> naprawde nie wiecie jak to rozgryzc ??
Metodą brutalnej siły wiemy, paroma innymi lepszymi (choć wciąż
prostymi) metodami też, ale my nie dajemy gotowców. Po prostu.
--
Paweł
Piotr Wyderski
> paroma innymi lepszymi
W jakim sensie lepszymi? Przeciez to jest problem
NP-zupelny -- zgodnie z najlepsza wiedza ludzkosci
w ogolnym przypadku dziala tylko brute force, w
szczegolnych heurystyki, po zrezygnowaniu z szukania
rozwiazania dokladnego (czyli de facto z rozwiazania
_tego_ problemu) algorytmy aproksymacyjne, a i to
niezbyt dobrze, bo dowodzi sie, ze nie istnieje dla
niego algorytm k-aproksymacyjny dla zadnego k
rzeczywistego. Tylko dla grafow o wagach (przypisanych
krawedziom) spelniajacych nierownosc trojkata istnieje
wielomianowy algorytm 2-aproksymacyjny, a na szczescie
takie grafy maja duze znaczenie praktyczne.
> ale my nie dajemy gotowców. Po prostu.
A to inna sprawa. :-)
Pozdrawiam
Piotr Wyderski
A.L.
<Zbig...@Daleczko.com> wrote:
>Użytkownik CosmoUN napisał:
>> Witam - na razie w arkuszu excela mam tylko macierz odleglosci a musze
>> obliczyc tzw problem traveling salesman problem czyli przejscie po
>> najkrotszej drodze przez wszystkie punkty (kazdy odwiedzajac tylko raz) i
>> powrocic do poczatku - nie wiem jak to ustawic w solverze :(
>>
>> Sprawa jest bardzo pilna
>O ile pamietam jest wiele metod rozwiązania zagadnienia transportowego.
>Z metod pamiętam metodę Vogla (VAM), metodę potencjałów, metodę
>Forda-Fulkersona, algorytmem czynników rozwiązujących. Każda z tych
>metod ma swoje wady i zalety. Można zagadnienie rozwiązać zwykłą
>symulacją na komputerze.
Zle pamietasz. Zadanie transportowe i zadanie komiwojazera to
zupelnie dwa rozne zadania i rowiazuej sie roznymi metodami.
A.L.
A.L.
A czy ten co ci to zadal, umie to zadanie rozwiazac Excelem? Sam, z
glowy, bez studiowania literatury? A moze zadal ci zebys te
literature postudiowal?
Zadanie jest trydne, a nawet bardzo trudne. Excel rozwiazuje zadania
programwoania liniowego, wiec do takiej postaci nalezy sprowadzic
zadanie komiwojazera. Pierwszy raz zostalo to dokonane przez George
Dantziga (tworce programowania liniowego) w latach 50. Mimo ze to
bylo 50 lat temu, zadanie nie stalo sie wcale latwiejsze.
Szczegolnie zas trudne jest sformulowanuie ograniczenia ze ma byc
tylko jeden cykl.
Poszukaj w literaturze. Odpowiedz jest na googlach w zasiegu jednego
kliku mysza.
A.L.
A.L.
Wiemy. Jest na googlach.
A.L.
CosmoUN
Użytkownik "A.L." <alewando_tego_nie@oddpost_tego_tez_nie.com> napisał w
wiadomości news:g7p1t0h96qjcj53f4...@4ax.com...
A.L.
<cosm...@poczta.nospam.onet.pl> wrote:
>
>Użytkownik "A.L." <alewando_tego_nie@oddpost_tego_tez_nie.com> napisał w
>> Wiemy. Jest na googlach.
>>
> ale nie w solverze - czytajcie dokladnie
>
Acha. Rozumiem. Chcesz gotowca.
A.L.
CosmoUN
jakiego gotowca - czizus
potrzebuje tylko wskazowki !
zaprogramowanie problemu na podstawie grafu nie jest czyms niewykonalnym ale
chodzi mi o solvera!
Mam tylko macierz odleglosci - i co
Takimi tekstami na pewno nie ulatwiasz mi zadania.
A.L.
<cosm...@poczta.nospam.onet.pl> wrote:
>
>Użytkownik "A.L." <alewando_tego_nie@oddpost_tego_tez_nie.com> napisał w
>wiadomości news:p212t0tjdto7t4154...@4ax.com...
>> On Tue, 28 Dec 2004 06:53:11 +0100, "CosmoUN"
>> <cosm...@poczta.nospam.onet.pl> wrote:
>>
>> >
>> >Użytkownik "A.L." <alewando_tego_nie@oddpost_tego_tez_nie.com> napisał w
>>
>> >> Wiemy. Jest na googlach.
>> >>
>> > ale nie w solverze - czytajcie dokladnie
>> >
>>
>> Acha. Rozumiem. Chcesz gotowca.
>
>jakiego gotowca - czizus
>potrzebuje tylko wskazowki !
>zaprogramowanie problemu na podstawie grafu nie jest czyms niewykonalnym ale
>chodzi mi o solvera!
Nie rozumiem o co ci chodzi. Napisalem juz ze: a) Solver rozwiazuje
zdania programowania liniowego, b) Problem komiwojazera mozna
sprowadzic do problemu programowania liniowego, c) Zatem mozna ow
problem rozwiazac przy pomocy Solvera, d) Jak sprowadzic problem
komiwojazera do problemu liniowego napisane jest w roznych papierach
ktore mozna znalezc na googlu.
Co jeszcze wiecej mam ci napisac?
A.L.
PFG
> On Tue, 28 Dec 2004 21:39:02 +0100, "CosmoUN"
> <cosm...@poczta.nospam.onet.pl> wrote:
>
>
>>Użytkownik "A.L." <alewando_tego_nie@oddpost_tego_tez_nie.com> napisał w
>>wiadomości news:p212t0tjdto7t4154...@4ax.com...
>>
>>>Acha. Rozumiem. Chcesz gotowca.
>>
>>jakiego gotowca - czizus
> Nie rozumiem o co ci chodzi. Napisalem juz ze: [...]
> Co jeszcze wiecej mam ci napisac?
Gotowca :-)
--
Paweł
A.L.
No, chyba ze... Ale mi sie nie chce....
A.L.
Piotr Wyderski
> b) Problem komiwojazera mozna sprowadzic
> do problemu programowania liniowego
uzupelnie: liniowego calkowitoliczbowego, bo Jeszcze Ktos Cos Pomysli. ;-)
Pozdrawiam
Piotr Wyderski
A.L.
<wydersk...@ii.uni.wroc.pl> wrote:
>A.L. wrote:
>
>> b) Problem komiwojazera mozna sprowadzic
>> do problemu programowania liniowego
>
>uzupelnie: liniowego calkowitoliczbowego, bo Jeszcze Ktos Cos Pomysli. ;-)
>
Actually, pierwszy papier Dantziga z kims tam jaszcze, nie pamietam,
byl w czasach gdy programwoania liniowego calkowitoliczbowego jeszcze
nie bylo. Musieli sie wiec gimnastykwoac aby rozwiazanie
calkowitoliczbose dostac, co wykonali uzywajac prototypu techniki
ktora dzis nazywa sie "cutting planes".
A.L.
Piotr Wyderski
> Actually, pierwszy papier Dantziga z kims tam jaszcze, nie pamietam,
> byl w czasach gdy programwoania liniowego calkowitoliczbowego jeszcze
> nie bylo.
Wtedy nie bylo jeszcze nawet pojecia NP-zupelnosci (1971 r.). :-)
Pozdrawiam
Piotr Wyderski
A.L.
No, ale jakos sobie bez tego poradzili :) Moze gdyby to pojecie bylo
znane to by wiedzieli ze Nie Da Rady...
A.L.
India1
Jeśli jesteś na bakier z excelem, to sobie rozpisz to jako zadanie PL na
kartce (kupa roboty, ale jak załapiesz mechanizm, to już dalej nie będziesz
musiał rozpisywać) i wklep wszystko solverowi
A jeśli jesteś w miarę zaawansowany w kwestii excela, to po prostu napisz
makro, które za ciebie to rozwiąże.
A tak BTW - po polsku to jest to problem komiwojażera...
To naprawdę nie jest trudne - poczytaj co Ci moi przedmówcy napisali i
napewno uda Ci się to zrobić!
Użytkownik "CosmoUN" <cosm...@poczta.nospam.onet.pl> napisał w wiadomości
news:cqpfi9$rfr$1...@nemesis.news.tpi.pl...
A.L.
<indi...@USUNTOpoczta.onet.pl> wrote:
>Użytkownik "CosmoUN" <cosm...@poczta.nospam.onet.pl> napisał w wiadomości
>news:cqpfi9$rfr$1...@nemesis.news.tpi.pl...
>>
>> Użytkownik "CosmoUN" <cosm...@poczta.nospam.onet.pl> napisał w
>wiadomości
>> news:cqlsvg$pru$2...@atlantis.news.tpi.pl...
>> > Witam - na razie w arkuszu excela mam tylko macierz odleglosci a musze
>> > obliczyc tzw problem traveling salesman problem czyli przejscie po
>> > najkrotszej drodze przez wszystkie punkty (kazdy odwiedzajac tylko raz)
>i
>> > powrocic do poczatku - nie wiem jak to ustawic w solverze :(
>> >
>> > Sprawa jest bardzo pilna
>> > Pozdrawiam
>> >
>> >
>> naprawde nie wiecie jak to rozgryzc ??
Twoja odpowiedz, Indio1, powinna byc tutaj:
>
>
>Jeśli jesteś na bakier z excelem, to sobie rozpisz to jako zadanie PL na
>kartce (kupa roboty, ale jak załapiesz mechanizm, to już dalej nie będziesz
>musiał rozpisywać) i wklep wszystko solverowi
>A jeśli jesteś w miarę zaawansowany w kwestii excela, to po prostu napisz
>makro, które za ciebie to rozwiąże.
>A tak BTW - po polsku to jest to problem komiwojażera...
>To naprawdę nie jest trudne - poczytaj co Ci moi przedmówcy napisali i
>napewno uda Ci się to zrobić!
>
...albowiem takei sa zwyczaje na usenecie. A rozwiazalie problemu
komiwojazera przy pomocy LP jest dosyc trudne, albowiem wypada
wprowadzic ograniczenie ktore spowoduje ze bedzie dokladnie jedna
droga, a nie na przyklad dwie (eliminacja "subcykli"). Nie jest to
wcale takie oczywiste jak to zrobic, dlatego tez zapytalem czy
"mundry" ktory zadal facetowi to zadanie sam wie jak je prawidlowo
rozwiazac.
A.L.