0
$\begingroup$

I have the following question, and I need to write it as an integer programming problem:

A manager of a company wants to give presents to his 1000 employers. He can buy the presents from two different suppliers:

  1. Every present costs 110\$. For any present above 500, the manager would have to pay 5\$ extra for insurance (for example, for 502 presents, there will be 10\$ extra for insurance).
  2. Every present costs 120$. For any present above 300, there is a discount of 30% (each present above 300 costs 84\$).

I need to find how many presents he should buy from each supplier, in order to spend the minimal amount of money.

I defined:

$x_1, x_2$ - The number of presents to buy from each supplier.

$z_1$ - Indicator which represents whether or not $x_1 \ge501$

$z_2$ - Indicator which represents whether or not $x_2 \ge301$

I know how to represents the indicators using linear functions, but I don't know how to find a linear objective function.

My best suggestion is:

$$ 110x_1+5z_1(x_1-500)+120x_2-36z_2(x_2-300) $$

However, this is not a linear function, because I multiply the decision variables.

How can I turn it into a linear function?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Introduce nonnegative integer decision variables $y_1$ and $y_2$ to represent "extra" presents. The problem is to minimize $$110x_1+5y_1+120x_2-36y_2$$ subject to \begin{align} x_1 &\le 500 + y_1 \tag1 \\ y_2 &\le (1000-300) z_2 \tag2 \\ x_2 &\ge 300 z_2 \tag3 \end{align} Constraint $(1)$ and the objective enforce $y_1 = \max\{x_1-500, 0\}$. You don't need $z_1$. Constraint $(2)$ enforces $y_2 > 0 \implies z_2 = 1$. Constraint $(3)$ enforces $z_2 = 1 \implies x_2 \ge 300$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.