Title: Operaatiotutkimus

Tarkastellaan taulukossa esitettyä kuljetusongelmaa:

\( \begin{array}{c|ccc|l} & 1 & 2 & 3 & \text{Tarjonnat} \\ \hline 1 & [value] & [value] & [value] & 20 \\ \hline 2 & [value] & [value] & [value] & 12 \\ \hline 3 & [value] & [value] & [value] & 8 \\ \hline & 20 & 15 & 5 & 40 \\ & \text{Ky} & \text{syn} & \text{nät} \end{array} \)

Etsi luoteiskulman säännöllä oheiselle kuljetustaulukolle käypä aloituskantaratkaisu ja optimoi ratkaisu kuljetusalgoritmia käyttäen. Taulukon alkiot ovat yksikkökuljetuskustannuksia euroina.

Luoteiskulman säännöllä saadaan seuraavanlainen aloituskantaratkaisu:

 |  | \(v_1\) | \(v_2\) | \(v_3\)
 |  | \(1\) | \(2\) | \(3\)
\(u_1\) | \(1\) | 20 [value] | [value] | [value]
\(u_2\) | \(2\) | 0 [value] | 12 [value] | [value]
\(u_3\) | \(3\) | [value] | 3 [value] | 5 [value]

Muodosta kantamuuttujia vastaavat apumuuttujayhtälöt ja laske arvot \(u_{i}\):lle ja \(v_i\):lle asettamalla \(u_{1}=0\).

\(u_1\) | \(=\) |  |  | \(v_1\) | \(=\) |
\(u_2\) | \(=\) |  |  | \(v_2\) | \(=\) |
\(u_3\) | \(=\) |  |  | \(v_3\) | \(=\) |

Määritä ei-kantamuuttujia vastaavat indeksit (esim. \(x_{11}\) syötä kenttään 11) ja näitä vastaavien kertoimien arvot

Ei-kantamuuttujia \(x_{\_\_}\) |  | Vastaava kerroin \(\overline{C}_{ij}\)

Onko optimi?

Saapuva muuttuja \(x_{\_\_}\)    (esim. \(x_{11}\) syötä kenttään 11)

Lähtevä muuttuja \(x_{\_\_}\)    (esim. \(x_{11}\) syötä kenttään 11)

Uusi käypä kantaratkaisu: (syötä tyhjiin arvoihin -)

 |  | \(v_1\) | \(v_2\) | \(v_3\)
 |  | \(1\) | \(2\) | \(3\)
\(u_1\) | \(1\) | [value] | [value] | [value]
\(u_2\) | \(2\) | [value] | [value] | [value]
\(u_3\) | \(3\) | [value] | [value] | [value]

Muodosta kantamuuttujia vastaavat apumuuttujayhtälöt ja laske arvot \(u_{i}\):lle ja \(v_i\):lle asettamalla \(u_{1}=0\).

\(u_1\) | \(=\) |  |  | \(v_1\) | \(=\) |
\(u_2\) | \(=\) |  |  | \(v_2\) | \(=\) |
\(u_3\) | \(=\) |  |  | \(v_3\) | \(=\) |

Määritä ei-kantamuuttujia vastaavat indeksit (esim. \(x_{11}\) syötä kenttään 11) ja näitä vastaavien kertoimien arvot

Ei-kantamuuttujia \(x_{\_\_}\) |  | Vastaava kerroin \(\overline{C}_{ij}\)

Onko optimi?

Optimaaliset kuljetuskustannukset ovat:

\(z_{min} = \,\) (€)
Feedback: Mallivastaus Luoteiskulman säännöllä saadaan seuraavanlainen aloituskantaratkaisu: | | \(v_1\) | \(v_2\) | \(v_3\) | | \(1\) | \(2\) | \(3\) \(u_1\) | \(1\) | 20 [value] | [value] | [value] \(u_2\) | \(2\) | 0 [value] | 12 [value] | [value] \(u_3\) | \(3\) | [value] | 3 [value] | 5 [value] Muodosta kantamuuttujia vastaavat apumuuttujayhtälöt ja laske arvot \(u_{i}\):lle ja \(v_i\):lle asettamalla \(u_{1}=0\). \(u_1\) | \(=\) | [value] | | \(v_1\) | \(=\) | [value] \(u_2\) | \(=\) | [value] | | \(v_2\) | \(=\) | [value] \(u_3\) | \(=\) | [value] | | \(v_3\) | \(=\) | [value] Määritä ei-kantamuuttujia vastaavat indeksit (esim. \(x_{11}\) syötä kenttään 11) ja näitä vastaavien kertoimien arvot Ei-kantamuuttujia \(x_{\_\_}\) | | Vastaava kerroin \(\overline{C}_{ij}\) [value] | | [value] [value] | | [value] [value] | | [value] [value] | | [value] Onko optimi? [value] Saapuva muuttuja \(x_{\_\_}\) [value] (esim. \(x_{11}\) syötä kenttään 11) Lähtevä muuttuja \(x_{\_\_}\) [value] (esim. \(x_{11}\) syötä kenttään 11) Uusi käypä kantaratkaisu: (syötä tyhjiin arvoihin -) | | \(v_1\) | \(v_2\) | \(v_3\) | | \(1\) | \(2\) | \(3\) \(u_1\) | \(1\) | [value] [value] | [value] [value] | [value] [value] \(u_2\) | \(2\) | [value] [value] | [value] [value] | [value] [value] \(u_3\) | \(3\) | [value] [value] | [value] [value] | [value] [value] Muodosta kantamuuttujia vastaavat apumuuttujayhtälöt ja laske arvot \(u_{i}\):lle ja \(v_i\):lle asettamalla \(u_{1}=0\). \(u_1\) | \(=\) | [value] | | \(v_1\) | \(=\) | [value] \(u_2\) | \(=\) | [value] | | \(v_2\) | \(=\) | [value] \(u_3\) | \(=\) | [value] | | \(v_3\) | \(=\) | [value] Määritä ei-kantamuuttujia vastaavat indeksit (esim. \(x_{11}\) syötä kenttään 11) ja näitä vastaavien kertoimien arvot Ei-kantamuuttujia \(x_{\_\_}\) | | Vastaava kerroin \(\overline{C}_{ij}\) [value] | | [value] [value] | | [value] [value] | | [value] [value] | | [value] Onko optimi? [value] Optimaaliset kuljetuskustannukset ovat: \(z_{min} = \,\)[value] (€)

Q: Tarkastellaan lineaarista optimointiongelmaa, jonka käypä ratkaisualue koostuu sellaisista pisteistä \((x_1,x_2)\in \mathbb R^2\), jotka toteuttavat ehdot:

\[ \qquad\left\{ \begin{aligned} x_1 + x_2 &\geq[value],\\ x_1 + x_2 &\leq[value],\\ x_1 - x_2 &\leq[value],\\ x_2 &\geq[value],\\ x_1 & \text{ rajoittamaton.} \end{aligned} \right. \]

Piirrä itsellesi kuva käyvästä ratkaisualueesta. Tämän jälkeen määritä graafista ratkaisua hyödyntäen tehtävän optimaalinen ratkaisu (jos sellainen on olemassa), joka siis sisältää sekä optimipisteen että optimiarvon kun tavoitteena on

 | Optimipiste | Optimiarvo
(a) minimoida
\(z = -x_1 + 2x_2\)
(b) maksimoida
\(z = 2x_1 + x_2\)
(c) minimoida
\(z = x_1 + 3x_2\)
(d) maksimoida
\(z = x_2\)

Ohjeita:

Jos optimia ei ole olemassa esimerkiksi optimointialueen tietynsuuntaisen rajaamattomuuden vuoksi, anna optimipiste \((x_1,x_2)\) tyhjänä listana [] ja optimiarvo oikeanmerkkisenä äärettömyytenä (\(\infty\) kirjoitetaan inf).

Jos taas jostain syystä alueen sisällä tapahtuisi nollalla jakoa jossakin pisteessä, anna piste tavalliseen tapaan, mutta merkitse funktion arvoa oikeanmerkkisellä äärettömyydellä.
Feedback: Optimointialue:
  Hint: Vihje 1: Ratkaise jokainen epäyhtälöryhmän epäyhtälö muuttujan \(x_2\) suhteen, jos vain mahdollista, ja piirrä kyseisten funktioiden kuvaajat samaan kuvaan.
  Hint: Vihje 1: Ratkaise jokainen epäyhtälöryhmän epäyhtälö muuttujan \(x_2\) suhteen, jos vain mahdollista, ja piirrä kyseisten funktioiden kuvaajat samaan kuvaan. Vihje 2: Optimointialue
  Hint: Vihje 1: Ratkaise jokainen epäyhtälöryhmän epäyhtälö muuttujan \(x_2\) suhteen, jos vain mahdollista, ja piirrä kyseisten funktioiden kuvaajat samaan kuvaan. Vihje 2: Optimointialue Vihje 3: Ratkaise funktio \(z(x_1,x_2)\) muuttujan \(x_2\) suhteen, ja liikuta syntyneen polynomin kuvaajaa varioimalla sen vakiotermiä haluttuun suuntaan, kunnes optimointialueen raja tulee vastaan.

/*Tyylittelyjä*/ /*ITSE TEHTÄVÄNANTO*/ /* [Image: Tässä pitäisi olla pixabaysta vedetty kuva.] */

Pieni maalitehdas tuottaa kahta maalityyppiä sisä- ja ulkokäyttöä varten, joiden päivittäistä valmistusmäärää tonneissa merkitään vastaavasti muuttujilla \(x_1\) ja \(x_2\). Maalien valmistuksessa tarvitaan kahta eri raaka-ainetta, \(M_1\) ja \(M_2\). Ongelman muut lähtötiedot ovat oheisen taulukon mukaiset:

 | Tonnia raaka-ainetta maalitonnia kohden
 | Sisämaali | Ulkomaali
\(M_1\) | [value] | [value]
\(M_2\) | [value] | [value]
Tuotto per maalitonni \((1\,000\,\mathrm €)\) | [value] | [value]

Ohje:

Muuttujat \(x_1\) ja \(x_2\) syötetään vastauskenttiin vastaavasti x1 jax2.

Anna vastaukset muodossa \[a_1x_1 + a_2x_2\, \mathcal R\, c,\] missä \(a_1,a_2\) sekä \(c\) ovat vakioita ja \(\mathcal R\) on jokin relaatioista \(=\) (=), \(\leq\) (<=) tai \(\geq \) (>=).

Itse tehtävä, jossa oletetaan tuotannon vastaavan kysyntää:

Muotoile seuraavat sanallisesti annetut rajoitteet matemaattisiksi yhtälöiksi tai epäyhtälöiksi:

1. Sisämaalin päivittäinen kysyntä ylittää ulkomaalin kysynnän vähintään [value] tonnilla.
2. Maalien yhteenlaskettu päivittäinen valmistusmäärä on enintään [value] tonnia.
3. Raaka-aineen \(M_1\) päivittäinen käyttö on enintään [value] tonnia.
4. Raaka-aineen \(M_2\) päivittäinen käyttö on vähitään [value] tonnia.
5. Raaka-aineiden \(M_1\) ja \(M_2\) yhteenlaskettu kulutus on enintään [value] tonnia.
6. Maalien myynnistä saatavan kokonaistuoton on oltava vähintään [value] €.
7. Sisämaalin osuus kokonaistuotannosta on oltava vähintään [value] prosenttia.
8. Ulkomaalin osuus kokonaistuotannosta ei saa ylittää [value] prosenttia.

Tehtävänanto:

/* [value][value][value][value][value]
[value][value][value][value][value]
[value][value][value][value][value]
*/
1. Kirjoita duaalinen ongelma LP-tehtävälle, jossa tavoitteena on minimoida funktio \(z = [value]\) ehdoin \begin{alignat}{2} [value]x_1 &+ [value]x_2 &&\geq [value]\\ [value]x_1 &+ [value]x_2 &&= [value]\\ [value]x_1 &+ [value]x_2 &&\leq [value],\\ &x_1,x_2 &&\geq 0 \end{alignat}
2. Samoin ehdoin kuin kohdassa a., muodosta duaalinen ongelma kun primaalin tavoitteena on ollut maksimoida funktio \(z = [value]\).

Ohjeita:

Tehtävän toteutustavasta johtuen duaalisen funktion symbolina tulee käyttää merkkiä \(w\) (kirjoitetaan w), kun taas duaalisten muuttujien tapauksessa tulee käyttää merkintöjä \(y_1, y_2, y_3, y_4,\dots\) (kirjoitetaan y1,y2,y3,y4, jne.). Älä unohda käyttää kertomerkkinä symbolia *.

Anna tavoitefunktiot sekä -ehdot symbolisesti; ensimmäiset yhtenä yhtälönä (w = ...) ja jälkimmäinen joukkona yhtälöitä tai epäyhtälöitä ({eq1,eq2,eq3,...}). Anna lopuksi vielä molemmissa tapauksissa rajoittamattomat muuttujat joukkorajoittimien sisällä.

Ratkaisut:

Kohta | Tavoiteyhtälö | Optimointisuunta | Ehdot | Rajoittamattomat muuttujat
a. |  |  |  |
b. |  |  |  |

/*

Testitulosteita

[value][value][value][value][value]
[value][value][value][value]
[value][value][value][value]
[value]
[value]
[value]
[value]
[value]
[value] */

Tehtävänanto

Kirjoita duaalinen ongelma LP-tehtävälle, jossa pitäisi minimoida funktio \(z = [value]\) ehdoin

\begin{equation} \begin{aligned} [value] &\geq [value],\\ x_1,x_2,x_3 &\geq 0 \end{aligned} \end{equation}

ja ratkaise se. Käytämällä tätä ratkaisua, määritä lisäksi primaalitehtävän optimiratkaisu. Anna vastauksena sekä duaali- että primaalitehtävän optimiarvot sekä kohdat, joissa ne saavutetaan.

Anna vastaukset rationaalilukuina, vaikka ne mahdollisesti ilkeitä ovatkin.

Huomio

Tehtävän on tarkoitus havainnollistaa duaalitehtävän muodostamisen tarkoitusta: se saattaa olla yksinkertaisempi ratkaista ja helpottaa näin primaalitehtävänkin ratkaisua niiden välisten vahvojen yhteyksien vuoksi (vahva duaalisuuslause). Tässä duaalitehtävä on hyvinkin yksinkertainen yhden muuttujan LP-tehtävä, kun taas primaalissa on jo 3 muuttujaa, standardointia vielä lukuunottamatta.

Ratkaisu

Ongelma | Optimiarvo | Optimikohta
Primaali |  |
Duaali |  |

/*Testitulosteita

Testitulosteita

\(M =\)[value]
\(M_1 =\)[value]
\(M_{a,1} =\)[value]
\(M_{a,1} =\)[value] (laskento)
\(M_{a,2} =\)[value]
\(M_{a,2} =\)[value] (laskento)
\(M_{b,1} =\)[value]
\(M_{b,1} =\)[value] (laskento)
\(M_{b,2} =\)[value]
\(M_{b,2} =\)[value] (laskento)
\(M_{b,3} =\)[value]
\(M_{b,3} =\)[value] (laskento)
\(M_c =\)[value]
\(M_c =\)[value] (laskento)
\(z_{a,1} =\)[value]
\(z_{a,2} =\)[value]
\(z_{b,1} =\)[value]
\(z_{b,2} =\)[value]
\(z_{b,3} =\)[value]
\(z_c=\)[value]
*/ /*Taulukon tyylittelyjä*/

Tehtävänanto

Etsi taulukon 1 kuljetusongelmalle käypä aloituskantaratkaisu

1. luoteiskulman säännöllä,
2. pienin kustannus -menetelmällä ja
3. Vogelin approksimointimenetelmällä.

Taulukko 1: Kuljetusongelma.
 | Päämäärät
1 | 2 | 3 | 4 | 5 | Tarjonnat
Lähteet
1
 | [value]
\(x_{11}\) |
 | [value]
\(x_{12}\) |
 | [value]
\(x_{13}\) |
 | [value]
\(x_{14}\) |
 | 0
\(x_{15}\) |
65
2
 | [value]
\(x_{21}\) |
 | [value]
\(x_{22}\) |
 | [value]
\(x_{23}\) |
 | [value]
\(x_{24}\) |
 | 0
\(x_{25}\) |
55
Kysynnät | 25 | 40 | 15 | 20 | 20

Laske myös jokaisessa tapauksessa kantaratkaisua vastaava kokonaiskuljetuskustannus \(z\). Vastaukseen vaaditaan myös lopullinen kuljetusalgoritmin jälkeinen matriisi \(M\), jossa mahdollisia yliviivattuja soluja merkitään y.

Luoteiskulman sääntö

\(M_a = \)

\(z_a = \)

Pienin kustannus -menetelmä

\(M_b = \)

\(z_b = \)

Vogelin approksimointi

\(M_c = \)

\(z_c = \)

Lisäkysymys

Koska tarjonnat ja kysynnät eivät olleet alun perin tasapainossa, on tehtävän kuljetusmalli jouduttu tasapainottamaan lisäämällä siihen kuvitteellinen lähde tai määränpää. Päättele taulukon 1 perusteella, kumpi vastaus on oikein:

Neljä taksia on lähdössä noutamaan neljää asiakasta eri paikoista. Taksikeskus haluaa jakaa tehtävät niin, että taksien yhteenlaskettu siirtymäajomatka on mahdollisimman pieni. Alla olevan matriisin \(ij\)-alkio kertoo \(i.\) taksin etäisyyden \(j.\) matkustajasta. Ratkaise kohdistusongelma unkarilaisen algoritmin avulla.

\( \begin{array}{c|cccc|} & \text{A} & \text{si} & \text{a} & \text{kas} \\ \text{Taksi} & 1 & 2 & 3 & 4 \\ \hline 1 & [value] & [value] & [value] & [value] \\ 2 & [value] & [value] & [value] & [value] \\ 3 & [value] & [value] & [value] & [value] \\ 4 & [value] & [value] & [value] & [value] \end{array} \)

[value] | \(\rightarrow\) |  | \(\rightarrow\) |  | \(\rightarrow\) |

Optimikohdistus on:

Taksi | Asiakas | Siirtymäajomatka
1 |  |
2 |  |
3 |  |
4 |  |

Kokonaissiirtymäajomatka:
Feedback: Mallivastaus [value] | \(\rightarrow\) | [value] | \(\rightarrow\) | [value] | \(\rightarrow\) | [value] Optimikohdistus on: Taksi | Asiakas | Siirtymäajomatka 1 | [value] | [value] 2 | [value] | [value] 3 | [value] | [value] 4 | [value] | [value] Kokonaissiirtymäajomatka: [value]

Junioreiden jääkiekkojoukkueen ykkösketjun pelaajat on valittu, mutta pelaajien roolitus on vielä epäselvä. Kenttään tarvitaan keskushyökkääjä (C), vasen laituri (VL), oikea laituri (OL) ja kaksi puolustajaa (P). Kutakin pelaajaa A, B, C, D ja E pyydettiin arvioimaan omaa halukkuuttaan kuhunkin tehtävään asteikolla 1-5, ja tulokset olivat oheisen taulukon mukaiset:

\( \begin{array}{|c|cccc|} \hline \text{Pelaaja\ Rooli}& \text{C} & \text{VL} & \text{OL} & \text{P} \\ \hline \text{A} & [value] & [value] & [value] & [value] \\ \text{B} & [value] & [value] & [value] & [value] \\ \text{C} & [value] & [value] & [value] & [value] \\ \text{D} & [value] & [value] & [value] & [value] \\ \text{E} & [value] & [value] & [value] & [value] \\ \hline \end{array} \)

Valmentaja haluaa maksimoida pelaajien motivaation ja valita roolit niin, että pelaajien yhteenlaskettu kiinnostus saamiaan tehtäviä kohtaan on mahdollisimman suuri. Käytä unkarilaista algoritmia ja auta junnujoukkueen valmentajaa jakamaan roolit.

\(\hphantom{\large \rightarrow}\) |  | \(\large \rightarrow\) |  | \(\large \rightarrow\) |

\(\large \rightarrow\) |  | \(\large \rightarrow\) |

Optimikohdistus on:

Pelaaja | Rooli | Halukkuus
A |  |
B |  |
C |  |
D |  |
E |  |

Onko olemassa vaihtoehtoisia optimiratkaisuja?
Feedback: Mallivastaus \(\hphantom{\large \rightarrow}\) | [value] | \(\large \rightarrow\) | [value] | \(\large \rightarrow\) | [value] | \(\large \rightarrow\) | [value] | \(\large \rightarrow\) | [value] Optimikohdistus on: Pelaaja | Rooli | Halukkuus A | [value] | [value] B | [value] | [value] C | [value] | [value] D | [value] | [value] E | [value] | [value] Onko olemassa vaihtoehtoisia optimiratkaisuja? [value]

a) Määritä alla olevien kahden pelin satulapisteratkaisut ja niiden arvot (matriisit ovat vaakarivipelaajan \(A\) matriiseja):

 | \(B_1\) | \(B_2\) | \(B_3\) | \(B_4\) | rivi minimi
\(A_1\) | [value] | [value] | [value] | [value] |
\(A_2\) | [value] | [value] | [value] | [value] |
\(A_3\) | [value] | [value] | [value] | [value] |
sarake
maksimi

maximin:

minimax:

Satulapisteratkaisu \(\Big(A\)_, \(B\)_\(\Big)\), pelin arvo v = .

 | \(B_1\) | \(B_2\) | \(B_3\) | \(B_4\) | rivi minimi
\(A_1\) | [value] | [value] | [value] | [value] |
\(A_2\) | [value] | [value] | [value] | [value] |
\(A_3\) | [value] | [value] | [value] | [value] |
\(A_4\) | [value] | [value] | [value] | [value] |
sarake
maksimi

maximin:

minimax:

Satulapisteratkaisu \(\Big(A\)_, \(B\)_\(\Big)\), pelin arvo v = .

b) Tarkastellaan alla olevaa kahden pelaajan peliä. Määritä parametreille p ja q arvoalueet, joiden sisällä niiden arvot voivat vaihdella niin, että alla olevan pelin satulapiste pysyy pisteessä \((A_2, B_2)\). Ohjeita: anna vastaus reaalilukuvälin muodossa hakasulkunotaatiolla. Äärettömän ja miinus äärettömän saat tarvittaessa komennoilla inf ja -inf. Huomioi myös sulkeiden suunta puoliavoimen välin tapauksessa.

\( \begin{array}{c|ccc|} & B_1 & B_2 & B_3 \\ \hline A_1 & [value] & [value] & [value] \\ A_2 & [value] & [value] & [value] \\ A_3 & [value] & [value] & [value] \\ \hline \end{array} \)

Jos \(p\in \,\), ja \(q\in \,\),, niin \((A_2, B_2)\) on pelin satulapiste.
Feedback: Mallivastaus a) | \(B_1\) | \(B_2\) | \(B_3\) | \(B_4\) | rivi minimi \(A_1\) | [value] | [value] | [value] | [value] | [value] \(A_2\) | [value] | [value] | [value] | [value] | [value] \(A_3\) | [value] | [value] | [value] | [value] | [value] sarake maksimi | [value] | [value] | [value] | [value] | maximin: [value] minimax: [value] Satulapisteratkaisu \(\Big(A\)_[value], \(B\)_[value]\(\Big)\), pelin arvo v = [value]. | \(B_1\) | \(B_2\) | \(B_3\) | \(B_4\) | rivi minimi \(A_1\) | [value] | [value] | [value] | [value] | [value] \(A_2\) | [value] | [value] | [value] | [value] | [value] \(A_3\) | [value] | [value] | [value] | [value] | [value] \(A_4\) | [value] | [value] | [value] | [value] | [value] sarake maksimi | [value] | [value] | [value] | [value] | maximin: [value] minimax: [value] Satulapisteratkaisu \(\Big(A\)_[value], \(B\)_[value]\(\Big)\), pelin arvo v = [value]. b) \( \begin{array}{c|ccc|} & B_1 & B_2 & B_3 \\ \hline A_1 & [value] & [value] & [value] \\ A_2 & [value] & [value] & [value] \\ A_3 & [value] & [value] & [value] \\ \hline \end{array} \) Jos \(p\in \,\)[value][value],[value][value] ja \(q\in \,\)[value][value],[value][value], niin \((A_2, B_2)\) on pelin satulapiste.

Han Solo on saanut Hutt Jabbalta tehtäväkseen salakuljettaa arvokkaan maustelastin Kesselistä Corelliaan. Mikäli Solo saa vietyä lastin perille, saa hän Jabbalta palkkioksi [value] kultakrediittiä. Mikäli Solo menettää lastin, joutuu hän maksamaan korvaukseksi Jabballe [value] kultakrediittiä. Hänellä on kaksi vaihtoehtoista reittiä A ja B, joista A on lyhyempi ja siten kuljetuskustannuksiltaan edullisempi. Reitillä A kuljetuskustannuksia tulee [value] ja reitillä B [value] kultakrediittiä (ko. kustannus vähennetään palkkiosta salakuljetusoperaation onnistuessa ja lisätään tappioihin sen epäonnistuessa). Imperiumin rajavalvontaviranomainen on tietoinen Solon hankkeesta ja pyrkii minimoimaan Solon saamat pimeät ja laittomat tulot. Tätä varten Imperiumin tulli aikoo asettaa tehostetun tullivalvonnan jommalle kummalle reiteistä. Solo menettää lastin, mikäli hän sattuu valitsemaan tehovalvonnassa olevan reitin, muussa tapauksessa hän pääsee perille lastin kanssa. Määritä näiden tietojen perusteella kummankin pelaajan optimistrategiat sekä ko. nollasummapelin arvo. Onko Han Solon salakuljetustoiminta keskimäärin kannattavaa?

Huom! Syötä vastaukset tarkkoina arvoina.

\(2\times 2\)-nollasummapelin matriisiksi tulee

 |  | A | B
Solo | A |  |
B |  |
 |  | Imperiumi

Onko satulapistettä

\(2\times 2\)-pelin kaavoilla saadaan

\(x^* = \Big(\),\(\Big)\)

\(y^* = \Big(\),\(\Big)\)

\(v^* =\, \)

Toiminta on siis Sololle

tulee keskimäärin kultakrediittiä.
Feedback: Mallivastaus \(2\times 2\)-nollasummapelin matriisiksi tulee | | A | B Solo | A | [value] | [value] B | [value] | [value] | | Imperiumi Onko satulapistettä [value] \(2\times 2\)-pelin kaavoilla saadaan \(x^* = \Big(\)[value],[value]\(\Big)\) \(y^* = \Big(\)[value],[value]\(\Big)\) \(v^* =\, \) [value] Toiminta on siis Sololle [value] [value] tulee keskimäärin [value] kultakrediittiä.

Rape on intohimoinen keskioluen ystävä, jonka juomaharrastus on saanut niin suuret mittasuhteet, että hänelle on syntynyt varastointiongelma (korostettakoon, että Rape on täysin fiktiivinen henkilö, mahdolliset samankaltaisuudet todellisten henkilöiden kanssa ovat puhtaasti sattumanvaraisia). Rape siemailee mallasjuomaa vakionopeudella \(72\) tölkkiä viikossa, eikä kaljan puutetta tietenkään voida sallia. Rapella itsellään ei ole jääkaappia, mutta hän on onnistunut vuokraamaan naapureilta ja ryyppykavereiltaan jääkaappitilaa hintaan \(0.10\) euroa tölkiltä viikossa. Rapella on kaksi vaihtoehtoa täydentää varastoaan. Hän voi hakea oluensa taksilla lähikaupasta, mistä aiheutuu kustannuksia \(10\) euroa. Toinen vaihtoehto on varata pakettimatka ja hakea kaljat Virosta, jolloin yhdelle ostosmatkalle tulee hintaa \(90\) euroa.

a) Määritä kummallekin hankintatavalle optimaalinen tilauserän koko, optimaalisen varastopolitiikan kustannukset sekä optimaalinen tilausväli.

Kysyntänopeus \(D=\,\) (tölkkiä/viikko)

Varastointikustannus \(h=\,\) (€/tölkki \(\cdot \) viikko)

i) Lähikaupasta ostettaessa tilauskustannus \(K=\,\) € ja saadaan

\(y^* = \,\)

\(TCU(y^*) = \,\) (€/viikko)

\(t_0^* = \,\) viikkoa

ii) Virosta ostettaessa tilauskustannus \(K=\,\) € ja saadaan

\(y^* = \,\)

\(TCU(y^*) = \,\) (€/viikko)

\(t_0^* = \,\) viikkoa

b) Otetaan sitten huomioon myös oluiden hankintakustannus. Lähikaupassa yksi tölkki maksaa euron, Virossa \(0.50\) euroa. Kumpi hankintatapa on kokonaiskustannuksiltaan edullisempi, ja paljonko Rapen juomaharrastus tulee tällöin maksamaan viikossa?

i) Lähikaupasta ostettaessa \(c=\,\) € ja viikossa kustannuksia tulee yhteensä

\(TCU(y^*)+CD = \,\) (€/viikko)

ii) Virosta ostettaessa \(c=\,\) € ja viikossa kustannuksia tulee yhteensä

\(TCU(y^*)+CD = \,\) (€/viikko)

Virosta ostamalla Rape siis € viikossa ja maksaa harrastuksestaan €/viikko.
Feedback: Mallivastaus a) Kysyntänopeus \(D=\,\)[value] (tölkkiä/viikko) Varastointikustannus \(h=\,\)[value] (€/tölkki \(\cdot \) viikko) i) Lähikaupasta ostettaessa tilauskustannus \(K=\,\)[value] € ja saadaan \(y^* = \,\)[value] \(TCU(y^*) = \,\)[value] (€/viikko) \(t_0^* = \,\)[value] viikkoa ii) Virosta ostettaessa tilauskustannus \(K=\,\)[value]€ ja saadaan \(y^* = \,\)[value] \(TCU(y^*) = \,\)[value] (€/viikko) \(t_0^* = \,\)[value] viikkoa b) i) Lähikaupasta ostettaessa \(c=\,\)[value] € ja viikossa kustannuksia tulee yhteensä \(TCU(y^*)+CD = \,\)[value] (€/viikko) ii) Virosta ostettaessa \(c=\,\)[value] € ja viikossa kustannuksia tulee yhteensä \(TCU(y^*)+CD = \,\)[value] (€/viikko) Virosta ostamalla Rape [value] siis [value] € viikossa ja maksaa harrastuksestaan [value] €/viikko.

Ilmalämpöpumppuja myyvällä yrityksellä on huollettavanaan yli tuhannen asiakkaansa ilmalämpöpumput. Joka kuukausi keskimäärin kahdeksaan ilmalämpöpumppuun pitää vaihtaa uusi koneisto. Yhden koneiston varastointikustannukset ovat [value] euroa vuodessa. Mikäli vaihto-osaa ei löydy yrityksen varastosta ja asiakas joutuu odottamaan pumpun huoltoa, joutuu yritys hyvittämään asiakkaan sähkölaskua [value] eurolla jokaista asiakkaan odottamaa viikkoa kohti. Varaosatilauksen tekeminen maksaa yritykselle [value] euroa (riippumatta tilattujen koneistojen lukumäärästä). Määritä varastopolitiikan kannalta optimaalinen tilauserän koko, maksimipuute ja varastopolitiikan kokonaiskustannukset.

\(D=\,\) (yksikköä vuodessa "kysyntää")

\(K=\,\) (€, tilauskustannukset)

\(h=\,\) (€/vuosi, varastointikustannus/kpl)

\(p=\,\) (€/vuosi, puutekustannus)

\(y^*\approx \,\) kpl

\(w^*\approx \,\) kpl

\(TCU(y^*,w^*)\approx \,\) | (€/vuosi)
 | (kahden desimaalin tarkkuudella)
Feedback: Mallivastaus \(D=\,\)[value] (yksikköä vuodessa "kysyntää") \(K=\,\)[value] (€, tilauskustannukset) \(h=\,\)[value] (€/vuosi, varastointikustannus/kpl) \(p=\,\)[value] (€/vuosi, puutekustannus) \(y^*\approx \,\)[value] kpl \(w^*\approx \,\)[value] kpl \(TCU(y^*,w^*)\approx \,\) | [value] (€/vuosi)

Pienleipomon erästä suosikkileipää myydään joka päivä keskimäärin [value] kappaletta. Puutetta ei sallita, vaan vanhan varaston loppuessa aletaan välittömästi valmistaa uutta erää. Jokaisen erän aloittaminen maksaa erinäisinä kuluina [value] euroa, valmiiden leipien varastoinnista puolestaan aiheutuu kustannuksia [value] euroa kappaleelta päivässä (hinta koostuu lähinnä vanhenevien leipien aiheuttamasta hävikistä). Tuotannon olessa käynnissä voidaan päivässä leipoa [value] leipää. Määritä varastopolitiikan kustannusten kannalta optimaalinen tilausväli, tilauserän koko sekä optimipolitiikan aiheuttamat päivittäiset kustannukset.

Kyseessä on perusmalli äärellisen täydennysnopeuden tapauksessa:

\(\alpha=\,\) (leipää/päivä, täydennysnopeus)

\(D=\,\) (leipää/päivä, kysyntänopeus)

\(K=\,\) (tilauskustannus)

\(h=\,\) (varastointikustannus yksiköltä)

(Syötä vastaukset kahden desimaalin tarkkuudella)

Optimaalinen tilausväli:

\(t_0^*\approx \,\) (päivää)

Optimaalinen tilauserän koko:

\(y^*\approx \,\) (leipää)

Optimipolitiikan kustannukset:

\(TCU(y^*)\approx \,\) (€/vuosi)
Feedback: Mallivastaus Kyseessä on perusmalli äärellisen täydennysnopeuden tapauksessa: \(\alpha=\,\)[value] (leipää/päivä, täydennysnopeus) \(D=\,\)[value] (leipää/päivä, kysyntänopeus) \(K=\,\)[value] (tilauskustannus) \(h=\,\)[value] (varastointikustannus yksiköltä) Optimaalinen tilausväli: \(t_0^*\approx \,\)[value] (päivää) Optimaalinen tilauserän koko: \(y^*\approx \,\)[value] (leipää) Optimipolitiikan kustannukset: \(TCU(y^*)\approx \,\) [value] (€/vuosi)

Yritys tarvitsee erästä tuotetta vuodessa [value] yksikköä, eikä tuotteiden loppumista voida sallia. Yhden tuotteen varastointi maksaa \(2\)€ kappaleelta vuodessa. Jokaisesta tilauksesta peritään \(40\)€ käsittely- ja toimitusmaksuja. Tuotteista maksettava hinta määräytyy oheiseen taulukkoon merkittyjen paljousalennusten mukaisesti. Yhtiö haluaa minimoida ostohinnoista, tilauksista ja varastoinnista aiheutuvat kokonaiskustannukset. Määritä optimaalinen tilauserän koko, optimaalinen tilausväli sekä optimaalisen varastopolitiikan kokonaiskustannukset. (Syötä desimaaliluvut kahden desimaalin tarkkuudella)

\( \begin{array}{|l|l|} \hline \text{Tilauserän koko} & \text{Tuotteen yksikköhinta} \\ \hline 0-99 & 20.00€ \\ 100-199 & 19.50€ \\ 200-499 & 19.00€ \\ 500- & 18.75€\\ \hline \end{array} \)

\(D = \,\) kpl/vuosi

\(h = \,\) €/kpl\(\cdot \)vuosi

\(K = \,\) €

Varastopolitiikan kannalta optimaalinen tilauserän koko:

\(y^* \approx \,\)

Kokonaiskustannusten kannalta kannattaa tilata joko \(a=\,\), \(b=\,\) tai \(c=\,\) kpl.

\(C(a) \approx\,\) €

\(C(b) \approx\,\) €

\(C(c) \approx\,\) €

Optimaalinen tilauseränkoko on siis \(y=\,\)

Tilausväli \(t_0 \approx\,\) vuotta

Kokonaiskustannus on siis €/vuosi.
Feedback: Mallivastaus \(D = \,\)[value] kpl/vuosi \(h = \,\)[value] €/kpl\(\cdot \)vuosi \(K = \,\)[value] € Varastopolitiikan kannalta optimaalinen tilauserän koko: \(y^* \approx \,\)[value] Kokonaiskustannusten kannalta kannattaa tilata joko \(a=\,\)[value], \(b=\,\)[value] tai \(c=\,\)[value] kpl. \(C(a) \approx\,\)[value] € \(C(b) \approx\,\)[value] € \(C(c) \approx\,\)[value] € Optimaalinen tilauseränkoko on siis \(y=\,\)[value] Tilausväli \(t_0 \approx\,\)[value] vuotta Kokonaiskustannus on siis [value] €/vuosi.

Q: /*Tyylitteyjä*/ /*

[Image]

*/

Pienyrittäjä ostaa yksinkertaisia ja halpoja kiinalaista alkuperää olevia sähkölaitteita maahantuojalta. Yrityksessään hän teettää niihin tiettyjä parannuksia ja saa näin laitteet käymään erittäin hyvin kaupaksi. Parannuksissaan hän tarvitsee kahden työntekijänsä, sähköasentajan ja metallityöntekijän työsuorituksia. Laitetyyppejä on kaksi, malli \(A\) ja malli \(B\). Malli \(A\) vaatii tunnin sähkötöitä ja puoli tuntia metallitöitä, malli \(B\) taas puoli tuntia sähkötöitä ja tunnin metallitöitä.

Koska kyseessä on pienyritys, eivät kyseiset ammattilaiset voi kuitenkaan käyttää koko työaikaansa laitteiden paranteluun. Sähköasentajalla on tähän aikaa enintään [value] tuntia ja metallityöntekijällä taas [value] tuntia. Mallista \(A\) saatava voitto on 24e/kpl ja mallista \(B\) 44e/kpl.

1. Yrittäjä haluaa maksimoida lampuista saatavan tuoton. Muotoile tehtävä LP-ongelmaksi ja ratkaise se graafisesti.

Optimipiste | Optimiarvo

2. Oletetaan, että mallista \(A\) saatava tuotto muuttuu, mutta mallin \(B\) tuotto pysyy samana. Missä rajoissa mallista \(A\) saatava tuotto saa vaihdella ilman, että a-kohdassa määritelty optimipiste muuttuu?

Mallin \(A\) tuoton alaraja | Mallin \(A\) tuoton yläraja

3. Sama kysymys kuin b-kohdassa, mutta nyt mallin \(A\) tuotto pysyy samana ja mallin \(B\) vaihtelee.

Mallin \(B\) tuoton alaraja | Mallin \(B\) tuoton yläraja

4. Olkoon eri laitemallien \(A\) ja \(B\) tuotot samoja kuin alkuperäisessä tehtävänannossa. Merkitse alla olevaan taulukkoon optimipisteen sarakkeeseen niiden pisteiden koordinaatit, joihin optimipistettä voidaan äärimmillään siirtää kun ko. työntekijän työaikaresurssia kasvatetaan riittävästi. Optimiarvo-sarakkeisiin merkitse näitä pisteitä vastaavat tavoitefunktion arvot. Tämän jälkeen määritä sähköasentajan ja metallityöntekijän työaikaresurssien yksikköarvot (anna vastaus murtolukuna). Kumpaa resurssia kannatta ensisijaisesti pyrkiä lisäämään, mikäli halutaan kasvattaa toiminnolla saatavaa tuottoa mahdollisimman paljon?

Ammattilainen | Optimipiste | Optimiarvo | Yksikköarvo
Metallityöntekijä |  |  |
Sähköasentaja |  |  |

Yksikköhinnan perusteella lisättävä resurssi:
  Hint: Vihje 1 Mieti tarkkaan mitä halutaan optimoida.

Q: /*Tyylitteyjä*/ /*

[Image]

*/

Pienyrittäjä ostaa yksinkertaisia ja halpoja kiinalaista alkuperää olevia sähkölaitteita maahantuojalta. Yrityksessään hän teettää niihin tiettyjä parannuksia ja saa näin laitteet käymään erittäin hyvin kaupaksi. Parannuksissaan hän tarvitsee kahden työntekijänsä, sähköasentajan ja metallityöntekijän työsuorituksia. Laitetyyppejä on kaksi, malli \(A\) ja malli \(B\). Malli \(A\) vaatii tunnin sähkötöitä ja puoli tuntia metallitöitä, malli \(B\) taas puoli tuntia sähkötöitä ja tunnin metallitöitä.

Koska kyseessä on pienyritys, eivät kyseiset ammattilaiset voi kuitenkaan käyttää koko työaikaansa laitteiden paranteluun. Sähköasentajalla on tähän aikaa enintään [value] tuntia ja metallityöntekijällä taas [value] tuntia. Mallista \(A\) saatava voitto on 24e/kpl ja mallista \(B\) 44e/kpl.

1. Yrittäjä haluaa maksimoida lampuista saatavan tuoton. Muotoile tehtävä LP-ongelmaksi ja ratkaise se graafisesti.

Optimipiste | Optimiarvo

2. Oletetaan, että mallista \(A\) saatava tuotto muuttuu, mutta mallin \(B\) tuotto pysyy samana. Missä rajoissa mallista \(A\) saatava tuotto saa vaihdella ilman, että a-kohdassa määritelty optimipiste muuttuu?

Mallin \(A\) tuoton alaraja | Mallin \(A\) tuoton yläraja

3. Sama kysymys kuin b-kohdassa, mutta nyt mallin \(A\) tuotto pysyy samana ja mallin \(B\) vaihtelee.

Mallin \(B\) tuoton alaraja | Mallin \(B\) tuoton yläraja

4. Olkoon eri laitemallien \(A\) ja \(B\) tuotot samoja kuin alkuperäisessä tehtävänannossa. Määritä sähköasentajan ja metallityöntekijän työaikaresurssien yksikköarvot. Kumpaa resurssia kannatta ensisijaisesti pyrkiä lisäämään, mikäli halutaan kasvattaa toiminnolla saatavaa tuottoa mahdollisimman paljon?

Ammattilainen | Optimipiste | Optimiarvo | Yksikköarvo
Metallityöntekijä |  |  |
Sähköasentaja |  |  |

Yksikköhinnan perusteella lisättävä resurssi:
  Hint: Vihje 1 Mieti tarkkaan mitä halutaan optimoida.

Q: /*TYYLITTELYJÄ*/

Tarkastellaan standardimuotoista LP-tehtävää

\[ \quad \left\{ \begin{aligned} z - 2x_1 - 4x_2 - 7x_3 &= 0,\\ 2x_1 + 3x_2 + 6x_3 + s_1 &= 18,\\ x_2 + s_2 &= 5,\\ x_1,x_2,x_3,s_1,s_2 &\geq 0\,. \end{aligned} \right. \] [Image]

Maksimoi funktio \(z\) käyttämällä Simplex-algoritmia aloittaen käyvästä kantaratkaisusta \( (x_1,x_2,x_3,s_1,s_2) = (0,0,0,18,5)\). Täydennä alla oleviin taulukoihin puuttuvat kertoimet, käyttäen tarvittaessa murtolukuja. Anna muuttujien arvot listana hakasulkeiden sisällä pilkulla eroteltuna ([...]) ja yhtälöiden ratkaisut lukuarvoina.

Vaihe 1:

Kanta | \([x_1,x_2,x_3,s_1,s_2]\) | Ratkaisu
\(z\) |  |
\(s_1\) |  |
\(s_2\) |  |

Vaihe 2:

Kanta | \([x_1,x_2,x_3,s_1,s_2]\) | Ratkaisu
\(z\) |  |
\(x_3\) |  |
\(s_2\) |  |

Vaihe 3:

Kanta | \([x_1,x_2,x_3,s_1,s_2]\) | Ratkaisu
\(z\) |  |
\(x_3\) |  |
\(x_2\) |  |
Feedback: Yleinen palaute
  Hint: Vihje 1: Käypä kantaratkaisu on etsitty jo valmiiksi, eli jäljellä on itse Simplex-algoritmin suorittaminen.
  Hint: Vihje 1: Käypä kantaratkaisu on etsitty jo valmiiksi, eli jäljellä on itse Simplex-algoritmin suorittaminen. Vihje 2: Jokaisessa välivaiheessa saapuva muuttuja on se, jonka arvo \(z\)-rivillä on negatiivisin.
  Hint: Vihje 1: Käypä kantaratkaisu on etsitty jo valmiiksi, eli jäljellä on itse Simplex-algoritmin suorittaminen. Vihje 2: Jokaisessa välivaiheessa saapuva muuttuja on se, jonka arvo \(z\)-rivillä on negatiivisin. Vihje 3: Saapuvan muutttujan arvo seuraavassa kantaratkaisussa on aina saapuvan muuttujan ja saman rivin ratkaisun suhde.
  Hint: Vihje 1: Käypä kantaratkaisu on etsitty jo valmiiksi, eli jäljellä on itse Simplex-algoritmin suorittaminen. Vihje 2: Jokaisessa välivaiheessa saapuva muuttuja on se, jonka arvo \(z\)-rivillä on negatiivisin. Vihje 3: Saapuvan muutttujan arvo seuraavassa kantaratkaisussa on aina saapuvan muuttujan ja saman rivin ratkaisun suhde. Vihje 4: Lähtevä muutuja on se, jonka rivillä yläpuolinen ei-negatiivinen suhde on pienin.

/*Tyylittelyjä*/

Tarkastellaan standardimuotoista LP-tehtävää:

\[ \left\{ \begin{aligned} z = x_1 + x_2 + 3x_3 &+ 2x_4 \\ x_1 + 2x_2 - 3x_3 + 5x_4 &\leq 4,&(1) \\ 5x_1 -2 x_2 + 6x_4 &\leq 8,&(2)\\ 2x_1 + 3x_2 - 2x_3 + 3x_4 &\leq 3, &(3)\\ -x_1 + x_3 + 2x_4 &\leq 0, &(4)\\ x_1,x_2,x_3,x_4 &\geq 0, \end{aligned} \right. \]

missä funktio \(z\) on maksimoitu Simplex-algoritmilla ja tulokseksi on saatu seuraava taulukko:

Kanta | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | Ratkaisu
\(z\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]
\(s_1\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]
\(x_1\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]
\(x_2\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]
\(x_3\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]

1. Mikä on tehtävän optimiarvo, ja missä se saavutetaan?
Optimipiste:
Optimiarvo:
2. Mitkä ovat kantamuuttujia tämänhetkisessä ratkaisussa? Anna ne järjestettynä listana siten, että \(x\):ät tulevat ennen \(s\):iä alaindeksien määräämässä järjestyksessä:
3. Kuvitellaan, että jonkin rajoite-ehdoista (1)-(4) oikean puolen vakiotermiä on mahdollista kasvattaa yhdellä yksiköllä. Mitä niistä kannattaa lisätä, jotta tavoitefunktion arvo kasvaisi mahdollisimman paljon?

Kuinka paljon tavoitefunktio tällöin kasvaa?
4. Rajoitteen (3) oikean puolen vakiotermiä kasvatetaan viidellä yksiköllä, eli arvosta 3 arvoon 8. Laske taulukon avulla uusi optimiratkaisu, kantamuuttujien pysyessä samoina.
Optimipiste:
Optimiarvo:

/*Tyylitelyjä*/ /* Testitulosteita

Testitulosteita

[value][value] */ Tarkastellaan standardimuotoista LP-tehtävää:

\[ \left\{ \begin{aligned} z = x_1 + x_2 + 3x_3 &+ 2x_4 \\ x_1 + 2x_2 - 3x_3 + 5x_4 &\leq 4,&(1) \\ 5x_1 -2 x_2 + 6x_4 &\leq 8,&(2)\\ 2x_1 + 3x_2 - 2x_3 + 3x_4 &\leq 3, &(3)\\ -x_1 + x_3 + 2x_4 &\leq 0, &(4)\\ x_1,x_2,x_3,x_4 &\geq 0, \end{aligned} \right. \]

missä funktio \(z\) on maksimoitu Simplex-algoritmilla ja tulokseksi on saatu seuraava taulukko:

Kanta | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | Ratkaisu
\(z\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]
\(s_1\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]
\(x_1\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]
\(x_2\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]
\(x_3\) | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value] | [value]

1. Mikä on tehtävän optimiarvo, ja missä se saavutetaan?
Optimipiste:
Optimiarvo:
2. Mitkä ovat kantamuuttujia tämänhetkisessä ratkaisussa? Anna ne järjestettynä listana siten, että \(x\):ät tulevat ennen \(s\):iä alaindeksien määräämässä järjestyksessä:
3. Kuvitellaan, että jonkin rajoite-ehdoista (1)-(4) oikean puolen vakiotermiä on mahdollista kasvattaa yhdellä yksiköllä. Mitä niistä kannattaa lisätä, jotta tavoitefunktion arvo kasvaisi mahdollisimman paljon?

Kuinka paljon rajoitefunktio tällöin kasvaa?
4. Rajoitteen (3) oikean puolen vakiotermiä kasvatetaan viidellä yksiköllä, eli arvosta 3 arvoon 8. Laske taulukon avulla uusi optimiratkaisu, kantamuuttujien pysyessä samoina.
Optimipiste:
Optimiarvo:

1. Tarkastellaan LP-tehtävää, jossa halutaan maksimoida funktio \(z = x_1 + 2x_2 + 3x_3\) ehdoin
\[ \left\{ \begin{aligned} 3x_1 + x_2 - x_3 &\leq 4, &(1)\\ 2x_1 + x_2 + x_3 &\geq 3,&(2)\\ -x_1 + 3x_2 - x_3 &= 5.&(3) \end{aligned} \right. \]

Simplex-menetelmän soveltamista varten tehtävälle halutaan löytää käypä aloituskantaratkaisu. Tätä varten rajoite-ehdot pitää standardoida ja mahdollisesti lisätä niihin keinomuuttujia. Tarkastellaan rajoite-ehtoja erikseen.
Ehto (1)
Jotta haluttu tavoite saavutettaisiin, tulee ehtoon lisätä
Mikäli halutaan käyttää M-menetelmää, tulee tavoitefuntiota muokata
Ehto (2)
Jotta haluttu tavoite saavutettaisiin, tulee ehtoon lisätä
Mikäli halutaan käyttää M-menetelmää, tulee tavoitefuntiota muokata
Ehto (3)
Jotta haluttu tavoite saavutettaisiin, tulee ehtoon lisätä
Mikäli halutaan käyttää M-menetelmää, tulee tavoitefuntiota muokata
2. Alkaen samoista ehdoista (1)-(3) kuin Kohdassa (a), tarkoituksena olisi minimoida funktio \(z\). Tarkastellaan taas tällöin rajoite-ehtoja erikseen.
Ehto (1)
Jotta haluttu tavoite saavutettaisiin, tulee ehtoon lisätä
Mikäli halutaan käyttää M-menetelmää, tulee tavoitefuntiota muokata
Ehto (2)
Jotta haluttu tavoite saavutettaisiin, tulee ehtoon lisätä
Mikäli halutaan käyttää M-menetelmää, tulee tavoitefuntiota muokata
Ehto (3)
Jotta haluttu tavoite saavutettaisiin, tulee ehtoon lisätä
Mikäli halutaan käyttää M-menetelmää, tulee tavoitefuntiota muokata
3. Rajoite-ehdot toteuttava käypä aloituskantaratkaisu halutaan sittenkin löytää soveltamalla kaksivaihemenetelmän ensimmäistä vaihetta. Tämän vaiheen kannalta ei ole merkitystä onko kyseessä minimointi- vaiko maksimointiongelma.
Kaksivaihemenetelmän tarkoituksena on
tavoitefunktio \(r =\)
.
Mikäli tehtävällä ei ole olemassa käypää kantaratkaisua, ilmenee se kaksivaihemenetelmän 1. vaiheen lopussa seuraavasti:

/*Testitulosteita [value] [value] [value] [value] [value] [value]
[value] [value] [value] [value] [value] [value]
[value] [value] [value] [value] [value] [value]*/ /*Tyylittelyjä*/

Lähtötiedot

Tarkastellaan LP-tehtävää, jossa tulisi maksimoida funktio \(z = [value]x_1+[value]x_2\) ehdoin

\[ \left\{ \begin{aligned} x_1 + 3x_2 &\leq [value],\\ 3x_1 + 2x_2 &\leq [value],\\ x_1,x_2 &\geq 0\,. \end{aligned} \right. \]

Standardoi tehtävä lisäämällä rajoite-ehtoihin liikkumavaramuuttujat \(s_1\) ja \(s_2\). Tehtävän kantaratkaisut saadaan asettamalla standardoidussa tehtävässä vuorotellen kaksi muuttujista \(x_1, x_2, s_1\) ja \(s_2\) kantamuuttujiksi ja loput kaksi nolla-arvoisiksi ei-kantamuuttujiksi. Tämän jälkeen ratkaistaan saatu yhtälöpari (mikäli mahdollista) ja tarkistetaan ratkaisun käypyys. Käypässä kantaratkaisussa ei ole negatiivisia muuttujia.

Käypien kantaratkaisujen selvittäminen

Laske allaolevaan taulukkoon kantamuuttujien arvot ja luokittele kussakin tapauksessa kantaratkaisu joko käypäksi tai ei-käypäksi. Teknisistä syistä tulee kantamuuttujien arvot syöttää listan sisällä samassa järjestyksessä kuin ne ovat taulukon vasemmanpuolimmaisimmassa sarakkeessa.

Kantamuuttujat | Kantamuuttujien arvot | Kanta käypä?
\(s_1\) ja \(s_2\) |  |
\(x_1\) ja \(s_1\) |  |
\(x_2\) ja \(s_1\) |  |
\(x_1\) ja \(s_2\) |  |
\(x_2\) ja \(s_2\) |  |
\(x_1\) ja \(x_2\) |  |

Funktion \(z\) optimointi

LP-tehtävä voidaan aina ratkaista myös niin, että lasketaan tavoitefunktion arvot kaikissa käypissä kantaratkaisuissa ja valitaan niistä suurin tai pienin riippuen tavoitteesta. Ratkaise ylläoleva LP-ongelma tällä menetelmällä.

\(z_{\rm max}\) =

Jos harrastuneisuutta ja tarmoa tenttiin valmistautumiseen riittää, voit lopuksi piirtää kuvan käypästä alueesta, ratkaista tehtävän graafisesti ja miettiä mikä yleinen piirre on käypillä ja toisaalta kaikilla ei-käypillä kantaratkaisuilla kuvassa.

/* Testitulosteita [value] [value] [value] [value] [value] [value]
[value] [value] [value] [value] [value] [value]
[value] [value] [value] [value] [value] [value] */ /*Tyylittelyjä*/

Lähtötiedot

Tarkastellaan LP-tehtävää, jossa tulisi maksimoida funktio \(z = [value]x_1+[value]x_2\) ehdoin

\[ \left\{ \begin{aligned} x_1 + 3x_2 &\leq [value],\\ 3x_1 + 2x_2 &\leq [value],\\ x_1,x_2 &\geq 0\,. \end{aligned} \right. \]

Standardoi tehtävä lisäämällä rajoite-ehtoihin liikkumavaramuuttujat \(s_1\) ja \(s_2\). Tehtävän kantaratkaisut saadaan asettamalla standardoidussa tehtävässä vuorotellen kaksi muuttujista \(x_1, x_2, s_1\) ja \(s_2\) kantamuuttujiksi ja loput kaksi nolla-arvoisiksi ei-kantamuuttujiksi. Tämän jälkeen ratkaistaan saatu yhtälöpari (mikäli mahdollista) ja tarkistetaan ratkaisun käypyys. Käyvässä kantaratkaisussa ei ole negatiivisia muuttujia.

Käypien kantaratkaisujen selvittäminen

Laske allaolevaan taulukkoon kantamuuttujien arvot ja luokittele kussakin tapauksessa kantaratkaisu joko käyväksi tai ei-käyväksi. Teknisistä syistä tulee kantamuuttujien arvot syöttää listan sisällä samassa järjestyksessä kuin ne ovat taulukon vasemmanpuolimmaisimmassa sarakkeessa.

Kantamuuttujat | Kantamuuttujien arvot | Kanta käypä?
\(s_1\) ja \(s_2\) |  |
\(x_1\) ja \(s_1\) |  |
\(x_2\) ja \(s_1\) |  |
\(x_1\) ja \(s_2\) |  |
\(x_2\) ja \(s_2\) |  |
\(x_1\) ja \(x_2\) |  |

Funktion \(z\) optimointi

LP-tehtävä voidaan aina ratkaista myös niin, että lasketaan tavoitefunktion arvot kaikissa käyvissä kantaratkaisuissa ja valitaan niistä suurin tai pienin riippuen tavoitteesta. Ratkaise ylläoleva LP-ongelma tällä menetelmällä.

\(z_{\rm max}\) =

Jos harrastuneisuutta ja tarmoa tenttiin valmistautumiseen riittää, voit lopuksi piirtää kuvan käyvästä alueesta, ratkaista tehtävän graafisesti ja miettiä mikä yleinen piirre on käyvillä ja toisaalta kaikilla ei-käyvillä kantaratkaisuilla kuvassa.

/*Tyylittelyjä*/ /*[value][value][value]*/

Lähtötiedot

Tarkastellaan LP-tehtävää, jossa on tarkoitus maksimoida funktio \(z = 5x_1 + 3x_2 + x_3\) ehdoin

\[ \left\{ \begin{aligned} x_1 + x_2 + x_3 &\leq [value],&(1)\\ 5x_1 + 3x_2 + 6x_3&\leq [value],&(2)\\ x_1,x_2,x_3 &\geq 0 \end{aligned} \right. \]

Ongelmaa on lähdetty ratkaisemaan taulukkomuotoisella Simplex-menetelmällä, ja tietyn iteraatiomäärän jälkeen on saatu seuraavanlainen taulukko:

Kanta | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | Ratkaisu
\(z\) | [value] | [value] | [value] | [value] | [value] | [value]
\(s_1\) | [value] | [value] | [value] | [value] | [value] | [value]
\(x_1\) | [value] | [value] | [value] | [value] | [value] | [value]

(a) Alkuperäisen taulukon tila

Mikä on kunkin muuttujan arvo tämänhetkisessä kantaratkaisussa? Entä mitkä muuttujista ovat kanta- ja ei-kantamuuttujia?

Muuttuja | Muuttujan arvo | Onko kantamuuttuja?
\(x_1\) |  |
\(x_2\) |  |
\(x_3\) |  |
\(s_1\) |  |
\(s_2\) |  |

Onko funktion arvo optimaalinen?

.

(b) Yksi iteraatio lisää

Suorita yksi Simplex-iteraatio lisää niin, että muuttujien \(x_1\) ja \(x_2\) roolit vaihtuvat (kantamuuttujasta ei-kantamuuttuja ja päin vastoin). Täytä tätä seuraavaa iteraatiota vastaava taulukko alle.

Kanta | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | Ratkaisu
\(z\) |  |
\(s_1\) |  |
\(x_2\) |

Onko uusi ratkaisu optimaalinen?

Mikä on selitys tälle?

Kuva 1 - Optimointialue  (kuva avautuu linkkiä klikkaamalla).

Oletetaan, että oheisen Kuvan 1 monisärmiö esittää jonkin kolmen muuttujan LP-tehtävän käypää ratkaisualuetta. Oletetaan myös, että ongelmaa lähdetään ratkaisemaan Simplex-algoritmilla niin, että ratkaisu aloitetaan käyvästä kantaratkaisusta \(A\), eli origosta, ja että yksikäsitteinen optimiarvo saavutetaan pisteessä \(H\).

Alla on esitetty 10 erilaista polkua pisteestä \(A\) pisteeseen \(H\). Ilman tarkempaa tietoa tavoitefunktiosta, voidaan osaa näistä poluista pitää Simplex-algoritmille mahdollisina, osa taas on kahdesta eri syystä selvästi mahdottomia. Reitit voidaan siis luokitella yhteen tai useampaan seuraavista kategorioista.

1. Reitti on periaatteessa mahdollinen.
2. Reitti ei ole mahdollinen, sillä iteraatioiden välissä vaihtuu useampi kuin yksi kantamuuttuja.
3. Reitti ei ole mahdollinen, sillä saapuvaa muuttujaa ei aina valita niin, että tavoitefunktion arvo kasvaisi mahdollisimman paljon.

Luokittele reitit näihin kolmeen eri kategoriaan.

(a) \(A \to B \to G \to H\)

(b) \(A \to D \to G\to H\)

(c) \(A \to C \to I \to H\)

(d) \(A \to C \to E \to B \to A \to D \to G \to H\)

(e) \(A \to C \to E \to B \to G \to H\)

(f) \(A \to D \to F \to D \to G \to H\)

(g) \(A \to C \to E \to I \to H\)

(h) \(A \to C \to E \to I \to J \to H\)

(i) \(A \to D \to F \to H\)

(j) \(A \to E \to I \to H\)