Ing. Informatica



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 unproblema 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 seasocian 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.

Elalgoritmo 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 factible5. 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 seconocen 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 dosvariables 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 yotros 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 seencuentra 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ónobjetivo.



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...