第3章线性规划应用及扩展

《第3章线性规划应用及扩展》由会员分享，可在线阅读，更多相关《第3章线性规划应用及扩展（52页珍藏版）》请在金锄头文库上搜索。

1、第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础第第3章线性规划：应用及扩展章线性规划：应用及扩展第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础l网络流问题的网络单纯形法网络流问题的网络单纯形法 生成树与基生成树与基 (原始原始)网络单纯形法网络单纯形法l最小费用流的应用最小费用流的应用 运输问题和指派问题运输问题和指派问题 最大流问题最大流问题 最短路问题最短路问题第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础网络网

2、络(图图)l 节点集节点集(nodes)，设节点的个数为，设节点的个数为 ml 有向弧集有向弧集(directed arcs) 是所有可能弧集是所有可能弧集 的子集的子集 弧是有方向的：弧是有方向的：网络的基本元素：网络的基本元素：第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础网络流网络流 = 网络数据网络数据(运输网络运输网络)假定假定II：弧没有容量限制：弧没有容量限制l , 节点节点 i 的供给量的供给量 l , 沿着弧沿着弧 (i, j) 运输运输 1 单位物品的费用单位物品的费用注注： 表示节点表示节点 i 是需求节是需求节

3、点，需求量是点，需求量是假定假定I：供需平衡问题供需平衡问题第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础最小费用流问题最小费用流问题决策变量：决策变量：目标：目标：约束：约束：l 流平衡流平衡(flow conservation)l 沿着弧沿着弧 (i, j) 运输物资的数量：运输物资的数量：l 非负性：非负性：outflow(k) inflow(k) =supply(k) = -demand(k),第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础矩阵记号矩阵记号l A是是点

4、弧关联矩阵点弧关联矩阵(node-arc incidence matrix)l A是是稀疏稀疏的，且行相关的，且行相关(秩为秩为m-1)注注其中：其中：开发矩阵开发矩阵A的结构！的结构！第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础图的基本概念图的基本概念l弧的头弧的头(head)和尾和尾(tail) l出度出度 vs.入度入度(outdegree(Od) vs. Indegree(Id)l 源源 vs. 宿宿(source vs. sink) l 路路(path)(没有方向没有方向)l 连通连通 vs. 不连通不连通 (connec

5、ted vs. disconnected) 不连通不连通圈圈连通、无圈连通、无圈l 圈圈 vs. 非圈非圈 (cyclic vs. acyclic)第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础树树(trees)与生成树与生成树(spanning trees)树树 连通的非圈网络连通的非圈网络网网 络络子网络子网络重要事实重要事实：m 个节点的树有个节点的树有 m-1 条弧条弧.如果如果 且且 ，称，称 是是 的的子网络子网络生成树生成树 触及到触及到每个节点每个节点的树，是节点集为的树，是节点集为 的子网络的子网络第第 3 章章 线

6、性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础树解树解(tree solution)及其计算及其计算l 树解的计算树解的计算?l 树解树解(tree solution)：给定生成树给定生成树(共有共有 m-1 条弧条弧)首先固定一个根节点，比如首先固定一个根节点，比如 e (任一节点均可作为根节点) 基于树型数据结构的实现：从基于树型数据结构的实现：从 叶子节点开始叶子节点开始, 逆向依次解流平逆向依次解流平衡方程衡方程 线性代数解释线性代数解释 满足流平衡约束且满足满足流平衡约束且满足叶子节点叶子节点:出度与入度之和为出度与入度之和为1的节点的节点第

7、第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础树解与基本解的关系树解与基本解的关系引理引理. 点弧关联矩阵点弧关联矩阵 A 的秩是的秩是 m-1. 在生成树中，选择一个节点，删除与之对应的流平衡在生成树中，选择一个节点，删除与之对应的流平衡约束，并称之为约束，并称之为根节点根节点(root node);定理定理 一个原始一个原始流是基本解当且仅当它是一个树解流是基本解当且仅当它是一个树解.树解树解 基本解基本解记对应的关联矩阵和供给向量分别为记对应的关联矩阵和供给向量分别为 和和定理定理 的的 m-1 阶子方阵是最小费用流问题的某个基本

8、解对阶子方阵是最小费用流问题的某个基本解对应的基应的基当且仅当其当且仅当其列对应的弧恰好是网络的一棵生成树列对应的弧恰好是网络的一棵生成树.树弧树弧 基变量，非树弧基变量，非树弧 非基变量非基变量第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础树解单纯形乘子与既约费用系数树解单纯形乘子与既约费用系数原始数据原始数据迭代数据迭代数据l 从从根节点开始根节点开始，沿着树弧利用，沿着树弧利用向外递归计算，可得到节点处的向外递归计算，可得到节点处的单纯形乘子单纯形乘子(节点旁的数字节点旁的数字)l 利用利用 计算非树弧上的计算非树弧上的既约费用

9、系数既约费用系数沿弧方向单纯形乘子减少沿弧方向单纯形乘子减少cij，逆弧方向单纯形乘子增加，逆弧方向单纯形乘子增加cij.第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础原始网络单纯形法原始网络单纯形法树解的更新树解的更新假设树解是假设树解是原始可行原始可行的，即满足非负条件：的，即满足非负条件：入弧入弧选取规则：选取规则：出弧出弧选取规则：选取规则：l 在圈中，与入弧的方向相反；在圈中，与入弧的方向相反；l 且在所有这样可能的弧中流最小且在所有这样可能的弧中流最小.树解的更新树解的更新(*)：l 与出弧同方向的流值减去出弧上的流；与出

10、弧同方向的流值减去出弧上的流； l 与出弧反方向的流值加上出弧上的流与出弧反方向的流值加上出弧上的流.入弧为入弧为(d, e);出弧为出弧为(d, c).选取弧选取弧 (i, j) 使得既约费用系数使得既约费用系数第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础原始网络单纯形法原始网络单纯形法单纯形乘子的更新单纯形乘子的更新单纯形乘子单纯形乘子的更新规则：的更新规则：l 含根节点的子树含根节点的子树(T0)上的节点的单纯形乘子保持不变上的节点的单纯形乘子保持不变l 如果入弧从含根节点的子树指向含根节点的子树，则不含根节如果入弧从含根节点

11、的子树指向含根节点的子树，则不含根节点的子树点的子树(T1)上的节点的单纯形乘子减少入弧的原有既约费用系上的节点的单纯形乘子减少入弧的原有既约费用系数；否则，这些单纯形乘子均增加入弧的原有既约费用系数数；否则，这些单纯形乘子均增加入弧的原有既约费用系数新的树解去掉入弧，得两棵子树！新的树解去掉入弧，得两棵子树！T1T0入弧从入弧从T1指向指向T0第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础原始网络单纯形法原始网络单纯形法既约费用系数的更新既约费用系数的更新相对费用系数相对费用系数的更新规则：的更新规则：l 在同一子树内的非树弧上的既

12、约费用系数保持不变在同一子树内的非树弧上的既约费用系数保持不变l 与入弧同向桥接两棵子树的非树弧的既约费用系数减去入弧的与入弧同向桥接两棵子树的非树弧的既约费用系数减去入弧的原有既约费用系数；原有既约费用系数；l与入弧反向桥接两棵子树的非树弧的既约费用系数增加入弧的与入弧反向桥接两棵子树的非树弧的既约费用系数增加入弧的原有既约费用系数原有既约费用系数新的树解去掉入弧，得两棵子树！新的树解去掉入弧，得两棵子树！T1T0与入弧同向桥接与入弧同向桥接T1和和T0与入弧反向桥接与入弧反向桥接T1和和T0最优树解！最优树解！第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUA

13、A数学规划基础数学规划基础(用于无容量限制网络的用于无容量限制网络的)网络单纯形法：网络单纯形法：Step 1. 从一个可行的树解开始，从一个可行的树解开始，假设第假设第 m 个节点是根节点个节点是根节点.Step 4. 确定出弧确定出弧：入弧和出弧必形成一个圈：入弧和出弧必形成一个圈. 如果圈中的所如果圈中的所 有弧和入弧同向，则最优费用是有弧和入弧同向，则最优费用是 -，终止算法，终止算法. 否否 则，在与入弧反向的树弧中选一个最小的流作为则，在与入弧反向的树弧中选一个最小的流作为出弧出弧. Step 5. 转轴转轴： 在当前树解中用入弧代替出弧，更新树解，得在当前树解中用入弧代替出弧，更

14、新树解，得 新的树解新的树解. 转转 Step2.Step 2. 计算计算单纯形乘子单纯形乘子. 从根节点向叶子节点，依次求解方程从根节点向叶子节点，依次求解方程 (i, j) 使得使得 ，称之为，称之为入弧入弧.如果他们全非负，当前树解是最优的；否则，选取弧如果他们全非负，当前树解是最优的；否则，选取弧Step 3. 计算计算既约费用系数既约费用系数/相对费用系数：相对费用系数：第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础l 法法1 改变改变原始问题的原始问题的费用向量费用向量使得所给树解是对偶可行的；使得所给树解是对偶可行的；

15、利用利用对偶对偶网络单纯形法求解新问题，得到最优解；网络单纯形法求解新问题，得到最优解； 新问题的最优解是原始问题的新问题的最优解是原始问题的可行可行树解；树解； 从此树解出发，利用从此树解出发，利用原始原始网络单纯形法求解所给问题网络单纯形法求解所给问题.l 法法2 改变改变原始问题的原始问题的供给向量供给向量使得所给树解是原始可行的；使得所给树解是原始可行的； 利用利用原始原始网络单纯形法求解新问题，得到最优解；网络单纯形法求解新问题，得到最优解； 新问题的最优解是原始问题的新问题的最优解是原始问题的对偶可行对偶可行树解；树解； 从此树解出发，利用从此树解出发，利用对偶对偶网络单纯形法求解

16、所给问题网络单纯形法求解所给问题.求解一般的最小费用流问题求解一般的最小费用流问题第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础整性定理整性定理(integrality theorem)整性定理整性定理. 考虑无容量限制的网络流问题，考虑无容量限制的网络流问题， (i) 如果如果供给量供给量 bi 是整数，则每个是整数，则每个基本可行解基本可行解的分量是整数的分量是整数.(ii) 如果如果费用系数费用系数 cij 是整数，则每个是整数，则每个单纯形乘子单纯形乘子是整数是整数.整数线性规划整数线性规划通常不易求解；通常不易求解；但是具有

17、整性数据的最小费用流问题可用网络单纯形法求解！但是具有整性数据的最小费用流问题可用网络单纯形法求解！第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础最小费用流问题的特例和扩展最最小小费费用用流流问问题题狭义狭义模型模型广义模型广义模型运输运输问题问题指派指派问题问题最大流问题最大流问题最短路问题最短路问题带增益的最小费用流问题带增益的最小费用流问题非线性最小费用流问题非线性最小费用流问题多商品流问题多商品流问题第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础运输问题运输问题(tr

18、ansportation problem)每个节点是两种类型之一每个节点是两种类型之一l 源源(供给供给)节点节点l 宿宿(需求需求)节点节点每条弧满足：每条弧满足：l尾是源节点尾是源节点l头是宿节点头是宿节点 二部二部/分图分图(bipartite)第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础 需求量需求量供给量供给量1027157 56*1184318*9*16*36运输问题的表上作业法运输问题的表上作业法7 个节点个节点 8 条弧！条弧！ 6 个基变量个基变量(树弧树弧)， 2 个非基变量个非基变量(非树弧非树弧)第第 3 章

19、章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础运输问题的表上作业法运输问题的表上作业法数据表数据表运输表运输表 需求量需求量供给量供给量1027157 56*1184318*9*16*36 -5-1-40 75*338-48*18*2*115单纯形乘子单纯形乘子第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础指派问题指派问题(assignment problem)l 给定给定 n 个人和个人和 n 项任务，第项任务，第 i 个人完成任务个人完成任务 j 的费用是的费用是 cijl 指派每个

20、人去做且只做一项任务指派每个人去做且只做一项任务l 每项任务只由一个人去完成每项任务只由一个人去完成忽略忽略整数要求，得特殊的整数要求，得特殊的运输问题运输问题。由。由整性定理整性定理，利用网络，利用网络单纯形法可得到指派问题的解！单纯形法可得到指派问题的解！严重退化！严重退化！有有 2n 个约束，一个是冗余的，但基本可行解个约束，一个是冗余的，但基本可行解只有只有 n 个非零元素！个非零元素！相对于相对于二次指派二次指派问题问题(习题习题3.7)，称该问题为，称该问题为线性指派线性指派问题！问题！线性指派问题：p.2 例1.1.2；p.49，2.26第第 3 章章 线性规划：应用及线性规划：

21、应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础最大流问题最大流问题(maximum flow problem)问题：问题：求从求从 s 到到 t 的最大流量的最大流量(将尽可能多的流从将尽可能多的流从 s 推向推向 t)l 网络网络 ，设，设 A 是点弧关联矩阵是点弧关联矩阵 l 弧的弧的容量容量l 源源 和宿和宿 （s = 1, t = 4）给定：给定：l Ford-Fulkerson算法算法l 最大流最小割定理最大流最小割定理() l 置其它弧的费用置其它弧的费用cij =0；置每个节点的需求量；置每个节点的需求量 bi= 0l 添加人工弧添加人工弧 (t, s)，令，令

22、 反问题：设反问题：设 s 为为唯一唯一的供给节点，的供给节点，t 为为唯一唯一的需求节点，其的需求节点，其余为中转节点，求节点余为中转节点，求节点 s 的最大可供给量？的最大可供给量？第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础割及割的容量割及割的容量l s-t 割割(cut)：l 割集割集(cut set)：最大流最小割定理最大流最小割定理(Max-Flow Min-Cut Theorem)在任一网络中，最大流的流量等于最小割的容量在任一网络中，最大流的流量等于最小割的容量. 由由Ford与与Fulkerson于于1956年提出

23、来的，是图论和网年提出来的，是图论和网络流中的最重要结论之一络流中的最重要结论之一!有向图中去掉割集，则不存在从有向图中去掉割集，则不存在从 s 到到 t 的的有向路；有向路；无向无向图中去掉割集，则不存在从图中去掉割集，则不存在从 s 到到 t 的的路路(即即s 与与 t 不连通不连通)前向前向弧集合弧集合前向弧的容量之和，即前向弧的容量之和，即l 割的割的容量容量(capacity)：第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础最大流最小割定理的证明最大流最小割定理的证明流平衡方程：流平衡方程：设设是最大流问题的解是最大流问题的

24、解设设是对偶问题的解是对偶问题的解令令易验证易验证 是一个是一个s t 割，且割，且第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础最短路问题最短路问题(shortest path problem)给定：给定：l 网络：网络：l 费用费用/权重权重/距离：距离：l 根节点根节点(home or root)：问题：确定从问题：确定从 每一个节点出发到根节点的每一个节点出发到根节点的最短路最短路(有向的有向的)根节点根节点 5：l 13 5：5l 25： 5l 35： 1l 43 5：3 1 4 2 3 5 7 4 5 1 2 5 1 4

25、第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础最短路的网络流问题表述最短路的网络流问题表述l 令令l 求解最小费用网络流问题求解最小费用网络流问题l 由最优树弧得到从由最优树弧得到从 i 到到 r 的最短路的最短路l 最短路的长度为最短路的长度为 1 4 2 3 5 7 4 5 1 2 5 1 4 第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础动态规划动态规划(dynamic programming)l Bellman方程、动态规划原理方程、动态规划原理/最优性原理最优性原理

26、l 令令 vi = 从节点从节点 i 到根节点到根节点 r 的最短时间的最短时间 在网络文献中称为在网络文献中称为标号标号(label); 在动态规划的文献中称为在动态规划的文献中称为值值(value).以下算法中使用的记号：以下算法中使用的记号：最优化原理最优化原理(最优子结构性质最优子结构性质)：一个最优化策略具有这样的性：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最而言，余下的诸决策必须构成最优策略。简而言之，一个最优策略的子策略总是最优的。优策略的子

27、策略总是最优的。第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础标号设置算法标号设置算法(label setting algorithm)Dijkstra算法，算法，1959年，适用于年，适用于弧的费用非负弧的费用非负的问题的问题记号：记号：Dijkstra算法：算法：当还有未完成的节点时，选择当还有未完成的节点时，选择 vi 最小的节点最小的节点, 记为记为 j. 将将 j 添加到已完成节点集添加到已完成节点集 对每个未完成的节点对每个未完成的节点 i ，且有弧，且有弧(i, j)将将 i 和和 j 连接起来：连接起来：l 是已完成的

28、节点集是已完成的节点集(已经确定了标号的节点集已经确定了标号的节点集)l 是是 在在 i 之后要访问的节点之后要访问的节点l 初始化：初始化：l 迭代：迭代：如果如果 置置原理原理：每次新扩展一个标号最小的节点，并更新与其相邻每次新扩展一个标号最小的节点，并更新与其相邻的点的距离。的点的距离。第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础Dijkstra 算法算法根节点根节点 5：l 13 5：5l 25： 5l 35： 1l 43 5：3 1 4 2 3 5 7 4 5 1 2 5 1 4 第第 3 章章 线性规划：应用及线性规划：

29、应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础动态规划动态规划(dynamic programming)是是运筹学运筹学的一个分支，是求解最优决策过程的一个分支，是求解最优决策过程(decision process) 的数学方法。的数学方法。20世纪世纪50年代初年代初美国美国数学家数学家R.E.Bellman等人在研究多阶段等人在研究多阶段决策过程决策过程(multistep decision process)的优化问题时，提出的优化问题时，提出了著名的了著名的最优性原理最优性原理(principle of optimality)，把多阶段过，把多阶段过程程转化为转化为一系

30、列单阶段问题，利用各阶段之间的关系，逐一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法个求解，创立了解决这类过程优化问题的新方法动态动态规划。规划。 1957年出版了他的名著年出版了他的名著Dynamic Programming，这是该领，这是该领域的第一本著作。域的第一本著作。 第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础最优控制最优控制(optimal control )是是现代控制理论现代控制理论的的核心核心，它研究的，它研究的主要问题主要问题是：在满足一是：在满足一定约束条件下，寻求最优控

31、制策略，使得性能指标取极大定约束条件下，寻求最优控制策略，使得性能指标取极大值或极小值值或极小值 。方法描述方法描述：对一个受控的动力学系统或运动过程，从一类：对一个受控的动力学系统或运动过程，从一类允许的控制方案中找出一个最优的控制方案，使系统的运允许的控制方案中找出一个最优的控制方案，使系统的运动在由某个初始状态转移到指定的目标状态的同时，其性动在由某个初始状态转移到指定的目标状态的同时，其性能指标值为最优能指标值为最优 。典型例子典型例子确定一个最优控制方式使空间飞行器由一个轨道转换到确定一个最优控制方式使空间飞行器由一个轨道转换到另一轨道过程中燃料消耗最少。另一轨道过程中燃料消耗最少。

32、选择一个温度的调节规律和相应的原料配比使化工反应选择一个温度的调节规律和相应的原料配比使化工反应过程的产量最大。过程的产量最大。制定一项最合理的人口政策使人口发展过程中老化指数、制定一项最合理的人口政策使人口发展过程中老化指数、抚养指数和劳动力指数等为最优。抚养指数和劳动力指数等为最优。 第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础最优控制最优控制(续续)是是 20 世纪世纪 50 年代中期在年代中期在空间技术的推动空间技术的推动下开始形成和下开始形成和发展起来的发展起来的 。开创性开创性工作是美国学者贝尔曼工作是美国学者贝尔曼19

33、57年提出的年提出的动态规划动态规划和和前苏联学者庞特里亚金前苏联学者庞特里亚金1958年提出的年提出的极大值原理极大值原理。先期工作先期工作应该追溯到维纳（应该追溯到维纳（N.Wiener）等人奠基的控制）等人奠基的控制论（论（Cybernetics）。）。1948年维纳发表了题为年维纳发表了题为控制论控制论关关于动物和机器中控制与通讯的科学于动物和机器中控制与通讯的科学的论文，第一次科的论文，第一次科学的提出了信息、反馈和控制的概念，为最优控制理论学的提出了信息、反馈和控制的概念，为最优控制理论的诞生和发展奠定了基础。的诞生和发展奠定了基础。 线性系统在二次型性能指标下线性系统在二次型性能

34、指标下(LQ)的最优控制问题的最优控制问题则是卡则是卡尔曼在尔曼在60年代初提出和解决的年代初提出和解决的. 第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础l 整数线性规划整数线性规划 典型问题典型问题()实用建模技术实用建模技术()对偶理论对偶理论l 求解整数线性规划的典型方法求解整数线性规划的典型方法 Gomory 割平面法割平面法 分枝定界法分枝定界法()第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础集合覆盖问题集合覆盖问题(set-covering problem)考

35、虑移动通信公司，考虑移动通信公司，已知已知l 有有 m 个小区个小区(cell)； i = 1, , ml 有有 n 个备选地建基站个备选地建基站(base station)； j = 1, , n ， 建站成本建站成本 cjl 基站和小区的关系：基站和小区的关系：问题问题：建哪些基站，能使所有小区被覆盖，且总成本最小：建哪些基站，能使所有小区被覆盖，且总成本最小?合理地建立基站使每个小区至少在某个基站的服务覆盖范围内！合理地建立基站使每个小区至少在某个基站的服务覆盖范围内！决策变量决策变量集合覆盖集合覆盖问题问题第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUA

36、A数学规划基础数学规划基础集合分割问题集合分割问题(set-partitioning problem )航空公司，航空公司，已知已知l 有有m 个航段个航段(leg)；航段；航段 i = 1, 2, , m l 有有n个可能的航线个可能的航线(route)；航线；航线 j = 1, 2, , n ，费用费用cjl 航段和航班的关系：航段和航班的关系：问题问题：开通那些航线以涵盖这些既定航段，使得每个航段：开通那些航线以涵盖这些既定航段，使得每个航段 仅归属于一个仅归属于一个航线，且总成本最低。航线，且总成本最低。把航段合理的不重不漏地安排到不同的航线上！把航段合理的不重不漏地安排到不同的航线上

37、！决策变量决策变量集合分割集合分割问题问题第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础 旅行商问题旅行商问题(traveling salesman problem, TSP)l旅行商从城市旅行商从城市 1 出发，周游城出发，周游城 市市 2, ，n；l每个城市只经过一次，最后回每个城市只经过一次，最后回 到城市到城市1； l城市两两之间的距离为城市两两之间的距离为cij问题：安排周游使总路程最短问题：安排周游使总路程最短.可能的周游数目：可能的周游数目： (n-1)!周游周游 = 所有城市的排列所有城市的排列第第 3 章章 线性规划

38、：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础 顶点约束顶点约束原有问题的原有问题的松弛松弛该问题的解可能含子圈，也称该问题的解可能含子圈，也称子周游子周游.想办法排除子圈！想办法排除子圈！为每个城市对为每个城市对 (i, j) 引入决策变量引入决策变量 xij 决定哪些弧决定哪些弧在周游上！在周游上！指派约束！指派约束！圈的特征圈的特征：节点的数目等于弧的数目：节点的数目等于弧的数目第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础 子周游表述子周游表述(subtour formulation)添加一

39、族子周游添加一族子周游(消去消去)约束约束一开始不必把所有的子周游消去约束都放进去；一开始不必把所有的子周游消去约束都放进去；可以可以边算边放边算边放！有指数多个约束！有指数多个约束！第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础 MTZ(Miller-Tucker-Zemlin)表述表述引入新变量引入新变量规模小！可处理有偏好的周游！规模小！可处理有偏好的周游！ti 表示进入城市表示进入城市 i 之前经过的城市数目之前经过的城市数目，第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规

40、划基础 实用建模技术实用建模技术或约束或约束引入引入0-1变量变量 y其中其中 M 是是充分大的正数充分大的正数带固定成本的目标函数带固定成本的目标函数进一步假设进一步假设+第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础二次目标二次目标函数的线性化函数的线性化l l 其中其中 yij 满足满足其中其中 zij 满足满足不需要新引入的变量是整数！第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础整数线性规划的整数线性规划的线性规划松弛线性规划松弛(LP-relaxation)割平面

41、割平面称称忽略掉整性约束忽略掉整性约束后所得问题是后所得问题是整数线性规划的整数线性规划的线性规划松弛线性规划松弛。第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础分枝与定界分枝与定界当前最好当前最好(best-so-far)解、最好值解、最好值枚举树枚举树(enumeration tree)线性规划松弛：线性规划松弛：x= (1.25, 0)T, L = 1.25宽度优化法宽度优化法(breadth-first-search)l 优先求解树的优先求解树的同一层同一层的子问题的子问题 剪枝剪枝(pruning)分枝分枝(branchin

42、g)定界定界(bounding)：父节点松弛问题的最优值父节点松弛问题的最优值第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础分枝与定界分枝与定界深度优先法深度优先法(depth-first search)l 优先考虑优先考虑底层底层问题问题l 然后逐层向上回溯然后逐层向上回溯l 回溯过程中仍然保持底层优先回溯过程中仍然保持底层优先第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础深度优先法深度优先法(深探法深探法)与线性整数规划与线性整数规划探测到整数解的好处：探测到整数解的好处

43、：l 一个可行解对应一种一个可行解对应一种可行设计可行设计或者或者可行决策可行决策！l 找到可行解就找到可行解就有可能更新当前最好解有可能更新当前最好解，这可以帮助剪枝，这可以帮助剪枝深探法的深探法的优势优势：l 整数解通常位于枚举树的底层整数解通常位于枚举树的底层l 深探法的程序编写较容易深探法的程序编写较容易l 可应用可应用对偶单纯形法对偶单纯形法求解下一层的子问题求解下一层的子问题第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础应用对偶单纯形法求解子问题应用对偶单纯形法求解子问题P1=P0+ “x1 1”P2=P0+ “x1 2”

44、用单纯形法求解用单纯形法求解P0，之后用，之后用对偶对偶单纯形法求解单纯形法求解 P1和和P2第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础分枝定界法的原理分枝定界法的原理节点对应着一个连续优化问题，其中根节点对应的是节点对应着一个连续优化问题，其中根节点对应的是松弛问题松弛问题P0 节点分三类：根节点、父节点和叶子节点；其中叶子节点分三类：根节点、父节点和叶子节点；其中叶子节点分为：无可行解、下界大于等于当前最好值、解节点分为：无可行解、下界大于等于当前最好值、解是整数是整数节点与节点之间由分枝连接起来节点与节点之间由分枝连接起来分

45、枝定界法中枚举树的结构分枝定界法中枚举树的结构分枝定界法的动机分枝定界法的动机：通过探测枚举树来寻找解是整数通过探测枚举树来寻找解是整数的叶子节点，从而找到目标值最小的一个。的叶子节点，从而找到目标值最小的一个。 在一个父节点，连续优化问题的解可能有多个分量在一个父节点，连续优化问题的解可能有多个分量违反整性约束。因此有多种方式来选取分枝变量。从而违反整性约束。因此有多种方式来选取分枝变量。从而枚举树不是惟一确定的。枚举树不是惟一确定的。第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础分枝定界法的原理分枝定界法的原理(续续)下一次应该求

46、解哪个节点对应的问题下一次应该求解哪个节点对应的问题应该对哪个变量进行分支应该对哪个变量进行分支为当前节点对应的子问题确定一个下界为当前节点对应的子问题确定一个下界2 从已经探测到的整性叶子节点中，找到从已经探测到的整性叶子节点中，找到 目前最好的整数可行解目前最好的整数可行解 及目标值及目标值 ；部分搜索策略中需要确定部分搜索策略中需要确定1 保持一个未解决问题栈，且每个问题有一个最优值的下界；保持一个未解决问题栈，且每个问题有一个最优值的下界；栈栈(stack)方法：方法：第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础Initia

47、lly , the continuous problem is put in the stack with , andBranch and Bound Method for Integer Programming ProblemThe algorithm proceeds as following:(i) If no problem is in the stack, finish with as x* and f *; Otherwise take the top problem from the stack.(iii) Try to solve the problem: if no feas

48、ible point exists reject the problem and go to (i).(iv) Let the solution be x with f : if reject the problem and go to (i).(v) If x is integer feasible then set and go to (i).(vi)Select an integer variable i such that , create two new problems by branching on xi , place these on the stack with lower

49、 bound (or a tighter lower bound derived from f ) , and go to (i).(ii) If reject the problem and go to (i).由下界来剪枝！由下界来剪枝！第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础推荐的数学书：推荐的数学书：1.什么是数学对思想和方法的基本研究，R柯朗 H罗宾 著 I斯图尔特 修订 左平 张饴慈 译，上海：复旦大学出版社，2011.2.微积分的历程，W. Dunham著，李伯民等译，北京：人民邮电出版社，2010.3.A Fir

50、st Course in Probability, Sheldon M. Ross, 英文版第8版，人民邮电出版社.4.Introduction to Linear Algebra, Gilbert Strang, 第四版，Wellesley- Cambridge Press, Wellesley, USA, 2009.一个有用的网站一个有用的网站：http:/ocw.mit.edu/courses/mathematics/18-01sc-single-variable-calculus-fall-2010/syllabus/第第 3 章章 线性规划：应用及线性规划：应用及扩展扩展LHY-SMSS-BUAA数学规划基础数学规划基础推荐的人文书：做人做事1 傅雷家书(傅敏编，江苏文艺出版社) 结合儿子傅聪在国内和国外学习钢琴，以父亲和过来人的角色讲了年轻人可能碰到的问题及一些很好的建议！2 梁启超家书 主要是梁启超教导自己的孩子如何做人处事，也表现了梁启超本人对生活的极度热爱和治学精神等。推荐的世界名著和中国名著：约翰克里斯朵夫和名人传(法,罗曼罗兰著，傅雷译)，童年、红楼梦、边城等。