全对偶整数性

全对偶整数性(total dual integrality)组合优化问题的一种性质。指线性规划max Z=c，满足Ax=b具有如下性质：矩阵A及向量b均取整数值，而且对于任意的整数向量。此问题的对偶问题均具有整值最优解。

简介由此性质可知，约束条件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)；目标函数的系数是另一个约束条件右端的向量；约束系数矩阵是另一个的约束系数矩阵的转置；约束方程的个数与另一个的变量的个数相等。

相关研究针对混合整数非线性规划问题，提出了凸松弛方法与分解方法。在这个方法里利用凸松弛技术将原问题凸松弛化，并用块分离思想把原问题的对偶问题分解成若干个小问题，用对偶切平面法求解，可使问题简单化，并进行了收敛性分析和证明1。

整数规划中经典的Lagrange对偶方法是一个有效的方法，但是由于对偶缝隙的原因它经常不能求出原问题的最优解。

一个用于有界整数规划的指数对偶公式。此公式具有渐进强对偶的特性并且可以保证找到原问题的最优解。它的另一个特性是当参数选择的合适时不需要进行实际的对偶搜索 2。

本词条内容贡献者为:

武伟 - 高级工程师 - 天津直升机有限责任公司