# Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme

 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 en_ZA (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. 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
﻿ Find Full text