数学建模第二章整数规划2

1、数学建模数学建模第二章第二章 整数规划整数规划数学建模数学建模2.1 概论2.1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。2.1.2 整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：1. 变量全限制为整数时，称纯（完全）整数规划。2. 变量部分限制为整数的，称混合整数规划。数学建模数学建模（1）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： 原线性规划最优

2、解全是整数，则整数规划最优解与线性规划最优解一致。 整数规划无可行解。2.1.3 整数规划特点数学建模数学建模有可行解（当然就存在最优解），但最优解值变差。(2) 整数规划最优解不能按照实数最优解简单取整而获得。数学建模数学建模2.1.4 求解方法分类：（i）分枝定界法可求纯或混合整数线性规划。（ii）割平面法可求纯或混合整数线性规划。（iii）隐枚举法求解“0-1”整数规划： 过滤隐枚举法； 分枝隐枚举法。（iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法求解各种类型规划。数学建模数学建模2.2 0 1 型整数规划 0 1 型整数规划是整数规划中的特殊情形，它的变量x

3、j 仅取值0 或1。这时xj称为0 1变量约束条件：2.2.1 相互排斥的约束条件此种情况对应实际问题例1： 有两种运输方式可选，但只能用其中一种，用车的约束条件为了统一在一个问题中，引入 0 1变量y，约束条件可改写为：用船的约束条件数学建模数学建模其中M为充分大的数。y=0为用车，1为用船例例2：把相互排斥的约束条件改成普通约束条件：把相互排斥的约束条件改成普通约束条件数学建模数学建模例例3：M个相互排斥的约束条件个相互排斥的约束条件如果有m 个互相排斥的约束条件：为了保证这m 个约束条件只有一个起作用，我们引入m 个0 1变量 yi ( i=1, 2 , .m ） 和一个充分大的常数M

4、，则变为m 个yi中只有一个能取0 值数学建模数学建模2.2.2 关于固定费用的问题（关于固定费用的问题（Fixed Cost Problem） 在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。例例2.3 2.3 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考

5、虑。今设有三种方式可供选择，令xj表示采用第j 种方式时的产量；cj表示采用第j 种方式时每件产品的变动成本；kj表示采用第j 种方式时的固定成本。数学建模数学建模分析：采用各种生产方式的总成本分别为在构成目标函数时，为了统一在一个问题中讨论，现引入 0 1变量yj于是目标函数数学建模数学建模对应的3个线性约束条件其中是一个充分小的正常数，M 是个充分大的正常数数学建模数学建模2.2.3指派问题指派问题例2.4 拟分配n 人去干n 项工作，每人干且仅干一项工作，若分配第i 人去干第j项工作，需花费 cij单位时间，问应如何分配工作才能使工人花费的总时间最少？分析 要给出一个指派问题的实例，只需

6、给出矩阵 C= ( cij)，C 被称为指派问题的系数矩阵。 引入变量 xij ，若分配i 干j 工作，则取xij = 1 ，否则取xij = 0 。上述指派问题的数学模型为数学建模数学建模2.3 蒙特卡洛法例2.6 已知非线性整数规划为： 如果用显枚举法试探，共需计算 ( 100 ) 5 个点，其计算量非常之大。然而应用蒙特卡洛去随机计算106个点，便可找到满意解，数学建模数学建模 随机取样采集6 个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。假设目标函数落在高值区的概率分别为0.01，0.00001，则当计算106个点后，有任一个点能落在高

7、值区的概率分别为（i）首先编写子函数M 文件mente.m 定义目标函数f 和约束向量函数g，程序如下：function f,g=mengte(x);f=x(1)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)-8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5);数学建模数学建模g=sum(x)-400 x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-8002*x(1)+x(2)+6*x(3)-200 x(3)+x(4)+5*x(5)-200;（ii）随机取样计算方法-编写主函数对应M文件mainint.m如下求问题的解：rand(state,sum(c

8、lock);p0=0;ticfor i=1:106 x=99*rand(5,1); x1=floor(x);x2=ceil(x); f,g=mengte(x1); if sum(g=0)=4数学建模数学建模 if p0=f x0=x1;p0=f; end end f,g=mengte(x2); if sum(g=0)=4 if p0=f x0=x2;p0=f; end endendx0,p0toc数学建模数学建模p0=0;X=;ticfor i1=0:99 X(1,1)=i1; for i2=0:99 X(2,1)=i2; for i3=0:99 X(3,1)=i3; for i4=0:99

9、X(4,1)=i4; for i5=0:99 X(5,1)=i5; f,g=mengte(X); if sum(g=0)=4枚举法数学建模数学建模 if p0=1; x3+x5=1; x1+x2=1; x2+x6=1; x4+x6=1; x1+x2+x3+x4+x5+x6=3 代码如下 c=-193;-191;-187;-186;-180;-185; a=0,0,0,0,-1,-1;0,0,-1,0,-1,0;1,1,0,0,0,0;0,1,0,0,0,1;0,0,0,1,0,1; b=-1,-1,1,1,1; aeq=1,1,1,1,1,1; beq=3; x=bintprog(c,a,b,

10、aeq,beq) 0 1整数规划问题，可以直接利用Matlab 的函数bintprog 进行求解。数学建模数学建模 对于指派问题等 0 1整数规划问题，可以直接利用Matlab 的函数bintprog 进行求解。例2.7 求解下列指派问题，已知指派矩阵为数学建模数学建模%解：编写Matlab 程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 58 4 2 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25);for i=1:5 a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1;endb=ones(10,1);x,y=bint

11、prog(c,a,b);x=reshape(x,5,5),y%求得最优指派方案为 x51 =x44= x32 =x23= x15 = 1 最优值为21。数学建模数学建模2.5 分枝定界法分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。数学建模数学建模 分枝定界法可用于解

12、纯整数或混合的整数规划问题。在本世纪六十年代初由 Land Doig 和Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。 设有最大化的整数规划问题 A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作 ,而A的任意可行解的目标函数值将是z*的一个下界 分枝定界法就是将B的可行域分成子区域的方法。逐步减小和增大最终求到z*。现用下数学建模数学建模例来说明：解 （i）先不考虑整数

13、限制，即解相应的线性规划B ，得最优解为：数学建模数学建模可见它不符合整数条件。这时z 是问题A的最优目标函数值z*的上界，记作 。而x1=0, x2 = 0 显然是问题A的一个整数可行解，这时z = 0，是z*的一个下界，记作 ，即0 z* 356。（ii）因为 x1, x2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1进行分枝，把可行集分成2 个子集：因为 4 与5 之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：数学建模数学建模数学建模数学建模再定界：（iii）对问题B1再进行分枝得问题 B11和B12 ，它们的最优解为

14、（iv）对问题B2再进行分枝得问题 B12和 B22 ，它们的最优解为数学建模数学建模于是可以断定原问题的最优解为：从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题 A ，将与它相应的线性规划问题称为问题B 。（i）解问题B 可能得到以下情况之一：（a） B 没有可行解，这时A 也没有可行解，则停止（b） B 有最优解，并符合问题A 的整数条件， B 的最优解即为A 的最优解，则停止。（c） B 有最优解，但不符合问题A 的整数条件，记它的目标函数值为数学建模数学建模（ii）用观察法找问题A的一个整数可行解，一般可取 x j =0, j =

15、 1,. ,n，试探求得其目标函数值，并记作 。以z*表示问题A的最优目标函数值；这时有进行迭代。第一步：分枝，在 B 的最优解中任选一个不符合整数条件的变量 xj ，其值为 b j ，以b j 表示小于bj的最大整数。构造两个约束条件 xj b j 和 xj b j 将这两个约束条件，分别加入问题B ，求两个后继规划问题B 1和 B 2 。不考虑整数条件求解这两个后继问题。数学建模数学建模定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界 。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界 ，若无作用 不变。第二步：比较与剪

16、枝，各分枝的最优目标函数中若有小于z 者，则剪掉这枝，即以后不再考虑了。若大于 ，且不符合整数条件，则重复第一步骤。一直到最后得到z* = 为止。得最优整数解x * j . j =1.2.n 。剪枝的条件剪枝的条件1.无可行解的分支；2.得到整数解的分支；3.目标函数值小于下界的分支数学建模数学建模数学建模数学建模数学建模数学建模补充数学建模数学建模生产与销售计划问题生产与销售计划问题例9 某公司用两种原油（ A 和B ）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油的最低比例分别为50和60，每吨售价分别为4800 元和5600 元。该公司现有原油A 和B 的库存量分别为500 吨和1000 吨，还可以从市场上买到不超过1500吨的原油A 。原油A 的市场价为：购买量不超过500 吨时的单价为10000 元/吨；购买量超过500 吨单不超过1000 吨时，超过500 吨的部分8000 元/吨；购买量超过1000 吨时，超过1000 吨的部分6000 元/吨。该公司应如何安排原油的采购和加工。数学建模数学建模建立模型建立模型（1）问题分析安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收入