《MBA学位课程-运筹学二)》由会员分享，可在线阅读，更多相关《MBA学位课程-运筹学二)（140页珍藏版）》请在金锄头文库上搜索。
1、1,解：这是一个产销平衡的运输问题， 设Xij表示从Ai调运产品到Bj的数量（吨），其数学模型是：,2,一、产销平衡的运输问题及其解法,1.产销平衡的运输问题的数学模型及其特点 ：,特点：（1）其系数矩阵的结构疏松，且每一列向量 Pij=(0,1,1,0)T=ei+em+j 可以证明，r(A)=m+n1。即有m+n1个独立方程。 于是，该LP问题有且仅有m+n1个基变量。,3,（2） （产销平衡条件）,（3）因为 , 故必有可行解和最优解。,由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大大增加，故用特殊解法表上作业法。 2.表上作业法 表上作业法实质上还是单纯形法，但具体计算和术
2、语上有所不同。其计算步骤和方法，我们通过对引例的求解过程说明之。 （1）用最小元素法确定初始方案（即初始基可行解） 切记在产销平衡表上必须且只能填写m+n1个数字格,4,例18（P37）设某产品从产地A1，A2，A3运往销地B1，B2，B3，B4，B5，运量和单位运价如下表所示，问如何调运才能使总的运费最少？,解：用最小元素法或伏格尔法求得其初始调运方案如下：,5,接下来我们就要判别这个调运方案是否是最优调运方案？ 判别的方法同线性规划一样，首先求出空格的检验数，由于是最小化问题，所以当所有空格的检验数均小于0时得到的解为最优解。 求运输问题的空格的检验数的方法有闭回路法和位势法。,6,（2）
3、用闭回路法或位势法求空格的检验数 1) 用闭回路法求检验数： 首先，每一个空格有且仅有一个闭回路，而圈格无闭回路。 闭回路是以空格为起点，沿同一行或同一列前进，遇上圈格可转90度继续前进，按此方法进行下去，直到回到始点的一个封闭折线。 以始点为第0个点，依次给闭回路上的每一个顶点编号。其中奇序数对应的为奇顶点，偶数对应的为偶顶点。 其次，每一个空格的检验数=奇顶点运费之和 偶顶点运费之和。,7,2)用位势法求出空格的检验数并进行最优解的判别 设u1,u2,um; v1,v2,vn是对应运输问题m+n个约束条件的对偶变量，B为含有人工变量的初始可行基，由LP问题的对偶理论知：CBB-1=(u1,
4、u2,um; v1,v2,vn) 而每个决策变量Xij相应的系数向量Pij=ei+em+j，所以CBB-1Pij=ui+vj， 于是，检验数ij=CBB-1PijCij =(ui+vj)Cij 又各基变量的检验数为0，故对每个基变量所在的圈格的检验数有,即有方程组：,共m+n个未知数 s=m+n1个方程,8,显然上述方程有解，且由于含有一个自由变量，因此，令任一未知数为0，就可求出上述方程组的解(ui1,ui2,uim,vj1,vj2,vjn)称为位势解。 如用位势法求引例初始基可行解的检验数：,9,第一步：将运价表中增加vj和ui列。 第二步：利用圈格分别算出ui和vj，即 令u1=0，然后
5、按ui+vj=Cij (i,jJB)，相继确定ui，vj的值。 第三步：按ij= (ui+vj)Cij (i,jJN)算出表中各空格（即非基变量）的检验数： 由于运输问题的目标函数是求最小化，故判别最优解的准则是所有的非基变量的检验数：ij=CBB-1PijCij0 因为25 =+4， 32 =+1， 34 =+2均为正数，所以目前尚未得到最优解（其实只要有一个正检验数，所对应的方案就不是最优方案），尚须改进。,方案的调整（即换基迭代）是在闭回路上进行,10,3）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的调运方案） i) 确定进基变量：自上而下，自左向右第一个正检验数相应的非基变
6、量（空格）为进基变量。 ii) 作闭回路：以进基变量空格为出发点，用水平或垂直线向前划，当碰到某一恰当数格转90后，继续前进，直至回到起始空格止。 iii) 确定调整量=min奇顶点的调运量（即闭回路上奇顶点运量的最小值为调整量） iv) 在闭回路上进行调整：对闭回路上每个奇顶点的调运量，对闭回路上每个偶顶点（含起始格）的调运量+。调整后，将闭回路中为0的一个数格作为空格（即出基变量）。闭回路外的各调运量不变。这样便得到新的调运方案（新基可行解),11,20,12,4）表上作业法须注意的问题： i) 在最终调运表中，若有某个空格（非基变量）的检验数为0时，则表明该运输问题有多重调运方案； ii
7、) 在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列（绝对不能同时把行、列划去，否则就不满足圈格=m+n1个的要求，即基变量的个数永远要保持为m+n1个）； iii) 在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格=m+n1个的需要。 iv) 用最小元素法所得到的初始方案可以不唯一。,13,二、产销不平衡的运输问题及其求解方法,1.数学模型：,产大于销,销大于产,14,然后再用产销平衡的运输问题的解法进行解之。,2.解法思路： 将不平衡运输问题转化为平衡运输问题。即当 时，考虑在平衡表中增加一虚
8、拟列，表示增加一个销货点 (j=n+1)如仓库，其销货量为 ，且各运价 Cin+1=0；当 时，考虑在平衡表中增加一虚拟 行，表示增加一个新产地，且各运价Cm+1j=0。,15,例题19（P45） 三个电视机厂供应四个地区某种型号的电视机，其运价表如下，试求总运费最少的调运方案？,例18 下表是一个运输问题的单位运价表。,比较总产量和总销量可知，这是一个非平衡运输问题（属于产大于销的情况），为化为平衡运输问题，需虚设一个销点B5，其运价为0，其销量为40。,16,化为产销平衡的运输问题有：,17,三、转运问题及其解法,1.所谓转运问题是在以下背景产生的： (1)每个工厂生产的产品不直接运到销地
9、，可以几个产地集中一起运。 (2)运往各销地的物资可先运给其中的几个销地，再转运给其它销地。 (3)除产、销地之外，还可以有几个中间转运站，在产地之间，销地之间或产销地之间转运。 凡类似上述情况下的调运物资并使总运费最小的问题统称为转运问题。 2.求解“转运问题”的思路是把问题中所有的产地、中转站和销地都既看作产地，又都看作销地，把“转运问题”变成扩大后的产销平衡的运输问题处理。,18,3.求解“转运问题”的方法步骤： (1)建立扩大的产销平衡运输问题单位运价表。其中 1)对两地不能直接运输的单位运价定为M（很大的正数）,3)对产量列的各数据可按下式计算并填入： Ai的产量=ai+,Tj产量=
10、，Bj的产量= 4)对销量行的各数据可按下式计算并填入： Aj的产量=,Tj销量=，Bj的销量=+bj (2)用表上作业法进行求解,2)对所有中转站Tj的产量和销量定为相等，设定为,19,例26（P61）已知甲、乙两处分别有100吨和85吨同种物质外运，A、B、C三处各需物质55，60，70（吨），物质可以直接运到目的地，也可以经某些中转点转运，已知各处之间的距离如下表所示，试确定一个最优的调运方案。,再用表上作业法进行求解。,20,2.7 线性目标规划及其解法,前面的线性规划问题都是处理单个目标的情况，但是在现实世界中有许多问题具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，有的目
11、标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源，又不希望超越资源限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论线性目标规划问题。 1、目标规划模型的建立,21,现在工厂领导要考虑市场等一系列其他因素，提出如下目标： （1）根据市场信息，甲产品的销量有下降的趋势，而乙产品的销量有上升的趋势，故考虑乙产品的产量应大于甲产品的产量。 （2）尽可能充分利用工时，不希望加班。 （3）应尽可能达到并超过计划利润30元。 现在的问题
12、是：在原材料不能超计划使用的前提下，如何安排生产才能使上述目标依次实现？,22,解：（1）决策变量：仍设每天生产甲、乙两种产品各为x1和x2 偏差变量：对于每一目标，我们引进正、负偏差变量。 如对于目标1，设d1-表示乙产品的产量低于甲产品产量的数，d1+表示乙产品的产量高于甲产品产量的数。称它们分别为产量比较的负偏差变量和正偏差变量。则对于目标1，可将它表示为等式约束的形式 -x1+x2+ d1- d1+ =0 (目标约束) 同样设d2-和d2+分别表示安排生产时，低于可利用工时和高于可利用工时，即加班工时的偏差变量，则对目标2，有 -3x1+2x2+ d2-d2+ =26 对于目标3，设d
13、3-和d3+分别表示安排生产时，低于计划利润30元和高于计划利润30元的偏差变量，有：,23,4x1+3x2+ d3-d3+ =30 （2）约束条件：有资源约束和目标约束 资源约束：2x1+3x224 目标约束：为上述各目标中得出的约束 （3）目标函数：三个目标依次为： minZ1=d1- ，minZ2=d2+d2- ，minZ3=d3-,24,例20（提级加新问题） 某公司的员工工资有四级，根据公司的业务发展情况，准备招收部分新员工，并将部分员工的工资提升一级。该公司的员工工资及提级前后的编制表如下，其中提级后编制是计划编制，允许有变化，其中1级员工中有8%要退休。公司领导的目标如下： （1
14、）提级后在职员工的工资总额不超过550千元； （2）各级员工不要超过定编人数； （3）为调动积极性，各级员工的升级面不少于现有人数的18%； （4）总提级面不大于20%，但尽可能多提； （5）4级不足编制人数可录用新工人。,25,问：应如何拟定一具满意的方案，才能接近上述目标？,解：（1）决策变量：设x1,x2,x3,x4分别表示提升到1，2，3级和新录用的员工数。 偏差变量：为各目标的正、负偏差变量。 （2）约束条件： 1） 提级后在职员工的工资总额不超过550千元； 8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=550,2
15、6,2）各级员工不要超过定编人数 1级有： 10-10 8%+x1+d2-d2+=10 2级有： 20-x1+ x2+d3-d3+=22 3级有： 40-x2+ x3+d4-d4+=52 4级有： 30-x3+ x4+d5-d5+=30 3）各级员工的升级面不少于现有人数的18% 对2级有： x1+d6-d6+=22 18% 对3级有： x2+d7-d7+=40 18% 对4级有： x3+d8-d8+=30 18% 4）总提级面人数不大于20%，但尽可能多提 x1+ x2+ x3+d9-d9+=100 20%,27,（3）目标函数： minZ1=d1+ minZ2=d2+d3+ d4+ d5+
16、 minZ3=d6-+ d7-+ d8- minZ4=d9+ d9- 目标规划的一般模型见书本P48,二、目标规划的解法 由于目标规划有多个目标，各个目标又有相对不同的重要性，求解时是首先满足重要性权数大的目标，再满足重要性权数次大的目标，所以并不能保证所有的目标都能达到，所求的解也不一定是最优解，而只能求出满意解。,28,求解目标规划有图解法和单纯形法，在这里我们主要介绍单纯形法。 求解目标规划的单纯形法与线性规划的单纯形法原理基本一致，只是此时检验数行不再是一行，而是变化为一个检验数矩阵。,解：取x3，d1-，d2-，d3-为基变量，建立初始单纯形表,29,迭代的步骤完全与线性规划的单纯形法一样。 满意解的判定：检验数矩阵的每一列从上至下第一个非零元为负数，则解为满意解。迭代的最优表如下：,30,因而满意解为：x1=24/5，
