§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