Viete, čo to znamená optimalizovať systém, aby ste dosiahli čo najlepší výsledok, ak ste študent inžinierstva alebo inžinier.
Optimalizácia riešenia je kľúčom k úspechu vo všetkom, od budovania mostov až po tvorbu softvéru.
V tomto bode prichádza na rad myšlienka základného realizovateľného riešenia.
Je to základná myšlienka lineárneho programovania, ktorá vám umožňuje zistiť, ktoré zo súboru možných riešení je najlepšie.
Ale prečo na tom tak záleží? V tomto článku budem hovoriť o základných realizovateľných riešeniach a o tom, ako ich možno použiť na riešenie technických problémov v reálnom svete.
Poviem vám, ako ich nájsť, z čoho sú vyrobené a prečo sú dôležité.
Či už ste skúsený inžinier alebo študent, ktorý práve začínate, poďte s nami, keď sa ponorím do sveta základných realizovateľných riešení a ukážem vám, ako využiť silu lineárneho programovania.
Pochopenie základného realizovateľného riešenia
Formálna definícia:
Základné riešenie lineárneho modelu programu, v ktorom sú všetky premenné nezáporné.
Základné realizovateľné riešenie (BFS) je kľúčovou myšlienkou lineárneho programovania, ktorá pomáha nájsť najlepšie riešenia.
BFS je riešenie s najmenším možným počtom nenulových premenných.
Je to roh mnohostenu realizovateľných riešení.
Inými slovami, BFS je základné riešenie, ktoré spĺňa nezáporné obmedzenia a nachádza sa v realizovateľnom regióne alebo problémovej oblasti.
Nájdenie optimálneho základného realizovateľného riešenia
Aby sme našli najlepší BFS, musíme urobiť nasledovné:
- Napíšte program v štandardnej forme pre lineárnu postupnosť.
- Premeňte systém nerovností na rozšírenú maticu.
- Zistite, ktoré premenné sú základné a ktoré nie.
- Zistite, aké sú základné premenné z hľadiska ostatných premenných.
- Vložte tieto výrazy do objektívnej funkcie, aby ste získali funkciu iba premenných, ktoré nie sú základné.
- Nájdite nezákladnú premennú, ktorú možno zvýšiť bez porušenia akýchkoľvek obmedzení a vďaka ktorej bude cieľ fungovať lepšie.
Táto premenná je teraz základnou premennou a jedna z ďalších základných premenných už nie je základnou premennou.
Ak existuje optimálne riešenie, musí byť na jednom z koncov alebo vrcholov oblasti, kde sú možné riešenia.
Takže, ak má LP optimálne riešenie, má optimálne riešenie v extrémnom bode realizovateľného súboru.
Tiež vždy existuje optimálne BFS, ak existuje optimálne riešenie.
Použitie simplexnej metódy na nájdenie optimálneho BFS
Simplexová metóda je algoritmus na riešenie problémov v lineárnom programovaní.
Presúva sa z jedného BFS do „susedného“ BFS pomocou postupu pivot.
V kontingenčnej procedúre sa vyberie nezákladná premenná, ktorá sa stane základnou premennou, a potom sa na riešenie nových základných premenných použije aktuálny BFS.
Keď nie je možné zmeniť žiadnu nezákladnú premennú, aby sa zlepšila funkcia cieľa, algoritmus je hotový.
Prečo sú základné realizovateľné riešenia kľúčové pri riešení zložitých technických problémov
Stále ťažké pochopiť? Dovolím si trochu zmeniť uhol pohľadu:
Kto vlastne potrebuje jednoduché, funkčné odpovede? Stačí dať všetko dokopy a dúfať v to najlepšie.
Veď kto potrebuje optimalizáciu, keď je chaos oveľa zábavnejší? Vitajte vo svete nezáporných premenných, kde je všetko len návrh a zlyhanie je takmer isté.
Alebo je to?
Poďme preskúmať, prečo je zdanlivo základný koncept základných realizovateľných riešení niečím iným, len nie základným a prečo môžu byť len kľúčom k riešeniu aj tých najzložitejších technických problémov.
Dobre, to bol len vtip, ktorý vyzeral ako televízna reklama.
Teraz sa vráťme k vysvetleniu.
Hľadanie základného realizovateľného riešenia
Základné realizovateľné riešenie (BFS) je riešenie problému lineárnej optimalizácie, ktoré spĺňa všetky obmedzenia a má najmenší počet nenulových premenných.
Každý BFS je rohom mnohostenu realizovateľných riešení z geometrického hľadiska.
Ak existuje najlepšie riešenie, musí existovať aj najlepší prvý krok.
V tomto článku si povieme, ako nájsť počiatočné základné uskutočniteľné riešenie, ako nájsť všetky základné realizovateľné riešenia a ako nájsť základné uskutočniteľné riešenie bez premenných nevyužitých vecí.
Nájdenie počiatočného základného realizovateľného riešenia
Môžeme použiť rôzne metódy, v závislosti od toho, ako je problém nastavený, aby sme našli počiatočné základné riešenie, ktoré funguje pre lineárny optimalizačný problém.
Jedným zo spôsobov je pridať k obmedzeniam nerovností premenné uvoľnenia a všetky ostatné premenné nastaviť na nulu.
Slack premenné sa stávajú základnými premennými a zvyšok sú nezákladné premenné.
Dvojfázová metóda Simplex je ďalším spôsobom riešenia problému.
Táto metóda zahŕňa riešenie extra problému lineárneho programovania s cieľom nájsť počiatočné základné riešenie, ktoré je uskutočniteľné.
Po nájdení počiatočného základného realizovateľného riešenia možno použiť metódu Simplex na prechod od jedného základného realizovateľného riešenia k ďalšiemu a potom k najlepšiemu riešeniu.
Hľadanie všetkých základných realizovateľných riešení
Pre lineárny program môže existovať viacero základných riešení.
Môžeme zmeniť systém pridaním voľných premenných a potom použiť nový systém na nájdenie všetkých základných realizovateľných riešení pre lineárny program.
Potom sa tieto základné realizovateľné riešenia použijú na nájdenie základných realizovateľných riešení pôvodného problému.
Nájdenie základného realizovateľného riešenia bez premenných nevyužitých
Musíme použiť premenné nevyužitia, aby sme sa zbavili obmedzení, aby sme mohli nájsť základné riešenie, ktoré funguje bez premenných nevyužitých.
Premenná uvoľnenia je len rozdiel medzi pravou stranou obmedzenia a ľavou stranou.
Napríklad pre prvé obmedzenie definujeme premennú uvoľnenia x4 = 14 - 2x1 - x2 - x3. Z hľadiska tejto novej premennej je prvé obmedzenie ekvivalentné jednoducho x4 ≥ 0, čo je kladné obmedzenie pre x4.
Keď spočítame tieto premenné, dostaneme lineárny program, ktorý je rovnaký ako pôvodný, až na to, že všetky obmedzenia sú buď rovnice, alebo obmedzenia, ktoré hovoria, že niečo je kladné.
Množina základných premenných, ktoré majú v základnom riešení iné hodnoty ako nula, sa nazýva báza.
Premenné, ktoré majú v základnom riešení nulovú hodnotu, nie sú základnými premennými.
Aby sme našli najlepšie riešenie, musíme nájsť vektor x, ktorý spĺňa všetky pravidlá a má najväčšiu alebo najmenšiu hodnotu pre cieľ.
Nájdenie najlepšieho riešenia si však vyžaduje viac krokov, než len nájsť riešenie, ktoré funguje a nemá žiadne premenné.
Nie je vždy možné nájsť základné riešenie bez voľných premenných, najmä pri problémoch s menšími obmedzeniami.
Ak chcete nájsť základné možné riešenie, musíte použiť simplexnú metódu alebo iný algoritmus lineárneho programovania, aby ste našli riešenie, ktoré spĺňa všetky obmedzenia a má najmenej nenulových premenných.
Vlastnosti a význam základného realizovateľného riešenia
Vlastnosti základného realizovateľného riešenia
Základné realizovateľné riešenie má najviac m premenných, ktoré nie sú nula a najmenej nm premenných, ktoré sú nulové, kde n je počet rozhodovacích premenných a m je počet obmedzení.
BFS je rohom mnohostenu možných riešení a každý BFS má n aktívnych obmedzení, ktoré sú lineárne nezávislé.
Ak existuje najlepšie riešenie, musí existovať aj najlepší prvý krok.
Najdôležitejšia vec na základných realizovateľných riešeniach je, že sú to konce množiny konvexných riešení problému lineárneho programovania.
Aby sa našla najlepšia odpoveď, simplexný algoritmus prechádza sériou BFS.
Simplexový algoritmus prehľadne prehľadá všetky základné možné riešenia, aby našiel to najlepšie.
Význam základného realizovateľného riešenia
Hľadanie základného riešenia, ktoré je možné, je dôležité, pretože pomáha nájsť najlepšiu odpoveď na problémy lineárneho programovania.
Poskytuje tiež miesto pre spustenie zložitých algoritmov a môže sa použiť na zistenie, či je lineárny program možný alebo nie.
Ak chcete nájsť všetky základné možné riešenia pre lineárny program, môžete zmeniť systém pridaním premenných nevyužitých a potom použiť zmenený systém na nájdenie všetkých základných realizovateľných riešení.
Potom sa tieto základné realizovateľné riešenia použijú na nájdenie základných realizovateľných riešení pôvodného problému.
Video: Základné realizovateľné riešenia
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: | BFS možno použiť na rozdelenie obmedzených zdrojov medzi viacero projektov tak, aby sa dalo urobiť čo najviac s čo najmenším počtom. Táto metóda môže byť použitá v mnohých rôznych oblastiach, ako je doprava, poľnohospodárstvo a financie. |
| Optimalizácia siete: | BFS možno použiť na zlepšenie fungovania komunikačných, dopravných a logistických sietí. BFS môže pomôcť nájsť najlepšie trasy pre tovar a služby, skrátiť čas a peniaze vynaložené na prepravu a zrýchliť a zabezpečiť presnejšie dodávky. |
| Plánovanie výroby: | BFS možno použiť na plánovanie výroby tak, aby sa zdroje ako pracovná sila, suroviny a vybavenie využívali najlepším možným spôsobom, aby sa z nich vyťažilo maximum. BFS môže pomôcť znížiť výrobné náklady, znížiť množstvo odpadu a zvýšiť efektivitu. |
| Finančné plánovanie: | Vo finančnom plánovaní možno BFS použiť na optimalizáciu investičných portfólií, zníženie rizika a získanie čo najväčšieho množstva peňazí späť. BFS môže pomôcť nájsť najlepší spôsob, ako rozdeliť aktíva, znížiť transakčné náklady a zarobiť viac peňazí. |
| Riadenie dodávateľského reťazca: | BFS možno použiť na zlepšenie toku tovaru a služieb od dodávateľov k zákazníkom ako súčasť riadenia dodávateľského reťazca. BFS môže pomôcť určiť najlepšie množstvo zásob, ktoré je potrebné mať po ruke, skrátiť dodacie lehoty a zlepšiť služby zákazníkom. |
Záver
Keď sa tento pohľad na základné realizovateľné riešenia blíži ku koncu, je jasné, že sú dôležitým nástrojom pre každého inžiniera alebo študenta inžinierstva.
Základné realizovateľné riešenia poskytujú rámec na dosiahnutie najlepšieho možného výsledku, od nájdenia najlepšieho spôsobu, ako vybudovať komplikovaný systém až po maximálne využitie dostupných zdrojov.
Ale viac než len to, že sú užitočné, ukazujú, aká elegantná a krásna môže byť matematika.
Je úžasné, že zložité problémy môžete zredukovať na jednoduchý súbor rovníc a potom tieto rovnice použiť na riešenie problémov v reálnom svete.
Je to dobrá pripomienka, že inžinierstvo je predovšetkým o riešení problémov a že pomocou sily matematiky môžeme nájsť odpovede, ktoré sa kedysi považovali za nemožné.
Takže, keď sa dozviete viac o inžinierstve, majte na pamäti, čo ste sa naučili o jednoduchých riešeniach, ktoré fungujú, a použite ich na to, aby bol svet lepším a efektívnejším miestom.
Odkazy a referencie
knihy:
- Lineárne programovanie: základy a rozšírenia
- Lineárne programovanie: teória a aplikácie
Zdieľať na…
