EJEMPLO DE PROGRAMACION NO LINEAL

 

Ejercicios de la ruta mas corta

2do ejercicio

La ruta más corta

ALGORITMO DE LA RUTA MÁS CORTA

---

Ya el nombre de este tipo de algoritmo es bastante sugestivo. El algoritmo de la ruta más corta  consiste, si es necesario decirlo, en una modalidad de problemas de redes, en la cual se debe determinar el plan de rutas que genere la trayectoria con la mínima distancia total, que una un nodo fuente con un nodo destino, sin importar el número de nodos que existan entre estos.

Esta modalidad de problemas puede solucionarse como un modelo de transbordo normal, sin embargo la principal sugerencia es la de establecer una oferta en el nodo fuente igual a una unidad (1) y establecer una demanda en el arco destino igual a una unidad (1).

Vale la pena considerar, que en la práctica, es muy frecuente la utilización del algoritmo resultante con variaciones que consisten en la minimización de tiempos, no necesariamente de distancias.

---

Algoritmo de la Ruta más corta - Ejemplo

Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra ubicada en el nodo 1, se conoce de antemano que el minero permanece atrapado en el nodo 9, para llegar a dicho nodo hay que atravesar una red de túneles que van conectados entre sí. El tiempo de vida que le queda al minero sin recibir auxilio es cada vez menor y se hace indispensable hallar la ruta de acceso al nodo 9 más corta. Las distancias entre nodos de la mina se encuentran en la siguiente gráfica dadas en cientos de metros. Formule un modelo de transbordo y resuelva mediante cualquier paquete de herramientas de investigación operativa que permita establecer la ruta más corta para poder así auxiliar al minero.

www.ingenieriaindustrialonline.com

VARIABLES DE DECISIÓN

El nombre de las variables en este caso poco importa, dado que de ser escogida para la solución básica eso significa simplemente que será empleada como ruta para ir a rescatar al minero, sin embargo nada tiene de malo el que se le pueda asociar con el envío de unidades desde la entrada de la mina hacia el minero, por ende puede sugerirse este como nombre de las variables. "Cantidad de unidades enviadas desde el nodo i hacia el nodo j".

X₁₂ = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2
X₁₃ = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3
X₂₃ = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3
X₂₄ = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4
X₃₂ = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2
X₃₄ = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 4
X₃₅ = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 5
X₄₆ = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 6
X₄₇ = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 7
X₅₄ = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 4
X₅₆ = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 6
X₅₇ = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 7
X₅₈ = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 8
X₆₇ = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 7
X₆₉ = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 9
X₇₆ = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 6
X₇₈ = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 8
X₇₉ = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 9
X₈₇ = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 7
X₈₉ = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 9

---

---

RESTRICCIONES

Restricciones de Oferta y Demanda

Hay que recordar que el objetivo de este modelo es la consecución de un plan de ruta que nos permita encontrar al minero lo más pronto posible al recorrer la distancia mínima posible, por ende la clave para plantear el modelo como si fuese de transbordo es establecer una demanda y oferta igual a la unidad (1).

X₁₂ + X₁₃ = 1
X₆₉ + X₇₉ + X₈₉ = 1

Restricciones de Balance

X₁₂ + X₃₂ - X₂₃ - X₂₄ = 0
X₁₃ + X₂₃ - X₃₂ - X₃₄ - X₃₅ = 0
X₂₄ + X₃₄ + X₅₄ - X₄₆ - X₄₇ = 0
X₃₅ - X₅₄ - X₅₆ – X₅₇ – X₅₈ = 0
X₄₆ + X₅₆ + X₅₇ - X₆₇ – X₆₉ = 0
X₆₇ + X₄₇ + X₅₇ + X₈₇ – X₇₆ – X₇₈ – X₇₉ = 0
X₇₈ + X₅₈ – X₈₉ = 0

En palabras sencillas: "Todo lo que entra a cada nodo es igual a lo que sale de él"

FUNCIÓN OBJETIVO

Z_MIN = 4X₁₂ + 2X₁₃ + 2X₂₃ + 7X₂₄ + 4X₃₂ + 9X₃₄ + 6X₃₅ + 1X₄₆ + 5X₄₇ + 2X₅₄ + 4X₅₆ + 3X₅₇+ 2X₅₈ + 1X₆₇ + 5X₆₉ + 4X₇₆ + 3X₇₈ + 5X₇₉ + 2X₈₇ + 7X₈₉

INGRESANDO LOS DATOS A WINQSB

www.ingenieriaindustrialonline.com

SOLUCIÓN OBTENIDA MEDIANTE WINQSB

www.ingenieriaindustrialonline.com

La ruta más corta para rescatar al minero  tiene como distancia total 1600 metros (dado que las distancias estaban dadas en cientos de metros) y es tal como se muestra en la siguiente gráfica.

www.ingenieriaindustrialonline.com

Sin embargo, WinQSB cuenta con una metodología mucho más sencilla de resolución de algoritmos de ruta más corta, metodología que explicaremos más adelante, de todas formas hemos encontrado cómo, aplicando debidamente la razón y un algoritmo conocido como el de transbordo, podemos solucionar problemas distintos en teoría.

ejemplos de asignacion con software

ccccd                                                        ejemplo 1




                                                      ejemplo 2

                                                      ejemplo 3

Ejemplos de asignación

Problema de asignación

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 res

puesta. 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 = 1X21 + X22 + X23 + X24 = 1X31 + X32 + X33 + X34 = 1X41 + X42 + X43 + X44 = 1

Y como cada máquina solo puede tener un operario asignado...

X11 + X21  + X31 + X41 = 1X12 + X22  + X32 + X42 = 1X13 + X23  + X33 + X43 = 1X14 + 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 3	Má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.

Teorema fundamental de la asignación:

Si a todos los elementos de una fila o de una columna de una matriz de rendimientos se le suma o se le resta una cantidad constante la asignación optima no varía.

Algoritmo húngaro:

El algoritmo Húngaro está destinado para minimizar si tenemos que maximizar tendremos previamente que darle la vuelta a la matriz restándole el mayor elemento de toda la matriz a cada uno de los elementos de la misma de manera que el elemento que era más pequeño pasara a ser el más grande y a la inversa.

El Algoritmo Húngaro se debe a D. König y E. E Egervóry.

Cuando hay que pasar de maximizar a minimizar en lugar de operar con el mayor de toda la matriz podemos ir tomando el mayor de cada fila o columna e ir restándole todos los elementos de esa fila o columna con lo cual conseguiremos de camino obtener por lo menos un cero como mínimo en cada fila o columna. Si en alguna columna no hubiera ceros le quitamos el mayor a la columna.

El método Húngaro:

Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación. Las fases para la aplicación del método Húngaro son:

Paso 1: Encontrar primero el elemento más pequeño en cada fila de la matriz de costos m*m; se debe construir una nueva matriz al restar de cada costoel costo mínimo de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. A continuación se debe construir una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna.

Paso 2: (En algunos pocos textos este paso se atribuye a Flood). Consiste en trazar el número mínimo de líneas (horizontales o verticales o ambas únicamente de esas maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima entre los ceros cubiertos de la matriz. Si se requieren menos de m líneas para cubrir todos los ceros, se debe continuar con el paso 3. El número de líneas para cubrir los ceros es igual a la cantidad de asignaciones que hasta ese momento se pueden realizar.

Paso 3: Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no está cubierto por las líneas dibujadas en el paso 2; a continuación se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por dos líneas (intersecciones). Por último se debe regresar al paso 2.

Notas:

1. Para resolver un problema de asignación en el cual la meta es maximizar la función objetivo, se debe multiplicar la matriz de ganancias por menos uno (-1) y resolver el problema como uno de minimización.

2. Si el número de filas y de columnas en la matriz de costos son diferentes, el problema de asignación está desbalanceado. El método Húngaro puede proporcionar una solución incorrecta si el problema no está balanceado; debido a lo anterior, se debe balancear primero cualquier problema de asignación (añadiendo filas o columnas ficticias) antes de resolverlo mediante el método Húngaro.

3. En un problema grande, puede resultar difícil obtener el mínimo número de filas necesarias para cubrir todos los ceros en la matriz de costos actual. Se puede demostrar que si se necesitan j líneas para cubrir todos los ceros, entonces se pueden asignar solamente j trabajos a un costo cero en la matriz actual; esto explica porqué termina cuando se necesitan m líneas.

Mediante el siguiente ejemplo vamos a ilustrar la manera de aplicar el método Húngaro a la solución de un problema de asignación de minimización:

Una factoría tiene cuatro operarios, los cuales deben ser asignados al manejo de cuatro máquinas; las horas requeridas para cada trabajador en cada máquina se dan en la tabla adjunta; el tiempo a laborar por cada operario en cada una de las máquinas se pretende que sea mínimo, para lo cual se busca la asignación óptima posible.

OPERARIOS					MAQUINAS
					1	2	3	4
Antonio					10	14	16	13
Bernardo					12	13	15	12
Carlos					9	12	12	11
Diego	14	13	18	16

Planteamiento del Modelo Primal

MIN W = 10 X11+ 14 X12+ 16 X13+ 13 X14+ 12 X21+ 13 X22+ 15 X23+ 12 X24+ + 9 X31+ 12 X32+ 12 X33+ 11 X34+ 14 X41+ 16 X42+ 18 X43+ 16 X44

sujeto a las siguientes restricciones:

Aplicando el método Húngaro tenemos:

	1	2	3	4
A	10	14	16	13
B	12	13	15	12
C	9	12	12	11
D	14	16	18	16
Restamos 10, 12, 9 y 14 (costos mínimos de cada fila) de cada elemento en cada una de las filas correspondientes:
	1	2	3	4
A	0	3	6	3
B	0	1	3	0
C	0	3	3	2
D	0	2	4	2
En la matriz anterior trazamos el menor número de líneas (3), de manera tal que cubran todos los ceros (Método de Flood):
	1	2	3	4
A	0	3	3	3
B	0	0	0	0
C	0	2	0	2
D	0	1	1	2
En la matriz anterior trazamos el menor número de líneas (3), de manera tal que cubran todos los ceros (Método de Flood):
	1	2	3	4
A	0	2	3	2
B	1	0	1	0
C	0	1	0	1
D	0	0	1	1

Solución Optima Unica:A-1, B-4, C-3 y D-2.Lo anterior quiere decir que Antonio va a laborar en la máquina 1 (10 horas), Bernardo en la máquina 4 (12 horas), Carlos va a trabajar en la máquina 3 (12 horas) y Diego en la máquina 2 (16 horas).

La combinación óptima de los recursos para este problema de minimización de asignación es de 50 horas, resultantes de adicionar las asignadas a cada uno de los operarios en cada una de las máquinas. Dicho valor corresponde al valor óptimo de la función objetivo.

Método de Voguel

Método de Voguel

El método de Vogel, o aproximación de Vogel, es un método que permite llegar a una solución inicial factible del problema de transporte.

El procedimiento de este método es el siguiente:

1. Tener los valores de costos de envíos desde cada origen a cada destino tabulados (matriz de costos). En caso de que la matriz no este equilibrada (el numero de filas es diferentes del numero de columnas), agregar una fila o columna de ceros según corresponda. Esto quiere decir que según sea el caso se creara un origen o un destino ficticio.
2. Realizar el cálculo de las penalizaciones para cada fila y columna. Las penalizaciones se calculan restando los dos valores más pequeños de cada fila y cada columna. Las penalizaciones tienen valor absoluto.
3. Identificar la fila o columna con la mayor penalización (en caso de que exista un empate en las penalizaciones, se puede elegir cualquiera de las que tiene el mayor valor), y asignar la mayor cantidad de material posible a la casilla con el menor costo en esa fila o columna.
4. Se sombrean (eliminan) las filas o columnas que hayan sido satisfechas, reduciendo así la matriz.
5. Se repite el procedimiento desde en paso 2.
6. Una vez satisfechos todos los orígenes y destinos (sombreadas todas las filas y columnas) se puede proceder a calcular el costo del programa de envió encontrado mediante este método (cabe resaltar que la solución factible encontrada con este método no es necesariamente la optima).