《对偶理论和灵敏度分析课件》由会员分享,可在线阅读,更多相关《对偶理论和灵敏度分析课件(128页珍藏版)》请在金锄头文库上搜索。
1、福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析一、单纯形法的矩阵描述一、单纯形法的矩阵描述CjC1 C2 Cj. CnCBXBbx1 x2 xj xnxB1xB2xBnb1b2.bna11 a12 a1j a1na21 a22 a2j a2nan1 an2 anj ann检验数检验数 j1对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院设线性规划问题设线性规划问题:目标函数目标函数maxz=CX;约束条件约束条件AXb; Xb; 非负条件非负条件 X0 X02对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院给这线性规划问题的
2、约约束条件加入松给这线性规划问题的约约束条件加入松弛变量以后,得到标准型:弛变量以后,得到标准型: m max z=CX+0Xs;AX+IXX+IXs s=b; X=b; X,X X s s00这里这里I I 是是mmmm单位矩阵。单位矩阵。3对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析初始单纯形表和最终单纯形矩阵表示如下初始单纯形表和最终单纯形矩阵表示如下:CjCN CB 00XSb XN XB XSXS b NBI检验数检验数 jCjCN CB 0CBXBb XN XB XSXBB-1bB-1NBB-1B-1检验数检验数
3、jCN -CB B-1N-CB B-14对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院令非基变量令非基变量=0;由上式得到:;由上式得到:5对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院二、改进单纯形法二、改进单纯形法求解线性规划问题的关键是计算求解线性规划问题的关键是计算以下介绍一种比较简便的计算方法以下介绍一种比较简便的计算方法设设mmmm系数矩阵系数矩阵A A,求其逆矩阵。,求其逆矩阵。6对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院可以先从第可以先从第1列开始列开始以以为主元素为主元素,进行变换进行变换7对偶理论和灵敏度分析福州大学公共管理学院
4、福州大学公共管理学院8对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院然后然后构造含有(含有(1 1)列,而其他列都是)列,而其他列都是单位列的矩阵单位列的矩阵9对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院可得到:可得到:10对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院而后以第而后以第2列的列的为主元素,进行变为主元素,进行变换换11对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院然后然后构造含有(含有(2 2)列,而其他列都是)列,而其他列都是单位列的矩阵单位列的矩阵12对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院可得到
5、可得到13对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院重复以上的步骤,直到获得重复以上的步骤,直到获得14对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院求单纯形表的基矩阵的逆矩阵也可以用求单纯形表的基矩阵的逆矩阵也可以用这方法这方法例:用改进单纯形法求解线性规划问题:例:用改进单纯形法求解线性规划问题:15对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第第1步步:确定初始基,初始基变量:确定初始基,初始基变量;确定换入,确定换入,换出变量。换出变量。(1)确定初始基和初始基变量:)确定初始基和初始基变量:16对偶理论和灵敏度分析福州大学公共管理学院福
6、州大学公共管理学院(2)计算非基变量的检验数,确定换入)计算非基变量的检验数,确定换入变量。变量。17对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院(3)确定换出变量确定换出变量计算:计算:表示选择表示选择0的元素的元素18对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院(4)基变换计算)基变换计算将新的基将新的基单位矩阵。计算:单位矩阵。计算:19对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院(5)计算非基变量的系数矩阵)计算非基变量的系数矩阵20对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院(6)计算)计算RHS21对偶理论和灵敏度分析
7、福州大学公共管理学院福州大学公共管理学院第第1步计算结束后的结果步计算结束后的结果22对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第第2步步重复第重复第1步的计算步骤步的计算步骤从新的基,基变量开始。从新的基,基变量开始。23对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院计算非基变量的检验数,确定换入变计算非基变量的检验数,确定换入变量。量。24对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院(3)确定换出变量确定换出变量计算:计算:表示选择表示选择0的元素的元素25对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院26对偶理论和灵敏度分析福
8、州大学公共管理学院福州大学公共管理学院计算计算RHS27对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第第2步计算结束后的结果步计算结束后的结果28对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第第3步步从新的基,基变量开始从新的基,基变量开始,重复第重复第1步的计算步骤步的计算步骤.29对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院计算非基变量检验数,检查检验数,确计算非基变量检验数,检查检验数,确定换入变量定换入变量30对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院(3)确定换出变量确定换出变量计算:计算:表示选择表示选择0的进行计算
9、的进行计算31对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院新的基新的基32对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院计算计算B逆矩阵逆矩阵33对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院34对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院计算非基变量的检验数计算非基变量的检验数35对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院最优解最优解36对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院目标函数的值目标函数的值37对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析
10、对偶理论和灵敏度分析若若第第一一章章中中例例一一关关于于某某厂厂的的生生产产计计划划问问题题,现现有有另另一一企企业业想想租租赁赁其其设设备备。厂厂方方为为了了在在谈谈判判时时心心中中有有数数,需需掌掌握握设设备备台台时时费费用用的的最最低低价价码码,以以便便衡衡量量对对方方出出价,对出租与否做出抉择。价,对出租与否做出抉择。在在这这个个问问题题上上厂厂长长面面临临着着两两种种选选择择:自自行行生生产产或或出出租设备。首先要弄清两个问题:租设备。首先要弄清两个问题:合理安排生产能取得多大利润合理安排生产能取得多大利润?为保持利润水平不降低,资源转让的最低价格是多少?为保持利润水平不降低,资源转
11、让的最低价格是多少?问题问题的最优解:的最优解:x1=4,x2=2,Z*=14。三、对偶问题的提出三、对偶问题的提出38对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析第二个问题:出让定价第二个问题:出让定价假设出租单位设备台时的租金和出让单位原材料假设出租单位设备台时的租金和出让单位原材料A、B所得利所得利润分别为润分别为y1、y2、y3原本用于生产原本用于生产I产品的设备台时,如若出让,不应低于自行生产品的设备台时,如若出让,不应低于自行生产带来的利润,否则宁愿自己生产。于是有产带来的利润,否则宁愿自己生产。于是有y1+4y2
12、2同理,对同理,对产品而言,则有产品而言,则有 2y1+4y33设备台时出让的收益(希望出让的收益最少值)设备台时出让的收益(希望出让的收益最少值)min =8y1+16y2+12y3显然还有显然还有 y1,y2,y3039对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析对偶问题的最优解:对偶问题的最优解:y1=3/2,y2=1/8,y3=0,W*=14两个问题的目标函数值相等,这不是偶然的,上述两个问题两个问题的目标函数值相等,这不是偶然的,上述两个问题实际上是一个问题的两个方面,如果把前者称为线性规划原实际上是一个问题的两个方
13、面,如果把前者称为线性规划原问题,则后者便是它的对偶问题,反之亦然。问题,则后者便是它的对偶问题,反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中,初始基对偶问题的最优解对应于原问题最优单纯型法表中,初始基变量的检验数的负值。变量的检验数的负值。例例1的对偶问题的数学模型的对偶问题的数学模型min =8y1+16y2+12y3 y1+4y2 2 2y1+4y35 y1,y2,y30 S.t.Max Z=2x1+3x2 x1+2x284x116 4x212 x1 , x2 040对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析
14、原问题与对偶问题的表达形式原问题与对偶问题的表达形式41对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析四四线性规划的对偶理论线性规划的对偶理论(一)原问题与对偶问题的关系(一)原问题与对偶问题的关系1 1、标准、标准(max,(max, ) )型的对偶变换型的对偶变换目标函数由目标函数由max型变为型变为min型型对应原问题每个约束行有一个对偶变量对应原问题每个约束行有一个对偶变量yi,i=1,2,m对偶问题约束为对偶问题约束为 型,有型,有n行行原问题的价值系数原问题的价值系数 C 变换为对偶问题的右端项变换为对偶问题的右端项
15、原问题的原问题的右端项右端项 b 变换为对偶问题的变换为对偶问题的价值系数价值系数原问题的技术系数矩阵原问题的技术系数矩阵 A 转置后成为对偶问题的技转置后成为对偶问题的技术系数矩阵术系数矩阵42对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院原问题与对偶问题的关系原问题与对偶问题的关系这两个式这两个式子之间的变换子之间的变换关系称为关系称为“对对对对称形式的对偶称形式的对偶称形式的对偶称形式的对偶关系关系关系关系”。 43对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院例:写出下面线性规划的对偶问题:例:写出下面线性规划的对偶问题:44对偶理论和灵敏度分析福州大学公共
16、管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析2、非非标准标准型的对偶变换型的对偶变换 含等式约束时,将等式约含等式约束时,将等式约 束分解为两个不等式束分解为两个不等式 约束条件。约束条件。 45对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析按对称形式变换关系可写出它的对偶问题,如上所示。按对称形式变换关系可写出它的对偶问题,如上所示。46对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院原问题与对偶问题的关系,归纳如下:(原始对偶表)原问题与对偶问题的关系,归纳如下:(原始对偶表)
17、原问题(或对偶问题)原问题(或对偶问题)对偶问题对偶问题 (或原问题)(或原问题)目标函数目标函数maxz变量变量n个个00无约束无约束目标函数目标函数minw约束条件约束条件n个个约束条件约束条件m个个约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数变量变量m个个00无约束无约束目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项47对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析怎样写出非对称形式的对偶问题?怎样写出非对称形式的对偶问题?把一个等式约束写成两个不等式约束,再根据对称形式的对把一个等式
18、约束写成两个不等式约束,再根据对称形式的对把一个等式约束写成两个不等式约束,再根据对称形式的对把一个等式约束写成两个不等式约束,再根据对称形式的对偶关系定义写出;偶关系定义写出;偶关系定义写出;偶关系定义写出;按照按照按照按照原始原始原始原始- - - -对偶表对偶表对偶表对偶表直接写出直接写出直接写出直接写出 。48对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析例:试述下列线性规划问题分对偶问题例:试述下列线性规划问题分对偶问题minz=2x1+3x2-5x3 +x4 x1+x2-3x3 +x4 5 2x1+2x3-x4 4
19、x2+x3 +x4=6 x10;x2,x3 0; x4 无约束无约束Maxz5y14y26y3y12y22y1y333y12y2y35y1y2y31y10,y20,y3无约束无约束49对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析练习:练习:练习:练习:写出下面线性规划的对偶规划写出下面线性规划的对偶规划50对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院哪一个正确?哪一个正确?前一个。原问题是极小化问题,因此应从原始对偶表的右边往左前一个。原问题是极小化问题,因此应从原始对偶表的右边往左边查!边查!51对偶理论和灵
20、敏度分析福州大学公共管理学院福州大学公共管理学院(二)对偶问题的基本性质(二)对偶问题的基本性质1、对称性:、对称性:对偶问题的对偶是原问题。对偶问题的对偶是原问题。2、弱对偶性、弱对偶性若若一对对称形式的对偶线性规划一对对称形式的对偶线性规划一对对称形式的对偶线性规划一对对称形式的对偶线性规划(L) 和和 (D) 均有可行解,分别为均有可行解,分别为 和和 ,则,则C b。52对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院证明思路:证明思路:弱对偶性推论:弱对偶性推论:极大化问题极大化问题极大化问题极大化问题的任意一个可行解所对应的目标函数值的任意一个可行解所对应的目标函数值的
21、任意一个可行解所对应的目标函数值的任意一个可行解所对应的目标函数值是其是其是其是其对偶问题对偶问题对偶问题对偶问题最优目标函数值的一个最优目标函数值的一个最优目标函数值的一个最优目标函数值的一个下界下界下界下界。极小化。极小化。极小化。极小化问题的任意一个可行解所对应的目标函数值是其对问题的任意一个可行解所对应的目标函数值是其对问题的任意一个可行解所对应的目标函数值是其对问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个偶问题最优目标函数值的一个偶问题最优目标函数值的一个偶问题最优目标函数值的一个上界上界上界上界。由由(L) 左乘左乘 ,得,得 由由(D) 右乘右乘 ,得,
22、得 53对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析如果原如果原max(min)问题为无界解,则其对偶问题为无界解,则其对偶min(max)问题无可行解问题无可行解如果原如果原max(min)问题有可行解,其对偶问题有可行解,其对偶min(max)问问题无可行解,则原问题为无界解题无可行解,则原问题为无界解注注:有可能存在原问题和对偶问题同时无可行解的:有可能存在原问题和对偶问题同时无可行解的情况。情况。3、最优性准则定理最优性准则定理最优性准则定理最优性准则定理 若若若若 、 分别为对称形式对偶线性规划的可行解,分别为对称形
23、式对偶线性规划的可行解,分别为对称形式对偶线性规划的可行解,分别为对称形式对偶线性规划的可行解,且两者目标函数的相应值相等,即且两者目标函数的相应值相等,即且两者目标函数的相应值相等,即且两者目标函数的相应值相等,即C C C C b b b b ,则,则,则,则 , 分别为原始问题和对偶问题的最优解。分别为原始问题和对偶问题的最优解。分别为原始问题和对偶问题的最优解。分别为原始问题和对偶问题的最优解。54对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析证明思路:由弱对偶性和已知条件易证。证明思路:由弱对偶性和已知条件易证。4、主
24、对偶主对偶定理定理如果原问题和对偶问题都有可行解,则它们都有最优如果原问题和对偶问题都有可行解,则它们都有最优解,且它们的最优解的目标函数值相等。解,且它们的最优解的目标函数值相等。证明要点:证明要点:第一部分第一部分第一部分第一部分证明两者均有最优解。证明两者均有最优解。证明两者均有最优解。证明两者均有最优解。由于原始问题和对偶问题由于原始问题和对偶问题均可行均可行均可行均可行,根据弱对偶定理知,根据弱对偶定理知两者两者均有界均有界均有界均有界,于是,于是均有最优解均有最优解均有最优解均有最优解。第第第第二二二二部部部部分分分分证证证证明明明明在在在在达达达达到到到到最最最最优优优优时时时时
25、,两两两两个个个个问问问问题题题题的的的的目目目目标标标标函函函函数值相等。数值相等。数值相等。数值相等。55对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析设设X0 为原问题的最优解,它所对应的基矩阵是为原问题的最优解,它所对应的基矩阵是B,X0=B 1b,则其检验数满足,则其检验数满足C CBB 1A 0。令令Y0=CBB 1,则有,则有Y0A C ;而对原问题松弛变量;而对原问题松弛变量的检验数有的检验数有0 CBB 1I 0,即,即Y0 0 。显然显然Y0为对偶问题的可行解。因此有对偶问题目标为对偶问题的可行解。因此有对偶
26、问题目标函数值,函数值,g(Y0)=Y0b=CBB 1b而原问题最优解的目标函数值为而原问题最优解的目标函数值为f(X0)=CX0=CBB 1b故由最优解判别定理可知故由最优解判别定理可知Y0 为对偶问题的最优解。为对偶问题的最优解。证证毕毕。56对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析该定理的证明告诉我们一个非常重要的概念:该定理的证明告诉我们一个非常重要的概念:对偶变量对偶变量的最优解等于原问题松弛变量的机会成本的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的即对偶变量的最优解是原问题资源的影子价格
27、影子价格5、互补松弛互补松弛定理定理若若X0, , Y0分别是原问题和对偶问题的可行解。那么分别是原问题和对偶问题的可行解。那么Y0Xs0和和X0Ys0,当且仅当,当且仅当X0, , Y0为最优解。为最优解。证明:证明:1 1) Y0Xs0和和X0Ys0时,时,X0, , Y0为最优解为最优解2 2) 当当X0, , Y0为最优解时,为最优解时, Y0Xs0,X0Ys057对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析例例4 4:已知线性规划问题:已知线性规划问题试用对偶理论证明上述线性规划问题无最优解。试用对偶理论证明上述线性
28、规划问题无最优解。证明:上述问题的对偶问题是:证明:上述问题的对偶问题是:由约束条件可知对偶问题无可行由约束条件可知对偶问题无可行解,而原问题有可行解。故无解,而原问题有可行解。故无最优解。最优解。58对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析例例5:已知线性规划问题:已知线性规划问题已知其对偶问题的最优解为已知其对偶问题的最优解为y1*=4/5,y2*=3/5,z=5。试用对偶理论找出问题的最优解。试用对偶理论找出问题的最优解。解:解:59对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵
29、敏度分析对偶理论和灵敏度分析这说明这说明yi是右端项是右端项bi每增加一个单位对目标函数每增加一个单位对目标函数Z的贡献。的贡献。对偶变量对偶变量yi在经济上表示原问题第在经济上表示原问题第i种资源的种资源的边际价值边际价值边际价值边际价值。对偶变量的值对偶变量的值yi*所表示的第所表示的第i种资源的边际价值,称为种资源的边际价值,称为影子价值影子价值影子价值影子价值。若原问题的价值系数若原问题的价值系数Cj表示单位产值,则表示单位产值,则yi 称为称为影子价格影子价格影子价格影子价格。若原问题的价值系数若原问题的价值系数Cj表示单位利润,则表示单位利润,则yi 称为称为影子利润影子利润影子利
30、润影子利润。五、对偶问题的经济解释五、对偶问题的经济解释60对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析影影子子价价格格不不是是资资源源的的实实际际价价格格,而而是是资资源源配配置置结结构构的的反反映映,是是在在其其它它数数据据相相对对稳稳定定的的条条件件下下某某种种资资源源增增加加一一个个单单位位导导致致的目标函数值的增量变化。的目标函数值的增量变化。对资源对资源i总存量的评估:总存量的评估:购进购进购进购进 or出让出让出让出让对资源对资源i当前分配量的评估:当前分配量的评估:增加增加增加增加 or减少减少减少减少它它表表
31、明明了了当当前前的的资资源源配配置置状状况况,告告诉诉经经营营者者应应当当优优先先增增加加何种资源,才能获利更多。何种资源,才能获利更多。告诉经营者以怎样的代价去取得紧缺资源。告诉经营者以怎样的代价去取得紧缺资源。提示设备出租或原材料转让的基价。提示设备出租或原材料转让的基价。告诉经营者补给紧缺资源的数量,不要盲目大量补给。告诉经营者补给紧缺资源的数量,不要盲目大量补给。借助影子价格进行内部核算。借助影子价格进行内部核算。特别注意特别注意61对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析六、对偶单纯形法六、对偶单纯形法基本思路基
32、本思路原单纯型迭代要求每步都是基础可行解原单纯型迭代要求每步都是基础可行解达到最优解时,检验数达到最优解时,检验数cjzj 0(max)或或cjzj 0(min)但对于但对于(min, )型所加的剩余变量无法构成初始基础型所加的剩余变量无法构成初始基础可行解,因此通过加人工变量来解决可行解,因此通过加人工变量来解决大大M法和二阶段法较繁法和二阶段法较繁能否从能否从剩余变量构成的初始基础非可行解出发剩余变量构成的初始基础非可行解出发迭代,迭代,但保证但保证检验数满足最优条件,检验数满足最优条件,cjzj 0(max)或或cjzj 0(min),保持对偶问题是基可行解,原问题,保持对偶问题是基可行
33、解,原问题在非可行解的基础上,通过逐步迭代达到基可行解。在非可行解的基础上,通过逐步迭代达到基可行解。62对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析对偶单纯形的计算步骤如下:对偶单纯形的计算步骤如下:1确定出变量确定出变量找非可行解中最小者,即找非可行解中最小者,即minbi |bi0,可可使使用用原原始始单单纯纯形形法法继继续续迭迭代代求求出出新新的最优解。的最优解。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析如从最优表中,如从最优表中,C C3 3是非基变量是非基变量x x3 3 的系数,当的系数,当C C3 3
34、变变化时,只会影响到化时,只会影响到 3 3。75对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院当当cr是是基基变变量量xr的的价价值值系系数数它它的的变变化化将将影影响所有非基变量的检验数响所有非基变量的检验数,为什麽?,为什麽?当当cr变变化化时时,如如能能保保持持,则则当当前前解解仍仍为为最最优优解解,否否则则可可用用单单纯纯形形法法继继续续迭迭代代求求出出新新的最优解的最优解。将将cr看作待定参数,令看作待定参数,令解这解这n-m个不等式,可算出保持最优解不变个不等式,可算出保持最优解不变时时cr的变化范围的变化范围!第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析7
35、6对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院例:当例:当c1发生变化时,仍用发生变化时,仍用c1代表代表x1的价值系的价值系数(看成待定参数),原最优表格即为:数(看成待定参数),原最优表格即为:012-1/31/3cjxjCBXBbc13300X1X2X3X4X5c13X1X21210-14/3-1/3-Z-c1-600c1-31-4/3c11/3c1-1第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析77对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院令所有检验数小于令所有检验数小于0,得不等式组:,得不等式组:解该不等式组得:解该不等式组得:说明当说明当
36、时,最优解不变。时,最优解不变。当当c13时时,有有,可可选选x3或或x5进基进基,x2出基出基.78对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析资源数量资源数量bi变换的分析变换的分析当当bi发生变化时,将影响所有基变量的取值。为什麽?发生变化时,将影响所有基变量的取值。为什麽?因为:因为:因为因为:79对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院保保持持B-1b0,当当前前的的基基仍仍为为最最优优基基,最最优优解解的的结结构构不变(取值改变);不变(取值改变);(B-1b)i0,当当前前基基为为非非可可行行
37、基基,但但是是仍仍保保持持为为对对偶偶可可行行基基,(为为什什麽麽?),可可用用对对偶偶单单纯纯形形法法求求出出新新的的最最优优解;解;如何求出保持最优基不变的如何求出保持最优基不变的bi的范围的范围?把把bi看作待定参数看作待定参数,令令B-1b0,求解该不等式组即可;求解该不等式组即可; 80对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院10-14/3-1/3012-1/31/312X1X22300-1-5/3-1/3-8-Z233000-Z3/19/1111101470139X4X500j23300x1 x2 x3 x4 x5CjbxjXBCB仍然来看上例的最优表格:仍然来
38、看上例的最优表格:81对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院原原b1=3,现现用用待待定定参参数数b1代代替替3,则最优表中的解答列应为:则最优表中的解答列应为:若若b1的的变变化化超超出出这这个个范范围围,则则解解答答列列中中至至少少有有一一个个元元素小于素小于0,可用对偶单纯形法迭代求出新的最优解。,可用对偶单纯形法迭代求出新的最优解。82对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院7.37.3技术系数技术系数技术系数技术系数ij ij的变化的变化的变化的变化 分两种情况来讨论技术系数分两种情况来讨论技术系数ij的变化,下面以具体例子来说明。的变化,下
39、面以具体例子来说明。例例9分分析析在在原原计计划划中中是是否否应应该该安安排排一一种种新新产产品品。以以第第1章章例例1为为例例。设设该该厂厂除除了了生生产产产产品品,外外,现现有有一一种种新新产产品品III。已已知知生生产产产产品品III,每每件件需需消消耗耗原原材材料料A,B各各为为6kg,3kg,使使用用设设备备2台台时时;每每件件可可获获利利5元元。问问该该厂厂是是否否应应生生产产该该产产品品和和生生产多少产多少?83对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院解解分析该问题的步骤是:分析该问题的步骤是:分析该问题的步骤是:分析该问题的步骤是:(1) 设设 生生 产产
40、产产 品品 II为为 x3台台 , 其其 技技 术术 系系 数数 向向 量量P3=(2,6,3)T,然后计算最终表中对应,然后计算最终表中对应x3的检验数的检验数3=c3-CB-13=5-(1.5,0.125,0)(2,6,3)T=1.250说明安排生产产品说明安排生产产品III是有利的。是有利的。84对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院 分析该问题的步骤分析该问题的步骤分析该问题的步骤分析该问题的步骤(2)(2)是:是:是:是: 85对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院表表2-13(a)由于b列的数字没有变化,原问题的解是可行解。但检验数行中还
41、有正检验数,说明目标函数值还可以改善。86对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院分析该问题的步骤分析该问题的步骤分析该问题的步骤分析该问题的步骤(3)(3)是是是是:(3) (3) 将将x x3 3作作为为换换入入变变量量,x x5 5作作为为换换出出变变量量,进进行行迭迭代代,求求出出最最优优解解。计计算算结结果果见见表表2-13(b)2-13(b),这这时时得得最最优优解解:x x1 1=1,x=1,x2 2=1.5=1.5,x x3 3=2=2。总总的的利利润润为为16.516.5元元。比比原原计计划增加了划增加了2.52.5元。元。87对偶理论和灵敏度分析福州大学
42、公共管理学院福州大学公共管理学院表表2-13(b)2-13(b)88对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院例例10 10 分析原计划生产产品的工艺结构发生变化。分析原计划生产产品的工艺结构发生变化。仍以第仍以第1 1章例章例1 1为例,若原计划生产产品为例,若原计划生产产品的工艺结的工艺结构有了改进,这时有关它的技术系数向量变为构有了改进,这时有关它的技术系数向量变为P P1 1=(2,5,2)=(2,5,2)T T,每件利润为,每件利润为4 4元,试分析对原最优计元,试分析对原最优计划有什么影响划有什么影响? ? 89对偶理论和灵敏度分析福州大学公共管理学院福州大学公共
43、管理学院解解解解 把改进工艺结构的产品把改进工艺结构的产品把改进工艺结构的产品把改进工艺结构的产品看作产品看作产品看作产品看作产品,设,设,设,设x x x x1 1 1 1为其产量。为其产量。为其产量。为其产量。于是在原于是在原于是在原于是在原计计计计算的最算的最算的最算的最终终终终表中以表中以表中以表中以x x x x1 1 1 1代替代替代替代替x x x x1 1 1 1,计计计计算算算算对应对应对应对应x x x x1 1 1 1的列向量。的列向量。的列向量。的列向量。同时计算出x1的检验数为c1-CBB-1P1=4-(1.5,0.125,0)(2,5,2)T=0.375将以上计算结
44、果填入最终表x1的列向量位置.得表2-14。90对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院表表表表2-142-14可见x1为换入变量,x1为换出变量,经过迭代。得到表2-1591对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院表表表表2-152-1592对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院表表2-152-15表表明明原原问问题题和和对对偶偶问问题题的的解解都都是是可可行行解解。所所以以表表中中的的结结果果已已是是最最优优解解。即即应应当当生生产产产产品品,3.23.2单位;生产产品单位;生产产品,0.80.8单位。可获利单位。可获利15.2
45、15.2元。元。注意:注意: 若若碰碰到到原原问问题题和和对对偶偶问问题题均均为为非非可可行行解解时时,就就需需要要引进引进人工变量人工变量后重新求解。后重新求解。93对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院例例例例11 11 11 11 假设例假设例假设例假设例10101010的产品的产品的产品的产品的技术系数向量变为的技术系数向量变为的技术系数向量变为的技术系数向量变为P P P P1 1 1 1=(4,5,2)=(4,5,2)=(4,5,2)=(4,5,2)T T T T,而每件获利仍为,而每件获利仍为,而每件获利仍为,而每件获利仍为4 4 4 4元。试问该厂应如何安
46、元。试问该厂应如何安元。试问该厂应如何安元。试问该厂应如何安排最优生产方案排最优生产方案排最优生产方案排最优生产方案? ? ? ?解方法与例方法与例10相同,以相同,以x1代替代替x1,并计算列向量,并计算列向量x1的检验数为c1-CBB-1P1=4-(1.5,0.125,0)(4,5,2)T = -2.625。将这些数字填入最终表1-15的x1列的位置,得到表2-16。94对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院表表表表2-162-16将表2-16的x1变换为基变量,替换x1,得表2-17。95对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院 从表2-17可见
47、原问题和对偶问题都是非可行解。于是引入人工变量x6。因在表2-17中x2所在行,用方程表示时为0x1+x2+0.5x3-0.4x4+0x5= -2.4表表表表2-172-1796对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院引入人工变量引入人工变量x x6 6后,便为后,便为-x-x2 2-0.5x-0.5x3 3+0.4x+0.4x4 4+x+x6 6=2.4=2.4将将x x6 6作作为为基基变变量量代代替替x x2 2,填填入入表表2-172-17,得得到到表表2-182-18。97对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院表表表表2-182-1898对偶
48、理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院这时可按单纯形法求解。这时可按单纯形法求解。X4为换入变量,为换入变量,x6为换出变量。经基变换运算后,得到表为换出变量。经基变换运算后,得到表2-19的上表。的上表。在表在表2-19的上表中,确定的上表中,确定x2为换入变量,为换入变量,x5为换出变量。经基为换出变量。经基变换运算后,得到表变换运算后,得到表2-19的下表。的下表。此表的所有检验数都为非正,已得最优解。最优生产方案为此表的所有检验数都为非正,已得最优解。最优生产方案为生产产品生产产品,0.667单位;产品单位;产品,2.667单位,可得最大利单位,可得最大利润润10.6
49、7元。元。99对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院表表表表2-192-19100对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院系数阵系数阵A A的元素发生变化:的元素发生变化:(1 1)增加)增加1 1个新变量:相当于系数阵个新变量:相当于系数阵A A增加增加1 1列列如如开开发发出出一一种种新新产产品品,已已知知其其有有关关工工艺艺参参数数(或或消消耗耗的的资资源源量量)和和单单位位产产品品利利润润,设设该该种种产产品品的的产产量量为为x xk k,则则c ck k和和P Pk k已已知知,需需要要进进行行“是是否投产否投产”的决策的决策。如例中欲增加产
50、品如例中欲增加产品D,单件利润,单件利润为为c6=5千元,工时消耗与材料千元,工时消耗与材料消耗为消耗为101对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院相相当当于于在在原原始始表表中中增增加加1列列P6,则则在在最最优优表表中中P6应变成应变成相应的检验数:相应的检验数:在此基础上继续迭代,直至求出最优解:在此基础上继续迭代,直至求出最优解:102对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院23CBXBcjxjbjX1X2X3X4X5X6X1X2121/(5/3)2/(1/3)-Z-800-1-5/3-1/32/353X6X23/59/53/50-3/54/5
51、-1/51-1/5111/5-3/52/50-Z-42/5-2/50-3/5-11/5-1/5023300510-14/3-1/35/3012-1/31/31/3q-Zq-800-1-5/3-1/32/3-Z-42/52/50-3/5-11/5-1/5023CBXBcjxjbjX1X2X3X4X5X6X1X2121/(5/3)2/(1/3)-Z-800-1-5/3-1/32/353X6X23/59/53/50-3/54/5-1/51-1/5111/5-3/52/50-Z-42/5-2/50-3/5-11/5-1/5023300510-14/3-1/35/3012-1/31/31/3q-Z103
52、对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院说说明明新新产产品品D应应于于投投产产,新新的的生生产产计计划划为为X*=(0,9/5,0,0,0,3/5)T,即即生生产产B产产品品5/9吨吨,生生产产D产产品品3/5吨吨,两两种种资资源源全全部部用用完完,可可得得到到最大利润为最大利润为8.4(千元千元)(42/5=8.4)。如如果果算算出出的的60,说说明明新新产产品品D不不宜宜投投产产,否则会使产品总利润下降!否则会使产品总利润下降!104对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院(2) (2) 增加增加1 1个约束条件:个约束条件: 相当于系数阵相当于系数
53、阵A A增加增加1 1行行 q 首首先先将将原原最最优优解解代代入入新新增增约约束束检检查查是是否否满满足足?是是,则则说说明明新新增增约约束束不不影影响响最最优解。优解。否则再作下面的讨论:否则再作下面的讨论: 将将新新增增约约束束标标准准化化,添添加加到到原原最最优优表表格中(相当于约束矩阵新增格中(相当于约束矩阵新增1 1行);行); 进进行行规规格格化化处处理理用用矩矩阵阵的的行行变变换换将当前基变成单位阵;将当前基变成单位阵;105对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院 用适当方法(通常是对偶单纯形法)用适当方法(通常是对偶单纯形法)进行迭代求出新的最优解。进行
54、迭代求出新的最优解。 如如 在在 上上 例例 中中 增增 加加 约约 束束 :2x2x1 1+2x+2x2 2+x+x3 35,5,当当前前最最优优解解x x1 1=1,x=1,x2 2=2,x=2,x3 3=0=0不不满满足足该该约约束束,将将约约束束条条件件标标准准化化后后加加入入原原最最优优表表格格,进进行行规规格格化化处处理理,然然后后用用对对偶偶单单纯纯形形法法迭迭代代求求出新的最优解:出新的最优解:106对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院-ZCBXBcjxjb233005X1X2X3X4X5X6230X1X2X612510-14/3-1/30012-1/3
55、1/30221001230X1X2X612-110-14/3-1/30012-1/31/3000-1-20100-1-5/3-1/30比比 值值-15/6-230X1X2X41/313/61/210-5/30-1/32/30113/601/3-1/6001/210-1/2-Z-43/6-43/600-1/60-1/3-5/6-Zq-800-1-5/3-1/30107对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第第8 8节节* * 参数线性规划参数线性规划灵灵敏敏度度分分析析时时,主主要要讨讨论论在在最最优优基基不不变变情情况况下下,确确定定系数系数a aijij,b bi i,
56、c cj j的变化范围。的变化范围。而而参参数数线线性性规规划划是是研研究究这这些些参参数数中中某某一一参参数数连连续续变变化化时时,使使最最优优解解发发生生变变化化的的各各临临界界点点的的值值。即即把把某某一一参参数数作作为为参参变变量量,而而目目标标函函数数在在某某区区间间内内是是这这个个参参变变量量的的线线性性函函数数,含含这这个个参参变变量量的的约约束束条条件件是是线线性性等等式式或或不等式。不等式。因因此此仍仍可可用用单单纯纯形形法法和和对对偶偶单单纯纯形形法法分分析析参参数数线线性性规规划问题。其步骤是:划问题。其步骤是:108对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管
57、理学院(1) (1) 对对含含有有某某参参变变量量t t的的参参数数线线性性规规划划问问题题。先先令令t=0t=0,用单纯形法求出最优解;,用单纯形法求出最优解;(2) (2) 用灵敏度分析法,将参变量用灵敏度分析法,将参变量t t直接反映到最终表中;直接反映到最终表中;(3) (3) 当当参参变变量量t t连连续续变变大大或或变变小小时时,观观察察b b列列和和检检验验数数行行各各数数字字的的变变化化。若若在在b b列列首首先先出出现现某某负负值值时时,则则以以它它对对应应的的变变量量为为换换出出变变量量;于于是是用用对对偶偶单单纯纯形形法法迭迭代代一一步步。若若在在检检验验数数行行首首先先
58、出出现现某某正正值值时时,则则将将它它对对应应的的变量为换入变量;用单纯形法迭代一步;变量为换入变量;用单纯形法迭代一步;109对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院(4) (4) 在在经经迭迭代代一一步步后后得得到到的的新新表表上上,令令参参变变量量t t继继续续变变大大或或变变小小,重重复复步步骤骤(3)(3),直直到到b b列列不不能能再再出出现现负负值,检验数行不能再出现正值为止。值,检验数行不能再出现正值为止。110对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院8.1 8.1 参数参数c c的变化的变化例例12 12 试试分分析析以以下下参参数数线
59、线性性规规划划问问题题。当当参参数数t0t0时的最优解变化。时的最优解变化。111对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院解解解解 将此模型化为标准型将此模型化为标准型将此模型化为标准型将此模型化为标准型112对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院令令令令t=0t=0t=0t=0,用单纯形法求解,用单纯形法求解,用单纯形法求解,用单纯形法求解的结果的结果的结果的结果,见表见表见表见表2-202-202-202-20。113对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院将将将将c c的变化直接反映到最终表的变化直接反映到最终表的变化直接反映
60、到最终表的变化直接反映到最终表2-202-20中,得表中,得表中,得表中,得表2-212-21。计算t的变化范围114对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院当当当当 t t值变化,在值变化,在值变化,在值变化,在4 40 0,即,即,即,即0 0t t9/79/7时,为最优解时,为最优解时,为最优解时,为最优解(2,6,2,0,0)(2,6,2,0,0)T T;当当当当 t t值增大,值增大,值增大,值增大,t t(3/2)/(7/6)=9/7(3/2)/(7/6)=9/7时,时,时,时,在检验数行在检验数行在检验数行在检验数行首先出现首先出现首先出现首先出现4 40 0
61、;表表表表示还可以继续改进。示还可以继续改进。示还可以继续改进。示还可以继续改进。t=9/7t=9/7为第一临界点。当为第一临界点。当为第一临界点。当为第一临界点。当t t9/79/7时,时,时,时,4 40 0,这,这,这,这时时时时x x4 4作为换入变量。用单纯形法迭代一步,得表作为换入变量。用单纯形法迭代一步,得表作为换入变量。用单纯形法迭代一步,得表作为换入变量。用单纯形法迭代一步,得表2-222-22。 115对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院当当当当t t t t继续增大继续增大继续增大继续增大t(5/2)/(1/2)=5t(5/2)/(1/2)=5t(
62、5/2)/(1/2)=5t(5/2)/(1/2)=5时,时,时,时,在检验数行在检验数行在检验数行在检验数行首先出现首先出现首先出现首先出现5 5 5 50000,在,在,在,在5 5 5 50000,即,即,即,即9/7t59/7t59/7t59/7t5时,得最优解时,得最优解时,得最优解时,得最优解(4,3,0,6,0) (4,3,0,6,0) (4,3,0,6,0) (4,3,0,6,0) T T 。t=5t=5t=5t=5为第二临界点。当为第二临界点。当为第二临界点。当为第二临界点。当t t t t5 5 5 5时,时,时,时,5 5 5 50 0 0 0,这时,这时,这时,这时x x
63、 x x5 5 5 5作为换入变量作为换入变量作为换入变量作为换入变量,用单纯形法迭代一步,得表,用单纯形法迭代一步,得表,用单纯形法迭代一步,得表,用单纯形法迭代一步,得表2-232-232-232-23。t 继续增大时,在检验数行恒有2,30,故当t5时,最优解为(4,0,0,12,6)T。116对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院8.2 8.2 参数参数b b的变化分析的变化分析例例13分分析析以以下下线线性性规规划划问问题题,当当t0时时,其其最最优优解解的的变变化范围。化范围。117对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院解解 将上述模型化
64、为标准型将上述模型化为标准型将上述模型化为标准型将上述模型化为标准型118对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院令令令令t=0t=0,用单纯形法迭代两次,求解,用单纯形法迭代两次,求解,用单纯形法迭代两次,求解,用单纯形法迭代两次,求解的结果的结果的结果的结果,见,见,见,见表表表表2-242-24。119对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院将此计算结果反映到最终表将此计算结果反映到最终表将此计算结果反映到最终表将此计算结果反映到最终表2-242-24,得,得,得,得表表表表2-252-25。120对偶理论和灵敏度分析福州大学公共管理学院福州大学公
65、共管理学院在表在表在表在表2-252-252-252-25中中中中进行分析进行分析进行分析进行分析 ,当,当,当,当t t t t增大至增大至增大至增大至t2t2t2t2时,时,时,时,则则则则b0b0b0b0;即;即;即;即0t20t20t20t2时,最优解为时,最优解为时,最优解为时,最优解为 (2-t.4,0,0)(2-t.4,0,0)T T。当当当当t t2 2时,则时,则时,则时,则b b1 10 0;故将;故将;故将;故将x x1 1作为换出变量,用对偶单纯形法迭代一步,作为换出变量,用对偶单纯形法迭代一步,作为换出变量,用对偶单纯形法迭代一步,作为换出变量,用对偶单纯形法迭代一步
66、,得表得表得表得表2-262-26121对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院结论结论从从表表2-262-26可可见见,当当t t6 6时时,问问题题无无可可行行解解;当当2t62t6时,问题的最优解为时,问题的最优解为(0,6-t,0,-6+3t)T。122对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析.已知线性规划问题已知线性规划问题s.t.用单纯形方法求解得最终单纯形如下表用单纯形方法求解得最终单纯形如下表123对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院124对偶理论和灵敏度分析福州
67、大学公共管理学院福州大学公共管理学院试确定试确定:(1)当目标函数变为当目标函数变为时时,最优解会出最优解会出现什么变化现什么变化?(2)当目标函数变为当目标函数变为时时,在在什么范围内变化什么范围内变化,最优解不变最优解不变?(3)若第若第2个约束条件的右端项增大到个约束条件的右端项增大到32时时,分析最优解分析最优解的变化的变化;(4)若第若第2个约束条件变为个约束条件变为,分析分析在什么范围内变化在什么范围内变化,表中基为最优基表中基为最优基?125对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析解:解:(1)新解)新解(2)时时,最优解不变最优解不变.(3)最优解为最优解为(4)时时,最优解不变最优解不变.126对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院分析下列参数规划问题中当分析下列参数规划问题中当变化时最优解的变化情变化时最优解的变化情况况.1、127对偶理论和灵敏度分析福州大学公共管理学院福州大学公共管理学院解:解:128对偶理论和灵敏度分析