线性规划的对偶理论及其应用

第二章线性规划的对偶理论及其应用2.3线性规划的对偶定理2.5对偶单纯型算法22.3线性规划的对偶定理1弱对偶定理定理对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值•为了便于讨论，下面不妨总是假设2最优解判别定理定理若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解=0XbAXCX..)(max:tsxf原问题=0YCYAtsYbyg..)(min:对偶问题33弱对偶定理推论如果原max(min)问题为无界解，则其对偶min(max)问题无可行解如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解注：存在原问题和对偶问题同时无可行解的情况4强对偶定理定理如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。45互补松弛定理定理1设X0,Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是Y0U0+V0X0=0定理2在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则给约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。56原问题检验数与对偶问题的解在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。例162.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(0min**-jijijjjaazc