管理运筹学-2课件.pptVIP

第八章 整数规划 §1 整数规划的图解法 §2整数规划的计算机求解 §3整数规划的应用 §4整数规划的分枝定界法 §1 整数规划的图解法 例1. 某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备 需要A、B两种材 料的消耗以及资 源的限制，如右 表。 问题：工厂应分 别生产多少件甲、乙种仪器设备才 能使工厂获利最多？ §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变量 §3整数规划的应用(1) 一、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每 年可获利润由于地点不同都是 不一样的，预测情况见右表所 示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大? 二、固定成本问题 例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 §4整数规划的分枝定界法(1) 问题（A） Min z = c1 x1 + c2 x2 + … + cn xn 记 问题（B）为去掉整数约束的问题（A） s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… ……