Thesis (MComm (Logistics))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: Suppose a lottery draw consists of forming a winning ticket by randomly choosing t m distinct
numbers from a universal set Um = f1; : : : ;mg. Each lottery participant forms a set of tickets
prior to the draw, each ticket consisting of n m distinct numbers from Um, and is awarded a
prize if k minfn; tg or more numbers in at least one of his/her tickets matches those of the
winning ticket. A lottery of this form is denoted by the quadruple hm; n; t; ki, and the prize is
known as a k-prize. The participant's set of tickets is also known as a playing set.
The participant may wish to form a playing set in such a way that the probability of winning
a k-prize is at least 0 < 1. Naturally, the participant will want to minimise the cost
of forming such a playing set, which means that the cardinality of the playing set should be
as small as possible. This combinatorial minimisation problem is known as the incomplete
lottery problem and was introduced by Gr undlingh [16], who also formulated a related problem
called the resource utilisation problem. In this problem one attempts to select a playing set of
pre-speci ed cardinality ` in such a way that the probability of winning a k-prize is maximised.
Gr undlingh [16] studied the incomplete lottery problem and the resource utilisation problem in
the special case where n = t. In this thesis both problems are considered in the general case
where n 6= t. Exact and approximate solution methods are presented and compared to each other
in terms of solution quality achieved, execution time and practical feasibility. The rst solution
method involves a mathematical programming formulation of both problems. Using this solution
method, both problems are solved for small lottery instances. An exhaustive enumeration
solution method, which uses the concept of overlapping playing set structures [5, 16], is reviewed
and used to solve both combinatorial optimisation problems for the same small lottery instances.
The concept of an overlapping playing set structure is further explored and incorporated in an
attempt to solve both combinatorial optimisation problems approximately by means of various
metaheuristic solution approaches, including a simulated annealing algorithm, a tabu search
and a genetic algorithm.
The focus of the thesis nally shifts to a di erent problem involving lotteries. An investigation
is conducted into the probability, P(N; ), of participants sharing a k-prize if a total of N
tickets are purchased by participants of the lottery hm; n; t; ki. Special attention is a orded in
this problem to the jackpot prize of the South African national lottery, Lotto, represented by
the quadruple h49; 6; 6; 6i and how the value of P(N; ) is a ected by the way that participants
select their playing sets. / AFRIKAANSE OPSOMMING: Gestel 'n lotery-trekking bestaan uit die ewekansige seleksie van 'n wenkaartjie bestaande uit
t m verskillende getalle uit 'n universele versameling Um = f1; : : : ;mg. Elke lotery-deelnemer
vorm 'n versameling kaartjies voor die trekking, wat elk uit n m verskillende getalle in Um
bestaan, en wen 'n prys indien k minfn; tg of meer getalle in minstens een van sy/haar
kaartjies ooreenstem met di e in die wenkaartjie. 'n Lotery van hierdie vorm word deur die
viertal hm; n; t; ki aangedui, en die prys staan as 'n k-prys bekend. 'n Deelnemer se kaartjies
staan ook as a spelversameling bekend.
'n Lotery-deelnemer mag poog om sy spelversameling s o te selekteer dat die waarskynlikheid
om 'n k-prys te wen, minstens 0 < 1 is. Die deelnemer sal natuurlik die koste wat met
so 'n spelversameling gepaard gaan, wil minimeer, wat beteken dat die kardinaliteit van sy
spelversameling so klein as moontlik moet wees. Hierdie kombinatoriese minimeringsprobleem
staan as die onvolledige lottery-probleem bekend en is vir die eerste keer deur Gr undlingh [16]
bestudeer, wat ook die verwante hulpbronbenuttingsprobleem geformuleer het. In laasgenoemde
probleem word daar gesoek na 'n spelversameling van vooraf-gespesi seerde kardinaliteit wat
die waarskynlikheid om 'n k-prys te wen, maksimeer.
Gr undlingh [16] het die onvolledige lottery-probleem en die hulpbronbenuttingsprobleem in die
spesiale geval oorweeg waar n = t. In hierdie tesis word beide probleme in die algemeen oorweeg
waar n 6= t. Eksakte en heuristiese oplossingstegnieke word vir beide probleme daargestel
en met mekaar in terme van oplossingskwaliteit, oplossingstyd en praktiese haalbaarheid
vergelyk. Die eerste oplossingstegniek behels 'n wiskundige programmeringsformulering van
beide probleme. Die probleme word deur middel van hierdie benadering vir klein loterye opgelos.
'n Uitputtende enumerasietegniek, wat gebruik maak van die konsep van spelversameling
oorvleuelingstrukture [5, 16], word daarna in o enskou geneem en beide kombinatoriese optimeringsprobleme
word vir dieselfde klein loterye met behulp van hierdie tegniek opgelos. Die
konsep van 'n spelversameling oorvleuelingstruktuur word verder ondersoek en in 'n benaderde
oplossingstegniek vir beide kombinatoriese optimeringsprobleme ge nkorporeer deur gebruik te
maak van verskeie metaheuristiese oplossingsbenaderings, insluitende 'n gesimuleerde
afkoelingsalgoritme, 'n tabu-soektog en 'n genetiese algoritme.
Die fokus in die tesis verskuif laastens na 'n ander probleem oor loterye. 'n Ondersoek word
geloots na die waarskynlikheid, P(N; ), dat lottery-deelnemers 'n k-prys sal deel indien 'n
totaal van N kaartjies in die lotery hm; n; t; ki gekoop word. Spesiale aandag word aan hierdie
probleem geskenk in die geval van die boerpot-prys in die Suid-Afrikaanse nasionale lotery, Lotto,
wat deur die viertal h49; 6; 6; 6i voorgestel word, en hoe die waarde van P(N; ) be nvloed word
deur die manier waarop deelnmers hul spelversamelings selekteer.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/4137 |
| Date | 03 1900 |
| Creators | Du Plessis, Andre |
| Contributors | Van Vuuren, J. H., Burger, A. P., University of Stellenbosch. Faculty of Economic and Management Sciences. Dept. of Logistics. |
| Publisher | Stellenbosch : University of Stellenbosch |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | Unknown |
| Type | Thesis |
| Format | 184 p. : ill. |
| Rights | University of Stellenbosch |
Page generated in 0.0028 seconds