第八章蓑教规 §1整数规划的图解法 §2整数规划的计算机求解 §3整数规划的应用 §4整数规划的分枝定界法
第八章 整数规划 §1 整数规划的图解法 §2整数规划的计算机求解 §3整数规划的应用 §4整数规划的分枝定界法
§1整数规划的图解法 例1.某工厂在计划期内要安排甲、乙两种仪器设备的生产,已知生产仪器设备 需要A、B两种材 乙 资源限制 料的消耗以及资 材料A 2 源的限制,如右 材料B 0 表 单件获利1万元1万元 问题:工厂应分 别生产多少件甲、乙种仪器设备才 能使工厂获利最多? 解 目标函数:Maxz=x1+x2 约束条件:st 3x+2x=10 3X1+2x2<10 2x x1,x2≥0为整数 不考虑整数约束得到最优解: X1=1.667,X2=2.5 4.167 x1+2x2=6 考虑整数约束得到最优解: X1=2,x2=2; 4 整数规划的最优目标值小于相应 目标函数 等值线 线性规划的最优目标值(相当于附加一个约束) 图6.4.1
§1 整数规划的图解法 例1. 某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备 需要A、B两种材 料的消耗以及资 源的限制，如右 表。 问题：工厂应分 别生产多少件甲、乙种仪器设备才 能使工厂获利最多？ 甲 乙 资源限制 材料 A 3 2 10 材料 B 0 2 5 单件获利 1 万元 1 万元 解、 目标函数： Max z = x1 + x2 约束条件： s.t. 3 x1 + 2 x2 ≤ 10 2 x2 ≤ 5 x1，x2 ≥ 0 为整数 不考虑整数约束得到最优解： x1 =1.667， x2 = 2.5；z = 4.167 考虑整数约束得到最优解： x1 = 2， x2 = 2； z = 4 整数规划的最优目标值小于相应 线性规划的最优目标值(相当于附加一个约束)
§2蓬数规划的计算机求解 例2: 例2: Maxz=15x1+10x2+7x3 Max z= 15x+ 10xo t 7x s. t 5x1-10x2+7x3≤8 5x1-10x2+7x3≤8 6 4 22 +8x2≤12 6x1+4x2+ x2 8X2≤12 3x1+2x2+2x3≤10 3x1+2x2+2x3≤10 x1,x2,x3≥0为整数 x1,X2,X2≥0 x3为整数x1为0-1变量 用《管理运筹学》软件求解得: 0 X3 用《管理运筹学》软件求解得: 0
§2整数规划的计算机求解 例2： Max z = 15x1 + 10x2 + 7x3 s.t. 5x1 - 10x2 + 7x3 ≤ 8 6x1 + 4x2 + 8x3 ≤ 12 -3x1 + 2x2 + 2x3 ≤ 10 x1,x2,x3 ≥ 0 为整数 例2： Max z = 15x1 + 10x2 + 7x3 s.t. 5x1 - 10x2 + 7x3 ≤ 8 6x1 + 4x2 + 8x3 ≤ 12 -3x1 + 2x2 + 2x3 ≤ 10 x1,x2,x3 ≥ 0 x3 为整数 x1 为0-1变量 用《管理运筹学》软件求解得： x1 = 0 x2 = 3 x3 = 0 z = 30 用《管理运筹学》软件求解得： x1 = 1 x2 = 1.5 x3 = 0 z = 30
§3数规划的应用(1) 、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有10个 位置A(=1,2,3,…,10)可供选择,考虑到各地区居民的消费水平及居民居住密集 度,规定 在东区由A1,A2,A3三个点至多选择两个; 在西区由A4,A5两个点中至少选一个 在南区由A6,A7两个点中至少选一个 在北区由A3,A,A10三个点中至少选两个 A各点的设备投资及每 AIA2A3 A4 A, A8 A 年可获利润由于地点不同都是[投资额10012015080709080140160180 不一样的,预测情况见右表所L利润36405022203025485861 示(单位:万元)。但投资总额不能超过720万元,问应选择哪几个销售点,可使年利润为最 大 解:设:0-1变量x=1(A点被选用)或0(A1点没被选用)。 这样我们可建立如下的数学模型 axz=36x1+40x2+50x3+22x4+20x+30x6+25x2+48X8+58形+61x1o s.t.100x1+120x2+150x3+80x1+70x5+90x6+80x2+140x+160x+180x0≤720 X x8+x+x10≥2 x1≥0x1为0--1变量,i=1,2,3,…,10
§3整数规划的应用(1) 一、投资场所的选择 例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 解：设：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数规划的应用(2) 固定成本问题 例5.高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机 器设备,制造一个容器所需的各种资源的数量如右 资源 小号容器中号容器大号容器 表所示。不考虑固定费用,每种容器售出一只所得金属板(吨 的利润分别为4万元、5万元、6万元,可使用的金 劳动力(人月) 机器设备(台月) 221 432 843 属板有500吨,劳动力有300人月,机器有100台月, 此外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是100万元,中号为150 万元,大号为200万元。现在要制定一个生产计划,使获得的利润为最大。 解:这是一个整数规划的问题。 设x1,x2,x3分别为小号容器、中号容器和大号容器的生产数量 各种容器的固定费用只有在生产该种容器时才投入,为了说明固定费用的这种性质,设 =1(当生产第i种容器,即x1>0时)或0(当不生产第i种容器即x1=0时) 引入约束x1≤My,i=1,2,3,M充分大,以保证当y=0时,x1=0。 这样我们可建立如下的数学模型: axz=4x1+5x2+6x3-1 150y2-200 t.2x1+4x2+8x3≤500 2x1+3x2+4x3≤300 x1+2x2+3x3≤100 x1≤My,i=1,2,3,M充分大 x≥0y1为0--1变量,i=1,2,3
二、固定成本问题 例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机 器设备，制造一个容器所需的各种资源的数量如右 表所示。不考虑固定费用，每种容器售出一只所得 的利润分别为 4万元、5万元、6万元，可使用的金 属板有500吨，劳动力有300人月，机器有100台月， 此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 解：这是一个整数规划的问题。 设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 = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 为0--1变量，i = 1,2,3 §3整数规划的应用(2) 资源 小号容器 中号容器 大号容器 金属板（吨） 2 4 8 劳动力（人月） 2 3 4 机器设备（台月） 1 2 3