数模lingo应用-分配问题

1、例7.7 分配问题（指派问题，Assignment Problem） 这是个给n个人分配n项工作以获得某个最高总效果的问题。第i 个人完成第j 项工作需要平均时间cij。要求给每个人分配一项工作，并要求分配完这些工作，以使完成全部任务的总时间为最小。该问题可表示如下： min s.t. 显然，此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题，每个源有1 单位的可获量，而每个汇有1 单位的需要量。从表面看，这问题要求用整数规划以保证xij 能取0 或1。然而，幸运的是，此问题是运输问题的特例，因此即使不限制xij 取0 或1 ，最优解也将取0 或1。如果把婚姻看作分配问题

2、，丹茨证明，整数性质证明一夫一妻会带来最美满幸福的生活！显然，分配问题可以作为线性规划问题来求解，尽管模型可能很大。例如，给100 人分配100 项工作将使所得的模型具有10000 个变量。这时，如采用专门算法效果会更好。时间复杂度为O(n3 的匈牙利算法便是好选择，这是由Kuhu（1955） 提出的。 现举一例： 若某单位指派工人做某工作的完成时间表如下：j1j2j3j4j5j6j7W16267425W24953858W35219743W47673927W52395726W655228114W7923124510问应如何指派任务，使完成任何的总时间最少？model: !7 个工人，7 个工作

3、的分配问题; sets: workers/w1.w7/; jobs/j1.j7/; links(workers,jobs: cost,volume; endsets !目标函数; min=sum(links: cost*volume; !每个工人只能有一份工作;for(workers(I:sum(jobs(J: volume(I,J=1; !每份工作只能有一个工人;for(jobs(J: sum(workers(I: volume(I,J=1; data: cost= 6 2 6 7 4 2 5 4 9 5 3 8 5 8 5 2 1 9 7 4 3 7 6 7 3 9 2 7 2 3 9 5

4、 7 2 6 5 5 2 2 8 11 4 9 2 3 12 4 5 10;enddataend计算的部分结果为： Global optimal solution found at iteration: 14Objective value: 18.00000Variable Value Reduced CostCOST( W1, J1 6.000000 0.000000COST( W1, J2 2.000000 0.000000COST( W1, J3 6.000000 0.000000COST( W1, J4 7.000000 0.000000COST( W1, J5 4.000000 0.

5、000000COST( W1, J6 2.000000 0.000000COST( W1, J7 5.000000 0.000000COST( W2, J1 4.000000 0.000000COST( W2, J2 9.000000 0.000000COST( W2, J3 5.000000 0.000000COST( W2, J4 3.000000 0.000000COST( W2, J5 8.000000 0.000000COST( W2, J6 5.000000 0.000000COST( W2, J7 8.000000 0.000000COST( W3, J1 5.000000 0.

6、000000COST( W3, J2 2.000000 0.000000COST( W3, J3 1.000000 0.000000COST( W3, J4 9.000000 0.000000COST( W3, J5 7.000000 0.000000COST( W3, J6 4.000000 0.000000COST( W3, J7 3.000000 0.000000COST( W4, J1 7.000000 0.000000COST( W4, J2 6.000000 0.000000COST( W4, J3 7.000000 0.000000COST( W4, J4 3.000000 0.

7、000000COST( W4, J5 9.000000 0.000000COST( W4, J6 2.000000 0.000000COST( W4, J7 7.000000 0.000000COST( W5, J1 2.000000 0.000000COST( W5, J2 3.000000 0.000000COST( W5, J3 9.000000 0.000000COST( W5, J4 5.000000 0.000000COST( W5, J5 7.000000 0.000000COST( W5, J6 2.000000 0.000000COST( W5, J7 6.000000 0.

8、000000COST( W6, J1 5.000000 0.000000COST( W6, J2 5.000000 0.000000COST( W6, J3 2.000000 0.000000COST( W6, J4 2.000000 0.000000COST( W6, J5 8.000000 0.000000COST( W6, J6 11.00000 0.000000COST( W6, J7 4.000000 0.000000COST( W7, J1 9.000000 0.000000COST( W7, J2 2.000000 0.000000COST( W7, J3 3.000000 0.

9、000000COST( W7, J4 12.00000 0.000000COST( W7, J5 4.000000 0.000000COST( W7, J6 5.000000 0.000000COST( W7, J7 10.00000 0.000000VOLUME( W1, J1 0.000000 4.000000VOLUME( W1, J2 0.000000 0.000000VOLUME( W1, J3 0.000000 3.000000VOLUME( W1, J4 0.000000 4.000000VOLUME( W1, J5 1.000000 0.000000VOLUME( W1, J6

10、 0.000000 0.000000VOLUME( W1, J7 0.000000 0.000000VOLUME( W2, J1 0.000000 2.000000VOLUME( W2, J2 0.000000 7.000000VOLUME( W2, J3 0.000000 2.000000VOLUME( W2, J4 1.000000 0.000000VOLUME( W2, J5 0.000000 4.000000VOLUME( W2, J6 0.000000 3.000000VOLUME( W2, J7 0.000000 3.000000VOLUME( W3, J1 0.000000 5.

11、000000VOLUME( W3, J2 0.000000 2.000000VOLUME( W3, J3 0.000000 0.000000VOLUME( W3, J4 0.000000 8.000000VOLUME( W3, J5 0.000000 5.000000VOLUME( W3, J6 0.000000 4.000000VOLUME( W3, J7 1.000000 0.000000VOLUME( W4, J1 0.000000 5.000000VOLUME( W4, J2 0.000000 4.000000VOLUME( W4, J3 0.000000 4.000000VOLUME

12、( W4, J4 0.000000 0.000000VOLUME( W4, J5 0.000000 5.000000VOLUME( W4, J6 1.000000 0.000000VOLUME( W4, J7 0.000000 2.000000VOLUME( W5, J1 1.000000 0.000000VOLUME( W5, J2 0.000000 1.000000VOLUME( W5, J3 0.000000 6.000000VOLUME( W5, J4 0.000000 2.000000VOLUME( W5, J5 0.000000 3.000000VOLUME( W5, J6 0.0

13、00000 0.000000VOLUME( W5, J7 0.000000 1.000000VOLUME( W6, J1 0.000000 4.000000VOLUME( W6, J2 0.000000 4.000000VOLUME( W6, J3 1.000000 0.000000VOLUME( W6, J4 0.000000 0.000000VOLUME( W6, J5 0.000000 5.000000VOLUME( W6, J6 0.000000 10.00000VOLUME( W6, J7 0.000000 0.000000VOLUME( W7, J1 0.000000 7.0000

14、00VOLUME( W7, J2 1.000000 0.000000VOLUME( W7, J3 0.000000 0.000000VOLUME( W7, J4 0.000000 9.000000VOLUME( W7, J5 0.000000 0.000000VOLUME( W7, J6 0.000000 3.000000VOLUME( W7, J7 0.000000 5.000000Row Slack or Surplus Dual Price1 18.00000 -1.0000002 0.000000 -5.0000003 0.000000 -5.0000004 0.000000 -3.0000005 0