Knapsack Problem A Case Study of Metro T.V., A Television Station in Ghana

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
The Knapsack or Rucksack problem is a problem in combinatorial optimization. Though the name existed in folklore, it might have been derived from the maximization problem of the best choice of essentials that can fit into a bag to be carried on a trip. Supposing a traveler has a traveling bag (knapsack) that takes a maximum of of “items.” The traveler has items (1,2,3, …, n), they weigh and are of value to him. How many pieces of items should be placed in the knapsack so as not to exceed the maximum weight of “b”? The practice of selecting commercials to be played on air from a pile of commercials in most TV and radio stations to generate the maximum revenue given a fixed time, is a clear case of Knapsack problem. In this research, our interest is in the systematic and efficient way of organizing adverts on Metro TV, a TV station in Ghana, with the help of the Heuristic Scheme (simple flip) proposed by Amponsah and Darkwah (2007), a variant of the classical 0-1 Knapsack problem to maximize income. Nevertheless, our methodology focuses among others, on general techniques such as Simulated Annealing, Genetic Algorithm, Branch-bound Method, Dominance Relations, Dynamic Programming and thus may be applicable in implementation of the Knapsack problem. We also pointed out some reasons for the good practical performance of our algorithm. A computer solution developed in Visual Basic Dot Net employed in analyzing the data collected from Metro TV can be used for any problems that can be modeled as a single 0-1 Knapsack problem. The results of the analysis of data showed a 35.19% increase in income of the station; from GH¢21,000.00 when adverts were selected arbitrarily to GH¢28,390.00 daily, at the time the software was used.
A Thesis Submitted to the Department of Mathematics, Kwame Nkrumah University of Science and Technology in Partial Fulfillment of the Requirement of the Degree of, Master of Science.