运筹学大题举例

1、运 筹 学,大题举例,例1:某药厂生产A、B、C三种药物，可供选择的原料有甲、乙、丙、丁，四种原料的成本分别是5元，6元，7元，8元。每公斤不同原料所能提取的各种药物的数量（单位：克/公斤）见下表. 药厂要求每天生产A药恰好100克，B药至少530克，C药不超过160克，要求选配各种原料的数量既满足生产需要，又使总成本最小，试建立此问题的数学模型。,解：设 x1 , x2 , x3 , x4 分别为原料甲、乙、丙、丁的选配数量（单位：公斤），则有,min z =5x1+6x2+7x3+8x4,s . t . x1+ x2+ x3+ x4 = 100,5x1+4 x2+5 x3+ 6 x4 53

2、0,2x1+ x2+ x3+ 2 x4 160,x1 , x2 , x3 , x4 0,求解如下线性规划问题,例2,复 习,解：加入松弛变量，标准化得,建立单纯形表如下：,复 习,复 习,解毕,复 习,例3:用大M法计算下列线性规划,max z = 2x1 + 3x2 s.t. 2x1 + x2 16 x1 + 3x2 20 x1 + x2 = 10 x1, x2 0,解：化为标准形并加入人工变量为：,max z = 2x1 + 3x2 - Mx5 - Mx6 s.t. 2x1 + x2 + x4 = 16 x1 + 3x2 - x3 + x5 = 20 x1 + x2 + x6= 10 x1

3、, x2 , x3 , x4 , x5 , x6 0,最优解为(0，10)T , 最优值为 z* = 30,设某种物资有3个产地 A1，A2，A3， 生产量分别为9，5，7;有4个销地B1，B2，B3，B4 ，销售量分别为3，8，4，6 ;已知从Ai到Bj 物资的单位运价见下表。求总运费最小的调运方案。,例4,复 习,伏格尔法计算1,用伏格尔法寻找初始基：,先算出运价表中各行与各列的最小运费与次小运费的差额，并填入该运价表的最右列和最下行。 从行差或列差中选出最大者，并选择其所在行或列的最小元素。,A1的行差最大，而其中运价c11最小, 令x11为优先运输路线。,复 习,用伏格尔法寻找初始基：

4、,销地B1的销量3全由产地A1供给，所以x21=x31=0。将x11=3 填到调运方案表中第1行第1列上。,画去运输数据表第一列，A1的产量剩余为9-3=6。得到新的产销平衡与单位运价表.,令,伏格尔法计算1,复 习,用伏格尔法寻找初始基：,再算出运价表中的行差与列差。,B4的列差最大，而其中运价c24最小, 令x24为优先运输路线。,产地A2的产量2全供给销地B4，所以x23=x24=0。,画去运输数据表中第2行，B4的销量还要6-5=1。得新表。,令,伏格尔法计算1,复 习,用伏格尔法寻找初始基：,伏格尔法计算1,复 习,用伏格尔法寻找初始基：,伏格尔法计算1,复 习,用伏格尔法寻找初始基

5、：,现在只有一个产地两个销地，故令x12 =5 ,x14 =1为基变量，将其分别填到调运方案表中1行2列与1行4列上。,得到产销平衡运输问题的一个初始方案,伏格尔法计算1,复 习,此方案的运费是 32+59+47+52+34+42=88。 伏格尔法给出的初始解往往更接近于最优解。,复 习,利用伏格尔法确定的初始解如下表所示：,1、写出基可行解对应的位势方程组; 2、并计算非基变量的检验数。,复 习,求解位势及检验数的过程可在一个特殊设计的表上完成，这个表的构造如下： 在原单位运价表增加一行与一列，在列中填入ui，在行中填入vj；把运价cij记在每一格的右上角，用框标定，在基变量对应的格中标出0

6、，构成表。,复 习,由u1+v1=2, u1+v2=9, u1+v4=7,得v1=2, v2=9, v4=7;,0,-5,-5,2,9,7,7,位势表：,再由u2+v4=2，u3+v2=4，得u2=-5，u3=-5;,最后由u3+v3=2 得v3=7.,取u1=0;,复 习,检验数表：,(计算所有非基变量的检验数),0,-5,-5,2,9,7,7,(3),(4),(-1),(2),(11),(3),当存在非基变量的检验数kl 0，说明现行方案为最优方案，否则目标成本还可以进一步减小。,复 习,伏格尔法的初始方案：,(3),(4),(-1),(2),(11),(3),x22为换入变量, 从 x2

7、2所在格出发做闭回路L, L中有两个偶点x24, x12，,取x12为换出变量，调整量为5.,复 习,伏格尔法的调整方案：,在闭回路L上，偶点变量减5，奇点变量加5.,0,x22为换入变量,取x12为换出变量.,0,6,5,复 习,它所对应的位势与检验数为：,2,8,6,7,0,-5,-4,(1),(4),(4),(3),(10),(2),所有检验数都非负，迭代停止，运费为： 32 + 67 + 53 + 34 + 42 = 83,复 习,练习: 单纯形表,解：化为标准形为,20,10,20,0,30,4,-5,-3,0,10,2,-3,-1,0,1,-3,-2,20,7.5,5,1,5,-1

8、.5,-0.5,0.5,15,0,0.5,0.5,0.5,10,0,1,-1,-2,25,0,0,0,-1.5,-1.5,-0.5,所以，所求最优解为 z*=25 , x1=15 , x2=5 , x3=0 , x4=10 , x5=x6=0,练习:求解下列运费最少的运输问题,由伏格法（差额法）得：,差额,差额,1,4,1,1,1,2,1,2,20,1,1,4,4,30,3,2,1,7,25,1,2,6,5,5,15,最优性检验：由位势法得,6,1,0,2,2,2,7,1,2,3,1,5,-1,从表中可以看出，a32 的检验数小于零，,需要进行调整，得,+5, 5,+5,5,新的运输方案为,重

9、新进行检验得：,6,1,0,2,1,3,8,1,2,2,0,4,1,z *= 257+15 2+10 6+15 9+5 3+30 4=535,练习: 求节点v1到节点v5的最短距离及其路线,vS,v1,v2,v3,v4,v5,1,2,2,2,3,3,3,4,4,解 P(vs)=0 T(vj)=,j=1,5,第一步：,T(v1)=minT(v1),P(vs)+ds1=min,0+4=4,(1)与节点vs直接相连的临时标号的节点为 v1, v2，将这两个节点的临时标号改为,T(v2)=minT(v2),P(vs)+ds2=min,0+3=3,0,42,(2)在所有T标号中，最小的为T(v2)=3,

10、于是令P(v2)=3,vS,v1,v2,v3,v4,v5,1,2,2,2,3,3,3,4,4,0,4,3,第二步：,(1)与节点v2直接相连的临时标号的节点为V1和v4，把这两个节点的T标号改为,T(v1)=minT(v1),P(v2)+d21=min4,3+2=4,T(v4)=minT(v4),P(v2)+d24=min,3+2=5,(2).在所有T变化中，T(v1)=4最小，于是令P(v1)=4,5,第三步：,(1).与节点v1相连的临时标号的节点为v3,v4，把这两个节点的T标号改为,T(v3)=minT(v3),P(v1)+d13=min,4+3=7,T(v4)=minT(v4),P(v1)+d14=min5,4+1=5,(2).在T标号中，T(v4)=5最小，令P(v4)=5,vS,v1,v2,v3,v4,v5,1,2,2,2,3,3,3,4,4,0,4,5,3,7,第四步：,(1).与节点v4相连的T标号有v3,v5把这两个节点的T标号改为,T(v3)=minT(v3),P(v4)+d43=min7,5+2=7,T(v5)=minT(v5),P(v5)+d45=min,5+4=9,vS,v1,v2,v3,v4,v5,1,2,2,2,3,3,3,4,4,0,4,5,3,7