第二章 线性规划 运筹学讲义

第二章线性规划问题与计算机求解§1问题的提出§2图解法§3单纯形法§4计算机求解例1(生产计划问题)某工厂生产A、B两种产品，其成本决定于所用的材料。已知单位产品所需材料量、材料日供应量及单价如表1-1所示。若每生产A或B产品一个单位，所费工资同为30元，又A、B的每单位销售价分别为120元和150元。问：工厂应如何安排生产，才能使所获总利润最大？产品生产所需原材料材料单价资源限制日供给给量kg产品A产品B原料a621元/kg180kg原料b4102.30元/kg400kg原料c3514.60元/kg210kg销售单价(元)120150单位产品利润(元)3122相关数据§1问题的提出产品A利润：120–1.00×6+2.30×4+14.60×3（材料）–30（工资）=31(元)数学模型设工厂日产A、B产品分别为x1,x2单位（决策变量）线性规划模型：目标函数：Maxz=31x1+22x2约束条件(subjectto)：s.t.材料的a约束6x1+2x2≤1804x1+10x2≤4003x1+5x2≤210x1,x2≥0产品A利润：120–(1.00×6+2.30×4+14.60×3)(材料)–30（工资）=31(元)产品A利润：150–(1.00×2+2.30×10+14.60×5)(材料)–30（工资）=22(元)§1问题的提出例2.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？设工厂生产产品A、B分别为x1，x2单位，则线性规划模型：目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0产品Ⅰ产品Ⅱ设备使用成本和单价资源限制设备1110元/时300台时原料A2112元/kg400kg原料B0118元/kg250kg销售单价(元)84140单位产品利润(元)50100例3.某饲料公司希望用玉米、红薯两种原料来配置一种混合饲料，已知两种原料含三种营养成分和混合饲料对营养成分的要求如下表：问题：公司应任何采购两种原材料，使即满足营养要求，又使成本最少？设公司采购用于混合饲料中玉米数量x1kg，红薯数量x2kg线性规划模型：目标函数：Minz=2x1+1.8x2约束条件：s.t.8x1+4x2≥203x1+6x2≥18x1+5x2≥16x1,x2≥0营养成分每公斤玉米每公斤红薯饲料对营养要求碳水化合物8420蛋白质3618维他命1516采购成本（元/KG）21.8线性规划问题主要类型•资源分配问题（resource-allocation）以符号表示的函数约束称为资源约束，这些限制要求使用的资源必须小于等于所能提供的资源的数量。资源分配问题的共性就是它们的函数约束全部为资源约束。例1、2•成本收益平衡问题（cost-benefit-trade-off）以符号表示的函数约束为收益约束，形式为收益取得的水平必须大于等于最低可接受水平。收益约束反映了管理层所规定的目标。如果所有约束均为收益约束，这一问题为成本收益平衡问题。例3•网络配送问题（distribution-network）以＝符号表示的函数约束称为确定需求的约束，它们表示了一定数量的确定的需求，提供的数量等于要求的数量。网络配送问题的共性就是它们的主要函数约束为一种特定形式的确定需求的约束。•混合问题（mixedProblem）除以上三类以外的问题•建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；Decisionvariables决策变量3.用决策变量的函数形式写出目标函数，确定最大化或最小化目标；Objectivefunction目标函数4.用一组决策变量的线性等式或线性不等式表示解决问题过程中必须遵循的约束条件;Constraints约束•一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥0非负性例2.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500§2图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：§2图解法画出可行域满足约束的区域(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1x2≥0x2=0x2x1x1≥0x1=0（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1§2图解法确定等值线与梯度（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADEz250200§2图解法确定最优解平行移动等值线，当移动到B点时，z在可行域内实现了最大化,B的坐标为最优解。解方程组得最优解：x1=50,x2=250,这时z=27500。点A，B，C，D，O是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限x2=250x1+x2=300x1x2z=27500=50x1+100x2CBADE可行域的性质1、凸集的概念：定义:如果集合C中任意两个点X1,X2其连线上的所有点也都是集合C中的点,称C为凸集.由于X1,X2的连线可表示为:αX1+(1-α)X2(其中0α1)因此,凸集用数学表示为:对任何X1∈C,X2∈C,有αX1＋(1-α)X2∈C(其中0α1),则称道C为凸集。规定：单点集{x}为凸集，空集为凸集。ABCDE顶点:设C是凸集,X∈C;若X不能用不同的两点X1∈C和X2∈C的线性组合表示为X=αX1＋(1-α)X2(其中0α1),则称X为C的一个顶点定理1：若线性规划问题存在可行解,则问题的可行域是凸集。定理2:可行域有有限个顶点。重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；最优解可在顶点达到,但不一定都是顶点无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。线性规划可行域为一个凸集（有界或无界）进一步讨论求极小化问题例4某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q线性规划的标准化一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥0•标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn目标最大化；约束条件：s.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2约束为等式；…………am1x1+am2x2+…+amnxn=bm决策变量均非负；x1，x2，…，xn≥0，bi≥0右端项非负。1.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+…+cnxn(可以)令z＝-f，则该极小化问题与下面的极大化问题有相同的最优解，即Maxz=－c1x1－c2x2－…－cnxn但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即Minf＝－Maxz2右端项有负值的问题：如bi0，则把该等式约束两端同时乘以－1，得到：－ai1x1－ai2x2－…－ainxn=－bi非标准形式的线性规划非标准形式的线性规划非标准形式的线性规划非标准形式的线性规划3、约束条件不是等式的问题：1）设约束条件为：ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的松弛变量s，使它等于约束右边与左边之差s=bi–(ai1x1+ai2x2+…+ainxn)显然，s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi2）当约束条件为：ai1x1+ai2x2+…+ainxn≥bi时类似地令剩余变量s=(ai1x1+ai2x2+…+ainxn)－bi；s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn－s=bi4.当某一个变量xj无约束，既没有非负约束时，可以令xj=xj’－xj”其中xj’≥0，xj”≥0例5：将以下线性规划问题转化为标准形式Minf=2x1－3x2+4x3s.t.3x1+4x2－5x3≤62x1+x3≥8x1+x2+x3=－9x1,x3≥0，x2无约束解：首先,将目标函数转换成极大化：令z=－f=－2x1+3x2－4x3其次考虑约束，有2个不等式约束，引进松弛变量x4，x5≥0。第三个约束条件的右端值为负，在等式两边同时乘－1。x2无约束，令x2=x2’－x2”其中x2’≥0，x2”≥0通过以上变换，可以得到以下标准形式的线性规划问题：Maxz=－2x1+3(x2’－x2”)－4x3s.t.3x1+4(x2’－x2”)－5x3+x4=62x1+x3－x5=8－x1－(x2’－x2”)－x3=9x1,x2’,x2”,x3,x4,x5≥0Minf=2x1－3x2+4x3s.t.3x1+4x2－5x3≤62x1+x3≥8x1+x2+x3=－9x1,x3≥0，x2无约束非标准形式化为标准形式总结线性规划模型化为标准形式变量xj≥0不变xj≤0令xj*=－xj,则xj*≥0xj取值无约束令xj=xj’－xj”,且xj’，xj”≥0约