AOR4 原始对偶方法

原始对偶算法

原始对偶算法利用了及其巧妙的方法减少参数，优化解，最后找到最优解。

互补松弛定理：最优解的等价命题为: 对于所有的j， 有$(A_j^{T}y-c_j)x_j=0$
我们知道每一行约束的权值为yi，对于一个x，确定了y的一个线性组合的约束。如果该x不是0, 则要求y的约束取等号。否则该约束取小于等于号。

假如已知一个集合J, 里面是xj满足xj不是0，由于在J之外的x全部是0, 因此在原问题中只剩下那些xj的项，转化为对偶问题后，只有J中的元素xj才能产生对y的约束。

这样原来的约束从m个减少到了|J|个，我们只要寻找限制集J即可。

上面是原始对偶算法的思路，下面是更加详细的操作：

假如对原问题每个约束增加一个人工变量x’i, i=1,2,…,m 目标函数变为x’i的求和(和两阶段法类似)，此时的对偶问题变为DRP问题，和原来的D问题相比

• 增加了一个约束y<1,
• 约束的右边常数变为0,
• 目标函数没有发生变化。

如果DRP问题最大值为0, 说明找到原问题最优解。

由此可以看出，原始对偶算法的精髓是限制集J。和单纯形法相比，单纯形法通过用不同的变量表示目标函数进行迭代，而原始对偶算法通过修改限制集进行迭代。

原始对偶算法过程：

1.确定限制集J

2.计算DRP问题最优解

3.最优解为0，则限制集为最优，根据限制集解出最优解

4.最优解>0, 则将一个新的x加入限制集。限制集，挑选进入限制集的x的方法是：对于一个x，如果其对应的y约束值和cj最接近，则选择它。

5.返回2

最短路径问题

设xi为第i条边是否在最短路径中，则目标函数为:

$\min z=\sum c_i{x}_i$, c是第i条边权值

对于最短路径中每一个点，如果该点是起点，则出度-入度为1，是终点则出度-入度为-1，其他点入度=出度

对于每个点建立约束，如果该边是出边，则系数为1，否则系数为-1，其和为0

写出其D问题
$\max z=y_t$
$y_i-y_j\le c_e,(i,j)\in J$

写出其DRP问题：
$\max z=y_t$
$y_i-y_j\le 0,(i,j)\in J$
$y\le 1$

下面是迭代过程：