管理运筹学基础作业.docx

《管理运筹学基础作业.docx》由会员分享，可在线阅读，更多相关《管理运筹学基础作业.docx（15页珍藏版）》请在课桌文档上搜索。

1、本次作业是本门课程本学期的第1次作业，注释如下：一、判断题(判断正误，共14道小题)1 .判断正误线性规划问题的一般模型中不能出现等式约束。你选择的答案：说法错误正确正确答案：说法错误解答参考：2 .在线性规划模型的标准型中必(j=l,2.m)一定是非负的。你选择的答案：说法正确正确正确答案：说法正确解答参考：3 .判误线性规划问题的基本解一定是基本可行解你选择的答案：说法错误正确正确答案：说法错误解答参考：4 .线性规划问题的最优解只能在可行域的顶点上达到。你选择的答案：说法错误正确正确答案：说法错误解答参考：5 .判断正误同一问题的线性规划模型是唯一的。你选择的答案：说法错误正确正确答案：

2、说法错误解答参考：6 .判断正误任1可线性规划问题存在并具有唯一的对偶问题。你选择的答案：说法正确正确正确答案：说法正确解答参考：7 .对偶问题的对偶不一定是原问题。正确答案：说法错误解答参考：8 .判断正误运输问题的求解结果可能出现下列4种情况之一:有唯一解；有无穷多最优解；无界解；可行解。你选择的答案：说法错误正确正确答案：说法错误解答参考：9 .在运输问题中，只要给出一组含有（m+n-1）个非零的Xij且满足全部约束，就可以作为基本可行解。你选择的答案：说法错误正确正确答案：说法错误解答参考：10 .判断正误整数规划解的目标函数值一般优于其相应的线性规划问题的目标函数值。你选择的答案：说

3、法错误正确正确答案：说法错误解答参考：11 .用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。你选择的答案：说法错误正确正确答案：说法错误解答参考：12 .第一个顶点和最后一个顶点相同的闭链叫回路。你选择的答案：说法错误正确正确答案：说法错误解答参考：13 .判断正误任一运输网络中至少存在一个流。你选择的答案：说法正确正确正确答案：说法正确解答参考：14 .判断正误DjiSktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。你选择的答案：说法正确正确解答参考：(注意:若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观Sg答案。

4、)二、主观题(共3道小题)15 .简述编制统筹图的基本原则.参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个终点，没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。16 .已知线性规划maxZ=3+2+33(1)、求出不考虑X3为整数约束时的最优解。(2)、写出分支条件及约束方程。(3)、求最优解。参考答案：(1) =16/3,X2=3,X3=10/3;(2)10/3=3,X34或X33;-4/9-1/9x5-4/9x6+x7=-1/3;-4/91-1/95-4/96+7=2/3;17.简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出刃

5、的方法得出的解较优。参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的最西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法：在运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所在某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，直至得到初始可行解。一般来讲,用差值法求出的初始可行解最接近最优解,也就是最优的。本次作业是本门课程本学期的第2次作业，注释如下：一、判断题(判断正误，共16道小题

6、)线性规划一般模型中的变量不一定是非负的。你选择的答案：说法正确正确正确答案：说法正确解答参考：2 .用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能找出最优解。你选择的答案：说法正确正确正确答案：说法正确解答参考：3 .图解法与单纯形法求解的形式不同，但从几何上理解,两者是一致的。你选择的答案：说法正确正确正确答案：说法正确解答参考：4 .单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数的值增加更快。你选择的答案：说法错误正确正确答案：说法错误解答参考：5 .若原问题可行，而对偶问题不可行，则原问题无界。你选择的答案：说法正确正确正确答案：说法正确解

7、答参考：6 .若原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。你选择的答案：说法正确正确正确答案：说法正确解答参考：7 .按最小元素法给出的初始基本可行解，从每一个空格出发仅能找出唯一的闭回路。你选择的答案：说法正确正确正确答案：说法正确解答参考：8 .表上作业法中，任可一种确定初始基本可行解的方法都必须保证有（m+n-1）个变量。正确答案：说法正确解答参考：9 .用分枝定界法求解一个极大化整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界你选择的答案：说法正确正确正确答案：说法正确解答参考：10 .用割平面法解整数规划问题时，要求包括松弛变量在内的全部变量必须取整数

8、。你选择的答案：说法正确正确正确答案：说法正确解答参考：11 .有向图G中任意两点是可达的，称此图为强连通图你选择的答案：说法正确【正确正确答案：说法正确解答参考：12 .数T的任两顶点间恰有一条初等链。你选择的答案：说法正确正确正确答案：说法正确解答参考：13 .G的任一流f的流值valf可能超过任一割的容量。你选择的答案：说法错误正确正确答案：说法错误解答参考：14 .f为G上一个流，若e为f不饱和边，那么e也一定为f正边。你选择的答案：说法错误正确正确答案：说法错误解答参考：15 .判断正误统筹网络中任一节点都表示前一道工序的结束和后一道工序的开始你选择的答案：说法错误正确正确答案：说法

9、错误解答参考：1.1. 在统筹网络图中只能有一个始点和一个终点.你选择的答案：说法正确正确解答参考：(注意:若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观即答案。)二、主观题(共8道小题)17 .Djisktra算法能否求有负权的有向图中两点间的最短路径,举例说明。参考答案：DjiSktra算法不能求有负权的有向图中两点间的最短路径。如下图：左边的点为Vl,右边的点为v3,下面的点为v2,若Vl到v2的权重为1,vl到v3的权重为2,v3到V2的权重为-3,则，若用Djisktra算法则最短路径的数值不能收敛，致使求不出最优解。18 .指出统筹图网络中的

10、错误，并改正。转答案：(De,d工序有错。(2)两个终点。(3)两个始点，两个终点。(4)工序循环不是统筹图。19 .简述在求最大流过程中，寻找由到源到汇的不期口链的方法。参考答案：标号法寻找增流链的步骤：第一步：对未检查的边(U,V)的顶点V进行标号，标号的方式为(U,边的方向,/e),其中标号的各个部分按照如下确定:(1)U：表示被标号点V的前一个顶点。(2)边的方向：当被标号点V为终点时，即边(u,v)为前向边时，用“十”标示；当被标号点V为始点时，即边(u,为后向边时，用“-”标示。(3)/(。：当被标号点V为终点时，/(v)=mn(u),c(ufv)-f(ufv)；当被标号点U为始点

11、时，/(v)=mM/(U)J(U,v)。另外，默认源X的标号为S,+,+8)。第二步：继续检查，判断顶点后面的边(z)能否成为增流链的边，边(Z)若成为增流链中的边所具备的条件如下：(1)如果边(V,Z)是前向边，则应该有f(v,z)O由前面知识可知，后向边流量只能减少，那么边(z)就不能是零边。第三步：若边(Z)能够成为增流链的边，就使顶点Z成为被标号的点，再对被标号点Z按照第一步的标号方式进行标号。第四步：返回第二步，不断循环，直至不能找到被标号点，则反向追踪找出不饱和链。20 .用标号法求图所示的网络中从VS到Vt的最大流。参考答案：(2)Valf=7(1)Valf=521 .简述分枝定

12、界法的主要步骤参考答案：第一步：先不考虑整数约束条件，对一般情况的线性规划问题用单纯形法或对偶单纯形法求解。如果求出的最优解满足整数规划问题的所有整数约束条件，那么这个最优解也就是整数规划问题的最优解，如果有一个或多个整数约束条件没有被满足，转到第二步。第二步：任意选择一个应该是整数而不是整数解的变量Xk,设它的非整数解是bk,同时设以对应的整数位是bk,现在将原问题分成两枝，一枝是在原问题的基础上，增加约束条件XkWg小另一枝是在原问题的基础上，增加约束条件Xk2gk+1,这样就构成了两个新的线性规划问题的子问题。第三步：按照第3.3节对偶单纯形法扩展应用的思路，分别对分枝后的两个新线性规划

13、子问题继续求解。若新的解不满足原问题整数约束，再按第二步进行新的分枝，直到满足下面的情况停止分枝：22 .已知某整数规划不考虑整数约束时最优单纯型表，写出一个割平面方程。参考答案：-1/73-2/7x5+6=-6/7;23 .求解下列0-1规划问题的解。(1) minZ=8x1+2x2+4x3+7x4+5x5参考答案：(1)(1/2/3/4,5)=(0,1,1,0,0),Z=6(2)(x1fX2zX3,X4zx5)=(1,1,0,0,0),Z=5(3)(x1lX2zX3,X4,x5)=(0,0zlzlzl),Z=624.简述运输方案的调整过程。参考答案：第一步：确定换入变量同单纯形法一样，在所

14、有的负检验数中，一般选取检验数最小的非基变量作为换入变量。第二步：确定换出变量和调整量由定理5.4可知，由此时还是非基变量的换入变量和一组基变量可以组成一个唯一的闭回路，找到这个闭回路以后，以此非基变量为起点，取此闭回路中偶数顶点取值最小的基变量做为换出变量，调整量的量值即为此基变量的值。第三步：调整方法（1）闭回路以外的变量取值均保持不变。（2）针对闭回路，奇数顶点变量的值全部加上调整量，偶数顶点变量的值全部减去调整量。第四步：标识方法为了保证基变量的个数为m+rrl个，在标识上作如下处理：（1）调整后，原来作为非基变量的换入变量就变成了基变量，所以要把这个变量的值标识成“O”。（2）调整后

15、，原来作为基变量的换出变量就变成了非基变量，所以要在这个变量的位置打上“X”。第五步：继续求检验数，如果存在负的检验数，就返回第一步，否则计算停止，说明找到了最优解。本次作业是本门课程本学期的第3次作业，注释如下：一、判断题（判断正误，共11道小题）1 .一般情况下，松弛变量和多余变量的目标函数系数为零。你选择的答案：说法正确正确正确答案：说法正确解答参考：2 .用单纯形法求解标准型线性规划问题时，与检验数大于。相对应的变量都可被选作换入变量。你选择的答案：说法正确正确正确答案：说法正确解答参考：3 .由应用问题建立的线性规划模型中，其约束方程有多种形式你选择的答案：说法正确正确正确答案：说法

16、正确解答参考：4 .%为对偶问题的最优解，若yi0,说明在最优生产计划中第i种资源已完全耗尽.你选择的答案：说法正确正确正确答案：说法正确解答参考：5 .当所有产量和销量均为整数值时，运输问题的最优解也为整数解。你选择的答案：说法错误正确正确答案：说法错误解答参考：6 .整数规划问题的可行解与其线性规划问题的可行域内的整数点相对应。你选择的答案：说法正确正确解答参考：7 .判断正误任一图G中，当点集确定之后，树图是G中边数最少的连通图.你选择的答案：说法正确正确正确答案：说法正确解答参考：8 .在有向图中，如图所示中的边e和e是平行边你选择的答案：说法错误正确正确答案：说法错误解答参考：9 .

17、若Q为f饱和链，则链中至少有一前向边条边为f饱和边，同时至少有一条边后向为f零边。你选择的答案：说法错误正确正确答案：说法错误解答参考：10 .既要满足流值最大又要满足费用最小的流是不存在的.你选择的答案：说法错误正确正确答案：说法错误解答参考：11 .标号法每迭代一步，没有取得永久性标号顶点的标号都会被改变一次.你选择的答案：说法正确正确正确答案：说法正确解答参考：（注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观题答案。）二、主观题（共9道小题）12 .求下列图中的指定顶点（1）到（5）的最短距离和路（径）。转答案：(1)路线：(1)(4)一(3

18、)(5)(2)路径：(1)-(3)-(2)-(4)-(5)13 .简述在求最小费用流的过程中，寻找由到源到汇的不饱和链的方法参考答案：第一步：如果运输网络G的流值没有达到4先用最大流算法把流值调到4如果运输网络G的流值达到4则不对网络流调整。第二步：针对流值为4的运输网络G,构建伴随网络流f的增流网络G/0第三步：针对增流网络，查看是否存在基于”的负回路，如果不存在负回路，说明当前的网络流已经是最小费用流，算法终止，否则转到下一步。第四步：针对存在的负回路C,令6=mMd(e),e为中负回路的边。第五步：针对负回路C对应运输网络G中的圈，判断该圈是否为增流圈，如果不是增流圈，转到第三步继续寻找

19、负回路，否则转到下一步。第六步：针对运输网络G中的增流圈，按照定理9.5,把增流圈中方向与负回路方向一致的所有不饱和边的流量加上6;把增流圈中方向与负回路方向相反的所有正边的流量减去6。第七步：继续寻找负回路，如果有负回路，继续调整，否则返回第二步。14 .根据对偶规则填表：参考答案：15 .简述如何在单纯型表上判别问题是否具有唯一解、无穷多解、无界解或无可行解参考答案：将检验数C厂Z/作为判断基本可行解是否为最优解的标准，判断的方法如下：(I)若所有非基变量的检验数C厂存0,已经达到最优解；(2)若存在C厂少0,但所有crzj0所在列对应的所有,70,无界解;(3)从几何意义的角度就是说，约

20、束条件方程组没有可行域，则线性规划问题五可行解；(4)在最优单纯形表中，如果出现检验数等于0的个数多于基变量的个数，线性规划模型就有多重解。16 .简述若标准型变为求目标函数最小，则用单纯形法计算时，如何判别问题已取得最优解。参考答案：对目标函数为极小化线性规划问题时,则用单纯形法计算时,当所有非基变量的检验数大于或等于零时，已经达到最优解；17 .建立下列问题的线性规划模型并化为标准型某工厂生产A1、A2两种产品，有关的信息由下表给出，建立制定最优生产计划的模型（利润最大）.参考答案：提示：设产品Ai、A2的产量分别为均、X2个单位，maxZ=70x1+120x218 .某工厂生产A、B两种

21、产品，已知生产A每公斤要用煤9吨、电4度、劳动力3个；生产B每公斤要用煤4吨、电5度、劳动力10个。又知每公斤A、B的利润分别为7万元和12万元。现在该工厂只有煤360吨、电200度、劳动力300个。问在这种情况下，各生产A、B多少公斤，才能获最大利润，请建立三1.参考答案：提示：设A、B各生产Xi、X2公斤，maxZ=7+12x219 .目标函数中人工变量前面的系数M（M是充分大的正数）的作用是参考答案：使人工变量不可能进入最优解20 .解包含人工变量线性规划问题的单纯形法有有参考答案：大M法、两阶段i去本次作业是本门课程本学期的第4次作业，注释如下：（注意：若有主观题目，请按照题目，离线完

22、成，完成后纸质上交学习中心，记录成绩。在线只需提交客现题答案。）一、主观题（共4道小题）1 .找出下列线性规划问题的一组可行解和基本可行解。参考答案：提示：可行解是满足约束条件的解，基本可行解是与基列（线性无关）对应的可行解。2 .目标函数为maxZ=28x4+x5+26,约束形式为,且x，x2,X3为松弛变量，表中的解代入目标函数中得Z=14,求出ag的值，并判断是否最优解。参考答案：a=7fb=-6,c=0,d=l,e=0,f=1/3,g=0;最优解3 .用单纯形法求解下列线性规划。参考答案：(1)X=(12/7,15/7),Z=-120/7;(2)X=(5/6,0,17/5,0,0)Z=81/5;(3)X=(2,6),Z=36;(3)X=(-3,O),Z=-94.某工厂生产A、B两种产品，每公斤的产值分别为600元和400元。又知每生产1公斤A需要电2度、煤4吨；生产1公斤B需要电3度、煤2吨，该厂的电力供应不超过100度,煤最多只有120吨，问如何生产以取得最大产值？建立模型，用图解法求解。参考答案：提示：设A、B各生产Xi、X2公斤，maxZ=600+400x2,(xbx2)=(20,20),产值最大为20000元。