1

シンプレックス法の式変形まとめ

19
0
$$$$

はじめに

自分用の備忘録です。一般形で簡潔にまとめる方法をご存じでしたらお教えいただけますと幸いです。

標準形、主問題

\begin{align} \begin{matrix} \text{minimize} & c^\top x \\ \text{subject to} & A x = b \\ & x \geq 0 \end{matrix} \end{align}

\begin{align} A x &= b \\ A_B x_B + A_N x_N &= b \\ x_B &= A_B^{-1} b - A_B^{-1} A_N x_N \end{align}

\begin{align} c^\top x &= c_B x_B + c_N x_N \\ &= c_B (A_B^{-1} b - A_B^{-1} A_N x_N) + c_N x_N \\ &= c_B A_B^{-1} b + (c_N - c_B A_B^{-1} A_N x_N) x_N \end{align}

標準形、双対問題

\begin{align} \begin{matrix} \text{maximize} & b^\top y \\ \text{subject to} & A^\top y + z = c \\ & z \geq 0 \end{matrix} \end{align}

\begin{align} A^\top y + z &= b \\ A_B^\top y + z_B &= c_B \\ A_N^\top y + z_N &= c_N \end{align}

\begin{align} A_B^\top y + z_B &= c_B \\ y &= (A_B^\top)^{-1} c_B - (A_B^\top)^{-1} z_B \end{align}

\begin{align} A_N^\top y + z_N &= c_N \\ A_N^\top ((A_B^\top)^{-1} c_B - (A_B^\top)^{-1} z_B) + z_N &= c_N \end{align}

\begin{align} z_N &= (c_N - A_N^\top (A_B^\top)^{-1} c_B) + A_N^\top (A_B^\top)^{-1} z_B \\ \end{align}

\begin{align} b^\top y &= b^\top ((A_B^\top)^{-1} c_B - (A_B^\top)^{-1} z_B) \\ &= b^\top (A_B^\top)^{-1} c_B - b^\top (A_B^\top)^{-1} z_B \end{align}

一般形

\begin{align} \begin{matrix} \text{minimize} & g^\top x + h^\top y \\ \text{subject to} & A x + B y = e \\ & C x + D y + z = f \\ & x, z \geq 0 \end{matrix} \end{align}

\begin{align} \begin{pmatrix} A & B & O \\ C & D & I \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} &= \begin{pmatrix} e \\ f \end{pmatrix} \\ \begin{pmatrix} A_{B_C} & A_{N_C} & B & O & O \\ C_{B_R B_C} & C_{B_R N_C} & D_{B_R} & I & O \\ C_{N_R B_C} & C_{N_R N_C} & D_{N_R} & O & I \end{pmatrix} \begin{pmatrix} x_{B_R} \\ x_{N_R} \\ y \\ z_B \\ z_N \end{pmatrix} &= \begin{pmatrix} e \\ f_{B_R} \\ f_{N_R} \end{pmatrix} \end{align}

\begin{align} \begin{pmatrix} A_{B_C} & A_{N_C} & B & O \\ C_{B_R B_C} & C_{B_R N_C} & D_{B_R} & I \end{pmatrix} \begin{pmatrix} x_{B_R} \\ x_{N_R} \\ y \\ z_B \end{pmatrix} &= \begin{pmatrix} e \\ f_{B_R} \end{pmatrix} \\ \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix} \begin{pmatrix} x_{B_R} \\ y \end{pmatrix} + \begin{pmatrix} A_{N_C} & O \\ C_{B_R N_C} & I \end{pmatrix} \begin{pmatrix} x_{N_R} \\ z_B \end{pmatrix} &= \begin{pmatrix} e \\ f_{B_R} \end{pmatrix} \end{align}

\begin{align} \begin{pmatrix} x_{B_R} \\ y \end{pmatrix} &= \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix}^{-1} \begin{pmatrix} e \\ f_{B_R} \end{pmatrix} - \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix}^{-1} \begin{pmatrix} A_{N_C} & O \\ C_{B_R N_C} & I \end{pmatrix} \begin{pmatrix} x_{N_R} \\ z_B \end{pmatrix} \end{align}

\begin{align} \begin{pmatrix} C_{N_R B_C} & C_{N_R N_C} & D_{N_R} & I \end{pmatrix} \begin{pmatrix} x_{B_R} \\ x_{N_R} \\ y \\ z_N \end{pmatrix} &= f_{N_R} \\ \begin{pmatrix} C_{N_R B_C} & D_{N_R} \end{pmatrix} \begin{pmatrix} x_{B_R} \\ y \end{pmatrix} + C_{N_R N_C} x_{N_R} + z_N &= f_{N_R} \\ \begin{pmatrix} C_{N_R B_C} & D_{N_R} \end{pmatrix} \left( \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix}^{-1} \begin{pmatrix} e \\ f_{B_R} \end{pmatrix} - \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix}^{-1} \begin{pmatrix} A_{N_C} & O \\ C_{B_R N_C} & I \end{pmatrix} \begin{pmatrix} x_{N_R} \\ z_B \end{pmatrix} \right) + C_{N_R N_C} x_{N_R} + z_N &= f_{N_R} \\ \begin{pmatrix} C_{N_R B_C} & D_{N_R} \end{pmatrix} \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix}^{-1} \begin{pmatrix} e \\ f_{B_R} \end{pmatrix} - \begin{pmatrix} C_{N_R B_C} & D_{N_R} \end{pmatrix} \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix}^{-1} \begin{pmatrix} A_{N_C} & O \\ C_{B_R N_C} & I \end{pmatrix} \begin{pmatrix} x_{N_R} \\ z_B \end{pmatrix} + C_{N_R N_C} x_{N_R} + z_N &= f_{N_R} \end{align}

\begin{align} z_N &= \left( f_{N_R} - \begin{pmatrix} C_{N_R B_C} & D_{N_R} \end{pmatrix} \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix}^{-1} \begin{pmatrix} e \\ f_{B_R} \end{pmatrix} \right) + \begin{pmatrix} C_{N_R B_C} & D_{N_R} \end{pmatrix} \begin{pmatrix} A_{B_C} & B \\ C_{B_R B_C} & D_{B_R} \end{pmatrix}^{-1} \begin{pmatrix} A_{N_C} & O \\ C_{B_R N_C} & I \end{pmatrix} \begin{pmatrix} x_{N_R} \\ z_B \end{pmatrix} - C_{N_R N_C} x_{N_R} \end{align}

何形?

\begin{align} \begin{matrix} \text{minimize} & e^\top x \\ \text{subject to} & A x = c \\ & B x + y = d \\ & x, y \geq 0 \end{matrix} \end{align}

\begin{align} \begin{pmatrix} A & O \\ B & I \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} &= \begin{pmatrix} c \\ d \end{pmatrix} \\ \begin{pmatrix} A_{B_C} & A_{N_C} & O & O \\ B_{B_R B_C} & B_{B_R N_C} & I & O \\ B_{N_R B_C} & B_{N_R N_C} & O & I \\ \end{pmatrix} \begin{pmatrix} x_{B_C} \\ x_{N_C} \\ y_{B_R} \\ y_{N_R} \end{pmatrix} &= \begin{pmatrix} c \\ d_{B_R} \\ d_{B_R} \end{pmatrix} \end{align}

\begin{align} \begin{pmatrix} A_{B_C} & A_{N_C} & O & O \\ B_{B_R B_C} & B_{B_R N_C} & I & O \end{pmatrix} \begin{pmatrix} x_{B_C} \\ x_{N_C} \\ y_{B_R} \\ y_{N_R} \end{pmatrix} &= \begin{pmatrix} c \\ d_{B_R} \end{pmatrix} \\ \begin{pmatrix} A_{B_C} \\ B_{B_R B_C} \end{pmatrix} \begin{pmatrix} x_{B_C} \end{pmatrix} + \begin{pmatrix} A_{N_C} & O \\ B_{B_R N_C} & I \end{pmatrix} \begin{pmatrix} x_{N_C} \\ y_{B_R} \end{pmatrix} &= \begin{pmatrix} c \\ d_{B_R} \end{pmatrix} \end{align}

\begin{align} x_{B_C} &= \begin{pmatrix} A_{B_C} \\ B_{B_R B_C} \end{pmatrix}^{-1} \begin{pmatrix} c \\ d_{B_R} \end{pmatrix} - \begin{pmatrix} A_{B_C} \\ B_{B_R B_C} \end{pmatrix}^{-1} \begin{pmatrix} A_{N_C} & O \\ B_{B_R N_C} & I \end{pmatrix} \begin{pmatrix} x_{N_C} \\ y_{B_R} \end{pmatrix} \\ &= \begin{pmatrix} M_1 & M_2 \end{pmatrix} \begin{pmatrix} c \\ d_{B_R} \end{pmatrix} - \begin{pmatrix} M_1 & M_2 \end{pmatrix} \begin{pmatrix} A_{N_C} & O \\ B_{B_R N_C} & I \end{pmatrix} \begin{pmatrix} x_{N_C} \\ y_{B_R} \end{pmatrix} \\ &= \left( M_1 c + M_2 d_{B_R} \right) - \left( M_1 A_{N_C} + M_2 B_{B_R N_C} \right) x_{N_C} - M_2 y_{B_R} \end{align}

\begin{align} \begin{pmatrix} B_{N_R B_C} & B_{N_R N_C} & O & I \\ \end{pmatrix} \begin{pmatrix} x_{B_C} \\ x_{N_C} \\ y_{B_R} \\ y_{N_R} \end{pmatrix} &= \begin{pmatrix} d_{B_R} \end{pmatrix} \\ B_{N_R B_C} x_{B_C} + B_{N_R N_C} x_{N_C} + y_{N_R} &= d_{B_R} \\ \end{align}

\begin{align} y_{N_R} &= d_{B_R} - B_{N_R B_C} x_{B_C} - B_{N_R N_C} x_{N_C} \\ &= d_{B_R} - B_{N_R B_C} \left( \left( M_1 c + M_2 d_{B_R} \right) - \left( M_1 A_{N_C} + M_2 B_{B_R N_C} \right) x_{N_C} - M_2 y_{B_R} \right) - B_{N_R N_C} x_{N_C} \\ &= \left( d_{B_R} - B_{N_R B_C} \left( M_1 c + M_2 d_{B_R} \right) \right) + \left( B_{N_R B_C} \left( M_1 A_{N_C} + M_2 B_{B_R N_C} \right) - B_{N_R N_C} \right) x_{N_C} + B_{N_R B_C} M_2 y_{B_R} \\ \end{align}

\begin{align} \begin{pmatrix} x_{B_C} \\ y_{N_R} \end{pmatrix} &= \begin{pmatrix} M_1 c + M_2 d_{B_R} \\ d_{B_R} - B_{N_R B_C} \left( M_1 c + M_2 d_{B_R} \right) \end{pmatrix} - \begin{pmatrix} \left( M_1 A_{N_C} + M_2 B_{B_R N_C} \right) & B_{N_R N_C} - B_{N_R B_C} \left( M_1 A_{N_C} + M_2 B_{B_R N_C} \right) \\ M_2 y_{B_R} & - B_{N_R B_C} M_2 \end{pmatrix} \begin{pmatrix} x_{N_C} \\ y_{B_R} \end{pmatrix} \end{align}

投稿日:2023122

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

seytwo
12
3102

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中