第三章 对偶理论 第一讲 线性规划的对偶模型,对偶性质.ppt

3.1对偶线性规划问题对偶线性规划问题对偶问题的提出对偶问题的提出原问题原问题对偶问题对偶问题原问题原问题对偶问题对偶问题原问题与对偶问题原问题与对偶问题关系关系(1)原问题的约束个数原问题的约束个数(不含非负约束不含非负约束)等于对等于对偶变量的个数偶变量的个数(2)原问题的目标函数系数对应于对偶问题的原问题的目标函数系数对应于对偶问题的右端项右端项(3)原问题的右端项对应于对偶问题的目标函原问题的右端项对应于对偶问题的目标函数系数数系数(4)原问题的约束矩阵转置就是对偶问题系原问题的约束矩阵转置就是对偶问题系数矩阵数矩阵(5)原问题求最小原问题求最小(最大最大)，对偶问题是求最大，对偶问题是求最大(最小最小)(6)原问题不等式约束符号为原问题不等式约束符号为“”(“”,),对偶问题不等式约束符号为对偶问题不等式约束符号为“”(“”)原问题原问题对偶问题对偶问题原问题与对偶问题原问题与对偶问题关系关系(1)原问题的约束个数原问题的约束个数(不含非负约束不含非负约束)等于对等于对偶变量的个数偶变量的个数(2)原问题的目标函数系数对应于对偶问题的原问题的目标函数系数对应于对偶问题的右端项右端项(3)原问题的右端项对应于对偶问题的目标函原问题的右端项对应于对偶问题的目标函数系数数系数(4)原问题的约束矩阵转置就是对偶问题系原问题的约束矩阵转置就是对偶问题系数矩阵数矩阵【例例】写出下列线性规划的对偶问题写出下列线性规划的对偶问题【解解】设设Y=(y1，y2)(5)原问题求最小原问题求最小(最大最大)，对偶问题是求最大，对偶问题是求最大(最小最小)(6)原问题不等式约束符号为原问题不等式约束符号为“”(“”,),对偶问题不等式约束符号为对偶问题不等式约束符号为“”(“”)【例例3.3】写出下列线性规划的对偶问题写出下列线性规划的对偶问题线性规划问题的线性规划问题的规范形式规范形式(CanonicalForm或叫或叫对称形式对称形式)：定义：定义：目标函数求目标函数求极大值极大值时，所有约束条件时，所有约束条件为为号号，变量非负变量非负；目标函数求目标函数求极小值极小值时，所有约束条件时，所有约束条件为为号，变量非负号，变量非负。注：注：(1)(1)线性规划规范形式与标准型是两种不同形式，但可以线性规划规范形式与标准型是两种不同形式，但可以相互转换。相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式规范形式的线性规划问题的对偶仍然是规范形式原问题原问题(或对偶问题或对偶问题)对偶问题对偶问题(或原问题或原问题)目标函数目标函数max目标函数系数目标函数系数(资源限量资源限量)约束条件系数矩阵约束条件系数矩阵A(AT)目标函数目标函数min资源限量资源限量(目标函数系数目标函数系数)约束条件系数矩阵约束条件系数矩阵AT(A)变变量量n个变量个变量第第j个变量个变量0第第j个变量个变量0第第j个变量无约束个变量无约束约约束束n个约束个约束第第j个约束为个约束为第第j个约束为个约束为第第j个约束为个约束为=约约束束m个约束个约束第第i个约束个约束第第i个约束个约束第第i个约束为个约束为=变变量量m个变量个变量第第i个变量个变量0第第i个变量个变量0第第i个变量无约束个变量无约束问题问题：讨论一般形式的线性规划问题的对偶问题？：讨论一般形式的线性规划问题的对偶问题？方法：方法：先将其转化为规范形式的线性规划问题，然后写出其对偶问题，适当先将其转化为规范形式的线性规划问题，然后写出其对偶问题，适当将其进行化简。将其进行化简。3.2对偶性质对偶性质Dualproperty对偶问题是对偶问题是(记为记为DP)：这里这里A是是mn矩阵矩阵,X是是n1列向量列向量,Y是是1m行向量。行向量。【性质性质1】对称性对称性:对偶问题的对偶是原问题。对偶问题的对偶是原问题。设原问题是设原问题是(记为记为LP)：3.2.1对偶性质对偶性质【性质性质2】弱对偶性弱对偶性:设设X*、Y*分别为分别为LP(min)与与DP(max)的可行解，则的可行解，则 【性质性质2】弱对偶性弱对偶性:设设X*、Y*分别为分别为LP(mix)与与DP(max)的可行解，则的可行解，则 由这个性质可得到下面几个由这个性质可得到下面几个结论结论：1)(DP)的任一可行解的目标值是的任一可行解的目标值是(LP)的最优值下界；的最优值下界；(LP)的任一可行解的的任一可行解的目标是目标是(DP)的最优值的上界；的最优值的上界；2)在在互互为为对对偶偶的的两两个个问问题题中中，若若一一个个问问题题可可行行且且具具有有无无界界解解，则则另另一一个个问问题无可行解；题无可行解；3)若原问题可行且另一个问题不可行，则原问题具若原问题可行且另一个问题不可行，则原问题具有无界解。有无界解。注注意意:上上述述结结论论(2)及及(3)的的条条件件不不能能少少。一一个个问问题题无无可可行行解解时时，另另一一个个问问题题可可能能有有可可行解行解(此时具有无界解此时具有无界解)也可能无可行解。也可能无可行解。例如：例如：无可行解无可行解而对偶问题而对偶问题有可行解有可行解有无界解有无界解【性性质质3】最最优优准准则则定定理理:设设X*与与Y*分分别别是是(LP)与与(DP)的可行解，则的可行解，则X*、Y*是是(LP)与与(DP)的最优解当且仅当的最优解当且仅当C X*=Y*b.【性性质质4】对对偶偶性性：若若互互为为对对偶偶的的两两个个问问题题其其中中一一个个有有最优解，则另一个也有最优解，且最优值相同。最优解，则另一个也有最优解，且最优值相同。另另一一结结论论：若若(LP)与与(DP)都都有有可可行行解解，则则两两者者都都有有最最优优解，若一个问题无最优解，则另一问题也无最优解。解，若一个问题无最优解，则另一问题也无最优解。【性性质质5】互互补补松松弛弛定定理理:设设X*、Y*分分别别为为(LP)与与(DP)的的可可行行解解，XS和和YS分分别别是是它它们们的的松松弛弛变变量量的的可可行行解解，则则X*和和Y*是最优解当且仅当是最优解当且仅当YSX*=0和和Y*XS=0【性性质质5】互互补补松松弛弛定定理理:设设X*、Y*分分别别为为(LP)与与(DP)的的可可行行解解，XS和和YS分分别别是是它它们们的的松松弛弛变变量量的的可可行行解解，则则X*和和Y*是最优解当且仅当是最优解当且仅当YSX*=0和和Y*XS=0可写成下式可写成下式即即已知一个问题的最优解时求另一个问题的最优解的方法已知一个问题的最优解时求另一个问题的最优解的方法可写成下式可写成下式即即已知一个问题的最优解时求另一个问题的最优解的方法已知一个问题的最优解时求另一个问题的最优解的方法【例例3.5】已知线性规划已知线性规划的最优解是的最优解是,求对偶问题的最优解。求对偶问题的最优解。【解解】对偶问题是对偶问题是因因为为x10，x20，所所以以对对偶偶问问题题的的第第一一、二二个个约约束束的松弛变量等于零，即的松弛变量等于零，即解解此此线线性性方方程程组组得得y1=1,y2=1,从从而而对对偶偶问问题题的的最最优优解解为为Y=(1，1)，最优值，最优值w=26。【例例3.6】已知线性规划已知线性规划的对偶问题的最优解为的对偶问题的最优解为Y=(0，2)，求原问题的最优解。，求原问题的最优解。【解解】对偶问题是对偶问题是解方程组得：解方程组得：x1=5,x3=1,所以原问题的最优解为所以原问题的最优解为X=(5，0，1)T，最优值，最优值Z=12。因为因为y20，所以原问题第二个松弛变量，所以原问题第二个松弛变量=0，由，由y1=0、y2=2知，松弛变量知，松弛变量故故x2=0，则原问题的约束条件为线性方程组：则原问题的约束条件为线性方程组：【例例3.7】证明该线性规划无最优解：证明该线性规划无最优解：【证证】容易看出容易看出X=(4，0，0)是一可行解。是一可行解。将三个约束的两端分别相加得将三个约束的两端分别相加得,而第二个约束有而第二个约束有y21,矛盾，故对偶问题无可行解，因而原问题具有矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。无界解，即无最优解。对偶问题对偶问题【性性质质6】LP(min)的的检检验验数数对对应应于于DP(max)的的一一组组基基解解。其其中中第第j个个决决策策变变量量xj的的检检验验数数对对应应于于(DP)中中第第j个个松松弛弛变变量量的的解解，第第i个个松松弛弛变变量量的的检检验验数数对对应应于于第第i个个对对偶偶变变量量yi的的解解。反反之之，(DP)的的检检验验数数(注意：乘负号注意：乘负号)对应于对应于(LP)的一组基本解。的一组基本解。注：注：应用性质应用性质6 6 的前提是线性规划为规范形式，而的前提是线性规划为规范形式，而性质性质1-51-5则对所有形式线性规划有效。则对所有形式线性规划有效。根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：表表36一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解(有可行解有可行解)无可行解无可行解性质性质2解解无可行解无可行解无界解无界解(有可行解有可行解)应用应用已知最优解已知最优解通过解方程通过解方程求最优解求最优解性质性质5已知检验数已知检验数检验数乘以检验数乘以求得基本解求得基本解性质性质6【性性质质6】LP(min)的的检检验验数数对对应应于于DP(max)的的一一组组基基解解。其其中中第第j个个决决策策变变量量xj的的检检验验数数对对应应于于(DP)中中第第j个个松松弛弛变变量量的的解解，第第i个个松松弛弛变变量量的的检检验验数数对对应应于于第第i个个对对偶偶变变量量yi的的解解。反反之之，(DP)的的检检验验数数(注意：乘负号注意：乘负号)对应于对应于(LP)的一组基本解。的一组基本解。对偶单纯形法对偶单纯形法看看性质看看性质6 6的应用的应用对偶单纯形法对偶单纯形法对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。原问题的解的方法。找一个基，建立初始对偶单纯形表，检验数全部非负；找一个基，建立初始对偶单纯形表，检验数全部非负；若若b b列元素非负，则已经是最优基。否则下一步。列元素非负，则已经是最优基。否则下一步。确定换出变量确定换出变量 确定换入变量确定换入变量主元变换主元变换例例3用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：解：先将问题改写为：解：先将问题改写为：约束条件两端乘约束条件两端乘“1”，得，得例例4 4 考虑线性规划问题考虑线性规划问题