Lineaarista optimointia etc.

[viesti Survo-keskustelupalstalla (2001-2013)]

Survossa on ollut mahdollista ratkaista lineaarisen optimoinnin ongelmia
ja kahden hengen nollasummapelejä SIMPLEX-ohjelman ja matriisitulkin
avulla tavalla, joka esitetään mm. Survon englanninkielisen käyttöoppaan
http://www.survo.fi/books/1992/Survo_Book_1992_with_comments.pdf 
sivuilla 390-392.
Erityisesti näiden juttujen opetusta ajatellen olen laatinut kaksi
sukroa, jotka perustuvat ilmaisohjelman lp_solve
http://lpsolve.sourceforge.net/5.5/ 
käyttöön suoraan Survosta.
Sukro /LP_SOLVE ratkaisee lineaarisen optimointiongelman ja /ZS_GAME
kahden hengen nollasummapelin.
Nämä uudet sukrot kuten myös erillinen Survo-ohjelmien päähakemistoon
DD <Survo>\U sijoitettava LP_SOLVE.EXE tulevat mukaan versiosta
3.32 lähtien, mutta ne on mahdollista ottaa käyttöön myös Survon
verkkosivuilta osoitteista
http://www.survo.fi/tmp/lp_solve.exe 
http://www.survo.fi/tmp//LP_SOLVE.TUT 
http://www.survo.fi/tmp//ZS_GAME.TUT 

Tässä esimerkkinä em. oppaan sivulla 392 olevan pelin ratkaiseminen:
Kaikki komennon /ZS_GAME A jälkeiset rivit ovat toimituskenttään
ilmaantuvaa tulostusta.
Siitä näkyy mm., miten tehtävä muunnetaan "selväkieliseksi" LP-ongelmaksi
ja miten pelin optimistrategiat (#P ja #Q) on poimittu suoraan
lp_solve-ohjelman antamasta ratkaisusta.

MATRIX A
///  B1  B2  B3  B4
A1    3   6   1   4
A2    5   2   4   2
A3    1   4   3   5

MAT SAVE A
/ZS_GAME A

Solving zero-sum game A:
MAT LOAD A
MATRIX A
///            B1       B2       B3       B4
A1              3        6        1        4
A2              5        2        4        2
A3              1        4        3        5


MAT DIM A /* rowA 3 colA 4
MAT #A=A           / *#A~A 3*4
Add a constant to all elements to make them non-negative:
MAT MIN=MIN(MIN(#A)')
-MAT_MIN(1) -1
MAT #A1=CON(3,4,0)
MAT #A=#A+#A1      / *#A~A+0 3*4

Presenting the problem as an LP program:
SAVEP CUR+1,E,zs_game.lp
min: v;
u1 >= 0;
u2 >= 0;
u3 >= 0;
u4 >= 0;
3 u1 + 6 u2 + 1 u3 + 4 u4 <= v;
5 u1 + 2 u2 + 4 u3 + 2 u4 <= v;
1 u1 + 4 u2 + 3 u3 + 5 u4 <= v;
u1 + u2 + u3 + u4 = 1;

Solving the problem zs_game.lp by the lp_solve program:
>G:\e\u\lp_solve zs_game.lp -S4 >D:\ARK\lpresult.txt
LOADP lpresult.txt

Value of objective function: 3.25000000

Actual values of the variables:
v                            3.25
u1                      0.0833333
u2                       0.416667
u3                            0.5
u4                              0

Actual values of the constraints:
R1                              0
R2                              0
R3                              0
R4                              1

Objective function limits:
                                 From            Till       FromValue
v                       2.220446e-016          1e+030         -1e+030
u1                         -0.2307692               1         -1e+030
u2                                 -3       0.1578947         -1e+030
u3                               -0.5       0.1666667         -1e+030
u4                             -0.125          1e+030       0.5263158

Dual values with from - till limits:
                           Dual value            From            Till
R1                             -0.125      -0.6666667               2
R2                               -0.5            -0.5             2.5
R3                             -0.375              -2       0.2857143
R4                               3.25   6.217249e-015          1e+030
v                                   0         -1e+030          1e+030
u1                                  0         -1e+030          1e+030
u2                                  0         -1e+030          1e+030
u3                                  0         -1e+030          1e+030
u4                              0.125      -0.1538462       0.5263158

Solution of the game A: Value=3.25
Optimal strategies:

(MATRIX #P)
///          Prob
A1       0.125000
A2       0.500000
A3       0.375000

(MATRIX #Q)
///          Prob
B1       0.083333
B2       0.416667
B3       0.500000
B4       0.000000

• lp_solve kokeilu (Petri Palmu 23.11.2012 15:38)

Luettelo keskustelunaiheista

Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!