运筹学总复习(课堂PPT).ppt

China University of Mining and Technology,-,*,-,运筹学,运 筹 学,复 习,求解如下线性规划问题,例,1,复 习,解：加入松弛变量，标准化得,建立单纯形表如下：,复 习,复 习,解毕,复 习,用对偶单纯形法计算,例,2,复 习,解：为了便于寻找初始正则解，将问题变形为：,取,x,4,x,5,为初始正则解，列单纯形表如下：,复 习,-2,-3,-4,0,0,X,B,b,x,1,x,2,x,3,x,4,x,5,x,4,-3,-1,-2,-1,1,0,x,5,-4,-2,1,-3,0,1,0,-2,-3,-4,由于初始正则解有负分量，于是取,min-3,-4=-4,x,5,为换出变量，取,x,1,为换入变量，得新基,x,4,x,1,，,51,=-2,为主元,复 习,基变换的过程：,主元变为,1,，即用,-2,去除单纯形表中基变量,x,5,所在的行；,主元所在列的其它元变为,0,，消去非基变量,x,1,所在的列的其余元,-1,，,-2,；,得新基,x,4,x,1,的单纯形表,-2,-3,-4,0,0,X,B,b,x,1,x,2,x,3,x,4,x,5,x,4,-3,-1,-2,-1,1,0,x,5,-4,-2,1,-3,0,1,0,-2,-3,-4,复 习,基变换的过程：,-2,-3,-4,X,B,b,x,1,x,2,x,3,x,4,x,5,x,4,x,1,-2,-3,-4,0,0,X,B,b,x,1,x,2,x,3,x,4,x,5,x,4,-3,-1,-2,-1,1,0,x,5,-4,-2,1,-3,0,1,0,-2,-3,-4,2,1,-1/2,3/2,0,-1/2,-1,0,-5/2,1/2,1,-1/2,4,0,-4,-1,0,-1,复 习,-2,-3,-4,X,B,b,x,1,x,2,x,3,x,4,x,5,x,4,x,1,2,1,-1/2,3/2,0,-1/2,-1,0,-5/2,1/2,1,-1/2,4,0,-4,-1,0,-1,可见正则解的有负分量，由于,x,4,=1,所以取,x,4,为换,出变量，取,x,2,为换入变量，得新基,x,2,x,1,，,42,=-5/2,为主元,复 习,-2,-3,-4,X,B,b,x,1,x,2,x,3,x,4,x,5,x,2,2/5,0,1,-1/5,-2/5,1/5,x,1,11/5,1,0,7/5,-1/5,-2/5,28/5,0,0,-3/5,-8/5,-1/5,此时正则解是可行解，也是最优解。,X,*=(11/5,，,2/5,，,0,，,0,，,0),；,z,*=-28/5,进行基变换，得新正则解的单纯形表：,复 习,试用对偶原理求解线性规划问题,已知其对偶规划的最优解为,例,3,复 习,解：,该问题的对偶规划为,复 习,利用松紧关系，,代入对偶规划的约束条件得下列约,束是松约束，,将最优解,松约束,紧约束,其对偶约束是紧约束,复 习,设原问题的最优解为,紧约束,复 习,设某种物资有,3,个产地,A,1,，,A,2,，,A,3,，,生产量分别为,9,，,5,，,7;,有,4,个销地,B,1,，,B,2,，,B,3,，,B,4,，销售量分别为,3,，,8,，,4,，,6,;,已知从,A,i,到,B,j,物资的单位运价见下表。求总运费最小的调运方案。,B,1,B,2,B,3,B,4,产量,A,1,2,9,10,7,9,A,2,1,3,4,2,5,A,3,8,4,2,5,7,销量,3,8,4,6,例,4,复 习,存在基变量为,0,的解称为,退化解,。,在确定初始基可行解的过程中，如果某一步中出现情况：当产地,A,i,处的余量与销地,B,j,处的需求量相等时，在格,(,i,j,),填入运量后，产地,A,i,处的余量与销地,B,j,处的销量同时为,0,相应地要划去一行和一列。这时就出现了,退化,。,为了使基变量个数恰好有,m,+,n,-1,个，应在同时划去的一行或一列中的某个格中填入数字,0,，表示这格中的变量是取值为,0,的基变量；,复 习,B,1,B,2,B,3,B,4,a,i,行差,A,1,2,9,10,7,9,A,2,1,3,4,2,5,A,3,8,4,2,5,7,b,j,3,8,4,6,列差,伏格尔法计算,1,用伏格尔法寻找初始基：,先算出运价表中各行与各列的最小运费与次小运费的差额，并填入该运价表的最右列和最下行。,从行差或列差中选出最大者，并选择其所在行或列的最小元素。,A,1,的行差最大，而其中运价,c,11,最小,令,x,11,为优先运输路线。,5,1,2,1,1,2,3,复 习,B,1,B,2,B,3,B,4,a,i,行差,A,1,2,9,10,7,9,5,A,2,1,3,4,2,5,1,A,3,8,4,2,5,7,2,b,j,3,8,4,6,列差,1,1,2,3,0,3,0,3/0,9/6,用伏格尔法寻找初始基：,销地,B,1,的销量,3,全由产地,A,1,供给，所以,x,21,=,x,31,=0,。,将,x,11,=3,填到调运方案表中第,1,行第,1,列上。,画去运输数据表第一列，,A,1,的产量剩余为,9-3=6,。,得到新的产销平衡与单位运价表,.,令,伏格尔法计算,1,复 习,B,1,B,2,B,3,B,4,a,i,行差,A,1,2,9,10,7,9/6,5,A,2,1,3,4,2,5,1,A,3,8,4,2,5,7,2,b,j,3/0,8,4,6,列差,1,1,2,3,0,3,0,6/1,5/0,用伏格尔法寻找初始基：,再算出运价表中的行差与列差。,B,4,的列差最大，而其中运价,c,24,最小,令,x,24,为优先运输路线。,产地,A,2,的产量,2,全供给销地,B,4,，,所以,x,23,=,x,24,=0,。,画去运输数据表中第,2,行，,B,4,的销量还要,6-5=1,。得新表。,5,2,1,1,2,2,1,1,2,2,3,3,0,5,0,令,伏格尔法计算,1,复 习,B,1,B,2,B,3,B,4,a,i,行差,A,1,2,9,10,7,9/6,5,A,2,1,3,4,2,5/0,1,A,3,8,4,2,5,7,2,b,j,3/0,8,4,6/1,列差,1,1,2,3,0,3,0,4/0,7/3,用伏格尔法寻找初始基：,5,2,1,1,2,2,1,1,2,2,3,3,0,5,0,5,2,2,1,1,2,2,2,1,1,5,2,2,8,3,3,2,0,4,伏格尔法计算,1,复 习,B,1,B,2,B,3,B,4,a,i,行差,A,1,2,9,10,7,9/6,5,A,2,1,3,4,2,5/0,1,A,3,8,4,2,5,7/3,2,b,j,3/0,8,4/0,6/1,列差,1,1,2,3,0,3,0,8/5,7/3/0,用伏格尔法寻找初始基：,5,2,1,1,2,2,1,1,2,2,3,3,0,5,0,5,2,2,1,1,2,2,2,1,1,5,2,2,8,3,3,2,0,4,5,2,2,2,1,1,2,2,2,1,1,1,5,5,2,2,8,3,3,2,2,0,3,伏格尔法计算,1,复 习,B,1,B,2,B,3,B,4,a,i,行差,A,1,2,9,10,7,9/6,5,A,2,1,3,4,2,5/0,1,A,3,8,4,2,5,7/3,2,b,j,3/0,8,4/0,6/1,列差,1,1,2,3,0,3,0,8/5,7/3/0,用伏格尔法寻找初始基：,0,5,0,0,4,5,2,2,2,1,1,2,2,2,1,1,1,5,5,2,2,8,3,3,2,2,0,3,现在只有一个产地两个销地，故令,x,12,=5,x,14,=1,为基变量，将其分别填到调运方案表中,1,行,2,列与,1,行,4,列上。,5,1,得到产销平衡运输问题的一个初始方案,伏格尔法计算,1,复 习,B,1,B,2,B,3,B,4,a,i,A,1,2,9,10,7,9,A,2,1,3,4,2,5,A,3,8,4,2,5,7,b,j,3,8,4,6,3,5,4,3,5,1,此方案的运费是,32+59+47+52+34+42=88,。,伏格尔法给出的初始解往往更接近于最优解。,复 习,利用伏格尔法确定的初始解如下表所示：,B,1,B,2,B,3,B,4,a,i,A,1,3,2,5,9,10,1,7,9,A,2,1,3,4,5,2,5,A,3,8,3,4,4,2,5,7,b,j,3,8,4,6,1,、写出,基可行解对应的位势方程组,;,2,、并计算非基变量的检验数。,复 习,求解位势及检验数的过程可在一个特殊设计的表上完成，这个表的构造如下：,在原单位运价表增加一行与一列，在列中填入,u,i,，在行中填入,v,j,；把运价,c,ij,记在每一格的右上角，用框标定，在基变量对应的格中标出,0,，构成表。,复 习,由,u,1,+,v,1,=2,u,1,+,v,2,=9,u,1,+,v,4,=7,得,v,1,=2,v,2,=9,v,4,=7;,B,1,B,2,B,3,B,4,u,i,A,1,0,2,0,9,10,0,7,A,2,1,3,4,0,2,A,3,8,0,4,0,2,5,v,j,0,-5,-5,2,9,7,7,位势表：,再由,u,2,+,v,4,=2,，,u,3,+,v,2,=4,，得,u,2,=-5,，,u,3,=-5;,最后由,u,3,+,v,3,=2,得,v,3,=7.,取,u,1,=0;,复 习,检验数表：,(,计算所有非基变量的检验数,),B,1,B,2,B,3,B,4,u,i,A,1,0,2,0,9,10,0,7,A,2,1,3,4,0,2,A,3,8,0,4,0,2,5,v,j,0,-5,-5,2,9,7,7,(3),(4),(-1),(2),(11),(3),当存在非基变量的检验数,kl,0,，说明现行方案为最优方案，否则目标成本还可以进一步减小。,复 习,伏格尔法的初始方案：,B,1,B,2,B,3,B,4,u,i,A,1,3,2,5,9,10,1,7,0,A,2,1,3,4,5,2,-5,A,3,8,3,4,4,2,5,-5,v,j,2,9,7,7,(3),(4),(-1),(2),(11),(3),x,22,为,换入变量,从,x,22,所在格出发做闭回路,L,L,中有两个偶点,x,24,x,12,，,取,x,12,为,换出变量,，调整量为,5.,复 习,伏格尔法的调整方案：,B,1,B,2,B,3,B,4,a,i,A,1,3,2,5,9,10,1,7,9,A,2,1,0,3,4,5,2,5,A,3,8,3,4,4,2,5,7,b,j,3,4,8,6,在闭回路,L,上，偶点变量减,5,，奇点变量加,5.,0,x,22,为,换入变量,取,x,12,为,换出变量,.,0,6,5,复 习,它所对应的位势与检验数为：,B,1,B,2,B,3,B,4,u,i,A,1,3,2,9,10,6,7,A,2,1,5,3,4,0,2,A,3,8,3,4,4,2,5,v,j,2,8,6,7,0,-5,-4,(1),(4),(4),(3),(10),(2),所有检验数都非负，迭代停止，运费为：,32+67+53+34+42=83,复 习,P,1,：充分利用现有工时，必要时可以加班；,P,2,：,A,，,B,，,C,的最低产量分别为,5,，,5,，,8,台，并依单位工时的利润比例确定权系数；,P,3,：生产线加班时每月不超过,20,小时；,P,4,：,A,，,B,，,C,的月销售指标分别定为,10,，,12,，,10,台，依单位工时利润比例确定权系数,.,试建立目标规划模型,.,A,、,B,、,C,三种计算机，在一条生产线上装配。装配时间分别为,5,，,8,，,12,小时；利润分别为每台,1000,元，,1440,元，,2520,元。生产线每月正常运转,170,小时。该厂的经营目标为：,例,5,复 习,复 习,在,5,个地点中选,3,处建生产同一产品的工厂，在这,5,个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示。,地点,1,2,3,4,5,所需投资（万元）,320,280,240,210,180,占用农田（亩）,20,18,15,11,8,生产能力（万吨）,70,55,42,28,11,现在有总投资,800,万元，占用农田指标,60,亩，应如何选择厂址，使建成后总生产能力最大。,例,6,复 习,复 习,解：设五个,01,变量,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，其中,i,=1,2,3,4,5.,建立整数规划模型为,Max z,=,70 x,1,+55x,2,+42x,3,+28x,4,+11x,5,s.t.,320 x,1,+280 x,2,+240 x,3,+210 x,4,+180 x,5,800,20 x,1,+18x,2,+15x,3,+11x,4,+8x,5,60,x,1,+x,2,+x,3,+x,4,+x,5,=3,x,1,，,x,2,，,x,3,，,x,4,，,x,5,=0,1,利用割平面算法求解下面的规划问题,例,7,复 习,解：将约束条件的系数化整；去掉“,x,1,x,2,是整数”的条件，得到一个线性规划的标准型（,LP,1,）为：,利用单纯形法求解这个线性规划问题，得出最终单纯形表：,3 2 0 0,x,1,x,2,x,3,x,4,x,2,x,1,2.5,3.25,0 1 1/2 -1/2,1 0 -1/4 3/4,j,0 0 -1/4 -5/4,复 习,最优解不是整数解，由最终表得到变量之间的关系：,3 2 0 0,x,1,x,2,x,3,x,4,x,2,x,1,2.5,3.25,0 1 1/2 -1/2,1 0 -1/4 3/4,j,0 0 -1/4 -5/4,将上面的约束条件当中的变量和系数改写成,整数,与,非负真分数,的和,把整数部分放在左边，非整数部分放在右边。,下面增加割平面,，,选真分数最大的一个,由于上式左端是整数，因此右端也应是整数，由于变量都是不小于,0,的整数，所以上式右端必是一个不大于,0.5,的整数，即,称这个不等式为一个,割平面。,引入一个松弛变量，化割平面为：,将它作为一个新增加的约束条件加入线性规划,LP,1,中得到一个新的,线性规划,LP,2,；,或者直接反映到,LP,1,的最终单纯形表中，得,LP,2,单纯形表,：,割平面的处理,：,复 习,LP,2,的单纯形表：,3 2 0 0 0,x,1,x,2,x,3,x,4,x,5,x,2,x,1,x,5,5/2,13/4,-1/2,0 1 1/2 -1/2 0,1 0 -1/4 3/4 0,0 0 -1/2 -1/2 1,0 0 -1/4 -5/4 0,3 2 0 0,x,1,x,2,x,3,x,4,x,2,x,1,2.5,3.25,0 1 1/2 -1/2,1 0 -1/4 3/4,j,0 0 -1/4 -5/4,LP,1,：,LP,2,：,复 习,3 2 0 0 0,x,1,x,2,x,3,x,4,x,5,j,0 0 -1/4 -5/4 0,x,2,x,1,x,3,2,7/2,1,0 1 0 -1 1,1 0 0 1 -1/2,0 0 1 1 -2,j,0 0 0 -1 -1/2,由于不是整数解，找出不满足条件的基变量,x,1,.,用对偶单纯型法求解：,复 习,将它作为一个新增加的约束加到线性规划,LP,2,中又得一个线性规划,LP,3,构造线性规划,LP,2,的割平面,复 习,LP,3,：,LP,3,的单纯形表：,3 2 0 0 0 0,x,1,x,2,x,3,x,4,x,5,x,6,x,2,x,1,x,3,x,6,2,7/2,1,-1/2,0 1 0 -1 1 0,1 0 0 1 -1/2 0,0 0 1 1 -2 0,0 0 0 0 -1/2 1,j,0 0 0 -1 0 -1,复 习,3 2 0 0 0 0,x,1,x,2,x,3,x,4,x,5,x,6,j,0 0 0 -1 -1/2 0,x,2,x,1,x,3,x,5,1,4,3,1,0 1 0 -1 0 2,1 0 0 1 0 -1,0 0 1 1 0 -4,0 0 0 0 1 -2,j,0 0 0 -1 0 -1,从上表中我们可以看到，已经找到了整数最优解：,x,1,=4,x,2,=1,。故求解结束。,用对偶单纯型法求解：,复 习,有一份资料，要分别译成四种文字，现有甲、乙、丙、丁四人可以承担这项工作。因为各人专长不同，他们翻译成不同文字所需要的时间用效率矩阵,C,表示。应如何分配工作，使他们完成任务的总时间最短？,例,8,Step 1,、先对效率矩阵进行列变换，使其各行各列中都出现,0,元素,.,效率矩阵变换方法为：,从效率矩阵,C,的每行元素中减去该行的最小元素,得矩阵,B,；从矩阵,B,中每列元素中减去该列的最小元素得矩阵,C,1,。,min 0 0 5 0,Step 2,、确定,C,1,中线性独立的,0,元素,.,从第一行开始，若该行只有一个,0,元素，就对这个,0,元素加圈，然后划去其所在列的其它,0,元素,;,若该行没有其它,0,元素或有两个以上,0,元素（已划去的不计），转下一行；直到最后一行为止。,然后,从第一列开始,若该列只有一个,0,元素,就对这个,0,元素加圈（同样不考虑已划的）,再划去其所在行的其它,0,元素,;,若该列没有,0,元素或有两个以上,0,元素，则转下列直到最后一列为止。,重复上述步骤,.,上述步骤可能出现三种情况,情况一：矩阵每行都有一个打圈的,0,元素。此时得到问题的最优解,.,情况二：有多于两行或两列存在两个以上的未处理的,0,元素，即出现,0,元素的闭回路。此时，可从中任选一个,0,元素加圈，划掉其同行同列的,0,元素，再重复上述两个步骤。,情况三：矩阵中所有,0,元素或被加圈，或被划去，而已加圈的,0,元素,m,小于矩阵的行数,n,。即矩阵中至少存在有一行不含加圈的,0,元素。转步骤三。,Step 3,寻找能覆盖,C,1,中所有,0,元素的最小直线数,.,(1),按照从上到下、从左到右的顺序对,C,1,没有加圈的,0,元行打,号；,(2),对已打,号的行中未加圈,0,元的列打,号；,(3),对已打,号的列中加圈,0,元的行打,号；,(4),重复下去，直到找不出打,号的行、列为止。,(5),对没打,号的行划一横线，对打,号的列划一纵线，这就是覆盖矩阵,C,1,中所有,0,元素的最小直线数,.,Step 4,、改进,C,1,(1),寻找,C,1,没有被直线覆盖的所有元素中的最小元素,；,例中,=2,.,(2),在已打,号的行中减去,；,(3),在已打,号的列中加上,；,得到一个新矩阵,C,2,。,-2,6,0,3,-2,9,2,3,0,13,4,0,0,5,4,3,0,0,用,C,2,代替,C,1,，返回步骤,2.,即例题的最优分配方案：,确定,C,2,中线性独立的,0,元素,.,应用动态规划求解,其中,c,是一个给定的正数。,分析：将该规划问题看成是产品生产问题。,即终止状态已知。,例,9,设阶段数,k,=1,2,3,；,状态变量为,其中,决策变量为,;,的指标函数为,则状态转移方程为：,解 用顺序法,.,问题直观模型为：,1,2,3,各阶段的允许决策集合为：,1,2,3,令最优值函数 表示从第阶段到第,阶段终止状态 所得到的最大值,.,则基本方程为,:,和 （舍去）,得：,令,由,所以,因为,类似可得：,由于,从而推出,因此得到最优解为：,最大值为,