Definition. Linjär programmering (LP) - vetenskapen om forskningsmetoder och att hitta extrema (maximala och lägsta) värden för en linjär funktion, för 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 x j- 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 för vilken målfunktionen 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 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 de 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/∂x 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 produktutgivningsalternativet

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 krämig glass ä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, dvs. 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 en initial referenslösning med en "enhetsbas" (om det inte finns någon referenslösning har problemet ingen lösning, på grund av inkompatibiliteten i systemet med begränsningar)

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 sätten 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.

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 £ dj , 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 till grund för en stor grupp av 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ängligt 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 FRÅN 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 den form 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 på 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 ett 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 används en enklare GTE-modell, vilket är beroendet av dragkraften 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 förutom konstruktionsegenskaperna också beror 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 med 20°, ställs tryckkraften in på 6780 kg, och ytterligare tio sekunder senare, när gasreglaget avböjs med 30°, sätts tryckkraften till 10170 kg. Gränsvärdet för dragkraften är
14270 kg.

Liknande information.

stat läroanstalt högre

yrkesutbildning

"Moscow State Technical University uppkallad efter N.E. Bauman"

Kaluga gren

"Lösning av problemet med linjär programmering med simplexmetoden"

Syftet med arbetet: att studera och lära sig omsätta simplexet i praktiken - en metod för att lösa de direkta och dubbla problemen med linjär programmering

Teoretisk del.

Matematisk formulering av problemet med linjär programmering.

Det följer av praxis att överväga problem med matematisk programmering att det är nästan omöjligt att lösa dem i allmänna termer. Det är tillrådligt att överväga separata klasser (typer) av problem. För varje sådan klass är det möjligt att formulera en lösningsalgoritm som endast är acceptabel för den här klassen uppgifter. De mest utvecklade inom matematisk programmering är linjär programmeringsproblem (LP).

I linjära programmeringsproblem är objektivfunktionen linjär, och begränsningsvillkoren innehåller linjära likheter och linjära olikheter. Variabler kan eller kanske inte omfattas av kravet på icke-negativitet. Samma linjära programmeringsproblem kan skrivas i olika former. Om alla begränsningar är i form av ojämlikheter, så skrivs problemet i standardform. Om alla dess begränsningar förutom

är likheter, skrivs det linjära programmeringsproblemet i kanonisk form.

Allmän bild av ett linjärt programmeringsproblem

,

Begränsningar:

1. Rätt delar av alla begränsningar måste vara icke-negativa . Om någon av koefficienterna< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

2. Alla begränsningar måste presenteras i form av jämlikheter, därför, när man går från ojämlikhet till jämlikhet, används apparaten av ytterligare variabler.

Om de initiala begränsningarna bestämmer förbrukningen av någon resurs (tecknet ""), då variablerna ska tolkas som återstoden eller oanvänd del av resursen. I det här fallet är det restvariabeln och läggs in i ekvationen med tecknet "+".

Om de initiala begränsningarna definierar ett överskott av någon resurs (tecken ""), så introduceras en överskottsvariabel tecken "-".

Variabler:

Alla variabler måste vara icke-negativa, d.v.s. .

Om en variabel inte har någon teckenbegränsning måste den representeras som skillnaden mellan två icke-negativa variabler: , där . En sådan substitution bör användas i alla begränsningar som innehåller denna variabel, såväl som i uttrycket för den objektiva funktionen.

Om en sådan variabel faller in i den optimala lösningen, då

Målfunktion:

Att maximeras eller minimeras.

Systemet med begränsningar i form av likheter och ojämlikheter bildar en konvex uppsättning - en konvex polyeder. Denna uppsättning kan vara begränsad eller obegränsad. Den objektiva funktionen för ett linjärt programmeringsproblem är också en konvex funktion. Således är det linjära programmeringsproblemet ett specialfall av det konvexa programmeringsproblemet.

Betrakta systemet med begränsningar för ett linjärt programmeringsproblem i form av likheter

(1)

System (1) av linjära ekvationer är konsekvent om det har minst en lösning. System (1) kallas redundant om en av ekvationerna kan uttryckas som en linjär kombination av de andra.

I system (1) är antalet variabler (n okända) större än antalet restriktioner m. Vi kommer att anta att rangordningen för detta system är lika med m (systemet är icke-redundant) och att systemet (1) är konsekvent. Då bildar m variabler från deras totala antal basvariabler, och andra variabler kallas icke-grundläggande.Om ett ekvationssystem har en lösning, så har det också en grundläggande lösning.En lösning till ekvationssystemet (1) kallas tillåtlig om alla dess komponenter är icke-negativa. Om ett system av linjära ekvationer har en tillåten lösning, så har det också en grundläggande tillåten lösning. av alla möjliga lösningar av system (1) är en konvex mängd, dvs. Lösningarna på det linjära programmeringsproblemet är konvexa. Eftersom denna uppsättning bildas av plan (hyperplan) har den formen av en konvex polyeder. Den grundläggande möjliga lösningen motsvarar den konvexa polyederns ytterpunkt (dess ytor eller vertex). finns en optimal lösning på ett linjärt programmeringsproblem, då finns det en grund är den optimala lösningen.

Den objektiva funktionen för ett linjärt programmeringsproblem är ekvationen för ett plan (eller ett hyperplan för mer än tre variabler). Max eller lägsta värde objektivfunktionen för ett linjärt programmeringsproblem når antingen en vertex av en konvex polyeder eller en av dess ytor. Sålunda ligger lösningen (lösningarna) av det linjära programmeringsproblemet vid hörnen på den konvexa polyedern, och för att hitta den är det nödvändigt att beräkna värdena för den objektiva funktionen vid hörnen på den konvexa polyedern som bestäms av villkoren - begränsningar av problemet.

Lösa ett linjärt programmeringsproblem med en grafisk metod.

Svårigheten med att bygga en matematisk modell ligger i identifieringen av variabler och den efterföljande representationen av målet och begränsningarna i form av matematiska funktioner för dessa variabler. Om modellen bara innehåller två variabler kan det linjära programmeringsproblemet lösas grafiskt. Vid tre variabler blir den grafiska lösningen mindre visuell och med ett större värde på variablerna är det till och med omöjligt. Den grafiska lösningen tillåter oss dock att dra slutsatser som ligger till grund för utvecklingen av en generell metod för att lösa ett linjärt programmeringsproblem.

Det första steget i att använda den grafiska metoden är att representera de genomförbara lösningarna geometriskt, d.v.s. konstruktion av domänen av tillåtna lösningar (ODD.), där alla begränsningar för modellen samtidigt är uppfyllda. När en grafisk lösning erhålls plottas variabeln längs den horisontella axeln och - längs den vertikala. När man bildar SDE är det nödvändigt att förhindra mottagandet av oacceptabla lösningar som är förknippade med behovet av att uppfylla villkoret om variablernas icke-negativitet. Före konstruktionen är det nödvändigt att bestämma kvadranter där ODR kommer att finnas. Kvadranterna definieras av tecknen för variablerna och . Villkoren för variablernas icke-negativitet och begränsar intervallet för deras tillåtna värden till den första kvadranten. Om variabeln inte är begränsad i tecken, så begränsas området av den första och andra kvadranten, om , då - av den första och fjärde kvadranten. Övriga gränser för lösningsutrymmet på planet visas med raka linjer konstruerade enligt begränsningsekvationerna, förutsatt att tecknet ersätts med "="-tecknet. I detta fall måste följande beaktas: den högra sidan av alla begränsningar måste vara icke-negativa . Om någon begränsning< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.

Som ett resultat av konstruktionerna erhålls en polygon, som bestämmer utrymmet för lösningar. Om en av restriktionerna har tecknet "=", degenererar ODD till ett segment.

Vid varje punkt som hör till området eller gränserna för lösningspolygonen är alla begränsningar uppfyllda, så alla lösningar som motsvarar dessa punkter är giltiga. Lösningsutrymmet innehåller ett oändligt antal sådana punkter, trots detta är det möjligt att hitta den optimala lösningen. För att göra detta är det nödvändigt att konstruera i variabelplanet , gradienten för den objektiva funktionen. Bestämning av den optimala punkten beror på problemet som ska lösas.

Om ett maximeringsproblem definieras i objektivfunktionen, kommer den optimala punkten att placeras i riktningen för att öka gradienten; om minimeringsproblemet definieras, då i riktning mot att minska gradienten för objektivfunktionen. För att bestämma den optimala punkten kommer vi att flytta objektivfunktionen i riktning mot att öka (minska) gradienten tills den skiftar till området med oacceptabla lösningar.

Efter att ha hittat den optimala punkten i lösningsutrymmet, bestäms dess koordinater och värdet av den objektiva funktionen i det. Riktigheten av valet av den optimala punkten kan kontrolleras genom att beräkna objektivfunktionen vid hörnen av lösningspolyedern. I LLP är domänen av genomförbara lösningar alltid en konvex uppsättning, dvs. en sådan mängd att, tillsammans med vilka två punkter som helst som hör till denna mängd, segmentet som förbinder dessa två punkter också tillhör samma mängd. Varje funktion ökar på det snabbaste sättet i riktning mot dess gradient.

Lösning av ett linjärt programmeringsproblem med simplexmetoden.

direkt uppgift.

Betrakta ett linjärt programmeringsproblem i kanonisk form:

Hitta max (minimum) för en funktion under förhållanden

Det antas att det finns en lösning på detta problem. För att hitta den optimala lösningen är det nödvändigt att hitta tillåtna baslösningar och välja den optimala baslösningen bland dem.

Simplexmetoden är en algebraisk metod för att lösa linjära programmeringsproblem. Under beräkningarna förbigås hörnen av lösningspolyedern (ODP) sekventiellt med en kontroll av optimalitetsförhållandena vid varje vertex. Dessutom åtföljs varje övergång till en intilliggande vertex av en förbättring av objektivfunktionen.

Beräkningsprocedurer av simplexmetoden.

Med den grafiska metoden för att lösa LLP, motsvarar den optimala lösningen alltid en av hörnpunkterna (extrema) i lösningsutrymmet. Detta resultat ligger till grund för konstruktionen av simplexmetoden. Simplexmetoden har inte synligheten av en geometrisk representation av lösningsrummet.

Simplexmetoden implementerar en ordnad process i vilken, med utgångspunkt från någon initial tillåten hörnpunkt, successiva övergångar görs från en tillåten extrempunkt till en annan tills en optimal lösningspunkt hittas.

Låt oss beteckna: - Det totala antalet variabler i LLP, presenterade i kanonisk form; - Antal initiala variabler; - antalet restriktioner, - antalet ytterligare variabler, alltså .

Varje vertex av lösningspolyedern har - icke-noll variabler och () - noll variabler.

Variabler som inte är noll kallas grundläggande, nollvariabler kallas icke-grundläggande.

Vi kompletterar systemet med likheter med jämlikheten i den objektiva funktionen, samtidigt som vi utgår från att det är en grundvariabel som alltid finns i grunden för vilken vertex som helst.

För att få en lösning sammanställs ett initialt godtagbart underlag, där grundvariablerna ska representeras som enhetsvektorer. Detta innebär att ekvationerna som representerar en given vertex måste inkludera varje basvariabel i endast en rad med faktorn 1.

När man väljer en initial acceptabel grund för att sammanställa en simplextabell, i det första steget CT(0), är de initiala variablerna lika med noll och är icke-grundläggande, bland de ytterligare variablerna som introduceras väljs variabler med koefficienter lika med ett. Variablerna i likheter (2) - (4) är grundläggande och anger - raden med koefficienter lika med 0. För att fylla simplextabellen är det nödvändigt att transformera objektivfunktionen till formuläret . Så får vi äntligen:

Vid sammanställning av en simplextabell följs följande regler:

kolumnen längst till vänster innehåller de grundläggande variablerna och ;

kolumnen längst till höger innehåller de högra delarna av begränsningarna;

Den första raden innehåller variablerna i en viss ordning:

först, sedan icke-basvariabler, basvariabler finns i de sista kolumnerna före den högra sidan (IF). Vi skriver koefficienterna i CT(0):

							OM
	1			0	0	0	0
	0			1	0	0
	0			0	1	0
	0			0	0	1

Optimiteten för någon av hörnen bestäms av koefficienterna för icke-grundläggande variabler i raden i den aktuella simplextabellen:

För maximeringsproblemet är denna vertex optimal om alla koefficienter för icke-grundläggande variabler i raden – är icke-negativa (>0);

För minimeringsproblemet är denna vertex optimal om alla koefficienter för icke-grundläggande variabler i raden - är icke-positiva (< 0).

Om i problemet med maximering (minimering) en icke-grundläggande variabel i raden – har en koefficient<0(>0), då är den aktuella punkten inte optimal och det är nödvändigt att ändra grunden. För att göra detta, välj en icke-grundläggande variabel som har den mest negativa (positiva) koefficienten på raden -. Den valda icke-grundläggande variabeln kommer att inkluderas i den nya basen, därför kallas den för den inkluderade variabeln. Basvariabeln som kommer att tas ur basen kallas exkluderingsvariabeln.

Den exkluderade variabeln kommer att vara den grundläggande variabeln som först kommer att vända till "0" när man flyttar till en intilliggande vertex efter att ha angett den inkluderade variabeln.

Kolumnen för den inkluderade variabeln kommer att kallas den lösa kolumnen.

Strängen för den exkluderade variabeln kommer att kallas den lösa strängen.

Skärningen mellan en tillåtande kolumn och en rad definierar ett tillåtande element (RE).

Så här definierar du en utesluten variabel:

dividera de högra delarna av alla grundläggande variabler (förutom raden) med motsvarande positiva koefficienter för den lösa kolumnen;

välj det minsta av de erhållna förhållandena.

Det är inte tillåtet att dividera med "0" och ett negativt värde, eftersom detta leder till frånvaron av en skärande vertex eller till en vertex utanför ODT.

För att flytta till en intilliggande vertex är det nödvändigt att bilda en övergångsmatris B(0), som kommer att bestämma förhållandet mellan ST(0) och ST(1): ST(1) = B(0) ST(0).

För en godtycklig kvadratisk matris med dimensionen n, som har enhetsorter som (n - 1) kolumner, arrangerade i enlighet med enhetsorterna för identitetsmatrisen, och en godtycklig kolumn med ett element som inte är noll på huvuddiagonalen, invers matrisär enligt följande regel:

Varje element i j-kolumnen delas med RE och ändrar tecken till det motsatta, förutom det lösande elementet.

Konstgjord initial grund. M - metod.

Om den initiala begränsningen skrivs i form av likhet "=" eller har tecknet "", är det omöjligt att omedelbart få en acceptabel initial grundläggande lösning, eftersom när du skriver problemet i standardformuläret, efter att ha introducerat ytterligare variabler, en variant kan visa sig när de resulterande ekvationerna inte tillåter en att bilda initialt tillåten bas i form av enhetsvektorer.

I det här fallet, för att hitta den initiala tillåtna basen, introduceras ytterligare artificiella variabler. Artificiella variabler är inte relaterade till innehållet i uppgiften, deras introduktion är endast tillåten om motsvarande beräkningsschema ger en optimal lösning där alla artificiella variabler kommer att vara lika med noll.

Variablerna R bestämmer den initiala tillåtna basen ur synvinkeln av en eventuell ytterligare övergång till en av ODT:s hörn. För användning av artificiella variabler i den objektiva funktionen införs ett straff M. I problemet med att maximera M, negativ (M)<<0), в задаче минимизации М положительное (М>>0).

Egenskap M: När man adderar (subtraherar) med valfritt ändligt värde som bestämmer vilket värde som helst som var och en av variablerna i den ursprungliga LLP kan ta, ändras inte dess värde (variabel M), nämligen,

Formel (1.2), restriktioner för variablers icke-negativitet (ja, nej) - formel (1.3) (1.1) i = 1, ... m (1.2) (1.3) Algoritmen för att lösa linjära programmeringsproblem kräver att man tar med dem till kanonisk form när den objektiva funktionen ...

I praktiken ges begränsningar i ett linjärt programmeringsproblem ofta inte av ekvationer, utan av ojämlikheter.

Låt oss visa hur man kan gå från ett problem med ojämlikhetsbegränsningar till huvudproblemet med linjär programmering.

Låt det finnas ett linjärt programmeringsproblem med variabler, där de begränsningar som läggs på variablerna har formen av linjära ojämlikheter. I vissa av dem kan olikhetstecknet vara och andra (den andra typen reduceras till den första genom en enkel förändring av tecknet för båda delarna). Därför sätter vi alla ojämlikhetsbegränsningar i standardformuläret:

Det krävs att hitta en sådan uppsättning icke-negativa värden som skulle tillfredsställa ojämlikheter (4.1), och dessutom skulle minimera den linjära funktionen:

Från problemet som ställs på detta sätt är det lätt att övergå till huvudproblemet med linjär programmering. Faktum är att vi introducerar notationen:

var finns några nya variabler, som vi kommer att kalla "ytterligare". Enligt villkor (4.1) måste dessa tilläggsvariabler, som de borde vara, vara icke-negativa.

Således står vi inför problemet med linjär programmering i följande formulering: att hitta sådana icke-negativa värden på variablerna att de uppfyller ekvationssystemet (4.3) och samtidigt minimera den linjära funktionen hos dessa variabler:

Som du kan se har vi framför oss i sin rena form huvudproblemet med linjär programmering (LPP). Ekvationerna (4.3) ges i den form som redan är löst med avseende på grundvariablerna, vilka uttrycks i termer av fria variabler. Funktionen L uttrycks endast i termer av de "initiella" variablerna (koefficienterna för de "ytterligare" variablerna i den är lika med noll).

Således har vi reducerat problemet med linjär programmering med ojämlikhetsbegränsningar till huvudproblemet med linjär programmering, men med ett större antal variabler än vad som ursprungligen fanns i problemet.

Exempel 1 Det finns ett linjärt programmeringsproblem med ojämlikhetsbegränsningar: hitta icke-negativa värden för variabler som uppfyller villkoren

och minimera den linjära funktionen

Det är nödvändigt att reducera detta problem till formen av OLP.

Lösning. Vi för in ojämlikheter (4.4) till standardformuläret;

Vi introducerar ytterligare variabler:

Uppgiften är att hitta icke-negativa värden för variablerna

uppfylla ekvationerna (4.6) och minimera den linjära funktionen (4.5).

Vi har visat hur det är möjligt att gå från ett linjärt programmeringsproblem med ojämlikhetsbegränsningar till ett problem med likhetsbegränsningar (ELP). Den omvända övergången är alltid möjlig - från LLP till problemet med ojämlikhetsbegränsningar. Om vi ​​i det första fallet ökade antalet variabler, kommer vi i det andra fallet att minska det, eliminera de grundläggande variablerna och lämna bara de fria.

Exempel 2. Det finns ett linjärt programmeringsproblem med Equality Constraints (OLP):

och funktionen som ska minimeras

Det krävs att skriva det som ett linjärt programmeringsproblem med ojämlikhetsbegränsningar.

Lösning. Sedan väljer vi två av variablerna som fria. Observera att variabler inte kan väljas som fria, eftersom de är relaterade till den första av ekvationerna (4 7): värdet på en av dem bestäms helt av värdet på den andra, och de fria variablerna måste vara oberoende

Av samma anledning är det omöjligt att välja variabler som fria (de är förbundna med den andra ekvationen). Vi väljer som fria variabler och uttrycker resten i termer av dem:

Eftersom villkor (4 9) kan ersättas med ojämlikheter:

Låt oss överföra uttrycket för den linjära funktionen L till fria variabler. Substituera i L istället för och deras uttryck (4.9). skaffa sig.

LINJÄR PROGRAMMERINGSMODELL

1 Matematisk beskrivning av den linjära programmeringsmodellen

2 Metoder för att implementera linjära programmeringsmodeller

3 Dubbel linjär programmeringsproblem

Linjär programmeringsmodell(LP) sker om i det studerade systemet (objektet) begränsningarna för variabler och den objektiva funktionen linjär.

LP-modeller används för att lösa två huvudtyper av tillämpade problem:

1) optimal planering inom alla områden av mänsklig aktivitet - social, ekonomisk, vetenskaplig, teknisk och militär. Till exempel med optimal produktionsplanering: fördelning av ekonomiska, arbetskraft och andra resurser, försörjning av råvaror, lagerhantering etc.

2) transportproblemet (att hitta den optimala planen för olika typer av transporter, den optimala planen för fördelning av olika medel över objekt för olika ändamål, etc.)

MATEMATISK BESKRIVNING AV DEN LINJÄRA PROGRAMMERINGSMODELLEN

Det krävs att hitta icke-negativa värden för variabler

uppfylla linjära begränsningar i form av jämlikheter och ojämlikheter

,

var - givna siffror,

och tillhandahålla ett extremum av den linjära objektivfunktionen

,

där ges siffror, som skrivs som

Acceptabel lösning vilken uppsättning som helst kallas , som uppfyller villkoren.

Domän av tillåtna lösningarär uppsättningen av alla tillåtna lösningar.

Optimal lösning
, för vilka .

Anmärkningar

1. Den reducerade LP-modellen är allmän. Det finns också standard- och kanonisk former av LP-modeller.

2. Tillvarovillkor implementering av LP-modellen:

– Uppsättningen av tillåtna lösningar är inte tom.

- objektiv funktion begränsat av (åtminstone uppifrån när man söker efter ett maximum och underifrån när man söker efter ett minimum).

3.LP bygger på två satser

Sats 1. Mycket av G, definierad av systemet av begränsningar i formen, är en konvex sluten uppsättning ( konvex polyeder in med hörnpunkter - toppar.)

Sats 2. Linjär form , definierad på en konvex polyeder

j=1,2,…,s

i=s+1,s+2,…, m,

når ett extremum vid en av hörnen på denna polyeder.

Denna sats kallas den linjära formen extremumsatsen.

I enlighet med Weierstrass-satsen är den optimala lösningen unik och är ett globalt extremum.

Det finns ett generellt analytiskt förhållningssätt till implementeringen av LP-modellen - simplexmetoden. När man löser linjära programmeringsproblem finns det ofta ingen lösning. Detta händer av följande skäl.

Låt oss illustrera det första skälet med ett exempel.

Om en sådan anledning säger de att begränsningarna är inkonsekventa. Domänen för tillåtna lösningar är den tomma uppsättningen.

Det andra skälet kommenteras av följande exempel:

I det här fallet är området med möjliga lösningar inte avgränsat från ovan. Området för tillåtna lösningar är inte begränsat.

I enlighet med traditionerna för linjär programmering kommer vi att ge LP-problemet en ekonomisk tolkning. Låt oss ha det m resurstyper. Nummer på typresurs j lika med . Dessa resurser behövs för att producera n typer av varor. Låt oss beteckna mängden av dessa varor med symbolerna respektive. Objekttyp i kostar . Tillverkning av varutyp i bör begränsas till respektive. För tillverkning av en enhet av varor av typen i förbrukad resurstyp j. Det är nödvändigt att fastställa en sådan plan för produktion av varor ( ) så att deras totala kostnad är minimal.

Linjära programmeringsproblem som används för att optimera funktionen hos verkliga objekt innehåller ett betydande antal variabler och begränsningar. Detta gör det omöjligt att lösa dem med grafiska metoder. Med ett stort antal variabler och begränsningar används algebraiska metoder, som är baserade på iterativa beräkningsprocedurer. Inom linjär programmering har många algebraiska metoder utvecklats som skiljer sig åt i sättet att konstruera en initial genomförbar lösning och i förutsättningarna för att gå från en iteration till en annan. Alla dessa metoder är dock baserade på allmänna teoretiska principer.

Allmänheten i de huvudsakliga teoretiska bestämmelserna leder till att algebraiska metoder för att lösa linjära programmeringsproblem i stort sett liknar varandra. I synnerhet kräver nästan vilken som helst av dem preliminär reduktion av ett linjärt programmeringsproblem till en standard (kanonisk) form.

Algebraiska metoder för att lösa LP-problemet börjar med att reducera det till standardform (kanonisk).:

,

,

i=1,..,n;j=1,..,m.

Alla linjära programmeringsproblem kan reduceras till en standardform. Jämförelse av den allmänna modellen med den kanoniska modellen gör det möjligt för oss att dra slutsatsen att för att reducera LP-problemet till standardformen är det nödvändigt för det första att gå från systemet av ojämlikheter till jämlikheter, och för det andra att transformera alla variabler så att att de är icke-negativa.

Övergången till likheter utförs genom att lägga till en icke-negativ restvariabel till vänster sida av begränsningarna för olikheter av typ , och subtrahera från den vänstra sidan av en icke-negativ överskottsvariabel för olikheter av typ . Till exempel ojämlikhet när man går över till standardformuläret omvandlas det till jämlikhet och ojämlikheten - till jämställdhet . I det här fallet är både restvariabeln och överskottsvariabeln icke-negativa.

Det antas att den högra sidan av ojämlikheterna är icke-negativ. Annars kan detta uppnås genom att multiplicera båda sidor av ojämlikheten med "-1" och ändra dess tecken till det motsatta.

Om variabeln i det ursprungliga linjära programmeringsproblemet inte är begränsad i tecken, kan den representeras som skillnaden mellan två icke-negativa variabler , var .

En viktig egenskap hos variabler är att för varje tillåten lösning kan endast en av dem ta ett positivt värde. Detta betyder att om , då och vice versa. Därför kan den betraktas som en residual, men - som en redundant variabel.

Exempel Låt ett linjärt programmeringsproblem ges:

,

.

Du måste ta den till en standardform. Observera att den första olikheten i det ursprungliga problemet har tecknet , därför är det nödvändigt att införa restvariabeln i den. Som ett resultat får vi .

Den andra olikheten har ett tecken och för omvandling till standardformen kräver det införandet av en redundant variabel , utför denna operation får vi .

Variabeln är inte heller begränsad i tecken. Därför, både i den objektiva funktionen och i båda begränsningarna, måste den ersättas med skillnaden . Efter att ha utfört substitutionen får vi ett linjärt programmeringsproblem i standardform, motsvarande det ursprungliga problemet:

.

Problemet med linjär programmering, skrivet i standardform, är problemet med att hitta extremumet av den objektiva funktionen på uppsättningen vektorer som är lösningar till systemet med linjära ekvationer, med hänsyn till villkoren för icke-negativitet. Som ni vet kan ett system av linjära ekvationer inte ha några lösningar, ha en enda lösning eller ha ett oändligt antal lösningar. Optimering av målfunktionen är endast möjlig om systemet har oändlig många lösningar. Ett system av linjära ekvationer har ett oändligt antal lösningar om det är konsekvent (huvudmatrisens rang är lika med den utökade) och om huvudmatrisens rang är mindre än antalet okända.

Låt rangordningen för begränsningssystemmatrisen vara lika med m. Det betyder att matrisen har minst en mindre m ordningen är inte lika med noll. Utan förlust av generalitet kan vi anta att minor är placerad i det övre vänstra hörnet av matrisen. Detta kan alltid uppnås genom att ändra numreringen av variablerna. Detta icke-noll rang mindre m kallas basen. Låt oss göra ett system från första början m systemets ekvationer, skriv det så här:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .