Jednoduchá metóda lineárnej optimalizácie je jednoducho vysvetlená

instagram viewer

Lineárna optimalizácia je o optimálnom rozdelení obmedzených zdrojov na rôzne použitia. Nedostatkovými zdrojmi môžu byť napríklad kapacity strojov alebo priestorové požiadavky na tovar. Optimum je určené matematicky, často pomocou simplexovej metódy.

Modelovanie lineárnych programov

Pri modelovaní lineárnych programov sa používajú rôzne parametre ako napr B. Možno určiť časy spracovania obrobkov alebo kapacity strojov. Potom je definovaná objektívna funkcia, ktorá sa má za určitých obmedzení maximalizovať. Cieľová funkcia je často funkcia zisku, pretože maximalizácia čistého zisku je kľúčovým cieľom spoločností. Obmedzenia sú popísané nedostatkom zdrojov (napr. B. Kapacita, čas, priestor). Potom môžete problém vyriešiť pomocou simplexovej metódy.

  • Obzvlášť ľahko sa naučíte postup pri vytváraní lineárnych modelov, ak si urobíte jednoduchý príklad: Predpokladajme, že máte tri stroje M1, M2 a M3 na ktorom sú dva výrobky P1 a P2 by mali byť vyrobené. Stroje majú rôzne kapacity a spracovanie určitého produktu vyžaduje určitý čas na strojoch rôzne dlho a hotové konečné výrobky generujú rôzne zisky preč.
  • Teraz hľadáme výrobný program s maximálnym ziskom, teda taký výrobný program, v ktorom sa dosahuje najväčší zisk.

Príklad s číselnými hodnotami a úvod do simplexovej metódy

V nasledujúcom kroku budete potrebovať konkrétne číselné hodnoty na modelovanie vášho problému. Predpokladajme, že na úpravu P1 na M1 2 hodiny pribúdajú na M2 3 hodiny a na M3 4 hodiny. Pre P.2 spadnúť na M1 4 hodiny ďalej, na M2 5 hodín a na M3 3 hodiny. Kapacity stroja pre M1 500 hodín, pre M2 300 hodín a pre M3 600 hodín. Zisky za hotové konečné výrobky P1 sú 3 eurá / kus, za hotové konečné výrobky P2 4 eura / kus.

  1. Najlepšie je vytvoriť tabuľku s tromi riadkami a tromi stĺpcami s ďalším priestorom pre nadpisy riadkov a stĺpcov. Mali by ste nechať stĺpce. Napríklad čas spracovania P je v poli „Stĺpec 1 a riadok 1“1 na M1, v poli „Stĺpec 2 a Riadok 3“ čas spracovania P2 na M3. Stĺpec 3 uvádza kapacity strojov týchto troch strojov.
    2. Stručne povedané, Gaussov algoritmus lineárnych systémov rovníc

    S lineárnymi sústavami rovníc sa prvýkrát stretnete na strednej škole na ...

  2. Teraz potrebujete dve premenné x1, X2 definovať výrobné množstvá P1 a P2 korešpondovať.
  3. Takže získate obmedzenia 2x1+ 4x2 ≤ 500 (stroj 1), 3x1+ 5x2 ≤ 300 (stroj 2) a 4x1+ 3x2 ≤ 600 (stroj 3). V každom prípade existujú nerovnosti, pretože kapacity nemusia byť úplne vyčerpané.
  4. Maximálna cieľová funkcia (zisk) je G (x1, X2) = 3x1+ 4x2 -> max.
  5. Na výrobné množstvo navyše platia podmienky non-negativity x1, X2 ≥ 0. Vidíte, všetky rovnice sú lineárne rovnice. Ak sa na ne pozriete spoločne, dostanete problém s lineárnou optimalizáciou.

Lineárna optimalizácia a aplikácia simplexovej metódy

Myšlienka riešenia lineárneho programu je, že nerovnosti sú odstránené zavedením „premenných premenných“ do Rovnice a problém upravenej optimalizácie je vyriešený ako LGS. Simplexová metóda je preto veľmi podobná gaussovskému algoritmu na riešenie LGS.

  1. Príklad: Lietadlo je delené tromi tovarmi G1, G.2, G.3 naložiť s najvyššou možnou celkovou hodnotou nákladu. Tieto majú priestorovú požiadavku 1, 0,2 alebo 6 dm3, majú hmotnosť 1, 0, 4 a 8 kg a hodnotou 10, 3 resp 50 eur. Ako je lietadlo ideálne naložené, keď je nákladný priestor 2 000 dm3 a unesie maximálne 3000 kg nákladu?
  2. Definujete x1, X2, X3 ako množstvo tovaru G1, G.2, G.3.
  3. Teraz môžete nastaviť obmedzenia pomocou premenných uvoľnenia nasledovne: x1+ 0,4x2+ 8x3+ x4 = 3000 a x1+ 0,2x2+ 6x3+ x5 = 2000. Cieľová funkcia (celková hodnota nákladu) je G (x1, X2, X3) = 10x1+ 3x2+ 50x3 -> max. Môžete to zmeniť tak, že všetky premenné umiestnite na jednu stránku (G-10x1-3x2-50x3 = 0).
  4. Potom nastavte panel Simplex. Má 3 riadky a 7 stĺpcov. Na ľavej strane zadáte do stĺpcov x1, X2, X3, X4, X5 a G ako nadpisy. Vpravo je b jediný stĺpec. Tu je uvedené optimálne množstvo tovaru a najvyššia možná celková hodnota tovaru. Tretí riadok je cieľový riadok. (Kontrola: v troch riadkoch s vyššie uvedenými nadpismi sú čísla: Riadok 1: 1, 0,4, 8, 1, 0, 0, 3000, Riadok 2: 1, 0,2 6, 0, 1, 0, 2000 a riadok 3: -10, -3, -50, 0, 0, 1, 0).
  5. Teraz postupujte ako pri riešení LGS pomocou Gaussovej metódy. V prvom kroku zmeníte riadok 1 resp. Riadok 2 sa odošle a pridá sa do druhého riadka tak, aby sa v „riadku 1 + stĺpci 1“ zobrazila iba 1 a v „riadku 2 + stĺpci 1“ iba 0. To tiež automaticky zmení hodnoty v cieľovom riadku.
  6. V tomto prípade by ste napríklad mohli vynásobiť riadok 2 o -1, pridať ho do riadka 1 a vynásobiť riadok 2 o 10. a pridajte do riadka 3 (kontrola: riadok 1: 0, 0,2, 2, 1, -1, 0, 1000, riadok 2: zostane rovnaký, riadok 3: 0, -1, 10, 0, 10, 1, 20.000).
  7. V druhom kroku vezmite stĺpec 2 a vytvorte 0 transformáciou „riadku 2 + stĺpca 2“ a potom 1 v „riadku 1 a stĺpci 2“. Opäť je potrebné poznamenať, ako sa cieľová čiara mení.
  8. Kroky transformácie by boli napríklad vynásobením riadka 1 číslom -1 a pridaním do riadka 2 a riadkov 1 až 5 a pridaním do riadku 3. (Kontrola: po vykonaní oboch krokov je výsledok: riadok 1: 0, 1, 10, 5, -5, 0, 5000, riadok 2: 1, 0, 4, -1, 2, 0, 1000 a riadok 3: 0, 0, 20, 5, 5, 1, 25.000).
  9. Teraz si môžete prečítať riešenia na pravej strane panelu. Výsledkom je celková hodnota nákladu 25 000 eur, 5 000 jednotiek tovaru 1, 1 000 kusov tovaru 2 a žiadna jednotka tovaru 3 sa neprepravuje.

Upozorňujeme, že riešenie jednoduchého tabla prináša optimálne riešenie iba vtedy, ak sú v cieľovom riadku vľavo po poslednom kroku pretvárania zobrazené iba pozitívne výsledky. Počítanie stáť. Po ďalších 2-3 príkladoch ste systém zvnútornili a v budúcnosti budete môcť takéto úlohy hravou formou riešiť.

click fraud protection