Optimal allocation of resources among disjoint sets of discrete and continuous activities.

摘要

Optimal resource allocation has been a very active area of research in mathematical programming for many years. The problem arises in a large number of different situations, with many different forms. As a result, numerous papers have been published in the related literature, dealing with its various aspects.; The so-called Knapsack Problem is a big family of problems that have been formulated in order to address the numerous variations of the problem that arise in practice. The Knapsack Problem has been the basis for most of the resource allocation models that have been developed. Besides the tremendous theoretical interest that the problem enjoys, the practical applications in which it can be applied are countless. As a result, it continues to stimulate the interest of many researchers, in spite of the fact that it has been studied extensively in the past.; In this dissertation, several variations of this problem, with special constraints, are addressed. Both discrete and continuous decision variables are considered, depending on the nature of the activities that these variables represent. These activities (and therefore the variables representing them too) are partitioned into disjoint sets. A new special type of constraints called equity constraints is introduced that ensures a certain balance on the resource amounts allocated to different activity sets. Special constraints called multiple choice constraints are also included that handle the interactions that arise between the continuous activities of the problem.; The main application of the problems addressed in this dissertation is in transportation management for optimal allocation of funds to highway improvements. The decision variables represent highway improvements that can be applied to the highways under consideration. These highways are partitioned into disjoint segments. Each of the disjoint variable sets corresponds to a set of improvements associated with a highway segment. The objective is to allocate an available budget in order to optimize some appropriate measure of effectiveness. The equity constraints are used to keep a certain balance on the budget amounts allocated to different highway segments.; To the best knowledge of the author, the problems addressed in this dissertation have not been studied in the past. For each of these problems, original theoretical groundwork and important properties are developed that provide valuable insight. Then, based on this theory, efficient algorithms are developed that can be used to obtain the optimal solution of each problem. Besides analyzing the complexity of each of these algorithms, computational results are presented that show their behavior and compare their performance with the performance of commercial software packages that can be used alternatively. The importance and the sensitivity of the various parameters of each of the problems addressed is also investigated thoroughly. This provides important insight that can be very useful in future research. The dissertation concludes with a discussion on the conclusions reached and on how this work can be extended in the future.