線形計画法における目的関数の無限大
説明
$$ \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になることがある。
百聞は一見にしかず1。幾何学的にシンプレックス・メソッドを考えた時、目標関数がアンバウンドであるとは、そもそもシンプレックス自体を構成できないという意味になる。このように目標関数がバウンドされていない場合、最大化問題であっても目標値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} $$ が正でなければ目標関数がアンバウンドであると分かる。2