A legegyszerűbbek az úgynevezett lineáris determinisztikus modellek. Ezeket a vezérlőváltozók lineáris alakjában adják meg ( x):

W = a 0 + a 1 x 1 + … + a k x k

az űrlap lineáris korlátai alatt

b 1 j x 1 + b 2 j x 2 + … + b kj x k ³ bj , j = 1,…, q 1 ;

c 1 j x 1 + c 2 j x 2 + … + c kj x k = cj , j = 1,…, q 2 ;

d 1 j x 1 + d 2 j x 2 + … + d kj x k £ dj , j = 1,…, q 3 .

A korlátozások teljes száma m = q 1 + q 2 + q 3 meghaladhatja a változók számát (m> k). Ezenkívül a változók pozitivitásának feltétele ( x i ³ 0).

A lineáris modell válaszfelülete a hipersík. Vegyünk például egy lineáris kétváltozós modellt a következő formában:

W=–2x 1 –3x 2 (2.2)

az alábbi korlátozások mellett

(2.3)

2x 1 + 3x 2 £18;

x 1 – 4x 2 £4;

–2x 1 + x 2 £2;

x 1³ 0; x 2³ 0.

Érvényes tartomány (a meghatározás hatóköre) OABCD a (2.2) modellhez a (2.3) kényszerek alkotják (2.2. ábra). A válaszfelület egy lapos sokszög OA"B"C"D"(2.2. ábra, b).

Egy bizonyos kényszerreláció esetén a megvalósítható megoldások halmaza hiányozhat (üres). Egy ilyen készletre egy példa látható a ábrán. 2.3. Közvetlen AUÉs nap felülről korlátozza a megengedett értékek tartományát. A harmadik megszorítás levágja az alábbi megengedett értékek tartományát az egyenesből AB.Így nincs olyan közös terület, amely mindhárom feltételnek eleget tenne.

A lineáris modellek meglehetősen egyszerűek, ezért egyrészt a probléma jelentős leegyszerűsítését jelentik, másrészt egyszerű és hatékony megoldási módszerek kidolgozását teszik lehetővé.

A DLA tanulmányozása során a lineáris modelleket ritkán és szinte kizárólagosan alkalmazzák a problémák közelítő leírásában.

A lineáris modellek nemlineáris modellek lépésről lépésre történő közelítésére (a probléma linearizálására) használhatók. Ez a technika különösen hatékony a vizsgált tér kis területeinek tanulmányozásakor. Ennek hátterében a nemlineáris válaszfelület egyes szakaszainak lineáris modellel történő ábrázolása áll nagy csoport optimalizálási módszerek, az ún. lineáris taktikájú módszerek.

A lineáris modellek tanulmányozása nem nehéz. Különösen az egyes változók befolyása az űrlap modelljének jellemzőire

W = a 0 + a 1 x 1 + a 2 x 2 + …+ a k x k

együtthatói adják meg:

, én = 1,…, k.

A lineáris modell optimumának megtalálása W Az opt hatékony szimplex módszert dolgozott ki.

A felmerült költségek halmazának tekintett legegyszerűbb költségmodelleket néha lineárisra redukálják.

Ilyen modell például a klasszikus szállítási költség modell (szállítási probléma)(2.4. ábra).

Elérhető k termelési pontok
(én = 1,…, k) És m fogyasztási pontok
(j = 1,…, m) néhány termék esetében. Az egyesben előállított termék mennyisége k termelési pontok, a i; a szükséges termék mennyisége mindegyikben m fogyasztási pontok, bj.

Feltételezzük a teljes termelés és fogyasztás egyenlőségét:

Innen szállított termék mennyisége én-a gyártási pont j-edik fogyasztási pont, egyenlő xij; a termék egy egységének szállítási költsége - ij-vel.

A szállítás teljes költsége VAL VEL S adott lineáris modell:

az alábbi korlátozások mellett

A lineáris modellek közé tartoznak a lineáris differenciálegyenletek (közönséges vagy parciális deriváltak) formájában megjelenő modellek is.

Lineáris közönséges differenciálegyenlet n a rendelésnek van formája

A kezdeti feltételeket így írjuk

A lineáris parciális differenciálegyenlet alakja

A parciális differenciálegyenletként adott modell kezdeti és peremfeltételeket tartalmaz (feltételeket az F( függvény definíciós tartományának határán). t)).

2.3. A legegyszerűbb matematikai modell tanulmányozása
gázturbinás motor működése

A gázturbinás hajtómű (GTE) a modern repülőgépek fő erőműve.

A GTE-séma az ábrán látható formában van. 2.5.

Itt 1 – bemeneti diffúzor; 2 - kompresszor; 3 - az égéstér; 4 – turbina;
5 - kimeneti fúvóka.

A GTE munkaciklusa a következő szakaszokat tartalmazza:

1) Sebességgel szembejövő V a légáramlás a diffúzoron keresztül belép a kompresszorba.

2) A turbinával ugyanazon a tengelyen forgó kompresszor összenyomja az égéstérbe belépő levegőt.

3) Az égéstérbe folyamatosan üzemanyagot (kerozint) fecskendeznek be, amelyet sűrített levegővel kevernek össze.

4) Az égés során keletkező gáz belép a turbinába, ami azt sebességre gyorsítja W.

5) Ennél a sebességnél a gáz a fúvókán keresztül a légkörbe távozik.

Annak a ténynek köszönhető, hogy a W > V, vonóerő keletkezik R, amely lehetővé teszi, hogy a repülőgép a légkörben repüljön.

A vonóerő megváltoztatása az égéstérbe történő üzemanyag-befecskendezés sebességének változtatásával történik a motorvezérlő gomb (THROT) mozgatásával. A fojtószelep mozgását a fojtószelep bizonyos d szögébe a pilóta manuálisan, vagy egy működtető segítségével hajtja végre az ACS repülés közbeni jelei szerint. A d tolóerő értékének növekedése az erő növekedését okozza R, és a csökkenés ennek az erőnek a csökkenését jelenti.

A GTE összetett műszaki rendszer, amelyben jelentős számú fizikai és kémiai folyamat játszódik le. A motor mindenféle automatizálási eszközzel, turbinalapátok forgatására és hűtésére szolgáló rendszerekkel stb. Természetesen a gázturbinás motor működésének matematikai leírása is meglehetősen nehézkes lesz, beleértve a differenciálegyenlet-rendszereket parciális deriváltokban, közönséges differenciálegyenleteket, transzcendentális függvényeket, algoritmusokat. digitális rendszer motorvezérlő. Az ilyen modelleket a gázturbinás motorok tervezése során használják.

A repülésirányítás problémáinak megoldására több mint egyszerű modell GTE, ami a tolóerő függősége R a fojtószelep fojtószelep-eltérésének d szögétől. A tolóerő megváltoztatásának folyamatát egy szokásos differenciálegyenlet írja le:

, (2.11)

ahol t > 0 a motor időállandója, amely amellett függ tervezési jellemzők a környezeti hőmérsékletre, annak páratartalmára és egyéb külső tényezőkre is; k[kg/deg] – arányossági együttható.

A (2.11) egyenlet kezdeti feltétele így van felírva

R(0) = R 0 . (2.12)

Így a (2.11) egyenlet a (2.12) kezdeti feltétellel együtt az a gázturbinás motor legegyszerűbb matematikai modellje, közönséges differenciálegyenlet formájában 1-edik sorrend.

Az arányossági tényező meghatározásához k a tolóerő fojtószelepek elfordulási szögétől való függésének a kísérleti adatok alapján felépített kalibrációs görbéit alkalmazzuk. A grafikon meredekségének érintője megegyezik a kívánt együtthatóval.

A (2.11) egyenlet és a (2.12) kiindulási feltétel integrálása lehetővé teszi annak megállapítását, hogy a tolóerő hogyan változik az időben (2.6. ábra).

Amikor a fojtószelep el van térítve, a tolóerő R növekszik, majd egy bizonyos határértéknél stabilizálódik, azaz. A GTE egy inerciális objektum.

Tolóerő határ(2.11)-ből kapjuk, ha változásának mértéke nulla:

. (2.13)

Emelkedési idő a t motoridőállandó értékétől függ. A folyamat akkor tekinthető egyenletesnek, amikor t = t száját, amikor a tolóerő a tolóerő határértékének úgynevezett öt százalékos folyosójába kerül (2.6. ábra). Minél nagyobb a t, annál inerciálisabb a motor, és ennek következtében annál több t száj

ábrán. A 2.7 ábra a tolóerő viselkedését mutatja a fojtószelep eltérítési szögétől függően t = 0,5-nél.

A felszállás során fellépő tolóerő, amikor a fojtószelepet 10°-kal eltérítjük, a harmadik másodpercben eléri az állandósult állapotot, és eléri a 3390 kg-os értéket. Tíz másodperccel a felszállás után, amikor a fojtószelepet 20°-kal eltérítik, a tolóerőt 6780 kg-ra, további tíz másodperccel később, amikor a gázkart 30°-kal eltérítik, a tolóerőt 10170 kg-ra állítják. A vonóerő határértéke az
14270 kg.

Hasonló információk.

3.1. Általános feladat lineáris programozás

Lineáris programozás- ez a matematikai programozás legfejlettebb része, melynek segítségével lineáris kapcsolatokkal és megszorításokkal extremális feladatok elemzése és megoldása történik.

A lineáris programozás számos heurisztikus (közelítő) megoldási módszert tartalmaz, amelyek adott feltételek mellett lehetővé teszik az összes lehetőségek gyártási problémák megoldásai a legjobb, optimális kiválasztásához. Ezek a módszerek közé tartoznak a következők: grafikus, szimplex, potenciális módszer (módosított elosztási módszer - MOD), Khichkov, Kreko, Vogel közelítési módszer és mások.

Ezen módszerek némelyikét egy közös név egyesíti - az elosztási vagy szállítási módszer.

A lineáris programozás szülőhelye Oroszország. Az első munkák a lineáris programozásról a leendő akadémikus L.V. Kantorovich 1939-ben jelent meg. 1975-ben közgazdasági Nobel-díjat kapott a lineáris programozási módszerek fejlesztéséért. Mivel L.V. akadémikus munkáinak többsége. Kantorovich elkötelezett a közlekedési problémák megoldásában, úgy tekinthetjük, hogy az említett Nobel-díj az orosz közlekedéstudomány érdemeit is jelzi.

A közúti szállításban a lineáris programozási módszereket az 1960-as évek óta alkalmazzák számos legfontosabb termelési probléma megoldására, nevezetesen: a teherszállítás távolságának csökkentése; optimális szállítási terv elkészítése; a legrövidebb mozgási útvonalak kiválasztása; különböző, de felcserélhető rakományok szállításának feladatai; műszakos napi tervezés; kis tételes rakományok szállításának tervezése; buszok elosztása útvonalak mentén és mások.

A lineáris programozási modell jellemzői a következők:

A célfüggvény és a megszorítások kifejezésre kerülnek lineáris függőségek(egyenlőségek vagy egyenlőtlenségek);

A függőségek száma mindig kevesebb, mint az ismeretlenek száma (bizonytalansági feltétel);

A szükséges változók nem-negativitása. A lineáris programozási modell rövidített formában történő megírásának általános formája a következő:

megtalálja x ij ≥ 0 (j = 1, 2…n) a következő típusú megszorítások mellett:

Ezek a megszorítások minimalizálják (vagy maximalizálják) a célfüggvényt

A lineáris programozási modell megírásának szabványos formája egy lineáris egyenletrendszer, amelybe be van írva kánoni formában, azaz lineáris egyenlőségek formájában, nem negatív számokban:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n \u003d b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n \u003d b 2 ; (3.1)

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

a m x 1 + a m 2 x 2 + ...+ a mn x n = b m ..

Ha a modellt nemnegatív számok egyenlőtlenségei formájában írjuk fel, azaz ilyen alakja van

a 11 x 1 + a 12 x 2 + ... + a 1 n x n ≤ b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)

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

a m x 1 + a m 2 x 2 + …+ a mn x n ≤ b m ,..

akkor ez a bejegyzés a következőre redukálódik kánoni forma (3.1) további változók bevezetésével x n +1> 0 (én=1,2…m) az egyenlőtlenség bal oldalára (vagy a változók számának csökkentésére, ha az egyenlőtlenség elője ellentétes irányba mutat). További változók képezik az alapot.

A lineáris programozási probléma megoldásának standard formája az, hogy olyan nemnegatív számokból álló lineáris egyenletrendszerre keressünk megoldást, amely minimalizálja a célfüggvényt. A célfüggvénynek ekkor van formája

L = c 1 x 1 + c 2 x 2 ... c n x n → perc, (3,3)

Ahol s 1 , s 2 … s n célfüggvény-együtthatók L változókkal x j .

További változók nulla együtthatóval lépnek be a célfüggvénybe.

A célfüggvény maximalizálása esetén L a célfüggvény változóinak előjeleit meg kell fordítani, és ismét eljutunk a minimalizálási problémához, ti. az egyik feladat egy másik helyettesítésre redukálódik L tovább - L vagy max L=min(- L).

A lineáris egyenletrendszer (3.1) alapmegoldása egy olyan megoldás, amelyben a nem alapváltozók nulla értéket kapnak.

Megengedhetőnek nevezzük azt az alapmegoldást, amelyben a bázisban szereplő változók nem negatívak.

Optimálisnak nevezzük azt az elfogadható megoldást, amely maximalizálja (vagy minimalizálja) a célfüggvényt (3.3).

Minden lineáris programozási probléma megfelel egy másiknak, amelyet duális lineáris programozási feladatnak neveznek. A kettősre vonatkozó eredeti problémát direkt problémának nevezzük. Az elsődleges és a duális problémák egy párt alkotnak, amelyet a lineáris programozásban duális párnak neveznek. A primál és a duális pár aszimmetrikus párt alkot, ha a primálprobléma kanonikus formában van felírva, és szimmetrikus párt, ha a feladatok feltételeit egyenlőtlenségként írjuk fel.

A duális probléma matematikai modelljének összeállításának szabályai a mátrixszámítás szabályain alapulnak.

A kettősség fogalmát széles körben használják a lineáris programozási problémák elemzésében. A kettősség tulajdonságát minden esetben részletesen megvizsgáljuk.

3.2. Grafikus-analitikai módszer

A gráf-analitikai módszer a lineáris programozás egyik legegyszerűbb módszere. Világosan feltárja a lineáris programozás lényegét, geometriai értelmezését. Hátránya, hogy 2 vagy 3 ismeretlennel is megoldható a probléma, vagyis a problémák szűk körére alkalmazható. A módszer az analitikus geometria szabályain alapul.

Probléma megoldása két változóval x 1És x 2, amely a feladat jelentése szerint nem lehet negatív, a derékszögű koordináták rendszerében kerül végrehajtásra. Egyenletek x 1=0 és x 2= 0 az első kvadráns koordinátarendszerének tengelyei

Tekintsük a megoldási módot egy konkrét példa segítségével.

Példa 3.1. Raktáron 300 tonna habbeton termék és 200 tonna acéltermék van. Az autóipari vállalkozásnak ezeket a termékeket az épülő létesítménybe kell szállítania. Az autógyártó cég kamatok KAMAZ - 5320 és

ZIL-4314. Egy útra a KamAZ-5320 6 tonna habbetont és 2 tonna acélt tud szállítani, és az utazás nyeresége 4 ezer rubel lesz. A ZIL-4314 2 tonna habbetont és 4 tonna acélt szállít egy út során, az utazásból származó haszon 6 ezer rubel. A szállítást úgy kell megszervezni, hogy az autóipari vállalkozás a legnagyobb profitot biztosítsa.

Szerkesszük meg a probléma matematikai modelljét. Jelölje x 1-gyel a KamAZ-5320 és azon keresztül történő utazások kívánt számát x 2 szükséges számú ZIL-4314 lovas.

A habbeton termékek teljes szállítása tonnában 6 x 1+ 2x 2, és acélból 2 x 1+ 4x 2. A szállítási limit a rendelkezésre álló tételek száma alapján 6 x 1+ 2x 2 ≤ 300t habbetonnál és 2 x 1+ 4x 2 ≤ 200t acélhoz.

Teljes nyereség ezer rubelben. 4-ként kifejezve x 1 + 6x 2 , amelyet maximalizálni kell, és amely a vizsgált probléma optimálissági kritériuma. A probléma matematikai modellje tehát a következőképpen néz ki. Szükséges a célfüggvény maximalizálása

L = 4x 1+ 6x 2 → Max feltételek mellett: 6 x 1+ 2x 2 ≤ 300; 2x 1+ 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.

Tekintsük a 6. egyenletet x 1+ 2x 2 = 300. Az egyenlettel leírt egyenes megszerkesztéséhez két pontot találunk ezen az egyenesen. Nál nél x 1= 0 egy egyenes egyenletéből 2-t találunk x 2 = 300, ahonnan x 2 \u003d 150. Ezért az A pont koordinátákkal (0,150) a kívánt egyenesen fekszik. Nál nél x 2= 0 nálunk 6 van x 1\u003d 300, ahonnan x 1 \u003d 50, és a pont D koordinátákkal (50,0) is a kívánt vonalon van. Húzzon egy vonalat ezen a két ponton keresztül HIRDETÉS(3.1. ábra).

Lineáris egyenlőtlenség 6 x 1+ 2x 2 ≤ A 300 egy félsík, amely az épített 6-os vonal egyik oldalán helyezkedik el x 1+ 2x 2 = 300. Annak megállapításához, hogy ennek az egyenesnek melyik oldalán helyezkednek el a kívánt félsík pontjai, behelyettesítjük a 6-os egyenlőtlenségbe x 1+ 2x 2 ≤ Valamelyik pont 300 koordinátája, amely nem esik a határvonalon. Például az origó 0-(0,0). Kielégíti a 6∙0 + 2∙0 = 0 egyenlőtlenséget< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой HIRDETÉSábrán pedig. 3.1 árnyékolt.

2. egyenlet x 1+ 4x 2= 200 két pontból lesz megszerkesztve. Nál nél x 1 = 0 4x 2 = 200 honnan x 2 = 50. Majd pont E koordinátái (0,50) vannak, és a szükséges sorhoz tartozik. Nál nél x 2= 0, 2x 2 = 200 pont Val vel az adott egyenesen van koordinátákkal (100,0). Az egyenlőtlenségbe behelyettesítve a pont koordinátáit Val vel(0,0), azt kapjuk, hogy 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

A feladatkényszer rendszer megköveteli, hogy a tervek ( x 1; x 2) teljesíti mind a négy egyenlőtlenséget, azaz az elfogadható tervek pontok ( x 1; x 2) egyidejűleg mind a négy félsíkban kell lennie. Ennek a követelménynek csak a poligon belsejében és határán elhelyezkedő pontok felelnek meg. OEKD, amely a megengedett megoldások sokszöge.

A megvalósítható megoldások sokszögének csúcsai a pontok O, E, K, D vonalszakaszok OE, EK, KD, OD- a bordáit. A sokszög bármely pontja OEKD a feladat terve, amely minden feltételnek eleget tesz. A sokszög csúcsai két egyenes metszéspontjából jönnek létre, és megfelelnek a feladat alapterveinek, amelyek között a legjobb (optimális) terv található. Így annyi referenciaterv lesz, ahány csúcs van a megvalósítható megoldások sokszögében.

A célfüggvényhez vizuális geometriai ábrázolást is kaphatunk L = 4x 1+ 6x 2. Rögzítjük például a célfüggvény valamely értékét L= 120. 4. egyenlet x 1+ 6x 2 = A 120 egy ponton átmenő egyenest határoz meg BAN BEN koordinátákkal (x 1 \u003d 0; x 2 \u003d 20) és egy ponttal L koordinátákkal (( x 1 = 30; x 2 = 0). Vonalszakasz BL a sokszög belsejében fekszik OEKD. Ezért ennek a szegmensnek az összes tervére (pontjára) a célfüggvény értéke azonos és egyenlő 120-zal. A célfüggvény egyéb értékeinek megadásával párhuzamos egyeneseket kapunk, amelyeket ún. szintvonalak cél funkció.

A vonal mozgatása Lönmagával párhuzamosan az egyik irányban növekedést kapunk a célfüggvényben, ellenkező irányban pedig csökkenését. Ebben a példában egy egyenes vonal mozgása BL jobbra határozza meg az általunk maximalizált célfüggvény növekedését. Ezt a sorig csináljuk BL legalább egy közös pontja lesz az elfogadható megoldások sokszögével OEKD. ábrából. 3.1 ebből következik, hogy az utolsó pont, amelyet a célfüggvény szintjének egyenese metszi, az lesz a pont NAK NEK. Ez azt jelenti, hogy a lényeg NAK NEK meghatározza az optimális feladattervet.

A szintvonalra merőleges növekedési irányt ún legnagyobb növekedés iránya célfüggvény, és meghatározza annak maximális nyereségét. Ez az irány szintvonalak húzása nélkül állítható be. Ehhez a tengelyeken szükséges x 1És x 2 tegyünk félre a célfüggvény együtthatóival egyenlő szegmenseket, és ezek felhasználásával, mint a koordinátákkal, alkossuk meg a célfüggvény legnagyobb növekedésének vektorát. A matematikában úgy hívják gradiensés a grad jellel jelöljük. Gradiens egy tereptárgyhoz L = 4x1 + 6x2 akarat vektor n| 4; 6 | . Felépítésének kényelme érdekében a koordinátákat például 10-szeresére növeljük, pl. n | 40; 60 | . Szerkesszük meg a célfüggvény gradiensét L, melyhez a (40; 60) koordinátájú pontot összekötjük az origóval. A célfüggvény szintvonalait a gradiens irányára merőlegesen húzzuk meg.

Így vagy úgy, hogy a lényeg NAK NEK meghatározza az optimális feladattervet, melynek változóinak értékei megfelelnek az adott pont koordinátáinak. A koordináták meghatározásához meg kell oldani az ezt a csúcsot alkotó egyenesek egyenletrendszerét:

6x 1+ 2x 2= 300;

2x 1+ 4x 2= 200.

Kiegyenlítjük az együtthatókat x 1-nél úgy, hogy a második egyenletet megszorozzuk 3-mal, és kivonjuk az elsőt a második egyenletből. Vegyünk 10-et x 2= 300,x 2 = 30. Az x 2 \u003d 30 értéket behelyettesítve bármelyik egyenletbe, például az elsőbe, meghatározzuk az értéket x 1:

6x 1+ 2X · 30 = 300,

honnan 6 x 1 = 300 - 60 = 240, ezért x 1 = 40.

Így ahhoz, hogy egy autógyártó cég a legtöbb profitot elérje, 40 utazást kell teljesítenie a KamAZ-5320-hoz és 30 utazást a ZIL-4314-hez. A maximális nyereség ebben az esetben lesz

L = 4x 1+ 6x 2\u003d 4 40 + 6 30 \u003d 340 ezer rubel.

A vizsgált példa és a két változós optimalizálási feladat geometriai értelmezése alapján a következő következtetéseket vonhatjuk le:

1) a kétdimenziós térben a megvalósítható megoldások területe egy sokszög;

2) a sokszög minden oldala egy nullával egyenlő változó értékének felel meg;

3) az elfogadható megoldások sokszögének minden csúcsa két nullával egyenlő változó értékének felel meg;

4) a célfüggvény minden értéke egy egyenesnek felel meg;

5) a feladat optimális megoldása annak a sokszögnek a csúcsának felel meg, amelyben a célfüggvény az optimális értéket kapja, míg az optimális változók ennek a csúcsnak a koordinátái.

Általános esetben az optimalizálási feladatoknak hasonló geometriai értelmezése van. A feladattervek halmaza egy poliéder lesz, amelynek csúcsai megfelelnek a referenciaterveknek. A feladat megoldása során a poliéder egyik csúcsából a másikba való átmenetet nagy célfüggvény értékkel végezzük, amíg el nem érjük annak optimális értékét. Vegyük észre, hogy az optimalizálási módszerek hatékonysága éppen abban rejlik, hogy a csúcsok felsorolása (iteráció) csak a célfüggvény legnagyobb növekedésének irányában történik. Ezért nem veszik figyelembe az összes csúcsot, amelyekből nagyon sok van, hanem csak azokat, amelyek közelebb vannak a szélsőhöz.

Az optimalizálási feladatok osztályának meghatározásakor és a megoldási módszer kiválasztásánál tudni kell, hogy a megvalósítható megoldások halmaza konvex vagy nem konvex, lineáris vagy nemlineáris célfüggvény.

Definíció szerint egy halmazt ún konvex ha bármely két pontra az ezeket a pontokat összekötő teljes szakasz ebbe a halmazba tartozik. Konvex halmazok például egy szakasz (3.2. ábra, a), egy kör alakú sík, egy kocka, egy paralelepipedon, valamint olyan sokszögek, amelyek mindegyik oldalának egy-egy oldalán helyezkednek el. stb.

ábrán. A 3.2b nem konvex halmazokat mutat. A nem konvex halmazokban az AB szakasz legalább két olyan pontja jelezhető, amelyek nem tartoznak a vizsgált halmazhoz.

3.3. Simplex módszer

Simplex módszer egy általános módszer a lineáris programozási problémák megoldására. A módszer a nevét a "simplex" szóból kapta, amely a legegyszerűbb konvex sokszöget jelöli, amelynek csúcsainak száma mindig eggyel több, mint a tér mérete. A szimplex módszert J. Dantzig matematikus fejlesztette ki az USA-ban az 1940-es évek végén.

A szimplex módszer magában foglalja a (3.1) típusú kanonikus lineáris egyenletrendszer nem negatív alapmegoldásának megszerzését, a célfüggvény (3.3) utólagos minimalizálását (maximalizálását), és ily módon a célfüggvény optimális értékeinek megtalálását. szükséges változók x 1, x 2… x n.

A szimplex módszer ötlete abban rejlik, hogy a számítás során az első alapmegoldástól sorban haladunk át a második, harmadik stb. keresztül az ún szimplexátalakulások. Az átalakítások szimplex táblák formájában készülnek, ami nagyban leegyszerűsíti és felgyorsítja a számításokat.

Egy lineáris egyenletrendszer nemnegatív alapmegoldásának megszerzéséhez az ismeretlenek kiküszöbölésének folyamatát úgy kell végrehajtani, hogy az egyenletek szabad tagjai a folyamat minden szakaszában nem negatívak maradjanak. Ebben az esetben a következő szabályt kell követni: minden szabad változót, amelyhez legalább egy pozitív együttható van, új alapváltozónak vesszük; a bázisból egy változót származtatunk, amely megfelel az egyenletek szabad tagjainak legkisebb arányának az egyenletek megfelelő pozitív együtthatóihoz a bázisba bevitt változóval. Az ilyen transzformációkat ún szimplex konverterek.

Ez nagyon fontos, mert ahhoz, hogy egy adott nemnegatív megoldást találjunk, amely egy szabad változó lehető legnagyobb értékének felel meg más szabad változók nulla értékével, ahelyett, hogy meghatároznánk a megadott változó tartományát, és a legnagyobbat helyettesítenék. lehetséges értéket be közös döntés Elegendő ezt a változót alapváltozónak venni, és a rendszert szimplex transzformációnak alávetni, új bázisra lépni, ami nagymértékben leegyszerűsíti a számításokat.

A számítások kényelmesen elvégezhetők szimplex táblázatok segítségével. Az egyik táblából a másikba való átmenet egy iterációnak felel meg, vagyis az egyik bázisról a másikra való átmenetnek, miközben a célfüggvény értéke csökken. Bizonyos számú iterációnál átmennek arra az alapra, amelyre a célfüggvény optimális (minimális vagy maximális) értékét megkapjuk. Tekintsük a szimplex módszert általános formában.

A lineáris programozás általános feladata a célfüggvény minimalizálása (maximalizálása), amelynek változóit lineáris egyenletrendszer köti össze, figyelemmel a nem-negativitás feltételére.

Legyen szükséges a lineáris forma minimalizálása

L = c 1 x 1 + c 2 x 2 + ... c n x n.

A következő feltételek mellett (az egyértelműség kedvéért a nulla és az egység együtthatókat az egyenletekben megtartjuk):

1x 1+ 0x 2 + ... 0x m + a 1m+ 1x m+1 ... + a 1n x n \u003d b 1;

0x 1+ 1x 2+… 0x m + a 2m+ 1x m+1 ... + a 2n x n \u003d b 2;

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

0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n \u003d b m.

Ennek az egyenletrendszernek már kész alapja van, hiszen minden kényszeregyenlet eggyel egyenlő együtthatójú ismeretlent tartalmaz, ami más egyenletekben, azaz a változók együtthatóiból nincs meg. x 1 , x 2 …, x m létrehozhat egy identitásmátrixot.

Oldjuk meg az alapváltozók egyenleteit:

x 1 \u003d b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);

x 2 \u003d b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

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

x m \u003d b m - (a mm + 1x m + 1 ... + a mn x n),

és a célfüggvényt szabad változókkal fejezzük ki, behelyettesítve abba az alapváltozók helyett azok szabad változókkal való kifejezéseit:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1 m +c 2 a 2 m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Változók x 1, x 2 ..., x m, amelyek segítségével az első alapterv megtalálható, az alap, a többi x m +1 , x m +2 ,…x n – ingyenes. Mindig annyi alapváltozónak kell lennie, ahány egyenlet van a rendszerben. A nem negativitás feltétele alapján a szabad változók legkisebb értéke nulla. Az egyenletrendszer eredő alapmegoldása annak kezdeti megvalósítható megoldása, azaz. x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, x n = 0.

Ez a megoldás megfelel a célfüggvény értékének

L = c 1 b 1 + c 2 b 2 + ... c m b m.

A kezdeti megoldás optimálisságát ellenőrizzük. Ha nem optimális, akkor a bázisba szabad változókat bevezetve a következő megvalósítható megoldásokat találjuk a célfüggvény kisebb értékével. Ehhez meg kell határozni egy szabad változót, amelyet be kell írni a bázisba, valamint egy változót, amelyet el kell távolítani a bázisból. Ezután az előző rendszerről a következő egyenértékű rendszerre lépnek át. Ez szimplex táblák segítségével történik. A feladat megoldása addig folytatódik, amíg a célfüggvény optimális értékét meg nem kapjuk.

A szimplex táblákat a következőképpen állítjuk össze (lásd a 3.1. táblázatot). Helyezzen minden változót a táblázat tetejére! x 1 , x 2 …, x nés együtthatók cj, amellyel a megfelelő változók szerepelnek a célfüggvényben. Első oszlop c i a bázisban szereplő változókra vonatkozó célfüggvény együtthatójából áll. Ezt követi az alapváltozók oszlopa és az egyenletek szabad tagjai. A táblázat többi oszlopának elemei azoknak a változóknak az együtthatói, amelyekkel az utóbbiak belépnek az egyenletrendszerbe. Így a táblázat minden sora megfelel a rendszer egyenletének, az alapváltozóra tekintettel megoldva. A táblázatban a terv egy olyan változata is látható, amely adott alapon megfelel a célfüggvénynek.

A táblázat alsó sorát ún index. Minden eleme (becslés) ∆ j meghatározni

∆j = z j – c j ,

Ahol cj a célfüggvény megfelelő változóinak együtthatói; zj – a célfüggvény alapváltozókkal és a megfelelő változókkal - elemek szorzatainak összege j- táblázat oszlopa.

asztal 3.1

Szimplex táblázat érvényes kezdőbetűvel

1.

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

A matematikai modellek lehetővé teszik az ismeretlen paraméterek optimális értékeinek meghatározását gazdasági rendszerek 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. Matematikai modellezés a legtökéletesebb és egyben leghatékonyabb módszer a vizsgált tárgyról 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 fejleszt 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 szakasz olyan feladatokat tartalmaz, amelyek véletlen változókat tartalmaznak 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. Matematikai modellek gazdasági folyamatok a jelenségeket pedig közgazdasági és matematikai modelleknek nevezzük

A modellek a következőkre oszthatók:

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. Matematikailag az optimális megoldás meghatározása sok változó függvényének szélsőértékének (max vagy min) meghatározá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 :

Bemutatjuk a jelölést paraméterek beállítása:

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ékei, az egyes típusok különböző vágási lehetőségekkel kapott nyersdarabjainak száma (aij), valamint az értékek hulladék (Cj) mennyiségét határozzák meg.

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ó. Az ismeretlen változók értékeit, amelyek kielégítik a lineáris programozási probléma összes megkötését, az ún. 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 bármely két ponthoz tartozó ponttal együtt adott készlet, egy őket összekötő szegmenst 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. Minden egyes sarokpont Az ODZ az alapterv.

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ásra kerül.

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< Ө ≤ . Adott sor engedélyezési karakterláncnak nevezik.

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 valamely  j vektorára

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 nevezzük 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 akkor negatív és nulla adott vektor beszámítható az alapba. 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 jelöljük latin betű M. Egyenlőnek tekinthető +∞-val. 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. töltse ki az első szimplex táblát a szokásos módon, függetlenül a szabad tagok előjeleitől. Ú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 beszá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 a „-” jel el nem kerül abban 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 egy 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). Hagyja, hogy egy kedvezőtlen cella igényt tartson a Q termékre. A táblázat egyensúlyhiányának elkerülése érdekében a cikluson keresztüli átmenetekben 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 el a jelölt cellából, Q jószágokat 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. Ismerjük meg a j típusú termék cj egységköltségét (j=1,n) és az i-edik erőforrás felhasználási arányát (i=1,m) a termeléshez j-edik egységek termékek - 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.

Ahhoz, hogy egy kettős feladatpár megvalósítható megoldása optimális legyen, szükséges és elegendő a következő feltétel teljesülése: 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 xj- 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/∂х 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. Fogyasztása krémfagylaltná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.

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) megoldásainak végtelen halmaza 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 algoritmust egy grafikus módszerhez 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 széles körben használt 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, egy plusz (egyenleg) változót vezet be a „+” jellel a kényszerrendszer első egyenlőtlenségének bal oldalába, és egy további „mínusz” jelű változót a második egyenlőtlenség bal oldalába.

Előfordulhat, hogy a különféle 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 kiválasztásának problémájában pedig a vállalkozás kihasználatlan idejét mutatják meg egy-egy technológiával; a vágás problémájában - a tervet meghaladó, adott hosszúságú nyersdarabok kiadása stb.