第三章 整数规划模型08-5.ppt

第三章 整数规划 3.1 整数规划简介 要求所有 xj 的解为整数，称为纯整数规划 要求部分 xj 的解为整数，称为混合整数规划 对应没有整数解要求的线性规划称之为松弛问题 整数规划的解是可数个的，最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解 3.2 整数规划问题及其数学模型 1、生产计划问题 例3.2.1 某工厂生产A1、A2两种产品，产品分别由B1、B2两种部件组装而成。每件产品所用部件数量和部件的产量限额以及产品利润如下表所示，应如何安排A1、A2的产量，该厂才能获得最大利润？ 3.2 整数规划问题及其数学模型 2、投资项目选择问题 例3.2.2 某单位有5个拟选择的投资项目，其所需投资额与期望收益如下表所示。由于各项目之间有一定联系，A、C、E之间必须选择一项，且仅需选择一项；B和D之间需选择且仅需选择一项；C的实施必须以D的实施为前提条件。该单位共筹集资金15万元，应选择哪些项目投资，使期望收益最大？ 3.2 整数规划问题及其数学模型 解：考虑到有的项目有可能被选中，也有可能不被选中，设决策变量xi(i=1,2,3,4,5)分别表示项目A、B、C、D、E，且定义 3.2 整数规划问题及其数学模型 目标函数为期望收益最大，可表示为 max Z=10x1+8x2+7x3+6x4+9x5 因此，此问题的数学模型为 3.2 整数规划问题及其数学模型 3、指派问题 例3.2.3 现有A1、A2、A3、A4四人，每人都能完成工作B1、B2、B3、B4四项中的一项。下表列出了他们完成各项工作所需的时间。如果每项工作需安排且仅需安排一人完成。问如何安排四人可使完成四项任务所花费的总时间最少？ 3.2 整数规划问题及其数学模型 解：由于每项工作需安排一人且仅需一人去完成，所以，设xij表示Ai去做Bj工作（i,j=1,2,3,4），且 3.3 分枝定界法 3.3.1 思路与解题步骤 只解松弛问题, 通过分枝， 逐步缩小目标函数的上下界之差 1、在全部可行性域上解松弛问题 若松弛问题最优解为整数解，则其也是整数规划的最优解 2、分枝过程 若松弛问题最优解中某个 xk=bk 不是整数，令 ? bk ? 为 bk 的整数部分 构造两个新的约束条件 xk? ? bk ? 和 xk? ? bk ?+1，分别加于原松弛问题，形成两个新的整数规划 3、求解分枝的松弛问题 — 定界过程 设两个分枝的松弛问题分别为问题 1 和问题 2 ，它们的最优解有如下情况 表3.3.1 分枝问题解可能出现的情况 3.3.2 分枝定界法举例 例3.3.1 3. 解问题（1）的松弛问题，问题（2）暂时记录下来. 问题（1）的松弛问题最优解为 x1=2, x2=2.67, Z=83.3 由于x2不为整数，对问题（1）分别增加新的约束条件x2 ? 2. x2 ? 3，分枝为两个子问题，它们的松弛问题如下： 4. 解问题（3）的松弛问题，问题（4）暂时记录下来. 问题（3）的松弛问题最优解为 x1 =2, x2 =2, Z=70 由于解为整数，问题（3）不再分枝，目标函数新的下界为Z=max{0,70}=70. 5.对记录下来的问题， 依“后进先出”的原则进行求解. 对问题（4）进行求解，最优解为 x1 =1, x2 =3, Z=75 由于解为整数，问题（4）不再分枝，目标函数新的下界为Z=max{70,75}=75. 6.对问题（2）进行求解，最优解为 x1 =3, x2 =1.75, Z=80.由于解x2不为整数，并且Z=80 Z=75.对问题（2）进行分枝,增加新的约束条件 x2 ? 1. x2 ? 2，分枝为两个子问题，它们的松弛问题如下： 7.对问题（5）进行求解，最优解为 x1 =3.5, x2 =1, Z=72.5 由于Z=72.5 Z=75, 问题（5）不再分枝.8.对问题（6）进行求解.无可行解，问题（6）不再分枝. 由下图可知，所有分枝已查清. 原整数规划问题的最优解为 x1 =1, x2 =3, Z=75. 3.3.2 分枝定界法举例 例3.3.2 用分枝定界法求解混合整数规划： 3.4 0-1规划的解法 3.4.1 完全枚举法 基本思路：将全部变量取0或1的所有组合列出，然后，再逐个检查这些组合是否可行，并求出最优解。在此过程中，可利用增加并不断修改过滤条件的办法，减少计算量。 例3.4.1 用完全枚举法求解0-1规划问题： 例3.4.1 解 （1）列出变量所有的解(x1,x2,x3)，共有23=8个： （0，0，0）；（0，0，1）；（0，1，0）；（0，1，1）； （1，0，0）；（1，0，1）；（1，1，0），（1，1，1）。 （2）增设过滤条件。用