整数规划的特点及应用 Page 6 mimz=22,+200,+1500 x1+x21+x31+x41=350 x12+x22+x32+x42=400 X13+X23+x33+x43=300 x14+x24+x34+x4=150 〉 混合整数规划问题 x11+x12+x13+x14=400 s.t x21+x2+x23+x24=600 x31+x32+x33+x34=200y1 x1+x42+x3+x4=200y2 x≥0(i,j=1,2,3,4) y:=0,1(i=1,2)
整数规划的特点及应用 Page 6 = = = + + + = + + + = + + + = + + + = + + + = + + + = + + + = + + + = = + + = = 0,1 ( 1,2) 0 ( , 1,2,3,4) 200 200 600 400 150 300 400 350 . min [1200 1500 ] 4 1 4 2 4 3 4 4 2 3 1 3 2 3 3 3 4 1 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 1 4 2 4 3 4 4 4 1 3 2 3 3 3 4 3 1 2 2 2 3 2 4 2 1 1 2 1 3 1 4 1 4 1 4 1 1 2 y i x i j x x x x y x x x x y x x x x x x x x x x x x x x x x x x x x x x x x s t z c x y y i ij i j ij ij 混合整数规划问题
整数规划的特点及应用 Page 7 例4.2现有资金总额为B。可供选择的投资项目有n个，项目 j所需投资额和预期收益分别为a和c(j=1,2,n),此外由 于种种原因，有三个附加条件： ·若选择项目1，就必须同时选择项目2。反之不一定 ·项目3和4中至少选择一个； ·项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大
整数规划的特点及应用 Page 7 例4.2 现有资金总额为B。可供选择的投资项目有n个，项目 j所需投资额和预期收益分别为aj和cj（j＝1,2,.,n），此外由 于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2。反之不一定 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大
整数规划的特点及应用 Page 8 解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令x表示第j个项目的决策选择，记为： 对项目投资 对项目不投资 j=1,2m 投资问题可以表示为： max =2c,x j=1 公sa 2≥x S.t x3+x4≥1 x5+x6+x7=2 x,=0或者1 (j=1,2,.n)
整数规划的特点及应用 Page 8 解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令xj表示第j个项目的决策选择，记为： ( 1,2,., ) 0 1 j n j j xj = = 对项目 不投资 对项目 投资 投资问题可以表示为： = = + + = + = = = x 或 者 （ n） x x x x x x x a x B s t z c x j n j j j n j j j 0 1 j 1,2, 2 1 . max 5 6 7 3 4 2 1 1 1
整数规划的特点及应用 Page 9 例4.3指派问题或分配问题。人事部门欲安排四人到四个不 同岗位工作，每个岗位一个人。经考核四人在不同岗位的成 绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 工作 A B D 人员 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 19 90 丁 86 90 80 88
整数规划的特点及应用 Page 9 例4.3 指派问题或分配问题。人事部门欲安排四人到四个不 同岗位工作，每个岗位一个人。经考核四人在不同岗位的成 绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88
整数规划的特点及应用 Page 10 设 分配第人做工作时 不分配第人做工作时 数学模型如下： maxZ=85x11+92x12+73x13+90x14+95x21+87x22+ +78x23+95x24+82x31+83x32+79x33+90x34+ +86x41+90x2+80x43+88x44 要求每人做一项工作，约束条件为： x1+x2+x13+X14=1 X21+x22+X23+x24=1 尤31+x32+x3+X34=1 x1+x42+x43+x44=1
整数规划的特点及应用 Page 10 设 = 不分配第人做 工作时 分配第 人做 工作时 i j i j xij 0 1 数学模型如下： 4 1 4 2 4 3 4 4 2 3 2 4 3 1 3 2 3 3 3 4 1 1 1 2 1 3 1 4 2 1 2 2 8 6 9 0 8 0 8 8 7 8 9 5 8 2 8 3 7 9 9 0 max 8 5 9 2 7 3 9 0 9 5 8 7 x x x x x x x x x x Z x x x x x x + + + + + + + + + + + = + + + + + + 要求每人做一项工作，约束条件为： + + + = + + + = + + + = + + + = 1 1 1 1 4 1 4 2 4 3 4 4 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 x x x x x x x x x x x x x x x x