Jaamme kolmannen rivin avainelementillä, joka on yhtä suuri kuin 5, saamme uuden taulukon kolmannen rivin.

Perussarakkeet vastaavat yksittäisiä sarakkeita.

Taulukon jäljellä olevien arvojen laskeminen:

"BP - perussuunnitelma":

; ;

"x1": ; ;

"x5": ; .

Indeksirivin arvot eivät ole negatiivisia, joten saamme optimaalisen ratkaisun: , ; .

Vastaus: suurin voitto valmistettujen tuotteiden myynnistä, joka vastaa 160/3 yksikköä, varmistetaan vapauttamalla vain toisen tyypin tuotteita 80/9 yksikköä.

Tehtävä numero 2

Epälineaarisen ohjelmoinnin ongelma on annettu. Etsi tavoitefunktion maksimi ja minimi graafianalyyttisellä menetelmällä. Muodosta Lagrange-funktio ja näytä, että riittävät minimi- (maksimi-) ehdot täyttyvät ääripisteissä.

Koska salauksen viimeinen numero on 8, jolloin A=2; B = 5.

Koska salauksen toiseksi viimeinen numero on 1, niin sinun tulee valita tehtävä numero 1.

Päätös:

1) Piirretään alue, jonka epäyhtälöjärjestelmä määrittelee.

Tämä alue on kolmio ABC, jonka kärkien koordinaatit: A(0; 2); B(4; 6) ja C(16/3; 14/3).

Tavoitefunktiotasot ovat ympyröitä, joiden keskipiste on pisteessä (2; 5). Säteiden neliöt ovat tavoitefunktion arvoja. Sitten kuvasta näkyy, että tavoitefunktion minimiarvo saavutetaan pisteessä H, maksimiarvo on joko pisteessä A tai pisteessä C.

Tavoitefunktion arvo pisteessä A: ;

Tavoitefunktion arvo pisteessä C: ;

Tämä tarkoittaa, että funktion maksimiarvo saavutetaan pisteessä A(0; 2) ja se on 13.

Etsitään pisteen H koordinaatit.

Voit tehdä tämän harkitsemalla järjestelmää:

ó

ó

Suora on ympyrän tangentti, jos yhtälöllä on ainutlaatuinen ratkaisu. Neliöyhtälöllä on ainutlaatuinen ratkaisu, jos diskriminantti on 0.

Sitten ; ; - funktion vähimmäisarvo.

2) Laadi Lagrange-funktio löytääksesi vähimmäisratkaisun:

klo x 1 =2.5; x 2 =4.5 saamme:

ó

Järjestelmässä on ratkaisu mm. riittävät ääriehdot täyttyvät.

Laadimme Lagrange-funktion maksimiratkaisun löytämiseksi:

Riittävät edellytykset ääripäälle:

klo x 1 =0; x 2 =2 saamme:

ó ó

Järjestelmässä on myös ratkaisu, ts. riittävät ääriehdot täyttyvät.

Vastaus: tavoitefunktion minimi saavutetaan ; ; suurin tavoitefunktio saavutetaan, kun ; .

Tehtävä numero 3

Kahdelle yritykselle myönnetään määrärahoja d yksiköitä. Kun se jaetaan ensimmäiselle yritykselle vuodeksi x rahastoyksiköitä se tuottaa tuloja k 1 x yksikköä ja kun se kohdistetaan toiselle yritykselle y rahastoyksikköä, se tuottaa tuloja k 1 y yksiköitä. Ensimmäisen yrityksen varojen saldo vuoden lopussa on yhtä suuri nx, ja toiselle minun. Kuinka jakaa kaikki varat 4 vuoden sisällä niin, että kokonaistulo on suurin? Ratkaise ongelma dynaamisen ohjelmoinnin avulla.

i = 8, k = 1.

A = 2200; k1 = 6; k2 = 1; n = 0,2; m = 0,5.

Päätös:

Koko 4 vuoden ajanjakso on jaettu 4 vaiheeseen, joista jokainen on yhtä suuri kuin yksi vuosi. Numeroidaan vaiheet ensimmäisestä vuodesta alkaen. Olkoon X k ja Y k yrityksille A ja B kohdistetut varat vastaavasti k-vaiheessa. Tällöin summa X k + Y k =a k on k - tuossa vaiheessa käytettyjen ja edellisestä vaiheesta k - 1 jäljellä olevien varojen kokonaismäärä. Ensimmäisessä vaiheessa käytetään kaikki allokoidut varat ja a 1 = 2200 yksikköä. tulot, jotka saadaan vaiheessa k - tuossa vaiheessa, kun X k ja Y k yksikköä kohdennetaan, on 6X k + 1Y k . olkoon viimeisillä vaiheilla saadut maksimitulot k:sta alkaen - tuo vaihe on f k (a k) yksikköä. Kirjoitetaan optimaalisuuden periaatetta ilmaiseva Bellman-funktionaalinen yhtälö: oli alkutila ja alkuratkaisu mikä tahansa, seuraavan ratkaisun tulee olla optimaalinen suhteessa alkutilan tuloksena saatuun tilaan:

Jokaiselle vaiheelle on valittava arvo X k ja arvo Y k=ak- Xk. Tätä silmällä pitäen löydämme tulot k-asteelta:

Toiminnallinen Bellman-yhtälö näyttää tältä:

Harkitse kaikkia vaiheita viimeisestä alkaen.

(koska lineaarifunktion maksimi saavutetaan janan lopussa kohdassa x 4 = a 4);

Liittovaltion koulutusvirasto

Valtion budjettikoulutuslaitos

korkeampi ammatillinen koulutus

"Omskin valtion teknillinen yliopisto"

LASKENTA JA GRAAFISET TYÖT

kurinalaisuudesta"OPTIMAALINEN OHJAUSTEORIA »

aiheesta "OPTIMOINTIMENETELMÄT JA TOIMINTATUTKIMUS »

vaihtoehto 7

Valmistunut:

kirjeenvaihto-opiskelija

4. vuosiryhmä ZA-419

Nimi: Kuzhelev S.A.

Tarkistettu:

Devyaterikova M.V.

Omsk - 2012
^

Tehtävä 1. Graafinen menetelmä lineaarisen ohjelmoinnin ongelmien ratkaisemiseksi.

7) 7x 1 + 6x 2 → max 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Vaihe 1. Hyvän alueen rakentaminen

Muuttujien ja neliöiden ei-negatiivisuuden ehdot rajoittavat niiden sallittujen arvojen alueen ensimmäiseen neljännekseen. Jokainen mallin jäljelle jäävistä neljästä rajoituksesta-epäyhtälöstä vastaa jotakin puolitasoa. Näiden puolitasojen leikkaus ensimmäisen kvadrantin kanssa muodostaa joukon mahdollisia ratkaisuja ongelmaan.

Mallin ensimmäinen rajoitus on . Korvaamalla siinä olevan merkin ≤ merkillä =, saadaan yhtälö . Kuvassa 1.1 se määrittelee suoran (1), joka jakaa tason kahteen puolitasoon, tässä tapauksessa viivan ylä- ja alapuolelle. Valitse, kumpi tyydyttää epätasa-arvon , korvaamme siihen minkä tahansa pisteen koordinaatit, jotka eivät ole annetulla suoralla (esim. X 1 = 0, X 2 = 0). Koska saamme oikean lausekkeen (20 0 + 6 0 = 0 ≤15), niin origon sisältävä puolitaso (merkitty nuolella) täyttää epäyhtälön. Muuten toinen puolitaso.

Jatkamme samalla tavalla ongelman jäljellä olevien rajoitusten kanssa. Kaikkien rakennettujen puolitasojen leikkaus ensimmäisen neljänneksen kanssa muodostuu ABCD(katso kuva 1). Tämä on tehtävän pätevä laajuus.

Vaihe 2. Tasoviivan rakentaminen Tasoviiva tavoitefunktio on joukko tasossa olevia pisteitä, joissa tavoitefunktio saa vakioarvon. Tällainen joukko saadaan yhtälöstä f ( x) = konst. Laitetaanpa esim. konst = 0 ja piirrä viiva tasolle f ( x) = 0 eli meidän tapauksessamme suora 7 x 1 + 6x 2 = 0.

Tämä viiva kulkee origon läpi ja on kohtisuorassa vektoriin nähden. Tämä vektori on tavoitefunktion gradientti kohdassa (0,0). Funktion gradientti on tietyn funktion osittaisten derivaattojen arvojen vektori kyseisessä pisteessä. LP-ongelman tapauksessa tavoitefunktion osittaiset derivaatat ovat yhtä suuria kuin kertoimet Cminä, j = 1 , ..., n.

Gradientti näyttää funktion nopeimman kasvun suunnan. Siirretään tavoitefunktion tasoviivaa f ( x) = konst. kohtisuorassa gradientin suuntaan, etsi viimeinen piste, jossa se leikkaa alueen kanssa. Meidän tapauksessamme tämä on piste D, joka on tavoitefunktion maksimipiste (katso kuva 2).

Se sijaitsee viivojen (2) ja (3) leikkauskohdassa (katso kuva 1) ja asettaa optimaalisen ratkaisun.

^ Huomaa, että jos haluat löytää tavoitefunktion minimiarvon, tasoviivaa siirretään gradientin suuntaa vastakkaiseen suuntaan.

^ Vaihe 3. Maksimipisteen (minimipisteen) koordinaattien ja tavoitefunktion optimaalisen arvon määrittäminen

Pisteen C koordinaattien löytämiseksi on ratkaistava järjestelmä, joka koostuu vastaavista suorista yhtälöistä (tässä tapauksessa yhtälöistä 2 ja 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Saamme optimaalisen ratkaisun = 1,33.

^ Tavoitefunktion optimaalinen arvo f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

Päätös: etsi funktion \(f (x, y)\) suurin ja pienin arvo seuraavien rajoitusten alla $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \ \begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(tapaukset) $$
On suositeltavaa käyttää graafista ongelmanratkaisumenetelmää kahden muuttujan tehtäviin, jotka on kirjoitettu symmetriseen muotoon, sekä monien muuttujien ongelmiin edellyttäen, että niiden kanoninen merkintä sisältää enintään kaksi vapaata muuttujaa.

Tässä tapauksessa tehtävä, jossa on kaksi muuttujaa.

Algoritmi ongelman "lineaarisen ohjelmointitehtävän geometrinen tulkinta" ratkaisemiseksi:

1. Muodostetaan sallittujen ratkaisujen alue xOy-tasolle.
2. Valitse ei-negatiivisten ratkaisujen alue.

4. Muodostetaan tavoitefunktioiden perhe.
5. Etsi tavoitefunktion suurin (minimi)arvo.

1. Rakennamme ongelman \(D\) hyväksyttävien ratkaisujen alueen.

Toteutettavien ratkaisujen alueen rakentaminen:
1) Rakennamme rajaviivoja:
muunnamme epäyhtälöt yhtälöiksi ja sitten suoran yhtälöön segmenteissä muotoa \(\frac(x)(a)+\frac(y)(b) = 1\), sitten \ (x=a\) on Ox-akselilta leikattu segmentti, \(y=b\) - Oy-akselilla $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(cases) => \begin(tapaukset) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ Varaa jokaiselle riville segmentit akseleille ja yhdistä ne. Meillä on oikeat linjat.

2) Löydämme puolitasot, jotka täyttävät annetut epäyhtälöt:
Epäyhtälölle \(2x+3y\geq 6\) on puolitaso, joka sijaitsee suoran \(2x+3y = 6\) yläpuolella. Suora AC
Epäyhtälölle \(3x-2y\leq 18 => -3x+2y \geq -18\) on puolitaso, joka sijaitsee suoran \(3x-2y = 18\) yläpuolella. Suora CB
Epäyhtälölle \(-x+2y\leq 8\) on puolitaso, joka sijaitsee viivan \(-x+2y = 8\) alapuolella. Suora AB

Toteutettavien ratkaisujen alue määritellään annettuja epäyhtälöitä vastaavien kolmen puolitason yhteisenä osana. Tämä alue on kolmio \(ABC\)

Alue \(D\) on kolmio \(ABC\) katso kuva.

2. Valitse ei-negatiivisten ratkaisujen alue.

Ei-negatiivisten ratkaisujen alue sijaitsee ensimmäisellä neljänneksellä ja on yhteinen osa kaikkia viittä puolitasoa, joista kolme on epäyhtälöistä saatu alue \(D\) ja lisäksi kaksi epäyhtälöä \(x \geq 0\ ) - ylempi puolitaso (I ja II neljännes) ja \(y \geq 0\) - oikea puolitaso (I ja IV neljännes), jotka ilmaisevat muuttujien ei-negatiivisuuden ehdon \(x; y\). Saatiin haluttu alue ei-negatiivisia ratkaisuja \(DEBFG\)

3.Etsi alueen kärkipisteiden koordinaatit.
Neljän kärjen koordinaatit ovat jo tiedossa (nämä ovat suorien ja akselien leikkauspisteitä).
Kirjataan muistiin nämä koordinaatit:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Etsi pisteen \(B\) koordinaatit suorien \(-x+2y = 8\) ja \(3x-2y = 18\) leikkauspisteinä. Ratkaise yhtälöjärjestelmä ja etsi tämän pisteen koordinaatit $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(tapaukset)=> \begin(tapaukset) x = 13\\ y =10,5\loppu(tapaukset)$$
Saimme pisteen koordinaatit \(B(13;10.5)\)

4. Rakennamme tavoitefunktioiden perheen.
Yhtälö \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) määrittää xOy-tasolla samankeskisten ympyröiden perheen, joiden keskipiste on pisteessä, jonka koordinaatit \ (Q(4 ;3)\), joista jokainen vastaa parametrin \(f\) tiettyä arvoa. Kuten tiedät, ympyrän yhtälölle parametri \(f=R^2\).

Esitetään samassa koordinaattijärjestelmässä samankeskisten ympyröiden \(f\) perhe ja suorien perhe. Ongelma pisteen \(f\) maksimi- (minimi-) pisteen määrittämisessä rajoittuu siihen, että sallitulta alueelta löydetään piste, jonka läpi perheen ympyrä \(f=const\) kulkee ja joka vastaa parametrin \(f\) suurin (pienin) arvo.

5. Etsi tavoitefunktion suurin (minimi)arvo.

Tavoitefunktion vähimmäisarvo: Kasvattamalla vähitellen ympyrän sädettä, olemme saaneet, että ensimmäinen kärki, jonka läpi ympyrä kulkee, on piste \(G(3;0)\). Tavoitefunktio on tässä vaiheessa minimaalinen ja yhtä suuri kuin \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

Tavoitefunktion enimmäisarvo: Lisäämällä edelleen ympyrän sädettä, olemme saaneet, että viimeinen kärkipiste, jonka kautta ympyrä kulkee, on piste \(B(13;10.5)\). Tavoitefunktio on tässä vaiheessa maksimi ja yhtä suuri kuin \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\)

Voit varmistaa ratkaisun oikeellisuuden korvaamalla tavoitefunktion yhtälön jäljellä olevien kärkien koordinaatit:
kärjessä \(D(0;2)\) tavoitefunktion arvo on yhtä suuri kuin \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
kärjessä \(E(0;4)\) tavoitefunktion arvo on yhtä suuri kuin \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
kärjessä \(F(6;0)\) tavoitefunktion arvo on \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Selvä

Vastaus:
tavoitefunktion vähimmäisarvo \(f_(min) = 10\)
tavoitefunktion maksimiarvo \(f_(max) = 137,25\)

tavoitefunktio- 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. Tavoitefunktion lisäksi optimointitehtävässä muuttujat voivat olla rajoituksen alaisia ​​yhtä- tai epäyhtälöjärjestelmän muodossa. Yleisessä tapauksessa 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 voidaan yhtäpitää 0:aan (\displaystyle 0) kaikkien muuttujien osittaiset derivaatat. Optimaalinen tavoitefunktio on yksi ratkaisuista tällaiseen yhtälöjärjestelmään. Toiminnon (1) (\displaystyle (1)) tapauksessa tämä on pienimmän neliösumman (LSM) yhtälöjärjestelmä. Mikä tahansa alkuperäisen järjestelmän ratkaisu on pienimmän neliösumman järjestelmän ratkaisu. Jos alkuperäinen järjestelmä on epäjohdonmukainen, niin LSM-järjestelmä, jolla on aina ratkaisu, mahdollistaa alkuperäisen järjestelmän likimääräisen ratkaisun saamisen. LSM-järjestelmän yhtälöiden lukumäärä osuu yhteen tuntemattomien määrän kanssa, mikä joskus helpottaa yhteisten alkujärjestelmien ratkaisemista.

Lineaarinen ohjelmointi

Toinen hyvin tunnettu esimerkki tavoitefunktiosta on lineaarinen funktio, jota esiintyy lineaarisissa ohjelmointiongelmissa. 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ä-ongelman tavoitefunktio. Tämä funktio on yhtä suuri kuin Hamiltonin syklin pituus kuvaajassa. Se annetaan graafin kärkien permutaatiojoukossa n − 1 (\displaystyle n-1) ja se määräytyy graafin reunan pituusmatriisin mukaan. Tällaisten ongelmien tarkka ratkaisu riippuu usein vaihtoehtojen luettelemisesta.

Luku 1. Esitys lineaarisen ohjelmoinnin pääongelmasta

1. Lineaarinen ohjelmointi

Lineaarinen ohjelmointi on matemaattisen ohjelmoinnin haara, joka tutkii menetelmiä äärimmäisten ongelmien ratkaisemiseksi, joille on tunnusomaista lineaarinen suhde muuttujien ja lineaarisen kriteerin välillä. Tällaisia ​​tehtäviä käytetään laajasti ihmisen toiminnan eri aloilla. Tällaisten ongelmien systemaattinen tutkiminen aloitettiin vuosina 1939–1940. L.V.:n teoksissa. Kantorovich.

Lineaarisen ohjelmoinnin matemaattisiin ongelmiin kuuluu tiettyjen tuotanto- ja taloustilanteiden tutkiminen, jotka tavalla tai toisella tulkitaan rajallisten resurssien optimaalisen käytön ongelmiksi.

Lineaarisilla ohjelmointimenetelmillä ratkaistavien ongelmien kirjo on varsin laaja. Näitä ovat mm.

resurssien optimaalisen käytön ongelma tuotannon suunnittelussa;

seosten ongelma (tuotteiden koostumuksen suunnittelu);

ongelma löytää optimaalinen yhdistelmä erityyppisiä tuotteita 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ähän sisältyy: kokonaisluku, dynaaminen, epälineaarinen, parametrinen ohjelmointi). Tämä selitetään seuraavasti:

useiden taloudellisten ongelmien matemaattiset mallit ovat lineaarisia vaadittujen muuttujien suhteen;

Tämäntyyppiset ongelmat ovat tällä hetkellä eniten tutkittuja. Hänelle on kehitetty erityisiä menetelmiä, joiden avulla nämä ongelmat ratkaistaan, ja vastaavat tietokoneohjelmat;

monet lineaarisen ohjelmoinnin ongelmat, joita ratkaistaan, ovat löytäneet laajan sovelluksen;

Jotkut ongelmat, jotka eivät ole lineaarisia alkuperäisessä koostumuksessa, voivat useiden lisärajoitusten ja oletusten jälkeen muuttua lineaariseksi 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.

Yleensä malli on kirjoitettu seuraavasti:

tavoitefunktio

(1.1) rajoitusten mukaisesti

(1.2) ei-negatiivisuusvaatimukset

(1.3) missä x j– muuttujat (tuntemattomat);

- 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) kutsutaan suoriksi rajoituksiksi.

Vektoria, joka täyttää rajoitukset (1.2) ja (1.3), kutsutaan lineaarisen ohjelmointiongelman toteuttamiskelpoiseksi ratkaisuksi (suunnitelmaksi). Suunnitelmaa, jossa funktio (1.1) saavuttaa maksimi (minimi) arvonsa, kutsutaan optimaaliseksi.

1.2. Simpleksi menetelmä lineaarisen ohjelmoinnin ongelmien ratkaisemiseen

Simpleksimenetelmän kehitti ja sovelsi ensimmäisen kerran ongelmien ratkaisemiseen vuonna 1947 amerikkalainen matemaatikko J. Dantzig.

Kaksiulotteiset lineaariset ohjelmointitehtävät ratkaistaan ​​graafisesti. Tapauksessa N=3 voidaan harkita kolmiulotteista avaruutta ja tavoitefunktio saavuttaa optimaalisen arvonsa yhdessä monitahoisen kärjestä.

Vakiomuodossa annetun LP-tehtävän hyväksyttävä ratkaisu (hyväksyttävä suunnitelma) on järjestetty numerosarja (x1, x2, ..., xn), joka täyttää rajoitukset; on piste n-ulotteisessa avaruudessa.

Hyväksyttyjen ratkaisujen joukko muodostaa LP-ongelman hyväksyttävien ratkaisujen alueen (SDR). ODR on kupera monikulmio.

Yleisesti ottaen, kun ongelmaan liittyy N-tuntematonta, voidaan sanoa, että rajoitusehtojärjestelmän määrittelemää toteuttamiskelpoisten ratkaisujen aluetta edustaa kupera monitahoinen n-ulotteisessa avaruudessa ja objektiivin optimaalinen arvo. funktio saavutetaan yhdessä tai useammassa kärjessä.

Ratkaisua kutsutaan perusratkaisuksi, jos kaikki vapaat muuttujat ovat yhtä suuria kuin nolla.

Vertailuratkaisu on emäksinen ei-negatiivinen ratkaisu. Tukiratkaisu voi olla rappeutumaton ja rappeutunut. Tukiratkaisua kutsutaan ei-degeneroituneeksi, jos sen nollasta poikkeavien koordinaattien määrä on yhtä suuri kuin järjestelmän arvo, muuten se on rappeutunut.

Toteutettavaa 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 tapa ratkaista lineaarisen ohjelmoinnin ongelmia, jota kutsutaan simplex-menetelmäksi.

Simplex-menetelmä on universaali menetelmä LP-ongelmien ratkaisemiseen, 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 tarkoitus on siirtyä peräkkäin rajoituspolyhedrin yhdestä kärjestä viereiseen, jossa tavoitefunktio saa parhaan (tai ei ainakaan huonoimman) arvon, kunnes optimaalinen ratkaisu löytyy - kärki missä optimaalinen arvo saavutetaan tavoitefunktio (jos ongelmalla on äärellinen optimi).

Näin ollen, kun rajoitusjärjestelmä on pelkistetty kanoniseen muotoon (kaikki toiminnalliset rajoitukset ovat yhtäläisyyksiä), voidaan 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 osoittautui toteuttamiskelpoiseksi, sen optimaalisuus tarkistetaan. Jos se ei ole optimaalinen, siirrytään toiseen, välttämättä hyväksyttävään perusratkaisuun. Simplex-menetelmä takaa, että tällä uudella ratkaisulla tavoitefunktio, jos se ei saavuta optimia, lähestyy sitä (tai ei ainakaan lähde siitä pois). Uudella hyväksyttävällä perusratkaisulla sama tehdään, kunnes löydetään optimaalinen ratkaisu.

Simplex-menetelmän soveltamisprosessi sisältää sen kolmen pääelementin toteuttamisen:

menetelmän jonkin alkuperäisen toteuttamiskelpoisen perusratkaisun määrittämiseksi ongelmaan;

parhaaseen (tarkemmin, ei pahimpaan) ratkaisuun siirtymisen sääntö;

kriteeri löydetyn ratkaisun optimaalisuuden tarkistamiseksi.

Simpleksimenetelmä sisältää useita vaiheita, ja se voidaan muotoilla selkeäksi algoritmiksi (selkeä ohje peräkkäisten toimintojen suorittamiseen). Näin voit ohjelmoida ja toteuttaa sen onnistuneesti tietokoneella. Ongelmat, joissa on pieni määrä muuttujia ja rajoitteita, voidaan ratkaista simplex-menetelmällä manuaalisesti.

6.1 Johdanto

Optimointi. Osa 1

Optimointimenetelmien avulla voit valita parhaan suunnitteluvaihtoehdon kaikista mahdollisista vaihtoehdoista. Viime vuosina näihin menetelmiin on kiinnitetty paljon huomiota, ja sen seurauksena on kehitetty useita erittäin tehokkaita algoritmeja, joiden avulla on mahdollista löytää optimaalinen suunnitteluvaihtoehto digitaalisen tietokoneen avulla. Tässä luvussa hahmotellaan optimointiteorian perusteet, tarkastellaan optimaalisten ratkaisujen algoritmien rakentamisen taustalla olevia periaatteita, kuvataan tunnetuimpia algoritmeja sekä analysoidaan niiden etuja ja haittoja.

6.2 Optimointiteorian perusteet

Käsite "optimointi" viittaa kirjallisuudessa prosessiin tai toimintosarjaan, jonka avulla voit saada hienostuneen ratkaisun. Vaikka optimoinnin perimmäisenä tavoitteena on löytää paras eli "optimaalinen" ratkaisu, on yleensä tyydyttävä tunnettujen ratkaisujen parantamiseen sen täydentämisen sijaan. Siksi optimointi ymmärretään todennäköisemmin täydellisyyden tavoitteluna, jota ei ehkä 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ällaiseen ongelmaan on yleensä yksi ratkaisu. Jos m>n, niin ongelma määritellään uudelleen, eikä sillä yleensä ole ratkaisua. Lopuksi m

Ennen kuin siirrymme keskusteluun optimointikysymyksistä, esittelemme useita määritelmiä.

Suunnitteluparametrit

Tämä termi tarkoittaa riippumattomia muuttujaparametreja, jotka määrittelevät täysin ja yksiselitteisesti ratkaistavan suunnitteluongelman. Suunnitteluparametrit ovat tuntemattomia suureita, joiden arvot lasketaan optimointiprosessin aikana. Mikä tahansa perus- tai johdannaissuureet, jotka kuvaavat järjestelmää kvantitatiivisesti, voivat toimia suunnitteluparametreina. Joten se voi olla tuntemattomia pituuden, massan, ajan, lämpötilan arvoja. Suunnitteluparametrien määrä luonnehtii tämän suunnitteluongelman monimutkaisuuden astetta. Yleensä suunnitteluparametrien lukumäärä merkitään n:llä ja itse suunnitteluparametrit x vastaavilla indekseillä. Siten tämän ongelman n suunnitteluparametria merkitään

X1, x2, x3,...,xn.

tavoitefunktio

Tämä on lauseke, jonka arvon suunnittelija pyrkii maksimoimaan tai minimoimaan. Tavoitefunktio mahdollistaa kahden vaihtoehtoisen ratkaisun kvantitatiivisen vertailun. Matemaattisesta näkökulmasta kohdefunktio kuvaa jotakin (n + 1) -ulotteista pintaa. Sen arvo määräytyy suunnitteluparametrien mukaan

M = M(x1, x2,...,xn).

Esimerkkejä insinöörikäytännössä usein tavattavasta tavoitefunktiosta 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 esitetään pinnalla kolmen ulottuvuuden avaruudessa (kuva 6.2). Kolmella tai useammalla suunnitteluparametrilla kohdefunktion määrittelemiä pintoja kutsutaan hyperpinnoiksi, eikä niitä voida kuvata.

zheniya tavanomaisin keinoin. Kohdefunktiopinnan topologiset ominaisuudet ovat tärkeässä roolissa 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 kohdefunktio.

suljettu matemaattinen muoto, muissa tapauksissa voi

olla paloittain sileä toiminto. Tavoitefunktio voi joskus vaatia teknisen tietotaulukon (esimerkiksi höyrytilataulukon) tai se voi olla tarpeen suorittaa koe. 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 arvoa - kyllä ​​tai ei. Laadullisia parametreja, kuten asiakastyytyväisyys, luotettavuus, estetiikka, on vaikea ottaa huomioon optimointiprosessissa, koska niitä on lähes mahdotonta mitata. Kuitenkin missä muodossa tavoitefunktio esitetään, sen on oltava suunnitteluparametrien yksiarvoinen funktio.

Useissa optimointiongelmissa vaaditaan useamman kuin yhden tavoitefunktion käyttöönotto. Joskus yksi niistä voi olla yhteensopimaton toisen kanssa. Esimerkkinä on lentokoneiden suunnittelu, jolloin vaaditaan samanaikaisesti maksimaalinen lujuus, vähimmäispaino ja vähimmäiskustannukset. Tällaisissa tapauksissa suunnittelijan on otettava käyttöön prioriteettijärjestelmä ja osoitettava jokaiselle tavoitefunktiolle jokin dimensioton kertoja. Tämän seurauksena näkyviin tulee "kompromissifunktio", joka mahdollistaa yhden yhdistetyn tavoitefunktion käytön optimointiprosessissa.

Löytää minimi ja maksimi

Jotkut optimointialgoritmit on mukautettu etsimään maksimi, toiset etsimään minimi. Ratkaistavan äärimmäisen ongelman tyypistä riippumatta voidaan kuitenkin käyttää samaa algoritmia, koska minimointitehtävä voidaan helposti muuttaa maksimiongelmaksi muuttamalla tavoitefunktion etumerkki päinvastaiseksi. 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 se on yleensä rajoitettu useisiin

olosuhteet, jotka liittyvät ongelman fyysiseen olemukseen. Rajoitukset voivat olla niin voimakkaita, että tehtävällä ei ole niitä

Kuva 6.3. Kohdefunktion etumerkin muuttaminen päinvastaiseksi

Maksimitehtävästä tulee minimitehtävä.

tyydyttävä ratkaisu. Rajoitukset jaetaan kahteen ryhmään: rajoitteet - yhtäläisyydet ja rajoitteet - epätasa-arvot.

Rajoitukset - tasa-arvo

Rajoitukset - yhtäläisyydet - on suunnitteluparametrien välinen riippuvuus, joka on otettava huomioon ratkaisua etsittäessä. Ne heijastavat luonnonlakeja, taloutta, oikeuksia, vallitsevia makuja ja tarvittavien materiaalien saatavuutta. Rajoitusten lukumäärä - yhtäläisyydet voivat olla mitä tahansa. He 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, voit sulkea tämän parametrin optimointiprosessin ulkopuolelle. Tämä vähentää suunnittelutilan mittojen määrää ja yksinkertaistaa ongelman ratkaisua.

Rajoitukset - epätasa-arvo

Tämä on erityinen rajoitus, jota eriarvoisuus ilmaisee. Yleensä niitä voi olla mikä tahansa määrä, ja 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 optimaalista arvoa ei saavuteta, jos sen pinnalla on nollagradientti. Usein paras ratkaisu on jollain suunnittelualueen rajoista.

Paikallinen optimi

Tämä on sen pisteen nimi suunnittelutilassa, jossa kohdefunktiolla on suurin arvo verrattuna sen arvoihin kaikissa muissa sen välittömässä läheisyydessä.

Kuva 6.4 Mielivaltaisella tavoitefunktiolla voi olla useita

paikallinen optimi.

Kuvassa Kuvassa 6.4 on yksiulotteinen tavoitefunktio, 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 tätä suunnittelija etsii. Useiden yhtäläisten globaalien optimien tapaus, jotka sijaitsevat suunnittelutilan eri osissa, on mahdollista. Optimointiongelman asettamista havainnollistaa parhaiten esimerkki.

Esimerkki 6.1

Olkoon tarpeen suunnitella suorakaiteen muotoinen säiliö, jonka tilavuus on 1 m ja joka on suunniteltu kuljettamaan pakkaamatonta kuitua. 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 on halvempaa. Jotta kontti olisi kätevä kuljettaa trukilla, sen leveyden on oltava 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 ala:

A=2(x 1 x 2 + x 2 x 3 + x 1 x 3), m2.

Rajoitus - tasa-arvo:

Tilavuus \u003d x 1 x 2 x 3 \u003d 1m3.

Rajoitus - epätasa-arvo:

Lineaarisen ohjelmoinnin ongelmat

Lineaarinen ohjelmointi (LP) on yksi matemaattisen ohjelmoinnin osista - tieteenala, joka tutkii äärimmäisiä (optimointi)ongelmia ja kehittää menetelmiä niiden ratkaisemiseksi.

Optimointi ongelma on matemaattinen ongelma, joka koostuu tavoitefunktion optimaalisen (eli maksimi- tai minimiarvon) löytämisestä, ja muuttujien arvojen tulee kuulua tietylle sallittujen arvojen alueelle (ODV).

Yleensä matemaattisen ohjelmoinnin äärimmäisen ongelman muotoilu koostuu funktion suurimman tai pienimmän arvon määrittämisestä, ns. tavoitefunktio, ehdoilla (rajoituksilla) , joissa ja on annettu funktioita, ja niille on annettu vakioita. Samanaikaisesti yhtäläisyyksien ja epätasa-arvojen muodossa olevat rajoitukset määrittävät toteutettavissa olevien ratkaisujen (ODS) joukon (alueen), ja niitä kutsutaan ns. suunnitteluparametreja.

Riippuen funktioiden tyypistä ja tehtävistä matemaattinen ohjelmointi jaetaan useisiin luokkiin (lineaarinen, epälineaarinen, konveksi, kokonaisluku, stokastinen, dynaaminen ohjelmointi jne.).

AT yleisnäkymä LP-ongelmalla on seuraava muoto:

, (5.1)

, , (5.2)

, , (5.3)

jossa , , annetaan vakioita.

Funktiota (5.1) kutsutaan tavoitefunktioksi; järjestelmät (5.2), (5.3) - rajoitusjärjestelmän avulla; ehto (5.4) on suunnitteluparametrien ei-negatiivisuuden ehto.

Rajoitukset (5.2), (5.3) ja (5.4) täyttävää suunnitteluparametrien joukkoa kutsutaan ns. hyväksyttävä ratkaisu tai suunnitelma.

Optimaalinen ratkaisu tai optimaalinen suunnitelma LP-tehtävää kutsutaan toteuttamiskelpoiseksi ratkaisuksi, jossa tavoitefunktio (5.1) saa optimaalisen (maksimi- tai minimiarvon).

Vakiotehtävä LP on tavoitefunktion (5.1) suurimman (minimi)arvon löytämisen ongelma ehdoilla (5.2) ja (5.4), missä , , ts. nuo. 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:tä kutsutaan ongelmaksi tavoitefunktion (5.1) maksimi- (minimi-) arvon löytämisessä ehdoilla (5.3) ja (5.4), missä , , ts. nuo. 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.

Kanonisen LP-tehtävän matriisimuodolla on seuraava muoto:

Kanonisen LP-ongelman vektorimuoto.