运筹学－北京邮电大学2-1PPT模板|运筹学－北京邮电大学2-1PPT模版(幻灯片模板|Powerpoint模板)

运筹学－北京邮电大学2-1

第二章线性规划的对偶理论及其应用
窗含西岭千秋雪，门泊东吴万里船

对偶是一种普遍现象
2.1 线性规划的对偶理论 2.1.1 线性规划原问题与对偶问题的表达形式
任何线性规划问题都有其对偶问题
对偶问题有其明显的经济含义
例2.1.1
设A、B资源的出售价格分别为 y1 和 y2
显然商人希望总的收购价越小越好
工厂希望出售资源后所得不应比生产产品所得少
2.1.1 线性规划原问题与对偶问题的表达形式
2.1.1 线性规划原问题与对偶问题的表达形式
2.1.2 标准(max,%26#61603;)型的对偶变换
目标函数由 max 型变为 min 型
对应原问题每个约束行有一个对偶变量 yi，i=1,2,…,m
对偶问题约束为 %26#61619; 型，有 n 行
原问题的价值系数 C 变换为对偶问题的右端项
原问题的右端项 b 变换为对偶问题的价值系数
原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵
原问题与对偶问题互为对偶
对偶问题可能比原问题容易求解
对偶问题还有很多理论和实际应用的意义

2.1.3 非标准型的对偶变换
表2.1.1 对偶变换的规则
约束条件的类型与非负条件对偶
非标准的约束条件类型对应非正常的非负条件
对偶变换是一一对应的
2.2 线性规划的对偶定理
2.2.1 弱对偶定理
定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值
弱对偶定理推论
max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限
如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解
如果原max(min)问题有可行解，其对偶 min (max)问题无可行解，则原问题为无界解
注：存在原问题和对偶问题同时无可行解的情况
2.2.2 最优解判别定理
定理 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解
证：由弱对偶定理推论1，结论是显然的。
即CX0 = Y0b %26#61619; CX, Y0b = CX0 %26#61603; Yb 。 证毕。
主对偶定理的证明
证：现证明定理的后一句话。
设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B%26#61485;1 b，则其检验数满足 C %26#61485; CBB%26#61485;1A %26#61603; 0
令 Y0= CBB%26#61485;1，则有 Y0 A %26#61619; C。
显然Y0为对偶问题的可行解。因此有对偶问题目标函数值， g(Y0)=Y0b= CBB%26#61485;1 b
而原问题最优解的目标函数值为
f(X0)=CX0= CBB%26#61485;1 b
故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。
该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本
即对偶变量的最优解是原问题资源的影子价格
2.2.4 互补松弛定理
定理 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0
证：由定理所设，可知有
A X0 + U0 = b X0, U0 %26#61619;0 (1)
Y0 A %26#61485; V0 = C Y0, V0 %26#61619;0 (2)
分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得
Y0 U0 + V0 X0 = Y0 b %26#61485; C X0
若 Y0 U0 + V0 X0 = 0，根据最优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。 证毕。
2.2.5 原问题检验数与对偶问题的解
在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值
容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值
由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。
更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。
例2.2.3 原问题检验数与对偶问题的解

2.3 对偶单纯型算法 2.3.1 基本思路
原单纯型迭代要求每步都是基础可行解
达到最优解时，检验数 cj–zj %26#61603;0 (max) 或 cj–zj %26#61619;0 (min)
但对于(min, %26#61619;)型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决
大M法和二阶段法较繁
能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件， cj–zj %26#61603;0 (max) 或 cj–zj %26#61619;0 (min)
每步迭代保持检验数满足最优条件，但减少非可行度
如何判断达到最优解
如何保证初始基础解满足最优条件
为什么叫对偶单纯型法
2.3.2 迭代步骤
确定出变量
找非可行解中最小者，即 min{ bi | bi%26lt;0}，设第 i*行的最负，则i*行称为主行，该行对应的基变量为出变量，xi*'
确定入变量
最大比例原则
例2.3.1 对偶单纯型解法
表2.3.1 对偶单纯型法的单纯型表(min)
习 题 课
学而时习之，不亦乐乎
— 《论语》
第 1 题
解：设车间 1 生产x1A单位A、生产x1B单位B；
设车间 2 生产x2A单位A、生产x2B单位B；
设车间 3 生产x3A单位A、生产x3B单位B；
则有生产安排最优化的模型如下：
第 2 题
解：
设 x1A 为饮料甲中A的总含量 (升)
设 x2A 为饮料乙中A的总含量 (升)
设 x3A 为饮料丙中A的总含量 (升)
设 x1B 为饮料甲中B的总含量 (升)
设 x2B 为饮料乙中B的总含量 (升)
设 x3B 为饮料丙中B的总含量 (升)
设 x1C 为饮料甲中C的总含量 (升)
设 x2C 为饮料乙中C的总含量 (升)
设 x3C 为饮料丙中C的总含量 (升)
则有模型如下：

第 3、4 题