Ak ste inžinier alebo študent inžinierstva, možno viete, čo to znamená optimalizovať.
Aby ste dosiahli čo najlepší výsledok, je dôležité nájsť najlepší spôsob, ako veci robiť.
V lineárnom programovaní môžete použiť základné riešenie na nájdenie najlepšieho riešenia.
Aké je však základné riešenie a prečo je také dôležité, aby o nich inžinieri vedeli? V tomto článku budem hovoriť o tom, aké sú základné riešenia, prečo sú dôležité v inžinierstve a ako ich možno použiť na dosiahnutie najlepších výsledkov v rôznych situáciách.
Tak sa pripútajte a pripravte sa ponoriť sa do sveta základných riešení, kde vám odhalím záhady a ukážem vám, aká silná môže byť táto technika.
Základné riešenia v lineárnom programovaní
Formálna definícia:
Riešenie lineárneho programového modelu pozostávajúceho z m rovníc v n premenných sa získa riešením pre m premenných z hľadiska zostávajúcich (nm) premenných a nastavením (nm) premenných na nulu.
Základným riešením v lineárnom programovaní je spôsob riešenia problému lineárneho programovania, ktorý spĺňa určité technické požiadavky.
Najmä vektor x je základným riešením pre mnohosten, ak sú vektory {ai : xi = 0} lineárne nezávislé.
To znamená, že stĺpce A, ktoré majú premenné xi, ktoré nie sú nulové, sú lineárne nezávislé.
Základné riešenie s nezápornými zložkami sa nazýva základné realizovateľné riešenie (BFS) (BFS).
BFS spĺňa všetky pravidlá, ktoré definujú mnohosten.
Každý BFS je rohom mnohostenu realizovateľných riešení z geometrického hľadiska.
Ak chcete nájsť základné riešenie, musíte nastaviť nm premenné, ktoré nie sú základné, na nulu a vyriešiť m premenných, ktoré sú základné.
Rôzne bázy môžu viesť k rovnakému základnému riešeniu, čo znamená, že môže existovať viac spôsobov, ako vyriešiť ten istý problém.
Simplexová metóda je iteratívny proces, ktorý prechádza z jedného BFS k ďalšiemu BFS, kým nenájde najlepší BFS.
Po použití simplexnej metódy na nájdenie BFS môžeme zistiť, či je riešenie najlepšie, a to tak, že uvidíme, či nejaké iné BFS v okolí poskytujú lepšiu hodnotu pre cieľovú funkciu.
Ak taký BFS neexistuje, potom je súčasný BFS najlepší.
Model lineárneho programovania
Model lineárneho programovania zahŕňa tri hlavné komponenty: rozhodovacie premenné, cieľovú funkciu a obmedzenia.
Cieľová funkcia aj obmedzenia musia byť lineárne funkcie a rozhodovacie premenné musia byť spojité.
Účelová funkcia sa používa na zvýšenie alebo zníženie čísla, ktoré predstavuje zisk, náklady, počet vyrobených produktov atď.
Obmedzenia sú limity alebo obmedzenia celkového množstva určitého zdroja, ktorý je potrebný na vykonanie úloh, ktoré určia úroveň úspechu v rozhodovacích premenných.
Niektoré lineárne programy navyše vyžadujú, aby všetky rozhodovacie premenné boli nezáporné.
V modeloch lineárneho programovania môžete použiť aj celočíselné a binárne premenné.
Binárne premenné môžu mať iba hodnotu 0 alebo 1, takže môžu mať iba hodnotu 0 alebo 1.
Simplexná metóda
Jedným z najpoužívanejších spôsobov riešenia problémov lineárneho programovania je Simplexová metóda.
Základné riešenia sú v simplexnej metóde dôležité, pretože zodpovedajú rohovým bodom realizovateľnej oblasti a simplexová metóda sa pohybuje z jedného rohu do druhého, kým sa nenájde optimálne riešenie.
Simplexová metóda je rýchly spôsob, ako nájsť najlepšiu odpoveď na problém lineárneho programovania pomocou vlastností základných riešení.
Aby sme mohli použiť simplexnú metódu na nájdenie najlepšieho BFS, musíme nájsť základ B pre maticu obmedzení A a vyriešiť systém Ax = b so všetkými premennými okrem základne nastavenými na nulu.
Výsledné hodnoty pre základné premenné tvoria BFS.
Ak existuje optimálne riešenie, potom existuje aj optimálny BFS.
Simplexná metóda sa presúva z jedného BFS k susednému BFS, kým nedosiahne optimálnu BFS pomocou pivotných procedúr.
Porovnanie základných riešení a realizovateľných riešení
Rozdiel medzi základným riešením a realizovateľným riešením je v tom, že základné riešenie nemusí spĺňať žiadne podmienky.
Najmä musí mať vektory, ktoré sú lineárne nezávislé a majú nenulové hodnoty pre xi a x musí byť menšie ako 0.
Na druhej strane, uskutočniteľným riešením je akýkoľvek bod, ktorý zapadá do hraníc problému.
Ale nie všetky realizovateľné riešenia sú základnými realizovateľnými riešeniami.
Základné realizovateľné riešenia (BFS) sú len tie, ktoré zodpovedajú rohom mnohostenu realizovateľných riešení.
Späť na základy: Odomknutie sily základných riešení v inžinierstve
Stále ťažké pochopiť? Dovolím si trochu zmeniť uhol pohľadu:
Už vás nebaví používať zložité metódy a algoritmy na riešenie ťažkých problémov? Želáte si, aby existoval jednoduchší a priamočiarejší spôsob riešenia problémov s lineárnym programovým modelom?
Nebojte sa, pretože odpoveď je tu: vyriešte pre m premenných z hľadiska zostávajúcich (nm) premenných a nastavte (nm) premenné na nulu.
Kto potrebuje algoritmy, ktoré znejú fantasticky, keď sa môžete vrátiť k základom? Odložte teda kalkulačky a začnime sa učiť o jednoduchých riešeniach.
Dobre, to bol len vtip, ktorý vyzeral ako televízna reklama.
Teraz sa vráťme k vysvetleniu.
Základné riešenie Lineárne programovanie
Tip: Ak potrebujete, zapnite tlačidlo titulkov. Ak nie ste oboznámení s hovoreným jazykom, vyberte v tlačidle nastavení „automatický preklad“. Možno budete musieť najskôr kliknúť na jazyk videa, až potom bude váš obľúbený jazyk dostupný na preklad.
Prípady použitia
| Použité v: | Popis: |
|---|---|
| Pridelenie zdrojov: | Základné riešenie je možné použiť pri problémoch s alokáciou zdrojov, kde cieľom je rozdeliť obmedzené zdroje medzi konkurenčné potreby. Spoločnosť môže napríklad potrebovať rozdeliť svoj rozpočet medzi rôzne oddelenia alebo projekty. Použitím základných riešení môžu prísť na najlepší spôsob, ako využiť svoje zdroje, aby zarobili čo najviac peňazí alebo míňali čo najmenej. |
| Plánovanie výroby: | Pri plánovaní výroby je možné použiť základné riešenie na nájdenie najlepšej kombinácie produktov, aby ste zarobili čo najviac peňazí. Spoločnosti môžu pomocou základného riešenia nájsť najlepší výrobný mix, ktorý prináša najviac peňazí a najmenej nákladov. |
| Plánovanie: | Základné riešenie možno použiť na to, aby ste zistili, ako naplánovať úlohy alebo úlohy tak, aby sa dali robiť čo najefektívnejšie. Spoločnosť môže napríklad potrebovať naplánovať pracovný čas svojich zamestnancov, aby sa uistili, že majú dostatok pracovníkov, keď je podnik zaneprázdnený. Použitím základného riešenia môžu prísť na najlepší spôsob, ako naplánovať veci tak, aby bolo čo najmenej prestojov a urobilo sa čo najviac práce. |
| Riadenie dodávateľského reťazca: | Pri riadení dodávateľského reťazca je cieľom zabezpečiť, aby sa tovar a služby pohybovali čo najhladšie od dodávateľa k zákazníkovi. Podnik môže napríklad potrebovať nájsť najlepšie trasy na prepravu tovaru, aby náklady boli minimálne a tovar bol dodaný včas. Pomocou základných riešení dokážu nájsť najlepší plán riadenia dodávateľského reťazca, ktorý udrží nízke náklady a zabezpečí spokojnosť zákazníkov. |
| Optimalizácia portfólia: | Pri optimalizácii portfólia, kde je cieľom nájsť najlepší mix investícií, aby ste zarobili čo najviac peňazí pri čo najmenšom riziku, možno použiť základné riešenia. Napríklad investičná spoločnosť môže potrebovať nájsť najlepšiu kombináciu akcií, dlhopisov a iných cenných papierov, aby pomohla svojim klientom dosiahnuť ich investičné ciele. Pomocou jednoduchého riešenia môžu nájsť najlepší spôsob, ako zmiešať svoje portfóliá tak, aby dosiahli čo najlepší výnos a zároveň podstúpili čo najmenšie riziko. |
Záver
Na záver, myšlienka základného riešenia je v oblasti strojárstva veľmi dôležitá a dá sa využiť mnohými rôznymi spôsobmi.
Keď vieme, čo je základné riešenie a čo robí v lineárnom programovaní, môžeme riešenia zlepšovať, znižovať náklady a zefektívňovať ich.
Je však dôležité si uvedomiť, že základné riešenie nie je univerzálne riešenie, aj keď ide o výkonný nástroj.
Aby ste dosiahli čo najlepšie výsledky, každý problém je potrebné starostlivo preskúmať a premyslieť.
Ako inžinieri musíme neustále skúmať, ako nám základné riešenia a ďalšie optimalizačné techniky môžu pomôcť napredovať a prichádzať s novými nápadmi.
Uvedomme si teda silu jednoduchých riešení a pokračujme v posúvaní hraníc toho, čo je možné pomocou nových techník a stratégií.
Odkazy a referencie
knihy:
- Lineárne programovanie Vaška Chvátalu
- Modelovanie a riešenie lineárneho programovania pomocou R od Jose M. Sallana
Zdieľať na…
