Az optimalizálás segít megtalálni a legjobb eredményt, amely nyereséget hoz, csökkenti a költségeket, vagy olyan paramétert állít be, amely üzleti folyamatok meghibásodását okozza.
Ezt a folyamatot matematikai programozásnak is nevezik. Megoldja az optimalizálási feladat vezetője által kitűzött cél eléréséhez szükséges korlátozott erőforrások elosztásának meghatározását. Az összes lehetséges opció közül kívánatos megtalálni azt, amely maximalizálja (vagy csökkenti) a vezérlő paramétert, például a nyereséget vagy a költséget. Az optimalizálási modelleket előírónak vagy normatívnak is nevezik, mert az üzlet számára megvalósítható stratégiát keresnek.
Fejlesztési előzmények
A lineáris programozás (LP) olyan optimalizálási problémákkal működik, ahol minden kényszer lineáris.
Az LP fejlődésének rövid történetének bemutatása:
- 1762-ben Lagrange egyszerű optimalizálási feladatokat oldott meg egyenlőségi megszorításokkal.
- 1820-ban Gauss úgy döntöttlineáris egyenletrendszer eliminációval.
- 1866-ban Wilhelm Jordan tökéletesítette a legkisebb négyzetek hibáinak megtalálásának módszerét, mint illeszkedési kritériumot. Ezt most Gauss-Jordan módszernek hívják.
- A digitális számítógép 1945-ben jelent meg.
- Danzig 1947-ben találta fel a szimplex módszereket.
- 1968-ban Fiacco és McCormick bevezette az Inside Point módszert.
- 1984-ben Karmarkar a belső módszert alkalmazta lineáris programok megoldására, hozzátéve innovatív elemzését.
Az LP rendkívül hatékony eszköznek bizonyult mind a valós problémák modellezésére, mind pedig széles körben alkalmazott matematikai elméletként. Sok érdekes optimalizálási probléma azonban nem lineáris.
Mi a teendő ebben az esetben? Az ilyen problémák tanulmányozása magában foglalja a lineáris algebra, a többváltozós számítások, a numerikus elemzés és a számítási módszerek változatos keverékét. A tudósok számítási algoritmusokat fejlesztenek, beleértve a belső pontmódszereket lineáris programozáshoz, geometriához, konvex halmazok és függvények elemzéséhez, valamint speciálisan strukturált problémák, például a másodfokú programozás tanulmányozásához.
A nemlineáris optimalizálás alapvető ismereteket nyújt a matematikai elemzésről, és széles körben alkalmazzák különféle területeken, mint például a mérnöki, regressziós elemzés, erőforrás-gazdálkodás, geofizikai feltárás és közgazdaságtan.
Optimalizálási problémák osztályozása
Fontos lépésAz optimalizálási folyamat a modellek osztályozása, mivel megoldási algoritmusaik egy adott típushoz vannak igazítva.
1. Problémák a diszkrét és folyamatos optimalizálással. Egyes modelleknek csak akkor van értelme, ha a változók az egész számok diszkrét részhalmazából vesznek értéket. Mások olyan adatokat tartalmaznak, amelyek bármilyen valós értéket felvehetnek. Általában könnyebben megoldhatók. Az algoritmusok fejlesztései a számítástechnika fejlődésével kombinálva drámaian megnövelték a lineáris programozási optimalizálási probléma méretét és összetettségét.
2. Korlátlan és korlátozott optimalizálás. Egy másik fontos különbség az olyan feladatok, ahol nincs megkötés a változókra vonatkozóan. Az egyszerű becslésektől az adatok közötti összetett kapcsolatokat modellező egyenlőség- és egyenlőtlenségi rendszerekig terjedhet. Az ilyen optimalizálási problémák a függvények jellege szerint tovább osztályozhatók (lineáris és nemlineáris, konvex és sima, differenciálható és nem differenciálható).
3. Megvalósíthatósági feladatok. Céljuk az, hogy olyan változó értékeket találjanak, amelyek kielégítik a modell korlátait, anélkül, hogy bármilyen konkrét optimalizálási célt tennének.
4. Komplementaritási feladatok. Széles körben használják a technológiában és a gazdaságban. A cél a komplementaritási feltételeket kielégítő megoldás megtalálása. A gyakorlatban a több célú feladatokat gyakran újrafogalmazzák egyetlen célú feladatokká.
5. Determinisztikus versus sztochasztikus optimalizálás. A determinisztikus optimalizálás feltételezi, hogy a fora feladatok teljesen pontosak. Sok időszerű kérdésben azonban több okból nem ismerhetők.
Az első egy egyszerű mérési hibával kapcsolatos. A második ok alapvetőbb. Ez abban rejlik, hogy bizonyos adatok a jövőre vonatkozó információkat képviselnek, például egy termék keresletét vagy árát egy jövőbeli időszakra vonatkozóan. Sztochasztikus optimalizálási feltételek mellett végzett optimalizálás esetén a modellben benne van a bizonytalanság is.
Fő összetevők
A célfüggvény az, amelyet minimalizálni vagy maximalizálni kell. A legtöbb optimalizálási feladattípusnak egyetlen célfüggvénye van. Ha nem, akkor gyakran újrafogalmazhatók úgy, hogy működjenek.
Két kivétel ez alól a szabály alól:
1. Cél keresési feladat. A legtöbb üzleti alkalmazásban a menedzser egy konkrét célt szeretne elérni, miközben eleget tesz a modell korlátainak. A felhasználó nem akar különösebben optimalizálni valamit, ezért nincs értelme célfüggvényt definiálni. Ezt a típust általában kielégítési problémának nevezik.
2. Sok objektív tulajdonság. A felhasználó gyakran több különböző célt szeretne egyszerre optimalizálni. Általában összeférhetetlenek. Előfordulhat, hogy az egyik célhoz optimalizáló változók nem a legjobbak mások számára.
Alkatrésztípusok:
- A vezérelt bemenet olyan döntési változók halmaza, amelyek befolyásolják egy célfüggvény értékét. Egy termelési feladatban a változók magukban foglalhatják a különféle rendelkezésre álló erőforrások vagy az ehhez szükséges munkaerő elosztásátminden egyes művelet.
- A kényszerek a döntési változók és paraméterek közötti kapcsolatok. Termelési probléma esetén nincs értelme sok időt tölteni semmilyen tevékenységgel, ezért korlátozza az összes "ideiglenes" változót.
- Lehetséges és optimális megoldások. A változókra vonatkozó döntés azon értékét, amely alatt minden megkötés teljesül, kielégíthetőnek nevezzük. A legtöbb algoritmus először megtalálja, majd megpróbálja javítani. Végül megváltoztatják a változókat, hogy az egyik megvalósítható megoldásról a másikra lépjenek. Ezt a folyamatot addig ismételjük, amíg a célfüggvény el nem éri maximumát vagy minimumát. Ezt az eredményt nevezzük optimális megoldásnak.
A következő matematikai programokhoz kifejlesztett optimalizálási feladatok algoritmusait széles körben használják:
- Konvex.
- Elválasztható.
- Kvadratikus.
- Geometriai.
Google Lineáris Solvers
Lineáris optimalizálás vagy programozás a probléma optimális megoldásának számítási folyamatának elnevezése. Lineáris összefüggések halmazaként modellezték, amelyek számos tudományos és mérnöki tudományágban felmerülnek.
A Google három módszert kínál a lineáris optimalizálási problémák megoldására:
- Glop nyílt forráskódú könyvtár.
- Lineáris optimalizálási bővítmény a Google Táblázatokhoz.
- Lineáris optimalizálási szolgáltatás a Google Apps Scriptben.
A Glop be van építve a Google-balineáris megoldó. Nyílt forráskódban érhető el. A Glop az OR-Tools lineáris megoldó burkolóján keresztül érhető el, amely a Glop burkolója.
A Google Táblázatok lineáris optimalizálási modulja lehetővé teszi az optimalizálási probléma lineáris meghatározását úgy, hogy adatokat ír be egy táblázatba.
Kvadratikus programozás
A Premium Solver platform a Simplex módszer kiterjesztett LP/Quadratic változatát használja LP és QP problémafeldolgozási korlátokkal akár 2000 döntési változóig.
Az SQP Solver nagy léptékű problémákhoz az aktív halmaz módszerének modern megvalósítását használja ritkítással a kvadratikus programozási (QP) problémák megoldására. Az XPRESS Solver motor az "Interior Point" vagy a Newton Barrier módszer természetes kiterjesztését használja a QP problémák megoldására.
MOSEK Solver beágyazott "Belső pont" és automatikus kettős módszereket alkalmaz. Ez különösen hatékony a laza csatolású QP problémák esetén. Megoldhatja a skála kvadratikus kényszer (QCP) és a másodrendű kúpprogramozás (SOCP) problémákat is.
Több műveletes számítások
Elég sikeresen használhatók a Microsoft Office szolgáltatásaival, például az optimalizálási problémák megoldásával Excelben.
A fenti táblázatban a szimbólumok a következők:
- K1 – K6 – olyan ügyfelek, akiknek árukat kell biztosítaniuk.
- Az S1 - S6 potenciális gyártási helyek, amelyek erre építhetők. Létrehozható1, 2, 3, 4, 5 vagy mind a 6 hely.
Az I. oszlopban felsorolt minden létesítményhez fix költségek tartoznak (Fix).
Ha a hely nem változtat semmit, akkor nem számít. Akkor nem lesznek fix költségek.
Azonosítsa a lehetséges helyeket a legalacsonyabb költség elérése érdekében.
E körülmények között a hely vagy létrejön, vagy nem. Ez a két állapot: "IGAZ - HAMIS" vagy "1 - 0". Hat állapot van hat helyhez, például a 000001 csak a hatodik, az 111111 pedig az összes.
A kettes számrendszerben pontosan 63 különböző lehetőség van 000001 (1) és 111111 (63) között.
A L2-L64 feliratnak most a következőnek kell lennie: {=MULTIPLE OPERATION (K1)}, ezek az összes alternatív megoldás eredményei. Ekkor a minimális érték=Min (L), a megfelelő alternatíva pedig INDEX (K).
CPLEX egészszámú programozás
Néha a lineáris kapcsolat nem elegendő egy üzleti probléma lényegéhez. Ez különösen igaz akkor, ha a döntések diszkrét döntéseket foglalnak magukban, például nyitnak-e raktárt egy bizonyos helyen vagy sem. Ezekben a helyzetekben egészszámú programozást kell használni.
Ha a probléma diszkrét és folyamatos választásokat is tartalmaz, akkor ez egy vegyes egész program. Lineáris, konvex kvadratikus problémái és ugyanazok a másodrendű megszorítások lehetnek.
Az egész számú programok sokkal összetettebbek, mint a lineáris programok, de vannak fontos üzleti alkalmazásaik. SzoftverA CPLEX szoftver összetett matematikai módszereket használ az egész problémák megoldására. Módszerei közé tartozik a diszkrét változók lehetséges kombinációinak szisztematikus keresése lineáris vagy másodfokú szoftverrelaxáció segítségével, hogy kiszámítsa az optimális megoldás értékének határait.
Az LP-t és más optimalizálási problémamegoldó módszereket is használnak a kényszerek kiszámításához.
Standard Microsoft Excel Solver
Ez a technológia a fő Simplex módszer alapvető megvalósítását használja az LP problémák megoldására. 200 változóra korlátozódik. A "Premium Solver" egy továbbfejlesztett elsődleges szimplex módszert használ a változók kétoldalas korlátaival. A Premium Solver platform az LP/Quadratic Simplex Solver kibővített változatát használja, hogy megoldjon egy optimalizálási problémát akár 2000 döntési változóval.
A Premium Solver platform nagyléptékű LP-je az egyszerű és dupla szimplex módszer legkorszerűbb megvalósítását alkalmazza, amely az LP-modell ritkaságát használja, hogy időt és memóriát takarítson meg, fejlett frissítési stratégiákat és refaktoráló mátrixok, többszörös és részleges árazás és rotáció, valamint a degeneráció leküzdésére. Ez a motor három változatban érhető el (akár 8 000, 32 000 vagy korlátlan változó és korlát kezelésére képes).
MOSEK Solver tartalmaz elsődleges és kettős szimplexet, egy olyan módszert, amely a ritkaságot is kihasználja, és fejlett stratégiákat használ a mátrix frissítéséhez és "újrafaktorizálásához". Korlátlan méretű problémákat old meg, voltLineáris programozási problémákon tesztelve millió döntési változóval.
Lépésről lépésre példa az EXCEL-ben
Az optimalizálási probléma modelljének Excelben történő meghatározásához hajtsa végre a következő lépéseket:
- Rendszerezze a probléma adatait egy táblázatban logikus formában.
- Válasszon ki egy cellát az egyes változók tárolására.
- Hozzon létre a cellában egy képletet az optimalizálási probléma cél matematikai modelljének kiszámításához.
- Hozzon létre képleteket az egyes megszorítások bal oldalának kiszámításához.
- Használjon párbeszédpaneleket az Excelben, hogy tájékoztassa a Solvert a döntési változókról, célokról, megszorításokról és ezeknek a paramétereknek a kívánt határairól.
- Futtassa a "Solver"-t az optimális megoldás megtalálásához.
- Hozzon létre egy Excel-lapot.
- Rendszerezze a feladat adatait Excelben, ahol a célfüggvény és a kényszer képlete kiszámításra kerül.
A fenti táblázatban a B4, C4, D4 és E4 cellák le vannak foglalva az X 1, X 2, X 3 és X 4 döntési változók megjelenítésére. Döntési példák:
- A termékmix modelljét (450 USD, 1150 USD, 800 USD és 400 USD nyereség termékenként) a B5, C5, D5 és E5 cellákba írták be. Ez lehetővé teszi a cél kiszámítását a következőképpen: F5=B5B4 + C5C4 + D5D4 + E5E4 vagy F5:=SUMPRODUCT (B5: E5, B4: E4).
- A B8 mezőbe írja be az egyes terméktípusok gyártásához szükséges erőforrások mennyiségét.
- F8 képlet:=ÖSSZEG(B8:E8, $B$4:$E$4).
- Másolja eztképlet az F9-ben. A $B$4:$E$4 dollárjelek azt jelzik, hogy ez a cellatartomány állandó marad.
- A G8-ban adja meg az egyes típusokhoz rendelkezésre álló erőforrások mennyiségét, a jobb oldali korlátozások értékének megfelelően. Ezzel a következőképpen fejezheti ki őket: F11<=G8: G11.
- Ez négy határértéknek felel meg F8<=G8, F9 <=G9, F10 <=G10 és F11=0
A módszer gyakorlati alkalmazási területei
A lineáris optimalizálásnak számos gyakorlati alkalmazása van, mint például egy optimalizálási probléma:
Egy vállalat több terméket is készíthet ismert hozzájárulási árréssel. Az egyes cikkekből egy egység előállítása ismert mennyiségű korlátozott erőforrást igényel. A feladat egy gyártási program létrehozása, amely meghatározza, hogy az egyes termékekből mennyit kell előállítani, hogy a vállalat profitja maximalizálódjon anélkül, hogy az erőforrás-korlátokat megsértené.
A keverési problémák megoldást jelentenek az összetevők végtermékbe való keverésével kapcsolatos optimalizálási problémákra. Példa erre a George Danzig által 1947-ben tanulmányozott táplálkozási probléma. Számos nyersanyagot adnak meg, például zab-, sertés- és napraforgóolajat, valamint tápanyagtartalmukat, például fehérjét, zsírt, A-vitamint és kilogrammonkénti árat. A kihívás az, hogy egy vagy több végterméket nyersanyagokból a lehető legalacsonyabb költséggel keverjünk össze, miközben tiszteletben tartják a tápértékük minimális és maximális határait.
A lineáris optimalizálási probléma klasszikus alkalmazása az útválasztás igény szerinti meghatározásaforgalom a távközlési vagy közlekedési hálózatokban. Ugyanakkor az áramlásokat úgy kell átirányítani a hálózaton, hogy minden forgalmi követelmény teljesüljön a sávszélességi feltételek megsértése nélkül.
A matematikai elméletben a lineáris optimalizálás felhasználható az optimális stratégiák kiszámítására nulla összegű, két fős játékokban. Ebben az esetben minden résztvevőre kiszámítják a valószínűségi eloszlást, amely a stratégiái véletlenszerű keveredésének együtthatója.
A világon egyetlen sikeres üzleti folyamat sem lehetséges optimalizálás nélkül. Számos optimalizálási algoritmus áll rendelkezésre. Egyes módszerek csak bizonyos típusú problémákra alkalmasak. Fontos, hogy felismerjük sajátosságaikat és válasszuk ki a megfelelő megoldási módot.
