Investigación De Operaciones

Contenido

Parte I

• Transporte. (Rosangélica)

El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos de modelos son:

Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.

El costo de transporte unitario de la mercancía a cada destino.

Como solo hay una mercancía, un destino puede recibir su demanda de una o más fuentes. El objetivo de este modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino tal que se minimice el costo del transporte total.

La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional el número de unidades transportadas. La definición de “unidades de transporte” varía dependiendo de la “mercancía” que se transporte.

• Problema de transporte. (Rosangélica)

• Es un caso especial del problema de transbordo, en el que todos los nodos son o fuentes (nodos de oferta) o destinos (nodos de demanda). En un problema de transporte no existen nodos de transbordo.

• Ejemplo. La Boor´s Brewery Company elabora una cerveza que se distribuye a nivel nacional a partir de dos fabricas de cerveza, Una en cada una de las costas de E.U.. La cerveza se envía a cuatro mayoristas que se encargan de la distribución subsecuente, por lo que la Boor´s se ocupa sólo de la distribución a los mayoristas. Los costos de distribución, por conjunto de 100 cajas que se envían a cada mayorista, se presentan en la tabla 2.3 , junto con la oferta mensual en cada fabrica y la demanda mensual de cada mayorista. Plantear el problema en forma de Red y de Programación Lineal.

Fábrica de cerveza Albany

N.Y. Ames,

Iowa Luckenbach,

Tx Needles,

Calif. Oferta (en cientos de cajas)

Silver, Wa

Apple Chill, N.C. $21

$10 $15

$14 $18

$16 $9

$23 550

650

Demanda (cientos de cajas) 200 250 400 350

Tres empresas suministran ordenadores a cuan detallistas, la cantidad de demanda semanal de los 4 detallistas es de 150, 150, 400 y 100 ordenadores respectivamente. La oferta de las empresas está dictada por la mano de obra regular disponible y se calcula en 250 unidades a la semana. El costo en euros del transporte por unidad viene detallado en la siguiente tabla:

Tabla de costos:

Detallistas

Proveedores

1

2

3

4

1 10 20 10 20

2 20 40 10 20

3 10 10 50 30

Variables de decisión:

Xij i = número de empresas

j= número de detallistas

Cij:Costos del

transporte i= 1-3

j= 1-4

Forma estándar de programación lineal:

Función objetivo:

Min: Z= ∑Xij.Cij

Reemplazando el valor de Cij con los valores de la tabla de costo:

Min: Z= 10X11+ 20X12+ 30X13+ 20X14 + 20X21 +

40X22 + 10X23 + 20X24 + 10X31 + 30X32 + 50X33 + 30X34

Restricciones:

-Oferta:

X11 + X12 + X13 + X14<=250

X21 + X22+ X23 + X24<= 300

X31 + X32 + X33 + X34<= 250

-Demanda:

X11 + X21 + X31= 150

X21 + X22+ X32= 150

X13 + X23 + X33= 400

X14 + X24 + X34= 100

Xij=>0

• Matriz de incidencia. (Manuel).

Matriz de incidencia

De Wikipedia, la enciclopedia libre

Saltar a: navegación, búsqueda

La matriz de incidencia es una matriz binaria (sus elementos sólo pueden ser unos o ceros), que se utiliza como una forma de representar relaciones binarias.

[editar] Construcción de la matriz a partir de un grafo

Relación binaria descrita mediante una matriz de incidencia, y mediante un grafo.

1. Las columnas de la matriz representan las aristas del grafo.

2. Las filas representan a los distintos nodos.

3. Por cada nodo unido por una arista, ponemos un uno (1) en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros (0).

En el ejemplo de la figura, si sumamos las cantidades de 1's que hay en cada columna, veremos que hay solo dos. Pero si sumamos las cantidades de unos 1's que hay por cada fila, comprobaremos que los nodos 2, 4 y 5 poseen un valor de 3. Ese valor indica la cantidad de aristas que inciden sobre el nodo

• Nodos, arcos y tablas de transporte. (Manuel)

• Técnicas de resolución. (Eduar)

Parte II

• Problemas de la ruta más económica y flujo máximo de redes. (Osmar).

 Problema de flujo máximo de redes. Este problema también está definido en redes de flujo, a diferencia del problema anterior, no se toman en cuenta los costos del flujo en cada uno de los arcos de la red. En este problema se quiere, dado que se tiene especificada la capacidad de cada arco, encontrar el flujo máximo que podría circular entre un nodo origen y un nodo destino. Este flujo máximo debería adicionalmente cumplir con restricciones de balance de flujo y de no-negatividad. Para este problema también se cuenta con algoritmos eficientes para resolverlos.

 • PROBLEMA DE LA RUTA MAS CORTA

 Trata el problema de encontrar el camino más corto (el camino de longitud mínima) desde el nodo 1 hacia cualquier otro nodo en la red.

 EJEMPLO. Acabo de comprar (en el tiempo 0) un automóvil nuevo en 12,000 dólares. El costo del mantenimiento anual de un automóvil depende de la edad del automóvil al inicio del año, como se da en la tabla 2.4. Para evitar los altos costos de mantenimiento de un automóvil más viejo, puedo dar como adelanto mi automóvil y comprarme un automóvil nuevo. El precio que recibo al dar como adelanto automóvil depende de su edad al momento de la transacción (tabla 2.5). Para simplificar los cálculos, suponemos que en cualquier momento, me cuesta 12,000 dólares comprar un automóvil nuevo. Mi meta es minimizar el costo neto (costos de compra + costos de mantenimiento - dinero recibido por el automóvil viejo) incurrido durante los próximos cinco años. Formula la red del modelo

Edad del automóvil (Años) Costo anual de mantenimiento (Dólares)

0 2000

1 4000

2 5000

3 9000

4 12000

 Tabla 2.4 Costos de mantenimiento del automóvil

Edad del automóvil (años) Costo al dar precio (dólares)

1 7000

2 6000

3 2000

4 1000

5 0

 Tabla 2.5 Precios del automóvil al darlo como adelanto



• Algoritmos para resolver los problemas de la ruta más económica y el flujo máx. de redes. (Erninyer)

Parte III

• Algoritmo húngaro para problemas de asignación. (Kenia)

• El problema del asignacion es encontrar un matching de peso máximo en un grafo bipartido ponderado. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática.

• Una descripción apropiada de lo que trata de lograr el modelo de asignación es:

• “La mejor persona para el trabajo”

• El problema de asignación tiene que ver con la designación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas, etc. En otras palabras, a la disposición de algunos recursos(maquinas o personas) para la realización de ciertos productos a 'costo mínimo.

• Una definición más formal pudiera ser:

• Problema de Asignación: Caso particular del problema de Transporte donde los asignados son recursos destinados a la realización de tareas, los asignados pueden ser personas, máquinas, vehículos, plantas o períodos de tiempo. En estos problemas la oferta en cada origen es de valor 1 y la demanda en cada destino es también de valor 1.

• Pasos para el método húngaro

• 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 costo el 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: 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 (En algunos textos este paso se atribuye a Flood).

• 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. (scrib2)

• Paso 4: En caso de

...