Lineær programmering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 5. maj 2022; checks kræver 5 redigeringer .

Lineær programmering er en matematisk disciplin dedikeret til teori og metoder til løsning af ekstreme problemer på sæt af dimensionelle vektorrum defineret af systemer af lineære ligninger og uligheder. $n$

Lineær programmering (LP) er et særligt tilfælde af konveks programmering , som igen er et særligt tilfælde af matematisk programmering . Samtidig er det grundlaget for flere metoder til løsning af heltals- og ikke-lineære programmeringsproblemer . En generalisering af lineær programmering er fraktioneret lineær programmering .

Mange egenskaber ved lineære programmeringsproblemer kan også tolkes som egenskaber ved polyedre og kan således formuleres og bevises geometrisk.

Historie

Matematiske undersøgelser af individuelle økonomiske problemer, matematisk formalisering af numerisk materiale blev udført så tidligt som i det 19. århundrede . I den matematiske analyse af den udvidede produktionsproces blev algebraiske relationer brugt, deres analyse blev udført ved hjælp af differentialregning . Dette gjorde det muligt at få en generel idé om problemet.

Udviklingen af økonomien krævede kvantitative indikatorer, og i 1920'erne blev der skabt en tværsektoriel balance ( IOB ). Det var ham, der tjente som drivkraft i skabelsen og studiet af matematiske modeller. Udviklingen af MOB i 1924-1925 i USSR påvirkede økonomen og statistikeren Vasily Vasilievich Leontievs arbejde . Han udviklede en tværsektoriel model for produktion og distribution af produkter.

I 1938 begyndte Leonid Vitalievich Kantorovich i løbet af en videnskabelig konsultation at studere den rent praktiske opgave med at udarbejde den bedste plan for indlæsning af skrælningsmaskiner (krydsfinertrust). Denne opgave egnede sig ikke til konventionelle metoder. Det blev klart, at opgaven ikke var tilfældig. [en]

I 1939 udgav Leonid Kantorovich værket "Mathematical Methods of Organization and Planning of Production", hvori han formulerede en ny klasse af ekstreme problemer med restriktioner og udviklede en effektiv metode til at løse dem, hvorved han lagde grundlaget for lineær programmering.

Studiet af sådanne problemer førte til skabelsen af en ny videnskabelig disciplin af lineær programmering og åbnede et nyt trin i udviklingen af økonomiske og matematiske metoder.

I 1949 udviklede den amerikanske matematiker George Bernard Dantzig en effektiv metode til løsning af lineære programmeringsproblemer (LPP) - simplex-metoden . [en]

Udtrykket "programmering" skal forstås i betydningen "planlægning" (en af oversættelserne af engelsk programmering ). Det blev foreslået i midten af 1940'erne af George Danzig, en af grundlæggerne af lineær programmering, før computere blev brugt til at løse lineære optimeringsproblemer .

Den indre punktmetode blev første gang nævnt af I. I. Dikin i 1967 . [2] . Disse undersøgelser blev fortsat, herunder af indenlandske videnskabsmænd. I 1970'erne lykkedes det V. G. Zhadan at opnå de vigtigste resultater og udvikle en generel tilgang til konstruktionen af indre punktmetoder til løsning af problemer med lineær og ikke-lineær programmering, baseret på transformation af rum; foreslå barriereprojektive og barriere-newtonske numeriske metoder.

Opgaver

Det generelle (standard) problem med lineær programmering er problemet med at finde minimum af en lineær objektiv funktion (lineær form) af formen [3] :

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

Et problem, hvor der opstår begrænsninger i form af uligheder, kaldes et grundlæggende lineæ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 lineær programmering vil have en kanonisk form, hvis der i hovedproblemet i stedet for det første system af uligheder er et system af ligninger med begrænsninger i form af lighed [4] :

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

Hovedproblemet kan reduceres til et kanonisk problem ved at indføre yderligere variabler.

Lineære programmeringsproblemer af den mest generelle form (problemer med blandede begrænsninger: ligheder og uligheder, tilstedeværelsen af variable fri for begrænsninger) kan reduceres til ækvivalente (som har samme sæt af løsninger) ændringer af variable og erstatning af ligheder med et par uligheder [5] .

Det er let at se, at problemet med at finde maksimum kan erstattes af problemet med at finde minimum ved at tage koefficienterne med det modsatte fortegn. $c$

Eksempler på problemer

Maksimal matchning

Overvej det maksimale matchningsproblem i en todelt graf : der er flere drenge og piger, og for hver dreng og pige ved man, om de kan lide hinanden. Det er nødvendigt at gifte det maksimale antal par med gensidig sympati.

Lad os introducere variabler , der svarer til parret fra -th dreng og -th pige og opfylder begrænsningerne: $x_{ij}$ $jeg$ $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 , hvor er lig med 1 eller 0 afhængigt af om den -th dreng og -th pige er søde ved hinanden. Det kan påvises, at blandt de optimale løsninger på dette problem er der en heltalsløsning. Variabler lig med 1 vil svare til par, der bør være gift. ${\displaystyle f=c_{11}x_{11}+c_{12}x_{12}+\ldots +c_{nm}x_{nm))$ $c_{ij}$ $jeg$ $j$

Maksimalt flow

Lad der være en graf (med rettede kanter), hvor for hver kant dens kapacitet er angivet. Og to hjørner er givet: en vask og en kilde. Det er nødvendigt at specificere for hver kant, hvor meget væske der vil strømme gennem den (ikke mere end dens kapacitet) for at maksimere den totale strøm fra kilde til synk (væske kan ikke forekomme eller forsvinde ved alle hjørner undtagen henholdsvis kilde og synke).

Lad os tage mængden af væske, der strømmer gennem den th kant, som variable. Derefter $x_{i}$ $jeg$

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

hvor er kapaciteten af den th kant. Disse uligheder skal suppleres med ligheden mellem mængden af indgående og udgående væske for hvert toppunkt, undtagen for synken og kilden. Som funktion er det naturligt at tage forskellen mellem mængden af udstrømmende og indstrømmende væske ved kilden. $c_{i}$ $jeg$ $f$

En generalisering af det tidligere problem er den maksimale strøm af minimumsomkostninger. I dette problem er omkostningerne for hver kant givet, og det er nødvendigt at vælge blandt de maksimale strømme flowet med minimumsomkostningerne. Denne opgave er reduceret til to lineære programmeringsproblemer: Først skal du løse problemet med det maksimale flow, og derefter tilføje begrænsningen til dette problem , hvor er værdien af det maksimale flow, og løse problemet med en ny funktion - omkostningerne ved flowet. $f(x)\geqslant m$ $m$ $f(x)$

Disse problemer kan løses hurtigere end med generelle algoritmer til løsning af lineære programmeringsproblemer på grund af den særlige struktur af ligninger og uligheder.

Transportproblem

Der er en vis homogen last, der skal transporteres fra lagre til fabrikker. For hvert lager er det kendt, hvor meget last der er i det , og for hvert anlæg er dets behov for last kendt. Transportomkostningerne er proportionale med afstanden fra lageret til fabrikken (alle afstande fra det -. lager til -. fabrikken er kendt). Det er påkrævet at udarbejde den billigste transportplan. $n$ $m$ $jeg$ $a_{i}$ $b_{j}$ $c_{ij}$ $jeg$ $j$

De afgørende variabler i dette tilfælde er - mængden af gods, der transporteres fra det -. lager til -. De opfylder begrænsningerne: $x_{ij}$ $jeg$ $j$

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

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

Den objektive funktion har formen: , som skal minimeres. $f(x)=x_{{11}}c_{{11}}+x_{{12}}c_{{12}}+\ldots +x_{{nm}}c_{{nm}}$

Nulsum spil

Der er en størrelsesmatrix . Den første spiller vælger et tal fra 1 til , den anden - fra 1 til . Så tjekker de tallene, og den første spiller får point, og den anden får point ( - nummeret valgt af den første spiller - den anden). Vi skal finde den optimale strategi for den første spiller. $EN$ $n\ gange m$ $n$ $m$ $a_{{ij}}$ $(-a_{{ij}})$ $jeg$ $j$

Indtast den optimale strategi, for eksempel den første spiller, nummeret skal vælges med sandsynlighed . Så er den optimale strategi en løsning på følgende lineære programmeringsproblem: $jeg$ $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 ),

hvor funktionen skal maksimeres . Værdien i den optimale løsning vil være den værst tænkelige forventning om den første spillers udbetaling. $f(p_{1},\;\ldots ,\;p_{n},\;c)=c$ $c$

Løsningsalgoritmer

Den mest berømte og udbredte i praksis til at løse det generelle problem med lineær programmering (LP) er simpleksmetoden . På trods af at simplex-metoden er en ret effektiv algoritme, der har vist gode resultater i løsning af anvendte LP-problemer, er det en algoritme med eksponentiel kompleksitet . Årsagen til dette er den kombinatoriske karakter af simplex-metoden, som successivt opregner toppunkterne i polyederen af tilladelige løsninger, mens man søger efter den optimale løsning.

Den første polynomielle algoritme , ellipsoidmetoden , blev foreslået i 1979 af den sovjetiske matematiker L. Khachiyan , og løste dermed et problem, der havde været uløst i lang tid. Ellipsoidmetoden har en helt anden ikke-kombinatorisk karakter end simpleksmetoden. Men i beregningsmæssig henseende viste denne metode sig ikke at være lovende. Ikke desto mindre førte selve den polynomiske kompleksitet af problemerne til skabelsen af en hel klasse af effektive LP-algoritmer - indre punktmetoder , hvoraf den første var N. Karmarkars algoritme foreslået i 1984 . Algoritmer af denne type bruger en kontinuerlig fortolkning af LP-problemet, når der i stedet for at opregne hjørnerne af polytopen af løsninger til LP-problemet, søges langs baner i rummet af variabler af problemet, der ikke passerer gennem knudepunkterne af polytopen. Den indre punktmetode, som i modsætning til simplex-metoden omgår punkter fra det indre af toleranceområdet, bruger ikke-lineær programmering af logaritmiske barrierefunktionsmetoder udviklet i 1960'erne af Fiacco og McCormick.

En anden metode til at løse LP er at bruge Seidel-algoritmen:

LP'en er givet i kanonisk form med variabler og begrænsninger, der udgør sættet . $d$ $m$ $H$
Hvis eller , udled den optimale basisløsning . $d=1$ $m=0$ $H$
Ellers skal du vælge en tilfældig begrænsning og rekursivt beregne den optimale basisløsning for . $h\in H$ ${\displaystyle H\setminus \{h\))$
Hvis den optimale basisløsning for ikke overtræder begrænsningen , skal du returnere den. ${\displaystyle H\setminus \{h\))$ $h$
Ellers skal du beregne skæringspunktet mellem LP-polyederet og hyperplanet og rekursivt løse den resulterende LP med en variabel. $h$ $d-1$

Denne metode har asymptotisk kompleksitet . $O(m\cdot d!)$

Problemer med dobbelt lineær programmering

Hvert lineært programmeringsproblem [6] i formularen

\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 er muligt på en bestemt måde at sammenligne et andet lineært programmeringsproblem, kaldet dobbelt eller konjugeret, med det originale eller direkte. Forbindelsen mellem de oprindelige og dobbelte problemer ligger hovedsageligt i, at løsningen af det ene af dem kan opnås direkte fra løsningen af det andet. Lad os definere det dobbelte problem med hensyn til det oprindelige lineære programmeringsproblem

Indledende opgave	Dobbelt 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$

Hvis vektorerne og er tilladelige løsninger på de primære og dobbelte problemer, så , og lighed opnås, hvis og kun hvis og er optimale løsninger. Hvis den objektive funktion af et af parret af dobbelte problemer ikke er begrænset (ovenfra for det originale, nedefra for det dobbelte), så er området med mulige løsninger på det andet problem tomt. $x$ $y$ $F(x)\leqslant T(y)$ $x$ $y$

Hvis vektorerne og er de optimale løsninger af henholdsvis de direkte og dobbelte problemer, så er følgende ligheder sande $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 vil sige, at for optimale løsninger på de primære og dobbelte problemer svarer ikke-spændte (streng ulighed er opfyldt) begrænsninger til nul variabler, og ikke-nul variable (inkluderet i støtteplanen) svarer til stram (ikke-streng ulighed er implementeret som lighed) begrænsninger. Men der kan være nul variabler svarende til stramme begrænsninger.

Disse egenskaber ved dobbeltløsninger kan reducere løsningstiden markant, hvis du skal løse et problem med en række begrænsninger, der er meget større end antallet af variable. Derefter er det muligt, efter at have løst det dobbelte problem, at finde dens støtteplan, hvorefter man i det direkte problem kun har valgt de begrænsninger, der svarer til støtteplanen (alle disse begrænsninger skal spændes), løse det sædvanlige system af lineære ligninger for dem.

Sætning. Det dobbelte af det dobbelte LP-problem er det primære LP-problem.

Bevis: Overvej en direkte LP af formen under betingelsen . Lad os forbinde den dobbelte LP med den og få den under betingelsen . Lad os bringe det til en anden form, tilsvarende i betydning: under betingelsen . Lad os igen sammenligne den dobbelte LP med den og få den under betingelsen . Vi bringer den i en tilsvarende form og får en LP identisk med den originale: under betingelsen . ${\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$

Software

lp_solve er open source-software (LGPL GNU GNU General Public License for Libraries ) til løsning af lineære ligninger. LpSolve har en IDE , native C API og mange andre API'er til Java, AMPL, MATLAB, Wolfram Mathematica, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R og Microsoft Solver Foundation .

Se også

Noter

↑ 1 2 Kilde: Altai Regional Universal Scientific Library. V. Ya. Shishkova (AKUNB) Arkiveret 5. marts 2022 på Wayback Machine . Optimeringsmetoder: Proc. godtgørelse. Brazovskaya N.V.; Altai State Technical University I. I. Polzunova, [Afstandscenter. læring]. - Barnaul: AltGTU Publishing House, 2000. - 120 s. - ISBN 5-BNV-MOr.9.00 - UDC / LBC 22.183.4 B871.
↑ Dikin I. I. Iterativ løsning af lineære og kvadratiske programmeringsproblemer // Dokl. USSR's Videnskabsakademi. - 1967. - T. 174 , nr. 4 . - S. 747-748 .
↑ Karmanov, 1986 , s. 63.
↑ Karmanov, 1986 , s. 80.
↑ Karmanov, 1986 , s. 77.
↑ Elektronisk lærebog "Økonomiske og matematiske metoder". Dualitet i lineær programmering Arkiveret 17. juni 2016 på Wayback Machine

Litteratur

Abramov L. M., Kapustin V. F. Matematisk programmering. - Tutorial. - L . : LGU, 1981. - 328 s.
Akof R., Sasieni M. Fundamentals of Operations Research. — Trans. fra engelsk. V. Ya. Altaeva., red. I. A. Ushakova. — M .: Mir, 1971. — 551 s.
Akulich I. L. Kapitel 1. Problemer med lineær programmering, Kapitel 2. Særlige problemer med lineær programmering // Matematisk programmering i eksempler og problemer. - M . : Højere skole, 1986. - 319 s. — ISBN 5-06-002663-9 .
Astafiev NN Uendelige systemer af lineære uligheder i matematisk programmering. - M. : Nauka, 1991. - 134 s.
Ashmanov S. A., Timokhov A. V. Optimeringsteori i opgaver og øvelser. - M. : Nauka, 1991. - 446 s.
Gass S. Lineær programmering. - M. : Fysisk-matematisk litteratur, 1961. - 300 s.
Davydov E. G. Operations Research. - M . : Højere skole, 1990. - 382 s.
Degtyarev Yu. I. Forskning af operationer. — Lærebog for universiteter. - M . : Højere skole, 1986. - 320 s.
Zukhovitsky S. I., Avdeeva L. I. Lineær og konveks programmering. — M .: Nauka, 1966. — 348 s.
Karmanov VG Matematisk programmering. — 3. udgave. — M .: Nauka, 1986. — 288 s.
Kuznetsov A. V., Sakovich V. A., Kholod N. I. Højere matematik. Matematisk programmering. - Minsk.: Højere skole, 1994. - 286 s.
Thomas H. Kormen et al. Kapitel 29. Lineær programmering // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
Yudin D. B. , Holstein E. G. Lineær programmering. — M .: Nauka, 1969. — 424 s.
Dantzig JB Erindringer om begyndelsen af lineær programmering.
Gabasov R., Kirillova F. M. Metoder til lineær programmering. - Minsk: BGU, 1977. - 176 s.

Links

Linear Program Solver (LiPS) — En gratis optimeringspakke til løsning af problemer med lineær, heltal og målprogrammering.
Vershik A. M. O L. V. Kantorovich og lineær programmering
Lineære programmeringsdias
Bolshakova I. V., Kuralenko M. V. Lineær programmering. Læremiddel til kontrolarbejdet . (downlink siden 13-05-2013 [3461 dage])
Barsov A. S. Hvad er lineær programmering // Populære forelæsninger om matematik , Gostekhizdat, 1959.
Vyalyi MN Lineære uligheder og kombinatorik . — MTsNMO , 2003.

Ordbøger og encyklopædier

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

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