1 弱对偶定理 定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不 小于原问题(max)任何可行解X0的目标函数值 2 最优解判别定理
定理 若原问题的某个可行解X0的目标函数值与 对偶问题某个可行解Y0的目标函数值相等， 则X0, Y0分别是相应问题的最优解
2
3 弱对偶定理推论

第二章 线性规划的对偶理论及其应用
2.3 线性规划的对偶定理 2.5 对偶单纯型算法
2.3 线性规划的对偶定理
• 为了便于讨论，下面不妨总是假设
原问题 :
max f ( x) = CX AX b s.t. X0
对偶问题 :Байду номын сангаас
min g ( y) = Yb YA C s.t. Y 0
4
6 原问题检验数与对偶问题的解


在最优解的单纯型表中，都有原问题虚变量(松 弛或剩余) 的检验数对应其对偶问题实变量 (对 偶变量)的最优解，原问题实变量(决策变量) 的 检验数对应其对偶问题虚变量 (松弛或剩余变量) 的最优解。 因此，原问题或对偶问题只需求解其中之一就 可以了。
例1
5
2.5 对偶单纯型算法 1 迭代步骤 1 确定出变量 找非可行解中最小者，即 min{ bi | bi<0}，设第 i*行的为 负，则i*行称为主行，该行对应的基变量为出变量，xi*'
2
确定入变量
最大比例原则
( 2 .3 .1)
cj - zj min a i* j < 0 j a i* j
– 设 j* 列满足(2.3.1)式， j* 列称为主列，xj* 为出变量 3 以主元 ai*j* 为中心迭代 4 检查当前基础解是否为可行解 – 若是，则当前解即为最优解 – 否则，返回 步骤 1 6 例2
3
5互补松弛定理
定理1 设X0, Y0分别是原问题和对偶问题的可行 解，U0为原问题的松弛变量的值、V0为对 偶问题剩余变量的值。X0, Y0分别是原问题 和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0 定理2 在线性规划问题的最优解中，如果对应某 一约束条件的对偶变量值为非零，则给约束 条件取严格等式；反之如果约束条件取严格 不等式，则其对应的对偶变量一定为零。
如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解 如果原max(min)问题有可行解，其对偶 min (max) 问题无可行解，则原问题为无界解 注：存在原问题和对偶问题同时无可行解的情况
4 强对偶定理
定理 如果原问题和对偶问题都有可行解，则它们都 有最优解，且它们的最优解的目标函数值相等。