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