Tudja, mit jelent egy rendszer optimalizálása a lehető legjobb eredmény elérése érdekében, ha Ön mérnökhallgató vagy mérnök.
A megoldás optimalizálása a siker kulcsa a hidak építésétől a szoftverkészítésig.
Ezen a ponton merül fel az alapvető megvalósítható megoldás ötlete.
Ez egy alapötlet a lineáris programozásban, amely lehetővé teszi, hogy kitaláljuk, hogy a lehetséges megoldások közül melyik a legjobb.
De miért számít ez annyira? Ebben a cikkben az alapvető megvalósítható megoldásokról fogok beszélni, és arról, hogyan használhatók fel mérnöki problémák megoldására a való világban.
Beszélni fogok arról, hogyan lehet megtalálni őket, miből készülnek, és miért fontosak.
Tehát, akár tapasztalt mérnök, akár most kezdő diák, jöjjön velünk, amikor belemerülök az alapvető megvalósítható megoldások világába, és megmutatom, hogyan kell kihasználni a lineáris programozás erejét.
Az alapvető megvalósítható megoldás megértése
Formális meghatározás:
Egy lineáris programmodell alapvető megoldása, amelyben minden változó nemnegatív.
Az alapvető megvalósítható megoldás (BFS) kulcsfontosságú ötlet a lineáris programozásban, amely segít megtalálni a legjobb megoldásokat.
A BFS olyan megoldás, amely a lehető legkisebb számú nem nullától eltérő változót tartalmaz.
A megvalósítható megoldások poliéderének sarka.
Más szóval, a BFS olyan alapvető megoldás, amely megfelel a nem negatív megszorításoknak, és a megvalósítható régióban vagy problématerületen található.
Az optimális alapvető megvalósítható megoldás megtalálása
A legjobb BFS megtalálásához a következőket kell tennünk:
- Írja fel a programot szabványos formában lineáris sorozathoz!
- Alakítsd az egyenlőtlenségek rendszerét kiterjesztett mátrixsá.
- Nézze meg, mely változók alapvetőek és melyek nem.
- Nézze meg, melyek az alapvető változók a többi változóhoz képest.
- Helyezze ezeket a kifejezéseket a célfüggvénybe, hogy csak a nem alapvető változók függvénye legyen.
- Keressen egy nem alapváltozót, amely megszorítások nélkül növelhető, és amely javítja a célfüggvényt.
Ez a változó most alapváltozó, és a többi alapváltozó egyike már nem alapváltozó.
Ha van optimális megoldás, akkor annak a tartomány egyik végén vagy csúcsán kell lennie, ahol a megoldás lehetséges.
Tehát, ha egy LP-nek van optimális megoldása, akkor a megvalósítható halmaz egy szélső pontján van optimális megoldása.
Emellett mindig van optimális BFS, ha van optimális megoldás.
A szimplex módszer használata az optimális BFS megtalálásához
A szimplex módszer a lineáris programozás problémáinak megoldására szolgáló algoritmus.
Az egyik BFS-ről a "szomszédos" BFS-re lép a pivot eljárással.
A pivot eljárásban egy nem alapváltozót választunk ki alapváltozóvá, majd az aktuális BFS-t használják az új alapváltozók megoldására.
Ha egyetlen nem alapváltozó sem módosítható a célfüggvény jobbá tétele érdekében, az algoritmus elkészül.
Miért elengedhetetlenek az alapvető megvalósítható megoldások az összetett mérnöki problémák megoldásához?
Még mindig nehéz megérteni? Hadd változtassak egy kicsit a nézőponton:
Kinek kellenek egyébként egyszerű, működőképes válaszok? Csak dobj össze mindent, és reméld a legjobbat.
Végül is kinek van szüksége optimalizálásra, amikor a káosz sokkal szórakoztatóbb? Üdvözöljük a nemnegatív változók világában, ahol minden csak javaslat, és a kudarc szinte biztos.
Vagy ez?
Vizsgáljuk meg, hogy az alapvető megvalósítható megoldások alapvetőnek tűnő koncepciója miért nem más, mint alapvető, és miért lehetnek ezek a kulcsok még a legösszetettebb mérnöki problémák megoldásában is.
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.
Az alapvető megvalósítható megoldás megtalálása
Az alapvető megvalósítható megoldás (BFS) egy lineáris optimalizálási probléma megoldása, amely megfelel minden megkötésnek, és a legkevesebb nullától eltérő változót tartalmaz.
Mindegyik BFS egy sarka a geometriai szempontból megvalósítható megoldások poliéderének.
Ha van a legjobb megoldás, akkor meg kell lennie a legjobb első lépésnek is.
Ebben a cikkben arról fogunk beszélni, hogyan találhatunk egy kezdeti alapvető megvalósítható megoldást, hogyan találhatunk meg minden alapvető megvalósítható megoldást, és hogyan találhatunk egy alapvető megvalósítható megoldást laza változók nélkül.
A kezdeti, megvalósítható megoldás megtalálása
A probléma felállításától függően különböző módszereket használhatunk, hogy megtaláljuk a kezdeti alapmegoldást, amely egy lineáris optimalizálási probléma esetén működik.
Az egyik módja az, hogy laza változókat adunk az egyenlőtlenségek megszorításaihoz, és az összes többi változót nullára állítjuk.
A laza változók alapváltozókká válnak, a többi pedig nem alapváltozó.
A probléma megoldásának másik módja a kétfázisú szimplex módszer.
Ez a módszer egy extra lineáris programozási probléma megoldását foglalja magában, hogy megtaláljuk a megvalósítható kezdeti alapvető megoldást.
Miután megtaláltuk a kezdeti alapvető megvalósítható megoldást, a Simplex módszerrel át lehet lépni az egyik lehetséges alapvető megoldásról a másikra, majd a legjobb megoldásra.
Az összes megvalósítható alapvető megoldás megtalálása
Egy lineáris programnál több alapmegoldás is működhet.
Megváltoztathatjuk a rendszert laza változók hozzáadásával, majd az új rendszer segítségével megtalálhatjuk az összes alapvető megvalósítható megoldást egy lineáris programhoz.
Ezután ezeket az alapvető megvalósítható megoldásokat használják az eredeti probléma alapvető megvalósítható megoldásainak megtalálásához.
Alapvető megvalósítható megoldás keresése laza változók nélkül
Slack változókat kell használnunk, hogy megszabaduljunk a kevésbé megszorításoktól, hogy olyan alapvető megoldást találjunk, amely laza változók nélkül is működik.
A laza változó csak a különbség a megszorítás jobb oldala és a bal oldala között.
Például az első megszorításhoz definiálunk egy laza változót: x4 = 14 - 2x1 - x2 - x3. Az új változó szempontjából az első megszorítás egyszerűen ekvivalens x4 ≥ 0-val, ami az x4 pozitivitási megkötése.
Ha hozzáadjuk ezeket a laza változókat, egy lineáris programot kapunk, amely megegyezik az eredetivel, azzal a különbséggel, hogy az összes megszorítás vagy egyenlet vagy megszorítás, amely valami pozitívat mond.
Az alapváltozók azon halmazát, amelyeknek az alapmegoldásban nullától eltérő értéke van, bázisnak nevezzük.
Azok a változók, amelyeknek az alapmegoldásban az értéke nulla, nem alapváltozók.
A legjobb megoldás megtalálásához olyan x vektort kell találnunk, amely megfelel minden szabálynak, és a cél legnagyobb vagy legkisebb értékét kapja.
A legjobb megoldás megtalálása azonban több lépést igényel, mint egy olyan megoldás megtalálása, amely működik, és nem tartalmaz laza változókat.
Nem mindig lehet olyan alapvető megoldást találni, ahol nincsenek laza változók, különösen a kevésbé megszorításokkal járó problémák esetén.
Egy alapvető megvalósítható megoldás megtalálásához a szimplex módszert vagy egy másik lineáris programozási algoritmust kell használni, hogy olyan megoldást keressünk, amely megfelel minden megkötésnek, és a legkevesebb nem nullától eltérő változót tartalmaz.
Az alapvető megvalósítható megoldás tulajdonságai és jelentősége
Az alapvető megvalósítható megoldás tulajdonságai
Egy alapvető megvalósítható megoldásban legfeljebb m olyan változó van, amely nem nulla, és legalább nm olyan változó, amely nulla, ahol n a döntési változók száma, m pedig a megszorítások száma.
A BFS a lehetséges megoldások poliéderének egy sarka, és minden BFS-nek n aktív kényszere van, amelyek lineárisan függetlenek.
Ha van a legjobb megoldás, akkor meg kell lennie a legjobb első lépésnek is.
Az alapvető megvalósítható megoldásoknál az a legfontosabb, hogy egy lineáris programozási probléma konvex megoldásainak végeit jelentik.
A legjobb válasz megtalálásához a szimplex algoritmus egy sor BFS-en megy keresztül.
A Simplex Algoritmus szervezett módon végigkeresi az összes alapvető lehetséges megoldást, hogy megtalálja a legjobbat.
Az alapvető megvalósítható megoldás jelentősége
A lehetséges alapvető megoldás megtalálása azért fontos, mert ez segít megtalálni a legjobb választ a lineáris programozási problémákra.
Ezenkívül bonyolult algoritmusoknak is kiindulópontot ad, és felhasználható annak kiderítésére, hogy egy lineáris program lehetséges-e vagy sem.
A lineáris program összes megvalósítható alapvető megoldásának megtalálásához módosíthatja a rendszert laza változók hozzáadásával, majd a megváltozott rendszer segítségével megtalálhatja az összes megvalósítható alapvető megoldást.
Ezután ezeket az alapvető megvalósítható megoldásokat használják az eredeti probléma alapvető megvalósítható megoldásainak megtalálásához.
Videó: Alapvető megvalósítható megoldások
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: | A BFS segítségével a korlátozott erőforrásokat fel lehet osztani több projekt között, hogy a legtöbbet meg lehessen tenni a legkevesebbből. Ez a módszer számos különböző területen alkalmazható, mint például a szállítás, a mezőgazdaság és a pénzügy. |
| A hálózat optimalizálása: | A BFS felhasználható a kommunikációs, szállítási és logisztikai hálózatok jobb működésére. A BFS segíthet megtalálni a legjobb útvonalakat az áruk és szolgáltatások számára, csökkentheti a szállításra fordított időt és pénzt, valamint felgyorsíthatja és pontosabb szállítást végezhet. |
| A gyártás tervezése: | A BFS segítségével megtervezheti a termelést úgy, hogy az erőforrásokat, például a munkaerőt, a nyersanyagokat és a berendezéseket a lehető legjobb módon használják fel, hogy a legtöbbet hozhassák ki belőlük. A BFS segíthet csökkenteni a termelési költségeket, csökkenteni a hulladék mennyiségét és javítani a hatékonyságot. |
| Pénzügyi tervezés: | A pénzügyi tervezésben a BFS felhasználható a befektetési portfóliók optimalizálására, a kockázat csökkentésére és a legtöbb pénz visszaszerzésére. A BFS segíthet megtalálni a legjobb módot az eszközök felosztására, csökkentheti a tranzakciós költségeket és több pénzt kereshet. |
| Az ellátási lánc irányítása: | A BFS segítségével javítható az áruk és szolgáltatások áramlása a beszállítóktól az ügyfelekig az ellátási lánc menedzsment részeként. A BFS segíthet kitalálni a legjobban kéznél tartható készletmennyiséget, lerövidíti az átfutási időt és javítja az ügyfélszolgálatot. |
Következtetés
Amint az alapvető megvalósítható megoldások áttekintése a végéhez közeledik, nyilvánvaló, hogy ezek minden mérnök vagy mérnökhallgató számára fontos eszközt jelentenek.
A bonyolult rendszer felépítésének legjobb módjának kitalálásától a rendelkezésre álló erőforrások maximális kihasználásáig az alapvető megvalósítható megoldások keretet adnak a lehető legjobb eredmény eléréséhez.
De nemcsak hasznosak, hanem megmutatják, milyen elegáns és szép is lehet a matematika.
Csodálatos, hogy a bonyolult problémákat egyszerű egyenletcsoportokká lehet levezetni, majd ezeket az egyenleteket a való világban felmerülő problémák megoldására használhatja.
Jó emlékeztető arra, hogy a mérnöki munka a problémák megoldásáról szól, és hogy a matematika erejét felhasználva olyan válaszokat találhatunk, amelyeket korábban lehetetlennek hittünk.
Tehát, amikor többet tanul a mérnöki tudományokról, tartsa észben, amit az egyszerű, működő megoldásokról tanult, és használja őket a világ jobbá és hatékonyabbá tételére.
Linkek és hivatkozások
Könyvek:
- Lineáris programozás: alapok és bővítmények
- Lineáris programozás: elmélet és alkalmazások
Oszd meg…
