复习题
一、问答题
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不为整数，将对应的线性规划问题分别加入两个不等式，即xk??bk?和xk??bk??1。“定界”：如果在分支过程中的某一步求得了一个可行整数解，它对应的目标函数值为z0 ,则把z0 作为一个界，以便提高计算效率。
5、答：设f={fij}是D中的一个可行流，若存在一条{vs-vt}链u，满足：1）对一切（i，j）
1
∈u+,有fij 2) 对一切（i，j）∈u-,有fij>0; 则称u是一条关于{vs-vt}的增广链 ?1?mincij?fij*,?2?minfij*,则调整量??min??1,?2? (i,j)???(i,j)????????fij*??,若(i,j)?????*?新的流为：fij'??fij??,若(i,j)?? ?*??fij，若(i,j)??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、如线性规划问题的标准型为max型，则当检验数?j?CBB?1Pj?Cj?0时，相应的基可行解是最优解。☆ 4、若原问题第i个约束条件为严格的不等式，则第i个对偶变量的最优值yi*=0。☆ 5、根据弱对偶定理，当x,y分别是maxcTX,s.t.AX?b,X?0和 minbTY,s.t.ATY?c,Y?0的可行解，则cTX?bTY。¤ 6、若线性规划问题的原问题无可行解，则其对偶问题无可行解。¤ 7、若序列{Vs , V1 , V2 ,??，Vn-1 , Vn }是从Vs到Vn的最短路，则序列{Vs , V1 , V2 ,??，Vn-1 }必定是Vs到Vn-1的最短路。☆ 8、表上作业法实质上是单纯形法在求解运输问题的一种简化方法。☆ 9、整数规划的目标函数值一般优于相应的线性规划问题的目标函数值。¤ 2 10、目标规划问题中，当目标允许超额完成时（如利润、产值），则目标函数的表达式为minf(d)?di。¤ 10-1目标规划问题中，当要求不低于目标值（如利润、产值）时，则目标函数的表达式为minf(d)?di☆ 11、在对需要引入人工变量构成原线性规划辅助问题的单纯形法求得的最优解中，若人工变量不等于零，则说明原问题没有可行解。☆ 12、如不按最小比值原则选取换出基变量，则在下一个解中至少有一个基变量的值为负值。☆ 13、单纯法计算中，选取最大的正检验数б使目标函数值得到最快的增长。¤ 14、若X、X分别是某一线性规划问题的最优解，λλ1X +λ ^k??对应的变量 xk作为换入变量 ，将 121、λ 2为任意实数，则X= 1X也是该问题的最优解。¤ 2^215、设x，y分别为标准形式为最大化的原问题与对偶问题的可行解， xji*j， y*i分别是其最优解，则恒有 ?cxj?1jn^j≥?j?1ncx??byj*ji?1im*i≥?i?1mbyi*i^i。¤ 16、已知 y*i是线性规划对偶问题的最优解，若 y*〉0，说明在最优生产计划中 第i种资源已完全耗尽。☆ 16-1已知yi是线性规划对偶问题的最优解，若yi=0，说明在最优生产计划中第 *i种资源的消耗未超过界限值。 17、若线性规划问题中的 c，b值同时发生变化，反映到最终单纯形表中，不 ji会出现原问题与对偶问题均为非可行解。¤ 18、按表上作业法(最小元素法或左上角法）给出的初始基可行解，从每个空格出发可以找出而且仅能找出唯一的闭回路。☆ 18-1表上作业法(最小元素法或左上角法等）每次给出一个格点取值后，总是划去满足的一行或一列（若行与列同时满足则只划去其一），以保证所有填上数字（包括填上“0” ）的格点（基变量所在的点）不形成闭回路。 19、当所有产地的产量和销地的销量均为整数时，运输问题的最优解也为整数。☆ 20、目标规划模型中，应同时包含绝对约束与目标约束。¤ 3 21、指派问题效率矩阵的每一个元素都乘上同一个常数k将不影响最优指派方案。¤ 22、若序列{Vs , V1 , V2 ,??，Vn-1 , Vn }是从Vs到Vn的最短路，则序列{ V2,??，Vn }必定是V2到Vn的最短路。 22-1若序列{Vs , V1 , V2 ,??，Vn-1 , Vn }是从Vs到Vn的最短路，则序列{ V1,??，Vn-1 }必定是V1到Vn-1的最短路。 三、算法题 1、已知线性规划问题： minz?2x1?x2?2x3?kx1?x2?x3?4 ??x?x?x?6?123?x?0,x?0,x无约束23?1其最优解为x1=-5,x2=0,x3=-1 1)写出并求其对偶问题的最优解；2）求k的值。 、 maxw?4y1?6y2?ky1?y2?2?1、答：其对偶问题为：?y1?y2??1 ??y1?y2?2??y1无约束，y2?0 由z*=w* 可得 4y1?6y2?2?(?5)?0?2?(?1)??12 由对偶问题第三约束式得y1?y2?2 解得 y1?0,y2??2 由互补松弛性可得 ky1?y2?2， 并代入y1?0,y2??2可得： 0?k?(?2)?2,故k?1 1、已知线性规划问题： minz?2x1?x2?2x3??x1?x2?x3?4 ??x?x?kx?6?123?x?0,x?0,x无约束23?1其最优解为x1=-5,x2=0,x3=-1 4
相关推荐：
loading