Thesis (Ph.D. (Statistics)) -- University of Limpopo, 2017 / Operations Research (OR) is a scientific method for developing quantitatively
well-grounded recommendations for decision making. While it is true that it
uses a variety of mathematical techniques, OR has a much broader scope. It is
in fact a systematic approach to solving problems, which uses one or more analytical
tools in the process of analysis. Over the years, OR has evolved through
different stages. This study is motivated by new real-world challenges needed
for efficiency and innovation in line with the aims and objectives of OR – the
science of better, as classified by the OR Society of the United Kingdom. New
real-world challenges are encountered on a daily basis from problems arising
in the fields of water, energy, agriculture, mining, tourism, IT development,
natural phenomena, transport, climate change, economic and other societal requirements.
To counter all these challenges, new techniques ought to be developed.
The growth of global markets and the resulting increase in competition
have highlighted the need for OR techniques to be improved. These developments,
among other reasons, are an indication that new techniques are needed
to improve the day-to-day running of organisations, regardless of size, type and
location.
The principal aim of this study is to modify and develop new OR techniques
that can be used to solve emerging problems encountered in the areas of linear
programming, integer programming, mixed integer programming, network
routing and travelling salesman problems. Distribution models, resource allocation
models, travelling salesman problem, general linear mixed integer
ii
programming and other network problems that occur in real life, have been
modelled mathematically in this thesis. Most of these models belong to the
NP-hard (non-deterministic polynomial) class of difficult problems. In other
words, these types of problems cannot be solved in polynomial time (P). No general
purpose algorithm for these problems is known. The thesis is divided into
two major areas namely: (1) network models and (2) resource allocation and
distribution models. Under network models, five new techniques have been developed:
the minimum weight algorithm for a non-directed network, maximum
reliability route in both non-directed and directed acyclic network, minimum
spanning tree with index less than two, routing through 0k0 specified nodes,
and a new heuristic to the travelling salesman problem. Under the resource
allocation and distribution models section, four new models have been developed,
and these are: a unified approach to solve transportation and assignment
problems, a transportation branch and bound algorithm for the generalised assignment
problem, a new hybrid search method over the extreme points for
solving a large-scale LP model with non-negative coefficients, and a heuristic
for a mixed integer program using the characteristic equation approach. In
most of the nine approaches developed in the thesis, efforts were done to compare
the effectiveness of the new approaches to existing techniques. Improvements
in the new techniques in solving problems were noted. However, it was
difficult to compare some of the new techniques to the existing ones because
computational packages of the new techniques need to be developed first. This
aspect will be subject matter of future research on developing these techniques
further. It was concluded with strong evidence, that development of new OR
techniques is a must if we are to encounter the emerging problems faced by the
world today.
Key words: NP-hard problem, Network models, Reliability, Heuristic, Largescale
LP, Characteristic equation, Algorithm.
Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:ul/oai:ulspace.ul.ac.za:10386/1930 |
Date | January 2017 |
Creators | Nyamugure, Philimon |
Contributors | Lesaoana, M., Munapo, E., Kumar, S. |
Publisher | University of Limpopo |
Source Sets | South African National ETD Portal |
Language | English |
Detected Language | English |
Type | Thesis |
Format | xxi, 244 leaves |
Relation |
Page generated in 0.0016 seconds