Enkel metode forklart med et eksempel. Enkel metode for å løse lineære programmeringsproblemer

For å selge tre grupper av varer, har et kommersielt foretak tre typer begrensede materielle og monetære ressurser i mengden b 1 = 240, b 2 = 200, b 3 = 160 enheter. Samtidig, for salg av 1 gruppe varer for 1 tusen rubler. vareomsetning, ressursen til den første typen forbrukes i mengden a 11 = 2 enheter, ressursen til den andre typen i mengden 21 = 4 enheter, ressursen til den tredje typen i mengden a 31 = 4 enheter. For salg av 2 og 3 grupper av varer for 1 tusen rubler. omsetningen forbrukes i henhold til ressursen til den første typen i mengden a 12 = 3, a 13 = 6 enheter, ressursen til den andre typen i mengden a 22 = 2, a 23 = 4 enheter, ressursen til den tredje typen i mengden av en 32 = 6, en 33 = 8 enheter. Fortjeneste fra salg av tre grupper av varer for 1 tusen rubler. omsetningen er henholdsvis c 1 = 4, c 2 = 5, c 3 = 4 (tusen rubler). Bestem det planlagte volumet og strukturen for handelsomsetningen slik at fortjenesten til handelsbedriften maksimeres.

Til det direkte problemet med omsetningsplanlegging, løses ved simpleksmetoden, komponere dobbelt problem lineær programmering.
Installer konjugerte par av variabler rett og dobbelt problem.
I henhold til konjugerte par av variabler, fra løsningen av det direkte problemet får vi løsning av det doble problemet, der den er produsert ressursvurdering, brukt på salg av varer.

Løse problemet ved hjelp av simpleksmetoden

La x 1, x 2, x 3 være antall solgte varer, i tusen rubler, henholdsvis 1, 2, 3 grupper. Da matematisk modell oppgaven har formen:

F = 4 x 1 + 5 x 2 + 4 x 3 ->maks

0)))(~)" title="delim(lbrace)(matrise(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Vi løser simpleksmetoden.

Vi introduserer tilleggsvariabler x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 for å transformere ulikhetene til likheter.

La oss ta x 4 = 240 som grunnlag; x 5 = 200; x 6 = 160.

Vi legger inn dataene simplex bord

Simplex bord nr. 1

Objektiv funksjon:

0 240 + 0 200 + 0 160 = 0

Vi beregner estimater ved å bruke formelen:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Siden det er negative estimater er ikke planen optimal. Laveste poengsum:

Vi introduserer variabelen x 2 i grunnlaget.

Vi definerer en variabel som kommer ut fra grunnlaget. For å gjøre dette finner vi det minste ikke-negative forholdet for x2-kolonnen.

= 26.667

Minste ikke-negative: Q 3 = 26,667. Vi utleder variabelen x 6 fra grunnlaget

Del den tredje linjen med 6.
Fra den første linjen trekker du den tredje linjen, multiplisert med 3
Fra den andre linjen trekker du den tredje linjen, multiplisert med 2

Vi beregner:

Vi får et nytt bord:

Simplex bord nr. 2

Objektiv funksjon:

0 160 + 0 440/3 + 5 80/3 = 400/3

Vi beregner estimater ved å bruke formelen:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Siden det er et negativt estimat Δ 1 = - 2/3, er ikke planen optimal.

Vi introduserer variabelen x 1 i grunnlaget.

Vi definerer en variabel som kommer ut fra grunnlaget. For å gjøre dette finner vi det minste ikke-negative forholdet for kolonnen x 1.

Minste ikke-negative: Q 3 = 40. Vi utleder variabelen x 2 fra grunnlaget

Del den tredje linjen med 2/3.
Fra den andre linjen trekker du den tredje linjen, multiplisert med 8/3

Vi beregner:

Vi får et nytt bord:

Simplex bord nr. 3

Objektiv funksjon:

0 160 + 0 40 + 4 40 = 160

Vi beregner estimater ved å bruke formelen:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Siden det ikke er noen negative vurderinger, er planen optimal.

Løsning på problemet:

Svare

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F maks = 160

Det vil si at det er nødvendig å selge den første typen varer i mengden 40 tusen rubler. Produkter av type 2 og 3 trenger ikke selges. I dette tilfellet vil maksimal fortjeneste være F max = 160 tusen rubler.

Løsning på det doble problemet

Det doble problemet har formen:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Title="delim(lbrace)(matrise(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Vi introduserer tilleggsvariabler y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 for å transformere ulikhetene til likheter.

Konjugerte par av variabler av de direkte og doble problemene har formen:

Fra den siste simplekstabellen nr. 3 i det direkte problemet finner vi løsningen på det dobbelte problemet:

Z min = Fmaks = 160;
y1 = A4 = 0; y2 = Δ5 = 0; y3 = A6 = 1; y4 = Δ1 = 0; y5 = A2 = 1; y6 = A3 = 4;

Lineære programmeringsproblemer. Det er i en sekvensiell konstruksjon som karakteriserer prosessen under vurdering. Løsningen er delt inn i tre hovedtrinn: valg av variabler, konstruksjon av et system av begrensninger og søk etter en objektiv funksjon.

Basert på denne inndelingen kan problemtilstanden omformuleres som følger: ekstremum av objektivfunksjonen Z(X) = f(x1, x2, … ,xn) → maks (min) og de tilsvarende variablene, hvis det er kjent at de tilfredsstille systemet med begrensninger: Φ_i ( x1, x2, … ,xn) = 0 for i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 for i = k+1, k+ 2, …, m.

Systemet med restriksjoner må bringes til kanonisk form, dvs. til systemet lineære ligninger, hvor antall variabler flere tall ligninger (m > k). I dette systemet vil det helt sikkert være variabler som kan uttrykkes gjennom andre variabler, og hvis dette ikke er tilfelle, så kan de introduseres kunstig. I dette tilfellet kalles de første basis eller kunstig grunnlag, og de andre er gratis.

Det er mer praktisk å vurdere simpleksmetoden på spesifikt eksempel. La det bli gitt lineær funksjon f(x) = 6x1 + 5x2 + 9x3 og systemet med restriksjoner: 5x1 + 2x2 + 3x3 ≤ 25; (x).

Løsning På det første trinnet, spesifiser den første (referanse) løsningen av ligningssystemet absolutt tilfeldig, som må tilfredsstille dette restriksjonssystemet. I i dette tilfellet det kreves innføring av kunstig, dvs. grunnleggende variabler x4, x5 og x6 som følger: 5x1 + 2x2 + 3x3 + x4 = 25;

Som du kan se, har ulikhetene blitt transformert til likheter takket være de adderte variablene x4, x5, x6, som er ikke-negative størrelser. Dermed har du brakt systemet til dets kanoniske form. Variabelen x4 inngår i den første ligningen med koeffisienten 1, og i den andre ligningen med koeffisienten 0, gjelder det samme for variablene x5, x6 og de tilsvarende ligningene, som tilsvarer definisjonen av grunnlaget.

Du har forberedt systemet og funnet den første referanseløsningen – X0 = (0, 0, 0, 25, 20, 18). Presenter nå koeffisientene til variablene og de frie leddene til ligningene (tallene til høyre for "="-tegnet) i form av en tabell for å optimere ytterligere beregninger (se figur).

Essensen av simpleksmetoden er å bringe denne tabellen til en form der alle tallene i rad L vil være ikke-negative verdier. Hvis det viser seg at dette er umulig, så har ikke systemet en optimal løsning i det hele tatt. Velg først det minste elementet i denne linjen, som er -9. Nummeret er i tredje kolonne. Konverter den tilsvarende x3-variabelen til en basisvariabel. For å gjøre dette, del linjen med 3 slik at cellen ender opp med 1.

Nå trenger du cellene og snu til 0. For å gjøre dette, trekk fra de tilsvarende tallene i den tredje raden med 3. Fra elementene i den andre raden - elementene i den tredje, multiplisert med 2. Og til slutt, fra elementene i L-raden - multiplisert med (-9). Du har fått den andre referanseløsningen: f(x) = L = 54 med x1 = (0, 0, 6, 7, 8, 0).

Tråd, knapper og stoff brukes til å lage tre typer skjorter. Lagre av tråd, knapper og stoff, normene for deres forbruk for å sy en skjorte er angitt i tabellen. Finne maksimal fortjeneste Og optimal plan utgivelse av produkter som gir det (finn).

skjorte 1

skjorte 2

skjorte 3

Reserver

tråder (m.)

knapper (stk.)

640

tekstil (

Fortjeneste (r.)

Problemløsning

Modellbygg

Gjennom og antall skjorter av 1., 2. og 3. type beregnet på utgivelse.

Da vil ressursrestriksjonene se slik ut:

I tillegg, i henhold til oppgavens betydning

Målfunksjon som uttrykker mottatt fortjeneste:

Vi får følgende lineære programmeringsproblem:

Redusere et lineært programmeringsproblem til kanonisk form

La oss redusere problemet til kanonisk form. La oss introdusere flere variabler. Vi introduserer alle tilleggsvariabler i objektivfunksjonen med en koeffisient lik null. Vi legger til flere variabler på venstre side av restriksjonene som ikke har en foretrukket form, og vi oppnår likheter.

Løse problemet ved hjelp av simpleksmetoden

Fyll ut simplekstabellen:

Siden vi løser problemet maksimalt, indikerer tilstedeværelsen av negative tall i indekslinjen når vi løser problemet maksimalt at vi optimal løsning ikke mottatt og at det er nødvendig å flytte fra tabellen for den 0. iterasjonen til den neste.

Vi fortsetter til neste iterasjon som følger:

ledende kolonne tilsvarer

Nøkkelraden bestemmes av minimumsforholdet mellom ledige medlemmer og medlemmer av den ledende kolonnen (enkle relasjoner):

I skjæringspunktet mellom nøkkelkolonnen og nøkkelraden finner vi aktiveringselementet, dvs. 9.

Nå fortsetter vi med å kompilere den første iterasjonen: I stedet for en enhetsvektor introduserer vi vektoren .

I nytt bord i stedet for aktiveringselementet skriver vi 1, alle andre elementer i nøkkelkolonnen er null. Nøkkelstrengelementene er delt inn i aktiveringselementet. Alle andre elementer i tabellen beregnes ved å bruke rektangelregelen.

Nøkkelkolonnen for 1. iterasjon tilsvarer

Det løsende elementet er tallet 4/3. Vi utleder vektoren fra basisen og introduserer vektoren i stedet. Vi får tabellen for 2. iterasjon.

Nøkkelkolonnen for 2. iterasjon tilsvarer

Vi finner nøkkellinjen, for dette definerer vi:

Det løsende elementet er tallet 10/3. Vi utleder vektoren fra basisen og introduserer vektoren i stedet. Vi får tabellen for den tredje iterasjonen.

№

c B

A o

x 1

x 2

x 3

x 4

x 5

x 6

Enkelt

forhold

x 4

32/3

x 5

640

x 6

F j - c j

-2

-5

-4

x 2

32/3

1/9

1/3

1/9

x 5

1600/3

170/9

80/3

-10/9

x 6

68/3

7/9

4/3

-2/9

F j - c j

160/3

-13/9

-7/3

5/9

x 2

-1/12

1/6

-1/4

x 5

10/3

-20

x 3

7/12

-1/6

3/4

204/7

F j - c j

-1/12

1/6

7/4

x 2

1/4

1/40

-3/4

x 1

3/10

-6

x 3

-3/4

-7/40

17/4

F j - c j

1/4

1/40

5/4

I indeksraden er alle termer ikke-negative, så følgende løsning på det lineære programmeringsproblemet oppnås (vi skriver det ut fra kolonnen med frie termer):

Det er nødvendig å sy 24 skjorter av 1. type, 7 skjorter av 2. type og 3 skjorter av 3. type. I dette tilfellet vil det mottatte overskuddet være maksimalt og beløpe seg til 95 rubler.

Du kan finne hjelp til å løse problemene dine om dette emnet ved å sende en melding på VKontakte, Viber eller fylle ut skjemaet. Løsningskostnad lekser starter fra 7 BYN. per oppgave (200 russiske rubler), men ikke mindre enn 10 hviterussiske rubler. (RUB 300) for hele bestillingen. Detaljert design. Kostnaden for online eksamenshjelp (i dette tilfellet kreves 100 % forhåndsbetaling) er fra 30 BYR. (1000 russiske rubler) for å løse billetten.

Hvis du trenger å løse et lineært programmeringsproblem ved å bruke simplekstabeller, er vår online tjeneste vil være til stor hjelp for deg. Simplexmetoden innebærer sekvensiell oppregning av alle toppunktene i regionen akseptable verdier for å finne toppunktet der funksjonen har en ekstrem verdi. I det første trinnet finner man en løsning, som forbedres ved hvert påfølgende trinn. Denne løsningen kalles grunnleggende. Her er handlingssekvensen når du løser et lineært programmeringsproblem ved hjelp av simpleksmetoden:

Første steg.

I den kompilerte tabellen må du først og fremst se på kolonnen med gratis medlemmer. Hvis det er negative elementer i det, er det nødvendig å gå til det andre trinnet, hvis ikke, så til det femte.

Andre trinn.

På det andre trinnet er det nødvendig å bestemme hvilken variabel som skal ekskluderes fra grunnlaget og hvilken som skal inkluderes for å beregne simplekstabellen på nytt. For å gjøre dette ser vi gjennom kolonnen med frie termer og finner et negativt element i den. Linjen med et negativt element vil bli kalt ledende. I den finner vi det maksimale negative elementet i modul, den tilsvarende kolonnen er slaven. Hvis det er negative verdier blant de frie termene, men ikke i den tilsvarende raden, vil en slik tabell ikke ha løsninger. Variabelen i den ledende raden i kolonnen med frie termer er ekskludert fra grunnlaget, og variabelen som tilsvarer den ledende kolonnen er inkludert i grunnlaget.	Tabell 1.	grunnleggende variabler
	Tabell 1.	Gratis medlemmer under restriksjoner	Ikke-grunnleggende variabler	...	x 1	...	x 2
x l	x n	x n+1	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

Tredje trinn.

I det tredje trinnet beregner vi hele simplekstabellen ved å bruke spesielle formler.

Fjerde trinn. Hvis det etter omberegning er negative elementer igjen i kolonnen med frie termer, gå til det første trinnet hvis det ikke er noen, så til det femte. Femte trinn.

Har du kommet til det femte trinnet, så har du funnet en løsning som er akseptabel. Dette betyr imidlertid ikke at det er optimalt. Det vil bare være optimalt hvis alle elementene i F-strengen er positive. Hvis dette ikke er tilfelle, er det nødvendig å forbedre løsningen, for hvilken vi finner den ledende raden og kolonnen for neste omberegning ved hjelp av følgende algoritme. I utgangspunktet finner vi minimum negativt tall i linje F, unntatt funksjonsverdien. Kolonnen med dette nummeret vil være den ledende. For å finne den ledende raden finner vi forholdet mellom det tilsvarende frie leddet og elementet fra den ledende kolonnen, forutsatt at de er positive. Minimumsforholdet lar deg bestemme den ledende linjen. Vi regner om tabellen igjen ved å bruke formlene, dvs. gå til trinn 3. Enkel metode

er en iterativ prosess med rettet løsning av et ligningssystem trinn for trinn, som begynner med en referanseløsning og på jakt etter beste alternativet beveger seg langs hjørnepunktene til det mulige løsningsområdet, og forbedrer verdien av målfunksjonen til målfunksjonen når den optimale verdien. Formålet med tjenesten

. Tjenesten er beregnet på
nettbaserte løsninger

Lineære programmeringsproblemer (LPP) ved bruk av simpleksmetoden i følgende notasjonsformer: i form av en simplekstabell (Jordan transformasjonsmetode); grunnleggende opptaksskjema; modifisert simpleksmetode; i kolonneform; i linjeform.

Antall variabler Antall rader (antall restriksjoner) Neste I dette tilfellet må du ikke ta hensyn til restriksjoner som x i ≥ 0. Hvis det ikke er noen begrensninger i oppgaven for noen x i, må ZLP konverteres til KZLP, eller bruke denne tjenesten. Ved løsning bestemmes bruken automatisk.

M-metoden
(enkel metode med kunstig grunnlag) og
to-trinns simpleksmetode
Følgende brukes også med denne kalkulatoren:
Grafisk metode for å løse ZLP online-modus du kan bestemme prisen på et matrisespill (nedre og øvre grenser), se etter tilstedeværelsen av et setepunkt, finne en løsning på en blandet strategi ved å bruke følgende metoder: minimaks, simpleksmetode, grafisk (geometrisk) metode, Browns metode .
Ekstremum av en funksjon av to variabler
Dynamiske programmeringsproblemer
Fordel 5 homogene partier med varer mellom tre markeder for å oppnå maksimal inntekt fra salget deres. Inntekter fra salg i hvert marked G(X) avhenger av antall solgte partier av produkt X og er presentert i tabellen.

Produktvolum X (i partier)	Inntekt G(X)
Produktvolum X (i partier)	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Enkel metodealgoritme inkluderer følgende trinn:

Utarbeide den første grunnplanen. Gå til kanonisk form lineære programmeringsproblemer ved å introdusere ikke-negative tilleggsbalansevariabler.
Sjekker planen for optimalitet. Hvis det er minst én indekslinjekoeffisient mindre enn null, er planen ikke optimal og må forbedres.
Bestemme ledende kolonne og rad. Fra de negative koeffisientene til indekslinjen velges den største i absolutt verdi. Deretter blir elementene i den frie medlemskolonnen i simplekstabellen delt inn i elementer med samme fortegn til den ledende kolonnen.
Bygger en ny referanseplan . Overgangen til ny plan gjennomføres som følge av omberegning av simplekstabellen ved bruk av Jordan-Gauss-metoden.

Hvis det er nødvendig å finne ytterpunktet til den objektive funksjonen, så snakker vi om å søke minimumsverdi(F(x) → min , se eksempel på løsning av en funksjonsminimering) og maksimal verdi((F(x) → maks , se eksempel på løsning av en funksjonsmaksimering)

En ekstrem løsning oppnås ved grensen til regionen tillatte løsninger ved en av toppunktene til polygonens hjørnepunkter, eller på et segment mellom to tilstøtende hjørnepunkter.

Grunnleggende teorem for lineær programmering. Hvis ZLP-målfunksjonen når en ekstrem verdi på et tidspunkt i området for gjennomførbare løsninger, tar den denne verdien ved hjørnepunktet. Hvis ZLP-objektivfunksjonen når en ekstrem verdi ved mer enn ett hjørnepunkt, tar den samme verdi ved hvilken som helst av de konvekse lineære kombinasjonene av disse punktene.

Essensen av simpleksmetoden. Bevegelse til det optimale punktet utføres ved å flytte fra ett hjørnepunkt til nabopunktet, noe som bringer nærmere og raskere til X opt. En slik ordning for å telle opp punkter, kalt simpleksmetoden, foreslått av R. Danzig.
Hjørnepunkter er preget av m grunnleggende variabler, så overgangen fra ett hjørnepunkt til et tilstøtende kan oppnås ved å endre bare én grunnleggende variabel i basisen til en variabel fra en ikke-basis.
Implementeringen av simpleksmetoden, på grunn av ulike funksjoner og formuleringer av LP-problemer, har forskjellige modifikasjoner.

Konstruksjonen av simplekstabeller fortsetter til den optimale løsningen er oppnådd. Hvordan kan du bruke en simplekstabell for å finne ut at løsningen på et lineært programmeringsproblem er optimal?
Hvis siste linje(verdier av objektivfunksjonen) inneholder ikke negative elementer, derfor vil den finne den optimale planen.

Merknad 1. Hvis en av grunnvariablene er lik null, så er det ekstreme punktet som tilsvarer dette grunnleggende løsning- degenerert. Degenerasjon oppstår når det er uklarhet i valget av ledelinje. Du vil kanskje ikke legge merke til degenerasjonen av problemet i det hele tatt hvis du velger en annen linje som veiledning. Ved tvetydighet bør raden med lavest indeks velges for å unngå looping.

Merknad 2. La på et eller annet ytterpunkt alle simpleksforskjeller være ikke-negative D k ³ 0 (k = 1..n+m), dvs. en optimal løsning oppnås og det eksisterer slik A k - en ikke-basisvektor som D k = 0. Da oppnås maksimum ved å i det minste på to punkter, dvs. det er et alternativt optimum. Hvis vi introduserer denne variabelen x k i grunnlaget, vil ikke verdien av objektivfunksjonen endres.

Merknad 3. Løsningen på det dobbelte problemet er i det siste simplex bord. De siste m komponentene i vektoren av simpleksforskjeller (i kolonnene med balansevariabler) er den optimale løsningen på det doble problemet. Betydning målfunksjoner De direkte og doble problemene faller sammen på optimale punkter.

Merknad 4. Ved løsning av minimeringsproblemet introduseres vektoren med den største positive simpleksforskjellen i basisen. Deretter brukes den samme algoritmen som for maksimeringsproblemet.

Hvis betingelsen "Det er nødvendig at type III-råvarer er fullstendig forbrukt" er spesifisert, er den tilsvarende betingelsen en likhet.