2008 北京奥运会即将开幕，举国上下都在为这一盛事做好准备。为了高效率、
成功地举办奥运会，对物流系统进行规划是必不可少的。
物流系统由若干物流基站组成，以1…N 进行编号。每个物流基站i 都有且
仅有一个后继基站Si，而可以有多个前驱基站。基站i 中需要继续运输的物资都
将被运往后继基站Si，显然一个物流基站的后继基站不能是其本身。编号为1 的
物流基站称为控制基站，从任何物流基站都可将物资运往控制基站。注意控制基
站也有后继基站，以便在需要时进行物资的流通。在物流系统中，高可靠性与低
成本是主要设计目。对于基站i，我们定义其“可靠性”R(i)如下：
设物流基站i 有w 个前驱基站P1，P2，...Pw，即这些基站以i 为后继基站，则基
站i 的可靠性R(i)满足下式：
R(i)=Ci+k ∑R(Pj) ，这里1≤j≤w。
其中Ci 和k 都是常实数且恒为正，且有k 小于1。
整个系统的可靠性与控制基站的可靠性正相关，我们的目标是通过修改物流
系统，即更改某些基站的后继基站，使得控制基站的可靠性R(1)尽量大。但由于
经费限制，最多只能修改m 个基站的后继基站，并且，控制基站的后继基站不
可被修改。因而我们所面临的问题就是，如何修改不超过m 个基站的后继，使
得控制基站的可靠性R(1)最大化。
4 1 0.5 2 3 1 3 10.0 10.0 10.0 10.0
30.00
原有物流系统如左图所示，4 个物流基站的可靠性依次为22.8571，21.4286，
25.7143，10。
最优方案为将2 号基站的后继基站改为1 号，如右图所示。 此时4 个基站
的可靠性依次为30，25，15，10。
对于所有的数据，满足 m ≤ N ≤ 60，Ci ≤ 10^6，0.3 ≤ k < 1。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||