整数规划（运筹学）.ppt

* * 例5模型为 * * 整数规划的计算方法 软件实现 例5在LINDO中的实现为 * * 资源 小号容器 中号容器 大号容器 限制 金属板(吨) 2 4 8 500 劳动力(人月) 2 3 4 300 机器设备(台月) 1 2 3 100 利润 4万元 5万元 6万元 生产固定费用 100万元 150万元 200万元 例6：某厂打算生产三种型号的容器，使用的资源情况、利润如下： 其中固定费用是指，只要生产，不管数量多少，都要投入的费用。问题是三种容器要不要投产、产多少？ * * 求解： 假设计划生产小、中、大号容器的数量分别为x1、x2、x3 是否生产的逻辑变量为y1、y2、y3，取值1表示生产，取值0表示不生产, 那么利润函数为 金属板的限制为 劳动力的限制为 机器设备的限制为 xi与yi之间的关系 * * 例7.投资场所的选择 在10个位置Ai当中选择若干个, 总投资额不超过720万元, 其中A1, A2, A3最多选两个; A4, A5至少选一个; A6, A7至少选一个; A8, A9, A10至少选两个. 投资额及利润见表8—2. 选中的有收益(费用), 未选中的则没有. A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 投资额Ci 100 120 150 80 70 90 80 140 160 180 利润Ri 36 40 50 22 20 30 25 48 58 61 * * 假设逻辑变量xi=1表示选用Ai, xi=0表示不选用Ai，那么 相应的投资额(ci xi)，利润为(pi xi) x1+x2+x3=2 x6+x7=1 x4+x5=1 x8+x9+x10=2 整数约束 总投资额约束 总利润最大 0-1约束 x1, x2, ……, x10为0-1整数 阅读材料 参考书 P80-89，第4.3节 * * * * * * * * * * 前两章内容回顾和总结 1，线性规划模型 2，线性规划的建模实例分析 3，线性规划的求解－图解法和Lindo 4，对偶问题 5，敏感性分析 * * 总结1： 目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。 线性规划问题（LP问题）的共同特征： 每一个问题变量都用一组决策变量（x1, x2, …, xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 若LP问题有最优解，则要么最优解唯一，要么有无 穷多最优解。 * * 总结2: LP问题 有可行解 有最优解 唯一解 无穷多解 无最优解（可行域为无界） 无可行解（无解） 规律1： * * 规律2： 线性规划问题的可行域为一凸集 线性规划问题凸集的顶点个数是有限的 最优解肯定可在凸集的某顶点处达到 * * 总结3： 线性规划问题的标准型 1. 标准型 * * 2. 所有LP问题均可化为标准型 * * 3，标准型LP问题的解 * * 线性规划对偶的一般形式 * * 敏感性分析 很多软件可以生成目标函数系数或者约束右端参数的灵敏度报告，可以很快计算出最优域 ； 运用目标函数系数的百分百法则，可进一步方便地检验所有参数同时变动的情况 ； 通过影子价格分析，发现改变决策会产生的影响，从而为管理层更好的决策提供指导 ； 用约束右端值变动的百分百法则来判断变动的幅度。 * * 第四章 整数规划 整数规划问题的提出 整数规划的求解-分支定界法 0-1规划建模 * * 什么时候需要整数解？ 得到小数解时如何处理呢？ 整数解 你有什么绝招吗？ * * 舍入解的挑战 舍入解可能不是可行解 舍入解与最优解离很远 可能有多个舍入解出现 * * 第一节.整数规划问题的提出 一、整数规划的一般形式 1、实例： 例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5－1： 货物 体积 每箱（米3） 重量 每箱（百斤） 利润 每箱（百元） 甲 乙 5 4 2 5 20 10 托运限制 24 13 问两种货物各托运多少箱，可使获得的利润为最大？ * * 2、整数规划一般形式 解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为： * * （2）求解方法方面 3、与线性规划问题的区别 在例1中， 此IP问题的最优解(值)为： 线性规划问题的最优解(值)为： （1）放松整数约束的整数规划就是线性规划 * * 例2 做图分析例1的最优解(直观) IP 问题可行域不为凸集