| 一个瓶颈问题的多项式算法 |
| |
| 引用本文： | 杨延龄,申世伟.一个瓶颈问题的多项式算法[J].北京工商大学学报(自然科学版),1987(1). |
| |
| 作者姓名： | 杨延龄 申世伟 |
| |
| 作者单位： | 北京轻工业学院数学教研室，北京轻工业学院计算机教研室 |
| |
| 摘 要： | 在生产安排中会遇到这样问题:确定满足约束条件x_1+…+x_n=m的正整向量X=(x_1,…,x_n),使目标函数y=min{c_jx_i)达到最大。罗宗俊曾给出这个问题的一个拟多项式算法,大约需要n(m-n)次运算。本文给出一个多项式算法,仅需要n·log_2n次运算。
|
POLYNOMAL ALGORITHM TO A BOTTLENECK PROBLEM |
| |
| Abstract: | Wang De-ying posed the following problem, maximize y=min (c_gx_g), subjected to x_1+…+x_n=m, where x_j iS positive integer and c_j is positive constant. Luo zong-jun gave an algorithm to this problem which needs about n(m-n) comparisons. In this paper we give a new method which needs about n·log_2n comparisons only. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
|
