文档介绍：典型的整数线性规划问题
一、背包问题
有一徒步旅行者要带一背包,设对背包的总重量限制为b千克,今有n种物品可供选择,已知第j种物品每件重量为aj千克,使用价值为cj,问旅行者应如何选取这些物品,使得总价值最大?
整数线性规划及0-1规划
令xj表示第j种物品的装入件数
模型建立
整数线性规划模型(IP)
典型的整数线性规划问题
二、投资问题
今有一笔资金,设金额为b个单位,可以投资的发展项目有n个,要求对每个发展项目的的投资单位数必须是非负整数,且只考虑两种决策:要么投资,要么不投资,若对第j个发展项目投资,所花资金为aj。已知对第j个发展项目每投资一单位可获利cj个单位,问如何投资才能使总利润最大?
令xj表示对第j个发展项目的投资数量
模型建立
整数线性规划0-1模型(IP)
如果生产某一类型汽车,则至少要生产80辆, 那么最优的生产计划应作何改变?
例1 汽车厂生产计划
汽车厂生产三种类型的汽车,已知各类型每辆车对钢材、劳动时间的需求,利润及工厂每月的现有量。
小型中型大型现有量
钢材(吨) 3 5 600
劳动时间(小时) 280 250 400 60000
利润(万元) 2 3 4
制订月生产计划,使工厂的利润最大。
整数线性规划及0-1规划
设每月生产小、中、大型汽车的数量分别为x1, x2, x3
汽车厂生产计划
模型建立
小型中型大型现有量
钢材 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,。
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+400x3<60000
end
gin 3
OBJECTIVE FUNCTION VALUE
1)
VARIABLE VALUE REDUCED COST
X1 -
X2 -
X3 -
模型求解
IP 结果输出
其中3个子模型应去掉,然后逐一求解,比较目标函数值,再加上整数约束,得最优解:
方法1:分解为8个LP子模型
汽车厂生产计划
若生产某类汽车,则至少生产80辆,求生产计划。
x1,x2,, x3=0 或80
x1=80,x2= 150,x3=0,最优值z=610
LINDO中对0-1变量的限定:
int y1
int y2
int y3
方法2:引入0-1变量,化为整数规划
M为大的正数,可取1000
OBJECTIVE FUNCTION VALUE
1)
VARIABLE VALUE REDUCED COST
X1 -
X2 -
X3 -
Y1
Y2
Y3
若生产某类汽车,则至少生产80辆,求生产计划。
x1=0 或80
x2=0 或80
x3=0 或80
最优解同前