Metoder optimale løsninger

INDHOLD

Hovedbestemmelserne i disciplinen "Metoder til optimale løsninger" er grundlaget for den matematiske uddannelse af en certificeret specialist, der har vigtig for succesfuldt studium af særlige discipliner, der er fastsat i hoveduddannelsen for dette speciale.

For effektiv absorption undervisningsmateriale og opnåelse af endelig certificering er nødvendig inden for de fastsatte frister læseplan, udføre kontrolopgaver og give dem til kontrol af læreren iflg e-mail. Tidsplanen for studier og rapportering efter disciplin er vist i tabel 1.

Tabel 1. Graf selvstændigt arbejde i disciplinen "Metoder til optimale løsninger"

1. INTRODUKTION. GENEREL FORMULERING AF PROBLEMET

Beslutningsprocesser er kernen i alle målrettede aktiviteter. Inden for økonomi går de forud for oprettelsen af ​​produktions- og erhvervsorganisationer og sikrer deres optimale funktion og interaktion. I videnskabelig undersøgelse– gøre det muligt at identificere de vigtigste videnskabelige problemer, finde måder at studere dem på og forudbestemme udviklingen af ​​det eksperimentelle grundlag og det teoretiske apparat. Mens du skaber ny teknologi– udgøre vigtigt stadium i design af maskiner, enheder, instrumenter, komplekser, bygninger, i udviklingen af ​​teknologi til deres konstruktion og drift; V sociale sfære– bruges til at organisere funktion og udvikling af sociale processer, deres koordinering med økonomiske og økonomiske processer. Optimale (effektive) løsninger giver dig mulighed for at nå mål med minimumsomkostninger arbejdskraft, materiale- og råmaterialeressourcer.

I klassisk matematik overvejes metoder til at finde optimale løsninger i afsnit relateret til studiet af ekstrema funktioner i matematisk programmering.

Optimale beslutningsmetoder er en af ​​grenene af operationsforskning - anvendt retning kybernetik, brugt til at løse praktiske organisatoriske problemer. Matematiske programmeringsproblemer bruges i forskellige områder menneskelig aktivitet, hvor det er nødvendigt at vælge et af de mulige handlingsforløb (handlingsprogrammer).

Et betydeligt antal problemer, der opstår i samfundet, er forbundet med kontrollerede fænomener, det vil sige med fænomener, der reguleres på baggrund af bevidst truffet beslutninger. Med den begrænsede mængde information, der var tilgængelig på tidlige stadier udvikling af samfundet, blev den optimale beslutning truffet baseret på intuition og erfaring, og derefter, med en stigning i mængden af ​​information om det fænomen, der blev undersøgt, ved hjælp af en række direkte beregninger. Dette skete for eksempel i forbindelse med oprettelsen af ​​arbejdsplaner for industrivirksomheder.

Et helt andet billede opstår for eksempel i en moderne industrivirksomhed med multi-batch og multi-item produktion, når mængden af ​​inputinformation er så stor, at den behandles med henblik på accept bestemt beslutning umuligt uden brug af moderne elektronisk computere. Endnu større vanskeligheder opstår i forbindelse med problemet med at træffe den bedste beslutning.

I kurset "Optimale beslutningsmetoder" forstås beslutningstagning som en kompleks proces, hvor der kan skelnes mellem følgende hovedstadier:

1. etape. Konstruktion kvalitetsmodel det problem, der overvejes, dvs. at identificere de faktorer, der synes at være de vigtigste, og etablere de mønstre, som de adlyder. Normalt går denne fase ud over matematik.

2. etape. Konstruktion af en matematisk model af det pågældende problem, dvs. at skrive en kvalitativ model i matematiske termer. Således er den matematiske model skrevet ind matematiske symboler en abstraktion af et virkeligt fænomen, så konstrueret, at dets analyse gør det muligt at trænge ind i fænomenets essens. En matematisk model etablerer relationer mellem et sæt af variable - parametrene til at kontrollere et fænomen. Dette trin omfatter også konstruktionen af ​​en målfunktion af variable, dvs. en numerisk karakteristik, hvis større (eller mindre) værdi svarer til den bedste situation set ud fra den beslutning, der træffes.

Så som et resultat af disse to faser, den tilsvarende matematisk problem. Desuden kræver anden fase allerede brug af matematisk viden.

3. etape. Undersøgelse af variables indflydelse på værdien af ​​den objektive funktion. Dette trin involverer mestring af det matematiske apparat til løsning af matematiske problemer, der opstår på anden fase af beslutningsprocessen.

En bred klasse af kontrolproblemer består af sådanne ekstreme problemer, i hvis matematiske modeller betingelserne for variablerne er specificeret af ligheder og uligheder. Teorien og metoderne til at løse disse problemer er netop indholdet af matematisk programmering. På tredje trin, ved hjælp af matematiske værktøjer, findes en løsning på de tilsvarende ekstreme problemer. Lad os henlede opmærksomheden på det faktum, at matematiske programmeringsproblemer forbundet med løsning af praktiske problemer som regel har stort antal variabler og restriktioner. Mængden af ​​beregningsarbejde for at finde passende løsninger er så stor, at hele processen er utænkelig uden brug af moderne elektroniske computere (computere), og kræver derfor enten oprettelse af computerprogrammer, der implementerer bestemte algoritmer, eller brug af allerede eksisterende standard programmer.

4. etape. Sammenligning af beregningsresultaterne opnået på 3. trin med det modellerede objekt, dvs. ekspertverifikation af resultaterne (praksiskriterium). På dette stadium er graden af ​​tilstrækkelighed af modellen og det modellerede objekt således etableret inden for nøjagtigheden af ​​den indledende information. Der er to mulige tilfælde her:

1. tilfælde. Hvis sammenligningsresultaterne er utilfredsstillende (en almindelig situation i indledende fase modelleringsprocessen), fortsæt derefter til den anden cyklus af processen. Samtidig afklares inputinformationen om det modellerede objekt og om nødvendigt tydeliggøres problemformuleringen (trin 1); den matematiske model forfines eller genopbygges (trin 2); det tilsvarende matematiske problem løses (3. trin), og til sidst udføres sammenligningen igen (4. trin).

2. tilfælde. Hvis sammenligningsresultaterne er tilfredsstillende, accepteres modellen. Når det drejer sig om gentagen brug af beregningsresultater i praksis, opstår opgaven med at udarbejde modellen til drift. Antag for eksempel, at formålet med modellering er at skabe kalenderplaner for en virksomheds produktionsaktiviteter. Herefter omfatter driften af ​​modellen indsamling og bearbejdning af information, indtastning af de bearbejdede informationer i en computer, beregninger baseret på udviklede skemaprogrammer og endelig udsendelse af beregningsresultater (i en brugervenlig form) til deres brug inden for området. produktionsaktiviteter.

Der er to retninger i matematisk programmering.

Den første, allerede veletablerede retning - selve matematisk programmering - omfatter deterministiske problemer, der antager, at al indledende information er fuldstændig defineret.

Den anden retning - den såkaldte stokastiske programmering - omfatter problemer, hvor den indledende information indeholder elementer af usikkerhed, eller når nogle parametre af problemet er tilfældige i naturen med kendte sandsynlighedsmæssige karakteristika. Planlægning af produktionsaktiviteter udføres således ofte under forhold med ufuldstændig information om den reelle situation, hvor planen vil blive implementeret. Eller for eksempel, når et ekstremt problem simulerer arbejdet automatiske enheder, som er ledsaget af tilfældig interferens. Bemærk, at en af ​​de største vanskeligheder ved stokastisk programmering ligger i selve formuleringen af ​​problemerne, hovedsageligt på grund af kompleksiteten i at analysere den indledende information.

Traditionelt er matematisk programmering opdelt i følgende hovedafsnit:

Lineær programmering – objektivfunktionen er lineær, og det sæt, hvorpå yderpunktet af objektivfunktionen søges, er specificeret af et system af lineære ligheder og uligheder. Til gengæld er der i lineær programmering klasser af problemer, hvis struktur giver dig mulighed for at skabe specielle metoder til at løse dem, som sammenligner positivt med metoder til løsning af problemer generel. Således dukkede et afsnit af transportproblemer op i lineær programmering.

Ikke-lineær programmering – den objektive funktion og begrænsninger er ikke-lineære. Ikke-lineær programmering er normalt opdelt som følger:

Konveks programmering - den objektive funktion er konveks (hvis problemet med at minimere det overvejes), og det sæt, som det ekstreme problem løses på, er konveks.

Kvadratisk programmering – objektivfunktionen er kvadratisk, og begrænsningerne er lineære ligheder og uligheder.

Multiekstremale problemer. Her skelnes sædvanligvis specialiserede klasser af problemer, der ofte opstår i applikationer, for eksempel problemer med at minimere konkave funktioner på et konveks sæt.

En vigtig gren af ​​matematisk programmering er heltals programmering, når heltalsbetingelser pålægges variablerne.

Målet med matematisk programmering er at skabe, hvor det er muligt, analytiske metoder at bestemme løsningen, og i mangel af sådanne metoder, skabe effektive beregningsmetoder til at opnå en omtrentlig løsning.

Endelig bemærker vi, at emnets navn – ”metoder til optimale løsninger” – skyldes, at målet med at løse problemer er at vælge et handlingsprogram. Lad os se nærmere på problemet med lineær programmering

2. GEOMETRISK FORTOLKNING AF DET LINEÆRE PROGRAMMERINGSPROBLEM

Lineært programmeringsproblem (LPP):

find vektoren X = (x 1 ,x 2 ,...,x n), der maksimerer den lineære form

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

J=1

og opfylder betingelserne:

Σa ij x j ≤ bi (2.2)

J=1

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

Den lineære funktion F kaldes problemets objektive funktion.

Lad os omskrive dette problem ind vektor form:

Lad os finde funktionerne:

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)

hvor P 1, ..., P n og P 0 er m-dimensionelle vektorsøjler, fra koefficienterne for de ukendte og frie led i problemets ligningssystem:

B 1 a 11 a 12 a 1n

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

… … … …

B n a m1 a m2 a mn

Planen X = (x 1 ,x 2 ,...,x n) kaldes referenceplanen for hoved-ZLP'en, hvis de positive koefficienter x j er ved lineært uafhængige vektorer P j .

Et løsningspolyhedron er ethvert ikke-tomt sæt planer for det lineære hovedprogrammeringsproblem, og ethvert hjørnepunkt i et løsningspolyeder kaldes et toppunkt.

Sætning

Hvis det primære OPP har en optimal plan, maksimal værdi den objektive funktion af problemet tager et af hjørnerne af løsningspolyederet.

Hvis den objektive funktion af et problem tager sin maksimale værdi ved mere end ét toppunkt, så tager den den på ethvert punkt, der er en konveks lineær kombination af disse toppunkter.

Konklusioner:

Det ikke-tomme sæt af planer for den vigtigste ZLP danner et konveks polyeder;

Hvert hjørne af dette polyeder definerer en referenceplan;

Ved et af polyederens hjørner er værdien af ​​objektivfunktionen maksimal.

Todimensionelt tilfælde af ZLP

Lad os finde en løsning på problemet, som består i at bestemme den maksimale værdi af funktionen

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 programmeringsproblem er at finde et punkt i løsningspolygonen, hvor objektivfunktionen F får den maksimale værdi. Dette punkt eksisterer, når løsningspolygonen ikke er tom, og objektivfunktionen på den er afgrænset ovenfra.

For at bestemme dette toppunkt konstruerer vi en niveaulinje c 1 x 1 +c 2 x 2 =h, (hvor h er en eller anden konstant), der går gennem løsningspolygonen, og vi flytter den i retning af vektoren C = ( c 1,c 2) indtil den passerer gennem sit sidste fælles punkt med løsningspolygonen. Koordinaterne for det angivne punkt bestemmer den optimale plan for denne opgave.

Niveauer OPP-beslutninger geometrisk metode:

1. Konstruer rette linjer ved hjælp af ligningerne (2.9), (2.10).

2. Find de halvplaner, der er defineret af hver af problemets begrænsninger.

3. Find løsningspolygonen.

4. Konstruer vektor C.

5. Konstruer en ret linje c 1 x 1 + c 2 x 2 =h, der går gennem løsningspolygonen.

6. Flyt den rette linje c 1 x 1 + c 2 x 2 =h i retningen af ​​vektor C.

7. Bestem koordinaterne for funktionens maksimumpunkt og beregn værdien af ​​den objektive funktion på dette punkt.

Eksempel 1.

Til at producere to typer produkter A og B anvender virksomheden tre typer råvarer. Forbrugsraterne for hver type råvare til fremstilling af en produktenhed af denne type er angivet i tabel 2.1. Det angiver også fortjenesten ved salg af et produkt af hver type og den samlede mængde råvarer af denne type, som virksomheden kan bruge.

Tabel 2.1

I betragtning af at produkter A og B kan fremstilles i ethvert forholdnias (salg sikres), er det nødvendigt at udarbejde en plan for deres udgivelse, hvoriVirksomhedens maksimale fortjeneste ved salg af alle produkter er lille

Løsning:

x1 – produktion af produkter af type A

x2 – produktion af produkter af type B

Så er problemet begrænsninger:

Den samlede fortjeneste ved salg af produkter af type A og B vil være: F = 30x 1 + 40x 2

Lad os finde en løsning på problemet ved hjælp af dens geometriske fortolkning.

For at gøre dette, i ulighederne i begrænsningssystemet, lad os gå videre til ligheder og konstruere de tilsvarende lige linjer:

Lad os finde koordinaterne for punkt B - skæringspunktet mellem linjer:

Efter at have løst dette ligningssystem får vi: x 1 = 12; x 2 = 18

Derfor, hvis en virksomhed producerer 12 produkter af type A og 18 produkter af type B, så vil den modtage en maksimal fortjeneste svarende til

F max = 30·12+40·18 = 1080 gnid.

Eksempel 2.

Løs PIL

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

Løsning. At bygge et område tilladte løsninger Vi konstruerer lige grænselinjer i systemet x 1 Ox 2, der svarer til disse ulighedsbegrænsninger:

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

Vi finder halvplaner, hvori disse uligheder holder. For at gøre dette, på grund af konveksiteten af ​​et hvilket som helst halvplan, er det nok at tage et vilkårligt punkt, gennem hvilket den tilsvarende grænse lige linje ikke passerer, og kontrollere, om dette testpunkt opfylder ulighedsbegrænsningen. Hvis den opfylder, så er denne ulighed opfyldt i halvplanet, der indeholder prøvepunktet. Ellers tages et halvt plan, der ikke indeholder et testpunkt. Det er ofte praktisk at tage udgangspunktet for koordinaterne O(0; 0) som et testpunkt. For vores eksempel er regionen med mulige løsninger sættet af punkter i firkanten ABCD (fig. 6).

Vi konstruerer en vektor c = (c 1; c 2) = (2; 3). Da det kun er nødvendigt at tydeliggøre stigningsretningen af ​​den objektive funktion, er det nogle gange for større klarhed praktisk at konstruere λc(λ > 0). Vinkelret på vektoren c tegner vi en niveaulinje F=0. Ved parallel bevægelse af den rette linje F=0 finder vi det ekstreme punkt B, hvor objektivfunktionen tager maksimumværdien, og punkt A, hvor minimumsværdien opnås.

Koordinaterne for punkt B bestemmes af systemet

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

OPGAVER TIL SELVSTÆNDIG LØSNING

Løs problemer 1.1-1.10 grafisk.

Problem med mange variabler

Overvej følgende lineære programmeringsproblem

For at løse det grafisk er det nødvendigt at transformere systemet af begrænsninger på en sådan måde, at systemet i form af hovedproblemet ikke indeholder mere end 2 variabler.

Dette kan gøres sekventielt, ekskluderende variabler eller ved at bruge Jordan-Gauss-metoden. Lad os overveje Jordan-Gauss-metoden.

tabel 1

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

tabel 2

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

Tabel 3

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

Tabel 4

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

Lad os kassere ikke-negative tilladte ukendte i begrænsningsligningerne

x 2 , x 4 , x 5 og erstatte lighedstegnet med ulighedstegn, får vi hjælpeopgave lineær programmering med to variable:

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

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

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

3. ENKEL METODE TIL LØSNING AF ET LINEÆRT PROGRAMMERINGSPROBLEM

3.1. Geometrisk fortolkning af simpleksmetoden

Hvis et lineært programmeringsproblem er optimeret, svarer det optimale til hjørnepunktet (mindst et) af O.D.R. og falder sammen med mindst én af de ikke-negative basisløsninger. Altså sortering igennem endeligt nummer ikke-negative grundlæggende løsninger af systemet, vælger vi fra dem den, der svarer til den ekstreme værdi af den objektive funktion. Grafisk betyder det, at vi går gennem hjørnepunkterne af løsningspolyederet, hvilket forbedrer værdien af ​​den objektive funktion.

Simplex metoden består af:

1) at bestemme den oprindelige acceptable grundlæggende løsning opgaver;

2) at gå til en bedre løsning;

3) at kontrollere den optimale gennemførlige løsning.

3.2. Tabelfortolkning af simpleksmetoden

Simplexmetoden bruges til at løse lineære programmeringsproblemer skrevet i kanonisk form:

Find den optimale løsning

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

opfylder systemet af begrænsninger (ligninger)

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

j=1

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

og giver den ekstreme værdi af den objektive funktion

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

j=1

Lad den indledende ikke-negative basisløsning af system (3.2) findes, hvor x 1, x 2, x 3 ... x m er de grundlæggende ukendte, og x m+1, x m+2, ..., x n er gratis ukendte.

Så bliver system (3.2) til et tilladt system

(3.4)

Dette system svarer til en ikke-negativ basisløsning af formen

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

Lad os erstatte den resulterende løsning med den objektive funktion

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

J=1

og transformer det på en sådan måde, at det kun afhænger af de frie ukendte x m+1, x m+2, ... x n

Alle grundlæggende ukendte x 1, x 2, x 3 ... x m kan udtrykkes i form af fri x m+1, x m+2, … x n og erstatte det i den objektive funktion.

Så vil objektivfunktionen antage formen (3.6)

Lad os introducere konceptet med at estimere Δ j af frie ukendte

(3.7)

Så vil den objektive funktion antage formen

(3.8)

Lad os introducere vektorerne C = (c 1 , c 2 , …, c m) og B = (a 1j , a 2j , …, a mj) (j=m+1,n) , så kan lighed (3.7) skrives i vektorform

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

Lighed (3.8) er ikke forskellig i karakter fra systemets ligninger, så lad os tilføje det til dette system og få et udvidet system:

Resultaterne af de udførte transformationer, registreret som et system, kan indtastes i følgende simplekstabel:

den første kolonne indeholder de grundlæggende ukendte x 1 , x 2 , ..., x m ; Kolonne C indeholder koefficienterne fra den objektive funktion svarende til disse grundlæggende ubekendte; i kolonne B - frie termer af systemligningerne, der falder sammen med de positive komponenter af den initiale ikke-negative basisløsning X 0 . Under de ukendte x 1 , x 2 , …, x n er koefficienterne fra systemet skrevet i kolonnerne.

Den sidste række i denne tabel, kaldet evalueringen eller indekset, s beregnes ved hjælp af formler. Når man går fra én basisløsning til For en anden kan den estimerede linje også beregnes direkte efter reglen kvadrat (Jordan-Gauss-metoden).

I evalueringslinjen betyder uligheden Δ j ≥0 optimalitetskriteriet for referenceplanen.

Algoritme til løsning af ZLP ved hjælp af simplex-metoden.

1. Find referenceplanen.

2. Opret en simplekstabel.

3. Find ud af, om der er mindst én et negativt talΔj

Hvis ikke, så er den fundne referenceplan optimal. Hvis der blandt tallene er Δ j negative, så er enten problemets uløselighed fastslået chi, eller gå videre til en ny referenceplan.

4. Find guidekolonnen og rækken. Den største kolonne bestemmes af det største negative tal Δ j i absolut værdi , og ledelinjen er minimum af forholdet mellem kolonnekomponenterne i vektoren Po og de positive komponenter i styresøjlen.

5. Bestem de positive komponenter ved hjælp af formlerne (3.7) – (3.9). ny referenceplan, nedbrydningskoefficienter af vektorer P j til vektorer nyt grundlag og antal. Alle disse tal er skrevet i den nye simplex bord.

6. Tjek den fundne plan for optimalitet. Hvis planen ikke er optimal, og det er nødvendigt at flytte til en ny referenceplan, så vend tilbage til punkt 4, og hvis der opnås en optimal plan eller etableres mere end én gang Med beslutsomhed afsluttes processen med at løse problemet.

Eksempel 3.1.

Til fremstilling af forskellige produkter A, B og C bruger virksomheden tre forskellige typer råmateriale. Satser for råvareforbrug til produktion af et produkt af hver type, prisen på et produkt A, B og C samt den samlede mængde råvarer af hver type, der kan anvendes af virksomheden vi spiser, kl er vist i tabellen.

Lav en produktionsplan for produkter, hvor de samlede omkostninger af alle producerede produkter vil være maksimalt.

Løsning:

Lad os skabe en matematisk model. Lad os betegne:

x 1 – produktion af produkter af type A;

x 2 – produktion af produkter af type B;

x3 – produktion af produkter af type C.

Lad os nedskrive systemet med begrænsninger:

De samlede omkostninger for producerede varer er:

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

Ifølge det økonomiske indhold kan variablerne x 1, x 2, x 3 kun have ikke-negative værdier:

x 1, x 2, x 3 ≥0

Lad os skrive dette problem i form af den vigtigste ZLP, for dette går vi fra systemet med uligheder til ligheder, for dette introducerer vi tre yderligere variabler:

Den økonomiske betydning af de nye variable er mængden af ​​råvarer af den ene eller anden type, som ikke anvendes i en given produktionsplan.

Lad os skrive det transformerede ligningssystem 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

Da der blandt vektorerne Pj er tre enhedsvektorer, kan vi for dette problem skrive referenceplanen X = (0, 0, 0, 360, 192, 180) defineret af systemet af enhedsvektorer P 4, P 5, P 6, som danner grundlaget for det tredimensionelle rum.

Vi kompilerer en simplekstabel med iteration I og beregner værdierne af F 0, z j -c j.

Vi tjekker den oprindelige plan for optimalitet:

Fo = (C, Po) = 0; z1=(C,P1)=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 tal Δ j er i 4. række i kolonne P 3. Derfor introducerer vi vektoren P 3 i basisen. Lad os definere vektoren til at være undtagelse fra grundlaget, for dette finder vi Θ 0 = min(b i /a ij) for a i3 >0 dvs. Θ = min (360/12; 192/8; 180/3) = 192/8 = 24.

De der. den begrænsende faktor for produktion af produkter C er tilgængelig mængde råvarer af type II. Under hensyntagen til dens tilgængelighed kan virksomheden producere 24 produkter C, mens råvarer af type II vil blive fuldstændigt forbrugt vano.

Som følge heraf skal vektoren P 5 udelukkes fra basis. Kolonne vektorerne P 3 og 2. række er hjælpelinjer.

Lad os lave en tabel til iteration II. Først udfylder vi rækken af ​​vektoren, der nyligt er indført i basis, dvs. ledelinje 2. Elementerne i denne linje fås ved at dividere de tilsvarende elementer i tabel 1 med aktiveringselement (dvs. 8). Samtidig skriver vi i kolonne C b koefficienten patient C 3 = 16, stående i kolonnen af ​​vektoren P 3 indført i basis

For at bestemme de resterende elementer i tabel II anvender vi trekantreglen.

Lad os beregne elementerne i tabel II i kolonnen P 0.

Første element - find tre tal

1) tallet i linje 1 i skæringspunktet mellem kolonne P0 og 1. linje (360);

2) tallet i linje 1 i skæringspunktet mellem kolonne P3 og 1. linje (12);

3) tallet i punkt 2 i skæringspunktet mellem kolonne P0 og 2. linje (24).

360-12 24 = 72

Det andet element blev beregnet tidligere (Θ 0 = 192/8 =24)

Tredje element -

1) tallet i linje 1 i skæringspunktet mellem kolonne P0 og 3. linje (180);

2) tallet i linje 1 i skæringspunktet mellem kolonne P3 og 3. linje (3);

3) tallet i punkt 2 i skæringspunktet mellem kolonne P0 og 2. linje (24).

180-3·24 =108

Værdien af ​​F 0 i 4. række i samme kolonne kan findes på to måderbami:

1) ifølge formlen F 0 =(C, P 0) =0,72+16,24+0,108 = 384;

2) efter trekantsreglen:

Lad os beregne elementerne i vektoren P 1 t.2. Vi tager de to første tal fra kolonnentsov R 1 og R 3 v.1,

og det tredje tal er fra punkt 2 i skæringspunktet mellem 2. række og kolonne P1.

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

Nummer z 1 - c 1 i 4. række i kolonnen af ​​vektor P 1 i tabel 2

kan findes på to måder:

1) ifølge formlen z 1 -с 1 =(C,P 1)-c 1 har vi:

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

2) efter trekantsreglen får vi:

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

På samme måde finder vi elementerne i kolonnen af ​​vektoren P 2.

Elementerne i kolonnen af ​​vektoren P 5 beregnes ved hjælp af trekantsreglen.

Men de trekanter, der er konstrueret til at definere disse elementer

Ved beregning af elementet i 1. række i den angivne kolonne er resultatettrekant dannet af tallene 0;12 og 1/8. Derfor er det ønskedeelement er ens

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

Elementet på 3. linje af denne kolonne, er lige

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

Efter afslutning af beregningen af ​​alle elementer i tabel II opnåede den mengrundlæggende plan og koefficienter for ekspansion af vektorer Р j til grundlæggendevektorer P 4, P 3, P 6 og værdier F 0 "Δ j".

Som det fremgår af denne tabel, er den nye referenceplan for problemetplan X=(0; 0; 24; 72; 0; 108).

Problemplanen fundet ved iteration II er ikke optimal.

denne linje indeholder et negativt tal - 2. Dette kan også ses fra 4. linje i tabel 2, da i kolonnen af ​​vektoren P 2 .

Det betyder, at vektoren P 2 skal indgå i grundlaget, dvs. den nye plan skal sørge for produktion af produkter B.

Ved bestemmelse af det mulige antal produktioner af produkter B bør man tage højde for den tilgængelige mængde råvarer af hver type, nemlig: evt. outputtet af produkter B er bestemt af min (b i "/a i 2") for a i2 ">0, dvs. vi finder Θ 0 = min(72/9; 24 2/1; 108 2/3) = 72/9= 8.

Som følge heraf er vektor P4 udelukket fra grundlaget, med andre ord er produktionen af ​​produkter B begrænset af de råvarer af type I, som virksomheden har til rådighed. Under hensyntagen til de tilgængelige mængder af dette råmateriale skal virksomheden producere 8 produkter B. Tallet 9 er det løsende element, og kolonnen i vektoren P2 og 1. række i tabel 2 er guiderne.

Lad os oprette en tabel til iteration III.

I tabel III udfylder vi først elementerne i den 1. række, som er rækken af ​​vektoren P2, der netop er indført i basisen. Elementerne i denne række fås fra elementerne i 1. række i tabel 2 ved at dividere sidstnævnte med det opløselige element (dvs. med 9).

Samtidig skriver vi i kolonne C b i denne række c 2 = 10.

Derefter udfylder vi elementerne i kolonnerne i basisvektorerne og ved hjælp af trekantsreglen beregner vi elementerne i de resterende kolonner.

Som et resultat opnår vi i tabel III en ny referenceplan X = (0; 8; 20; 0; 0; 96) og ekspansionskoefficienter for vektorerne P j gennem basisvektorerne P 1, P 2 og P 3 tilsvarende værdier ​F 0 "" og Δ j .

Vi tjekker om den givne referenceplan er optimal eller ej. For at gøre dette skal du overveje den 4. række, tabel 3. Der er ingen negative tal blandt tallene i denne linje. Det betyder, at den fundne referenceplan er optimal og F max =400.

Derfor er en produktionsplan, der omfatter produktion af 8 produkter B og 20 produkter C, optimal. Med denne produktproduktionsplan er råvarer af type I og II fuldt ud brugt, og 96 kg råvarer af type III forbliver ubrugte, og prisen på de producerede produkter er 400 €.

Den optimale produktionsplan giver ikke mulighed for produktion af produkter A. Indførelse af produkter af type A i produktionsplanen vil føre til et fald i de angivne samlede omkostninger. Dette kan ses fra 4. række i kolonnen af ​​vektor P1, hvor tallet 5 viser, at for en given plan, herunder frigivelse af en enhed af produkt A i den, kun fører til et fald i de samlede omkostninger med 5 €.

Eksempel 3.2

Udfyld den indledende simplex-tabel for følgende PPP:

Løsning:

Lad os gøre det næste skridt i denne rækkefølge:

-i anden linje skriver vi de ukendte x 1, x 2, ..., x 5;

- i den første linje over dem er de tilsvarende koefficienter 3, -2, 1,4, -1 fra den objektive funktion;

-Under de ukendte x 1 , x 2 , …, x 5 udfyldes kolonnerne sammensat af de tilsvarende koefficienter på venstre side af ligningerne i det oprindelige system;

- i kolonnen nedskriver vi de frie led i ligning 3,1,5;

-i første kolonne B.p. lad os sætte de ukendte x 2 ,x 3 , x 5 , da der er enhedskolonner under dem, og derfor vil vi betragte dem som grundlæggende; de grundlæggende ukendte er arrangeret i en sådan rækkefølge, at enhederne i kolonnerne er i skæringspunktet mellem identiske ukendte;

-i kolonnen skriver vi koefficienterne -2,1,-1, fra objektivfunktionen for de udvalgte basale ubekendte x 2 ,x 3 , x 5 ;

- udfyld evalueringslinjen som følger: under kolonne B placerer vi tallet Δ 0, beregnet ved hjælp af formel (3.5); under grundlæggende ukendte x 2 ,x 3 , x 5 - nuller, som også kan opnås fra lighed (3.9); under frie variabler x 1 , x 4 - nedskriv værdierne opnået fra lighed (3.9).

Vi registrerer resultaterne af disse handlinger i følgende tabel:

Lad os vælge kolonnen x 4 som den løsende kolonne, som den "dårligeste" (den svarer til det største negative estimat i absolut værdi). Dernæst introducerer vi opløsningslinjen som følger: For positive koefficienter for x 4-kolonnen beregner vi forholdene b i /a i4 og skriver dem i kolonnen θ.

Det mindste tal bestemmer opløsningsstrengen. Vi betragter ikke negative og nul-koefficienter på grund af den ikke-negativitet af højre side af systemligningerne og kravet om, at den objektive funktion mindst skal være ikke-aftagende.

I skæringspunktet mellem tilladelsesrækken og tilladelseskolonnen skal du vælge tilladelseselementet. Lad os opnå, at det løsende element er lig med en, hvor vi deler hele den første linje med to. Dernæst transformerer vi tabellen ved hjælp af Jordan-Gauss-metoden.

Allerede i tabellen for andet trin er optimalitetskriteriet således opfyldt. Vi modtog den optimale plan X(0;0;11/2;3/2;13/2), max L(X) =5.