Lineáris optimalizálás
Ez a fejezet a lineáris optimalizálás (LOP) komplex témájának bevezetése. Ebben az összefüggésben felmerül néhány kérdés, amelyet fokozatosan szeretnénk tisztázni.
- Mit jelent a "lineáris optimalizálás" kifejezés?
- Hogyan lehet a problémát matematikailag megfogalmazni?
- A lineáris optimalizálás ismert felhasználási esetei?
- Milyen megoldási módszerek vannak?
- Milyen megoldások lehetségesek?
Ebben a fejezetben a magyarázataink egy lineáris optimalizálásra korlátozódnak, két változóval.
Mi a lineáris optimalizálás?
A lineáris optimalizálás használható (praktikus) Lineáris egyenlőtlenségi rendszerek alkalmazása meg kell érteni. Ennek megfelelõen az elõzõ cikk, a "Lineáris egyenlõtlenségek rendszere két változóval", ennek a fejezetnek az alapja.
A lineáris optimalizálás azon matematikai folyamatokkal foglalkozik, amelyek meghatározzák a lineáris függvény legnagyobb vagy legkisebb értékét. Ezeket általában további feltételek korlátozzák.
A lineáris optimalizálás egy lineáris függvény korlátozással történő maximalizálásával vagy minimalizálásával foglalkozik.
Matematikai megfogalmazás
Az úgynevezett "lineáris program" (LP) a következő összetevőkből áll
Objektív funkció
A maximalizálandó (minimalizálandó) lineáris függvényt objektív függvénynek nevezzük. Az objektív függvényben előforduló változókat (\ (x \), \ (y \)) döntési változóknak nevezzük.
Korlátozások (korlátozások)
\ (\ begina_1x + b_1y & \ leq c_1 \\ a_2x + b_2y & \ leq c_2 \\\ qquad \ vdots \ qquad \ vdots \\ a_nx + b_ny & \ leq c_n \ end \)
(Nemnegativitási feltétel)
A legtöbb gyakorlati probléma esetén a döntési változók nulla feletti vagy azzal egyenlő értékekre korlátozódnak. Ennek oka az, hogy általában nem vállalhatnak negatív értékeket. Például egy vállalat nem képes "negatív számú" terméket előállítani.
Excursus: Mit jelent a nem negativitás feltétel grafikusan?
\ (x \ geq 0 \) grafikusan azt jelenti, hogy csak az y tengelytől jobbra eső terület releváns a megfigyeléshez.
\ (y \ geq 0 \) grafikusan azt jelenti, hogy csak az x tengely feletti terület a szempont.
Ha megfigyeljük mind a \ (x \ geq 0 \), mind a \ (y \ geq 0 \) értékeket, akkor azt találjuk, hogy csak a koordináta-rendszer 1. kvadrátja releváns a megfontolás szempontjából.
A színnel kiemelt terület tehát az a terület, amely teljesíti a nem negativitás feltételét.
Alkalmazások
A gyakorlatban a lineáris optimalizálásra számos alkalmazás létezik. Ezek némelyikét példákkal részletesebben elmagyarázzuk.
Mivel a nem negativitás feltételeinek a következő példákban teljesülniük kell, a grafikus megfontolás a koordináta-rendszer 1. negyedére korlátozódik.
Ezen a ponton erősen ajánlott áttekinteni az "Egyenlőtlenségek lineáris rendszerei két változóval" fejezetet.
a) termelési probléma
Két különböző típusú kábelt gyártanak egy gyárban, és 150 euróért (A típus) és 100 euróért (B típus) adnak el 100 méterenként. Az A típusú kábelekhez 16 kg műanyag és 4 kg réz szükséges. A B típusú kábelekhez 6 kg műanyag és 12 kg réz szükséges. Az előállított B mennyisége nem lehet nagyobb, mint az A mennyiségének kétszerese. Ezenkívül az anyagellátás jelenleg csak 252 kg műanyag és 168 kg réz.
A kétféle kábel melyik mennyisége maximalizálja a vállalat forgalmát, figyelemmel a korlátokra?
1.) A feladat egyértelmű összeállítása
2.) A probléma matematikai megfogalmazása
| Objektív funkció | \ (z (x, y) = 150x + 100y \ quad \ rightarrow \ quad \ text \) |
| Korlátok | \ (\ kezdődik 16x + 6y & \ leq 252 \\ 4x + 12y & \ leq 168 \ end \) |
| . és \ (y \ leq 2x \) miatt van: | \ (2x - y \ geq 0 \) |
| Nemnegativitási feltétel | \ (x \ geq 0 \) \ (y \ geq 0 \) |
3.) Grafikus megfontolás
Szeretné az 1. másodlagos feltételt
\ (16x + 6y \ leq 252 \)
koordinátarendszerbe rajzolva meg kell oldani az \ (y \) \ (6y \ leq - 16x + 252 \) egyenlőtlenséget
\ (y \ leq - \ fracx + 42 \)
majd az egyenlőtlenséget egyenes egyenletként értelmezi
\ (y = - \ fracx + 42 \)
A színes terület azt a területet jelöli, amely teljesíti az 1. másodlagos feltételt.
Szeretné a 2. másodlagos feltételt
\ (4x + 12y \ leq 168 \)
koordinátarendszerbe rajzolva meg kell oldani az \ (y \) \ (12y \ leq - 4x + 168 \) egyenlőtlenséget
\ (y \ leq - \ fracx + 14 \)
majd az egyenlőtlenséget egyenes egyenletként értelmezi
\ (y = - \ fracx + 14 \)
A színes terület azt a területet jelöli, amely teljesíti a 2. másodlagos feltételt.
A 3. másodlagos feltétel:
"Az előállított B mennyisége nem lehet nagyobb, mint az A mennyiségének kétszerese."
. vagy matematikailag megfogalmazva: \ (y \ leq 2x \)
A színes terület azt a területet jelöli, amely teljesíti a 3. másodlagos feltételt.
A Megoldáskészlet a lineáris egyenlőtlenségi rendszer.
\ (16x + 6y \ leq 252 \)
\ (4x + 12y \ leq 168 \)
\ (y \ leq 2x \)
.a szomszédos grafikán színes színnel van kiemelve.
Most már tudjuk, hogy grafikusan hogyan néz ki a megvalósítható megoldáskészlet. A következő lépés az optimális megoldás keresése. Ezt grafikusan vagy számítással meghatározhatjuk.
4.1) Határozza meg az optimális megoldást (matematikai)
Mivel az optimális megoldás megegyezik a megoldás területének sarokpontjával, először leolvastuk: \ (P_1 (0,0) \); \ (P_2 (6.12) \); \ (P_3 (12,10) \); \ (P_4 (15,75; 0) \);
Most beletesszük a pontokat a célfüggvénybe, és meghatározzuk a maximumot.
\ (z (0.0) = 150 \ szer 0 + 100 \ szor 0 = 0 € \)
\ (z (6.12) = 150 \ szor 6 + 100 \ szor 12 = 2100 € \]
\ (z (12.10) = 150 \ cdot 12 + 100 \ cdot 10 = 2800 € \ qquad \ rightarrow \ quad \ text \]
\ (z (15,75; 0) = 150 \ szor 15,75 + 100 \ szor 0 = 2362,50 € \)
válasz:
A gyár maximalizálja eladásait, a korlátok betartása mellett, amikor 12 x 100 m-es A és 10 x 100 m-es B-kábelt gyárt.
4.2) Határozza meg az optimális megoldást (grafikusan)
Grafikusan megtalálható maximális, az objektív függvény behúzásával, majd párhuzamos eltolásával, amíg az egyenes nem jelöli utolsó sarokpont az oldat területének. Ezután az utolsó sarok felel meg az optimális megoldásnak.
Először oldjuk meg az \ (y \) célfüggvényét.
\ (z (x, y) = 150x + 100y = 0 \)
\ (100y = -150x \)
\ (y = -1,5x \)
.hogy felhívják őket a koordinátarendszerbe. Ezután az egyeneset párhuzamosan mozgatjuk, amíg el nem érjük a megoldás területének utolsó sarkát.
Az optimumot (itt: maximum) a grafikonon egy piros pont mutatja.
b) Szállítási probléma
Egy légitársaság repülési kapcsolatot akar létesíteni két város között. A cél 1600 ember és 96 tonna rakomány szállítása egy bizonyos idő alatt. Jelenleg kétféle repülőgép áll rendelkezésre: 11 A típusú és 8 B típusú repülőgép, az A típus repülésenként 4000 euróba kerül, 200 ember és 6 tonna rakomány szállítására alkalmas. A B típus repülésenként 1000 euróba kerül, és 100 embert és 15 tonna rakományt képes szállítani.
Mint minden típusú sok repülőgép, a légitársaság is korlátozások alatt fog működni, hogy minimalizálja költségeit?
1.) A feladat egyértelmű összeállítása
\ kezdődik
& \ text & \ text & \ text \\ \ hline
\ text & 200 & 100 & 1600 \\ \ hline
\ text & 6 & 15 & 96 \\ \ hline
\ text & 4000 & 1,000 &
\ end
2.) A probléma matematikai megfogalmazása
| Objektív funkció | \ (z (x, y) = 4000x + 1000y \ quad \ rightarrow \ quad \ text \) |
| Korlátok | \ (\ kezdődik 200x + 100 év és \ geq 1600 \\ 6x + 15y & \ geq 96 \ end \) |
| . vonatkozik: | \ (x \ leq 11 \) \ (y \ leq 8 \) |
| Nemnegativitási feltétel | \ (x \ geq 0 \) \ (y \ geq 0 \) |
3.) Grafikus megfontolás
Szeretné az 1. másodlagos feltételt
\ (200x + 100y \ geq 1600 \)
koordinátarendszerbe rajzolva meg kell oldani az \ (y \) \ (100y \ geq -200x + 1600 \) egyenlőtlenséget
\ (y \ geq -2x + 16 \)
majd az egyenlőtlenséget egyenes egyenletként értelmezi
\ (y = -2x + 16 \)
A színes terület azt a területet jelöli, amely teljesíti az 1. másodlagos feltételt.
Szeretné a 2. másodlagos feltételt
\ (6x + 15y \ geq 96 \)
koordinátarendszerbe rajzolva meg kell oldani az \ (y \) \ (15y \ geq - 6x + 96 \) egyenlőtlenséget
\ (y \ geq - 0,4x + 6,4 \)
majd az egyenlőtlenséget egyenes egyenletként értelmezi
\ (y = - 0,4x + 6,4 \)
A színes terület azt a területet jelöli, amely teljesíti a 2. másodlagos feltételt.
A 3. másodlagos feltétel
\ (x \ leq 11 \)
párhuzamos az y tengellyel a tengely metszéspontjával \ (x = 11 \).
A színes terület azt a területet jelöli, amely teljesíti a 3. másodlagos feltételt.
A 4. másodlagos feltétel
\ (y \ leq 8 \)
párhuzamos az x tengellyel a tengely metszéspontjával \ (y = 8 \).
A színes terület azt a területet jelöli, amely teljesíti a 4. másodlagos feltételt.
A Megoldáskészlet a lineáris egyenlőtlenségi rendszer.
\ (200x + 100y \ geq 1600 \)
\ (6x + 15y \ geq 96 \)
\ (x \ leq 11 \)
\ (y \ leq 8 \)
.a szomszédos grafikán színes színnel van kiemelve.
Most már tudjuk, hogy grafikusan hogyan néz ki a megvalósítható megoldáskészlet. A következő lépés az optimális megoldás keresése. Ezt grafikusan vagy számítással meghatározhatjuk.
4.1) Határozza meg az optimális megoldást (matematikai)
Mivel az optimális megoldás megfelel a megoldás területének sarokpontjának, először leolvastuk: \ (P_1 (6,4) \); \ (P_2 (4,8) \); \ (P_3 (11,8) \); \ (P_4 (11.2) \);
Most betesszük a pontokat a célfüggvénybe, és meghatározzuk a minimumot.
\ (z (6.4) = 4000 \ x 6 + 1000 x 4 = 28 000 € \)
\ (z (4.8) = 4,000 4-szer 4 + 1000-szer 8 = 24 000 € \ qquad \ rightarrow \ quad \ text \)
\ (z (11,8) = 4000 \ 11-szer + 1000-szer 8 = 52 000 € \)
\ (z (11.2) = 4000 \ 11-szer + 1000-szer 2 = 46 000 € \)
válasz:
A légitársaság a korlátozásoknak megfelelően minimalizálja költségeit, ha 4 A típusú és 8 B típusú repülőgépet üzemeltet.
4.2) Határozza meg az optimális megoldást (grafikusan)
Grafikusan megtalálható minimális, az objektív függvény behúzásával, majd párhuzamos eltolásával, amíg az egyenes nem jelöli első sarokpont az oldat területének. Ezután az első sarok megfelel az optimális megoldásnak.
Először oldjuk meg az \ (y \) célfüggvényét.
\ (z (x, y) = 4000x + 1000y = 0 \)
\ (1000y = -4000x \)
\ (y = -4x \)
.hogy felhívják őket a koordinátarendszerbe. Ezután az egyeneset párhuzamosan mozgatjuk, amíg el nem érjük a megoldási terület első sarkát.
Az optimumot (itt: minimum) egy piros pont mutatja a grafikán.
Lehetséges megoldások
A fenti példákban már láthattuk, hogy egy optimalizálási problémának egyedi megoldása lehet. Az is lehetséges, hogy több megoldás létezik, vagy egyáltalán nincs megoldás.
A következőkben talál egy grafikus példát az egyes megoldásokra. A cél mindig a minimum megtalálása.
Világos optimális megoldás
. Két példát már részletesen megvizsgáltunk fent.
Végtelen számú optimális megoldás
Ha az objektív függvény párhuzamos egy korlátozással, akkor több megoldás is létezik. Grafikusan ez azt jelenti, hogy a párhuzamos eltolással az objektív függvény egybeesik ezzel a korlátozási vonallal.
Nem optimális megoldás
Vannak esetek, amikor nincs optimális megoldás.
Következtetés
Ami a "lineáris optimalizálás" témáját illeti, gyakran szóproblémákkal kell megküzdenünk. Fontos, hogy elolvassa a feladat lényegét, és összefoglalja egy táblázatban. Ennek az egyértelmű ábrázolásnak a segítségével a későbbi matematikai megfogalmazás rendkívül leegyszerűsödik.
Ha a lineáris programnak csak két változója van, akkor egy grafikus elemzés alkalmas az optimalizálási feladat megoldására.
- A maximális grafikusan megtalálható úgy, hogy behúzza a célfüggvényt, és párhuzamosan eltolja, amíg el nem éri a utolsó sarokpont az oldat területének.
- A minimális grafikusan megtalálható úgy, hogy behúzza a célfüggvényt, és párhuzamosan eltolja, amíg el nem éri a első sarokpont az oldat területének.
A lineáris optimalizálási feladatokra elvileg lehet világos, végtelen vagy nincs (optimális) megoldás.
Kettőnél több változóval rendelkező lineáris programok esetén a grafikus nézet (többnyire) nem lehetséges. A gyakorlatban ebben az esetben az optimum kiszámítása az úgynevezett szimplex algoritmus segítségével történik.
A nevem Andreas Schneider, és 2013 óta teljes munkaidőben működtetem az ingyenes és díjnyertes www.mathebibel.de matematikai tanulási platformot. Havonta legfeljebb 1 millió diák, szülő és tanár nézi meg állításaimat. Szinte minden nap új tartalmat teszek közzé. Iratkozzon fel hírlevelemre, és 46 e-könyvemből 3-at ingyen kapjon meg!
PS: Már láttam a #MatheAmMontag sorozatom aktuális részét?