An algorithm for solving a structured class of linear programming problems (Q1078069)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An algorithm for solving a structured class of linear programming problems |
scientific article |
Statements
An algorithm for solving a structured class of linear programming problems (English)
0 references
1986
0 references
The author presents a procedure for solving the following class of specially structured linear programs: maximize \(Z_{PN}=\sum_{j\in J}c_ jx_ j\) subject to \(\ell_ i\leq \sum_{i\in J(i)}a_ jx_ j\leq b_ i,\) \(i=1,2,...,m,\) \(d_ j\leq x_ j\leq u_ j,\) \(j\in J,\) where \(b_ i,\) \(c_ j\) and \(a_ j\) are positive and \(d_ j\) are nonnegative scalars, \(J=\cup^{m}_{i=1}J(i)\) and the sets J(i) are assumed to be nested: if \(i\neq k\) then either J(i) and J(k) are disjoint or one set is properly contained in the other. The proposed algorithm consists of solving a sequence of continuous knapsack problems each of which requires linear time to solve. The computational effort required by the procedure is proportional to the number of non-zero entries in the constant matrix.
0 references
portfolio selection
0 references
advertising
0 references
production planning
0 references
interval
0 references
linear programming
0 references
knapsack
0 references
weighted selection algorithm
0 references
specially structured linear programs
0 references
sequence of continuous knapsack problems
0 references