Nastavljamo dalje prema materijalima iz skripte - str. 51-58, ali se ponovno vraćamo na istu temu nakon što obradimo problem određivanja maksimalnog toka/minimalnog reza. To nam je u planu dovršiti u idućem tjednu pa bi bilo dobro već u ovom krenuti s osnovnim pojmovima (rezultati dualnosti) za problem maksimalnog toka na transportnoj mreži str. 59-70. Za sada neće biti jasna veza ova dva problema, to ostavljamo za idući tjedan.
U problemu dodjeljivanja cilj je rasporediti n radnika na n poslova (jedan na jedan) tako da od n! mogućnosti odaberemo onu s minimalnim ukupnim troškom (za svakog radnika poznato je koliki je trošak njegove obuke za svaki posao - tablica troškova).
Zanimljivo je da se radi o posebnom slučaju transportnog problema, no rješavamo ga potpuno drugačijom metodom... Ključno je dobro razumjeti Primjer 6! Vezano uz razumijevanje, dodatno pitanje - je li ponuđeno rješenje jedinstveno (postoji li raspored s istim troškom)? Molim odgovor!
Uvode se pojmovi maksimalnog sparivanja i minimalnog pokrivača i bitno je na dosta primjera provježbati kako ih prepoznati. Pravi (algoritamski) pristup će biti obrađen idući tjedan, ali na manjim primjera dovoljno je "prepoznavanje". Oni su ključni u formulaciji mađarske metode - jezgra ovog dijela. Metoda je demonstrirana samo na jednom primjeru pa ju je bitno još malo provježbati (str. 162-163).
U uvodnom dijelu o transportnim mrežama cilj je uvesti međusobno dualne probleme traženja makstimalnog toka i minimalnog i-p reza. Ovdje veza s pravom dualnošću u linearnom programiranju nije tako očita (ali se ipak može dobiti) tako da se nećemo osloniti na nju već direktno dokazati teoreme slabe i jake dualnosti. Kao i u svim drugim primjenama već slaba dualnost nam pomaže prepoznati (potvrditi) rješenja primarne i dualne zadaće - tako je i riješen Primjer 8.
Nastavljamo dalje prema materijalima iz skripte - str. 51-58, ali se ponovno vraćamo na istu temu nakon što obradimo problem određivanja maksimalnog toka/minimalnog reza. To nam je u planu dovršiti u idućem tjednu pa bi bilo dobro već u ovom krenuti s osnovnim pojmovima (rezultati dualnosti) za problem maksimalnog toka na transportnoj mreži str. 59-70. Za sada neće biti jasna veza ova dva problema, to ostavljamo za idući tjedan.
U problemu dodjeljivanja cilj je rasporediti n radnika na n poslova (jedan na jedan) tako da od n! mogućnosti odaberemo onu s minimalnim ukupnim troškom (za svakog radnika poznato je koliki je trošak njegove obuke za svaki posao - tablica troškova).
Zanimljivo je da se radi o posebnom slučaju transportnog problema, no rješavamo ga potpuno drugačijom metodom... Ključno je dobro razumjeti Primjer 6! Vezano uz razumijevanje, dodatno pitanje - je li ponuđeno rješenje jedinstveno (postoji li raspored s istim troškom)? Molim odgovor!
Uvode se pojmovi maksimalnog sparivanja i minimalnog pokrivača i bitno je na dosta primjera provježbati kako ih prepoznati. Pravi (algoritamski) pristup će biti obrađen idući tjedan, ali na manjim primjera dovoljno je "prepoznavanje". Oni su ključni u formulaciji mađarske metode - jezgra ovog dijela. Metoda je demonstrirana samo na jednom primjeru pa ju je bitno još malo provježbati (str. 162-163).
U uvodnom dijelu o transportnim mrežama cilj je uvesti međusobno dualne probleme traženja makstimalnog toka i minimalnog i-p reza. Ovdje veza s pravom dualnošću u linearnom programiranju nije tako očita (ali se ipak može dobiti) tako da se nećemo osloniti na nju već direktno dokazati teoreme slabe i jake dualnosti. Kao i u svim drugim primjenama već slaba dualnost nam pomaže prepoznati (potvrditi) rješenja primarne i dualne zadaće - tako je i riješen Primjer 8.
_________________
Marko Vrdoljak
