Keverékek számítása

Algoritmusok

Sziasztok!
Egy matematikai problémán akadtam fenn a napokban. A gondom a következő:
Vannak eltérő mennyiségű különböző sűrűségű folyadékaim. Csak egymással keverhetők. Az lenne a célom, hogy megtudjam mennyi a legtöbb kikeverhető adott x sűrűségű folyadékom.
Az én elméletem szerint:

Sűrűség szerint sorbarendezem őket. Addig számolom az átlagos sűrűségüket lépésről lépésre, míg a célsűrűség alatt vagyok, utána csak a következőből (legsűrűbből) adok még hozzá. Tehát

C-célsűrűség
Mln - legsűrűbb nélküli mennyiség
Msz - további szükséges mennyiség
M1, M2 - mennyiségek
S1, S2 - sűrűségek
Sx - következő(legnagyobb) szűrűségű

C*(Mln+Msz)=M1*S1+M1*S1+...+Sx*Msz
innen már kifejezhető a mennyiség

Remélem érthető voltam... Kíváncsi lennék mi a véleményetek, hogyan lehetne hatékonyan megoldani, merre tapogatózzak.
Várom az ötleteket, előre is kösz!

  • 6650 megtekintés

( htmm v | 2010. 06. 23., sze – 15:02 )

Operációkutatás témakörben nézelődj.
Ha papíron szeretnéd megoldani (vagy saját programot írni rá), akkor a "lehetséges kanonikus alakú feladat" megoldását keresd. Ha csak megoldás kell gyorsan, akkor Excelben (Solver) vagy OOo-ban is meg lehet csinálni.

--
http://blog.htmm.hu/

( horvatha | 2010. 06. 23., sze – 15:11 )

Szívesen segítenék, de nem értem:

a) Hány folyadékod van?
b) Hányat tehetsz bele ezekből a keverékbe?
c) Az egyes folyadékokból, gondolom, egy-egy maximális mennyiség adott. De ennél kevesebbet tehetsz bele, ha akarsz?

Klasszikus operaciokutatasi temakor, keveresi feladat. Igy keress ra, van irodalom boven a temakorben.

Ahogy elottem ajanlottak, konnyeden megoldhato ez a feladat is Excelben, vagy Oo-ban, gondolom ennel pontosabb megoldas nem szukseges, ha igen, tudok ajanlani egy-ket celprogramot.

( Nyosigomboc v | 2010. 06. 23., sze – 16:07 )

Letoltod az LPsolve-ot, es kulso programkent vagy libkent meghivod. Linearis egyenlet/egyenlotlensegrendszereket old meg.
Ha m1,m2,m3, stb a tomeg, max1,max2,max3 a maximalis mennyiseg, amid van, m a celfolyadek tomege, r1,r2,r3, stb. a suruseg, r a celsuruseg, akkor:
max m
m1<=max1
m2<=max2
m3<=max3
m1>=0
m2>=0
m3>=0
m1+m2+m3=m
r1*m1+r2*m2+r3*m3=r*m (r-eket behelyettesited)
ezutan megoldatod az m-ekre, es megkapsz mindent.
Nyilvan ha akarod, lekodolhatod te is, csak minek..

Amugy a linearis programozas temakoreben is nezelodhetsz, egy tobbe-kevesbe hatekony algoritmus:
http://en.wikipedia.org/wiki/Simplex_algorithm

--
What's the difference between the Israeli navy and Somali pirates?
If you negotiate with Somali pirates,you can prevent them from murdering their victims. - sickipedia

( szemet | 2010. 06. 23., sze – 16:05 )

Feltételezheted hogy keveréskor a térfogatok pontosan összeadódnak?

Mert ez általában nem igaz a folyadékokra, gondolj pl. arra az esetre amikor homokot keversz a kavics közé: bár a tömeg összeadódik a térfogat nem...

Ha LP (nem MIP) solverek kellenek, akkor a barátaid:

lp_solve (beteg, mert az ubuntu/kubuntu 9.10/10.04 alapból tartalmazza)
glpk (benne a glpsol bináris, van mindenféle unix/w.* OS alá)
clp (www.coin-or.org:443, ubuntu repó-synapticban cbc részstringre keress rá!)

olvasható formátumot (lp-t, cplex lp-t csak az elsõ kettõ tud kezelni, a harmadik csak a de facto ipari standard MPS formátumot)

http://nocirc.org/

( lorinczi v | 2010. 06. 24., cs – 08:15 )

Így első ránézésre wxMaxima vagy R nyelven (cran.r-project.org) a limSolve package - de ezt a csomagot soha nem használtam.
---------------------------------------------------------------------------
Környezetvédelmi nyilatkozat: Ez a hozzászólás kizárólag reciklált elektronok felhasználásával íródott.