运筹学--0-1整数规划.ppt

一、相互排斥的计划 例4.6 某公司拟在市东、西、南三区中建立门市部，有例7个点Ai（i＝1，2，…，7）可供选择，要求满足以下条件： 1) 在东区，在A1，A2，A3三个点中至多选两个； 2) 在西区，A4，A5两个点中至少选一个； 3) 在南区，A6，A7两个点为互斥点。 4) 选A2点必选A5点。 若Ai点投资为bi万元，每年可获利润为ci万元，投资总额为B万元，试建立利润最大化的0－1规划模型。 第四节 0－1整数规划 解：设决策变量为 建立0－1规划模型如下： 解：设决策变量为 建立0－1规划模型如下： 在东区，在A1，A2，A3三个点中至多选两个； 2) 在西区，A4，A5两个点中至少选一个； 3) 在南区，A6，A7两个点为互斥点; 4) 选A2点必选A5点。 例4.7 某产品有A1和A2两种型号，需要经过B1、B2、B3三道工序，单位工时和利润、各工序每周工时限制见表所示，问工厂如何安排生产，才能使总利润最大？（B3工序有两种加工方式B31和B32，产品为整数）。 二、互排斥的约束条件 工序 型号 B1 B2 B3 利润 （元/件） B31 B32 A1 A2 0.3 0.7 0.2 0.1 0.3 0.5 0.2 0.4 25 40 每周工时(小时/月) 250 100 150 120 解：设A1、A2产品的生产数量分别为x1、x2件，在不考虑B31和B32相互排斥的情况下，问题的数学模型为 工序B3只能从两种加工方式中选择一种，那么约束条件（1）和（2）就成为相互排斥的约束条件。为了统一在一个问题中，引入0-1变量 则数学模型为 一般地，在建立数学模型时，若需从p个约束条件中选择q个约束条件，则可以引入p个0-1变量 那么约束条件组 三、固定成本问题 例4.8 某公司制造小、中、大三种尺寸的容器，所需资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示：不考虑固定费用，小、中、大号容器每售出一个其利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，另外若生产，不管每种容器生产多少，都需要支付一笔固定费用：小号为100万元，中号为150万元，大号为200万元。问如何制定生产计划使获得的利润对大？ 资源 小号容器 中号容器 大号容器 限量 金属板（吨） 2 4 8 500 劳动力（人/月） 2 3 4 300 机器设备（台/月） 1 2 3 100 利润（万元/台） 4 5 6 固定费用（万元） 100 150 250 解：设x1、x2、x3分别为小号容器、中号容器、大号容器的生产数量。不考虑固定费用，则问题的数学模型为 资源 小号容器 中号容器 大号容器 限量 金属板（吨） 2 4 8 500 劳动力（人/月） 2 3 4 300 机器设备（台/月） 1 2 3 100 利润（万元/台） 4 5 6 固定费用（万元） 100 150 250 若考虑固定费用就必须引入0—1变量： 则该问题的数学模型为 0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。 例一、求解下列0－1 规划问题 0－1 整数规划求解方法 约束条件 x1 . x2. x3 Z 值 (1) (2) (3) (4) 过滤条件 ( 0. 0. 0 ) 0 0 0 0 0 Z≥0 ( 0. 0. 1 ) 5 －1 1 0 1 Z≥5 ( 0. 1. 0 ) －2 ( 0. 1. 1 ) 3 ( 1. 0. 0 ) 3 ( 1. 0. 1 ) 8 0 2 1 1 Z≥8 ( 1. 1. 0 ) 1 ( 1. 1. 1 ) 6 解：对于0－1 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。 例二、求解下列0－1 规划问题 例二、求解下列0－1 规划问题 约束条件 x2. x1 . x4. x3 Z 值