Revidovaná simplexní metoda - Revised simplex method - Wikipedia

v matematická optimalizace, revidovaná simplexní metoda je varianta George Dantzig je simplexní metoda pro lineární programování.

Revidovaná simplexní metoda je matematicky ekvivalentní standardní simplexní metodě, ale liší se v implementaci. Namísto udržování tabla, které výslovně představuje omezení upravená na sadu základních proměnných, udržuje reprezentaci základ z matice představující omezení. Maticově orientovaný přístup umožňuje větší výpočetní efektivitu umožněním řídkých maticových operací.^[1]

Formulace problému

Ve zbývající části diskuse se předpokládá, že problém lineárního programování byl převeden do následující standardní formy:

${ displaystyle { begin {pole} {rl} { text {minimalizovat}} & { boldsymbol {c}} ^ { mathrm {T}} { boldsymbol {x}} { text {předmětem }} & { boldsymbol {Ax}} = { boldsymbol {b}}, { boldsymbol {x}} geq { boldsymbol {0}} end {pole}}}$

kde A ∈ R^m×n. Bez ztráty obecnosti se předpokládá, že matice omezení A má celou řadu a že problém je proveditelný, tj. existuje alespoň jeden X ≥ 0 takhle Sekera = b. Li A má nedostatek hodnocení, buď existují nadbytečná omezení, nebo je problém neproveditelný. Obě situace mohou být vyřešeny předem připraveným krokem.

Algoritmický popis

Podmínky optimality

Pro lineární programování je Karush – Kuhn – Tuckerovy podmínky jsou oba nezbytné a dostatečné pro optimalitu. Podmínky KKT problému lineárního programování ve standardní formě jsou

${ displaystyle { begin {aligned} { 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 {zarovnáno}}}$

kde λ a s jsou Lagrangeovy multiplikátory spojené s omezeními Sekera = b a X ≥ 0, resp.^[2] Poslední podmínka, která je ekvivalentní k s_iX_i = 0 pro všechny 1 < i < n, se nazývá podmínka doplňkové ochablosti.

Tím, co je někdy známé jako základní věta lineárního programování, vrchol X proveditelného polytopu lze identifikovat jako základ B z A vybráno z jeho sloupců.^[A] Od té doby A má plnou hodnost, B je nesmyslná. Předpokládejme, že bez ztráty obecnosti A = [B N]. Pak X darováno

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

kde X_B ≥ 0. Rozdělit C a s podle toho do

${ displaystyle { begin {aligned} { boldsymbol {c}} & = { begin {bmatrix} { boldsymbol {c_ {B}}} { boldsymbol {c_ {N}}} end {bmatrix }}, { boldsymbol {s}} & = { begin {bmatrix} { boldsymbol {s_ {B}}} { boldsymbol {s_ {N}}} end {bmatrix}}. konec {zarovnáno}}}$

Abychom splnili podmínku doplňkové ochablosti, dovolte s_B = 0. Z toho vyplývá, že

${ displaystyle { begin {aligned} { boldsymbol {B}} ^ { mathrm {T}} { boldsymbol { lambda}} & = { boldsymbol {c_ {B}}}, { boldsymbol {N}} ^ { mathrm {T}} { boldsymbol { lambda}} + { boldsymbol {s_ {N}}} & = { boldsymbol {c_ {N}}}, end {zarovnáno}} }$

což z toho vyplývá

${ displaystyle { begin {aligned} { boldsymbol { lambda}} & = ({ boldsymbol {B}} ^ { mathrm {T}}) ^ {- 1} { boldsymbol {c_ {B}} }, { boldsymbol {s_ {N}}} & = { boldsymbol {c_ {N}}} - { boldsymbol {N}} ^ { mathrm {T}} { boldsymbol { lambda}} . end {zarovnáno}}}$

Li s_N ≥ 0 v tomto okamžiku jsou podmínky KKT splněny, a tedy X je optimální.

Otočná operace

Pokud dojde k porušení podmínek KKT, a otočná operace spočívající v zavedení sloupce N do základu na úkor existujícího sloupce v B se provádí. V nepřítomnosti zvrhlost, operace otočení vždy vede k přísnému snížení C^TX. Pokud je tedy problém omezený, musí být revidovaná simplexní metoda ukončena na optimálním vrcholu po opakovaných operacích otáčení, protože existuje pouze konečný počet vrcholů.^[4]

Vyberte rejstřík m < q ≤ n takhle s_q < 0 jako zadávání indexu. Odpovídající sloupec A, A_q, budou přesunuty do základny a X_q se bude moci zvyšovat od nuly. To lze ukázat

${ displaystyle { frac { částečné ({ boldsymbol {c}} ^ { mathrm {T}} { boldsymbol {x}})}} { částečné x_ {q}}} = s_ {q},}$

tj. každá jednotka se zvýší o X_q má za následek pokles o −s_q v C^TX.^[5] Od té doby

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

X_B musí být odpovídajícím způsobem sníženo o ΔX_B = B⁻¹A_qX_q podléhá X_B - ΔX_B ≥ 0. Nechat d = B⁻¹A_q. Li d ≤ 0, bez ohledu na to, kolik X_q je zvýšena, X_B - ΔX_B zůstane negativní. Proto, C^TX lze libovolně snížit, a tím je problém neomezený. Jinak vyberte index p = argmin_1≤i≤m {X_i/d_i | d_i > 0} jako opouštějící index. Tato volba se efektivně zvyšuje X_q od nuly do X_p se sníží na nulu při zachování proveditelnosti. Pivotní operace končí výměnou A_p s A_q v základu.

Numerický příklad

Zvažte lineární program, kde

${ displaystyle { begin {aligned} { 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 {zarovnáno}}}$

Nechat

${ displaystyle { begin {aligned} { boldsymbol {B}} & = { begin {bmatrix} { boldsymbol {A}} _ {4} & { boldsymbol {A}} _ {5} end { bmatrix}}, { boldsymbol {N}} & = { begin {bmatrix} { boldsymbol {A}} _ {1} & { boldsymbol {A}} _ {2} & { boldsymbol {A }} _ {3} end {bmatrix}} end {zarovnáno}}}$

zpočátku, což odpovídá proveditelnému vrcholu X = [0 0 0 10 15]^T. Nyní,

${ displaystyle { begin {aligned} { boldsymbol { lambda}} & = { begin {bmatrix} 0 & 0 end {bmatrix}} ^ { mathrm {T}}, { boldsymbol {s_ {N }}} & = { begin {bmatrix} -2 & -3 & -4 end {bmatrix}} ^ { mathrm {T}}. end {zarovnáno}}}$

Vybrat q = 3 jako vstupní index. Pak d = [1 3]^T, což znamená jednotkový nárůst v X₃ výsledky v X₄ a X₅ se snižuje o 1 a 3, resp. Proto, X₃ se zvyšuje na 5, na kterém místě X₅ se sníží na nulu a p = 5 se stává odcházejícím indexem.

Po otočné operaci

${ displaystyle { begin {aligned} { boldsymbol {B}} & = { begin {bmatrix} { boldsymbol {A}} _ {3} & { boldsymbol {A}} _ {4} end { bmatrix}}, { boldsymbol {N}} & = { begin {bmatrix} { boldsymbol {A}} _ {1} & { boldsymbol {A}} _ {2} & { boldsymbol {A }} _ {5} end {bmatrix}}. End {zarovnáno}}}$

Odpovídajícím způsobem,

${ displaystyle { begin {aligned} { boldsymbol {x}} & = { begin {bmatrix} 0 a 0 a 5 a 5 & 0 end {bmatrix}} ^ { mathrm {T}}, { boldsymbol { lambda}} & = { begin {bmatrix} 0 & -4 / 3 end {bmatrix}} ^ { mathrm {T}}, { boldsymbol {s_ {N}}} & = { begin {bmatrix} 2 / 3 a 11/3 a 4/3 end {bmatrix}} ^ { mathrm {T}}. End {zarovnáno}}}$

Pozitivní s_N naznačuje to X je nyní optimální.

Praktické problémy

Degenerace

Protože revidovaná simplexní metoda je matematicky ekvivalentní simplexové metodě, také trpí degenerací, kde operace otočení nevede ke snížení C^TXa řetězec pivotních operací způsobí, že základna bude cyklovat. K zabránění cyklování a zaručení ukončení lze použít odchylku nebo lexikografickou strategii.^[6]

Základní reprezentace

Dva typy lineární systémy zahrnující B jsou přítomny v revidované simplexní metodě:

${ displaystyle { begin {aligned} { boldsymbol {Bz}} & = { boldsymbol {y}}, { boldsymbol {B}} ^ { mathrm {T}} { boldsymbol {z}} & = { boldsymbol {y}}. end {zarovnáno}}}$

Místo refaktorování B, obvykle Faktorizace LU je přímo aktualizován po každé pivotní operaci, pro kterou existuje několik strategií, jako jsou metody Forrest-Tomlin a Bartels-Golub. Množství dat představujících aktualizace i numerické chyby se však postupem času hromadí a je nezbytná pravidelná refaktorizace.^[1][7]

Poznámky a odkazy

Poznámky

Reference

Bibliografie