全對偶整數性(total dual integrality)組合最佳化問題的一種性質。指線性規劃max Z=c，滿足Ax=b具有如下性質：矩陣A及向量b均取整數值，而且對於任意的整數向量。此問題的對偶問題均具有整值最優解。
基本介紹
- 中文名：全對偶整數性
- 外文名：total dual integrality
- 分類：性質
- 屬性：數學術語
- 相關：最優解
簡介,對偶,相關研究,
簡介
由此性質可知，約束條件Ax=b決定的多面形的所有頂點均為整點。因此，對組合最佳化問題而言，全對偶整數性是一個重要的性質，同時它的要求是相當強的。例如，間題是在二部圖上建立匹配，此二部圖上每條邊都帶整數權，目標是求匹配上對應的權和達到極大。這個問題具有全對偶整數性。
對偶
對偶問題：每一個線性規劃問題都存在一個與其對偶的問題，原問題與對偶問題對一個實際問題從不同角度提出來，並進行描述，組成一對互為對偶的線性規劃問題。
對偶空間：設V為數域P上一個n 維線性空間。V上全體線性函式組成的集合記作L(V，P)。定義在L(V，P)上的加法和數量乘法：(f+g)(a)=f(a)+g(a)，(kf)(a)=kf(a)，則L(V，P)也是數域P上的線性空間。這樣構造的L(V，P)就稱為V的對偶空間。
對偶理論是研究線性規劃中原始問題與對偶問題之間關係的理論。 線上性規劃早期發展中最重要的發現是對偶問題，即每一個線性規劃問題（稱為原問題）有一個與它對應的對偶線性規劃問題（稱為對偶問題）。 1928年美籍匈牙利數學家 J.von諾伊曼在研究對策論時，發現線性規劃與對策論之間存在著密切的聯繫。
設線性規劃問題中P問題：min f = c'x ，Ax≥b ，且c'≥0；D問題：max g = y'b， y'A≤c'， 且y'≥0。問題 P和問題D互為對偶問題。其特點如下：目標函式的目標互為相反(max，min)；目標函式的係數是另一個約束條件右端的向量；約束係數矩陣是另一個的約束係數矩陣的轉置；約束方程的個數與另一個的變數的個數相等。
相關研究
針對混合整數非線性規劃問題，提出了凸鬆弛方法與分解方法。在這個方法裡利用凸鬆弛技術將原問題凸鬆弛化，並用塊分離思想把原問題的對偶問題分解成若干個小問題，用對偶切平面法求解，可使問題簡單化，並進行了收斂性分析和證明。
一個用於有界整數規劃的指數對偶公式。此公式具有漸進強對偶的特性並且可以保證找到原問題的最優解。它的另一個特性是當參數選擇的合適時不需要進行實際的對偶搜尋 。
