安徽建筑大学运筹学模拟试题.doc

（8分）已知线性规划问题 其对偶问题最优解为，，试根据队友理论求出原问题的最优解。 2、已知运输问题的供需关系表与单位运价表如下所示，试用伏格尔法求出该问题的近似最优解。（6分） 产地 销地 甲 乙 丙 丁 产量 1 3 2 7 6 50 2 7 5 2 3 60 3 2 5 4 5 25 销量 60 40 20 15 3请用匈牙利法求解该指派问题：（8分） 已知效率矩阵如下： 4网络最大流问题：（12分） 下面为一容量网络，各弧上的代表该弧的（可行流流量，容量） 请用标号法求出该网络最大流。 5、指派问题：（10分） 现有五个人Ai (i=1,2,3,4,5)被分配去完成完成五项工作Bj (j=1,2,3,4,5)，每人只能完成一项工作，且每项工作只能有一人来完成，每人完成每项工作所花费的费用如下表，请求使总费用最小的最优解。 人员 任务 B1 B2 B3 B4 B5 A1 12 7 9 7 9 A2 8 9 6 6 6 A3 7 17 12 14 12 A4 15 14 6 6 10 A5 4 10 7 10 6 6、规划问题：（7分） 用单纯形法求解某线性规划问题得如下单纯形表： cj 100 80 0 0 S 基变量 x1 x2 x3 x4 a c 0 1 3/10 -1/5 12 b d 1 0 -1/10 2/5 16 cj-zj e f -14 -24 g 上述问题是求maxS=100x1+80x2 ,x3,x4为松弛变量，则a,b,c,d,e,f,g各为多少，上述表所给出的解是最优解吗？ 上述问题的对偶问题的解是什么？最优值是什么？ 7、运输问题：（10分） 对如下表的运输方案： 若要使总利润最大，该方案是否为最优方案？ 若问题中B1的需要量改为700，该方案是否为最优方案？ 8.已知线性规划问题 写出其对偶问题； 用图解法求对偶问题的解； 利用（2）的结果及对偶性质求原问题解。 9．某土石方从三个产地运往四个工地，产地的产量、工地的需求量及单位运费如下表，求最优运输方案。 产地 销地 B1 B2 B3 B4 产量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量 3 6 5 6 10．求下面网络图的最小支撑树： 11求总运费最小的运输问题，某步运输图如下： 写出a, b ,c ,d ,e的值，并求出最优运输方案； A3到B1的单位运费满足什么条件时，表中运输方案为最优方案。 12.分配甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间如下表，试确定总花费时间为最少的指派问题。 人 任务 A B C D E 甲 12 7 9 7 9 乙 8 9 6 6 6 丙 7 17 12 14 9 丁 15 14 6 6 10 戊 4 10 7 10 9 13.求下图所示容量网络中从～的最大流。其中每边上的数为。 14.某公司下属的3个分厂A1、A2、A3生产质量相同的工艺品，要运输到B1、B2、B3、B4 ，4个销售点，分厂产量、销售点销量、单位物品的运费数据如下： 求最优运输方案。 15.考虑下列线性规划： 最优单纯形表为： （1）、写出此线性规划的最优解、最优基 B 和它的逆 B-1 ；（2）、求此线性规划的对偶问题的最优解；（3）、试求 c2 在什么范围内，此线性规划的最优解不变；（4）、若 b1 = 20 变为 45，最优解及最优值是什么？ 16.某公司决定投资60万元（以10万元为单位），以提高三种主要产品 A、B、C 的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下： 试确定如何安排对各种产品的投资数，可获得最大总期望利润？ 17.有下面线性规划： 要求：1、用单纯性发就解该线性规划问题； 2、写出该问题的对偶规划； 3、利用原问题的最优解和互补松弛性，直接秋池对偶问题的最优解； 4、利用原问题的最后一张单纯形表，直接秋池对偶问题最优解。 18.某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如下表所示。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总的运费最小。 产地 需地 B1 B2 B3 B4 产量 A1 2 9 10 7 9 A2 1 3 4 2 5 A3 3 4 2 5 7 需求量 3 8 4 6 19.已知下图表示7个城市间拟建一条连接各个城市的通讯线路，各边的权数表示两个城市之间的修建费用，求连接各城市通讯线路最修修建费用方案。 20