搜索
1一、填空题：（10分）1、运输问题中，求总利润最大时，当运输图所有空格的检验数，得最优解；求总运费最小时，当运输图所有空格的检验数，得最优解。2、若线性规划问题的最优基为B，则问题的最优值为，线性规划的对偶问题的最优解是，其中CB是基B所对应的基变量在目标函数中的系数向量，线性规划问题是：0maxXbAXCXZ3、运输问题中，当总供应量小于总需求量时，求解时需虚设一个点，此点的供应量应（总需求量与总供应量之差）。4、结点的最迟完成时间又称时间，若将最迟完成时间后延，将使整个网络工期。5、树是的连通图，在树上任意除去一条边则该树余下的图。二、单项选择题（10分）1、为了在各住宅之间安装一条供暖管道，若要求所用材料最省，则应采用（）。A．求最大流量法B.求最小支撑树法C．求最短路线法D.树的逐步生成法2、在网络计划中，进行时间与成本优化时，随工期延长，简介费用将（）。A．减少B.增加C.不变D.不易估计3、图论中，图的基本要素是（）。A．点和带方向的连线B.点和线C．点及点与点之间的连线D.点和一定要带权的连线三、判断题。（10分）1、线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。2、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。3、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。4、目标规划中，英同时包含系统约束（绝对约束）与目标约束。5、用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值得下界。四、建立数学模型题：（8分）某饲养场饲养动物出售，设每头动物每天至少需700克蛋白质、30克矿物质、100毫克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示：要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。饲料成分蛋白质（克）矿物质（克）维生素（毫克）价格（元/千克）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8五、（8分）已知线性规划问题20,,,2020max4321432143214321232322432xxxxxxxxxxxxxxxxZ其对偶问题最优解为2.11y，2.02y，试根据队友理论求出原问题的最优解。六、已知运输问题的供需关系表与单位运价表如下所示，试用伏格尔法求出该问题的近似最优解。（6分）产地销地甲乙丙丁产量132765027523603254525销量60402015七、用图解法找出下列目标规划问题的满意解（8分）)3,2,1(0,;0,15524)(min21332222111211132231526iZddxxddxddxxddxxddpdpdpii八、请用匈牙利法求解该指派问题：（8分）已知效率矩阵如下：1096109532485724679278310283九、网络最大流问题：（12分）下面为一容量网络，各弧上的),(cfijij代表该弧的（可行流流量，容量）请用标号法求出该网络最大流。3一、单项选择题：(10分)1、若用图解法求解线性规划问题，则该问题所包含决策变量的数目应为（）。A、二个B、五个以上C、三个以上D、无限制2、原问题的检验数对应于对偶规划的一个解，符号相反，对偶规划的检验数对应于原规划的一个解（符号性反），特别的，若原问题的最优基为B，则对偶问题的最优解为：（）A、Y*=-CBB-1B、Y*=CBB-1C、Y*=CN-CBB-1D、Y*=B-CBB-13、甲、乙、丙、丁四个球队进行比赛，任两个队都有一场比赛，且没有和局，用来表示这四个队比赛状况的图是（）。A、一棵树B、没有圈C、连通图D、任两点之间有一条带有方向的线4、下列图形中是一棵树的为：()ABCD5、以下哪个性质是对偶问题所不具有的（）A、对称性B、互补松弛性C、弱对偶性D、可行性二、判断题：（10分）1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（）2、线性规划问题每一个基解对应于可行域的一个顶点。（）3、正偏差变量应取正值，负偏差变量应取负值。（）4、线性规划问题是目标规划问题的一种特殊形式。（）5、表上作业法实质就是求解运输问题的单纯形法。（）三、填空题：（10分）1、在图论方法中，通常用表示人们研究的对象，用表示对象之间的某种联系。2、xi是某线性规划问题的一个决策变量，若它是该线性规划问题某步单纯形表中的一个基变量，则xi的检验数为；若其检验数不为零，则其为变量。3、利用单纯形法求解线性规划问题时，在最终单纯形表中，若某一基变量为零，该基解称为解；若某一非基变量检验数为零，则该问题可能有解。4、关键路线是从起点到终点所有路中的最路，它的线路时差为。5、求支撑树有法和法两种方法。四、指派问题：（10分）4现有五个人Ai(i=1,2,3,4,5)被分配去完成完成五项工作Bj(j=1,2,3,4,5)，每人只能完成一项工作，且每项工作只能有一人来完成，每人完成每项工作所花费的费用如下表，请求使总费用最小的最优解。人员任务B1B2B3B4B5A1127979A289666A3717121412A415146610A54107106五、规划问题：（7分）用单纯形法求解某线性规划问题得如下单纯形表：cj1008000S基变量x1x2x3x4ac013/10-1/512bd10-1/102/516cj-zjef-14-24g（1）上述问题是求maxS=100x1+80x2,x3,x4为松弛变量，则a,b,c,d,e,f,g各为多少，上述表所给出的解是最优解吗？（2）上述问题的对偶问题的解是什么？最优值是什么？六、运输问题：（10分）对如下表的运输方案：（1）若要使总利润最大，该方案是否为最优方案？（2）若问题中B1的需要量改为700，该方案是否为最优方案？（3）填空题：（10分）1、在图论中，图的基本要素有两个，它们是和。2、结点的最早开始时间和时间是同一时间，最早开始是对结点的后接工序而言，是对结点的紧前工序而言。3、对需要量供应量的运输问题，求最优解时要先一个供应点。4、关键路线是从起点到终点所有路中的最路，它的线路时差为。5、在图论中，为了表示两个队比赛的胜负关系可以用一条带的来表示。（4）选择题（10分）1、若T是图G的最小支撑树，则（）A．T必唯一B.G不一定是连通图C．T中必不含圈D.G中不含圈54、若线性规划问题的最优解在可行域的两个顶点达到，则最优解（）。A．有两个B.有无穷多个C.过这两点的直线D.不可能发生5、在n个产地，m个销地的产销平衡运输问题中，（）是错误的。A．运输问题是线性规划问题B．基变量的个数是数字格的个数C．空格有mn-n-m+1个D．每一格在运输图中均有一闭合回路一、判断题（10分）1、用单纯形法求解标准型式的线性规划问题时，与j0对应的变量都可以被选作换入变量。（）2、对偶问题的对偶一定是原问题。（）3、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。（）4、指派问题效率矩阵地每个元素都乘以同意常数k，将不影响最优指派方案。（）5、求网络最大流的问题可归结为求解一个线性规划模型。（）二、规划问题（16分）已知线性规划问题)4,3,2,1(032min32326532432143214321jzxxxxxxxxxxxxxj（1）写出其对偶问题；（2）用图解法求对偶问题的解；（3）利用（2）的结果及对偶性质求原问题解。三、运输问题（10分）某土石方从三个产地运往四个工地，产地的产量、工地的需求量及单位运费如下表，求最优运输方案。产地销地B1B2B3B4产量A13113107A219284A3741059销量3656四、支撑树问题（6分）求下面网络图的最小支撑树：6五、运输问题（10分）求总运费最小的运输问题，某步运输图如下：(1)写出a,b,c,d,e的值，并求出最优运输方案；(2)A3到B1的单位运费满足什么条件时，表中运输方案为最优方案。六、指派问题（10分）分配甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间如下表，试确定总花费时间为最少的指派问题。人任务ABCDE甲127979乙89666丙71712149丁15146610戊4107109七、求下图所示容量网络中从vs～vt的最大流。其中每边上的数为),(fcijij。78一、多项选择题（18分）1、下面命题正确的是（）。A、线性规划的最优解是基本可行解；B、基本可行解一定是基本解；C、线性规划一定有可行解；D、线性规划的最优值至多有一个。2、一个线性规划问题（P）与它的对偶问题（D）有关系（）。A、（P）有可行解则（D）有最优解；B、（P）、（D）均有可行解则都有最优解；C、（P）可行（D）无解，则（P）无有限最优解；D、（P）（D）互为对偶。3、运输问题的基本可行解有特点（）。A、有m＋n－1个基变量；B、有m+n个位势；C、产销平衡；D、不含闭回路。4、关于动态规划问题的下列命题中（）是错误的。A、动态规划分阶段顺序不同，则结果不同；B、状态对决策有影响；C、在求解最短路径问题时，标号法与逆序法求解的思路是相同的；D、动态规划的求解过程都可以用列表形式实现。9二、计算题1、某公司下属的3个分厂A1、A2、A3生产质量相同的工艺品，要运输到B1、B2、B3、B4，4个销售点，分厂产量、销售点销量、单位物品的运费数据如下：求最优运输方案。2、考虑下列线性规划：最优单纯形表为：（1）、写出此线性规划的最优解、最优基B和它的逆B-1；（2）、求此线性规划的对偶问题的最优解；（3）、试求c2在什么范围内，此线性规划的最优解不变；（4）、若b1=20变为45，最优解及最优值是什么？3、某公司决定投资60万元（以10万元为单位），以提高三种主要产品A、B、C的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下：10试确定如何安排对各种产品的投资数，可获得最大总期望利润？一、有下面线性规划：3.2.1,020102..2max321321321jtszxxxxxxxxxxj要求：1、用单纯性发就解该线性规划问题；2、写出该问题的对偶规划；3、利用原问题的最优解和互补松弛性，直接秋池对偶问题的最优解；4、利用原问题的最后一张单纯形表，直接秋池对偶问题最优解。二、某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如下表所示。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总的运费最小。产地需地B1B2B3B4产量A1291079A213425A334257需求量3846三、已知下图表示7个城市间拟建一条连接各个城市的通讯线路，各边的权数表示两个城市之间的修建费用，求连接各城市通讯线路最修修建费用方案。11四、下图中vs表示仓库，vt表示商店，现要从仓库运10单位的物资到商店，应如何调运才能使运费最省（图中狐表示交通线，狐旁数字为（cij,bij）cij表示交通线上运输能力限制，bij表示单位运价。五．网络计划问题：12