A lineáris programozási modell matematikai leírása. Lineáris matematikai modellek formái és transzformációjuk A lineáris programozási modell általános képe

1.

2. használati útmutató mat. modellek a gazdaságban.

A matematikai modellek lehetővé teszik a gazdasági rendszerek ismeretlen paramétereinek optimális értékeinek meghatározását, ami fontos a döntéshozatali folyamatban. A matematikai programozás csak egy olyan berendezést biztosít, amely lehetővé teszi a kiválasztási folyamat optimalizálását a legjobb lehetőségeket tervek a gazdálkodási folyamatban a gazdasági rendszerekben.

Használt matematikai statisztikában, optimalizálási módszerekben, közgazdasági módszerekben. kibernetika, kísérleti problémák.

A gazdaság összetett folyamatainak és jelenségeinek tanulmányozásakor gyakran alkalmaznak modellezést - a vizsgált objektum figyelembe vett jellemzőinek jól meghatározott konkrét megjelenítését. Lényege abban rejlik, hogy a vizsgált jelenséget kísérleti körülmények között, eltérő időbeli és térbeli léptékű modell segítségével reprodukálják. A modell egy speciálisan létrehozott objektum, amelynek segítségével a vizsgált rendszer bizonyos jellemzőit reprodukálják annak tanulmányozása érdekében. A matematikai modellezés a legtökéletesebb és egyben leghatékonyabb módszer a vizsgált objektumról való információszerzésre. Ez egy hatékony eszköz a közgazdaságtan elemzéséhez. A modellek felhasználásával végzett kutatások eredményei akkor lesznek gyakorlati érdeklődésre számot tartóak, ha a felépített modell kellően adekvát a vizsgált jelenségnek, azaz. elég jól tükrözni a valós helyzetet.

2. a matematikai programozás mint tudomány, felépítése. Optimalizálási problémák. A klasszikus optimalizálási módszerek alkalmazásának nehézségei a gazdasági problémák megoldásában.

Matematikai programozás az alkalmazott matematikának egy olyan ága, amely fejleszti elméleti alapjaés az extrém problémák megoldásának módszerei.

A matematikai programozás számos részből áll, amelyek közül a legfontosabbak a következők:

1. Lineáris programozás. Ez a rész olyan problémákat tartalmaz, amelyekben az ismeretlen változók első fokon szerepelnek a matematikai kapcsolatokban.

2. Nemlineáris programozás. Ez a szakasz olyan problémákat tartalmaz, amelyekben a célfüggvény és (vagy) megszorítások nemlineárisak lehetnek.

3. Dinamikus programozás. Ez a rész olyan feladatokat tartalmaz, amelyekben a megoldási folyamat külön szakaszokra osztható.

4. Egész számok programozása. Ez a szakasz olyan feladatokat tartalmaz, amelyekben az ismeretlen változók csak egész számokat vehetnek fel.

5. Sztochasztikus programozás. Ez a rész olyan feladatokat tartalmaz, amelyek tartalmazzák Véletlen változók a célfüggvényben vagy megszorításokban.

6. Paraméteres programozás. Ez a rész olyan problémákat tartalmaz, amelyekben a célfüggvényben vagy a megszorításokban lévő ismeretlen változók együtthatói bizonyos paraméterektől függenek.

A matematikai programozási feladatok megoldásához nehéz a klasszikus módszereket használni szélsőségek megtalálására, mivel a matematikai programozási feladatokban a célfüggvény az ismeretlen változók elfogadható értékeinek tartományának határán éri el szélsőértékét, és deriváltak nem léteznek. a határpontokon. Az elfogadható pontok teljes felsorolása a jelentős számuk miatt lehetetlen.

3. A matematikai modell fogalma, a szőnyeg típusai. modellek

Matematikai modell egy valós jelenség vagy folyamat matematikai szimbólumokkal és kifejezésekkel írt absztrakciója. A gazdasági folyamatok és jelenségek matematikai modelljeit közgazdasági és matematikai modelleknek nevezzük

A modellek a következőkre oszlanak:

1. lineáris, amelyben minden függőséget lineáris összefüggések írnak le,

2. nem lineáris, amelyben nemlineáris relációk vannak;

3. sztochasztikus amelyek figyelembe veszik a vizsgált folyamatok véletlenszerűségét,

4. meghatározó, amelyek figyelembe veszik az összes paraméter átlagos értékét.

5. dinamikus olyan modellek, amelyekben a vizsgált rendszerek fejlesztése több időszakon keresztül történik,

6. statikus, amelyben az időtényezőt nem veszik figyelembe.

7. optimalizálás modellek, amelyekben a választás attól függően történik szélsőségesség néhány kritérium,

8. nem optimalizálás, amelyben nincs optimalitási kritérium.

9. makromodellek(az egész háztartásra)

10. mikromodellek(a gazdaság egyéni kapcsolatai vagy folyamatai).

A matematikai modellek típusai: lineáris, nemlineáris, másodfokú, egész, diszkrét, parametrikus, lineáris tört, dinamikus, sztochasztikus

4. A matematikai programozás feladatainak általános megfogalmazása.

Tekintsük a matematikai programozás problémájának általános megállapítását.

A matematikai programozás általános problémája a célfüggvény optimális értékének meghatározása, és a változók értékeinek a megengedett értékek egy bizonyos tartományába kell tartozniuk. Matematikai definíció optimális megoldás sok változó függvényének szélsőértékének (max vagy min) megtalálásában fejeződik ki

Z = f(x1, x2, …, xn)

e változók adott változási tartományában

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

ahol Ri a ≥, =, ≤ előjelek egyike.

5. A termelési terv optimalizálásának problémája. A problémák matematikai modelljének közgazdasági megfogalmazása és felépítése.

Gazdasági környezet:

A cég gyárt n felhasznált termékek típusai m nyersanyagok fajtái. Egy termelési egység előállításához szigorúan meghatározott mennyiségű alapanyagot használnak fel. Az egyes típusok alapanyagai a vállalkozásban korlátozottak. A vállalat bizonyos nyereséget kap egy termelési egység eladásából. Meg kell találni egy olyan termelési tervet, amelyben a vállalkozás a maximális teljes nyereséget kapja.

Matematikai beállítás:

Legyen j a j = 1, n terméktípus indexe

i - az erőforrástípus indexe i = 1, m

és ij nyersanyagköltségek én-adik típus termelési egység előállítására j-th típusú;

Аi az i-edik típusú erőforrások rendelkezésre álló mennyiségének adott korlátja;

Pj - j-edik típusú termelési egység értékesítéséből származó nyereség;

xj a j-edik típusú kimenet térfogata.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → max

a11x 1 + a12x 2 +…+ a1nx n ≤ A1

a21x 1 + a22x 2 +…+ a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +…+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. A diéta feladata. A probléma közgazdasági megfogalmazása és matematikai modelljének felépítése.

Gazdasági környezet

Egyes gazdaságok állatokat etetnek. Hizlalásra használják n takarmányfajták. A tápanyag (kalcium, foszfor stb.) tartalma minden fajnál takarmányegységenként ismert. Az állatok megfelelő takarmányozása érdekében a tápanyagokat legalább a megadott mennyiségben kell fogyasztani. Az egyes takarmányok egységköltsége ismert. Meg kell határozni az állati takarmányozás étrendjét, amelyben a hizlalás teljes költsége minimális lesz.

Matematikai beállítás:

j az előtolás típusának indexe, j = 1, n

i – tápanyagtípus index, i = 1, m

Аi az i-edik típusú tápanyag szükséges napi bevitele;

Сj a j-edik típusú takarmány egység költsége.

Mutassunk be ismeretlen változókat:

хj - az állatok takarmányozásának napi mennyisége j-edik nézet zord.

A bevezetett jelölés szempontjából adott feladatot legközelebb lesz megírva

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +…+ és mnxn ≥Am

xj ≥ 0, j = 1, n

7. Szállítási feladat . A probléma közgazdasági megfogalmazása és matematikai modelljének felépítése.

Gazdasági környezet :

Elérhető m homogén termékek beszállítói és n ennek a terméknek a fogyasztói. Egy termelési egységnek az egyes szállítóktól minden fogyasztóhoz való eljuttatásának ismert egységköltsége. A beszállítói készletek korlátozottak. Az egyes fogyasztók termékei iránti igények is ismertek.

Meg kell határozni egy ilyen tervet a termékek szállítóktól a fogyasztókhoz történő szállítására, amelyben a szállítás teljes költsége minimális lesz.

Matematikai beállítás :

Mutassuk be az adott paraméterek megnevezését:

j – fogyasztói index, j = 1, n

i – beszállítói index, i = 1, m

Аi az i-edik szállítótól elérhető termékek mennyisége;

Bj - a j-edik fogyasztó termékei iránti kereslet volumene;

A Cij a termék egységnyi költsége az i-edik szállítótól a j-edik fogyasztóig.

Mutassunk be ismeretlen változókat:

хij a termékek i-edik szállítótól a j-edik fogyasztóig történő szállításának mennyisége.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → min

Feladat korlátozások.

I. Minden beszállítótól legfeljebb a rendelkezésre álló mennyiséget veheti fel:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Minden fogyasztó termékigényét ki kell elégíteni

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Nem-negatív feltétel: xij ≥0, i = 1, m ; j = 1, n

Gyakran célszerű a matematikai állítást hajtogatott formában írni:

, i = 1, m , j = 1, n

8. A feladatok vagy megbízások kiválasztásának problémája. A probléma közgazdasági megfogalmazása és matematikai modelljének felépítése.

Gazdasági környezet :

Elérhető n munkafajták és n előadók. Az előadók mindegyike bármilyen, de csak egy munkát végezhet. Az egyes előadók minden egyes munkája elvégzésének költségét meghatározzák. Az előadóművészeket úgy kell munkára kijelölni, hogy a munka teljes költsége minimális legyen.

Matematikai beállítás .

Vezessük be az adott paraméterek jelölését.

i – művek indexe, i = 1, m

j a teljesítők indexe, j = 1, n

A Cij az i-edik feladat j-edik végrehajtó általi elvégzésének költsége.

Vezessünk be ismeretlen változókat. Ebben a feladatban az ismeretlen változók csak két értéket vehetnek fel, 0 vagy 1. Az ilyen változókat null változóknak nevezzük.

1 - ha a j-edik előadó az i-edik munkához van hozzárendelve;

0 - egyébként.

A bevezetett jelölés szempontjából ez a probléma a következőképpen írható fel:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1) (n-1) + Сnnxnn → min

A korlátozások I. csoportja.

Minden műhöz csak egy előadót szabad hozzárendelni:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. korlátozási csoport.

Minden végrehajtó csak egy feladatot hajthat végre:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ij = ( 0,1) i = 1, n ; j = 1, n

9. A vágási anyagok problémája. A probléma közgazdasági megfogalmazása és matematikai modelljének felépítése.

Gazdasági környezet .

A vágáshoz az azonos méretű alapanyagot szállítjuk. Adott mennyiségben adott méretű nyersdarabokra kell felvágni, hogy az összes hulladék minimális legyen.

Matematikai beállítás .

Bemutatjuk a jelölést:

én vagyok az üresek indexe,

Аi - az i-edik típusú üres lapok szükséges száma;

j - vágási lehetőségek indexe,

Cj a hulladék mérete egy egységnyi kiindulási anyag vágásakor a j lehetőség szerint;

és ij az i-edik típusú nyersdarabok száma egy egységnyi kiindulási anyag vágásakor a j lehetőség szerint.

Vezessük be az ismeretlen változók jelölését.

xj a j lehetőség szerint levágott alapanyag mennyisége.

A bevezetett jelölés szempontjából ez a probléma a következőképpen írható fel:

z \u003d С1x1 + С2x2 + ... + Сnxn → min

a11x1 + a12x2 +…+ a1nxn = A1

a21x1 + a22x2 +…+ a2nxn = A2

…………………………….

am1x1 + am2x2 +…+ amnxn =Am

xj ≥ 0, j = 1, n

A matematikai modellek használatával a nyersanyagok akár 20%-át is megtakaríthatja.

A vágás matematikai modellje két szakaszban épül fel.

Az első szakaszban a vágási lehetőségeket összeállítják, aminek eredményeként az n opciók számának értéke, az egyes típusok nyersdarabjainak száma különféle lehetőségeket vágás (aij), valamint a hulladék értéke (Cj).

A nyersanyag egység darabolásának lehetőségeinek felépítése a következő táblázatban történik:

opció számát

Üres i1

i2 üres

üres im

A nyersdarabok méretük nem növekvő sorrendben vannak elrendezve. A változatok felépítése a teljes felsorolás módszerével történik.

10. Az LP problémamodell általános formája és jellemzői

Az LLP általános formája:

z \u003d С1x1 + ... + Сnxn max (perc)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

Általánosságban minden R1 , R2 ,…, Rm szimbólum a következő előjelek egyikét jelenti: ≥, = vagy ≤ .

Az LP problémamodell általános formája a következő jellemzőkkel rendelkezik.

1. A kényszerrendszert egyenletek (merev feltételek) és egyenlőtlenségek (nem merev feltételek) formájában mutatjuk be.

2. Nem negativitási feltételek nem vonatkoznak minden változóra

3. A célfüggvény vagy a maximumra, vagy a minimumra törekszik.

11. Az LP problémamodell standard formája és jellemzői

A szabványos forma a következő.

Keresse meg a z célfüggvény maximumát vagy minimumát:

z = С1x1 + … + Сnxn → max (min) (1)

A következő korlátozások mellett:

a11 X1 + a12 X2 + … + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ am

xj ≥ 0, j = 1, k, k ≤ n

Az LP problémamodell szabványos formájának jellemzői a következők:

1. a korlátozások rendszere egyenlőtlenségek (nem merev feltételek) formájában kerül bemutatásra

2. minden változóra nem-negatív feltételek vonatkoznak

3. a célfüggvény max vagy min

12. Az LP problémamodell kanonikus formája és jellemzői

A kanonikus forma a következő:

Határozzuk meg a z célfüggvény minimumát:

z = С1x1 + … + Сnxn → min

A következő korlátozások mellett:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

A kanonikus forma jellemzői a következők:

1. A korlátozások rendszerét egyenletek (szigorú feltételek) formájában mutatjuk be.

2. A nem negativitás feltételei minden változóra érvényesek

3. A célfüggvény arra törekszik

Egyes forrásokban az LP probléma kanonikus formában bemutatott célfüggvénye a maximumra hajlik. Ez a probléma megoldásának kényelme érdekében történik a maximális célfüggvényhez kifejlesztett algoritmus szerint.

13. Az LP feladat lehetséges, elfogadható, optimális alapfeladatterve, ODZ-je

1. definíció. Ismeretlen változók értékei, amelyek kielégítik a probléma összes megkötését lineáris programozás, hívják elfogadható változó értékek ill terveket .

2. definíció. A lineáris programozási probléma összes tervének halmazát a változók megengedett értékeinek tartományának ( ODZ ).

3. definíció. A lineáris programozási feladat terve, amelyben a célfüggvény a minimális (vagy maximum) értéket veszi fel az ODZ-n, ún. optimális .

14. Az LP feladatok rekordjainak típusai: kiterjesztett, hajtogatott, mátrix, vektor.

Az LP problémamodellek többféle formában írhatók.

1. A modellrekord kiterjesztett nézete

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Összecsukott nézet:

,

Xj ≥ 0, j = 1, n.

3. Az LP probléma modellje mátrix formában:

X ≥ 0

Ahol

a11 a12 … a1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

am1 am2 … amn X3 am

4. Az LP probléma modellje vektor formában:

Ahol

X1 a11 a12 a1n a1

X2 , a21 , a22 , a2n , a2

… … … … …

Хn am1 am2 am2 am

15. Átmenet az LP feladatok standard és általános formájáról a kanonikusra. Kapcsolódási tétel

Az általános vagy szabványos formáról a kanonikusra való áttéréshez a következő technikákat alkalmazzuk.

1. Változó konverzió. Ha valamelyik Xk változó nem pozitív (Xk ≤ 0), akkor egy új Xk " változó kerül bevezetésre, így Xk " = –Xk . Nyilvánvaló, hogy Xk " ≥ 0. Ezt követően minden kényszerben és célfüggvényben az Xk változó helyére [ – Xk "].

Ha valamelyik Xt változó tetszőleges értéket vehet fel, akkor azt két nem negatív Xt' és Xt'' változó különbségével helyettesítjük, azaz azt feltételezzük, hogy xt = Xt' – Xt'', ahol Xt' 0 ≥ és Xt'' ≥ 0.

2. Kényszer transzformáció. Ha a modellben a megszorítások közül bármelyik egyenlőtlenség alakú, akkor azt a bal oldaláról összeadva (ha az egyenlőtlenség ≤ típusú) vagy kivonva (ha az egyenlőtlenség típusa ≥) egyenlőséggé alakítjuk. Ezeket a változókat egyensúlyi változóknak nevezzük. Az egyenlegváltozók nulla együtthatóval szerepelnek a célfüggvényben. Az egyenleg változó az index értéket szekvenciálisan veszi fel a már meglévők után. Ha például a korlátozási rendszernek 5 változója van, akkor az első mérlegváltozó X6, a második pedig X7 stb.

16. Átmenet a ZLP-modell kanonikus formájáról a szabványra

A kanonikus formáról a standard formára való áttéréshez mindegyik

egyenlőtlenségi rendszerrel helyettesítendő egyenletek:

Egy másik módszer az egyenletrendszer speciális formába hozása és egyes változók további kiiktatása.

A Jordan-Gauss módszerrel minden egyenletben kiválasztjuk az alapváltozót. Az ilyen kiválasztás ekvivalens (elemi) Gauss-transzformációk segítségével történik. Ezek tartalmazzák:

a) bármely egyenlet szorzata nullától eltérő állandóval;

b) összeadás bármely más egyenlet bármely egyenletéhez, bármely állandóval megszorozva.

Kényelmes a kezdeti lineáris egyenletrendszert a transzformáció előtt felírni mátrix vagy táblázat formájában:

A problémát szabványos formában írjuk le.

17. Félsík hipersíkjának, támasztó hipersíkjának fogalma.

18. Geometriai. a kényszerrendszer és a célfüggvény értelmezése LP feladatokban

19. Konvex halmaz: a halmaz szélső (sarok) pontjai. Konvex poliéder

Meghatározás Egy M halmazt konvexnek nevezünk, ha az adott halmazhoz tartozó bármely két ponttal együtt egy azokat összekötő szakaszt is tartalmaz.

domború halmaz

Meghatározás Az M halmaz egy x pontját sarok- vagy szélsőpontnak nevezzük, ha nem belső része egyetlen olyan szakasznak sem, amely teljes egészében az adott halmazhoz tartozik.

1. tétel. Egy szakasz bármely pontja a sarokpontjainak konvex kombinációjaként ábrázolható.

x \u003d λ 1 A + λ 2 B

λ 1 , λ 2 ≥ 0 A és B sarokpontok konvex kombinációja

λ1 + λ2 = 1

2. tétel. Egy konvex zárt halmaz bármely pontja a sarokpontjainak konvex kombinációjaként ábrázolható.

20. Az LP feladatok megoldásának grafikus módszerének algoritmusa

1. Ellenőrzik, hogy az eredeti LPP szabványos formában van-e, ha nem, akkor a feladatot át kell alakítani a szabványos formára.

2. Ellenőrzi az ismeretlen változók számát. Ha ez a szám több mint három, akkor a probléma nem oldható meg grafikus módszerrel (vannak más hatékony módszerek is az ilyen problémák megoldására).

3. A ZLP változóinak megengedett értékeinek régiója kialakítás alatt áll.

4. Vezetővektor épül c .

5. A kezdeti egyenlőcellás az ODZ-n keresztül (az irányvektorra merőlegesen) megrajzolódik.

6. A kezdeti izocoel mentális mozgása a vektor irányába történik c, ha a célfüggvény maximális értékét határozzuk meg, vagy ellenkező irányban, ha a minimális értékét határozzuk meg, amíg az izogól az ODZ-re való hivatkozás nem lesz. A referencia izocoel és az ODZ metszéspontjai lesznek a probléma optimális pontjai.

7. Az optimális pont koordinátáinak meghatározásához meg kell oldani a megfelelő lineáris egyenletrendszert.

8. A célfüggvény optimális értékének megtalálásához be kell cserélni a változók optimális értékeit a célfüggvénybe, és ki kell számítani annak értékét.

20. grafikus algoritmus. LP problémamegoldó módszer

A grafikus módszer algoritmusa.

1. A probléma korlátrendszerének minden egyes feltételének egymás utáni felépítésével valósul meg az ODZ felépítése.

2. A C irányító vektort a célfüggvény változóinak együtthatói alkotják.

3. Az origón keresztül az irányvektorra merőlegesen húzzuk meg a kezdő izocoel-t.

4. A kezdeti izogoált gondolatban a C vektor értékének növekedési irányába mozgatjuk, ha a célfüggvény maximális értékét határozzuk meg, vagy ellenkező irányba, ha meghatározzuk a minimális értékét, amíg az izogoál a hivatkozás az ODZ-re. A referencia izocoel és az ODZ metszéspontjai lesznek a probléma optimális pontjai.

5. Az optimális pont koordinátáinak meghatározásához meg kell oldani azoknak a feltételeknek a megfelelő lineáris egyenletrendszerét, amelyek metszéspontjában az optimális pont található.

6. A célfüggvény optimális értékének megtalálásához be kell cserélni az optimális pont koordinátáit a célfüggvénybe, és ki kell számítani az értékét.

23. tételek az LP probléma megengedett értékeinek tartományáról és a célfüggvényről

Az ODZ tétel. Az LP probléma megengedhető megoldásainak tartománya egy konvex halmaz (zárt és n-dimenziós térben korlátos)

2. Tétel. Egy lineáris programozási feladat célfüggvényéről.

Az LLP célfüggvény optimális értékét a változók elfogadható értékeinek tartományának egyik sarokpontjában veszi fel. Ha a célfüggvény több sarokponton veszi fel az optimális értékét, akkor minden olyan pontban ugyanazt az értéket veszi fel, amely ezen sarokpontok konvex kombinációja.

24. Tétel a sarokpontról. Elegendő és szükséges feltétel

25. Következtetések az LP problémák megoldásainak tulajdonságairól szóló tételből és következtetések. Az alapvonal fogalma.

Következmények a tételekből.

Meghatározás. Terv = (х1,х2,…,хn), amelyek pozitív koordinátái lineárisan független vektoroknak felelnek meg, ún. alapterv PLP .

Következmény 1. A referenciatervnek legfeljebb m pozitív koordinátája van.

Ha pontosan m pozitív koordinátája van, akkor az ilyen tartószerkezetet nem degeneráltnak, egyébként degeneráltnak nevezzük.

2. következmény. Az ODZ minden sarokpontja egy referenciaterv.

27. A szimplex módszer algoritmusa.

Az LP feladatok szimplex módszerrel történő megoldása során a következő műveletsort kell végrehajtani.

1. Ellenőrizzük, hogy az LP probléma kanonikus formában van-e. Ha nem, akkor az eredeti modellt kanonikus formává kell konvertálni.

2. Ehhez a referenciatervhez a kezdeti referenciaterv és a célfüggvény értéke kerül kiválasztásra.

3. A kezdeti szimplex tábla összeállítása.

4. Az indexsorban lévő optimalitásbecslések értékeit ellenőrizzük. Ha nincs pozitív becslés, akkor kiírjuk az optimális megoldást, és az algoritmus befejezi a munkáját. Ellenkező esetben az 5. pont teljesül.

5. A bázisban egy vektort vezetünk be, amely a legnagyobb pozitív becslésnek felel meg. Ezt az oszlopot engedélyezés oszlopnak nevezik.

6. A bázisból egy vektort származtatunk, amely megfelel a 0 képlettel számított szimplex aránynak< Ө ≤ . Данная строка называется разрешающей строкой.

7. Új szimplex asztal készül. A B és C B oszlop ennek megfelelően módosul, a táblázat többi részét az előzőből Gauss-transzformációkkal töltjük ki, az indexsort m+1 soroknak tekintjük, és szintén Gauss-transzformációkkal transzformáljuk. Folytatjuk az algoritmus 4. bekezdésének megvalósítását.

Az egyes táblák elkészítése után az előző bekezdésben megadott becslések kiszámítására szolgáló képletek segítségével ellenőrizheti a számítások helyességét.

28. Alapválasztás és kezdeti referenciaterv készítése a szimplex módszerrel történő problémák megoldásához.

29. Simplex táblázatok, kitöltése. Képletek az indexsor együtthatók kiszámításához.

30 . A lineáris programozási probléma tervének optimalitástétele a szimplex módszerrel történő feladatok megoldásához szükséges optimalitásbecslési tétel következménye.

Tétel 1: Ha a rendszer valamelyik vektorára  j

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2

…………………………………………………..

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

A Z j – c j > 0 összefüggés teljesül, akkor az X B0 terv nem optimális, és át lehet lépni az X B1 tervre úgy, hogy Z (X B1) ≤ Z (X B0).

Itt Z j = (С, Ā j) a vektorok skaláris szorzata.

C a Z célfüggvény alapváltozóinak együtthatóiból álló vektor

Ā j egy vektor, amely a megfelelő vektor bázisvektorokban kifejezett kiterjesztési együtthatóiból áll.

c j az X j változójú Z célfüggvény együtthatója

Következmény tól től tételek: Ha valamely referenciaterv összes  1 ,  2 , …,  n vektorára Х a Z j – c j reláció< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Így a tétel és a következmény lehetővé teszi annak megállapítását, hogy a következő támogatási terv optimális-e, és ha nem, akkor át kell váltani egy másik támogatási tervre, amelyben a célfüggvény értéke kisebb lesz.

Megjegyzés. A tétel és a következtetés feltételezi, hogy a probléma kanonikus formában van, minimális célfüggvénnyel. A szimplex módszer azonban maximum célfüggvényű feladatok megoldására is használható. Ebben az esetben a becslések értékeinek elemzésekor azok ellentétes jelentését használják, vagyis a terv akkor lesz optimális, ha az összes optimalitásbecslés nem negatív (pozitív vagy negatív).

31. A bázisba belépő és a bázisból származtató vektor megválasztása. Simplex összefüggés.

Az új referenciatervre való váltáshoz a szabad vektorok egyikére van szükség lépjen be a bázisba, és adja ki a bázisvektorok egy részét. A bázisba való bevezetéshez olyan vektort választunk, amelynek legalább egy pozitív koordinátája van. Legyen az A m+1 vektor egy ilyen vektor.

bomlás -

Ill. vektor, kat. referenciaterv lesz, ha a koordinátái nem negatívak, és a pozitív koordináták száma egyenlő lesz m-rel.

Az X1 vektorkoordinátáknak nem negatívnak kell lenniük, azaz. .

Ha , akkor ez a koordináta nem negatív lesz.

Legyen az (5) reláció minimuma i =1-nél, akkor ha vesszük

akkor az 1. vektor első koordinátája x nulla lesz.

A (6) relációt hívjuk szimplex reláció. Így elmozdultunk az eredeti 0-s alapvonaltól x(A1, A2, ... Am alapvektorok) az 1. referenciatervhez x(A2,А3,…,Аm, Am+1 alapvektorok).

32. a táblázat megengedő eleme, választása. Teljes Jordan eliminációs szabály szimplex tábla újraszámításához.

33. Négyszögszabály szimplex tábla újraszámítására

34. Az optimális terv egyediségének, az optimális tervek halmazának és az optimális terv hiányának jele az LP feladat szimplex módszerrel történő megoldása során.

A szimplex módszerrel történő problémák megoldása során a következő típusú optimális megoldások lehetségesek:

1. Egyediség . Ha az összes szabad vektor becslése szigorúan negatív, akkor a kapott támogatási terv optimális és egyedi. (lásd a példát az előző bekezdésben).

2. Alternatív optimum (optimális megoldások halmaza).

Ha a szabad vektorok nem pozitív becslései között van legalább egy nulla becslés, akkor a kapott támogatási terv optimális lesz, de nem az egyetlen. Ebben az esetben áttérhet más támogatási tervekre (a nulla becslésnek megfelelő vektorok kerülnek be a bázisba), majd felírhatja az általános optimális megoldást a kapott optimális támogatási tervek konvex kombinációjaként.

3. Az LLP-nek nincs optimális megoldása, mivel a célfüggvény alulról nem korlátos . Ha a szimplex tábla pozitív pontszámú, és minden eleme adott oszlop negatív és nulla, akkor ez a vektor bevihető a bázisba. A bázisból azonban egyik bázisvektor sem vezethető le. Ebből az következik, hogy a célfüggvény további csökkentése nem támogató tervre való átállás esetén lehetséges.

4. Az LLP-nek nincs optimális megoldása, mivel a kényszerrendszer inkonzisztens. Mivel az LLP megoldásánál a szokásos szimplex módszer legyen a kezdeti referenciaterv, a lineáris egyenletrendszer biztosan nem inkonzisztens. Ezért a szokásos szimplex módszerrel történő megoldásnál ilyen eset nem fordulhat elő.

5. Ha az ODZ egy pontból áll, akkor egy ilyen probléma megoldása triviális, és a szimplex módszer használata nélkül is elérhető.

35. Mikor alkalmazzák a mesterséges bázis módszert?

mesterséges.

36. Az M-probléma felépítése mesterséges bázis módszerrel

Ha azonban a lineáris programozási probléma kanonikus formában van, akkor nem minden egyenlet tartalmaz alapvető változókat, azaz nincs eredeti alapvonal. Ebben az esetben azokban az egyenletekben, amelyekben nincsenek alapváltozók, szükséges hozzáadni néhány nem negatív változót, amelynek együtthatója +1. Az ilyen változót ún mesterséges.

A célfüggvényhez nagyon nagy pozitív számmal mesterséges változót kell hozzáadni (hiszen a célfüggvény a minimum megtalálása). Ezt a számot a latin M betű jelöli. Ez egyenlőnek tekinthető +∞-vel. Ebben a tekintetben a mesterséges bázismódszert néha M-módszernek nevezik. Az eredeti probléma ilyen transzformációját a kiterjesztett probléma konstrukciójának nevezzük. Ha egy feladatot egy célfüggvénnyel oldunk meg, hogy mesterséges változót találjunk, akkor a célfüggvényhez nagyon nagy pozitív számot kell hozzáadni (mivel a célfüggvény a minimum megtalálása). Ezt a számot a latin M betű jelöli. Ez egyenlőnek tekinthető +∞-vel. Ebben a tekintetben a mesterséges bázismódszert néha M-módszernek nevezik. Az eredeti probléma ilyen transzformációját a kiterjesztett probléma konstrukciójának nevezzük. Ha egy feladatot egy célfüggvénnyel oldunk meg, hogy megtaláljuk a maximumot, akkor a mesterséges változók -M együtthatóval lépnek be a célfüggvénybe.

Így a kiterjesztett feladatban van egy alapállapotunk (bár az alapváltozók egy része mesterséges).

A kezdeti szimplex tábla létrejön.

37. indexvonal felépítése mesterséges bázis módszerrel

Egy kezdeti szimplex tábla készül, amelyben az indexsort két sorra osztjuk, mivel a becslések két tagból állnak. A felső sor az M nélküli becslés tagját tartalmazza, az alsó sorban az M-nél az együtthatók láthatók. A becslés előjelét az M-nél lévő együttható előjele határozza meg, függetlenül az M nélküli tag értékétől és előjelétől, mivel M egy nagyon nagy pozitív szám.

Így a bázisba bevitt vektor meghatározásához az alsó indexvonalat kell elemezni. Ha a bázisból mesterséges vektort származtatunk, akkor a következő szimplex táblákban a megfelelő oszlop elhagyható, ha nem kell megoldást találni a duális feladatra (lásd a következő témakört).

Miután az összes mesterséges vektort kivettük az alapból, az alsó sorban minden nulla elem lesz, kivéve a mesterséges vektoroknak megfelelő becsléseket. Egyenlõek lesznek -1-gyel. Egy ilyen vonal kivehető a mérlegelésből, és a további megoldás a szokásos szimplex módszerrel végezhető el, ha a kettős feladatra nem kell megoldást találni (lásd a következő témakört).

38. Optimalitási kritérium a mesterséges bázis módszerében. A jel az eredeti feladat kiinduló alaptervének konstrukciója.

39. A duális szimplex módszer algoritmusa

A kettős szimplex módszer algoritmusa:

1. a szokásos módon töltse ki az első szimplex tablót, figyelmen kívül hagyva a szabad kifejezések jeleit. Úgy gondolják, hogy egy ilyen problémának kezdeti egységalapon kell lennie.

2. Válassza ki a vezetővonalat a szabad tagok oszlopának A0 legnagyobb abszolút negatív eleme mellett

3. A vezetőoszlopot az indexvonal elemeinek a vezetővonal negatív elemeihez viszonyított arányának legkisebb abszolút értékének megfelelően választjuk ki.

4. Számítsa újra a szimplex táblát a teljes Jordan elimináció szabálya szerint!

5. ellenőrizze a kapott terv elfogadhatóságát. Az elfogadható referenciaterv megszerzésének jele a negatív elemek hiánya az A0 oszlopban. Ha az A0 oszlopban negatív elemek vannak, akkor lépjen a második bekezdésre. Ha nincs ilyen, akkor a szokásos módon folytatják a probléma megoldását.

6. A kettős szimplex módszerrel optimális megoldás megszerzésének jele a közönséges szimplex módszer optimálissági kritériuma.

41. Nyitott és zárt szállítási modellek. Átmenet nyílt szállítási modellről zárt modellre.

A szállítási feladatok fajtái.

Elérhető m ismert termékkészlettel rendelkező homogén termékek beszállítói és n e termékek adott mennyiségű szükséglettel rendelkező fogyasztói. A szállítás egységköltsége is ismert.

Ha a termékkészletek mennyiségének összege megegyezik az összes fogyasztó szükségleteinek mennyiségével, akkor egy ilyen problémát ún. zárt szállítási feladat

(vagyis ha ∑ Ai = ∑ Bj), különben a szállítási probléma ún. nyisd ki. A szállítási probléma megoldásához be kell zárni.

Egy nyitott szállítási feladat zárttá alakítható a következő módon.

Legyen ∑Ai > ∑Bj. Ebben az esetben be kell vezetni egy fiktív n + 1 fogyasztót ∑Ai – ∑Bj szükségletekkel A szállítóktól a fiktív fogyasztóig történő szállítás fajlagos költsége 0, mivel az ilyen szállítás valójában nem lesz és a termékek egy része a beszállítóknál marad.

Ha ∑Bj > ∑Ai . Ebben az esetben egy fiktív m + 1 szállítót kell bevezetni ∑Bj – ∑Ai készletmennyiséggel. Feltételezzük, hogy a fiktív szállítótól a fogyasztókhoz történő szállítás egységköltsége 0, mivel valójában ilyen szállításra nem kerül sor, és a fogyasztók nem kapják meg a termékek egy részét.

42. A kezdeti eloszlás felépítésének módszerei a szállítási feladatban: az északnyugati sarok módszere és a mátrix legkisebb elemének módszere.

Northwestern technika referenciaterv készítéséhez. E technika szerint a forgalmi értékek kialakítása az s.-z. asztalsarok, i.e. x11 cellából. E módszer szerint mindenekelőtt az első szállító áruit osztják szét. Sőt, az első szállító először az első fogyasztót elégíti ki, amennyire csak lehetséges. Ezután, ha a szállítónak még megvan az áru,

A mátrix legkisebb elemének módszere.

A módszer lényege abban rejlik, hogy mindig a lehető legnagyobb kínálat kerül a cellába, ami megfelel a mátrix legalacsonyabb tarifájának.

Először is jelölünk (például ▼ jellel) a sorok azon celláiban, amelyekben a sor legalacsonyabb ára figyelhető meg. Ezután oszloponként körbejárjuk a táblázatot, és ugyanazokat a megjegyzéseket tesszük azokban a cellákban, amelyekben a legkisebb ár van oszloponként.

A további elosztás először lehetőség szerint két jelölésű cellákon történik, majd - eggyel, majd kiegyenlítjük a feladatot (m + n - 1) kitöltésekre. Az asztal balról jobbra haladásakor és fentről lefelé haladva szervezzük a kitöltést.

43. A szállítási feladatok tulajdonságai

A szállítási problémának van néhány olyan tulajdonsága, amelyet a következő tételek tükröznek.

1. tétel. A zárt közlekedési problémára mindig van megoldás.

2. tétel. Ha a termékkészletek mennyisége és a szükségletek mennyisége egész szám, akkor a szállítási feladat megoldása is egész szám lesz.

3. tétel. egy zárt szállítási probléma kényszerrendszere mindig lineárisan függő.

Ebből a tételből következik, hogy egy zárt szállítási probléma eloszlása ​​mindig m + n – 1 alapváltozóval és (m – 1) (n – 1) szabadidő-változóval rendelkezik.

44. Degenerált eloszlás a közlekedési problémákban, a degenerációtól való megszabadulás. Áthúzott kombináció.

Az eloszlást degeneráltnak nevezzük, ha a cellák száma kisebb, mint m + n - 1.

45. Optimalitási tételek a transzport problémára.

Tétel. Ha a szállítási feladat valamely elosztására Ön

feltételek teljesülnek:

A). ui+vj = cij az elfoglalt cellákhoz

b) ui+vj ≤ сij, szabad cellákhoz,

akkor ez az eloszlás optimális.

Az ui értékeket sorpotenciáloknak, a vj értékeket oszloppotenciáloknak nevezzük.

46. ​​Lehetőségek és számítási módszerek.

A sorok és oszlopok potenciáljának meghatározásához az alábbi érvelést alkalmazzuk az optimalitástétel a) feltétele alapján.

Az ezen feltételen alapuló egyenletek száma m + n – 1, az ui és vj ismeretlenek száma pedig m + n. Hogy. a változók száma nagyobb, mint az egyenletek száma, és minden egyenlet lineárisan független. Egy ilyen lineáris egyenletrendszer megoldása határozatlan, ezért az egyik potenciálhoz tetszőleges értéket kell rendelni. A gyakorlatban ui = 0. m + n – 1 egyenletrendszert kapunk m + n – 1 ismeretlen változóval. Ez a rendszer bármilyen módszerrel megoldható. A gyakorlatban a potenciálok kiszámításához azokat a foglalt cellákat veszik figyelembe, amelyekre az egyik potenciáljuk ismert, és a tétel a) feltétele alapján kiszámítják a fennmaradó ismeretlen potenciálok értékeit.

47. Becslések számítása a szállítási feladatok elosztásának optimálisságára és az optimalitás kritériumára.

A tétel b) összefüggése alapján a következő képletet írhatjuk fel a becslések kiszámításához: δ ij= ui + vj – сij. Annak érdekében, hogy ne keverjük össze a becsléseket a forgalommal, ezeket (becsléseket) körökbe zárjuk.

A szabad TK-cellákban az optimalitásbecslések olyan optimalitási kritériumok, amelyek ellenőrzik az eloszlást az optimalitás szempontjából. Ha az összes szabad cella becslése nullánál kisebb vagy egyenlő, akkor ez az eloszlás optimális.

48. az ellátás újraelosztása a szállítási problémában

Ha az elosztás nem optimális, akkor szükséges a készletek újraelosztása.

Az újraelosztáshoz egy újraszámítási ciklus épül. A legmagasabb pozitív pontszámmal rendelkező cella lesz kiválasztva cellának. Ez a cella „+” jellel van jelölve, azaz bizonyos mennyiségű szállítást kell rögzíteni benne. Ekkor azonban az oszlop egyensúlya megbomlik, ezért ennek az oszlopnak az egyik foglalt celláját „-” jellel kell megjelölni, vagyis az ellátás mennyiségét ugyanennyivel kell csökkenteni. Ekkor azonban ennek a sornak az egyensúlya megváltozik, ezért ennek a sornak néhány elfoglalt celláját „+” jellel kell megjelölni. Ez a folyamat addig folytatódik, amíg egy „-” jel nem kerül abba a sorban, ahol az eredeti cella volt.

Minden szabad cellához van egy újraszámítási ciklus, és ráadásul az egyetlen.

49. újraelosztási láncok, típusaik.

Legyen a vizsgált szállítási terv ne optimális, pl. vannak pozitív relatív becslések. Ezután vesznek egy kedvezőtlen cellát (a kedvezőtlenek egyikét), és felépítenek egy újraszámítási ciklust, amely szerint a tervezett szállítást újra elosztják. A ciklus tört zárt vonal formájában épül fel, melynek szakaszai vagy az oszlop mentén, vagy a vonal mentén futnak. A szaggatott vonal egyik sarkában a terméket igénylő kedvezőtlen cella található, a többi sarkában pedig a cellák kitöltése, pl. ciklus felépítésénél a jelölt cellából indulunk ki és szaggatott vonal mentén térünk vissza oda, de csak a kitöltött cellákban tudunk fordulatot tenni (az alapváltozóknak megfelelően). Egy kedvezőtlen cella hivatkozzon a Q termékre. A táblázat egyensúlyhiányának elkerülése érdekében szükséges

hozzáadni és kivonni Q-t az elérhető forgalomból. Mivel páros számú sarok van, Q hozzáadódik a cellák feléhez, és kivonja a másik feléből. A ciklus az óramutató járásával megegyező vagy azzal ellentétes irányba indul a jelölt cellából, jó Q-t helyezve oda, majd Q-t kivonunk a szomszédos cellából, majd hozzáadjuk, és így tovább. Maga a Q értéke úgy van megválasztva, hogy az egyik cella kiürüljön, de egyik készlet sem lesz negatív.

Ehhez a Q-t egyenlőnek kell választani azon cellák legkisebb redukálható értékével, amelyekben Q ki van vonva. A következő ábrán. 7.1 és 7.2 példákat mutatunk be a ciklusokra és a számítási szabályra.

Ebben az esetben két cella ürül ki. De szükséges, hogy csak egy cella legyen kölcsönösen üres. Ezt teszik: az új táblában az egyik ürítő cellát üressé teszik, a másik ürítő cellába pedig nullát helyeznek el. Ez a cella az új táblázatban alap (kitöltésnek) minősül.

50. Az újraelosztás mértékének megválasztása.

A szállított termékek mennyiségének meghatározása. A számlálási cikluson keresztül mozgott termékek mennyiségének meghatározásakor a következő két szempontot kell figyelembe vennünk:

a) a táblázat celláiban történő transzformáció után ne kapjunk negatív számokat;

b) az egyik elfoglalt cellának fel kell szabadulnia.

Ahhoz, hogy ezek a feltételek teljesüljenek, a szállított termékek mennyiségét az alábbiak szerint kell kiválasztani: θ=min (хij) -, ahol (хij) az újraszámítási ciklus „ jellel jelölt celláiból történő szállítás mennyisége -” jel.

θ=min(20;30)=20

A „+” jellel jelölt cellák értékéhez hozzáadódik a θ. A θ-t kivonjuk a „-” jellel jelölt cellák értékéből. A fennmaradó cellák ellátási értéke változtatás nélkül felülírásra kerül. Ennek eredményeként a következő táblázatot kapjuk.

53. A potenciálok módszerének algoritmusa.

Algoritmus:

1. Ellenőrizze, hogy az egyenlet teljesül-e a feladatra ha nem, akkor egy fiktív szállítót vagy fogyasztót vezetnek be a feladatba

2. A feladatfeltételt egy szállítás.tábla formájában írjuk fel

3. A kezdeti alapvonal kiépítése folyamatban van

4. Az ellátási és fogyasztói lehetőségek meghatározása

5. A szabad cellák pontszámait kiszámítjuk. Ha nem mindegyik negatív, akkor a terv optimális, és ki kell írni a választ. A szállítási mátrix X és határozza meg a szállítási költségek összegét. Ha a terv nem optimális, azaz a becslések között vannak negatívak is, akkor válasszunk egy ígéretes cellát a legnagyobb negatív értékkel. becsülje meg és adja át a nagyságrendet a következőnek.

6. Töltsön be egy perspektivikus cellát. Készítsen új alaptervet szállítási táblázat formájában. Tovább a 4. pontra.

54. Termékek előállítási és szállítási költségének elszámolása. Szállítási feladat ellátási tilalmakkal.

Egyes problémák megoldásánál nem csak az áruszállítás, hanem a szállított termékek előállításának költségeit is figyelembe kell venni. Ehhez a mátrix transzp. feladatokat

Ahol Cij ' egy egységnyi kibocsátás előállításának csökkentett költsége.

Cij “- egy termelési egység szállításának költsége.

Feladatok ellátási tilalmakkal.

Bizonyos helyzetekben a termékek szállítása semmilyen útvonalon nem lehetséges.

Ehhez a szállítási feladat mátrixába, amelyen keresztül a szállítás tilos, egy tiltó tarifát írunk be M. A továbbiakban a feladat megoldása a szokásos módon történik, de ez a cella mindig negatív cellapontszámnak fog megfelelni.

55. figyelembe véve az útvonalak áteresztőképességére vonatkozó korlátozásokat, figyelembe véve az egyes szállítások kötelező jellegét a szállítási problémában.

figyelembe véve az útvonalak áteresztőképességére vonatkozó korlátozásokat.

Egyes szállítási feladatokban, egyes útvonalakon egy kisebb áteresztőképesség mint amennyi a fogyasztási hely keresletének kielégítéséhez szükséges.

figyelembe véve a szállítási probléma egyes szállításainak kötelező jellegét.

Bizonyos esetekben a feladat megköveteli, hogy például az Ak Bs útvonalon A mennyiségi egységekben történő szállítást kell végrehajtani. Ebben az esetben az A pont termelési mennyiségéből és az S Bs mennyiségből levonjuk a kötelező beszerzést, és az opcionális ellátás tekintetében megoldódik a probléma. Az optimális megoldás elérése után az Ak Bs cellában álló térfogathoz szükségszerűen hozzáadjuk az utánpótlást.

56. Lehetséges következtetések a gazdasági. az optimális eloszlás értelmezése nyílt szállítási problémákra.

Az optimális eloszlás megérkezése után vissza kell térni az eredeti problémához és gazdaságossá kell tenni a megfelelőt. következtetéseket. Ezek a következők:

1. Ha egy fogyasztási pontot vezetnek be, ez azt jelenti, hogy az elemzett rendszerben túlzott termelési mennyiségek vannak, és a vizsgált rendszer sérelme nélkül lehetőség van ezen termelési pontok kapacitásának csökkentésére a kötés mértékével. amelyek a fiktív fogyasztási ponthoz kötődnek.

2. Ha egy fiktív termelési pontot vezetnek be, akkor ez azt jelenti, hogy a valós termelési pontok kapacitásai nem elegendőek, és növelni kell azokat. A fiktív termelőhelyhez kötött fogyasztási pontokhoz legközelebb eső termelőhelyek kapacitását növeljük. A gyártó kapacitását a kötési érték növeli. Ehhez vegye figyelembe a fogyasztási hely oszlopát, amely a fiktív termelési ponthoz van kötve, és keresse meg benne a legalacsonyabb tarifát. A leghatékonyabb a kötés mértékével növelni az ennek a tarifának megfelelő termelőhely kapacitását.

57. A kettősség fogalma. Kettős problémák közgazdasági megfogalmazása a termelési terv optimalizálása probléma példáján.

A kettős probléma a lineáris programozás egy segédproblémája, amelyet bizonyos szabályokkal közvetlenül az eredeti, vagy direkt probléma feltételeiből fogalmaznak meg.

Legyen feladat a termelési terv optimalizálása. Ez így néz ki:

Kezdeti feladat:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | 2-kor

……………….. |.. (1)

A T 1 x 1 +a T 2 x 2 + ... + a T n x n ≤v 1 | nál nél T

x j ≥0, j = 1,n(2)

z = c 1 x 1 + c 2 x 2 +…+c n x n ->max(3)

X \u003d (x 1, x 2, ..., x n)

a ij - az i-edik típusú alapanyagok száma, amelyeket a j-edik típusú termék előállítására költöttek

Kettős probléma

Hagyja, hogy a vállalkozás bármilyen okból ne tudjon termékeket előállítani. Az állásidő költségeinek csökkentése érdekében a cég értékesítheti a nála lévő alapanyagokat. Milyen áron kell eladni az alapanyagokat?

i - a vállalkozásnál elérhető i-edik típusú alapanyag ára.

a 11 év 1 + a 21 év 2 + ... + a T 1 év T≥s 1

a 12 x 1 + a 22 y 2 + ... + a T 2 x n ≥s 2

……………….. (1’)

A 1p y 1 +a 2p y 2 +…+ a tp nál nél T≥s P

i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b m y m -> min(3’)

58. A direkt és a kettős probléma szerkezeti elemei közötti megfelelés

Minden lineáris programozási probléma társítható

kettős feladat az alábbi szabályok szerint:

1. Az eredeti probléma minden megkötésében a szabad kifejezéseknek kell

a jobb oldalon legyen, a bal oldalon pedig az ismeretlenekkel jelölt kifejezések.

2. Az eredeti probléma megszorításainak-egyenlőtlenségének előjelekkel kell rendelkeznie,

egy irányba irányítják.

3. Ha az eredeti feladatban a célfüggvényt minimalizáljuk, akkor az egyenlőtlenségi kényszereket "≤" előjellel kell írni, akkor a duális feladatban a célfüggvény minimalizálódik és az egyenlőtlenségi kényszerek előjele "≥" lesz.

4. Az eredeti probléma minden kényszere egy in változónak felel meg

kettős feladat. Ha egy változó egyenlőtlenségnek felel meg, akkor nem negatív, ha egyenlőségnek felel meg, akkor a változó előjelre vonatkozó korlátozások nélkül („tetszőleges”).

5. A kettős feladat kényszereiben szereplő változók együtthatóit a következő mátrix transzponálásával kapjuk meg.

együtthatók az eredeti probléma változóihoz.

6. Az eredeti feladat szabad tagjai az at együtthatók

változók a duális probléma célfüggvényében, és szabad

A duális feladatban szereplő kifejezések az in változók együtthatói

Az eredeti probléma függvényei Megjegyezzük azt is, hogy a dualitási reláció kölcsönös, i.e. a duálishoz képest duális feladat egybeesik az eredetivel A duális feladatpárok szimmetrikusra és aszimmetrikusra oszthatók. Egy szimmetrikus párban a primál és a duális probléma kényszerei nem szigorú egyenlőtlenségek, ezért mindkét probléma változói csak nem negatív értékeket vehetnek fel.

59. Duális feladatok konstrukciója a modell standard, kanonikus és általános formájába írt eredeti feladatokra (szimmetrikus és aszimmetrikus duális feladatok konstrukciója)

Szabványos forma (eredeti)

Σ a ij x j ≤ b i , i=1,n(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Kettős szabvány

Σ a ij y i ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = Σ b i y i ->min(3)

Az eredeti probléma kanonikus formában:

Σ a ij x j = b i , i=1,m(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

Kettős kanonikus

Σ a ij y i ≤ c j , j=1,n(1)

y i - bármelyik (2)

F = Σ b i y i ->max(3)

Adjunk közgazdasági értelmezést egy kettős problémapárnak. Tekintsük az erőforrások ésszerű felhasználásának problémáját. Legyen a vállalkozásnak olyan b1,b2,…bm erőforrása, amelyet n-féle termék előállítására használhat fel. Ismertesse még a j típusú termék egységköltségét cj (j=1,n) és az i-edik erőforrás felhasználási arányát (i=1,m) egy egység előállításához j-edik produkció– aij Meg kell határozni az egyes típusok termelési mennyiségét xj (j=1,n), maximalizálva az összköltséget

f= c1x1+…+cnxn (1)

Ugyanakkor az erőforrások felhasználása nem haladhatja meg a rendelkezésre állásukat:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Az összes ismert gazdasági értelemben nem negatív:

Xj>=0 (j=1,n). (3)

Vegye figyelembe, hogy ez a probléma szimmetrikus kettős problémát alkot.

Aszimmetrikus kettős problémák.

Vegyük maximálisra a ZLP-t kanonikus formában:

Max Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Fő és második dualitástétel (állapottételek és magyarázat)

Az első kettősségi tétel.

Tétel: ha az egyik kettős feladatnak van optimális terve, akkor a másik megoldható, pl. opt.-tervvel rendelkezik. Ebben az esetben a célfüggvények szélső értékei egybeesnek (j=1-től n-ig) Σcjxj*= (i=1-től m)Σbiyi*, ha az eredetiben. probléma esetén a célfüggvény korlátlan a tervek halmazán, akkor a duális feladatban a kényszerrendszer inkonzisztens.

Második dualitástétel és közgazdasági értelmezése.

Azért, hogy érvényes megoldások duális feladatpárok optimálisak, szükséges és elegendő a feltétel teljesítéséhez: xj*(∑aij yi*-cj)=0, j 1-től n-ig, yi*(∑aij xj*-bi)=0, I 1-től m-ig. Ezek a komplementer lazaság feltételei. Ezekből következik: ha a kettős probléma bármely korlátozását az optimális terv szigorú egyenlőséggé alakítja, akkor az opt megfelelő összetevője. A kettős feladat tervének nullának kell lennie. terv egyenlő nullával, akkor a kettős feladat megfelelő megszorítását az opt.terv szigorú xj*>0 egyenlőséggé alakítja át, ezért (i= 1-től m-ig)Σaij yi*=cj opt.terv, akkor ha költségek>árak, termelési mennyiség=0 Σaij yi* >cj tehát xj*=0

yi*>0 tehát (j=1-től n-ig) Σaij xj*=bi (erőforrás versenyek = erőforráskészlet).

(j=1-től n-ig) Σaij xj*

A tétel jelentése a következő:

Ha egy egységnyi prod-ii \u003d ár előállításához szükséges erőforrás-felhasználás költségbecslése, akkor az ilyen típusú prod-ii szerepel az optimális tervben;

Ha a költségek meghaladják az árat, akkor a prod-yu-t nem szabad előállítani;

Ha erőforrás-felhasználás = készlet, akkor ennek az erőforrásnak a költségbecslése pozitív. Az ilyen erőforrást szűkösnek nevezik. A leghiányosabb.res-s rendelkezik a legmagasabb pontszámmal;

Ha az erőforrás nincs teljesen elhasználva, akkor a költségbecslése = 0.

61. A duális feladat optimális támogatási tervének felépítése az eredeti feladat szimplex táblájából

Információk a lineáris transzformációk inverz mátrixának oszlopaiból, amelyek az optimális eredményhez vezettek. A D-1 mátrix oszlopai nagyon hasznos információkkal szolgálnak.

A3 oszlop: az S2 erőforrás "árnyék" ára y01=0, az oszlop marad

single és az első sorból kiolvasható, hogy x3=9, azaz. a talált optimális terv megvalósítása során az 1. erőforrás többlet lesz, és ez a többlet (alulkihasználtság) mindössze 9 konvencionális egységet tesz ki.

A4 oszlop: az S2 erőforrás „árnyék” ára egyenlő y02=1-gyel, az erőforrás teljes mértékben felhasználásra kerül, és annak esetleges növelése a célfüggvény (azaz a bevétel) növekedéséhez vezet. És mert y02=1, akkor az S2 erőforrás növekedése 1 c.u. hozzáadást ad a bevétel szempontjából.Z = y02· .w2 = = 1.1 = 1 (ezer UAH) (itt.w2 az S2 erőforrás növekménye, .Z pedig a megfelelő jövedelemnövekmény). Az S2 erőforrás ilyen növelésével a maximális bevétel már Zmax=58 ezer UAH lesz. + 1 ezer UAH = 59 ezer UAH. ábrán. A 6.2 ezt a helyzetet szemlélteti, amelyhez az alábbiakban adunk magyarázatot. Az A4 oszlopból az is következik, hogy az S2 erőforrás 1 c.u-val történő növelésével. az új optimális ponthoz a T1 áru kibocsátása ½ tonnával csökken (az x1 alapváltozó sorának és az A4 oszlopnak a metszéspontjában "-1/2"), a T2 áru kibocsátása pedig 3-mal nő. /2 tonna (mivel az x2 alapváltozós sorban az A4 oszlopban "3/2" van. Az A4 oszlopról elmondottakat az alábbiakban grafikus konstrukciók segítségével kommentáljuk (6.2. ábra). A5 oszlop: az "árnyék" " az S3 erőforrás ára egyenlő: y03=2. Ez azt jelenti, hogy az S3 erőforrás 1 c.u-val nő. Z-ben hozzáadódik.Z = y03 · .v3 = 2,1 =2(ezer hrivnya), és Zmax=58 ezer hrivnya lesz. + 2 ezer UAH = 60 ezer UAH. Ugyanakkor a táblázat A5 oszlopából következően. 3, a T1 kibocsátása ½ tonnával nő, a T2 pedig ½ tonnával csökken. Az S1 nyersanyag készlet (lásd 1. sor) 3/2 c.u-val nő.

62. A dinamikus programozási módszer ötlete és geometriai értelmezése. Bellman optimalitás elve.

A feladat dinamikus programozási módszerrel történő optimális megoldását a funkcionális egyenlet alapján találjuk meg

Ennek meghatározásához a következőkre van szüksége:

1. írja fel a folyamat utolsó állapotának funkcionális egyenletét (megfelel l \u003d n-1)

fn-1(Sl-1)=optimum(Rn(Sn-1,Un)+f0(Sn))

2. Keresse meg Rn(Sn-1,Un) értékeinek diszkrét halmazából bizonyos rögzített Sn-1 és Un értékeket a megfelelő megengedett területekből (mivel f0(Sn)=0, akkor f1(Sn-1)= optimum(Rn(Sn-1,Un)

Ennek eredményeként az első lépés után az Un megoldás és az f1(Sn-1) függvény megfelelő értéke ismert.

3. Csökkentse l értékét eggyel, és írja fel a megfelelő funkcionális egyenletet! Az l=n-k (k= 2,n) esetén így néz ki

fk(Sn-k)=optimum(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. találni egy feltételesen optimális megoldást a (2) kifejezés alapján

5. ellenőrizze, hogy mekkora l értéke Ha l=0, akkor a feltételesen optimális megoldások számítása befejeződött, és megvan a feladat optimális megoldása a folyamat első állapotára. Ha l nem egyenlő 0-val, folytassa a 3. lépéssel.

6. Számítsa ki a feladat optimális megoldását a folyamat minden további lépésére, a számítások végétől az elejéig haladva!

A programok dinamizmusa lehetővé teszi, hogy egy sok változós problémát több, egymás után megoldott, kisebb számú változóval rendelkező feladat helyettesítsen. A döntés lépésről lépésre születik. A fő elv, amelyen a többlépéses folyamat optimalizálása, valamint a számítási módszer jellemzői alapul, a Bellman optimalitás elve.

Az optimális viselkedésnek az a tulajdonsága, hogy bármilyen legyen is a kezdeti állapot és a kezdeti döntés, a későbbi döntéseknek optimálisnak kell lenniük a kezdeti döntésből következő állapothoz képest.

Matematikailag a forma kifejezéseként van írva:

fn-1(Sl)=optimum(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1) Az optimum a kifejezésben a maximumot vagy minimumot jelenti a probléma állapotától függően.

63. A DP módszerrel megoldott problémákra vonatkozó követelmények

A dinamikus programozás egy matematikai módszer a többlépcsős problémák optimális megoldásának megtalálására. A többlépcsős folyamat olyan folyamat, amely idővel fejlődik, és több lépésre vagy szakaszra bomlik.

A dinamikus programozási módszer egyik jellemzője, hogy a többlépcsős folyamatokkal kapcsolatos döntéseket nem egyetlen aktusnak, hanem egymással összefüggő döntések egész komplexumának tekinti. Az egymással összefüggő döntések ezt a sorozatát stratégiának nevezzük.Az optimális tervezés célja egy olyan stratégia kiválasztása, amely egy előre kiválasztott kritérium alapján a legjobb eredményt nyújtja. Az ilyen stratégiát optimálisnak nevezzük.

A módszer másik fontos jellemzője a következő lépésben meghozott optimális döntés függetlensége az őstörténettől, azaz. hogy az optimalizált folyamat hogyan érte el jelenlegi állapotát. Az optimális megoldást csak a folyamatot jelenleg jellemző tényezők figyelembevételével választják ki.

A dinamikus programok módszerére az is jellemző, hogy minden lépésnél az optimális megoldás kiválasztását a jövőbeni következmények figyelembevételével kell meghozni. Ez azt jelenti, hogy miközben minden egyes lépésnél optimalizálja a folyamatot, semmi esetre sem szabad megfeledkezni az összes további lépésről.

64. A DP módszerrel megoldott probléma matematikai modelljének közgazdasági megfogalmazása és felépítése (a tőkebefektetések eloszlási problémájának példáján). Bellman recidíva reláció.

Előzetesen magyarázzuk el, hogy a dinamikus programozási módszert elsősorban azokra a problémákra alkalmazzuk, amelyekben az optimalizálandó folyamat (vagy szituáció) térben vagy időben, vagy mindkettőben kerül alkalmazásra.

Legyen maga a folyamat (szituáció) olyan bonyolult, hogy nincs mód ismert módszerekkel optimalizálni. Ezután a dinamikus programozás módszere szerint egy KOMPLEX folyamatot (műveletet, szituációt) több szakaszra (lépésre) osztanak (particionálnak). Ez a bontás sok esetben természetes, de általában mesterségesen vezetik be. . Például, ha bármilyen sakkjátszmát mérlegelünk, minden játékos minden lépése csak adogat

a teljes tétel külön lépésekre (szakaszokra) bontása. Egy rakéta elleni hadműveletben pedig az egész folyamatos folyamatot mesterségesen szakaszokra kell osztani, például a megfigyelés minden másodpercében. A dinamikus programozási módszer lehetővé teszi, hogy a teljes komplex folyamat optimalizálását felváltsa az egyes szakaszok feltételes optimalizálása

(lépések) követi a teljes folyamat optimális szabályozásának szintézise. Ugyanakkor a módszer biztosítja, hogy a feltételes optimalizálás külön lépésben (szakaszban) történik, elsősorban a teljes művelet érdekében.

Minden olyan számítást, amely lehetővé teszi az n lépésben elért hatás optimális értékének, fn(S0) meghatározását, az (1) képlet szerint hajtjuk végre, amelyet alapfunkcionális Bellman-egyenletnek vagy ismétlődési relációnak nevezünk. Az fn-1 függvény következő értékének kiszámításakor az előző lépésben kapott fn-(l+1) függvény értékét, valamint az Rl+1(Sl,Ul+1) hatás közvetlen értékét használjuk, adott állapotú Sl rendszerekre az Ul+1 megoldás választásának eredményeként. Az fn-1(l=0,n-1) függvény értékének kiszámításának folyamata

Az f0(Sn)=0 természetes kezdeti feltétel mellett hajtjuk végre, ami azt jelenti, hogy a rendszer végállapotán kívül a hatás nulla.

65. A tőkebefektetések megoszlásának problémája (példa).

A tőkebefektetések optimális eloszlásának problémájának megoldására a funkcionális Bellman-egyenletet használjuk. Először a legegyszerűbb szituáció felhasználásával szemléltetjük a Bellman-féle funkcionális egyenlet levezetését, majd egy példán keresztül bebizonyítjuk, hogyan lehet ezzel az egyenlettel megoldani a számunkra érdekes problémát.

Kezdjük a K nagyságú allokált tőkebefektetések optimális eloszlásával két vállalkozás között. A vállalkozások tervezési osztályai számításaik alapján a P1 vállalkozásnál a q(x), a P2 vállalkozásnál a h(x) jövedelemfüggvényeket alakították ki. Ezek a függvények azt jelentik, hogy ha az első vagy második vállalkozás x összegű befektetést kap, akkor az első vállalkozás

a q(x) bevétel érkezik, a második h(x), és az x értéke folyamatos vagy ismert diszkrét értékeket vehet fel 0-tól K-ig.

Tehát legyen a P1 vállalat allokált tőkebefektetések x összegben, majd a P2 vállalat kapja a K - x összeget. Ebben az esetben az első vállalkozástól q(x), a másodiktól pedig h(K - x) bevétel érkezik. Ha a K beruházásokat egy tervezési időszakra osztották fel, akkor a két vállalkozás teljes bevétele R(K, x) = q(x) + h(K - x). Nyilvánvalóan x-et és ennek megfelelően K - x-et úgy kell megválasztani, hogy R(K, x) vegye fel a maximális értékét, amit F(K)-val jelölünk:

Ez a bejegyzés olyan, mint egy csontváz a teljesebb bejegyzésekhez.

funkcionális Bellman-egyenlet. BONYOLÍTSA feladatunkat azzal, hogy a tőkebefektetéseket két tervezési időszakra (két szakaszra) osztjuk fel. . Kezdetben döntsenek arról, hogy az x összeget az első P1 vállalkozáshoz, az x összeget pedig a második P1 vállalkozáshoz rendelik. Általában a jövedelem egyenlő R(K, x) = q(x) +

h(K - x). Ha szem előtt tartjuk, hogy a befektetések 2 periódusra (2 szakaszra) oszlanak meg, akkor az első vállalkozásnál a befektetések egyenlege x lesz, ahol , a másodiknál ​​pedig - .(K - x), ahol Ennek megfelelően a bevétel a a második periódus q( .x) - az első lehetőség szerint és h[.(K - x)] - a második szerint. A dinamikus programozás optimalizálás általában a végfokozattól kezdődik. Ezért a második szakaszból indulunk ki, és a másodikban F1-nek jelöljük a két vállalkozástól származó maximális bevételt

színpad. Kap

Ezután a figyelembe vett utolsó (esetünkben a második) szakaszhoz mintegy hozzáadjuk az előző (esetünkben az első) szakaszt, és megkeressük a két szakaszból együtt a maximális bevételt:

Hasonlóképpen n szakaszra kapjuk

ahol Fn-1 az a célfüggvény, amely a legjobb eredményt adja az utolsó (n - 1) szakaszra. A kapott funkcionális Bellman-egyenlet ismétlődő, azaz. az Fn értéket az Fn-1 értékhez társítja.

Általánosságban elmondható, hogy a Bellman-egyenlet alakja

ahol , Fn-1 - maximális bevétel (n - 1) utolsó szakaszra, Fn -

maximális bevétel mind az n szakaszra.

66. A nemlineáris programozás feladatmegoldásának fogalma

Tegyük fel a nemlineáris programozás problémáját a következő általános formában: keressük meg az x1, x2, ..., xn változók olyan értékeit, amelyek megfelelnek a feltételeknek:

és hozza be a célfüggvény szükséges szélsőértékét (maximumát vagy minimumát).

f = f(x1, x2,…, xn), (13,2)

ahol f(х1, …, хn) és qi(х1, …, хn) (m , 1 i =) valós nemlineáris,

n valós változó reguláris függvényei.

Általános tulajdonságaik szerint a nemlineáris programozási problémák képesek

jelentősen eltérnek a lineárisaktól. Például a megvalósítható megoldások tartománya már nem konvex lehet, és a célfüggvény extrémuma a megvalósítható tartomány bármely pontján megfigyelhető. A nemlineáris problémák megoldásának módszerei is jelentősen eltérnek egymástól. Tekintsünk csak néhány megközelítést ezeknek a problémáknak a megoldására.

A grafikus megközelítés mindenekelőtt a nemlineáris programozás legegyszerűbb problémáinak megoldására is érvényes. Tehát, ha az x1 és x2 változók a probléma argumentumai, akkor először ezeknek a változóknak a síkjára építjük fel a megvalósítható megoldások területét, majd a célfüggvény szintjei segítségével meghatározzuk a terület optimális pontját. f(x1,x2).

A nemlineáris programozásban gradiens megközelítést alkalmaznak számos probléma megoldására. Számos gradiens módszer létezik, amelyek lényege az optimális eredmény megtalálása a célfüggvény gradiensével - egy vektorral, amely jelzi a cél maximális növekedésének irányát a figyelembe vett pontra vonatkozóan. Általános esetben a keresési eljárás iteratív módban történik az eredetileg kiválasztott ponttól a legjobb mutatójú pontokig. Legyen például . - az elfogadható megoldások területe

problémát, és a számítások iteratív folyamata a ponttól indul

Továbbá először a célfüggvény gradiense mentén átmenet történik, majd visszatérés a területre. a gradiens mentén az O2 O3 régió bolygatott határáig. A 13.3 úgy van ábrázolva, hogy a páratlan indexű Ai a területhez tartozik, a páros indexű Ai pontok pedig nem.. Ahogy közeledünk az optimális Q ponthoz, a munkagradiensek irányai konvergálnak. Ezért a folyamat megállításának ideális kritériuma a célgradiens és a megszakított határgradiens kollinearitása lesz.

67. A parametrikus és egész programozás fogalma .

A ZCLP állítása és matematikai modellje.

Az oszthatatlan objektumokkal kapcsolatos problémák esetén a változókra egészszámú feltételek vonatkoznak. Néha ezek a feltételek minden változóra érvényesek, néha néhány változóra. Tekintsünk egy teljesen integer problémát

f=(n,j=1)∑CjXi max

(n,j=1)∑AijXj=bi, i=1,m

xi-egész szám,j=1,n

Most az általános lineáris programozási feladattól eltérően az optimális terv nem feltétlenül a tervpoliéder csúcsán lesz. Az egész feladatok megoldására a következő módszerek állnak rendelkezésre:

1. Vágási módszerek

2.Kombinatorikus

3. Hozzávetőleges módszerek..

A paraméteres programozás a matematikai programozás azon ága, amely olyan optimalizálási problémák vizsgálatára irányul, amelyekben az elfogadhatósági feltételek és a célfüggvény bizonyos determinisztikus paraméterektől függ.

Meghatározás. Lineáris programozás (LP) - a kutatási módszerek tudománya és egy lineáris függvény extrém (maximum és minimum) értékeinek megtalálása, amelyek ismeretleneire lineáris korlátozások vonatkoznak.

Ezt a lineáris függvényt nevezzük cél,és a matematikailag egyenletként vagy egyenlőtlenségként felírt kényszereket nevezzük korlátozások rendszere.

Meghatározás. A célfüggvény és korlátai matematikai kifejezését ún a gazdasági probléma matematikai modellje.

Általában a lineáris programozási (LP) probléma matematikai modelljét a következőképpen írják fel

korlátozásokkal:

Ahol x j- ismeretlen; aij, b i, cj konstansokat kapnak.

A kényszerrendszer összes vagy néhány egyenlete felírható egyenlőtlenségként.

A matematikai modellnek rövidebb jelölésben van a formája

korlátozásokkal:

Meghatározás. Egy lineáris programozási probléma megvalósítható megoldása (terve) egy vektor = ( x 1 , x 2 ,..., x p), a korlátozási rendszer kielégítése.

Az elfogadható megoldások halmaza alkotja az elfogadható megoldások tartományát (ODD).

Meghatározás. Azt a megvalósítható megoldást, amelyben a célfüggvény eléri szélső értékét, a lineáris programozási probléma optimális megoldásának nevezzük, és opt.

Alapvető elfogadható megoldás (X 1 , x 2 ,...,x r , 0, …, 0) egy referenciamegoldás, ahol r- a kényszerrendszer rangja.

Az LP probléma matematikai modellje lehet kanonikus és nem kanonikus.

7. Lineáris programozási feladatok megoldása grafikus módszerrel. Kényszerfüggvények grafikonjai. Szintvonalak.

Grafikus módszer lineáris programozási problémák megoldására

A lineáris programozás legegyszerűbb és leglátványosabb módszere a grafikus módszer. LP-problémák megoldására szolgál két nem kanonikus formában megadott változóval és sok kanonikus formában megadott változóval, feltéve, hogy ezek legfeljebb két szabad változót tartalmaznak.

Geometriai szempontból egy lineáris programozási feladatban olyan sarokpontot vagy egy megengedhető megoldási halmazból olyan ponthalmazt keresünk, amelynél a legmagasabb (alsó) szintvonalat érjük el, amely távolabb (közelebb) helyezkedik el, mint a mások a leggyorsabb növekedés irányába.

Az LP feladatok grafikus megoldásában a célfüggvény szélsőértékének meghatározásához a vektort használjuk L() a felszínen x 1 Ó 2 , amelyet jelölünk . Ez a vektor a célfüggvény leggyorsabb változásának irányát mutatja. Más szóval, a vektor a szintvonal normálja L()

Ahol e 1 és e 2 - egységvektorok a tengelyek mentén ÖKÖR 1 és ÖKÖR 2, ill. így = (∂L/∂x 1 , ∂L/∂х 2 ). A vektorkoordináták a célfüggvény együtthatói L(). A szintvonal kiépítését a gyakorlati feladatok megoldásánál részletesen átgondoljuk.

Problémamegoldó algoritmus

1. Megtaláljuk a megvalósítható megoldások területét a probléma korlátrendszerére.

2. Vektor építése .

3. Rajzolj egy szintvonalat L 0 , amely merőleges .

4. A szintvonalat a vektor irányába mozgatjuk a feladatoknál a maximumig és az ellenkező irányba , minimális feladatokhoz.

A szintvonalat addig mozgatjuk, amíg csak egy közös pontja lesz a megvalósítható megoldások területével. Ez a pont, amely meghatározza az LP probléma egyedi megoldását, lesz a szélsőpont.

Ha kiderül, hogy a szintvonal párhuzamos az ODT egyik oldalával, akkor ebben az esetben a megfelelő oldal minden pontján elérjük az extrémumot, és az LP feladatnak végtelen számú megoldása lesz. Azt mondják, hogy van egy ilyen LP probléma alternatív optimum megoldását pedig a következő képlet adja meg:

ahol 0 ≤ t≤ 1, 1 és 2 - optimális megoldásokat az ODS sarokpontjain.

Egy LP probléma megoldhatatlan lehet, ha az azt meghatározó megszorítások ellentmondásosnak bizonyulnak.

5. Megtaláljuk benne a szélsőpont koordinátáit és a célfüggvény értékét.

3. példa A legjobb termékkiadási lehetőség kiválasztása

A cég 2 féle fagylaltot gyárt: tejszínt és csokoládét. A fagylalt gyártásához két kezdeti terméket használnak: tejet és töltőanyagokat, amelyek 1 kg fagylalt és napi készletek költségeit a táblázat tartalmazza.

A piackutatások kimutatták, hogy a vajfagylalt napi kereslete meghaladja a csokoládéfagylalt keresletét, de legfeljebb 100 kg-mal.

Ráadásul azt is megállapították, hogy a csokoládéfagylalt iránti kereslet nem haladja meg a napi 350 kg-ot. 1 kg krémes fagylalt kiskereskedelmi ára 16 rubel, csokoládé - ​​14 rubel.

Mennyit kell a cégnek az egyes fagylaltfajtákból előállítania, hogy maximalizálja árbevételét?

Megoldás. Jelöli: x 1 - tejszínes fagylalt napi termelési mennyisége, kg; x 2 - csokoládé fagylalt napi kibocsátása, kg.

Készítsük el a probléma matematikai modelljét.

A fagylalt ára ismert: 16 rubel, illetve 14 rubel, tehát a célfüggvény így fog kinézni:

Határozza meg a fagylalthoz használt tej mennyiségét. Felhasználása tejszínes fagylaltnál 0,8 kg, csokoládé fagylaltnál - 0,5 kg. Tejkészlet 400 kg. Ezért az első egyenlőtlenség így fog kinézni:

0,8x 1 + 0,5x 2 ≤400 - az első egyenlőtlenség egy megszorítás. A többi egyenlőtlenség hasonló módon épül fel.

Az eredmény egy egyenlőtlenségek rendszere. mi az egyes egyenlőtlenségek megoldási területe. Ezt úgy tehetjük meg, hogy az O(0:0) pont koordinátáit behelyettesítjük az egyes egyenlőtlenségekbe. Ennek eredményeként a következőket kapjuk:

Ábra OABDEF- az elfogadható megoldások területe. Megszerkesztjük a (16; 14) vektort. szintvonal L 0-t a 16x 1 +14x 2 =Const egyenlet adja meg. Tetszőleges számot választunk, például 0-t, majd 16x 1 +14x 2 =0. Az ábrán az L 0 egyeneshez valamilyen pozitív számot választunk, amely nem egyenlő nullával. Minden szintvonal párhuzamos egymással. A szintvonal normálvektora.

Mozgassa a szintvonalat a vektor irányába. kilépési pont L 0 a megvalósítható megoldások tartományából a lényeg D, koordinátáit az egyenletek által megadott egyenesek metszéspontjaként határozzuk meg:

A rendszert megoldva megkapjuk a pont koordinátáit D(312,5; 300), amelyben lesz optimális megoldás, pl.

Így a cégnek napi 312,5 kg vajas fagylaltot és 300 kg csokoládéfagylaltot kell előállítania, míg az értékesítésből származó bevétel 9200 rubel lesz.

8. Egy tetszőleges lineáris programozási probléma redukálása a fő problémára. Az egyenlőtlenségek által adott kényszerek átalakítása megfelelő egyenletekre.

9.Simplex módszer. A módszer jellemzői, algoritmusa, alkalmazhatósága.

A probléma szimplex módszerrel történő megoldásához szükséges:

1. Jelöljön meg egy módszert az optimális referenciamegoldás megtalálásához!

2. Adja meg az egyik referenciamegoldásból a másikba való átmenet módját, amelyen a célfüggvény értéke közelebb lesz az optimálishoz, i.e. mutasson módot a referenciamegoldás javítására

3. Állítsa be a kritériumokat, amelyek lehetővé teszik, hogy időben leállítsa a referenciamegoldások felsorolását az optimális megoldásra vonatkozóan, vagy következtetést vonjon le az optimális megoldás hiányáról.

A szimplex módszer algoritmusa lineáris programozási problémák megoldására

1. Helyezze a problémát a kanonikus formára

2. Keresse meg a kezdeti támogatási megoldást "egységbázissal" (ha nincs támogatási megoldás, akkor a problémának nincs megoldása, a kényszerrendszer összeférhetetlensége miatt)

3. Számítsa ki a vektorbővülésekre vonatkozó becsléseket a referenciamegoldás alapja alapján, és töltse ki a szimplex módszer táblázatát

4. Ha az optimális megoldás egyediségének kritériuma teljesül, akkor a probléma megoldása véget ér

5. Ha az optimális megoldások halmazának létezésének feltétele teljesül, akkor egyszerű felsorolással minden optimális megoldás megtalálható

10. Szállítási feladat. A közlekedési probléma kezdeti megoldásának meghatározása, típusai, módszerei.

A szállítási probléma az egyik leggyakoribb lineáris programozási probléma. Célja a legracionálisabb áruszállítási módok és eszközök kialakítása, kiküszöbölve a túlzottan nagy távolságú, szembejövő, ismétlődő szállítást.

1. A kiinduló referenciamegoldás megtalálása;

2. A megoldás optimálisságának ellenőrzése;

3. Átmenet egyik alapmegoldásról a másikra.

T10. A lineáris programozási probléma megfogalmazása

matematikai modell A gazdasági probléma a gazdasági folyamatot leíró matematikai összefüggések összessége.

A matematikai modell összeállításához szükséges:

1. feladatváltozók kiválasztása;

2. korlátozási rendszer kidolgozása;

3. állítsa be a célfüggvényt.

Feladatváltozók az x 1 , x 2 ,…, x n mennyiségeket nevezzük, amelyek teljes mértékben jellemzik a gazdasági folyamatot. Általában X \u003d (x 1, x 2, ..., x n) vektorként írják őket.

Feladat kényszerrendszer Olyan egyenletek és egyenlőtlenségek halmaza, amelyeket a probléma változói kielégítenek, és amelyek a korlátozott erőforrásokból és egyéb gazdasági feltételekből, például a változók pozitivitásából következnek. Általában így néznek ki:

A célfüggvényt ún a feladatváltozók F(X) = f(x 1 , x 2 ,…, x n) függvénye, amely a feladat minőségét jellemzi, és amelynek az extrémumát meg kell találni.

A matematikai programozás általános problémája a következőképpen van megfogalmazva: keressük meg azokat az x 1 , x 2 ,…, x n feladatváltozókat, amelyek a célfüggvény szélsőértékét adják

F (X) \u003d f (x 1, x 2, ..., x n) ® max (min) (2)

és kielégíti a kényszerrendszert (1).

Ha a célfüggvény (2) és a kényszerrendszer (1) lineáris, akkor a matematikai programozás problémáját ún. lineáris programozási probléma (LPP).

Az X vektort (feladatváltozók halmazát) hívjuk elfogadható megoldás, vagy a PLP-terv, ha az megfelel a korlátozási rendszernek (1). Egy megvalósítható X tervet, amely a célfüggvény extrémumát adja, hívjuk optimális megoldás ZLP.

2. Példák a gazdasági problémák matematikai modelljeinek összeállítására

A konkrét termelési helyzetek tanulmányozása a ZLP-hez vezet, amelyeket a korlátozott erőforrások optimális felhasználásának problémájaként értelmeznek.

1.Az optimális termelési terv probléma

Kétféle T 1 és T 2 termék előállításához háromféle S 1, S 2, S 3 erőforrást használnak. Az erőforrások készleteit, a termelési egység előállítására fordított erőforrás-egységek számát, valamint a termelési egység értékesítéséből származó nyereséget a táblázat tartalmazza:

Meg kell találni egy olyan tervet a termékek előállítására, amelyekben az értékesítésből származó nyereség maximális lesz.

Megoldás.

Jelöljük x 1, x 2 - a termelésre tervezett termelési egységek számát, rendre T 1 és T 2. Előállításukhoz (x 1 + x 2) egység S 1 erőforrásra, (x 1 + 4x 2) egység S 2 erőforrásra, (x 1) egység S 3 erőforrásra lesz szükség. Az S 1 , S 2 , S 3 erőforrások felhasználása nem haladhatja meg a tartalékaikat, rendre 8, 20 és 5 egységet.

Ekkor a probléma gazdasági-matematikai modellje a következőképpen fogalmazható meg:

Keressen egy X \u003d (x 1, x 2) gyártási tervet, amely megfelel a korlátozási rendszernek:

és a feltétel

amely alatt a funkció a maximális értéket veszi fel.

A probléma könnyen általánosítható arra az esetre, amikor n típusú terméket állítanak elő m típusú erőforrás felhasználásával.

2.Az optimális étrend probléma

Kétféle K 1 és K 2 élelmiszer létezik, amelyek S 1 , S 2 és S 3 tápanyagokat tartalmaznak. Az egyes takarmányfajták 1 kg tápanyagegység-tartalmát, a szükséges tápanyag-minimumot, valamint 1 kg takarmány költségét a táblázat tartalmazza:

Minimális költségű napi adagot kell összeállítani, amelyben az egyes tápanyagfajták tartalma nem lenne kevesebb, mint a megállapított határérték.

Megoldás.

Jelöljük x 1, x 2 - a napi étrendben szereplő K 1 és K 2 takarmány mennyiségét. Ekkor ez a diéta (3x 1 + x 2) egységnyi S 1 tápanyagot, (x 1 + 2x 2) egység S 2 anyagot, (x 1 + 6x 2) egység S 3 tápanyagot tartalmaz. Mivel az étrendben az S 1 , S 2 és S 3 tápanyag tartalma 9, 8 és 12 egység legyen, a probléma gazdasági-matematikai modellje a következőképpen fogalmazható meg:

Állítson össze egy napi étrendet X \u003d (x 1, x 2), amely megfelel a korlátozási rendszernek:

és a feltétel

amely alatt a funkció a minimális értéket veszi fel.

PLP rögzítési űrlapok

Az LLP-ben meg kell találni a lineáris célfüggvény szélsőértékét:

korlátozásokkal:

és a nem negativitás feltétele

ahol a ij , b i , c j ( , ) állandók.

Így van beírva a ZLP Tábornok forma. Ha a kényszerrendszer csak egyenlőtlenségeket tartalmaz, akkor az LLP-t ebben a formában ábrázoljuk alapértelmezett forma. Kanonikus (fő) a ZLP jelölés formája az a jelölés, amikor a kényszerrendszer csak egyenlőségeket tartalmaz. Tehát a fenti LLP-k szabványos formában vannak megírva.

Az LLP általános, szabványos és kanonikus formái egyenértékűek abban az értelemben, hogy egyszerű transzformációk segítségével mindegyik más-más formában átírható. Ez azt jelenti, hogy ha van mód ezen problémák egyikének megoldására, akkor bármelyik problémára meghatározható az optimális terv.

Ahhoz, hogy az LLP egyik jelölési formájáról a másikra válthassunk, képesnek kell lenni arra, hogy az egyenlőtlenség-megszorításoktól az egyenlőség-megszorítások felé haladjunk, és fordítva.

Egy egyenlőtlenségi kényszer (£) egyenlőségi megszorítássá konvertálható, ha egy további nem negatív változót adunk a bal oldalához, és egy egyenlőtlenségi kényszer (³) átalakítható egyenlőségi megszorítássá, ha kivonunk egy további nem negatív változót. bal oldal. A bevezetett további nemnegatív változók száma megegyezik a transzformált egyenlőtlenségi kényszerek számával.

Bemutatott a további változóknak van némi gazdasági értelme. Így, ha az eredeti PLP megszorításai az erőforrások fogyasztását és elérhetőségét tükrözik, akkor a kiegészítő PLP változó értéke kanonikus formában megegyezik a fel nem használt megfelelő erőforrás mennyiségével.

1. példa. Írja be kanonikus ZLP formában:

korlátozásokkal:

Megoldás.

A célfüggvény változatlan marad:

Az egyenlőtlenségek rendszere egyenlőségrendszerré alakul:

Az LLP grafikus módszerrel történő megoldása során a kanonikus formáról a standard formára kell áttérni.

Az LLP szabványos formába állításához használja a Jordan–Gauss módszer SLAU megoldások. Ellentétben a Gauss-módszerrel, amelyben a rendszer kiterjesztett mátrixa lépcsős formára redukálódik, a Jordan-Gauss módszerben a kiterjesztett mátrix részeként identitásmátrixot képeznek. Ezért itt nincs szükség fordított mozgásra.

Az eredeti kanonikus LLP konvertálása egyenértékű szabványos LLP-vé:

a) a kényszerrendszer kiterjesztett mátrixában egy a qp nem nulla elemet választunk. Ezt az elemet ún megengedő, és q - i sor és p-edik oszlop engedélyezési sor és oszlop engedélyezése.

b) a feloldó sztringet változtatás nélkül átírjuk, és a feloldó oszlop minden elemét a feloldó oszlop kivételével nullákra cseréljük. A kiterjesztett mátrix többi elemét a "téglalapszabály" segítségével határozzuk meg:

Tekintsük a kiterjesztett mátrix négy elemét: az átalakítandó a ij elemet, a qp feloldóelemet és az a i p és a qj elemet. Az a ij elem megtalálásához az a ij elemből az következik, hogy ki kell vonni a téglalap ellentétes csúcsaiban található a i p és a qj elemek szorzatát, osztva az a qp feloldóelemmel:

c) a megengedett ismeretlenek egyidejűleg kikerülnek a célfüggvényből. Ehhez a kibővített mátrixba az utolsó sorba írjuk a célfüggvény együtthatóit. A számítások figyelembe veszik, hogy az utolsó sorban lévő engedélyező elem nem választható ki.

2. példa. Váltás szabványos űrlapra:

Megoldás.

A Jordan-Gauss módszerrel az LLP kényszeregyenletrendszerét egy ekvivalens egyenlőtlenség-rendszerbe hozzuk. Feloldó elemnek válasszuk az első sor harmadik elemét:

Az utolsó sor utolsó oszlopában kapott -9 számot az ellenkező előjelű célfüggvénybe kell írni. Az átalakítások eredményeként az LLP a következő formát ölti:

Mert Az x 2 és x 3 változók nem negatívak, akkor ezeket elvetve a ZLP-t szimmetrikus formában írhatjuk fel:

Az LLP kanonikus formájában a célfüggvény minimalizálható és maximalizálható. A maximum megtalálásától a minimum megtalálásáig, vagy fordítva, elegendő a célfüggvény együtthatóinak előjeleit megváltoztatni: F 1 = - F. Az eredményül kapott probléma és az eredeti LLP-nek ugyanaz az optimális megoldása, és a célfüggvények értéke ezen a megoldáson csak abban tér el. jel.

ZLP tulajdonságai

1. Egy lineáris programozási probléma kényszerrendszerének összes megengedhető megoldásának halmaza konvex.

A ponthalmazt ún konvex, ha tartalmazza a halmaz bármely két pontját összekötő teljes szakaszt.

E definíció szerint az 1a. ábrán látható sokszög konvex halmaz, míg az 1b. ábra sokszöge nem, mert a két M és N pontja közötti MN szakasz nem tartozik teljesen ehhez a sokszöghez.

A konvex halmazok nem csak sokszögek lehetnek. Konvex halmazokra példa a kör, szektor, szakasz, kocka, piramis stb.

2. Ha az LLP-nek van optimális megoldása, akkor a lineáris függvény a döntési poliéder egyik sarokpontjában veszi fel a maximális (minimális) értéket. Ha egy lineáris függvény egynél több sarokpontban vesz fel egy maximális (minimális) értéket, akkor bármely olyan pontban veszi fel, amely e pontok konvex lineáris kombinációja.

Az X pontot hívják konvex lineáris kombináció X 1 , X 2 ,…, X n pontok, ha a következő feltételek teljesülnek:

X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,

αj ≥ 0, Σαj = 1.

Nyilvánvaló, hogy n = 2 speciális esetben két pont konvex lineáris kombinációja egy őket összekötő szakasz.

3. A kanonikus LLP kényszerrendszer minden megengedett alapmegoldása megfelel a megoldási poliéder egy sarokpontjának, és fordítva, a megoldási poliéder minden sarokpontjának egy-egy megengedett alapmegoldás.

Az utolsó két tulajdonságból az következik, hogy ha egy LLP-nek van optimális megoldása, akkor az legalább az egyik megengedett alapmegoldással egybeesik.

Így az LLP lineáris függvény extrémumát véges számú megengedhető alapmegoldása között kell keresni.

2. előadás

BAN BEN kanonikus forma

a PLP elfogadható megoldása(elfogadható terv).

az LLP optimális megoldása.

Szükségesség

Példa.

Írjuk be a problémát kanonikus forma

A ZLP grafikus megoldásának speciális helyzetei

Kivéve, ha a feladat az egyetlen optimális megoldás mert és , lehet speciális helyzetek:

1. feladat rendelkezik végtelen számú optimális megoldás – a függvény szélsőpontját a szegmensen érjük el ( alternatív optimum)- 2. ábra;

2. feladat nem megoldható az ODR korlátlansága miatt, vagy - 3. ábra;

3. ODR - egyetlen pont Ah, akkor ;

4. feladat nem megoldható ha az ODR-nek van üres területe.

A

2. ábra 3. ábra

Ha a szintvonal párhuzamos a megvalósítható megoldások területének oldalával, akkor az oldal minden pontján elérjük a szélsőséget. A problémának végtelen számú optimális megoldása van - alternatív optimum . Az optimális megoldást a képlet találja meg

hol van a paraméter. Bármely 0 és 1 közötti értékhez megkaphatja a szegmens összes pontját, amelyek mindegyikére ugyanazt az értéket kapja a függvény. Innen a név – alternatív optimum.

Példa. Oldja meg grafikusan a lineáris programozási feladatot ( alternatív optimum):

Kérdések az önkontrollhoz

1. Írja le általános formában a lineáris programozási feladatot!

2. Írja le a lineáris programozási feladatot kanonikus és szabványos formában!

3. Milyen transzformációkkal léphetünk át a lineáris programozási feladat általános vagy szabványos formájából a kanonikusra?

4. Adja meg a lineáris programozási probléma megvalósítható és optimális megoldásainak definícióját!

5. A megoldások közül melyik a „legjobb” a függvény minimalizálásának problémájára, ha ?

6. A megoldások közül melyik a „legjobb” a függvény maximalizálásának problémájára, ha ?

7. Írja fel egy lineáris programozási feladat két változós matematikai modelljének standard alakját!

8. Hogyan készítsünk két változós lineáris egyenlőtlenséggel adott félsíkot ?

9. Mit nevezünk kétváltozós lineáris egyenlőtlenségrendszer megoldásának? Szerkessze meg a síkon egy olyan lineáris egyenlőtlenség-rendszer megvalósítható megoldásainak tartományát, amely:

1) egyedi megoldása van;

2) végtelen számú megoldása van;

3) nincs megoldása.

10. Írjon egy lineáris függvényre vektor gradiens, nevezze meg a szintvonalak típusát. Hogyan helyezkednek el a gradiens és a szintvonalak egymáshoz képest?

11. Fogalmazzon meg egy grafikus módszer algoritmust két változós szabványos LLP megoldására!

12. Hogyan találjuk meg a megoldás koordinátáit és értékeit?

13. Szerkessze meg a megvalósítható megoldások, gradiens- és szintvonalak területét olyan lineáris programozási problémákhoz, amelyekben:

1) egyetlen ponton éri el, és - az ODR szegmensen;

2) eléri az ODS egyetlen pontját, és .

14. Adja meg az LLP geometriai illusztrációját, ha:

1) egyedi optimális megoldásokkal rendelkezik és ;

2) rendelkezik optimális megoldásokkal a -ra.

2. előadás

grafikus módszer az optimális megoldás megtalálásához

1. Lineáris matematikai modellek formái és transzformációjuk

2. Grafikus módszer lineáris programozási probléma megoldására

3. AZ LLP GRAFIKUS MEGOLDÁSÁNAK KÜLÖNLEGES HELYZETEI

4. Lineáris programozás gazdasági problémáinak grafikus megoldása

Lineáris matematikai modellek formái és transzformációjuk

Egy lineáris programozási probléma (LPP) matematikai modellje háromféle formában írható fel.

BAN BEN a matematikai modell általános formája meg kell találni a célfüggvény maximumát vagy minimumát; a kényszerrendszer egyenlőtlenségeket és egyenleteket tartalmaz; nem minden változó lehet nemnegatív.

BAN BEN kanonikus forma a matematikai modellnek meg kell találnia a célfüggvény maximumát; a kényszerrendszer csak egyenletekből áll; minden változó nem negatív.

A matematikai modell szabványos alakjában meg kell találni egy függvény maximumát vagy minimumát; minden megkötés egyenlőtlenség; minden változó nem negatív.

A kényszerrendszernek a változók nem-negativitásának feltételeit kielégítő megoldását ún. a PLP elfogadható megoldása(elfogadható terv).

A megvalósítható megoldások halmazát ún az LLP megvalósítható megoldásainak területe.

Olyan megvalósítható megoldást nevezünk, amelyben a célfüggvény szélső értéket ér el az LLP optimális megoldása.

Az LLP három formája ekvivalens abban az értelemben, hogy mindegyik más-más formára redukálható matematikai transzformációk segítségével.

Szükségesség átmenet a matematikai modell egyik formájából a másikba problémamegoldó módszerekkel kapcsolatos: például a lineáris programozásban elterjedt szimplex módszert egy kanonikus formában írt feladatra, a grafikus módszert pedig egy matematikai modell standard formájára alkalmazzák.

Áttérés a ZLP kanonikus jelölésre.

Példa.

Írjuk be a problémát kanonikus forma, a kényszerrendszer első egyenlőtlenségének bal oldalába egy plusz (egyenleg) változót vezetve be a „+” jellel, a második egyenlőtlenség bal oldalába pedig egy további „mínusz” jelű változót.

Előfordulhat, hogy a különböző további változók gazdasági jelentése nem azonos: ez attól függ, hogy milyen gazdasági jelentéssel bírnak azok a korlátozások, amelyekben ezek a változók szerepelnek.

Tehát az alapanyag-felhasználás problémájában a nyersanyagok maradékát, az optimális technológiák megválasztásának problémájában pedig egy adott technológia alkalmazásával a vállalkozás kihasználatlan idejét mutatják be; a vágás problémájában - a tervet meghaladó, adott hosszúságú nyersdarabok kiadása stb.

A gazdasági problémák megoldásának alapja a matematikai modell.

matematikai modell A probléma a probléma lényegét leíró matematikai összefüggések összessége.

A matematikai modell elkészítése a következőket tartalmazza:

• feladat változó kiválasztása
• korlátozási rendszer kidolgozása
• célfüggvény kiválasztása

Feladatváltozók X1, X2, Xn mennyiségeknek nevezzük, amelyek teljes mértékben jellemzik a gazdasági folyamatot. Általában vektorként írják fel: X=(X 1 , X 2 ,...,X n).

A korlátozások rendszere A feladatok egyenletek és egyenlőtlenségek halmaza, amelyek leírják a vizsgált probléma korlátozott erőforrásait.

cél funkció feladatot feladatváltozók függvényének nevezzük, amely a feladat minőségét jellemzi, és amelynek extrémumát meg kell találni.

Általában egy lineáris programozási probléma a következőképpen írható fel:

Ez a bejegyzés a következőket jelenti: keresse meg a célfüggvény szélsőértékét (1) és a megfelelő X=(X 1 , X 2 ,...,X n) változókat, feltéve, hogy ezek a változók kielégítik a (2) és nem kényszerrendszert. -negativitási feltételek (3) .

Elfogadható megoldás Egy lineáris programozási feladat (terve) bármely n-dimenziós X=(X 1 , X 2 ,...,X n) vektor, amely kielégíti a kényszerek és a nem-negativitás feltételrendszerét.

A feladatformák megvalósítható megoldásainak (terveknek) összessége megvalósítható megoldások sora(ODR).

Az optimális megoldás Egy lineáris programozási feladat (terv) olyan megvalósítható megoldása (terv), amelyben a célfüggvény egy szélsőséget ér el.

Példa matematikai modell összeállítására

Az erőforrások (nyersanyagok) felhasználásának feladata

Feltétel: n féle termék gyártásához m féle erőforrást használnak fel. Készíts egy matematikai modellt.

Ismert:

• b i (i = 1,2,3,...,m) az egyes i-edik típusú erőforrások tartalékai;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) az egyes i-edik típusú erőforrások egységnyi térfogatú előállítási költsége. a j-edik terméktípus;
• c j (j = 1,2,3,...,n) a j-edik típusú termék térfogategységének értékesítéséből származó nyereség.

Tervet kell készíteni olyan termékek előállítására, amelyek maximális profitot biztosítanak az erőforrások (alapanyagok) adott korlátozása mellett.

Megoldás:

Bevezetjük az X=(X 1 , X 2 ,...,X n) változók vektorát, ahol x j (j = 1,2,...,n) a j-edik típusú termelési volumen. termék.

Az i-edik típusú erőforrás költségei adott mennyiségű x j termék előállításához egyenlőek a ij x j -vel, ezért az erőforrások felhasználásának korlátozása minden típusú termék előállításához a következőképpen alakul:
A j-edik típusú termék értékesítéséből származó nyereség c j x j , tehát a célfüggvény egyenlő:

Válasz- A matematikai modell így néz ki:

Lineáris programozási probléma kanonikus formája

Általános esetben egy lineáris programozási feladatot úgy írnak le, hogy az egyenletek és az egyenlőtlenségek is kényszerek, és a változók lehetnek nem negatívak vagy tetszőlegesen változóak.

Abban az esetben, ha minden megszorítás egyenlet, és minden változó kielégíti a nem-negativitás feltételét, a lineáris programozási feladatot ún. kánoni.

Koordináta, vektor és mátrix jelöléssel ábrázolható.

A kanonikus lineáris programozási probléma koordinátajelölésben a következő formában jelenik meg:

A kanonikus lineáris programozási probléma mátrixjelölésben a következő formában jelenik meg:

• A az egyenletrendszer együtthatóinak mátrixa
• Az X feladatváltozók oszlopmátrixa
• Az Ao a kényszerrendszer jobb oldali részeinek mátrixoszlopa

Gyakran lineáris programozási problémákat használnak, amelyeket szimmetrikusnak neveznek, és amelyek mátrixjelölésben a következő formában vannak:

Általános lineáris programozási probléma redukálása kanonikus formára

A lineáris programozási problémák megoldásának legtöbb módszerében azt feltételezik, hogy a kényszerrendszer egyenletekből és a változók nem-negativitásának természetes feltételeiből áll. A közgazdasági problémák modelljeinek összeállításakor azonban a korlátok főként egyenlőtlenségi rendszer formájában jönnek létre, ezért szükséges, hogy az egyenlőtlenségek rendszeréből egyenletrendszerbe tudjunk lépni.

Ezt így lehet megtenni:

Vegyünk egy a 1 x 1 +a 2 x 2 +...+a n x n ≤b lineáris egyenlőtlenséget, és adjunk a bal oldalához valamilyen x n+1 értéket úgy, hogy az egyenlőtlenség az a 1 x 1 +a 2 x 2 + egyenlőség legyen. ...+a n x n +x n+1 =b. Ráadásul ez az x n+1 érték nem negatív.

Nézzünk meg mindent egy példával.

26.1. példa

Csökkentse a lineáris programozási problémát kanonikus formára:

Megoldás:
Térjünk át a célfüggvény maximumának megtalálásának problémájára.
Ehhez megváltoztatjuk a célfüggvény együtthatóinak előjeleit.
A kényszerrendszer második és harmadik egyenlőtlenségének egyenletté alakításához nemnegatív további változókat vezetünk be x 4 x 5 (ezt a műveletet D betűvel jelöljük a matematikai modellen).
Az x 4 változó a második egyenlőtlenség bal oldalán egy "+" jellel kerül beírásra, mivel az egyenlőtlenség alakja "≤".
Az x 5 változót a harmadik egyenlőtlenség bal oldalán a "-" jellel kell beírni, mivel az egyenlőtlenség "≥" alakú.
Az x 4 x 5 változók együtthatóval kerülnek be a célfüggvénybe. egyenlő nullával.
A problémát kanonikus formában írjuk le.