第二章线性规划的对偶理论及其应用23线性规划的对偶定理25对偶.pptVIP

第二章线性规划的对偶理论及其应用 2.3 线性规划的对偶定理 2.5 对偶单纯型算法 2.3 线性规划的对偶定理 1 弱对偶定理 定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值 3 弱对偶定理推论 如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解 如果原max(min)问题有可行解，其对偶 min (max)问题无可行解，则原问题为无界解 注：存在原问题和对偶问题同时无可行解的情况 5互补松弛定理 定理1 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0 定理2 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则给约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 6 原问题检验数与对偶问题的解 在最优解的单纯型表中，都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。 因此，原问题或对偶问题只需求解其中之一就可以了。 2.5 对偶单纯型算法1 迭代步骤 确定出变量 找非可行解中最小者，即 min{ bi | bi0}，设第 i*行的为负，则i*行称为主行，该行对应的基变量为出变量，xi* 确定入变量 最大比例原则 * * 为了便于讨论，下面不妨总是假设 2 最优解判别定理 定理 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解 ? í ì 3 ￡ = 0 X b AX CX . . ) ( max : t s x f 原问题 ? í ì 3 3 = 0 Y C YA t s Yb y g . . ) ( min : 对偶问题 4 强对偶定理 定理 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。 例1 设 j* 列满足(2.3.1)式， j* 列称为主列，xj* 为出变量 以主元 ai*j* 为中心迭代 检查当前基础解是否为可行解 若是，则当前解即为最优解 否则，返回 步骤 1 例2 ) 1 . 3 . 2 ( 0 min * * ú ú ? ù ê ê ? é - j i j i j j j a a z c