《运筹学灵敏度分析课件》由会员分享，可在线阅读，更多相关《运筹学灵敏度分析课件（66页珍藏版）》请在金锄头文库上搜索。
1、第六节 线性规划应用举例 例1：某工厂生产A,B两种产品，均需经过两道工序， 每种产品需各工序加工的时间及各工序可提供的时间如下表。生产产品B同时生产出副产品C，每生产一吨产品B可同时得到2吨产品C，无需费用。出售一顿A盈利400元，B盈利1000元，C盈利300元，而生产要报废的C每吨损失200元，经预测C最大销量为5吨，列模型决定A,B产量，使工厂总盈利最大。 A B C工时限量一工序二工序 2 3 3 4 12 24盈利损失400 1000 300 -200可控变量：设X1为A产量，X2为B产量，X3为C销售量，X4为C报废量目标为总盈利，约束为资源限制等 maxZ=4X1+10X2+3
2、X3-2X4 2X1+3X212 3X1+4X224 X3+X4=2X2 X35 X1,X2,X3,X40 例2：某工厂生产的一种产品由四个零件一和三个零件二组成，这两种零件要用两种原材料，由于三个车间拥有的设备和工艺不同，每个工班原材料耗用量和零件产量不同，问三个车间应各开多少工班，才能使该产品的配套数达到最大。 分析：可控变量是什么，目标和约束是什么每班用料数（公斤）每班产量（件数）A材料B材料零件一零件二一车间二车间三车间853698768594资源限量300500可控变量：三个车间工班数，目标：产品配套数，约束资源约束 目标为两目标取小，要转化为一个目标时的方法。Z=min( (7x1
3、+6x2+8x3)/4 ,(5x1+9x2+4x3)/3)可令y= min( (7x1+6x2+8x3)/4 ,(5x1+9x2+4x3)/3)则上目标转化为maxZ=y (7x1+6x2+8x3)/4y(5x1+9x2+4x3)/3y maxZ=y (7x1+6x2+8x3)/4y (5x1+9x2+4x3)/3y 8x1+5x2+3x3300 6x1+9x2+8x3500 x1,x2,x3,y0 解 先看有多少种裁料方案，再进行组合和选择。方案： 例3 合理利用线材问题 现要做一百套钢管, 每套要长为2.9m、2.1m和1.5m的钢管各一根。已知原料长7.4m，问应如何下料，使用的原料最省
4、。 设用方案设用方案,分别裁原料分别裁原料钢管钢管x1,x2, ,x8根根, 则：则：Min z= x1+ x2+ x3+x4+ x5+x6+x7+x8 2x1+ x2+x3 + x4 100 2x2+x3+ 3x5 +2x6+ x7 100 x1+ x3 +3x4 +2x6+3x7+4x8 100 x1, x2, x3, x4, x5 ,x6, x7, x8 0 例例4 4 某工厂要用三种原材料某工厂要用三种原材料C,P,HC,P,H混合调配出混合调配出三种不同规格的产品三种不同规格的产品A,B,DA,B,D。已知产品的规格要。已知产品的规格要求、单价和原料的供应量、单价如下表。该厂应求、单
5、价和原料的供应量、单价如下表。该厂应如何安排生产，能使利润最大？如何安排生产，能使利润最大？ 根据产品要求有：根据产品要求有： AC0.5A, AP0.25A BC0.25B, BP0.5B AC+AP+AH=A BC+BP+BH=B根据原料供应量有：根据原料供应量有： AC+BC+DC100 AP+BP+DP100 AH+BH+DH60设设AC,AP,DH分别为分别为x1,x2,x9，有，有Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x10.5(x1+
6、 x2+ x3) x2 0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5(x4+ x5+ x6) x1+ x4+ x7100 x2+ x5+ x8100 x3+ x6+ x960 xj0, j=1,2,3,4,5,6,7,8,9解：记产品解：记产品A,B,DA,B,D中中C,P,HC,P,H的含量分的含量分别为别为AC,AP,AH,BC,BP,BH,DC,DP,DH。 例例5 连续投资问题。某单位有资金连续投资问题。某单位有资金10万元，在今万元，在今后后5年内可考虑下列投资项目，已知：年内可考虑下列投资项目，已知： 项目项目A：从第：从第1到第到第4年每
7、年初可投资，并于次年每年初可投资，并于次年末回收本利年末回收本利115%； 项目项目B：第：第3年初需要投资，到第年初需要投资，到第5年末回收本年末回收本利利125%，但最大投资额不超过，但最大投资额不超过4万元；万元； 项目项目C：第：第2年初需要投资，到第年初需要投资，到第5年末能回收年末能回收本利本利140%，但最大投资额不超过，但最大投资额不超过3万元；万元； 项目项目D：5年内每年初可购买公債，当年末回年内每年初可购买公債，当年末回收本利收本利106%。 问它应该如何安排每年的投资，使到问它应该如何安排每年的投资，使到5年末拥年末拥有的资金最多？有的资金最多？ 年份年份项目项目 一一
8、 二二 三三 四四 五五 A X1AX2AX3AX4A B X3B CX2C D X1DX2DX3DX4DX5D x2A+x2C+x2D=1.06x1D解：每年的投资额解：每年的投资额应不超过手中的资应不超过手中的资金。由于项目金。由于项目D每每年都可投资，且当年都可投资，且当年末就可收回。所年末就可收回。所以该单位每年必然以该单位每年必然把资金全部投出去，把资金全部投出去，即投资额等于手中即投资额等于手中的资金数。的资金数。 设第设第i年投资各项目的资金年投资各项目的资金为为xiA,xib,xiC,xiD 。数学模型为：。数学模型为： x1A+x1D=10x3A+x3B+x3D=1.15x1
9、A+1.06x2Dx4A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D第二章第二章 线性规划的对偶理论线性规划的对偶理论与灵敏度分析与灵敏度分析改进单纯型法对偶问题 对偶理论 目标函数值之间的关系 最优解之间的互补松弛关系 对偶单纯形法对偶的经济解释灵敏度分析DUAL第一节 改进单纯型法 需要求的几个重要指标需要求的几个重要指标 ，不需要完全的矩阵，不需要完全的矩阵变换就可求得。变换就可求得。需要求的：基可行解，需要求的：基可行解，非基变量，非基变量，XBB
10、-1b B-1B-1Pk初始表为单位阵（初始基）确定主元素 -Y=-CBB-1 k 求求，确定换入变确定换入变量量xk ,计算计算B-1Pk ,计计算算，确定主元素确定主元素，对简化单纯型表作对简化单纯型表作旋转变换旋转变换简简化化单单纯纯形形表表Cj CCB XB B-1b X b A B-1b B-1ACCB B-1A Cj CB CS CN1CB XB B-1b XB XS XN1 CS XS b B E N1 CB XB B-1b E B-1 B-1N1 0 CSCB B-1 CN1CB B-1N1初始表初始表以以B为基的为基的单纯形表单纯形表当XS为松弛变量时CS=0,松弛变量检验数
11、为C CB B B B-1-1 ， C CB B B B-1-1称为称为单纯形乘子单纯形乘子单纯形乘子单纯形乘子Cj CB CNCB XB B-1b XB XN b B N B-1b E B-1N 0 CNCB B-1N 最优单纯形表最优单纯形表B-1cB B -1EO 第二节 对偶问题 产品产品资源资源 I II 总量总量原料原料工时工时 2 3 4 6 100 120利润利润 6 4原问题：确定获利最大的生产方案原问题：确定获利最大的生产方案对偶问题：确定资源最低可接受对偶问题：确定资源最低可接受 出让价格出让价格建立两问题的模型，对比其最优解，最优目标函数建立两问题的模型，对比其最优解，
12、最优目标函数值的关系。值的关系。 两规划最优目标函数值相等 为Z=CB B-1b 此时最优解XB= B-1b， Y= CB B-1(为原规划松弛变量在最终表 中的检验数,即单纯形乘子）原始问题max z=C Xs.t.AXbX 0对偶问题min =Ybs.t. YACY 0maxbAC CTATbTminmnmn 1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第三节第三节 对偶的经济解释对偶的经济解释2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，
13、对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的种资源的影子价格（影子价格（Shadow Price）影子价格为当影子价格为当bi有单位增量，有单位增量，若原最终优基不变若原最终优基不变，总收益总收益Z的变化，也可以说的变化，也可以说yi是对第是对第i种资源的一种种资源的一种价格估计，由于影子价格是指资源增加时对最优收价格估计，由于影子价格是指资源增加时对最优收益的贡献，所以又称
14、它为资源的机会成本或者边际益的贡献，所以又称它为资源的机会成本或者边际产出产出当市场价格低于影子价格时，企业应该买进资源用当市场价格低于影子价格时，企业应该买进资源用于扩大生产，高于影子价格时，企业应该将已有资于扩大生产，高于影子价格时，企业应该将已有资源卖掉。源卖掉。影子价格的计算影子价格的计算 例子：两种产品由三种原料混合而成，A包括原料一60%，原料二40%，B包括原料一50%，原料二10%，原料三40%，原料一、二、三限量为11250,4000,6000（吨）.试建立模型，求解。A每吨25美元，B每吨10美元maxZ=25x1+10x20.6x1+0.5x2120000.4x1+0.1
15、x240000.4x26000x1,x20原料原料2的约束的约束原料原料1的约束的约束原料原料3的约束的约束 当市场价格低于影子价格时，企业应该买进资源用于扩大生产，高于影子价格时，企业应该将已有资源卖掉。 一个不起作用约束的影响价格总为0,一个起作用约束的影子价格在资源在一定范围内变化时是不变的。这个变化范围就是关于资源限量bi的灵敏度不起作用的约束是对最优解而言，该约束的松弛变量 的值不为0起作用的约束是是对最优解而言，该约束的松弛变量 的值为0 x2=0x1=0x3=0x4=0OABC不起作用约束不起作用约束,影子价格为影子价格为0起作用约束，起作用约束，影子价格不为影子价格不为0第四节
16、 对偶理论 一、对偶问题的性质1、对偶的对偶就是原始问题对偶的定义对偶的定义max z=CXmax z=CXs.t. AXbs.t. AXb X 0 X 0min=Ybs.t. YACY 0对偶的定义对偶的定义max =-Ybs.t. -YA-CY 0min z=-Cmin z=-C X Xs.t. -AX-bs.t. -AX-b X 0 X 02、其他形式问题的对偶原始问题约束条件的性质，影响对偶问题变量的性质。原始问题变量的性质，影响对偶问题约束条件的性质。max z=Cmax z=C X Xs.t. AXs.t. AX b b X 0 X 0min =Ybs.t. YAC Y 0maxz
17、=Cmaxz=C X Xs.t. AXs.t. AX= =b b X 0 X 0min =Ybs.t. YAC Y :unrmax z=Cmax z=C X Xs.t. AXs.t. AX b b X 0 X 0min =Ybs.t. YAC Y 0原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标目标maxZ目标目标min变量变量（n个）个）00无约束无约束约束约束（n个）个）=约束约束（m个）个）=变量变量（m个）个）00无约束无约束min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3
18、8 x1+3x2-x3 15max =6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10x20x3: unrq原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。二、原始对偶关系1、可行解的目标函数值之间的关系 设XF、YF分别是原始问题和对偶问题的可行解z=C XF YF AX
19、F YF b=2、最优解的目标函数值之间的关系 设Xo、Yo分别是原始问题和对偶问题的最优解 z=C Xo=Yo AXo=Yo b=Ymax z=CXs.t.AX+XS=bX, XS 0min =Ybs.t. YA-YS=CY, YS 0 YSX=0Y XS=0ATY-EYsCT Tmn=nXA EXsb=nmm3、基解与检验数之间的关系 单纯形表和对偶 max z=C Xs.t. AX+XS=b X, XS0min =Yb s.t. YA -YS=C Y, YS0min =Yb s.t. YA C Y0对偶问题max z=C Xs.t. AX b X 0原始问题引进松弛变量引进松弛变量max
20、 z=C Xs.t. AX+XS=b X, XS0min Y=Yb s.t. YA -YS= C Y, YS0令Y =CB B-1则由YS = YA C得YS= CBB-1A C为对偶问题基解 结论：原问题单纯型表的检验数与其对偶问题的基解互为相反数y1. yi . ym ym+1 . ym+j . yn+m x1 . xj . xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0检验数与基解的对应关系检验数与基解的对应关系第五
21、节 对偶单纯形法 把对其对偶问题运用单纯型算法的计算步骤反应在对原问题的求解步骤上面。在原问题初始表检验数0,B-1b为非可行解的时候可用。通常不单独使用，运用与灵敏度分析时候较多。如何从最优单纯形表中读出对偶问题的解（1） x1x2x3x4x5x6x7x5 * 100x6 *0 10x7 *00 1 x1x2x3x4x5x6x7初始单纯形表最优单纯形表 *000 -y4-y5-y6-y7-y1-y2-y3-ATY EYs -CT Tmn=nXA EXsb=nmmMin Z = 2 x1 + 3 x2 + 4 x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1
22、 , x2 , x3 0 标准化：标准化： Max Z = - 2x1 - 3x2 - 4x3 S.t. - x1 - 2x2 - x3 + x4 = - 3 - 2x1 + x2 - 3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0对对偶偶单单纯纯形形法法 cj3 4 0 0 0CB XB b y1 y2 y3 y4 y50 y3 20 y4 30 y5 41 2 1 0 01 - 1 0 1 01 3 0 0 13 4 0 0 04 y2 1 0 y4 40 y5 1 1/2 1 1/2 0 05/2 0 1/2 1 0-1/2 0 3/2 0 11 0 -2
23、 0 0和和单单纯纯形形法法的的比比较较 进一步理解最优单纯形表中各元素的含义进一步理解最优单纯形表中各元素的含义 考虑问题考虑问题 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0 引入引入 m 个松弛变量后，通过计算得到最优单纯形表。应个松弛变量后，通过计算得到最优单纯形表。应 -1 -1能够找到最优基能够找到最优基 B的逆矩阵的逆矩阵 B ，以及，以及 B
24、N，检验数等。，检验数等。 第六节第六节 灵敏度分析灵敏度分析 A,b,C变化时对最优解的影响，最优解（最优基）不变，A,b,C的变化范围以下作图看看C,b变化对最优解的影响 x2=0x1=0x3=0x4=0OABCC的变化等值线斜率发生变化，旋转 x2=0x1=0x3=0x4=0OABCb的变化约束对应直线的截距变化，平移 思考，A的变化将如何影响最优解。 两类问题：一、已知变化，求新最优解1、增广阵( b, A )的变化。包括改变约束、增减变量，增减约束。主要充分利用原最终表信息得到一新表，在新表基础上选择适当方法变化得新最优解。 比较 原最终表 B-1( b , A ) 新表 B-1(
25、b+b , A+A ) = B-1 ( b+b , P1+P1 ， P2+P2 Pn+Pn）=原最终表(B-1b , B-1P1 , B-1P2 B-1 Pn） 2、C的变化 仅对产生影响产生的新表 可以分为四种情况： 1）已是最优解 2）单纯形法继续求解 3）对偶单纯形法继续求解 4）人工变量法或保持原有最有基方法继续求解二、未知变化，保持原最优基，求变化范围 CjCCB XB B-1b X bA B-1b B-1ACCB B-1A CjCCB XB B-1b X bA B-1b B-1ACCB B-1A 原最终表原最终表新表新表原问题原问题新问题新问题CjCCB XB B-1b X b+b
26、A+A B-1b+ B-1b B-1 A+ B-1 A CCB B-1A CjCCB XB B-1b X b+bP1+P1 . Pn+Pn B-1b+ B-1bB-1P1 + B-1 P1 . B-1Pn + B-1 PnCCB B-1A 价值系数价值系数C发生变化：发生变化： 一、保持原最优解，求变化范围一、保持原最优解，求变化范围1、若、若 ck 是非基变量的系数：是非基变量的系数： 设设 ck 变化为变化为 ck + ck 只要只要 k 0 ， 则最优解不变；否则，将最优单纯则最优解不变；否则，将最优单纯形表中的检验数形表中的检验数 k 用用 k取代，继续单纯形法的表取代，继续单纯形法的
27、表格计算格计算。 例例: Max Z = - 2x1 - 3x2 - 4x3 S.t. - x1 - 2x2 - x3 + x4 = - 3 - 2x1 + x2 - 3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0 例：最优单纯形表例：最优单纯形表从表中看到从表中看到 3 = C3 +CC3 - （C2 * a13 + C1* a23 ） 可得到可得到 CC3 9/5 时，原最优解不变。时，原最优解不变。 2、若、若 cs 是基变量的系数：是基变量的系数： 例例: Max Z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 S.t. x1 + 2x2+
28、 x3 = 8 4x1 + x4 =16 4x2 +x5 = 12 x1 , x2 , x3 , x4 , x5 0 例、下表为最优单纯形表，考虑基变量系数例、下表为最优单纯形表，考虑基变量系数 c2 发生变化发生变化从表中看到从表中看到 可得到可得到 -3 C-3 C2 1 时，原最优解不变。时，原最优解不变。 二、已知二、已知C ，求新最优解，求新最优解见书见书右端项右端项 b 发生变化发生变化一、保持原最优基，求变化范围一、保持原最优基，求变化范围见书见书二、已知变化，求新最优解二、已知变化，求新最优解 例、上例最优单纯形表如下例、上例最优单纯形表如下 0 0.25 0 这里这里 B-1
29、 = -2 0.5 1 0.5 -0.125 0 因此，因此，设设 b1 增加增加 4，则，则 x1 , x5 , x2 分别变为：分别变为： 4 + 0*4 = 4，4 + (-2)*4 = - 4 0，2 + 0.5*4 = 4用对偶单纯形法进一步求解，可得：用对偶单纯形法进一步求解，可得： x* = ( 4, 3, 2, 0, 0 )T f* = 17 增加一个变量增加一个变量 增加变量增加变量 xn+1 则有相应的则有相应的 pn+1 ， cn+1 。那么，计算出。那么，计算出 B-1pn+1 n+1 填入最优单纯形表，若填入最优单纯形表，若 n+1 0 则最优解不变；否则，则最优解不
30、变；否则，进一步用单纯形法求解。进一步用单纯形法求解。例、前例增加例、前例增加 x6，p6 = ( 2, 6, 3 )T ，c6 = 5 。计算得到。计算得到用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5 增加一个约束增加一个约束 增加约束一个之后，应把最优解带入新增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，优单纯形表作为新的一行， 用保持原最优基用保持原最优基的方法求解的方法求解例、前例增加例、前例增加3x1+ 2x215，原最
31、优解不满足，原最优解不满足这个约束。于是这个约束。于是 A中元素发生变化中元素发生变化 （只讨论 N 中某一列变化情况） 与增加变量与增加变量 xn+1 的情况类似，假设的情况类似，假设 pj 变化变化 。那么，重。那么，重新计算出新计算出 B-1pj j 填入最优单纯形表，若填入最优单纯形表，若 j 0 则最优解不变；否则，进则最优解不变；否则，进一步用单纯形法求解。一步用单纯形法求解。可得最优解：x* = ( 3.2,0.8,0,0,2.4 )T f* = 15.2 灵敏度分析灵敏度分析 (内容，为重点内容，为重点) Ci 发生变化 Bj发生变化 增加一个变量 增加一个约束 A中元素发生变化
