📂最適化理論

線形計画法における辞書と表

ノーテーション

$$\begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix}$$

matrix $A \in \mathbb{R}^{m \times n}$、$\mathbf{b} \in \mathbb{R}^{m \times 1}$、$\mathbf{c} \in \mathbb{R}^{n}$について、linear programming problemが上記のようなequation formで示されるとする。そして、その成分を以下のように記述しよう。 $$\begin{align*} A =& \left( a_{ij} \right) \\ \mathbf{b} =& \left( b_{1} , \cdots , b_{m} \right) \\ \mathbf{c} =& \left( c_{1} , \cdots , c_{n} \right) \\ \mathbf{x} =& \left( x_{1} , \cdots , x_{n} \right) \end{align*}$$

ディクショナリ ¹

$i = 1 , \cdots , m$について、以下の形の連立方程式をディクショナリと呼ぶ。 $$\begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*}$$

$\zeta$を除く左辺の変数を基底変数、右辺の変数を非基底変数と呼ぶ。まず、これらのインデックスを $$\begin{align*} \mathcal{B} :=& \left\{ n+1 , n+2 , \cdots , n+m \right\} \\ \mathcal{N} :=& \left\{ 1 , 2 , \cdots , n \right\} \end{align*}$$ のように表す。ただし、これは最初に与えられたlinear programming problemをそのまま書き写したものであり、解が進むにつれて変化する係数にはバーをつけて、次のように表現する。 $$\begin{align*} \zeta &=& \bar{\zeta} &+& \sum_{j \in \mathcal{N}} \bar{c}_{j} x_{j} \\ x_{n+i} &=& \bar{b}_{i} &-& \sum_{j \in \mathcal{N}} \bar{a}_{ij} x_{j} \end{align*}$$ ここで、$i \in \mathcal{B}$であり、表記からもわかるように、$\mathcal{N}$と$\mathcal{B}$は固定された集まりではなく、解が進むにつれて変わる。

タブロー ²

feasible basis $B$によって決定されるシンプレックスタブロー$\mathcal{T}(B)$は、与えられたlinear programming problem $A \mathbf{x} = \mathbf{b}, z = \mathbf{c}^{T} \mathbf{x}$と同じ解の集合を持つ、$m+1$次の連立線形方程式を意味する。$N := \left\{ 1 , \cdots , n + m \right\} \setminus B$に対して、$\mathbf{x}_{B}$を基底変数のベクトル、$\mathbf{x}_{N}$を非基底変数のベクトルとするとき、何らかのベクトル$\mathbf{p} \in \mathbb{R}^{m}$、$\mathbf{r} \in \mathbb{R}^{n-m}$と行列$Q \in \mathbb{R}^{m \times (n-m)}$に対して、次のように表される。 $$\begin{align*} \mathbf{x}_{B} &=& \mathbf{p} &+& Q \mathbf{x}_{N} \\ z &=& z_{0} &+& \mathbf{r}^{T} \mathbf{x}_{N} \end{align*}$$

説明

正直言って、ディクショナリとタブローは同じものであり、引用からもわかるように、著者によって表現の好みの違いに過ぎない。当然ながら、概念的には$B = \mathcal{B}$と$N = \mathcal{N}$は同じであり、使っている変数をそのまま使ったのか、行列の表記を使ったのかの違いにすぎない。

投稿のために、多くのlinear programmingの教科書を調べてみたが、ディクショナリであれタブローであれ、これらについて詳しく説明したいと思っている著者はいなかった。‘連立方程式’からしてそうだが、高度な抽象化に慣れている数学者は、‘次のような形’や’アルゴリズムに従って変わる’といったあいまいな表現に対して極度の不安感、嫌悪感を抱く。そうした気持ちは理解できるが、著者たちもまた、ノーテーションに囚われるよりはlinear programmingそのものについての議論に早く進みたがっているように見えたし、真にlinear programmingに興味があるならば、読者も適当に納得して進むことをお勧めする。