《管理运筹学》课件04整数规划.pptx

明德明德 砺志砺志 博学博学 笃行笃行整数规划整数规划第四章管理学院2管理运筹学Chapter4 整数整数规划划(Integer Programming )整数规划的数学模型整数规划的数学模型分支定界法分支定界法分配问题与匈牙利法分配问题与匈牙利法本章主要内容：本章主要内容：管理学院3管理运筹学4.1 整数整数规划的数学模型划的数学模型整数整数规规划（划（简简称：称：IPIP）要求一部分或全部决策变量取整数值的规划问题称为整数规划不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题若该松弛问题是一个线性规划，则称该整数规划为整数线性规划整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式：管理学院4管理运筹学整数整数整数整数线线性性性性规规划划划划问题问题的种的种的种的种类类： 纯整数线性规划：指全部决策变量都必须取整数纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划值的整数线性规划 混合整数线性规划：决策变量中有一部分必须取混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划整数值，另一部分可以不取整数值的整数线性规划。

0-1型整数线性规划：决策变量只能取值型整数线性规划：决策变量只能取值0或或1的整的整数线性规划数线性规划4.1 整数整数规划的数学模型划的数学模型管理学院5管理运筹学整数整数整数整数规规划的典型例子划的典型例子划的典型例子划的典型例子例例4.1 工厂工厂A1和和A2生产某种物资由于该种物资供不应求，故生产某种物资由于该种物资供不应求，故需要再建一家工厂相应的建厂方案有需要再建一家工厂相应的建厂方案有A3和和A4两个这种物两个这种物资的需求地有资的需求地有B1,B2,B3,B4四个各工厂年生产能力、各地年需四个各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费求量、各厂至各需求地的单位物资运费cij，见下表：，见下表：B1B2B3B4年生产能力年生产能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工厂工厂A3或或A4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为1200万或万或1500万元现要决定应万元现要决定应该建设工厂该建设工厂A3还是还是A4，才能使今后每年的总费用最少才能使今后每年的总费用最少。

4.1 整数整数规划的数学模型划的数学模型管理学院6管理运筹学解：解：这是一个物是一个物资运运输问题，特点是事先不能确定，特点是事先不能确定应该建建A3还是是A4中哪一个，因而不知道新厂投中哪一个，因而不知道新厂投产后的后的实际生生产物物资为此，引入此，引入0-1变量：量：再设再设xij为由为由Ai运往运往Bj的物资数量，单位为千吨；的物资数量，单位为千吨；z表示总费用，单位万元则该规划问题的数学模型可表示总费用，单位万元则该规划问题的数学模型可以表示为：以表示为：4.1 整数整数规划的数学模型划的数学模型管理学院7管理运筹学混合整数规划问题混合整数规划问题4.1 整数整数规划的数学模型划的数学模型管理学院8管理运筹学例4.2 现有资金总额为B可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j1,2,.,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2反之不一定项目3和4中至少选择一个；项目5,6,7中恰好选择2个应该怎样选择投资项目，才能使总预期收益最大4.1 整数整数规划的数学模型划的数学模型管理学院9管理运筹学解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：投资问题可以表示为：投资问题可以表示为：4.1 整数整数规划的数学模型划的数学模型管理学院10管理运筹学例4.3 指派问题或分配问题。

人事部门欲安排四人到四个不同岗位工作，每个岗位一个人经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁869080884.1 整数整数规划的数学模型划的数学模型管理学院11管理运筹学设 数学模型如下：要求每人做一项工作，约束条件为：4.1 整数整数规划的数学模型划的数学模型管理学院12管理运筹学每项工作只能安排一人，约束条件为：变量约束：4.1 整数整数规划的数学模型划的数学模型管理学院13管理运筹学整数整数整数整数规规划划划划问题问题解的特征：解的特征：解的特征：解的特征： 整数规划问题的可行解集合是它松弛问题可行解整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解满足整数约束条件，因而不一定仍为可行解 整数规划问题的可行解一定是它的松弛问题的可整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不行解（反之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。

会优于后者最优解的目标函数值4.1 整数整数规划的数学模型划的数学模型管理学院14管理运筹学例4.3 设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）4.1 整数整数规划的数学模型划的数学模型管理学院15管理运筹学用用图解法求出最解法求出最优解解为：x13/2, x2 = 10/3，且有，且有Z = 29/6现求整数解现求整数解(最优解最优解):如用舍如用舍入取整法可得到入取整法可得到4个点即个点即(1，3),(2，3),(1，4),(2，4)显然，它显然，它们都不可能是整数规划的最优解们都不可能是整数规划的最优解x1x233(3/2,10/3)按整数规划约束条件，其可行按整数规划约束条件，其可行解肯定性规划问题的可行域解肯定性规划问题的可行域内且为整数点故整数规划问题内且为整数点故整数规划问题的可行解集是一个有限集，如右的可行解集是一个有限集，如右图所示其中其中(2,2),(3,1)点的目点的目标函数值最大，即为标函数值最大，即为Z=44.1 整数整数规划的数学模型划的数学模型管理学院16管理运筹学整数整数规划划问题的求解方法：的求解方法： 分支定界法和割平面法分支定界法和割平面法 匈牙利法（指派问题）匈牙利法（指派问题）4.1 整数整数规划的数学模型划的数学模型管理学院17管理运筹学4.2 分支定界法分支定界法1）求整数）求整数规划的松弛划的松弛问题最最优解；解；若松弛若松弛问题的最的最优解解满足整数要求，得到整数足整数要求，得到整数规划的最划的最优解解,否否则转下下一步；一步；2）分支与定界：）分支与定界：任意任意选一个非整数解的一个非整数解的变量量xi，在松弛，在松弛问题中加上中加上约束：束：xixi 和和 xixi+1组成两个新的松弛成两个新的松弛问题，称，称为分枝。

新的松弛分枝新的松弛问题具有特征：当原具有特征：当原问题是求最大是求最大值时，目，目标值是分枝是分枝问题的上界；当原的上界；当原问题是求最小是求最小值时，目，目标值是分枝是分枝问题的下界检查所有分枝的解及目所有分枝的解及目标函数函数值，若某分枝的解是整数并且目，若某分枝的解是整数并且目标函数函数值大于（大于（max）等于其它分枝的目）等于其它分枝的目标值，则将其它分枝剪去不再将其它分枝剪去不再计算，算，若若还存在非整数解并且目存在非整数解并且目标值大于大于(max)整数解的目整数解的目标值，需要，需要继续分分枝，再枝，再检查，直到得到最，直到得到最优解分支定界法的解题步骤：分支定界法的解题步骤：管理学院18管理运筹学例例4.4 用分枝定界法求解整数用分枝定界法求解整数规划划问题解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题( (原整数规划原整数规划问题的松驰问题问题的松驰问题) )LPIP4.2 分支定界法分支定界法管理学院19管理运筹学用用图解法求松弛解法求松弛问题的最的最优解，如解，如图所示x1x23(18/11,40/11)21123x118/11, x2 =40/11Z=218/11(19.8)即即Z 也是也是IP最小值的下限。

最小值的下限对于对于x118/111.64，取值取值x1 1， x1 2对于对于x2 =40/11 3.64，取值，取值x2 3 ，x2 4先将（先将（LP）划分为）划分为（LP1）和（）和（LP2）,取取x1 1, x1 24.2 分支定界法分支定界法管理学院20管理运筹学分支：分支：分别求出（分别求出（LP1）和（）和（LP2）的最优解的最优解4.2 分支定界法分支定界法管理学院21管理运筹学先求先求LP1,如如图所示此时在在B点取得最点取得最优解x11, x2 =3, Z(1)16找到整数解，找到整数解，问题已探明，已探明，此枝停止此枝停止计算x1x233(18/11,40/11)11BAC同理求同理求LP2,如图所示在如图所示在C 点点取得最优解即取得最优解即:x12, x2 =10/3, Z(2)56/318.7 Z(2) Z(1)16 原问题有比原问题有比16更小的最优更小的最优解，但解，但 x2 不是整数，故继续不是整数，故继续分支4.2 分支定界法分支定界法管理学院22管理运筹学在在IP2中分中分别再加入条件：再加入条件： x23, x24 得下式两支：得下式两支：分别求出分别求出LP21和和LP22的最优解的最优解4.2 分支定界法分支定界法管理学院23管理运筹学x1x233(18/11,40/11)11BACD先求先求LP21,如图所示。

此时如图所示此时D 在点取得最优解在点取得最优解即即 x112/52.4, x2 =3, Z(21)-87/5-17.4 Z(211) 如对如对LP212继续分解，其最小值继续分解，其最小值也不会低于也不会低于15.5 ，问题探明，问题探明,剪枝4.2 分支定界法分支定界法管理学院26管理运筹学原整数原整数规划划问题的最的最优解解为: x1=2, x2 =3, Z* =17以上的求解以上的求解过程可以程可以用一个用一个树形形图表示如表示如右：右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22无可无可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x134.2 分支定界法分支定界法管理学院27管理运筹学例例4.5 用分枝定界法求解用分枝定界法求解解解: 先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）用图解法得到最优解用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所示。

如下图所示4.2 分支定界法分支定界法管理学院28管理运筹学1010松弛问题松弛问题LP0的最优解的最优解X=(3.57,7.14),Z0=35.7x1x2oABC4.2 分支定界法分支定界法管理学院29管理运筹学10 x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.54.2 分支定界法分支定界法管理学院30管理运筹学10 x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.3364.2 分支定界法分支定界法管理学院31管理运筹学10 x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP21。