Enkel metode

Ikke at forveksle med den "simplekse metode" - en metode til at optimere en vilkårlig funktion. Se Nelder-Mead metode

Simplexmetoden er en algoritme til at løse et optimeringsproblem ved lineær programmering ved at optælle hjørnerne af et konveks polyeder i et flerdimensionalt rum.

Essensen af metoden: konstruktionen af grundlæggende løsninger, hvorpå den lineære funktionelle monotont falder, indtil situationen, hvor de nødvendige betingelser for lokal optimalitet er opfyldt.

I arbejdet med L. V. Kantorovich "Matematiske metoder til organisering og planlægning af produktion" (1939) blev principperne for en ny gren af matematikken, som senere blev kendt som lineær programmering, først fremsat. [en]

Historisk set blev det generelle problem med lineær programmering først stillet i 1947 af George Bernard Dantzig , Marshall Wood og deres samarbejdspartnere i US Air Force Department. På det tidspunkt undersøgte denne gruppe muligheden for at bruge matematiske og relaterede metoder til militære og planlægningsmæssige problemer. Senere blev en forskningsgruppe kaldet Project SCOOP organiseret i luftvåbnet for at udvikle disse ideer. Den første vellykkede løsning af et lineært programmeringsproblem på en SEAC-computer blev udført i januar 1952 [2] .

Beskrivelse

Problemet med lineær programmering er, at det er nødvendigt at maksimere eller minimere nogle lineære funktioner på et multidimensionelt rum under givne lineære begrænsninger.

Bemærk, at hver af de lineære uligheder på variabler afgrænser et halvt rum i det tilsvarende lineære rum. Som et resultat begrænser alle uligheder nogle konvekse polyeder (muligvis uendelig), også kaldet et polyederkompleks . Ligningen W ( x ) = c , hvor W ( x ) er en maksimeret (eller minimeret) lineær funktional, genererer et hyperplan L(c) . Afhængighed af c genererer en familie af parallelle hyperplaner. Så får det ekstreme problem følgende formulering: det er nødvendigt at finde det største c , således at hyperplanet L(c) skærer polyederen i det mindste i ét punkt. Bemærk, at skæringspunktet mellem et optimalt hyperplan og et polyeder vil indeholde mindst ét toppunkt, og der vil være mere end ét, hvis skæringspunktet indeholder en kant eller en k -dimensionel flade. Derfor kan det maksimale af det funktionelle søges ved polyederens toppunkter. Princippet for simpleksmetoden er, at der vælges et af polyederens toppunkter, hvorefter bevægelsen langs dens kanter fra toppunkt til toppunkt begynder i retning af at øge værdien af det funktionelle. Når overgangen langs kanten fra det aktuelle toppunkt til et andet toppunkt med en højere værdi af det funktionelle er umuligt, vurderes det, at den optimale værdi af c er fundet.

Beregningssekvensen ved simpleksmetoden kan opdeles i to hovedfaser :

at finde det indledende toppunkt for sættet af mulige løsninger,
sekventiel overgang fra et toppunkt til et andet, hvilket fører til optimering af værdien af den objektive funktion.

I nogle tilfælde er den oprindelige løsning desuden indlysende, eller dens definition kræver ikke komplekse beregninger, for eksempel når alle begrænsninger er repræsenteret af uligheder på formen "mindre end eller lig med" (så er nulvektoren absolut en mulig løsning , selvom det højst sandsynligt er langt fra det mest optimale). I sådanne problemer kan den første fase af simplex-metoden helt udelades. Simplexmetoden er henholdsvis opdelt i enkeltfaset og tofaset .

Algoritmen for simplex-metoden

Styrket problemformulering

Overvej følgende lineære programmeringsproblem :

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

Lad os nu stille dette problem i en tilsvarende forbedret form. Det er nødvendigt at maksimere Z , hvor:

{\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

Her er x variable fra den oprindelige lineære funktional, x s er nye variable, der supplerer de gamle på en sådan måde, at uligheden bliver til lighed, c er koefficienterne for den oprindelige lineære funktional, Z er den variabel, der skal maksimeres. Halvrummene og ved skæringspunktet danner et polyeder, der repræsenterer sættet af mulige løsninger. Forskellen mellem antallet af variable og ligninger giver os antallet af frihedsgrader. Kort sagt, hvis vi betragter toppunktet af et polyeder, så er dette antallet af kanter, som vi kan fortsætte med at bevæge os langs. Så kan vi tildele en værdi på 0 til dette antal variable og kalde dem "ikke-grundlæggende" . I dette tilfælde vil de resterende variable blive beregnet entydigt og vil blive kaldt "basic" . Det samme sæt af disse variable kaldes basis . Det resulterende punkt vil være toppunktet i skæringspunktet mellem hyperplanerne svarende til de ikke-grundlæggende variable. For at finde den såkaldte. den indledende tilladelige løsning (den toppunkt, hvorfra vi vil begynde at bevæge os), vil vi tildele værdien 0 til alle indledende variabler x , og vi vil betragte dem som ikke-grundlæggende, og alle nye vil blive betragtet som grundlæggende. I dette tilfælde beregnes den oprindelige tilladte løsning entydigt: . $x\geqslant 0$ $x_{s}\geqslant 0$ ${\mathbf {x}}_{{si}}={\mathbf {b}}_{i}$

Algoritme

Nu præsenterer vi trinene i algoritmen. På hvert trin vil vi ændre sæt af basis- og ikke-grundlæggende vektorer (bevæge sig langs kanterne), og matricen vil se sådan ud:

{\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}},

hvor er koefficienterne for vektoren svarende til grundvariablene (variabler svarer til 0), er kolonnerne svarende til grundvariablerne. Matrixen dannet af de resterende kolonner er angivet med . Hvorfor matricen vil have denne form, vil blive forklaret i beskrivelsen af algoritmens trin. $c_{B}$ $c$ $x_{s}$ $B$ $[{\mathbf {A}}{\mathbf {E}}]$ $D$

Første skridt .

Vi vælger den oprindelige gyldige værdi, som angivet ovenfor. Ved det første trin , identitetsmatrixen, da de grundlæggende variabler er . er en nulvektor af samme årsager. $B$ $x_{s}$ $c_{B}$

Andet trin

Lad os vise, at i udtrykket kun ikke-grundlæggende variable har en koefficient, der ikke er nul. Bemærk, at fra udtrykket er de grundlæggende variabler entydigt udtrykt i form af ikke-grundlæggende, da antallet af grundvariable er lig med antallet af ligninger. Lad være grundlæggende og være ikke-grundlæggende variable ved en given iteration. Ligningen kan omskrives som . Lad os gange det med til venstre: . Vi har således udtrykt grundvariablene i form af ikke-basisvariable, og i udtrykket svarende til venstre side af ligheden har alle grundvariable enhedskoefficienter. Derfor, hvis vi tilføjer lighed til lighed , så vil alle grundvariable i den resulterende lighed have en nulkoefficient - alle grundvariable på formen x vil blive reduceret, og grundvariable på formen x s vil ikke indgå i udtrykket . $(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}$

Lad os vælge en kant, som vi vil bevæge os langs. Da vi ønsker at maksimere Z , er det nødvendigt at vælge en variabel, der vil mindske udtrykket mest

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

For at gøre dette vælger vi en variabel, der har den største negative koefficient i modul [3] . Hvis der ikke er sådanne variabler, det vil sige, at alle koefficienterne for dette udtryk er ikke-negative, så er vi kommet til det ønskede toppunkt og fundet den optimale løsning. Ellers vil vi begynde at øge denne ikke-grundlæggende variabel, det vil sige bevæge os langs kanten, der svarer til den. Lad os kalde denne variabel input .

Tredje trin

Nu skal vi forstå, hvilken grundvariabel der først vil gå til nul, når inputvariablen øges. For at gøre dette er det nok at overveje systemet:

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

For faste værdier af ikke-basisvariable er systemet entydigt løseligt med hensyn til basisvariablerne, så vi kan bestemme, hvilken af basisvariablerne, der vil være den første til at nå nul, når inputtet stiger. Lad os kalde denne variabel output . Det vil betyde, at vi har ramt et nyt højdepunkt. Lad os nu bytte de indgående og udgående variable - den indgående vil "indtræde" i basisvariablen, og den udgående variabel vil "forlade" de ikke-grundlæggende. Nu omskriver vi matricen B og vektoren c B i overensstemmelse med de nye sæt af grundlæggende og ikke-grundlæggende variable, hvorefter vi vender tilbage til andet trin. x''

Da antallet af hjørner er begrænset, vil algoritmen en dag slutte. Det fundne toppunkt vil være den optimale løsning.

Tofaset simpleksmetode

Årsager til at bruge

Hvis i tilstanden af et lineært programmeringsproblem ikke alle begrænsninger er repræsenteret af uligheder af typen "≤", så vil nulvektoren ikke altid være en gyldig løsning. Hver iteration af simplex-metoden er dog en overgang fra et toppunkt til et andet, og hvis intet toppunkt er kendt, kan algoritmen slet ikke startes.

Processen med at finde det indledende toppunkt er ikke meget forskellig fra den enfasede simpleksmetode, men det kan ende med at blive sværere end yderligere optimering.

Begrænsningsændringer

Alle opgavebegrænsninger ændres i henhold til følgende regler:

restriktioner af typen "≤" oversættes til ligheder ved at skabe en ekstra variabel med koefficienten "+1". Denne modifikation udføres også i den enkeltfasede simplex-metode, yderligere variabler bruges yderligere som det indledende grundlag.
begrænsninger af typen "≥" suppleres af én variabel med koefficienten " -1 ". Da en sådan variabel ikke kan bruges i det oprindelige grundlag på grund af en negativ koefficient, er det nødvendigt at oprette en ekstra hjælpevariabel . Hjælpevariabler oprettes altid med en faktor på "+1".
restriktioner af typen "=" er suppleret med en hjælpevariabel.

I overensstemmelse hermed vil der blive oprettet en række yderligere og hjælpevariable. I den indledende basis vælges yderligere variable med en koefficient på "+1" og alle hjælpevariabler. Forsigtig: den løsning, som dette grundlag svarer til, er ikke tilladt.

Forskelle mellem yderligere og hjælpevariable

På trods af, at både ekstra- og hjælpevariabler er skabt kunstigt og bruges til at skabe det indledende grundlag, er deres værdier i løsningen meget forskellige:

yderligere variabler rapporterer, hvor "underudnyttet" deres tilsvarende begrænsning er. Værdien af den ekstra variabel, lig med nul, svarer til ligheden mellem værdierne af højre og venstre del af begrænsningen.
hjælpevariable fortæller, hvor langt den givne betingelse er fra acceptabel (i forhold til en bestemt begrænsning). Hvis værdien af hjælpevariablen er større end nul, så opfylder denne løsning ikke en vis begrænsning og er derfor ikke gyldig.

Det vil sige, at en ikke-nul værdi af den ekstra variabel kan (men bør ikke) signalere, at løsningen ikke er optimal . En værdi, der ikke er nul, af hjælpevariablen indikerer, at løsningen er ugyldig .

Beslutningsfaser

Efter at betingelsen er blevet ændret, oprettes en hjælpeobjektivfunktion . Hvis hjælpevariablene blev betegnet som , , så definerer vi hjælpefunktionen som $y_{i}$ ${\displaystyle i\in \left\{1,\dots ,k\right\))$

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

Derefter udføres den almindelige simplex-metode med hensyn til hjælpeobjektivfunktionen. Da alle hjælpevariable øger værdien af , vil de under algoritmen blive udledt en efter en fra basis, og efter hver overgang vil den nye løsning være tættere på sættet af mulige løsninger. $z'$

Når den optimale værdi af hjælpeobjektivet er fundet, kan der opstå to situationer:

den optimale værdi er større end nul. Det betyder, at mindst én af hjælpevariablene forblev i grundlaget. I dette tilfælde kan vi konkludere, at der ikke er nogen gennemførlige løsninger på dette lineære programmeringsproblem. $z'$
den optimale værdi er nul. Det betyder, at alle hjælpevariable er taget ud af grundlaget, og den nuværende løsning er gyldig. $z'$

I det andet tilfælde har vi et acceptabelt grundlag, eller med andre ord en indledende acceptabel løsning. Det er muligt at udføre yderligere optimering under hensyntagen til den oprindelige objektivfunktion, uden at være opmærksom på hjælpevariabler. Dette er anden fase af løsningen.

Ændret simpleksmetode

I den modificerede metode, matrixen

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

ikke genberegnet, kun matrixen gemmes og genberegnes . Resten af algoritmen ligner den, der er beskrevet ovenfor. $B^{{-1}}$

1. Beregn dobbelte variable $d=c_{B}^{T}B^{{-1}}$

2. Kontrol af optimaliteten. er konverteret til . $c_{B}^{T}B^{{-1}}Ac^{T}$ $d^{T}Ac^{T}$

Kontrollen består i at beregne for alle kolonner . En kolonne med en værdi < 0 kan indtastes i grundlaget. $d^{T}A_{n}-c_{n}$ $n\i N$

Vælg ofte minimumsværdien, men for dette skal du iterere over alle kolonnerne.

Vælg oftere en værdi mindre end en given værdi $-\varepsilon$

Hvis en sådan kolonne ikke findes, tages den maksimale fundne absolutte værdi som den fundne, og den tilsvarende kolonne indtastes i grundlaget. $\varepsilon$ $A_{J}$

3. Definition af output.

Lad være den input kolonne, der svarer til variablen Grundplanen er løsningen af systemet Forøg . $A_{J}$ $x_{J}$ $A_{B}p=b$ $A_{B}p+\vartheta A_{J}=b$

Multiplicer til venstre med , dvs. $B^{{-1}}$ $B^{{-1}}A_{B}p+\vartheta B^{{-1}}A_{J}=B^{{-1}}b$

Her er den grundlæggende plan, er udvidelsen af input kolonnen med hensyn til grundlaget. $B^{{-1}}b$ $q=B^{{-1}}A_{J}$

Find den maksimale værdi , som alle værdier er ikke-negative for. Hvis der kan tages vilkårligt store, er løsningen ubegrænset. Ellers vil et af elementerne gå til nul. Vi udleder den tilsvarende kolonne fra grundlaget. $\vartheta$ $\vartheta$

4. Genberegning af reference (grund)planen.

Vi beregner en ny referenceplan ved hjælp af den allerede givne formel med den fundne værdi . $x=p+\vartheta B^{{-1}}A_{J}$ $\vartheta$

5. Vi genberegner det omvendte til grundtallet . $B^{{-1}}$

Lad være outputkolonnen. $B^{{-1}}A_{F}$

Matrix B kan repræsenteres som $[B_{G}A_{F}]$

hvor er basismatrixen uden outputkolonnen. $B_{G}$

Efter ændring af kolonnen vil basismatrixen se ud $[B_{G}A_{J}]$

Vi skal finde sådan en matrix $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}}$

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

Kommentar.

Matrix-genberegning akkumulerer afrundingsfejl. For at undgå store fejl genberegnes matrixen fuldstændig fra tid til anden. Denne proces kaldes "gentagelse". $B^{{-1}}$

En multiplikativ version af simplex-metoden

I den multiplikative version er matrixen ikke gemt, kun faktorer gemt $B^{{-1}}$ ${\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix))$

Når du løser økonomiske problemer, er begrænsningsmatricen ofte sparsom , i hvilket tilfælde den multiplikative mulighed får yderligere fordele - du kan gemme multiplikatorer i en komprimeret form (gem ikke nuller).

Andre varianter af simplex-metoden

LU-dekomponeringen af matrixen kan bruges til at undgå akkumulering af afrundingsfejl .

Med det overvældende antal restriktioner af typen "ulighed" kan metoden med variabel basis bruges . [fire]

Metoden er baseret på, at basismatricen kan repræsenteres som

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

Dens omvendte har formen

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

Med relativt små matrixstørrelser kan resten af matrixen muligvis ikke opbevares. $A_{B}^{{-1}}$

Denne tilgang kan løse problemer med titusindvis af millioner af strenge af begrænsninger (f.eks. fra spilteori).

Dual simplex-metoden

For at implementere den dobbelte metode er det nødvendigt at gå fra problemet til minimum til problemet til maksimum (eller omvendt) ved at transponere matrixen af koefficienter. Når du flytter fra opgaven til minimum, vil den objektive funktion have formen:

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

under restriktioner

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

Dualitetssætningen . Hvis den ene af et par af dobbelte problemer har en optimal plan, så har den anden en løsning, og ekstremværdierne af de lineære funktioner af disse problemer er ens.

Hvis den lineære funktion af et af problemerne ikke er begrænset, så har den anden ingen løsning.

Beregningseffektivitet

Simplex-metoden er overraskende effektiv i praksis, men i 1972 gav Klee og Minty [5] et eksempel, hvor simpleks-metoden itererede over alle hjørnerne af simpleksen og viste metodens eksponentielle konvergens i værste fald. Siden er der for hver variant af metoden fundet et eksempel, hvor metoden opførte sig usædvanligt dårligt.

Observationer og analyser af metodens effektivitet i praktiske anvendelser førte til udviklingen af andre måder at måle effektiviteten på.

Simplexmetoden har en gennemsnitlig polynomisk konvergens med et bredt udvalg af fordeling af værdier i tilfældige matricer. [6] [7]

Beregningseffektivitet estimeres normalt ved hjælp af to parametre:

antallet af iterationer, der kræves for at opnå en løsning;
maskintidsomkostninger.

Som et resultat af numeriske eksperimenter blev følgende resultater opnået.

Antallet af iterationer i løsning af lineære programmeringsproblemer i standardformen med begrænsninger og variable er mellem og . Gennemsnitligt antal iterationer . Den øvre grænse for antallet af iterationer er . $m$ $n$ $m$ $3m$ $2m$ $2m+n$
Den nødvendige maskintid er proportional med . $m^{3}$

Antallet af restriktioner påvirker beregningseffektiviteten mere end antallet af variable, derfor bør man, når man formulerer lineære programmeringsproblemer, stræbe efter at reducere antallet af restriktioner, selv om man øger antallet af variable.

Metoder til forbedring af effektiviteten

En af de mest tidskrævende procedurer i simplex-metoden er søgningen efter en kolonne, der er indført i grundlaget. For bedre konvergens ser det ud til, at du skal vælge en variabel med den bedste residual, men dette kræver en fuld scanning, det vil sige, at du skal gange en kolonne med dobbelte variable (nogle gange kaldet skyggepriser) med alle søjler i matrixen [8] . Denne tilgang fungerer godt til små problemer, der løses manuelt. Ydermere kan streng overholdelse af reglen for valg af den maksimale rest i modul vise sig at være suboptimal med hensyn til det samlede antal iterationer, der kræves for at opnå et ekstremum. Den maksimale forstærkning ved én iteration kan føre til et langsomt fald i værdien af den objektive funktion ved efterfølgende trin og derfor bremse processen med at løse problemet [9] .

Med store begrænsningsmatricer begynder proceduren for at søge efter en inputvariabel at tage meget tid, og man forsøger ofte at undgå at se på alle matrixens kolonner, hvortil følgende metoder kan bruges:

Barriere . Så snart uoverensstemmelsen i variablen er tilstrækkeligt forskellig fra nul (overstiger en vis værdi kaldet barrieren), introduceres variablen i grundlaget. Hvis alle residualerne viste sig at være mindre end barrieren, vælges variablen med den mindste residual som input, mens selve barrieren reduceres efter en eller anden regel (f.eks. halvdelen af den mindste residual). Barrieren bruges ofte med følgende teknik. En lignende tilgang er beskrevet i Murtaughs bog, se afsnit 3.6.2. Delvis evaluering af bogen [10] . Cykelvisning . Søgningen efter en inputvariabel starter fra positionen efter den variabel, der blev introduceret ved den forrige iteration. Gruppeudvælgelse (I Murtaughs bog kaldes denne teknik for multipel evaluering . Se afsnit 3.6.3. Multipel evaluering [11] .) Når man søger på en inputvariabel, vælges ikke én variabel, men flere kandidater. Ved de næste iterationer udføres visning kun blandt de udvalgte kandidater, mens kandidaten kan slettes fra listen. Formål med vægte . Variabler tildeles vægte. Se afsnit 3.6.4 DEVEX- scoringsmetode af Murtafa [12] . Søg efter den stejleste ribbe af Goldfarb og Reed. Se afsnit 3.6.5 Stejleste kantestimationsmetode i Murtaughs bog [13] .

Andre tricks er også mulige, såsom Zadeh-reglen .

Noter

↑ Kantorovich L. V. Matematiske metoder til at organisere produktionsplanlægning // Udgave af Leningrad State University. - Leningrad, 1939.
↑ S. Gass. Lineær programmering (metoder og applikationer). - Moskva: State Publishing House of Physical and Mathematical Literature, 1961. - (Ingeniørens fysiske og matematiske bibliotek).
↑ Denne anbefaling findes ofte i lærebøger, men er ikke altid korrekt. Se #Metoder til at forbedre effektiviteten
↑ V.I. Muravyov. Sekventiel forbedringsmetode med variabel størrelse basis for lineære programmeringsproblemer. — Samling "Forskning af operationer og metoder til statistisk modellering". - Leningrad: Leningrad State University, 1972.
↑ Klee, Victor; Minty, George J. Hvor god er simplex-algoritmen? // Inequalities III (Proceedings of the Third Symposium on Inequalities afholdt ved University of California, Los Angeles, Californien, 1.-9. september 1969, dedikeret til Theodore S. Motzkins minde) (engelsk) / Shisha, Oved . - New York-London: Academic Press , 1972. - S. 159-175.
↑ Alexander Schrijver, teori om lineær og heltalsprogrammering . John Wiley & sønner, 1998, ISBN 0-471-98232-6 (matematisk)
↑ Simplexalgoritmen tager i gennemsnit D trin for en terning. Borgwardt, Karl-Heinz. Simplexmetoden: En probabilistisk analyse . - Berlin: Springer-Verlag , 1987. - Vol. 1. - P.xii+268. - (Algorithms and Combinatorics (Studie- og forskningstekster)). - ISBN 3-540-17096-0 .
↑ Anbefalingen om at vælge den maksimale modulo-værdi af residualen kan ofte findes i beskrivelserne af simpleksmetoden, for eksempel i artiklerne Algoritme for simpleksmetoden Arkiveret 17. marts 2018 på Wayback Machine og SIMPLEX LINEAR PROGRAMMERINGSMETODE Arkiveret 17. marts 2018 på Wayback Machine
↑ Shamray, 2009 , s. 44.
↑ Murtaf, 1984 .
↑ Murtaf, 1984 , s. 61.
↑ Murtaf, 1984 , s. 62.
↑ Murtaf, 1984 , s. 63.

Litteratur

Hemdy A. Taha. Kapitel 3. Den simple metode // Introduktion til operationsforskning = Operationsforskning: En introduktion. - 7. udg. - M . : "Williams" , 2007. - S. 95-141. — ISBN 0-13-032374-8 .
Akulich I.L. Kapitel 1. Problemer med lineær programmering // Matematisk programmering i eksempler og opgaver. - M . : Højere skole , 1986. - 319 s. — ISBN 5-06-002663-9 .
Thomas H. Kormen et al. Kapitel 29 Lineær programmering // Algoritmer: Konstruktion og analyse = INTRODUKTION TIL ALGORITHMER. - 2. udg. - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
V. N. Shevchenko, N. Yu. Zolotykh. Lineær og heltals lineær programmering . - Nizhny Novgorod: Forlaget for Nizhny Novgorod State University. N.I. Lobachevsky, 2004. - S. 63 -66 (afsnit 2.8. Bemærkninger om kompleksiteten i at løse LLP). — ISBN 5-85746-761-6 .
Shamray Natalya Borisovna. Praktisk lineær programmering for økonomer . - Vladivostok: Publishing House of the Far Eastern University, 2009. - S. 44. - ISBN 978-5-7444-2215-8 . Arkiveret 17. marts 2018 på Wayback Machine
Murtaf B. Moderne lineær programmering. - Moskva: Mir, 1984.

Links

En kort beskrivelse af simplex-metoden på hjemmesiden for Institut for Fjernundervisning INTUIT
Enkel online simpleksløser med grafisk display

Ordbøger og encyklopædier	Britannica (online)
I bibliografiske kataloger	GND : 4181488-5 J9U : 987007546249105171 LCCN : sh85122745

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering