Metodo Simplex - Codigo Matlab 5h2g3r
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 3b7i
Overview 3e4r5l
& View Metodo Simplex - Codigo Matlab as PDF for free.
More details w3441
- Words: 1,705
- Pages: 4
Trabajo Final M´etodos Num´ericos, M´etodo Simplex Juli´an Triana, Codigo:1088303755
I. R ESUMEN min(max) f (x) en Rn (1) El “M´etodo Simplex” es un m´etodo algebraico sistem´atico que examina las esquinas, llamadas v´ertices o puntos extremos de un conjunto res- El problema planteado por medio de la ecuatringido de programaci´on lineal en busca de una ci´on 1 es conocido como un problema de optimizaci´on sin restricciones. Un ejemplo com´un soluci´on o´ ptima. consiste en determinar la localizaci´on optima Resumen—The “Simplex Method” is a systematic de n recursos [x1 , x2 , x3 , x4 , ..., xn ] compitiendo algebraic method that examines the corners, called vertices or extreme points of a restricted set of linear entre si y regidos por una ley especifica. Por lo general, muchos de estos recursos no son programming in search of an optimal solution. ilimitados, bajo estas circunstancias, desde el punto de vista matem´atico, se requiere que la mi´ II. I NTRODUCCI ON nimizaci´on de la funci´on objetivo est´e dentro del n El “M´etodo Simplex” muestra la eficacia de este conjunto Ω ⊂ R y posiblemente algunas restricm´etodo en laformulaci´on y soluci´on de diversos ciones de igualdades o desigualdades tengan que problemas de optimizaci´on y dem´as.Este m´etodo ser satisfechas. Los problemas de optimizaci´on permite ver las aplicaciones a las ramas de las formulados con la ecuaci´on 2, se conocen como problemas de optimizaci´on con restricciones y ciencias e´ ingenier´ıa. tiene la siguiente forma: III. O BJETIVOS 1. Definir el analisis n´umerico por medio de la optimizaci´on 2. Mostrar los conceptos b´asicos de programacion 3. Desarrollar el M´etodo Simplex y algunas de sus aplicaciones. 4. Programar por medio de matlab el M´etodo Simplex. IV.
´ ´ A N ALISIS N UMERICO ´ ) (O PTIMIZACI ON
En esta secci´on se busca la soluci´on num´erica del problema de minimizaci´on (maximizaci´on) de funciones en varias variables. La formulaci´on b´asica del problema viene dada por: f : Rn → R, llamada funci´on objetivo.
minimize
f (x)
in Ω (2)
s.a. h1(x)=0; h2(x)=0; . . . hn−2 (x) ≤ 0; hn−1 (x) ≤ c; . . . hn (x) ≤ c; Algunas de las restricciones del problema planteado en la ecuaci´on 2 son de tipo igualdad (hn (x) = 0) o desigualdad (hn (x) ≤ 0) y se caracterizan por tener soluci´on en Ω. Estas condiciones de igualdad o desigualdad (restricciones) son conocidas como funciones de costo que son continuas en Ω.
´ UNIVERSIDAD TECNOLOGICA DE PEREIRA, JUNIO 04 DE 2018
V.
2
´ L INEAL P ROGRAMACI ON
ecuaciones de desigualdad con variables de Este tipo de problemas consiste en optimizar holgura para llevarlas a la forma de restricciones (minimizar o maximizar) una funci´on objetivo e igualdad (ya que el m´etodo camina sobre lineal que satisfacen un conjunto de restricciones las restricciones activas). Se iguala la funci´on objetivo a cero. lineales de igualdad o desigualdad. Formulaci´on del problema: Considere el siguiente problema: Igualar la funf (x) = c1 x1 + c2 x2 + c3 x3 + ... + cn xn (3) ci´on objetivo a cero. La ecuaci´on 3 es la funci´on a minimizar, los coeficientes de costo son c1 , c2 , c3 , ... + cn y las min(f (x)) = z variables de decisi´on son x = x1 , x2 , x3 , ..., xn z = c1 x 1 + c2 x 2 + c3 x 3 + · · · + cn x n (variables que minimizan o maximizan la z − c1 x 1 − c2 x 2 − c3 x 3 − · · · − cn x n = 0 funci´on objetivo). Con restricciones de tipo lineal, en cualquiera de los casos donde la funci´on objetivo no Convertir las restricciones de desigualdad en sea lineal o alguna de las restricciones no condiciones de igualdad sumando una variable sea de tipo lineal, entonces no es posible a cada restricci´on. aplicar los m´etodos para resolver problemas de programaci´on lineal. a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn ≤ b1 a21 x1 + a22 x2 + a23 x3 + · · · + a2n xn ≤ b2 a31 x1 + a32 x2 + a33 x3 + · · · + a3n xn ≤ b3 VI. M E´ TODO S IMPLEX . El M´etodo Simplex es un m´etodo anal´ıtico de . soluci´on de problemas de programaci´on lineal, . capaz de resolver modelos m´as complejos que a x + a x + a x n1 1 n2 2 n3 3 + · · · + ann xn ≤ bn los resueltos mediante el m´etodo gr´afico, sin restricci´on en el n´umero de variables. El M´etodo Simplex es un m´etodo iterativo que permite ir mejorando la soluci´on en cada paso.
a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn + s1 = b1 a21 x1 + a22 x2 + a23 x3 + · · · + a2n xn + s2 = b2 a31 x1 + a32 x2 + a33 x3 + · · · + a3n xn + s3 = b3 . ´ . Util para solucionar el problema de . minimizaci´on o maximizaci´on del problema de programaci´on lineal. Este tipo de problemas an1 x1 + an2 x2 + an3 x3 + · · · + ann xn + sn = bn ocurren cuando la funci´on objetivo y sus restricciones son lineales. Si alguna de las Pivotaje: Se llama pivotaje al conjunto de operaanteriores no es lineal entonces no es posible ciones que transforma un cuadro simplex, con solucionar el problema de programaci´on lineal. una base conocida, en otro cuadro simplex con El m´etodo simplex consiste en encontrar el nueva base. valor de los recursos (variables) para que el valor en la funci´on objetivo sea m´aximo o m´ınimo y cumpla con las restricciones. La Criterio de parada maximizaci´on: Cuando se metodolog´ıa consiste en encontrar la soluci´on pide maximizar el criterio de parada esta dado dentro de la regi´on factible (La regi´on formada cuando en la fila Z(objetivo) no aparece ning´un por las restricciones). Alguno de los puntos valor negativo. formados por las restricciones son candidatos a optimo. La metodolog´ıa consiste en caminar Criterio de parada minimizaci´on: Cuando se por la regi´on factible y evaluar cada uno de los pide minimizar el criterio de parada esta dado candidatos a optimo tanto en la funci´on objetivo cuando en la fila Z(objetivo) no aparece ning´un como en las restricciones. Para implementar valor positivo. el m´etodo simplex es necesario completar las
´ UNIVERSIDAD TECNOLOGICA DE PEREIRA, JUNIO 04 DE 2018
3
Ejemplo 1: Maximizar f (x) = 300x1 + 100x2
Tabla 3. Eliminaci´on Gauss z 1 0 0 0
s.a. 40x1 + 8x2 ≤ 800 10x1 + 5x2 ≤ 320 x2 ≤ 60 x1 , x2 ≥ 0
x1 0 1 0 0
x2 0 0 1 0
s1 25/6 1/24 -1/12 1/12
s2 s3 b 40/3 0 7600 -1/5 0 12 1/3 0 40 -1/3 1 20 Tabla 4. Resultados
Reescribir el problema de maximizaci´on, se debe igualar la funci´on objetivo z a cero y Finalmente, la soluci´on o´ ptima global del convertir las restricciones de desigualdad en problema de maximizaci´on es x = [12; 40], restricciones de igualdad. x1 = 12, x2 = 40. Con un valor m´aximo dentro de la regi´on factible de f (x) = 7600. z − 300x1 − 100x2 = 0 40x1 + 8x2 + s1 = 800 10x1 + 5x2 + s2 = 320 x2 + s3 = 60
Ejemplo 2: Minimizar f (x) = x1 − 2x2 s.a. −x1 + x2 ≤ 2 −x1 + x2 ≤ 6 x1 , x2 ≥ 0
z x1 x2 s 1 1 -300 -100 0 0 40 8 1 0 10 5 0 0 0 1 0 Tabla
s2 s3 b 0 0 0 0 0 800 1 0 320 Los coeficientes de costo de la funci´on 0 1 60 objetivo pasan con signo contrario, convertir las 1. Forma Matricial restricciones de desigualdad en restricciones de igualdad. En la fila de la funci´on objetivo se toma el valor que sea m´as negativo (la columna 2 de la tabla −x1 + x2 + s1 = 2 contiene el valor de -300 el m´as negativo) y −x1 + x2 + s2 = 6 esta columna se llama columna pivote. Luego se dividen los t´erminos de la columna b entre z x1 x2 s 1 s 2 b bi los t´erminos de la columna asi y se toma 1 -1 2 0 0 0 i 0 -1 1 1 0 2 el menor valor positivo y esta se convierte en la 0 -1 2 0 1 6 fila pivote. 1 1 0 -2 0 -4 0 -1 1 1 0 2 0 1 0 -2 1 2 b i/bi 1 0 0 0 -1 -6 40 800 20 0 0 1 -1 1 4 10 320 32 0 1 0 -2 1 2 0 60 no se hace,divisi´on por cero Tabla 5. Forma Matricial Tabla 2. Fila Pivote, Columna Pivote La soluci´on del problema de minimizaci´on es: El siguiente paso es generar la tabla 1 pero x = [2; 4] cambiando la columna por una eliminaci´on de gauss. z 1 0 0 0
x1 0 1 0 0
x2 s1 s2 -40 15/2 0 1/5 1/40 0 3 -1/4 1 1 0 0
s3 0 0 0 1
b 6000 20 120 60
´ UNIVERSIDAD TECNOLOGICA DE PEREIRA, JUNIO 04 DE 2018
C´odigo en Matlab:
4
3. https://www.phpsimplex.com/ejemplo metodo simplex.htm
Fig 1. C´odigo en Matlab VII.
C ONCLUCIONES
1. Se pudo concluir que el m´etodo s´ımplex es un algoritmo eficiente y confiable para resolver problemas de programaci´on l´ıneal. 2. Vimos que el m´etodo s´ımplex es un procedimiento algebraico, en cada iteraci´on se mueve de la soluci´on b´asica factible actual a una adyacente mejor. 3. Se puede decir que el m´etodo simplex es un m´etodo muy pr´actico y de f´acil aplicaci´on, ya que solo trabaja con los coeficientes de la funci´on objetivo y de las restricciones. 4. Se pudo observar el poder que tiene del m´etodo simplex al ser programado en Matlab.
VIII.
B IBLIOGRAFIA
1. Facultad de Ciencias B´asicas, Departamento de Matematicas,UTP 2. https://www.ingenieriaindustrialonline.com/herra mientas-para-el-ingeniero−industrial/investigaci % C3 %B3n-de-operaciones/m %C3 %A9todosimplex/.
I. R ESUMEN min(max) f (x) en Rn (1) El “M´etodo Simplex” es un m´etodo algebraico sistem´atico que examina las esquinas, llamadas v´ertices o puntos extremos de un conjunto res- El problema planteado por medio de la ecuatringido de programaci´on lineal en busca de una ci´on 1 es conocido como un problema de optimizaci´on sin restricciones. Un ejemplo com´un soluci´on o´ ptima. consiste en determinar la localizaci´on optima Resumen—The “Simplex Method” is a systematic de n recursos [x1 , x2 , x3 , x4 , ..., xn ] compitiendo algebraic method that examines the corners, called vertices or extreme points of a restricted set of linear entre si y regidos por una ley especifica. Por lo general, muchos de estos recursos no son programming in search of an optimal solution. ilimitados, bajo estas circunstancias, desde el punto de vista matem´atico, se requiere que la mi´ II. I NTRODUCCI ON nimizaci´on de la funci´on objetivo est´e dentro del n El “M´etodo Simplex” muestra la eficacia de este conjunto Ω ⊂ R y posiblemente algunas restricm´etodo en laformulaci´on y soluci´on de diversos ciones de igualdades o desigualdades tengan que problemas de optimizaci´on y dem´as.Este m´etodo ser satisfechas. Los problemas de optimizaci´on permite ver las aplicaciones a las ramas de las formulados con la ecuaci´on 2, se conocen como problemas de optimizaci´on con restricciones y ciencias e´ ingenier´ıa. tiene la siguiente forma: III. O BJETIVOS 1. Definir el analisis n´umerico por medio de la optimizaci´on 2. Mostrar los conceptos b´asicos de programacion 3. Desarrollar el M´etodo Simplex y algunas de sus aplicaciones. 4. Programar por medio de matlab el M´etodo Simplex. IV.
´ ´ A N ALISIS N UMERICO ´ ) (O PTIMIZACI ON
En esta secci´on se busca la soluci´on num´erica del problema de minimizaci´on (maximizaci´on) de funciones en varias variables. La formulaci´on b´asica del problema viene dada por: f : Rn → R, llamada funci´on objetivo.
minimize
f (x)
in Ω (2)
s.a. h1(x)=0; h2(x)=0; . . . hn−2 (x) ≤ 0; hn−1 (x) ≤ c; . . . hn (x) ≤ c; Algunas de las restricciones del problema planteado en la ecuaci´on 2 son de tipo igualdad (hn (x) = 0) o desigualdad (hn (x) ≤ 0) y se caracterizan por tener soluci´on en Ω. Estas condiciones de igualdad o desigualdad (restricciones) son conocidas como funciones de costo que son continuas en Ω.
´ UNIVERSIDAD TECNOLOGICA DE PEREIRA, JUNIO 04 DE 2018
V.
2
´ L INEAL P ROGRAMACI ON
ecuaciones de desigualdad con variables de Este tipo de problemas consiste en optimizar holgura para llevarlas a la forma de restricciones (minimizar o maximizar) una funci´on objetivo e igualdad (ya que el m´etodo camina sobre lineal que satisfacen un conjunto de restricciones las restricciones activas). Se iguala la funci´on objetivo a cero. lineales de igualdad o desigualdad. Formulaci´on del problema: Considere el siguiente problema: Igualar la funf (x) = c1 x1 + c2 x2 + c3 x3 + ... + cn xn (3) ci´on objetivo a cero. La ecuaci´on 3 es la funci´on a minimizar, los coeficientes de costo son c1 , c2 , c3 , ... + cn y las min(f (x)) = z variables de decisi´on son x = x1 , x2 , x3 , ..., xn z = c1 x 1 + c2 x 2 + c3 x 3 + · · · + cn x n (variables que minimizan o maximizan la z − c1 x 1 − c2 x 2 − c3 x 3 − · · · − cn x n = 0 funci´on objetivo). Con restricciones de tipo lineal, en cualquiera de los casos donde la funci´on objetivo no Convertir las restricciones de desigualdad en sea lineal o alguna de las restricciones no condiciones de igualdad sumando una variable sea de tipo lineal, entonces no es posible a cada restricci´on. aplicar los m´etodos para resolver problemas de programaci´on lineal. a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn ≤ b1 a21 x1 + a22 x2 + a23 x3 + · · · + a2n xn ≤ b2 a31 x1 + a32 x2 + a33 x3 + · · · + a3n xn ≤ b3 VI. M E´ TODO S IMPLEX . El M´etodo Simplex es un m´etodo anal´ıtico de . soluci´on de problemas de programaci´on lineal, . capaz de resolver modelos m´as complejos que a x + a x + a x n1 1 n2 2 n3 3 + · · · + ann xn ≤ bn los resueltos mediante el m´etodo gr´afico, sin restricci´on en el n´umero de variables. El M´etodo Simplex es un m´etodo iterativo que permite ir mejorando la soluci´on en cada paso.
a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn + s1 = b1 a21 x1 + a22 x2 + a23 x3 + · · · + a2n xn + s2 = b2 a31 x1 + a32 x2 + a33 x3 + · · · + a3n xn + s3 = b3 . ´ . Util para solucionar el problema de . minimizaci´on o maximizaci´on del problema de programaci´on lineal. Este tipo de problemas an1 x1 + an2 x2 + an3 x3 + · · · + ann xn + sn = bn ocurren cuando la funci´on objetivo y sus restricciones son lineales. Si alguna de las Pivotaje: Se llama pivotaje al conjunto de operaanteriores no es lineal entonces no es posible ciones que transforma un cuadro simplex, con solucionar el problema de programaci´on lineal. una base conocida, en otro cuadro simplex con El m´etodo simplex consiste en encontrar el nueva base. valor de los recursos (variables) para que el valor en la funci´on objetivo sea m´aximo o m´ınimo y cumpla con las restricciones. La Criterio de parada maximizaci´on: Cuando se metodolog´ıa consiste en encontrar la soluci´on pide maximizar el criterio de parada esta dado dentro de la regi´on factible (La regi´on formada cuando en la fila Z(objetivo) no aparece ning´un por las restricciones). Alguno de los puntos valor negativo. formados por las restricciones son candidatos a optimo. La metodolog´ıa consiste en caminar Criterio de parada minimizaci´on: Cuando se por la regi´on factible y evaluar cada uno de los pide minimizar el criterio de parada esta dado candidatos a optimo tanto en la funci´on objetivo cuando en la fila Z(objetivo) no aparece ning´un como en las restricciones. Para implementar valor positivo. el m´etodo simplex es necesario completar las
´ UNIVERSIDAD TECNOLOGICA DE PEREIRA, JUNIO 04 DE 2018
3
Ejemplo 1: Maximizar f (x) = 300x1 + 100x2
Tabla 3. Eliminaci´on Gauss z 1 0 0 0
s.a. 40x1 + 8x2 ≤ 800 10x1 + 5x2 ≤ 320 x2 ≤ 60 x1 , x2 ≥ 0
x1 0 1 0 0
x2 0 0 1 0
s1 25/6 1/24 -1/12 1/12
s2 s3 b 40/3 0 7600 -1/5 0 12 1/3 0 40 -1/3 1 20 Tabla 4. Resultados
Reescribir el problema de maximizaci´on, se debe igualar la funci´on objetivo z a cero y Finalmente, la soluci´on o´ ptima global del convertir las restricciones de desigualdad en problema de maximizaci´on es x = [12; 40], restricciones de igualdad. x1 = 12, x2 = 40. Con un valor m´aximo dentro de la regi´on factible de f (x) = 7600. z − 300x1 − 100x2 = 0 40x1 + 8x2 + s1 = 800 10x1 + 5x2 + s2 = 320 x2 + s3 = 60
Ejemplo 2: Minimizar f (x) = x1 − 2x2 s.a. −x1 + x2 ≤ 2 −x1 + x2 ≤ 6 x1 , x2 ≥ 0
z x1 x2 s 1 1 -300 -100 0 0 40 8 1 0 10 5 0 0 0 1 0 Tabla
s2 s3 b 0 0 0 0 0 800 1 0 320 Los coeficientes de costo de la funci´on 0 1 60 objetivo pasan con signo contrario, convertir las 1. Forma Matricial restricciones de desigualdad en restricciones de igualdad. En la fila de la funci´on objetivo se toma el valor que sea m´as negativo (la columna 2 de la tabla −x1 + x2 + s1 = 2 contiene el valor de -300 el m´as negativo) y −x1 + x2 + s2 = 6 esta columna se llama columna pivote. Luego se dividen los t´erminos de la columna b entre z x1 x2 s 1 s 2 b bi los t´erminos de la columna asi y se toma 1 -1 2 0 0 0 i 0 -1 1 1 0 2 el menor valor positivo y esta se convierte en la 0 -1 2 0 1 6 fila pivote. 1 1 0 -2 0 -4 0 -1 1 1 0 2 0 1 0 -2 1 2 b i/bi 1 0 0 0 -1 -6 40 800 20 0 0 1 -1 1 4 10 320 32 0 1 0 -2 1 2 0 60 no se hace,divisi´on por cero Tabla 5. Forma Matricial Tabla 2. Fila Pivote, Columna Pivote La soluci´on del problema de minimizaci´on es: El siguiente paso es generar la tabla 1 pero x = [2; 4] cambiando la columna por una eliminaci´on de gauss. z 1 0 0 0
x1 0 1 0 0
x2 s1 s2 -40 15/2 0 1/5 1/40 0 3 -1/4 1 1 0 0
s3 0 0 0 1
b 6000 20 120 60
´ UNIVERSIDAD TECNOLOGICA DE PEREIRA, JUNIO 04 DE 2018
C´odigo en Matlab:
4
3. https://www.phpsimplex.com/ejemplo metodo simplex.htm
Fig 1. C´odigo en Matlab VII.
C ONCLUCIONES
1. Se pudo concluir que el m´etodo s´ımplex es un algoritmo eficiente y confiable para resolver problemas de programaci´on l´ıneal. 2. Vimos que el m´etodo s´ımplex es un procedimiento algebraico, en cada iteraci´on se mueve de la soluci´on b´asica factible actual a una adyacente mejor. 3. Se puede decir que el m´etodo simplex es un m´etodo muy pr´actico y de f´acil aplicaci´on, ya que solo trabaja con los coeficientes de la funci´on objetivo y de las restricciones. 4. Se pudo observar el poder que tiene del m´etodo simplex al ser programado en Matlab.
VIII.
B IBLIOGRAFIA
1. Facultad de Ciencias B´asicas, Departamento de Matematicas,UTP 2. https://www.ingenieriaindustrialonline.com/herra mientas-para-el-ingeniero−industrial/investigaci % C3 %B3n-de-operaciones/m %C3 %A9todosimplex/.
Related Documents 3m3m1z
Metodo Simplex - Codigo Matlab 5h2g3r
August 2020 0
Metodo Simplex Con Matlab 6i2va
August 2020 0
Metodo Simplex 131f6n
May 2023 0
Metodo Simplex 131f6n
December 2022 0
Metodo Simplex. x2v5i
May 2020 5