• hjem
  •  > 
  • Sikkerhed
  •  > 
  • Grafisk metode til at løse problemer online. Grafisk metode til løsning af lineære programmeringsproblemer

Grafisk metode til at løse problemer online. Grafisk metode til løsning af lineære programmeringsproblemer

Eksempel 6.1.

Løsning:

Det lineære programmeringsproblem er givet i standardform og har derfor to designparametre

Det er muligt at løse det ved hjælp af den geometriske metode.

Scene 1: ( ODR ).

Overvej den første begrænsning, erstat ulighedstegnet med et lighedstegn og udtryk variablen x2 igennem x1:

.

På samme måde bestemmer vi punkterne for de resterende begrænsninger af systemet og konstruerer lige linjer fra dem svarende til hver ulighed (fig. 1). Vi nummererer linjerne efter den tidligere vedtagne ordning.

Fase 2: .

Lad os definere halvplaner - løsninger på hver af ulighederne.

Lad os overveje den første ulighed i problembegrænsningssystemet. Lad os tage et punkt (kontrolpunkt), der ikke hører til den linje, der svarer til denne ulighed, for eksempel punkt (0; 0). Lad os erstatte det med den ulighed, der overvejes:

Ved udskiftning af koordinater kontrolpunkt ulighed er fortsat retfærdig. Følgelig vil sættet af punkter, der hører til denne linje (da uligheden ikke er streng), såvel som dem, der er placeret under den, være løsninger på den ulighed, der overvejes (lad os markere på grafen (fig. 1) den fundne halvdel -plan med to pile, der peger ned ved siden af ​​linjen jeg ) .

Vi bestemmer på samme måde løsningerne på andre uligheder og markerer dem på grafen i overensstemmelse hermed. Som et resultat vil grafen se således ud:

Trin 3: .

De fundne halvplaner (løsninger til hver af ulighederne i systemet af begrænsninger) danner en polygon, når de skærer hinanden ABCDEO, som er UDD for det undersøgte problem.

Ris. 1. Område tilladte løsninger opgaver

Fase 4:
Gradientvektoren viser maksimeringsretningen objektiv funktion. Lad os bestemme dets koordinater: koordinaterne for dets begyndelsespunkt (anvendelsespunkt) – (0; 0), koordinaterne for det andet punkt:

Lad os plotte denne vektor på grafen (fig. 2).

Trin 5: .

Lad os overveje den objektive funktion af dette problem:

.

Lad os give det noget værdi, for eksempel . Lad os udtrykke variablen x2 igennem x1:

.

For at konstruere en ret linje ved hjælp af denne ligning, vil vi specificere to vilkårlige punkter, for eksempel:

Lad os konstruere en ret linje svarende til objektivfunktionen (fig. 2).

Ris. 2. Konstruktion af målfunktionen F(X) og gradientvektoren C

Fase 6: bestemme maksimum af målfunktionen.

Flytning af en lige linje F(x) parallelt med sig selv i retning af gradientvektoren, bestemmer vi ekstrempunktet (punkterne) af ODR. Ifølge grafen (fig. 3) er et sådant punkt punkt C - skæringspunktet for linjer jeg Og II .

Ris. 3. Bestemmelse af maksimumpunktet for objektivfunktionen F(X)

Lad os bestemme koordinaterne for punkt C, til dette formål løser vi følgende system af lineære ligninger:

Lad os erstatte de fundne koordinater i objektivfunktionen og finde dens optimale (maksimale) værdi:

Svar: under givne begrænsninger den maksimale værdi af den objektive funktion F(x)=24, hvilket opnås ved punkt C, hvis koordinater x1=6, x2=4.

Eksempel 6.2. Løs det lineære programmeringsproblem ved hjælp af den geometriske metode:

Løsning:

Trin 1-3 ligner de tilsvarende stadier i den foregående opgave.
Fase 4: konstruktion af en gradientvektor.
Konstruktionen af ​​gradientvektoren udføres på samme måde som i den foregående opgave. Lad os plotte denne vektor på grafen (fig. 4). Vi noterer også vedr dette diagram pilen er retningen modsat gradientvektoren - retningen for minimering af objektivfunktionen F (x).

Trin 5: opbygning af en direkte målfunktion.

Konstruktion af en direkte objektiv funktion F(x) udføres på samme måde som i den foregående opgave (konstruktionsresultatet er vist i fig. 4).

Ris. 4. Konstruktion af målfunktionen F(x) og gradientvektoren C

Fase 6: bestemmelse af optimum for målfunktionen.

Flytning af en lige linje F(x) parallelt med sig selv i retning modsat gradientvektoren, bestemmer vi ODR's ekstreme punkt (punkter). Ifølge grafen (fig. 5) er et sådant punkt punkt O med koordinater (0; 0).

Ris. 5. Bestemmelse af minimumspunktet for den objektive funktion

Ved at erstatte koordinaterne for minimumspunktet i målfunktionen bestemmer vi dens optimale (minimum) værdi, som er lig med 0.
Svar: under givne restriktioner minimumsværdi objektiv funktion F(x)=0, som nås ved punktet O (0; 0).

Eksempel 6.3. Løs følgende lineære programmeringsproblem ved hjælp af den geometriske metode:

Løsning:

Det lineære programmeringsproblem, der overvejes, er givet i kanonisk form, vælger vi som grundvariable x 1 Og x2 .

Lad os oprette en udvidet matrix og vælge den ved hjælp af metoden Jordan-Gauss grundlæggende variabler x1 Og x 2 .

Multiplicer (element for element) den første linje med -3 og læg den til den anden:
.

Gang den anden linje med:

.

Lad os tilføje den anden linje til den første linje:

.

Som følge heraf vil begrænsningssystemet antage følgende form:

Lad os udtrykke de grundlæggende variabler i form af frie:

Lad os også udtrykke målfunktionen i form af frie variable; For at gøre dette erstatter vi de opnåede værdier af de grundlæggende variabler i målfunktionen:

Lad os skrive det resulterende lineære programmeringsproblem:

Siden variablerne x1 Og x2 ikke-negativ, så kan det resulterende system af begrænsninger skrives i følgende form:

Derefter oprindelige problem kan skrives i form af følgende ækvivalent standard opgave lineær programmering:

Dette problem har to designparametre, derfor kan det løses ved hjælp af den geometriske metode.

Scene 1: konstruktion af lige linjer, der begrænser området for mulige løsninger ( ODR ).

Lad os overveje systemet af begrænsninger for det lineære programmeringsproblem (for nemheds skyld nummererer vi ulighederne):

Lad os konstruere lige linjer svarende til hver ulighed (fig. 6). Vi nummererer de lige linjer i henhold til den tidligere vedtagne ordning.

Fase 2: bestemmelse af løsningen på hver af ulighederne i systemet af begrænsninger.

Ved hjælp af kontrolpunkter bestemmer vi halvplaner - løsninger til hver af ulighederne, og markerer dem på grafen (fig. 6) ved hjælp af pile.

Trin 3: bestemmelse af ODD for et lineært programmeringsproblem.

De fundne halvplaner (dvs. løsninger til hver af ulighederne i begrænsningssystemet) har ikke et fælles skæringspunkt (så løsningerne på uligheden modsiger jeg generelt de resterende uligheder i begrænsningssystemet), derfor er begrænsningssystemet inkonsekvent og det lineære programmeringsproblem har derfor ingen løsning.

Ris. 6. Fragment af et MathCAD-dokument:

at konstruere en region med gennemførlige løsninger på et problem

Svar: Det lineære programmeringsproblem, der overvejes, har ingen løsning på grund af inkonsistensen i systemet af begrænsninger.

Hvis, efter at have erstattet kontrolpunktets koordinater i uligheden, dets betydning krænkes, så er løsningen på denne ulighed et halvt plan, der ikke indeholder dette punkt (dvs. placeret på den anden side af linjen).

Retningen modsat gradientvektoren svarer til retningen for at minimere objektivfunktionen.

Den enkleste og mest visuelle metode til at løse et lineært programmeringsproblem (LPP) er den grafiske metode. Det er baseret på den geometriske fortolkning af det lineære programmeringsproblem og bruges til at løse ZLP med to ubekendte:

Vi vil overveje løsningen af ​​dette problem på et fly. Hver ulighed i systemet af funktionelle begrænsninger definerer geometrisk et halvt plan med en grænselinje en s x, ++ a j2 x 2 = b n i = 1, T. Ikke-negativitetsbetingelser definerer halvplaner med grænselinjer X (= 0, x 2= 0 tilsvarende. Hvis systemet er konsistent, danner halvplanerne, der skærer hinanden, en fælles del, som er en konveks mængde og repræsenterer en samling af punkter; koordinaterne for hvert af disse punkter er en løsning på dette system. Sættet af disse punkter kaldes løsningspolygon. Det kan være et punkt, et segment, en stråle, en afgrænset eller ubegrænset polygon.

Geometrisk er ZLP finde et hjørnepunkt af løsningspolygonen, hvis koordinater giver den maksimale (minimum) værdi af den lineære objektivfunktion, Desuden er alle punkter i løsningspolygonen tilladte løsninger.

En lineær ligning beskriver et sæt punkter, der ligger på samme linje. Lineær ulighed beskriver et område på flyet.

Lad os bestemme, hvilken del af planet, der beskriver uligheden 2x ( + 3x 2 12.

Lad os først konstruere en ret linje 2x, + Zx 2 = 12. Den passerer gennem punkterne (6; 0) og (0; 4). For det andet bestemmer vi, hvilket halvplan der opfylder uligheden. For at gøre dette skal du vælge ethvert punkt på grafen, der ikke hører til linjen, og erstatte dets koordinater med uligheden. Hvis uligheden holder, så givet point er en tilladt løsning, og halvplanet, der indeholder punktet, opfylder uligheden. Det er praktisk at bruge oprindelsen af ​​koordinater til at erstatte uligheden. Lad os erstatte x ( = x 2 = 0 til ulighed 2x, + 3x 2 12. Vi får 2 0 + 3 0

På samme måde kan du grafisk afbilde alle begrænsningerne for et lineært programmeringsproblem.

Løsningen på hver ulighed i ZLP-begrænsningssystemet er et halvt plan, der indeholder grænselinjen og placeret på den ene side af den. Skæringspunktet mellem halvplaner, som hver især er bestemt af systemets tilsvarende ulighed, kaldes område med mulige løsninger(ODR) eller definitionsdomæne.

Det skal huskes, at regionen med gennemførlige løsninger opfylder betingelserne for ikke-negativitet (Xj > 0, j = 1, P). Koordinaterne for ethvert punkt, der hører til definitionsdomænet, er en gyldig løsning på problemet.

For at finde den ekstreme værdi af objektivfunktionen, når du løser ZLP grafisk, skal du bruge gradient vektor, hvis koordinater er partielle afledte af den objektive funktion:

Denne vektor viser retningen for den hurtigste ændring i objektivfunktionen. Lige c [ x l + c 2 x 2 = f(x 0), vinkelret på gradientvektoren er niveau linje målfunktion (fig. 2.2.2). På et hvilket som helst punkt på niveaulinjen har objektivfunktionen samme værdi. Lad os sidestille målfunktionen med en konstant værdi EN.Ændring af betydning EN, vi opnår en familie af parallelle linjer, som hver er en niveaulinje af den objektive funktion.


Ris. 2.2.2.

En vigtig egenskab ved en niveaulinje lineær funktion er, at når linjen er parallelt forskudt til den ene side, er niveauet kun stiger og når den flyttes til den anden side - kun falder.

Grafisk metode OPP's beslutning består af fire faser:

  • 1. Regionen af ​​tilladte løsninger (ADA) af PLP er konstrueret.
  • 2. Gradientvektoren for objektivfunktionen (TF) er konstrueret med begyndelsen ved punktet x 0(0; 0): V = (s, fra 2).
  • 3. Niveaulinje CjXj + c 2 x 2 = a (a - konstant værdi) - en ret linje vinkelret på gradientvektoren V, - bevæger sig i retning af gradientvektoren i tilfælde af maksimering af objektivfunktionen f(x v x 2) indtil den forlader ODR. Når du minimerer /(*, x 2) niveaulinjen bevæger sig i retning modsat gradientvektoren. Det yderste punkt (eller punkter) af ODR under denne bevægelse er maksimum (minimum) punkt f(x p jc 2).

Hvis den rette linje, der svarer til niveaulinjen, ikke forlader ODR under dens bevægelse, er minimum (maksimum) af funktionen f(x p x 2) eksisterer ikke.

Hvis målfunktionsniveaulinjen er parallel med den funktionelle begrænsning af opgaven, hvor optimal værdi CF, så vil den optimale CF-værdi blive opnået på et hvilket som helst punkt af denne begrænsning, der ligger mellem to optimale hjørnepunkter, og følgelig er et hvilket som helst af disse punkter den optimale løsning af ZLP.

4. Koordinaterne for det maksimale (minimum) punkt bestemmes. For at gøre dette er det nok at løse et system af ligninger af linjer, der giver et maksimum (minimum) punkt i skæringspunktet. Betyder f(x ( , x 2), fundet ved det resulterende punkt er den maksimale (minimum) værdi af objektivfunktionen.

Mulige situationer grafisk løsning PAP'er er præsenteret i tabel. 2.2.1.

Tabel 2.2.1

Type af ODR

Type af optimal løsning

Begrænset

Eneste beslutning

Uendelige løsninger

Ubegrænset

CF er ikke begrænset nedefra

CF er ikke begrænset fra oven

Eneste beslutning

Uendelige løsninger

Eneste beslutning

Uendelige løsninger

Eksempel 2.2.1. Planlægning af produktionen af ​​en syvirksomhed (problem med jakkesæt).

Det er planlagt at udgive to typer jakkesæt - herre og kvinder. En kvindedragt kræver 1 m uld, 2 m lavsan og 1 dagsværk; for mænd - 3,5 m uld, 0,5 m lavsan og 1 dagsværk. I alt er der 350 m uld, 240 m lavsan og 150 dagsværk.

Det er nødvendigt at bestemme, hvor mange dragter af hver type, der skal sys for at sikre maksimal profit, hvis fortjenesten ved salg af en damedragt er 10 den. enheder, og fra mænd - 20 den. enheder Man skal huske på, at det er nødvendigt at sy mindst 60 herredragter.

Økonomisk og matematisk model af problemet

Variabler: X, - antal kvinders dragter; x 2 - antal herredragter.

Objektiv funktion:

Begrænsninger:

Den første begrænsning (på uld) har formen x ( + 3,5x 2 x ( + 3,5x 2 = 350 passerer gennem punkterne (350; 0) og (0; 100). Den anden begrænsning (ifølge lavsan) har formen 2x (+ 0,5x 2 2x x + 0,5x 2 = 240 passerer gennem punkterne (120; 0) og (0; 480). Den tredje begrænsning (på arbejdskraft) har formen x y + x 2 150. Direkte x ( + x 2 = 150 passerer gennem punkterne (150; 0) og (0; 150). Den fjerde begrænsning (på antallet af herredragter) har formen x 2> 60. Løsningen på denne ulighed er halvplanet, der ligger over den rette linje x 2 = 60.

Som et resultat af skæringen af ​​de konstruerede fire halvplaner opnår vi en polygon, som er regionen med mulige løsninger på vores problem. Ethvert punkt på denne polygon opfylder alle fire funktionelle uligheder, og for ethvert punkt uden for denne polygon vil mindst én ulighed blive overtrådt.

I fig. 2.2.3 regionen med mulige løsninger (ADA) er skraveret. For at bestemme bevægelsesretningen mod det optimale, konstruerer vi vektor-gradient V, hvis koordinater er partielle afledte af den objektive funktion:

For at konstruere en sådan vektor skal du forbinde punktet (10; 20) med oprindelsen. For nemheds skyld kan du konstruere en vektor proportional med vektoren V. Således i fig. 2.2.3 viser vektoren (30; 60).

Så vil vi bygge en niveaulinje 10xj + 20x 2 = EN. Lad os sidestille målfunktionen med en konstant værdi EN.Ændring af betydning EN, opnår vi en familie af parallelle linjer, som hver er en niveaulinje af den objektive funktion.

Den grafiske metode til løsning af ZLP er baseret på udsagnene i afsnit 2.1. Ifølge sætning 2, optimal løsning er i toppen af ​​regionen af ​​gennemførlige løsninger og løser derfor ZLP'en - find toppen af ​​regionen af ​​gennemførlige løsninger, hvis koordinater giver den optimale værdi af den objektive funktion.

Den grafiske metode bruges til at løse en begrænset klasse af problemer med to variable, nogle gange med tre variable. Det skal bemærkes, at for tre variabler er dette område ikke klart nok.

Algoritme til den grafiske metode til at løse problemer

Vi vil overveje implementeringen af ​​den grafiske metode til løsning af ZLP ved hjælp af eksempler.

Eksempel 2.2.1. Løs ZLP grafisk:

(2.2.1)

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

Løsning. For at konstruere et område af mulige løsninger, som består af skæringen af ​​halvplaner svarende til hver ulighed i systemet af begrænsninger (2.2.1), skriver vi ligningerne for de rette grænselinjer:

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

l 1 til formen (2.2.3.) dividerer vi begge dens dele med 5:
. Altså lige l 1 skærer på akse Åh 1 5 enheder, på akse Åh 2 1 enhed. Tilsvarende har vi for l 2:
Og l 3:
.

For at bestemme halvplaner, der opfylder systemets begrænsninger (2.2.1), skal du erstatte koordinaterne for ethvert punkt, der ikke ligger på grænselinjen, i begrænsningerne. Hvis vi opnår en sand ulighed, så er alle punkter fra dette halvplan løsninger på denne ulighed. Ellers skal du vælge et andet halvplan.

Således er det første og andet ønskede halvplan placeret i den modsatte retning fra koordinaternes oprindelse (0 – 5 0 - 5; 7 0 + 0 7), og den anden - mod oprindelsen af ​​koordinater (0 + 0 6). Området med mulige løsninger i figur 2.2.1 er skraveret.

Figur 2.2.1 – Område med mulige løsninger

For at finde den optimale plan, som vil være placeret i toppunktet af løsningspolygonen, skal du konstruere en vektor af retninger
=(Med 1 ,Med 2), som angiver retningen for den største stigning i den objektive funktion z=Med 1 x 1 +Med 2 x 2 .

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

Dernæst konstruerer vi en ret linje, der går gennem området af mulige løsninger, vinkelret på vektoren, og kaldes målniveaulinje funktioner. Vi flytter niveaulinjen i vektorens retning i tilfælde af at maksimere objektivfunktionen z og i den modsatte retning, i tilfælde af minimering z, indtil det sidste kryds med området for mulige løsninger. Som følge heraf bestemmes punktet eller punkterne, hvor objektivfunktionen når en ekstrem værdi, eller objektivfunktionens ubegrænsethed er etableret z på sæt af løsninger på problemet.

Således det maksimale punkt for den objektive funktion z er pointen EN linjekryds l 2 og l 3 .

At beregne den optimale værdi af objektivfunktionen z find punktets koordinater EN . Siden pointen EN er linjernes skæringspunkt l 2 og l 3, så opfylder dens koordinater et ligningssystem sammensat af ligningerne for de tilsvarende grænselinjer:



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

For at beregne den optimale værdi af objektivfunktionen skal du erstatte punktets koordinater i den EN .

Udskiftning af koordinaterne for punktet EN ind i den objektive funktion (2.4), opnår vi

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

Eksempel 2.2.2. Konstruer på planet området med mulige løsninger af systemet af lineære uligheder (2.2.4) og find de største og mindste værdier af den objektive funktion (2.2.5):

(2.2.4)

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

Løsning. For at konstruere et område af mulige løsninger, som består af skæringen af ​​halvplaner svarende til hver ulighed i systemet af begrænsninger (2.2.4), skriver vi ligningerne for de rette grænselinjer:

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.

Lige l 1 går gennem punktet med koordinater (0;0). For at konstruere det, udtrykker vi x 2 igennem x 1: x 2 = 4x 1 . Lad os finde et andet punkt, som linjen går igennem l 1, for eksempel (1;4). Gennem punktet med koordinaterne (0;0) og punktet med koordinaterne (1;4) tegner vi en ret linje l 1 .

At reducere ligningen for en ret linje l 2 til formen i segmenter på akserne (2.2.3), dividerer vi begge dens dele med 6:
. Altså lige l 2 snit på akse Åh 1 6 enheder, på akse Åh 2 - 2 enheder. Tilsvarende har vi for l 3:
og direkte l 4 parallelt med aksen Åh 1 og går gennem punktet med koordinaterne (0;1) .

For at bestemme halvplaner, der opfylder systemets begrænsninger (2.2.4), er det nødvendigt at erstatte koordinaterne for ethvert punkt, der ikke ligger på grænselinjen, i begrænsningerne. På grund af restriktionerx 1 0, x 2 0, området med tilladte løsninger af ZLP ligger i den første fjerdedel af koordinatplanet.

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

Figur 2.2.2 – Område med mulige løsninger

Lad os konstruere en vektor af retninger
= (–2,–1). Dernæst bygger vi en niveaulinje vinkelret på vektoren .

At finde højeste værdi af objektivfunktionen flytter vi niveaulinjen i vektorens retning indtil den sidste skæring med området for mulige løsninger. Således det maksimale punkt for den objektive funktion z er pointen EN(skæring af linjer l 1 og l 2).

At beregne den optimale værdi af objektivfunktionen z find punktets koordinater EN. Siden pointen EN er linjernes skæringspunkt l 1 og l 2, så opfylder dens koordinater et ligningssystem sammensat af ligningerne for de tilsvarende grænselinjer:



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

Udskiftning af koordinaterne for punktet EN ind i objektivfunktionen (2.2.5), opnår vi den optimale værdi af objektivfunktionen

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

For at finde den mindste værdi af objektivfunktionen flytter vi niveaulinjen i retning modsat vektoren indtil den sidste skæring med området for mulige løsninger. I dette tilfælde er den objektive funktion ubegrænset i området for mulige løsninger, dvs. ZLP har intet minimum.

Som følge af OPP's beslutning er følgende tilfælde mulige:

    Objektivfunktionen når sin optimale værdi ved et enkelt toppunkt af løsningspolygonen;

    Objektivfunktionen når sin optimale værdi på ethvert punkt på kanten af ​​løsningspolygonen (ZLP har alternativ referenceplaner med samme værdier z );

    PAP har ikke optimale planer;

    PAP har optimal plan i tilfælde af et ubegrænset udvalg af gennemførlige løsninger.

Lineær programmering bruger en grafisk metode til at bestemme konvekse mængder (opløsningspolyeder). Hvis det lineære hovedprogrammeringsproblem har en optimal plan, så antager objektivfunktionen en værdi ved et af hjørnerne af løsningspolyederet (se figur).

Formålet med tjenesten. Ved hjælp af af denne tjeneste muligt i online-tilstand løse det lineære programmeringsproblem ved hjælp af den geometriske metode, og også opnå en løsning på dobbeltproblemet (vurdere den optimale udnyttelse af ressourcer). Derudover oprettes en løsningsskabelon i Excel.

Instruktioner. Vælg antallet af rækker (antal begrænsninger).

Antal restriktioner 1 2 3 4 5 6 7 8 9 10
Hvis antallet af variable er mere end to, er det nødvendigt at bringe systemet til SZLP (se eksempel og eksempel nr. 2). Hvis begrænsningen er dobbelt, for eksempel 1 ≤ x 1 ≤ 4, så opdeles den i to: x 1 ≥ 1, x 1 ≤ 4 (dvs. antallet af rækker øges med 1).
Du kan også bygge et gennemførligt løsningsområde (ADA) ved hjælp af denne service.

Følgende bruges også med denne lommeregner:
Enkel metode til løsning af ZLP

Løsning af transportproblemet
Løsning af et matrixspil
Ved hjælp af onlinetjenesten kan du bestemme prisen på et matrixspil (nedre og øvre grænser), kontrollere tilstedeværelsen af ​​et sadelpunkt, finde en løsning på en blandet strategi ved hjælp af følgende metoder: minimax, simpleksmetode, grafisk (geometrisk) ) metode, Browns metode.
Ekstremum af en funktion af to variable
Beregning af grænser

Løsning af et lineært programmeringsproblem ved hjælp af grafisk metode omfatter følgende trin:

  1. Linjer er konstrueret på planet X 1 0X 2.
  2. Halve fly er bestemt.
  3. Definer en løsningspolygon;
  4. Der konstrueres en vektor N(c 1, c 2), som angiver retningen af ​​objektivfunktionen;
  5. Gå fremad objektiv funktion c 1 x 2 + c 2 x 2= 0 i retningen af ​​vektor N til det yderste punkt af løsningspolygonen.
  6. Punktets koordinater og værdien af ​​objektivfunktionen på dette punkt beregnes.
Følgende situationer kan opstå:

Eksempel. Virksomheden producerer to typer produkter - P1 og P2. Til produktion af produkter bruges to typer råmaterialer - C1 og C2. Bulk priser produktionsenhed er lig med: 5 enheder. til P1 og 4 enheder til P2. Forbruget af råvarer pr. produktenhed af type P1 og type P2 er angivet i tabellen.
Tabel - Forbrug af råvarer til produktion

Der er etableret restriktioner for produktefterspørgsel: den daglige produktionsmængde for P2-produkter bør ikke overstige den daglige produktionsmængde for P1-produkter med højst 1 ton; Den maksimale daglige produktionsvolumen af ​​P2 bør ikke overstige 2 tons.
Du skal bestemme:
Hvor mange produkter af hver type skal virksomheden producere for at maksimere indkomsten fra produktsalget?
  1. Formuler matematisk model lineære programmeringsproblemer.
  2. Løs et lineært programmeringsproblem grafisk(for to variable).
Løsning.
Lad os formulere en matematisk model af det lineære programmeringsproblem.
x 1 - produktion af produkter P1, enheder.
x 2 - produktion af produkter P2, enheder.
x 1, x 2 ≥ 0

Ressourcegrænser
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6

Krav restriktioner
x 1 +1 ≥ x 2
x 2 ≤ 2

Objektiv funktion
5x 1 + 4x 2 → maks

Så 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

Opgave. Løs det lineære programmeringsproblem grafisk ved at bestemme den ekstreme værdi af objektivfunktionen:

under restriktioner

Lad os konstruere en region af gennemførlige løsninger, dvs. Lad os løse ulighedssystemet grafisk. For at gøre dette konstruerer vi hver lige linje og definerer halvplanerne defineret af ulighederne (halvplanerne er angivet med et primtal).

Lad os bygge ligningen 3x 1 +x 2 = 9 på to punkter.
For at finde det første punkt sidestiller vi x 1 = 0. Vi finder x 2 = 9. For at finde det andet punkt sidestiller vi x 2 = 0. Vi finder x 1 = 3. Vi forbinder punktet (0;9) med (3;0) med en lige linje. Lad os definere halvplanet defineret af uligheden. Efter at have valgt punktet (0; 0), definerer vi ulighedstegnet i halvplanet: 3. 0 + 1. 0 - 9 ≤ 0, dvs. 3x 1 +x 2 - 9≥ 0 i halvplanet over den rette linje.
Lad os konstruere ligningen x 1 +2x 2 = 8 på to punkter.
For at finde det første punkt sætter vi lighedstegn mellem x 1 = 0. Vi finder x 2 = 4. For at finde det andet punkt sætter vi lighedstegn mellem x 2 = 0. Vi finder x 1 = 8. Vi forbinder punktet (0;4) med (8;0) med en lige linje. Lad os definere halvplanet defineret af uligheden. Efter at have valgt punktet (0; 0), definerer vi ulighedstegnet i halvplanet: 1. 0 + 2. 0 - 8 ≤ 0, dvs. x 1 +2x 2 - 8≥ 0 i halvplanet over den rette linje.
Lad os konstruere ligningen x 1 + x 2 = 8 på to punkter.
For at finde det første punkt sætter vi lighedstegn mellem x 1 = 0. Vi finder x 2 = 8. For at finde det andet punkt sætter vi lighedstegn mellem x 2 = 0. Vi finder x 1 = 8. Vi forbinder punktet (0;8) med (8;0) med en lige linje. Lad os definere halvplanet defineret af uligheden. Efter at have valgt punktet (0; 0), definerer vi ulighedstegnet i halvplanet: 1. 0 + 1. 0 - 8 ≤ 0, dvs. x 1 +x 2 - 8≤ 0 i halvplanet under den rette linje.

Skæringspunktet mellem halvplaner vil være et område, hvis punktkoordinater opfylder ulighederne i systemet af begrænsninger af problemet.
Lad os betegne grænserne for området af løsningspolygonen.

Du kan kontrollere rigtigheden af ​​konstruktionen af ​​funktionsgrafer ved hjælp af en lommeregner

Overvej opgavens objektive funktion F = 4x 1 +6x 2 → min.
Lad os konstruere en ret linje svarende til værdien af ​​funktionen F = 0: F = 4x 1 +6x 2 = 0. Gradientvektoren, der er sammensat af koefficienterne for den objektive funktion, angiver retningen for minimering af F(X). Begyndelsen af ​​vektoren er punkt (0; 0), slutningen er punkt (4; 6). Lad os flytte denne lige linje på en parallel måde. Da vi er interesserede minimal løsning, så vi flytter den lige linje, indtil den først rører det udpegede område. På grafen er denne lige linje angivet med en stiplet linje.

Lige F(x) = 4x 1 +6x 2 skærer området ved punkt B. Da punkt B er opnået som et resultat af skæringen af ​​linjer (1) Og (2) , så opfylder dens koordinater ligningerne for disse linjer:
3x1 +x2 =9
x 1 + 2 x 2 = 8

Efter at have løst ligningssystemet får vi: x 1 = 2, x 2 = 3
Hvordan kan vi finde minimumsværdien af ​​objektivfunktionen:
F(X) = 4*2 + 6*3 = 26