运筹学填空题

第二章线性规划的基本概念填空题1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。2．图解法适用于含有两个变量的线性规划问题。3．线性规划问题的可行解是指满足所有约束条件的解。4．在线性规划问题的基本解中，所有的非基变量等于零。5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。7．线性规划问题有可行解，则必有基可行解。8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。9．满足非负条件的基本解称为基本可行解。10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。13．线性规划问题可分为目标函数求极大值和极小_值两类。14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。19.如果某个变量Xj为自由变量，则应引进两个非负变量Xj′,Xj〞,同时令Xj＝Xj′－Xj。20.表达线性规划的简式中目标函数为max(min)Z=∑cijxij。第三章线性规划的基本方法填空题1．线性规划的代数解法主要利用了代数消去法的原理，实现基可行解的转换，寻找最优解。2．标准形线性规划典式的目标函数的矩阵形式是_maxZ=CBB－1b+(CN－CBB－1N)XN。3．对于目标函数极大值型的线性规划问题，用单纯型法求解时，当基变量检验数δj_≤_0时，当前解为最优解。4．用大M法求目标函数为极大值的线性规划问题时，引入的人工变量在目标函数中的系数应为－M。5．在单纯形迭代中，可以根据最终_表中人工变量不为零判断线性规划问题无解。6．在线性规划典式中，所有基变量的目标系数为0。7．当线性规划问题的系数矩阵中不存在现成的可行基时，一般可以加入人工变量构造可行基。8．在单纯形迭代中，选出基变量时应遵循最小比值θ法则。9．线性规划典式的特点是基为单位矩阵，基变量的目标函数系数为0。10．对于目标函数求极大值线性规划问题在非基变量的检验数全部δj≤O、问题无界时，问题无解时情况下，单纯形迭代应停止。11．在单纯形迭代过程中，若有某个δk0对应的非基变量xk的系数列向量Pk_≤0_时，则此问题是无界的。12．在线性规划问题的典式中，基变量的系数列向量为单位列向量_13.对于求极小值而言，人工变量在目标函数中的系数应取-114.(单纯形法解基的形成来源共有三种15.在大M法中，M表示充分大正数。第四章线性规划的对偶理论填空题1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的线性规划问题与之对应，反之亦然。2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。4．对偶问题的对偶问题是原问题_。5．若原问题可行，但目标函数无界，则对偶问题不可行。6．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加3k。7．线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y﹡=CBB－1。8．若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡=Y﹡b。9．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX≤Yb。10．若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡=Y*b。11．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=YbYA≥cY≥0_。12．影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。13．线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为AT。14．在对偶单纯形法迭代中，若某bi0，且所有的aij≥0(j=1，2，…n)，则原问题_无解。第五章线性规划的灵敏度分析填空题1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。2、在线性规划的灵敏度分析中，我们主要用到的性质是_可行性，正则性。3．在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。4．如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应出基。5．约束常数b；的变化，不会引起解的正则性的变化。6．在某线性规划问题中，已知某资源的影子价格为Y1，相应的约束常数b1，在灵敏度容许变动范围内发生Δb1的变化，则新的最优解对应的最优目标函数值是Z*+yi△b(设原最优目标函数值为Z﹡)7．若某约束常数bi的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用对偶单纯形法求解。8．已知线性规划问题，最优基为B，目标系数为CB，若新增变量xt，目标系数为ct，系数列向量为Pt，则当Ct≤CBB－1Pt时，xt不能进入基底。9．如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个变量。10、若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加一行，一列。11．线性规划灵敏度分析应在最优单纯形表的基础上，分析系数变化对最优解产生的影响12．在某生产规划问题的线性规划模型中，变量xj的目标系数Cj代表该变量所对应的产品的利润，则当某一非基变量的目标系数发生增大变化时，其有可能进入基底。第六章物资调运规划运输问题填空题1．物资调运问题中，有m个供应地，Al，A2…，Am，Aj的供应量为ai(i=1，2…，m)，n个需求地B1，B2，…Bn，B的需求量为bj(j=1，2，…，n)，则供需平衡条件为miia1=njib12．物资调运方案的最优性判别准则是：当全部检验数非负时，当前的方案一定是最优方案。3．可以作为表上作业法的初始调运方案的填有数字的方格数应为m+n－1个(设问题中含有m个供应地和n个需求地)4．若调运方案中的某一空格的检验数为1，则在该空格的闭回路上调整单位运置而使运费增加1。5．调运方案的调整是要在检验数出现负值的点为顶点所对应的闭回路内进行运量的调整。6．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到_1条闭回路7．在运输问题中，单位运价为Cij位势分别用ui，Vj表示，则在基变量处有cijCij=ui+Vj。8、供大于求的、供不应求的不平衡运输问题，分别是指miia1_＞njib1的运输问题、miia1_＜njib1的运输问题。10．在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。11．在某运输问题的调运方案中，点(2，2)的检验数为负值，(调运方案为表所示)则相应的调整量应为300_。IⅡⅢⅣA300100300B400C60030012.若某运输问题初始方案的检验数中只有一个负值：－2，则这个－2的含义是该检验数所在格单位调整量。13.运输问题的初始方案中的基变量取值为正。14表上作业法中，每一次调整1个“入基变量”。15.在编制初始方案调运方案及调整中，如出现退化，则某一个或多个点处应填入数字016运输问题的模型中，含有的方程个数为n+M个。17表上作业法中，每一次调整，“出基变量”的个数为1个。18给出初始调运方案的方法共有三种。19.运输问题中，每一行或列若有闭回路的顶点，则必有两个。第七章整数规划填空题1．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。2．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为X1≤1，X1≥2。3．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P。无可行解。4．在0-1整数规划中变量的取值可能是_0或1。5．对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为n个。6．分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，则以X1行为源行的割平面方程为_76－71X3－72X5≤0_。8．在用割平面法求解整数规划问题时，要求全部变量必须都为整数。9．用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法_。11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。12．在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零元素_。13.分枝定界法一般每次分枝数量为2个.第八章图与网络分析填空题1．图的最基本要素是点、点与点之间构成的边2．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。3．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。4．在图论中，图是反映研究对象_之间_特定关系的一种工具。5．任一树中的边数必定是它的点数减1。6．最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。7．最小树的算法关键是把最近的未接_结点连接到那些已接结点上去。8．求最短路问题的计算方法是从0≤fij≤cij开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。动态规划石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的B1、B2、B3;C1、C2、C3;D1、D2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小62335744441545解：第四阶段：D1—E3；D2—E4；第三阶段：C1—D1—E5；C2—D2—E8；C3—D1—E8；C3—D2—E8；第二阶段：B1—C1—D1—E11；B1—C2—D2—E11；B2—C1—D1—E8；B3—C1—D1—E9；B3—C2—D2—E9；第一阶段：A—B1—C1—D1—E14；A—B1—C2—D2—E14；A—B2—C1—D1—E13；A—B3—C1—D1—E13；A—B3—C2—D2—E13；最优解：A―B2―C1―D1―E；A―B3―C1―D1―E；A―B3―C2―D2―E最优值：13最小生成树问题某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中V1，……，V7表示7个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。解：①在G中找到一个圈（V1，V7，V6，V1）,并知在此圈上边[V1，V6]的权数10为最大，在G中去掉边[V1，V6]得图G1，如上图所示5847234331V7V4V5V6V1V2V3G1584723431031V7V4V5V6V1V2V3G423535AB1B2B3C1C2C3D1D2E②在G1中找到一个圈（V3，V4，V5，V7，V3），去掉其中权数最大的边[V4，V5]，得图G2，如上图所示③在G2中找到一个圈（V2，V3，V5，V7，V2），去掉其中权数最大的边[V5，V7]，得图G3，如上图所示④在G3中找到一个圈（V3，V5，V6，V7，