Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

IO04001 – Investigación de Operaciones I

Tema # 7 Solución de problemas mediante el método simplex matricial o revisado

Objetivos de aprendizaje Al finalizar el tema serás capaz de: • Emplear el Método simplex Matricial para la solución de problemas de programación lineal. • Obtener las diferentes matrices para llegar a la solución óptima.

D.R. © Universidad TecMilenio

1

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Introducción al tema • El Método Simplex Matricial es el más usado para la programación de paquetes computacionales de programación lineal, ya que utiliza únicamente los coeficientes relevantes del sistema de ecuaciones del modelo en cuestión, sin necesidad de acarrear números inútiles, evitando así errores entre datos. • En este tema aprenderás a manejarlo para la solución problemas,, usando una serie de matrices definidas de p portadoras de los coeficientes necesarios para obtener el resultado óptimo.

Introducción al tema

Lo interesante de este método es q que no necesariamente tienes que realizar la operación de toda la matriz, ya que los resultados de ciertas columnas son los que interesan, por lo que la mayoría del tiempo estás multiplicando y sumando renglones y columnas; y a veces, cuando la operación es para toda la matriz, por lo general, están llenas de ceros y unos, facilitando los cálculos.

4

D.R. © Universidad TecMilenio

2

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Método simplex matricial En el tema anterior estudiamos las características principales del método simplex matricial. Además, aprendimos que este método tiene ciertas ventajas sobre el simplex original, por las siguientes razones: 1. Realiza las mismas funciones que el método simplex original, pero es más eficiente. 2. Es fácil de programar en computadora para dar solución a modelos de PL PL. 3. Hace solamente las operaciones necesarias, sin guardar datos que no son útiles. 4. Las operaciones que realiza son entre matrices. 5

Método simplex matricial El simplex matricial trabaja con operaciones entre matrices, así que te sugiero repases las operaciones básicas como suma, resta, multiplicación y matriz inversa. Ya que conoces las generalidades del método simplex simplex, vamos a ilustrar esta poderosa herramienta mediante un ejemplo, de manera que te quede claro cómo utilizarlo. 6

D.R. © Universidad TecMilenio

3

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Ejemplo En una pastelería se venden 2 tipos de pasteles: pastel de fresa y tarta de chocolate. Se cuenta con 2 reposteras: A y B. La repostera A tarda 2.5 horas en preparar los pasteles, mientras que la repostera 2 tarda 4 horas. Ambos productos son los de mayor venta del negocio y tienen una utilidad de $20 y $40 respectivamente. El dueño de la pastelería quiere maximizar sus ganancias.

7

Pasos para resolver el problema problema:: 1. Definir modelo original Función Objetivo: Max Z = 20x1 + 40x2 Sujeto a: X1 ≤ 2.5 X1 + X2 ≤ 8

8

D.R. © Universidad TecMilenio

4

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Pasos para resolver el problema: 2. Definir forma aumentada del modelo: Max Z = 20x1 + 40x2 Sujeto a: X1 + X3 = 2.5 X1 + X2 + X4 = 8 Realizar las iteraciones necesarias, siguiendo el algoritmo del método simplex. Empezar con (0,0) y así de manera iterativa hasta encontrar la solución que optimice el valor de la función objetivo. 9

Pasos para resolver el problema:

10

D.R. © Universidad TecMilenio

5

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

• Segunda Iteración: El siguiente punto de la región factible es [0, 4] por lo que introducimos X2 en el lugar de la X4 para tener X1= 0

11

Tercera Iteración: Continuamos con el siguiente punto de la región factible [2.5, 1.5]

Como te podrás dar cuenta, el valor de la función objetivo disminuyó: Z = 11, mientras que en el punto [0 8] Z = 22, representando la solución óptima para este modelo. 12

D.R. © Universidad TecMilenio

6

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Método simplex tabular revisado • Una vez que has visualizado y comprendido las operaciones que se realizan en el método simplex matricial, veremos una forma todavía más sencilla de resolver problemas de PL utilizando la forma tabular del simplex revisado. • Al igual que en el método simplex original, te puedes ayudar de una tabla en la que tendrás que realizar una serie de pasos e introducir y sacar variables básicas para poder encontrar la solución que optimice la función objetivo.

13

• A continuación se presenta la forma general de la tabla. Para su uso solamente debes llenar los respectivos valores que tengas en tu modelo para las diferentes variables.

14

D.R. © Universidad TecMilenio

7

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Método simplex tabular revisado PASO 1. Definir las matrices con los valores iniciales. PASO 2. Determinar la variable básica entrante. – Buscar el coeficiente de matriz renglón c más negativo.

15

Método simplex tabular revisado • PASO 4. Determinar una nueva solución básica factible. – Realizar la prueba de optimalidad optimalidad. – Si tenemos coeficientes negativos en c, continuamos con las iteraciones. • PASO 3. Determinar la variable básica saliente. – Seleccionar los números positivos correspondientes y dividirlos entre el lado derecho correspondiente para determinar cuál es el de menor razón. – El proceso es similar al simplex original, solamente que las operaciones se realizan entre matrices. 16

D.R. © Universidad TecMilenio

8

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Continuando con el ejemplo anterior…

17

Continuando con el ejemplo anterior…

18

D.R. © Universidad TecMilenio

9

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Segunda iteración: iteración:

19

Segunda iteración: iteración:

20

D.R. © Universidad TecMilenio

10

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Método simplex tabular revisado

Como te p puedes dar cuenta,, ya y no tenemos coeficientes negativos, por lo que ya encontramos la solución óptima que maximiza la función objetivo:

21

Cierre Al saber manejar el Método Simplex Tabular, el Matricial se vuelve más sencillo de aplicar, p ,p pues no realiza todas las operaciones de la Tabla, sino únicamente de los renglones y columnas necesarios para cada iteración.

D.R. © Universidad TecMilenio

11

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Reflexión • Reflexiona sobre algunas ventajas y desventajas de aplicar el Método Simplex Matricial y el Tabular.

23

Para aprender más: más: • En el siguiente sitio puedes encontrar un e-book sobre Investigación de operaciones. Seguramente encontrarás numerosos ejemplos de problemas de programación lineal que te ayudarán a una mejor comprensión de los temas estudiados. • http://books.google.com.mx/books?id=8IMSA6DEaRoC &pg=PA563&lpg=PA563&dq=problemas+simplex+revisa do&source=bl&ots=MGiY208FQq&sig=R7HdV9dCP7JT zx42tEaZTIHItQw&hl=es&sa=X&oi=book_result&resnum =8&ct=result#PPA562,M1 (revisado 14 de enero de 2009). 24

D.R. © Universidad TecMilenio

12

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Para aprender más: más: • Si quieres conocer más sobre las principales características del método simplex, consulta la siguiente li d liga de IInternet, t t en d donde d encontrarás t á iinformación f ió sobre b los conceptos clave y ejemplos de problemas de programación lineal. • The simplex method. http://www.cise.ufl.edu/~davis/Morgan/chapter1.htm ((recuperado p 14 de enero de 2009))

25

Referencias bibliográficas Libro Hillier, F., Lieberman, G. (2006). Introducción a la Investigación de Operaciones. (8ª Ed.) México: McGraw Hill. ISBN 970-10-5621-3

D.R. © Universidad TecMilenio

13

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Créditos Diseño de contenido: Ing. Ingrid Gabriela Benavides García Coordinador académico del área: Lic. José de Jesús Romero A. MC y MED Edición de contenido: Lic. Rosa Luz Fernández Retana Edición de texto: Lic. Dalila de León Bañuelos, MTE

D.R. © Universidad TecMilenio

14