文档介绍：运筹学赵明霞山西大学经济与管理学院第五章整数规划整数规划的数学模型割平面法分支定界法0-1整数规划指派问题应用2020/8/212*求整数解的线性规划问题,不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的,而要用整数规划的方法加以解决。在整数规划中:如果所有的变量都为非负整数,则称为纯整数规划问题;如果只有一部分变量为非负整数,则称之为混合整数规划问题。如果所有的变量都为0-1变量,则称之为0-1规划。2020/8/213*、乙两种货物,这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件,问两种货物各托运多少件,可使获得利润最大?货物每件体积(立方英尺)每件重量(百千克)每件利润(百元)甲乙**********托运限制1365140第一节整数规划的数学模型2020/8/214*解:设x1、x2分别为甲、乙两种货物托运的件数,建立模型Maxz=2x1++273x2≤13654x1+40x2≤140x1≤4x1,x2≥0为整数。如果去掉最后一个约束,就是一个线性规划问题。2020/8/215*得到线性规划的最优解为x1=,x2=,。由图表可看出,整数规划的最优解为x1=4,x2=2,目标函数值为14。12341232x1+3x2=+3x2=142x1+3x2=62020/8/216*性质:任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值;任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。2020/8/21713/4,5/2松弛问题第一次切割4,1第二次切割x1+x2≤5第二节割平面法2020/8/218设纯整数规划伴随LP的最优解若全为整数,则为IP的最优解。否则,若不全为整数,设第r行基变量非整。对应方程为2020/8/219将分离成一个整数与一个非负真分数之和:则有等式两边都为整数并且有2020/8/2110