Oletetaan, että meillä vaikka kasa neljänlaisia pelikortteja. Merkitään eri kortteja A,B,C,D. Näissä korteissa on kolme eri arvoa, vaikka A-korteissa (x_a, y_a, z_a) jne. (myöhemmin A:n x-arvo on siis tuo x_a). Nyt näitä kortteja nostetaan käteen jossain suhteessa niin, että korttien z-arvot saavat yhteensä arvon N. Tehtävänä on maksimoida x- ja y-arvojen summa ehdolla sum z=N ja 0,9x < y < 1,1x, eli pitäisi löytää millä suhteella kortteja kannattaa käteen kerätä.
Millä työkaluilla tuota voisi lähteä ratkomaan?
Millä työkaluilla tuota voisi lähteä ratkomaan?
Vastaukset 5
Vanhimmat
Vaikuttaisi lineaarisen ohjelmoinnin tehtävältä (linear programming) eli simplex-algoritmi varmaan sopii tähän.
Eli pitää löytää tuntemattomat p1,p2,p3,p4 (suhteet)
Joille pitää
opitimointitehtävä
max(x y)
rajoitteet
p1 p2 p3 p4=1
p1*Za p2*Zb p3*Zc p3*Zd=N
p1*(0,9Xa-Ya) p2*(0,9*Xb-Yb) p3*(0,9Xc-Yc) p4*(0,9Xd-Yd)0
Tämä ei ole aivan standardimuoto lineaarisen optimoinnin probleemasta, mutta se voidaan kyllä saattaa sellaiseen muotoon. Simplex algoritmilla sitten ratkeaa!!
Tarkennan vielä sen verran, että noissa erilaisissa korteissa on siis tosiaan aina vakioarvot, kuten arvasitkin. Numeeriset arvot ovat seuraavat:
A=(65,35,1)
B=(35,60,1)
C=(40,50,1)
D=(115,55,2)
Kuitenkin nyt kun lähtee asiaa pohtimaan järjellä, niin kyseessä on x- ja y-arvojen maksimisumman etsintä annetulla ehdolla. Tätä vasten tuo viimeinen luku itse asiassa on tavallaan vain suhdeluku kahden ensimmäisen suhteen ja D voidaan tulkita yhtälailla arvoille D=(57.5,27.5,1). Jolloin meillä on
A=(65,35,1)
B=(35,60,1)
C=(40,50,1)
D=(57.5,27.5,1)
Koska kyseessä on maksimisumman etsintä, niin käsittääkseni riittää edelleen jos yksinkertaistetaan tilannetta summaamalla suoraan jokaisen korttityypin x- ja y-arvot. Eli
A=(100,1)
B=(95,1)
C=(90,1)
D=(85,1)
Kuitenkin nyt hukataan haettu suhdeluku, mutta onko tämä ongelma, koska selvästikin A ja B antavata suurimmat summat suoraan ja tiedämme että niiden arvot (65,35) ja (35,60) kuitenkin annetun suhteen täyttävät, jos niitä otetaan 50-50 suhteella?
Meneekö tässä päättelyssä jotain pieleen?
... että tietty ehto sallii maksimisumman, joka saataisiin ilmankin kyseistä ehtoa, voit tietysti teeskennellä, ettei sitä ehtoa ole olemassa maksimoinnin kannalta.
Jos tehtävä on moniosainen, ja seuraavaksi pyydetään optimoimaan jotain muuta, ehdot on jälleen otettava huomioon.
Toki on harvinaista, että kurssitehtävässä olisi turhaa infoa, mutta en tiedä mistä sen olet repäissyt.
... tyytyväinen tapaan, jolla puolitit D-kohdan. Puolikkaita kortteja kun ei kuitenkaan voi valita. Jos teet niin, joudut lisäämään ehdon, että uusia D-arvoja voit valita vain parillisen määrän.
Alkuperäisen ehdon toimivuus myös kyseenalaistuu, kun D-kohta on pilkottu?
Muodollisuus ei ehkä muuta loppupäätelmiäsi, mutta on silti tärkeää oikeellisuuden kannalta.
Kyseessä on eräs peli, johon haeskelin parasta lähestymistapaa. Tarkemmin sanoen sotapeli, jota hahmotin pelikorttien muodossa.