第8章整数规划（IntegerProgramming）§1整数规划的图解法§2整数规划的计算机求解§3整数规划的应用§4整数规划的分枝定界法©&®byH.Q.Feng,CUFE2/33第八章整数规划求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。舍入化整求得到解可能是非可行解，或虽是可行解，但不是最优解在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；如果有一部分变量为负整数，则称之为混合整数规划问题。在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。在纯整数规划和混合整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。©&®byH.Q.Feng,CUFE3/33§1整数规划的图解法例1:某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。货物每件体积/（立方英尺）每件重量/百千克每件利润/百元甲乙19527344023托运限制1365140©&®byH.Q.Feng,CUFE4/33§1整数规划的图解法解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型目标函数：Maxz=2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1，x2≥0的整数。若去掉变量的整数约束，就是一个线性规划问题。©&®byH.Q.Feng,CUFE5/33性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=6§1整数规划的图解法得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4,x2=2,目标函数值为14。©&®byH.Q.Feng,CUFE6/33例2：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x1,x2,x3≥0的整数例3：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0，x1，x3为整数，x3为0-1变量用《管理运筹学》软件求解得：x1=5x2=2x3=2Zmax=23用《管理运筹学》软件求解得：x1=4x2=1.25x3=1z=16.25§2整数规划的计算机求解©&®byH.Q.Feng,CUFE7/33§3整数规划的应用一、投资场所的选择（相互排斥的计划，0-1规划）例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，...
