《运筹课件灵敏度分析123讲解》由会员分享，可在线阅读，更多相关《运筹课件灵敏度分析123讲解（64页珍藏版）》请在金锄头文库上搜索。
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报废量 目标为总盈利，约束为资源限制等
2、 maxZ=4X1+10X2+3X3-2X4 2X1+3X212 3X1+4X224 X3+X4=2X2 X35 X1,X2,X3,X40 例2：某工厂生产的一种产品由四个零件一和 三个零件二组成，这两种零件好用两种原 材料，由于三个车间拥有的设备和工艺不 同，每个工班原材料耗用量和零件产量不 同，问三个车间应各开多少工班，才能使 该产品的配套数达到最大。 分析：可控变量是什么，目标和约束是什 么 每班用料数（ 公斤） 每班产量（件数） A材料B材料零件一零件二 一车间 二车间 三车间 8 5 3 6 9 8 7 6 8 5 9 4 资源限量300500 可控变量：三个车间工班数， 目标：产品
3、配套数，约束资源约束 目标为两目标取小，要转化为一个目标时 的方法。 Z=min( (7x1+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 合理利用线材问题 现要做一百套钢管,
4、每套要长为2.9m、2.1m和1.5m的 钢管各一根。已知原料长7.4m，问应如何下料，使用的 原料最省。 设用方案 , 分别裁原料 钢管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 某工厂要用三种原材料C,P,H混合调配出 三种不同规格的产品A,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+ x2+ x3) x2 0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5
6、(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,D中C,P,H的含量分 别为AC,AP,AH,BC,BP,BH,DC,DP,DH。 例5 连续投资问题。某单位有资金10万元，在今 后5年内可考虑下列投资项目，已知： 项目A：从第1到第4年每年初可投资，并于次 年末回收本利115%； 项目B：第3年初需要投资，到第5年末回收本 利125%，但最大投资额不超过4万元； 项目C：第2年初需要投资，到第5年末能回收 本利140%，但最大投资额不超过3万元； 项目D：5年内每年
7、初可购买公債，当年末回 收本利106%。 问它应该如何安排每年的投资，使到5年末拥 有的资金最多？ 年份 项目 一 二 三 四 五 A X1AX2AX3AX4A B X3B CX2C D X1DX2DX3DX4DX5D x2A+x2C+x2D=1.06x1D 解：每年的投资额 应不超过手中的资 金。由于项目D每 年都可投资，且当 年末就可收回。所 以该单位每年必然 把资金全部投出去 ，即投资额等于手 中的资金数。 设第i年投资各项目的资金 为xiA,xib,xiC,xiD 。数学模型为： x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2D x4A+x4D=1.15x2
8、A+1.06x3D x5D=1.15x3A+1.06x4D xiA,xib,xiC,xiD0 Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D 第二章 线性规划的对偶理论 与灵敏度分析 改进单纯型法 对偶问题 对偶理论 目标函数值之间的关系 最优解之间的互补松弛关系 对偶单纯形法 对偶的经济解释 灵敏度分析 DUAL 第一节 改进单纯型法 需要求的几个重要指标 ，不需要完全的矩阵 变换就可求得。 需要求的：基可行解，非基变量， XBB-1b B-1B-1Pk 初始表为单位 阵（初始基） 确定 主元 素 -Y=-CBB-1 k 求，确定换入变 量xk ,计算B-1Pk ,
9、计 算，确定主元素， 对简化单纯型表作 旋转变换 简化单纯形表 Cj C CB XB B-1b X b A B-1b B-1A CCB B-1A Cj CB CS CN1 CB 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,松弛变量检验数为C CB B B B -1-1 ， C CB B B B -1-1称为 称为单纯形乘子单纯形乘子 Cj CB CN CB XB B-1b XB XN b B N B-1b E B-1N 0
10、CNCB B-1N 第二节 对偶问题 产品 资源 I II 总 量 原料 工时 2 3 4 6 100 120 利润 6 4 原问题：确定获利最大的生产方案 对偶问题：确定资源最低可接受 出让价格 建立两问题的模型，对比其最优解，最优目标函数 值的关系。 两规划最优目标函数值相等 为 Z=CB B-1b 此时 最优解XB= B-1b， Y= CB B-1(为原规划松弛变量在最 终表 中的检验数,即单纯形乘子） 原始问题 max z=C X s.t.AXb X 0 对偶问题 min =Yb s.t. YAC Y 0 max bA C CTAT bT min m n m n 第三节 对偶理论 一、
11、对偶问题的性质 1、对偶的对偶就是原始问题 对偶的定义 max z=CXmax z=CX s.t. AXbs.t. AXb X 0 X 0 min=Yb s.t. YAC Y 0 对偶的定义 max =-Yb s.t. -YA-C Y 0 min z=-Cmin z=-C X X s.t. -AX-bs.t. -AX-b X 0 X 0 2、其他形式问题的对偶 原始问题约束条件的性质，影响对偶问题变量的性质。 原始问题变量的性质，影响对偶问题约束条件的性质。 max z=Cmax z=C X X s.t. AXs.t. AX b b X 0 X 0 min =Yb s.t. YAC Y 0 m
12、axz=Cmaxz=C X X s.t. AXs.t. AX= =b b X 0 X 0 min =Yb s.t. YAC Y :unr max z=Cmax z=C X X s.t. AXs.t. AX b b X 0 X 0 min =Yb s.t. YAC Y 0 原问题（或对偶问题）对偶问题（或原问题 ） 目标maxZ目标min 变量 （n个） 0 0 无约束 约束 （n个） = 约束 （m个） = 变量 （m个） 0 0 无约束 min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15
13、max =6y1+12y2+8y3+15y4 s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0 = unr = x10 x20 x3: unr q原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 q原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。 二、原始对偶关系 1、可行解的目标函数值之间的关系 设XF、YF分别是原始问题和对偶问题的可行解 z=C XF YF AXF
14、YF b= 2、最优解的目标函数值之间的关系 设Xo、Yo分别是原始问题和对偶问题的最优解 z=C Xo=Yo AXo=Yo b=Y max z=CX s.t.AX+XS=b X, XS 0 min =Yb s.t. YA-YS=C Y, YS 0 YSX=0 Y XS=0 AT Y -E Ys C T T mn =n X A E Xs b= nm m 3、基解与检验数之间的关系 单纯形表和对偶 max z=C X s.t. AX+XS=b X, XS0 min =Yb s.t. YA -YS=C Y, YS0 min =Yb s.t. YA C Y0 对偶问题 max z=C X s.t. AX b X 0 原始问题 引
