精品资料（2021-2022年收藏）倪金霞B0807109二章航空运输规划作业第二章习题

1、航空运输规划学作业 学院： 民航学院 学号： B0807109 姓名： 倪金霞 Email: njx1210 日期：2009年3月24日第二章 思考题和练习题思考题1、整数规划求解的困难在哪里？你学过的整数规划求解算法有哪些？这些算法的效率如何？整数规划求解的困难在于：整数规划属于组合优化问题，具有NP难解性。大规模的整数规划问题的难解性，已经成为解决问题难以逾越的障碍，不得以放弃最优解的获得，退而求其次，用启发式算法获得次优解或满意解。整数规划求解算法有：（i）分枝定界法可求纯或混合整数线性规划。（ii）割平面法可求纯或混合整数线性规划。（iii）枚举法穷举法和隐枚举法。其中隐枚举法可求解“

2、0-1”整数规划，包括：过滤隐枚举法；分枝隐枚举法。（iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法求解各种类型规划。分枝定界法由于使用灵活且便于用计算机求解，已是求解整数规划的重要方法。现在它已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等，但不是多项式算法，有时需要与其它算法结合才能解决问题；割平面法用于求解纯整数规划问题时，会遇到收敛很慢的情形，有时和分枝定界法配合使用；枚举法不能用于求解大规模整数规划问题。2、什么是组合优化问题？整数规划和网络流问题是组合优化问题吗？你能举出几个组合优化的典型问题吗？问题的可行解个数是用问题规模

3、的排列或组合数来计算的，这一类问题叫做组合优化问题。如果对这类问题采用枚举法寻找最优解，算法的复杂度是用问题规模的阶乘来表示的，因此是指数型算法。一般这类问题不易找到多项式算法，通常是NP完全问题。整数规划问题和网络流问题属于组合优化问题。典型的组合优化问题有：旅行推销员问题、运输问题、工作指派问题、货物装箱问题、最短路问题、最大（小）支撑树问题、最优边无关集问题、最小截集问题等。3、什么是算法的复杂度？如何分析算法的复杂度？什么叫做NP问题，什么叫做NP完全问题，什么叫做NP难问题？以问题的变量数或/和约束条件数表达问题的规模，当把求解该问题的计算量表达成问题规模的函数形式时，且不计常数项和

4、常系数，写成如O(n3)或O(2n)形式，叫做算法的复杂度。即解决问题的一个具体的算法的执行时间，这是算法的性质。算法的复杂度分析总是考虑最坏的情形，因此如果这种最坏情形很难发生，则这种计算复杂度的代表性比较差。有时指数型算法的表现好于多项式的算法。例如线性规划问题的单纯形算法在最坏的情形下被证明是指数型的，内点法是多项式的。但通常情况下，单纯形算法比内点法还快。NP里面的N代表Non-Deterministic（意思是非确定性的），P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。NP完全问题，即“

5、NP COMPLETE”，是不确定性图灵机在P时间内能解决的问题，是世界七大数学难题之一，是一类非常特殊的NP问题。NP完全问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。对于这类问题，其求解的计算时间不能随着计算机性能的提高而有效缩短，因此不能指望依靠计算机性能的提高来解决。NP难问题，即“NP-Hard”。4、你能举出几个约束最短路问题吗？多商品流问题在生产实际中是否存在？举一二例说明。确定机组航班环是约束最短路问题。多商品流问题在生产实际中存在，例如：航线网络规划问题。5、Lagrange分解算法、Danzig-Wolfe分解算法、Benders分解算法各有什么特点？请

6、分析它们的优缺点。Lagrange分解算法采用了Lagrangian乘子，解除了模型中的困难约束,将难解问题分解成易解问题。在Lagrangian松弛算法中最关键的是如何更新Lagrangian乘子，一般情况下，Lagrangian松弛算法收敛速度较慢，而且是振荡收敛。最大Lagrangian函数值也不一定等于最小目标函数值，可能会存在所谓的对偶间隙。Danzig-Wolfe分解算法是结合列生成方法，由限制主问题和子问题交替求解的。与列生成算法相比，列生成算法没有区分“难处理”和“易处理”约束条件，也就是认为都是“易处理”的约束条件，而Danzig-Wolfe分解算法则可将“难处理”和“易处理

7、”的约束条件分开处理。Danzig-Wolfe分解算法需要求解一个线性规划问题，还需要求出子问题的各顶点（基本可行解），这在计算上并不划算。但可以与列生成结合使用，构建有用的算法。Benders分解算法利用对偶理论将“易处理”变量和“难处理”变量分离开来，分别形成Benders主问题和子问题来进行迭代求解，其中只含有“易处理”变量的模型是子问题，含有“难处理”变量的模型是Benders主问题。使用Benders分解算法进行网络设计时，主问题一般都存在最优解，而子问题在开始迭代的几步则可能不可行，这引起几个问题：无法给出较好的目标函数上界；对偶问题无界，如何寻找对偶问题可行域的极点和极方向？难处

8、理变量初始值对求解效率影响很大，如何确定它们？练习题3、试推导网络设计问题的Benders分解算法的限制主问题和子问题模型。设网络中各边的流变量为，选择变量为，其中。选择变量是0-1变量，当边(i,j)被选中，yij=1，否则=0。若分别表示边（i,j）的容量、单位流费用和边选择成本，则此该问题的数学模型如下：首先令（取），构造模型：该模型中只含有“易处理”变量，此模型为原问题的子问题。通常该子问题不可行，它的对偶问题是根据对偶定理，对偶问题的最优解的目标函数等于原问题的最优目标函数值（不包括常数项），若对偶问题可行域存在，并且已知它的k个顶点，l个极方向ri,i=1,2,.,l，则我们可以构

9、造与原问题等价的规划模型该问题又可以等价为 该问题只含有实数变量和难处理变量，不含有变量，已实现“难”“易”两种变量的分离，该模型为Berders 主问题。5、试用Benders分解算法求解图2-37的网络设计问题。图中分别表示边（i,j）的容量、单位流费用和边选择成本，要求从源点s运送6个单位流量到汇点t。解：设网络中各边的流变量为，选择变量为。选择变量是0-1变量，当边(i,j)被选中，yij=1，否则=0，。该问题的数学模型如下：首先，令=0，构造子问题该子问题不可行，它的对偶问题是其中对应节点i的流平衡约束条件，对应边(i,j)的容量约束条件。该可行域存在，但无界，因此存在若干顶点和极方向。取极点，极方向，由此构成第一次主问题如下：求得该限制主问题的解，则原问题目标函数的下界为LB=。将主问题的解带入原问题，得该次迭代的子问题，若可行求得其解，且得到原问题目标函数的上界UB。当LB=UB时，解，为原问题的最优解。否则，若还是不可行