Revidert simpleksmetode - Revised simplex method

I matematisk optimalisering , den reviderte simplex-metoden er en variant av George Danzig 's simplex metode for lineær programmering .

Den reviderte simpleksmetoden er matematisk ekvivalent med standard simpleksmetoden, men er forskjellig i implementeringen. I stedet for å opprettholde et tablå som eksplisitt representerer begrensningene justert til et sett med grunnleggende variabler, opprettholder det en representasjon av et grunnlag for matrisen som representerer begrensningene. Den matriseorienterte tilnærmingen gir større beregningseffektivitet ved å muliggjøre sparsomme matriseoperasjoner.

Problemformulering

For resten av diskusjonen antas det at et lineært programmeringsproblem er konvertert til følgende standardform:

${\ displaystyle {\ begin {array} {rl} {\ text {minimize}} og {\ boldsymbol {c}} ^ {\ mathrm {T}} {\ boldsymbol {x}} \\ {\ text {underlagt }} og {\ boldsymbol {Ax}} = {\ boldsymbol {b}}, {\ boldsymbol {x}} \ geq {\ boldsymbol {0}} \ end {array}}}$

hvor A ∈ R ^{m × n} . Uten tap av generalitet antas det at begrensningsmatrisen A har full radrangering og at problemet er gjennomførbart, dvs. at det er minst en x ≥ 0 slik at Ax = b . Hvis A er rangmangel, er det enten overflødige begrensninger, eller problemet er gjennomførbart. Begge situasjonene kan håndteres med et forhåndsstilt trinn.

Algoritmisk beskrivelse

Optimalitetsforhold

For lineær programmering er forholdene Karush – Kuhn – Tucker både nødvendige og tilstrekkelige for optimalitet. KKT-forholdene til et lineært programmeringsproblem i standardform er

${\ displaystyle {\ begin {align} {\ boldsymbol {Ax}} & = {\ boldsymbol {b}}, \\ {\ boldsymbol {A}} ^ {\ mathrm {T}} {\ boldsymbol {\ lambda} } + {\ boldsymbol {s}} & = {\ boldsymbol {c}}, \\ {\ boldsymbol {x}} & \ geq {\ boldsymbol {0}}, \\ {\ boldsymbol {s}} & \ geq {\ boldsymbol {0}}, \\ {\ boldsymbol {s}} ^ {\ mathrm {T}} {\ boldsymbol {x}} & = 0 \ end {align}}}$

hvor λ og s er Lagrange-multiplikatorene assosiert med begrensningene henholdsvis Ax = b og x ≥ 0 . Den siste tilstanden, som tilsvarer s _i x _i = 0 for alle 1 < i < n , kalles komplementær slakkhetstilstand .

Med det som noen ganger kalles den grunnleggende teoremet for lineær programmering , kan et toppunkt x på den mulige polytopen identifiseres ved å være en basis B av A valgt fra sistnevnte kolonner. Siden A har full rang, er B ikke-singular. Uten tap av generalitet, anta at A = [ B   N ] . Da er x gitt av

${\ displaystyle {\ boldsymbol {x}} = {\ begin {bmatrix} {\ boldsymbol {x_ {B}}} \\ {\ boldsymbol {x_ {N}}} \ end {bmatrix}} = {\ begin { bmatrix} {\ boldsymbol {B}} ^ {- 1} {\ boldsymbol {b}} \\ {\ boldsymbol {0}} \ end {bmatrix}}}$

hvor x _B ≥ 0 . Partisjon c og s deretter inn i

${\ displaystyle {\ begin {align} {\ boldsymbol {c}} & = {\ begin {bmatrix} {\ boldsymbol {c_ {B}}} \\ {\ boldsymbol {c_ {N}}} \ end {bmatrix }}, \\ {\ boldsymbol {s}} & = {\ begin {bmatrix} {\ boldsymbol {s_ {B}}} \\ {\ boldsymbol {s_ {N}}} \ end {bmatrix}}. \ slutt {justert}}}$

For å tilfredsstille den komplementære slakkhetsbetingelsen, la s _B = 0 . Det følger at

${\ displaystyle {\ begin {align} {\ boldsymbol {B}} ^ {\ mathrm {T}} {\ boldsymbol {\ lambda}} & = {\ boldsymbol {c_ {B}}}, \\ {\ boldsymbol {N}} ^ {\ mathrm {T}} {\ boldsymbol {\ lambda}} + {\ boldsymbol {s_ {N}}} & = {\ boldsymbol {c_ {N}}}, \ end {align}} }$

som innebærer det

${\ displaystyle {\ begin {align} {\ boldsymbol {\ lambda}} & = ({\ boldsymbol {B}} ^ {\ mathrm {T}}) ^ {- 1} {\ boldsymbol {c_ {B}} }, \\ {\ boldsymbol {s_ {N}}} & = {\ boldsymbol {c_ {N}}} - {\ boldsymbol {N}} ^ {\ mathrm {T}} {\ boldsymbol {\ lambda}} . \ end {align}}}$

Hvis s _N ≥ 0 på dette punktet, er KKT-forholdene oppfylt, og dermed er x optimal.

Dreieoperasjon

Dersom KKT betingelser er brutt, en dreieoperasjon som består av innføring av en søyle av N til basis på bekostning av en eksisterende kolonne i B utføres. I fravær av degenerasjon resulterer en dreieoperasjon alltid i en streng reduksjon i c ^T x . Derfor, hvis problemet er avgrenset, må den reviderte simpleksmetoden avsluttes ved et optimalt toppunkt etter gjentatte svingoperasjoner fordi det bare er et endelig antall hjørner.

Velg en indeks m < q ≤ n slik at s _q <0 som inngående indeks . Den tilsvarende kolonnen med A , A _q , vil bli flyttet til grunnlaget, og x _q vil få lov til å øke fra null. Det kan vises

${\ displaystyle {\ frac {\ partial ({\ boldsymbol {c}} ^ {\ mathrm {T}} {\ boldsymbol {x}})} {\ partial x_ {q}}} = s_ {q},}$

dvs. at hver enhetsøkning i x _q resulterer i en reduksjon med - s _q i c ^T x . Siden

${\ displaystyle {\ boldsymbol {Bx_ {B}}} + {\ boldsymbol {A}} _ {q} x_ {q} = {\ boldsymbol {b}},}$

x _B må tilsvarende reduseres med Δ x _B = B ⁻¹ A _q x _q underlagt x _B - Δ x _B ≥ 0 . La d = B ⁻¹ A _q . Hvis d ≤ 0 , uansett hvor mye x _q økes, forblir x _B - Δ x _B ikke-negativ. Derfor kan c ^T x reduseres vilkårlig, og dermed er problemet ubegrenset. Hvis ikke, velger en indeks p = argmin _{1≤ i ≤ m} { x _I / d _i | d _i > 0} som avgangsindeks . Dette valget øker effektivt x _q fra null til x _p reduseres til null mens man opprettholder muligheten. Svinge operasjonen avsluttes med å erstatte A _p med A _Q i grunnlaget.

Numerisk eksempel

Vurder et lineært program hvor

${\ displaystyle {\ begin {align} {\ boldsymbol {c}} & = {\ begin {bmatrix} -2 & -3 & -4 & 0 & 0 \ end {bmatrix}} ^ {\ mathrm {T}}, \\ {\ boldsymbol {A}} & = {\ begin {bmatrix} 3 & 2 & 1 & 1 & 0 \\ 2 & 5 & 3 & 0 & 1 \ end {bmatrix}}, \\ {\ boldsymbol {b}} & = {\ begin {bmatrix} 10 \\ 15 \ end {bmatrix}} . \ end {align}}}$

La

${\ displaystyle {\ begin {align} {\ boldsymbol {B}} & = {\ begin {bmatrix} {\ boldsymbol {A}} _ {4} og {\ boldsymbol {A}} _ {5} \ end { bmatrix}}, \\ {\ boldsymbol {N}} & = {\ begin {bmatrix} {\ boldsymbol {A}} _ {1} & {\ boldsymbol {A}} _ {2} og {\ boldsymbol {A }} _ {3} \ end {bmatrix}} \ end {justert}}}$

å begynne med, noe som tilsvarer en mulig topp-punkt x = [0 0 0 10 15] ^T . I dette øyeblikk,

${\ displaystyle {\ begin {align} {\ boldsymbol {\ lambda}} & = {\ begin {bmatrix} 0 & 0 \ end {bmatrix}} ^ {\ mathrm {T}}, \\ {\ boldsymbol {s_ {N }}} & = {\ begin {bmatrix} -2 & -3 & -4 \ end {bmatrix}} ^ {\ mathrm {T}}. \ end {justert}}}$

Velg q = 3 som inngangsindeks. Deretter d = [1 3] ^T , som betyr en enhetsøkning i x ₃ resulterer i at x ₄ og x ₅ reduseres med henholdsvis 1 og 3 . Derfor økes x ₃ til 5 , hvor x ₅ reduseres til null, og p = 5 blir den forlate indeksen.

Etter dreieoperasjonen,

${\ displaystyle {\ begin {align} {\ boldsymbol {B}} & = {\ begin {bmatrix} {\ boldsymbol {A}} _ {3} og {\ boldsymbol {A}} _ {4} \ end { bmatrix}}, \\ {\ boldsymbol {N}} & = {\ begin {bmatrix} {\ boldsymbol {A}} _ {1} og {\ boldsymbol {A}} _ {2} og {\ boldsymbol {A }} _ {5} \ end {bmatrix}}. \ End {justert}}}$

Tilsvarende

${\ displaystyle {\ begin {align} {\ boldsymbol {x}} & = {\ begin {bmatrix} 0 & 0 & 5 & 5 & 0 \ end {bmatrix}} ^ {\ mathrm {T}}, \\ {\ boldsymbol {\ lambda}} & = {\ begin {bmatrix} 0 & -4 / 3 \ end {bmatrix}} ^ {\ mathrm {T}}, \\ {\ boldsymbol {s_ {N}}} & = {\ begin {bmatrix} 2 / 3 & 11/3 & 4/3 \ end {bmatrix}} ^ {\ mathrm {T}}. \ End {justert}}}$

Et positivt s _N indikerer at x nå er optimal.

Praktiske spørsmål

Degenerasjon

Fordi den reviderte simpleksmetoden er matematisk ekvivalent med simplex-metoden, lider den også av degenerasjon, der en pivotoperasjon ikke resulterer i en reduksjon i c ^T x , og en kjede av pivotoperasjoner får grunnlaget til å sykle. En forstyrrelse eller leksikografisk strategi kan brukes til å forhindre sykling og garantere avslutning.

Grunnrepresentasjon

To typer lineære systemer som involverer B er til stede i den reviderte simpleksmetoden:

${\ displaystyle {\ begin {align} {\ boldsymbol {Bz}} & = {\ boldsymbol {y}}, \\ {\ boldsymbol {B}} ^ {\ mathrm {T}} {\ boldsymbol {z}} & = {\ boldsymbol {y}}. \ end {align}}}$

I stedet for å omfaktorisere B , blir en LU-faktorisering vanligvis oppdatert direkte etter hver dreieoperasjon, for hvilket formål det finnes flere strategier som Forrest-Tomlin og Bartels-Golub-metodene. Mengden data som representerer oppdateringene, samt numeriske feil, bygger seg imidlertid opp over tid og gjør periodisk refaktorisering nødvendig.

Merknader og referanser

Merknader

Referanser

Bibliografi