Sådan finder du et opløsningselement i en simplekstabel. Tilpasset lineær programmeringsløsning

Det er praktisk at udføre ovenstående transformationer i specielle tabeller kaldet simplex-tabeller.

Simplextabellen indeholder følgende blokke:

Lad os skrive løsningen på eksempelproblemet fra afsnit 3.3 i simplekstabeller:

Alle indledende data indeholdt i den matematiske tilstand af problemet overføres til den første simplex bord. Ved at sætte de frie variable til nul, får vi referenceplanen

I den sidste række af den første simplex-tabel indtaster vi kriteriet i implicit form

Vi udelukker grundvariablen x 4 fra dette kriterium, hvilket bringer kriteriet til formen

For at løsningen er optimal, skal alle estimater være ikke-negative

Løsningen er ikke optimal, pga der er negative vurderinger.

Scorer kan beregnes ved hjælp af formler. Produktet er den aktuelle vektor af tilstandsmatricen, så kan estimatet af den frie variabel beregnes som skalarproduktet af vektoren af koefficienter for de grundlæggende variable ved den aktuelle vektor af tilstandsmatricen minus koefficienten af den objektive funktion for denne variabel. Så, for vi får værdien

Løsningskolonnen er valgt til at være den med det mindste skøn (hvis problemet er for maksimum). Og for at vælge en opløsende linje skal du blandt alle linjerne finde variablen udtrykt fra den, som falder, og som hurtigt bliver nul.

Som et resultat får vi, at den løsende kolonne er , og den løsende række er . Det betyder, at en variabel kommer ud af listen over grundlæggende, og en variabel kommer ind.

Løsningen er ikke optimal, pga der er en negativ vurdering på -2.

Løsningen er optimal, pga alle score er større end nul. Det kan naturligvis ikke øges.

Regler for konstruktion af simplekstabeller

En simplekstabel er konstrueret til enhver referenceløsning.

Lad referenceløsningen. Simplextabellen for denne løsning har formen

Basismatrix B = (A 1 , A 2 , ... A m)

· for grundlæggende variabler er den aktuelle matrix identitet.

· enhver kolonne.
· vektor af højre side af begrænsninger.
· estimater for frie variabler er ikke nul

· i nederste højre celle - værdien af kriteriet

Stadier af simpleksmetoden

1. Kontrol af optimalitetstegnet ()
2. Hvis der er, så er løsningen ikke optimal. Vælg derefter kolonnen med minimumscore. Lad os kalde det eftergivende.
3. Opløsningsrækken vælges baseret på minimumsforholdet mellem frie led og de positive koefficienter i opløsningskolonnen. Basisvariablen udtrykt fra denne linje fjernes fra listen over basisvariabler. De der. x k går ud og x s går ind.

4. Den aktuelle simplekstabel konverteres efter følgende regel:
- · den tilladte linje er opdelt i det tilladte element:

· opløsningskolonnen erstattes af en enkelt.
· alle andre elementer i simplekstabellen kan genberegnes ved hjælp af firkantsreglen:

En firkant er mentalt konstrueret på diagonalen, der forbinder det søgte element med det opløsende element. Så er den nye værdi af elementet lig med den tidligere værdi minus produktet af elementerne på den modsatte diagonal divideret med det opløsende element.

Eller den nye elementværdi er lig med produktet af elementerne på hoveddiagonalen minus produktet af elementerne på den modsatte diagonal, alle divideret med det opløsende element.

Kommentar : Hvis der var et nul-element i opløsningsrækken, ændres denne kolonne ikke; Hvis der er et null-element i resolve-kolonnen, ændres den tilsvarende række ikke.

For at begynde arbejdet kræves det, at det givne system af begrænsninger udtrykkes ved ligheder, og i dette system af begrænsninger skal de grundlæggende ukendte identificeres. Løsning af et problem ved hjælp af simpleksmetoden er opdelt i en række trin. Ved hvert trin flytter de fra dette grundlag B til et andet, nyt grundlag B 1 med en sådan beregning, at værdien af funktionen Z falder, dvs. . For at flytte til et nyt grundlag fjernes en af variablerne fra den gamle basis, og en anden blandt de frie indføres i stedet. Efter et endeligt antal trin findes et bestemt grundlag B (k), for hvilket der er det ønskede minimum for den lineære funktion Z, og den tilsvarende grundlæggende løsning er optimal, eller det viser sig, at problemet ikke har nogen løsning.

4.1 Simplexmetodens algoritme.

Lad mig overveje et system af begrænsninger og en lineær form af formen:

(4.1)

Ved hjælp af Jordan-Gauss metoden reducerer vi det skrevne system til en form, hvor de grundlæggende variabler er fremhævet.

Lad os introducere nogle konventioner:

-grundlæggende variabler;

– frie variabler.

(4.4)

Ved at bruge det sidste system af begrænsninger, vil vi konstruere en tabel. 4.1.

Tabel 4.1

Simplex bord

Ledig

Grundlæggende

ukendt

Gratis

Denne tabel kaldes en simplex tabel. Alle yderligere transformationer er forbundet med ændringer i indholdet af denne tabel.

Algoritmen for simplex-metoden er som følger.

1. Den sidste række i simplekstabellen indeholder det mindste positive element, frit led ikke medregnet. Kolonnen, der svarer til dette element, betragtes som tilladelig.

2. Beregn forholdet mellem frie led og de positive elementer i opløsningskolonnen (simpleksforhold). Find den mindste af disse simplex-relationer, den svarer til opløsningsstrengen.

3. I skæringspunktet mellem den løsende række og kolonnen er der et opløsningselement.

4. Hvis der er flere simpleksrelationer af samme størrelse, så vælg en af dem, vælg derefter en af dem. Det samme gælder for de positive elementer i den sidste række i simplekstabellen.

5. Efter at have fundet aktiveringselementet, gå videre til næste tabel. De ukendte variabler svarende til det aktiverende dræn og søjle ombyttes. I dette tilfælde bliver grundvariablen en fri variabel og omvendt. Simplextabellen konverteres som følger

Tabel 4.2

Simplex bord

Ledig

Grundlæggende

ukendt

Gratis

6. Bordelement 4.2 svarende til det tilladte element i tabellen. 4.1, er lig med den gensidige værdi af det opløsende element.

7. Tabelrækkeelementer. 4.2, svarende til elementerne i tabellens tillade strømme. 4.1 opnås ved at dividere de tilsvarende elementer i tabellen. 4.1 til det løsende element.

8. Tabelsøjleelementer. 4.2, svarende til elementerne i opløsningskolonnen i tabellen. 4.1 opnås ved at dividere de tilsvarende elementer i tabellen. 4.1 til det opløselige element og tages med modsat fortegn.

9. De resterende elementer beregnes efter rektangelreglen: vi tegner mentalt et rektangel i tabel 4.2, hvor det ene toppunkt falder sammen med det opløsende element, og det andet med det element, hvis billede vi leder efter; de resterende to hjørner er entydigt bestemt. Derefter det nødvendige element i bordet. 4.2 vil være lig med det tilsvarende element i tabellen. 4,1 minus brøken i nævneren, der indeholder det opløselige element, og i tælleren produktet af elementerne fra rektanglets to ubrugte spidser.

10. Så snart der er opnået en tabel, hvor alle elementer i den sidste række er negative, anses det for, at minimum er fundet. Funktionens minimumværdi er lig med det frie led i rækken af objektivfunktionen, og den optimale løsning bestemmes af basisvariablenes frie led. Alle frie variable i dette tilfælde er lig med nul.

11. Hvis alle elementer i opløsningskolonnen er negative, har problemet ingen løsninger (minimum er ikke opnået).

5. Metoder til at finde en referenceløsning til et lineært programmeringsproblem.

5.1. Kunstig basismetode.

Simplex-metodealgoritmen formuleret ovenfor kan kun anvendes, hvis den første mulige løsning er identificeret, dvs. oprindelige problem lineær programmering bragt i tankerne

Samtidig med at sætte de frie ubekendte lig med nul, får vi en referenceløsning.

Jeg vil overveje en metode til at finde en referenceløsning baseret på introduktion af kunstige variable. For at gøre dette skriver vi det lineære programmeringsproblem ind generel opfattelse. Vi vil overveje et problem med en række ukendte og begrænsninger:

(5.1)

Lad os omskrive systemet (5.1) i en anden form. For at gøre dette introducerer vi kunstige variable, så et grundlag identificeres. Så vil systemet tage formen

(5.2)

Systemer (5.1) og (5.2) vil være ækvivalente, hvis alle for er lig med 0. Derudover tror jeg, at alle for. Ellers multiplicerer vi de tilsvarende begrænsninger fra system (5.1) med – 1. For at de skal være lig med 0, skal vi transformere problemet på en sådan måde, at alle kunstige variable bliver frie ubekendte.

I dette tilfælde vil system (5.2) efter transformation have formen:

(5.3)

Du kan altid gå fra system (5.2) til system (5.3) ved at bruge simplex-metodens trin. I en sådan overgang betragtes funktionen som en lineær form

lig med summen af kunstige variable. Overgangen er afsluttet, når alle kunstige variable er konverteret til frie ubekendte.

Analyse af løsningsmuligheder

1. Hvis , og alle konverteres til frie variable, så har problemet ikke en positiv løsning.

2. Hvis , og en del forbliver i grundlaget, så for at konvertere dem til gratis dem er det nødvendigt at bruge specielle teknikker.

I simplekstabellen svarende til system (5.3), efter , og alle er frie, streg rækken ud for og kolonnerne for og løs problemet for den oprindelige lineære form.

5.2. Anden søgealgoritme referenceplan.

Lad det lineære programmeringsproblem skrives i kanonisk form:

(5.5)

Lad os konstruere den første Jordan-Gauss-tabel for problemer (5.5) og (5.6). For at sikre ensartethed af beregningsproceduren tildeler vi en række af målfunktionen til kildetabellen:

Efter at have bragt systemet med begrænsninger til en enhedsbasis objektiv funktion, ligesom de grundlæggende variabler, vil blive udtrykt gennem frie variable. Jeg brugte en lignende teknik, når jeg løser problemer ved hjælp af den grafiske metode med mere end to variable.

Metode algoritme

1. Lad os skrive problemet i formen (5.7), og alle elementer i kolonnen med frie udtryk skal være ikke-negative. Systemligninger (5.5), hvor de frie led er negative, skal først ganges med – 1.

2. Vi transformerer tabel (5.7) ved hjælp af Jordan-Gauss eliminationstrin. I dette tilfælde kan en hvilken som helst kolonne, der indeholder mindst ét positivt element ved hvert trin, vælges som opløsende. Rækken af objektivfunktionen påvirker ikke valget af opløsningskolonner.

3. Opløsningsrækken bestemmes af den mindste af forholdet mellem frie led og elementerne i den løsende kolonne.

4. Under transformationsprocessen krydser vi linjer, der kun består af nuller.

5. Hvis der i processen med transformationer stødes på en streng, hvor alle elementer er nuller, og det frie led er ikke-nul, så har problemet ingen løsning. Hvis man støder på en linje, hvor der udover den frie sigt ikke er andre positive elementer, så siger man, at problemet ikke har nogen positive løsninger.

Forklaring. I paragraf 1.1 i algoritmen antages det, at alle elementer i kolonnen med frie termer er ikke-negative. Dette krav er valgfrit. I det tilfælde, hvor der er negative tal i kolonnen med frie led, vil vi bruge sætningen.

Sætning. Hvis det opløsende element vælges i overensstemmelse med det mindste positive simplex-forhold, så efter Jordan-Gauss-trinnet bliver det frie led i opløsningslinjen positiv, og de resterende led beholder deres fortegn.

Valget af det opløsende element foretages anderledes, nemlig.

1. Se på linjen, der svarer til ethvert negativt friled. Vælg et hvilket som helst negativt element i det - kolonnen, der svarer til dette element, løses.

2. Valget af opløsningselementet foretages i henhold til det mindste positive simpleksforhold. Hvis problemet kan løses, opnås den første mulige løsning efter et begrænset antal trin, og simplex-metoden kan anvendes.

I nogle tilfælde er den første mulige løsning fundet på denne måde også den optimale løsning.

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 sikre 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 af uligheder med et system af lineære ligninger ved at indføre yderligere ikke-negative variable 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.

Siden i sidste linje har vi igen negative tal, 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.

Lad os overveje løsningen ZLP ved hjælp af simplex-metoden og præsentere det i forhold til maksimeringsproblemet.

1. På baggrund af problemets betingelser sammenstilles dens matematiske model.

2. Den kompilerede model konverteres til kanonisk form. I dette tilfælde kan et grundlag med en indledende referenceplan identificeres.

3. Den kanoniske model af problemet er skrevet i form af en simplekstabel, så alle frie termer er ikke-negative. Hvis den oprindelige referenceplan er valgt, skal du fortsætte til trin 5.

Simplex tabel: et system af begrænsningsligninger og en objektiv funktion indtastes i form af udtryk, der er løst i forhold til startgrundlaget. Rækken, hvori koefficienterne for objektivfunktionen F er skrevet, kaldes F-rækken eller objektivfunktionsrækken.

4. Find den indledende referenceplan ved at udføre simplekstransformationer med positive opløsningselementer svarende til minimumssimplexrelationerne og uden at tage hensyn til fortegnene for F-rækkeelementerne. Hvis der under transformationerne stødes på en 0-række, hvis elementer, bortset fra det frie led, er nuller, så er systemet af begrænsningsligninger for problemet inkonsistent. Hvis vi støder på en 0-række, hvor der udover det frie led ikke er andre positive elementer, så har systemet af restriktive ligninger ingen ikke-negative løsninger.

Reduktion af system (2.55), (2.56) til et nyt grundlag vil blive kaldt en simplekstransformation. Hvis en simplekstransformation betragtes som en formel algebraisk operation, så kan man bemærke, at som et resultat af denne operation omfordeles roller mellem to variable inkluderet i et bestemt system lineære funktioner: den ene variabel går fra afhængig til uafhængig, og den anden går tværtimod fra uafhængig til afhængig. Denne operation er kendt i algebra som Jordan-elimineringstrinnet.

5. Den fundne indledende støtteplan undersøges for optimalitet:

a) hvis der ikke er negative elementer i F-rækken (frit led ikke medregnet), så er planen optimal. Hvis der ikke er nuller, så er der kun én optimal plan; hvis der er mindst et nul, så er der et uendeligt antal optimale planer;

b) hvis der er mindst et negativt element i F-rækken, som svarer til en kolonne af ikke-positive elementer, så<

c) hvis der er mindst et negativt element i F-rækken, og der er mindst et positivt element i dens kolonne, så kan du flytte til en ny referenceplan, der er tættere på den optimale. For at gøre dette skal den angivne kolonne tildeles som en løsende kolonne, ved hjælp af minimum simplex-relationen, find den løsende række og udfør simplex transformation. Den resulterende referenceplan undersøges igen for optimalitet. Den beskrevne proces gentages, indtil der opnås en optimal plan, eller indtil problemets uløselighed er fastslået.

Kolonnen med koefficienter for en variabel, der er inkluderet i grundlaget, kaldes opløsning. Ved at vælge en variabel indført i basis (eller vælge en opløsende kolonne) baseret på det negative element i F-rækken sikrer vi således, at funktionen F øges.

Det er lidt sværere at bestemme den variabel, der skal udelukkes fra grundlaget. For at gøre dette sammensætter de forholdet mellem frie udtryk og de positive elementer i den løsende kolonne (sådanne relationer kaldes simplex) og finder den mindste blandt dem, som bestemmer rækken (opløsning), der indeholder den udelukkede variabel. Valget af en variabel, der er udelukket fra grundlaget (eller valget af en opløsende linje) i henhold til den minimale simplex-relation garanterer, som det allerede er fastslået, positiviteten af basiskomponenterne i den nye referenceplan.

I punkt 3 i algoritmen antages det, at alle elementer i kolonnen frie termer er ikke-negative. Dette krav er ikke nødvendigt, men hvis det er opfyldt, udføres alle efterfølgende simplex-transformationer kun med positive opløsningselementer, hvilket er praktisk til beregninger. Hvis der er negative tal i kolonnen med frie termer, vælges det løsende element som følger:

1) se gennem rækken, der svarer til et negativt frit led, for eksempel en t-række, og vælg et negativt element i den, og den tilsvarende kolonne tages som løsende (vi antager, at problemets begrænsninger er konsistente);

2) opgør relationerne mellem elementerne i kolonnen med frie udtryk til de tilsvarende elementer i den løsende kolonne, der har de samme tegn (simplekse relationer);

3) vælg den mindste af simpleksrelationerne. Dette vil bestemme aktiveringsstrengen. Lad det for eksempel være en p-streng;

4) i skæringspunktet mellem den løsende kolonne og rækken findes et opløsende element. Hvis et element i y-rækken viser sig at være opløselig, vil efter simplex-transformationen den frie led i denne række blive positiv. Ellers vender næste trin tilbage til t-strengen. Hvis problemet kan løses, vil der efter et vist antal trin ikke være nogen negative elementer tilbage i kolonnen med frie udtryk.

At finde den oprindelige referenceplan, kanonisk visning af ZLP

Ideen om sekventiel forbedring af løsningen dannede grundlaget for en universel metode til løsning af lineære programmeringsproblemer - simplex-metoden eller metoden til sekventiel forbedring af planen.

Simplexmetodens geometriske betydning består i en sekventiel overgang fra et toppunkt af begrænsningspolyederet (kaldet det indledende) til det naboliggende, hvor den lineære funktion tager den bedste (i hvert fald ikke den dårligste) værdi i forhold til målet med problemet; indtil den er fundet optimal løsning- det toppunkt, hvor den optimale værdi af målfunktionen opnås (hvis problemet har et endeligt optimum).

Simplexmetoden blev først foreslået af den amerikanske videnskabsmand J. Danzig i 1949, men tilbage i 1939 blev ideerne til metoden udviklet af den russiske videnskabsmand L.V. Kantorovich.

Simplex-metoden, som gør det muligt at løse ethvert lineært programmeringsproblem, er universel. I øjeblikket bruges det til computerberegninger, men simple eksempler ved hjælp af simpleksmetoden kan løses manuelt.

For at implementere simplex-metoden - konsekvent forbedring af løsningen - er det nødvendigt at mestre tre hovedelementer:

En metode til at bestemme enhver indledende gennemførlig grundlæggende løsning på et problem;

Reglen om overgang til den bedste (mere præcist, ikke værre) løsning;

Kriterium for kontrol af optimaliteten af den fundne løsning.

For at bruge simpleksmetoden skal det lineære programmeringsproblem reduceres til kanonisk form, dvs. systemet af begrænsninger skal præsenteres i form af ligninger.

Litteraturen beskriver tilstrækkeligt detaljeret: at finde den oprindelige referenceplan (indledende tilladte basisløsning), også at bruge den kunstige basismetode, at finde den optimale referenceplan, at løse problemer ved hjælp af simplekstabeller.

58. Simplexmetodens hovedsætning.

???????????????????????????????????????????????????????????????????????

59. Alternativt optimum i ZLP, degeneration i ZLP.

Degeneration i lineære programmeringsproblemer

Når vi overvejede simpleksmetoden, antog vi, at det lineære programmeringsproblem er ikke-degenereret, dvs. hver støtteplan indeholder præcis m positive komponenter, hvor m er antallet af begrænsninger i problemet. I en degenereret støtteplan viser antallet af positive komponenter sig at være mindre end antallet af restriktioner: nogle grundlæggende variabler svarende til en given støtteplan har nul værdier. Ved at bruge den geometriske fortolkning til det enkleste tilfælde, når n - m = 2 (antallet af ikke-grundlæggende variable er 2), er det let at skelne et degenereret problem fra et ikke-degenereret problem. I en degenereret opgave skærer mere end to rette linjer i det ene toppunkt af betingelsespolyederet, beskrevet ved ligninger på formen xi = 0. Det betyder, at en eller flere sider af betingelsespolygonen er kontraheret til et punkt. På samme måde, for n - m = 3 i et degenereret problem, skærer mere end 3 planer hinanden ved et toppunkt xi = 0. Under den antagelse, at problemet er ikke-degenereret

der var kun én værdi, ved hvilken indekset for vektoren af betingelser afledt af basis (variablen afledt af basis) blev bestemt. I

Det degenererede problem kan opnås på flere indekser på én gang (for flere rækker). I dette tilfælde vil flere grundvariable i den fundne referenceplan være nul. Hvis det lineære programmeringsproblem viser sig at være degenereret, kan der med et dårligt valg af vektoren af betingelser afledt af grundlaget forekomme uendelig bevægelse langs baserne af den samme referenceplan. Dette er det såkaldte looping-fænomen. Selvom looping er ret sjælden i praktiske lineære programmeringsproblemer, er dens mulighed ikke udelukket. En af metoderne til at håndtere degeneration er at transformere problemet ved "mindre" at ændre vektoren på højre side af systemet af begrænsninger på mængder på en sådan måde, at problemet bliver ikke-degenereret, og samtidig tid, så denne ændring ikke rigtig påvirker den optimale plan for problemet. Mere almindeligt implementerede algoritmer inkluderer nogle simple regler, der reducerer sandsynligheden for, at en loop opstår eller bliver overvundet. Lad variablen xj gøres grundlæggende. Lad os overveje

sættet af indekser E0 bestående af de i, som er opnået. Vi betegner det sæt af indekser i, for hvilket denne betingelse er opfyldt af E0,. Hvis E0 består af et element, så er vektoren af betingelser Ai udelukket fra basis (variablen xi gøres ikke-grundlæggende). Hvis E0 består af mere end et element, så dannes mængden E1, som består af , hvorpå . Hvis E1 består af et indeks k, så udledes variablen xk fra basis. Ellers dannes sættet E2 mv. I praksis bør reglen bruges, hvis cykling allerede er opdaget.

Alternativt optimum i ZLP????????????????????????????

60. Kunstig basismetode. M-opgave. Sætning om sammenhængen mellem løsningerne af det oprindelige problem og M-problemet.

Kunstig basismetode.

Den kunstige basismetode bruges til at finde en acceptabel basisløsning på et lineært programmeringsproblem, når betingelsen indeholder begrænsninger af lighedstypen. Lad os overveje problemet:

max(F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0).

De såkaldte "kunstige variable" Rj indføres i begrænsningerne og i målfunktionen som følger:

∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj

Ved indføring af kunstige variable i den kunstige basismetode i objektivfunktionen tildeles de en tilstrækkelig stor koefficient M, hvilket har betydningen af en straf for at indføre kunstige variable. I tilfælde af minimering tilføjes kunstige variable til målfunktionen med en koefficient M. Indførelse af kunstige variable er tilladt, hvis de i processen med at løse problemet successivt forsvinder.

En simplex-tabel, som udarbejdes under løsningsprocessen ved hjælp af den kunstige basismetode, kaldes udvidet. Den adskiller sig fra den sædvanlige ved, at den indeholder to linjer for målfunktionen: en for komponenten F = ∑cixi, og den anden for komponenten M ∑Rj. Lad os overveje proceduren for at løse problemet ved hjælp af et specifikt eksempel.

Eksempel 1. Find maksimum af funktionen F(x) = -x1 + 2x2 - x3 under begrænsningerne:

x1≥0, x2≥0, x3≥0.

Lad os bruge den kunstige basismetode. Lad os introducere kunstige variable i problembegrænsningerne

2x1 + 3x2 + x3 + R1 = 3;

x1 + 3x3 + R2 = 2;

Objektiv funktion F(x)-M ∑Rj= -x1 + 2x2 - x3 - M(R1+R2).

Lad os udtrykke summen R1 + R2 fra systemet af begrænsninger: R1 + R2 = 5 - 3x1 - 3x2 - 4x3, derefter F(x) = -x1 + 2x2 - x3 - M(5 - 3x1 - 3x2 - 4x3) .

Når vi kompilerer den første simplekstabel (tabel 1), vil vi antage, at de oprindelige variable x1, x2, x3 er ikke-basiske, og de introducerede kunstige variable er grundlæggende. I maksimeringsproblemer vendes fortegnet af koefficienterne for ikke-grundlæggende variable i F- og M-rækkerne. Tegnet for den konstante værdi i M-linjen ændres ikke. Optimering udføres først langs M-linjen. Udvælgelsen af ledende kolonner og rækker, alle simplex-transformationer ved brug af den kunstige basismetode udføres som i den sædvanlige simpleksmetode.

Den maksimale negative koefficient i absolut værdi (-4) bestemmer den førende søjle og variablen x3, som vil gå ind i grundlaget. Det minimale simpleksforhold (2/3) svarer til den anden række i tabellen, derfor skal variablen R2 udelukkes fra grundlaget. Det ledende element er skitseret.

I den kunstige basismetode returneres kunstige variable, der er udelukket fra grundlaget, ikke længere til den, så kolonnerne med elementer i sådanne variable udelades. Bord 2. nedsat med 1 kolonne. Ved at foretage en genberegning af denne tabel går vi videre til tabellen. 3., hvor linjen M er blevet nulstillet, kan den fjernes. Efter at have fjernet alle kunstige variable fra grundlaget, opnår vi en acceptabel basisløsning på det oprindelige problem, som i det betragtede eksempel er optimal:

x1=0; x2=7/9; Fmax=8/9.

Hvis løsningen ikke er optimal ved eliminering af M-strengen, fortsætter optimeringsproceduren og udføres ved hjælp af den sædvanlige simpleksmetode. Lad os overveje et eksempel, hvor der er begrænsninger af alle typer: ≤,=,≥

Opgaven

Find de optimale produktionsværdier for produkter af type A, B og C. Råvareomkostninger pr. produktionsenhed: A – 5, B – 2, C – 4. Råvaremængde – 2000 enheder. Udstyrsomkostninger pr. produktionsenhed: A – 4, B – 5, C – 4. Udstyrsvolumen – 1000 enheder. Fortjeneste ved salg af en produktionsenhed: A – 10, B – 8, C – 12. Kriteriet er virksomhedens maksimale fortjeneste. Produktionen af produkt A skal være på mindst 100 enheder. Produktionen af produkt B skal være på mindst 50 enheder.

Løsning af simplex-problemet ved hjælp af M-metoden

1) Fastlæggelse af den optimale produktionsplan

Lad x1, x2, x3 være mængden af producerede produkter af henholdsvis type A, B, C. Så har den matematiske model af problemet formen:

F = 10 x1 + 8 x2 + 12 x3 –>maks

Vi introducerer yderligere variable x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0 for at transformere ulighederne til ligheder.

For at vælge et indledende grundlag introducerer vi kunstige variable x8 ≥ 0, x9 ≥ 0 og meget stort antal M (M –> ∞). Vi løser ved hjælp af M-metoden.

F = 10 x1 + 8 x2 + 12 x3 + 0 x4 + 0 x5 + 0 x6 + 0 x7– M x8– M x9 –>max

Lad os tage x4 = 2000 som grundlag; x5 = 1000; x8 = 100; x9 = 50.

Vi indtaster dataene i en simplekstabel

Simplex bord nr. 1

Objektiv funktion:

0 2000 + 0 1000 + (– M) 100 + (– M) 50 = – 150 mio.

Vi beregner estimater ved hjælp af formlen:

Δ1 = 0 5 + 0 4 + (– M) 1 + (– M) 0 – 10 = – M – 10

Δ2 = 0 2 + 0 5 + (– M) 0 + (– M) 1 – 8 = – M – 8

Δ3 = 0 4 + 0 4 + (– M) 0 + (– M) 0 – 12 = – 12

Δ4 = 0 1 + 0 0 + (– M) 0 + (– M) 0 – 0 = 0

Δ5 = 0 0 + 0 1 + (– M) 0 + (– M) 0 – 0 = 0

Δ6 = 0 0 + 0 0 + (– M) (–1) + (– M) 0 – 0 = M

Δ7 = 0 0 + 0 0 + (– M) 0 + (– M) (–1) – 0 = M

Δ2 = 0 0 + 12 0 + 10 0 + 8 1 – 8 = 0

Δ3 = 0 0 + 12 1 + 10 0 + 8 0 – 12 = 0

Δ4 = 0 1 + 12 0 + 10 0 + 8 0 – 0 = 0

Δ5 = 0 (–1) + 12 1/4 + 10 0 + 8 0 – 0 = 3

Δ6 = 0 1 + 12 1 + 10 (–1) + 8 0 – 0 = 2

Δ7 = 0 · (–3) + 12 · 5/4 + 10 · 0 + 8 · (–1) – 0 = 7

Da der ikke er nogen negative vurderinger, er planen optimal.

Løsning på problemet: x1 = 100; x2 = 50; x3 = 175/2 = 87,5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450

Svar: x1 = 100; x2 = 50; x3 = 175/2 = 87,5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450 Det vil sige, at det er nødvendigt at producere x1 = 100 enheder af type A-produkter, x2 = 50 enheder af type B-produkter og x3 = 87,5 enheder af type C-produkter. Maksimal fortjeneste i dette tilfælde vil det være Fmax = 2450 enheder.

Sætning om sammenhængen mellem løsningerne af det oprindelige problem og M-problemet.

???????????????????????

Som det er kendt, er Jordan-Gauss-metoden, også kendt som metoden til sekventiel eliminering af ukendte, en modifikation af Gauss-metoden til løsning af lineære systemer algebraiske ligninger(SLAU).

Metoden er baseret på elementære transformationer (omdannelse af systemet til et tilsvarende), som omfatter:

tilføjelse til begge sider af en ligning af et system af en anden ligning af samme system, ganget med et andet tal end nul;
omarrangering af ligninger i systemet;
fjernelse fra ligningssystemet på formen 0 = 0.

I modsætning til den Gaussiske metode elimineres en variabel ved hvert trin fra alle ligninger undtagen én.

Metodetrinnet er som følger:

vælg en ukendt i den næste ligning med en koefficient forskellig fra nul (opløsende element);
dividere den valgte ligning med det opløsende element;
ved hjælp af den valgte ligning, udelukke det ukendte ved det opløsende element fra alle andre ligninger;
ved næste trin er den anden ukendte på samme måde udelukket fra alle ligninger undtagen én;
processen fortsætter, indtil alle ligninger er blevet brugt.

Du kan algoritme det sådan her:

For SLAE i matrixform A*x=b (matrix A med dimension m*n, ikke nødvendigvis kvadratisk), er følgende tabel kompileret:

Det løsende element a r,s ≠0 er valgt i tabellen, derefter er r den løsende række, s er den løsende kolonne.

Overgangen til næste tabel udføres i henhold til reglerne:

1. elementerne i den løsende række beregnes: a" r,j =a r,j /a r,s - dvs. tabellens r-række divideres med det løsende element;

2. alle elementer i opløsningskolonnen undtagen en r,s, lig med én, blive lig med nul;

3. Elementer uden for den tilladelige række og kolonne beregnes ved hjælp af formlen vist nedenfor:

Det er let at undgå forvirring, når du ser, at tælleren i denne formel svarer til at beregne determinanten for en 2-til-2-matrix.

4. Ved manuel beregning sammenlignes værdien i den sidste kontrolkolonne med summen af de foregående elementer i rækken. Hvis værdierne ikke stemmer overens, skal der kigges efter fejl i denne linje. Ved automatiserede beregninger kan kontrolkolonnen udelades.

Følgende tilfælde er mulige:

1. I elimineringsprocessen vender venstre side af systemligningen til 0, og højre side b≠0, så har systemet ingen løsning.

2. Identiteten 0 = 0 opnås - ligningen er en lineær kombination af resten og nullinjen kan slettes fra systemet.

3. Efter at have brugt alle ligningerne til at eliminere de ukendte, indeholder tabellen enten den ønskede løsning eller viser inkonsistensen af systemet af begrænsninger.

Lad os programmere metoden i Excel ved hjælp af én formel, som ikke burde være for svær at ændre. For eksempel at løse SLAE

Lad os udfylde arkcellerne fra A1 til og med D4 med systemets koefficienter, vælge opløsningselementet a 1,1 =1 og lave det første trin i metoden i celle A6, hvor vi indtaster den "universelle" formel for Jordan-Gauss transformationen:

HVIS(RÆKKE($A$1)=RÆKKE(A1);A1/$A$1;
HVIS(KOLUMNE($A$1)=KOLONNE(A1),0,(A1*$A$1-
INDIREKTE(ADRESSE(RÆKKE(A1),KOLONNE($A$1)))*
INDIREKTE(ADRESSE(RÆKKE($A$1),KOLONNE(A1)))/$A$1))

I det næste trin kunne opløsningselementet for eksempel være en 2,2 =1 (celle B7). Alt vi skal gøre er at kopiere formlen fra A6 til A11 (af tom linje forlad for visuelt at adskille metodens trin), indtast formelredigeringstilstanden ( Dobbeltklik af celle eller vælg den og tryk på F2-tasten) og ret (træk forsigtigt musen uden for grænsen) alle fastgjorte links fra celle A1 til B7.

Selvfølgelig kan du erstatte den fastgjorte reference $A$1 overalt i formlen med en konstruktion af formen INDIRECT(CELL) , der danner dynamisk adresse links. Lad os sige, INDIREKTE(F8), og i celle F8 vil adressen på opløsningselementcellen automatisk blive genereret i henhold til det brugerspecificerede række- og kolonnenummer. Derefter skal du angive disse række- og kolonnenumre individuelle celler for eksempel sådan her:

Ak, alt dette vil ikke give noget - i stedet for $A$1, bliver vi simpelthen nødt til at rette INDIRECT($F$8) i formlen og alligevel trække og slippe det samme antal links, når vi kopierer formlen. Derudover skal de "manuelt" indtastede række- og kolonnenumre også kontrolleres for gyldighed (i det mindste som i figuren), så vi vil ikke gange entiteter.

Du kan se metoden i aktion på de to første ark af den vedhæftede Excel-fil(2 forskellige eksempler).

Det følgende er også baseret på Jordan-Gauss-transformationen universel metode løsning af lineære optimeringsproblemer, som f.eks simpleks metode. Beskrivelser af det er normalt skræmmende, lange og overlæssede med sætninger. Lad os prøve at lave en simpel beskrivelse og udvikle en algoritme, der er egnet til beregning i Excel. Faktisk er simplex-metoden allerede indbygget i standardanalysepakketilføjelsen, og der er ingen grund til at programmere den "manuelt", så vores kode har en ret pædagogisk værdi.

Først et minimum af teori.

Hvis kolonnevektorerne i SLAE er lineært uafhængige, er de tilsvarende variable grundlæggende og resten - gratis. For eksempel i SLAU

variablerne x 2 og x 4 er grundlæggende, og x 1 og x 3 er frie. Grundvariablerne er uafhængige af hinanden, og de frie kan laves fx nuller og få ( x 2 =2, x 4 =1) – grundlæggende løsning systemer.

Ved at vælge forskellige opløsningselementer er det muligt at opnå løsninger af SLAE'er med forskellige baser. Enhver ikke-negativ basisløsning af en SLAE kaldes understøttende.

Simplexmetoden giver en overgang fra en referenceløsning til en anden, indtil den er opnået optimal løsning, der giver den minimale objektive funktion.

Simplex-metodens algoritme er som følger:

1. LP-problemet er transformeret til kanonisk form:

Dette kan altid gøres på følgende måde: til problemet skrevet i standardformuleringen

yderligere tilføjes balancevariabler, hvis antal svarer til antallet af ulighedsbegrænsninger m (begrænsninger for ikke-negativiteten af værdierne af de ukendte er ikke taget i betragtning). Herefter bliver uligheder med tegnet "≤" til ligheder, for eksempel et system af begrænsninger af formen

2*x 1 +3*x 2 ≤20
3*x 1 +x 2 ≤15
4*x 1 ≤16
3*x 2 ≤12
x 1, x 2 ≥0

vil tage formen

2*x1 +3*x2 +x3 =20
3*x1 +x2 +x4 =15
4*x 1 +x 5 =16
3*x2 +x6 =12
x 1, x 2,..., x 6 ≥0

Det vil sige, at den "økonomiske" betydning af balancevariabler er meget enkel - disse er "resterne" af ubrugte ressourcer af hver type.

Hvis i oprindelige problem ikke minimum, men maksimum blev søgt, vil objektivfunktionen Z blive erstattet af Z 1 = -Z. Løsningerne på problemerne falder sammen, med min Z = - max Z 1 . For eksempel mål

Z(x 1,x 2)=2*x 1 +5*x 2 (maks.)

omskrevet som

Z 1 (x 1, x 2)=-2*x 1-5*x 2 (min.)

Hvis det oprindelige problem havde ulighedsligninger med fortegn "≥" i stedet for "≤", multipliceres begge sider af hver sådan ulighed med -1, og fortegnet for uligheden vendes f.eks.

3*x 1 +x 2 +x 4 ≥15

bliver til

3*x 1 -x 2 -x 4 ≤15

Modellens kanoniske form opnås, og for den skriver vi simplex bord:

Grundvariabler (BP) er skrevet i venstre kolonne, hvis de endnu ikke er valgt, er den tom.

2. Ved hjælp af Jordan–Gauss-trinene søges den indledende referenceplan, dvs. SLAE er reduceret til sin grundlæggende form med ikke-negative frie termer b i >0. I dette tilfælde skal objektivfunktionen Z kun udtrykkes i form af frie ukendte (nulkoefficienter i Z-rækken er kun under variablerne x i, der er i basis). Når vi vælger det løsende element a r,s, skriver vi variablen x s ned i række r i BP-kolonnen; hvis der allerede var en variabel der, streger vi den ud (vi fjerner den fra basis).

3. Vi skriver referenceplanen X * ned under kolonnerne x i: under de frie variable - nuller, under grundvariablene - koefficienterne fra kolonne b svarende til grundvariablen.

Nedenfor udskriver vi vektoren R efter reglen: under de grundlæggende variable er der nuller, under de frie R i =Z i.

Hvis alle R i ≥0, findes den optimale løsning X * og målværdien Z min = -q, ellers skal vi ny plan, har du det, kammerat Zhyukov? (paragraf 4).

4. For at vælge opløsningskolonnen s skal du vælge den maksimale absolutte negative komponent af vektoren R, opløsningskolonne s vælges. Derefter analyserer vi koefficienterne for den s. kolonne i matrixen af begrænsningssystemet. Hvis alle a i,s ≤0, er der ingen løsning, og Z min har en tendens til minus uendeligt, ellers gå til trin 5.

5. For at vælge en opløsende streng r, komponerer vi ikke-negative relationer b i /A i,s ≥0, i=1,2,...,m, og vælger den mindste blandt dem. Hvis minimum er nået for flere linjer, kan enhver af dem opfattes som løsende, og i den nye referenceplan vil værdierne af nogle grundvariable blive lig med 0, det vil sige, at vi får en degenereret referenceplan.

6. Vi udfører Jordan-Gauss-transformationen med opløsningselementet a r,s og går til trin 3

Geometrisk svarer simpleksmetoden til den korteste gennemløb af hjørnerne af et n-dimensionelt konveks polyeder, der danner et område tilladte løsninger opgaver:

Her er vi gået fra referenceplanen C, som er et af hjørnerne i en flerdimensionel polygon, til optimal plan E=X * .

Det er ikke nemt at programmere alt dette i Excel, men det er muligt. Det vedhæftede dokument giver 3 eksempler, der implementerer løsningen af problemer ved hjælp af simpleksmetoden. Sandt nok, når du udfører trinnet, bliver du allerede nødt til at ændre 3 formler; på arket med det første eksempel for simpleksmetoden er de fremhævet med gult: beregning af relationerne til valg af den løsende række i celle I2, udfyld BP-kolonnen i celle A12, trinnet i Jordan-Gauss-transformationen i celle B12. Som i eksemplet med Jordan-Gauss-transformationen er ændring af formlerne kun forbundet med behovet for at henvise til ny linje, der indeholder adressen på cellen med aktiveringselementet (for det første trin - celle C9).