LINEAARINEN OHJELMOINTI: MITÄ VARTEN SE ON, MALLIT, RAJOITUKSET, SOVELLUKSET - MATEMATIIKKA - 2026

Lineaarinen ohjelmointi on matemaattinen menetelmä, jota on käytetty optimoida (suurentaa tai pienentää tapauksen mukaan) funktiona, jonka muuttujat on rajoitettu, niin kauan kuin toiminto ja rajoitteet ovat lineaarisesti riippuvia muuttujia.

Yleensä optimoitava toiminto mallii käytännön tilanteen, kuten sellaisen valmistajan voitto, jonka tuotantopanokset, työvoima tai koneet ovat rajalliset.

Kuva 1. Lineaarista ohjelmointia käytetään laajasti voittojen optimointiin. Lähde: Piqsels.

Yksi yksinkertaisimmista tapauksista on maksimoitava lineaarifunktio, joka riippuu vain kahdesta muuttujasta, joita kutsutaan päätösmuuttujiksi. Se voi olla muodossa:

Z = k ₁ x + k ₂ y

Kun k ₁ ja k _{2 ovat} vakioita. Tätä toimintoa kutsutaan objektiivifunktioksi. Tietenkin on tilanteita, jotka ansaitsevat enemmän kuin kaksi muuttujaa tutkittavaksi, koska ne ovat monimutkaisempia:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Ja rajoitukset mallitaan myös matemaattisesti yhtälö- tai epäyhtälöiden järjestelmällä, jotka ovat yhtä lineaarisia x: ssä ja y: ssä.

Tämän järjestelmän ratkaisukokonaisuutta kutsutaan toteuttamiskelpoisiksi ratkaisuiksi tai toteutettavissa olevina pisteinä. Ja toteutettavissa olevien pisteiden joukossa on ainakin yksi, joka optimoi objektiivisen toiminnan.

Lineaarisen ohjelmoinnin kehittivät itsenäisesti yhdysvaltalainen fyysikko ja matemaatikko George Dantzig (1914-2005) ja venäläinen matemaatikko ja taloustieteilijä Leonid Kantorovich (1912-1986) pian toisen maailmansodan jälkeen.

Yksinkertaisena menetelmäna tunnettu ongelmanratkaisumenetelmä on Dantzigin, joka työskenteli Yhdysvaltain ilmavoimissa, Berkeleyn yliopistossa ja Stanfordin yliopistossa.

Kuva 2. Matemaatikot George Dantzig (vas.) Ja Leonid Kantorovich (oikealla). Lähde: F. Zapata.

Lineaariset ohjelmointimallit

Käytännön tilanteeseen sopivan lineaarisen ohjelmointimallin luomiseksi tarvittavat elementit ovat:

-Objektiivinen toiminto

-Päätösmuuttujat

-Restrictions

Objektiivitoiminnossa määrität, mitä haluat saavuttaa. Oletetaan esimerkiksi, että haluat maksimoida tiettyjen tuotteiden valmistuksesta saatavat voitot. Sitten "voitto" -toiminto määritetään sen hinnan mukaan, jolla tuotteet myydään.

Matemaattisesti tämä funktio voidaan ilmaista lyhennettynä käyttämällä summausmerkintää:

Z = ∑k _i x _i

Tässä yhtälössä k _i ovat kertoimet ja x _i ovat päätöksen muuttujia.

Päätösmuuttujat ovat järjestelmän elementtejä, joita on hallittu, ja niiden arvot ovat positiivisia reaalilukuja. Ehdotetussa esimerkissä päätöksen muuttujat ovat kunkin valmistettavan tuotteen määrä maksimaalisen voiton saamiseksi.

Viimeinkin meillä on rajoituksia, jotka ovat lineaarisia yhtälöitä tai päätöksentekijöiden epätasa-arvoisia. Ne kuvaavat ongelmalle tunnetut rajoitukset, jotka voivat olla esimerkiksi valmistuksessa saatavien raaka-aineiden määrät.

Rajoitustyypit

Sinulla voi olla useita M rajoituksia, alkaen j = 1 - j = M. Matemaattisesti rajoituksia on kolme tyyppiä:

1. A _j = ∑ a _ij. x _i
2. B _j ≥ ∑ b _ij. x _i
3. C _j ≤ ö c _ij. x _i

Ensimmäinen rajoitus on lineaarinen yhtälötyyppi ja tarkoittaa sitä, että tunnettu arvo A _j on kunnioitettava.

Kaksi jäljellä olevaa rajoitusta ovat lineaarista epätasa-arvoa, ja se tarkoittaa, että tunnetut arvot B _j ja C _j voidaan kunnioittaa tai ylittää, kun ilmestyvä symboli on ≥ (suurempi tai yhtä suuri) tai kunnioitettava tai ylittymättä, jos symboli on ≤ (Pienempi kuin tai yhtä suuri kuin).

Malli-esimerkki

Soveltamisalat ovat hyvin erilaisia, liikkeenjohdosta ravitsemukseen, mutta menetelmän ymmärtämiseksi ehdotetaan jäljempänä yksinkertaista mallia käytännöllisestä tilanteesta kahdella muuttujalla.

Paikallinen konditoria tunnetaan kahdesta erikoisuudesta: mustan metsän kakku ja sacripantine kakku.

Valmistelussaan he tarvitsevat munia ja sokeria. Mustalle metsälle tarvitset 9 munaa ja 500 g sokeria, kun taas sakkantiinille tarvitset 8 munaa ja 800 g sokeria. Vastaavat myyntihinnat ovat 8 dollaria ja 10 dollaria.

Ongelmana on: kuinka monta kakkua jokaisesta tyypistä leipomon on tehtävä maksimoidakseen tuotonsa tietäen, että siinä on 10 kiloa sokeria ja 144 munaa?

Päätöksen muuttujat

Päätösmuuttujat ovat "x" ja "y", joilla on todelliset arvot:

-x: mustan metsäkakkujen lukumäärä

-y: sacripantine-tyyppiset kakut.

rajoitukset

Rajoituksia antaa se, että kakkujen lukumäärä on positiivinen ja raaka-aineiden määrät niiden valmistamiseksi ovat rajalliset.

Siksi matemaattisessa muodossa nämä rajoitukset ovat seuraavat:

1. x ≥ 0
2. ja ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8 y ≤ 10

Rajoitukset 1 ja 2 muodostavat aiemmin paljastuneen ei-negatiivisuuden tilan ja kaikki esiin nostetut epätasa-arvot ovat lineaarisia. Rajoituksissa 3 ja 4 on arvot, joita ei saa ylittää: 144 munaa ja 10 kg sokeria.

Tavoitetoiminto

Lopuksi, tavoitefunktio on voitto, joka saadaan valmistettaessa ”x” määrää mustan metsän kakkuja plus “y” määrä sacripantineja. Se rakennetaan kertomalla hinta valmistettujen kakkujen määrällä ja lisäämällä kullekin tyypille. Se on lineaarinen funktio, jota kutsutaan G (x, y):

G = 8x + 10 vuotta

Ratkaisumenetelmät

Eri ratkaisumenetelmät sisältävät graafisia menetelmiä, simplex-algoritmin ja sisäpisteen menetelmän muutaman mainitsemiseksi.

- Graafinen tai geometrinen menetelmä

Kun sinulla on kahden muuttujan ongelma, kuten edellisessä osiossa, rajoitukset määrittävät monikulmaisen alueen xy-tasolla, jota kutsutaan toteutettavissa olevaksi alueeksi tai elinkelpoisuusalueeksi.

Kuva 3. Mahdollinen alue, jolla optimointiongelmaan löydetään ratkaisu. Lähde: Wikimedia Commons.

Tämä alue rakennetaan käyttämällä rajoitusviivoja, jotka ovat rajoitusten epätasa-arvoista saatuja viivoja, jotka toimivat vain tasa-arvomerkillä.

Leipomon tapauksessa, joka haluaa optimoida voitot, rajoitukset ovat seuraavat:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8 y = 10

Kaikki näiden linjojen ympäröimät alueet ovat mahdollisia ratkaisuja, joten niitä on äärettömän paljon. Lukuun ottamatta tapauksia, joissa toteutettavissa oleva alue osoittautuu tyhjäksi, tällöin esitetyllä ongelmalla ei ole ratkaisua.

Onneksi leivonnaisongelman kannalta toteutettavissa oleva alue ei ole tyhjä, meillä on se alla.

Kuva 4. Leivonnaisongelman toteutettavissa oleva alue. Rivi, jolla on vahvisuus 0, ylittää alkuperäisen. Lähde: F. Zapata ja Geogebra.

Optimaalinen ratkaisu, jos sellainen on, löytyy kohdefunktion avulla. Esimerkiksi, kun yritetään löytää suurin voitto G, meillä on seuraava rivi, jota kutsutaan iso-voitto-riviksi:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Tällä viivalla saadaan kaikki parit (x, y), jotka antavat tietyn vahvistuksen G, joten olemassa on joukko rivejä G: n arvon mukaan, mutta kaikilla on sama kaltevuus -k ₁ / k ₂, joten ne ovat yhdensuuntaiset viivat.

Optimaalinen ratkaisu

Nyt voidaan osoittaa, että lineaarisen ongelman optimaalinen ratkaisu on aina toteutettavan alueen ääripiste tai kärki. Niin:

Jos lähinnä lähinnä olevalla linjalla on koko segmentti yhteistä toteutettavissa olevan alueen kanssa, sanotaan, että ratkaisuja on äärettömiä. Tämä tapahtuu, jos isovoittoviivan kaltevuus on yhtä suuri kuin minkä tahansa muun alueen rajoittavan viivan kaltevuus.

Leivonnaissamme ehdokashuiput ovat A, B ja C.

- Dantzigin simplex-menetelmä

Graafista tai geometristä menetelmää voidaan soveltaa kahteen muuttujaan. Se on kuitenkin monimutkaisempaa, kun muuttujia on kolme, ja mahdotonta käyttää suurempien muuttujien lukumäärään.

Kun käsitellään useamman kuin kahden muuttujan ongelmia, käytetään simplex-menetelmää, joka koostuu sarjasta algoritmeja objektiivitoimintojen optimoimiseksi. Matriiseja ja yksinkertaista laskutoimitusta käytetään usein laskelmien suorittamiseen.

Yksinkertainen menetelmä alkaa valitsemalla toteutettavissa oleva ratkaisu ja tarkistamalla onko se optimaalinen. Jos on, olemme jo ratkaisseet ongelman, mutta jos ei, jatkamme kohti ratkaisua, joka on lähempänä optimointia. Jos ratkaisu on olemassa, algoritmi löytää sen muutamasta yrityksestä.

Sovellukset

Lineaarista ja epälineaarista ohjelmointia käytetään monilla aloilla parhaiden päätösten tekemiseen kustannusten vähentämiseksi ja voittojen lisäämiseksi, jotka eivät aina ole rahallisia, koska ne voidaan mitata ajoissa, esimerkiksi jos haluat minimoida tarvittavan ajan. suorittaa sarjan toimintoja.

Tässä on joitain kenttiä:

-Markkinoinnissa sitä käytetään etsimään paras mediayhdistelmä (sosiaaliset verkostot, televisio, lehdistö ja muut) tietyn tuotteen mainostamiseksi.

- Sijoita asianmukaiset tehtävät yrityksen tai tehtaan henkilöstölle tai aikataulut heille.

- Valittaessa ravinteimpia ruokia ja alhaisin kustannuksin karja- ja siipikarjateollisuudessa.

Ratkaistuja harjoituksia

- Harjoitus 1

Ratkaise graafisesti edellisissä kappaleissa esiin tuotu lineaarinen ohjelmointimalli.

Ratkaisu

On tarpeen piirtää arvojoukko, jonka määrittelee ongelmassa määritelty rajoitusjärjestelmä:

1. x ≥ 0
2. ja ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8 y ≤ 10

Epätasa-arvojen 1 ja 2 antama alue vastaa Cartesian-tason ensimmäistä neljännestä. Eriarvoisuuksien 3 ja 4 osalta aloitamme etsimällä rajoitusviivat:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Mahdollinen alue on nelikulma, jonka kärjet ovat pisteitä A, B, C ja D.

Pienin voitto on 0, joten rivi 8x + 10y = 0 on alaraja ja isovoittoisten rivien kaltevuus -8 / 10 = - 0,8.

Tämä arvo eroaa muiden rajoituslinjojen rinteistä ja koska toteutettavissa oleva alue on rajoitettu, ainutlaatuinen ratkaisu on olemassa.

Kuva 5. Graafinen ratkaisu harjoituksesta 1, joka esittää toteutettavissa olevan alueen ja ratkaisupisteen C mainitun alueen yhdellä kärjellä. Lähde: F. Zapata.

Tämä ratkaisu vastaa kaltevuusviivaa -0,8, joka kulkee minkä tahansa pisteen A, B tai C läpi, jonka koordinaatit ovat:

A (11; 5,625)

B (0; 12,5)

C (16,0)

Optimaalinen ratkaisu

Laskemme G: n arvon jokaiselle näistä pisteistä:

- (11; 5,625): G = 8 x 11 + 10 x 5,625 = 144,25

- (0, 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Suurin voitto on 11 mustan metsäkakun ja 5 625 sacripantine-kakun valmistuksessa. Tämä ratkaisu on yhtä kuin ohjelmiston kautta löydetty.

- Harjoitus 2

Varmista edellisen harjoituksen tulos käyttämällä Solver-toimintoa, joka on saatavana useimmissa taulukoissa, kuten Excel tai LibreOffice Calc, jotka sisältävät Simplex-algoritmin optimoimiseksi lineaarisessa ohjelmoinnissa.

Ratkaisu

Kuva 6. Yksityiskohta ratkaisusta harjoituksesta 1 Libre Office Calc -laskentataulukon kautta. Lähde: F. Zapata.

Kuva 7. Yksityiskohta ratkaisusta harjoituksesta 1 Libre Office Calc -laskentataulukon kautta. Lähde: F. Zapata.

Viitteet

1. Loistava. Lineaarinen ohjelmointi. Palautettu osoitteesta: brilliant.org.
2. Eppen, G. 2000. Hallintotieteen toimintatutkimus. 5th. Painos. Prentice Hall.
3. Haeussler, E. 1992. Johtamisen ja talouden matematiikka. 2nd. Painos. Grupo Editorial Iberoamericana.
4. Hiru.eus. Lineaarinen ohjelmointi. Palautettu: hiru.eus.
5. Wikipedia. Lineaarinen ohjelmointi. Takaisin: es. wikipedia.org.