Jos on vain yksi rajoittava tekijä (esimerkiksi niukka kone), ratkaisu voidaan löytää käyttämällä yksinkertaisia kaavoja(katso linkki artikkelin alussa). Jos rajoittavia tekijöitä on useita, käytetään menetelmää lineaarinen ohjelmointi.
Lineaarinen ohjelmointi on nimi, joka annetaan johtamistieteessä käytettyjen työkalujen yhdistelmälle. Tämä menetelmä ratkaisee jakeluongelman rajalliset resurssit kilpailevien toimintojen välillä joidenkin maksimoimiseksi tai minimoimiseksi numeerisia arvoja, kuten maksumarginaali tai kulut. Liiketoiminnassa sitä voidaan käyttää esimerkiksi tuotannon suunnittelussa suurin suurennus voitot, komponenttien valinta kustannusten minimoimiseksi, investointiportfolion valinta kannattavuuden maksimoimiseksi, tavaroiden kuljetuksen optimointi etäisyyksien lyhentämiseksi, henkilöstön määrääminen työn tehokkuuden maksimoimiseksi ja työn ajoittaminen ajan säästämiseksi.
Lataa muistiinpano muodossa, kuvat muodossa
Lineaarinen ohjelmointi sisältää rakentamisen matemaattinen malli harkittava ongelma. Tämän jälkeen ratkaisu löytyy graafisesti (käsitelty alla), jossa käyttämällä Exceliä(käsitellään erikseen) tai erikoistuneet tietokoneohjelmat.
Ehkä matemaattisen mallin rakentaminen on vaikein osa lineaarista ohjelmointia, ja se vaatii tarkasteltavan ongelman kääntämistä muuttujien, yhtälöiden ja epäyhtälöiden järjestelmäksi - prosessiksi, joka viime kädessä riippuu käyttäjän taidoista, kokemuksesta, kyvyistä ja intuitiosta. mallintaja.
Tarkastellaan esimerkkiä lineaarisen ohjelmoinnin matemaattisen mallin rakentamisesta
Nikolai Kuznetsov johtaa pientä mekaanista tehdasta. Ensi kuussa hän suunnittelee valmistavansa kaksi tuotetta (A ja B), joiden ominaismarginaalivoiton arvioidaan olevan 2 500 ja 3 500 ruplaa.
Molemmat tuotteet vaativat koneistuksen, raaka-aineet ja työvoimakustannukset (kuva 1). Jokainen tuoteyksikkö A vaatii 3 tuntia koneistusta, 16 yksikköä raaka-aineita ja 6 yksikköä työvoimaa tuottaakseen. Tuotteen B vastaavat yksikkövaatimukset ovat 10, 4 ja 6. Nicholas ennustaa voivansa toimittaa ensi kuussa 330 koneistustuntia, 400 yksikköä raaka-aineita ja 240 työyksikköä. Tuotantoprosessin tekniikka on sellainen, että tuotetta B tulee tuottaa vähintään 12 yksikköä kuukaudessa.
Riisi. 1. Resurssien käyttö ja tarjoaminen
Nikolai haluaa rakentaa mallin, jolla määritetään tuotteiden A ja B yksiköiden lukumäärä, jotka hänen on tuotettava seuraavan kuukauden aikana maksimoidakseen panoksensa.
Lineaarinen malli voidaan rakentaa neljässä vaiheessa.
Vaihe 1: Muuttujien määrittäminen
On tavoitemuuttuja (kutsutaanko sitä Z:ksi), joka on optimoitava, eli maksimoitava tai minimoitava (esimerkiksi voitto, tuotot tai kulut). Nikolay pyrkii maksimoimaan maksumarginaalin, joten tavoitemuuttuja:
Z = kokonaismarginaalivoitto (ruplina), joka on saatu seuraavan kuukauden aikana tuotteiden A ja B valmistuksesta.
On olemassa joukko tuntemattomia tuntemattomia muuttujia (merkitkäämme ne x 1, x 2, x 3 jne.), joiden arvot on määritettävä optimaalisen arvon saamiseksi. tavoitefunktio, joka meidän tapauksessamme on kokonaismarginaalivoitto. Tämä marginaali riippuu tuotettujen tuotteiden A ja B määristä. Näiden määrien arvot on laskettava, ja siksi ne edustavat mallissa haluttuja muuttujia. Merkitään siis:
x 1 = seuraavan kuukauden aikana valmistettujen tuotteen A yksiköiden lukumäärä.
x 2 = seuraavan kuukauden aikana valmistettujen tuotteen B yksiköiden lukumäärä.
On erittäin tärkeää määritellä kaikki selkeästi muuttujia; erityistä huomiota Kiinnitä huomiota mittayksiköihin ja aikajaksoon, johon muuttujat viittaavat.
Vaihe. 2. Tavoitefunktion rakentaminen
Tavoitefunktio on lineaarinen yhtälö, joka on joko maksimoitava tai minimoitava. Se sisältää kohdemuuttujan ilmaistuna kohdemuuttujilla, eli Z ilmaistuna x 1, x 2 ... lineaarisena yhtälön muodossa.
Esimerkissämme jokainen valmistettu tuote A tuo 2500 ruplaa. rajavoitto, ja kun tuotetta A tuottaa x 1 yksikköä, marginaalivoitto on 2500 * x 1. Samoin marginaalivoitto tuotteen B x 2 yksikön valmistamisesta on 3500 * x 2. Siten kokonaismarginaalivoitto, joka saadaan seuraavan kuukauden aikana tuottamalla x 1 yksikköä tuotetta A ja x 2 yksikköä tuotetta B, eli tavoitemuuttuja Z on:
Z = 2500 * x 1 + 3500 * x 2
Nikolay pyrkii maksimoimaan tämän indikaattorin. Siten mallimme tavoitefunktio on:
Maksimoi Z = 2500 * x 1 + 3500 * x 2
Vaihe. 3. Määrittele rajoitukset
Rajoitukset ovat järjestelmä lineaariset yhtälöt ja/tai epäyhtälöt, jotka rajoittavat haettujen muuttujien arvoja. Ne kuvaavat matemaattisesti resurssien saatavuutta, teknisiä tekijöitä, markkinointiolosuhteita ja muita vaatimuksia. Rajoitukset voivat olla kolmenlaisia: "pienempi tai yhtä suuri", "suurempi tai yhtä suuri", "tiukasti yhtä suuri".
Esimerkissämme tuotteiden A ja B valmistaminen vaatii koneistusaikaa, raaka-aineita ja työvoimaa, ja näiden resurssien saatavuus on rajallinen. Näiden kahden tuotteen tuotantomääriä (eli arvoja x 1 x 2) rajoittaa siis se, että tuotantoprosessissa tarvittavien resurssien määrä ei voi ylittää käytettävissä olevia resursseja. Tarkastellaan tilannetta koneenkäsittelyajan kanssa. Jokaisen tuotteen A yksikön valmistaminen vaatii kolme tuntia koneistusta, ja jos valmistetaan x 1 yksikköä, tätä resurssia kuluu 3 * x 1 tuntia. Jokaisen tuoteyksikön B valmistukseen tarvitaan 10 tuntia, joten jos tuotetta valmistetaan x 2, vaaditaan 10 * x 2 tuntia. Näin ollen kokonaisaika, joka tarvitaan x 1 yksikön tuotetta A ja x 2 yksikköä tuotetta B, on 3 * x 1 + 10 * x 2 . Tämä koneen kokonaisaika ei saa ylittää 330 tuntia. Matemaattisesti tämä on kirjoitettu seuraavasti:
3 * x 1 + 10 * x 2 ≤ 330
Samankaltaiset näkökohdat koskevat raaka-aineita ja työvoimaa, minkä ansiosta voimme kirjoittaa vielä kaksi rajoitusta:
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
Lopuksi on huomattava, että on olemassa ehto, jonka mukaan tuotetta B on tuotettava vähintään 12 yksikköä:
Vaihe 4. Ei-negatiivisten ehtojen kirjoittaminen
Vaaditut muuttujat eivät voi olla negatiivisia lukuja, jotka on kirjoitettava epäyhtälöiden muodossa x 1 ≥ 0 ja x 2 ≥ 0. Esimerkissämme toinen ehto on redundantti, koska edellä määritettiin, että x 2 ei voi olla pienempi kuin 12 .
Täydellinen lineaarinen ohjelmointimalli tuotantotehtävä Nicholas voidaan kirjoittaa seuraavasti:
Maksimoi: Z = 2500 * x 1 + 3500 * x 2
Edellyttäen, että: 3 * x 1 + 10 * x 2 ≤ 330
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
Tarkastellaan graafista menetelmää lineaarisen ohjelmoinnin ongelman ratkaisemiseksi.
Tämä menetelmä soveltuu vain ongelmiin, joissa on kaksi tuntematonta muuttujaa. Menetelmän havainnollistamiseen käytetään yllä rakennettua mallia.
Kaavion akselit edustavat kahta kiinnostavaa muuttujaa (kuva 2). Ei ole väliä, mikä muuttuja on piirretty mille akselille. On tärkeää valita mittakaava, jonka avulla voit lopulta rakentaa visuaalisen kaavion. Koska molempien muuttujien on oltava ei-negatiivisia, vain 1. kvadrantti piirretään.
Riisi. 2. Graafisten akselien lineaarinen ohjelmointi
Tarkastellaan esimerkiksi ensimmäistä rajoitusta: 3 * x 1 + 10 * x 2 ≤ 330. Tämä epäyhtälö kuvaa viivan alla olevaa aluetta: 3 * x 1 + 10 * x 2 = 330. Tämä suora leikkaa x 1 -akselin kohdassa x 2 = 0, eli yhtälö näyttää tältä: 3 * x 1 + 10 * 0 = 330 ja sen ratkaisu: x 1 = 330 / 3 = 110
Samalla tavalla laskemme leikkauspisteet x1- ja x2-akseleilla kaikille rajoituksille:
| Alue hyväksyttäviä arvoja | Hyväksyttyjen arvojen raja | Leikkaus x-akselin 1 kanssa | Leikkaus x-akselin 2 kanssa |
| 3 * x 1 + 10 * x 2 ≤ 330 | 3 * x 1 + 10 * x 2 = 330 | x 1 = 110; x 2 = 0 | x 1 = 0; x 2 = 33 |
| 16 * x 1 + 4 * x 2 ≤ 400 | 16 * x 1 + 4 * x 2 = 400 | x 1 = 25; x 2 = 0 | x 1 = 0; x 2 = 100 |
| 6 * x 1 + 6 * x 2 ≤ 240 | 6 * x 1 + 6 * x 2 = 240 | x 1 = 40; x 2 = 0 | x 1 = 0; x 2 = 40 |
| x 2 ≥ 12 | x 2 = 12 | ei mene ristiin; kulkee yhdensuuntaisesti x-akselin 1 kanssa | x 1 = 0; x 2 = 12 |
Graafisesti ensimmäinen rajoitus on esitetty kuvassa. 3.
Riisi. 3. Ensimmäisen rajoitteen toteuttamiskelpoisten ratkaisujen alueen rakentaminen
Mikä tahansa valitun kolmion sisällä tai sen rajoilla oleva piste täyttää tämän rajoituksen. Tällaisia pisteitä kutsutaan kelvollisiksi ja kolmion ulkopuolisia pisteitä kutsutaan virheellisiksi.
Samalla tavalla näytämme jäljellä olevat rajoitukset kaaviossa (kuva 4). Arvot x 1 ja x 2 varjostetulla alueella ABCDE tai sen sisällä täyttävät kaikki mallin rajoitukset. Tätä aluetta kutsutaan toteuttamiskelpoisten ratkaisujen alueeksi.
Riisi. 4. Koko mallin toteuttamiskelpoisten ratkaisujen alue
Nyt toteutettavissa olevien ratkaisujen alueella on tarpeen määrittää arvot x 1 ja x 2, jotka maksimoivat Z:n. Tätä varten tavoitefunktion yhtälössä:
Z = 2500 * x 1 + 3500 * x 2
jaa (tai kerro) kertoimet ennen x 1 ja x 2 samalla luvulla niin, että tuloksena saadut arvot osuvat kaaviossa näkyvälle alueelle; meidän tapauksessamme tämä alue on 0 - 120; joten kertoimet voidaan jakaa 100:lla (tai 50:llä):
Z = 25 x 1 + 35 x 2
määritä sitten Z:lle arvo, joka on yhtä suuri kuin kertoimien tulo ennen x 1:tä ja x 2:ta (25 * 35 = 875):
875 = 25x1 + 35x2
ja lopuksi etsi suoran leikkauspisteet x 1- ja x 2 -akselien kanssa:
Piirretään tämä kohdeyhtälö kuvaajalle, joka on samanlainen kuin rajoitukset (kuva 5):
Riisi. 5. Kohdefunktion käyttäminen (musta pisteviiva) toteuttamiskelpoisten ratkaisujen alueelle
Z-arvo on vakio koko tavoitefunktion rivillä. Löytääksesi arvot x 1 ja x 2, jotka maksimoivat Z:n, sinun on siirrettävä kohdefunktion viiva rinnakkain pisteeseen, joka on toteutettavissa olevan ratkaisualueen rajoissa, joka sijaitsee suurin etäisyys kohdefunktion alkuperäisestä rivistä ylöspäin ja oikealle, eli pisteeseen C (kuva 6).
Riisi. 6. Tavoitefunktion viiva on saavuttanut maksiminsa mahdollisten ratkaisujen alueella (pisteessä C)
Siitä voidaan päätellä optimaalinen ratkaisu sijoitetaan yhteen päätösalueen ääripisteistä. Kumpi riippuu tavoitefunktion kulmasta ja siitä, mitä ongelmaa ratkaisemme: maksimointi vai minimointi. Siten ei ole tarpeen piirtää tavoitefunktiota - tarvitsee vain määrittää x 1:n ja x 2:n arvot kussakin ääripisteessä lukemalla kaaviosta tai ratkaisemalla sopiva yhtälöpari. Löydetyt arvot x 1 ja x 2 korvataan sitten tavoitefunktioon Z:n vastaavan arvon laskemiseksi. Optimaalinen ratkaisu on se, joka saa Z:n maksimiarvon maksimointitehtävää ratkaistaessa ja minimin ratkaistaessa minimointiongelma.
Määritetään esimerkiksi x 1:n ja x 2:n arvot pisteessä C. Huomaa, että piste C sijaitsee viivojen leikkauskohdassa: 3x 1 + 10x 2 = 330 ja 6x 1 + 6x 2 = 240. Tämän yhtälöjärjestelmän ratkaiseminen antaa: x 1 = 10, x 2 = 30. Laskentatulokset toteutettavissa olevien ratkaisujen alueen kaikkien kärkien osalta on esitetty taulukossa:
| Piste | Arvo x 1 | Arvo x 2 | Z = 2500x1 + 3500x2 |
| A | 22 | 12 | 97 000 |
| IN | 20 | 20 | 120 000 |
| KANSSA | 10 | 30 | 130 000 |
| D | 0 | 33 | 115 500 |
| E | 0 | 12 | 42 000 |
Näin ollen Nikolai Kuznetsin pitäisi suunnitella ensi kuussa 10 tuotteen A ja 30 tuotteen B tuotanto, mikä antaa hänelle mahdollisuuden saada 130 tuhannen ruplan marginaalivoittoa.
Lyhyesti ydin graafinen menetelmä ratkaisuja lineaariset ongelmat ohjelmointi voidaan ilmaista seuraavasti:
- Piirrä kaavioon kaksi akselia, jotka edustavat ratkaisun kahta parametria; piirrä vain 1. kvadrantti.
- Määritä kaikkien rajaehtojen ja akseleiden leikkauspisteiden koordinaatit korvaamalla vuorotellen arvot x 1 = 0 ja x 2 = 0 rajaehtojen yhtälöihin.
- Piirrä mallin rajoitusviivat kaavioon.
- Määritä kaaviosta alue (jota kutsutaan toteuttamiskelpoiseksi päätösalueeksi), joka täyttää kaikki rajoitukset. Jos sellaista aluetta ei ole, mallilla ei ole ratkaisua.
- Määritä kohdemuuttujien arvot päätösalueen ääripisteissä ja laske kussakin tapauksessa vastaava kohdemuuttujan Z arvo.
- Maksimointiongelmissa ratkaisu on piste, jossa Z on maksimi, ratkaisu on piste, jossa Z on minimi.
Objektiivinen toiminto- useiden muuttujien reaali- tai kokonaislukufunktio, jota optimoidaan (minimoidaan tai maksimoidaan) jonkin optimointiongelman ratkaisemiseksi. Termiä käytetään matemaattisessa ohjelmoinnissa, operaatiotutkimuksessa, lineaarisessa ohjelmoinnissa, tilastollisessa päätösteoriassa ja muilla matematiikan alueilla, ensisijaisesti soveltavassa luonteessa, vaikka optimoinnin tavoitteena voi olla myös itse matemaattisen ongelman ratkaisu. Optimointitehtävän tavoitefunktion lisäksi muuttujille voidaan määrittää rajoituksia yhtäläisyys- tai epäyhtälöjärjestelmän muodossa. Yleensä tavoitefunktion argumentit voidaan määrittää mielivaltaisissa joukoissa.
Esimerkkejä
Sileät funktiot ja yhtälöjärjestelmät
Minkä tahansa yhtälöjärjestelmän ratkaisemisen ongelma
(F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1, x 2, …, x M) = 0 … F N (x 1, x 2, …, x M) = 0 ( \displaystyle \left\((\begin(matriisi)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\lpisteet ,x_(M))=0\\\lpisteet \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matriisi) )\oikein.)
voidaan muotoilla tavoitefunktion minimoimisen ongelmaksi
S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\näyttötyyli S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad (1))
Jos funktiot ovat sileitä, minimointiongelma voidaan ratkaista gradienttimenetelmillä.
Minkä tahansa tasaisen tavoitefunktion osalta kaikkien muuttujien osittaiset derivaatat voidaan rinnastaa 0:ksi (\displaystyle 0). Tavoitefunktion optimi on yksi ratkaisuista tällaiseen yhtälöjärjestelmään. Toiminnon (1) (\displaystyle (1)) tapauksessa tämä on yhtälöjärjestelmä, joka käyttää pienimmän neliösumman menetelmää (LSM). Jokainen päätös alkuperäinen järjestelmä on ratkaisu pienimmän neliösumman järjestelmään. Jos alkuperäinen järjestelmä on epäjohdonmukainen, niin pienimmän neliösumman järjestelmä, jolla on aina ratkaisu, mahdollistaa alkuperäisen järjestelmän likimääräisen ratkaisun. Pienimmän neliösumman järjestelmän yhtälöiden lukumäärä on sama kuin tuntemattomien lukumäärä, mikä joskus helpottaa yhteisten alkujärjestelmien ratkaisua.
Lineaarinen ohjelmointi
Muille kuuluisa esimerkki Tavoitefunktio on lineaarinen funktio, joka syntyy lineaarisen ohjelmoinnin ongelmissa. Toisin kuin neliöllinen tavoitefunktio, lineaarisen funktion optimointi on mahdollista vain, jos on olemassa rajoituksia lineaaristen yhtäläisyyksien tai epäyhtälöiden järjestelmän muodossa.
Kombinatorinen optimointi
Tyypillinen esimerkki kombinatorisesta tavoitefunktiosta on matkustavan myyjän ongelman tavoitefunktio. Tämä funktio on yhtä suuri kuin Hamiltonin syklin pituus kuvaajassa. Se määritellään graafin n − 1 (\displaystyle n-1) kärjen permutaatioiden joukossa ja määräytyy graafin reunan pituuksien matriisin avulla. Tällaisten ongelmien tarkka ratkaisu riippuu usein vaihtoehtojen luettelemisesta.
Luku 1. Lineaarisen ohjelmoinnin pääongelman selvitys
Lineaarinen ohjelmointi
Lineaarinen ohjelmointi on matemaattisen ohjelmoinnin osa, joka tutkii menetelmiä ratkaista äärimmäisiä ongelmia, joille on tunnusomaista lineaarinen riippuvuus muuttujien ja lineaarisen testin välillä. Tällaiset ongelmat löytävät laajoja sovelluksia ihmisen toiminnan eri aloilla. Tällaisten ongelmien systemaattinen tutkiminen aloitettiin vuosina 1939–1940. L.V.:n teoksissa. Kantorovich.
Lineaarisen ohjelmoinnin matemaattisiin ongelmiin kuuluvat tiettyjen tuotanto- ja taloustilanteiden tutkimukset, jotka tavalla tai toisella tulkitaan ongelmiksi optimaalinen käyttö rajalliset resurssit.
Lineaarisilla ohjelmointimenetelmillä ratkaistavien ongelmien kirjo on melko laaja. Näitä ovat esimerkiksi:
resurssien optimaalisen käytön ongelma tuotannon suunnittelussa;
sekoitusongelma (tuotteen koostumuksen suunnittelu);
löytämisen ongelma optimaalinen yhdistelmä erilaisia tyyppejä tuotteet varastointiin (varastonhallinta tai);
kuljetustehtävät (yrityksen sijainnin analyysi, tavaroiden liikkuminen).
Lineaarinen ohjelmointi on matemaattisen ohjelmoinnin kehittynein ja laajimmin käytetty osa (lisäksi tämä sisältää: kokonaisluku-, dynaamisen, epälineaarisen, parametrisen ohjelmoinnin). Tämä selitetään seuraavasti:
matemaattisia malleja suuri määrä taloudellisia tehtäviä lineaarinen suhteessa haluttuihin muuttujiin;
Tämän tyyppinen ongelma on tällä hetkellä eniten tutkittu. Sitä varten on kehitetty erityisiä menetelmiä, joiden avulla nämä ongelmat ratkaistaan, ja vastaavia tietokoneohjelmia;
monet lineaariset ohjelmointiongelmat ovat ratkaistuaan löytäneet laajan sovelluksen;
joitakin ongelmia, jotka alkuperäisessä koostumuksessa eivät ole lineaarisia, sarjan jälkeen lisärajoituksia ja olettamuksista voi tulla lineaarisia tai ne voidaan pelkistää sellaiseen muotoon, että ne voidaan ratkaista lineaarisilla ohjelmointimenetelmillä.
Minkä tahansa lineaarisen ohjelmointiongelman taloudellinen ja matemaattinen malli sisältää: tavoitefunktion, jonka optimaalinen arvo (maksimi tai minimi) on löydettävä; rajoitukset lineaaristen yhtälöiden tai epäyhtälöiden muodossa; vaatimus muuttujien ei-negatiivisuudesta.
IN yleinen näkemys malli on kirjoitettu seuraavasti:
tavoitefunktio
(1.1) rajoituksin
(1.2) ei-negatiivisuusvaatimukset
(1.3) missä x j– muuttujat (tuntematon);
- lineaarisen ohjelmointiongelman kertoimet.
Ongelmana on löytää funktion (1.1) optimaalinen arvo rajoitusten (1.2) ja (1.3) alaisena.
Rajoitusjärjestelmää (1.2) kutsutaan ongelman toiminnallisiksi rajoituksiksi ja rajoituksia (1.3) suoriksi.
Vektoria, joka täyttää rajoitukset (1.2) ja (1.3), kutsutaan lineaarisen ohjelmointitehtävän hyväksyttäväksi ratkaisuksi (suunnitelmaksi). Suunnitelmaa, jossa funktio (1.1) saavuttaa maksimi (minimi) arvonsa, kutsutaan optimaaliseksi.
1.2. Simplex menetelmä lineaarisen ohjelmoinnin ongelmien ratkaisemiseen
Simpleksimenetelmän kehitti ja käytti ensimmäisen kerran ongelmien ratkaisemiseen vuonna 1947 amerikkalainen matemaatikko J. Danzig.
Kaksiulotteiset lineaariset ohjelmointitehtävät ratkaistaan graafisesti. Tapauksessa N=3 voidaan tarkastella kolmiulotteista avaruutta ja tavoitefunktio saavuttaa optimaalisen arvonsa yhdessä monitahoisen kärjestä.
Hyväksyttävä ratkaisu (hyväksyttävä suunnitelma) annettuun LP-ongelmaan vakiomuotoinen, on järjestetty numerosarja (x1, x2, ..., xn), jotka täyttävät rajoitukset; se on piste n-ulotteisessa avaruudessa.
Hyväksyttyjen ratkaisujen joukko muodostaa LP-ongelman hyväksyttävien ratkaisujen alueen (ADS). ODR on kupera monikulmio.
Yleisesti, kun ongelmaan liittyy N-tuntematonta, voidaan sanoa, että rajaehtojärjestelmän määrittelemää toteutettavissa olevien ratkaisujen aluetta edustaa kupera monitahoinen n-ulotteisessa avaruudessa ja tavoitefunktion optimaalinen arvo saavutetaan yhdellä tai useampia pisteitä.
Perusratkaisu on ratkaisu, jossa kaikki vapaat muuttujat ovat yhtä suuria kuin nolla.
Tukiratkaisu on ei-negatiivinen perusratkaisu. Tukiratkaisu voi olla rappeutumaton ja rappeutunut. Vertailuratkaisua kutsutaan ei-degeneroituneeksi, jos sen nollasta poikkeavien koordinaattien määrä on yhtä suuri kuin järjestelmän arvo, muuten se on rappeutunut.
Hyväksyttävää ratkaisua, jossa tavoitefunktio saavuttaa ääriarvonsa, kutsutaan optimaaliseksi ja merkitään 
.
Näitä ongelmia on erittäin vaikea ratkaista graafisesti, kun muuttujia on enemmän kuin 3. On olemassa universaali menetelmä lineaarisen ohjelmoinnin ongelmien ratkaiseminen, jota kutsutaan simpleksimenetelmäksi.
Simplex-menetelmä on universaali menetelmä LP-ongelmien ratkaiseminen, joka on iteratiivinen prosessi, joka alkaa yhdestä ratkaisusta ja etsii parasta vaihtoehtoa, liikkuu toteuttamiskelpoisten ratkaisujen alueen kulmapisteitä pitkin, kunnes se saavuttaa optimaalisen arvon.
Sitä voidaan käyttää minkä tahansa lineaarisen ohjelmoinnin ongelman ratkaisemiseen.
Simplex-menetelmä perustuu ajatukseen tuloksena olevan ratkaisun peräkkäisestä parantamisesta.
Simpleksimenetelmän geometrinen merkitys on peräkkäinen siirtyminen rajoituspolyhedrin yhdestä kärjestä viereiseen, jossa tavoitefunktio saa parhaan (tai esim. vähintään, ei pahin) arvo, kunnes optimaalinen ratkaisu löytyy - kärki, jossa tavoitefunktion optimaalinen arvo saavutetaan (jos ongelmalla on lopullinen optimi).
Näin ollen rajoitusjärjestelmän vähentäminen kanoninen muoto(kaikilla toiminnallisilla rajoituksilla on yhtäläisyyksiä), löytää mikä tahansa tämän järjestelmän perusratkaisu huolehtien vain sen löytämisestä mahdollisimman yksinkertaisesti. Jos ensimmäinen löydetty perusratkaisu osoittautuu toteuttamiskelpoiseksi, sen optimaalisuus tarkistetaan. Jos se ei ole optimaalinen, siirrytään toiseen, välttämättä hyväksyttävään perusratkaisuun. Simpleksimenetelmä takaa sen, että tällä uudella ratkaisulla tavoitefunktio, jos se ei saavuta optimia, lähestyy sitä (tai ei ainakaan poistu siitä). Samaa tehdään uudella toteuttamiskelpoisella perusratkaisulla, kunnes löydetään optimaalinen ratkaisu.
Simplex-menetelmän soveltamisprosessi sisältää sen kolmen pääelementin toteuttamisen:
menetelmän minkä tahansa alkuperäisen toteuttamiskelpoisen perusratkaisun määrittämiseksi ongelmaan;
parhaaseen (tarkemmin, ei huonompaan) ratkaisuun siirtymisen sääntö;
kriteeri löydetyn ratkaisun optimaalisuuden tarkistamiseksi.
Simpleksimenetelmä sisältää useita vaiheita ja se voidaan muotoilla selkeän algoritmin muodossa (selkeä ohje peräkkäisten toimintojen suorittamiseen). Näin voit ohjelmoida ja toteuttaa sen onnistuneesti tietokoneella. Tehtävät kanssa pieni määrä muuttujat ja rajoitteet voidaan ratkaista simplex menetelmä käsin.
6.1. Johdanto
Optimointi. Osa 1
Optimointimenetelmien avulla voit valita paras vaihtoehto malleja kaikilta mahdollisia vaihtoehtoja. IN viime vuosina nämä menetelmät on annettu suurta huomiota, ja sen seurauksena on kehitetty useita erittäin tehokkaita algoritmeja paras vaihtoehto suunnittelee tietokoneella. Tässä luvussa hahmotellaan optimointiteorian perusteet, tarkastellaan optimaalisten ratkaisujen algoritmien rakentamisen periaatteita, kuvataan tunnetuimpia algoritmeja sekä analysoidaan niiden etuja ja haittoja.
6.2.Optimointiteorian perusteet
Termi "optimointi" kirjallisuudessa viittaa prosessiin tai toimintosarjaan, jonka avulla voidaan saada jalostettu ratkaisu. Vaikka optimoinnin perimmäisenä tavoitteena on löytää paras eli "optimaalinen" ratkaisu, on yleensä tyytyä parantamiseen. tunnettuja ratkaisuja, eikä saattamalla niitä täydellisyyteen. Siksi optimointi ymmärretään pikemminkin haluksi täydellisyyteen, jota ei välttämättä saavuteta.
Kun otetaan huomioon jokin mielivaltainen järjestelmä, jota kuvaa m yhtälö, jossa on n tuntematonta, voimme erottaa kolme päätyyppiä ongelmia. Jos m = n, ongelmaa kutsutaan algebraksi. Tällä ongelmalla on yleensä yksi ratkaisu. Jos m>n, niin ongelma on ylimäärätty, eikä sillä yleensä ole ratkaisua. Lopuksi m
Ennen kuin alamme keskustella optimointikysymyksistä, esittelemme useita määritelmiä.
Suunnitteluparametrit
Tämä termi tarkoittaa riippumattomia muuttujaparametreja, jotka määrittävät täysin ja yksiselitteisesti ratkaistavan suunnitteluongelman. Suunnitteluparametrit ovat tuntemattomia suureita, joiden arvot lasketaan optimointiprosessin aikana. Kaikki perus- tai johdetut suureet, jotka kuvaavat järjestelmää kvantitatiivisesti, voivat toimia suunnitteluparametreina. Joten nämä voivat olla tuntemattomia pituuden, massan, ajan, lämpötilan arvoja. Suunnitteluparametrien määrä kuvaa tietyn suunnitteluongelman monimutkaisuuden astetta. Yleensä suunnitteluparametrien lukumäärä merkitään n:llä ja itse suunnitteluparametrit x:llä vastaavilla indekseillä. Siten tämän ongelman n suunnitteluparametria merkitään
X1, x2, x3,...,xn.
Objektiivinen toiminto
Se on lauseke, jonka arvon insinööri pyrkii tekemään maksimin tai minimin. Tavoitefunktio mahdollistaa kahden kvantitatiivisen vertailun vaihtoehtoisia ratkaisuja. Matemaattisesta näkökulmasta kohdefunktio kuvaa jotakin (n+1)-ulotteista pintaa. Sen arvo määräytyy suunnitteluparametrien mukaan
M = M(x 1, x 2,..., x n).
Esimerkkejä insinööritoiminnassa usein esiintyvistä tavoitefunktioista ovat hinta, paino, lujuus, mitat, tehokkuus. Jos suunnitteluparametreja on vain yksi, tavoitefunktio voidaan esittää käyrällä tasolla (kuva 6.1). Jos suunnitteluparametreja on kaksi, kohdefunktio kuvataan pintana kolmiulotteisessa avaruudessa (kuva 6.2). Kolmella tai useammalla suunnitteluparametrilla kohdefunktion määrittelemiä pintoja kutsutaan hyperpinnoiksi, eikä niitä voi kuvata.
avioliitto tavallisin keinoin. Tavoitefunktion pinnan topologisilla ominaisuuksilla on suuri rooli optimointiprosessissa, koska tehokkaimman algoritmin valinta riippuu niistä.
Tavoitefunktio voi joissain tapauksissa olla mitä odottamattomimmissa muodoissa. Sitä ei esimerkiksi aina ole mahdollista ilmaista
Kuva 1. Yksiulotteinen tavoitefunktio.
Kuva 6.2 Kaksiulotteinen objektiivifunktio.
suljettu matemaattinen muoto, muissa tapauksissa voi
edustavat paloittain sileää funktiota. Tavoitefunktion määrittäminen voi joskus vaatia teknisten tietojen taulukon (esimerkiksi vesihöyryn tilataulukon) tai kokeen. Joissakin tapauksissa suunnitteluparametrit ottavat vain kokonaislukuja. Esimerkkinä voisi olla hammaspyörän hampaiden lukumäärä tai laipan pulttien lukumäärä. Joskus suunnitteluparametreilla on vain kaksi merkitystä - kyllä tai ei. Laadulliset parametrit, kuten tuotteen ostaneen ostajan kokema tyytyväisyys, luotettavuus, estetiikka, on vaikea ottaa huomioon optimointiprosessissa, koska niitä on lähes mahdotonta luonnehtia kvantitatiivisesti. Riippumatta siitä, miten tavoitefunktio esitetään, sen on kuitenkin oltava suunnitteluparametrien yksiselitteinen funktio.
Useat optimointiongelmat edellyttävät useamman kuin yhden tavoitefunktion käyttöönottoa. Joskus toinen niistä voi osoittautua yhteensopimattomaksi toisen kanssa. Esimerkki on lentokonesuunnittelu, jossa vaaditaan samanaikaisesti maksimilujuutta, vähimmäispainoa ja vähimmäiskustannuksia. Tällaisissa tapauksissa suunnittelijan on otettava käyttöön prioriteettijärjestelmä ja osoitettava jokaiselle tavoitefunktiolle tietty dimensioton kertoja. Tämän seurauksena näkyviin tulee "kompromissifunktio", joka mahdollistaa yhden yhdistetyn tavoitefunktion käytön optimointiprosessin aikana.
Löytää minimi ja maksimi
Jotkut optimointialgoritmit on suunniteltu löytämään maksimi, toiset - etsimään minimi. Ratkaistavan äärimmäisen ongelman tyypistä riippumatta voit kuitenkin käyttää samaa algoritmia, koska minimointitehtävä voidaan helposti muuttaa maksimihakutehtäväksi kääntämällä tavoitefunktion etumerkki. Tämä tekniikka on kuvattu kuvassa 6.3.
Suunnittelutila
Tämä on kaikkien n suunnitteluparametrien määrittämän alueen nimi. Suunnittelutila ei ole niin suuri kuin miltä se saattaa näyttää, koska sitä rajoittaa yleensä useita
olosuhteet, jotka liittyvät ongelman fyysiseen olemukseen. Rajoitukset voivat olla niin voimakkaita, että ongelmalla ei ole mitään
Kuva 6.3. Kohdefunktion etumerkin muuttaminen päinvastaiseksi
maksimitehtävä muuttuu minimitehtäväksi.
tyydyttävä ratkaisu. Rajoitukset jaetaan kahteen ryhmään: rajoitukset - tasa-arvo ja rajoitteet - epätasa-arvo.
Rajoitukset – Tasa-arvot
Rajoitukset - yhtäläisyydet - ovat suunnitteluparametrien välisiä riippuvuuksia, jotka on otettava huomioon ratkaisua etsittäessä. Ne heijastavat luonnonlakeja, taloutta, lakia, vallitsevia makuja ja saatavuutta tarvittavat materiaalit. Rajoitusten lukumäärä - yhtäläisyydet voivat olla mitä tahansa. Ne näyttävät
C 1 (x 1, x 2,...,x n) = 0,
C 2 (x 1, x 2,..., x n) = 0,
..................
Cj(x1, x2,...,xn) = 0.
Jos jokin näistä suhteista voidaan ratkaista jonkin suunnitteluparametrin suhteen, tämä sallii tämän parametrin sulkemisen pois optimointiprosessista. Tämä vähentää suunnittelutilan mittojen määrää ja yksinkertaistaa ongelman ratkaisua.
Rajoitukset - epätasa-arvo
Tämä on erityinen rajoitus, joka ilmaistaan eriarvoisuuksilla. Yleensä niitä voi olla niin monta kuin haluat, ja niillä kaikilla on muoto
z 1 r 1 (x 1 , x 2 ,..., x n) Z 1
z 2 r 2 (x 1 , x 2 ,..., x n) Z 2
.......................
z k r k (x 1 , x 2 ,..., x n) Z k
On huomattava, että hyvin usein rajoitusten vuoksi tavoitefunktion optimaalinen arvo ei saavuteta siellä, missä sen pinnalla on nollagradientti. Usein paras ratkaisu vastaa yhtä suunnittelualueen rajoista.
Paikallinen optimi
Tämä on sen pisteen nimi suunnitteluavaruudessa, jossa tavoitefunktiolla on korkein arvo verrattuna sen arvoihin kaikissa muissa pisteissä sen välittömässä läheisyydessä.
Kuva 6.4. Mielivaltaisella tavoitefunktiolla voi olla useita
paikallinen optimi.
Kuvassa Kuva 6.4 esittää yksiulotteisen tavoitefunktion, jolla on kaksi paikallista optimia. Usein suunnittelutila sisältää monia paikallisia optimeja, ja on varottava, ettei ensimmäistä erehdy optimaaliseksi ratkaisuksi ongelmaan.
Globaali optimi
Globaali optimi on optimaalinen ratkaisu koko suunnittelutilalle. Se on parempi kuin kaikki muut paikallista optimia vastaavat ratkaisut, ja sitä suunnittelija etsii. On mahdollista, että sisällä on useita yhtä suuria globaaleja optimeja eri osia suunnittelutilaa. Optimointiongelman asettamista havainnollistaa parhaiten esimerkki.
Esimerkki 6.1
Oletetaan, että sinun on suunniteltava suorakaiteen muotoinen säiliö, jonka tilavuus on 1 m, ja joka on tarkoitettu pakkaamattoman kuidun kuljettamiseen. On toivottavaa, että tällaisten säiliöiden valmistukseen käytetään mahdollisimman vähän materiaalia (olettaen, että seinämän paksuus on vakio, tämä tarkoittaa, että pinta-alan tulisi olla minimaalinen), koska se tulee halvemmaksi. Jotta kontti olisi kätevästi nostettavissa trukilla, sen leveyden tulee olla vähintään 1,5 m.
Muotoilkaamme tämä ongelma optimointialgoritmin soveltamiseen sopivassa muodossa.
Suunnitteluparametrit: x 1, x 2, x 3.
Objektifunktio (joka on minimoitava) on säiliön sivupinnan pinta-ala:
A=2(x 1 x 2 + x 2 x 3 + x 1 x 3), m2.
Rajoitus - tasa-arvo:
Tilavuus = x 1 x 2 x 3 = 1 m3.
Rajoitus - epätasa-arvo:
Lineaarisen ohjelmoinnin ongelmia
Lineaarinen ohjelmointi (LP) on yksi matemaattisen ohjelmoinnin haaroista - tieteenala, joka tutkii äärimmäisiä (optimointi)ongelmia ja kehittää menetelmiä niiden ratkaisemiseksi.
Optimointi ongelma- Tämä matemaattinen ongelma, joka koostuu tavoitefunktion optimaalisen (eli maksimi- tai minimiarvon) löytämisestä, ja muuttujien arvojen tulee kuulua tiettyyn hyväksyttävien arvojen (APV) alueelle.
Yleensä matemaattisen ohjelmoinnin äärimmäisen ongelman muotoilussa määritetään suurin tai pienin arvo kutsuttu toiminto kohdetoiminto, ehdoin (rajoituksin) , missä ja – määritettyjä toimintoja, a ovat vakioarvoja. Tässä tapauksessa yhtäläisyyksien ja epäyhtälöiden muodossa olevat rajoitukset määräävät sallittujen ratkaisujen (ADS) joukon (alueen), ja niitä kutsutaan ns. suunnitteluparametreja.
Funktioiden tyypistä riippuen matemaattiset ohjelmointiongelmat jaetaan useisiin luokkiin (lineaarinen, epälineaarinen, konveksi, kokonaisluku, stokastinen, dynaaminen ohjelmointi jne.).
IN yleinen näkemys LP-ongelma on seuraava näkymä:
, (5.1)
, , (5.2)
, 
, (5.3)
jossa , , annetaan vakioarvot.
Funktiota (5.1) kutsutaan tavoitefunktioksi; järjestelmät (5.2), (5.3) – rajoitusjärjestelmä; ehto (5.4) – suunnitteluparametrien ei-negatiivisuuden ehto.
Rajoitukset (5.2), (5.3) ja (5.4) täyttäviä suunnitteluparametreja kutsutaan ns. hyväksyttävä ratkaisu tai suunnitelma.
Optimaalinen ratkaisu tai optimaalinen suunnitelma LP-tehtävää kutsutaan hyväksyttäväksi ratkaisuksi, jossa tavoitefunktio (5.1) saa optimaalisen (maksimi- tai minimiarvon).
Vakiotehtävä LP on tavoitefunktion (5.1) maksimi (minimi) arvon löytäminen ehdoissa (5.2) ja (5.4), missä , , ts. ne. rajoitukset vain epäyhtälöiden muodossa (5.2) ja kaikki suunnitteluparametrit täyttävät ei-negatiivisuuden ehdon, eikä yhtäläisyyksien muodossa ole ehtoja:
,
, , (5.5)
.
Kanoninen (pää)tehtävä LP on tavoitefunktion (5.1) maksimi (minimi) arvon löytämisen ongelma ehdoissa (5.3) ja (5.4), missä , , ts. ne. rajoitukset vain yhtälöiden muodossa (5.3) ja kaikki suunnitteluparametrit täyttävät ei-negatiivisuuden ehdon, eikä epäyhtälöiden muodossa ole ehtoja:
,
.
Kanoninen LP-tehtävä voidaan kirjoittaa myös matriisi- ja vektorimuodossa.
Matriisi muoto kanoninen ongelma LP:llä on seuraava muoto:
Kanonisen LP-ongelman vektorimuoto.
Tavoitefunktio on matemaattinen esitys optimaalisuuskriteerin riippuvuudesta halutuista muuttujista.2. Funktion gradientti.
Vektori, jonka komponentit ovat osittaisten derivaattojen arvoja, eli vektori
kutsutaan pisteessä lasketun funktion gradienttiksi.
3. Yleinen lineaarisen ohjelmoinnin ongelma.
Yleisen lineaarisen ohjelmoinnin ongelman tavallinen matemaattinen muotoilu näyttää tältä: sinun on löydettävä tehokkuusindikaattorin (objektiivisen funktion) ääriarvo.
(liuoselementtien lineaarinen funktio) liuoselementeille asetetuissa lineaarisissa rajoittavissa olosuhteissa:
missä on annettu numerot. 
4. Normaali LP-ongelma.
Vakiomuodossa lineaarinen ohjelmointitehtävä on lineaarisen tavoitefunktion maksimi- (minimi)ongelma. Sen rajoitusjärjestelmä koostuu seuraavista: lineaariset epätasa-arvot kuten"<= » или « >= " Kaikki tehtävämuuttujat ei-negatiivinen.
Mikä tahansa lineaarinen ohjelmointiongelma voidaan muotoilla vakiomuotoinen.
Minimiongelman muuntaminen maksimiongelmaksi sekä sen varmistaminen, että muuttujat eivät ole negatiivisia, tehdään samalla tavalla kuin ennenkin. Mikä tahansa tasa-arvo rajoitusjärjestelmässä vastaa keskenään vastakkaisten epätasa-arvojen järjestelmää:
On muitakin tapoja muuttaa tasa-arvojärjestelmä epätasa-arvojärjestelmäksi, ts.
Jokainen lineaarisen ohjelmoinnin ongelma voidaan muotoilla vakiomuotoon.
Vastausvaihtoehto 2:
Normaali LP-ongelma.
IN tai matriisimerkinnällä missä on kerroinmatriisi. Vektoria kutsutaan lineaarisen muodon kertoimien vektoriksi, rajoitusten vektoriksi. 5. Kanoninen lp-ongelma. kanoninen muoto ongelma on jonkin lineaarisen funktion maksimi (minimi) ongelma F 1 , sen rajoitusjärjestelmä koostuu vain yhtälöistä (yhtälöistä). Samaan aikaan tehtävämuuttujat 2 X , X , ..., X
|
| |
n
ovat ei-negatiivisia:
Mikä tahansa lineaarinen ohjelmointiongelma voidaan muuntaa kanoniseen muotoon.
On muitakin tapoja muuttaa tasa-arvojärjestelmä epätasa-arvojärjestelmäksi, ts.
Lyhyt merkintä kanonisesta LP-ongelmasta:
X = (x1, x2, ..., xn), C = (c1, c2, ..., cn).
Kanoninen LP-ongelma.
tai matriisimerkinnällä, 
6. Symmetrinen ja epäsymmetrinen kaksoistehtävä. 
Kaksoislineaarinen ohjelmointiongelma. Harkitse LP-ongelmaa 
(1) tai matriisimerkinnässä (2) Tehtävää dual to (1) (kaksoistehtävä) kutsutaan LP-tehtäväksi muodon muuttujissa
Tehtävän (1) matriisissa on yhtä monta muuttujaa kuin on rivejä. Kohdan (3) rajoitusmatriisi on kuljetettu matriisi. Kohteen (3) rajoitusten oikean puolen vektori toimii maksimoidun lineaarisen muodon kertoimien vektorina kohdassa (1), ja epäyhtälöiden merkit muuttuvat yhtäläisiksi. Päinvastoin, (3):n tavoitefunktio on lineaarinen muoto, jonka kertoimet määritellään tehtävän (1) rajoitusten oikean puolen vektorilla, kun taas maksimointi muuttuu minimointiin. Ei-negatiivisuuden ehto on asetettu kaksoismuuttujille. Tehtävää (1), toisin kuin kaksoistehtävä (3), kutsutaan suoraksi.. Kaksinaisuuslause.
Jos kaksoistehtävä (2), (4) hyväksytään, niillä molemmilla on ratkaisu ja sama arvo
Symmetrinen kaksoisongelma
Useat duaaliset lineaariset ohjelmointiongelmat ovat kaksoissymmetrisiä tehtäviä, joissa sekä alkuperäisen että kaksoistehtävän rajoitusjärjestelmä määritellään epäyhtälöillä ja ei-negatiivisuuden ehto asetetaan kaksoismuuttujille.<функция>, <система ограничений>, <опции>);
Voit löytää tavoitefunktion maksimin käyttämällä maximize-funktiota, jonka muoto on maximize(
> Tässä tapauksessa on kätevää määrittää muuttujien ei-negatiivisuuden ehto käyttämällä NONNEGATIVE-vaihtoehtoa.
optimi:=maximize(f,syst_ogr,NONNEGATIVE); x Käytä subs-komentoa, jonka avulla voit korvata muuttujien arvoja x 1 ja 2 per toiminto.
> f
fmax:=subs(x1=83/17,x2=19/17,f);
> Käytä evalf-funktiota ilmaistaksesi vastauksen reaalilukuna, jossa on 4 merkitsevää numeroa.
fmax:=evalf(fmax,4);
LP-ongelman ratkaisuun voit tutustua ilman selitystä liitteessä.
Optimointiongelmien ratkaiseminen SimplexWin-erikoispaketissa. Http://www.Simplexwin.Narod.Ru/
Tämä ohjelma on suunniteltu ratkaisemaan lineaarisen ohjelmoinnin ongelmia simplex-menetelmällä. Tehtävä x 1 . Etsi muuttuvia arvoja x Ja
2, jossa
rajoitusten alla:
Työjärjestys
Käynnistä SimplexWin-ohjelma ja aseta tarvittava rajoitusmatriisin koko valitsemalla valikosta Asetukset – Matriisin koko (Kuva 13). Riisi. 13
. Matriisin koon määrittäminen. Syötä tiedot (kuva 14). Jos ongelmaa ei esitetä kanonisessa muodossa, lisämuuttujat ja keinotekoiset pohjat
(sekä vastaavat tavoitefunktiokertoimet) lisätään automaattisesti. Kuva 14
. Tietojen syöttö.
II. Optimaalisen suunnitelman ja tavoitefunktion optimaalisen arvon löytäminen. Riisi. 15
Napsauta Tulokset-lomakkeessa Tulos-painiketta, jonka avulla voit ratkaista ongelman automaattinen tila ja näyttää uusimmat simplex pöytä ja tulos (kuva 16).
Riisi. 16. Ongelman ratkaiseminen.
Optimointiongelmien ratkaiseminenExcel
Katsotaanpa esimerkkiä seuraavan lineaarisen ohjelmointiongelman löytämisestä.
Tämä ohjelma on suunniteltu ratkaisemaan lineaarisen ohjelmoinnin ongelmia simplex-menetelmällä. Tehtävä x 1 . Etsi muuttuvia arvoja x Ja
2, jossa
rajoitusten alla:
I. Alkutietojen rekisteröinti.
Luo ruutulomake tehtävän ehtojen (muuttujat, tavoitefunktio, rajoitteet) syöttämiseksi ja syötä siihen alkutiedot (tavoitefunktion kertoimet, muuttujien kertoimet rajoitteissa, rajoitteiden oikeat puolet) (kuva 17). ).
Riisi. 17. Tehtävän näyttömuoto (kohdistin solussa D6).
Kommentti: Kuvan näyttömuodossa. 17 Jokaiselle tehtävän muuttujalle ja kertoimelle on määritetty erityinen solu Excelissä. Joten esimerkiksi tehtävämuuttujat vastaavat soluja B3 ( 
), C3 ( 
), tavoitefunktion kertoimet vastaavat soluja B6 ( 
), C6 ( 
), rajoitusten oikeat puolet vastaavat soluja F10 ( 
), F11 ( 
),F12 ( 
), jne.
Syötä matemaattisen mallin riippuvuudet näyttölomakkeeseen, ts. Syötä tavoitefunktion laskentakaava ja rajoitusten vasemmanpuoleisten arvojen laskentakaava.
Tehtävän ehtojen mukaan tavoitefunktion arvo määräytyy lausekkeen avulla 
. Excelin vastaavien solujen merkintöjen avulla tavoitefunktion laskentakaava voidaan kirjoittaa muodossa tuotteiden summa kukin tehtävämuuttujien arvoille (B3, C3) varatuista soluista kohdefunktion kertoimille allokoituihin vastaaviin soluihin (B6, C6).
Voit määrittää tavoitefunktion riippuvuuskaavan seuraavasti: :
– aseta kohdistin soluun D6;
– soittoikkuna Ohjattu toiminto - Vaihe 1/2 painamalla painiketta 
päällä vakio paneeli työkalut;
-ikkunassa Toiminto valitse toiminto SUMMATUOTE;
- avautuvassa ikkunassa SUMMATUOTE rivittää Taulukko 1 syötä lauseke B$3:C$3, ja linjalle Taulukko 2– ilmaisu B6: C6;
– paina painiketta OK.
Riisi. 18. CF:n laskentakaavan syöttäminen Function Wizard -ikkunaan.
Kun olet syöttänyt solut riveihin Taulukko 1 Ja Taulukko 2 ikkunassa SUMMATUOTE tulee näkyviin numeerisia arvoja syötetyt taulukot (kuva 18), ja syötetyllä kaavalla laskettu nykyinen arvo, eli 0 (koska kaavan syöttöhetkellä tehtävämuuttujien arvot ovat nolla) ilmestyvät näyttölomakkeeseen ( kuva 19).
Kommentti: $-symboli ennen rivinumeroa tarkoittaa, että kun kopioit tämän kaavan muihin paikkoihin Excel-laskentataulukossa, rivinumero 3 ei muutu. Symboli : tarkoittaa, että kaava käyttää kaikkia soluja kaksoispisteen vasemmalla ja oikealla puolella olevien solujen välillä.
Ongelmarajoitteiden vasemmalla puolella ovat tuotteiden summa jokainen ongelmamuuttujien arvoille (B3, C3) varattu solu vastaavaan soluun, joka on varattu tietyn rajoitteen kertoimille (B10, C10 – 1. rajoitus; B11, C11 – 2. rajoite; B12, C12 – 3. rajoitus).
Kaavat, jotka määrittävät ongelmarajoitusten vasemman puolen, eroavat toisistaan ja kohdesolun kaavasta D6 vain rivin numero toisessa taulukossa. Tämä luku määräytyy sen rivin mukaan, jolle rajoitus on kirjoitettu näyttömuodossa. Siksi riippuvuuksien asettamiseksi rajoitteen vasemmille osille riittää, että kaava kopioidaan kohdesolusta rajoitusten vasenten osien soluihin.
Voit laskea rajoitusten vasemman puolen arvot seuraavasti:
– aseta kohdistin soluun D6 ja kopioi solun sisältö leikepöydälle (käyttäen Ctrl+C-näppäimiä);
– aseta kohdistin vuorotellen kunkin rajoituksen vasemman reunan kenttiin, eli D10 ,D11 , D12 , ja liitä puskurin sisältö näihin kenttiin (käyttäen Ctrl+V-näppäimiä) (tässä tapauksessa kaavan toisen taulukon solujen määrä muuttuu sen rivin numeroksi, johon liittäminen on tehty. puskuri).
Kun olet syöttänyt ruudulle kenttiin D10 ,D11 , D12 0 (nolla-arvo) tulee näkyviin (kuva 19).
Riisi. 19. Tehtävän näyttömuoto veden jälkeen
kaikki tarvittavat kaavat.
Tarkista, että kaavat on syötetty oikein.
Voit tehdä tämän seuraavasti:
- tee se yksitellen kaksoisnapauta hiiren vasen painike soluissa, joissa on kaava, kun taas kaavassa käytetyt solut korostetaan ruudulla kehyksellä (Kuva 20 ja Kuva 21).
Riisi. 20
kaavat kohdesoluun D6.
Riisi. 20. Oikean lisäyksen tarkistaminen
kaavat solussa D10 rajoitusten vasemmalle puolelle.
Määritä tavoitefunktio ja syötä rajoitukset ikkunaan Ratkaisun löytäminen(Kuva 21).
Voit tehdä tämän seuraavasti:
– aseta kohdistin soluun D6;
– soittoikkuna Ratkaisun löytäminen valitsemalla työkalupalkista Data - Ratkaisun löytäminen;
– aseta kohdistin kenttään Aseta kohdesolu;
– syötä kohdesolun osoite $ D $ 6 tai napsauta hiiren vasemmalla painikkeella kohdesolua näyttölomakkeessa, mikä vastaa osoitteen syöttämistä näppäimistöltä;
– osoita kohdefunktion optimoinnin suunta napsauttamalla kerran hiiren vasemmalla painikkeella valintapainiketta enimmäisarvo;
-ikkunassa Ratkaisujen löytäminen kentällä Solujen vaihtaminen syötä solut muuttuvilla arvoilla $B$3:$C$3, valitsemalla ne näyttölomakkeesta pitäen samalla hiiren vasenta painiketta painettuna;
Riisi. 21. Ikkuna Etsi ratkaisua.
– paina painiketta Lisätä;
– valitse tehtävän ehtojen mukaisesti tarvittava merkki merkkikentästä, esim. 1 rajoitukselle tämä on merkki 
;
- kentällä Rajoitus syötä esimerkiksi kyseisen rajoitteen oikean puolen solun osoite $10 F$;
– muodostaa samalla tavalla suhteita muiden rajoitusten oikean ja vasemman osan välille ( $D$11
1 dollaria1
,
$D$12
1 dollaria2)
;
– vahvista kaikkien lueteltujen ehtojen syöttäminen painamalla painiketta OK(Kuva 22 ja kuva 23).
Riisi. 22. Ehdon lisääminen.
Kommentti: Jos tehtäväehtoa syötettäessä on tarvetta muuttaa tai poistaa syötettyjä rajoituksia, se voidaan tehdä napsauttamalla painikkeita Muuttaa tai Poistaa.
Järjestelmän toimintaa ja sen käyttäytymistä ei luonnehdi ainoastaan tavoitteen saavuttamisen tosiasian toteaminen, vaan myös sen saavuttamisen aste, joka määritetään tavoitefunktion avulla.
Objektiivinen toiminto – on järjestelmän yleinen indikaattori, joka kuvaa sitä, missä määrin järjestelmä saavuttaa tavoitteensa. Kohdefunktion muodostaminen on yksi tärkeimmät tehtävät järjestelmää suunniteltaessa. Ei kuitenkaan ole olemassa yleistä teoriaa tavoitefunktioiden rakentamiselle, on vain joitain suosituksia.
Tavoitefunktio kootaan teknisten eritelmien ohjeiden mukaisesti optimointikriteeristä analysoimalla järjestelmän ulkoiset parametrit ja niitä koskevat rajoitukset.
Kohdefunktion on oltava merkittävästi riippuvainen ulkoisista parametreista tai niiden osasta. Muuten tämän tavoitefunktion optimoinnissa ei ole järkeä. Tavoitefunktio edustaa vektoria in m-järjestelmän ulkoisten parametrien ulottuvuusavaruus
Yleensä tavoitefunktio määritellään skalaarimuodossa.
Käytetään seuraavia neljää tavoitefunktion muotoa.
1. Yleisimmin käytetty kohdefunktio on yksi ulkoinen parametri
Tässä tapauksessa tavoitefunktio on yksinkertaisesti yhtä suuri kuin jokin ulkoisista parametreista tai sen käänteisarvo
Kaikki muut ( m– 1) ulkoiset parametrit muunnetaan rajoitusjärjestelmäksi.
Annettujen tyyppien tavoitefunktion fyysinen merkitys on, että mitä suurempi (tai pienempi) parametri on y i, sitä parempi, kun muut asiat ovat samanlaisia tämä järjestelmä, ja muiden ehtojen yhtäläisyys ymmärretään jäljelle jäävien rajoitusten merkityksessä ulkoiset parametrit. Tyypillisiä ongelmia tavoitefunktion pelkistetyssä muodossa: järjestelmän optimointi luotettavuuden kannalta ( y = P(t)), melunsieto, kustannukset ja muut ulkoiset parametrit. Tällaisella tavoitefunktiolla on selkeä fyysinen (tekninen tai taloudellinen) merkitys, se kuvaa objektiivisesti järjestelmää ja siksi sitä käytetään usein. Eli tässä tapauksessa kohdefunktio on järjestelmän ulkoinen parametri. Tätä kutsutaan järjestelmän tavoitefunktioksi. Näitä voivat olla: tarkkuus, nopeus, aika, hinta, luotettavuus, paino, mitat, jonkinlainen tekninen indikaattori jne.
2. Tavoitefunktion toinen muoto on samankokoisten parametrien summa tai näiden parametrien funktioiden summa
Tämä muoto on tyypillinen optimoitaessa taloudellisten kriteerien, monimutkaisuuskriteerien jne. mukaan.
Esimerkiksi minimoitaessa järjestelmän vuosittaisia alenevia kustannuksia tavoitefunktio on kahden ulkoisen parametrin summa: vuosittaiset käyttökustannukset ja järjestelmän takaisinmaksuaikaan liittyvät pääomakustannukset. Tässä tapauksessa jokainen näistä järjestelmän ulkoisista parametreista on monimutkainen toiminto sen sisäiset (löydyttävät) parametrit.
Kompleksisuuskriteeriin perustuvien optimointitehtävien tavoitefunktioilla on myös toinen muoto, koska ne esitetään järjestelmän yksittäisten osajärjestelmien tai lohkojen monimutkaisuuden summana.
3. Tavoitefunktion kolmas muoto - järjestysmuoto - on järjestetty joukko ensimmäisen muodon tavoitefunktioita prioriteeteineen
Ensimmäinen tavoitefunktio on tärkein, viimeinen tavoitefunktio on vähiten tärkeä.
Tietyssä tapauksessa tämän tyypin tavoitefunktio kirjoitetaan seuraavasti:
Esimerkki sijoituksesta on (esimerkiksi) seuraava tavoitefunktioiden järjestys: tarkkuus, luotettavuus, hinta. Kolmannen muodon tavoitefunktion merkitys on seuraava. Tärkein - listalla ensimmäinen - tunnustetaan joillekin i-järjestelmäparametri - y i(esim. tarkkuus). Jos jollain järjestelmällä on tämä i Parametri on suurempi kuin kaikkien muiden järjestelmien, joten muiden parametrien arvoista riippumatta (niin kauan kuin ne täyttävät rajoitukset), tätä järjestelmää pidetään parhaana. Sitten toisen parametrin mukaan jne.
Optimointimenettely on tässä tapauksessa pääsääntöisesti monivaiheinen. Tällaista optimointia sovelletaan usein tietämättään teknisissä järjestelmissä. Ensin valitaan järjestelmä, jolla on paras tarkkuus, jos useilla järjestelmillä on sama tarkkuus, valitaan luotettavampi ja sitten valitaan halvempi. Jokaisessa optimointivaiheessa käytetään vain yhtä kriteeriä, mikä ei ole ristiriidassa konseptin kanssa järjestelmällinen lähestymistapa(optimointi yhden kriteerin perusteella, katso alla).
4. Tavoitefunktion neljäs - yleisin - muoto on mielivaltainen riippuvuus kaikista heterogeenisistä ulkoisista parametreista tai osasta (mutta vähintään kahdesta)
Tällöin heterogeeniset parametrit muunnetaan dimensiottomiksi (tai yksiulotteisiksi) ja tavoitefunktio muodostetaan tiettynä koostumuksena (esimerkiksi aritmeettisena keskiarvona) saaduista dimensiottomista indikaattoreista.
Yksi neljännen muodon tavoitefunktio voidaan saada kolmannen muodon tavoitefunktioista kertomalla ne painotuskertoimilla ja sitä seuraavalla summauksella:
Jossa kanoninen muoto S (y i) – yksi niistä k kolmannen muodon kohdefunktiot;
ω S– sen painokerroin.
Kuitenkin, kuten siellä osoitetaan, yksittäisten tavoitefunktioiden painokertoimien määrittäminen on erittäin vaikeaa.
Tuloksena olevan määrän ääriarvoa pidetään optimaalisena.
Siten voidaan osoittaa, että useimmissa tapauksissa (1. ja 3. muoto) järjestelmän laatuindikaattorit arvioidaan vektorin tavoitefunktion komponenttien numeerisilla arvoilla, joita kutsutaan ns. funktionaalisia :
- - - - - - - - - - - - - - - - - -
Koska järjestelmät toimivat satunnaisten vaikutusten olosuhteissa, funktionaalisten funktioiden arvot osoittautuvat usein satunnaismuuttujiksi. Tämä on hankalaa käytettäessä toimintoja laatuindikaattoreiden muodossa. Siksi tällaisissa tapauksissa käytetään yleensä vastaavien funktionaalisten funktioiden keskiarvoja. Esimerkiksi: keskimääräinen tuotettujen tuotteiden määrä vuorossa; keskimääräiset tuotantokustannukset jne.
Joissakin tapauksissa laatuindikaattorit edustavat tiettyjen satunnaisten tapahtumien todennäköisyyttä. Tässä tapauksessa tavoitefunktioksi valitaan todennäköisyys 
asetetun tavoitteen (tehtävän) täyttäminen järjestelmän toimesta
Esimerkiksi tutkan kohteen havaitsemisen todennäköisyys jne.
