Sok gazdasági jellegű feladat, problémaaz emberi élet más területein felmerülő kérdések megtervezése és még megoldása egész számokkal kapcsolatos változókhoz kapcsolódik. Elemzéseik és az optimális megoldások keresése eredményeként megjelent egy szélsőséges probléma fogalma. Jellemzői a fenti tulajdonság, hogy egész értéket kapjanak, és maga a feladat a matematikában egész szám programozásnak tekinthető.
Mivel a felhasználás fő irányaAz egész értékeket figyelembe vevő változókkal végzett feladatok az optimalizálás. Az egész lineáris programozást alkalmazó módszert vágási módszernek is nevezik.
A Gomori módszer nevét kaptamatematika, az első, aki 1957-1958-ban dolgozott ki egy algoritmust, amelyet még mindig széles körben használnak egész számú lineáris programozási problémák megoldására. Az egész programozási probléma kanonikus formája lehetővé teszi számunkra, hogy teljes mértékben és teljes mértékben feltárjuk ennek a módszernek az előnyeit.
Gomori módszer a lineárisraA programozás jelentősen megnehezíti az optimális értékek megtalálását. Végül is az integeritás a fő feltétel, a probléma összes paraméterén túl. Gyakran előfordul, hogy egy elfogadható (egész) tervvel rendelkező probléma, ha az objektív funkcióknak korlátozása van egy megengedhető halmazra, nem éri el a megoldásban szereplő maximális értéket. Ez egész számú megoldás hiányának tudható be. E feltétel nélkül általában megfelelő vektor található oldat formájában.
A numerikus algoritmusok alátámasztására a problémák megoldása során különféle kiegészítő feltételeket kell előírni.
A Gomori módszerrel soka problématerveket az úgynevezett megoldások sokszöke korlátozza. Mindezek alapján az következik, hogy a feladathoz tartozó összes egész terv halmaza véges.
Ezenkívül a függvény integritásának garantálása érdekében feltételezzük, hogy az értékek együtthatói is egészek. Az ilyen körülmények súlyossága ellenére lehetséges egy kicsit ellazítani.
A Gomori módszer lényegében olyan megszorítások megteremtését foglalja magában, amelyek elválasztják az egészben nem értékelt döntéseket. Ugyanakkor az egész terv egyetlen megoldása sem szakad meg.
A probléma megoldására szolgáló algoritmus tartalmazzamegfelelő variánsok megtalálása a simplex módszerrel, az egész feltételek figyelembevétele nélkül. Ha az optimális terv minden összetevőjében vannak megoldások egész számokra, akkor feltételezhetjük, hogy az egész szám programozásának célja elérhető. Lehetséges, hogy felfedezték a probléma megoldhatatlanságát, így bizonyítékot kapunk arra, hogy az egész szám programozási problémájának nincs megoldása.
Ez az opció lehetséges, ha az alkatrészekben vannakAz optimális megoldás nem egész számot tartalmaz. Ebben az esetben egy új kényszert adunk a feladat összes korlátozásához. Az új korlátozást számos tulajdonság jellemzi. Először is lineárisnak kell lennie, és egy egész szám nélküli tervet kell levágnia a megtalált optimális halmaztól. Egy egész számot sem szabad elveszíteni, csonkolni.
A korlátozások megalkotásakor az optimális terv azon részét kell kiválasztani, amelynek a legnagyobb tört része. Ez a korlátozás hozzáadódik a meglévő szimplex táblához.
Megoldást találunk a problémára a következő használatávalrendes simplex transzformációk. Ellenőrizzük a probléma megoldását egész szám optimális terv létezésére, ha a feltétel teljesül, akkor a probléma megoldódik. Ha ismét eredményt kapunk nem egész számú megoldások jelenlétével, akkor vezetünk be egy további korlátozást, és ismételjük meg a számítási folyamatot.
A véges számú iteráció elvégzése után megkapjuk az optimális tervet az egész programozáshoz felvetett problémára, vagy bebizonyíthatjuk a probléma megoldhatatlanságát.
