Lineaarinen ohjelmointi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 5. toukokuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Lineaarinen ohjelmointi on matemaattinen tieteenala, joka on omistettu teorialle ja menetelmille äärimmäisten ongelmien ratkaisemiseksi lineaaristen yhtälö- ja epäyhtälöysjärjestelmien määrittämissä -ulotteisen vektoriavaruuden joukoissa. $n$

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

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

Historia

Yksittäisten talousongelmien matemaattisia tutkimuksia, numeerisen aineiston matemaattista formalisointia tehtiin jo 1800-luvulla . Laajennetun tuotantoprosessin matemaattisessa analyysissä käytettiin algebrallisia suhteita, joiden analyysi suoritettiin differentiaalilaskennan avulla . Tämä mahdollisti yleiskäsityksen ongelmasta.

Talouden kehitys vaati määrällisiä indikaattoreita, ja 1920- luvulla luotiin sektorien välinen tasapaino ( IOB ). Hän oli se, joka toimi sysäyksenä matemaattisten mallien luomisessa ja tutkimisessa. MOB : n kehitys Neuvostoliitossa vuosina 1924-1925 vaikutti taloustieteilijän ja tilastotieteilijän Vasily Vasilievich Leontievin työhön . Hän kehitti sektorien välisen mallin tuotteiden tuotannosta ja jakelusta.

Vuonna 1938 Leonid Vitalievich Kantorovich alkoi tieteellisen kuulemisen aikana tutkia puhtaasti käytännöllistä tehtävää laatia paras kuormauskoneiden lastaussuunnitelma (vanerin luottamus). Tämä tehtävä ei soveltunut perinteisiin menetelmiin. Kävi selväksi, että tehtävä ei ollut satunnainen. [yksi]

Vuonna 1939 Leonid Kantorovich julkaisi teoksen "Matematical Methods of Organisation and Planning of Production", jossa hän muotoili uuden luokan äärimmäisiä ongelmia rajoituksin ja kehitti tehokkaan menetelmän niiden ratkaisemiseksi, mikä loi perustan lineaariseen ohjelmointiin.

Tällaisten ongelmien tutkiminen johti uuden tieteellisen lineaarisen ohjelmoinnin tieteenalan luomiseen ja avasi uuden vaiheen taloudellisten ja matemaattisten menetelmien kehityksessä.

Vuonna 1949 amerikkalainen matemaatikko George Bernard Dantzig kehitti tehokkaan menetelmän lineaaristen ohjelmointiongelmien (LPP) ratkaisemiseksi - simplex-menetelmän . [yksi]

Termi "ohjelmointi" on ymmärrettävä merkityksessä "suunnittelu" (yksi englanninkielisen ohjelmoinnin käännöksistä ). George Danzig, yksi lineaarisen ohjelmoinnin perustajista, ehdotti sitä 1940-luvun puolivälissä, ennen kuin tietokoneita käytettiin lineaarisen optimointiongelmien ratkaisemiseen .

Sisäpistemenetelmän mainitsi ensimmäisen kerran I. I. Dikin vuonna 1967 . [2] . Näitä tutkimuksia jatkettiin, mukaan lukien kotimaiset tutkijat. 1970-luvulla V. G. Zhadan onnistui saamaan tärkeimmät tulokset ja kehittämään yleisen lähestymistavan sisäpistemenetelmien rakentamiseen lineaarisen ja epälineaarisen ohjelmoinnin ongelmien ratkaisemiseksi, jotka perustuvat tilojen muuntamiseen; ehdottaa esteprojektiivisia ja este-newtonilaisia numeerisia menetelmiä.

Tehtävät

Lineaarisen ohjelmoinnin yleinen (vakio)ongelma on muotoa [3] olevan lineaarisen tavoitefunktion (lineaarisen muodon) minimin löytämisen ongelma:

f(x)=\sum _{j=1}^{n}c_{j}x_{j}=c_{1}x_{1}+c_{2}x_{2}+\ldots + c_{n}x_{n}.

Ongelmaa, jossa esiintyy rajoitteita epäyhtälöiden muodossa, kutsutaan peruslineaariseksi ohjelmointiongelmaksi (BLP) .

\sum _{j=1}^{n}a_{ij}x_{j}\geqslant b_{i},\quad (i=1,\;2,\;\ldots ,\;m)

x_{j}\geqslant 0.\quad (j=1,\;2,\;\ldots ,\;n)

Lineaarisen ohjelmoinnin ongelmalla on kanoninen muoto , jos pääongelmassa ensimmäisen epäyhtälöjärjestelmän sijasta on yhtälöjärjestelmä, jossa on rajoituksia tasa-arvon muodossa [4] :

\sum _{j=1}^{n}a_{ij}x_{j}=b_{i}.\quad (i=1,\;2,\;\ldots ,\;m)

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 pelkistää ekvivalenteiksi (sama ratkaisujoukko) muuttujien muutoksiin ja yhtälöiden korvaamiseen parilla. epätasa-arvo [5] .

On helppo nähdä, että maksimin löytämisen ongelma voidaan korvata minimin löytämisen ongelmalla ottamalla kertoimet päinvastaisella etumerkillä. $c$

Ongelmaesimerkkejä

Suurin vastaavuus

Harkitse maksimaalista yhteensopivuusongelmaa kaksiosaisessa kaaviossa : poikia ja tyttöjä on useita, ja jokaiselle pojalle ja tytölle tiedetään pitävätkö he toisistaan. On välttämätöntä solmia naimisiin mahdollisimman monta paria molemminpuolisella sympatialla.

Otetaan käyttöön muuttujat , jotka vastaavat -: nnen pojan ja -: nnen tytön paria ja täyttävät rajoitukset: $x_{ij}$ $i$ $j$

0\leqslant x_{{ij}}\leqslant 1,

x_{1j}+x_{2j}+\ldots +x_{nj}\leqslant 1,

x_{{i1}}+x_{{i2}}+\ldots +x_{{im}}\leqslant 1,

tavoitefunktiolla , jossa ovat 1 tai 0 riippuen siitä, ovatko -. poika ja -. tyttö mukavia toisilleen. Voidaan osoittaa, että tämän ongelman optimaalisten ratkaisujen joukossa on kokonaislukuratkaisu. Muuttujat 1 vastaavat pareja, joiden tulisi olla naimisissa. ${\displaystyle f=c_{11}x_{11}+c_{12}x_{12}+\ldots +c_{nm}x_{nm))$ $c_{ij}$ $i$ $j$

Suurin virtaus

Olkoon graafi (suunnattu reuna), jossa kunkin reunan kapasiteetti on osoitettu. Ja kaksi kärkeä annetaan: nielu ja lähde. Jokaiselle reunalle on määriteltävä, kuinka paljon nestettä virtaa sen läpi (enintään sen kapasiteetti), jotta kokonaisvirtaus lähteestä nieluon maksimoituu (neste ei voi ilmestyä tai kadota kaikissa pisteissä paitsi lähteessä ja nielussa, vastaavasti).

Otetaan muuttujiksi th reunan läpi virtaavan nesteen määrä . Sitten $x_{i}$ $i$

0\leqslant x_{i}\leqslant c_{i},

missä on th reunan kapasiteetti. Näitä epätasa-arvoja on täydennettävä saapuvan ja lähtevän nesteen määrän yhtäläisyydellä jokaisessa kärjessä, lukuun ottamatta nielua ja lähdettä. Funktiona on luonnollista ottaa lähteellä ulosvirtaavan ja sisäänvirtaavan nesteen määrän erotus. $c_{i}$ $i$ $f$

Edellisen ongelman yleistys on minimikustannusten maksimivirtaus. Tässä tehtävässä kunkin reunan kustannukset on annettu ja maksimivirtojen joukosta on valittava virtaus pienimmällä kustannuksella. Tämä tehtävä rajoittuu kahteen lineaariseen ohjelmointitehtävään: ensin on ratkaistava maksimivirtauksen ongelma ja sitten lisättävä tähän ongelmaan rajoitus , jossa on maksimivirtauksen arvo, ja ratkaista ongelma uudella funktiolla - virtauksen hinta. $f(x)\geqslant m$ $m$ $f(x)$

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

Kuljetusongelma

On tietty homogeeninen lasti, joka on kuljetettava varastoista tehtaille. Jokaisen varaston osalta tiedetään, kuinka paljon rahtia siinä on , ja kunkin tehtaan rahtitarve tunnetaan. Kuljetuskustannukset ovat verrannollisia etäisyyteen varastosta tehtaaseen (kaikki etäisyydet varastosta -tehtaan tunnetaan). On laadittava halvin kuljetussuunnitelma. $n$ $m$ $i$ $a_{i}$ $b_{j}$ $c_{ij}$ $i$ $j$

Ratkaisevia muuttujia tässä tapauksessa ovat - varastosta -: nnelle tehtaalle kuljetetun lastin määrä . Ne täyttävät rajoitukset: $x_{ij}$ $i$ $j$

x_{{i1}}+x_{{i2}}+\ldots +x_{{im}}\leqslant a_{i},

x_{{1j}}+x_{{2j}}+\ldots +x_{{nj}}\geqslant b_{j}.

Tavoitefunktion muoto on: , joka on minimoitava. $f(x)=x_{{11}}c_{{11}}+x_{{12}}c_{{12}}+\ldots +x_{{nm}}c_{{nm}}$

Nollasummapeli

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 - toinen). Meidän on löydettävä optimaalinen strategia ensimmäiselle pelaajalle. $A$ $n\ kertaa m$ $n$ $m$ $a_{{ij}}$ $(-a_{{ij}})$ $i$ $j$

Anna optimaalinen strategia, esimerkiksi ensimmäinen pelaaja, numero on valittava todennäköisyydellä . Sitten optimaalinen strategia on ratkaisu seuraavaan lineaariseen ohjelmointiongelmaan: $i$ $p_{i}$

0\leqslant p_{i}\leqslant 1,

p_{1}+\ldots +p_{n}=1,

a_{1i}p_{1}+a_{2i}p_{2}+\ldots +a_{ni}p_{n}\geqslant c\quad (i=1,\;\ldots ,\;m ),

jossa funktio halutaan maksimoida . Optimaalisen ratkaisun arvo on pahimman tapauksen odotus ensimmäisen pelaajan voitosta. $f(p_{1},\;\ldots ,\;p_{n},\;c)=c$ $c$

Ratkaisualgoritmit

Tunnetuin ja laajimmin käytetty käytännössä lineaarisen ohjelmoinnin (LP) yleisen ongelman ratkaisemiseksi on simpleksimenetelmä . Huolimatta siitä, että simpleksimenetelmä on melko tehokas algoritmi, joka on osoittanut hyviä tuloksia sovellettujen LP-ongelmien ratkaisemisessa, se on algoritmi, jonka monimutkaisuus on eksponentiaalinen . Syynä tähän on simplex-menetelmän kombinatorinen luonne, joka luettelee peräkkäin hyväksyttävien ratkaisujen monitahoisen kärjet etsiessään optimaalista ratkaisua.

Neuvostoliiton matemaatikko L. Khachiyan ehdotti vuonna 1979 ensimmäistä polynomialgoritmia , ellipsoidimenetelmää , mikä ratkaisi ongelman, joka oli ollut ratkaisematta pitkään. Ellipsoidimenetelmällä on täysin erilainen ei-kombinatorinen luonne kuin simpleksimenetelmällä. Laskennallisesti tämä menetelmä osoittautui kuitenkin lupaamattomaksi. Siitä huolimatta ongelmien polynomimonimutkaisuus johti kokonaisen luokan tehokkaiden LP-algoritmien luomiseen - sisäpistemenetelmiin , joista ensimmäinen oli N. Karmarkarin vuonna 1984 ehdotettu algoritmi . Tämän tyyppisissä algoritmeissa käytetään jatkuvaa LP-ongelman tulkintaa, jolloin LP-ongelman ratkaisujen polytoopin kärkipisteiden luettelemisen sijaan tehdään haku trajektoreja pitkin tehtävän muuttujien avaruudessa, jotka eivät kulje kärkien läpi. polytooppista. Sisäpistemenetelmä, joka toisin kuin simpleksimenetelmä ohittaa pisteet toleranssialueen sisäpuolelta, käyttää Fiaccon ja McCormickin 1960-luvulla kehittämiä ei-lineaarisen ohjelmoinnin logaritmisen estefunktiomenetelmiä.

Toinen tapa ratkaista LP on käyttää Seidel-algoritmia:

LP annetaan kanonisessa muodossa muuttujien ja rajoitusten kanssa, jotka muodostavat joukon . $d$ $m$ $H$
Jos tai , johda optimaalinen perusratkaisu . $d=1$ $m = 0$ $H$
Muussa tapauksessa valitse satunnainen rajoitus ja laske rekursiivisesti optimaalinen perusratkaisu . $h\in H$ $H\setminus \{h\}$
Jos optimaalinen perusratkaisu ei riko rajoitusta , palauta se. $H\setminus \{h\}$ $h$
Muussa tapauksessa laske LP-polyhedronin leikkauspiste hypertason kanssa ja ratkaise tuloksena oleva LP rekursiivisesti muuttujalla. $h$ $d-1$

Tällä menetelmällä on asymptoottinen monimutkaisuus . $O(m\cdot d!)$

Kaksoislineaariset ohjelmointiongelmat

Jokainen muodon lineaarinen ohjelmointitehtävä [6]

\sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m));

x_{j}\geqslant 0,\;j={\overline {1,\;n));

F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max

on mahdollista tietyllä tavalla verrata jotain muuta lineaarista ohjelmointiongelmaa, jota kutsutaan duaaliksi tai konjugaatiksi suhteessa alkuperäiseen tai suoraan. Yhteys alkuperäisen ja kaksoisongelman välillä on pääasiassa siinä, että toisen ratkaisu voidaan saada suoraan toisen ratkaisusta. Määritellään kaksoisongelma suhteessa alkuperäiseen lineaariseen ohjelmointitehtävään

Alkutehtävä	Kaksoisongelma
$\sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m))$	$y_{i}\geqslant 0,\;i={\overline {1,\;m))$
$x_{j}\geqslant 0,\;j={\overline {1,\;n))$	$\sum _{i=1}^{m}a_{ij}y_{i}\geqslant b_{j},\;j={\overline {1,\;n))$
$F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max$	$T(y)=\sum _{i=1}^{m}c_{i}y_{i}\to \min$

Jos vektorit ja ovat hyväksyttäviä ratkaisuja alku- ja kaksoisongelmiin, niin , ja tasa-arvo saavutetaan jos ja vain jos ja ovat optimaalisia ratkaisuja. Jos toisen kaksoistehtäväparin tavoitefunktiota ei ole rajoitettu (ylhäältä alkuperäiselle, alhaalta kaksoistehtävälle), toisen ongelman toteuttamiskelpoisten ratkaisujen alue on tyhjä. $x$ $y$ $F(x)\leqslant T(y)$ $x$ $y$

Jos vektorit ja ovat suorien ja kaksoisongelmien optimaalisia ratkaisuja, niin seuraavat yhtälöt ovat tosia $x^{*}$ $y^{*}$

x_{j}^{*}(\sum _{i=1}^{m}a_{ij}y_{i}^{*}-b_{j})=0,\;j={ \overline {1,\;n}};

y_{i}^{*}(\sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,\;i={ \overline {1,\;m}}.

Toisin sanoen primaali- ja kaksoisongelmien optimaalisille ratkaisuille ei-kireät (tiukka eriarvoisuus täyttyy) rajoitukset vastaavat nollaa muuttujaa ja nollasta poikkeavat muuttujat (sisältyvät tukisuunnitelmaan) vastaavat tiukkaa (ei-tiukka epäyhtälö toteutuu). tasa-arvon) rajoituksina. Mutta tiukkoja rajoituksia vastaavia muuttujia voi olla nolla.

Nämä kaksoisratkaisujen ominaisuudet voivat merkittävästi lyhentää ratkaisuaikaa, jos joudut ratkaisemaan ongelman useilla rajoituksilla, jotka ovat paljon suurempia kuin muuttujien lukumäärä. Sitten on mahdollista, kun kaksoistehtävä on ratkaistu, löytää sen tukisuunnitelma, jonka jälkeen, kun suorassa tehtävässä on valittu vain tukisuunnitelmaa vastaavat rajoitukset (kaikki nämä rajoitukset on jännityttävä), ratkaista tavallinen lineaarinen yhtälöjärjestelmä. heille.

Lause. Dual LP -ongelman duaali on primaali-LP-ongelma.

Todistus: Harkitse muodon suoraa LP: tä ehdon alla . Yhdistetään kaksois-LP siihen ja hankitaan ehdolla . Viedään se toiseen muotoon, merkitykseltään vastaava: ehdolla . Verrataanpa taas kaksois-LP:tä siihen ja saadaan ehdolla . Muutamme sen vastaavaan muotoon ja saamme alkuperäisen kanssa identtisen LP: n: ehdolla . ${\näyttötyyli \max c^{T))$ $Ax\leqslant b,x\geqslant 0$ ${\näyttötyyli \min b^{T}y}$ $A^{T}y\geqslant c,y\geqslant 0$ $\max -b^{T}y$ $-A^{T}y\leqslant -c,y\geqslant 0$ $\min -c^{T}x$ $-Ax\geqslant -b,x\geqslant 0$ ${\näyttötyyli \max c^{T))$ $Ax\leqslant b,x\geqslant 0$

Ohjelmisto

lp_solve on avoimen lähdekoodin ohjelmisto (LGPL GNU GNU General Public License for Libraries ) lineaaristen yhtälöiden ratkaisemiseen. LpSolvessa on IDE , natiivi C API ja monet muut sovellusliittymät Javalle, AMPL:lle, MATLAB:lle, Wolfram Mathematicalle, O-Matrixille, Sysquaken, Scilabille, Octavelle, FreeMatille, Eulerille, Pythonille, Sagelle, PHP:lle, R:lle ja Microsoft Solver Foundationille. .

Katso myös

Muistiinpanot

↑ 1 2 Lähde: Altai Regional Universal Scientific Library. V. Ya. Shishkova (AKUNB) Arkistoitu 5. maaliskuuta 2022 Wayback Machinessa . Optimointimenetelmät: Proc. korvaus. Brazovskaja N.V.; Altain osavaltion tekninen yliopisto I. I. Polzunova, [Etäisyyskeskus. oppiminen]. - Barnaul: AltGTU Publishing House, 2000. - 120 s. - ISBN 5-BNV-MOr.9.00 - UDC / LBC 22.183.4 B871.
↑ Dikin I. I. Lineaarisen ja toisen asteen ohjelmointiongelmien iteratiivinen ratkaisu // Dokl. Neuvostoliiton tiedeakatemia. - 1967. - T. 174 , nro 4 . - S. 747-748 .
↑ Karmanov, 1986 , s. 63.
↑ Karmanov, 1986 , s. 80.
↑ Karmanov, 1986 , s. 77.
↑ Sähköinen oppikirja "Taloudelliset ja matemaattiset menetelmät". Duality in Linear Programming Arkistoitu 17. kesäkuuta 2016 Wayback Machinessa

Kirjallisuus

Abramov L. M., Kapustin V. F. Matemaattinen ohjelmointi. - Opetusohjelma. - L .: LGU, 1981. - 328 s.
Akof R., Sasieni M. Operaatiotutkimuksen perusteet. — Per. englannista. V. Ya. Altaeva., toim. I. A. Ushakova. - M .: Mir, 1971. - 551 s.
Akulich I. L. Luku 1. Lineaarisen ohjelmoinnin ongelmat, Luku 2. Lineaarisen ohjelmoinnin erityistehtävät // Matemaattinen ohjelmointi esimerkeissä ja tehtävissä. - M . : Higher School, 1986. - 319 s. — ISBN 5-06-002663-9 .
Astafiev NN Äärettömät lineaaristen epäyhtälöiden järjestelmät matemaattisessa ohjelmoinnissa. - M .: Nauka, 1991. - 134 s.
Ashmanov S. A., Timokhov A. V. Optimointiteoria tehtävissä ja harjoituksissa. - M .: Nauka, 1991. - 446 s.
Gass S. Lineaarinen ohjelmointi. - M. : Fysikaalis-matemaattinen kirjallisuus, 1961. - 300 s.
Davydov E. G. Operaatiotutkimus. - M . : Higher School, 1990. - 382 s.
Degtyarev Yu. I. Operaatioiden tutkimus. — Oppikirja yliopistoille. - M . : Higher School, 1986. - 320 s.
Zukhovitsky S. I., Avdeeva L. I. Lineaarinen ja kupera ohjelmointi. - M .: Nauka, 1966. - 348 s.
Karmanov VG Matemaattinen ohjelmointi. – 3. painos. - M .: Nauka, 1986. - 288 s.
Kuznetsov A. V., Sakovich V. A., Kholod N. I. Korkeampi matematiikka. Matemaattinen ohjelmointi. - Minsk.: Higher School, 1994. - 286 s.
Thomas H. Kormen ym. Luku 29. Lineaarinen ohjelmointi // Algoritmit: Konstruointi ja analyysi = Johdanto algoritmeihin. - 2. painos - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
Yudin D. B. , Holstein E. G. Lineaarinen ohjelmointi. - M .: Nauka, 1969. - 424 s.
Dantzig JB Muistoja lineaarisen ohjelmoinnin alusta.
Gabasov R., Kirillova F. M. Lineaarisen ohjelmoinnin menetelmät. - Minsk: BGU, 1977. - 176 s.

Linkit

Linear Program Solver (LiPS) — Ilmainen optimointipaketti lineaari-, kokonaisluku- ja kohdeohjelmoinnin ongelmien ratkaisemiseen.
Vershik A. M. O L. V. Kantorovich ja lineaarinen ohjelmointi
Lineaariset ohjelmointidiat
Bolshakova I. V., Kuralenko M. V. Lineaarinen ohjelmointi. Ohjaustyön opetusapu . (downlink alkaen 13-05-2013 [3461 päivää])
Barsov A. S. Mikä on lineaarinen ohjelmointi // Suosittuja matematiikan luentoja , Gostekhizdat, 1959.
Vyalyi MN Lineaariset epäyhtälöt ja kombinatoriikka . – MTsNMO , 2003.

Sanakirjat ja tietosanakirjat

Bibliografisissa luetteloissa
BNF : 119415380 GND : 4035816-1 J9U : 987007555765405171 LCCN : sh85082127 NDL : 00570683 NKC : ph122356

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi