「全双対整数性」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
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) であるという.
+
線形不等式システム  <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) であるという.

2007年7月17日 (火) 14:52時点における版

【ぜんそうついせいすうせい (totally dual integrality (TDI))】

線形不等式システム が線形計画問題 が有界であるような任意の整数ベクトル に対して, その双対問題 が, 整数の最適解 をもつならば, 全双対整数的 (totally dual integral, TDI) であるという.

「https://orsj-ml.org/orwiki/wiki/index.php?title=全双対整数性&oldid=5323」から取得