Linjär programmering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 5 maj 2022; kontroller kräver 5 redigeringar .

Linjär programmering är en matematisk disciplin som ägnas åt teori och metoder för att lösa extrema problem på uppsättningar av dimensionellt vektorrum definierat av system av linjära ekvationer och ojämlikheter. $n$

Linjär programmering (LP) är ett specialfall av konvex programmering , som i sin tur är ett specialfall av matematisk programmering . Samtidigt är det grunden för flera metoder för att lösa heltals- och icke-linjära programmeringsproblem . En generalisering av linjär programmering är fraktionerad linjär programmering .

Många egenskaper hos linjära programmeringsproblem kan också tolkas som egenskaper hos polyedrar och kan således formuleras och bevisas geometriskt.

Historik

Matematiska studier av enskilda ekonomiska problem, matematisk formalisering av numeriskt material genomfördes redan på 1800-talet . I den matematiska analysen av den utökade produktionsprocessen användes algebraiska relationer, deras analys utfördes med hjälp av differentialkalkyl . Detta gjorde det möjligt att få en allmän uppfattning om problemet.

Ekonomins utveckling krävde kvantitativa indikatorer och på 1920 - talet skapades en intersektoriell balans ( IOB ). Det var han som fungerade som en drivkraft för att skapa och studera matematiska modeller. Utvecklingen av MOB 1924-1925 i Sovjetunionen påverkade ekonomen och statistikern Vasilij Vasilievich Leontievs arbete . Han utvecklade en intersektoriell modell för produktion och distribution av produkter.

1938 började Leonid Vitalievich Kantorovich , under vetenskapligt samråd, studera den rent praktiska uppgiften att utarbeta den bästa planen för lastning av skalmaskiner (plywood trust). Denna uppgift lämpade sig inte för konventionella metoder. Det blev tydligt att uppgiften inte var slumpmässig. [ett]

1939 publicerade Leonid Kantorovich verket "Mathematical Methods of Organization and Planning of Production", där han formulerade en ny klass av extrema problem med restriktioner och utvecklade en effektiv metod för att lösa dem, och därmed lade grunden för linjär programmering.

Studiet av sådana problem ledde till skapandet av en ny vetenskaplig disciplin av linjär programmering och öppnade ett nytt steg i utvecklingen av ekonomiska och matematiska metoder.

1949 utvecklade den amerikanske matematikern George Bernard Dantzig en effektiv metod för att lösa linjära programmeringsproblem (LPP) - simplexmetoden . [ett]

Termen "programmering" måste förstås i betydelsen "planering" (en av översättningarna av engelsk programmering ). Det föreslogs i mitten av 1940-talet av George Danzig, en av grundarna av linjär programmering, innan datorer användes för att lösa linjära optimeringsproblem .

Den inre punktmetoden nämndes första gången av I. I. Dikin 1967 . [2] . Dessa studier fortsatte, inklusive av inhemska forskare. På 1970-talet lyckades V. G. Zhadan erhålla huvudresultaten och utveckla ett allmänt tillvägagångssätt för konstruktionen av inre punktmetoder för att lösa problem med linjär och olinjär programmering, baserad på transformation av utrymmen; föreslå barriärprojektiva och barriär-newtonska numeriska metoder.

Uppgifter

Det allmänna (standard) problemet med linjär programmering är problemet med att hitta minimum av en linjär objektiv funktion (linjär form) av formen [3] :

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

Ett problem där begränsningar i form av ojämlikheter uppstår kallas ett grundläggande linjärt programmeringsproblem (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)

Problemet med linjär programmering kommer att ha en kanonisk form om det i huvudproblemet istället för det första systemet av ojämlikheter finns ett ekvationssystem med begränsningar i form av likhet [4] :

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

Huvudproblemet kan reduceras till ett kanoniskt genom att införa ytterligare variabler.

Linjära programmeringsproblem av den mest allmänna formen (problem med blandade begränsningar: likheter och ojämlikheter, närvaron av variabler fria från begränsningar) kan reduceras till ekvivalenta (med samma uppsättning lösningar) förändringar av variabler och ersättning av likheter med ett par ojämlikheter [5] .

Det är lätt att se att problemet med att hitta maximum kan ersättas med problemet att hitta minimum genom att ta koefficienterna med motsatt tecken. $c$

Problemexempel

Maximal matchning

Tänk på det maximala matchningsproblemet i en tvådelad graf : det finns flera pojkar och flickor, och för varje pojke och flicka är det känt om de gillar varandra. Det är nödvändigt att gifta det maximala antalet par med ömsesidig sympati.

Låt oss introducera variabler som motsvarar paret från den -e pojken och den -e flickan och uppfyller begränsningarna: $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,

med en objektiv funktion , där är lika med 1 eller 0 beroende på om den -e pojken och -e tjejen är trevliga mot varandra. Det kan visas att bland de optimala lösningarna på detta problem finns en heltalslösning. Variabler lika med 1 kommer att motsvara par som ska vara gifta. ${\displaystyle f=c_{11}x_{11}+c_{12}x_{12}+\ldots +c_{nm}x_{nm))$ ${\displaystyle c_{ij))$ $i$ $j$

Maximalt flöde

Låt det finnas en graf (med riktade kanter) där för varje kant dess kapacitet anges. Och två hörn ges: ett handfat och en källa. Det är nödvändigt att specificera för varje kant hur mycket vätska som kommer att flöda genom den (inte mer än dess kapacitet) för att maximera det totala flödet från källa till sjunka (vätska kan inte uppträda eller försvinna vid alla hörn utom källan respektive sjunka).

Låt oss ta som variabler mängden vätska som strömmar genom den e kanten. Sedan $x_{i}$ $i$

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

var är kapaciteten för den th kanten. Dessa ojämlikheter måste kompletteras med jämlikheten mellan mängden inkommande och utgående vätska för varje vertex, med undantag för sänkan och källan. Som en funktion är det naturligt att ta skillnaden mellan mängden utströmmande och inströmmande vätska vid källan. $c_{i}$ $i$ $f$

En generalisering av det tidigare problemet är det maximala flödet av minimikostnad. I detta problem anges kostnaderna för varje kant och det är nödvändigt att välja bland de maximala flödena flödet med lägsta kostnad. Den här uppgiften reduceras till två linjära programmeringsproblem: först måste du lösa problemet med det maximala flödet, och sedan lägga till det här problemet begränsningen , där är värdet på det maximala flödet, och lösa problemet med en ny funktion - kostnaden för flödet. $f(x)\geqslant m$ $m$ $f(x)$

Dessa problem kan lösas snabbare än med allmänna algoritmer för att lösa linjära programmeringsproblem på grund av den speciella strukturen hos ekvationer och ojämlikheter.

Transportproblem

Det är en viss homogen last som måste transporteras från lager till fabriker. För varje lager är det känt hur mycket last som finns i det , och för varje anläggning är dess behov av last känt. Kostnaden för transport är proportionell mot avståndet från lagret till anläggningen (alla avstånd från -: e lagret till -: e anläggningen är kända). Det krävs att man upprättar den billigaste transportplanen. $n$ $m$ $i$ $a_{i}$ $b_{j}$ $c_{ij}$ $i$ $j$

De avgörande variablerna i detta fall är - mängden gods som transporteras från -: e lagret till -: e anläggningen. De uppfyller begränsningarna: $x_{ij}$ $i$ $j$

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

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

Objektivfunktionen har formen: , som måste minimeras. $f(x)=x_{{11}}c_{{11}}+x_{{12}}c_{{12}}+\ldots +x_{{nm}}c_{{nm}}$

Nollsummespel

Det finns en storleksmatris . Den första spelaren väljer ett nummer från 1 till , den andra - från 1 till . Sedan kontrollerar de siffrorna och den första spelaren får poäng, och den andra får poäng ( - numret som valts av den första spelaren - den andra). Vi måste hitta den optimala strategin för den första spelaren. $A$ $n\ gånger m$ $n$ $m$ $a_{{ij}}$ $(-a_{{ij}})$ $i$ $j$

Sätt in den optimala strategin, till exempel den första spelaren, numret måste väljas med sannolikhet . Då är den optimala strategin en lösning på följande linjära programmeringsproblem: $i$ $pi}$

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 ),

där funktionen ska maximeras . Värdet i den optimala lösningen kommer att vara den värsta förväntan på den första spelarens utdelning. $f(p_{1},\;\ldots ,\;p_{n},\;c)=c$ $c$

Lösningsalgoritmer

Den mest kända och mest använda i praktiken för att lösa det allmänna problemet med linjär programmering (LP) är simplexmetoden . Trots att simplexmetoden är en ganska effektiv algoritm som visat goda resultat för att lösa tillämpade LP-problem är det en algoritm med exponentiell komplexitet . Anledningen till detta är den kombinatoriska karaktären hos simplexmetoden, som successivt räknar upp polyederns hörn av tillåtna lösningar samtidigt som man söker efter den optimala lösningen.

Den första polynomalgoritmen , ellipsoidmetoden , föreslogs 1979 av den sovjetiske matematikern L. Khachiyan , och löste därmed ett problem som hade förblivit olöst under lång tid. Ellipsoidmetoden har en helt annan icke-kombinatorisk karaktär än simplexmetoden. Men i beräkningsmässiga termer visade sig denna metod vara föga lovande. Ändå ledde själva faktumet av problemens polynomiska komplexitet till skapandet av en hel klass av effektiva LP-algoritmer - inre punktmetoder , varav den första var N. Karmarkars algoritm som föreslogs 1984 . Algoritmer av denna typ använder en kontinuerlig tolkning av LP-problemet, när istället för att räkna upp hörn av polytopen av lösningar på LP-problemet, görs en sökning längs banor i utrymmet för variabler av problemet som inte passerar genom hörnen av polytopen. Den inre punktmetoden, som, till skillnad från simplexmetoden, kringgår punkter från det inre av toleransområdet, använder icke-linjära logaritmiska barriärfunktionsmetoder som utvecklades på 1960-talet av Fiacco och McCormick.

En annan metod för att lösa LP är att använda Seidel-algoritmen:

LP:n ges i kanonisk form med variabler och begränsningar som utgör uppsättningen . $d$ $m$ $H$
Om eller , härled den optimala grundlösningen . $d=1$ $m=0$ $H$
Välj annars en slumpmässig begränsning och beräkna rekursivt den optimala grundlösningen för . $h\in H$ ${\displaystyle H\setminus \{h\))$
Om den optimala grundlösningen för inte bryter mot begränsningen , returnera den. ${\displaystyle H\setminus \{h\))$ $h$
Beräkna annars skärningspunkten mellan LP-polyedern och hyperplanet och lös den resulterande LP rekursivt med en variabel. $h$ $d-1$

Denna metod har asymptotisk komplexitet . $O(m\cdot d!)$

Dubbla linjära programmeringsproblem

Varje linjär programmeringsproblem [6] i formuläret

\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

det är möjligt på ett visst sätt att jämföra något annat linjärt programmeringsproblem, kallat dubbelt eller konjugat, med det ursprungliga eller direkta. Sambandet mellan de ursprungliga och dubbla problemen ligger främst i det faktum att lösningen av det ena av dem kan erhållas direkt från lösningen av det andra. Låt oss definiera det dubbla problemet med avseende på det ursprungliga linjära programmeringsproblemet

Inledande uppgift	Dubbla problem
$\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$

Om vektorerna och är tillåtliga lösningar på de primära och dubbla problemen, då , och jämlikhet uppnås om och bara om och är optimala lösningar. Om den objektiva funktionen för ett av paret av dubbla problem inte är begränsad (uppifrån för det ursprungliga, underifrån för det dubbla), är området för genomförbara lösningar för det andra problemet tomt. $x$ $y$ $F(x)\leqslant T(y)$ $x$ $y$

Om vektorerna och är de optimala lösningarna för de direkta respektive dubbla problemen, så är följande likheter sanna $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}}.

Det vill säga, för optimala lösningar på de primära och dubbla problemen, motsvarar icke-spända (strikt ojämlikhet uppfylls) begränsningar nollvariabler, och icke-nollvariabler (inkluderade i stödplanen) motsvarar snäva (icke strikt ojämlikhet är implementerad som jämlikhet) begränsningar. Men det kan finnas noll variabler som motsvarar snäva begränsningar.

Dessa egenskaper hos dubbla lösningar kan avsevärt minska lösningstiden om du måste lösa ett problem med ett antal begränsningar som är mycket större än antalet variabler. Sedan är det möjligt, efter att ha löst det dubbla problemet, att hitta dess stödplan, varefter, efter att ha valt i det direkta problemet endast de begränsningar som motsvarar stödplanen (alla dessa begränsningar måste ansträngas), lösa det vanliga systemet med linjära ekvationer för dem.

Sats. Det dubbla av det dubbla LP-problemet är det primära LP-problemet.

Bevis: Överväg en direkt LP av formen under villkoret . Låt oss associera den dubbla LP-skivan med den och skaffa den under villkoret . Låt oss föra det till en annan form, motsvarande betydelse: under villkoret . Låt oss återigen jämföra den dubbla LP-skivan med den och skaffa den under villkoret . Vi tar den till en likvärdig form och skaffar en LP som är identisk med originalet: under villkoret . ${\displaystyle \max c^{T))$ $Ax\leqslant b,x\geqslant 0$ $\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$ ${\displaystyle \max c^{T))$ $Ax\leqslant b,x\geqslant 0$

Programvara

lp_solve är programvara med öppen källkod (LGPL GNU GNU General Public License for Libraries ) för att lösa linjära ekvationer. LpSolve har en IDE , inbyggt C API och många andra API:er för Java, AMPL, MATLAB, Wolfram Mathematica, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R och Microsoft Solver Foundation .

Se även

Anteckningar

↑ 1 2 Källa: Altai Regional Universal Scientific Library. V. Ya. Shishkova (AKUNB) Arkiverad 5 mars 2022 på Wayback Machine . Optimeringsmetoder: Proc. ersättning. Brazovskaya N.V.; Altai State Technical University I. I. Polzunova, [Center of Distance. inlärning]. - Barnaul: AltGTU Publishing House, 2000. - 120 sid. - ISBN 5-BNV-MOr.9.00 - UDC / LBC 22.183.4 B871.
↑ Dikin I. I. Iterativ lösning av linjära och kvadratiska programmeringsproblem // Dokl. USSR:s vetenskapsakademi. - 1967. - T. 174 , nr 4 . - S. 747-748 .
↑ Karmanov, 1986 , sid. 63.
↑ Karmanov, 1986 , sid. 80.
↑ Karmanov, 1986 , sid. 77.
↑ Elektronisk lärobok "Ekonomiska och matematiska metoder". Dualitet i linjär programmering Arkiverad 17 juni 2016 på Wayback Machine

Litteratur

Abramov L. M., Kapustin V. F. Matematisk programmering. - Handledning. - L . : LGU, 1981. - 328 sid.
Akof R., Sasieni M. Fundamentals of Operations Research. — Trans. från engelska. V. Ya. Altaeva., ed. I. A. Ushakova. — M .: Mir, 1971. — 551 sid.
Akulich I. L. Kapitel 1. Problem med linjär programmering, Kapitel 2. Specialproblem med linjär programmering // Matematisk programmering i exempel och problem. - M . : Högre skola, 1986. - 319 sid. — ISBN 5-06-002663-9 .
Astafiev NN Oändliga system av linjära ojämlikheter i matematisk programmering. - M. : Nauka, 1991. - 134 sid.
Ashmanov S. A., Timokhov A. V. Optimeringsteori i uppgifter och övningar. - M. : Nauka, 1991. - 446 sid.
Gass S. Linjär programmering. - M. : Fysikalisk-matematisk litteratur, 1961. - 300 sid.
Davydov E. G. Operations Research. - M . : Högre skola, 1990. - 382 sid.
Degtyarev Yu. I. Forskning om operationer. — Lärobok för universitet. - M . : Högre skola, 1986. - 320 sid.
Zukhovitsky S. I., Avdeeva L. I. Linjär och konvex programmering. — M .: Nauka, 1966. — 348 sid.
Karmanov VG Matematisk programmering. — 3:e upplagan. — M .: Nauka, 1986. — 288 sid.
Kuznetsov A. V., Sakovich V. A., Kholod N. I. Högre matematik. Matematisk programmering. - Minsk.: Högre skola, 1994. - 286 sid.
Thomas H. Kormen et al Kapitel 29. Linjär programmering // Algoritmer: Konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
Yudin D. B. , Holstein E. G. Linjär programmering. — M .: Nauka, 1969. — 424 sid.
Dantzig JB Minnen från början av linjär programmering.
Gabasov R., Kirillova F. M. Metoder för linjär programmering. - Minsk: BGU, 1977. - 176 sid.

Länkar

Linear Program Solver (LiPS) — Ett gratis optimeringspaket för att lösa problem med linjär-, heltals- och målprogrammering.
Vershik A. M. O L. V. Kantorovich och linjär programmering
Linjära programmeringsbilder
Bolshakova I. V., Kuralenko M. V. Linjär programmering. Läromedel för kontrollarbetet . (nedlänk sedan 2013-05-13 [3461 dagar])
Barsov A. S. Vad är linjär programmering // Populära föreläsningar om matematik , Gostekhizdat, 1959.
Vyalyi MN Linjära ojämlikheter och kombinatorik . — MTsNMO , 2003.

Ordböcker och uppslagsverk

I bibliografiska kataloger
BNF : 119415380 GND : 4035816-1 J9U : 987007555765405171 LCCN : sh85082127 NDL : 00570683 NKC : ph122356

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering