运筹学考点

第二章线性规划第二章线性规划本章考点建立线性规划问题的数学模型图解法及灵敏度分析将一般形式的线性规划问题转换成标准形式计算机输出结果的解释•一般形式:目标函数：Max(Min)z=c1x1+c2x2+…+cnxn•约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2……am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥01.线性规划问题及其数学模型•一般形式:简化：nMax(Min)z=∑cjxjj=1约束条件：n∑aijxj≤(=,≥)biJ=1xj≥0(j=1,2,…,n)1.线性规划问题及其数学模型•一般形式:向量式：Max(Min)z=CX约束条件：n∑Pjxj≤(=,≥)bJ=1X≥01.线性规划问题及其数学模型•一般形式:矩阵和向量形式：Max(Min)z=CX约束条件：AX≤(=,≥)bX≥0A称为系数矩阵1.线性规划问题及其数学模型•标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥01.线性规划问题及其数学模型可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:1.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+…+cnxn则可以令z＝-f，该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-…-cnxn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Minf＝-Maxz1.线性规划问题及其数学模型２、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的变量xs，使它等于约束右边与左边之差xs=bi–(ai1x1+ai2x2+…+ainxn)显然，xs也具有非负约束，即xs≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+xs=biXs称为松弛变量。１.线性规划问题及其数学模型当约束条件为ai1x1+ai2x2+…+ainxn≥bi时，类似地令xs=(ai1x1+ai2x2+…+ainxn)-bi显然，xs也具有非负约束，即xs≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-xs=bixs称为剩余变量。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量（剩余变量）。在实际问题中,松弛变量表示未被充分利用的资源数、剩余变量表示超出的资源数,均未转化为价值或利润,所以引进模型后,它们在目标函数中的系数均为0。１.线性规划问题及其数学模型３.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj’-xj”其中xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，４．右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn=-bi。１.线性规划问题及其数学模型例2.3：将以下线性规划问题转化为标准形式Minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58x1,x3,x4≥01.线性规划问题及其数学模型Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7=58x1,x2’,x2”,x3,x4,x5,x6,x7≥0１.线性规划问题及其数学模型２．线性规划的图解法线性规划的图解法(解的几何表示)对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：(1)分别取决策变量x1,x2为坐标向量建立直角坐标系。２．线性规划的图解法（2）图示约束条件，得到可行域。对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面交出来的区域(存在或不存在），若存在，其中的点表示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。然后进行（3）否则该线性规划问题无可行解。２．线性规划的图解法（３）图示目标函数直线，求出最优解。任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置（有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。２．线性规划的图解法例2.4:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）150025002、线性规划的图解法图解法求解线性规划２．线性规划的图解法任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点(5,25)T，此目标函数的值为70000。于是，我们得到这个线性规划的最优x1=5,x2=25最优值z=70000。即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。２.线性规划的图解法线性规划问题求解的几种结局：１，唯一最优解：２，无穷多最优解：3，无界解4，无可行解3.图解法的灵敏度分析所谓灵敏度分析就是在建立数学模型和求得最优解之后，研究线性规划的一些系数cj、aij、bi变化时，对最优解产生什么影响。书上P11例1:某工厂在计划期内要安排I和II两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原料的消耗，以及资源的限制，如表所示。该厂每产生一件I产品可获利50元，每生产一件II产品可获利100元，如何生产可获得最大的总利润？III资源限制设备11300台时原料A21400千克原料B01250千克3.图解法的灵敏度分析解：目标函数Maxz=50x1+100x2约束条件s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0z=0=50x1+100x2x2x1z=27500=50x1+100x2z=20000=50x1+100x2z=10000=50x1+100x2ABCDE当等值线走到顶点B时，获得取优解B点，此时B点坐标（50，250）为最优解，即x1=50，x2=250，此时的z=27500，为最优值。3.图解法的灵敏度分析（一）目标函数中的系数cj的灵敏度分析以上例为例，看一下目标函数cj中变化时，会对最优解产生什么影响？目标函数Maxz=50x1+100x2约束条件s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥03.图解法的灵敏度分析（一）目标函数中的系数cj的灵敏度分析由图可知，如果cj发生变化，则目标函数的等值线的斜率会发生变化。如果要求最优解仍在B点，则会以B点为轴点而发生转动。x2x1z=27500=50x1+100x2ABCDEk=0k=-c1/c2k=-2k=-13.图解法的灵敏度分析（二）约束条件中右边系数bj的灵敏度分析仍以上例为例，设设备台时数增加了10个台时，即约束条件x1+x2≤300变为x1+x2≤310，则最优解和最优值为多少？如图，如果约束条件发生变化，则可行域的边界也会发生变化，原来的BC直线变为B’C’直线，因此等值线可以继续向右上方移动，直到B’点，B’点成为新的最优解。此时B’点坐标（60，250），即x1=60，x2=250，此时的z=28000，为最优值。x2x1ABCDEB’C’3.图解法的灵敏度分析（二）约束条件中右边系数bi的灵敏度分析可见，由于增加了10个台时数，使利润增加了500元，可见每个台时数可增加利润50元.像这样在约束条件右边常量增加一个单位而使最优目标函数值得到改进的数量称为这个约束条件的对偶价格。本例中的设备对偶价格为50元/台时。但不是每个约束条件右边常量的变化都会引起目标函数值的变化的。本例中，如果A原料的量增加10千克，也可以使可行域扩大，但对最优解却没有影响，因此原料A的对偶价格为0。3.图解法的灵敏度分析（二）约束条件中右边系数bi的灵敏度分析所以，当约束条件中的松弛变量（剩余变量）不为0时，这个约束条件的对偶价格为0。某一约束条件的对偶价格也仅在一定的范围内有效，当这个约束条件的资源不断取得时，由于受其它约束条件的限制，使得这一资源用不完，即其松弛变量不为0后，导致其对偶价格为0。总结如下：书上P22（1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，变得更大；求最小值时，变得更小。（2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，变得小了；求最小值时，变得大了。（3）如果对偶价格等于0，则其最优目标函数值不变。第三章对偶理论本章考点求出所给线性规划问题的对偶规划的一般形式2、对称形式下对偶问题的一般形式：定义：变量均具有非负约束，约束条件当目标函数求极大时均取“≤”号，求极小时，均取“≥”号。对称形式下原、对偶问题的一般形式：(LP1)Maxz=cx(LP2)Minw=yTbs.t.Ax≤bs.t.ATy≥cx≥0y≥0“Max--≤”“Min--≥”１.线性规划的对偶问题3、非对称形式的原对偶问题关系其对应关系可列表如下：原问题（对偶问题）对偶问题（原问题）A约束系数矩阵其转置b约束条件的右端项向量价值系数向量c价值系数向量约束条件的右端项向量目标函数Maxz=cxMinw=yTb变量n个约束条件n个变量≥0约束条件≥变量≤0约束条件≤变量无约束约束条件=约束条件m个变量m个约束条件≤变量≥0约束条件≥变量≤0约束条件=变量无约束１.线性规划的对偶问题第四章运输问题第四章运输问题本章考点•画出运输问题的产销平衡的标准运价表•表上作业法求最优方案第五章.整数规划第五章整数规划本章考点•建立整数规划的数学模型第六章图与网络分析第六章图与网络分析•求最小支撑树•求最短路和最短路长•求网络系统的最大流本章考点2.树三.最小支撑树问题定义:设G=（V，E）是一个连通图，G的每一条[vi,vj]对应一个非负的权l(e),一个支撑树上所有边的权的和为支撑树的权.具有最小权的生成树称为G的最小支撑树（最小树）。算法1（Kruskal算法）：类似“避圈法”。每步从未选的边中选取边e,使它与已选边不构成圈，且e为未选边中的最小权边，直到选够n-1条为止。42.树算法2（破圈法）：a.从图G中任选一个圈；b.在所找的圈中去掉一条权数最大的边;c.如果余下的图已不含圈,则计算结束,所余下的图即为最小生成树.3.最短路径问题一般意义下的最短路问题:设G==（V，E），图中每边（vi,vj）有权lij(lij=∞表示vi,vj间无边），vs,vt为图中任意两点，求一条道路u,使它是从vs到vt的所有路中总权最小的路（最短路）。即L(u)=∑lij最小。（vi,vj）∈u3.最短路径问题二.Dijkstra算法标号法步骤：（1）给vs以P标号，P(vs)=0,其余各点均给T标号，T(vi)=+∞.(2)若点vi为刚得到P标号的点，考虑这样的点vj：（vi,