运筹学课件ch5整数规划.ppt

《运筹学课件ch5整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第五章整数规划IntegerProgramming四个目标:熟悉IP规划适用的应用领域掌握建立好的模型化技巧使用EXCEL获得模型的结果说明与分析结果报告整数规划——变量只能取整数的规划问题。当变量只能取0或1两个值，称0-1规划。整数规划分类：纯整数规划——全部变量为整数。混合整数规划——部分变量为整数。典型的整数线性规划问题一、背包问题有一徒步旅行者要带一背包，设对背包的总重量限制为b千克，今有n种物品可供选择，已知第j种物品每件重量为aj千克，使用价值为cj，问旅行者应如何选取这些物品，使得总价值最

2、大？令决策变量xj表示第j种物品的装入件数模型建立整数线性规划模型(IP)二、投资场所选址问题(0-1整数规划Binaryplanning)计划在东、西、南三个区开设若干商业网点，拟在A1，…，A77个地点中选择。规定：东区在A1，A2，A3中至多选2个，西区在A4，A5中至少选1个，南区在A6，A7中至少选1个。已知在Ai建点需投资bi，可获利ci，现共有资金为B。问应如何布局可使总利润最大？分析：东区在A1，A2，A3中至多选2个怎样表示？问2:如果生产某一类型汽车，则至少要生产80辆，那么最优的生产

3、计划应作何改变？例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234问1:制订月生产计划，使工厂的利润最大。整数线性规划设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解3）模型中增加条件：x1,x2,x3均为整数

4、，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=6

5、5，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP的最优解x1=64，x2=168，x3=0，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTION

6、VALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解IP结果输出四舍五入是一种达到整数解的方式,但总是不能产生最佳解.一个很重要的观念是对于相同的LP问题,一个整数规划解不比LP解要好整数问题解总是较差,才会产生较高的成本及较低的利润整数线性规划求解----分支定界法分支定界法是枚举法基础上的改进。分支定界法的关键是分支和定界。思路：利用其松弛问题的最优

7、解（值）来分支定界。一部分或全部决策变量取整数值的规划问题——整数规划整数规划中不考虑整数条件是对应的规划问题——该整数规划的松弛问题例：求解整数规划问题A且为整数松弛问题B设问题A的最优目标函数值为。整数规划问题A初始上界即松驰问题的最优值图解法分析：、、、、、、、、、、、0123456789108-7-6-5-4-3-2-1-B不是问题A解但图解法分析：012345674321图解法分析：012345674321图解法分析：432101234567是问题A解但不是问题A解而剪枝图解法分析：012345

8、674321分支定界的全过程：分支定界的全过程：分支定界法的求解步骤：步骤1、整数规划问题为A，其松弛问题为B，设为问题A的初始下界（min问题为上界）步骤2、求解问题B，有三种情况：（a）B无可行解，此时问题A也无可行解，停止。（b）B有可行解且为整数，则问题B的最优解即是问题A的最优解，停止。（c）B有可行解但不是整数，设目标函数值为它是问题A的上（下）界，转入步骤3。步骤3、分支、定界。步骤4、比较、剪枝。其中3个子模型