当前位置：文档之家 › 指派问题

指派问题

  • 格式：doc
  • 大小：58.50 KB
  • 文档页数：6

指派问题模型摘要指派问题是在满足特定指派要求条件下，使指派方案总体效果最佳。

如：有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包：有若干班级需要安排在若干教室里上课等。

指派问题是属于运筹学里面的一种问题，而运筹学是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。

运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。

所以，指派问题也是一个非常重要的问题，在生活中，我们遇到指派问题时该如何解决呢？首先，我们对问题进行分析，建立数学模型，再利用lingo对数据进行分析，得出最佳的指派方案。

本次是对于一个6人指派6个工作的问题进行建立模型与分析。

问题的重现6个人计划做6项工作，其效益如下表（”-”表示某人无法完成某项工作），求一种指派方式，使得每个人完成一项工作，并使得总收益最大。

所建模型最好具有推广性。

人工作1 工作2 工作3 工作4 工作5 工作61 20 15 16 5 4 72 17 15 33 12 8 63 9 12 18 16 30 134 12 8 11 27 19 145 - 7 10 21 10 326 - - - 6 11 13问题分析从6个人中分配6份工作，且6人的工作各不相同使总收益最大，容易想到穷举法，但不是最好的办法，且随着问题规模的变大，穷举法的计算量是无法接受的。

可以用0-1变量表示1个人是否接那份工作，从而建立这个问题的0-1规划模型，借助lingo数学软件求解。

模型的建立与求解记每个工作人分别为i=1，2，3，4，5，6；工作1、工作2、工作3、工作4、工作5、工作6分别为j=1，2，3，4，5，6；工作人i的第j个工作的收益为C ij,引入0-1变量，若第i个人做第j份工作记X ij=1，否则记X ij=0，根据要求X ij应满足两个要求：1、161=∑=iijx,i=1,2 (6)2、161=∑=jijx,i=1,2 (6)∑∑=66ijijxcMax,I,j=1,2 (6)将题目所给的数据输入LINGO：max20x11+15x12+16x13+5x14+4x15+7x16+17x21+15x22+33x23+12x24+8x25+6x26+9x31+1 2x32+18x33+16x34+30x35+13x36+12x41+8x42+11x43+27x44+19x45+14x46+7x52+10x5 3+21x54+10x55+32x56+6x64+11x65+13x66s.t.x11+x12+x13+x14+x15+x16=1x21+x22+x23+x24+x25+x26=1x31+x32+x33+x34+x35+x36=1x41+x42+x43+x44+x45+x46=1x51+x52+x53+x54+x55+x56=1x61+x62+x63+x64+x65+x66=1x11+x21+x31+x41+x51+x61=1x12+x22+x32+x42+x52+x62=1x13+x23+x33+x43+x53+x63=1x14+x24+x34+x44+x54+x64=1x15+x25+x35+x45+x55+x65=1x16+x26+x36+x46+x56+x66=1endint36求解得到结果：Global optimal solution found.Objective value: 142.0000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced CostX11 1.000000 -20.00000X12 0.000000 -15.00000X13 0.000000 -16.00000X14 0.000000 -5.000000X15 0.000000 -4.000000X16 0.000000 -7.000000X21 0.000000 -17.00000X22 0.000000 -15.00000X23 1.000000 -33.00000X24 0.000000 -12.00000X25 0.000000 -8.000000X26 0.000000 -6.000000X31 0.000000 -9.000000X32 0.000000 -12.00000X34 0.000000 -16.00000 X35 1.000000 -30.00000 X36 0.000000 -13.00000 X41 0.000000 -12.00000 X42 0.000000 -8.000000 X43 0.000000 -11.00000 X44 1.000000 -27.00000 X45 0.000000 -19.00000 X46 0.000000 -14.00000 X52 0.000000 -7.000000 X53 0.000000 -10.00000 X54 0.000000 -21.00000 X55 0.000000 -10.00000 X56 1.000000 -32.00000 X64 0.000000 -6.000000 X65 0.000000 -11.00000 X66 0.000000 -13.00000 X51 0.000000 0.000000 X61 0.000000 0.000000 X62 1.000000 0.000000 X63 0.000000 0.000000Row Slack or Surplus Dual Price1 142.0000 1.0000002 0.000000 0.0000003 0.000000 0.0000004 0.000000 0.0000005 0.000000 0.0000006 0.000000 0.0000007 0.000000 0.0000008 0.000000 0.0000009 0.000000 0.00000010 0.000000 0.00000011 0.000000 0.00000012 0.000000 0.00000013 0.000000 0.000000方法2;model:sets:warehouses/wh1..wh6/;vendors/v1..v6/;links(warehouses,vendors):cost,volume;endsets@for(warehouses(I):@sum(vendors(J):volume(I,J))=1);@for(vendors(J):@sum(warehouses(I):volume(I,J))=1);data:cost=20 15 16 5 4 717 15 33 12 8 69 12 18 16 30 1312 8 11 27 19 140 7 10 21 10 320 0 0 6 11 13;enddataend求解得到结果：Global optimal solution found.Objective value: 142.0000Total solver iterations: 6Variable Value Reduced Cost COST( WH1, V1) 20.00000 0.000000 COST( WH1, V2) 15.00000 0.000000 COST( WH1, V3) 16.00000 0.000000 COST( WH1, V4) 5.000000 0.000000 COST( WH1, V5) 4.000000 0.000000 COST( WH1, V6) 7.000000 0.000000 COST( WH2, V1) 17.00000 0.000000 COST( WH2, V2) 15.00000 0.000000 COST( WH2, V3) 33.00000 0.000000 COST( WH2, V4) 12.00000 0.000000 COST( WH2, V5) 8.000000 0.000000 COST( WH2, V6) 6.000000 0.000000 COST( WH3, V1) 9.000000 0.000000 COST( WH3, V2) 12.00000 0.000000 COST( WH3, V3) 18.00000 0.000000 COST( WH3, V4) 16.00000 0.000000 COST( WH3, V5) 30.00000 0.000000 COST( WH3, V6) 13.00000 0.000000 COST( WH4, V1) 12.00000 0.000000 COST( WH4, V2) 8.000000 0.000000 COST( WH4, V3) 11.00000 0.000000 COST( WH4, V4) 27.00000 0.000000 COST( WH4, V5) 19.00000 0.000000 COST( WH4, V6) 14.00000 0.000000COST( WH5, V3) 10.00000 0.000000 COST( WH5, V4) 21.00000 0.000000 COST( WH5, V5) 10.00000 0.000000 COST( WH5, V6) 32.00000 0.000000 COST( WH6, V1) 0.000000 0.000000 COST( WH6, V2) 0.000000 0.000000 COST( WH6, V3) 0.000000 0.000000 COST( WH6, V4) 6.000000 0.000000 COST( WH6, V5) 11.00000 0.000000 COST( WH6, V6) 13.00000 0.000000 VOLUME( WH1, V1) 1.000000 0.000000 VOLUME( WH1, V2) 0.000000 5.000000 VOLUME( WH1, V3) 0.000000 4.000000 VOLUME( WH1, V4) 0.000000 21.00000 VOLUME( WH1, V5) 0.000000 27.00000 VOLUME( WH1, V6) 0.000000 26.00000 VOLUME( WH2, V1) 0.000000 16.00000 VOLUME( WH2, V2) 0.000000 18.00000 VOLUME( WH2, V3) 1.000000 0.000000 VOLUME( WH2, V4) 0.000000 27.00000 VOLUME( WH2, V5) 0.000000 36.00000 VOLUME( WH2, V6) 0.000000 40.00000 VOLUME( WH3, V1) 0.000000 10.00000 VOLUME( WH3, V2) 0.000000 7.000000 VOLUME( WH3, V3) 0.000000 1.000000 VOLUME( WH3, V4) 0.000000 9.000000 VOLUME( WH3, V5) 1.000000 0.000000 VOLUME( WH3, V6) 0.000000 19.00000 VOLUME( WH4, V1) 0.000000 9.000000 VOLUME( WH4, V2) 0.000000 13.00000 VOLUME( WH4, V3) 0.000000 10.00000 VOLUME( WH4, V4) 1.000000 0.000000 VOLUME( WH4, V5) 0.000000 13.00000 VOLUME( WH4, V6) 0.000000 20.00000 VOLUME( WH5, V1) 0.000000 19.00000 VOLUME( WH5, V2) 0.000000 12.00000 VOLUME( WH5, V3) 0.000000 9.000000 VOLUME( WH5, V4) 0.000000 4.000000 VOLUME( WH5, V5) 0.000000 20.00000 VOLUME( WH5, V6) 1.000000 0.000000 VOLUME( WH6, V1) 0.000000 0.000000 VOLUME( WH6, V2) 1.000000 0.000000 VOLUME( WH6, V3) 0.000000 0.000000 VOLUME( WH6, V4) 0.000000 0.000000Row Slack or Surplus Dual Price1 142.0000 1.0000002 0.000000 33.000003 0.000000 46.000004 0.000000 32.000005 0.000000 34.000006 0.000000 32.000007 0.000000 13.000008 0.000000 -13.000009 0.000000 -13.0000010 0.000000 -13.0000011 0.000000 -7.00000012 0.000000 -2.00000013 0.000000 0.000000结果分析通过lingo的分析，我们可以得到以下结论，用以下方式将使公司收益最大：第一个人选第一个工作，第二个人选第三个工作，第三个人选第五个工作，第四个人选第四个工作，第五个人选第六个工作，第六个人选第二个工作，最大收益为142.参考文献（1）姜启源谢金星叶俊,数学建模(第三版),北京：高等教育出版社,2004年（2）万义国，游小青《优化建模软件LINGO 在运筹学中的应用》。

合集下载

第5章 整数-指派问题

第5章 整数-指派问题


(if i ≠ k ); cij , bij = ckj + a, (if i = k ).
则以b 则以 ij为系数的新指派问题的目标函数为 n n z = ∑i =1 ∑ j =1 bij xij
= ∑i ≠ k ∑ j =1 cij xij + ∑ j =1 (ckj + a ) xkj
n n
= ∑i =1 ∑ j =1 cij xij + a ∑ j =1 xkj = z + a
n n n
利用性质1, 利用性质 ,可使原系数矩阵变换为含 有很多0元素的新系数矩阵 元素的新系数矩阵, 有很多 元素的新系数矩阵,而最优解保 持不变,在系数矩阵(b 中 持不变,在系数矩阵 ij)中,我们关心位 于不同行不同列的0元素 元素, 于不同行不同列的 元素,以下简称为独 立的0元素. 立的 元素. 元素 利用性质2,若能在系数矩阵(b 中找 利用性质 , 若能在系数矩阵 ij)中找 个独立的0元素 出n个独立的 元素;则令解矩阵 ij)中对 个独立的 元素;则令解矩阵(x 中对 应这n个独立的 元素的元素取值为1, 个独立的0元素的元素取值为 应这 个独立的 元素的元素取值为 ,其 他元素取值为0. 他元素取值为 .将其代入目标函数中得 到zb=0,它一定是最小. ,它一定是最小. 这就是以 ij)为系数矩阵的指派问题的 这就是以(b 为系数矩阵的指派问题的 最优解.也就得到了原问题的最优解. 最优解.也就得到了原问题的最优解.
解 按上述第一步,将这系数矩阵进行变换.
min 12 7 9 7 9 7 5 0 2 0 8 9 6 6 6 6 2 3 0 0 7 17 12 14 9 7 → 0 10 5 7 15 14 6 6 10 6 9 8 0 0 4 10 7 10 9 4 0 6 3 6 2 0 2 4 5
指派问题

指派问题


-2 -4 -9 -7
0 13 11 6 0 10 0 5 7 0 1 4
-4
2 11 4 2
-2
x14 1, x22 1, x31 1, x43 1
其余全为0。
步骤2：用圈0法确定 C1 中的独立0元素。若独立零元素个 素有n个，则已得最优解。若 独立零元素的个数 < n, 则转
min Z 4x11 8x12 10x54 6x55
5 xij 1 i 1,2, 5 j5 1 s.t. xij 1 j 1,2, 5 i 1 xij 0 或1
B1
B2
B3
B4
B5
C
A1 4 A2 7 A3 6 A4 6 A5 6
入步骤3。
在只有一个0元素的行（或列）加圈，表示此人只能做该事
（或此事只能由该人来做），每圈一个“0”，同时把位于同 列（或同行）的其他零元素划去。表示此时已不能再由他
人来做（或此人已不能做其它事）。如此反复，直到矩阵
中所有零元素都被圈去或划去为至。
在遇到所有行和列中，零元素都不止一个时，可任选其中
注：指派问题是一种特殊的LP问题，是一种特殊的运输问题。 下用目前认为最简洁的方法—匈牙利法求解 (The Hungarian
Method of Assignment )。
例12：某商业公司计划开办五家新商店。为了尽早建成
营业，商业公司决定由5家建筑公司分别承建。已知建筑
公司 Ai (i 1,2,,5) 对新商店 B j ( j 1,2,,5) 的建造 报价（万元）为 cij (i, j 1,2,,5) ，见下矩阵。商业公 司应当对5家建筑公司怎样分配建筑任务，才能使总的建 筑费用最少？
第4章整数规划——指派问题

第4章整数规划——指派问题


4 指派问题
解： 可行解｛c12=0， c24 =0， c31 =0， c43 =0｝是一个独立零元素组， c12=0， c24 =0， c31 =0， c43 =0分别称 为独立零元素； ｛c12=0， c23 =0， c31 =0， c44 =0｝也 是一个独立零元素组，而｛c14=0， c23 =0， c31 =0， c44 =0｝就不是独立零元素 组.
4 指派问题
1）对新矩阵中所有不含“*”元素的行打√ ； 2）对打√的行中，所有打×零元素所在的列打√； 3）对所有打√列中标记“*”元素所在行打√； 4）重复上述2），3）步，直到不能进一步打√为止； 5）对未打√的每一行划一直线，对已打√的每一列划一纵线， 即得到覆盖当前0元素的最少直线数。 第四步：对矩阵未被直线覆盖过的元素中找最小元素，将打 √行的各元素减去这个最小元素，将打√列的各元素加上这个最小 元素（以避免打√行中出现负元素），这样就增加了零元素的个 数，返回第二步。 【例5】 求解例1和例2
X (2)
都是指派问题的最优解。
4 指派问题
4.3 指派问题的求解 指派问题既是一类特殊的整数规划问题，又是特殊的运输问 题，因此可以用多种相应的解法来求解，然而这些解法都没有充 分利用指派问题的特殊性质，有效地减少计算量，直到1955年库 恩（W. W. Kuhn）提出的匈牙利法才有效地解决了指派问题。 匈牙利法的理论基础 定义2 独立零元素组 在效率矩阵中，有一组在不同行不同 列的零元素，称为独立零元素组，其每个元素称为独立零元素。 5 0 2 0 2 3 0 0 C 【例4】 已知效率矩阵 0 5 6 7 4 8 0 0 求其独立零元素组。
0 , 不 指 派 Ai 承 建 商 店 B j x ij ( i , j 1, 2 ,3, 4 ,5 ) 1, 指 派 Ai 承 建 商 店 B j
指派问题的四个计算步骤

指派问题的四个计算步骤

指派问题的四个计算步骤
指派问题是一种优化问题，旨在找到最佳的分配方式。

解决指派问题通常有四个计算步骤：
1. 创建代价矩阵：将问题抽象为一个二维矩阵，其中每个元素表示将某个任务分配给某个工人的成本或者效益。

代价矩阵的大小为n行m列，其中n表示任务的数量，m表示工人的数量。

2. 匹配行和列：通过在代价矩阵中查找每一行和列的最小元素，将其标记为零。

如果需要，通过减去每一行和列的最小元素，可以使矩阵中至少有n个零。

3. 寻找最佳分配方案：通过选择代价矩阵中的一个零，并将其标记为星号，然后将与该零所在行或列相交的所有其他零标记为井号。

如果井号的数量等于n，则找到了一个最佳分配方案。

如果不是，请执行第4步。

4. 修改代价矩阵：通过选择未被标记的最小元素，并从该元素中减去所有未被标记的行和列的最小值，可以修改代价矩阵。

然后，返回第2步继续迭代，直到找到一个最佳分配方案。

这些计算步骤被称为匈牙利算法或者KM算法。

通过依次执
行这些步骤，可以找到指派问题的最优解。