第三章线性规划模型

第三章线性规划模型应用运筹学浙江大学管理学院杜红博士副教授第三章线性规划模型线性规划问题的提出线性规划问题的建模典型特征和基本条件一般模型和标准模型线性规划的图解方法敏感分析与影子价格线性规划模型的应用线性规划问题的提出解决有限资源的最佳分配问题。即如何对有限的资源作出最佳方式的调配和最有利的使用，以使最充分地发挥资源的效能去获取最佳的经济效益。线性规划（LinearProgramming,LP)康托洛维奇1939《生产组织与计划中的数学方法》丹捷格（美）1947单纯形方法第三章线性规划模型线性规划问题的提出线性规划（LP)问题包含下列要素：变量：决策要控制的因素目标：决策目标（最优）的数学描述约束条件：实现目标的一组限制条件求LP问题：在约束条件下使目标最优的一组变量的取值解决环节：确定问题、建立模型、问题求解、经济分析、敏感性分析第三章线性规划模型建立线性规划问题模型线性规划问题举例：教材P40LP模型：决策变量：每周的生产批次G、T目标函数：maxZ＝30×G+20×T（获利最大）约束条件：1×G+2×T≤40（配料工序约束）(s.t.)2×G+1×T≤40（整流工序约束）1×G+1×T≤25（包装工序约束）G≥0;T≥0（生产批次的非负约束）第三章线性规划模型第三章线性规划模型建立线性规划问题模型总结模型构建的一般思路：确定该LP问题的目标是什么？实现目标取决于什么因素和条件？确定哪几个因素为决策变量？目标如何用决策变量来加以描述？约束条件如何表达？决策变量本身是否有限制条件？第三章线性规划模型例3-1:请你构建以下问题的LP模型：某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：用线性规划制订使总利润最大的生产计划。每件产品占用的机时数（小时/件）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18第三章线性规划模型建立的模型如下：设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数Z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：maxZ=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥0求解这个线性规划，可以得到最优解为：x1=294.12x2=1500x3=0x4=58.82最大利润为：z=12737.06（元）请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。另外，变量是否需要取整也是需要考虑的问题。第三章线性规划模型总结：线性规划问题的典型特征可用一些变量表示这类问题的待定方案，这些变量（决策变量）的一组值代表一个具体方案；存在一定的约束条件，这些约束条件都能用关于决策变量的线性不等式或等式来表示；有一个期望达到的目标，这个目标能以某种确定的数量指标刻划出来，而这种数量指标可表示为关于决策变量的线性函数，按所考虑的问题的不同，要求该函数值最大化或最小值。第三章线性规划模型线性规划问题的基本要求目标函数和约束条件必须是线性函数；线性表达：相加性、比例性决策变量的连续分布；不限于整数，可以是小数，但不能四舍五入目标函数的单一性；多目标是要设法简化成单目标模型必须是确定型的；所有参数(a、b、c)都应是确定值决策变量的非负性第三章线性规划模型线性规划问题模型的一般形式：目标函数：约束条件：max(min)zcxcxcxnn1122mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(..22112222212111212111第三章线性规划模型0x,x,xn21线性规划问题一般模型的简化形式：目标函数：maxZ=∑CjXj约束条件：∑aijXj≥(=,≤)biXj≥0i=1,2,3,……,mj=1,2,3,……,n第三章线性规划模型j=1nXj的单位贡献第i资源的约束量Xj的技术性系数：表示第j种活动消耗资源i的数量线性规划问题的标准形式目标函数为最大化；约束条件（非负条件除外）全为等式；约束条件右端项为大于等于零；maxZ=C1X1+C2X2+…+CnXns.t.a11X1+a12X2+…+a1nXn=b1a21X1+a22X2+…+a2nXn=b2……………am1X1+am2X2+…+amnXn=bmX1,X2,...,Xn≥0第三章线性规划模型将非标准形式转化为标准形式•目标函数为最小化：令Z’=-Z,Z’为最大化问题。•若约束条件是小于等于型：在不等式左边加上一个新变量（松弛变量），不等式改为等式，目标函数中新变量系数为零。•若约束条件是大于等于型：在不等式左边减去一个新变量（剩余变量），不等式改为等式，目标函数中新变量系数为零。第三章线性规划模型将非标准形式转化为标准形式•若约束方程右端项bi0:在约束方程两端乘以（－1），不等号改变方向，然后再转化成等式。•若决策变量Xk没有非负要求：作两个新变量Xk’≥0,Xk”≥0,令Xk＝Xk’-Xk”，在原有模型中用（Xk’－Xk”）代替所有的Xk，在非负约束中增加Xk’≥0和Xk”≥0。第三章线性规划模型第三章线性规划模型例3-2:将下列LP问题转化为标准形式x1,x3≥0,x2无符号限制minZ=2x1-3x2+x3s.t.x1-x2+2x3≤32x1+3x2-x3≥5x1+x2+x3=4第三章线性规划模型令Z’=-Z，引进松弛变量x4≥0,和剩余变量x5≥0，令x2=x2'-x2'‘其中x2'≥0，x2''≥0,得到以下等价的标准形式:MAXz’=-2x1+3x2'-3x2''-x3s.t.x1-x2'+x2''+2x3+x4=32x1+3x2'-3x2''-x3-x5=5x1+x2'-x2''+x3=4x1,x2',x2'',x3,x4,x5≥0第三章线性规划模型两个变量的线性规划问题的几何解释例3-3:z=0z=3z=6z=9z=12z=15.30123456-8-7-6-5-4-3-2-1654321x1x2目标函数等值线Z=X1+3X2可行域(4/3,14/3)Maxz=X1+3X2s.t.X1+X2≤6-X1+2X2≤8X1,X2≥0线性规划的可行域及最优解的性质若线性规划的可行域非空，则可行域必为凸集若线性规划有最优解，则最优解至少在一个极点上第三章线性规划模型(a)凸集(b)凸集(c)凸集(a)非凸集(b)非凸集(c)非凸集第三章线性规划模型线性规划的可行域及最优解的可能结果可行域为封闭的有界区域：唯一、多个最优解可行域为非封闭的无界区域：唯一、多个最优解、目标函数无界，无最优解可行域为空集：没有可行解，更无最优解线性规划的可行域及最优解的可能结果图示：(a)可行域封闭，唯一最优解(a)可行域封闭，多个最优解(d)可行域开放，多个最优解(e)可行域开放，目标函数无界(f)可行域为空集(c)可行域开放，唯一最优解第三章线性规划模型第三章线性规划模型线性规划的EXCEL求解：例3-1:某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：用线性规划制订使总利润最大的生产计划。每件产品占用的机时数（小时/件）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18第三章线性规划模型线性规划问题的提出线性规划问题的建模典型特征和基本条件一般模型和标准模型线性规划的图解方法影子价格与敏感分析线性规划模型的应用第三章线性规划模型第三章线性规划模型某厂生产甲、乙两种产品，消耗A、B两种原材料。生产一件甲产品可获利2元，生产乙产品获利3元。问在以下条件下如何安排生产？甲乙总量设备台时原材料A原材料B14020481612•对偶问题的提出建立线性规划模型：目标函数：MAXZ=2X1+3X2约束条件：X1+2X2≤84X1+≤164X2≤12X1,X2≥0从另一角度考虑：如果该厂决定不生产甲、乙两种产品，而将其资源出租或出售，这时工厂的决策者就要考虑给每种资源如何定价的问题。设用Y1,Y2,Y3分别表示出租单位设备台时的租金和出让原材料A、B的附加值。作如下比较，用一个单位设备台时和四个单位的原材料可以生产甲产品一件，获利2元，那么出租和出让的收益不应低于自己生产时的收益。因此有Y1+4Y2≥2;同样地乙产品也有：2Y1+4Y3≥3第三章线性规划模型•对偶问题的提出全部出让或出租的总收入为W=8Y1+16Y2+12Y3从决策者来看，当然希望W值越大越好。但从接受者来讲，支付越少越好。为提高竞争力，因此工厂只能在满足≥所有产品的利润条件，使其总收入具有竞争力的，因此，W需要求解最小值。因此有线性规划模型：目标函数：minW=8Y1+16Y2+12Y3s.tY1+4Y2≥22Y1+4Y3≥3Y1,Y2,Y3≥0第三章线性规划模型线性规划模型：目标函数：MAXZ=2X1+3X2s.t.X1+2X2≤84X1≤164X2≤12X1,X2≥0第三章线性规划模型线性规划模型：目标函数：MINW=8Y1+16Y2+12Y3s.t.Y1+4Y2≥22Y1+4Y3≥3Y1,Y2,Y3≥0最优解：X1=4,X2=2,Z=14最优解：Y1=1.5,Y2=0.125,Y3=0,W=14原问题对偶问题对偶问题与影子价格定义：设以下线性规划问题MAXZ=CTXs.t.AX≤bX≤0为原始问题，则称以下问题MINW=bTYs.t.ATY≤CY≥0为原始问题的对偶问题，最优值Y为影子价格第三章线性规划模型第三章线性规划模型对偶问题对偶问题第三章线性规划模型原问题与对偶问题转换：maxZ=6x1+8x2s.t.3x1+x2≥45x1+2x2≤7x1≥0,x2≤0minY=4w1+7w2s.t.3w1+5w2≥6w1+2w2≤8w1≤0,w2≥0对偶问题与原始问题的关系第三章线性规划模型目标极大化问题Cj（maxZ）极小化问题bi（minW）目标变量nxj≥0——aTijyi≥cj约束nxj无约束——aTijyi=cjxj≤0——aTijyi≤cj约束maijxj≥bi——yi≤0变量maijxj=bi——yi无约束aijxj≤bi——yi≥0对偶问题的性质对偶问题的对偶是原问题。若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等(Z*=W*)，最优解满足CX*=Y*b。若X*,Y*分别是原问题和对偶问题的可行解，则X*,Y*为最优解的充分必要条件是Y*XL=0和YSX*=0。第三章线性规划模型原问题标准型：MaxZ=CXAX+XL=bX,XL≥0对偶问题标准型：MinW=YbYA-YS=CY,YS≥0Yi*0可以推出xn+i*=0；xn+i*0可以推出Yi*=0；Ym+j*0可以推出xj*=0；xj*0可以推出Ym+j*=0第三章线性规划模型对偶问题的性质（续）原问题和对偶问题的互补松松弛关系第三章线性规划模型例3-4:根据对偶原理求解以下线性规划问题：minz=6x1+8x2