Optimum product disassembly / assembly path I have a store Σ, which contains products (denoted by latin mayuscules) and components (denoted by greek minuscules). A product consists of a set of components (but not more than one of each distinct component). For instance:
A = {β, γ}, B = {α}, C = {α, β, γ}
A store contains both products and components:
Σ = {(10, A), (5, B), (20, β)}
(Meaning 10 items of A, 5 items of B and 20 items of β).
You can transform the store by disassembling a product, for instance by disassembling 2 items of C, {(10, C)} transforms into {(8, C), (2, α), (2, β), (2, γ)}.
You can transform the store by assembling a product, for instance by assembling 1 item of B, {(10, α), (10, β)} transforms into {(1, B), (9, α), (10, β)}.
Given an arbitrary store, and an amount n of a required product X, how can I determine the optimal sequence(s) of transformations needed, to obtain a store that contains (n, X)? A sequence is optimal if and only if there exists no other sequence which consists of less transformations.
I am not good at mathematical syntax, please do see my post about the same topic on SO.
EDIT
Dear Milcak
I tried your solution, but obviously I am doing something wrong. Let'say we have in store three products $A_1 = \{\alpha, \beta, \gamma\}$, $A_2 = \{\alpha, \gamma, \delta\}$ and $A_3 = \{\beta, \delta\}$. We need to extract one product $X = \{\alpha, \beta, \delta\}$. Now using your notation this would be:
$$
X = (1, 1, 1) \\
A_1 = (1, 1, 0) \\
A_2 = (1, 0, 1) \\
A_3 = (0, 1, 1)
$$
This gives the equation:
$$
\begin{pmatrix}
1 1 0 \\ 
1 0 1 \\ 
0 1 1
\end{pmatrix}
\begin{pmatrix}
z_1\\ 
z_2\\ 
z_3
\end{pmatrix}
=
\begin{pmatrix}
1 \\ 1 \\ 1
\end{pmatrix}
$$
Which I think is the same as:
$$z_1 + z_2 = 1 \\
z_1 + z_3 = 1 \\
z_2 + z_3 = 1
$$
Now the solution is (hopefully) $Z = ( \frac 1 2 ,  \frac 1 2 ,  \frac 1 2 )$.
You say:

then pick $y_i$'s so that they are non-negative integers, and that their sum is minimized, which is equivalent to finding the closest integral lattice point to $z$ such that $y_i \ge z_i$ and $y_i \ge 0$ for all $i$. 

This yields $Y = (1, 1, 1)$, but doesn't this means I need one of each of the $A_i$? Wouldn't the solutions be $(1, 1, 0)$, $(1, 0, 1)$ and $(0, 1, 1)$?
I am sure I misunderstood some parts of your answer. Could you please expand your answer, undoing my brain knots? Thank you very much.
 A: Here you are looking for an optimal solution for a system of linear inequalities.
First some simplifications:


*

*we may assume that we only need to assemble one final product $X$. If we needed $nX$, then we need $n$-times as much components as for $X$. But no matter how we get the components to assemble $nX$, we will have to spend $n$ transformations for the final assembly. Thus if we need $nX$, we may just assume that $X$ needs $n$ times more of each component. In other words, we only care to minimize the amount times we disassemble products. 

*secondly, we need to only consider the components of $X$. Suppose we have $k_1$ components total, and $X$ consists of some $k \le k_1$ different components. Then we may write $X = ( x_1, \dots, x_k, 0, \dots, 0 )$ (with $k_1 - k$ $0$'s). Then if another product $A$ has components $(a_1, \dots, a_k, a_{k+1}, \dots, a_{k_1} )$, we need not consider what the $ a_{k+1}, \dots, a_{k_1}$ are. 
So now, say we have products $A_1, ..., A_n$ where $A_i = (a^i_1, \dots, a^i_k)$. Then we are looking for non-negative integers $y_1, \dots, y_n$ such that $\sum_{i=1}^n y_i$ is minimized, and:
\begin{equation}
\begin{pmatrix}
a^1_1 & \dots & a^n_1 \\ 
\vdots& \ddots   & \vdots \\ 
a^1_k & \dots   & a^n_k
\end{pmatrix}
\begin{pmatrix}
y_1\\ 
\vdots\\ 
y_n
\end{pmatrix} \ge \begin{pmatrix}
x_1\\ 
\vdots\\ 
x_k
\end{pmatrix}
\end{equation}
where "$\ge$" refers to the lexicographical ordering.
Since we assume that you can indeed build $X$ from the other products, we know that this will always have a solution (quite a few, actually). 
Now, you can solve the above inequality as if it were an equality, for this however, you may need to extend the quantities of products to contain rational numbers. You get a solution $z= (z_1, \dots, z_n)$; then pick $y$ so that:


*

*$y_i$'s are non-negative integers

*$\sum y_i = \left\lceil \sum z_i \right\rceil$ (as $z$ is optimal, an integer solution may only be worse)

*$\sum |y_i - z_i|$ is minimized


EDIT
I have edited the end requirements for $y$. I apologize, for my previous error - I have misunderstood the relevance of "$z$". It is clear that this is the optimal solution (over the rationals). Hence $y$ must be close to it, however, not necessarily that $y_i \ge z_i$ for all $i$. 
Since $z$ is optimal, any integral solution will require at least $\sum z_i$ transformations. For $y$ to be closest to $z$ we need $\sum |y_i - z_i|$ minimized.
We have $ \left\lceil \sum z_i \right\rceil = \left\lfloor \sum z_i \right\rfloor + l \le \left\lfloor \sum z_i \right\rfloor +n - 1$. Thus $y$ is of the form $(\lfloor z_1 \rfloor + \delta_1, \dots, \lfloor z_n \rfloor + \delta_n)$, where $l$ of the $\delta_i$'s are $1$ and the others $0$.
In your example $\lfloor z_i \rfloor = 0$ for all $i$. Then since $ \left\lceil \sum z_i \right\rceil = 2$, we have $y = (\delta_1, \delta_2, \delta_3)$, with one $\delta = 0$ and others $= 1$. That gives you your three answers, since each coordinate of $z$ is $1/2$. 

I can try and prove this tomorrow, but for now you have at least a basic framework - $y = (\lfloor z_1 \rfloor + \delta_1, \dots, \lfloor z_n \rfloor + \delta_n)$ as defined above is clearly correct, and if the condition "$\sum |y_i - z_i|$ is minimized" may be flawed, the correct answer is now limited to $\binom {n}{l}$ possibilities: i.e. choosing which $\delta$'s are $1$'s. In general, this should be a small amount of cases, so it should be easy to check by brute force.
I will update tomorrow.
