Olkoon matriisimuodossa esitettynä yhtälöryhmä Ac = b s.e. tuntemattomia on enemmän kuin yhtälöitä, eli esim.
a11 c1 a12 c2 a13 c3 a14 c4 = b1
a21 c1 a22 c2 a23 c3 a24 c4 = b2
a31 c1 a32 c2 a33 c3 a34 c4 = b3
Perushavainto on, että yhtälön tuntemattomat eivät ratkea yksikäsitteisesti, mutta ne voidaan ratkaista jonkin tuntemattoman funktiona. Olkoon tuo tuntematon c1:
a12 c2 a13 c3 a14 c4 = b1 - a11 c1
a22 c2 a23 c3 a24 c4 = b2 - a21 c1
a32 c2 a33 c3 a34 c4 = b3 - a31 c1
Ratkaisuna saadaan c2(c1), c3(c1), c4(c) jotka tietenkin tässä tapauksessa ovat lineaarisuuden vuoksi suoria. On myös olemassa tiettyjä rajoituksia, esim. c2,c3,c4 ovat välillä [0,1]. Tehtävänä on määrittää se pienin c1:n arvo, joka toteuttaa yhtälöryhmän ja rajoitteet. Onko tämä ylipäätänsä LP-ongelma ja kuinka tämä voidaan pyöritellä kanoniseen muotoon jotta se voidaan syöttää ratkaisijalle?
Tässä tapauksessa on tietenkin mahdollista ja helppoa ratkaista yhtälöryhmä ja piirtää kolme suoraa sekä ratkaista "rajoittavin" suora, mutta olisin kiinnostunut optimointiteoriasta, koska graafinen ratkaisu käy nopeasti mahdottomaksi kun yhtälöiden ja tuntemattomien määrää kasvatetaan.
a11 c1 a12 c2 a13 c3 a14 c4 = b1
a21 c1 a22 c2 a23 c3 a24 c4 = b2
a31 c1 a32 c2 a33 c3 a34 c4 = b3
Perushavainto on, että yhtälön tuntemattomat eivät ratkea yksikäsitteisesti, mutta ne voidaan ratkaista jonkin tuntemattoman funktiona. Olkoon tuo tuntematon c1:
a12 c2 a13 c3 a14 c4 = b1 - a11 c1
a22 c2 a23 c3 a24 c4 = b2 - a21 c1
a32 c2 a33 c3 a34 c4 = b3 - a31 c1
Ratkaisuna saadaan c2(c1), c3(c1), c4(c) jotka tietenkin tässä tapauksessa ovat lineaarisuuden vuoksi suoria. On myös olemassa tiettyjä rajoituksia, esim. c2,c3,c4 ovat välillä [0,1]. Tehtävänä on määrittää se pienin c1:n arvo, joka toteuttaa yhtälöryhmän ja rajoitteet. Onko tämä ylipäätänsä LP-ongelma ja kuinka tämä voidaan pyöritellä kanoniseen muotoon jotta se voidaan syöttää ratkaisijalle?
Tässä tapauksessa on tietenkin mahdollista ja helppoa ratkaista yhtälöryhmä ja piirtää kolme suoraa sekä ratkaista "rajoittavin" suora, mutta olisin kiinnostunut optimointiteoriasta, koska graafinen ratkaisu käy nopeasti mahdottomaksi kun yhtälöiden ja tuntemattomien määrää kasvatetaan.
Vastaukset
Vanhimmat
Ei vielä vastauksia
Aloittaja odottaa vastauksia. Kerro oma näkemyksesi ensimmäisenä.