Lineaarinen ohjelmointi syntyi erillisenä soveltavan matematiikan haarana 40- ja 50-luvuilla. XX vuosisadalla kiitos Neuvostoliiton tiedemiehen, Nobel-palkinnon voittajan L.V. Kantorovich. Vuonna 1939 hän julkaisi teoksen "Tuotannon organisoinnin ja suunnittelun matemaattiset menetelmät", jossa hän ratkaisi taloudellisia ongelmia paras lataus koneet, materiaalien leikkaaminen alhaisin kustannuksin, rahdin jakaminen useille kuljetusmuodoille ja muut, kertojien ratkaisumenetelmän ehdottaminen 8.

L.V. Kantorovich oli ensimmäinen, joka muotoili laajalti käytetyt taloudelliset ja matemaattiset käsitteet, kuten optimaalinen suunnitelma, optimaalinen resurssien allokointi, objektiivisesti määrätyt arvioinnit, jotka osoittavat lukuisia taloustieteen alueita, joilla niitä voidaan soveltaa.

Käsite lineaarinen ohjelmointi sen esitteli amerikkalainen matemaatikko D. Dantzig, joka vuonna 1949 ehdotti algoritmia lineaarisen ohjelmoinnin ongelman ratkaisemiseksi, jota kutsutaan "simplex-menetelmäksi".

Matemaattinen ohjelmointi, joka sisältää lineaarisen ohjelmoinnin, on tällä hetkellä yksi operaatiotutkimuksen osa-alueista. Ratkaistavien ongelmien tyypistä riippuen se erottaa sellaiset alueet kuten lineaarinen, epälineaarinen, diskreetti, dynaaminen ohjelmointi jne. Termi "ohjelmointi" otettiin käyttöön, koska tuntemattomat muuttujat, jotka ovat ratkaisemassa ongelmaa, määrittävät yleensä jonkin taloudellisen kokonaisuuden ohjelma tai toimintasuunnitelma.

Klassisessa matemaattisessa analyysissä tutkitaan ehdollisen ääripään määrittämisen ongelman yleistä muotoilua. Teollisen tuotannon, liikenteen, maatalouden ja pankkisektorin kehityksen yhteydessä perinteiset matemaattisen analyysin tulokset eivät kuitenkaan riittäneet. Käytännön tarpeet ja tietotekniikan kehitys ovat johtaneet tarpeeseen löytää optimaaliset ratkaisut monimutkaisia ​​talousjärjestelmiä analysoitaessa.

Tärkein työkalu tällaisten ongelmien ratkaisemiseen on matemaattinen mallintaminen. Tässä tapauksessa ensin rakennetaan yksinkertainen malli, jonka jälkeen tehdään sen tutkimus, jonka avulla voidaan ymmärtää, mitkä kohteen integroivista ominaisuuksista eivät ole kaapattuja muodollisessa kaaviossa, minkä jälkeen mallia monimutkaisemalla sen suurempi riittävyys. todellisuuteen on varmistettu. Monissa tapauksissa ensimmäinen approksimaatio todellisuuteen on malli, jossa kaikki kohteen tilaa kuvaavien muuttujien väliset riippuvuudet ovat lineaarisia. Käytäntö osoittaa, että riittävä määrä taloudellisia prosesseja kuvataan melko täydellisesti lineaarisilla malleilla. Näin ollen lineaarinen ohjelmointi laitteistona, jonka avulla voidaan löytää ehdollinen ääriarvo lineaaristen yhtälöiden ja epäyhtälöiden määrittämästä joukosta tärkeä rooli kun näitä prosesseja analysoidaan.

Lineaarinen ohjelmointi on saanut laajaa kehitystä johtuen siitä, että on todettu, että useita suunnittelu- ja ohjausongelmia voidaan muotoilla lineaaristen ohjelmointiongelmien muotoon, joiden ratkaisemiseen on olemassa tehokkaita menetelmiä. Asiantuntijoiden mukaan noin 80–85 % kaikista käytännössä ratkaistavista optimointiongelmista liittyy lineaariseen ohjelmointiongelmiin.

Luotu matemaattinen laitteisto yhdessä työvoimavaltaisia ​​laskelmia suorittavien tietokoneohjelmien kanssa mahdollistaa lineaaristen ohjelmointimallien laajan käytön taloustieteissä ja käytännössä.

Määritelmä 1 9 . Lineaarinen ohjelmointi (LP) on matemaattisen ohjelmoinnin ala, joka on matematiikan ala, joka tutkii menetelmiä löytää äärimmäisiä (suurimpia ja pienimpiä) arvoja lineaariselle funktiolle äärellisestä määrästä muuttujia, joiden tuntemattomat ovat riippuvaisia lineaariset rajoitukset.

Tätä lineaarista funktiota kutsutaan kohdefunktioksi, ja rajoituksia, jotka edustavat taloudellisen ongelman ehtoja ja vaatimuksia ilmaisevien muuttujien välisiä kvantitatiivisia suhteita ja jotka on kirjoitettu matemaattisesti yhtälöiden tai epäyhtälöiden muodossa, kutsutaan rajoitusjärjestelmäksi.

Laaja kirjo taloudellisten prosessien suunnitteluun liittyvistä asioista rajoittuu lineaarisiin ohjelmointiongelmiin, joissa tehtävänä on löytää paras (optimaalinen) ratkaisu.

Yleinen lineaarinen ohjelmointiongelma (GLP) on löytää lineaarifunktion ääriarvo (maksimi tai minimi), jota kutsutaan tavoitteeksi 10:

alkaen n muuttujia x 1 , x 2 , …, X n asetetuilla toiminnallisilla rajoituksilla:

(3.2)

ja suorat rajoitukset (muuttujien ei-negatiivisuuden vaatimus)

, (3.3)

Jossa a ij , b i , c j– annetut vakioarvot.

Rajoitusjärjestelmässä (3.2) merkit ”pienempi tai yhtä suuri”, ”yhtä kuin” ja ”suurempi tai yhtä suuri kuin” voivat esiintyä samanaikaisesti.

PAP lisää lyhyt huomautus on muotoa:

,

rajoituksin:

;

.

Vector". X = (x 1 , x 2 , …, X n), joiden komponentit täyttävät ongelman toiminnalliset ja suorat rajoitukset, kutsutaan suunnitelma(tai hyväksyttävä ratkaisu) ZLP.

Kaikki mahdolliset ratkaisut muodostuvat määritelmän alue lineaariset ohjelmointiongelmat tai toteuttamiskelpoisten ratkaisujen alue (ODR). Toteutettava ratkaisu, joka tuottaa tavoitefunktion maksimin tai minimin f(`X), kutsutaan ongelman optimaaliseksi suunnitelmaksi ja on merkitty f(`X * ), missä ` X * =(x 1 * , x 2 * , …, X n * ).

Toinen PPP-tallennusmuoto:

,

Jossa f(`X * ) on suurin (minimi) arvo f(KANSSA, X), otti kaikki sarjaan kuuluvat ratkaisut mahdollisia ratkaisuja X .

Määritelmä 2 11 . Tavoitefunktion ja sen rajoitteiden matemaattista ilmaisua kutsutaan taloudellisen ongelman matemaattiseksi malliksi.

Kokoamaan matemaattinen malli tarpeellista:

1) tunnistaa muuttujat;

2) luoda tavoitefunktio, joka perustuu ongelman päämäärään;

3) kirjoittaa muistiin rajoitusjärjestelmän ottaen huomioon ongelmanselvityksen indikaattorit ja niiden määrälliset mallit.

15. Analyyttiset menetelmät. Lineaariset ohjelmointimenetelmät.

15.1. Analyyttiset menetelmät

Koko evoluutionsa ajan ihminen pyrki tiettyjä toimia suorittaessaan käyttäytymään siten, että jonkin toiminnan seurauksena saavutettu tulos osoittautui tietyssä mielessä parhaaksi. Siirtyessään pisteestä toiseen hän yritti löytää lyhimmän mahdollisen polun. Asuntoa rakentaessaan hän etsi geometriaa, joka pienimmällä polttoaineenkulutuksella antaisi hyväksyttävän mukavat olosuhteet olemassaolo. Laivoja rakentaessaan hän yritti antaa niille muodon, jossa vesi vastustaisi vähiten. Samankaltaisten esimerkkien luetteloa voidaan helposti jatkaa.

Parhaita ratkaisuja ongelmiin tietyssä mielessä kutsutaan yleensä optimaalinen. Tällä hetkellä mitään ongelmaa ei voida ratkaista ilman optimointiperiaatteiden käyttöä. monimutkainen ongelma. Optimointiongelmia asetettaessa ja ratkaistaessa herää kaksi kysymystä: mitä ja miten optimoidaan?

Vastaus ensimmäiseen kysymykseen saadaan ratkaistavan ongelman perusteellisen tutkimuksen tuloksena. Parametri, joka määrittää esiin tulleen ongelman ratkaisun täydellisyyden asteen, tunnistetaan. Tätä parametria kutsutaan yleensä kohdetoiminto tai laatukriteeri. Seuraavaksi määritetään joukko suureita, jotka määrittävät tavoitefunktion. Lopuksi muotoillaan kaikki rajoitukset, jotka on otettava huomioon ongelmaa ratkaistaessa. Tämän jälkeen muodostetaan matemaattinen malli, jossa määritetään tavoitefunktion analyyttinen riippuvuus kaikista argumenteista ja laaditaan analyyttisesti ongelmaan liittyvät rajoitteet. Seuraavaksi alamme etsiä vastausta toiseen kysymykseen.

Todetaan siis sovelletun ongelman formalisoinnin tuloksena, että tavoitefunktio on , missä joukko X on rajoitteiden yleistys, sitä kutsutaan sallittujen ratkaisujen joukoksi. Optimointitehtävän ydin on etsiä joukosta X - tällaisen ratkaisun toteuttamiskelpoisten ratkaisujen joukko
, jossa kohde toimii f saavuttaa minimi- tai maksimiarvonsa.

Olennainen osa optimointimenetelmiä on lineaarinen ohjelmointi.

15.2. Lineaarisen ohjelmoinnin peruskäsitteet

Ensimmäinen maininta (1938) matemaattisista menetelmistä tehokkaassa tuotannonhallinnassa kuuluu Neuvostoliiton matemaatikko L. V. Kantorovichille. Vuotta myöhemmin, vuonna 1939, L. V. Kantorovich julkaisi työn "Tuotannon organisoinnin ja suunnittelun matemaattiset menetelmät" ja sovelsi saatuja tuloksia käytännössä. Amerikkalaiset matemaatikot J. Danzig ja T. Koopmans ottivat käyttöön termin "lineaarinen ohjelmointi" 40-luvun lopulla. J. Dantzig kehitti simplex-menetelmän matemaattisen laitteen lineaarisen ohjelmoinnin ongelmien ratkaisemiseen (1951). Simplex-menetelmää käytetään useiden lineaarisen ohjelmoinnin ongelmien ratkaisemiseen, ja se on edelleen yksi tärkeimmistä menetelmistä.

Lineaarinen ohjelmointi on matematiikan haara, joka keskittyy ääripisteen (maksimi- tai minimiarvo) löytämiseen ongelmissa, jotka kuvataan lineaarisilla yhtälöillä. Lisäksi lineaariset yhtälöt kuvaavat sekä itse tavoitefunktiota että rajoitusten ehtojen syöteparametreja (muuttujia). syöttöparametreja. Lineaaristen ohjelmointiongelmien välttämätön edellytys on pakollinen resurssirajoitusten olemassaolo (raaka-aineet, materiaalit, rahoitus, valmistettujen tuotteiden kysyntä jne.). Muille tärkeä ehto ongelman ratkaiseminen on algoritmin pysäytyskriteerin valinta, eli tavoitefunktion on oltava jossain mielessä optimaalinen. Optimaalisuus tavoitefunktio on ilmaistava määrällisesti. Jos kohdefunktio esitetään yhdellä tai kahdella yhtälöllä, niin käytännössä tällaiset ongelmat voidaan ratkaista melko helposti. Algoritmin pysäytyskriteerin (tai optimaalisuuskriteerin) on täytettävä seuraavat vaatimukset:

olla ainoa tietyssä tehtävässä;

mitataan määräyksiköissä;

riippuvat lineaarisesti syöttöparametreista.

Yllä olevan perusteella voimme muotoilla lineaarisen ohjelmoinnin ongelman yleinen näkemys:

etsi tavoitefunktion ääriarvo

tasa-arvorajoituksin:

(2.2)

eriarvoisuuden muodossa olevien rajoitusten alla:

(2.3)

ja syöttöparametrien ei-negatiivisuuden ehdot:

Lyhyesti sanottuna lineaarinen ohjelmointiongelma voidaan kirjoittaa seuraavasti:

(2.5)

sen huomioon ottaen

Jossa
- syöttömuuttujat;

Numerot ovat positiivisia, negatiivisia ja yhtä suuria kuin nolla.

Matriisimuodossa tämä ongelma voidaan kirjoittaa seuraavasti:

Lineaarisen ohjelmoinnin ongelmat voidaan ratkaista analyyttisesti ja graafisesti.

15.3. Kanoninen lineaarinen ohjelmointiongelma

, i=1,…,m,

, j=1,…,n.

Tärkeimmät laskentamenetelmät lineaarisen ohjelmoinnin ongelmien ratkaisemiseksi kehitettiin erityisesti kanonista ongelmaa varten.

15.4. Yleinen lineaarisen ohjelmoinnin ongelma

On tarpeen maksimoida (minimoida) lineaarinen funktio n muuttujia.

rajoitusten alla

, i=1,…, k,

, i=1+ k,…, m,

, …,

Tässä k≤ m, r≤ n. Vakiotehtävä saadaan yleisen erikoistapauksena k= m, r= n; kanoninen – klo k=0, r= n.

Esimerkki.

Makeistehdas valmistaa monenlaisia ​​makeisia. Kutsutaan niitä "A", "B" ja "C". Tiedetään, että kymmenen kilon makeisten "A" myynti antaa voittoa 90 ruplaa, "B" - 100 ruplaa ja "C" - 160 ruplaa. Karkkia voidaan valmistaa mitä tahansa määrää (myynti taataan), mutta raaka-aineita on rajoitetusti. On tarpeen määrittää, millaisia ​​makeisia ja kuinka monta kymmeniä kiloja on tuotettava, jotta kokonaismyyntivoitto maksimoidaan. Kunkin lajin 10 kg:n makeisten valmistukseen tarvittavien raaka-aineiden kulutusprosentit on esitetty taulukossa 1.

Taulukko 1. Raaka-aineen kulutustasot

tuotantoa varten

Ongelman taloudellisella ja matemaattisella muotoilulla on muoto

Etsi tällaiset muuttujan arvot X=(x1, x2, x3), kohteeseen

tavoitefunktio

ehdoin-rajoituksin:

Lineaarisia ohjelmointimenetelmiä käytetään ratkaisemaan monia äärimmäisiä ongelmia, joita usein käsitellään taloustieteessä. Tällaisten ongelmien ratkaiseminen edellyttää joidenkin muuttuvien määrien funktioiden ääriarvojen (maksimi- ja minimiarvo) löytämistä.
Lineaarinen ohjelmointi perustuu järjestelmän ratkaisemiseen lineaariset yhtälöt(muuntamalla yhtälöiksi ja epäyhtälöiksi), kun tutkittavien ilmiöiden välinen suhde on tiukasti toiminnallinen. Sille on ominaista muuttujien matemaattinen lauseke, tietty järjestys, laskutoimitusjärjestys (algoritmi), looginen analyysi. Sitä voidaan käyttää vain tapauksissa, joissa opiskelut aiheet muuttujia ja tekijöillä on matemaattinen varmuus ja määrällinen rajoitus, kun tunnetun laskentasarjan seurauksena syntyy tekijöiden vaihtokelpoisuutta, kun logiikka laskelmissa, matemaattinen logiikka yhdistetään loogisesti perustuvaan ymmärrykseen tutkittavan ilmiön olemuksesta.
Käyttämällä tätä menetelmää teollinen tuotanto esimerkiksi optimaalinen yleistä suorituskykyä koneet, yksiköt, tuotantolinjat (tietyllä tuotevalikoimalla ja muilla annetuilla arvoilla), materiaalien rationaalisen leikkaamisen ongelma (työkappaleiden optimaalisella tuotolla) on ratkaistu. Maataloudessa sitä käytetään määrittämään rehuannosten vähimmäiskustannukset tietylle rehumäärälle (tyypin ja niissä olevien ravinteiden mukaan). Seosongelmalle voi löytyä käyttöä myös valimotuotannossa (metallurgisen panoksen koostumus). Samalla menetelmällä ratkaistaan ​​kuljetusongelma, kuluttajayritysten järkevä liittäminen tuotantoyrityksiin.
Kaikki lineaarisen ohjelmoinnin avulla ratkaistavissa olevat taloudelliset ongelmat eroavat vaihtoehtoisista ratkaisuista ja tietyistä rajoittavista ehdoista. Tällaisen ongelman ratkaiseminen tarkoittaa parhaan, Optimaalisen, valitsemista kaikista hyväksyttävistä mahdollisista (vaihtoehtoisista) vaihtoehdoista. Lineaarisen ohjelmointimenetelmän käytön merkitys ja arvo taloustieteessä on, että optimaalinen vaihtoehto valitaan erittäin merkittävästä joukosta vaihtoehtoisia vaihtoehtoja. Tällaisia ​​ongelmia on lähes mahdotonta ratkaista muilla menetelmillä.

Harkitse esimerkiksi tuotantolaitteiden käyttöajan järkevän käytön ongelman ratkaisemista.
Mukaan toimintasuunnitelma Joulukuun ensimmäisellä viikolla hiomaosasto valmisti 500 rengasta tyypin A laakereille, 300 rengasta tyypin B laakereille ja 450 rengasta tyypin B laakereille. Kaikki renkaat hiottiin kahdella vaihdettavalla koneella erilainen suorituskyky. Jokaisen koneen koneen käyttöaika on 5000 minuuttia. Eri renkaiden valmistuksen toimintojen monimutkaisuus (minuutteina rengasta kohti) on kuvattu seuraavilla tiedoilla (taulukko 6.5).
Taulukko 6.5
On tarpeen määrittää optimaalinen vaihtoehto toimintojen jakamiseen koneille ja aika, joka kuluisi tällä optimaalisella vaihtoehdolla. Suoritetaan tehtävä loppuun simplex menetelmä.
Tämän ongelman matemaattisen mallin laatimiseksi esittelemme seuraavan symboleja: jc, x2, xъ, - vastaavasti koneella I valmistettujen laakereiden L, B, V renkaiden lukumäärä; x4, x5, x6 - vastaavasti renkaiden lukumäärä tyyppien A, B, C laakereille, jotka on valmistettu koneella II.
Optimaalisuuskriteeriä heijastava lineaarinen muoto näyttää tältä:
min a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 rajoituksin
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
x = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=l, ..., 6

Muunnetaan ongelmaehto ottamalla käyttöön lisämuuttujia (apu) ja fiktiivisiä muuttujia. Kirjoitetaan ehto näin:
piikki lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
Yhtälöjärjestelmä, joka kuvastaa tietokoneajan rajoittavia ehtoja ja tuotettujen tuotteiden määrää:
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Ratkaisu tähän ongelmaan on esitetty taulukossa. 6.6. Optimaalinen vaihtoehto saatiin seitsemännessä vaiheessa (iteraatio). Jos kone I valmistaisi 125 tyypin A laakerirengasta, 450 tyyppiä B laakerirengasta ja kone II 375 laakerirengasta tyyppiä A ja 300 laakerirengasta tyyppiä B, niin tällaisella laitekuormalla 350 minuuttia koneaikaa vapautuu koneelle II. Käytetty aika yhteensä optimaalinen vaihtoehto olisi 9650 minuuttia, kun taas tietokoneaikaa käytettiin 10 000 minuuttia.
Hyvin tyypillinen lineaarisella ohjelmoinnilla ratkaistava ongelma on kuljetusongelma. Sen tarkoitus on minimoida rahdin kiertokulku kuljetettaessa kulutustavaroita valmistajalta kuluttajalle, tukkuvarastoista ja tukikohdista vähittäiskauppoihin. kauppayrityksiä. Se voidaan ratkaista käyttämällä simpleksimenetelmää tai jakelumenetelmää.
Ratkaisu kuljetusongelma jakelumenetelmä esitettiin oppikirjan "Theory of Economic Analysis" kolmannessa painoksessa ("Finance and Statistics", 1996).

Työstökoneiden järkevän käytön ongelman ratkaiseminen simpleksimenetelmällä

Lineaarinen ohjelmointi

Lineaarinen ohjelmointi- matemaattinen tieteenala, joka on omistettu teorialle ja menetelmille ratkaista äärimmäisiä ongelmia lineaaristen yhtälöiden ja epäyhtälöiden määrittämillä -ulotteisen vektoriavaruuden sarjoilla.

Lineaarinen ohjelmointi on konveksin ohjelmoinnin erikoistapaus, joka puolestaan ​​on matemaattisen ohjelmoinnin erikoistapaus. Samalla se on perusta useille menetelmille kokonaisluku- ja epälineaaristen ohjelmointiongelmien ratkaisemiseksi. Yksi lineaarisen ohjelmoinnin yleistys on murto-lineaarinen ohjelmointi.

Monet lineaarisen ohjelmointiongelmien ominaisuudet voidaan myös tulkita polyhedrien ominaisuuksiksi ja siten muotoilla ja todistaa geometrisesti.

Tarina

Sisäpistemenetelmän mainitsi ensimmäisen kerran I. I. Dikin vuonna 1967.

Tehtävät

Pääasiallinen (standardi) lineaarisen ohjelmoinnin ongelma kutsutaan ongelmaksi löytää lineaarisen tavoitefunktion minimi ( lineaarinen muoto) muodossa:

olosuhteissa

Lineaarisen ohjelmoinnin ongelma on kanoninen näkemys , jos pääongelmassa ensimmäisen epäyhtälöjärjestelmän sijasta on yhtälöjärjestelmä:

Pääongelma voidaan pelkistää kanoniseksi ottamalla käyttöön lisämuuttujia.

Yleisimmän muodon lineaariset ohjelmointiongelmat (ongelmia, joissa on sekalaisia ​​rajoituksia: yhtäläisyydet ja epätasa-arvot, rajoituksista vapaat muuttujat) voidaan vähentää vastaaviksi (joilla on sama ratkaisujoukko) korvaamalla muuttujat ja korvaamalla yhtäläisyydet parilla epätasa-arvoa.

On helppo nähdä, että maksimin löytämisen ongelma voidaan korvata tehtävällä löytää minimi ottamalla kertoimet päinvastaisella etumerkillä.

Esimerkki ongelmia

Suurin vastaavuus

Harkitse maksimaalista yhteensopivuusongelmaa kaksiosaisessa kaaviossa: poikia ja tyttöjä on useita, ja jokaiselle pojalle ja tytölle tiedetään, ovatko he toisilleen houkuttelevia. Pitää mennä naimisiin enimmäismäärä parit, joilla on molemminpuolista myötätuntoa.

Otetaan käyttöön muuttujat, jotka vastaavat -poika ja -tyttö -paria ja täyttävät rajoitukset:

objektiivifunktiolla. Voidaan osoittaa, että tämän ongelman optimaalisten ratkaisujen joukossa on kokonaisluku. Muuttujat 1 vastaavat pareja, joiden tulisi olla naimisissa.

Suurin virtaus

Olkoon graafi (orientoituneilla reunoilla), jossa jokaiselle reunalle oma läpijuoksu. Ja kaksi kärkeä on annettu: valua ja lähde. Jokaisen reunan kohdalla on ilmoitettava, kuinka paljon nestettä virtaa sen läpi (enintään sen kapasiteetti), jotta kokonaisvirtaus lähteestä viemäriin saadaan maksimoitua (neste ei voi ilmestyä tai kadota kaikissa kärjeissä paitsi viemäriä ja lähdettä).

Otetaan muuttujiksi rivan läpi virtaavan nesteen määrä. Sitten

missä on sen reunan kapasiteetti. Näitä epätasa-arvoja on täydennettävä sisäänvirtaavan ja ulosvirtaavan nesteen määrän yhtäläisyydellä jokaisessa kärjessä, lukuun ottamatta viemäriä ja lähdettä. Funktiona on luonnollista ottaa lähteellä ulosvirtaavan ja sisäänvirtaavan nesteen määrän erotus.

Edellisen ongelman yleistys on vähimmäiskustannusten maksimivirtaus. Tässä tehtävässä kunkin reunan kustannukset on annettu ja sinun on valittava maksimivirtojen joukosta pienin kustannus. Tämä ongelma johtuu kahdesta lineaarisesta ohjelmointitehtävästä: ensin sinun on ratkaistava suurimman virtauksen ongelma ja sitten lisätään tähän tehtävään rajoitus , jossa on maksimivirtauksen arvo, ja ratkaistaan ​​ongelma uusi ominaisuus- virtauskustannukset.

Nämä ongelmat voidaan ratkaista nopeammin kuin yleisillä lineaaristen ohjelmointiongelmien ratkaisualgoritmeilla, johtuen yhtälöiden ja epäyhtälöiden erityisrakenteesta.

Kuljetustehtävä

On tietty homogeeninen lasti, joka on siirrettävä varastoista tehtaille. Jokaisen varaston osalta tiedetään, kuinka paljon rahtia se sisältää, ja kunkin tehtaan lastin kysyntä tunnetaan. Kuljetuskustannukset ovat verrannollisia etäisyyteen varastosta tehtaaseen (kaikki etäisyydet varastosta tehtaaseen ovat tiedossa). Eniten vaaditaan säveltämistä halpa suunnitelma kuljetus.

Ratkaisevat muuttujat tässä tapauksessa ovat tavaramäärät, jotka kuljetetaan varastosta tehtaalle. Ne täyttävät rajoitukset:

Tavoitefunktion muoto on: , joka on minimoitava.

Nollasummapeli

Siellä on kokomatriisi. Ensimmäinen pelaaja valitsee numeron väliltä 1 - , toinen - 1 - . Sitten he tarkistavat numerot ja ensimmäinen pelaaja saa pisteitä ja toinen pisteitä (ensimmäisen pelaajan valitsema numero saa toisen). Meidän on löydettävä optimaalinen strategia ensimmäiselle pelaajalle.

Oletetaan, että esimerkiksi optimaalisessa strategiassa ensimmäisen pelaajan on valittava luku, jonka todennäköisyys on . Silloin optimaalinen strategia on ratkaisu seuraavaan lineaariseen ohjelmointiongelmaan:

jossa funktio on maksimoida. Optimaalisen ratkaisun arvo on pahimmassa tapauksessa ensimmäisen pelaajan voiton matemaattinen odotus.

Ratkaisualgoritmit

Tunnetuin ja yleisimmin käytännössä käytetty yleisen lineaarisen ohjelmoinnin (LP) ongelman ratkaisemiseen on simplex-menetelmä. Huolimatta siitä, että simpleksimenetelmä on melko tehokas algoritmi, joka on osoittanut hyviä tuloksia Sovellettuja LP-ongelmia ratkaistaessa se on eksponentiaalisesti monimutkainen algoritmi. Syynä tähän on simpleksimenetelmän kombinatorinen luonne, joka luettelee peräkkäin toteutettavissa olevien ratkaisujen polyhedronin kärjet optimaalista ratkaisua etsittäessä.

Neuvostoliiton matemaatikko L. Khachiyan ehdotti vuonna 1979 ensimmäistä polynomialgoritmia, ellipsoidimenetelmää, mikä ratkaisi ongelman. pitkään aikaan jäi ratkaisematta. Ellipsoidimenetelmällä on täysin erilainen, ei-kombinatorinen luonne kuin simpleksimenetelmällä. Laskennallisesti tämä menetelmä osoittautui kuitenkin lupaamattomaksi. Kuitenkin itse ongelmien polynomi monimutkaisuus johti kokonaisen luokan luomiseen tehokkaita algoritmeja LP - sisäpistemenetelmät, joista ensimmäinen oli N. Karmarkarin vuonna 1984 ehdottama algoritmi. Tämän tyyppisissä algoritmeissa käytetään jatkuvaa LP-ongelman tulkintaa, kun LP-ongelman ratkaisujen monitahojen kärkien laskemisen sijaan suoritetaan haku avaruuden lentoratoja pitkin. ongelmamuuttujat, joka ei kulje monitahoisen kärkien läpi. Sisäpistemenetelmä, joka, toisin kuin simpleksimenetelmä, ohittaa pisteet alueen sisäpuolelta hyväksyttäviä arvoja, käyttää Fiaccon ja McCormickin 1960-luvulla kehittämiä log-barrier-epälineaarisia ohjelmointimenetelmiä.

Katso myös

• Graafinen menetelmä lineaarisen ohjelmoinnin ongelman ratkaisemiseksi

Huomautuksia

Kirjallisuus

• Thomas H. Corman et ai. Luku 29. Lineaarinen ohjelmointi // Algoritmit: rakentaminen ja analyysi = ALGORITMEIN JOHDANTO. - 2. painos - M.: "Williams", 2006. - S. 1296. - ISBN 5-8459-0857-4
• Akulich I.L. Luku 1. Lineaarisen ohjelmoinnin tehtävät, Luku 2. Lineaarisen ohjelmoinnin erityistehtävät // Matemaattinen ohjelmointi esimerkeissä ja tehtävissä. - M.: Higher School, 1986. - 319 s. - ISBN 5-06-002663-9
• Karmanov V. G. Matemaattinen ohjelmointi. - 3. painos. - M.: Nauka, 1986. - 288 s.
• Danzig George Bernard "Muistoja lineaarisen ohjelmoinnin alusta"

Linkit

• - Ilmainen optimointipaketti, joka on suunniteltu ratkaisemaan lineaarisia, kokonaislukuja ja tavoiteohjelmointiongelmia.
• Vershik A. M. "Tietoja L. V. Kantorovichista ja lineaarisesta ohjelmoinnista"
• Bolshakova I. V., Kuralenko M. V. "Lineaarinen ohjelmointi. Kokeen koulutus- ja metodologinen käsikirja."
• Barsov A. S. "Mikä on lineaarinen ohjelmointi", Suosittuja matematiikan luentoja, Gostekhizdat, 1959.
• M. N. Vyalyi Lineaariset epäyhtälöt ja kombinatoriikka. - MCNMO, 2003.

Wikimedia Foundation.

• 2010.
• Salten, Felix

Glagow, Martina

Katso, mitä "Lineaarinen ohjelmointi" on muissa sanakirjoissa: lineaarinen ohjelmointi - - lineaarinen ohjelmointi Matemaattisen ohjelmoinnin alue, joka on omistettu teorialle ja menetelmille ratkaista äärimmäisiä ongelmia, joille on ominaista lineaarinen riippuvuus välillä……

Lineaarinen ohjelmointi

Lineaarinen ohjelmointi Teknisen kääntäjän opas - matemaattisen ohjelmoinnin ala, joka on omistettu teorialle ja menetelmille äärimmäisten ongelmien ratkaisemiseksi, joille on ominaista muuttujien välinen lineaarinen suhde. Yleisimmässä muodossaan L.p.:n ongelma. voi kirjoittaa näin. Dana......

Talous- ja matemaattinen sanakirja Suuri määrä taloudellisia tehtäviä

pelkistyy lineaarisiin matemaattisiin malleihin. Perinteisesti niitä kutsutaan lineaarisiksi ohjelmointimalleiksi. Lineaarinen ohjelmointi tarkoittaa lineaarista suunnittelua, ts. optimaalisen ratkaisusuunnitelman saaminen lineaarisen rakenteen ongelmiin. Sitä käyttävät yleensä pääkonttoriyksiköiden asiantuntijat tuotantovaikeuksien ratkaisemiseen. Tyypillisiä esimerkkejä lineaarisen ohjelmointimallin sovelluksista ovat seuraavat:

integroitu tuotannon suunnittelu (tuotantoaikataulujen laatiminen, jotka minimoivat korkotason muutoksista johtuvat kokonaiskustannukset); tuotevalikoiman suunnittelu (määritelmä optimaalinen rakenne

elintarvikkeiden tuotanto ihmisille);

tuotteen tuotannon reititys (optimaalisen teknologisen reitin määrittäminen tuotteen valmistukseen);

varaston säätely (optimaalisen tuotteiden yhdistelmän määrittäminen varastossa);

tuotannon aikataulutus (kustannuksia minimoivien aikataulujen laatiminen, ottaen huomioon varaston ylläpitokustannukset, ylitöiden maksaminen ja ulkoiset tilaukset);

tuotteiden jakelun suunnittelu jne.

Yleisimmässä muodossaan lineaarinen ohjelmointi pelkistetään optimointiongelmaksi ja kirjoitetaan seuraavassa muodossa:
Optimointitehtävän ratkaisemiseksi riittää, että löytää sen optimaalinen ratkaisu, ts. osoittaa f(X 0 )≥ f(X) sellasta
milloin tahansa f(X 0 )≤ f(X) tai minimoinnin tapauksessa -
.

milloin tahansa f(X) ei ole rajoitettu ylhäältä sallittuun joukkoon W.

Optimointiongelmien ratkaisumenetelmät riippuvat sekä tavoitefunktion tyypistä f(X) , ja hyväksyttävän joukon rakenteesta W. Jos tehtävän kohdefunktio on funktio n muuttujat, niin ratkaisumenetelmiä kutsutaan matemaattisiksi ohjelmointimenetelmiksi.

Lineaarinen ohjelmointiongelma on operaatiotutkimuksen ongelma, jonka matemaattinen malli on muotoa:

Tässä tapauksessa lineaaristen yhtälöiden (2) ja epäyhtälöiden (3), (4) järjestelmä, joka määrittää hyväksyttävät ratkaisut ongelmaan W, kutsutaan lineaarisen ohjelmointiongelman rajoitusjärjestelmäksi ja lineaarifunktioksi f(X) kutsutaan tavoitefunktioksi tai optimiteettikriteeriksi.

Jos lineaarisen ohjelmointitehtävän matemaattisen mallin muoto on:

sitten he sanovat, että ongelma esitetään kanonisessa muodossa.

Mikä tahansa lineaarinen ohjelmointiongelma voidaan pelkistää lineaariseksi ohjelmointiongelmaksi kanonisessa muodossa siirtämällä maksimointi minimointiin, epätasa-arvorajoituksista tasa-arvorajoituksiin ja korvaamalla muuttujat, jotka eivät noudata ei-negatiivisuusehtoa. Tietyn funktion maksimointi vastaa saman funktion minimoimista vastakkaisella merkillä ja päinvastoin.

Sääntö lineaarisen ohjelmoinnin ongelman vähentämiseksi kanoninen muoto on seuraava:

1) jos alkuperäisessä tehtävässä on tarpeen määrittää lineaarisen funktion maksimi, sinun tulee muuttaa etumerkkiä ja etsiä tämän funktion minimi;

2) jos rajoitusten oikea puoli on negatiivinen, tämä rajoitus tulee kertoa (-1);

3) jos rajoitusten joukossa on epätasa-arvoja, ne muunnetaan yhtäläisiksi lisäämällä ei-negatiivisia muuttujia;

4) jos jokin muuttuja x k ei ole merkkirajoituksia, niin se korvataan (tavoitefunktiossa ja kaikissa rajoituksissa) kahden uuden ei-negatiivisen muuttujan erolla: x k = x’ k - x 1 , jossa 1 on vapaa indeksi, x’ k ≥ 0, x 1 ≥ 0.

Yhteenvetona edellä olevasta voimme tehdä seuraavat johtopäätökset:

1. Lineaaristen ohjelmointiongelmien rajoitteet voidaan ilmaista sekä yhtäläisyyksillä että epätasa-arvoilla.

2. Lineaarinen funktio voi pyrkiä sekä maksimiin että minimiin.

3. Mallin muuttujat ovat aina ei-negatiivisia.

4. Mistä tahansa lineaarisesta ohjelmointitehtävästä voit siirtyä kanoniseen (pää) lineaariseen ohjelmointitehtävään.

Jokainen lineaarinen ohjelmointitehtävä voidaan verrata toiseen lineaariseen ohjelmointitehtävään, joka on kaksoispiste alkuperäisen (suoran) ongelman kanssa.

Harkitse seuraavan muotoista lineaarista ohjelmointitehtävää:

Ongelma edellyttää tavoitefunktion maksimoimista; kaikki rajoitukset ovat epäyhtälöitä, joiden merkki on ≤, kaikki muuttujat X 1 , X 2 ,…,X n n ohjausmuuttujat ja m rajoituksia. Tavoitefunktion muuttujien kertoimet: c 1 , c 2 ,…, c n; ilmaiset jäsenet: b 1 , b 2 ,…, b m .

Kaksoislineaarisen ohjelmoinnin ongelmalla on muoto:

Kaksoistehtävässä on löydettävä tavoitefunktion minimi, rajoitukset - epäyhtälöt merkillä ≥, ohjausmuuttujat y 1 , y 2 ,…, y m ei-negatiivinen. Tehtävä sisältää m ohjausmuuttujat ja n rajoituksia. Tehtävän tavoitefunktion kertoimet b 1 , b 2 ,…, b m ovat alkuperäisen lineaarisen ohjelmointiongelman ilmaiset ehdot ja ilmaiset ehdot kaksoisongelma c 1 , c 2 ,…, c n – alkuperäisen lineaarisen ohjelmointitehtävän kohdefunktion kertoimet. Duaalitehtävän kerroinmatriisi transponoidaan, ts. Rivit korvataan sarakkeilla ja sarakkeet rivillä.

Tehtävät (9)–(10) ja (11)–(12) muodostavat tehtäväparin, jota kutsutaan lineaarisessa ohjelmoinnissa kaksoispariksi.

Kaksoisongelma alkuperäiseen verrattuna muodostetaan seuraavien sääntöjen mukaisesti:

1. Objektiivifunktio alkuperäinen ongelma on asetettu maksimiarvoon ja kaksoisobjektifunktio on asetettu minimiin.

2. Matriisi A(13)

jotka koostuvat alkuperäisen tehtävän (9) – (10) rajoitusjärjestelmän (10) tuntemattomien kertoimista ja kaksoistehtävän (11) – (12) vastaavasta matriisista saadaan toisistaan ​​transponoimalla.

3. Kaksoistehtävän (11) – (12) muuttujien lukumäärä on yhtä suuri kuin alkuperäisen tehtävän järjestelmässä (10) olevien rajoitusten määrä ja kaksoistehtävän järjestelmässä (12) olevien rajoitusten määrä on yhtä suuri kuin alkuperäisen tehtävän muuttujien lukumäärä.

4. Tuntemattomien kertoimet kaksoistehtävän tavoitefunktiossa (11) ovat alkuperäisen tehtävän järjestelmän (10) vapaita termejä ja järjestelmän (12) rajoitusten oikeat puolet. kaksoistehtävä ovat alkuperäisen tehtävän tavoitefunktion (9) tuntemattomien kertoimet.

5. Jos muuttuja x j Alkuperäisen ongelman (9)–(10) arvot voivat olla vain ei-negatiivisia j- Kaksoistehtävän järjestelmän (12) rajoitus on muotoa ≥ oleva epäyhtälö. Jos muuttuja x j voi siis ottaa sekä positiivisia että negatiivisia arvoja j- e rajoitus järjestelmässä (12) on yhtälö. Samanlaisia ​​yhteyksiä esiintyy alkuperäisen ongelman rajoitteiden (10) ja kaksoisongelman muuttujien välillä. Jos i- Jos alkuperäisen ongelman järjestelmän (10) rajoitus on epäyhtälö, niin i- Olen kaksoisongelman muuttuja y i ≥ 0. Jos i- Jos rajoite on yhtälö, niin muuttuja y i voi ottaa sekä positiivisia että negatiivisia arvoja.

Ajatus ratkaisun peräkkäisestä parantamisesta muodosti perustan universaalille menetelmälle lineaaristen ohjelmointiongelmien ratkaisemiseksi - simplex-menetelmälle. Tämän menetelmän geometrinen merkitys koostuu peräkkäisestä siirtymisestä rajoituspolyhedronin yhdestä kärjestä (kutsutaan alkuperäiseksi) viereiseen, jossa lineaarinen funktio saa parhaan (mukaan vähintään, ei pahin) arvo (suhteessa ongelman tavoitteeseen), kunnes optimaalinen ratkaisu löytyy - kärki, jossa tavoitefunktion optimaalinen arvo saavutetaan (jos ongelmalla on lopullinen optimi). Menetelmän ideat julkaisi venäläinen tiedemies L.V. Kantorovich vuonna 1939

Yksipuolisen menetelmän soveltamiseksi ongelmarajoitteisiin lisätään lisämuuttujia y 1 , y 2 ,…, y i ja alkuperäisen ongelman ehto on muodossa:

Tämä lausunto voidaan esittää taulukon muodossa - simplex-menetelmän ensimmäinen taulukko (taulukko 1.1).

Taulukko 1.1.

Ensimmäinen simplex-pöytä

Yksipuolisen taulukon laatimiseksi voit soveltaa tiettyjä sääntöjä.

1. Ensimmäinen taulukko:

a) Kirjoita ensimmäiseen sarakkeeseen y m– perusmuuttujat, jotka ovat vasemmalla olevissa yhtälöissä;

b) vapaat muuttujat a mn vietiin ulos ylälinja taulukot;

c) vapaiden muuttujien edessä olevat kertoimet kirjoitetaan jäljellä oleviin sarakkeisiin.

2. Seuraavat taulukot:

a) Indeksirivin pienin negatiivinen elementti valitaan haettaessa maksimiarvoa, mutta suurin positiivinen elementti valitaan minimiä haettaessa, vapaiden termien vektoria lukuun ottamatta;

b) tämä elementti määrittelee avainsarakevektorin ja se syötetään kantaan;

c) vapaiden termien vektorin komponentit jaetaan positiivisiin elementteihin avainsarake;

d) pienin valitaan saaduista suhteista;

e) rivivektori, joka sisältää pienimmän positiivisen osamäärän, on avain ja johdetaan kannasta;

f) avainrivien ja sarakkeen leikkauskohdassa on salliva elementti;

g) matriisimuunnos:

Jokainen avainmerkkijonoelementti on jaettu käyttöönottoelementtiin. Tuloksena olevat osamäärät ovat seuraavan taulukon avainrivielementtejä,

Avainsarake sisään uusi pöytä– nollia, erotuselementtiä lukuun ottamatta,

Uuden taulukon muut elementit lasketaan seuraavan kaavion mukaisesti:

Uusi elementti = vanha elementti -

- Avainrivielementti*Avainsarakkeen elementti

Salliva elementti

Jos nollarivi (sarake) sisältää nollan, vastaava sarake (uuden taulukon rivi0 ei muutu.

3. Pisteitä "a" - "g" toistetaan, kunnes indeksirivillä ei ole enää yhtään negatiivista elementtiä haettaessa maksimia (mutta ei yhtäkään positiivista elementtiä minimiä haettaessa).

Esimerkki 1.1. On tarpeen tehdä päätös optimaalisesta suunnitelmasta neuleiden valmistukseen kuukaudeksi Sviyazh OJSC:ssä simplex-menetelmillä.

Tehdään suunnitelma miesten neulemallien tuotannosta, jotta saadaan maksimaalinen voitto annetuilla resursseilla rakentamalla matemaattinen malli. Lähtötiedot on esitetty taulukossa 1.2.

Taulukko 1.2.

Alkutiedot

Alustavat tiedot materiaali- ja työvoimaresurssien ominaiskulutuksesta on esitetty taulukossa. 1.2 organisaatiossa voimassa olevien säädösten ja teknisten asiakirjojen mukaisesti. Rivi "Materiaalivarat" tallentaa niukkaimman (rajoitetun0) materiaalityypin - villalangan - kulutuksen.

Rivi "Laitteisto" näyttää yhteenvetona työvoimaintensiteetin tuoteyksikön valmistuksen normaalitunneissa kaikkien osatoimintojen kokonaissummana. Myös muun tyyppiset resurssit otetaan luonnollisissa yksiköissä: työvoimavarat - tunneissa; materiaali - dm 2.

"Tuotto"-rivi kuvaa tuoteyksikön myynnistä saatua voittoa tuoteyksikön suunnitellusta kustannusarviosta.

Kautta x 1 , x 2 , x 3 , x 4 ilmoitettiin tuotettujen tuotteiden määrät kullekin lajitelmatyypille.

Luodaan matemaattinen malli lineaarisen ohjelmointitehtävän muodostamisen säännön mukaan:

Tehtävän rajoituksissa otamme käyttöön lisämuuttujia y 1 , y 2 , y 3 ja kirjoita ongelmaehto uudelleen yhtälön muotoon:

Viimeinen lause voidaan esittää taulukon 1.3 muodossa - simplex-menetelmän ensimmäinen taulukko, jota käytämme lineaarisen ohjelmoinnin ongelman ratkaisemiseen.

Taulukko 1.3.

Ensimmäinen simplex-pöytä

Ensimmäinen sarake sisältää y i – perusmuuttujat ovat yhtälön vasemmalla puolella olevat muuttujat ja vapaat muuttujat x j sijoitetaan taulukon ylimmälle riville. Loput sarakkeet sisältävät vapaiden muuttujien kertoimet. Indeksiviiva on tulos, kun vapaiden muuttujien edessä olevat kertoimet vähennetään nollasta.

Seuraavan taulukon luomiseksi valitaan indeksirivin pienin negatiivinen elementti (tämä on 222). Tämä elementti määrittelee avainsarakevektorin ja se lisätään kantaan. Vapaiden termien vektorin komponentit jaetaan avainsarakkeen positiivisilla elementeillä ja tuloksena olevista suhteista valitaan pienin. Rivivektori, joka sisältää pienimmän positiivisen osamäärän, on avain ja johdetaan kannasta ( y 2 ). Avainrivien ja sarakkeen leikkauskohdassa on aktivointielementti (tämä on 55.50).

Jokainen avainmerkkijonoelementti jaetaan sitten käyttöönottoelementiksi. Tuloksena olevat osamäärät ovat seuraavan taulukon avainrivin elementtejä. Tuloksena saatiin toinen simpleksitaulukko (taulukko 1.4).

Taulukko 1.4.

Toinen simplex-taulukko

Koska indeksiriville on ilmestynyt negatiivinen elementti, kaikki vastaavat vaiheet tulee toistaa ja rakentaa kolmas simpleksitaulukko.

Tuloksena on taulukko. 1.5.

Taulukko 1.5.

Lopullinen simplex-taulukko

Taulukon 1.5 perusteella voimme tehdä johtopäätökset: vapaiden termien sarakkeessa kaikki elementit ovat positiivisia (tämä tarkoittaa, että tuloksena oleva ratkaisu on hyväksyttävä); indeksirivillä kaikki elementit ovat myös positiivisia (tämä tarkoittaa, että tuloksena oleva ratkaisu on optimaalinen, eli se maksimoi tavoitefunktion); optimaalinen suunnitelma olisi seuraavat arvot:
(eli ne ovat perus);
(koska ne ovat ilmaisia); tavoitefunktio L= 4 201 195.

Taulukosta 1.5 seuraa myös, että perusmuuttuja y 3 =9716 ja vapaat muuttujat y 1 = y 2 = 0 eli optimaalisessa suunnitelmassa työvoima- ja materiaaliresurssit ovat nolla, koska ne on täysin käytetty. Varusteet resurssit y 2 = 9716, mikä osoittaa sen ylijäämää.

Siten lineaarisen ohjelmointimenetelmän soveltamisen seurauksena päätettiin valmistaa valitun mallin miesten neulepuseroita 3981 kappaletta, miesten villapaitoja mallia 55-1 29 875 kappaletta.