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

はじめに

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

標準形、主問題

\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}