Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme

Simple item page
dc.contributor.advisorDe Kock, H. C.
dc.contributor.authorVisagie, Stephan E.en_ZA
dc.contributor.otherUniversity of Stellenbosch. Faculty of Economic and Management Sciences. Dept. of Logistics.
dc.date.accessioned2008-08-06T12:42:30Zen_ZA
dc.date.accessioned2010-06-01T08:12:05Z
dc.date.available2008-08-06T12:42:30Zen_ZA
dc.date.available2010-06-01T08:12:05Z
dc.date.issued2007-03
dc.descriptionThesis (PhD (Logistics))--University of Stellenbosch, 2007.
dc.description.abstractIn 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.identifier.urihttp://hdl.handle.net/10019.1/1082
dc.language.isoafen_ZA
dc.publisherStellenbosch : University of Stellenbosch
dc.rights.holderUniversity of Stellenbosch
dc.subjectAlgoritmeen_ZA
dc.subjectKnapsack problem (Mathematics)en_ZA
dc.subjectComputer algorithms
dc.subjectMathematical optimization
dc.subjectConvex programming
dc.subjectDissertations -- Logistics
dc.subjectTheses -- Logistics
dc.titleAlgoritmes vir die maksimering van konvekse en verwante knapsakproblemeaf
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Visagie, S E.pdf
Size:
1.08 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Doctoral Degrees (Logistics)