[管理学]管理运筹学 第三版韩伯棠 考点归纳

第二章 线性规划,第二章 线性规划,本章考点,建立线性规划问题的数学模型图解法及灵敏度分析将一般形式的线性规划问题转换成标准形式计算机输出结果的解释,一般形式:目标函数：Max(Min)z = c1x1 + c2x2 + + cnxn约束条件： a11x1+a12x2+a1nxn( =, )b1a21x1+a22x2+a2nxn( =, )b2 am1x1+am2x2 +amnxn( =, )bmx1 ，x2 ， ，xn 0,1.线性规划问题及其数学模型,一般形式:简化： nMax(Min)z = cjxj j=1约束条件： naijxj( =, )bi J=1xj 0(j=1,2,n),1.线性规划问题及其数学模型,一般形式:向量式：Max(Min)z = CX约束条件： n Pjxj( =, )bJ=1X 0,1.线性规划问题及其数学模型,一般形式:矩阵和向量形式：Max(Min)z = CX约束条件：AX ( =, )bX 0A称为系数矩阵,1.线性规划问题及其数学模型,标准形式目标函数：Max z = c1x1 + c2x2 + + cnxn,约束条件：a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,1.线性规划问题及其数学模型,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式: 1.极小化目标函数的问题：设目标函数为 Min f = c1x1 + c2x2 + + cnxn则可以令z -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z,1.线性规划问题及其数学模型,、约束条件不是等式的问题：设约束条件为ai1 x1+ai2 x2+ +ain xn bi可以引进一个新的变量xs，使它等于约束右边与左边之差 xs=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然， xs也具有非负约束，即xs0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+ xs = biXs称为松弛变量。,.线性规划问题及其数学模型,当约束条件为ai1 x1+ai2 x2+ +ain xn bi时，类似地令xs =(ai1 x1+ai2 x2+ +ain xn)- bi 显然， xs也具有非负约束，即xs 0，这时新的约束条件成为ai1 x1+ai2 x2+ +ain xn- xs = bi xs称为剩余变量。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量（剩余变量）。在实际问题中,松弛变量表示未被充分利用的资源数、剩余变量表示超出的资源数,均未转化为价值或利润,所以引进模型后,它们在目标函数中的系数均为0。,.线性规划问题及其数学模型,. 变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi=0，求的一个可行流f=fij,使得流量w(f)=v,且总费用d(f)=dijfij达到最小。 （Vi,Vj）E当f为最大流时，此问题即为网络系统的最小费用最大流问题。,5.网络系统的最小费用流问题,5.网络系统的最小费用流问题,二、最小费用最大流的网络图论解法对网络上弧（vi,vj）的（cij,dij）的表示作如下改动，用(b)来表示(a)。,vi,vj,vi,vj,（cij,dij ）,（0,-dij ）,（a）,（b）,（cij,dij ）,（cij,dij ）,vi,vj,（cji,dji ）,（cij,dij ）,vi,vj,（cji,dji ）,（0,-dji),（0,-dji),（c）,（d）,5.网络系统的最小费用流问题,例7 如图。从采地 v1向销地 v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。,5.网络系统的最小费用流问题,在对弧的标号作了改进的网络图上求最小费用最大流的算法与求最大流的算法完全一样，不同的只是在步骤（1）中要选择一条总的单位费用最小的路.,用上述方法对例7中的图形进行改进，得图如下,5.网络系统的最小费用流问题,用上述方法对例7求解： 第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为1，总费用10。,v5,5.网络系统的最小费用流问题,第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为3，总费用32。,5.网络系统的最小费用流问题,第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后总流量为5，总费用56。,5.网络系统的最小费用流问题,第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后总流量为6，总费用72。,5.网络系统的最小费用流问题,第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后总流量为9，总费用123。,5.网络系统的最小费用流问题,第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后总流量为10，总费用145。已经找不到从v1到v7的每条弧容量都大于零的路了，故已求得最小费用最大流了。,v5,图g,5.网络系统的最小费用流问题,如果对例7求一个最小费用流的问题：每小时运送6万加仑石油从v1到v7的最小费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代及图e即可得到运送6万加仑最小费用72百元，其运送方式通过比较图a及图e即得图i所示。 至于每小时运送7万加仑，我们可以在图i的基础上，再按第五次迭代所选的最短路运送1万加仑即得最小费用：72+1*17=8