文档介绍：第五章整数规划模型
汽车生产
接力队选拔和选课策略
y
如果生产某一类型汽车,则至少要生产80辆, 那么最优的生产计划应作何改变?
例1 汽车厂生产计划
汽车厂生产三种类型的汽车,已知各类型每辆车对钢材、劳动时间的需求,利润及工厂每月资源的现有量。
小型中型大型现有量
钢材(吨) 3 5 600
劳动时间(小时) 280 250 400 60000
利润(万元) 2 3 4
制订月生产计划,使工厂的利润最大。
汽车生产
设每月生产小、中、大型汽车的数量分别为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
最优解同前
NLP虽然可用现成的数学软件求解(如LINGO, MATLAB),但是其结果常依赖于初值的选择。
方法3:化为非线性规划
非线性规划(Non- Linear Programming,简记NLP)
实践表明,本例仅当初值非常接近上面方法算出的最优解时,才能得到正确的结果。
若生产某类汽车,则至少生产80辆,求生产计划。
x1=0 或80
x2=0 或80
x3=0 或80
分派问题
接力队选拔和选课策略
若干项任务分给一些候选人来完成,每人的专长不同,完成每项任务取得的效益或需要的资源就不同,如何分派任务使获得的总效益最大,或付出的总资源最少。
若干种策略供选择,不同的策略得到的收益或付出的成本不同,各个策略之间有相互制约关系,如何在满足一定条件下作出决择,使得收益最大或成本最小。
丁的蛙泳成绩退步到1’15”2;戊的自由泳成绩进步到57”5, 组成接力队的方