21整数规划数学模型

1第2章整数规划例1、集装箱运货货物体积(米3/箱)重量(百公斤/箱)利润(千元/箱)甲5220乙4510装运限制2413§2.1数学模型2解：设X1,X2为甲、乙两货物各托运箱数5X1+4X2242X1+5X213X1,X20X1,X2为整数maxZ=20X1+10X23例2、背包问题背包可再装入8单位重量，10单位体积物品物品名称重量体积价值1书52202摄像机31303枕头14104休闲食品23185衣服45154解：Xi为是否带第i种物品maxZ=20X1+30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X582X1+X2+4X3+3X4+5X510Xi为0,15一般形式：0max11iniiiniiiXbXaXCZ,整数6(1)、Xi为i物品携带数量ai为i物品单位重量ci为i物品重要性估价b为最大负重(2)、投资决策Xi为在i地区建厂规模ai为在i地区建厂基建费用ci为在i地区建厂单位利润b为最大资本(3)、Xi取0或1时，可作项目投资模型7例3、选址问题A1A3B2B4B3B1A2Ai:可建仓库地点，容量ai,投资费用bi，建2个Bj:商店，需求dj(j=1…4)Cij:仓库i到商店j的单位运费问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。8解：设Xi(i=1,2,3)为是否在Ai建仓库yij(i=1,2,3,j=1…4)由i仓库向j商店运货量y11+y21=d1y12+y22+y32=d2y23+y33=d3y14+y24+y34=d4x1+x2+x3=2y11+y12+y14a1x1y21+y22+y23+y24a2x2y32+y33+y34a3x3xi为0－1，yij0313141miniijijijiiyCxbZ混合整数规划90－1决策变量的应用可用于相互排斥计划中例1、运输方式：火车、船。火车：5X1+4X224(体积)船：7X1+3X245(体积)10maxZ=20X1+10X22X1+5X2135X1+4X224+MX37X1+3X245+M(1-X3)X1,X20整数X3为0或1M0当X3=0火车X3=1船11例2、ai1x1+ai2x2+…+ainxnbi(i=1,…,m)互相排斥m个约束，只有一个起作用ai1x1+…+ainxnbi+yiM(i=1,…,m)y1+…+ym=m-1yi为0或1M0