84、浅谈原始对偶算法

  • Post author:
  • Post category:其他


原始对偶算法理解过很多次,每一个的理解都不一样,这次将其记录一下

这里定义原始问题为资源有限下的价值最大化模型,A是资源消耗矩阵,b是资源量,c是产品价值向量

max cTx

s.t. Ax <= b

对偶的定义是啥呢,它先组合一下原始的约束,组合权重用y表示,那么组合出来的向量为ATy,我约束其在每个维度的值都大于c,强行赋一个定义可以是保证价值情况下的资源最小化,这样对偶问题就被构造出来了,不难可以知道bTy >= xTATy >= xTc,

min bTy

s.t. ATy >= c

2、

如果x0,y0分别是原始问题和对偶问题的最优解,那么有bTy0 = x0TATy0 = x0Tc。

证明:因为原始问题有最优解,由单纯形法可知,x0 = B-1b,故x0Tc = bT(B-1)Tc >= bTy0,而bTy0 >= x0TATy0 >= x0Tc ,故bTy0 =  x0Tc, 故bTy0 = x0TATy0 = x0Tc

这里证明不难,但结论是非常好的,给大家一个体感就是原始问题紧的地方(最优解时为等号的约束)在对偶问题里往往是松的(有可能为紧),但原始问题松的地方对偶问题一定是紧的

3、

互补松弛条件是原始对偶算法的基础,流程为:原始P–对偶D–限制原始RP-限制原始对偶DRP,其基本思想有一个可行解时,再去找对偶问题的可行解,然后按互补松弛的条件不断的迭代

附:

单纯形法从原问题(P)的一个可行解出发, 在满足互补松弛条件的前提下, 使得其对偶变量朝着对偶可行解的方向迭代.



版权声明:本文为chaoyuzhang原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。