Lineárna optimalizácia

Táto kapitola je určená ako úvod do komplexnej témy lineárnej optimalizácie (LOP). V tejto súvislosti vyvstávajú niektoré otázky, ktoré chceme postupne objasniť.

Čo sa rozumie pod pojmom „lineárna optimalizácia“?
Ako možno matematicky formulovať problém?
Známe prípady použitia lineárnej optimalizácie?
Aké metódy riešenia existujú?
Aké riešenia sú možné?

Naše vysvetlenia v tejto kapitole sú obmedzené na lineárnu optimalizáciu s dvoma premennými.

Čo je to lineárna optimalizácia?

Lineárnu optimalizáciu je možné použiť ako (praktickú) Aplikácia systémov lineárnej nerovnosti treba chápať. Predchádzajúci článok „Systémy lineárnych nerovností s dvoma premennými“ je základom pre túto kapitolu.

Lineárna optimalizácia sa zaoberá tými matematickými procesmi, ktoré určujú najväčšiu alebo najmenšiu hodnotu lineárnej funkcie. Spravidla sú obmedzené ďalšími podmienkami.

The lineárna optimalizácia sa zaoberá maximalizáciou alebo minimalizáciou lineárnej funkcie za určitých obmedzení.

Matematická formulácia

Takzvaný „lineárny program“ (LP) sa skladá z nasledujúcich komponentov

Objektívna funkcia

Lineárna funkcia, ktorá sa má maximalizovať (minimalizovať), sa nazýva objektívna funkcia. Premenné (\ (x \), \ (y \)) vyskytujúce sa v objektívnej funkcii sa nazývajú rozhodovacie premenné.

Obmedzenia (obmedzenia)

\ (\ 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 \)

(Podmienka nezápornosti)

Vo väčšine praktických problémov sú rozhodovacie premenné obmedzené na hodnoty väčšie alebo rovné nule. Dôvodom je to, že zvyčajne nemôžu predpokladať záporné hodnoty. Spoločnosť napríklad nemôže vyrábať „záporný počet“ výrobkov.

Exkurz: Čo znamená podmienka nezápornosti graficky?

\ (x \ geq 0 \) graficky znamená, že na zváženie je relevantná iba oblasť napravo od osi y.

\ (y \ geq 0 \) graficky znamená, že na zváženie je relevantná iba oblasť nad osou x.

Ak pozorujeme \ (x \ geq 0 \) aj \ (y \ geq 0 \), zistíme, že pre úvahu je relevantný iba 1. kvadrant súradnicového systému.

Farebne zvýraznená oblasť je teda oblasťou, ktorá spĺňa podmienku negativity.

Aplikácie

V praxi existuje množstvo aplikácií pre lineárnu optimalizáciu. Niektoré z nich budú podrobnejšie vysvetlené na príkladoch.

Pretože v nasledujúcich príkladoch musí byť splnená podmienka negativity, grafické zohľadnenie je obmedzené na 1. kvadrant súradnicového systému.

Na tomto mieste sa dôrazne odporúča pozrieť si znovu kapitolu „Lineárne systémy nerovnosti s dvoma premennými“.

a) výrobný problém

V továrni sa vyrábajú dva rôzne typy káblov, ktoré sa predávajú za 150 EUR (typ A) a 100 EUR (typ B) na 100 metrov. Káble typu A vyžadujú 16 kg plastu a 4 kg medi. Káble typu B vyžadujú 6 kg plastu a 12 kg medi. Množstvo vyrobeného B nesmie byť väčšie ako dvojnásobok množstva A. Okrem toho je dodávka materiálu v súčasnosti iba 252 kg plastu a 168 kg medi.

Ktoré množstvá týchto dvoch typov káblov maximalizujú obrat spoločnosti pri dodržaní obmedzení?

1.) Jasná kompilácia úlohy

2.) Matematická formulácia problému

Objektívna funkcia	\ (z (x, y) = 150x + 100y \ quad \ rightarrow \ quad \ text \)
Obmedzenia	\ (\ začať 16x + 6r & \ leq 252 \\ 4x + 12r & \ leq 168 \koniec\)
. a kvôli \ (y \ leq 2x \) máme:	\ (2x - y \ geq 0 \)
Podmienka nezápornosti	\ (x \ geq 0 \) \ (y \ geq 0 \)

3.) Grafická úvaha

Prajete si 1. sekundárny stav
\ (16x + 6r \ leq 252 \)
nakreslite súradnicový systém, musíte vyriešiť nerovnosť \ (y \) \ (6r \ leq - 16x + 252 \)
\ (y \ leq - \ fracx + 42 \)
a potom interpretujte nerovnosť ako priamku
\ (y = - \ fracx + 42 \)

Farebná oblasť označuje oblasť, ktorá spĺňa 1. sekundárnu podmienku.

Prajete si 2. sekundárny stav
\ (4x + 12r \ leq 168 \)
nakreslite súradnicový systém, musíte vyriešiť nerovnosť \ (y \) \ (12r \ leq - 4x + 168 \)
\ (y \ leq - \ fracx + 14 \)
a potom interpretujte nerovnosť ako priamku
\ (y = - \ fracx + 14 \)

Farebná oblasť označuje oblasť, ktorá spĺňa 2. sekundárnu podmienku.

3. sekundárna podmienka je:
„Množstvo vyrobeného B nesmie byť väčšie ako dvojnásobok množstva A.“
. alebo matematicky formulované: \ (y \ leq 2x \)

Farebná oblasť označuje oblasť, ktorá spĺňa 3. sekundárnu podmienku.

The Sada riešení systému lineárnej nerovnosti.
\ (16x + 6r \ leq 252 \)
\ (4x + 12r \ leq 168 \)
\ (y \ leq 2x \)
.je v susednej grafike farebne zvýraznená.

Teraz vieme, ako grafická realizovateľná sada riešení vyzerá. Ďalším krokom je hľadanie optimálneho riešenia. Môžeme to určiť buď graficky alebo výpočtom.

4.1) Určite optimálne riešenie (matematické)

Pretože optimum zodpovedá rohovému bodu oblasti riešenia, prečítali sme si ho najskôr: \ (P_1 (0,0) \); \ (P_2 (6,12) \); \ (P_3 (12,10) \); \ (P_4 (15,75; 0) \);

Teraz dáme body do objektívnej funkcie a určíme maximum.

\ (z (0,0) = 150 \ krát 0 + 100 \ krát 0 = 0 € \)

\ (z (6.12) = 150 \ krát 6 + 100 \ krát 12 = 2 100 € \)

\ (z (12.10) = 150 \ cdot 12 + 100 \ cdot 10 = 2 800 € \ qquad \ rightarrow \ quad \ text \)

\ (z (15,75; 0) = 150 \ krát 15,75 + 100 \ krát 0 = 2 362,50 € \)

odpoveď:
Továreň maximalizuje svoj predaj pri dodržaní obmedzení, ak vyrába kábel 12 x 100 m typu A a 10 x 100 m kábel typu B.

4.2) Určite optimálne riešenie (graficky)

Nájdete to graficky maximálne, vtiahnutím objektívnej funkcie a jej paralelným posúvaním, kým neoznačuje rovná čiara posledný rohový bod oblasti riešenia. Posledný roh potom zodpovedá optimálnemu riešeniu.

Najskôr vyriešime objektívnu funkciu pre \ (y \).
\ (z (x, y) = 150x + 100y = 0 \)
\ (100r = -150x \)
\ (y = -1,5x \)
.nakresliť ich do súradnicového systému. Potom posunieme priamku rovnobežne, až kým sa nedostaneme do posledného rohu oblasti riešenia.

Optimum (tu: maximum) je v grafe zobrazené červeným bodom.

b) Problém s prepravou

Letecká spoločnosť chce nadviazať letecké spojenie medzi dvoma mestami. Cieľom je prepraviť 1 600 ľudí a 96 ton nákladu v určitom časovom období. V súčasnosti sú k dispozícii dva typy lietadiel: 11 lietadiel typu A a 8 lietadiel typu B. Stojan typu A stojí 4 000 EUR za let a prepraví 200 ľudí a 6 ton nákladu. Typ B stojí 1 000 EUR za let a môže prepraviť 100 osôb a 15 ton nákladu.

Rovnako ako mnoho lietadiel každého typu, aj letecká spoločnosť bude pracovať v rámci obmedzení, aby minimalizovala svoje náklady?

1.) Jasná kompilácia úlohy

\ začať
& \ text & \ text & \ text \\ \ hline
\ text & 200 & 100 & 1600 \\ \ hline
\ text & 6 & 15 & 96 \\ \ hline
\ textové & 4 000 & 1 000 &
\koniec

2.) Matematická formulácia problému

Objektívna funkcia	\ (z (x, y) = 4000x + 1 000y \ quad \ rightarrow \ quad \ text \)
Obmedzenia	\ (\ začať 200 x + 100 rokov a \ geq 1600 \\ 6x + 15r & \ geq 96 \koniec\)
. platí tiež:	\ (x \ leq 11 \) \ (y \ leq 8 \)
Podmienka nezápornosti	\ (x \ geq 0 \) \ (y \ geq 0 \)

3.) Grafická úvaha

Prajete si 1. sekundárny stav
\ (200 x + 100 rokov \ geq 1600 \)
nakreslite súradnicový systém, musíte vyriešiť nerovnosť pre \ (y \) \ (100y \ geq -200x + 1600 \)
\ (y \ geq -2x + 16 \)
a potom interpretujte nerovnosť ako priamku
\ (y = -2x + 16 \)

Farebná oblasť označuje oblasť, ktorá spĺňa 1. sekundárnu podmienku.

Prajete si 2. sekundárny stav
\ (6x + 15r \ geq 96 \)
nakreslite súradnicový systém, musíte vyriešiť nerovnosť \ (y \) \ (15r \ geq - 6x + 96 \)
\ (y \ geq - 0,4x + 6,4 \)
a potom interpretujte nerovnosť ako priamku
\ (y = - 0,4x + 6,4 \)

Farebná oblasť označuje oblasť, ktorá spĺňa 2. sekundárnu podmienku.

3. obmedzenie
\ (x \ leq 11 \)
je rovnobežka s osou y s priesečníkom osi \ (x = 11 \).

Farebná oblasť označuje oblasť, ktorá spĺňa 3. sekundárnu podmienku.

4. sekundárna podmienka
\ (y \ leq 8 \)
je rovnobežka s osou x s priesečníkom osi \ (y = 8 \).

Farebná oblasť označuje oblasť, ktorá spĺňa 4. sekundárnu podmienku.

The Sada riešení systému lineárnej nerovnosti.
\ (200 x + 100 rokov \ geq 1600 \)
\ (6x + 15r \ geq 96 \)
\ (x \ leq 11 \)
\ (y \ leq 8 \)
.je v susednej grafike farebne zvýraznená.

Teraz vieme, ako grafická realizovateľná sada riešení vyzerá. Ďalším krokom je hľadanie optimálneho riešenia. Môžeme to určiť buď graficky alebo výpočtom.

4.1) Určite optimálne riešenie (matematické)

Pretože optimum zodpovedá rohovému bodu oblasti riešenia, prečítali sme si ho najskôr: \ (P_1 (6,4) \); \ (P_2 (4,8) \); \ (P_3 (11,8) \); \ (P_4 (11,2) \);

Teraz dáme body do objektívnej funkcie a určíme minimum.

\ (z (6,4) = 4 000 \ krát 6 + 1 000 \ krát 4 = 28 000 € \)

\ (z (4,8) = 4 000 \ krát 4 + 1 000 \ krát 8 = 24 000 € \ qquad \ rightarrow \ quad \ text \)

\ (z (11,8) = 4 000 \ krát 11 + 1 000 \ krát 8 = 52 000 € \)

\ (z (11,2) = 4 000 \ krát 11 + 1 000 \ krát 2 = 46 000 € \)

odpoveď:
Letecká spoločnosť minimalizuje svoje náklady použitím 4 lietadiel typu A a 8 lietadiel typu B pri dodržaní obmedzení.

4.2) Určite optimálne riešenie (graficky)

Nájdete to graficky minimum, vtiahnutím objektívnej funkcie a jej paralelným posúvaním, kým neoznačuje rovná čiara prvý rohový bod oblasti riešenia. Prvý roh potom zodpovedá optimálnemu riešeniu.

Najskôr vyriešime objektívnu funkciu pre \ (y \).
\ (z (x, y) = 4000x + 1000y = 0 \)
\ (1000r = -4000x \)
\ (y = -4x \)
.nakresliť ich do súradnicového systému. Potom posunieme priamku rovnobežne, až kým sa nedostaneme do prvého rohu oblasti riešenia.

Optimum (tu: minimum) je na obrázku zobrazené červeným bodom.

Možné riešenia

V príkladoch vyššie sme už videli, že problém s optimalizáciou môže mať jedinečné riešenie. Je tiež možné, že existuje niekoľko riešení alebo vôbec žiadne.

V nasledujúcej časti nájdete grafický príklad každého riešenia. Cieľom je vždy nájsť minimum.

Jasné optimálne riešenie

. Vyššie sme sa už pozreli na dva príklady.

Nekonečné množstvo optimálnych riešení

Ak je objektívna funkcia paralelná s obmedzením, existuje niekoľko riešení. Graficky to znamená, že pri paralelnom posune sa objektívna funkcia zhoduje s touto obmedzovacou čiarou.

Nie je to optimálne riešenie

Existujú prípady, keď neexistuje optimálne riešenie.

Záver

Pokiaľ ide o tému „lineárnej optimalizácie“, človek sa často musí vyrovnať so slovnými úlohami. Je dôležité, aby ste si prečítali podstatné časti úlohy a zhrnuli ju do tabuľky. Pomocou tohto jasného znázornenia sa následná matematická formulácia enormne zjednoduší.

Ak má lineárny program iba dve premenné, je na riešenie úlohy optimalizácie vhodná grafická analýza.

The maximálne sa dá nájsť graficky tak, že sa vtiahne objektívna funkcia a paralelne sa ňou posúva, až kým nedosiahne hodnotu posledný rohový bod oblasti riešenia.
The minimum sa dá nájsť graficky tak, že sa vtiahne objektívna funkcia a paralelne sa posúva, až kým nedosiahne hodnotu prvý rohový bod oblasti riešenia.

V zásade môžu mať úlohy lineárnej optimalizácie jasné, nekonečné množstvo alebo žiadne (optimálne) riešenie.

Pre lineárne programy s viac ako dvoma premennými nie je (väčšinou) možné grafické zobrazenie. V praxi sa v tomto prípade optimum počíta pomocou takzvaného simplexného algoritmu.

Moje meno je Andreas Schneider a od roku 2013 prevádzkujem bezplatnú a ocenenú platformu pre výučbu matematiky www.mathebibel.de na plný úväzok. Moje výroky si každý mesiac prezerá až 1 milión študentov, rodičov a učiteľov. Publikujem nový obsah takmer každý deň. Prihláste sa na odber môjho bulletinu a získajte 3 z mojich 46 elektronických kníh zadarmo!

PS: Aktuálnu epizódu mojej série #MatheAmMontag som už videl?