The problem at hand can be summarized as follows: we have to allocate a ressource to $n$ production units. The allocation to production unit $i$ is $x_i$. Each of the production unit will produce at different rate. Let us define ${\bf r} = (r_1,...,r_n)$ where the production rate of unit $i$ is $r_i$.
We have also a method to come up with an initial allocation $(x_1,...,x_n)$ for a total desired production $R$ (a given constant). We do not give any details about this method because it is irrelevant to the question.
So the method finds a solution ${\bf x}=(x_1,...,x_n)$ to the system $$ R={\bf r}{\bf x}^T$$ where ${\bf x}\geq {\bf 0}$.
We also regroup the production units into categories. We would like to obtain a minimum production from certain categories and a maximum production in other categories. This can be expressed by a system of linear inequalities $B{\bf x}\geq{\bf b}$.
The initial solution found by the method does not necessarily meets all the constraints.
My Questions:
- what would be the best approach to shift the production from one category of production units to another when the constraints are not met (and still have $R={\bf r}{\bf x}^T$ )? We would like the final solution not too far from the initial one and the all the constraints are respected.
- Can you provide some reference (papers, website, etc.) for this type of problems?
Thank you.
This is not probably the answer you want, but you have some $\mathbf{x_0}\ge 0$ such that $\mathbf{r}\mathbf{x_0}^T=R$ and you want to solve:
$$\min_{\mathbf{x}} (\mathbf{x}-\mathbf{x_0})\,D\,(\mathbf{x}-\mathbf{x_0})^T$$ subject to the following constraints: $\mathbf{x\ge 0}$, $\mathbf{r}\mathbf{x}^T=R$ and $B\mathbf{x}\ge \mathbf{b}$.
Here $D$ is a symmetric, positive-definite matrix so it defines an inner product, if $D$ is the identity, we have the usual inner product.
This becomes a standard quadratic minimization problem with linear constaints. You are trying to minimize the distance between $\mathbf{x}$ and your original point $\mathbf{x_0}$.
If it is more costly to change some production categories than others, you can adjust the weights of $D$ to reflect that.
As for references, I think any quadratic programming book must be able to cover this problem.
Notice that there is no guarantee that your feasible set $\mathbf{x\ge 0}$, $\mathbf{r}\mathbf{x}^T=R$ and $B\mathbf{x}\ge \mathbf{b}$ is not empty.
In practice if you have few categories (say two or three), you can check whether the feasible set is empty of not using some computer algebra package. See cylindrical algebraic decomposition in Mathematica or Maple.