1、复习题一、问答题1、线性规划最优解的存在有哪几种情况？简述各种情况在单纯形法求解过程中的表现？1(1)、在遇到退化的基可行解时、单纯形法求解出现循环时如何处理？2、什么是影子价格？影子价格有什么作用？3、什么是平衡运输问题？该类问题数学模型上有什么样的特征？4、分支定界法包含两个重要概念，即“分支”和“定界”。试述这两个概念的基本含义！5、什么是增广链？如何确定调整量？如何确定新的流？6、试阐述具有不同等级目标规划求解的基本过程。7、试述目标规划问题的解决思路。8、在图论中什么是最小生成树，试述破圈法求最小生成树的方法。9、图论中的图的涵义是什么？10、在图论中什么是生成子图？11、在图论中网
2、络的含义是什么？ 12、如何识别线性规划问题有多重最优解？13、如何识别运输问题有多重最优解？一、问答题1、答：线性规划问题的最优解主要存在四种情况：1）唯一最优解。判断条件：单纯形最终表中所有非基变量的检验数均小于零2）多重最优解：判断条件：单纯形最终表中存在至少一个非基变量的检验数等于零。3）无界解。判断条件：单纯形法迭代中某一变量的检验数大于零，同时它所在系数矩阵列中的所有元素均小于等于零4）无可行解。判断条件：在辅助问题的最优解中，至少有一个人工变量大于零2、答：把在一定条件下的最优生产方案中，某种资源增加或减少一个单位给总收益带来的改变量，称为此种资源在一定条件的影子价格。作用：a.
3、能为经理的经营决策提供重要的指导（可举例说明）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 作为一个界，以便提高计算
4、效率。5、答：设f=fij是D中的一个可行流，若存在一条vs-vt链u，满足：1）对一切（i，j）u+,有fij0; 则称u是一条关于vs-vt的增广链新的流为：6、答：首先求出目标规划的最优先级目标解，然后把已经求得的优先级的目标最优解作为下一优先级目标规划的约束条件来求解，以此类推，逐级求得所有优先级的目标最优解。7、答：首先对于管理部门提出的每一个目标，由决策者确定一个具体的数量目标，并对每一个目标建立目标函数，然后寻求一个使目标函数和对应目标之间的偏差之和达到最小的解.8、答：无圈的、最小的、连通的生成子图；在连通图中逢圈去掉最大的边。9、答：具有表达对象之间特定关系的含义（如朋友关系
5、，地点之间的通路关系）10、答：在给定的无向图G(V,E)中，保留G中所有的点，而删掉G的部分边剩下（或保留）部分边所得到的图称为图G的生成子图。11、答：在赋权有向图D（V,A）中指定了一个点（Vs），称为为发点,指定另一个点（Vt）为收点,其余的点为中间点，并把D中的每一条弧的赋权数Cij称之为弧（Vi,Vj）的容量,这样的赋权有向图D就称之为网络。12、答：看在单纯形方法的最优解中是否存在非基变量的检验数为零的情况。如果存在，则存在最优解。13、答：看在运输问题的最优方案是否存在非基变量的检验数为零。如果存在，则存在最优解。二、判断下列说法的正确性（-对，-错） 1、线性规划问题可行解X
6、为基可行解的充分必要条件是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、表上作业法实质上是单纯形法在求解运输问题的一
7、种简化方法。 9、整数规划的目标函数值一般优于相应的线性规划问题的目标函数值。10、目标规划问题中，当目标允许超额完成时（如利润、产值），则目标函数的表达式为。10-1目标规划问题中，当要求不低于目标值（如利润、产值）时，则目标函数的表达式为11、在对需要引入人工变量构成原线性规划辅助问题的单纯形法求得的最优解中，若人工变量不等于零，则说明原问题没有可行解。12、如不按最小比值原则选取换出基变量，则在下一个解中至少有一个基变量的值为负值。13、单纯法计算中，选取最大的正检验数对应的变量作为换入变量 ，将使目标函数值得到最快的增长。14、若X、X分别是某一线性规划问题的最优解，、为任意实数，则X
8、=X +X也是该问题的最优解。15、设，分别为标准形式为最大化的原问题与对偶问题的可行解， ，分别是其最优解，则恒有。16、已知是线性规划对偶问题的最优解，若0，说明在最优生产计划中第i种资源已完全耗尽。16-1已知是线性规划对偶问题的最优解，若=0，说明在最优生产计划中第i种资源的消耗未超过界限值。17、若线性规划问题中的，值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解。18、按表上作业法(最小元素法或左上角法）给出的初始基可行解，从每个空格出发可以找出而且仅能找出唯一的闭回路。18-1表上作业法(最小元素法或左上角法等）每次给出一个格点取值后，总是划去满足的一行
9、或一列（若行与列同时满足则只划去其一），以保证所有填上数字（包括填上“0” ）的格点（基变量所在的点）不形成闭回路。19、当所有产地的产量和销地的销量均为整数时，运输问题的最优解也为整数。20、目标规划模型中，应同时包含绝对约束与目标约束。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的最短路。三、算法
10、题1、已知线性规划问题：其最优解为x1=-5,x2=0,x3=-11)写出并求其对偶问题的最优解；2）求k的值。、1、答：其对偶问题为：由z*=w* 可得 由对偶问题第三约束式得解得 由互补松弛性可得 ，并代入可得： 1、已知线性规划问题：其最优解为x1=-5,x2=0,x3=-11)写出并求其对偶问题的最优解；2）求k的值。、1、答：其对偶问题为：由z*=w* 可得 由互补松弛性可得 解得 代入可得：2、设有LP问题： 其辅助问题的最优表的下半部分为： X1X2X3S1R2右端11/52/51/58/517/51/52/59/5其中，S1是第一个约束方程中的松弛变量，R2是第二个约束方程中的
11、人工变量。现问：当原问题约束条件的右端由（5 2）T变为（3 10）T时，新的最优解是什么？2、答：首先写出两阶段法的辅助问题，计算出各个检验数，然后通过灵敏度分析判断出原问题无最优解。3、在下面的运输问题中，假定B1、B2、B3的需求未被满足时，其单位惩罚成本分别是5、3和2，求最优解。B1B2B3供给量A151710A264680A332515需求量7520503、答：用最小元素法或VOGEL法求初始解，通过位势法进行检验并获得最优解。该问题的最小运费为595元。4、求解下述最小支撑树问题： v1 4 v2 1 v3 2 31 1 1v8 4 v0 4 v45 5 2 45 v7 3 v6
12、 2 v54、答：该问题的最小支撑树如下图所示。W（T）=13v1 v2 1 v3 2 1 1 1v8 v0 v4 2 v7 3 v6 2 v55、设有线性规划问题及其最优单纯形表如下：规划模型： （1） St：3x+ 5x+ x =15 （2） 2x+ x+ x =5 （3） 2x+ 2x+ x=11 （4）x、x、x、x、x0 最终单纯形表：x x x x x右端比值Z -3/7 -13/7 -110/7xxx 1 2/7 -3/7 1 -1/7 5/7 -2/7 -4/7 115/710/727/7如约束条件（2）中的b的系数由15变成为7，求变化后的最优基可行解。5、答1：St：3x+
13、 5x+1x =15 +1t=7 （2） 2x+ x+ x =5 （3） 2x+ 2x+ x=11 （4）由最终单纯形表：x x x x x右端（变化前）t=-8右端（变化后）Z -3/7 -13/7 -110/7-3/7t=-86/7xxx 1 2/7 -3/7 1 -1/7 5/7 -2/7 -4/7 115/7+10/7+27/7+2/7t=-1/7t=-2/7t=-1/718/743/7用对偶单纯形法继续计算可得新问题的最优解和最优值为：x x x x x右端（变化前）t=-8右端（变化后）Z -13/3 -5/3 0 -35/3xxx -7/3 -2/3 1 1 -1/7 0 -2/
14、7 -4/7 11/37/319/35、答2：用对偶单纯形法继续计算可得新问题的最优解和最优值为：。过程如下：由题目的模型可知：迭代次数基变量cB x1 x2 x3 x4 x5 b 比值 bi/aij5 4 0 0 0 0 X3 X4 X5 0 0 0 3 5 1 0 0 2 1 0 1 0 2 2 0 0 1 15 5 11 5 5/2 11/2 ZjCj- Zj0 0 0 0 05 4 0 0 0 0迭代次数基变量cB x1 x2 x3 x4 x5 b 比值 bi/aij5 4 0 0 0 1 X3 X1 X5 0 5 0 0 7/2 1 -3/2 0 1 1/2 0 1/2 0 0 1
15、0 -1 1 15/25/2 615/75/16/1 ZjCj- Zj0 0 0 0 00 3/2 0 -5/2 0 0故本题的最优解值为此表符合对偶单纯形法求解的条件，故利用对偶单纯形法计算如下：迭代次数基变量cB x1 x2 x3 x4 x5 b 比值 bi/aij 5 4 0 0 0 3 X4 X1 X5 0 5 0 0 -7/3 -2/3 1 0 0 5/3 1/3 0 0 0 -4/3 -10/21 0 1 1/3 7/319/3 Zj Cj- Zj0 25/3 5/3 0 00 -13/3 -5/3 0 035/3得其最优解为：X1=7/3，x2=0，x3=0，x4=1/3，x5=
16、19/3；Z=35/36、求解如下运输问题的最优解： B1B2B3A151020A232410A375215A49601551015要求收点B1的需求必须由发点A1满足。6、答：利用最小元素法或VOGEL法求出初始解；用位势法检验并求出最优解。该问题的最小运费为：Z=35。7、下列表格为目标规划求解过程的单纯性表格，试指出下列表格（）、（）、（）优化到哪一级目标，接下去要优化优化哪一级目标？表3Bx1x2S2右端111（）P111P2451P31231190S24218011154511140（）P11P25441P313112260S214420x1111155441180x1x2S2右端（
17、）P26P31130x21210x11151307、答：表正准备对P1级目标进行优化，表P1级目标已得到最优化，正准备优化P2级目标，表P2级目标已得到最优化且正准备要优化的P3级目标也已经实现最优化了。8、用最小元素法求下表所表达的运输问题的初始基可行解，如何求得最优解?收点发点B1B2B3B4发量A165344A244756A37658 3收量 2 4 3 4 13138、答：(1)初始可行解为：，其费用为：元 收点发点B1B2B3B4发量A1653 34 14A24 24 475 06A37658 3 3收量 2 4 3 4 1313(2)下一步进行优化判别：可用闭回路法或位势法求出各个
18、非基变量的检验数，如存在小于零的检验数，则需进一步进行优化。9、求下图中v1到v8点得最短路 V1 V2 V3 V4 V5V6V7V821 28 8988 2777 24269、答：最短路长为25； 路径为：v1-v5-v2-v4-v8V1V8V2V5V6V1V3V4V78821142211122244529810、电力公司准备在甲（V1）、乙（V8）两地沿路架设一条电缆线，问如何架设使其电缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。10、答：最短路径：v1-v3-v4-v6-v7- v8；路长：=2+2+1+2+1=811、已知某线性规划化问题的数学模型
19、如下：试写出该问题大M方法的数学求解模型（也叫大M法辅助模型），并指出在辅助模型中哪些变量可作为基变量？辅助问题的最优解在什么情况下可以得到原问题的最优解？11B、已知某线性规划化问题的数学模型如下： 试写出该问题大M方法的数学求解模型（也叫大M法辅助模型），并指出在辅助模型中哪些变量可作为基变量？辅助问题的最优解在什么情况下可以得到原问题的最优解？11B、答：（1）目标函数： max z=2x13x2Ma1Ma2. 约束条件：x1+x2s1+a1=350， x1s2+a2=125， 2x1+x2+s3=600， x1，x2，s1，s2，s3，a1，a20.（2）答：s3，a1，a2，这三个变
20、量可以做基变量；（3）当辅助问题的最优解中的两个人工变量a1，a2，等于零的时候，可以作为原问题的最优解。12、用最小元素法求下列运输作业表所表达的运输问题的初始基可行解： 销地 产地B1B2B3B4产量A13113107A219284A3741059销量3656 20 20并判断是否为最优解？如不是如何进行优化？12、（1）答：x13 =4, x14=3, x21=3, x23=1, x32=6, x34=3,其余xij=0为非基变量；（2）答：用闭回路法或位势方程组法判断是否为最优解，若是结束，若不是，则进行优化变换：找出检验数为负数非基变量作为入基变量进行出入基变换，得出更优的解，然后再重复上述步骤，直至最优。14、已知指派问题的效率矩阵如下，试用匈牙利法求出其最优指派方案。（10分）7 9 10 1213 12 16 1715 16 14 1511 12 15 1614、答：1）13、燃气公司准备在甲、乙两地沿路铺设一条管路，问如何铺设使其管路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里） V1 （甲地）1517624
