Egy online számológép grafikus megoldása. Lineáris programozási feladatok megoldási módszerei. A megvalósítható megoldások tartományának felépítése

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 keressen optimális megoldás, vagy megállapítja, hogy nincs optimális megoldás.

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

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

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

Megoldás:

A problémát kanonikus formába visszük.

Ehhez az első egyenlőtlenségi kényszer bal oldalára bevezetünk egy további x 6 változót +1 együtthatóval. 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 kiterjeszté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. A célfüggvény együtthatóinak helyes elrendezése esetén a "C b" oszlopban a bázisban szereplő egységvektorok becslései 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 gazdasági megoldás igazolását a termelésben felhasznált erőforrásokkal (befektetett eszközök, anyagok, munkaerő) kapcsolatos szigorú korlátozások körülményei között. Ennek a módszernek a közgazdasági elemzésben való alkalmazása 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 a termékkibocsátás optimális mennyiségeit, valamint a szervezet rendelkezésére álló termelési erőforrások leghatékonyabb felhasználásának irányait.

Ezzel a módszerrel az ún. extrém problémákat oldjuk meg, ami abból áll, hogy szélsőértékeket, azaz változó mennyiségek függvényeinek maximumát és minimumát keressük.

Ez az időszak lineáris egyenletrendszer megoldásán alapul olyan esetekben, amikor a vizsgált gazdasági jelenségeket lineáris, szigorúan funkcionális függés 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.

Kívül, ez a módszer talál 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és és a felhasználás elemzésében. különféle típusok források, valamint a szervezetek tevékenységének tervezése és előrejelzése folyamatában.

Mindazonáltal a matematikai programozás azokra a gazdasági jelenségekre is alkalmazható, 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. Így a 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. A konvex programozást a gazdasági tevékenységek elemzésében használják a költségek minimalizálása céljából, a konkáv programozást pedig azzal a céllal, hogy maximalizálják a bevételt a meglévő korlátozások mellett, amelyek a vizsgált mutatókat ellenkező módon befolyásolják. Következésképpen a szóban forgó programozási típusokkal a konvex célfüggvények minimálisra, a konkáv célfüggvények pedig maximalizálva vannak.

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

×

Figyelem

Törli az összes cellát?

Bezárás Törlés

Adatbeviteli utasítások. A számok egész számok (például 487, 5, -7623 stb.), tizedesjegyek (pl. 67., 102,54 stb.) vagy törtek formájában kerülnek megadásra. A törtet a/b formában kell megadni, ahol a és b (b>0) egész vagy tizedes. Példák 45/5, 6,6/76,4, -7/6,7 stb.

Simplex módszer

Példák a ZLP megoldására szimplex módszerrel

1. példa Oldja meg a következő lineáris programozási feladatot:

Az egyenletrendszer megszorításainak jobb oldala a következő alakú:

Jegyezzük fel az aktuális referenciatervet:

Ez a referenciaterv nem optimális, mert az utolsó sorban negatív elemek vannak. A modulus legnagyobb negatív eleme (-3), ezért a vektor benne van a bázisban x nál nél . min(40:6, 28:2)=20/3 az 1. sornak felel meg. A vektor a bázisból jön ki x 3. Végezzünk Gauss-eliminációt az oszlopra x 2, mivel a vezető elem az 1. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja össze a 2., 3., 4. sor sorait az 1. sorral, szorozva -1/3, 1/6, 1/2-vel. Ezután a vezető elemet tartalmazó sort elosztjuk a vezető elemmel.

Ez a referenciaterv nem optimális, mivel az utolsó sor negatív elemű (-3), ezért a bázis tartalmazza a vektort x 1 . Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél . min(44/3:11/3, 62/3:5/3)=4 a 2. sornak felel meg. A vektor a bázisból jön ki x 4. Végezzünk Gauss-eliminációt az oszlopra x 1, mivel a vezető elem a 2. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja hozzá az 1., 3., 4. sorokat a 2. sor 1/11, -5/11, 9/11 szorzatával. Ezután a vezető elemet tartalmazó sort elosztjuk a vezető elemmel.

A szimplex táblázat a következő formájú lesz:

A jelenlegi referenciaterv optimális, hiszen a változók 4. sorában nincsenek negatív elemek.

A megoldást így írhatjuk fel: .

A célfüggvény értéke ezen a ponton: F(x)=.

Példa 2. Keresse meg egy függvény maximumát

Megoldás.

Alapvektorok x 4 , x 3 tehát minden elem oszlopban x 4 , x A vízszintes vonal alatti 3-nak nullának kell lennie.

Állítsa vissza az összes oszlopelemet nullára x 4, kivéve a vezető elemet. Ehhez adja hozzá a 3. sort az 1. sor 4-gyel szorozva. Állítsa vissza az oszlop összes elemét nullára x 3, kivéve a vezető elemet. Ehhez adja hozzá a 3. sort a 2. sor 1-gyel szorozva.

A szimplex táblázat a következő formában jelenik meg:

Ez a referenciaterv nem optimális, mivel az utolsó sor negatív elemű (-11), ezért a bázis tartalmazza a vektort x 2. Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél . Ezért a célfüggvény felülről korlátlan. Azok. a lineáris programozási probléma megoldhatatlan.

Példák a ZLP megoldására mesterséges bázis módszerrel

Példa 1. Keresse meg egy függvény maximumát

Megoldás: Mivel a bázisvektorok számának 3-nak kell lennie, hozzáadunk egy mesterséges változót, és a célfüggvényhez hozzáadjuk ezt a változót −M-mel szorozva, ahol M egy nagyon nagy szám:

Az egyenletrendszer együtthatómátrixának alakja:

A bázisvektorok ezért a vízszintes vonal alatti oszlopokban minden elemnek nullának kell lennie.

Állítsuk vissza az oszlop összes elemét, kivéve a vezető elemet. Ehhez adja hozzá az 5. sort a 3. sor -1-gyel szorozva.

A szimplex táblázat a következő formában jelenik meg:

Ez a referenciaterv nem optimális, mert az utolsó sorban negatív elemek vannak. A legnagyobb abszolút negatív elem (-5), ezért a vektor benne van a bázisban Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél A bázisból egy vektor jön ki. Tegyünk egy Gauss-kivételt az oszlopra, mivel a vezető elem a 3. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja hozzá az 5. sort a 3. sor 1-gyel szorozva. Ezután ossza el a bevezető elemet tartalmazó sort a vezető elemmel.

A szimplex táblázat a következő formájú lesz:

Ez a referenciaterv nem optimális, mert az utolsó sorban negatív elemek vannak. A legnagyobb abszolút negatív elem (-3), ezért a vektor benne van a bázisban Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél az 1. sornak felel meg. A vektor a bázisból jön ki x 2. Végezzünk Gauss-eliminációt az oszlopra x 1 , mivel a vezető elem az 1. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja össze a 2., 3., 4. sor sorait az 1. sorral, szorozva 3/2, -1/10, 3/2-vel. Ezután a vezető elemet tartalmazó sort elosztjuk a vezető elemmel.

A szimplex táblázat a következő formájú lesz:

Ez a referenciaterv nem optimális, mert az utolsó sorban negatív elemek vannak. A modulusz legnagyobb negatív eleme (-13/2), ezért a bázis tartalmazza a vektort x 3. Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél a 3. sornak felel meg. A vektor a bázisból jön ki x 5. Végezzünk Gauss-eliminációt az oszlopra x 3, mivel a vezető elem a 3. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja össze az 1., 2., 4. sor sorait a 3. sorral, szorozva 5/3, 25/9, 65/9. Ezután a vezető elemet tartalmazó sort elosztjuk a vezető elemmel.

A szimplex táblázat a következő formájú lesz:

A jelenlegi referenciaterv optimális, mivel a 4-5. sor változói alatt nincsenek negatív elemek.

Az eredeti probléma megoldása a következőképpen írható fel:

2. példa Keresse meg az optimális tervet egy lineáris programozási feladathoz:

Az egyenletrendszer együtthatómátrixának alakja:

Alapvektorok x 4 , x 5 , x 6 ezért minden elem oszlopban x 4 , x 5 , x 6, a vízszintes vonal alatt nullának kell lennie.

Állítsa vissza az összes oszlopelemet nullára x 4, kivéve a vezető elemet. Ehhez adja hozzá a 4. sort az 1. sor -1-gyel szorozva. Állítsa vissza az összes oszlopelemet nullára x 5, kivéve a vezető elemet. Ehhez adja hozzá az 5. sort a 2. sor -1-gyel szorozva. Állítsa vissza az összes oszlopelemet nullára x 6, kivéve a vezető elemet. Ehhez adja hozzá az 5. sort a 3. sor -1-gyel szorozva.

A szimplex táblázat a következő formában jelenik meg:

Az 5. sorban a változóknak megfelelő elemeket x 1 , x 2 , x 3 , x 4 , x 5 , x A 6 nem negatív, és a szám egy adott sor és oszlop metszéspontjában található x 0 negatív. Ekkor az eredeti problémának nincs referenciaterve. Ezért eldönthetetlen.

A ZLP megoldásának grafikus módszere a 2.1. bekezdésben megadott állításokon alapul. A 2. Tétel szerint az optimális megoldás a megvalósítható megoldások tartományának tetején található, ezért a ZLP megoldásához meg kell találni a megvalósítható megoldások tartományának tetejét, amelynek koordinátái adják a célfüggvény optimális értékét.

A grafikus módszert egy korlátozott számú probléma megoldására használják két változóval, néha három változóval. Meg kell jegyezni, hogy három változó esetében ez a terület nem elég egyértelmű.

Algoritmus a feladatok grafikus módszeréhez

Megvizsgáljuk a grafikus módszer megvalósítását a ZLP megoldására példákon keresztül.

Példa 2.2.1. Oldja meg a ZLP-t grafikusan:

(2.2.1)

max z=x 1 + 4x 2 (2.2.2)

Megoldás. A (2.2.1) kényszerrendszer minden egyenlőtlenségének megfelelő félsíkok metszéspontjából álló megvalósítható megoldások tartományának megalkotásához felírjuk a határegyenesek egyenleteit:

l 1: x 1 + 5x 2 = 5; l 2: x 1 + x 2 = 6; l 3: 7x 1 + x 2 = 7.

l 1-et a (2.2.3.) formára mindkét részét elosztjuk 5-tel:
. Így egyenesen l 1 vágás a tengelyen Ó 1 5 egység, a tengelyen Ó 2 1 egység. Hasonlóképpen mi is l 2:
És l 3:
.

A (2.2.1) rendszer kényszereinek megfelelő félsíkok meghatározásához bármely olyan pont koordinátáit be kell cserélni a kényszerekbe, amelyek nem a határvonalon helyezkednek el. Ha valódi egyenlőtlenséget kapunk, akkor ennek a félsíknak minden pontja megoldása ennek az egyenlőtlenségnek. Ellenkező esetben válasszon másik félsíkot.

Így az első és a második kívánt félsík a koordináták origójával ellentétes irányban helyezkedik el (0 – 5 0 - 5; 7 0 + 0 7), a második pedig a koordináták origója felé (0 + 0 6). A 2.2.1. ábrán a megvalósítható megoldások tartománya árnyékolt.

2.2.1 ábra – A megvalósítható megoldások területe

Az optimális terv megtalálásához, amely a megoldási sokszög csúcsán lesz, meg kell alkotnia egy irányvektort
=(Val vel 1 ,Val vel 2), amely a célfüggvény legnagyobb növekedésének irányát jelzi z=Val vel 1 x 1 +Val vel 2 x 2 .

Ebben a feladatban az irányvektor
= (1, 4): a pontnál kezdődik RÓL RŐL(0,0) és a pontban ér véget N(1, 4).

Ezután megszerkesztünk egy egyenest, amely átmegy a megvalósítható megoldások tartományán, merőlegesen a vektorra, és ún. célszint vonal funkciókat. A célfüggvény maximalizálása esetén a szintvonalat a vektor irányába mozgatjuk zés ellenkező irányban, minimalizálás esetén z, az utolsó metszéspontig a megvalósítható megoldások régiójával. Ennek eredményeként meghatározásra kerül az a pont vagy pontok, ahol a célfüggvény szélső értéket ér el, vagy megállapítható a célfüggvény határtalansága z a probléma megoldásainak halmazáról.

Így a célfüggvény maximális pontja z a lényeg A vonal kereszteződései l 2 és l 3 .

A célfüggvény optimális értékének kiszámításához z keresse meg a pont koordinátáit A . A lényeg óta A a vonalak metszéspontja l 2 és l 3, akkor a koordinátái kielégítik a megfelelő határvonalak egyenleteiből összeállított egyenletrendszert:

Szóval a lényeg A koordinátái vannak x 1 =1/6, x 2 = 35/6.

A célfüggvény optimális értékének kiszámításához be kell cserélni a pont koordinátáit A .

A pont koordinátáinak behelyettesítése A a célfüggvénybe (2.4) kapjuk

max z = 1/6 + 4·(35/6) = 47/2.

Példa 2.2.2. Szerkessze meg a síkon a lineáris egyenlőtlenségrendszer (2.2.4) megvalósítható megoldásainak tartományát, és keresse meg a célfüggvény (2.2.5) legnagyobb és legkisebb értékét:

(2.2.4)

z= –2x 1 –x 2 (2.2.5)

Megoldás. A (2.2.4) kényszerrendszer minden egyenlőtlenségének megfelelő félsíkok metszéspontjából álló megvalósítható megoldások tartományának megalkotásához felírjuk a határegyenesek egyenleteit:

l 1: 4x 1 – x 2 = 0; l 2: x 1 + 3x 2 = 6; l 3: x 1 – 3x 2 = 6; l 4: x 2 = 1.

Egyenes l 1 áthalad a (0;0) koordinátájú ponton. Megalkotásához kifejezzük x 2 keresztül x 1: x 2 = 4x 1 . Keressünk egy másik pontot, amelyen az egyenes áthalad l 1, például (1;4). A (0;0) koordinátájú ponton és a (1;4) koordinátájú ponton keresztül egyenest húzunk l 1 .

Az egyenes egyenletének csökkentésére l 2-es formához a tengelyeken szegmensekben (2.2.3), mindkét részét elosztjuk 6-tal:
. Így egyenesen l 2 vágás a tengelyen Ó 1 6 egység, a tengelyen Ó 2-2 egység. Hasonlóképpen mi is l 3:
és Közvetlen l 4 párhuzamos a tengellyel Ó 1 és áthalad a (0;1) koordinátájú ponton.

A (2.2.4) rendszer kényszereinek megfelelő félsíkok meghatározásához minden olyan pont koordinátáit be kell cserélni, amelyek nem a határvonalon helyezkednek el a kényszerekbe. A korlátozások miattx 1 0, x 2 0, a ZLP megengedett megoldásainak tartománya a koordinátasík első negyedében található.

RÓL RŐL
A 2.2.2. ábrán a megvalósítható megoldások területe árnyékolt.

2.2.2 ábra – A megvalósítható megoldások területe

Készítsünk irányvektort
= (–2,–1). Ezután a vektorra merőleges szintvonalat építünk .

A célfüggvény legnagyobb értékének megtalálásához a szintvonalat a vektor irányába mozgatjuk a megvalósítható megoldások tartományával való utolsó metszéspontig. Így a célfüggvény maximális pontja z a lényeg A(vonalak metszéspontja l 1 és l 2).

A célfüggvény optimális értékének kiszámításához z keresse meg a pont koordinátáit A. A lényeg óta A a vonalak metszéspontja l 1 és l 2, akkor a koordinátái kielégítik a megfelelő határvonalak egyenleteiből összeállított egyenletrendszert:

Szóval a lényeg A koordinátái vannak x 1 =6/13, x 2 = 24/13.

A pont koordinátáinak behelyettesítése A a célfüggvénybe (2.2.5), megkapjuk a célfüggvény optimális értékét

max z= – 2·(6/13) – (24/13) = – 36/13.

A célfüggvény legkisebb értékének megtalálásához a szintvonalat a vektorral ellentétes irányba mozgatjuk a megvalósítható megoldások tartományával való utolsó metszéspontig. Ebben az esetben a célfüggvény a megvalósítható megoldások tartományában korlátlan, pl. A ZLP-nek nincs minimuma.

A PPP döntése következtében a következő esetek lehetségesek:

A célfüggvény a megoldási sokszög egyetlen csúcsánál éri el optimális értékét;

A célfüggvény a megoldási sokszög peremének bármely pontján eléri optimális értékét (a ZLP-nek vannak alternatív referenciatervei azonos értékekkel z );

A PAP-nak nincsenek optimális tervei;

A ZLP-nek van egy optimális terve a megvalósítható megoldások korlátlan köre esetén.

A lineáris programozás (LP) legegyszerűbb és legvizuálisabb módszere a grafikus módszer. LP problémák megoldására szolgál két változóval. Tekintsük az LP problémát szabványos formában:

max f(x 1 , x 2 , ..., x n) = ,

, i = 1, 2, …, m,

x j 0, j = 1, 2, …, n.

Tegyük fel n=2és megfontoljuk a problémát a repülőn. Legyen az egyenlőtlenségek rendszere konzisztens (legyen legalább egy megoldása).

Ennek a rendszernek minden egyenlőtlensége geometriailag meghatároz egy félsíkot a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2 határvonallal, …, m. A nem-negativitás feltételei rendre x 1 = 0, x 2 = 0 határegyenesekkel rendelkező félsíkokat határoznak meg. A rendszer konzisztens, ezért az egymást metsző félsíkok, mint a konvex halmazok, közös részt alkotnak, ami egy konvex halmaz és pontok halmaza, ahol az egyes pontok koordinátái ennek a rendszernek a megoldásai. Ezeknek a pontoknak a halmazát megoldási sokszögnek nevezzük. Lehet pont, szakasz, sugár, korlátos vagy korlátlan sokszög.

Így geometriailag a ZLP egy olyan pont keresése a megoldási sokszögben, amelynek koordinátái megadják lineáris függvény a cél a maximális (minimális) érték, és a megoldási sokszög minden pontja érvényes megoldás.

A lineáris egyenlet ugyanazon az egyenesen elhelyezkedő pontok halmazát írja le. A lineáris egyenlőtlenség a sík valamely régióját írja le. Határozzuk meg, hogy a sík melyik részét írja le a 2x 1 + 3x 2 12 egyenlőtlenség.

Először készítsünk egy 2x 1 + egyenest 3x 2= 12. Átmegy a (6; 0) és (0; 4) pontokon. Annak meghatározásához, hogy melyik félsík elégíti ki az egyenlőtlenséget, ki kell választani a gráf bármely pontját, amely nem tartozik az egyeneshez, és annak koordinátáit be kell cserélni az egyenlőtlenségbe. Ha az egyenlőtlenség fennáll, akkor az adott pont megvalósítható megoldás, és a pontot tartalmazó félsík kielégíti az egyenlőtlenséget. Az egyenlőtlenség behelyettesítéséhez célszerű a kezdőpontot használni. Helyettesítsük be az x 1 = x 2 = 0-t a 2x 1 + 3x 2 12 egyenlőtlenségbe. 2x0 + 3x0 12-t kapunk. Ez az állítás igaz, tehát a 2x 1 + 3x 2 12 egyenlőtlenség a pontot tartalmazó alsó félsíknak felel meg. (0; 0). Ezt tükrözi az ábrán látható grafikon. 1.1.

Hasonlóképpen, az LP probléma összes kényszere grafikusan ábrázolható.

A ZLP kényszerrendszer minden egyenlőtlenségének megoldása egy félsík, amely tartalmazza a határvonalat és annak egyik oldalán helyezkedik el. A félsíkok metszéspontját, amelyek mindegyikét a rendszer megfelelő egyenlőtlensége határozza meg, a megengedett megoldások tartományának vagy definíciós tartománynak nevezzük. Emlékeztetni kell arra, hogy a megvalósítható megoldások tartománya kielégíti a nem-negativitás feltételeit ( x j 0, j = 1, 2, …, n). A definíciós tartományba tartozó bármely pont koordinátái érvényes megoldást jelentenek a feladatra.

A célfüggvény szélsőértékének megtalálásához LP feladatok grafikus megoldása során egy gradiensvektort használunk, amelynek koordinátái a célfüggvény parciális deriváltjai, azaz.

Ez a vektor a célfüggvény leggyorsabb változásának irányát mutatja. Egyenes vonal 1 x 1 + 2 x 2 = f(x 0), merőleges a gradiens vektorra, a célfüggvény szintvonala. A szintvonal bármely pontján a célfüggvény ugyanazt az értéket veszi fel. Tegyük egyenlővé a célfüggvényt egy állandó értékkel "A". Az „a” értékét megváltoztatva párhuzamos egyenesek családját kapjuk, amelyek mindegyike a célfüggvény szintvonala.

A lineáris függvény szintvonalának fontos tulajdonsága, hogy a vonal párhuzamos eltolásakor az egyik irányba a szint csak nő, másik irányba tolva pedig csak csökken.

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

Grafikus módszer a PPP döntése a következő szakaszokból áll.

1. A PLP megengedhető megoldásainak poligonális régiója (ADS) létrejön.

2. A célfüggvény (TF) gradiensvektorát az ODR-hez tartozó x 0 pontban szerkesztjük meg:

3. A c 1 x 1 + c 2 x 2 = a (a egy állandó érték) szintvonal - a gradiens vektorra merőleges egyenes - ennek a vektornak az irányába mozog f maximalizálása esetén (x 1, x 2) amíg ki nem hagyja az ODR-t. A terület határpontja (vagy pontjai) ennél a mozgásnál az f(x 1, x 2) maximális pont.

4. A maximális pont koordinátáinak megtalálásához elegendő két olyan egyenes egyenletet megoldani, amelyeket a megfelelő korlátozásokból kapunk, és megadjuk a maximális pontot a metszéspontban. Az eredményül kapott pontban talált f(x 1, x 2) érték a maximum.

Az f(x 1, x 2) függvény minimalizálásakor (maximálásakor) a szintvonal a gradiensvektorral ellentétes irányba mozog. Ha a szintvonalnak megfelelő egyenes nem hagyja el mozgása során az ODR-t, akkor az f(x 1, x 2) függvény minimuma (maximuma) nem létezik.

Ha a szintvonal párhuzamos a probléma bármely funkcionális megszorításával, akkor a CF optimális értéke ennek a kényszernek két optimális sarokpont között elhelyezkedő bármely pontján elérhető lesz, és ennek megfelelően ezen pontok bármelyike ​​az optimális megoldás a ZLP. Az LP problémák grafikus megoldásának lehetséges helyzeteit a táblázat mutatja be. 1.3.

1.3. táblázat

Tekintsük a lineáris programozási feladatok grafikus megoldását a következő példa segítségével.

Példa 1.1. Varróvállalkozás gyártásának tervezése (öltönyökkel kapcsolatos probléma).

A tervek szerint kétféle - férfi és női - öltöny kerül forgalomba. Egy női öltönyhöz 1 m gyapjú, 2 m lavsan és 1 fő/nap munka szükséges. Férfi öltönyhöz - 3,5 m gyapjú, 0,5 m lavsan és 1 fő/nap munka. Összesen 350 m gyapjú, 240 m lavsan és 150 ember/nap munka. Meg kell határozni, hogy az egyes típusokból hány öltönyt kell készíteni a maximális profit eléréséhez, ha a női öltöny eladásából származó nyereség 10 pénzegység, a férfi öltönyből pedig 20 pénzegység. Nem szabad megfeledkezni arról, hogy legalább 60 férfi öltönyt kell varrni.

Vezessük be a következő jelölést: x 1 - a női öltönyök száma; x 2 – férfi öltönyök száma. A női öltönyök eladásából származó nyereség 10x 1, a férfi öltönyök értékesítéséből pedig 20x 2, azaz. a célfüggvény maximalizálása szükséges:

10x1 + 20x2

A feladatmegszorítások alakja a következő:

x 1 + x 2 150,

2 x 1 + 0,5 x 2 240,

x 1 + 3,5 x 2 350,

x 2 60,

x 1 0.

Az első munkakorlátozás x 1 + x 2 150. Az x 1 + x 2 = 150 egyenes áthalad a (150; 0) és (0; 150) pontokon (1.2. ábra).

A lavsan második megszorítása 2 x 1 + 0,5 x 2 240. A 2 x 1 + 0,5 x 2 = 240 egyenes áthalad a (120; 0) és (0; 480) pontokon. Harmadik korlátozás a gyapjúra x 1 + 3,5 x 2 350. Adjunk hozzá egy negyedik korlátozást a férfi öltönyök számára x 2 60. Ennek az egyenlőtlenségnek a megoldása az x 2 = 60 egyenes felett fekvő félsík. 1.3 a megvalósítható megoldások tartománya árnyékolt. Az optimum felé irányuló mozgás irányának meghatározásához gradiens vektort szerkesztünk, melynek koordinátái a célfüggvény parciális deriváltjai, azaz.

Egy ilyen vektor megalkotásához a pontot (10;20) az origóval kell összekötni. A célfüggvény maximalizálásánál a gradiensvektor irányába, minimalizáláskor pedig az ellenkező irányba kell elmozdulni. A kényelem kedvéért létrehozhat egy vektorral arányos vektort. Tehát az ábrán. Az 1.4 a gradiens vektort mutatja (30;60).

Az optimum felé irányuló mozgás irányának meghatározásához gradiens vektort szerkesztünk, melynek koordinátái a célfüggvény parciális deriváltjai, azaz.

Esetünkben addig mozgatjuk a szintvonalat, amíg az elhagyja a megvalósítható megoldások tartományát. A szélső, sarokponton elérjük a célfüggvény maximumát. Ennek a pontnak a koordinátáinak megtalálásához elegendő két olyan egyenes egyenletet megoldani, amelyeket a megfelelő korlátozásokból kapunk, és megadjuk a maximális pontot a metszéspontban:

x 1 + 3,5 x 2 = 350,

x 1 + x 2 = 150.

Innentől könnyű leírni a megoldást az eredeti ZLP-hez: max f(x)= 2300, és az x 1 = 70 és x 2 = 80 értékeknél érhető el (lásd az 1.4. ábrát).

1.3. TECHNOLÓGIA LINEÁRIS PROGRAMOZÁSI PROBLÉMÁK MEGOLDÁSÁRA A MEGOLDÁSKERESŐ BŐVÍTMÉNY HASZNÁLATÁVAL EXCEL KÖRNYEZETBEN

1.3.1. Általános információ az Excel táblázatkezelővel való munkáról

Nézzünk meg néhány szempontot az Excel táblázatkezelő processzorral való munkavégzés során, amelyek leegyszerűsítik az optimalizálási problémák megoldásához szükséges számításokat. Az asztali processzor az szoftver, amelyet a táblázatos adatok feldolgozásának automatizálására terveztek.

Excel képernyőelemek. Az Excel indítása után egy táblázat jelenik meg a képernyőn, melynek megjelenését az 1.5. ábra mutatja.

Ezt a képet munkalapnak nevezzük. Ez egy sorokból és oszlopokból álló rács, amelyek metszéspontjai celláknak nevezett téglalapokat alkotnak. A munkalapok adatbevitelre, számítások elvégzésére, információs bázis rendszerezésére stb. Az Excel ablak a főbb programelemeket jeleníti meg: címsor, menüsor, állapotsor, ablakvezérlő gombok.

Képletekkel való munka. A táblázatkezelő programok képleteket használnak számos különböző számítás elvégzésére. Az Excel segítségével gyorsan létrehozhat egy képletet. A képlet három fő részből áll:

1) egyenlőségjel;

2) értékek vagy hivatkozások halmaza azokban a cellákban, amelyekkel a számításokat végzik;

3) operátorok.

4) Ha nincs egyenlőségjel, akkor az Excel nem képletként, hanem cellába beírt adatként értelmezi az adatokat. A képletek beírhatók közvetlenül egy cellába vagy a képletsorba – akár szöveg, akár számok. Ebben az esetben a következő lépéseket kell végrehajtania:

· válassza ki azt a cellát, amelyben a képletet tartalmaznia kell, és írja be a jelet (=);

· írjon be egy operátort vagy műveleti jelet;

· válasszon ki egy másik cellát a képletben;

· Nyomja meg az Enter billentyűt.

A beírt képlet megjelenik a képletsorban, a számítás eredménye pedig a cellában.

Függvények használata képletekben. A képletek bevitelének megkönnyítése érdekében használhatja az Excel függvényeket. A függvények az Excelbe beépített képletek. Az Excel sok képletet tartalmaz. szerint vannak csoportosítva különféle típusok: logikai, matematikai, mérnöki, statisztikai stb.

Egy adott képlet aktiválásához kattintson a Beszúrás, a Funkciók gombokra. A bal oldalon megjelenő Funkcióvarázsló ablak a függvénytípusok listáját tartalmazza. A típus kiválasztása után a jobb oldalon megjelenik a funkciók listája. Egy funkciót a megfelelő névre kattintva lehet kiválasztani.

Különféle funkciók végrehajtása különböző típusok számítások bizonyos szabályok szerint. Ha egy függvény egyetlen objektum egy munkalapcellában, akkor egy (=) jellel kezdődik, amelyet a függvény neve követ, majd a függvény argumentumai zárójelben.

A Find a Solution egy Excel-bővítmény, amely lehetővé teszi az optimalizálási problémák megoldását. Ha a Megoldás keresése parancs nem érhető el az Eszközök menüben, akkor le kell töltenie ezt a kiegészítőt. Válassza az Eszközök => Kiegészítők parancsot, és aktiválja a Megoldás keresése bővítményt. Ha ez a bővítmény nincs a Kiegészítők párbeszédpanelen, akkor a panelre kell lépnie Windows kezelés, kattintson a Programok telepítése és törlése ikonra, és használja az Excel (vagy az Office) telepítőjét a Megoldás keresése bővítmény telepítéséhez.

Az Eszközök => Megoldás keresése parancsok kiválasztása után megjelenik a Megoldás keresése párbeszédpanel.

A Megoldás keresése párbeszédpanelen három fő lehetőség van;

Állítsa be a célcellát.

Változó sejtek.

Korlátozások.

Először ki kell töltenie a Célcella beállítása mezőt. A Megoldás keresése eszköz minden feladatában a munkalap egyik cellájában lévő eredmény optimalizálva van. A célcella képletek segítségével kapcsolódik a munkalap többi cellájához. A Megoldás keresése eszköz olyan képleteket használ, amelyek eredményt adnak a célcellában az ellenőrzéshez lehetséges megoldások. Választhat, hogy megkeresi-e a célcella legkisebb vagy legnagyobb értékét, vagy beállíthat egy adott értéket.

A Megoldás keresése eszköz második fontos opciója a Cellák megváltoztatása opció. Itt adhatja meg azokat a cellákat, amelyek értéke megváltozik, hogy optimalizálja az eredményt a célcellában. A megoldás megtalálásához legfeljebb 200 módosítható cellát adhat meg. Ezekkel a cellákkal szemben két fő követelmény van: nem tartalmazhatnak képleteket, és az értékük változásának tükröződnie kell a célcellában bekövetkezett eredmény változásában. Más szavakkal, a célsejt a módosítandó sejtektől függ.

A harmadik paraméter, amelyet meg kell adni a Megoldás keresése lapon, a korlátozások.

A probléma megoldásához szüksége van:

1) jelölje meg azoknak a celláknak a címét, amelyekbe a döntés eredménye kerül (cserélhető cellák);

2) adja meg a kezdeti adatokat;

3) a célfüggvény függőségét bevezetni;

4) függőséget vezet be a korlátozásokhoz,

5) futtassa a Megoldások keresése parancsot;

6) rendeljen hozzá egy cellát a célfüggvényhez (set target cell);

7) korlátozásokat vezet be;

8) adjon meg paramétereket a PLP megoldásához.

Tekintsük a megoldási technológiát az 1.1. példa feltételeivel (az öltönyfeladat).

A probléma gazdasági és matematikai modellje

Legyen x 1 a női öltönyök száma; x 2 - a férfi öltönyök száma,

10 x x 1 + 20 x x 2 max

A feladatmegszorítások alakja a következő:

x 1 + x 2 150 - munkakorlátozás;

2 x 1 + 0,5 x x 2240 - korlát a lavsanra;

x 1 + 3,5 x x 2 350 - gyapjúkorlát;

x 2 60 - a férfi öltönyök korlátozása;

x 1 0 - a női öltönyök korlátozása.

1. Adja meg azoknak a celláknak a címét, amelyekbe a megoldás eredménye kerül (cserélhető cellák).

Jelölje x 1 , x 2 az egyes típusok öltönyeinek számát. Problémánkban az = (x 1, x 2) vektor optimális értékei az A2:B2 cellákba kerülnek, a célfüggvény optimális értéke az S3 cellába.

2. Adja meg a kezdeti adatokat.

Adja meg a kezdeti feladatadatokat az ábra szerint. 1.6.

3. Vezessen be függőséget a célfüggvényre.

· Vigye a kurzort az „ÉNy” cellába, a cella kiválasztásra kerül.

· Vigye a kurzort az eszköztár Funkcióvarázsló gombjára.

· Enter. A Funkcióvarázsló 1/2. lépése párbeszédpanel jelenik meg a képernyőn.

· A Funkciók ablakban válassza ki a SUMPRODUCT sort (1.7. ábra). A képernyőn

· megjelenik a SUMPRODUCT párbeszédpanel (1.8. ábra).

· Írja be az 1. tömb sorába A2:B2.

· Írja be az AZ:VZ értéket a 2. tömb sorába.

Az 1. tömb kerül felhasználásra a megszorítások függőségének megadásakor, ezért abszolút hivatkozni kell erre a tömbre. ábrán. Az 1.9. ábra azt mutatja, hogy egy függvény került az SZ cellába.

5. Adja meg a megszorítások függőségeit (1.10. ábra).

· Helyezze a kurzort az ÉNy-i cellába.

· Az eszköztáron található a Másolás vágólapra gomb.

· Helyezze a kurzort a C4 cellába.

· Helyezze a kurzort a C5 cellába.

· Az eszköztáron a Beillesztés a vágólapról gomb.

· Helyezze a kurzort a Sat cellába.

· Az eszköztáron a Beillesztés a vágólapról gomb.

· Helyezze a kurzort a C7 cellába.

· Az eszköztáron kattintson a Beillesztés a vágólapról gombra. (A C4-C7 cellák tartalmát ellenőrizni kell. Információkat kell tartalmazniuk, amint az például az 1.11. ábrán látható; a C5 cella tartalma példaként látható.)

· A Menü sorban vigye az egérmutatót a Szolgáltatásra. A kibontott menüben válassza a Megoldás keresése parancsot. Megjelenik a Megoldás keresése párbeszédpanel (1.12. ábra).

5. Futtassa a Megoldás keresése parancsot.

6. Rendeljen cellát a célfüggvényhez (állítsa be a célcellát), adja meg a módosítandó cellák címét.

· Vigye a kurzort a Set target cell sorba.

· Írja be a $С$3 cella címét.

· Adja meg a célfüggvény típusát a probléma körülményeitől függően. Ehhez vegye figyelembe, hogy a célfüggvény mivel egyenlő - Maximális érték vagy Minimális érték.

· Helyezze a kurzort egy sorba a cellák megváltoztatásával.

· Adja meg a szükséges változók címét A$2:B$2 (1.13. ábra).

7. Korlátozások bevezetése.

· Vigye az egérmutatót a Hozzáadás gombra. Megjelenik a Kényszer hozzáadása párbeszédpanel.

· Írjon be egy korlátozó jelet.

· A Korlátozás sorba írja be a $D$4 címet (1.14. ábra).

· Vigye az egérmutatót a Hozzáadás gombra. Újra megjelenik a Korlátozás hozzáadása párbeszédpanel.

· Adja meg a probléma fennmaradó kényszereit a fent leírt algoritmus segítségével.

· Az utolsó korlátozás megadása után kattintson az OK gombra. Megjelenik a képernyőn a Megoldás keresése párbeszédpanel a megadott feltételekkel (1.15. ábra).

8. Adja meg a paramétereket a lineáris programozási probléma megoldásához.

· A párbeszédpanelen vigye az egérmutatót a Beállítások gombra. Megjelenik a képernyőn a Megoldás keresési opciói párbeszédpanel (1.16. ábra).

· Jelölje be a Lineáris modellben (ez biztosítja a szimplex módszer használatát) és a Nem negatív értékek négyzeteit.

· Vigye az egérmutatót az OK gombra. A Megoldás keresése párbeszédpanel jelenik meg a képernyőn.

· Vigye az egérmutatót a Futtatás gombra.

Rövid idő múlva megjelenik a megoldáskeresési eredmények párbeszédpanel és az eredeti táblázat AZ:VZ kitöltött cellákkal az x i értékekhez és az SZ c cellához. maximális érték célfüggvény (1.17. ábra).

Ha megadja a Stabilitás jelentéstípust, további információkat kaphat az optimális megoldásról (1.18. ábra).

A feladat megoldása eredményeként a válasz érkezett: 70 darabot kell varrni. női öltönyök és 80 db. férfi öltönyök, hogy a maximális profit 2300 USD.

1.4. KETŐSSÉG A LINEÁRIS PROGRAMOZÁSI PROBLÉMÁKBAN. AZ ELÉRT OPTIMÁLIS MEGOLDÁSOK ELEMZÉSE

1975-ben honfitársunk, L.V. Kantorovich közgazdasági Nobel-díjat kapott (T. Koopmans amerikai közgazdászsal együtt) az erőforrások optimális felhasználásának elméletének kidolgozásáért (lásd 1. melléklet).

Minden lineáris programozási problémához szorosan kapcsolódik egy másik lineáris probléma, az úgynevezett kettős; az eredeti problémát eredetinek vagy közvetlennek nevezzük. Az eredeti és a kettős probléma közötti kapcsolat különösen abban rejlik, hogy az egyik megoldása közvetlenül a másik megoldásából nyerhető.

Az y i kettős probléma változóit objektíven meghatározott becsléseknek, vagy kettős becsléseknek, vagy erőforrások „áraknak”, vagy árnyékáraknak nevezzük.

A kettős páros feladatok mindegyike valójában független lineáris programozási probléma, és a másiktól függetlenül megoldható.

A kettős probléma az eredetihez képest a következő szabályok szerint áll össze:

1) az eredeti probléma célfüggvénye maximumként, a duális probléma célfüggvénye pedig minimumként van megfogalmazva, míg a maximális feladatban a funkcionális megszorítások minden egyenlőtlensége (), a minimális feladatban formájuk van ( );

2) az A mátrixot, amely az eredeti probléma rendszerében az ismeretlen kényszerek együtthatóiból áll, és egy hasonló A T mátrixot a duális feladatban, transzponálással kapjuk meg egymástól;

3) a duális probléma változóinak száma megegyezik az eredeti feladatban szereplő funkcionális megszorítások számával, a duális probléma rendszerében a korlátozások száma pedig az eredeti feladatban lévő változók számával;

4) a duális probléma célfüggvényében szereplő ismeretlenek együtthatói az eredeti feladat kényszerrendszerében lévő szabad tagok, a duális probléma megszorításaiban a jobb oldalak pedig a duális feladatban lévő ismeretlenek együtthatói. az eredeti objektív funkciója; j 0.

A bemutatott két probléma szimmetrikus kettős problémapárt alkot. A kölcsönösen kettős problémákra vonatkozó főbb megállapításokat a következő két tétel tartalmazza.

Első dualitástétel. Kölcsönösen kettős problémák esetén az egymást kizáró esetek egyike fordul elő.

1. A közvetlen és a kettős problémákban vannak optimális megoldások,
ebben az esetben a célfüggvények értékei az optimális megoldásokon alapulnak
mérkőzés

2. A direkt feladatban a megengedett halmaz nem üres, és a célfüggvény ezen a halmazon nincs felülről korlátos. Ebben az esetben a kettős probléma üres megengedett halmaza lesz.

3. Duális feladatban a megengedett halmaz nem üres, és a célfüggvény ezen a halmazon nincs alulról korlátos. Ebben az esetben a közvetlen probléma megengedett halmaza üresnek bizonyul.

4. Mindkét vizsgált probléma üres megengedett halmazokkal rendelkezik.

Második dualitástétel (komplementer nem-merevségi tétel). Legyen = ( x 1, x 2,..., x n) a direkt probléma megengedhető megoldása, a = (y 1,y 2,...,y t) a duális probléma megengedhető megoldása. Ahhoz, hogy ezek optimális megoldást jelentsenek a direkt, illetve a kettős problémákra, szükséges és elegendő, ha a következő összefüggések fennállnak:

Az (1.4) és (1.5) feltételek lehetővé teszik, hogy az egyik kölcsönösen kettős probléma optimális megoldásának ismeretében egy másik probléma optimális megoldását megtaláljuk.

Vegyünk egy másik tételt, amelynek következtetéseit a továbbiakban felhasználjuk.

Becslési tétel. Az y i változók értékei a kettős probléma optimális megoldásában a direkt probléma kényszerrendszerének (egyenlőtlenségei) szabad tagjainak b i értékére gyakorolt ​​hatásának becsléseit jelentik.

A szimplex módszerrel megoldva a ZLP-t egyszerre oldjuk meg a duális ZLP-t. Az y i duális probléma változóit objektíven meghatározott becsléseknek nevezzük.

Tekintsük a kettős probléma közgazdasági értelmezését a szőnyegproblémával példaként.

1. példa .2. A szőnyegprobléma megfogalmazásának felhasználásával hajtsa végre a következő feladatokat.

1. Fogalmazza meg a szőnyegek problémájának ökonómiai-matematikai modelljét a maximális előállítási összköltségre a táblázat adatainak felhasználásával! 1.1.

2. A Megoldás keresése segítségével keressen egy gyártási tervet, amelynél a gyártás összköltsége maximális lesz.

3. Fogalmazzon meg egy közgazdasági-matematikai modellt a duálprobléma és a szőnyegprobléma között!

4. Keresse meg a duális probléma optimális tervét a dualitástételek segítségével, magyarázza el X 1 és X 4 nullával való egyenlőségét!

5. A Solution Search protokollok segítségével végezze el az eredeti probléma optimális megoldásának elemzését.

6. Határozza meg, hogyan változik a teljes költség és a gyártási terv, ha a cső élettartama 12 egységgel nő.

1. Fogalmazzuk meg a probléma közgazdasági és matematikai modelljét.

Jelöljük X 1, X 2, X 3, X 4-el az egyes típusok szőnyegeinek számát. A célfüggvénynek van formája

F(X) = 3X 1 + 4X 2 + 3X 3 + X 4 max,

és az erőforrások korlátai

7Х 1 + 2Х 2 + 2Х 3 + 6X 4 80,

5Х 1 + 8Х 2 + 4 X 3+ ZH 4 480,

2X 1 + 4 X 2 + X 3 + 8X 4 130,

X 1, X 2, X 3, X 4 0.

2. Keresse meg az optimális kiadási tervet.

Oldjuk meg a problémát egy bővítmény segítségével Excel keresés megoldásokat. A feladat megoldásának technológiáját a jelmezfeladatnál részletesen tárgyaltuk. Problémánkban az X = (X 1, X 2, X 3, X 4) vektor optimális értékei a VZ:EZ cellákba kerülnek, a célfüggvény optimális értéke - a cellába. F4.

Adjuk meg a kezdeti adatokat. Először is leírjuk a célfüggvényt a SUMPRODUCT (1.19. ábra) függvény segítségével. Ezután a korlátozások bal oldali részeihez írunk be adatokat. A Megoldás keresése mezőben megadjuk a célfüggvény irányát, a keresett változók címét, és korlátozásokat adunk hozzá. Megjelenik a képernyőn a Megoldás keresése párbeszédpanel a megadott feltételekkel (1.20. ábra).

A probléma megoldásához szükséges paraméterek megadása után kattintson a Végrehajtás gombra. A képernyőn megjelenik egy üzenet, hogy megoldást találtunk (1.21. ábra).

A kapott megoldás azt jelenti, hogy a maximális bevétel 150 ezer rubel. egy gyár gyártáskor 30 db második típusú és 10 db harmadik típusú szőnyeget kaphat. Ebben az esetben az erőforrások „munkaerő” és „felszerelés” teljes mértékben felhasználásra kerül, és 480 kg fonalból (erőforrás „alapanyag”) 280 kg kerül felhasználásra.

Jelentés készítése a megoldáskeresés eredményei alapján. Az Excel lehetővé teszi a megoldáskeresés eredményeinek jelentés formájában történő bemutatását (1.4. táblázat). Háromféle ilyen jelentés létezik:

· Eredmények (válasz). A jelentés tartalmazza a cél és a módosított cellák kezdeti és végső értékét, valamint további információkat a korlátozásokról.

· Stabilitás (érzékenység). Egy jelentés, amely információkat tartalmaz a megoldás érzékenységéről a módosítandó cellákban vagy a kényszerképletek kis változásaira.

· Korlátok. Az érintett és célsejtek forrás- és célértékein kívül a jelentés tartalmazza azon értékek felső és alsó korlátait, amelyeket a befolyásoló sejtek el tudnak fogadni, ha a korlátozások teljesülnek.

Tekintsünk több módszert a lineáris programozási problémák megoldására.

A grafikus módszer meglehetősen egyszerű és intuitív két változós lineáris programozási problémák megoldására. A feladat megvalósítható megoldásainak és TF-einek geometriai ábrázolásán alapul.

A lineáris programozási feladat minden egyenlőtlensége meghatároz egy-egy félsíkot a koordinátasíkon, az egyenlőtlenségrendszer egésze pedig a megfelelő síkok metszéspontját. Ezen félsíkok metszéspontjainak halmazát régiónak nevezzük elfogadható megoldások (ODR). Az ODR mindig egy konvex alak, azaz. a következő tulajdonsággal: ha ehhez az ábrához két A és B pont tartozik, akkor a teljes AB szakasz hozzátartozik. Az ODR grafikusan ábrázolható konvex sokszöggel, korlátlan számú konvex sokszögterülettel, szegmenssel, sugárral vagy egy ponttal. Ha az (1) probléma kényszerrendszere inkonzisztens, akkor az ODS üres halmaz.

A fentiek mind érvényesek arra az esetre is, amikor a korlátozási rendszer (1) egyenlőségeket tartalmaz, hiszen minden egyenlőség

két egyenlőtlenség rendszereként ábrázolható

A rögzített értékű digitális szűrő egy egyenest határoz meg a síkon. L értékeinek megváltoztatásával párhuzamos egyenesek családját kapjuk, amelyeket vonalaknak nevezünk szint.

Ennek az az oka, hogy L értékének megváltoztatása csak a tengelyen lévő szintvonal által levágott szakasz hosszában (kezdeti ordináta) változik, és az egyenes szögegyütthatója állandó marad. Ezért a megoldáshoz elegendő az egyik szintvonal megépítése, önkényesen megválasztva L értékét.

A CF együtthatók koordinátáival rendelkező vektor a és az egyes szintvonalakra merőleges. A vektor iránya egybeesik az iránnyal a CF növelése, ami az fontos pont problémák megoldására. Irány a CF csökkenése ellentétes a vektor irányával.

A grafikus módszer lényege a következő. Az ODR-ben lévő vektor irányában (iránnyal szemben) az optimális pontot keresi. Az optimális pont az a pont, amelyen a szintvonal áthalad, amely megfelel a függvény legnagyobb (legkisebb) értékének. Az optimális megoldás mindig az ODD határán található, például az ODD sokszög utolsó csúcsánál, amelyen a célvonal át fog haladni, vagy annak teljes oldalán.

A lineáris programozási problémák optimális megoldásának keresése során a következő helyzetek lehetségesek: létezik egyedi megoldás a problémára; végtelen sok megoldás létezik (alternatíva); A TF nem korlátozott; a megvalósítható megoldások tartománya egyetlen pont; a problémának nincs megoldása.

1. ábra A probléma kényszereinek és TF-einek geometriai értelmezése

Tekintsünk egy technikát az LP problémák grafikus módszerrel történő megoldására.

• 1) az (1) feladat megszorításaiban cserélje ki az egyenlőtlenség jeleit pontos egyenlőségjelekre, és állítsa össze a megfelelő egyeneseket;
• 2) keresse meg és árnyékolja be az (1) feladat egyenlőtlenségi kényszerei által megengedett félsíkokat. Ehhez be kell cserélnie egy pont koordinátáit [például (0;0)] egy adott egyenlőtlenségbe, és ellenőriznie kell a kapott egyenlőtlenség igazságát.

Ha az egyenlőtlenség igaz, akkor árnyékolnunk kell az ezt a pontot tartalmazó félsíkot; egyébként (az egyenlőtlenség hamis) árnyékolni kell azt a félsíkot, amelyik nem tartalmazza az adott pontot.

Mivel és nem negatívnak kell lennie, megengedett értékeik mindig a tengely felett és a tengelytől jobbra lesznek, pl. az első kvadránsban.

Az egyenlőségi megszorítások csak azokat a pontokat engedik meg, amelyek a megfelelő egyenesen vannak. Ezért szükséges az ilyen egyenes vonalakat kiemelni a grafikonon;

• 3) határozza meg az ODR-t a sík részeként, amely egyidejűleg minden engedélyezett területhez tartozik, és válassza ki. SDT hiányában a problémának nincs megoldása;
• 4) ha az ODR nem egy üres halmaz, akkor meg kell alkotnia a célvonalat, pl. bármelyik szintvonal (ahol L tetszőleges szám, például többszörös, és ez kényelmes a számításokhoz). Az építési mód hasonló a közvetlen kényszerek felépítéséhez;
• 5) alkossunk egy vektort, amely a (0;0) pontban kezdődik és a pontban ér véget. Ha a célegyenes és a vektor helyesen van megszerkesztve, akkor merőlegesek lesznek;
• 6) a maximális CF keresésekor a célvonalat kell mozgatni a vektor iránya, amikor a minimális CF - ellen keresünk vektor irányok. Az ODR utolsó csúcsa a mozgás irányában a CF maximumának vagy minimumának pontja lesz. Ha ilyen pont(ok) nem léteznek, akkor arra következtethetünk CF tovább sok tervek felülről (ha a maximumot keresik) vagy alulról (amikor a minimumot keresik);
• 7) határozza meg a digitális szűrő max (min) pontjának koordinátáit és számítsa ki a digitális szűrő értékét. Az optimális pont koordinátáinak kiszámításához meg kell oldani azon egyenesek egyenletrendszerét, amelyek metszéspontjában található.

A szimplex módszer az egyik első olyan speciális optimalizálási módszer, amely lineáris programozási problémák megoldására irányul, míg az egyszerű és irányított felsorolási módszerekkel szinte minden optimalizálási probléma megoldható. Az amerikai G. Dantzig javasolta 1951-ben. A szimplex módszer abból áll, hogy a kényszerek konvex poliédere mentén haladunk csúcstól csúcsig, amelyben minden lépésben javítják a célfüggvény értékét az optimum eléréséig.

A szimplex módszer az iteratív számítások tipikus példája a legtöbb optimalizálási probléma megoldásában. A szimplex módszer számítási sémájában egy rendezett folyamatot valósítanak meg, amelyben valamilyen kezdeti megengedhető sarokpontból (általában az origóból) kiindulva egymást követő átmeneteket hajtanak végre az egyik megengedett szélső pontból a másikba, amíg az optimális megoldásnak megfelelő pont meg nem születik. talált (2. ábra).

2. ábra Átmenet egyik csúcsból a másikba

A szimplex módszert, amelyet szakirodalmunkban a terv szekvenciális javításának módszereként is ismernek, először Danzig G. dolgozta ki 1947-ben. Ez a módszer lehetővé teszi az egyik megvalósítható alapmegoldásról a másikra való áttérést, és oly módon, hogy a a célfüggvény értékei folyamatosan nőnek. Ennek eredményeként véges számú lépésben megtaláljuk az optimális megoldást.

Simplex módszer - univerzális megoldási módszer lineáris rendszer egyenletek vagy egyenlőtlenségek és lineáris funkcionális.

Algoritmus a ZLP megoldásához szimplex módszerrel.

A szimplex módszer magában foglalja az elfogadható értékek tartományának összes csúcsának szekvenciális keresését annak érdekében, hogy megtalálják azt a csúcsot, ahol a függvény szélső értéket vesz fel. Az első szakaszban valamilyen megoldást találnak, amelyet minden következő lépésben javítanak. Ezt a megoldást nevezzük alapnak.

Nézzük meg a szimplex módszer lépéseit.

• 1) az összeállított táblázatban először meg kell nézni a szabad tagokat tartalmazó oszlopot. Ha vannak benne negatív elemek, akkor át kell lépni a második lépésre, ha nem, akkor az ötödikre;
• 2) a második lépésben el kell dönteni, hogy melyik változót zárjuk ki a bázisból és melyiket vegyük be a szimplex tábla újraszámításához. Ehhez nézze át a szabad kifejezéseket tartalmazó oszlopot, és keressen benne negatív elemet. A negatív elemet tartalmazó vonalat vezetőnek nevezzük. Ebben megtaláljuk a maximális negatív elemet modulusban, a megfelelő oszlop a slave. Ha a szabad kifejezések között vannak negatív értékek, de nem a megfelelő sorban, akkor egy ilyen táblázatnak nem lesz megoldása. A szabad kifejezések oszlopában elhelyezkedő bevezető sorban lévő változót kihagyjuk a bázisból, a bevezető oszlopnak megfelelő változót pedig a bázisból. Az 1. táblázat egy szimplex táblára mutat példát.

Asztal 1

Példa szimplex táblára

• 3) a harmadik lépésben speciális képletekkel újraszámoljuk a teljes szimplex táblát;
• 4) ha az újraszámítás után negatív elemek maradtak a szabad kifejezések oszlopában, akkor lépjen az első lépésre, ha nincs ilyen elem, akkor az ötödikre;
• 5) ha elérte az ötödik lépést, akkor talált egy elfogadható megoldást. Ez azonban nem jelenti azt, hogy az optimális. Csak akkor lesz optimális, ha az F-sztring minden eleme pozitív. Ha ez nem így van, akkor javítani kell a megoldáson, amelyhez a következő újraszámításhoz a következő algoritmussal keressük meg a vezető sort és oszlopot. Kezdetben az F karakterláncban találjuk meg a minimális negatív számot, kivéve a függvény értékét. Az ezzel a számmal rendelkező oszlop lesz a vezető. A vezető sor megtalálásához megkeressük a megfelelő szabad tag és a vezető oszlop elemének arányát, feltéve, hogy ezek pozitívak. A minimális arány lehetővé teszi a vezetővonal meghatározását. A táblázatot a képletek segítségével újra kiszámoljuk, pl. folytassa a 3. lépéssel;
• 6) ha nem lehet megtalálni a vezető sort, mivel a vezető oszlopban nincsenek pozitív elemek, akkor a probléma megvalósítható megoldásainak tartományában a függvény nincs fent és F max ->?. Ha az F sorban és a szabad tagok oszlopában minden elem pozitív, akkor megtaláltuk az optimális megoldást.