Konvexa uppsättningar och deras egenskaper. För att studera egenskaperna hos en konvex mängd är det nödvändigt att ge en strikt definition av en konvex mängd. Tidigare definierades en konvex uppsättning som en uppsättning som tillsammans med två av dess punkter innehåller ett segment som förbinder dem.

En generalisering av konceptet med ett segment för flera punkter är deras konvexa linjära kombination.

Punkt X kallas konvex linjär kombination poäng, om villkoren är uppfyllda

Uppsättningen av punkter är konvex, om den, tillsammans med två av dess punkter, innehåller deras godtyckliga konvexa, linjära kombination.

Vi kan bevisa följande sats om representationen av en konvex polyeder.

Sats 1.1. En konvex n-dimensionell polyeder är en konvex linjär kombination av dess hörnpunkter.

Av sats 1.1 följer att en konvex polyeder genereras av dess hörnpunkter eller hörn: ett segment med två punkter, en triangel med tre, en tetraeder med fyra punkter, etc. Samtidigt är ett konvext polyedriskt område, som är en obegränsad mängd, inte unikt definierat av sina hörnpunkter: någon av dess punkter kan inte representeras som en konvex linjär kombination av hörnpunkter.

Egenskaper för ett linjärt programmeringsproblem. Tidigare övervägdes olika former av ett linjärt programmeringsproblem och det visades att vilket linjärt programmeringsproblem som helst kan representeras som ett generellt eller kanoniskt problem.

För att underbygga egenskaperna hos det linjära programmeringsproblemet och metoder för att lösa det, är det tillrådligt att överväga ytterligare två typer av notation av det kanoniska problemet.

Matrisinspelningsformulär:

Här MED– radmatris, A– systemmatris, X– matriskolumn av variabler, I– matriskolumn med gratismedlemmar:

Vektorform av inspelning:

där vektorerna motsvarar kolumnerna med koefficienter för de okända.

Det var formulerat ovan, men inte bevisat i allmän syn nästa sats.

Sats 1.2. Uppsättningen av alla möjliga lösningar på systemet av begränsningar för ett linjärt programmeringsproblem är konvex.

Bevis: Låta - två möjliga lösningar av PLP, givna i matrisform. Sedan . Låt oss överväga en konvex linjär kombination av lösningar, dvs.

och visa att det också är en tillåten systemlösning (1.3). Verkligen

dvs. lösning X uppfyller system (1.3). Men sedan dess X>0, dvs. lösningen uppfyller icke-negativitetsvillkoret.

Så det har bevisats att uppsättningen av alla möjliga lösningar på ett linjärt programmeringsproblem är konvex, eller mer exakt, den representerar en konvex polyeder eller en konvex polyedrisk region, som vi vidare kommer att kalla med en term - polyeder av lösningar.

Svaret på frågan vid vilken punkt av polyedern av lösningar är möjligt optimal lösning linjärt programmeringsproblem ges i följande grundläggande sats.

Sats 1.3. Om ett linjärt programmeringsproblem har en optimal lösning, tar den linjära funktionen sitt maximala värde vid en av hörnpunkterna i lösningspolyedern. Om en linjär funktion tar ett maximalt värde vid mer än en hörnpunkt, så tar den det vid vilken punkt som helst som är en konvex linjär kombination av dessa punkter.

Bevis: Vi kommer att anta att lösningspolyedern är avgränsad. Låt oss beteckna dess hörnpunkter med , och den optimala lösningen är klar X*. Sedan F(X*)³ F(X) för alla punkter X polyeder av lösningar. Om X*är en hörnpunkt, är den första delen av satsen bevisad.

Låt oss låtsas som det X*är alltså inte en hörnpunkt baserat på sats 1.1 X* kan representeras som en konvex linjär kombination av hörnpunkterna i lösningspolyedern, dvs.

Därför att F(X)är en linjär funktion får vi

I denna nedbrytning väljer vi det maximala bland värdena. Låt det motsvara hörnpunkten Xk(1 £ k£ R); låt oss beteckna det med M, de där. . Låt oss ersätta varje värde i uttrycket (1.5) med detta maximala värde M. Sedan

Genom antagande X* är den optimala lösningen, därför å ena sidan, men å andra sidan har det bevisats att
F(X*)£ M, därför, , var Xk– hörnpunkt. Så det finns en hörnpunkt Xk, där den linjära funktionen tar sitt maximala värde.

För att bevisa den andra delen av satsen, låt oss anta att objektivfunktionen tar ett maximalt värde vid mer än en hörnpunkt, till exempel vid punkter , Var , Sedan

Låta X– en konvex linjär kombination av dessa hörnpunkter, dvs.

I det här fallet, med tanke på att funktionen F(X)– linjär, får vi

de där. linjär funktion F tar det maximala värdet vid en godtycklig punkt X, som är en konvex linjär kombination av hörnpunkter.

Kommentar. Kravet på att lösningspolyedern är avgränsad i satsen är väsentligt, eftersom i fallet med ett obegränsat polyederområde, som noterats i sats 1.1, inte varje punkt i ett sådant område kan representeras av en konvex linjär kombination av dess hörnpunkter.

Den beprövade satsen är grundläggande, eftersom den indikerar ett grundläggande sätt att lösa linjära programmeringsproblem. I själva verket, enligt detta teorem, istället för att studera en oändlig uppsättning möjliga lösningar för att hitta den önskade optimala lösningen bland dem, är det nödvändigt att studera endast ett ändligt antal hörnpunkter i lösningspolyedern.

Nästa sats ägnas åt den analytiska metoden att hitta hörnpunkter.

Sats 1.4. Varje tillåten grundlösning av ett linjärt programmeringsproblem motsvarar en hörnpunkt i lösningspolyedern, och vice versa, till varje hörnpunkt i lösningspolyedern motsvarar en tillåten baslösning.

Bevis: Låt vara en tillåten grundläggande lösning av systemet med begränsningar av LLP (1.4), där den första T komponenten är huvudvariablerna och resten p - t komponent – ​​icke-huvudvariabler lika med noll i grundlösningen (om så inte är fallet kan motsvarande variabler numreras om). Låt oss visa det X

Låt oss anta motsatsen, dvs. Vad Xär inte en hörnpunkt. Peka sedan X kan representeras av den inre punkten av ett segment som förbinder två olika som inte sammanfaller med X, poäng

med andra ord en konvex linjär kombination av punkter polyeder av lösningar, dvs.

var (vi antar att , för annars är det meningen X sammanfaller med poängen X 1 eller X 2).

Låt oss skriva vektorlikheten (1.6) i koordinatform:

Därför att alla variabler och koefficienter är icke-negativa, då från den sista p-t jämlikheter följer att , dvs. i beslut X 1 , X 2 och X ekvationssystem (1.4) värden p - t komponenter är lika med noll i detta fall. Dessa komponenter kan betraktas som värdena för icke-primära variabler. Men värdena för icke-grundläggande variabler bestämmer unikt värdena för de viktigaste, därför,

Alltså allt P komponent i lösningar X 1 , X 2 och X sammanfaller, och därför punkterna X 1 och X 2 slå samman, vilket motsäger antagandet. Därav, X– hörnpunkt för lösningspolyedern.

Låt oss bevisa det omvända påståendet. Låta vara hörnpunkten för lösningspolyedern och dess första T koordinaterna är positiva. Låt oss visa det X– godtagbar grundlösning. är inte en hörnpunkt, vilket motsäger villkoret. Därför är vårt antagande felaktigt, d.v.s. vektorerna är linjärt oberoende och Xär en godtagbar grundläggande lösning på problemet (1.4).

En viktig följd följer direkt av satserna 1.3 och 1.4: om ett linjärt programmeringsproblem har en optimal lösning, så sammanfaller det, enligt minst, med en av dess tillåtna baslösningar.

Så, optimalt linjär funktion Linjära programmeringsproblem bör sökas bland ett ändligt antal av dess genomförbara grundläggande lösningar.

Låt oss överväga det huvudsakliga linjära programmeringsproblemet (LPLP): hitta icke-negativa värden för variablerna x1, x2, ..., xn, som uppfyller m villkor - likheter

och maximera den linjära funktionen av dessa variabler

För enkelhetens skull antar vi att alla villkor (1) är linjärt oberoende (r=m), och vi kommer att föra vårt resonemang under detta antagande.

Låt oss kalla en tillåten lösning av OLP vilken som helst uppsättning av icke-negativa värden x1, x2, ..., xn som uppfyller villkoren (1). Låt oss kalla optimal den av de tillåtna lösningarna som maximerar funktionen (2). Vi måste hitta den optimala lösningen.

Har detta problem alltid en lösning? Nej inte alltid.

ZLP är olöslig (har inte en optimal lösning):

På grund av begränsningssystemets inkompatibilitet. De där. systemet har inte en enda lösning, som visas i figur 1.

Figur 1 - Inkonsekvens av begränsningssystemet

På grund av den obegränsade objektivfunktionen på uppsättningen av lösningar. Med andra ord, när man löser LLP vid max, tenderar värdet på objektivfunktionen till oändlighet, och i fallet med LLP vid min - till minus oändlighet, som visas i figur 2.

Figur 2 - Obegränsning av objektivfunktionen på uppsättningen av lösningar

ZLP är lösbart:

Lösningsuppsättningen består av en enda punkt. Det är också optimalt, som visas i figur 3.

Figur 3 - Uppsättningen av lösningar består av en punkt

Den enda optimala lösningen för ZLP. Den räta linjen som motsvarar objektivfunktionen vid gränsläget skär uppsättningen lösningar vid en punkt, som visas i figur 4.

Figur 4 - Den enda optimala lösningen

Den optimala lösningen för ZLP är inte unik. Vektor N är vinkelrät mot en av sidorna av lösningsmängden. I det här fallet är vilken punkt som helst på segmentet AB optimal, som visas i figur 5.

Figur 5 - Den optimala lösningen är inte unik

Lösning av linjära programmeringsproblem med simplexmetoden

Simplexmetoden är en algoritm för att lösa ett LP-problem som implementerar en uppräkning av hörnpunkterna i regionen av genomförbara lösningar i riktning mot att förbättra värdet av objektivfunktionen C. Simplexmetoden är den huvudsakliga inom linjär programmering.

Användningen av denna metod i ett diplomprojekt för att lösa LP-problemet beror på följande faktorer:

Metoden är universell, tillämpbar på alla linjära programmeringsproblem i kanonisk form;

Metodens algoritmiska karaktär gör att den framgångsrikt kan programmeras och implementeras med hjälp av tekniska medel.

Det yttersta av den objektiva funktionen uppnås alltid i hörnpunkterna i regionen av genomförbara lösningar. Först och främst hittas någon genomförbar initial (referens)lösning, d.v.s. valfri hörnpunkt i regionen av genomförbara lösningar. Metodens förfarande låter dig svara på frågan om denna lösning är optimal. Om ja, då är problemet löst. Om "nej" görs en övergång till den intilliggande hörnpunkten av regionen med genomförbara lösningar, där värdet av den objektiva funktionen förbättras. Processen att räkna upp hörnpunkterna i området med möjliga lösningar upprepas tills en punkt hittas som motsvarar den objektiva funktionens extremum.

Eftersom antalet hörn av polyedern är begränsat, är det garanterat i ett ändligt antal steg att hitta det optimala värdet eller fastställa det faktum att problemet är olösligt.

Systemet av begränsningar här är ett system av linjära ekvationer där antalet okända mer kvantitet ekvationer. Om systemets rangordning är lika, är det möjligt att välja okända som uttrycks i termer av återstående okända. För att vara säker, antas det vanligtvis att de första på varandra följande okända är valda. Dessa okända (variabler) kallas grundläggande, resten är gratis. Antalet basvariabler är alltid lika med antalet begränsningar.

Genom att tilldela vissa värden till fria variabler och beräkna värdena för de grundläggande (uttryckta i termer av fria), erhålls olika lösningar på systemet med begränsningar. Av särskilt intresse är de lösningar som erhålls i fallet när de fria variablerna är lika med noll. Sådana lösningar kallas grundläggande. En grundlösning kallas en tillåten grundlösning eller stödlösning om värdena på dess variabler är icke-negativa. Den uppfyller alla restriktioner.

Genom att ha ett system av begränsningar, finns alla grundläggande lösningar på detta system. Om den första grundläggande lösningen som hittas visar sig vara genomförbar, kontrolleras den för optimalitet. Om det inte är optimalt så görs en övergång till en annan genomförbar grundlösning.

Simplexmetoden garanterar att med denna nya lösning kommer den linjära formen, om den inte når det optimala, att närma sig den. De gör samma sak med den nya genomförbara baslösningen tills de hittar en lösning som är optimal.

Om den första grundlösningen som hittas visar sig vara oacceptabel, görs med simplexmetoden en övergång till andra baslösningar, tills baslösningen vid något lösningssteg visar sig vara acceptabel, eller en slutsats kan dras om inkonsekvensen av begränsningssystemet.

Således är tillämpningen av simplexmetoden uppdelad i två steg:

Att hitta en acceptabel grundläggande lösning på ett system av begränsningar eller fastställa faktumet av dess inkonsekvens;

Att hitta den optimala lösningen när det gäller kompatibilitet med begränsningssystemet.

Algoritmen för att gå till nästa genomförbara lösning är som följer:

I raden av koefficienter för objektivfunktionen väljs det minsta negativa talet när man hittar maximum. Koefficientens serienummer är . Om det inte finns någon, är den ursprungliga grundlösningen optimal;

Bland elementen i matrisen med kolumnnumret (denna kolumn kallas den ledande eller lösa kolumnen) väljs positiva element. Om det inte finns några, är den objektiva funktionen obegränsad i intervallet av tillåtna värden för variablerna och problemet har inga lösningar;

Bland de valda elementen i den ledande kolumnen i matrisen väljs den för vilken värdet på förhållandet mellan motsvarande fria term och detta element är minimalt. Detta element kallas ledande, och linjen där det är beläget kallas ledande;

Den grundläggande variabeln som motsvarar raden i det ledande elementet måste överföras till kategorin fria, och den fria variabeln som motsvarar kolumnen i det ledande elementet måste anges i antalet grundläggande. En ny lösning konstrueras som innehåller nya antal grundläggande variabler.

Villkor för planens optimalitet när man löser problemet maximalt: det finns inga negativa element bland koefficienterna för den objektiva funktionen.

Optimering av linjära modeller i MS Excel genomförs simplex metod- målmedvetet sökande efter referenslösningar till ett linjärt programmeringsproblem. Simplexmetodens algoritm handlar om att konstruera en konvex polyeder i ett flerdimensionellt utrymme och sedan räkna upp dess hörn för att hitta ett extremvärde objektiv funktion.

Effektiva medel linjär programmering utgör grunden för både heltals- och olinjär programmering för att lösa mer komplexa optimeringsproblem. Dessa metoder kräver dock längre beräkningstider.

Efterföljande föreläsningar kommer att diskutera i detalj exempel på att lösa typiska optimeringsproblem och fatta förvaltningsbeslut med hjälp av MS Excel-tillägget "Sök efter en lösning". De uppgifter som bäst löses med detta verktyg har tre huvudegenskaper:

• det finns ett enda mål, funktionellt relaterat till andra parametrar i systemet, som måste optimeras (för att hitta dess maximum, minimum eller ett visst numeriskt värde);
• det finns begränsningar, vanligtvis uttryckta i form av ojämlikheter (till exempel får volymen av använda råvaror inte överstiga lagret av råvaror i lagret, eller så bör maskinens drifttid per dag inte vara mer än 24 timmar minus underhåll tid);
• det finns en uppsättning indatavariabelvärden som påverkar de optimerade värdena och begränsningarna.

Parametrarna för uppgifterna är begränsade till följande gränsindikatorer:

• antal okända – 200;
• antal formelrestriktioner för okända – 100;
• antalet begränsningsvillkor för okända är 400.

Algoritmen för att hitta optimala lösningar inkluderar flera steg:

• förarbete;
• felsöka lösningen;
• lösningsanalys.

Sekvensen av nödvändigt förberedande arbete som utförs vid lösning av problem med ekonomisk och matematisk modellering med MS Excel visas i blockschemat i figur 1.6.

Ris. 1.6.

Av de fem punkterna i den förberedande arbetsplanen är endast den femte punkten formaliserbar. Resten av arbetet kräver kreativitet – och olika människor kan göra det på olika sätt. Låt oss kort förklara kärnan i ordalydelsen av planpunkterna.

Vid inställning av problemet är målkoefficienterna och normaliserade koefficienter kända. I det föregående exemplet var koefficienterna som bildar den objektiva funktionen värdena för normaliserad vinst per hylla av typ ( ) och en hylltyp ( ). De normaliserade koefficienterna var normerna för materialförbrukning och maskintid per hylla av varje typ. Matrisen såg ut så här:

Dessutom är resursvärdena alltid kända. I det föregående exemplet var detta en veckas tillgång på brädor och möjligheten att använda maskintid: , . Ofta i problem måste värdena på variabler begränsas. Därför är det nödvändigt att bestämma de nedre och övre gränserna för intervallet för deras förändringar.

Således, i dialogrutan för optimeringsprogrammet "Sök efter en lösning" måste vi ställa in följande målalgoritm:

Målfunktionen är lika med produkten av vektorn av önskade variabelvärden med vektorn av målkoefficienter

De normaliserade koefficienterna för vektorn av erforderliga variabelvärden bör inte överstiga värdet för den givna resursvektorn

Variabelvärdena måste ligga inom de angivna gränserna för antalet initiala element i systemet

Antal initiala element i systemet

Antal angivna resurstyper

Felsökning av lösningen är nödvändig när programmet visar ett meddelande om negativa resultat (Figur 1.7):

Ris. 1.7.

• om en acceptabel lösning inte erhålls, justera sedan källdatamodellen;
• om inte mottaget optimal lösning, inför sedan ytterligare begränsningar.

Programfrågorna optimal lösning endast för en modell av det verkliga problemet, och inte en lösning på själva problemet. Vid konstruktionen av modellen gjordes olika förenklade antaganden om den verkliga situationen. Detta gjorde det möjligt att formalisera processen och ungefär visa verkliga kvantitativa samband mellan systemparametrarna och målet. Och om de verkliga parametrarna skiljer sig från de som ingår i modellen, hur kommer lösningen då att förändras? För att ta reda på detta görs en analys av modelllösningen innan ett ledningsbeslut fattas.

Analys optimal lösning, inbyggd i programmet, representerar det sista steget av matematisk modellering av ekonomiska processer. Det möjliggör en djupare kontroll av modellens överensstämmelse med processen, såväl som tillförlitligheten hos den optimala lösningen. Det är baserat på data optimal lösning och rapporter som ges i "Sök efter en lösning". Men det utesluter eller ersätter inte den traditionella analysen av planen ur ett ekonomiskt perspektiv innan ett förvaltningsbeslut fattas.

Ekonomisk analys har följande mål:

• bestämning av möjliga konsekvenser i systemet som helhet och dess element vid ändring av en modellparameter;
• bedömning av stabiliteten hos den optimala planen för förändringar i enskilda parametrar av problemet: om den inte är stabil mot förändringar i de flesta parametrar, minskas garantin för dess genomförande och uppnående av det beräknade optimala;
• utföra variantkalkyler och erhålla nya planalternativ utan att lösa problemet på nytt från det ursprungliga underlaget med hjälp av justeringar.

Möjliga analysmetoder presenteras i diagrammet i figur 1.8.

Efter att ha erhållit den optimala lösningen analyseras den utifrån de mottagna rapporterna. Stabilitetsanalys- studie av inverkan av förändringar i individuella modellparametrar på indikatorerna för den optimala lösningen. Gränsanalys- analys av tillåtna ändringar i den optimala planen, där planen förblir optimal.

Med tanke på ansvaret att acceptera ekonomiska ledningsbeslut, måste chefen se till att den resulterande optimala planen är den enda korrekta. För att göra detta, baserat på modellen, är det nödvändigt att få svar på följande frågor:

• "vad händer om..."
• "vad krävs för att..."

Analys för att besvara den första frågan kallas variantanalys; analys för att besvara den andra frågan kallas skräddarsydda lösningar.

Variantanalys kan vara av följande typer:

• Parametrisk- analys, som består i att lösa ett problem för olika värden av en viss parameter.
• Strukturanalys- när en lösning på ett optimeringsproblem söks under en annan struktur av restriktioner.
• Multikriterieanalysär en lösning på ett problem med hjälp av olika objektiva funktioner.
• Analys med villkorad initial data- när de ursprungliga uppgifterna som används för att lösa ett problem beror på efterlevnaden av ytterligare villkor.

Efter analysen bör resultaten presenteras i grafisk form och en rapport bör sammanställas med rekommendationer för att fatta beslut med hänsyn till den specifika ekonomiska situationen.

För närvarande innehåller utbildningsprogrammet för specialiteter relaterade till ekonomi, ekonomi och ledning en disciplin som kallas "Methods of Optimal Decisions". Inom denna disciplin studerar eleverna den matematiska sidan av optimering, operationsforskning, beslutsfattande och modellering. huvud funktion Denna disciplin bestäms av den gemensamma studien av matematiska metoder med deras tillämpning för att lösa ekonomiska problem.

Optimeringsuppgifter: allmän information

Om vi ​​betraktar det allmänna fallet, så är meningen med optimeringsproblemet att hitta den så kallade optimala lösningen som maximerar (minimerar) den objektiva funktionen under vissa begränsningsvillkor.

Beroende på funktionernas egenskaper kan optimeringsproblem delas in i två typer:

• linjärt programmeringsproblem (alla funktioner är linjära);
• olinjärt programmeringsproblem (minst en av funktionerna är inte linjär).

Speciella fall av optimeringsproblem är fraktionerad-linjära, dynamiska och stokastiska programmeringsproblem.

De mest studerade optimeringsproblemen är linjära programmeringsproblem (LPP), vars lösningar endast tar heltalsvärden.

PPP: formulering, klassificering

Det linjära programmeringsproblemet i det allmänna fallet består av att hitta minimum (maximum) av en linjär funktion under vissa linjära begränsningar.

En allmän ZLP är ett formproblem

under restriktioner

var är variablerna, är de givna reella talen, är den objektiva funktionen, är problemplanen, (*)-(***) är begränsningarna.

En viktig egenskap hos ZLP är att den yttersta delen av den objektiva funktionen uppnås vid gränsen av området för genomförbara lösningar.

Praktiska ekonomiska tillämpningar av optimala lösningsmetoder finns för att lösa problem av följande typer:

• problem med blandningar (d.v.s. planering av produkternas sammansättning);
• problem med optimal resursallokering vid produktionsplanering;

PAP: exempel

Blandningsproblem

Lösningen på problemet med blandningar består i att hitta den billigaste uppsättningen, bestående av vissa utgångsmaterial som ger en blandning med önskade egenskaper.

Resursallokeringsproblem

Företaget producerar n olika produkter, vars produktion kräver m olika typer av resurser. Reserverna av använda resurser är begränsade och uppgår till resp b 1, b 2,…, b m c.u. Dessutom är teknologiska koefficienter kända en ij, som visar hur många enheter i-th resurs krävs för att producera en produktenhet j-th typen (). Vinsten som ett företag får vid försäljning av en produkt j-th typen, uppgår till c j monetära enheter Det är nödvändigt att utarbeta en plan för produktion av produkter, vars vinst under genomförandet kommer att vara störst.

Problem med blandningar och resursfördelning skrivs ofta i tabellform.

Resurser	Behov			Reserver
	B 1	…	Bn
A 1				b 1
…				…
Am				b m
Vinst	c 1	…	c n

Blandnings- och resursallokeringsproblem kan lösas på flera sätt:

• grafisk metod (vid ett litet antal variabler i matematisk modell);
• simplex-metod (om antalet variabler i en matematisk modell är fler än två).

Transportproblemet avser en klass av uppgifter som har en viss specifik struktur. Det enklaste transportproblemet är problemet med att transportera en produkt till destinationer från avgångsställen vid minimikostnader för transport av alla produkter.

För tydlighetens skull och för att underlätta uppfattningen skrivs tillståndet för transportproblemet vanligtvis i följande tabell:

I allmänhet utförs att lösa ett transportproblem i flera steg:

• Etapp I: konstruktion av den ursprungliga referensplanen;
• Steg II: kontroll av referensplanen för optimalitet;
• Steg III: förtydligande av referensplanen om den inte är optimal.

Det finns flera metoder för att erhålla den initiala referensplanen, till exempel nordvästra hörnmetoden, Vogelmetoden och minimikostnadsmetoden.

Planen kontrolleras för optimalitet med hjälp av den potentiella metoden:

- för ockuperade celler,
- för lediga celler.

Om planen inte är optimal byggs en cykel och transporterna omfördelas.

Slutsats

Det är inte möjligt att täcka hela teorin och praktiken för optimala lösningsmetoder inom ramen för en artikel, därför övervägs endast några punkter som gör att vi kan ge en allmän uppfattning om denna disciplin, problem och metoder för att lösa dem.

Dessutom är det bra att notera att för att kontrollera de erhållna lösningarna på optimeringsproblem kan du mycket effektivt använda tillägget "Solution Search" i MS Excel-paketet. Men det är faktiskt en annan historia, liksom en detaljerad övervägande av metoder för att lösa optimeringsproblem.

Här är flera läroböcker för att studera optimala lösningsmetoder:

1. Bandi B. Grunderna i linjär programmering: Trans. från engelska – M.: Radio och kommunikation, 1989. – 176 sid.
2. Kremer N.Sh. Operations Research in Economics: Proc. manual för universitet / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Friedman; Ed. prof. N.Sh. Kremer. – M.: ENHET, 2005. – 407 sid.

Lösning av anpassade optimeringsmetoder

Vi kan hjälpa dig att lösa eventuella problem med optimala lösningsmetoder. Du kan beställa lösningar på problem på vår hemsida. Du behöver bara ange deadline och bifoga filen med uppgiften. din beställning är gratis.

Linjär programmeringär en gren av matematiken som studerar metoder för att hitta minimum eller maximum av en linjär funktion av ett ändligt antal variabler, förutsatt att variablerna uppfyller ett ändligt antal begränsningar i form av linjära ekvationer eller linjära olikheter.

Således kan det allmänna linjära programmeringsproblemet (GLP) formuleras enligt följande.

Hitta värden för verkliga variabler för vilka objektiv funktion

tar ett minimivärde på den uppsättning punkter vars koordinater uppfyller begränsningssystem

Som bekant en ordnad samling av värden n variabler , , … representeras av en punkt i det n-dimensionella rummet. I det följande kommer vi att beteckna denna punkt X=( , , … ).

I matrisform kan det linjära programmeringsproblemet formuleras enligt följande:

, A– storleksmatris,

Punkt X=( , , … ), som uppfyller alla villkor, kallas giltig punkt . Uppsättningen av alla tillåtna poäng kallas giltigt område .

Optimal lösning (optimal plan) ett linjärt programmeringsproblem kallas en lösning X=( , , … ), som hör till det tillåtna området och för vilket den linjära funktionen F tar det optimala (högsta eller lägsta) värdet.

Sats. Uppsättningen av alla möjliga lösningar på systemet av begränsningar för ett linjärt programmeringsproblem är konvex.

Uppsättningen av punkter kallas konvex , om den, tillsammans med två av dess punkter, innehåller deras godtyckliga konvexa linjära kombination.

Punkt X kallad konvex linjär kombination poäng om villkoren är uppfyllda

Uppsättningen av alla möjliga lösningar på ett linjärt programmeringsproblem är en konvex polyedrisk region, som vi hädanefter kommer att kalla polyeder av lösningar .

Sats. Om ZLP har en optimal lösning, tar objektivfunktionen det maximala (minsta) värdet vid en av hörnen av lösningspolyedern. Om objektivfunktionen tar ett maximalt (minimum) värde vid mer än en punkt, så tar den detta värde vid vilken punkt som helst som är en konvex linjär kombination av dessa punkter.

Bland de många lösningarna i systemet m linjära ekvationer som beskriver polyhedronen av lösningar, de så kallade baslösningarna urskiljs.

Grundläggande lösning av systemet m linjära ekvationer med n variabler är en lösning där alla n-m icke-kärnvariabler är noll. I linjära programmeringsproblem kallas sådana lösningar tillåtna baslösningar (referensplaner).

Sats. Varje tillåten grundläggande lösning på ett linjärt programmeringsproblem motsvarar en spets av lösningspolyedern, och vice versa, till varje spets av lösningspolyedern motsvarar en tillåten grundlösning.

En viktig konsekvens följer av ovanstående satser:

Om ett linjärt programmeringsproblem har en optimal lösning, så sammanfaller det med åtminstone en av dess möjliga grundläggande lösningar.

Följaktligen måste det optimala för den linjära funktionen för målet för ett linjärt programmeringsproblem sökas bland det ändliga antalet av dess möjliga grundläggande lösningar.