Kakorkoli že, tu je še drugi problem:
100 tovarn izdela po 100 kosov posameznega sestavnega dela za izdelavo rakete, za katero pa so potrebni sestavni deli iz vseh tovarn. Za končno sestavitev rakete je tako treba doseči, da bo v vsaki tovarni po en kos sestavnega dela iz vsake tovarne, da jih v tovarni sestavijo skupaj, vendar pa zmanjkuje časa in ga je na voljo le 100 ur. Na voljo imate 100 tovornjakov, od katerih lahko vsak naloži do 100 kosov sestavnih delov (vsi so enako veliki), vendar pa med tovarnami lahko potujejo le sorazmerno počasi: med poljubnima dvema tovarnama pridejo v 5 urah, prav tako pa potrebujejo 5 ur, da do poljubne tovarne pridejo od začetnega parkirišča.
Ali obstaja način, da tovornjaki uspejo sestavne dele razpeljati v 100 urah? (Pri čemer velja, da tovornjaki ne izgubljajo časa s prekladanjem in tudi nimajo premorov, naenkrat pa lahko v eni tovarni nakladata in razkladata dva tovornjaka.)
Sam bi se tega lotil s "simpleks metodo" – lahko da bi brcnil v temo 🙂 – ampak se mi niti pod razno ne da "zezati" s tem :).
problemi
Kaj pa logična uganka/nelogični misterij Ustavnega sodišča?
Anonimni, kot je bilo rečeno pri prvi objavi o cepljenju dlak, si lahko moj odziv o misteriju US preberete v posebni objavi, tu pa se osredotočimo na zastavljeno uganko. Problemi, "simpleks metoda" je tudi meni najljubša in pri zastavljeni nalogi človek v bistvu ne potrebuje svinčnika in papirja, zadošča že ena malo daljša avtobusna vožnja v mesto. (Če človeka seveda povsem ne okupirajo reklamni ekrani s sporočili SMS tipa "UCER JE BLO FAAAJN", "MARI MAHA MIHA <3" in "Zakaj se spet nism dost ucila slovooo???".) Kar človeka tu res zaskrbi, je Shashina predlagana rešitev naloge. Takole pravi: "Osnovna ideja rešitve… Beri dalje »
Matej, mislim, da si predlog reševanja s "simpleks metodo" narobe razumel (no, razen, če je šlo za šaljivo pripombo). Simpleks je čisto prava matematična metoda (algoritem) za reševanje problemov linearnega programiranja, med katere spadajo tudi transportni problemi.
Sam sem mislil na "simpleks metodo", kot jo je zgoraj opredelil shrink. Povsem resno sem mislil, vendar kolikor sem sam delal s to metodo in pretežno ravno na "transportnih problemih" je precej zamudna. Seveda govorim za primer, da se zgornjega primera lotiš "peš".
problemi
Shrink je kar zadel – metode simpleks ne poznam (kot nemara še marsikatere matematične metode ne) in sem mislil, da gre za malo nenavadno poimenovanje metode sanae mentis rusticorum (=zdrave kmečke pameti) oziroma navdahnjenega ugibanja o tem, kaj bi lahko bila prava rešitev. Še toliko bolj zato, ker je bilo govora o brcanju v temo. Pardon in hvala za pojasnilo. 🙂 Res pa je, da gre za tako brcanje v temo morda tudi pri pravi simpleks metodi, če jo je Shasha uporabil za svoj izračun. Shashina rešitev je namreč hudo potratna – s 100 tovornjaki potrebuje kar 100 ur, oziroma… Beri dalje »
No, vprašanje je, če se gornji problem sploh da zapisati kot linearni program; če se namreč da (nisem poskusil), potem simpleks vselej da optimalno rešitev (za nek izbrani kriterij optimizacije – pri transportnih problemih so ponavadi kriterij transportni stroški).
Seveda pa verjamem, da se da problem rešiti (tudi) s kako drugo metodo iz nabora metod operacijskih raziskav. Če je Tomaž Cedilnik tisti, za katerega mislim, da je (namreč: matematik), potem je zelo hitro našel pravi način. Nenazadnje bi ga moral tudi Shasha, ki ima PhD iz uporabne matematike.
Shrink, strinjam se, zato sem tudi napisal, da bi lahko brcnil v temo. Imaš pa vsekakor prav, da ti simpleks vselej da optimalno rešitev (kakor tudi metodi "stopalniki" in "modi"). No, moral bi si osvežiti znanje in preveriti ali je v primeru, če je sistem "degeneriran" (vedno) več rešitev.
Mogoče bi se dalo "poiskali" kriterialno funkcijo (max, min, zgoraj verjetno minimum) tudi za zgornji problem.
problemi
Tukaj sta obljubljeni rešitvi Tomaža Cedilnika in moje malenkosti (Tomaž Cedilnik je po mojem isti, na katerega misliva oba – v mojem primeru v kontekstu gimnazijskih spominov, čeprav ni ista generacija). Ker sta malo daljši, ju bom objavil vsako v svojem komentarju. Cedilnik predlaga najprej tovarne razdeliti na 4 skupine po 25 tovarn, potem pa sledi rešitev v več korakih (pri 2. in 3. vožnji se v knjigi sicer tudi ta rešitev malo zatipka, a se s takim pristopom s popravkom lapsusa vendarle izide). 1. vožnja: tovornjaki gredo vsak do svoje tovarne. nato izvirno po knjižnem besedilu: 2. vožnja: iz… Beri dalje »
Moja rešitev pa gre takole: 1. vožnja: vsak tovornjak pelje v svojo tovarno. 2. vožnja: vsak tovornjak pelje 50 kosov tovarne n iz n v n+1 (mod 100) (iz tovarne 1 v tovarno 2, iz tovarne 2 v tovarno 3 in vse do vožnje iz tovarne 100 v tovarno 1). 3. vožnja: tovornjaki peljejo po 25 kosov n in (n-1) v tovarno (n+2) (iz tovarne 1 v tovarno 3, itd.). 4. vožnja: tovornjaki peljejo po 12 kosov n do (n-3) v tovarno (n+4) (iz tovarne 1 v tovarno 5, itd.). 5. vožnja: tovornjaki peljejo po 6 kosov n do (n-7)… Beri dalje »
Matej, poskusi pobarati Shasho o tem problemu. Morda mu ne bo izpod časti odgovoriti. Drugače pa so lahko na videz preprosti problemi zelo trd oreh, vsaj kar se iskanja najboljše rešitve tiče. V tem smislu mi je zanimiv problem kuharja, ki speče n palačink različnih velikosti in jih povsem poljubno razvrsti eno na drugo na krožnik. Vprašanje je sedaj, kolikšno je najmanjše možno število premetavanj palačink, da bodo te razporejene od največje do najmanjše. Verjetno je komu znano, da je ta problem (ki je kar težek) reševal med študijem na Harvardu tudi Bill Gates, katerega rešitev je čez nekaj let… Beri dalje »
Shrink, lahko poveš rešitev glede problema "kuhar"?
V primeru, da bi kuhar poljubno (naključno) že polagal palačinke od največje do najmanjše – zelo majhna verjetnost, pa vendarle – bi bilo najmanjše možno število premetavanj 0. Bi bila naloga že opravljena:).
problemi
Ha, očitno gre za tole nalogo, išče pa se najmanjše število obračanj, pri katerem vedno (tudi iz najslabšega možnega izhodišča) prideš do prave razporeditve.
Na prvo žogo je očitno, da pri n palačinkah število ni večje od (2n-3), a očitno obstaja še boljša (in zapletenejša) rešitev.
Tako je, Matej. Optimalna rešitev pa leži med 15n/14 in 18n/11:
http://en.wikipedia.org/wiki/Pancake_sorting#The_original_pancake_problem