《2013参考数学建模常用方法整数规划ppt课件》由会员分享，可在线阅读，更多相关《2013参考数学建模常用方法整数规划ppt课件（34页珍藏版）》请在金锄头文库上搜索。
1、第二章 整 数 规 划,1整数规划的基本概念 2分枝定界法解整数规划 3规划 4. 指派问题的解法,第一节 概 述,人们探讨某些线性规划问题，有时必须把全部或部分决策变量限制为整数。这样的线性规划问题，通常称为整数规划。作为线性规划的特殊情况，整数规划也有最小化和最大化之别。此外，整数规划还可以分成纯整数规划和混整数规划。二者的区别在于：前者的决策变量必定全部取整数。而后者的决策变量只是部分取整数。,例1 某医药公司现有两个制药厂A1和A2，三个销售店B1、B2 和 B3。公司打算由两个拟建的制药厂A3 和 A4 中选择一个，来兴建新厂。各销售店每周药品需求量见表2-1。各制药厂每周药品产量和
2、每箱药品运费见表2-2。新厂投产后，估计每周的操作费（含折旧费）：A3 是100元，A4 是120元。在两个拟建的制药厂中，应当选择哪个呢？,表 21,表 22,设：制药厂Ai 每周运到销售店Bj 的药品为xij 箱（i =1,2，3，4； j =1，2，3）；,解：建立数学模型,两个老厂A1 和 A2 及一个新厂A3 和 A4 每周的 总费用为 y 元。新厂厂址的选择应该确保 y 达到 最小值。于是，y 是目标函数，xij、u 和 v 都是 决策变量。它们之间的关系可以表述为： y = 3x11 + 2x12 + 3x13（A1每周的运费） + 10 x21 + 5x22 + 8x23（A2
3、每周的运费） + x31 + 3x32 +10 x33（A3每周的运费） + 4x41 + 5x42 + 3x43（A4每周的运费） + 100 u（A3每周的操作费） + 120 v（A4每周的操作费）,(1) u 和 v 全是 01 变量：,约束条件：,x11 + x 12 + x13 50 x21 + x 22 + x23 70 x31 + x 32 + x33 20 u x41 + x 42 + x43 20 v,u, v = 0, 1,(2) 由 A3 和 A4 选择一个来兴建新厂：,u + v =1,(3) 每个制药厂每周运到各销售店的药品不会超过其产量：,(4) 每个销售店每周药
4、品的需求量能够得到各制药厂的充分供应：,（5）药品箱数一定取非负值：,xij 0,x11 + x21 + x31 + x41 = 50 x12 + x22 + x32 + x42 = 60 x13 + x23 + x33 + x43 = 30,例1的数学模型为：,Min y = 3x11 + 2x12 + 3x13 + 10 x21 + 5x22 + 8x23+ x31 + 3x32 +10 x33+ 4x41 + 5x42 + 3x43+100u+120v,本数学模型属于最小化混整数规划,例2 某医疗器械厂生产A1和A2两种产品。出 厂前，每种产品均须经过两道工序：先用机器B1 制造，后由机
5、器B2包装。每台产品的利润和加工 时间见表2-3。在下周内，机器B1和B2分别可以 使用45小时和6小时。问怎样安排下周的生产任 务，才能使所获利润最大？,解：建立数学模型 设：在下周产品A1和 A2分别生产 x1 合和 x2 合，所获利润为 y 百元。例2的数学模型为：,表 2 - 3,最大化纯 整数规划,其中：“ xk为整数 ” ,称为整数条件。,一般地，可把整数规划的数学模型写为：,整数规划问题及其数学模型一律简称为整数规划；整数规划删去整数条件之前和之后，分别称为原整数规划和相应线性规划。,按照四舍五入的规则，使相应线性规划的最优解整数化，在通常情况下，不能作为原整数规划的最优解。这可
6、以从两个方面来说明：,其一、相应线性规划的最优解化整后，已经不是原整数规划的可行解，当然也就不可能是它的最优解。,其二、相应线性规划的最优解化整后，虽然是原整数规划的可行解，但是有可能不是它的最优解。,例2是最大化纯整数规划，其相应线性规划为：,下面求解这个相应线性规划。我们采用图解法。,并且最优解是：(x1, x2)=（2.25, 3.75）。按照四舍五入的规则，将这个最优解整数化，就得到：(x1, x2)=（2，4）。它对应于点D，而点D却位于可行域R 之外，因此,D（2，4）不是例2的可行解。从而，D（2，4）也不可能是例2的最优解。容易断定，点 A（0，5）才是例2的最优解。,图解法:
7、,相应线性规划的可行域R为图中的四边形OABC，,5x1 +9 x2 = 45,x1 + x2 =6,B(2.25, 3.75),D(2, 4),最优解 A ( 0, 5 ),整数规划常用的解法是分枝定界法和割平面法。一旦遇到仅含两个决策变量的情况，可以采用图解法，其计算方法与线性规划图解法大同小异，就不再赘述。,求解整数规划不宜采用枚举法。,第二节 分 枝 定 界 法,分枝定界法可以用来求解纯整数规划和混整数规划，它是整数规划的常用解法。,分枝定界法可以划分为三步。现就每 一步的主要特征、理论依据和具体作 法说明如下：,第一步,第一步的具体作法是：首先，删去整数条件，把原整数规划化成相应线性
8、规划。其次，求解相应线性规划。最后，如果相应线性规划的最优解也是原整数规划的最优解，那么整个计算过程即告结束；否则，便转入第二步。,实现放宽之后，能够得到三个结论：原整数规划的可行域真包含于相应线性规划的可行域。不失一般性，单就最大化问题而言（下同），原整数规划的最优值不大于相应线性规划的最优解。若相应线性规划的最优解满足原整数规划的整数条件，则它也是原整数规划的最优解。,主要特征就是放宽。指通过删去整数条件，把原整数规划化成相应线性规划。,第二步 主要特征是分枝。从相应线性规划的最优解中，任意选择一个不满足原整数规划整数条件的决策变量xj=bj。以使相应线性规划增加一个约束条件；xj小于bj
9、的最大整数（或xj大于bj的最小整数），因而得到两个新的线性规划，称为分枝。其中每个新的线性规划，统称为枝。,经过分枝之后，就有如下结论：原整数规划的可行域真包含于两枝可行域的并集。原整数规划的最优解不大于两枝最优值的最大值。,第二步的具体作法是：先列出两枝各自的数学模型，后计算每枝的最优解和最优值。,第三步 主要特征就是定界，由各枝的最优值中选最大值，称为定界。而该最大值，称为界。最优值称为界的枝，称为界枝。,完成定界之后，即可得到这样的结论：若界枝的最优解满足原整数规划的最优条件，则它也是原整数规划的最优解。,第三步的具体做法为：进行定界，找出界枝。若界枝的最优解就是原整数规划的最优解，则
10、计算过程便告结束；否则，回到第二步。,解：它是例2的数学模型，并且属于最大化纯整数规划。为便于叙述，我们将其记作A。现在利用分枝定界法求解之。,例3 利用分枝定界法求解：,放宽：由A得到相应线性规划，记作B。,采取图解法或单纯形法，求得B的 最优解（x1 , x2）=（ 2.25 , 3.75 ） 最优值 ymax = 41.25。,B的最优解不满足A的整数条件，所以它并非A的最优解。,分枝：由B的最优解中，选择决策变量x2=3.75，按照既定的原则写出B的两枝：,把它们依次记作B1和B2。 解B1得：最优解（x1，x2）=（3，3）,最优值 ymax= 39解B2得：最优解（x1，x2）=（
11、1.8,4）,最优值 ymax= 41,已完成的求解过程和所得到的计算结果可用框图来表示，见下图。,定界：由图可知。界为max 39，41 = 41。于是界枝是B2。但是，B2的最优解不满足A的整数条件，从而它不是A的最优解。因此，应当再次分枝。 第二次分枝：由B2的最优解中，选择决策变量 x1= 1.8，写出B2的两枝：,解B21得：最优解（x1，x2）=（1，4），最优值ymax=40. 不难判断， B22无可行解。,至此，已完成的求解过程和所得到的计算结果运用框图来表示，如图所示：,第三次分枝：,解B211得：最优解（x1, x2）=（1, 4）,最优值 ymax = 37。 解B212
12、得：最优解（x1, x2）=（0, 5）,最优值 ymax = 40。,第二次定界：由上图可知，界为max 39， 365/9 = 365/9 。界枝为B21. 因为B21最优解不满足A的整数条件，不是A的最优解。,由B21最优解中，选择变量,把B21分成两枝：,现在，已完成的求解过程和所得到的计算结果见下图：,第三次定界：由上图可知，界为max 39, 37, 40 = 40. 所以，界枝是B212。由于B212的最优解满足A的整数条件，它一定也是A的最优解。于是，原整数规划的最优解为： （x1，x2）=（0，5），最优值 ymax= 40。 例3是一个利用分枝定解法求解纯整数规划问题，其基
13、本步骤也适用于混整数规划问题。,例4 某卫生防疫站准备做100套钢架。每套钢架均由长为2.9米、2.1米和1.5米的钢管各一根所组成。已知原料长7.4米。如何下料方能使原料最省？,解：原料的下料方式如下表。,设按照方式 Aj下料的原料有 xj 根（j =1， 2，8）；所用原料为 y 根。于是，本下料问题的数学模型是：,这是最小化纯整数规划，利用分枝定界法解之。,采取单纯形法来求解。可知最优解（x1，x2，x3，x4，x5，x6，x7，x8）=（40，20，0，0，0，30，0， 0）。由于它是整数解，它必定也是例4的最优解。这表明，只须采用下料方式A1 、A2 和 A6，而且所用原料分别为40根、20根和30根，可使所用原料最省。例4的求解过程说明，当利用分枝定界法时，有时仅仅经历“放宽”这一步，就能够求得最优解。,放宽:得到相应线性规划为：,例4还可以采用另外的目标函数，即100套钢架的料头总长度为 y 米。数学模型是：,#,小 结,一、整数规划的基本概念,二、分枝定界法解整数规划,纯整数规划、混整数规划,分枝定界法分三步：,第一步 放宽第二步 分枝第三步 定界,
