第六章 整数规划
1 第六章 整数规划
引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量、可获利润及托运限制如下：利润体积重量甲52205乙4102413托运限制两种货物各托运多少箱使利润最大？MaxZ=20x, +10x25x1 +4x2≤242x +5x2≤13X1,X2≥0 X1,X2 为整数
引例：某厂利用集装箱托运甲、乙两种货物，每箱体 积重量 、可获利润及托运限制如下： 体积 重量 利润 甲 5 2 20 乙 4 5 10 托运限制 24 13 两种货物各托运多少箱使利润最大？ Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0 x1 , x2 为整数
整数规划的数学模型1、整数规划问题(IP)整数规划问题：是指要求部分或全部决策变量的取值为整数的规划问题松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题重点研究：喜整数线性规划问题
一、 整数规划的数学模型 1、整数规划问题 整数规划问题（IP）:是指要求部分或全部决策变 量的取值为整数的规划问题。 松弛问题：不考虑整数条件，由余下的目标函数 和约束条件构成的规划问题。 重点研究：整数线性规划问题
2、整数线性规划问的模型max(min) Z =c;x;j=1nZaijX, ≤(≥,=)b; i=1,2,..,mj=1x≥0x,中取部分或全部为整数j=1,2,.,n
2、整数线性规划问题的模型 j=1,2,.,n j n j Z c j x = = 1 max(min) 0 ( , ) 1 = = j i n j ij j x a x b i=1,2,.,m xj 中取部分或全部为整数
3、整数规划问题的类型：(1）纯整数规划问题minZ=X, +X2+x3+x$+xs+x6+x$+xgXi≥ 8X1 + X2 ≥ 8X1 + X2+ X3 ≥7Xi+X2+ X3 + X4 ≥1X2+ X3 + X4 + Xs≥2X3+ X4 + Xs +X ≥ 1X4 + Xs +X +X ≥5Xs+ X6 + X+Xg ≥ 10X6 + X +Xg ≥ 10X +Xg ≥ 6Xg≥ 6x;≥0(i=1,...,8)且为整数
3、整数规划问题的类型： (1) 纯整数规划问题 x1 8 x1 + x2 8 x1 + x2+ x3 7 x1+x2+ x3 + x4 1 x2+ x3 + x4 + x5 2 x3+ x4 + x5 +x6 1 x4 + x5 +x6 + x7 5 x5+ x6 + x7 +x8 10 x6 + x7 +x8 10 x7 +x8 6 x8 6 xi 0 (i =1,.,8)且为整数 minZ= x1 + x2 +x3+x4+x5+x6 +x7+x8
2）0-1型整数线性规划例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为a，和c，此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之，不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？Max Z-Ecyj1对项目i投资X=Zax<B【0对项目不投资X2≥XiXs+x≥1Xs+X6 +x,=2x;=0或1 (j=1,2,...n)
(2) 0-1型整数线性规划 例2：现有资金总额为B。可供选择的投资项目有n个，项 目j所需投资额和预期收益分别为aj 和cj ,此外，因种种 原因，有3个附加条件：若选择项目1必须同时选择项目2， 反之，不一定；项目3和项目4中至少选择一个；第三， 项目5、6、7中恰好选择两个。应当怎样选择投资项目， 才能使总预期收益最大？ 1 对项目j 投资 0 对项目j 不投资 xj= Max Z=∑cjxj ∑ajxj≤B x2 ≥ x1 x3+ x4≥ 1 x5+ x6 +x7=2 xj=0或1（j=1,2,.n）
(3）混合整数规划例3：工厂A,和A,生产某种物资，由于该种物资供不应求，还需要建一家工厂。由两个待选方案A,和A4。物资需求地为B;(j=1,2,3,4)。工厂A,和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小。B1B2B3B4生产能力93A124400857A23600762A312002A4455200需求量350400300150
例3: 工厂A1和A2生产某种物资，由于该种物资供不应 求，还需要建一家工厂。由两个待选方案A3和A4。物 资需求地为Bj (j=1,2,3,4)。工厂A3和A4的生产费用估计 为1200万元或1500万元。选择哪一个方案才能使总费 用（包括物资运费和新工厂的生产费用）最小。 (3) 混合整数规划 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
B1B2B3B4生产能力A129344008357A26007612A320025A445200350400300150需求量 +[1200y+1500(1-y)]mir -Z2cijX11+ X21+ X31+ X41=350— 0-1变量KX12+ X22+ X32+ X42=400y=『1若建工厂A3X13+ X23+ X33+ X43=3000若建工厂A4X14+ X24+ X34+ X44=150设x为由A;送往B；的物资数量。X11+ X12+ X13+ X14=400X21+ X22+ X23+ X24=600X31+ X32+ X33+ X34=200yX41+ X42+ X43+ X44=200(1-y)Xi≥0,y=0或1
y—— 0-1变量 y= 1 若建工厂A3 0 若建工厂A4 设xij为由Ai送往Bj 的物资数量。 x11+ x21+ x31+ x41=350 x12+ x22+ x32+ x42=400 x13+ x23+ x33+ x43=300 x14+ x24+ x34+ x44=150 x11+ x12+ x13+ x14=400 x21+ x22+ x23+ x24=600 x31+ x32+ x33+ x34=200y x41+ x42+ x43+ x44=200(1-y) xij≥0, y=0或1 min Z=∑∑cijxij +[1200y+1500(1-y)] 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
割平面法1、基本思想找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。由松弛问题的可行域向整数规划的可行域逼近
二、 割平面法 1、基本思想 找到纯整数线性规划的松弛问题，不考虑整数 约束条件，但增加线性约束条件，将松弛问题的可 行域切割一部分，但不切割掉任何整数解，只切割 掉包括松弛问题的最优解在内的非整数解。 由松弛问题的可行域向整数规划的可行域逼近
割平面求解举例二、Max Z=xi+x2Max Z=xi+x2-Xi+x2≤1-Xi+x2+x3=1松弛问题3xj+x2 ≤43xj+x2 +x4=4X1,X2≥0且为整数X1, X2≥0
二、割平面求解举例 Max Z=x1+x2 -x1+x2≤1 3x1+x2 ≤4 x1 , x2≥0且为整数 松弛问题 Max Z=x1+x2 -x1+x2≤1 3x1+x2 ≤4 x1 , x2≥0 -x1+x2+x3 =1 3x1+x2 +x4=4 x1 , x2≥0