1、运筹学习题习 题Exercises第一章 线性规划一、以下集合中，哪些是凸集，哪些不是凸集?(1)(x1, x2)x1+x21(2)(x1, x2, x3)x1+x21,x1-x32(3)(x1, x2)x1-x2=0(4)(x1, x2, x3)x1x2, x1+x2+x36(5)(x1, x2)x1=1,x24(6)(x1, x2 , x3) | x3 = | x2| , x14二、求出以下不等式组所定义的多面体的所有极点，(1)x1+x2+x35-x1+x2+2x36x1,x2,x30(2)x1+x2+x31-x1+2x24x1,x2,x30三、用图解法求解以下线性规划问题(1)maxz
2、=x1+3x2s.t.x1+x210-2x1+2x212x1 7x1,x20(2)minz=x1-3x2s.t.2x1-x24x1+x23x25x14x1,x20(3)maxz=x1+2x2 s.t.x1-x21 x1+2x24 x13 x1,x20(4)minz=x1+3x2 s.t.x1+2x24 2x1+x24 x1,x20四、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。maxz=2x1+x2-x3s.t.x1+ x2+2x36 x1+4x2-x34 x1,x2,x30五、对于以下的约束x1+2x26x1-x24 x22x1,x20(1).画出该可行域，并求出各极
3、点的座标。(2).从原点开始，从一个基础可行解移到下一个“相邻的”基础可行解，指出每一次叠代，哪个变量进基，哪个变量离基。六、用单纯形原理求解以下线性规划问题maxz=3x1+2x2s.t.2x1-3x23 -x1+x25 x1,x20七、已知(x1，x2，x3)(4，0，4)是以下线性规划的一个基础可行解，以这个基为初始可行基，求解这个线性规划问题maxz=x1-2x2s.t.3x1+4x212 2x1-x212 x1,x20八、用单纯形表求解以下线性规划问题(1)maxz=x1-2x2+x3 s.t.x1+x2+x312 2x1+x2-x3 6 -x1+3x2 9 x1,x2,x3 0(2
4、)minz=-2x1-x2+3x3-5x4 s.tx1+2x2+4x3-x4 6 2x1+3x2-x3+x412 x1+x3+x4 4 x1,x2,x3,x4 0(3)minz=3x1-x2 s.t.-x1-3x2-3 -2x1+3x2-6 2x1+x2 8 4x1-x216 x1,x2 0九、用两阶段法求解以下线性规划问题(1)maxz=x1+3x2+4x3 s.t.3x1+2x213 x2+3x317 2x1+x2+x3=13 x1,x2,x30(2)maxz=2x1-x2+x3 s.t.x1+x2-2x38 4x1-x2+x32 2x1+3x2-x34 x1,x2,x30(3)minz=
5、x1+3x2-x3 s.t.x1+x2+x33 -x1+2x22 -x1+5x2+x34 x1,x2,x30第二章 对偶线性规划和灵敏度分析一.写出以下问题的对偶问题(1)maxz=-x1+2x2 s.t.3x1+4x212 2x1-x2 2 x1,x2 0(2)minz=2x1+3x2+5x3+6x4 s.t.x1+2x2+3x3+x42 -2x1-x2-x3+3x4-3 x1,x2,x3,x40(3)minz=2x1+3x2-5x3 s.t.x1+x2-x3+x45 2x1+x34 x2+x3+x4=6 x10, x20, x30, x4无符号限制二、设原始问题为maxz=2x1+3x2s
6、.t.x1+x24 x23 x1,x20s. 写出对偶问题(2)用图解法分别求出原始问题和对偶问题的各基础可行解，并求出各基础可行解的目标函数值，并比较他们的大小。(3)验证原始问题和对偶问题的最优解满足Kuhn-Tucker最优性条件。三、已知如下最优单纯形表，其中x4，x5是松弛变量，两个约束都是型的。zx1x2x3x4x5RHSz10 -40-4-2-40x300 1/21 1/2 05/2x101-1/20-1/61/35/2（1）写出原始问题及对偶问题。（2）从上表中直接求出对偶问题的最优解。四、对于以下线性规划问题maxz=2x1+3x2+6x3s.t.x1+x2+x310 x1-
7、x2+3x3 6 x1,x2,x3 0(1).写出对偶问题(2).写出原始问题所有的基，判断这些是否原始可行基，是否对偶可行基。(3).求出原始问题和对偶问题的最优解。五、对于以下问题maxz=4x1+6x2-x3s.t.x1+x2+2x36 x1+4x2-x34 x1,x2,x30(1) 写出对偶问题(2) 用单纯形表求解原始问题，求出每一次叠代的当前基B对应的对偶变量WTCTBB-1，并判断每次得到的对偶变量是否满足对偶可行条件。六、用对偶单纯形法求解以下问题(1)minz=4x1+6x2+18x3 s.t.x1+3x33 x2+2x35 x1,x2,x30(2)minz=10x1+6x2
8、 s.t.x1+x22 2x1-x26 x1,x20七、对以下问题minz=x1+x2s.t.2x1+x23 x1+4x24 x1+2x23 x1,x20（1）用图解法画出可行域和各个极点。（2）用对偶单纯形表求解以上问题，并在图上画出叠代路线。八、已知以下线性规划问题maxz=2x1+x2-x3s.t.x1+2x2+x38-x1+x2-2x34x1,x2,x30及其最优单纯形表如下：zx1x2x3x4x5RHSz10332016x10121108x6003-11112（1） 求使最优基保持不变的c2=1的变化范围。如果c2从1变成5，最优基是否变化，如果变化，求出新的最优基和最优解。（2）
9、对c1=2进行灵敏度分析，求出c1由2变为4时的最优基和最优解。（3） 对变量x3在第二个约束中的系数a23=-2进行灵敏度分析，求出a23从-2变为1时新的最优基和最优解。（4） 增加一个新的变量x6，它在目标函数中的系数c6=4，在约束条件中的系数向量为， 求新的最优基和最优解。（5） 增加一个新的约束x2+x32，求新的最优基和最优解。（6） 设变量x1在约束条件中的系数向量由变为，求出新的最优基和最优解。九、某工厂用甲、乙、丙三种原料生产A、B、C、D四种产品，每种产品消耗原料定额以及三种原料的数量如下表所示:产 品ABCD原料数量（吨）对原料甲的单耗(吨/万件)32142400对原料
10、乙的消耗(吨/万件)2233200对原料丙的消耗(吨/万件)1321800单位产品的利润(万元/万件)25121415（1）求使总利润最大的生产计划和按最优生产计划生产时三种原料的耗用量和剩余量。（2）求四种产品的利润在什么范围内变化，最优生产计划不会变化。（3）求三种原料的影子价格和四种产品的机会成本，并解释最优生产计划中有的产品不安排生产的原因。（4）在最优生产计划下，哪一种原料更为紧缺?如果甲原料增加120吨，这时紧缺程度是否有变化?第三章 整数规划1、 分别用割平面法和分枝定界法求以下整数规划问题maxz=x1+4x2s.t.14x1+42x2196-x1+2x2 5x1x202、 用
11、分枝定界法求解以下混合整数规划问题maxz=3x1+7x2s.t.2x1+3x212-x1+x2 2x1x2 0x1为整数3、 求解以下整数规划问题maxz=65x1+80x2+30x3s.t.2x1+3x2+x35x1x2x30x1，x2，x3为整数第四章 运输问题1、 求解如下图所示的运输问题，并将最优解在网络中表示。2、 将下表所示的一组解作为初始解，分别用闭回路法和对偶变量法求出非基变量的zij-cij，并求出运输问题的最优解。981213184141010121424248911126241010111212756143553、 对下表所示的运输问题（表内部的数字表示cij，表右面和
12、下面的数字分别表示供应量和需求量）。B1B2B3B4A162-105A2472525A331212510102015（1） 分别用西北角法和最小元素法得到初始基础可行解；（2） 选择其中一个基础可行解，从这个基础可行解出发，求出这个问题的最优解；（3） 如果c11=6变为-4，最优解是否改变？如改变，求出新的最优解；（4） 在原来的问题中，如果从A2到B1的道路被阻，最优解是否会改变？如改变，求出新的最优解。4、 求解下表所示的供求不平衡的运输问题，其中AiBj格子中的数字表示cij。供求地B1B2B3B4供应量A1211347A2103595A378127需求量23465、 有n项任务，分配
13、给n个人去完成，每项任务只需要一个人去做，每个人只做一项任务。第i项任务分配给第j个人去做所需要的费用为cij。应如何分配各项任务，使完成n项任务的总费用最小。这个问题称为指派问题（Assignment Problem）。矩阵C=cijnn称为指派问题的费用矩阵。指派问题是一类特殊的运输问题。用运输问题算法求解以下指派问题，费用矩阵如下表所示：人员1人员2人员3任务1121110任务29814任务313912第五章 网络优化1、 对以下网络，用试凑的方法得到一个初始可行的生成树，求这个网络的最小费用流。2、 求解下图所示的最小费用流问题（注意：）3、 求解下图所示的具有中转站的运输问题，其中节
14、点1、2、3是发地，6、7是收地，4、5是中转站。边上的数字是cij。 4、用两阶段法求解下图所示的网络最小费用流问题。5、 求解以下的生产运输存储问题。一个公司在A1、A2两地生产同一种产品，考虑一、二两个季度的生产。不同的产地，不同的季节，生产费用和生产能力都不相同。产地A1、A2两个季度的生产费用和生产能力如下表。产地第一季度第二季度生产费用生产能力生产费用生产能力A125元/吨6吨35元/吨2吨A230元/吨10吨43元/吨9吨A1、A2生产的产品可以运输到两个销地B1、B2（运输时间可以不计），以满足两地的需求，B1、B2两地的需求量如下表所示。销地第一季度第二季度B13吨2吨B25
15、吨4吨运输费用也随运输路线和季节不同而变化。如下表所示。产地第一季度第二季度销地B1销地B2销地B1销地B2A150元/吨60元/吨60元/吨80元/吨A240元/吨70元/吨70元/吨90元/吨另外，每个产地和销地都可以库存第一季度的产品，以供第二季度之用，库存费用如下表所示。产/销地库存费用A12元/吨A22元/吨B13元/吨B24元/吨求两个季度的最优生产、库存计划，使两个季度的总费用最小。6、求下图所示网络的最大流（1）（2）4、求以下网络从节点1到其余各节点的最短路径（1）（2）第六章 动态规划一、用动态规划求解以下网络从A到F的最短路径，路径上的数字表示距离。二、某公司有5台设备，
16、分配给所属A,B,C三个工厂。各工厂获得不同的设备台数所能产生效益（万元）的情况如下表。求最优分配方案，使总效益最大。 台数 工厂012345A01015202325B51720222324C71215182023三、用动态规划求解以下非线性整数规划问题：min z=3x12-5x1+3x22-3x2+2x32-7x3s.t. 2x1+3x2+2x316 x1 ,x2 ,x30 ,x1 ,x2 ,x3为整数四、用动态规划求解以下背包问题（1）max z=12x1+22x2+15x3s. t. 2x1+4x2+3x310x1 ,x2 ,x30, x1 , x2 , x3 为整数（2）max z=
17、17x1+72x2+35x3s.t. 10x1+41x2+20x350x1 ,x2 ,x30, x1 , x2 , x3 为整数五、某工厂要安排某种产品一年中四个季度的生产计划。生产费用的经验公式是： 0.005元(本季度产量)2产品的存储费用为每件每季度1元。设初始存储量为0，最大存储量为1500件。四个季度的市场销售量预测如下：季度销售量（件）累计销售量（件）一600600二7001300三5001800四12003000用动态规划确定四个季度的生产量和储存量，在满足各季度销售额的条件下使总生产、存储费用为最小。六、有三种新产品A，B，C有待研制。每种新产品在一年内研制不成功的概率与投入该
18、产品的研制费用有关，有关数据如下表。设总的研制经费为3万元。试求三个项目研制费用的分配方案，使这三个产品研制全不成功的概率为最小。产 品ABC1万元0.400.600.802万元0.200.400.503万元0.150.200.30七、求解以下设备更新问题：当设备年龄为k年时，设备运行每年所得的净收入可用下式表示： Ik=26-2k-0.5k2, k=0,1,2,3,4设备用过4年后就被废弃，更新设备的费用为22。现有一台设备，已用过一年，要作这种设备更新的五年计划，决定每一年初设备更新或留用，使总收入最大。八、求以下货郎担问题的最小旅行费用周游线路，以下是5个城市中从城市 i 到城市 j 的
19、费用。注意其中两个城市之间往返的费用是不相等的。 i j1234519117821361243108510471262511943第七章 排队论一、某修理店只有一个修理工，来修理的顾客到达的次数服从Poisson分布，平均每小时4人；修理时间服从负指数分布，每次服务平均需要6分钟。求：（1）修理店空闲的概率；（2）店内有三个顾客的概率；（3）店内至少有一个顾客的概率；（4）在店内平均顾客数；（5）顾客在店内的平均逗留时间；（6）等待服务的平均顾客数；（7）平均等待修理的时间；二、一个单人理发点，顾客到达服从Poisson分布，平均到达时间间隔为20分钟；理发时间服从负指数分布，平均理发时间为1
20、5分钟。求：（1）顾客来店理发不必等待的概率；（2）理发店内顾客平均数；（3）顾客在理发店内的平均逗留时间；（4）当顾客到达速率是多少时，顾客在店内的平均逗留时间将超过1.25小时。三、在第一题中，如果修理店内已有三个顾客时，店主就拒绝顾客排队。求：（1）店内空闲的概率；（2）各运行指标L，Lq，W，Wq。四、在M/M/1:N/FCFS系统中，设顾客到达速率为，服务速率为，求单位时间内被拒绝的顾客数的期望值。五、在第一题中，设顾客到达速率增加到12人/小时，这时又增加一个同样熟练的修理工，平均修理时间也是6分钟。求：（1）店内空闲的概率；（2）店内有两个或更多顾客的概率；（3）计算运行指标L，Lq，W，Wq。六、如果将第五题中的两个修理工分别安排在两家修理店里，成为两个单人修理店，每个店顾客到达速率都是6人/小时，服务速率都是6分钟。（1）求这两个修理店的运行指标L，Lq，W，Wq；（2）将以上运行指标与第五题两个修理工的系统比较。
