【迂回运输】运输问题的求解方法_牛宝宝文章网【迂回运输】运输问题的求解方法专题：第3章 运输问题的求解方法物资最佳调运问题是属于线性规划的一种特殊类型——运输问题。它的解法很多，在这一章里将介绍两种求解方法----------- 表上作业法和图上作业法。3.1 平衡运输问题及数模3.1.1 问题的提出社会生产活动川流不息、工农之间、地区之间、各生产企业之间、各企业车间之间，必然产生不间断的，错综复杂的经济联系。这种联系是由交通运输业的货物运输来实现的。无论地区范围内的运输或者工地范围内的运输，在组织运输时，必须选择合理的物资调运方案。选择合理的物资调运方案是运输工作组织中十分重要的问题，特别是当物资的需要特点（收点）及供应地点（发点）较多，而需要的供应数量又各不相同时，如何根据具体条件，各个收发点的分布，交通运输线路的位置及其他条件等，科学地确定最为合理，经济的调运方案，对于充分发挥运输工具的潜力，降低运输成本，保证建设任务的完成有着极为重要的作用。3.1.2 平衡运输问题的数模设Ai(i=1,2,…,m)为出发点，Bj(j=1,2,…,n)为收点，ai和bj分别表示Ai和Bj的xij分别表示Ai到Bj的单位运费和运量。 发量和收量，Cij和则有线性规划模型。min f(x)=∑∑cijxiji=1j=1mn?ns?t?∑xij=aij=1??m?x=bijj?∑i=1???xij≥0m(i=1,2,",m)(j=1,2,",n)(i=1,2,",m;j=1,2,",n)在这里假定∑ai=∑bj，且 ai,bj≥0，cij≥0。满足以上条件的运输问题被称为平衡运输模型，为了叙述方便起见，采用（T，P）表示。3.1.3 （T，P）的特性1．（T，P）的系数矩阵A的秩为m+n+1。 i=1j=1n因为，A的前m行相加的结果等于后n行相加的结果，所以，它的m+n行的行向量是线性相关的，秩不可能超过m+n+1。另一方面，我们还可以在A中找到一个m+n-1阶的非奇异方阵，从而可知A的秩只能为m+n+1。并由此可推知，（T，P）的每个基本可行解的基变量的个数为m+n+1个。2.任一个（T，P）问题至少有一个最优解存在。（1） （T，P）至少有如下的一个可行解：xaibjij=Q(i=1,2,",m;j=1,2,",n)mn其中，Q=∑ai=∑bj。i=1j=1（2）它的目标函数显然有下界零(非负)。故由（1），（2）知（T，P）必有最优解存在。3.2 图上作业法图上作业法是解决（T，P）问题的一个方法，它是在一张运输交通上通过一定步骤的规划和计算来完成物资调运计划的编制工作，以便使物资运行的总吨-----------公里数最小可使物资运费降低，并缩短了运输时间，所以，在一定条件下称这样的方案为最优方案。制定一个物资调运方案时，首先要编制物资平衡表（如表3-1）。在编制物资平衡表时需要做3件事。1.出需要调出物资的地点（即发点）及发量。2.出需要调进物资的地点（即收点）及收量。3.求：总发量=总收量。第二步，根据物资平衡表和收点，发点间的相互位置绘制交通图。所谓交通图就是表明收点和发点间的相互位置以及联结这些点之间的交通线路的简要地图。在交通图上，用圆圈“〇”表示发点，将该发点的发量填入圆圈“〇”内。用方框“□”表示收点，将该收点的收量填入方框“□”内 。两点间的距离，记在交通线路的旁边。交通图绘制好后，即可在其上面进行物资调运，找出初始调运方案(初始基可行解)。即第三步，作物资调运流向图。我们用箭头“→”表示物资调运的方向即称流向，并规定：流向“→”必须画在沿着线路前进的右侧。把运送物资的数量记在流向 “→”的旁边并加括号（ ），以区别于两点之间的距离数。另一方面，为了保持图面的整洁，流向量最好不要通过收，发点以及交叉路口，如图3-1中，(a)，(b)是正确的。图3-2中，AE是正确的。由此可知，当一个交通图成圈时，若运输方向沿逆时针方向，则需将流向“→”画在圈外，称外圈流向；若运输方向是沿顺时针方向，则将流向“→”画在圈内，称为内圈流向。若在图中每个发点吨数全部运完，每个收点所需吨数均已满足，则称此图为流向图。在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨—公里数是最小的调运方案。这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。（1）对流：所谓对流就是在一段线路上有同一种物资往返运输（同一段线路上，两各方向都有流向），如图3-3。将某种物资10吨从A1运往B2，同时又有同样的物资10吨同时从A2运往B1，于是在A1A2之间就出现了对流现象.如果把流向图改成图3-4，即将A1的10吨运往B1，而将A2的10吨运往B2，就避免了A1A2的对流，从而可以节约运输量2×10×30=600(吨公里)。（2）迂回：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如图3-5所示。显然，它是一个迂回运输流向图，它的内圈长6大于整个圈长的一半5。如果把它改成图3-6，就避免了迂回现象，可节约运输量5×6-5×4=10（吨公里）理论上可以证明，一个物资调运方案中，如果没有对流和迂回运输，则该方案就是最优调运方案。即运输量最小的方案。从以上讨论可以看到，图上作业法的实质就是在一张交通图上寻找没有对流和迂回的最优流向图。为了贯彻以上原则，则须采用逐步逼近法，即我们可以先设法作一个流向图，然后图3-6来检查它是不是最优的，如果是的话，问题就解决了;如果不是，就把这个流向图稍微变化一下，这样的变化称为调整。调整后的新流向图所花费的吨公里比原流向图的要少一些。然后再检查新流向图是不是最优的，如果仍旧不是，就再进行调整，一直到找到最优流向图为止。物资运输的交通图总共分为两类：一类是不成圈的交通图，另一类是成圈交通图，以下分别举例说明他们的最优流向图的求法。例3.1 求表3-1中，水泥的最优调运方案，其交通图如图3-7。 此例道路不成圈，只要按口诀图3-7首先看A1→A2共70出时必须先经B1吨，所以最好将此70吨全部给B1。根据前述，在图上可在沿着线路前进的方向的右侧箭并将按此流向头来表示流向，调运水泥的物资平衡表 表3-1调运的数量写在箭头的旁边，并把同方向的两个流向合并成一个。再看B2→A3→B1支线，A3需调出30吨，B2需调入10吨，本着先平衡支线的原则，从A3调给B210吨余下20吨须调给其他的地方。由于自A3调出时必经过B1，而B1还需10吨，因此从A3调给A110吨，余下10吨调给另外地方。最后看B4→A4→B3→B1支线。为了避免对流，A3调出的10吨只能给B3，而B3还需20吨，则由A4供应，A4余下的50吨全部给B4。这样最后得到的流向图（如图3-8）。图3-8所示的流向图既无对流，又无迂回，所以它是最优流向图，对应的方案是最好方案。相应于该流向图的调运方案显然不是唯一的，现在给出两个调运方案，如表3-2所示。对于第一个方案运行的总吨公里是f(x)=50×(66+52)+20×52+10×71+10×85+10×(71+45)+20×120+50×150 =19560(吨公里)对于第二个方案运行的总吨公里是f(x)= 45×(66+52)+15×52+20×71+10×85+5×(66+52+45)+5×(52+45)+20×120+50×150 =19560(吨公里)3.3表上作业法3.1.1 问题的提出在前节中所介绍的图上作业法，可以很简便地求得吨公里数最小的调运方案。可是吨公里数有时还不能充分地反映运输耗费的大小程度。例如，从10个不同的产地各运10吨物资到10公里外的10个销地所耗费的运输力量与从一个产地运10吨物资到100公里以外的一个销地所耗费的运输力量相比较，虽然它们的吨-公里数都是相等的，两者都是100吨-公里。可是在不考虑道路好坏的情况下，只是装卸工作量，前者就要比后者大10倍。因此，从图上作业法所得的吨-公里数最小的调运方案，有时要想利用图上作业法解决是有一定限制的。故在这节中要介绍的表上作业法就是为了解决寻求费用最省的这个问题。3.3.2 表上作业法表上作业法就是要把解决的（T，P）问题放在表格上来进行。其大致步骤为： 首先列出被调物资的单位运价表和平衡表，然后判定初始调运方案，即求出初始基可行解。其次判别所得解是不是最优解（即运费最少的调运方案）。如果所得解不优，则进行调整，得出新的基可行解（新的调运方案），再进行判定新基可行解，直至得到最优解为止。1．初始调运方案的编制（初始基可行解的方法）初始方案编制的好坏将直接影响着求优解进度的快慢，一般来说，初始方案编制的较好，该方案的运费离最小运费的差距就较小，相对来说调整的次数也少。如果初始方案编的不好，调整的次数也就越多。目前采用的初始编制方案很多，但其中较好的方法就是最小元素法，故在这里我们以例来介绍该方法。最小元素法的基本思想是按运价最小的尽可能地优先供应优先满足，为了便于理解以实际问题来介绍其具体做法。例 3.4 已知某物资的平衡表和运价表如表3-3和表3-4所示，求该（T，P）问题的最优调运方案。平 衡 表 表3-3运 价 表 表3-4用(i,j)为了叙述方便起见，我们在表3-5中把xij排列在第i行第j列交叉的方格内，代表这一个方格，一个方格对应一个变量。将（T，P）的一个基可行解中基变量所取的值填入对应的方格里，非基变量对应的方格让空着（因为非基变量所取的值为O），由（T，P）的性质1知，m行n列的方格内恰有(m+n-1)个格子要填上数字，其余mn?(m+n-1)方格要空着，现我们采用最小元法编制例3.4的初始调运方案见表3-5(每一个方格可右上角数字为单位运价) 。初始调运方案表 表3-51.1 表3-5中的数字的填法为:在表中找到最小的运价(本例为(2，2)格)在本方格中填上尽可能的数字，(本例为min(25,20) 20=)，将该数圈入圆圈内填到格上，(本例在(2，2)格所对应的行发行量运完，则用虚线划掉该行，若对应的列收量得到满足.则划掉该例(本例划掉第2例)。1.2 在划去一行或一列后，在余下的方格中重复上述步骤，直到所有的行列被划去为止，得出表3-5 。[注]:当某方格填入数字后，如果所对应的行发量无余量且列收量同时得到满足，此时只能划去行(或列)，而在所在列(或行)然后再划去这一列(或行)例：表3-6中编制的初始调运方案表3-6在(2.4)格上填mn?(m+n-1)个。。在表3-8中，填了数字的格恰好为m+n-1个(包括格子)。空格为2.最优解的判定方法给定一个初始解之后，就需要判定这个解是不是最优的，即运费是不是最小的。现我们仍以例3.4为例进行说明。由线性规划知，最优解的判定准则是:如果所有检验数都非负，则该解对应的调运方案就是最优调运方案。反之，如果检验数中有负数，则这个解对应的方案就不优，需调整。所以，要判定方案的优劣，必须求出检验数.而利用表上作业法求检验数的方法，一般采用闭回路法或位势法。2.1 闭回路法闭回路法是首先在初始调运方案表上找出适当的闭回路，然后把闭回路上每个转角上的数字通过代数运算得出检验数，最后才利用检验数来判定方案的优﹑劣，所以，我们首先了解闭回路的作法，其次了解检验数的求法，最后给出判定及调整法。（1）闭回路的作法从某一空格出发，沿水平或垂直方向前进，当碰到另一个适当的有数字格后，转90度弯继续前进，依次进行下去，一直回到原出发空格为止，我们称按以上方法做出的路径为原出发空格的闭回路。例表3-5中的各空格的闭回路分别是：a (1，1)d (2，1)b (1，2)e(2，3)c(1，3)f (3，2)(2)检验数求法检验数的求法是：从空格开始出发，沿闭回路前进，凡奇数次转角格相应的运价前加负号，空格和偶数次转角空格相应的运价前加正号，然后求其代数和，将所得的和作为空格(i,j)的检验数，记为λij 。λ11=10-9+8-7=2，相应地λ12=5-2+6-7=2，λ13=3，例表5中（1.1）格的检验数，λ21=1，λ23=5，λ32=?1，2.2 位势法 (1)作位势表第一步：做出调运方案表中有数字格所对应的运价表第二步：在做出表的下方和右方加行和一列，并且在所加行﹑列构成的每一空格上填上一个数，在各行上填的数称为行位势，记为ui。在各列上填的数称为列位位势表 表3-7′(数字格(i,j)对应的运价)。 势，记为vj，新填数要求满足：ui+vj=Cij填满数字的位势表 表3-8例表3-5对应的位势表如表3-7所示，表的填法是：首先在表3-9的的第一行令u1=3，则在第4列（B4列）下方填′=7的满足u1+v1=C14一个列位势v1=4，要求，其次填u2=2，v2=0，……依次下去，得到表3-7，并称表3-7为位势表。检验数表 表3-9(2)求检验数第一步，在位势表的空格中填入(ui+vj)，如表3-8(填满数字的位势表)′′?(ui+vj) 第二步，计算λij=Cij′′为调运方案中空格对应的运价，其中，Cij或利用运价表，表3-4中数减去表3-8中相对应的数(ui+vj) 。得表3-9(检验数表)。A3-1表3-11中的检验数和我们利用闭回路法求出来的完全一样，这样我们就可根据情况来选择其中一种方法来求检验数。另一方面表3-9中检验数λ32=?1&0，所以初始方案不是最优方案，还需要进行调整。2.3 调运方案的调整方法 现我们仍以上例说明其调整方法。该例λ32=?1&0，第一步，据需调整的调运方案表，画出λ&0所对应空格的闭回路，画出(3，2)格的闭回路第二步，从空格（3，2）出发沿闭回路前进，在回路所有奇数次转角格中选出最小的运量（调整量）本例（3，4）格对应的运量是5。第三步，将闭回路上凡奇数转角格对应的运量减去调整量（本例为5），其余转角格对应的运量加调整量，将得到的新的调运方案，本调整后的调运方案 表3-10例如表3-10所示。在重复三，利用位势法求得调整后的调运方案的检验数如表3-13所示。从检验数表3-13看出，所有的检验数都非负，所以，我们调整后的调运方案是一个优方案它所对应的最优解为：x11=x12=x13=x21=x23=x34=0检验数表 表3-11x14=25x22==15x24=10 x33=30A31x31=15x32==5最小运费为：minf=2×15+7×25+6×10+9×15+3×5+4×30=5353.4平衡的运输问题及其解法上面讨论的运输问题都是产销平衡问题，但是实际问题中，产销往往是不平衡的，这时为了仍能应用表上作业法进行计算，就需要将产销不平衡问题化为产销平衡问题。(j=1,2,…,n)的销 (i=1,2,…,m)的产量，b表示销地 和前面一样，用a表示产地 ABiijj量，xij表示由Ai调运给Bj的物资数量。于是当产大于销时，即当∑a&∑bii=1j=1mnj时，运输问题的数字模型可写为：(Ⅰ)min s=∑∑cijxiji=1j=1mn?ns?t?∑xij≤aij=1??m?x=bijj?∑i=1???xij≥0(i=1,2,",m)(j=1,2,",n)(i=1,2,",m;j=1,2,",n)其中cij表示从Ai到Bj的单价物资的运价。由于总的产量大于销量，就要考虑将多余的物资就地存储起来。设xi,n+1是产地Ai的存储量，于是有nn+1j=1∑xj=1ij+xi,n+1=∑xij=ai(i=1,2,",m)或者移项得xi,n+1=ai?∑xijj=1n(i=1,2,",m)所以有∑xj=1n+1i,n+1=∑ai?∑∑xij=∑ai?∑bj=bn+1i=1i=1j=1i=1j=1mmnmn由于就地存储贮的部分运价为零，所以ci,n+1=0 (i=1,2,…,m)，于是模型（Ι）变为min S′=∑∑cijxij=∑∑cijxij+∑ci,n+1xi,n+1(Ⅱ)i=1j=1i=1j=1i=1mn+1mnm?n+1s?t?∑xij=aij=1??m?x=bijj?∑i=1???xij≥0(i=1,2,",m)(j=1,2,",n)(i=1,2,",m;j=1,2,",n)在模型(Ⅱ)中，由于∑a=∑∑x=∑∑x+∑xiijiji=1i=1j=1i=1j=1i=1mmn+1mnmi,n+1=∑bj+bn+1=∑bjj=1j=1nn+1所以这是一个产销平衡的运输问题。因此，当产大于销时，只要增加一个假想的销地Bn+1(实际上是仓库)，该销地的总需求量为mmn∑xi=1i,n+1=∑ai?∑bji=1j=1而从产地Ai到假想销售地Bn+1的单位运输费（因为是基地存贮）为ci,n+1=0。这样就转化为一个产销平衡的运输问题。同样，当销大于产时，只要增加一个假想的产地Am+1，它的产量是nnm∑xj=1m+1,j=∑bj?∑aij=1i=1而从假想产地Am+1到销地Bj的单位运价为cm+1,j=∞也同样可以转化为一个产销平衡的运输问题。例1:设有三个产地和五个销地，它们的产量和销量以及它们之间单位运价见表3-12 。试决定总运费最少的调运方案。解：产地的总产量为10+8+13=31（吨），销地的总销量为4+6+7+5+4=26（吨）所以这是一个产大于销的运输问题。按上述方法增加一个假想的销地，即表3-12存贮B6，其总存贮量为31-6=5（吨）。于是就转化为以下的产销平衡的运输问题如表3-13。表3-13再用表上作业法解这个产销平衡问题即得最优调运方案如下表3-14所示：这个最优方案明确告诉我们，A3就地存贮产地A1就地存贮2吨，3吨。表3-14例2 设有三个预制厂供应四个工地，各厂的产量，各工地需要以及从各预制厂各工地的单位运价如表3-15所示，试求总运费最少的调运方案解：这是一个产销不平衡的运输问题，总产量为160万吨，四个工地的最低年需求量为110万吨，最高需求为无限，根据现有产量，第四个工地最多能分配到60万吨，这样最高需求为210万吨，所以这是一个销量大于产量的问题，因此需要增加一个假想的预制厂A4，它的年产量为50万吨。表3-15由于各个工地的年需求量包含两部分。例如工地Ⅰ，其中30万吨是最低需求，不能由假想的预制厂A4，来供应，这只要令相对应的运价为任意大正数M，而另一部分20万吨满足不满足都可以，因此可以由假想的预制厂A4，来供应，但相应的运价为0，这样对凡是需求分两种情况的工地，实际上可以相当作两个工地来对待，于是就可以将这个问题转化为如表3-16。用表上作业法可以求得这个问题的最优调运方案如表3-17。表3-16表3-17转载请保留本文连接：分享到：相关文章声明：《【迂回运输】运输问题的求解方法》由“四毛”分享发布，如因用户分享而无意侵犯到您的合法权益，请联系我们删除。TA的分享君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
运输问题的数学模型
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口绝密★启用前；黑龙江外国语学院继续教育学院2014年秋季学期；《运筹学》试卷（A卷）；一、选择题（本大题共10小题，每小题2分，共20；1．线性规划具有唯一最优解是指（）；A．最优表中存在常数项为零B．最优表中非基变量检；则基本可行解为；A．(0,0,4,3)B．(3,4,0,0)C．；3．则（）；A．无可行解B．有唯一最优解mednC．有多重最；4．互为对
绝密★启用前
黑龙江外国语学院继续教育学院 2014 年 秋 季学期
《运筹学》试卷（ A 卷）
一、 选择题（本大题共 10小题，每小题 2分，共 20分）
1．线性规划具有唯一最优解是指（
A．最优表中存在常数项为零
B．最优表中非基变量检验数全部非零
C．最优表中存在非基变量的检验数为零
D．可行解集合有界 2．设线性规划的约束条件为（
则基本可行解为
A．(0, 0, 4, 3)
B．(3, 4, 0, 0)
C．(2, 0, 1, 0)
D．(3, 0, 4, 0)
A．无可行解
B．有唯一最优解medn
C．有多重最优解
D．有无界解
4．互为对偶的两个线性规划, 对任意
可行解X 和Y，存在关系（
D．Z≤W 5．有6 个产地4个销地的平衡运输问题模型具有特征（
A．有10个变量24个约束
B．有24个变量10个约束
C．有24个变量9个约束
D．有9个基变量10个非基变量
6.下例错误的说法是（
A．标准型的目标函数是求最大值
B．标准型的目标函数是求最小值
C．标准型的常数项非正
D．标准型的变量一定要非负 7. m+n－1个变量构成一组基变量的充要条件是（
A．m+n－1个变量恰好构成一个闭回路
B．m+n－1个变量不包含任何闭回路
C．m+n－1个变量中部分变量构成一个闭回路
D．m+n－1个变量对应的系数列向量线性相关 8．互为对偶的两个线性规划问题的解存在关系（
A．原问题无可行解，对偶问题也无可行解
B．对偶问题有可行解，原问题可能无可行解
C．若最优解存在，则最优解相同
D．一个问题无可行解，则另一个问题具有无界解 9.有m个产地n个销地的平衡运输问题模型具有特征（
A．有mn个变量m+n个约束 …m+n-1个基变量
B．有m+n个变量mn个约束
C．有mn个变量m+n－1约束
D．有m+n－1个基变量，mn－m－n－1个非基变量 10．要求不超过第一目标值、恰好完成第二目标值，目标函数是（
minZ?pd?p(d?d)minZ?pd?p(d?d) A．
??????minZ?pd?p(d?d)minZ?pd?p(d?d)
二、判断题（本大题共 15
小题，每小题 2分，共 30分）
11.若线性规划无最优解则其可行域无界X基本解为空（
） 12.凡基本解一定是可行解X同19（
13.线性规划的最优解一定是基本最优解X可能为负（
14.可行解集非空时,则在极点上至少有一点达到最优值X可能无穷（
） 15.互为对偶问题，或者同时都有最优解，或者同时都无最优解
16.运输问题效率表中某一行元素分别乘以一个常数,则最优解不变X （
17.要求不超过目标值的目标函数是 （
18.求最小值问题的目标函数值是各分枝函数值的下界 （
19.基本解对应的基是可行基X当非负时为基本可行解，对应的基叫可行基（
） 20.对偶问题有可行解，则原问题也有可行解X （
） 21.原问题具有无界解，则对偶问题不可行（
22.m+n－1个变量构成基变量组的充要条件是它们不包含闭回路 （
） 23.目标约束含有偏差变量（
24.整数规划的最优解是先求相应的线性规划的最优解然后取整得到X（
） 25.匈牙利法是对指派问题求最小值的一种求解方法（
三、填空题（本大题共 10小题，每小题 1分，共10分）
26．有5个产地5个销地的平衡运输问题，则它的基变量有（
27．已知最优基
，CB=（3，6)，则对偶问题的最优解是（
28．已知线性规划求极小值，用对偶单纯形法求解时，初始表中应满足条件（
） 29．非基变量的系数cj变化后，最优表中(
)发生变化 30．设运输问题求最大值，则当所有检验数（
）时得到最优解。
31．线性规划
第1、2个约束中松驰变量（S1,S2）= （
的最优解是(0，6),它的
32．在资源优化的线性规划问题中，某资源有剩余，则该资源影子价格等于（
33．将目标函数转化为求极小值是（
34．来源行x1?6x3?6x4
?3的高莫雷方程是（
） 35．运输问题的检验数λij
的经济含义是（
四、求解下列各题（本大题共4小题，每题10分，共40分）
maxZ?3x36．已知线性规划
?x1?2x2?x3?10
（1）求原问题和对偶问题的最优解；（2）求最优解不变时c?
j的变化范围
?2x1?x2?3x3?5
37.求下列指派问题（min）的最优解 ??5685?
38.求解下列目标规划 minz?p?d?
?1(d?34)?P2d1?P?
?1?x2?d?1?d1?40
? ?x1?x2?d??2?d2?60?x?
?30?1?d3?d?3 x???2?d4?d4?20
x??1,x2,di,di?0(i?1,
39．求解下列运输问题（min） ?854?
一、单选题1.B
10.A 二、判断题
25. √ 三、填空题
28.(对偶问题可行)
30.(小于等于0)
(minZ???x1?5x2)(s6x?56x2
34??3或s1?5x3?5x4??4) 35.xij增加一个单位总运
费增加λij 四、计算题
maxZ?3x1?4x2?5x3
x1?2x2?x3?x?410
?2x1?x5?2?3x3?x?5
（1）化标准型
?0，j?1,2,,5
（2）单纯形法
（3）最优解X=(0，7，4)；Z＝48
（4）对偶问题的最优解Y＝（3.4，2.8）
（5）Δc-17/2，Δc1?(??,9),2??,c3??1
1≤6，Δc2≥3≥-6，则3
三亿文库包含各类专业文献、文学作品欣赏、各类资格考试、高等教育、应用写作文书、生活休闲娱乐、外语学习资料、中学教育、运筹学试卷A 以及 答案31等内容。　
　运筹学试题及答案(两套)_教育学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 运筹学试题及答案(两套)_教育学_高等教育_教育专区。运筹学 A 卷)一... 　运筹学期末考试试卷及答案运筹学期末考试试卷及答案隐藏&& &&运筹学&&期末试卷(A)一、不定项选择题(每小题 2 分共 20 分) 1、配送是一种先进的物资管理模... 　运筹学考试题a卷及答案_理学_高等教育_教育专区。运筹学期末考试题(a 卷)注意事项: 1、答题前,考生务必将自己的姓名、班级填写在答题卡上。 2、答案用钢笔或圆... 　最全的运筹学复习题及答案_管理学_高等教育_教育专区。四、把下列线性规划问题...A.纯整数规划 B.混合整数规划 C.0―1 规划 D.线性规划 3.下列方法中用于... 　运​筹​学​试​卷​A​及​参​考​答​案北京理工大学 《运筹学》期终试卷(A 卷) 姓名注意:① 答案一律写在答题纸上,写在其他地方无效。... 　2013《运筹学》考试题及其答案_理学_高等教育_教育专区。运筹学试题及答案2012...4 x1 ? x2 沿其法线方向逐渐向上平移,直至 A 3 6 3 6 18 点,A 点的... 　《运筹学》模拟试题及答案_理学_高等教育_教育专区。^ 高等教育《运筹学》模拟...并依此,我们把决策问题分为三 类,下列哪项不是( D ) A 确定性决策问题 B... 　运筹学试题及答案._工学_高等教育_教育专区。运筹学试题及答案 一、填空题(本...19.线性规划问题的标准型最本质的特点是 A.目标要求是极小化 C.变量和右端... 　运筹学试题及答案_工学_高等教育_教育专区。一、填空题: (每空格 2 分,共 ...Ⅰ A B C 单位产品利润(元) 1 10 2 10 Ⅱ 1 4 2 6 Ⅲ 1 5 6 4...一、判断题
1．运输问题是一种特殊的线性规划模型，因而求解的结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解．
2．在运输问题中，只要任意地给出一组含m+n-1个非零的{xij}，且满足
=ai，∑xij=bj，就可以作为一个初始基本可行解．
3．按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路．
4.如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化．
5.如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化．
6.当所有产地的产量和所有销地的销量均为整数时，运输问题的最优解也为整数值．
7.如果运输问题单位运价表的全部元素乘上一个常数k（k&0），最优调运方案将不会发生变化．
8.用位势法求运输问题某一调运方案的检验数时，其结果可能同闭回路法求得的结果有异．
9.m+n-1个变量构成基变量组的充要条件是它们不包含闭回路．
10. 运输问题的可行解中基变量的个数一定遵循m+n-1的规则．
二、选择题
1.在求解运输问题的过程中运用到下列哪些方法（
） A．西北角法
C. 闭回路法
2．在运输方案中出现退化现象，是指数字格的数目 (
A．等于m+n
B．等于m+n-1
C．小于m+n-1
D．大于m+n-1
3．在产销平衡运输问题中，设产地为m个，销地为n个，那么基可行解中非零变量的个数（
A. 不能大于m+n-1；
B. 不能小于m+n-1； C. 等于m+n-1 ；
4 . m+n-1个变量构成一组基变量的充要条件是（
A．m+n-1个变量恰好构成一个闭回路
B．m+n-1个变量不包含任何闭回路
C．m+n-1个变量中部分变量构成一个闭回路
D．m+n-1个变量对应的系数列向量线性相关
5.有m个产地n个销地的平衡运输问题模型具有特征（
A．有mn个变量m+n个约束m+n-1个基变量
B．有m+n个变量mn个约束
C．有mn个变量m+n-1约束
D．有m+n-1个基变量，mn-m-n+1个非基变量
三、填空题
1．有5个产地5个销地的平衡运输问题，则它的基变量有（
）个 2．设运输问题求最大值，则当所有检验数（
）时得到最优解。 3．运输问题的检验数σij与对偶变量ui,vj之间存在关系（
） 4．运输问题的检验数σij的经济含义是（
5．运输问题中m+n-1个变量构成基变量的充要条件是（
四、计算题
1．某一运输问题的产销平衡表和单位运价表如下图所示：
用表上作业法求最优解.
2．已知运输问题的产销地的供需量与单位运价表如下表所示，试用表上作业法求此运输问题的最优解．
一、判断题
1.整数规划的最优解是先求相应的线性规划的最优解然后取整得到．
2. 整数规划模型不考虑变量的整数约束得到的相应的线性规划模型，如该模型有无穷多最优解，则整数规划模型也一定有无穷多最优解． 3．用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值．
4. 一个整数规划问题如果存在两个以上的最优解，则该问题一定有无穷多最优解． 5．用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝．
6．整数规划解的目标函数值一般优于其相应的线性松弛规划问题的解的目标函数值． 7．用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解．
8．指派问题的效率矩阵的每个元素都乘上同一常数k(k&0)，将不影响最优指派方案．
9．指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解．
10．分支定界法在需要分支时必须满足：一是分支后的各子问题必须容易求解，二是各子问题解的集合必须覆盖原问题的解． 二、选择题
1．下列说法错误的是（
A．整数规划解的目标函数值一般优于其相应的线性规划问题解的目标函数值；
B．用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值；
C．指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解；
D．求解0-1规划的隐枚举法是分枝定界法的特例。 三、填空题
1．割平面法中，来源于行x1+x3-x4=的割平面方程是（
2．割平面法中，来源于行x2-x3+x4=的割平面方程是（
3．求解某纯整数规划问题的线性松弛模型得最优解为x1=5.8,x2=0，应该如何构造分支条件__________________.
第六章动态规划
一、判断题
1．在动态规划模型中，问题的阶段数等于问题中的子问题的数目；
2．动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性； 3．动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策；
4．对一个动态规划问题，应用顺推或者逆推解法可能会得出不同的最优解； 5．在动态规划基本方程中，凡子问题具有叠加性质的，其边界条件取值均为零，子问题为乘积型的，边界条件取值均为1；
6．一个线性规划问题若转化为动态规划方法求解时，应严格按变量的下标顺序来划分阶段，如将决定x1的值作为第一阶段，决定x2的值作为第二阶段等。
7．动态规划是用于求解多阶段优化决策的模型和方法，这里多阶段既可以是时间顺序的自然分段，也可以是根据问题性质人为的将决策过程划分成先后顺序的阶段。 二、选择题
1．以下关于动态规划的陈述中不正确的是（
A．使用动态规划必须满足无后效性的原则 B．动态规划可求解多阶段优化问题
C．动态规划的指标函数要满足可分离性、单调性、递推性 D．动态规划只能倒推求解
2．关于动态规划问题的下列命题中（
）是错误的。
A、动态规划阶段的顺序与求解过程无关；
B、状态是由决策确定的；
C、用逆序法求解动态规划问题的重要基础之一是最优性原理；
D、列表法是求解某些离散变量动态规划问题的有效方法。
三、计算题
1．某工厂有100台机器，准备生产A,B两种产品，若生产产品A,每台机器
每年可收入10万元，年完好率为，若生产产品B，每台机器年收入为7万元，
年完好率，三年后这批机器将全部淘汰，试问每年如何生产，使三年内的收
入最多？运用动态规划方法具体计算求解．