📂最適化理論

線形計画法における目的関数の無限大

説明

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

行列 $A \in \mathbb{R}^{m \times n}$と$\mathbf{b} \in \mathbb{R}^{m \times 1}$と$\mathbf{c} \in \mathbb{R}^{n}$について、线形计划问题が上記のように方程式フォームで表されるとしよう。制約条件に従っても目標関数がアンバウンド^unboundedになることがある。

百聞は一見にしかず¹。幾何学的にシンプレックス・メソッドを考えた時、目標関数がアンバウンドであるとは、そもそもシンプレックス自体を構成できないという意味になる。このように目標関数がバウンドされていない場合、最大化問題であっても目標値^{objective value}がずっと大きくなることがある。

判別法

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

与えられた問題で、解答が進むにつれて変わる係数の上にバー^barを置いたディクショナリーまたはタブローを上記のように示した時、退場変数が$x_{i}$であるとしたら、すべての $$ \bar{a}_{i1} \bar{b}_{i}, \cdots , \bar{a}_{in} \bar{b}_{i} $$ が正でなければ目標関数がアンバウンドであると分かる。²