运筹学复习题ppt课件

复习题,1,1.用单纯形法求解下列规划问题,MaxZ=5x1+2x2+3x3-x4x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x40,2,2.已知运输问题的供需关系表与运价表,试用表上作业法求最优解,3,3.某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使得总的钻探费用为最小。若10个井位的代号为s1，s2，s10，相应的钻探费用为c1，c2，c10，并且井位选择上要满足下列限制条件：或选择s1和s7，或选择钻探s8；选择了s3或s4就不选s5，反之亦然；在s5，s6，s7，s8中最多只能择两个；试建立这个问题的整数规划模型。,4,4某彩色电视机组装厂，生产A，B，C三种规格的电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台，10台，6台。该厂经营目标如下：P1:利润指标定为每月16000元；P2:充分利用生产能力；P3:加班时间不超过24小时；P4:产量以预计销量为标准；为确定生产计划,试建立该问题的目标规划模型。,5,5.用求V1至V6的最短距离与最短路径,13,9,18,10,7,12,19,12,5,V1,V2,V3,V5,V4,V6,6,6.用标号算法,求V1至V6的最大流,7,1.用单纯形法求解下列规划问题,8,9,最优解为：,最优值为：,10,MaxZ=5x1+2x2+3x3-x4-Mx5-Mx6x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60,MaxZ=5x1+2x2+3x3-x4x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x40,11,12,得到最优解：(25/3，10/3，0，11)T，最优目标值：112/3,MaxZ=5x1+2x2+3x3-x4x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x40,13,2已知运输问题的供需关系表与运价表,试用表上作业法求最优解,14,解:(1)以最小元素法确定初始基本可行解并以闭回路法判别,15,解:(1)以最小元素法确定初始基本可行解并以闭回路法判别,16,解:(2)以闭回路法调整,并判别,由于所有检验数均大于等于零,此解是最优解.,17,3.某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使得总的钻探费用为最小。若10个井位的代号为s1，s2，s10，相应的钻探费用为c1，c2，c10，并且井位选择上要满足下列限制条件：或选择s1和s7，或选择钻探s8；选择了s3或s4就不选s5，反之亦然；在s5，s6，s7，s8中最多只能择两个；试建立这个问题的整数规划模型。,18,3.解:设0-1变量,该问题的整数规划模型为:,x1x8=1x3x51x7x8=1x4x51x5x6x7x82xi0,且xi为0-1变量,(i=1,2,10),19,4某彩色电视机组装厂，生产A，B，C三种规格的电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台，10台，6台。该厂经营目标如下：P1:利润指标定为每月16000元；P2:充分利用生产能力；P3:加班时间不超过24小时；P4:产量以预计销量为标准；为确定生产计划,试建立该问题的目标规划模型。,20,4.解:设生产A型电视机x1台，B型电视机x2台，C型电视机x3台,该问题的目标规划模型为:,Minz=P1（d1-）+P2（d2-）+P3（d3+）+P4（d4+d4-+d5+d5-+d6+d6-）500 x1650 x2800 x3-d1+d1-=160006x18x210 x3d2+d2-=2006x18x210 x3d3+d3-=224x1-d4+d4-=12x2-d5+d5-=10 x3-d6+d6-=6x1,x2,x30;di+,di-0(i=1,2,6),21,5.解:,22,.给出点V1以标号(0，s)2.s12=l1+c12=0+13=13s13=l1+c13=0+9=9MIN(s12,s13)=s13=9给出点V3以标号(9，1)3.s12=l1+c12=0+13=13s34=l3+c34=9+18=27s35=l3+c35=9+12=21MIN(s12,s34,s35)=s12=13给出点V2以标号(13，1)4.s24=l2+c24=13+10=23s34=l3+c34=9+18=27s35=l3+c35=9+12=21MIN(s24,s34,s35)=s35=21给出点V5以标号(21，3),5.s24=l2+c24=13+10=23s56=l5+c56=21+19=40MIN(s24,s56)=s24=23给出点V4以标号(23，2)6.s46=l4+c46=23+12=35s56=l5+c56=21+19=40MIN(s46,s56)=s46=35给出点V6以标号(35，4)7.计算结束,得到最短路V1至V6的最短距离为35最短路径为V1-V2-V4-V6,23,6.解(1)通过标号求寻找可增广链V1-V2-V4-V6,，+,+V1，1,+V1，6,+V2，5,-V2，2,+V4，2,24,6.解(2)调整值为2,25,6.解(3)再通过标号求寻找可增广链V1-V2-V5-V6,，+,+V1，4,+V1，1,+V2，3,-V2，2,+V5，2,26,6.解(4)调整值为2,27,6.解(5)再通过标号求寻找可增广链V1-V3-V5-V6,，+,+V1，2,+V2，2,