1 lineær programmering. Lineære programmeringsmetoder

Anmærkning: Dette foredrag dækker en række emner, der er helliget lineær programmering som en af ​​grenene af matematisk programmering; formulerer især hovedtyperne af opgaver lineær programmering, afslører forskellene mellem disse opgaver og klassiske problemer matematisk analyse; introducerer forskellige former for registrering af disse opgaver, udfører deres formulering og undersøgelse af strukturen. Spørgsmålet om at løse lineære programmeringsproblemer ved hjælp af simpleksmetoden er mest udforsket.

1. Begrebet matematisk programmering

er en matematisk disciplin, hvor der udvikles metoder til at finde ekstreme værdier af en objektiv funktion blandt sættet af dets mulige værdier bestemt af begrænsninger.

Tilstedeværelsen af ​​begrænsninger gør problemerne fundamentalt forskellige fra de klassiske problemer med matematisk analyse med at finde ekstreme værdier af en funktion. Metoder til matematisk analyse til søgning ekstremum af funktionen i opgaver matematisk programmering vise sig at være uegnet.

At løse problemer matematisk programmering Særlige metoder og teorier er blevet udviklet og er under udvikling. Da løsning af disse problemer kræver at udføre en betydelig mængde beregninger, hvornår sammenlignende vurdering metoder stor betydning er givet til effektiviteten og bekvemmeligheden af ​​deres implementering på en computer.

Det kan betragtes som et sæt af uafhængige sektioner, der er involveret i undersøgelse og udvikling af metoder til at løse visse klasser af problemer.

Afhængigt af egenskaberne af den objektive funktion og begrænsningsfunktionen, alle problemer matematisk programmering er opdelt i to hovedklasser:

• lineære programmeringsproblemer,
• opgaver ikke-lineær programmering.

Hvis den objektive funktion og begrænsningsfunktionerne er lineære funktioner, så er det tilsvarende problem med at finde et ekstremum et lineært programmeringsproblem. Hvis mindst én af specificerede funktioner er ikke-lineær, så er det tilsvarende problem med at finde et ekstremum problemet ikke-lineær programmering.

2. Begrebet lineær programmering. Typer af lineære programmeringsproblemer

Lineær programmering(LP) – et af de første og mest grundigt studerede afsnit matematisk programmering. Nemlig lineær programmering var det afsnit, hvorfra selve disciplinen begyndte at udvikle sig" matematisk programmering". Udtrykket "programmering" i disciplinens titel har intet til fælles med udtrykket "programmering (dvs. kompilering af et program) til en computer" har intet at gøre med disciplinen " lineær programmering" opstod allerede før den tid, hvor computere begyndte at blive meget brugt til at løse matematiske, tekniske, økonomiske og andre problemer.

Begrebet " lineær programmering" opstod som følge af en unøjagtig oversættelse af det engelske "lineær programmering". En af betydningerne af ordet "programmering" er at lave planer, planlægge. Derfor ville den korrekte oversættelse af det engelske "lineær programmering" ikke være " lineær programmering", og "lineær planlægning", som mere præcist afspejler indholdet af disciplinen. Men vilkårene lineær programmering, ikke-lineær programmering, matematisk programmering etc. er blevet almindeligt accepterede i vor litteratur og vil derfor blive bevaret.

Så, lineær programmering opstod efter Anden Verdenskrig og begyndte at udvikle sig hurtigt, hvilket tiltrak sig opmærksomhed fra matematikere, økonomer og ingeniører på grund af muligheden for bred praktisk anvendelse såvel som matematisk harmoni.

Det kan man sige lineær programmering anvendelig til at løse matematiske modeller af de processer og systemer, der kan baseres på hypotesen om en lineær repræsentation af den virkelige verden.

Lineær programmering bruges til at løse økonomiske problemer, i opgaver som ledelse og produktionsplanlægning; i problemer med at bestemme optimal placering udstyr på søfartøjer, i værksteder; i problemer med at bestemme optimal plan godstransport (transportopgave); i problemer med optimal personalefordeling mv.

Lineært programmeringsproblem(LP), som det allerede fremgår af det, der blev sagt ovenfor, består i at finde minimum (eller maksimum) af en lineær funktion under lineære restriktioner.

Generel form problemet har formen: find under betingelserne

Sammen med den generelle form er de også meget brugt kanonisk Og standard formularer. Både i kanonisk og standardform

De der. alle variabler i enhver mulig løsning på problemet skal have ikke-negative værdier (sådanne variabler kaldes normalt ikke-negativ i modsætning til den såkaldte gratis variabler, hvis værdiområde ikke er underlagt sådanne begrænsninger). Forskellen mellem disse former er, at i det ene tilfælde I 2 = 0, og i det andet - I 1 = 0.

LP-problemet i kanonisk form.

Lineær programmering

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

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

Mange egenskaber ved lineære programmeringsproblemer kan også tolkes som egenskaber ved polyedre og dermed geometrisk formuleret og bevist.

Historie

Den indre punktmetode blev første gang nævnt af I. I. Dikin i 1967.

Opgaver

Det vigtigste (standard) lineære programmeringsproblem kaldes problemet med at finde minimum af en lineær objektiv funktion ( lineær form) af formularen:

under forhold

, .

Det lineære programmeringsproblem vil have kanonisk opfattelse , hvis der i hovedproblemet i stedet for det første system af uligheder er et system af ligninger:

,

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

Lineære programmeringsproblemer af den mest generelle form (problemer med blandede begrænsninger: ligheder og uligheder, tilstedeværelsen af ​​variable fri for begrænsninger) kan reduceres til ækvivalente (som har det samme sæt af løsninger) ved at erstatte variabler og erstatte ligheder med et par uligheder.

Det er let at se, at problemet med at finde maksimum kan erstattes af opgaven med at finde minimum ved at tage koefficienter med modsat fortegn.

Prøveproblemer

Maksimal matchning

Overvej det maksimale matchningsproblem i en todelt graf: Der er flere drenge og piger, og for hver dreng og pige ved man, om de er attraktive for hinanden. Vi er nødt til at gifte det maksimale antal par med gensidig sympati.

Lad os introducere variable, der svarer til parret af -drengen og -pigen og opfylder begrænsningerne:

med objektiv funktion. Det kan påvises, at blandt de optimale løsninger på dette problem er der et heltal. Variabler lig med 1 vil svare til par, der bør være gift.

Maksimalt flow

Lad der være en graf (med orienterede kanter), hvori for hver kant dens gennemløb. Og to hjørner er givet: dræn og kilde. Det er nødvendigt at angive for hver kant, hvor meget væske der vil strømme gennem den (ikke mere end dens kapacitet) for at maksimere den samlede strøm fra kilde til afløb (væske kan ikke forekomme eller forsvinde ved alle hjørner undtagen afløbet og kilden).

Lad os tage mængden af ​​væske, der strømmer gennem ribben, som variable. Derefter

,

hvor er kapaciteten af ​​den kant. Disse uligheder skal suppleres med ligheden mellem mængden af ​​indstrømmende og udstrømmende væske for hvert toppunkt, undtagen afløbet og kilden. Som en funktion er det naturligt at tage forskellen mellem mængden af ​​udstrømmende og indstrømmende væske ved kilden.

En generalisering af det tidligere problem er maksimal strøm af minimumsomkostninger. I denne opgave er omkostningerne for hver kant angivet, og blandt de maksimale flows skal du vælge et flow med minimumsomkostninger. Dette problem kommer ned til to lineære programmeringsproblemer: først skal du løse problemet med det maksimale flow, og derefter tilføje begrænsningen til dette problem, hvor er værdien af ​​det maksimale flow, og løse problemet med ny funktion- flowomkostninger.

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

Transportopgave

Der er en vis homogen last, der skal flyttes fra lagre til fabrikker. For hvert lager er det kendt, hvor meget last det indeholder, og for hvert anlæg er dets efterspørgsel efter last kendt. Omkostningerne til transport er proportionale med afstanden fra lageret til fabrikken (alle afstande fra th lager til th fabrik er kendt). Det kræves at komponere mest billig plan transport.

Afgørende variable i I dette tilfælde er mængden af ​​gods, der transporteres fra th lager til th anlæg. De opfylder begrænsningerne:

Den objektive funktion har formen: , som skal minimeres.

Nul sum spil

Der er en størrelsesmatrix. Den første spiller vælger et tal fra 1 til , den anden - fra 1 til . Så tjekker de tallene, og den første spiller får point, og den anden spiller får point (nummeret valgt af den første spiller får det andet). Vi skal finde den optimale strategi for den første spiller.

Antag, at i en optimal strategi, for eksempel, skal den første spiller vælge et tal med sandsynlighed . Så er den optimale strategi en løsning på følgende lineære programmeringsproblem:

, , (),

hvor funktionen skal maksimeres. Værdien i den optimale løsning vil være den matematiske forventning om den første spillers udbetaling i værste fald.

Løsningsalgoritmer

Den mest berømte og udbredte i praksis til at løse fælles opgave Lineær programmering (LP) er en simpleksmetode. På trods af at simplex-metoden er en ret effektiv algoritme, der har vist gode resultater i løsning af anvendte LP-problemer, er det en algoritme med eksponentiel kompleksitet. Årsagen til dette er den kombinatoriske karakter af simplex-metoden, som sekventielt itererer over polyederens hjørner tilladte løsninger når man leder efter den optimale løsning.

Den første polynomielle algoritme, ellipsoidmetoden, blev foreslået i 1979 af den sovjetiske matematiker L. Khachiyan, og løste dermed et problem, der havde været uløst i lang tid. Ellipsoidmetoden har en helt anden, ikke-kombinatorisk karakter end simpleksmetoden. Men fra et beregningsmæssigt synspunkt viste denne metode sig ikke at være lovende. Men selve kendsgerningen om polynomisk kompleksitet af problemer førte til skabelsen af ​​en hel klasse effektive algoritmer LP - indvendige punktmetoder, hvoraf den første var N. Karmarkars algoritme foreslået i 1984. Algoritmer af denne type bruger en kontinuerlig fortolkning af LP-problemet, når der i stedet for at opregne hjørnerne af polyederet af løsninger til LP-problemet, udføres en søgning langs baner i rummet problemvariabler, der ikke passerer gennem polyederens hjørner. Den indre punktmetode, som i modsætning til simplexmetoden omgår punkter fra regionens indre acceptable værdier, bruger log-barriere ikke-lineære programmeringsmetoder udviklet i 1960'erne af Fiacco og McCormick.

se også

• Grafisk metode til løsning af et lineært programmeringsproblem

Noter

Litteratur

• Thomas H. Corman et al. Kapitel 29. Lineær programmering // Algoritmer: konstruktion og analyse = INTRODUKTION TIL ALGORITHMER. - 2. udg. - M.: "Williams", 2006. - S. 1296. - ISBN 5-8459-0857-4
• Akulich I.L. Kapitel 1. Lineære programmeringsproblemer, Kapitel 2. Særlige lineære programmeringsproblemer // Matematisk programmering i eksempler og opgaver. - M.: Højere skole, 1986. - 319 s. - ISBN 5-06-002663-9
• Karmanov V.G. Matematisk programmering. - 3. udgave. - M.: Nauka, 1986. - 288 s.
• Danzig George Bernard "Erindringer om begyndelsen af ​​lineær programmering"

Links

• - Gratis optimeringspakke designet til at løse lineære, heltal- og målprogrammeringsproblemer.
• Vershik A. M. "Om L. V. Kantorovich og lineær programmering"
• Bolshakova I. V., Kuralenko M. V. "Lineær programmering. Pædagogisk og metodisk manual til testen."
• Barsov A. S. "Hvad er lineær programmering", Populære forelæsninger om matematik, Gostekhizdat, 1959.
• M. N. Vyalyi Lineære uligheder og kombinatorik. - MCNMO, 2003.

Wikimedia Foundation. 2010.

• Salten, Felix
• Glagow, Martina

Se, hvad "Lineær programmering" er i andre ordbøger:

lineær programmering- - lineær programmering Et område med matematisk programmering, der er viet til teorien og metoderne til at løse ekstreme problemer karakteriseret ved lineær afhængighed mellem… … Teknisk oversættervejledning

Lineær programmering

Lineær programmering- et felt af matematisk programmering, der er viet til teori og metoder til løsning af ekstreme problemer karakteriseret ved en lineær sammenhæng mellem variabler. I sin mest generelle form er problemet med L.p. kan skrives sådan. Er givet… … Økonomisk og matematisk ordbog

15. Analysemetoder. Lineære programmeringsmetoder.

15.1. Analytiske metoder

Gennem hele sin udvikling søgte mennesket, når det udførte visse handlinger, at opføre sig på en sådan måde, at resultatet opnået som følge af en handling viste sig i en vis forstand at være det bedste. Han flyttede fra et punkt til et andet og søgte at finde den kortest mulige vej. Da han byggede en bolig, ledte han efter en geometri, der ville give acceptable levevilkår med det mindste brændstofforbrug. Mens han byggede skibe, forsøgte han at give dem en form, hvor vandet ville yde den mindste modstand. Listen over lignende eksempler kan nemt fortsættes.

De bedste løsninger på problemer i en vis forstand kaldes normalt optimal. I øjeblikket kan intet problem løses uden brug af optimeringsprincipper. komplekst problem. Ved opstilling og løsning af optimeringsproblemer opstår to spørgsmål: hvad og hvordan optimerer man?

Svaret på det første spørgsmål er opnået som et resultat af en dybdegående undersøgelse af det problem, der skal løses. Parameteren, der bestemmer graden af ​​perfektion af løsningen på det opståede problem, identificeres. Denne parameter kaldes normalt målfunktion eller kvalitetskriterium. Dernæst etableres et sæt af mængder, der bestemmer den objektive funktion. Til sidst formuleres alle de begrænsninger, der skal tages i betragtning ved løsning af problemet. Herefter opbygges en matematisk model, som består i at fastslå objektivfunktionens analytiske afhængighed af alle argumenter og den analytiske formulering af de begrænsninger, der er forbundet med problemet. Dernæst begynder vi at søge efter et svar på det andet spørgsmål.

Så lad, som et resultat af formaliseringen af ​​det anvendte problem, fastslå, at den objektive funktion er , hvor mængden X er en generalisering af restriktioner, kaldes det sættet af gennemførlige løsninger. Essensen af ​​optimeringsproblemet er at søge på sættet X - sættet af gennemførlige løsninger til en sådan løsning
, hvor målet fungerer f når sin minimums- eller maksimumværdi.

En integreret del af optimeringsmetoder er lineær programmering.

15.2. Grundlæggende begreber for lineær programmering

Den første omtale (1938) af matematiske metoder i effektiv produktionsstyring tilhører den sovjetiske matematiker L. V. Kantorovich. Et år senere, i 1939, udgav L. V. Kantorovich værket "Matematiske metoder til organisering og planlægning af produktion" og anvendte praktisk de opnåede resultater. Udtrykket "lineær programmering" blev introduceret af amerikanske matematikere J. Danzig og T. Koopmans i slutningen af ​​40'erne. J. Dantzig udviklede simplexmetodens matematiske apparat til løsning af lineære programmeringsproblemer (1951). Simplexmetoden bruges til at løse en lang række lineære programmeringsproblemer og er stadig en af ​​hovedmetoderne.

Lineær programmering er en gren af ​​matematikken fokuseret på at finde et ekstremum (maksimum eller minimum) i problemer, der er beskrevet af lineære ligninger. Desuden beskriver lineære ligninger både selve objektivfunktionen og inputparametrene (variablerne) af betingelserne for restriktioner på input parametre. En nødvendig betingelse for lineære programmeringsproblemer er den obligatoriske tilstedeværelse af restriktioner på ressourcer (råmaterialer, materialer, finansiering, efterspørgsel efter fremstillede produkter osv.). Til andre en vigtig betingelse løsning af problemet er valget af stopkriterium for algoritmen, dvs. objektivfunktionen skal være optimal i en eller anden forstand. Optimiteten af ​​den objektive funktion skal udtrykkes kvantitativt. Hvis målfunktionen er repræsenteret af en eller to ligninger, kan sådanne problemer i praksis løses ganske let. Algoritmestopkriteriet (eller optimalitetskriteriet) skal opfylde følgende krav:

være den eneste til en given opgave;

målt i mængdeenheder;

lineært afhænger af inputparametrene.

Baseret på ovenstående kan vi formulere det lineære programmeringsproblem i generel form:

find yderpunktet af den objektive funktion

under restriktioner i form af ligestilling:

(2.2)

under restriktioner i form af uligheder:

(2.3)

og betingelser for ikke-negativitet af inputparametre:

I kort form kan det lineære programmeringsproblem skrives som følger:

(2.5)

givet det

Hvor
- inputvariabler;

Tal er positive, negative og lig med nul.

I matrixform kan dette problem skrives som følger:

Lineære programmeringsproblemer kan løses analytisk og grafisk.

15.3. Kanonisk lineær programmeringsproblem

, i=1,…,m,

, j=1,…,n.

De vigtigste beregningsmetoder til løsning af lineære programmeringsproblemer blev udviklet specifikt til det kanoniske problem.

15.4. Generelt lineært programmeringsproblem

Det er nødvendigt at maksimere (minimere) en lineær funktion af n variabler.

under restriktioner

, jeg=1,…, k,

, jeg=1+ k,…, m,

, …,

Her k≤ m, r≤ n. Standardproblemet fås som et specialtilfælde af det generelle med k= m, r= n; kanonisk – kl k=0, r= n.

Eksempel.

Konfekturefabrikken producerer flere slags slik. Lad os kalde dem "A", "B" og "C". Det er kendt, at salget af ti kilo slik "A" giver et overskud på 90 rubler, "B" - 100 rubler og "C" - 160 rubler. Slik kan produceres i enhver mængde (salget er garanteret), men forsyningerne af råvarer er begrænsede. Det er nødvendigt at bestemme, hvilken slags slik og hvor mange titalls kilo, der skal produceres, så den samlede fortjeneste fra salget maksimeres. Forbrugsraterne for råvarer til fremstilling af 10 kg slik af hver type er angivet i tabel 1.

Tabel 1. Råvareforbrugsrater

til produktion

Den økonomiske og matematiske formulering af problemet har formen

Find sådanne variable værdier X=(x1, x2, x3), til

objektiv funktion

under betingelser-begrænsninger:

Hvis et lineært programmeringsproblem kun har to variable, kan det løses grafisk metode.

Overvej et lineært programmeringsproblem med to variable og:
(1.1) ;
(1.2)
Her, der er vilkårlige tal. Opgaven kan enten være at finde maksimum (max) eller at finde minimum (min). Systemet med restriktioner kan indeholde både tegn og tegn.

Opbygning af regionen af ​​gennemførlige løsninger

Den grafiske metode til løsning af problem (1) er som følger.
Først tegner vi koordinatakserne og vælger skalaen. Hver af ulighederne i systemet af begrænsninger (1.2) definerer en halvplan afgrænset af den tilsvarende rette linje.

Altså den første ulighed
(1.2.1)
definerer et halvt plan afgrænset af en ret linje. På den ene side af denne lige linje og på den anden side. På den meget lige linje. For at finde ud af, på hvilken side ulighed (1.2.1) holder, vælger vi et vilkårligt punkt, der ikke ligger på linjen. Dernæst erstatter vi koordinaterne for dette punkt i (1.2.1). Hvis uligheden holder, så indeholder halvplanet det valgte punkt. Hvis uligheden ikke holder, så er halvplanet placeret på den anden side (indeholder ikke det valgte punkt). Skygge det halvplan, som uligheden (1.2.1) gælder for.

Vi gør det samme for de resterende uligheder i systemet (1.2). På denne måde får vi skyggefulde halvplaner. Punkterne i regionen med gennemførlige løsninger opfylder alle uligheder (1.2). Derfor er regionen med mulige løsninger (ADA) grafisk skæringspunktet mellem alle konstruerede halvplaner. Skyggelægning af ODR. Det er en konveks polygon, hvis flader hører til de konstruerede lige linjer. En ODF kan også være en ubegrænset konveks figur, et segment, en stråle eller en lige linje.

Der kan også opstå tilfælde, at halvplanerne ikke indeholder fællespunkter. Så er domænet for mulige løsninger det tomme sæt. Dette problem har ingen løsninger.

Metoden kan forenkles. Du behøver ikke skygge hvert halvplan, men først konstruer alle de lige linjer
(2)
Vælg derefter et vilkårligt punkt, der ikke hører til nogen af ​​disse linjer. Indsæt koordinaterne for dette punkt i systemet af uligheder (1.2). Hvis alle uligheder er opfyldt, så er området af mulige løsninger begrænset af de konstruerede rette linjer og inkluderer det valgte punkt. Vi skygger området med mulige løsninger langs linjernes grænser, så det inkluderer det valgte punkt.

Hvis mindst én ulighed ikke er opfyldt, så vælg et andet punkt. Og så videre, indtil der findes et punkt, hvis koordinater opfylder systemet (1.2).

At finde yderpunktet af den objektive funktion

Så vi har en skyggefuld region af mulige løsninger (ADA). Den er begrænset af en brudt linje bestående af segmenter og stråler, der hører til de konstruerede lige linjer (2). ODS er altid et konveks sæt. Det kan enten være et afgrænset sæt eller ikke afgrænset langs nogle retninger.

Nu kan vi lede efter yderpunktet af den objektive funktion
(1.1) .

For at gøre dette skal du vælge et hvilket som helst tal og bygge en lige linje
(3) .
For at lette den videre præsentation antager vi, at denne lige linje går gennem ODR. På denne linje er objektivfunktionen konstant og lig med . sådan en ret linje kaldes en funktionsniveaulinje. Denne lige linje deler planet i to halvplaner. På et halvt plan
.
På et andet halvt fly
.
Det vil sige, på den ene side af den rette linje (3) øges objektivfunktionen. Og jo længere vi flytter punktet fra den lige linje (3), jo større bliver værdien. På den anden side af lige linje (3) falder objektivfunktionen. Og jo længere vi flytter punktet fra lige linje (3) til den anden side, jo mindre vil værdien være. Hvis vi tegner en ret linje parallelt med linje (3), så vil den nye rette linje også være en niveaulinje af objektivfunktionen, men med en anden værdi.

For at finde den maksimale værdi af den objektive funktion er det således nødvendigt at tegne en ret linje parallel med den rette linje (3), så langt som muligt fra den i retning af stigende værdier, og som passerer gennem mindst et punkt af ODD. For at finde minimumsværdien af ​​den objektive funktion er det nødvendigt at tegne en ret linje parallelt med lige linje (3) og så langt som muligt fra den i retning af faldende værdier og passere gennem mindst et punkt af ODD.

Hvis ODR er ubegrænset, kan der opstå en sag, hvor en sådan direkte linje ikke kan trækkes. Det vil sige, uanset hvordan vi fjerner den lige linje fra niveaulinjen (3) i retning af stigende (faldende), vil den rette linje altid passere gennem ODR. I dette tilfælde kan den være vilkårligt stor (lille). Derfor er der ingen maksimum (minimum) værdi. Problemet har ingen løsninger.

Lad os overveje tilfældet, når den ekstreme linje parallel med en vilkårlig linje af formen (3) passerer gennem et toppunkt af ODR-polygonen. Ud fra grafen bestemmer vi koordinaterne for dette toppunkt. Derefter bestemmes den maksimale (minimum) værdi af objektivfunktionen af ​​formlen:
.
Løsningen på problemet er
.

Der kan også være et tilfælde, hvor den lige linje er parallel med en af ​​ODR's flader. Derefter passerer den rette linje gennem to hjørner af ODR-polygonen. Vi bestemmer koordinaterne for disse hjørner. For at bestemme den maksimale (minimum) værdi af objektivfunktionen kan du bruge koordinaterne for et hvilket som helst af disse hjørner:
.
Problemet har uendeligt mange løsninger. Løsningen er ethvert punkt placeret på segmentet mellem punkterne og , inklusive punkterne og dem selv.

Et eksempel på løsning af et lineært programmeringsproblem ved hjælp af den grafiske metode

Opgaven

Virksomheden producerer kjoler af to modeller A og B. Der bruges tre typer stof. For at lave en kjole af model A kræves der 2 m stof af den første type, 1 m stof af den anden type, 2 m stof af den tredje type. For at lave en kjole af model B kræves 3 m stof af den første type, 1 m stof af den anden type, 2 m stof af den tredje type. Lagrene af stof af den første type er 21 m, af den anden type - 10 m, af den tredje type - 16 m. Frigivelsen af ​​et produkt af type A giver en indkomst på 400 den. enheder, et produkt type B - 300 den. enheder

Lav en produktionsplan, der giver virksomheden den største indkomst. Løs problemet grafisk.

Løsning

Lad variablerne og angive antallet af producerede kjoler, henholdsvis model A og B. Derefter vil mængden af ​​stof af den første type, der forbruges, være:
(m)
Mængden af ​​stof af den anden type forbrugt vil være:
(m)
Mængden af ​​forbrugt stof af den tredje type vil være:
(m)
Da antallet af producerede kjoler ikke kan være negativt, så
Og .
Indtægterne fra de producerede kjoler vil være:
(den. enheder)

Så har den økonomisk-matematiske model af problemet formen:

Vi løser det grafisk.
Vi tegner koordinatakserne og .

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 7) og (10.5; 0).

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 10) og (10; 0).

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 8) og (8; 0).

Vi skygger området, så punktet (2; 2) falder ind i den skraverede del. Vi får firkantet OABC.

(A1.1) .
kl.
kl.
Tegn en lige linje gennem punkterne (0; 4) og (3; 0).

Vi bemærker endvidere, at da koefficienterne for og af den objektive funktion er positive (400 og 300), stiger den efterhånden som og stiger. Vi tegner en ret linje parallelt med lige linje (A1.1), så langt som muligt fra den i retning af stigende , og passerer gennem mindst et punkt i firkantet OABC. En sådan linje går gennem punkt C. Ud fra konstruktionen bestemmer vi dens koordinater.
.

Løsningen af ​​problemet: ;

Svar

.
Det vil sige, at for at opnå den største indkomst er det nødvendigt at lave 8 kjoler af model A. Indtægten bliver 3200 den. enheder

Eksempel 2

Opgaven

Løs et lineært programmeringsproblem grafisk.

Løsning

Vi løser det grafisk.
Vi tegner koordinatakserne og .

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 6) og (6; 0).

Vi bygger en lige linje.
Herfra.
kl.
kl.
Tegn en lige linje gennem punkterne (3; 0) og (7; 2).

Vi bygger en lige linje.
Vi bygger en lige linje (abscisse-akse).

Området for tilladte løsninger (ADS) er begrænset af de konstruerede rette linjer. For at finde ud af hvilken side bemærker vi, at punktet tilhører ODR, da det opfylder systemet med uligheder:

Vi skygger for området langs grænserne for de konstruerede linjer, så punktet (4; 1) falder ind i den skraverede del. Vi får trekant ABC.

Vi bygger en vilkårlig linje af niveauet af den objektive funktion, f.eks.
.
kl.
kl.
Tegn en lige plan linje gennem punkterne (0; 6) og (4; 0).
Da objektivfunktionen stiger med stigende og , trækker vi en ret linje parallelt med niveaulinjen og så langt som muligt fra den i retning af stigende , og passerer gennem mindst ét ​​punkt i trekant ABC. En sådan linje går gennem punkt C. Ud fra konstruktionen bestemmer vi dens koordinater.
.

Løsningen af ​​problemet: ;

Svar

Eksempel på ingen løsning

Opgaven

Løs et lineært programmeringsproblem grafisk. Find maksimum- og minimumværdien af ​​objektivfunktionen.

Løsning

Vi løser problemet grafisk.
Vi tegner koordinatakserne og .

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 8) og (2.667; 0).

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 3) og (6; 0).

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (3; 0) og (6; 3).

De rette linjer er koordinatakserne.

Området for tilladte løsninger (ADA) er begrænset af de konstruerede rette linjer og koordinatakser. For at finde ud af hvilken side bemærker vi, at punktet tilhører ODR, da det opfylder systemet med uligheder:

Vi skygger området, så punktet (3; 3) falder ind i den skraverede del. Vi får et ubegrænset område afgrænset af den stiplede linje ABCDE.

Vi bygger en vilkårlig linje af niveauet af den objektive funktion, f.eks.
(A3.1) .
kl.
kl.
Tegn en lige linje gennem punkterne (0; 7) og (7; 0).
Da koefficienterne for og er positive, stiger den med stigende og .

For at finde maksimum, skal du tegne en parallel linje, som er så langt væk som muligt i retning af stigende , og passerer gennem mindst et punkt i regionen ABCDE. Men da området er ubegrænset på siden af ​​store værdier og , kan en sådan lige linje ikke tegnes. Lige meget hvilken lige linje vi trækker, vil der altid være punkter i regionen, der er længere væk i retning af stigende og . Derfor er der ikke noget maksimum. du kan gøre den så stor som du vil.

Vi leder efter minimum. Vi tegner en lige linje parallelt med lige linje (A3.1) og så langt som muligt fra den i retning af aftagende , og passerer gennem mindst et punkt i regionen ABCDE. En sådan linje går gennem punkt C. Ud fra konstruktionen bestemmer vi dens koordinater.
.
Minimumsværdi objektiv funktion:

Svar

Maksimal værdi eksisterer ikke.
Minimumsværdi
.

Denne metode er en metode til målrettet opregning af referenceløsninger til et lineært programmeringsproblem. Det giver mulighed for, i et begrænset antal trin, enten at finde en optimal løsning eller at fastslå, at der ikke er nogen optimal løsning.

Hovedindholdet af simplex-metoden er som følger:

1. Angiv en metode til at finde den optimale referenceløsning
2. Angiv metoden til overgang fra en referenceløsning til en anden, hvor værdien af ​​den objektive funktion vil være tættere på den optimale, dvs. angive en måde at forbedre referenceløsningen på
3. Sæt kriterier, der giver dig mulighed for omgående at stoppe med at søge efter supportløsninger ved den optimale løsning eller drage en konklusion om fraværet af en optimal løsning.

Algoritme af simplex-metoden til løsning af lineære programmeringsproblemer

For at løse problemet simpleks metode du skal gøre følgende:

1. Bring problemet til kanonisk form
2. Find den indledende supportløsning med et "enhedsgrundlag" (hvis der ikke er nogen supportløsning, så har problemet ikke en løsning på grund af inkompatibiliteten af ​​systemet af begrænsninger)
3. Beregn estimater af vektornedbrydninger baseret på referenceopløsningen og udfyld simplexmetodens tabel
4. Hvis kriteriet for den optimale løsnings unikke karakter er opfyldt, slutter løsningen af ​​problemet
5. Hvis betingelsen for eksistensen af ​​et sæt af optimale løsninger er opfyldt, så findes alle optimale løsninger ved simpel opregning

Et eksempel på løsning af et problem ved hjælp af simpleksmetoden

Eksempel 26.1

Løs problemet ved hjælp af simpleksmetoden:

Løsning:

Vi bringer problemet til kanonisk form.

For at gøre dette introducerer vi en ekstra variabel x 6 med koefficient +1 til venstre side af den første ulighedsbegrænsning. Variablen x 6 er inkluderet i objektivfunktionen med en koefficient på nul (dvs. den er ikke inkluderet).

Vi får:

Vi finder den indledende supportløsning. For at gøre dette sætter vi lighedstegn mellem frie (uløste) variabler til nul x1 = x2 = x3 = 0.

Vi får referenceløsning X1 = (0,0,0,24,30,6) med enhedsbasis B1 = (A4, A5, A6).

Vi beregner estimater af vektornedbrydning betingelser på basis af referenceopløsningen ifølge formlen:

Δ k = Cb X k - c k

• C b = (c 1, c 2, ..., c m) - vektor af koefficienter for den objektive funktion for de grundlæggende variable
• X k = (x 1k , x 2k , ... , x mk) - ekspansionsvektor af den tilsvarende vektor A k i henhold til referenceopløsningens grundlag
• C k er koefficienten for objektivfunktionen for variablen x k.

Estimaterne af de vektorer, der indgår i grundlaget, er altid lig nul. Referenceløsningen, udvidelseskoefficienter og estimater af udvidelser af tilstandsvektorer baseret på referenceløsningen er skrevet ind simplex bord:

Øverst i tabellen, for at lette beregningen af ​​estimater, er koefficienterne for den objektive funktion skrevet. I den første kolonne "B" er de vektorer, der indgår i referenceløsningens basis, skrevet. Rækkefølgen, hvori disse vektorer er skrevet, svarer til antallet af tilladte ukendte i begrænsningsligningerne. I den anden kolonne i tabellen "C b" er koefficienterne for den objektive funktion for de grundlæggende variable skrevet i samme rækkefølge. På korrekte placering Koefficienterne for den objektive funktion i kolonnen "C b" af estimatet af enhedsvektorerne inkluderet i grundlaget er altid lig med nul.

I sidste linje tabeller med estimater af Δ k i kolonnen "A 0" er værdierne af objektivfunktionen på referenceløsningen Z(X 1) skrevet.

Den initiale støtteløsning er ikke optimal, da estimaterne Δ 1 = -2, Δ 3 = -9 for vektorerne A 1 og A 3 i det maksimale problem er negative.

Ifølge sætningen om forbedring af støtteløsningen, hvis mindst én vektor i et maksimalt problem har et negativt estimat, så kan du finde en ny støtteløsning, hvor værdien af ​​den objektive funktion vil være større.

Lad os bestemme, hvilken af ​​de to vektorer, der vil føre til en større stigning i objektivfunktionen.

Forøgelsen af ​​objektivfunktionen findes ved formlen: .

Vi beregner værdierne af parameteren θ 01 for den første og tredje kolonne ved hjælp af formlen:

Vi får θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (Tabel 26.1).

Vi finder stigningen af ​​den objektive funktion, når vi indfører den første vektor ΔZ 1 = - 6*(- 2) = 12 i basis, og den tredje vektor ΔZ 3 = - 3*(- 9) = 27.

Derfor for en hurtigere tilgang til optimal løsning det er nødvendigt at indføre vektor A3 i basis af referenceopløsningen i stedet for den første vektor af basis A6, da minimum af parameteren θ 03 er opnået i den første række (l = 1).

Vi udfører Jordan-transformationen med elementet X13 = 2, vi opnår den anden referenceløsning X2 = (0,0,3,21,42,0) med basis B2 = (A3, A4, A5). (Tabel 26.2)

Denne løsning er ikke optimal, da vektor A2 har et negativt estimat Δ2 = - 6. For at forbedre løsningen er det nødvendigt at indføre vektor A2 i referenceopløsningens basis.

Vi bestemmer antallet af vektoren afledt af basis. For at gøre dette beregner vi parameteren θ 02 for den anden kolonne, den er lig med 7 for l = 2. Derfor udleder vi den anden basisvektor A4 fra basis. Vi udfører Jordan-transformationen med elementet x 22 = 3, vi får den tredje referenceløsning X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabel 26.3).

Denne løsning er den eneste optimale, da estimaterne for alle vektorer, der ikke er inkluderet i grundlaget, er positive

Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.

Svar: max Z(X) = 201 ved X = (0,7,10,0,63).

Lineær programmeringsmetode i økonomisk analyse

Lineær programmeringsmetode gør det muligt at retfærdiggøre den mest optimale økonomiske løsning under forhold med strenge restriktioner relateret til de ressourcer, der bruges i produktionen (anlægsaktiver, materialer, arbejdskraft). Anvendelse af denne metode i økonomisk analyse giver dig mulighed for at løse problemer primært relateret til planlægning af organisationens aktiviteter. Denne metode hjælper med at bestemme de optimale outputniveauer, såvel som anvisningerne for de fleste effektiv brug produktionsressourcer til rådighed for organisationen.

Ved hjælp af denne metode løses de såkaldte ekstreme problemer, som består i at finde ekstreme værdier, det vil sige maksimum og minimum af funktioner af variable mængder.

Denne periode er baseret på løsning af et system af lineære ligninger i tilfælde, hvor de analyserede økonomiske fænomener er forbundet med en lineær, strengt funktionel afhængighed. Den lineære programmeringsmetode bruges til at analysere variable i nærvær af visse begrænsende faktorer.

En meget almindelig løsning er den såkaldte transport problem ved hjælp af den lineære programmeringsmetode. Indholdet af denne opgave er at minimere omkostningerne i forbindelse med driften Køretøj under eksisterende restriktioner med hensyn til antallet af køretøjer, deres bæreevne, varigheden af ​​deres drift, og hvis der er behov for vedligeholdelse maksimal mængde kunder.

Udover, denne metode bruges i vid udstrækning til at løse planlægningsproblemer. Denne opgave består af en sådan fordeling af driftstiden for personalet i en given organisation, som ville være mest acceptabel både for medlemmerne af dette personale og for organisationens kunder.

Denne opgave er at maksimere antallet af klienter, der betjenes under betingelser med begrænsninger af antallet af ledige medarbejdere, såvel som arbejdstidsfonden.

Den lineære programmeringsmetode er således ret almindelig i placerings- og brugsanalyse. forskellige typer ressourcer, såvel som i processen med at planlægge og forudsige organisationers aktiviteter.

Endnu matematisk programmering kan også anvendes på de økonomiske fænomener, hvis forhold ikke er lineært. Til dette formål kan der anvendes ulineære, dynamiske og konvekse programmeringsmetoder.

Ikke-lineær programmering er afhængig af den ikke-lineære karakter af den objektive funktion eller begrænsninger, eller begge dele. Formerne for den objektive funktion og ulighedsbegrænsninger i disse forhold kan være forskellige.

Ikke-lineær programmering bruges i økonomisk analyse, især ved etablering af forholdet mellem indikatorer, der udtrykker effektiviteten af ​​en organisations aktiviteter og omfanget af denne aktivitet, strukturen af ​​produktionsomkostninger, markedsforhold osv.

Dynamisk programmering er baseret på at konstruere et beslutningstræ. Hvert niveau i dette træ tjener som et trin til at bestemme konsekvenserne af en tidligere beslutning og for at eliminere ineffektive muligheder for denne beslutning. Dermed, dynamisk programmering har en multi-trin, multi-stage karakter. Denne type programmering bruges i økonomisk analyse til at finde optimale muligheder udvikling af organisationen både nu og i fremtiden.

Konveks programmering er en form for ikke-lineær programmering. Denne type programmering udtrykker den ikke-lineære karakter af forholdet mellem resultaterne af en organisations aktiviteter og dens omkostninger. Konveks (alias konkav) programmeringsanalyser konveks objektive funktioner og konvekse systemer af restriktioner (punkter med acceptable værdier). Konveks programmering bruges i analysen af ​​økonomiske aktiviteter med det formål at minimere omkostningerne, og konkav programmering med det formål at maksimere indkomsten under eksisterende restriktioner på virkningen af ​​faktorer, der påvirker de analyserede indikatorer på den modsatte måde. Følgelig minimeres konvekse objektivfunktioner med de typer programmering, der er under overvejelse, og konkave objektivfunktioner maksimeres.