Lineaarisen optimoinnin simplex -menetelmä selitettiin yksinkertaisesti

instagram viewer

Lineaarinen optimointi koskee niukkojen resurssien optimaalista kohdentamista eri käyttötarkoituksiin. Niukat resurssit voivat olla esimerkiksi koneiden kapasiteettia tai tavaroiden tilaa. Optimi määritetään matemaattisesti, usein simplex -menetelmän avulla.

Lineaaristen ohjelmien mallintaminen

Lineaarisia ohjelmia mallinnettaessa erilaisia ​​parametreja, kuten B. Työkappaleiden käsittelyajat tai konekapasiteetit voidaan määrittää. Sitten määritellään tavoitefunktio, joka on maksimoitava tietyin rajoituksin. Tavoitefunktio on usein voittofunktio, koska nettotuloksen maksimointi on yrityksille keskeinen tavoite. Rajoitukset kuvataan resurssien niukkuudesta (esim. B. Kapasiteetti, aika, tila). Voit sitten ratkaista ongelman simplex -menetelmällä.

  • Voit oppia lineaaristen mallien luomisen erityisen helposti, jos teet itsellesi yksinkertaisen esimerkin: Oletetaan, että sinulla on kolme konetta M1, M2 ja M3 johon kaksi tuotetta P.1 ja P2 pitäisi tuottaa. Koneilla on eri kapasiteetti, ja tietyn tuotteen käsittely vie aikaa koneilla eri ajanjaksoilla ja lopputuotteilla on erilaiset voitot pois.
  • Etsimme nyt tuotto -ohjelmaa, jolla on suurin voitto, eli tuotanto -ohjelmaa, jossa saavutetaan suurin voitto.

Esimerkki numeerisista arvoista ja johdanto simplex -menetelmään

Seuraavassa vaiheessa tarvitset konkreettisia numeerisia arvoja ongelmasi mallintamiseen. Oletetaan, että muokkausta varten P.1 M1 2 tuntia, M2 3 tuntia ja M3 4 tuntia. P: lle2 kaatua M: lle1 4 tuntia, M2 5 tuntia ja M3 3 tuntia. Koneen kapasiteetti M: lle1 500 tuntia, M.2 300 tuntia ja M3 600 tuntia. Valmiiden lopputuotteiden voitot P1 ovat 3 euroa / kpl, lopputuotteet P2 4 euroa / kpl.

  1. On parasta luoda taulukko, jossa on kolme riviä ja kolme saraketta ja jossa on enemmän tilaa rivien ja sarakkeiden otsikoille. Sarakkeet pitäisi jättää. Esimerkiksi P: n käsittelyaika on "Sarake 1 ja rivi 1" -kentässä1 M1, kenttään "Sarake 2 ja rivi 3" P: n käsittelyaika2 M3. Sarake 3 näyttää kolmen koneen konekapasiteetin.
    2. Lineaaristen yhtälöjärjestelmien Gaussin algoritmi selitetty pähkinänkuoressa

    Löydät lineaarisia yhtälöjärjestelmiä ensimmäistä kertaa lukiossa ...

  2. Nyt tarvitset kaksi muuttujaa x1, x2 määritellä P: n tuotantomäärät1 ja P2 vastaavat.
  3. Joten saat rajoitukset 2x1+ 4x2 ≤ 500 (kone 1), 3x1+ 5x2 ≤ 300 (kone 2) ja 4x1+ 3x2 ≤ 600 (kone 3). Kussakin tapauksessa on epätasa -arvoa, koska kapasiteetin ei tarvitse olla kokonaan käytetty.
  4. Maksimoitava tavoitefunktio (voitto) on G (x1, x2) = 3x1+ 4x2 -> max.
  5. Lisäksi x: n negatiiviset ehdot koskevat tuotantomäärää1, x2 ≥ 0. Kaikki yhtälöt ovat lineaarisia yhtälöitä. Jos katsot niitä yhdessä, saat lineaarisen optimointitehtävän.

Lineaarinen optimointi ja simplex -menetelmän soveltaminen

Idea lineaarisen ohjelman ratkaisemiseksi on, että eriarvoisuudet ottamalla käyttöön "löysiä muuttujia" Yhtälöt ja muutettu optimointitehtävä ratkaistaan ​​nimellä LGS. Simplex -menetelmä on siis hyvin samanlainen kuin Gaussin algoritmi LGS: n ratkaisemiseksi.

  1. Esimerkki: Lentokone on jaettu kolmella tavaralla G1, G2, G3 kuormitettava mahdollisimman korkealla rahdin kokonaisarvolla. Näiden tilantarve on 1, 0,2 tai 6 dm3, paino 1, 0, 4 ja 8 kg ja arvo 10, 3 tai 50 euroa. Kuinka lentokone on ihanteellisesti ladattu, kun tavaratila on 2000 dm?3 ja se voi kuljettaa enintään 3000 kg rahtia?
  2. Määrität x: n1, x2, x3 tavaroiden määrinä G1, G2, G3.
  3. Voit nyt asettaa rajoitukset löysillä muuttujilla seuraavasti: x1+ 0,4x2+ 8x3+ x4 = 3000 ja x1+ 0,2x2+ 6x3+ x5 = 2000. Tavoitefunktio (rahdin kokonaisarvo) on G (x1, x2, x3) = 10x1+ 3x2+ 50x3 -> max. Voit muuttaa tätä tuomalla kaikki muuttujat yhdelle sivulle (G-10x1-3x2-50x3 = 0).
  4. Asenna sitten Simplex -paneeli. Siinä on 3 riviä ja 7 saraketta. Vasemmalla puolella kirjoitetaan sarakkeisiin x1, x2, x3, x4, x5 ja G otsikoina. Oikealla, b on ainoa sarake. Tässä luetellaan optimaaliset tavaramäärät ja suurin mahdollinen rahdin arvo. Kolmas rivi on kohdelinja. (Ohjaus: kolme riviä, joissa on edellä mainitut otsikot, sisältävät numerot: Rivi 1: 1, 0,4, 8, 1, 0, 0, 3000, Rivi 2: 1, 0,2 6, 0, 1, 0, 2000 ja rivi 3: -10, -3, -50, 0, 0, 1, 0).
  5. Jatka nyt kuten käytettäessä Gaussin menetelmää LGS: n ratkaisemiseksi. Ensimmäisessä vaiheessa vaihdat riviä 1 tai vastaavaa. Rivi 2 lähetetään ympäri ja lisätään toiselle riville niin, että vain 1 näkyy rivillä 1 + sarake 1 ja 0 rivillä 2 + sarake 1. Tämä muuttaa myös kohderivin arvot automaattisesti.
  6. Tässä tapauksessa voit esimerkiksi kertoa rivin 2 -1: llä ja lisätä sen riville 1 ja kertoa rivin 2 10: llä ja lisää riville 3 (ohjaus: rivi 1: 0, 0,2, 2, 1, -1, 0, 1000, rivi 2: pysyy samana, rivi 3: 0, -1, 10, 0, 10, 1, 20.000).
  7. Ota toisessa vaiheessa sarake 2 ja luo 0 muuntamalla "Rivi 2 + sarake 2" ja sitten 1 rivillä 1 ja sarakkeessa 2. Jälleen on huomattava, miten kohdelinja muuttuu.
  8. Muunnosvaiheet olisivat esimerkiksi kertomalla rivi 1 -1: llä ja lisäämällä rivi 2 ja rivi 1-5 ja lisää rivi 3 (Tarkista: kun olet suorittanut molemmat vaiheet, tulos on: rivi 1: 0, 1, 10, 5, -5, 0, 5000, rivi 2: 1, 0, 4, -1, 2, 0, 1000 ja rivi 3: 0, 0, 20, 5, 5, 1, 25.000).
  9. Voit nyt lukea ratkaisut paneelin oikealta puolelta. Tämän seurauksena rahdin kokonaisarvo on 25 000 euroa, 5000 yksikköä tavaraa 1, 1000 yksikköä tavaraa 2 eikä kuljeteta yksikköä tavaraa 3.

Huomaa, että simplex -taulukon ratkaisu johtaa optimaaliseen ratkaisuun vain, jos vasemmanpuoleisessa kohderivissä näkyy vain positiivisia tuloksia viimeisen uudelleenmuodostusvaiheen jälkeen Laskenta seistä. Olet sisäistänyt järjestelmän 2-3 muun esimerkin jälkeen ja pystyt ratkaisemaan tällaiset tehtävät tulevaisuudessa leikkisällä tavalla.

click fraud protection