整数线性规划

《整数线性规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、整数线性规划数学建模与数学实验实验目的实验内容2.掌握用数学软件求解整数线性规划问题.1.了解整数线性规划的基本内容.2.用数学软件包MATLAB求解整数线性规划问题.4.实验作业.3.用数学软件包LINGO求解整数线性规划问题.1.整数线性规划整数规划整数规划问题与模型整数规划算法计算软件应用案例整数规划问题实例特点模型分类例3某储蓄所每天的营业时间为上午9：00到下午的17：00，根据经验，每天不同时间段所需要的服务员的数量为：时间段9－1010－1111－1212－1313－1414－1515－1616－17数量43465688储蓄所

2、可以雇用全时和半时两类服务员，全时的报酬是100元每天，中午必须在12：00到14：00之间休息1个小时；每天雇用不超过3名的半时服务员，必须连续工作4小时，报酬为40元问：1）该储蓄所应该如何雇用全时和半时两类服务员？2）如果不雇用半时服务员，每天费用增加多少？3）如果雇用半时服务员的数量没有限制，可减少多少费用？X1，X2分别为全时服务员在12：00－13：00和13：00－14：00安排休息的人数，Y1，Y2，Y3，Y4，Y5，分别为9：00，10：00，11：00，12：00，13：00，开始工作的半时服务人员Example3.m如

3、果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234制订月生产计划，使工厂的利润最大。设每月生产小、中、大型汽车的数量分别为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.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=

5、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<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDC

6、OSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解IP结果输出特征—变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质—可行域是离散集合线性整数规划模型一般整数规划模型0-1整数规划模型混合整数规划模型一般整数规划模型0-1整数规划模型混合整数规划模型算法与线性规划的关系分支定界算法割平面算法近似算法与线性规划的关系整数规划放松的线性规划可行解是放松问题的可行解最优值大于等于放松问题的最优值注释最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近

7、整数解整数可行解远多余于顶点，枚举法不可取算法思想算法步骤算例割平面算法算法思想由放松问题的可行域向整数规划的可行域逼近方法—利用超平面切除要求整数解保留放松问题最优值增加割平面生成方法条件--保留整数解删除最优解整数可行解最优基可行解正则解算法步骤求放松问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯性表中加入一列利用对偶单纯性算法求最优解算例(1,1.5)分支定界算法算法思想算法步骤算例注释算法思想隐枚举法求解放松问题最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比界好分支边界分支舍弃分支的方法定界当前得到的最好整数

8、解的目标函数值分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则删除该分支其中无最优解非整数解且目标值小于原有最好