?0?0?10??w1??0???????????????????? ??1??0???wm????0?00??wi自由，i?1,...,p,wi?0,i?p?1,...,m. 17
第二章 整数规划 §1 整数线性规划问题
要求变量值取整数值的线性规划问题称为整数线性规划，其中变量只取0或1的线性规划称为0-1规划。
投资决策问题 总金额B万元，n个项目，第j项目所需资金bj，利润cj，应该选哪些项目使总利润最大。
??max???s.t.????z=?cjxjj=1n?bxjj=1nj?B
xj=0,1房产投资 地产面积3000 M2，甲类房产每幢250M2，可收利润10万元，可建设不超过8幢，乙类房产每幢400M2，可收利润20万元，可建设不超过4幢，应该建设甲乙各几幢使得利润最大？
?maxz=10x?20y?s.t.250x?400y?3000 ??x?8?y?4?x,y?N?货朗问题 从v0出发，恰好经过v1，v2，?，vn 各一次回到v0，从vi到vj路程为dij，（dii＝M充分大），怎么走最近？
18
n??minz??dijxiji,j?0?n??s.t.?xij=1,i?0??n?xij=1,??j?0?ui?uj?nxij?n?1,??xij?0or1,??ui为实数，?j?0,?,ni?0,?,n1?i?j?ni,j?0,?,ni?1,?,n
背包问题 n个物品，体积分别为v1，v2，?，vn，价值分别为p1，p2，?，pn，一个容积为V的包，取哪些物品放入包内，使包内物品总价值最高。
例：
1) V=100, v1=p1=49, v2=p2=51, v3=p3=52 2) V=100, v1=p1=49, v2=p2=51, v3=52, p3=52.1 算法：穷举，共2n种物品的组合。
??max????s.t.???z=?pixii=1n?vxi=1nii?V
xi=0,1 19
§2 整数线性规划问题解法
1． 图解法
图解法求解下面的ILP问题
?min?s..?t????
z?x1?5x2x1?2x2?8x1? x2?4x1,x2?0且为整数
2． 分枝定界法
?minz??x1?x2?s..t?4x1?2x2??1??4x1?2x2?11 ???2x2??1?x1,x2?0且为整数??
(1.5, 2.5) ?minz??x1?x2?minz??x1?x2?s..?s..t?4x?2x??1?4x1?2x2??112??t??4x1?2x2?114x1?2x2?11 ???2x2??1?2x2??1??x1?1x1?2????x1,x2?0且为整数x1,x2?0且为整数??20
(1, 1.5) (2, 1.5) 21