运筹学第3章-对偶模型课件.ppt

赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院管理运筹学管理运筹学 模型与方法模型与方法1第第3 3章对偶模型章对偶模型3 3.1.1线性性规划的划的对偶关系偶关系3 3.2.2线性性规划的划的对偶性偶性质3.33.3对偶偶单纯形法形法23.13.1线性规划的对偶关系线性规划的对偶关系对偶偶问题例例1-1.某工厂要安排甲、乙两种产品分别在车间某工厂要安排甲、乙两种产品分别在车间A、B生产，生产，然后都在然后都在C车间装配生产数据如下表：车间装配生产数据如下表：问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？最多？3解：解：设设安排甲、乙两种产品产量分别为安排甲、乙两种产品产量分别为x xj j 件件 max z=3x max z=3x1 1+2x+2x2 2 s.t.x s.t.x1 1 6 6 2x 2x2 28 8 2x2x1 1+3x+3x2 21818 x xj j0 0（j=1,2j=1,2）4例例3-3-1.将例将例1-11-1中三种中三种资源用于源用于对外加工，如何外加工，如何给资源定价源定价？解：解：设设三种资源分别可获利润为三种资源分别可获利润为yj j(100(100元元/工时工时)m minin w w=6y 6y1 1 +8y8y2 2 +18y18y3 3 s.t.s.t.y y1 1 +2y2y3 3 33 2 2y y2 2+3y3y3 3 2 2 y yj j0 0（j=1,2j=1,2,3,3）5对偶关系偶关系规范范对偶关系（偶关系（对称称对偶）偶）标准形准形LPLP对偶关系（非偶关系（非对称称对偶）偶）一般一般对偶关系（混合偶关系（混合对偶）偶）6规范范对偶关系（偶关系（对称称对偶）偶）其中：其中：C=C=（c c1 1，c c2 2,c,cn n)T T b=b=（b b1 1，b b2 2,b,bm m)T T X=X=（x x1 1，x x2 2,x,xn n)T T Y=Y=（y y1 1，y y2 2,y,ym m)T TA=A=A=A=a a a a11111111 a a a a12121212 a a a a1n1n1n1na a a a11111111 a a a a12121212 a a a a1n1n1n1n a a a am1m1m1m1 a a a am m m m2 2 2 2 a a a anmnmnmnm maxmaxmaxmax z=2 xz=2 x1 1+x+x2 2 5 5x x2 2 15 156 6x x1 1+2x+2x2 2 24 24x x1 1+x+x2 2 5 5x x1 1，x x2 2 0 0st st.6 6y y2 2+y+y3 32 25 5y y1 1+2y+2y2 2+y+y3 31 1z=15yz=15y1 1+24y+24y2 2 +5y+5y3 3minminy y1 1,y,y2 2,y,y3 30 0st.st.X 0st.AX bmax z=CTXY 0st.ATY Cmin w=bTYP57表表3-2，37例例3-23-2标准形标准形LPLP对偶关系（非对称对偶）对偶关系（非对称对偶）X X 0 0st.st.AX AX=b bmax z=max z=C CT TX XY Y 自由自由st.st.A AT TY CY Cmin w=min w=b bT TY Y m m m minininin w w=5y5y1 1+6y6y2 2 2y2y1 1+3y+3y2 2 5 5y y1 1+2+2y y2 2 1 13y3y1 1+y y2 2 2 2st.st.x x2 2+3x3x3 3=5 53x3x1 1+2+2x x2 2+x x3 36 6=z=5z=5x x1 1+x x2 2 +2x2x3 3m maxaxx x1 1,x x2 2,x x3 30 0st.st.2x1+P58表表3-48一般一般对偶关系（混合偶关系（混合对偶）偶）例例3-3x x1 1 0,x 0,x2 2 0,x 0,x3 3无约束无约束 st.st.a a1111x x1 1+a+a1212x x2 2+a+a1313x x3 3 b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2323x x3 3 =b =b2 2a a3131x x1 1+a+a3232x x2 2+a+a3333x x3 3 b b3 3max z=cmax z=c1 1x x1 1+c+c2 2x x2 2+c+c3 3x x3 3 min w=bmin w=b1 1y y1 1+b+b2 2y y2 2+b+b3 3y y3 3a a1111y y1 1+a a2121y y2 2+a a3131y y3 3 c c1 1a a1212y y1 1+a a2222y y2 2+a a3232y y3 3 c c2 2a a1313y y1 1+a a2323y y2 2+a a3333y y3 3 =c=c3 3st.st.y y1 10,y0,y2 2无约束无约束，y y3 3 0 09对偶规则对偶规则 变量、约束与系数变量、约束与系数&原问题原问题有有m个约束条件，个约束条件，对偶问题对偶问题有有m个个变量变量&原问题原问题的规范约束（的规范约束（max,或或min，）对应）对应对偶问题对偶问题的变量的变量0；&原原问题问题的非规范的非规范约束（约束（max,或或min，）对应）对应对偶问题对偶问题的的变量变量0；&原问题原问题的等式约束的等式约束（max,=或或min，=）对应对应对偶问题对偶问题的的变量无限制。

变量无限制原问题原问题有有n个变量，个变量，对偶问题对偶问题有有n个约束条件个约束条件&原原问题问题的价值系数对应的价值系数对应对偶问题对偶问题的右端项的右端项&原问题原问题的右端项对应的右端项对应对偶问题对偶问题的价值系数的价值系数&原问题原问题的系数矩阵的系数矩阵转置后为转置后为对偶问题对偶问题系数矩阵系数矩阵P59表表3-5113 3.2.2线性规划的对偶性质线性规划的对偶性质11.对称性对称性：对偶问题的对偶问题是原：对偶问题的对偶问题是原问题12.弱弱对偶性对偶性：原：原问题的任一可行解的目标函数值，问题的任一可行解的目标函数值，不优于其不优于其对对偶问题偶问题任一可行解任一可行解的目标函数值的目标函数值13.最优性最优性：,则则 分别为原问题与对偶问题的最优分别为原问题与对偶问题的最优解1214.强对偶性强对偶性：若一个问题有最优解，则另一问题也有最优解，：若一个问题有最优解，则另一问题也有最优解，且二者最优目标值相等且二者最优目标值相等无界性无界性：若一个问题有无界解，则另一问题无可行解若一个问题有无界解，则另一问题无可行解对偶定理对偶定理：要么同时有解，且最优值相等；要么同时无解。

要么同时有解，且最优值相等；要么同时无解不可能一个有解，一个无解不可能一个有解，一个无解1315.互互补性性：原：原问题与与对偶偶问题的的变量或基本解之量或基本解之间具有互具有互补性互互补变量量 互互补基本解基本解：目：目标值相等相等P1与与D1互相对偶互相对偶PS与与DS广义对偶广义对偶1416.兼容性兼容性：原问题：原问题PS单纯形表的检验行，对应对偶问题单纯形表的检验行，对应对偶问题DS的一的一个基本解；最优单纯形表的检验行，对应对偶问题的最优解个基本解；最优单纯形表的检验行，对应对偶问题的最优解互补基本解均可行必然均为最优解15161717.基本松基本松紧性性：互：互补变量量满足足 对于非退化的基本解于非退化的基本解u若若X可行，可行，则有有u若若Y可行，可行，则有有18.最最优松松紧性性：这些性质同样适用于非对称形问题这些性质同样适用于非对称形问题18对偶偶变量的量的经济属性属性p 是第是第i种资源的种资源的边际价值边际价值p 是第是第i种资源的种资源的影子价值影子价值（shadow value）单位产值（收入），单位产值（收入），影子价格影子价格；单位利润，单位利润，影子利润影子利润。

p 的值相当于在资源得到最优利用的生产条件下，的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数每增加一个单位时目标函数z z的贡献（增量）的贡献（增量）19对资源源i现用用总量的量的经济分析分析 代表影子价格代表影子价格 ，可增加，可增加资源源i的用量，可的用量，可买进资源，源，对总目目标贡献献 ；，可，可买进资源，源，对总目目标贡献献 ；，应减少减少资源源i的用量，可的用量，可卖出出资源，源，对总目目标贡献献 代表影子利代表影子利润资源源i单位成本位成本 ，则资源源i对总价价值的的单位位贡献即献即 ，即，即 为资源源i的影子价格的影子价格对资源源i分配方案分配方案的的经济分析分析20对偶偶问题的的经济意意义(3-12b)：资源源aji对总价价值的的贡献，献，应当不少于将其用于当不少于将其用于项目目j时的的贡献献cj;(3-12c)：资源源i对总价价值的的贡献必献必须非非负，否，否则不用或出售不用或出售3-12a)：资源源隐性价性价值w，确定，确定转让的成交价格最低限度的成交价格最低限度yi21最最优松松紧性的性的经济意意义每每经营一个一个单位位项目目xj所消耗的各种所消耗的各种资源的影子价源的影子价值总和，必和，必定等于定等于该项目目创造的造的单位价位价值cj。

当资源当资源i的供量未被耗尽时，该资源的边际价值必为的供量未被耗尽时，该资源的边际价值必为023最最优性性检验的的经济意意义 是决策是决策变量，量，说明明该资源的影子利源的影子利润为负，需要改善需要改善是剩余是剩余变量量说明明该资源的影子利源的影子利润小于小于项目目j的的单位利位利润cj，需要改善需要改善24互互补基本解均可行必然均基本解均可行必然均为最最优解对偶偶单纯形法基本思路形法基本思路1、标准化，准化，允允许bi0;2、建立典式，、建立典式，若若，转至至3；3、最、最优性性检验，否，否则转至至4；4、解的判断、解的判断原原问题无可行解，无可行解，对偶偶问题无下界；否无下界；否则，转至至5；5、换基；基；先确定出基先确定出基变量量后确定入基后确定入基变量量主元主元为负数数3 3.3.3对偶单纯形法对偶单纯形法2526例例3-427前提条件前提条件进化进化换基换基主元主元原原SM先入先入后出后出 正正数数对偶对偶SM先出先出后入后入 负负数数原本、对偶单纯形法对比原本、对偶单纯形法对比28交替交替单纯形法形法无无须顾及二者的前提条件及二者的前提条件一般可，一般可先先对偶偶单纯形法，化形法，化为原本可行原本可行；再用；再用单纯形法形法，使，使。

29例例3-5cj3-20100基基bx1x2x3x4x5x63x1810-1/400 x5005/20-1/41-3/41x340-1/213/401/428060001无穷多解无穷多解30cj1200基基bx1x2x3x41x1110-1/3-1/32x20012/3-1/3001-1例例3-6原：无界解原：无界解对偶：无可行解对偶：无可行解例例3-7cj1100基基bx1x2x3x40 x4-5/205/21/211x1-1/217/21/2005/21/20原：无可行解原：无可行解对偶：无界解对偶：无界解32习 题3.2（2）（）（4）3.10（1）3.113.12（1）（）（2）交替）交替单纯形法求解形法求解4、已知已知线性性规划划问题其其对偶偶问题的最的最优解解为 试用用对偶偶性性质找出原找出原问题的最的最优解33写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits34谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal。