Text in Afikaans / In this thesis contributions to the solution of the generalised knapsack problem are given and discussed.
Attention is given to problems with functions that are calculable but not necessarily in a closed form.
Algorithms and test problems can be used for problems with closed-form functions as well.
The focus is on the development of good heuristics and not on exact algorithms. Heuristics must be
investigated and good test problems must be designed. A measure of convexity for convex functions
is developed and adapted for concave functions. A test problem generator makes use of this measure
of convexity to create challenging test problems for the concave, convex and mixed knapsack problems.
Four easy-to-interpret characteristics of an S-function are used to create test problems for the S-shaped
as well as the generalised knapsack problem.
The in
uence of the size of the problem and the funding ratio on the speed and the accuracy of the
algorithms are investigated. When applicable, the in
uence of the interval length ratio and the ratio of
concave functions to the total number of functions is also investigated.
The Karush-Kuhn-Tucker conditions play an important role in the development of the algorithms. Suf-
cient conditions for optimality for the convex knapsack problem with xed interval lengths is given
and proved. For the general convex knapsack problem, the key theorem, which contains the stronger
necessary conditions, is given and proved. This proof is so powerful that it can be used to proof the
adapted key theorems for the mixed, S-shaped and the generalised knapsack problems as well.
The exact search-lambda algorithm is developed for the concave knapsack problem with functions that
are not in a closed form. This algorithm is used in the algorithms to solve the mixed and S-shaped
knapsack problems. The exact one-step algorithm is developed for the convex knapsack problem with
xed interval length. This algorithm is O(n). The general convex knapsack problem is solved by using
the pivot algorithm which is O(n2). Optimality cannot be proven but in all cases the optimal solution
was found and for all practical reasons this problem will be considered as being concluded. A good heuristic is developed for the mixed knapsack problem. Further research can be done on this
heuristic as well as on the S-shaped and generalised knapsack problems. / Mathematical Sciences / D. Phil. (Operasionele Navorsing)
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:unisa/oai:uir.unisa.ac.za:10500/8603 |
| Date | 06 February 2013 |
| Creators | Venter, Geertien |
| Contributors | Wolvaardt, J. S. |
| Source Sets | South African National ETD Portal |
| Language | Afrikaans |
| Detected Language | English |
| Type | Thesis |
| Format | 1 online resource (xviii, 302 leaves) : col. ill. |
| Rights | University of South Africa |
Page generated in 0.0027 seconds