• Author / Uploaded
• Manuel Cardenas

Citation preview

Nombre: José Manuel Cárdenas Hernández Matrícula: 2885907 Nombre del curso: Modelación para Nombre del profesor: Norma Leticia la toma de decisiones Módulo: 1 Fecha: 23/09/2020 Bibliografía: 

Cárdenas Hernández Actividad: Evidencia 1

Hillier, F. y Frederick, S. (2010). Investigación de operaciones (9ª ed.). México: McGraw-Hill. ISBN: 978-607-15-0308-4

1. 2. 3. 4. 5. 6.

Define el concepto de método gráfico y simplex. Elabora un listado con las ventajas y desventajas de cada uno de los métodos gráfico y simplex. Describe el concepto o definición de cada uno de los cuatro casos especiales del método simplex. De acuerdo a su concepto redacta por lo menos dos ejemplos donde puedas aplicar cada uno de los cuatro casos especiales del método simplex. Con la información obtenida, elabora el cuadro comparativo sobre los dos modelos que se te solicita. Concluye sobre esta actividad.

1. Método grafico Uno de los métodos de solución para los modelos de programación lineal es el método gráfico, el cual consiste en la representación gráfica de las restricciones y función objetivo definidos en el tema anterior. Para poder hacer uso del método gráfico, es necesario que el modelo de programación lineal sea únicamente de dos variables, cuya función objetivo sea de minimizar o maximizar. De acuerdo con Taha (2012), el método gráfico consta de dos pasos: 1. 2.

Determinar el espacio de soluciones factibles. Determinar la solución óptima de entre todos los puntos localizados en el espacio de soluciones.

Método simplex El método simplex está basado en las siguientes consideraciones: 

Toma en cuenta sólo las soluciones factibles delimitadas por los vértices del área de soluciones o región factible.

  



En caso de que la primera solución factible no sea la óptima, inicia el proceso de iteración (repetición de pasos en búsqueda de la solución óptima). Cuando sea posible, debemos considerar el origen (0,0) como la primera solución factible o la inicial. Si existe la necesidad de iniciar el proceso de iteración, la siguiente solución factible a ser evaluada debe de ser la adyacente al vértice de solución que está siendo evaluada. Analiza la tasa de crecimiento que habría al moverse de un vértice de solución factible a otro. Un valor positivo significa que la solución adyacente es mejor que la actual. Un valor negativo significa que la solución adyacente es peor a la actual.

2. Ventajas y desventajas del método grafico Ventajas     

Permite reducir los sistemas de ecuaciones hasta en dos variables. Es sencillo de realizar. Los resultados obtenidos son confiables. Utilizando técnicas de despejes podemos aplicarlos a cualquier sistema de ecuaciones. Es mas rápido que el metodo de reducción y sustitución. Desventajas

    

Puede estar sometido a errores de escala de la grafica. En ocasiones las graficas de las funciones no son sencillas de realizar. Podemos cometer errores de aproximación al momento de observar Podemos cometer errores de aproximación por el trasado. El construir la gráfica no siembre es favorable.

Ventajas y desventajas del método simplex Ventajas 

Es un método heurístico. Se basa en consideraciones geométricas y no

 

requiere el uso de derivadas de la función objetivo. Es de gran eficacia incluso para ajustar gran número de parámetros. Es fácil de implementar y usar, y sin embargo tiene una alta eficacia.



Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales fácilmente. Desventajas

 

Converge más lentamente que otros métodos pues requiere mayor número de iteraciones Requiere muchas repeticiones de acuerdo a la dimensión del problema,



el procedimiento del gráfico es sencillo Se necesitan conocimientos avanzados de programación lineal, el método gráfico solo requiere de conocimientos generales de



programación lineal Es largo y fácil de equivocarse, el gráfico es mucho mas corto

3. Casos especiales del método simplex: En la búsqueda de la solución óptima para un modelo de programación lineal, podemos hacer uso del método simplex si las condiciones del modelo lo ameritan, pero debemos estar conscientes de que podrían presentarse los llamados casos especiales en el desarrollo de la solución del modelo, debido al tipo de restricciones y función objetivo que se tengan y cómo quede su recta representada en la gráfica del modelo. Debido a que en un modelo de programación lineal puede existir más de una solución, el método simplex permite ir mejorando las soluciones seleccionadas (iteración), hasta que ya no haya mejoría en la solución planteada. Cuando hacemos uso del Método simplex debemos considerar que existen cuatro casos especiales que podrían presentarse:    

Degeneración Óptimos alternativos Solución no acotada Solución no factible Solución Degenerada Este caso se presenta cuando en el método simplex, durante el proceso de ir mejorando las soluciones seleccionadas (iteración), hay un empate

en la variable de salida, que se puede romper arbitrariamente. Si esto sucede, en la siguiente iteración al menos una variable básica será 0, por lo que se dice que la nueva solución está degenerada.

EJEMPLO:  

Maximizar  Sujeto a:

V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

-3

-9

0

0

0

S1

0

1

4

1

0

8

S2

0

1

2

0

1

4

V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

-3/4

0

9/4

0

18

X2

0

1/4

1

1/4

0

2

S2

0

1/2

0

-1/2

1

0

V. Básica

Z

X1

X2

S1

S2

Solución

 

 

Z

1

0

0

3/2

3/2

18

X2

0

0

1

1/2

-1/2

2

S2

0

1

0

-1

2

0

 

Óptimos alternativos Se presenta cuando la recta de la ecuación función objetivo es paralela al menos a una restricción que cumpla como una ecuación de la mejor solución o solución óptima.

Ejemplo

Maximizar 

 

Sujeto a:

    V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

-4

-14

0

0

0

S1

0

2

7

1

0

21

S2

0

7

2

0

1

21

V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

0

0

2

0

42

X2

0

2/7

1

1/7

0

3

S2

0

4/7

0

-5/7

1

15

 

 

 

Nota: Si existe un cero en el primer renglón significa que hay soluciones óptimas múltiples.   V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

0

0

2

0

42

X2

0

0

1

7/45

-2/45

7/3

X1

0

1

0

-2/45

7/45

7/3

 

Solución no acotada Sucede cuando al menos una variable puede incrementarse indefinidamente, sin estar violando alguna restricción. En este caso donde no está acotado el área de soluciones indica que el modelo ha sido mal construido, pudiendo estar mal definidas las restricciones en cuanto a su valor o que alguna de ellas no esté siendo considerada en la construcción del modelo.

Maximizar   

Sujeto a:  

  V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

-2

-1

0

0

0

S1

0

1

-1

1

0

10

S2

0

2

-1

0

1

40

V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

0

-3

2

0

20

X1

0

1

-1

1

0

10

S2

0

0

1

-2

1

20

V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

0

0

-4

3

80

X1

0

1

0

-1

1

30

S2

0

0

1

-2

1

20

 

 

 

No existe acotación para la variable. (Solución Optima no Acotada). Acotada no tiene límite. Solución no factible

Se presenta cuando no se cumple con al menos una restricción, lo que indicaría que el modelo no ha sido construido correctamente. De acuerdo con Taha (2012), esta situación no ocurre si todas las restricciones son del tipo ≤ con lados derechos no negativos, porque las holguras proporcionan una solución factible obvia. Para otros tipos de restricciones, se utilizan variables artificiales penalizadas para iniciar la solución. Si al menos una variable artificial es positiva en la iteración óptima, entonces el modelo de programación lineal no tiene una solución factible.

Maximizar   

Sujeto a:

 

 

V. Básica

Z

X1

X2

S1

S2

S3

R1

Solución

Z

1

-4

-6

0

0

0

-M

0

S1

0

3

4

1

0

0

0

12

R1

0

3

5

0

-1

0

1

30

S3

0

0

1

0

0

1

0

10

V. Básica

Z

X1

X2

S1

S2

S3

R1

Solución

Z

1

-4+3M

-6+5M

0

-M

0

0

30M

S1

0

3

4

1

0

0

0

12

R1

0

3

5

0

-1

0

1

30

S3

0

0

1

0

0

1

0

10

  V. Básica

Z

X1

X2

S1

S2

S3

R1

Solución

1

1/ 2-3/4M

0

3/2-5/4M

-M

0

0

18+15m

S1

0

3/ 4

1

1/ 4

0

0

0

3

R1

0

-3/4

0

-5/4

-1

0

1

15

S3

0

-3/4

0

-1/4

0

1

0

7

Z

  No existen soluciones factibles del problema. No existe ninguna combinación de valores de X 1 y X2 que satisfagan todas las restricciones.

Cuadro comparativo Simplex

Metodo grafico

Definición • Toma en cuenta sólo las soluciones factibles delimitadas por los vértices del área de soluciones o región factible. • En caso de que la primera solución factible no sea la óptima, inicia el proceso de iteración (repetición de pasos en búsqueda de la solución óptima). • Cuando sea posible, debemos considerar el origen (0,0) como la primera solución factible o la inicial. • Si existe la necesidad de iniciar el proceso de iteración, la siguiente solución factible a ser evaluada debe de ser la adyacente al vértice de solución que está siendo evaluada. • Analiza la tasa de crecimiento que habría al moverse de un vértice de solución factible a otro. Un valor positivo significa que la solución adyacente es mejor que la actual. Un valor negativo significa que la solución adyacente es peor a la actual.

Definición Uno de los métodos de solución para los modelos de programación lineal es el método gráfico, el cual consiste en la representación gráfica de las restricciones y función objetivo definidos en el tema anterior. Para poder hacer uso del método gráfico, es necesario que el modelo de programación lineal sea únicamente de dos variables, cuya función objetivo sea de minimizar o maximizar. De acuerdo con Taha (2012), el método gráfico consta de dos pasos: 1. Determinar el espacio de soluciones factibles. 2. Determinar la solución óptima de entre todos los puntos localizados en el espacio de soluciones.

Ventajas: • Permite reducir los sistemas de ecuaciones hasta en dos variables. • Es sencillo de realizar. • Los resultados obtenidos son confiables. • Utilizando técnicas de despejes podemos aplicarlos a cualquier sistema de ecuaciones. • Es más rápido que el método de reducción y sustitución

Ventajas: • Es un método heurístico. Se basa en consideraciones geométricas y no requiere el uso de derivadas de la función objetivo. • Es de gran eficacia incluso para ajustar gran número de parámetros. • Es fácil de implementar y usar, y sin embargo tiene una alta eficacia. • Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales fácilmente. Desventajas: Desventajas: • Converge más lentamente que otros métodos • Puede estar sometido a errores de escala de la gráfica. pues requiere mayor número de iteraciones • En ocasiones las gráficas de las funciones no son • Requiere muchas repeticiones de acuerdo con sencillas de realizar. la dimensión del problema, el procedimiento del • Podemos cometer errores de aproximación al gráfico es sencillo momento de observar • Se necesitan conocimientos avanzados de • Podemos cometer errores de aproximación por el programación lineal, el método gráfico solo trasado. requiere de conocimientos generales de • El construir la gráfica no siembre es favorable. programación lineal • Es largo y fácil de equivocarse, el gráfico es mucho más corto

Conclusión: Ambos métodos son correctos y pueden ser usados para resolver diferentes modelos matemáticos, sin embargo, considero que el mejor es el método grafico ya que es mas sencillo de usar y requiere menos conocimientos técnicos.