Grafisk metode for å løse problemer på nett. Grafisk metode for å løse lineære programmeringsproblemer

Eksempel 6.1.

Løsning:

Det lineære programmeringsproblemet er gitt i standardform og har derfor to designparametere

Det er mulig å løse det ved hjelp av den geometriske metoden.

1. stadie: ( ODR ).

Tenk på den første begrensningen, bytt ut ulikhetstegnet med et likhetstegn og uttrykk variabelen x2 gjennom x1:

På samme måte bestemmer vi punktene for de gjenværende restriksjonene i systemet og konstruerer rette linjer fra dem som tilsvarer hver ulikhet (fig. 1). Vi nummererer linjene etter tidligere vedtatt ordning.

Trinn 2: .

La oss definere halvplan - løsninger på hver av ulikhetene.

La oss vurdere den første ulikheten i problembegrensningssystemet. La oss ta et punkt (kontrollpunkt) som ikke tilhører linjen som tilsvarer denne ulikheten, for eksempel punkt (0; 0). La oss erstatte det med ulikheten som vurderes:

Når du erstatter koordinater kontrollpunkt ulikhet er fortsatt rettferdig. Følgelig vil settet med punkter som tilhører denne linjen (siden ulikheten ikke er streng), så vel som de som ligger under den, være løsninger på ulikheten under vurdering (la oss markere på grafen (fig. 1) den funnet halvdelen -plan med to piler som peker ned ved siden av linjen Jeg ) .

Vi bestemmer på samme måte løsningene på andre ulikheter og merker dem på grafen deretter. Som et resultat vil grafen se slik ut:

Trinn 3: .

De funnet halvplanene (løsninger på hver av ulikhetene i systemet av begrensninger) danner en polygon når de krysser hverandre ABCDEO, som er ODD av problemet under vurdering.

Ris. 1. Område tillatte løsninger oppgaver

Trinn 4:
Gradientvektoren viser retningen for maksimering objektiv funksjon. La oss bestemme koordinatene: koordinatene til dets startpunkt (applikasjonspunktet) – (0; 0), koordinatene til det andre punktet:

La oss plotte denne vektoren på grafen (fig. 2).

Trinn 5: .

La oss vurdere den objektive funksjonen til dette problemet:

La oss gi det litt verdi, for eksempel . La oss uttrykke variabelen x2 gjennom x1:

For å konstruere en rett linje ved hjelp av denne ligningen, vil vi spesifisere to vilkårlige punkter, for eksempel:

La oss konstruere en rett linje som tilsvarer objektivfunksjonen (fig. 2).

Ris. 2. Konstruksjon av målfunksjonen F(X) og gradientvektoren C

Trinn 6: bestemme maksimum av målfunksjonen.

Flytte en rett linje F(X) parallelt med seg selv i retning av gradientvektoren, bestemmer vi ekstrempunktet (punktene) til ODR. I følge grafen (fig. 3) er et slikt punkt punkt C - skjæringspunktet mellom linjer Jeg Og II .

Ris. 3. Bestemmelse av maksimumspunktet for objektivfunksjonen F(X)

La oss bestemme koordinatene til punkt C, for dette formålet løser vi følgende system med lineære ligninger:

La oss erstatte de funnet koordinatene i målfunksjonen og finne dens optimale (maksimum) verdi:

Svar: under gitte begrensninger, maksimalverdien av den objektive funksjonen F(X)=24, som oppnås ved punkt C, hvis koordinater x1=6, x2=4.

Eksempel 6.2. Løs det lineære programmeringsproblemet ved å bruke den geometriske metoden:

Løsning:

Trinn 1-3 ligner på de tilsvarende stadiene i forrige oppgave.
Trinn 4: konstruksjon av en gradientvektor.
Konstruksjonen av gradientvektoren utføres på samme måte som i forrige oppgave. La oss plotte denne vektoren på grafen (fig. 4). Vi noterer oss også dette diagrammet pilen er retningen motsatt av gradientvektoren – retningen for minimering av objektivfunksjonen F (X).

Trinn 5: konstruksjon av en direkte målfunksjon.

Konstruksjon av en direkte objektiv funksjon F(X) utføres på samme måte som i forrige oppgave (konstruksjonsresultatet er vist i fig. 4).

Ris. 4. Konstruksjon av målfunksjonen F(x) og gradientvektoren C

Trinn 6: bestemme det optimale for målfunksjonen.

Flytte en rett linje F(x) parallelt med seg selv i retning motsatt av gradientvektoren, bestemmer vi ekstrempunktet (punktene) til ODR. I følge grafen (fig. 5) er et slikt punkt punkt O med koordinater (0; 0).

Ris. 5. Fastsettelse av minimumspunktet for objektivfunksjonen

Ved å erstatte koordinatene til minimumspunktet i målfunksjonen, bestemmer vi dens optimale (minimum) verdi, som er lik 0.
Svar: under gitte begrensninger minimumsverdi objektiv funksjon F(X)=0, som nås ved punktet O (0; 0).

Eksempel 6.3. Løs følgende lineære programmeringsproblem ved å bruke den geometriske metoden:

Løsning:

Det lineære programmeringsproblemet som vurderes er gitt i kanonisk form, velger vi som grunnleggende variabler x 1 Og x2 .

La oss lage en utvidet matrise og velge den ved hjelp av metoden Jordan-Gauss grunnleggende variabler x1 Og x 2 .

Multipliser (element for element) den første linjen med –3 og legg den til den andre:
.

Multipliser den andre linjen med:

La oss legge til den andre linjen til den første linjen:

Som et resultat vil restriksjonssystemet ha følgende form:

La oss uttrykke de grunnleggende variablene i form av frie:

La oss også uttrykke målfunksjonen i form av frie variabler for å gjøre dette, erstatter vi de oppnådde verdiene til de grunnleggende variablene i målfunksjonen:

La oss skrive det resulterende lineære programmeringsproblemet:

Siden variablene x1 Og x2 ikke-negativ, så kan det resulterende systemet med restriksjoner skrives i følgende form:

Deretter originalt problem kan skrives i form av følgende ekvivalent standard oppgave lineær programmering:

Dette problemet har to designparametere, derfor kan det løses ved hjelp av den geometriske metoden.

1. stadie: konstruksjon av rette linjer som begrenser området for gjennomførbare løsninger ( ODR ).

La oss vurdere systemet med begrensninger for det lineære programmeringsproblemet (for enkelhets skyld nummererer vi ulikhetene):

La oss konstruere rette linjer som tilsvarer hver ulikhet (fig. 6). Vi nummererer de rette linjene i henhold til den tidligere vedtatte ordningen.

Trinn 2: bestemmelse av løsningen på hver av ulikhetene i systemet av begrensninger.

Ved hjelp av kontrollpunkter bestemmer vi halvplan - løsninger på hver av ulikhetene, og markerer dem på grafen (fig. 6) ved hjelp av piler.

Trinn 3: bestemmelse av ODD for et lineært programmeringsproblem.

De funnet halvplanene (dvs. løsninger til hver av ulikhetene i begrensningssystemet) har ikke et felles skjæringspunkt (så løsningene på ulikhet jeg generelt motsier de gjenværende ulikhetene i begrensningssystemet), derfor er begrensningssystemet ikke konsistent og det lineære programmeringsproblemet har derfor ingen løsning.

Ris. 6. Fragment av et MathCAD-dokument:

å konstruere en region med gjennomførbare løsninger på et problem

Svar: Det lineære programmeringsproblemet som vurderes har ingen løsning på grunn av inkonsistensen i systemet med begrensninger.

Hvis, etter å ha erstattet koordinatene til kontrollpunktet i ulikheten, dens betydning blir krenket, så er løsningen på denne ulikheten et halvplan som ikke inneholder dette punktet (dvs. plassert på den andre siden av linjen).

Retningen motsatt av gradientvektoren tilsvarer retningen for å minimere objektivfunksjonen.

Den enkleste og mest visuelle metoden for å løse et lineært programmeringsproblem (LPP) er den grafiske metoden. Den er basert på den geometriske tolkningen av det lineære programmeringsproblemet og brukes til å løse ZLP med to ukjente:

Vi vil vurdere løsningen av dette problemet på et fly. Hver ulikhet i systemet med funksjonelle begrensninger definerer geometrisk et halvplan med en grenselinje en s x, ++ a j2 x 2 = b n i = 1, T. Ikke-negativitetsforhold definerer halvplan med grenselinjer X (= 0, x 2= 0 tilsvarende. Hvis systemet er konsistent, danner halvplanene, som krysser hverandre, en felles del, som er en konveks sett og representerer en samling av punkter; koordinatene til hvert av disse punktene er en løsning på dette systemet. Settet med disse punktene kalles løsningspolygon. Det kan være et punkt, et segment, en stråle, en avgrenset eller ubegrenset polygon.

Geometrisk er ZLP finne et hjørnepunkt av løsningspolygonet hvis koordinater gir den maksimale (minimum) verdien av den lineære objektivfunksjonen, Dessuten er alle punkter i løsningspolygonen tillatte løsninger.

En lineær ligning beskriver et sett med punkter som ligger på samme linje. Lineær ulikhet beskriver en region på flyet.

La oss finne ut hvilken del av planet som beskriver ulikheten 2x ( + 3x 2 12.

Først, la oss konstruere en rett linje 2x, + Zx 2 = 12. Den går gjennom punktene (6; 0) og (0; 4). For det andre bestemmer vi hvilket halvplan som tilfredsstiller ulikheten. For å gjøre dette, velg et hvilket som helst punkt på grafen som ikke tilhører linjen og sett inn koordinatene i ulikheten. Hvis ulikheten holder, da gitt poeng er en tillatt løsning og halvplanet som inneholder punktet tilfredsstiller ulikheten. Det er praktisk å bruke opprinnelsen til koordinater for å erstatte ulikheten. La oss erstatte x ( = x 2 = 0 til ulikhet 2x, + 3x 2 12. Vi får 2 0 + 3 0

På samme måte kan du grafisk skildre alle begrensningene til et lineært programmeringsproblem.

Løsningen på hver ulikhet i ZLP-begrensningssystemet er et halvplan som inneholder grenselinjen og plassert på den ene siden av den. Skjæringspunktet mellom halvplan, som hver er bestemt av den tilsvarende ulikheten i systemet, kalles område med gjennomførbare løsninger(ODR) eller definisjonsdomene.

Det må huskes at regionen med gjennomførbare løsninger tilfredsstiller betingelsene for ikke-negativitet (Xj > 0, j = 1, P). Koordinatene til ethvert punkt som tilhører definisjonsdomenet er en gyldig løsning på problemet.

For å finne den ekstreme verdien av objektivfunksjonen når du løser ZLP grafisk, bruk gradientvektor, hvis koordinater er partielle derivater av objektivfunksjonen:

Denne vektoren viser retningen til den raskeste endringen i objektivfunksjonen. Rett c [ x l + c 2 x 2 = f(x 0), vinkelrett på gradientvektoren er nivålinje målfunksjon (fig. 2.2.2). På et hvilket som helst punkt på nivålinjen har objektivfunksjonen samme verdi. La oss likestille målfunksjonen til en konstant verdi EN. Endre betydningen EN, vi får en familie av parallelle linjer, som hver er en nivålinje for den objektive funksjonen.

Ris. 2.2.2.

En viktig egenskap ved en nivålinje lineær funksjon er at når linjen er parallelt forskjøvet til den ene siden, er nivået bare øker og når den flyttes til den andre siden - bare avtar.

Grafisk metode beslutningen til OPS består av fire stadier:

1. Regionen for tillatte løsninger (ADA) i PLP er konstruert.
2. Gradientvektoren til objektivfunksjonen (TF) er konstruert med begynnelsen ved punktet x 0(0; 0): V = (s, fra 2).
3. Nivålinje CjXj + c 2 x 2 = a (a - konstant verdi) - en rett linje vinkelrett på gradientvektoren V, - beveger seg i retning av gradientvektoren i tilfelle maksimering av objektivfunksjonen f(x v x 2) til den forlater ODR. Når du minimerer /(*, x 2) nivålinjen beveger seg i retning motsatt av gradientvektoren. Ytterpunktet (eller punktene) til ODR under denne bevegelsen er maksimumspunktet (minimum). f(x pjc 2).

Hvis den rette linjen som tilsvarer nivålinjen ikke forlater ODR under bevegelsen, er minimum (maksimum) av funksjonen f(x p x 2) eksisterer ikke.

Hvis målfunksjonsnivålinjen er parallell med funksjonsbegrensningen for oppgaven optimal verdi CF, vil den optimale CF-verdien oppnås på et hvilket som helst punkt av denne begrensningen som ligger mellom to optimale hjørnepunkter, og følgelig er hvilket som helst av disse punktene den optimale løsningen for ZLP.

4. Koordinatene til maksimum (minimum) punkt bestemmes. For å gjøre dette er det nok å løse et system av ligninger av linjer som gir et maksimum (minimum) punkt i skjæringspunktet. Betydning f(x ( , x 2), funnet ved det resulterende punktet er den maksimale (minimum) verdien av objektivfunksjonen.

Mulige situasjoner grafisk løsning PAP-er er presentert i tabell. 2.2.1.

Tabell 2.2.1

Type ODR	Type optimal løsning
Begrenset	Eneste avgjørelse
Begrenset	Uendelige løsninger
Ubegrenset	CF er ikke begrenset nedenfra
	CF er ikke begrenset ovenfra
	Eneste avgjørelse
	Uendelige løsninger
	Eneste avgjørelse
	Uendelige løsninger

Eksempel 2.2.1. Planlegging av produksjon av en sybedrift (problem med dresser).

Det er planlagt å gi ut to typer dresser - menn og kvinner. En kvinnedress krever 1 m ull, 2 m lavsan og 1 dagsverk; for menn - 3,5 m ull, 0,5 m lavsan og 1 dagsverk. Totalt er det 350 m ull, 240 m lavsan og 150 dagsverk.

Det er nødvendig å bestemme hvor mange drakter av hver type som må sys for å sikre maksimal fortjeneste, hvis fortjenesten fra salget av en damedress er 10 den. enheter, og fra menn - 20 den. enheter Det bør huskes at det er nødvendig å sy minst 60 herredresser.

Økonomisk og matematisk modell av problemet

Variabler: X, - antall kvinners dresser; x 2 - antall herredresser.

Objektiv funksjon:

Begrensninger:

Den første begrensningen (på ull) har formen x ( + 3,5x 2 x ( + 3,5x 2 = 350 går gjennom punktene (350; 0) og (0; 100). Den andre begrensningen (ifølge lavsan) har formen 2x (+ 0,5x 2 2x x + 0,5x 2 = 240 passerer gjennom punktene (120; 0) og (0; 480). Den tredje begrensningen (på arbeidskraft) har formen x y + x 2 150. Direkte x ( + x 2 = 150 går gjennom punktene (150; 0) og (0; 150). Den fjerde begrensningen (på antall herredresser) har formen x 2> 60. Løsningen på denne ulikheten er halvplanet som ligger over den rette linjen x 2 = 60.

Som et resultat av skjæringspunktet mellom de konstruerte fire halvplanene får vi en polygon, som er regionen med mulige løsninger på problemet vårt. Ethvert punkt på denne polygonen tilfredsstiller alle fire funksjonelle ulikheter, og for ethvert punkt utenfor denne polygonen vil minst én ulikhet bli krenket.

I fig. 2.2.3 regionen med mulige løsninger (ADA) er skyggelagt. For å bestemme bevegelsesretningen mot det optimale, konstruerer vi vektor-gradient V, hvis koordinater er partielle derivater av objektivfunksjonen:

For å konstruere en slik vektor må du koble punktet (10; 20) til origo. For enkelhets skyld kan du konstruere en vektor proporsjonal med vektoren V. Således, i fig. 2.2.3 viser vektoren (30; 60).

Deretter skal vi bygge en nivålinje 10xj + 20x 2 = EN. La oss likestille målfunksjonen til en konstant verdi EN. Endre betydningen EN, får vi en familie av parallelle linjer, som hver er en nivålinje for den objektive funksjonen.

Den grafiske metoden for å løse ZLP er basert på utsagnene gitt i avsnitt 2.1. I følge teorem 2, optimal løsning er på toppen av regionen av gjennomførbare løsninger og løser derfor ZLP - finn toppen av regionen av gjennomførbare løsninger, hvis koordinater gir den optimale verdien av målfunksjonen.

Den grafiske metoden brukes til å løse en begrenset klasse av problemer med to variabler, noen ganger med tre variabler. Det skal bemerkes at for tre variabler er ikke dette området tydelig nok.

Algoritme for den grafiske metoden for å løse problemer

Vi vil vurdere implementeringen av den grafiske metoden for å løse ZLP ved hjelp av eksempler.

Eksempel 2.2.1. Løs ZLP grafisk:

(2.2.1)

maks z=x 1 + 4x 2 (2.2.2)

Løsning. For å konstruere et område med gjennomførbare løsninger, som består av skjæringspunktet mellom halvplan som tilsvarer hver ulikhet i systemet av begrensninger (2.2.1), skriver vi likningene til grensens rette linjer:

l 1: x 1 + 5x 2 = 5; l 2: x 1 + x 2 = 6; l 3: 7x 1 + x 2 = 7.

l 1 til skjemaet (2.2.3.) deler vi begge delene med 5:
. Altså rett l 1 kutt på akse Åh 1 5 enheter, på akse Åh 2 1 enhet. Tilsvarende har vi for l 2:
Og l 3:
.

For å bestemme halvplan som oppfyller systembegrensningene (2.2.1), må du erstatte koordinatene til ethvert punkt som ikke ligger på grenselinjen i begrensningene. Hvis vi oppnår en sann ulikhet, så er alle punkter fra dette halvplanet løsninger på denne ulikheten. Ellers velger du et annet halvplan.

Dermed er det første og andre ønskede halvplanet plassert i motsatt retning fra origo for koordinatene (0 – 5 0 - 5; 7 0 + 0 7), og den andre - mot opprinnelsen til koordinatene (0 + 0 6). Regionen med gjennomførbare løsninger i figur 2.2.1 er skyggelagt.

Figur 2.2.1 – Område med gjennomførbare løsninger

For å finne den optimale planen, som vil være plassert i toppunktet til løsningspolygonet, må du konstruere en vektor med retninger
=(Med 1 ,Med 2), som angir retningen for den største økningen i målfunksjonen z=Med 1 X 1 +Med 2 X 2 .

I denne oppgaven er retningsvektoren
= (1, 4): den starter på punktet OM(0,0) og slutter på punktet N(1, 4).

Deretter konstruerer vi en rett linje som går gjennom området med mulige løsninger, vinkelrett på vektoren, og kalles målnivålinje funksjoner. Vi flytter nivålinjen i retning av vektoren i tilfelle maksimering av objektivfunksjonen z og i motsatt retning, ved minimering z, til det siste krysset med regionen med gjennomførbare løsninger. Som et resultat bestemmes punktet eller punktene der målfunksjonen når en ekstrem verdi, eller hvor ubegrenset målfunksjonen er etablert z på settet med løsninger på problemet.

Dermed er det maksimale punktet for den objektive funksjonen z er poenget EN linjekryss l 2 og l 3 .

For å beregne den optimale verdien av objektivfunksjonen z finn koordinatene til punktet EN . Siden punktet EN er skjæringspunktet mellom linjene l 2 og l 3, tilfredsstiller dens koordinater et likningssystem sammensatt av likningene til de tilsvarende grenselinjene:

Så poenget EN har koordinater x 1 =1/6, x 2 = 35/6.

For å beregne den optimale verdien av målfunksjonen, må du erstatte koordinatene til punktet i den EN .

Erstatter koordinatene til punktet EN inn i objektivfunksjonen (2.4), får vi

maks z = 1/6 + 4·(35/6) = 47/2.

Eksempel 2.2.2. Konstruer på planet området med gjennomførbare løsninger av systemet med lineære ulikheter (2.2.4) og finn de største og minste verdiene for objektivfunksjonen (2.2.5):

(2.2.4)

z= –2x 1 –x 2 (2.2.5)

l 1: 4x 1 – x 2 = 0; l 2: x 1 + 3x 2 = 6; l 3: x 1 – 3x 2 = 6; l 4: x 2 = 1.

Rett l 1 går gjennom punktet med koordinater (0;0). For å konstruere det, uttrykker vi x 2 gjennom x 1: x 2 = 4x 1 . La oss finne et annet punkt som linjen går gjennom l 1, for eksempel (1;4). Gjennom punktet med koordinater (0;0) og punktet med koordinater (1;4) trekker vi en rett linje l 1 .

For å redusere ligningen til en rett linje l 2 til skjemaet i segmenter på aksene (2.2.3), deler vi begge delene med 6:
. Altså rett l 2 kutt på aksen Åh 1 6 enheter, på akse Åh 2 - 2 enheter. Tilsvarende har vi for l 3:
og direkte l 4 parallelt med aksen Åh 1 og går gjennom punktet med koordinater (0;1) .

For å bestemme halvplan som oppfyller systemets begrensninger (2.2.4), er det nødvendig å erstatte koordinatene til ethvert punkt som ikke ligger på grenselinjen i begrensningene. På grunn av restriksjonerX 1 0, X 2 0, området med tillatte løsninger av ZLP ligger i første kvartal av koordinatplanet.

OM
området med mulige løsninger i figur 2.2.2 er skyggelagt.

Figur 2.2.2 – Område med gjennomførbare løsninger

La oss konstruere en vektor av retninger
= (–2,–1). Deretter bygger vi en nivålinje vinkelrett på vektoren .

Å finne høyeste verdi av objektivfunksjonen flytter vi nivålinjen i vektorens retning til siste skjæringspunkt med området med mulige løsninger. Dermed er det maksimale punktet for den objektive funksjonen z er poenget EN(skjæringspunktet mellom linjer l 1 og l 2).

For å beregne den optimale verdien av objektivfunksjonen z finn koordinatene til punktet EN. Siden punktet EN er skjæringspunktet mellom linjene l 1 og l 2, tilfredsstiller dens koordinater et likningssystem sammensatt av likningene til de tilsvarende grenselinjene:

Så poenget EN har koordinater x 1 =6/13, x 2 = 24/13.

Erstatter koordinatene til punktet EN inn i objektivfunksjonen (2.2.5), får vi den optimale verdien av objektivfunksjonen

maks z= – 2·(6/13) – (24/13) = – 36/13.

For å finne den minste verdien av objektivfunksjonen, flytter vi nivålinjen i retning motsatt av vektoren til det siste skjæringspunktet med området med mulige løsninger. I dette tilfellet er objektivfunksjonen ubegrenset i området for gjennomførbare løsninger, dvs. ZLP har ikke noe minimum.

Som et resultat av avgjørelsen fra OPS er følgende tilfeller mulig:

Objektivfunksjonen når sin optimale verdi ved et enkelt toppunkt av løsningspolygonet;

Objektivfunksjonen når sin optimale verdi når som helst på kanten av løsningspolygonen (ZLP har alternativ referanseplaner med samme verdier z );

PLP har ikke optimale planer;

PAP har optimal plan når det gjelder et ubegrenset utvalg av gjennomførbare løsninger.

Lineær programmering bruker en grafisk metode for å bestemme konvekse sett (løsningspolyeder). Hvis det lineære hovedprogrammeringsproblemet har en optimal plan, tar objektivfunksjonen en verdi ved en av toppunktene til løsningspolyederet (se figur).

Formålet med tjenesten. Ved bruk av av denne tjenesten mulig i online-modus løse det lineære programmeringsproblemet ved hjelp av den geometriske metoden, og også få en løsning på det dobbelte problemet (vurdere optimal ressursbruk). I tillegg lages en løsningsmal i Excel.

Bruksanvisning. Velg antall rader (antall restriksjoner).

Hvis antallet variabler er mer enn to, er det nødvendig å bringe systemet til SZLP (se eksempel og eksempel nr. 2). Hvis begrensningen er dobbel, for eksempel 1 ≤ x 1 ≤ 4, deles den i to: x 1 ≥ 1, x 1 ≤ 4 (dvs. antall rader øker med 1).
Du kan også bygge et mulig løsningsområde (ADA) ved å bruke denne tjenesten.

Følgende brukes også med denne kalkulatoren:
Enkel metode for å løse ZLP

Løsning av transportproblemet
Løse et matrisespill
Ved å bruke nettjenesten kan du 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
Beregning av grenser

Å løse et lineært programmeringsproblem med grafisk metode inkluderer følgende trinn:

Linjer er konstruert på planet X 1 0X 2.
Halve fly er bestemt.
Definer en løsningspolygon;
Det er konstruert en vektor N(c 1,c 2), som indikerer retningen til objektivfunksjonen;
Flytt frem objektiv funksjon c 1 x 2 + c 2 x 2= 0 i retning av vektor N til ytterpunktet av løsningspolygonet.
Koordinatene til punktet og verdien av målfunksjonen på dette punktet beregnes.

Følgende situasjoner kan oppstå:

Eksempel. Selskapet produserer to typer produkter - P1 og P2. For produksjon av produkter brukes to typer råvarer - C1 og C2. Bulkpriser produksjonsenhet er lik: 5 enheter. for P1 og 4 enheter for P2. Forbruket av råvarer per produktenhet av type P1 og type P2 er gitt i tabellen.
Tabell - Forbruk av råvarer til produksjon

Det er etablert restriksjoner på produktetterspørselen: det daglige produksjonsvolumet av P2-produkter bør ikke overstige det daglige produksjonsvolumet til P1-produkter med ikke mer enn 1 tonn; Maksimalt daglig produksjonsvolum av P2 bør ikke overstige 2 tonn.
Du må bestemme:
Hvor mye av hver type produkt bør bedriften produsere for å maksimere inntektene fra produktsalg?

Formuler matematisk modell lineære programmeringsproblemer.
Løs et lineært programmeringsproblem grafisk(for to variabler).

Løsning.
La oss formulere en matematisk modell av det lineære programmeringsproblemet.
x 1 - produksjon av produkter P1, enheter.
x 2 - produksjon av produkter P2, enheter.
x 1, x 2 ≥ 0

Ressursgrenser
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6

Krev restriksjoner
x 1 +1 ≥ x 2
x 2 ≤ 2

Objektiv funksjon
5x 1 + 4x 2 → maks

Da får vi følgende PLP:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1, x 2 ≥ 0
5x 1 + 4x 2 → maks

Oppgave. Løs det lineære programmeringsproblemet grafisk ved å bestemme ekstremverdien til objektivfunksjonen:

under restriksjoner

La oss konstruere en region med gjennomførbare løsninger, dvs. La oss løse systemet med ulikheter grafisk. For å gjøre dette konstruerer vi hver rett linje og definerer halvplanene definert av ulikhetene (halvplanene er indikert med et primtall).

La oss bygge ligningen 3x 1 +x 2 = 9 med to poeng.
For å finne det første punktet, setter vi likhetstegn mellom x 1 = 0. Vi finner x 2 = 9. For å finne det andre punktet, setter vi likhetstegn mellom x 2 = 0. Vi finner x 1 = 3. Vi kobler punktet (0;9) med (3;0) med en rett linje. La oss definere halvplanet definert av ulikheten. Etter å ha valgt punktet (0; 0), definerer vi ulikhetstegnet i halvplanet: 3. 0 + 1. 0 - 9 ≤ 0, dvs. 3x 1 +x 2 - 9≥ 0 i halvplanet over den rette linjen.
La oss konstruere ligningen x 1 +2x 2 = 8 med to poeng.
For å finne det første punktet, setter vi likhetstegn mellom x 1 = 0. Vi finner x 2 = 4. For å finne det andre punktet, setter vi likhetstegn mellom x 2 = 0. Vi finner x 1 = 8. Vi kobler punktet (0;4) med (8;0) med en rett linje. La oss definere halvplanet definert av ulikheten. Etter å ha valgt punktet (0; 0), definerer vi ulikhetstegnet i halvplanet: 1. 0 + 2. 0 - 8 ≤ 0, dvs. x 1 +2x 2 - 8≥ 0 i halvplanet over den rette linjen.
La oss konstruere ligningen x 1 + x 2 = 8 med to poeng.
For å finne det første punktet, setter vi likhetstegn mellom x 1 = 0. Vi finner x 2 = 8. For å finne det andre punktet, setter vi likhetstegn mellom x 2 = 0. Vi finner x 1 = 8. Vi kobler punktet (0;8) med (8;0) med en rett linje. La oss definere halvplanet definert av ulikheten. Etter å ha valgt punktet (0; 0), definerer vi ulikhetstegnet i halvplanet: 1. 0 + 1. 0 - 8 ≤ 0, dvs. x 1 +x 2 - 8≤ 0 i halvplanet under den rette linjen.

Skjæringspunktet mellom halvplan vil være et område hvis koordinater av punkt tilfredsstiller ulikhetene i systemet med begrensninger av problemet.
La oss angi grensene for området til løsningspolygonet.

Du kan kontrollere riktigheten av å konstruere funksjonsgrafer ved hjelp av en kalkulator

Tenk på den objektive funksjonen til oppgaven F = 4x 1 +6x 2 → min.
La oss konstruere en rett linje som tilsvarer verdien av funksjonen F = 0: F = 4x 1 +6x 2 = 0. Gradientvektoren, sammensatt av koeffisientene til objektivfunksjonen, indikerer retningen for minimering av F(X). Begynnelsen av vektoren er punkt (0; 0), slutten er punkt (4; 6). La oss flytte denne rette linjen parallelt. Siden vi er interessert minimal løsning, så vi flytter den rette linjen til den først berører det angitte området. På grafen er denne rette linjen indikert med en stiplet linje.

Rett F(x) = 4x 1 +6x 2 skjærer området ved punkt B. Siden punkt B er oppnådd som et resultat av skjæringspunktet mellom linjer (1) Og (2) , så tilfredsstiller dens koordinater likningene til disse linjene:
3x 1 +x 2 =9
x 1 +2x 2 =8

Etter å ha løst ligningssystemet får vi: x 1 = 2, x 2 = 3
Hvordan kan vi finne minimumsverdien til objektivfunksjonen:
F(X) = 4*2 + 6*3 = 26