Zadaci za vježbu (informacija)

[markov]

Vezano uz zadatak koji sam dao na vježbama 9.3. - zadaća je degenerirana pa ćemo o tome na idućim vježbama. Zato ću malo promijeniti brojke (samo a_3) tako da tablica
glasi:

	O1	O2	O3	a_i
I1	13	25	18	20
I2	15	14	26	30
I3	40	13	24	45
b_j	40	40	40

Kako smo rekli, dodajemo jedno fiktivno ishodište I4 uz a_4:=25 i c_4j:=0.
Rješenje je sljedeći bazični transport:

	O1	O2	O3
I1	10		10
I2	30
I3		40	5
I4			25

Dakle, O3 ostaje s 25 jedinica robe manje nego je trebao.

_________________
Marko Vrdoljak

[markov]

Zadaci vezani uz transportni problem koje sam danas pokazivao na nastavi.

_________________
Marko Vrdoljak

[gflegar]

Vezano uz 3. zadatak, da li možda fail pretpostavka da je transport određen s [tex]x_{ij}[/tex] bazičan? Npr. za problem

	O_1	O_2	a_i
I_1	1	1	2
I_2	1	1	2
b_j	2	2

i pripadni transport

	O_1	O_2
I_1	1	1
I_2	1	1

sustav iz zadatka ima jedinstveno rješenje [tex] u = (0, 0), v = (1, 1)[/tex], a podgraf određen s [tex]x_{ij}[/tex] nije stablo.

_________________
http://web.studenti.math.pmf.unizg.hr/~gflegar

[markov]

Odlična primjedba. Dakle pretpostavka je da ima najviše n+m-1 bridova na kojima je transport netrivijalan, tj. x je bazičan. Popravio sam i tekst zadatka u attachemntu gore. Hvala!

_________________
Marko Vrdoljak

[markov]

Referenca za praktična pitanja implementacije algoritama s predavanja:
Ahuja R.K., Magnanti T.L., Orlin J.B. Network flows.. theory, algorithms, and applications, Prentice Hall, 1993.

_________________
Marko Vrdoljak

[markov]

Još malo zadataka za vježbu.

_________________
Marko Vrdoljak

[markov]

Vezano uz kraj današnjeg predavanja, u prilogu je primjer dopustivog toka koji nije bazičan. Uočite slobodni ciklus i odredite bazični tok kao u dokazu leme s početka gradiva o minimalnim troškovima toka na mreži. Primijenite mrežnu simpleks metodu s ovim početnim tokom. Rješenje zadatka možete naći na temi " Zadaci za vježbu (informacija)" od 11. 4. 2014.

_________________
Marko Vrdoljak