第八章蓑数规 §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 整数规划的计算机求解
§3蓬数规划的应用 投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门 市部,拟议中有10个位置A;(=1,2,3,…,10)可供选择,考虑到各地 区居民的消费水平及居民居住密集度,规定 在东区由A1,A2,A3三个点至多选择两个; 在西区由A4,A5两个点中至少选一个; 在南区由A,A两个点中至少选一个; 在北区由A,A,A10三个点中至少选两个。 A A A A 投资额10012015080709080140160180 利润36405022203025485861 A;各点的设备投资及每年可获利润由于地点不同都是不一样的,预测 情况见表所示(单位:万元)。但投资总额不能超过720万元,问应选择哪 几个销售点,可使年利润为最大? 管理蓦
管 理 运 筹 学 6 §3 整数规划的应用 一、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门 市部，拟议中有10个位置Aj (j＝1，2，3，…，10)可供选择，考虑到各地 区居民的消费水平及居民居住密集度，规定： 在东区由A1， A2 ，A3 三个点至多选择两个； 在西区由A4， A5 两个点中至少选一个； 在南区由A6， A7 两个点中至少选一个； 在北区由A8， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测 情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪 几个销售点，可使年利润为最大? A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 投资额 100 120 150 80 70 90 80 140 160 180 利润 36 40 50 22 20 30 25 48 58 61
§3蓬数规划的应用 解:设:0-1变量x1=1(A1点被选用)或0(A1点没被选用)。 这样我们可建立如下的数学模型: Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x+58x+61x10 s.t.100x1+120x+150x+80x4+70x5+90x6+80x7+140x8+160xg+180x10 ≤720 x1+x2+x3≤2 X+石+x10≥2 x1≥0且x为0-1变量,i=1,2,3,……,10 管理蓦
管 理 运 筹 学 7 §3 整数规划的应用 解：设：0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 且xj 为0--1变量，i = 1,2,3,……,10
§3整教规划的应用 固定成本问题 例5.高压容器公司制造小、中、大三种尺寸的金属容器, 所用资源为金属板、劳动力和机器设备,制造一个容器所需 的各种资源的数量如表所示。不考虑固定费用,每种容器 售出一只所得的利润分别为4万元、5万元、6万元,可使用的 金属板有500吨,劳动力有300人/月,机器有100台/月,此外 不管每种容器制造的数量是多少,都要支付一笔固定的费用: 小号是100万元,中号为150万元,大号为200万元。现在要制 定一个生产计划,使获得的利润为最大。 资源 小号容器中号容器大号容器 金属板(吨) 4 劳动力(人月) 机器设备(台月) 221 2
管 理 运 筹 学 8 §3 整数规划的应用 二、固定成本问题 例5．高压容器公司制造小、中、大三种尺寸的金属容器， 所用资源为金属板、劳动力和机器设备，制造一个容器所需 的各种资源的数量如表所示。不考虑固定费用，每种容器 售出一只所得的利润分别为 4万元、5万元、6万元，可使用的 金属板有500吨，劳动力有300人/月，机器有100台/月，此外 不管每种容器制造的数量是多少，都要支付一笔固定的费用： 小号是l00万元，中号为150 万元，大号为200万元。现在要制 定一个生产计划，使获得的利润为最大。 资源 小号容器 中号容器 大号容器 金属板（吨） 2 4 8 劳动力（人月） 2 3 4 机器设备（台月） 1 2 3
§3整教规划的应用 解:这是一个整数规划的问题。 设x1,x2,x3分别为小号容器、中号容器和大号容器的生产数量。各 种容器的固定费用只有在生产该种容器时才投入,为了说明固定费用的这 种性质,设y;=1(当生产第i种容器,即x;>0时)或0(当不生产第种容 器即x1=0时)。 引入约束x≤My1,i=1,2,3,M充分大,以保证当y=0时,x 0 这样我们可建立如下的数学模型: Maxz=4x1+5x2+6x3-100y1-150y2-200y s.t2x1+4x2+8x3≤500 2xx9+3x2≤100 +3x2+4x3≤300 x;SMy,i=1,2,3,M充分大 x≥0y;为0--1变量,i=1,2,3 管理筹学
管 理 运 筹 学 9 §3 整数规划的应用 解：这是一个整数规划的问题。 设x1，x2，x3 分别为小号容器、中号容器和大号容器的生产数量。各 种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这 种性质，设yi = 1(当生产第i种容器, 即 xi ＞ 0 时) 或0（当不生产第i种容 器即 xi = 0 时）。 引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以保证当yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型： Max z = 4x 1 + 5x 2 + 6x 3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x 2 + 8x 3 ≤ 500 2x1 + 3x 2 + 4x 3 ≤ 300 x 1 + 2x 2 + 3x 3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 x j ≥ 0 y j 为0--1变量，i = 1,2,3
§3整教规划的应用 三、指派问题 有n项不同的任务,恰好n个人可分别承担这些任务,但由 于每人特长不同,完成各项任务的效率等情况也不同。现假设必须 指派每个人去完成一项任务,怎样把n项任务指派给n个人,使 得完成n项任务的总的效率最髙,这就是指派问题。 例6.有四个工人,要分别指派他们完成四项不同的工作,每 人做各项工作所消耗的时间如下表所示,问应如何指派工作,才能 使总的消耗时间为最少 工作 A B 工人 15 18 21 24 19 18 26 1716 19 19 21 23 运筹 10
管 理 运 筹 学 10 §3 整数规划的应用 三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由 于每人特长不同，完成各项任务的效率等情况也不同。现假设必须 指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使 得完成 n 项任务的总的效率最高，这就是指派问题。 例6．有四个工人，要分别指派他们完成四项不同的工作，每 人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能 使总的消耗时间为最少。 工作 工人 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17