• Author / Uploaded
• yahaira adama galarza

Citation preview

UNIVERSIDAD NACIONAL TECNOLOGICA DE LIMA SUR

INGENIERIA DE SISTEMAS

Investigación Operativa II Sección IS05S2 – Jueves 11:20 → 13:50 (T) / 13:50 → 15:30 (P) Sección IS05S3 – Jueves 15:30 → 18:00 (T) / 18:00 → 19:40 (P)

Docente: Dr. Joe Alexis González Vásquez [email protected]

Recomendaciones de clase Por conectividad ingresar con audífonos y cámaras apagadas, activarlas cuando el docente lo indique. Durante la videoconferencia no interrumpir, cualquier duda o pregunta, solicitar el uso de la palabra por el chat o icono respectivo. Sin embargo al final de la explicación se realizará una retroalimentación para absolver las preguntas. La asistencia se llevará a cabo en cualquier momento del desarrollo de la clase. Respetar las fechas programadas para prácticas, laboratorios, trabajos y exámenes.

Socialización de sílabo

SESION 01 PROGRAMACION LINEAL (PLE): Transporte, Asignación y Trasbordo

LOGRO DE LA SESION DE APRENDIZAJE 01 Programación Lineal (PL) Al finalizar la sesión, el estudiante formula y resuelve problemas de programación lineal especiales como: transporte, asignación y trasbordo, utilizando los algoritmos de solución que se ajusten a las características y particularidades de cada tipo.

INTRODUCCION 1. ¿Cómo se realiza la distribución de cualquier bien desde cualquier grupo de centros de suministro, llamados orígenes, a cualquier grupo de centros de recepción, llamados destinos, de tal manera que se minimicen los costos totales de distribución? 2. ¿Cómo se asignan empleados a quienes se tiene que dar trabajo? o ¿Cómo asignar maquinas, vehículos, plantas a los que se asignan tareas? 3. ¿Cómo enviar bienes entre puntos de oferta o entre puntos de demanda si entre ellos existen puntos intermedios que puede tanto recibir bienes de otros puntos como enviar bienes hacia otros puntos?

Los problemas de transporte, de asignación y de trasbordo son casos especiales de programación lineal. Es posible resolver todos estos problemas mediante el algoritmo simplex, pero, además hay algoritmos especializados para cada uno de los tipos de problemas que son más efectivos que el algoritmo simplex. El problema de transporte recibe este nombre debido a que muchas de sus aplicaciones involucran determinar la manera óptima de transportar bienes. Sin embargo, algunas de aplicaciones importantes (como la programación de la producción), de hecho no tienen nada que ver con el transporte. El problema de asignación, incluye aplicaciones tales como asignar personas a tareas. Aunque sus aplicaciones parecen diferir del problema de transporte, se vera que este problema es un acaso especial del problema de transporte. El problema de trasbordo es una variación del modelo original de transporte que se ajusta a la posibilidad común de transportar unidades mediante nodos fuentes, destinos y transitorios.

PROBLEMAS DE TRANSPORTE El problema de transporte frecuentemente se presenta al planear la distribución de bienes y servicios desde varias localizaciones de suministro (origen) hacia varias ubicaciones de la demanda (destino). La cantidad de los bienes disponibles en cada localización de suministro (origen) es limitada y la cantidad de los bienes necesarios en cada localización de demanda (destino) es conocida.

Por lo general, en un problema de transporte el objetivo es minimizar el costo de embarcar los bienes desde los orígenes hacia los destinos.

ORIGEN

DESTINO

El modelo general de programación lineal de un problema de transporte con “m” orígenes y “n” destinos es como sigue: 𝑚

𝑛

𝑀𝑖𝑛 ෍ ෍ 𝐶𝑖𝑗 𝑋𝑖𝑗 𝑖=1 𝑗=1

Sujeto a:

Donde:

𝑛

෍ 𝑋𝑖𝑗 ≤ 𝑆𝑢𝑚𝑖𝑛𝑖𝑠𝑡𝑟𝑜𝑖

i = 1, 2, … , m

𝑗=1 𝑚

෍ 𝑋𝑖𝑗 = 𝐷𝑒𝑚𝑎𝑛𝑑𝑎𝑗

j = 1, 2, … , n

𝑖=1

𝑋𝑖𝑗 ≥ 0

Para todas las i y j

i = índice de los orígenes, i = 1, 2, … , m j = índice de los destinos, j = 1, 2, … , n Xij = Número de unidades embarcadas desde el origen i hasta el destino j Cij = Costo unitario de embarcar del origen i al destino j

Ejemplo 01 (Métodos: Esquina Nor Oeste, Costo Mínimo, Aproximación de Vogel) Determine la solución óptima para el siguiente problema de transporte.

Fuentes

Destinos

Oferta

1

2

3

4

1

10

0

20

11

15

2

12

7

9

20

25

3

0

14

16

18

5

Demanda

5

15

15

10

Se requiere determinar cuantos artículos enviar de cada fuente a cada destino con el mínimo costo.

PROBLEMAS DE ASIGNACION Los problemas típicos de asignación implican asignar tareas a maquinarias, agentes a trabajos especiales, personal de ventas a territorios, contratos a licitantes, etc. Una característica que distingue a los problemas de asignación es que un agente se le asigna a una y solamente una tarea. Específicamente buscamos el conjunto de asignaciones que optimizarán un objetivo dado como minimizar el costo, minimizar el tiempo o maximizar la utilidad.

El problema de asignación es un caso especial de problema de transporte, en que todos los valores de oferta y demanda son iguales a 1, y la cantidad que se embarca en cada uno de los arcos es 0 o 1.

El problema general de asignación involucra a “m” agentes a “n” tareas. Si hacemos que Xij = 1 o 0 , dependiendo si el agente i es asignado o no a la tarea j, si Cij indica el costo de asignar el agente i a la tarea j, podemos escribir el modelo general de asignación de la forma: 𝑚

𝑛

𝑀𝑖𝑛 ෍ ෍ 𝐶𝑖𝑗 𝑋𝑖𝑗 𝑖=1 𝑗=1

Sujeto a: 𝑛

෍ 𝑋𝑖𝑗 = 1

Para i = 1, 2, … , n

Agentes

Para j = 1, 2, … , n

Agentes

𝑗=1 𝑛

෍ 𝑋𝑖𝑗 = 1 𝑖=1

𝑋𝑖𝑗 ≥ 0

Para todas las i y j

Ejemplo 02 (Método húngaro) Se desea asignar un almacén para abastecer una localidad, de tal forma que el recorrido entre ellos sea la menor distancia. Para ello se ha resumido la información en la siguiente Tabla.

Tabla de distancias (km) Almacenes

Localidades 1

2

3

4

1

230

200

210

240

2

190

210

200

200

3

200

180

240

220

4

220

180

210

230

PROBLEMAS DE TRASBORDO El problema de trasbordo es una extensión al problema del transporte, en el cual se agrega nodos intermedios conocidos como “nodos de trasbordo”, para tomar en consideraciones localizaciones como por ejemplo almacenes.

La oferta o suministro disponible en cada origen es limitada y en cada destino la demanda es conocida. El objetivo del problema de trasbordo es determinar cuantas unidades deberán embarcarse en cada uno de los arcos de la red, de manera que todas las demandas – destino se satisfagan al costo de transporte mínimo posible.

El modelo de programación lineal general del problema de trasbordo es: 𝑀𝑖𝑛

෍

𝐶𝑖𝑗 𝑋𝑖𝑗

𝑡𝑜𝑑𝑜𝑠 𝑙𝑜𝑠 𝑎𝑟𝑐𝑜𝑠

Sujeto a: ෍ 𝑎𝑟𝑐𝑜𝑠 𝑑𝑒 𝑠𝑎𝑙𝑖𝑑𝑎

෍

෍ 𝑎𝑟𝑐𝑜𝑠 𝑑𝑒 𝑒𝑛𝑡𝑟𝑎𝑑𝑎

Nodos de Origen i

𝑋 𝑖𝑗 = 0

Nodos de Trasbordo

𝑋 𝑖𝑗 = 𝐷𝑒𝑚𝑎𝑛𝑑𝑎 𝑗

Nodos de Destino j

𝑎𝑟𝑐𝑜𝑠 𝑑𝑒 𝑒𝑛𝑡𝑟𝑎𝑑𝑎

෍

𝑋𝑖𝑗 −

𝑎𝑟𝑐𝑜𝑠 𝑑𝑒 𝑠𝑎𝑙𝑖𝑑𝑎

𝑋 𝑖𝑗 ≤ 𝑆𝑢𝑚𝑖𝑛𝑖𝑠𝑡𝑟𝑜𝑖

෍

𝑋𝑖𝑗 −

𝑎𝑟𝑐𝑜𝑠 𝑑𝑒 𝑒𝑛𝑡𝑟𝑎𝑑𝑎

𝑋𝑖𝑗 −

෍ 𝑎𝑟𝑐𝑜𝑠 𝑑𝑒 𝑠𝑎𝑙𝑖𝑑𝑎

Donde: Xij = Número de unidades embarcadas del nodo i al nodo j Cij = Costo unitario de embarcar del nodo i al nodo j

Ejemplo 03 (Nodos de trasbordo) Una empresa cuenta con dos plantas para satisfacer a tres clientes cuyas demandas semanales actuales son de 50, 60 y 40 respectivamente. Para lograr la distribución de los productos, se tienen dos distribuidores que funcionan como nodos intermedios. Cada planta puede proveer como máximo 75 unidades a sus clientes cada uno. A continuación se muestra información adicional. Costos unitarios de los fabricantes para los distribuidores ($)

Planta

Distribuidor 1 Distribuidor 2

Costos unitarios de los distribuidores para los clientes ($)

Distribuidor Cliente 1 Cliente 2 Cliente 3

1

5

8

1

1

5

8

2

7

4

2

3

4

4

Determinar el costo mínimo de esta distribución.