第五讲-整数规划与指派问题.ppt

指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小。 可行解矩阵的每一行每一列只有一个元素为1，共有n个取1，其余取值为零。 同解变化 四、匈牙利解法 美国数学家W.Knhn于1955年给出的，由于他的解法运用了匈牙利数学家D.Konig关于矩阵零元素的一个定理，因此被称为匈牙利解法。 定理：对于指派问题，成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解。 定理：覆盖一个方阵内所有0元的最小直线数等于该阵中位于不同行、列的0元的最多个数； 基本思想（反复应用同解变换） 成本矩阵（效益矩阵）的每一行及每一列减去该行或列的最小数，使每行每列至少有一个0，假如能够从中找出n个位于不同行、列的0元，则为最优阵，对应最优解。 如果划去这些0所需要的直线数不少于n（等于n），则此时就可以求得最优解。 四、匈牙利解法（续） 练习 一般指派问题（非标准）： 最大化指派问题（效益矩阵） 人数和工作数不等的指派问题 一个人可做几项工作的指派问题 某项工作一定不能由某人做的指派问题 最大化指派问题 最大化指派问题 最大值 最小化指派问题 人数和工作数不等的指派问题 一个人可做几项工作的指派问题： A1可同时做三项工作 某项工作一定不能由某人做的指派问题： A1不能做B4; A3不能做B3 * * * * * 运筹学（整数规划问题） 李琳 运筹学（整数规划问题） 李琳 华东理工大学 East China University of Science And Technology 运筹学（整数规划问题） 李琳 * * 整 数 规 划 与 指派 问 题 内容提要 一、整数规划的应用 二、整数规划的求解方法概述 四、匈牙利解法 三、指派问题 一、整数规划的案例 案例1：集装箱托运问题 公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如下表所示: 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？ 货物 每件体积/立方英尺 每件重量/百千克 每件利润/百元 甲 195 4 2 乙 273 40 3 托运限制 1365 140 设 分别为甲、乙两种货物托运的件数，其数学规划模型如下： 一、整数规划的案例（续） 案例2：固定成本问题 高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表： 不考虑固定费用，每种容器售出一只所得的利润分别为4万元，5万元，6万元，可使用的金属板有500，劳动力有300人月，机器有100台月。 资源 小号容器 中号容器 大号容器 金属板 2 4 8 劳动力 2 3 4 机器设备 1 2 3 此外，不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号为100万元，中号为150万元，大号为200万元。现在要制定生产计划，使获得利润最大。 设 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，故设 扣除了固定费用的最大利润的目标函数为 约束条件1（资源限制）： 约束条件2（固定费用逻辑约束） 约束条件3： 可简化 一、整数规划的案例（续） 案例3：分布系统设计问题 企业在A1地已有一个工厂，其生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂，建厂的固定成本分别为175千元，300千元，375千元，500千元。其他信息见下表： B1 B2 B3 产量/千箱 A1 8 4 3 30 A2 5 2 3 10 A3 4 3 4 20 A4 9 7 5 30 A5 10 4 2 40 销量 30 20 20 （1）应该在哪几个地方建厂，在满足销量前提下，使得其总固定成本和总运输费用之和最小？ （2）由于政策要求必须在A2，A3 地建一个厂，应在哪几个地方建厂？ 解：设 为从 运往 的运输量， 固定成本及总运输费用最小的目标为 产量限制约束条件： 销量限制约束条件： （2）增加约束条件 二、整数规划的求解方法概述 整数线性规划，是要求整数解的线性规划，包括上班的人数、设备的台数、材料的件数等。 问题： 最优整数解是否可以对非整数解进行四舍五入法或者去尾法呢？ * * * * * * * * * * * * *