文档介绍：典型的整数线性规划问题一、背包问题有一徒步旅行者要带一背包,设对背包的总重量限制为 b 千克,今有 n种物品可供选择,已知第 j种物品每件重量为 aj千克,使用价值为 cj,问旅行者应如何选取这些物品, 使得总价值最大? 整数线性规划及 0-1规划令xj表示第 j种物品的装入件数模型建立整数线性规划模型(IP) 11 . . 0 n j j jn j j jj Max z c x s t a x b x ????????且为整数(j=1,2, ,n) 典型的整数线性规划问题二、投资问题今有一笔资金,设金额为 b个单位,可以投资的发展项目有n个,要求对每个发展项目的的投资单位数必须是非负整数,且只考虑两种决策:要么投资,要么不投资,若对第j个发展项目投资,所花资金为 aj。已知对第 j个发展项目每投资一单位可获利 cj个单位,问如何投资才能使总利润最大? 令xj表示对第 j个发展项目的投资数量模型建立整数线性规划 0-1模型(IP) 11 . . 0 n j j jn j j jj Max z c x s t a x b x ????????或1(j=1,2, ,n) 如果生产某一类型汽车,则至少要生产 80辆, 那么最优的生产计划应作何改变? 例1 汽车厂生产计划汽车厂生产三种类型的汽车,已知各类型每辆车对钢材、劳动时间的需求,利润及工厂每月的现有量。小型中型大型现有量钢材(吨) 3 5 600 劳动时间(小时) 280 250 400 60000 利润(万元) 2 3 4 制订月生产计划,使工厂的利润最大。整数线性规划及 0-1规划设每月生产小、中、大型汽车的数量分别为 x1, x2, x3 321432xxxz Max ??? 600 .. 321???xxxts 60000 400 250 280 321???xxx0,, 321?xxx 汽车厂生产计划模型建立小型中型大型现有量钢材 3 5 600 时间 280 250 400 60000 利润 2 3 4 线性规划模型(LP) 模型求解 3)模型中增加条件: x1, x2, x3 均为整数,重新求解。 OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 X3 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 结果为小数,怎么办? 1)舍去小数:取 x1=64 , x2=167 ,算出目标函数值 z=629 , 与 LP 最优值相差不大。 2)试探:如取 x1=65 , x2=167 ; x1=64 , x2=168 等,计算函数值 z,通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么? IP可用 LINDO 直接求解整数规划(Integer Programming, 简记 IP) “ gin 3 ”表示“前3个变量为整数”,等价于: gin x1 gin x2 gin x3 IP 的最优解 x1=64 , x2=168 , x3=0 ,最优值 z=632 max 2x1+3x2+4x3 st +3x2+5x3<600 280x1+250x2+40