1

I have been given a problem to translate into a linear model.

The relevant part to my question is: we're given $ \{{ 1,..., m}\}$ robots to work on $\{ 1,...,n \} $ products

  • each robot $i$ takes time $a_{ij}$ to complete his task on product $j$
  • each robot $i$ has a life time $b_i$
  • if the robot $j$ is employed in producing $j$ we'll incur in a cost $c_{ij}$
  • each product $j$ can be sold at a price of $p_j$
  • a net income of $B$ must be achieved

The task is to make the production uniform (i.e. maximizing the least produced product).

Now, calling $x_{ij} \in \mathbb{R}^+ \cup\{0\}$ the amount of $j$ produced by $i$ and $y_{ij} \in \{ 0,1 \} $ the variable indicating "$x_{ij}>0$" this is what I've come up with:

$\max v$

$\text{s.t.}:$

  • $v \leq x_{ij}$ $\forall (i,j) $, to ensure $v$ is the minimum
  • $\sum _j a_{ij} x_{ij} \leq b_i$ $\forall i $, to guarantee that each robot's capacity is not exceeded
  • $\sum_jp_j\sum_ix_{ij}-\sum_{i,j}c_{ij} y_{ij} \geq B$, minimum net income
  • $x_{ij} \leq \frac{b_i}{a_{ij}} y_{ij} $ $\forall (i,j) $, to translate $x_{ij} > 0 \implies y_{ij}=1$
  • *

where $v \in \mathbb{R}^+ \cup \{0\} $

Now, instead of * I'd like to include a constraint for which $x_{ij} =0 \implies y_{ij}=0$. In the solutions I've been provided with this is not included, and I'm wondering why: if * is not present then $y_{ij} = 1 $ $\wedge $ $x_{ij}=0$ would be admissible, and we could be paying more than we're actually paying.

Why is it correct to formulate the model without * ?

Thanks in advance!

Lilla
  • 2,099

1 Answers1

0

The fundamental issue is that you have a secondary criterion (minimize cost, or maximize net income, or at least don't spend money you don't need to) that is not incorporated in the objective function. If the objective function contained a penalty term for spending, then you would automatically get $y_{ij}=0$ whenever $x_{ij}=0$.

As it stands, the model without * is correct in the sense that, given an optimal solution with gratuitous spending, you can manually change $y_{ij}$ to zero when $x_{ij}$ is zero and get another solution that is both feasible and optimal in the model (but without the gratuitous spending). To enforce this in a constraint, you would need in effect to declare a minimum production level (call it $L_{ij}$) for each combination of robot and product when the robot does in fact produce the product. Constraints * would then be $x_{ij} \ge L_{ij} y_{ij}\,\forall (i,j).$ In a real-world production problem, a constraint like this would be perfectly reasonable from a practical perspective (we're not going to turn the robot on / use operator time / whatever) to make a tiny amount of product (if a tiny amount of product even makes sense, which for discrete products like television sets or metal stampings it clearly does not).

prubin
  • 4,923