Gomory módszer, egész programozási

Gazdasági és geometriai értelmezése egész programozási feladat. Extrém feladat változók, amelyeknek csak egész értékek, az úgynevezett problémája egész programozás.

A matematikai modell az egész programozási problémát, mivel az objektív függvény, és a függvény korlátozási rendszer lehet lineáris, nemlineáris és vegyes. Csak arra az esetre, ha a célfüggvény és a kényszer-rendszer a probléma lineáris.

Az üzletben a cég úgy döntött, hogy telepíteni extra felszerelés, amelyre a lefoglalt terület a szállás. A berendezések vásárlására, a cég töltheti 10.000. Dörzsöljük. míg lehet vásárolni két típusú berendezések. A berendezést valahogy költség 1000 rubel. és II-es típusú - 3000 rubel. Megszerzése egy sor berendezések I. típusú növelheti a kimenet egy műszakban 2 egységgel. és egy sor II típusú berendezés - 4 db. Annak ismeretében, hogy egy készlet berendezések I kell beírni 2 m 2 területen, és berendezések II-es típusú - 1 m 2 területet határoz meg, kiegészítő berendezések, amely lehetővé teszi a teljesítmény maximalizálása érdekében

Határozat. Építünk a matematikai modell a probléma. Tegyük fel, hogy a cég megvásárolja x1 meghatározza a berendezések I. típusú és II meghatározza a berendezések. Ezután az x1 és meg kell felelniük a következő egyenlőtlenségek:

Ha a vállalat megszerzi a megadott számú berendezés, a teljes termelés növekedése lesz

A gazdasági tartalmát x1 és hogy csak nem-negatív egész számok, azaz a. E.

Így érkezünk a következő matematikai probléma: találni egy maximális érték a lineáris függvény (71), ha teljesülnek a feltétel (70), (72) és (73). Mivel az ismeretlen vehet csak egész értéket, akkor a probléma (70) - (73) egy probléma egész programozás. Mivel az ismeretlenek száma a probléma két, a probléma megtalálható segítségével geometriai értelmezést. Ehhez elsősorban konstrukció egy sokszög az oldatok álló meghatározásakor a maximális értéket a lineáris függvény (71) körülmények között (70) és (72) (11.). A koordinátáit az összes pontot a sokszög OAEVS megoldások megfelelnek a rendszer lineáris egyenlőtlenségek (70), és a feltétel nem-negativitás változók (72). Azonban, állapot (73), t. E. teljességére állapot változókat koordináták megfelelnek csupán 12 jelű pontokban ábrán. 11. Ahhoz, hogy megtalálja a pontot, amelynek koordinátái határozzák meg a megoldást az eredeti problémát, cserélje ki a sokszög sokszög OABC OKEMNF. amely tartalmazza az összes érvényes pont koordinátája egész szám, és oly módon, hogy a koordinátákat minden csúcsa egész számok. Tehát, ha úgy találja, a legmagasabb pont funkció (71) a sokszög OKEMNF. koordinátáit ebben a kérdésben, és meghatározza az optimális programot a probléma.

Ahhoz, hogy ezt megtehessük, vektort, és egy átmenő a sokszög OKEMNF döntések (száma 12 önkényes). Építése Direct irányban mozog a vektor mindaddig, amíg ez nem megy át az utolsó közös pontja annak poligon adatokat. Az koordinátáit ebben a kérdésben, és meghatározza a legjobb terv, valamint az objektív függvény értékét úgy maximalizálható.

Ebben az esetben, a kívánt pont E (1, 3), amelyben a célfüggvény feltételezi a maximális érték C. következetes volt, a koordinátái az E pontban meghatározzuk az optimális probléma (70) - (73). Ennek megfelelően a tervet, a cég meg kell vásárolni egy sor berendezések 1-es és II-es típusú három berendezés. Ez biztosítja a vállalat a jelenlegi korlátozások termelési létesítmények és alapok maximális termelés növekedése 14 egység. műszakonként.

A munka lehet használni, hogy azt állítják mechanizmusokat. Performance i-edik mechanizmust, amikor a j- edik munka. Feltételezve, hogy mindegyik módszer csak akkor használható egy feladat, és minden munkahelyet lehet végezni egyetlen mechanizmus, a biztosító mechanizmusok határozzák meg, amely biztosítja a legjobb teljesítményt. Szerkesszünk egy matematikai modellt a probléma.

Határozat. Bemutatjuk a xij változót. amelynek értéke 1, ha használják J- th mechanizmust, amikor az i- edik művelet, és 0 egyébként. Ezután a felhasználási feltételek egyes mechanizmus csak egy feladat lehet kifejezni egyenletek

és a feltételeket, a feladat egyetlen mechanizmus - az egyenletek

Így, a probléma az, hogy meghatározza az értékeket az ismeretlenek, hogy kielégítik az egyenletrendszert (74) és (75), és a feltétel (76), amelynél a maximális értéke a függvény

A formulázott probléma probléma egész programozás.

Meghatározása az optimális terv egész programozási feladat. Tekintsük a egész programozási feladat, amelyben mind a célfüggvény, és a funkció a rendszerben a korlátok lineáris. Ebben a tekintetben, megfogalmazzuk az alapvető probléma a lineáris programozás, amelyben a változók, hogy csak egész értékeket. Általánosságban elmondható, hogy ez a probléma felírható a következőképpen: megtalálni a legnagyobb a függvény

Ha talál egy megoldást a problémára (78) - (81) szimplex módszer, ez lehet akár egy egész vagy sem (egy példa a lineáris programozási feladat, amelynek megoldása mindig egy egész, egy közlekedési problémát.). Az általános esetben, az optimális programja probléma (78) - (81) bekezdése előírja, speciális technikákat. Jelenleg több ilyen módszereket, amelyek közül a legismertebb a módszer Gomory. alapján a szimplex fent leírt módszer.

Gomory módszer. Megoldást találni egészértékű programozási problémát Gomory kezdődik meghatározása szimplex módszer az optimális program a probléma (78) - (80) nélkül integer. Ha ez a terv is található, böngészi összetevői. Ha van, elemei között tört számok talált a terv a legjobb terv egészértékű programozási feladat (78) - (81). Ha az optimális terv a probléma (78) - (80) változó egy frakcionális érték, akkor az egyenletrendszert (79) adunk az egyenlőtlenség

és megoldást találni a problémára (78) - (80) (82).

A (82), és - a transzformált referencia értékeket és az értékeket, amelyeket úgy vettek az utolsó simplex asztal, egy és - frakciói egészek (frakcionált része számos jól ismert legkisebb nemnegatív b oly módon, hogy a különbség a és b egész szám). Ha az optimális terv problémás (78) - (80) tört értékeket vesz több változó további egyenlőtlenség (82) határozza meg a legnagyobb frakció.

Ha az eredmények tekintetében a (78) - (80), (82) a változók tört értékeket, majd ismét hozzáadunk egy további restrikciós és számítási eljárást megismételjük. Keresztül véges számú iteráció, vagy a legjobb tervet integer programozási feladat (78) - (81), illetve, hogy megoldhatatlan.

Ha a kereslet egész (81) csak bizonyos változók, például a feladatokat az úgynevezett vegyes egész. Ők is konzisztens megoldást erre a problémákat, amelyek mindegyike nyert az előző bevezetésével további korlátozásokat. Ebben az esetben az ilyen korlátozás az űrlap

amelyek meghatározása a következő feltételeket:

1), hogy el tudja fogadni nem egész szám,

2), amely feltételezi, hogy csak egész számok,

Ebből következik a fentiekből, hogy a folyamat során meghatározzuk az optimális terv egész programozási feladat Gomori eljárás magában foglalja a következő lépéseket.

1. A szimplex módszer, megtalálni a megoldást a problémára (78) - (80) anélkül, hogy figyelembe véve a követelményeket az egész változó.

2. Töltsük fel további megszorítás a változó az optimális terv a probléma (78) - (80) van egy maximális frakcionális érték, és az optimális terv a probléma (78) - (81) egész számnak kell lennie.

3. A duál szimplex módszer. megoldást találni a problémára, amely nyert probléma (78) - (80) eredményeként további korlátozások csatlakozás.

4. Ha szükséges, alkotnak egy további korlátozást, és továbbra is az iteratív folyamat, amíg az optimális probléma (78) - (81), illetve hogy megállapítsa oldhatatlan.

Gomory módszert találni a maximális értéket a függvény

Adj egy geometriai értelmezése a megoldás.

Határozat. Meghatározni az optimális programot a probléma (86) - (89) először megtalálni az optimális programot a probléma (86) - (88) (22. táblázat).

Most azt látjuk, a maximális értéke (86) körülmények között (87), (88) és (90) (Table. 23).

táblázatból látható 23, hogy a kezdeti probléma egész programozás az optimális terv w-dik a tekintetben, a célfüggvény érték egyenlő. Adjunk egy geometriai értelmezése a megoldás. A körét megengedett megoldások a probléma (86) - (88) van OABCD sokszög (12.). Ábra. 12 azt mutatja, hogy a maximális érték a célfüggvény feltételezi a C pont (19/2; 7/2), t e .. X = (19/2, 7/2, 0, 0, 34) van az optimális terv. Ez azonnal kitűnik a táblázat 22. Mivel X = (19/2, 7/2, 0, 0, 34) nem optimális programja (86) - (89) (és a szám - frakcionált), a további korlátot bevezetjük . Kivéve belőle, és ebben az esetben a megfelelő értékeket ezen egyenletek rendszer korlátai (87), megkapjuk a elzáró háromszög sokszög OABCD EFC.

Amint az ábrából látható. 12, a terület a megvalósítható megoldásokat kapott probléma OABEFD sokszög. E pontban (9; 4) a sokszög a célfüggvény a probléma veszi a maximális érték. Mivel a pontok koordinátáinak E - egészek és az ismeretlen, és kap egy egész értéket behelyettesítve egyenlet (87) értékek és az optimális terv a probléma (86) - (89). Ebből következik, az asztal 23.

Gomory módszer megoldást találni, hogy a probléma az volt, hogy meghatározzák a maximális érték a függvény

Adj egy geometriai értelmezése a megoldás.

Határozat. Fogalmazza meg a problémát újraírni az alábbiak szerint: megtalálni a legnagyobb értéke a függvény

A probléma (95) - (98) szerves részét képezi, mivel a változók és tudja fogadni értéke nem egész szám.

Find szimplex módszer zadayai oldatot (95) - (97) (24. táblázat).