Exam text content

MAT-51250 — Matemaattinen optimointiteoria 2
Tentti 24.4.2006

Ei kirjallisuutta, muistiinpanoja, taulukoita tai laskimia mukana!

3.

Ehdon A; (i=0,...,n) toteutumista kuvataan muuttujalla x;, joka saa arvon 1, jos
4; on tosi ja arvon 0 muuten. Esitä seuraavat loogiset ehdot algebrallisessa
muodossa muuttujia x; koskevilla lineaarisilla yhtälöillä tai epäyhtälöillä (siis
muodossa, jossa ne voivat olla MILP-tehtävän rajoitusehtoina):

a) Jos 49 ei toteudu, niin korkeintaan yksi ehdoista A, ja 4 ja ainakin yksi

ehdoista 43,...,4n toteutuu..
b) Jos 4) toteutuu, niin mikään ehdoista 41,..., A, ei toteudu.

Miten esittäisit oheisen kuvan mukaisen käyvän joukon (varjostettu osa)
MILP-ongelman käypänä joukkona eli lineaarisina epäyhtälöinä muuttujista x;,
x» ja apumuuttujina toimivista (yhdestä tai useammasta) binäärimuuttujista?

 

 

a) Mitkä seuraavista matriiseista ovat totaalisesti unimodulaarisia?

ja 1J0
11 0
-1 0 0 1
A=|0 1 1), B=
0 1 0 -1
101
0 0 1 0

b) Kuvaile yleistä Jokaalin haun menetelmää ja erityisesti TSP:n lokaalin
haun algoritmia 2-opt.

Käännä!
4.

5

Ratkaise branch-and-bound-menetelmällä oheinen binäärinen knapsack-
ongelma

max z = 14x]+18x+22x3+26x4
x] + 3x2 + 4x3 + 6x4 < 7

x € B',x>0.

Jakeluautojen (K kpl) on toimitettava tavaraa tukkuliikkeen varastosta
asiakkaille, joita on N kpl. Asiakkaat 1, 2, ..., N ovat solmuina verkossa,
jonka kaaret ilmaisevat käytettävissä olevat tieyhteydet. Kaarien (i, j)

pituudet c; tunnetaan. Lisäksi verkossa on solmu 0, joka on varasto. Kunkin
asiakkaan i tarvitseman tavaramäärän tilavuus on d, . Kullakin autolla k on
tietty tilavuuden kapasiteetti a, . Miten tavarantoimitukset hoidetaan niin, että
jakeluautojen yhteenlaskettu ajokilometrimäärä minimoituu?

a) Tee ongelmasta MILP-malli.
b) Mitä voit sanoa probleeman laskennallisesta vaativuudesta?