整数规划数学模型完整版

1

整数线性规划（IntegerLinearProgramming）§1整数线性规划问题的提出

线性规划的最优解有时候可能是分数或小数，事实上，线性规划是连续变量的线性优化问题。但在实际中，常有要求解答必须是整数的情形（称为整数解）。例如，所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。把带有分数或小数的解经过“舍入化整”常常是不行的，因为化整后不一定是可行解；或者虽是可行解但不一定是最优解。因此，对求最优整数解的问题需要另行研究。我们称这样的问题为整数线性规划。2整数线性规划的可行解集为点集对应与其松弛问题的可行解的整数点集maxz=x1+4x2s.t.-2x1+3x2≤

3x1+2x2≤

8x1,x2≥0,且为整数***********oAB(18/7,19/7)312R1:X1=18/7x2=19/7Z=13.430A1A2ABCA3A4R2:OA1A4Cx1=2x2=7/3Z=11.33R3:A2AA3x1=3x2=5/2z=13无可行解R4:A2A5A6AX1=4x2=2Z=12A5A64整数规划：要求一部分或全部决策变量必须取整数值的规划问题。整数规划问题的松弛问题：不考虑整数要求，由余下的目标函数和约束条件构成的规划问题。整数线性规划：若松弛问题是一个线性规划，则称该整数规划为整数线性规划。5整数规划中，如果所有的变量都要求是（非负）整数，就称为纯整数规划(PureIntegerProgramming)或全整数规划(AllIntegerProgramming)；如果仅是其中一部分变量取值为整数，则称为混合整数规划(MixedIntegerProgramming)。整数线性规划的一种特殊情形是0-1规划，它的变量取值仅限于0或1。指派问题就是一种特殊的0-1规划。6例1某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大？货物体积(米3/箱)重量(百公斤/箱)利润(千元/箱)甲5220乙4510装运限制24137解：设X1,X2为甲、乙两货物各托运箱数5X1+4X2

242X1+5X2

13X1,X20X1,X2为整数maxZ=20X1+

10X28例2背包问题背包可装入8单位重量，10单位体积物品物品名称重量体积价值1书52202摄像机31303枕头14104休闲食品23185衣服45159解：Xi为是否带第i种物品maxZ=20X1+

30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X5

82X1+X2+4X3+3X4+5X510Xi为0,110,整数§2整数规划问题的数学模型11(1)、Xi为i物品携带数量

ai为i物品单位重量

ci为i物品重要性估价

b为最大负重(2)、投资决策

Xi为在i地区建厂规模

ai为在i地区建厂基建费用

ci为在i地区建厂单位利润

b为最大资本(3)、Xi取0或1时，可作项目投资模型12例3选址问题A1A3B2B4B3B1A2Ai:可建仓库地点，容量ai,投资费用bi，建2个Bj:商店，需求dj(j=1…4)Cij:仓库i到商店j的单位运费问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。13解：设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+y14a1x1y21+y22+y23+y24a2x2y32+y33+y34a3x3xi为0－1，yij0混合整数规划14

§30－1决策变量的应用0-1变量通常表示“是”或“否”这样的逻辑是非判断，可以在很多问题中应用。

1.可用于相互排斥计划中例4运输方式：火车、船。火车：5X1+4X2

24(体积)船：7X1+3X2

45(体积)15maxZ=20X1+

10X22X1+5X2

135X1+4X2

24+My1

火车7X1+3X2

45+M(1-y1

)船X1,

X20整数y1为0或1

M>0当y1=0火车

y1

=1船16maxZ=20X1+

10X22X1+5X2

135X1+4X2

24+My1

火车7X1+3X2

45+My2船X1,

X20整数y1+y2=1当y1,y2=0,117例5.ai1x1+ai2x2+…+ainxn

bi(i=1,…,m)互相排斥m个约束，只有一个起作用ai1x1+…+ainxn

bi+yiM

(i=1,…,m)y1+…+ym=m-1yi为0或1M>0182.投资选址某公司拟在市东，西，南三区建门市部，拟议中有7个位置可供选择，规定在东区，A1,A2,A3三个点至多选2个在西区，A4,A5两个点至少选1个在南区，A6,A7两个点至少选1个若选Ai点，投资bi,每年利润Ci,总投资不超过B。19xi=1,Ai点建门市部

=0，Ai点不建门市部Maxz=∑CiXiSt∑biXi≤BX1+X2+X3≤2X4+X5≥1X6+X7≥1Xi=0,120覆盖选址问题以最少数目的地点覆盖所有区域可能的分布地址覆盖区域

Ax11，5，7Bx21，2，5，7Cx31，3，5Dx42，4，5Ex53，4，6Fx64，5，6Gx71，5，6，721Minz=x1+x2+x3+x4+x5+x6+x7

(Xi分别代表ABCDEFG)Stx1+x2+x3+x7≥1地点1x2+x4≥1地点2x3+x5≥1地点3x4+x5+x6≥1地点4x1+x2+x3+x4+x6+x7≥1地点5x5+x6+x7≥1地点6x1+x2+x7≥1地点7xi=0,122分公司选址问题某销售公司打算通过在武汉或长春设立分公司（也许在2个城市都设分公司）增加市场份额，管理层同时也计划在新设分公司的城市至多建一个配送中心，也可以不建配送中心。经过财务和技术经济专家的计算，每种选择对公司收益的净现值、每种选择所需的费用如下，总的预算费用不得超过20万元。目标是在满足以上约束的条件下使总的净现值最大。23问题决策变量净现值(万元)所需资金(万元)

是否在长春设分公司x11812是否在武汉设分公司x2106是否在长春建配送中心x31210是否在武汉建配送中心x48424maxZ=18x1+10x2+12x3+8x4st12x1+6x2+10x3+4x4≤20x3+x4≤1x3≤x1x4≤x2xj=0,1，j=1,2,3,4253.固定成本问题关于固定费用问题Xj表示产量Cj单位变动成本Kj表示固定成本Pj为总成本Pj=Kj+CjXj,Xj>0=0,Xj=0,j=1,2,326固定成本核算产品利润原料1原料2原料3固定成本添加剂400.40.6200溶剂300.50.20.350清洁剂500.60.10.340020吨5吨21吨27不考虑固定成本maxZ=40x1+30x2+50x30.4x1+0.5x2+0.6x3≤20