整数规划(整数规划)ppt课件.ppt

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

1、想一想：在生产管理和经营活动中若要求解：在生产管理和经营活动中若要求解： 安排上班的人数 运输车辆台数第八章第八章 整数规划（整数规划（IP）(Integer Programming) 1 1 整数规划的模型（掌握）整数规划的模型（掌握） 3 3 整数规划的应用（掌握）整数规划的应用（掌握） （补充指派问题的匈牙利解法）（补充指派问题的匈牙利解法） 2 2 整数规划的计算机求解（掌握）整数规划的计算机求解（掌握）主要内容：主要内容：一、整数规划的模型一、整数规划的模型（一）整数规划实例（一）整数规划实例例例1：某公司拟用集装箱托运甲、乙两种货物，：某公司拟用集装箱托运甲、乙两种货物，这两种货物

2、每件的体积、重量，可获利润以及这两种货物每件的体积、重量，可获利润以及托运所受限制如表所示：托运所受限制如表所示：甲种货物至多托运甲种货物至多托运4件。件。问：两种货物各托运多少件，可使获得利润最大？问：两种货物各托运多少件，可使获得利润最大？ 货物货物 每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲乙乙1951952732734 440402 23 3托运限制托运限制 1365 1365140140规划模型：规划模型：为整数运件数分别为甲乙两种货物托设2121121212121,0,41404041365273195. .32

3、max,xxxxxxxxxtsxxzxx 货物货物每件体积每件体积 每件重量每件重量每件利润每件利润甲甲乙乙1951952732734 440402 23 3托运限制托运限制 1365 1365140140（二）整数规划的一般数学模型（二）整数规划的一般数学模型一般形式一般形式且且部部分分或或全全部部为为整整数数或或 n)1.2(j 0)2 . 1( )min(max11jnjijijnjjjxmibxaxcZZ 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、数规划、全整数规划、混合整数规划、0 01 1整数规划。

4、整数规划。 纯整数规划：纯整数规划：所有决策变量要求取非负整所有决策变量要求取非负整数。数。 全整数规划：全整数规划：除了所有决策变量要求取非负除了所有决策变量要求取非负整数外，技术系数整数外，技术系数aij和常数和常数bi也要求取整数。也要求取整数。 混合整数规划：混合整数规划：只有一部分的决策变量要只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。求取非负整数，另一部分可以取非负实数。 01整数规划：整数规划：所有决策变量只能取所有决策变量只能取 0 或或 1 两个整数两个整数。 对整数规划问题，先按线对整数规划问题，先按线性规划问题（不受整数约束）性规划问题（不受整数约束）求解

5、，然后求解，然后“舍入化整舍入化整”，就，就可得到整数最优解，可以吗？可得到整数最优解，可以吗？想一想：（三）整数规划与线性规划的关系（三）整数规划与线性规划的关系 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但满足整数要求的解即可。但实际上两者实际上两者却有很大的不同，却有很大的不同，通过舍入得到的解通过舍入得到的解（整数）也不一定就是最优解，有时甚（整数）也不一定就是最优解，有时甚至不能保证所得的解是整数可行解。至不能

6、保证所得的解是整数可行解。举例说明。举例说明。例：设整数规划问题如下例：设整数规划问题如下 且为整数0,13651914max21212121xxxxxxxxZ 首先不考虑整数约束，得到线性规划问题。首先不考虑整数约束，得到线性规划问题。0,13651914max21212121xxxxxxxxZ用用 解法求出最优解解法求出最优解x13/2, x2 = 10/3且有且有MaxZ = 29/6x1x233(3/2,10/3) 现求整数解（最优解）：现求整数解（最优解）：如用如用“舍入取整法舍入取整法”可得可得到到4个点即个点即(1，3) (2，3)(1，4)(2，4)。显然，它们。显然，它们都不

7、可能是整数规划的最都不可能是整数规划的最优解。优解。 按整数规划约束条件，其可行解肯定在线性规划问题按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。是一个有限集，如图所示。图图1. 整数规划的解是可数个的，最整数规划的解是可数个的，最 优解不一定发生在顶点。优解不一定发生在顶点。2. 整数规划的最优解不会优于其整数规划的最优解不会优于其对应线性规划问题的最优解。对应线性规划问题的最优解。（定理）（定理）重点重点 因此，可将集合内的整数点一一找出，其最大因此，可将集合内的整数点一一找

8、出，其最大目标函数的值为最优解，此法为目标函数的值为最优解，此法为完全枚举法。完全枚举法。 如上例：其中如上例：其中（2，2）（）（3，1）点为最大点为最大值，值，MaxMaxZ=4。 目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有： 分支定界法和割平面法（不作为课堂授课内分支定界法和割平面法（不作为课堂授课内容）；容）； 对于特别的对于特别的0 01 1规划问题采用规划问题采用隐枚举法隐枚举法和和匈牙利法。匈牙利法。 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任项不同的任务，需要务，需要n 个人分别完成其中的一项，但由于任务的个人分别完成

9、其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。题称为指派问题或分派问题。二、二、指派问题（匈牙利法）指派问题（匈牙利法） 指派问题是指派问题是0101规划的特例。规划的特例。 库恩（库恩（ww.kuhnww.kuhn）于）于1

10、9551955年提出了指派问题的年提出了指派问题的解法。他引用了匈牙利数学家康尼格一个关于解法。他引用了匈牙利数学家康尼格一个关于矩阵中矩阵中0 0元素的定理，所以把这解法称为匈牙元素的定理，所以把这解法称为匈牙利法。以后在方法上虽有不断改进，但仍沿用利法。以后在方法上虽有不断改进，但仍沿用这名称。这名称。四、整数规划问题计算机求解四、整数规划问题计算机求解(P165)(P165)例例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1,x2,x3 0 为整数用用管理运筹学管理运筹学软件求解得

11、：软件求解得： x x1 1 = 5 = 5 x x2 2 = 2 = 2 x x3 3 = 2 = 2 四、整数规划问题计算机求解四、整数规划问题计算机求解(P165)(P165)例例3 3： Max z = 3xMax z = 3x1 1 + x + x2 2 + 3x + 3x3 3 s.ts.t. . -x -x1 1 + 2x + 2x2 2 + x + x3 3 4 4 4x 4x2 2 -3x -3x3 3 2 2 x x1 1 -3x -3x2 2 + 2x + 2x3 3 3 3 x x3 3 1 1 x x1 1,x,x2 2,x,x3 3 0 0 x x1 1，x x3

12、3 为整数为整数 x x3 3 为为0-10-1变量变量用用管理运筹学管理运筹学软件求解得：软件求解得： x x1 1 = 4 = 4 x x2 2 = 1.25 = 1.25 x x3 3 = 1 z = 16.25= 1 z = 16.258.3 8.3 整数规划的应用整数规划的应用 投资场所的选择。例投资场所的选择。例4 4 固定成本问题。例5 指派问题（分配问题）。例指派问题（分配问题）。例6 6 分布系统设计。例7 投资问题。例8例例4、京成畜产品公司计划在市区的东、西、南、北四区建立、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有销售门市部，拟议中有10个位置

13、个位置 Aj (j1，2，3，10)可可供选择，考虑到各地区居民的消费水平及居民居住密集度，供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：规定： 在东区由在东区由A1 ， A2 ，A3 三个点至多选择两个；三个点至多选择两个； 在西区由在西区由A4 ， A5 两个点中至少选一个；两个点中至少选一个； 在南区由在南区由A6 ， A7 两个点中至少选一个；两个点中至少选一个； 在北区由在北区由A8 ， A9 ， A10 三个点中至少选两个。三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示样

14、的，预测情况见表所示 (单位：万元单位：万元)。但投资总额不能超。但投资总额不能超过过720万元，问应选择哪几个销售点，可使年利润为最大万元，问应选择哪几个销售点，可使年利润为最大?五、投资场所的选择。例五、投资场所的选择。例4(P166)4(P166)解：设：解：设：0-10-1变量变量 x xi i = 1 (A= 1 (Ai i 点被选用）点被选用）或或 0 0 ( (A Ai i 点没被选用）。点没被选用）。 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z =36Max z =36x x1 1+40+40 x x2 2+50+50 x x3 3+22+22x x

15、4 4+20+20 x x5 5+30+30 x x6 6+25+25x x7 7+48+48x x8 8+58+58x x9 9+61+61x x1010s.ts.t. . 100100 x x1 1+120+120 x x2 2+150+150 x x3 3+80+80 x x4 4+70+70 x x5 5+90+90 x x6 6+80+80 x x7 7+140+140 x x8 8+160+160 x x9 9+180+180 x x1010 720 720 x x1 1 + + x x2 2 + + x x3 3 2 2 x x4 4 + + x x5 5 1 1 x x6 6

16、+ + x x7 7 1 1 x x8 8 + + x x9 9 + + x x1010 2 2 x xi i 0 0 且且x xi i 为为0-10-1变量变量，i i = 1,2,3,= 1,2,3,10,10例例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有拟议中有10个位置个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：的消费水平及居民居住密集度，规定： 在东区由在东区由A1 ， A2 ，A3 三个点至多选择两个；三个点至多选

17、择两个； 在西区由在西区由A4 ， A5 两个点中至少选一个；两个点中至少选一个； 在南区由在南区由A6 ， A7 两个点中至少选一个；两个点中至少选一个； 在北区由在北区由A8 ， A9 ， A10 三个点中至少选两个。三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示情况见表所示 (单位：万元单位：万元)。但投资总额不能超过。但投资总额不能超过720万元，问应选择哪万元，问应选择哪几个销售点，可使年利润为最大几个销售点，可使年利润为最大?在西区由在西区由A A4 4 ， A A5 5

18、两个点或者都选，或者都不选。两个点或者都选，或者都不选。五、投资场所的选择。例五、投资场所的选择。例4(P166)4(P166) 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任项不同的任务，需要务，需要n 个人分别完成其中的一项，但由于任务的个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的

19、总效率最高（或所需时间最少），这类问项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。题称为指派问题或分派问题。 （一）、指派问题的数学模型（一）、指派问题的数学模型 设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第件工作，每件工作只有一个人去做。已知第i 个人去做个人去做第第j 件工作的的效率（件工作的的效率（ 时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij 0。问应如何分配才。问应如何分配才能使总效率（能使总效率（ 时间或费用）最高？时间或费用）最高？六、指

20、派问题六、指派问题 指派问题是指派问题是0101规划的特例。规划的特例。 库恩（库恩（ww.kuhnww.kuhn）于）于19551955年提出了指派问题的年提出了指派问题的解法。他引用了匈牙利数学家康尼格一个关于解法。他引用了匈牙利数学家康尼格一个关于矩阵中矩阵中0 0元素的定理，所以把这解法称为匈牙元素的定理，所以把这解法称为匈牙利法。以后在方法上虽有不断改进，但仍沿用利法。以后在方法上虽有不断改进，但仍沿用这名称。这名称。【例】下表为某一个分配问题的效率矩阵，其中aij表示 第i个人完成第j项工作需要的时间。要求：1.将此分配问题的求解转化为一个网络图中求始点 与终点之间的最短路问题，画

21、出该网络图，注明 节点和边的含义，并标明每一条边的aij值； 2.以上述网络图为基础，利用01变量建立该最短 路问题的01整数规划模型，列出该模型的数学 表达式。 工作人B1B2B3A1A2A3a11a21a31a12a22a32a13a23a33例例6 6有四个工人，要分别指派他们完成四项不同有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为示，问应如何指派工作，才能使总的消耗时间为最少。最少。解：引入解：引入0 01 1变量变量 x xijij，并令并令 x xijij = 1

22、(= 1(当指派第当指派第 i i人去完成第人去完成第j j项工作时项工作时) )或或0 0（当不指派第（当不指派第 i i人去人去完成第完成第j j项工作时项工作时) )这可以表示为一个这可以表示为一个0-10-1整数规划问题：整数规划问题：MinzMinz=15=15x x1111+18+18x x1212+21+21x x1313+24+24x x1414+19+19x x2121+23+23x x2222+22+22x x2323+18+18x x2424+26+26x x3131+17+17x x3232+16+16x x3333+19+19x x3434+19+19x x41 41

23、 +21+21x x4242+23+23x x4343+17+17x x4444s.ts.t. . x x1111+ + x x1212+ + x x1313+ + x x1414= 1 (= 1 (甲只能干一项工作甲只能干一项工作) ) x x2121+ + x x2222+ + x x2323+ + x x2424= 1 (= 1 (乙只能干一项工作乙只能干一项工作) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (= 1 (丙只能干一项工作丙只能干一项工作) ) x x4141+ + x x4242+ + x x4343+ + x x4444

24、= 1 (= 1 (丁只能干一项工作丁只能干一项工作) ) x x1111+ + x x2121+ + x x3131+ + x x4141= 1 ( A= 1 ( A工作只能一人干工作只能一人干) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( B= 1 ( B工作只能一人干工作只能一人干) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( C= 1 ( C工作只能一人干工作只能一人干) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( D= 1 ( D

25、工作只能一人干工作只能一人干) ) x xijij 为为0-10-1变量变量，i,ji,j = 1,2,3,4= 1,2,3,4 * * * * * * 求解可用求解可用管理运筹学管理运筹学软件中整数规划方法。软件中整数规划方法。 设决策变量设决策变量 1 分配第分配第i 个人去做第个人去做第j 件工作件工作 xij = 0 相反相反 ( I,j=1.2. n )其数学模型为：其数学模型为： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或 （二）匈牙利法解题步骤（二）匈牙利法解题步骤（补充，重点）（补充，重点）

26、 指派问题是指派问题是0-1 规划的特例，也是运输问题的特例，规划的特例，也是运输问题的特例，当然可用整数规划，当然可用整数规划，0-1 规划或运输问题的解法去求规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即匈牙利法，即系数矩阵中独立系数矩阵中独立 0 0 元素的最多个数等于元素的最多个数等于能覆盖所有能覆盖所有 0 0 元素的最少直线数。元素的最少直线数。 第一步：变换指派问题的系数矩阵（第一步：变换指派问题的系数矩阵（

27、cij）为）为(bij)，使，使在在(bij)的各行各列中都出现的各行各列中都出现0元素，即元素，即 (1) 从（从（cij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的每列元素中减去该列的最再从所得新系数矩阵的每列元素中减去该列的最小元素。小元素。 第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 在在(bij)中找尽可能多的独立中找尽可能多的独立0元素，若能找出元素，若能找出n个独个独立立0元素，就以这元素，就以这n个独立个独立0元素对应解矩阵元素对应解矩阵(xij)中的元中的元素为素为1，其余为，其余为0，这就得到最

28、优解。找独立，这就得到最优解。找独立0元素，常元素，常用的步骤为：用的步骤为： (1)从只有一个从只有一个0元素的行元素的行(列列)开始，给这个开始，给这个0元素加元素加圈，记作圈，记作 。然后划去。然后划去 所在列所在列(行行)的其它的其它0元素，记元素，记作作 ；这表示这列所代表的任务已指派完，不必再考；这表示这列所代表的任务已指派完，不必再考虑别人了。虑别人了。 (2)给只有一个给只有一个0元素的列元素的列(行行)中的中的0元素加圈，记作元素加圈，记作；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 (3)反复进行反复进行(1)，(2)两步，直到尽可能多的两步，直到尽可能多的

29、0元素都元素都被圈出和划掉为止。被圈出和划掉为止。 (4)若仍有没有划圈的若仍有没有划圈的0元素，且同行元素，且同行(列列)的的0元素至元素至少有两个，则从剩有少有两个，则从剩有0元素最少的行元素最少的行(列列)开始，比较这开始，比较这行各行各0元素所在列中元素所在列中0元素的数目，选择元素的数目，选择0元素少的那列元素少的那列的这个的这个0元素加圈元素加圈(表示选择性多的要表示选择性多的要“礼让礼让”选择性选择性少的少的)。然后划掉同行同列的其它。然后划掉同行同列的其它0元素。可反复进行，元素。可反复进行，直到所有直到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。 （5）若）若 元素

30、的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n，那么这指，那么这指派问题的最优解已得到。若派问题的最优解已得到。若m n, 则转入下一步。则转入下一步。 第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0元素。元素。 (1)对没有对没有的行打的行打号；号； (2)对已打对已打号的行中所有含号的行中所有含元素的列打元素的列打号；号； (3)再对打有再对打有号的列中含号的列中含 元素的行打元素的行打号；号； (4)重复重复(2)，(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止； (5)对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，号的列画纵线，

31、这就得到覆盖所有这就得到覆盖所有0元素的最少直线数元素的最少直线数 l 。l 应等于应等于m，若不相等，说明试指派过程有误，回到第二步若不相等，说明试指派过程有误，回到第二步(4)，另，另行试指派；若行试指派；若 lm n，须再变换当前的系数矩阵，须再变换当前的系数矩阵，以找到以找到n个独立的个独立的0元素，为此转第四步。元素，为此转第四步。第四步：变换矩阵第四步：变换矩阵(bij)以增加以增加0元素。元素。在没有被直线覆盖的所有元素中找出最小元素，然后在没有被直线覆盖的所有元素中找出最小元素，然后打打各行都减去这最小元素；打各行都减去这最小元素；打各列都加上这最小元各列都加上这最小元素（以保

32、证系数矩阵中不出现负元素）。新系数矩阵素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。的最优解和原问题仍相同。转回第二步。 指派问题指派问题 例：有一份中文说明书，需译成英、日、德、俄四例：有一份中文说明书，需译成英、日、德、俄四种文字。分别记作种文字。分别记作E、J、G、R。有甲、乙、丙、。有甲、乙、丙、丁四人。他们将中文说明书译成不同语种的说明书丁四人。他们将中文说明书译成不同语种的说明书所需的时间如表所示。问应指派何人去完成何工作，所需的时间如表所示。问应指派何人去完成何工作，使所需总时间最少？使所需总时间最少？ 人员人员 任务任务E JG R甲甲乙乙丙

33、丙丁丁2 109715 414813141611415139例一：例一： 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119 9118713161491514410413152 24104750111006211130249742 00102350960607130 00102350960607130 0100000100101000 甲、乙、丙、丁四个人加工甲、乙、丙、丁四个人加工A、B、C、D四种工四种工件所需时间（单位：件所需时间（单位：min）如表所示。应指派何人加工）如表所示。应指派何人加工何种工件，能使总的加工时间最少？何种工件，能使总的加工

34、时间最少？ 工件工件人员人员ABCD甲甲149415乙乙117910丙丙132105丁丁1791513例二、例二、 指派问题是指派问题是0101规划的特例。规划的特例。 库恩（库恩（ww.kuhnww.kuhn）于）于19551955年提出了指派问题的年提出了指派问题的解法。他引用了匈牙利数学家康尼格一个关于解法。他引用了匈牙利数学家康尼格一个关于矩阵中矩阵中0 0元素的定理，所以把这解法称为匈牙元素的定理，所以把这解法称为匈牙利法。以后在方法上虽有不断改进，但仍沿用利法。以后在方法上虽有不断改进，但仍沿用这名称。这名称。复习：指派问题指派问题 例例2：有一份中文说明书，需译成英、日、德、俄：

35、有一份中文说明书，需译成英、日、德、俄四种文字。分别记作四种文字。分别记作E、J、G、R。有甲、乙、丙、。有甲、乙、丙、丁四人。他们将中文说明书译成不同语种的说明书丁四人。他们将中文说明书译成不同语种的说明书所需的时间如表所示。问应指派何人去完成何工作，所需的时间如表所示。问应指派何人去完成何工作，使所需总时间最少？使所需总时间最少？ 人员人员 任务任务E JG R甲甲乙乙丙丙丁丁2 109715 414813141611415139例一：例一： 任务任务人员人员EJGR甲甲215134乙乙1041415丙丙9141613丁丁78119 9118713161491514410413152 24

36、104750111006211130249742 00102350960607130第一步：变换指派问题的第一步：变换指派问题的系数矩阵（系数矩阵（c cijij）为）为( (b bijij) )，使在使在( (b bijij) )的各行各列中都的各行各列中都出现出现0 0元素，即元素，即 00102350960607130 0100000100101000 任务任务人员人员EJGR甲甲215134乙乙1041415丙丙9141613丁丁78119指派方案是：甲翻译R，乙翻译J，丙翻译E，丁翻译G最少的时间是：minZ=4+4+9+11=28第二步：进行试指派，以寻求最优解。第二步：进行试指派

37、，以寻求最优解。 (1)从只有一个从只有一个0元素的行开始，给这个元素的行开始，给这个0元素加元素加圈，记作圈，记作 。然后划去。然后划去 所在列的其它所在列的其它0元素，记元素，记作作 ；这表示这列所代表的任务已指派完，不必再；这表示这列所代表的任务已指派完，不必再考虑别人了。考虑别人了。一般指派问题一般指派问题2、人数和任务不等的指派问题、人数和任务不等的指派问题 （1）人少任务多）人少任务多 （2）人多任务少）人多任务少 3、一个人可做几件事的指派问题、一个人可做几件事的指派问题4、某事一定不能由某人做的指派问题、某事一定不能由某人做的指派问题 5、 目标函数不是求最小，求最大？目标函数

38、不是求最小，求最大？6、经过两步之后，、经过两步之后，mn，怎么办？，怎么办？ 思考思考 分配甲、乙、丙、丁四个人去完成五项任务。每分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务数多于人数，人完成各项任务时间如表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每故规定其中有一个人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间为最少的指派方案。人完成一项，试确定总花费时间为最少的指派方案。 任务任务人员人员ABCD甲甲25293143乙乙38372520丙丙37272840丁丁44413523例三、例三、E37323223 任务任务

39、人员人员ABCD甲甲25293143乙乙38372520丙丙37272840丁丁44413523E373232232327202500000232335414432402827373220253738374331292500000001218215131010120517181218640由于任务多，人少，所以增加一个虚拟的人，由于任务多，人少，所以增加一个虚拟的人，该人完成各项任务的时间都为零。该人完成各项任务的时间都为零。第一步：增加一种泳姿，各位运动员的成绩第一步：增加一种泳姿，各位运动员的成绩均为零，得方阵：均为零，得方阵： 已知下列五名运动员各种姿势的游泳成绩（各为已知下列五名运动员

40、各种姿势的游泳成绩（各为50米），如表所示，试问如何从中选拔一个参加米），如表所示，试问如何从中选拔一个参加200米米混合泳的接力队，使预期比赛成绩为最好。单位：秒混合泳的接力队，使预期比赛成绩为最好。单位：秒 任务任务人员人员ABCD甲甲37.743.433.329.2乙乙32.924.738.926.4丙丙33.842.228.529.6丁丁37.033.130.428.5例四、例四、 戊戊35.441.833.631.101 .316 .338 .414 .3505 .284 .301 .330 .3706 .295 .282 .428 .3304 .269 .387 .349 .320

41、2 .293 .334 .437 .37第一步：增加一种泳姿，各位运动员的成绩均为零，第一步：增加一种泳姿，各位运动员的成绩均为零，得方阵：得方阵： 从甲、乙、丙、丁、戊五人中挑选四人去完成四从甲、乙、丙、丁、戊五人中挑选四人去完成四项任务。每人完成各项任务时间如表所示。规定每项项任务。每人完成各项任务时间如表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作只能由一个人去单独完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因为某任务。又假定对甲必须保证分配一项任务，丁因为某种原因决定不同意承担第种原因决定不同意承担第4项任务。在满足上述条件下，项任务。在满足上述

42、条件下，如何分配工作，使完成四项工作所花费时间为最少。如何分配工作，使完成四项工作所花费时间为最少。 任务任务人员人员ABCD甲甲1051520乙乙210515丙丙2151413丁丁15276例五、例五、 戊戊94158508154907215013141520155102201551008154907215013141520155102151005-2-5先增加一种假想工作先增加一种假想工作5，再据题中给的条件列出矩阵：，再据题中给的条件列出矩阵：-8 任务任务人员人员ABCD甲甲20192028乙乙18242720丙丙26161518丁丁17202419例六、课后题例六、课后题P182（6

43、）（2）如果把消耗时间数据看成创造效益的数据，）如果把消耗时间数据看成创造效益的数据，那么应如何指派，可使得总的效益最大？那么应如何指派，可使得总的效益最大？解决办法：解决办法：转化成最小化问题，找出最大元素，转化成最小化问题，找出最大元素，用最大元素分别减去表中各元素求解。用最大元素分别减去表中各元素求解。 任务任务人员人员ABCD甲甲20192028乙乙18242720丙丙26161518丁丁17202419例六、例六、P182（6）（4）如果再增加一个人戊，他完成）如果再增加一个人戊，他完成A，B，C，D的的时间分别为时间分别为16，17，20，21分钟，这时应指派哪四分钟，这时应指派哪

44、四个人去干这四项工作，使得消耗时间最少？个人去干这四项工作，使得消耗时间最少？要求建立模型：要求建立模型：解：引入解：引入0 01 1变量变量 x xijij，并令并令 x xijij = 1(= 1(当指派第当指派第 i i人去完成第人去完成第j j项工作时项工作时) )或或0 0（当不指派第（当不指派第 i i人去完成第人去完成第j j项工作时项工作时) )这可以表示为一个这可以表示为一个0-10-1整数规划问题：整数规划问题：MinzMinz=20=20 x x1111+19+19x x1212+20+20 x x1313+28+28x x1414+18+18x x2121+24+24x

45、 x2222+27+27x x2323+20+20 x x2424+26+26x x3131+16+16x x3232+15+15x x3333+18+18x x3434+17+17x x41 41 +20+20 x x4242+24+244343+19+19x x4444+16+16x x51 51 +17+17x x5252+20+205353+21+21x x5454s.ts.t. . x x1111+ + x x1212+ + x x1313+ + x x1414 1 ( 1 (甲最多只能干一项工作甲最多只能干一项工作) ) x x2121+ + x x2222+ + x x2323+

46、 + x x24 24 1 ( 1 (乙最多只能干一项工作乙最多只能干一项工作) ) x x3131+ + x x3232+ + x x3333+ + x x34 34 1 ( 1 (丙最多只能干一项工作丙最多只能干一项工作) ) x x4141+ + x x4242+ + x x4343+ + x x44 44 1 ( 1 (丁最多只能干一项工作丁最多只能干一项工作) ) x x5151+ + x x5252+ + x x5353+ + x x54 54 1 ( 1 (戊最多只能干一项工作戊最多只能干一项工作) ) x x1111+ + x x2121+ + x x3131+ + x x41

47、41= 1 ( A= 1 ( A工作只能一人干工作只能一人干) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( B= 1 ( B工作只能一人干工作只能一人干) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( C= 1 ( C工作只能一人干工作只能一人干) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( D= 1 ( D工作只能一人干工作只能一人干) ) x xijij 为为0-10-1变量变量，i,ji,j = 1,2,3,4= 1,2,3,4 * *

48、 * * * * 求解可用求解可用管理运筹学管理运筹学软件中整数规划方法。软件中整数规划方法。 有一份中文说明书，需译成英、日、德、俄四种有一份中文说明书，需译成英、日、德、俄四种文字，分别记作文字，分别记作A、B、C、D。现有甲、乙、丙、丁四。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？间如下表所示，问如何分派任务，可使总时间最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982例七、例七、求解过程如下：求解过程如下：第一步，变换系数矩阵：第一步，变

49、换系数矩阵：2142 289541013895421176)( ijc 0673390245100954 01733402401004545第二步，试指派：第二步，试指派： 0173340240100454 找到找到 3 3 个独立零元素个独立零元素 但但 m m = 3 3 n = 4 第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0 0元素：元素： 17334241454独立零元素的个数独立零元素的个数m等于最少直线数等于最少直线数l，即，即lm=3n=4； 第四步，变换矩阵第四步，变换矩阵( (bij) )以增加以增加0 0元素：没有被直线元素：没有被直线覆盖的所有元素中的最小

50、元素为覆盖的所有元素中的最小元素为1 1，然后打，然后打各行都减各行都减去去1 1；打；打各列都加上各列都加上1 1，得如下矩阵，并转第二步进，得如下矩阵，并转第二步进行试指派：行试指派： 第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0 0元素。元素。 (1)(1)对没有的行打对没有的行打号；号； (2)(2)对已打对已打号的行中所有含号的行中所有含 元素的列打元素的列打号；号； (3)(3)再对打有再对打有号的列中含号的列中含 元素的行打元素的行打号；号； (4) (4)重复重复(2)(2)，(3)(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止； (5)(5