管理运筹学复习题讲解.doc

复习题 一、问答题 1、线性规划最优解的存在有哪几种情况？简述各种情况在单纯形法求解过程中的表现？ 1(1)、在遇到退化的基可行解时、单纯形法求解出现循环时如何处理？ 2、什么是影子价格？影子价格有什么作用？ 3、什么是平衡运输问题？该类问题数学模型上有什么样的特征？ 4、分支定界法包含两个重要概念，即“分支”和“定界”。试述这两个概念的基本含义！ 5、什么是增广链？如何确定调整量？如何确定新的流？ 6、试阐述具有不同等级目标规划求解的基本过程。 7、试述目标规划问题的解决思路。 8、在图论中什么是最小生成树，试述破圈法求最小生成树的方法。 9、图论中的图的涵义是什么？ 10、在图论中什么是生成子图？ 11、在图论中网络的含义是什么？ 12、如何识别线性规划问题有多重最优解？ 13、如何识别运输问题有多重最优解？ 一、问答题 1、答：线性规划问题的最优解主要存在四种情况： 1）唯一最优解。判断条件：单纯形最终表中所有非基变量的检验数均小于零 2）多重最优解：判断条件：单纯形最终表中存在至少一个非基变量的检验数等于零。 3）无界解。判断条件：单纯形法迭代中某一变量的检验数大于零，同时它所在系数矩阵列中的所有元素均小于等于零 4）无可行解。判断条件：在辅助问题的最优解中，至少有一个人工变量大于零 2、答：把在一定条件下的最优生产方案中，某种资源增加或减少一个单位给总收益带来的改变量，称为此种资源在一定条件的影子价格。作用：a.能为经理的经营决策提供重要的指导（可举例说明）b.为重新分配一个组织内的资源提供依据。 3、答：平衡运输问题指的是总供给等于总需求的运输问题。其特点如下： 1）系数矩阵全部由0和1两种元素值组成，前m行每行有n个1，后n行每行有m个1。每列又且只有2个1，Pij向量的1分别在第i行和第m+j行。 2）共有m*n个决策变量，m+n个约束方程，基变量却只有m+n-1个。 3）任何一个平衡运输问题至少有一个最优解 4、答：“分支”：若xk不为整数，将对应的线性规划问题分别加入两个不等式，即和。“定界”：如果在分支过程中的某一步求得了一个可行整数解，它对应的目标函数值为z0 ,则把z0 作为一个界，以便提高计算效率。 5、答：设f={fij}是D中的一个可行流，若存在一条{vs-vt}链u，满足：1）对一切（i，j）∈u+,有fijcij; 2) 对一切（i，j）∈u-,有fij0; 则称u是一条关于{vs-vt}的增广链 新的流为： 6、答：首先求出目标规划的最优先级目标解，然后把已经求得的优先级的目标最优解作为下一优先级目标规划的约束条件来求解，以此类推，逐级求得所有优先级的目标最优解。 7、答：首先对于管理部门提出的每一个目标，由决策者确定一个具体的数量目标，并对每一个目标建立目标函数，然后寻求一个使目标函数和对应目标之间的偏差之和达到最小的解. 8、答：无圈的、最小的、连通的生成子图；在连通图中逢圈去掉最大的边。 9、答：具有表达对象之间特定关系的含义（如朋友关系，地点之间的通路关系） 10、答：在给定的无向图G(V,E)中，保留G中所有的点，而删掉G的部分边剩下（或保留）部分边所得到的图称为图G的生成子图。 11、答：在赋权有向图D（V,A）中指定了一个点（Vs），称为为发点,指定另一个点（Vt）为收点,其余的点为中间点，并把D中的每一条弧的赋权数Cij称之为弧（Vi,Vj）的容量,这样的赋权有向图D就称之为网络。 12、答：看在单纯形方法的最优解中是否存在非基变量的检验数为零的情况。如果存在，则存在最优解。 13、答：看在运输问题的最优方案是否存在非基变量的检验数为零。如果存在，则存在最优解。 二、判断下列说法的正确性（☆---对，¤---错） 1、线性规划问题可行解X为基可行解的充分必要条件是X的正分量所对应的系数列向量是线性独立的。☆ 2、线性规划模型的每一个基可行解对应可行域的一个顶点。☆ 3、如线性规划问题的标准型为型，则当检验数时，相应的基可行解是最优解。☆ 4、若原问题第i个约束条件为严格的不等式，则第i个对偶变量的最优值yi*=0。☆ 5、根据弱对偶定理，当x,y分别是和的可行解，则。¤ 6、若线性规划问题的原问题无可行解，则其对偶问题无可行解。¤ 7、若序列{Vs , V1 , V2 ,……，Vn-1 , Vn }是从Vs到Vn的最短路，则序列{Vs , V1 , V2 ,……，Vn-1 }必定是Vs到Vn-1的最短路。☆ 8、表上作业法实质上是单纯形法在求解运输问题的一种简化方法。☆ 9、整数规划的目标函数值一般优于相应的线性规划问题的目标函数值。¤ 10、目标规划问题中，当目标允许超额完成时（如利润、产值），则目标函数的表达式为。¤ 10-1目标规划问题