计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2008年
1期
97-99
,共3页
近似算法%工厂选址%k-种产品
近似算法%工廠選阯%k-種產品
근사산법%공엄선지%k-충산품
对于k-种产品工厂选址问题,有如下描述:存在一组客户和一组可以建立工厂的厂址.现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品.在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质.问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品.对于此类问题,优化目标是最小化建厂费用以及运输费用.论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法.
對于k-種產品工廠選阯問題,有如下描述:存在一組客戶和一組可以建立工廠的廠阯.現在有k種不同的產品,要求每一箇客戶必鬚由k箇不同的工廠來提供k種不同的產品,其中每箇工廠都隻能為客戶提供唯一的一種產品.在該問題中,假定建廠費用以及任意兩箇結點之間的運輸費用都為非負,併且任意兩箇結點之間的運輸費用都滿足對稱和三角不等式關繫的性質.問題的要求是要從若榦廠阯中選擇一組廠阯來建立工廠,給每箇工廠指定一種需要生產的產品,併且給每一箇客戶提供一組指派使每箇客戶都能有k箇工廠來為其供應這k種不同的產品.對于此類問題,優化目標是最小化建廠費用以及運輸費用.論文在假設建廠費用為零的前提下,提齣瞭求解該類問題的一種最壞性能比為3k/2-1的近似算法.
대우k-충산품공엄선지문제,유여하묘술:존재일조객호화일조가이건립공엄적엄지.현재유k충불동적산품,요구매일개객호필수유k개불동적공엄래제공k충불동적산품,기중매개공엄도지능위객호제공유일적일충산품.재해문제중,가정건엄비용이급임의량개결점지간적운수비용도위비부,병차임의량개결점지간적운수비용도만족대칭화삼각불등식관계적성질.문제적요구시요종약간엄지중선택일조엄지래건립공엄,급매개공엄지정일충수요생산적산품,병차급매일개객호제공일조지파사매개객호도능유k개공엄래위기공응저k충불동적산품.대우차류문제,우화목표시최소화건엄비용이급운수비용.논문재가설건엄비용위령적전제하,제출료구해해류문제적일충최배성능비위3k/2-1적근사산법.
