Tárgyfelelős: Dósa György, MTA doktora (dosa.gyorgy@mik.uni-pannon.hu)
A tárgy az alábbi tárgy ismeretét tételezi fel, arra épít:
Lineáris és nemlineáris programozás
Tematika:
Egészértékű programozás, a feladat formalizálása, relaxált feladat, egészértékű feladatok és modellek, megoldási módszerek, korlátozás és szétválasztás alapú algoritmusok.
Hálózati programozás: hálózati modellek, hálózati folyam probléma és változatai mint egészértékű programozási feladatok.
Egészértékű és vegyes egész értékű programozási feladatok és modellszintű leírásuk.
Vágósíkos módszerek egész- és vegyes-egész értékű programozási feladatok megoldására.
Heurisztikák alkalmazása egészértékű feladatok megoldására (becslések, genetikus algoritmus, tabu keresés, szimulált hűtés).
Utazóügynök probléma. Heurisztikák utazó ügynök probléma megoldására.
Hozzárendelési feladat és változatai. A Magyar-módszer és változatai. Mohó segédalgoritmusok
Halmazlefedési probléma: matematikai modellek és heurisztikák.
Ütemezési feladatok.
Ládapakolási feladatok (egy és többdimenziós változatok).
Esettanulmányok (nagyméretű) egészértékű feladatokra, és azok megoldására.
Irodalom:
Nemhauser, G. L. and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, New York, 1988.
Schrijver, A., Theory of Linear and Integer Programming, John Wiley & Sons, New York, 1986.
Rockafellar, R. T., Network Flows and Monotropic Optimization, John Wiley & Sons, New York, 1984.
Papadimitriou C. H. and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall Inc., New Jersey, 1982.
Winston, W.L.: Operations Research : Applications and Algorithms.:, Duxbury Press, 2004