Sådan bestemmes et opløsningselement i en simplekstabel. Gauss-Jordan metode
Lad os overveje i detaljer, hvordan simplekstabeller genberegnes (ved at bruge eksemplet med en iteration). Lad der være en simplex tabel præsenteret på Fig.1. Problemet med at maksimere den objektive funktion er løst. Opløsningskolonnen svarer til variablen x 2, og den aktiverende streng for variablen x 3(røde tal), ved deres skæringspunkt er der et opløsningselement (en celle med en grå baggrund). Det første, vi skal gøre, er at udskifte. Opløsningslinjen angiver, hvilken variabel der skal udledes af grundlaget (i vores tilfælde x 3), og opløsningskolonnen viser, hvilken variabel der skal inkluderes i grundlaget (i vores tilfælde x 2). På Fig.2 udskiftningen understreges af en blå linje.
Lad os nu genberegne elementerne i opløsningslinjen. For at gøre dette opdeler vi simpelthen hver af dem i et løsende element (i vores eksempel 4 ). Og vi nulstiller alle elementer i opløsningskolonnen, undtagen elementet i opløsningsrækken. (Se Fig.2)
Billede 1
Tabellens resterende celler (bortset fra kolonnen "Ratio") genberegnes vha. den såkaldte rektangel regel, hvis betydning er lettest at forstå med et eksempel. Antag, at vi skal genberegne elementet cirklet af Fig.1 rød omrids. Tegn mentalt en lodret linje fra det og vandret linje indtil skæringspunktet, med den løsende række og den løsende kolonne. Elementer placeret ved kryds er skitseret med blå konturer (se Fig.1). Den nye værdi af det "røde" element vil være lig med den aktuelle værdi af elementet minus produktet af det "blå" element divideret med det opløsende ("grå") element (se Fig.1). Det er: 18 - (64 * -1) / 4 = 34
, er bekendt her" *
" viser multiplikationsoperationen.
Vi skriver den nye værdi til gammelt sted(Se Fig.2 rødt omrids).
Figur 2
Ved at bruge denne regel udfylder vi alle de tomme elementer i tabellen (undtagen kolonnen "Relation"). Se Fig.3. Herefter vil vi definere en ny opløsningskolonne. For at gøre dette, lad os analysere linjen "Q" og da vores opgave er til det maksimale, vil vi finde i det maksimalt positivt element, vil det bestemme opløsningskolonnen. I vores tilfælde er det 3/2 . Alle elementer i opløsningskolonnen vises med rød skrift (se Fig.3). Hvis efter næste iteration i linjen "Q" der vil ikke være nogen positive elementer - det betyder, at den optimale løsning er opnået, iterationer stopper. Hvis vores problem var på et minimum, så ville løsningskolonnen blive bestemt af det mindste negative element, og hvis efter den næste iteration i rækken "Q" der er ingen negative elementer, hvilket betyder, at den optimale løsning er opnået.
Figur 3
Lad os nu udfylde kolonnen "Attitude". For at gøre dette skal du dividere det tilsvarende (stående i samme række) element i kolonnen "Beslutning" med det tilsvarende element i opløsningskolonnen (se Fig.3). Bemærk, Hvad denne operation afholdt kun for positive elementer i den løsende kolonne og række "Q" er ikke involveret i denne operation. Hvis der efter nogle iterationer ikke er positive elementer i opløsningskolonnen, så denne opgave er uløselig på grund af den objektive funktions ubegrænsethed, stopper iterationer.
Efter at have udfyldt kolonnen "Relation", vil vi definere en ny løsningsrække. Det bestemmes af minimumselementet fra kolonnen "Relation". I vores tilfælde er det 32 , vises alle elementer i opløsningsstrengen med rød skrift (se Fig.3). Det er her den næste iteration slutter, ved den næste iteration variablen x 2 vil blive fjernet fra basis (den nye løsningslinje fortæller os dette), vil dens plads blive taget af variablen x 1(den nye opløsningskolonne fortæller os dette), og alle beregninger vil blive gentaget igen.
Læs også:
|
Sætning (om valget af et opløsende element)
Hvis der er negative elementer i flere kolonner i den z-te række, skal den løsende kolonne vælges til at være den kolonne, der har det maksimale produkt af den absolutte værdi af koefficienten i den z-te række og det minimale simpleksforhold denne kolonne.
Bevis:
Lad elementet være det tilladte element. Som et resultat af det modificerede Jordan-elimineringstrin vil det frie led i z-rækken være tallet lig med . Da og , vil parentesen i dette udtryk altid være positiv. Og da værdien af det funktionelle altid er lig med det frie led, repræsenterer denne parentes den tilføjelse til den funktionelle, der opnås som et resultat af det taget skridt.
Jo større stigning funktionaliteten modtager ved hvert trin, jo færre trin (dvs. beregninger) kræves for at opnå det optimale. Størrelsen af denne stigning afhænger af den absolutte værdi af koefficienten og af værdien af det mindste simpleksforhold. Det vil sige, at den løsende kolonne vil være den kolonne, der har maksimum af dette produkt.
Eksempel: lineær programmering:
Lad os finde det maksimale af funktionen
under restriktioner
Løsning: Lad os skabe et Jordan-bord.
Da dens gratis medlemmer er positive, er planen en støttende en. Det er dog ikke optimalt, da z-rækkekoefficienterne er negative. Vi vælger blandt dem den med det største produkt af absolut værdi og det mindste simpleksforhold. Vi anser den tredje kolonne for at være opløsende, da den har den største absolutte værdi 8 og simplex-relationer: henholdsvis ( , derfor vil element 1 i den tredje kolonne være opløsende). Vi tager det modificerede Jordan-elimineringstrin og når frem til følgende tabel.
At dømme efter z-rækkekoefficienterne har den resulterende tabel ikke opnået den optimale løsning. Vi tager den anden kolonne med en negativ koefficient i z-rækken som den løsende kolonne (kun den første kan være den løsende række). Med element 5 fundet, tager vi det næste skridt.
I z-rækken er alle koefficienter positive; designet opnået ved at sidestille de øverste variable til nul og sidevariablene med frie led er optimalt. Vi skriver værdierne af de vigtigste ukendte fra tabellen: Maksimal værdi Vi beregner funktionaliteten i den sidste celle i tabellen:
I sluttabellen er alle determinanter ikke-negative. Dette tyder på, at for ukendte værdier når den funktionelle et maksimum
Det antages normalt, at der ikke er nogen punkter på sættet af problemplaner, hvor nævneren af det objektive fungerer lig med nul. Uden tab af almenhed kan vi antage, at .
I problemet, fraktioneret lineær programmering yderpunktet af den objektive funktion opnås ved toppunktet af opløsningspolyederet. Denne lighed med lineær programmering gør det muligt at løse fraktioneret lineære problemer ved hjælp af Stiefel-metoden.
Beregninger præsenteres i form af Jordan-tabeller. I dette tilfælde tildeles to lavere linjer til den funktionelle: i den første af dem skriver vi tællerens koefficienter, og i den anden - nævneren. Tabel 1 svarer til det oprindelige problem:
| –x 1 | –x 2 | … | –x j | … | –x n | ||
| y 1 | -en 11 | -en 12 | … | -en 1 j | … | -en 1 n | -en 1 |
| … | ……………………………………… | … | |||||
| y i | et i 1 | et i 2 | … | en ij | … | en ind | et i |
| … | ……………………………………… | … | |||||
| y m | en m 1 | en m 2 | … | en mj | … | en mn | en m |
| z 1 | –s 1 | –s 2 | … | –p j | … | –p n | |
| z 2 | –q 1 | –q 2 | … | –q j | … | –qn |
igennem y i forskellene mellem højre og venstre del af begrænsningssystemet er angivet:
y i= et i–et i 1 x 1 – et i 2 x 2 –et i 3 x 3 – … – a i x n ³ 0.
Vi vil kalde frie variabler variablerne placeret i den øverste titelrække i Jordan-tabellen. Giver gratis variabler nul værdier, får vi originalen grundlæggende løsning: . Denne vektor kan ikke være en referenceplan, fordi nævneren for objektivfunktionen på den er lig nul ( z 2 = 0). Derfor blandt de frie medlemmer af systemet med restriktioner -en 1 ,…, en m helt sikkert har negative tal(ellers ville basisløsningen være referenceplanen).
Ved trin med modificerede Jordan-elimineringer, på samme måde som ved løsning af et lineært programmeringsproblem (se), finder vi den oprindelige plan for problemet. Som resultat k trin vi kommer til tabel 2:
| –y 1 | … | –x j | … | –x n | ||
| x 1 | b 11 | … | b 1 j | … | b 1 n | b 1 |
| .… | ……………………………………… | |||||
| y i | b i 1 | … | b ij | … | b i | b i |
| …. | ……………………………………. | |||||
| y m | b m 1 | … | b mj | … | b mn | b m |
| z 1 | f 1 | … | f j | … | fn | F |
| z 2 | g 1 | … | g j | … | g n | G |
I tabel 2 alle gratis medlemmer b i er ikke-negative, hvilket sikrer basisvariablernes ikke-negativitet x 1 ,…, y m. Derudover (på grund af den positive nævner af den objektive funktion z 2 om et sæt referenceplaner). Den oprindelige referenceplan er en vektor med koordinater. Værdien af den objektive funktion på den oprindelige referenceplan er .
Bemærk, at hvis ved et af Jordan-elimineringstrinene nogen af de gratis vilkår b Jeg vil være negativ, og alle andre elementer jeg th rækker vil være ikke-negative, så vil problemet ikke have en løsning på grund af manglen på planer.
Lad os se, hvordan det ændrer sig objektiv funktion når man flytter fra en referenceplan opgaver til en anden. Det viser sig, at tegnet på forskellen mellem de nye og gamle værdier af funktionen falder sammen med fortegnet for determinanten. Hvis. Fordi opløsningen polyhedron indeholder kun endeligt nummer referenceplaner, så vil vi i et begrænset antal trin nå frem til den optimale referenceplan.
Denne proces kan kun hindres af ubegrænsetheden af polyederet af opløsninger. I dette tilfælde kan den objektive funktion have et såkaldt asymptotisk ekstremum (in I dette tilfælde– maksimum). Det asymptotiske maksimum for et fraktioneret lineært programmeringsproblem er den nøjagtige øvre grænse for den objektive funktion på et sæt planer, som ikke opnås på nogen af planerne. I det tilfælde, hvor problemet har et asymptotisk maksimum, er det inden for planområdet altid muligt at finde en plan (ikke en reference), hvor den objektive funktion tager en værdi vilkårligt tæt på det asymptotiske maksimum.
Stiefel-metoden giver dig mulighed for at finde ikke kun det maksimale, men også det asymptotiske maksimum af et fraktioneret lineært programmeringsproblem. Lad os se nærmere på overgangen fra plan til plan og finde ud af det. Valg af det løsende element i j kolonne, skal vi være styret af princippet om minimum simplex-relationen. De der. aktiverende element i j Den -te kolonne skal være i den række, hvor simpleksrelationen er positiv og minimal.
Fordi efter at have fundet den indledende referenceplan, alle højre sider b i bliver ikke-negativ, så det løsende element j Den th kolonne kan være et af dens positive elementer (). Hvis der på hvert trin i søgestadiet for den optimale referenceplan er (mindst et) positivt element i den valgte opløsningskolonne, så har et sådant problem et maksimum (muligvis mere end et).
Men hvis på et af trinene nogle estimat er mindre end nul, og alle elementer j kolonne. Så i denne kolonne, styret af princippet om den minimale simplex-relation, kan det løsende element ikke vælges. Forøgelse af værdierne af den frie variabel x j fra 0 til (se tabel 2), forbliver vi i planområdet hele tiden. Dette skyldes, at en stigning i variablen x j forårsager ikke en ændring i fortegn til minus for nogen af de grundlæggende variable.
Lad os betegne med M den grænse, til hvilken den objektive funktion, monotont stigende, tenderer til:. Dette tal er det asymptotiske maksimum.
| 2 |
En af løsningsmetoderne optimeringsproblemer (normalt forbundet med at finde minimum eller maksimum) lineær programmering kaldes . Enkel metode omfatter en hel gruppe af algoritmer og metoder til løsning af lineære programmeringsproblemer. En af disse metoder, som involverer registrering af kildedata og genberegning af dem i en speciel tabel, kaldes tabulær simplex metode .
Lad os overveje algoritmen for den tabelformede simplex-metode ved at bruge eksemplet på løsningen produktionsopgave, som går ud på at finde produktionsplan at sørge for maksimal profit.
Inputdata for simpleksmetodeproblemet
Virksomheden producerer 4 typer produkter, bearbejder dem på 3 maskiner.
Tidsstandarder (min./styk) for forarbejdning af produkter på maskiner er specificeret af matrix A:
Maskinens driftstidsfond (min.) er angivet i matrix B:
Fortjeneste ved salg af hver enhed af produktet (RUB/styk) er givet af matrix C:
Formål med produktionsopgaven
Udarbejd en produktionsplan, der vil maksimere virksomhedens fortjeneste.
Løsning af problemet ved hjælp af den tabelformede simpleksmetode
(1) Lad os angive med X1, X2, X3, X4 det planlagte antal produkter af hver type. Så den ønskede plan: ( X1, X2, X3, X4)
(2) Lad os nedskrive planens begrænsninger i form af et ligningssystem:
(3) Så er målfortjenesten:
Det vil sige, at fortjenesten ved at opfylde produktionsplanen skal være maksimal.
(4) For at løse det resulterende problem på betinget ekstrem, erstatter vi systemet med uligheder med systemet lineære ligninger ved at indføre yderligere ikke-negative variabler i det ( X5, X6, X7).
(5) Lad os acceptere følgende referenceplan:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Lad os indtaste dataene simplex bord:
I sidste linje indtaster vi objektivfunktionens koefficienter og selve dens værdi med det modsatte fortegn;
(7) Vælg ind sidste linje størst (modulo) et negativt tal.
Lad os beregne b = N / Elementer_af_den_valgte_kolonne
Blandt de beregnede værdier af b vælger vi mindst.
Skæringspunktet mellem den valgte kolonne og række vil give os det løsende element. Vi ændrer grundlaget til en variabel svarende til det opløsende element ( X5 til X1).
- Selve det løsende element bliver til 1.
- For elementer i opløsningslinjen – a ij (*) = a ij / RE ( det vil sige, at vi dividerer hvert element med værdien af det løsende element og får nye data).
- For elementer i opløsningskolonnen nulstilles de blot til nul.
- Vi genberegner de resterende elementer i tabellen ved hjælp af rektangelreglen.
a ij (*) = a ij – (A * B / RE)
Som du kan se, tager vi den aktuelle celle, der genberegnes, og cellen med det løsende element. De danner modsatte hjørner af rektanglet. Derefter multiplicerer vi værdierne fra cellerne i de to andre hjørner af dette rektangel. Dette arbejde ( EN * B) dividere med det opløsende element ( RE). Og træk fra den aktuelle celle, der genberegnes ( en ij) hvad skete der. Vi får en ny værdi - a ij (*).
(9) Tjek den sidste linje igen ( c) på tilstedeværelsen af negative tal. Hvis de ikke er der, er den optimale plan fundet, gå til sidste etape løse problemet. Hvis der er, er planen endnu ikke optimal, og simplekstabellen skal genberegnes igen.
Da vi igen har negative tal i sidste linje, begynder vi en ny iteration af beregninger.
(10) Da der ikke er negative elementer i den sidste linje, betyder det, at vi har fundet den optimale produktionsplan! Nemlig: vi vil producere de produkter, der er flyttet til kolonnen "Basis" - X1 og X2. Vi kender fortjenesten fra produktionen af hver outputenhed ( matrix C). Det er tilbage at gange de fundne produktionsmængder af produkter 1 og 2 med fortjeneste pr. 1 styk, vi får den endelige ( maksimum! ) fortjeneste for en given produktionsplan.
SVAR:
X1 = 32 stk., X2 = 20 stk., X3 = 0 stk., X4 = 0 stk.
P = 48 * 32 + 33 * 20 = 2.196 gnid.
Galyautdinov R.R.
© Kopiering af materiale er kun tilladt, hvis et direkte hyperlink til
På grafisk metode til løsning af LP-problemer valgte vi faktisk fra mængden af toppunkter, der hører til grænsen for mængden af løsninger til systemet af uligheder, et toppunkt, hvor værdien af den objektive funktion nåede et maksimum (minimum). I tilfælde af to variable er denne metode fuldstændig intuitiv og giver dig mulighed for hurtigt at finde en løsning på problemet.
Hvis et problem har tre eller flere variabler, og i reelle økonomiske problemer er dette præcis situationen, er det vanskeligt at visualisere løsningsområdet for systemet af begrænsninger. Sådanne problemer løses vha simpleks metode eller metode konsekvente forbedringer. Ideen med metoden er enkel og er som følger.
Ifølge en bestemt regel findes den oprindelige referenceplan (noget toppunkt af begrænsningsområdet). Den tjekker om planen er optimal. Hvis ja, så er problemet løst. Hvis ikke, så går vi videre til en anden forbedret plan – til en anden top. værdien af den objektive funktion på dette plan (ved dette toppunkt) er åbenbart bedre end i det foregående. Overgangsalgoritmen udføres ved hjælp af et bestemt beregningstrin, som bekvemt er skrevet i form af tabeller kaldet simplex tabeller . Da der er et begrænset antal hjørner, kommer vi i et begrænset antal trin frem til den optimale løsning.
Lad os overveje simpleks metode på konkret eksempel opgaver omkring udarbejdelse af en plan.
Lad os endnu en gang bemærke, at simpleksmetoden er anvendelig til at løse kanoniske problemer LP'er reduceret til en speciel form, dvs. at have et grundlag, positive højresider og en objektiv funktion udtrykt i form af ikke-grundlæggende variable. Hvis opgaven ikke er reduceret til en speciel form, er der behov for yderligere trin, som vi vil tale om senere.
Lad os overveje problemet med en produktionsplan, efter at vi tidligere har konstrueret en model og bragt den til en speciel form.
Opgave.
Til fremstilling af produkter EN Og I Lageret kan højst frigive 80 enheder råvarer. Desuden til fremstilling af produktet EN to enheder forbruges, og produkterne I- en enhed råvarer. Det er nødvendigt at planlægge produktionen, så den største fortjeneste sikres, hvis produkterne EN det er påkrævet at producere ikke mere end 50 stykker og produkter I- ikke mere end 40 stk. Desuden fortjeneste fra salg af ét produkt EN- 5 rubler, og fra I- 3 gnidninger.
Lad os bygge matematisk model, betegner som x 1 mængde produkter A i plan, for x 2 - antal produkter I. så vil begrænsningssystemet se sådan ud:
Lad os reducere problemet til kanonisk form ved at indføre yderligere variabler:
(3.10)
F = -5x 1 - 3x 2 → min.
Denne opgave har speciel type(med basis er højre sider ikke-negative). Det kan løses ved hjælp af simpleksmetoden.
jegscene. Registrering af et problem i en simplekstabel. Der er en en-til-en overensstemmelse mellem systemet af begrænsninger af problemet (3.10) og simplekstabellen. Der er lige så mange rækker i tabellen, som der er ligheder i systemet af begrænsninger, og der er lige så mange kolonner, som der er frie variable. Grundlæggende variabler fylder den første kolonne, frie - øverste linje borde. Bundlinjen kaldes indekslinjen; koefficienterne for variablerne i objektivfunktionen er skrevet i den. I nederste højre hjørne skrives 0 i første omgang, hvis der ikke er et ledigt medlem i funktionen; hvis der er, så skriv det med modsat fortegn. På dette sted (i nederste højre hjørne) vil der være en værdi af objektivfunktionen, som bør stige i absolut værdi, når du flytter fra en tabel til en anden. Så Tabel 3.4 svarer til vores system af restriktioner, og vi kan gå videre til fase II af løsningen.
Tabel 3.4
|
grundlæggende |
gratis |
||
IIscene. Kontrol af referenceplanen for optimalitet.
Denne tabel 3.4 svarer til følgende referenceplan:
(x 1 , x 2 , x 3 , x 4 , x 5) = (0, 0, 50, 40, 80).
Gratis variabler x 1 , x 2 er lig med 0; x 1 = 0, x 2 = 0. Og de grundlæggende variable x 3 , x 4 , x 5 tage værdier x 3 = 50, x 4 = 40, x 5 = 80 - fra kolonnen frie vilkår. Objektiv funktionsværdi:
-F = - 5x 1 - 3x 2 = -5 0 - 3 0 = 0.
Vores opgave er at tjekke, om en given referenceplan er optimal. For at gøre dette skal du se på indekslinjen - målfunktionslinjen F.
Forskellige situationer er mulige.
1. I indekset F- der er ingen negative elementer i strengen. Det betyder, at planen er optimal, og en løsning på problemet kan skrives ned. Objektivfunktionen har nået sin optimale værdi, svarende til tallet i nederste højre hjørne, taget med det modsatte fortegn. Lad os gå videre til fase IV.
2. Indeksrækken har mindst ét negativt element, hvis kolonne ikke har positive elementer. Så konkluderer vi, at den objektive funktion F→∞ falder uden grænse.
3. Indeksrækken har et negativt element, der har mindst ét positivt element i sin kolonne. Så går vi videre til næste fase III. Vi genberegner tabellen og forbedrer referenceplanen.
IIIscene. Forbedring af referenceplanen.
Fra de negative elementer i indekset F-rækker, vælg den med det største modul, kald den tilsvarende kolonneopløsning og marker den med "".
For at vælge en løsende række er det nødvendigt at beregne forholdet mellem elementerne i kolonnen frie termer kun Til positiv elementer i opløsningskolonnen. Vælg den mindste fra de opnåede relationer. Det tilsvarende element, hvor minimum er nået, kaldes opløsning. Vi vil fremhæve det med en firkant.
I vores eksempel, 
, element 2 er tilladt. Linjen, der svarer til dette element, kaldes også opløsning (tabel 3.5).
Tabel 3.5
Efter at have valgt det tilladte element, genberegner vi tabellen i henhold til reglerne:
1. I en ny tabel af samme størrelse som før ombyttes variablerne i den løsende række og kolonne, hvilket svarer til overgangen til et nyt grundlag. I vores eksempel: x 1 indgår i grundlaget i stedet for x 5, som forlader grundlaget og nu er gratis (tabel 3.6).
Tabel 3.6
|
grundlæggende |
gratis |
||
2. Skriv dets omvendte tal i stedet for det løsende element 2.
3. Vi deler opløsningslinjens elementer med opløsningselementet.
4. Vi deler opløsningskolonnens elementer med opløsningselementet og skriver dem med modsat fortegn.
5. For at udfylde de resterende elementer i tabel 3.6 omregner vi ved hjælp af rektangelreglen. Lad os sige, at vi vil tælle elementet ved position 50.
Vi forbinder mentalt dette element med det løsende, find produktet, fratræk produktet af elementerne placeret på den anden diagonal af det resulterende rektangel. Vi dividerer forskellen med det løsende element.
Så, . Vi skriver 10 på det sted, hvor der var 50. Tilsvarende :
, 
, , 
.
Tabel 3.7
Vi har nyt bord 3.7, er de grundlæggende variable nu variablerne (x 3,x 4,x 1). Værdien af den objektive funktion blev lig med -200, dvs. faldt. For at kontrollere denne grundlæggende løsning for optimalitet, skal vi gå igen til fase II. Processen er åbenlyst begrænset; stopkriteriet er punkt 1 og 2 i trin II.
Lad os færdiggøre løsningen af problemet. For at gøre dette, lad os kontrollere indekslinjen og, når vi ser et negativt element i den, kalder den tilsvarende kolonneopløsning og genberegner tabellen i henhold til trin III. Efter at have kompileret relationerne og valgt minimum = 40 blandt dem, bestemte vi det løsende element 1. Nu udfører vi genberegningen i henhold til reglerne 2-5.
Tabel 3.8
|
grundlæggende |
gratis |
||
|
x 3 = 30, x 2 = 40, x 1 = 20. Frie variabler er 0, x 5 = 0, x 4 = 0. Objektivfunktionen tager værdien sidste element kolonne med frie udtryk med det modsatte fortegn: - F = -220 F = 220, i vores eksempel blev funktionen undersøgt ved min, og indledningsvis F max, så skiltet skiftede faktisk to gange. Så, x* = (20, 40, 30, 0, 0), F* = 220. Svar på problemet: Det er nødvendigt at medtage 20 produkter af typen i produktionsplanen EN, 40 produkter af type B, mens fortjenesten vil være maksimal og vil være lig med 220 rubler. I slutningen af dette afsnit præsenterer vi et flowchart af simplex-metodealgoritmen, som nøjagtigt gentager trinene, men måske for nogle læsere vil det være mere praktisk at bruge, da pilene angiver en klar retning af handlinger. Linkene over boksene i rutediagrammet angiver, hvilket trin eller underpunkt den tilsvarende gruppe af transformationer tilhører. reglen for at finde den oprindelige referenceplan vil blive formuleret i afsnit 3.7.
Spørgsmål til selvkontrol 1. Hvordan er et simpleksbord opbygget? 2. Hvordan afspejles en ændring i grundlaget i tabellen? 3. Formuler stopkriteriet for simpleksmetoden. 4. Hvordan organiserer man tabelgenberegning? 5. Fra hvilken linje er det praktisk at begynde at genberegne tabellen? |
For at tillade appletten at køre på din computer, skal du gøre følgende - klik på Start>Kontrolpanel>Programmer>Java. I Java-vinduet Kontrolpanel vælg fanen Sikkerhed, klik på knappen Rediger webstedsliste, knappen Tilføj og indsæt stien til denne side fra det frie felt adresse bar browser. Klik derefter på OK, og genstart derefter computeren.
For at starte appletten skal du klikke på knappen "Simplex". Hvis knappen "Simplex" ikke er synlig over denne linje, er Java ikke installeret på din computer.
Efter at have klikket på knappen "Simplex", vises det første vindue til indtastning af antallet af variabler og antallet af begrænsninger for problemet på simpleksmetoden.
Efter at have klikket på knappen "ok" vises et vindue til indtastning af de resterende data for problemet ved hjælp af simpleksmetoden: visningstilstand (decimalbrøker eller almindelige), type opgavekriterium min eller maks., input af koefficienter for objektivfunktionen og koefficienter for systemet af begrænsninger med tegnene "≤", " ≥ "eller "=", begrænsninger af formen x i ≥ 0 behøver ikke at indføres, tager højde for dem i sin algoritme.
Efter at have klikket på knappen "Løs" vises et vindue med resultaterne af løsningen af problemet .Vinduet består af to dele, øverst er der et tekstfelt med en beskrivelse af rollebesætningen. oprindelige problem til den kanoniske form, som bruges til at kompilere den første simplex-tabel. I bunden af vinduet, i et panel med faner, er der simplekstabeller af hver iteration med en lille tekstfelt nedenfor angiver tilladelseskolonnen, tilladelsesrækken og andre oplysninger, som gør programmet lærerigt. I fanen med den optimale (sidste) tabel vises den resulterende optimale løsning på problemet i tekstfeltet.
Send eventuelle fejl, du bemærker, og kommentarer til appletten til: [e-mail beskyttet] eller ring på 8 962 700 77 06, hvilket vi vil være dig meget taknemmelig for.
M-metode program
Program til at løse transport problem
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. 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. Problemer, der skal løses ved hjælp af simplex-metoden, skal have følgende to egenskaber:
-systemet af begrænsninger skal være et ligningssystem med et grundlag;
-frie led for alle ligninger i systemet skal være ikke-negative.
Det resulterende system er et system med et grundlag, og dets frie udtryk er ikke-negative, så simplex-metoden kan anvendes. Lad os skabe den første simplex-tabel (Iteration 0), 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.
iteration 0
BP |
Løsning | Holdning | |||||
For at forbedre løsningen går vi videre til næste iteration og får den følgende simplex-tabel. For at gøre dette skal du vælge aktivér kolonne, dvs. en variabel, der vil indgå i grundlaget ved næste iteration. Det vælges af den største absolutte negative koefficient i z-rækken (i det maksimale problem) - i den indledende iteration er dette x 2 kolonnen (koefficient -6).
Vælg derefter aktivere streng, dvs. en variabel, der forlader basis ved næste iteration. 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 erstatte s 3 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 elementer i række x 2 i tabellen "Iteration 1" 0 1 0 0 1 20 med -3, få 0 -3 0 0 -3 -60 og tilføje denne række med s 2 - række i tabellen "Iteration 0" 1 3 0 1 0 72, vi får rækken 1 0 0 1 -3 12. I kolonnen x 2 opnå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 linje= Gammel række – (Gamle rækkeopløsningskolonnekoefficient)*(Ny opløsningsrække).
For eksempel har vi for en z-streng:
Gammel z-streng (-4 -6
0
0
0
0)
-(-6)*Ny opløsningslinje -(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.
iteration 1
| Løsning | 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.
Gentagelse 2
| Løsning | 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.
Gentagelse 3
| Løsning | 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.
Enkel metode, der løser et problem med et kunstigt grundlag
2) Lad os løse problemet med et kunstigt grundlag (mindst ét ulighedsbegrænsningstegn "≥" eller "=").
Lad os skrive problemet i kanonisk form (i form af et ligningssystem, som kræver simpleksmetoden), for at gøre dette introducerer vi to variable x 3 ≥ 0 og x 4 ≥ 0, vi får:
Systemet af begrænsninger tilbyder kun én tilladt grundvariabel x 4, kun den er inkluderet i kun én ligning i den tredje med en koefficient på 1, så vi tilføjer kunstige variable R 1 ≥ 0 og R 2 ≥ 0 til den første og anden ligning så simplex-metoden kan anvendes skal systembegrænsningsligninger være et system med basis, dvs. i hver ligning skal der være en variabel med koefficienten 1, som kun indgår i én af systemets ligning, i vores tilfælde er disse R 1, R 2 og x 4. Vi fik den såkaldte M-opgave:
Dette system er et system med et grundlag, hvor R 1, R 2 og x 4 er grundvariable, og x 1, x 2 og x 3 er frie variable, er de frie led i alle ligninger ikke-negative. Derfor kan simpleksmetoden bruges til at løse problemet. Lad os skrive den indledende simplex-tabel ned:
iteration 0
| Løsning | Holdning | |||||||
| -16 | ||||||||
Linjen "Evaluering" er tilføjet tabellen for problemer med et kunstigt grundlag. Det opnås ved at summere de tilsvarende koefficienter for rækker med kunstige variable (R) med det modsatte fortegn. Det vil være til stede i tabellen, så længe mindst én af de kunstige variable er i grundlaget. Baseret på den største modulo negative koefficient på "Evaluering"-linjen, bestemmes den løsende kolonne, mens den er i tabellen. Når rækken "Evaluering" forlader tabellen (der er ingen kunstige variable i grundlaget), vil den løsende kolonne blive bestemt af z-rækken, som i problemet med startgrundlaget. I denne tabel er den løsende kolonne x 2, den er valgt ud fra den største absolutte negative score (-7). Den løsende række R 2 er valgt baseret på det mindste forhold mellem "Løsning"-kolonnen og de tilsvarende positive elementer i den løsende kolonne, som i problemet uden kunstige variable. Det betyder, at ved næste iteration vil variablen x2 gå fra fri til basis, og variablen R2 vil gå fra basis til fri. Lad os skrive følgende simplekstabel:
Løsning af kolonne x 1, løsning af række R 1, R 1 forlader basis, x 1 går ind i basis. Herefter er der ingen kunstige variable tilbage i grundlaget, så der er ingen "Evaluering" linje i følgende tabel:
iteration 2
| Løsning | Holdning | |||||||
Dernæst vælges opløsningskolonnen af z-rækken. I z-rækken er alle koefficienter ikke-negative bortset fra koefficienten for den kunstige variabel R 1, som ikke påvirker optimaliteten, når de kunstige variable forlader basis. Som følge heraf opnås den optimale opløsning x 1 = 6/5; x 2 = 3/5; z max = 72/5.
Særlige tilfælde af brug af simpleksmetoden
1) Når den rette linie (hvis et todimensionelt lineært programmeringsproblem betragtes, og i det generelle tilfælde et hyperplan), der repræsenterer den objektive funktion, er parallel med den rette linie (hyperplan), der svarer til en af ulighedsbegrænsningerne (som ved optimalt punkt er opfyldt som en nøjagtig lighed), tager den objektive funktion en og samme optimal værdi på et bestemt sæt punkter på grænsen af området for gennemførlige løsninger. Disse løsninger kaldes alternativ optimale løsninger . Tilgængelighed alternative løsninger kan bestemmes ud fra den optimale simplex-tabel. Hvis z-rækken i den optimale tabel indeholder nulkoefficienter af ikke-grundlæggende variable, så er der alternative løsninger.
2) Hvis alle koefficienter i simplex-tabellens opløsningskolonne er mindre end eller lig med nul, så er det umuligt at vælge en opløsningsrække, i dette tilfælde er løsningen ubegrænset.
3) Hvis begrænsningerne for et lineært programmeringsproblem er inkonsistente (det vil sige, at de ikke kan opfyldes samtidigt), så har problemet ingen gennemførlige løsninger. Denne situation kan ikke opstå, hvis alle de uligheder, der udgør restriktionssystemet, er af typen "≤" med ikke-negative højresider, fordi i dette tilfælde kan yderligere variable udgøre mulig løsning. For andre typer begrænsninger anvendes kunstige variable. Hvis problemet har en løsning, så er der i den optimale tabel ingen kunstige variable (R i) i grundlaget. Hvis de er der, så har problemet ingen løsninger.