第八章蓑数规 §1整数规划的图解法 §2整数规划的计算机求解 §3整数规划的应用 §4整数规划的分枝定界法 §5割平面方程
管 理 运 筹 学 1 第八章 整数规划 §1 整数规划的图解法 §2 整数规划的计算机求解 §3 整数规划的应用 §4 整数规划的分枝定界法 §5 割平面方程
第八章簦数规 求整数解的线性规划问题,不是用四舍五入法或 去尾法对线性规划的非整数解加以处理都能解决 的,而要用整数规划的方法加以解决。 在整数规划中,如果所有的变量都为非负整数, 则称为纯整数规划问题;如果有一部分变量为负 整数,则称之为混合整数规划问题。在整数规划 中,如果变量的取值只限于0和1,这样的变量我 们称之为0-1变量。在纯整数规划和混合整数规划 问题中,如果所有的变量都为0-1变量,则称之为 0-1规划。 管理蓦
管 理 运 筹 学 2 第八章 整数规划 • 求整数解的线性规划问题，不是用四舍五入法或 去尾法对线性规划的非整数解加以处理都能解决 的，而要用整数规划的方法加以解决。 • 在整数规划中，如果所有的变量都为非负整数， 则称为纯整数规划问题；如果有一部分变量为负 整数，则称之为混合整数规划问题。在整数规划 中，如果变量的取值只限于0和1，这样的变量我 们称之为0-1变量。在纯整数规划和混合整数规划 问题中，如果所有的变量都为0-1变量，则称之为 0-1规划
§1整教规划的图解法 例1.某公司拟用集装箱托运甲、乙两种货物,这两种货物每件的体积、 重量、可获利润以及托运所受限制如表所示。 货物 每件体积 每件重量 每件利润 (立方英尺) (百千克) (百元) 甲 195 2 273 40 3 托运限制 1365 140 甲种货物至多托运4件,问两种货物各托运多少件,可使获得利润最大 解:设x1、x2分别为甲、乙两种货物托运的件数,建立模型 目标函数:Maxz=2x1+3x2 约束条件:st 195X1+273x,≤1365 4x1+40x2≤140 <4 x1,x2≥0为整数。 如果去掉最后一个约束,就是一个线性规划问题。利用图解法
管 理 运 筹 学 3 §1 整数规划的图解法 例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、 重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 解：设x1 、x2分别为甲、乙两种货物托运的件数，建立模型 目标函数：Max z = 2x1 +3 x2 约束条件： s.t. 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1，x2 ≥ 0 为整数。 如果去掉最后一个约束，就是一个线性规划问题。利用图解法， 货物 每件体积 （立方英尺） 每件重量 （百千克） 每件利润 （百元） 甲 乙 195 273 4 40 2 3 托运限制 1365 140
§1教规划的图解法 2x1+3x2=14.66 2x1+3x2=14 2x1+3x2=6 得到线性规划的最优解为x1=244x2=3.26,目标函数值为1466 由图表可看出,整数规划的最优解为x1=4,x2=2,目标函数值为14 性质1:任何求最大目标函数值的纯整数规划或混合整数规划的最大目 标函数值小于或等于相应的线性规划的最大目标函数值;任何求最小目 标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相 应的线性规划的最小目标函数值 管理遠筹 4
管 理 运 筹 学 4 得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。 性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目 标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目 标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相 应的线性规划的最小目标函数值。 1 2 3 4 1 2 3 2x1+3x2 =14.66 x1 x2 2x1+3x2 =14 2x1+3x2 =6 §§11 整数规划的图解法 整数规划的图解法
§2教规划的计算机求解 例2: 例3 Max z= 3x+ xo t 3x Max z= 3x, xo t 3x s. t x1+2x+ 4 x1+2x2+x3≤4 4x,-3x2≤2 4x2-3x3≤2 3x2+2x3≤3 x1-3x2+2x3≤3 X x1,x2,x3≥0为整数 X1,x,x2≥0 x1,x3为整数x3为 0-1变量 用《管理运筹学》软件求解得: 用《管理运筹学》软件求解得: 5 x1=4 1.25 Z=16.25 运筹
管 理 运 筹 学 5 例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 ≤ 4 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x1,x2,x3 ≥ 0 为整数 例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 ≤ 4 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x3 ≤1 x1,x2,x3 ≥ 0 x1，x3 为整数 x3 为 0-1变量 用《管理运筹学》软件求解得： x1 = 5 x2 = 2 x3 = 2 用《管理运筹学》软件求解得： x1 = 4 x2 = 1.25 x3 = 1 z = 16.25 §2 整数规划的计算机求解