第五章 整 数 规 划(Integer Programming,IP) 本章本章内容内容|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题 整数规划问题|要求一部分或全部决策变量必须取整数值的规划问题称为整数规划不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题若松弛问题是一个线性规划，则该整数规划为整数线性规划integer linear programming）|纯整数线性规划，混合整数线性规划，0－1型整数线性规划 投资组合问题案例| 某财团有 万元的资金，经过考察选中 个投资项目，每个项目只能投资一个其中第 个项目需投资金额为 万元，预计5年后获利 万元 ，问应如何选择项目使得5年后总收益最大？ 投资组合问题模型|变量—每个项目是否投资|约束—总金额不超过限制|目标—总收益最大 背包问题实例|某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。
尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里 背包问题实例物品12345678910体积200350500430320120700420250100价格1545100705075200902030 背包问题模型|变量变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数为此我们设变量为第i个物品是否放在第j个包裹中 |约束约束 包裹容量限制： 必带物品限制： 选带物品限制：|目标函数目标函数 未带物品购买费用最小背包问题模型 背包问题模型s.t. 整数整数规划规划问题问题n特征特征—变量整数性要求；n来源来源— 问题本身的要求； 引入的逻辑变量的需要；n性质性质—可行域是离散集合； 线性整数规划模型|一般整数规划模型|0-1整数规划模型|混合整数规划模型 一般整数规划模型整数线性规划线性数学问题模型的一般形式为 0-1整数规划模型 混合整数规划模型 投资问题的进一步例子| 现有资金总额为B。
可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj(j=1,2,…，n)此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2反之，则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7中恰好选择两个应当怎样选择投资项目，才能使总预期收益最大?属于 0-1规划问题 投资问题的进一步例子|令|问题模型为： 整数规划问题解的特点（IP）问题的松弛问题 整数规划问题解的特点∩≤松弛问题的最优值是原整数规划的目标函数值的上界 注释|最优解不一定在顶点上达到|最优解不一定是松弛问题最优解的邻近整数解|整数可行解远多于顶点，枚举法不可取 本章本章内容内容|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题 割平面法的基本思想：若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.割平面法 割平面法|由松弛问题的可行域向整数规划的可行域逼近|方法—利用超平面切除|要求整数解保留 松弛问题最优值向最优解逼近|目标得到的新的可行域的某个整数坐标的极点恰好是问题的最优解 割平面法非基变量下标集合n符号[*]表示不超过“*”的最大整数，f(*)表示“*”的非负真分数。
Gomory约束 L0的最优单纯形表：x1… xi… xmxm+1… xm+j… xn解检0… 0… 0λ1… λm+j… λnz-z0x11… 0… 0a1m+1… a1m+j… a1nb10︰︰︰︰︰︰︰︰xi0… 1… 0aim+1… aim+j… ainbi0︰︰︰︰︰︰︰︰xm0… 0… 1amm+1… amm+j… amnbm0源方程 ------对应于生成行i的割平面 1.松弛问题的非整数最优解不满足上式2.松弛问题的整数可行解满足上式 |求解整数线性规划第一步：解整数规划问题的松弛问题，见表5-3 ，x1=13/7， x2=9/7；4 cj3-1000cBxBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70x431/700-3/7122/7cj-zj00-5/70-3/7表 5-3|第二步：写出割平面方程，选择第一行产生割平面约束， cj3-10000cBxBibix1x2x3x4x5x63-100x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7[-2/7]0001cj-zj-5/200-5/70-3/70…3-100x1x2x3X515/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4cj-zj000-1/40-17/4表 5-4 |类似地，写出割平面方程，选择第四行产生割平面约束， cj3-1000 00cBxBibix1x2x3x4x5x6x73-1000x1x2x3x5x41241310000010000010000001000101-1-5-110-1-21-4cj-zj-100000-4-1表 5-5原整数规划问题的最优解为，x1=1, x2=2,max z=1 四、割平面计算步骤：第一步： 用单纯刑法解整数问题IP的松弛问题L0若L0没有最优解，则IP没有最优解。
停止若L0有最优解X0:(1)X0是整数解， 则X0也是IP的最优解，停止(2)X0不是整数解， 转第二步第二步： 求割平面方程 第三步：将割平面加到L0得L1第四步：解L1在L0的最优单纯型表中增加一行一列，得L1的单纯型表，用对偶单纯刑法求解，若其解是整数解，则该解也是原整数规划的最优解否则将该解记为X0，返回第二步 本章本章内容内容|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法分支定界法|0-1型整数规划|指派问题 分支定界法 分支定界法(branch and bound method)是一种隐枚举法(implicit enumeration)或部分枚举法，它不是一种有效算法，是枚举法基础上的改进 分支定界法的关键是分支和定界 分支 求解放松问题 舍弃 变界 分支最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比界好 |分枝定界法的基本思路： 通过对松弛问题的分枝，不断降低（IP）最优值的上界，提高下界，当上界等于下界时，得到最优解。
分支[ ]是不超过 的最大整数 IP松弛问题L0L1L2通过对（L0）分枝，使（IP）的最优值的上界不断下降，L3L4L5L6下界不断上升，上界=下界得最优值 定界|当前得到的最好整数解的目标函数值|分支后计算放松的线性规划的最优解|整数解且目标值优于原有最好解的值则替代原有最好解；|整数解且目标值劣于原有最好解的值则 删除该分支其中无最优解；|非整数解且目标值优于原有最好解的值则继续分支；|非整数解且目标值劣于原有最好解的值则删除该分支其中无最优解； 算例|例6 求解下述整数规划 算例|第一步：舍弃整数要求，用单纯形法求解，得X(0)=(3/2,10/3),点 A,目标函数值z (0) =29/6（上界），（0，0）显然是一个可行解，目标函数值0（下界） 算例|第二步，由于x1,x2都不是整数，分解成子问题（分支）先考虑x1 ， x1 =3/2 （1）（2）X(1)=(2,23/9), B点z (1) =41/9X(2)=(1,7/3), C点,z (2) =10/3 (新下界) 算例 算例|第三步，由于z (2)
此时，问题（2）已探明，结束问题（1）需继续分支3）（4）无可行解，删去（剪枝）X(4)=(33/14,2), D点， z (4) =61/14 算例 算例|第四步，由于z (2)
要求制订一个生产计划，使总收益最大§40-1整数规划 §40-1整数规划 |求解设xj是第 j 种产品的产量，j=1,2,3；再设 其中约束条件 如何理解？ 0-1整数规划解法|隐枚举法（适合于变量个数较少的0-1规划）| 例 10 求解0-1整合规划（5.14a）（5.14b）（5.14d）（5.14c） 算例|解： 约束条件(x1, x2, x3)abcdz(0,0,0)√ √√√ 0（初始滤值）(0,0,1)√√√√ 5（新滤值）(0,1,0)-------- -2(0,1,1)-------- 3(1,0,0)-------- 3(1,0,1)√√√√ 8 （最后过滤值）(1,1,0)-------- 1(1,1,1)-------- 6最优解 整整数数规规划划|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题（指派问题（assignment problem）） 指派问题模型n模型Cij为第i人做第j事的费用令一般称矩阵C=(cij)n×n为指派问题的系数矩阵 指派问题的匈牙利解法|性质：假定C=(cij)为指派问题的价值系数矩阵。
现将它的某一行（或某一列）的各元素都减去一个常数k，得到一新矩阵 若以C’代替C作为该指派问题的价值系数矩阵，而构成一新的指派问题，则这个分派问题的最优解与原指派问题的最优解相同 第1步：把各行元素分别减去本行元素的最小值；然后在此基础上再把每列元素减去本列中的最小值算例例12系数矩阵此时每行及每列中肯定都有0元素了 第2步：确定独立零元素，并作标记1）首先逐行判断是否有含有独立0元素的行，如果有，则按行继续处理；如没有，则要逐列判断是否有含有独立0元素的列，若有，则按列继续处理若既没有含有独立0元素的行，也没有含有独立0元素的列，则仍然按行继续处理 （2）在按行处理时，若某行有独立0元素，把该0元素标记为a，把该0所在的列中的其余0元素标记为b；否则，暂时越过本行，处理后面的行把所有含有独立0元素的行处理完毕后，再回来处理含有2个以及2个以上的0元素的行：任选一个0做a标记，再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b （3）在按列处理时，若某列有独立0元素，把该0元素标记为a，把该0所在的行中的其余0元素标记为b；否则，暂时越过本列，处理后面的列。
把所有含有独立0元素的列处理完毕后，再回来处理含有2个以及2个以上的0元素的列：任选一个0做a标记，再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b4）重复上述过程，即得到独立零元素（标记a的“0”） 第3步：若独立零元素等于矩阵阶数，则已经得到最优解，若小于矩阵阶数，则继续以下步骤：（1）对没有标记a的行作标记（2）在已作标记 的行中，对标记b所在列作标记（3）在已作标记 的列中，对标记a 所在的行作标记（4）对没有标记 的行划线，对有标记 的列划线√√√√√√√√√√ 第4步：在未被直线覆盖的所有元素中找出一个最小元素（Xmin），未被直线覆盖的行（或列）中所有元素都减去这个数注：若未被直线覆盖部分是行数<列数，则是按行减，反之则按列） 第5步：这样必然出现负元素，所以对负元素所在列（或行）中各元素都加上这一最小元素（Xmin）以消除负数这样，再返回步骤2，确定独立零元素个数重复上述操作，直到找出最优解 中已有5个独立零元素，故可确定指派问题的最优指派方案 |非标准形式的指派问题最大化指派问题人数和事数不等的指派问题一个人可能几件事的指派问题 收益1 2 … j … n12…i…n指派问题模型：i=1,2, …,nj=1,2, …,n第i个人做第j 人件事Z表示总收益i=1,2, …,n; j=1,2, …,n第i个人不做第j 人件事 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。
cij表示第i个人做第j件事的收益,求总收益最大的指派方案1)最大化指派问题 工作人收益1 2 … j … n12…i…n指派问题最大化的数学模型：i=1,2, …,nj=1,2, …,n指派问题最小化的数学模型：i=1,2, …,nj=1,2, …,n用匈牙利法n （2）人数与事数不等的指派问题 设有n个工作，要由 m个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作cij表示第i个人做第j件事的费用,求总费用最低的指派方案a)m>n工作人费用1 2 … j … n12…i…mn+1 n+2 …m 用匈牙利法求解 工作人费用1 2 … j … n12…i…mm+1 m+2 … n (b)m