A gazdasági problémák megoldásának alapja a matematikai modell.
Tervezés matematikai modell magába foglalja:matematikai modell A probléma a probléma lényegét leíró matematikai összefüggések összessége.
Feladatváltozók az X1, X2, Xn mennyiségeket nevezzük, amelyek teljes mértékben jellemzik gazdasági folyamat. Általában vektorként írják fel: X=(X 1 , X 2 ,...,X n).
A korlátozások rendszere A feladatok egyenletek és egyenlőtlenségek halmaza, amelyek leírják a vizsgált probléma korlátozott erőforrásait.
cél funkció feladatot feladatváltozók függvényének nevezzük, amely a feladat minőségét jellemzi, és amelynek extrémumát meg kell találni.
Általában egy lineáris programozási probléma a következőképpen írható fel:
Ez a bejegyzés a következőket jelenti: keresse meg a célfüggvény szélsőértékét (1) és a megfelelő X=(X 1 , X 2 ,...,X n) változókat, feltéve, hogy ezek a változók kielégítik a (2) és nem kényszerrendszert. -negativitási feltételek (3) .
Elfogadható megoldás Egy lineáris programozási feladat (terve) bármely n-dimenziós X=(X 1 , X 2 ,...,X n) vektor, amely kielégíti a kényszerek és a nem-negativitás feltételrendszerét.
A feladatformák megvalósítható megoldásainak (terveknek) összessége megvalósítható megoldások sora(ODR).
Az optimális megoldás Egy lineáris programozási feladat (terv) olyan megvalósítható megoldása (terv), amelyben a célfüggvény egy szélsőséget ér el.
Feltétel: n féle termék gyártásához m féle erőforrást használnak fel. Készíts egy matematikai modellt.
Ismert:
Tervet kell készíteni olyan termékek előállítására, amelyek maximális profitot biztosítanak az erőforrások (alapanyagok) adott korlátozása mellett.
Megoldás:
Bevezetjük az X=(X 1 , X 2 ,...,X n) változók vektorát, ahol x j (j = 1,2,...,n) a j-edik típusú termelési volumen. termék.
Az i-edik típusú erőforrás költségei adott mennyiségű x j termék előállításához egyenlőek a ij x j -vel, ezért az erőforrások felhasználásának korlátozása minden típusú termék előállításához a következőképpen alakul:
A j-edik típusú termék értékesítéséből származó nyereség c j x j , tehát a célfüggvény egyenlő:
Válasz- A matematikai modell így néz ki:
Általános esetben egy lineáris programozási feladatot úgy írnak le, hogy az egyenletek és az egyenlőtlenségek is kényszerek, és a változók lehetnek nem negatívak vagy tetszőlegesen változóak.
Abban az esetben, ha minden megszorítás egyenlet, és minden változó kielégíti a nem-negativitás feltételét, a lineáris programozási feladatot ún. kánoni.
Koordináta-, vektor- és mátrixjelöléssel ábrázolható.
A kanonikus lineáris programozási probléma koordinátajelölésben a következő formában jelenik meg:
A kanonikus lineáris programozási probléma mátrixjelölésben a következő formában jelenik meg:
Gyakran lineáris programozási problémákat használnak, amelyeket szimmetrikusnak neveznek, és amelyek mátrixjelölésben a következő formában vannak:
A lineáris programozási problémák megoldásának legtöbb módszerében azt feltételezik, hogy a kényszerrendszer egyenletekből és a változók nem-negativitásának természetes feltételeiből áll. A közgazdasági problémák modelljeinek összeállításakor azonban a korlátok főként egyenlőtlenségi rendszer formájában jönnek létre, ezért szükséges, hogy az egyenlőtlenségek rendszeréből egyenletrendszerbe tudjunk lépni.
Ezt így lehet megtenni:Vegyünk egy a 1 x 1 +a 2 x 2 +...+a n x n ≤b lineáris egyenlőtlenséget, és adjunk a bal oldalához valamilyen x n+1 értéket úgy, hogy az egyenlőtlenség az a 1 x 1 +a 2 x 2 + egyenlőség legyen. ...+a n x n +x n+1 =b. Ráadásul ez az x n+1 érték nem negatív.
Nézzünk meg mindent egy példával.
26.1. példaCsökkentse a lineáris programozási problémát kanonikus formára:
Megoldás:
Térjünk át a célfüggvény maximumának megtalálásának problémájára.
Ehhez megváltoztatjuk a célfüggvény együtthatóinak előjeleit.
A kényszerrendszer második és harmadik egyenlőtlenségének egyenletté alakításához nemnegatív további változókat vezetünk be x 4 x 5 (ezt a műveletet D betűvel jelöljük a matematikai modellen).
Az x 4 változó a második egyenlőtlenség bal oldalán egy "+" jellel kerül beírásra, mivel az egyenlőtlenség alakja "≤".
Az x 5 változót a harmadik egyenlőtlenség bal oldalán a "-" jellel kell beírni, mivel az egyenlőtlenség "≥" alakú.
Az x 4 x 5 változók együtthatóval kerülnek be a célfüggvénybe. egyenlő nullával.
A problémát kanonikus formában írjuk le.
A lineáris programozási probléma (LPP) egy lineáris függvény legnagyobb (vagy legkisebb) értékének megtalálása egy konvex poliéder halmazon.
A szimplex módszer egy lineáris programozási probléma megoldásának módszere. A módszer lényege, hogy megtaláljuk a kiindulási megvalósítható tervet, majd a tervet addig javítjuk, amíg egy adott konvex poliéder halmazban a célfüggvény maximális (vagy minimum) értékét el nem érjük, vagy a probléma megoldhatatlanná válik.
Tekintsük a következő lineáris programozási problémát kanonikus formában:
| (1) |
| (2) |
| (3) |
Mint fentebb említettük, egy kanonikus formában írt feladathoz, ha a mátrix oszlopvektorai között A Van m egység és lineárisan független, közvetlenül megadhatja a referenciatervet. Azonban számos kanonikus formában írt lineáris programozási probléma esetén, amelyek támogatási tervekkel rendelkeznek, a mátrix oszlopvektorai között A nem mindig ott m szinguláris és lineárisan független. Tekintsük a következő feladatot:
Legyen szükséges, hogy megtaláljuk a függvény maximumát
feltételek mellett
hol vannak az elsők n elemek nullák. Változók 
mesterségesnek nevezik. Vektorok oszlopai
  | (28) |
alkotják az úgynevezett mesterséges alapot m-dimenziós vektortér.
Mivel a kiterjesztett probléma támogatási tervvel rendelkezik, megoldása szimplex módszerrel kereshető meg.
Tétel 4. Ha az optimális tervben 
mesterséges változók kiterjesztett probléma (24)−(26) értékei 
, Azt 
a (21)−(23) probléma optimális terve.
Így, ha a kiterjesztett probléma megtalált optimális tervében a mesterséges változók értéke nulla, akkor megkapjuk az eredeti probléma optimális tervét. Foglalkozzunk részletesebben a kiterjesztett probléma megoldásának megtalálásával.
A célfüggvény értéke a referenciatervvel (27):
Ezt észrevesszük F(X)és két független részből áll, amelyek közül az egyik attól függ M, míg a másik nem.
Számítás után F(X)és ezek értékeit, valamint a kiterjesztett feladat kiinduló adatait a szimplex táblába a fentiek szerint beírjuk. Az egyetlen különbség az adott táblázat egy sorral többet tartalmaz, mint egy normál szimplex tábla. Ezzel egy időben ( m+1)-edik sorba tedd a nem tartalmazó együtthatókat M, és ( m+2) sor − együtthatók at M.
Amikor egyik referenciatervről a másikra lépünk, a bázisba egy vektor kerül be, amely abszolút értékben a legnagyobb negatív számnak felel meg ( m+2) sorok. A bázisból kizárt mesterséges vektort nincs értelme újra bevezetni a bázisba. Más referenciatervre váltáskor előfordulhat, hogy a bázisból egyetlen mesterséges vektor sem kerül kizárásra. A szimplex tábla újraszámítása az egyik referenciatervről a másikra való átmenet során a szimplex módszer szokásos szabályai szerint történik (lásd fent).
Az iteratív folyamat az m+2 sor olyan hosszú, mint az elemek m+2 sor a változóknak megfelelően 
nem lesz negatív. Ebben az esetben, ha a mesterséges változókat kizárjuk az alapból, akkor a kiterjesztett probléma talált terve megfelel az eredeti probléma valamilyen alaptervének.
m+2 sor, oszlop x 0 negatív, akkor az eredeti feladatnak nincs megoldása.
Ha nem minden mesterséges változót kizárunk a bázisból és az elemből m+2 sor, oszlop x 0 egyenlő nullával, akkor az eredeti feladat támogatási terve degenerált és a bázis legalább egy mesterséges bázisvektort tartalmaz.
Ha az eredeti feladat több egységvektort tartalmaz, akkor azokat bele kell foglalni a mesterséges bázisba.
Ha az iterációk során m A +2 sor már nem tartalmaz negatív elemeket, akkor az iteratív folyamat a következővel folytatódik m+1 sor, amíg meg nem találjuk a kiterjesztett probléma optimális tervét, vagy a probléma megoldhatatlanná válik.
Így a (21)−(23) lineáris programozási probléma mesterséges alapú módszerrel történő megoldásának folyamata a következő fő lépéseket tartalmazza:
A lineáris programozási problémák online megoldásához használja a számológépet
A matematikai modell összetevői
A gazdasági problémák megoldásának alapja a matematikai modell.
A matematikai modell elkészítése a következőket tartalmazza:matematikai modell A probléma a probléma lényegét leíró matematikai összefüggések összessége.
Feladatváltozók X1, X2, Xn mennyiségeknek nevezzük, amelyek teljes mértékben jellemzik a gazdasági folyamatot. Általában vektorként írják fel: X=(X1, X2,...,Xn).
A korlátozások rendszere A feladatok egyenletek és egyenlőtlenségek halmaza, amelyek leírják a vizsgált probléma korlátozott erőforrásait.
cél funkció feladatot feladatváltozók függvényének nevezzük, amely a feladat minőségét jellemzi, és amelynek extrémumát meg kell találni.
Általában egy lineáris programozási probléma a következőképpen írható fel:
Ez a bejegyzés a következőket jelenti: keresse meg a célfüggvény (1) szélsőértékét és a megfelelő X=(X1, X2,...,Xn) változókat, feltéve, hogy ezek a változók kielégítik a (2) kényszerrendszert és a nem-negativitást. feltételek (3).
Elfogadható megoldás Egy lineáris programozási probléma (terve) bármely n-dimenziós X=(X1, X2,...,Xn) vektor, amely kielégíti a kényszerek és nem-negativitási feltételek rendszerét.
A feladatformák megvalósítható megoldásainak (terveknek) összessége megvalósítható megoldások sora(ODR).
Példa matematikai modell összeállítására Az erőforrások (nyersanyagok) felhasználásának feladataAz optimális megoldás Egy lineáris programozási feladat (terv) olyan megvalósítható megoldása (terv), amelyben a célfüggvény egy szélsőséget ér el.
Feltétel: n féle termék gyártásához m féle erőforrást használnak fel. Készíts egy matematikai modellt.
Ismert:
Tervet kell készíteni olyan termékek előállítására, amelyek maximális profitot biztosítanak az erőforrások (alapanyagok) adott korlátozása mellett.
Megoldás:
Vezessünk be egy X=(X1, X2,...,Xn) változók vektorát, ahol xj (j = 1,2,...,n) a j-edik típusú termék termelési volumene.
Az i-edik típusú erőforrás költségei adott mennyiségű xj termék előállításához megegyeznek aijxj-vel, tehát az erőforrások felhasználásának korlátozása minden típusú termék előállítására a következőképpen alakul:
A j-edik típusú termék értékesítéséből származó nyereség egyenlő cjxj-vel, tehát a célfüggvény egyenlő:
Válasz- A matematikai modell így néz ki:
Lineáris programozási probléma kanonikus formája
Általános esetben egy lineáris programozási feladatot úgy írnak le, hogy az egyenletek és az egyenlőtlenségek is kényszerek, és a változók lehetnek nem negatívak vagy tetszőlegesen változóak.
Abban az esetben, ha minden megszorítás egyenlet, és minden változó kielégíti a nem-negativitás feltételét, a lineáris programozási feladatot ún. kánoni.
Koordináta-, vektor- és mátrixjelöléssel ábrázolható.
A kanonikus lineáris programozási probléma koordinátajelölésben a következő formában jelenik meg:
A kanonikus lineáris programozási probléma mátrixjelölésben a következő formában jelenik meg:
Gyakran lineáris programozási problémákat használnak, amelyeket szimmetrikusnak neveznek, és amelyek mátrixjelölésben a következő formában vannak:
Általános lineáris programozási probléma redukálása kanonikus formára
A lineáris programozási problémák megoldásának legtöbb módszerében azt feltételezik, hogy a kényszerrendszer egyenletekből és a változók nem-negativitásának természetes feltételeiből áll. A közgazdasági problémák modelljeinek összeállításakor azonban a korlátok főként egyenlőtlenségi rendszer formájában jönnek létre, ezért szükséges, hogy az egyenlőtlenségek rendszeréből egyenletrendszerbe tudjunk lépni.
Ezt így lehet megtenni:Vegyünk egy a1x1+a2x2+...+anxn≤b lineáris egyenlőtlenséget, és adjunk a bal oldalához valamilyen xn+1 értéket úgy, hogy az egyenlőtlenség az a1x1+a2x2+...+anxn+xn+1=b egyenlőség legyen. Ráadásul ez az xn+1 érték nem negatív.
Nézzünk meg mindent egy példával.
26.1. példaCsökkentse a lineáris programozási problémát kanonikus formára:
Megoldás:
Térjünk át a célfüggvény maximumának megtalálásának problémájára.
Ehhez megváltoztatjuk a célfüggvény együtthatóinak előjeleit.
A kényszerrendszer második és harmadik egyenlőtlenségének egyenletté alakításához x4 x5 nemnegatív további változókat vezetünk be (ezt a műveletet a matematikai modellen D betűvel jelöljük).
Az x4 változó a második egyenlőtlenség bal oldalán egy "+" jellel kerül beírásra, mivel az egyenlőtlenség "≤" formájú.
Az x5 változót a harmadik egyenlőtlenség bal oldalán a "-" jellel kell beírni, mivel az egyenlőtlenség "≥" alakú.
Az x4 x5 változók együtthatóval kerülnek be a célfüggvénybe. egyenlő nullával.
A problémát kanonikus formában írjuk:
Az általános lineáris programozási probléma (GLP) a következőképpen fogalmazódik meg - keresse meg a probléma változóit x 1 , x 2 , ..., x n , amelyek a célfüggvény extrémumát adják
A lineáris programozási probléma (LPP) megvalósítható megoldása (terve) bármely n-dimenziós vektor x=(x 1 , x 2 , ..., x n) az egyenlőségek és egyenlőtlenségek kényszerrendszerének kielégítése. A probléma megvalósítható megoldásainak halmaza alkotja a megvalósítható megoldások tartományát D.
Egy lineáris programozási probléma optimális megoldása (terve) olyan megvalósítható megoldás, amelynél a célfüggvény Z(x) szélsőséget ér el.
A kanonikus lineáris programozási feladatnak (KZLP) van a formája
(1.2)
Abban különbözik az OZLP-től, hogy a kényszerrendszere csak egyenletrendszer, és minden változó nem negatív.
Az OZLP átvezetése a ZLP kanonikus formájába:
Ahhoz, hogy az eredeti minimalizálási feladatot maximalizálási feladatra cseréljük (vagy fordítva, a maximalizálási feladatot egy minimalizálási feladatra), elegendő a célfüggvényt "-1"-gyel megszorozni, és megkeresni az eredményül kapott függvény maximumát (minimumát);
Ha a megszorítások között egyenlőtlenségek vannak, akkor további nemnegatív változók bevezetésével x n +1 ≥ 0 egyenlőségekké alakítják át:
egyenlőtlenség aén 1 x 1 +…+a ban ben x n≥ b i helyébe egyenlőség lép aén 1 x 1 +…+a ban ben x n+ x n+1 = bén,
egyenlőtlenség aén 1 x 1 +…+a ban ben x n≤ b i helyébe egyenlőség lép aén 1 x 1 +…+a ban ben x n+ x n+1 = bén ;
Ha valamilyen változó x k nincs előjel-korlátozása, akkor azt (a célfüggvényben és az összes korlátozásban) két új nemnegatív változó különbsége helyettesíti: x k = x" k – x” k , Ahol x" k ≥ 0. x” k ≥ 0.
Grafikus módszer az LLP megoldására két ismeretlennel
A két ismeretlennel rendelkező ZLP alakja:
A módszer a megvalósítható megoldások területének grafikus ábrázolásának lehetőségén és az optimális megoldás megtalálásán alapul.
A probléma megvalósítható megoldásainak területe (SDE) egy konvex sokszög, és a megoldási területek metszéspontjaként (közös részeként) van megszerkesztve a probléma kényszereinek minden egyenlőtlenségére.
Egyenlőtlenség megoldási terület aén 1 x 1 +aén 2 x 2 ≤ b i egyike annak a két félsíknak, amelyhez az egyenes aén 1 x 1 +aén 2 x 2 = b i , ennek az egyenlőtlenségnek megfelelően osztja a koordinátasíkot. Annak meghatározásához, hogy a két félsík közül melyik a megoldási terület, elegendő bármely olyan pont koordinátáját behelyettesíteni az egyenlőtlenségbe, amely nem fekszik az osztóegyenesen:
Ha az egyenlőtlenség igaz, akkor a megoldási tartomány az ezt a pontot tartalmazó félsík;
Ha az egyenlőtlenség nem igaz, akkor a megoldási tartomány az a félsík, amelyik nem tartalmazza ezt a pontot.
Szintvonalak segítségével találjuk meg az optimális megoldást a megvalósítható megoldások között.
A szintvonal egy egyenes Val vel 1 x 1 +Val vel 2 x 2 = l, Ahol l= const, amelyen a feladat célfüggvénye állandó értéket vesz fel. Minden szintvonal párhuzamos egymással.
célfüggvény gradiens grad Z(x) határozza meg a normálvektort C = (c 1 , c 2) szintvonalak. A szintvonalakon a célfüggvény növekszik, ha a szintvonalakat a normális irányába mozgatjuk, és csökken az ellenkező irányba.
A referenciavonal olyan szintvonal, amelynek legalább egy közös pontja van az ODR-rel, és amelyhez képest az ODR az egyik félsíkban van. A probléma ODD-jének legfeljebb két támogatási vonala van.
Az LLP optimális megoldása az ODD sokszög sarokpontjában található referenciavonalon található. A ZLP-nek egyedi megoldása van, ha a referenciavonal áthalad az ODT egy sarokpontján, végtelen számú megoldása van, ha a referenciavonal áthalad az ODT sokszög élén. A ZLP-nek nincs megoldása, ha az ODE üres halmaz (amikor a kényszerrendszer inkonzisztens), és ha az ODE a szélsőség irányában nem korlátos (a célfüggvény nem korlátos).
Algoritmus a grafikus módszerhez az LLP két ismeretlennel történő megoldásához:
Építsd meg az ODR-t.
Szerkesszünk normálvektort C = (c 1 , c 2) és szintvonal Val vel 1 x 1 +Val vel 2 x 2 = 0 az origón átmenő és a vektorra merőlegesen VAL VEL.
Mozgassa a szintvonalat a referenciavonalig a vektor irányába VAL VEL a feladatban max, vagy ellenkező irányban - a feladatban min.
Ha a szintvonal extrémum irányába való mozgatásakor az ODE a végtelenbe megy, akkor az LLP-nek a célfüggvény határtalansága miatt nincs megoldása.
Ha az LLP-nek van optimális megoldása, akkor annak megtalálásához oldja meg közösen az ODS-t határoló egyenesek egyenleteit, amelyek közös pontjai vannak a referenciavonallal. Ha a szélsőértéket két sarokponton érjük el, akkor az LLP-nek végtelen számú megoldása van az ODD éléhez, amelyet ezek a sarokpontok határolnak. BAN BEN ez az eset mindkét sarokpont koordinátáit kiszámítjuk.
Számítsa ki a célfüggvény értékét a szélsőpontban!
Simplex módszer az LLP megoldására
A szimplex módszer a következő elveken alapul:
Egy lineáris programozási probléma ODE-ja egy konvex halmaz véges sok sarokponttal;
Az LLP optimális megoldása az ODD egyik sarokpontja. Az ODS sarokpontjai algebrailag az LLP kényszerrendszerének néhány alapvető (támogató) megoldását reprezentálják.
Az LLP alap (támogató) megoldása ilyen elfogadható megoldás x 0 =(x 10 , x 20 , ..., x m 0 , 0,…0), amelyre a feltételvektorok (a rendszerben ismeretlen kényszerek együtthatóoszlopai) lineárisan függetlenek.
Nem nulla koordináták x 10 , x 20 , ..., x m 0 megoldások x A 0-t alapváltozóknak, a megoldás fennmaradó koordinátáinak nevezzük x 0 - szabad változók. A referenciamegoldás nullától eltérő koordinátáinak száma nem haladhatja meg a rangot r LLP kényszerrendszerek (lineárisan független egyenletek száma az LLP kényszerrendszerben). Továbbá feltételezzük, hogy az LLP kényszerrendszer lineárisan független egyenletekből áll, azaz. r = m.
A szimplex módszer jelentése az egyik LLP referenciamegoldásról a másikra (vagyis az egyikre) való átmenetben rejlik. sarokpont ODR a másikba) az extrémum irányába, és szakaszok sorozatából áll:
Keresse meg a kezdeti referenciamegoldást;
Az egyik referenciamegoldásról a másikra való átmenet végrehajtása;
Határozza meg az optimális megoldás elérésének kritériumát, vagy vonjon le következtetést a megoldás hiányára.
Végrehajtási algoritmusSimplex módszer ZLP
A szimplex módszer algoritmusa az egyik LLP referenciamegoldásból a másikba való átmenetet hajtja végre a célfüggvény extrémuma irányában.
Adjuk meg az LLP-t kanonikus formában (1.2) és a feltételt
b i ≥ 0, én=1,2,…,m, (1.3)
az (1.3) összefüggés mindig teljesíthető, ha a megfelelő egyenletet megszorozzuk "-1"-gyel negativitás esetén bén . Feltételezzük azt is, hogy az (1.2) feladat kényszereiben szereplő egyenletrendszer lineárisan független és rangja van r = m. Ebben az esetben a referenciamegoldásvektor rendelkezik m nem nulla koordináták.
Legyen az eredeti feladat (1.2), (1.3) redukálva arra a formára, ahol az alapváltozók x 1 , x 2 , ..., x m-t szabad változókkal fejezzük ki x m + 1 , x m + 2 , ..., x n
(1.4)
Ezen összefüggések alapján elkészítjük az 1. táblázatot
Asztal 1.
Az 1. táblázatot szimplex táblának nevezzük. Minden további átalakítás a táblázat tartalmának változásaihoz kapcsolódik.
Algoritmus -valimplex módszer:
1. Az utolsó sorban Z a szimplex táblák a min feladatban megtalálják a legkisebb pozitív elemet (a max feladatban a legkisebb negatív elemet), nem számítva a szabad tagot. Az ennek az elemnek megfelelő oszlopot feloldó oszlopnak nevezzük.
2. Számítsa ki a szabad tagok arányát a felbontóoszlop pozitív elemeihez (szimplex arány). Keresse meg a legkisebb szimplex arányt, amely megegyezik a megengedő karakterlánccal.
3. Az engedélyező egyenes és az engedélyező oszlop metszéspontjában van egy engedélyező elem.
4. Ha több azonos méretű szimplex reláció van, akkor válasszon ezek közül bármelyiket. Ugyanez vonatkozik a szimlex tábla utolsó sorának pozitív elemeire is.
5. Miután megtalálta az engedélyező elemet, lépjen a következő táblázatra. A feloldó sornak és oszlopnak megfelelő ismeretlen változók felcserélődnek. Ebben az esetben az alapváltozó szabad változóvá válik, és fordítva. Szimplex – a táblázatot a következőképpen konvertáljuk (2. táblázat):
2. táblázat
6. A 2. táblázat 1. táblázat engedélyező elemének megfelelő eleme egyenlő az engedélyező elem reciprokával.
7. A 2. táblázat sorának az 1. táblázat megengedő sorának elemeinek megfelelő elemeit úgy kapjuk meg, hogy az 1. táblázat megfelelő elemeit elosztjuk a megengedő elemmel.
8. A 2. táblázat oszlopának az 1. táblázat megengedő oszlopának elemeinek megfelelő elemeit úgy kapjuk meg, hogy az 1. táblázat megfelelő elemeit elosztjuk a megengedő elemmel, és ellenkező előjellel vesszük.
9. A fennmaradó elemek kiszámítása a szerint történik téglalap szabály: gondolatban rajzoljunk egy téglalapot az 1. táblázatba, amelynek egyik csúcsa egybeesik a feloldó elemmel (Re), a másik pedig a keresett elemmel; jelöljük az új 2. táblázatban szereplő elemet (Ne), a régi 1. táblázatban ugyanott lévő elemet pedig (Се). A maradék két A és B csúcs téglalappá egészíti ki az ábrát. Ekkor a kívánt Ne elem a 2. táblázatból egyenlő Ne = Ce - A*B/Re.
10. Optimalitási kritérium. Amint létrejön egy táblázat, amelyben a min feladat utolsó sorában lévő összes elem negatív (a max feladatban minden elem pozitív), a rendszer a szélsőértéket megtaláltnak tekinti. A célfüggvény optimális értéke megegyezik a Z sorban lévő szabad taggal, az optimális megoldást pedig az alapváltozókban lévő szabad tagok határozzák meg. Feltételezzük, hogy minden szabad változó nulla.
11. Ha a felbontás oszlopban minden elem negatív, akkor a problémának nincs megoldása (a minimumot nem érte el).
Mesterséges alapmódszer az LLP megoldásához
A szimplex módszer algoritmusa akkor alkalmazható, ha az LLP bármely referenciamegoldását választjuk, azaz az eredeti LLP-t (1.2) az (1.4) formára redukáljuk. A mesterséges alapmódszer eljárást kínál egy ilyen referenciamegoldás megalkotására.
A mesterséges bázismódszer mesterséges bázisváltozók bevezetésén alapul y 1 , y 2 ,…, y m
(1.5)
át lehet alakítani
(1.6)
Az (1.5) és (1.6) rendszerek egyenértékűek lesznek, ha mindegyik y én egyenlő lesz a nullával. Ahogy korábban, most is hiszünk ebben b én ≥ 0. Azért, hogy nál nél én 0-val egyenlők voltak, a feladatot úgy kell átalakítanunk, hogy az összes mesterséges alapváltozót y én szabad változókba ment át. Ilyen átmenetet a szimplex módszer algoritmusával lehet végrehajtani a további célfüggvény vonatkozásában
F(y) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 +d 2 x 2 +…+d n x n). (2.7)
A metódus kezdeti szimplex táblája a következő formában van
Először a szimplex táblát transzformáljuk a célfüggvényhez képest F(y) addig, amíg összehasonlító oldatot nem kapunk. A referencia-megoldás akkor jön létre, ha a következő kritérium teljesül: F(y) = 0 és az összes mesterséges változó nál nél én szabad változókká konvertálva. Ezután egy sor törlődik a szimplex táblából F(y) és oszlopok ehhez nál nél én és oldja meg a feladatot az eredeti célfüggvényre Z(x) amíg optimális megoldást nem kapunk.
Lineáris programozás A matematikának egy olyan ága, amely véges számú változó lineáris függvényének minimumának vagy maximumának meghatározására szolgáló módszereket tanulmányozza, feltéve, hogy a változók véges számú megszorítást teljesítenek, amelyek lineáris egyenletek vagy lineáris egyenlőtlenségek formájában vannak.
Így az általános lineáris programozási probléma (GLP) a következőképpen fogalmazható meg.
Keresse meg a valós változók olyan értékeit, amelyekhez objektív funkció
veszi a minimális értéket azon pontok halmazán, amelyek koordinátái megfelelnek korlátozások rendszere
Mint tudod, rendezett értékkészlet n változók , , … az n-dimenziós tér egy pontjával van ábrázolva. A továbbiakban erre a pontra úgy fogunk hivatkozni x=( , , … ).
Mátrix formában a lineáris programozási probléma a következőképpen fogalmazható meg:
, A egy méretű mátrix,
Pont x=( , , … ) amely minden feltételt kielégít, hívjuk érvényes pont . Az összes megengedett pont halmazát hívjuk érvényes terület .
Optimális megoldás (optimális terv) A lineáris programozási problémát megoldásnak nevezzük x=( , , … ), amely a megengedett tartományba tartozik, és amelyre a lineáris függvény K az optimális (maximum vagy minimum) értéket veszi fel.
Tétel. Egy lineáris programozási feladat kényszerrendszerének összes megengedett megoldásának halmaza konvex.
A ponthalmazt ún konvex , ha két pontjával együtt tartalmazza azok tetszőleges konvex lineáris kombinációját.
Pont x hívott konvex lineáris kombináció pontokat, ha a feltételek teljesülnek
A lineáris programozási probléma összes elfogadható megoldásának halmaza egy konvex poliéder tartomány, amelyre úgy fogunk hivatkozni. megoldások poliédere .
Tétel. Ha az LLP-nek van optimális megoldása, akkor a célfüggvény a döntési poliéder egyik csúcsán veszi fel a maximális (minimális) értéket. Ha a célfüggvény egynél több pontban veszi fel a maximális (minimális) értéket, akkor ezt az értéket bármely olyan pontban veszi fel, amely e pontok konvex lineáris kombinációja.
A rendszer számos megoldása között m a megoldási poliédert leíró lineáris egyenletek, az ún. alapmegoldások különböztethetők meg.
A rendszer alapmegoldása m n változós lineáris egyenleteket olyan megoldásnak nevezzük, amelyben minden n-m a nem alapváltozók nullával egyenlőek. A lineáris programozási feladatokban az ilyen megoldásokat ún elfogadható alapmegoldások (támogató tervek).
Tétel. Egy lineáris programozási feladat minden megengedett alapmegoldása megfelel a megoldási poliéder egy csúcsának, és fordítva, a megoldási poliéder minden csúcsának egy-egy megengedett alapmegoldás.
A fenti tételekből egy fontos következmény következik:
Ha egy lineáris programozási feladatnak van optimális megoldása, akkor az legalább egy megvalósítható alapmegoldással egybeesik.
Következésképpen egy lineáris programozási feladat lineáris célfüggvényének optimumát véges számú elfogadható alapmegoldása között kell keresni.
