Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme

SUNScholar Research Repository

Show simple item record

dc.contributor.advisor De Kock, H. C.
dc.contributor.author Visagie, Stephan E. en_ZA
dc.contributor.other University of Stellenbosch. Faculty of Economic and Management Sciences. Dept. of Logistics.
dc.date.accessioned 2008-08-06T12:42:30Z en_ZA
dc.date.accessioned 2010-06-01T08:12:05Z
dc.date.available 2008-08-06T12:42:30Z en_ZA
dc.date.available 2010-06-01T08:12:05Z
dc.date.issued 2007-03
dc.identifier.uri http://hdl.handle.net/10019.1/1082
dc.description Thesis (PhD (Logistics))--University of Stellenbosch, 2007.
dc.description.abstract In this dissertation original algorithms are introduced to solve separable resource allocation problems (RAPs) with increasing nonlinear functions in the objective function, and lower and upper bounds on each variable. Algorithms are introduced in three special cases. The first case arises when the objective function of the RAP consists of the sum of convex functions and all the variables for these functions range over the same interval. In the second case RAPs with the sum of convex functions in the objective function are considered, but the variables of these functions can range over different intervals. In the last special case RAPs with an objective function comprising the sum of convex and concave functions are considered. In this case the intervals of the variables can range over different values. In the first case two new algorithms, namely the fraction and the slope algorithm are presented to solve the RAPs adhering to the conditions of the case. Both these algorithms yield far better solution times than the existing branch and bound algorithm. A new heuristic and three new algorithms are presented to solve RAPs falling into the second case. The iso-bound heuristic yields, on average, good solutions relative to the optimal objective function value in faster times than exact algorithms. The three algorithms, namely the iso-bound algorithm, the branch and cut algorithm and the iso-bound branch and cut algorithm also yield considerably beter solution times than the existing branch and bound algorithm. It is shown that, on average, the iso-bound branch and cut algorithm yields the fastest solution times, followed by the iso-bound algorithm and then by die branch and cut algorithm. In the third case the necessary and sufficient conditions for optimality are considered. From this, the conclusion is drawn that search techniques for points complying with the necessary conditions will take too long relative to branch and bound techniques. Thus three new algorithms, namely the KL, SKL and IKL algorithms are introduced to solve RAPs falling into this case. These algorithms are generalisations of the branch and bound, branch and cut, and iso-bound algorithms respectively. The KL algorithm was then used as a benchmark. Only the IKL algorithm yields a considerable improvement on the KL algorithm. en_ZA
dc.language.iso af en_ZA
dc.publisher Stellenbosch : University of Stellenbosch
dc.subject Algoritme en_ZA
dc.subject Knapsack problem (Mathematics) en_ZA
dc.subject Computer algorithms
dc.subject Mathematical optimization
dc.subject Convex programming
dc.subject Dissertations -- Logistics
dc.subject Theses -- Logistics
dc.title Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme af
dc.type Thesis en_ZA
dc.rights.holder University of Stellenbosch


Files in this item

This item appears in the following Collection(s)

Show simple item record