「全双対整数性」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【ぜんそうついせいすうせい (totally dual integrality (TDI))】''' 線形不等式システム $\mbox{\boldmath $A x$} \leq \mbox{\boldmath $b$}$ が線形計...') |
|||
| 1行目: | 1行目: | ||
'''【ぜんそうついせいすうせい (totally dual integrality (TDI))】''' | '''【ぜんそうついせいすうせい (totally dual integrality (TDI))】''' | ||
| − | 線形不等式システム | + | 線形不等式システム <math>\mathbf{A} \mathbf{x} \leq \mathbf{b} \,</math> が線形計画問題 <math> \max \{\mathbf{c} \mathbf{x} \mid \mathbf{A} \mathbf{x} \leq \mathbf{b} \} \,</math> が有界であるような任意の整数ベクトル <math>\mathbf{c} \,</math> に対して, その双対問題 <math> \min\{ \mathbf{b} \mathbf{y} \mid \mathbf{y} \mathbf{A} = \mathbf{c}, \mathbf{y} \geq \mathbf{0} \} \,</math>が, 整数の最適解 <math>\mathbf{y}^* \,</math> をもつならば, 全双対整数的 (totally dual integral, TDI) であるという. |
2007年7月14日 (土) 01:49時点における版
【ぜんそうついせいすうせい (totally dual integrality (TDI))】
線形不等式システム が線形計画問題 が有界であるような任意の整数ベクトル に対して, その双対問題 が, 整数の最適解 をもつならば, 全双対整数的 (totally dual integral, TDI) であるという.
