分支定界法作业题

1、 用分支定界法解下列整数规划：解题思路：把原线性规划问题模型化为标准形式，用单纯形法或对偶单纯形法求解整数规划问题对应的线性规划问题的最优解，根据解的情况进行分支（即增加约束条件），定界（即不断缩小可行域）。

对各个分支继续求解，再分支，直到解出最优解。

2.用割平面法解下列整数规划解题思路：先将原问题化为标准形式，列出初始单纯形表，用单纯形法解出原问题对应线性规划问题的最优解。

然后根据割平面法，加入新的约束条件（即割平面方程），得到新的规划问题。

用单纯形法或对偶单纯形法继续求最优解。

参考答案：3.写出下列线性规划问题的对偶问题。

解题思路：根据原问题与对偶问题的关系（见表2-4），求出 对偶问题。

参考答案：⎪⎪⎩⎪⎪⎨⎧≥≤+≤+-≤+且为整数,0,21260521212121x x x x x x x x 212max )1(x x z +=21max )1(x x z +=⎪⎩⎪⎨⎧≥≤+≤+且为整数,0,205462212121x x x x x x )0,47,0,0,25,45,1(*=X 321422min x x x z ++=⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++无约束321321321321,0,534332243x x x x x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧≤≥=++≤++≤++无约束321321321321,0,0434243222y y y y y y y y y y y y4.试用对偶单纯形法求解下列线性规划问题。

解题思路：先将原问题化为标准形式的线性规划问题依据对偶，列出初始单纯形表。

然后按照对偶单纯形法计算步骤解题。

参考答案：最优解：5.用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

解题思路：根据图解法步骤，建立直角坐标系，并根据约束条件画出可行域，图示出目标函数。

然后目标函数直线在梯度方向平行移动，在可行域内找到最优解。

第3章作业分配问题问题描述题1:作业分配问题：设有A,B,C,D,E, …等n个人从事J1,J2,J3,J4,J5,…等n项工作，每人只能从事一项任务，每个任务由不同的工人从事有着不同的费用，求最佳安排使费用最低。

要求：输出每人所从事的工作任务以及最佳安排的最低费用。

题2:有两艘船和需要装运的n个货箱，第一艘船的载重量是c1，第二艘船的载重量是c2，Wi是货箱i的重量，且W1+W2+W3+W4+......+Wn<=c1+c2。

希望确定是否有一种可将所有n个货箱全部装船的方法。

要求:输出每艘船最终载重量.问题分析分支搜索法是一种在问题解空间上进行搜索尝试的算法。

是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。

和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。

然后从表中选择一个结点作为下一个E-结点,断续搜索。

在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：(1)产生当前扩展结点的所有孩子结点；(2)在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；(3)将其余的孩子结点加入活结点表；(4)从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。

分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。

题1:先看一个实例,设有A,B,C,D,E 5人从事J1,J2,J3,J4,J5项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使效益最高。

要求：输出每人所从事的工作项目以及最佳安排的最高效益。

考虑任意一个可行解,例如矩阵中的对角线是一个合法的选择,表示将任务J1分配给人员A,任务J2分配给人员B,任务J3分配给人员C,任务J4分配给D,任务J5分配给E,其总效益是10+10+7+11+4=42;或者应用贪心法求得一个近似解:人员A从事J2时效益最大,将任务J2分配给人员A,剩余工作中人员B从事J1时效益最大,任务J1分配给人员B,J3、J4、J5中人员D从事J4时效益最大,任务J4分配给人员D,J3和J5中人员C从事J3时效益最大,任务J3分配给人员C,任务J5只能分配给人员E,其总效益是11+13+11+7+4=46.显然,42和46都不能确定是最优解,有可能还有比其更大的效益,这两个解其一并不一定是一个最可行的选择,它们仅仅提供了一个参考,这样,可以以其中一个作为参考来进一步对各种作业分配方案进行搜索,比较其每种分配方式的效益.最大的总效益为最优解,其分配方案为最佳分配方案.题2:先看一个实例,当n=3,c1=c2=50,w={10,40,40}时,可将货箱1,2装到第一艘船上,货箱3装到第二艘船上.但如果w={20,40,40},则无法将货箱全部装船.由此可知问题可能有解,可能无解,也可能有多解.下面以找出问题的一个解为目标设计算法.虽然是关于两艘船的问题,其实只讨论一艘船的最大装载问题即可.因为当第一艘船的最大装载为bestw时,若w1+w2+…+wn-bestw<=c2则可以确定一种解,否则问题就无解.这样问题转化为第一艘船的最大装载问题.算法设计题1:问题的解空间为一个子集树,所有可能的解都可通过一个求解树给出.也就是算法要考虑任务是否分配给人员的情况组合,n个任务分配给n个人员的组合共n*n种情况,作业分配子集树是n=4的子集树它是用FIFO分支搜索算法解决该问题的扩展结点的过程编号的.1 个人作业分配2 3 13 4 2 24 5 3 4 5 35 4 5 5 4 4作业分配子集树在任务分配中,如实例中若n=4时,J1分配给A则向左走,否则往右走,直到走到最后,把最终的总效益求出,并把第一次求出的总效益作为最大效益与后边的总效益相比较,比其大者,交换两者,大的作为最大效益.依次方法,直到找到最优解,并输出其值以及其最大效益时的最佳分配方案.(1)用FIFO分支搜索所有的分支,并记录已搜索分支的最优解,搜索完子集树也就找出了问题的解.图中结点1为第零层,是初始E-结点;扩展后结点2,3为第一层;3,4,2是第一个任务分配出去后的下一层扩展结点,4,5,3,4,5是第二个任务分配出去后下一层的扩展结点(即分配情况).(2)用task[i]来表示任务是否分配及分配了给哪个工人,即task[i]=0时表示任务i 未分配, task[i]=j表示任务i分配给了工人j;用worker[k]=0或1来表示工人k是否分配了任务, worker[k]=0表示工人k未分配任务, worker[k]=1表示工人k已分配了任务.(3)把最低费用用mincost来表示和c[i][j]表示工人j执行任务i时的费用,并把c[i][j]和mincost分别初始化为c[1000][1000]和100000;同时把ask[i]和temp[i]、worker[i]的存储空间初始为task[1000]和temp[1000]、worker[1000],之后把其初始化为0.(4)用Plan(int k,unsigned int cost)来对分配作业的解空间树进行搜索,搜索的时候,每个活结点要记录下搜索的路径(即分配方案),存储在temp[i]中,并求出费用cost,然后cost与最小费用mincost进行比较,较小者是最小费用,其分配方案为最佳分配方案.(5)下面的算法中用Plan(int k,unsigned int cost)中的第二个for循环来实现对解空间树的搜索,第一次for(i=0)时，找出0号工人分别执行0，1，2，3，4号任务时总花费最小;第二次for(i=1)时，找出1号工人分别执行除0号工人的任务以外任务时总花费最小，并与i=0时的总花费最小比较;…;第五次for(i=4)时，找出总花费最小，并与上次的总花费最小比较;依次类推对解空间树进行搜索.第一个for循环把cost 与mincost进行比较,求出最小费用并记录出最小费用的分配方案.题2:转化为一艘船的最优化问题后,问题的解空间为一个子集树(问题的解空间树中的子集树).也就是算法要考虑所有物品取舍情况的组合.(1)要想求出最优解,必须搜索到叶结点.所以要记录树的层次,当层次为n+1时,搜索完全部叶结点,算法结束.不同于回溯算法,分支搜索过程中活结点的“层”是需要标识的,否则在入队后无法识别结点所在的层.下面算法,每处理完一层让“-1”入队,以此来标识“层”,并用记数变量i来记录当前层.(2)每个活结点要记录当前船的装载量.(3)为了突出算法思想,对数据结构队及其操作只进行抽象描述.用Queue代表队列类型，则Queue Q：定义了一个队列Q，相关操作有：add（Q，….）表示入队；Empty（Q）测试队列是否为空，为空则返回真值。

《运筹学》试题及答案一、单选题1. μ是关于可行流f的一条增广链，则在μ上有（D）A.对一切B.对一切C.对一切D.对一切2.不满足匈牙利法的条件是(D)A.问题求最小值B.效率矩阵的元素非负C.人数与工作数相等D.问题求最大值3.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法4.串联系统可靠性问题动态规划模型的特点是（）DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.当基变量x i的系数c i波动时，最优表中引起变化的有(B)A.最优基BB.所有非基变量的检验数C.第i 列的系数D.基变量X B6.当非基变量x j的系数c j波动时，最优表中引起变化的有(C)A.单纯形乘子B.目标值C.非基变量的检验数D. 常数项7.当线性规划的可行解集合非空时一定(D)A.包含点X=(0,0,···,0)B.有界C.无界D.是凸集8.对偶单纯形法的最小比值规划则是为了保证(B)A.使原问题保持可行B.使对偶问题保持可行C.逐步消除原问题不可行性D.逐步消除对偶问题不可行性9.对偶单纯形法迭代中的主元素一定是负元素（）AA.正确B.错误C.不一定D.无法判断10.对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（）BA.换出变量B.换入变量C.非基变量D.基变量11.对LP问题的标准型：max,,0Z CX AX b X==≥，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值Z必为（）BA.增大B.不减少C.减少D.不增大12. 单纯形法迭代中的主元素一定是正元素( ）AA.正确B.错误C.不一定D.无法判断13.单纯形法所求线性规划的最优解（）是可行域的顶点。

AA.一定B.一定不C.不一定D.无法判断14.单纯形法所求线性规划的最优解（）是基本最优解。

第06章流水生产线设计_题库
一、名词解释（20分，每小题5分）
1、流水生产
2、流水线平衡
3、分支定界法
4、流水线节拍
二、填空题（20分，每小题2分）
1、进行流水线作业方法改善的改善四要法(ECRS)包括：、、、。

2、流水线平衡的方法有：、。

3、流水线按生产对象的数目可以分为：、。

4、流水线按连续程度可以分为：、。

三、选择题（10分，每小题5分）
1、流水线生产适合下列哪种生产方式（）。

A.大量生产
B.成批生产
C.单件小批生产
D.定制生产
2、当设备负荷系数Ka>0.75时，该流水线是（）。

A.间断流水线
B.连续流水线
C.成组流水线
D.可变流水线
四、简述题（20分，每小题10分）
1、简述流水线平衡的方法。

2、对给定的流水线进行平衡,如何确定闲置时间比率?
五、计算题（30分，每小题15分）
1、欲使有17项作业的生产线平衡.作业时间最长的为1.2min,所有作业的时间之和为18min,该生产线每天工作540min.
1)可能的最小和最大的节拍分别是多少?
2)从理论上看,该生产线的产量范围是什么?
3)如果要求达到最大的产量,最少所需工作地数是多少?
2、12个作业进行流水线平衡，工作时间及先后顺序如表所示。

已知节拍为1.5min
1)画出产品装配网络图。

例：现有三个投资项目（如下表），总投资500万元，第一年和第二年投资限额目标函数：maxNPV = B j,t −C j,t 1+i −tn t=0∙x j m j=1= −50× 1+10% −1−50× 1+10% −2+20× P A ,10%,10∙ P F ,10%,2 x 1+ −80× 1+10% −1−70× 1+10% −2+30× P A ,10%,10∙ P F ,10%,2 x 2+ −110× 1+10% −1−90× 1+10% −2+40× P A ,10%,10∙ P F ,10%,2 x 3+ −100× 1+10% −1−100× 1+10% −2+50× P A ,10%,10∙ P F ,10%,2 x 4+ −150× 1+10% −1−100× 1+10% −2+65× P A ,10%,10∙ P F ,10%,2 x 5即目标函数为：max NPV =14.79x 1+21.77x 2+28.75x 3+80.35x 4+111.07x 5；约束条件：1、总投资不超过500万100x 1+150x 2+200x 3+200x 4+250x 5≤500；2、第1年投资约束260万50x 1+80x 2+110x 3+100x 4+150x 5≤260；3、第2年投资约束260万50x 1+70x 2+90x 3+100x 4+100x 5≤260；4、互斥约束x 2+x 3≤1；x 4+x 5≤1；5、项目的不可分性x j=0,1 j=1,2,3,4,5；一、分支定界法求解上述问题：分成四个部分：1、100x1+150x2+200x4≤500 50x1+80x2+100x4≤260 50x1+70x2+100x4≤2602、100x1+150x2+250x5≤500 50x1+80x2+150x5≤260 50x1+70x2+100x5≤2603、100x1+200x3+200x4≤500 50x1+110x3+100x4≤260 50x1+90x3+100x4≤2604、100x1+200x3+250x5≤500 50x1+110x3+150x5≤260 50x1+90x3+100x5≤260其中，x j=0,1 j=1,2,3,4,5；对于不等式组1，采用分支定界法。

1.问题重述利用分支定界算法求解从甲地（Num.1）到乙地（Num.50）的最短路径，且需要满足花费小于1500。

一共有50座城市，城市之间相连的有向路径长度由M1.txt给出，9999代表不连通；城市之间有向路径的花费由M2.txt给出。

2.算法设计构建状态树，树上每个节点记录状态，从出发点到当前节点的距离length、花费cost、路径path[]；从节点i，经过可行边到节点j。

搜索操作若某个节点没有被剪枝掉，即存在最优解的可能，进行下一步搜索。

对于当前节点i，分别去搜索每一个从该点出发的边，若边的长度不是9999，且边的另一边的点并没有被访问过，且扩展点后的状态满足要求，则拓展该点信息，根据当前状态计算该点状态，继续搜索。

剪枝操作设从节点i到终点的最少花费为minCost[i]，若当前花费curCost+ minCost[i]>1500，则进行剪枝；同理，若从节点i到终点的最短长度为minLen[i]，若当前长度curLen+minLen[i]>bestLen，则进行剪枝。

当扩展边时，若目标点已经被扩展过、当前花费curCost+edge.cost> 1500、curLen+edge.len>bestLen，则进行剪枝。

更新答案当搜索到终点时，若当前解满足条件且更优，则更新答案（包括花费、长度、路径）。

3.算法实现和结果伪代码dfs(int curPoint)// dfs搜索，分支定界算法// 输入：当前节点curPoint// 输出：无，但是会更新全局变量最优解// 到达终点if curPoint = 终点if curCost满足要求 && curLen满足要求更新最优解endreturn;end// 剪枝//（其中curPoint到终点的最小花费和最小长度通过dijstra算法预处理得到）if 当前花费 + curPoint到终点最小花费 > 1500 || 当前长度 + curPoint到终点最小长度 > 最优长度 return;end// 搜索for 边e in curPoint的所有有效边if e.end未被访问 && 当前花费 + e.cost <= 1500 && 当前长度 + e.len <= 最优长度e.end被访问;当前花费 += e.cost;当前长度 += e.len;当前路径添加 e.end;dfs(e.end);e.end未被访问;当前路径删除 e.end;当前花费 -= e.cost;当前长度 -= e.len;endend预处理为了获得各个点到终点的最短长度和最小花费，且只需要获得该数据，为了达到更好的时间复杂度，因此使用优先队列优化的dijstra算法，利用反向图，得到终点到任意点的最短长度和最小花费，从而得到各个点到终点的最短长度和最小花费。