Método gráfico
La solución en forma gráfica se obtiene representando en un plano cartesiano las restricciones tecnológicas y la función objetivo. No es el método generalmente usado pero nos permite visualizar rápidamente la solución en problemas sencillos de dos y tres variables. Si el problema tiene dos variables obtiene una gráfica en el plano de dos dimensiones y si se trata de un problema de 3 variables se dibuja entonces una superficie en el espacio. Estudiaremos el método por la utilidad didáctica que tiene. 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.
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 más utilizado para obtener la solución analítica de los problemas de P.L.
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 cada una de las restricciones
3. Identificar gráficamente el conjunto de soluciones factibles (región de factibilidad).
4. Evaluar la función objetivo en cada uno de los puntos extremos de la región factible
5. Identificar la solución óptima. Si el problema es de maximización la solución corresponde al punto en el cual el valor de la función objetivo es mayor. Si el problema es de minimización la solución está dado por aquel punto en donde la función objetivo tiene un menor valor.
Si se trata de un problema de dos variables, x1 y x2, tenga en cuenta: una recta se puede trazar si se conocen al menos dos puntos de la misma, los puntos más fáciles de calcular con los cortes con los ejes, para lo cual se asume como cero una de las variables y se calcula el valor de la otra variable, con lo cual se obtienen los puntos (0, x2) y (x1,0) los cuales se pueden unir con una recta.
EL TEOREMA DEL PUNTO EXTREMO-SOLUCIÓN ÓPTIMA
La región de soluciones posibles de un modelo con dos variables es un polígono, mas exactamente un polígono convexo. Puede demostrarse que lo anterior es una característica general para los problemas de P.L. En efecto, la región de factibilidad de todo problema de P.L., en más de dos dimensiones, es un poliedro convexo. Más adelante veremos que, como casos especiales, algunos problemas presentan regiones de factibilidad no acotadas en algún sentido y otros tienen conjunto vacío de soluciones posibles
Cada vértice del polígono (o poliedro) de factibilidad se llama punto extremo y los puntos que pertenecen a las líneas que forman los lados se conocen como puntos frontera. Dos puntos extremo son adyacentes si la recta que los une es una frontera o lado del espacio de soluciones.
Teorema: Si un problema de P.L. tiene solución óptima, esta se encuentra en uno de los puntos extremo o en una de las líneas que una dos puntos extremo adyacentes de la región de factibilidad.
Tipos de solución:
1. Solución óptima única: Una solución es óptima única, cuando tanto las variables como la función del objetivo toman valores finitos, existiendo una sola combinación de valores de las variables que optimiza el valor de la función objetivo.
2.
Solución óptima múltiple: Cuando al
mover la isocuanta (recta que produce iguales valores) en su dirección de
mejoría, su último contacto con la región de factibilidad no es un punto, sino
toda una línea, ó sea uno de los lados del polígono (poliedro); entonces todos
los puntos que están sobre la recta son soluciones optimas del modelo. Como una
recta tiene un número infinito de puntos, hemos encontrado un número infinito
de soluciones optimas equivalentes. De otra manera se dice que el modelo tiene soluciones
óptimas alternativas
La solución óptima múltiple no es tan frecuente en la práctica como la solución optima única. Si realmente encontramos este tipo de solución, tendríamos una gran flexibilidad para tomar la decisión, puesto que con diferentes valores de las variables, podemos obtener el mismo valor de la función objetivo, pudiendo de esta manera “escoger la solución” que más nos convenga en un momento determinado, en consideración a otros factores no cualitativos del problema. Como ilustración, consideremos el siguiente modelo:
Maximizar: Z = 14X1 + 6X2
s.a. 3X1 + 5X2
8X1 - 12X2
7X1 + 3X2
con X1, X2
3. Solución ilimitada: Se presenta solución ilimitadamente óptima, o simplemente solución ilimitada, cuando una o más variables y la función objetivo toman un valor ilimitado, cumpliendo con las restricciones estructurales. Cuando se obtiene solución ilimitada, es debido a una de las siguientes causas:
a. Omisión de una o más restricciones.
b. Fallas en la formulación.
c. Errores en el valor de los parámetros.
De manera que ningún problema real de programación lineal tiene este tipo de solución y cuando se presenta es porque se ha cometido alguno de los errores descritos. Consideremos el siguiente modelo:
Maximizar: Z = 10X1 +
5X2
s.a. -3X1 + 4X2
X1 - 2X2
X1 + 2X2
con X1, X2
4. Solución infactible: Consideremos el siguiente modelo:
Maximizar:
Z = 2X1 + 3 X2
s.a. 1X1 - 4X2
1X1 - 1 X2
1X1 + 1 X2
con X1, X2
Al realizar la grafica observamos que la región de puntos que cumplen todas las restricciones no cumplen la condición de no negatividad de las variables. En este caso se puede decir que el modelo tiene solución matemática, pero no tiene una solución real ya que los puntos que cumplen las restricciones, tienen una o más componentes negativas.
Se dice que un problema de programación lineal tiene solución infactible, cuando no pueden encontrarse soluciones que además de cumplir con las restricciones estructurales, cumplan con la condición de no negatividad de las variables. Geométricamente, esto implica que la región de los puntos que cumplen todas las restricciones se halla fuera del primer cuadrante (primer ortante para más de dos dimensiones). Al igual que la solución ilimitada, no es normal que un problema real de P.L., tenga este tipo de solución. Su aparición se debe a errores tales como:
a. Hay restricciones en conflicto, ó sea que ellas no pueden satisfacerse simultáneamente.
b. Fallas en la modelación.
c. Errores en los valores de los parámetros.
5. Inexistencia de una solución: La última situación que puede presentarse, durante la solución de un problema, es que este no tenga ninguna solución. Se presenta el caso cuando no pueden hallarse puntos que cumplan las restricciones tecnológicas. Cuando se tiene esta solución, puede ser debido a alguna de las siguientes causas:
a. Fallas en la formulación.
b. Errores en los parámetros.
c. Hay restricciones en conflicto.
Consideremos el siguiente modelo:
Maximizar: Z = 4X1 + 7X2
s.a. -2X1 + 3X2
3X1 + 2X2
-5X1 + 1X2
con X1, X2
Se observa que la región de factibilidad es un espacio vacío, pues ningún punto cumple simultáneamente con las restricciones estructurales. A veces se denomina tanto a la solución infactible como a la inexistente con el nombre genérico de solución inconsistente.
Ejemplo. Se va a organizar una planta de un taller de automóviles donde van a trabajar electricistas y mecánicos. Es necesario que los mecánicos al menos superen en número de 5 a los electricistas y que el número de mecánicos no supere al doble que el de electricistas. En total hay disponibles 8 electricistas y 10 mecánicos. Cada electricista produce 250 euros al día y cada mecánico produce 200 euros. ¿Cuántos obreros contratar para maximizar la ganancia?
Modelo completo: Max Z = 250X1 + 200X2 SA: R1: X1 – X2 >= 5 R2: X1 – 2X2 <= 0 R3: X1 <= 10 R4: X2 <= 8 X1>=0 y X2 >=0
Función objetivo: Max Z = 250X1 + 200X2
Restricciones:
Cantidad de mecánicos: X1 >= X2 + 5 equivalente a: X1 – X2 >= 5
X1 <= 2x2 equivalente a: X1 – 2X2 <= 0
Por disponibilidad de mano de obra:
X1 <= 10
X2 <= 8
Gráficamente tenemos:
Trazamos el plano cartesiano y definimos a X1 como el eje de las abscisas y a X2 el eje de las ordenadas.
Para trazar la recta R1:
Calculamos los cortes con los ejes. En R1, si X1 = 0 entonces X2=-5, esto nos permite obtener el punto (0,5). Si X2 = 0 entonces X1=5, lo que nos da el punto (5,0). Con estos dos puntos podemos trazar la recta R1.
Recta R2:
Si X1=0 entonces X2=0, lo que nos da el punto (0,0). Necesitamos otro punto para poder trazar la recta, cualquier valor nos puede servir, tomemos por ejemplo cuando X1 = 10, entonces X2=5, con lo que obtenemos el punto (10, 5).
Recta 3: se trata de una línea recta paralela al aje de X2 que cruza al eje X1 en el punto (10,0)
R2 R3 R4 X2 X1
C (10,0) (10,5) (0,8) (0,5)
R1 (5,0)
Para hallar el punto C debemos resolver el sistema de ecuaciones simultáneas formado por R1 y R2:
R1: X1 – X2 >= 5
R2: X1 – 2X2 <= 0
Básicamente existen tres métodos para resolverlo: igualación, sustitución o reducción. Por ejemplo usemos el método de sustitución: de R1 despejamos X1 y la reemplazamos en R2, así:
De R1obtenemos: X1 = 5 + X2, reemplazando en R2 tenemos: 5 + X2 – 2X2 = 0. Agrupando términos semejantes tenemos: -X2 + 5 = 0, equivalente a: -X2 = -5. >Si multiplicamos por -1 a ambos lados de la ecuación, esta no cambia, por lo tanto obtenemos: X2 = 5, ahora este valor lo reemplazamos en cualquiera de las dos ecuaciones originales con lo cual podemos hallar el valor de la otra variable. Entonces en R1:
X1 – 5 = 5 de donde obtenemos: X1 = 10.