Metoder optimale løsninger

INNHOLD

Hovedbestemmelsene i disiplinen "Metoder for optimale løsninger" er grunnlaget for den matematiske utdanningen til en sertifisert spesialist som har viktig for vellykket studie av spesielle disipliner som er gitt i hovedutdanningsprogrammet for denne spesialiteten.

For effektiv absorpsjon undervisningsmateriell og innhenting av endelig sertifisering er nødvendig innen de fastsatte fristene læreplan, henrette kontrolloppgaver og gi dem til kontroll av lærer iht e-post. Tidsplanen for studier og rapportering etter disiplin er vist i tabell 1.

Tabell 1. Graf selvstendig arbeid i faget "Metoder for optimale løsninger"

1. INTRODUKSJON. GENERELL FORMULERING AV PROBLEMET

Beslutningsprosesser er kjernen i all målrettet virksomhet. I økonomi går de foran opprettelsen av produksjons- og forretningsorganisasjoner og sikrer optimal funksjon og samhandling. I Vitenskapelig forskning– gjøre det mulig å identifisere de viktigste vitenskapelige problemene, finne måter å studere dem på og forhåndsbestemme utviklingen av den eksperimentelle basen og det teoretiske apparatet. Mens du lager ny teknologi– utgjøre viktig stadium i design av maskiner, enheter, instrumenter, komplekser, bygninger, i utviklingen av teknologi for deres konstruksjon og drift; V sosial sfære– brukes til å organisere funksjon og utvikling av sosiale prosesser, deres koordinering med økonomiske og økonomiske prosesser. Optimale (effektive) løsninger lar deg nå mål med minimumskostnader arbeids-, material- og råstoffressurser.

I klassisk matematikk vurderes metoder for å finne optimale løsninger i seksjoner knyttet til studiet av ekstrema av funksjoner i matematisk programmering.

Optimale beslutningsmetoder er en av grenene innen operasjonsforskning - anvendt retning kybernetikk, brukt til å løse praktiske organisatoriske problemer. Matematiske programmeringsproblemer brukes i ulike områder menneskelig aktivitet, der det er nødvendig å velge en av de mulige handlingsmåtene (handlingsprogrammer).

Et betydelig antall problemer som oppstår i samfunnet er knyttet til kontrollerte fenomener, det vil si fenomener regulert på grunnlag av bevisste beslutninger. Med den begrensede mengden informasjon som var tilgjengelig på tidlige stadier utvikling av samfunnet, den optimale beslutningen ble tatt basert på intuisjon og erfaring, og deretter, med en økning i mengden informasjon om fenomenet som studeres, ved hjelp av en serie direkte beregninger. Dette skjedde for eksempel ved opprettelsen av arbeidsplaner for industribedrifter.

Et helt annet bilde oppstår, for eksempel i en moderne industribedrift med multi-batch og multi-item produksjon, når volumet av inputinformasjon er så stort at det behandles med formålet om aksept. bestemt avgjørelse umulig uten bruk av moderne elektronisk datamaskiner. Enda større vanskeligheter oppstår i forbindelse med problemet med å ta den beste avgjørelsen.

I kurset "Optimale beslutningsmetoder" forstås beslutningstaking som en kompleks prosess der følgende hovedstadier kan skilles:

1. trinn. Konstruksjon kvalitetsmodell problemet under vurdering, det vil si å identifisere faktorene som ser ut til å være de viktigste og etablere mønstrene de adlyder. Vanligvis går dette stadiet utover matematikk.

2. trinn. Konstruksjon av en matematisk modell av problemet under vurdering, dvs. å skrive en kvalitativ modell i matematiske termer. Dermed er den matematiske modellen skrevet inn matematiske symboler en abstraksjon av et reelt fenomen, slik konstruert at dets analyse gjør det mulig å trenge inn i fenomenets essens. En matematisk modell etablerer forhold mellom et sett med variabler – parametrene for å kontrollere et fenomen. Dette stadiet inkluderer også konstruksjonen av en målfunksjon av variabler, dvs. en numerisk karakteristikk hvis større (eller mindre) verdi tilsvarer den beste situasjonen fra synspunktet til beslutningen som tas.

Så, som et resultat av disse to stadiene, den tilsvarende matematisk problem. Dessuten krever den andre fasen allerede bruk av matematisk kunnskap.

3. trinn. Studie av påvirkning av variabler på verdien av den objektive funksjonen. Dette stadiet innebærer å mestre det matematiske apparatet for å løse matematiske problemer som oppstår i andre fase av beslutningsprosessen.

En bred klasse av kontrollproblemer består av slike ekstreme problemer, i hvis matematiske modeller betingelsene på variablene er spesifisert av likheter og ulikheter. Teorien og metodene for å løse disse problemene er nettopp innholdet i matematisk programmering. På det tredje trinnet, ved hjelp av matematiske verktøy, blir en løsning på de tilsvarende ekstreme problemene funnet. La oss rette oppmerksomheten mot det faktum at matematiske programmeringsproblemer knyttet til å løse praktiske problemer som regel har stort antall variabler og restriksjoner. Volumet av beregningsarbeid for å finne passende løsninger er så stort at hele prosessen er utenkelig uten bruk av moderne elektroniske datamaskiner (datamaskiner), og krever derfor enten opprettelse av dataprogrammer som implementerer visse algoritmer, eller bruk av allerede eksisterende standard. programmer.

4. trinn. Sammenligning av beregningsresultatene oppnådd på 3. trinn med det modellerte objektet, dvs. ekspertverifisering av resultatene (praksiskriterium). Således, på dette stadiet, er graden av tilstrekkelighet for modellen og det modellerte objektet etablert innenfor nøyaktigheten til den første informasjonen. Det er to mulige tilfeller her:

1. tilfelle. Hvis sammenligningsresultatene er utilfredsstillende (en vanlig situasjon i det første stadiet modelleringsprosess), fortsett deretter til den andre syklusen av prosessen. Samtidig klargjøres inngangsinformasjonen om det modellerte objektet og om nødvendig klargjøres problemstillingen (trinn 1); den matematiske modellen foredles eller bygges om (trinn 2); det tilsvarende matematiske problemet løses (3. trinn) og til slutt utføres sammenligningen på nytt (4. trinn).

2. tilfelle. Hvis sammenligningsresultatene er tilfredsstillende, aksepteres modellen. Når det gjelder gjentatt bruk av beregningsresultater i praksis, oppstår oppgaven med å utarbeide modellen for drift. Anta for eksempel at formålet med modellering er å lage kalenderplaner for produksjonsaktivitetene til en bedrift. Deretter inkluderer driften av modellen innsamling og bearbeiding av informasjon, innføring av den behandlede informasjonen i en datamaskin, beregninger basert på utviklede tidsplanprogrammer og til slutt utgivelse av beregningsresultater (i en brukervennlig form) for deres bruk innen fagområdet produksjonsaktiviteter.

Det er to retninger i matematisk programmering.

Den første, allerede veletablerte retningen - selve matematisk programmering - inkluderer deterministiske problemer som forutsetter at all innledende informasjon er fullstendig definert.

Den andre retningen - den såkalte stokastiske programmeringen - inkluderer problemer der den første informasjonen inneholder elementer av usikkerhet, eller når noen parametere ved problemet er tilfeldige i naturen med kjente sannsynlighetsegenskaper. Planlegging av produksjonsaktiviteter utføres derfor ofte under forhold med ufullstendig informasjon om den reelle situasjonen der planen vil bli implementert. Eller for eksempel når et ekstremt problem simulerer arbeidet automatiske enheter, som er ledsaget av tilfeldig interferens. Legg merke til at en av hovedvanskene ved stokastisk programmering ligger i selve formuleringen av problemene, hovedsakelig på grunn av kompleksiteten ved å analysere den første informasjonen.

Tradisjonelt er matematisk programmering delt inn i følgende hovedseksjoner:

Lineær programmering - objektivfunksjonen er lineær, og settet som ytterpunktet til objektivfunksjonen søkes på er spesifisert av et system med lineære likheter og ulikheter. I sin tur, i lineær programmering er det klasser av problemer, hvis struktur lar deg lage spesielle metoder for å løse dem, som sammenligner gunstig med metoder for å løse problemer generell. Dermed dukket det opp en del av transportproblemer i lineær programmering.

Ikke-lineær programmering - den objektive funksjonen og begrensningene er ikke-lineære. Ikke-lineær programmering er vanligvis delt inn som følger:

Konveks programmering - objektivfunksjonen er konveks (hvis problemet med å minimere det vurderes) og settet som det ekstreme problemet løses på er konveks.

Kvadratisk programmering – objektivfunksjonen er kvadratisk, og begrensningene er lineære likheter og ulikheter.

Multiekstremale problemer. Her skilles vanligvis spesialiserte klasser av problemer som ofte oppstår i applikasjoner, for eksempel problemer med å minimere konkave funksjoner på et konveks sett.

En viktig gren av matematisk programmering er heltallsprogrammering, når heltallsbetingelser pålegges variablene.

Målet med matematisk programmering er å skape, der det er mulig, analytiske metoder bestemme løsningen, og i fravær av slike metoder, skape effektive beregningsmetoder for å oppnå en omtrentlig løsning.

Til slutt bemerker vi at navnet på faget – «metoder for optimale løsninger» – skyldes at målet med å løse problemer er å velge et handlingsprogram. La oss se nærmere på problemet med lineær programmering

2. GEOMETRISK TOLKNING AV DET LINEÆRE PROGRAMMERINGSPROBLEMET

Lineært programmeringsproblem (LPP):

finn vektoren X = (x 1 ,x 2 ,...,x n) som maksimerer den lineære formen

F = Σ c j x j → maks (2,1)

J=1

og oppfyller vilkårene:

Σa ij x j ≤ b i (2.2)

J=1

x j ≥0 , j = 1,…,n (2,3)

Den lineære funksjonen F kalles den objektive funksjonen til problemet.

La oss omskrive dette problemet inn vektorform:

La oss finne funksjonene:

F = c 1 x 1 + c 2 x 2 + … + c n x n (2,4)

x 1 P 1 + x 2 P 2 + … + x n P n = P 0 , (2,5)

x j ≥0 , j = 1,…,n (2,6)

der P 1, ..., P n og P 0 er m-dimensjonale vektorkolonner, fra koeffisientene til de ukjente og frie ledd i likningssystemet for problemet:

B 1 a 11 a 12 a 1n

Po = (b2); Pi = (a 21); P 2 = (a 22) ;……. Pn = (a2n); (2,7)

… … … …

B n a m1 a m2 a mn

Planen X = (x 1 ,x 2 ,...,x n) kalles referanseplanen til hoved-ZLP hvis de positive koeffisientene x j er ved lineært uavhengige vektorer P j .

Et løsningspolyeder er et hvilket som helst ikke-tomt sett med planer for det viktigste lineære programmeringsproblemet, og ethvert hjørnepunkt i et løsningspolyeder kalles et toppunkt.

Teorem

Hvis hoved-OPS har en optimal plan, maksimal verdi den objektive funksjonen til problemet tar på et av toppunktene til løsningspolyederet.

Hvis den objektive funksjonen til et problem tar sin maksimale verdi ved mer enn ett toppunkt, tar den den på et hvilket som helst punkt som er en konveks lineær kombinasjon av disse toppunktene.

Konklusjoner:

Det ikke-tomme settet med planer til hoved-ZLP danner et konveks polyeder;

Hvert toppunkt av dette polyederet definerer en referanseplan;

Ved en av toppunktene til polyederet er verdien av objektivfunksjonen maksimal.

Todimensjonalt tilfelle av ZLP

La oss finne en løsning på problemet, som består i å bestemme maksimalverdien av funksjonen

F = c 1 x 1 + c 2 x 2 (2,8)

under forhold

a i1 x 1 + a i2 x 2 ≤ bi , (i=1,…,k) (2,9)

x j ≥0 (j=1,2) (2,10)

Det lineære programmeringsproblemet er å finne et punkt i løsningspolygonet der objektivfunksjonen F får maksimalverdien. Dette punktet eksisterer når løsningspolygonet ikke er tomt og objektivfunksjonen på den er avgrenset ovenfra.

For å bestemme dette toppunktet vil vi konstruere en nivålinje c 1 x 1 +c 2 x 2 =h, (hvor h er en konstant) som går gjennom løsningspolygonet, og vi vil flytte den i retning av vektoren C = ( c 1,c 2) til den passerer gjennom sitt siste felles punkt med løsningspolygonet. Koordinatene til det angitte punktet bestemmer den optimale planen for denne oppgaven.

Stadier OPS-vedtak geometrisk metode:

1. Konstruer rette linjer ved å bruke ligningene (2.9), (2.10).

2. Finn halvplanene definert av hver av begrensningene til problemet.

3. Finn løsningspolygonet.

4. Konstruer vektor C.

5. Konstruer en rett linje c 1 x 1 +c 2 x 2 =h som går gjennom løsningspolygonet.

6. Flytt den rette linjen c 1 x 1 + c 2 x 2 =h i retningen til vektor C.

7. Bestem koordinatene til maksimumspunktet for funksjonen og beregn verdien av objektivfunksjonen på dette punktet.

Eksempel 1.

For å produsere to typer produkter A og B bruker selskapet tre typer råvarer. Forbruksratene for hver type råvare for produksjon av en produktenhet av denne typen er gitt i tabell 2.1. Det indikerer også fortjenesten fra salg av ett produkt av hver type og den totale mengden råvarer av denne typen som kan brukes av bedriften.

Tabell 2.1

Tatt i betraktning at produktene A og B kan produseres i alle forholdnias (salg er sikret), er det nødvendig å utarbeide en plan for utgivelsen derMaksimal fortjeneste for bedriften fra salg av alle produkter er liten

Løsning:

x1 – produksjon av produkter av type A

x2 – produksjon av produkter av type B

Da er problemet begrensninger:

Den totale fortjenesten ved salg av produkter av type A og B vil være: F = 30x 1 + 40x 2

La oss finne en løsning på problemet ved å bruke dens geometriske tolkning.

For å gjøre dette, i ulikhetene i restriksjonssystemet, la oss gå videre til likheter og konstruere de tilsvarende rette linjene:

La oss finne koordinatene til punkt B - skjæringspunktet mellom linjer:

Etter å ha løst dette ligningssystemet får vi: x 1 = 12; x 2 = 18

Derfor, hvis en bedrift produserer 12 produkter av type A og 18 produkter av type B, vil den motta en maksimal fortjeneste lik

F maks = 30·12+40·18 = 1080 gni.

Eksempel 2.

Løs PIL

maks(min)F = 2x1 +3x2;

Løsning. Å bygge et område tillatte løsninger Vi konstruerer rette grenselinjer i systemet x 1 Ox 2 som tilsvarer disse ulikhetsbegrensningene:

x 1 +x 2 ≤ 6, x 1 +4x 2 ≥ 4, 2x 1 -x 2 ≥ 0.

Vi finner halvplan der disse ulikhetene holder. For å gjøre dette, på grunn av konveksiteten til et hvilket som helst halvplan, er det nok å ta et vilkårlig punkt som den korresponderende rette grensen ikke passerer gjennom, og sjekke om dette testpunktet tilfredsstiller ulikhetsbegrensningen. Hvis den tilfredsstiller, er denne ulikheten tilfredsstilt i halvplanet som inneholder prøvepunktet. Ellers tas et halvplan som ikke inneholder et testpunkt. Det er ofte praktisk å ta opprinnelsen til koordinatene O(0; 0) som et testpunkt. For vårt eksempel er regionen med gjennomførbare løsninger settet med punkter til firkanten ABCD (fig. 6).

Vi konstruerer en vektor c = (c 1; c 2) = (2; 3). Siden det bare er nødvendig å klargjøre økningsretningen til objektivfunksjonen, er det noen ganger for større klarhet praktisk å konstruere λc(λ > 0). Vinkelrett på vektoren c tegner vi en nivålinje F=0. Ved parallell bevegelse av den rette linjen F=0 finner vi ekstrempunktet B der objektivfunksjonen tar maksimumsverdien og punktet A hvor minimumsverdien oppnås.

Koordinatene til punkt B bestemmes av systemet

Hvor er Fmax = F (A) = 32/9

OPPGAVER FOR UAVHENGIG LØSNING

Løs problemer 1.1-1.10 grafisk.

Problem med mange variabler

Tenk på følgende lineære programmeringsproblem

For å løse det grafisk, er det nødvendig å transformere systemet med restriksjoner på en slik måte at systemet i form av hovedproblemet ikke inneholder mer enn 2 variabler.

Dette kan gjøres sekvensielt, ekskluderende variabler, eller ved å bruke Jordan-Gauss-metoden. La oss vurdere Jordan-Gauss-metoden.

Tabell 1

(-3) 1 , (-1) 3,4

tabell 2

(2) 1 , (-1) 2 ,(1) 3

Tabell 3

(-1) 2 , (1) 3 ,(2) 4

Tabell 4

(-1) 2 , (1) 3 ,(2) 4

La oss forkaste ikke-negative tillatte ukjente i begrensningsligningene

x 2 , x 4 , x 5 og erstatte likhetstegnet med ulikhetstegn, får vi hjelpeoppgave lineær programmering med to variabler:

F (x) = 2 x 3 +2 → maks

F (x) = 0: 2 x 3 +2 -0 (0;-1) ;(5;-1)

Fmaks = 2 ved x 1 = 0; x 3 = 0

3. ENKEL METODE FOR LØSE ET LINEÆRT PROGRAMMERINGSPROBLEM

3.1. Geometrisk tolkning av simpleksmetoden

Hvis et lineært programmeringsproblem er optimalisert, tilsvarer det optimale hjørnepunktet (minst ett) av O.D.R. og faller sammen med minst én av de ikke-negative basisløsningene. Altså sortering endelig nummer ikke-negative grunnleggende løsninger av systemet, velger vi fra dem den som tilsvarer den ekstreme verdien av den objektive funksjonen. Grafisk betyr dette at vi går gjennom hjørnepunktene til løsningspolyederet, og forbedrer verdien av objektivfunksjonen.

Simplexmetoden består av:

1) bestemme den innledende akseptable grunnleggende løsning oppgaver;

2) gå til en bedre løsning;

3) sjekke den optimale gjennomførbare løsningen.

3.2. Tabellform tolkning av simpleksmetoden

Simplexmetoden brukes til å løse lineære programmeringsproblemer skrevet i kanonisk form:

Finn den optimale løsningen

X = (x 1,x 2,...,x n) (3.1)

tilfredsstiller systemet av begrensninger (ligninger)

Σa ij x j = bi (i=1,m) (3.2)

j=1

og betingelser x j ≥ 0 (j=1,n)

og gir den ekstreme verdien av den objektive funksjonen

Z(x) = Σ c j x j (3,3)

j=1

La den innledende ikke-negative basisløsningen av system (3.2) bli funnet, der x 1, x 2, x 3 ... x m er de grunnleggende ukjente, og x m+1, x m+2, ..., x n er gratis ukjente.

Da blir system (3.2) til et tillatt system

(3.4)

Dette systemet tilsvarer en ikke-negativ grunnløsning av skjemaet

X 0 = (b 1 ,b 2 ,...,b m ,0,0...0)

La oss erstatte den resulterende løsningen i den objektive funksjonen

Δ 0 = L(X 0) = Σ C j B j (3,5)

J=1

og transformer det på en slik måte at det bare avhenger av de frie ukjente x m+1, x m+2, ... x n

Alle grunnleggende ukjente x 1, x 2, x 3 ... x m kan uttrykkes i form av gratis x m+1, x m+2, … x n og erstatte den med den objektive funksjonen.

Da vil objektivfunksjonen ha formen (3.6)

La oss introdusere konseptet med å estimere Δ j av frie ukjente

(3.7)

Da vil objektivfunksjonen ta formen

(3.8)

La oss introdusere vektorene C = (c 1 , c 2 , …, c m) og B = (a 1j , a 2j , …, a mj) (j=m+1,n) , så kan likhet (3.7) skrives i vektorform

Δj =CB j-c j(3,9)

Likhet (3.8) er ikke forskjellig i karakter fra systemets ligninger, så la oss legge det til dette systemet og få et utvidet system:

Resultatene av utførte transformasjoner, registrert som et system, kan legges inn i følgende simplekstabell:

den første kolonnen inneholder de grunnleggende ukjente x 1 , x 2 , ..., x m ; Kolonne C inneholder koeffisientene fra objektivfunksjonen som tilsvarer disse grunnleggende ukjente; i kolonne B - frie termer av systemligningene, sammenfallende med de positive komponentene til den innledende ikke-negative basisløsningen X 0 . Under de ukjente x 1 , x 2 , …, x n er koeffisientene fra systemet skrevet i kolonnene.

Den siste raden i denne tabellen, kalt evalueringen eller indeksen, s beregnes ved hjelp av formler. Når man går fra én grunnleggende løsning til For en annen kan den estimerte linjen også beregnes direkte i henhold til regelen kvadrat (Jordan-Gauss-metoden).

I evalueringslinjen betyr ulikheten Δ j ≥0 optimalitetskriteriet for referanseplanen.

Algoritme for å løse ZLP ved hjelp av simpleksmetoden.

1. Finn referanseplanen.

2. Lag en simplekstabell.

3. Finn ut om det er minst én et negativt tallΔj

Hvis ikke, er den funnet referanseplanen optimal. Hvis det blant tallene er Δ j negative, er enten problemets uløselighet etablert chi, eller gå videre til en ny referanseplan.

4. Finn guidekolonnen og raden. Den største kolonnen bestemmes av det største negative tallet Δ j i absolutt verdi , og ledelinjen er minimum av forholdet mellom kolonnekomponentene til vektoren P 0 og de positive komponentene i ledekolonnen.

5. Bruk formlene (3.7) – (3.9) og bestem de positive komponentene ny referanseplan, koeffisienter for dekomponering av vektorer P j til vektorer nytt grunnlag og antall. Alle disse tallene er skrevet i den nye simpleksen bord.

6. Sjekk den funnet planen for optimalitet. Hvis planen ikke er optimal og det er nødvendig å gå over til en ny referanseplan, gå tilbake til punkt 4, og hvis en optimal plan oppnås eller det etableres mer enn én gang Med besluttsomhet er prosessen med å løse problemet fullført.

Eksempel 3.1.

For å produsere ulike produkter A, B og C bruker selskapet tre forskjellige typer råvarer. Satser for råvareforbruk for produksjon av ett produkt av hver type, prisen på ett produkt A, B og C, samt total mengde råvarer av hver type som kan brukes av bedriften vi spiser, kl er vist i tabellen.

Lag en produksjonsplan for produkter der den totale kostnaden av alle produserte produkter vil være maksimalt.

Løsning:

La oss lage en matematisk modell. La oss betegne:

x 1 – produksjon av produkter av type A;

x 2 – produksjon av produkter av type B;

x3 – produksjon av produkter av type C.

La oss skrive ned systemet med restriksjoner:

Den totale kostnaden for produserte varer er:

F = 9x 1 +10x 2 +16x 3

I henhold til det økonomiske innholdet kan variablene x 1, x 2, x 3 bare ha ikke-negative verdier:

x 1, x 2, x 3 ≥0

La oss skrive dette problemet i form av hoved-ZLP, for dette går vi fra systemet med ulikheter til likheter, for dette introduserer vi tre ekstra variabler:

Den økonomiske betydningen av de nye variablene er mengden råvarer av en eller annen type som ikke brukes i en gitt produksjonsplan.

La oss skrive det transformerte ligningssystemet i vektorform:

x 1 P 1 +x 2 P 2 +x 3 P 3 +x 4 P 4 +x 5 P 5 +x 6 P 6 =P 0

Hvor

Siden det er tre enhetsvektorer blant vektorene Pj, kan vi for dette problemet skrive referanseplanen X = (0, 0, 0, 360, 192, 180) definert av systemet med enhetsvektorer P 4, P 5, P 6, som danner grunnlaget for tredimensjonalt rom.

Vi kompilerer en simplekstabell med iterasjon I og beregner verdiene til F 0, z j -c j.

Vi sjekker den opprinnelige planen for optimalitet:

Fo = (C, Po) = 0; z 1 = (C, P 1) = 0; z2=(C,P2)=0; z3=(C,P3)=0;

z1-c1 = 0-9 = -9; z2-c2 = 0-10 = -10; z3-c3 = 0-16 = -16;

For basisvektorer zj -c j = 0 (j=4,5,6).

Det maksimale negative tallet Δ j er i 4. rad i kolonne P 3. Følgelig introduserer vi vektoren P 3 i basisen. La oss definere vektoren til å være unntak fra grunnlaget, for dette finner vi Θ 0 = min(b i /a ij) for a i3 >0 dvs. Θ = min (360/12; 192/8; 180/3) =192/8 =24.

De. den begrensende faktoren for produksjon av produkter C er tilgjengelig volum av råvarer av type II. Tatt i betraktning tilgjengeligheten, kan bedriften produsere 24 produkter C, mens råvarer av type II vil bli fullstendig konsumert vano.

Følgelig må vektoren P 5 ekskluderes fra grunnlaget. Kolonne vektorene P 3 og 2. rad er guider.

La oss lage en tabell for iterasjon II. Først fyller vi ut raden av vektoren som nylig er introdusert i grunnlaget, dvs. ledelinje 2. Elementene i denne linjen oppnås ved å dele de tilsvarende elementene i tabell 1 med aktiveringselement (dvs. 8). Samtidig skriver vi i kolonne C b koeffisienten pasient C 3 =16, stående i kolonnen til vektoren P 3 introdusert i basisen

For å bestemme de gjenværende elementene i tabell II, bruker vi trekantregelen.

La oss beregne elementene i Tabell II i P 0-kolonnen.

Første element - finn tre tall

1) tallet i linje 1 i skjæringspunktet mellom kolonne P0 og 1. linje (360);

2) tallet i linje 1 i skjæringspunktet mellom kolonne P3 og 1. linje (12);

3) tallet i punkt 2 i skjæringspunktet mellom kolonne P0 og 2. linje (24).

360-12 24 = 72

Det andre elementet ble beregnet tidligere (Θ 0 = 192/8 =24)

Tredje element -

1) tallet i linje 1 i skjæringspunktet mellom kolonne P0 og 3. linje (180);

2) tallet i linje 1 i skjæringspunktet mellom kolonne P3 og 3. linje (3);

3) tallet i punkt 2 i skjæringspunktet mellom kolonne P0 og 2. linje (24).

180-3·24 =108

Verdien av F 0 i 4. rad i samme kolonne kan finnes på to måterbami:

1) i henhold til formelen F 0 =(C,P 0) =0,72+16,24+0,108 = 384;

2) i henhold til trekantregelen:

La oss beregne elementene i vektoren P 1 t.2. Vi tar de to første tallene fra kolonnentsov R 1 og R 3 v.1,

og det tredje tallet er fra punkt 2 i skjæringspunktet mellom 2. rad og kolonne P1.

18-12 (3/ 4) = 9; 5-3 (3/ 4)=11/ 4.

Nummer z 1 -c 1 i 4. rad i kolonnen til vektor P 1 i tabell 2

kan finnes på to måter:

1) i henhold til formelen z 1 -с 1 =(C,P 1)-c 1 har vi:

0 9+16 3/ 4+0 11/ 4-9 =3

2) i henhold til trekantregelen får vi:

-9-(-16) 3/ 4 = 3

På samme måte finner vi elementene i kolonnen til vektoren P 2.

Elementene i kolonnen til vektoren P 5 beregnes ved hjelp av trekantregelen.

ser annerledes ut. Imidlertid er trekantene konstruert for å definere disse elementene

Når du beregner elementet i den første raden i den angitte kolonnen, er resultatettrekant dannet av tallene 0;12 og 1/8. Derfor ønsketelement er likt

0 – 12 (1/8) = -3/2.

Elementet på 3. linje av denne kolonnen, er lik

0 - 3 (1 /8) = -3/8.

Etter fullføring av beregningen av alle elementene i tabell II, oppnådde den mengrunnleggende plan og koeffisienter for utvidelse av vektorer Р j til grunnleggendevektorer P 4, P 3, P 6 og verdiene F 0 "Δ j".

Som det fremgår av denne tabellen er den nye referanseplanen for problemstillingenplan X=(0; 0; 24; 72; 0; 108).

Problemplanen funnet ved iterasjon II er ikke optimal.

denne linjen inneholder et negativt tall - 2. Dette kan også sees fra den 4. linjen i tabell 2, siden i kolonnen til vektoren P 2 .

Dette betyr at vektoren P 2 skal legges inn i grunnlaget, dvs. den nye planen skal sørge for produksjon av produkter B.

Når man skal bestemme mulig antall produksjon av produkter B, bør man ta hensyn til tilgjengelig mengde råvarer av hver type, nemlig: evt. produksjonen av produkter B bestemmes av min (b i "/a i 2") for a i2 ">0, dvs. vi finner Θ 0 = min(72/9; 24 2/1; 108 2/3) = 72/9= 8.

Følgelig er vektor P4 underlagt utelukkelse fra grunnlaget, med andre ord er produksjonen av produkter B begrenset av råvarene av type I som er tilgjengelig for bedriften. Tatt i betraktning de tilgjengelige volumene av dette råmaterialet, bør bedriften produsere 8 produkter B. Tallet 9 er det løsende elementet, og kolonnen til vektoren P2 og 1. rad i tabell 2 er guidene.

La oss lage en tabell for iterasjon III.

I tabell III fyller vi først inn elementene i den første raden, som er raden til vektoren P2 som nylig er introdusert i basisen. Elementene i denne raden er hentet fra elementene i den første raden i tabell 2 ved å dele sistnevnte med det løsende elementet (dvs. med 9).

Samtidig skriver vi i kolonne C b i denne raden c 2 = 10.

Deretter fyller vi inn elementene i kolonnene til basisvektorene, og ved hjelp av trekantregelen beregner vi elementene i de gjenværende kolonnene.

Som et resultat får vi i tabell III en ny referanseplan X = (0; 8; 20; 0; 0; 96) og ekspansjonskoeffisienter for vektorene P j gjennom basisvektorene P 1, P 2 og P 3 tilsvarende verdier ​F 0 "" og Δ j .

Vi sjekker om gitt referanseplan er optimal eller ikke. For å gjøre dette, vurder den fjerde raden, tabell 3. Det er ingen negative tall blant tallene på denne linjen. Dette betyr at den funnet referanseplanen er optimal og F max =400.

Derfor er en produksjonsplan som inkluderer produksjon av 8 produkter B og 20 produkter C optimal. Med denne produktproduksjonsplanen er råvarer av type I og II fullt brukt og 96 kg råvarer av type III forblir ubrukt, og kostnadene for produktene som produseres er 400 €.

Den optimale produksjonsplanen sørger ikke for produksjon av produkter A. Innføring av produkter av type A i produksjonsplanen vil føre til en reduksjon i den angitte totalkostnaden. Dette kan sees fra den fjerde raden i kolonnen til vektor P1, der tallet 5 viser at for en gitt plan, inkludert utgivelse av en enhet av produkt A i den, bare fører til en reduksjon i den totale kostnaden med 5 €.

Eksempel 3.2

Fyll inn den første simplekstabellen for følgende PPP:

Løsning:

La oss gjøre det neste skritt i denne rekkefølgen:

-i den andre linjen skriver vi de ukjente x 1, x 2, ..., x 5;

- i den første linjen over dem er de tilsvarende koeffisientene 3, -2, 1,4, -1 fra objektivfunksjonen;

- under de ukjente x 1 , x 2 , …, x 5 , fyll inn kolonnene som er sammensatt av de tilsvarende koeffisientene til venstresiden av ligningene til det opprinnelige systemet;

- i kolonnen skriver vi ned de frie leddene til ligning 3,1,5;

-i første kolonne B.p. la oss sette det ukjente x 2 ,x 3 , x 5 , siden det er enhetskolonner under dem, og derfor vil vi vurdere dem som grunnleggende; de grunnleggende ukjente er ordnet i en slik rekkefølge at enhetene i kolonnene er i skjæringspunktet mellom identiske ukjente;

-i kolonnen skriver vi koeffisientene -2,1,-1, fra objektivfunksjonen for de valgte grunnleggende ukjente x 2 ,x 3 , x 5 ;

- fyll ut evalueringslinjen som følger: under kolonne B plasserer vi tallet Δ 0, beregnet ved hjelp av formel (3.5); under grunnleggende ukjente x 2 ,x 3 , x 5 - nuller, som også kan fås fra likhet (3.9); under frie variabler x 1 , x 4 - skriv ned verdiene oppnådd fra likestilling (3.9).

Vi registrerer resultatene av disse handlingene i følgende tabell:

La oss velge x 4-kolonnen som den løsende kolonnen, som den "dårligste" (den tilsvarer det største negative anslaget i absolutt verdi). Deretter introduserer vi oppløsningslinjen som følger: for positive koeffisienter for x 4-kolonnen, beregner vi forholdene b i /a i4 og skriver dem i kolonnen θ.

Det minste tallet vil bestemme oppløsningsstrengen. Vi tar ikke hensyn til negative og null koeffisienter på grunn av ikke-negativiteten til høyre side av systemligningene og kravet om at objektivfunksjonen minst skal være ikke-avtagende.

I skjæringspunktet mellom tillatelsesraden og tillatelseskolonnen, velg tillatelseselementet. La oss oppnå at det løsende elementet er lik en, som vi deler hele den første linjen med to. Deretter transformerer vi tabellen ved å bruke Jordan-Gauss-metoden.

Allerede i tabellen for det andre trinnet er således optimalitetskriteriet oppfylt. Vi fikk den optimale planen X(0;0;11/2;3/2;13/2), maks L(X) =5.