全双対整数性

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

線形不等式システム ${\boldsymbol {A}}{\boldsymbol {x}}\leq {\boldsymbol {b}}\,$ が線形計画問題 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \max \{\boldsymbol{c} \boldsymbol{x} \mid \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \} \,} が有界であるような任意の整数ベクトル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{c} \,} に対して, その双対問題 $\min\{{\boldsymbol {b}}{\boldsymbol {y}}\mid {\boldsymbol {y}}{\boldsymbol {A}}={\boldsymbol {c}},{\boldsymbol {y}}\geq {\boldsymbol {0}}\}\,$が, 整数の最適解 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{y}^* \,} をもつならば, 全双対整数的 (totally dual integral, TDI) であるという.