• Author / Uploaded
• Fer Jimenez Figueroa

Citation preview

N.E. 2

N.L.8

INVESTIGACIÓN DE OPERACIONES

INGENIERÍA MECÁNICA

Examen

Tema: Proporcionar el enunciado de un problema de transporte, transbordo, transbordo de una variable ,asignación el cual se solucionará por medio de PL donde además explicitaremos el modelo matemático, el número de iteraciones, el reporte combinado, su dual y la solución del mismo

04/10/2018

09/10/2018

Fecha de asignación

Fecha de entrega

Jiménez Figueroa Fernando Santiago

Planteamiento del ejercicio La empresa HIMER que se dedica la fabricación de mesas y sillas. Por la cuales genera un utilidad de 7 por mesa y de 5 por silla, la empresa tiene un tiempo de carpintería en horas disponibles es de 240 al mes y se sabe que una mesa requiere de 4 horas y una silla de 3 horas, otra restricción es el tiempo disponible para pintura al mes es de 100 horas y se sabe que una mesa requiere de 2 horas y una silla de 1 hora. ¿Determinar el número de mesas y sillas a fabricar para obtener la máxima utilidad?

Formulación 𝑀𝑎𝑥𝑓(𝑥) = 7𝑥1 + 5𝑥2 (Utilidad) 𝑆. 𝑎 4𝑥1 + 3𝑥2 ≤ 240 𝑅𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑑𝑒 𝑡𝑖𝑒𝑚𝑝𝑜 𝑒𝑛 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑒𝑟𝑖𝑎 2𝑥1 + 𝑥2 ≤ 100 𝑅𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑑𝑒 𝑡𝑖𝑒𝑚𝑝𝑜 𝑒𝑛 𝑝𝑖𝑛𝑡𝑢𝑟𝑎

Datos WinQSB

Solución Método Simplex Solución WinQSB

Primera iteración

Segunda iteración

Ultima iteración

Solución Método Dual Primera iteración

Segunda iteración

Tercera iteración

Ultima iteración

Análisis de sensibilidad Para realizar este análisis de sensibilidad utilizare el reporte combinado que no ofrecen las dos herramientas.

Reporte WinQSB

Análisis Como se pude ver en los reportes de las dos herramientas nos proveen información similar en el caso de WinQSB ofrece los rangos de los coeficientes de aportación de nuestra función objetivo en el recuadro verde .Estos rangos significan que si modificamos uno de estos coeficientes el número de sillas y mesas no se vería afectado por este cambio en el coeficiente de aportación. En este caso la solución es: 𝑀𝑒𝑠𝑎𝑠 = 30 𝑆𝑖𝑙𝑙𝑎𝑠 = 40 𝑼𝒕𝒊𝒍𝒊𝒅𝒂𝒅 = 𝟒𝟏𝟎 Ahora veamos el caso en que La empresa Himer lograra que sus utilidades por Mesa sean de 9 unidades monetarias su utilidad aumentaría pero no el número de mesas y sillas que tendría que hacer para obtener la máxima utilidad.

Como vemos en las anteriores imágenes se evidencia lo anterior mente dicho quedando como resultado de nuestro problema de programación lineal así: 𝑀𝑒𝑠𝑎𝑠 = 30 𝑆𝑖𝑙𝑙𝑎𝑠 = 40 𝑼𝒕𝒊𝒍𝒊𝒅𝒂𝒅 = 𝟒𝟕𝟎 La ecuación que representa la utilidad para cualquier coeficiente de utilidad de mesas (C1) dentro del rango (6,6667 - 10) es: 𝑴𝒂𝒙𝒇(𝒙) = 𝐶1 ∗ 30 + 200

Para continuar con el análisis de sensibilidad ahora analizare que pasaría si la empresa HIMER lograra aumentar el número de horas en pintura a 110 horas.

Como se puede observar en la imagen anterior se evidencia que al modificar el número máximo de horas disponibles para pintura el número de sillas y mesas que es necesario para alcanzar la máxima utilidad también cambia. También el valor máximo de la función objetivo quedando así: 𝑀𝑒𝑠𝑎𝑠 = 45 𝑆𝑖𝑙𝑙𝑎𝑠 = 20 𝑼𝒕𝒊𝒍𝒊𝒅𝒂𝒅 = 𝟒𝟏𝟓

Recomendaciones Basado en los resultados obtenidos por el método simplex, dual y analizar la sensibilidad de la solución óptima del modelo de programación lineal. Mi primera recomendación es la de lograr aumentar la utilidad de por lo menos uno de los productos (Mesas y Sillas). Que es cuando se logra evidenciar un aumento considerable en la utilidad máxima. Otra de las mediad que se podrían tomar serían las de aumentar el número de horas disponibles en cada sección (Carpintería y pintura).

Por método de transporte Ahora se consignan los costos asociados al modelo, igualmente se consignan la respectiva oferta de cada una de las plantas y las demandas de las ciudades.

Ahora que se ha completado de suministrar toda la información se procede a resolver el modelo (click en resolver), la ventana que se abrirá tendrá la información respecto a las unidades enviadas de cada Planta hacia cada ciudad y el costo total óptimo.

Carga

costo unitario costo total de la d.

De esta manera se obtiene la solución óptima del modelo de transporte, sin embargo no es todo lo que WinQSB tiene para ofrecer respecto al modelo de transporte, dado que este software posee herramientas que entregan el resultado gráficamente y presenta los resultados que se obtienen mediante los métodos heurísticos que hemos visto en módulos anteriores como Método de Aproximación de Vogel, Método de Costos Mínimos y el Método de la Esquina Noroeste, que una vez se ha obtenido la solución mediante el programa sirven para entornos netamente académicos.

Para poder visualizar (recordamos que esto es regularmente requerido con fines académicos) los tabulados finales obtenidos mediante los métodos heurísticos en Network Modeling tenemos que acceder a la pestaña llamada "Solve and Analyze" una vez ahí

debemos seleccionar la opción "Select Initial Soluction Method", Tal como lo mostramos a continuación.

Una vez cumplido este procedimiento se abrirá un menú en el cual podremos seleccionar el método heurístico cuyo tabulado final queremos observar.

Una vez hemos seleccionado el método damos click en "OK" y procedemos a acceder a la opción "Solve and Display Steps - Tableu" que se encuentra en la pestaña "Solve and Analyze" tal como lo mostramos a continuación.

Podemos cotejar los resultados con los obtenidos mediante los mismos métodos en los módulos anteriormente explicados, observaremos que son exactamente iguales preponderando la función de este software.

Resolución De Un Problema De Transbordo Mediante Programación Lineal Para poder resolver un problema de transbordo mediante programación lineal, basta con conocer una nueva familia de restricciones, las llamadas restricciones de balanceo. En un problema de transbordo existen 3 clases de nodos, los nodos de oferta pura, los de demanda pura y los nodos transitorios que posibilitan el transbordo y que deben de balancearse para hacer que el sistema sea viable, es decir, que todas las unidades que ingresen a un nodo sean iguales a las que salgan del mismo (unidades que salen + unidades que conserve el nodo).

El Problema Modelar mediante programación lineal el problema de transbordo esbozado en la siguiente figura .

TAHA - Investigación de Operaciones La figura muestra una serie de nodos y sus respectivas rutas mediante las cuales se supone distribuir las unidades de un producto, el número que lleva cada arco (flecha) representa el costo unitario asociado a esa ruta (arco), y las cantidades que se ubican en los nodos iniciales representan la oferta de cada planta, así como las cantidades de los nodos finales representa la demanda de cada distribuidor.

Las Variables De Decisión En este caso como en la mayoría las variables de decisión deben representar la cantidad de unidades enviadas por medio de cada ruta. Es muy aconsejable denotar cada nodo con un número para simplificar la definición nominal de las variables.

Una vez renombrado cada nodo definiremos las variables: XA,C = Cantidad de unidades enviadas desde P1 hacia T1 XA,D = Cantidad de unidades enviadas desde P1 hacia T2 XB,C = Cantidad de unidades enviadas desde P2 hacia T1 XB,D = Cantidad de unidades enviadas desde P2 hacia T2 XC,D = Cantidad de unidades enviadas desde T1 hacia T2 XC,E = Cantidad de unidades enviadas desde T1 hacia D1 XC,F = Cantidad de unidades enviadas desde T1 hacia D2 XD,F = Cantidad de unidades enviadas desde T2 hacia D2 XD,G = Cantidad de unidades enviadas desde T2 hacia D3 XE,F = Cantidad de unidades enviadas desde D1 hacia D2 XF,G = Cantidad de unidades enviadas desde D2 hacia D3

Restricciones Existen en este modelo 3 tipos de restricciones y están estrechamente relacionadas con los tipos de nodos existentes, para un nodo oferta pura existe la restricción de oferta; para un nodo demanda pura existe la restricción de demanda, y para un nodo transitorio y/o transitorio de demanda existe la restricción de balance. Recordemos que los nodos transitorios son aquellos que tienen rutas (arcos o flechas) de entrad y salida, y si además este presenta un requerimiento de unidades se denomina transitorio de demanda. Restricciones de Oferta: XA,C + XA,D = 1000 XB,C + XB,D = 1200

Restricciones de demanda: XD,G + XF,G = 500 Restricciones de balanceo para nodos únicamente transitorios: Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a las unidades que salgan. XA,C + XB,C - XC,D - XC,E - XC,F = 0 XA,D + XB,D + XC,D - XD,F - XD,G = 0 Restricciones de balanceo para nodos transitorios con requerimientos: Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a la sumatoria de las unidades que salen más los requerimientos del nodo (demanda). XC,E - XE,F = 800 XC,F + XD,F + XE,F - XF,G = 900

Función Objetivo En este caso la definición de la función objetivo se limita a la consignación de cada ruta con su respectivo costo bajo el criterio "minimizar". ZMIN = 3XA,C + 4XA,D + 2XB,C + 5XB,D + 7XC,D + 8XC,E + 6XC,F + 4XD,F + 9XD,G + 5XE,F + 3XF,G

Ingresando El Modelo A Winqsb

www.ingenieriaindustrialonline.com

Solución Obtenida Mediante Winqsb

Esta es la representación gráfica de la solución cuyo costo óptimo es de 20.700 unidades monetarias.

Transporte y Asignación Al ejecutar el módulo “Network Modeling” la ventana de inicio es la siguiente

desde la cual, a partir del menú File ↓ New Problem puedes introducir un nuevo problema (también se puede hacer pinchando sobre el primer icono que aparece debajo de “File”

), o bien con

File ↓ Load Problem puedes cargar un problema guardado con anterioridad (también se puede usar para ello el segundo icono

). El propio programa incluye algunos ejemplos de

muestra. Podemos salir del programa con File ↓ Exit o bien, pinchando el icono

.

Introducción de un nuevo problema La ventana que aparece es la siguiente

en la que debemos especificar: En Problem Type: el tipo de problema (si es un Problema de Transporte (Transportation Problem) o de Asignación (Assignment Problem)). En Objective Criterion, el tipo de problema (si es de maximizar (Maximization) o de minimizar (Minimization)). En Data Entry Format, el tipo de formato para la entrada de datos. Además, debemos incluir: Problem Title: Un título para el problema que vamos a introducir. Number of Sources: Número de orígenes del problema. Number of Destinations: Número de destinos del problema. Notemos que no es necesario equilibrar el problema para su resolución, internamente lo hará el programa.  El formato de datos “Spreadsheet Matrix Form” presenta el problema en una hoja de cálculo como la siguiente

en la que debemos introducir a) Los coeficientes (costes) de la función objetivo. b) Los valores de las demandas correspondientes a cada destino. c) Los valores de las disponibilidades correspondientes a cada origen. En el menú Edit

podemos cambiar cualquier dato del problema: nombre del problema, de los nodos, el criterio de la función objetivo (maximizar o minimizar), tipo del problema (Transporte, Asignación, etc) e insertar o eliminar un nodo. Por ejemplo, el siguiente problema. Ejemplo 1. Una compañía proporciona a ICE Corporation motores para refrigeradores. La compañía tiene dos instalaciones, I1 e I2, donde se fabrican los motores siendo las capacidades de producción de cada una 45 y 10, respectivamente. La ICE Corporation fabrica los refrigeradores en tres plantas ubicadas en Boston, Denver y Atlanta. Los planes de producción requieren que se fabriquen al menos 10, 20 y 30, respectivamente. En la siguiente tabla se proporcionan las estimaciones de los costos de transporte y producción.

se incluiría como

 El formato gráfico “Graphic Model Form” presenta el problema mediante una red, especificando los nodos que representan los orígenes y destinos y los arcos que los unen.

No contemplamos la introducción de los datos en el formato Graphic Model Form ya que excede los objetivos de esta guía. No obstante, si se está interesado se puede consultar la ayuda correspondiente. A continuación mostramos una pantalla de cómo se visualizaría un problema en ese caso.

En el menú Format

o con los iconos se puede seleccionar en Number, el formato de los datos (notación científica, número de decimales, etc.); en Font, el tamaño, color, estilo y efecto de la letra; en Alignment, la alineación de la primera fila, primera columna, todas las columnas o columnas selccionadas; en Row Height, la altura de las celdas; en Column Width, la anchura de las celdas. Además en Switch to Graphic Model, presenta la red correspondiente al problema introducido.

Resolución de un problema En el menú Solve and Analyze

podemos elegir:

Solve the Problem (icono resultado de la resolución.

), para resolver el problema. En este caso, nos muestra el

Solve and Display Steps-Network (icono ), para resolver el problema mostrando las distintas redes o grafos hasta obtener la solución óptima. Solve and Display Steps-Tableau (icono ), para resolver el problema mostrando las distintas tablas solución hasta obtener la solución óptima. Select Initial Solution Method, para seleccionar el método que determine una solución básica factible inicial (Método del elemento mínimo, Método de la esquina Nororeste, etc). Veamos cada uno de ellos con un ejemplo. Ejemplo 1: Resolver el siguiente problema de transporte minimizando los costes.

Si lo resolvemos con Solve the Problem, se obtiene Orígenes y destinos

Valores de la solución

Costes o Contribución coeficientes de cada variable de la función en el valor óptimo objetivo de la función objetivo

Valor óptimo de la función objetivo: 145. Una vez resuelto el problema en el menú

Costos reducidos (costo que genera incrementar una unidad para cada variable no básica)

podemos solicitar distintas opciones para mostrar los resultados. La opción Solution Table –Nonzero Only muestra en la tabla resumen las variables básicas.

La opción Solution Table-All muestra el valor de todas las variables de decisión.

La opción Graphic Solution muestra la solución óptima gráfica mediante una red.

La opción Range of Optimality muestra el análisis de sensibilidad para los coeficientes de la función objetivo, es decir, el rango de valores de los coeficientes para que las variables básicas no cambien.

La opción Range of feasibility muestra el rango de valores de los recursos y demandas para que las variables básicas sean las mismas. Este comando está disponible en los problemas de Transporte, no de Asignación.

La opción Perform What if Analysis permite hacer un Análisis de sensibilidad de los costos y recursos/demandas. La opción Perform Parametric Analysis permite hacer un Análisis de sensibilidad paramétrico de los costos y de los recursos/demandas. En el caso de los costos se puede especificar si el análisis se hace para una única variable o para un vector perturbación de la función objetivo. En el caso de los recursos se puede hacer para un único recurso o para un vector perturbación de todos ellos. Analizaremos todo más adelante.

Por último, la opción Show run time and iteration muestra un mensaje con información sobre el tiempo y número de iteraciones necesarias para la resolución. Si resolvemos el problema con Solve and Display Steps-Network (para volver a mostrar el problema se selecciona dentro del menú Window) se obtiene

que corresponde a la primera iteración de la resolución mediante el método gráfico; a continuación en menú Simplex Iteration

marcamos Next Iteration y se obtienen de forma sucesiva los gráficos correspondientes a las sucesivas iteraciones y con el último, la tabla óptima resumen . En este ejemplo, sería

Si marcamos Show Entering and Leaving arcs muestra la variable que entra y sale de la base.

Si resolvemos el problema con Solve and Display Steps-Tableau (para volver a mostrar el problema se selecciona dentro del menú Window) se obtiene

Para resolver un problema de Asignación los módulos descritos anteriormente funcionan de la misma manera. Por ello, nos limitamos sólo a resolver un ejemplo. Ejemplo 2: Una empresa de alimentación tiene en plantilla a tres ejecutivos, Ei, i=1,2,3, que debe asignar a tres grandes clientes Cj, j=1,2,3. Los costes estimados (en euros x104) de la asignación de cada ejecutivo a cada cliente son

Introducción de datos

Notar que en este tipo de problemas no hay que especificar los recursos y demandas ya que todos toman el valor uno. Solución del problema

MODELO DE TRANSBORDO Ingresemos la información de un modelo de red que enlaza 2 fábricas con 4 almacenes y 3 grupos demandantes (9 nodos en total):

Para modificar los nombres de los nodos pulsamos sobre Node Name en el menú Editar (Edit). Modifiquemos dichos nombre como se muestra a continuación:

La tabla muestra dos fuentes (fábricas S1 y S2) que cuentan con capacidades de producción de 600 y 800 unidades para un período dado. Hay 4 almacenes intermedios, T1 a T4, de los cuales T2 y T3 poseen 350 y 200 unidades respectivamente. Las demandas son T1, 200 unidades; T4, 100 unidades; D1, 500 unidades; D2, 350 unidades y D3 900 unidades. Los costos de transportar una unidad de producto desde cada fuente y punto de trasbordo hasta cada sitio de demanda se encuentran en el cuerpo de la tabla.

Para ver el modelo en modo gráfico procedemos a marcar la opción

Una versión arreglada de nuestro modelo de redes se muestra a continuación:

La tabla de resultados finales muestra cómo se da el flujo de productos desde a las fuentes iniciales (S) a los puntos de transbordo (T) y de estas a los destinos finales, con un costo total de 7900 u.m.

Modelo de Transbordo: Una empresa de distribución de derivados de petróleo esta estudiando un esquema para la distribución de combustible en una región con 4 mercados (A, B, C y D), cuya demanda es presentada en el siguiente cuadro:

DEMANDA SEMANAL (TON/MES) MERCADO DEMANDA A

150 000

B

200 000

C

100 000

D

250 000

Para atender esta demanda, la empresa pretende utilizar transporte marítimo y transporte terrestre. Por lo tanto es necesario terminales marítimos a lo largo de la costa. Los terminales considerados son denominados T1, T2 y T3. Las capacidades de cada terminal se presentan en el cuadro siguiente: CAPACIDAD TERMINAL (TON/MES) T1 350 000 T2 300 000 T3 350 000 El combustible a ser distribuido en la Región puede venir de dos refinerías distintas. La refinería 1 tiene una capacidad de producir 300 000 Ton/mes. La segunda refinería tiene una capacidad de 500 000 Ton/mes. Los costos de transporte por tonelada se presentan en el cuadro siguiente:

COSTOS DE TRANSPORTE ($/Ton) MERCADOS

REFINERÍAS

A

B

C

D

1

2

T1

15

14

16

12

18

14

T2

20

13

14

12

19

13

T3

15

10

15

10

20

15

a) Suponiendo que los terminales tienen capacidad irrestricta, utilizando el WinQSB, determine el plan de distribución que minimice el costo total. ¿Cuál es el costo total? ¿Cuál es la capacidad ociosa en cada refinería? SOLUCIÓN

a)

Para visualizar mejor el problema dibujamos la red del problema, luego ingresamos los datos utilizando el tipo de problema: Network Flor Problem

La solución es la siguiente:

Por lo tanto, el plan de distribución (gráficamente) es:

El costo total es $19 150 000, la única capacidad ociosa es 100 000 toneladas en la Refinería