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

はじめに

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

標準形、主問題

$\begin{array}{r} \begin{array}{c} minimize & c^{⊤} x \\ subject to & A x = b \\ x \geq 0 \end{array} \end{array}$

$\begin{aligned} 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{aligned}$

$\begin{aligned} c^{⊤} 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{aligned}$

標準形、双対問題

$\begin{array}{r} \begin{array}{c} maximize & b^{⊤} y \\ subject to & A^{⊤} y + z = c \\ z \geq 0 \end{array} \end{array}$

$\begin{aligned} A^{⊤} y + z & = b \\ A_{B}^{⊤} y + z_{B} & = c_{B} \\ A_{N}^{⊤} y + z_{N} & = c_{N} \end{aligned}$

$\begin{aligned} A_{B}^{⊤} y + z_{B} & = c_{B} \\ y & = (A_{B}^{⊤})^{- 1} c_{B} - (A_{B}^{⊤})^{- 1} z_{B} \end{aligned}$

$\begin{aligned} A_{N}^{⊤} y + z_{N} & = c_{N} \\ A_{N}^{⊤} ((A_{B}^{⊤})^{- 1} c_{B} - (A_{B}^{⊤})^{- 1} z_{B}) + z_{N} & = c_{N} \end{aligned}$

$\begin{aligned} z_{N} & = (c_{N} - A_{N}^{⊤} (A_{B}^{⊤})^{- 1} c_{B}) + A_{N}^{⊤} (A_{B}^{⊤})^{- 1} z_{B} \end{aligned}$

$\begin{aligned} b^{⊤} y & = b^{⊤} ((A_{B}^{⊤})^{- 1} c_{B} - (A_{B}^{⊤})^{- 1} z_{B}) \\ = b^{⊤} (A_{B}^{⊤})^{- 1} c_{B} - b^{⊤} (A_{B}^{⊤})^{- 1} z_{B} \end{aligned}$

一般形

$\begin{array}{r} \begin{array}{c} minimize & g^{⊤} x + h^{⊤} y \\ subject to & A x + B y = e \\ C x + D y + z = f \\ x, z \geq 0 \end{array} \end{array}$

$\begin{aligned} (\begin{array}{c} A & B & O \\ C & D & I \end{array}) (\begin{array}{c} x \\ y \\ z \end{array}) & = (\begin{array}{c} e \\ f \end{array}) \\ (\begin{array}{c} 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{array}) (\begin{array}{c} x_{B_{R}} \\ x_{N_{R}} \\ y \\ z_{B} \\ z_{N} \end{array}) & = (\begin{array}{c} e \\ f_{B_{R}} \\ f_{N_{R}} \end{array}) \end{aligned}$

$\begin{aligned} (\begin{array}{c} A_{B_{C}} & A_{N_{C}} & B & O \\ C_{B_{R} B_{C}} & C_{B_{R} N_{C}} & D_{B_{R}} & I \end{array}) (\begin{array}{c} x_{B_{R}} \\ x_{N_{R}} \\ y \\ z_{B} \end{array}) & = (\begin{array}{c} e \\ f_{B_{R}} \end{array}) \\ (\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array}) (\begin{array}{c} x_{B_{R}} \\ y \end{array}) + (\begin{array}{c} A_{N_{C}} & O \\ C_{B_{R} N_{C}} & I \end{array}) (\begin{array}{c} x_{N_{R}} \\ z_{B} \end{array}) & = (\begin{array}{c} e \\ f_{B_{R}} \end{array}) \end{aligned}$

$\begin{aligned} (\begin{array}{c} x_{B_{R}} \\ y \end{array}) & = {(\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array})}^{- 1} (\begin{array}{c} e \\ f_{B_{R}} \end{array}) - {(\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array})}^{- 1} (\begin{array}{c} A_{N_{C}} & O \\ C_{B_{R} N_{C}} & I \end{array}) (\begin{array}{c} x_{N_{R}} \\ z_{B} \end{array}) \end{aligned}$

$\begin{aligned} (\begin{array}{c} C_{N_{R} B_{C}} & C_{N_{R} N_{C}} & D_{N_{R}} & I \end{array}) (\begin{array}{c} x_{B_{R}} \\ x_{N_{R}} \\ y \\ z_{N} \end{array}) & = f_{N_{R}} \\ (\begin{array}{c} C_{N_{R} B_{C}} & D_{N_{R}} \end{array}) (\begin{array}{c} x_{B_{R}} \\ y \end{array}) + C_{N_{R} N_{C}} x_{N_{R}} + z_{N} & = f_{N_{R}} \\ (\begin{array}{c} C_{N_{R} B_{C}} & D_{N_{R}} \end{array}) ({(\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array})}^{- 1} (\begin{array}{c} e \\ f_{B_{R}} \end{array}) - {(\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array})}^{- 1} (\begin{array}{c} A_{N_{C}} & O \\ C_{B_{R} N_{C}} & I \end{array}) (\begin{array}{c} x_{N_{R}} \\ z_{B} \end{array})) + C_{N_{R} N_{C}} x_{N_{R}} + z_{N} & = f_{N_{R}} \\ (\begin{array}{c} C_{N_{R} B_{C}} & D_{N_{R}} \end{array}) {(\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array})}^{- 1} (\begin{array}{c} e \\ f_{B_{R}} \end{array}) - (\begin{array}{c} C_{N_{R} B_{C}} & D_{N_{R}} \end{array}) {(\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array})}^{- 1} (\begin{array}{c} A_{N_{C}} & O \\ C_{B_{R} N_{C}} & I \end{array}) (\begin{array}{c} x_{N_{R}} \\ z_{B} \end{array}) + C_{N_{R} N_{C}} x_{N_{R}} + z_{N} & = f_{N_{R}} \end{aligned}$

$\begin{aligned} z_{N} & = (f_{N_{R}} - (\begin{array}{c} C_{N_{R} B_{C}} & D_{N_{R}} \end{array}) {(\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array})}^{- 1} (\begin{array}{c} e \\ f_{B_{R}} \end{array})) + (\begin{array}{c} C_{N_{R} B_{C}} & D_{N_{R}} \end{array}) {(\begin{array}{c} A_{B_{C}} & B \\ C_{B_{R} B_{C}} & D_{B_{R}} \end{array})}^{- 1} (\begin{array}{c} A_{N_{C}} & O \\ C_{B_{R} N_{C}} & I \end{array}) (\begin{array}{c} x_{N_{R}} \\ z_{B} \end{array}) - C_{N_{R} N_{C}} x_{N_{R}} \end{aligned}$

何形？

$\begin{array}{r} \begin{array}{c} minimize & e^{⊤} x \\ subject to & A x = c \\ B x + y = d \\ x, y \geq 0 \end{array} \end{array}$

$\begin{aligned} (\begin{array}{c} A & O \\ B & I \end{array}) (\begin{array}{c} x \\ y \end{array}) & = (\begin{array}{c} c \\ d \end{array}) \\ (\begin{array}{c} 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{array}) (\begin{array}{c} x_{B_{C}} \\ x_{N_{C}} \\ y_{B_{R}} \\ y_{N_{R}} \end{array}) & = (\begin{array}{c} c \\ d_{B_{R}} \\ d_{B_{R}} \end{array}) \end{aligned}$

$\begin{aligned} (\begin{array}{c} A_{B_{C}} & A_{N_{C}} & O & O \\ B_{B_{R} B_{C}} & B_{B_{R} N_{C}} & I & O \end{array}) (\begin{array}{c} x_{B_{C}} \\ x_{N_{C}} \\ y_{B_{R}} \\ y_{N_{R}} \end{array}) & = (\begin{array}{c} c \\ d_{B_{R}} \end{array}) \\ (\begin{array}{c} A_{B_{C}} \\ B_{B_{R} B_{C}} \end{array}) (\begin{array}{c} x_{B_{C}} \end{array}) + (\begin{array}{c} A_{N_{C}} & O \\ B_{B_{R} N_{C}} & I \end{array}) (\begin{array}{c} x_{N_{C}} \\ y_{B_{R}} \end{array}) & = (\begin{array}{c} c \\ d_{B_{R}} \end{array}) \end{aligned}$

$\begin{aligned} x_{B_{C}} & = {(\begin{array}{c} A_{B_{C}} \\ B_{B_{R} B_{C}} \end{array})}^{- 1} (\begin{array}{c} c \\ d_{B_{R}} \end{array}) - {(\begin{array}{c} A_{B_{C}} \\ B_{B_{R} B_{C}} \end{array})}^{- 1} (\begin{array}{c} A_{N_{C}} & O \\ B_{B_{R} N_{C}} & I \end{array}) (\begin{array}{c} x_{N_{C}} \\ y_{B_{R}} \end{array}) \\ = (\begin{array}{c} M_{1} & M_{2} \end{array}) (\begin{array}{c} c \\ d_{B_{R}} \end{array}) - (\begin{array}{c} M_{1} & M_{2} \end{array}) (\begin{array}{c} A_{N_{C}} & O \\ B_{B_{R} N_{C}} & I \end{array}) (\begin{array}{c} x_{N_{C}} \\ y_{B_{R}} \end{array}) \\ = (M_{1} c + M_{2} d_{B_{R}}) - (M_{1} A_{N_{C}} + M_{2} B_{B_{R} N_{C}}) x_{N_{C}} - M_{2} y_{B_{R}} \end{aligned}$

$\begin{aligned} (\begin{array}{c} B_{N_{R} B_{C}} & B_{N_{R} N_{C}} & O & I \end{array}) (\begin{array}{c} x_{B_{C}} \\ x_{N_{C}} \\ y_{B_{R}} \\ y_{N_{R}} \end{array}) & = (\begin{array}{c} d_{B_{R}} \end{array}) \\ B_{N_{R} B_{C}} x_{B_{C}} + B_{N_{R} N_{C}} x_{N_{C}} + y_{N_{R}} & = d_{B_{R}} \end{aligned}$

$\begin{aligned} 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}} ((M_{1} c + M_{2} d_{B_{R}}) - (M_{1} A_{N_{C}} + M_{2} B_{B_{R} N_{C}}) x_{N_{C}} - M_{2} y_{B_{R}}) - B_{N_{R} N_{C}} x_{N_{C}} \\ = (d_{B_{R}} - B_{N_{R} B_{C}} (M_{1} c + M_{2} d_{B_{R}})) + (B_{N_{R} B_{C}} (M_{1} A_{N_{C}} + M_{2} B_{B_{R} N_{C}}) - B_{N_{R} N_{C}}) x_{N_{C}} + B_{N_{R} B_{C}} M_{2} y_{B_{R}} \end{aligned}$

$\begin{aligned} (\begin{array}{c} x_{B_{C}} \\ y_{N_{R}} \end{array}) & = (\begin{array}{c} M_{1} c + M_{2} d_{B_{R}} \\ d_{B_{R}} - B_{N_{R} B_{C}} (M_{1} c + M_{2} d_{B_{R}}) \end{array}) - (\begin{array}{c} (M_{1} A_{N_{C}} + M_{2} B_{B_{R} N_{C}}) & B_{N_{R} N_{C}} - B_{N_{R} B_{C}} (M_{1} A_{N_{C}} + M_{2} B_{B_{R} N_{C}}) \\ M_{2} y_{B_{R}} & - B_{N_{R} B_{C}} M_{2} \end{array}) (\begin{array}{c} x_{N_{C}} \\ y_{B_{R}} \end{array}) \end{aligned}$

投稿日：2023年1月22日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

seytwo

4961

他の人のコメント

コメントはありません。

読み込み中

seytwo

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

はじめに
標準形、主問題
標準形、双対問題
一般形
何形？