A hozzárendelési probléma megoldása nem degenerált lineáris szállítási feladatként

Absztrakt

Az ún. hozzárendelési probléma az operációkutatás egyik klasszikus feadattípusa. Megfogalmazását tekintve lineáris szállítási feladat, ennek ellenére a lineáris programozás hagyomnyos módszereivel eddig gyakorlatilag nem volt kezelhető. A legismertebb megoldási algoritmusa a külön oerre a célra kifejlesztett ún. magyar módszer, melyet H. KUHN javasolt 1955-ben; ez EGERVÁRY JENŐ egy mátrix-kombinatorikai tételén alapul.
Az alábbiakban szintén egy kombinatorikai tételt bizonyítunk be a mátrixok egy osztályára. Ennek ismerete lehetővé teszi, hogy a hozzárendelési feladatot olyan lineáris szállítási feladattal helyettesítsük, amelynek mérete (és költségmátrixa) az eredetivel azonos, de ahol a hozzárendelési feladatra jellemző ún. degeneráció előfordulása kizárt. A transzformáció előnye, hogy az új modellen a hozzárendelési feladat esetleges alternatív optimumainak megkeresése és az érzékenységi vizsgálatok is egyszerűbben, a szállítási feladatoknál általában alkalmazott módon vihetők keresztül.