metodo de alforja-carga de bultos-ruta corta-asignacion de recursos
TRANSCRIPT
Programación Dinámica
1. METODO DE LA ALFORJA (MOCHILA O KNAPSACK)...........6
1.1. Definición...........................................................................................6
1.2. Formulación.......................................................................................8
1.3. Métodos de resolución...........................................................................9
1.4. Algoritmos voraces..............................................................................10
Algoritmos voraces...................................................................................14
2. PROBLEMA DE LA ASIGNACION DE RECURSOS..................16
3. METODO HUNGARO....................................................................20
4. PROBLEMA DE ASIGNACIÓN....................................................25
5. PROBLEMA DE CARGA DE BULTOS........................................29
6. PROBLEMAS DE RUTA CORTA.................................................33
1. METODO DE LA ALFORJA (MOCHILA O KNAPSACK)
El problema de la mochila es un problema de programación entera, estando ésta
última dentro del campo de la programación matemática y consiste en escoger un
conjunto de artículos para llenar una mochila de modo de que se cumplan ciertas
restricciones.
1.1. Definición
Un problema típico de programación entera es el que nos ocupa, “el
problema de la mochila”, que responde a la siguiente situación: imagínese hacer
una excursión a la que solo podemos llevar una mochila que, lógicamente, tiene
una capacidad limitada. Cada objeto que introducimos ocupa un volumen
dentro de la misma y en contrapartida durante el viaje nos proporcionará un
beneficio o utilidad (ejemplo: una cantimplora), el problema surge cuando
debemos elegir qué objetos seleccionar para llevar en la mochila de forma que
nuestro beneficio sea máximo (tengamos todo lo necesario) sin exceder su
capacidad.
Esta situación se presenta con cierta frecuencia en los ámbitos económico e
industrial, donde la mochila suele representar la restricción presupuestaria
(cantidad máxima de recursos económicos de los que se dispone) y donde la
utilidad de los objetos seleccionados se equipara a un beneficio económico por
adquirir o llevar a cabo ciertas acciones.
Veamos a continuación un ejemplo de la aplicación del planteamiento de la
mochila al ámbito económico.
Ejemplo: una empresa que fabrica lapiceros, “Escribe Bien S.A.” que en el
ejercicio económico que se cierra ha obtenido un excedente de 300.000€ (su
beneficio neto, una vez descontados los impuestos y retribuidos los fondos
propios es de 300.000€), esto le hace replantearse una posible inversión
productiva (ampliar la capacidad productiva, ampliar la fábrica, contratar más
trabajadores,....) que le permita incrementar su cartera de productos (número de
productos que tiene en el mercado). El gerente de la empresa, Don L, reúne a
sus asesores financieros y comerciales para que determinen de forma conjunta
qué productos serán los escogidos para la ampliación de cartera.
Los asesores comerciales sugieren los siguientes productos, basándose en
estudios de mercado que han realizado para estimar la cifra de negocios que
cada nuevo producto generará:
- Lápices de colores con un beneficio de 200.000 €, esta cuantía es la que
relacionamos con la utilidad que mencionábamos en la definición.
- Gomas de borrar con un beneficio de 100.000 €
- Minas para portaminas con un beneficio de 250.000 €
- Carboncillos con un beneficio de 150.000 €
Por su parte, los asesores financieros han estudiado los costes que implica
reformar las instalaciones productivas para poder incrementar la cartera de
productos, estos costes se podrían equiparar al volumen que ocupan los objetos
dentro de la mochila, por tanto, la suma de estos costes deberá ser menor a la
capacidad de la mochila, en este caso, los recursos financieros sobrantes:
300.000€.
- Coste de las instalaciones para fabricar lápices de colores: 75.000 €
- Coste de las instalaciones para fabricar gomas de borrar: 150.000 €
- Coste de las instalaciones para fabricar minas para portaminas: 100.000 €
- Coste de las instalaciones para fabricar carboncillos: 50.000 €
Intuitivamente escogerá fabricar aquel producto que mayores beneficios le
dé, si con la inversión en la fabricación de ese nuevo producto no consume los
300.000 € podrá plantearse aumentar aún más su cartera y así sucesivamente
mientras le resten recursos.
1.2. Formulación
Para facilitar la comprensión del lector, antes de incorporar a este escrito la
formulación del problema, analizaremos las partes de las que se compone la
misma.
Datos del problema
- n: número de objetos entre los que se puede elegir.
- ci: peso del objeto “i” - se refiere el objeto “í”-ésimo que no es más que una forma
de hacer referencia a un objeto cualquiera que pueda ser incluido en la mochila -, es
decir, ci representa el coste de escoger un objeto, en tanto en cuanto va a ocupar un
“espacio de la mochila” que dejará fuera otros objetos.
- bi: utilidad o beneficio que proporciona cada objeto, de nuevo se hace referencia al
objeto i-ésimo.
- P: capacidad de la mochila, equivale al presupuesto máximo del que se dispone.
Variables a tener en cuenta
Los elementos a introducir en la mochila van a ser nuestras variables objeto de
análisis, cada variable la denotaremos como xi. El rasgo más importante de nuestras
xi es que se tratan de variables dicotómicas o binaria, es decir, sólo pueden tomar
dos valores, en este caso, escogeremos el valor “1” (si el objeto se incluye en la
mochila) ó “0” (si el objeto se excluye de la mochila)
Restricciones
La restricción vendrá marcada por la capacidad máxima de la mochila, de tal forma
que la suma de todos los objetos multiplicados por el espacio que ocupan en la
mochila no podrá exceder dicha capacidad máxima. Su formulación matemática es
la que sigue:
Función a maximizar
Tal y como se expresa en la definición, el objetivo de este problema es
seleccionar aquellos objetos que introducidos en la mochila nos proporcionan una
mayor utilidad. En otras palabras, lo que debemos hacer es maximizar la utilidad de
nuestra mochila.
Si redefinimos el problema introduciendo los elementos que mencionamos en las
líneas precedentes llegaremos a la siguiente formulación:
“El problema de la mochila consiste en llenar una mochila con n objetos. Cada
objeto i tiene un peso determinado ci siempre positivo y una utilidad o valor
asociado, también positivo, bi. Se ha de considerar además que la mochila tiene
una capacidad limitada P, por tanto, se han de escoger aquellos objetos xi que
maximicen la utilidad de quien llena la mochila sin exceder su capacidad”.
Ahora procederemos a formular el problema de la mochila:
Nota: pueden existir otras restricciones técnicas que nada tengan que ver con las
anteriormente citadas que serían comunes a cualquier problema de Programación
Matemática.
1.3. Métodos de resolución
Este problema se ha resuelto tradicionalmente mediante programación lineal
entera.
El hecho de que se trate de programación lineal hace referencia a que la
función a optimizar y las inecuaciones que constituyen las restricciones han de
ser lineales, es decir, han de ser funciones cuyas incógnitas estén elevadas
exclusivamente a la unidad.
Existe otra forma de resolver este tipo de problema, a través de los
denominados algoritmos voraces. Una aproximación voraz consiste en que cada
elemento a considerar se evalúa una única vez, siendo descartado o
seleccionado, de tal forma que si es seleccionado forma parte de la solución, y
si es descartado, no forma parte de la solución ni volverá a ser considerado para
la misma. Con este método no siempre es posible dar una solución a un
problema.
Ejemplo: si continuamos con el ejemplo de “Escribe bien S.A.” vemos que
la solución intuitiva que aportamos se corresponde con el método de algoritmos
voraces comentado en el párrafo anterior.
Si quisiéramos resolver el problema mediante programación lineal entera
tendríamos que plantear el modelo, del mismo modo que hicimos con
Costuritas S.L. al comentar cómo se expresa un problema que solucionar por
este método.
Otro sistema para resolver el problema de la mochila es mediante algoritmos
genéticos que son métodos de optimización que tratan de hallar (xi,...,xn) tales
que sea máximo.
1.4. Algoritmos voraces
a) Aplicación del método:
Partimos de la formulación del problema de la mochila aportada
anteriormente:
Maximizar [Sumatoria (bi*xi) desde i= 1 hasta n]
sujeto a: xi Є {0,1} con i =1,..., n
[Sumatoria (ci*xi) desde i=1 hasta n] < P
La utilización de un algoritmo voraz consiste en introducir en la mochila
según orden decreciente de utilidad (beneficio) los diversos objetos. En una
primera etapa, se adicionarán unidades enteras hasta que, por motivo de
capacidad, no sea posible seguir introduciendo enteros y haya que añadir la
porción que quepa del siguiente objeto.
b) Concepto de solución óptima:
Teorema: si se ordenan los objetos de forma de decreciente en cuanto a su
relación (utilidad/ponderación = bi/ci) y se introducen en la mochila enteros en
este orden mientras quepan y cuando no quede capacidad para uno entero se
añade la porción que aún tenga cabida el resultado al que se llega es una
solución óptima.
Planteamiento del problema
El Club Baloncesto Unicaja de Málaga ante la lesión de Daniel Santiago y la
escasa aportación del pívot brasileño Vitor Faverani se plantea reforzar el juego
interior para la disputa de los play-offs por el título a partir del 17 de mayo,
para ello la secretaria técnica del equipo ha sondeado el mercado y ha
encontrado a 5 jugadores que pueden adaptarse a lo requerido por el entrenador.
Para reforzar el equipo el Unicaja dispone de un presupuesto máximo de 50.000
$ / mes. En la siguiente tabla aparece una relación de los candidatos a ser
fichados junto con su aportación esperada y el sueldo que percibirían.
JUGADOR/EQUIPO SUELDO APORTACIÓN
Esteban Batista (Hawks) 50000 $ 15
Jared Reiner (Sioux Falls) 25200 $ 8
Chriss Burgess (Ulsan Phoebus) 36000 $ 15
Marcus Goree (Benetton) 47000 $ 17
K.C. Walekowski (Farho Vigo) 12000 $ 7
Como puede apreciarse, en este caso, estamos aplicando el problema de la
mochila a una situación de índole económico. Nuestra intención es elegir los
mejores jugadores –aquellos cuya aportación es mayor, es decir, los que
proporcionan una mayor utilidad – para el Unicaja optimizando también el
desembolso que conlleva una nueva contratación. Sin perder en ningún
momento de vista la restricción de 50.000 $.
Formulación del problema
Una vez se ha planteado el problema, el siguiente paso lógico es formularlo
en términos matemáticos, recuérdese que se está intentando llegar a una
solución cuantitativa concreta y no simplemente intuitiva.
Maximizar 15x1 + 8x2 + 15x3 + 17x4 +7x5
sujeto a: 50000x1 + 25200x2 + 36000x3 + 47000x4 + 12000x5 < 50000
x1,x2,x3,x4,x5 Є {0,1}
siendo:
x1 Esteban Batista (Hawks)
x2 Jared Reiner (Sioux Falls)
x3 Chriss Burgess (Ulsan Phoebus)
x4 Marcus Goree (Benetton)
x5 K.C. Walekowski (Farho Vigo)
El conjunto de ecuaciones que aparecen en las líneas precedentes
constituyen la formulación matemática del problema que estamos tratando de
resolver. Para una mejor comprensión del lector, analizaremos lo que
representa cada una de ellas.
La primera ecuación: 15x1 + 8x2 + 15x3 + 17x4 +7x5 es la suma de las
utilidades que reporta cada jugador, representa, por tanto, la utilidad que
percibirá Unicaja en función de la combinación de jugadores que elija, puesto
que se trata de la utilidad (en este caso, estará medida por el número de
partidos que el jugador haga ganar o en los que tenga un peso importante) al
club de Baloncesto le interesará que sea lo mayor posible. De ahí que el
objetivo sea maximizar la función.
Las otras dos inecuaciones representan el conjunto de restricciones del
problema, la primera de ella: 50.000x1 + 25.200x2 + 36.000x3 + 47.000x4 +
12.000x5 < 50.000, se corresponde con la expresión [Sumatoria (ci*xi) desde
i=1 hasta n] < P, donde, los ci o pesos del objeto “i”, se corresponden con los
salarios de cada jugador y las xi representan a cada jugador, al igual que
ocurre en la ecuación anterior. P es la restricción presupuestaria del equipo, es
decir, son los 50.000 $ mensuales de los que puede disponer para remunerar a
sus nuevos jugadores.
La última inecuación: x1,x2,x3,x4,x5 Є {0,1}, trata de indicar que estamos
ante un problema dicotómico en el que cada variable puede tomar sólo el
valor 1 o el valor 0. En este caso, si x toma el valor 1 querrá decir que el
jugador es contratado y si toma el valor 0, será señal de que el club prefiere
prescindir de él.
Solución del problema planteado
El problema de elección que afronta el Club Baloncesto Unicaja se puede
resolver por distintas vías:
- Por el método tradicional: a través de la maximización del problema
anteriormente formulado mediante métodos de programación lineal entera.
- Por algoritmos: existen tipos de algoritmos (genéticos, voraces), pero en
esta ocasión mostraremos el algoritmo más intuitivo y sencillo de ver. Este
algoritmo es el denominado "voraz". Dejamos a un lado el algoritmo genético
ya que al ser poco intuitivo y tener cierta complejidad (no en su teoría, sino en
su práctica) podría hacer que el lector tuviera cierta reticencia a continuar con
su lectura y comprensión.
Método tradicional (Programación Lineal Entera)
Retomemos el problema formulado e reinterpretemos dicha formulación
para comprender mejor cómo vamos a resolver el problema de elección de
jugadores (vamos a repetir de forma resumida el desarrollo del punto 3.2.)
Maximizar 15x1 + 8x2 + 15x3 + 17x4 +7x5
sujeto a: 50000x1 + 25200x2 + 36000x3 + 47000x4 + 12000x5 < 50000
x1,x2,x3,x4,x5 Є {0,1}
Lo que pretendemos es maximizar el valor que los jugadores contratados
aportarían al equipo, teniendo en cuenta que hay un presupuesto al que
ajustarse (50000 $/mes). No hemos de olvidar que la solución a este problema
habrá de darse en números enteros, ya que es imposible contratar una porción
de jugador.
Algoritmos voraces
El método de algoritmo voraces es muy parecido a aquello que llaman "la
cuenta de la vieja". Se trata, simplemente, de elegir la opción más lógica de
acuerdo con un criterio. Para este ejemplo escogeremos como criterio el ratio
"Aportación/Sueldo".
Parece lógico ponderarlo así, ya que tenemos en cuenta ambos factores en
la decisión. Cuanto más alto sea este ratio, preferible será contratar a este
jugador. Reconsideraremos el sueldo, dividiéndolo por 1000 para hacer el
ratio más operativo, lo que obtendremos será llamado *Sueldo*.
Jugador (Equipo) Sueldo Aportación Ratio
Esteban Batista (Hawks) 50 15 0,3000
Jared Reiner (Sioux Falls) 25,2 8 0,3175
Chriss Burgess (Ulsan Phoebus) 36 15 0,4167
Marcus Goree (Benetton) 47 17 0,3617
K.C. Walekowski (Farho Vigo) 12 7 0,5833
Como hemos dicho, escogeremos aquellos jugadores con mejor ratio hasta
agotar el presupuesto.
- K.C. Walekowski: ratio =0.58333, sueldo = 12000 $
- Chriss Burgess: ratio =0.41666, sueldo = 36000 $, total acumulado =
48000 $
Como no hay más jugadores cuyo sueldo pueda entrar en presupuesto, éste
es nuestro resultado definitivo por algoritmos voraces.
El resultado que nos ofrece el método de algoritmos voraces coincide con
el obtenido por el método tradicional. Aquí lógica y matemáticas puras
coinciden y se refrendan mutuamente, por lo que la directiva del club no
deberá tener dudas en la contratación de nuestros dos nuevos fichajes:
- K.C. Walekowski
- Chriss Burgess
2. PROBLEMA DE LA ASIGNACION DE RECURSOS
Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o
no. Así Muchas de las situaciones en la vida exigen una de dos respuestas posibles:
si o no. Así es que podemos representar éstas posibilidades con los valores 0 (no) y
1 (si), y aprovechar las matemáticas para que nos den una mano ante decisiones
difíciles; a esto es lo que solemos llamar -por obvias razones- Programación
Binaria. Una de las muchísimas aplicaciones de la Programación Binaria, es el
problema de la Asignación. Este método analiza el problema de asignar un cierto
número de recursos a un determinado número de tareas, con base en algún tipo de
valoración para cada recurso. Cada recurso, podrá ser asignado a una sola tarea. El
PA consiste en asignar recursos a tareas en función de un objetivo ligado a la
eficiencia del sistema. Un ejemplo típico es el de asignación de personas a turnos
horarios, o el de asignar personas a máquinas
Se tienen tres personas (recurso) para asignarlos a tres labores diferentes. Cada
uno de ellos puede efectuar cualquiera de las tareas existentes, pero con diferente
nivel de especialidad. Sus respectivos jefes los han calificado de 1 a 10, para cada
tarea en particular. Por supuesto el objetivo es el de asignar a las personas de
manera tal que la calificación en conjunto sea la máxima. Ver tabla de
calificaciones abajo.
Calificación de Operario por Tarea
Tarea 1 Tarea 2 Tarea 3
Operario 1 8 6 4
Operario 2 9 7 3
Operario 3 6 5 7
Nota: También funciona para minimizar. Por ejemplo, en vez de calificación podrían ser tiempos de
manufactura de cualquier tipo de productos, y el objetivo sería el de minimizar el tiempo total de
manufactura.
Xij = 1 si asignamos el operario i a la tarea j, de lo contrario 0
En éste orden de ideas, nuestro deseo es maximizar la calificación total al asignar
los operarios a las diferentes tareas.
Max Z = 8X11 + 6 X12 + 4 X13 + 9X21 +7 X22 +3X33 +6X31 +5X32 +7X33
Sujeto a:
1. Cada operario sólo puede tener una tarea asignada
X11 +X12 +X13 = 1 (Es decir, sólo se puede responder Si una sóla vez.)
X21 +X22 +X23 = 1
X31 +X32 +X33 = 1
2. Cada tarea puede tener un sólo operario asignado (la restricción anterior
no necesariamente garantiza esto)
X11 + X21 + X31 = 1
X12 + X22 + X32 = 1
X13 + X23 + X33 = 1
3. La obvia: Xij = 0,1 para toda i y toda j.
Ahora en Excel...
Este puede ser el formato:
Las variables de decisión, están localizadas en el rango de celdas B4:D6, como
ya habíamos dicho son binarias, van a tomar el valor de 1 si se asigna ese operario a
esa tarea, cero de lo contrario. La calificación que se logre está en la celda B2, y es
el resultado de sumar el producto de dichas variables con su respectiva calificación
en la matriz de abajo. Ya se había dicho que esto se logra facílmente así:
=SUMAPRODUCTO(B4:D6,B9:D11). Como un operario sólo se puede asignar a
una tarea, colocamos una columna de Suma (E), ésta es por ejemplo para la celda
E4: =B4+C4+D4. Cuando agreguemos las restricciones, ésta columna debe ser igual
a uno, pues sólo se puede responder que si una vez, ni más, ni menos. De igual
manera agregamos una fila (7), para asegurarnos que a una tarea sólo se asigne un
operario, por ejemplo la celda B7: =B4+B5+B6 Deberá ser igual a 1. Ahora en el
cuadro de diálogo de los parámetros de Solver, lo colocamos así:
Luego de hacer click en resolver...
La calificación máxima lograda es de 22. Y se asignó el operario 1 a la tarea 2,
el operario 2 a la tarea 1 y el operario 3 a la tarea 3. Fácil, no?
Para los programas Lineales enteros es muy importante que Solver, esté
debidamente configurado para un número suficiente de iteraciones, de tiempo, de
precisión y de convergencia, para esto ver los detalles de Solver.
3. METODO HUNGARO
Se necesita procesar 4 diferentes tareas para lo cual se cuenta con 4 máquinas.
Por diferencias tecnológicas el desperdicio que se produce depende del tipo de tarea
y la máquina en la cual se ejecuta, dada la matriz de Desperdicios expresada en
pesos definir la asignación óptima.
MAQUINAS
TAREAS 1 2 3 4
A 49 86 54 70
B 45 79 66 81
C 46 58 78 88
D 44 38 66 69
Como se trata de Desperdicios, buscaremos MINIMIZARLOS.
Checamos que todas las casillas tengan su costo unitario, en este caso se cumple
sin ningún problema.
Balanceamos la tabla M= renglones = 4 N= columnas= 4
Por lo que M=N, quedando balanceada.
MAQUINAS
TAREAS 1 2 3 4
A 49 86 54 70
B 45 79 66 81
C 46 58 78 88
D 44 38 66 69
POR RENGLÓN
Elegir el menor valor de renglón y restarlo a los demás. En este caso es son :
49,45,46,38.
Restamos ese valor a cada uno de los demás del renglón.
MAQUINAS
TAREA
S
1 2 3 4
A49-49=0 86-49=37 54-49=5 70-49=21
B
45-45=0 79-45=34 66-45=21 81-45=36
C
46-46=0 58-46=12 78-46=32 88-46=42
D
44-38=6 38-38=0 66-38=28 69-38=31
Formamos la nueva tabla
MAQUINAS
TAREAS 1 2 3 4
A 0 37 5 21
B 0 34 21 36
C 0 12 32 42
D 6 0 28 31
POR COLUMNA.
Elegimos los menores valores de cada columna en este caso son : 0,0,5,21
Restamos esos valores a los demás números de las columnas
MAQUINAS
TAREAS 1 2 3 4
A 0-0=0 37-0=37 5-5=0 21-21=0
B 0-0=0 34-0=34 21-5=16 36-21=15
C 0-0=0 12-0=12 32-5=27 42-21=21
D 6-0=6 0-0=0 28-5=23 31-21=10
Obtenemos la nueva tabla:
MAQUINAS
TAREAS 1 2 3 4
A 0 37 0 0
B 0 34 16 15
C 0 12 27 21
D 6 0 23 10
Trazamos las líneas.
MAQUINAS
TAREAS 1 2 3 4
A 0 37 0 0
B 0 34 16 15
C 0 12 27 21
D 6 0 23 10
Contamos el número de líneas y observamos que son 3 líneas y el número de la
matriz es de 4 por lo que NO ES ÓPTIMO.
Buscamos dentro de la tabla el menor valor no tachado en este caso es 12
Lo restamos a todos los demás, respetando los valores de los ya tachados y
adicionándolos a los que están intersectados.
MAQUINAS
TAREAS 1 2 3 4
A 0+12=12 37 0 0
B 0 34-12=22 16-12=4 15-12=3
C 0 12-12=0 27-12=15 21-12=9
D 6+12=18 0 23 10
Nos queda:
MAQUINAS
TAREAS 1 2 3 4
A 12 37 0 0
B 0 22 4 3
C 0 0 15 9
D 18 0 23 10
Trazamos las líneas.
3 ≠ 4 NO ES ÓPTIMO
Volvemos a buscar el menor número de los no tachados.
MAQUINAS
TAREAS 1 2 3 4
A 12+3=15 37+3=40 0 0
B 0 22 4-3=1 3-3=0
C 0 0 15-3=12 9-3=6
D 18 0 23-3=20 10-3=7
En este caso es 3 y se lo restamos a los demás no tachados y respetamos a los
tachados y se los sumamos a los intersectados. Y volvemos a trazar líneas.
MAQUINAS
TAREAS 1 2 3 4
A 15 40 0 0
B 0 22 1 0
C 0 0 12 6
D 18 0 20 7
4=4 ES ÓPTIMO
Ahora checamos las asignaciones, sean 1 a 1.
MAQUINAS
TAREAS 1 2 3 4
A 15 40 0 0
B 0 22 1 0
C 0 0 12 6
D 18 0 20 7
0 = se escogen
0= se deshabilitan
Se traduce la solución:
Realizar la tarea A en la máquina 3 con un costo de $54
Realizar la tarea B con la máquina 4 con un costo $81.
Realizar la tarea C en la máquina 1 con un costo $46.
Realizar la tarea D en la máquina 2 con un costo $38.
COSTO TOTAL MÍNIMO= $219
4. PROBLEMA DE ASIGNACIÓN
El Problema de la Asignación es un problema clásico de la Investigación de
Operaciones y es un caso particular del Problema del Transporte.
Este problema se trata de asignar una serie de Recursos a una serie de tareas.
Tiene una limitante y es que a cada tarea se le puede asignar sólo un recurso, pueden
sobrar recursos o podrían sobrar tareas pero no se le puede asignar dos recursos a
una misma tarea, o tres... por ejemplo si se tienen tres operarios con diferentes
tiempos de operación en cuatro máquinas el modelo nos diría como asignar los tres
operarios a tres máquinas (nos sobraría una) de manera que se minimice el tiempo
total, pero no nos diría como asignar dos operarios a dos máquinas y el otro operario
a las otras dos máquinas.
Ejemplos de Asignaciones: Operarios a Tareas, Máquinas a Operarios,
Nadadores a Estilos, Novias a días de la semana, etc, etc, etc.
El Problema de la Asignación se basa en una información comparativa para
tomar la decisión de que asignar a que, por ejemplo una matriz de costos, una matriz
de tiempos, de ingresos, etc. Cuando la matriz no está balanceada, es decir, cuando
no es cuadrada, cuando sobran filas o columnas, se debe balancear para que tenga
solución mediante la inclusión de filas o columnas ficticias, con valores de cero en
dicha matriz.
Supongamos el siguiente ejemplo:
Existen cuatro operarios que se pueden asignar al trabajo con tres máquinas. Un
estudio de tiempos y movimientos ha arrojado los siguientes tiempos por operario
para las tres máquinas. Indicar que operario debe trabajar en que máquina y cuál de
ellos no será asignado a ninguna.
Máquina 1 Máquina 2 Máquina 3
Operario 1 10 7 9
Operario 2 7 5 8
Operario 3 9 8 10
Operario 4 8 9 7
Como la matriz no esta balanceada, es necesario incluir una máquina ficticia:
(esto es fundamental para asegurar que haya una respuesta. Si la matriz no está
balanceada, el problema no será factible de resolver)
Máquina 1 Máquina 2 Máquina 3 Máquina Ficticia
Operario 1 10 7 9 0
Operario 2 7 5 8 0
Operario 3 9 8 10 0
Operario 4 8 9 7 0
Xij = Se debe asignar el operario i a la máquina j? Sí o no?
En matemáticas existen dos números cuyas propiedades hacen que puedan
representar estas respuestas son el 1 y el 0, debido a que todo número multiplicado
por 1 da el mismo número entonces el 1 se puede reemplazar por la respuesta Sí y
como todo número multiplicado por cero da cero entonces se puede reemplazar por
la respuesta No.
Así por ejemplo:
10X11 + 7X12 + 9X13 + 0X14
representa el tiempo sumado que emplearía el operario1 en operar las máquinas,
pero solo una variable de las tres anteriores puede tomar el valor de Sí, o sea de 1
las demás tendrán que tomar el valor de 0, y eso es debido a que el operario 1 sólo
puede ser asignado a una máquina, lo que significaría que el tiempo que utilice el
operario 1 puede ser ya sea de "10" de "7" o de "9". Con base en esto podemos
formular la función objetivo:
Min Z = 10X11 + 7X12 + 9X13
7X21 + 5X22 + 8X23
9X31 + 8X32 + 10X33
8X41 + 9X42 + 7X43
Restricciones:
Como cada operario sólo puede estar asignado a una máquina....
X11 + X12 + X13 + X14 = 1
X21 + X22 + X23 + X24 = 1
X31 + X32 + X33 + X34 = 1
X41 + X42 + X43 + X44 = 1
Y como cada máquina solo puede tener un operario asignado...
X11 + X21 + X31 + X41 = 1
X12 + X22 + X32 + X42 = 1
X13 + X23 + X33 + X43 = 1
X14 + X24 + X34 + X44 = 1
Xij = 1 o 0 para toda i,j.
Al resolver utilizando Software, por ejemplo el Solver del Excel, la respuesta que
se obtiene es la siguiente:
Máquina 1 Máquina 2 Máquina 3Máquina
Fic.
Operario 1 0 0 0 1
Operario 2 0 1 0 0
Operario 3 1 0 0 0
Operario 4 0 0 1 0
Esto significa que el Operario 1 queda asignado a la Máquina Ficticia (es decir,
es el que sobra), el operario 2 se asigna a la máquina 2, el operario 3 se asigna a la
máquina 1 y el operario 4 se asigna a la máquina 3.
5. PROBLEMA DE CARGA DE BULTOS
El modelo de Carga de bultos aborda el problema de cargar artículos en un barco,
contenedores, bolsa, mochila, financieras, etc, en las cuales se utilice la opción de
privilegio entre varias alternativas.
Cada artículo produce un nivel de utilidad. El objetivo es cargar el barco con la
carga más valiosos. Observamos también que el problema de carga de bultos
también se conoce como el problema del equipaje de emergencia, en el cual se debe
determinar los artículos más valiosos que se debe llevar a bordo o dentro.
6. PROBLEMAS DE RUTA CORTA
1.- Un Ingeniero Forestal, requiere saber: i)Cuál es el costo mínimo, y ii)Cuál es la ruta con ese
costo mínimo, para ir desde su oficina hasta el lugar donde está la cosecha. En su camino
debe pasar por 3 sectores o ciudades antes de llegar a su destino, y lugares posibles en esos
sectores o ciudades. Las posibles rutas, y el costo asociado por Kms. de distancia y otros en
$, se ven en el siguiente esquema:
Solución:
Para ir de 1 a 13 hay 48 rutas posibles. Una posibilidad para encontrar la solución es
calcular el valor asociado a cada una y ver cuál es la que proporciona el menor costo. ¿Y si
fuesen miles de rutas?. Por se descarta esa alternativa y se usa el método de la programación
Dinámica, donde se resuelve desde el final hacia el inicio, y hay etapas y estados.
Etapas: Son 4. La etapa 1 es decidir ir del estado inicial 1 al estado 2,3,4 o 5 que son los
puntos posibles en el sector siguiente. La etapa 2 es decidir ir a 6, 7 u 8. La etapa 3 es
decidir ir a 9, 10, 11 o 12. La etapa 4 es decidir a 13.
Estado: Lugar donde se encuentra. La etapa 1 tiene 1 estado: el 1. La etapa 2 tiene 4 estados:
2, 3, 4, 5. La etapa 3 tiene 3 estados: 6,7,8. La etapa 4 tiene 4 estados: 9, 10, 11, 12.
Cálculos n = 4 S \ X4 13 F4* X4*
9 12 12 13
10 16 16 13
11 15 15 13
12 14 14 13
n = 3 S \ X3 9 10 11 12 F3* X3*
6 3+12=15 2+16=18 1+15=16 3+14=17 15 9
7 4+12=16 1+16=17 4+15=19 6+14=20 16 9
8 2+12=14 3+16=19 6+15=21 5+14=19 14 9
n=2 S \ X2 6 7 8 F2* X2*
2 9+15=24 4+16=20 6+14=20 20 7 - 8
3 5+15=20 7+16=23 4+14=18 18 8
4 9+15=24 10+16=26 8+14=22 22 8
5 9+15=24 10+16=26 11+14=25 24 6
n = 1 S \ X1 2 3 4 5 F1* X1*
1 7+20=27 6+18=24 5+22=27 6+24=30 24 3
Respuesta: El óptimo es: 24
La solución óptima es: X1 = 3 ; X2 = 8 ; X3= 9 ; X4= 13.
La ruta óptima es: 1 3 8 9 13
Respuesta al problema planteado:
El Ingeniero Forestal tiene un costo mínimo de $24 para ir desde su oficina al lugar de
cosecha, y ese mínimo lo puede lograr yendo desde su oficina al lugar 3 luego al lugar 8
luego al lugar 9 y de ahí al lugar 13, que es donde está la cosecha.
2.-Un Técnico Forestal, debe revisar 3 faenas: Poda, Raleo y Cosecha, y dispone de 4 días.
Según la dedicación en días que le de a cada faena, éstas tendrán una probabilidad de
fracasar, y con ello fracasar la faena total, por lo que puede ser despedido. Por ello,
dicho Técnico desea minimizar la probabilidad de ser despedido minimizando la
probabilidad de que las 3 tareas fracasen al mismo tiempo.
Dedicación \ Faenas Poda Raleo Cosecha
0 día 0.50 0.60 0.40
1 día 0.42 0.51 0.35
2 días 0.36 0.41 0.21
3 días 0.25 0.36 0.18
Un día no asignado a una faena no tiene valor asociado. A lo más se puede asignar 3
días a una misma faena.
Solución:
Etapas: Son 3. La etapa 1 es el proceso de asignación de días a Poda. La etapa 2 es el
proceso de asignación de días a Raleo. La etapa 3 es el proceso de asignación de días a
Cosecha.
Estados: Son los días disponibles para ser asignados, y van de 0 a 4, dependiendo de las
etapas. La etapa 1 tiene 1 estado factible y es: tener 4 días disponibles para ser asignados.
Las variables de decisión son 3: X1, X2, X3 y representan: Cuántos días asignar a la faena
poda, Cuántos días asignar a la faena de raleo, Cuántos días asignar a la faena de cosecha;
respectivamente.
La Función Objetivo y las restricciones forman en el modelo para este problema y es: P:
Min( p(X1)*p(X2)*p(X3) ) ; s.a: X1+X2+X3 4 ; Xi 0,1,2,3; i=1,2,3
La probabilidad de ser despedido en este momento es: 0.5*0.6*0.4 =0.12, que es de un
12%, y con los 4 días disponibles desea minimizar esa probabilidad.
Los cálculos.
n = 3 S \ X3 0 1 2 3 F3* X3*
0 0.4*1=0.40 - - - 0.40 0
1 0.4*1=0.40 0.35*1=0.35 - - 0.35 1
2 0.4*1=0.40 0.35*1=0.35 0.21 - 0.21 2
3 0.4*1=0.40 0.35*1=0.35 0.21 0.18 0.18 3
4 0.4*1=0.40 0.35*1=0.35 0.21 0.18 0.18 3
n = 2
S\X2 0 1 2 3 F2* X
2*
1 0.6*0.35=0.210 0.51*0.40=0.2040 - - 0.2040 1
2 0.6*0.21=0.126 0.51*0.35=0.1785 0.41*0.40=0.1640 - 0.1260 0
3 0.6*0.18=0.108 0.51*0.21=0.1071 0.41*0.35=0.1435 0.36*0.40=0.144 0.1071 1
4 0.6*0.18=0.108 0.51*0.18=0.0918 0.41*0.21=0.0861 0.36*0.35=0.1260 0.0861 2
n = 1
S\X1 0 1 2 3 F1* X1*
4 0.5*0.0861
= 0,04305
0.42*0.1071
= 0,044982
0.36*0.1260
= 0,04536
0.25*0.2040
= 0,051
0.04305 0
Respuesta: óptimo = 0.04305 ( un 4,3% ).
La solución óptima es: X1 = 0 ; X2 = 2 ; X3= 2
La ruta óptima es: 4 4 2 2
Respuesta al problema planteado: La probabilidad mínima de ser despedido es 0.04305 , es
decir de un 4,3%, y la asignación óptima de días es: 0 días a la Poda, 2 días al
Raleo, 2 Días a la Cosecha.
3.- Un aserradero debe enviar 4 o 5 cargamentos a cuatro destinos. La máxima asignación
para cada destino es de cuatro cargamentos. En la tabla siguiente se indica g(xi) como
los ingresos en MM$ obtenidos por cada una de las decisiones posibles. Se desea
maximizar el ingreso del aserradero por estos envíos.
Además al destino 2 no se puede asignar 4 sino que máximo 3 cargamentos. Al destino
3 ya se ha decidido asignar exactamente 1 cargamento. Un cargamento no asignado no
tiene valor asignado.
cargamentos \ destinos 1 2 3 4
0 0 0 0 0
1 5 6 4 7
2 11 10 12 10
3 15 16 17 14
4 21 - 22 23
Solución:
Etapas: son 4 etapas. La etapa 1,2,3,4 es el proceso de decisión de envíos de cargamento al
destino 1, destino 2, destino 3 y destino 4 respectivamente.
Estados: La cantidad de cargamentos disponibles para ser enviados en cada etapa.
El modelo en este caso es: (Son 2 problemas en uno).
P: Máx ( g(xi); i=1,2,3,4) s.a: X1+X2+X3 +X4 5 ; Xi 0,1,2,3,4; i=1,2,3,4.
P: Máx ( g(xi); i=1,2,3,4) s.a: X1+X2+X3 +X4 4 ; Xi 0,1,2,3,4; i=1,2,3,4.
Los Cálculos.
n = 4 S \X3 0 1 2 3 4 F4* X4*
0 0 - - - - 0 0
1 0 7+0=7 - - - 7 1
2 0 7+0=7 10 - - 10 2
3 0 7+0=7 10 14 - 14 3
4 0 7+0=7 10 14 23 23 4
n =3 S \ X3 1 F3* X3*
1 4+ 0 = 4 4 1
2 4+ 7 =11 11 1
3 4+10=14 14 1
4 4+14=18 18 1
5 4+23=27 27 1
n = 2 S\X2 0 1 2 3 F2* X2*
1 0 + 4 = 4 - - - 4 0
2 0+11=11 6+4=10 - - 11 0
3 0+14=14 6+11=17 10+4=14 - 14 1
4 0+18=18 6+14=20 10+11=21 16+ 4=20 21 2
5 0+27=27 6+18=24 10+14=24 16+11=27 27 0 - 3
n = 1 S \ X1 0 1 2 3 4 F1* X
1*
4 0+21=21 5+14=19 11+11=22 15+4=19 --- 22 2
5 0+27=27 5+21=26 11+17=28 15+11=26 21+4=25 28 2
Respuesta:
A) Si envía 4 cargamentos, el óptimo es: MM$ 22, y la solución óptima es: X1 = 3 ; X2 =
0 ; X3= 1; X4= 0;
X1 = 2 X2 = 0 X3= 1 X4= 1
La ruta óptima es: 4 2 2 1 0
11 0 4 7
Es decir: Al destino-1 debe enviar 2 cargamentos, al destino-2 debe enviar 0
cargamento, al destino-3 enviar 1 cargamento, y al destino-4 enviar 1 cargamento. Con
esto obtiene el máx que es de MM$22.
B) Si envía 5 cargamentos, el óptimo es: MM$ 28, y la solución óptima es: X1 = 2 ; X2
= 1 ; X3= 1; X4= 1;
X1 = 2 X2 =1 X3= 1 X4= 1
La ruta óptima es: 5 3 2 1 0
11 6 4 7
Es decir: Al destino-1 debe enviar 2 cargamentos, al destino-2 debe enviar 1
cargamento, al destino-3 enviar 1 cargamento, y al destino-4 enviar 1 cargamento. Con
esto obtiene el máx que es de MM$22.
4.- Un dueño de tres supermercados tiene 5 cargas de fresas frescas. Su problema es destinar
las fresas a cada supermercado, ya que en cada uno las fresas tienen distinto valor. El
ingreso en los supermercados, según la asignación de cargas se indica a continuación en
MM$.
Cargamentos \ destino Supermercado 1 Supermercado 2 Supermercado 3
0 0 0 0
1 5 6 4
2 9 11 9
3 14 15 13
4 17 19 18
5 21 22 20
El no asignar las cargas de fresas a un supermercado tiene valor asociado de cero pesos al
horizonte, porque se perderán.
¿Cuál es el máximo ingreso posible, y cuál es la asignación que para ello?.
Solución:
n = 3 S \ X3 0 1 2 3 4 5 F3* X3*
0 0 - - - - - 0 0
1 0 4+0 - - - - 4 1
2 0 4+0 9+0 - - - 9 2
3 0 4+0 9+0 13+0 - - 13 3
4 0 4+0 9+0 13+0 18+0 - 18 4
5 0 4+0 9+0 13+0 18+0 20+0 20 5
n = 2
S \ X2 0 1 2 3 4 5 F2* X2*
0 0+0=0 - - - - - 0 0
1 0+4=4 6+0=6 - - - - 6 1
2 0+9=9 6+4=10 11 - - - 11 2
3 0+13=13 6+9=15 11+4=15 15 - - 15 1-2-3
4 0+18=18 6+13=19 11+9=20 15+4=19 19 - 20 2
5 0+20=20 6+18=24 11+13=24 15+9=24 19+4=23 22 24 1-2-3
n = 1
S\ X1 0 1 2 3 4 5 F1* X1*
5 0+24=24 5+20=25 9+15=24 14+11=25 17+6=23 21+0=21 25 1-3
Respuesta: El máximo ingreso posible es MM$ 25, y se puede alcanzar con la asignación :
X1 = 1 ; X2 = 2 ; X3= 2 ( Con ingresos: 5+11+9= 25). O bien con la
asignación: X1 = 3 ; X2 = 2 ; X3= 0 ( Con ingresos: 14+11+0 = 25 ).
5.- Se dispone de 6 brigadas para asignar a tres sectores. El aumento de la productividad en
los sectores depende de la asignación, y es la que se indica en el cuadro siguiente:
Núm.brigadas asign. \ sector Sector-1 Sector-2 Sector-3
0 0 0 0
1 12 14 13
2 25 19 21
3 30 37 32
4 40 49 48
¿Cuántas brigadas asignar a cada sector para hacer máxima la suma de aumento de la
productividad?.
Una brigada no asignada no tiene valor asociado en la productividad. Esto equivale a
decir que el valor al horizonte de una brigada no asignada es de cero, ya que ese valor
no influye sobre el valor de la función objetivo.
Solución:
Las etapas: Son tres etapas
Los Estados: Son el número de brigadas disponibles al inicio de la etapa.
Estado inicial: Es uno sólo, y es tener 6 brigadas disponibles.
Variables de decisión: Son 3, indicadas por: X1 , X2 , X3 y el valor de ellas es un
elemento del conjunto: 0,1,2,3, 4
El modelo: P: Máx ( f (Xi ); i=1,2,3) s.a: X1+X2+X3 6 ; Xi 0,1,2,3,4; i=1,2,3.
Los cálculos: n = 3 S \ X3 F3* X3*
6 48 4
5 48 4
4 48 4
3 32 3
2 21 2
1 13 1
0 0 0
n=2 S \ X2 4 3 2 1 0 F2* X2*
6 49+21=70 37+32=69 19+48=67 14+48=62 0+48 70 4
5 49+13=62 37+21=58 19+32=51 14+48=62 0+48 62 1-4
4 49+ 0=49 37+13=50 19+21=40 14+32=46 0+48 50 3
3 - 37+0=37 19+13=32 14+21=35 0+32 37 3
2 - - 19+ 0=19 14+13=27 0+21 27 1
n=1 S \ X1 4 3 2 1 0 F1* X
1*
6 40+27=67 30+37=67 25+50=75 12+62=74 0+70=70 75 2
Respuesta: Optimo =75; Solución óptima: X1*=2; X2*=3; X3*=1
Respuesta: La mayor productividad posible es de 75 y se logra asignando 2 brigadas al
sector 1, 3 brigadas al sector 2 y 1 brigada al sector 3.
Ruta óptima:
X1 = 2 X2 = 3 X3= 1
La ruta óptima es: 6 4 1 0
25 37 13
6 4 1 2