《整数线性规划》PPT课件.ppt

第七章整数线性规划 西北农林科技大学 教师 朱玉春教授单位 经济管理学院2011年 本章主要内容 7 1整数线性规划的的分类7 2全整数线性规划的图解法7 3含有0 1变量的整数线性规划的应用7 40 1整数变量在建模过程中的灵活性分析 7 1整数线性规划的的分类 本章将讨论这样一类问题 这类问题可以被构建成线性规划的模型 并且其中至少有一个变量是整数 此类问题称作整数线性规划问题 如果所有变量均为整数 就称其为全整数线性规划 例 max2x1 3x2s t 3x1 3x2 122 3x1 x2 4x1 2x2 6x1 x2 0 且为整数请注意 如果去掉次模型中的 整数 一词 我们将得到我们所熟悉的双变量线性规划 去掉整数要求后得到的线性规划称做整数线性规划的LP松弛 如果只有一些变量是整数而非全部都是 则称做混合整数线性规划 例 max3x1 4x2s t x1 2x2 8x1 2x2 122x1 x2 16x1 x2 0 且x2为整数去掉 x2为整数 这个条件后 我们将得到此混合整数线性规划的LP松弛 另外 在某些应用软件中 整数变量只能取0或1 这类规划被称做0 1整数线性规划 7 1整数线性规划的的分类 7 2全整数线性规划的图解法 案例 伊斯特伯恩房地产公司有200万美元可用于购买新的租赁财产 经筛选 公司已将投资项目的方案减少为联体别墅和公寓楼 每套联体别墅售价282000美元 现有5套空置 每幢公寓楼售价400000美元 而且开发商可以根据伊斯特伯恩的需要数量建房 伊斯特伯恩的财产经理每月可以有140小时用来处理这些新置的财产 其中 每套联体别墅预计每月要花4小时 每幢公寓楼预计每月40小时 扣除抵押偿还和经营成本后 年现金流量预计为 每套联体别墅10000美元 每幢公寓楼15000美元 伊斯特伯恩的股东想知道在保证年现金流量最大的要求下 购买联体别墅和公寓楼的数量 我们先定义决策变量如下 T 联体别墅的数量A 公寓楼的数量伊斯特伯恩房地产问题的模型即为如下全整数线性规划 max10T 15As t 282T 400A 2000可用资金4T 40A 140管理者的时间T 5可得联体别墅T A 0 且为整数 7 2全整数线性规划的图解法 7 2 1LP松弛的图解法我们去掉T和A为整数的条件 重新来求解伊斯特伯恩公司的LP松弛问题 运用第二章中的图解步骤 图7 1即为最优的线性规划解法 即T 2 479套联体别墅 A 3 252幢公寓楼 目标函数的最优值为73 574 但伊斯特伯恩无法购买零星数量的联体别墅和公寓楼 所以需要进一步分析 7 2全整数线性规划的图解法 最优解LP松弛T 2 479 A 3 252 目标函数 73 574 可行域 图7 1 7 2全整数线性规划的图解法 7 2全整数线性规划的图解法 7 2 2近似整数解的获得大多数情况下 可以通过使用本节的方法来求得可接受的整数解 例如 关于生产进度问题求得的线性规划结果可能要求生产15132 4箱谷类食品 其近似结果为15132箱 而近似解对目标函数的值及其结果的可行性只产生极小的影响 因此 近似是一个较好的方法 实际上 只要对目标函数的约束条件只产生极小的影响 大多数管理者都可以接受 此时 一个近似解就够了 然而近似并不是一个万能的方法 当决策变量取很小的数值就对目标函数的值和结果的可行性产生较大影响时 就需要一个最优的整数解 以伊斯特伯恩问题为例 假设我们把LP松弛的解近似到整数 T 2 A 3 于是目标函数值为 10 2 15 3 65 而65000美元的年现金流比LP松弛的结果73754美元少很多 那么有没有其他可能的近似解 对其他近似方法研究表明 整数结果T 3 A 3不可行 因为这样资金就超过了伊斯特伯恩公司现有的2000000美元 同理 T 2 A 4也不可行 在这样的情况下 近似得到此问题的最可行的整数结果 2套联体别墅 3幢公寓楼和65000美元的年现金流 但我们并不知道这一结果是否为该问题的最优整数结果 近似到整数解是一个反复试验的方法 每一个近似解都必须经过可行性检验和对目标函数值影响的检查 即使当近似解是可行时 我们也无法保证我们找到了最优整数解 稍后我们会发现近似解 T 2 A 3 不是以上问题的最优解 7 2全整数线性规划的图解法 7 2全整数线性规划的图解法 联体别墅可得能力约束 管理者时间约束 6 5 4 3 2 1 0 A T 123456 可得资金约束 联体别墅的数量 公寓楼的数量 图7 2 可行域 目标函数 70 最优整数解T 4 A 2 7 2 3全整数问题的图解法 图7 2说明了用图解法求解伊斯特伯恩房地产整数线性规划问题中所需做的变化 首先 可行域图几乎和LP松弛问题的一样 然后 因为最优解一定是整数型的 我们可以标出可行的整数解 最后 不是将目标函数向可行域的极值点移动 而是尽量将它朝着使目标函数最优的方向移动 参看图7 2 我们得到最优解T 4 A 3 年现金流70000美元 这一结果比近似得到的最优解T 2 A 3 年现金流65000美元好的多 所以我们可以看到近似法并不是伊斯特伯恩公司房地产问题的最好的求解方法 7 2全整数线性规划的图解法 7 2全整数线性规划的图解法 7 2 4应用LP松弛法建立约束边界从伊斯特伯恩房地产问题的研究中 我们可以得出一个结论 一定要处理好最有整数解的值和LP松弛后的最优解的值之间的关系 在含有最大化问题的整数线性规划中 LP松弛后的最优解的值就是最优整数解的值的上限 在含有最小化问题的整数线性规划中 LP松弛后的最优解的值就是最优整数解的值的下限 通过LP松弛的上下限特性 我们可以得出结论 如果LP松弛的解恰好是整数 那么 它也是该整数线性规划的最优解 这一上下限的特性也可以用来确定近似解是否 足够好 如果一个近似的LP松弛是可行的 并能使得到的目标函数值同LP松弛的目标函数值几乎一样好 我们就认为该近似解是最优近似整数解 因此 我们也可以不用整数线性规划来求解问题 整数线性规划在构建模型上的灵活性很大程度上是由于使用了0 1变量 在很多应用中 如果采取相应行动 则变量值取1 否则取0 0 1变量因此而提供着选择的功能 本节所讲的资金预算 固定成本核算 分布系统设计 银行选址 产品设计和市场份额的应用问题都用到了0 1变量 7 3含有0 1变量的整数线性规划的应用 7 3含有0 1变量的整数线性规划的应用 7 3 1资金预算案例 爱斯柯德冰箱公司正在考虑随后四年内的投资方案 这些方案有着不同的资金需求 面对每年有限的资金 管理者需要选择最好的方案 每种方案的估计净现值 资金需求和4年内的可用资金见课本204页表7 1 在资金预算问题中 公司的目标函数是使资金预算的净现值最大化 此问题有4个约束条件 其一是4年中每年的可用资金 4个0 1决策变量如下 如果工厂扩建方案通过 P 1 如果否决 P 0 如果仓库扩建方案通过 W 1 如果否决 W 0 如果机器更新方案通过 M 1 如果否决 M 0 如果新产品研发方案通过 R 1 如果否决 R 0 该0 1整数线性规划模型如下 Max90P 40W 10M 37RS t 15P 10W 10M 15R 40第一年的可用资金20P 15W 10R 50第二年的可用资金20P 20W 10R 40第三年的可用资金15P 5W 4M 10R 35第四年的可用资金P W M R 0 1该模型的求解可用管理科学家软件进行处理 详见课本204页 7 3含有0 1变量的整数线性规划的应用 7 3含有0 1变量的整数线性规划的应用 7 3 2固定成本核算在许多应用中 产品的成本由两部分构成 其一为配置成本 即固定成本 其二为可变成本 直接与产量有关 0 1变量的应用 使得在生产应用软件包中考虑配置成本成为可能 我们将RMC问题视为固定成本问题的例子 三种原料用来生产三种产品 一种燃料添加剂 一种溶剂 一种地板清洁剂 使用以下决策变量 F 生产的燃料添加剂的吨数S 生产的溶剂的吨数C 生产的地板清洁剂的吨数 RMC问题的一个线性规划模型如下 Max40F 30S 50CS t 0 4F 0 5S 0 6C 20原料一0 2S 0 1C 5原料二0 6F 0 3S 0 3C 21原料三F S C 0运用管理科学家软件的规划模型 我们得到一个最优解 27 5吨燃料添加剂 0吨溶剂和15吨地板清洁剂 总价值1850美元 7 3含有0 1变量的整数线性规划的应用 RMC问题的这一线性规划问题并不包含这些产品的配置成本 假设已知配置成本和三种产品的最高产量 我们现在可以利用0 1变量带来的建模灵活性 把固定的配置成本加入到生产模型中 0 1变量定义如下 如果生产燃料添加剂 则SF 1 否则 SF 0 如果生产溶剂 则SS 1 否则 SS 0 如果生产地板清洁剂 则SC 1 否则 SC 0 我们可以得到RMC问题的固定成本模型 Max40F 30S 50C 200SF 50SS 400SCS t 0 4F 0 5S 0 6C 20原料一0 2S 0 1C 5原料二 7 3含有0 1变量的整数线性规划的应用 0 6F 0 3S 0 3C 21原料三F 50SF 0F的最大值S 25SS 0S的最大值C 40SC 0C的最大值F S C 0 SF SS SC 0 1用管理科学家软件求解含有配置成本的RMC问题 最优解为25吨燃料添加剂和20吨溶剂 扣除配置成本后的目标函数值为1350美元 燃料添加剂和溶剂的配置成本为200 50 250美元 最优解的结果为SC 0 表示应取消昂贵的400美元的地板清洁剂配置成本 因此不应生产地板清洁剂 7 3含有0 1变量的整数线性规划的应用 7 3含有0 1变量的整数线性规划的应用 7 3 3分布系统设计案例 马丁贝克公司在圣路易斯经营一家年产量为30000件产品的工厂 产品被运输到位于波士顿 亚特兰大和休斯敦的地区分销中心 由于预期将有需求的增长 马丁贝克公司计划在底特律 托莱多 丹佛和堪萨斯城中的一个或多个城市建立新工厂以增加生产力 在上述四个城市建立工厂的年固定成本和年生产能力 以及每件产品从各工厂到各分销中心的运费详见教材207页 现在说明在该分布系统设计问题中 如何应用0 1变量建立模型来选择最优的厂址 确定从各工厂到各分销中心的运输量 我们可以用以下的0 1变量来表示建立工厂的决策 如果在底特律建厂 y1 1 否则 y1 0 如果在托莱多建厂 y2 1 否则 y2 0 如果在丹佛建厂 y3 1 否则 y3 0 如果在堪萨斯建厂 y4 1 否则 y4 0 对各工厂到每个中心的运输量变量的定义和运输问题中的相同 xij 工厂i到分销中心j的运输量其中 i 1 2 3 4 5 且j 1 2 3 7 3含有0 1变量的整数线性规划的应用 马丁贝克公司的目标函数为 年运输成本与经营新建立的工厂的年固定成本之和最小化 于是 我们得到了马丁贝克公司的分布系统设计问题的完整模型 min5x11 2x12 3x13 4x21 3x22 4x23 9x31 7x32 5x33 10 x41 4x42 2x43 8x51 4x52 3x53 175y1 300y2 375y3 500y4s t x11 x12 x13 10y1 0底特律的生产能力x21 x22 x23 20y2 0托莱多的生产能力x31 x32 x33 30y3 0丹佛的生产能力x41 x42 x43 40y4 0堪萨斯城的生产能力x51 x52 x53 30圣路易斯的生产能力 7 3含有0 1变量的整数线性规划的应用 x11 x21 x31 x41 x51 30波士顿的需求x12 x22 x32 x42 x52 20亚特兰大的需求x13 x23 x33 x43 x53 20休斯敦的需求对所有的i j 有xij 0 y1 y2 y3 y4 0 1 利用管理科学家软件的整数线性规划模型 我们得到最优解 最优解说明要在堪萨斯建立一个工厂 y4 1 从堪萨斯到亚特兰大运输20000件产品 x42 20 从堪萨斯到休斯敦运输20000件产品 x43 20 从圣路易斯到波士顿运输30000件产品 x51 30 注意 包括堪萨斯工厂的固定成本500000美元在内 该解所得到的总成本为860000美元 7 3含有0 1变量的整数线性规划的应用 7 3 4银行选址案例 俄亥俄州信托公司的长期计划部再考虑在俄亥俄州东北部20个郡的地区开展业务 俄亥俄州信托公司目前在这20个郡没有一个营业处 根据该州相关法律 如果一个银行在任一个郡建立一个主营业处 即可在该郡及所有毗邻郡建立分行 但是 为了建立一个主营业处 俄亥俄州信托公司必须获得本州银行管理者的批准 或者购买一家当地现存的银行 计划的第一步 俄亥俄州信托公司需要确定将来在这20个郡全部都营业总共需要建立的主营业处的最小数目 可用一个整数规划模型来求解俄亥俄州信托公司的选址问题 我们定义变量如下 如在i郡建立主营业处 则xi 1 否则 xi 0 为了得到所需主营业处的最小数目 我们将目标函数写为 minx1 x2 x20 7 3含有0 1变量的整数线性规划的应用 该银行选址问题的完整表述如下 minx1 x2 x20s t x1 x2 x12 x16 1阿什特比拉郡x1 x2 x3 x12 1莱克郡 x11 x14 x19 x20 1卡罗尔郡xi 0 1i 1 2 20利用管理科学家软件求解这个含有20个变量 20个约束条件的函数 我们得知最优解为 需要在阿什兰 斯塔克 吉奥特设立主营业处 其他所有决策变量的最优值都为0 即不需要在这些郡设立主营业处 7 3含有0 1变量的整数线性规划的应用 7 3 5产品设计和市场份额的最优化联合分析是一种市场研究方法 通过该种方法可以了解预期的购买者如何评价产品的属性 本节将说明如何把联合分析的结果应用到产品设计和市场份额最优化问题的整数线性规划模型中去 案例 塞伦食品公司计划进入冷冻比萨饼市场 目前已有两个品牌 安东澳和国王 它们占据了主要的市场份额 塞伦准备开发一种香肠比萨饼 并想以之夺取大量市场份额 为了使其品牌获得成功 塞伦食品公司意识到必须诱使市场上的消费者从他们中意的比萨饼品牌转变到塞伦的产品上来 假设目前所研究的抽样调查的8位顾客可以代表整个冷冻香肠比萨市场 那么我们就可以列出并解决一个整数线性规划模型来帮助塞伦得出设计方案 在市场营销领域 这个问题被称为份额选择问题 7 3含有0 1变量的整数线性规划的应用 7 3含有0 1变量的整数线性规划的应用 7 3含有0 1变量的整数线性规划的应用 7 40 1整数变量在建模过程中的灵活性分析 7 40 1整数变量在建模过程中的灵活性分析 7 4 1多重选择和互斥约束请回顾一下前一节中讲到的爱斯柯德冰箱公司的资金预算问题 其决策变量的定义如下 P 1 表示执行公司扩建方案 否则取0 W 1 表示执行仓库扩建方案 否则取0 M 1 表示执行新机器方案 否则取0 R 1 表示执行新产品研制方案 否则取0 假设爱斯柯德公司不是执行扩建一个仓库的方案 而是需要考虑扩建三个仓库的方案 其中有一个仓库必须被扩建以迎合增长的产品需求 但是新增需求还没有达到必须扩建一个以上的仓库 下面定义的变量和多重选择约束 实际上可以考虑用0 1整数线性规划模型 从而反映爱斯柯德公司目前所面临的局面 如果扩建现有仓库的方案通过 W1 1 否则 W1 0 如果扩建第二个仓库的方案通过 W2 1 否则 W2 0 如果扩建第三个仓库的方案通过 W3 1 否则 W3 0 由于要求这些方案中只能执行其中一个方案 则反映这一要求的多重选择约束为 W1 W2 W3 1 如果W1 W2和W3为0 1变量 则意味着只能从这些方案中选择其一 如果不要求必须扩建一个仓库 则多重选择约束条件可以写成 W1 W2 W3 1 该多重选择约束条件允许不扩建任何仓库的 W1 W2 W3 0 情况出现 但不允许出现扩建一个以上的仓库的情况 这种多重选择约束条件称为互斥约束 7 40 1整数变量在建模过程中的灵活性分析 7 40 1整数变量在建模过程中的灵活性分析 7 4 2n选k约束将多重选择约束概念延伸就可以很容易得出n个方案中挑选k个方案的模型 也即n选k约束 设W1 W2 W3 W4和W5代表五个潜在的仓库扩建方案 并且在这五个方案中至少必须执行二个 那么这个约束条件可以写成 W1 W2 W3 W4 W5 2如果五个方案中执行的方案不能超过二个 则约束条件可写成 W1 W2 W3 W4 W5 2当然 这里使用的变量都是0 1变量 7 40 1整数变量在建模过程中的灵活性分析 7 4 3条件约束和并行约束很多时候 必须执行一个方案才能触发另一个方案执行 例如 爱斯柯德公司的工厂扩建方案是仓库扩建方案的必备条件 我们用P代表工厂扩建方案 而用W代表仓库扩建方案 则需要引入条件约束来反映该要求 W P W和P必须为0 1变量 而且 P为0 则W就只能取0 而P取1 则W也有可能取1 这样 工厂和仓库才能被扩建 然而 必须指出 执行工厂扩建方案 并不要求一定执行仓库扩建方案 而如果我们要求不管工厂扩建方案执行与否 都必须执行仓库扩建的方案 反之亦然 我们就说P和W是并行约束 对于这种情形 可以用一个简单的等式来表达 W P 同样 P和W也仅限于0 1变量 7 40 1整数变量在建模过程中的灵活性分析 7 4 4关于灵敏度分析的讨论在线性规划问题中 特别是整数线性规划问题 灵敏度分析起到至关重要的作用 在一些应用中经常可以看到 当约束条件中某个参数发生很小的变化 就可能使得最优解的值产生很大的波动 下面我们考虑一个针对简单资本预算问题而构建的线性规划模型 它包括4个方案和一段时期内的预算约束条件 max40 x1 60 x2 70 x3 160 x4s t 16x1 35x2 45x3 85x4 100 x1 x2 x3 x4 0 1 我们可以简单地使用枚举法求出最优解 即x1 1 x2 1 x3 1 x4 0 且目标函数的值为170美元 但是 如果预算变量增加1美元 比如从100美元增加到101美元 则最优解的值就会变成 x1 1 x2 0 x3 0 x4 1 目标函数也会相应变成200美元 也即 预算中增加1美元就会导致收入增加30美元 管理层当然很乐意遇到这种情况 也乐意去增加1美元的预算 从这个资金预算问题中 我们可以看到 由于最优解的值对预算资金这个条件参数有着极大的灵敏反应 人们通常建议在选择最后实施的最优解之前 先对各个条件参数稍加改变 多求解几次最优解的值 7 40 1整数变量在建模过程中的灵活性分析