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

Two Polynomial Algorithms for an Integer Bottleneck Problem

讨论下列数学模型Ⅰ:求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),并列举了一个数值例子．

In this paper, we discuss the following mathematical model I：min x∈s max i≥j≥n{cjxj}S={x｜∑n j=1aijxj≥bi,i=1,2…,m;x=（x1,x2…,xn）}is an n-vector of integers and x≥0}where cj ,ajj and bi are positive integer constants and m 〈 n. Furthermore, two polynomial algorithms to Model I are given. Their complexity are O（n^2）. At last, a numerical example is listed.