Lineární programování není jen abstraktní matematika. Je motorem logistiky, dodavatelského řetězce a řízení zdrojů. Je založen na simplexové metodě. Tato standardní metoda nalézá nejlepší možný výsledek v systému daném omezeními a účelovou funkcí.
Představte si to takto. Máte cíl. Například maximalizace zisku nebo minimalizace nákladů. Máte také omezení. Provozní doba zařízení. Suroviny. Práce. Simplexová metoda prochází těmito omezeními, aby nalezla maximální účinnost. Nehádá. On počítá.
Proč potřebujeme systematický přístup
Možná si myslíte, že stačí vykreslit dvě proměnné a zjistit, kde se protínají. Toto funguje pro jednoduché úkoly. Továrna vyrábí dva produkty. Kreslíš čáry. Najdete úhel, kde je zisk maximální. To je jasné. Je to intuitivní.
Ale realita je málokdy dvourozměrná. Problémy reálného světa zahrnují stovky rovnic a tisíce proměnných. Počet možných řešení začíná být astronomický. Je nemožné vykreslit graf pro tisíce proměnných. Potřebovali byste měření, která nemůžete vnímat.
George Dantzig tento problém vyřešil v roce 1947. Pracoval jako matematický konzultant pro americké letectvo. Armáda měla obrovské logistické problémy. Potřebovali optimalizovat zásobovací trasy a alokaci zdrojů. Danzig vyvinul simplexovou metodu k odstranění přebytku.
Metoda omezuje počet extrémních bodů, které je třeba testovat. Proměňuje nemožný úkol ve zvládnutelný. Dodnes zůstává standardním algoritmem na počítačích. Jeden z nejužitečnějších nástrojů, jaký byl kdy vynalezen.
Jak funguje simplexová metoda krok za krokem
Proces je systematický. Přechází od jedné možnosti k druhé. Zde je návod, jak to funguje v praxi.
Za prvé, předpokládá, že máte výchozí bod. Extrémní bod. Pokud žádný nemáte, možnost nazvaná Fáze I najde platný výchozí bod nebo určí, že žádné řešení neexistuje.
Dále metoda kontroluje tento bod. Je to optimální? Tuto kontrolu provádí specifikace algebraického problému. Pokud test selže, algoritmus se přesune do sousedního extrémního bodu. Pohybuje se podél okraje. Vybírá směr, ve kterém cílová funkce roste nejrychlejším tempem.
Někdy se funkce zvyšuje donekonečna. Procedura se zastaví a určí hranu, kde se hodnota blíží kladnému nekonečnu. Našli jste neomezené řešení.
Pokud se tak nestane, dosáhnete nového extrémního bodu. Tato hodnota je minimálně stejně vysoká jako ta předchozí. Sekvence se opakuje. Pokračuje, dokud není nalezen optimální bod nebo odhalena neohraničenost.
Teoreticky může počet kroků exponenciálně růst s počtem extrémních bodů. V praxi dochází ke konvergenci rychle. Obvykle je vyžadován pouze malý násobek krajních bodů.
Případová studie: Maximalizace zisku továrny
Podívejme se na konkrétní případ. Továrna vyrábí dva produkty. Říkejme jim x1 a x2. Zisk z druhého typu je dvakrát vyšší než z prvního. Celkový zisk je reprezentován rovnicí:
x1 + 2×2
Toto je vaše objektivní funkce. Chcete to maximalizovat.
Přirozeně byste chtěli vyrábět pouze x2. Vydělává více peněz na jednotku. Ale existují omezení. Nemůžete vyrábět donekonečna.
Zde jsou skutečná omezení:
- Suroviny pro x2 omezují výrobu na pět jednotek na šarži (x2 ≤ 5).
- Suroviny pro x1 omezují výrobu na osm jednotek na šarži (x1 ≤ 8).
- Provozní doba strojů umožňuje vyrobit celkem maximálně deset jednotek (x1 + x2 ≤ 10).
- Nelze vytvářet záporná množství (x1 ≥ 0 a x2 ≥ 0).
Simplexová metoda najde hodnoty x1 a x2, které maximalizují zisk v těchto mezích. Jakékoli řešení je dvojice čísel (x1, x2). Například vytvoření tří jednotek x1 a šesti jednotek x2 je platným bodem (3, 6).
Při vynesení do grafu tvoří tato omezení polygonální oblast. Toto je soubor proveditelných řešení. Body mimo tuto oblast porušují jedno nebo více omezení.
Chcete-li vidět, jak simplexová metoda určuje optimální vrchol, zvažte účelovou funkci x1 + 2×2 = k. Pokud nastavíte k na 4, dostanete na grafu čáru. Jak se k zvyšuje, dostanete rovnoběžné čáry. Největší hodnota k, která se ještě dotýká oblasti proveditelných řešení, je maximální možný zisk.
V tomto příkladu se přímka pro k = 15 dotýká oblasti v bodě (5, 5). Pokud je k vyšší, je čára mimo povolenou množinu. Optimálním řešením je vyrábět stejné množství každého zboží.
Proč jsou vrcholy důležité v lineárním programování
Výsledek není náhoda. V lineárních úlohách se optimálního řešení dosáhne vždy ve vrcholu. V extrémním bodě.
To je základní vlastnost lineárního programování. Funkce je lineární. Omezení jsou lineární. Tvar je konvexní mnohoúhelník (nebo mnohostěn ve vyšších rozměrech). Vrchol lineární funkce nad konvexní množinou je vždy v rohu.
Nemusíte kontrolovat každý bod v prostoru proveditelného řešení. Musíte pouze zkontrolovat vrcholy. Simplexová metoda to dělá. Skáče z vrcholu na vrchol. Leze po povrchu regionu proveditelných řešení. Zastaví se, když se nemůže zvednout výš.
Někdy není optimum jediné. Všechny hrany mohou produkovat stejnou maximální hodnotu. Ale simplexová metoda stále najde jeden z těchto optimálních bodů. Dá vám konkrétní odpověď. Akční data.
Pro studenty a odborníky je pochopení tohoto mechanismu klíčové. Nejde jen o řešení rovnic. Jde o to vědět, jak se orientovat ve složitých systémech s omezenými zdroji. Simplexová metoda poskytuje cestu.
Simplexová metoda odpovědi jen nehádá. Pohybuje se po okrajích oblasti možných řešení a kontroluje vrcholy, dokud nenajde to nejlepší. Nejprve zjednoduší matematickou formulaci problému. Vezmete tyto těžkopádné lineární nerovnosti a přeměníte je na úhledné rovnosti. Za tímto účelem jsou zavedeny „proměnné odchylky“ (angl. „slack variables“).
Myslete na volnost jako na zbývající sílu. Pokud máte omezení ve tvaru $x_1 \le 8$, přidáte proměnnou $x_3$ tak, aby $x_1 + x_3 = 8$. A pamatujte, že $x_3$ musí být větší nebo rovno nule. Děláte to pro každé omezení.
- $ x_1 + x_3 = 8 $ (při $ x_3 \ge 0 $)
- $ x_2 + x_4 = 5 $ (při $ x_4 \ge 0 $)
- $ x_1 + x_2 + x_5 = 10 $ (při $ x_5 \ge 0 $)
Také potřebujete proměnnou pro samotnou cílovou funkci. Říkejme tomu $x_0$. Pokud je vaším cílem maximalizovat $x_0 = x_1 + 2x_2$, přepište to jako $x_1 + 2x_2 – x_0 = 0 $.
Nyní je úkol jednodušší. Najděte nezáporné hodnoty pro $x_1$ až $x_5$. Udělejte $x_0$ co největší.
Původ v místě původu
kde začít? Nejjednodušší bod je původ. Nastavte všechny rozhodovací proměnné na nulu. $ x_1 = 0 $. $ x_2 = 0 $.
Toto je platné řešení. Toto je extrémní bod. Ve skutečnosti je to počáteční vrchol. Hodnota účelové funkce $x_0$ je také nulová. Není to moc dobré, ale je to právní jednání.
Můžeme to udělat lépe? Ano. Pokud jednu z proměnných zvýšíte z nuly a druhou necháte rovnou nule, $x_0$ se zvýší. Otázkou je, která proměnná vám dá nejvíc peněz.
Podívejte se na rovnici účelové funkce: $x_1 + 2x_2 – x_0 = 0$. Vyjádříme-li $x_0$, dostaneme $x_0 = x_1 + 2x_2$.
Zvýšení $x_1$ přidá 1 k celkové hodnotě. Zvýšení $x_2$ přidá 2. $x_2$ je jasný vítěz. Produkuje největší nárůst x_0 $ za změnu jednotky. Vyberete tedy $x_2$ a zvýšíte jej.
Setkání s prvním omezením
Nemůžete zvyšovat $x_2$ donekonečna. Proměnné musí zůstat nezáporné. Pokud zvýšíte $x_2$ nad 5, něco se pokazí. Zejména se podívejte na druhé omezení: $ x_2 + x_4 = $ 5.
Pokud $x_2 = 6$, pak $x_4$ bude -1. To je zakázáno. Požadavek na nezápornost funguje jako pevné omezení. Limit je 5.
Takže nastavíte $ x_2 = 5 $. Jak vypadá řešení nyní?
- $ x_2 = 5 $
- $ x_1 = 0 $ (stále nula)
- $x_4 = 0$ (tato proměnná dosáhla svého limitu, takže je nyní nula)
- $ x_3 = 8 $ (protože $ 0 + 8 = 8 $)
*$
