5 Dualitet i lineær programmering 83

5.1 Dualitetsbegrebet 83

5.2 Økonomisk fortolkning af det dobbelte problem 87

5.3 Første dualitetssætning 88

5.4 Anden dualitetssætning 90

5.5 Tredje dualitetssætning 92

5.6 Eksempel på løsning af relaterede problemer 96

5.6.1 Problem dobbelt til diætproblemet 96

5.6.2 Tilfredsstillelse af hoveddualitetssætningen 97

5.6.3 Udførelse af ligevægtssætning 99

5.6.4 Udførelse af estimeringssætningen 99

5.7 Spørgsmål og øvelser 106

5 Dualitet i lineær programmering

5.1 Begrebet dualitet

Lad os overveje lineære programmeringsproblemer i standardform, skrevet i matrixform:

hvor С = (с1...сn), X = , B = , A =

,

hvor Y= (y 1 . . . y m).

Her er X, Y variabler *; A, B, C er konstanter.

Opgave (21) og ethvert lineært programmeringsproblem svarende til det kaldes dobbelt problem (20) og ethvert tilsvarende problem.

Vi lægger vægt på, at der indføres præcis lige så mange nye variable, som der er begrænsninger i problemstilling (20), dvs. m.

Da ethvert lineært programmeringsproblem kan skrives i standardform, giver denne definition os mulighed for at konstruere et dobbelt problem for ethvert lineært programmeringsproblem.

Det oprindelige problem, som det dobbelte problem er konstrueret til, kaldes nogle gange også for det direkte problem.

Sætning(om relaterede problemer). Problemet dual til dual svarer til det originale.

Bevis. Lad os konstruere et lineært programmeringsproblem dual til (21). Da definitionen gør det muligt kun at konstruere et dobbelt problem for en opgave i samme notationsform som opgave (20), transformerer vi først opgave (21), så dens notationsform er den samme.

Lad os reducere problem (21) til standardform til det maksimale:

Vi transponerer mængderne inkluderet her, så rækkefølgen af ​​operationer på vektorer og matricer er den samme som i opgave (20):

max -B T Y T

Nu kan vi konstruere et dobbelt problem i overensstemmelse med den formulerede definition. Lad os introducere en række variable Z.

Denne opgave er dobbelt til dobbelt. Lad os forvandle det.

Dette problem svarer til opgave (20) op til notation.

Sætningen er blevet bevist.

Dualiteten er således gensidig. Et par gensidigt dobbelte problemer kaldes et par relaterede opgaver.

Overvej problemet i kanonisk form. For at konstruere et problem dual til det, transformerer vi det til standardform.

Lad os nu konstruere et dobbelt problem. Bemærk, at antallet af begrænsninger i problemet er fordoblet (hver ligning er transformeret til to uligheder). Vi vil opdele rækkevektoren af ​​variabler i det dobbelte problem i to dele, som hver vil omfatte et lige antal variabler, og betegne det (U,V) = (u 1, …,u m,v 1, …,v m ).

I dette tilfælde, i alle lineære udtryk, kan komponenterne af vektor B og matrix A tages ud af parentes, og forskellen mellem vektorerne U = (u 1, ..., u m) og V = (v 1, . .., v m) forbliver i parentes. For eksempel, når du multiplicerer en række variable med den første kolonne i matrix A, vil resultatet være: (a 11 u 1 +a 21 u 2 + ...+ a m1 u m - a 11 v 1 - a 21 v 2 - ... - a m1 v m = a 11 ( u 1 - v 1) + a 21 (u 2 - v 2) + ... + a m1 (um - v m); - osv.

Lad os betegne U - V = Y. I dette tilfælde er variablerne Y = (u 1 -v 1 ; …;u m –v m) = = (y 1 . . .y m) ikke begrænset i fortegn. Så vil det dobbelte problem have formen:

Så begrænsningsligningerne er forbundet med variabler, der ikke er begrænset i fortegn. Da dualitet er reciprok, kan vi sige, at variable, der er ubegrænsede i fortegn, bør være forbundet med begrænsningerne for en ligning snarere end en ulighed.

Baseret på ovenstående ræsonnement kan vi konkludere, at for at konstruere et dobbelt problem, er det ikke nødvendigt at reducere det lineære programmeringsproblem til standardformen hver gang, nemlig at der ikke er behov for at transformere ligninger til uligheder og ikke variabler. begrænset i fortegn til ikke-negative. Lad de første m`-begrænsninger i en opgave i blandet form være ligninger, og de resterende m-m` være uligheder; og de første n`-variabler er ikke-negative, og de resterende n-n`-variabler kan have et hvilket som helst fortegn. Følgende overensstemmelse kan etableres mellem det lineære programmeringsproblem i blandet form og dets dobbelte lineære programmeringsproblem:

max c j x j	min b i y i
a ij x j = bi,	a ij y i c j ,
a ij x j b i,	a ij y i = c j ,
x j 0,	y i 0,
x j 0,	y i 0,

Lad os formulere en række regler for at konstruere et dobbelt problem:

a) Variablerne i det dobbelte problem svarer til det oprindelige problems begrænsninger, og begrænsningerne svarer til variablerne.

b) Hvis det oprindelige lineære programmeringsproblem er sat til et maksimum, så er det dobbelte konstrueret til et minimum og omvendt.

c) I et lineært programmeringsproblem skal ulighedsbegrænsningerne indeholde tegnet  for maksimum og - for minimum.

d) Ulighedsbegrænsningerne for det oprindelige problem svarer til ikke-negative dobbeltvariable, og ligningerne svarer til variable, der ikke er begrænset i fortegn.

e) De ikke-negative variabler i det oprindelige problem svarer til ulighedsbegrænsningerne for det dobbelte problem, og de ligninger, der ikke er begrænset af fortegn, svarer til dem.

Hvis begge relaterede problemer er skrevet i standardform, kaldes de symmetrisk koblede problemer.

Lad os for eksempel konstruere et problem dual til følgende problem:

min 2x 1 + 3x 2 - 4x 3 + x 5

4x 1 - 3x 2 - x 3 + x 4 + x 5 10

x 1 + 4x 2 + x 3 + x 5 = 15

2x 1 - 4x 2 - x 3 + x 4 3

Da problemet er et minimum, multiplicerer vi begge sider af den første begrænsning med -1 for at få ulighedstegnet : -4x 1 + 3x 2 + x 3 - x 4 - x 5  -10.

Da det direkte problem har tre begrænsninger på fem variable, vil det dobbelte problem involvere fem begrænsninger på tre variable.

Den objektive funktion af det dobbelte problem er maksimeret, da det direkte problem er sat til et minimum. Koefficienterne for den objektive funktion af det dobbelte problem repræsenterer det direkte problems frie vilkår.

Den første begrænsning af det dobbelte problem svarer til variablen x 1 af det direkte problem, så koefficienterne for denne begrænsning er taget fra kolonnen med koefficienter for x 1, og det frie led er taget fra den objektive funktion af det direkte problem. Siden x 1 0 er denne begrænsning en ulighed. Da det dobbelte problem er et maksimum, er ulighedstegnet . Den anden, tredje og femte begrænsning er konstrueret på samme måde. Den fjerde begrænsning svarer til variablen x 4, hvis fortegn kan være et hvilket som helst. Derfor er det en ligning.

Variablerne y 1 og y 3 svarer til den første og tredje begrænsning af det fremadrettede problem, som er uligheder. Derfor er disse variabler ikke-negative. Den anden begrænsning af det direkte problem er en ligning, så variablen y 2 er ikke begrænset i fortegn.

max -10 år 1 + 15 år 2 + 3 år 3

4y 1 + y 2 + 2y 3  2

3y 1 + 4y 2 - 4y 3  3

1.6.1. Konceptet med et dobbelt LP-problem. Lad KZLP (1.7) blive givet. Hvis den objektive funktion f(x) = cx når sin maksimale værdi på sættet D, så virker spørgsmålet om, hvordan man kan konstruere en øvre grænse for det, rimeligt. Selvfølgelig, hvis igennem Og udpege nogle m-dimensionel vektor altså

Lad os lade som om Og kan vælges på en sådan måde, at iA ≥ s. Så for evt x≥ 0 uligheden er gyldig

ivrig efter at få bedste skøn(1.47), kommer vi til formuleringen af ​​et nyt ekstremt problem, som i en eller anden forstand er logisk konjugeret med problem (1.7) kaldes dobbelt. Lad os tage forbehold for, at ovenstående betragtninger ikke er af streng karakter og kun har til formål at forberede læseren på den formelle definition af det dobbelte lineære programmeringsproblem, der er givet nedenfor.

F Hvis der er givet et kanonisk LP-problem

så LP problemet

hedder dobbelti forhold til hende. Derfor er opgaven (D, f) intet forhold til

(D*,f*) hedder lige (eller original).

1.6.2. Generel ordning konstruere et dobbelt problem. Ovenstående definition af et problem dobbelt til en kanonisk ZLP kan udvides til tilfældet med et generelt lineært programmeringsproblem.

F Hvis der er givet et generelt LP-problem

f(x) = c 1 x 1 + ... + c j x j + c j +1 x j+ 1 + ... + med n x n → max, xÎ D, (1.50)

hvor D er bestemt af systemet af ligninger og uligheder:

Atdobbelti forhold til det kaldes det generelle LP-problem

hvor D* er bestemt af systemet af ligninger og uligheder:

Reglerne for at konstruere en problemdual med hensyn til OPLP er tydeligt repræsenteret af diagrammet vist i ris. 1.9.

Som følger af ovenstående diagram, når du går fra et direkte LP-problem til et dobbelt problem:

1. Typen af ​​optimum ændres til det modsatte, dvs. maksimum til minimum, og omvendt.

2. Vektor af koefficienter for den objektive funktion Med og restriktioner kolonne b skifte plads.

3. Problembegrænsningsmatrix EN omsat.

4. Sættet af indekser af variabler, som ikke-negativitetsbetingelsen er pålagt i det direkte problem (f.eks. x j≥ 0 eller u j≥ 0), bestemme antallet af begrænsninger, der har form af uligheder i det dobbelte problem ( a j u ≥ med j eller en i x ≤ b j).

5. Et sæt af antal restriktioner, der har form af uligheder i det direkte problem (f.eks. en i x ≤ b j eller a j u ≥ med j) Bestem det sæt af indekser af variable, som ikke-negativitetsbetingelsen er pålagt i det dobbelte problem ( u i≥ 0 eller x i ≥ 0).

F F En vigtig egenskab følger af ovenstående definition - symmetrien af ​​dualitetsrelationen, dvs. problemet dual til dual falder sammen med det direkte (oprindelige) problem:

Derfor giver det mening at tale om et par indbyrdes dobbelte problemer.

I matrixform kan et par dobbelte generelle lineære programmeringsproblemer skrives kortfattet som:

Lad os overveje processen med at konstruere et dobbelt problem på konkret eksempel. Lad OLP blive givet ( D, f):

så vil dets dobbelte problem være ( D*, f*):

1.6.3. Dualitetsteoremer og deres anvendelser. De grundlæggende egenskaber, som dobbelt lineære programmeringsproblemer har, kan formuleres som følgende udsagn. De kaldes normalt dualitetssætninger.

Bevis.

Det er nok at bevise sætningen for tilfældet, når problemet ( D, f) er kanonisk. Lad os overveje et par dobbelte problemer

Fra hvad vektoren Og er en gyldig opgaveplan ( D*, f*), følger det iA ≥Med. Multiplicer venstre og højre side af denne ulighed med vektoren x≥ 0, får vi et ækvivalent system af uligheder

På samme tid, for vektoren x, som er en tilladt plan for problemet ( D, f), er ligestillingen sand Ax=b. Dette beviser det иb ≥ сх. EN

Kommentar. Sætning 1.4 gælder selvfølgelig også for optimale planer for gensidigt dobbelte problemer: f(x*) ≤ f*(u*), Hvor X* Og u*- eventuelle optimale opgaveplaner ( D, f) Og ( D*,f*). Faktisk, som det vil fremgå nedenfor, ligestillingen f(x*) = f*(u*).

Bevis.

Ifølge sætning 1.4, for alle tilladte planer x opgaver ( D, f) uligheden er sand cx < b. Ifølge sætningens betingelser f()=f() eller hvad er det samme, c = b. Derfor er følgende udsagn sandt: for enhver x О D c > cx, dvs. x er den optimale plan for problemet ( D, f).

Begrundelse, der beviser planens optimalitet til opgave ( D*,f*), udføres på samme måde. EN

Bevis.

Hvis vi antager, at det dobbelte problem ( D*,f*) der er mindst én gyldig plan Og, derefter, ifølge sætning 1.4, for enhver tilladt plan x opgaver ( D, f) uligheden er sand f(x) ≤ f*( ) <+∞. Последнее означает, что целевая функция f opgaver ( D, f) er begrænset fra oven. Da dette er i modstrid med betingelserne for teoremet, vil antagelsen om eksistensen af ​​tilladte planer for det dobbelte problem ( D*,f*) er forkert. EN

Følgende erklæring, kendt som ligevægtssætning, bruges til at kontrollere optimaliteten af ​​ansøgernes planer.

Bevis.

Vektorer X* Og Og*, er tilladte planer for de tilsvarende opgaver, opfylder betingelserne: Axe* = b, x* > 0 og u*A-c ≥ 0. Lad os finde det skalære produkt

Ifølge bemærkningen til sætning 1.2 falder de optimale værdier af de objektive funktioner af gensidigt dobbelte problemer sammen, dvs. . u*b=сх*. Det sidste betyder det (u*A-c)x*= 0 . Imidlertid kan skalarproduktet af to ikke-negative vektorer kun være nul, hvis alle parvise produkter af deres tilsvarende koordinater er nul. Derfor, hvis x j *> 0, så u*a j – med j= 0, hvis x j= 0, så er det muligt u*a j – med j≥ 0, hvilket er det, der står i sætningen. EN

Den praktiske betydning af dualitetssætninger er, at de gør det muligt at erstatte processen med at løse hovedproblemet med at løse det dobbelte, som i visse tilfælde kan vise sig at være enklere. For eksempel et problem, hvis rækkevidde af tilladte værdier er beskrevet af to ligninger, der forbinder seks variable ( m = 2, n= 6), kan ikke løses grafisk metode. Imidlertid denne metode kan bruges til at løse sit dobbelte problem, som kun har to variabler.

Lad os gå tilbage til bordet igen T 2 (q) (ris. 1.8), opnået ved den endelige iteration af proceduren modificeret simpleksmetode. Lad os se nærmere på nulrækken i matricen Δ -1 (β ( q)), for hvilken betegnelsen δ 0 (β ( q)). Det kan skrives element for element i følgende form:

Lad os introducere vektoren = (δ 0,1 (β ( q)), δ 0,2 (β ( q)),..., δ 0, m (β ( q))). Det er nemt at kontrollere, at vurderingslinjen -en 0 (β ( q)) kan repræsenteres som følger:

Ifølge optimalitetskriteriet, ved sidste iteration givet linje er ikke-negativ, dvs. ũА≥с. Derfor er vektoren et tilladeligt design af det dobbelte problem.

Samtidig elementet b 0 (β ( q)), der indeholder den aktuelle værdi af objektivfunktionen og lig med ved sidste iteration f(x*), indrømmer repræsentation

Ifølge sætning 1.5 fra ligestillingen f(X*) = f*(ũ ) følger det, at vektoren ũ fungerer som en optimal plan for det dobbelte problem: u = ũ.

Endelig kan vi sige det for det optimale grundlag

F F En væsentlig fordel ved den modificerede simplex-metode er således, at den giver dig mulighed for samtidig at finde optimale planer for både direkte og dobbelte problemer.

Til læseren som selvstændig øvelse det foreslås at konstruere et problem dual til (1.34)-(1.35), hvis løsning blev givet i afsnit 1.5.2, og sikre, at vektoren u= (-10, 32, 2) opnået i tabellen T 2, stk. 3, er en acceptabel og optimal plan for det.

1.6.4. Økonomisk fortolkning. Traditionel økonomisk fortolkning dual problem LP er baseret på modellen enkleste opgave produktions planlægning beskrevet i indledningen. Lad os minde dig om, at i det hver ( j th) vektorelement x betragtes som en plan for produktion af produkter af en given type i naturlige enheder, med j- pris per stk j-den slags, en j- vektor, der bestemmer teknologien til at bruge tilgængelig m ressourcer til at producere en outputenhed j-den slags, b- vektor af restriktioner på mængden af ​​disse ressourcer.

Lad os antage det for nogle værdier A, b Og Med optimal plan fundet X*, maksimering af den samlede indkomst max( cx}=cx*. Spørgsmålet virker ganske naturligt: ​​hvordan vil den optimale plan ændre sig? x* ved ændring af komponenterne i begrænsningsvektoren b og i særdeleshed under hvilke variationer b optimal plan x* vil forblive uændret? Denne opgave fik navnet bæredygtighedsspørgsmål optimal plan. Det er indlysende, at bæredygtighedsforskning x* har direkte praktisk betydning, da mængderne i reel produktion tilgængelige ressourcer b i; kan svinge betydeligt efter at have truffet en planlægningsbeslutning x*.

Når begrænsningsvektoren bændres til Δ b eller, som de også siger, modtager en stigning Δ b, så opstår der tilsvarende variationer for den optimale plan x*(b+Δ b) og værdierne af den objektive funktion f( x*(b+Δ b)). Lad os sige stigningen Δ b er sådan, at det ikke fører til en ændring af problemets optimale grundlag, dvs. x*(b+Δ b)≥0. Lad os definere funktionen F(b), vender tilbage optimal værdi objektiv funktion af problemet ( D(b), f) Til forskellige betydninger begrænsningsvektorer b

Lad os overveje forholdet mellem dets stigning F(b+Δ b)-F(b) til argumenttilvæksten Δ b. Hvis for nogle jeg direkte Δ b i→ 0, så får vi

I betragtning af, at i overensstemmelse med sætning 1.5

og erstatter (1.57) i (1.56), når vi frem til udtrykket

F F Af formel (1.58) følger økonomisk fortolkning af optimale variabler af det dobbelte problem. Hvert element du i * kan betragtes som en marginal (øjeblikkelig) vurdering af bidraget jeg ressource til den samlede indkomst F med optimal løsning x*. Groft sagt er værdien af ​​u i * lig med den stigning i indkomsten, der opstår, når ressource i stiger med én, under forudsætning af optimal udnyttelse af ressourcerne.

I forskellige kilder kaldes komponenterne i det optimale design af dobbeltproblemet også dobbelte vurderinger eller skyggepriser, og L.V. Kantorovich foreslog et sådant udtryk som objektivt fastlagte vurderinger.

Baseret på dualitetssætninger for et par LP-opgaver i generel form Nogle vigtige (ud fra et økonomisk fortolkningssynspunkt) konsekvenser kan formuleres.

F F Hvis, når man bruger den optimale plan for det direkte problem, dvs., begrænsningen er opfyldt som en streng ulighed, så er den optimale værdi af den tilsvarende dobbelte variabel lig med nul, dvs. Hvis

Inden for rammerne af det undersøgte produktionsplanlægningsproblem betyder dette, at hvis en eller anden ressource b i, er tilgængelig i overskud (ikke fuldt ud brugt ved implementering af den optimale plan), så jeg-e begrænsningen bliver uvigtig, og værdien af ​​en sådan ressource er 0.

F F Hvis, når du bruger det optimale design af det dobbelte problem j-e begrænsning er opfyldt som en streng ulighed, så skal den optimale værdi af den tilsvarende variabel i det direkte problem være lig med nul, dvs. 1, j u 1 * +...og m, j og m – med j > 0, så x j * = 0.

I betragtning af det økonomiske indhold af dobbeltvurderinger u 1 *,...,u m, udtryk EN 1, j u 1 * +…a m , j u m * kan tolkes som enhedsomkostninger vedr j th teknologisk proces. Derfor, hvis disse omkostninger overstiger fortjenesten ved salg af en enhed j-th produkt, derefter produktion j-th produkt er urentabelt og bør ikke være til stede i det optimale produktionsplan (x j * =0).

På trods af de mulige analogier, der kan opstå for læsere, der er fortrolige med sådanne grundlæggende begreber økonomisk teori, ligesom marginalomkostninger og marginalindtægter, bør dobbelte værdiansættelser ikke entydigt identificeres med priser (selvom sådanne forsøg nogle gange er blevet gjort i indledende fase etablering af operationsforskning som videnskab). Lad os understrege det endnu en gang Variablerne for den dobbelte opgave i deres betydning er estimater af den potentielle mulighed for at opnå yderligere profit ved at øge den tilsvarende ressource under betingelser for optimal funktion af det administrerede økonomiske objekt.

1.6.5. Analyse af parametrisk stabilitet af PLP-løsninger. I det foregående afsnit berørte vi nogle aspekter af den optimale plans følsomhed og stabilitet med hensyn til ændringer i begrænsningsvektoren b. Naturligvis kan lignende spørgsmål stilles i tilfælde af variation af koefficienterne for den objektive funktion med j,jО1: n.

Fra et økonomisk fortolkningssynspunkt kan problemet med at studere parametrisk stabilitet betragtes som at studere grænserne for prisudsving for produkterne fra en administreret virksomhed (virksomhed), hvor den vedtagne produktionsplan fortsat forbliver optimal.

Også indholdet af problemet med stabilitet af den optimale ZLP-plan med hensyn til variationer af den objektive funktion kan illustreres ved hjælp af den første geometriske fortolkning. På ris. 1.10 viser sæt af gennemførlige planer D noget LP-problem. Som det kan ses af figuren, er den objektive funktion f(dens adfærd afspejles af niveaulinjen vist med fed stiplet linje) når en ekstrem værdi på punktet x*, og ændringen i dens koefficienter fra Med Til Med" eller Med" i figuren svarer til drejningen af ​​niveaulinjen i forhold til x*. Aktiv, dvs. bliver til ligestilling, begrænsninger på det punkt x* svarer til linje (1) og (2). Indtil, når drejning forårsaget af en ændring i vektor Med, niveaulinjen for objektivfunktionen går ikke ud over keglen dannet af begrænsningslinjerne, X* forbliver den optimale plan. Som vist i ris. 1.10, denne plan ændres ikke, når man flytter fra Med Til Med", og omvendt, når man går fra Med Til Med" objektiv funktionsniveaulinje f(x)=c"x vil krydse linje (2), hvilket vil forårsage en ændring i den optimale basislinje, som nu vil være punktet .

Brug af optimalitetsbetingelserne for ZLP-planen

Det er ikke svært at opnå kvantitative estimater for grænserne for udsving i koefficienterne for den objektive funktion, hvor den optimale plan ikke ændres. Lad os sige, at et element har gennemgået variation med r: med r′ = med r + ε r. Der er to mulige tilfælde:

1. Kolonne r er ikke inkluderet i det optimale grundlag ( rÎ N(β ( q))). Så, for at den optimale plan forbliver uændret, er det nødvendigt og tilstrækkeligt at opfylde betingelsen

Herfra kan du få værdien for den tilladte variation

2. Kolonne r er inkluderet i det optimale grundlag ( rÎ N(β ( q))). I dette tilfælde, for at holde den nuværende plan optimal, ville det være nødvendigt at udføre på alle ikke-baserede kolonner ( j Ï N(β ( q))) betingelser

Derfor skal den tilladte variation i dette tilfælde opfylde betingelserne

Det givne eksempel på at studere følsomheden af ​​den optimale plan med hensyn til ændringer i problemets parametre er meget enkelt. Det er klart, at der er flere komplekse opgaver, hvori f.eks. fælles variationer af parametre studeres forskellige typer. De er genstand for en særlig gren af ​​operationsforskning kaldet parametrisk programmering. Den interesserede læser kan få yderligere information om dette emne på.

Introduktion
Et dobbelt problem forstås som et lineært hjælpeprogrammeringsproblem, formuleret ved hjælp af visse regler direkte fra betingelserne for det direkte problem. Interessen for at bestemme den optimale løsning på et direkte problem ved at løse dets dobbelte problem skyldes, at beregninger ved løsning af et fjerntliggende problem kan vise sig at være mindre komplekse. Kompleksiteten af ​​beregninger hvornår OPP's beslutning afhænger mere af antallet af begrænsninger frem for antallet af variable.
Formålet med kursusprojektet er at studere litteraturen om det valgte emne og lære i praksis at anvende simpleksmetoden til løsning af direkte og dobbelt lineære programmeringsproblemer, samt løsning af dobbelt lineære programmeringsopgaver ved hjælp af MS Excel.
Kursusprojektet består af en introduktion, to kapitler og en konklusion.
Det første kapitel diskuterer de grundlæggende begreber og forslag fra ZLP's dualitetsteori, typer af matematiske modeller af dobbelte problemer og deres økonomiske fortolkning.
Det andet kapitel diskuterer løsningen af ​​et dobbelt problem ved hjælp af MS Excel.

1. Dualitet i lineær programmering
1.1 Direkte og dobbelt lineære programmeringsproblemer
Fra et økonomisk synspunkt kan det dobbelte problem fortolkes som følger: hvad skal enhedsprisen for hver ressource være for at minimere de samlede omkostninger ved givne mængder ressourcer b i og enhedsomkostningsværdier C j? Og vi definerer det indledende problem som følger: hvor mange og hvilken slags produkter x j (j = 1,2,..., n) skal produceres, så der ved givne omkostninger C j (j = 1,2,.. ., n) produktionsenheder og størrelsen af ​​tilgængelige ressourcer b i (i =1,2,…, n) maksimerer output i værdi. De fleste lineære programmeringsproblemer er oprindeligt defineret som originale eller dobbelte problemer. Efter at have lavet en konklusion, kan vi tale om et par dobbelte lineære programmeringsproblemer.
Hvert lineært programmeringsproblem kan på en bestemt måde forbindes med et andet problem (lineær programmering), kaldet dobbelt eller konjugere med hensyn til det oprindelige eller direkte problem. Lad os definere det dobbelte problem mhp generelt lineært programmeringsproblem, der, som vi allerede ved, består i at finde den maksimale værdi af funktionen:
F=c 1 x 1 + c 2 x 2 +…c n x n
under forhold

Ved at sammenligne de to formulerede problemer ser vi, at det dobbelte problem er sammensat efter følgende regler:
1. Den objektive funktion af det oprindelige problem er sat til det maksimale, og den objektive funktion af det dobbelte problem er sat til et minimum.
2. Matrix

sammensat af koefficienter for ukendte begrænsninger i systemet med det oprindelige problem og en lignende matrix

i et dobbelt problem opnås de fra hinanden ved transponering (dvs. udskiftning af rækker med kolonner og kolonner med rækker).
3. Antallet af variable i det dobbelte problem er lig med antallet af restriktioner i det oprindelige problems system, og antallet af restriktioner i systemet for det dobbelte problem er lig med antallet af variable i det oprindelige problem.
4. Koefficienterne for de ukendte i det dobbelte problems objektive funktion er de frie led i det oprindelige problems system, og højresiden i relationerne til systemet for det dobbelte problem er koefficienterne for de ukendte i den objektive funktion af det oprindelige problem.
5. Hvis variablen x j af det oprindelige problem kan kun tage positive værdier, så j Den th betingelse i det dobbelte problemsystem er en ulighed af formen ">". Hvis variablen x j kan tage både positive og negative værdier, så 1 – forholdet i systemet er en ligning. Lignende forbindelser finder sted mellem det oprindelige problems begrænsninger og det dobbelte problems variable. Hvis jeg – forholdet i systemet af det oprindelige problem er altså en ulighed jeg-th variabel i det dobbelte problem . Ellers variablen y j kan tage både positive og negative værdier.
Dobbelt par problemer er normalt opdelt i symmetriske og asymmetriske. I et symmetrisk par af dobbelte problemer er begrænsningerne for det direkte problem og relationerne til det dobbelte problem uligheder af formen " ". Således kan variablerne for begge problemer kun tage ikke-negative værdier.
Det dobbelte problem er tæt forbundet med det lineære programmeringsproblem. Den indledende opgave kaldes den indledende. Løsningen på det dobbelte problem kan fås fra løsningen på det oprindelige problem og omvendt. Forbindelsen mellem disse to problemer er koefficienterne Cj for funktionen af ​​det oprindelige problem. Disse koefficienter kaldes frie termer af systemet af begrænsninger for det dobbelte problem. Koefficienterne Bi for systemet af begrænsninger for det oprindelige problem kaldes koefficienterne for det dobbelte problem. Den transponerede matrix af koefficienter for begrænsningssystemet for det oprindelige problem er matrixen af ​​koefficienter for begrænsningssystemet for det dobbelte problem.
Overvej ressourceudnyttelsesproblemet. Virksomheden har t typer ressourcer i mængden af ​​b i (i=1, 2,..., m) enheder, hvoraf n typer produkter produceres. Til produktion af 1 enhed. i-th produkter a ij enheder er brugt. t-te ressource, dens omkostninger er C j enheder. Det er nødvendigt at fastlægge en produktionsplan, der sikrer dens maksimale output i værdi. Lad os tage x j (j=1,2,..., n) for at være antallet af enheder. j-th produkter er maksimal værdi lineær funktion
Z=C 1 x 1 + C 2 x 2 + … + C n x n

Lad os bestemme de ressourcer, der kræves for at fremstille produktet. Lad os betegne ressourceomkostningsenheden som omkostningsenheden for de producerede varer. Og gennem y i (j=1,2,..., m) prisen på en enhed af den i-te ressource. De der. prisen på alle brugte ressourcer, der bruges til at opfinde en enhed jth produkter, udgør. Prisen på de forbrugte ressourcer bør ikke overstige prisen på det endelige produkt.
1.2 Grundlæggende om dualitetssætningen
1.2.1. Asymmetriske dobbeltproblemer

Dualitetssætning:

Systemet af begrænsninger af det oprindelige problem i asymmetriske dobbeltproblemer defineres som lighed. Det dobbelte problem er angivet som en ulighed, og variablerne kan også være negative. For at gøre det lettere at forstå problemformuleringen vil vi fortolke det i matrixform.
Lad os formulere et dobbelt problem. Det er nødvendigt at definere en rækkematrix Y=(y 1 , y 2 ,…, y m), som maksimerer lineær funktion f=YA 0 og opfylder begrænsningerne
YA>C (1,1)
Lad os formulere det indledende problem. Definer en kolonnematrix X=(x 1, x 2,…, x n), som minimerer den lineære funktion Z=СХ og. opfylder begrænsningerne
AX=A0,Х>0 (1,2)
Både i de originale og i de dobbelte problemer er A = (a ij) matrixen af ​​koefficienter for systemet af begrænsninger, A 0 = (b 1, b 2,..., b m) er en søjlematrix, C = (c 1, c 2,..., c n) – rækkematrix. Dualitetssætningen etablerer en sammenhæng mellem de optimale planer for et par dobbelte problemer.
Dualitetssætningen siger: hvis den ene af et par af dobbeltopgaver har en optimal plan, så har den anden også en løsning, og for ekstreme værdier af lineære funktioner gælder forholdet minZ = maxf. Hvis den lineære funktion af et af problemerne er ubegrænset, så har den anden ingen løsning
Bevis.
Vi vil antage, at det oprindelige problem har en optimal plan. Planen blev fastlagt ved hjælp af simpleksmetoden. Vi kan antage, at det endelige grundlag består af de første m vektorer A 1, A 2,..., A m.
Vi antager, at D er en matrix sammensat af komponenter af de endelige basisvektorer A 1, A 2., A m Ovenstående tabel består af ekspansionskoefficienterne for vektorerne A 1, A 2,..., A n originalt system ved basisvektorer. I denne tabel svarer hver vektor A j til en vektor X j.
Ved at bruge relationer (1.3) og (1.4) får vi:
(1,5) A=D, D-1A=
(1,6) Ao=DX*; D-1A0=X
(1,7) min Z= C*X*,
(1,8) = C* – C > 0,
hvor С=(C1, C2,..., Cm), С=(C1, C2,..., Cm, Cm+1,..., Cn), a=(CX1-C1; СХ 2 – С 2, …, CX n –C n)=(Z 1 –С; Z 2 -C 2 ;…, Z n –C n) – en vektor, hvis komponenter er ikke-positive, da de falder sammen med Z j – C j >0, svarende til den optimale plan.
Den optimale plan for det oprindelige problem har formen X = D -1 A 0, så vi leder efter den optimale plan for dobbeltproblemet i formularen
(1,9) Y = C*D-1
Lad os vise, at Y* faktisk er planen for det dobbelte problem. For denne begrænsning skriver vi (1.2) som uligheden YA-C>0, i venstre side af hvilken vi erstatter Y*. Så får vi baseret på (1.9), (1.5) og (1.8).
YA–C=C*D -1 A–C=C-C>0, hvorfra vi finder Y*A>C
Da Y* opfylder begrænsninger (1.2), er dette planen for det dobbelte problem. Med denne plan er værdien af ​​den lineære funktion af det dobbelte problem f(Y)=Y*A 0. Under hensyntagen til relationer (1.9), (1.6) og (1.7), har vi
(1,10) f (Y) = Y*A 0 =C * D -1 A 0 = C*X = minZ(X)
Værdien af ​​den lineære funktion af det dobbelte problem på Y er således numerisk lig minimumsværdi lineær funktion af det oprindelige problem
Lad os nu bevise, at Y* er den optimale plan. Lad os gange (1.1) med en hvilken som helst plan Y af det dobbelte problem, og (1.2) med en hvilken som helst plan X af det oprindelige problem: YAX=YA 0 =f(Y), YAX>СХ=Z(X), det følger at for alle planer X og Y gælder uligheden
(1,11) f(Y)>Z(X)
Det samme forhold relaterer også ekstremværdierne maxf(Y)>minZ(X). Fra den sidste ulighed konkluderer vi, at den maksimale værdi af den lineære funktion kun opnås, hvis maxf(Y)=minZ(X), men denne værdi af f(Y) opnås med plan Y, derfor er plan Y den optimale plan for det dobbelte problem.
På samme måde kan det bevises, at hvis det dobbelte problem har en løsning, så har det originale også en løsning, og forholdet maxf(Y)=minZ(X) gælder
For at bevise anden del af sætningen, lad os antage, at den lineære funktion af det oprindelige problem ikke er afgrænset nedefra. Så af (1.11) følger det, at f(Y) – Y. Dette udtryk er meningsløst, derfor har det dobbelte problem ingen løsninger.
Antag på samme måde, at den lineære funktion af det dobbelte problem ikke er afgrænset ovenfra. Så ud fra (1.11) får vi at Z(X)+Y. Dette udtryk giver heller ingen mening, så det oprindelige problem har ingen løsninger.
Den gennemprøvede sætning gør det muligt, når man løser et af de dobbelte problemer, at finde den optimale plan for den anden. Her rækkematricen C = (0; 1; 0; –1; – 3, 0), kolonnematrix
1 1 2 0 -1 1 0
A 0 = 2 A = 0 -4 1 2 -1 0
3 0 3 0 0 1 1
1 0 0
2 -4 3
A «' = 0 1 0
-1 2 0
1 -1 0
0 0 1
Dobbelt opgave. Find den maksimale værdi af den lineære funktion f=y 1 +2y 2 +5y 3 under restriktioner
y 1 > 0
2y 1 – 4y 2 + 3y 3 > 1,
y 2 > 0,
(-y 1) + 2y 2 >(-1),
y 1 – y 2 + y 3 = -3, y 3 > 0
Den optimale plan for det oprindelige problem er X = (0; 1/3; 0; 11/3; 4; 0), hvorved vi opnår Z min = -46/3. Ved hjælp af denne iteration finder vi den optimale plan for det dobbelte problem. Ifølge dualitetssætningen findes den optimale plan for dobbeltproblemet ud fra relationen Y= C*D -1, hvor matrix D -1 er den inverse matrix af matrixen sammensat af komponenterne af vektorerne inkluderet i den sidste basis , hvor den optimale plan for det oprindelige problem blev opnået. Den sidste basis omfatter vektorerne A5, A4, A2; Midler,
1 -1 2
D = (A5, A4, A2) = -12-4
1 0 3
omvendt matrix D -1 er dannet ud fra koefficienterne i kolonne A 1 , A 3 , A 6 i den fjerde iteration:
2 1 0
D -1 = -1/3 1/3 2/3
-2/3 -1/3 1/3
Fra samme iteration følger C = (–3; –1; 1). Dermed
2 1 0
Y=С*D -1 =(-3; – 1; 1) -1/3 1/3 2/3
-2/3 1/3 1/3
Y=(-19/3; – 11/3; – 1/3),
de der. y i =C*X i, hvor X i er ekspansionskoefficienterne for den sidste iteration, placeret i kolonnerne af vektorerne for den indledende enhedsbasis.
Så, i-th dual variablen kan fås fra værdien af ​​estimatet af den (m+1)-te række modsat den tilsvarende vektor inkluderet i den oprindelige enhedsbasis, hvis den tilsvarende værdi af koefficienten for den lineære funktion tilføjes til den:
y1 = -19/3+0 = -19/3; y2 = -11/3+0 = -11/3; y3 =-1/3+0=-1/3
Med denne plan maxf=-46/3

1.2.2 Symmetriske dobbeltproblemer

En række af dobbelte lineære programmeringsproblemer er dobbeltsymmetriske problemer, hvor systemet af begrænsninger for både de oprindelige og dobbelte problemer er specificeret af uligheder, og betingelsen om ikke-negativitet pålægges de dobbelte variable.
Indledende opgave. Find kolonnematrixen X=(x 1 , x 2 ,…, x n), der opfylder begrænsningssystemet
(1.12). AX>A 0, X>0 og minimerer den lineære funktion Z=CX
Et system af uligheder ved hjælp af yderligere variable kan omdannes til et ligningssystem, derfor kan ethvert par symmetriske dobbelte problemer omdannes til et par asymmetriske, for hvilke dualitetssætningen allerede er blevet bevist.
Ved hjælp af symmetri kan du vælge et problem, der er mere bekvemt at løse. Omfanget af problemet, der løses ved hjælp af en computer, er begrænset af antallet af inkluderede linjer, så et problem, der er ret besværligt i sin oprindelige formulering, kan forenkles i en dobbeltformulering. Når du regner uden hjælp fra maskiner, forenkler brugen af ​​dualitet beregningerne.
For at nedskrive det dobbelte problem er det naturligvis først nødvendigt at reducere systemet af begrænsninger for det oprindelige problem til at danne sig. For at gøre dette skal den anden ulighed ganges med -1.
1.3 Typer af matematiske modeller af dobbelte problemer
Baseret på de betragtede asymmetriske og symmetriske dobbelte problemer bemærker vi, at par af dobbelte problemer af matematiske modeller kan repræsenteres som følger:
· Symmetriske problemer
(1) Oprindeligt problem Dobbelt problem
Z min =CX; fmax =Y>A0;
AX=A 0; YA=С
X>0 Y>0
(2) Oprindeligt problem Dobbelt problem
Zmax =CX; fmin =YA0;
AX=A 0; YA=С
X>0 Y>0
· Asymmetriske problemer
(3) Oprindeligt problem Dobbelt problem
Z min =CX; fmax =YA0;
AX=A 0; YA=С
X>0
(4) Oprindeligt problem Dobbelt problem
Zmax =CX; fmin =YA0;
AX=A 0; YA=С
X>0
Derfor, før du formulerer et dobbelt problem for et givet oprindeligt problem, er det nødvendigt at transformere systemet af begrænsninger for det oprindelige problem korrekt.

1.4 Dobbelt simpleks metode

For at få en løsning på det oprindelige problem kan vi gå videre til det dobbelte. Og ved hjælp af estimater af dens optimale plan, kan vi bestemme optimal løsning original opgave.
Hvis vi betragter den første simplex-tabel med et ekstra enhedsgrundlag, er overgangen til det dobbelte problem ikke nødvendig. Dette skyldes, at det oprindelige problem er defineret i kolonnerne, og det dobbelte problem er defineret i rækkerne.
b i er estimater af den dobbelte problemplan. C j er skøn over planen for det oprindelige problem.
Lad os finde en løsning på det dobbelte problem iflg simplex bord. Simplextabellen indeholder det indledende problem. Vi fastlægger også den optimale plan for det dobbelte problem. Vi finder også den optimale plan for det oprindelige problem.
Denne metode kaldes normalt dual simplex-metoden.
Lad os sige, at du skal bestemme det indledende lineære programmeringsproblem, som stilles i generel form: minimer funktionen Z=СХ med AX=A 0, X>0. Dette betyder, at i det dobbelte problem skal funktionen f=YA 0 maksimeres for YA>C. Lad følgende basis defineres D = (A 1 , A 2 ,..., A i ,..., A m), og i det mindst en af ​​komponenterne i vektoren X = D -1 A 0 = (x 1, x 2 ,..., x i,..., x m) negativ. For alle vektorer A j anvendes følgende relation: Z j –C j >0 (i=1,2,..., n).
Ved at bruge dualitetssætningen er Y=C-baserne D -1 planen for det dobbelte problem. Denne plan er ikke optimal. Fordi estimaterne af den optimale plan for det dobbelte problem skal være ikke-negative, og det valgte grundlag X indeholder en negativ komponent og er ikke planen for det oprindelige problem, men på den anden side.
Derfor er det nødvendigt at udelukke fra grundlaget for det oprindelige problem vektoren A i, som svarer til komponenten x i<0. Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи.
Vi ser gennem den i-te linje for at vælge en vektor, der er inkluderet i grundlaget for den oprindelige opgave. De der. hvis strengen ikke har x ij<0, тогда линейная функция двойственной задачи не ограничена на многограннике решений. Поэтому нет решений исходной задачи.
Ellers definerer vi for kolonner med negative værdier q 0j =min(x i /x ij)>0. Vi finder også den vektor, der svarer til minq 0j (Z j –C j), når den oprindelige opgave løses maksimalt, samt maxq 0j (Z j –C j), når den oprindelige opgave løses til et minimum.
Vi inkluderer den fundne vektor i grundlaget for den oprindelige opgave. Retningslinjen bestemmer den vektor, der skal fjernes fra grundlaget for den oprindelige opgave.

Lad os antage, at q 0j =min(x i /x ij)=0, dvs. x i =0, så vælges x ij som et opløsningselement, men kun når x ij >0.
Denne tilgang til at løse problemet fører ikke til en stigning i antallet af negative komponenter af vektoren X. Indtil X>0 er opnået, stopper processen ikke.
Ved at bestemme den optimale plan for det dobbelte problem, finder vi også den optimale plan for det oprindelige problem.
Brug ved løsning af den dobbelte algoritme simpleks metode betingelsen Z j –C j >0 kan ignoreres, indtil alle x i er udelukket<0.
Den optimale plan bestemmes ved hjælp af den sædvanlige simplex-metode. Denne metode bruges normalt, forudsat at alle x i<0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q 0j =max(x i /x ij)>0.
Lineære programmeringsproblemer kan løses ved hjælp af dual simplex-metoden. Systemer med restriktioner i problemer med et positivt grundlag har frie vilkår for ethvert tegn. Dual simplex-metoden kan betydeligt reducere størrelsen af ​​simplex-tabellen og antallet af transformationer af begrænsningssystemet.

2 . Programudvikling
2.1 Problemstilling
Det er nødvendigt at planlægge syværkstedets arbejde i en vis periode. Der er etableret en liste over fremstillede produkter, og markedsprisen for hvert produkt er kendt. Til at producere produkter bruges ressourcer: materiale, tråde, knapper, skærearbejde, syersker osv. Der er etableret en komplet liste over disse ressourcer og det samlede beløb for hver ressource, der kan bruges i planlægningsperioden. Forbruget af hver ressource pr. enhed af hvert produkt er kendt. Det er nødvendigt at bestemme, hvor meget af hvert produkt, der skal produceres, så den samlede markedspris på alle produkter (output, omsætning) er størst.
Lad os introducere følgende notation:
jeg=1,…, m- antal (indekser) af anvendte ressourcer;
- lager jeg-th ressource, dvs. tilladt strømningshastighed jeg-th ressource i planlægningsperioden; et andet navn er ressourcebegrænsning jeg;
j=1,…, n- antal (indeks) af produkter;
- markedspris j-th produkt;
- forbrug jeg-th ressource til produktion af en enhed j-th produkt;
- planlagt produktionsvolumen j produkt, mængden er ukendt, den skal findes i processen med at løse problemet. Lad os skrive de indledende data for problemet i form af en matrix.


Ris. 2
Hver række i matrixen svarer til én ressource, hver kolonne til ét produkt. Til højre for hver linje er skrevet værdien af ​​ressourcebegrænsningen ( b 1 ,…, b i,…, b m); nederst i hver kolonne er prisen på produkter ( s 1,..., sj,..., Medm).
Hver celle i matrixen indeholder de såkaldte teknologiske koefficienter -en ij , viser forbrug jeg-th ressource til produktion af en enhed j-th produkt.
Lad os skrive et specifikt numerisk eksempel ned

Ris. 3

2.2 Konstruktion af en matematisk model
Lad os nu begynde at skabe en matematisk model, dvs. til den matematiske notation af problemet.
Objektiv funktion:

Begrænsninger:

x 1³0;
x 2³ 0;
x 3³ 0.
2.3 Beskrivelse af løsningen på dette problem
Lad os løse ovenstående problem ved hjælp af EXCEL.

Celleindhold:
B1:D1 – navne på produkter (teknologiske metoder);
A2:A4 – ressourcenavne;
B2:D4 – teknologiske koefficienter (ressourceforbrug ved enhedsintensiteter af teknologiske metoder);
B6:D6 – produktpriser;
B8:D8 – variabler;
F2:F4 – ressourcereserve;
G2:G4 – planlagte ressourceudgifter, opnået som følge af beslutningen;
G6 – værdien af ​​den objektive funktion, opnået som et resultat af løsningen.
Formler til beregninger:
G2=SUMPRODUKT(B$8:D$8; B2:D2);
G3:G4 – kopieret fra G2;
G6=SUMPRODUKT (B8:D8; B6:D6).
Lad os skrive formlerne i cellerne G2:G4. Placer markøren på G2. Vælg formelikonet ( f). To vinduer vises. I vinduet "kategori" skal du vælge "matematisk", og derefter vælge "SUMPRODUKT" i ​​vinduet "funktion". Vinduet SUMPRODUKT vises. Det skal angive, hvor operanderne er placeret. Den første operand er strengen B$8:D$8, den anden operand er drain B2:D2. Kopier formlen fra G2 ind i cellerne G3:G4. På samme måde skal du skrive objektivfunktionsformlen i celle G6. Nu skal du specificere de resterende betingelser for at løse problemet. Placer markøren på målfunktionscellen G6. I hovedmenuen skal du vælge "service", og derefter "søg efter en løsning". Der vises et vindue, hvor du skal angive:
1. Målcelle – G6;
2. Tænd for "maksimal værdi"-knappen;
3. Angiv de celler, der skal ændres (placering af variable) – B8:D8;
4. Skriv restriktionerne ned. De kan skrives ned direkte i det samme vindue, men det er bedre at vælge "tilføj" og i "tilføj" vinduet, der vises, nedskriv begrænsningerne sekventielt:
G2:G4 F2:F4 – det planlagte ressourceforbrug er mindre end deres reserve.
Nu er den elektroniske model dannet, og problemet kan løses. For at gøre dette skal du vende tilbage til vinduet "søg efter løsning" og klikke på "kør". Hvis den elektroniske model er udformet korrekt, vil der blive modtaget en besked om, at problemet er løst. Resultatet af løsningen er på EXCEL-arket og i tre rapporter: Resultater, Stabilitet, Grænser.

Ris. 4.1.4
De vigtigste resultater er synlige i tabellen (fig. 4.1.4.). Sammenlignet med problemforholdene vist i fig. 4.1.3., viste data:
1. Værdien af ​​objektivfunktionen i celle G6 = 15880;
2. Variable værdier i celler B8:D8: x 1 = 86, x 2 = 0, x 3 = 268; det betyder, at det 1. produkt skal produceres i et volumen på 86 enheder, det 2. - 0, og det 3. - 286.
3. Planlagt ressourceforbrug i celler G2:G4: 1. ressourceforbrug = 271,6, 2. ressourceforbrug = 310, 3. ressourceforbrug = 2200.
Som du kan se, er 1. ressource underudnyttet, og 2. og 3. er helt brugt op.
Ud over resultaterne i regnearket udarbejder EXCEL tre rapporter: Resultater, Bæredygtighed, Grænser. Resultatrapporten er vist i figur 4.1.5, som viser tre tabeller.
Resultatrapport
Målcelle (maksimum)
$G$6 Priser TF 15880
Udskiftelige celler

Cellenavn Oprindeligt resultat

$B$8 Variabel Pr1 0 86

$C$8 Variabel Pr2 0 0

$D$8 Variabel Pr3 0 268

Begrænsninger

Cellenavn Værdi Formel Statusforskel

$G$2 Res 1 Udgift 271,6 $G$2 $F$2 ikke forbundet 228,4

$G$3 Res 2 Flow 310 $G$3 $F$3 tilknyttet 0

$G$4 Res 3 Udgift 2200 $G$4 $F$4 forbundet 0

$B$8 Variabel Pr1 86 $B$8 0 ikke forbundet 86

$C$8 Variabel Pr2 0 $C$8 0 forbundet 0

$D$8 Variabel Pr3 268 $D$8 0 ikke forbundet 268

Ris. 4.1.5
Den 1. tabel - målcellen - giver værdien af ​​målfunktionen, som allerede er i EXCEL-tabellen, hvilket betyder, at disse data er overflødige.
Den 2. tabel - udskiftelige celler - giver værdierne af variabler, der allerede er i EXCEL-tabellen; disse data er også overflødige.
Den 3. tabel - restriktioner - giver en vurdering af restriktionerne. Kolonnen "Værdi" giver værdierne for det planlagte forbrug af ressourcer og variabler - disse data er tilgængelige i EXCEL-tabellen og er overflødige her. Kolonnen "status" med værdien "bundet" markerer de restriktioner (ikke mere eller mindre), der som følge af beslutningen blev til strenge ligheder; andre restriktioner har status "urelaterede". Kolonnen "forskel" viser, hvor meget begrænsningerne afveg fra streng lighed. Så for eksempel er begrænsningen af ​​den 1. ressource 500, den planlagte værdi er 271,6, forskellen = 500 – 271,6 = 228,4.
Bæredygtighedsrapporten er vist i fig. 4.1.6. Den består af to borde.
Bæredygtighedsrapport
Udskiftelige celler

Cellenavn Resultat Norir. Gradientværdi

$B$8 Variabel Pr1 86 0

$C$8 Variabel Pr2 0 -22,8

$D$8 Variabel Pr3 268 0

Begrænsninger

Resultat af cellenavn. Lagrange Multiplikatorværdi

$G$2 Res 1 Udgift 271,6 0

$G$3 Res 2 Flow 310 20

$G$4 Res 3 Forbrug 2200 4.4

Ris. 4.1.6
Tabellen "redigerbare celler" viser værdierne af variabler, der allerede findes i EXCEL-tabellen. Kolonnen "normaliseret gradient" viser, hvordan en forøgelse af variabler med én påvirker værdien af ​​objektivfunktionen. Tabellen "begrænsninger" indeholder vigtige oplysninger i kolonnen "Lagrange multiplikatorer". Disse mængder har forskellige navne i litteraturen: objektivt bestemte estimater (O.O.O.) ifølge L. Kantorovich, dobbelte estimater ifølge D. Danzig, optimale priser, skyggepriser og andre. I det følgende vil vi kalde dem ved det mest almindelige navn - dobbelte skøn og betegne - v i, Hvor jeg– begrænsningsnummer. I dette eksempel v 1 = 0, v 2 = 20,0, v 3 = 4,4. Grænserapporten er vist i fig. 4.1.7.
Begrænsningsrapport

Navn på celleredigerbar værdi	Lavere mål grænse resultat	Lavere mål grænse resultat
$B$8 Variabel Pr1 86	0 10720	86 15880
$C$8 Variabel Pr2 0	0 15880	0 15880
$D$8 Variabel Pr3 268	0 5160	268 15880

Ris. 4.1.7.
Denne rapport angiver værdien af ​​objektivfunktionen 15880 for tredje gang, og værdien af ​​variablerne ( x 1 = 86, x 2 = 0, x 3 = 268). Den nedre grænse for alle variable = 0, så der er begrænsninger på variablerne. Den øvre grænse er henholdsvis 86, 0 ​​og 268 for at sætte ressourcegrænser. Målresultatet viser værdien af ​​den objektive funktion med de tilsvarende værdier af variablerne. Hvis x 1= 0, så CF = 10720 osv.
Lad os nedskrive den matematiske model af problemet betragtet i generel form:

Lad ske:
I- budget, dvs. mængden af ​​penge, der kan bruges på at købe ressourcer til at producere produkter, og s jeg- markedspris jeg-th ressource. Så vil den eneste ressourcebegrænsning se sådan ud:
.
Meningen med denne begrænsning er, at du ikke kan bruge flere ressourcer end I.
Her: - forbrug jeg-th ressource i fysisk henseende ved j-th teknologiske metode;
- forbrug jeg-th ressource i naturalier efter alle metoder;
- total pris jeg-th ressource brugt på alle måder;
- den samlede pris for alle ressourcer for alle teknologiske metoder.
Lad os løse problemet med at maksimere produktionen med en budgetbegrænsning. Lad os tage den elektroniske model i Fig. som grundlag. 4.1.3. og supplere med ressourcepriser s jeg og budget B (fig. 4.1.8)

Ris. 4.1.8

Yderligere mængder:
H2:H4 – ressourcepriser (sæt);
I2:I4 – omkostninger (beregnet);
I2 = G2*H2;
I3:I4 – kopieret fra I2;
H6 = 5000 – budget (sæt);
I6 – samlede omkostninger (beregnet);
I6 = SUM (I2:I4).
Begrænsninger:
B8:D8 0 – ikke-negativitet af variable;
I6 H6 – de samlede omkostninger overstiger ikke budgettet.
Der vil blive modtaget en løsning
x 1 = 0; x 2 = 0; x 3 = 409,84.
v= 3,08 – dobbelt skøn over budgetbegrænsningen – en stigning i budgettet med én enhed øger bruttoproduktet med 3,28.
Hvis ressourcebegrænsninger i modellen giver mening og ikke er mere end () og ikke mindre end (), og alle værdier () ikke er negative, kan en konklusion om eksistensen eller fraværet af en acceptabel plan i det generelle tilfælde ikke blive lavet. Det hele afhænger af de specifikke værdier af og . Det er muligt, at for nogle k Den th ressource har en sådan begrænsning, at den ikke kan opfyldes på grund af andre begrænsninger. Så er der ingen gyldig plan.

Konklusion

Som et resultat af det udførte arbejde blev teoretisk materiale dedikeret til løsning af dobbelt lineære programmeringsproblemer gennemgået, og processen med at løse dem blev automatiseret ved hjælp af MS Excel-programmet.
Resultatet af arbejdet med kursusprojektet er et program til løsning af lineære programmeringsproblemer ved hjælp af dual simplex-metoden.

Bibliografi

1. Kuznetsov Yu.N., Kuzubov V.I., Voloshchenko A.B. Matematisk programmering. "Science", 1980

Dualitet i lineær programmering

1. Dobbelt lineær programmeringsproblemer

Fra enhver LP problem det er muligt at associere et andet LP-problem, som i forhold til det første kaldes dual. Så vil det oprindelige problem blive kaldt direkte.

Lad os betragte et standard LP-problem med n variable og m begrænsninger i form af uligheder

f(x) = c 1x 1+c 2x 2 + …+ c n x n max, 11 x 1 + a 12 x 2 + … + a 1n x n b 1,21 x 1 + a 22 x 2 + … + a 2n xn b 2,

…………………………………….……m1 x 1 + a m2 x 2 + … + a mn x n b m ,j 0, j = 1, 2, …, n.

Et LP-problem af følgende form kaldes dets dobbelte:

g(y) = b 1 y 1+b 2 y 2 + …+ b m y m ??min 11 y 1 + a 21 y 2 + … + a m1 y m c 112 y 1 + a 22 y 2 + … + a m2 år m c 2

………………………….………………1n y 1 + a 2n y 2 + … + a mn y m c n

yi 0, i = 1, 2, …, m.

Udskrivning af tilstandsmatricer for de direkte og dobbelte problemer

vi ser, at Adv = ATpr.

Derfor kan et par dobbelte problemer skrives i matrixform:

< c, x >max; Axe ab, x a0.g(y) =< b, y >min; PÅ y?с, y?0.

2. Symmetrisk par af dobbelte problemer

Et par dobbelte problemer, hvor det direkte problem er standard, kaldes et symmetrisk par af dobbelte problemer.

Regler for at konstruere det dobbelte problem til standard LP-problemet.

· Antallet af variable i det dobbelte problem er lig med antallet af hovedbegrænsninger for det direkte problem og omvendt.

· Hvis det direkte problem er et problem for max under begrænsninger "", så er det dobbelte problem et problem for min under begrænsninger ".

· Højre side af det direkte problems begrænsninger - tal b jeg - blive koefficienter for den objektive funktion af det dobbelte problem.

· Koefficienter for den objektive funktion af det direkte problem - tal c j - blive den højre side af begrænsningerne af det dobbelte LP-problem.

· Den j-te kolonne i matrixen af ​​betingelser for det direkte problem bliver til den j-te række af matrixen af ​​betingelser for det dobbelte problem.

· Variablerne for de direkte og dobbelte problemer er ikke-negative.

Eksempel. Lad os betragte et standard LP-problem med to variable, tre begrænsninger i form af uligheder og ikke-negativitetsbetingelser.

f(x)=2x 1-4x 2max; 1 + 3x 2 8,

3x 1+ x 2 -7,

2x 1 - 5x 2 10,

x 1.x 2 0.

Lad os konstruere et dobbelt problem for det, styret af reglerne. Det vil have tre variable og to begrænsninger.

g(y)=8 år 1-7 år 2+10 år 3min; 1 - 3 år 2+2 år 3 2,

3 år 1+ y 2 -5 år 3 -4,1, y 2 0.

Lad os vise det LP-dualen til det dobbelte problem falder sammen med den direkte linje LP problem,som vi vil bruge det foregående eksempel til.

Først reducerer vi det dobbelte problem til standard visning

g(y)= -8y 1+7 år 2-10 år 3max; 1+ 3 år 2 - 2 år 3 -2,

3 år 1 -y 2+ 5 år 3 4,1, y 2 0.

Lad os konstruere et dobbelt problem for det i henhold til reglerne 1-6, der angiver de dobbelte variable med x1, x 2.

f(x)= -2x 1+ 4 x 2min;

x1 - 3x 2 -8,

x 1 - x 2 7,

2x 1+ 5x2 -10,

x 1.x 2 0.

For at opnå det oprindelige problem er det nok at gange koefficienterne for den objektive funktion og alle restriktioner med (-1).

Af ovenstående følger det, at hvis det direkte problem har formen:

f(x) =< c, x >min; b, x 0,

så bliver opgaven dobbelt til den

g(y) =< b, y >max; T y s, y 0.

3. Økonomisk betydning af den dobbelte opgave

Overvej følgende produktionsopgave.

Efter frigivelse af hovedproduktet har virksomheden overskudsressourcer af to typer: R 1- 10 enheder, R 2- 8 enheder. Der er to måder at administrere disse ressourcer på:

· organisere udgivelsen af ​​3 nye typer produkter fra dem: P 1, P2 , P 3.

· sælge dem.

Lad os overveje begge metoder.

De indledende data er vist i tabellen:

RessourcerRessourceforbrug pr. produktionsenhedResourcebeholdningP 1P 2P 3R 112110R 22138Specifik profit$6$4$4

Ifølge første metode, er det nødvendigt at udarbejde en produktionsplan, der maksimerer den samlede profit. Lad os bygge en matematisk model af dette problem.

Lad x j - produktionsplan Pj.

Så vil objektivfunktionen se sådan ud:

f(x)=6x 1+4x2 +4x 3max;

Ressourcegrænser:

1+2x2 +x 3 10,

x 1+x 2+3x 3 8,j 0, j=1,2,3.

Vi modtog et standard LP-problem.

Lad os overveje anden vejbrug af ressourcer, nemlig salg heraf.

Virksomhedens interesse er at sælge ressourcer til priser, hvor indtægten fra salg af ressourcer ikke vil være mindre end den fortjeneste, der kan opnås ved salg af produkter fremstillet af disse ressourcer.

Til gengæld er køberen interesseret i at købe ressourcer til priser, hvor købsomkostningerne vil være minimale.

Opgaven med at aftale priser på ressourcer, der passer til begge parter, kan beskrives som følger matematisk model.

Lad y 1- prisen på en enhed af ressource R 1,y 2- prisen på en enhed af ressource R2.

Købers interesse vil blive udtrykt ved en målfunktion svarende til de samlede omkostninger for købte ressourcer

g(y) = 10y 1+8 år 2min.

Sælgers interesse vil være underlagt følgende begrænsninger:

y 1+2 år 2 6,

y1 +y 2 4,

y1 +3 år 2 4,

hvor venstre side betyder omkostningerne ved ressourcer brugt på at producere en enhed af det tilsvarende produkt, og højre side betyder det specifikke overskud fra salget.

Tilføjelse af naturlige betingelser for ikke-negativitet af priser:

y 1, y2 , y 3 0,

vi får dobbelt LP problem.

Der kan således gives en vis økonomisk betydning til et symmetrisk par af dobbelte problemer.

Direkte opgaveBestem en sådan produktionsplan x =(x 1, x 2,…, x n ), ved brug af begrænsede ressourcereserver, hvor fortjenesten fra salg af produkter vil være maksimal. Dobbelt problemIndstil et sådant sæt ressourcepriser y =(y 1, y 2,…, y m ), hvor omkostningerne ved ressourcer brugt på at producere en produktenhed ikke vil være lavere end fortjenesten fra salget, men samtidig vil de samlede omkostninger til omkostningerne være minimale.

Ressourcepriser y 1, y 2,…, y m kaldes skygge-, implicitte eller interne priser. Disse navne adskiller dem fra "eksterne", forud kendte priser med 1, Med 2,..., Med n for fremstillede produkter. Priser 1, y 2,…, y m for ressourcer bestemmes ud fra løsningen af ​​et dobbelt problem og karakteriserer produktionsomkostningerne for specifikke typer produkter, derfor kaldes de ofte dobbelte ressourceestimater.

4. Asymmetrisk par af dobbelte problemer

Lad nu det oprindelige problem være kanonisk, det vil sige have formen:

f(x) =< c, x >max;(4.1)Ax = b,(4.2)x 0.(4.3)

Her er x = (x 1,..., x n ), c = (c 1,..., c n) , b = (b 1,…, b m ), så antallet af ligninger i systemet (4.2) er lig med m.

For at konstruere det dobbelte problem til opgave (4.1) - (4.3), reducerer vi det til standardformen.

Vi erstatter hver lighed i (4.2) med et par uligheder

eller hvad er det samme

Vi får et standard LP problem med 2m begrænsninger.

f(x)=< c, x >max;b,

Lad os konstruere et dobbelt LP-problem til det i henhold til kendte regler.

For at gøre dette introducerer vi dobbelte variable:

u = (u 1,..., u m) 0,

v = (v 1,…, v m) 0.

Bemærk, at da der var 2m begrænsninger i det direkte LP-problem, vil der være 2m variable i den dobbelte.

Den objektive funktion af det dobbelte problem vil antage formen:

g(u,v)=< b, u > + < - b, v >min,

og begrænsningerne vil blive skrevet sådan:

PÅ u - A T vc,

Lad os omskrive dette problem mere kompakt:

g(u,v)=< b, u - v>min,T (u - v) c, 0, v 0.

Lad os introducere ny vektor dobbelte variable y = (y 1,y 2,…, y m) med y-koordinater jeg = u jeg -v jeg . Da forskellen mellem ikke-negative tal også kan være negativ (for eksempel 2-5 = -3), så er de dobbelte variable y jeg har ingen tegnrestriktioner.

Således vil det dobbelte problem til det kanoniske have formen:

g(y) =< b, y >min;T y 0,

Variabel ethvert tegn!

5. Tabeller til at konstruere det dobbelte problem

Til ethvert LP-problem kan der konstrueres en dobbelt. For at gøre dette skal du reducere det til en standard eller kanonisk form. Du kan også bruge tabellerne nedenfor.

Direkte lineær programmeringsproblemDobbelt lineær programmeringsproblemObjektiv funktion< c, x >max< b, y >minObjective functionType af i-te begrænsning jeg b jeg y jeg 0 Tegn for den i-te variabel jeg b jeg y jeg 0jeg = b jeg y jeg j 0j c j Skriv j-constraintx j 0j c j x j ? fri variabel j =c j

Direkte lineær programmeringsproblemDobbelt lineær programmeringsproblemObjektiv funktion< c, x >min< b, y >?maxObjective functionType af i-te begrænsning jeg b jeg y jeg ?0Tegnet for den i-te variabel jeg b jeg y jeg 0jeg = b jeg y jeg - ethvert tegn for den j-te variablex j 0j c j Skriv j-constraintx j 0j c j x j ? fri variabel j =c j

Dyrke motion. Komponer dobbeltopgaver til følgende LP-opgaver.

1. f(x) = 2x 1- 2x 2+ 3x3 - 6x 4max

x 1+ x 2 - 2x 3 + x 4 = -101- 5x 2-x 3 + 2x 4= 35j 0, j=1,2,3,4

F(x) = -x 1 - 3x 2+ x 3min 1+ x 2+ x 3 61-x 2+ x 3 8j 0, j=1,2,3

F(x) = 9x 1+ 2x 2+ 3x3 + 2x 4min

x 1+ x2 + 2x 3 = 2

x 1+ x 2-x 3 - 4x 4= -1j 0, j=1,2,3,4

F(x) = x 1 - 2x 2max1 + x 2 4

x1 -x 2 8

x1 + x 2 0

x2 0

6. Forholdet mellem planer for dobbelte problemer

Lad os overveje symmetrisk par dobbelte problemer:

f(x) =< c, x >max;(4,4)g(y) =< b, y >min;(4,7)Ax b(4,5)A T y c(4,8)x 0(4,6)(y 0(4,9)x = (x 1,…, x n) y = (y1 ,…, y m)

Der er en tæt sammenhæng mellem løsningerne på disse problemer, afspejlet af følgende egenskaber og sætninger.

7. Første dualitetssætning

Ud over den største ulighed og et tilstrækkeligt tegn på optimaliteten af ​​planer for gensidigt dobbelte problemer, er der andre forbindelser mellem deres løsninger. Det er vigtigt at fastslå, om tilstedeværelsen eller fraværet af en løsning på det ene af et par problemer påvirker eksistensen af ​​en løsning på det andet. Svaret på dette spørgsmål er givet af følgende sætning, kendt som den første dualitetssætning.

Sætning 1. Hvis den ene af et par af dobbeltopgaver har en optimal plan, så har den anden også en optimal plan, og værdierne af de objektive funktioner på disse planer er ens

(x *) = g(x *) eller< c, x*> = < b, y*>.

Hvis den objektive funktion af et af parret af dobbelte problemer ikke er begrænset til dets sæt af planer (direkte - ovenfra, dobbelt - nedefra), så er sættet af planer for det andet problem tomt.

Af den første del af sætningen, som vi præsenterer uden beviser, følger det, at lighed (4.14) ikke blot er tilstrækkelig, men også en nødvendig betingelse optimaliteten af ​​planer for et par dobbelte problemer.

Udsagnet i anden del af sætningen kan let bevises ved modsigelse. Lad os antage, at i den direkte opgave (4.4) - (4.6) er objektivfunktionen ikke afgrænset ovenfra på mængden X, det vil sige max f(x) ¥ , x Î X, men sættet af planer Y for det dobbelte problem er ikke tomt - der er mindst et punkt y Î Y. Så, på grund af dualitetsteoriens vigtigste ulighed: max f(x) g(y), hvilket modsiger ubegrænsetheden af ​​den objektive funktion af det direkte problem. Det faktum, at det oprindelige problems objektive funktion er ubegrænset ovenfra, indebærer således inkonsistensen af ​​det dobbelte problems begrænsninger. Det er på samme måde bevist, at da den dobbelte objektive funktion g(y) på mængden Y er ubegrænset nedefra, følger det, at sættet af planer X for det direkte problem er tomt.

Interessant nok er det modsatte ikke sandt. Tomheden af ​​sættet af planer for et problem betyder ikke nødvendigvis, at den objektive funktion i dets dobbelte problem er ubegrænset. (Begge sæt kan være tomme.)

Den første dualitetssætning giver os mulighed for at undersøge enhver given plan for optimalitet.

8. Anden dualitetssætning

Sætning 2. Planer x * = (x 1*,…, x n *) og y * = (y 1*,…, y m *) - er optimale (hver i sin egen opgave), hvis og kun hvis følgende betingelser er opfyldt:

< Ax*- ved* > = 0,(4.15)

< AT y *- c, x* > = 0,(4.16)

Bevis.

Lad os udføre beviset for et asymmetrisk par af dobbelte problemer.

Direkte LP problemDobbelt LP problemf(x) =< c, x >maxg(y) =< b, y >min(4,17) Ax = bAT y cx 0

Nødvendighed.

Lad x *, y *- optimale planer for henholdsvis de direkte og dobbelte problemer. Lad os vise, at betingelserne (4.15), (4.16) er opfyldt.

Bemærk, at for x = x *fra (4.17) følger (4.15). Siden Axe *- b= 0, hvilket betyder det skalære produkt *- ved * > er også nul. Ved den første dualitetssætning for optimale planer x *, y *lighed gælder:< c, x* > = < b, y*>. Lad os her erstatte udtrykket for b fra (14): b = Ax *. Ved at bruge overførselsreglen får vi:

< c, x* > = < Ax*, y * >= < x*, A T y * > = < AT y* , x * >,

hvorfra følger< AT y *- c, x * > = 0. Og dette er ikke andet end betingelse (4.16)

Tilstrækkelighed.

Udleje for tilladte planer x *, y *(4.15), (4.16) gælder. Lad os bevise deres optimalitet.

Betingelser (4.15) og (4.16) kan skrives som følger

< Ax*, y * > = < b, y* >, < AT y *, x * > = < c, x* >.

Efter overførselsreglen< Ax*, y * > = < AT y *, x *>. Da venstre side af betingelserne er ens, er højre sider også ens:

< b, y* > = < c, x* >,

herfra, ved egenskab 2, konkluderer vi, at x *- optimal plan for det direkte problem, *- optimal plan for et dobbelt problem. Q.E.D.

. Ligevægtsforhold

Lad os fortsætte vores undersøgelse af de nødvendige og tilstrækkelige betingelser for optimaliteten af ​​planer for gensidigt dobbelte problemer, bevist i den anden dualitetssætning.

< Ax*- ved* > = 0,(4.18)

< AT y *- c, x* > = 0. (4.19)

Direkte LPD-problem Dobbelt LP-problemf(x) = c 1x 1+ … + c n x n maxg(y) = b 1 y 1+ …+ b m y m ??mina i1 x 1 + … + a i x n b jeg , i =1,…, ma 1j y 1 + … + a mj y m c j , j = 1,…, nx j 0, j = 1,…, nyi 0, i = 1,..., m

Ved at udvide skalarprodukter beskriver vi betingelser (4.18) og (4.19) mere detaljeret.

å ( -en i1 x 1*+ … + a i x n * -b jeg ) yi * = 0,(4.20)

å ( -en 1j y 1*+ … + a mj y m * -c j )xj * = 0.(4.21)

I summen (4.20) er hvert led produktet af forskellen mellem venstre og højre side af begrænsningen af ​​det direkte problem med den tilsvarende dobbelte variabel. Det er klart, at alle led har samme fortegn "0", da forskellene i parentes er mindre end eller lig med nul, og y jeg 0. Det følger, at summen (4.20) er lig med nul, hvis og kun hvis hvert led i det er lig med nul.

(-en i1 x 1*+ … + a i x n * -b jeg )y jeg * = 0, i =1,..., m. (4,22)

dualitet ulighed ligevægt lineær

I summen (4.21) er hvert led lig med produktet af forskellen mellem venstre og højre side af det dobbelte problems begrænsning og den tilsvarende variabel for det direkte problem. Alle led i denne sum har samme fortegn (0), da forskellene er i parentes og variablerne x j * ikke-negativ. For at summen er lig nul, skal ethvert led i summen være lig nul.

(-en 1j y 1*+ … + a mj y m * -c j )x j * = 0, j = 1,…, n. (4,23)

Under hensyntagen til tegnene på faktorerne i produktet (4.22), kan vi ud fra det få et par betingelser

Hvis en i1 x 1*+ … + a i x n * <b jeg , så yi * = 0. (4.22a)

Hvis y jeg * > 0, derefter a i1 x 1*+ … + a i x n * = bi . (4.22b)

Tilsvarende følger fra (6) et par betingelser

Hvis en 1j y 1*+ … + a mj y m * >c j , derefter xj * = 0. (4.23a)

Hvis x j * > 0, derefter a 1j y 1*+ … + a mj y m *cj. (4.23b)

Således for et par dobbelte problemer

· hvis en begrænsning af et problem på den optimale plan er opfyldt som en streng ulighed, så er den tilsvarende koordinat af den optimale plan for et andet problem lig med nul (betingelser (4.22a) og (4.23a)).

· Hvis en koordinat af den optimale plan for et problem er positiv, så bliver den tilsvarende begrænsning af det andet problem lighed (betingelser (4.22b) og (4.23b)).

Disse forhold kaldes komplementære slaphedsbetingelser eller ligevægtsbetingelser.

. Geometrisk betydning af ligevægtsbetingelser

Definition 1 . Begrænsning af et standard lineært programmeringsproblem

-en i1 x 1 + … + a i x n b jeg (4.24)

kaldes forbundet eller aktiv på plan x" hvis det på dette plan bliver til lighed

-en i1 x 1"+ … + a i xn "b jeg .

Definition 2. Begrænsning (4.24) kaldes disconnected (inaktiv, passiv) på planet x" hvis det på dette plan gælder som en streng ulighed

-en i1 x 1"+ … + a i x n " <b jeg .

Geometrisk passerer en begrænsning, der er aktiv ved punkt x" gennem det punkt, mens en inaktiv begrænsning ikke gør det.

På figuren ved punkt x" P 1og P 3- aktive, sammenhængende restriktioner; P 2- inaktiv begrænsning. Ved punkt x» P 1,P 2 - aktive restriktioner; P 3- inaktiv begrænsning.

Nu kan ligevægtsbetingelserne gives en geometrisk betydning.

På optimale planer for dobbelte problemer

· En inaktiv begrænsning for en opgave svarer til en nulplanvariabel for en anden opgave.

· den positive variabel i den optimale plan for en opgave svarer til den aktive begrænsning af en anden opgave.

Litteratur

1. Ayvazyan S.A., Ivanova S.S. Økonometri. Kort kursus: lærebog. godtgørelse / S.A. Ayvazyan, S.S. Ivanova. - M.: Marked DS, 2007. - 104 s.

Borodich S.A. Indledende økonometrikursus: Lærebog. - Mn.: BSU, 2009. - 354 s.

Byvshev V.A. Økonometri: lærebog. godtgørelse / V.A. Byvshev. - M.: Finans og statistik, 2008. - 480 s.

Dougherty Christopher. Introduktion til økonometri: Lærebog i økonomi. specialist. universiteter / Overs. fra engelsk E.N. Lukash et al. - M.: INFRA-M, 2007. - 402 s.

Dubrov A.M., Mkhitaryan V.S., Troshin L.I. Multivariate statistiske metoder: Lærebog. - M.: Finans og statistik, 2009. - 352 s.

Dubrova T.A. Forecasting af socioøkonomiske processer. Statistiske metoder og modeller: lærebog. godtgørelse / T.A. Dubrova. - M.: Marked DS, 2007. - 192 s.

Magnus Y.R., Katyshev P.K., Peresetsky A.A. Økonometri. Begyndelseskursus: Lærebog. -3. udg., revideret. og yderligere - M.: Delo, 2008. - 400 s.

Metoder til matematisk statistik til behandling af økonomisk information: lærebog. godtgørelse / T.T. Tsymbalenko, A.N. Baudakov, O.S. Tsymbalenko og andre; redigeret af prof. T.T. Tsymbalenko. - M.: Finans og Statistik; Stavropol: ARGUS, 2007. - 200 s.

Paliy I.A. Anvendt statistik: Lærebog. - M.: Forlags- og handelsselskab "Dashkov og K", 2008. - 224 s.

Poryadina O.V. Økonometrisk modellering af lineære regressionsligninger: En tutorial. - Yoshkar-Ola: MarSTU, 2006. - 92 s.

Workshop om økonometri: Proc. godtgørelse / I.I. Eliseeva, S.V. Kurysheva, N.M. Gordeenko og andre; Ed. I.I. Eliseeva. - 2. udg., revideret. og yderligere - M.: Finans og statistik, 2007. - 344 s.

Anvendt statistik. Fundamentals of econometrics: Lærebog for universiteter: I 2 bind, 2. udg., revideret. - T. 2: Ayvazyan S.A. Grundlæggende om økonometri. - M.: UNITY-DANA, 2009. - 432 s.

Simchera V.M. Metoder til multivariat analyse af statistiske data: lærebog. godtgørelse. - M.: Finans og statistik, 2008. - 400 s.

Churakov E.P. Forecasting økonometrisk tidsserie: lærebog. godtgørelse / E.P. Churakov. - M.: Finans og statistik, 2008. - 208 s.

Økonometri: lærebog. /udg. doktor i økonomi naturvidenskab, prof. V.S. Mkhitaryan. - M.: Prospekt, 2008. - 384 s.

Økonometri: lærebog. /udg. I.I. Eliseeva. - M.: Prospekt, 2009. - 288 s.

Økonometri: Lærebog/I.I. Eliseeva, S.V. Kurysheva, T.V. Kosteeva et al., red. I.I. Eliseeva. - 2. udg., revideret. og yderligere - M.: Finans og statistik, 2006. - 576 s.

Vejledning

Har du brug for hjælp til at studere et emne?

Vores specialister rådgiver eller yder vejledningstjenester om emner, der interesserer dig.
Send din ansøgning med angivelse af emnet lige nu for at finde ud af om muligheden for at få en konsultation.

Kan formuleres regler for at opnå det dobbelte problem fra det oprindelige problem.

1. Hvis der i den oprindelige opgave søges maksimum af den objektive funktion, så søges i dens dobbelte problem minimumet.

2. Koefficienter af variable i den objektive funktion af et problem er frie medlemmer af systemet af begrænsninger for et andet problem.

3. I den originale ZLP er alle funktionelle begrænsninger uligheder af formen "≤", og i den dobbelte problemstilling er de uligheder af formen "≥".

4. Koefficienter af variable i systemer af begrænsninger af gensidigt dobbelte problemer er beskrevet af matricer transponeret i forhold til hinanden.

5. Antallet af uligheder i systemet af begrænsninger for et problem falder sammen med antallet af variable i det andet.

6. Betingelsen for variables ikke-negativitet er bevaret i begge problemer.

Forbindelsen mellem optimale planer for gensidigt dobbelte problemer etableres af dualitetssætninger.

Sætning 1.Hvis et af de dobbelte problemer har et endeligt optimum, så har det andet også et endeligt optimum, og de ekstreme værdier af de objektive funktioner falder sammen:

Således, hvis en komponent af den optimale plan er større end nul, så bliver denne begrænsning til en sand lighed, og omvendt, når den erstattes i den tilsvarende begrænsning af det dobbelte problem med den optimale plan.

Estimationssætning.Værdierne af variablerne i den optimale løsning af det dobbelte problem er estimater af indflydelsen af ​​de frie vilkår b i i systemet af begrænsninger af det direkte problem på værdien af ​​den objektive funktion:

(2.8)

Komponenterne i den optimale løsning på det dobbelte problem kaldes normalt dobbelte vurderinger. Begrebet "objektivt fastsatte vurderinger" bruges også ofte.

Den økonomiske og matematiske analyse af ressourcefordeling er baseret på egenskaberne ved dobbeltvurderinger. Inden for grænserne for stabilitet af dobbelte estimater finder de egenskaber, der diskuteres nedenfor, sted.

Når vi beskriver egenskaberne ved dobbelte estimater, vil vi bruge problemet med hockeystave og skaksæt til klart at illustrere de bestemmelser, der overvejes.

Formulering af det direkte (indledende) problem:

y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0.

Som et resultat af løsningen opnår vi følgende optimale planer:

= (24, 4); = (1/3, 1/3, 0).

Det er let at verificere, at når man erstatter optimale planer i problemernes objektive funktioner, er begge resulterende værdier lig med 64.

Lad os gå videre til at overveje egenskaberne ved dobbelte skøn.

Ejendom 1. Vurderinger som et mål for ressourceknaphed. Dobbelte vurderinger afspejler den relative knaphed på produktionsfaktorer. Jo højere værdien af ​​estimatet er, jo højere knaphed på den i-te ressource. Faktorer vurderet til nul er ikke sparsomme og begrænser ikke produktionen.

I vores eksempel fik den tredje ressource en nulkarakter ( = 0), så den er ikke knap, dvs. set fra opgavens synspunkt begrænser arbejdstidsfonden på site C ikke produktionen. Tværtimod er den første (afsnit A) og anden (afsnit B) ressource knappe og begrænser produktionen i samme omfang (= 1/3).

Det sidste udsagn kan nemt bekræftes ved at erstatte og ind i det oprindelige problems begrænsninger:

4 24 + 6 4 = 120, 2 24 + 6 4 = 72, 4< 10.

Dette viser, at når den optimale plan implementeres, er arbejdstidsfonden i afsnit C faktisk ikke helt brugt.

Ejendom 2. Estimater som et mål for begrænsningers indflydelse på værdien af ​​den objektive funktion. Værdien af ​​den dobbelte vurdering af en ressource viser, hvor meget den maksimale værdi af den objektive funktion ville stige, hvis volumen af ​​denne ressource steg med én. I denne forbindelse kaldes værdien af ​​en objektivt bestemt vurdering nogle gange en ressources skyggepris. Skyggeprisen er prisen pr. ressourceenhed i den optimale løsning.

Det skal dog tages i betragtning, at dobbelte vurderinger giver os mulighed for at måle effektiviteten af ​​kun en lille ændring i mængden af ​​ressourcer. Med væsentlige ændringer kan en ny optimal plan og nye dobbelte estimater opnås.

For vores eksempel skulle en stigning (reduktion) i tidsfonden i sektion A eller B føre til en stigning (reduktion) i den maksimale profit med $1/3. Følgelig, for eksempel, hvis tidsfonden i sektion A stiger med 12 n-timer, bør det samlede overskud stige med $4 (1/3-12).

Ejendom 3. Vurderinger som et værktøj til at bestemme effektiviteten af ​​individuelle forretningsbeslutninger. Ved hjælp af dobbelte vurderinger er det muligt at bestemme rentabiliteten af ​​at frigive nye produkter og effektiviteten af ​​nye teknologiske produktionsmetoder. I dette tilfælde kan produktionsmuligheden, for hvilken mængden af ​​tabt fortjeneste på grund af omdirigering af knappe ressourcer vil være mindre end den modtagne fortjeneste, anses for effektiv. Forskellen mellem disse værdier (Δ j) beregnes som:

(2.9)

I tilfælde af, at Δ j ≤ 0, er produktionsmuligheden rentabel, hvis Δ j > 0, er muligheden urentabel.

Lad os vende tilbage til vores eksempel. Lad virksomheden planlægge at frigive den nye slags produkter: baseballbat. For at producere en flagermus er det nødvendigt at bruge 3 timers arbejde i område A, 4 timers arbejde i område B og 1 times arbejde i område C. Fortjenesten modtaget fra salget af en bit er $3. Er det rentabelt for en virksomhed at producere nye produkter?

For at besvare spørgsmålet, lad os beregne Δ j ved hjælp af formel (2.9):

Δ j = 3ּ + 4ּ + 1ּ - 3 = 3ּ1/3 + 4ּ1/3 + 1ּ0 - 3 = -2/3,

Δj< 0, значит производить бейсбольные биты выгодно.

Ejendom 4. Estimater som et mål for ressourcernes relative substituerbarhed i form af den endelige effekt. For eksempel viser forholdet /, hvor mange enheder af den k-te ressource, der kan frigives, når volumen af ​​den i-te ressource øges med én, således at maksimum af objektivfunktionen forbliver på samme niveau; eller omvendt, hvor mange enheder af den k-te ressource skal der yderligere indføres, når volumen af ​​den i-te ressource reduceres med én enhed, hvis vi ønsker, at værdien af ​​den objektive funktion forbliver uændret.

I vores eksempel er den dobbelte værdiansættelse af den første og anden ressource ens. Det betyder, at f.eks. hvis tidsfonden i afdeling A nedsættes med 1 time, er det nødvendigt at øge tidsfonden i afdeling B med 1 time, således at det samlede overskud til virksomheden forbliver uændret.

Som afslutning på vores overvejelse af spørgsmålet bemærker vi, at brugen af ​​dualitetssætninger (nemlig relationer (2.6) og (2.7)) gør det muligt, ved at kende den optimale løsning af et af de gensidigt dobbelte problemer, nemt at finde den optimale løsning af et andet problem .

Lad os illustrere dette udsagn eksempel.

For at producere fire typer produkter A 1, A 2, A 3 og A 4 skal anlægget anvende tre typer råvarer I, II og III. Råvarelagre for planperioden er på henholdsvis 1000, 600 og 150 enheder.

Teknologiske koefficienter (forbrug af hver type råvare til produktion af en enhed af hvert produkt) og fortjeneste ved salg af en enhed af hvert produkt er vist i tabel 2.12.

Tabel 2.12 - Indledende data for problemet om fire typer produkter

Det er påkrævet, at kende løsningen på et givet problem, at løse det dobbelte problem.

Lad os formulere den indledende ZLP.