课程名称：《运筹学》第13讲次授课题目整数规划本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，会建立整数规划模型，学会用割平面法、分支定界法求解整数规划问题。[重点及难点】割平面法、分支定界法。内容[本讲课程的引入]引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量可获利润及托运限制如下：体积重量利润甲5220乙45102413托运限制两种货物各托运多少箱使利润最大？Max Z=20x, +10x25x, +4x,≤242x, +5x,≤13x,x≥0x,x为整数[本讲课程的内容]整数规划的数学模型-1、整数规划问题整数规划问题（IP）：是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。重点研究：整数线性规划问题2、整数线性规划问题的模型max(min) Z-Zc*)-1(2a*) (2,)b -1..mj-1x,≥0x,中取部分或全部为整数j=1,2,.n
课程名称：《运筹学》 第 13 讲次 授课题目 整数规划 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，会建立整数规划模型，学会用割平面法、分支定界法 求解整数规划问题。 [重点及难点] 割平面法、分支定界法。 内 容 [本讲课程的引入] [本讲课程的内容] 一、 整数规划的数学模型 1、整数规划问题 整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。 松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。 重点研究：整数线性规划问题 2、整数线性规划问题的模型
内容3、整数规划问题的类型：(1)纯整数规划问题minZ=x,+x,+xg+x+xs+xo+x,+xg(X)≥ 8X+X≥8Xf + X2+ Xg≥7Xi+x2+ Xg+ X ≥1X2+ X+ Xy+ Xg≥2X3+ X+ Xs+x≥1X4+Xg+X+X,≥5Xg+X+X+Xg≥10X+ X,+xg≥10X,+xg≥6Xg≥6x≥0(i=1,.,8)且为整数(2)0-1型整数线性规划例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj，此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之，不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？Max Z-Eeyj（1对项目/投资X(Zax<B【0对项目/不投资x≥xiX+x≥1Xg+xg +x,=2XF0或1 (j=1,2,..n)(3）混合整数规划例3：工厂A1和A2生产某种物资，由于该种物资供不应求，还需要建一家工厂。由两个待选方案A3和A4。物资需求地为Bj(i-1,2,3,4)。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小
内 容 (2) 0-1 型整数线性规划 例 2：现有资金总额为 B。可供选择的投资项目有 n 个，项目 j 所需投资额和预期收益 分别为 aj 和 cj ,此外，因种种原因，有 3 个附加条件：若选择项目 1 必须同时选择项目 2， 反之，不一定；项目 3 和项目 4 中至少选择一个；第三，项目 5、6、7 中恰好选择两个。 应当怎样选择投资项目，才能使总预期收益最大？ (3) 混合整数规划 例 3: 工厂 A1 和 A2 生产某种物资，由于该种物资供不应求，还需要建一家工厂。由 两个待选方案 A3 和 A4。物资需求地为 Bj(j=1,2,3,4)。工厂 A3 和 A4 的生产费用估计为 1200 万元或 1500 万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用） 最小
内容生产B3B1B2B4能力A129344008357A26007612A32005425A4200300150 350400需求量min Z-Zcjxj, +[1200y+1500(1-y)]y——0-1变量X11+ X21+ X31+ X41=350X12+ X22+ X32+ X42=400y=『1若建工厂A;X13+ X23+ X33+ X43=300（o若建工厂AX14+ X24+ X34+ X44=150设x为由A送往B，的物资数量。X1+ X12+ X13+ X14=400X21+ X22+ X23+ X24=600X31+X32+X33+X34=200yX41+ X42+ X43+ X44=200(1-y)X≥0,y=0或1割平面法二、1、基本思想找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。由松弛问题的可行域向整数规划的可行域逼近二、割平面求解举例Max Z=xi+x2Max Z=x,+x2[-xtx,≤1-x;+x2+x3 =1松弛问题3xjtx2 ≤43x;+x2 +x,=4Xx≥0且为整数X,x,≥0
内 容 二、 割平面法 1、基本思想 找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松 弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在 内的非整数解。 由松弛问题的可行域向整数规划的可行域逼近 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
内“容不考虑整数解约束，解松弛问题的最优单纯形表为1100CBbXBX1X2X3X4-111010X3031041X41100a...........1103/4-1/41/4X17/403/41/411X200Z=5/2-1/2-1/2a得到非整数的最优解：max z=5/2X,=3/4，×,=7/4,×3=X4=0,103/4-1/41/41Xi01/417/413/4X200Z=5/20-1/2-1/2得到非整数的最优解：X,=3/4,x,=7/4,x,=x=0,max z=5/2不能满足整数最优解的要求。为此考虑将带有分数的最优解的可行域中分数部分割去，再求最优解可从最终计算表中得到非整数变量对应的关系式：113xr4tt4t=4317X2+43+4*=4为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和313X +(-1+x+X44443.134+=1+x,+43+4然后将整数部分与分数部分分开，移到等式左右两边得到：3(31x-x4745+x43(31-1=X+4A4
内 容
内容现考虑整数条件要求xl、x2都是非负整数，于是由条件可知x3、x4也都是非负整数,这一点对以下推导是必要的，如不都是整数，则应在引入x3、x4之前乘以适当常数，使之都是整数。在上式中（其实只考虑一式即可）从等式左边看是整数；等式右边也应是整数。但在等式右边的()内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是整数条件可由下式所代替；331x)≤0x+444·即-3×3-×4≤-3这就得到一个切割方程（或称为切割约束），将它作为增加约束条件，再解例3。引入松弛变量x5，得到等式-3x3-×,+x,=3将这新的约束方程加到最终计算表110Ci00XbbCsX1X2X3X4X5013/41-1/41/40Xi17/4013/41/40X20010-3-3-1Xs005/20-1/2-1/2CZi·11000?CBbXB+5X1X2X3X410011/4X13/4-1/400111/47/43/4X2[-3]0-300-11X5000Z=5/2-1/2-1/2a11010X11/31/121101001/4×2010011/3-1/3X3000Z=2-1/3-1/30
内 容 现考虑整数条件 要求 x1、x2 都是非负整数，于是由条件可知 x3、x4 也都是非负整数,这一点对以 下推导是必要的，如不都是整数，则应在引入 x3、x4 之前乘以适当常数，使之都 是整数。 在上式中(其实只考虑一式即可)从等式左边看是整数；等式右边也应是整数。但在 等式右边的(·)内是正数；所以等式右边必是非正数。就是说，右边的整数值最大 是零。于是整数条件可由下式所代替；