4.PROBLEM RAZVOZA

problem razvoza, problem razvoza z omejitvami

definicija problema razvoza

Imamo usmerjen utežen graf G=(V,E), kjer je V množica vozlišč in E množica usmerjenih povezav, ter uteži na vozliščih b_v ∈ R( v∈V) in uteži na povezavah c_uv ∈ R( uv ∈ E), kjer:

• b_v ≥ 0, če je v vozlišču v poraba b_v, in

• b_v < 0, če je v vozlišču v proizvodnja −b_v.

Predpostavimo ∑_v∈V b_v = 0.

iščemo x_uv > 0 za vsako povezavo uv ∈ E, tako da velja Kirchhoffov zakon:

∀v ∈ V: ∑_uv∈E x_uv − ∑_vu∈E x_vu = bv.

Radi bi minimizirali ceno ∑_uv∈E c_uvx_uv

zapiši problem razvoza kot linearni program

definicija drevesna dopustna rešitev za problem razvoza + trditev

definicija:

Dopustna rešitev x za problem razvoza Π na grafu G=(V,E) je drevesna dopustna rešitev, če v grafu G obstaja vpeto drevo T=(V,E′), da velja x_e= 0 za vsak e∈ E \ E′.

trditev:

če ima problem razvoza dopustno rešitev, ima tudi drevesno dopustno rešitev

definicija prema in obratna povezava

Naj bo G usmerjen graf in C cikel v G, ki vsebuje povezavo f. Potem je povezava e v ciklu C (glede na povezavo f) prema, če kaže v isto smer kot f, in obratna sicer.

opiši simpleksno metodo na Omrežjih

kdaj je rešitev optimalna?

dvofazna simpleksna metoda:

Kako pridemo do Začetne dopustne rešitve oziroma dokažemo, da je problem nedopusten?

Izrek o Celoštevilskih Rešitvah

Dan je problem razvoza s celoštevilskimi vrednostmi b_v (v∈V).

1. Če obstaja dopustna rešitev, obstaja tudi celoštevilska dopustna rešitev.

2. Če obstaja optimalna rešitev, obstaja tudi celoštevilska optimalna rešitev.

dokaži izrek o celoštevilskih Rešitvah

definicija problem razvoza z omejitvami

definicija ( prazna in nasičena povezava )

definicija drevesna dopustna rešitev (problem razvoza z omejitvami)

Naj bo x dopustna rešitev problema razvoza z omejitvami. Rešitev x je drevesna dopustna Rešitev, če obstaja vpeto drevo T = ( V, E’ ) v grafu G = ( V, E ), da velja ∀e ∈ E \ E’ : (x_e = 0 ∨ x_e = d_e)

(torej, povezave izven drevesa so prazne ali nasičene).

trditev optimalna rešitev ( problem razvoza z omejitvami )

Naj bo x drevesna dopustna rešitev problema razvoza z omejitvami za vpeto drevo T=(V,E′) v grafu G=(V,E) ter y razvozne cene (tj., ∀uv ∈ E′: y_u + c_uv = y_v ). Če za vsako povezavo uv∈ E \ E′ velja (x_uv =0 ∧ y_u + c_uv ≥ y_v ) ∨ (x_uv = d_uv ∧ y_u + c_uv ≤ y_v ),potem je x optimalna rešitev.

dodatna mini Vprašanja:

1. katere probleme Rešujemo z osnovno simpleksno metodo na omrezjih?

2. kaj velja za osnovno rešitev, kako pridemo do osnovne rešitve?

3. kako določamo vhodne in izhodne povezave?

4. kako preberemo rešitev kakšne rešitve so možne?

1. probleme prevoza

2. osnovna rešitev ima drevesno strukturo ( brez ciklov ), opišeš postopek SM na omrežjih

3. vhodna povezava (e) je povezava izven drevesa na grafu G, za katero velja y_u + c_uv < y_v, ta je na natanko enem ciklu C v grafu H = (V, E’ U {e}). izstopna povezava (f) pa je obratna povezava na tem ciklu z Najmanjšo vrednostjo x_f

4. rešitev preberemo tako, da pogledamo vrednosti x_uv na vseh povezavah, optimalna vrednost pa je Σ_{uv iz E’} c_uvx_uv