运筹学复习题

复习题.1.用单纯形法求解下列规划问题Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0.2.已知运输问题的供需关系表与运价表,

试用表上作业法求最优解

销地产地甲乙丙丁产量132765027523603254525销量60402015.3.某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使得总的钻探费用为最小。若10个井位的代号为s1，s2，…s10，相应的钻探费用为c1，c2，…，c10，并且井位选择上要满足下列限制条件：①或选择s1和s7，或选择钻探s8；②选择了s3或s4就不选s5，反之亦然；③在s5，s6，s7，s8中最多只能择两个；试建立这个问题的整数规划模型。.4．某彩色电视机组装厂，生产A，B，C三种规格的电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台，10台，6台。该厂经营目标如下：P1:利润指标定为每月16000元；P2:充分利用生产能力；P3:加班时间不超过24小时；P4:产量以预计销量为标准；为确定生产计划,试建立该问题的目标规划模型。.5.用求V1至V6的最短距离与最短路径139181071219125V1V2V3V5V4V6.6.用标号算法,求V1至V6的最大流(14,8)(10,9)(10,2)(15,10)(6,6)(15,1)(8,3)(5,0)V1V2V3V5V4V6(18,16).1.用单纯形法求解下列规划问题解:令于是原线性规划问题变为标准形式：.迭代次数基CBx1x2x3x4b比值-3-1-1-10x3-1-221042x4-1310166zj-1-3-1-1j=

cj-zj-22001x2-1-111/202-x4-140-1/2141zj-3-10-1j=

cj-zj00-102x2-1013/81/43-x1-310-1/81/411zj100-1j=

cj-zj00-10.最优解为：最优值为：.Max

Z=5x1+2x2+3x3-x4-M

x5-Mx6

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4,x5,x6

≥0Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0.

基CBx1x2x3x4x5x6b比值523-1-M-Mx5-M123010155x6-M21(5)001204x4-1124100266.5j3M+63M+48M+700035M+26x5-M-1/57/5001-3/5315/7x332/51/51001/5420x4-1-3/56/5010-4/51025/3j-M/5+16/57/5M+13/5000-8/5M-7/53M-2x22-1/71005/7-3/715/7－x33(3/7)010-1/72/725/725/3x4-1-3/7001-6/7-2/752/7－j25/7000-M-13/7-M-2/7-53/7x22011/302/3-1/310/3x15107/30-1/32/325/3x4-10011-1011j00-25/30-M-2/3-M+8/3-112/3.得到最优解：(25/3，10/3，0，11)T，最优目标值：112/3Max

Z=5x1+2x2+3x3-x4

x1+2x2+3x3=152x1+x2+5x3=20

x1+2x2+4x3+x4=26

x1,x2,x3,x4≥0.2已知运输问题的供需关系表与运价表,

试用表上作业法求最优解

销地产地甲乙丙丁产量132765027523603254525销量60402015.销地产地甲乙丙丁产量132765010409

7275236025-12015325452525

477销量60402015135135解:(1)以最小元素法确定初始基本可行解

并以闭回路法判别.销地产地甲乙丙丁产量13276501001040972752360402525-120153254525025477销量6025400200150135135解:(1)以最小元素法确定初始基本可行解

并以闭回路法判别.销地产地甲乙丙丁产量132765035158

627523601252015325452525466销量60402015135135解:(2)以闭回路法调整,并判别由于所有检验数均大于等于零,此解是最优解..3.某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使得总的钻探费用为最小。若10个井位的代号为s1，s2，…s10，相应的钻探费用为c1，c2，…，c10，并且井位选择上要满足下列限制条件：①或选择s1和s7，或选择钻探s8；②选择了s3或s4就不选s5，反之亦然；③在s5，s6，s7，s8中最多只能择两个；试建立这个问题的整数规划模型。.3.解:设0-1变量,该问题的整数规划模型为:x1＋x8=1x3＋x5≤1x7＋x8=1x4＋x5≤1x5＋x6＋

x7＋x8≤2xi≥0,且xi为0-1变量,(i=1,2…,10)

.4．某彩色电视机组装厂，生产A，B，C三种规格的电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台，10台，6台。该厂经营目标如下：P1:利润指标定为每月16000元；P2:充分利用生产能力；P3:加班时间不超过24小时；P4:产量以预计销量为标准；为确定生产计划,试建立该问题的目标规划模型。.4.解:设生产A型电视机x1台，B型电视机x2台，C型电视机x3台,该问题的目标规划模型为:Minz=P1（d1-）+P2（d2-）+P3（d3+）+P4（d4++

d4-+

d5++

d5-+

d6++

d6-）

500x1＋650x2＋800x3-d1++d1-

=160006x1＋8x2＋10x3–d2++d2-

=2006x1＋8x2＋10x3–d3++d3-

=224x1-d4++d4-=12x2-d5++d5-=10x3-d6++d6-=6x1,x2,x3≥0;di+,di-≥0(i=1,2…,6).5.解:139181071219125V1(0,s)V2(13,1)V3(9,1)V5(21,3)V4(23,2)V6(35,4).１.给出点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.6.解(1)通过标号求寻找可增广链V1->V2->V4->V6(14,8)(10,9)(10,2)(15,10)(6,6)(15,1)(8,3)(5,0)V1V2V3V5V4V6(18,16)[△，+∞][+V1，1

][+V1，6

][+V2，5

][-V2，2

][+V4，2

].6.解(2)调整值为2(14,10)(10,9)(10,2)(15,12)(6,6)(15,1)(8,3)(5,0)V1V2V3V5V4V6(18,18).6.解(3)再通过标号求寻找可增广链V1->V2->V5->V6(14,10)(10,9)(10,2)(15,12)(6,6)(15,1)(8,3)(5,0)V1V2V3V5V4V6(18,18)[△，+∞][+V1，4

][+V1，1

][+V2，3

][-V2，2

][+V5，2

].6.解(4)调整值为2(14,12)(10,9)(10,0)(15,12)(6,6)(15,3