Den løsende ledende raden i en simplekstabell kalles. Enkel metode for å løse lineære programmeringsproblemer

En av løsningsmetodene optimaliseringsproblemer (vanligvis forbundet med å finne minimum eller maksimum) lineær programmering kalt . Enkel metode inkluderer en hel gruppe algoritmer og metoder for å løse lineære programmeringsproblemer. En av disse metodene, som går ut på å registrere kildedataene og beregne dem på nytt i en spesiell tabell, kalles enkel tabellmetode.

La oss vurdere algoritmen til den tabellformede simpleksmetoden ved å bruke eksempelet på løsningen produksjonsoppgave , som koker ned til å finne produksjonsplan gir maksimal fortjeneste.

Inndata for simpleksmetodeproblemet

Selskapet produserer 4 typer produkter, behandler dem på 3 maskiner.

Tidsstandarder (min./stk) for bearbeiding av produkter på maskiner er spesifisert av matrise A:

Maskinens driftstidsfond (min.) er spesifisert i matrise B:

Fortjeneste fra salg av hver produktenhet (RUB/stk) er gitt av matrise C:

Formål med produksjonsoppgaven

Lag en produksjonsplan som vil maksimere fortjenesten til bedriften.

Løse problemet ved å bruke den enkle tabellmetoden

(1) La oss angi med X1, X2, X3, X4 det planlagte antallet produkter av hver type. Så ønsket plan: ( X1, X2, X3, X4)

(2) La oss skrive ned planbegrensningene i form av et ligningssystem:

(3) Da er målfortjenesten:

Det vil si at fortjenesten ved å oppfylle produksjonsplanen skal være maksimal.

(4) For å løse det resulterende problemet på betinget ekstrem, erstatter vi systemet med ulikheter med systemet lineære ligninger ved å introdusere flere ikke-negative variabler i den ( X5, X6, X7).

(5) La oss godta følgende referanseplan :

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) La oss legge inn dataene simplex bord:

I siste linje legger vi inn koeffisientene for objektiv funksjon og selve dens betydning har motsatt fortegn;

(7) Velg inn siste linje størst (modulo) et negativt tall.

La oss beregne b = N / Elementer_av_den_valgte_kolonnen

Blant de beregnede verdiene av b velger vi minst.

Skjæringspunktet mellom den valgte kolonnen og raden vil gi oss det løsende elementet. Vi endrer grunnlaget til en variabel som tilsvarer det løsende elementet ( X5 til X1).

Selve løsningselementet blir til 1.
For elementer i oppløsningslinjen – a ij (*) = a ij / RE ( det vil si at vi deler hvert element med verdien til det løsende elementet og får nye data).
For elementer i oppløsningskolonnen tilbakestilles de ganske enkelt til null.
Vi beregner de gjenværende elementene i tabellen på nytt ved å bruke rektangelregelen.

a ij (*) = a ij – (A * B / RE)

Som du kan se, tar vi den gjeldende cellen som beregnes på nytt og cellen med det løsende elementet. De danner motsatte hjørner av rektangelet. Deretter multipliserer vi verdiene fra cellene i de to andre hjørnene av dette rektangelet. Denne jobben ( EN * B) dividere med det løsende elementet ( RE). Og trekk fra den gjeldende cellen som beregnes på nytt ( en ij) hva skjedde. Vi får en ny verdi - a ij (*).

(9) Sjekk siste linje igjen ( c) på tilstedeværelsen av negative tall. Hvis de ikke er der - optimal plan funnet, gå til siste etappe løse problemet. Hvis det er det, er planen ennå ikke optimal, og simplekstabellen må beregnes på nytt.

Siden i siste linje har vi igjen negative tall, starter vi en ny iterasjon av beregninger.

(10) Siden det ikke er noen negative elementer i siste linje, betyr dette at vi har funnet den optimale produksjonsplanen! Nemlig: vi vil produsere de produktene som har flyttet til "Basis"-kolonnen - X1 og X2. Vi kjenner fortjenesten fra produksjonen av hver produksjonsenhet ( matrise C). Det gjenstår å multiplisere de funnet produksjonsvolumene for produkt 1 og 2 med fortjeneste per 1 stykke, vi får den endelige ( maksimum! ) fortjeneste for en gitt produksjonsplan.

SVAR:

X1 = 32 stk., X2 = 20 stk., X3 = 0 stk., X4 = 0 stk.

P = 48 * 32 + 33 * 20 = 2.196 gni.

Galyautdinov R.R.

3.1.
3.2.
3.3.
3.4.
3.5.
3.6. Eksempel(1) på å løse LP-problemet ved å bruke simplekstabellmetoden
3.7. Eksempel(2) på å løse LP-problemet ved å bruke simplekstabellmetoden

Ideen med simplex-tabellmetoden er å målrettet telle opp hjørnene til en simpleks. For å starte søket, må du velge et referansepunkt som du vil starte søket fra. Simplexmetoden for å løse et lineært programmeringsproblem er basert på overgangen fra en referanseplan til en annen (ved å telle opp simpleksen til toppunktene) hvor verdien av målfunksjonen øker (minker). Den angitte overgangen er mulig dersom en innledende referanseplan er kjent. For å utarbeide en slik plan, er det nødvendig å utføre en vektoranalyse, på grunnlag av hvilken man bestemmer referansepunktet som søket vil begynne fra.Systemet med ulikheter er redusert til kanonisk form:

x 1 + en 1,m+1* x m+1 + ... + en 1s* x s +...+ en 1n * x n = b 1 ;

x 2 + en 2,m +1* x m+1 + ... + en 2s * x s +...+ en 2n* x n = b 2 ;

x m + en m,m+1* x m+1 + ... + en ms* x s +...+ en mn* x n = b m.

Variabler x 1, x 2,...,x m, inkludert med enhetskoeffisienter i bare én ligning av systemet og med null koeffisienter i resten, kalles grunnleggende. I det kanoniske systemet tilsvarer hver ligning nøyaktig én grunnleggende variabel. Hvile n-m variabler(x m+1 , ...,x n) kalles ikke-grunnleggende variabler.

3.1. Å bringe en matematisk modell til kanonisk form

La oss gi matematisk modell problemer til kanonisk form.For å gjøre dette, la oss bli kvitt ulikhetstegnene ved å introdusere flere variabler og erstatte ulikhetstegnet med et likhetstegn. En ekstra variabel legges utelukkende til for hver ulikhet, og denne variabelen spesifiseres i objektivfunksjonen med en koeffisient på null. Regel for å legge inn tilleggsvariabler: med ">=" - variabelen legges inn i ulikheten med en koeffisient på +1; på "<=" - с коэффициентом (-1).

Noen ganger, når det ikke er noen grunnleggende variabel i ligningen, for å gjøre en negativ tilleggsvariabel til en grunnleggende, kan du multiplisere hele ligningen med (-1).

Du kan også reorientere objektivfunksjonen fra minimum til maksimum eller omvendt ved å multiplisere alle koeffisientene til variablene i denne funksjonen med (-1).

3.2. Vektoranalyse

I vektoranalyse konstrueres vektorer for hver variabel: komponentkoordinatene til den n-dimensjonale (n-antall likninger i systemet) vektoren vil være koeffisientene til denne variabelen i de tilsvarende likningene.

Som nevnt ovenfor kalles en vektor der det er en enhetskoeffisient i bare én ligning og null koeffisienter i andre. grunnleggende. I det kanoniske systemet tilsvarer hver ligning nøyaktig én grunnleggende variabel. Etter å ha kontrollert alle restriksjonene, oppnås systemet i kanonisk form, og det blir mulig å fylle ut den første simplekstabellen.

3.3. Kunstige variabler Metode

Det hender ofte at det er færre basisvektorer enn antall ligninger, dvs. flere ligninger inneholder ikke grunnleggende variabler. I dette tilfellet, bruk den kunstige variabelmetoden for å legge til grunnleggende variabler.

Siden de introduserte variablene ikke er relatert til essensen av LP-problemet i den opprinnelige formuleringen, er det nødvendig å sikre at de kunstige variablene forsvinner. Dette kan gjøres ved hjelp av to-trinns simpleksmetoden.

1. stadie. En kunstig objektivfunksjon vurderes, lik summen av kunstige variabler, som minimeres ved hjelp av simpleksmetoden. Med andre ord er kunstige variabler ekskludert. Hvis minimumsverdien av hjelpeproblemet er null, forsvinner alle kunstige variabler og en tillatt grunnleggende løsning på det opprinnelige problemet oppnås. Deretter implementeres trinn 2. Hvis minimumsverdien til hjelpeproblemet er positiv, er minst en av de kunstige variablene også positiv, noe som indikerer inkonsistensen til det opprinnelige problemet, og beregningene stopper.

Trinn 2. Den gjennomførbare grunnløsningen som ble funnet i det første trinnet forbedres i samsvar med den objektive funksjonen til det opprinnelige LP-problemet basert på simpleksmetoden, dvs. den optimale tabellen i trinn 1 blir til den første tabellen i trinn 2, og målfunksjonen endres.

3.4. Konstruksjon av et simpleksbord

Velge innledende gjennomførbar basisløsning. Grunnleggende løsning er en løsning oppnådd for nullverdier av ikke-grunnleggende variabler, dvs. xi =0, i=m+1,...,n. Grunnløsningen kalles tillatt grunnløsning, hvis verdiene til de grunnleggende variablene som er inkludert i den er ikke-negative, dvs. x j = b j>=0, j=1,2,...,m. I dette tilfellet vil objektivfunksjonen ha følgende form: S = c b* x b = c 1* b 1+ c 2* b 2 +...+c m* b m . Vi fyller ut den innledende tabellen til simpleksmetoden:

Tabell 2.3

c b x b c 1 c 2 ... c m c m+1 ... c n b i
basis x 1 x 2 ... x m x m+1 ... x n
fra 1 x 1 1 0 ... 0 a 1,m+1 ... en n b 1
fra 2 x 2 0 1 ... 0 en 2,m+1 ... en 2 n b 2
... ... ... ... ... ... ... ... ... ...
c m x m 0 0 ... 1 a m,m+1 ... en m n b m
S

3.5. Enkel tabellanalyse

Beregn vektoren for relative estimater c ved å bruke punktproduktregelen

c j = c j - c b* S j,

Hvor

Med b - vektor for estimater av grunnleggende variabler;

S j - J. kolonne i det kanoniske systemet som tilsvarer grunnlaget under vurdering.

Vi supplerer den originale tabellen c - linje.

Tabell 2.4

basis x 1 x 2 ... x m x m+1 ... x n med 1 x 1 1 0 ... 0 en 1,m+1 ... a 1 n b 1med 2 x 2 0 1 ... 0 en 2,m+1 ... en 2 n b 2... ... ... ... ... ... ... ... ... ... c m x m 0 0 ... 1 en m,m+1 ... a m n b m 0 0 ... 0 ... W

c b	x b	c 1	c 2	...	c m	c m+1	...	c n	b i

c- linje

3. Hvis alle estimater c j <=0 (c j >= 0), i=1,...,n, da er den nåværende gjennomførbare løsningen maksimum (minimum). Løsningen er funnet.

4. Ellers må en ikke-grunnleggende variabel x r med størst verdi introduseres i grunnlaget c j i stedet for en av grunnvariablene (tabell 2.5).

Bruker regelen minimumsforhold min( b Jeg/ en ir) vi definerer variabelen x p utledet fra basisen. Hvis koeffisienten en ir er negativ, da b Jeg/ en ir =evighet. Som et resultat vil skjæringspunktet mellom kolonnen der den ikke-grunnleggende inngangsvariabelen x r er plassert og linjen der den utgående grunnvariabelen x p befinner seg, bestemme posisjonen til det ledende elementet i tabellen (tabell 2.6).

Tabell 2.5

		c m+1			b i
	basis	x m+1
fra 1		a 1,m+1	a 1 r	a 1 n
fra 2		a 2,m+1	en 2 r	a 2 n

		a m,m+1	en m r	en m n	b m
c- linje

Tabell 2.6

c m+1

b i

b i /

en ir

x m+1

fra 1

a 1,m+1

a 1 r

a 1 n

b 1/ en 1r

fra 2

a 2,m+1

en 2 r

a 2 n

b 2 / en 2r

med s

a p,m+1

en pr

apn

b p / en pr

a m,m+1

en m r

en m n

b m

b m / en nr

c- linje

6. Vi bruker elementære transformasjoner for å få en ny gjennomførbar baseløsning og et nytt bord. Som et resultat bør det ledende elementet være lik 1, og de resterende elementene i kolonnen med ledende element skal ha verdien null.

Vi beregner nye relative poengsummer ved hjelp av skalartransformasjonsregelen og går videre til trinn 4.

Den, som den første linjen, er reservert for indikatorer for optimalitetskriteriet. Forskjellen mellom den første raden og den første kolonnen er denne:

Den første raden, i motsetning til kolonnen, lagres bare i den første simplekstabellen. Fra den andre iterasjonen er den øverste linjen ikke lenger nødvendig.

Den første linjen indikerer alle uten unntak (både hoved- og tilleggsindikatorer) for optimalitetskriteriet, dvs. alle koeffisienter som de ukjente er inkludert i den objektive funksjonen. Den første kolonnen inkluderer bare en del av koeffisientene for de ukjente i objektivfunksjonen, fordi antall rader i matrisen er lik antall ekstra ukjente. Denne delen består av indikatorer hvis tall er angitt i den andre kolonnen (p k).

Andre kolonne– p k (kalkun k – iterasjonsnummer).

Denne kolonnen angir tallene på de ukjente som er inkludert i basisløsningen. Disse tallene brukes til å nummerere de tilsvarende radene i matrisen.

I den første simplekstabellen indikerer kolonne p 0 tallene til alle tilleggsvariabler.

3. Tredje kolonne– x 0.

I den første simplekstabellen er den fylt med frie termer av ligningene fra systemet av begrensninger. I prosessen med iterativ beregning konverteres disse indikatorene til ønsket løsning. Derfor kalles denne kolonnen totalt kolonne.

4. Objektiv funksjonsverdi Fk.

Ved skjæringspunktet mellom den siste kolonnen i mållinjen, er verdien av den funksjonelle Fk som tilsvarer et gitt trinn av løsningen, en gitt iterasjon k, indikert.

"Matrix base" kolonner.

Vanligvis plasseres kolonnene for de primære ukjente først, etterfulgt av de ekstra ukjente.

I disse kolonnene i den første simplekstabellen er koeffisientene for de ukjente fra likningene til startbetingelsene gitt.

6. De neste tre kolonnene i tabellen (, , ) har hjelpebetydninger. Du kan klare deg uten disse kolonnene, men de gjør beregningene mye enklere. Innholdet i disse kolonnene vil bli diskutert mer detaljert nedenfor.

Eksempel

La oss vurdere et simpleksproblem skrevet i generell form:

La oss redusere problemet til kanonisk form. For å gjøre dette introduserer vi en ukjent (ekstra) i hver av ulikhetene i systemet - x 4, x 5. x 6. Deretter

F = 15x 1 + 20x 2 +5x 3  maks.

La oss fylle ut den første simplekstabellen.

Vi vil fylle ut alle cellene basert på betingelsene for problemet.

For å fylle ut celle F 0 i den første tabellen, må du summere produktene til elementene i kolonne x 0 med elementene i kolonne c 0, dvs.

F 0 = 600∙0 + 520∙0 +600∙0 =0.

For å fylle målraden i den første tabellen, må du trekke den tilsvarende verdien c j fra summen av produktene til elementene i kolonne x j med elementene i kolonne c 0.

For kolonne x 1 vil verdien av dobbeltestimatet bli bestemt

(0∙80+0∙15+0∙5) – 15=-15;

For x 2: (0 35+0 60+0 5) – 20=-20;

x 3: (0 10+0 0+0 90) – 5=-5, osv.

Som et resultat vil den første simplekstabellen se slik ut:

Tabell 1

Før man går videre med løsningen er det nødvendig å sjekke om planen (løsningen) som er foreslått i tabellen er optimal.

Definisjon

Vedtaket vurderes optimal hvis alle tallverdier i målstrengen er positive.

Hvis den resulterende løsningen ikke er optimal, kan den forbedres. For å gjøre dette trenger du:

1. Velg den maksimale negative verdien for tallet i mållinjen i absolutt verdi.

I vårt eksempel vil dette tallet være (-20), plassert i "x 2"-kolonnen. Dette er verdien som setter nøkkelkolonne.

Merk:

Nøkkelkolonne viser hvilken av x j som skal inkluderes i den nye løsningen på problemet. I vårt tilfelle er det ukjente x 2.

Vennligst merk:

For å inkludere en ukjent x j i en ny løsning som forbedrer denne løsningen, er det nødvendig å utlede en av x j inkludert i den fra basisløsningen.

2. Velg minimumsverdien til kvotienten av elementene i kolonne x 0 til elementene i nøkkelkolonnen. Resultatene av disse beregningene legges inn i kolonnen "" i simplekstabellen.

I vårt eksempel er disse forholdstallene like:

Minimumsverdien tilsvarer x 5 og er lik 8,67. Dette forholdet setter nøkkelstreng.

Velg et element som ligger i skjæringspunktet mellom en nøkkelkolonne og en nøkkelrad, som kallesnøkkelelement .

I vårt eksempel er nøkkelelementet 60 og er plassert i skjæringspunktet mellom kolonne x 2 og rad x 5.

Merk:

En nøkkelkolonne kan ikke være en kolonne hvis elementer alle er negative eller null.

Sum matriseelementer etter rader(starter fra kolonne x 0 og slutter med kolonne x 6). De mottatte beløpene registreres i kolonnen "".

Konverter nøkkelstreng. For dette

Hvert nøkkelradelement er delt inn i et nøkkelelement, som starter med kolonneelementet "x0";

Fragment

I kolonne p 1 er x 2 skrevet i stedet for x 5;

Kolonne c j registrerer verdien av optimalitetskriteriet ved x 2, dvs. 20.

Alle andre elementer i simplekstabellen beregnes på nytt, i samsvar med grunnregelen. Denne regelen kalles diagonalregler eller trekantregler.

Når vi beregner verdien av målfunksjonen på nytt, får vi:

Vi fortsetter på samme måte med alle andre elementer i tabellen. Som et resultat får vi en ny simplekstabell.

Tabell 2.

Som det fremgår av tabellen. 2 ble den optimale løsningen ikke oppnådd, dvs. det er nødvendig å fortsette løsningen ved å bruke alle de betraktede reglene for transformering av simplekstabeller.

Merknad 1.

Kolonnen "" brukes til å kontrollere fremdriften til løsningen rad for rad. Summen av de nye verdiene til radelementene må være lik verdien av elementet i denne raden og kolonnen "", transformert i henhold til diagonalregelen.

Notat 2.

Verdien av målfunksjonen må være lik summen av produktene til elementene i kolonne j med elementene i kolonne x0.

Fullfør denne oppgaven selv. Resultatet skal være:

F=236,7; x 1 = 3,31; x 2 = 7,8; x 3 = 6,05.

Merknad 3.

I kolonnen "" er kvotientene for å dele elementet i nøkkelkolonnen og rad i med nøkkelelementet skrevet.

Merknad 4.

I den følgende tabellen starter du beregninger ved å bruke diagonalregelen fra målraden. Hvis alle estimater er positive, er den optimale løsningen funnet og det gjenstår bare å fylle ut x0-kolonnen. I dette tilfellet er det ikke nødvendig å beregne matrisegrunnlaget på nytt.

Denne metoden er en metode for målrettet oppregning av referanseløsninger til et lineært programmeringsproblem. Den tillater, i et begrenset antall trinn, enten å finne en optimal løsning eller å fastslå at det ikke finnes noen optimal løsning.

Hovedinnholdet i simpleksmetoden er som følger:

Angi en metode for å finne den optimale referanseløsningen
Angi metoden for overgang fra en referanseløsning til en annen, hvor verdien av objektivfunksjonen vil være nærmere den optimale, dvs. angi en måte å forbedre referanseløsningen på
Sett kriterier som lar deg umiddelbart slutte å søke etter støtteløsninger ved den optimale løsningen eller trekke en konklusjon om fraværet av en optimal løsning.

Algoritme av simpleksmetoden for å løse lineære programmeringsproblemer

For å løse et problem ved hjelp av simpleksmetoden, må du gjøre følgende:

Bring problemet til kanonisk form
Finn den første støtteløsningen med en "enhetsbasis" (hvis det ikke er noen støtteløsning, har ikke problemet en løsning på grunn av inkompatibiliteten til systemet med begrensninger)
Beregn estimater av vektordekomponeringer basert på referanseløsningen og fyll ut tabellen for simpleksmetoden
Hvis kriteriet for unikheten til den optimale løsningen er oppfylt, slutter løsningen av problemet
Hvis betingelsen for eksistensen av et sett med optimale løsninger er oppfylt, blir alle optimale løsninger funnet ved enkel oppregning

Et eksempel på å løse et problem ved hjelp av simpleksmetoden

Eksempel 26.1

Løs problemet ved å bruke simpleksmetoden:

Løsning:

Vi bringer problemet til kanonisk form.

For å gjøre dette introduserer vi en ekstra variabel x 6 med koeffisient +1 til venstre side av den første ulikhetsbegrensningen. Variabelen x 6 er inkludert i objektivfunksjonen med en koeffisient på null (dvs. den er ikke inkludert).

Vi får:

Vi finner den første støtteløsningen. For å gjøre dette, likestiller vi frie (uløste) variabler til null x1 = x2 = x3 = 0.

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

Vi beregner estimater av vektornedbrytninger forhold på grunnlag av referanseløsningen i henhold til formelen:

Δ k = C b X k - c k

C b = (c 1, c 2, ..., c m) - vektor av koeffisienter til objektivfunksjonen for de grunnleggende variablene
X k = (x 1k , x 2k , ... , x mk) - vektor for dekomponering av den tilsvarende vektoren A k i henhold til grunnlaget for referanseløsningen
C k er koeffisienten til objektivfunksjonen for variabelen x k.

Estimatene for vektorene som inngår i grunnlaget er alltid lik null. Referanseløsningen, ekspansjonskoeffisienter og estimater for utvidelser av vektorer av tilstander på grunnlag av referanseløsningen er skrevet i simplex bord:

Øverst i tabellen, for å lette beregningen av estimater, er koeffisientene til objektivfunksjonen skrevet. I første kolonne "B" er vektorene som er inkludert i grunnlaget for referanseløsningen skrevet. Rekkefølgen som disse vektorene er skrevet tilsvarer antallet tillatte ukjente i begrensningsligningene. I den andre kolonnen i tabellen "C b" er koeffisientene til objektivfunksjonen for de grunnleggende variablene skrevet i samme rekkefølge. Med riktig arrangement av koeffisientene til objektivfunksjonen i kolonnen "C b", er estimatene for enhetsvektorene som er inkludert i grunnlaget alltid lik null.

I den siste raden i tabellen med estimater av Δ k i kolonnen "A 0" er verdiene til objektivfunksjonen på referanseløsningen Z(X 1) skrevet.

Den initiale støtteløsningen er ikke optimal, siden i maksimalproblemet er estimatene Δ 1 = -2, Δ 3 = -9 for vektorene A 1 og A 3 negative.

I følge teoremet om å forbedre støtteløsningen, hvis i et maksimalt problem minst én vektor har et negativt estimat, kan du finne en ny støtteløsning der verdien av objektivfunksjonen vil være større.

La oss bestemme hvilken av de to vektorene som vil føre til en større økning i objektivfunksjonen.

Økningen til målfunksjonen finner du av formelen: .

Vi beregner verdiene til parameteren θ 01 for den første og tredje kolonnen ved å bruke formelen:

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

Vi finner økningen av objektivfunksjonen når vi innfører den første vektoren ΔZ 1 = - 6*(- 2) = 12, og den tredje vektoren ΔZ 3 = - 3*(- 9) = 27 i basisen.

Følgelig, for en raskere tilnærming til den optimale løsningen, er det nødvendig å introdusere vektor A3 i grunnlaget for referanseløsningen i stedet for den første vektoren til basis A6, siden minimum av parameteren θ 03 oppnås i den første raden ( l = 1).

Vi utfører Jordan-transformasjonen med elementet X13 = 2, vi får den andre referanseløsningen X2 = (0,0,3,21,42,0) med basis B2 = (A3, A4, A5). (Tabell 26.2)

Denne løsningen er ikke optimal, siden vektor A2 har et negativt estimat Δ2 = - 6. For å forbedre løsningen er det nødvendig å introdusere vektor A2 i grunnlaget for referanseløsningen.

Vi bestemmer nummeret på vektoren utledet fra grunnlaget. For å gjøre dette, beregner vi parameteren θ 02 for den andre kolonnen, den er lik 7 for l = 2. Følgelig utleder vi den andre basisvektoren A4 fra basisen. Vi utfører Jordan-transformasjonen med elementet x 22 = 3, vi får den tredje referanseløsningen X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabell 26.3).

Denne løsningen er den eneste optimale, siden for alle vektorer som ikke er inkludert i grunnlaget, er estimatene positive

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

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

Lineær programmeringsmetode i økonomisk analyse

Lineær programmeringsmetode gjør det mulig å rettferdiggjøre den mest optimale økonomiske løsningen under forhold med strenge restriksjoner knyttet til ressursene som brukes i produksjonen (anleggsmidler, materialer, arbeidsressurser). Bruken av denne metoden i økonomisk analyse gjør det mulig å løse problemer knyttet hovedsakelig til planlegging av aktivitetene til en organisasjon. Denne metoden hjelper til med å bestemme de optimale mengdene av produktutgang, samt instruksjonene for den mest effektive bruken av produksjonsressursene som er tilgjengelige for organisasjonen.

Ved hjelp av denne metoden løses de såkalte ekstreme problemene, som består i å finne ekstreme verdier, det vil si maksimum og minimum av funksjoner av variable mengder.

Denne perioden er basert på å løse et system av lineære ligninger i tilfeller der de analyserte økonomiske fenomenene er forbundet med en lineær, strengt funksjonell avhengighet. Den lineære programmeringsmetoden brukes til å analysere variabler i nærvær av visse begrensende faktorer.

Det er svært vanlig å løse det såkalte transportproblemet ved hjelp av den lineære programmeringsmetoden. Innholdet i denne oppgaven er å minimere kostnadene som påløper i forbindelse med drift av kjøretøy under eksisterende begrensninger med hensyn til antall kjøretøy, deres bæreevne, varigheten av deres drift, dersom det er behov for å betjene maksimalt antall kunder.

I tillegg er denne metoden mye brukt for å løse planleggingsproblemet. Denne oppgaven består av en slik fordeling av driftstid for personellet i en gitt organisasjon som vil være mest akseptabel både for medlemmene av dette personellet og for organisasjonens klienter.

Denne oppgaven er å maksimere antallet klienter som betjenes under betingelser med begrensninger på antall tilgjengelige ansatte, samt arbeidstidsfondet.

Dermed er den lineære programmeringsmetoden veldig vanlig i analysen av plassering og bruk av ulike typer ressurser, så vel som i prosessen med å planlegge og forutse organisasjoners aktiviteter.

Ikke desto mindre kan matematisk programmering også brukes på de økonomiske fenomenene, hvor forholdet mellom disse ikke er lineært. For dette formålet kan ikke-lineære, dynamiske og konvekse programmeringsmetoder brukes.

Ikke-lineær programmering er avhengig av den ikke-lineære naturen til den objektive funksjonen eller begrensningene, eller begge deler. Formene for den objektive funksjonen og ulikhetsbegrensningene i disse forholdene kan være forskjellige.

Ikke-lineær programmering brukes i økonomisk analyse, spesielt når man etablerer forholdet mellom indikatorer som uttrykker effektiviteten til en organisasjons aktiviteter og volumet av denne aktiviteten, strukturen til produksjonskostnader, markedsforhold, etc.

Dynamisk programmering er basert på å konstruere et beslutningstre. Hvert lag i dette treet fungerer som et stadium for å bestemme konsekvensene av en tidligere beslutning og for å eliminere ineffektive alternativer for den avgjørelsen. Dermed har dynamisk programmering en flertrinns, flertrinns natur. Denne typen programmering brukes i økonomisk analyse for å finne optimale muligheter for utvikling av en organisasjon både nå og i fremtiden.

Konveks programmering er en type ikke-lineær programmering. Denne typen programmering uttrykker den ikke-lineære naturen til forholdet mellom resultatene av en organisasjons aktiviteter og kostnadene. Konveks (aka konkav) programmering analyserer konvekse objektivfunksjoner og konvekse begrensningssystemer (gjennomførbarhetspunkter). Konveks programmering brukes i analyse av økonomiske aktiviteter med sikte på å minimere kostnader, og konkav programmering med sikte på å maksimere inntekter under eksisterende restriksjoner på virkningen av faktorer som påvirker de analyserte indikatorene på motsatt måte. Følgelig, med de typer programmering som vurderes, minimeres konvekse objektivfunksjoner, og konkave objektivfunksjoner maksimeres.

Hvis problemsetningen inneholder begrensninger med ≥-tegnet, kan de reduseres til formen ∑a ji b j ved å multiplisere begge sider av ulikheten med -1. La oss introdusere m tilleggsvariabler x n+j ≥0(j =1,m) og transformere restriksjonene til form av likheter

(2)

La oss anta at alle innledende variabler for oppgaven x 1 , x 2 ,..., x n er ikke-grunnleggende. Da vil tilleggsvariablene være grunnleggende, og en spesiell løsning på systemet av begrensninger har formen

x 1 = x 2 = ... = x n = 0, x n+ j = b j, j = 1,m. (3)

Siden i dette tilfellet verdien av målfunksjonen F 0 = 0, kan vi representere F(x) som følger:

F(x)=∑c i x i +F 0 =0 (4)

Den første simplekstabellen (simplekstabell 1) er kompilert basert på ligningene (2) og (4). Hvis tilleggsvariablene x n+j innledes med et “+”-tegn, som i (2), så legges alle koeffisientene foran variablene x i og det frie leddet b j inn i simplekstabellen uten endringer. Ved maksimering av målfunksjonen legges koeffisientene inn i den nederste raden i simplekstabellen med motsatte fortegn. De frie termene i simplekstabellen bestemmer løsningen på problemet.

Algoritmen for å løse problemet er som følger:

1. trinn. Medlemmene i kolonnen for gratis medlemmer vises. Hvis alle er positive, er det funnet en tillatt grunnløsning og man bør gå videre til trinn 5 i algoritmen, som tilsvarer å finne den optimale løsningen. Hvis den første simplekstabellen har negative frie termer, er løsningen ikke gyldig, og du bør gå til trinn 2.

2. trinn. For å finne en tillatt løsning gjennomføres den, og det er nødvendig å bestemme hvilken av de ikke-grunnleggende variablene som skal inkluderes i grunnlaget og hvilken variabel som skal fjernes fra grunnlaget.

Tabell 1.

x n

grunnleggende variabler	Gratis medlemmer under restriksjoner	Ikke-grunnleggende variabler
grunnleggende variabler	Gratis medlemmer under restriksjoner	x 1	x 2	...	x l	...
x n+1	b 1	en 11	en 12	...	en 1l	...	en 1n
x n+2	b 2	en 21	en 22	...	en 2l	...	en 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+r	b2	en r1	en r2	...	en rl	...	arn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+m	b m	en m1	en m2	...	en ml	...	en mn
F(x)maks	F 0	-c 1	-c 2	...	-c 1	...	-c n

For å gjøre dette, velg et av de negative elementene i kolonnen med frie termer (la det være b 2 ledende, eller løsende. Hvis det ikke er negative elementer i raden med en negativ fri term, er systemet med begrensninger inkonsekvent og problemet har ingen løsning.

Samtidig ekskluderes variabelen som er den første som endrer fortegn når den valgte NP x l øker fra BP. Dette vil være x n+r, hvis indeks r bestemmes fra betingelsen

de. variabelen som har det minste forholdet mellom frileddet og elementet i den valgte ledende kolonnen. Dette forholdet kalles simpleks forhold. Bare positive simpleksrelasjoner bør vurderes.

Linjen som tilsvarer variabelen x n+r kalles leder, eller tillater. Elementet i simplekstabellen a rl, som ligger i skjæringspunktet mellom den ledende raden og den ledende kolonnen, kalles det ledende eller løsende elementet.Å finne det ledende elementet avslutter arbeidet med hvert vanlig simpleksbord.

3. trinn. En ny simplekstabell beregnes, hvis elementer beregnes på nytt fra elementene i simplekstabellen i forrige trinn og er merket med et primtall, dvs. b" j, a" ji, c" i, F" 0 . Elementene beregnes på nytt ved å bruke følgende formler:

Først vil den nye simplekstabellen fylle ut raden og kolonnen som ledet i den forrige simplekstabellen. Uttrykk (5) betyr at elementet a" rl i stedet for det ledende elementet er lik det gjensidige til elementet i forrige simplekstabell. Elementene i raden a ri er delt med det ledende elementet, og elementene i kolonne a jl er også delt med ledende element, men tas med motsatt fortegn. Elementene b" r og c" l beregnes etter samme prinsipp.

Resten av formlene kan enkelt skrives ved hjelp av .

Rektangelet er konstruert i henhold til den gamle simplekstabellen på en slik måte at en av diagonalene dannes av de omkalkulerte (a ji) og ledende (a rl) elementene (fig. 1). Den andre diagonalen bestemmes unikt. For å finne et nytt element a" ji, trekkes produktet av elementene i den motsatte diagonalen delt på det ledende elementet fra elementet a ji (dette er indikert med "-" tegnet ved siden av cellen). Elementene b" j, (j≠r) og c"i omregnes på samme måte. (i≠l).

4. trinn. Analysen av den nye simplekstabellen begynner med 1. trinn i algoritmen. Handlingen fortsetter inntil en gjennomførbar grunnløsning er funnet, dvs. alle elementer i flytesøylen må være positive.

5. trinn. Vi mener det er funnet en tillatt grunnløsning. Vi ser på koeffisientene til linjen til målfunksjonen F(x) . Et tegn på optimaliteten til en simplekstabell er ikke-negativiteten til koeffisientene for ikke-grunnleggende variabler i F-raden.

Ris. 1. Rektangelregel

Hvis det blant koeffisientene til F-raden er negative (med unntak av den frie termen), må du gå videre til en annen grunnleggende løsning. Når du maksimerer objektivfunksjonen, inkluderer grunnlaget en av de ikke-grunnleggende variablene (for eksempel x l), hvis kolonne tilsvarer den maksimale absolutte verdien av den negative koeffisienten c l i den nederste raden i simplekstabellen. Dette lar deg velge variabelen hvis økning fører til en forbedring av målfunksjonen. Kolonnen som tilsvarer variabelen x l kalles ledende kolonne. Samtidig er den variabelen x n+r ekskludert fra grunnlaget, hvis indeks r bestemmes av minimum simpleksrelasjonen:

Raden som tilsvarer x n+r kalles ledende, og elementet i simplekstabellen a rl, som står i skjæringspunktet mellom ledende rad og ledende kolonne, kalles ledende element.

6. trinn. i henhold til reglene skissert i trinn 3. Prosedyren fortsetter til en optimal løsning er funnet eller det konkluderes med at den ikke eksisterer.

Under løsningsoptimalisering, hvis alle elementene i den innledende kolonnen er ikke-positive, kan ikke den innledende raden velges. I dette tilfellet er funksjonen i området for mulige løsninger på problemet ikke avgrenset ovenfor og F maks ->&∞.

Hvis en av grunnvariablene blir lik null ved neste trinn av å søke etter et ekstremum, kalles den tilsvarende grunnløsningen degenerert. I dette tilfellet oppstår en såkalt sykling, karakterisert ved at den samme kombinasjonen av BP begynner å gjenta seg med en viss frekvens (verdien av funksjonen F bevares) og det er umulig å gå over til en ny gjennomførbar grunnløsning . Looping er en av hovedulempene med simpleksmetoden, men det er relativt sjeldent. I praksis, i slike tilfeller, nekter de vanligvis å legge inn i grunnlaget variabelen hvis kolonne tilsvarer den maksimale absolutte verdien av den negative koeffisienten i målfunksjonen, og velger tilfeldig en ny basisløsning.

Eksempel 1. Løs problemet

maks(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Bruke simpleksmetoden og gi en geometrisk tolkning av løsningsprosessen.

En grafisk tolkning av løsningen på problemet er presentert i fig. 2. Den maksimale verdien av målfunksjonen oppnås ved toppunktet til ODZP med koordinater . La oss løse problemet ved å bruke simplekstabeller. La oss multiplisere den andre begrensningen med (-1) og introdusere tilleggsvariabler for å bringe ulikhetene til form av likheter, så

Vi tar startvariablene x 1 og x 2 som ikke-grunnleggende, og anser de ekstra x 3, x 4 og x 5 som grunnleggende og setter sammen en simplekstabell (simplekstabell 2). Løsningen som tilsvarer simplekstabellen. 2, er ikke gyldig; det ledende elementet er skissert og valgt i samsvar med trinn 2 i den forrige algoritmen. Følgende simplekstabell. 3 definerer en tillatt basisløsning, toppunktet til ODZP i fig. 1 tilsvarer den. 2 Det ledende elementet er skissert og valgt i samsvar med 5. trinn i problemløsningsalgoritmen. Bord 4 tilsvarer den optimale løsningen på problemet, derfor: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F maks = 20.

Ris. 2. Grafisk løsning på problemet