Útmutató megoldására lineáris programozási feladatok - studopediya
Lineáris programozási feladat volt az első részletes tanulmányt a feladat megtalálni a szélsőérték funkciók jelenlétében egyenlőtlenségek korlátok. Távú jelenlétét a neve „programozás”, mert az első tanulmány, és az első alkalmazás a lineáris optimalizálási problémák már a gazdaság területén. Az angol szó «programozás»: a tervezés, előkészítés a tervek és programok. Persze, az terminológia tükrözi szoros kapcsolat áll fenn, hogy a matematikai megfogalmazása a problémát és a gazdasági értelmezése (a tanulmány optimális gazdasági program). A „lineáris programozás” javasolta George. Danzig 1949 tanulmányozása elméleti és algoritmikus kapcsolatos problémák optimalizálása lineáris függvények lineáris korlátok.
Az átfogó cél a lineáris programozás (ZLP) utalva a probléma
és a nem-negativitás feltétel-rész
Itt is - adott valós számok, a funkció az úgynevezett cél. vektor - feladat tervet. Egy tervet, amely kielégíti a rendszer korlátai (1.2), elfogadható. Elfogadható terv, amelyben az objektív függvény eléri a maximális vagy minimális értéket nevezzük optimális. Az alábbi esetekben:
1. Optimális csak terv;
2. Optimális tervek végtelen;
3. A célfüggvény korlátos a készlet megvalósítható terveket;
4. Field elfogadható megoldásokat, amelyek egy ponton, ahol a célfüggvény eléri egyidejűleg a maximális és minimális értékeket.
1. példa Tekintsük a következő ZLP
Mi megoldjuk ezt a problémát grafikusan. Ahhoz, hogy ezt megtehessük, építeni egy sík derékszögű koordinátarendszerben. Mind a egyenlőtlenségek (1.3) határozza meg a néhány félig síkban. A kereszteződésekben a tetszőleges számú fél-síkok egy konvex halmaz.
Emlékezzünk vissza, hogy a konvex nevezzük meg, bármely két pont, amely csatlakoztatható egy szakaszt, amelynek minden pontja tartozik a készlet. Egy példa a konvex halmaz egy háromszög.
Készítünk egy kétpontos egyes határvonalak
Ezek ábrán látható. 1.
Most bármely ponton (pl azon a ponton, O (0,0)) határozza meg, hogyan egyenlőtlenség jele végzünk, és válassza ki a kívánt félsíkra. A metszéspontja a kiválasztott fél-sík lesz egy háromszög, amely több pontból a háromszög megvalósítható sor megoldást ZLP (1.3). Az 1. ábra a háromszöget festett sötét színű.
Most megépíteni a sorban a célfüggvény szinten
A származási vektort-gradiens,
amelynek az összetevői a együtthatók a célfüggvény. Ez a vektor irányát jelzi a legmeredekebb növekedés funkciót. Az egyszerűség kedvéért az ábrán vektort mutatja.
Mi mozog a szint vonal irányába a gradiens a keresztezi a politóp a megvalósítható megoldásokat. Első metszéspont M egy pont a minimum. A koordináták E pont M (2,1) határozzuk meg a rendszer
Így az optimális terv ZLP (1.3) van. Vége a probléma.
Szimmetrikus forma ZLP felvétel van a probléma
A gazdasági problémák az elmélet (1.4) és (1.5) a leggyakoribb.
Végül a kanonikus formoyzapisi ZLP nevezett feladat
Rendszer korlátok probléma (1,6) jelentése lineáris algebrai rendszer. A mátrix formában felírható
ZLP hogy van egy megoldás, amely korlátozza a rendszer legyen együttműködő. Ez akkor lehetséges, ha a rang egybeesik a rangot a kibővített mátrix. jelent
ZLP változók megfelelő alap vektorok nevezzük alap és a kijelölt BP. A többi változó szabad és jelöli ki a közös vállalat. Ha a szabad változók nullával egyenlő, és ahol a bázikus változók lesznek a nem-negatív értékeket, a kapott részleges oldatát (1,7) nevezzük a referencia oldat (fel).
Azt mondjuk, hogy a kényszer-rendszer (1.7) van ZLP előnyös forma. ha nonnegativeness jobb oldalán a bal oldalon a korlát egy változtatható előforduló együtthatóval egyenlő az egység és a többi egyenlőség korlátokat - tényező nulla. Például, a rendszer a megszorítások
az első és a második korlátozások az előnyös fajokat, és a harmadik - nem.
. G. Zh.Fure 1820, majd 1947-ben J. Danzig javasolt eljárás irányított felsorolás a szomszédos csúcsok irányába növeli a célfüggvény - szimplex módszer. lett jelentős megoldásában lineáris programozási feladatok. Szovjet akadémikus, Nobel-díjas (1975) LV Kantorowicz, megfogalmazott egy sor lineáris programozási problémák és azt javasolta, (1939) módszere megoldásuk (a megoldási módja szorzók), kissé eltér a szimplex módszer.
A megoldási módja ZLP úgynevezett simplex. Ez csak azt a kanonikus alakban felvételt. Átalakítás szimmetrikus forma ZLP felvétel a gyűjtő. Tegyük fel, hogy az eredeti probléma formában van (1.4). Bemutatjuk m további változókat Alakításával típusú egyenlőtlenség egyenlőség, ehhez hozzátesszük, hogy a bal oldali részén a további változók. A célfüggvény ezeket a változókat írja nulla együtthatók. A rendszer korlátokat (1.4) formáját ölti
Itt - alapváltozó - ingyen. Következésképpen az eredeti támogatási program fog kinézni.
Most úgy vélik a probléma (1,5). M is bevezethetnek további változók, hanem egyenlőtlenségek típusú átalakítani a saját tőke, vonja ki azt a bal oldalán a további változók. (A célfüggvény ezeket a változókat írja nulla együtthatók.)
Most azonban, a rendszernek nincs korlátozás előnyös forma, mivel a további változók a bal oldalon (a) az együtthatók -1, annál. Ezért alapvető tervet
Ez elfogadhatatlan. Ebben az esetben azt be egy mesterséges alapon. A célfüggvény változók kerülnek bevezetésre együtthatóval. ahol - a nagy pozitív szám.
A kapott probléma az úgynevezett M-feladat. a megfelelő referencia. Mindig van egy előnyös kilátás. Kezdeti támogatás program
Hagyja az eredeti ZLP néz
Továbbá, sem a korlátok nem előnyösek változó. M -problem írva
ahol a + jel a célfüggvény vonatkozik a probléma, hogy a minimum. Kezdeti támogatási program ebben az esetben
Ha néhány korlátját a rendszer előnyös formája, nem adható mesterséges változókat ott.
2. példa Tekintsük az alábbi ZLP
Itt az a probléma, hogy kanonikus megadásával további változókat
A második egyenlet nem tartalmazza az alapvető változó, ezért az ehhez az egyenletben a mesterséges alapon. Az eredmény egy M-probléma
Tegyük fel most, hogy az előnyös forma ZLP
Probléma (1.9) van írva a táblázatban, amely az úgynevezett simplex
Itt az első sorban az együtthatók a célfüggvény, amikor a vonatkozó változókat. Az első oszlopban a célfüggvény együtthatók az alapvető változókat.
Most, hogy az alapvető tételek a szimplex módszer.
1. Tétel Tegyük fel, hogy a kezdeti probléma megoldódott a legnagyobb. Ha valamilyen támogatási program minden becslések nem negatív, akkor a terv optimális.
2. tétel Tegyük fel, hogy a kezdeti probléma megoldódott legalább néhány támogatási tervet valamennyi nem pozitív értékelés, hogy egy ilyen terv optimális.
3. tétel Ha az index sorban az utolsó szimplex tábla tartalmazza az optimális terv, van legalább egy nulla értéket, amely megfelel a szabad változó, a ZLP végtelen sor optimális terveket.
4. Tétel Ha az index sorban simplex ZLP táblázat tartalmazza a maximális negatív pontszámot. és a megfelelő oszlopban nem változó nincs pozitív elem, az objektív függvény a forgatáson nem korlátos felett elfogadható terveket.
5. Tétel Ha az index sorban simplex asztal ZLP legalább egy pozitív értékelést. és a megfelelő oszlopban nem változó nincs pozitív elem az objektív függvény a sor elfogadható tervek nem alulról korlátos.
Tétel 6. Ha az optimális terv M-probléma legalább az egyik mesterséges változók nullától eltérő, akkor az eredeti probléma nem rendelkezik érvényes tervek, azaz A rendszer összeegyeztethetetlen korlátozásokat.