logo

線形計画法における目的関数の無限大 📂最適化理論

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

説明

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

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

20211218_030218.png

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

判別法

ζ=ζˉ+jNcˉjxjxn+i=bˉijNaˉijxj \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を置いたディクショナリーまたはタブローを上記のように示した時、退場変数がxix_{i}であるとしたら、すべての aˉi1bˉi,,aˉinbˉi \bar{a}_{i1} \bar{b}_{i}, \cdots , \bar{a}_{in} \bar{b}_{i} が正でなければ目標関数がアンバウンドであると分かる。2


  1. Matousek. (2007). Understanding and Using Linear Programming: p61. ↩︎

  2. Vanderbei. (2020). 线形プログラミング(第5版): p19~20. ↩︎