整数规划 课件.ppt

《整数规划 课件.ppt》由会员分享，可在线阅读，更多相关《整数规划 课件.ppt（146页珍藏版）》请在三一办公上搜索。

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

2、,变量每个项目是否投资约束总金额不超过限制目标总收益最大,整数规划,整数规划,旅游售货员问题,背景案例模型,整数规划,背景,旅游线路安排 预定景点走且只走一次 路上时间最短配送线路货郎担问题 送货地到达一次 总路程最短,案例,有一旅行团从 出发要遍游城市 已知从 到 的旅费为，问应如何安排行程使总费用最小？,整数规划,模型,变量是否从i第个城市到第j个城市约束 每个城市只能到达一次、离开一次,整数规划,目标总费用最小,整数规划,整数规划,背包问题,背景案例模型,整数规划,背景,邮递包裹 把形状可变的包裹用尽量少的车辆运走旅行背包 容量一定的背包里装尽可能的多的物品,整数规划,实例,某人出国留学

3、打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,整数规划,整数规划,问题分析,变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品

4、放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中,整数规划,约束 包裹容量限制 必带物品限制 选带物品限制,整数规划,目标函数未带物品购买费用最小,整数规划,模型,整数规划,特征变量整数性要求来源 问题本身的要求 引入的逻辑变量的需要性质可行域是离散集合,整数规划,线性整数规划模型,一般整数规划模型0-1整数规划模型混合整数规划模型,一般整数规划模型,返回,0-1整数规划模型,返回,混合整数规划模型,返回,算 法,与线性规划的关系分支定界算法割平面算法,返回,与线性规划的关系,整数规划,放松的线性规划,可行解是放松问题的可行解,最优

5、值大于等于放松问题的最优值,线性规划模型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 为整数,整数线性规划（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。因此整数规划的最优解一般不能由线性规划

6、的最优解通过简单的取整得到。,整数线性规划（ILP）解的特点,ILP是其中LP的一个子问题，所有解也是LP的可行解，所以如果LP的最优解满足ILP的整数条件，则已得最优解。,注释,最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取,分支定界算法,算法思想算法步骤算例注释,算法思想,隐枚举法 分支 求解放松问题 舍弃 变界 分支,最优值比界坏,最优解为整数最优值比界好,最优解为非整数最优值比界好,整数规划,分枝定界法,整 数 规 划,在许多线性规划问题中,要求最优解必须取整数.例如所求的解是机器的台数、人数车辆船只数等.如果所得的解中决策变量为分

7、数或小数则不符合实际问题的要求.对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划;如果仅要求部分决策变量取整数,称为混合整数规划问题.有的问题要求决策变量仅取0或l两个值,称为0-l规划问题.整数规划简称为IP问题.这里主要讨论的是整数线性规,划问题,简称为ILP问题.,对于整数线性规划问题,为了得到整数解,初看起来,似乎只要先不管整数要求,而求线性规划的解,然后将求得的非整数最优解“舍零取整”就可以了.但实际上,这个想法却常常行不通,有时“舍零取整”后的整数解根本就不是可行解,有虽然为可行解,却不是最优解.,例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利

8、润以及托 运所受限制见表1.问每集装箱中两种货物各装多少箱,可使所获利润最大?,解 设 分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题.其数学模型为:,（1）,若暂且不考虑 取整数这一条件.则(1)就变为下列线性规划:,（2）,我们将式(2)称为(1)的伴随规划.解(2)得到最优解:,（3）,但它不满足(1)的整数要求.因此它不是(1)的最优解,若把,解(3)舍零取整,如取X1=(5.0,0)T,但它不是式,(1)的可行解.因为它不满足(1)中的约束条件,若取X2=(4.0,0)T.X2是(1)的可行解,但它却不是(1)的最优解,因为当X2=(4.0,0)T 时,Z2=80,但当X3

9、=(4,1)T 时,Z3=90 Z2 即伴随规划的最优解通过“舍零取整”得到的X1,X2 都不是(1)的最优解.因此通过伴随规划最优解的“舍零取 整”的办法,一般得不到原整数规划问题的最优解.,若伴随规划(2)的可行域 K 是有界的,则原整数规划(1)的可行域 K 0应是K中有限个格点(整数点）的集合.见图1,图中“*为整数点(格点).,图1 中四边形 OABC 是伴随规划(2)的可行域.它的最优解为 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).将

10、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共三个数值,因此其组合最多为15个(其中有不可行的点).但对大型问题,这种组合数的个数可能大得惊人!如在指派问题中,有n 项任务指派n个人去完成,不同的指派方案共有n!种.当 n=20 时,这个数超过21018.如果

11、用穷举法每一个方案都计算一遍,就是用每秒百万次的计算机,也要几万年.,显然“穷举法”并不是一种普遍有效的方法.因此研究求解整数规划的一般方法是有实际意义的.自20世纪60年代以来,已发展了一些常用的解整数规划的算法,如各种类型的割平,面法、分枝定界法、解 0-1 规划的隐枚举法、,分解方法、群论方法、动态规划方法等等。近十年来有人发展了一些近似算法及用计算机模拟法,也取得了较好的效果.,分枝定界法,在20世纪60年代初 Land Doig 和 Dakin 等人提出了分枝定界法.由于该方法灵活且便于用计算机求解,所以目前已成为解整数规划的重要方法之一.分枝定界法既可用来解纯整数规划,也可用来解混

12、合整数规划.,分枝定界法的主要思路是首先求解整数规划的伴随规划,如果求得的最优解不符合整数条件,则增加新约,束缩小可行域;将原整数规划问题分枝分为两个子规划,再解子规划的伴随规划通过求解一系列子规划的伴随规划及不断地定界.最后得到原整数规划问题的整数最优解.,下面结合一个极大化例题来介绍分枝定界法的主要思路.,例2 某公司计划建筑两种类型的宿舍.甲种每幢占地0.25 103m2,乙种每幢地0.4103m2.该公司拥有土地3103m2.计划甲种宿舍不超过 8 幢,乙种宿舍不超过4幢.甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元.问该公司应,计划甲、乙两种类型宿舍各建多少幢时,能使,公司

13、获利最大?,解 设计划甲种宿舍建 幢,乙种宿舍建 幢,则本题数学模型为:,这是一个纯整数规划问题,称为问题。将(1)中约束条件,的系数全化为整数,改为：,（1）,然后去掉整数条件,得到问题 的伴随规划(2),称之为问题,（2）,用单纯形法求解问题,得到最优解及最优值：,1.计算原问题 目标函数值的初始上界,因为问题 的最优解不满足整数条件,因此 不是问题 的最优解,又因为 的可行域 问题 的可行域,故问题 的最优值不会超过问题 的最优值.即有,因此可令 作为 的初始上界,即,一般说来,若问题 无可行解,则问题 也无可行解,停止计,算。若问题 的最优解 满足问题 的整数,条件,则 也是问题 的最

14、优解,停止计算.,2.计算原问题 目标函数值的初始下界,若能从问题 的约束条件中观察到一个整数可行解,则可将其目标函数值作为问题 目标函数值的初始下界,否则可令初始下界Z=-.给定下界的目的,是希望在求解过程中寻找比当前 更好的原问题的目标函数值.,对于本例,很容易得到一个明显的可行解X=(0,0)T,Z=0.问题 的最优目标函数值决不会比它小,故可令=0.,3.增加约束条件将原问题分枝,当问题 的最优解 不满足整数条件时,在 中任选一个不符合整数条件的变量.如本例选 显然问题 的整数最优解只能是 或,而绝不会在5与6之间.因此当将可行域 切去 部分时,并没有切去 的整数可行解.可以用分别增加

15、约束条件 及 来达到在 切去 部分的目的.切去 后就分为 及 两部分,即问题 分为问题 及问题 两枝子规划.,问题,问题,作出问题 的伴随规划 则问题 的可行域为 见图2(b).以下我们将由同一问题分解出的两个分枝问题称为一对分枝.,4.分别求解一对分枝,在一般情况下,对某个分枝问题(伴随规划)求解时,可能出现以下几种可能:,(a),(b),图2,(1)无可行解,若无可行解,说明该枝情况己查明,不需要由此分枝再继续,分枝,称该分枝为 树叶.,(2)得到整数最优解,若求得整数最优解，则该枝情况己查明,不需要再对此继续分枝，该分枝也是 树叶.,(3)得到非整数最优解,若求得某个分枝问题得到的是不满

16、足整数条件的最优解，,还要区分两种情况：,该最优解的目标函数值Z小于当前的下界，则该分枝内不可能含有原问题的整数最优解，称为“枯枝”，需剪掉。,该最优解的目标函数值Z大于当前的下界，则仍需对该枝继续分枝，以查明该分枝内是否有目标函数值比当前的 更好的整数最优解。,本例中问题 及问题 的模型及求解结果如下：,问题,问题,解为:,解为:,问题 的解 是整数最优解,它当然也是问题 的整数可行解,故 的整数最优解,即此时可将 修改为:,同时问题 也被查清,成为“树叶”。,因为,不满足整数条件,故问题 分别增加约束条件：及。分为 与 两枝,建立相应的伴随规划问题 与,问题,问题,它们的可行域分别为,见图

17、3。,图3,因为，问题无可行解，此问题已是树叶,已被查清.,求解问题,得到最优解,5.修改上、下界 与,(l)修改下界,修改下界的时机是:每求出一个整数可行解时,都要作修改,下界 的工作.,修改下界 的原则:在至今所有计算出的整数可行解中,选目标函数值最大的那个作为最新下界。,因此在用分枝定界法的求解全过程中,下界 是不断增大的.,(2)修改上界,上界 的修改时机是:每求解完一对分枝,都要考虑修改上界,修改上界 的原则是:挑选在迄今为止所有未被分枝的问题的目标函数值中最大的一个作为新的上界.新的上界 应该小于原来的上界.,在分枝定界法的整个求解过程中,上界的值在不断减小.,问题,问题,解为:,

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

19、不可行,下面将分枝定界法求解混合型整数规划的计算步骤归纳如下:,第1步:将原整数线性规划问题称为问题.去掉问题的整数条件,得到伴随规划问题,第2步:求解问题,有以下几种可能:,(l)没有可行解,则 也没有可行解,停止计算.,(2)得到 的最优解,且满足问题 的整数条件,则 的最优解也是 的最优解,停止计算.,(3)得到不满足问题 的整数条件的 的最优解,记它的目标函数值为,这时需要对问题(从而对问题)进,行分枝,转下一步.,(3)得到不满足问题 的整数条件的 的最优解,记它的目标函数值为,这时需要对问题(从而对问题)进行分枝,转下一步.,第3步:确定初始上下界 与.,以 作为上界.观察出问题

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

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

22、完上、下界 和 后,若已有 此时所有分枝均已查明,即得到了问题 的最优值,求解结束.,若仍有,则说明仍有分枝没查明,需要继续分枝,回到第4步.,割平面法,基本原理：根据单纯形法求得其松弛问题的最优解，若不满足整数条件，则由最优解中选取具有最大真分数部分的非整分量所在行构造割平面约束，将其加入原松弛问题中形成一个新的线性规划求解，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解结束。,割平面法,约束条件构造的条件1)已获得的不符合整数要求的线性规划最优解不满足该线性约束条件,从而不可能在以后的解中出现;2)凡是整数可行解均满足该线性约束条件,因而整数最优解始终保留在每次形成的线性规划中.

23、,割平面法,割平面束构造：设最终单纯形表的第i个约束条件为：,将该约束方程所在系数和常数分解为整数N和正真分数f之和，即：,则该约束方程等价于：,例：求解Max Z=x1+x2s.t.-x1+x2 1 3x1+x2 4 x1,x2 0，x1，x2 为整数对应的LP的可行域如下图,0 1 2,2 1,A,x1,3x1+x2 4,-x1+x2 1,C,x2,D,LP的标准型为：Max Z=x1+x2s.t.-x1+x2+x3=1 3x1+x2+x4=4 x1,x2,x3,x4 0最终计算表中得到非整数的最优解表5-2,割平面法,ex：,j,1,1,0,0,3,5,x1入 x3出,6,8/3,x2入

24、 x4出,由右边结果构造割平面束,例（接上）：,由上面结果构造割平面束,0-1型整数规划,等价于,取整数,一 引例,例：某公司拟在东、西、南三区建立门市部，有7个位置Ai(i=1,2,7)可供选择。在东区，由A1、A2、A3 三个点中至多选两个；在西区由A4、A5 两个点中至少选一个；在南区由A6、A 7两个点中至少选一个。如选用点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？,解：引入0-1变量,当Ai点被采用,当Ai点没被采用,东区，由A1、A2、A3 三个点中至多选两个；,东区，由A1、A2、A3 三个点中至多选两个；,东区，

25、由A1、A2、A3 三个点中至多选两个；在西区由A4、A5 两个点中至少选一个；,东区，由A1、A2、A3 三个点中至多选两个；在西区由A4、A5 两个点中至少选一个；,东区，由A1、A2、A3 三个点中至多选两个；在西区由A4、A5 两个点中至少选两个；在南区由A6、A 7两个点中至少选一个。,东区，由A1、A2、A3 三个点中至多选两个；在西区由A4、A5 两个点中至少选两个；在南区由A6、A 7两个点中至少选一个。,东区，由A1、A2、A3 三个点中至多选两个；在西区由A4、A5 两个点中至少选两个；在南区由A6、A 7两个点中至少选一个。如选用点，设备投资估计为bi元，每年可获利润估计

26、为ci元，但投资总额不能超过B元。,东区，由A1、A2、A3 三个点中至多选两个；在西区由A4、A5 两个点中至少选两个；在南区由A6、A 7两个点中至少选一个。如选用点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。,解：引入0-1变量,当Ai点被采用,当Ai点没被采用,数学模型为：,例：,体积限制为：5x1+4x224 设其为车运时的体积限制 7x1+3x245 设其为船运时的体积限制,用船运,用车运,5x1+4x224+yM 7x1+3x245+(1-yM),若有m个互相排斥的约束：,为保证m个约束条件只有一个起作用，引入m个0-1变量，和充分大的数M。作如下约

27、束即可。,约束条件只有一个起作用,二 0-1规划的解法,例：,是可行解。,故：,是过滤条件,Z值,5,3,8,变量,按照目标函数的系数递增的顺序排列：,也按下列顺序取值（0，0，0），,（0，0，1），（0，1，1），这样最优解易较早得到，同时，结合过滤条件的改进，使计算简化。上例写为：,过滤条件改进为：,过滤条件改进为：,5 指派问题,指派问题：有n项工作，恰好有n个人去承担，每个人的专长不同，做每项工作的效率不同，应派哪个人去完成哪项工作，使总效率最高。,例：有一份中文说明书，需译成英、日、德、俄四种文字。表格如下：,丁,人员,甲,乙,丙,任务,E,G,J,R,21097,154148,1

28、3141611,415139,人,工作,1 2n,1 2 n,应派哪个人去完成哪项工作，使总效率最高。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,数学模型：设 是第 个人完成第 项任务的效率，=1，2，n.引入变量，其取值为1或0。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,数学模型：设 是第 个人完成第 项任务的效率，=1，2，n.引入变量，其取值为1或0。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,第 项任务只能有一个人来完成,数学模型：设 是第 个人完成第 项任务的效率，=1，2，n.引入变量，其取值为1或0。,当指派第 个人完

29、成第 项任务,当不指派第 个人完成第 项任务,第 项任务只能有一个人来完成,第 个人只能完成一项任务,满足约束条件的可行解 写成矩阵形式，称为解矩阵。如：,解矩阵中的1一定在不同的行和不同的列。,指派问题的一些结果：(1)指派问题是0-1规划的特例也是运输问题的特例，当然也是线性规划问题。（2）若从系数矩阵（）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（），则新系数阵对应的最优解与原系数阵对应的最优解相同。证明：若从 中每行减去一个常数，每列减去一个常数，得到的新系数阵为。,独立0元素：不同行不同列的0元素。,定理（康尼格）：效率矩阵中独立0元素的最多个数等于能覆盖所有0元素

30、的最少直线数。W.W.Kuhn在1955年提出匈牙利法。,匈牙利法步骤,化指派问题为极小化问题，对各行或各列减去改行或该列的最小元素，使价值系数矩阵中的行或列元素都有零元素出现为止。为变换后的价值系数矩阵确定独立零元素，即用最少的横线或竖线划去0元素，通常从0元素最多的行或列划起，如果能全覆盖各元素，则已能找到最优解，否则转第4步。找最有解，从行或列最少的0元素开始寻找，把该行或列的一个0元素变为1，其余为0，形成单位阵的一行或一列，最后形成一个单位阵，其中为1的元素对应其行任务由列人做。价值系数矩阵变化，在未被直线覆盖的元素中找出一个最小元素Cik，对未被直线覆盖的元素减去该元素，被覆盖一次

31、的元素不变，被覆盖两次的元素加上该元素。得到新的价值矩阵，返回2步。,例：,min,4,2,9,7,min,4 2,例：,最优解为：最优值Z=28,(小时）,人员,甲乙丙丁戊,任务,A B C D E,1287154,例：,79171410,961267,7614610,969109,例：,min,76764,例：,76764,例：,76764,例：,76764,（1）对没有（0）的行打；（2）对打行中所有含 0的列打；（3）对打的列中含（0）的行打；（4）重复（2）、（3）直到打不出为止；（5）对没打的行和打的列画线，得到覆盖所有0元素的最少直线数。,+2,-2,在没有被直线覆盖的部分找出最

32、小元素，然后在打行中减去最小元素，在打列中加上最小元素。,-2,甲-B,乙-C,丙-E,丁-D,戊-A 或,甲-B,乙-D,丙-E,丁-C,戊-AMinz=32,或,例1 甲乙丙丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高？,解：类似运输问题的最小元素法第一步 造0各行各列减其最小元素 4 10 7 5-4 0 6 3 1 6 2 1 Cij=2 7 6 3-2 0 5 4 1 0 5 3 1 3 3 4 4-3 0 0 1 1 0 0 1 4 6 6 3-3 1 3 3 0 1 3 2-1 第二步 圈0寻找不同行不同列的0元素，圈之

33、。所在行和列其它0元素划掉 第三步 打无的行打，打行上0列打，打列上行打，打行上0列打,解：类似运输问题的最小元素法第一步 造0各行各列减其最小元素 4 10 7 5-4 0 6 3 1 6 2 1 Cij=2 7 6 3-2 0 5 4 1 0 5 3 1 3 3 4 4-3 0 0 1 1 0 0 1 4 6 6 3-3 1 3 3 0 1 3 2-1 第二步 圈0寻找不同行不同列的0元素，圈之。所在行和列其它0元素划掉 第三步 打无的行打，打行上0列打，打列上行打，打行上0列打,第四步 划线无行、打列划线第五步 造0直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的0元素，Go

34、 to 2 0 6 2 1-1 5 1 0 0 4 0 Cij=0 5 3 1-1 0 4 2 0 3 1 0 0 0 0 1 1 0 1 2 0 2 1 3 2 0 2 3 2 2 2 1+1 最优解：x13=1,x21=1,x32=1,x44=1 Z=15,相关问题：,非标准型的转化（1）maxZ=cijxij minZ=(-cij)xij minZ=(M-cij)xij=bijxij M是足够大的常数，新问题的最优解就是原问题的最优解（2）工作与人数不等的指派问题,（2.1）人数大于工作数的指派问题例:从甲、乙、丙、丁、戊中挑选四人去完成四项工作。每人完成各项工作的时间如下表，规定每人完

35、成一项工作，每项工作由一个人完成。又规定甲必须保证分配到一项任务，丁因为某种原因不承担第4项任务，问如何分配使总的花费时间为最少？,解：先增加一个假想工作5，依题意列表如下：,用匈牙利法解得最优分配方案为：甲-2，乙-3，丙-1，戊-4,（2.2）人数少于工作数的指派问题例:分配甲、乙、丙、丁四人去完成五项工作。每人完成各项工作的时间如下表，规定每人完成一项工作，每项工作由一个人完成。问如何分配使总的花费时间为最少？,解：先增加一个假想人戊，依题意列表如下：,如上例，一人可完成两项工作例:分配甲、乙、丙、丁四人去完成五项工作。每人完成各项工作的时间如下表，由于工作数多于人数，故规定其中一人可完

36、成两项工作，其余三人每人完成一项工作。问如何分配使总的花费时间为最少？,用匈牙利法解得最优分配方案为：甲-B，乙-D、C，丙-E，丁-A,一人可完成两项工作例:分配甲、乙、丙三人去完成五项工作。每人完成各项工作的时间如下表，由于工作数多于人数，故规定一人可完成1-2项工作，问如何分配使总的花费时间为最少？,-1,-1,-1,+1,-2,-2,-2,甲A;乙C,E;丙B,DZ=3+10+12+9+12=46,应用案例分析,人力资源分配问题应急设施选址问题,人力资源分配问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问

37、应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,返回,模型假设,每天工作8小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量,问题分析,因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。变量：每天开始休息的人数 约束条件：1.每人休息时间2天，自然满足。,3.变量非负约束：,目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于,模型,