Método Grafico

Método Grafico

I. Definición del Método.

 

El método grafico para la resolución de problemas de programación lineal (PL) consiste en representar gráficamente las restricciones, condiciones técnicas y función objetivo de dicho problema  para tratar de identificar el área de soluciones factibles, para lograr así una tabla con valores que las variables de decisión pueden adoptar, con lo cual se busca el valor máximo que la función objetivo puede obtener en base a estos valores.

Es importante mencionar que este método solo es práctico para problemas PL con únicamente 2 variables de decisión, pues cada variable representa un plano adicional en la grafica, lo que se traduce en graficas en dimensiones mayores a 2.

                

II. Pasos del Método.

 

1.    Se plantea el problema como un problema PL, en el caso de que no se tenga ya en esta forma.

2.    se grafican las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultánea, es decir, graficar cada restricción como si fuera una función lineal, con lo cual se encontrará un área que contiene todas las soluciones factibles del problema.

3.    trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada es decir, se indica con una línea hacia donde se cumple la desigualdad, hacia valores positivos, o hacia valores negativos.

4.     Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible.

5.    luego de obtener el conjunto de soluciones factibles, se identifican los vértices de la figura generada por el área factible, y se genera una tabla con los puntos de los vértices.

6.    se evalúa cada punto encontrado en la función objetivo, y el punto con el que se obtenga el mayor o menor valor, según sea el caso(Minimización o Maximización), será la solución factible del problema.

III. Ejemplo Practico.

Cierto fabricante produce dos artículos, A y B, para lo que requiere la utilización de dos secciones de producción: sección de montaje y sección de pintura. El artículo A requiere una hora de trabajo en la sección de montaje y dos en la de pintura; y el artículo B, tres horas en la sección de montaje y una hora en la de pintura. La sección de montaje solo puede estar en funcionamiento nueve horas diarias, mientras que la de pintura solo ocho horas cada día. El beneficio que se obtiene produciendo el artículo B es de 40 dólares y el de A es de 20 dólares.

Calcula la producción diaria de los artículos A y B que maximiza el beneficio.

 

1.  Se plantea el problema:

max   20A  +   40B

SA         2A  +      B<=8

               A  +     3B<=9

                        A, B>=0

2.  Se grafican las restricciones para encontrar el área factible:

 

3.  Se encuentran los valores de los vértices(Extremos del polígono formado por la solución factible)

 

Punto (B, A)	Función objetivo (Z=20A + 40 B)	Valor de Z
(0,0)	Z=20(0) + 40(0)	Z=0
(0,4)	Z=20(4) + 40(0)	Z=80
(2,3)	Z=20(3) + 40(3)	Z=140
(0,3)	Z=20(0) + 40(3)	Z=120

 

4.   Solución del problema

Se deben producir 2 productos diarios de tipo b y 3 de tipo A para una ganancia de 140.

Contribución de: Juan Maldonado, Frederick Jiménez, Johansen Pineda, Marlon Lizardo, Luis Mejía.  

 

Ejemplo Análisis de sensibilidad utilizando Solver de Excel

Ejemplo Análisis de sensibilidad utilizando Solver de Excel:

Considere el siguiente problema.

Maximizar Z = 2x1 + 4x2 + 3x3,

sujeta a:

1) x1+ 3x2 + 2x3 <= 30

2) x1 + x2 + x3 <= 24

3) 3x1 + 5x2 + 3x3 <= 60 y

4) x1>= 0, x2 >= 0, x3 >= 0.

Usted obtiene la información de que x1 > 0, x2 =0 y x3 >0 en la solución óptima.

a) Describa cómo puede usar la información para adaptar el método simplex a fin de resolver este problema en el número mínimo posible de iteraciones (si comienza con la solución BF inicial de costumbre). No realice iteraciones. *

Solución:

Planteamiento del Problema en Excel

Paso 1: Planteamiento del modelo en la hoja de cálculo. Esto incluye la definición de los recuadros "celdas cambiantes", que se refieren a las celdas de las variables que se quieren determinar.

Paso 2: Se plantea la fórmula que permite obtener la utilidad (costo) del problema como función objetivo. En este caso se define en E3, la suma producto de las celdas cambiantes (B2:D2) por la utilidad de cada variable (B3:D3).

Paso 3: Se plantean las restricciones del modelo y la utilización de los recursos de acuerdo a las celdas cambiantes. Por ejemplo, la utilización de los recursos para la restricción 1, se visualiza en la celda E6 con la suma producto de los coeficientes de los recursos de esta restricción (B6:D6) por las celdas cambiantes (B2:D2).

Paso 4: Se activa la función de Solver, en el caso del Excel 2007, ir a la sección de Datos y seleccione la opción de Solver.

Celda objetivo (Set Target Cell): se selecciona la ubicación donde se calcula el valor que se desea optimizar. En este caso la celda E5 calcula la utilidad del problema.

Valor de la celda objetivo (Equalto): Como el problema es de maximización se selecciona Max.

Celdas cambiantes (ByChangingCells): se les denomina así ya que Solver asignará valores a estas celdas en orden de conseguir la solución óptima del problema. En este caso las celdas cambiantes van de B2 a D2.

Sujetas a las siguientes restricciones (SubjecttotheConstraints): se agregan las restricciones presionando Agregar (Add) y definiendo la utilización de los recursos de acuerdo al nivel de actividad (E6:E8) versus los limites del problema planteado (G6:G8).

Luego se selecciona Opciones (Options) para definir el tipo de problema y preferencias para la solución del mismo. En ese sentido, se define asumir modelo lineal y asumir no negativos, y entre las preferencias estimaciones lineal (Tangent), derivaciones progresivas (Forward) y hallar por metodología Newton, entre otras opciones. (En la mayoría de casos no es necesario modificar datos en esta ventana, ya que pueden usarse los valores por defecto).

Paso 5: Resolver el problema haciendo click en Resolver (Solve). Inmediatamente aparece un recuadro notificando que Solver ha encontrado una solución que parece óptima. En lado de derecho de este cuadro permite seleccionar la generación de 3 informes: Respuestas (Answer), Sensibilidad (Sensivity) y Limites (Limits).

La solución óptima encontrada tiene un valor de 50 en la función objetivo maximizada con la entrada de las variables X1 y X3 en la solución óptima ambas con 10 unidades y cero para X2. También se visualiza una holgura de 4 en la restricción 2 que pasa a formar parte integral de la solución final.

Conclusión

El análisis de sensibilidad es una técnica muy empleada en la práctica. Aunque, vale la pena indicar que además de esta técnica existen muchas otras como los árboles de decisión, el análisis del riesgo y la simulación, las cuales pueden ser empleadas para evaluar la incertidumbre de una alternativa de inversión. Para concluir, revisaremos las principales ventajas que proporciona el uso del análisis de sensibilidad:

a) Su fácil entendimiento, ya que no se requiere tener conocimientos sobre la teoría de probabilidades, y por ende es una técnica de aplicación sencilla y económica.

b) Cuantifica el efecto que puede tener sobre la rentabilidad de un proyecto la incertidumbre en el comportamiento de las variables que condicionan la rentabilidad.

c) Pone de relieve las desviaciones y errores de estimación que pueden perjudicar seriamente la rentabilidad de un proyecto.

d) Separa las áreas que deben ser objeto de particular esfuerzo de recopilación de información, análisis y control.

e) Permite fijar los valores límite que han de tener las variables determinantes de la rentabilidad para que el proyecto sea rentable.

f) Exige una mayor precisión en la formulación de hipótesis y en la estimación de parámetros.

Contribución de: Mariela Nuñez, Thelma Gonzales,Jorge Altamirano, Ludwin Osorto,Camilo Reyes, Alejandro Umaña

Ejemplo de Análisis de sensibilidad simple

Ejemplo de análisis de sensibilidad simple:

A continuación se expondrá un ejemplo sencillo de Análisis de Sensibilidad desarrollado en Excel, con el que se podrán identificar los pasos principales y será más fácil apreciar el resultado y su interpretación. Pero Antes de crear el análisis de sensibilidad en Excel debo agregar los datos para los cuales se crearán los diferentes escenarios en Excel. Como puedes observar, en la fila 7 he colocado diferentes montos de venta y en la columna B (por debajo de los cálculos previos) he colocado diferentes montos de gastos variables.



Para poder crear el análisis de sensibilidad en Excel debemos seleccionar el rango de datos B7:F11 y pulsar el botón Análisis Y si que se encuentran en la ficha Datos y posteriormente seleccionar el comando Tabla de datos.



En la opción Celda de entrada (fila) colocaré la referencia a la celda que contiene el monto original de ventas (B4) y como Celda de entrada (columna) especificaré la celda que contiene los gastos variables (B6). Al pulsar el botón Aceptar se realizarán los cálculos para obtener las ganancias para cada una de las combinaciones de valores indicados.



Nota: Por motivos ilustrativos he dado formato de moneda a las celdas y he colocado en rojo los números negativos pero Excel no hará eso automáticamente por nosotros.

 

Con esta tabla de datos podemos analizar y llegar a conclusiones muy interesantes sobre nuestra información. Podemos observar que si las ventas fueran en realidad por 65,000 dólares y los gastos variables subieran a 35,000 dólares entonces comenzaríamos a tener pérdidas en el negocio.

Por otro lado puedes observar que el punto de equilibrio financiero se da cuando las ventas son de 75,000 dólares y los gastos variables son de 40,000 dólares dejándonos sin pérdidas ni ganancias. En fin, podemos pasar tiempo considerable analizando la información para poder decidir si vale la pena invertir nuestro dinero en este negocio.

Lo que Excel ha realizado es que para cada posible valor de ventas y de gastos variables que hayamos especificado ha calculado la fórmula de ganancias que está en la celda B7. Esto es un gran beneficio para nosotros porque en lugar de ir remplazando los valores de las celdas B4 y B6 para ver el comportamiento en las ganancias Excel realizará todos los cálculos en un solo paso y los colocará en la tabla de datos.

El análisis se tornará interesante si para cada proyecto de inversión que tengas realizas un análisis de sensibilidad en Excel para compararlos entre ellos y decidir por la alternativa que represente el menor riesgo posible y que tenga la mayor rentabilidad.

Contribución de: Mariela Nuñez, Thelma Gonzales,Jorge Altamirano, Ludwin Osorto,Camilo Reyes, Alejandro Umaña.

Análisis de Sensibilidad

Uno de los Temas centrales en la Investigación de Operaciones es el análisis de sensibilidad, algunos textos en inglés la denominan la técnica del "What if...", reconociendo que lo que trata de hacer esta metodología, es determinar qué pasa con la rentabilidad del proyecto, si una o más variables cambian.

Puede decirse que es una de las partes más importantes en la programación lineal, sobre todo para la toma de decisiones, es un método que nos permite visualizar de manera inmediata las ventajas y desventajas económicas de un proyecto. Este método es muy utilizado para determinar cuándo una solución sigue siendo óptima, dados algunos cambios ya sea en el entorno del problema, en la empresa o en los datos del problema mismo. Éste método se puede aplicar también a inversiones que no sean productos de instituciones financieras, por lo que también es recomendable para los casos en que un familiar o amigo nos ofrezca invertir en algún negocio o proyecto que nos redituaría dividendos en el futuro.

La base para aplicar este método es identificar los posibles escenarios del proyecto de inversión, los cuales se clasifican en los siguientes:

• Pesimista: Es el peor panorama de la inversión, es decir, es el resultado en caso del fracaso total del proyecto. 
• Probable: Éste sería el resultado más probable que supondríamos en el análisis de la inversión, debe ser objetivo y basado en la mayor información posible.
• Optimista: Siempre existe la posibilidad de lograr más de lo que proyectamos, el escenario optimista normalmente es el que se presenta para motivar a los inversionistas a correr el riesgo.

Así podremos darnos cuenta que en dos inversiones donde estaríamos dispuestos a invertir una misma cantidad, el grado de riesgo y las utilidades se pueden comportar de manera muy diferente, por lo que debemos analizarlas por su nivel de incertidumbre, pero también por la posible ganancia que representan.

En otras palabras este análisis consiste en determinar qué tan sensible es la respuesta óptima del Método Simplex (Detallado más adelante), al cambio de algunos datos como las ganancias o costos unitarios (coeficientes de la función objetivo) o la disponibilidad de los recursos (términos independientes de las restricciones).

La variación en estos datos del problema se analizará individualmente, es decir, se analiza la sensibilidad de la solución debido a la modificación de un dato a la vez, asumiendo que todos los demás permanecen sin alteración alguna. Esto es importante porque estamos hablando de que la sensibilidad es estática y no dinámica, pues solo contempla el cambio de un dato a la vez y no el de varios.

Objetivo

El objetivo principal del Análisis de Sensibilidad es determinar la factibilidad de un proyecto mediante la identificación de los parámetros sensibles, por ejemplo, los parámetros cuyos valores no pueden fluctuar significativamente sin que cambie la solución óptima, nos dará una visión más amplia del problema. Dicho de otra forma, este método busca determinar los efectos que se producen en la solución óptima al realizar cambios en cualquiera de los parámetros del modelo de programación lineal planteado inicialmente.

Los análisis más importantes son:

1. Los coeficientes de la función objetivo; y
2. Los términos independientes de las restricciones y se pueden abordar por medio del Método Gráfico o del Método Simplex.

A modo general, cuando se realiza un análisis de sensibilidad a una solución óptima se debe verificar cada parámetro de forma individual, dígase los coeficientes de la función objetivo y los limites de cada una de las restricciones. En ese sentido se plantea el siguiente procedimiento, que esta detallado con un ejercicio al final de este documento:

· Revisión del modelo: se realizan los cambios que se desean investigar en el modelo.
· Revisión de la tabla final Símplex: se aplica el criterio adecuado para determinar los cambios que resultan en la tabla final Símplex.
· Conversión a la forma apropiada de eliminación Gauss: se convierta la tabla en la forma apropiada para identificar y evaluar la solución básica actual, para lo cual se aplica la metodología de eliminación Gauss si es necesario.
· Prueba de factibilidad: se prueba la factibilidad de esta solución mediante la verificación de que todas las variables básicas de la columna del lado derecho aun tengan valores no negativos.
· Prueba de optimalidad: se verifica si esta solución es optima y factible, mediante la comprobación de que todos lo coeficientes de las variables no básicas del reglón Z permanecen no negativos.
· Re optimización: si esta solución no pasa una de las pruebas indicadas en los puntos 4 y 5 anteriores, se procede a buscar la nueva solución optima a partir de la tabla actual como tabla Símplex inicial, luego de aplicadas las conversiones de lugar, ya sea con el método Símplex o el Símplex Dual.

Ya sea que resolvamos nuestro modelo gráficamente o utilizando el Método Simplex, lo que se busca es que estas variaciones o sensibilidad hagan uso de la solución y valor óptimo actual, sin tener la necesidad de resolver para cada variación un nuevo problema.

Hay que tomar en cuenta que la información que obtengamos después de realizar el análisis puede interpretarse en dos sentidos:

1. identifica los parámetros más importantes, con lo que se puede poner un cuidado especial al hacer sus estimaciones y al seleccionar una solución que tenga un buen desempeño para la mayoría de los valores posibles.
2. Segundo, identifica los parámetros que será necesario controlar de cerca cuando el estudio se lleve a la práctica. Si se descubre que el valor real de un parámetro se encuentra fuera de su intervalo de valores permisibles, ésta es una señal de que es necesario cambiar la solución. Esto significa que puede llevarnos a un proceso iterativo, no siempre la solución la tendremos directamente pero al verificar que las restricciones se cumplan estaremos seguros de que nuestra respuesta estará maximizada o minimizada según sea el caso.Cabe mencionar que podemos apoyarnos en herramientas como SOLVER de Excel que nos dará un análisis mas amplio, una respuesta directa y mucha mas facilidad para evaluar diferentes valores en los parámetros de nuestra función objetivo.

Nota: En relación a cuáles variables vamos a considerar. Precio y cantidad, de todas maneras, tienen que seleccionarse. Las demás variables, dependen de las características de su proyecto. Así por ejemplo, si tiene un alto componente de mano de obra en su estructura de costos, entonces, el salario podría ser un elemento clave en la rentabilidad del proyecto, si, adicionalmente, es un proyecto altamente apalancado (endeudado), la tasa de interés, puede convertirse en crucial para determinar si genera valor.

*En relación a cuántas variables debe escoger. Ni muchas ni pocas. Le sugiero entre 5 a 8 como máximo. Acuérdese que, es igual de malo, tener poca como también demasiada información; pues, podría perder el foco del análisis (sin dejar de mencionar, que si su proyecto tiene más de 10 variables que usted considera importantes para la rentabilidad del mismo, entonces podemos concluir a priori que es altamente riesgoso, ¿no?).

Contribución de: Mariela Nuñez, Thelma Gonzales,Jorge Altamirano, Ludwin Osorto,Camilo Reyes, Alejandro Umaña.

Problema de Trasporte o Distribución

Problema de Trasporte o Distribución.

En la actualidad los problemas de transportes es uno de los algoritmos de resolución de problemas más aplicado en la economía actual, pues han sido utilizados con muy buenos resultados en muchas áreas de desarrollo y distribución.

El problema del transporte o distribución es un problema de redes de interconexión en las aplicaciones de programación lineal que se centra en la necesidad de transportar unidades de un punto específico llamado Fuente u Origen  hacía otro punto específico llamado Destino. Los principales objetivos de un modelo de transporte son la satisfacción de todos los requerimientos establecidos por los destinos y claro está la minimización de los costos relacionados con el plan determinado por las rutas escogidas.

Estos entonces son muy utilizados en unidades de organización y métodos dentro de las empresas, en el control de inventarios y asignación de elementos.

El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante programación lineal común, sin embargo su estructura permite la creación de múltiples alternativas de solución tales como la estructura de asignación o los métodos heurísticos más populares como Vogel, esquina noroeste o costos mínimos.

Los datos del modelo son:

1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. 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 del 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 al número de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.

Este esquema representa el modelo de transporte como una red con m fuentes y n destinos. Una fuente o un destino está representado por un nodo, el arco que une  fuente y un destino representa la ruta por la cual se transporta la mercancía. La cantidad de la oferta en la fuente i es ai, y la demanda en el destino j es bj. El costo de transporte unitario entre la fuente  i  y el destino j es Cij.

Ejemplo de solución de problema de transporte

Una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 400 unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribución con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:

	C. Dist. 1	C. Dist. 2	C. Dist. 3
Planta 1	21	25	15
Planta 2	28	13	19

Se requiere formular un modelo de Programación Lineal que permita satisfacer los requerimientos de demanda al mínimo costo.

Solución:

Variables de Decisión (X_ij): Unidades transportadas desde la planta i (i=1, 2) hasta el centro de distribución j (j=1, 2, 3)

Función Objetivo: Minimizar el costo de transporte dado por la función: 21X₁₁ + 25X₁₂ + 15X₁₃ + 28X₂₁ + 13X₂₂ + 19X₂₃

Restricciones:

Satisfacer los requerimientos de Demanda:

X₁₁+ X₂₁ = 200

X₁₂ + X₂₂ = 200

X₁₃ + X₂₃ = 250

Sujeto a la Oferta de las plantas:

X₁₁+ X₁₂ + X₁₃ = 250

X₂₁ + X₂₂+ X₂₃ = 400

No Negatividad: X_ij>= 0

Contribución de: Fernando Cárcamo, Christian Velásquez.

Método Simplex

El método simplex es un algoritmo muy utilizado en la resolución de problemas de programación lineal que tienen más de dos(2) variables.

A continuación una explicación de dicho método a través del siguiente video: