《对偶和灵敏度分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《对偶和灵敏度分析PPT讲稿.ppt（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1页，共105页，编辑于2022年，星期六第第三三章章 内容提要内容提要3.1 单纯形法的矩阵描述3.2 对偶问题的提出3.3 线性规划的对偶理论3.4 影子价格3.5 对偶单纯形法3.6 灵敏度分析第2页，共105页，编辑于2022年，星期六3.1 3.1 单纯形法的矩阵描述单纯形法的矩阵描述介绍用矩阵来描述单纯形法的计算过程，有助于加深对单纯形法的理解，和学习对偶理论。第3页，共105页，编辑于2022年，星期六设线性规划问题：Max z=CXAX=bX 0其中松驰变量 Xs=(xn+1,xn+2,xn+m)TI 是mm 阶单位矩阵化为标准型：Max z=CX+0Xs (3.1)AX+I
2、Xs=b (3.2)X 0,Xs 0 (3.3)第4页，共105页，编辑于2022年，星期六设B是一个可行基，则可将系数矩阵(A,I)分为两块(B,N)，N 是非基变量的系数矩阵。对应于B的变量xB1,xB2,xBm 是基变量，用向量 XB=(xB1,xB2,xBm)T 表示其它为非基变量，则第5页，共105页，编辑于2022年，星期六同时将 C 也分为两块(CB,CN)，则第6页，共105页，编辑于2022年，星期六这时可将(3.1),(3.2),(3.3)式改写为 Max z=CBXB+CNXN (3.4)BXB+NXN=b (3.5)XB 0,XN 0 (3.6)将(3.5)式移项后，得
3、到 BXB=b-NXN (3.7)给(3.7)式左乘B-1后，得到XB的表达式 XB=B-1 b-B-1 NXN (3.8)将(3.8)式代入目标函数，得 z=CB B-1 b+(CN-CBB-1 N)XN (3.9)第7页，共105页，编辑于2022年，星期六 XB=B-1 b-B-1 NXN (3.8)z=CB B-1 b+(CN-CBB-1 N)XN (3.9)令非基变量XN=0，得到一个基可行解则，目标函数值 z=CB B-1 b第8页，共105页，编辑于2022年，星期六 XB=B-1 b-B-1 NXN (3.8)z=CB B-1 b+(CN-CBB-1 N)XN (3.9)从上式
4、中可以看到：非基变量 XN 的系数CN-CBB-1 N 就是检验数，即N=CN-CBB-1 N 因为 XB 在式(2.9)中的系数是0，即CB-CBB-1 B=0 故包括基变量在内的所有检验数可用 C-CBB-1A0表示。松驰变量检验数为-CBB-1，故所有检验数可用 C-CBB-1A和-CBB-1，即 C-YA和-Y 表示。第9页，共105页，编辑于2022年，星期六将式(3.8)和(3.9)综合写成矩阵式如下：XB=B-1 b-B-1 NXN (3.8)z=CB B-1 b+(CN-CBB-1 N)XN (3.9)右端项RHS基变量非基变量XBXN1XsB-1bIB-1N1B-1-CBB-
5、1b0CN1-CBB-1N1-CBB-1在单纯形表中表示如下：第10页，共105页，编辑于2022年，星期六3.2 3.2 对偶问题的提出对偶问题的提出在第1章例1中讨论了工厂生产计划模型及其解法，现从另一个角度来讨论这个问题。假设该工厂的决策者决定不生产产品I，II，而将其所有资源出租或外售，这时工厂的决策者就要考虑给每种资源如何定价的问题。第11页，共105页，编辑于2022年，星期六某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示：III合计设备128 台时原材料A4016 千克原材料B0412 千克该工厂每生产一件 I 可获得
6、2元，每生产一件产品II可获得3元。问应如何安排计划使该工厂获得最多？第12页，共105页，编辑于2022年，星期六其数学模型归结为：目标函数 Max z=2 x1+3 x2约束条件 x1+2 x28 4 x1 16 s.t.4 x2 12 x1,x20第13页，共105页，编辑于2022年，星期六设用 y1,y2,y3 分别表示出租单位设备台时的租金和出让单位原材料A,B的利润。若用一个单位设备台时和4个单位原材料A可以生产一件产品I可获得2元，那么生产每件产品I的设备台时和原材料出租和出让的所有收入不应低于生产一件产品I的利润，即 y1+4y22换一种思维的角度第14页，共105页，编辑于
7、2022年，星期六同理，将每生产每件产品II的设备台时和材料出租和出让的所有收入不应低于生产一件产品II的利润，即 2y1+4y33把工厂所有设备台时和资源都出租或出让，其收入为 w=8y1+16y2+12y3第15页，共105页，编辑于2022年，星期六从工厂的决策者来看，当然 w 越大越好，但从接受者来看他的支付越少越好。因此决策者只能在满足所有产品利润的条件下，使其总收入尽可能地小。即解如下线性规划问题 Min w=8y1+16y2+12y3 y1+4y2 2 2y1 +4y33 y1,y2,y3 0这个问题即为原问题的对偶问题。第16页，共105页，编辑于2022年，星期六矩阵形式的对
8、偶问题矩阵形式的对偶问题从前面知检验数C-CBB-1A和-CBB-1均非正时，线性规划问题达到最优解，即 C-YA0和-Y 0则Y 0，YA C对单纯形因子Y=CBB-1两边同乘b得Yb=CBB-1b=z因Y 的上界为无限大，所以只存在最小值。由此得另一个线性规划问题：Min w=Yb YA C Y 0此即原问题Max z=CX|AXb,X0的对偶问题第17页，共105页，编辑于2022年，星期六3.3 3.3 线性规划的对偶理论线性规划的对偶理论原问题与对偶问题的关系第18页，共105页，编辑于2022年，星期六3.3.1 3.3.1 原问题与对偶问题的关系原问题与对偶问题的关系左右不对称，
9、左右 右左 阅读p54-56原问题P(或对偶问题)对偶问题D(或原问题)目标函数 max z 目标函数 min w 变量 n 个 约束条件 n 个 变量0 约束条件 变量0 约束条件 变量无约束 约束条件=变量 m 个 约束条件 m 个 变量 0 约束条件 变量 0 约束条件 变量无约束 约束条件=约束条件右端项 目标函数变量的系数 约束条件右端项 目标函数变量的系数第19页，共105页，编辑于2022年，星期六例 写出下述线形规划问题的对偶问题Max Z=5x1+4x2+6x3 x1+2x2 2 x1 +x33-3x1+2x2+x3-5 x1-x2+x31x10;x20,;x3无约束minW
10、=2y1+3y2-5y3+y4 y1+y2-3y3+y45 2y1 +2y3-y44 y2+y3+y4=6y10,y2,y3 0,y4无约束第20页，共105页，编辑于2022年，星期六例 写出下述线形规划问题的对偶问题minZ=2x1+3x2-5x3+x4 x1+x2-3x3+x45 2x1 +2x3-x44 x2+x3+x46x10,x2,x30;x4无约束maxZ=5y1+4y2+6y3 y1+2y2 2 y1 +y33-3y1+2y2+y3-5 y1-y2+y3=1y10,y20,y3无约束第21页，共105页，编辑于2022年，星期六写出下列问题的对偶问题：写出下列问题的对偶问题：解
11、解：先将先将约束约束条件变形为条件变形为“”形式形式 第22页，共105页，编辑于2022年，星期六第23页，共105页，编辑于2022年，星期六再根据非对称形式的对应关系，直接写出对偶规划 第24页，共105页，编辑于2022年，星期六3.3.2 3.3.2 对偶问题的基本性质对偶问题的基本性质1.1.对称性对称性2.2.弱对偶性弱对偶性3.3.无界性无界性4.4.可行解是最优解时的性质可行解是最优解时的性质5.5.对偶定理对偶定理6.6.互补松驰性互补松驰性7.7.解的关系解的关系第25页，共105页，编辑于2022年，星期六1 1 对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原
12、问题。对原问题：Max z=CXAXbX0对(1)式两边取负号有 -Min w=-Yb又因Min w=-Max(-w)故可得 Max(-w)=-Yb -YA-C Y0其对偶问题：Min w=Yb （1）YACY0它的对偶问题是：Min-w=-CX;-AX-b;X0又因Min w=-Max(w)故可得 Max w=Max z=CX AXb X0第26页，共105页，编辑于2022年，星期六2 2 弱对偶性弱对偶性若若 是原问题的可行解，是原问题的可行解，是对偶问题的可行解，则存在是对偶问题的可行解，则存在第27页，共105页，编辑于2022年，星期六3 3 无界性无界性若原问题若原问题(对偶问题
13、对偶问题)无界解，则对偶问题无界解，则对偶问题(原问题原问题)无可行解。无可行解。第28页，共105页，编辑于2022年，星期六4 4 可行解是最优解的性质可行解是最优解的性质若 是原问题的可行解，是对偶问题的可行解，则当 ，是最优解。第29页，共105页，编辑于2022年，星期六5 5 对偶定理对偶定理若原问题有最优解，那么对偶问题也有最优解；且目标函若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。数值相等。第30页，共105页，编辑于2022年，星期六试用对偶理论判断下面线性规划是否有最优解试用对偶理论判断下面线性规划是否有最优解 解解解解:此规划存在可行解此规划存在可行解 ，
14、其对偶规划为，其对偶规划为 第31页，共105页，编辑于2022年，星期六显然，对偶规划没有可行解，因此，原规划没有最优解。显然，对偶规划没有可行解，因此，原规划没有最优解。第32页，共105页，编辑于2022年，星期六推论推论 若原问题有一个对应于基若原问题有一个对应于基B B的最优解，那么此时的最优解，那么此时的单纯形乘子的单纯形乘子Y YC CB BB B-1-1是对偶问题的一个最优解是对偶问题的一个最优解第33页，共105页，编辑于2022年，星期六 maxZ=3x1+5 x2 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 例例Cj比值CBXBb检验数jx
15、1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9第34页，共105页，编辑于2022年，星期六Cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1最终单纯型表最终单纯型表求其对偶问题的最优解？求其对偶问题的最优解？第35页，共105页，编辑于2022年，星期六求解下面线性规划问题，并根据最优单纯形表中的检验求解下面线性规划问题，并根据最优单纯形表中的检验数，给出其对偶问题的最优解。数，给出其对偶问题的最优解。解解
16、 引入松弛变量、将模型化为标准型，经求解后得引入松弛变量、将模型化为标准型，经求解后得到其最优单纯形表到其最优单纯形表 第36页，共105页，编辑于2022年，星期六c 4 3 7 0 0 cB xB B-1b x1 x2 x3 x4 x5 3 x2 25 -3/4 1 0 3/4 -1/2 7 x3 25 5/4 0 1 -1/4 1/2 Z 250 -10/4 0 0 -1/2 -2对偶规划的最优解为对偶规划的最优解为 :第37页，共105页，编辑于2022年，星期六6 6 互补松驰性互补松驰性 若若 X*X*和和 Y*Y*分别是原问题和对偶问题的可行解，那么它分别是原问题和对偶问题的可行
17、解，那么它们为最优解的充要条件是们为最优解的充要条件是 (C-Y*AC-Y*A)X X=0=0 和和Y Y(b-AX*b-AX*)=0)=0若由最优解得约束条件为绝对不等式，则对偶问题对若由最优解得约束条件为绝对不等式，则对偶问题对应变量为零。应变量为零。变量最优解值大于零，对偶问题对应约束条件取等号。变量最优解值大于零，对偶问题对应约束条件取等号。Key第38页，共105页，编辑于2022年，星期六例 已知线性规划问题Min z=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x5 4 2x1-x2+3x3+x4+x5 3 x1,x2,x3,x4,x5 0其对偶问题的最优
18、解为 y1=4/5,y2=3/5，试应用对偶理论求原问题的解。第39页，共105页，编辑于2022年，星期六将将 y1=4/5,y2=3/5的值代入，得知的值代入，得知 为严格不等式，于是由互补松驰为严格不等式，于是由互补松驰性，必有性，必有 x2=x3=x4=0 解：写出对偶问题：解：写出对偶问题：Max S=4y1+3y2 y1+2y2 2 y1-y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0又因又因 y1,y2 0，故原问题的两个约束条件必为紧约束，即有，故原问题的两个约束条件必为紧约束，即有 x1+3x5=4 2x1+x5=3 解得解得 x1=x5=1
19、即即 X*=(1,0,0,0,1)T,Z*=5第40页，共105页，编辑于2022年，星期六7 7 解的关系解的关系则原问题单纯表的检验数行对应其对偶问题的一个基解。则原问题单纯表的检验数行对应其对偶问题的一个基解。Ys1 是对应原问题是对应原问题中基变量中基变量XB的剩余变量，的剩余变量，Ys2 是对应原问题中基变量是对应原问题中基变量XN 的剩余变量的剩余变量设原问题：设原问题：Max z=CXAX+Xs=bX,Xs0其对偶问题：其对偶问题：Min w=Yb YA-Ys=CY,Ys0XBXNXs0CN1-CBB-1N1-CBB-1Ys1-Ys2-Y第41页，共105页，编辑于2022年，星
20、期六B B-1-1在单纯表中的位置在单纯表中的位置可将可将(3.4),(3.5)式式 Max z=CBXB+CNXN (3.4)BXB+NXN=b (3.5)改写为改写为 -z+CB XB+CN1XN1+0Xs=0 BXB+NXN+IXs=b最后得最后得B-1即为初始基变量在最终单纯形表中的列向量组成。即为初始基变量在最终单纯形表中的列向量组成。第42页，共105页，编辑于2022年，星期六B-1初始基变量B-1为初始基变量在最终单纯形表中的列向量组成。第43页，共105页，编辑于2022年，星期六3.4 3.4 影子价格影子价格前面讲到，在单纯法的每一步迭代中，目标函数取值前面讲到，在单纯法
21、的每一步迭代中，目标函数取值 z z=C CB BB B-1-1b b 和检验数和检验数 C CN N-C-CB BB B-1-1N N中都有乘子中都有乘子 Y Y=C CB BB B-1-1那么那么Y Y 的经济意义是什么呢？的经济意义是什么呢？设设B B 是是max max z z=CX CX|AXAXb b,X X00的最优基，则的最优基，则 z*z*=C CB BB B-1-1b=Y*bb=Y*b两边对两边对b b求偏导有求偏导有 z*/z*/b b=C CB BB B-1-1=Y*=Y*从对偶问题来看，变量从对偶问题来看，变量 y yi i*的经济意义是在其它条件不变的的经济意义是在
22、其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。情况下，单位资源变化所引起的目标函数的最优值的变化。这种资源的单位改变量引起目标函数的价值改变量，称为该这种资源的单位改变量引起目标函数的价值改变量，称为该资源的影子价格。资源的影子价格。第44页，共105页，编辑于2022年，星期六影子价格的特征影子价格的特征影子价格的大小客观地反映了资源在系统内的稀缺程度。影子价格的大小客观地反映了资源在系统内的稀缺程度。根据互补松驰定理的条件，如果某一资源在系统内供大于求，其影根据互补松驰定理的条件，如果某一资源在系统内供大于求，其影子价格就为零。子价格就为零。即增加该资源的供应不会引起系
23、统目标的任何变化。即增加该资源的供应不会引起系统目标的任何变化。如果某一资源是稀缺资源（即相应约束条件的剩余变量为零）如果某一资源是稀缺资源（即相应约束条件的剩余变量为零），则影子价格必然大于零。，则影子价格必然大于零。影子价格越高，资源在系统中越稀缺。影子价格越高，资源在系统中越稀缺。第45页，共105页，编辑于2022年，星期六影子价格的特征影子价格的特征在完全市场经济条件下，当某种资源的市场价格低于影子价在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大再生产；而当某种资源的格时，企业应买进该资源用于扩大再生产；而当某种资源的市场价格高于影子价格时，企业应
24、卖掉已有资源。市场价格高于影子价格时，企业应卖掉已有资源。影子价格是一种边际价值，与经济学所说的边际成本的概念影子价格是一种边际价值，与经济学所说的边际成本的概念相似，因而在经济管理中有重要的应用价值。相似，因而在经济管理中有重要的应用价值。影子价格是对系统资源的一种最优估价，只有当系统达到最影子价格是对系统资源的一种最优估价，只有当系统达到最优时，才能赋予该资源的这种价值，因此影子价格也称为最优时，才能赋予该资源的这种价值，因此影子价格也称为最优价格。优价格。影子价格的取值与系统状态有关。系统内部资源数量、技术影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起
25、影子价格的变化，影子价系数和价格的任何变化，都会引起影子价格的变化，影子价格是一种动态价格。格是一种动态价格。第46页，共105页，编辑于2022年，星期六事事实实上上，如如例例中中互互为为对对偶偶LPLP问问题题分分别别描描述述生生产产计计划划问问题题和和资资源源的定价问题，其数学模型分别是：的定价问题，其数学模型分别是：原问题原问题对偶问题对偶问题第47页，共105页，编辑于2022年，星期六 cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 -1/5 -6/5用单纯形法求得其最优表为：用单纯形法求得
26、其最优表为：由此，它们的最优解分别是由此，它们的最优解分别是X*=(6,4)X*=(6,4)T T和和Y*=(1/5,6/5)Y*=(1/5,6/5)最优值为：最优值为：Z*=W*=36=24yZ*=W*=36=24y1 1*+26y*+26y2 2*第48页，共105页，编辑于2022年，星期六 其其中中y y1 1*=1/5*=1/5表表示示单单独独对对材材料料增增加加1 1个个单单位位，可可使使Z Z值值增增加加1/51/5个个单单位位的的利利润润；y y2 2*=6/5*=6/5表表示示单单独独对对工工时时增增加加1 1个个单单位位，可可使使Z Z值值增增加加6/56/5个个单单位的利
27、润。位的利润。2.2.影子价格的定义影子价格的定义 把把某某一一经经济济结结构构中中的的某某种种资资源源，在在最最优优决决策策下下的的边边际际价价值值称称为为该该资资源在此经济结构中的影子价格。源在此经济结构中的影子价格。影影子子价价格格是是在在最最优优决决策策下下对对资资源源的的一一种种估估价价，没没有有最最优优决决策策就就没没有有影影子子价价格格，所所以以影影子子价价格格又又称称“最最优优计计划划价价格格”，“预预测测价价格格”等等。等等。第49页，共105页，编辑于2022年，星期六（2 2）对市场资源的最优配置起着推进作用）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大
28、的企业，资源优先供给即在配置资源时，对于影子价格大的企业，资源优先供给 （3 3）可以预测产品的价格）可以预测产品的价格产产品品的的机机会会成成本本为为C CB BB B-1-1A-CA-C，只只有有当当产产品品价价格格定定在在机机会会成成本本之之上上，企业才有利可图。企业才有利可图。（4 4）可作为同类企业经济效益评估指标之一。）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来的收益就越大，对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。经济效益就越好。（1 1）指出企业挖潜革新的途径）指出企业挖潜革新的途径影价影价00，说明该资源已
29、耗尽，说明该资源已耗尽，成为短线资源。成为短线资源。影价影价=0=0，说明该资源有剩余，说明该资源有剩余，成为长线资源。成为长线资源。影子价格的参谋作用影子价格的参谋作用:第50页，共105页，编辑于2022年，星期六0 1 2 3 4 5 6 7 8可行域x2非可行域x1+2x2=8 4x2=1243214x1=16x1第第1 1章例章例1 1最优解点x1=4，x2=2例1 数学模型归结为：目标函数 Max z=2 x1+3 x2约束条件 x1+2 x28 4 x1 16 s.t.4 x2 12 x1,x20新最优解点(4,2.5)z*增大1.5，此增值即影子价格设备增加1 台时第51页，共
30、105页，编辑于2022年，星期六假设输入参数没有其它变化，那么约束条件右端项的单位增长所引起目标函数值的变化就称为“影子价格”。第52页，共105页，编辑于2022年，星期六3.5 3.5 对偶单纯形法对偶单纯形法根据对偶理论，也可以这样求解线性规划问题：初始解不一定要是基可行解，可以从非基可行解开始，逐步迭代达到最优解。对左端项 b 可不作非负要求。对减去剩余变量的约束条件两端同乘-1后，可找到初始基变量。第53页，共105页，编辑于2022年，星期六对偶单纯法步骤对偶单纯法步骤1.根据线性规划问题，列出初始单纯形表。检查b列数字：若都为非负，而检验数均非正，则已得最优解。若至少还有一个负
31、分量，且检验数均非正，则进入第2步。第54页，共105页，编辑于2022年，星期六2.确定换出变量按 min(B-1b)i|(B-1b)i0=(B-1b)l 对应的基变量为换出变量。即 b 列负数中最小的一个对应的基变量换出。最“富”(负)的b第55页，共105页，编辑于2022年，星期六3.3.确定换入变量确定换入变量在单纯形表中检查在单纯形表中检查 x xl l 所在行的各个系数所在行的各个系数 a aljlj(j=j=1,2,1,2,n n)若所有若所有a aljlj00 ，则无可行解。，则无可行解。若存在若存在a aljlj 0 0 ，计算，计算，并按，并按 规则所对应的非基变量为换入
32、规则所对应的非基变量为换入变量。变量。第56页，共105页，编辑于2022年，星期六4.4.迭代迭代以以 alk 为主元素，按原单纯形法在表中进行迭代运算，得到为主元素，按原单纯形法在表中进行迭代运算，得到新的单纯形表。新的单纯形表。重复重复重复重复1-41-4的步骤，直到找到最优解的步骤，直到找到最优解的步骤，直到找到最优解的步骤，直到找到最优解第57页，共105页，编辑于2022年，星期六例例 用对偶单纯法求解线性规划问题用对偶单纯法求解线性规划问题 Min w=2x1+3x2+4x3 x1+2x2 +x3 3 2x1-x2 +3x3 4 x1,x2,x3 0这个问题化为这个问题化为 Ma
33、x z=-2x1-3x2-4x3 -x1-2x2 -x3+x4 =-3 -2x1+x2-3x3 +x5=-4 x1,x2,x3,x4,x5 0第58页，共105页，编辑于2022年，星期六对偶单纯对偶单纯形法求解形法求解cBxBbx1x2x3x4x5-2-3-400 x4x500-3-4-1-2-21-1-31001-2-3-400cj-zj 1-24/3换出变量的确定min(B-1b)i|(B-1b)i0=(B-1b)l-4计算 确定换入变量x4x10-2-10-5/2-1/21/23/210-1/2-1/20-4-10-1cj-zj 12 8/52x2x1-3-22/5010-1/57/5
34、-2/5-1/51/5-2/500-9/5-8/5-1/5cj-zj 1-z=28/511/5-5/2取得最优解取得最优解X*=(11/5,2/5,0,0,0)TZ*=28/5第59页，共105页，编辑于2022年，星期六最终单纯形表最终单纯形表对偶问题的最优解为对偶问题的最优解为 Y*=(8/5,1/5)x2x1-3-22/5010-1/57/5-2/5-1/51/5-2/500-3/5-8/5-1/5cj-zj 1-z=28/511/5cBxBbx1x2x3x4x5-2-3-400B-1熟练掌握对偶单纯形法熟练掌握对偶单纯形法 参见参见P64 例例5第60页，共105页，编辑于2022年，
35、星期六练习：用对偶单纯形方法求解：练习：用对偶单纯形方法求解：解解:（1 1）引引入入松松弛弛变变量量 x x3 3 ,x x4 4 ,x x5 5 化化为为标标准准形形，并在约束等式两侧同乘并在约束等式两侧同乘-1-1，得到，得到第61页，共105页，编辑于2022年，星期六取取x x3 3 ,x,x4 4,x,x5 5为基变量，此式即为典式形式，并且为基变量，此式即为典式形式，并且检验数皆非正，因此可构初始对偶单纯形表检验数皆非正，因此可构初始对偶单纯形表 第62页，共105页，编辑于2022年，星期六第63页，共105页，编辑于2022年，星期六第64页，共105页，编辑于2022年，星
36、期六例例 用对偶单纯形法求解下面线性规划用对偶单纯形法求解下面线性规划 解解解解:构造对偶单纯形表进行迭代，构造对偶单纯形表进行迭代，第65页，共105页，编辑于2022年，星期六从最后的表可以看到，从最后的表可以看到，B B-1-1b b列元素中有列元素中有-20-200 c cj j min mink k+,k k/rkrk rkrk0 0 第75页，共105页，编辑于2022年，星期六基变量CBl的变化范围CjC15000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/20C1x14100-2/31/3检验数j0002C1/3-5/2-C1/3第76页，
37、共105页，编辑于2022年，星期六 例例 Max Max z z=-2=-2x x1 1-3-3x x2 2-4-4x x3 3 S.t.S.t.-x x1 1-2-2x x2 2-x x3 3+x x4 4 =-3=-3 -2 -2x x1 1+x x2 2-3-3x x3 3+x x5 5=-4=-4 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 00第77页，共105页，编辑于2022年，星期六最优单纯形表 从表中看到3=c3+c3-(c2a13+c1a23)可得到c3 9/5 时，原最优解不变。第78页，共105页，编辑于2022年，星期六例例 胜胜利利家家具
38、具厂厂生生产产桌桌子子和和椅椅子子两两种种家家具具。桌桌子子售售价价5050元元。椅椅子子售售价价3030元元，生生产产桌桌子子和和椅椅子子需需要要木木工工和和油油漆漆工工两两种种工工种种。生生产产一一个个桌桌子子需需要要木木工工4 4小小时时，油油漆漆工工2 2小小时时。生生产产一一个个椅椅子子需需要要木木工工3 3小小时时，油油漆漆工工1 1小小时时。该该厂厂每每月月可可用用木木工工工工时时为为120120小小时时，油油漆漆工工工工时时为为5050小小时时。问问该该厂厂如如何组织生产才能使每月的销售收入最大何组织生产才能使每月的销售收入最大?max z=50 x1+30 x2 4x1+3x
39、2 120 2x1+x2 50 x1,x2 0第79页，共105页，编辑于2022年，星期六例例例例:对上例的目标函数系数进行敏感性分析。对上例的目标函数系数进行敏感性分析。解：解：家具厂问题的最优单纯形表：家具厂问题的最优单纯形表：第80页，共105页，编辑于2022年，星期六c c1 1:x x1 1在在基基的的第第二二行行(r r=2),=2),非非基基变变量量下下标标k k=3=3和和4,4,2323=-1/2,-1/2,2424=3/2,=3/2,可得可得:max max-,-15/1.5,-15/1.5 c c1 1 minmin+,-5/(-0.5),-5/(-0.5)-10-1
40、0 c c1 1 10 10即即:0301（50 c1）(1/2)0;030(-2)（50 c1）3/2 0第81页，共105页，编辑于2022年，星期六c c2 2：x x2 2 在基的第一行，在基的第一行，r r1 1，13131 1，1414-2-2，可得：，可得：maxmax-,(-5)/(1),(-5)/(1)c c2 2 minmin+,(-15)/(-2),(-15)/(-2)-5-5 c c2 2 7.5 7.5即即:0(30+c2)150(1/2)0;0(30+c2)(-2)503/2 0第82页，共105页，编辑于2022年，星期六2.2.右边项发生变化的灵敏度分析右边项发
41、生变化的灵敏度分析(1)(1)分析什么？分析什么？假定只有一个假定只有一个 b br r 变化，假定变化，假定 b br r 从从 b br r 变到变到b br r*=*=b br r+b br r，当当 b br r在什么范围内变化时，不会影响最在什么范围内变化时，不会影响最优基。（不改变产品种类，只调整数量）优基。（不改变产品种类，只调整数量）(2)(2)怎么分析？怎么分析？最优基不变的充要条件是：最优基不变的充要条件是：第83页，共105页，编辑于2022年，星期六第84页，共105页，编辑于2022年，星期六为了保持最优基不变，应使为了保持最优基不变，应使 ，即，即 解不等式组，得解
42、不等式组，得第85页，共105页，编辑于2022年，星期六 例如例如 参数参数bi的变化范围的变化范围 第86页，共105页，编辑于2022年，星期六b b3 3发生发生变化第87页，共105页，编辑于2022年，星期六例例例例:对例的右边项进行敏感性分析。对例的右边项进行敏感性分析。1)1)对对b b1 1进行分析：进行分析：i i=1=1对对 应应 基基 的的 第第 一一 列列，1111=1313=1=1，2121=23 23=-0.5 =-0.5 maxmax-,-20/1,-20/1 b b1 1 minmin+,-15/(-0.5),-15/(-0.5)20 20 b b1 1 30
43、 30第88页，共105页，编辑于2022年，星期六即：即：20 b1 30第89页，共105页，编辑于2022年，星期六2)对 b2 进行分析：i=2 对应基的第二列，3)12=14=-2，22=24=1.5 max-,-15/1.5 b2 min+,-20/(-2)10 b2 10第90页，共105页，编辑于2022年，星期六3 3 3 3、约束条件中的系数变化、约束条件中的系数变化假设只有一个假设只有一个 a aijij 变化。其他数据不变，并且只讨论变化。其他数据不变，并且只讨论 a aijij 为非基变量的系数的情况。因此，为非基变量的系数的情况。因此，a aijij的变化只影响一个
44、检的变化只影响一个检验数。当验数。当 a aijij在什么范围内变化时，不会影响最优解在什么范围内变化时，不会影响最优解(1)(1)分析什么？分析什么？(2)(2)怎么分析？怎么分析？最优解不变的充要条件是：最优解不变的充要条件是：第91页，共105页，编辑于2022年，星期六第92页，共105页，编辑于2022年，星期六其中其中Y Y为对偶最优解，为对偶最优解，y yi i为为Y Y的第的第i i个分量。个分量。为使最优解不变，要使为使最优解不变，要使 即即第93页，共105页，编辑于2022年，星期六4.4.增加新变量的灵敏度分析增加新变量的灵敏度分析 在在管管理理中中经经常常遇遇到到的的
45、问问题题：已已知知一一种种新新产产品品的的技技术术经经济济指指标标，在在原原有有最最优优生生产产计计划划的的基基础础上上，怎怎样样最最方方便便地地决决定定该该产产品品是是否否值值得得投投入入生生产产，可可在在原原线线性性规规划划中中引引入新的变量入新的变量 ；无无论论增增加加什什么么样样的的新新变变量量，新新问问题题的的目目标标函函数数只只能能向好的方向变化。向好的方向变化。第94页，共105页，编辑于2022年，星期六例例例例:家具厂设计了一种新柜子，市场售价为家具厂设计了一种新柜子，市场售价为100100元，生元，生产一个柜子需产一个柜子需9 9个木工工时，个木工工时，3.53.5个油漆工
46、工时。问个油漆工工时。问柜子是否应投产？柜子是否应投产？解：解：解：解：令令 x x5 5 代表柜子产量，新模型为：代表柜子产量，新模型为：max z=50 x1+30 x2 +100 x5s.t.4x1+3x2+x3 +9 x5=120 2x1+x2 +x4+3.5x5=50 x1,x2,x3,x4,x5 0第95页，共105页，编辑于2022年，星期六B-1p5=新变量及其系数放在原单纯形表的最后一列，新向量新变量及其系数放在原单纯形表的最后一列，新向量需经过左乘基的逆矩阵后才能写入最优单纯形表：需经过左乘基的逆矩阵后才能写入最优单纯形表：第96页，共105页，编辑于2022年，星期六计计
47、算算新新产产品品影影子子(机机会会)成成本本：由由y y1 1=5 5，y y2 2=1515，影影子成本子成本 y py pj j 为为 ：9 9 5+3.55+3.5 15=97.5 15=97.5 100 100第97页，共105页，编辑于2022年，星期六5.5.增加一个新约束的分析增加一个新约束的分析增加一个新约束的分析增加一个新约束的分析当出现新的资源限制时，当出现新的资源限制时，模型要加入新约束，可在原最模型要加入新约束，可在原最优解的基础上进行分析：优解的基础上进行分析：最优解满足新约束，最优解满足新约束，最优解不变；最优解不变；最优解不满足新约束，最优解不满足新约束，应继续寻
48、找新的最优解；应继续寻找新的最优解；无论加入什么类型约束，无论加入什么类型约束，目标函数值都不会改善。目标函数值都不会改善。第98页，共105页，编辑于2022年，星期六例例例例:如果家具厂每月可用的木材只有如果家具厂每月可用的木材只有1010立方米，生产一个桌立方米，生产一个桌子需木材子需木材0.40.4立方米，椅子需立方米，椅子需0.30.3立方米。问应该如何生产立方米。问应该如何生产？解：解：加入新约束为：加入新约束为：4 4x x1 1+3+3x x2 2 100 100，引引入入松松弛弛变变量量 x x5 5 并并令令其其入入基基，加加入入原原最最优优表表后后得得到到的的不不是是标标
49、准准单单纯纯形形表表，需需要要通通过过矩矩阵阵的的初初等等变变换换将将其其化为标准表，再进一步用对偶单纯形法求解。化为标准表，再进一步用对偶单纯形法求解。第99页，共105页，编辑于2022年，星期六第100页，共105页，编辑于2022年，星期六系数变化对解的结果的影响C的变化只影响检验数（对偶问题的解），不影响原问题的基本解；b的变化只影响原问题的基本解，不影响检验数（对偶问题的解）；A中系数的变化可能既影响原问题的基本解，又影响对偶问题的解。灵敏度分析时，要弄清楚：1）系数在什么范围内变化时，最优解（基）不变；2）若系数的变化使最优解发生变化，如何最简便地求得新最优解。第101页，共10
50、5页，编辑于2022年，星期六系数变化的灵敏度分析系数变化的灵敏度分析1、价值系数的变化范围的确定1）非基变量的系数2）基变量的系数2、右手项（资源总量）的变化范围的确定3、技术系数的变化对最优解的影响1）基变量系数变化了2）非基变量系数的变化范围第102页，共105页，编辑于2022年，星期六决策变量增减的灵敏度分析 增加产品新品种相当于增加一列1、解决是否值得生产的问题2、解决若值得生产，生产计划应如何调整第一种问题可以直接使用机会成本分析法第二种问题需先计算新的一列当前值，再 继续求解。第103页，共105页，编辑于2022年，星期六约束条件增减的灵敏度分析约束条件增减的灵敏度分析增加约