LINEÁRNE PROGRAMOVANIE: NA ČO SLÚŽI, MODELY, OBMEDZENIA, APLIKÁCIE - MATEMATIKA - 2026

Lineárne programovanie je matematická metóda, ktorá sa používa na optimalizáciu (maximalizovať alebo minimalizovať podľa potreby), funkcie, ktorých premenné sú obmedzené, ako dlho, ako je funkcie a obmedzenia sú lineárne závislé premenné.

Vo všeobecnosti funkcia, ktorá má byť optimalizovaná, predstavuje praktickú situáciu, napríklad zisk výrobcu, ktorého vstupy, práca alebo strojové vybavenie sú obmedzené.

Obrázok 1. Lineárne programovanie sa bežne používa na optimalizáciu ziskov. Zdroj: Piqsels.

Jedným z najjednoduchších prípadov je lineárna funkcia, ktorá sa má maximalizovať, ktorá závisí iba od dvoch premenných, ktoré sa nazývajú rozhodovacie premenné. Môže mať podobu:

Z = k ₁ x + k ₂ r

S konštantou k ₁ k ₂ . Táto funkcia sa nazýva objektívna funkcia. Samozrejme, existujú situácie, ktoré si zaslúžia viac ako dve premenné, ktoré sú zložitejšie:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

A obmedzenia sú tiež matematicky modelované systémom rovníc alebo nerovností, rovnako lineárne v xay.

Súbor riešení v tomto systéme sa nazýva uskutočniteľné riešenia alebo uskutočniteľné body. A medzi uskutočniteľnými bodmi je aspoň jeden, ktorý optimalizuje objektívnu funkciu.

Lineárne programovanie bol nezávisle vyvinutý americkým fyzikom a matematikom Georgeom Dantzigom (1914-2005) a ruským matematikom a ekonómom Leonidom Kantorovičom (1912-1986) krátko po druhej svetovej vojne.

Metóda riešenia problémov známa ako simplexná metóda je duchovným dielom Dantziga, ktorý pracoval pre americké letectvo, Berkeley University a Stanford University.

Obrázok 2. Matematici George Dantzig (vľavo) a Leonid Kantorovich (vpravo). Zdroj: F. Zapata.

Lineárne programovacie modely

Prvky potrebné na vytvorenie modelu lineárneho programovania vhodného pre praktickú situáciu sú:

-Objektívna funkcia

-Rozhodovacie premenné

-Restrictions

V objektívnej funkcii definujete, čo chcete dosiahnuť. Predpokladajme napríklad, že chcete maximalizovať zisky z výroby určitých výrobkov. Potom sa stanoví funkcia „zisk“ podľa ceny, za ktorú sa výrobky predávajú.

Z matematického hľadiska možno túto funkciu vyjadriť skrátene pomocou sumačného zápisu:

Z = ∑k _i x _i

V tejto rovnici, K _i sú koeficienty a x _i sú rozhodovacie premenné.

Premenné rozhodovania sú prvky systému, ktorého kontrola bola vykonávaná, a ich hodnoty sú kladné reálne čísla. V navrhovanom príklade sú premenné rozhodnutia množstvo každého výrobku, ktorý sa má vyrobiť, aby sa dosiahol maximálny zisk.

Nakoniec máme obmedzenia, ktoré sú lineárnymi rovnicami alebo nerovnosťami, pokiaľ ide o premenné rozhodovania. Opisujú obmedzenia problému, ktoré sú známe a môžu to byť napríklad množstvá suroviny dostupné pri výrobe.

Druhy obmedzení

Môžete mať niekoľko obmedzení, počnúc j = 1 až j = M. Matematicky obmedzenia sú troch typov:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

Prvé obmedzenie je lineárneho typu rovnice a znamená, že hodnota A _j má, o ktorej je známe, je potrebné rešpektovať.

Dve zostávajúce obmedzenia sú lineárne nerovnosti a to znamená, že známe hodnoty B _j a C _j môžu byť rešpektované alebo prekročená, keď je symbol, ktorý sa objaví, je ≥ (väčší alebo rovné) alebo rešpektovaná alebo nie je prekročený, v prípade, že symbol je ≤ (menšia alebo rovná).

Príklad modelu

Oblasti použitia sú veľmi rôznorodé, od podnikovej správy až po výživu, ale na pochopenie metódy je nižšie uvedený jednoduchý model praktickej situácie s dvoma premennými.

Miestna cukráreň je známa dvoma špecialitami: koláč z čierneho lesa a koláč svätého mena.

Pri príprave vyžadujú vajcia a cukor. Pre čierny les potrebujete 9 vajec a 500 g cukru, zatiaľ čo pre sacripantín potrebujete 8 vajec a 800 g cukru. Príslušné predajné ceny sú 8 USD a 10 USD.

Problém je: Koľko koláčov každého typu musí pekáreň urobiť, aby maximalizovala svoj zisk, pretože vie, že má 10 kilogramov cukru a 144 vajec?

Premenné rozhodnutia

Premenné rozhodovania sú „x“ a „y“, ktoré majú reálne hodnoty:

-x: počet čiernych lesných koláčov

-y: koláče typu sacripantine.

obmedzenia

Obmedzenia sú dané skutočnosťou, že počet koláčov je kladné množstvo a na ich prípravu je obmedzené množstvo surovín.

Z tohto dôvodu majú tieto obmedzenia v matematickej podobe podobu:

1. x ≥ 0
2. a ≥0
3. 9x + 8r <144
4. 0,5 x + 0,8 r <10

Obmedzenia 1 a 2 vytvárajú podmienku predtým nezasaženej negativity a všetky vzniknuté nerovnosti sú lineárne. V obmedzeniach 3 a 4 sú hodnoty, ktoré sa nesmú prekročiť: 144 vajec a 10 kg cukru.

Objektívna funkcia

A konečne, cieľovou funkciou je zisk získaný pri výrobe „x“ množstva čiernych lesných koláčov plus „y“ množstva sacripantínov. Je zostavená tak, že sa cena vynásobí počtom vyrobených koláčov a sčítaním pre každý typ. Je to lineárna funkcia, ktorú nazývame G (x, y):

G = 8x + 10r

Metódy riešenia

Rôzne metodológie riešenia zahŕňajú napríklad grafické metódy, simplexný algoritmus a metódu vnútorného bodu.

- Grafická alebo geometrická metóda

Ak máte problém s dvoma premennými, ako je ten v predchádzajúcej časti, obmedzenia určia polygonálnu oblasť v rovine xy, nazývanú realizovateľná oblasť alebo oblasť životaschopnosti.

Obrázok 3. Realizovateľná oblasť, v ktorej sa nachádza riešenie problému s optimalizáciou. Zdroj: Wikimedia Commons.

Táto oblasť je skonštruovaná pomocou reštrikčných čiar, ktoré sú čiarami získanými z nerovností obmedzení a pracujú iba so znakom rovnosti.

V prípade pekárne, ktorá chce optimalizovať zisky, sú riadkami obmedzenia:

1. x = 0
2. y = 0
3. 9x + 8r = 144
4. 0,5 x + 0,8 r = 10

Všetky body v regióne ohraničené týmito čiarami sú možnými riešeniami, takže ich je nekonečne veľa. S výnimkou prípadu, keď je realizovateľná oblasť prázdna, a v takom prípade problém nie je vyriešený.

Našťastie, pre problém s pečivom nie je realizovateľná oblasť prázdna, máme ju nižšie.

Obrázok 4. Realizovateľná oblasť problému s pečivom. Čiara so ziskom 0 prekračuje pôvod. Zdroj: F. Zapata s Geogebra.

Optimálne riešenie, ak existuje, je nájdené pomocou objektívnej funkcie. Napríklad, keď sa snažíme nájsť maximálny zisk G, máme nasledujúci riadok, ktorý sa nazýva iso-ziskový riadok:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

S touto čiarou získame všetky páry (x, y), ktoré poskytujú daný zisk G, takže existuje skupina čiar podľa hodnoty G, ale všetky majú rovnaký sklon -k ₁ / k ₂ , takže sú rovnobežné čiary.

Optimálne riešenie

Teraz je možné ukázať, že optimálne riešenie lineárneho problému je vždy krajným bodom alebo vrcholom uskutočniteľnej oblasti. takže:

Ak čiara najbližšia k pôvodu má celý segment spoločný s uskutočniteľnou oblasťou, hovorí sa, že existujú nekonečné riešenia. Tento prípad nastane, ak je sklon izo-ziskového riadku rovnaký so sklonom ktoréhokoľvek z ostatných riadkov, ktoré obmedzujú región.

V prípade nášho pečiva sú vrcholy kandidátov A, B a C.

- Dantzigova simplexná metóda

Grafická alebo geometrická metóda je použiteľná pre dve premenné. Je však zložitejšie, keď existujú tri premenné a nie je možné ich použiť pre väčší počet premenných.

Pri riešení problémov s viac ako dvoma premennými sa používa simplexná metóda, ktorá pozostáva z radu algoritmov na optimalizáciu objektívnych funkcií. Na výpočet sa často používajú matice a jednoduché aritmetické postupy.

Simplexná metóda začína výberom uskutočniteľného riešenia a kontrolou, či je optimálna. Ak je, už sme problém vyriešili, ale ak nie, pokračujeme v riešení bližšie k optimalizácii. Ak riešenie existuje, algoritmus ho nájde v niekoľkých pokusoch.

aplikácia

Lineárne a nelineárne programovanie sa používa v mnohých oblastiach na to, aby sa čo najlepšie rozhodovalo o znižovaní nákladov a zvyšovaní ziskov, ktoré nie sú vždy peňažné, pretože sa môžu merať v čase, napríklad ak sa snažíte minimalizovať potrebný čas. vykonávať sériu operácií.

Tu sú niektoré polia:

- V marketingu sa používa na nájdenie najlepšej kombinácie médií (sociálne siete, televízia, tlač a iné) na reklamu určitého produktu.

- Na pridelenie primeraných úloh personálu spoločnosti alebo závodu alebo ich rozvrhnutiu.

- pri výbere naj výživnejších potravín a pri najnižších nákladoch v živočíšnom a hydinárskom priemysle.

Riešené cvičenia

- Cvičenie 1

Graficky vyriešiť model lineárneho programovania uvedený v predchádzajúcich častiach.

Riešenie

Je potrebné zmapovať množinu hodnôt určenú systémom obmedzení špecifikovaným v probléme:

1. x ≥ 0
2. a ≥0
3. 9x + 8r <144
4. 0,5 x + 0,8 r <10

Región daný nerovnosťami 1 a 2 zodpovedá prvému kvadrantu karteziánskej roviny. Pokiaľ ide o nerovnosti 3 a 4, začneme hľadaním hraničných čiar:

9x + 8r = 144

0,5 x + 0,8 r = 10 → 5 x + 8 r = 100

Realizovateľnou oblasťou je štvoruholník, ktorého vrcholy sú body A, B, C a D.

Minimálny zisk je 0, preto riadok 8x + 10r = 0 je dolná hranica a riadky iso-zisku majú sklon -8/10 = - 0,8.

Táto hodnota sa líši od sklonov ostatných reštrikčných čiar a keďže uskutočniteľná oblasť je ohraničená, existuje jedinečné riešenie.

Obrázok 5. Grafické riešenie cvičenia 1, znázorňujúce uskutočniteľnú oblasť a bod C riešenia v jednom z vrcholov uvedenej oblasti. Zdroj: F. Zapata.

Toto riešenie zodpovedá priamke sklonu -0,8, ktorá prechádza ktorýmkoľvek z bodov A, B alebo C, ktorých súradnice sú:

A (11; 5,625)

B (0; 12,5)

C (16, 0)

Optimálne riešenie

Vypočítame hodnotu G pre každý z týchto bodov:

- (11; 5,625): G = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Najvyšší zisk je vo výrobe 11 čiernych lesných koláčov a 5 625 sviatočných koláčov. Toto riešenie súhlasí s riešením nájdeným prostredníctvom softvéru.

- Cvičenie 2

Overte výsledok predchádzajúceho cvičenia pomocou funkcie Riešiteľ, ktorá je k dispozícii vo väčšine tabuliek, napríklad Excel alebo LibreOffice Calc, ktoré obsahujú algoritmus Simplex pre optimalizáciu v lineárnom programovaní.

Riešenie

Obrázok 6. Detail riešenia od cvičenia 1 cez tabuľku Libre Office Calc. Zdroj: F. Zapata.

Obrázok 7. Detail riešenia od cvičenia 1 cez tabuľku Libre Office Calc. Zdroj: F. Zapata.

Referencie

1. Brilantná. Lineárne programovanie. Obnovené z: brilliant.org.
2. Eppen, G. 2000. Operačný výskum v oblasti administratívy. 5 .. Vydanie. Prentice Hall.
3. Haeussler, E. 1992. Matematika pre riadenie a ekonomiku. 2 .. Vydanie. Grupo Editorial Iberoamericana.
4. Hiru.eus. Lineárne programovanie. Získané z: hiru.eus.
5. Wikipedia. Lineárne programovanie. Získané z: es. wikipedia.org.