搜索
第一章测试题1:某工厂用三种原料Q1,Q2,Q3生产三种产品P1,P2,P3。已知单位产品所需原料数量如下表所示，试制订出利润最大的生产计划。答案该问题的数学模型为2:用图解法求解下列LP问题,并指出各问题是否具有唯一最优解，无穷多最优解,无界解或无可行解。答案(1)有唯一最优解Z=3，x1=1/2，x2=0(见图(a))(2)无可行解(见图(b))(3)有无穷多最优解(4)无可行解3:将下列LP问题变换成标准型，并列出单纯形表:答案(1)令，再引入变量x6，x7，原问题化为标准型初始单纯形表为(2)令，再引入变量x7，x8，x9，则原问题的标准形式为初始单纯形表为4:某线性规划问题的约束条件是问变量x2,x4而所对应的列向量A1，A2是否构成可行基?如果是，写出B，N，并求出B所对应的基本可行解。答案可以构成，B对应的基本可行解为5:对于下面的线性规划问题，以B=(A2，A3,A6)为基写出对应的典式。答案6:用单纯形法求解下列LP问题。答案(1)首先将问题化为标准形式此时取基变量x3,x4,x5,然后进行如下迭代由上表可得时最优值为16，时最优值仍为16。由于可行解都是凸集，凸集中的两相异的最优解，的连线上的点都是最优解，即都为最优解,其最优值为16。(2)首先将问题化为标准型初始表取基变量为x3，x4，单纯形表如下从初始的单纯形表可以看出，检验数为正数的第二列中不含有正数,故此问题无最优解。7:用两阶段法求解下列LP问题:答案(1)因为系数矩阵中已包含一个单位向量,所以第一阶段的只要增加两个人工变量x5，x6，所得辅助问题为进行如下表的迭送按单纯形法迭代关于目标函数G的检验数都不是正数，因此辅助问题LP的最优解为X=(0,8/5,18/5,0,41/5,0)T,其最优值G=41/50，所以原问题无解。8:写出下列LP问题的对偶问题。答案对偶问题为9:用对偶单纯形法求解下面LP问题答案引进剩余变量x4，x5≥0，将不等式约束化为等式约束对其应用单纯形迭代如下此时b0,故原问题的最优解为X=(2/13，7/13,0,0)T,其最优值为9/13。10:把线性规划问题记为p。(1)用单纯形法解p；(2)写出P的对偶D；(3)写出P的对偶松紧条件，并利用它们解对偶D。通过计算P和D的S优值，检查你的答案。答案(1)(2)(3)略11:考虑上一题的线性规划P，在下述的每一种情况下，试用解问题P所得到的最优单纯形表继续求解。答案(1)(2)略第二章测试题1:有一推销员，从城市v0出发，要遍访城市v1，v2，…，vn各一次，最后返回v0。已知从vi到vj的旅行费为cij，问他应按怎样的次序访问这些城市，使得总旅行费用最少？试建立这个问题的数学模型。答案对每一对城市vi,vj,指定一个变量XU。令XU=1，若推销员决定从vi直接进人vj；否则XU=0。则该问题的数学模型为2:用割平面法求解下列整数规划问题答案引入松弛变量x3，x4，令Z`=-Z，将原问题标准化得用单纯形法求得的最后一张单纯形表为得最优解为由于该解不是整数解，所以生成割平面。第一行生成的个平面条件为:可进一步求得该割平面方程为引入松弛变量s1将其化为标准形式为加到最优单纯形表中,再用对偶单纯形求解得到下表得到新的最优解由于得到这个新的解仍不是整数解，所以取第二行为割平面的约束条件可进一步求得该割平面方程为引入松弛变量s2将其化为标准形式为加到最优表中，再用对偶单纯形法求解得得新的最优解为X2=(4,1)T，Z2=14。此时得到的解为最优解故停止。综上原问题的最优解为X=(4,1)T,Z=143:用分枝界定法求解下列问题：答案解除整数约束,用图解法或单纯形法得此问题的最优解为X0=(3。6,2。8)T,Z0=32。8因为3x14,上述问题可分解为两个子问题由图解法或单纯形法可得这两个问题的最优解为因为Z1Z2故原问题的最优解为4:用简单隐枚举法求解下列0-1规划问题：答案(1)x=(1,0,1)T,Z=8；(2)x=(0,0,1,1,1)T,Z=6。第三章测试题1:两个水厂A1,A2将自来水供应三个小区B1,B2,B3,每天各厂的供应量与各小区的需求量以及各水厂调运到各小区的供水单价如下表。试用表上作法给出下表的最优供水方案。答案先用最小元素法确定初始方案。这种方法的基本思想是”就近供应”,即从运输问题数据表中找出最小运价cij,选择这个最小运价在运输方案表中对应位置xij作为数字格(基变量），在格内填写允许取得的最大数。每次总选择剩余运价中的最小cij所对应的xij作为数字格，并填写允许的最大数,直至得到初始方案,如下表下面用位势法判别其是否为最优解，即λij=zij-cij，可得λ12=2,λ23=-5因为λ12=20，则取x12为进基变量。调整量θ=min{90，50}=50,所以x11为出基变量。闭回路上奇数顶点增加50,偶数定点减少50。调整后的方案如下表对调整后的方案表进行最优解的判别如下λ11=-20,λ23=-30则所有的检验数都小于0,所以此方案为最优方案。最优方案的总运费为Z=50X6+120X4+160X7+40X5=21002:已知运输问题的产销平衡表和单位运价如下,试用表上作业法求其最优解。答案最优方案与检验数表如下括号内为检验数.最小运输费用为:Zmin=335.3:下表给出了三个产地和四个销地的某种物资的供需量及产销的运价,试求出运费最少的运输方案。答案最优方案如下表Zmin=5X3+10X2+5X1+5X2+10X3=80第四章测试题1:写出下图的关联矩阵和邻矩阵。答案关联矩阵邻接矩阵2:分别用避圈法和破圈法求解下图的支撑树。答案略3:分别用破圈法和避圈法求下面各图的最小支撑树。答案4:已知网络如下图所示，求从s到t的最短路径及最短距离。答案则最短路径为(s,3,4,t),最短距离为1+4+2=75:求解下图中v1至各点的最短距离与最短路径。答案V1至各点最短距离为：v2(4),v3(7),v4(11),v5(7),v6(9),v7(11),v8(18),v9(13),v10(9),v11(14).6:求下面网络的最大流集。答案最大流量为20。第五章测试题1:求解具有下述系数矩阵的最小指派问题：答案最优指派方案为最优值分别为：48，21.2:求解具有下述系数矩阵的最大化指派问题:答案最优指派方案为最优值为：363:四个人完成四项工作，由于个人的技术专长不同，他们完成四项工作任务所获得收益如下表，且规定每人只能做一项工作，试求使总受益最大的分配方案。答案最优指派方案为所得最大收益为：maxZ=10+9+11+13=434:分配甲，乙,丙，丁四人去完成A，B，C，D，E五项任务。每个人完成各项任务的时间如下表所示。由于任务数多余人数，故考虑：(1)任务E必须完成,其它四项可任选三项完成；(2)其中有一人完成两项，其它每人完成一项。试分别确定最优分配方案,使完成的总时间最少。答案(1)由于任务数多余人数,所以霜要有一名假想的人物，因为工作E必须完成，故设完成E的时间为M(M为非常大的数）,其余的假想时间为0，则用匈牙利算法如下所以最优解为：x12=x24=x35=1，其余的xij=0，最少时间为105h.(2)由于所有的任务，都必须由甲乙丙丁完成，所以假想的人的效率应该对每项工作而言，都是完成它的最好的人，而不能假设为0值,所以构造的效率表如下：用匈牙利方法求解,可得最佳分配方案：甲—B，乙—C和D,丙—E，丁—A，共需要131h.第六章测试题1:某企业有三种方案可供选择：方案S1是对原厂进行扩建；方案S2是对原厂进行技术改造；方案S3是建新厂,而未来市场可能出现滞销(E1）,一般(E2）和畅销(E3）三种状态，其受益如下表(单位:万元)。试分别安以下决策准则确定最优方案:(1)悲观准则；(2)乐观准则；(3)折衷准则（乐观系数a=0.6)；(4)后悔值准则；(5)等可能性准则。答案(1)根据悲观准则有故最优决策方案为S2.(2)根据乐观准则有故最优决策方案为S3.(3)根据折衷准则有故最优决策方案为S3.(4)根据后悔准则有后悔准则值表如下故最优决策方案为Sl.(5)等可能准则有故最优决策方案为Sl.2:某企业生产一种季节性商品。当需求量为D时，企业生产x件商品时获得的利润为：设D有五种可能的值:1000件，2000件,3000件，4000件和5000件，并且他们出现的概率均为0。2。若企业追求最大的期望利润，那么最优生产为多少件？答案该问题收益矩阵如下表则由上表可知最优选择为生产4000件。3:某工程队承担一座桥梁的施工任务，由于夏季多雨，需停工三个月。在停工期间该工程队可将施工机械搬走或留在原处。若搬走,需运费1800元。如留在原处，一种方案是花500元筑护堤,防止河水上涨发生髙水位的侵袭,若不筑护堤，髙水位侵袭将损失10000元。发生洪水时，不管是否筑护堤,都将受到60000元的损失。根据历史资料，该地区夏季髙水位的概率是0.25,洪水的概率是0.02。试用决策树找出最优方案。答案故以不搬走并筑护堤最合算。阶段性作业一1:已知线形规划问题要求:（1)化为标准形式；(2)若用两阶段法求解，写出其辅助问题并列出第一阶段的初始单纯行表。答案(1)令,再引入松弛变量x4,x5.则原模型可化为：初始单纯形表为2:用图解法或单纯形法求解下列线形规划问题：答案(1)图解法则由图可知：当x1=4,x2=2时，此问题有最优解Z=-14(2)单纯形法增加松弛变量x3,x4,x5,x6化为标准型由上表可知所有的x1=4,x2=2,x3=x4=x5=0,x6=4，则最优解为Z=14.3:求解0-1规划的简单隐枚举法答案则最优解为：X=(0,0,1)T,Z0=5.4:已知某一运输问题的单位运价和产销表如下表所示，请给出两个最优方案。答案下面给出三个最优方案5:用Dijkstra算法求下图由s到t最的最短路。答案则最短有向路为：s-3-4-t,最短距离为21.6:求下列最小指派问题。答案7:某农场要在一块地里种一种农作物，有三种可供选择的方案，即种蔬菜、小麦或棉花。根据过去的经验和大量调查研究发现天气干旱、天气正常和天气多雨的概率分别为0。2,0。7,0。1。每种农作物在三种天气下获利情况如下表所示。为获得最大利润应如何决策?(用决策树法)答案由决策树可知应种棉花。阶段性作业二1:已知线形规划问题：(1)求解并写出其最优单纯形表；(2)若c2由0变为1，试求新问题的解。答案增加人工变量x6，x7得到辅助LP问题则形成下表则辅助问题的一个最优解为(0,1/4，3/8,0,0,0,0)T,原向题的第一基本可行解为X0=(0,1/4,3/8,0,0)T.继续迭代，得原问题得最优解为x=(1/2，0，1/4，0，0)T,最优值为31/4.最优单纯形表为由于x2是非基变量，故只须计算，因为,因此原问题的最优解仍是新问题的最优解.2:已知下列线形规划问题的最优解为，试写出其对偶问题并用互补松弛条件求其对偶问题的最优解。答案对偶问题为互补松弛条件为则对偶问题的最优解为:3:分支界定法求解下面整数规划问题。答案先不考虑整数约束,变成一般得的LP问题，用图解法求其最优解为：如下图因所求的解不是整数解则转化为如下问题并求解过程如下最优解为4:已知某一运输问题的单位运价和产销表如下表所示,试用最小元素法求其初始的调运方案。答案这是一个“销产”的问题,故销地要增加一列，则原问题转化为:5:用避圈法或破圈法求下图最小树。答案(1)避圈法w(T)=1+2+2+3=8.(2)破圈法w(T)=1+2+2+3=8.6:有四项工作要甲乙丙丁四个人去完成，每项工作只许一个人去做，每个人只完成一项工作。已知每个人完成各项工作时间如下表所示，问应如何指派使总的消耗时间最少？答案用匈牙利求法解此题则最优指派方案为(1)甲-1，乙-4，丙-3，丁-2；或(2)甲-2，乙-1，丙-3，丁-4.总时间消耗为70。7:某一决策问题的损益矩阵如下表，其中矩阵元素为年利润。试用最大可能法和期