Statisztikai eloszlási sorozatok és jellemzőik. Statisztikai eloszlássorok, jelentésük és alkalmazása a statisztikában

3. előadás. Simplex táblázatok. A szimplex módszer algoritmusa.

§ 3 EGYSZERŰ MÓDSZER

3.1. A szimplex módszer általános ötlete. Geometriai értelmezés

A grafikus módszer a problémák nagyon szűk csoportjára alkalmazható lineáris programozás: hatékonyan képes megoldani a legfeljebb két változót tartalmazó problémákat. Figyelembe vették a lineáris programozás alaptételeit, amelyekből az következik, hogy ha egy lineáris programozási feladatnak van optimális megoldása, akkor az megfelel a megoldási poliéder legalább egy sarokpontjának, és egybeesik a megoldási poliéder legalább egyik megengedett alapmegoldásával. korlátok rendszere. Bármilyen lineáris programozási probléma megoldásának módját jelezték: felsorolás végső szám a kényszerrendszer elfogadható alapmegoldásait, és válassza ki közülük azt, amelyre a célfüggvény az optimális megoldást adja. Geometriailag ez megfelel a megoldási poliéder összes sarokpontjának számbavételének. Egy ilyen kimerítő keresés végső soron optimális megoldáshoz vezet (ha létezik), de gyakorlati megvalósítása óriási nehézségekkel jár, hiszen a valós problémák esetében a megvalósítható alapmegoldások száma, bár véges, rendkívül nagy lehet.

A keresendő megengedhető alapmegoldások száma csökkenthető, ha a keresést nem véletlenszerűen, hanem a lineáris függvény változásait figyelembe véve, pl. biztosítva, hogy mindenki következő megoldás„jobb” (vagy legalábbis „nem rosszabb”) volt, mint az előző, a lineáris függvény értékei szerint (növelve a maximum megtalálásakor, csökkentve a minimum megtalálásakor
). Ez a keresés lehetővé teszi, hogy csökkentse a lépések számát, amikor megtalálja az optimálisat. Magyarázzuk meg ezt egy grafikus példával.

Legyen a megvalósítható megoldások tartománya sokszöggel ábrázolva ABCDE. Tegyük fel, hogy a sarokpontja A megfelel az eredeti megvalósítható alapmegoldásnak. Véletlenszerű keresésnél öt elfogadható alapmegoldást kell kipróbálni, amelyek ötnek felelnek meg sarokpontok poligon. A rajzból azonban jól látszik, hogy a felső után A jövedelmező elmenni szomszédos csúcs BAN BEN, majd az optimális pontig VAL VEL.Öt helyett csak három csúcson mentünk keresztül, következetesen javítva a lineáris függvényt.

A megoldás egymás utáni javításának ötlete egy univerzális módszer alapját képezte a lineáris programozási problémák megoldására - szimplex módszer vagy a terv szekvenciális javításának módszere.

A szimplex módszer geometriai jelentése a kényszerpoliéder egyik csúcsából (amelyet kezdeti csúcsnak nevezünk) szekvenciális átmenetből áll a szomszédosba, amelyben a lineáris függvény a legjobb (legalábbis nem a legrosszabb) értéket veszi fel a korláthoz képest. a probléma célja; az optimális megoldás megtalálásáig - az a csúcs, ahol a célfüggvény optimális értékét elérjük (ha a feladatnak van végső optimuma).

A szimplex módszert először J. Danzig amerikai tudós javasolta 1949-ben, de még 1939-ben a módszer ötleteit L. V. orosz tudós dolgozta ki. Kantorovics.

A szimplex módszer, amely lehetővé teszi bármely lineáris programozási probléma megoldását, univerzális. Jelenleg számítógépes számításokhoz használják, de a szimplex módszerrel egyszerű példák kézzel is megoldhatók.

A szimplex módszer - a megoldás szekvenciális javítása - megvalósításához elsajátításra van szükség három fő elem:

módszer egy probléma kezdeti megvalósítható alapvető megoldásának meghatározására;

a legjobb (pontosabban, nem rosszabb) megoldásra való áttérés szabálya;

kritérium a talált megoldás optimálisságának ellenőrzésére.

A szimplex módszer használatához a lineáris programozási problémát le kell redukálni kanonikus forma, azaz a kényszerrendszert egyenletek formájában kell bemutatni.

A szakirodalom kellő részletességgel ismerteti: a kezdeti támogatási terv (kezdetben elfogadható alapmegoldás) megkeresése, mesterséges bázis módszer alkalmazása is, az optimális támogatási terv megtalálása, a feladatok megoldása szimplex táblák segítségével.

3.2. A szimplex módszer algoritmusa.

Tekintsük a ZLP szimplex módszerrel történő megoldását, és mutassuk be a maximalizálási probléma kapcsán.

1. A feladat feltételei alapján összeállítjuk annak matematikai modelljét.

2. Az elkészült modellt kanonikus formára konvertáljuk. Ebben az esetben egy kezdeti referenciatervvel rendelkező alapot lehet azonosítani.

3. A probléma kanonikus modelljét szimplex tábla formájában írjuk fel úgy, hogy minden szabad tag nem negatív. Ha a kezdeti referenciaterv van kiválasztva, folytassa az 5. lépéssel.

Szimplex tábla: egy kényszeregyenletrendszert és egy célfüggvényt a kezdeti alaphoz képest feloldott kifejezések formájában kell megadni. Az együtthatókat tartalmazó sor objektív funkció
, hívott
– egy karakterlánc vagy a célfüggvény karakterlánca.

4. Keresse meg a kezdeti referenciatervet szimplex transzformációk végrehajtásával a minimális szimplex relációknak megfelelő pozitív feloldó elemekkel, anélkül, hogy figyelembe venné az elemek előjeleit.
– vonalak. Ha a transzformációk során egy 0 sorral találkozunk, amelynek a szabad tag kivételével minden eleme nulla, akkor a probléma kényszeregyenletrendszere inkonzisztens. Ha olyan 0 sorral találkozunk, amelyben a szabad tagon kívül nincs más pozitív elem, akkor a restriktív egyenletrendszernek nincsenek nemnegatív megoldásai.

A (2.55), (2.56) rendszer redukcióját új alapra hívjuk szimplex transzformáció . Ha egy szimplex transzformációt formális algebrai műveletnek tekintünk, akkor észrevehető, hogy a művelet eredményeként a szerepek újraelosztásra kerülnek egy bizonyos rendszerben lévő két változó között. lineáris függvények: az egyik változó függőről függetlenre, a másik pedig, ellenkezőleg, függetlenről függőre. Ez a művelet az algebrában ún Jordan kieső lépés.

5. A talált kezdeti támogatási tervet megvizsgáljuk az optimálisság szempontjából:

a) ha bent van
– nincs negatív elem a sorban (nem számítva a szabad futamidőt), akkor a terv optimális. Ha nincsenek nullák, akkor csak egy optimális terv van; ha van legalább egy nulla, akkor végtelen sok optimális terv van;

b) ha c
– legalább egy negatív elem van a sorban, amely nem pozitív elemek oszlopának felel meg, akkor
;

c) ha benne van
– a sorban van legalább egy negatív elem, az oszlopában pedig legalább egy pozitív elem, akkor át lehet lépni egy új, az optimálishoz közelebbi referenciatervre. Ehhez a megadott oszlopot feloldó oszlopnak kell kijelölni, a minimális szimplex arány segítségével meg kell keresni a feloldó sort és végrehajtani egy szimplex transzformációt. Az így kapott referenciatervet ismét megvizsgáljuk az optimálisság szempontjából. A leírt folyamatot addig ismételjük, amíg el nem születik egy optimális terv, vagy amíg a probléma megoldhatatlansága meg nem állapítható.

A bázisban szereplő változó együtthatók oszlopát feloldásnak nevezzük. Így a bázisba bevitt változó kiválasztása (vagy egy feloldó oszlop kiválasztása) a negatív elem által
-strings, növelő funkciót biztosítunk
.

Kicsit nehezebb meghatározni a bázisból kizárandó változót. Erre valók a kapcsolatok ingyenes tagok a feloldó oszlop pozitív elemeire (az ilyen kapcsolatokat szimplexnek nevezzük), és keressük meg közülük a legkisebbet, amely meghatározza a kizárt változót tartalmazó sort (feloldást). A minimum szimplex reláció szerinti bázisból kizárt változó (illetve a feloldósor választása) a már megállapított báziskomponensek pozitivitását garantálja az új referenciatervben.

Az algoritmus 3. pontjában feltételezzük, hogy a szabad kifejezések oszlop összes eleme nem negatív. Ez a követelmény nem szükséges, de ha teljesül, akkor minden további szimplex transzformáció csak pozitív feloldóelemekkel történik, ami kényelmes a számításokhoz. Ha a szabad tagok oszlopában negatív számok vannak, akkor a feloldó elemet választjuk a következő módon:

1) nézd meg például egy negatív szabad kifejezésnek megfelelő sort – egy sort, és jelöljünk ki benne egy negatív elemet, és a megfelelő oszlopot tekintjük megoldónak (feltételezzük, hogy a probléma kényszerei konzisztensek);

2) hozza létre a szabad kifejezések oszlopának elemeinek viszonyait a feloldó oszlop megfelelő, azonos előjelű elemeihez (simplex relációk);

3) válassza ki a legkisebb szimplex relációt. Ez határozza meg az engedélyezési karakterláncot. Legyen ez pl. R-vonal;

4) a feloldó oszlop és sor metszéspontjában egy felbontó elem található. Ha az elem megengedő –stringek, akkor a szimplex transzformáció után ennek a karakterláncnak a szabad tagja lesz pozitív. BAN BEN másképp a következő lépésben ismét rátérünk -vonal. Ha a probléma megoldható, akkor bizonyos számú lépés után nem marad negatív elem a szabad kifejezések oszlopában.

Ha egy bizonyos valós termelési helyzetet PLP formába helyezünk, akkor a modellbe a kanonikus formára konvertálás során bevezetendő járulékos változóknak mindig van bizonyos gazdasági jelentése.

Egy példa egy probléma megoldására szimplex módszerrel, valamint egy példa egy kettős probléma megoldására.

A feladat

Három árucsoport értékesítéséhez egy kereskedelmi vállalkozás háromféle korlátozott anyagi és pénzforrással rendelkezik b 1 = 240, b 2 = 200, b 3 = 160 egység összegben. Ugyanakkor 1 árucsoport értékesítéséhez 1 ezer rubelért. áruforgalom, az első típusú erőforrást a 11 = 2 egység, a második típusú erőforrást a 21 = 4 egység, a harmadik típusú erőforrást a 31 = mennyiségben fogyasztanak el. 4 egység. 2 és 3 árucsoport értékesítésére 1 ezer rubelért. a forgalom az első típusú erőforrás szerint a 12 = 3, a 13 = 6 egység, a második típusú erőforrása a 22 = 2, a 23 = 4 egység, a 23 = 4 egység a harmadik típus a 32 = 6, a 33 = 8 egység mennyiségben. Nyereség három árucsoport eladásából 1 ezer rubelért. a forgalom rendre c 1 = 4, c 2 = 5, c 3 = 4 (ezer rubel). Határozza meg a kereskedelmi forgalom tervezett volumenét és szerkezetét úgy, hogy a kereskedelmi vállalkozás profitja maximalizálva legyen.

A forgalomtervezés közvetlen problémájára, szimplex módszerrel oldják meg, összeállít kettős probléma lineáris programozás.
Telepítés konjugált változópárok közvetlen és kettős problémák.
Konjugált változópárok szerint a direkt probléma megoldásából kapjuk a kettős probléma megoldása, amelyben előállítják erőforrás felmérés, áru eladására költött.

A feladat megoldása szimplex módszerrel

Legyen x 1, x 2, x 3 az eladott áruk száma ezer rubelben, 1, 2, 3 csoportból. Akkor matematikai modell a feladat formája:

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(mátrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Megoldjuk a szimplex módszert.

További x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 változókat vezetünk be, hogy az egyenlőtlenségeket egyenlőséggé alakítsuk.

Vegyünk alapul x 4 = 240-et; x 5 = 200; x 6 = 160.

Beírjuk az adatokat szimplex asztal

Simplex táblázat 1. sz

Objektív funkció:

0 240 + 0 200 + 0 160 = 0

A becsléseket a következő képlet alapján számítjuk ki:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Mivel negatív becslések vannak, a terv nem optimális. Legalacsonyabb pontszám:

Bevezetjük az x 2 változót a bázisba.

Az alapból kilépő változót definiáljuk. Ehhez megtaláljuk a legkisebbet nem negatív attitűd x 2 oszlophoz.

= 26.667

Legkisebb nem negatív: Q 3 = 26,667. Az x 6 változót a bázisból származtatjuk

Osszuk el a 3. sort 6-tal.
Az 1. sorból vonjuk ki a 3. sort, megszorozzuk 3-mal
A 2. sorból kivonjuk a 3. sort 2-vel szorozva

Kiszámoljuk:

Kapunk új asztal:

Simplex táblázat 2. sz

Objektív funkció:

0 160 + 0 440/3 + 5 80/3 = 400/3

A becsléseket a következő képlet alapján számítjuk ki:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Mivel van negatív becslés Δ 1 = - 2/3, a terv nem optimális.

Az x 1 változót bevisszük a bázisba.

Az alapból kilépő változót definiáljuk. Ehhez megtaláljuk az x 1 oszlop legkisebb nem negatív arányát.

Legkisebb nemnegatív: Q 3 = 40. Az x 2 változót a bázisból származtatjuk

Osszuk el a 3. sort 2/3-dal.
A 2. sorból vonja ki a 3. sort, szorozva 8/3-mal

Kiszámoljuk:

Kapunk egy új táblázatot:

Simplex táblázat 3. sz

Objektív funkció:

0 160 + 0 40 + 4 40 = 160

A becsléseket a következő képlet alapján számítjuk ki:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Mivel nincs negatív értékelés, a terv optimális.

A probléma megoldása:

Válasz

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

Vagyis az első típusú árut 40 ezer rubel értékben kell eladni. Nincs szükség 2-es és 3-as típusú áruk értékesítésére. Ebben az esetben a maximális nyereség F max = 160 ezer rubel lesz.

A kettős probléma megoldása

A kettős probléma formája a következő:

Z = 240 év 1 + 200 év 2 + 160 év 3 -> perc

Title="delim(lbrace)(mátrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

További y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 változókat vezetünk be, hogy az egyenlőtlenségeket egyenlőséggé alakítsuk.

A direkt és duális problémák konjugált változópárjai a következő formájúak:

A direkt probléma utolsó szimplex táblájából 3. találjuk meg a megoldást a duális feladatra:

Z min = Fmax = 160;
y1=A4=0; y2=A5=0; y3=A6=1; y4 = Δ1 = 0; y5 = Δ2 = 1; y6=A3=4;

Ez a módszer egy lineáris programozási probléma referenciamegoldásának célirányos felsorolásának módszere. Lehetővé teszi, hogy véges számú lépésben vagy optimális megoldást találjunk, vagy megállapítsuk, hogy nincs optimális megoldás.

A szimplex módszer fő tartalma a következő:

1. Jelöljön meg egy módszert az optimális referenciamegoldás megtalálásához!
2. Jelölje meg az egyik referenciamegoldásból a másikba való átmenet módját, amelynél a célfüggvény értéke közelebb lesz az optimálishoz, pl. mutasson módot a referenciamegoldás javítására
3. Állítson be olyan kritériumokat, amelyek lehetővé teszik, hogy azonnal leállítsa a támogatási megoldások keresését az optimális megoldásnál, 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

Egy probléma szimplex módszerrel történő megoldásához a következőket kell tennie:

1. Hozd a problémát kanonikus formába
2. Keresse meg a kezdeti támogatási megoldást „egységbázissal” (ha nincs támogatási megoldás, akkor a korlátrendszer összeférhetetlensége miatt a problémának nincs megoldása)
3. Számítsa ki a vektorbontások becsléseit a referenciamegoldás 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ó

Példa egy feladat megoldására szimplex módszerrel

26.1. példa

Oldja meg a problémát a szimplex módszerrel:

Megoldás:

A problémát kanonikus formába hozzuk.

Erre a célra be bal oldal Az első egyenlőtlenségi kényszerhez egy további x 6 változót vezetünk be, amelynek együtthatója +1. Az x 6 változó nulla együtthatóval szerepel a célfüggvényben (azaz nincs benne).

Kapunk:

Megtaláljuk a kezdeti támogatási megoldást. Ehhez a szabad (feloldatlan) változókat nullával egyenlővé tesszük x1 = x2 = x3 = 0-val.

Kapunk referencia oldat X1 = (0,0,0,24,30,6) egységalapon B1 = (A4, A5, A6).

Kiszámoljuk vektorbontások becslései feltételek a referenciaoldat alapján a következő képlet szerint:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - a célfüggvény együtthatóinak vektora az alapváltozókra
• X k = (x 1k, x 2k, ..., x mk) - a megfelelő A k vektor tágulási vektora a referenciamegoldás alapján
• C k a célfüggvény együtthatója az x k változóra.

A bázisban szereplő vektorok becslései mindig nullával egyenlőek. A referenciamegoldás, a kiterjesztési együtthatók és a feltételvektorok kiterjesztésének becslései a referenciamegoldás alapján a szimplex asztal:

A táblázat tetejére a becslések könnyebb kiszámíthatósága érdekében a célfüggvény együtthatóit írjuk. Az első "B" oszlopba a referenciamegoldás alapjában szereplő vektorokat írjuk. A vektorok felírásának sorrendje megfelel a kényszeregyenletekben megengedett ismeretlenek számának. A „C b” tábla második oszlopában az alapváltozókra vonatkozó célfüggvény együtthatói ugyanabban a sorrendben vannak beírva. Nál nél helyes hely a célfüggvény együtthatói a becslés "C b" oszlopában egységvektorok az alapban szereplő értékek mindig nullával egyenlőek.

A táblázat utolsó sorában a Δ k becslésekkel az „A 0” oszlopban a Z(X 1) referenciamegoldás célfüggvényének értékeit írjuk.

A kezdeti támaszmegoldás nem optimális, mivel a maximumfeladatban az A 1 és A 3 vektorokra vonatkozó Δ 1 = -2, Δ 3 = -9 becslések negatívak.

A támaszmegoldás javítására vonatkozó tétel szerint, ha egy maximumfeladatban legalább egy vektor negatív becsléssel rendelkezik, akkor lehet olyan új támaszmegoldást találni, amelyen a célfüggvény értéke nagyobb lesz.

Határozzuk meg, hogy a két vektor közül melyik vezet nagyobb növekedéshez a célfüggvényben.

A célfüggvény növekményét a következő képlet határozza meg: .

A θ 01 paraméter értékeit az első és a harmadik oszlophoz a következő képlettel számítjuk ki:

l = 1 esetén θ 01 = 6, l = 1 esetén θ 03 = 3 (26.1. táblázat).

A célfüggvény növekményét akkor kapjuk meg, ha a bázisba bevisszük az első vektort ΔZ 1 = - 6*(- 2) = 12, és a harmadik vektort ΔZ 3 = - 3*(- 9) = 27.

Következésképpen az optimális megoldás gyorsabb megközelítéséhez az A3 vektort kell bevinni a referenciamegoldás bázisába az A6 bázis első vektora helyett, mivel a θ 03 paraméter minimumát az első sorban érjük el ( l = 1).

A Jordan transzformációt X13 = 2 elemmel végezzük, a második X2 = (0,0,3,21,42,0) referenciamegoldást B2 = (A3, A4, A5) bázissal kapjuk. (26.2. táblázat)

Ez a megoldás nem optimális, mivel az A2 vektor negatív becslése Δ2 = - 6. A megoldás javításához be kell vezetni az A2 vektort a referenciamegoldás alapjába.

Meghatározzuk a bázisból származtatott vektor számát. Ehhez kiszámítjuk a θ 02 paramétert a második oszlophoz, amely l = 2 esetén 7. Következésképpen a bázisból származtatjuk az A4 második bázisvektort. A Jordan-transzformációt x 22 = 3 elemmel végezzük, megkapjuk a harmadik referenciamegoldást X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (26.3. táblázat).

Ez a megoldás az egyetlen optimális, mivel minden, a bázisban nem szereplő vektorra a becslések pozitívak

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Válasz: max Z(X) = 201 X = (0,7, 10, 0,63).

Lineáris programozási módszer a közgazdasági elemzésben

Lineáris programozási módszer lehetővé teszi a legoptimálisabb igazolását gazdasági döntés a termelésben felhasznált erőforrásokkal kapcsolatos szigorú korlátozások mellett (befektetett eszközök, anyagok, munkaerő-források). Ennek a módszernek az alkalmazása a gazdasági elemzés elsősorban a szervezet tevékenységének tervezésével kapcsolatos problémák megoldását teszi lehetővé. Ez a módszer segít meghatározni az optimális kimeneti szinteket, valamint a legtöbb irányt hatékony felhasználása a szervezet rendelkezésére álló termelési erőforrások.

Ezzel a módszerrel az úgynevezett extrém problémákat oldják meg, ami a megtalálásból áll szélsőséges értékek, vagyis a változó mennyiségek függvényeinek maximuma és minimuma.

Ez az időszak a rendszer megoldásán alapul lineáris egyenletek azokban az esetekben, amikor a vizsgált gazdasági jelenségeket lineáris, szigorúan funkcionális függőség köti össze. A lineáris programozási módszer a változók elemzésére szolgál bizonyos korlátozó tényezők jelenlétében.

Nagyon elterjedt az úgynevezett szállítási probléma megoldása lineáris programozási módszerrel. Ennek a feladatnak a tartalma az üzemeltetéssel kapcsolatban felmerülő költségek minimalizálása Jármű a meglévő korlátozások mellett a járművek számát, teherbírását, üzemeltetési idejét és karbantartási igényét illetően maximális mennyiség vásárlók.

Ezenkívül ez a módszer megállapítja széles körű alkalmazás az ütemezési probléma megoldása során. Ez a feladat egy olyan működési idő elosztásából áll egy adott szervezet személyi állománya számára, amely a legelfogadhatóbb lenne mind a személyzet tagjai, mind a szervezet ügyfelei számára.

Ez a feladat a rendelkezésre álló létszám és a munkaidő keret korlátozása mellett a kiszolgált ügyfelek számának maximalizálása.

Így a lineáris programozási módszer meglehetősen elterjedt az elhelyezési és használati elemzésben. különféle típusok források, valamint a szervezetek tevékenységének tervezése és előrejelzése folyamatában.

Ennek ellenére a matematikai programozás ezekre is alkalmazható gazdasági jelenségek, amelyek közötti kapcsolat nem lineáris. Erre a célra nemlineáris, dinamikus és konvex programozási módszerek használhatók.

A nemlineáris programozás a célfüggvény vagy a megszorítások nemlineáris természetére támaszkodik, vagy mindkettőre. A célfüggvény és az egyenlőtlenségi kényszerek formái ezekben a feltételekben eltérőek lehetnek.

A nemlineáris programozást a gazdasági elemzésben használják, különösen a szervezet tevékenységének hatékonyságát kifejező mutatók és e tevékenység volumene, a termelési költségek szerkezete, a piaci feltételek stb.

A dinamikus programozás döntési fa felépítésén alapul. A fa minden egyes szintje egy korábbi döntés következményeinek meghatározásához és az adott döntés nem hatékony lehetőségeinek kiküszöböléséhez szolgál. És így, dinamikus programozás többlépcsős, többlépcsős természetű. Ezt a fajta programozást a közgazdasági elemzésben használják, hogy optimális lehetőségeket találjanak egy szervezet fejlesztéséhez mind most, mind a jövőben.

A konvex programozás a nemlineáris programozás egyik fajtája. Az ilyen típusú programozás a szervezet tevékenységeinek eredményei és költségei közötti kapcsolat nemlineáris jellegét fejezi ki. A konvex (más néven konkáv) programozás konvex célfüggvényeket és konvex kényszerrendszereket (megvalósíthatósági pontokat) elemez. Az elemzésben alkalmazott konvex programozás gazdasági aktivitás a költségek minimalizálása érdekében, és homorú - a bevétel maximalizálása érdekében a vizsgált mutatókat befolyásoló tényezők hatásának meglévő korlátozásai mellett ellenkező módon. Következésképpen a szóban forgó programozási típusokkal a konvex célfüggvények minimalizálva, a konkáv célfüggvények pedig maximalizálva vannak.

Az első sorhoz hasonlóan az optimalitási kritérium mutatói számára van fenntartva. Az első sor és az első oszlop közötti különbség a következő:

Az első sor, az oszloptól eltérően, csak az első szimplex táblában tárolódik. A második iterációtól kezdve a felső sor már nem szükséges.

Az első sor az optimalitási kritérium kivétel nélkül minden mutatóját (fő és kiegészítő) jelöli, pl. minden olyan együttható, amellyel az ismeretlenek szerepelnek a célfüggvényben. Az első oszlop a célfüggvényben szereplő ismeretlenekre vonatkozó együtthatóknak csak egy részét tartalmazza, mert a mátrix sorainak száma megegyezik a további ismeretlenek számával. Ez a rész mutatókból áll, amelyek számai a második oszlopban (p k) vannak feltüntetve.

Második oszlop– p k (pulyka k – iterációs szám).

Ebben az oszlopban az alapmegoldásban szereplő ismeretlenek száma látható. Ezek a számok a mátrix megfelelő sorainak számozására szolgálnak.

Az első szimplex táblázatban a p 0 oszlop az összes további változó számát jelzi.

3. Harmadik oszlop– x 0.

Az első szimplex táblában a kényszerrendszerből származó egyenletek szabad tagjaival van kitöltve. Az iteratív számítás során ezeket a mutatókat a kívánt megoldássá alakítjuk. Ezért ezt az oszlopot ún teljes oszlop.

4. Az objektív függvény értéke Fk.

Az eredményül kapott oszlop metszéspontjában a célsorban a függvénynek megfelelő F k értéke ezen a ponton k iterációnál adott megoldás.

„Matrix base” oszlopok.

Általában az elsődleges ismeretlenek oszlopai kerülnek először, majd a további ismeretlenek.

Az első szimplex táblázatban ezekben az oszlopokban adjuk meg a kezdeti feltételek egyenletéből származó ismeretlenek együtthatóit.

6. A táblázat következő három oszlopa (, , ) rendelkezik segédjelentés. Az oszlopok nélkül is megteheti, de sokkal könnyebbé teszik a számításokat. Ezeknek az oszlopoknak a tartalmát az alábbiakban részletesebben tárgyaljuk.

Példa

Tekintsünk egy szimplex problémát általános formában:

Csökkentsük a problémát kanonikus formára. Ehhez a rendszer minden egyenlőtlenségébe bevezetünk egy ismeretlent (kiegészítőt) - x 4, x 5. x 6. Akkor

F = 15x 1 + 20x 2 +5x 3  max.

Töltsük ki az első szimplex táblát.

Az összes cellát kitöltjük a probléma körülményei alapján.

Az első táblázat F 0 cellájának kitöltéséhez össze kell adni az x 0 oszlop elemeinek szorzatát a c 0 oszlop elemeivel, azaz.

F 0 = 600∙0 + 520∙0 +600∙0 =0.

Az első táblázat célsorának kitöltéséhez ki kell vonni a megfelelő c j értéket az x j oszlop elemeinek szorzatából a c 0 oszlop elemeivel.

Az x 1 oszlop esetében a kettős becslés értéke kerül meghatározásra

(0∙80+0∙15+0∙5) – 15=-15;

x 2 esetén: (0 35+0 60+0 5) – 20=-20;

x 3: (0 10+0 0+0 90) – 5=-5 stb.

Ennek eredményeként az első szimplex tábla így fog kinézni:

Asztal 1

A megoldás folytatása előtt ellenőrizni kell, hogy a táblázatban javasolt terv (megoldás) optimális-e.

Meghatározás

A döntést megfontolják optimális ha a célkarakterlánc összes számértéke pozitív.

Ha a kapott megoldás nem optimális, javítható. Ehhez szüksége van:

1. Válassza ki a célsorban lévő szám maximális negatív értékét abszolút értékben.

Példánkban ez a szám (-20), az „x 2” oszlopban található. Ez az érték, ami beállít kulcs oszlop.

Jegyzet:

Kulcsoszlop megmutatja, hogy az x j közül melyik kerül bele a feladat új megoldásába. Esetünkben az ismeretlen x 2.

Kérjük, vegye figyelembe:

Ahhoz, hogy egy ismeretlen x j-t beépítsünk egy új, ezt a megoldást javító megoldásba, a benne szereplő x j egyikét az alapmegoldásból kell származtatni.

2. Válassza ki az x oszlop elemeinek hányadosának minimális értékét 0 a kulcsoszlop elemeire. A számítások eredményeit a szimplex táblázat „” oszlopába kell beírni.

Példánkban ezek az arányok egyenlőek:

A minimális érték x 5-nek felel meg, és egyenlő 8,67-tel. Ez a kapcsolat meghatározza kulcsfüzér.

Válasszon ki egy kulcsoszlop és egy kulcssor metszéspontjában elhelyezkedő elemet, amelyet a program hívkulcsösszetevő .

Példánkban a kulcselem a 60, és az x 2 oszlop és az x 5 sor metszéspontjában található.

Jegyzet:

Kulcsoszlop nem lehet olyan oszlop, amelynek minden eleme negatív vagy nulla.

A mátrixelemek összegzése soronként(x 0 oszloptól kezdve és x 6 oszlopig érve). A beérkezett összegek a „” oszlopban kerülnek rögzítésre.

Kulcskarakterlánc konvertálása. Ezért

1. Minden kulcssorelem egy kulcselemre van felosztva, amely az "x0" oszlopelemmel kezdődik;

Töredék

A p 1 oszlopban x 5 helyett x 2 van írva;

A c j oszlop az optimalitási kritérium értékét rögzíti x 2-nél, azaz. 20.

A szimplex tábla összes többi eleme újraszámításra kerül, betartva az alapszabályt. Ezt a szabályt úgy hívják átlós szabályok vagy háromszög szabályok.

.

A célfüggvény értékének újraszámítása során a következőket kapjuk:

.

Ugyanígy járunk el a táblázat összes többi elemével is. Ennek eredményeként egy új szimplex táblát kapunk.

2. táblázat.

Ahogy a táblázatból is látszik. 2, nem sikerült az optimális megoldást kapni, azaz. a megoldást folytatni kell a szimplex táblák transzformációjának összes figyelembe vett szabályával.

1. megjegyzés.

A "" oszlop a megoldás előrehaladásának soronkénti ellenőrzésére szolgál. A sorelemek új értékeinek összegének meg kell egyeznie a sor és a „” oszlop elemének értékével, az átlós szabály szerint átalakítva.

Jegyzet 2.

A célfüggvény értékének meg kell egyeznie a j oszlop elemeinek az x0 oszlop elemei szorzatainak összegével.

Hajtsa végre ezt a feladatot saját maga. Az eredmény a következő legyen:

F=236,7; x 1 = 3,31; x 2 = 7,8; x 3 = 6,05.

3. megjegyzés.

A „” oszlopba a kulcsoszlopban és az i-es sorban lévő elem kulcselemmel való elosztásának hányadosait írjuk.

4. megjegyzés.

A következő táblázatban kezdje el a számításokat az átlós szabály segítségével a célsorból. Ha minden becslés pozitív, akkor megtaláltuk az optimális megoldást, és már csak az x0 oszlopot kell kitölteni. Ebben az esetben nem szükséges újraszámolni a mátrixalapot.

A TÁBLÁZAT SIMPLEX MÓDSZER HASZNÁLATA LINEÁRIS PROGRAMOZÁSI PROBLÉMÁK MEGOLDÁSÁRA A GAZDASÁGI FELADATOK OPTIMALIZÁLÁSA

BEVEZETÉS

Ennek célja tanfolyam projekt- tervet készíteni a szükséges termékek előállítására, biztosítva az értékesítésből származó maximális profitot, csökkenteni ez a feladat egy lineáris programozási feladathoz, oldja meg szimplex módszerrel, és készítsen programot a feladat megoldására ezzel a módszerrel számítógépen.

1. AZ ILYEN TÍPUSÚ PROBLÉMÁK MEGOLDÁSÁNAK ALGORITMUSOK RÖVID ÁTTEKINTÉSE

1.1 Matematikai programozás

A matematikai programozás extrém problémák tanulmányozása és megoldási módszerek keresése. Feladatok matematikai programozás a következőképpen fogalmazva: keressük meg sok f (x 1, x 2, ... , x n) változó egy bizonyos függvényének szélsőértékét g i (x 1, x 2, ... , x n) * b i korlátozások mellett, ahol g i a korlátozásokat leíró függvény , * - a következő jelek egyike £ , = , ³ és b i - valós szám, i = 1, ... , m. f-et célfüggvénynek (objektív függvénynek) nevezzük.

A lineáris programozás a matematikai programozás egyik ága, amely olyan extrém problémák megoldási módszereivel foglalkozik, amelyek lineáris funkcionális és lineáris megszorításokat tartalmaznak, amelyeket a kívánt változóknak kell kielégíteniük.

A lineáris programozási probléma a következőképpen fogalmazható meg. Keresse meg max

feltéve: a 11 x 1 + a 12 x 2 +. . . + a 1n x n £ b 1 ;

a 21 x 1 + a 22 x 2 +. . . + a 2n x n £ b 2 ;

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

a m1 x 1 + a m2 x 2 +. . . + a mn x n £ b m ;

x 1 ³ 0, x 2 ³ 0, . . . , x n ³ 0 .

Ezeket a korlátozásokat nem-negatív feltételeknek nevezzük. Ha minden korlátozást szigorú egyenlőségek formájában adunk meg, akkor ez a forma kanonikusnak nevezik.

Mátrix formában a lineáris programozási feladatot a következőképpen írjuk fel. Keresse meg a max c T x-et

tekintettel arra

ahol A egy (m´n méretű) kényszermátrix, b (m ´ 1) szabad tagok oszlopvektora, x (n ´ 1) változók vektora, T = pedig együtthatók sorvektora a célfüggvény.

Egy x 0 megoldást akkor nevezünk optimálisnak, ha a Т x 0 ³ с Т x feltétel teljesül rá, minden x О R(x) esetén.

Mivel min f(x) ekvivalens max [ - f(x) ] értékkel, a lineáris programozási probléma mindig egy ekvivalens maximalizálási feladatra redukálható.

A problémák megoldására ebből a típusból használt módszerek:

1) grafika;

2) táblázatos (közvetlen, egyszerű) szimplex - módszer;

3) mesterséges alapú módszer;

4) módosított szimplex módszer;

5) kettős szimplex módszer.

1.2 Táblázatos szimplex módszer

Használatához az szükséges, hogy a megszorításokban szereplő előjelek „kisebb vagy egyenlő” alakúak legyenek, és a b vektor komponenseinek pozitívnak kell lenniük.

A megoldási algoritmus a következőre csapódik le:

Korlátozási rendszer kanonikus formába hozása további változók bevezetésével az egyenlőtlenségek csökkentésére.

Ha az eredeti korlátozási rendszer „egyenlő” vagy „nagyobb vagy egyenlő” jeleket tartalmazott, akkor a megadott korlátozások hozzáadódnak

mesterséges változókat, amelyeket az optimum típusa által meghatározott előjelekkel is bevezetünk a célfüggvénybe.

Egy szimplex tábla jön létre.

A szimplex különbségek kiszámítása.

Döntés születik a számlálás befejezéséről vagy folytatásáról.

Az iterációkat szükség szerint hajtjuk végre.

Minden iterációnál meghatározzuk a bázisba bevitt vektort és a bázisból kiadott vektort. A táblázat újraszámítása Jordan-Gauss módszerrel vagy más módszerrel történik.

1.3 Mesterséges bázis módszer

Ezt a megoldási módszert akkor használjuk, ha a megszorítás az „egyenlő”, „nagyobb vagy egyenlő”, „kisebb vagy egyenlő” előjeleket tartalmazza, és a táblázatos módszer módosítása. A rendszert az optimum típusától függő előjelű mesterséges változók bevezetésével oldják meg, pl. hogy ezeket a változókat kizárjuk a bázisból, az utóbbiakat nagy m negatív együtthatóval vezetjük be a célfüggvénybe, pozitív m-rel pedig a minimalizálási problémába. Így egy új m-feladatot kapunk az eredetiből.

Ha az m-probléma optimális megoldásában nincsenek mesterséges változók, ez a megoldás az eredeti probléma optimális megoldása. Ha az m-probléma optimális megoldásában a mesterséges változók közül legalább egy eltér nullától, akkor az eredeti probléma kényszerrendszere inkonzisztens, az eredeti probléma pedig megoldhatatlan.

1.4 Módosított szimplex módszer

Az ilyen típusú szimplex módszer a következő tulajdonságokon alapul: lineáris algebra, amelyek lehetővé teszik, hogy egy probléma megoldása során a kényszermátrix egy részével dolgozzon. Néha a módszert inverz mátrix módszernek nevezik.

Az algoritmus működése során a kényszermátrix spontán módon invertálódik az aktuális bázisvektoroknak megfelelő részekre. Ez a képesség nagyon vonzóvá teszi a számítások gépi végrehajtását a közbenső változók memóriamegtakarítása és a számítási idő jelentős csökkentése miatt. Jó olyan helyzetekben, amikor az n változók száma jelentősen meghaladja az m megszorítások számát.

Általában a módszer a hagyományos jellemzőket tükrözi közös megközelítés lineáris programozási feladatok megoldására, ideértve a problémafeltételek kanonizálását, szimplex különbségek számítását, az optimalitási feltételek ellenőrzését, döntéshozatalt báziskorrekción és Jordan-Gauss elimináción.

A jellemzők közé tartozik a két táblázat - a fő és a segédtábla jelenléte, a kitöltés sorrendje és a számítási képletek bizonyos sajátosságai.

Kétféle A és B termék előállításához háromféle technológiai berendezést használnak. Egy egységnyi A termék előállítása időt, órát vesz igénybe: 1. típusú berendezéssel - a 1, 2. típusú berendezéssel - a 2, 3. típusú berendezéssel - a 3. Időt, órát vesz igénybe, egységnyi B termék előállítására: 1- 1. típusú berendezéssel - b 1, 2. típusú berendezéssel - b 2, 3. típusú berendezéssel - b 3.

Valamennyi termék gyártásához a vállalkozás adminisztrációja 1. típusú berendezést legfeljebb t 1, 2. típusú berendezéseket legfeljebb t 2, 3. típusú berendezéseket legfeljebb t 3 óráig tud biztosítani. .

Az A késztermék egységnyi eladásából származó nyereség egy rubel, a B termék pedig b rubel.

Készítsen gyártási tervet az A és B termékekre, amely biztosítja az értékesítésükből származó maximális profitot. Oldja meg a problémát szimplex módszerrel. Adja meg a probléma geometriai értelmezését az egyenlőtlenségi megszorítások segítségével!

a 1 = 1 b 1 = 5 t 1 = 10 a = 2

a 2 = 3 b 2 = 2 t 2 = 12 b = 3

a 3 = 2 b 3 = 4 t 3 = 10

3. A PROBLÉMA MEGOLDÁSÁNAK ALGORITMUSÁNAK KIFEJLESZTÉSE ÉS LEÍRÁSA

3.1 A probléma matematikai modelljének felépítése

A matematikai modell felépítése három lépésben történik:

1. Azon változók meghatározása, amelyekre matematikai modellt állítunk össze.

Mivel meg kell határozni az A és B termékek gyártási tervét, akkor modellváltozók lesz:

x 1 - az A termék gyártási mennyisége, egységekben;

x 2 - a B termék gyártási mennyisége, egységekben.

2. A célfüggvény kialakítása.

Mivel az A és B késztermékek egységnyi értékesítéséből származó nyereség ismert, az értékesítésükből származó teljes bevétel 2x 1 + 3x 2 (rubel). A teljes jövedelmet F-vel jelölve a következőket adhatjuk matematikai megfogalmazás célfüggvény: határozza meg érvényes értékek x 1 és x 2 változók, amelyek maximalizálják az F = 2x 1 + 3x 2 célfüggvényt.

3. Korlátozási rendszer kialakítása.

A termékgyártási terv meghatározásakor figyelembe kell venni azokat az időkorlátokat, amelyeket a vállalati adminisztráció minden termék előállítására biztosítani tud. Ez a következő három korlátozáshoz vezet:

x 1 + 5x 2 10 GBP; 3x 1 + 2x 2 12 GBP ; 2x 1 + 4x 2 10 GBP.

Mivel a termelési mennyiségek nem vehetnek fel negatív értékeket, nem negatív korlátozások jelennek meg:

x 1³ 0; x 2³ 0.

Így a probléma matematikai modelljét a következő formában mutatjuk be: határozzunk meg egy x 1, x 2 tervet, amely biztosítja maximális érték Jellemzők:

max F = max (2x 1 + 3x 2)

ha vannak korlátozások:

x 1 + 5x 2 10 GBP;

3x 1 + 2x 2 £ 12 ;

2x 1 + 4x 2 10 GBP.

x 1³ 0; x 2³ 0.

3.2 A probléma kézi megoldása

A táblázatos módszert a becslés szekvenciális javításának módszerének is nevezik. A probléma megoldása szakaszosan történik.

1. A probléma redukálása a következőre:

x 1 + 5x 2 10 GBP;

3x 1 + 2x 2 £ 12 ;

2x 1 + 4x 2 10 GBP.

x 1³ 0; x 2³ 0.

2. Kanonizáljuk a korlátozások rendszerét:

x 1 + 5x 2 + x 3 =10;

3x 1 + 2x 2 + x 4 = 12 ;

2x 1 + 4x 2 + x 5 = 10.

x 1³ 0; x 2³ 0.

A 1 A 2 A 3 A 4 A 5 A 0

3. A kiindulási szimplex táblázat kitöltése és a szimplex különbségek kiszámítása a következő képletekkel történik:

- a célfüggvény aktuális értéke - szimplex különbségek számítása, ahol j = 1..6.

Előző cikk: Mekkora a fénysebesség Következő cikk: Harmonikus rezgések Az oszcillációs frekvencia fizikai képlete