一个整数瓶颈问题的两个多项式算法

讨论下列数学模型Ⅰ:求x=(x_1,x_2,…,x_n)适合条件{■a_(ij)x_j≥b_i (i=1,2,…,m) x_j≥0且整数(j=1,2,…,n)使f(x)■{c_jx_j}达到最小值,其中m＜n,a_(ij),b_i及c_j均为正整数。对该模型,建立了两个多项式算法,其复杂度均为O(n^2),并列举了一个数值例子．

一个带多约束的整数瓶颈问题的Primal算法和Threshold算法

在这篇文章中,我们讨论了数学模型1:maxf(x),x∈{x|x=(x_1,x_2,…,x_n),sum from j=1 to n a_(ij)x_j≤b_i,i=1,2,…,m,x_i≥1且为整数},其中f(x)={c_jx_j}且sum from j=1 to n aI(ij)≤b_i,并给出了模型1最大最优解的定义以及最大最优解的充分必要条件,根据该条件,我们介绍了求模型1的最大最优解的两个算法:Primal算法和Threshold算法。