《运筹学02对偶理论1线性规划的对偶模型,对偶性质.ppt》由会员分享，可在线阅读，更多相关《运筹学02对偶理论1线性规划的对偶模型,对偶性质.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter3对偶理论对偶理论DualTheory3.1线性规划的对偶模型线性规划的对偶模型DualModelofLP3.2对偶性质对偶性质Dualproperty3.3对偶单纯形法对偶单纯形法DualSimplexMethod3.4灵敏度与参数分析灵敏度与参数分析SensitivityandParametricAnalysis运筹学运筹学OperationsResearch3.1线性规划的对偶模型线性规划的对偶模型DualModelofLPChapter3对偶理论对偶理论DualTheory例例3.1(原例原例1.1)某工厂生产甲、乙两种产品。这些产品某工厂生产甲、乙两种产品。这些产品分别
2、要在分别要在A、B、C三种不同的设备上加工。企业决策者三种不同的设备上加工。企业决策者应如何安排生产计划，使企业总的利润最大？应如何安排生产计划，使企业总的利润最大？3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLPChapter3对偶理论对偶理论DualTheory解：设解：设x1、x2分别为甲、乙两种产品的产量，分别为甲、乙两种产品的产量，Z为总利润，则数为总利润，则数学模型为：学模型为：3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP现现在在从从另另一一个个角角度度来来考考虑虑企企业业的的决决策策问问题题。假假如如企企业业不不考考虑虑自自己己生生产产
3、产产品品，而而将将现现有有的的资资源源标标价价出出售售，问问题题：决决策策者者应怎样给定资源一个合理的价格？应怎样给定资源一个合理的价格？Chapter3对偶理论对偶理论DualTheory设设y1，y2，y3分别表示三种资源的单位增值价格分别表示三种资源的单位增值价格(售价成本售价成本增值增值)，总增值最低可用，总增值最低可用min w=36y1+40y2+76y3表表示示。企企业业生生产产一一件件产产品品甲甲用用了了四四种种资资源源的的数数量量分分别别是是3，5和和9个个单单位位，利利润润是是32,企企业业出出售售这这些些数数量量的的资资源源所所得得的的利利润润不不能能少少于于32，即，即
4、同理，对产品同理，对产品乙有乙有3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLPChapter3对偶理论对偶理论DualTheory这这是是一一个个线线性性规规划划数数学学模模型型，称称这这一一线线性性规规划划模模型型是是前前面面生生产产计计划划模模型型的的对对偶偶线线性性规规划划模模型型,这这一一问问题题称称为为对对偶偶问问题题。生生产产计计划划的的线性规划问题称为原始线性规划问题或线性规划问题称为原始线性规划问题或原问题原问题。3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP价格不可能小于零，即有价格不可能小于零，即有yi0(i=1,4),从而企业的
5、资源价格从而企业的资源价格模型为模型为Chapter3对偶理论对偶理论DualTheory注：注：以上两问题是同一组数据参以上两问题是同一组数据参数，只是位置有所不同，所描述数，只是位置有所不同，所描述的问题实际上是从两个不同的角的问题实际上是从两个不同的角度去描述。原始线性规划问题考度去描述。原始线性规划问题考虑的是充分利用现有资源，以产虑的是充分利用现有资源，以产品数量和单位产品的利润来决定品数量和单位产品的利润来决定企业的总利润，没有考虑资源的企业的总利润，没有考虑资源的价格，实际上在构成产品的利润价格，实际上在构成产品的利润中，不同的资源对利润的贡献也中，不同的资源对利润的贡献也不同，
6、它是企业生产过程中一种不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为隐含的潜在价值，经济学中称为影子价格影子价格。3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLPChapter3对偶理论对偶理论DualTheoryChapter3对偶理论对偶理论DualTheory线性规划问题线性规划问题(3.2)就是原线性规划问题就是原线性规划问题(3.1)的对偶线性规划问题，的对偶线性规划问题，反之，反之，(3.2)的对偶问题就是的对偶问题就是(3.1)3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP原问题与对偶问题有如下原问题与对偶问题有如下关系关系(假
7、设原问题假设原问题(3.1)：(1)原问题的原问题的约束个数约束个数(不含非负约束不含非负约束)等于等于对偶变量的个数对偶变量的个数(2)原问题的原问题的目标函数系数目标函数系数对应于对偶问题的对应于对偶问题的右端项右端项(3)原问题的原问题的右端项右端项对应于对偶问题的对应于对偶问题的目标函数系数目标函数系数(4)原问题的原问题的约束矩阵转置约束矩阵转置就是对偶问题就是对偶问题系数矩阵系数矩阵(5)原问题求原问题求最大最大，对偶问题是求，对偶问题是求最小最小(6)原问题不等式约束符号为原问题不等式约束符号为“”,对偶问题不等式约束符号为对偶问题不等式约束符号为“”Chapter3对偶理论对偶
8、理论DualTheory【例例3.2】写出下列线性规划的对偶问题写出下列线性规划的对偶问题【解解】设设Y=(y1，y2)，则有则有3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP从而对偶问题为从而对偶问题为Chapter3对偶理论对偶理论DualTheory【例例3.3】写出下列线性规划的对偶问题写出下列线性规划的对偶问题【解解】该该线线性性规规划划的的对对偶偶问问题题是是求求最最小小值值，有有三三个个变变量量且非负且非负,有两个有两个“”约束约束,即即3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLPChapter3对偶理论对偶理论DualTheory线
9、性规划问题的线性规划问题的规范形式规范形式(CanonicalForm或叫或叫对称形式对称形式)：定义：定义：目标函数求目标函数求极大值极大值时，所有约束条件时，所有约束条件为为号号，变量非负变量非负；目标函数求目标函数求极小值极小值时，所有约束条件时，所有约束条件为为号，变量非负号，变量非负。3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP注：注：(1)(1)线性规划规范形式与标准型是两种不同形式，但可以线性规划规范形式与标准型是两种不同形式，但可以相互转换。相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式规范形式的线性规划问题的对偶仍然是规范形式Chapter
10、3对偶理论对偶理论DualTheory原问题原问题(或对偶问题或对偶问题)对偶问题对偶问题(或原问题或原问题)目标函数目标函数max目标函数系数目标函数系数(资源限量资源限量)约束条件系数矩阵约束条件系数矩阵A(AT)目标函数目标函数min资源限量资源限量(目标函数系数目标函数系数)约束条件系数矩阵约束条件系数矩阵AT(A)变变量量n个变量个变量第第j个变量个变量0第第j个变量个变量0第第j个变量无约束个变量无约束约约束束n个约束个约束第第j个约束为个约束为第第j个约束为个约束为第第j个约束为个约束为=约约束束m个约束个约束第第i个约束个约束第第i个约束个约束第第i个约束为个约束为=变变量量m
11、个变量个变量第第i个变量个变量0第第i个变量个变量0第第i个变量无约束个变量无约束3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP问题问题：讨论一般形式的线性规划问题的对偶问题？：讨论一般形式的线性规划问题的对偶问题？方法：方法：先将其转化为规范形式的线性规划问题，然后写出其对先将其转化为规范形式的线性规划问题，然后写出其对偶问题，适当将其进行化简。偶问题，适当将其进行化简。3.2对偶性质对偶性质(了解了解)DualpropertyChapter3对偶理论对偶理论DualTheory对偶问题是对偶问题是(记为记为DP)：这里这里A是是mn矩阵矩阵,X是是n1列向量列向量,Y
12、是是1m行向量。行向量。【性质性质1】对称性对称性:对偶问题的对偶是原问题。对偶问题的对偶是原问题。设原问题是设原问题是(记为记为LP)：3.2对偶性偶性质Dualproperty3.2.1对偶性质对偶性质【性质性质2】弱对偶性弱对偶性:设设X*、Y*分别为分别为LP(max)与与DP(min)的可行解，则的可行解，则 Chapter3对偶理论对偶理论DualTheory3.2对偶性偶性质Dualproperty由这个性质可得到下面几个由这个性质可得到下面几个结论结论：(1)(LP)的任一可行解的目标值是的任一可行解的目标值是(DP)的最优值下的最优值下界；界；(DP)的任一可行解的目标是的任
13、一可行解的目标是(LP)的最优值的上界；的最优值的上界；(2)在在互互为为对对偶偶的的两两个个问问题题中中，若若一一个个问问题题可可行行且且具有无界解，则另一个问题无可行解；具有无界解，则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具若原问题可行且另一个问题不可行，则原问题具有无界解。有无界解。注注意意:上上述述结结论论(2)及及(3)的的条条件件不不能能少少。一一个个问问题题无无可可行行解解时时，另另一一个个问问题题可可能能有有可可行行解解(此此时时具具有有无无界界解解)也可能无可行解。也可能无可行解。Chapter3对偶理论对偶理论DualTheory例如：例如：无可
14、行解，而对偶问题无可行解，而对偶问题有可行解，由结论有可行解，由结论(3)知必有无界解。知必有无界解。3.2对偶性偶性质DualpropertyChapter3对偶理论对偶理论DualTheory【性性质质3】最最优优准准则则定定理理:设设X*与与Y*分分别别是是(LP)与与(DP)的可行解，则的可行解，则X*、Y*是是(LP)与与(DP)的最优解当且仅当的最优解当且仅当C X*=Y*b.3.2对偶性偶性质Dualproperty【性性质质4】对对偶偶性性：若若互互为为对对偶偶的的两两个个问问题题其其中中一一个个有有最优解，则另一个也有最优解，且最优值相同。最优解，则另一个也有最优解，且最优值
15、相同。另另一一结结论论：若若(LP)与与(DP)都都有有可可行行解解，则则两两者者都都有有最最优优解，若一个问题无最优解，则另一问题也无最优解。解，若一个问题无最优解，则另一问题也无最优解。【性性质质5】互互补补松松弛弛定定理理:设设X*、Y*分分别别为为(LP)与与(DP)的的可可行行解解，XS和和YS分分别别是是它它们们的的松松弛弛变变量量的的可可行行解解，则则X*和和Y*是最优解当且仅当是最优解当且仅当YSX*=0和和Y*XS=0Chapter3对偶理论对偶理论DualTheory性性质质5告告诉诉我我们们已已知知一一个个问问题题的的最最优优解解时时求求另另一一个个问问题题的最优解的方法
16、，即已知的最优解的方法，即已知Y*求求X*或已知或已知X*求求Y*。Y*XS=0和和YS X*=0两式称为两式称为互补松弛条件互补松弛条件。将互补松弛条件写成下式。将互补松弛条件写成下式由由于于变变量量都都非非负负，要要使使求求和和式式等等于于零零，则则必必定定每每一一分分量为零，因而有下列关系：量为零，因而有下列关系：3.2对偶性偶性质DualpropertyChapter3对偶理论对偶理论DualTheory(1)当当yi*0时，时，,反之当反之当,时时yi*=0；利利用用上上述述关关系系，建建立立对对偶偶问问题题(或或原原问问题题)的的约约束束线线性性方方程组，方程组的解即为最优解。程组
17、，方程组的解即为最优解。【例例3.5】已知线性规划已知线性规划的最优解是的最优解是,求对偶问题的最优解。求对偶问题的最优解。3.2对偶性偶性质DualpropertyChapter3对偶理论对偶理论DualTheory【解解】对偶问题是对偶问题是因因为为x10，x20，所所以以对对偶偶问问题题的的第第一一、二二个个约约束束的松弛变量等于零，即的松弛变量等于零，即解解此此线线性性方方程程组组得得y1=1,y2=1,从从而而对对偶偶问问题题的的最最优优解解为为Y=(1，1)，最优值，最优值w=26。3.2对偶性偶性质DualpropertyChapter3对偶理论对偶理论DualTheory【例例
18、3.6】已知线性规划已知线性规划的对偶问题的最优解为的对偶问题的最优解为Y=(0，2)，求原问题的最优解。，求原问题的最优解。【解解】对偶问题是对偶问题是3.2对偶性偶性质DualpropertyChapter3对偶理论对偶理论DualTheory解方程组得：解方程组得：x1=5,x3=1,所以原问题的最优解为所以原问题的最优解为X=(5，0，1)T，最优值，最优值Z=12。因为因为y20，所以原问题第二个松弛变量，所以原问题第二个松弛变量=0，由，由y1=0、y2=-2知，松弛变量知，松弛变量故故x2=0，则原问题的约束条件为线性方程组：则原问题的约束条件为线性方程组：3.2对偶性偶性质Du
19、alpropertyChapter3对偶理论对偶理论DualTheory【例例3.7】证明该线性规划无最优解：证明该线性规划无最优解：【证证】容易看出容易看出X=(4，0，0)是一可行解。对偶问题是一可行解。对偶问题将三个约束的两端分别相加得将三个约束的两端分别相加得,而第二个约束有而第二个约束有y21,矛盾，故对偶问题无可行解，因而原问题具有矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。无界解，即无最优解。3.2对偶性偶性质DualpropertyChapter3对偶理论对偶理论DualTheory【性性质质6】LP(max)的的检检验验数数的的相相反反数数对对应应于于DP(m
20、in)的的一一组组基基本本解解。其其中中第第j个个决决策策变变量量xj的的检检验验数数的的相相反反数数对对应应于于(DP)中中第第j个个松松弛弛变变量量的的解解，第第i个个松松弛弛变变量量的的检检验验数数的的相相反反数数对对应应于于第第i个个对对偶偶变变量量yi的的解解。反反之之，(DP)的的检检验验数数(注注意意：不不乘乘负负号号)对对应应于于(LP)的一组基本解。的一组基本解。3.2对偶性偶性质Dualproperty注：注：应用性质应用性质6 6 的前提是线性规划为规范形式，而的前提是线性规划为规范形式，而性质性质1-51-5则对所有形式线性规划有效。则对所有形式线性规划有效。Chapt
21、er3对偶理论对偶理论DualTheory【例例3.8】线性规划线性规划(1)用单纯形法求最优解；用单纯形法求最优解；(2)写出每步迭代对应对偶问题的基本解；写出每步迭代对应对偶问题的基本解；(3)从最优表中写出对偶问题的最优解；从最优表中写出对偶问题的最优解；(4)用公式用公式Y=CBB-1求对偶问题的最优解。求对偶问题的最优解。【解解】(1)加入松弛变量加入松弛变量x4、x5后，单纯形迭代后，单纯形迭代如表如表3-5所示。所示。3.2对偶性偶性质DualpropertyChapter3对偶理论对偶理论DualTheoryXBx1x2x3x4x5b表表（1）x4x5211024100124j
22、62100表表（2）x1x5101/21/2131/21/20113j01530表表（3）x1x2100146011246j001122表表3-53.2对偶性偶性质Dualproperty最优解最优解X=(4，6，0)T，最优值，最优值Z=6426=12；Chapter3对偶理论对偶理论DualTheory(2)设对偶变量为设对偶变量为y1、y2,松弛变量为松弛变量为y3、y4、y5,Y=(y1、y2、y3、y4、y5)，由由 性性 质质 6得得 到到 对对 偶偶 问问 题题 的的 基基 本本 解解 (y1、y2、y3、y4、y5)=(4,5,1,2,3)，即，即表表25(1)中中=(6，2，
23、1，0，0)，则则Y(1)=(0，0，-6，2，1)表表25(2)中中=(0，1，5，3，0)，则则Y(2)=(3，0，0，1，5)表表35(3)中中=(0，0，11，2，2)，则则Y（3）=(2，2，0，0，11)3.2对偶性偶性质DualpropertyChapter3对偶理论对偶理论DualTheory(3)因因为为表表32(3)为为最最优优解解，故故Y（3）=(2，2，0，0，11)为对偶问题最优解；为对偶问题最优解；CB=(6，2)，因而，因而(4)表表32(3)中的最优基中的最优基B-1为表为表32(3)中中x4，x5两列的系数，即两列的系数，即3.2对偶性偶性质Dualprope
24、rtyChapter3对偶理论对偶理论DualTheory根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：表表36一个问题一个问题max另一个问题另一个问题min有最优解有最优解有最优解有最优解性质性质4无无无最优解无最优解无最优解无最优解性质性质4最最优优无界解无界解(有可行解有可行解)无可行解无可行解性质性质2解解无可行解无可行解无界解无界解(有可行解有可行解)应用应用已知最优解已知最优解通过解方程通过解方程求最优解求最优解性质性质5已知检验数已知检验数检验数乘以检验数乘以1求得基本解求得基本解性质性质63.2对偶性偶性质Du
25、alpropertyChapter3对偶理论对偶理论DualTheory作业：教材作业：教材P801.6(1)3.1线性规划的对偶模型线性规划的对偶模型DualmodelofLP1.如何写规范与非规范问题的对偶问题如何写规范与非规范问题的对偶问题;2.本节介绍的本节介绍的6个性质都是原问题与对偶问题的有关解的对应关个性质都是原问题与对偶问题的有关解的对应关系；系；3.性质性质5和性质和性质6可用来已知一个问题的最优解求另一个问题的最可用来已知一个问题的最优解求另一个问题的最优解；优解；Chapter3对偶理论对偶理论DualTheory互补松弛定理的解释：互补松弛定理的解释：若若原原问问题题(LP)最最优优解解X*中中第第j个个变变量量Xj*为为正正,则则对对偶偶问问题题(DP)与与之之对对应应的的第第j个个约约束束在在最最优优情情况况下下呈呈严严格格等等式式（即松弛变量为（即松弛变量为0）；）；若若对对偶偶问问题题(DP)中中第第j个个约约束束在在最最优优情情况况下下呈呈严严格格不不等等式，则原问题式，则原问题(LP)最优解最优解X*中第中第j个变量个变量Xj*必为必为0。3.2对偶性偶性质Dualproperty