整数规划的数学模型分枝定界法割平面法型整数规

2020/6/221.整数规划的数学模型2.分枝定界法3.割平面法4.0-1型整数规划5.指派问题2020/6/22整数规划的数学模型max(min)(c1x1+c2x2+…+cnxn)a11x1+a12x2+…+a1nxn(=,)b1a21x1+a22x2+…+a2nxn(=,)b2……...am1x1+am2x2+…+amnxn(=,)bmx1~n0且取整数纯整数规划:所有变量都有取整约束混合整数规划:只有部分变量有取整约束2020/6/22分枝定界法1.分枝定界法的基本思路2.第65页例5-13.练习题2020/6/22分枝定界法的基本思路利用连续的(线性规划)模型来求解非连续的(整数规划)问题。假设rx是一个有取整约束的变量而它的最优连续值rx是非整数，那么下列区间1][][rrrxxx不可能包含任何整数解，这里][rx表示rx的取整值。因此，rx的可行整数值必然满足此二条件之一：][rrxx或1][rrxx。2020/6/22把这两个约束条件分别加到原来的解空间上，便产生了两个互斥的子问题。这便是分枝的含义。由于分枝过程是通过增加约束条件来实现的，因此每一问题的子问题都不会有比其自身还大（目标函数求极大值）的最优目标值。当所有子问题的解均为非整数可行解时，应首先选择具有最大最优目标值的子问题来分枝；当得到第一个整数可行解时，它的相应目标值可作为该整数规划最优值的下界，舍掉所有最优值不大于该下界的子问题。按最优值的大小顺序对保留下来的子问题进行分枝，如果出现具有更大目标值的整数可行解，将下界更新为此整数可行解的目标值并进一步剪枝。从复这一过程，最终保留下来的整数可行解即为整数规划的最优解。分枝定界法的基本思路2020/6/22第65页例5-1maxz=40x1+90x29x1+7x2567x1+20x270x1，x20且取整2020/6/22用分枝定界法解例5-11.求解相应的线性规划L0maxz=40x1+90x29x1+7x2567x1+20x270x1，x202020/6/22用分枝定界法解例5-1x259x1+7x2=564327x1+20x2=701012345678910x1L0:x*=(4.81,1.82),Z*=3562020/6/22用分枝定界法解例5-12.将L0分解为L1和L2L1：maxz=40x1+90x29x1+7x2567x1+20x270x14x1，x20L2：maxz=40x1+90x29x1+7x2567x1+20x270x15x1，x20L1：X*=(4,2.10),Z*=349L2：X*=(5,1.57),Z*=3412020/6/22用分枝定界法解例5-13.分解L1形成L3、L4，其中：L3={L1,x22}L4={L1,x23}L3:X*=(4,2),Z*=340L4:X*=(1.42,3),Z*=327(1)取下界min=340(L3);(2)舍弃L42020/6/22用分枝定界法解例5-14.分解L2形成L5、L6，其中：L5={L2,x21}L6={L2,x22}L5:X*=(5.44,1),Z*=308L6:无可行解(1)舍弃L5、L6；(2)得最优解X*=(4,2),Z*=340。2020/6/22例5-1求解过程示意图L0(4.81，1.82)356L1(4，2.1)349L2(5，1.57)341L3(4，2)340L4(1.42，3)327L5(5.44，1)308L6无可行解2020/6/22练习题maxz=2x1+5x2+4x3x1+x2+x312x1+2x2154x1+5x326x1~30且取整2020/6/22求解练习题首先求解线性规划L0:maxz=2x1+5x2+4x3x1+x2+x3+x4=12x1+2x2+x5=154x1+5x3+x6=26x1~602020/6/22求解练习题线性规划L0的最终单纯形表cj254000CBXBx1x2x3x4x5x6b450x3x2x61/2011-1/201/21001/203/200-55/219/215/27/2σ-5/200-4-1/202020/6/22求解练习题将L0分解为L1和L2，其中：L1={L0,x27}L2={L0,x28}2020/6/22求解练习题L1求解单纯形表cj2540000CBXBx1x2x3x4x5x6x7b4500x3x2x6x71/2011-1/2001/21001/2003/200-55/21001000019/215/27/27σ基变量系数向量单位化cj2540000CBXBx1x2x3x4x5x6x7b4500x3x2x6x71/2011-1/2001/21001/2003/200-55/210-1/2000-1/2019/215/27/2-1/2σ-5/200-4-1/2002020/6/22求解练习题线性规划L1的最终单纯形表cj2540000CBXBx1x2x3x4x5x6x7b4500x3x2x6x5101100-10100001-100-5015100010-25711σ-200-400-1L1有整数最优解X*=（0，7，5），Z*=55线性规划L2无可行解所以原整数规划的最优解为X*=（0，7，5）最优值为Z*=552020/6/22求解练习题L0（0，15/2，9/2）111/2L1（0，7，5）55L2无可行解2020/6/22割平面法1.割平面法的基本思路2.例3.练习题2020/6/22割平面法的基本思路同分枝定界法一样，割平面法也是一种利用连续模型求解非连续问题的常用方法。割平面法的基本思路是：当得到的解不满足取整约束时，就设法在问题上增加一个约束条件，把包含这个非整数解的一部分可行域从原来的可行域中割除，但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。2020/6/22例maxz=x1+x2-x1+x213x1+x24x1，x20且取整2020/6/22用割平面法解例1.求解相应的线性规划L0maxz=x1+x2-x1+x213x1+x24x1，x202020/6/22用割平面法解例表1（线性规划最终单纯形表）cj1100CBXBx1x2x3x4b11x2x1013/41/410-1/41/47/43/4σ00-1/2-1/2Z=5/2非整数解，为建立割平面，首先考虑非整数解中余数最大的基变量，此例中x1、x2的余数均为3/4，不妨选取x2：x2+3/4x3+1/4x4=7/42020/6/22用割平面法解例x2+3/4x3+1/4x4=7/4现将各系数分成整数和非负真分数两部分，从而可得：(1+0)x2+(0+3/4)x3+(0+1/4)x4=(1+3/4)将整数部分的变量移至等式右端有：3/4x3+1/4x4=3/4+（1-x2）非负整数解(1-x2)为整数，左端非负故有：3/4x3+1/4x4=3/4+非负整数从而：3/4x3+1/4x43/4或x21以x21为割平面可使可行域减少一个包括A点在内的三角形。2020/6/22x2A101x1用割平面法解例2020/6/22用割平面法解例表2（加入割平面的单纯形表）cj11000CBXBx1x2x3x4x5b110x2x1x5013/41/4010-1/41/40010017/43/41σ基变量系数向量单位化表3（最终单纯形表）cj11000CBXBx1x2x3x4x5b110x2x1x3010011001/3-1/30011/3-4/3111σ000-1/3-2/3Z=22020/6/22练习题maxz=2x1+5x2+4x3x1+x2+x312x1+2x2154x1+5x326x1~30且取整2020/6/22求解练习题线性规划L0的最终单纯形表cj254000CBXBx1x2x3x4x5x6b450x3x2x61/2011-1/201/21001/203/200-55/219/215/27/2σ-5/200-4-1/202020/6/22求解练习题选取x2：1/2x1+x2+1/2x5=15/21/2x1+1/2x5=1/2+（7-x2）于是有割平面：1/2x1+1/2x51/2或x272020/6/22求解练习题cj2540000CBXBx1x2x3x4x5x6x7b4500x3x2x6x71/2011-1/2001/21001/2003/200-55/21001000019/215/27/27σ基变量系数向量单位化cj2540000CBXBx1x2x3x4x5x6x7b4500x3x2x6x71/2011-1/2001/21001/2003/200-55/210-1/2000-1/2019/215/27/2-1/2σ-5/200-4-1/2002020/6/22求解练习题cj2540000CBXBx1x2x3x4x5x6x7b4500x3x2x6x5101100-10100001-100-5015100010-25711σ-200-400-1已得整数最优解X*=（0，7，5），Z*=55所以原整数规划的最优解为X*=（0，7，5）最优值为Z*=552020/6/220-1型整数规划1.0-1规划：0-1规划是整数规划的特例，是所有决策变量仅取0和1的整数规划问题。2.引例（1）第69页例5-3（2）引例23.0-1规划的隐枚举法（1）隐枚举法的基本步骤（2）第70页例5-4（3）第71页例5-52020/6/22第69页例5-3某公司拟在东、西、南三个区建立销售门市部，拟议中有7个场点A1~7可供选择。东区的三个点A1~3最多选两个，西区的两个点A4~5最少选一个，南区的两个点A6~7最少选一个。如果建设Ai点，需要投资bi元，年可获利ci元，公司可筹集到的投资总额为B元，问应如何决策才能使年利潤最大。2020/6/22例5-3令xi=0或1，其中：xi=0表示第I个点未被选取xi=1表示第I个点被选取其数学模型为：x1+x2+x32x4+x51x6+x71iiixcMaxz71Bxbiii712020/6/22引例2两种运输方式的限制条件分别为：6x1+4x2307x1+3x240互斥的约束统一于一个模型中：6x1+4x230+Mx37x1+3x240+M(1-x3)其中x3为0-1变量。2020/6/22隐枚举法的基本步骤1.目标函数极小化；2.目标函数系数非负化，如果xj的系数为负数，可令xj=1-xj；3.决策变量按其目标函数系数的大小排列；4.令所有变量为“0”，检查该解的可行性，如果可行此解即为最优解，如果不可行进入下一步；5.按变量的顺序依次令各变量分别取“0”或“1”，根据分枝定界的原理进行剪枝，直至结束。2020/6/22第70页例5-4Maxz=3x1-2x2+5x3x1+2x2-x32x1+4x2+x34x1~3=0或1第一步：Minw=-3x1+2x2-5x3x1+2x2-x32x1+4x2+x34x1~3=0或12020/6/22例5-4第二步：令x1=1-x1，x3=1-x3Minw=3x1+2x2+5x3-8-x1+2x2+x32-x1+4x2-x32x1~3=0或1第三步：Minw=2x2+3x1+5x3-82x2-x1+x324x2-x1-x32x1~3=0或1第四步：令所有变量为“0”，得可行解，所以原问题的最优解为（1，0，1），最优值为8。2020/6/22maxz=8x1+2x2-4x3-7x4-5x53x1+3x2+x3+2x4+3x545x1+3x2-2x3-x4+x54x1~5=0或1经前三步有：令x1=1-x1，x2=1-x2minw=2x2+4x3+5x5+7x4+8x1-103x2-x3-3x5-2x4+3x123x2+2x3-x5+x4+5x14x1~5=0或1第71页例5-5202