4 PROBLEM RAZVOZA, PRETOKI IN PREREZI

Opiši graf s katerim rešujemo probleme razvoza.

Usmerjen utežen graf G = (V, E); V - množica vozlišč, E - množica povezav

b_v € IR uteži na vozliščih in c_uv € IR uteži na povezavah.

b_v < 0 : proizvajalec, b_v >= 0 : porabnik, vsota vseh b_v = 0

Kirchhoffov zakon

incidenčna matrika

zapiši problem razvoza kot linearni program

b € IR^v, c € IR^e

zapiši dual problema razvoza

Kdaj sta x,y dopustni in optimalni rešitvi?

x_uv = 0 pomeni: med u in v ne prevažamo ničesar

y_{u +} c_uv = y_v pomeni: dualna cena u + utež na povezavi uv = dualna cena v

dopustna rešitev za problem razvoza

x_e = 0 pomeni: po vseh povezavah, ki niso del drevesne dopustne rešitve nič ne peljemo

preme in obratne povezave

Naj bo G usmerjen graf s ciklom C in povezavo f v ciklu. Povezava e € C je prem, če glede na f kaže v isto smer, sicer je obratna.

simpleksna metoda na omrežjih

optimalna rešitev problema razvoza

Kjer je c_uv: cena prevoza, y_u: cena v začetnem mestu u, y_v: cena v končnem mestu v

dokaži

Opiši kako določimo koren.

umetne in prvotne povezave

zveza med prvotnim in pomožnim problemom

Prvotni problem je dopusten natanko tedaj, ko je optimalna vrednost pomožnega problema enaka 0. Ker so vse cene v pomožnem problemu nenegativne, je problem omejen.

izrek o celoštevilskih rešitvah

dokaži izrek o celoštevilskih rešitvah

dvojno stohastična matrika

pomeni: vsota elementov poljubnega stolpca/vrstice = 1

permutacijska matrika

P € {0, 1}^nxn : v vsaki vrstici in stolpcu je natanko ena enica

zveza med stohastično in permutacijsko matriko

nxn stohastična matrika A, potem obstaja taka permutacijska matrika P, da velja:

p_ij = 1 → a_ij > 0

prirejanje in popolno prirejanje

Königov izrek o plesnih parih

Naj bo G = (V, E) dvodelen regularen graf in množico vozlišč zapišemo kot V = X + Y in IXI = IYI. Potem v grafu obstaja popolno prirejanje.

opiši graf problema razvoza z omejitvami

Usmerjen utežen graf G = (V, E); V - množica vozlišč, E - množica povezav

b_v € IR uteži na vozliščih in c_uv € IR uteži na povezavah.

b_v < 0 : proizvajalec, b_v >= 0 : porabnik, vsota vseh b_v = 0

d_uv € [0, neskončno) : omejitev na povezavi

zapiši problem razvoza z omejitvami kot linearni program

prazna in polna/nasičena povezava

Pri dopustni rešitvi x je povezava e:

• polna: x_e = d_e < neskončno

• prazna: x_e = 0

Kakšne so povezave izven drevesne dopustne rešitve?

optimalna rešitev problema razvoza z omejitvami

rešitev pomeni: (pretok je 0 in prevoz je predrag) ali (pretok je maximalen in poceni)

simpeksna metoda za problem razvoza z omejitvami

opiši dvofazno simpleksno metodo za problem razvoza z omejitvami: koren, prvotne in umetne povezave

opiši problem max pretoka

Imamo usmerjen graf G = (V, E) in pretočnost d_e za vsako povezavo e € E. Iščemo max pretok, da velja:

0 =< x_e =< d_e

prostornina pretoka

Kjer je s začetno in t končno vozlišče:

zapiši LP za max pretok

povečujoča pot

Povečujoča pot je v₀v₁……v_k;

v_i € V in v₀ = s, v_k = t

Povečujoča pot sestoji iz premih povezav, ki niso nasičene, in obratnih povezav, ki niso prazne.

prema, obratna povezava

v_i vozlišče, d_vi pretočnost

Ford-Fulkersonov algoritem

Ko ni več povečujočih poti, smo našli optimalno rešitev.

prerez

kapaciteta prereza

zveza med pretokom in prerezom

Kdaj je pretok max in prerez min?

F = K

Kaj velja za problem max pretoka in min prereza?

Velja natanko ena od:

dokaži prejšnji izrek