Potentiaalinen menetelmä

Potentiaalinen menetelmä on lineaarisen ohjelmointiongelman ratkaisun simpleksimenetelmän muunnos suhteessa kuljetusongelmaan . Se mahdollistaa jostain toteuttamiskelpoisesta ratkaisusta alkaen saada optimaalisen ratkaisun äärellisessä määrässä iteraatioita.

Kuljetusongelman muotoilu

Lavastusta on kahta tyyppiä - matriisi ja verkko. Matriisiformulaatiossa kuljetus on sallittu vain tuottajalta kuluttajalle. Verkkoympäristössä kuljetus voidaan suorittaa mihin tahansa suuntaan (pisteet voivat olla kauttakulkua). Olkoon tuotanto-/kulutuspisteitä, kuljetuskaareja , rahtihintoja kaaria pitkin ja joukko perussarakkeita. $M$ $N$ $C[N]$ $N$ $HUOM}$

Tehtävä on muotoiltu [1]

löytö $min(C[N]x[N])$

olosuhteissa $A[M,N]x[N]=b[M]$

missä - kuljetuskustannukset kaareina, - tuotanto (+) / kulutus (-) $C[N]$ $b[M]$

$x[N]$ - ratkaisu

Kuljetusongelman rajoitusmatriisi koostuu sarakkeista, joissa on vain kaksi nollasta poikkeavaa elementtiä - +1 tuottajalle ja -1 kuluttajalle [2] . $A[M,N]$

Huomautus: Yleisesti ottaen mikä tahansa matriisin neliömatriisi (eli ) on degeneroitunut, joten jotta simpleksimenetelmä toimisi, on tarpeen ottaa käyttöön keinotekoisia muuttujia tai jättää yksi rivi huomiotta. Käytettäessä kaatopaikkaa (katso alla), sitä vastaava rivi jätetään huomioimatta. $A[M,M']$ $|M'|=|M|,M'\subset N$ $A[M,N]$

Algoritmi

Potentiaalimenetelmä on muunnos simpleksimenetelmästä, jossa kantamatriisi on esitetty puuna [3] . $B[M,N_{B}]$

Kuljetusongelman simpleksimenetelmän kaksoismuuttujia kutsutaan potentiaalisiksi .

Potentiaalit lasketaan kaavalla , joka vastaa $P[M]$ $C[N_{B}]=B[M,N_{B}]P[M]$ $P[M]=C[N_{B}]B^{{-1}}[N_{B},M]$

Kaarelle kaarien potentiaalit suhteutetaan kaavalla . $n(i\nuoli oikealle j)\in N_{B}$ $P[i]+C[n]=P[j]$

Siten kuluttajan potentiaali on sama kuin tuottajan potentiaali + kuljetuskustannukset. Taloudellisesta näkökulmasta tämä voidaan tulkita tuotteen kustannuksiksi kulutuspisteessä.

Suunnitelman optimaalisuuden tarkistaminen on taloudellisesti helposti tulkittavissa - jos tuotteen hinta kulutuspisteessä on suurempi kuin tuotantokustannukset + kuljetushinta, tämä kaari tulee kuljettaa. Suuruutta kutsutaan jäännöskaareksi . $P[i]+C[n]\geq P[j]$ $P[j]-P[i]-C[n]$

Kaaren lisääminen aiheuttaa puussa syklin. Kelkan lisäys syötettyä kaaria pitkin johtaa virtausten uudelleenlaskentaan jakson aikana, jolloin kuljetus pitkin yhtä kaaria laskee nollaan. Kaari, jonka virtaus on nolla, poistetaan kannasta, kun taas kantagraafi pysyy puuna (sykli katkeaa).

Jää vain laskea uudelleen potentiaalit - lisää (tai vähennä - riippuu kaaren suunnasta) kaikkiin "riippuvan haaran" kärkiin jäännösarvolla $P[j]-P[i]-C[n]$

Prosessi päättyy, kun optimaalisuusehto täyttyy kaikille kaarille. $P[i]+C[n]\geq P[j]$

Avaa ongelmat

Ongelma on suljettu, jos tuotantojen summa on yhtä suuri kuin kulutuksen summa.

Yleensä ympäristössä tuotannon määrä on suurempi kuin kulutuksen määrä. Ei-suljettujen ongelmien ratkaisemiseksi sekä alkuperäisen perussuunnitelman saamisen helpottamiseksi käytetään keinotekoista perusmenetelmää [4] . Tätä varten alkuperäistä kaaviota laajennetaan, otetaan käyttöön "kaatopaikka" - lisäpiste, johon kaikki ylituotanto tuodaan nollahintaan.

Jos tuodaan kaareja kaatopaikalta kulutuspisteille erittäin korkealla hinnalla, alkuratkaisu rakentuu triviaalisti - kuljetamme kaiken tuotannon kaatopaikalle, kaiken kulutuksen kaatopaikalta.

Kaaret tuotantopisteistä kaatopaikalle vastaavat lisämuuttujia simplex-menetelmässä ja kaareet kaatopaikalta kulutuspisteisiin vastaavat keinotekoisia muuttujia .

Luoteiskulmamenetelmä

Matriisikuljetusongelmalle toinen algoritmi alkuperäisen suunnitelman rakentamiseksi on mahdollinen.

1. Valitse jokin kärkipiste i.

2. Valitse kaaritapahtuma i:lle. Asetetaan kaaren virtaus kaaren päissä olevien tuotanto- ja kulutusmäärien minimiin. Pienennetään näitä tilavuuksia kaaren virtauksen määrällä. Jätämme huomioimatta pisteen, jonka tilavuus on nolla, yhdessä siihen tulevien kaarien kanssa. Siirrytään kohtaan 2.

Jos tuotannon ja kulutuksen huiput numeroidaan uudelleen ja joka kerta kun valitaan pienimmän numeron omaava kaari, menetelmää kutsutaan luoteiskulmamenetelmäksi [5] .

Muutama huomio algoritmin tehokkuudesta

Lähtökaaren määrittely ja potentiaalien uudelleenlaskenta toteutetaan varsin tehokkaasti. Pääasiallinen ajan "kuluttaja" on optimitarkistus [6] .

Optimaalisuuden tarkistamiseen kuluvan ajan lyhentämiseksi käytetään useita menetelmiä.

1. Esteen avulla - heti kun poikkeaman arvo on suurempi kuin tietty arvo, tuomme kaaren kantaan menemättä muiden kaarien läpi. Jos kaaria ei löydy, vähennämme esteen havaittuun enimmäispoikkeamaan ja lisäämme vastaavan kaaren kantaan.

2. Syklinen näkymä - haku alkaa kohdasta, johon se pysähtyi edellisessä näkymässä.

3. "Hakijoiden" valinta - katseltaessa ei valita yhtä kaaria, vaan useita. Seuraavassa vaiheessa vain valitut kaaret tarkistetaan.

Perusmatriisin determinantti on aina 1, joten kokonaislukutiedolla tehtävä antaa kokonaislukuratkaisuja.

Kaistanleveysrajoitukset

Joillekin kaareille voidaan asettaa kaistanleveysrajoituksia . Pieni algoritmin monimutkaisuus voi ratkaista ongelman rajoitetulla kaistanleveydellä [7] . $N_{L}$ $L[N_{L}]$

löytö $min(C[N]x[N])$

olosuhteissa

$A[M,N]x[N]=b[M]$

$E[N_{L},N_{L}]x[N_{L}]+E[N_{L},N_{L}]p[N_{L}]=L[N_{L}]$

Tässä — lisämuuttujia (otettu käyttöön epätasa-arvon muuttamiseksi tasa-arvoksi). $p[N_{L}]$

Perus koostuu kolmesta sarjasta - , ja . $HUOM}$ $N_{{BN}}$ $N_{{BL}}$ $N_{{BP}}$

missä ovat kaaret, jotka vastaavat tavallisia rajoituksia ( ) $N_{{BN}}$ $M$

$N_{{BL}}$ — kaaret, jotka ovat saavuttaneet kaistanleveyden rajan (kyllästyt kaaret) ( ) $x[N_{L}]$

$N_{{BP}}$ — kaaret, jotka eivät ole saavuttaneet kaistanleveysrajaa (vastaavat lisämuuttujia)( ) $p[N_{L}]$

Perusmatriisilla on muoto ${\begin{bmatrix}A[M,N_{{BN}}]&A[M,N_{{BL}}]&0[M,N_{{BP}}]\\0[N_{{BL}}, N_{{BN}}]&E[N_{{BL}},N_{{BL}}]&0[N_{{BL}},N_{{BP}}]\\0[N_{{BP}}, N_{{BN}}]&0[N_{{BP}},N_{{BL}}]&E[N_{{BP}},N_{{BP}}]\\\end{bmatrix}}$

Kantaluvun käänteisarvo on tällöin yhtä suuri kuin ${\begin{bmatrix}A^{{-1}}[N_{{BN}},M]&-A^{{-1}}[N_{{BN}},M]A[M,N_{ {BL}}]&0[M,N_{{BP}}]\\0[N_{{BL}},N_{{BN}}]&E[N_{{BL}},N_{{BL}}] &0[N_{{BL}},N_{{BP}}]\\0[N_{{BP}},N_{{BN}}]&0[N_{{BP}},N_{{BL}}] &E[N_{{BP}},N_{{BP}}]\\\end{bmatrix}}$

Kaksoismuuttujat lasketaan kaavalla ${\begin{bmatrix}C[N_{{BN}}]A^{{-1}}[N_{{BN}},M]&C[N_{{BL}}]-C[N_{{BN} }A^{{-1}}[N_{{BN}},M]A[M,N_{{BL}}]&C[N_{{BP}}]\end{bmatrix}}$

Tässä

$C[N_{{BN}}]A^{{-1}}[N_{{BN}},M]$ — potentiaalit (kuten potentiaalien standardimenetelmässä).

$C[N_{{BL}}]-C[N_{{BN}}]A^{{-1}}[N_{{BN}},M]A[M,N_{{BL}}]$ — lisämaksu kuljetuksesta kyllästettyä kaaria pitkin.

Myös kaaren kaistanleveyden rajoittamista voidaan lisätä muuttamalla kuvaajaa hieman [8] .

Kaareen A->B lisätään kaksi kärkeä kustannuksella c ja maksimiläpäisyllä p: C kulutus -p ja D tuotanto p. Huiput yhdistetään kaavion A->C<-D->B mukaan A->B:n sijaan. Kaaren A->C hinta on c, kaarien C<-D ja D->B hinta on nolla. Tällainen kaavio ei salli p:tä suuremman virtauksen kulkea pisteiden A->B välillä.

Algoritmi

Algoritmi on hyvin samanlainen kuin tavallinen potentiaalimenetelmä. Kyllästynyt kaari ei saa täyttää optimaalisuuskriteeriä, muuten virtausta sitä pitkin tulisi vähentää. Loput kaaret tarkistetaan kriteerin suhteen samalla tavalla kuin vakioversiossa. Aivan kuten vakioalgoritmissa, molemmissa tapauksissa tulee ääriviiva, jossa virtausta tulee muuttaa (vähennä valitulle kaarelle, jos kaari poistetaan kyllästetyistä ja kasvaa normaalin kaaren tapauksessa). Kun virtaukset muuttuvat, yksi kaarista voi mennä nollaan (kuten vakioalgoritmissa) tai kaistanleveyden ylärajaan - käännämme sen kyllästyneiksi.

Samoin kuin vakioalgoritmissa, myös potentiaalit lasketaan uudelleen.

Muistiinpanot

↑ Romanovsky, 1977 , s. 109-110.
↑ Romanovsky, 1977 , s. 111.
↑ Romanovsky, 1977 , s. 115.
↑ Romanovsky, 1977 , s. 122.
↑ Romanovsky, 1977 , s. 124.
↑ Itse asiassa nämä ovat samoja lähestymistapoja kuin simplex-menetelmässä, hieman muutetulla terminologialla. Katso Yksipuolista menetelmää käsittelevän artikkelin Tehokkuustekniikat -osio.
↑ Romanovsky, 1977 , s. 137.
↑ Romanovsky, 1977 , s. 139.

Linkit

I.V. Romanovski. Algoritmit äärimmäisten ongelmien ratkaisemiseen. - Moskova: Nauka , 1977.
J. Danzig. Lineaarinen ohjelmointi, sen sovellukset ja yleistykset. Kustantaja " Progress " Moskova 1966
S. Gass. Lineaarinen ohjelmointi (menetelmät ja sovellukset). Käännös englannista: E. G. Golstein ja M. I. Sushkevich, toimittanut D. B. Yudin. M: Valtion fyysisen ja matemaattisen kirjallisuuden kustantaja 1961
A.V. Kuznetsov, N.I. Kholod, L.S. Kostevich. Opas matemaattisen ohjelmoinnin ongelmien ratkaisemiseen. Minsk, "Korkein koulu" 1978
Lungu KN, Lineaarinen ohjelmointi. Ohje ongelmanratkaisuun. — M.: Fizmatlit, 2005. — 128 s. — ISBN 5-9221-0631-7 .
http://www.ami.nstu.ru/~headrd/seminar/publik_html/MO_conspect.pdf Lemeshko B.Yu., Optimointimenetelmät: Luentomuistiinpanot / B.Yu. Lemeshko. - Novosibirsk: NSTU:n kustantaja, 2009
Panyukov A.V., Telegin V.A., STREAM-ALGORITMIJEN OHJELMISTON TOTEUTUSTEKNIIKKA
https://web.archive.org/web/20130618194857/http://www.iasa.org.ua/lections/
KULJETUSTEHTÄVÄ KUSTANNUS- JA AIKAKRITEERIIN, SELITYS kurssiprojektiin tieteenalalla Päätösteoria, Irkutsk 2009.

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