MBA学位课程-运筹学2(1)

1§2.6运输问题及其解法引例：某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A1-40吨，A2-40吨，A3-90吨。该公司把这些产品分别运往四个销售点，各销售点每日销量为：B1-30吨，B2-40吨，B3-60吨，B4-20吨,B5-20吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少销地产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）30406020202解：这是一个产销平衡的运输问题，设Xij表示从Ai调运产品到Bj的数量（吨），其数学模型是：0X20XXX20XXX60XXX40XXX30XXX90XXXXX40XXXXX40XXXXX.t.sXCzminij35251534241433231332221222211135343332312524232221151413121131i51jijij3一、产销平衡的运输问题及其解法1.产销平衡的运输问题的数学模型及其特点：minjijijXCZ11min)n,...,1j,m,...,1i(0X)m,...,2,1i(aX)n,...,2,1j(bXijn1jiijm1ijij特点：（1）其系数矩阵的结构疏松，且每一列向量Pij=(0,…1,…1,…0)T=ei+em+j可以证明，r(A)=m+n－1。即有m+n－1个独立方程。于是，该LP问题有且仅有m+n－1个基变量。4（2）（产销平衡条件）minjjiba11（3）因为,故必有可行解和最优解。minjijijXCMinZ110由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大大增加，故用特殊解法──表上作业法。2.表上作业法表上作业法实质上还是单纯形法，但具体计算和术语上有所不同。其计算步骤和方法，我们通过对引例的求解过程说明之。（1）用最小元素法确定初始方案（即初始基可行解）切记在产销平衡表上必须且只能填写m+n－1个数字格5例18（P37）设某产品从产地A1，A2，A3运往销地B1，B2，B3，B4，B5，运量和单位运价如下表所示，问如何调运才能使总的运费最少？销地运价产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）3040602020解：用最小元素法或伏格尔法求得其初始调运方案如下：6销地运价产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）3040602020304060202000接下来我们就要判别这个调运方案是否是最优调运方案？判别的方法同线性规划一样，首先求出空格的检验数，由于是最小化问题，所以当所有空格的检验数均小于0时得到的解为最优解。求运输问题的空格的检验数的方法有闭回路法和位势法。7（2）用闭回路法或位势法求空格的检验数1)用闭回路法求检验数：首先，每一个空格有且仅有一个闭回路，而圈格无闭回路。闭回路是以空格为起点，沿同一行或同一列前进，遇上圈格可转90度继续前进，按此方法进行下去，直到回到始点的一个封闭折线。以始点为第0个点，依次给闭回路上的每一个顶点编号。其中奇序数对应的为奇顶点，偶数对应的为偶顶点。其次，每一个空格的检验数=奇顶点运费之和–偶顶点运费之和。82)用位势法求出空格的检验数并进行最优解的判别设u1,u2,…um;v1,v2,…,vn是对应运输问题m+n个约束条件的对偶变量，B为含有人工变量的初始可行基，由LP问题的对偶理论知：CBB-1=(u1,u2,…um;v1,v2,…,vn)而每个决策变量Xij相应的系数向量Pij=ei+em+j，所以CBB-1Pij=ui+vj，于是，检验数σij=CBB-1Pij－Cij=(ui+vj)－Cij又各基变量的检验数为0，故对每个基变量所在的圈格的检验数有即有方程组：isjsjsisjijijijiCvuCvuCvu:22221111共m+n个未知数s=m+n－1个方程Cvuijji)(09显然上述方程有解，且由于含有一个自由变量，因此，令任一未知数为0，就可求出上述方程组的解(ui1,ui2,…uim,vj1,vj2,…vjn)──称为位势解。如用位势法求引例初始基可行解的检验数：销地运价产地B1B2B3B4B5vjA17108646A259712612A336581110ui-7-3-50-2-8-7-70412-330406020200010第一步：将运价表中增加vj和ui列。第二步：利用圈格分别算出ui和vj，即令u1=0，然后按ui+vj=Cij(i,jJB)，相继确定ui，vj的值。第三步：按σij=(ui+vj)－Cij(i,jJN)算出表中各空格（即非基变量）的检验数：由于运输问题的目标函数是求最小化，故判别最优解的准则是所有的非基变量的检验数：σij=CBB-1Pij－Cij≤0因为σ25=+4，σ32=+1，σ34=+2均为正数，所以目前尚未得到最优解（其实只要有一个正检验数，所对应的方案就不是最优方案），尚须改进。方案的调整（即换基迭代）是在闭回路上进行113）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的调运方案）i)确定进基变量：自上而下，自左向右第一个正检验数相应的非基变量（空格）为进基变量。ii)作闭回路：以进基变量空格为出发点，用水平或垂直线向前划，当碰到某一恰当数格转90后，继续前进，直至回到起始空格止。iii)确定调整量=min{奇顶点的调运量}（即闭回路上奇顶点运量的最小值为调整量）iv)在闭回路上进行调整：对闭回路上每个奇顶点的调运量－，对闭回路上每个偶顶点（含起始格）的调运量+。调整后，将闭回路中为0的一个数格作为空格（即出基变量）。闭回路外的各调运量不变。这样便得到新的调运方案（新基可行解)12销地运价产地B1B2B3B4B5产量（万吨）A171086+04-040A259712-06+040A336581190销量（万吨）304060202020B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）3040602020200040306020306040020200134）表上作业法须注意的问题：i)在最终调运表中，若有某个空格（非基变量）的检验数为0时，则表明该运输问题有多重调运方案；ii)在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列（绝对不能同时把行、列划去，否则就不满足圈格=m+n－1个的要求，即基变量的个数永远要保持为m+n－1个）；iii)在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格=m+n－1个的需要。iv)用最小元素法所得到的初始方案可以不唯一。14二、产销不平衡的运输问题及其求解方法1.数学模型：minjjiijXCZ11min),...,2,1,,...,2,1(0),...,2,1(),...,2,1(11njmiXnjbXmiaXijmijijnjiijminjjiijXC11min),...,2,1,,...,2,1(0),...,2,1(),...,2,1(11njmiXnjbXmiaXijmijijnjiijnjjmiiba11产大于销njjmiiba11销大于产15然后再用产销平衡的运输问题的解法进行解之。2.解法思路：将不平衡运输问题转化为平衡运输问题。即当时，考虑在平衡表中增加一虚拟列，表示增加一个销货点(j=n+1)如仓库，其销货量为，且各运价Cin+1=0；当时，考虑在平衡表中增加一虚拟行，表示增加一个新产地，且各运价Cm+1j=0。njjmiiba11njjmiiba11njjmiiba1116例题19（P45）三个电视机厂供应四个地区某种型号的电视机，其运价表如下，试求总运费最少的调运方案？例18下表是一个运输问题的单位运价表。B1B2B3B4产量（万吨）A11035650A221131270A3781870销量（万吨）20304060比较总产量和总销量可知，这是一个非平衡运输问题（属于产大于销的情况），为化为平衡运输问题，需虚设一个销点B5，其运价为0，其销量为40。B50004017销地厂家B1B2B3B4产量（万台）A16312610A2439—12A3910131010最低需求61405最高需求10146不限(12)销地厂家B1B1`B2B3B4B4`产量（万台）A1663126610A24439MM12A3991013101010A4M0M0M1010销量6414657化为产销平衡的运输问题有：18三、转运问题及其解法1.所谓转运问题是在以下背景产生的：(1)每个工厂生产的产品不直接运到销地，可以几个产地集中一起运。(2)运往各销地的物资可先运给其中的几个销地，再转运给其它销地。(3)除产、销地之外，还可以有几个中间转运站，在产地之间，销地之间或产销地之间转运。凡类似上述情况下的调运物资并使总运费最小的问题统称为转运问题。2.求解“转运问题”的思路是把问题中所有的产地、中转站和销地都既看作产地，又都看作销地，把“转运问题”变成扩大后的产销平衡的运输问题处理。193.求解“转运问题”的方法步骤：(1)建立扩大的产销平衡运输问题单位运价表。其中1)对两地不能直接运输的单位运价定为M（很大的正数）3)对产量列的各数据可按下式计算并填入：Ai的产量=ai+,Tj产量=，Bj的产量=4)对销量行的各数据可按下式计算并填入：Aj的产量=,Tj销量=，Bj的销量=+bj(2)用表上作业法进行求解m1in1jji},max{ba2)对所有中转站Tj的产量和销量定为相等，设定为20例26（P61）已知甲、乙两处分别有100吨和85吨同种物质外运，A、B、C三处各需物质55，60，70（吨），物质可以直接运到目的地，也可以经某些中转点转运，已知各处之间的距离如下表所示，试确定一个最优的调运方案。从到甲乙甲乙010120从到ABC甲乙101514121218从到ABCABC0108140121140从到甲乙ABC产量甲乙ABC010MMM120MMM1015010814121401212181140285270185185185销量185185240245255再用表上作业法进行求解。21§2.7线性目标规划及其解法前面的线性规划问题都是处理单个目标的情况，但是在现实世界中有许多问题具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，有的目标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源，又不希望超越资源限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论线性目标规划问题。1、目标规划模型的建立22引例：对于生产计划问题：甲乙资源限额材料2324工时3226单位利润43现在工厂领导要考虑市场等一系列其他因素，提出如下目标：（1）根据市场信息，甲产品的销量有下降的趋势，而乙产品的销量有上升的趋势，故考虑乙产品的产量应大于甲产品的产量。（2）尽可能充分利用工时，不希望加班。（3）应尽可能达到并超过计划利润30元。现在的问题是：在原材料不能超计划使用的前提下，如何安排生产才能使上述目标依次实现？23解：（1）决策