Problemas Combinatorios

Los problemas combinatorios son aquellos en los cuales se desea determinar combinaciones óptimas. Se caracterizan por tener un número finito de soluciones factibles. Generalmente, este número es muy grande

Problema de Distribución o Transporte

Tenemos un conjunto de lugares, cada uno de los cuales tiene disponible una cantidad de unidades de un producto. Otro conjunto de lugares, cada uno de los cuales demanda una cantidad de unidades de un producto. Se conoce el costo $C_{ij}$ de enviar una unidad desde el origen $i$ hasta el destino $j$. Si la cantidad de unidades de un producto no es igual a la demanda, entonces tendremos que definir destinos ficticios, ya sean para indicar faltantes como sobrantes.

El objetivo es determinar la cantidad de unidades de producto que cada origen envía a cada destino, para minimizar los costos de transporte totales en un cierto periodo de tiempo.

Supondremos que el producto es homogéneo (el mismo en origen y en destino), y los costos de envío son lineales (proporcionales a la cantidad de producto enviado).

Formulación

Definimos $X_{ij}$ como la cantidad de unidades del origen $i$ a enviar al destino $j$. Debemos asegurarnos que se cumpla la demanda y la disponibilidad de todos los productos.

$$\sum _{j=1}^{n_d}{X}_{ij}=\text{Disponibilidad de origen i},\forall i$$ $$\sum _{i=1}^{n_o}{X}_{ij}=\text{Disponibilidad de destino j},\forall j$$

Para definir el funcional, definiremos las constantes $C_{ij}$ que indica el costo de distribuir unidad del origen $i$ al destino $j$

$$Z_{\min }\sum _{i=0}^{n_o}\sum _{j=0}^{n_d}{C}_{ij}{X}_{ij},\forall i,j$$

Existe un teorema que demuestra que, si todas las ofertas son números enteros, y todas las demandas son números enteros, siendo todas las restricciones igualdades, el problema de distribución o transporte tendrá como resultado que todas las variables tomarán valor entero.

Problema de Transbordo

En este problema, las unidades no son enviadas directamente desde los orígenes hacia los destinos, sino que las unidades van desde los orígenes hasta alguno de los centros de transbordo y desde este a alguno de los destinos.

Formulación

Definimos $X{O}_i{T}_J$ como la cantidad de unidades que son enviadas desde el origen $i$ hasta el transbordo $j$. También definimos $X{T}_{i}Dj$ la cantidad de unidades que son enviadas del transbordo $i$ hasta el destino $j$. Debemos asegurarnos que se cumpla la demanda y la disponibilidad de todos los productos.

$$\sum _{j=1}^{n_t}X{O}_i{T}_j=\text{Disponibilidad de origen i},\forall i$$ $$\sum _{i=1}^{n_t}X{T}_i{D}_j=\text{Disponibilidad de destino j},\forall j$$

Por otro lado, todo lo que entra en un transbordo debe salir

$$\sum _{i=1}^{n_o}X{O}_i{T}_j=\sum _{i=1}^{n_d}X{T}_j{D}_i,\forall j=0,1,\cdots ,n_t$$

Para calcular el funcional, definimos la constante $C{O}_i{T}_j$ como el costo de enviar una unidad del origen $i$ al transbordo $j$. También definimos $C{T}_i{D}_j$ como el costo de enviar una unidad del transbordo $i$ al destino $j$.

$$Z_{\min }\sum _{i=1}^{n_o}\sum _{j=1}^{n_t}C{O}_i{T}_j\times X{O}_i{T}_j+\sum _{i=1}^{n_t}\sum _{j=1}^{n_d}C{T}_i{D}_j\times X{T}_i{D}_j$$

Problema de Asignación

Sean $A,B$, dos conjuntos con $n$ elementos. El problema de asignación consiste en encontrar el conjunto $P$ tal que cada elemento de $P$ es un par $(a,b)\in A\times B$, tal que minimice una función de costo $\sum C(a,b)$. Se debe cumplir que cada elemento de $A$ debe aparecer en $P$ exactamente una vez, y cada elemento de $B$ debe aparecer en $P$ exactamente una vez.

Definimos la variable bivalente $Y_{ij}$ como positiva si el elemento $i$ de $A$ está asignado al elemento $j$ de $B$. Luego restringimos a que cada elemento aparezca una sola vez.

$$\sum _{j=1}^n{Y}_{ij}=1,\forall i$$ $$\sum _{i=1}^n{Y}_{ij}=1,\forall j$$

Para el funcional, definimos la constante $C_{ij}$ como el costo de asociar el elemento $i$ con el elemento $j$.

$$Z_{\min }=\sum _{i=1}^n\sum _{j=1}^n{C}_{ij}{Y}_{ij}$$

Asignación Cuadrática

Ocurre cuando existe un costo o beneficio que se produce únicamente si se dan dos asociaciones particulares en conjunto.

Sea $C_{ijkl}$ el costo asociado al par de asociaciones $ij$ y $kl$. Entonces el funcional valdría:

$$\sum _{i=1}^M\sum _{j=1}^M\sum _{k=1}^M\sum _{l=1}^M{Y}_{ij}{Y}_{kl}{C}_{ijkl}$$

Parece que el funcional es cuadrático. Para solucionarlo, definimos una nueva variable $Y_{ijkl}$ que tome valor uno si ambas asociaciones se cumplen:

$$2Y_{ijkl}\le Y_{ij}+Y_{kl}\le 1+Y_{ijkl}$$

Cambiamos el funcional por el linealizado

$$\sum _{i=1}^M\sum _{j=1}^M\sum _{k=1}^M\sum _{l=1}^M{Y}_{ijkl}{C}_{ijkl}$$

Problema de la Mochila

Este problema se caracteriza por tener una persona con una mochila con una cierta capacidad, y tiene que elegir qué elementos pondrá en ella. Cada elemento aportará un valor, pero también ocupará espacio en la mochila.

Definiendo las siguientes variables:

• Capacidad de la mochila constante: $C$.
• Beneficio unitario por llevar el producto $i$: $P_i$
• Peso del producto $i$: $W_i$
• Cantidad de elementos constante: $N$

Por último, defino $Y_i$ como verdadero si llevo el elemento en la mochila. Entonces podemos plantear el modelo como:

$$\sum _{i=1}^n{W}_i{Y}_i\le C$$ $$Z_{\max }=\sum _{i=1}^n{P}_i{Y}_i$$

El problema es simple, pero existen múltiples variantes

Acotado

En lugar de contar con un elemento de cada tipo, podremos llevar muchos. Bastaría con utilizar variables enteras $X_i$ en lugar de las bivalentes, definiendo límites de ser necesario.

Suma de Subconjuntos

Si el beneficio de cada elemento equivale a su peso, estamos ante un problema de suma de subconjuntos.

Múltiples Mochilas

En este caso, definiremos $Y_{ij}$ si se lleva el elemento $i$ en la mochila $j$. Luego

$$\sum _{i=1}^n{W}_i{Y}_{ij}\le C_j,\forall j$$ $$Z_{\max }=\sum _{i=1}^n\sum _{j=1}^m{P}_i{Y}_{ij}$$

Cada elemento puede estar en una única mochila

$$\sum _{j=1}^m{Y}_{ij}\le 1,\forall i$$

Calendarización (Scheduling)

Se busca encontrar una solución a la pregunta ¿En qué orden deberán ejecutarse las tareas? ¿Quién deberá ejecutar cada tarea? Analicemos el caso de una fábrica.

Definimos dos variables. $I_{ij}$ como el tiempo en el que empieza la tarea $i$ en la máquina $j$, y $F_{ij}$ como el tiempo en el que finaliza la tare $i$ en la máquina $j$. Si las tareas no se interrumpen, tendremos que:

$$F_{ij}=I_{ij}+T_{ij}$$

Siendo $T_{ij}$ el tiempo constante que le toma a la máquina $j$ ejecutar la tarea $i$.

Si únicamente tenemos dos tareas, y si las tareas deben ejecutarse primero en la máquina $1$ y luego en la máquina $2$, entonces debemos definir que:

$$F_{i1}\le I_{i2},\forall i$$

Si buscamos el tiempo total que toma completar el trabajo, entonces tendremos que:

$$\text{FINAL}\ge F_{i2},\forall i$$

Las tareas no pueden ejecutarse a la vez en cada máquina, esto se puede plantear indicar que se deben cumplir uno de dos casos. La tarea $A$ finaliza antes de que empiece la tarea $B$. La tarea $B$ finaliza antes de que empiece la tarea $A$. Planteamos entonces para cada par desordenado de tareas $i,j$ en cada máquina $k$.

$$\begin{array}{c}{F}_{ik}\le I_{jk}+M{Y}_{i<j}\\ F_{jk}\le I_{ik}+M{Y}_{i>j}\\ Y_{i<j}+Y_{i>j}=1\end{array}$$

Notación

Es un problema tan común que se propuso una notación para identificarlos:

$$\alpha |\beta |\gamma$$

El término $\alpha$ representa el entorno de máquinas. Una única máquina se representa con un uno, $m$ máquinas idénticas se identifica con $P_m$.

El segundo término $\beta$ índica las características de la tarea. $pmtn$ en este término indica que las tareas son interrumpibles

El último término $\gamma$ incluye la función objetivo. Minimizar el término se denota con $\text{Cmax}$.

Satisfacibilidad Booleana - SAT

Dada una función proposicional en su forma normal conjuntiva, hallar los valores para los cuales la proposición es verdadera.

Se definen $X_i$ como variables binarias o bivalentes y definimos $Y$ como verdadera si existe solución. Luego planteamos las restricciones de la forma:

$$\begin{array}{c}{f}_1(X)\ge Y\\ f_2(X)\ge Y\\ \cdots \end{array}$$

Donde $f_i$ son las proposiciones cuya intersección forma la función proposicional original.

Uncapacitated Facility Location (UFL)

Se debe decidir dónde abrir los depósitos, qué proporción de la demanda de los clientes satisface cada depositó abierto.

Definimos $X_{ij}$ como la fracción de la demanda de la zona $j$ satisfecha por el depósito ubicado en $i$. Por otro lado, $Y_i$ valdrá $1$ cuando se establece un depósito en $i$.

Conoceremos $f_i$ como el costo anual fijo de establecer un depósito en el lugar $i$, y $c_{ij}$ como el costo de producción y distribución si el depósito que está ubicado en $i$ le proporcionará al cliente $j$ todo lo que este demanda.

El modelo propuesto por Erlenkotter (1978) es minimizar:

$$Z_{\min }=\sum _i\sum _j{c}_{ij}{x}_{ij}+\sum _i{f}_i{y}_i$$

Se debe satisfacer toda la demanda de todos los clientes

$$\sum _i{x}_{ij}=1,\forall j$$

Para que una fábrica distribuya producto, deberá haber sido establecida

$$x_{ij}\le y_i,\forall i,j$$

Para que tenga sentido, se define $Y_i$ como bivalente y $x_{ij}$ como positiva, $\forall i,j$