---

Hejsa.
Jeg er ny til denne nyhedsgruppe, men håber der er nogen, der kender lidt
til dette.

Mit problem er at jeg har et LP-problem som skal dualiseres. Jeg kender de
generelle dualitetsregler, men jeg synes ikke rigtigt at jeg selv kan gøre
det. Findes der en eller anden derude, som er skrap til det? Eller er der
en, der kender et program til PC'en der kan gøre sådan noget? (Jeg har
Scientific WorkPlace 3.0 men den kan ikke - eller jeg kan i hvert fald ikke
finde det). Eller nogle rigtig gode sider på nettet, der kunne hjælpe mig
lidt videre...?

Håber på hurtigt svar...

Venlig hilsen
Pernille

Problemet ser således ud:
max 10x11 + 6x12 + 12x13 + 8x14 + 15x21 + 18x22 + 5x23 + 11x24 + 17x31 +
10x32 + 13x33 + 16x34 + 14x41 + 12x42 + 13x43 + 10x44 + 14x51 + 16x52 + 6x53
+ 12x54 (tallene efter x'et er indextal fra en matrice!)

s.t x11 + x12 + x13 + x14 =< 1
x21 + x22 + x23 + x24 =< 1
x31 + x32 + x33 + x34 =< 1
x41 + x42 + x43 + x44 =< 1
x51 + x52 + x53 + x54 =< 1
x11 + x21 + x31 + x41 + x51 = 1
x12 + x22 + x32 + x42 + x52 = 1
x13 + x23 + x33 + x43 + x53 = 1
x14 + x24 + x34 + x44 + x54 = 1
xij >= 0 i = 1, 2, 3, 4, 5 j = 1, 2, 3, 4

---

Der måske noget du kan bruge her:

http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html

Men ellers vil "Solveren" i Excel måske kunne klare dit LP-problem.
I øvrigt synes jeg problemet ser noget mystisk ud!

Mvh

Sune T.



Pernille Bennedsen <pernille1000@hotmail.com> skrev i en
nyhedsmeddelelse:3ccd6426$0$73225$edfadb0f@dspool01.news.tele.dk...
> Hejsa.
> Jeg er ny til denne nyhedsgruppe, men håber der er nogen, der kender lidt
> til dette.
>
> Mit problem er at jeg har et LP-problem som skal dualiseres. Jeg kender
de
> generelle dualitetsregler, men jeg synes ikke rigtigt at jeg selv kan gøre
> det. Findes der en eller anden derude, som er skrap til det? Eller er der
> en, der kender et program til PC'en der kan gøre sådan noget? (Jeg har
> Scientific WorkPlace 3.0 men den kan ikke - eller jeg kan i hvert fald
ikke
> finde det). Eller nogle rigtig gode sider på nettet, der kunne hjælpe mig
> lidt videre...?
>
> Håber på hurtigt svar...
>
> Venlig hilsen
> Pernille
>
> Problemet ser således ud:
> max 10x11 + 6x12 + 12x13 + 8x14 + 15x21 + 18x22 + 5x23 + 11x24 + 17x31 +
> 10x32 + 13x33 + 16x34 + 14x41 + 12x42 + 13x43 + 10x44 + 14x51 + 16x52 +
6x53
> + 12x54 (tallene efter x'et er indextal fra en matrice!)
>
> s.t x11 + x12 + x13 + x14 =< 1
> x21 + x22 + x23 + x24 =< 1
> x31 + x32 + x33 + x34 =< 1
> x41 + x42 + x43 + x44 =< 1
> x51 + x52 + x53 + x54 =< 1
> x11 + x21 + x31 + x41 + x51 = 1
> x12 + x22 + x32 + x42 + x52 = 1
> x13 + x23 + x33 + x43 + x53 = 1
> x14 + x24 + x34 + x44 + x54 = 1
> xij >= 0 i = 1, 2, 3, 4, 5 j = 1, 2, 3, 4
>
>

---

Pernille Bennedsen wrote:

> Mit problem er at jeg har et LP-problem som skal dualiseres. Jeg kender
> de generelle dualitetsregler, men jeg synes ikke rigtigt at jeg selv kan
> gøre det.

Det her bygger på Mas-Colell mfl. "Microeconomics" (1995, Oxford UP)
appendix M.M (sæt din font til Courier eller lignende, ellers er resten
ulæseligt).

Dit problem kan skrives fx. således:

Max f(x) hvor X er en 20-dimensionel vektor [x11, x12, ... x54]
og f er sum(i,j) af aij gange xij (i,j) som du selv nævner.
st. Ax <= c hvor A er en 13x20 matrix (fordi ax = 1 <=> ax=>1 OG ax<=1)
idet der er 5 uligheder og 4 ligheder (2x4=8 uligheder)
= 13 uligheder), mens c er en 13-dim. vektor.

Matricen A og vektoren c vil se ud noget a la:

A c

1 1 1 1 0 0 0 0 ... 1
0 0 0 0 1 1 1 1 0 ... 1
0 ... 0 1 1 1 1 0 ... 1
0 ... 1
0 ... 1
1 0 0 0 1 0 0 0 0 ... 1
1 0 0 0 1 0 0 0 0 ... 1
1 0 0 0 1 0 0 0 0 ... 1
1 0 0 0 1 0 0 0 0 ... 1
-1 0 0 0 -1 0 0 0 0 ... -1
-1 0 0 0 -1 0 0 0 0 ... -1
-1 0 0 0 -1 0 0 0 0 ... -1
-1 0 0 0 -1 0 0 0 0 ... -1

Til dette problem findes en skyggepris til hver af de tretten uligheder,
den 13-dim vektor p. Den duale løsning er således (ligning M.M.2):

Min c1 l1 + c2 l2 + ... c13 l13
st. a11 l1 + a21 l2 + ... a13,1 l13 >= f'(x1) (for dig er f'(x1)=10
a21 l1 ... >= f'(x2) (=6)
...
a20,1 l1 ...

l er nok fornuftig at få regnet ud i et eller andet program. Jeg ville
bruge GAMS (fordi jeg er hjemmevant her), men hvis Excel kan er det sikkert
nemmere for de fleste. Lidt søgning med de rigtige søgeord giver lidt flere
eksempler:

http://www.google.com/search?hl=en&q=LP+dual+problem

Er det sådan noget polit-operationsanalyse?


--
Venlige hilsner Mikkel