帮助—一道很难的数模题！！

丁何平 · 发表于 2004-3-9 05:16:57

某商业公司计划在某地区筹建5家超市，决定由5家建筑公司分别筹建5家超市，5家建筑公司分别对5家超市的抱价(见下表，单位万元)。已知建筑公司A(i) (i=1,2……5),对于超市B(j) (j=1,2……6),建筑公司分别对5家超市的抱价为C(i,j) (i,j=1,2……5)，问商业公司如何分配建筑任务，使其费用最低，并计算出由那家建筑公司筹建那家超市。(C语言编写程序）。

   B(j) B(1)    B(2)    B(3)    B(4)    B(5)
C(i,j)
  A(i)

  A(1)       4       6       7       15    12

  A(2)       7       9       17    14    10

  A(3)       6       9       12       8       7

  A(4)       6       7       14       6    10

  A(5)       6       9       12       10    6

Newton1983 · 发表于 2004-3-9 06:15:23

典型的指派问题。
最优解34，A(1)－B(3),A(2)--B(2),A(3)--B(1),A(4)--B(4),A(5)--B(5).

knight · 发表于 2004-3-9 06:20:44

好像很简单的优化啊
这个问题我觉得用图论里的最短路径最好
你可以将这个问题分成5层（每层优化一个超市），每层是有5种选择（5个建筑公司）
那么你就可以得到一个网络（边权为报价）
你只要求从原点出发到最后一个点的最短路径就可以了
那就应该和简单了吧
拿出以前做的最短路径的程序
加些数据就可以用了吧

itmwk · 发表于 2004-3-9 06:59:45

可以划归为组合最优化的问题嘛，我认为用模拟退火应该不难的。

lex · 发表于 2004-3-9 19:40:02

嗯，是个二分图最佳匹配问题。

丁何平 · 发表于 2004-3-10 22:59:01

没有朋友给我发个程序来！

itmwk · 发表于 2004-3-11 02:30:39

程序还是先照着上面各位说的自己认真写写吧，都让别人帮忙了，自己就没有锻炼提高的机会了。
不行了偶门再帮你

瑞特 · 发表于 2004-4-28 06:38:39

跟酋长嫁女问题差不多!

luoyuan1984 · 发表于 2004-4-29 06:27:53

<

>运筹学里有</P>

totoerer · 发表于 2004-4-29 08:10:40

<

>好像不是太难用c会复杂些</P>

		自动登录	找回密码
密码			注-册-帐-号

帮助—一道很难的数模题！！

我喜欢图论！