Modificeret simpleksmetode til løsning af målprogrammeringsproblemer. Modificeret simpleksmetode

1.5.1. Et beregningsskema baseret på transformation af inverse matricer. Ved at analysere beregningsproceduren for simplex-metoden ud fra synspunktet om at estimere arbejdsintensiteten er det let at se, at det mest kritiske i denne henseende er stadiet med genberegning af værdier EN Og b når du flytter fra en grundplan til en anden (klausul 3 i algoritmen). Men i det tilfælde, hvor antallet af begrænsninger af problemet m klart færre variabler n, kan du opnå betydelige "besparelser" ved at udføre ved næste iteration q Jordan-Gauss transformation ikke over matrix EN(β ( q)), og over matrixen Δ -1 (β ( q)). Dette tager også højde for, at man ved brug af formel (1.26) om nødvendigt altid kan opnå EN(β ( q)) med Δ -1 (β ( q)). Desuden havde vi faktisk ikke brug for en matrix for at udføre handlingerne i simplex-proceduren beskrevet ovenfor EN(β ( q)) helt. I virkeligheden blev der kun brugt ratinglinjen i den -en 0 (β ( q)) og ledende kolonne en l(β ( q)). Disse overvejelser danner grundlag for simplexmetodens beregningsskema baseret på transformation af inverse matricer, som også kaldes modificeret simpleksmetode. Først denne algoritme blev foreslået i 1951 i værker af L. V. Kantorovich.

Beregningsskemaet for den modificerede simplex-metode svarer til et system af tabeller T 1 og T 2 (q). Bord T 1 (ris. 1.7) er fælles for alle iterationer og tjener til at opnå en linje med estimater for den aktuelle basislinje -en 0 (β ( q)). Hvis vi betegner med δ jeg(β ( q)) (jegÎ 0: m) rækker af matrixen Δ -1 (β ( q)), så af (1.26), i særdeleshed, følger det

Som det kan ses af ris. 1.7, T 1 består af tre blokke:

Ø Ø centret indeholder matrix A;

Ø Ø i tabellens venstre blok ved hver iteration tilføjes nul rækker i matricenΔ -1 (β ( q))for det nuværende grundlag;

Ø Ø nederste blok placeret under matrix A, ved hver iteration suppleres den med en række estimater af den nuværende plan, beregnet ved hjælp af formel (1.42).

Simplex bord T 2 (q) vist i ris. 1.8, svarer til det tilladte KZLP-grundlag β ( q) modtaget kl q iterationen. Kolonne N(β ( q)) indeholder numrene på basiskolonnerne (i rækkefølgen af forekomst i basis); kolonne b(β ( q)) - komponenter af begrænsningsvektoren i forhold til den aktuelle basis β ( q); Δ -1 (β ( q)) - matrix invers til matrixen af udvidede kolonner af den aktuelle basis β ( q); kurve en l indeholder en udvidet vektor af forhold introduceret i basis ved den aktuelle iteration, og den næste graf indeholder koordinater en l(β ( q)) i samme kolonne i det aktuelle grundlag β ( q) .

I analogi med afsnit 1.4.1 vil vi beskrive det formelle skema for algoritmen for den modificerede simplex-metode.

0-trin. At finde en mulig baseline.

1. For at finde et acceptabelt grundlag kan metoden til at minimere rester, diskuteret i afsnit 1.4.5, anvendes. På samme tid at løse hjælpeopgave proceduren for den modificerede simplex-metode anvendes. Som et resultat af 0-stadiet opnår vi en mulig baseline x(β (1)) og den tilsvarende matrix Δ -1 (β (1)) og vektor b(β(1)).

2. Udfyld centrale del borde T 1 indeholdende matrixen EN.

3. Indhold af matrix Δ -1 (β (1)) og vektor b(β (1)), opnået i søgningen efter en godkendt grundplan, overføres til tabellen T 2 (1) .

4. Indstil nummeret på den aktuelle iteration q lig med 1 og gå til fase I.

Scene 1. Standard iteration af algoritmen- udføres til næste grundplan x(β ( q)).

1°. Kontrol af optimaliteten af den nuværende basisplan. Indholdet af nulrækken i tabellen T 2 (q) - δ 0 (β ( q)) omskrives til den tilsvarende kolonne i tabellen T 1 . Ved hjælp af formel (1.42) beregner og udfylder vi linjen -en 0 (β ( q)). Vi ser vurderingslinjen -en 0 (β ( q)). Der er to muligheder:

1. -en 0 (β ( q))≥0 -plan svarende til det aktuelle grundlag for problemet, optimal. Computerproces færdig. Ifølge formlerne (1.33) og (1.32) skriver vi optimal plan opgaver x* = x(β ( q)) Og optimal værdi objektiv funktion f(x*) = f(x(β ( q))).

1". I vurderingslinjen -en 0 (β ( q)) der er mindst ét element -en 0, j(β ( q))<0, т. е. имеющий отрицательную оценку. Следовательно, план x(β ( q)) - suboptimal. Nummer er valgt l, svarende til et element, der har en minimum (maksimum i absolut værdi) negativ score:

l matrix kolonne EN bliver til førende og skal indgå i næste grundlag. Lad os gå videre til punkt 2° i algoritmen.

2°. Definition af en kolonne afledt af et grundlag. Omskrivning af den førende kolonne en l fra bordet T 1 til den aktuelle tabel T 2 (q). Ifølge formlen en l(β ( q)) = Δ -1 (β ( q))en l udfyld den tilsvarende kolonne i tabellen T 2 (q). Der er to muligheder:

2". For alle jegО 1: m a i, l(β ( q))≤0. Det konkluderes, at ubegrænset objektiv funktion og computerprocessen slutter.

2". Der er mindst et indeks jegО 1: m, for hvilket a i, l(β ( q))>0. Efter regel (1.27) bestemmes placeringen r og nummer N r(β ( q)) for en kolonne afledt af grundlaget. Lad os gå videre til punkt 3° i algoritmen.

3°. Genberegning i forhold til det nye grundlag for elementer i kolonne b Og matricer A -1. Overgang til en ny basis β ( q+1), som opnås ved at indføre β ( q) kolonne en l og udsende en kolonne fra den en r, udføres ifølge formler svarende til formlerne (1.28)-(1.31). De ser ud som:

Vi indstiller nummeret på den aktuelle iteration q: =q+l og gå til det første punkt i algoritmen.

Afslutningsvis understreger vi, at det på grund af ovenstående fordele er den modificerede simplex-metode, der faktisk anvendes i software, designet til at løse kanoniske problemer lineær programmering.

1.5.2. Eksempel OPP-beslutninger modificeret simpleksmetode. Lad os præsentere en løsning på det tidligere overvejede problem (1.34)-(1.35), baseret på brugen af proceduren for den modificerede simplex-metode. Analogt med afsnit 1.4.3 begynder det med valget af et oplagt begyndelsesgrundlag dannet af kolonner (5,2,3). For det, Δ -1 (β ( q)) Og b(β ( q)), så udfyld de indledende tabeller T 1 og T 2, stk. 1, er ikke svært.

I den første iteration omskriver vi nullinjen

fra T 2 (1) tommer T 1 og gange det med matricen EN, får vi en række vurderinger

Fordi -en 0 (β (1)) indeholder negative elementer, så konkluderer vi, at planen svarende til grundlaget β (1) ikke er optimal, og ved at vælge det mindste negative estimat (-88) får vi nummeret på den indtastede kolonne grundlaget, l= 4.

Omskrivning af kolonnen

fra bordet T 1 in T 2 (1) og genberegn dens koordinater i forhold til det aktuelle grundlag, dvs. multiplicer matrixen Δ -1 (β ( q)), placeret i tabellen T 2 (1) til venstre, på EN 4 .

Efter at have udfyldt tabellen T 2 (1) Med dataene på kolonnen indtastet i det nye grundlag, kan du gå videre til at bestemme nummeret på outputkolonnen. Denne procedure udføres i fuldstændig analogi med den konventionelle simplex-metode. Efter at have overvejet forholdet mellem elementerne b i(β(1)) og a i, l(β (1)) for ( jegО1: m| a i, l(β (1))>0) og efter at have bestemt minimumet af dem, finder vi det r= 2. Derfor er kolonnen med nummer N 2 (β ( q)) = 2 skal udledes af grundlaget. Dermed opnår vi endnu et acceptabelt grundlag for problemet med N(β (2)) = (5, 4, 3). Element -en 2,3(β(1)) er førende (cirklet). Ved at anvende formlerne (1.43)-(1.46) går vi videre til simplekstabellen svarende til den anden iteration T 2 (2) , og indstil indekset for den aktuelle iteration q = 2.

Gentag de samme trin (de kan let følges fra tabellerne givet her) T 2 (2) og T 2 (3), ved den tredje iteration opnår vi den optimale plan for problemet og den optimale værdi af den objektive funktion, som uddrages fra den anden kolonne i tabellen T 2 (3). Det er let at bemærke, at vi i løsningsprocessen "gennemgik" den samme rækkefølge af tilladte grundplaner, som vi stødte på i afsnit 1.4.3.

Lad os overveje en metode til at løse CPU-problemet ved hjælp af ideerne fra simplex-metoden. Hovedtræk ved CPU-opgaver er designet af den objektive funktion og de variabler, der indikerer afvigelser fra det ønskede niveau for målopfyldelse. Hvis disse funktioner tages i betragtning, kan den sædvanlige simpleksmetode bruges til at løse sådanne problemer. Lad os illustrere dette ved at bruge det tidligere omtalte eksempel. Algoritmen er til en vis grad forenklet på grund af det faktum, at originalen grundlæggende løsning det er tydeligt her. Grundvariables rolle for indledende plan negative afvigelser "d" spiller her, som indgår i modellen med koefficienter på +1. Det er sværere med linjen for koefficienterne for den objektive funktion, dvs. med en evalueringslinje. Som vi ved, er koefficienterne for afvigelser i den objektive funktion af en CPU-opgave vægte, der rangerer mål efter prioritet. Deres numeriske værdier er som regel ikke bestemt. Det er vigtigt, at afvigelseskoefficienten for en målbegrænsning med højere prioritet er væsentligt større end koefficienten for afvigelse fra et lavere prioriteret mål. Derfor er evalueringslinjen opdelt i flere linjer (i henhold til antallet af prioriteter), af hensyn til beregningerne, og beregninger udføres for hver linje separat.

Så lad problemet løses min Z = P 1 d 1 - + P 2 d 2 - + P 3 d 3 + + P 4 d 4 - ,

forudsat at

7x 1 + 6x 2 + d 1 - – d 1 + = 30;

2x 1 + 3x 2 + d 2 - – d 2 + = 12;

6x 1 + 5x 2 + d 3 - – d 3 + = 30;

x 2 + d 4 - – d 4 + = 7;

x 1, x 2, di-, di + 3 0 (i = ).

Lad os oprette den indledende simplex-tabel (tabel 5.1.)

Tabel 5.1 – Indledende simplex bord

C j C B

Basis

Løsning

0 x 1

0 x 2

P 1 d 1 -

P 2 d 2 -

d 3 -

P 4 d 4 -

d 1+

d2+

P3d3+

d 4+

P 1 P 2 P 4

d 1 - d 2 - d 3 - d 4 -

-1

30/7 30/6 -

Z j – С j

P 4 P 3 P 2 P 1

-1

Som det er kendt, beregnes elementerne i evalueringslinjen (Z j - C j) i henhold til reglen: "fra summen af produkterne af elementerne i kolonnen "C in" af elementerne i den tilsvarende kolonne, element øverste linje" For eksempel for kolonnen "løsning" er elementet "Z j – C j" lig med: Р 1 *30 + Р 2 *12 + 0* 30 + р 4 *7 – 0 = 30Р 1 + 12Р 2 + 7Р 4 og koefficienter for den tilsvarende P i (i = ) er skrevet ud i denne kolonne i blokken "Z j - C j" (læs fra bund til top). For kolonnen "x 1": P 1 *7 + P 2 *2 + 0 * 6 + P 4 *0 – 0 = 7P 1 + 2P 2, og disse er koefficienterne for P 1 og P 2 i blokken " Z j – C j " osv.

Da CPU-problemet altid er løst til et minimum, vil løsningen være optimal, hvis alle elementer i evalueringslinjen ikke er positive. I vores tilfælde er to estimater (i kolonnerne "x 1" og "x 2") positive, derfor er planen ikke optimal. For at bestemme den variabel, der indgår i grundlaget, bestemmer vi ved den første iteration det største positive estimat. Det bestemmes af fortegnet for koefficienten ved P 1, fordi P 1 >> P 2 >> P 3 >> P 4 . Hvis koefficienterne for P 1 er ens, "går vi op" til linjen ovenfor og vælger den største koefficient der. I tilfælde af fuldstændig lighed på tværs af alle rækker, vælges enhver af dem. I vores tilfælde vil den løsende kolonne være kolonnen "x 1" (da 7 > 6). Opløsningsrækken vælges på samme måde som i simplexmetoden - i henhold til det mindste simpleksforhold q (vi dividerer elementerne i "løsnings"-kolonnen med de positive elementer i den løsende kolonne). I tabel 5.1 er det mindste forhold q i første række. Så ved næste iteration indtastes variablen "x 1" i grundlaget, "d 1 -" udlæses. Vi genberegner tabellen som i den sædvanlige simpleksmetode (tabel 5.2.)

Tabel 5.2 – Anden simplekstabel

C j C B

Basis

Løsning

x 1

x 2

P 1 d 1 -

P 2 d 2 -

d 3 -

P 4 d 4 -

d 1+

d2+

P3d3+

d 4+

P 2 P 4

x 1 d 2 - d 3 - d 4 -

30/7 24/7 30/7

6/7 9/7 1/7

1/7 2/7 6/7

-1

30/6 24/9 -

Z j – C j

P 4 P 3 P 2 P 1

24/7

9/7

2/7 -1

2/7

-1

Som vi kan se, fjernes d 2 - fra basis ved den anden iteration, og x 2 indføres i basis. Og så videre indtil vi får den optimale løsning. Efter 4. iteration får vi tabel 5.3.

Tabel 5.3 – Endelig simplekstabel

C j C B	Basis	Løsning	x 1	x 2	P 1 d 1 -	P 2 d 2 -	d 3 -	P 4 d 4 -	d 1+	d2+	P3d3+	d 4+
P 4	d 2 + x 2 d 1 + d 4 -		1,6 1,2 0,2 -1,2		-1	-1	0,6 0,2 1,2 -0,2				-0,6 -0,2 -1,2 0,2	-1
Z j – C j	P 4 P 3 P 2 P 1		-1,2		-1	-1	-0,2				0,2 -1	-1

At der er et positivt element i rækken ved P 4 (i kolonne d 3 +) betyder, at det fjerde mål ikke er helt nået. I dette tilfælde er målfunktionen lig med P 4, dette er dens mindst mulige værdi. Generelt er estimatet af variablen d 3 + lig med (0,2 P 4 - P 3), og da P 3 >> P 4 er det i sidste ende negativt. Alle andre estimater er ikke-positive, derfor er planen optimal set fra simplex-metoden.

Løsningen på dette problem kan kommenteres som følger. For at fuldføre opgaven er det nødvendigt at producere et andet produkt i mængden af 6 enheder. (x 2 = 6). Frigiv ikke det første produkt. Samtidig blev det første og andet mål overskredet med 6 enheder. (d 1 + = d 2 + = 6), og den fjerde er underopfyldt med 1 enhed. (d4-=1). Det modtagne overskud var således 6 enheder. mere end det ønskede niveau blev den første ressource brugt ud over den normale grænse med 6 enheder, og produkter af 2. type kunne ikke produceres i det ønskede volumen - i stedet for 7 enheder. udgivet 6 (den 2. ressource manglede; dens "besparelse" er et højere prioriteret mål).

Afslutningsvis, lad os som et eksempel på at skabe en model for en CPU-opgave oprette en model til en anden opgave.

Eksempel 5.2. Byens administration planlægger at udvide idrætsfaciliteterne. Byens budget afsatte 5,4 millioner rubler til disse formål. Det var planlagt yderligere at bygge fire typer sportsfaciliteter: tennisbaner, svømmebassiner, mikrostadioner (atletikbaner) og gymnastiksale. Dataene vedrørende disse projekter er som følger (tabel 5.4).

Tabel 5.4 – Oplysninger om genstande under opførelse

Løsning. Byen har afsat 20 hektar friareal til disse formål, men om nødvendigt kan dette areal udvides. Ved gennemførelsen af dette projekt opstiller administrationen følgende mål i rækkefølge:

1) opfylde det budgetterede beløb;

2) de opførte sportsfaciliteter skal give mindst 14.000 besøg om ugen;

3) i videst muligt omfang imødekomme den forventede efterspørgsel efter idrætsfaciliteter. Når du genererer objektivfunktionen for disse objektive begrænsninger, skal du bruge vægte, der er proportionale med forventet brug;

4) ved implementering af projektet, hvis det er muligt, skal du ikke optage mere end den tildelte plads Fri plads på 20 hektar.

Når vi udarbejder en model for denne opgave, vil vi huske på, at begrænsningerne ved formulering af mål ikke er kategoriske og kan være enten over- eller underopfyldte.

Opgavevariabler: x 1, x 2, x 3, x 4 – henholdsvis antallet af byggede strukturer: tennisbaner, svømmebassiner, atletikbaner og gymnastiksale.

Alle restriktioner vil blive målrettet, der er ingen systemrestriktioner.

Det første mål er at nå det tildelte beløb:

120x 1 + 600x 2 + 480x 3 + 1.200x 4 + d 1 - – d 1 + = 5.400.

Vi minimerer "overforbruget": min Z = P 1 d 1 + .

Det andet mål er mindst 14.000 besøg om ugen:

500 x 1 + 1.000x 2 + 2.000x 3 + 1.500x 4 + d 2 - – d 2 + = 14.000

Vi minimerer "underbesøg". Under hensyntagen til det første mål har vi:

min Z = P1d1++P2d2-.

Implementeringen af det tredje mål vil kræve implementering af 4 begrænsninger for hver type struktur:

x 1 + d3 - – d3 + = 8;

x 2 + d 4 - – d 4 + = 3;

x 3 + d 5 - – d 5 + = 3;

x 4 + d 6 - – d 6 + = 2.

Vi minimerer "underopfyldelse". Dette er det tredje vigtigste mål, derfor vil alle 4 led i målfunktionen have en koefficient P 3, men med forskellige skalaer:

min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5 P 3 d 6 -.

Fjerde mål: 0,8x 1 + 5x 2 + 3,2x 3 + 1,6x 4 + d 7 - – d 7 + = 20.

Objektiv funktion under hensyntagen til alle mål:

min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5 P 3 d 6 - + P 4 d 7 +.

Så problemmodellen vil have formen:

Find min Z = P 1 d 1 + + P 2 d 2 - + 0,5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1,5P 3 d 6 - + P 4 d 7 +

forudsat at

120x 1 + 600x 2 + 480x 3 + 1200x 4 + d 1 - – d 1 + = 5 400,

500x 1 + 1.000x 2 + 2.000x 3 + 1.500x 4 + d 2 - – d 2 + = 14.000,

x 1 + d 3 - – d 3 + = 8,

x 2 + d 4 - – d 4 + = 3,

x 3 + d 5 - – d 5 + = 3,

x 4 + d 6 - – d 6 + = 2,

0,8x 1 + 2x 2 + 3,2x 3 + 1,6x 4 + d 7 - – d 7 + = 20.

x j³ 0 (j =); di-, di + 30 (i = ).

Hvis dette problem er løst på sædvanlig måde simpleks metode, så skal vægtene P i gives specifikke værdier, men tag dog højde for, at P 1 >> P 2 >>...>> P 7 . Udviklede sig særlige programmer at løse sådanne problemer. Ved at implementere en af dem (QM for Window-programmet) opnår vi følgende optimale løsning (tabel 5.5):

Tabel 5.5 – Løsning af problemet fra eksempel 5.2.

(Målprogrammering)

x 1 = 8, x 2 = 3, x 3 = 3, x 4 = 1, d 2 + = 500, d 6 - = 1, d 7 + = 3,6. (d 7 + = –653.994 er det kodede tal 3.6 - det er angivet i Priority 4-linjen). Den angivne underopfyldelse (Ikke-præstation) i Prioritet 3-linjen, lig med 1,5, tager højde for vægtningskoefficienten i målfunktionen ved ).

Så med de afsatte midler er det muligt at bygge 8 tennisbaner, 3 swimmingpools, 3 ministadioner og et fitnesscenter. Som vi kan se, er det fjerde mål underopfyldt med 1 (d = 1), dvs. i stedet for de to planlagte bygges én gymnastiksal. Det andet mål blev overskredet (d 2 + = 500), dvs. i stedet for 14.000 besøg er der mulighed for 14.500. Det 4. mål blev også overskredet (d 7 + = 3,6), dvs. i stedet for de afsatte 20 hektar til disse idrætsanlæg, vil der blive behov for 23,6 hektar.

Kapitel 6. Metoder netværksplanlægning og ledelse

Netværksplanlægningsmetoder gør det muligt at analysere et sæt værker, som bl.a stort antal indbyrdes forbundne operationer. Du kan bestemme den sandsynlige varighed af alt arbejde, deres omkostninger, mulige tidsbesparelser eller Penge, samt hvilke operationer der ikke kan forsinkes uden at forsinke projektet som helhed. Problemet med at stille ressourcer til rådighed er også vigtigt. Metoder netværksanalyse kan bruges til at udarbejde en tidsplan for udførelse af operationer, der tilfredsstiller eksisterende restriktioner at stille ressourcer til rådighed.

Analysen af ethvert projekt udføres i tre faser:

1. Opdeling af projektet i et antal separate værker (eller operationer), hvorfra der så udarbejdes et logisk diagram.

2. Skøn over varigheden af hver operation; udarbejdelse af en projektplan og fremhævelse af det arbejde, der afgør projektets afslutning som helhed.

3. Vurdering af ressourcebehovet for hver operation; revision af driftsplanen under hensyntagen til tilvejebringelsen af ressourcer eller
omfordeling af penge eller andre ressourcer, der vil forbedre planen.

Når listen er kompileret, kan den logiske rækkefølge af operationer illustreres ved hjælp af en graf. Eksisterer Forskellige typer grafer, men de mest brugte er de såkaldte vertex- og pilegrafer.

Optimeringsproblem i matematik er problemet med at finde yderpunktet for en reel funktion i en bestemt region. Som regel betragtes domæner, der tilhører og defineres af et sæt ligheder og uligheder.

3.1. Beskrivelse

Det lineære programmeringsproblem er, at det er nødvendigt at maksimere eller minimere nogle lineære funktioner på et multidimensionelt rum under givne lineære begrænsninger.

Hver af lineære uligheder into variables begrænser et halvt rum i det tilsvarende lineære rum. Som følge heraf bandt alle uligheder et bestemt polyeder (muligvis uendeligt), også kaldet en polyederkegle.

Ligningen W(x) = c, hvor W(x) er den lineære funktion, der skal maksimeres (eller minimeres), genererer hyperplanet L(c). Afhængigheden af c genererer en familie af parallelle hyperplaner. I dette tilfælde antager det ekstreme problem følgende formulering: det er påkrævet at finde det største c, således at hyperplanet L(c) skærer polyederen i det mindste i ét punkt. Bemærk, at skæringspunktet mellem et optimalt hyperplan og et polyeder vil indeholde mindst ét toppunkt, og der vil være mere end ét, hvis skæringspunktet indeholder en kant eller en k-dimensionel flade. Derfor kan det maksimale af det funktionelle søges ved polyederens toppunkter. Princippet for simpleksmetoden er, at en af polyederens toppunkter vælges, hvorefter bevægelse begynder langs dens kanter fra toppunkt til toppunkt i retning af at øge værdien af det funktionelle. Når overgang langs en kant fra det aktuelle toppunkt til et andet toppunkt med en højere funktionel værdi er umulig, anses det for, at den optimale værdi af c er fundet.

Essensen af simplex-metoden er, at hvis antallet af ukendte flere tal ligninger altså dette system usikker med utallige løsninger. For at løse systemet er alle ukendte vilkårligt opdelt i grundlæggende og gratis. Antallet af grundvariable bestemmes af antallet af lineært uafhængige ligninger. De resterende ukendte er gratis. De tildeles vilkårlige værdier og erstattes derefter i systemet. Ethvert sæt af frie ukendte kan gives et uendeligt antal vilkårlige værdier, hvilket vil give et uendeligt antal løsninger. Hvis alle frie ukendte er sat til nul, vil løsningen bestå af værdierne for de grundlæggende ukendte. Denne løsning kaldes basic.

I teorien om lineær programmering er der en sætning, der siger, at man blandt systemets grundlæggende løsninger kan finde de optimale, og i nogle tilfælde, flere optimale løsninger, som alle vil give et ekstremum af den objektive funktion. Så hvis du finder en grundplan og derefter forbedrer den, får du en optimal løsning. Simplexmetoden er bygget på dette princip.

Sekvensen af beregninger ved hjælp af simplex-metoden kan opdeles i to hovedfaser:

1. at finde det indledende toppunkt for sættet af mulige løsninger;

2. sekventiel overgang fra toppunkt til toppunkt, hvilket fører til optimering af værdien af objektivfunktionen.

I nogle tilfælde er den oprindelige løsning indlysende, eller dens definition kræver ikke komplekse beregninger - for eksempel når alle begrænsningerne er repræsenteret af uligheder på formen "mindre end eller lig med" (så er nulvektoren absolut en acceptabel løsning, selvom det højst sandsynligt er langt fra optimalt). I sådanne problemer kan den første fase af simplex-metoden helt udelades. Simplexmetoden er derfor opdelt i enkelt fase Og

to-faset.

3.2. Simplex metode algoritme

Styrket problemformulering

Overvej følgende lineære programmeringsproblem:

Lad os nu stille dette problem i en tilsvarende styrket form. Det er nødvendigt at maksimere Z, hvor:

Her er x variablerne fra den oprindelige lineære funktional; x s – nye variable, der supplerer de gamle på en sådan måde, at ulighed bliver til lighed; c - koefficienter for den oprindelige lineære funktional; Z er den variabel, der skal maksimeres. Halvrummene og ved krydset danner et polyeder, der repræsenterer sættet af mulige løsninger. Forskellen mellem antallet af variable og ligninger giver antallet af frihedsgrader. Kort sagt, hvis vi betragter toppunktet af et polyeder, er dette antallet af kanter, som vi kan fortsætte med at bevæge os langs.

Så kan vi tildele værdien 0 til dette antal variabler og kalde

3. Modificeret simpleksmetode

Denne type simpleksmetode er baseret på træk ved lineær algebra, der gør det muligt at arbejde med en del af begrænsningsmatricen, når man løser et problem. Nogle gange kaldes metoden den inverse matrix-metode.

Under driften af algoritmen inverteres begrænsningsmatrixen spontant i dele svarende til de aktuelle basisvektorer. Denne evne gør maskinimplementeringen af beregninger meget attraktiv på grund af besparelsen af hukommelse til mellemvariable og en betydelig reduktion i beregningstiden. Denne evne er god til situationer, hvor antallet af variable n væsentligt overstiger antallet af begrænsninger m.

Generelt afspejler metoden de traditionelle træk ved den generelle tilgang til løsning af lineære programmeringsproblemer, herunder kanonisering af problembetingelser, beregning af simpleksforskelle, verifikation af optimalitetsbetingelser, beslutningstagning på basiskorrektion og Jordan-Gauss-eliminering. Funktioner inkluderer tilstedeværelsen af to tabeller - de vigtigste og de ekstra tabeller, rækkefølgen, hvori de er udfyldt, og en vis specificitet af beregningsformlerne.

At kende den optimale plan for dette problem, baseret på relationerne får vi den optimale plan oprindelige problem.

Processen med at finde en løsning på et ikke-lineært programmeringsproblem omfatter således følgende trin:

1. Det oprindelige problem er reduceret til et lineært programmeringsproblem.

2. Find en løsning lineært problem

Brug relationer, bestem den optimale plan for det oprindelige problem og find maksimal værdi objektiv funktion af et ikke-lineært problem.

Første fase: Modtagelse af opgaver til kurser

1. Alle numeriske data vedrørende den foreslåede produktion og økonomiske processer er baseret på en sekscifret kode:

Under hvert tal er bogstaverne a, b, c, d, e, f skrevet i følgende form:

fra sidste linje tabeller over individuelle opgaver, finder vi de kolonner, der svarer til bogstaverne a, b, c, d, e, f. Derefter de numeriske data, der er nødvendige for at udføre dette kursus arbejde, vil der være data placeret i a - den kolonne i linje 9, b - den kolonne i linje 5, c - den kolonne i linje 5, d - den kolonne i linje 8, e - den kolonne i linje 7, og f - den kolonne i linje 2.

Ifølge tabellen over indledende opgaver for enhver variant af opgaver i kolonne a, modtager udføreren varianten af den opgave, der udføres. I mit tilfælde svarer tallet 9 til mulighed 9.

En bestemt plante producerer tre typer produkter og forbruger to typer ressourcer. Produktionsfunktionen for hver type produkt i virksomheden er beskrevet ved lighederne:

hvor C i og er konstante værdier, i = 1, 2, 3;

X 1 – arbejdsressourcer i dagsværk;

X 2 – monetære og materielle ressourcer, i tenge;

Y i er det resulterende produkt

X 1 = a 1 x 1 + b 1 x 2 + c 1 x 3

X 2 = a 2 x 1 + b 2 x 2 + c 2 x 3

Find alle ikke-negative basisløsninger og bestem den optimale plan F = y 1 + y 2 + y 3.

Det er kendt, at til produktion af j – den type produkt, bruges en ij enheder af i – den ressource. Disse omkostninger er angivet i tabel 3.9.1. – 3.9.10

Efterfølgende numeriske data tages kun fra kildedatatabellen for den valgte opgavemulighed, dvs. fra tabel nr. 3.9.11.

2. Ifølge tabelkolonne nr. 3.9.11 for linje 8 vil den indledende tabel over omkostninger for ressourceenheder være tabel nr. 3.9.4, dvs. følgende tabel:

Produktressourcer
jeg	8	4	6
II	160	240	200

3. Ved hjælp af kolonne c – på linje 3 finder vi med 1 =6, α 1 =0,6

4. Ved hjælp af kolonne d – på linje 5 bestemmer vi med 2 =5, α 2 =0,5

5. Ved hjælp af kolonne e – linje 4 fastslår vi, at c 3 =8, α 3 =0,4.

6. Og endelig, ved at bruge kolonne f - i linje 1 finder vi T persondage = 1000, P tenge = 280000

Til produktion er der arbejdsressourcer T mandage og pengeressourcer P tenge.

Det er nødvendigt at finde den optimale produktionsplan, hvor outputproduktet vil være størst.

Anden fase er kompilering matematisk model opgaver

1. Baseret på de indledende data opnået i første fase og beskrivelsen af den givne produktionsproces, er følgende tabel udarbejdet:

Produktressourcer
jeg	8	4	6	1000
II	160	240	200	280000

Lad X 1 betegne ressourcer af den første type.

Lad X 2 betegne ressourcer af type II.

2. Med hensyn til problemets betingelser bestemmer vi alt mulige begrænsninger, der kombinerer dem i et system af restriktioner.

8Х 1 + 4Х 2 + 6Х 3 ≤ 1000

240Х 1 + 200Х 2 + 160Х 3 ≤ 280000

Således fik vi et ikke-lineært programmeringsproblem. Sådanne problemer kaldes ikke-lineære programmeringsproblemer.

Ikke-lineære programmeringsproblemer løses ved at reducere dem til lineære programmeringsproblemer.

For at løse det lineære programmeringsproblem anvendes simpleksmetoden.

Den tredje fase er valget af en metode til at løse det opnåede matematisk problem

1. For at løse lineære programmeringsproblemer ved brug af simpleksmetoden reduceres problemet til kanonisk form:

8X 1 + 4X 2 + 6X 3 + X 4 = 1000

240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000

Metoder udvikles til at finde ekstreme værdier af den objektive funktion blandt sættet af dets mulige værdier bestemt af begrænsninger. Tilstedeværelsen af restriktioner gør opgaver matematisk programmering fundamentalt forskellig fra klassiske problemer matematisk analyse for at finde ekstreme værdier af en funktion. Metoder til matematisk analyse til at søge efter yderpunktet af en funktion i problemer...

At finde Kuhn-Tucker-punktet giver en optimal løsning på det ikke-lineære programmeringsproblem. Sætning 2 kan også bruges til at bevise optimaliteten denne beslutning ulineære programmeringsproblemer. For at illustrere, overvej eksemplet igen: Minimer under begrænsninger Ved hjælp af sætning 2 beviser vi, at løsningen er optimal. Vi har så...

Stråler, der udgår fra et punkt, kaldes en polyhedral konveks kegle med et toppunkt i et givet punkt. 1.4 Matematisk grundlæggende løsning af et lineært programmeringsproblem grafisk 1.4.1 Matematisk apparat For at forstå alt yderligere, er det nyttigt at kende og forestille sig den geometriske fortolkning af lineære programmeringsproblemer, som kan gives for tilfældene n = 2 og n = ...

Hvis vi sætter de nuværende grundvariable i en sådan simplex-tabel lig med Ai,0, og de frie lig med nul, så opnås en optimal løsning. Praksis med at bruge simplex-metoden har vist, at antallet af iterationer, der kræves for at løse et lineært programmeringsproblem, normalt varierer fra 2m til 3m, selvom for nogle specialkonstruerede opgaver bliver beregninger i henhold til simplex-metodens regler til direkte...

Lad os forklare beregningerne a i, j¢ ved hjælp af "rektangelreglen". Det er nødvendigt at tage aktiveringselementet ak, s og mentalt forbinde det med koefficienten, hvis nye værdi du ønsker at finde. Denne linje skal betragtes som hoveddiagonalen; et rektangel er konstrueret på den, hvis sider er rækker og kolonner. Du skal tegne en sekundær diagonal i rektanglet, så vil værdien af den nye koefficient være lig med dens oprindelige værdi, hvorfra produktet af elementerne placeret på den sekundære diagonal divideret med det løsende element trækkes fra. Lad os forklare disse handlinger i diagrammet (fig. 1.9). Inden du udfylder simplekstabellen, skal de originale ligninger præsenteres i skemaet (1.21).

en k,j

a i,j

Lad os se på essensen af transformationerne af simplex-metoden ved hjælp af eksempel 1.4. Lad os huske begrænsningsulighederne og objektiv funktion fra dette eksempel og finde max objektiv funktion ved hjælp af ovenstående metode:

F = 908X 1 + 676X 2 ® max.

X 1 + X 2 14,

X 2 10,

10 X 1 + 8 X 2 120,

7X 1 + 5 X 2 70,

4X 1 + 2X 2 28,

Lad os omdanne det til kanonisk form ved at introducere yderligere variabler Xj 0, og gør uligheder til ligheder. Det skal bemærkes, at hvis der er et "" tegn i uligheden, så skriver de med en fri variabel "-", ellers - "+":

X 1 + X 2 = 14 - X 3,

X 2 = 10 - X 4,

10 X 1 + 8 X 2 = 120 - X 5,

7X 1 + 5 X 2 = 70 - X 6,

4X 1 + 2X 2 = 28 - X 7.

For at begynde simpleksmetoden skal du først finde en referenceløsning fra sættet af grundlæggende løsninger af det resulterende ligningssystem. Med dette i betragtning er der tre faser i løsning af problemer ved hjælp af simplex-metoden:

At finde den indledende grundlæggende løsning og danne den indledende simplex-tabel;

Definition mulig løsning;

Bestemmelse af den optimale løsning.

1. etape

Vi finder den indledende grundlæggende løsning af systemerne ved at antage frie variable X 1 Og x 2 .

Derefter X 3 = 14 - X 1 - X 2,

X 4 = 10 - X 2,

X 5 =120 - 10X 1 - 8X 2,

X 6 = 70 - 10X 1 - 5X 2,

X 7 = 28 - 4X 1 - 2X 2,

F = 908X 1 + 676X 2 = 0.

Lad os transformere disse ligninger til normalt udseende:

X 3 = 14 - (X 1 + X 2),

X 4 = 10 - (0X 1 + X 2),

X5 =120 - (10X 1 + 8X 2),

X 6 = 70 - (7X 1 + 5X 2),

X 7 = 10 - (4X 1 + 2X 2),

F = 0 + 908 X 1 + 676 X 2.

Vi skriver det resulterende ligningssystem i form af den oprindelige simplex-tabel (tabel 1.9). I tabel 1.9 der er ingen negative gratis medlemmer. Som følge heraf har vi opnået en støtte (tilladelig) løsning, da en tilladelig løsning er enhver ikke-negativ løsning (hvortil > 0 ), men det er ikke optimalt.

Selvfølgelig, hvis for alle de ukendte i den objektive funktion F Hvis koefficienterne var positive, ville den maksimale værdi nås F. Det følger heraf tegn på optimalitet af en tilladt løsning: V F- rækken i simplekstabellen må ikke have negative koefficienter.

Tabel 1.9

Grundlæggende variabler X b	Gratis medlem	Gratis variabler
X 1	X 2
X 3
X 4
X 5
X 6
X 7
F		- 908	- 676

2. etape

Lad os huske på, at simplex-metodens hovedoperation i det væsentlige er, at en eller anden grundlæggende variabel erstattes af en fri variabel . I dette tilfælde udføres udskiftningsoperationen på følgende betingelser:

Objektiv funktionsværdi F den nye (antagelige) referenceløsning skal være større end den tidligere;

Den nye løsning af systemet skal også være reference (tilladelig).

I vores eksempel er den første betingelse opfyldt, hvis aktiveringselementet er positivt og er valgt i kolonnen med negativ koefficient F-linjer.

Den anden betingelse er opfyldt, hvis opløsningselementet findes som det mindste positive forhold mellem elementerne i kolonnen med frie elementer og de tilsvarende elementer i opløsningskolonnen.

I henhold til reglen nævnt ovenfor, for at finde en acceptabel løsning, byttes de grundlæggende og frie variable. For at gøre dette skal du finde et løsningselement (det er indrammet i tabel 1.9). I vores tilfælde skulle den tilladelige kolonne være som x 1 , så X 2. At dividere frie variable med deres tilsvarende værdier X 1 Og x 2 (bortset fra linjen F), finder vi den mindste positive værdi. Det er vigtigt at bemærke, at for kolonnen x 1 :

Det er vigtigt at bemærke, at for kolonnen X 2:

Det mindste forhold 28/4 definerer den løsende række og den løsende kolonne, og skæringspunktet mellem den løsende kolonne og den løsende række er det løsende element en ks= 4. I tabel. 1.9 markerer vi tilladelseskolonnen og tilladelsesrækken med pile (®). at have bestemt en ks, opbyg følgende tabel, hvor variablerne, der er inkluderet i rækken og kolonnen i det løsende element, er byttet om ᴛ.ᴇ. konvertere grundlæggende variabler til frie, og frie til grundlæggende.

I vores eksempel bytter vi variablerne x 7 Og x 1 , noteret i tabel. 1,9 pile. Koefficienter for den nye tabel. 1,10 findes ud fra koefficienterne i den gamle tabel. 1.9 ved at bruge de udtryk, der er angivet i tabel. 1.8 og "rektangelreglen". I tabel 1.10 igen har vi ikke en optimal løsning.

Tabel 1.10

Grundlæggende variabler X b

Gratis medlem B

Gratis variabler

X 7

X 2

X 3

- 1/4

1/2

X 4

X 5

-5/2

X 6

-7/4

3/2

X 1

1/4

1/2

-222

I henhold til reglerne beskrevet ovenfor i tabellen. 1.10 finder vi det løsende element 1 og bygger en ny tabel. 1.11 ved at erstatte grundlaget ( X 4 Og X 2). Vi understreger især, at for at finde det opløsende element skal vi vælge den mindste positive værdi, ᴛ.ᴇ. Vi betragter ikke negative forhold mellem frie vilkår og koefficienterne i opløsningskolonnen.

3. etape

Lad os kontrollere, om den fundne løsning er optimal, og for vores eksempel - maksimal. For at gøre dette vil vi analysere den objektive funktion F: F = 8576 + 227 X 7 + 222 X 4.

Objektivfunktionen indeholder ikke negative koefficienter og har højeste værdi I den sidste tabel fik vi den optimale løsning:

X3 = 2; X2 = 10; X5 = 20; X6 = 6; X1 = 2; X7 = X4 = 0;

F max = 8576.

Bemærk venligst, at resultaterne af løsningen af simplex-metoden og den grafiske metode er de samme.

I overensstemmelse med den betragtede sekvens skal simplex-metodealgoritmen have følgende blokke:

1. At finde den indledende grundlæggende (reference) løsning og danne den indledende tabel.

2. Find det løsende element en ks(at finde det negative frie udtryk - b i < 0 и минимального отношенияb i / a ij; Hvis der ikke er negative koefficienter i rækken af det negative frie led, så er problemet uløseligt).

3. Genberegning nyt bord i henhold til formlerne i tabellen. 1.8.

4. Tjek for tilstedeværelsen af en negativ fri term. Hvis det findes, så fortsæt til trin 2. Fraværet af et negativt frit udtryk betyder, at der er opnået en reference (tilladelig) løsning.

5. I lighed med trin 2 - 4 genberegnes tabellen, når der søges efter den optimale løsning.

Løsning af LP-problemet ved hjælp af simpleksmetoden i matrixform

Nødvendig for at minimere ,

under restriktioner

ved " x³ 0.

Lad os introducere vektorer:

C= (C 1 , ... , C n) - vektor for estimater,

x= (X 1 , ... , X n) - vektor af variable,

b= (B 1 , ... , B m) - vektor af restriktioner

og matrix

EN=

størrelse (mn) - matrix af begrænsningskoefficienter.

Så vil LP-problemet have følgende fortolkning:

minimere F=CX

under forhold AX = b, X 0.

Dette problem kan skrives i matrixform:

Lad os introducere notationen:

A * = - her er matrixen EN* størrelse (m+1)(n+1).

Ifølge ovenstående metode findes det opløsende element en ks.

Det næste trin i simplex-metoden er den Gaussiske eliminationsprocedure, som giver dig mulighed for at lave alle koefficienterne i s- m kolonne, undtagen en ks, nul, en ks- lig med en.

Det er vigtigt at bemærke, at for simpleksmetoden i matrixform svarer iteration af simplexmetoden til at gange matrixligningen til venstre med følgende kvadratisk matrix:

(1.23)

, Hvor k 0; s 0.

Hvis alle søjler i matrixen EN opdele i grundlæggende B og ikke-grundlæggende N, så kan LP-problemet skrives som følger:

Hvor Cb Og C N- tilsvarende vektorkomponenter C, X b, X N- grundlæggende og ikke-grundlæggende variable.

For at vælge initiale basisvariabler x b du skal gange ligningen til venstre med matrixen:

Hvor R=CbB-1.

Som et resultat får vi

Hvor jeg- identitetsmatrix.

Det følger heraf, at relative estimater for ikke-grundlæggende variabler

cj = cj - CbB-1 aj = cj - Raj.

Grundlaget vil være tilladt, hvis de frie vilkår for basisvariablerne er ikke-negative, ᴛ.ᴇ. B -1 b ³ 0.

Hvis c j³ 0 for , så er grundlaget optimal løsning opgaver. Vektoren kaldes den aktuelle prisvektor. Hver række ganges med en vektor R og trækkes fra omkostningskoefficientlinjen for at eliminere omkostningskoefficienterne for de underliggende variable.

Hvis LP-problemet ikke er givet i kanonisk form, ᴛ.ᴇ.

minimere F=CX

under forhold AX b , X 0,

derefter, ved at introducere svage variabler, kan de skrives i form

Rækkelimineringsmetoden for en matrix svarer til at gange denne matrix fra venstre med B-1, Hvor B- submatrix basis EN, Derefter

ᴛ.ᴇ. matrix opnået i stedet for identitetsmatrixen jeg, vil være den omvendte matrix for det nuværende grundlag. De relative scorer placeret over identitetsmatrixen vil være

da er enhedsvektorer.

Fordi F= CbB-1 b = Rb, den aktuelle værdi af den objektive funktion er lig med produktet af vektoren af nuværende priser på matricen EN til den oprindelige vektor b.

Eksempel.
Opslået på ref.rf
F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5® min

under restriktioner

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10 ,

3X 2 + 3X 4 + 6X 5 = 9,

Til dette eksempel matrix EN* vil se ud

Lade X 1 Og X 2- grundlæggende variabler.

Matrix B ligner

Derefter den omvendte matrix B-1 har følgende form

Lad os minde dig om det , hvor den adjoint matrix består af algebraiske komplementer af elementer b ik determinant for matricen B.

Determinanten er lig med:

= .

Derfor matrixen B ikke speciel.

Algebraiske tilføjelser elementer af determinanten har følgende betydninger:

b 11 = 3, b 12 = 0, b 12 = 0, b 22 = 2; de der . .

Gang med , finder vi omvendt matrix:

Vektoren af nuværende priser vil være

R = CbB-1 = = .

Lad os minde dig om det Cb- basis vektorkomponenter C:

Så = .

For at vælge startgrundlaget skal du bruge en matrix EN* venstre gange med matrix

Det opløsende element er i en firkant.

En iteration af simplexmetoden svarer til den resulterende tabel ganget til venstre med følgende matrix:

Denne matrix er hentet fra matrix (1.23)

Her aks = 2;

a11 = 1; a 12 = - a 0s / a ks = - 12/2 = - 6;

a13 = 0; a21 = 0; a22 = 1/a ks = 1/2; a23 = 0;

a31 = 0; a32 = -a ms/a ks = -1/2; a 33 = 1.

Så har vi

(1.24)

Det opløsende element placeres i en firkant.

Den næste iteration af simpleksmetoden svarer til venstre multiplikation med matrixen

Derfor, Fmin =11; X 4=7/3; X 5=1/3; X 1 = X 2 = X 3=0.

Modificeret simpleksmetode (MSM) forskellig fra den sædvanlige simpleksmetode (CM) fordi i CM Alle elementer i simplekstabeller genberegnes ved hver iteration, og når den næste tabel er opnået, gemmes alle tidligere tabeller, inklusive den originale, ikke. I MSM den oprindelige tabel gemmes, og ved hver iteration bestemmes følgende: en række af relative estimater C indtastet i grundlaget, og den aktuelle værdi af vektoren på højre side af begrænsningerne. For at bestemme alle tabelelementer efter j- iterationen CM, er det nok at kende matrixen B-1, svarende til denne tabel, den oprindelige matrix og indekser for de aktuelle grundvariable. Derefter den aktuelle vektor R = CbB-1(indeksene for de aktuelle grundvariable bestemmer, hvilke elementer af vektoren af estimater fra kildetabellen der er inkluderet i vektoren C b); =B-1 b, Hvor b er taget fra den oprindelige tabel, og enhver kolonne i den nye tabel = B-1-en j , Hvor -en j - kolonne i kildetabellen.

Lad nu kildetabellen gives B-1, svarende til tabellen jeg iterationen. For at få matrixen B-1, tilsvarende (i+1)- I den iteration skal du definere en ikke-basiskolonne jeg den tabel, der skal indtastes i grundlaget. Fra CM det følger heraf, at det skal indgå i grundlaget if Cj<0. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, крайне важно вычислить C j Til jeg tabeller, vælg blandt dem<0, а затем вычислить

-en S = B-1 og = B-1 b (= C j - Ra j ).

Efter at have fundet det opløsende element og bruge elementerne i vektorerne og , finder vi matrixen B-1 for følgende tabel.

Eksempel. Brug af den modificerede simpleksmetode til at minimere

F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® min

med restriktioner:

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,

3X 2 + 3X 4 + 6X 5 = 9,

At vælge som grundvariable X 1 Og X 2, fik vi følgende opgave: F = 43 - 9/2X 3 - 12X 4 - 12X 5