Exam text content

MATH.APP.260 Operaatiotutkimus
Tentti 05.05.2023 Frank Cameron
Huom 1: Opiskelija saa käyttää taskulaskinta.
Huom 2: Näytä välivaiheita.

Huom 3: Tentissä on 4 sivua.

1. Tässä tehtävässä tarkastellaan kaupparatsuongelmaa, jossa on n kaupunkia ja joukko
N määritellään seuraavasti:
NS 15240 Ih]

Oletetaan, että kaupparatsuongelman optimointimallissa käytetään seuraavia binääri-
muuttujia:

,1€EN,jEN,

1 jos kaupungista i kaupparatsu menee seuraavaksi kaupunkiin j
TIS
X 0 muulloin

Näiden lisäksi käytetään muuttujia u;, i = 2,3, ...n. Yksi perinteinen esitys kauppa-
ratsuongelman optimointimallille annetaan tässä:

min ya Mi Ci Dij (1)

iEN jEN

M zy<1, iceN (2)
JEN

Dayn jEN (3)
1EN

n E =in  10S0.3. 08 17 — 2.3, n, (4)
ij € (0,1),1€N, jEN (5)

Oletetaan, että n = 5. Käyvällä ratkaisulla on kaksi ominaisuutta:

e jokaisella muuttujalla on arvo
e muuttujien arvoilla voidaan osoittaa, että jokainen rajoite toteutuu

Osittainen ratkaisu on sellainen, että vain osalla muuttujista on arvo. Joskus on mahdol-
lista täydentää osittainen ratkaisu käyväksi ratkaisuksi antamalla jokaiselle puuttuvalle
muuttujalle arvo. Kussakin kohdassa (a) ja (b) on osittainen ratkaisu. Kullekin kohdalle
vastaa seuraaviin kysymyksiin: i

    
  
 

(i) Voidaanko osittainen ratkaisu täydentää käyväksi ratkaisuksi!

ratkaisuksi.

  

(a) (4p) us =3, 253 = 1, 714 = 0, 212 =0, 213
 

2. Tässä tehtävässä käytetään seuraavaa verkkomallia:

  

Oletetaan, että jokaiseen virtaukseen 21 liittyvä väli on [0, 1]. Seuraavat joukot määri-
tellään, jotta voidaan muodostaa verkkomallia vastaava. optimointimalli.

P= (a,b,0,f)

0 = (1,2,3,4,5,6, 7,8,9,10,11)

R = ((d, 1), (d, 2), (c,3), (1.4), (G 5), (c, 6), (e, 7), (a, 8), (b, 9), (b, 10), (d, 11))

5 = ((6.D, (1.2); (2,3), (c.4), (6,5), (b, 6), (e, 7), (c,8), (4,9), (e. 10), (ä, 11))
Näiden lisäksi määritellään kuhunkin virtaukseen 2; liittyvä kustannus:

ALL S 5 6.75 070 i
10598 6... 0

Näiden avulla ehdotetaan seuraavaa optimointimallia:

min DW Cm: (6)
i€0
BOINC (7)
(j)eR (ik)ES
x; >0,1€0 (8)
Ta 10/0 (9)

(a) (4p) Ikävä kyllä rajoitteita puuttuu optimointimallista (6)-(9). Muodosta puuttu-
vat rajoitteet.
Huom: Anna ainoastaan puuttuvat rajoitteet.

(b) (5p) Oletetaan, että x; = 1/2, x6 = 0 ja T10 = 1/4. Täydennä tämä osittainen
ratkaisu kokonaiseksi käyväksi ratkaisuksi.

(c) (5p) Määritellään seuraavat binäärimuuttujat:

   
  
 

5 = 1 jos pisteestä i lähtee ainakin yksi nollasta poikkeava virtaus
* ]0 muulloin

Halutaan lisätä seuraava ehto optimointimalliin: i
Joukon P pisteistä korkeintaan kahdesta lähtee nollasta poi
Käyttäen binäärimvuttujia 6, i €

jotta tämä ehto otetaan huomioon.

  
3. Mari on projektipäällikkö. Hänen ryhmänsä on vastuussa lukuisista projekteista seu-
raavan puolen vuoden aikana. Marin ryhmässä on lukuisia työntekijöitä, jotka hänen
ja osoitettava viisaasti näihin projekteihin. Hän haluaa muodostaa mallin, joka auttaa
häntä päättämään, mitkä työntekijät tulisi osoittaa mihinkin projektiin. Hän aloittaa
määrittelemällä seuraavat joukot.

UV = (työntekijät Marin ryhmässä]

0 = ( projektit, joista Marin ryhmä on vastuussa seuraavan puolen vuoden aikana)

Hän myös määrittelee seuraavat muuttujat:

Oi; = ,1€V, jen

1 kun työntekijä i osallistuu projektiin j
0 kun työntekijä i ei osallistu projektiin j

%;j = kuinka monta viikkoa työntekijä i tekee työtä projektissa j ,i € V, j e 0

Kussakin kohdassa (a), (b), (c), (d), (e), (£) ja (g) esitetään ehto, jonka Mari haluaa sisäl-
lyttää optimointimalliin. Muodostaa kullekin ehdolle lineaarinen rajoite (tai lineaariset
rajoitteet).

(a) (2p) Mari haluaa, että jokainen työntekijä osallistuu ainakin 3 projektiin.

(b) (2p) Mari haluaa, että jokaiseen projektiin osallistuu korkeintaan 10 työntekijää

 

() (2p) Mari määrittelee parametrin t; kuvaamaan, kuinka monta työviikkoa yhteensä
työntekijä i voi käyttää projekteihin. Siis työntekijä i saa tehdä työtä projekteissa
korkeintaan %; työviikkoa.

(d) (2p) Työntekijän i työviikkojen määrä projektissa j on nollasta poikkeava ainoas-
taan silloin, kun hän osallistuu projektiin j.

(e) (2) Jos työntekijä osallistuu projektiin, Mari haluaa, että työntekijä on tosissaan
mukana. Näin ollen, jos työntekijä i osallistuu projektiin j, niin hänen täytyy tehdä
ainakin 4 viikkoa työtä projektissa.

(£) (2p) Hän tietää, että joidenkin työntekijöiden osaamista ei tietyissä projekteissa
tarvita. Näin ollen, hän määrittelee seuraavan joukon:
A = f(i,5) : työntekijä j ei osallistu projektiin i)
Muodosta rajoite (tai rajoitteet), jossa joukko A otetaan huomioon.
(g) (4p) Mari on jakanut ryhmänsä työntekijät 3 luokkaan kokemuksen perusteella:
luokka I työntekijällä on korkeintaan 1 vuoden kokemus

luokka II työntekijällä on 1-3 vuoden kokemus
luokka III työntekijällä on enemmän kuin 3 vuoden kokemus

Jotta hän voi ottaa nämä luokat huomioon, Mari määrittelee se

  
  
 
     

T = ((6,5) : työntekijä i kuuluu luokkaan j,i € W, j € (1

Esimerkiksi, kun työntekijä 4 kuuluu luo!
Mari haluaa, että kaikista projektiin
jäsosa voi kuulua luokkaan 1.
4. Oletetaan, että on lineaarinen optimiointimalli, jonka käypä alue on kolmio (11, 72)-
tasossa. Kolmion kulmien koordinaatit ovat (=a,2). (a,2) ja (a,a + 2), jossa a > 0.
Tämä kolmio esitetään seuraavassa kuvassa.

 

Kolmion pinta-ala on 1.

(a) (2p) Laske a:n arvo.

(b) (6p) Muodosta rajoitteet, jotka määrittävät käyvän alueen.

(c) (2p) Keksi käypä ratkaisu, jossa on täsmälleen 1 sitova rajoite.
(d) (2p) Oletetaan, että optimointimallin kohdefunktio on

min 21 + cr?

    

  

illa optimointimallin optimiratkaisu on (a,a + 2)?
K4G6 aki ;