数学建模-第五章整数规划

《数学建模-第五章整数规划》由会员分享，可在线阅读，更多相关《数学建模-第五章整数规划（30页珍藏版）》请在金锄头文库上搜索。

1、 第五章 整数规划运 筹 学Operations Research 第五章 整数规划在 LP 问题的讨论中，有些最优解是小数 . 但对于某些具体问题常有要求最优解是整数( 即整数解) . 如决策变量为机器的台数、人数、车辆数 etc. 如果在问题中所有决策变量有整数限制，称为 纯整数规划( Pure IP ) 或 全整数规划 ( All IP )；如果在问题中仅部分决策变量有整数限制，称为 混合整数规划( Mixed IP ) ；如果在问题中决策变量仅取 0 、1，称为 0-1 (整数) 规划 .Integer Programming第五章 整数规划1 整数规划问题及其数学模型2 整数规划的解

2、法3 整数规划的应用举例1 整数规划问题及其数学模型1 整数规划问题及其数学模型货 物每箱体积 （m3）每箱重量 （kg）每箱利润 （百元）甲5220乙4510托运限制2413Example 1 （装载问题） 某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运限制如表，问两种货物各托运几箱，可获利润最大？Solution: 设 x1、x2 分别为甲、乙两种货物托运箱数.则这是一个 Pure IP 问题.第五章 整数规划Example 2 （工厂选址问题） 现准备从 A1、A2、A3 三个地点中选择两个开设工厂，工厂建成后它每月的 产量 ai (i =1,2,3)、三个客户 B1

3、、B2、B3 每月的需求量bj (j =1,2,3) 及 Ai 至客户 Bj 的单位运价 cij 见表. Bj AiB1B2B3aiA145370 A223480 A364590bj406045已知三工厂每月的经营费用 di (与产量无关)分别为 100、90、120 .问如何选址使每月经营和运输费用最低 .Solution:因为只有三个厂址选两个， ，所以简单的方法是任取两个厂用运输问题求解，再加上每月的经营费用比较即可.设选地点 Ai 开设工厂 否则 i = 1,2,3 ； xij 为Ai 开设工厂时，从 Ai 至 Bj 的运量显然如果 Ai 处开设工厂，则运量满足：不开设呢？客户端需求满

4、足：目标（每月的费用）：这是一个 Mixed IP 问题.可用于设计分配系统、新生活小区的设置 etc.1 整数规划问题及其数学模型在 Ex.2 中，引进 01 变量给出了在 n 件任务中,选择 j 项的约束又用 来刻画不设第 i 项任务，则 xij j = 1n 都不起作用，为零.可应用于选择性 约束条件中某工厂生产第 j 种产品的数量为 xj ( j =1,2,3) 其使用的材料在甲、乙中选择一种，其消耗约束分别为：其他资源约束条 件未列出引进 01 变量 y 选择材料甲选择材料乙M 为充分大的 正数一般地，假定要在 p个约束条件 中至少要选择 q 个约束条件得到满足，可引进0-1变量 y

5、第五章 整数规划Example 3 （背包问题）假设有人要出发旅行，考虑带七种物品，每件物品的重量与价值如表. 现在假设他最多带 35kg 物品，问该带哪几件物品使总价值最大？物品重量 aj价值 cj1 3 122 4 123 3 94 3 155 15 906 13 267 16 112Solution:如果带第 j 件物品否则 j = 17这是一个 0-1 规划问题.一般整数规划中的变量 x , 也可用 0-1 变量替代，如0x15 ，x=x020+x121+x222+x323 其中 x0,x1,x2,x3 为0-1 变量 .1 整数规划问题及其数学模型参见 Ex.1, 去掉整数约束，得舍

6、入化整o 1 2 3 4 5 x14321x2由图解法得最优 解为：x1= 4.8, x2= 0 Zmax = 96显然，x1 不是整数. 是否可以根据化整的原问题的解？x1=5、x2=0 不是可行解， x1=4、x2=0 Z=80 . 但是 x1=4、x2=1 也可行 且 Z=90 .所以，“舍入化整”的结果：1、化整后未必可行；2、即使是可行解，也未必是最优解； 3、用这个方法即使能得到最优解，但如果有n 个变量，则取舍方案有 2n 种，计算量也是很大的.Go back第五章 整数规划o 1 2 3 4 5 x14321x22 2 整数规划的解法整数规划的解法有人在研究在建立模型中，什么条

7、件下 LP 问题的解一定是整数解？ 如： 运输问题从 Ex.1 的讨论，可得到一些启迪1、是否能在 LP 的约束区域中, 切去 n 块不含整数解的可行域使整数解作为顶点，则 LP 的最优解即为整数解 ；如增加约束 x14, 则 LP 问题的解即为整数解;2、在 LP 的可行域中，整数点不多，（12个）是否可以用穷举法.2 整数规划的解法一、割平面法1959年由 R.E.Gomory 首先提出，从此使 IP 逐渐形成为一个独立的运筹学分支. 割平面法的实质是用解 LP 问题的方法求解 IP 问题；割平面法的基本思想是通过对 LP 问题的求解，如果最优解是整数解，则就是 IP 的解；否则设法对 L

8、P 问题增加约束(割平面)，把 LP 问题的可行域中去掉一部分不含整数解的，再求 LP 问题，反复进行 .割平面法的关键在于如何寻找适当的切割约束条件.用割平面法求解 IP 问题常常会计算量大、收敛速度慢的情况，但在理论上是重要的，被认为是 IP 的核心.第五章 整数规划二、分支定界法分支与定界法的基本思想是对有约束条件的最优化问题的所有可行解（其数目为有限集）空间适当地进行 搜索 .具体执行时，把可行解空间不断分割为越来越小的子集（称为分支），并确定每个分支内的解值的下界或上界（称为定界）. 在每次分支后，对凡是界超出已知可行解值的子集被剪去，从而不断缩小搜索范围. 这个过程一直进行到找出最

9、优解为止，该可行解的值不大于或不小于任何子集的界 .优点：1、适用面广 2、可检查较少的解（运 气好）3、可获得最优解缺点：本质是穷举，复杂性大于穷举法2 整数规划的解法设如果 则称问题（2）是问题（1）的松弛问题.Note : 1、松弛问题未必比原问题难解；如：整数规划与线性规划；TSP 与指派问题 etc.如： A：寻找全国18 岁百米最快的运动员.B：寻找全国所有百米最快的运动员.显然，B 问题是 A 问题的松弛问题，且B 问题更易解 .2、如果松弛问题易解，则先解松弛问题是有益的 .1）设 x0 是松弛问题的最优解，且 则原问题已解2）即使 给出了原问题最优值的界 f(x0) .x0B

10、ABAx0第五章 整数规划分枝与定界法为什么能少检查一些解？B10sB1B210.2s *10sB3B410.3s *几点注意： 确定问题（子问题）的最优值的界通常是通过求解松弛问题，用松弛问题的解作为界，也可 以用启发式算法得到 .Note : : 松弛问题选择的原则1 1、松弛问题要与原问题的最优值尽量接近；2 2、松弛问题要尽量容易解 .这两个原则不易统一，所以可选择不同的松弛问题2 整数规划的解法 划分方法的选择原则是希望分出来的子问题容易被查清，可加快计算. 选哪个活问题先检查1 1、先检查最大上界（极大化问题）的活问题优点：检查子问题较其他规则为少；缺点：计算机储存量较大 . .2

11、 2、先检查最新产生的最大上界的活问题优点：计算机储存量较少 ；缺点：需要更多的分支运算 . .选择的不同，提供了发挥的余地分枝与定界法的重要在于它提出了一类新的思路（隐枚举法），使得许多原来不好解决的问题有了解决的可能性. （具有普适性）第五章 整数规划Example 4 用分支定界法求解如右 IP 问题Solution:解松弛问题 P0 得：x1=2.25、x2=3.75 Zmax=41.25去掉整数约束为 原 问题的松弛问题41.25是原问题最优值的上界 进行分支，任选一个不是整数的变量,如取 x2 则可认为最优解 x24 或 x23 . 原问题分为两个子问题 . 3x24 之间无整数解

12、0 1 2 3 4 5 6 7 8 9 x1x254321P1P2再分别求解两个松弛问题 P1、P2P0x1=2.25 x2=3.75 Z0=41.25P1(x23)P2（x24）x1=3、x2=3 Z1=39 *x1=1.8、x2=4 Z2=41P3（x12）P4 (x11) 不可行 *x1=1、x2=40/9 Z4=365/9P5（x24）P6 (x25)x1=1、x2=4Z5=37 *x1=0、x2=5Z6=40 *此时已没有活问题，所以最优解为 x1=0、x2=5 Zmax=40 .2 整数规划的解法Example 5 （投资方案的最优选择）背包问题可以看成为一个一次性的投资问题，简单

13、的扩展：1、分几次投资；2、虽然一次性投资，但不同的项目有一些政策上的限制 etc.某公司欲对三个项目进行投资，根据预算四年内的投资额、三个项目每年所需投资额以及所创利润如表. 问应对哪几个项目进行投资，可获利最大？投资 年度项目投资 额度 A1A2A310425251273403745136回报 利润20816Solution:如果对项目Aj 投资否则 j = 13设对于0-1 规划的求解，首先会 想到枚举法，但变量取0、1的所 有组合有 2n . 是否能设计一些方法，只检查所有组合的一部分就 求得最优解，即隐枚举法.分支定界法是 一种隐枚举.给出一个重要思想: 设门槛 (1、可行性 2、目

14、标函数值)第五章 整数规划(x1 x2 x3)约束条件Z值(0 0 0)(0 0 1)(0 1 0)(0 1 1)(1 0 0)(1 0 1)(1 1 0)(1 1 1)0 16 8 20 28 (x1 x2 x3)约 束 条 件Z值 (0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1)增加一个判别 A , 目标函数值小于已知可行解的值，则不必继续计算 .A 0 16 20 28 可以改进吗？(x2 x3 x1)约 束 条 件Z值 (0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1)A 0 20 28 还有想法吗？Go back第五章 整数规划3 3 整数规划的应用举例整数规划的应用举例Example 6 （人员时间安排问题）为了尽可能有效地利用劳动力，有必要对一天各个不同时刻需要人员的情况作一分析，特别是在一些 大型服务性机构中，顾客的需要是重复性的，但不同 时刻之间需要的服务量是有显著差别的. 如：电话接线员、公交乘务员