A matematikai megfogalmazása a hozzárendelési problémát
Mielőtt a probléma megoldásához szükséges, hogy megszüntesse az egyensúly hozzáadásával fiktív munka vagy gép függően a kezdeti feltételek. Ezért Az általánosság elvesztése nélkül, tudjuk állítani m = n.
Legyen xij = 0, ha j-i műveletet nem hajtunk végre az i-edik gép,
xij = 1, eslij-I munkát végeznek az i-edik gép.
Így, az oldatot felírható egy kétdimenziós tömböt X = (xij). Egy lehetséges megoldás az úgynevezett hozzárendelési. Egy lehetséges megoldás úgy van kialakítva, hogy kiválasztunk egy elemet minden sorban a mátrix X = (xij), és egy elem minden egyes oszlopban a mátrix. Egy adott érték az n n! megvalósítható megoldásokat.
Most a probléma a következőképp alakul:
első csoport korlátozások szükségesek, hogy minden munkát végezni egyszerre. Korlátozások a második csoport biztosítja, hogy mindenki kap egy feladatot.
Annak illusztrálására, a hozzárendelési probléma, fontolja meg egy asztal, három munkahely és három gép.
A sajátos szerkezetét a feladat feladat segítségével használni egy hatékony módszer megoldására.
Megjegyzés. Az optimális megoldás nem változik, ha bármelyik sorban vagy oszlopban a mátrix értékek kivonni tetszőleges konstans értéket (csökkenés).
A megadott megjegyzés azt mutatja, hogy ha egy új mátrixot nullákkal és a nulla elemek, vagy azok egy részhalmazát megfelelnek az elfogadható megoldás, egy ilyen megoldás lesz optimális:
5 7 9 5 0 2 4 0 2 2
C = 14 10 12 10 4 0 2 4 0 0
15 13 16 13 2 0 3 1 2 0
Mivel a feladat probléma egy speciális esete a TK kezelésére lehet használni bármilyen algoritmus lineáris programozás, de hatékonyabb a magyar módszer (algoritmus).
ÖSSZEFOGLALÁS magyar módszer az, hogy az eredeti mátrix CIJ kap m = n független nullák, t. E. hogy minden egyes sorban vagy oszlopban kell csak egy nulla.
Lépés 1.Reduktsiya sorok és oszlopok.
E lépés az, hogy a maximális lehetséges számát nulla elemek a mátrixban értékek. Ebből a célból minden elemét az egyes sorok levonjuk a minimális megfelelő sorában elemet, majd az összes elem az egyes oszlopok a kapott mátrix levontuk a minimális eleme a megfelelő oszlop. Az eredmény a csökkentett értékek mátrixából, és továbblép a keresni kinevezések.
Lépés 2.Modifikatsiya csökkentett mátrix.
A csökkentett mátrix értékek:
a) kihúz a sorok és oszlopok, amelyek a maximális számú nullát. Továbbá, mozgó a sorok (fentről lefelé) és oszlopok (balról jobbra) van eltávolítottak vonalak, illetve, majd az oszlopok, amely nulla elemeket.
b) az így kapott kondenzált mátrixon elem és válassza a minimális:
- Vonjuk ki az összes nem törölt sejtek;
- Adjuk hozzá az elem található a két egyenes metszéspontját.
Lépés 3.Proveryaem terv optimalitást.
Ha ez nem optimális, ismételje meg a 2. lépést.
1) Ha a sorok száma szükség, hogy törli a nulla elemek egyenlő a sorok számát (oszlopok), van egy teljes hozzárendelés.
2) Ha a kezdeti feladat a feladat, hogy maximalizálják, minden elem a mátrix értékek meg kell szorozni (- 1), és verem őket egy kellően nagy számú, hogy a mátrix nem negatív elemeket tartalmaznak. Ezután a problémát meg kell oldani, mint minimalizálását probléma.
Megmutatjuk a munkát a magyar módszer egy példát hozzárendelési probléma a következő értékek mátrixa:
Be kell, hogy fordítson forrásokat a tárgyakat úgy, hogy a teljes költség minimális volt
Lépés 1.Reduktsiya sorok és oszlopok.
Az értékek a minimális elemeket sorok 1, 2, 3 és 4 egyenlő 2, 4, 11 és 4, ill. Kivonása az elemek minden sor megfelel egy minimális érték, megkapjuk a következő mátrix:
Az értékek a minimális elemeket oszlopok 1, 2, 3 és 4 0, 0, 5 és 0, ill. Kivonása az elemek az egyes oszlopok megfelel egy minimális érték, megkapjuk a következő mátrix:
=
Ebben a mátrixban a 3. sor és oszlop 1 két nulla, R. F., mely szükséges egy további módosítása a csökkentett értékek a mátrix (optimális terv nem kapott).
Lépés 2.Modifikatsiya csökkentett mátrix.
Megkapjuk a rövidített értékek mátrixa:
Ez a minimális adunk az elemek a csökkentett mátrix felé néző törlik a kereszteződésekben a sorok és oszlopok (11, 2). Az eredmény egy módosított mátrix:
Lépés 3.Proveryaem kapott optimális tervet, és találkozókat.
Megkeresi vonósok, egy nulla, és jegyezze meg. Ez a vonal 2. A következő sort-4. Megjegyezzük, a nulla ezen a vonalon, míg a fennmaradó rész eltávolítottak nullát az első oszlopban. A következő sorban tartalmazó 0-1 jelet ennek nulla egyidejűleg eltávolítottak nulla 3. oszlopban. Megjegyezzük, a nulla 4. oszlopban. Minden nullák függetlenek, azaz a. E. kaptunk optimális tervet. Impozáns, módosított mátrix az eredeti költség mátrix, azt látjuk, hogy a kinevezések.
Impose kezdeti módosított mátrixot, azt kapjuk, F (x) = 4 + 9 + 11 + 4 = 28
V: Az első erőforrás célja a 3. tárgy, a második - a 2. tárgy, a negyedik - az 1. cél, a harmadik forrás - a 4. objektumot. rendeltetési költség: 9 + 4 + 11 + 4 = 28.
1. megjegyzés: Ha az eredeti mátrix nem tér, meg kell adnia a fiktív források vagy ál tárgyak, a mátrix vált téren.
Így a lényege a magyar módszer a következő: Azáltal, egy bizonyos módon a számok találhatók néhány oszlopot, majd levont bizonyos számok rendszere az úgynevezett független nullák. Egy sor nullák nevezzük rendszer független nullák, ha bármely két (vagy több) a nulla nem fekszik ugyanazon a vonalon (egy sorban vagy oszlopban). Ha a több független nullák n, akkor azáltal, hogy a megfelelő változók HIJ jelentése 1, és az összes többi - a 0, megkapjuk az optimális hozzárendelés tervet.