运筹学填空题

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

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

3、若化为标准形式，需要引入一松弛变量。19.如果某个变量Xj为自由变量，则应引进两个非负变量Xj , Xj, 同时令XjXj Xj。20.表达线性规划的简式中目标函数为max(min)Z=cijxij。第三章 线性规划的基本方法填空题1线性规划的代数解法主要利用了代数消去法的原理，实现基可行解的转换，寻找最优解。2标准形线性规划典式的目标函数的矩阵形式是_ maxZ=CBB1b+(CNCBB1N)XN 。3对于目标函数极大值型的线性规划问题，用单纯型法求解 时，当基变量检验数j_0时，当前解为最优解。4用大M法求目标函数为极大值的线性规划问题时，引入的人工变量在目标函数中的系数应为M。5在单纯形

4、迭代中，可以根据最终_表中人工变量不为零判断线性规划问题无解。6在线性规划典式中，所有基变量的目标系数为0。7当线性规划问题的系数矩阵中不存在现成的可行基时，一般可以加入人工变量构造可行基。8在单纯形迭代中，选出基变量时应遵循最小比值法则。9线性规划典式的特点是基为单位矩阵，基变量的目标函数系数为0。10对于目标函数求极大值线性规划问题在非基变量的检验数全部jO、问题无界时，问题无解时情况下，单纯形迭代应停止。11在单纯形迭代过程中，若有某个k>0对应的非基变量xk的系数列向量Pk_0_时，则此问题是无界的。12在线性规划问题的典式中，基变量的系数列向量为单位列向量_13.对于求极小值而

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

6、相应的目标函数值将增加3k 。7线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y= CBB1。8若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX= Yb。9若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CXYb。10若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX=Y*b。 11设线性规划的原问题为maxZ=CX，Axb，X0，则其对偶问题为min=Yb YAcY0_。 12影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。 13线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为AT 。 14在对偶单纯形法迭

7、代中，若某bi<0，且所有的aij0(j=1，2，n)，则原问题_无解。第五章 线性规划的灵敏度分析填空题1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。2、在线性规划的灵敏度分析中，我们主要用到的性质是_可行性，正则性。3在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。4如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应出基。5约束常数b；的变化，不会引起解的正则性的变化。6在某线性规划问题中，已知某资源的影子价格为Y1，相应的约束常数b1，在灵敏度容许变动范围内发生b1的变化，则新的最优解对应的最优目标

8、函数值是Z*+yib (设原最优目标函数值为Z)7若某约束常数bi的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用对偶单纯形法求解。8已知线性规划问题，最优基为B，目标系数为CB，若新增变量xt，目标系数为ct，系数列向量为Pt，则当CtCBB1Pt时，xt不能进入基底。9如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个变量。10、若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加一行，一列。11线性规划灵敏度分析应在最优单纯形表的基础上，分析系数变化对最优解产生的影响12在某生产规划问题的线性规划模型中，变量xj的目标系数Cj代表该变

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

10、为顶点所对应的闭回路内进行运量的调整。6按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到_1条闭回路7在运输问题中，单位运价为Cij位势分别用ui，Vj表示，则在基变量处有cij Cij=ui+Vj 。8、供大于求的、供不应求的不平衡运输问题，分别是指_的运输问题、_的运输问题。10在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。 11在某运输问题的调运方案中，点(2，2)的检验数为负值，(调运方案为表所示)则相应的调整量应为300_。IA300100300B400C60030012.若某运输问题初始方案的检验数中只有一个负值：2，则这个2

11、的含义是该检验数所在格单位调整量。13.运输问题的初始方案中的基变量取值为正。14表上作业法中，每一次调整1个“入基变量”。 15.在编制初始方案调运方案及调整中，如出现退化，则某一个或多个点处应填入数字016运输问题的模型中，含有的方程个数为n+M个。17表上作业法中，每一次调整，“出基变量”的个数为1个。18给出初始调运方案的方法共有三种。19.运输问题中，每一行或列若有闭回路的顶点，则必有两个。第七章 整数规划填空题1用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。2在分枝定界法中，若选Xr=43进行分支，则构造的约束条件应为X11，X12。3已

12、知整数规划问题P0，其相应的松驰问题记为P0，若问题P0无可行解，则问题P。无可行解。4在0 - 1整数规划中变量的取值可能是_0或1。5对于一个有n项任务需要有n个人去完成的分配问题，其 解中取值为1的变量数为n个。6分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。7若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+17x3+27x5=137，则以X1行为源行的割平面方程为_X3X50_。8在用割平面法求解整数规划问题时，要求全部变量必须都为整数。9用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部

13、系数化为整数。10求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法_。11求解01整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。 12在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零元素_。13.分枝定界法一般每次分枝数量为2个.第八章 图与网络分析填空题1图的最基本要素是点、点与点之间构成的边 2在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。3在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。4在图论中，图是反映研究对象_之间_特定关系的一种工具。5任一树中的边数必定是它的点数减1。6最小

14、树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。7最小树的算法关键是把最近的未接_结点连接到那些已接结点上去。8求最短路问题的计算方法是从0fijcij开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。动态规划石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的B1、B2、B3;C1、C2、C3;D1、D2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？3AED2D1C3C2C1B3B2 B1 6 2 55 3 23

15、 3 4 5 7 4 4 4 4 1 5 4 5 解：第四阶段：D1E 3；D2E 4；第三阶段：C1D1E 5；C2D2E 8；C3D1E 8；C3D2E 8；第二阶段：B1C1D1E 11；B1C2D2E 11；B2C1D1E 8； B3C1D1E 9 ；B3C2D2E 9；第一阶段：AB1C1D1E 14；AB1C2D2E 14； AB2C1D1E 13；AB3C1D1E 13；AB3C2D2E 13；最优解：AB2C1D1E；AB3C1D1E；AB3C2D2E最优值：13最小生成树问题 某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中V1，V7表示7

16、个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。584723431031V7V4V5V6V1V2V3G 5847234331V7V4V5V6V1V2V3G1 解：在G中找到一个圈（V1，V7，V6，V1）,并知在此圈上边V1，V6的权数10为最大，在G中去掉边V1，V6得图G1 ，如上图所示 5472343131V7V4V5V6V1V2V3G2 472343131V7V4V5V6V1V2V3G3 在G1中找到一个圈（V3，V4，V5，V7，V3），去掉其中权数最大的边 V4，V5，得图G2 ，如上图

17、所示在G2中找到一个圈（V2，V3，V5，V7，V2），去掉其中权数最大的边 V5，V7，得图G3 ，如上图所示72343131V7V4V5V6V1V2V3G47233131V7V4V5V6V1V2V3G5在G3中找到一个圈（V3，V5，V6，V7，V3），去掉其中权数最大的边 V5，V6，得图G4 ，如上图所示在G4中找到一个圈（V2，V3， V7，V2），去掉其中权数最大的边 V3，V7，得图G5 ，如上图所示在G5中已找不到任何一个圈了，可知G5即为图G的最小生成树。这个最小生成树的所有边的总权数为3+3+3+1+2+7=19（18,3）(13)某一个配送中心要给一个快餐店送快餐原料，应

18、按照什么路线送货才能使送货时间最短。下图给出了配送中心到快餐店的交通图，图中V1，V7表示7个地名，其中V1表示配送中心，V7表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段道路所需要的时间（单位：分钟）（27,5）（25,4）（24,3）（4,1）V4（16,2）（0,S）5V26V26V28V27V22V212V216V218V24V2V1V7（快餐店）（配送中心）V5V3V6V2解：给起始点V1标号为（0，S） I=V1,J= V2，V3，V4，V5，V6 ,V7 ，边的集合Vi，Vj Vi，Vj两点中一点属于I,而另一点属于J= V1，V2， V1，V3，

19、并有 S12=L1+C12=0+4=4 ； S13=L1+C13=0+18=18min (S12,S13)= S12 =4给边 V1，V2中的未标号的点V2 标以（4，1），表示从V1 到V2 的距离为4，并且在V1到V2的最短路径上V2的前面的点为V1.这时I=V1 ，V2,J=V3，V4，V5，V6 ,V7，边的集合Vi，Vj Vi，Vj两点中一点属于I,而另一点属于J= V1，V3， V2，V3， V2，V4，并有S23=L2+C23=4+12=16 ；S24=L2+C24=4+16=20 ；min (S23,S24 , S13)= S23 =16给边 V2，V3中的未标号的点V3 标以

20、（16，2）这时I=V1 ，V2 ，V3,J=V4，V5，V6 ,V7，边的集合Vi，Vj Vi，Vj两点中一点属于I,而另一点属于J= V2，V4， V3，V4， V3，V5，并有S34=L3+C34=16+2=18 ； S35=L3+C35=16+6=22 ； S24=L2+C24=4+16=20min (S34,S35,S24)= S34 =18给边 V3，V4中的未标号的点V4 标以（18，3）这时I=V1 ，V2 ，V3 ，V4,J=V5，V6 ,V7，边的集合Vi，Vj Vi，Vj两点中一点属于I,而另一点属于J= V4，V6， V4，V5， V3，V5，并有S46=L4+C46=

21、18+7=25 ； S45=L4+C45=18+8=26 ；min (S46,S45 ,S35)= S35 =24给边 V3，V5中的未标号的点V5 标以（24，3）这时I=V1 ，V2 ，V3 ，V4 ，V5 ,J= V6 ，V7，边的集合Vi，Vj Vi，Vj两点中一点属于I,而另一点属于J= V5，V7， V4，V6 ，并有S57=L5+C57=22+5=27 ；min (S57,S46)= S46 =25给边 V4，V6中的未标号的点V6 标以（25，4）这时I=V1 ，V2 ，V3 ，V4 ，V5 ，V6 ,J= V7，边的集合Vi，Vj Vi，Vj两点中一点属于I,而另一点属于J=

22、 V5，V7， V6，V7 ，并有S67=L6+C67=25+6=31 ；min (S57,S67)= S57 =27给边 V5，V7中的未标号的点V7 标以（27，5）此时I=V1 ，V2 ，V3 ，V4 ，V5 ，V6 ，V7,J=空集，边集合Vi，Vj Vi，Vj两点中一点属于I,而另一点属于J=空集，计算结束。得到最短路。从V7 的标号可知从V1 到V7 的最短时间为27分钟。 即：配送路线为： V1 V2 V3 V5 V7最小生成树问题某电力公司要沿道路为8个居民点架设输电网络，连接8个居民点的道路图如图所示，其中V1，V8表示8个居民点，图中的边表示可架设输电网络的道路，边上的赋权

23、数为这条道路的长度，单位为公里，请设计一个输电网络，联通这8个居民点，并使总的输电线路长度为最短 。275623432524V8V7V6V5V4V3V1V2G在图中找到一个圈（V1，V2，V5，V3）,并知在此圈上边V1，V2和V3，V5的权数4为最大，在图中去掉边V1，V2 ；在图中找到一个圈（V3，V4，V8 ，V5 ，V3, V1），去掉其中权数最大的边 V4，V8；在图中找到一个圈（V3，V4， V5，V3），去掉其中权数最大的边 V4，V5；在图中找到一个圈（V5，V2，V6，V7 ，V5），去掉其中权数最大的边 V2，V6；在图中找到一个圈（V5，V7， V8，V5），去掉其中权数

24、最大的边 V5，V8。在图中已找不到任何一个圈了，可知此即为图G的最小生成树。这个最小生成树的所有边的总权数为2+2+4+2+3+3+2=18最大流问题某地区的公路网如图所示，图中V1，V6为地点，边为公路，边上所赋的权数为该段公路的流量（单位为千辆/小时），请求出V1 到V6 的最大流量。 65125641066V6V5V2V4V1V38 解：第一次迭代：选择路为V1 V3 V6 。弧（V3 ，V6）的顺流流量为5，决定了pf=5，改进的网络流量图如图所示：第一次迭代后的总流量55555000000V4000065125641066V6V5V2V1V380第二次迭代：选择路为V1 V2 V5

25、 V6 。弧（V1 ，V2）的顺流流量为6，决定了pf=6，改进的网络流量图如图所示：第二次迭代后的总流量111106266655500000V40006512 6466V6V5V2V1V380第三次迭代：选择路为V1V4 V6 。弧（V1 ，V4）的顺流流量为6，决定了pf=6，改进的网络流量图如图所示：第三次迭代后的总流量171706060626665550000V40065646V6V5V2V1V3第四次迭代：选择路为V1V3V4 V2V5V6 。弧（V2 ，V5）的顺流流量为2，决定了pf=2，改进的网络流量图如图所示：第四次迭代后的总流量19193742220880606062666

26、555000V40564V6V5V2V1V34第五次迭代：选择路为V1V3V4V5V6 。弧（V1 ，V3）的顺流流量为3，决定了pf=3，改进的网络流量图如图所示：第五次迭代后的总流量222203111523111474222088060606500V45V6V5V2V1V3在通过第五次迭代后在图中已找不到从发点到收点的一条路上的每一条弧顺流容量都大于零，运算停止。我们已得到此网络的从 V1到V6的最大流量，最大流量为22，也就是公路的最大流量为每小时通过22千辆车。最小费用最大流问题请求下面网路图中的最小费用最大流,图中弧(Vi , Vj)的赋权（Cij , bij），其中Cij为从Vi 到Vj 的流量，bij 为Vi 到Vj 的单位流量的费用。（5，2）（1，2）（2，4）（1，1）（3，3）（4，1）（5，3）（2，4）V6V5V4V3V2V1（1，2）一、填空题：（每空格2分，共16分）1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种