Yksinkertainen menetelmä

Ei pidä sekoittaa "simplex-menetelmään" - menetelmään mielivaltaisen funktion optimoimiseksi. Katso Nelder-Meadin menetelmä

Simpleksimenetelmä on algoritmi lineaarisen ohjelmoinnin optimointitehtävän ratkaisemiseksi laskemalla kuperan monitahoisen pisteet moniulotteisessa avaruudessa.

Menetelmän ydin: perusratkaisujen rakentaminen, joissa lineaarinen funktionaalisuus pienenee monotonisesti, kunnes tilanne, jossa paikallisen optimiteetin välttämättömät ehdot täyttyvät.

L. V. Kantorovichin teoksessa "Tuotannon organisoinnin ja suunnittelun matemaattiset menetelmät" (1939) esitettiin ensimmäisen kerran uuden matematiikan haaran periaatteet, joka myöhemmin tunnettiin nimellä lineaarinen ohjelmointi. [yksi]

Historiallisesti yleisen lineaarisen ohjelmoinnin ongelman esittivät ensimmäisen kerran vuonna 1947 George Bernard Dantzig , Marshall Wood ja heidän työtoverinsa Yhdysvaltain ilmavoimien osastolla. Tuolloin tämä ryhmä tutki mahdollisuutta käyttää matemaattisia ja niihin liittyviä menetelmiä sotilaallisiin ja suunnitteluongelmiin. Myöhemmin ilmavoimiin perustettiin Project SCOOP -tutkimusryhmä kehittämään näitä ideoita. Ensimmäinen onnistunut ratkaisu lineaarisen ohjelmoinnin ongelmaan SEAC-tietokoneella tehtiin tammikuussa 1952 [2] .

Kuvaus

Lineaarisen ohjelmoinnin ongelmana on, että on tarpeen maksimoida tai minimoida jokin lineaarinen funktio moniulotteisessa avaruudessa tietyillä lineaarisilla rajoituksilla.

Huomaa, että jokainen muuttujien lineaarinen epäyhtälö rajoittaa puoliavaruutta vastaavassa lineaarisessa avaruudessa. Tämän seurauksena kaikki epäyhtälöt rajoittavat jotakin kuperaa monitahoista (mahdollisesti ääretöntä), jota kutsutaan myös monitahoiseksi kompleksiksi . Yhtälö W ( x ) = c , jossa W ( x ) on maksimoitu (tai minimoitu) lineaarinen funktio, generoi hypertason L(c) . Riippuvuus c : stä luo rinnakkaisten hypertasojen perheen. Sitten äärimmäinen ongelma saa seuraavan formulaation: vaaditaan suurin c niin, että hypertaso L(c) leikkaa monitahoisen ainakin yhdessä pisteessä. Huomaa, että optimaalisen hypertason ja monitahoisen leikkauspisteessä on vähintään yksi kärki, ja niitä on enemmän kuin yksi, jos leikkauskohta sisältää reunan tai k - ulotteisen pinnan. Siksi funktionaalin maksimi voidaan etsiä monitahoisen kärjestä. Simpleksimenetelmän periaate on, että valitaan yksi monitahoisen kärjestä, jonka jälkeen liike sen reunoja pitkin kärjestä kärkeen alkaa funktionaalin arvon kasvun suuntaan. Kun siirtyminen reunaa pitkin nykyisestä kärjestä toiseen kärkeen, jolla on korkeampi funktion arvo, katsotaan, että c :n optimaalinen arvo on löydetty.

Simplex-menetelmällä suoritettavat laskelmat voidaan jakaa kahteen päävaiheeseen :

löytää mahdollisten ratkaisujen joukon alkupiste,
peräkkäinen siirtyminen kärjestä toiseen, mikä johtaa tavoitefunktion arvon optimointiin.

Lisäksi joissain tapauksissa alkuperäinen ratkaisu on ilmeinen tai sen määrittely ei vaadi monimutkaisia laskelmia, esimerkiksi kun kaikki rajoitukset esitetään epäyhtälöillä, jotka ovat muotoa "pienempi tai yhtä suuri" (niin nollavektori on ehdottomasti käyttökelpoinen ratkaisu , vaikka todennäköisimmin se on kaukana optimaalisimmasta). Tällaisissa ongelmissa simplex-menetelmän ensimmäinen vaihe voidaan jättää kokonaan pois. Yksivaiheinen menetelmä on jaettu yksivaiheiseen ja kaksivaiheiseen .

Simpleksimenetelmän algoritmi

Vahvistettu ongelmanselvitys

Harkitse seuraavaa lineaarista ohjelmointiongelmaa :

c^{T}x\to \max ,Ax\leqslant b,x\geqslant 0,b\geqslant 0.

Esitetään nyt tämä ongelma vastaavassa parannetussa muodossa. On tarpeen maksimoida Z , jossa:

{\begin{bmatrix}1&-c^{T}&0\\0&A&E\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{ bmatrix}0\\b\end{bmatrix}},x,x_{s}\geqslant 0

Tässä x ovat muuttujia alkuperäisestä lineaarifunktiosta, x s ovat uusia muuttujia, jotka täydentävät vanhoja siten, että epäyhtälö muuttuu tasa-arvoksi, c ovat alkuperäisen lineaarifunktion kertoimet, Z on maksimoitava muuttuja. Puoliavaruudet ja leikkauspiste muodostavat monitahoisen, joka edustaa mahdollisia ratkaisuja. Muuttujien lukumäärän ja yhtälöiden välinen ero antaa meille vapausasteiden lukumäärän. Yksinkertaisesti sanottuna, jos otamme huomioon monitahoisen kärjen, tämä on niiden reunojen lukumäärä, joita pitkin voimme jatkaa liikkumista. Sitten voimme antaa tälle muuttujien lukumäärälle arvon 0 ja kutsua niitä "ei-perus" . Tässä tapauksessa loput muuttujat lasketaan yksiselitteisesti ja niitä kutsutaan "perus" . Samaa näiden muuttujien joukkoa kutsutaan kantaksi . Tuloksena oleva piste on ei-perusmuuttujia vastaavien hypertasojen leikkauspiste. Löytääkseen ns. Alkuperäisen hyväksyttävän ratkaisun (kärkipisteen, josta lähdemme liikkumaan), annamme arvon 0 kaikille alkumuuttujille x ja pidämme niitä ei-perusmuuttujina ja kaikkia uusia pidetään perusmuuttujina. Tässä tapauksessa alkuperäinen hyväksyttävä ratkaisu lasketaan yksiselitteisesti: . $x\geqslant 0$ $x_{s}\geqslant 0$ ${\mathbf {x}}_{{si}}={\mathbf {b}}_{i}$

Algoritmi

Nyt esittelemme algoritmin vaiheet. Jokaisessa vaiheessa muutamme perus- ja ei-perusvektoreiden joukot (siirrämme reunoja pitkin), ja matriisi näyttää tältä:

{\begin{bmatrix}1&c_{B}^{T}B^{{-1}}Ac^{T}&c_{B}^{T}B^{{-1}}\\0&B^{{- 1}}A&B^{{-1}}\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{bmatrix}c_{B} ^{T}B^{{-1}}b\\B^{{-1}}b\end{bmatrix}},

missä ovat perusmuuttujia vastaavan vektorin kertoimet (muuttujat vastaavat 0), ovat perusmuuttujia vastaavat sarakkeet . Muiden sarakkeiden muodostama matriisi on merkitty . Miksi matriisilla on tämä muoto, selitetään algoritmin vaiheiden kuvauksessa. $c_{B}$ $c$ $x_{s}$ $B$ $[{\mathbf {A}}{\mathbf {E}}]$ $D$

Ensimmäinen askel .

Valitsemme alkuperäisen kelvollisen arvon, kuten yllä on osoitettu. Ensimmäisessä vaiheessa identiteettimatriisi, koska perusmuuttujat ovat . on nollavektori samoista syistä. $B$ $x_{s}$ $c_{B}$

Toinen vaihe

Osoitetaan, että lausekkeessa vain ei-perusmuuttujilla on nollasta poikkeava kerroin. Huomaa, että lausekkeesta perusmuuttujat ilmaistaan yksiselitteisesti ei-perusmuuttujilla, koska perusmuuttujien lukumäärä on yhtä suuri kuin yhtälöiden lukumäärä. Olkoon perus- ja ei-perusmuuttujia tietyssä iteraatiossa. Yhtälö voidaan kirjoittaa uudelleen muotoon . Kerrotaan se vasemmalla olevalla: . Esitimme siis perusmuuttujat ei-perusmuuttujina, ja yhtälön vasenta puolta vastaavassa lausekkeessa kaikilla perusmuuttujilla on yksikkökertoimet. Jos siis lisätään yhtäläisyys yhtäläisyyteen , niin tuloksena olevassa yhtäläisyydessä kaikilla perusmuuttujilla on nollakerroin - kaikki x -muodon perusmuuttujat pienennetään, eikä muotoa x s olevia perusmuuttujia sisällytetä lausekkeeseen . $(c_{B}^{T}B^{{-1}}Ac^{T})x+(c_{B}^{T}B^{{-1}})x_{s}$ $Ax+x_{s}=b$ $x'$ $x''$ $Ax+x_{s}=b$ $Bx'+Dx''=b$ $B^{{-1}}$ $x'+B^{{-1}}Dx''=B^{{-1}}b$ $B^{{-1}}Ax+B^{{-1}}x_{s}$ $Zc^{T}x=0$ $c_{B}^{T}B^{{-1}}Ax+c_{B}^{T}B^{{-1}}x_{s}$ $c_{B}^{T}B^{{-1}}x_{s}$

Valitaan reuna, jota pitkin liikumme. Koska haluamme maksimoida Z , on tarpeen valita muuttuja, joka vähentää lauseketta eniten

$(c_{B}^{T}B^{{-1}}Ac^{T})x+(c_{B}^{T}B^{{-1}})x_{s}$ .

Tätä varten valitsemme muuttujan, jolla on suurin negatiivinen kerroin moduulissa [3] . Jos tällaisia muuttujia ei ole, eli kaikki tämän lausekkeen kertoimet ovat ei-negatiivisia, olemme päässeet haluttuun kärkeen ja löytäneet optimaalisen ratkaisun. Muuten alamme kasvattaa tätä ei-perusmuuttujaa, eli liikkua sitä vastaavaa reunaa pitkin. Kutsutaan tätä muuttujaa syötteeksi .

Kolmas vaihe

Nyt meidän on ymmärrettävä, mikä perusmuuttuja menee ensin nollaan, kun syöttömuuttuja kasvaa. Tätä varten riittää, että harkitset järjestelmää:

{\begin{bmatrix}B^{-1}A&B^{-1}\end{bmatrix}}{\begin{bmatrix}x\\x_{s}\end{bmatrix}}=B^{ -1}b

Ei-perusmuuttujien kiinteille arvoille järjestelmä on yksiselitteisesti ratkaistavissa perusmuuttujien suhteen, joten voimme määrittää, mikä perusmuuttujista saavuttaa ensimmäisenä nollan syötteen kasvaessa. Kutsutaan tätä muuttujaa ulostuloksi . Tämä tarkoittaa, että olemme saavuttaneet uuden huipun. Vaihdetaan nyt saapuvat ja lähtevät muuttujat - saapuva "syöttää" perusmuuttujaan ja lähtevä "lähtee" ei-perusmuuttujat. Nyt kirjoitetaan matriisi B ja vektori c B uusien perus- ja ei-perusmuuttujien joukkojen mukaisesti, minkä jälkeen palataan toiseen vaiheeseen. x''

Koska pisteiden määrä on äärellinen, algoritmi jonain päivänä päättyy. Löytynyt kärkipiste on optimaalinen ratkaisu.

Kaksivaiheinen simpleksimenetelmä

Syitä käyttää

Jos lineaarisen ohjelmointitehtävän tilanteessa kaikkia rajoituksia ei edusta "≤"-tyyppiset epäyhtälöt, niin nollavektori ei aina ole kelvollinen ratkaisu. Yksipuolisen menetelmän jokainen iteraatio on kuitenkin siirtymä pisteestä toiseen, ja jos kärkeä ei tunneta, algoritmia ei voida käynnistää ollenkaan.

Alkupisteen löytämisprosessi ei eroa paljoa yksivaiheisesta simpleksimenetelmästä, mutta se voi olla vaikeampaa kuin jatkooptimointi.

Rajoituksen muutokset

Kaikkia tehtävärajoituksia muokataan seuraavien sääntöjen mukaisesti:

"≤"-tyypin rajoitukset muunnetaan yhtäläisiksi luomalla lisämuuttuja kertoimella "+1". Tämä muunnos suoritetaan myös yksivaiheisessa simplex-menetelmässä, lisämuuttujia käytetään edelleen alkuperustana.
tyypin "≥" rajoituksia täydennetään yhdellä muuttujalla, jonka kerroin on " -1 ". Koska tällaista muuttujaa ei voida käyttää alkuperäisessä perustassa negatiivisen kertoimen vuoksi, on tarpeen luoda yksi apumuuttuja lisää . Apumuuttujat luodaan aina kertoimella "+1".
"="-tyypin rajoituksia täydennetään yhdellä apumuuttujalla.

Tämän mukaisesti luodaan joukko lisä- ja apumuutujia. Aluksi valitaan lisämuuttujat kertoimella "+1" ja kaikki apumuuttujat. Varoitus: Ratkaisu, jota tämä peruste vastaa, ei ole hyväksyttävä.

Erot lisä- ja lisämuuttujien välillä

Huolimatta siitä, että sekä lisä- että apumuuttujat luodaan keinotekoisesti ja niitä käytetään alkuperäisen perustan luomiseen, niiden arvot ratkaisussa ovat hyvin erilaisia:

lisämuuttujat kertovat, kuinka "alikäytössä" niiden vastaava rajoitus on. Lisämuuttujan arvo, joka on yhtä suuri kuin nolla, vastaa rajoitteen oikean ja vasemman osan arvojen yhtäläisyyttä.
apumuuttujat kertovat kuinka kaukana annettu ehto on hyväksyttävästä (suhteessa tiettyyn rajoitteeseen). Jos apumuuttujan arvo on suurempi kuin nolla, tämä ratkaisu ei täytä tiettyä rajoitusta, joten se ei ole kelvollinen.

Toisin sanoen lisämuuttujan nollasta poikkeava arvo voi (mutta ei saa) osoittaa, että ratkaisu ei ole optimaalinen . Apumuuttujan nollasta poikkeava arvo osoittaa, että ratkaisu on virheellinen .

Päätöksen vaiheet

Kun ehtoa on muutettu, luodaan aputavoitteen funktio . Jos apumuuttujat nimettiin , niin määritämme apufunktioksi $y_{i}$ ${\displaystyle i\in \left\{1,\dots ,k\right\))$

z'=\sum _{{i=1}}^{k}y_{i}\to min

Tämän jälkeen suoritetaan tavallinen simpleksimenetelmä aputavoitteen funktion suhteen. Koska kaikki apumuuttujat lisäävät arvoa , ne johdetaan algoritmin aikana yksitellen perusteesta ja jokaisen siirtymän jälkeen uusi ratkaisu on lähempänä toteutettavissa olevien ratkaisujen joukkoa. $z'$

Kun aputavoitteen funktion optimaalinen arvo löytyy, voi syntyä kaksi tilannetta:

optimaalinen arvo on suurempi kuin nolla. Tämä tarkoittaa, että ainakin yksi apumuuttujista jäi pohjaan. Tässä tapauksessa voimme päätellä, että tähän lineaariseen ohjelmointiongelmaan ei ole toteutettavissa olevia ratkaisuja. $z'$
optimaalinen arvo on nolla. Tämä tarkoittaa, että kaikki apumuuttujat on poistettu kannasta ja nykyinen ratkaisu on voimassa. $z'$

Toisessa tapauksessa meillä on hyväksyttävä peruste tai toisin sanoen ensimmäinen hyväksyttävä ratkaisu. On mahdollista suorittaa lisäoptimointi ottamalla huomioon alkuperäinen tavoitefunktio, huomioimatta apumuuttujia. Tämä on ratkaisun toinen vaihe.

Muokattu simpleksimenetelmä

Modifioidussa menetelmässä matriisi

${\begin{bmatrix}1&c_{B}^{T}B^{{-1}}Ac^{T}&c_{B}^{T}B^{{-1}}\\0&B^{{- 1}}A&B^{{-1}}\end{bmatrix}}$

ei lasketa uudelleen, vain matriisi tallennetaan ja lasketaan uudelleen . Loppuosa algoritmista on samanlainen kuin yllä kuvattu. $B^{{-1}}$

1. Laske kaksoismuuttujat $d=c_{B}^{T}B^{{-1}}$

2. Optimiteetin tarkistaminen. muunnetaan muotoon . $c_{B}^{T}B^{{-1}}Ac^{T}$ $d^{T}Ac^{T}$

Tarkistuksessa lasketaan kaikki sarakkeet . Perusteelle voidaan syöttää sarake, jonka arvo on < 0. $d^{T}A_{n}-c_{n}$ $n\in N$

Valitse usein vähimmäisarvo, mutta tätä varten sinun on iteroitava kaikki sarakkeet.

Valitse useammin arvo, joka on pienempi kuin jokin annettu arvo $-\varepsilon$

Jos tällaista saraketta ei löydy, suurimmaksi löydetty absoluuttinen arvo otetaan löydetyksi ja vastaava sarake syötetään perusteeseen. $\varepsilon$ $A_{J}$

3. Tuotoksen määritelmä.

Olkoon muuttujaa vastaava syöttösarake.Perussuunnitelma on ratkaisu järjestelmään Increase . $A_{J}$ $x_{J}$ $A_{B}p=b$ $A_{B}p+\vartheta A_{J}=b$

Kerro vasemmalla puolella , eli . $B^{{-1}}$ $B^{{-1}}A_{B}p+\vartheta B^{{-1}}A_{J}=B^{{-1}}b$

Tässä on perussuunnitelma, on laajennus tulosarakkeen kannalta perusteella. $B^{{-1}}b$ $q=B^{{-1}}A_{J}$

Etsi suurin arvo , jonka kaikki arvot eivät ole negatiivisia. Jos voidaan ottaa mielivaltaisen suuri, ratkaisu on rajaton. Muuten yksi elementeistä menee nollaan. Päättelemme vastaavan sarakkeen perusteesta. $\vartheta$ $\vartheta$

4. Viite- (perus)suunnitelman uudelleenlaskenta.

Laskemme uuden vertailusuunnitelman käyttämällä jo annettua kaavaa löydetyllä arvolla . $x=p+\vartheta B^{{-1}}A_{J}$ $\vartheta$

5. Laskemme käänteisen uudelleen kantaan . $B^{{-1}}$

Antaa olla tulossarake. $B^{{-1}}A_{F}$

Matriisi B voidaan esittää muodossa $[B_{G}A_{F}]$

missä on perusmatriisi ilman tulossaraketta. $B_{G}$

Sarakkeen vaihtamisen jälkeen perusmatriisi näyttää tältä $[B_{G}A_{J}]$

Meidän on löydettävä sellainen matriisi $B_1$

$[B_{G},A_{J}]B_{1}^{{-1}}=E$ => => => $[B^{{-1}}B_{G}B_{1}^{{-1}},B^{{-1}}A_{J}]=B^{{-1}}$ $[B^{{-1}}B_{G},q]B_{1}^{{-1}}=B^{{-1}}$

${\begin{bmatrix}E&q'\\0&q_{f}\end{bmatrix}}B_{1}^{{-1}}=B^{{-1}}$

Missä $B_{1}^{{-1}}={\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix}}B^{{-1}}$

Kommentti.

Matriisin uudelleenlaskenta kerää pyöristysvirheitä. Suurten virheiden välttämiseksi matriisi lasketaan kokonaan uudelleen ajoittain. Tätä prosessia kutsutaan "toistoksi". $B^{{-1}}$

Yksipuolisen menetelmän moninkertainen versio

Kertovassa versiossa matriisia ei tallenneta, vain tekijät tallennetaan $B^{{-1}}$ ${\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix))$

Taloudellisia ongelmia ratkaistaessa rajoitematriisi on usein harva , jolloin kertova vaihtoehto saa lisäetuja - voit tallentaa kertoimia pakatussa muodossa (älä tallenna nollia).

Muita simpleksimenetelmän muunnelmia

Matriisin LU - hajotusta voidaan käyttää pyöristysvirheiden kertymisen välttämiseksi .

"Epäyhtälö"-tyyppisten rajoitusten ylivoimaisella määrällä voidaan käyttää muuttujapohjaista menetelmää . [neljä]

Menetelmä perustuu siihen, että kantamatriisi voidaan esittää muodossa

${\begin{bmatrix}A_{B}&0\\A_{E}&E\end{bmatrix}}$

Sen käänteisversiolla on muoto

${\begin{bmatrix}A_{B}^{{-1}}&0\\-A_{B}^{{-1}}A_{E}&E\end{bmatrix}}$

Suhteellisen pienillä matriisikooilla matriisin loppuosaa ei ehkä tallenneta. $A_{B}^{{-1}}$

Tämä lähestymistapa voi ratkaista ongelmia kymmenillä miljoonilla rajoituksilla (esimerkiksi peliteorian perusteella).

Dual simplex -menetelmä

Kaksoismenetelmän toteuttamiseksi on välttämätöntä siirtyä ongelmasta minimiin ongelmaan maksimiin (tai päinvastoin) transponoimalla kertoimien matriisi. Kun siirrytään tehtävästä minimiin, tavoitefunktio on muodossa:

$g=\sum _{{i=1}}^{n}b_{i}y_{i}\to max$

rajoitusten alla

${\displaystyle \sum _{i=1}^{n}a_{ij}y_{i}\leq c_{j))$ .

Kaksinaisuuslause . Jos toisella kaksoistehtäväparista on optimaalinen suunnitelma, niin toisella on ratkaisu, ja näiden tehtävien lineaarifunktioiden ääriarvot ovat yhtä suuret.

Jos yhden ongelman lineaarista funktiota ei ole rajoitettu, toisella ei ole ratkaisua.

Laskennallinen tehokkuus

Simpleksimenetelmä on yllättävän tehokas käytännössä, mutta vuonna 1972 Klee ja Minty [5] antoivat esimerkin, jossa simpleksimenetelmä iteroitui kaikki simplexin kärjet, mikä osoittaa menetelmän eksponentiaalisen konvergenssin pahimmassa tapauksessa. Sen jälkeen jokaiselle menetelmän muunnokselle on löydetty esimerkki, jossa menetelmä on toiminut poikkeuksellisen huonosti.

Havainnot ja analyysi menetelmän tehokkuudesta käytännön sovelluksissa johtivat muiden tapojen kehittämiseen tehokkuuden mittaamiseksi.

Simplex-menetelmällä on keskimääräinen polynomikonvergenssi , jossa on laaja valikoima arvojakaumia satunnaismatriiseissa. [6] [7]

Laskennallinen tehokkuus arvioidaan yleensä kahdella parametrilla:

ratkaisun saamiseksi tarvittavien iteraatioiden lukumäärä;
koneen aikakustannukset.

Numeeristen kokeiden tuloksena saatiin seuraavat tulokset.

Iteraatioiden määrä lineaarisen ohjelmoinnin ongelmien ratkaisemisessa vakiomuodossa rajoituksilla ja muuttujilla on välillä ja . Keskimääräinen iteraatioiden määrä . Iteraatioiden lukumäärän yläraja on . $m$ $n$ $m$ $3m$ $2 m$ $2m+n$
Tarvittava koneen aika on verrannollinen . $m^{3}$

Rajoitusten määrä vaikuttaa laskennan tehokkuuteen enemmän kuin muuttujien lukumäärä, joten lineaarisia ohjelmointiongelmia muotoiltaessa tulee pyrkiä vähentämään rajoitusten määrää, vaikka muuttujien määrää lisäämällä.

Menetelmiä tehokkuuden parantamiseksi

Yksi aikaa vievistä toimenpiteistä simplex-menetelmässä on kantaan lisätyn sarakkeen etsiminen. Paremman konvergenssin saavuttamiseksi näyttää siltä, että sinun on valittava muuttuja, jolla on paras jäännös, mutta tämä vaatii täyden skannauksen, eli sinun on kerrottava kaksoismuuttujien sarake (jota joskus kutsutaan varjohinnoiksi) matriisin kaikilla sarakkeilla. [8] . Tämä lähestymistapa toimii hyvin pienissä ongelmissa, jotka ratkaistaan manuaalisesti. Lisäksi moduulin maksimijäännösarvon valintasäännön tiukka noudattaminen voi osoittautua optimaalista ääripään saamiseksi vaadittavien iteraatioiden kokonaismäärän kannalta. Maksimivahvistus yhdellä iteraatiolla voi johtaa tavoitefunktion arvon hitaaseen laskuun seuraavissa vaiheissa ja siten hidastaa ongelman ratkaisuprosessia [9] .

Suurilla rajoitematriiseilla syötemuuttujan etsiminen alkaa viedä paljon aikaa, ja usein yritetään välttää matriisin kaikkien sarakkeiden katsomista, jolloin voidaan käyttää seuraavia menetelmiä:

Este . Heti kun muuttujan poikkeama poikkeaa riittävästi nollasta (ylittää tietyn arvon, jota kutsutaan esteeksi), muuttuja lisätään kantaan. Jos kaikki jäännökset osoittautuivat estettä pienemmiksi, syötteeksi valitaan muuttuja, jolla on pienin jäännös, kun taas itse este pienennetään jonkin säännön mukaan (esimerkiksi puolet pienimmästä jäännöksestä). Estettä käytetään usein seuraavan tekniikan kanssa. Samanlainen lähestymistapa on kuvattu Murtaughin kirjassa, katso kohta 3.6.2. Kirjan osittainen arviointi [10] . Pyöräilynäkymä . Syötemuuttujan haku alkaa edellisessä iteraatiossa esiteltyä muuttujaa seuraavasta paikasta. Ryhmävalinta (Murtaughin kirjassa tätä tekniikkaa kutsutaan moninkertaiseksi arvioimiseksi . Katso kohta 3.6.3. Moniarviointi [11] .) Syöttömuuttujaa haettaessa ei valita yhtä muuttujaa, vaan useita ehdokkaita. Seuraavissa iteraatioissa katselu suoritetaan vain valittujen ehdokkaiden kesken, kun taas ehdokas voidaan poistaa listalta. Vaakojen tarkoitus . Muuttujille on annettu painoarvot. Katso kohta 3.6.4 Murtafan DEVEX- pisteytysmenetelmä [12] . Etsi Goldfarbin ja Reedin jyrkimpiä kylkiluita. Katso kohta 3.6.5 Jyrkimmän reunan estimointimenetelmä Murtaughin kirjassa [13] .

Myös muut temput ovat mahdollisia, kuten Zadeh-sääntö .

Muistiinpanot

↑ Kantorovich L. V. Matemaattiset menetelmät tuotannon suunnittelun järjestämiseen // Leningradin valtionyliopiston painos. - Leningrad, 1939.
↑ S. Gass. Lineaarinen ohjelmointi (menetelmät ja sovellukset). - Moskova: Valtion fyysisen ja matemaattisen kirjallisuuden kustantaja, 1961. - (Insinöörin fyysinen ja matemaattinen kirjasto).
↑ Tämä suositus löytyy usein oppikirjoista, mutta se ei aina pidä paikkaansa. Katso #Menetelmät tehokkuuden parantamiseksi
↑ V.I. Muravjov. Jaksottainen parannusmenetelmä vaihtelevan koon perusteella lineaarisen ohjelmoinnin ongelmiin. — Kokoelma "Tilastollisen mallinnuksen toimintojen ja menetelmien tutkimus". - Leningrad: Leningradin valtionyliopisto, 1972.
↑ Klee, Victor; Minty, George J. Kuinka hyvä simplex-algoritmi on? // Inequalities III (Proceedings of the Third Symposium on Inequalities, joka pidettiin Kalifornian yliopistossa Los Angelesissa, Kaliforniassa, 1.–9. syyskuuta 1969, omistettu Theodore S. Motzkinin muistolle) (englanniksi) / Shisha, Oved. - New York-Lontoo: Academic Press , 1972. - P. 159-175.
↑ Alexander Schrijver, Lineaarisen ja kokonaislukuohjelmoinnin teoria . John Wiley & sons, 1998, ISBN 0-471-98232-6 (matemaattinen)
↑ Simpleksialgoritmi kestää keskimäärin D askelta kuutiolle. Borgwardt, Karl-Heinz. Simpleksimenetelmä : Todennäköisyysanalyysi . - Berlin: Springer-Verlag , 1987. - Voi. 1. - P.xii+268. - (Algoritmit ja kombinatoriikka (tutkimus- ja tutkimustekstit)). - ISBN 3-540-17096-0 .
↑ Suositus residuaalin suurimman moduloarvon valitsemiseksi löytyy usein simplex-menetelmän kuvauksista, esimerkiksi artikkeleista Simplex-menetelmän algoritmi Arkistoitu 17. maaliskuuta 2018 Wayback Machinessa ja SIMPLEX LINEAR PROGRAMMING METHOD Arkistoitu 17. maaliskuuta 2018 Wayback Machinessa
↑ Shamray, 2009 , s. 44.
↑ Murtaf, 1984 .
↑ Murtaf, 1984 , s. 61.
↑ Murtaf, 1984 , s. 62.
↑ Murtaf, 1984 , s. 63.

Kirjallisuus

Hemdy A. Taha. Luku 3. Simplex-menetelmä // Johdatus operaatiotutkimukseen = Operations Research: An Introduction. - 7. painos - M . : "Williams" , 2007. - S. 95-141. — ISBN 0-13-032374-8 .
Akulich I.L. Luku 1. Lineaarisen ohjelmoinnin tehtävät // Matemaattinen ohjelmointi esimerkeissä ja tehtävissä. - M . : Korkeakoulu , 1986. - 319 s. — ISBN 5-06-002663-9 .
Thomas H. Kormen ym. Luku 29 Lineaarinen ohjelmointi // Algoritmit: Konstruointi ja analyysi = ALGORITMEIN JOHDANTO. - 2. painos - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
V. N. Shevchenko, N. Yu. Zolotykh. Lineaarinen ja kokonaisluku Lineaarinen ohjelmointi . - Nižni Novgorod: Nizhny Novgorod State Universityn kustantamo. N.I. Lobachevsky, 2004. - P. 63 -66 (osio 2.8. Huomautuksia LLP:n ratkaisemisen monimutkaisuudesta). — ISBN 5-85746-761-6 .
Shamray Natalya Borisovna. Käytännön lineaarinen ohjelmointi ekonomisteille . - Vladivostok: Far Eastern Universityn kustantamo, 2009. - S. 44. - ISBN 978-5-7444-2215-8 . Arkistoitu 17. maaliskuuta 2018 Wayback Machinessa
Murtaf B. Moderni lineaarinen ohjelmointi. - Moskova: Mir, 1984.

Linkit

Sanakirjat ja tietosanakirjat	Britannica (verkossa)
Bibliografisissa luetteloissa	GND : 4181488-5 J9U : 987007546249105171 LCCN : sh85122745

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