证明如果标准形式的线性规划存在非退化的最优基可行解,其对偶规划必有唯一最优解
时间: 2023-06-11 15:07:12 浏览: 72
要证明标准形式的线性规划存在非退化的最优基可行解时,我们需要先了解什么是非退化性和最优基。
非退化性是指在一个线性规划问题中,基变量的取值都是非零的,即基变量不为零的概率为1。
最优基是指在标准形式的线性规划问题中,基变量的取值确定了非基变量的取值,使得目标函数取得最小值或最大值。
因此,非退化的最优基可行解是指在标准形式的线性规划问题中,存在一个非退化的基向量集合使得该集合对应的基变量的取值确定了非基变量的取值,并且这个基向量集合对应的可行解是最优解。
接下来,我们需要证明标准形式的线性规划存在非退化的最优基可行解时,其对偶规划必有唯一最优解。
根据对偶理论,线性规划的原问题与对偶问题具有以下关系:
- 原问题的最大值等于对偶问题的最小值;
- 原问题的最优解对应着对偶问题的最优解;
- 对偶问题的最优解对应着原问题的最优解。
因此,我们只需要证明对偶问题存在唯一最优解即可。
假设对偶问题存在两个不同的最优解y1和y2,且它们都对应着原问题的最优解x。
因为y1和y2都是最优解,所以它们都满足对偶问题的约束条件,即y1和y2都是非负向量,并且$y_1A=y_2A=c$。
进一步地,因为x是原问题的最优解,所以它也满足原问题的约束条件,即$Ax=b$,并且目标函数最小化。
由于x是非退化的最优基可行解,所以它的基向量集合是非退化的。因此,基向量集合的个数等于矩阵A的列数,即基向量集合的个数等于对偶问题的约束条件个数。
因此,我们可以得出以下结论:
- 在非退化的最优基可行解中,基向量集合的个数等于对偶问题的约束条件个数;
- 对偶问题的最优解y1和y2都满足对偶问题的约束条件;
- 因此,y1和y2都是对偶问题的可行解。
接下来,我们将证明y1和y2相等。假设它们不相等,即存在某个分量y1i和y2i不相等。
不失一般性,我们假设y1i>y2i。注意到y1和y2都是非负向量,所以$y_1A>y_2A$。
我们将y1和y2的差向量记为d=y1-y2,因此d>0。接下来,我们将d乘以A,得到$dA=y_1A-y_2A>0$。
因为$y_1A=y_2A=c$,所以$cA=0$。因此,我们可以得到$dA=cA=0$。
因为d>0,所以我们可以找到一个正数a使得ad<dA,即ad<y1A-y2A。因此,我们可以得到以下不等式:
$$(y_2+a\cdot d)A=y_2A+a\cdot dA<y_1A$$
但是这与y1是对偶问题的最优解相矛盾,因为y2+a·d是对偶问题的可行解,且它的目标函数值小于y1。
因此,我们可以得出结论:对偶问题的最优解唯一。
综上所述,如果标准形式的线性规划存在非退化的最优基可行解,其对偶规划必有唯一最优解。