《线性规划的对偶理论及其应用ppt课件.ppt》由会员分享，可在线阅读，更多相关《线性规划的对偶理论及其应用ppt课件.ppt（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第二章第二章线性规划的对偶理论及其应用线性规划的对偶理论及其应用2.3 线性规划的对偶定理线性规划的对偶定理2.5 对偶单纯型算法对偶单纯型算法22.3 线性规划的对偶定理线性规划的对偶定理 1 弱弱对偶定理对偶定理定理定理 对偶问题对偶问题(min)的任何可行解的任何可行解Y0，其目标函数值总是不，其目标函数值总是不小于原问题小于原问题(max)任何可行解任何可行解X0的目标函数值的目标函数值 为了便于讨论，下面不妨总是假设为了便于讨论，下面不妨总是假设 2 最优解判别最优解判别定理定理定理定理 若原问题的某个可行解若原问题的某个可行解X0的目标函数值与的目标函数值与对偶问题某个可行解对偶
2、问题某个可行解Y0的目标函数值相等，的目标函数值相等，则则X0, Y0分别是相应问题的最优解分别是相应问题的最优解=0XbAXCX. .)(max :tsxf原问题=0YCYA tsYbyg.)(min :对偶问题对偶问题3 3 弱对偶定理推论n如果原如果原max(min)问题为无界解，则其对偶问题为无界解，则其对偶 min (max)问题无可行解问题无可行解n如果原如果原max(min)问题有可行解，其对偶问题有可行解，其对偶 min (max)问题无可行解，则原问题为无界解问题无可行解，则原问题为无界解n注注：存在原问题和对偶问题同时无可行解的情况：存在原问题和对偶问题同时无可行解的情况
3、4 强对偶强对偶定理定理定理定理 如果原问题和对偶问题都有可行解，则它们都如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。有最优解，且它们的最优解的目标函数值相等。4 5互补松弛互补松弛定理定理定理定理1 1 设设X0, , Y0分别是原问题和对偶问题的可行分别是原问题和对偶问题的可行解，解，U0为原问题的松弛变量的值、为原问题的松弛变量的值、V0为对为对偶问题剩余变量的值。偶问题剩余变量的值。X0, , Y0分别是原问题分别是原问题和对偶问题最优解的充分必要条件是和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0定理定理2 2 在线性规划问
4、题的最优解中，如果对应某在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则给约束一约束条件的对偶变量值为非零，则给约束条件取严格等式；反之如果约束条件取严格条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零不等式，则其对应的对偶变量一定为零。5 6 原问题检验数与对偶问题的解原问题检验数与对偶问题的解n在最优解的单纯型表中，都有原问题在最优解的单纯型表中，都有原问题虚变量虚变量(松松弛或剩余弛或剩余) 的检验数对应其对偶问题的检验数对应其对偶问题实变量实变量 (对对偶变量偶变量)的最优解，原问题的最优解，原问题实变量实变量(决策变量决策变量) 的的检验数
5、对应其对偶问题检验数对应其对偶问题虚变量虚变量 (松弛或剩余变量松弛或剩余变量)的最优解。的最优解。n因此，原问题或对偶问题只需求解其中之一就因此，原问题或对偶问题只需求解其中之一就可以了。可以了。例16 2.5 对偶单纯型算法对偶单纯型算法1 迭代步骤迭代步骤1确定出变量确定出变量找非可行解中最小者，即找非可行解中最小者，即 min bi | bi0，设第，设第 i*行的为行的为负，则负，则i*行称行称为主行为主行，该行对应的基变量为，该行对应的基变量为出变量出变量，xi*2确定入变量确定入变量 最大比例原则最大比例原则 设设 j* 列满足列满足(2.3.1)式，式， j* 列称为列称为主列主列，xj* 为为出变量出变量3 以主元以主元 ai*j* 为中心迭代为中心迭代4 检查当前基础解是否为可行解检查当前基础解是否为可行解 若是，则当前解即为最优解若是，则当前解即为最优解 否则，返回否则，返回 步骤步骤 1例例2)1 . 3 . 2(0 min*-jijijjjaazc