• Tidligere ble det vist at hvis et lineært programmeringsproblem har en optimal løsning, så er en av de optimale løsningene en tillatt grunnleggende løsning på dets system av begrensninger, som tilsvarer et visst hjørnepunkt av polyederet av tillatte løsninger av systemet.

• Det ble vist hvordan man finner denne optimale løsningen ved å bruke et begrenset søk etter grunnleggende løsninger på systemet med begrensninger for problemet. Etter hvert som dimensjonen n til problembegrensningssystemet øker, vokser imidlertid volumet av beregninger for å løse problemet ved hjelp av metoden for uttømmende oppregning av grunnleggende løsninger eksponentielt og blir uegnet i praksis.

Det er mulig å organisere en oppregning av kun tillatte basisløsninger og kraftig redusere antallet oppregnede løsninger dersom hver etterfølgende tillatelig grunnleggende løsning velg slik at den tilsvarende verdien av objektivfunksjonen forbedres eller i det minste ikke forverres. Denne tilnærmingen lar deg redusere antall trinn når du finner den optimale grunnløsningen. La oss forklare denne ideen grafisk.

La polygonet ABCDEFGH representere settet med tillatte løsninger av PLP med to variabler, og vektoren N - gradient av objektivfunksjonen.

• Vi må finne punktet til denne polygonen der objektivfunksjonen får den minste verdien.

• La den innledende gjennomførbare grunnløsningen av problemet som tilsvarer hjørnepunktet B bestemmes.

• Med et fullstendig søk av alle mulige grunnløsninger vil det være nødvendig å undersøke åtte slike løsninger som tilsvarer de åtte hjørnepunktene til polygonet.

• Imidlertid er det klart fra figuren at, tatt i betraktning retningen til gradienten N, er det mer lønnsomt å flytte til det nærliggende toppunktet C, deretter til det nærliggende toppunktet D, som tilsvarer den optimale grunnleggende løsningen av problemet.

• I stedet for åtte løsninger vil derfor kun tre gjennomførbare basisløsninger måtte vurderes.

• Ideen om sekvensiell forbedring av løsningen danner grunnlaget for den universelle metoden for å løse lineære programmeringsproblemer - simpleksmetoden.

Geometrisk betydning Simplexmetoden består i å utføre en sekvensiell overgang fra ett toppunkt av polyederet tillatte løsninger oppgave til naboen, der objektiv funksjon tar en verdi som ikke er dårligere enn den for forrige toppunkt. Denne overgangen fortsetter til en optimal løsning er funnet eller det oppdages at problemet ikke har en.

• Simplexmetoden og dens navn ble først foreslått av den amerikanske matematikeren John Danzig i 1947, selv om ideene til metoden ble publisert av den russiske matematikeren L.V. Kantorovich tilbake i 1939 i artikkelen "Matematiske metoder for organisering og planlegging av produksjon."

Simplexmetoden består av tre hovedelementer:

• å bestemme en innledende gjennomførbar grunnleggende løsning på problemet;

• regler for overgang til neste ikke-verst tillatte grunnløsning;

• kontrollere optimaliteten til løsningen som er funnet.

• Simplexmetoden brukes på et lineært programmeringsproblem skrevet i kanonisk form.

Enkle transformasjoner av et system av lineære ligninger

• La oss vurdere ZLP i kanonisk form. La et system med lineære ligninger gis:

• Vi må finne en ikke-negativ løsning på dette systemet som minimerer den lineære funksjonen

• La oss betegne - matrisen til ligningssystemet (1),

• – utvidet matrise av dette systemet.

Vi vil vurdere tilfellet når rekkene til matrisene A og B er like: , dvs. når system (1) har et uendelig antall løsninger. Vår oppgave er å finne ut om det finnes optimale løsninger på problemet i dette tilfellet og hvordan man finner dem.

• For definitivthetens skyld antar vi at de første r-kolonnene i matrise A er lineært uavhengige, deretter kan system (1) transformeres, ved å bruke den Gaussiske eliminasjonsmetoden, til formen:

• Dette systemet er ekvivalent med ligningssystemet (1). Odds kolonner

• danner grunnlaget for systemet av kolonner i matrisen til system (2), og derfor er variablene grunnleggende, og settet er et grunnleggende sett.

• For korthets skyld vil vi også kalle basissettet av variabler en basis, som betyr det tilsvarende grunnlaget for koeffisientkolonnene. De resterende variablene er gratis.

La oss uttrykke de grunnleggende variablene i system (3) i form av frie, og få system (4):

• (4)

• Det er vanlig å si at (4) er en generell løsning på ligningssystemet (1). Ved å tilordne nullverdier til de frie variablene, bestemmer vi verdiene til de grunnleggende variablene og konstruerer en grunnleggende løsning som tilsvarer det konstruerte grunnleggende settet med variabler.

• Så, den grunnleggende løsningen av system (1).

• I det følgende vil det vises at hvis system (1) har tillatte løsninger, kan det transformeres til form (3) slik at betingelse (5) er oppfylt

• Derfor vil vi anta at betingelse (5) er oppfylt. Da er grunnløsningen en gjennomførbar grunnløsning.

Ved å bruke likheter (4) kan vi uttrykke funksjonen f i form av frie variabler: (6) Nå kan vi beregne verdien av funksjonen f som tilsvarer grunnløsningen

• Ved å implementere ideen om simpleksmetoden vil vi lære å gå fra en gjennomførbar grunnleggende løsning til en annen. For å gjøre dette fjernes en av grunnvariablene xi fra grunnlaget og erstattes av en fri variabel xj.

• Med denne endringen i grunnlaget transformeres likningssystemet (4) og den lineære funksjonen (6). For å gjøre dette må den i-te ligningen til system (3) løses mht xj.

• Den resulterende ligningen er:

• Ved å erstatte dets uttrykk fra (7) i stedet for xj i de gjenværende ligningene til system (4) og inn i funksjon (6), får vi et nytt system tilsvarende system (1), som vil bli løst med hensyn til det nye grunnlaget

Koeffisienten aij, som indikerer at i basisen er xi erstattet av en fri variabel xj, kalles oppløsningselementet i simplekstabellen. Av likestilling (7) følger det at

• Siden den nye basisløsningen må være tillatt (ikke-negativ),

• da må betingelsen være oppfylt, som betyr . Med andre ord må det løsende elementet aij (xi er en fri variabel) i den jth kolonnen velges positivt. Vi vil kalle den beskrevne transformasjonen simpleks hvis det løsende elementet aij er valgt i henhold til følgende regel:

• 1. Element aij velg fra den jth kolonnen som inneholder positive elementer.

• 2. Hvis det er flere positive elementer i denne kolonnen, vil vi komponere forholdet mellom de frie leddene bk og koeffisientene akj>0.

• Av alle forholdene velger vi den minste. La det være :

• (8)

• Vi velger nevneren til denne brøken som det løsende elementet. Hvis flere av disse forholdstallene er minimale (like), vil vi velge hvilken som helst av disse nevnerne.

Teorem. Hvis i systemet med lineære ligninger (4) alle frie ledd er ikke-negative, vil de etter bruk av simplekstransformasjonen forbli ikke-negative.

• Bevis. La oss betegne de nye frie termene etter simplekstransformasjonen i (4) ved

• Deretter på

• Hvis akj>0, så følger det av (8).

• Hvis akj

• Hvis akj =0, da

• Konsekvens. Ved å bruke en simplekstransformasjon kan du gå fra en tillatt grunnleggende løsning av ZLP til en annen akseptabel grunnleggende løsning på dette problemet.

Ideen om simpleksmetoden

Enkel metode

I forrige avsnitt ble det vist at hvis oppgaven lineær programmering har en optimal løsning, så er en av de optimale løsningene en tillatt grunnleggende løsning av sitt system av begrensninger, som tilsvarer et visst hjørnepunkt av polyederet av tillatte løsninger av systemet. Det ble vist hvordan man finner denne optimale løsningen ved å bruke et begrenset søk etter grunnleggende løsninger på systemet med begrensninger for problemet. Etter hvert som dimensjonen n til problembegrensningssystemet øker, vokser imidlertid volumet av beregninger for å løse problemet ved hjelp av metoden for uttømmende oppregning av grunnleggende løsninger eksponentielt og blir uegnet i praksis. Det er mulig å organisere en oppregning av kun gjennomførbare basisløsninger og kraftig redusere antallet oppregnede løsninger dersom hver påfølgende tillatte grunnløsning velges slik at den tilsvarende verdien av målfunksjonen forbedres eller i det minste ikke forringes. Denne tilnærmingen lar deg redusere antall trinn når du finner den optimale grunnløsningen. La oss forklare denne ideen grafisk.

La polygonet ABCDEFGH representere settet med tillatte vedtak fra OPS med to variabler, og en vektor – gradient av objektivfunksjonen.

Vi må finne punktet til denne polygonen der objektivfunksjonen får den minste verdien. La den innledende tillatte grunnløsningen av problemet som tilsvarer hjørnepunktet B bestemmes Etter et fullstendig søk av alle tillatte grunnleggende løsninger, vil det være nødvendig å undersøke åtte slike løsninger som tilsvarer de åtte hjørnepunktene til polygonen. Imidlertid er det klart fra figuren at, med tanke på gradientens retning, er det mer lønnsomt å gå til nabotoppunktet C, deretter til nabotoppunktet D, som tilsvarer den optimale grunnleggende løsningen av problemet. I stedet for åtte løsninger vil derfor kun tre gjennomførbare basisløsninger måtte vurderes.

Ideen om sekvensiell forbedring av løsningen danner grunnlaget for den universelle metoden for å løse lineære programmeringsproblemer – simpleks metode.

Den geometriske betydningen av simpleksmetoden er at en sekvensiell overgang utføres fra ett toppunkt av polyederet av mulige løsninger på problemet til det naboliggende, der objektivfunksjonen ikke tar en verdi dårligere enn ved forrige toppunkt. Denne overgangen fortsetter til en optimal løsning er funnet eller det oppdages at problemet ikke har en.

Simplexmetoden og dens navn ble først foreslått av den amerikanske matematikeren John Danzig i 1947, selv om ideene til metoden ble publisert av den russiske matematikeren L.V. Kantorovich tilbake i 1939 i artikkelen " Matematiske metoder organisasjon og produksjonsplanlegging."

Simplexmetoden består av tre hovedelementer.

Kursk Academy of State and Municipal Service

Institutt for informasjon og teknologisfæresikkerhet

Essay

ved disiplin "Metoder for optimale løsninger"

om emnet "Ideen om simpleksmetoden"

Fullført av: 2. års student

Spesialiteter "Økonomi"

Moskaleva O.S.

Sjekket av: Ph.D., førsteamanuensis Pogosyan S. L.

Kursk – 2012

Innledning………………………………………………………………………………………………..3

1. Ideen om simpleksmetoden………………………………………………………….…4

2. Implementering av simpleksmetoden ved å bruke eksempelet…………………………..……6

3. Tabellbasert implementering av en enkel simpleksmetode……………….10

Konklusjon……………………………………………………………………………………………….15

Liste over referanser…………………………………..…….16

Introduksjon.

Simplex-metoden er et typisk eksempel på iterative beregninger som brukes til å løse de fleste optimaliseringsproblemer.

I beregningsskjemaet til simpleksmetoden implementeres en ordnet prosess der, med start fra et innledende tillatt hjørnepunkt (vanligvis opprinnelsen), påfølgende overganger gjøres fra ett tillatt ytterpunkt til et annet til et punkt som tilsvarer den optimale løsningen er funnet.

Ideen om simpleksmetoden

La oss vurdere en universell metode for å løse det kanoniske lineære programmeringsproblemet, med n variabler og m likhetsbegrensninger, kjent som simpleksmetoden.

Mange planer kanonisk problem- et konveks polyedrisk sett med et begrenset antall hjørnepunkter. Og hvis dette problemet har en optimal løsning, oppnås det i det minste på ett hjørnepunkt.

Ethvert hjørnepunkt er knyttet til en grunnleggende plan for problemet, der variablene er lik null, og de resterende variablene korresponderer lineært uavhengige kolonner tilstandsmatriser. Disse lineært uavhengige kolonnene danner en ikke-singular basismatrise.

Iterering over alle hjørnepunkter er beregningsmessig dyrt og derfor ineffektivt. I 1947 foreslo J. Dantzig en ryddig prosedyre for å telle opp hjørnepunkter, der man kan finne optimal løsning det er nok å undersøke bare en liten del av dem. Denne prosedyren kalles simpleks metode.

J. Danzig foreslo, når han flyttet fra et ytterpunkt til et annet, å bytte inn basismatrise bare én vektor. Dette betyr at under en slik overgang må vi ekskludere en av de grunnleggende variablene - gjør den ikke-grunnleggende ( lik null), og i stedet introduser en ny variabel blant de ikke-grunnleggende (null) - gjør den grunnleggende (positiv).

Det viser seg at geometrisk sett fører en slik utskifting til en overgang fra ett hjørnepunkt til et tilstøtende (nabo) forbundet med forrige punkt felles kant.

Fra alle nabopunkter velges den der målfunksjonen øker mest. Siden antall hjørnepunkter er endelig, gjennom et begrenset antall overganger toppunktet med høyeste verdi objektiv funksjon, eller objektivfunksjonens ubegrensning vil bli etablert på et ubegrenset sett med planer.

Generell ordning Simplexmetoden består av følgende hovedtrinn: trinn 0. Bestemmelse av startgrunnlaget og tilsvarende starthjørnepunkt (grunnlinje).

trinn 1. Kontrollerer gjeldende grunnlinje for optimalitet . Hvis optimalitetskriteriet er oppfylt, At planen er optimal og løsningen er komplett. Ellers gå til trinn 2.

steg 2. Finne variabelen introdusert i de grunnleggende. (Fra betingelsen om å øke den objektive funksjonen).

trinn 3. Finne en variabel ekskludert fra de grunnleggende variablene (Fra betingelsen om å bevare begrensningene til problemet).

steg 4 . Finne koordinatene til den nye grunnlinjen (tilstøtende hjørnepunkt). Gå til trinn 1.

Gjentatte trinn 1-4 danner én iterasjon av simpleksmetoden.

Fra dette diagrammet følger det at for det første, for å starte simpleksmetoden, må du ha et slags hjørnepunkt - en innledende grunnleggende plan, og for det andre må du være i stand til å undersøke det nåværende hjørnepunktet for optimalitet uten å beregne alle tilstøtende hjørner. Disse problemene løses enkelt hvis det kanoniske LP-problemet har en viss spesiell type.

Definisjon. Vi vil si at det kanoniske LP-problemet har en "foretrukket form" hvis: høyresiden av ligningene; betingelsesmatrisen inneholder en undermatrise av enhetsstørrelse.

Med andre ord, i enhver ligning er det en variabel med en koeffisient lik en, mangler i de andre ligningene. Den første betingelsen er ikke tyngende, siden i tilfellet med en negativ høyre side av en eller annen ligning, er det nok å multiplisere den med (-1). I et problem av foretrukket type er det veldig enkelt å finne den første grunnlinjen.

Implementering av simpleksmetoden ved hjelp av et eksempel

La oss demonstrere bruken av simpleksmetoden med et eksempel. Tenk på det kanoniske LP-problemet

f(x) = x 1 + 2x 2 + 0x 3 + 0x 4 > maks
-x 1 + 2x 2 +x 3 = 4,
3x 1 + 2x 2 +x 4 = 12,
x j? 0, j = 1,2,3,4.

Tilstandsmatrise EN = (EN 1 , EN 2 , EN 3 , EN 4), hvor

Målvektor c =(c 1, c 2, c 3, c 4) = (1, 2, 0, 0); vektor av høyre deler b=(b 1 ,b 2) = (4, 12).

Trinn 0. Finne starthjørnepunktet (grunnlinje).

Problemet har en foretrukket form, siden høyresiden av ligningene er positive, og kolonnene i tilstandsmatrisen EN 3, EN 4 danner en enhetsundermatrise. Dette betyr den innledende basismatrisen = (EN 3 ,A 4); x 3 Og x 4 - grunnleggende variabler x 1 Og x 2 - ikke-grunnleggende variabler, c B = (c 3, c 4) = = (0, 0).

Den første grunnlinjen ser ut som x 0 =(0, 0, x 3 , x 4) = (0, 0, 4, 12); f(x o) = 0.

Trinn 1. Sjekker den grunnleggende planen for optimalitet.

La oss beregne simpleksestimater for ikke-grunnleggende variabler ved å bruke formel (5.1)

? 1 = 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

Siden estimatene er negative, planen x- ikke optimalt. Vi vil se etter en ny grunnlinje (tilstøtende hjørnepunkt) med en større verdi av objektivfunksjonen.

Steg 2. Finne variabelen introdusert i grunnlaget.

Objektivfunksjonen kan økes ved å introdusere en av de ikke-grunnleggende variablene i de grunnleggende variablene (gjøre den positiv) x 1 eller x 2, siden begge estimater ? j x 2.

Trinn 3. Definisjon av en variabel utledet fra grunnlaget.

Etter å ha lagt inn variabelen i grunnlaget x 2 den nye planen vil se ut

x" =(0, x 2, x 3 , x 4).

Denne planen er ikke en grunnleggende, siden den inneholder bare én nullkoordinat, noe som betyr at det er nødvendig å gjøre en av variablene null (ekskluder fra grunnlaget) x 3 eller x 4. La oss erstatte koordinatene til planen x" =(0, x 2, x 3 ,x 4) i begrensningene til problemet. Vi får

2x 2 +x 3 = 4,

2x 2 + x 4 = 12.

La oss uttrykke de grunnleggende variablene herfra x 3 Og x 4 via variabel x 2 , lagt inn i grunnlaget.

x 3 = 4 - 2x 2,
x 4 = 12 - 2x 2 .

Altså variabler x 3 Og x 4 må være ikke-negative, får vi et system av ulikheter

4 - 2x 2 ? 0,
12 - 2x 2 ? 0.

Jo høyere verdi x 2 , jo mer den objektive funksjonen øker. Vi finner maksimal verdi en ny grunnleggende variabel som ikke bryter med begrensningene til problemet, det vil si tilfredsstiller betingelsene (2.8), (2.9).

La oss omskrive de siste ulikhetene i skjemaet

2x 2 ? 4,

2x 2 ? 12,

hvor kommer maksimumsverdien fra? x 2 = min ( 4/2, 12/2 ) = 2. Bytter denne verdien inn i uttrykk (2.6), (2.7) for x 3 Og x 4 , vi får x 3 = 0. Derfor x 3 utledet fra grunnlaget .

Trinn 4. Bestemme koordinatene til den nye grunnlinjen.

Den nye grunnlinjen (tilstøtende hjørnepunkt) er:

x" = (0, x 2, 0, x 4)

Grunnlaget for dette punktet består av kolonner EN 2 og EN 4 , så =( EN 2, EN 4). Dette grunnlaget er ikke enhetlig, siden vektoren EN 2 = (2,2), og derfor har ikke problem (2.2)-(2.5) en foretrukket form med hensyn til det nye grunnlaget. La oss transformere betingelsene for problem (2.3), (2.4) slik at det tar den foretrukne formen med hensyn til de nye grunnleggende variablene x 2, x 4, altså slik at variabelen x 2 ble inkludert i den første ligningen med en koeffisient lik én, og var ikke til stede i den andre ligningen. La oss omskrive likningene til problemet

- x 1 + 2 x 2 + x 3 = 4, (s 1)

3x 1 +2 x 2 + x 4 = 12. (s 2)

La oss dele den første ligningen med koeffisienten ved x 2 . Vi får en ny ligning = s 1/2 tilsvarende originalen

1/2 x 1 + x 2 + 1/2 x 3 = 2. ()

Vi bruker denne ligningen, som vi kaller oppløsning, for å eliminere variabelen x 2 fra den andre ligningen. For å gjøre dette må du multiplisere ligningen med 2 og trekke fra s 2 . Vi får = s 2 - 2= s 2 -s 1:

4 x 1 - x 3 + x 4 = 8. ()

Som et resultat mottok vi en ny "foretrukket" representasjon originalt problem i forhold til nye grunnleggende variabler x 2 , x 4:

f(x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 ? maks

1/2 x 1 + x 2 + 1/2 x 3 = 2 ()

4 x 1 - x 3 + x 4 = 8 ()

x j? 0, j = 1,2,3,4

Her erstatter representasjonen av den nye grunnlinjen x 1 = (0, x 2, 0, x 4), vil vi umiddelbart finne dens koordinater, siden verdiene til de grunnleggende variablene er lik høyresiden av ligningene

x" = (0, 2, 0, 8); f(x 1)=4.

Dette fullfører den første iterasjonen av simpleksmetoden. Deretter fortsetter prosessen med å løse problemet fra trinn 1, som består av å sjekke den funnet planen for optimalitet. Løsningen avsluttes når alle simpleksestimater av gjeldende grunnplan viser seg å være ikke-negative.

Vi vil ikke utføre den andre iterasjonen i henhold til skjemaet til den første, siden det er mer praktisk å utføre alle beregninger av simpleksmetoden i tabellform.

Tabellimplementering av en enkel simpleksmetode

Vi vil demonstrere den tabellformede implementeringen ved å bruke samme eksempel (2.2)-(2.5).

Trinn 0. Løsningen begynner med å konstruere en initial simplekstabell. Fylles ut først høyre del tabeller fra tredje kolonne. I to topplinjer navn er registrert problemvariabler (x 1, ...,x 4) og koeffisienter til objektivfunksjonen for disse variablene. Nedenfor er koeffisientene til likningene - elementer i tilstandsmatrisen EN, så under variabelen x 1 plassert kolonne EN 1, under variabel x 2 - kolonne EN 2 etc. Høyre side av begrensningene (tall) legges inn i høyre kolonne b i > 0).

Deretter finner vi kolonnene i tilstandsmatrisen som danner enhetsgrunnlaget - i vårt eksempel er dette EN 3 og EN 4 - og deres tilsvarende basisvariabler x 3, x 4 skriv i andre kolonne. Til slutt, i den første kolonnen skriver vi koeffisientene til objektivfunksjonen for de grunnleggende variablene.

Tabell 1- Innledende simplekstabell

	Grunnleggende variabler					Grunnleggende variabelverdier ( x B = b)
		x 1	x 2	x 3	x 4
	x 3	a 11 =-1
	x 4
Rangeringslinje ? j	? 1 = -1	? 2 = -2

Siden problemet har en foretrukket form, er verdiene til de grunnleggende variablene lik høyresiden av ligningene i den siste kolonnen. Siden ikke-basisvariablene er null, er den opprinnelige grunnlinjen

x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).

Trinn 1. For å sjekke planen x o for optimalitet beregner vi simpleksestimater for ikke-grunnleggende variabler x 1 Og x 2 i henhold til formelen

? j = B, A j > - c j.

? 1 = B, A 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

Med en tabellimplementering for beregning av poengsum ? 1 vi må finne summen av produktene til elementene i den første kolonnen ( c B) til de tilsvarende kolonneelementene EN 1 for en ikke-grunnleggende variabel x 1 . Poengsummen beregnes på samme måte ? 2 , som skalarproduktet av den første kolonnen ( c B) per kolonne ved variabel x 2.

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

Simplekse estimater er skrevet i den siste raden i simplekstabellen, som kalles deltaraden. I dette tilfellet fylles ikke bare cellene for ikke-grunnleggende variabler, men også de grunnleggende cellene. Det er lett å kontrollere at for grunnenhetskolonnene i tilstandsmatrisen er simpleksestimatene lik null. I den siste cellen i evalueringslinjen skriver vi verdien av objektivfunksjonen ved punktet xo. Merk at siden de ikke-grunnleggende koordinatene til grunnplanen er lik null, er det praktisk å beregne målfunksjonen ved å bruke formelen

f(x)= c B, x B >,

skalarisk multiplisere den første og siste kolonnen i tabellen.

Siden blant anslagene ? j Det er negativ , så planen x o er ikke optimal, og det er nødvendig å finne en ny grunnplan ved å erstatte en av grunnvariablene med en ny blant de ikke-grunnleggende.

Steg 2. Siden begge estimatene ? 1 Og ? 2 kan en hvilken som helst av variablene inkluderes i grunnlaget x 1, x 2 . La oss introdusere variabelen med det største absolutte negative estimatet i grunnlaget, dvs x 2 .

Kolonnen i simplekstabellen der variabelen som er lagt inn i grunnlaget befinner seg, kalles den ledende kolonnen.

I eksemplet vil den ledende kolonnen være kl x 2.

Trinn 3. Hvis alle elementene i den innledende kolonnen er negative, er det ingen løsning på problemet og maks f(x) ???. I eksemplet er alle elementene i den ledende kolonnen positive, derfor kan vi finne maksimumsverdien x 2 , hvor en av de gamle grunnvariablene går til null. Husk at den maksimale verdien x 2 = min(4/2, 12/2)=2.

I følge tabellen er denne verdien beregnet som den minste av forholdene mellom komponentene i grunnlinjen (fra den siste kolonnen) til den tilsvarende positivt elementer i den ledende kolonnen.

Det minste forholdet er i raden med basisvariabelen x 3. Så variabelen x 3 ekskludert fra de grunnleggende variablene ( x 3 = 0).

Linjen som inneholder variabelen som skal ekskluderes fra grunnlaget kalles den innledende linjen.

I eksemplet vil den innledende linjen være den første linjen.

Elementet som ligger i skjæringspunktet mellom den ledende raden og den ledende kolonnen kalles det ledende elementet.

I vårt tilfelle, det ledende element en 12 = 2.

Bord 2- Innledende simplekstabell med ledende rad og kolonne

	Grunnleggende endringer.					Grunnleggende variabelverdier	Ligninger
			x 2
c3=0	x 3	-1	2	1	0	4
			2
Rangeringslinje ? j	? 1 = -1	? 2 = -2

Trinn 4. For å få en ny grunnplan reduserer vi problemet til en ny foretrukket form med hensyn til de nye grunnvariablene.

For å gjøre dette, la oss bygge en ny simplekstabell, i den andre kolonnen i stedet for den ekskluderte variabelen x 3 la oss skrive en ny grunnleggende variabel x 2, og i den første kolonnen ( med B) i stedet for fra 3 La oss skrive ned koeffisienten til objektivfunksjonen ved x 2: c2=2. I den nye simplekstabellen er kolonnen kl x 2 må bli ett (det ledende elementet må være likt ett, og alle andre elementer må bli null). Dette oppnås ved hjelp av følgende tabellradtransformasjoner.

en. Vi deler alle elementene i ledende linje med ledende element og skriver dem i samme linje som en ny simpleks tabeller.

Den resulterende strengen p 1" La oss kalle det tillatt.

b. Til den gjenværende andre linjen legger vi til oppløsningslinjen, multiplisert med et slikt tall at elementet i den ledende kolonnen blir null.

p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.

c. La oss fylle ut den siste linjen ved å beregne estimatene ? j " = - - c j, Hvor c B ", A j " - de tilsvarende kolonnene i den nye simplekstabellen, og verdien av objektivfunksjonen f(x)= .

Vi får en andre simplekstabell med et nytt grunnlag.

Tabell 3- Resultat av den første iterasjonen

	Grunnleggende endringer.					Grunnleggende variabelverdier	Ligninger
		-1/2
	x 4	4	0	-1	1	8	p 2 " =p 2 - p 1
vurderinger ? j"	-2

Ny grunnlinje x " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ). Siden vurderingen ? 1 = -2 så planlegg x " ikke optimalt. For å flytte til en ny grunnplan (av nabohjørnepunktet), vil vi utføre en ny iterasjon av simpleksmetoden.

Fordi? 1 så introduseres en variabel i grunnlaget x 1. Den første kolonnen som inneholder x 1 - ledende.

Vi finner sammenhengene mellom komponentene i grunnplanen og de tilsvarende positivt elementer i den ledende kolonnen og ta raden med det minste forholdet som ledende rad. I tabell 2, i den ledende kolonnen er bare det andre elementet større enn null (= 4), derfor den andre linjen vil være den ledende, og grunnlaget som ligger i den variabel x 4 med forbehold om utelukkelse fra grunnlaget.

Vi velger den ledende kolonnen og ledende raden og ved deres skjæringspunkt finner vi ledende element (= 4).

Vi bygger en ny (tredje) simplekstabell, og erstatter den grunnleggende variabelen i den x 4 på x 1 , og igjen transformere tabellradene slik at det ledende elementet blir lik en, og de resterende elementene i ledende kolonne blir null. For å gjøre dette, del den ledende (andre) linjen med 4, og legg til den resulterende andre linjen delt på 2 til den første linjen. Siste linje beregne ved hjelp av formler for simpleksestimater ? j"" = "", A j""> - c j, Hvor c B"", A j"" - de tilsvarende kolonnene i den nye simplekstabellen. Verdien av målfunksjonen på den nye grunnlinjen er funnet ved hjelp av formelen f(x"")= "", x B"" >.

Tabell 4- Resultat av den andre iterasjonen

	Grunnleggende endring.					Grunnleggende variabelverdier	ligninger
							p 1 "" = p 1 "+p 2 ""/2
							p 2 "" = p 2 "/4
vurderinger ? j ""					f(x"")= 8

Ny grunnlinje x "" = (x 1, x 2, 0, 0) = (2, 3, 0, 0 ). Siden alle estimater er ikke-negative, så planen x ""- optimal plan.

Dermed, x* = (2, 3, 0, 0 ), f(x*) = 8.

KONKLUSJON

De vurderte metodene for å løse lineære programmeringsproblemer er mye brukt i praksis. Det bør imidlertid bemerkes at

matematisk modell alltid fattigere enn ekte økonomisk system. Den beskriver dette systemet bare omtrentlig, fremhever noen egenskaper og neglisjerer andre. For å kompensere for denne mangelen i matematisk økonomi, utvikles flere typer modeller, som hver er designet for å reflektere ett spesifikt aspekt av den økonomiske virkeligheten, slik at når man løser et spesifikt økonomisk problem, er det mulig å velge en modell som passer best til det. .

LISTE OVER BRUKTE REFERANSER

1. Ashmanov S.A. Lineær programmering. - M.: Nauka, 1981.

En av de universelle metodene er simpleksmetoden. I simpleksmetoden foretas et rettet søk av referanseplaner, i den forstand at ved flytting fra en referanseplan til en annen øker målfunksjonen. La problemet skrives inn kanonisk form:

f=(n; j=1)ΣCj*Xj (maks)

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

Xj>=0 (j=1,n)

Hvis problemet er løsbart, faller dens optimale plan sammen med i det minste med en av støtteløsningene til ligningene. Denne referanseplan og er funnet ved bruk av simpleksmetoden som et resultat av et bestilt søk i referanseplaner. Rekkefølge forstås på den måten at når du flytter fra en referanseplan til en annen, øker de tilsvarende verdiene til målfunksjonen. Derfor kalles simpleksmetoden m-house konsekvent forbedringsplan.

Generell idé enkel metode er så enkelt. m-d er delt inn i 2 stadier:

1. finne den første referanseplanen;

2. konsekvent forbedring opp til å finne den optimale, der målfunksjonen når sin maksimale verdi.

8. Et tegn på optimaliteten til støtteplanen til ZLP.

Støtteplanattributt er ikke-negativiteten til elementene i kolonnen med frie termer, ikke medregnet elementene i f-raden. Tegn på en optimal plan- hvis i simplex bord inneholder en støtteplan, alle elementer i f-strengen som er ikke-negative (ikke medregnet fribegrepet booo), så er denne støtteplanen optimal. Hvis i relasjonen f=boo-(n-m;j=1)Σboj*Xj+m verdien av alle frie variabler er lik null, vil objektivfunksjonen være lik frileddet f(vektorXo)=boo. Med økende verdier av gratis variabel funksjon vil begynne å avta, derfor får funksjonen med Ho-planen en ekstrem verdi.

9. Finne den første referanseplanen til ZLP.

For å finne den første referanseplanen kan vi foreslå følgende algoritme:

1. skriv oppgaven i form av en Jordan-tabell slik at alle elementene i kolonnen med frie termer er ikke-negative, dvs. ulikheten aio>=0 (i=1,m) ble tilfredsstilt. De ligningene der de frie leddene er negative, multipliseres først med -1.

		-x1….. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	amo	am1…..amn
f=		-c1…. -cn

Transformer tabellen ved å bruke Jordan-elimineringstrinn, og bytt ut nullene i venstre kolonne med tilsvarende x. Samtidig, på hvert trinn permissive kan velges enhver kolonne som inneholder minst ett positivt element. Den løsende raden bestemmes av det minste av forholdet mellom de frie leddene og de tilsvarende positive elementene i den løsende kolonnen. Hvis det i elimineringsprosessen støtes på en 0-rad, hvis elementer er null, og frileddet er ikke null, så har systemet med begrensningsligninger ingen løsninger. Hvis vi møter en 0-rad der det, bortsett fra frileddet, ikke er andre positive elementer, har ikke settet med restriktive ligninger ikke-negative løsninger If settet med restriktive ligninger ledd, så etter et visst antall trinn vil alle nullene i venstre kolonne bli erstattet med x og derved oppnå en viss basis, og følgelig en tilsvarende referanseplan.

10. Finne den optimale referanseplanen for ZLP.

Ho sin første støtteplan blir undersøkt for optimalitet.

Hvis det ikke er negative elementer i f-raden (ikke medregnet frileddet), er -planen optimal. Hvis det heller ikke er nullelementer i f-raden, så er det bare en optimal plan; hvis det er minst én null blant elementene, da optimale planer uendelig antall. Hvis det er minst ett negativt element i f-raden, og det ikke er noen positive elementer i den tilsvarende kolonnen, er objektivfunksjonen ikke begrenset i gyldig område. Problemet er ikke løsbart. Hvis det er minst ett negativt element i f-raden, og i hver kolonne med et slikt element er det minst ett positivt element, så kan du flytte til en ny referanseplan som er nærmere den optimale. For å gjøre dette tas kolonnen med et negativt element i f-raden som ettergivende; De bestemmer oppløsningsstrengen fra minimum simpleksrelasjonen og utfører Jordan-elimineringstrinnet. Den resulterende referanseplanen undersøkes igjen for optimalitet. Dette gjentas til den optimale referanseplanen er funnet eller problemets uløselighet er etablert.

11. Tegn på ubegrensethet til den objektive funksjonen på et sett med planer og geometrisk illustrasjon.

Et tegn på at objektivfunksjonen er ubegrenset, er at i prosessen med å søke etter en optimal plan, oppnås en kolonne med et negativt element i f-raden som ikke inneholder et eneste positivt element.

12. Tegn på uendelighet av settet med optimale planer og geometrisk illustrasjon.

Et tegn på uendeligheten til et sett med planer er tilstedeværelsen i f-raden til et simplekspunkt som inneholder den optimale planen for minst ett nullelement, uten å telle frileddet. La en optimal plan X1* bli funnet, med ett nullelement i f-raden. En annen optimal plan X2* finner du ved å velge en kolonne med et nullelement i f-raden som oppløsning. Resten er optimalisert. planer kan defineres som en lineær kombinasjon:

Х1*= λХ1*+(1-λ)Х2* 0=<λ<=λ

Finne den optimale planen. Denne metoden er universell, den tillater å løse lineære programmeringsproblemer av enhver dimensjon i en generell formulering. Imidlertid krever denne metoden å redusere det opprinnelige problemet til kanonisk form.

Hovedideen med simpleksmetoden er å flytte fra ett toppunkt av ODR til et annet slik at verdien av CF reduseres med hver overgang. Slik kan du komme deg fra et hvilket som helst toppunkt til det optimale og få den optimale planen.

For eksempel: la referanseplanen X =(x1,x2,…,xm,0,0,…,0) og det tilhørende systemet av lineært uavhengige vektorer: A1,A2,…,Am være kjent, så for denne referanseplanen du kan beregne verdien CF Z=(c1x1+c2x2+…+cmxm) og skrive begrensningsbetingelsene i følgende form x1A1+x2A2+…+xmAm=b

Siden vektorene A1, A2,…, Am er lineært uavhengige, kan enhver vektor Aj utvides til disse vektorene: Aj=x1jA1+x2jA2+…+xmjAm (*) La oss introdusere verdiene Zj Zj=x1jc1+x2jc2+…+ xmjcm, hvor xij er koeffisienten som tilsvarer Ai i ekspansjonsvektoren Aj ved basisvektorer

Teorem 1: Forbedring av referanseplanen

Hvis for noen indeks j betingelsen Zj-Cj>0 er oppfylt, kan verdien av CF reduseres og:

· hvis CF er begrenset nedenfra, er det mulig å konstruere en referanseplan med en mindre CF-verdi, den samme forrige

· hvis TF ikke er begrenset nedenfra, så er det mulig å konstruere en plan som tilsvarer en vilkårlig liten verdi av TF

Teorem 2: optimalitetskriterium for referanseplanen

Hvis for noen indeks j i referanseplanen ulikheten Zj-Cj0. La dette minimum oppnås for vektoren Ak, så er det denne vektoren som må utledes fra basisen. Linjen som tilsvarer denne vektoren kalles en guide og er betegnet "à".

4. Etter å ha definert kolonne- og radguidene, fyll ut en ny simplekstabell. I en slik tabell vil Ai vises i stedet for ledelinjen. Å fylle ut en ny tabell begynner med en ledelinje. Som en komponent i referanseplanen er verdien Ө0 X'l=Ө0=Xk/Xkl skrevet der, de resterende elementene i denne linjen bestemmes av formelen X'lj X'lj=Xkj/Xkl hvor Xkl er elementet plassert i skjæringspunktet mellom rad- og kolonneguidene, spesielt på den er alle tidligere elementer i ledelinjen delt, og en enhet vises automatisk i stedet for det tidligere Xkl-elementet. Den generelle regelen for omregning av en ledelinje kan skrives som følger: Ak (nytt element i ledelinjen) = (gammelt element i ledelinjen)/(element som står i skjæringspunktet mellom ledekolonnen og raden)

5. Alle elementer i de gjenværende radene i tabellen beregnes på nytt, inkludert den ekstra nederste raden. Omberegning utføres i henhold til formlene

· for komponenter i referanseplanen X’i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil

· for komponenter utvidet over basis X’ij=Xij-(Xkj/Xkl)*Xil

· for tilleggslinjen Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

Alle disse formlene er bygget i henhold til én regel:

(ny e-post)=(gammel e-post)-(ny e-post for radretning)*(e-post for kolonneretning i den tilsvarende raden)

Etter å ha fylt ut den nye simplekstabellen, skjer overgangen til det andre trinnet av algoritmen.

Metoder for naturlig og kunstig grunnlag. Grunnleggende begreper, algoritmer for metoder.

For de fleste lineære programmeringsproblemer oppstår det vanskeligheter med å løse dem knyttet til å bestemme den første referanseplanen og den innledende simplekstabellen som alle iterasjoner starter fra. Dette skyldes det faktum at i reelle problemer blant vektorene Ai er det ingen vektorer som inneholder bare en ikke-null komponent, dvs. vektorer av formen (0,0,0,...,0,1,0,...,0) eller antallet er ikke nok til å danne grunnlag. Det vil si at det ikke er mulig å danne et naturlig grunnlag.

Den kunstige basismetoden er basert på kunstig introduksjon av slike vektorer i den matematiske modellen av problemet.

La en ZLP av kanonisk form gis

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+…+an1xn=b1

a12x1+a22x2+…+an2xn=b2

…………………………

a1mx1+a2mx2+…+anmxn=bm

Deretter konverteres det til skjemaet

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+…+an1xn+xn+1=b1

a12x1+a22x2+…+an2xn+xn+2=b2

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

a1mx1+a2mx2+…+anmxn+xn+m=bm

Der M er uendelig store tall. I den resulterende oppgaven er startgrunnlaget umiddelbart synlig. vektorene med kunstig introduserte variabler xn+1, xn+2,..., xn+m bør tas som den. Siden disse vektorene vil ha formen: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Det transformerte problemet løses deretter ved hjelp av simpleksmetoden algoritmen. Den første referanseplanen for det transformerte problemet har formen (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, bm). Den originale simplekstabellen ser slik ut:

Basis	koeffisient CF	Plan	C1	C2	…	Cn	M	M	…	M
			A1	A2	…	An	En+1	An+2	…	An+m
En+1	M	b1	a11	a21	…	an1	1	0	…	0
An+2	M	b2	a12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	M	bm	kl. 1 m	a2m	…	anm	0	0	…	1
			Z0

Vi bestemmer elementene i tilleggslinjen ved å bruke formlene Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

For å bestemme forskjellene Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

Etter å ha mottatt den originale simplekstabellen, blir den transformert, og prøver å utlede fra basisvektorene som tilsvarer de introduserte tilleggsvariablene.

Siden M er et veldig stort tall, vil det være mange positive tall blant forskjellene Zj-Cj. Det vil si at det vil være mange kandidater for inkludering i grunnlaget blant vektorene A1,A2,...,An

Hvis en vektor tilsvarer de kunstig introduserte variablene xn+1,xn+2,...,xn+m, er den tilsvarende vektoren utledet fra basisen, og simplekskolonnen i tabellen med denne vektoren er krysset ut og returneres ikke til det igjen. På slutten av simplekstabelltransformasjonen er to alternativer mulige:

· alle vektorer som tilsvarer kunstige variabler er utledet fra grunnlaget, i dette tilfellet vil alle kolonnene i simplekstabellen som tilsvarer tilleggsvariabler forsvinne, og det opprinnelige problemet vil bli løst

· den resulterende optimale planen vil fortsatt inneholde en tilleggsvariabel, dette betyr at ODD for det opprinnelige problemet er tomt, dvs. begrensningene er motstridende, derfor har det opprinnelige problemet ingen løsninger i det hele tatt.

Problemer med dobbelt lineær programmering. Uttalelse av problemer, deres egenskaper.

Symmetriske doble problemer:

Første standardskjema

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+…+an1xn>=b1

a12x1+a22x2+…+an2xn>=b2

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

a1mx1+a2mx2+…+anmxn>=bm

Dobbelt problem

d(y)=b1y1+b2y2+…+bmymàmax

a11y1+a12y2+…+a1mym=0, V j=1,m

Ikke-sevenære par med doble problemer

Det opprinnelige problemet i kanonisk form

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+..+an1xn=b1

a12x1+a22x2+..+an2xn=b2

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