Operations Research 3

Investigación de Operaciones I Instituto Tecnológico y de Estudios Superiores de Monterrey Campus Saltillo Sesión 3

Actividades de la Sesión • • • •

Lista Exposición del método gráfico Presentación de Modelos de Minimización Ejemplos

Objetivos de la Sesión • Explicar la solución de problemas lineales de 2 variables usando el método gráfico. Afianzar los conocimientos de modelación mediante ejemplos.

El Método Gráfico • El método gráfico sirve para solucionar problemas de programación lineal con 2 variables (a lo mucho 3). • Su utilidad radica en que nos permite visualizar la forma de dar solución a dichos problemas

Metodología General • Se dibuja una figura en el plano (llamada poliedro) formada con las restricciones. • Se mueve la función objetivo en dirección de su incremento (si el problema es de maximización) o decremento (si el problema es de minimización • La solución está en el último punto que toca la función objetivo antes de salirse del poliedro.

El Método Gráfico • De acuerdo a lo anterior, el método gráfico posee 2 etapas: – Determinación de un espacio de solución, también llamada “Región Factible” – Determinación de la solución óptima, entre todas aquéllas posibles soluciones

La Región Factible Las restricciones de DESIGUALDAD dividen un plano en dos regiones llamadas “semiplanos”. Uno y sólo uno de estos semiplanos cumple la desigualdad. Nota que también se incluye la frontera, es decir la línea.

y

5

x+y=5

5

x+y≤ 5

x

El Modelo para Reddy Mikks (1) 6x1 + 4x2 ≤ 24 (2) x1 + 2x2 ≤ 6 (3) -x1 + x2 ≤ 1 (4) x2 ≤ 2 (5) x1 ≥0 (6) x2 ≥ 0

5 6

3

5

1

4 3

2

4

2

Cualquier punto aquí cumple con todas las restricciones !!!

1

1

2

3

4

5

6

6

Punto 1: (4/3, 7/3)

Pregunta…

• ¿Cómo sabemos si un punto cualquiera cumple con las restricciones? • Respuesta: Sustituyendo en cada una de las restricciones. Si se viola al menos una de las restricciones, este punto no cumple. Punto 3: (5, 0) Punto 2: (3, 1)

Encontrar la Solución Optima • Una vez que hemos graficado la región factible, ¿cuál de sus puntos nos entregará un mejor valor de nuestra función objetivo? – Es necesario encontrar la dirección de incremento (problemas de maximización) o decremente (problemas de minización) de la función objetivo

El punto optimo…. • Es el último punto que toca la recta de la función objetivo a medida que aumenta (maximización) o disminuye (minización) su valor.

Z = 5x1 + 4x2 x2 3 Punto Óptimo (3, 1.5)

2

1

1

2 Z=10

3

x1

4 Z=15

Z=21

Tarea 4 • Serie de Problemas 2.2A – 1, 2, 3, 4, 5