lunes, 13 de agosto de 2018

REPÚBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN
INSTITUTO UNIVERSITARIO POLITÉCNICO "SANTIAGO MARIÑO"
Índice

  • Introducción

  • Definición del Método Simplex

  • Matriz Identidad (Ejemplo de Cálculo)
  • Formulación del Método Simplex
  • Proceso de Cálculo
  • Ejemplo de Maximizar
  • Ejemplo de Minimizar
  • Conclusiones
  • Bibliografía

Introducción

Desarrollado por George Bernard Dantzig (8 de Noviembre de 1944 - 13 de Mayo de 2005) en 1947.Este método se basa en la conversión del problema con restricciones con desigualdades en un problema cuyas restricciones son ecuaciones lineales. Es un método matricial. El Método Simplex, como parte de la programación lineal, es un método analítico capaz de resolver aquellos modelos que se vuelven complejos en el uso del método gráfico por el numero de variables empleadas. El método simplex sirve para resolver problemas de programación lineal. El primer problema practico que se resolvió con este método fue uno de nutrición.





Definición del Método Simplex

El método Simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono o de las aristas del poliedro, si el número de variables es mayor. Cómo el número de vértices y de aristas es finito, siempre se podrá encontrar la solución. Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad “≤” y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo “≥” o “=” habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.


Matriz Identidad 
(Ejemplo de Cálculo)

Una matriz puede definirse como una ordenación rectangular de elementos o (listado finito de elementos), los cuales pueden ser números reales o complejos, dispuestos en forma de filas y de columnas. La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo numero de columnas como de filas) de orden n que tiene todos los elementos diagonales iguales a (1) y todos los demás componentes iguales a (0), se denomina matriz idéntica o identidad de orden n, y se denota por: 

     
La importancia de la teoría de matrices en el Método Simplex es fundamental, dado que el algoritmo se basa en dicha teoría para la resolución de sus problemas.

 Una Matriz Identidad es una matriz cuadrada que tiene solamente 1s en la diagonal principal, y 0s por todas partes.Por ejemplo, las matrices de identidad 2x2 y 3x3 se muestran a continuación.
Matriz de 2x2


Matriz de 3x3


Estas son llamadas matrices identidad porque, cuando las multiplica con una matriz compatible, se obtiene la misma matriz.


Ejemplo




Formulación del Método Simplex



Usar un modelo matemático para la resolución de problemas es la base de la programación lineal recordando que modelo se refiere a la representación simplificada de la realidad; los modelos matemáticos en específico hacen uso de símbolos matemáticos y presentan elementos como: 
  • Variables: Representan las incógnitas del problema.
  • Restricciones: Se contemplan las limitaciones a las que se encuentra sujeta la resolución del problema considerando la escasez de recursos en tiempo y espacio. 
  • Función objetivo: Representa la meta que se pretende alcanzar y en la cual se basan las decisiones principales para maximizar los beneficios o bien para minimizar los costos (considere que en la programación lineal el calificativo “lineal” hace referencia que las ecuaciones usadas en el modelo serán siempre de primer grado, es decir, sin exponentes). 
Sin embargo, los resultados no siempre deberán tomarse literalmente pues es deber del interprete considerar que hay factores externos como el cambio climático, la competencia, las condiciones de seguridad, entre otros; por lo tanto los resultados del modelo deberán ser usados como una base para el tomador de decisiones con el objetivo de conseguir los mejores resultados en diferentes situaciones. Por lo tanto, es importante señalar cuestiones que debe considerar la persona encargada del modelado.
  • Entre más sencillo sea el modelo, mejor será el resultado.Un modelo complejo no siempre será la mejor solución.              
  • El modelo debe ser validado antes de ser implementado para saber si representa la situación real y en caso de no ser así habrá que hacer los ajustes correspondientes.                   
  • Si se hacen las cosas de manera apresurada, el modelo saldrá mal. Debe hacerse un minucioso análisis de la información recabada para identificar que en verdad será útil para el modelo.
  • Los modelos son un herramienta más el tomador de decisiones tendrá siempre la última palabra. 
Proceso de Cálculo

La empresa el Saman, dedicada a la fabricación de muebles, ha ampliado su producción en dos líneas más.Por lo tanto actualmente fabrica mesas, sillas, camas y bibliotecas.



  • Variables:
X1 = Cantidad de mesas a producir
X2 = Cantidad de sillas a producir
X3 = Cantidad de camas a producir
X4 = Cantidad de bibliotecas a producir

Cada variable es por unidades.

  • Restricciones:
2X1 + 1X2 + 1X3 + 2X4 <= 24              

2X1 + 2X2 + 1X3 <= 20                    

2X3 + 2X4 <= 20                           

4X4 <= 16 

  • Función Objetivo:
Z minimizar ó maximizar  = 20000X1 + 20000X2 +20000X3 + 20000X4


Ejemplo de Maximizar

Maximizar Z = 16X1+ 15X2

Sujeto a:

40X1 + 31X2 <= 124 …(1)
-X1 + X2 <= 1 …(2)
X1 <= 3 …(3)
X1; X2 >= 0

Nuevos Datos:

Z = 16X1 + 15X2 + 0S1 + 0S2 + 0S3

40X1 + 31X2 + S1 = 124 …(1)
-X1 + X2 + S2 = 1 …(2)
X1 + S3 = 3 …(3)


Llenamos nuestra tabla con los coeficientes de Z y las restricciones.


Ya que vamos a maximizar obtendremos, de la columna Z, el coeficiente más negativo en este caso será el -16 y por lo tanto la fila x1 será la columna de pivote y esta reemplazara a la fila pivote que saldrá.


Ahora obtendremos la fila de pivote:

Tomaremos el menor valor  obtenido en la columna de Relación.

En este caso el 3; por lo tanto S3 será la fila que salga y obtenemos el elemento pivote el cual seria 1(Sombreado con color rojo en la anterior tabla tabla).

Ahora hallaremos la nueva fila:
Nueva fila pivote = Fila pivote actual / elemento pivote
Fila pivote actual = [0, 1, 0, 0, 0, 1, 3]
Elemento pivote = 1

Cálculos nueva Fila (S3)
0/1 = 0
1/1 = 1
0/1 = 0
0/1 = 0
0/1 = 0
1/1 = 1
3/1 = 3

Fila pivote obtenida = [0, 1, 0, 0, 0, 1, 3]

Ahora hallar las filas Z, S1, S2, X1
Hallando Z:

1-(-16 * 0) = 1
-16-(-16 * 1) = 0
-15-(-16 * 0) = -15
0-(-16 * 0) = 0
0-(-16 * 0) = 0
0-(-16 * 1) = 16
0-(-16 * 3) = 48

Fila obtenida (Z)  = [1, 0, -15, 0, 0, 16, 48]

Coeficiente: 40

0 - (40.0 * 0) = 0.0
40 - (40.0 * 1) = 0.0
31 - (40.0 * 0) = 31.0
1 - (40.0 * 0) = 1.0
0 - (40.0 * 0) = 0.0
0 - (40.0 * 1) = -40.0
124 - (40.0 * 3) = 4.0

Cálculos para S2
Coeficiente: -1

0 - (-1.0 * 0) = 0.0
-1 - (-1.0 * 1) = 0.0
1 - (-1.0 * 0) = 1.0
0 - (-1.0 * 0) = 0.0
1 - (-1.0 * 0) = 1.0
0 - (-1.0 * 1) = 1.0

1 - (-1.0 * 3) = 4.0


Hallando fila que reemplazara


Cálculos nueva Fila
Punto pivote: 31

0.0/31.0 = 0.0
0.0/31.0 = 0.0
31.0/31.0 = 1.0
1.0/31.0 = 0.03
0.0/31.0 = 0.0
-40.0/31.0 = -1.29
4.0/31.0 = 0.13

Cálculos para hallar Z
Coeficiente: -15

1.0 - (-15.0 * 0.0) = 1.0
0.0 - (-15.0 * 0.0) = 0.0
-15.0 - (-15.0 * 1.0) = 0.0
0.0 - (-15.0 * 0.032) = 0.48
0.0 - (-15.0 * 0.0) = 0.0
16.0 - (-15.0 * -1.29) = -3.35
48.0 - (-15.0 * 0.13) = 49.94

Cálculos para hallar S2
Coeficiente: 1

0 - (1 * 0) = 0
0 - (1 * 0) = 0
1 - (1 * 1) = 0
0 - (1 * 0.03) = -0.03
1 - (1 * 0) = 1
1 - (1 * -1.29) = 2.29
4 - (1 * 0.13) = 3.87

Cálculos para hallar X1
Coeficiente: 0

0 - (0 * 0 ) = 0
1 - (0 * 0 ) = 1
0 - (0 * 1 ) = 0
0 - (0 * 0.03 ) = 0.0
0 - (0 * 0 ) = 0
1 - (0 * -1.29 ) = 1.0
3 - (0 * 0.13 ) = 3.0

Llenando una nueva tabla con los valores obtenidos.



Hallando fila que será reemplazada.



Cálculos nueva Fila (S2):
Punto pivote 2.29

0/2.29 = 0.0
0/2.29 = 0.0
0/2.29 = 0.0
-0.03/2.29 = -0.01
1/2.29 = 0.44
2.29/2.29 = 1.0
3.87/2.29 = 1.69

Cálculos para hallar Z:
Coeficiente: -3.35

1 - (-3.35 * 0.0) = 1.0
0 - (-3.35 * 0.0) = 0.0
0 - (-3.35 * 0.0) = 0.0
0.48 - (-3.35 * -0.0131004366812) = 0.44
0 - (-3.35 * 0.436681222707) = 1.46
-3.35 - (-3.35 * 1.0) = 0.0
49.94 - (-3.35 * 1.68995633188) = 55.61

Cálculos para hallar X2:

0 - (-1.29 * 0.0) = 0.0
0 - (-1.29 * 0.0) = 0.0
1 - (-1.29 * 0.0) = 1.0
0.03 - (-1.29 * -0.01) = 0.01
0 - (-1.29 * 0.44) = 0.57
-1.29 - (-1.29 * 1.0) = 0.0
0.13 - (-1.29 * 1.69) = 2.31

Cálculos para hallar X1:

0 - (1 * 0.0) = 0.0
1 - (1 * 0.0) = 1.0
0 - (1 * 0.0) = 0.0
0 - (1 * -0.01) = 0.01
0 - (1 * 0.44) = -0.44
1 - (1 * 1.0) = 0.0
3 - (1 * 1.69) = 1.31


Respuesta:
Z = 55.61
X2 = 2.31
X1 = 1.31
S3 = 1.69


Ejemplo de Minimizar

Minimizar Z = 5X1-4X2+6X3+8X4

Sujeto a:

X1 + 2X2 + 2X3 + 4X4 <= 40 …(1)
2X1 - X2 + X3 + 2X4 <= 8 …(2)
4X1 - 2X2 + X3 - X4 <= 10 …(3)
X1; X2; X3; X4 >= 0

Nuevos Datos:

Z = 5X1 - 4X2 + 6X3 - 8X4 + 0S1 + 0S2 + 0S3
Z - 5X1 + 4X2 - 6X3 + 8X4 - 0S1 - 0S2 - 0S3 = 0

X1 + 2X2 + 2X3 + 4X4 + S1 = 40 …(1)
2X1 - X2 + X3 + 2X4 + S2 = 8 …(2)
4X1 - 2X2 + X3 - X4 + S3 = 10 …(3)
X1; X2; X3; X4 >= 0
S1; S2; S3 >= 0

Llenamos nuestra tabla con los coeficientes de Z y las restricciones.


Ahora obtendremos la fila de pivote:


Cálculos nueva Fila
Punto pivote: 2

Nueva fila pivote = Fila pivote actual / elemento pivote

0.0/2 = 0.0
2.0/2 = 1.0
-1.0/2 = -0.5
1.0/2 = 0.5
2.0/2 = 1.0
0.0/2 = 0.0
1.0/2 = 0.5
0.0/2 = 0.0
8.0/2 = 4.0

Cálculos Z
Coeficiente: 8

1 - (8 * 0.0 ) = 1.0
-5 - (8 * 1.0 ) = -13.0
4 - (8 * -0.5 ) = 8.0
-6 - (8 * 0.5 ) = -10.0
8 - (8 * 1.0 ) = 0.0
0 - (8 * 0.0 ) = 0.0
0 - (8 * 0.5 ) = -4.0
0 - (8 * 0.0 ) = 0.0
0 - (8 * 4.0 ) = -32.0

Cálculos S1
Coeficiente: 4

0 - (4 * 0.0 ) = 0.0
1 - (4 * 1.0 ) = -3.0
2 - (4 * -0.5 ) = 4.0
2 - (4 * 0.5 ) = 0.0
4 - (4 * 1.0 ) = 0.0
1 - (4 * 0.0 ) = 1.0
0 - (4 * 0.5 ) = -2.0
0 - (4 * 0.0 ) = 0.0
40 - (4 * 4.0 ) = 24.0

Cálculos S3
Coeficiente -1

0 - (-1 * 0.0 ) = 0.0
4 - (-1 * 1.0 ) = 5.0
-2 - (-1 * -0.5 ) = -2.5
1 - (-1 * 0.5 ) = 1.5
-1 - (-1 * 1.0 ) = 0.0
0 - (-1 * 0.0 ) = 0.0
0 - (-1 * 0.5 ) = 0.5
1 - (-1 * 0.0 ) = 1.0

10 - (-1 * 4.0 ) = 14.0

Nueva tabla con los valores obtenidos:


Encontrando la fila que va a salir:


Cálculos nueva Fila
Punto pivote: 4

Nueva fila pivote = Fila pivote actual / elemento pivote

0.0/4 = 0.0
-3.0/4 = -0.75
4.0/4 = 1.0
0.0/4 = 0.0
0.0/4 = 0.0
1.0/4 = 0.25
-2.0/4 = -0.5
0.0/4 = 0.0
24.0/4 = 6.0

Cálculos Z
Coeficiente: 8
1 - (8 * 0.0) = 1.0
-13 - (8 * -0.75) = -7.0
8 - (8 * 1.0) = 0.0
-10 - (8 * 0.0) = -10.0
0 - (8 * 0.0) = 0.0
0 - (8 * 0.25) = -2.0
-4 - (8 * -0.5) = 0.0
0 - (8 * 0.0) = 0.0
-32 - (8 * 6.0) = -80.0

Cálculos S4
Coeficiente: -0.5
0 - (-0.5 * 0.0) = 0.0
1 - (-0.5 * -0.75) = 0.625
-0.5 - (-0.5 * 1.0) = 0.0
0.5 - (-0.5 * 0.0) = 0.5
1 - (-0.5 * 0.0) = 1.0
0 - (-0.5 * 0.25) = 0.125
0.5 - (-0.5 * -0.5) = 0.25
0 - (-0.5 * 0.0) = 0.0
4 - (-0.5 * 6.0) = 7.0

Cálculos S3
Coeficiente -2.5
0 - (-2.5 * 0.0) = 0.0
5 - (-2.5 * -0.75) = 3.125
-2.5 - (-2.5 * 1.0) = 0.0
1.5 - (-2.5 * 0.0) = 1.5
0 - (-2.5 * 0.0) = 0.0
0 - (-2.5 * 0.25) = 0.625
0.5 - (-2.5 * -0.5) = -0.75
1 - (-2.5 * 0.0) = 1.0
14 - (-2.5 * 6.0) = 29.0


Respuesta:

Z = -80
X2 =  6
X4 =  7
S3 = 29



Conclusiones


  • El método simplex, emplea básicamente, la estrategia de resolver los problemas de programación lineal por medio de sistemas de ecuaciones lineales simultaneas siempre que se tenga una solución factible.
  • El método simplex es un algoritmo eficiente y confiable para resolver problemas de programación lineal. También proporciona la base para llevar a cabo, en forma muy eficiente, las distintas etapas del análisis óptimo.
  • Aunque tiene una interpretación geométrica útil, el método símplex es un procedimiento algebraico. En cada iteración se mueve de la solución básica factible actual a una adyacente mejor eligiendo tanto la variable básica entrante como la que sale y después usando la eliminación de Gauss para resolver el sistema de ecuaciones lineales. Cuando la solución actual no tiene una solución básica factible adyacente que sea mejor, la solución actual es óptima y el algoritmo se detiene.
Bibliografía
http://gomoryoperativauan.blogspot.com/2016/05/aplicacion.html

http://www.mty.itesm.mx/dmti/materias/tc3001/lecturas/tc3001-03-intro-simplex.pdf

http://metodosimplexvisemestre.blogspot.com/

http://ri.uaemex.mx/bitstream/handle/20.500.11799/33856/secme-16318.pdf?sequence=1

https://crodzmate3012.files.wordpress.com/2011/01/mate_3012_simplex_max.pdf

https://www.matematicas10.net/2015/12/ejemplos-de-matriz-unidad-o-identidad.html

https://es.wikipedia.org/wiki/Matriz_identidad

https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-simplex/

https://www.ingenieriaindustrialonline.com/herramientas-para-el.../método-simplex/




Alumna: Yeny Casiano 
C.I: 84.586.949
Escuela: 47 Ingeniería de Sistemas 



en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)