Jos olet insinööri tai insinööriopiskelija, saatat tietää, mitä optimointi tarkoittaa.
Parhaan mahdollisen tuloksen saavuttamiseksi on tärkeää löytää paras tapa tehdä asiat.
Lineaarisessa ohjelmoinnissa voit käyttää perusratkaisua löytääksesi parhaan ratkaisun.
Mutta mikä on perusratkaisu, ja miksi insinöörien on niin tärkeää tietää niistä? Tässä artikkelissa puhun siitä, mitä perusratkaisut ovat, miksi ne ovat tärkeitä suunnittelussa ja miten niitä voidaan käyttää parhaan tuloksen saavuttamiseksi eri tilanteissa.
Ota siis solki kiinni ja valmistaudu sukeltamaan perusratkaisujen maailmaan, jossa selvitän mysteerit ja näytän kuinka tehokas tämä tekniikka voi olla.
Lineaarisen ohjelmoinnin perusratkaisut
Muodollinen määritelmä:
Ratkaisu lineaariseen ohjelmamalliin, joka koostuu m yhtälöstä n muuttujassa, saadaan ratkaisemalla m muuttujalle jäljellä olevien (nm) muuttujien suhteen ja asettamalla (nm) muuttujat nollaksi.
Lineaarisen ohjelmoinnin perusratkaisu on tapa ratkaista lineaarisen ohjelmoinnin ongelma, joka täyttää tietyt tekniset vaatimukset.
Erityisesti vektori x on perusratkaisu monitahoiselle, jos vektorit {ai : xi = 0} ovat lineaarisesti riippumattomia.
Tämä tarkoittaa, että A:n sarakkeet, joiden muuttujat xi eivät ole nollia, ovat lineaarisesti riippumattomia.
Perusratkaisua, jossa on ei-negatiivisia komponentteja, kutsutaan perusratkaisuksi (BFS) (BFS).
BFS täyttää kaikki säännöt, jotka määrittelevät monitahoisen.
Jokainen BFS on geometrisesta näkökulmasta toteutettavien ratkaisujen monitahoisen kulma.
Perusratkaisun löytämiseksi sinun on asetettava nm muuttujaa, jotka eivät ole perusmuuttujia, nollaan ja ratkaistava m muuttujaa, jotka ovat perusmuuttujia.
Eri perusteet voivat johtaa samaan perusratkaisuun, mikä tarkoittaa, että sama ongelma voi ratkaista useammalla kuin yhdellä tavalla.
Simplex-menetelmä on iteratiivinen prosessi, joka siirtyy yhdestä BFS:stä seuraavaan BFS:ään, kunnes se löytää parhaan BFS:n.
Kun käytetään simpleksimenetelmää BFS:n löytämiseen, voimme kertoa, onko ratkaisu paras, katsomalla, antavatko muut lähellä olevat BFS:t paremman arvon tavoitefunktiolle.
Jos tällaista BFS:ää ei ole, nykyinen BFS on paras.
Lineaarinen ohjelmointimalli
Lineaarinen ohjelmointimalli sisältää kolme pääkomponenttia: päätösmuuttujat, tavoitefunktio ja rajoitukset.
Sekä tavoitefunktion että rajoitusten tulee olla lineaarisia funktioita ja päätösmuuttujien on oltava jatkuvia.
Tavoitefunktiota käytetään joko lisäämään tai vähentämään lukua, joka edustaa voittoa, kustannuksia, valmistettujen tuotteiden määrää jne.
Rajoitukset ovat rajoituksia tai rajoituksia tietyn resurssin kokonaismäärälle, joka tarvitaan päätösmuuttujien onnistumistason määrittävien tehtävien suorittamiseen.
Lisäksi jotkin lineaariset ohjelmat edellyttävät, että kaikki päätösmuuttujat ovat ei-negatiivisia.
Lineaarisissa ohjelmointimalleissa voit käyttää myös kokonaisluku- ja binäärimuuttujia.
Binäärimuuttujien arvo voi olla vain 0 tai 1, joten niillä voi olla vain arvo 0 tai 1.
Simplex-menetelmä
Yksi käytetyimmistä tavoista ratkaista lineaarisen ohjelmoinnin ongelmia on Simplex-menetelmä.
Perusratkaisut ovat tärkeitä simpleksimenetelmässä, koska ne vastaavat toteutettavissa olevan alueen kulmapisteitä ja simpleksimenetelmä liikkuu kulmasta toiseen, kunnes optimaalinen ratkaisu löytyy.
Simpleksimenetelmä on nopea tapa löytää paras vastaus lineaariseen ohjelmointitehtävään perusratkaisujen ominaisuuksien avulla.
Jotta voisimme käyttää simpleksimenetelmää parhaan BFS:n löytämiseen, meidän on löydettävä kanta B rajoitematriisille A ja ratkaistava järjestelmä Ax = b, jossa kaikki muut muuttujat paitsi kanta on asetettu nollaan.
Tuloksena saadut perusmuuttujien arvot muodostavat BFS:n.
Jos on olemassa optimaalinen ratkaisu, on olemassa optimaalinen BFS.
Simplex-menetelmä siirtyy yhdestä BFS:stä viereiseen BFS:ään, kunnes se saavuttaa optimaalisen BFS:n käyttämällä pivot-menettelyjä.
Perusratkaisujen ja toteutettavissa olevien ratkaisujen vertailu
Ero perusratkaisun ja käyttökelpoisen ratkaisun välillä on se, että perusratkaisun ei tarvitse täyttää mitään ehtoja.
Erityisesti siinä on oltava vektoreita, jotka ovat lineaarisesti riippumattomia ja joilla on nollasta poikkeavat arvot xi:lle, ja x:n on oltava pienempi kuin 0.
Toisaalta toteuttamiskelpoinen ratkaisu on mikä tahansa kohta, joka sopii ongelman rajoihin.
Mutta kaikki mahdolliset ratkaisut eivät ole perusratkaisuja.
Perusratkaisut (BFS) ovat vain sellaisia, jotka vastaavat toteutettavissa olevien ratkaisujen monitahoisen kulmia.
Takaisin perusteisiin: tekniikan perusratkaisujen tehon vapauttaminen
Vieläkö vaikea ymmärtää? Muutanpa hieman näkökulmaa:
Oletko kyllästynyt käyttämään monimutkaisia menetelmiä ja algoritmeja vaikeiden ongelmien ratkaisemiseen? Toivoisitko, että olisi olemassa yksinkertaisempi, suoraviivaisempi tapa käsitellä lineaarisen ohjelmamallin ongelmia?
No, älä huoli, sillä vastaus on tässä: ratkaise m muuttujaa jäljellä olevien (nm) muuttujien suhteen ja aseta (nm) muuttujat nollaan.
Kuka tarvitsee algoritmeja, jotka kuulostavat hienolta, kun voit palata perusasioihin? Joten laita laskimesi pois ja aloita oppimaan yksinkertaisista ratkaisuista.
Okei, se oli vain vitsi, joka tehtiin näyttämään TV-mainokselta.
Palataan nyt selitykseen.
Perusratkaisu Lineaarinen ohjelmointi
Vinkki: Ota tekstityspainike käyttöön, jos tarvitset sitä. Valitse asetuspainikkeesta "automaattinen käännös", jos puhuttu kieli ei ole sinulle tuttu. Sinun on ehkä napsautettava ensin videon kieltä, ennen kuin suosikkikielesi on saatavilla käännettäväksi.
Käytä koteloita
| Käytetty: | Kuvaus: |
|---|---|
| Resurssien kohdentaminen: | Perusratkaisua voidaan käyttää resurssien allokointiongelmissa, joissa tavoitteena on jakaa rajalliset resurssit kilpailevien tarpeiden kesken. Yrityksen voi esimerkiksi joutua jakamaan budjettinsa eri osastojen tai projektien kesken. Perusratkaisuja käyttämällä he voivat selvittää parhaan tavan käyttää resurssejaan saadakseen eniten rahaa tai kuluttamaan mahdollisimman vähän. |
| Tuotannon suunnittelu: | Tuotannon suunnittelussa perusratkaisun avulla voidaan keksiä paras tuoteyhdistelmä, joka tehdään, jotta saadaan mahdollisimman paljon rahaa. Yritykset voivat löytää perusratkaisun avulla parhaan tuotantoyhdistelmän, joka tuo eniten rahaa ja maksaa vähiten. |
| Ajoitus: | Perusratkaisun avulla voidaan selvittää, miten tehtävät tai työt ajoitetaan niin, että ne voidaan tehdä tehokkaimmalla tavalla. Yrityksen voi esimerkiksi joutua suunnittelemaan työntekijöidensä työaikaa varmistaakseen, että heillä on tarpeeksi työntekijöitä, kun yritys on kiireinen. Perusratkaisun avulla he voivat selvittää parhaan tavan ajoittaa asiat niin, että seisokkeja on mahdollisimman vähän ja töitä saadaan tehtyä mahdollisimman paljon. |
| Toimitusketjun hallinta: | Toimitusketjun hallinnassa tavoitteena on varmistaa, että tavarat ja palvelut siirtyvät mahdollisimman sujuvasti toimittajalta asiakkaalle. Yrityksen voi esimerkiksi joutua selvittämään parhaat reitit tavaroiden kuljettamiseen, jotta kustannukset pysyvät mahdollisimman pieninä ja tavarat toimitetaan ajallaan. Perusratkaisuja käyttämällä he voivat löytää parhaan toimitusketjun hallintasuunnitelman, joka pitää kustannukset alhaisina ja pitää asiakkaat tyytyväisinä. |
| Portfolion optimointi: | Salkun optimoinnissa, jossa tavoitteena on löytää paras sijoitusyhdistelmä tuottaakseen eniten rahaa ja ottaa pienin riski, voidaan käyttää perusratkaisuja. Esimerkiksi sijoituspalveluyrityksen on ehkä löydettävä paras yhdistelmä osakkeita, joukkovelkakirjoja ja muita arvopapereita auttaakseen asiakkaitaan saavuttamaan sijoitustavoitteensa. Yksinkertaista ratkaisua käyttämällä he voivat löytää parhaan tavan sekoittaa salkkujaan niin, että he saavat parhaan tuoton samalla kun he ottavat pienimmän riskin. |
Johtopäätös
Yhteenvetona voidaan todeta, että ajatus perusratkaisusta on erittäin tärkeä tekniikan alalla ja sitä voidaan käyttää monella eri tavalla.
Kun tiedämme, mikä perusratkaisu on ja mitä se tekee lineaarisessa ohjelmoinnissa, voimme parantaa ratkaisuja, leikata kustannuksia ja tehdä niistä tehokkaampia.
Mutta on tärkeää muistaa, että perusratkaisu ei ole yksikokoinen ratkaisu, vaikka se onkin tehokas työkalu.
Parhaan tuloksen saavuttamiseksi jokainen ongelma on tarkasteltava huolellisesti ja harkittava.
Insinööreinä meidän on jatkuvasti tutkittava, kuinka perusratkaisut ja muut optimointitekniikat voivat auttaa meitä edistymään ja keksimään uusia ideoita.
Tunnistakaamme siis yksinkertaisten ratkaisujen voima ja jatkamme mahdollisuuksien rajojen ylittämistä käyttämällä uusia tekniikoita ja strategioita.
Linkkejä ja referenssejä
Kirjat:
- Lineaarinen ohjelmointi Vasek Chvatal
- Lineaarisen ohjelmoinnin mallintaminen ja ratkaiseminen R:llä, Jose M. Sallan
Jaa…
