Optimizacija

[delta]

Zanima me, kako se reši tale naloga.
Poišči najcenejše popolno prirejanje v dvodelnem grafu, določenem z naslednjo matriko \(5 \times 5\): [a,b,3,1,1;2,-1,1,0,1;-1,1,3,1,0;1,0,2,3,3;2,1,-2,3,1]. Grd zapis matrike . Pri tem sta \(a,b\) poljubni realni števili. Določi tudi ceno tega prirejanja. Rabim do jutri zjutraj. Hvala

[Zajc]

Obravnavaš 3 možnosti. Prva možnost, da 1. izvajalec opravlja 1. opravilo - črtaš 1. stolpec in 1. vrstico. Druga možnost, če 1. izvajalec izvaja 2. opravilo (1. vrstica 2. stolpec). V teh dveh primerih dobiš 4krat4 matriko, ki jo rešuješ naprej. Tretja možnost je pa, če 1. izvajalec opravlja opravilo 3,4 ali 5. V tem primeru obdržiš 5krat5, le da a in b zamenjaš z neskončno.

[Zajc]

aha "jutri zjutraj" je pomenilo danes zjutraj