How do I go about splitting up 1 LP problem into 2?

Question

I have to set up a linear programming problem corresponding to the following scenario:

---

---

From Chapter 2 here.

Answer 1

What I tried:

Let $x_i$ denote allocated amount of budget in advertising media i

for i=1,2,3,4,5 corresponding to TV,radio,newspaper,billboard U, billboard R

Apparently, I'm supposed to split up into 2 LP Problems.

LP Problem 1:

Maximise sales increase:

$$z = [2.9 \ 2.7 \ 2.5 \ 2.7 \ 2.6] \cdot [x_1 \ x_2 \ x_3 \ x_4 \ x_5]$$

s.t.

$$x_i \ge 0$$

a

1. $$x_1 + x_2 \le (30\%)(1m)$$

2. $$x_4 + x_5 \ge (20\%)(1m)$$

b

$$x_2 \ge 1.5x_1$$

c

$$x_4 \le x_5$$

e

$$\sum_i x_i = 1m$$

d

$$x_3 \le 200,000$$

LP Problem 2:

Maximise sales increase:

$$z = [2.9 \ 2.7 \ 2.5 \ 2.7 \ 2.6] \cdot [x_1 \ x_2 \ x_3 \ x_4 \ x_5] + 0.1*(x_3 - 200,000)$$

s.t.

the same constraints except

d

$$\color{red}{x_3 > 200,000}$$

Since rebates are after the fact unlike discounts, the budget (constraint e) is not affected.

If it was instead discount, the objective function is the same, but the budget constraint is

$1m = \sum_i x_i - x_3 + 0.9*(x_3 - 200,000)$

Answer 2

In the problem 2 keep exactly the same objective as the one from problem 1.

• Just add the variables $$y_1 \ge 0$$$y_1$ will be the part of $x3$ above $200, 000$

• Change the constraint d, by : $$x_3 = 200,000 + y_1$$ or in the standard form : $$x_3 - y_1 = 200,000$$

• And change the constraint e, by : $$x_1 + x_2 + 0.9y_1 + x_4 + x_5 = 1,000,000 - 200,000$$

• Then solve problem 1 and problem 2, the one that gives the better objective is your solution