运筹学教程课件-第3章-整数规划.pptx

1、第第3章章 整数规划整数规划主要介绍三种方法：主要介绍三种方法：1 1、分支定界法、分支定界法（branch and bound method）2 2、割平面法、割平面法（cutting plane approach）3 3、匈牙利法、匈牙利法第第3章章 整数规划整数规划3.1 整数规划模型介绍整数规划模型介绍3.2 分支定界法分支定界法3.3 割平面法割平面法3.4 匈牙利算法匈牙利算法33.1 整数规划模型介绍整数规划模型介绍 整数规划的一般形式整数规划的一般形式（IP）问题）问题 Max（min）z=cjxj aijxj（或（或=，）bi i=1，2，m xj 0 j=1，2，n xj

2、Zs.t.（LIP）松弛问题）松弛问题 Max（min）z=cjxj aijxj（或（或=，）bi i=1，2，m xj 0 j=1，2，ns.t.43.1 整数规划模型介绍整数规划模型介绍（IP）问题与（）问题与（LIP）问题关系）问题关系（Min）1.(IP)问题的值问题的值(LIP)问题的最优值问题的最优值。2.(LIP)问题最优解若是整数，则一定是问题最优解若是整数，则一定是(IP)问题的最优解。问题的最优解。53.1 整数规划模型介绍整数规划模型介绍整数规划分类整数规划分类1.纯整数线性规划：决策变量都取整数值。纯整数线性规划：决策变量都取整数值。2.混合整数线性规划：决策变量中混合

3、整数线性规划：决策变量中一部分一部分取整数值，取整数值，另一部分可以不取整数值。另一部分可以不取整数值。3.0-1整数线性规划：决策变量只能取值整数线性规划：决策变量只能取值 0 或或 1。63.1 整数规划模型介绍整数规划模型介绍整数规划引例整数规划引例n背包问题背包问题n厂址选择问题厂址选择问题 n组合投资问题组合投资问题（见教材（见教材107-108页）页）Return7 3.2 分支定界法分支定界法 分支定界法是一种隐枚举方法或部分枚举方法，分支定界法是一种隐枚举方法或部分枚举方法，是枚举方法基础上的改进，是组合优化重要方法。其是枚举方法基础上的改进，是组合优化重要方法。其关键是分支和

4、定界。关键是分支和定界。例例1 Min Z=-2X1-3X2 5X1+7X2 35 4X1+9X2 36 X1，X2 0 X1，X2 Z8n解：解：先求相应线性规划的最优解，为：先求相应线性规划的最优解，为：n取取 分割可行域，得到子问题分割可行域，得到子问题Sub-1,Sub-2：n 3.2 分支定界法分支定界法1212168=3,=2,=-14171717xxzSub-2 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x2 3 x1 x2 0Sub-1 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x1 x2 0216=217x9 3

5、.2 分支定界法分支定界法Sub-1的最优解为：的最优解为：取取 分割可行域，得到两个子问题分割可行域，得到两个子问题Sub-3,Sub-4：12124,2,1455xxz 11=45xSub-3 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x1 4 x1 x2 0Sub-4 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x2 2 x1 5 x1 x2 010 3.2 分支定界法分支定界法Sub-3的最优解为：的最优解为：获得整数解，取得上界获得整数解，取得上界 ，停止分枝！，停止分枝！124,2,14xxz 14z 11 3.2 分支

6、定界法分支定界法Sub-4的最优解为：的最优解为：12325,1,1477xxz 13=17xSub-6 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x1 5 x2 2 x1 x2 0Sub-5 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x1 5 x21 x1 x2 0取取 分割可行域，得到两个子问题：分割可行域，得到两个子问题：Sub-5,Sub-612 3.2 分支定界法分支定界法Sub-5的最优解为：的最优解为：取取 分割可行域，得到两个子问题：分割可行域，得到两个子问题：Sub-7,Sub-812315,1,1455

7、xxz 13=55xSub-7 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x2 2 x1 5 x2 1 x1 5 x1 x2 0Sub-8 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x2 2 x1 5 x2 1 x1 6 x1 x2 013 3.2 分支定界法分支定界法Sub-6的可行域是空集，停止分枝。的可行域是空集，停止分枝。Sub-7的最优解为：的最优解为：获得整数解，停止分枝！获得整数解，停止分枝！由于由于上界仍保持为上界仍保持为125,1,13xxz 1341zz 14z 14 3.2 分支定界法分支定界法Sub-8的最优解为：

8、的最优解为：取取 分割可行域，得到两个子问题：分割可行域，得到两个子问题：Sub-9,Sub-1012536,1477xxz 15=7xSub-10 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x15 x21 x16 x21 x1 x2 0Sub-9 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x15 x21 x16 x20 x2 015 3.2 分支定界法分支定界法Sub-9的最优解为：的最优解为：获得整数解，停止分枝！获得整数解，停止分枝！由于由于上界仍保持为上界仍保持为127,0,14xxz 14=14zz 14z 16

9、 3.2 分支定界法分支定界法Sub-10的可行域是空集，停止分枝的可行域是空集，停止分枝!17 3.2 分支定界法分支定界法Sub-2的最优解为：的最优解为：，停止分支！，停止分支！12112,3,1342xxz 1=-13142zz 18 3.2 分支定界法分支定界法至此已将所有可能分解的子问题都已分解到底，最后得至此已将所有可能分解的子问题都已分解到底，最后得到到两个目标函数值相等的最优整数解：两个目标函数值相等的最优整数解：（x1，x2）=（4，0）和（）和（x1，x2）=(0，7)他们的目标函数值都是他们的目标函数值都是-14。Return原问题原问题Sub-1Sub-2Sub-3S

10、ub-4Sub-5Sub-6Sub-7Sub-8Sub-9Sub-10剪枝剪枝(4,2)，-14(5,1)，-13无可行解无可行解(7,0)，-14无可行解无可行解193.3 割平面法割平面法割平面法思想割平面法思想 求解求解(IP)的松驰问题的松驰问题(LIP)：若最优解：若最优解 X*Z，则从，则从 X*的非整分的非整分量中选取一个构造线性约束（量中选取一个构造线性约束（Gomory 割平面），将其加入原割平面），将其加入原(LIP)问题，形成一个新的线性规划并求解，问题，形成一个新的线性规划并求解，（重复），直至得重复），直至得到整数最优解。到整数最优解。关键：关键：新增的线性约束将切割

11、掉部分非整数解，至少切割新增的线性约束将切割掉部分非整数解，至少切割掉当前松驰问题的非整数最优解，掉当前松驰问题的非整数最优解，而不会切割掉问题的任何整数解而不会切割掉问题的任何整数解!203.3 割平面法割平面法 构造割平面的步骤：构造割平面的步骤：1、令令 xi 是是(LIP)问题最优解中非整数值的一个基变量，得：问题最优解中非整数值的一个基变量，得：xi+aik xk=bi（1）其中，其中，k B（B：非基变量下标集）：非基变量下标集）213.3 割平面法割平面法构造割平面的步骤：构造割平面的步骤：2、将、将 bi 和和 aik 分解成整数部分分解成整数部分 I（不超过（不超过 b 的最

12、大整数）与非的最大整数）与非负真分数部分负真分数部分 F 之和：之和：bi=Ii+Fi，其中，其中 0 Fi 1.(2)aik=Iik+Fik，其中，其中 0 Fik 1223.3 割平面法割平面法 构造割平面的步骤：构造割平面的步骤：3、将（将（2）代入（）代入（1）：）：xi+Iik xk-Ii=Fi-Fik xk（3）4、割平面方程：、割平面方程：Fi-Fik xk 0（4）！将（！将（4）加入原来）加入原来(LIP)问题继续求解。问题继续求解。23 3.3 割平面法割平面法例例2 用割平面法求解下列整数规划。用割平面法求解下列整数规划。IP Min Z=3X1+4X2 3X1+X2 4

13、 X1+2X2 4 X1，X2 0 X1，X2 Z LIP Min Z=3X1+4X2 3X1+X2 4 X1+2X2 4 X1，X2 0 24 3.3 割平面法割平面法解解:（1）先求解线性规划问题（先求解线性规划问题（LIP），得到最优单纯形表：），得到最优单纯形表：Cj3400I 表表CBXBB 1 bX1X2X3X40X3431-100X44120-1 j03400B 表表1X14/510-2/51/51X28/5011/5-3/5 j44/500-2/5-9/525 3.3 割平面法割平面法(2)(2)选择一个非整数的基变量，例如选择一个非整数的基变量，例如x2=8/5，构造割平面。

14、，构造割平面。增加松弛变量增加松弛变量x5后将这个约束加到线性规划的最优单纯形表，得到后将这个约束加到线性规划的最优单纯形表，得到b2=8/5=1+3/5，I2=1，F2=3/5a23=1/5=0+1/5，I23=0，F23=1/5a24=-3/5=-1+2/5，I24=-1，F24=2/510nrrjjj mFF x约条附的束件加为343/51/52/50 xx（）26 3.3 割平面法割平面法(3)求解新的松弛问题求解新的松弛问题Cj110001 表表CBXBB 1 bX1X2X3X4X51X14/510-2/51/501X28/5011/5-3/500X5-3/500-1/5-11 j4

15、4/500-2/5-9/502 表表1X121001-21X21010-110X330012-5 j10000-1-227 3.3 割平面法割平面法整数规划整数规划最优解最优解线性规划线性规划 最优解最优解切割约束切割约束最优解：最优解：x1=2,x2=1Return283.4 匈牙利算法匈牙利算法0-1 变量变量 只取只取0或或1，常被用来表示系统是否处于某个特定的状态，或者，常被用来表示系统是否处于某个特定的状态，或者是否取某个特定的决策方案。如是否取某个特定的决策方案。如xj=1 当方案当方案 S j被选中被选中0 否则否则293.4 匈牙利算法匈牙利算法0-1整数规划整数规划例例3 选

16、址问题选址问题 WAL-MART拟在常州的天宁、钟楼、新区建立分店，有拟在常州的天宁、钟楼、新区建立分店，有 7 个位个位置（地点）置（地点）Ai（i=1，2，7）供选择。总部规定）供选择。总部规定 在天宁，由在天宁，由 A1，A2，A3 三个点中至多选两个；三个点中至多选两个；在钟楼，由在钟楼，由 A4，A5 两个点中至少选一个；两个点中至少选一个；在新区，由在新区，由 A6，A7 两个点中至少选一个。两个点中至少选一个。如果选如果选 Ai 点，设备投资为点，设备投资为 ai 元，每年可获利润为元，每年可获利润为 ci 元，但投元，但投资总额不能超过资总额不能超过A元。问公司选择哪几个点可使

17、年总利润最大？元。问公司选择哪几个点可使年总利润最大？303.4 匈牙利算法匈牙利算法解：解：建立模型建立模型 引入引入 0-1 变量变量 1 当当 Ai 点被选用点被选用 0 否则否则xi=（i=1，2，7）max z=cixi aixi A x1+x2+x3 2 x4+x5 1 x6+x7 1 xi 0，1313.4 匈牙利算法匈牙利算法例例4 指派问题指派问题（assignment problem）有有 n 个人和个人和 n 件事，已知第件事，已知第 i 人做第人做第 j 事的费用为事的费用为 cij（i，j=1，2，n），要求确定人和事之间的一一对应的指派方案，使完成），要求确定人和事

18、之间的一一对应的指派方案，使完成这件事的总费用最少。如这件事的总费用最少。如任务任务人员人员ABCD甲甲乙乙丙丙丁丁3129714414813171611415139323.4 匈牙利算法匈牙利算法解解：建立模型：建立模型 令令 1 当指派第当指派第 i 人完成第人完成第 j 项任务项任务 0 否则否则xij=min z=cijxij xij=1，j=1，2，n xij=1，i=1，2，n xij 0，1333.4 匈牙利算法匈牙利算法匈牙利算法匈牙利算法 1955年，库恩（年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格）利用匈牙利数学家康尼格（D.Knig）的关于矩阵中独立零元素的定理，

19、提出了求解指）的关于矩阵中独立零元素的定理，提出了求解指派问题算法派问题算法匈牙利算法。匈牙利算法。343.4 匈牙利算法匈牙利算法 【性性 质质】若从指派问题的系数矩阵若从指派问题的系数矩阵 C=（cij ）nn 的某行（或某列）的某行（或某列）各元素分别各元素分别减去一个常数减去一个常数 k，得到一个新的系数矩阵，得到一个新的系数矩阵C=（cij ）则以则以 C 和和 C 为系数矩阵的两个指派问题有为系数矩阵的两个指派问题有相同的最优解相同的最优解。353.4 匈牙利算法匈牙利算法算法步骤算法步骤（1）变换系数矩阵变换系数矩阵C，使每行及每列至少有一个零元素，同时不出，使每行及每列至少有一

20、个零元素，同时不出现负元素。现负元素。（2）确定独立零元素组。若确定独立零元素组。若|独立零元素组独立零元素组|=n，结束；否则，转步，结束；否则，转步骤（骤（3）。）。（3）继续变换系数矩阵，然后返回步骤（继续变换系数矩阵，然后返回步骤（2）。）。363.4 匈牙利算法匈牙利算法例例5 求解下列指派问题（教材求解下列指派问题（教材121页）。页）。2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 22497min（cij ）=373.4 匈牙利算法匈牙利算法例例5（续）（续）0 13 11 2

21、 6 0 10 11 0 4 7 4 0 1 4 2 0 0 4 2min 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0=（cij ）383.4 匈牙利算法匈牙利算法例例5（续）（续）0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0此时圈此时圈 0 元素的个数元素的个数 m=n=4.393.4 匈牙利算法匈牙利算法例例5（续）0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0（xij ）=最优分配：最优分配：403.4 匈牙利算法匈牙利算法例例6 求下列指派问题（教材求下列指派问题（教材122页）。页）。任务任务人员人员ABCDE甲甲乙乙丙丙丁丁

22、戊戊1287154791714109612677614610969109413.4 匈牙利算法匈牙利算法例例6（续）（续）解：解：12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 976764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5423.4 匈牙利算法匈牙利算法例例6（续）（续）5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 此时圈此时圈 0 元素（元素（独立零元独立零元素）素）的个数的个数 m=4n=5，不，不能

23、确定最优能确定最优指派方案！指派方案！需要继续变换系数矩阵，以需要继续变换系数矩阵，以增加独立零元素个数增加独立零元素个数。方法如下：。方法如下：433.4 匈牙利算法匈牙利算法例例6（续）（续）1)对未加圈对未加圈0的行打的行打号；号；2)对所有打对所有打号行的所有含号行的所有含0的列打的列打号；号；3)对已打对已打号的列中含号的列中含0的行打的行打号；号；4)重复重复2)和和3)，直到无可以打，直到无可以打号行或列为止；号行或列为止；5)对未打对未打号的行画一横线，对打号的行画一横线，对打号的列画号的列画一竖线，即得能覆盖所有一竖线，即得能覆盖所有0的最少直线数的最少直线数目的直线集合。目

24、的直线集合。443.4 匈牙利算法匈牙利算法例例6（续）（续）5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5453.4 匈牙利算法匈牙利算法例例6（续）（续）继续变换系数矩阵：继续变换系数矩阵：在未被直线覆盖的元素中找出一个最小元素在未被直线覆盖的元素中找出一个最小元素 在打在打号号行行各元素都各元素都减减去这一最小元素，在去这一最小元素，在打打号号列列的各的各元素都元素都加加上这一最小元素（以保证上这一最小元素（以保证 0 元素不变），得新系数矩阵。元素不变），得新系数矩阵。若得到若得到 n 个独立的个独立的 0 元素，则获最优解；否则，

25、重复上步骤继元素，则获最优解；否则，重复上步骤继续变换系数矩阵。续变换系数矩阵。463.4 匈牙利算法匈牙利算法例例6（续）（续）5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5最小元素最小元素=2 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3473.4 匈牙利算法匈牙利算法例例6（续）（续）7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3此时加圈此时加圈 0的个数：的个数：m=n=5。最优解如下：最优解如下：483.4 匈牙利算法匈牙

26、利算法例例6（续）（续）（xij ）=0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 最优指派：最优指派：甲甲 B乙乙 C丙丙 E丁丁 D戊戊 A493.4 匈牙利算法匈牙利算法非标准形式的指派问题非标准形式的指派问题（！（！先转化为标准式，再用匈牙利法求解先转化为标准式，再用匈牙利法求解）1.最大化指派问题最大化指派问题 设最大化指派问题系数矩阵设最大化指派问题系数矩阵 C=（cij ），m为最大元素为最大元素m。令矩阵令矩阵 B=（bij）=（m-cij），则以），则以 B 为系数矩阵的最小为系数矩阵的最小化指派问题和以化指派问题和以 C

27、 为矩阵的最大化指派问题有相同最优解。为矩阵的最大化指派问题有相同最优解。2.“人数人数 事数事数”的指派问题的指派问题 若若人少事多人少事多，则添加一些虚拟的，则添加一些虚拟的“人人”，费用系数取，费用系数取 0；若；若人人多事少多事少，则添加一些虚拟的，则添加一些虚拟的“事事”，费用系数取，费用系数取 0。503.4 匈牙利算法匈牙利算法非标准形式的指派问题（续）非标准形式的指派问题（续）3.“一个人可做几件事一个人可做几件事”的指派问题的指派问题 若某个人可以做几件事，则将该人化作几个若某个人可以做几件事，则将该人化作几个“人人”来接受指派，来接受指派，这几个这几个“人人”做同一件事的费用系数都一样。做同一件事的费用系数都一样。4.“某事一定不能由某人做某事一定不能由某人做”的指派问题的指派问题 若某事一定不能由某人做，则可将相应的费用系数取为足够大若某事一定不能由某人做，则可将相应的费用系数取为足够大的数的数 M。Return