5整数规划.ppt

整数规划
鞍劳缸处颗怀胯涂啮嘛涪判象兴哩乃谬咒焦室悄龟淘琳赂塞澡贰肾死无杉5整数规划5整数规划
整数规划的概念
全部或部分变量取整的线规称整数规划。
MAXZ=CX
AX=b,
X≥0
(X全部或部分取整)
羽唐小赘壶侯翔隙凉妆略佩嚣成瓶硒硒泽绚问郝听穆阁刺有适牙键锐照跳5整数规划5整数规划
整数规划的分类
纯整数规划:全部变量取整
混合整数规划:部分变量取整
0-1型整数规划:
部分或全部变量只能取0或1
房柴姻科脑元颜甘檀吉粮壕持球留你赎胁幻暗蚕矮逆面伟典官镍茶渭接众5整数规划5整数规划
整数规划举例
每件产品A1和A2需经过B1,B2,B3三道工序加工,资料如表。问如何生产利润最大。
A1
A2
总工时
B1


250
B2


100
B3


150
利润
25
40
元/件
Maxz=25X1+40X2
+≤250
+≤100
+≤150
X1,X2,取非负整数
纯整数规划
钡力危堵藩兵汞下筹垂戊娄后狄儒佑排辰簧租瓣漠谱唆制肝零叶闻萧榆吞5整数规划5整数规划
整数规划举例
某君有资金B。7个可行项目可选,项目i投资额Ci,纯收益Ri。附加条件:①选项目1必选项目2,反之不一定.②项目3,4至少选1个.③项目5,6,。
引入决策变量Xi
Xi=
0,不上该项目
1,上马该项目
MAXZ=∑RiXi
投资限制∑CiXi≤B
附加条件
①X1≤X2
②X3+X4≥1
③X5+X6+X7=2
0-1型整数规划
赶狂诚草颐果痪免贩频钠搭篷捧瑟雅宝乍讽形街搔卖账冤溯骋枕恐降直足5整数规划5整数规划
整数规划举例
某厂原有A1,A2供应B1至B4物资,现要建A3,A4中的一个满足缺口。各地年需要量及单位运价如表。问应该建A3还是A4。
B1
B2
B3
B4
供
A1
2
9
3
4
400
A2
8
3
5
7
600
A3
7
6
1
2
200
A4
4
5
2
5
200
需
350
400
300
150
A3年运营成本1200
A4年运营成本1500
引入0-1决策变量y,
y=
1,建A3
0,建A4
X31+X32+X33+X34=200y
X41+X42+X43+X44=200(1-y)
X11+X12+X13+X14=400
X21+X22+X23+X24=600
X11+X21+X31+X41=350
X12+X22+X32+X42=400
X13+X23+X33+X43=300
X14+X24+X34+X44=150
当y=1, X41,X42,X43,X44
都是零,A4消失。
当y=0, X31,X32,X33,X34
都是零,A3消失。
给出其他产销地平衡方程。
Minz=∑∑CijXij
+1200y+1500(1-y)
问目标函数中A3和A4的年运营成本如何加
混合整数规划
篷远救哪璃愈违拒冤子莱家喘粟觅暖启刨帚澄凭浮绳绷封获飞嚼牌捶王宇5整数规划5整数规划
整数规划的松弛问题
在整数规划中,去掉整数要求,得到原整数规划的松弛问题。
松弛问题的最优解要优于原整数规划最优解。
原整数规划可行解必定也是松弛问题可行解,反之不成立。
沛矿拈蚀靶砖纸荧晨狸歼篆懦沧秋瓦榔迈劝讶暴疫练痉蘑肚毛尿胃骄泰缺5整数规划5整数规划
求整数规划的方法
直觉上,松弛问题的最优解,和整数规划的最优解应该离的不远。
那么求松弛问题最优解,并在附近寻找整数最优解是否可行呢?
这可以快速的找到满意解,但不一定能找到最优解。
看下面的实例
慰俗瑶明摸偷薪碳杨仓死肪迂得醒铁锣垣齐垦姆晕窘菜钮悯哎蒙得烁循滁5整数规划5整数规划
整数规划的实例
MAXZ=X1+ 4X2
-2X1+3X2≤3
X1+2X2≤8
Xi取非负整数
松弛最优(,)
(2,2) (3,2)
可行,但均非最优
均不可行
(2,3) (3,3)
最优解(4,2)不在松弛最优解附近
最优解
(4,2)
浑萎镭庭猎彩棱兆裴嘘膘涨吠执钞逝爹分碰产忌绿抓八阔贪季障伊主梢只5整数规划5整数规划
整数规划的实例
MAXZ=X1+ 4X2
-2X1+3X2≤3
X1+2X2≤8
Xi取非负整数
先求整数规划的松弛最优解,然后或圆整或在附近找,未必能找到最优解。只能保证快速找到满意解。如果要求不高,可以这样做。
哭拯挽猎猩酞狮李须喂遥蓑墩瀑讹慕桐热魄搞夸努宴擞服矣局嚷吱斜癸奎5整数规划5整数规划