Optimointi auttaa sinua löytämään parhaan tuloksen, joka tuottaa voittoa, alentaa kustannuksia tai asettaa parametrin, joka aiheuttaa liiketoimintaprosessien epäonnistumisia.
Tätä prosessia kutsutaan myös matemaattiseksi ohjelmoimiseksi. Se ratkaisee optimointiongelman päällikön asettaman tavoitteen saavuttamiseksi tarvittavien rajallisten resurssien jakautumisen määrittämisongelman. Kaikista mahdollisista vaihtoehdoista on toivottavaa löytää se, joka maksimoi (tai vähentää) ohjausparametria, esimerkiksi voittoa tai kustannuksia. Optimointimalleja kutsutaan myös preskriptiivisiksi tai normatiivisiksi, koska niillä pyritään löytämään yritykselle toteuttamiskelpoinen strategia.
Kehityshistoria
Lineaarinen ohjelmointi (LP) toimii optimointiongelmien luokan kanssa, jossa kaikki rajoitukset ovat lineaarisia.
Esittelyssä lyhyt historia LP:n kehityksestä:
- Vuonna 1762 Lagrange ratkaisi yksinkertaisia optimointiongelmia tasa-arvorajoituksilla.
- Vuonna 1820 Gauss päättilineaarinen yhtälöjärjestelmä eliminaatiolla.
- Vuonna 1866 Wilhelm Jordan kehitti menetelmää pienimmän neliösumman virheiden löytämiseksi sopivaksi kriteeriksi. Tätä kutsutaan nyt Gauss-Jordan-menetelmäksi.
- Digitaalinen tietokone ilmestyi vuonna 1945.
- Danzig keksi simpleksimenetelmät vuonna 1947.
- Vuonna 1968 Fiacco ja McCormick esittelivät Inside Point -menetelmän.
- Vuonna 1984 Karmarkar käytti sisäistä menetelmää lineaaristen ohjelmien ratkaisemiseen ja lisäsi innovatiivisen analyysinsä.
LP on osoittautunut erittäin tehokkaaksi työkaluksi sekä todellisten ongelmien mallintamiseen että laaj alti käytettynä matemaattisena teoriana. Monet mielenkiintoiset optimointiongelmat ovat kuitenkin epälineaarisia.
Mitä tehdä tässä tapauksessa? Tällaisten ongelmien tutkimiseen kuuluu monipuolinen sekoitus lineaarista algebraa, monimuuttujalaskentaa, numeerista analyysiä ja laskennallisia menetelmiä. Tiedemiehet kehittävät laskennallisia algoritmeja, mukaan lukien sisäpistemenetelmät lineaariseen ohjelmointiin, geometriaan, konveksien joukkojen ja funktioiden analysointiin sekä erikoisrakenteisten ongelmien, kuten asteen ohjelmoinnin, tutkimiseen.
Epälineaarinen optimointi tarjoaa perusymmärrystä matemaattisesta analyysistä, ja sitä käytetään laajasti eri aloilla, kuten suunnittelussa, regressioanalyysissä, resurssienhallinnassa, geofysikaalisessa etsinnässä ja taloustieteessä.
Optimointiongelmien luokittelu
Tärkeä askelOptimointiprosessi on mallien luokittelu, koska niiden ratkaisualgoritmit on mukautettu tiettyyn tyyppiin.
1. Ongelmia diskreetissä ja jatkuvassa optimoinnissa. Jotkut mallit ovat järkeviä vain, jos muuttujat ottavat arvot erillisestä kokonaislukujen osajoukosta. Toiset sisältävät tietoja, jotka voivat saada minkä tahansa todellisen arvon. Ne on yleensä helpompi ratkaista. Algoritmien parannukset yhdistettynä tietotekniikan kehitykseen ovat lisänneet dramaattisesti lineaarisen ohjelmoinnin optimointiongelman kokoa ja monimutkaisuutta.
2. Rajoittamaton ja rajoitettu optimointi. Toinen tärkeä ero on tehtävät, joissa muuttujia ei rajoiteta. Se voi vaihdella laajasti yksinkertaisista estimaateista yhtäläisyys- ja epätasa-arvojärjestelmiin, jotka mallintavat monimutkaisia suhteita datan välillä. Tällaiset optimointiongelmat voidaan luokitella edelleen funktioiden luonteen mukaan (lineaarinen ja epälineaarinen, kupera ja sileä, differentioituva ja ei-differentioituva).
3. Toteutettavuustehtävät. Heidän tavoitteenaan on löytää muuttuvia arvoja, jotka täyttävät mallin rajoitukset ilman erityistä optimointitavoitetta.
4. Täydentävyystehtävät. Niitä käytetään laaj alti tekniikassa ja taloudessa. Tavoitteena on löytää ratkaisu, joka täyttää täydentävyysehdot. Käytännössä tehtävät, joilla on useita tavoitteita, muotoillaan usein uudelleen yksittäisiksi tavoitteiksi.
5. Deterministinen vs. stokastinen optimointi. Deterministinen optimointi olettaa, että tiedot fortehtävät ovat täysin tarkkoja. Monissa ajankohtaisissa asioissa niitä ei kuitenkaan voida tietää useista syistä.
Ensimmäinen liittyy yksinkertaiseen mittausvirheeseen. Toinen syy on perustavanlaatuisempi. Se johtuu siitä, että osa tiedoista edustaa tietoa tulevaisuudesta, esimerkiksi tuotteen kysyntää tai hintaa tulevalle ajanjaksolle. Kun optimoidaan stokastisissa optimointiolosuhteissa, epävarmuus sisältyy malliin.
Pääkomponentit
Tavoitefunktio on se, joka tulee minimoida tai maksimoida. Useimmilla optimointiongelmien tyypeillä on yksi tavoitefunktio. Jos ei, ne voidaan usein muotoilla uudelleen toimiviksi.
Kaksi poikkeusta tähän sääntöön:
1. Kohdehakutehtävä. Useimmissa yrityssovelluksissa johtaja haluaa saavuttaa tietyn tavoitteen ja täyttää mallin rajoitukset. Käyttäjä ei halua erityisesti optimoida jotain, joten ei ole järkevää määritellä tavoitefunktiota. Tätä tyyppiä kutsutaan yleisesti tyytyväisyysongelmaksi.
2. Paljon objektiivisia piirteitä. Usein käyttäjä haluaa optimoida useita eri tavoitteita kerralla. Ne eivät yleensä ole yhteensopivia. Muuttujat, jotka optimoivat yhden tavoitteen, eivät välttämättä ole parhaita muille.
Osatyypit:
- Ohjattu syöte on joukko päätösmuuttujia, jotka vaikuttavat tavoitefunktion arvoon. Tuotantotehtävässä muuttujat voivat sisältää erilaisten käytettävissä olevien resurssien tai tarvittavan työvoiman jakautumisenjokainen toiminto.
- Rajoitteet ovat päätösmuuttujien ja parametrien välisiä suhteita. Tuotantoongelmassa ei ole järkevää käyttää paljon aikaa mihinkään toimintaan, joten rajoita kaikkia "väliaikaisia" muuttujia.
- Mahdollisia ja optimaalisia ratkaisuja. Muuttujien päätöksen arvoa, jossa kaikki rajoitukset täyttyvät, kutsutaan tyydyttäväksi. Useimmat algoritmit löytävät sen ensin ja yrittävät sitten parantaa sitä. Lopuksi he muuttavat muuttujia siirtyäkseen mahdollisesta ratkaisusta toiseen. Tätä prosessia toistetaan, kunnes tavoitefunktio saavuttaa maksiminsa tai miniminsä. Tätä tulosta kutsutaan optimaaliseksi ratkaisuksi.
Seuraaville matemaattisille ohjelmille kehitetyt optimointitehtäväalgoritmit ovat laaj alti käytössä:
- Kupera.
- Erotettavissa.
- Neliöllinen.
- Geometrinen.
Google Linear Solvers
Lineaarinen optimointi tai ohjelmointi on ongelman optimaalisen ratkaisemisen laskentaprosessille annettu nimi. Se on mallinnettu joukkona lineaarisia suhteita, joita syntyy monilla tieteen ja tekniikan aloilla.
Google tarjoaa kolme tapaa ratkaista lineaariset optimointiongelmat:
- Glop avoimen lähdekoodin kirjasto.
- Lineaarisen optimoinnin lisäosa Google Sheetsille.
- Lineaarinen optimointipalvelu Google Apps Scriptissa.
Glop on sisäänrakennettu Googleenlineaarinen ratkaisija. Se on saatavana avoimena lähdekoodina. Pääset Glopiin OR-Tools lineaarisen ratkaisijan kääreen kautta, joka on Glopin kääre.
Google Sheetsin lineaarisen optimointimoduulin avulla voit esittää optimointiongelman lineaarisesti syöttämällä tiedot laskentataulukkoon.
Kvadraattinen ohjelmointi
Premium Solver -alusta käyttää Simplex-menetelmän laajennettua LP/Quadratic-versiota LP- ja QP-ongelmien käsittelyrajoilla jopa 2000 päätösmuuttujalla.
SQP-ratkaisija laajamittaisille ongelmille käyttää nykyaikaista aktiivijoukkomenetelmän toteutusta, jossa on harvalukuisuus ratkaistakseen toisen asteen ohjelmoinnin (QP) ongelmia. XPRESS Solver -moottori käyttää "Interior Point"- tai Newton Barrier -menetelmän luonnollista laajennusta QP-ongelmien ratkaisemiseen.
MOSEK Solver käyttää upotettuja "Inside Point"- ja automaattisia kaksoismenetelmiä. Tämä on erityisen tehokasta löyhästi kytketyissä QP-ongelmissa. Se voi myös ratkaista Scale Quadratic Constraint (QCP) ja Second Order Cone Programming (SOCP) -ongelmat.
Monioperaatiolaskelmat
Niitä käytetään melko menestyksekkäästi Microsoft Office -ominaisuuksien käytössä, esimerkiksi optimointiongelmien ratkaisemisessa Excelissä.
Yllä olevassa taulukossa symbolit ovat:
- K1 - K6 - asiakkaat, joiden on toimitettava tavaroita.
- S1 - S6 ovat mahdollisia tuotantopaikkoja, jotka voitaisiin rakentaa tätä varten. Voidaan luoda1, 2, 3, 4, 5 tai kaikki 6 paikkaa.
Jokaisella sarakkeessa I (Korjaa) luetellulla laitoksella on kiinteät kustannukset.
Jos sijainti ei muuta mitään, sitä ei lasketa. Silloin ei ole kiinteitä kuluja.
Tunnista mahdolliset sijainnit saadaksesi halvimmat kustannukset.
Näissä olosuhteissa sijainti joko on määritetty tai ei. Nämä kaksi tilaa ovat: "TRUE - FALSE" tai "1 - 0". Kuudessa paikassa on kuusi tilaa, esimerkiksi 000001 on asetettu vain kuudenneksi, 111111 on asetettu kaikkiin.
Binäärilukujärjestelmässä on täsmälleen 63 eri vaihtoehtoa 000001 (1) - 111111 (63).
L2-L64:n pitäisi nyt lukea {=MULTIPLE OPERATION (K1)}, nämä ovat kaikkien vaihtoehtoisten ratkaisujen tuloksia. Tällöin minimiarvo on=Min (L) ja vastaava vaihtoehto on INDEKSI (K).
CPLEX-kokonaislukuohjelmointi
Joskus lineaarinen suhde ei riitä pääsemään liike-elämän ongelman ytimeen. Tämä pätee erityisesti silloin, kun päätökset sisältävät erillisiä valintoja, kuten avataanko varasto tietyssä paikassa vai ei. Näissä tilanteissa on käytettävä kokonaislukuohjelmointia.
Jos ongelmaan liittyy sekä diskreettejä että jatkuvia valintoja, kyseessä on sekoitettu kokonaislukuohjelma. Sillä voi olla lineaarisia, konveksia kvadraattisia ongelmia ja samat toisen asteen rajoitukset.
Kokonaislukuohjelmat ovat paljon monimutkaisempia kuin lineaariset ohjelmat, mutta niissä on tärkeitä liiketoimintasovelluksia. OhjelmistoCPLEX-ohjelmisto käyttää monimutkaisia matemaattisia menetelmiä kokonaislukuongelmien ratkaisemiseen. Hänen menetelmänsä käsittävät erillisten muuttujien mahdollisten yhdistelmien systemaattisen etsimisen käyttämällä lineaarisia tai neliöllisiä ohjelmistorelaksaatioita optimaalisen ratkaisun arvon rajojen laskemiseksi.
He käyttävät myös LP:tä ja muita optimoinnin ongelmanratkaisumenetelmiä rajoitusten laskemiseen.
Standard Microsoft Excel Solver
Tämä tekniikka käyttää Simplex-päämenetelmän perustoteutusta LP-ongelmien ratkaisemiseen. Se on rajoitettu 200 muuttujaan. "Premium Solver" käyttää parannettua ensisijaista simpleksimenetelmää, jossa muuttujien kaksipuoliset rajoitukset. Premium Solver -alusta käyttää LP/Quadratic Simplex Solverin laajennettua versiota optimointiongelman ratkaisemiseen jopa 2000 päätösmuuttujalla.
Suuressa mittakaavassa LP Premium Solver -alustalle käyttää yksinkertaisen ja kaksoissimplex-menetelmän uusinta toteutusta, joka käyttää LP-mallin harvaa säästääkseen aikaa ja muistia, kehittyneitä päivitysstrategioita ja refaktorointimatriiseja, moninkertaista ja osittaista hinnoittelua ja rotaatioita sekä rappeuman voittamiseen. Tästä moottorista on saatavana kolme versiota (pystyy käsittelemään jopa 8 000, 32 000 tai rajattomasti muuttujia ja rajoja).
MOSEK Solver sisältää ensisijaisen ja kaksoissimplexin, menetelmän, joka myös hyödyntää harvalukuisuutta ja käyttää edistyneitä strategioita matriisin päivittämiseen ja "uudelleenfaktorointiin". Se ratkaisee rajoittamattoman kokoisia ongelmia, olitestattu lineaarisissa ohjelmointiongelmissa miljoonien päätösmuuttujien kanssa.
Vaiheittainen esimerkki EXCELissä
Määritä optimointiongelmamalli Excelissä suorittamalla seuraavat vaiheet:
- Järjestä ongelman tiedot laskentataulukkoon loogiseen muotoon.
- Valitse solu, johon jokainen muuttuja tallennetaan.
- Luo soluun kaava optimointitehtävän matemaattisen kohdemallin laskemiseksi.
- Luo kaavoja kunkin rajoitteen vasemman puolen laskemiseksi.
- Käytä Excelin valintaikkunoita kertoaksesi Ratkaisijalle näiden parametrien päätösmuuttujista, tavoitteista, rajoituksista ja halutuista rajoista.
- Suorita "Solver" löytääksesi optimaalisen ratkaisun.
- Luo Excel-taulukko.
- Järjestä tehtävän tiedot Excelissä, jossa tavoitefunktion ja rajoitteen kaava lasketaan.
Yllä olevassa taulukossa solut B4, C4, D4 ja E4 on varattu edustamaan päätösmuuttujia X 1, X 2, X 3 ja X 4. Päätösesimerkit:
- Tuotevalikoiman malli (450 dollaria, 1150 dollaria, 800 dollaria ja 400 dollaria tuotetta kohti) syötettiin soluihin B5, C5, D5 ja E5. Tämä mahdollistaa tavoitteen laskemisen muodossa F5=B5B4 + C5C4 + D5D4 + E5E4 tai F5:=SUMMAT (B5: E5, B4: E4).
- Syötä kohtaan B8 kunkin tuotetyypin valmistukseen tarvittavien resurssien määrä.
- Formula for F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Kopioi tämäkaava F9:ssä. Dollarin merkit $B$4:$E$4:ssä osoittavat, että tämä solualue pysyy vakiona.
- Syötä G8:aan kunkin tyypin käytettävissä oleva resurssien määrä, joka vastaa oikeanpuoleisten rajoitusten arvoja. Tämän avulla voit ilmaista ne seuraavasti: F11<=G8: G11.
- Tämä vastaa neljää rajaa F8<=G8, F9 <=G9, F10 <=G10 ja F11=0
Menetelmän käytännön soveltamisalat
Lineaarisella optimoinnilla on monia käytännön sovelluksia esimerkkinä optimointiongelmasta:
Yritys voi valmistaa useita tuotteita tunnetulla marginaalilla. Kunkin tuotteen yksikön valmistaminen vaatii tunnetun määrän rajallisia resursseja. Tehtävänä on luoda tuotantoohjelma, jolla määritellään, kuinka paljon kutakin tuotetta tulisi tuottaa, jotta yrityksen voitto maksimoi resurssirajoituksia rikkomatta.
Sekoitusongelmat ovat ratkaisu optimointiongelmiin, jotka liittyvät ainesosien yhdistämiseen lopputuotteeksi. Esimerkki tästä on George Danzigin vuonna 1947 tutkima ruokavalioongelma. Tarjolla on useita raaka-aineita, kuten kaura-, sianliha- ja auringonkukkaöljy, sekä niiden ravintosisältö, kuten proteiini, rasva, A-vitamiini ja niiden kilohinta. Haasteena on sekoittaa yksi tai useampi lopputuote raaka-aineista mahdollisimman alhaisin kustannuksin noudattaen samalla niiden ravintoarvon vähimmäis- ja enimmäisrajoja.
Lineaarisen optimointitehtävän klassinen sovellus on määrittää reititys tarpeiden mukaantietoliikenne- tai liikenneverkoissa. Samanaikaisesti virrat tulee reitittää verkon läpi siten, että kaikki liikennevaatimukset täyttyvät kaistanleveysehtoja rikkomatta.
Matematiikan teoriassa lineaarista optimointia voidaan käyttää optimaalisten strategioiden laskemiseen kahden hengen nollasummapeleissä. Tässä tapauksessa lasketaan kunkin osallistujan todennäköisyysjakauma, joka on hänen strategioidensa satunnaisen sekoittumisen kerroin.
Mikään menestyvä liiketoimintaprosessi maailmassa ei ole mahdollista ilman optimointia. Saatavilla on monia optimointialgoritmeja. Jotkut menetelmät sopivat vain tietyntyyppisiin ongelmiin. On tärkeää osata tunnistaa niiden ominaisuudet ja valita sopiva ratkaisutapa.
