Kursusarbejde: Enkel metode i præsentationsform. Modificeret simpleksmetode
MODIFICERET SIMPLEX METODE Simplexmetoden er ikke den mest effektive
computer procedure, da den beregner og
gemmer information, der ikke er nødvendig for den aktuelle
iteration og må slet ikke bruges til
træffe beslutninger under efterfølgende iterationer. Til
koefficienter for ikke-hovedvariable i ligningen
(0), koefficienter for de indførte hovedvariable
i andre ligninger og højre side af ligningerne ved
Hver iteration bruger kun den relevante
Information. Derfor er der brug for en procedure, der
kan opnå disse oplysninger effektivt uden
beregninger og lagring af alle andre koefficienter
(dette er den modificerede simpleksmetode).
nødvendigt for dette øjeblik og vigtige data
formidler i en mere kompakt form.
Den bruger matrixoperationer, så
det er nødvendigt at beskrive problemet ved hjælp af matricer.
STORE bogstaver, fremhævet med fed skrift
repræsenterer matricer, store bogstaver,
dem med fed skrift repræsenterer
vektorer.
Kursiv er skalære mængder, fremhævet nul
(0) angiver nulvektoren (dens elementer er ens
nul, både rækker og kolonner), nul (0)
repræsenterer det normale tal 0. Ved hjælp af
matricer standard form for lineær model
programmering har formen: Maksimer Z = c x,
ifølge
A x ≤ b og x ≥ 0,
hvor c er en rækkevektor
x, b og 0 kolonnevektorer A - matrix
For forstørret form, kolonnevektor
dummy variabler:
Begrænsninger:
I = (m × m identitetsmatrix)
0 = (n + m elementer af nulvektoren) At finde en grundlæggende gennemførlig løsning
Den generelle tilgang til simplex-metoden er at opnå
rækkefølge af forbedring af OA-løsninger op til
indtil den optimale er fundet
løsning. En af nøglefunktionerne
modificeret simplex metode - hvordan det
finder en ny OD-løsning efter at have defineret den
main (grundlæggende) og ikke-grundlæggende (ikke-grundlæggende)
variabler. I betragtning af disse variabler vil den resulterende
hovedløsning – løsning af m-ligninger
I hvilke n ikke-grundlæggende variable fra n + m
elementer
sættes lig nul. Eliminering af disse n variabler ved at sætte dem til nul,
får vi et ligningssystem m med m variable
(hovedvariable (grundlæggende)):
hvor er vektoren af grundlæggende variable:
opnået ved at udelukke ikke-grundlæggende (ikke-grundlæggende)
variabler: Og basismatrixen
Resultatet opnået ved at ekskludere kolonnerne svarende til
koefficienter for ikke-grundlæggende variable fra .
(Desuden er xB-elementer og B-kolonner i forskellige
okay). Simplex-metoden introducerer kun grundlæggende
variabler sådan, at B er ikke-degenereret, så
omvendt matrix B-1 vil altid eksistere.
For at løse B x B = b multipliceres begge sider med B-1:
B-1 B x B = B-1 b. cB er en vektor, hvis elementer er koefficienter
objektive funktioner (inklusive nuller for dummy
variable) for de tilsvarende xB-elementer.
Den objektive funktion for denne grundlæggende løsning er: Eksempel:
- Gentagelse 0
så
så
10.
- Gentagelse 1så
så
11.
- Gentagelse 2så
så
12. Matrixform for det aktuelle ligningssæt
Matrixform for et sæt ligninger,vises i simplex-tabellen for enhver iteration
den originale simplex-metode. Til kildesystem
ligninger, er matrixformen:
Algebraiske operationer udført ved hjælp af simpleksmetoden (multiplicer ligningen med en konstant og add
produkt af en ligning med en anden) er udtrykt i
matrixform, efter at have ganget begge dele
det oprindelige ligningssystem ind i det tilsvarende
matricer
13.
14.
Denne matrix vil have de samme elementer som identitetsmatrixenmatrix, bortset fra at hvert produkt
for en bestemt algebraisk operation vil det tage
den nødvendige plads til at udføre denne operation,
ved hjælp af matrixmultiplikation. Også efter episoden
algebraiske operationer over flere iterationer,
vi kan stadig konkludere, at denne matrix
skal være for hele serien ved at bruge det, vi kender til
højre side nyt system ligninger. Efter evt
iterationer, xB = B-1b og Z = cB B-1b, så de rigtige sider
det nye ligningssystem tog formen
15.
Da vi udfører den samme seriealgebraiske operationer med begge sider
originale sæt, for at gange højre og
i venstre side bruger vi den samme matrix.
Derfor,
Ønsket matrixform af ligningssystemet
efter enhver iteration:
16.
Eksempel: matrixform opnået efter iteration 2til glasfabriksproblemet ved brug af B-1 og cB:
17.
Ved at bruge mængderne xB = B-1 b og Z = cB B-1 b:18.
Kun B-1 skal modtages til beregningalle numre i simplekstabellen fra originalen
opgaveparametre (A, b, cB). Ethvert af disse tal
kan fås individuelt som
Som regel udføres kun vektormultiplikation
(én række pr. kolonne) i stedet for fuld
matrix multiplikation. Nødvendige numre til
at udføre iterationer af simplex-metoden kan være
modtage efter behov uden udgifter
unødvendige beregninger for at få alle tallene.
19. Kort oversigt over den modificerede simpleksmetode
1. Initialisering: Som i den oprindelige simpleksmetode.2. Iteration: Trin 1 Bestem den indtastede basis (hoved)
variabler: Som i den originale simplex-metode.
Trin 2 Bestem de udgående basisvariabler: Som i originalen
simplex-metoden, med undtagelse af kun at tælle dem, der er nødvendige for
af disse tal [koefficienter for de indførte grundvariable i
hver ligning undtagen lign. (0), og derefter for hver strengt
positiv koefficient højre del denne ligning].
Trin 3 Bestem en ny OD-løsning: Få B-1 og indstil xB=B-1b.
3. Optimalitetsanalyse: Som i den oprindelige simplex metode, for
bortset fra kun at tælle de tal, der er nødvendige for denne analyse,
dvs. koefficienter for ikke-grundlæggende (ikke-grundlæggende) variable i
Ligning (0).
Ved trin 3 i iterationen kan B-1 opnås hver gang ved brug
standard computerprogram til vending (inversion)
matricer. Da B (dengang B-1) ændrer sig lidt fra én iteration til
en anden er det mere effektivt at få en ny B-1 (betegnet B-1 ny) fra
B-1 i den forrige iteration (B-1 gammel). (For den originale OA-løsning).
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 objektiv funktion og i variabler, der viser 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 – Originalt simpleksbord
| 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+ | q |
| P 1 P 2 P 4 | d 1 - d 2 - d 3 - d 4 - | 7 | -1 | -1 | -1 | -1 | 30/7 30/6 - | ||||||
| Z j – С j | P 4 P 3 P 2 P 1 | -1 | -1 | -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+ | q |
| 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/7 2/7 6/7 | -1 | -1 | -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 | -1 | -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.
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. I dette tilfælde bruges proceduren for den modificerede simplex-metode for at løse hjælpeproblemet. 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) udskrives den optimale plan for problemet 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ænsethed af den objektive 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 Nr(β ( 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. Et eksempel på løsning af en ZLP ved hjælp af en modificeret simplex-metode. 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.
Der er mange metoder til at løse lineære programmeringsproblemer. Lad os overveje en af dem, den forbedrede (modificerede) simplex-metode
Lad os først fortælle dig, hvad simplex-metoden er. Ordet SIMPLEX betyder i sin almindelige betydning simpel, ikke-sammensat i modsætning til KOMPLEKS.
Denne metode fik flere forskellige former (modifikationer) og blev udviklet i 1947 af G. Danzig.
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 substitueres ind 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, men 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.
En af modifikationerne af simplex-metoden er den forbedrede simplex-metode. I litteraturen findes denne metode også under navnet inverse matrix-metoden eller den modificerede simplex-metode.
Når man løser lineære programmeringsproblemer, hvor n (antallet af variable) er væsentligt større end m (antallet af begrænsninger), kræver den forbedrede simplex-metode betydeligt færre beregningsoperationer og computerhukommelse sammenlignet med andre.
Den forbedrede simpleksmetode implementerer samme grundidé som den konventionelle simpleksmetode, men her ved hver iteration genberegnes ikke hele matricen A -1, det inverse af begrænsningsmatricen A, men kun den del, der relaterer sig til det aktuelle grundlag A. x.
Lad os overveje trin for trin trinene til at løse et lineært programmeringsproblem ved hjælp af den forbedrede simplex-metode:
- 1. I begyndelsen af den første cyklus kender vi den inverse matrix (identitetsmatrix), den grundlæggende løsning x b = b.
- 2. For hver ikke-grundlæggende variabel danner vi den karakteristiske forskel j ved hjælp af ligningen:
j = c j -- = c j -- P j , (2)
hvor er de dobbelte variable, som kan findes som følger:
hvor c x er vektoren af koefficienter for den objektive funktion for de grundlæggende variable.
3. Forudsat brugt standard regel ved at vælge inputkolonnen finder vi:
- 4. Hvis s 0, stopper proceduren. Den nuværende basisløsning er optimal.
- 5. Hvis s 0, beregn den transformerede kolonne:
= (, ...,) . (2.4)
Hvis alle er 0, stopper proceduren: det optimale er ubegrænset.
7. Ellers finder vi variablen udledt af grundlaget:
8. Vi bygger en forstørret matrix:
og transformer det med det ledende element. De første m kolonner giver matrixen invers af det nye grundlag.
9. Transformer den grundlæggende løsning:
x b i x b i -- * , i r, (2,7)
og gå videre til fase 2.
Denne mulighed kaldes også den modificerede simplex-metode, fordi den reducerer mængden af beregning ved hvert trin. Tanken er, at ved hvert trin kan den kanoniske form af problemet for det aktuelle grundlag opnås uafhængigt af andre sådanne former direkte fra den originale post standard opgave LP.
For at gøre dette skal du bruge:
- 1. Oprethold den oprindelige registrering af opgaven gennem hele metodens drift, det er den pris, du skal betale for større ydeevne;
- 2. Brug de såkaldte simplex - multiplikatorer p - koefficienter til direkte overgang fra den oprindelige registrering af problemet til dens nuværende kanoniske basisform;
- 3. Brug den omvendte basis BO№ - en matrix med størrelsen m x m, som giver dig mulighed for at beregne den forreste kolonne aґs ved hvert trin og opdatere simplex - faktorerne s.
Den forbedrede simplex-metode har betydelige fordele i forhold til standardformularen. Det gælder krav til nøjagtighed, hastighed og hukommelse. De fleste af disse fordele er bestemt af det faktum, at, som regel, matricer af store lineære problemer(det vil sige med n>m>100) er svagt udfyldt og indeholder en lille procentdel af ikke-nul elementer.
En tæthed på 5 % eller mindre er almindelig. En forbedret form af simplex-metoden er bedre i stand til at drage fordel af de fordele, der følger af dette faktum. I denne form beregnes de karakteristiske forskelle og den førende vektor direkte ud fra de originale data. Da den oprindelige matrix er dårligt udfyldt, og multiplikation kun bør udføres, når begge faktorer er ikke-nul, reduceres beregningstiden betydeligt.
Derudover betyder det kun at bruge de originale data, at muligheden for at akkumulere afrundingsfejl reduceres. Tværtimod standard simplex tabeller, selvom de oprindeligt er svagt udfyldt, bliver de hurtigt fyldt med ikke-nul elementer under den iterative proces. Således øges beregningstiden, og da hver tabel er beregnet ud fra den foregående, kan ophobningen af fejl begynde at spille en mere alvorlig rolle.
Federal Agency for Education
Stat uddannelsesinstitution videregående faglig uddannelse
Perm State Technical University
Lysvensky filial
Økonomisk Institut
Kursusarbejde
i disciplinen "Systemanalyse og driftsforskning"
om emnet: "Simpel metode i præsentationsform"
Udført af en elev fra gruppe VIVT-06-1:
Startseva N.S.
Tjekket af læreren:
Mukhametyanov I.T.
Lysva 2010
Introduktion. 3
Matematisk programmering. 5
Grafisk metode. 6
Tabular simplex metode. 6
Metode kunstigt grundlag. 7
Modificeret simpleksmetode. 7
Dual simplex - metode. 7
Generelt billede af det lineære programmeringsproblem. 9
Løsning af et lineært programmeringsproblem ved hjælp af simpleksmetoden. elleve
Beregningsprocedurer af simplex-metoden. elleve
Sætning 1: 13
Sætning 2: 14
Sætning 3: 15
Sætning 4: 15
Sætning 5: 15
Overgang til det nye referenceplan. 15
Dobbelt opgave. 17
Sætning 1 (første dualitetssætning) 18
Sætning 2 (anden dualitetssætning) 18
Konklusion. 20
Den optimale løsning på det lineære programmeringsproblem er blandt referenceløsningerne. Ideen med simplex-metoden er, at referenceløsninger efter en bestemt regel sorteres fra, indtil den optimale er fundet blandt dem. Ved at sortere i referenceløsningerne sorterer vi i det væsentlige forskellige grundvariable fra, dvs. , på næste trin overføres en eller anden variabel blandt de grundlæggende, og i stedet for en variabel fra antallet af frie til antallet af grundlæggende.
7x 1 +5x 2 →maks
x 3 = 19-2x 1 -3x 2 (0;0;19;13;15;18)
x 4 =13-2x 1 -x 2 original referenceplan
x 6 =18-3x 1 F(x 1, x 2)=7*0+5*0=0
x i ≥0, (i=1,…n)
På et intuitivt niveau er det klart, at det vil være naturligt at øge x 1, da koefficienten for det er større end for x 2. Forlader x 2 =0, kan vi øge indtil x 3 , x 4 , x 5 , x 6 forbliver ikke-negative.
x 1 = min (19/2; 13/2; ∞; 18/3) = 6
Det betyder, at når x 1 =6, x 6 =0, det vil sige, går x 1 ind i antallet af grundlæggende, og x 6 går ind i antallet af frie.
x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2
x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2
F(x 2; x 6) =42-7/3 x 6 +5 x 2
Med en given referenceplan (6;0;7;1;15;0) x 2 overføres fra frie til grundlæggende variable:
x2 =min(∞;7/3;1/11;15/3)=1
Udtryk x 2 til x 4
x 2 = 1+2/3 x 6 - x 4
Vi udtrykker de ukendte variable og den objektive funktion i form af frie variable:
x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4
x 5 = 12-2x 6 +3x 4 -
F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4
x 6 er positiv, derfor kan den øges
x 6 = min (18; ∞; 3; 6) = 1
x 4 =4/3-4/9 x 6 - 1/3x 3
F=47+x 6 -5(4/3-4/9-1/3x 3)
I den objektive funktion er alle koefficienter for variablerne negative, værdien af funktionen kan ikke øges; vi transformerer på samme måde de resterende variable, find referenceplanen, hvorfra vi bestemmer x 1, x 2.
1. Skæringspunktet mellem lukkede sæt, et sæt ikke-trivielle restriktioner.
2. Sættet af løsninger til et system af lineære ikke-strenge uligheder og ligninger er lukket.
αX=(αx 1 , x 2 ,…, αx n)
X+Y=(x 1 +y 1, x 2 +y 2, … x n +y n)
Lineære koordinater X 1 ,X 2 ,…X n kaldes punkt P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k
Sæt P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 for i= 1,…k n åR i =1, 1≤ i ≤k konveks lineær kombination af punkter x 1 ,x 2,…x n. Hvis k=2, så kaldes dette sæt et segment. X 1,X 2 – enderne af segmentet. Et hjørnepunkt i et lukket sæt er et punkt, der ikke er en ikke-triviel lineær kombination af punkter i sættet (hjørnepunkt).
Ikke-trivialitet betyder, at mindst én af λ'erne er forskellig fra 0 eller 1.
 |
Enhver referenceløsning til et lineært programmeringsproblem er et hjørnepunkt i området for mulige løsninger.
Hvis et lineært programmeringsproblem har en unik løsning, ligger det blandt hjørnepunkterne i ODP. Og hvis der er mere end én løsning, så er der blandt løsningerne flere kantede, sådan at sættet af alle løsninger er deres konvekse lineære kombination.
Simplexmetoden består i først at finde en bestemt referenceløsning på problemet (den indledende referenceplan), og derefter målrettet bevæge sig fra en referenceplan til en anden og søge efter den optimale plan. Hvis der er flere af dem, er alle hjørnerne fundet, og sæt af løsninger er repræsenteret som deres lineære kombination.
Flytter til en ny referenceplan
F1=F(x1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 kan bevises, hvor υ k er det minimum betragtet ovenfor, som bestemmes ved at indføre den k-te variabel i basis, og Δ k =åс j x j ( 1) -С k, hvor n ≤ j ≤1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1)) er et estimat af den k-te variabel , så hvis det maksimale problem er løst, så skal værdien ΔF 2 være positiv, Δk skal være negativ. Ved løsning af minimumsproblemer er ΔF 2 negativ, Δ k er positiv. Disse værdier beregnes, og hvis alle værdier blandt ΔF 2 ikke er positive, så er det omvendt, når man løser minimumsproblemer. Hvis der, når der løses for et maksimum, er flere positive blandt ΔF 2, så indtaster vi i grundlaget den vektor, ved hvilken denne værdi når et maksimum, og hvis problemet løses for et minimum, og blandt ΔF 2 er der flere negative enere, så er vektoren med den mindste værdi ΔF 2 inkluderet i basis, det vil sige med den største i absolut værdi. Når disse betingelser er opfyldt, er den størst mulige ændring i værdien af funktionen garanteret.
Løsningen på problemet vil være unik, hvis for eventuelle vektorer x k, der ikke er inkluderet i grundlaget, estimerer Δ k ≠0, hvis mindst én af disse Δ k = 0, så er løsningen ikke unik, for at finde en anden løsning flytter vi til en anden referenceplan, herunder i basis x k, hvor Δ k =0. Søgning gennem alle sådanne støtteløsninger danner dem til en lineær kombination, som vil være løsningen på problemet.
Hvis koefficienterne for variablen x k ≤ 0 for nogen Δ k modsiger optimalitetsbetingelsen, så er systemet af restriktioner ikke begrænset, dvs. optimal plan eksisterer ikke.
Dobbelt problem
Det dobbelte problem (DP) er hjælpeopgave lineær programmering, formuleret ved hjælp af visse regler direkte fra betingelserne for det direkte problem. Interesse for at definere optimal løsning direkte problem ved at løse dets dobbelte problem skyldes, at beregninger ved løsning af et DP kan vise sig at være mindre komplekse end ved løsning af et direkte problem (DP). Kompleksiteten af beregninger hvornår OPP's beslutning afhænger mere af antallet af begrænsninger frem for antallet af variable. For at gå til PD er det nødvendigt, at PD er skrevet i standard kanonisk form. Ved præsentation af PP i standardform inkluderer variablerne x j også redundante og residuale variable.
Det dobbelte problem har:
1. m variable svarende til antallet af begrænsninger for det direkte problem;
2. n begrænsninger svarende til antallet af variable i det direkte problem.
Det dobbelte problem opnås ved symmetrisk strukturel transformation af betingelserne for det direkte problem i henhold til følgende regler:
· Hver begrænsning b i PD svarer til en variabel y i PD;
· Hver variabel x j PD svarer til en begrænsning C j PD;
· Koefficienterne for x j i PD-begrænsningerne bliver koefficienterne for venstre side af den tilsvarende PD-begrænsning;
· Koefficienterne C j for x j i PD'ens målfunktion bliver konstante på højre side af PD-begrænsningen;
· Begrænsningskonstanter b i PD bliver koefficienter for målfunktionen PD.
Overvej følgende to problemer:
F = С 1 x 1 +С 2 x 2 +... +С n x n →max
|
a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m
x j ≥0 j=1,…,n
Z = b 1 x 1 + b 2 x 2 +... + b n x n → min
|
a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2
. . . . . . . . . . . . . . . . . . . . . . .
a 1 n y n + a 2 m y n + ... + a nm y n ≤C n
Heri kursus arbejde grundlaget blev lagt matematiske metoder løsning af lineære programmeringsproblemer. Derfor blev der lagt mere vægt på følgende afsnit:
1. Grundlæggende om matematiske metoder og deres anvendelse;
2. Løsning af problemer ved hjælp af simpleksmetoden.