On two combinatorial optimisation problems involving lotteries

Simple item page
dc.contributor.advisorVan Vuuren, J. H.
dc.contributor.advisorBurger, A. P.
dc.contributor.authorDu Plessis, Andreen_ZA
dc.contributor.otherUniversity of Stellenbosch. Faculty of Economic and Management Sciences. Dept. of Logistics.
dc.date.accessioned2010-02-22en_ZA
dc.date.available2010-02-22en_ZA
dc.date.issued2010-03
dc.descriptionThesis (MComm (Logistics))--University of Stellenbosch, 2010.
dc.description.abstractENGLISH 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.en
dc.description.abstractAFRIKAANSE 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.af
dc.format.extent184 p. : ill.
dc.identifier.urihttp://hdl.handle.net/10019.1/4137
dc.language.isoen
dc.publisherStellenbosch : University of Stellenbosch
dc.rights.holderUniversity of Stellenbosch
dc.subjectLotteryen_ZA
dc.subjectComplete lottery problemen_ZA
dc.subjectResource utilisation problemen_ZA
dc.subjectIncomplete lottery problemen_ZA
dc.subjectDissertations -- Logisticsen
dc.subjectTheses -- Logisticsen
dc.subjectDissertations -- Operations researchen
dc.subjectTheses -- Operations researchen
dc.titleOn two combinatorial optimisation problems involving lotteriesen_ZA
dc.typeThesis
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
duplessis_two_2010.pdf
Size:
1.8 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters Degrees (Logistics)