1、1第二章第二章对偶理论与灵敏度分析对偶理论与灵敏度分析 窗含西岭千秋雪,门泊东吴万里船窗含西岭千秋雪,门泊东吴万里船 对偶是一种普遍现象对偶是一种普遍现象22.1 线性规划问题的对偶问题及其变换线性规划问题的对偶问题及其变换2.1.1 线性规划对偶问题的提出及其经济意义线性规划对偶问题的提出及其经济意义 任何线性规划问题都有其对偶问题任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义对偶问题有其明显的经济含义 假设有商人要向厂方购买资源假设有商人要向厂方购买资源A A和和B B,问他们谈判原料,问他们谈判原料价格的模型是怎样的?价格的模型是怎样的?0,B 1522A 25322.433
2、)(max4321432143214321xxxxxxxxxxxxt sxxxxxf资源资源例例 2.1.13 例例2.1.1设设A A、B B资源的出售价格分别为资源的出售价格分别为 y y1 1 和和 y y2 2显然商人希望总的收购价越小越好显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少工厂希望出售资源后所得不应比生产产品所得少 0,4 423 3 32 2 32 1 121525)(212121212121yyyyyyyyyyyyygMin的所得产品的所得产品的所得产品的所得产品 0,B 1522A 25322.433)(max4321432143214321
3、xxxxxxxxxxxxtsxxxxxf资源资源4 2.1.2 原问题与对偶问题的表达形式原问题与对偶问题的表达形式0XbAXtsCXxf.)(max :原问题原问题0YCYAtsYbyg.)(min :对偶问题对偶问题TmnmTnbbbbcccCyyyYxxxX),(),(),(),(21212121上两式中上两式中mnmmnnaaaaaaaaaA2122221112115 2.1.2原问题与对偶问题的表达形式原问题与对偶问题的表达形式0,.)(min21221122222112112211112211mnmmnnnmmmmmmyyycyayayacyayayacyayayatsybybyb
4、yg把对偶问题展开把对偶问题展开0YCYAYbYTTTTTtsg.)(min :对偶问题习惯写为6 一、一、标准标准(max,(max,)型的对偶变换型的对偶变换 目标函数由目标函数由 max max 型变为型变为 min min 型型 对应原问题每个约束行有一个对偶变量对应原问题每个约束行有一个对偶变量 y yi i,i i=1,2,=1,2,m m 对偶问题约束为对偶问题约束为 型,有型,有 n n 行行 原问题的价值系数原问题的价值系数 C C 变换为对偶问题的右端项变换为对偶问题的右端项 原问题的右端项原问题的右端项 b b 变换为对偶问题的价值系数变换为对偶问题的价值系数 原问题的技
5、术系数矩阵原问题的技术系数矩阵 A A 转置后成为对偶问题的技术转置后成为对偶问题的技术系数矩阵系数矩阵 原问题与对偶问题互为对偶原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义对偶问题还有很多理论和实际应用的意义 二、二、非非标准标准型的对偶变换型的对偶变换0,510342023.54)(max 2.1.2 1221212121xxxxxxxxtsxxxf不限不限原线性规划问题原线性规划问题例例 0,551033420223.554)(max)(max,221221221221221221xxxxxxxxxxxxxxxtsx
6、xxxf型标准问题型标准问题化为化为0,532532443.551020)(min 43214321432143214321wwwwwwwwwwwwwwwwtswwwwwh则则应用标准型对偶变换规应用标准型对偶变换规不限经整理得令yyyyyyyyytsyyyygwwywywy,.)(min:,8三、三、原问题和其线性规划对偶问题的相互关系表原问题和其线性规划对偶问题的相互关系表 约束条件的类型与非负条件对偶约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的对偶变换是一一对应的(max,)(min,)技术系数矩阵技
7、术系数矩阵 A 技术系数矩阵技术系数矩阵 AT 价值系数价值系数 C 右端项右端项 b 右端项右端项 b 价值系数价值系数 C 第第 i 行约束条件为行约束条件为 型型 决策决策变量变量 yi 0 第第 i 行约束条件为行约束条件为 型型 决策决策变量变量 yi 0 第第 i 行约束条件为行约束条件为=型型 决策决策变量变量 yi 不限不限 决策变量决策变量 xj 0 第第 j 行约束条件为行约束条件为 型型 决策变量决策变量 xj 0 第第 j 行约束条件为行约束条件为 型型 决策变量决策变量 xj 不限不限 第第 j 行约束条件为行约束条件为=型型 9在使用在使用上上表规则写出某一线性规划
8、的对偶规划时,要注意如下表规则写出某一线性规划的对偶规划时,要注意如下一些问题:一些问题:1)要看清原问题目标函数是)要看清原问题目标函数是max问题还是问题还是min问题。如果原问问题。如果原问题目标函数是题目标函数是max,在写其对偶问题时,应该利用,在写其对偶问题时,应该利用上上表左侧规表左侧规则向右侧规则变换;而如果原问题目标函数是则向右侧规则变换;而如果原问题目标函数是min,在写其对,在写其对偶问题时,则应该利用偶问题时,则应该利用上上表右侧规则向左侧规则变换;表右侧规则向左侧规则变换;2)如果原问题的约束条件不符合)如果原问题的约束条件不符合上上表的规范要求,应该利用表的规范要求
9、,应该利用等价变换规则,将约束条件变换成符合等价变换规则,将约束条件变换成符合上上表的规范要求。表的规范要求。例例 2.1.4 写出如下线性规划的对偶规划写出如下线性规划的对偶规划正负不限,0,010543215653 12 425324.4643)(inf43243214321143214321xxxxxxxxxxxxxxxxtsxxxxxM1)第一)第一、二、二约束方程可用两个约约束方程可用两个约束方程等价表示;束方程等价表示;2)没有给出没有给出x1 变量的约束条件,但变量的约束条件,但根据第二约束方程可推得,根据第二约束方程可推得,x1 变量变量的约束条件为的约束条件为x10。因此,上
10、述线性规划等价于如下线因此,上述线性规划等价于如下线性规划:性规划:10正负不限,0,0,010543215653 12 ,42532425324.4643)(inf43214321432111432143214321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxM正负不限,0,0,0,0,045633645224344323.10151242525)(654321652165216521654321654321yyyyyyyyyyyyyyyyyyyyyyyytsyyyyyyyMaxg112.2 2.2 线性规划的对偶定理线性规划的对偶定理1 1、弱弱对偶定理对偶定理定理定理1 1
11、 对偶问题对偶问题(min)(min)的任何可行解的任何可行解Y Y0 0,其目标函数值总其目标函数值总是不小于原问题是不小于原问题(max)(max)任何可行解任何可行解X X0 0的目标函数值的目标函数值 为了便于讨论,下面不妨总是假设为了便于讨论,下面不妨总是假设0XbAXCX.)(max :tsxf原问题0YCYAtsYbyg.)(min :对偶问题对偶问题(2)(1),:0000CAYbAXYX故有题的可行解分别为原问题和对偶问由于证将将(1)式左乘式左乘Y0,将,将(2)式右乘式右乘X0,立刻可得,立刻可得Y0b Y0AX0 CX0,证毕。,证毕。12 弱弱对偶定理推论对偶定理推论
12、 maxmax问题的任何可行解目标函数值是其对偶问题的任何可行解目标函数值是其对偶minmin问题目问题目标函数值的下限;标函数值的下限;minmin问题的任何可行解目标函数值问题的任何可行解目标函数值是其对偶是其对偶maxmax问题目标函数值的上限问题目标函数值的上限 如果原如果原max(min)max(min)问题为无界解,则其对偶问题为无界解,则其对偶 min(max)min(max)问题无可行解问题无可行解 如果原如果原max(min)max(min)问题有可行解,其对偶问题有可行解,其对偶 min(max)min(max)问问题无可行解,则原问题为无界解题无可行解,则原问题为无界解
13、注注:存在原问题和对偶问题同时无可行解的情况:存在原问题和对偶问题同时无可行解的情况13例例 2.2.1 设有如下线性规划原问题设有如下线性规划原问题 0,70276503232032.252)(max43214321432143214321xxxxxxxxxxxxxxxxt sxxxxxf 0,223523272163.705020)(min321321321321321321yyyyyyyyyyyyyyytsyyyyg令令 X0=(x01,x02,x03,x04)T=(1,1,1,1)T,Y0=(y01,y02,y03)=(1,1,1),则显然),则显然X0和和Y0分别为原分别为原问题和对
14、偶问题的可行解。它们对应的目标函数值分别为问题和对偶问题的可行解。它们对应的目标函数值分别为f(X0)=C X0=10,即其对偶问题目标函数值的下限不会小于,即其对偶问题目标函数值的下限不会小于10;g(Y0)=Y0 b=140,即其原问题目标函数值的上限不会大于,即其原问题目标函数值的上限不会大于140;这一结果验证了弱对偶定理这一结果验证了弱对偶定理C X0 Y0 b。14例例 2.2.2 设有如下线性规划原问题设有如下线性规划原问题0,501002.)(max21212121xxxxxxtsxxxf 0,112.50100)(min21212121yyyyyytsyyyg令令 X0=(x
15、01,x02)T=(1,1)T,则显然,则显然X0为原问题的可行解,为原问题的可行解,即线性规划原问题有可行解;但将对偶问题的两个约束方即线性规划原问题有可行解;但将对偶问题的两个约束方程相加后可得程相加后可得 -y1 2,这显然与非负约束矛盾,所以对偶,这显然与非负约束矛盾,所以对偶问题无可行解。根据弱对偶定理推论问题无可行解。根据弱对偶定理推论3可以判断原问题为无可以判断原问题为无界解。事实上,利用单纯形法求解原问题(见第一章界解。事实上,利用单纯形法求解原问题(见第一章例例1.10)可得,原问题的确为无界解,根据弱对偶定理推论)可得,原问题的确为无界解,根据弱对偶定理推论2可以判断对偶问
16、题无可行解可以判断对偶问题无可行解152 2、最优解判别、最优解判别定理定理定理定理2 2 若原问题的某个可行解若原问题的某个可行解X X0 0的目标函数值与对偶问题某个的目标函数值与对偶问题某个可行解可行解Y Y0 0的目标函数值相等,则的目标函数值相等,则X X0 0,Y Y0 0分别是相应问题的分别是相应问题的最优解最优解 证证:由弱对偶定理推论由弱对偶定理推论1,有有 CX0=Y0b CX,即即X0是原问题的最优解;是原问题的最优解;另有另有Y0b=CX0 Yb,即,即Y0是对偶问题的最优解;证毕。是对偶问题的最优解;证毕。3 3、主对偶主对偶定理定理定理定理3 3 如果原问题和对偶问
17、题都有可行解,则它们都有最优如果原问题和对偶问题都有可行解,则它们都有最优解,且它们的最优解的目标函数值相等。解,且它们的最优解的目标函数值相等。证证:由弱对偶定理推论:由弱对偶定理推论1 1可知,原问题和对偶问题的目标函可知,原问题和对偶问题的目标函数有界,故一定存在最优解。数有界,故一定存在最优解。现证明定理的后一句话。现证明定理的后一句话。16 主对偶主对偶定理的证明定理的证明 证证:现证明定理的后一句话,采用反证法。:现证明定理的后一句话,采用反证法。设设 X X0 0,Y Y0 0分别为原问题和对偶问题的最优解,且分别为原问题和对偶问题的最优解,且 Y Y0 0b CXb CX0 0
18、 根据最优性检验条件,非基变量的检验数满足根据最优性检验条件,非基变量的检验数满足C CN N C CB BB B 1 1N N 0 0,而,而基变量的检验数为基变量的检验数为0 0,可写成,可写成C CB B C CB BB B 1 1B B=0=0,所以,包括基变量在内的所有变量的,所以,包括基变量在内的所有变量的检验数满足检验数满足 C C C CB BB B 1 1A A 0 0。令令 Y=Y=C CB BB B 1 1,则有,则有 Y Y A A C C。另外,对应于松驰变量,有另外,对应于松驰变量,有 C CB BB B 1 1I I 0 0,即,即 Y=Y=C CB BB B 1
19、 1 0 0,故,故 Y Y为对偶问题的可行解。为对偶问题的可行解。对偶问题可行解对偶问题可行解Y的目标函数值为的目标函数值为 g(Y)=Yb=CBB 1bY0b 原问题最优解原问题最优解X0的目标函数值为的目标函数值为 f(X0)=CX0=CBB 1b=Yb 所以有所以有CX0Y0b,与假设矛盾。故得证与假设矛盾。故得证,该定理的证明告诉我们一个非常重要的概念:该定理的证明告诉我们一个非常重要的概念:对偶变量的最优对偶变量的最优解等于原问题松弛变量的机会成本解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的即对偶变量的最优解是原问题资源的影子价格影子价格173 3、互补松弛、互补
20、松弛定理定理定理定理4 4 设设X X0 0,Y Y0 0分别是原问题和对偶问题的可行解,分别是原问题和对偶问题的可行解,U U0 0为原问题为原问题的松弛变量的值、的松弛变量的值、V V0 0为对偶问题剩余变量的值。为对偶问题剩余变量的值。X X0 0,Y Y0 0分别分别是原问题和对偶问题最优解的充分必要条件是是原问题和对偶问题最优解的充分必要条件是 Y Y0 0 U U0 0+V V0 0 X X0 0=0 0证证:由定理所设,可知有:由定理所设,可知有 A XA X0 0+U+U0 0=b Xb X0 0,U,U0 0 0 0 (1)(1)Y Y0 0 A A V V0 0 =C YC
21、 Y0 0,V,V0 0 0 0 (2)(2)分别以分别以Y Y0 0左乘左乘(1)(1)式,以式,以X X0 0右乘右乘(2)(2)式后,两式相减,得式后,两式相减,得 Y Y0 0 U U0 0+V V0 0 X X0 0 =Y=Y0 0 b b C XC X0 0若若 Y Y0 0 U U0 0+V V0 0 X X0 0 =0 0,根据最优解判别定理,根据最优解判别定理,X X0 0,Y Y0 0分别是原问分别是原问题和对偶问题最优解。反之亦然。题和对偶问题最优解。反之亦然。证毕证毕。18根据互补松弛定理和决策变量满足非负条件可知,在最根据互补松弛定理和决策变量满足非负条件可知,在最优
22、解时,优解时,Y0 U0 和和 V0 X0同时等于同时等于0,所以有,所以有3 3、互补松弛、互补松弛定理定理miuynjxviijj,2,10,2,100000上面公式上面公式称为互补松弛条件。该条件表明,在最解条件下,如果称为互补松弛条件。该条件表明,在最解条件下,如果知道知道v0j与与x0j(或(或u0j与与y0j)中的任意一个值为非)中的任意一个值为非0时,则可推得另时,则可推得另一个必然为一个必然为0。利用这个条件,有时可大大地简化计算过程。利用这个条件,有时可大大地简化计算过程。例例 2.2.4 利用互补松弛定理求解如下线性规划问题利用互补松弛定理求解如下线性规划问题 0,2023
23、220322 .432)(4321432143214321xxxxxxxxxxxxt sxxxxxfMax0,2023220322 .432)(211432124321143214321uuuxxxxuxxxxuxxxxt sxxxxxfMax19其其对偶问题引入剩余变量对偶问题引入剩余变量v1,v2,v3和和v4后,可得到如下线性规划后,可得到如下线性规划0,423332 22 12 .2020)(43212142132122112121vvvvyyvyyvyyvyyvyytsyyygMin利用图解法可求得其最优解为:y01=1.2,y02=0.2,Min g(Y0)=28。利用得到的对偶规
24、划最优解和互补松弛定理,可求得原线性规划的最优解。具体步骤如下:1、因为y01=1.20,根据互补松弛定理可得u01=0;2、因为y02=0.20,根据互补松弛定理可得u02=0;3、因为y01+2y02=1.61,根据对偶规划(2.13)的第1个约束方程 可得v010,然后根据互补松弛定理可得x01=0;4、因为2y01+y02=2.62,根据对偶规划(2.13)的第2个约束方程 可得v020,然后根据互补松弛定理可得x02=0;5、根据上述4个步骤的结论及原线性规划的约束方程可得如下线性方程组 2023203204030403xxxx解得,x03=x04=4。X0=(x01,x02,x03
25、,x04)T=(0,0,4,4)T20 2.3 2.3原问题检验数与对偶问题的解原问题检验数与对偶问题的解 在主对偶定理的证明中我们有:对偶在主对偶定理的证明中我们有:对偶(min(min型型)变量的最优解变量的最优解等于原问题松弛变量的机会成本,或者说原问题松弛变量检等于原问题松弛变量的机会成本,或者说原问题松弛变量检验数的绝对值验数的绝对值 可以证明,对偶问题最优解的剩余变量解值等于原问题对可以证明,对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值应变量的检验数的绝对值 由于原问题和对偶问题是相互对偶的,因此对偶问题的检验由于原问题和对偶问题是相互对偶的,因此对偶问题的检验数
26、与原问题的解也有类似上述关系。数与原问题的解也有类似上述关系。更一般地讲,可以证明,不管原问题是否标准,在最优解的更一般地讲,可以证明,不管原问题是否标准,在最优解的单纯型表中,都有原问题虚变量单纯型表中,都有原问题虚变量(松弛、剩余或人工变量松弛、剩余或人工变量)的的机会成本的绝对值等于其对偶问题实变量机会成本的绝对值等于其对偶问题实变量(对偶变量对偶变量)的最优的最优解的绝对值,原问题实变量解的绝对值,原问题实变量(决策变量决策变量)的检验数的绝对值等的检验数的绝对值等于其对偶问题虚变量于其对偶问题虚变量(松弛或剩余变量松弛或剩余变量)的最优解的绝对值。的最优解的绝对值。因此,原问题或对偶
27、问题只需求解其中之一就可以了。因此,原问题或对偶问题只需求解其中之一就可以了。21 例例2.2.3 原问题检验数与对偶问题的解原问题检验数与对偶问题的解不限不限原问题原问题321321321321321,0,101632182.635)(max:xxxxxxxxxxxxtsxxxxf不限不限对偶问题对偶问题321321321321321,0,633252.101618)(min:yyyyyyyyyyyytsyyyyg22Cj 536-600 MCBXBbx1x2x3x3x4x5x60 x418121 11000 x51621(3)3010 Mx610111 1001OBJ=10M M M MM
28、00 Mcj-zj5+M3+M6+M-6-M0000 x438/31/35/3001 1/306x316/32/31/31 101/30 Mx614/31/3(2/3)000 1/31OBJ=32-14M/3 4-M/32-2M/36 602+M/3 Mcj-zj1+M/3 1+2M/3000-2-M/300 x41 1/200011/2 5/26x33(1/2)01 101/2 3/23x271/21000 1/23/2OBJ=399/236 603/23/2cj-zj1/20000 3/2-M-3/20 x44001 111 35x16102 201 13x2401 1(1)0 12OBJ
29、=42537 702 1cj-zj00 110 2-M+10 x48010010 15x11412000 13 6x3401 110 12OBJ=46546 6013cj-zj0 1000 1-M 3对偶问题最优解:对偶问题最优解:y4=0y5=1y6=0y1=0y2=1y3=3原问题最优解:原问题最优解:x1=14,x2=0,x3=-4,x4=8,x5=0,x6=0,OBJ=4623Cj 18161000MCBYBby1y2y3y4y5y60y4-5-1-2-11000y5-3-2-1-1010My6613(1)001OBJ=6MM3MM00Mcj-zj18-M16-3M10-M0000y4
30、10(1)01010y53-12001110y36131001OBJ=601030100010cj-zj8-14000M-1016y210101010y51-300-21-110y33101-30-2OBJ=46101610-140-4cj-zj800140M 4原问题最优解:原问题最优解:x4=8x5=0 x6=0 x1=14x2=0 x3=4对偶问题最优解:对偶问题最优解:y1=0,y2=1,y3=3,y4=0,y5=1,y6=0,OBJ=46242.42.4对偶单纯型法对偶单纯型法2.4.1 2.4.1 基本思路基本思路1 1、原单纯型迭代要求每步都是基础可行解、原单纯型迭代要求每步都是
31、基础可行解2 2、达到最优解时,检验数、达到最优解时,检验数 c cj jz zj j 0(max)0(max)3 3、对于、对于(min,(min,)型所加的剩余变量无法构成初始基础可行解型所加的剩余变量无法构成初始基础可行解4 4、因此通过加人工变量来解决、因此通过加人工变量来解决,但大但大M M法和二阶段法较繁法和二阶段法较繁5、对偶单纯形法基本思路:对偶单纯形法基本思路:从原问题的某一个满足最优检验条件的基本解出发,判断从原问题的某一个满足最优检验条件的基本解出发,判断该基本解是否满足可行性条件,若是,则已得最优解,若该基本解是否满足可行性条件,若是,则已得最优解,若否,则通过迭代得到
32、另一个满足最优检验条件且更接近可否,则通过迭代得到另一个满足最优检验条件且更接近可行解的基本解。如此循环,直到找到满足最优检验条件且行解的基本解。如此循环,直到找到满足最优检验条件且可行解的基本解(即最优解)为止。可行解的基本解(即最优解)为止。25 2.4.2对偶单纯形法的步骤对偶单纯形法的步骤1、求一个满足最优检验条件的初始、求一个满足最优检验条件的初始基础基础解,列出初始单纯形表;解,列出初始单纯形表;2、可行性检验、可行性检验 若所有的右端系数均大于等于若所有的右端系数均大于等于0,即,即 bi 0,i=1,2,.,m则已得最优解,停止运算。否则,转步骤则已得最优解,停止运算。否则,转
33、步骤3;3、求另一个满足最优检验条件且更接近可行解的、求另一个满足最优检验条件且更接近可行解的基础基础解解1)确定出变量)确定出变量 找非可行解中分量最小者,即找非可行解中分量最小者,即 min bi|bi 0,不会破坏最优解,不会破坏最优解 若若 aij 0,必须保证,必须保证 cj zj 041ijijjijjiijiijjjNjjiijjNjijijmkkkjjjaqzcqizcqaqazczcqazzaaqazx 所以所以型型行约束为行约束为对于第对于第即即则有则有变动变动设设则有则有为非基变量为非基变量设设 ,0 ,0,0001042x1,x3为非基变量,q1=0,q2=0.25,q
34、3=1,故有 333123211311175.275.2125.325.325.075.21125.025.313 aaaaaa x2,x4为基变量,x5=100,b1有剩余,故有5.020010011001001412aa x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/411300 4.2555.75400.251cj-zj-3.250-2.7500-0.25-143 2.5.5 新增决策变量的分析新增决策变量的分析 例例2.4.2中,若新增产品中,若新增产品 x8,问是
35、否生产?,问是否生产?已知已知 c8=9,a18=5,a28=4,a38=3 计算计算 x8 的检验数可知生产是否有利的检验数可知生产是否有利05)1325.0405(9318888iiiaqczc结论:生产x8有利。将B1P8加入最优单纯型表中,以x8为入变量进行迭代44 2.5.6 新增约束条件的分析新增约束条件的分析1、将最优解代入新的约束条件,若满足,则最优解不变、将最优解代入新的约束条件,若满足,则最优解不变2、若不满足,则当前最优解要发生变化;将新增约束条、若不满足,则当前最优解要发生变化;将新增约束条件加入最优单纯型表,并变换为标准型件加入最优单纯型表,并变换为标准型3、利用对偶
36、单纯型法继续迭代、利用对偶单纯型法继续迭代 为什么可以利用对偶单纯型法为什么可以利用对偶单纯型法x1x2x3x4x5x6x7x8CBXBb153400000 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4(1)11/400-3/4100 x865012330001例2.4.2 第2步45x1x2x3x4x5x6x7x8CBXBb153400000 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4(1)11/400-3/4100 x8650123300010 x51001/40-13/4011/4-
37、104x420020-2(1)01-105x2100-3/4111/400-3/4100 x84505/20-5/2301.5-210 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4111/400-3/4100 x8-150-7/207/200-1.51146x1x2x3x4x5x6x7x8CBXBb153400000 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4111/400-3/4100 x8-150-7/207/200(-1.5)111300 4.2555.75400.2510cj-zj
38、-3.250-2.7500-0.25-100 x575-0.330-2.67010-0.83 0.174x4100-0.3300.33100-0.33 0.675x21751110000.5-0.50 x61002.330-2.33001-0.67-0.671275 3.6756.334001.170.17cj-zj-2.670-3.33000-1.17-0.17注意:最优解的目标函数减少了25个单位47 2.5.7 灵敏度分析举例灵敏度分析举例产量产量 组别组别单位售价单位售价 品种品种I II III IV V(元元)A 产品数量产品数量3244010B 产品数量产品数量612145C 产
39、品数量产品数量265184耗费耗费 组别组别 资源资源I II III IV V资源限制资源限制工人工时工人工时(小时小时)0461280小时小时/天天机器工时机器工时(小时小时)1121150小时小时/天天每组生产费用每组生产费用(元元)481930407例例2.4.3 某工厂生产三种产品某工厂生产三种产品 A,B,C,有五种生产组合方案。,有五种生产组合方案。下两表给出有关数据。规定每天供应下两表给出有关数据。规定每天供应 A产品至少产品至少110 个,求收个,求收益最大的生产方案。益最大的生产方案。48 例例2.13解解:设设xj为已选定各种组合方案的组数为已选定各种组合方案的组数(j=
40、1,2,5),x6为为A产品产品的剩余变量,的剩余变量,x7,x8分别为工人工时和机器工时的松弛变量分别为工人工时和机器工时的松弛变量。8,2,1,0502802641104423.455403020)(max854321754326432154321jxxxxxxxxxxxxxxxxxtsxxxxxxfjx1x2x3x4x5x6x7x8CBXBb20304054500020 x126100.410-0.2-0.20.430 x216011.40.50-0.20.3-0.645x58000.2-0.510.4-0.11.2136020305912.54580.544cj-zj00-19-7.5
41、0-8-0.5-4449 例例2.13 最优解的最优解的B1是什么是什么 产品产品A的影子价为多少的影子价为多少 第第II组方案的生产费用提高组方案的生产费用提高2元,是否要调整生产组别元,是否要调整生产组别 若工人加班费为若工人加班费为1元元/小时,是否要采取加班措施小时,是否要采取加班措施 若通过租借机器增加工时,租费的上限应为多少若通过租借机器增加工时,租费的上限应为多少 A产品的订购合同是否有利,产品的订购合同是否有利,A产品的变动范围多大产品的变动范围多大 若要选用第若要选用第IV组方案,该组的生产费用应降低多少组方案,该组的生产费用应降低多少 若工人加班费为若工人加班费为0.3元元
42、/小时,最多允许加班时间多少小时,最多允许加班时间多少 若机器租费低于若机器租费低于44元元/小时,问租几部机器才合适小时,问租几部机器才合适(每天每天8小时计小时计)若第若第III组方案使机器工时减少组方案使机器工时减少0.5小时,能否被选入小时,能否被选入502.5.8 其他类型线性规划问题的灵敏度分析其他类型线性规划问题的灵敏度分析 目标函数为目标函数为min型型 当当 xj 不在基中:不在基中:jjjczc)(当 xj 在基中:0min0maxkjkjjjjkkjkjjjjaazccaazc 当第 i 个约束条件为 型 由于xn+i 为剩余变量,-Pn+i才代表B-1的第 i 列,故右端项 bi 的允许变化范围为0min0max,inkinkkkiinkinkkkaabbaab512.5.8 其他类型线性规划问题的灵敏度分析其他类型线性规划问题的灵敏度分析 当第当第 i 个约束条件为个约束条件为 型,其右端项型,其右端项 bi 的边际值为的边际值为 qi=-zn+i 无论目标函数为无论目标函数为 max 型或型或 min 型,若型,若 xj 为非基变量,为非基变量,则则 aij 的变化范围为的变化范围为 0,-0,ijjijjijijjijijjqzcqzcaqzcaqzc或或55