2整数规划(研究生)

1、整数规划南京航空航天大学经济与管理学院 教授、博士生导师 管理科学与工程系主任 1第五章 整数规划 在线性规划问题中，所有的解都假设为具有连续 型的数值，即解可以是整数、分数或带有小数点的实 数。但对于某些具体的问题，常要求最优解是整数的 情形。例如，所求的解是机器台数，完成工作的人数 或装货的车数等，这时，分数或小数的解答就不符合 要求。为了满足整数解的要求，初看起来，似乎只要 把已求得的解经过“舍入化整”就可以，但这常常是不 可行的。因为化整后不见得是可行解。或虽然是可行 解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数规划 (Integer Pro

2、gramming)，简称为 I P 。2整数规划中，如果所有的变量都要求是（非负） 整数，就称为纯整数规划(Pure Integer Programming) 或全整数规划(All Integer Programming)；如果仅是 其中一部分变量取值为整数，则称为混合整数规划( Mixed Integer Programming )。 3第2章 整数规划例1、集装箱运货 货物 体积(米3/箱) 重量(百公斤/箱) 利润(千元/箱) 甲 5 2 20 乙 4 5 10 装运限制 24 13 2.1 数学模型4解：设X1 , X2 为甲、乙两货物各托运箱数5X1+4X2 242X1+5X2 13

3、X1 , X2 0X1 , X2为整数maxZ = 20 X1 + 10 X25例2、背包问题背包可再装入8单位重量，10单位体积物品物品 名称 重量 体积 价值 1 书 5 2 20 2 摄像机 3 1 30 3 枕头 1 4 10 4 休闲食品 2 3 18 5 衣服 4 5 15 6解：Xi为是否带第 i 种物品maxZ=20X1 + 30X2 +10X3+18X4 +15X55X1+3X2 +X3 +2X4 +4X5 82X1+X2 +4X3 +3X4 +5X5 10Xi为0, 17一般形式：,整数8(1)、 Xi为i 物品携带数量 ai为i 物品单位重量 ci为i 物品重要性估价 b

4、为最大负重(2)、 投资决策 Xi为在i 地区建厂规模 ai为在i 地区建厂基建费用 ci为在i 地区建厂单位利润 b为最大资本(3)、 Xi 取0或1时，可作项目投资模型9例3、选址问题A1A3B2B4B3B1A2Ai: 可建仓库地点，容量ai ,投资费用bi ，建2个Bj: 商店，需求dj ( j=14 )Cij: 仓库 i 到商店 j 的单位 运费问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。10解：设Xi ( i=1,2,3)为是否在 Ai 建仓库 yij ( i=1,2,3, j=14)由 i仓库向 j商店运货量y11 + y21 = d1y12 + y22 + y32

5、= d2y23+ y33 = d3y14 + y24 + y34 = d4x1 + x2 + x3= 2y11 + y12 + y14 a1x1y21 + y22 + y23 + y24a2x2y32 + y33 + y34 a3x3xi 为01， yij 0混合整数规划1101决策变量的应用 可用于相互排斥计划中例1、运输方式：火车、船。 火车：5X1+4X2 24 (体积) 船： 7X1+3X2 45 (体积)12maxZ=20X1 + 10X2 2X1+5X2 135X1+4X2 24+MX37X1+3X2 45+M(1-X3 )X1 , X2 0 整数X3为0或1 M0当 X3 =0

6、火车 X3 =1 船 13例2、ai1x1+ai2x2 +ainxn bi (i=1,m)互相排斥m个约束，只有一个起作用ai1x1+ainxn bi+yi M (i=1,m)y1 + ym =m-1yi为0或1 M0142.2 整数规划解法(一)、整数规划的解：可行域为其相应线性规划问题的可行域的子集例1、LP:X=(4.8,0) maxZ=96 ILP:X=(4,1) maxZ=90 x1x262O6.5(4.8,0)15(1)、四舍五入法 可估近似解，例中X=(4,0), Z=80 80 Z* 96 0Z*- 80S0 且解为整数解，令ScS0 且解为非整数解，令(C)，(D)取代(B)

7、 返回(4)(6)、全部枝剪完，停25优点：(1)、任何模型均可用；(2)、思路简单、灵活；(3)、速度快；(4)、适合上机。26分枝定界法注意事项：(1)、分枝变量选择原则： 按目标函数系数：选系数绝对值最大者变 量先分。 对目标值升降影响最大。 选与整数值相差最大的非整数变量先分枝。 按使用者经验，对各整数变量排定重要性 的优先顺序。27(2)、分枝节点选择： 广探法： 选目标函数当前最大值节点，找到的整数 解质量高。慢。 深探法(后进先出法)： 最后打开的节点最先选，尽快找到整数解。 整数解质量可能不高。2801问题的分枝定界法（背包问题)例： maxZ=12X1 + 12X2 + 9X

8、3 + 15X4 + 90X5 + 26X6+ 112X7 (A)3X1 + 4X2 + 3X3 + 3X4 + 15X5 + 13X6+ 16X7 35Xj为0或1，(j=17)松弛问题(B)为同于(A)约束，目标0 Xj 1 (j=17)29解:“单位重量价值大的先放” 重量 价值 价/重 1 3 12 4 2 4 12 3 3 3 9 3 4 3 15 5 5 15 90 6 6 13 26 2 7 16 112 7 30(0)Z=221 X7=X5=X4=1X1=1/3(9)217 X1=X4=X7=1X5=13/5(10)217 X1=X7=X5=1X2=1/4(5)216X3=X7

9、=X5=1X4=1/3(6)219 X7=X5=X4=1X6=1/13(1)219 X1=X7=X5=1X4=1/3(7)174 X6=X7=1X5=6/15(8)217 X7=X5=X4=1(2)220X7=X5=X4=1X2=1/4(3)214 X2=X7=X5=1(4)220 X7=X5=X4=1X3=1/3X1=1X1=0 X2=1X2=0X3=1X3=0X4=1X4=0X6=1X6=031隐枚举法(一)、基本思想：对maxZ=CXAX=bX为0的2n个可能解，只检查其中一部分例：maxZ = 2x1+4x2 +x33x1 - 8x2+5x3 -1x1 , x2 , x3为 0 ,1

10、32(二)、简单隐枚举法(max)原则：(1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0(2)、增加过滤条件Z Z0(3)、将xi 按ci由小大排列33例：maxZ = 3x1 -2x2+5x3x1 +2x2 - x3 2 x1 +4x2 +x3 4 x1 + x2 3 4x2+x3 6 x1 , x2 , x3为0或1解：观察得解(x1 , x2 , x3 )=(1 ,0 ,0) Z0 =3过滤条件：3x1 - 2x2+5x3 3 将(x1 x2 x3 ) (x2 x1 x3 ) 34解(x2 x1 x3 ) 目标值 Z0 当前最好值 (0 ,0 ,0) 0 5 (0 ,1

11、,0) 3 8 (1 ,0 ,0) -2 (1 ,0 ,1) 3 (1 ,1 ,0) 1 (1 ,1 ,1) 6 最优解 x = (1 ,0 ,1 )T Z=835割平面法3637x1 xr xm ym+1 ym+2 yn RHS0 0 0 m+1 m+2 nf*x1.xr.xm1 0 0 a1m+1 a1m+2 a1n .0 1 0 ar m+1 ar m+2 ar n .0 0 1 am m+1 a m m+2 am nb1.br.bm38394041x1 x2 x3 x4RHS0 0 -1/2 -1/2-5/2x1x21 0 -1/4 1/40 1 3/4 1/43/47/44243得到

12、新的对偶单纯形表x1 x2 x3 x4 x5 RHS0 0 -1/2 -1/2 0-5/2x1x2x31 0 -1/4 1/4 0 0 1 3/4 1/4 0 0 0 -3/4 -1/4 1 3/4 7/4 -3/4 44进一步得到最优单纯形表:x1 x2 x3 x4 x5 RHS0 0 0 -1/3 -2/3-2x1x2x31 0 0 1/3 -1/30 1 0 0 10 0 1 1/3 -4/311145指派问题一、指派问题的数学模型 在生活中经常会遇到这样的问题，某单位需要指派 n 个人去完成 n 项任务，每个人只做一项工作，同时，每项工作只由一个人完成。由于各人的专长不同，每个人完成各

13、项任务的效率也不同。于是产生了应指派哪一个人去完成哪一项任务，使完成 n 项任务的总效率最高（如所用的时间为最少）。我们把这类问题称之为指派问题或分派问题(Assignment Problem)。46例 1 :有一份中文说明书,需要译成英、日、德、俄四 种文字，分别记作 E、J、G、R 。现有 甲、乙、丙丁四人，他们将中文说明书翻译成不同文字说明书所 需要的时间如表41所示。问应指派何人去完成哪一 项工作，使所需的总时间最少？ 表41 任务人员EJGR甲215134乙1041415丙9141613丁7811947 类似的有：n 项加工任务，怎样指派到 n 台机床上分别完成的问题；n 条航线，怎

14、样指定 n 艘船去航 行的问题等等。对应每个指派问题, 都有类似表4 1那样的表格，我们称之为效率矩阵或系数矩阵，某 元素 cij ( i , j = 1,2, , n ) 表示指派第 i 个人去完成 第 j 项任务时的效率(或时间、成本等)。解题时需要 引入变量 xij ；其取值只能是 1 或 0，并令 ：48 当问题是要求极小化时的数学模型是：49 指派问题的解矩阵应当是每行或每列只能有一个 元素为1，其余均为 0 的 n 阶方阵。如下就是例1 的 一个 解矩阵： 指派问题是 01规划的特例，也是运输问题的特 例；即 m = n ，ai = bj = 1。我们利用指派问题的特点 可以有更为

15、简便的求解方法。50 定理 设 (cij)是指派问题的系数矩阵, cij 0，i , j = 1 , 2, , n 。若从(cij)的某一行（列）各元素中分别减 去该行（列）的最小元素而得到的新矩阵 (bij) ，那么 以新矩阵 (bij) 为系数矩阵的指派问题与原问题具有相 同的最优解。 库恩（W.W.Kuhn）于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼（D.Knig) 一个关 于矩阵中 0 元素的定理：系数矩阵中独立 0 元素的最 多个数等于能覆盖所有 0 元素的最少直线数。这个解 法称之为匈牙利法。51 以下用例 1 来说明指派问题的解法。 第一步：使指派问题的系数矩阵，

16、经变换，在各行各 列中都出现 0 元素。为此分如下两步进行：（1）将系数矩阵的每行元素减去该行的最小元素；（2）再从所得的系数矩阵中，将每列减去该列的最 小元素。（若该行或列已有 0 元素，则就不必计算） 第二步：进行试指派以寻求最优解。为此按如下 5 个 分步骤进行：（1）从只有一个 0 元素的行（列）开始，给这个0 元 素加圈，记为 。然后划去 所在的列（行）的其它 0 元素，记为 。这表示该列所代表的任务已指派 完，不必再考虑别人。52 （2）给只有一个 0 元素的列的 0 元素加圈，记为 ；然后划去 所在行的 0 元素，记为 。（3）重复进行（1）、（2）两步，直到所有 0 元素 都被

17、圈出和划掉为止。（4）若仍然有没有被划圈的 0 元素，且同行（列） 的 0 元素至少有两个（表示对这个人可以从两项任务 中指派其一），则可用不同的方案去试探。从所剩 0 元素最少的行或列开始，比较该行或列各 0 元素所在列或行中 0 元素的数目，选择 0 元素少的那一列或行 的这个 0 元素加圈（表示选择性多的要“礼让”选择性 少的）。然后划掉同行或列的其它 0 元素。反复进行 直到所有 0 元素都已被圈出和划掉为止。（5）若 元素的数目 m 等于矩阵的阶数 n ,那么这个指派问题的最优解已得到。若 m n,则转入下一 步：5354 这时我们已经找到了4个不同行不同列的 0 元 素，所以，该问

18、题的最优解矩阵是： 这表示：指定甲翻译俄文，乙翻译日文，丙翻译英文 ，丁翻译徳文。所需总时间最少为：55 例：求如下系数矩阵所对应的指派问题： 解：按第一、二步将系数矩阵进行变换和试指派：56 这里独立 0 元素的个数 m = 4 5 ；所以解题没有完 成，这时，应按以下步骤进行： 第三步：作最少的直线覆盖所有的 0 元素，以确定该 系数矩阵中能找到最多的独立 0 元素。为此按以下步 骤进行：57（1）对没有 的行打 ；（2）对已打 的行中包含有 0 元素的列打 ；（3）再对有打 的列中含有的 的行打 ；（4）重复（2）、（3）直到得不出新的打 的行、 列为止； （5）对没有打 的行画一横线，

19、对打 的列画一纵 线，这就得到了能够覆盖所有 0 元素的最少直线数。 令这直线数为 l 。若 l n ，则说明必须再变换当 前的系数矩阵，才能找到 n 个独立的 0 元素，为此转 第四步；若 l = n ，应回到第二步，另行试探。58 在例中，对由第一、二步所求得的矩阵进行第 三步的工作： l = 4 5 ，所以应继续对上述矩阵进行变换，转 第四步；59 第四步：对于上述矩阵进行行变换的目的是增加 0 元素。为此，在没有被直线覆盖的部分中找出最小元素， 然后在打 行各元素中都减去该最小元素，而在打 列的各元素中都加上该最小元素，以保证原来的 0 元 素的位置在经过变换之后仍然还是 0 元素。这样得到 的新系数矩阵与原问题具有相同最优解。由此若能得 到 n 个独立的 0 元素，则已得到最优解；否则返回到 第三步重复进行。 对于上例，我们继续进行计算如下：6061 这时我们已经找到了 n 个不同行不同列的 0 元素 ，