搜索
管理运筹学期末总复习09年6月《管理运筹学》线性规划：标准形式图解法单纯形法建模对偶问题形成及定理对偶单纯形法灵敏度分析cj,bi,pij,增加变量，增加约束《管理运筹学》运输问题：表上作业法建模4图与网络基本的概念最优树问题网络最小费用流问题网络最大流问题最短路径问题-Dijkstra算法《管理运筹学》5统筹方法基本概念网络图的画法关键路径网络时间参数的计算概率型网络图网络计划的优化《管理运筹学》6动态规划：基本概念基本求解步骤例题：离散性、连续型《管理运筹学》7决策分析不缺性决策－乐观准则、悲观准则、乐观系数准则、等可能性准则、后悔值准则风险型决策－损益矩阵法、决策树法、Bayes决策、效用值理论系统评价－TheAnalyticHierarchyProcess,AHP《管理运筹学》8对策论矩阵对策的基本概念矩阵对策的解法《管理运筹学》9存储论存储论基本概念－ABC库存管理技术、库存管理中费用分类确定型存储模型－模型推导、四个模型随机型存储模型－离散型（报童问题）《管理运筹学》10《管理运筹学》排队论：模型分类主要指标及计算M/M/1模型M/M/c模型有限源模型优化问题11第二章线性规划建模及单纯形法本章内容重点线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划应用——建模121.线性规划的概念例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）1500250013问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A：两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1+2x2≤65；对设备B：两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1+x2≤40；1.线性规划的概念14对设备C：两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2≤75；另外，产品数不可能为负，即x1,x2≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：1.线性规划的概念15目标函数Maxz=1500x1+2500x2约束条件s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥01.线性规划的概念16这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于…”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。1.线性规划的概念17•一般形式•目标函数：Max(Min)z=c1x1+c2x2+…+cnxn•约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2...am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥01.线性规划的概念18•标准形式•目标函数：Maxz=c1x1+c2x2+…+cnxn•约束条件：A11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥01.线性规划的概念19可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:1.线性规划的概念201.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+…+cnxn则可以令z＝-f，该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-…-cnxn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Minf＝-Maxz1.线性规划的概念212、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的变量s，使它等于约束右边与左边之差s=bi–(ai1x1+ai2x2+…+ainxn)显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi1.线性规划的概念22当约束条件为ai1x1+ai2x2+…+ainxn≥bi时，类似地令s=(ai1x1+ai2x2+…+ainxn)-bi显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-s=bi1.线性规划的概念23为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。1.线性规划的概念24例2.2：将以下线性规划问题转化为标准形式Minf=3.6x1-5.2x2+1.8x3s.t.2.3x1+5.2x2-6.1x3≤15.74.1x1+3.3x3≥8.9x1+x2+x3=38x1,x2,x3≥01.线性规划的概念解：首先,将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8x325其次考虑约束，有2个不等式约束，引进松弛变量x4，x5≥0。于是，我们可以得到以下标准形式的线性规划问题：Maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9x1+x2+x3=38x1,x2,x3,x4,x5≥01.线性规划的概念263.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj’-xj”其中xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。1.线性规划的概念274.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn=-bi1.线性规划的概念28例2.3：将以下线性规划问题转化为标准形式Minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58x1,x3,x4≥01.线性规划的概念29解：首先，将目标函数转换成极大化：令z=-f=3x1–5x2–8x3+7x4；其次考虑约束，有3个不等式约束，引进松弛变量x5,x6,x7≥0；由于x2无非负限制，可令x2=x2’-x2”,其中x2’≥0，x2”≥0；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：1.线性规划的概念30Maxz=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≥01.线性规划的概念312.线性规划的图解法线性规划的图解法(解的几何表示)：对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：322.线性规划的图解法(1)建立直角坐标系：分别取决策变量x1,x2为坐标向量。332.线性规划的图解法（2）绘制可行域：对每个约束（包括非负约束）条件，作出其约束半平面（不等式）或约束直线（等式）。各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。称这个区域为可行集或可行域。然后进行下步。否则若交为空，那么该线性规划问题无可行解。342.线性规划的图解法（3）绘制目标函数等值线，并移动求解：目标函数随着取值不同，为一族相互平行的直线。首先，任意给定目标函数一个值，可作出一条目标函数的等值线（直线）；然后，确定该直线平移使函数值增加的方向；最后，依照目标的要求平移此直线。352.线性规划的图解法结果若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。否则，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。362.线性规划的图解法例2.4:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500372.线性规划的图解法问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据前面分析，可以建立如下的线性规划模型：Maxz=1500x1+2500x2s.t.3x1+2x2≤65(A)2x1+x2≤40(B)3x2≤75(C)x1,x2≥0(D,E)382.线性规划的图解法例题作图（1）按照图解法的步骤：（1）以决策变量x1，x2为坐标向量作平面直角坐标系；392.线性规划的图解法（2）对每个约束（包括非负约束）条件作出直线（A、B、C、D、E），并通过判断确定不等式所决定的半平面。各约束半平面交出来的区域即可行集或可行域如下图阴影所示。402.线性规划的图解法例题作图（2）第2步图示(1)分别作出各约束半平面412.线性规划的图解法例题作图（3）第2步图示(2)各约束半平面的交－可行域422.线性规划的图解法（3）任意给定目标函数一个值（例如37500）作一条目标函数的等值线，并确定该等值线平移后值增加的方向（向上移动函数值增大），平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点(5,25)T，即最优解。此目标函数的值为70000。2.线性规划的图解法例题作图（4）第3步图示作出目标函数等值线函数值增大2.线性规划的图解法例题作图（5）第3步图示(2)求出最优解452.线性规划的图解法根据上面的过程我们得到这个线性规划的最优解x1=5、x2=25，最优值z=70000即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。462.线性规划的图解法线性规划的解有如下几种情况：1、存在有限最优解：唯一最优解；无穷多个最优解2、无有限最优解（无界解）3、无可行解（可行域空）472.线性规划的图解法例2.5：在例2.4的线性规划模型中，如果目标函数变为：Maxz=1500x1+1000x2那么，最优情况下目标函数的等值线与直线（A）重合。这时，最优解有无穷多个，是从点(5,25)T到点(15,10)T线段上的所有点，最优值为32500。如下图所示：482.线性规划的图解法无穷多解的情况(15,10)T492.线性规划的图解法例2.6：在例2.4的线性规划模型中,如果约束条件（A）、（C）变为：3x1+2x2≥65(A’）3x2≥75(C’）并且去掉（D、E）的非负限制。那么，可行域成为一个上无界的区域。这时，没有有限最优解，如下图所示：502.线性规划的图解法无有限解的情况512、线性规划的图解法例2.7：在例2.4的线性规划模型中，如果增加约束条件（F）为：