Megoldás a lineáris programozás szimplex módszer
A megoldás a lineáris probléma
programozás szimplex módszer
Ladover Tatiana
Novorossiysk College of Building és Gazdaságtudományi
A megkülönböztető jegye ZLP alkotó részét matematikai programozási feladat az, hogy a cél a probléma meg van írva, mint egy lineáris függvény f (X) és a lineáris megkötöttség.
A fő feladat a lineáris programozás yavlyaetsyanahozhdenie
ilyen változók X = (x1. x2. x3. ..., xn) vezető megcélzott
f (x), hogy az extremális értéket.
Általános nézet a felvétel ZLP modell:
xi ≥ 0, i = 1 ÷ n - a kívánt értéket,
aij. bj. ci - előre meghatározott állandó érték,
bj - a nyersanyag, energia, stb j = 1 ÷ m.
A számok halmaza X = (x1. X2. X3. Xn) kielégíti a korlátok
A probléma az úgynevezett lehetséges megoldást, vagy egy terv vagy egy érvényes domain
oldatok (SDT).
Egy lehetséges megoldás, amely maximalizálja vagy minimalizálja az objektív függvény nevezzük optimális megoldás, és az optimális terv.
ZLP dönt a konkrét esetben, amikor két változó lehet grafikus módszer.
Ha ZLP több mint két változó, a leggyakoribb módszer a megoldás a szimplex módszer.
Simplex kifejeződése formájában
c1 x1 + x2 c2 + ... + xn cn
összege, vagy páronként termékek vektorok
Megoldási módja problémák f (x) → perc eltér a módszerek problémamegoldás c f (x) → max. A kényelem problémák megoldása mindkét típus azonos algoritmus a modellt kell hozni az úgynevezett kanonikus formában (CF).
Úgy véljük, hogy ZLP írt kanonikus formában, ha:
a) az objektív függvény maximalizálását;
b) a probléma korlátok formájában való egyenlőség nemnegatívak része a jobb (BJ ≥ 0);
c) az összes változó a modellben a probléma nem negatív (≥ 0).
Így a kanonikus forma ZLP modell formájában:
Tekintsük kétféle matematikai modellek ZLP.
I.
Adunk az EK ZLP meghatározott modellt, amelyben mindenféle korlátozás ≤:
Minden egyenlőtlenségek megszorítások a rendszer bal oldalán kisebb, vagy egyenlő, mint a jobb oldali (≤). Annak érdekében, hogy kiegyenlítsék őket (amint azt a kanonikus forma), szükséges, hogy korlátozza a bal oldalán add. illetve nem negatív egész változók xn + 1, x n + 2, ..., xn + m. Ha nem változik az értéke a célfüggvény, ezeket a változókat vezetünk bele nulla együtthatók.
így hozatalát követően a kanonikus
A feladat a következő lesz:
Amennyiben a korlátozás az eredeti matematikai modellje a probléma adott szigorúan egyenlőségjel (=), akkor nem vezet be további változó, de csak mesterséges (lásd alább).
Hagyja, hogy a gazdasági probléma leírása a következő modell
Adunk a matematikai modellt CF:
II.
Tekintsük a második különleges esetben: f (x) → perc, és legalább egy, a megszorítások a formában ≥ (vagy akár az összes). Modellje ez a probléma a következő formában:
Meghatározása a minimális érték a f (x) lehet csökkenteni, hogy megtalálják a maximális érték a függvény -f (x).
így Ilyen esetekben, az együtthatók a ismeretlenek f (x) → min kell szorozni (-1).
Hogy a szigorú egyenlőség megszorítások formájában ≥ szükséges a bal oldalon minden korlátozás ebben a formában levonására. Ennek megfelelően, a nem negatív egész szám változók xn + 1, x n + 2, .... xn + m.
Ezután a csökkenés után a CF feladat (**) a következő lesz:
Minden változó a matematikai modell két csoportba sorolhatjuk:
- bázis (függő), amely kifejezhető az összes többi
változókat. Változó az alap, ha jön
csak az egyik egyenletek a rendszerben egy tényezője 1 (mint a (*) alapvető változók x3. x4. x5).
- a többi változó nem-bázikus (független).
Egy adott megoldás, vagyis megtalálása alapvető változók nem-bázikus változók egyenlővé nullára (xi = 0), az úgynevezett bázis. Basic oldatot nevezzük degenerált, ha legalább az egyik alapvető változók = 0, egy ilyen probléma az úgynevezett degenerált. Ellenkező esetben - a probléma az úgynevezett nem-degenerált.
Fent már néztem két adott esetben az I. és II.
Abban az esetben, I bázis oldatot a lehetséges megoldást:
és nem érvényes, mert a ellentmond a nem-negativitás változók (xi ≥ 0).
Ezekben az esetekben a felosztás alapváltozó és találjanak megvalósítható megoldást módszerrel mesterséges alapján a következők:
1) minden egyes kényszer típusát = ≥ beadott vagy egy mesterséges nemnegatív változó y1. v2, ... um;
2) a mesterséges változókat tartalmaz egy faktort (-M) egy célzott funkciót, ahol M - nagyon nagy pozitív szám (innen a név - M módszer).
Miután belépett a CF feladat mesterséges változók (**) a következő lesz:
Egy sor mesterséges változók y1. y2, ..., um az eljárás M-mesterséges formák alapján. Mesterséges változók bevezetése csak megszerezni a kezdeti alap terv megoldása szimplex módszerrel LP problémákat. A döntés ZLP kényelmesen elvégezhetjük az úgynevezett simplex táblázata a következő formában:
Az érték a célfüggvény f (x) a következőképpen számítjuk összegeként termékek a párosított elemek és elemei oszlop C. oszlop B. A relatív értékelést - összegeként termékek elemeinek pár C és az oszlop elemei megfelelő i-edik oszlop.
Algoritmust megoldására ZLP szimplex módszer
1. Hozd matematikai
modellt egy kanonikus formában. Töltse ki a szimplex tábla és minták értékeinek
a célfüggvény és a relatív értékelés.
2. - Ha minden relatív
értékelése nem negatív, és nem mesterséges között az alapvető változók, a terv
optimális, azaz a probléma megoldódott. A megoldás a B oszlop:
- Ha az összes nem-negatív relatív értékelések és a köztük egyenlő nullával, és nincs ember által, akkor a probléma megoldható, és van egy végtelen számú megoldást, melyek közül az egyik jött a bázis (található B oszlop) között az alapvető változók;
- Ha minden nem negatív relatív értékelés, hanem az alapvető változók vannak mesterséges, a probléma nincs megoldás;
- ha a környezet viszonylag
becslések vannak negatív, akkor a megoldás nem optimális feladat felé
következő alapvonal terv (lépéshez 3).
3. Az összes negatív relatív értékelések kiválasztott legmagasabb modulus. A megfelelő oszlopot nevezik a fő. meg kell osztani a elemenként egy oszlopban a fő oszlop meghatározza az glavnoystroki
(Nulla és negatív számokat nem osztja a fő oszlop). A legkisebb hányadosa
Ez megfelel a fő vonal. A kereszteződésekben a fő vonal, és a fő oszlop
Simplex a fő eleme az asztalra. Ez a szám csak akkor lehet
pozitív.
Ezután meg kell tenni újraszámítása az asztalra.
4. Az új táblázat a változók és a fő vonalakat a fő oszlopot (együtt együtthatók) felcseréljük. Más változók és együtthatók átírni módosítás nélkül.
Ehelyett a fő eleme van rögzítve inverz szám 1 / fő eleme.
Elemei a fő oszlop a táblázatban van osztva a régi (- a fő elem).
Elemei a régi fő vonal a tábla van osztva (fő elem).
Minden egyéb elem átszámítva a szabály a téglalap:
A termékek az elemek a fő diagonális, amely áthalad a fő elem, kivonva a termék a másodlagos átlós elemek, és az eredményt elosztjuk a fő elem; A kapott számot fel kell jegyezni a megfelelő mezőbe az új szimplex tábla. Ha a fő vonal, vagy a fő oszlop nulla, akkor
elemek, amelyek megfelelnek a nullák oszlop és sor nélkül felülírásra
változások az új tábla.
5. Az új tábla számított célfüggvényértékek és a relatív
értékeléseket. Lépés a 2. pont.
2. példa.
Nézzük megoldani a következő problémát szimplex módszer.
Mester teszi cupronickel kanál két típusa van: nem dombornyomás (L1) az ára 2 euró és a bélyegzés (A2) az ára 3 euró. A nap varázslóval legalább egy kanállal. Day nyersanyagellátás nem több, mint 12 dm 3. így képeznek egy kanál L1 megy 3 dm 3 és kanál típusú A2 - 2 dm 3 nikkel ezüst.
Melyik a legnagyobb bevétel egy nap számíthat a mester, amelyekre ezek a szabványok?
jelölésére:
x1 - száma kanál A1 típusú,
x2 - száma kanál A2.
Mi elkészíti matematikai modellt a probléma nyilatkozata:
értékesítéséből származó jövedelem a kanalakat A1 típusú 2 * x1 (euró);
értékesítéséből származó jövedelem a kanalakat A2 3 * x1 (euró). Az összeg ezen számok egyenlő a bevétel a mester - a célfüggvény.
A termelés kanalakat A1 típusú töltött 3 * x1 m dm 3 nikkel-ezüst, és a termelés a kanalakat A2 típusú töltött 2 * x1 dm 3 m és a varázsló nem használható a nap több mint 12 dm 3 M - ez az első restrikciós. A feltétel, hogy a mester a nap készítés legalább egy kanállal, írjuk be a második etapban, és hogy a modell a probléma:
A probléma megoldása érdekében a szimplex módszer bemutatunk egy matematikai modellt a kanonikus formában:
Alapján a kanonikus alakja a kezdeti épít az alap terv célkitűzései:
A probléma nem oldódott meg, mert A bázis vannak mesterséges változók, beleértve a relatív értékelés - negatív. Között negatív relatív otsenokmso-Fareast-font-family: Calibri; mso-ansi-language: RU; mso-Fareast-language: EN-US;
Válaszd a legnagyobb modulus (-M 3) - ez megfelel a fő oszlop; találni alapsorban (második, t.k.1 / 1 negatív relatív score önmagában (-3), ez megfelel a fő oszlopra; fővonal - első, illetve a fő elem megegyezik két (sejt kékkel kiemelve) kitöltésével újraszámítást táblázatok lépni. új alap terv.
Minden nem-negatív relatív értékbecslésre alapján mesterséges változók, így a probléma megoldódott.
megoldás:
X1 = 0 (mivel ez a változó nincs balra egy alapon) a bázis ki X2 = 6, a maximális jövedelem ilyen cikkek gyártási kifejezések
f (x) = 2 * 3 * 0 + 6 = 18 (euró).
2 almasav GS Gazdálkodási és matematikai módszerek a tervezés / - Moszkva Gimnázium, 1988.-
279.