Avatar billede trp79 Nybegynder
15. oktober 2006 - 14:50 Der er 10 kommentarer og
1 løsning

Et lineært programmeringsproblem?

Hejsa
Jeg kunne godt tænke mig, at vide om følgende problemstilling kan opgøres i et lineær programmerings problem, og i så fald hvordan et sådan ville se ud.

Problemet.
Landmænd indgår gylleaftaler med hinanden fordi, der er nogle der er nogen, der har for meget gylle og andre, der har for lidt gylle til sine marker. Vi vil så gerne lave de mest optimale gylleaftaler for en række landmænd, så de indgår gylleaftaler med landmænd, der ligger geografisk tæt på dem.
Et eks:
Landmand A har en gylleaftale med landmand P. Landmand Q har en gylleaftale med Landmand B. Landmand A bor tæt på landmand B og langt fra P, der bor tæt på Q. Altså ville det være mere optimalt at A og B indgik en gylleaftale, og at P og Q gjorde det.

Vi har så 200 landmænd, som har under og overskud af gylle, og vi vil så gerne finde ud af hvem, der bør have gylleaftaler med hvem så der er optimeret på afstand.

Det er naturligvis forskelligt, hvor meget gylle landmændene har i over- og underskud. Der kan godt være flere landmænd om at dække en anden landmands gyllebehov.

Kan dette problem opstilles og løses gennem lineær programmering, og i så fald hvordan kunne det gøres?
Avatar billede arne_v Ekspert
15. oktober 2006 - 15:36 #1
hvis

a(i,j) er gyllen fra landmand i's stald til landmands j's mark
c1(i) er den totale gylle mængden fra landmands i's stald
c2(j) er den maksimale gylde som må spredes på landmands j's mark
c3(i,j) er antal km mellem i og j

så må det gælde at

for alle j:
  sum over i af a(i,j) <= c2(j)

for alle i:
  sum over j af a(i,j) = c1(i)

den funktion som skal minimeres er:
  sum over i sum over j af a(i,j)*c3(i,j)
Avatar billede trp79 Nybegynder
15. oktober 2006 - 16:42 #2
Der skal jo så også tages hensyn til hvor meget der forskellige kan levere(A,B,C). Jeg har forsøgt at illustrer problemet i understående - jeg håber ikke formateringen fucker. Men landmand O har fx et DE(gylle) behov på 7 og 3km til landmand A.
    O                P                Q       
    DE-behov    KM    DE-behov    KM    DE-behov    KM    DE-overskud
A    7            3    2            1    6            9    3
B    7            9    2            6    6            2    7
C    7            1    2            3    6            2    5
Avatar billede trp79 Nybegynder
15. oktober 2006 - 16:44 #3
Den fuckede så... jeg prøver igen(DE overskud viser hvor meget gylle henholdsvis landmand A, B og C har i overskud):
    O                P                Q       
    DE-behov    KM    DE-behov    KM    DE-behov    KM    DE-overskud
A    7            3    2            1    6            9    3
B    7            9    2            6    6            2    7
C    7            1    2            3    6            2    5
Avatar billede trp79 Nybegynder
15. oktober 2006 - 16:46 #4
nå, det er vist ikke så nemt at formatere :( håber det giver lidt mening alligevel. eller kan jeg sende et excel ark eller ligge det tilgængelig på nettet når jeg kommer hjem engang.
Avatar billede arne_v Ekspert
16. oktober 2006 - 01:49 #5
men er det ikke bare at smide ind i mine ligninger ?
Avatar billede trp79 Nybegynder
16. oktober 2006 - 10:27 #6
Jo det er det vist - du havde jo taget hensyn til hvor meget de forskellige kan levere. Jeg må lige se og få genopfrisket matematikken, så jeg kan minimere din funktion - måske excel eller lign. efterfølgende kan hjælpe med det...
Avatar billede arne_v Ekspert
16. oktober 2006 - 13:06 #7
det er jo simplex algoritmen

den kan programmeres !!!!
Avatar billede trp79 Nybegynder
16. oktober 2006 - 13:27 #8
Jamen, så kunne det da være at jeg skulle kaste mig over det i aften :)
Avatar billede trp79 Nybegynder
21. oktober 2006 - 17:11 #9
Jeg valgte så løsningen gennem Excel, da det blot er for at illustrer, at det kan lade sig gøre og da det ikke er en kodemæssig opgave jeg er i gang med.

Vil du ikke smide et svar Arne?

Tak for hjælpen
Avatar billede arne_v Ekspert
21. oktober 2006 - 17:37 #10
jeg anede ikke engang at man kune lave den slags i Execl

:-)
Avatar billede trp79 Nybegynder
21. oktober 2006 - 18:21 #11
Det gjorde jeg nu heller ikke - men det var der heldigvis nogle, der vidste noget om herinde :)
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Computerworld tilbyder specialiserede kurser i database-management

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester