Recorrido óptimo de desmontaje/montaje del producto

Question

Tengo una tienda, que contiene productos (denotados por mayúsculas latinas) y componentes (denotados por minúsculas griegas). Un producto está formado por un conjunto de componentes (pero no más de uno de cada componente distinto). Por ejemplo:

A = {, }, B = {}, C = {, , }

Una tienda contiene tanto productos como componentes:

\= {(10, A), (5, B), (20, )}

(Es decir, 10 elementos de A, 5 elementos de B y 20 elementos de ).

Se puede transformar el almacén desmontando un producto, por ejemplo desmontando 2 elementos de C, {(10, C)} se transforma en {(8, C), (2, ), (2, ), (2, )}.

Se puede transformar el almacén ensamblando un producto, por ejemplo ensamblando 1 artículo de B, {(10, ), (10, )} se transforma en {(1, B), (9, ), (10, )}.

Dado un almacén arbitrario, y una cantidad n de un producto requerido X, ¿cómo puedo determinar la(s) secuencia(s) óptima(s) de transformaciones necesarias, para obtener un almacén que contenga (n, X)? Una secuencia es óptima si y sólo si no existe otra secuencia que conste de menos transformaciones.

No soy bueno con la sintaxis matemática, por favor vea mi puesto sobre el mismo tema en SO.

EDIT

Estimado Milcak

He probado tu solución, pero obviamente estoy haciendo algo mal. Digamos que tenemos en la tienda tres productos $A_1 = \{\alpha, \beta, \gamma\}$ , $A_2 = \{\alpha, \gamma, \delta\}$ y $A_3 = \{\beta, \delta\}$ . Necesitamos extraer un producto $X = \{\alpha, \beta, \delta\}$ . Ahora, utilizando su notación, esto sería: $$X = (1, 1, 1) \\ A_1 = (1, 1, 0) \\ A_2 = (1, 0, 1) \\ A_3 = (0, 1, 1)$$

Esto da la ecuación:

$$\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}$$

Que creo que es lo mismo que:

$$z_1 + z_2 = 1 \\ z_1 + z_3 = 1 \\ z_2 + z_3 = 1$$

Ahora la solución es (esperemos) $Z = ( \frac 1 2 , \frac 1 2 , \frac 1 2 )$ .

Tú dices:

entonces escoge $y_i$ de manera que sean enteros no negativos, y que su suma se minimice, lo que equivale a encontrar el punto de la red integral más cercano a $z$ tal que $y_i \ge z_i$ y $y_i \ge 0$ para todos $i$ .

Esto da como resultado $Y = (1, 1, 1)$ pero, ¿no significa esto que necesito uno de cada uno de los $A_i$ ? ¿Las soluciones no serían $(1, 1, 0)$ , $(1, 0, 1)$ y $(0, 1, 1)$ ?

Estoy seguro de haber entendido mal algunas partes de su respuesta. ¿Podría ampliar su respuesta, deshaciendo mis nudos cerebrales? Muchas gracias.

Answer 1

Aquí se busca una solución óptima para un sistema de inecuaciones lineales.

En primer lugar, algunas simplificaciones:

• podemos suponer que sólo necesitamos ensamblar un producto final $X$ . Si necesitáramos $nX$ , entonces necesitamos $n$ -veces más componentes que para $X$ . Pero no importa cómo consigamos los componentes para ensamblar $nX$ Tendremos que gastar $n$ transformaciones para el montaje final. Así, si necesitamos $nX$ podemos suponer que $X$ necesita $n$ veces más de cada componente. En otras palabras, sólo nos preocupamos por minimizar la cantidad de veces que desmontamos los productos.

• En segundo lugar, debemos considerar únicamente los componentes de $X$ . Supongamos que tenemos $k_1$ componentes en total, y $X$ consiste en unos $k \le k_1$ diferentes componentes. Entonces podemos escribir $X = ( x_1, \dots, x_k, 0, \dots, 0 )$ (con $k_1 - k$ $0$ 's). Entonces, si otro producto $A$ tiene componentes $(a_1, \dots, a_k, a_{k+1}, \dots, a_{k_1} )$ No es necesario considerar lo que el $a_{k+1}, \dots, a_{k_1}$ son.

Así que ahora, digamos que tenemos productos $A_1, ..., A_n$ donde $A_i = (a^i_1, \dots, a^i_k)$ . Entonces buscamos enteros no negativos $y_1, \dots, y_n$ tal que $\sum_{i=1}^n y_i$ se minimiza, y:

$$\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} \N - La marca de la casa \begin{pmatrix} x_1\\ \vdots\\ x_k \end{pmatrix} \end{equation}$$

donde " $\ge$ "se refiere a la ordenación lexicográfica .

Ya que suponemos que sí se puede construir $X$ de los otros productos, sabemos que esto siempre tendrá una solución (bastantes, en realidad).

Ahora, puedes resolver la desigualdad anterior como si fuera una igualdad, para esto sin embargo, puedes necesitar extender las cantidades de productos para que contengan números racionales. Se obtiene una solución $z= (z_1, \dots, z_n)$ y luego elegir $y$ para que:

• $y_i$ son enteros no negativos
• $\sum y_i = \left\lceil \sum z_i \right\rceil$ (como $z$ es óptima, una solución entera sólo puede ser peor)
• $\sum |y_i - z_i|$ se minimiza

EDIT

He editado los requisitos finales para $y$ . Me disculpo, por mi error anterior - he entendido mal la relevancia de " $z$ ". Está claro que ésta es la solución óptima (sobre los racionales). Por tanto, $y$ debe estar cerca, sin embargo, no necesariamente que $y_i \ge z_i$ para todos $i$ .

Desde $z$ es óptima, cualquier solución integral requerirá al menos $\sum z_i$ transformaciones. Para $y$ para estar más cerca de $z$ necesitamos $\sum |y_i - z_i|$ minimizado.

Tenemos $\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$ . Así, $y$ es de la forma $(\lfloor z_1 \rfloor + \delta_1, \dots, \lfloor z_n \rfloor + \delta_n)$ , donde $l$ de la $\delta_i$ son $1$ y los demás $0$ .

En su ejemplo $\lfloor z_i \rfloor = 0$ para todos $i$ . Entonces, como $\left\lceil \sum z_i \right\rceil = 2$ tenemos $y = (\delta_1, \delta_2, \delta_3)$ , con una $\delta = 0$ y otros $= 1$ . Eso te da tus tres respuestas, ya que cada coordenada de $z$ es $1/2$ .

---

Puedo tratar de probar esto mañana, pero por ahora tienes al menos un marco básico - $y = (\lfloor z_1 \rfloor + \delta_1, \dots, \lfloor z_n \rfloor + \delta_n)$ como se ha definido anteriormente es claramente correcta, y si la condición " $\sum |y_i - z_i|$ se minimiza" puede ser errónea, la respuesta correcta se limita ahora a $\binom {n}{l}$ posibilidades: es decir, elegir qué $\delta$ son $1$ 's. En general, debería ser una cantidad pequeña de casos, por lo que debería ser fácil de comprobar por fuerza bruta.

Lo actualizaré mañana.