De enklaste är de så kallade linjära deterministiska modellerna. De ges i form av en linjär form av kontrollvariabler ( X):

W = a 0 + a 1 x 1 + … + a k x k

under linjära begränsningar av formen

b 1 j x 1 + b 2 j x 2 + … + b kj x k ³ bj , j = 1,…, q 1 ;

c 1 j x 1 + c 2 j x 2 + … + c kj x k = cj , j = 1,…, q 2 ;

d 1 j x 1 + d 2 j x 2 + … + d kj x k £ d j , j = 1,…, q 3 .

Totalt antal begränsningar m = q 1 + q 2 + q 3 kan överstiga antalet variabler (m> k). Dessutom är villkoret för positivitet hos variabler ( x i ³ 0).

Svarsytan för den linjära modellen är hyperplan. Tänk till exempel på en linjär modell med två variabler av följande form:

W=–2x 1 –3x 2 (2.2)

under följande begränsningar

(2.3)

2x 1 + 3x 2 £18;

x 1 – 4x 2 £4;

–2x 1 + x 2 £2;

X 1 ³ 0; x 2 ³ 0.

Giltigt intervall (definitionsomfång) OABCD för modell (2.2) bildas av begränsningar (2.3) (Fig. 2.2). Svarsytan är en platt polygon OA"B"C"D"(Fig. 2.2, b).

För en viss begränsningsrelation kan uppsättningen av genomförbara lösningar saknas (tom). Ett exempel på en sådan uppsättning visas i fig. 2.3. Direkt AC Och Sol begränsa intervallet för tillåtna värden ovanifrån. Den tredje begränsningen skär av området med tillåtna värden nedanför från den raka linjen AB. Det finns alltså inget gemensamt område som uppfyller alla tre begränsningarna.

Linjära modeller är ganska enkla och därför innebär de å ena sidan en betydande förenkling av problemet, och å andra sidan tillåter de utvecklingen av enkla och effektiva lösningsmetoder.

I studien av DLA används linjära modeller sällan och nästan uteslutande i den ungefärliga beskrivningen av problem.

Linjära modeller kan användas för steg-för-steg approximation av icke-linjära modeller (linjärisering av problemet). Denna teknik är särskilt effektiv när man studerar små områden av det studerade utrymmet. Representationen av enskilda sektioner av den olinjära svarsytan med en linjär modell ligger bakom stor grupp optimeringsmetoder, de så kallade metoderna med linjär taktik.

Studiet av linjära modeller är inte svårt. I synnerhet påverkan av var och en av variablerna på egenskaperna hos modellen av formuläret

W = a 0 + a 1 x 1 + a 2 x 2 + …+ a k x k

ges av dess koefficienter:

, i = 1,…, k.

För att hitta den linjära modellens optimum W opt utvecklade en effektiv simplexmetod.

De enklaste kostnadsmodellerna, betraktade som en uppsättning kostnader, reduceras ibland till linjära.

Ett exempel på en sådan modell är den klassiska transportkostnadsmodell (transportproblem)(Figur 2.4).

Tillgängliga k produktionspunkter
(i = 1,…, k) Och m konsumtionspunkter
(j = 1,…, m) av någon produkt. Mängden produkt som produceras i varje k produktionspunkter, ett i; mängden produkt som behövs i varje m konsumtionspunkter, bj.

Jämlikheten mellan total produktion och konsumtion antas:

Mängd produkt som transporteras från i-th produktionspunkten i j-th punkt för konsumtion, lika med xij; kostnaden för att transportera en enhet av denna produkt - med ij.

Total kostnad för transport MED S ges linjär modell:

under följande begränsningar

Linjära modeller inkluderar även modeller i form av linjära differentialekvationer (ordinära eller partiella derivator).

Linjär ordinär differentialekvation n beställningen har formen

De initiala villkoren skrivs som

En linjär partiell differentialekvation har formen

Modellen, given som en partiell differentialekvation, inkluderar initiala och randvillkor (villkor på gränsen för definitionsdomänen för funktionen F( t)).

2.3. Studie av den enklaste matematiska modellen
drift av en gasturbinmotor

Gasturbinmotorn (GTE) är huvudkraftverket för moderna flygplan.

GTE-schemat har formen som visas i fig. 2.5.

Här 1 – inloppsspridare; 2 - kompressor; 3 - förbränningskammaren; 4 – turbin;
5 - utloppsmunstycke.

GTE-arbetscykeln inkluderar följande steg:

1) Mötande med fart V luftflödet genom diffusorn kommer in i kompressorn.

2) Kompressorn, som roterar på samma axel som turbinen, komprimerar luften som kommer in i förbränningskammaren.

3) Bränsle (fotogen) sprutas ständigt in i förbränningskammaren, som blandas med tryckluft.

4) Gasen som genereras vid förbränning kommer in i turbinen, vilket accelererar den till en hastighet W.

5) Vid denna hastighet sprutas gasen ut genom munstycket till atmosfären.

På grund av det faktum att W > V, genereras dragkraft R, vilket gör att flygplanet kan flyga i atmosfären.

Ändringen i dragkraften utförs genom att ändra hastigheten på bränsleinsprutningen i förbränningskammaren genom att flytta motorns kontrollratt (THROT). Förflyttningen av gasreglaget till en viss vinkel d av gasreglaget utförs antingen manuellt av piloten, eller med hjälp av ett manöverdon enligt signaler från ACS under flygning. En ökning av värdet på d-dragkraften orsakar en ökning av kraften R, och en minskning är en minskning av denna kraft.

GTE är komplext tekniskt system, där ett betydande antal fysikaliska och kemiska processer äger rum. Motorn är utrustad med alla typer av automationsanordningar, system för att vrida och kyla turbinblad m.m. Naturligtvis kommer den matematiska beskrivningen av gasturbinmotorns funktion också att vara ganska besvärlig, inklusive system av differentialekvationer i partiella derivator, vanliga differentialekvationer, transcendentala funktioner, algoritmer digitalt system maskinkontroll. Sådana modeller används i processen att designa gasturbinmotorer.

För att lösa problemen med flygkontroll, mer än enkel modell GTE, som är beroendet av tryckkraften R från vinkeln d för gasreglagets avvikelse för gasreglaget. Processen att ändra dragkraften beskrivs av en vanlig differentialekvation av formen:

, (2.11)

där t > 0 är motorns tidskonstant, som beror, förutom designegenskaperäven på omgivningstemperaturen, dess fuktighet och andra yttre faktorer; k[kg/grad] – proportionalitetskoefficient.

Initialvillkoret för ekvation (2.11) skrivs som

R(0) = R 0 . (2.12)

Således är ekvation (2.11) tillsammans med initialvillkoret (2.12). den enklaste matematiska modellen av gasturbinmotorn, skriven i form av en vanlig differentialekvation 1-:e ordningen.

För att bestämma proportionalitetsfaktorn k kalibreringskurvor för dragkraftens beroende av gasspjällens rotationsvinkel, byggda på basis av experimentella data, används. Tangensen för grafens lutning är lika med den önskade koefficienten.

Integration av ekvation (2.11) med utgångsvillkoret (2.12) gör det möjligt att ta reda på hur axialkraften förändras över tiden (Fig. 2.6).

När gasen avleds, dragkraften Rökar och stabiliseras sedan vid ett visst gränsvärde, d.v.s. GTE är ett tröghetsobjekt.

Dragkraftsgräns vi får från (2.11) när hastigheten för dess förändring är lika med noll:

. (2.13)

Stigtid beror på värdet på motortidskonstanten t. Processen anses vara stadig när t = t mun, när dragkraften går in i den så kallade femprocentskorridoren av gränsvärdet för dragkraften (fig. 2.6). Ju större t, desto trögare är motorn och följaktligen desto mer t mun

På fig. 2.7 visar dragkraftens beteende beroende på gasreglagets avböjningsvinkel vid t = 0,5.

Tryckkraften under start, när gasreglaget avböjs med 10°, når ett stabilt tillstånd i den tredje sekunden och når ett värde på 3390 kg. Tio sekunder efter start, när gasreglaget avböjs 20°, ställs dragkraften in på 6780 kg, och ytterligare tio sekunder senare, när gasen avböjs 30°, ställs dragkraften in på 10170 kg. Gränsvärdet för dragkraften är
14270 kg.

Liknande information.

3.1. Allmän uppgift linjär programmering

Linjär programmering- detta är den mest utvecklade delen av matematisk programmering, med hjälp av vilken analys och lösning av extrema problem med linjära anslutningar och begränsningar utförs.

Linjär programmering inkluderar ett antal heuristiska (ungefärliga) lösningsmetoder som tillåter, under givna förhållanden, från alla alternativ lösningar på produktionsproblem för att välja det bästa, optimala. Dessa metoder inkluderar följande - grafisk, simplex, potentiell metod (modifierad distributionsmetod - MOD), Khichkov, Kreko, Vogel approximationsmetod och andra.

Vissa av dessa metoder förenas av ett gemensamt namn - distributions- eller transportmetoden.

Födelseplatsen för linjär programmering är Ryssland. Det första arbetet med linjär programmering av den blivande akademikern L.V. Kantorovich publicerades 1939. 1975 fick han Nobelpriset i ekonomi för utvecklingen av linjära programmeringsmetoder. Eftersom de flesta verk av akademiker L.V. Kantorovich ägnar sig åt att lösa transportproblem, man kan anse att det nämnda Nobelpriset också markerar den ryska transportvetenskapens förtjänster.

Inom vägtransporter har linjära programmeringsmetoder använts sedan 1960-talet för att lösa ett stort antal av de viktigaste produktionsproblemen, nämligen: att minska avståndet för godstransporter; utarbeta ett optimalt transportsystem; val av de kortaste rörelsevägarna; uppgifter för transport av olika, men utbytbara laster; skift-daglig planering; planering av transport av små partier; distribution av bussar längs sträckor och annat.

Funktionerna i den linjära programmeringsmodellen är följande:

Den objektiva funktionen och begränsningarna uttrycks linjära beroenden(jämlikheter eller ojämlikheter);

Antalet beroenden är alltid mindre än antalet okända (osäkerhetstillstånd);

Icke-negativitet för de nödvändiga variablerna. Den allmänna formen för att skriva en linjär programmeringsmodell i förkortad form är följande:

Hitta X ij ≥ 0 (j = 1, 2…n) under följande typ av begränsningar:

Dessa begränsningar minimerar (eller maximerar) den objektiva funktionen

Standardformen för att skriva en linjär programmeringsmodell är ett system av linjära ekvationer skrivna i kanonisk form, det vill säga i form av linjära likheter, i icke-negativa tal:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n \u003d b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n \u003d b 2 ; (3.1)

……………………………..

a m x 1 + a m 2 x 2 + ...+ a mn x n = b m ..

Om modellen skrivs i form av ojämlikheter i icke-negativa tal, dvs den har formen

a 11 x 1 + a 12 x 2 + ... + a 1 n x n ≤ b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)

……………………………..

a m x 1 + a m 2 x 2 + …+ a mn x n ≤ b m ,..

då reduceras denna post till kanonisk form (3.1) genom att införa ytterligare variabler xn+1> 0 (i=1,2…m) till vänster om olikheten (eller minskning av antalet variabler om olikhetstecknet är riktat i motsatt riktning). Ytterligare variabler ligger till grund.

Standardformen för att lösa ett linjärt programmeringsproblem är att hitta lösningar på ett system av linjära ekvationer i icke-negativa tal som minimerar objektivfunktionen. Den objektiva funktionen har då formen

L = c 1 x 1 + c 2 x 2 ... c n x n → min, (3,3)

Var s 1 , s 2 … s när objektiva funktionskoefficienter L med variabler X j .

Ytterligare variabler kommer in i målfunktionen med nollkoefficienter.

När det gäller att maximera den objektiva funktionen L tecknen på variablerna för den objektiva funktionen bör vändas, och vi kommer återigen till minimeringsproblemet, dvs. en uppgift reduceras till en annan ersättning L på - L eller max L=min(- L).

En grundläggande lösning av ett system av linjära ekvationer (3.1) är en lösning där nollvärden ges till icke-grundläggande variabler.

En baslösning kallas tillåten där de variabler som ingår i underlaget är icke-negativa.

En tillåten lösning som maximerar (eller minimerar) objektivfunktionen (3.3) kallas optimal.

Varje linjär programmeringsproblem motsvarar ett annat, kallat det dubbla linjära programmeringsproblemet. Det ursprungliga problemet med avseende på den dubbla kallas det direkta problemet. De primära och dubbla problemen bildar ett par, som kallas det dubbla paret i linjär programmering. Primal- och dubbelparet bildar ett asymmetriskt par när primalproblemet skrivs i kanonisk form, och ett symmetriskt par när problemens villkor skrivs som olikheter.

Reglerna för att sammanställa en matematisk modell av ett dubbelproblem baseras på reglerna för matriskalkyl.

Begreppet dualitet används flitigt i analysen av linjära programmeringsproblem. Dualitetens egenskap beaktas i detalj i varje specifikt fall.

3.2. Grafanalytisk metod

Grafanalytisk metod är en av de enklaste metoderna för linjär programmering. Det avslöjar tydligt essensen av linjär programmering, dess geometriska tolkning. Dess nackdel är att det låter dig lösa problem med 2 eller 3 okända, d.v.s. det är tillämpligt på ett smalt antal problem. Metoden bygger på reglerna för analytisk geometri.

Lösa ett problem med två variabler x 1 Och x 2, som, enligt problemets innebörd, inte bör vara negativ, utförs i systemet med kartesiska koordinater. Ekvationer x 1=0 och x 2= 0 är axlarna för koordinatsystemet för den första kvadranten

Låt oss överväga lösningsmetoden med ett specifikt exempel.

Exempel 3.1. Det finns 300 ton skumbetongprodukter och 200 ton stålprodukter i lager. Bilföretaget måste leverera dessa produkter till anläggningen under uppbyggnad. Bilföretaget har lastbilar KAMAZ - 5320 och

ZIL-4314. För en resa kan KamAZ-5320 leverera 6 ton skumbetong och 2 ton stål, och vinsten från resan kommer att vara 4 tusen rubel. ZIL-4314 levererar 2 ton skumbetong och 4 ton stål på en resa, vinsten från resan är 6 tusen rubel. Det är nödvändigt att organisera transporter på ett sådant sätt att bilföretaget får den största vinsten.

Låt oss konstruera en matematisk modell av problemet. Ange med x 1 det önskade antalet resor KamAZ-5320 och genom X 2 krävs antal ZIL-4314 förare.

Den totala transporten i ton skumbetongprodukter är 6 x 1+ 2x 2, och från stål 2 x 1+ 4x 2. Fraktgränsen, baserat på antalet tillgängliga artiklar, är 6 x 1+ 2x 2 ≤ 300t för skumbetong och 2 x 1+ 4x 2 ≤ 200t för stål.

Total vinst i tusen rubel. uttryckt som 4 X 1 + 6X 2 , som behöver maximeras och som är optimalitetskriteriet i det aktuella problemet. Den matematiska modellen av problemet ser alltså ut som följande. Det är nödvändigt att maximera den objektiva funktionen

L = 4x 1+ 6x 2 → max under förhållanden: 6 x 1+ 2x 2 ≤ 300; 2x 1+ 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.

Tänk på ekvation 6 x 1+ 2x 2 = 300. För att konstruera en linje som beskrivs av denna ekvation, finner vi två punkter som ligger på denna linje. På x 1= 0 från ekvationen för en rät linje finner vi 2 x 2 = 300, varifrån x 2 \u003d 150. Därför ligger punkt A med koordinater (0,150) på den önskade linjen. På x 2= 0 vi har 6 x 1\u003d 300, varifrån x 1 \u003d 50, och punkten D med koordinater (50,0) finns också på önskad linje. Rita en linje genom dessa två punkter AD(Fig. 3.1).

Linjär ojämlikhet 6 x 1+ 2x 2 ≤ 300 är ett halvplan beläget på ena sidan av den konstruerade linjen 6 x 1+ 2x 2 = 300. För att ta reda på vilken sida av denna linje punkterna i det önskade halvplanet är placerade, ersätter vi med olikhet 6 x 1+ 2x 2 ≤ 300 koordinater för någon punkt som inte ligger på gränslinjen. Till exempel är ursprunget 0-(0,0). Den uppfyller olikheten 6∙0 + 2∙0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD och i fig. 3.1 är skuggad.

Ekvation 2 x 1+ 4x 2= 200 kommer att konstrueras från två punkter. På x 1 = 0 4x 2 = 200 varifrån x 2 = 50. Peka sedan E har koordinater (0,50) och tillhör den önskade raden. På x 2= 0, 2x 2 = 200 prickar Medär på den givna linjen med koordinater (100,0). Ersätter punktens koordinater i ojämlikheten Med(0,0), vi får 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

Uppgiftsbegränsningssystemet kräver att planer ( x 1; x 2) uppfyller alla fyra ojämlikheterna, d.v.s. tillåtna mönster är poäng ( x 1; x 2) måste samtidigt vara i alla fyra halvplanen. Detta krav uppfylls endast av punkter placerade inuti och på gränsen till polygonen. OEKD, som är polygonen av tillåtna lösningar.

Spetsarna i polygonen av möjliga lösningar är punkterna O, E, K, D linjesegment OE, EK, KD, OD- hans revben. Vilken punkt som helst i polygonen OEKDär planen för uppgiften, som uppfyller alla dess villkor. Polygonens hörn bildas av skärningen av två räta linjer och motsvarar de grundläggande planerna för problemet, bland vilka är den bästa (optimala) planen. Således kommer det att finnas lika många referensplaner som det finns hörn i polygonen av genomförbara lösningar.

En visuell geometrisk representation kan också erhållas för objektivfunktionen L = 4x 1+ 6x 2. Vi fixar till exempel något värde på objektivfunktionen L= 120. ekvation 4 x 1+ 6x 2 = 120 definierar en linje som går genom en punkt I med koordinater (x 1 \u003d 0; x 2 \u003d 20) och en punkt L med koordinater (( X 1 = 30; X 2 = 0). Linjesegmentet BL ligger inuti polygonen OEKD. Därför, för alla planer (punkter) i detta segment är värdet på målfunktionen detsamma och lika med 120. Genom att ge andra värden på målfunktionen får vi parallella linjer, som kallas nivålinjer målfunktion.

Flytta linjen L parallellt med sig själv i en riktning får vi en ökning av den objektiva funktionen, och i motsatt riktning - dess minskning. I det här exemplet, rörelsen av en rak linje BL till höger bestämmer ökningen av den målfunktion som vi maximerar. Vi gör detta fram till raden BL kommer att ha minst en gemensam punkt med polygonen av tillåtna lösningar OEKD. Från fig. 3.1 följer att den sista punkten som den räta linjen på nivån för målfunktionen skär kommer att vara punkten TILL. Det betyder att poängen TILL bestämmer den optimala uppgiftsplanen.

Ökningsriktningen vinkelrätt mot nivålinjen kallas riktningen för den största ökningen objektiv funktion och bestämmer dess maximala vinst. Denna riktning kan ställas in utan att rita nivålinjer. För detta är det nödvändigt på axlarna x 1 Och x 2 avsätta segment lika med koefficienterna för den objektiva funktionen, och med hjälp av dem, som i koordinater, konstruera en vektor med den största ökningen av den objektiva funktionen. I matematik heter det lutning och betecknas med tecknet grad. Gradient för en funktion L = 4x 1 + 6x 2 kommer vektor n| 4; 6 | . För att underlätta dess konstruktion ökar vi koordinaterna, till exempel med 10 gånger, dvs. n | 40; 60 | . Låt oss konstruera gradienten för den objektiva funktionen L, för vilken vi kopplar punkten med koordinater (40; 60) med origo. Linjerna för objektivfunktionsnivån ritas vinkelrätt mot gradientens riktning.

Så på ett eller annat sätt är det fastslaget att poängen TILL bestämmer den optimala uppgiftsplanen, vars värden för variablerna motsvarar koordinaterna för den givna punkten. För att fastställa koordinaterna är det nödvändigt att lösa ekvationssystemet för de räta linjerna som bildar denna vertex:

6x 1+ 2x 2= 300;

2x 1+ 4x 2= 200.

Vi utjämnar koefficienterna vid x 1 genom att multiplicera den andra ekvationen med 3 och subtrahera den första från den andra ekvationen. Låt oss få 10 x 2= 300,x 2 = 30. Genom att ersätta värdet x 2 \u003d 30 i någon av ekvationerna, till exempel i den första, bestämmer vi värdet X 1:

6x 1+ 2X · 30 = 300,

varifrån 6 x 1 = 300 - 60 = 240, därför x 1 = 40.

Således, för att få mest vinst för ett bilföretag, är det nödvändigt att genomföra 40 resor till KamAZ-5320 och 30 resor till ZIL-4314. Den maximala vinsten i detta fall blir

L = 4x 1+ 6x 2\u003d 4 40 + 6 30 \u003d 340 tusen rubel.

Baserat på det övervägda exemplet och den geometriska tolkningen av optimeringsproblemet med två variabler kan vi dra följande slutsatser:

1) i tvådimensionellt utrymme är området för möjliga lösningar en polygon;

2) varje sida av polygonen motsvarar värdet av en variabel lika med noll;

3) varje hörn av polygonen av tillåtna lösningar motsvarar värdena för två variabler lika med noll;

4) varje värde på målfunktionen motsvarar en rät linje;

5) den optimala lösningen av problemet motsvarar polygonens vertex, där objektivfunktionen får det optimala värdet, medan de optimala variablerna är koordinaterna för denna vertex.

I det allmänna fallet har optimeringsproblem en liknande geometrisk tolkning. Uppsättningen av uppgiftsplaner kommer att vara en polyeder vars hörn motsvarar referensplanerna. När man löser problemet utförs övergången från en vertex av polyhedron till en annan med ett stort värde på objektivfunktionen tills dess optimala värde erhålls. Observera att effektiviteten av optimeringsmetoder ligger just i det faktum att uppräkningen av hörn (iteration) endast utförs i riktning mot den största ökningen av målfunktionen. Därför beaktas inte alla hörn, av vilka det finns ett stort antal, utan bara de som är närmare den extrema.

När man bestämmer en klass av optimeringsproblem och väljer en metod för att lösa den är det nödvändigt att veta om uppsättningen av möjliga lösningar är konvex eller icke-konvex, en linjär eller icke-linjär objektiv funktion.

Per definition kallas en uppsättning konvex om för två punkter hela segmentet som förbinder dessa punkter tillhör denna uppsättning. Exempel på konvexa mängder är till exempel ett segment (fig. 3.2, a), ett plan i form av en cirkel, en kub, en parallellepiped samt polygoner som är helt placerade på ena sidan av var och en av dess sidor , etc.

På fig. 3.2b visar icke-konvexa uppsättningar. I icke-konvexa mängder kan man ange minst två punkter i segmentet AB som inte tillhör den aktuella mängden.

3.3. Enkel metod

Enkel metodär en vanlig metod för att lösa linjära programmeringsproblem. Metoden fick sitt namn från ordet "simplex", som betecknar den enklaste konvexa polygonen, vars antal hörn alltid är en mer än rummets dimension. Simplexmetoden utvecklades i USA av matematikern J. Dantzig i slutet av 1940-talet.

Simplexmetoden inkluderar att erhålla en icke-negativ grundlösning av ett system av kanoniska linjära ekvationer av typen (3.1), efterföljande minimering (maximering) av objektivfunktionen (3.3) och på detta sätt hitta de optimala värdena för nödvändiga variabler x 1, x 2... x n.

Idén med simplexmetoden ligger i det faktum att man under beräkningen sekventiellt går från den första grundläggande lösningen till den andra, tredje, etc. genom den sk simplex transformationer. Transformationer görs i form av simplextabeller, vilket avsevärt förenklar och påskyndar beräkningar.

För att erhålla icke-negativa grundläggande lösningar av ett system av linjära ekvationer, är det nödvändigt att utföra processen för att eliminera okända på ett sådant sätt att de fria termerna för ekvationerna förblir icke-negativa i alla stadier av processen. I detta fall bör man vägledas av följande regel: varje fri variabel för vilken det finns minst en positiv koefficient tas som en ny basvariabel; en variabel härleds från basen, som motsvarar det minsta förhållandet mellan ekvationernas fria termer och motsvarande positiva koefficienter för ekvationerna med variabeln införd i basen. Sådana transformationer kallas simplex-omvandlare.

Detta är mycket viktigt, eftersom för att hitta en viss icke-negativ lösning som motsvarar det största möjliga värdet av en fri variabel med nollvärden av andra fria variabler, istället för att bestämma intervallet för den angivna variabeln och ersätta dess största möjligt värde till gemensamt beslut det räcker med att ta denna variabel som den grundläggande och utsätta systemet för en simplextransformation, övergå till en ny bas, vilket avsevärt förenklar beräkningarna.

Beräkningar utförs bekvämt med simplextabeller. Övergången från en tabell till en annan motsvarar en iteration, d.v.s. övergången från en bas till en annan, medan värdet på målfunktionen minskar. För ett visst antal iterationer övergår de till grunden för vilken det optimala (minsta eller maximala) värdet för målfunktionen erhålls. Låt oss överväga simplexmetoden i allmän form.

Den allmänna uppgiften för linjär programmering är att minimera (maximera) den objektiva funktionen, vars variabler är sammankopplade av ett system av linjära ekvationer, med förbehåll för icke-negativitetsvillkoret.

Låt det vara nödvändigt att minimera den linjära formen

L = c 1 x 1 + c 2 x 2 + ... c n x n.

Under följande förhållanden (för tydlighetens skull hålls noll- och enhetskoefficienter i ekvationerna):

1x 1+ 0x 2 + ... 0x m + a 1m+ 1x m+1 ... + a 1n x n \u003d b 1;

0x 1+ 1x 2+… 0x m + a 2m+ 1x m+1 ... + a 2n x n \u003d b 2;

……………………………………………

0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n \u003d b m.

Detta ekvationssystem har redan en färdig grund, eftersom varje restriktionsekvation innehåller en okänd med en koefficient lika med en, som inte finns i andra ekvationer, d.v.s. från variablernas koefficienter X 1 , X 2 …, x m du kan skapa en identitetsmatris.

Låt oss lösa ekvationerna för de grundläggande variablerna:

x 1 \u003d b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);

x 2 \u003d b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

………………………………

x m \u003d b m - (a mm + 1x m + 1 ... + a mn x n),

och vi kommer att uttrycka den objektiva funktionen i termer av fria variabler och ersätta deras uttryck i termer av fria variabler i stället för de grundläggande variablerna:

L=c 1 b 1 +c 2 b 2 + c m b m –(c 1 a 1m + c 2 a 2m+1 +...+c m a mn+1)x m+1 -...-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Variabler x 1, x 2 ..., x m, med vars hjälp den första grundplanen hittas, är grundläggande och resten x m +1 , x m +2 ,...x n – fri. Det ska alltid finnas lika många grundvariabler som det finns ekvationer i systemet. Baserat på icke-negativitetsvillkoret är det minsta värdet av fria variabler lika med noll. Den resulterande grundlösningen av ekvationssystemet är dess initiala genomförbara lösning, dvs. x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, xn = 0.

Denna lösning motsvarar värdet av den objektiva funktionen

L = c 1 b 1 + c 2 b 2 + ... c m b m.

Den initiala lösningen kontrolleras för optimalitet. Om det inte är optimalt, då genom att införa fria variabler i basen, hittas följande genomförbara lösningar med ett mindre värde på objektivfunktionen. För att göra detta bestäms en fri variabel som ska matas in i underlaget, samt en variabel som ska tas bort från underlaget. Sedan går de från det tidigare systemet till nästa motsvarande system. Detta görs med hjälp av simplextabeller. Lösningen av problemet fortsätter tills det optimala värdet av den objektiva funktionen erhålls.

Simplextabeller sammanställs enligt följande (se tabell 3.1). Placera alla variabler överst i tabellen X 1 , X 2 …, x n och koefficienter cj, med vilka motsvarande variabler ingår i objektivfunktionen. Första kolumnen c i består av objektivfunktionens koefficient för de variabler som ingår i underlaget. Detta följs av en kolumn med grundläggande variabler och fria termer av ekvationerna. Elementen i de återstående kolumnerna i tabellen är koefficienterna för de variabler med vilka de senare går in i ekvationssystemet. Således motsvarar varje rad i tabellen systemets ekvation, löst med avseende på grundvariabeln. Tabellen visar också en variant av planen som motsvarar målfunktionen för ett givet underlag.

Den nedre raden i tabellen kallas index. Vart och ett av dess element (uppskattning) ∆ j bestämma

∆j = z j – c j ,

Var cjär koefficienterna för motsvarande variabler i objektivfunktionen; zj – summan av produkterna av koefficienterna för målfunktionen med grundläggande variabler och motsvarande variabler - element j-th kolumn i tabellen.

Tabell 3.1

Enkel tabell med initial giltig

1.

2. bruksanvisning matta. modeller i ekonomin.

Matematiska modeller låter dig bestämma de optimala värdena för okända parametrar ekonomiska system vilket är viktigt i beslutsprocessen. Matematisk programmering ger bara en apparat som låter dig optimera urvalsprocessen de bästa alternativen planer i förvaltningsprocessen i ekonomiska system.

Används i matematisk statistik, optimeringsmetoder, ekonomiska metoder. cybernetik, experimentella problem.

När man studerar komplexa processer och fenomen i ekonomin används ofta modellering - en väldefinierad konkret visning av de övervägda egenskaperna hos det föremål som studeras. Dess väsen ligger i det faktum att fenomenet som studeras reproduceras under experimentella förhållanden med hjälp av en modell på en annan tidsmässig och rumslig skala. En modell är ett speciellt skapat föremål med hjälp av vilket ganska vissa egenskaper hos det studerade systemet reproduceras för att studera det. Matematisk modelleringär den mest perfekta och samtidigt effektiva metoden för att få information om föremålet som studeras. Det är ett kraftfullt verktyg för analys inom ekonomi. Resultaten av forskning med hjälp av modeller kommer att vara av praktiskt intresse när den konstruerade modellen är tillräckligt adekvat för fenomenet i fråga, dvs. tillräckligt bra för att spegla den verkliga situationen.

2. matematisk programmering som vetenskap, dess struktur. Optimeringsproblem. Svårigheter att tillämpa klassiska optimeringsmetoder för att lösa ekonomiska problem.

Matematisk programmeringär en gren av tillämpad matematik som utvecklas teoretisk grund och metoder för att lösa extrema problem.

Matematisk programmering innehåller ett antal avsnitt, varav de viktigaste är följande:

1. Linjär programmering. Detta avsnitt innehåller problem där okända variabler ingår i matematiska samband i första graden.

2. Icke-linjär programmering. Det här avsnittet innehåller problem där objektivfunktionen och (eller) begränsningarna kan vara icke-linjära.

3. Dynamisk programmering. Detta avsnitt innehåller uppgifter där lösningsprocessen kan delas upp i separata steg.

4. Heltalsprogrammering. Det här avsnittet innehåller uppgifter där okända variabler endast kan ta heltalsvärden.

5. Stokastisk programmering. Det här avsnittet innehåller uppgifter som innehåller slumpvariabler i målfunktionen eller begränsningar.

6. Parametrisk programmering. Detta avsnitt innehåller problem där koefficienterna för okända variabler i objektivfunktionen eller begränsningarna beror på vissa parametrar.

För att lösa matematiska programmeringsproblem är det svårt att använda klassiska metoder för att hitta ett extremum, eftersom objektivfunktionen i matematiska programmeringsproblem når sitt extremvärde vid gränsen av området för acceptabla värden av okända variabler, och derivator inte existerar vid gränspunkterna. En fullständig uppräkning av tillåtna poäng är omöjlig på grund av deras betydande antal.

3. Konceptet med en matematisk modell, typer av mattor. modeller

Matematisk modellär en abstraktion av ett verkligt fenomen eller en process skriven i matematiska symboler och uttryck. Matematiska modeller ekonomiska processer och fenomen kallas ekonomiska och matematiska modeller

Modellerna är indelade i:

1. linjär, där alla beroenden beskrivs av linjära relationer,

2. icke-linjär, där det finns olinjära relationer;

3. stokastisk, som tar hänsyn till den slumpmässiga karaktären hos de processer som studeras,

4. deterministisk, som tar hänsyn till medelvärdena för alla parametrar.

5. dynamisk modeller där de studerade systemen beaktas under utveckling under flera perioder,

6. statisk, där tidsfaktorn inte beaktas.

7. optimering modeller där valet görs beroende på extremisering något kriterium,

8. icke-optimering, där det inte finns något optimalitetskriterium.

9. makromodeller(för hela hushållet)

10. mikromodeller(individuella länkar eller processer i ekonomin).

Typer av matematiska modeller: linjära, olinjära, kvadratiska, heltal, diskreta, parametriska, linjära bråkdelar, dynamiska, stokastiska

4. Allmän problembeskrivning av matematisk programmering.

Betrakta det allmänna uttalandet om problemet med matematisk programmering.

Det allmänna problemet med matematisk programmering är att bestämma det optimala värdet för målfunktionen, och värdena för variablerna måste tillhöra ett visst intervall av tillåtna värden. Matematiskt uttrycks definitionen av den optimala lösningen i att hitta extremumet (max eller min) för en funktion av många variabler

Z = f(x1, x2, …, xn)

inom det givna förändringsintervallet för dessa variabler

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

där Ri är ett av tecknen ≥, =, ≤.

5. Problemet med att optimera produktionsplanen. Ekonomisk formulering och konstruktion av en matematisk problemmodell.

Ekonomisk miljö:

Företaget producerar n typer av produkter som använder m typer av råvaror. För produktion av en produktionsenhet används en strikt definierad mängd råvaror av ett eller annat slag. Råvarorna av varje typ i företaget är begränsade. Företaget får en viss vinst från försäljningen av en produktionsenhet. Det är nödvändigt att hitta en sådan produktionsplan där företaget kommer att få den maximala totala vinsten.

Matematisk inställning:

Låt j vara indexet för produkttypen j = 1, n

i - index för resurstyp i = 1, m

och ij är råvarukostnader i-th typen för produktion av en produktionsenhet j-th typen;

Аi är en given gräns för den tillgängliga volymen av resurser av den i-te typen;

Pj - vinst från försäljningen av en produktionsenhet av j-te typen;

xj är volymen av output av den j-te typen.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → max

a11x 1 + a12x 2 +…+ a1nx n ≤ A1

a21x 1 + a22x 2 +…+ a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +…+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Dietens uppgift. Ekonomisk formulering och konstruktion av en matematisk modell av problemet.

Ekonomisk miljö

Vissa gårdar matar djur. Används för gödning n typer av foder. Innehållet av näringsämnen (kalcium, fosfor etc.) är känt per foderenhet av varje art. För korrekt näring av djur är det nödvändigt att konsumera näringsämnen inte mindre än de angivna mängderna. Enhetskostnaden för varje foder är känd. Det är nödvändigt att bestämma dieten för djurfoder, där den totala kostnaden för gödning kommer att vara minimal.

Matematisk inställning:

j är indexet för fodertypen, j = 1, n

i – näringstypsindex, i = 1, m

Аi är det nödvändiga dagliga intaget av den i:te typen av näringsämne;

Сj är kostnaden för en foderenhet av j-te typen.

Låt oss introducera okända variabler:

хj - daglig volym av djurfoder j:te vy akter.

När det gäller den införda notationen given uppgift kommer att skrivas härnäst

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +…+ och mnxn ≥Am

xj ≥ 0, j = 1, n

7. Transportuppgift . Ekonomisk formulering och konstruktion av en matematisk modell av problemet.

Ekonomisk miljö :

Tillgängliga m leverantörer av homogena produkter och n konsumenter av denna produkt. Kända enhetskostnader för leverans av en produktionsenhet från varje leverantör till varje konsument. Leverantörslager är begränsade. Behoven av varje konsuments produkter är också kända.

Det är nödvändigt att fastställa en sådan plan för transport av produkter från leverantörer till konsumenter, där den totala kostnaden för transport kommer att vara minimal.

Matematisk inställning :

Låt oss presentera notationen ställa in parametrar:

j – konsumentindex, j = 1, n

i – leverantörsindex, i = 1, m

Аi är volymen av produkter som är tillgängliga från den i:e leverantören;

Bj - volymen av efterfrågan på den j:te konsumentens produkter;

Cij är enhetskostnaden för att transportera en produktenhet från den i:te leverantören till den j:te konsumenten.

Låt oss introducera okända variabler:

хij är volymen för transport av produkter från den i:te leverantören till den j:te konsumenten.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +...+ Сm(n -1)xm (n-1) + Сmnxmn → min

Uppgiftsbegränsningar.

I. Från varje leverantör kan du inte ta ut mer produkter än den tillgängliga kvantiteten:

x11 + x12 +…+ xln ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Varje konsuments behov av produkter måste tillgodoses

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Icke-negativitetstillstånd: xij ≥0, i = 1, m ; j = 1, n

Det är ofta bekvämt att skriva det matematiska påståendet i en vikt form:

, i = 1, m , j = 1, n

8. Problemet med att välja uppdrag eller uppdrag. Ekonomisk formulering och konstruktion av en matematisk modell av problemet.

Ekonomisk miljö :

Tillgängliga n typer av arbete och n artister. Var och en av artisterna kan utföra vilket jobb som helst, men bara ett jobb. Kostnaden för att utföra varje verk av varje utförare fastställs. Det är nödvändigt att tilldela utförare att arbeta på ett sådant sätt att den totala kostnaden för att slutföra arbetet är minimal.

Matematisk inställning .

Låt oss introducera notationen för de givna parametrarna.

i – index över verk, i = 1, m

j är indexet för utförare, j = 1, n

Cij är kostnaden för att utföra det i:te jobbet av den j:te utföraren.

Låt oss introducera okända variabler. I detta problem kan okända variabler bara ta två värden, 0 eller 1. Sådana variabler kallas nollvariabler.

1 - om den j:te artisten tilldelas det i:te jobbet;

0 - annars.

När det gäller den introducerade notationen kan detta problem skrivas på följande sätt:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → min

I grupp av restriktioner.

Endast en artist bör tilldelas varje verk:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. restriktionsgrupp.

Varje utförare kan endast utföra ett jobb:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ij = (0,1) i = 1, n; j = 1, n

9. Problemet med att skära material. Ekonomisk formulering och konstruktion av en matematisk modell av problemet.

Ekonomisk miljö .

Råvaran av samma storlek levereras för skärning. Det krävs att det skärs till ämnen av en given storlek i en given mängd, så att det totala avfallet blir minimalt.

Matematisk inställning .

Låt oss presentera notationen:

i är indexet för tomma ämnen,

Аi - det erforderliga antalet ämnen av den i-te typen;

j - index över skäralternativ,

Cj är storleken på avfallet vid skärning av en enhet av ursprungsmaterial enligt alternativ j;

och ij är antalet ämnen av den i:te typen vid skärning av en enhet av initialt material enligt alternativ j.

Låt oss introducera notationen för okända variabler.

xj är mängden råmaterial som kapats enligt alternativ j.

När det gäller den introducerade notationen kan detta problem skrivas på följande sätt:

z \u003d С1x1 + С2x2 + ... + Сnxn → min

a11x1 + a12x2 +…+ a1nxn = A1

a21x1 + a22x2 +…+ a2nxn = A2

…………………………….

am1x1 + am2x2 +…+ amnxn =Am

xj ≥ 0, j = 1, n

Användningen av matematiska modeller gör att du kan spara upp till 20% av råvarorna.

Den matematiska modellen för skärning är uppbyggd i två steg.

I det första steget konstrueras skäralternativen, som ett resultat av vilket värdena för antalet alternativ n, antalet ämnen av varje typ som erhållits med olika skäralternativ (aij), såväl som värdena avfall (Cj) bestäms.

Konstruktionen av alternativ för att skära en enhet av källmaterial utförs i form av följande tabell:

alternativnummer

Tom i1

i2 tom

tomt im

Ämnena är ordnade i icke-ökande ordning efter sina storlekar. Konstruktionen av varianter utförs med metoden för fullständig uppräkning.

10. Allmän form av LP-problemmodellen och dess egenskaper

Den allmänna formen för LLP är:

z \u003d С1x1 + ... + Сnxn max (min)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

I allmän form betyder varje symbol R1 , R2 ,..., Rm ett av tecknen: ≥, = eller ≤ .

Den allmänna formen av LP-problemmodellen har följande egenskaper.

1. Systemet av begränsningar presenteras i form av ekvationer (rigida förhållanden) och ojämlikheter (icke-rigida förhållanden).

2. Icke-negativitetsvillkor ställs inte på alla variabler

3. Den objektiva funktionen tenderar antingen till maximalt eller till minimum.

11. Standardform för LP-problemmodellen och dess egenskaper

Standardformuläret är som följer.

Hitta maximum eller minimum för målfunktionen z:

z = С1x1 + … + Сnxn → max (min) (1)

Med förbehåll för följande begränsningar:

a11 X1 + a12 X2 + … + aln Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ am

xj ≥ 0, j = 1, k, k ≤ n

Funktionerna i standardformen för LP-problemmodellen är följande:

1. begränsningssystemet presenteras i form av ojämlikheter (icke stela villkor)

2. icke-negativitetsvillkor ställs på alla variabler

3. objektivfunktionen tenderar att antingen max eller min

12. Kanonisk form av LP-problemmodellen och dess egenskaper

Den kanoniska formen är:

Hitta minimum av målfunktionen z:

z = С1x1 + … + Сnxn → min

Med förbehåll för följande begränsningar:

a11 X1 + a12 X2 + ... + aln Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

Funktionerna i den kanoniska formen är följande:

1. Systemet med begränsningar presenteras i form av ekvationer (stränga villkor).

2. Icke-negativitetsvillkor gäller för alla variabler

3. Den objektiva funktionen tenderar att

I vissa källor tenderar LP-problemets objektiva funktion, presenterad i kanonisk form, till ett maximum. Detta görs för att underlätta att lösa problemet enligt den algoritm som utvecklats för den maximala objektivfunktionen.

13. Möjlig, tillåten, optimal grunduppgiftsplan, ODZ för LP-uppgiften

Definition 1. Värden för okända variabler som uppfyller alla begränsningar för ett linjärt programmeringsproblem kallas tillåtlig variabelvärden eller planer .

Definition 2. Uppsättningen av alla planer för ett linjärt programmeringsproblem kallas domänen av tillåtna värden av variabler ( ODZ ).

Definition 3. Planen för det linjära programmeringsproblemet, där objektivfunktionen tar det lägsta (eller maximala) värdet på ODZ kallas optimal .

14. Typer av register över LP-uppgifter: expanderad, vikt, matris, vektor.

LP-problemmodeller kan skrivas i olika former.

1. Utökad vy av modellregistret

Z = cl X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Komprimerad vy:

,

Xj ≥ 0, j = 1, n.

3. Modell av LP-problemet i matrisform:

X ≥ 0

Var

a11 a12 … a1n X1 a1

A= a21 a22 … a2n, X= X2, A0 = a2

… … … … … …

amn 1 am2 … amn X3 am

4. Modell av LP-problemet i vektorform:

Var

X1 a11 a12 a1n a1

X2, a21, a22, a2n, a2

… … … … …

Хn am 1 am2 am2 am

15. Övergång från den vanliga och allmänna formen av LP-problem till den kanoniska. Kopplingssats

För att gå från en allmän eller standardform till en kanonisk, används följande tekniker.

1. Variabel konvertering. Om någon variabel Xk är icke-positiv (Xk ≤ 0), så introduceras en ny variabel Xk ", så att Xk " = –Xk . Uppenbarligen är Xk " ≥ 0. Därefter, i varje begränsnings- och objektivfunktion, ersätts variabeln Xk med [ – Xk "].

Om någon variabel Xt kan ta vilka värden som helst, så ersätts den av skillnaden mellan två icke-negativa variabler Xt' och Xt'', dvs. det antas att xt = Xt' – Xt'', där Xt' 0 ≥ och Xt'' ≥ 0.

2. Begränsningstransformation. Om någon av begränsningarna i modellen har formen av en olikhet, så omvandlas den till likhet genom att addera (om olikheten är av typen ≤) eller subtrahera (om olikheten är av typen ≥) från dess vänstra sida. Dessa variabler kallas balansvariabler. Balansvariabler ingår i målfunktionen med nollkoefficienter. Balansvariabeln tar indexvärdet sekventiellt efter de redan befintliga. Om till exempel systemet med begränsningar har 5 variabler, kommer den första balansvariabeln att vara X6, och den andra - X7, etc.

16. Övergång från den kanoniska formen av ZLP-modellen till standarden

Att gå från den kanoniska formen till standardformen, var och en av

ekvationer som ska ersättas av ett system av ojämlikheter:

Ett annat sätt är att föra ekvationssystemet till en speciell form och ytterligare eliminera vissa variabler.

Med Jordan-Gauss-metoden väljer vi grundvariabeln i varje ekvation. Sådant urval utförs med hjälp av ekvivalenta (elementära) Gausstransformationer. Dessa inkluderar:

a) multiplikation av valfri ekvation med en annan konstant än noll;

b) tillägg till valfri ekvation av någon annan ekvation, multiplicerat med en konstant.

Det är bekvämt att skriva det initiala systemet med linjära ekvationer före transformationen i form av en matris eller tabell:

Vi skriver problemet i standardform.

17. Konceptet med ett hyperplan av ett halvplan, ett stödjande hyperplan.

18. Geometrisk. tolkning av begränsningssystemet och den objektiva funktionen i LP-problem

19. Konvex uppsättning: extrema (hörn)punkter på uppsättningen. Konvex polyeder

Definition En mängd M kallas konvex om, tillsammans med två punkter som hör till given uppsättning, den innehåller också ett segment som förbinder dem.

konvex uppsättning

Definition En punkt x i en mängd M kallas en hörn- eller extrempunkt om den inte är intern i något segment som helt och hållet tillhör den givna mängden.

Sats 1. Vilken punkt som helst i ett segment kan representeras som en konvex kombination av dess hörnpunkter.

x \u003d λ 1 A + λ 2 B

λ 1 , λ 2 ≥ 0 konvex kombination av punkter i hörnpunkterna A och B

λ1 + λ2 = 1

Sats 2. Vilken punkt som helst i en konvex sluten uppsättning kan representeras som en konvex kombination av dess hörnpunkter.

20. Algoritm för den grafiska metoden för att lösa LP-problem

1. Det kontrolleras om den ursprungliga LPP finns i standardformuläret, om inte så måste uppgiften konverteras till standardformuläret.

2. Antalet okända variabler kontrolleras. Om detta antal är mer än tre, kan problemet inte lösas med en grafisk metod (det finns andra effektiva metoder för att lösa sådana problem).

3. Området med tillåtna värden för variabler för ZLP är under uppbyggnad.

4. En guidevektor byggs c .

5. Den initiala isocellen dras genom ODZ (vinkelrätt mot riktningsvektorn).

6. Den initiala isocoelens mentala rörelse i vektorns riktning utförs c, om maximivärdet för objektivfunktionen bestäms, eller i motsatt riktning, om dess minimivärde bestäms, tills isomålet blir en referens till ODZ. Skärningspunkterna för referensisocoel och ODZ kommer att vara de optimala punkterna för problemet.

7. För att bestämma koordinaterna för den optimala punkten är det nödvändigt att lösa systemet med motsvarande linjära ekvationer.

8. För att hitta det optimala värdet för målfunktionen är det nödvändigt att ersätta de optimala värdena för variablerna i målfunktionen och beräkna dess värde.

20. grafisk algoritm. LP problemlösningsmetod

Algoritm för den grafiska metoden.

1. Genom successiv konstruktion av var och en av villkoren för systemet med begränsningar av problemet, utförs konstruktionen av ODZ.

2. Riktvektorn C konstrueras av koefficienterna för variablerna för objektivfunktionen.

3. Den initiala isocoelen ritas vinkelrätt mot riktningsvektorn genom origo.

4. Det initiala isomålet flyttas mentalt i riktning mot ökande värden för vektorn C, om maximivärdet för objektivfunktionen bestäms, eller i motsatt riktning, om dess minimivärde bestäms, tills isogoalen blir en hänvisning till ODZ. Skärningspunkterna för referensisocoel och ODZ kommer att vara de optimala punkterna för problemet.

5. För att bestämma koordinaterna för den optimala punkten är det nödvändigt att lösa systemet med motsvarande linjära ekvationer för de förhållanden i skärningspunkten där den optimala punkten är belägen.

6. För att hitta det optimala värdet för objektivfunktionen är det nödvändigt att ersätta koordinaterna för den optimala punkten i målfunktionen och beräkna dess värde.

23. satser om intervallet av tillåtna värden för LP-problemet och om objektivfunktionen

ODZ-satsen. Domänen för tillåtna lösningar av LP-problemet är en konvex uppsättning (sluten och avgränsad i n-dimensionell rymd)

Sats 2. Om objektivfunktionen hos ett linjärt programmeringsproblem.

LLP-objektivfunktionen tar sitt optimala värde vid en av hörnpunkterna i regionen med acceptabla värden för variabler. Om objektivfunktionen tar sitt optimala värde vid flera hörnpunkter, så tar den samma värde vid vilken punkt som helst som är en konvex kombination av dessa hörnpunkter.

24. Satsen om hörnpunkten. Tillräckligt och nödvändigt tillstånd

25. Följder från satsen om egenskaperna hos lösningar på LP-problem och slutsatser. Konceptet med en baslinje.

Konsekvenser från satser.

Definition. Planen = (х1,х2,...,хn), vars positiva koordinater motsvarar linjärt oberoende vektorer, kallas grundplan PLP .

Konsekvens 1. Referensplanen har högst m positiva koordinater.

Om den har exakt m positiva koordinater, kallas en sådan stöddesign icke-degenererad, annars degenererad.

Konsekvens 2. Varje hörnpunkt ODZ är grundplanen.

27. Algoritm för simplexmetoden.

När du löser LP-problem med simplexmetoden är det nödvändigt att utföra följande sekvens av åtgärder.

1. Det kontrolleras om LP-problemet är i kanonisk form. Om inte, är det nödvändigt att konvertera den ursprungliga modellen till en kanonisk form.

2. Den ursprungliga referensplanen och värdet av målfunktionen väljs för denna referensplan.

3. Den initiala simplextabellen är konstruerad.

4. Värdena för optimalitetsuppskattningarna i indexraden kontrolleras. Om det inte finns några positiva uppskattningar skrivs den optimala lösningen ut och algoritmen avslutar sitt arbete. I annat fall är punkt 5 uppfylld.

5. I underlaget införs en vektor, som motsvarar den största positiva skattningen. Denna kolumn kallas aktiveringskolumnen.

6. En vektor härleds från basen, som motsvarar det simplexförhållande som beräknas med formeln 0< Ө ≤ . Given linje kallas aktiveringssträngen.

7. Ett nytt simplexbord byggs. Kolumnerna B och C B ändras i enlighet med detta. Resten av tabellen är fylld från den föregående med Gauss-transformationer, där indexraden anses vara m+1-rader och även transformerad med Gauss-transformationer. Vi fortsätter till implementeringen av punkt 4 i denna algoritm.

Efter att ha byggt varje tabell kan du kontrollera beräkningarnas korrekthet med hjälp av formlerna för beräkning av uppskattningarna i föregående stycke.

28. Val av underlag och konstruktion av en initial referensplan för att lösa problem med simplexmetoden.

29. Simplexbord, deras fyllning. Formler för beräkning av indexradskoefficienter.

30 . Optimitetssatsen för planen för ett linjärt programmeringsproblem är en konsekvens av optimalitetsuppskattningssatsen för att lösa problem med simplexmetoden.

Sats 1: Om för någon vektor  j i systemet

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2

…………………………………………………..

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

Relationen Z j – c j > 0 är uppfylld, då är planen X B0 inte optimal och det är möjligt att gå över till planen X B1 så att Z (X B1) ≤ Z (X B0).

Här är Z j = (С, Ā j) skalärprodukten av vektorer.

C är en vektor som består av koefficienter vid de grundläggande variablerna för objektivfunktionen Z

Ā j är en vektor som består av expansionskoefficienterna för motsvarande vektor i termer av basvektorer.

c j är koefficienten för objektivfunktionen Z med variabel X j

Följd från satser: Om för alla vektorer Ā 1 , Ā 2 , …, Ā n av någon referensplan Х relationen Z j – c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Således tillåter satsen och följden oss att fastställa om nästa stödplan är optimal och om inte, är det nödvändigt att byta till en annan stödplan, där värdet av den objektiva funktionen kommer att vara mindre.

Kommentar. Satsen och följden antar att problemet är i kanonisk form med en minsta objektiv funktion. Simplexmetoden kan dock även användas för att lösa problem med maximal objektiv funktion. I det här fallet, när man analyserar värdena för uppskattningarna, används deras motsatta betydelse, det vill säga planen kommer att vara optimal om alla optimalitetsuppskattningar är icke-negativa (positiva eller negativa).

31. Val av en vektor som kommer in i basen och härleder från basen. Enkelt förhållande.

För att byta till en ny referensplan behövs en av de fria vektorerna gå in i basen och mata ut några av basvektorerna. För att införa i basen väljer vi en vektor som har minst en positiv koordinat. Låt vektorn A m+1 vara en sådan vektor.

nedbrytning -

Resp. vektor, katt. kommer att vara en referensplan om dess koordinater är icke-negativa, och antalet positiva koordinater kommer att vara lika med m.

X1-vektorkoordinaterna måste vara icke-negativa, dvs. .

Om , då kommer denna koordinat att vara icke-negativ.

Låt minimum i relation (5) erhållas vid i =1, då om vi tar

sedan den första koordinaten för vektorn 1 X blir noll.

Relation (6) kallas simplex relation. Således har vi flyttat från den ursprungliga baslinjen 0 X(grundvektorerna A1, A2, ... Am) till referensplanen 1 X(grundläggande vektorer A2, A3,…,Am, Am+1).

32. tillåtande element i tabellen, dess val. Fullständig Jordan-elimineringsregel för omräkning av simplextabeller.

33. Fyrsidig regel för omräkning av simplextabeller

34. Ett tecken på det unika med den optimala planen, uppsättningen av optimala planer och frånvaron av en optimal plan när man löser LP-problemet med simplexmetoden.

När du löser problem med simplexmetoden är följande typer av optimala lösningar möjliga:

1. Unikhet . Om uppskattningarna av alla fria vektorer är strikt negativa, är den erhållna stöddesignen optimal och unik. (se exemplet i föregående stycke).

2. Alternativ optimum (uppsättning av optimala lösningar).

Om det bland de icke-positiva uppskattningarna av fria vektorer finns minst en nolluppskattning, kommer den erhållna stöddesignen att vara optimal, men inte den enda. I det här fallet kan du gå till andra stödplaner (vektorer som motsvarar nolluppskattningar införs i basen) och sedan skriva den allmänna optimala lösningen som en konvex kombination av de erhållna optimala stödplanerna.

3. LLP har inte en optimal lösning, eftersom den objektiva funktionen inte är avgränsad underifrån . Om simplextabellen har en positiv poäng, och alla element given kolumnär negativa och noll, då given vektor kan ingå i underlaget. Ingen av basvektorerna kan dock härledas från basen. Av detta följer att en ytterligare minskning av målfunktionen är möjlig vid byte till en icke-stödjande plan.

4. LLP har inte en optimal lösning, eftersom systemet med begränsningar är inkonsekvent. Eftersom när man löser LLP bör den vanliga simplexmetoden vara den initiala referensplanen, är systemet med linjära ekvationer verkligen inte inkonsekvent. Därför kan ett sådant fall inte inträffa när man löser med den vanliga simplexmetoden.

5. Om ODZ består av en punkt, är lösningen av ett sådant problem trivial och kan erhållas utan att använda simplexmetoden.

35. När används den artificiella basmetoden?

artificiell.

36. Konstruktion av M-problemet i den artificiella basmetoden

Om det linjära programmeringsproblemet är i kanonisk form, innehåller dock inte alla ekvationer grundläggande variabler, det vill säga det finns ingen ursprunglig baslinje. I det här fallet, i de ekvationer där det inte finns några grundläggande variabler, är det nödvändigt att lägga till någon icke-negativ variabel med koefficienten +1. En sådan variabel kallas artificiell.

En artificiell variabel måste läggas till objektivfunktionen med ett mycket stort positivt tal (eftersom objektivfunktionen är att hitta minimum). Detta nummer anges latinsk bokstav M. Det kan anses lika med +∞. I detta avseende kallas ibland den artificiella basmetoden M-metoden. En sådan omvandling av det ursprungliga problemet kallas konstruktionen av det utökade problemet. Om du löser ett problem med en objektiv funktion för att hitta en artificiell variabel måste du addera till objektivfunktionen med ett mycket stort positivt tal (eftersom objektivfunktionen är att hitta minimum). Denna siffra betecknas med den latinska bokstaven M. Den kan anses vara lika med +∞. I detta avseende kallas ibland den artificiella basmetoden M-metoden. En sådan omvandling av det ursprungliga problemet kallas konstruktionen av det utökade problemet. Om ett problem löses med en objektiv funktion för att hitta maximum, kommer artificiella variabler in i objektivfunktionen med en koefficient -M.

I det utökade problemet har vi alltså en baslinje (även om vissa av basvariablerna är artificiella).

Den initiala simplextabellen är konstruerad.

37. bygga en indexlinje i den artificiella basmetoden

En initial simplextabell byggs upp, där indexraden är uppdelad i två rader, eftersom uppskattningarna består av två termer. Den översta raden innehåller termen för skattningen utan M, den nedersta raden visar koefficienterna vid M. Uppskattningens tecken bestäms av tecknet för koefficienten vid M, oavsett värdet och tecknet för termen utan M, eftersom M är ett mycket stort positivt tal.

Således, för att bestämma vektorn som introduceras i basen, är det nödvändigt att analysera den nedre indexlinjen. Om en artificiell vektor härleds från basen, kan motsvarande kolumn i efterföljande simplextabeller utelämnas om det inte finns något behov av att få en lösning på det dubbla problemet (se nästa ämne).

Efter att alla artificiella vektorer har tagits ur basen kommer den nedersta raden att ha alla nollelement, förutom de skattningar som motsvarar artificiella vektorer. De kommer att vara lika med -1. En sådan linje kan tas bort från övervägande och den ytterligare lösningen kan utföras med den vanliga simplexmetoden, om det inte finns något behov av att få en lösning på det dubbla problemet (se nästa ämne).

38. Optimalitetskriterium i den konstgjorda basmetoden. Skylten är konstruktionen av den ursprungliga grundplanen för den ursprungliga uppgiften.

39. Algoritm för dubbelsimplexmetoden

Algoritm för dubbelsimplexmetoden:

1. fyll i den första simplextabellen på vanligt sätt, oavsett tecken på lediga medlemmar. Man tror att ett sådant problem bör ha en initial enhetsbas.

2. Välj riktlinjen vid det största absoluta negativa elementet i kolumnen med fria medlemmar A0

3. Styrkolumnen väljs enligt det minsta absoluta värdet av förhållandet mellan elementen i indexlinjen och de negativa elementen i riktlinjen.

4. Beräkna om simplextabellen enligt regeln om fullständiga Jordan-eliminationer

5. kontrollera den mottagna planen för tillåtlighet. Ett tecken på att få en acceptabel referensplan är frånvaron av negativa element i kolumn A0. Om det finns negativa element i kolumn A0, gå till andra stycket. Om det inte finns några fortsätter de att lösa problemet på vanligt sätt.

6. Ett tecken på att erhålla en optimal lösning med dubbelsimplexmetoden är optimalitetskriteriet för den vanliga simplexmetoden.

41. Öppna och stängda transportmodeller. Övergång från en öppen transportmodell till en stängd.

Typer av transportuppgifter.

Tillgängliga m leverantörer av homogena produkter med kända lager av produkter och n konsumenter av dessa produkter med givna behovsvolymer. Enhetskostnaderna för transport är också kända.

Om summan av volymerna av produktlager är lika med volymen av behov hos alla konsumenter, kallas ett sådant problem sluten transportuppgift

(dvs om ∑ Ai = ∑ Bj), annars kallas transportproblemet öppen. För att lösa transportproblemet är det nödvändigt att det stängs.

En öppen transportuppgift kan konverteras till en stängd på följande sätt.

Låt ∑Ai > ∑Bj. I det här fallet är det nödvändigt att införa en fiktiv n + 1 konsument med en behovsvolym ∑Ai – ∑Bj. Enhetskostnader för transport från leverantörer till en fiktiv konsument antas vara 0, eftersom sådan transport i själva verket inte kommer att vara 0. genomförs och en del av produkterna kommer att finnas kvar hos leverantörer.

Om ∑Bj > ∑Ai . I detta fall är det nödvändigt att införa en fiktiv m + 1 leverantör med lagervolym ∑Bj – ∑Ai . Enhetskostnaderna för transport från en fiktiv leverantör till konsumenter antas vara lika med 0, eftersom sådan transport i själva verket inte kommer att utföras och konsumenterna inte kommer att få en del av produkterna.

42. Metoder för att konstruera den initiala fördelningen i transportproblemet: metoden för det nordvästra hörnet och metoden för det minsta elementet i matrisen.

Northwestern-teknik för att konstruera en referensplan. Enligt denna teknik börjar bildandet av trafikvärden med s.-z. bordshörna, d.v.s. från cell x11. Enligt denna metod distribueras först och främst varorna från den första leverantören. Dessutom tillfredsställer den första leverantören först den första konsumenten så mycket som möjligt. Sedan, om leverantören fortfarande har varorna,

Metoden för det minsta elementet i matrisen.

Kärnan i metoden ligger i det faktum att det maximala möjliga utbudet alltid sätts i cellen, vilket motsvarar matrisens lägsta tariff.

Först gör vi märken (till exempel med tecknet ▼) i de celler i linjerna där det lägsta priset för linjen observeras. Sedan går vi runt tabellen kolumnvis och gör samma anteckningar i cellerna där det lägsta priset är kolumnvis.

Ytterligare fördelning görs först så långt som möjligt över celler med två märken, sedan - med ett, och sedan balanseras problemet om till (m + n - 1) fyllningar. Vi organiserar fyllningar när vi passerar bordet från vänster till höger och uppifrån och ned.

43. Transportuppgifters egenskaper

Transportproblemet har några egenskaper som kan återspeglas i följande satser.

Sats 1. Ett slutet transportproblem har alltid en lösning.

Sats 2. Om volymen av lager av produkter och volymen av behov är heltal, så kommer lösningen av transportproblemet också att vara heltal.

Sats 3. systemet av begränsningar för ett slutet transportproblem är alltid linjärt beroende.

Av denna sats följer att fördelningen av ett slutet transportproblem alltid har m + n – 1 basvariabler och (m – 1) (n – 1) fritidsvariabler.

44. Degenererad distribution i transportproblem, att bli av med degeneration. Överstruken kombination.

Fördelningen kallas degenererad om antalet celler är mindre än m + n - 1.

45. Optimalitetssatser för transportproblemet.

Sats. Om för någon fördelning av transportuppgiften du

villkoren är uppfyllda:

A). ui+vj = cij för upptagna celler

b) ui+vj ≤ сij, för fria celler,

då är denna fördelning optimal.

Värdena ui kallas radpotentialer, och värdena vj kallas kolumnpotentialer.

46. ​​Potentialer och metoder för deras beräkning.

För att hitta potentialerna för rader och kolumner används följande resonemang, baserat på villkor a) i optimalitetssatsen.

Antalet ekvationer baserade på detta villkor är m + n – 1, och antalet okända ui och vj är m + n. Den där. antalet variabler är större än antalet ekvationer, och alla ekvationer är linjärt oberoende. Lösningen av ett sådant system av linjära ekvationer är obestämd, så en av potentialerna måste tilldelas vilket värde som helst. I praktiken är ui = 0. ett system av m + n – 1 ekvationer med m + n – 1 okända variabler erhålls. Detta system kan lösas med vilken metod som helst. I praktiken, för att beräkna potentialer, övervägs ockuperade celler, för vilka en av deras potentialer är känd, och baserat på villkor a) i satsen beräknas värdena för de återstående okända potentialerna.

47. Beräkning av uppskattningar av optimaliteten i fördelningen av transportuppgifter och kriteriet för optimalitet.

Baserat på relation b) i satsen kan vi skriva följande formel för att beräkna skattningar: δ I j= ui + vj – сij. För att inte förväxla uppskattningar med trafikvolymer är de (uppskattningar) omgivna i cirklar.

Optimalitetsuppskattningar i fria TK-celler är ett optimalitetskriterium som kontrollerar fördelningen för optimalitet. Om uppskattningarna av alla fria celler är mindre än eller lika med noll, är denna fördelning optimal.

48. omfördelning av leveranser i transportproblemet

Om distributionen inte är optimal är det nödvändigt att omfördela leveranser.

För omfördelning byggs en omräkningscykel. Cellen med högst positiv poäng väljs som cell. Denna cell är markerad med ett "+"-tecken, det vill säga det är nödvändigt att registrera en viss mängd leverans i den. Men då kommer balansen i denna kolumn att störas, därför måste en av de ockuperade cellerna i denna kolumn markeras med ett "-"-tecken, det vill säga leveransvolymen ska minskas med samma mängd. Men då kommer balansen för denna linje att ändras, därför måste någon upptagen cell på denna linje markeras med ett "+"-tecken. Denna process fortsätter tills "-"-tecknet placeras på raden där den ursprungliga cellen fanns.

För varje fri cell finns en omräkningscykel och dessutom den enda.

49. omfördelningskedjor, deras typer.

Låt den aktuella transportplanen inte vara optimal, dvs. det finns positiva relativa uppskattningar. Sedan tas en ogynnsam cell (en av de ogynnsamma) och en omräkningscykel byggs för den, enligt vilken den planerade transporten sedan omfördelas. Cykeln är uppbyggd i form av en bruten sluten linje, vars segment löper antingen längs kolonnen eller längs linjen. I ett av hörnen av den brutna linjen finns en ogynnsam cell som gör anspråk på produkten, och i de andra hörnen fylls cellerna, d.v.s. när vi konstruerar en cykel utgår vi från kandidatcellen och återvänder till den längs en streckad linje, men vi kan bara göra svängar i fyllda celler (motsvarande grundvariablerna). Låt en ogynnsam cell göra anspråk på produkt Q. För att förhindra en obalans i tabellen är det nödvändigt att

lägga till och subtrahera Q till den tillgängliga trafiken. Eftersom det finns ett jämnt antal hörn kommer Q att läggas till i hälften av cellerna och subtraheras i den andra hälften. Cykeln startas medurs eller moturs från kandidatcellen, placerar bra Q där, sedan subtraheras Q från angränsande cell, adderas sedan, och så vidare. Värdet på själva Q väljs så att en av cellerna töms, men ingen av förråden skulle bli negativ.

För att göra detta måste Q väljas lika med den minsta reducerbara av cellerna i vilka Q subtraheras. I följande fig. 7.1 och 7.2 kommer vi att visa exempel på cykler och beräkningsregeln.

I detta fall töms två celler. Men det är nödvändigt att bara en cell blir ömsesidigt tom. De gör så här: en av tömningscellerna görs tom i den nya tabellen och noll sätts i den andra tömningscellen. Denna cell anses vara grundläggande (fylld) i den nya tabellen.

50. Valet av omfördelningsvolym.

Bestämning av volymen av transporterade produkter. När vi bestämmer volymen av produkter som flyttas genom räknecykeln måste vi utgå från följande två överväganden:

a) efter transformation i cellerna i tabellen bör negativa tal inte erhållas;

b) en av de ockuperade cellerna måste bli ledig.

För att dessa villkor ska uppfyllas är det nödvändigt att välja volymen av transporterade produkter enligt följande: θ=min (хij) -, där (хij) är transportvolymen från cellerna i omräkningscykeln markerade med " -" skylt.

6 = min(20;30)=20

θ läggs till värdena för celler markerade med ett "+"-tecken. θ subtraheras från värdena för celler markerade med ett "-"-tecken. Leveransvärdet för de återstående cellerna skrivs över utan ändringar. Som ett resultat får vi följande tabell.

53. Algoritm för metoden för potentialer.

Algoritm:

1. Kontrollera om ekvationen är uppfylld för uppgiften om inte, introduceras en fiktiv leverantör eller konsument i uppgiften

2. Uppgiftsvillkoret skrivs i form av en transport.tabell

3. En första baslinje håller på att byggas

4. Potentialen för leveranser och konsumenter bestäms

5. Poäng för fria celler beräknas. Om alla inte är negativa är planen optimal och du måste skriva ut svaret. Transportmatrisen X och bestäm mängden transportkostnader. Om planen inte är optimal, det vill säga bland uppskattningarna finns negativa, välj sedan en lovande cell med det största negativa värdet. uppskatta och övergå i storlek till nästa.

6. Ladda en perspektivcell. Förbered en ny grundplan i form av ett transportbord. Gå till punkt 4.

54. Redovisning av kostnaden för produktion och transport av produkter. Transportuppgift med leveransförbud.

När man löser vissa problem är det nödvändigt att ta hänsyn till kostnaderna inte bara för transport av varor utan också för produktion av transporterade produkter. För att göra detta, i matrisen transp. uppgifter

Där Cij ' är den reducerade kostnaden för att producera en produktionsenhet.

Cij “- kostnaden för att transportera en produktionsenhet.

Uppgifter med försörjningsförbud.

I vissa situationer är det inte möjligt att transportera produkter på någon rutt.

För att göra detta, i matrisen för transportuppgiften, genom vilken transporten är förbjuden, skrivs en förbjuden taxa M. Vidare löses uppgiften på vanligt sätt. Denna cell kommer dock alltid att motsvara en negativ cellpoäng.

55. ta hänsyn till begränsningarna för rutters genomströmning, med hänsyn till att vissa leveranser är obligatoriska i transportproblemet.

begränsningar av rutters genomströmning.

I vissa transportuppgifter, på vissa sträckor, en mindre genomströmningän vad som är nödvändigt för att tillgodose efterfrågan från konsumtionsstället.

med hänsyn till vissa leveransers obligatoriska karaktär i transportproblemet.

I vissa fall kräver uppgiften att till exempel längs sträckan Ak Bs ska leverans i volym A-enheter utföras. I detta fall dras den obligatoriska leveransen av från produktionsvolymen för punkt A och volymen S Bs och problemet löses med avseende på den valfria leveransen. Efter att ha erhållit den optimala lösningen läggs tillförseln nödvändigtvis till den volym som står i Ak Bs-cellen.

56. Möjliga slutsatser med ekonomiska. tolkning av den optimala fördelningen för öppna transportproblem.

Vid mottagandet av den optimala distributionen är det nödvändigt att återgå till det ursprungliga problemet och göra lämpligt ekonomiskt. Slutsatser. De är följande:

1. Om en konsumtionspunkt införs innebär detta att det finns alltför stora produktionsvolymer i det analyserade systemet, och det är möjligt, utan att det påverkar det aktuella systemet, att minska kapaciteten för dessa produktionsställen med mängden bindning som är knutna till den fiktiva konsumtionspunkten.

2. Om en fiktiv produktionspunkt införs, betyder det att kapaciteten hos verkliga produktionspunkter inte räcker till och att de måste ökas. Kapaciteten för de produktionspunkter som ligger närmast de konsumtionspunkter som är knutna till den fiktiva produktionspunkten ökar. Tillverkarens kapacitet ökas med bindningsvärdet. För att göra detta, överväg kolumnen för konsumtionspunkten, som är knuten till den fiktiva produktionspunkten, och hitta den lägsta tariffen i den. Det är mest effektivt att öka kapaciteten på produktionspunkten som motsvarar denna tariff med bindningsbeloppet.

57. Dualitetsbegreppet. Ekonomisk formulering av dubbla problem på exemplet med problemet med att optimera produktionsplanen.

Det dubbla problemet är ett hjälpproblem med linjär programmering formulerat med hjälp av vissa regler direkt från villkoren för det ursprungliga, eller direkta problemet.

Låt det finnas en uppgift att optimera produktionsplanen. Det ser ut så här:

Inledande uppgift:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | vid 2

……………….. |.. (1)

A T 1 x 1 +a T 2 x 2 + ... + a T n x n ≤v 1 | på T

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +...+c n x n ->max(3)

X \u003d (x 1, x 2, ..., x n)

a ij - antalet råvaror av den i:e typen som används för produktion av den j:te typen av produkt

Dubbla problem

Låt företaget av någon anledning inte kunna producera produkter. För att minska kostnaderna för stillestånd kan företaget sälja de råvaror som det har. Till vilket pris ska råvaror säljas?

i - priset på den i:te typen av råmaterial som finns tillgänglig på företaget.

a 11 y 1 + a 21 y 2 + ... + a T 1 år T≥s 1

a 12 x 1 + a 22 y 2 + ... + a T 2 x n ≥s 2

……………….. (1’)

A 1 sid y 1 +a 2p y 2 +…+ a tp på T≥s P

i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +...+b m y m ->min(3’)

58. Överensstämmelse mellan de strukturella delarna av de direkta och dubbla problemen

Varje linjär programmeringsproblem kan associeras

dubbel uppgift enligt följande regler:

1. I alla begränsningar av det ursprungliga problemet måste de fria villkoren

vara till höger och villkor med okända till vänster.

2. Begränsningar-ojämlikheter i det ursprungliga problemet måste ha tecken,

riktad åt ett håll.

3. Om den objektiva funktionen i det ursprungliga problemet minimeras, ska ojämlikhetsbegränsningarna skrivas med tecknet "≤", då i det dubbla problemet kommer objektivfunktionen att minimeras och tecknen på ojämlikhetsbegränsningarna kommer att vara "≥".

4. Varje begränsning av det ursprungliga problemet motsvarar en variabel i

dubbel uppgift. Om en variabel motsvarar en olikhet är den icke-negativ, om den motsvarar likhet är variabeln utan begränsningar för tecknet ("godtycklig").

5. Koefficienterna för variablerna i det dubbla problemets begränsningar erhålls genom att transponera matrisen som består av

koefficienter för variablerna i det ursprungliga problemet.

6. De fria villkoren för det ursprungliga problemet är koefficienterna vid

variabler i målfunktionen för det dubbla problemet, och gratis

termer i det dubbla problemet är koefficienterna för variablerna i

funktioner av det ursprungliga problemet. Vi noterar också att dualitetsrelationen är ömsesidig, dvs. uppgiften dubbla med avseende på den dubbla sammanfaller med den ursprungliga. Dubbla par av uppgifter är uppdelade i symmetriska och asymmetriska. I ett symmetriskt par är begränsningarna för de primära och dubbla problemen icke-strikta ojämlikheter och därför kan variablerna för båda problemen endast ta icke-negativa värden.

59. Konstruktion av dubbla problem till de ursprungliga problemen skrivna i modellens standard, kanoniska och allmänna form (konstruktion av symmetriska och asymmetriska dubbla problem)

Standardform (original)

Σ a ij x j ≤ bi , i=1,n(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Dubbel standard

Σ a ij y i ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = Σ b i y i ->min(3)

Det ursprungliga problemet i kanonisk form:

Σ a ij x j = bi, i=1,m(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

Dubbel kanonisk

Σ a ij y i ≤ c j , j=1,n(1)

y i - vilken som helst (2)

F = Σ b i y i ->max(3)

Låt oss ge en ekonomisk tolkning av ett par dubbla problem. Tänk på problemet med rationell användning av resurser. Låt företaget ha resurser b1,b2,...bm som kan användas för att producera n-typer av produkter. Låt oss också veta enhetskostnaden för j-typen av produkt cj (j=1,n) och förbrukningshastigheten för den i:te resursen (i=1,m) för produktion j:te enheter produkter - aij. Det krävs att bestämma produktionsvolymen för varje typ xj (j=1,n), för att maximera den totala kostnaden

f= c1x1+…+cnxn (1)

Samtidigt bör förbrukningen av resurser inte överstiga deras tillgänglighet:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Alla kända i sin ekonomiska mening är icke-negativa:

Xj>=0 (j=l,n). (3)

Observera att detta problem utgör ett symmetriskt dubbelproblem.

Asymmetriska dubbla problem.

Låt oss ta ZLP till det maximala i den kanoniska formen:

Max Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=l,n).

60. Huvud- och andra dualitetssats (tillståndssatser och förklara)

Den första dualitetssatsen.

Teorem: om ett av de dubbla problemen har en optimal plan, så är det andra lösbart, d.v.s. har en opt.plan. I det här fallet sammanfaller extremvärdena för objektivfunktionerna (j=från 1 till n) Σcjxj*= (i=från 1 till m)Σbiyi* om i originalet. problem är den objektiva funktionen obegränsad på uppsättningen av planer, då i det dubbla problemet är systemet av begränsningar inkonsekvent.

Andra dualitetssatsen och dess ekonomiska tolkning.

För att de möjliga lösningarna för ett par dubbla problem ska vara optimala är det nödvändigt och tillräckligt att följande villkor är uppfyllt: xj*(∑aij yi*-cj)=0, j från 1 till n, yi*( ∑aij xj*-bi)=0, I från 1 till m. Dessa är villkor för kompletterande slapphet. Det följer av dem: om någon begränsning av det dubbla problemet omvandlas av den optimala planen till strikt jämlikhet, då motsvarande komponent i opt. plan för det dubbla problemet bör vara lika med noll. Om någon komponent opt. planen är lika med noll, då konverteras motsvarande begränsning av det dubbla problemet av opt.planen till en strikt likhet xj*>0, därför (i= från 1 till m)Σaij yi*=cj opt.plan, då om kostnader>priser, produktionsvolym=0 Σaij yi* >cj därav xj*=0

yi*>0 därför (j=från 1 till n) Σaij xj*=bi (resursraser = resursbestånd).

(j=1 till n) Σaij xj*

Betydelsen av satsen är följande:

Om kostnadsuppskattningen av resursförbrukningen för produktion av en enhet av prod-ii \u003d pris, ingår denna typ av prod-ii i den optimala planen;

Om kostnaderna överstiger priset, bör prod-yu inte produceras;

Om resursförbrukning = lager, så är kostnadsberäkningen för denna resurs positiv. En sådan resurs kallas knapp. Den mest bristfälliga.res-s har högst poäng;

Om resursen inte är helt förbrukad är dess kostnadsberäkning = 0.

61. Konstruktion av den optimala stödplanen för det dubbla problemet från simplextabellen för det ursprungliga problemet

Information från kolumnerna i den inversa matrisen av linjära transformationer som ledde till det optimala resultatet. Kolumnerna i matris D-1 ger mycket användbar information.

Kolumn A3: "skuggpris" för resurs S2 är y01=0, kolumnen kvarstår

singel och från första raden kan man utläsa att x3=9, d.v.s. vid implementering av den hittade optimala planen kommer den första resursen att vara i överskott, och detta överskott (underutnyttjande) kommer bara att uppgå till 9 konventionella enheter.

Kolumn A4: "skuggpriset" för resursen S2 är lika med y02=1, resursen kommer att användas fullt ut och dess eventuella ökning kommer att leda till en ökning av målfunktionen (dvs. inkomst). Och eftersom y02=1, då ökningen av resurs S2 med 1 c.u. kommer att ge ett tillägg i termer av inkomst med.Z = y02· .w2 = = 1,1 = 1 (tusen UAH) (här.w2 är ökningen av resursen S2 och .Z är motsvarande inkomstökning). Med en sådan ökning av resursen S2 kommer den maximala inkomsten redan att vara Zmax=58 tusen UAH. + 1 tusen UAH = 59 tusen UAH. På fig. 6.2 illustrerar denna situation, en kommentar till den kommer att ges nedan. Av kolumn A4 följer också att med en ökning av resurs S2 med 1 c.u. för den nya optimala punkten kommer produktionen av varor T1 att minska med ½ ton (vid skärningspunkten mellan raden av grundvariabeln x1 och kolumn A4 är "-1/2"), och produktionen av varor T2 kommer att öka med 3 /2 ton (eftersom i raden med grundvariabeln x2 i kolumn A4 har vi "3/2". Vad som har sagts om kolumn A4 kommer att kommenteras nedan med grafiska konstruktioner (Fig. 6.2). Kolumn A5: "skuggan" " priset på resurs S3 är lika med y03=2. Detta innebär att en ökning av resursen S3 med 1 c.u. ger ett tillägg i Z till.Z = y03 .v3 = 2,1 =2(tusen hryvnia) och blir Zmax=58 tusen hryvnia. + 2 tusen UAH = 60 tusen UAH. Samtidigt, enligt kolumn A5 i tabell. 3 kommer produktionen från T1 att öka med ½ ton och T2 kommer att minska med ½ ton. Råvarulagret S1 (se rad 1) kommer att öka med 3/2 c.u.

62. Idén om den dynamiska programmeringsmetoden och dess geometriska tolkning. Bellmans optimitetsprincip.

Den optimala lösningen av problemet med den dynamiska programmeringsmetoden hittas på basis av den funktionella ekvationen

För att definiera det behöver du:

1. skriv ner den funktionella ekvationen för processens sista tillstånd (det motsvarar l \u003d n-1)

fn-1(Sl-1)=optimum(Rn(Sn-1,Un)+f0(Sn))

2. hitta Rn(Sn-1,Un) från en diskret uppsättning av dess värden för vissa fasta Sn-1 och Un från motsvarande tillåtna områden (eftersom f0(Sn)=0, sedan f1(Sn-1)= optimum(Rn( Sn-1,Un)

Som ett resultat, efter det första steget, är lösningen Un och motsvarande värde för funktionen f1(Sn-1) kända

3. Minska värdet på l med ett och skriv ner motsvarande funktionella ekvation. För l=n-k (k= 2,n) ser det ut som

fk(Sn-k)=optimum(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. hitta en villkorligt optimal lösning baserad på uttryck (2)

5. kontrollera vad värdet på l är lika med. Om l=0 är beräkningen av villkorligt optimala lösningar slutförd och den optimala lösningen av problemet för det första tillståndet av processen hittas. Om l inte är lika med 0, gå till steg 3.

6. Beräkna den optimala lösningen av problemet för varje efterföljande steg i processen, flytta från slutet av beräkningarna till början.

Dynamics of programs-metoden gör att ett problem med många variabler kan ersättas av ett antal successivt lösta problem med ett mindre antal variabler. Beslutet tas steg för steg. Huvudprincipen som optimeringen av en flerstegsprocess bygger på, liksom egenskaperna hos beräkningsmetoden, är Bellmans optimalitetsprincip.

Optimalt beteende har egenskapen att oavsett det initiala tillståndet och det initiala beslutet är, måste efterföljande beslut vara optimala med avseende på det tillstånd som är ett resultat av det initiala beslutet.

Matematiskt skrivs det som ett uttryck för formen:

fn-1(Sl)=optimum(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1)Optimum i uttrycket betyder maximum eller minimum beroende på problemets tillstånd.

63. Krav på problem lösta med DP-metoden

Dynamisk programmering är en matematisk metod för att hitta optimala lösningar på flerstegsproblem. En flerstegsprocess är en process som utvecklas över tid och bryts ner i ett antal steg, eller stadier.

En av egenskaperna hos den dynamiska programmeringsmetoden är att de beslut som fattas i relation till flerstegsprocesser inte betraktas som en enda handling, utan som ett helt komplex av sammanhängande beslut. Denna sekvens av inbördes relaterade beslut kallas en strategi.Målet med optimal planering är att välja en strategi som ger det bästa resultatet sett till ett förvalt kriterium. En sådan strategi kallas optimal.

En annan viktig egenskap hos metoden är oberoendet av det optimala beslut som tas vid nästa steg från förhistorien, d.v.s. om hur processen som optimeras har nått sitt nuvarande tillstånd. Den optimala lösningen väljs endast med hänsyn till de faktorer som kännetecknar processen för tillfället.

Metoden för dynamiska program kännetecknas också av det faktum att valet av den optimala lösningen vid varje steg bör göras med hänsyn till dess konsekvenser i framtiden. Detta innebär att samtidigt som du optimerar processen vid varje enskilt steg, bör du inte i något fall glömma alla efterföljande steg.

64. Ekonomisk formulering och konstruktion av en matematisk modell av problemet löst med DP-metoden (om exemplet med problemet med fördelningen av kapitalinvesteringar). Bellman återfallsrelation.

Låt oss preliminärt förklara att den dynamiska programmeringsmetoden främst tillämpas på de problem där processen (eller situationen) som optimeras är utplacerad i rum eller tid, eller både och.

Låt själva processen (situationen) vara så komplicerad att det inte finns något sätt att optimera den med kända metoder. Sedan, enligt metoden för dynamisk programmering, delas en KOMPLEX process (drift, situation) upp (partitioneras) i ett antal steg (steg). Denna uppdelning är i många fall naturlig, men i det allmänna fallet introduceras den på konstgjord väg. . Till exempel, när man överväger ett parti schack, tjänar varje drag av var och en av spelarna

bryta ner hela partiet i separata steg (steg). Och i en militär operation för att förfölja en missil mot en annan måste hela den kontinuerliga processen artificiellt delas upp i stadier, till exempel varje sekund av observation. Den dynamiska programmeringsmetoden tillåter att optimeringen av hela den komplexa processen ersätts av villkorlig optimering för vart och ett av stegen

(steg) följt av syntesen av optimal kontroll av hela processen. Samtidigt ger metoden att villkorlig optimering i ett separat steg (steg) görs i första hand av hela operationens intresse.

Alla beräkningar som gör det möjligt att hitta det optimala värdet av effekten som uppnås i n steg, fn(S0), utförs enligt formel (1), som kallas den grundläggande funktionella Bellman-ekvationen eller återfallsrelationen. Vid beräkning av nästa värde för funktionen fn-1 används värdet på funktionen fn-(l+1) som erhållits i föregående steg, och det direkta värdet av effekten Rl+1(Sl,Ul+1), uppnås som ett resultat av valet av lösningen Ul+1 för ett givet tillstånd Sl-system. Processen att beräkna värdet av funktionen fn-1(l=0,n-1)

Den utförs under det naturliga initiala tillståndet f0(Sn)=0, vilket betyder att utanför systemets sluttillstånd är effekten noll.

65. Problemet med fördelningen av kapitalinvesteringar (exempel).

För att lösa problemet med den optimala fördelningen av kapitalinvesteringar kommer vi att använda den funktionella Bellman-ekvationen. Först, med den enklaste situationen, kommer vi att illustrera härledningen av Bellmans funktionella ekvation, och sedan, med hjälp av ett exempel, kommer vi att bevisa hur man använder denna ekvation för att lösa problemet av intresse för oss.

Låt oss börja med den optimala fördelningen av allokerade kapitalinvesteringar i mängden K mellan två företag. Företagens planeringsavdelningar bildade på basis av sina beräkningar inkomstfunktionerna q(x) för företaget P1 och h(x) för företaget P2. Dessa funktioner innebär att om det första eller andra företaget erhåller en investering till ett belopp av x, då det första företaget

inkomsten q(x) kommer att tas emot, och den andra h(x), och värdet på x kan anta kontinuerliga eller kända diskreta värden från 0 till K.

Så låt företaget P1 allokera kapitalinvesteringar i mängden x, då tilldelas företaget P2 beloppet K - x. I detta fall kommer inkomst q(x) att erhållas från det första företaget och h(K - x) från det andra. Om investeringarna K fördelades för en planeringsperiod, blir den totala inkomsten från de två företagen R(K, x) = q(x) + h(K - x). Uppenbarligen måste x och följaktligen K - x väljas så att R(K, x) får sitt maximala värde, vilket vi betecknar med F(K):

Det här inlägget är som ett skelett för mer kompletta bidrag.

funktionell Bellman-ekvation. KOMPLICERA vår uppgift genom att fördela kapitalinvesteringar över två planeringsperioder (två steg) . Låt det initialt beslutas att allokera beloppet x till det första företaget P1 och x till det andra företaget P1. Generellt sett skulle inkomsten vara lika med R(K, x) = q(x) +

h(K - x). Om vi ​​har i åtanke att investeringarna är fördelade över 2 perioder (2 etapper), så kommer investeringsbalansen i det första företaget att vara x, där , och vid den andra - .(K - x), där Följaktligen inkomsten för andra perioden kommer att vara q( .x) - enligt den första faciliteten och h[.(K - x)] - enligt den andra. Dynamisk programmeringsoptimering börjar som regel från slutskedet. Därför utgår vi från det andra steget och betecknar F1 den högsta möjliga inkomsten från två företag i den andra

skede. Skaffa sig

Sedan, till det övervägda sista (i vårt fall, det andra) steget, lägger vi typ till det föregående (i vårt fall, det första) steget och hittar den maximala inkomsten från de två stegen tillsammans:

På liknande sätt får vi för n steg

där Fn-1 är den objektivfunktion som ger bäst resultat för de sista (n - 1) stegen. Den resulterande funktionella Bellman-ekvationen är återkommande, dvs. associerar Fn-värdet med Fn-1-värdet.

Mer allmänt har Bellman-ekvationen formen

där , Fn-1 - maximal inkomst för (n - 1) sista etapper, Fn -

maximal inkomst för alla n stadier.

66. Konceptet att lösa problem med icke-linjär programmering

Låt problemet med olinjär programmering ställas i följande allmänna form: hitta sådana värden av variablerna x1, x2, ..., xn som uppfyller villkoren:

och ta med det erforderliga extremumet (maximum eller minimum) för den objektiva funktionen

f = f(x1, x2,…, xn), (13,2)

där f(х1, …, хn) och qi(х1, …, хn) (m , 1 i =) är reellt icke-linjära,

reguljära funktioner av n reella variabler.

Enligt deras allmänna egenskaper kan icke-linjära programmeringsproblem

skiljer sig väsentligt från de linjära. Till exempel kan domänen av genomförbara lösningar redan vara icke-konvexa, och den yttersta delen av den objektiva funktionen kan observeras vid vilken punkt som helst av den genomförbara domänen. Metoder för att lösa olinjära problem skiljer sig också avsevärt. Låt oss bara överväga några metoder för att lösa dessa problem.

Först och främst är det grafiska tillvägagångssättet också giltigt för att lösa de enklaste problemen med olinjär programmering. Så om variablerna x1 och x2 är argumenten för problemet, byggs först området med möjliga lösningar på planet för dessa variabler, och sedan bestäms den optimala punkten i området med hjälp av nivåerna för den objektiva funktionen f(x1,x2).

I icke-linjär programmering används en gradientmetod för att lösa många problem. Det finns ett antal gradientmetoder, vars essens är att hitta det optimala resultatet med hjälp av gradienten för målfunktionen - en vektor som indikerar riktningen för maximal ökning av målet för den betraktade punkten. I det allmänna fallet utförs sökproceduren i ett iterativt läge från den initialt valda punkten till punkterna med den bästa indikatorn. Låt till exempel . - domän av tillåtna lösningar

övervägt problem, och den iterativa processen med beräkningar börjar från punkten

Vidare görs först en övergång längs gradienten för den objektiva funktionen, och sedan en återgång till området. längs gradienten till den störda gränsen för O2 O3-regionen. 13.3 visas så att Ai med udda index tillhör området, och punkterna Ai med jämna index inte gör det. När vi närmar oss den optimala punkten Q, konvergerar riktningarna för arbetsgradienterna. Därför kommer det ideala kriteriet för att stoppa processen att vara kollineariteten för målgradienten och den brutna gränsgradienten.

67. Begreppet parametrisk och heltalsprogrammering .

Påstående och matematisk modell av ZCLP.

I problem med odelbara objekt ställs heltalsvillkor på variabler. Ibland gäller dessa villkor för alla variabler, ibland för några av variablerna. Tänk på ett heltalsproblem

f=(n,j=1)∑CjXi max

(n,j=1)∑AijXj=bi, i=1,m

xi-heltal,j=1,n

Nu, till skillnad från det allmänna linjära programmeringsproblemet, kommer den optimala planen inte nödvändigtvis att vara i spetsen av planpolyedern. Det finns följande metoder för att lösa heltalsproblem:

1. Klippmetoder

2.Kombinatorisk

3. Ungefärliga metoder..

Parametrisk programmering är en gren av matematisk programmering som ägnas åt studiet av optimeringsproblem där tillåtlighetsvillkoren och den objektiva funktionen beror på några deterministiska parametrar.

Definition. Linjär programmering (LP) - vetenskapen om forskningsmetoder och att hitta extrema (maximala och lägsta) värden för en linjär funktion, på vilka okända linjära begränsningar åläggs.

Denna linjära funktion kallas mål, och begränsningar som är matematiskt skrivna som ekvationer eller ojämlikheter kallas begränsningssystem.

Definition. Det matematiska uttrycket för den objektiva funktionen och dess begränsningar kallas matematisk modell av det ekonomiska problemet.

I allmänhet skrivs den matematiska modellen för ett linjär programmeringsproblem (LP) som

med restriktioner:

Var xj- okänd; aij, b i, cj ges konstanter.

Alla eller vissa ekvationer i begränsningssystemet kan skrivas som olikheter.

Den matematiska modellen i en kortare notation har formen

med restriktioner:

Definition. En möjlig lösning (plan) av ett linjärt programmeringsproblem är en vektor = ( x 1 , x 2 ,..., x p), att tillfredsställa begränsningssystemet.

Uppsättningen av tillåtna lösningar utgör regionen av tillåtna lösningar (ODD).

Definition. En genomförbar lösning, där objektivfunktionen når sitt extremvärde, kallas den optimala lösningen av det linjära programmeringsproblemet och betecknas opt.

Grundläggande tillåten lösning (X 1 , X 2 ,..., x r , 0, …, 0) är en referenslösning, där r- begränsningssystemets rangordning.

Den matematiska modellen för LP-problemet kan vara kanonisk och icke-kanonisk.

7. Lösa linjära programmeringsproblem med en grafisk metod. Grafer över begränsningsfunktioner. Nivå linjer.

Grafisk metod för att lösa linjära programmeringsproblem

Den enklaste och mest visuella metoden för linjär programmering är den grafiska metoden. Det används för att lösa LP-problem med två variabler givna i icke-kanonisk form och många variabler i kanonisk form, förutsatt att de inte innehåller mer än två fria variabler.

Ur en geometrisk synvinkel, i ett linjärt programmeringsproblem, söker man efter en sådan hörnpunkt eller en uppsättning punkter från en tillåten uppsättning lösningar där den högsta (lägre) nivålinjen nås, belägen längre (närmare) än andra i riktning mot snabbast tillväxt.

För att hitta extremvärdet av objektivfunktionen i den grafiska lösningen av LP-problem används vektorn L() på ytan X 1 ÅH 2 , som vi betecknar . Denna vektor visar riktningen för den snabbaste förändringen i objektivfunktionen. Med andra ord är vektorn normalen för nivålinjen L()

Var e 1 och e 2 - enhetsvektorer längs axlarna OXE 1 och OXE 2 respektive; alltså = (∂L/∂х 1 , ∂L/∂х 2 ). Vektorkoordinaterna är de objektiva funktionskoefficienterna L(). Konstruktionen av nivålinjen kommer att övervägas i detalj vid lösning av praktiska problem.

Problemlösningsalgoritm

1. Vi hittar området med genomförbara lösningar för systemet med begränsningar av problemet.

2. Att bygga en vektor .

3. Rita en nivålinje L 0 , som är vinkelrät .

4. Vi flyttar nivålinjen i vektorns riktning för uppgifter maximalt och i motsatt riktning , för minimiuppgifter.

Nivålinjen flyttas tills den bara har en gemensam punkt med området för möjliga lösningar. Denna punkt, som bestämmer den unika lösningen av LP-problemet, kommer att vara yttersta punkten.

Om det visar sig att nivålinjen är parallell med en av sidorna av ODT, nås i detta fall extremumet på alla punkter på motsvarande sida, och LP-problemet kommer att ha ett oändligt antal lösningar. Det sägs att ett sådant LP-problem har alternativ optimum och dess lösning ges av formeln:

Där 0 ≤ t≤ 1, 1 och 2 - optimala lösningar vid hörnpunkterna av ODS.

Ett LP-problem kan vara olösligt när de begränsningar som definierar det visar sig vara motsägelsefulla.

5. Vi hittar koordinaterna för extremumpunkten och värdet av den objektiva funktionen i den.

Exempel 3 Att välja det bästa alternativet för produktsläpp

Företaget tillverkar 2 typer av glass: grädde och choklad. För tillverkning av glass används två initiala produkter: mjölk och fyllmedel, vars kostnader per 1 kg glass och dagliga leveranser anges i tabellen.

Marknadsundersökningar visade att den dagliga efterfrågan på smörglass överstiger efterfrågan på chokladglass, men med inte mer än 100 kg.

Dessutom fann man att efterfrågan på chokladglass inte överstiger 350 kg per dag. Detaljpriset på 1 kg krämig glass är 16 rubel, choklad - 14 rubel.

Hur mycket av varje typ av glass bör företaget producera för att maximera sina försäljningsintäkter?

Lösning. Beteckna: x 1 - daglig produktionsvolym av krämig glass, kg; x 2 - daglig produktion av chokladglass, kg.

Låt oss göra en matematisk modell av problemet.

Priserna för glass är kända: 16 rubel respektive 14 rubel, så den objektiva funktionen kommer att se ut:

Sätt gränser för mjölk för glass. Dess konsumtion för gräddglass är 0,8 kg, för chokladglass - 0,5 kg. Lager av mjölk 400kg. Därför kommer den första ojämlikheten att se ut så här:

0,8x 1 + 0,5x 2 ≤400 - den första ojämlikheten är en begränsning. Resten av ojämlikheterna är konstruerade på liknande sätt.

Resultatet är ett system av ojämlikheter. vad är lösningsområdet för varje ojämlikhet. Detta kan göras genom att ersätta koordinaterna för punkten O(0:0) i var och en av olikheterna. Som ett resultat får vi:

Figur OABDEF- domän av tillåtna lösningar. Vi bygger vektorn (16; 14). nivålinje L 0 ges av ekvationen 16x 1 +14x 2 =Konst. Vi väljer valfritt tal, till exempel talet 0, sedan 16x 1 +14x 2 =0. I figuren, för linjen L 0, väljs ett positivt tal, inte lika med noll. Alla nivålinjer är parallella med varandra. Den normala vektorn för nivålinjen.

Flytta nivålinjen i vektorns riktning. utgångspunkt L 0 från regionen av genomförbara lösningar är poängen D, dess koordinater definieras som skärningspunkten mellan linjerna som ges av ekvationerna:

När vi löser systemet får vi punktens koordinater D(312.5; 300), där det kommer att finnas en optimal lösning, dvs.

Således måste företaget producera 312,5 kg smörglass och 300 kg chokladglass per dag, medan intäkterna från försäljningen blir 9 200 rubel.

8. Reduktion av ett godtyckligt linjärt programmeringsproblem till huvudproblemet. Konvertera begränsningar som ges av ojämlikheter till motsvarande ekvationer.

9. Enkel metod. Metodens egenskaper och algoritm, dess tillämpbarhet.

För att lösa problemet med simplexmetoden är det nödvändigt:

1. Ange en metod för att hitta den optimala referenslösningen

2. Ange metoden för övergång från en referenslösning till en annan, på vilken värdet av målfunktionen kommer att vara närmare det optimala, d.v.s. ange ett sätt att förbättra referenslösningen

3. Sätt kriterier som gör att du i tid kan stoppa uppräkningen av referenslösningar på den optimala lösningen eller lämna en slutsats om frånvaron av en optimal lösning.

Simplexmetodens algoritm för att lösa linjära programmeringsproblem

1. Ta problemet till den kanoniska formen

2. Hitta den initiala supportlösningen med en "enhetsbas" (om det inte finns någon supportlösning har problemet ingen lösning, på grund av inkompatibiliteten hos begränsningssystemet)

3. Beräkna uppskattningar av vektorexpansion i termer av referenslösningens bas och fyll i tabellen för simplexmetoden

4. Om kriteriet för unikheten hos den optimala lösningen är uppfyllt, slutar lösningen av problemet

5. Om villkoret för existensen av en uppsättning optimala lösningar är uppfyllt, så hittas alla optimala lösningar genom enkel uppräkning

10. Transportuppgift. Definition, typer, metoder för att hitta den initiala lösningen av transportproblemet.

Transportproblemet är ett av de vanligaste linjära programmeringsproblemen. Dess mål är att utveckla de mest rationella sätten och medlen för att transportera varor, vilket eliminerar alltför långväga, mötande, upprepade transporter.

1. Hitta den initiala referenslösningen;

2. Kontrollera denna lösning för optimalitet;

3. Övergång från en grundläggande lösning till en annan.

Föreläsning 2

I kanonisk form

tillåten lösning av PLP(acceptabel plan).

optimal lösning av LLP.

Nödvändighet

Exempel.

Låt oss skriva in problemet kanonisk form

Speciella situationer för den grafiska lösningen av ZLP

Förutom när uppgiften är den enda optimala lösningen för och , kan vara speciella situationer:

1. uppgift har ett oändligt antal optimala lösningar – funktionens extremum nås på segmentet ( alternativ optimum)- Figur 2;

2. uppgift inte lösbart på grund av obegränsad ODR, eller - Figur 3;

3. ODR - enda poäng Ah, då;

4. uppgift inte lösbart om ODR har ett tomt område.

A

Figur 2 Figur 3

Om nivålinjen är parallell med sidan av området med möjliga lösningar, nås extremumet på alla punkter på sidan. Problemet har ett oändligt antal optimala lösningar - alternativ optimum . Den optimala lösningen hittas av formeln

var är parametern. För alla värden från 0 till 1 kan du få alla punkter i segmentet, för var och en av dem har funktionen samma värde. Därav namnet - alternativ optimum.

Exempel. Lös det linjära programmeringsproblemet grafiskt ( alternativ optimum):

Frågor för självkontroll

1. Skriv ner det linjära programmeringsproblemet i allmän form.

2. Skriv ner det linjära programmeringsproblemet i kanoniska och standardiserade former.

3. Vilka transformationer kan användas för att gå från den allmänna eller standardformen av ett linjärt programmeringsproblem till det kanoniska?

4. Ge en definition av genomförbara och optimala lösningar på det linjära programmeringsproblemet.

5. Vilken av lösningarna är "bäst" för problemet med att minimera funktionen if ?

6. Vilken av lösningarna är "bäst" för problemet med att maximera funktionen if ?

7. Skriv ner standardformen för den matematiska modellen av ett linjärt programmeringsproblem med två variabler.

8. Hur man konstruerar ett halvplan givet av en linjär olikhet med två variabler ?

9. Vad kallas lösningen av ett system av linjära olikheter med två variabler? Konstruera på planet domänen av möjliga lösningar för ett sådant system av linjära ojämlikheter, som:

1) har en unik lösning;

2) har en oändlig uppsättning lösningar;

3) har ingen lösning.

10. Skriv för en linjär funktion vektorgradient, namnge typen av nivålinjer. Hur är gradient- och nivålinjerna placerade i förhållande till varandra?

11. Formulera en algoritm för en grafisk metod för att lösa en standard LLP med två variabler.

12. Hur hittar man lösningens koordinater och värden, ?

13. Konstruera området med genomförbara lösningar, gradient- och nivålinjer, för linjära programmeringsproblem där:

1) nås vid en enda punkt, och - på ODR-segmentet;

2) nås vid en enda punkt av ODS, och .

14. Ge en geometrisk illustration av LLP om det:

1) har unika optimala lösningar för och ;

2) har en uppsättning optimala lösningar för .

Föreläsning 2

grafisk metod för att hitta den optimala lösningen

1. Former för linjära matematiska modeller och deras transformation

2. Grafisk metod för att lösa ett linjärt programmeringsproblem

3. SÄRSKILDA SITUATIONER FÖR DEN GRAFISKA LÖSNINGEN AV LLP

4. Grafisk lösning av ekonomiska problem med linjär programmering

Former för linjära matematiska modeller och deras transformation

En matematisk modell av ett linjärt programmeringsproblem (LPP) kan skrivas i en av tre former.

I generell form av den matematiska modellen det krävs för att hitta maximum eller minimum av den objektiva funktionen; begränsningssystemet innehåller ojämlikheter och ekvationer; inte alla variabler kan vara icke-negativa.

I kanonisk form den matematiska modellen behöver hitta det maximala av den objektiva funktionen; begränsningssystemet består endast av ekvationer; alla variabler är icke-negativa.

I standardformen för en matematisk modell krävs det att man hittar max eller minimum av en funktion; alla begränsningar är ojämlikheter; alla variabler är icke-negativa.

Lösningen av systemet av begränsningar som uppfyller villkoren för icke-negativitet hos variablerna kallas tillåten lösning av PLP(acceptabel plan).

Uppsättningen av genomförbara lösningar kallas området för genomförbara lösningar för LLP.

En genomförbar lösning, där den objektiva funktionen når ett extremvärde, kallas optimal lösning av LLP.

De tre formerna av LLP är likvärdiga i den meningen att var och en av dem kan reduceras till en annan form med hjälp av matematiska transformationer.

Nödvändighet övergång från en form av matematisk modell till en annan associerade med metoder för att lösa problem: till exempel, simplexmetoden, som används i stor utsträckning i linjär programmering, tillämpas på ett problem skrivet i kanonisk form, och den grafiska metoden tillämpas på standardformen av en matematisk modell.

Övergång till den kanoniska notationen ZLP.

Exempel.

Låt oss skriva in problemet kanonisk form, införa en extra (balans)variabel med "+"-tecknet på vänster sida av den första olikheten i begränsningssystemet, och en ytterligare variabel med "minustecknet" på den vänstra sidan av den andra olikheten.

Den ekonomiska innebörden av olika tilläggsvariabler kanske inte är densamma: den beror på den ekonomiska innebörden av de restriktioner som dessa variabler ingår i.

Så i problemet med användningen av råvaror visar de resten av råvarorna, och i problemet med att välja optimala teknologier visar de den outnyttjade tiden för företaget som använder en viss teknik; i problemet med skärning - frigöring av ämnen av en given längd som överstiger planen, etc.