Simplex metode løsningsalgoritme c. Enkel metode til at løse problemer
. Simplex metode algoritme
Eksempel 5.1. Løs følgende problem lineær programmering simplex metode:
Løsning:
jeg iteration:
x3, x4, x5, x6 x1,x2. Lad os udtrykke de grundlæggende variabler i form af frie:
Lad os reducere den objektive funktion til følgende form:
Baseret på det opnåede problem vil vi danne den indledende simplex-tabel:
Tabel 5.3
Originalt simplex bord
Evaluerende relationer |
||||
Ifølge definitionen af den grundlæggende løsning er de frie variable lig med nul, og værdierne af de grundlæggende variable er lig med de tilsvarende værdier af de frie tal, dvs.
Trin 3: kontrol af kompatibiliteten af PAP-begrænsningssystemet.
Ved denne iteration (i tabel 5.3) er tegnet på inkonsistens af begrænsningssystemet (tegn 1) ikke identificeret (dvs. der er ingen linje med et negativt frit tal (bortset fra linjen i den objektive funktion), hvor der ikke ville være mindst ét negativt element (dvs. negativ koefficient for en fri variabel)).
Ved denne iteration (i tabel 5.3) blev tegnet på ubegrænsethed af objektivfunktionen (tegn 2) ikke identificeret (dvs. der er ingen kolonne med et negativt element i rækken af objektivfunktionen (bortset fra kolonnen med frie tal) ) hvori der ikke ville være mindst ét positivt element).
Da den fundne basisopløsning ikke indeholder negative komponenter, er den tilladt.
Trin 6: optimalitetstjek.
Den fundne basisløsning er ikke optimal, da der ifølge optimalitetskriteriet (tegn 4) ikke bør være negative elementer i linjen af den objektive funktion (den frie nummer på denne linje tages ikke i betragtning, når dette kriterium overvejes). Derfor går vi videre til trin 8 i henhold til simplex-metodens algoritme.
Da den fundne grundlæggende løsning er tilladt, vil vi søge efter den løsende kolonne i henhold til følgende skema: vi bestemmer kolonnerne med negative elementer i rækken af objektivfunktionen (undtagen kolonnen med frie tal). Ifølge tabel 5.3 er der to sådanne kolonner: kolonne " x1"og kolonne" x2" Fra sådanne kolonner vælges den, der indeholder det mindste element i rækken af målfunktionen. Hun vil være den tilladelige. kolonne" x2" indeholder det mindste element (–3) sammenlignet med kolonnen " x1
For at bestemme den løsende linje finder vi de positive estimerede forhold mellem frie tal og elementerne i den løsende kolonne; den linje, der svarer til det mindste positive evalueringsforhold, accepteres som løst.
Tabel 5.4
Originalt simplex bord
I tabel 5.4 svarer den mindste positive evaluerende sammenhæng til linjen " x5", derfor vil det være tilladeligt.
Elementet placeret ved skæringspunktet mellem aktiveringskolonnen og aktiveringsrækken accepteres som aktiverende. I vores eksempel er dette det element, der er placeret i skæringspunktet mellem linjen " x5"og kolonner" x2».
Det løsende element viser en grundlæggende og en fri variabel, der skal byttes i simplex-tabellen for at flytte til den nye "forbedrede". grundlæggende løsning. I I dette tilfælde disse er variable x5 Og x2, i den nye simplex-tabel (tabel 5.5) bytter vi dem.
9.1. Transformation af det løsende element.
Opløsningselementet i tabel 5.4 er konverteret som følger:
Vi indtaster det resulterende resultat i en lignende celle i tabel 5.5.
9.2. Konvertering af opløsningsstreng.
Vi deler elementerne i den løsende række i tabel 5.4 med opløsningselementet i denne simplekstabel, resultaterne passer ind i lignende celler i den nye simplekstabel (tabel 5.5). Transformationer af opløsningsstrengelementer er angivet i tabel 5.5.
9.3. Konvertering af opløsningskolonnen.
Vi dividerer elementerne i opløsningskolonnen i tabel 5.4 med opløsningselementet i denne simplekstabel, og resultatet tages med det modsatte fortegn. De opnåede resultater passer ind i lignende celler i den nye simplex-tabel (tabel 5.5). Transformationer af elementerne i opløsningskolonnen er angivet i tabel 5.5.
9.4. Transformation af de resterende elementer i simplex-tabellen.
Transformationen af de resterende elementer i simplex-tabellen (dvs. elementer, der ikke er placeret i den løsende række og opløsningskolonnen) udføres i henhold til reglen om "rektangel".
Overvej for eksempel at transformere et element placeret i skæringspunktet mellem linjen " x3" og kolonner "", vil vi betinget betegne det " x3" I tabel 5.4 tegner vi mentalt et rektangel, hvoraf det ene toppunkt er placeret i cellen, hvis værdi vi transformerer (dvs. i cellen " x3"), og den anden (diagonal toppunkt) er i en celle med et opløsningselement. De to andre hjørner (af den anden diagonal) er entydigt bestemt. Derefter den transformerede værdi af cellen " x3" vil være lig med den foregående værdi af denne celle minus brøken, i hvis nævner er det opløselige element (fra tabel 5.4), og i tælleren er produktet af to andre ubrugte hjørner, dvs.
« x3»: .
Værdierne af andre celler konverteres på samme måde:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Som et resultat af disse transformationer modtog vi en ny simplex bord(Tabel 5.5).
II iteration:
Trin 1: udarbejdelse af en simplex-tabel.
Tabel 5.5
Simplex bordII iterationer
Anslået forhold |
||||
| ||||
|
|
Trin 2: Bestemmelse af den basiske opløsning.
Som et resultat af simplex-transformationerne blev der opnået en ny basisløsning (tabel 5.5):
Som du kan se, er værdien af objektivfunktionen med denne basisløsning = 15, hvilket er større end med den tidligere basisløsning.
Inkonsekvensen af begrænsningssystemet i overensstemmelse med funktion 1 i tabel 5.5 er ikke blevet identificeret.
Trin 4: kontrol af afgrænsningen af den objektive funktion.
Ubegrænsetheden af den objektive funktion i henhold til kriterium 2 i tabel 5.5 afsløres ikke.
Trin 5: kontrol af, om den fundne basisløsning er tilladt.
Den fundne basisløsning i overensstemmelse med kriterium 4 er ikke optimal, da linjen i simplex-tabellens objektivfunktion (tabel 5.5) indeholder et negativt element: –2 (den frie nummer på denne linje tages ikke i betragtning, når dette tages i betragtning. egenskab). Derfor går vi videre til etape 8.
Trin 8: bestemmelse af opløsningselementet.
8.1. Definition af opløsningskolonnen.
Den fundne grundlæggende løsning er acceptabel; vi bestemmer kolonnerne med negative elementer i rækken af objektivfunktionen (undtagen kolonnen med frie tal). Ifølge tabel 5.5 er der kun én sådan kolonne: " x1" Derfor accepterer vi det som tilladt.
8.2. Definition af en aktiveringsstreng.
Ifølge de opnåede værdier af positive evaluerende relationer i tabel 5.6 er minimum forholdet svarende til linjen " x3" Derfor accepterer vi det som tilladt.
Tabel 5.6
Simplex bordII iterationer
Anslået forhold |
||||
3/1=3 – min |
||||
Trin 9: transformation af simplex-tabellen.
Transformationer af simplekstabellen (tabel 5.6) udføres på samme måde som i forrige iteration. Resultaterne af transformationer af elementer i simplekstabellen er angivet i tabel 5.7.
III iteration
Baseret på resultaterne af simplex-transformationer af den tidligere iteration, sammensætter vi en ny simplex-tabel:
Tabel 5.7
Simplex bordIII iterationer
Anslået forhold |
||||
| ||||
|
|
Trin 2: Bestemmelse af den basiske opløsning.
Som et resultat af simplex-transformationerne blev der opnået en ny basisløsning (tabel 5.7):
Trin 3: kontrol af kompatibiliteten af begrænsningssystemet.
Inkonsistensen af begrænsningssystemet i overensstemmelse med funktion 1 i tabel 5.7 er ikke blevet identificeret.
Trin 4: kontrol af afgrænsningen af den objektive funktion.
Ubegrænsetheden af den objektive funktion i henhold til kriterium 2 i tabel 5.7 afsløres ikke.
Trin 5: kontrol af, om den fundne basisløsning er tilladt.
Den fundne basisløsning i overensstemmelse med kriterium 3 er acceptabel, da den ikke indeholder negative komponenter.
Trin 6: kontrol af optimaliteten af den fundne basisløsning.
Den fundne basisløsning i overensstemmelse med kriterium 4 er ikke optimal, da linjen i simplex-tabellens objektivfunktion (tabel 5.7) indeholder et negativt element: –3 (den frie nummer på denne linje tages ikke i betragtning, når dette tages i betragtning. egenskab). Derfor går vi videre til etape 8.
Trin 8: bestemmelse af opløsningselementet.
8.1. Definition af opløsningskolonnen.
Den fundne grundlæggende løsning er acceptabel; vi bestemmer kolonnerne med negative elementer i rækken af objektivfunktionen (undtagen kolonnen med frie tal). Ifølge tabel 5.7 er der kun én sådan kolonne: " x5" Derfor accepterer vi det som tilladt.
8.2. Definition af en aktiveringsstreng.
Ifølge de opnåede værdier af positive evaluerende relationer i tabel 5.8 er minimum forholdet svarende til linjen " x4" Derfor accepterer vi det som tilladt.
Tabel 5.8
Simplex bordIII iterationer
Anslået forhold |
||||
5/5=1 – min |
||||
Trin 9: transformation af simplex-tabellen.
Transformationer af simplekstabellen (tabel 5.8) udføres på samme måde som i forrige iteration. Resultaterne af transformationer af elementer i simplekstabellen er angivet i tabel 5.9.
IV iteration
Trin 1: konstruktion af et nyt simplex bord.
Baseret på resultaterne af simplex-transformationer af den tidligere iteration, sammensætter vi en ny simplex-tabel:
Tabel 5.9
Simplex bordIV iterationer
Anslået forhold |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Trin 2: Bestemmelse af den basiske opløsning.
Som et resultat af simplex-transformationerne blev der opnået en ny basisløsning; ifølge tabel 5.9 er løsningen som følger:
Trin 3: kontrol af kompatibiliteten af begrænsningssystemet.
Inkonsekvensen af begrænsningssystemet i overensstemmelse med funktion 1 i tabel 5.9 er ikke blevet identificeret.
Trin 4: kontrol af afgrænsningen af den objektive funktion.
Ubegrænsetheden af den objektive funktion i henhold til kriterium 2 i tabel 5.9 afsløres ikke.
Trin 5: kontrol af, om den fundne basisløsning er tilladt.
Den fundne basisløsning i overensstemmelse med kriterium 3 er acceptabel, da den ikke indeholder negative komponenter.
Trin 6: kontrol af optimaliteten af den fundne basisløsning.
Den fundne basisløsning i overensstemmelse med funktion 4 er optimal, da der ikke er nogen negative elementer i linjen for den objektive funktion af simplex-tabellen (tabel 5.9) (det frie nummer af denne linje tages ikke i betragtning, når denne funktion overvejes) .
Trin 7: kontrol af løsningens alternativhed.
Den fundne løsning er unik, da der ikke er nogen nul-elementer i linjen af objektivfunktionen (tabel 5.9) (det frie nummer på denne linje tages ikke i betragtning, når denne funktion overvejes).
Svar: optimal værdi objektiv funktion af det undersøgte problem =24, som opnås ved.
Eksempel 5.2. Løs ovenstående lineære programmeringsproblem forudsat at objektivfunktionen er minimeret:
Løsning:
jeg iteration:
Trin 1: Dannelse af den indledende simplex-tabel.
Det originale lineære programmeringsproblem er givet i standardform. Lad os bringe det til kanonisk form ved at indføre en ekstra ikke-negativ variabel i hver af ulighedsbegrænsningerne, dvs.
I det resulterende ligningssystem tager vi som tilladte (grundlæggende) variable x3, x4, x5, x6, så vil de frie variable være x1,x2. Lad os udtrykke de grundlæggende variabler i form af frie.
Lad os overveje simpleks metode til løsning af problemer med lineær programmering (LP). Det er baseret på overgangen fra en referenceplan til en anden, hvor værdien af den objektive funktion stiger.
Simplex-metodens algoritme er som følger:
- Vi oversætter det oprindelige problem til kanonisk opfattelse ved at indføre yderligere variabler. For uligheder på formen ≤ indføres yderligere variable med et fortegn (+), men hvis af formen ≥, så med et fortegn (-). Yderligere variable indføres i objektivfunktionen med tilsvarende fortegn med en koefficient lig med 0 , fordi målfunktionen bør ikke ændre dens økonomiske betydning.
- Vektorer skrives ud P i fra variablernes koefficienter og kolonnen med frie led. Denne handling bestemmer antallet af enhedsvektorer. Reglen er, at der skal være lige så mange enhedsvektorer, som der er uligheder i systemet af begrænsninger.
- Herefter indtastes kildedataene i en simplekstabel. Enhedsvektorer indføres i basis, og ved at udelukke dem fra basis, findes den optimale løsning. Koefficienterne for den objektive funktion skrives med det modsatte fortegn.
- Et optimalitetstegn for et LP-problem er, at løsningen er optimal, hvis i f– i rækken er alle koefficienter positive. Regel for at finde den aktiverende kolonne - vist f– en streng og blandt dens negative elementer vælges den mindste. Vektor P i dens indhold bliver eftergivende. Reglen for valg af et opløsningselement - forholdet mellem de positive elementer i den opløsningssøjle og elementerne i vektoren kompileres P 0 og det tal, der giver det mindste forhold, bliver det opløsende element, som simplekstabellen genberegnes i forhold til. Linjen, der indeholder dette element, kaldes aktiveringslinjen. Hvis der ikke er positive elementer i opløsningskolonnen, har problemet ingen løsning. Efter at have bestemt opløsningselementet går de videre til genberegning af en ny simplex-tabel.
- Regler for udfyldning af en ny simplex-tabel. Enhed sættes i stedet for det løsende element, og andre elementer antages at være ens 0 . Opløsningsvektoren tilføjes til basisen, hvorfra den tilsvarende nulvektor er udelukket, og de resterende basisvektorer skrives uden ændringer. Opløsningslinjens elementer divideres med opløsningselementet, og de resterende elementer genberegnes i henhold til rektangelreglen.
- Dette gøres indtil f– alle elementer i strengen bliver ikke positive.
Lad os overveje at løse problemet ved hjælp af algoritmen diskuteret ovenfor.
Givet:
Vi bringer problemet til kanonisk form:
Vi sammensætter vektorerne:
Udfyld simplex-tabellen:
:
Lad os genberegne det første element i vektoren P 0, for hvilket vi laver et rektangel af tal: og vi får: 
.
Vi udfører lignende beregninger for alle andre elementer i simplekstabellen:
I den modtagne plan f– linjen indeholder et negativt element – (-5/3), vektor P 1. Den indeholder i sin kolonne et enkelt positivt element, som vil være det aktiverende element. Lad os genberegne tabellen vedrørende dette element:
Ingen negative elementer i f– linje betyder fundet optimal plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Lineær programmering, M: Nauka, 1998,
- Ventzel E.S. Operations Research, M: Soviet Radio, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Matematisk programmering, M: Higher School, 1986.
Tilpasset lineær programmeringsløsning
Du kan bestille alle opgaver inden for denne disciplin på vores hjemmeside. Du kan vedhæfte filer og angive deadlines kl
Enkel metode er en iterativ proces med rettet løsning af et ligningssystem trin for trin, som begynder med en referenceløsning og på jagt efter bedste mulighed bevæger sig langs hjørnepunkterne af det mulige løsningsområde, hvilket forbedrer værdien af målfunktionen, indtil målfunktionen når den optimale værdi.Formålet med tjenesten. Tjenesten er beregnet til online løsninger Lineære programmeringsproblemer (LPP) ved hjælp af simplex-metoden i følgende notationsformer:
- i form af en simplex tabel (Jordan transformationsmetode); grundlæggende registreringsformular;
- modificeret simpleksmetode; i kolonneform; i linjeform.
Instruktioner. Vælg antallet af variable og antallet af rækker (antal begrænsninger). Den resulterende opløsning opbevares i Word-fil og Excel.
I dette tilfælde skal du ikke tage højde for begrænsninger som x i ≥ 0. Hvis der ikke er begrænsninger i opgaven for nogle x i, så skal ZLP'en konverteres til KZLP'en, eller bruge denne service. Ved løsning bestemmes forbruget automatisk M-metode(simpel metode med kunstigt grundlag) og to-trins simpleks metode.Følgende bruges også med denne lommeregner:
Grafisk metode til løsning af ZLP
Løsning af transportproblemet
Løsning af et matrixspil
Brug af tjenesten i online-tilstand du kan bestemme prisen på et matrixspil (nedre og øvre grænser), tjekke for tilstedeværelsen af et sadelpunkt, finde en løsning på en blandet strategi ved hjælp af følgende metoder: minimax, simplex metode, grafisk (geometrisk) metode, Browns metode .
Ekstremum af en funktion af to variable
Dynamiske programmeringsproblemer
Fordel 5 homogene partier af varer mellem tre markeder for at opnå maksimal indkomst fra deres salg. Indtægter fra salg på hvert marked G(X) afhænger af antallet af solgte partier af produkt X og er præsenteret i tabellen.
| Produktvolumen X (i partier) | Indkomst G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Simplex metode algoritme omfatter følgende trin:
- Udarbejdelse af den første grundplan. Overgang til kanonisk form lineære programmeringsproblemer ved at indføre ikke-negative yderligere balancevariable.
- Tjek planen for optimalitet. Hvis der er mindst én indekslinjekoefficient mindre end nul, så er planen ikke optimal og skal forbedres.
- Bestemmelse af den førende kolonne og række. Fra indekslinjens negative koefficienter vælges den største i absolut værdi. Derefter opdeles elementerne i den frie medlemskolonne i simplex-tabellen i elementer med samme fortegn i den forreste kolonne.
- Opbygning af en ny referenceplan. Overgangen til en ny plan sker som følge af genberegning af simplekstabellen ved hjælp af Jordan-Gauss metoden.
Hvis det er nødvendigt at finde yderpunktet af den objektive funktion, så taler vi om at søge minimumsværdi(F(x) → min , se eksempel på løsning af en funktionsminimering) og maksimal værdi((F(x) → max , se eksempel på løsning af en funktionsmaksimering)
En ekstrem løsning opnås ved grænsen af regionen tilladte løsninger ved et af hjørnerne af polygonens hjørnepunkter eller på et segment mellem to tilstødende hjørnepunkter.
Grundlæggende sætning for lineær programmering. Hvis ZLP-objektivfunktionen når en ekstrem værdi på et tidspunkt i området med mulige løsninger, så tager den denne værdi ved hjørnepunktet. Hvis ZLP-objektivets funktion når en ekstrem værdi ved mere end ét hjørnepunkt, tager den den samme værdi ved enhver af de konvekse lineære kombinationer af disse punkter.
Essensen af simplex-metoden. Bevægelse til det optimale punkt udføres ved at flytte fra det ene hjørnepunkt til det nabostillede, hvilket bringer tættere og hurtigere til X opt. En sådan ordning til optælling af punkter, kaldet simpleksmetoden, foreslået af R. Danzig.
Hjørnepunkter er karakteriseret ved m grundvariable, så overgangen fra et hjørnepunkt til et nabopunkt kan opnås ved kun at ændre én grundvariabel i basis til en variabel fra en ikke-basis.
Implementeringen af simplex-metoden, på grund af forskellige funktioner og formuleringer af LP-problemer, har forskellige modifikationer.
Konstruktionen af simplex-tabeller fortsætter, indtil den er opnået optimal løsning. Hvordan kan du bruge en simplekstabel til at bestemme, at løsningen på et lineært programmeringsproblem er optimal?
Hvis den sidste linje (værdierne af den objektive funktion) ikke indeholder negative elementer, vil den derfor finde den optimale plan.
Bemærkning 1. Hvis en af grundvariablerne er lig nul, så er det ekstreme punkt, der svarer til en sådan basisløsning, degenereret. Degeneration opstår, når der er uklarhed i valget af ledelinje. Du bemærker måske slet ikke problemets degeneration, hvis du vælger en anden linje som vejledning. I tilfælde af tvetydighed bør rækken med det laveste indeks vælges for at undgå looping.
Bemærkning 2. Lad på et eller andet yderpunkt alle simpleksforskelle være ikke-negative D k ³ 0 (k = 1..n+m), dvs. opnås en optimal løsning, og der eksisterer sådan en A k - en ikke-basisvektor, for hvilken D k = 0. Så opnås maksimum ved at i det mindste på to punkter, dvs. der er et alternativt optimum. Hvis vi introducerer denne variabel x k i grundlaget, ændres værdien af objektivfunktionen ikke.
Bemærkning 3. Løsning dobbelt problem er i den sidste simplex bord. De sidste m komponenter af vektoren af simplex-forskelle (i kolonnerne med balancevariabler) er den optimale løsning på det dobbelte problem. Værdierne af de objektive funktioner af de direkte og dobbelte problemer på optimale punkter falder sammen.
Bemærkning 4. Ved løsning af minimeringsproblemet indføres vektoren med den største positive simpleksforskel i basis. Dernæst anvendes den samme algoritme som for maksimeringsproblemet.
Hvis betingelsen "Det er nødvendigt, at type III-råvarer er fuldstændig forbrugt", er den tilsvarende betingelse en lighed.
Denne metode er en metode til målrettet opregning af referenceløsninger til et lineært programmeringsproblem. Han giver mulighed for endeligt nummer skridt til enten at finde en optimal løsning eller fastslå, at der ikke er nogen optimal løsning.
Hovedindholdet af simplex-metoden er som følger:- Angiv en metode til at finde den optimale referenceløsning
- Angiv metoden til overgang fra en referenceløsning til en anden, hvor værdien af den objektive funktion vil være tættere på den optimale, dvs. angive en måde at forbedre referenceløsningen på
- Sæt kriterier, der giver dig mulighed for omgående at stoppe med at søge efter supportløsninger ved den optimale løsning eller drage en konklusion om fraværet af en optimal løsning.
Algoritme af simplex-metoden til løsning af lineære programmeringsproblemer
For at løse et problem ved hjælp af simplex-metoden skal du gøre følgende:- Bring problemet til kanonisk form
- Find den indledende supportløsning med et "enhedsgrundlag" (hvis der ikke er nogen supportløsning, så har problemet ikke en løsning på grund af inkompatibiliteten af systemet af begrænsninger)
- Beregn estimater af vektornedbrydninger baseret på referenceopløsningen og udfyld simplexmetodens tabel
- Hvis kriteriet for den optimale løsnings unikke karakter er opfyldt, slutter løsningen af problemet
- Hvis betingelsen for eksistensen af et sæt af optimale løsninger er opfyldt, så findes alle optimale løsninger ved simpel opregning
Et eksempel på løsning af et problem ved hjælp af simpleksmetoden
Eksempel 26.1Løs problemet ved hjælp af simpleksmetoden:
Løsning:
Vi bringer problemet til kanonisk form.
For at gøre dette introducerer vi en ekstra variabel x 6 med koefficient +1 til venstre side af den første ulighedsbegrænsning. Variablen x 6 er inkluderet i objektivfunktionen med en koefficient på nul (dvs. den er ikke inkluderet).
Vi får:
Vi finder den indledende supportløsning. For at gøre dette sætter vi lighedstegn mellem frie (uløste) variabler til nul x1 = x2 = x3 = 0.
Vi får referenceløsning X1 = (0,0,0,24,30,6) med enhedsbasis B1 = (A4, A5, A6).
Vi beregner estimater af vektornedbrydning betingelser på basis af referenceopløsningen ifølge formlen:
Δ k = C b X k - c k
- C b = (c 1, c 2, ..., c m) - vektor af koefficienter for den objektive funktion for de grundlæggende variable
- X k = (x 1k, x 2k, ..., x mk) - ekspansionsvektor af den tilsvarende vektor A k i henhold til referenceopløsningens basis
- C k er koefficienten for objektivfunktionen for variablen x k.
Estimaterne af de vektorer, der indgår i grundlaget, er altid lig nul. Referenceløsningen, udvidelseskoefficienter og estimater af udvidelser af tilstandsvektorer baseret på referenceløsningen er skrevet ind simplex bord:
Øverst i tabellen, for at lette beregningen af estimater, er koefficienterne for den objektive funktion skrevet. I den første kolonne "B" er de vektorer, der indgår i referenceløsningens basis, skrevet. Rækkefølgen, hvori disse vektorer er skrevet, svarer til antallet af tilladte ukendte i begrænsningsligningerne. I den anden kolonne i tabellen "C b" er koefficienterne for den objektive funktion for de grundlæggende variable skrevet i samme rækkefølge. På korrekte placering Koefficienterne for den objektive funktion i kolonnen "C b" af estimatet af enhedsvektorerne inkluderet i grundlaget er altid lig med nul.
I sidste linje tabeller med estimater af Δ k i kolonnen "A 0" er værdierne af objektivfunktionen på referenceløsningen Z(X 1) skrevet.
Den initiale støtteløsning er ikke optimal, da estimaterne Δ 1 = -2, Δ 3 = -9 for vektorerne A 1 og A 3 i det maksimale problem er negative.
Ifølge sætningen om forbedring af støtteløsningen, hvis mindst én vektor i et maksimalt problem har et negativt estimat, så kan du finde en ny støtteløsning, hvor værdien af den objektive funktion vil være større.
Lad os bestemme, hvilken af de to vektorer, der vil føre til en større stigning i objektivfunktionen.
Forøgelsen af objektivfunktionen findes ved formlen: .
Vi beregner værdierne af parameteren θ 01 for den første og tredje kolonne ved hjælp af formlen:
Vi får θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (Tabel 26.1).
Vi finder stigningen af den objektive funktion, når vi indfører den første vektor ΔZ 1 = - 6*(- 2) = 12 i basis, og den tredje vektor ΔZ 3 = - 3*(- 9) = 27.
For en hurtigere tilgang til den optimale løsning er det derfor nødvendigt at indføre vektor A3 i basis af referenceopløsningen i stedet for den første vektor af basis A6, da minimum af parameteren θ 03 er opnået i den første række ( l = 1).
Vi udfører Jordan-transformationen med elementet X13 = 2, vi opnår den anden referenceløsning X2 = (0,0,3,21,42,0) med basis B2 = (A3, A4, A5). (Tabel 26.2)
Denne løsning er ikke optimal, da vektor A2 har et negativt estimat Δ2 = - 6. For at forbedre løsningen er det nødvendigt at indføre vektor A2 i referenceopløsningens basis.
Vi bestemmer antallet af vektoren afledt af basis. For at gøre dette beregner vi parameteren θ 02 for den anden kolonne, den er lig med 7 for l = 2. Derfor udleder vi den anden basisvektor A4 fra basis. Vi udfører Jordan-transformationen med elementet x 22 = 3, vi får den tredje referenceløsning X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabel 26.3).
Denne løsning er den eneste optimale, da estimaterne for alle vektorer, der ikke er inkluderet i grundlaget, er positive
Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.
Svar: max Z(X) = 201 ved X = (0,7,10,0,63).
Lineær programmeringsmetode i økonomisk analyse
Lineær programmeringsmetode gør det muligt at retfærdiggøre den mest optimale økonomiske løsning under forhold med strenge restriktioner relateret til de ressourcer, der bruges i produktionen (anlægsaktiver, materialer, arbejdskraft). Anvendelse af denne metode i økonomisk analyse giver dig mulighed for at løse problemer primært relateret til planlægning af organisationens aktiviteter. Denne metode hjælper med at bestemme de optimale outputniveauer, såvel som anvisningerne for de fleste effektiv brug produktionsressourcer til rådighed for organisationen.
Ved hjælp af denne metode løses de såkaldte ekstreme problemer, som består i at finde ekstreme værdier, det vil sige maksimum og minimum af funktioner af variable mængder.
Denne periode er baseret på systemets løsning lineære ligninger i tilfælde, hvor de analyserede økonomiske fænomener er forbundet af en lineær, strengt funktionel afhængighed. Den lineære programmeringsmetode bruges til at analysere variable i nærvær af visse begrænsende faktorer.
En meget almindelig løsning er den såkaldte transport problem ved hjælp af den lineære programmeringsmetode. Indholdet af denne opgave er at minimere omkostningerne i forbindelse med driften Køretøj under eksisterende restriktioner med hensyn til antallet af køretøjer, deres bæreevne, varigheden af deres drift, og hvis der er behov for vedligeholdelse maksimal mængde kunder.
Udover, denne metode bruges i vid udstrækning til at løse planlægningsproblemer. Denne opgave består af en sådan fordeling af driftstiden for personalet i en given organisation, som ville være mest acceptabel både for medlemmerne af dette personale og for organisationens kunder.
Denne opgave er at maksimere antallet af klienter, der betjenes under betingelser med begrænsninger af antallet af ledige medarbejdere, såvel som arbejdstidsfonden.
Den lineære programmeringsmetode er således ret almindelig i placerings- og brugsanalyse. forskellige typer ressourcer, såvel som i processen med at planlægge og forudsige organisationers aktiviteter.
Endnu matematisk programmering kan også anvendes på de økonomiske fænomener, hvis forhold ikke er lineært. Til dette formål kan ikke-lineære, dynamiske og konvekse programmeringsmetoder anvendes.
Ikke-lineær programmering er afhængig af den ikke-lineære karakter af den objektive funktion eller begrænsninger eller begge dele. Formerne for den objektive funktion og ulighedsbegrænsninger i disse forhold kan være forskellige.
Ikke-lineær programmering bruges i økonomisk analyse, især ved etablering af forholdet mellem indikatorer, der udtrykker effektiviteten af en organisations aktiviteter og omfanget af denne aktivitet, strukturen af produktionsomkostninger, markedsforhold osv.
Dynamisk programmering er baseret på at konstruere et beslutningstræ. Hvert niveau i dette træ tjener som et trin til at bestemme konsekvenserne af en tidligere beslutning og for at eliminere ineffektive muligheder for denne beslutning. Dermed, dynamisk programmering har en multi-trin, multi-stage karakter. Denne type programmering bruges i økonomisk analyse til at finde optimale muligheder udvikling af organisationen både nu og i fremtiden.
Konveks programmering er en form for ikke-lineær programmering. Denne type programmering udtrykker den ikke-lineære karakter af forholdet mellem resultaterne af en organisations aktiviteter og dens omkostninger. Konveks (alias konkav) programmeringsanalyser konveks objektive funktioner og konvekse begrænsningssystemer (punkter acceptable værdier). Konveks programmering bruges i analysen af økonomiske aktiviteter med det formål at minimere omkostningerne, og konkav programmering med det formål at maksimere indkomsten under eksisterende restriktioner på virkningen af faktorer, der påvirker de analyserede indikatorer på den modsatte måde. Følgelig minimeres konvekse objektivfunktioner med de typer programmering, der er under overvejelse, og konkave objektivfunktioner maksimeres.
Her er en manuel (ikke applet) løsning af to problemer ved hjælp af simplex-metoden (svarende til applet-løsningen) med detaljerede forklaringer for at forstå algoritmen til at løse problemer ved hjælp af simplex-metoden. Det første problem indeholder kun ulighedstegn "≤" (problem med et indledende grundlag), det andet kan indeholde tegn "≥", "≤" eller "=" (problem med kunstigt grundlag), løses de forskelligt.
Enkel metode, der løser et problem med en indledende basis
1)Enkel metode for et problem med en indledende basis (alle tegn på ulighedsbegrænsninger " ≤ ").
Lad os skrive problemet ind kanonisk form, dvs. vi omskriver ulighedsbegrænsningerne i form af ligheder, tilføjer balance variabler:
Dette system er et system med en basis (basis s 1, s 2, s 3, hver af dem er kun inkluderet i én af systemets ligning med en koefficient på 1), x 1 og x 2 er frie variable. Opgaver, der skal løses ved brug af simpleksmetoden, skal have følgende to egenskaber: - begrænsningssystemet skal være et ligningssystem med en basis; -frie led for alle ligninger i systemet skal være ikke-negative.
Det resulterende system er et system med et grundlag, og dets gratis vilkår er ikke-negative, så vi kan ansøge simpleks metode. Lad os lave den første simplex-tabel (Iteration 0) at løse problemet på simpleks metode, dvs. en tabel med koefficienter for objektivfunktionen og et ligningssystem for de tilsvarende variable. Her betyder "BP" kolonnen med grundlæggende variable, "Løsning" betyder kolonnen med højre side af systemligningerne. Løsningen er ikke optimal, pga der er negative koefficienter i z-rækken.
simplex metode iteration 0
|
Holdning |
|||||||
For at forbedre løsningen, lad os gå videre til næste iteration simpleks metode, får vi følgende simplekstabel. For at gøre dette skal du vælge aktivér kolonne, dvs. en variabel, der vil indgå i grundlaget ved næste iteration af simpleksmetoden. Det vælges af den største absolutte negative koefficient i z-rækken (i det maksimale problem) - i den indledende iteration af simplex-metoden er dette kolonne x 2 (koefficient -6).
Vælg derefter aktivere streng, dvs. en variabel, der vil forlade grundlaget ved næste iteration af simpleksmetoden. Det vælges af det mindste forhold mellem "Beslutning"-kolonnen og de tilsvarende positive elementer i opløsningskolonnen (kolonne "Ratio") - i den indledende iteration er dette række s 3 (koefficient 20).
Tilladende element er i skæringspunktet mellem den løsende kolonne og den løsende række, er dens celle fremhævet i farve, den er lig med 1. Derfor vil variablen x 2 ved næste iteration af simpleksmetoden erstatte s 1 i basis. Bemærk, at der ikke søges efter relationen i z-strengen; en bindestreg "-" er placeret der. Hvis der er identiske minimale relationer, vælges nogen af dem. Hvis alle koefficienter i opløsningskolonnen er mindre end eller lig med 0, så er løsningen på problemet uendelig.
Lad os udfylde følgende tabel "Iteration 1". Vi får det fra "Iteration 0"-tabellen. Målet med yderligere transformationer er at omdanne x2 opløsningskolonnen til en enhedskolonne (med en i stedet for opløsningselementet og nuller i stedet for de resterende elementer).
1) Beregn række x 2 i "Iteration 1"-tabellen. Først deler vi alle medlemmerne af den løsende række s 3 i "Iteration 0"-tabellen med opløsningselementet (det er lig med 1 i dette tilfælde) i denne tabel, vi får række x 2 i "Iteration 1"-tabellen . Fordi det løsende element i dette tilfælde er lig med 1, så vil række s 3 i "Iteration 0"-tabellen falde sammen med række x 2 i "Iteration 1"-tabellen. Række x 2 i Iteration 1-tabellen fik vi 0 1 0 0 1 20, de resterende rækker i Iteration 1-tabellen vil blive hentet fra denne række og rækkerne i Iteration 0-tabellen som følger:
2) Beregning af z-rækken i "Iteration 1"-tabellen. I stedet for -6 i den første række (z-rækken) i x2-kolonnen i Iteration 0-tabellen, skal der være et 0 i den første række af Iteration 1-tabellen. For at gøre dette skal du gange alle elementerne i rækken x 2 i tabellen "Iteration 1" 0 1 0 0 1 20 med 6, vi får 0 6 0 0 6 120 og tilføje denne række med den første række (z - række) af tabellen "Iteration 0" -4 -6 0 0 0 0, får vi -4 0 0 0 6 120. Et nul 0 vises i x 2 kolonnen, målet er nået. Elementer i opløsningskolonnen x 2 er fremhævet med rødt.
3) Beregning af række s 1 i "Iteration 1" tabellen. I stedet for 1 i s 1 række i "Iteration 0"-tabellen skal der være et 0 i "Iteration 1"-tabellen. For at gøre dette skal du gange alle elementerne i række x 2 i tabellen "Iteration 1" 0 1 0 0 1 20 med -1, få 0 -1 0 0 -1 -20 og tilføje denne række med s 1 - række af tabel "Iteration 0" 2 1 1 0 0 64, får vi rækken 2 0 1 0 -1 44. I kolonnen x 2 får vi den nødvendige 0.
4) Beregn række s 2 i "Iteration 1"-tabellen. På plads 3 i s 2 række i tabellen "Iteration 0" skal der være 0 i tabellen "Iteration 1". For at gøre dette skal du gange alle elementerne i række x 2 i tabellen "Iteration 1" 0 1 0 0 1 20 med -3, vi får 0 -3 0 0 -3 -60 og tilføje denne række med s 1 - række af tabellen "Iteration 0" 1 3 0 1 0 72, får vi rækken 1 0 0 1 -3 12. I kolonnen x 2 fås det påkrævede 0. Kolonnen x 2 i tabellen "Iteration 1" er blevet til en enhed, den indeholder en 1 og resten 0.
Rækkerne i tabellen "Iteration 1" opnås i henhold til følgende regel:
Ny række = Gammel række – (kolonnekoefficient for gammel rækkeopløsning)*(Ny opløsningsrække).
For en z-streng har vi for eksempel:
Gammel z-streng (-4 -6 0 0 0 0) -(-6)*Ny opløsende streng -(0 -6 0 0 -6 -120) =Ny z-streng (-4 0 0 0 6 120).
For de følgende tabeller sker genberegningen af tabelelementer på lignende måde, så vi udelader den.
simplex metode iteration 1
|
Holdning |
|||||||
Løsning af kolonne x 1, løsning af række s 2, s 2 forlader basis, x 1 går ind i basis. På nøjagtig samme måde får vi de resterende simplex-tabeller, indtil vi får en tabel med alle positive koefficienter i z-rækken. Dette er et tegn på et optimalt bord.
simplex metode iteration 2
|
Holdning |
|||||||
Løsning af kolonne s 3, løsning af række s 1, s 1 forlader basis, s 3 går ind i basis.
simplex metode iteration 3
|
Holdning |
|||||||
I z-rækken er alle koefficienter ikke-negative, derfor opnås den optimale løsning x 1 = 24, x 2 = 16, z max = 192.