Pokud jste inženýr nebo student inženýrství, možná víte, co to znamená optimalizovat.
Abyste dosáhli co nejlepšího výsledku, je důležité najít nejlepší způsob, jak věci dělat.
V lineárním programování můžete použít základní řešení k nalezení nejlepšího řešení.
Co je ale základní řešení a proč je tak důležité, aby o nich inženýři věděli? V tomto článku budu mluvit o tom, co jsou základní řešení, proč jsou důležitá ve strojírenství a jak je lze použít k dosažení nejlepších výsledků v různých situacích.
Takže se připoutejte a připravte se ponořit se do světa základních řešení, kde vám odhalím záhady a ukážu vám, jak mocná tato technika může být.
Základní řešení v lineárním programování
Formální definice:
Řešení lineárního programového modelu sestávajícího z m rovnic v n proměnných se získá řešením pro m proměnných pomocí zbývajících (nm) proměnných a nastavením (nm) proměnných na nulu.
Základní řešení v lineárním programování je způsob řešení problému lineárního programování, který splňuje určité technické požadavky.
Zejména vektor x je základním řešením pro mnohostěn, pokud jsou vektory {ai : xi = 0} lineárně nezávislé.
To znamená, že sloupce A, které mají proměnné xi, které nejsou nulové, jsou lineárně nezávislé.
Základní řešení s nezápornými složkami se nazývá základní proveditelné řešení (BFS) (BFS).
BFS splňuje všechna pravidla, která definují mnohostěn.
Každý BFS je rohem mnohostěnu proveditelných řešení z geometrického hlediska.
Chcete-li najít základní řešení, musíte nastavit nm proměnné, které nejsou základní, na nulu a vyřešit m proměnných, které jsou základní.
Je možné, že různé báze vedou ke stejnému základnímu řešení, což znamená, že může existovat více než jeden způsob řešení stejného problému.
Simplexní metoda je iterativní proces, který se přesouvá od jednoho BFS k dalšímu BFS, dokud nenajde nejlepší BFS.
Po použití simplexní metody k nalezení BFS můžeme zjistit, zda je řešení nejlepší tím, že uvidíme, zda nějaké jiné BFS poblíž dávají lepší hodnotu pro účelovou funkci.
Pokud takový BFS neexistuje, pak je aktuální BFS nejlepší.
Model lineárního programování
Model lineárního programování zahrnuje tři hlavní komponenty: rozhodovací proměnné, účelovou funkci a omezení.
Cílová funkce i omezení musí být lineární funkce a rozhodovací proměnné musí být spojité.
Objektivní funkce se používá ke zvýšení nebo snížení čísla, které představuje zisk, náklady, počet vyrobených produktů atd.
Omezení jsou limity nebo omezení celkového množství určitého zdroje, který je potřebný k provedení úkolů, které určují úroveň úspěchu v rozhodovacích proměnných.
Některé lineární programy navíc vyžadují, aby všechny rozhodovací proměnné byly nezáporné.
V modelech lineárního programování můžete také použít celočíselné a binární proměnné.
Binární proměnné mohou mít pouze hodnotu 0 nebo 1, takže mohou mít pouze hodnotu 0 nebo 1.
Simplexní metoda
Jedním z nejpoužívanějších způsobů řešení problémů lineárního programování je Simplexová metoda.
Základní řešení jsou v simplexové metodě důležitá, protože odpovídají rohovým bodům proveditelné oblasti a simplexová metoda se pohybuje z jednoho rohu do druhého, dokud není nalezeno optimální řešení.
Simplexová metoda je rychlý způsob, jak najít nejlepší odpověď na problém lineárního programování pomocí vlastností základních řešení.
Abychom mohli pomocí simplexové metody najít nejlepší BFS, musíme najít základ B pro matici omezení A a vyřešit systém Ax = b se všemi proměnnými kromě základu nastavenými na nulu.
Výsledné hodnoty pro základní proměnné tvoří BFS.
Pokud existuje optimální řešení, pak existuje optimální BFS.
Simplexní metoda se přesouvá z jednoho BFS na sousední BFS, dokud nedosáhne optimálního BFS pomocí pivotních procedur.
Srovnání mezi základními řešeními a proveditelnými řešeními
Rozdíl mezi základním řešením a proveditelným řešením je v tom, že základní řešení nemusí splňovat žádné podmínky.
Zejména musí mít vektory, které jsou lineárně nezávislé a mají nenulové hodnoty pro xi a x musí být menší než 0.
Na druhou stranu, proveditelným řešením je jakýkoli bod, který zapadá do mezí problému.
Ale ne všechna proveditelná řešení jsou základní proveditelná řešení.
Základní proveditelná řešení (BFS) jsou pouze ta, která odpovídají rohům mnohostěnu proveditelných řešení.
Zpět k základům: Odemknutí síly základních řešení ve strojírenství
Stále těžké pochopit? Dovolím si trochu změnit úhel pohledu:
Už vás nebaví používat složité metody a algoritmy k řešení těžkých problémů? Přáli byste si, aby existoval jednodušší a přímočařejší způsob, jak se vypořádat s problémy s lineárním programovým modelem?
No, nebojte se, protože odpověď je zde: řešte pro m proměnných z hlediska zbývajících (nm) proměnných a nastavte (nm) proměnných na nulu.
Kdo potřebuje algoritmy, které zní fantasticky, když se můžete vrátit k základům? Odložte tedy kalkulačky a pojďme se začít učit o jednoduchých řešeních.
Dobře, to byl jen vtip, který vypadal jako televizní reklama.
Nyní se vraťme k vysvětlení.
Základní řešení Lineární programování
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ů: | Základní řešení lze použít v problémech s alokací zdrojů, kde je cílem rozdělit omezené zdroje mezi konkurenční potřeby. Společnost může například potřebovat rozdělit svůj rozpočet mezi různá oddělení nebo projekty. Pomocí základních řešení mohou přijít na nejlepší způsob, jak využít své zdroje, aby vydělali co nejvíce peněz nebo utratili co nejméně. |
| Plánování výroby: | Při plánování výroby lze základní řešení použít k nalezení nejlepší kombinace produktů, které lze vyrobit, abyste vydělali co nejvíce peněz. Společnosti mohou pomocí základního řešení najít nejlepší výrobní mix, který přináší nejvíce peněz a nejnižší náklady. |
| Plánování: | Základní řešení lze použít k tomu, abyste zjistili, jak naplánovat úkoly nebo úlohy tak, aby mohly být provedeny co nejefektivněji. Společnost může například potřebovat naplánovat pracovní dobu svých zaměstnanců, aby se ujistila, že mají dostatek pracovníků, když je podnikání vytížené. Pomocí základního řešení mohou přijít na nejlepší způsob, jak naplánovat věci tak, aby byly co nejmenší prostoje a udělalo se co nejvíce práce. |
| Řízení dodavatelského řetězce: | V řízení dodavatelského řetězce je cílem zajistit, aby se zboží a služby pohybovaly co nejhladším způsobem od dodavatele k zákazníkovi. Podnik může například potřebovat vymyslet nejlepší trasy pro přepravu zboží, aby náklady byly co nejnižší a zboží bylo doručeno včas. Pomocí základních řešení mohou najít nejlepší plán pro řízení dodavatelského řetězce, který udržuje nízké náklady a udržuje zákazníky spokojené. |
| Optimalizace portfolia: | Při optimalizaci portfolia, kde je cílem najít nejlepší mix investic, abyste vydělali co nejvíce peněz při co nejmenším riziku, lze použít základní řešení. Investiční firma může například potřebovat najít nejlepší kombinaci akcií, dluhopisů a dalších cenných papírů, aby pomohla svým klientům dosáhnout jejich investičních cílů. Pomocí jednoduchého řešení mohou najít nejlepší způsob, jak namíchat svá portfolia tak, aby získali nejlepší výnosy a zároveň podstupovali co nejmenší riziko. |
Závěr
Závěrem lze říci, že myšlenka základního řešení je v oblasti strojírenství velmi důležitá a lze ji využít mnoha různými způsoby.
Když víme, co je základní řešení a co dělá v lineárním programování, můžeme řešení zlepšovat, snižovat náklady a zefektivňovat je.
Je však důležité si uvědomit, že základní řešení není univerzální řešení, i když jde o mocný nástroj.
Abyste dosáhli co nejlepších výsledků, je třeba každý problém pečlivě prozkoumat a promyslet.
Jako inženýři musíme neustále zkoumat, jak nám základní řešení a další optimalizační techniky mohou pomoci dosáhnout pokroku a přicházet s novými nápady.
Uvědomme si tedy sílu jednoduchých řešení a nepřestávejme posouvat hranice toho, co je možné, pomocí nových technik a strategií.
Odkazy a odkazy
knihy:
- Lineární programování Vaška Chvátala
- Modelování a řešení lineárního programování pomocí R od Jose M. Sallana
Sdílet na…
