Bevezetés, elméleti alapjait, a szimplex - módszer, mesterséges alapján - a probléma lineáris
A legtöbb feladatok néhány sajátossága. Az első az, hogy a döntések információk alapján. Néha az ilyen jellegű probléma lehet megfogalmazni (általában néhány egyszerűsítést) oly módon, hogy oldották meg a segítségével matematikai módszer, amely a nevét a lineáris programozás.
Ez a munka rávilágít az egyik módja, hogy megoldja lineáris programozási feladatok (ZLP), azaz a lineáris programozás valós számok szimplex módszer (konkrétan - a módszer a mesterséges alapon).
Simplex - módszer
Sok kezelése, szűkülnek le, hogyan osztja korlátozott erőforrásokkal legelőnyösebb. A nyelv a matematikai modellek, ez azt jelenti, hogy azt akarjuk, hogy maximalizálják (maximalizálása) valami (pl profit) vagy minimalizálása (minimalizálni) valami (például költség). Általában ez a funkciója valami (ami ismert, mint a célfüggvény) számos tényező, az úgynevezett változó. Ezt a folyamatot nevezik optimalizálása.
Gyakran előfordul, hogy ezek a kérdések is formálhatjuk után (általában néhány egyszerűsítést) oly módon, hogy oldották meg a segítségével matematikai módszer, amely a nevét a lineáris programozás.
A közös probléma a lineáris programozás (OZLP) megadott tetszőleges formában, úgynevezett egy feladat, amely megköveteli maximalizálják (minimalizálása) függvény
egy ij X j <= a i0 ( i = 1, …, s) (2)
egy ij x j = a I0 (i = s + 1, ..., m) (3)
X j> = 0 (j = 1, ..., t)
Vannak különböző formái ZLP rekord, de a munka mi érdekli a kanonikus formában ZLP felvétel, mivel széles körben használják a szimplex módszer alkalmazható ez a formája az írás.
Lineáris programozási feladat kanonikus formában felvételi feladatot nevezzük, amely ahhoz szükséges, hogy maximalizálja a funkciót
egy ij x j = a I0 (i = 1, ..., m) (5)
X j> = 0 (j = 1, ..., n) (6)
Megjegyzés: A probléma minimalizálása f lehet hivatalosan helyébe a probléma, hogy maximalizálják a függvényt (-f).
Annak érdekében, hogy kifejezze az alapötlet a szimplex módszer, bemutatunk néhány kapcsolatos alapfogalmakat lineáris programozás:
A számok halmaza X = (x 1; ...; x n), kielégíti a megszorítások a probléma az úgynevezett fel.
A számok halmaza X = (x 1; ...; x n), az úgynevezett referencia tervet, ha megfelel egy extrém pontot a polihedron megoldásokat.
Terv X = (x 1; ...; x n), szállító egy szélsőérték nevezett funkció optimális.
Tehát a lényeg a szimplex - módszer a megrendelt ellenőrzése csak a támogatási programok, amelynek során a célfüggvény értékét növeli. Így fokozatosan jön az optimális terv (ha a probléma megoldható).
Megjegyezzük továbbá, hogy minden megoldható lineáris programozási feladat lehet csökkenteni a kanonikus formában. A csökkentés az egyenlőtlenség az egyenlőség érhetők el a további nem-negatív változók a célfüggvény nulla együtthatók. Szellemek egyenlőtlenségrendszer megszorítások kanonikus alakja, akkor jelölje ki a rendszer korlátaira egység alapon.
Korlátozások az űrlap „# 63” - forrás. A jobb oldalon az, hogy mire használjuk a termelés a bal -, mi lesz belőle. Ilyen korlátok bevezetni további változók együtthatóval „1”, amely egy egység alapon. A célfüggvény ilyen változó tartalmazza a „0” tényező. Ezek a változók meghatározása gazdasági értelemben. Általában ők képviselik alatti kiadások források (a többi).
„=” Típusú korlátozást. Gyakran előfordul, hogy annak ellenére, hogy a megszorítások formájában részvény, egy egységet alapon nem látszanak, vagy nehezen látszanak. Ebben az esetben a mesterséges változókat be létrehozására egység alapon. A rendszer korlátai belépnek egy „1” együttható és az objektív függvény a «M» együttható, hajlamos a végtelenig (a Fmin - «+ M», amikor Fmax - «-M»). (Módszer mesterséges alapon).
Korlátozások az űrlap „# 63” - Tervezett korlátozásokat. További változók (X), melyen néhány gazdasági értelemben - túllépését a források vagy a feletti teljesítése a terv, túltermelés, hozzáadunk egy tényező „-1”, az objektív függvény - egy tényező „0”. És mesterséges változókat, mint az előző esetben.
ZLP legésszerűbb döntés lehet táblázatos formában. Ezek az úgynevezett simplex. A különböző irodalmi építése simplex táblázatok, amelyek kissé eltérnek egymástól. A leginkább elfogadható véleményem szerint a táblák táblázatban ismertetett. 1.
A módszer a mesterséges bázisok
Amint azt már említettük, gyakran problémát kiosztási egység alapon. Ebben az esetben előnyös egy olyan módszer, mesterséges alapon. Együtt az eredeti feladat, a feladat akkor tekinthető kiterjesztett alapján összeállított eredeti bevezetésével mesterséges nemnegatív változók és célfüggvény levonjuk az összeget a mesterséges változók szorozni egy tetszőlegesen nagy pozitív szám M. Az eredmény egy úgynevezett M-feladat.
F = CJ xj - x n + i (7)
egy ij + x n + i = a I0 (i = 1, ..., m) (8)
X j> = 0 (j = 1, ..., n + m) (9)
A rendszer (8) változók x n + i (i = 1, ..., m) alapját képezik az úgynevezett mesterséges. Amikor x 1 = ... = X n = 0 (8) kap az eredeti referencia terv M-feladatok: (0, ..., 0; 10, ..., egy M0).
Beszerzése optimális tervet az eredeti probléma bevonásával az M-probléma ez alapján az alábbi állításokat:
1. Ha az M-optimális tervet feladat összes mesterséges változókat nullával egyenlő (x1; ...; x n; 0, ..., 0), a terv (x 1, ..., xn) optimális a eredeti probléma.
2. Ha az optimális tervet M-feladat, legalább az egyik mesterséges változók pozitív bármilyen nagy M, az eredeti probléma nem egyetlen terv.
3. Ha az M-probléma megoldhatatlan, akkor az eredeti probléma megoldhatatlan.
A döntés ZLP módszer a mesterséges bázisok mesterséges változókat kell beadni csak azokban egyenletek, amelyek nem engedélyezettek a „természetes” alapon változó.
Amint az a (7) Most a célfüggvény tartalmaz két kifejezés
Ezért simplex táblázatok rendelni két sort f (1.3 táblázat.), és a optimalitás ellenőrizzük először a második sor összegének megfelelő
Csak miután minden eleme ez a sor nullával egyenlő, optimalitása ellenőrizzük a jele az első sor összegének megfelelő
Kivéve az alap a mesterséges változókat az ezeknek megfelelő csökkentjük oszlopok (nem számla) a mesterséges változókat vissza alapján nem vezettek be.