整数规划-课件.ppt

《整数规划-课件.ppt》由会员分享，可在线阅读，更多相关《整数规划-课件.ppt（146页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、整整 数数 规规 划划整数规划整数规划整数规划问题与模型整数规划问题与模型割平面法和分支定界法割平面法和分支定界法0-10-1整数规划整数规划指派问题的匈牙利法指派问题的匈牙利法应用案例应用案例整数规划整数规划整数规划问题实例特点模型分类整数规划整数规划应用案例投资组合问题旅游售货员问题背包问题整数规划整数规划投资组合问题背 景实 例模 型整数规划整数规划背景证券投资证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润项目投资项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。整数规划整数规划案例某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资

2、一个。其中第 个项目需投资金额为 万元，预计5年后获利 万元 ，问应如何选择项目使得5年后总收益最大？整数规划整数规划模型变量每个项目是否投资约束总金额不超过限制目标总收益最大整数规划整数规划整数规划整数规划旅游售货员问题背景案例模型整数规划整数规划背景旅游线路安排 预定景点走且只走一次 路上时间最短配送线路货郎担问题 送货地到达一次 总路程最短案例有一旅行团从 出发要遍游城市 已知从 到 的旅费为 ，问应如何安排行程使总费用最小？整数规划整数规划模型变量是否从i第个城市到第j个城市约束 每个城市只能到达一次、离开一次整数规划整数规划目标总费用最小整数规划整数规划整数规划整数规划背包问题背景案

3、例模型整数规划整数规划背景邮递包裹 把形状可变的包裹用尽量少的车辆运走旅行背包 容量一定的背包里装尽可能的多的物品整数规划整数规划实例某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。整数规划整数规划物品12345678910体积2

4、00350500430320120700420250100价格1545100705075200902030整数规划整数规划问题分析变量变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中整数规划整数规划约束约束 包裹容量限制 必带物品限制 选带物品限制整数规划整数规划目标函数未带物品购买费用最小整数规划整数规划模型整数规划整数规划n特征特征变量整数性要求n来源来源 问题本身的要

5、求 引入的逻辑变量的需要n性质性质可行域是离散集合整数规划整数规划线性整数规划模型一般整数规划模型0-1整数规划模型混合整数规划模型一般整数规划模型返回0-1整数规划模型返回混合整数规划模型返回算 法与线性规划的关系分支定界算法割平面算法返回与线性规划的关系整数规划放松的线性规划可行解是放松问题的可行解最优值大于等于放松问题的最优值线性规划模型max z=x1+4x2s.t.14x1+42x2196 -x1+2x2 5 x1,x20整数规划模型max z=x1+4x2s.t.14x1+42x2196 -x1+2x2 5 x1,x20 x1,x2 为整数0 1 2 3 4 5 6 7 84321

6、A(2.6,3.8)B(5,3)整数线性规划（整数线性规划（ILP）实例）实例线性规划的最优解A(x1,x2)=(2.6,3.8)不是整数解，目标函数值为z=17.8。整数规划的最优解B(x1,x2)=(5,3)目标函数值为z=17。线性规划最优解A(2.6,3.8)四舍五入得到的解为(3,4)，不是可行解；舍去尾数取整的解为(2,3)，目标函数值z=14。因此整数规划的最优解一般不能由线性规划的最优解通过简单的取整得到。0 1 2 3 4 5 6 7 84321A(2.6,3.8)B(5,3)整数线性规划（整数线性规划（ILP）解的特点）解的特点nILPILP是其中是其中是其中是其中LPLP

7、的一个子问题，所有解也是的一个子问题，所有解也是的一个子问题，所有解也是的一个子问题，所有解也是LPLP的可行解，所以如果的可行解，所以如果的可行解，所以如果的可行解，所以如果LPLP的最优解满足的最优解满足的最优解满足的最优解满足ILPILP的的的的整数条件，则已得最优解。整数条件，则已得最优解。整数条件，则已得最优解。整数条件，则已得最优解。注释最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取分支定界算法算法思想算法步骤算例注释算法思想隐枚举法 分支 求解放松问题 舍弃 变界 分支最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比

8、界好整数规划分枝定界法整 数 规 划 在许多线性规划问题中,要求最优解必须取整数.例如所求的解是机器的台数、人数车辆船只数等.如果所得的解中决策变量为分数或小数则不符合实际问题的要求.对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划;如果仅要求部分决策变量取整数,称为混合整数规划问题.有的问题要求决策变量仅取0或l两个值,称为0-l规划问题.整数规划简称为IP问题.这里主要讨论的是整数线性规划问题,简称为ILP问题.对于整数线性规划问题,为了得到整数解,初看起来,似乎只要先不管整数要求,而求线性规划的解,然后将求得的非整数最优解“舍零取整”就可以了.但实际上,这个想法却常

9、常行不通,有时“舍零取整”后的整数解根本就不是可行解,有虽然为可行解,却不是最优解.例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托 运所受限制见表1.问每集装箱中两种货物各装多少箱,可使所获利润最大?表 1货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413解 设 分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题.其数学模型为:（1）若暂且不考虑 取整数这一条件.则(1)就变为下列线性规划:（2）我们将式(2)称为(1)的伴随规划.解(2)得到最优解:（3）但它不满足(1)的整数要求.因此它不是(1)的最优解,若把解(3)舍零取整,

10、如取X1=(5.0,0)T,但它不是式(1)的可行解.因为它不满足(1)中的约束条件,若取X2=(4.0,0)T.X2是(1)的可行解,但它却不是(1)的最优解,因为当X2=(4.0,0)T 时,Z2=80,但当X3=(4,1)T 时,Z3=90 Z2 即伴随规划的最优解通过“舍零取整”得到的X1,X2 都不是(1)的最优解.因此通过伴随规划最优解的“舍零取 整”的办法,一般得不到原整数规划问题的最优解.若伴随规划(2)的可行域 K 是有界的,则原整数规划(1)的可行域 K 0应是K中有限个格点(整数点）的集合.见图1,图中“*为整数点(格点).图1 中四边形 OABC 是伴随规划(2)的可行

11、域.它的最优解为 C 点(4.8,0),而(1)的可行域为k0=(0,0),(0,1),(0,2),(1,0),(1,l),(1,2),(2,0),(2,1),(3,0),(3,1),(4,0),(4,l).将C点“舍零取整”后得到的X1=(5.0,0)T不在 K0中,而X2=(4,0)T在K0中,但不是(1)的最优解,最优解在B点.当然,我们也会想到能否用“穷举法”来求解整数规划.如(1)问题,将 K0 中所有整数点的目标函数值都计算出来,然后逐一比较找出最优解.这种方法对变量所能取的整数值个数较少时,勉强可以应用.如本例 可取 0,1,2,3,4共5个数值.而 只能取0,1,2共三个数值,

12、因此其组合最多为15个(其中有不可行的点).但对大型问题,这种组合数的个数可能大得惊人!如在指派问题中,有n 项任务指派n个人去完成,不同的指派方案共有n!种.当 n=20 时,这个数超过21018.如果用穷举法每一个方案都计算一遍,就是用每秒百万次的计算机,也要几万年.显然“穷举法”并不是一种普遍有效的方法.因此研究求解整数规划的一般方法是有实际意义的.自20世纪60年代以来,已发展了一些常用的解整数规划的算法,如各种类型的割平 面法、分枝定界法、解 0-1 规划的隐枚举法、分解方法、群论方法、动态规划方法等等。近十年来有人发展了一些近似算法及用计算机模拟法,也取得了较好的效果.分枝定界法在

13、20世纪60年代初 Land Doig 和 Dakin 等人提出了分枝定界法.由于该方法灵活且便于用计算机求解,所以目前已成为解整数规划的重要方法之一.分枝定界法既可用来解纯整数规划,也可用来解混合整数规划.分枝定界法的主要思路是首先求解整数规划的伴随规划,如果求得的最优解不符合整数条件,则增加新约束缩小可行域;将原整数规划问题分枝分为两个子规划,再解子规划的伴随规划通过求解一系列子规划的伴随规划及不断地定界.最后得到原整数规划问题的整数最优解.下面结合一个极大化例题来介绍分枝定界法的主要思路.例2 某公司计划建筑两种类型的宿舍.甲种每幢占地0.25 103m2,乙种每幢地0.4103m2.该

14、公司拥有土地3103m2.计划甲种宿舍不超过 8 幢,乙种宿舍不超过4幢.甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元.问该公司应计划甲、乙两种类型宿舍各建多少幢时,能使公司获利最大?解 设计划甲种宿舍建 幢,乙种宿舍建 幢,则本题数学模型为:这是一个纯整数规划问题,称为问题 。将(1)中约束条件的系数全化为整数,改为：（1）然后去掉整数条件,得到问题 的伴随规划(2),称之为问题（2）用单纯形法求解问题 ,得到最优解及最优值：1.计算原问题 目标函数值的初始上界 因为问题 的最优解不满足整数条件,因此 不是问题 的最优解,又因为 的可行域 问题 的可行域 ,故问题 的最优值不会超过

15、问题 的最优值.即有因此可令 作为 的初始上界即一般说来,若问题 无可行解,则问题 也无可行解,停止计算。若问题 的最优解 满足问题 的整数条件,则 也是问题 的最优解,停止计算.2.计算原问题 目标函数值的初始下界若能从问题 的约束条件中观察到一个整数可行解,则可将其目标函数值作为问题 目标函数值的初始下界,否则可令初始下界Z=-.给定下界的目的,是希望在求解过程中寻找比当前 更好的原问题的目标函数值.对于本例,很容易得到一个明显的可行解X=(0,0)T,Z=0.问题 的最优目标函数值决不会比它小,故可令 =0.3.增加约束条件将原问题分枝当问题 的最优解 不满足整数条件时,在 中任选一个不

16、符合整数条件的变量.如本例选 显然问题 的整数最优解只能是 或 ,而绝不会在5与6之间.因此当将可行域 切去 部分时,并没有切去 的整数可行解.可以用分别增加约束条件 及 来达到在 切去 部分的目的.切去 后就分为 及 两部分,即问题 分为问题 及问题 两枝子规划.问题 问题 作出问题 的伴随规划 则问题 的可行域为 见图2(b).以下我们将由同一问题分解出的两个分枝问题称为一对分枝.4.分别求解一对分枝在一般情况下,对某个分枝问题(伴随规划)求解时,可能出现以下几种可能:(a)(a)(b)图2(1)无可行解若无可行解,说明该枝情况己查明,不需要由此分枝再继续分枝,称该分枝为 树叶.(2)得到

17、整数最优解若求得整数最优解，则该枝情况己查明,不需要再对此继续分枝，该分枝也是 树叶.(3)得到非整数最优解若求得某个分枝问题得到的是不满足整数条件的最优解，还要区分两种情况：该最优解的目标函数值Z小于当前的下界 ，则该分枝内不可能含有原问题的整数最优解，称为“枯枝”，需剪掉。该最优解的目标函数值Z大于当前的下界 ，则仍需对该枝继续分枝，以查明该分枝内是否有目标函数值比当前的 更好的整数最优解。本例中问题 及问题 的模型及求解结果如下：问题问题解为:解为:问题 的解 是整数最优解,它当然也是问题 的整数可行解,故 的整数最优解即此时可将 修改为:同时问题 也被查清,成为“树叶”。因为 ,不满足

18、整数条件,故问题 分别增加约束条件：及 。分为 与 两枝,建立相应的伴随规划问题 与问题问题它们的可行域分别为 见图3。图3因为 ，问题无可行解，此问题已是树叶,已被查清.求解问题 ,得到最优解 5.修改上、下界 与(l)修改下界 修改下界的时机是:每求出一个整数可行解时,都要作修改下界 的工作.修改下界 的原则:在至今所有计算出的整数可行解中,选目标函数值最大的那个作为最新下界 。因此在用分枝定界法的求解全过程中,下界 是不断增大的.(2)修改上界 上界 的修改时机是:每求解完一对分枝,都要考虑修改上界修改上界 的原则是:挑选在迄今为止所有未被分枝的问题的目标函数值中最大的一个作为新的上界.

19、新的上界 应该小于原来的上界.在分枝定界法的整个求解过程中,上界的值在不断减小.问题问题解为:因为此时 的解为整数解,因此修改下界为 =130,而此时所有未被分枝的问题()的目标函数值中最大的为 ,故修改上界 =130.6.结束准则当所有分枝均已查明(或无可行解“树叶”,或为整数可行解“树叶”,或其目标函数值不大于下界 ”枯枝”）且此时 ，则已得到了原问题的整数最优 解，即目标函数值为下界 的那个整数解.在本例中,当解完一对分枝 后,得到 又 是树叶,为枯枝,因此所有分枝()均已查明.故已得到问题 的最优解:或故该公司应建甲种宿舍7幢乙种宿舍3幢;或甲种5幢、乙种4幢时,获利最大.获利为130

20、万元.可将本例的求解过程与结果用图5 来描述.问题问题问题问题问题问题问题不可行下面将分枝定界法求解混合型整数规划的计算步骤归纳如下:第1步:将原整数线性规划问题称为问题 .去掉问题的整数条件,得到伴随规划问题 第2步:求解问题 ,有以下几种可能:(l)没有可行解,则 也没有可行解,停止计算.(2)得到 的最优解,且满足问题 的整数条件,则 的最优解也是 的最优解,停止计算.(3)得到不满足问题 的整数条件的 的最优解,记它的目标函数值为 ,这时需要对问题 (从而对问题 )进行分枝,转下一步.(3)得到不满足问题 的整数条件的 的最优解,记它的目标函数值为 ,这时需要对问题 (从而对问题 )进

21、行分枝,转下一步.第3步:确定初始上下界 与 .以 作为上界 .观察出问题 的一个整数可行解,将其目标函数值记为下界 .若观察不到,则可记 =-.转下一步.第4步:将问题 分枝.在 的最优解 中,任选一个不符合整数条件的变量 ,其值为 ,以 表示小于 的最大整数.构造两个约束条件:将这两个约束条件分别加到问题 的约束条件集中,得到 的两个分枝:问题 与 对每个分枝问题求解,得到以下几种可能:(1)分枝无可行解该分枝是 树叶.(2)求得该分枝的最优解,且满足 的整数条件.将该最优解的目标函数值作为新的下界 ,该分枝也是树叶.(3)求得该分枝的最优解,且不满足 的整数条件,但其目标函数值不大于当前

22、下界 ,则该分枝是“枯枝”需要剪枝.(4)求得不满足 整数条件的该分枝的最优解,且其目标函数值大于当前下界 ,则该分枝需要继续进行分枝.若得到的是前三种情形之一,表明该分枝情况已探明,不需要继续分枝.若求解一对分枝的结果表明这一对分枝都需要继续分枝,则可先对目标函数值大的那个分校进行分枝计算,且沿着该分枝一直继续进行下去,直到全部探明情况为止.再返过来求 解目标函数值较小的那个分枝.第6步:修改上、下界.(1)修改下界 ：每求出一次符合整数条件的可行解时,都要考虑修改下界 ,选择迄今为止最好的整数可行解 相应的目标函数值作下界(2)修改上界 ：每求解完一对分枝,都要考虑修改上界 上界的值应是迄

23、今为止所有未被分枝的问题的目标函数值中最大的一个.在每解完一对分枝、修改完上、下界 和 后,若已有 此时所有分枝均已查明,即得到了问题 的最优值求解结束.若仍有 ,则说明仍有分枝没查明,需要继续分枝,回到第4步.割平面法割平面法n基本原理：基本原理：基本原理：基本原理：根据单纯形法求得其松弛问题的最优解，根据单纯形法求得其松弛问题的最优解，根据单纯形法求得其松弛问题的最优解，根据单纯形法求得其松弛问题的最优解，若不满足整数条件，则由最优解中选取具有最若不满足整数条件，则由最优解中选取具有最若不满足整数条件，则由最优解中选取具有最若不满足整数条件，则由最优解中选取具有最大真分数部分的非整分量所在

24、行构造割平面约大真分数部分的非整分量所在行构造割平面约大真分数部分的非整分量所在行构造割平面约大真分数部分的非整分量所在行构造割平面约束，将其加入原松弛问题中形成一个新的线性束，将其加入原松弛问题中形成一个新的线性束，将其加入原松弛问题中形成一个新的线性束，将其加入原松弛问题中形成一个新的线性规划求解，逐渐缩小解的范围，又不去掉整数规划求解，逐渐缩小解的范围，又不去掉整数规划求解，逐渐缩小解的范围，又不去掉整数规划求解，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解结束。解，直至找到最优解为整数解结束。解，直至找到最优解为整数解结束。解，直至找到最优解为整数解结束。割平面法割平面法n

25、约束条件构造的条件约束条件构造的条件约束条件构造的条件约束条件构造的条件1)1)已获得的不符合整数要求的线性规划最已获得的不符合整数要求的线性规划最已获得的不符合整数要求的线性规划最已获得的不符合整数要求的线性规划最优解不满足该线性约束条件优解不满足该线性约束条件优解不满足该线性约束条件优解不满足该线性约束条件,从而不可能在以后从而不可能在以后从而不可能在以后从而不可能在以后的解中出现的解中出现的解中出现的解中出现;2)2)凡是整数可行解均满足该线性约束条件凡是整数可行解均满足该线性约束条件凡是整数可行解均满足该线性约束条件凡是整数可行解均满足该线性约束条件,因而整数最优解始终保留在每次形成的

26、线性规因而整数最优解始终保留在每次形成的线性规因而整数最优解始终保留在每次形成的线性规因而整数最优解始终保留在每次形成的线性规划中划中划中划中.割平面法割平面法n割平面束构造：割平面束构造：割平面束构造：割平面束构造：设最终单纯形表的第设最终单纯形表的第设最终单纯形表的第设最终单纯形表的第i i个约束条件为：个约束条件为：个约束条件为：个约束条件为：将该约束方程所在系数和常数分解为整数将该约束方程所在系数和常数分解为整数将该约束方程所在系数和常数分解为整数将该约束方程所在系数和常数分解为整数NN和正和正和正和正真分数真分数真分数真分数f f之和，即：之和，即：之和，即：之和，即：则该约束方程等

27、价于：则该约束方程等价于：则该约束方程等价于：则该约束方程等价于：例：求解例：求解Max Z=x1+x2s.t.-x1+x2 1 3x1+x2 4 x1,x2 0，x1，x2 为整数为整数对应的对应的LP的可行域如下图的可行域如下图0 1 22 1 A Ax x1 13x3x1 1+x+x2 2 4 4 -x -x1 1+x+x2 2 1 1 C Cx x2 2D DLP的标准型为：的标准型为：Max Z=x1+x2s.t.-x1+x2+x3=1 3x1+x2+x4=4 x1,x2,x3,x4 0最终计算表中得到非整数的最优解最终计算表中得到非整数的最优解表表5-2割平面法割平面法nexex：

28、Cj1100CBXBbx1x2x3x40 x3621100 x4204501j1100 35x1入 x3出1x1311/21/200 x4803-21j01/2-1/20 68/3x2入 x4出1x28/301-2/31/31x15/3105/6-1/6j00-1/6-1/6由右边结果构造割平面束由右边结果构造割平面束由右边结果构造割平面束由右边结果构造割平面束n例（接上）：例（接上）：例（接上）：例（接上）：由上面结果构造割平面束由上面结果构造割平面束由上面结果构造割平面束由上面结果构造割平面束cj11000CBXBbx1x2x3x4x51X15/3105/6-1/601X28/301-2/

29、31/300 x5-2/3-2/300-5/6-5/61j00-1/6-1/60-1/51/5-1X11100-111X216/50101-4/50 x34/50011-6/5j0000-1/5cj110000CBXBbx1x2x3x4x5x61X11100-1101X2 16/50101-4/500 x34/50011-6/500 x6-4/50000-4/51j0000-1/501X10100-105/41X2401010-10X3200110-3/20 x5100001-5/4j00000-1/4 0-1型整数规划型整数规划等价于等价于等价于等价于取整数取整数取整数取整数一一一一 引例引

30、例 例：某公司拟在东、西、南三区建立门市部，有例：某公司拟在东、西、南三区建立门市部，有例：某公司拟在东、西、南三区建立门市部，有例：某公司拟在东、西、南三区建立门市部，有7 7个位置个位置个位置个位置A Ai i(i=1,2,(i=1,2,7),7)可供选择。可供选择。可供选择。可供选择。在东区，由在东区，由在东区，由在东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；在西区由在西区由在西区由在西区由A A4 4、A A5 5 两个点中至少选一个；两个点中至少选一个；两个点中至少选一个；两个点中至少选一个；在南区

31、由在南区由在南区由在南区由A A6 6、A A 7 7两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。如选用点，设备投资估计为如选用点，设备投资估计为如选用点，设备投资估计为如选用点，设备投资估计为b bi i元，每年可获利润估计为元，每年可获利润估计为元，每年可获利润估计为元，每年可获利润估计为c ci i元，但投元，但投元，但投元，但投资总额不能超过资总额不能超过资总额不能超过资总额不能超过B B元。问应选择哪几个点可使年利润为最大？元。问应选择哪几个点可使年利润为最大？元。问应选择哪几个点可使年利润为最大？元。问应选择哪几个点可使年利润为最大？解：解：引入

32、引入引入引入0-10-1变量变量变量变量当当当当A Ai i点被采用点被采用点被采用点被采用当当当当A Ai i点没被采用点没被采用点没被采用点没被采用东区，由东区，由东区，由东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；东区，由东区，由东区，由东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；东区，由东区，由东区，由东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点

33、中至多选两个；在西区由在西区由在西区由在西区由A A4 4、A A5 5 两个点中至少选一个；两个点中至少选一个；两个点中至少选一个；两个点中至少选一个；东区，由东区，由东区，由东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；在西区由在西区由在西区由在西区由A A4 4、A A5 5 两个点中至少选一个；两个点中至少选一个；两个点中至少选一个；两个点中至少选一个；东区，由东区，由东区，由东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点中至多选两个

34、；在西区由在西区由在西区由在西区由A A4 4、A A5 5 两个点中至少选两个；两个点中至少选两个；两个点中至少选两个；两个点中至少选两个；在南区由在南区由在南区由在南区由A A6 6、A A 7 7两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。东区，由东区，由东区，由东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；在西区由在西区由在西区由在西区由A A4 4、A A5 5 两个点中至少选两个；两个点中至少选两个；两个点中至少选两个；两个点中至少选两个；在南区由在南区由在南区由

35、在南区由A A6 6、A A 7 7两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。东区，由东区，由东区，由东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；在西区由在西区由在西区由在西区由A A4 4、A A5 5 两个点中至少选两个；两个点中至少选两个；两个点中至少选两个；两个点中至少选两个；在南区由在南区由在南区由在南区由A A6 6、A A 7 7两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。如选用点，设备投资估计为如选用点，设备投资估计为如

36、选用点，设备投资估计为如选用点，设备投资估计为b bi i元，每年可获利润估计为元，每年可获利润估计为元，每年可获利润估计为元，每年可获利润估计为c ci i元，但投元，但投元，但投元，但投资总额不能超过资总额不能超过资总额不能超过资总额不能超过B B元。元。元。元。东区，由东区，由东区，由东区，由A A1 1、A A2 2、A A3 3 三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；三个点中至多选两个；在西区由在西区由在西区由在西区由A A4 4、A A5 5 两个点中至少选两个；两个点中至少选两个；两个点中至少选两个；两个点中至少选两个；在南区由在南区由在南区由在南区由A A

37、6 6、A A 7 7两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。两个点中至少选一个。如选用点，设备投资估计为如选用点，设备投资估计为如选用点，设备投资估计为如选用点，设备投资估计为b bi i元，每年可获利润估计为元，每年可获利润估计为元，每年可获利润估计为元，每年可获利润估计为c ci i元，但投元，但投元，但投元，但投资总额不能超过资总额不能超过资总额不能超过资总额不能超过B B元。元。元。元。解：解：引入引入引入引入0-10-1变量变量变量变量当当当当A Ai i点被采用点被采用点被采用点被采用当当当当A Ai i点没被采用点没被采用点没被采用点没被采用数学模型为：数学

38、模型为：数学模型为：数学模型为：例：例：例：例：体积限制为：体积限制为：体积限制为：体积限制为：5x5x1 1+4x+4x2 2 24 24 设其为设其为设其为设其为车运车运车运车运时的体积限制时的体积限制时的体积限制时的体积限制 7x7x1 1+3x+3x2 2 45 45 设其为设其为设其为设其为船运船运船运船运时的体积限制时的体积限制时的体积限制时的体积限制 用船运用船运用船运用船运用车运用车运用车运用车运5x5x1 1+4x+4x2 2 24+yM 24+yM 7x7x1 1+3x+3x2 2 45+(1-yM)45+(1-yM)若有若有若有若有mm个互相排斥的约束：个互相排斥的约束：

39、个互相排斥的约束：个互相排斥的约束：为保证为保证为保证为保证mm个约束条件只有一个起作用，引入个约束条件只有一个起作用，引入个约束条件只有一个起作用，引入个约束条件只有一个起作用，引入mm个个个个0-0-1 1变量变量变量变量 ，和充分大的数，和充分大的数，和充分大的数，和充分大的数MM。作如下约。作如下约。作如下约。作如下约束即可。束即可。束即可。束即可。约束条件只有一个起作用约束条件只有一个起作用约束条件只有一个起作用约束条件只有一个起作用二二二二 0-10-1规划的解法规划的解法规划的解法规划的解法例：例：例：例：是可行解。是可行解。是可行解。是可行解。故：故：故：故：是过滤条件是过滤条

40、件是过滤条件是过滤条件Z Z值值值值5 53 38 8变量变量变量变量按照目标函数的系数递增的顺序排列：按照目标函数的系数递增的顺序排列：按照目标函数的系数递增的顺序排列：按照目标函数的系数递增的顺序排列：也按下列顺序取值也按下列顺序取值也按下列顺序取值也按下列顺序取值（0 0，0 0，0 0），），），），（0 0，0 0，1 1），），），），（0 0，1 1，1 1），），），），这样最优解易较，这样最优解易较，这样最优解易较，这样最优解易较早得到，同时，结合过滤条件的改进，使计算简化。早得到，同时，结合过滤条件的改进，使计算简化。早得到，同时，结合过滤条件的改进，使计算简化。早得到，同

41、时，结合过滤条件的改进，使计算简化。上例写为：上例写为：上例写为：上例写为：过滤条件改进为：过滤条件改进为：过滤条件改进为：过滤条件改进为：过滤条件改进为：过滤条件改进为：过滤条件改进为：过滤条件改进为：5 指派问题指派问题指派问题：指派问题：有有有有n n项工作，恰好有项工作，恰好有项工作，恰好有项工作，恰好有n n个人去承担，每个人去承担，每个人去承担，每个人去承担，每个人的专长不同，做每项工作的效率不同，应派哪个个人的专长不同，做每项工作的效率不同，应派哪个个人的专长不同，做每项工作的效率不同，应派哪个个人的专长不同，做每项工作的效率不同，应派哪个人去完成哪项工作，使总效率最高。人去完成

42、哪项工作，使总效率最高。人去完成哪项工作，使总效率最高。人去完成哪项工作，使总效率最高。例：有一份中文说明书，需译成英、日、例：有一份中文说明书，需译成英、日、德、俄四种文字。表格如下：德、俄四种文字。表格如下：丁丁丁丁人员人员人员人员甲甲甲甲乙乙乙乙丙丙丙丙任务任务任务任务E EGGJ JR R2 210109 97 715154 414148 813131414161611114 4151513139 9人工作 1 2n 1 2 n 应派哪个人去完成哪项工作，使总效率最高。应派哪个人去完成哪项工作，使总效率最高。应派哪个人去完成哪项工作，使总效率最高。应派哪个人去完成哪项工作，使总效率最高

43、。当指派第当指派第当指派第当指派第 个人完成第个人完成第个人完成第个人完成第 项任务项任务项任务项任务 当不指派第当不指派第当不指派第当不指派第 个人完成第个人完成第个人完成第个人完成第 项任务项任务项任务项任务 数学模型：数学模型：设设设设 是第是第是第是第 个人完成第个人完成第个人完成第个人完成第 项任务的效率，项任务的效率，项任务的效率，项任务的效率，=1=1，2 2，n.n.引入变量引入变量引入变量引入变量 ，其取值为，其取值为，其取值为，其取值为1 1或或或或0 0。当指派第当指派第当指派第当指派第 个人完成第个人完成第个人完成第个人完成第 项任务项任务项任务项任务 当不指派第当不指

44、派第当不指派第当不指派第 个人完成第个人完成第个人完成第个人完成第 项任务项任务项任务项任务 数学模型：数学模型：设设设设 是第是第是第是第 个人完成第个人完成第个人完成第个人完成第 项任务的效率，项任务的效率，项任务的效率，项任务的效率，=1=1，2 2，n.n.引入变量引入变量引入变量引入变量 ，其取值为，其取值为，其取值为，其取值为1 1或或或或0 0。当指派第当指派第当指派第当指派第 个人完成第个人完成第个人完成第个人完成第 项任务项任务项任务项任务 当不指派第当不指派第当不指派第当不指派第 个人完成第个人完成第个人完成第个人完成第 项任务项任务项任务项任务 第第第第 项任务只能有一个

45、人来完成项任务只能有一个人来完成项任务只能有一个人来完成项任务只能有一个人来完成 数学模型：数学模型：设设设设 是第是第是第是第 个人完成第个人完成第个人完成第个人完成第 项任务的效率，项任务的效率，项任务的效率，项任务的效率，=1=1，2 2，n.n.引入变量引入变量引入变量引入变量 ，其取值为，其取值为，其取值为，其取值为1 1或或或或0 0。当指派第当指派第当指派第当指派第 个人完成第个人完成第个人完成第个人完成第 项任务项任务项任务项任务 当不指派第当不指派第当不指派第当不指派第 个人完成第个人完成第个人完成第个人完成第 项任务项任务项任务项任务 第第第第 项任务只能有一个人来完成项任

46、务只能有一个人来完成项任务只能有一个人来完成项任务只能有一个人来完成 第第第第 个人只能完成一项任务个人只能完成一项任务个人只能完成一项任务个人只能完成一项任务 满足约束条件的可行解满足约束条件的可行解满足约束条件的可行解满足约束条件的可行解 写成矩阵形式，称为解矩阵。写成矩阵形式，称为解矩阵。写成矩阵形式，称为解矩阵。写成矩阵形式，称为解矩阵。如：如：如：如：解矩阵中的解矩阵中的解矩阵中的解矩阵中的1 1一定在不同的行和不同的列。一定在不同的行和不同的列。一定在不同的行和不同的列。一定在不同的行和不同的列。指派问题的一些结果：指派问题的一些结果：指派问题的一些结果：指派问题的一些结果：(1)

47、(1)指派问题是指派问题是指派问题是指派问题是0-10-1规划的特例也是运输问题的特例，当然规划的特例也是运输问题的特例，当然规划的特例也是运输问题的特例，当然规划的特例也是运输问题的特例，当然也是线性规划问题。也是线性规划问题。也是线性规划问题。也是线性规划问题。（2 2）若从系数矩阵（）若从系数矩阵（）若从系数矩阵（）若从系数矩阵（）的一行（列）各元素中分别）的一行（列）各元素中分别）的一行（列）各元素中分别）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（减去该行（列）的最小元素，得到新矩阵（减去该行（列）的最小元素，得到新矩阵（减去该行（列）的最小元素，得到新矩阵（），则

48、），则），则），则新系数阵对应的最优解与原系数阵对应的最优解相同。新系数阵对应的最优解与原系数阵对应的最优解相同。新系数阵对应的最优解与原系数阵对应的最优解相同。新系数阵对应的最优解与原系数阵对应的最优解相同。证明：若从证明：若从证明：若从证明：若从 中每行减去一个常数中每行减去一个常数中每行减去一个常数中每行减去一个常数 ，每列减去，每列减去，每列减去，每列减去一个常数一个常数一个常数一个常数 ，得到的新系数阵为，得到的新系数阵为，得到的新系数阵为，得到的新系数阵为 。独立独立独立独立0 0元素：不同行不同列的元素：不同行不同列的元素：不同行不同列的元素：不同行不同列的0 0元素。元素。元素

49、。元素。定理（康尼格）：效率矩阵中独立定理（康尼格）：效率矩阵中独立定理（康尼格）：效率矩阵中独立定理（康尼格）：效率矩阵中独立0 0元素的最多个数等于元素的最多个数等于元素的最多个数等于元素的最多个数等于能覆盖所有能覆盖所有能覆盖所有能覆盖所有0 0元素的最少直线数。元素的最少直线数。元素的最少直线数。元素的最少直线数。W.W.KuhnW.W.Kuhn 在在在在19551955年提出匈牙利法。年提出匈牙利法。年提出匈牙利法。年提出匈牙利法。匈牙利法步骤匈牙利法步骤化指派问题为极小化问题，对各行或各列减去改行或该列的最小化指派问题为极小化问题，对各行或各列减去改行或该列的最小化指派问题为极小化

50、问题，对各行或各列减去改行或该列的最小化指派问题为极小化问题，对各行或各列减去改行或该列的最小元素，使价值系数矩阵中的行或列元素都有零元素出现为止。元素，使价值系数矩阵中的行或列元素都有零元素出现为止。元素，使价值系数矩阵中的行或列元素都有零元素出现为止。元素，使价值系数矩阵中的行或列元素都有零元素出现为止。为变换后的价值系数矩阵确定独立零元素，即用最少的横线或竖为变换后的价值系数矩阵确定独立零元素，即用最少的横线或竖为变换后的价值系数矩阵确定独立零元素，即用最少的横线或竖为变换后的价值系数矩阵确定独立零元素，即用最少的横线或竖线划去线划去线划去线划去0 0元素，通常从元素，通常从元素，通常从