Ha Ön mérnök vagy mérnökhallgató, akkor talán tudja, mit jelent az optimalizálás.
A lehető legjobb eredmény elérése érdekében fontos megtalálni a dolgok legjobb módját.
A lineáris programozásban egy alapmegoldással lehet megtalálni a legjobb megoldást.
De mi az alapmegoldás, és miért olyan fontos, hogy a mérnökök tudjanak róla? Ebben a cikkben arról fogok beszélni, hogy melyek az alapvető megoldások, miért fontosak ezek a mérnöki tudományban, és hogyan használhatók a legjobb eredmény elérése érdekében különböző helyzetekben.
Csatold fel hát, és készülj belemerülni az alapvető megoldások világába, ahol megfejtem a rejtélyeket, és megmutatom, milyen erős is lehet ez a technika.
Alapvető megoldások a lineáris programozásban
Formális meghatározás:
Az n változóban lévő m egyenletből álló lineáris programmodell megoldását úgy kapjuk meg, hogy m változóra megoldjuk a fennmaradó (nm) változókat, és az (nm) változókat nullára állítjuk.
A lineáris programozás alapvető megoldása a lineáris programozási probléma megoldásának módja, amely megfelel bizonyos műszaki követelményeknek.
Konkrétan egy x vektor alapmegoldás egy poliéderre, ha az {ai : xi = 0} vektorok lineárisan függetlenek.
Ez azt jelenti, hogy A azon oszlopai, amelyek xi változói nem nullák, lineárisan függetlenek.
A nemnegatív komponenseket tartalmazó alapmegoldást alapvető megvalósítható megoldásnak (BFS) (BFS) nevezzük.
A BFS megfelel a poliédereket meghatározó összes szabálynak.
Mindegyik BFS egy sarka a geometriai szempontból megvalósítható megoldások poliéderének.
Az alapmegoldás megtalálásához nm nem alapváltozót kell nullára állítani, és meg kell oldani az m változót, amelyek alapvetőek.
Lehetséges, hogy különböző alapok ugyanahhoz az alapmegoldáshoz vezetnek, ami azt jelenti, hogy ugyanazt a problémát többféleképpen lehet megoldani.
A szimplex módszer egy iteratív folyamat, amely az egyik BFS-ről a következő BFS-re lép, amíg meg nem találja a legjobb BFS-t.
Miután a szimplex módszerrel kerestünk egy BFS-t, meg tudjuk állapítani, hogy a megoldás a legjobb-e, ha megnézzük, hogy a közelben található más BFS jobb értéket ad-e a célfüggvény számára.
Ha nincs ilyen BFS, akkor a jelenlegi BFS a legjobb.
Lineáris programozási modell
A lineáris programozási modell három fő összetevőből áll: döntési változókból, célfüggvényből és megszorításokból.
Mind a célfüggvénynek, mind a kényszereknek lineáris függvényeknek, a döntési változóknak pedig folytonosoknak kell lenniük.
A célfüggvény arra szolgál, hogy növelje vagy csökkentse a nyereséget, költséget, a gyártott termékek számát stb.
A megszorítások egy bizonyos erőforrás teljes mennyiségére vonatkozó korlátok vagy korlátozások, amelyek a döntési változók sikerének szintjét meghatározó feladatok elvégzéséhez szükségesek.
Ezenkívül néhány lineáris program megköveteli, hogy minden döntési változó nenegatív legyen.
A lineáris programozási modellekben használhatunk egész és bináris változókat is.
A bináris változók értéke csak 0 vagy 1 lehet, tehát csak 0 vagy 1 lehet.
A szimplex módszer
A lineáris programozási problémák megoldásának egyik leggyakrabban használt módja a szimplex módszer.
Az alapmegoldások azért fontosak a szimplex módszerben, mert megfelelnek a megvalósítható tartomány sarokpontjainak, és a szimplex módszer az egyik sarokból a másikba mozog, amíg meg nem születik az optimális megoldás.
A szimplex módszer egy gyors módja annak, hogy az alapmegoldások tulajdonságait felhasználva megtaláljuk a legjobb választ egy lineáris programozási problémára.
Ahhoz, hogy a szimplex módszerrel megtaláljuk a legjobb BFS-t, meg kell találnunk egy B bázist az A kényszermátrixhoz, és meg kell oldanunk az Ax = b rendszert a nullára állított bázison kívül minden változóval.
Az alapváltozók kapott értékei egy BFS-t alkotnak.
Ha létezik optimális megoldás, akkor létezik optimális BFS.
A szimplex módszer az egyik BFS-ről egy szomszédos BFS-re lép, amíg el nem éri az optimális BFS-t a pivot eljárások segítségével.
Az alapmegoldások és a megvalósítható megoldások összehasonlítása
Az alapmegoldás és a megvalósítható megoldás között az a különbség, hogy az alapmegoldásnak semmilyen feltételnek nem kell megfelelnie.
Konkrétan olyan vektorokkal kell rendelkeznie, amelyek lineárisan függetlenek, és xi értéke nem nulla, és x-nek 0-nál kisebbnek kell lennie.
Másrészt megvalósítható megoldás minden olyan pont, amely belefér a probléma határai közé.
De nem minden megvalósítható megoldás az alapvető megvalósítható megoldás.
Az alapvető megvalósítható megoldások (BFS) csak azok, amelyek illeszkednek a megvalósítható megoldások poliéderének sarkaihoz.
Vissza az alapokhoz: Az alapvető megoldások erejének felszabadítása a tervezésben
Még mindig nehéz megérteni? Hadd változtassak egy kicsit a nézőponton:
Eleged van a bonyolult módszerek és algoritmusok használatából a nehéz problémák megoldására? Szeretné, ha lenne egy egyszerűbb és egyértelműbb módja a lineáris programmodell problémáinak kezelésére?
Nos, ne aggódjon, mert a válasz itt van: oldjon meg m változót a fennmaradó (nm) változók alapján, és állítsa az (nm) változókat nullára.
Kinek kellenek olyan jól hangzó algoritmusok, ha vissza lehet térni az alapokhoz? Tehát tegye el a számológépeit, és kezdje el az egyszerű megoldások megismerését.
Oké, ez csak egy vicc volt, hogy úgy nézzen ki, mint egy tévéreklám.
Most térjünk vissza a magyarázathoz.
Alapvető megoldás Lineáris programozás
Tipp: Kapcsolja be a felirat gombot, ha szüksége van rá. Ha nem ismeri a beszélt nyelvet, válassza az „automatikus fordítás” lehetőséget a beállítások gombban. Előfordulhat, hogy először a videó nyelvére kell kattintania, mielőtt kedvenc nyelve elérhetővé válik a fordításhoz.
Használati esetek
| Használt: | Leírás: |
|---|---|
| Az erőforrások elosztása: | Az alapmegoldás az erőforrás-allokációs problémákban használható, ahol a cél a korlátozott erőforrások felosztása a versengő igények között. Például előfordulhat, hogy egy vállalatnak meg kell osztania a költségvetését a különböző részlegek vagy projektek között. Az alapvető megoldások használatával kitalálhatják, hogyan használhatják fel erőforrásaikat a legjobban a legtöbb bevétel vagy a lehető legkevesebb kiadás érdekében. |
| A gyártás tervezése: | A gyártástervezés során az alapmegoldás felhasználható arra, hogy kitaláljuk a termékek legjobb keverékét, hogy a legtöbb pénzt keressük. A cégek az alapmegoldás használatával megtalálhatják a legjobb termelési keveréket, amely a legtöbb pénzt hozza és a legkevesebb költséget okozza. |
| Ütemezés: | Az alapmegoldás segítségével kitalálható, hogyan ütemezzük a feladatokat vagy munkákat úgy, hogy azokat a leghatékonyabb módon lehessen elvégezni. Előfordulhat például, hogy egy vállalatnak meg kell terveznie az alkalmazottak munkaidejét, hogy megbizonyosodjon arról, hogy elegendő munkavállalójuk van, amikor az üzlet elfoglalt. Egy alapmegoldás használatával kitalálhatják a legjobb módot a dolgok ütemezésére, hogy a lehető legkevesebb állásidő legyen, és minél több munka legyen elvégezve. |
| Az ellátási lánc irányítása: | Az ellátási lánc menedzsmentjében az a cél, hogy az áruk és szolgáltatások a lehető legzökkenőmentesebben kerüljenek a szállítótól a vevőig. Például előfordulhat, hogy egy vállalkozásnak ki kell találnia a legjobb útvonalakat az áruszállításhoz, hogy a költségeket a lehető legalacsonyabb szinten tartsák, és az árukat időben kézbesítsék. Az alapvető megoldások használatával megtalálhatják a legjobb tervet az ellátási lánc kezeléséhez, amely alacsonyan tartja a költségeket és elégedetté teszi az ügyfeleket. |
| Portfólió optimalizálás: | A portfólióoptimalizálásban, ahol a befektetések legjobb keverékének megtalálása a cél, hogy a lehető legtöbb bevételt és a legkisebb kockázatot vállalva hozzanak létre, alapvető megoldások használhatók. Például előfordulhat, hogy egy befektetési vállalkozásnak ki kell találnia a részvények, kötvények és egyéb értékpapírok legjobb keverékét, hogy segítse ügyfeleit befektetési céljaik elérésében. Egy egyszerű megoldás segítségével megtalálhatják a legjobb módot portfólióik keverésére, hogy a lehető legjobb hozamot érjék el, miközben a legkisebb kockázatot vállalják. |
Következtetés
Összefoglalva, az alapmegoldás ötlete nagyon fontos a mérnöki területen, és sokféleképpen felhasználható.
Ha tudjuk, mi az alapmegoldás, és mit csinál a lineáris programozásban, javíthatjuk a megoldásokat, csökkenthetjük a költségeket és hatékonyabbá tehetjük azokat.
De nem szabad elfelejteni, hogy az alapmegoldás nem egy mindenre alkalmas megoldás, még akkor sem, ha hatékony eszköz.
A legjobb eredmény elérése érdekében minden problémát alaposan meg kell vizsgálni és át kell gondolni.
Mérnökként folyamatosan vizsgálnunk kell, hogy az alapvető megoldások és egyéb optimalizálási technikák hogyan segíthetnek előrelépésben és új ötletekkel.
Tehát ismerjük fel az egyszerű megoldások erejét, és feszegessük tovább annak határait, ami új technikák és stratégiák segítségével lehetséges.
Linkek és hivatkozások
Könyvek:
- Lineáris programozás, Vasek Chvatal
- Lineáris programozás modellezése és megoldása R-vel, Jose M. Sallan
Oszd meg…
