Indian cinema industry is one the largest cinema industries in the world. There are thousands of theaters in the country situated even in small villages and at remote locations. The medium of cinema has, therefore, long been recognized as an important one for advertising by the industry. In India, this medium is particularly significant for two reasons: One, it is probably the only source of entertainment for a vast population. Though lately televisions have become popular, they still are unaffordable by a large segment of the population. Second, though there has been tremendous improvement in the literacy rate, there are still millions who are functionally illiterate. Therefore, the print media is totally ineffective for advertising for a large population. The audio-visual communication through the medium of cinema is the only way to reach them. In this paper, we address some of the problems faced by the advertisers concerning media planning in the medium of cinema. The approach developed in this paper attempts to strike a balance between the requirements of fidelity, analytical rigor, and practicality. We have addressed two distinct but inter-related problems: (a) Problem of Evaluation, and (b) Problem of Selection. In the problem of evaluation, we are interested in evaluating a given plan in terms of its reach, frequency and the OTS (Opportunity-To-See) distribution. In the selection problem, we are interested in developing a cinema plan, which is optimal in some sense. We have used the probability theory and mathematical programming concepts to develop appropriate models. These models have been tested on real-life situations and it has been observed that it is possible to reduce advertising costs by at least 20 to 25 per cent.