Víte, co to znamená optimalizovat systém, abyste dosáhli co nejlepších výsledků, pokud jste student inženýrství nebo inženýr.
Optimalizace řešení je klíčem k úspěchu ve všem, od budování mostů po tvorbu softwaru.
V tomto bodě přichází na řadu myšlenka základního proveditelného řešení.
Je to základní myšlenka v lineárním programování, která vám umožní zjistit, které ze sady možných řešení je nejlepší.
Ale proč na tom tolik záleží? V tomto článku budu hovořit o základních proveditelných řešeních a o tom, jak je lze použít k řešení technických problémů v reálném světě.
Budu mluvit o tom, jak je najít, z čeho jsou vyrobeny a proč jsou důležité.
Takže, ať už jste zkušený inženýr nebo student, který právě začínáte, pojďte s námi, když se ponořím do světa základních proveditelných řešení a ukážu vám, jak využít sílu lineárního programování.
Pochopení základního proveditelného řešení
Formální definice:
Základní řešení lineárního programového modelu, ve kterém jsou všechny proměnné nezáporné.
Základní proveditelné řešení (BFS) je klíčová myšlenka v lineárním programování, která pomáhá najít nejlepší řešení.
BFS je řešení s nejmenším možným počtem nenulových proměnných.
Je to kout mnohostěnu proveditelných řešení.
Jinými slovy, BFS je základní řešení, které splňuje nezáporná omezení a nachází se v proveditelné oblasti nebo problémové oblasti.
Nalezení optimálního základního proveditelného řešení
Abychom našli nejlepší BFS, musíme udělat následující:
- Napište program ve standardním tvaru pro lineární sekvenci.
- Proměňte systém nerovností v rozšířenou matici.
- Zjistěte, které proměnné jsou základní a které ne.
- Zjistěte, jaké jsou základní proměnné z hlediska ostatních proměnných.
- Vložte tyto výrazy do objektivní funkce, abyste získali funkci pouze proměnných, které nejsou základní.
- Najděte nezákladní proměnnou, kterou lze zvýšit bez porušení jakýchkoli omezení, a díky které bude cíl fungovat lépe.
Tato proměnná je nyní základní proměnnou a jedna z dalších základních proměnných již základní proměnnou není.
Pokud existuje optimální řešení, musí být na jednom z konců nebo vrcholů oblasti, kde jsou možná řešení.
Takže pokud má LP optimální řešení, má optimální řešení v extrémním bodě možného souboru.
Také vždy existuje optimální BFS, pokud existuje optimální řešení.
Použití simplexní metody k nalezení optimálního BFS
Simplexová metoda je algoritmus pro řešení problémů v lineárním programování.
Přesune se z jednoho BFS na „sousední“ BFS pomocí procedury pivot.
V proceduře pivot je vybrána nezákladní proměnná, která se stane základní proměnnou, a pak se k řešení nových základních proměnných použije aktuální BFS.
Když nelze změnit žádnou nezákladní proměnnou, aby byla účelová funkce lepší, je algoritmus hotov.
Proč jsou základní proveditelná řešení zásadní pro řešení složitých technických problémů
Stále těžké pochopit? Dovolím si trochu změnit úhel pohledu:
Kdo vlastně potřebuje jednoduché a použitelné odpovědi? Stačí dát všechno dohromady a doufat v to nejlepší.
Koneckonců, kdo potřebuje optimalizaci, když je chaos mnohem zábavnější? Vítejte ve světě nezáporných proměnných, kde je vše jen sugesce a neúspěch je téměř jistý.
Nebo je to?
Pojďme prozkoumat, proč zdánlivě základní koncept základních proveditelných řešení není nic jiného než základní a proč mohou být právě klíčem k řešení i těch nejsložitějších inženýrských problémů.
Dobře, to byl jen vtip, který vypadal jako televizní reklama.
Nyní se vraťme k vysvětlení.
Nalezení základního proveditelného řešení
Základní proveditelné řešení (BFS) je řešením lineárního optimalizačního problému, který splňuje všechna omezení a má nejmenší počet nenulových proměnných.
Každý BFS je rohem mnohostěnu proveditelných řešení z geometrického hlediska.
Pokud existuje nejlepší řešení, musí existovat také nejlepší první krok.
V tomto článku si povíme, jak najít počáteční základní proveditelné řešení, jak najít všechna základní proveditelná řešení a jak najít základní proveditelné řešení bez proměnných nevyužitých věcí.
Nalezení počátečního základního proveditelného řešení
Můžeme použít různé metody v závislosti na tom, jak je problém nastaven, abychom našli počáteční základní řešení, které funguje pro lineární optimalizační problém.
Jedním ze způsobů je přidat k omezením pro nerovnosti proměnné slack a nastavit všechny ostatní proměnné na nulu.
Slack proměnné se stanou základními proměnnými a zbytek jsou nezákladní proměnné.
Dvoufázová simplexní metoda je dalším způsobem řešení problému.
Tato metoda zahrnuje řešení problému lineárního programování navíc, aby se našlo počáteční základní řešení, které je proveditelné.
Jakmile bylo nalezeno počáteční základní proveditelné řešení, lze Simplexovou metodu použít k přechodu od jednoho základního proveditelného řešení k dalšímu a poté k nejlepšímu řešení.
Nalezení všech základních proveditelných řešení
Pro lineární program může existovat více než jedno základní řešení.
Můžeme změnit systém přidáním proměnných prodlevy a pak použít nový systém k nalezení všech základních proveditelných řešení pro lineární program.
Poté se tato základní proveditelná řešení použijí k nalezení základních proveditelných řešení původního problému.
Nalezení základního proveditelného řešení bez proměnných
Potřebujeme použít volné proměnné, abychom se zbavili omezení menší než, abychom mohli najít základní řešení, které funguje bez proměnných nevyužitých.
Proměnná uvolněnosti je pouze rozdíl mezi pravou stranou omezení a levou stranou.
Například pro první omezení definujeme proměnnou uvolněnosti x4 = 14 - 2x1 - x2 - x3. Z hlediska této nové proměnné je první omezení ekvivalentní jednoduše x4 ≥ 0, což je kladné omezení pro x4.
Když sečteme tyto volné proměnné, dostaneme lineární program, který je stejný jako ten původní, kromě toho, že všechna omezení jsou buď rovnice, nebo omezení, která říkají, že je něco kladné.
Množina základních proměnných, které mají v základním řešení jiné hodnoty než nula, se nazývá báze.
Proměnné, které mají v základním řešení nulovou hodnotu, nejsou základními proměnnými.
Abychom našli nejlepší řešení, musíme najít vektor x, který splňuje všechna pravidla a získá pro cíl největší nebo nejmenší hodnotu.
Nalezení nejlepšího řešení však vyžaduje více kroků než jen nalezení řešení, které funguje a nemá žádné proměnné.
Není vždy možné najít základní řešení bez proměnných nevyužitých proměnných, zejména u problémů s omezeními menšími než.
Chcete-li najít základní proveditelné řešení, musíte použít simplexovou metodu nebo jiný algoritmus lineárního programování a hledat řešení, které splňuje všechna omezení a má nejméně nenulových proměnných.
Vlastnosti a význam základního proveditelného řešení
Vlastnosti základního proveditelného řešení
Základní proveditelné řešení má nejvýše m proměnných, které nejsou nulové, a nejméně nm proměnných, které jsou nulové, kde n je počet rozhodovacích proměnných a m je počet omezení.
BFS je rohem mnohostěnu možných řešení a každý BFS má n aktivních omezení, která jsou lineárně nezávislá.
Pokud existuje nejlepší řešení, musí existovat také nejlepší první krok.
Nejdůležitější na základních proveditelných řešeních je, že jsou to konce množiny konvexních řešení problému lineárního programování.
Aby našel nejlepší odpověď, simplexní algoritmus prochází řadou BFS.
Simplex Algorithm prohledá všechna základní možná řešení organizovaným způsobem, aby našel to nejlepší.
Význam základního proveditelného řešení
Nalezení základního řešení, které je možné, je důležité, protože pomáhá najít nejlepší odpověď na problémy lineárního programování.
Poskytuje také složitým algoritmům místo, kde začít, a může být použit ke zjištění, zda je lineární program možný nebo ne.
Chcete-li najít všechna základní proveditelná řešení pro lineární program, můžete změnit systém přidáním proměnných nevyužitých hodnot a poté použít změněný systém k nalezení všech základních proveditelných řešení.
Poté se tato základní proveditelná řešení použijí k nalezení základních proveditelných řešení původního problému.
Video: Základní proveditelná řešení
Tip: Pokud potřebujete, zapněte tlačítko titulků. Pokud nejste obeznámeni s mluveným jazykem, vyberte v tlačítku nastavení „automatický překlad“. Než bude váš oblíbený jazyk dostupný pro překlad, možná budete muset nejprve kliknout na jazyk videa.
Případy užití
| Použito v: | Popis: |
|---|---|
| Alokace zdrojů: | BFS lze použít k rozdělení omezených zdrojů mezi několik projektů tak, aby bylo možné udělat maximum s nejmenším. Tato metoda může být použita v mnoha různých oblastech, jako je doprava, zemědělství a finance. |
| Optimalizace sítě: | BFS lze použít ke zlepšení fungování komunikačních, dopravních a logistických sítí. BFS může pomoci najít nejlepší trasy pro zboží a služby, snížit čas a peníze vynaložené na přepravu a zrychlit a zpřesnit dodávky. |
| Plánování výroby: | BFS lze použít k plánování výroby tak, aby zdroje, jako je práce, suroviny a vybavení, byly využity tím nejlepším možným způsobem, aby se z nich dalo co nejvíce. BFS může pomoci snížit výrobní náklady, snížit množství odpadu a zvýšit efektivitu. |
| Finanční plánování: | Ve finančním plánování lze BFS použít k optimalizaci investičních portfolií, snížení rizika a získání co nejvíce peněz zpět. BFS může pomoci najít nejlepší způsob, jak rozdělit aktiva, snížit transakční náklady a vydělat více peněz. |
| Řízení dodavatelského řetězce: | BFS lze použít ke zlepšení toku zboží a služeb od dodavatelů k zákazníkům jako součást řízení dodavatelského řetězce. BFS může pomoci zjistit nejlepší množství zásob, které je třeba mít po ruce, zkrátit dodací lhůty a zlepšit služby zákazníkům. |
Závěr
Když se tento pohled na základní proveditelná řešení blíží ke konci, je jasné, že jsou důležitým nástrojem pro každého inženýra nebo studenta inženýrství.
Základní proveditelná řešení poskytují rámec pro dosažení nejlepšího možného výsledku, od nalezení nejlepšího způsobu, jak postavit komplikovaný systém až po maximální využití dostupných zdrojů.
Ale víc než jen to, že jsou užitečné, ukazují, jak elegantní a krásná může být matematika.
Je úžasné, že složité problémy můžete scvrknout na jednoduchou sadu rovnic a pak tyto rovnice použít k řešení problémů v reálném světě.
Je to dobrá připomínka toho, že inženýrství je především o řešení problémů a že použitím síly matematiky můžeme najít odpovědi, které byly kdysi považovány za nemožné.
Až se tedy budete učit více o strojírenství, mějte na paměti, co jste se naučili o jednoduchých řešeních, která fungují, a použijte je k tomu, aby byl svět lepší a efektivnější.
Odkazy a odkazy
knihy:
- Lineární programování: základy a rozšíření
- Lineární programování: Teorie a aplikace
Sdílet na…
