线性规划模型（课堂PPT）

1、管管 理理 运运 筹筹 学学1第第1节节 线性规划问题与模型线性规划问题与模型 一、线性规划模型一、线性规划模型 从招聘总经理谈起从招聘总经理谈起 v 管管 理理 运运 筹筹 学学2泰山工厂生产状况 泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表： 目前生产现状： 不生产产品A ，生产产品B每天30 ， 获利3600 产品A产品B资源限量设 备劳动力原材料9434510360200300利润元/kg70120管管 理理 运运 筹筹 学学3招聘总经理！ 约翰： 我应聘！ 在现有资源状况下，我可以使利润达到4280 ！ 方案是： 生产A 产品

2、20 ， 生产 B 产品 24 可行性：9*20+4*24=276360 4*20+5*24=200 3*20+10*24=300管管 理理 运运 筹筹 学学4怎么达到的？ 约翰使用了运筹学中的线性规划模型 问题：如何安排生产计划，使得获利最多？ 步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束 9X1+4X2360 人力约束4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20管管 理理 运运 筹筹 学学5线性规划图解法 由数学知识可知：y=ax+b是一条直线，同理：Z=70

3、x1+120 x2x2=70/120 x1-Z/120也是一条直线，以Z为参数的一族等值线。 9x1+4x2 360 x1 360/9-4/9x2 是直线 x1=360/9-4/9x2 下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。管管 理理 运运 筹筹 学学6例1图示. 90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2管管 理理 运运 筹筹 学学7 最优解： X1=20 , x2=24 对应

4、的生产方案： 生产A 产品20 生产 B 产品 24 获利：70*20+120*24=4280管管 理理 运运 筹筹 学学8约翰就任泰山工厂总经理！管管 理理 运运 筹筹 学学9二、线性规划图解法二、线性规划图解法例例2. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0管管 理理 运运

5、 筹筹 学学10例例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500图图 解解 法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法：管管 理理 运运 筹筹 学学11线性规划图解法（续）线性规划图解法（续） (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标

6、系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0管管 理理 运运 筹筹 学学12线性规划图解法（续）线性规划图解法（续）（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400管管 理理 运运 筹筹 学学13线性规划图解法（续）线性规划图解法（续）（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100

7、x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1管管 理理 运运 筹筹 学学14线性规划图解法（续）线性规划图解法（续）（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100

8、 x2z=10000=50 x1+100 x2CBADE管管 理理 运运 筹筹 学学15线性规划图解法（续）线性规划图解法（续） 重要结论： 如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解； 无穷多个最优解。若将例1中的目标函数变为max z=50 x1+50 x2，则线段BC上的所有点都代表了最优解； 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件； 无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。管管 理理 运运 筹筹

9、学学16线性规划图解法（续）线性规划图解法（续） 例例2 2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？管管 理理 运运 筹筹 学学17线性规划图解法（续）线性规划图解法（续）解：目标函数： Min f = 2x1 + 3 x2 约

10、束条件：s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300 400 500 600100200300400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200 x1 x2 Q管管 理理 运运 筹筹 学学18三、线性规划一般形式 企业管理的重点内容之一就是在各种生产因素和产品的调配问题上。 一方面， 在一固定阶段， 企业管理者所能“投入”的生产因素：原料、人力、设备时间是由一定限量的。

11、 在一固定期间，任何一工厂的厂房、工场、机器、一切固定资本是不会变动的， 再雄厚的资本， 也还是有它的限度。再从流动资本来看，原料的来源和存量， 各种技工的人数和时间，在一相当的短期中也是有一定的限度。 管管 理理 运运 筹筹 学学19线性规划一般形式 另一方面，企业管理者“投入”生产因素时，一定有一完整的目标。在商言商， 企业管理者的目标当然是求最高的利润和最低的成本。如何将受时间、空间、数量限制的“投入”生产因素调配“得当”，达到最佳的境界而获得最佳的“产出”量，因而获得最大的收益。 以上就是企业管理者须面对的一个问题的两个方面。企业管理者不仅要知道如何调配手头上有限的生产因素，同时要从不

12、同的调配中， 找出最佳的调配，来达到他的企业经营目标最低成本、最高利润。管管 理理 运运 筹筹 学学20线性规划一般形式 事实上，用最低的代价去追求最高的收获， 原是一种理性的要求，因此在任何理性活动中，都有一求“最佳”问题的存在。管管 理理 运运 筹筹 学学21例题3配方问题 养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200管管 理理 运运 筹筹 学学22例题3建模 设抓取饲料

13、I x1kg;饲料II x2kg;饲料III x3kg 目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5 约束条件：3x2+2x2+x3+6x4+18x5 700营养要求： x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5 =200用量要求： x1 50,x2 60,x3 50,x4 70,x5 40非负性要求：x1 0,x2 0,x3 0,x4 0,x5 0 管管 理理 运运 筹筹 学学23例题4：人员安排问题 医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计： 序号时段最少人数安排人数1061

14、060X12101470X23141860X34182250X45220220X56020630 x6管管 理理 运运 筹筹 学学24例题4建模 目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30非负性约束：xj 0,j=1,2,6管管 理理 运运 筹筹 学学25归纳：线性规划的一般模式 目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxn 约束条件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2

15、 am1x1+am2x2+am3x3+amnxn (= )bn非负性约束：x1 0,x2 0,xn 0 管管 理理 运运 筹筹 学学26四、线性规划的标准型四、线性规划的标准型 一般形式一般形式目标函数： Max （Min） 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 标准形式标准形式目标函数： Max z = c1

16、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，bi 0管管 理理 运运 筹筹 学学27线性规划的标准型线性规划的标准型 可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:管管 理理 运运 筹筹 学学28线性规划的标准型线性规划的标准型

17、1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 则该极小化问题与下面的极大化问题有相同的最优解，即 Max z = - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min f - Max z管管 理理 运运 筹筹 学学29线性规划的标准型线性规划的标准型2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi(ai1 x1 + ai2

18、 x2 + + ain xn )显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi管管 理理 运运 筹筹 学学30线性规划的标准型线性规划的标准型 当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi管管 理理 运运 筹筹 学学31线性规划的标准型线性规划的标准型 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于

19、”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。 3.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi 40 选选X2从从0，X1 =0X3 =30-2X2 0 0 X2 30/2 X4 =60-2X2 0 0 X2 60/2 X5 =24-2X2 0 0 X2 24/2 X2=min(30/2 , 60/2 , 24/2 ) =12X2进基变量，进基变量， X5出基变量。出基变量。管管 理理 运运 筹筹 学学44B B2 2=(P3 P

20、4 P2)Z=0+40X1+50X2 X3 +2X2 =30-X1 X4+2X2 =60-3X1 2X2=24-X5 管管 理理 运运 筹筹 学学45 1/2 ，代入式，代入式， ，Z=600 +40X1 -25X5X3 =6 -X1 +X5 X4 = 36-3X1 +X5 X2=12 -1/2X5令令X1 =X5 =0 X(2) =(0, 12, 6, 36, 0)T Z(2) =600管管 理理 运运 筹筹 学学46(2)(2) 判断判断 400 X(2)不是不是。(3)(3) 选选X1从从0， X5 =0 X3= 6- X1 0 0 X4= 36-3X1 0 0 X2=12 0 0 X1

21、=min( 6/1 , 36/3 , 1 ) =6X1进基，进基， X3出基。出基。管管 理理 运运 筹筹 学学47B3 =(P1 P4 P2 )Z=840-40X3+15X5X1=6 - X3 + X5 X4= 18+3X3 - 2X5X2=12 -1/2X5令令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)TZ(3) =840管管 理理 运运 筹筹 学学48(2)(2) 150 X(3)不是不是(3)(3) 选选X5从从0， X3 =0 X1=6 +X5 0 0 X4= 18 -2X5 0 0 X2=12-1/2 X5 0 0 X5=min( 18/2 , 12/1/2

22、 ) =9X5进基，进基， X4出基。出基。管管 理理 运运 筹筹 学学49B4=(P1 P5 P2 )Z=975- 35/2X3 - 15/2X4X1= 15 + 1/2X3 - 1/2X4X5= 9 + 3/2X3 - 1/2X4X2= 15/2 -3/4X3 + 1/4X4令令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975管管 理理 运运 筹筹 学学500(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)管管 理理 运运 筹筹 学学51 maxZ=CX当当LP的数学模型为矩阵型的数学模型为

23、矩阵型 AX=b 时，时， X 0 0两个重要公式：两个重要公式：XB =B-1 b-B-1 NXNZ=CB B-1 b+(CN -CB B-1 N)XN当当XN =0时，时， B-1 b 0X=Z= CB B-1 b管管 理理 运运 筹筹 学学52当当LPLP的数学模型为一般型时的数学模型为一般型时njjjXCZ1max), 2 , 1(0), 2 , 1(1njXmibXajnjijij两个重要公式形如：两个重要公式形如：nmjjmiijijmiiinmjjijiiXaCCbCZmiXabX1111)(), 2 , 1(管管 理理 运运 筹筹 学学531 00 a1m+1 a1n0 10

24、a2m+1 a2n0 01 amm+1 amn设设A=A=B=(P1 P2 Pm )=InmjijijimibXaX1), 1(), 2 , 1(1miXabXnmjjijii管管 理理 运运 筹筹 学学54nmjjmiijijimiinmjiinmjjijimiiminmjiiiiXaCCbCXCXabCXCXCZ11111111)()(miiiTmbCZbbX11)0,0,(当当Xj =0 (j=m+1,n)时时,管管 理理 运运 筹筹 学学551.5.2 单纯形法原理单纯形法原理njjjXCZ1max), 2 , 1(0), 2 , 1(1njXmibXajnjijijnmjjmiiji

25、jmiiinmjjijiiXaCCbCZmiXabX1111)(), 2 , 1(管管 理理 运运 筹筹 学学56此时，此时，B=(P1 P2 Pm )对应的基本可行解为对应的基本可行解为miiiTmbCZbbX11)0,0,(nmjjijiinmjjjmiXabXXZZ110), 2 , 1(1)(1)管管 理理 运运 筹筹 学学57定理定理1 1：对解：对解X(1) ，若检验数，若检验数 j ( j=m+1,n)全全部部 0，则则X(1)为最优解。为最优解。定理定理2 2：对：对X(1)，若有某个非基变量，若有某个非基变量Xm+k m+k00且相应的且相应的Pm+k =(a1m+k , ,

26、amm+k )T 0，则原问题则原问题无有限最优解。无有限最优解。管管 理理 运运 筹筹 学学58定理定理2证明证明Xi =bi - aij xjJ=m+1n令非基变量令非基变量Xm+k = ( 0)X(2) =(b1 - a1m+k , ,bm - amm+k ,0, , , ,0)TAX(2) =b X(2) 0Z=Z0+ m+k 当当 时时 Z 管管 理理 运运 筹筹 学学59例：例： Z=30X1+20X2 -X1+3X2 +X3 =10-3X1+2X2 +X4 =15初始基初始基B1 =(P3 P4 )X(1) =(0, 0, 10, 15 )T Z(1) =0Z=030X1+20X

27、2X3=10-(-X1 +3X2 )X4 =15-(-3X1 +2X2 )管管 理理 运运 筹筹 学学60选中选中X1从从0，X2 =0 X3=10-(-X1 ) 0 0 X4=15-(-3X1 ) 0 0 求求X1， X1+ , ,Z Z+ 管管 理理 运运 筹筹 学学61换基迭代公式：换基迭代公式：(1)、决定换入变量：决定换入变量：maxmax j = m+k ，则则Xm+k 为换入变量为换入变量 j00(2)、决定换出变量：决定换出变量：bi -aim+kXm+k 0 0 ( i=1 ,2 , m)Xm+k biaim+k(aim+k 0 0 )管管 理理 运运 筹筹 学学62= =

28、min aim+k 0 =0 =biaim+kbrarm+k则则X Xr为换出变量为换出变量。管管 理理 运运 筹筹 学学63定理定理3：经单纯形法得到的：经单纯形法得到的X(2) =(b1 - a1m+k , ,bm - amm+k ,0, , , ,0)T是基本可行解，且是基本可行解，且Z(2) Z(1) 管管 理理 运运 筹筹 学学64证明：设证明：设Xr = Xm , Xm =0, Xm+k = =bmAmm+k(0)X(1)中中P1 , Pm线性无关，下证线性无关，下证P1 , Pm -1 , Pm +k线性无关。线性无关。若否，因为若否，因为P1 , Pm线性无关线性无关则则Pm

29、+k = a1m +k P1+ + amm +k Pm 而而Pm +k = l1 P1+ lm -1 Pm -1 管管 理理 运运 筹筹 学学65 - (a1m +k - l1 )P1 + +(am -1m +k - lm -1 ) Pm -1+ am m+k Pm =0P1 , ,Pm线性相关，矛盾。线性相关，矛盾。X(2)是基本解，且是可行解是基本解，且是可行解 管管 理理 运运 筹筹 学学66单纯形法基本步骤单纯形法基本步骤(1)、定初始基，初始基本可行解、定初始基，初始基本可行解(3)、若有若有 k 0 0，Pk全全 0，停，停， 没有有限最优解；没有有限最优解； 否则转否则转(4)(

30、2)、对应于非基变量检验数、对应于非基变量检验数 j全全 0。 若是，停，得到最优解；若是，停，得到最优解； 若否，转若否，转(3)。管管 理理 运运 筹筹 学学67= = min aim+k 0 =0 =biaim+kbrarm+k定定X Xr为换出变量，为换出变量，a arm+k为为主元。主元。由最小由最小比值法求：比值法求：maxmax j = m+kXm+k 换入变量换入变量 j00(4)、管管 理理 运运 筹筹 学学68转转(2) (2) m+k 0 a1m+k 0arm+k 1amm+k 0初等行变换初等行变换Pm+k = =(5)、以、以a arm+k为中心，换基迭代为中心，换基

31、迭代管管 理理 运运 筹筹 学学69证明可用归纳法（略）证明可用归纳法（略）X(1)X(2)X(3)X XX在边界上在边界上X在内部在内部X X +(1- ) X(2) (0 1)X X(1) +(1- ) X(3) X(1) (1- ) X(2) (1- )X(3) X=+(0 1)管管 理理 运运 筹筹 学学70证明：证明： 设设X(1) , ,X(k) 为可行域顶点，若为可行域顶点，若X*不是不是顶点，但顶点，但 max Z = C X* X*=定理定理2：可行域有界，最优值必可在顶点得到：可行域有界，最优值必可在顶点得到 i X(i)ki=1 i =1ki=10 i 1 1CX*= i

32、C X(i)ki=1 i CX(m)ki=1= CX(m) 设设 CX(m) Max (C X(i) 1 1 i k k管管 理理 运运 筹筹 学学71Z(1) = Ci bii=1mZ(2) = Ci (bi - aim+k)+ Cm+k i=1m = Ci bi - + Cm+k i=1m Ci aim+ki=1m = Ci bi +Cm+k - Ci aim+k i=1m i=1mZ(2) - Z(1) =(Cm+k -Zm+k ) = m+k 0 管管 理理 运运 筹筹 学学721.5.3 单纯形表单纯形表 C1 C2 Cm Cm+1 Cm+k Cn X1 X2 Xm Xm+1 Xm+

33、k XnCB XB Z0 0 0 0 m+1 m+k nC1 X1 b1 1 0 0 a1m+1 a1m+k a1nC2 X2 b2 0 1 0 a2m+1 a2m+k a2nCr Xr br 0 0 0 arm+1 arm+k arnCm Xm bm 0 0 1 amm+1 amm+k annmiiibCZ10miijijjaCC1管管 理理 运运 筹筹 学学73 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 40 50 0 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X

34、4 6060 3 3 2 0 1 0 302 0 1 0 300 0 X5 24 0 (2) 0 0 1 12 24 0 (2) 0 0 1 12 XB 600 40 0 0 0 -25 600 40 0 0 0 -250 0 X3 6 (1) 0 1 0 -1 66 (1) 0 1 0 -1 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840 0 0 -40 0 15 840 0 0 -40 0 1540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4

35、18 0 0 -3 1 2 18 0 0 -3 1 250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2管管 理理 运运 筹筹 学学74 XB 975 0 0 -35/2 -15/2 0 975 0 0 -35/2 -15/2 040 40 X1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 0 0 X5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 50 50 X2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0本问题的最优解本问题的最优解 X=(15, 15/2, 0, 0, 9)T

36、Z=975管管 理理 运运 筹筹 学学75几点说明：几点说明：(1)(1)、例、例 maxZ=maxZ=X1 +2X2X1 4X2 3X1+2X2 8 X1 , X2 0 0 X1+X3 = = 4X2+X4 = = 3X1+2X2+X5= = 8 X1 X5 0 0管管 理理 运运 筹筹 学学76 1 2 0 0 0 1 2 0 0 0 X1 X2 X3 X4 X5CB XB 0 1 2 0 0 00 1 2 0 0 00 0 X3 4 1 0 1 0 0 4 1 0 1 0 00 0 X4 3 0 (1) 0 1 03 0 (1) 0 1 00 0 X5 8 1 2 0 0 1 8 1 2

37、 0 0 1CB XB 6 1 0 0 -2 0 6 1 0 0 -2 00 0 X3 4 1 0 1 0 0 4 1 0 1 0 0 2 2 X2 3 0 1 0 1 0 3 0 1 0 1 0 0 0 X5 2 2 (1) 0 0 -2 1 (1) 0 0 -2 1 ( (接下表接下表) )管管 理理 运运 筹筹 学学77 1 2 0 0 0 1 2 0 0 0 X1 X2 X3 X4 X5 CB XB 8 0 0 0 0 -18 0 0 0 0 -10 0 X3 2 0 0 1 (2) -1 2 0 0 1 (2) -12 2 X2 3 0 1 0 1 03 0 1 0 1 01 1 X

38、1 2 1 0 0 -2 1 2 1 0 0 -2 1CB XB 8 0 0 0 0 -1 8 0 0 0 0 -10 0 X4 1 0 0 1/2 1 -1/2 1 0 0 1/2 1 -1/2 2 2 X2 2 0 1 -1/2 0 1/2 2 0 1 -1/2 0 1/2 1 1 X1 4 4 1 0 1 0 0 1 0 1 0 0 管管 理理 运运 筹筹 学学78X X(1)(1)= = (2,3) Z Z(1)(1)=8 =8 X X(2)(2)= = (4,2) Z Z(2)(2)=8=8无穷多解无穷多解全部解：全部解：X X= + (1-) (0 1)2 4 3 2管管 理理 运

39、运 筹筹 学学79(2)(2)、例：、例： 求求 minZ=minZ=X1 -X2+X3 -3X5X2+X3 -X4+2X5 = = 6X1+2X2 -2X4 = = 52X2 +X4+3X5 +X6 = = 8X1 X6 0 0管管 理理 运运 筹筹 学学80 1 -1 1 0 -3 0 1 -1 1 0 -3 0 X1 X2 X3 X4 X5 X6CB XB 11 0 -4 0 3 -5 011 0 -4 0 3 -5 01 1 X3 6 0 1 1 -1 2 0 6 0 1 1 -1 2 01 1 X1 5 1 2 0 -2 0 05 1 2 0 -2 0 00 0 X6 8 0 2 0

40、 1 3 1 8 0 2 0 1 3 1CB XB -7/3 0 -2/3 0 14/3 0 5/3 -7/3 0 -2/3 0 14/3 0 5/31 1 X3 2/3 0 -1/3 1 -5/3 0 -2/3 2/3 0 -1/3 1 -5/3 0 -2/3 1 1 X1 5 1 2 0 -2 0 05 1 2 0 -2 0 0-3 -3 X5 8/38/3 0 2/3 0 1/3 1 1/30 2/3 0 1/3 1 1/3CB XB -4 1/3 0 0 4 0 5/3-4 1/3 0 0 4 0 5/31 1 X3 3/2 1/6 0 1 -2 0 -2/33/2 1/6 0 1 -

41、2 0 -2/3-1 -1 X2 5/2 1/2 1 0 -1 0 0 5/2 1/2 1 0 -1 0 0 -1 -1 X5 1 -2/3 0 0 1 1 1/31 -2/3 0 0 1 1 1/3管管 理理 运运 筹筹 学学81判定定理判定定理1 1：基本可行解：基本可行解X X，当全部，当全部 j 0 0时，时，X X为为最优解。最优解。判定定理判定定理2 2：对可行基：对可行基B B，当某，当某 k00，且，且Pk=(a1k amk )T 0，则原问题无有限最优解。则原问题无有限最优解。 换入变量：换入变量：maxmax j = j = m+k Xm+k j 00, 则判定原问题无可行

42、解。则判定原问题无可行解。管管 理理 运运 筹筹 学学98两阶段法原理：两阶段法原理：(1)、辅助问题的基本可行解、辅助问题的基本可行解X(0) 为最优解，对应为最优解，对应最小值最小值 =0 则则X(0) 的前的前n个分量是原问题的基本可行解。个分量是原问题的基本可行解。管管 理理 运运 筹筹 学学99 设设X(0)=(X1(0) Xn(0) , y1(0) yn(0) )T 使使 aij xj(0)+ yi(0) bi ( i=1, 2, ,n )nj=1 =0, y1(0) = = yn(0) =0 aij xj(0) bi ( i=1, ,m )nj=1证明：证明：管管 理理 运运 筹

43、筹 学学100(2)、原问题有可行解时，辅助问题最优值、原问题有可行解时，辅助问题最优值 =0 。证明：若原问题有可行解证明：若原问题有可行解X(0)=(X1(0) , , Xn(0)T使使 aij xj(0) bi ( i=1, ,m )j=1n作作X(1)=( X1(0) Xn(0) ,0 0 )T = yi 0 =0i=1m必为辅助问题最优解必为辅助问题最优解管管 理理 运运 筹筹 学学101maxZ= -X1 +2X2 X1 +X2 2-X1 +X2 1 X2 3 3X1 X2 0例例2 2：管管 理理 运运 筹筹 学学102第第(1)阶段：阶段：minW=X6 +X7 X1 +X2

44、-X3 +X6 = =2-X1 +X2 -X4 +X7 = =1 X2 +X5 = =3X1 X7 0管管 理理 运运 筹筹 学学103 0 0 0 0 0 1 1 0 0 0 0 0 1 1 X1 X2 X3 X4 X5 X6 X7CB XB 3 3 0 -2 1 1 0 1 1 0 0 0 0 01 1 X6 2 1 1 -1 0 0 1 0 2 1 1 -1 0 0 1 0 1 1 X7 1 -1 1 -1 (1) 0 -1 0 0 1 (1) 0 -1 0 0 1 0 X5 3 0 1 0 0 1 0 0 3 0 1 0 0 1 0 0 CB XB 1 1 -2 -2 0 1 -1 0

45、 1 -1 0 0 2 X6 1 (2) 0 -1 1 0 1 -1 1 (2) 0 -1 1 0 1 -1 X2 1 -1 1 -1 1 0 -1 0 0 1 1 0 -1 0 0 1 X5 2 1 0 0 1 1 0 -1 2 1 0 0 1 1 0 -1 XB 0 0 0 0 0 0 0 0 0 0 0 1 1 X1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 1/2 1 0 -1/2 1/2 0 1/2 -1/2 X2 3/2 0 3/2 0 1 -1/2 -1/2 0 1/2 1/21 -1/2 -1/2 0 1/2 1/2 X5 3/2 0 0 -1/2 1/2 1 -

46、1/2 -1/2 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 管管 理理 运运 筹筹 学学104 -1 2 0 0 0 X1 X2 X3 X4 X5CB XB 3/2 0 0 1/2 3/2 0 -1 X1 1/2 1 0 -1/2 (1/2) 0 2 X2 3/2 0 1 -1/2 -1/2 0 0 X5 3/2 0 0 1/2 1/2 1 XB 4 -3 0 2 0 0 X4 1 2 0 -1 1 0 X2 2 1 1 -1 0 0 X5 1 -1 0 (1) 0 1 XB 6 1 0 0 0 -2 X4 2 1 0 0 1 1 X2 3 0 1 0 0 1 X3 1 -1

47、0 1 0 1管管 理理 运运 筹筹 学学105例例3：maxZ= 2X1 +X2 5X1 +10X2 82X1 +2X2 1X1 ，X2 0管管 理理 运运 筹筹 学学106第第(1)(1)阶段：阶段：minW= X55X1 +10X2 -X3 +X5 =82X1 +2X2 +X4 = =1X1 X5 0管管 理理 运运 筹筹 学学107 0 0 0 0 1 0 0 0 0 1 X1 X2 X3 X4 X5 CB XB 8 -5 -10 1 0 01 X5 8 5 10 -1 0 10 X4 1 2 (2) 0 1 0 XB 3 5 0 1 5 01 X5 3 -5 0 -1 -5 10 X

48、2 1/2 1 1 0 1/2 0管管 理理 运运 筹筹 学学108X2X1O管管 理理 运运 筹筹 学学109第第1阶段阶段 最优基最优基B* min = *(1)、 *0 (2)、 * =0 yi 0( i=1,2, ,m) B* 基变量无人工变量基变量无人工变量 B* 基变量含人工变量基变量含人工变量yr 单纯形表中，单纯形表中， yr+ ark yk + arj xj =0 () k Jj JJ：非基变量下标集合：非基变量下标集合管管 理理 运运 筹筹 学学1101) arj 全全 =0 () 式多余方程式多余方程2) arj 有有 0 元，设为元，设为ars 0 以以ars为主元，换

49、基迭代，最后得到为主元，换基迭代，最后得到管管 理理 运运 筹筹 学学111例例4 4、求、求maxZ= -4X1 -3X3 1/2X1 +X2+1/2X3-2/3X4 = 23/2X1 +3/4X3 = =33X1 -6X2 +4X4 = 0X1 , X2 , X3 , X4 0满足满足管管 理理 运运 筹筹 学学112 0 0 0 0 1 1 1 X1 X2 X3 X4 y1 y2 y3 CB XB 5 -5 5 -5/4 -10/3 0 0 0 1 y1 2 1/2 1 1/2 -2/3 1 0 0 1 y2 3 3/2 0 3/4 0 0 1 0 1 y3 0 3 6 0 4 0 0

50、1 CB XB 5 0 -5 -4/5 10/3 0 0 5/3 1 y1 2 0 2 1/2 -4/3 1 0 -1/6 1 y2 3 0 3 3/4 2 0 1 -1/2 0 X1 0 1 -2 0 4/3 0 0 1/3第第 一一 阶阶 段段 一一二二管管 理理 运运 筹筹 学学113 CB XB 0 0 0 0 0 5/2 0 5/4 0 X2 1 0 1 1/4 -2/3 1/2 0 -1/2 1 y2 0 0 0 0 0 -3/2 1 -1/4 0 X1 2 1 0 1/2 0 1 0 1/6第一阶段第一阶段三三 -4 0 -3 0 X1 X2 X3 X4CB XB -8 0 0

51、-1 0 0 X2 1 0 1 1/4 -2/3-4 X4 2 1 0 1/2 0第二阶段第二阶段管管 理理 运运 筹筹 学学114的特殊情况的特殊情况: :第第1 1阶段结束时阶段结束时, ,有人工变量有人工变量在基中取在基中取0,0,但但Xi系数全为系数全为0,0,此方程为多余方此方程为多余方程。程。管管 理理 运运 筹筹 学学115例例5 5、求、求minZ=4X1 +3X31/2X1 +X2 +1/2X3 -2/3X4 =23/2X1 -1/2X3 = =33X1 -6X2 +4X4 =0X1 , X2 , X3 , X4 0满足满足管管 理理 运运 筹筹 学学116 0 0 0 0

52、1 1 1 X1 X2 X3 X4 y1 y2 y3 CB XB 5 -5 5 0 -10/3 0 0 0 1 y1 2 1/2 1 1/2 -2/3 1 0 0 1 y2 3 3/2 0 -1/2 0 0 1 0 1 y3 0 3 6 0 4 0 0 1 CB XB 5 0 -5 0 10/3 0 0 5/3 y1 2 0 2 1/2 -4/3 1 0 -1/6 y2 3 0 3 -1/2 -2 0 1 -1/2 X1 -2 1 -2 0 4/3 0 0 1/3第第 一一 阶阶 段段 一一二二管管 理理 运运 筹筹 学学117 CB XB 0 0 0 5/4 0 5/2 0 5/4 X2 1

53、 0 1 1/4 -2/3 1/2 0 -1/2 y2 0 0 0 -5/4 0 -3/2 1 -1/4 X1 2 1 0 1/2 0 1 0 1/6 CB XB 0 0 0 0 0 1 1 1 X2 1 0 1 0 -2/3 1/5 1/5 -2/15 X3 0 0 0 1 0 1/5 -4/5 1/5 X1 2 1 0 0 0 2/5 2/5 1/15第第 一一 阶阶 段段三三四四管管 理理 运运 筹筹 学学118 -4 0 -3 0 X1 X2 X3 X4CB XB -8 0 0 0 0 0 X2 1 0 1 0 -2/3-3 X3 0 0 0 1 0 -4 X1 2 1 0 0 0第二

54、阶段第二阶段的特殊情况，可将人工变量换出的特殊情况，可将人工变量换出管管 理理 运运 筹筹 学学119单纯形法小结：单纯形法小结：1)1)、标准型中有单位基。、标准型中有单位基。2)2)、标准型中没有单位基，用大、标准型中没有单位基，用大M M法加人工变法加人工变量，使之构成单位基。量，使之构成单位基。 求求maxZ时，目标中时，目标中M MXj 求求minZ时，目标中时，目标中M MXj3)3)、判定最优解定理：、判定最优解定理：maxZ问题，检验数问题，检验数j 0minZ问题，检验数问题，检验数j 0管管 理理 运运 筹筹 学学1204)4)、解的几种情况：、解的几种情况：唯一解唯一解无

55、穷多解最优表中非基变量检验数有为无穷多解最优表中非基变量检验数有为0 0者。者。无有限最优解无有限最优解 max,j 0 但但Pj 0 min,j 0 但但Pj 0无可行解无可行解最优表中人工变量在基中，且最优表中人工变量在基中，且0 0。建模有问题建模有问题5)5)、退化解问题、退化解问题管管 理理 运运 筹筹 学学121管管 理理 运运 筹筹 学学122第三章 运筹学优化模型大连海事大学刘巍管管 理理 运运 筹筹 学学123第第3节节 对偶线性规划与影子价格对偶线性规划与影子价格 一、对偶问题一、对偶问题 再谈招聘总经理再谈招聘总经理 v 管管 理理 运运 筹筹 学学124泰山工厂生产状况

56、 泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表： 目前生产现状： 不生产产品A ，生产产品B每天30 ， 获利3600 产品A产品B资源限量设 备劳动力原材料9434510360200300利润元/kg70120管管 理理 运运 筹筹 学学125招聘总经理！ 约翰： 我应聘！ 在现有资源状况下，我可以使利润达到4280 ！ 方案是： 生产A 产品20 ， 生产 B 产品 24 可行性：9*20+4*24=276360 4*20+5*24=200 3*20+10*24=300管管 理理 运运 筹筹 学学126怎么达到的？ 约翰使用了运筹学

57、中的线性规划模型 问题：如何安排生产计划，使得获利最多？ 步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束 9X1+4X2360 人力约束4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20管管 理理 运运 筹筹 学学127例1图示. 90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2管管 理理 运运 筹筹 学学128 X1=20 ,

58、x2=24 对应的生产方案： 生产A 产品20 生产 B 产品 24 获利：70*20+120*24=4280管管 理理 运运 筹筹 学学129问题的最优解*最优解如下* 目标函数最优值为 : 4280 变量 最优解 相差值 - - - x1 20 0 x2 24 0 约束 松弛/剩余变量 对偶价格 - - - 1 84 0 2 0 13.6 3 0 5.2 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 36 70 96 x2 87.5 120 233.333 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 276 360 无上限 2 150 200 2

59、26.923 3 227.586 300 400管管 理理 运运 筹筹 学学130再谈招聘总经理 约翰作为总经理将泰山工厂经营的很好了！ 汤姆来竞争了！ 竞争口号： 不裁员！ 不减薪！ 不加班！ 提高利润5 % ！管管 理理 运运 筹筹 学学131可能吗？ 目前约翰的经营已经是资源的最佳利用了！ 汤姆还有什么绝招增加利润呢？管管 理理 运运 筹筹 学学132 这个问题涉及到： （1） 线性规划的对偶问题 （2） 影子价格概念 管管 理理 运运 筹筹 学学133原来问题的最优解*最优解如下* 目标函数最优值为 : 4280 变量 最优解 相差值 - - - x1 20 0 x2 24 0 约束

60、松弛/剩余变量 对偶价格 - - - 1 84 0 2 0 13.6 3 0 5.2 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 36 70 96 x2 87.5 120 233.333 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 276 360 无上限 2 150 200 226.923 3 227.586 300 400管管 理理 运运 筹筹 学学134 对偶性是线性规划问题的最重要的内容之一。每对偶性是线性规划问题的最重要的内容之一。每一个线性规划（一个线性规划（ LP ）必然有与之相伴而生的另一个）必然有与之相伴而生的另一个线性规划问题，即