Soluciones Graficas

SOLUCION GRÁFICA

Introducción

Utilizaremos algunos conceptos fundamentales de la Teoría General de los Conjuntos Convexos para interpretar geométricamente la solución de los modelos de Programación Lineal. La solución en forma gráfica se obtiene representando en un plano cartesiano las restricciones tecnológicas y la función objetivo. La forma más conocida del método consiste en asociar los ejes coordenados a las variables de decisión o actividades del problema, dando lugar al llamado método gráfico en actividades; pero hay otro enfoque conocido como método gráfico en recursos en el cual se asocian los ejes a las restricciones o recursos del problema.

Debe quedar claro que la representación gráfica del modelo no es el método general utilizado para resolver problemas reales de programación lineal, los cuales tienen muchas variables y muchas restricciones, ya que no podemos dibujar en más de tres dimensiones,

En consecuencia, el método gráfico en actividades está limitado a la solución de problemas que tengan un máximo de tres variables (actividades), y cualquier número de restricciones. De la misma manera el método gráfico en recursos sólo puede utilizarse para solucionar modelos con cualquier cantidad de actividades, pero con un máximo de tres restricciones (“recursos”).

No obstante sus limitaciones, estudiaremos el método gráfico en actividades, ya que tiene una gran utilidad didáctica. Para mayor facilidad en los análisis, resolveremos problemas que contienen solo dos actividades alternativas, lo cual nos permitirá trabajar en el plano, en lugar de hacerlo en el espacio. Este capitulo nos servirá para comprender los fundamentos conceptuales de los métodos analíticos utilizados para la solución de los problemas de programación lineal y para identificar geométricamente los diferentes tipos de solución que podemos obtener.

El método gráfico en actividades

Este análisis gráfico nos permite intuir uno de los teoremas fundamentales de la P.L., llamado teorema del punto extremo – solución óptima. Igualmente descubriremos la esencia del método simplex, que es el algoritmo mas utilizado para obtener la solución analítica de los problemas de P.L.

En forma suscinta, el algoritmo del método gráfico en actividades es el siguiente.

1. Dibujar un plano coordenado y asociar un eje a cada variable del modelo.

2. Representar en el plano las restricciones tecnológicas.

3. Identificar gráficamente el conjunto de soluciones factibles (región de factibilidad).

4. Representar en el plano la función objetivo.

5. Identificar gráficamente la solución óptima.

Para aprender el uso del algoritmo, se hallará la solución del siguiente problema sencillo de mezcla productiva, cuyo modelo consta de dos variables y tres restricciones:

Problema ejemplo No 1: Un problema de maximización

La empresa Calzado Montoya produce zapatos para dama y para caballero, mediante un proceso que se compone de tres actividades. Algunos datos importantes del proceso son:

Actividad Tiempo

(minutos / unidad) Disponible

(minutos / día)

Dama Caballero

Formado de la suela

Corte del cuero

Ensamble 4

4

6 8

3

2 800

600

600

Utilidad neta

($/unidad)

10

6

Elabore y resuelva el modelo de programación lineal que permite determinar el número de unidades de cada producto que deben fabricarse para maximizar la utilidad neta total.

El problema tiene el siguiente modelo de P.L.:

Maximizar: Z = 10 X1 + 6 X2 Utilidad

Sujeto a: 4 X1 + 8 X2 800 (1) Tiempo de Formado (min/día)

4 X1 + 3 X2 600 (2) Tiempo de Corte “

6 X1 + 2 X2 600 (3) Tiempo de Ensamble “

con X1, X2 0 condición de no negatividad

En donde X1 y X2 son el número de pares a fabricar cada día, de los artículos zapato para dama y zapato para caballero respectivamente. La primera restricción se refiere al máximo de minutos que se pueden usar diariamente en la operación de formado, la segunda al máximo en la operación de corte y la tercera al máximo en la operación de ensamble.

Solución del modelo

Paso 1: Dibujamos el plano coordenado y asignamos, arbitrariamente, el eje horizontal a la variable X1 y el eje vertical a la variable X2. ( figura 3.1)

Recordar que una ecuación del tipo aX1 + bX2 = c

(o equivalentemente de la forma X2 = - X1 + ), corresponde a una línea recta, mientras que una inecuación del tipo aX1 + bX2 c, o del tipo aX1 + bX2 c, corresponde a un semiplano cuya frontera es la correspondiente recta aX1 + bX2 = c.

Veamos cómo se grafican las restricciones tecnológicas de nuestro modelo.

Para determinar el semiplano indicado por la restricción de formado, se grafica primero la recta 4X1 + 8X2 = 800.

El trazado de la recta se realiza en forma fácil determinando los intersectos con los ejes, para lo cual se asigna alternadamente el valor cero a una variable, despejando el valor para la otra.

Para nuestra ecuación quedaría:

Si X1 = 0 entonces X2 = 800/8 = 100 (punto B que es el intersecto con el eje X2)

Si X2 = 0 entonces X1 = 800/4 = 200 (punto A que es el intersecto con el eje X1)

Procedemos luego a trazar la recta que pasa por estos dos puntos (figura 3.2).

Para definir el semiplano indicado por la inecuación, se efectúa un sencillo chequeo, consistente en verificar si el origen forma parte del semiplano.

En caso afirmativo, deducimos que el semiplano indicado por la inecuación es aquel que contiene el origen e indicamos el hecho, mediante unas flechas que parten de la recta frontera del semiplano y apuntan hacia el origen. En caso negativo, las flechas tendrán la orientación contraria, indicando que el semiplano no contiene al origen.

Reemplazando el punto (X1, X2) = (0,0) en la inecuación se obtiene: 4(0) + 8(0) = 0 < 800; indicando así que el punto (0,0) hace parte del semiplano. Por lo tanto la región de todos los puntos que cumplen la restricción 4X1 + 8X2 800; es

...