雨课堂学堂在线学堂云《高级运筹学（中国石油大学（华东））》单元测试考核答案

第1题动态规划中的状态应具有如下性质：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展，即无后效性。第2题动态规划的最优决策具有如下的性质：无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。第3题动态规划中，如果每个阶段都是最优解，得到的就是最优解，所以动态规划立足局部最优即可，全局最优自然可以得到。第4题企业在生产过程中，需要在整个生产过程中逐月根据库存和需求决定生产计划，则该动态规划的阶段数为12个。第5题风险型决策是指状态确定，各状态发生的概率未知的决策问题第6题动态规划中，允许决策集合是状态变量的函数第7题动态规划的状态转移方程确定了各阶段状态之间的关系第8题最短路问题既可以使用动态规划求解，也可以使用图论求解。第9题无论怎样的动态规划问题，其基本方程都遵循边界为1的条件。第10题动态规划中确定各阶段状态之间的转化关系的方程称为基本方程。第11题交通网络最短距离问题在已知两两点之间距离的情形下可构建离散确定型动态规划模型。第12题动态规划中，阶段指标函数、过程（子过程）上的最优指标函数是状态变量与决策变量的函数第13题动态规划中定义状态时应保证各个阶段中所作决策的相互独立性。第14题如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。第15题动态规划只能用于与时间有关的数学规划建模，如果与时间无关，就不能构建动态规划模型。第16题对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解第17题在用动态规划解题时，定义状态时应保证各个阶段中所作的决策的相互独立型第18题动态规划计算中的“维数障碍”主要是由问题中阶段数的急剧增加而引起的第19题假如动态规划问题包含5个变量3个约束，则用动态规划方法求解时将划分为3个阶段，每个阶段由一个5维向量组成第20题设Sk是动态规划的第k阶段的状态，Sk的取值仅取决于S（k-1）阶段的状态和决策，而同S（k-1）阶段之前的状态和决策无关第21题动态规划的基本方程保证各阶段内决策的独立进行，可以不考虑这之前和之后决策如何进行第22题动态规划实质上是阶段上枚举，过程上寻最优第23题动态规划中状态转移方程表明了各阶段之间状态的联系第24题动态规划过程指标函数必须由阶段指标函数相加得到第1题在任一图G中，当点集V确定后，树图是G中边数最少的连通图。第2题任一图中奇点的个数可能为奇数个，也可能为偶数个。第3题图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。第4题一个图G是树的充分必要条件是边数最少的无孤立点的图。第5题如果一个图G从V1到各点的最短路是唯一的，则连接V1到各点的最短路，再去掉重复边，得到的图即为最小支撑树。第6题图G的最小支撑树中从V1到Vn的通路一定是图G从V1到Vn的最短路。第7题{fij=0}总是最大流问题的一个可行流。第8题无孤立点的图一定是连通图。第9题图中任意两点之间都有一条简单链，则该图是一棵树。第10题求网络最大流的问题总可以归结为求解一个线性规划问题。第11题在图中求一点V1到另一点Vn的最短路问题总可以归结为一个整数规划问题第12题图G中的一个点V1总可以看成是G的一个子图。第13题如果图T是树，则T中一定存在两个顶点，它们之间存在两条不同的链。第14题利用破圈法求赋权图的最小支撑树时，每次都是任取一个圈并去掉其中权最小的边，直到该赋权图不再含圈时，便得到最小支撑树。第15题任一图G=(V,E)都存在支撑子图和支撑树。第16题在任一图G中，当点集v确定后，树图是G中边数最少的连通图。第17题最短路问题既可以使用动态规划求解，也可以使用图论求解。第18题连通无圈的图必定是树。第19题一个连通图中的最小树是唯一确定的。第20题图论中点表示研究对象，边或有向边表示研究对象之间的特定关系。第21题图论中的图，用点与点的相互位置，边的长短曲直来表示研究对象的相互关系。第22题图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。第23题图论中的边表示研究对象，点表示研究对象之间的特定关系。第24题最小树是一个网络中连通所有点而边数最少的图第25题最小树是一个网络中连通所有的点，而权数最少的图第三章作业第1题网络计划中工序的总时差为零，是该工序在关键路线上的充分必要条件。第2题单代号和双代号网络图的最大区别在于后者可以描述滞后关系，前者则无法实现。第3题在网络图中只能存在一个始点和一个终点。第4题用最长、最短和最可能三个时间描述的网络图为非肯定型网络图，即概率网络图。第5题交通网络最短距离问题在已知两两点之间距离的情形下可构建离散确定型动态规划模型。第6题按网络图的综合程度分类，同一个任务可以画成几种详略程度不同的网络图：总网络图、一级网络图、二级网络图等各级网络图中工作和事项可以不必统一编号。第7题以同一结点为开始事件的各项作业的最早开始时间相同。第8题一个网络图有唯一的关键路线。第9题关键路线是网络图中工期最长的路线。第10题网络图中任何一个结点都表示前一工序的结束和后一工序的开始。第11题结点最早时间同最迟时间相等的点连接的线路就是关键路线。第12题若需将某工程项目工期缩短到了10天，简单可行的方法是:任意找出该项目网络中一条关键路线，采取必要措施将其缩短到10天即可。第13题在网络图中，允许工序有相同的开始和结束事件。第14题双代号网络图上,关键路线的重要性在于这条路线上的工序与其他工序相比有非常高的质量要求。第15题双代号网络图上,关键路线重要性在于其路长等于整个工程的总工期。第16题双代号网络图上,最早开工的工序不能多于一个。第17题双代号网络图上,最迟完工的工序不能多于一个。第18题双代号网络图中可以有缺口和回路。第19题某事项的最早时间应能保证其紧前事项都已完工。第20题虚工作的工时为零。第21题网络计划中的总工期等于各工序时间之和。第22题因网络图中工作时间的变化，关键路线也可能发生变化。第23题任何虚工作都不可能包含在关键路线中。第24题后续工序是紧后工序。第25题在网络图中，关键路线一定存在。第四章作业第1题灵敏度分析时，如果价值系数cj发生变化，只需要在最终单纯形表中更改相应的cj行和CB列，继续迭代即可。第2题原问题有几个约束条件，对偶问题就会有几个约束条件，它们之间是一一对应的关系。第3题如果原问题是非可行解，对偶问题也是非可行解，此时通常需要用对偶单纯形法继续迭代。第4题对偶问题的对偶是原问题，且是唯一的。第5题线性规划原问题无可行解，其对偶问题必无可行解。第6题如果x*和y*分别是原问题和对偶问题的可行解，二者对应的目标函数值相等，则二者也分别是原问题和对偶问题的最优解。第7题对于企业而言，影子价格与市场价格含义相同，都是由企业内外部环境决定的，单凭单一企业，无法决定影子价格与市场价格。第8题任何线性规划问题都具有唯一的对偶问题。第9题原问题有几个约束条件（决策变量正、负或正负不限的约束条件除外)，对偶问题就有几个决策变量。第10题任何线性规划问题都有对偶问题，而且对偶问题的形式不唯一。第11题通过单纯形表中检验数行可以获知对偶问题决策变量的解，即其相反数就是对偶问题的解。第12题如果原问题有可行解，对偶问题也必定有可行解。第13题对偶单纯形每一步迭代都要保证检验数行Cj-Zj≤0。第14题如果对偶问题为无界解，那么原问题可能无界也可能无可行解。第15题若线性规划的原问题和对偶问题都有最优解，则两个最优解相同。第16题若线性规划的原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。第17题如果线性规划问题增加一个新的约束条件，则可以先检验原线性规划模型最优解是否满足新约束条件，如果满足，最优解将保持不变。第18题进行灵敏度分析的目的主要是看参数对最优解或最优基的影响，考察解的稳定性。第19题资源的影子价格如果大于在纯市场经济条件下的市场价格，那么最好将其卖出，获得更大的收益。第20题如果有某种资源的影子价格为0，表明这种资源在企业中的作用不大，甚至更多时候是非紧缺资源。第21题若某种资源的影子价格等于k，在其他条件不变的情况下，该种资源增加5个单位时，相应的目标函数值将增加5k。第22题对偶单纯形法解最⼤化线性规划问题时，每次迭代要求单纯形表中A检验数都不⼩于零B检验数都⼤于零C基变量取值列元素不⼩于零D检验数都不⼤于零第五章作业第1题表上作业法实质上就是求解运输问题的单纯形法。第2题按最小元素法（或沃格尔法）给出的初始基可行解，从每一空格出发可以找出且仅能找出唯一的闭回路。第3题如果运输问题单位运价表的某一行（或某一列）元素分别加上一个非零常数k，最优调运方案将不会发生变化。第4题如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化。第5题产销不平衡的运输问题中，只要是增加虚拟的产地或销地，其单位运价必定设置为0，与问题的实际应用类型无关。第6题运输问题求解的时候，最小元素法、西北角法和沃格尔法得到的初始调运方案是一样的。第7题运输问题中，只要给出一组含(m+n-1)个非零的{xij}，且满足∑jxij=ai，∑ixij=bj，就可以作为一个初始基可行解。第8题在最终运输表格中，若有空格的检验数为0，则最优解多于一个。第9题由于产销平衡的运输问题系数矩阵的秩为ｍ+ｎ，为了保证运输问题的每步得到的解xij都是基可行解，迭代中基变量的个数应保持为ｍ+ｎ个。第10题当所有产地的产量和销地的销量都为整数时，运输问题最优解也为整数。第11题运输问题表上作业法得到的调运方案，每个空格有唯一的闭回路。第12题运输问题是一种特殊形式的LP问题，因而其求解结果也可能会有唯一的最优解、无穷多个最优解、无界解和无可行解四种情况。第13题同最小元素法、西北角法相比，沃格尔法最接近运输问题最优解，常被用来作为最优解的近似解。第14题运输问题是一种特殊的线性规划问题，其系数矩阵的秩一定比产地与销地的数量和m+n小，但是未必是m+n-1。第15题运输问题是一种特殊形式的LP问题，因而其求解结果也可能会有无可行解的情况。第16题对于求解运输问题的表上作业法，当空格的检验数不是负值时，表明该方案可能是最优解。第17题运输问题中用位势法求得的检验数不唯一。第18题产销不平衡的运输问题不一定有最优解。第19题m+n-1个变量构成基变量组的充要条件是它们不包含闭回路。第20题产地个数为m，销地个数为n的平衡运输问题的系数矩阵，其秩£m+n-1。第21题任何运输问题都存在可行解。第22题运输问题的单纯形法的条件是产量等于销量的平衡运输问题。第23题如果运输问题单位运价表的所有元素同时乘上一个非零常数k，最优调运方案发生变化。第24题运输问题的产销平衡表中有m个产地n个销地，其决策变量的个数有mn个，其数值格有m+n个。第25题在运输问题表上作业法的闭回路调整时，从检验数为负的单元格出发可以找到多条闭回路。第六章作业第1题如果目标规划的目标函数中出现偏差变量大于0的情形，表明该偏差变量对应的目标实际上并未达成，得到的只是满意解而非最优解。第2题目标规划的单纯形法与线性规划的单纯形法在原理上是不同的，因为前者要求所有检验数都大于等于0，后者却相反。第3题在用图解法解目标规划时,首先必须满足所有绝对约束。第4题目标规划模型中，优先因子的优先权要远高于其中的权系数，前者是绝对的，后者只是相对的。第5题由于目标规划模型中允许存在绝对约束，所以目标规划也可能存在无可行解的情形。第6题要求恰好达到目标值的目标函数是min{f(d++d-)}。第7题目标规划模型中应同时包含系统约束（绝对约束）和目标约束第8题目标规划的目标函数由各目标约束的偏差变量及相应的优先因子和权系数构成。第9题如果目标规划模型中不包含任何绝对约束，即只有目标约束，那么该目标规划问题必定存在满意解。第10题在目标规划问题中，正偏差变量取正值，负偏差变量取负值。第11题目标规划比线性规划更加符合实际，而且其本身也可以理解为一种线性规划模型。第12题在目标规划模型中，可以同时包含绝对约束和目标约束。第13题只包含目标约束（即软约束）的目标规划也可能不存在满意解。第14题目标规划模型的目标函数中，既包含决策变量（如x1），又包含偏差变量（如d1-）。第15题目标规划模型中，按照问题的要求可以表示为求max或min。第16题系统约束（绝对约束）中没有正负偏差变量。第17题在建立目标规划模型时，由于约束条件中存在正偏差变量，即超过目标值的部分，所以目标函数可以取最大化。第18题如果目标规划的两个目标没有绝对意义上的轻重差别，则可以设置同样的权系数，但是优先因子可以不同。第19题目标规划问题一定有满意解，但不一定有最优解。第20题当目标规划问题模型中存在x1+x2+d-=4的约束条件，则该约束为系统约束。第21题目标约束一定是等式约束。第22题一对正负偏差变量至少一个大于零。第23题要求不超过目标值的目标函数是min{f(d+)}。第24题超出目标的差值称为正偏差。第25题未达到目标的差值称为负偏差。第七章作业第1题整数规划是指决策变量都要求为整数的数学规划模型，既可以使用分枝定界法求解，也可以使用割平面法求解。第2题纯整数规划要求每个决策变量都是整数，只能用分枝定界法求解。第3题解0-1规划的过滤隐枚举算法中，对于目标函数值劣于过滤条件的解不必判断其可行性。第4题与线性规划类似，整数规划的最优解也必定出现在其松弛问题对应的可行域顶点上。第5题分枝定界法中从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界z。那么，只要其他分支的最优目标函数值中如果有小于z者，则剪掉这一枝，即以后不再考虑了。第6题在分支定界法中，每一个分支均需得到整数解或者无可行解时才终止分支。第7题分枝定界法适用于纯整数规划，但是未必适用于混合整数规划。第8题由于整数规划松弛问题的可行域顶点可能都不是整数可行解，所以整数规划最优解不一定发生在极点。第9题用割平面法求解整数规划时，要求价值系数也必须取整数。第10题整数规划最优解所对应的目标函数值不优于其松弛问题解所对应的目标函数值。第11题分枝定界法是求解整数规划的一种方法，它的分支和定界没有规律，可以任意选取。第12题用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。第13题用分支定界法求解一个最大化的整数规划问题时，任何一个可行解的目标函数值都是该问题目标函数值的下界。第14题分枝定界求解整数规划时,分枝问题的最优解不会优于原(上一级)问题的最优解。第15题指派问题可用求解运输问题的表上作业法求解，反过来运输问题经处理后也可以用匈牙利法求解。第16题一个整数规划问题如存在两个以上最优解，则一定有无穷多最优解。第17题整数规划是指变量取0或1的线性规划。第18题求解整数规划时,可先不考虑变量的整数约束,而求解其相应的线性规划问题,然后对求解结果中为非整数的变量凑整。第19题分枝定界法在需要分枝时必须满足:一是分枝后的所有子问题必须能够求解;二是所有子问题的解集合必须覆盖原问题的解。第20题如果与整数规划相对应的线性规划无可行域,则整数规划也无可行域。第21题整数规划的最优目标函数值不优于与之相对应的线性规划的最优值。第22题将所对应的线性规划的最优解取整来求解整数规划时,由于得不到可行解,因此也得不到最优解。第23题用分枝定界法求解一个极大化的整数规划问题,当得到多于一个可行解时,通常可任取其中一个作为下界值,再进行比较和剪枝。第24题将整数规划相对应的线性规划LP(1)分解为两个待求解的分枝LP(2)和LP(3)后,其中LP(2)求得整数解,LP(3)求得非整数解,尽管LP(2)的目标函数值小于LP(3)的目标函数值,但LP(2)的整数解必定是原问题的最优解。第八章作业第1题如果目标规划的目标函数中出现偏差变量大于0的情形，表明该偏差变量对应的目标实际上并未达成，得到的只是满意解而非最优解。第2题目标规划的单纯形法与线性规划的单纯形法在原理上是不同的，因为前者要求所有检验数都大于等于0，后者却相反。第3题在用图解法解目标规划