[Math] Constraints of a linear programming problem

discrete optimizationinteger programminglinear programmingoperations researchoptimization

QUESTION

Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour television shows listed in the table below, Sandy must schedule exactly five of these shows for the period from $8:00$pm to $10:30$ pm next Wednesday evening. For each television show, its estimated advertising revenue in ($million) is shown in the second column of the table. Furthermore, each show has been categorized into one or more of the categories of “Public Interest”, “Contains Violence”, “Comedy”, and “Drama”.

Table 1
Sandy would like to determine a revenue-maximizing schedule of television shows for next Wednesday evening. However, she must be mindful of the following considerations:

  1. There must be at least as many shows scheduled that are categorized as public interest as there are shows scheduled that are categorized as containing violence.

  2. If Sandy schedules "Focus on Science", then she must also schedule either "Jake" or "L.A. Law" (or both).

  3. Sandy cannot schedule both "Focus on Science" and "Urban Action for Education", as both of these shows are considered a bit on the dry side.

  4. If Sandy schedules two or more shows in the comedy category, then she must schedule at least one show in the drama category.

  5. If Sandy schedules more than three shows in the "Contains Violence" category, she will lose an estimated $\$4$ million in advertising revenues from family-oriented sponsors.

So I want to formulate a binary optimization model of the problem. I'm not very sure of the formulation for some of the constraints. Using the initials of the shows,

  1. LL$\,+\,$NS$\,+\,$FS$\,+\,$UA$\,=\,$D$\,+\,$LL$\,+\,$J$\,+\,$NS

  2. J$\,+\,$LL$\,\ge\,$FS

  3. FS$\,+\,$UA$\,\le1$

  4. Not sure how to do this one.

  5. I think I'll need to introduce a binary variable to account for the $4 million if incurred but I'm not sure of how to do it.

I need help with the constraints, can anyone give me some guidance?

Best Answer

Extending on your model lets take two decision variables. $x_{i}$ indicating if the $i^{th}$ show is on schedule or not. Another is $y_{ck}$ if $k$ number of shows are in schedule from category $c$ or not. Note the indexing set for $k$ will depend on number of shows in that category. Now the $(4^{th})$ constraint will be $$ \sum_{i \in Drama} x_{i} \geq \sum_{k = 2} y_{comedy,k} $$ Next we capture the effect of $(5)$ in the objective function. Objective function will look like $$ \sum_{i \in shows} r_{i} x_{i} - 4* \sum_{k = 3} y_{CV,k} $$ where $r_{i}$ is the advertising revenue and we want to maximize the total revenue. The relationship between $x_{i}$ and $y_{ck}$ can be captured with following additional constraints: $$ \sum_{i \in Category} x_{i} = \sum_{k = 1} k* y_{Category,k}$$ $$ \sum_{k = 1} y_{Category,k} \leq 1 \hspace{1cm} \forall \hspace{0.1cm} categories$$

Related Question