运筹学填空题

1、第二章线性规划的基本概念填空题1 线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。2. 图解法适用于含有两个变量的线性规划问题。3 .线性规划问题的可行解是指满足所有约束条件的解。4 在线性规划问题的基本解中，所有的非基变量等于零。_5 .在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6 .若线性规划问题有最优解，则最优解一定可以在可行域的顶点(极点)达到。7. 线性规划问题有可行解，则必有基可行解。8 如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解 的集合中进行搜索即可得到最优解。9 .满足非负条件的基本解称为基本可行解。10 .在将线性规

2、划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。_11. 将线性规划模型化成标准形式时，“W”的约束条件要在不等式左端加入松弛变量。12 .线性规划模型包括决策(可控)变量，约束条件，目标函数三个要素。13 .线性规划问题可分为目标函数求极大值和极小值两类。14 .线性规划问题的标准形式中，约束条件取等式,_目标函数求极大值所有变量必须非负。 15 .线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16 .在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界 的一切点都是最优解。4用大M法求目标函数为极大值的线性规划问题时，弓I

3、入的人工变量在目标函数中的系数应为5 在单纯形迭代中，可以根据最终 表中人工变量不为零判断线性规划问题无解。6 在线性规划典式中，所有基变量的目标系数为0。7当线性规划问题的系数矩阵中不存在现成的可行基时，一般可以加入人工变量构造可行基。8在单纯形迭代中，选岀基变量时应遵循最小比值B法则。9线性规划典式的特点是基为单位矩阵，基变量的目标函数系数为0。10对于目标函数求极大值线性规划问题在非基变量的检验数全部6j0对应的非基变量Xk的系数列向量Pk_w 0_时，则此问题是无界的12在线性规划问题的典式中，基变量的系数列向量为单位列向量13. 对于求极小值而言，人工变量在目标函数中的系数应取-11

4、4. （单纯形法解基的形成来源共有三种15. 在大M法中，M表示充分大正数第四章 线性规划的对偶理论填空题I 线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的线性规划问题与之对应，反之亦然。2 .在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。3如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。4 对偶问题的对偶问题是原问题 _。5 .若原问题可行，但目标函数无界，则对偶问题不可彳 6 若某种资源的影子价格等于 k。在其他条件不变的情况下（假设原问题的最佳基不变），当该种资源增加3个单位时。相应的目标函数值将增加3k

5、。7 线性规划问题的最优基为 B,基变量的目标系数为 Cb,则其对偶问题的最优解 Y* = CbE1。8 若乂和V分别是线性规划的原问题和对偶问题的最优解，则有CX*=Y *b。9 若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CXC 丫仁10.若X*和V分别是线性规划的原问题和对偶问题的最优解，则有Cx =Y*boII .设线性规划的原问题为 maxZ=CX Axwb，X0,则其对偶问题为min=Yb YAc Y0_。12 影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。13 线性规划的原问题的约束条件系数矩阵为A,则其对偶问题的约束条件系数矩阵为& o14 在对偶单纯

6、形法迭代中，若某bi0（j=1，2，n），则原问题_无解。第五章线性规划的灵敏度分析填空题1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。2、 在线性规划的灵敏度分析中，我们主要用_可行性，正则性。3在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。4如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应岀基。_5.约束常数b;的变化，不会引起解的正则性的变化。6在某线性规划问题中，已知某资源的影子价格为，相应的约束常数 4，在灵敏度容许变动范围内发生 b!的变化，则新的最优解对应的最优目标函数值是、 b （设原最优目

7、标函数值为 Z* ）7若某约束常数b、的变化超过其容许变动范围，为求得新的最优解,需在原最优单纯形表的基础上运用对_ 偶单纯形法求解。8已知线性规划问题，最优基为B,目标系数为Cb,若新增变量Xt，目标系数为G,系数列向量为Pt，则当C w CBE1Pt时，xt不能进入基底。9如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个变量。10、若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加二行，一列。11 线性规划灵敏度分析应在最优单纯形表的基础上，分析系数变化对最优解产生的影响12在某生产规划问题的线性规戈y模型中，变量x的目标系数c代表该变量所对应的产品的利润，

8、则当某一非基变量的目标系数发生增大变化时，其有可能进入基底。六章 物资调运规划运输问题填空题1 物资调运问题中,有m个供应地，A，人，Am, A的供应量为 a（i=1，2,m），n个需求地B，B2,B n，bij 1B的需求量为bj（j=1，2，n），则供需平衡条件为2 物资调运方案的最优性判别准则是：当全部检验数非负时前的方案一定是最优方案。3 可以作为表上作业法的初始调运方案的填有数字的方格数应为m+n-1个（设问题中含有m个供应地和n个需求地）4 若调运方案中的某一空格的检验数为1,则在该空格的闭回路上调整单位运置而使运费增加1 o5 调运方案的调整是要在检验数岀现负值的点为顶点所对应的

9、闭回路内进行运量的调整。一6 按照表上作业法给岀的初始调运方案，瓜每一空格岀发可以找到且仅能找到_丄条闭回路7 .在运输问题中，单位运价为C位势分别用5, V表示，则在基变量处有 Cij Cj=u+V o8、供大于求的、供不应求的不平衡运输问题，分别是指mai _ n b的运输问 蔦-三n b的运输问题。i 1 i _ j 1i 1 i _ j 1 i10.在表上作业法所得到的调运方案中，从某空格岀发的闭回路的转角点所对应的变量必为基变量。11 在某运输问题的调运方案中，点（2 , 2）的检验数为负值，（调运方案为表所示）则相应的调整量应为300 oInmIVA300100300B400C60

10、030012. 若某运输问题初始方案的检验数中只有一个负值：-2，则这个-2的含义是该检验数所在格单位调整13. 运输问题的初始方案中的基变量取值为正。_14表上作业法中，每一次调整1个“入基变量” o15.在编制初始方案调运方案及调整中，如岀现退化，则某一个或多个点处应填入数字 016运输问题的模型中，含有的方程个数为n+M个。17表上作业法中，每一次调整，“岀基变量”的个数为仝。18给岀初始调运方案的方法共有三种。19.运输问题中，每一行或列若有闭回路的顶点，则必有两个。_第七章整数规划填空题1 用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。_2

11、 在分枝定界法中，若选 X=4/ 3进行分支，则构造的约束条件应为XV 1, X& 2 o3 已知整数规划问题 P0，其相应的松驰问题记为 P。，若问题P。无可行解，则问题 Po无可行解。4 .在0 - 1整数规划中变量的取值可能是 _0或1 o5对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为n个。6 分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。7 .若在对某整数规划问题的松驰问题进行求解时，幺得到最优单纯形表中，由Xp所在行得 X+1/7x3+2/7x5=13/7,则以X1行为源行的割平面方程为二比-X5 0_o8 在用割平面法求解整数规划问题时，要

12、求全部变量必须都为整数。_9 用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。10 求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法_o11 求解0 1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。12 .在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零 _o13.分枝定界法一般每次分枝数量为2个.第八章图与网络分析填空题1 图的最基本要素是点、点与点之间构成的边2. 在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。3. 在图论中，通常用点表示研究对象，用边

13、或有向边表示研究对象之间4 在图论中，图是反映研究对象 之间特定关系的一种工具。5.任一树中的边数必定是它的点数减1。6 最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。7 最小树的算法关键是把最近的未接结点连接到那些已接结点上去。8求最短路问题的计算方法是从 Ofj c开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。动态规划石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为目的地，B、C D分别为三个必须建立油泵加压站的地区，其中的Bi、B2、E3;Ci、C、Q;Di、D2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，线段旁的数

14、字为铺设管线所需要的费用，问如何铺设管道才使总费用最小解:CBD3D4 ；A5I44/C2第四阶段：Di E 3 ; D2 E第三阶段：C1 D E 5 ;Cs第二阶段：B1 C D E11B3 C D E9第一阶段：A B G D -EA E2G D EA B Cs DsE;B G Ds E 9 ;14 ; A BCs Ds E 14 ;13 ; A B3C1 D E 13 ;13 ;8 ; C3D E 8 ; C3Ds E 8 ;最优解： A B2 C D E; A- B3G DE; A- B3 C2D2 E最优值：13最小生成树问题V7某大学准备对其所属的 7个学院办公室计算机联网，这个

15、网络的可能联通的途径如图所示，图中V1,表示7个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条路线的长度，单位为百米。请设计 一个网络能联通7个学院办公室，并使总的线路长度为最短。解：在G中找到一个圈（V1，“，V6, V ）,并知在此圈上边V1，V的权数10为最大，在G中去掉边V1，V6得图G，如上图所示在G2中找到一个圈（V2, V3, V5, V V2）,去掉其中权数最大的边V 5, V7，得图G ,如上图所示 在G3中找到一个圈（V3，V5，V6，V V3），去掉其中权数最大的边V 5，V6，得图G ,如上图所示 在G4中找到一个圈（V2，V3，V7，V2），去掉其中权数最

16、大的边V 3，V7，得图G ,如上图所示 在G中已找不到任何一个圈了，可知 G即为图G的最小生成树。这个最小生成树的所有边的总权数为3+3+3+1+2+7=19（13）某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。下图给岀了配送中心到快餐店的交通图，图中 VI，V7表示7个地名，其中V1表示配送中心，V7表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段道路所需要的时间（单位：分钟） 匸Vi,J= V2, V3，V4, Vs，V6 ,V7，边的集合Vi，V | V，V两点中一点属于I,而另一点属于J= Vi,V2 , Vi, V3,并

17、有Si2=Li+C2=0+4=4 ; Si3=Li+Ci3=0+18=18min (S i2,Si3)= S 12 =4给边Vi, VI中的未标号的点 V2标以(4, 1),表示从 V到V2的距离为4,并且在 V到V2的最短路径上 V2的前面 的点为Vi. 这时l=V i , V2,J=V 3, V，边的集合 W | V, V两点中一点属于I,而另一点属于J= Vi,W , V2 , V3 , V 2, V.，并有S23=L2+G3=4+12=16 ; S24=L2+C24=4+16=20 ; min (S 23,S2. , SQ= S 23 =16给边V2, VJ中的未标号的点V3标以(16

18、, 2) 这时I=V1, V3,J=V 4, V5，乂,V7，边的集合Vi,V丨V,V两点中一点属于I,而另一点属于 J= V2,W , V3, V4 , V 3, V,，并有S34=L3+G)4=16+2=18 ; S 35=L3+Gs=16+6=22 ; S 24=L2+G?4=4+16=20min (S 34 ,S 35,S 24)= S 34 =18给边V3, V,中的未标号的点 V4标以(18, 3) 这时I=V1 ,V2,U ,V4,J=V 5,M,V7，边的集合Vi,V I V ,乂两点中一点属于I,而另一点属于 J= V4, VJ , V4, V5 , V 3, VJ，并有S6

19、=L4+G6=18+7=25 ; S 45=L4+G5=18+8=26 ; min (S 46,S 45 ,S 35)= S 35 =24给边V3, M中的未标号的点 V5标以(24, 3) 这时I=V1 , V2 , M , V , M ,J= V , V，边的集合V i , Vj I V , V两点中一点属于I,而另一点属 于 J= V 5, V7 , V 4 , V6 ，并有Ss7=L5+G57=22+5=27 ; min (S 57,S 46)= S 46 =25给边V4, M中的未标号的点 V6标以(25, 4) 这时I=V1 ,V2, V ,V, 乂，VU,J=V7，边的集合V i

20、, V I V, V两点中一点属于I,而另一点属于 J= V 5, V7 , V 6 , V7 ，并有Ss7=L6+G7=25+6=31; min (S 57,S 67)= S 57 =27给边V5, VJ中的未标号的点V7标以(27, 5) 此时I=V1 , V2 , W , V. , * , M , V,J=空集，边集合Vi , V I V, Vj两点中一点属于I,而另一点 属于J=空集,计算结束。 得到最短路。从的标号可知从V1到V7的最短时间为27分钟。即卩：配送路线为：V1 T V2 T Vi T W T V7最小生成树问题某电力公司要沿道路为8个居民点架设输电网络，连接 8个居民点

21、的道路图如图所示，其中V1 ,M表示8个居民点，图中的边表示可架设输电网络的道路，边上的赋权数为这条道路的长度，单位为公里，请设计一个输 电网络，联通这8个居民点,并使总的输电线路长度为最短。 在图中找到一个圈(V, V2 , V, V,),并知在此圈上边V1 , V和V3 , W的权数4为最大,在图中去掉边V1 , M; 在图中找到一个圈（V3,V4,V8,V5,V3,Vi）,去掉其中权数最大的边V4 , V； 在图中找到一个圈（V3 , V4, V5, V3）,去掉其中权数最大的边V4, V5； 在图中找到一个圈（V5，V2，V6，V，V5），去掉其中权数最大的边V2，V6； 在图中找到一

22、个圈（V5，V V，V5），去掉其中权数最大的边V5, Vj。 在图中已找不到任何一个圈了，可知此即为图G的最小生成树。这个最小生成树的所有边的总权数为2+2+4+2+3+3+2=18最大流问题某地区的公路网如图所示，图中Vi,，V6为地点，边为公路，边上所赋的权数为该段公路的流量（单位为千辆/小时），请求岀Vi到V6的最大流量。V3解：第一次迭代：选择路为Vi TV3 TV6。弧（M，V）的顺流流量为5,决定了 Pf=5,改进的网络流量图如图所示:T 5第一次迭代后的总流量第二次迭代：选择路为Vi TV2 TV5 TV。弧（V , V2）的顺流流量为6,决定了 Pf=6,改进的网络流量图如图

23、所示:第二次迭代 后的总流量第三次迭代：选择路为 V1TV4TV6。弧（u , V4）的顺流流量为6, 决定了 pf=6,改进的网络流量图如图所示：17 Vi26 4V26060V317第三次迭代后的总流量第四次迭代：选择路为 Vi W Vl 匕V6。弧（V2 , V5）的顺流流量 为2，决定了 Pf=2，改进的网络流量图如图所示：第五次迭代：选择路为 Vi MU M V6。弧（Vi , V3）的顺流流量为3, 决定了 pf=3,改进的网络流量图如图所示：在通过第五次迭代后在图中已找不到从发点到收点的一条路上的每一条弧顺流容量都大于零，运算停止。我们已得到此网络的从 V到V6的最大流量，最大流

24、量为 22，也就是公路的最大流量为每小时通过22千辆车。最小费用最大流问题请求下面网路图中的最小费用最大流，图中弧（Vi , Vj）的赋权（C , b ij），其中C为从Vi到V的流量，bij为V到V的单位流量的费用。一、填空题：（每空格2分，共16 分）1、线性规划的解有唯一最优解、无穷多最优解、无界解和无可行解四种。2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4,则说明如果在该空格中增加一个运量运费将增加4，这句话对还是错错3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解” 4、如果某一整数规划:MaxZWXeX+9/14X2 51/14-2Xi+Xe 0且均为整数所对应的线性规划（松弛问题）的最优解为X1=3/2，X2=10/3，MaxZ=6/29,我们现在要对 X进行分枝，应该分为X1 25、 在用逆向解法求动态规划时，fk)的含义是：从第k个阶段到第n个阶段的最优解。6. 假设某线性规划的可行解的集合为D,而其所对应的整数规划的可行解集合为B,那么D和B的关系为D包含B7. 已知下表是制订生产计划问题的一张LP最优单纯形表(极大化问题，约束条件均为