LINEÁRNÍ PROGRAMOVÁNÍ: K ČEMU SLOUŽÍ, MODELY, OMEZENÍ, APLIKACE - MATEMATIKA - 2025

Lineární programování je matematická metoda, která se používá k optimalizaci (maximalizovat nebo minimalizovat podle potřeby), funkce, jejichž proměnné jsou omezeny, jak dlouho, jak je funkce a omezení jsou lineárně závislé proměnné.

Obecně platí, že funkce, která má být optimalizována, modeluje praktickou situaci, jako je zisk výrobce, jehož vstupy, práce nebo strojní zařízení jsou omezené.

Obrázek 1. Lineární programování se široce používá k optimalizaci zisků. Zdroj: Piqsels.

Jedním z nejjednodušších případů je lineární funkce, která má být maximalizována, což závisí pouze na dvou proměnných, které se nazývají rozhodovací proměnné. Může mít podobu:

Z = k ₁ x + k ₂ y

S konstantou k ₁ k ₂. Tato funkce se nazývá objektivní funkce. Samozřejmě existují situace, které si zaslouží více než dvě proměnné pro studium, které jsou složitější:

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

A omezení jsou také matematicky modelována soustavou rovnic nebo nerovností, stejně lineární v xay.

Soubor řešení v tomto systému se nazývá proveditelná řešení nebo proveditelné body. A mezi proveditelnými body existuje alespoň jeden, který optimalizuje objektivní funkci.

Lineární programování byl nezávisle vyvinut americkým fyzikem a matematikem Georgem Dantzigem (1914-2005) a ruským matematikem a ekonomem Leonidem Kantorovičem (1912-1986) krátce po druhé světové válce.

Metodou řešení problémů známou jako simplexní metoda je duchovní vývoj Dantziga, který pracoval pro americké letectvo, Berkeley University a Stanford University.

Obrázek 2. Matematici George Dantzig (vlevo) a Leonid Kantorovich (vpravo). Zdroj: F. Zapata.

Lineární programovací modely

Prvky nezbytné pro vytvoření modelu lineárního programování vhodného pro praktickou situaci jsou:

-Objektivní funkce

- Proměnné rozhodnutí

- Omezení

V objektivní funkci definujete, čeho chcete dosáhnout. Předpokládejme například, že chcete maximalizovat zisky z výroby určitých produktů. Poté je stanovena funkce „zisku“ podle ceny, za kterou se výrobky prodávají.

Z matematického hlediska lze tuto funkci vyjádřit zkráceně pomocí notace sumace:

Z = ∑k _i x _i

V této rovnici, K _i jsou koeficienty a x _i jsou rozhodovací proměnné.

Rozhodovací proměnné jsou prvky systému, jehož kontrola je a jejich hodnoty jsou kladná reálná čísla. V navrhovaném příkladu jsou rozhodovacími veličinami množství každého výrobku, který má být vyroben, aby se získal maximální zisk.

Nakonec máme omezení, která jsou lineárními rovnicemi nebo nerovnostmi z hlediska rozhodovacích proměnných. Popisují omezení problému, která jsou známá a mohou to být například množství suroviny dostupné při výrobě.

Druhy omezení

Můžete mít omezení M, počínaje j = 1 až j = M. Matematicky jsou omezení tří typů:

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

První omezení je typu lineární rovnice a znamená, že musí být respektována hodnota _Aj, která je známa.

Zbývající dvě omezení jsou lineární nerovnosti a to znamená, že známé hodnoty B _j a C _j mohou být respektovány nebo překročeny, když se objeví zobrazený symbol ≥ (větší nebo rovno) nebo respektován nebo nepřekročen, pokud je symbol ≤ (menší nebo rovno).

Vzorový příklad

Oblasti použití jsou velmi rozmanité, od správy podniků po výživu, ale pro pochopení této metody je níže navržen jednoduchý model praktické situace se dvěma proměnnými.

Místní cukrárna je známá pro dvě speciality: černý lesní koláč a sacripantinový dort.

Při přípravě vyžadují vejce a cukr. Pro černý les potřebujete 9 vajec a 500 g cukru, zatímco pro sacripantin potřebujete 8 vajec a 800 g cukru. Příslušné prodejní ceny jsou 8 USD a 10 USD.

Problém je: Kolik koláče každého typu musí pekařství vyrobit, aby maximalizoval svůj zisk, protože ví, že má 10 kilogramů cukru a 144 vajec?

Rozhodovací proměnné

Rozhodovací proměnné jsou „x“ a „y“, které berou skutečné hodnoty:

-x: počet koláčů z černého lesa

-y: koláče typu sacripantine.

Omezení

Omezení jsou dána skutečností, že počet dortů je kladné množství a pro jejich přípravu existuje omezené množství surovin.

Proto v matematické podobě mají tato omezení podobu:

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

Omezení 1 a 2 představují podmínku dříve nezasažené negativity a všechny vzniklé nerovnosti jsou lineární. V omezeních 3 a 4 jsou hodnoty, které nesmí být překročeny: 144 vajec a 10 kg cukru.

Objektivní funkce

A konečně, objektivní funkcí je zisk získaný při výrobě „x“ množství koláče z černého lesa plus „y“ množství sacripantinů. Je postaven vynásobením ceny množstvím vyrobených dortů a přičtením pro každý typ. Je to lineární funkce, kterou nazýváme G (x, y):

G = 8x + 10 let

Metody řešení

Různé metodiky řešení zahrnují grafické metody, simplexní algoritmus a metodu vnitřního bodu, abychom jmenovali alespoň některé.

- Grafická nebo geometrická metoda

Pokud máte problém se dvěma proměnnými, jako je ten v předchozí části, určují omezení polygonální oblast v rovině xy, která se nazývá proveditelná oblast nebo oblast životaschopnosti.

Obrázek 3. Realizovatelná oblast, kde se nachází řešení problému optimalizace. Zdroj: Wikimedia Commons.

Tato oblast je konstruována pomocí restrikčních linií, což jsou linie získané z nerovností omezení, fungující pouze se znaménkem rovnosti.

V případě pekárny, která chce optimalizovat zisky, jsou liniemi omezení:

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

Všechny body v oblasti ohraničené těmito čarami jsou možná řešení, takže jich je nekonečně mnoho. S výjimkou případu, kdy se proveditelná oblast ukáže být prázdná, v tom případě problém, který představuje, nemá řešení.

Naštěstí pro problém s pečivem není proveditelná oblast prázdná, máme ji níže.

Obrázek 4. Realizovatelná oblast problému pečiva. Řádek se ziskem 0 překračuje původ. Zdroj: F. Zapata s Geogebra.

Optimální řešení, pokud existuje, je nalezeno pomocí objektivní funkce. Například při pokusu o nalezení maximálního zisku G máme následující řádek, který se nazývá iso-profit line:

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

S touto čarou získáme všechny páry (x, y), které poskytují daný zisk G, takže existuje řada čar podle hodnoty G, ale všechny se stejným sklonem -k ₁ / k ₂, takže jsou rovnoběžky.

Optimální řešení

Nyní lze ukázat, že optimální řešení lineárního problému je vždy krajním bodem nebo vrcholem proveditelné oblasti. Tak:

Pokud má čára nejblíže k původu celý společný segment s proveditelnou oblastí, pak se říká, že existují nekonečná řešení. Tento případ nastane, pokud sklon linie iso-profit je stejný jako u kterékoli jiné linie, která omezuje region.

U našeho pečiva jsou vrcholy kandidátů A, B a C.

- Dantzigova simplexní metoda

Grafická nebo geometrická metoda je použitelná pro dvě proměnné. Je však složitější, když existují tři proměnné a nelze je použít pro větší počet proměnných.

Při řešení problémů s více než dvěma proměnnými se používá simplexní metoda, která se skládá z řady algoritmů pro optimalizaci objektivních funkcí. K výpočtu se často používají matice a jednoduchá aritmetika.

Simplexní metoda začíná výběrem proveditelného řešení a kontrolou, zda je optimální. Pokud ano, problém jsme již vyřešili, ale pokud tomu tak není, pokračujeme směrem k řešení blíže k optimalizaci. Pokud řešení existuje, algoritmus jej najde v několika pokusech.

Aplikace

Lineární a nelineární programování se používá v mnoha oblastech, aby bylo co nejlepší rozhodnutí z hlediska snižování nákladů a zvyšování zisků, které nejsou vždy peněžní, protože je lze měřit v čase, například pokud chcete minimalizovat potřebný čas provádět řadu operací.

Zde jsou některá pole:

- V marketingu se používá k nalezení nejlepší kombinace médií (sociální sítě, televize, tisk a další) k propagaci určitého produktu.

- Pro přiřazení adekvátních úkolů zaměstnancům společnosti nebo továrny nebo jejich naplánování.

-Výběr nejživnějších potravin a za nejnižší náklady v živočišném a drůbežářském průmyslu.

Řešená cvičení

- Cvičení 1

Graficky řešte model lineárního programování uvedený v předchozích oddílech.

Řešení

Je nutné graficky znázornit množinu hodnot určenou systémem omezení specifikovaným v problému:

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

Region daný nerovnostmi 1 a 2 odpovídá prvnímu kvadrantu karteziánské roviny. Pokud jde o nerovnosti 3 a 4, začneme hledáním omezujících linií:

9x + 8r = 144

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

Realizovatelnou oblastí je čtyřúhelník, jehož vrcholy jsou body A, B, C a D.

Minimální zisk je 0, proto řádek 8x + 10y = 0 je dolní mez a linie iso-profit mají sklon -8/10 = - 0,8.

Tato hodnota se liší od sklonů ostatních restrikčních linií a protože proveditelná oblast je ohraničena, existuje jedinečné řešení.

Obrázek 5. Grafické řešení cvičení 1, ukazující proveditelnou oblast a bod řešení C v jednom z vrcholů této oblasti. Zdroj: F. Zapata.

Toto řešení odpovídá přímce sklonu -0,8, která prochází kterýmkoli z bodů A, B nebo C, jejichž souřadnice jsou:

A (11; 5,625)

B (0; 12,5)

C (16, 0)

Optimální řešení

Vypočítáme hodnotu G pro každý z těchto bodů:

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

Nejvyšší zisk je ve výrobě 11 černých lesních koláčů a 5 625 sacripantinových dortů. Toto řešení souhlasí s řešením nalezeným prostřednictvím softwaru.

- Cvičení 2

Ověřte výsledek předchozího cvičení pomocí funkce Řešitele, která je k dispozici ve většině tabulek, jako jsou Excel nebo LibreOffice Calc, které obsahují algoritmus Simplex pro optimalizaci v lineárním programování.

Řešení

Obrázek 6. Detail řešení od cvičení 1 prostřednictvím tabulky Libre Office Calc. Zdroj: F. Zapata.

Obrázek 7. Detail řešení od cvičení 1 prostřednictvím tabulky Libre Office Calc. Zdroj: F. Zapata.

Reference

1. Brilantní. Lineární programování. Obnoveno z: brilliant.org.
2. Eppen, G. 2000. Operativní výzkum ve správní vědě. 5. Edice. Prentice Hall.
3. Haeussler, E. 1992. Matematika pro řízení a ekonomiku. 2. Edice. Grupo Editorial Iberoamericana.
4. Hiru.eus. Lineární programování. Získáno z: hiru.eus.
5. Wikipedia. Lineární programování. Obnoveno od: es. wikipedia.org.