线性规划的对偶理论ppt课件.ppt

《线性规划的对偶理论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对偶单纯形算法1.对偶问题几种解法2.对偶问题的经济解释——影子价格变换形式如下：原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项例二、原问题对偶问题的的一些解法1：对偶问题与原问题之间的关系。2：利用互补松弛性质。3：对偶单纯形法。例1、已知原问题的最优解为X*=（0,0,4），Z=12试求对偶问题的最优解。解：（1）（2）（3）将X*=（0,0,4）代入原问题中，有下式：所以，根据互补

2、松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为Y*=（0,0,3），W=12。(2)对偶问题与原问题的解的关系利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。⑴.设原问题为：maxZ=CXAX≤bX≥0引入xs，构建初始基变量，然后，用单纯形法求解。当检验数满足σj≤0，则求得最优解。此时，xs对应的σs为-Y*，故求对偶Y*，只要将最优单纯形表上xs对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1例一、cj

3、1018000cBxBbx1x2x3x4x50x317052100170/20x410023010100/30x515015001150/5-Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初始表最终表由上表可知：X*=（50/7,200/7），Z=4100/7对偶问题的最优解：Y*=（0,32/7,6/7），W=4100/7也就是外加工时的收费标准。定义：在一对P和D中，若P的

4、某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。3.对偶问题的经济解释——影子价格设：B是问题P的最优基，由前式可知，Z*=CBB-1b=Y*b=y*1b1+y*2b2+…+y*Ibi+…+y*mbm当bi变为bi+1时（其余右端项不变，也不影响B），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1目标函数最优值变为：Z′*=y*1b1+y*2b2+…+y*I（bi+1）+…+y*mbm∴△Z*=Z′*－

5、Z*=y*i也可以写成：即y*i表示Z*对bi的变化率。其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是第i个约束条件的影子价格。也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。若第i种资源的单位市场价格为mi，当yi>mi时，企业愿意购进这种资源，单位纯利为yi－mi，则有利可图；如果yi

6、增加了32/7即y*2x101020304050601020304050x2123(55/7.199/7)当b2增加一个单位时，目标函数怎么变化。01020304050601020304050x2x1123(50/7.200/7)当b1增加一个单位时，目标函数怎么变化。目标函数没有发生变化01020304050601020304050x2x1123(47/7.202/7)目标函数增加了6/7即y*3当b3增加一个单位时，目标函数怎么变化。01020304050601020304050x2x1123(47/7.202/7)目标函数增加了100/7不是6

7、00/7当b3增加100个单位时，目标函数怎么变化。012345678123456⑴⑵⑶⑷x2x1(42)⑴′X*=（4,2,0,0,0,4）Y*=（0,1.5,0.125,0）当b1增加1时，目标函数不变化。012345678123456⑴⑵⑶⑷x2x1(33)⑵′当b2增加1时，目标函数增加1而不是y2*的值。012345678123456⑴⑵⑶⑷x2x1(4.25,1.875)⑶′当b3增加1时，目标函数增加0.125。012345678123456⑴⑵⑶⑷x2x1(42)⑷′当b4增加1时，目标函数不变化。