「TDI性」の版間の差分
ナビゲーションに移動
検索に移動
Sakasegawa (トーク | 投稿記録) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
線形不等式システム <math>\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \,</math> が線形計画問題 <math> \max \{\boldsymbol{c} \boldsymbol{x} \mid \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \} \,</math> が有界であるような任意の整数ベクトル <math>\boldsymbol{c} \,</math> に対して, その双対問題 <math> \min\{ \boldsymbol{b} \boldsymbol{y} \mid \boldsymbol{y} \boldsymbol{A} = \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0} \} \,</math>が, 整数の最適解 <math>\boldsymbol{y}^* \,</math> をもつならば, 全双対整数的である (totally dual integral, TDI性を持つ) という. | 線形不等式システム <math>\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \,</math> が線形計画問題 <math> \max \{\boldsymbol{c} \boldsymbol{x} \mid \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \} \,</math> が有界であるような任意の整数ベクトル <math>\boldsymbol{c} \,</math> に対して, その双対問題 <math> \min\{ \boldsymbol{b} \boldsymbol{y} \mid \boldsymbol{y} \boldsymbol{A} = \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0} \} \,</math>が, 整数の最適解 <math>\boldsymbol{y}^* \,</math> をもつならば, 全双対整数的である (totally dual integral, TDI性を持つ) という. | ||
| + | |||
| + | [[Category:組合せ最適化|てぃーでぃーあいせい]] | ||
2008年11月5日 (水) 16:59時点における最新版
【てぃーでぃーあいせい (TDI (totally dual integrality))】
線形不等式システム が線形計画問題 が有界であるような任意の整数ベクトル に対して, その双対問題 が, 整数の最適解 をもつならば, 全双対整数的である (totally dual integral, TDI性を持つ) という.
