整数线性规划.ppt

第七章 整数线性规划,西北农林科技大学,教 师：朱玉春 教授单 位：经济管理学院 2011年,本章主要内容,7.1 整数线性规划的的分类7.2 全整数线性规划的图解法7.3 含有0-1变量的整数线性规划的应用7.4 0-1整数变量在建模过程中的灵活性 分析,7.1 整数线性规划的的分类,本章将讨论这样一类问题，这类问题可以被构建成线性规划的模型，并且其中至少有一个变量是整数。此类问题称作整数线性规划问题。如果所有变量均为整数，就称其为全整数线性规划。例：max 2x1+3x2 s.t.3x1+3x212 2/3x1+x2 4 x1+2x2 6 x1，x20，且为整数 请注意，如果去掉次模型中的“整数”一词，我们将得到我们所熟悉的双变量线性规划。去掉整数要求后得到的线性规划称做整数线性规划的LP松弛。,如果只有一些变量是整数而非全部都是，则称做混合整数线性规划。例：max 3x1+4x2 s.t.-x1+2x2 8 x1+2x2 12 2x1+x2 16 x1，x2 0，且x2为整数 去掉“x2为整数”这个条件后，我们将得到此混合整数线性规划的LP松弛。另外，在某些应用软件中，整数变量只能取0或1，这类规划被称做0-1整数线性规划。,7.1 整数线性规划的的分类,7.2 全整数线性规划的图解法,案例：伊斯特伯恩房地产公司有200万美元可用于购买新的租赁财产。经筛选，公司已将投资项目的方案减少为联体别墅和公寓楼。每套联体别墅售价282000美元，现有5套空置。每幢公寓楼售价400000美元，而且开发商可以根据伊斯特伯恩的需要数量建房。伊斯特伯恩的财产经理每月可以有140小时用来处理这些新置的财产，其中，每套联体别墅预计每月要花4小时，每幢公寓楼预计每月40小时。扣除抵押偿还和经营成本后，年现金流量预计为：每套联体别墅10000美元；每幢公寓楼15000美元。伊斯特伯恩的股东想知道在保证年现金流量最大的要求下，购买联体别墅和公寓楼的数量。,我们先定义决策变量如下：T联体别墅的数量 A公寓楼的数量 伊斯特伯恩房地产问题的模型即为如下全整数线性规划：max 10T+15A s.t.282T+400A2000 可用资金 4T+40A140 管理者的时间 T 5 可得联体别墅 T，A0，且为整数,7.2 全整数线性规划的图解法,7.2.1 LP松弛的图解法 我们去掉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整数线性规划模型如下：Max 90P+40W+10M+37R S.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问题的一个线性规划模型如下：Max 40F+30S+50C S.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问题的固定成本模型：Max 40F+30S+50C-200SF-50SS-400SC S.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 0 F的最大值 S-25SS 0 S的最大值 C-40SC 0 C的最大值 F,S,C0；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变量的整数线性规划的应用,马丁贝克公司的目标函数为：年运输成本与经营新建立的工厂的年固定成本之和最小化。于是，我们得到了马丁贝克公司的分布系统设计问题的完整模型：min 5x11+2x12+3x13+4x21+3x22+4x23+9x31+7x32+5x33+10 x41+4x42+2x43+8x51+4x52+3x53+175y1+300y2+375y3+500y4 s.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。为了得到所需主营业处的最小数目，我们将目标函数写为：min x1+x2+.+x20,7.3 含有0-1变量的整数线性规划的应用,该银行选址问题的完整表述如下：min x1+x2+.+x20 s.t.x1+x2+x12+x16 1 阿什特比拉郡 x1+x2+x3+x12 1 莱克郡.x11+x14+x19+x20 1 卡罗尔郡 xi=0,1 i=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.4 0-1整数变量在建模过程中的灵活性分析,7.4 0-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.4 0-1整数变量在建模过程中的灵活性分析,7.4 0-1整数变量在建模过程中的灵活性分析,7.4.2 n选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.4 0-1整数变量在建模过程中的灵活性分析,7.4.3 条件约束和并行约束 很多时候，必须执行一个方案才能触发另一个方案执行。例如，爱斯柯德公司的工厂扩建方案是仓库扩建方案的必备条件。我们用P代表工厂扩建方案，而用W代表仓库扩建方案，则需要引入条件约束来反映该要求：WP。W和P必须为0-1变量。而且，P为0，则W就只能取0；而P取1，则W也有可能取1。这样，工厂和仓库才能被扩建。然而，必须指出，执行工厂扩建方案，并不要求一定执行仓库扩建方案。而如果我们要求不管工厂扩建方案执行与否，都必须执行仓库扩建的方案，反之亦然，我们就说P和W是并行约束。对于这种情形，可以用一个简单的等式来表达：W=P。同样，P和W也仅限于0-1变量。,7.4 0-1整数变量在建模过程中的灵活性分析,7.4.4 关于灵敏度分析的讨论 在线性规划问题中，特别是整数线性规划问题，灵敏度分析起到至关重要的作用。在一些应用中经常可以看到，当约束条件中某个参数发生很小的变化，就可能使得最优解的值产生很大的波动。下面我们考虑一个针对简单资本预算问题而构建的线性规划模型，它包括4个方案和一段时期内的预算约束条件。max 40 x1+60 x2+70 x3+160 x4 s.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.4 0-1整数变量在建模过程中的灵活性分析,