Programación Lineal: Método Gráfico

Investigación Operativa I        Página:

[pic 1]

[pic 2]

Programación Lineal:

Método Gráfico

[pic 3]

I

OBJETIVOS

• Plantear problemas de programación lineal.
• Aplicar el método gráfico para solucionar problemas de programación lineal.
• Utilizar herramientas de software para encontrar la solución gráfica.

[pic 4]

II

TEMAS A TRATAR

• Planteamiento de problemas.
• Método Gráfico.
• Software Geogebra.

[pic 5]

III

[pic 6]

MARCO TEORICO

PROGRAMACIÓN LINEAL

Técnica de modelado matemático diseñada para optimizar el empleo de recursos limitados. Todo problema de programación lineal tiene cuatro elementos básicos en su modelado o planteamiento:

1. Variables de decisión: Es lo que se quiere determinar.
2. Objetivo o meta.  Es lo que se quiere optimizar.
3. Las restricciones o limitaciones que se deben satisfacer.
4. Rango de existencia de las variables de decisión.

MÉTODO DE SOLUCIÓN GRÁFICA

Método aplicable a problemas de dos variables, el cual sigue los siguientes pasos:

1. Graficar cada una de las restricciones (líneas), indicado el espacio de soluciones que delimita por sí sola.
2. Determinar el espacio de soluciones factibles del problema (intersección de todas las restricciones).
3. Graficar la función objetivo, denotada por Z, y de acuerdo a su inclinación y objetivo del problema, determinar la solución óptima del problema.

EJEMPLO

Reddy Mikks produce pinturas tanto para interiores como para exteriores, a partir de 2 materias primas, M1 y M2. La siguiente tabla proporciona los datos básicos del problema:

Tonelada de materia prima por tonelada de:

        Pintura para        Pintura para        Disponibilidad máxima

        Exteriores        interiores        diaria (Tn.)

Materia prima M1        6        4        24

Materia prima M2        1        2        6

Utilidad por tonelada        5        4

(miles de dólares)

Una encuesta de mercado restringe la demanda máxima diaria de pintura para interiores a 2 Tn. Además, la demanda diaria de pintura para interiores no puede exceder a la de pintura para exteriores por más de una tonelada. Reddy Mikks quiere determinar la mezcla de producto óptima de pinturas para interiores y para exteriores que maximice la utilidad total diaria. (TAHA)

• PLANTEAMIENTO

Max Z = 5X1 + 4X2, lo cual está restringido a:

        6X1 + 4X2 <= 24

        X1 + 2X2 <= 6

        X2 <= 2

        -X1 + X2 <= 1

        X1, X2 >= 0

PARA INGRESAR AL GEOGEBRA

MAX 5X+4Y

S.A

R1: 6X+4Y<=24

R2: X+2Y<=6

R3: Y<=2

R4: -X+Y<=1

X,Y >= 0 (Rango de existencia, restricción de no negatividad)

• SOLUCIÓN GRÁFICA

1. Se graficarán todas las restricciones en el primer cuadrante del plano cartesiano (ya que ambas variables son positivas), con X1 como eje X y X2 como eje Y.

• Los puntos para la primera restricción (6X1 + 4X2 <= 24) son:

Si X1 = 0 ==> X2 = 6  🡺  (0,6)

Si X2 = 0 ==> X1 = 4  🡺  (4,0)

• Su representación gráfica es:

[pic 7][pic 8][pic 9][pic 10]

• De la misma forma se deben graficar las tres restricciones restantes y hallar su espacio de soluciones.

1. Al final se obtiene el siguiente gráfico, en el cual la parte sombreada representa el espacio de soluciones factibles de este problema (intersección de todas las restricciones). [pic 11]

1. Ahora se debe graficar Z, para determinar su inclinación. Se grafica Z asignándole un valor arbitrario, por ejemplo 10.

10 = 5X1 + 4X2, ahora se reemplaza X1 y X2 por cero, para hallar los puntos respectivos:

10 = 5(0) + 4X2  ==> (0, 2.5)

10 = 5X1 + 4(0)  ==> (2, 0)

[pic 12]

Si se comienza a desplazar Z hacia arriba (ya que crece en valor, se está maximizando), existe un último punto con el que choca antes de dejar el espacio de soluciones, éste es la solución óptima:[pic 13]

Este punto está formado por la intersección de las restricciones 6X1 + 4X2 <= 24 y X1 + 2X2 <= 6, entonces resolviendo un simple sistema de ecuaciones se obtiene los siguientes valores:

X1 = 3

X2 = 1.5

Esto quiere decir que se debe producir 3 toneladas diarias de pintura para exteriores y 1.5 toneladas de pintura para interiores, lo cual nos da una utilidad de:

...