管理运筹学基础Word下载.docx
《管理运筹学基础Word下载.docx》由会员分享,可在线阅读,更多相关《管理运筹学基础Word下载.docx(25页珍藏版)》请在冰点文库上搜索。
8.
运输问题的求解结果可能出现下列4种情况之一:
有唯一解;
有无穷多最优解;
无界解;
可行解。
9.
在运输问题中,只要给出一组含有(m+n-1)个非零的xij且满足全部约束,就可以作为基本可行解。
10.
整数规划解的目标函数值一般优于其相应的线性规划问题的目标函数值。
11.
用割平面法求解整数规划时,构造的割平面有可能切去一些不属于最优解的整数解。
12.
第一个顶点和最后一个顶点相同的闭链叫回路。
13.
任一运输网络中至少存在一个流。
14.
Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。
三、主观题(共3道小题)
15.
简述编制统筹图的基本原则。
参考答案:
统筹图是有向图,箭头一律向右;
统筹图只有一个起始点。
一个终点,没有缺口;
两个节点之间只能有一个作业相连;
统筹图中不能出现闭合回路。
16.
已知线性规划
maxZ=
3x1
+x2
+3x3
(1)、求出不考虑x3为整数约束时的最优解。
(2)、写出分支条件及约束方程。
(3)、求最优解。
(1)x1
=16/3
,x2
=3,x3
=10/3
;
(2)[10/3]=3,
x3≥4或x3≤3;
-4/9x1
–1/9x5
–4/9x6
+x7
=-1/3;
=2/3
17.
简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。
西北角法:
按照地图中的上北下南,左西右东的判断,对调运表中的最西北角上的空格优先满足最大供应,之后划去一行或一列,重复这种做法,直至得到初始可行解。
最小元素法:
对调运表中的最小运价对应的空格优先没醉最大供应,之后划去一行或一列,重复这种做法,直至得到初始可行解。
差值法:
在运价表中,计算各行和各列的最小运价和次最小运价之差,选出最大者,它所在某行或某列中的最小运价对应的空格优先满足最大供应,重复这种做法,直至得到初始可行解。
一般来讲,用差值法求出的初始可行解最接近最优解,也就是最优的。
管理运筹学B第2次作业
本次作业是本门课程本学期的第2次作业,注释如下:
二、判断题(判断正误,共16道小题)
线性规划一般模型中的变量不一定是非负的。
用图解法求最优解时,只需求出可行域顶点对应的目标值,通过比较大小,就能找出最优解。
图解法与单纯形法求解的形式不同,但从几何上理解,两者是一致的。
单纯形法计算中,选取最大正检验数对应的变量作为换入变量,将使目标函数的值增加更快。
若原问题可行,而对偶问题不可行,则原问题无界。
若原问题有无穷多最优解,则其对偶问题也一定有无穷多最优解。
按最小元素法给出的初始基本可行解,从每一个空格出发仅能找出唯一的闭回路。
表上作业法中,任何一种确定初始基本可行解的方法都必须保证有(m+n-1)个变量。
用分枝定界法求解一个极大化整数规划问题时,任何一个可行解的目标函数值是该问题目标函数值的下界
用割平面法解整数规划问题时,要求包括松弛变量在内的全部变量必须取整数。
有向图G中任意两点是可达的,称此图为强连通图
数T的任两顶点间恰有一条初等链。
G的任一流f的流值valf可能超过任一割的容量。
f为G上一个流,若e为f不饱和边,那么e也一定为f正边。
统筹网络中任一节点都表示前一道工序的结束和后一道工序的开始
.在统筹网络图中只能有一个始点和一个终点。
三、主观题(共8道小题)
Djisktra算法能否求有负权的有向图中两点间的最短路径,举例说明。
Djisktra算法不能求有负权的有向图中两点间的最短路径。
如下图:
左边的点为v1,右边的点为v3,下面的点为v2,若v1到v2的权重为1,v1到v3的权重为2,v3到v2的权重为-3,则,若用Djisktra算法则最短路径的数值不能收敛,致使求不出最优解。
18.
指出统筹图网络中的错误,并改正。
(1)e,d工序有错。
(2)两个终点。
(3)两个始点,两个终点。
(4)工序循环不是统筹图。
19.
简述在求最大流过程中,寻找由到源到汇的不饱和链的方法。
标号法寻找增流链的步骤:
第一步:
对未检查的边(u,v)的顶点v进行标号,标号的方式为(u,边的方向,l(v)),其中标号的各个部分按照如下确定:
(1)u:
表示被标号点v的前一个顶点。
(2)边的方向:
当被标号点v为终点时,即边(u,v)为前向边时,用“+”标示;
当被标号点v为始点时,即边(u,v)为后向边时,用“-”标示。
(3)l(v):
当被标号点v为终点时,l(v)=min{l(u),c(u,v)-f(u,v)};
当被标号点v为始点时,l(v)=min{l(u),f(u,v)}。
另外,默认源x的标号为(0,+,+∞)。
第二步:
继续检查,判断顶点v后面的边(v,z)能否成为增流链的边,边(v,z)若成为增流链中的边所具备的条件如下:
(1)如果边(v,z)是前向边,则应该有f(v,z)<
c(v,z)。
由前面知识可知,前向边流量只能增加,那么边(v,z)就不能是饱和边。
(2)如果边(v,z)为后向边,则必有f(v,z)>
0。
由前面知识可知,后向边流量只能减少,那么边(v,z)就不能是零边。
第三步:
若边(v,z)能够成为增流链的边,就使顶点z成为被标号的点,再对被标号点z按照第一步的标号方式进行标号。
第四步:
返回第二步,不断循环,直至不能找到被标号点,则反向追踪找出不饱和链。
20.
用标号法求图所示的网络中从vs到vt的最大流。
(1)Valf=5
(2)Valf=7
21.
简述分枝定界法的主要步骤
先不考虑整数约束条件,对一般情况的线性规划问题用单纯形法或对偶单纯形法求解。
如果求出的最优解满足整数规划问题的所有整数约束条件,那么这个最优解也就是整数规划问题的最优解,如果有一个或多个整数约束条件没有被满足,转到第二步。
任意选择一个应该是整数而不是整数解的变量xk,设它的非整数解是bk,同时设bk对应的整数位是[bk],现在将原问题分成两枝,一枝是在原问题的基础上,增加约束条件xk≤[bk];
另一枝是在原问题的基础上,增加约束条件xk≥[bk]+1,这样就构成了两个新的线性规划问题的子问题。
按照第3.3节对偶单纯形法扩展应用的思路,分别对分枝后的两个新线性规划子问题继续求解。
若新的解不满足原问题整数约束,再按第二步进行新的分枝,直到满足下面的情况停止分枝:
22.
已知某整数规划不考虑整数约束时最优单纯型表,写出一个割平面方程。
-1/7x3
–2/7x5
+x6
=-6/7;
23.
求解下列0-1规划问题的解。
(1)
minZ=8x1
+2x2
+4x3
+7x4
+5x5
(1)(x1
,x3
,x4
,x5)=(0,1,1,0,0),Z=6
(2)(x1
,x5)=(1,1,0,0,0),Z=5
(3)(x1
,x5)=(0,0,1,1,1),Z=6
24.
简述运输方案的调整过程。
确定换入变量
同单纯形法一样,在所有的负检验数中,一般选取检验数最小的非基变量作为换入变量。
确定换出变量和调整量
由定理5.4可知,由此时还是非基变量的换入变量和一组基变量可以组成一个唯一的闭回路,找到这个闭回路以后,以此非基变量为起点,取此闭回路中偶数顶点取值最小的基变量做为换出变量,调整量的量值即为此基变量的值。
调整方法
(1)闭回路以外的变量取值均保持不变。
(2)针对闭回路,奇数顶点变量的值全部加上调整量,偶数顶点变量的值全部减去调整量。
标识方法
为了保证基变量的个数为m+n-1个,在标识上作如下处理:
(1)调整后,原来作为非基变量的换入变量就变成了基变量,所以要把这个变量的值标识成“○”。
(2)调整后,原来作为基变量的换出变量就变成了非基变量,所以要在这个变量的位置打上“×
”。
第五步:
继续求检验数,如果存在负的检验数,就返回第一步,否则计算停止,说明找到了最优解。
管理运筹学B第3次作业
本次作业是本门课程本学期的第3次作业,注释如下:
二、判断题(判断正误,共11道小题)
一般情况下,松弛变量和多余变量的目标函数系数为零。
用单纯形法求解标准型线性规划问题时,与检验数大于0相对应的变量都可被选作换入变量。
由应用问题建立的线性规划模型中,其约束方程有多种形式
yi为对偶问题的最优解,若yi>
0,说明在最优生产计划中第i种资源已完全耗尽。
当所有产量和销量均为整数值时,运输问题的最优解也为整数解。
整数规划问题的可行解与其线性规划问题的可行域内的整数点相对应。
任一图G中,当点集确定之后,树图是G中边数最少的连通图。
在有向图中,如图所示
中的边e和eˊ是平行边
若Q为f饱和链,则链中至少有一前向边条边为f饱和边,同时至少有一条边后向为f零边。
既要满足流值最大又要满足费用最小的流是不存在的。
标号法每迭代一步,没有取得永久性标号顶点的标号都会被改变一次。
三、主观题(共9道小题)
求下列图中的指定顶点
(1)到(5)的最短距离和路(径)。
(1)路线:
(1)—(4)—(3)—(5)
(2)路径:
(1)→(3)→
(2)→(4)→(5)
简述在求最小费用流的过程中,寻找由到源到汇的不饱和链的方法
如果运输网络G的流值没有达到A,先用最大流算法把流值调到A;
如果运输网络G的流值达到A,则不对网络流调整。
针对流值为A的运输网络G,构建伴随网络流f的增流网络Gf
。
针对增流网络Gf,查看是否存在基于w′的负回路,如果不存在负回路,说明当前的网络流已经是最小费用流,算法终止,否则转到下一步。
针对存在的负回路C,令δ=min{c′(e),e为Gf中负回路的边}。
针对负回路C对应运输网络G中的圈,判断该圈是否为增流圈,如果不是增流圈,转到第三步继续寻找负回路,否则转到下一步。
第六步:
针对运输网络G中的增流圈,按照定理9.5,把增流圈中方向与负回路方向一致的所有不饱和边的流量加上δ;
把增流圈中方向与负回路方向相反的所有正边的流量减去δ。
第七步:
继续寻找负回路,如果有负回路,继续调整,否则返回第二步。
根据对偶规则填表:
简述如何在单纯型表上判别问题是否具有唯一解、无穷多解、无界解或无可行解
将检验数cj-zj作为判断基本可行解是否为最优解的标准,判断的方法如下:
(1)若所有非基变量的检验数cj-zj<
0,已经达到最优解;
(2)若存在cj-zj>
0,但所有cj-zj>
0所在列对应的所有aij≤0,无界解;
(3)从几何意义的角度就是说,约束条件方程组没有可行域,则线性规划问题五可行解;
(4)在最优单纯形表中,如果出现检验数等于0的个数多于基变量的个数,线性规划模型就有多重解。
简述若标准型变为求目标函数最小,则用单纯形法计算时,如何判别问题已取得最优解。
对目标函数为极小化线性规划问题时,则用单纯形法计算时,当所有非基变量的检验数大于或等于零时,已经达到最优解;
建立下列问题的线性规划模型并化为标准型
某工厂生产A1、A2两种产品,有关的信息由下表给出,建立制定最优生产计划的模型(利润最大)。
提示:
设产品A1、A2的产量分别为x1、x2个单位,maxZ=70x1+120x2
某工厂生产A、B两种产品,已知生产A每公斤要用煤9吨、电4度、劳动力3个;
生产B每公斤要用煤4吨、电5度、劳动力10个。
又知每公斤A、B的利润分别为7万元和12万元。
现在该工厂只有煤360吨、电200度、劳动力300个。
问在这种情况下,各生产A、B多少公斤,才能获最大利润,请建立模型。
设A、B各生产x1、x2公斤,maxZ=7x1+12x2
目标函数中人工变量前面的系数±
M(M是充分大的正数)的作用是
使人工变量不可能进入最优解
解包含人工变量线性规划问题的单纯形法有
有
大M法、两阶段法
管理运筹学B第4次作业
本次作业是本门课程本学期的第4次作业,注释如下:
三、主观题(共4道小题)
找出下列线性规划问题的一组可行解和基本可行解。
可行解是满足约束条件的解,基本可行解是与基列(线性无关)对应的可行解。
目标函数为maxZ=28x4+x5+2x6,约束形式为“≤”,且x1,x2,x3为松弛变量,表中的解代入目标函数中得Z=14,求出a~g的值,并判断是否最优解。
a=7,b=-6,c=0,d=1,e=0,f=1/3,
g=0;
最优解
用单纯形法求解下列线性规划。
(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,0),Z=-9
某工厂生产A、B两种产品,每公斤的产值分别为600元和400元。
又知每生产1公斤A需要电2度、煤4吨;
生产1公斤B需要电3度、煤2吨,该厂的电力供应不超过100度,煤最多只有120吨,问如何生产以取得最大产值?
建立模型,用图解法求解。
设A、B各生产x1、x2公斤,maxZ=600x1+400x2,
(x1、x2)=(20,20),产值最大为20000元。