Tiedät, mitä tarkoittaa järjestelmän optimointi parhaan mahdollisen tuloksen saamiseksi, jos olet insinööriopiskelija tai insinööri.
Ratkaisun optimointi on avain menestykseen kaikessa siltojen rakentamisesta ohjelmistojen valmistukseen.
Ajatus toteuttamiskelpoisesta perusratkaisusta tulee esiin tässä vaiheessa.
Se on lineaarisen ohjelmoinnin perusidea, jonka avulla voit selvittää, mikä mahdollisista ratkaisuista on paras.
Mutta miksi sillä on niin väliä? Tässä artikkelissa puhun toteuttamiskelpoisista perusratkaisuista ja siitä, kuinka niitä voidaan käyttää ratkaisemaan teknisiä ongelmia todellisessa maailmassa.
Puhun siitä, miten ne löydetään, mistä ne on tehty ja miksi ne ovat tärkeitä.
Joten, olitpa kokenut insinööri tai vasta aloittava opiskelija, tule kanssamme, kun sukellan toteuttamiskelpoisten perusratkaisujen maailmaan ja näytän sinulle, kuinka käytät lineaarisen ohjelmoinnin tehoa.
Käyttökelpoisen perusratkaisun ymmärtäminen
Muodollinen määritelmä:
Perusratkaisu lineaariseen ohjelmamalliin, jossa kaikki muuttujat ovat ei-negatiivisia.
Perusratkaisu (BFS) on lineaarisen ohjelmoinnin keskeinen idea, joka auttaa löytämään parhaat ratkaisut.
BFS on ratkaisu, jossa on mahdollisimman pieni määrä nollasta poikkeavia muuttujia.
Se on toteuttamiskelpoisten ratkaisujen monitahoisen kulman kulma.
Toisin sanoen BFS on perusratkaisu, joka täyttää ei-negatiiviset rajoitukset ja on toteutettavissa olevalla alueella tai ongelma-alueella.
Optimaalisen perusratkaisun löytäminen
Löytääksemme parhaan BFS:n meidän on tehtävä seuraava:
- Kirjoita ohjelma standardimuodossa lineaarista sekvenssiä varten.
- Tee epäyhtälöjärjestelmästä lisätty matriisi.
- Selvitä, mitkä muuttujat ovat perusmuuttujia ja mitkä eivät.
- Selvitä, mitä perusmuuttujat ovat muiden muuttujien suhteen.
- Laita nämä lausekkeet tavoitefunktioon saadaksesi funktion vain muuttujista, jotka eivät ole perusmuuttujia.
- Etsi ei-perusmuuttuja, jota voidaan kasvattaa rikkomatta rajoituksia ja joka parantaa tavoitefunktiota.
Tämä muuttuja on nyt perusmuuttuja, ja yksi muista perusmuuttujista ei ole enää perusmuuttuja.
Jos optimaalinen ratkaisu on olemassa, sen on oltava sen alueen yhdessä päässä tai kärjessä, jossa ratkaisut ovat mahdollisia.
Joten jos LP:llä on optimaalinen ratkaisu, sillä on optimaalinen ratkaisu toteutettavissa olevan joukon ääripisteessä.
Myös optimaalinen BFS on aina olemassa, jos optimaalinen ratkaisu on olemassa.
Simplex-menetelmän käyttäminen optimaalisen BFS:n löytämiseen
Simplex-menetelmä on algoritmi lineaarisen ohjelmoinnin ongelmien ratkaisemiseen.
Se siirtyy yhdestä BFS:stä "viereiseen" BFS:ään käyttämällä pivot-menettelyä.
Pivot-menettelyssä ei-perusmuuttuja valitaan perusmuuttujaksi, ja sitten nykyistä BFS:ää käytetään uusien perusmuuttujien ratkaisemiseen.
Kun ei-perusmuuttujaa ei voida muuttaa tavoitefunktion parantamiseksi, algoritmi on valmis.
Miksi toteuttamiskelpoiset perusratkaisut ovat ratkaisevia monimutkaisten suunnitteluongelmien ratkaisemisessa?
Vieläkö vaikea ymmärtää? Muutanpa hieman näkökulmaa:
Kuka tarvitsee yksinkertaisia, toimivia vastauksia? Laita kaikki yhteen ja toivo parasta.
Loppujen lopuksi, kuka tarvitsee optimointia, kun kaaos on niin paljon hauskempaa? Tervetuloa ei-negatiivisten muuttujien maailmaan, jossa kaikki on vain ehdotusta ja epäonnistuminen on lähes varmaa.
Vai onko se?
Pohditaan, miksi näennäisen perustavanlaatuinen peruskonsepti toteutettavissa olevista perusratkaisuista on kaikkea muuta kuin perus ja miksi ne voivat olla avain monimutkaisimpienkin suunnitteluongelmien ratkaisemiseen.
Okei, se oli vain vitsi, joka tehtiin näyttämään TV-mainokselta.
Palataan nyt selitykseen.
Perusteellisen ratkaisun löytäminen
Perusratkaisu (BFS) on ratkaisu lineaariseen optimointiongelmaan, joka täyttää kaikki rajoitukset ja jossa on vähiten nollasta poikkeavia muuttujia.
Jokainen BFS on geometrisesta näkökulmasta toteutettavien ratkaisujen monitahoisen kulma.
Jos on paras ratkaisu, on oltava myös paras ensimmäinen askel.
Tässä artikkelissa puhumme siitä, kuinka löytää ensimmäinen toteuttamiskelpoinen perusratkaisu, kuinka löytää kaikki mahdolliset perusratkaisut ja kuinka löytää toteuttamiskelpoinen perusratkaisu ilman löysää muuttujaa.
Alkuperäisen perusratkaisun löytäminen
Voimme käyttää erilaisia menetelmiä, riippuen siitä, miten ongelma on asetettu, löytääksemme alkuperäisen perusratkaisun, joka toimii lineaarisen optimointitehtävän kanssa.
Yksi tapa on lisätä löysät muuttujat epäyhtälöiden rajoituksiin ja asettaa kaikki muut muuttujat nollaan.
Slack-muuttujista tulee perusmuuttujia, ja loput ovat ei-perusmuuttujia.
Kaksivaiheinen Simplex-menetelmä on toinen tapa ratkaista ongelma.
Tämä menetelmä sisältää ylimääräisen lineaarisen ohjelmointiongelman ratkaisemisen, jotta löydetään alkuperäinen perusratkaisu, joka on toteutettavissa.
Kun alkuperäinen perusratkaisu on löydetty, voidaan Simplex-menetelmällä siirtyä yhdestä toteuttamiskelpoisesta perusratkaisusta seuraavaan ja sitten parhaaseen ratkaisuun.
Kaikkien perusratkaisujen löytäminen
Lineaariselle ohjelmalle voi toimia useampi kuin yksi perusratkaisu.
Voimme muuttaa järjestelmää lisäämällä slack-muuttujia ja sitten löytää uuden järjestelmän avulla kaikki mahdolliset perusratkaisut lineaariseen ohjelmaan.
Sitten näitä perusratkaisuja käytetään alkuperäisen ongelman toteuttamiskelpoisten perusratkaisujen löytämiseen.
Toteutettavan perusratkaisun löytäminen ilman slack-muuttujia
Meidän on käytettävä slack-muuttujia päästäksemme eroon vähemmän kuin rajoituksista, jotta voimme löytää perusratkaisun, joka toimii ilman löysämuuttujia.
Slack muuttuja on vain ero rajoitteen oikean puolen ja vasemman puolen välillä.
Esimerkiksi ensimmäiselle rajoitukselle määritetään löysä muuttuja x4 = 14 - 2x1 - x2 - x3. Tämän uuden muuttujan kannalta ensimmäinen rajoite vastaa yksinkertaisesti x4 ≥ 0, joka on x4:n positiivisuusrajoitus.
Kun lisäämme nämä löysät muuttujat, saamme lineaarisen ohjelman, joka on sama kuin alkuperäinen, paitsi että kaikki rajoitukset ovat joko yhtälöitä tai rajoitteita, jotka sanovat jonkin olevan positiivista.
Perusmuuttujien joukkoa, joilla on perusratkaisussa muita arvoja kuin nolla, kutsutaan kantaksi.
Muuttujat, joiden arvo perusratkaisussa on nolla, eivät ole perusmuuttujia.
Parhaan ratkaisun löytämiseksi meidän on löydettävä vektori x, joka täyttää kaikki säännöt ja saa suurimman tai pienimmän arvon tavoitteelle.
Mutta parhaan ratkaisun löytäminen vaatii enemmän vaiheita kuin vain sellaisen ratkaisun löytäminen, joka toimii ja jossa ei ole löysää muuttujaa.
Aina ei ole mahdollista löytää perusratkaisua ilman löysää muuttujaa, etenkään ongelmiin, joissa on vähemmän rajoituksia.
Löytääksesi toteuttamiskelpoisen perusratkaisun, sinun on käytettävä simpleksimenetelmää tai jotakin muuta lineaarista ohjelmointialgoritmia etsiäksesi ratkaisu, joka täyttää kaikki rajoitukset ja jossa on vähiten nollasta poikkeavia muuttujia.
Toteutettavan perusratkaisun ominaisuudet ja merkitys
Toteutettavan perusratkaisun ominaisuudet
Käyttökelpoisessa perusratkaisussa on enintään m muuttujaa, jotka eivät ole nollia, ja vähintään nm muuttujaa, jotka ovat nolla, missä n on päätösmuuttujien lukumäärä ja m on rajoitusten lukumäärä.
BFS on mahdollisten ratkaisujen monitahoisen kulma, ja jokaisella BFS:llä on n aktiivista rajoitusta, jotka ovat lineaarisesti riippumattomia.
Jos on paras ratkaisu, on oltava myös paras ensimmäinen askel.
Tärkeintä toteutettavissa olevissa perusratkaisuissa on, että ne ovat lineaarisen ohjelmointitehtävän konveksiratkaisujen joukon päät.
Parhaan vastauksen löytämiseksi simpleksialgoritmi käy läpi sarjan BFS:itä.
Simplex-algoritmi etsii kaikki mahdolliset perusratkaisut järjestelmällisesti löytääkseen parhaan.
Toteutettavan perusratkaisun merkitys
Mahdollisen perusratkaisun löytäminen on tärkeää, koska se auttaa löytämään parhaan vastauksen lineaarisen ohjelmoinnin ongelmiin.
Se antaa myös monimutkaisille algoritmeille aloituspaikan ja sitä voidaan käyttää sen selvittämiseen, onko lineaarinen ohjelma mahdollinen vai ei.
Löytääksesi kaikki mahdolliset perusratkaisut lineaariselle ohjelmalle, voit muuttaa järjestelmää lisäämällä löysät muuttujat ja sitten etsiä muutetun järjestelmän avulla kaikki mahdolliset perusratkaisut.
Sitten näitä perusratkaisuja käytetään alkuperäisen ongelman toteuttamiskelpoisten perusratkaisujen löytämiseen.
Video: toteuttamiskelpoisia perusratkaisuja
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: | BFS:n avulla voidaan jakaa rajalliset resurssit useiden hankkeiden kesken niin, että eniten saadaan aikaan vähimmällä. Tätä menetelmää voidaan käyttää monilla eri aloilla, kuten kuljetuksissa, maataloudessa ja rahoituksessa. |
| Verkon optimointi: | BFS:n avulla voidaan parantaa viestintä-, kuljetus- ja logistiikkaverkostojen toimintaa. BFS voi auttaa löytämään parhaat reitit tavaroille ja palveluille, säästää kuljetuksiin kuluvaa aikaa ja rahaa sekä nopeuttaa ja tarkentaa toimituksia. |
| Tuotannon suunnittelu: | BFS:n avulla voidaan suunnitella tuotantoa siten, että resurssit, kuten työvoima, raaka-aineet ja laitteet, käytetään parhaalla mahdollisella tavalla, jotta niistä saadaan mahdollisimman paljon irti. BFS voi auttaa alentamaan tuotantokustannuksia, vähentämään jätettä ja parantamaan tehokkuutta. |
| Taloussuunnittelu: | Taloussuunnittelussa BFS:ää voidaan käyttää sijoitussalkkujen optimointiin, riskin pienentämiseen ja suurimman osan rahan saamiseen takaisin. BFS voi auttaa löytämään parhaan tavan jakaa varat, alentaa transaktiokustannuksia ja ansaita enemmän rahaa. |
| Toimitusketjun hallinta: | BFS:n avulla voidaan parantaa tavara- ja palveluvirtaa toimittajilta asiakkaille osana toimitusketjun hallintaa. BFS voi auttaa selvittämään parhaan varastossa pidettävän varastomäärän, lyhentää toimitusaikoja ja parantaa asiakaspalvelua. |
Johtopäätös
Kun tämä toteuttamiskelpoisten perusratkaisujen tarkastelu päättyy, on selvää, että ne ovat tärkeä työkalu jokaiselle insinöörille tai insinööriopiskelijalle.
Perusratkaisut tarjoavat puitteet parhaan mahdollisen tuloksen saavuttamiselle parhaan tavan rakentaa monimutkaisen järjestelmän keksimisestä aina käytettävissä olevien resurssien hyödyntämiseen.
Mutta enemmän kuin vain hyödyllisiä, ne osoittavat, kuinka tyylikästä ja kaunista matematiikka voi olla.
On hämmästyttävää, että voit keittää monimutkaiset ongelmat yksinkertaisiksi yhtälöiksi ja käyttää niitä sitten ongelmien ratkaisemiseen todellisessa maailmassa.
Se on hyvä muistutus siitä, että suunnittelussa on kyse ongelmien ratkaisemisesta ja että matematiikan voimaa käyttämällä voimme löytää vastauksia, joita aikoinaan pidettiin mahdottomina.
Joten kun opit lisää suunnittelusta, pidä mielessäsi, mitä olet oppinut yksinkertaisista toimivista ratkaisuista, ja käytä niitä tekemään maailmasta parempi ja tehokkaampi paikka.
Linkkejä ja referenssejä
Kirjat:
- Lineaarinen ohjelmointi: Perusteet ja laajennukset
- Lineaarinen ohjelmointi: teoria ja sovellukset
Jaa…
