运筹学模型.doc

第四章 运筹学模型本章教学重点是： 线性规划模型 目标规划模型 运输模型及其应用 图论模型 最小树问题 最短路问题 最大流问题与最小割 复习要求1进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵。2进一步理解数学模型的作用与特点。 本章复习重点是线性规划模型、运输问题模型和目标规划模型。具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单。运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单。你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求。目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型。这是主要的考虑方向。另外，关于图模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型。这之前恐怕要善于将一个实际问题转化为图模型。还有一个最小数的问题，该如何把一个网络中的最小数找到。另外在个别场合可能会涉及一笔划问题。 1营养配餐问题的数学模型为或更简洁地表为 其中的常数C表示第j种食品的市场价格，a表示第j种食品含第i种营养的数量，b表示人或动物对第i种营养的最低需求量.例1 医院为病人配制营养餐，要求每餐中含有铁不低于50单位，蛋白质不低于40单位，钙不低于42单位假设仅有两种食品A和B可供配餐，相关数据见下表试问，如何购买两种食品进行搭配，才能即使病人所需营养达到需求，又使总花费最低？ 食品营养含量A B（单位）铁蛋白质钙10 55 86 5（mg）(g)(mg)价格4 3(元/kg)解：设购买食品A和B依次为x1和x2（kg），则有营养最低要求满足：10x1+5x250 （铁含量） 5x1+8x240 （蛋白质含量）6x1+5x242 （钙含量）总花费数记为Z，则有数学模型 s.t.用图解法求解上述问题首先以x1,x2为坐标轴，建立平面直角坐标系（如图3-10），由于x1,x2均非负，故只画出了第一象限x1x2ABCDOx1x2ABCDO其次，将其余约束条件几何化条件（3.1）表示的是一个半平面，先画出直线10x1+5x2=50,因为10x1+5x250，故直线（3.1）的上方区域即条件（3.1）所满足的x1,x2的取值范围；同理将条件（3.2）、（4.3）也几何化，并注意到几个条件要同时满足，便求得一个以顶点A、B、C、D为顶点的右上方无界的五边形区域ABCD.这个区域内的任一点（x1,x2）都是一个可行性配餐方案 图310 图311最后，为了求出最优解，将目标函数也进行几何化，有称为目标函数直线族，因为其中的Z作为参数出现.易见，随着Z的逐渐增大，目标函数直线（3.4）向右上方平行移动也就是说，随着目标函数直线的逐渐往右上方平移，Z的值越来越大，反之，Z的值越来越小（如图3-11）.又原问题是求函数Z的最小值，故应令目标函数直线尽可能往左下方平移但这种平移是有限制的，即点（x1,x2）必须在可行域内.于是两者的结合便可确定本例的最优解.通过上述斜率关系分析可知目标函数直线与直线（3.1）和直线（3.3）的交点（顶点C）相切，即直线（3.1）与直线（3.3）的交点即最优解点.于是问题就变成了求解方程组易解得x1=2,x2=6为最优解，通常记作：对应的目标函数值称为最优值，记作 Z*=26 2运输问题模型运输问题也是一种线性规划问题，只是决策变量设置为双下标变量. 假如问题具有m个产地和n个销地, 第i个产地用Ai表示,其产量为ai(i=1,2,，m)，第j个销地用Bj表示,其销量为bj(j=1,2,n), 从Ai运往Bj的运价为cij, 而表示产销平衡。那么产销平衡运输问题的一般模型可以写成为 例2 某公司经营的一种产品拥有四个客户，由公司所辖三个工厂生产，每月产量分别为3000，5000，4000件。该公司已承诺下月出售4000件给客户1，出售3000件给客户2以及至少1000件给客户3。客户3与客户4都想尽可能多购剩下的产品。已知各工厂运销一件产品给客户1、2、3、4可得到的净利润是：工厂1为65、63、62、64元；工厂2为68、67、65、62元；工厂3为63、60、59、60元。问该公司应如何拟订运销方案，才能在履行诺言的前提下获利最多？ 上述问题是否可以转化为运输模型加以处理？若是，请写出对应的表格形式的运输模型（即产销平衡运价表），否则说明理由。解：可以。产销平衡表如下： 表41 产销平衡表 客户工厂12334产量165636262643000268676565625000363605959604000虚-M-M-M004000销量40003000100040004000 例3 设有一批产品要从三个生产地A1、A2和A3运往四个销售地B1、B2、B3和B4（生产地和销售地以后简称为产地和销地）。三个产地运往四个销地的运价，三个产地的产量和四个销地的需求量如下表所示，试策划一个运输方案，使得在满足需求条件下，总运输费用最少。 表4-2 产销平衡运价表 单位：拾元/吨销 地 运 价产 地B1 B2 B3 B4产量A1A2A33 11 3 101 9 2 87 4 10 5749销量3 6 5 6 2020解：以xij表示从第i个产地运送到第j个销地的运量,则依供需关系有下列约束条件:供给方面: 需求方面: 非负性: xij0 总运费: 将上述目标函数与约束条件合在一起便构成所谓具有三个产地和四个销地的产销平衡运输问题的数学模型. 下面用表上作业法求解。首先，用最小元素法确定初始方案。表43 单位:拾元/吨 销地运价产地B1 B2 B3 B4产量A13 11 3 107A21 9 2 84A37 4 10 59销量3 6 5 6如表45所示的运价中,由于1最小,于是决定由A2供应B1，于是第一个基变量被确定为.再看供求关系,B1需要3吨,而A2产量为4吨,于是尽量满足需求,由A2供应B13吨.在运价1的右下角写上.由于B1的需求已满足,故A1,A3不必再向B1供应,于是在运价3与7右下角打,表示变量x11与x31被确定为非基变量.在剩下的9个运价中再找最小运价为2,并按上述方法确定第二个基变量x23=1，同时变量x22与x24被确定为非基变量.依此类推，便可确定4个基变量和6个非基变量如表44 表4 销地运价产地B1 B2 B3 B4产量A13 11 3 107A21 9 2 84A37 4 10 59销量3 6 5 6此时，只有两个变量x14和x34未被确定，但它们必须成为基变量.于是根据产销平衡关系确定10下画，5下画.终于得到初始基变量组及其取值为:x13=4, x14=3, x21=3, x23=1, x32=6, x34=3, 其余xij=0即为初始运输方案(表48),其总运费也在表上计算为Z(0)=34+103+13+21+46+53=86(拾元) 表5 销地运价产地B1 B2 B3 B4产量A13 11 3 107A21 9 2 84A37 4 10 59销量3 6 5 6其次，方案的最优性检验闭回路法检验一个方案的最优性说到底是看此方案是否还有改进的余地.而方案是否有改进余地，关键是看非基变量中是否有能转变为基变量（取值大于零）而使目标值进一步改善，若有，则称这个变量为进基变量. 如x11增加1, 按照产销平衡原则, x13必须减值为3, 否则与产量为7矛盾.而当x13减值为3时, x23必须增值一个单位, 否则又与销量为5矛盾, 依此又知, x21需减少一个单位.以上变化导至总运费发生的变化值为11=3+2=10这就是说,令x11变为基变量,总运费将增加1个单位,故此举不合适。由此可知,11具有检验x11进基是否能改善目标值的作用,称为非基变量x11的检验数.如果非基变量的检验数大于零,则该变量进基不合适;若检验数等于零, 则该变量进基也无助于目标值的改进.由此可推出:若所有非基变量的检验数均0, 则目前这个方案便没有改进的余地, 即已是最优方案.反之,若至少有一个非基变量的检验数0, 则目前的方案便非最优方案.这就是运输问题的方案最优性检验原理.值得注意的是,在求非基变量x11的检验数时,恰好是在不存在闭回路的基变量组内引进一个非基变量后所形成的唯一闭回路中进行的相应运算:以进基变量为第一个顶点,按逆时针(或顺时针)将闭回路的奇数顶点运价赋以“+”号,偶数顶点运价赋以“”号所形成的代数和便是该变量的检验数.按此法则,可求得所有非基变量的检验数如下:11=3+210, 12=1110+54022=92+310+50,24=10+031=75+103+210, 33=105+1030由于140,故初始方案非最优方案.然后，用闭回路法调整方案由240,故令x24进基,按产销平衡原则在相应的闭回路上进行调整.注意到基变量总数量m+n-1个,则应令原基变量组成员之一出基(取值为0).易见,令x24=min该闭回路上偶数顶点运量=1,3=1,便知新基变量x24取值为1,被保留下来的基变量为x13=4+1=5,x14=31=2,x21=3,x32=6,x34=3,其余为非基变量,其中x23=11=0为新增非基变量.重新画一张表49,标上新基变量及其取值,便得新运输方案表,总运费为z=35+102+13+81+46+53=85(拾元).那么这个方案是否最优方案?返回2)步再检验即可.表6 销地产地B1 B2 B3 B4产量A13 11 3 107A21 9 2 84A37 4 10 59销量3 6 5 6现求新方案中非基变量的检验数:11=310+81=0, 12=1110+540,22=98+50, 31=71+850,33=105+1030, 23=28+1030,可见所有ij0,故表49所给方案已是最优方案, 用运销图画在下面:2B35B431B1B463B2B4A1 A2 A3 图4-13目标规划模型 例4 某工厂生产两种产品A、B分两班生产，每周生产总时间为80小时，两种产品的预测销售量、生产率和赢利如下表产品预测售量（万件/周）生产率（件/小时）单位利润（元/件）A710000.15B4.510000.3制定一合理的生产方案，要求依次满足下列目标： （1）充分利用现有能力，避免设备闲置； （2）周加班时间限制在10小时以内； （3）两种产品周生产品量应满足预测销售，满足程度的权重之比等于它们单位利润之比； （4）尽量减少加班时间 解： （1）建立模型 设：每班上班时间为8小时，在上班时间内只能生产一种产品； 周末加班时间内生产哪种产品不限； 生产A产品用x班，生产B产品用y班，周加班时生产A产品用x1小时，生产B产品用y1小时则有 （2）求解 现在求满足（1）中第2，3个方程可看出：，； 将（1）中的第1个方程代入第4个方程得：现在就是在满足，条件下，使上式两端的取值尽量接近显然， 因此 制定方案为，生产A，B两种产品所占总时间各一半，周加班10小时全用于生产产品B4最短路问题的数学模型许多实际问题都归结为最短路问题，例如两地间的管道铺设，线路安装，道路修筑，运路选取等等；再如工厂布局，设备更新等问题也可转化为最短路问题。最短路问题一般描述如下：在一个图（或者说网络）中，给定一个始点vs和一个终点vt，求vs到vt的一条路，使路长最短（即路的各边权数之和最小）。这里介绍求最短路的常用算法：狄克斯屈（E.D.Dijkstra）双标号法该法是狄克斯屈在1959年提出的，适用于所有权数均为非负（即一切, wij表示顶点vi与vj的边的权数）的网络，能够求出网络的任一点vs到其它各点的最短路，为目前求这类网络最短路的最好算法。该法在施行中，对每一个点vj都要赋予一个标号，并分为固定标号P（vj）和临时标号T（vj）两种，其含义如下：P（vj）从始点vs到vj的最短路长；T（vj）从始点vs到vj的最短路长上界。一个点vj的标号只能是上述两种标号之一。若为T标号，则需视情况修改，而一旦成为P标号，就固定不变了。开始先给始点vs标上P标号0，然后检查点vs，对其一切关联边（vs, vj）的终点vj，给出vj的T标号wij；再在网络的已有T标号中选取最小者，把它改为P标号。以后每次都检查刚得到P标号那点，按一定规则修改其一切关联边终点的T标号，再在网络的所有T标号中选取最小者并把它改为P标号。这样，每次都把一个T标号点改为P标号点，因为网络中总共有n个结点，故最多只需n-1次就能把终点vt改为P标号。这意味着已求得了vs到vt的最短路。狄克斯屈标号法的计算步骤如下：1 令S=vs为固定标号点集，为临时标号点集，再令2检查点vi，对其一切关联边（vi, vj）的终点,计算并令3从一切中选取并令选取相应的弧（vi, vr）。再令4若，则停止，即vs到vj的最短路长，特别即vs到vt的最短路长，而已选出的弧即给出vs到各点的最短路；否则令，返2。注意：若只要求vs到某一点vt的最短路，而没要求vs到其他各点的最短路，则上述步骤4可改为4若r=t则结束，即为所求最短路长；否则令，返2.例5 设有七个单位要求煤气公司为其铺设煤气管道，经施工单位测量，七个单位间可通管道的路线长度如表47所示.其中单位A距煤气公司供应网最近，为1.5km.现拟铺设地下管道，并经A与供应网连通，铺设费用为25元/m，试协助施工单位进行施工路线设计，使得费用最少，求出最小费用值.表47 单位:km j 距 离IA B C D E F GABCDEFG0 3 4 7 3