tu77t6tr
Páginas: 20 (4861 palabras)
Publicado: 24 de enero de 2015
CAPÍTULO 4. EL MÉTODO DEL
SIMPLEX
4.1.
Introducción a los problemas de P.L. ............................................ 2
4.2.
Caracterización de los problemas de P.L. ...................................... 2
4.3.
El algoritmo del Simplex. ................................................................. 7
4.3.1.
4.3.2.
4.3.3.
4.3.4.
4.4.
Costes reducidos y test deoptimalidad. ........................................................... 7
Regla de entrada de la Base.............................................................................. 9
Regla de salida de la Base. ............................................................................... 9
Resumen del algoritmo del Simplex............................................................... 11
ElMétodo del Simplex en forma de Tableau. ............................. 13
EJEMPLO 4.1. Aplicación del método Simplex en forma de «tableau»................ 15
4.5. Determinación de una solución básica factible inicial: el método
de la M grande y el de las 2 fases. ............................................................ 21
4.5.1. El método de eliminación (o de la «M grande»)............................................ 22
EJEMPLO 4.2. Aplicación del método de eliminación (o de la «M grande»)....... 23
4.5.2. El método de las dos fases.............................................................................. 28
EJEMPLO 4.3. Aplicación del método de las dos fases......................................... 29
4.6.
El método Simplexrevisado........................................................... 35
EJEMPLO 4.4. Aplicación del método del Simplex revisado. .............................. 38
CAPÍTULO 4. EL MÉTODO DEL
SIMPLEX
4.1. Introducción a los problemas de P.L.
4.2. Caracterización de los problemas de P.L.
El método más conocido y habitual para resolver problemas de P.L. es el método
del Simplex debido a Dantzig 1 . Antes de desarrollar este método espreciso enunciar dos
teoremas que no probaremos, aunque en parte vimos como se cumplían en algunos
análisis gráficos del capítulo anterior.
1. El conjunto de posibles soluciones o conjunto factible de cualquier problema de
P.L. puede representarse mediante un poliedro convexo.
2. Si un P.L. tiene una solución óptima y finita, ésta estará en un vértice del
poliedro convexo que representa alproblema de P.L.
La expresión general de un P.L. es:
Max( z ) c1 x1 c2 x2 ... cn xn
a11 x1 a12 x2 ... a1n xn d b1
#
am1 x1 am 2 x2 ... amn xn d bm
x j t 0
Siendo las matrices:
x
ª x1 º
«x »
« 2»
« #»
« »
«¬ xn »¼
c
ª c1 º
«c »
« 2»
« #»
« »
«¬ cn »¼
ª a11 " a1n
« a "a
21
2n
A «
« #
#
«
«¬ am1 amn
º
»
»
»
»
»¼
b
ª b1 º
«b»
« 2»
« #»
« »
«¬ bm »¼
De todo lo anterior se deduce que, puesto que el número de vértices de cualquier
poliedro factible es finito, el número de posibles soluciones de un P.L. también es finito.
Además, sugiere un posible algoritmo para obtener la solución óptima. Consistiría en
calcular el valor de la función objetivo en cada uno de los vértices del conjunto factible
1
Vid.Dantzig (1963).
y escoger el mejor. Para ilustrar esta idea empezaremos planteando un problema de P.L.
en su forma canónica2 . A continuación ilustramos esta idea mediante un ejemplo.
n
Max( z)
¦c x
j
j
j 1
sujeto a:
n
d bi
i ^1,..., m`
xj t 0
j ^1,..., n`
¦a x
ij
j
j 1
añadiendo variables de holgura a cada una de las restricciones se obtendríala
formulación equivalente:
n
Max( z)
¦c x
j
j
j 1
sujeto a:
n
¦a x
ij
j
si
i ^1,..., m`
bi
j 1
xj t 0
j ^1,..., n`
si t 0
i ^1,..., m`
El número de vértices del conjunto factible del problema es:
§m n·
¨
¸
© m ¹
m n !
m ! m n m !
[1]
La cantidad m + n refleja el número de variables originales (n) más...
SIMPLEX
4.1.
Introducción a los problemas de P.L. ............................................ 2
4.2.
Caracterización de los problemas de P.L. ...................................... 2
4.3.
El algoritmo del Simplex. ................................................................. 7
4.3.1.
4.3.2.
4.3.3.
4.3.4.
4.4.
Costes reducidos y test deoptimalidad. ........................................................... 7
Regla de entrada de la Base.............................................................................. 9
Regla de salida de la Base. ............................................................................... 9
Resumen del algoritmo del Simplex............................................................... 11
ElMétodo del Simplex en forma de Tableau. ............................. 13
EJEMPLO 4.1. Aplicación del método Simplex en forma de «tableau»................ 15
4.5. Determinación de una solución básica factible inicial: el método
de la M grande y el de las 2 fases. ............................................................ 21
4.5.1. El método de eliminación (o de la «M grande»)............................................ 22
EJEMPLO 4.2. Aplicación del método de eliminación (o de la «M grande»)....... 23
4.5.2. El método de las dos fases.............................................................................. 28
EJEMPLO 4.3. Aplicación del método de las dos fases......................................... 29
4.6.
El método Simplexrevisado........................................................... 35
EJEMPLO 4.4. Aplicación del método del Simplex revisado. .............................. 38
CAPÍTULO 4. EL MÉTODO DEL
SIMPLEX
4.1. Introducción a los problemas de P.L.
4.2. Caracterización de los problemas de P.L.
El método más conocido y habitual para resolver problemas de P.L. es el método
del Simplex debido a Dantzig 1 . Antes de desarrollar este método espreciso enunciar dos
teoremas que no probaremos, aunque en parte vimos como se cumplían en algunos
análisis gráficos del capítulo anterior.
1. El conjunto de posibles soluciones o conjunto factible de cualquier problema de
P.L. puede representarse mediante un poliedro convexo.
2. Si un P.L. tiene una solución óptima y finita, ésta estará en un vértice del
poliedro convexo que representa alproblema de P.L.
La expresión general de un P.L. es:
Max( z ) c1 x1 c2 x2 ... cn xn
a11 x1 a12 x2 ... a1n xn d b1
#
am1 x1 am 2 x2 ... amn xn d bm
x j t 0
Siendo las matrices:
x
ª x1 º
«x »
« 2»
« #»
« »
«¬ xn »¼
c
ª c1 º
«c »
« 2»
« #»
« »
«¬ cn »¼
ª a11 " a1n
« a "a
21
2n
A «
« #
#
«
«¬ am1 amn
º
»
»
»
»
»¼
b
ª b1 º
«b»
« 2»
« #»
« »
«¬ bm »¼
De todo lo anterior se deduce que, puesto que el número de vértices de cualquier
poliedro factible es finito, el número de posibles soluciones de un P.L. también es finito.
Además, sugiere un posible algoritmo para obtener la solución óptima. Consistiría en
calcular el valor de la función objetivo en cada uno de los vértices del conjunto factible
1
Vid.Dantzig (1963).
y escoger el mejor. Para ilustrar esta idea empezaremos planteando un problema de P.L.
en su forma canónica2 . A continuación ilustramos esta idea mediante un ejemplo.
n
Max( z)
¦c x
j
j
j 1
sujeto a:
n
d bi
i ^1,..., m`
xj t 0
j ^1,..., n`
¦a x
ij
j
j 1
añadiendo variables de holgura a cada una de las restricciones se obtendríala
formulación equivalente:
n
Max( z)
¦c x
j
j
j 1
sujeto a:
n
¦a x
ij
j
si
i ^1,..., m`
bi
j 1
xj t 0
j ^1,..., n`
si t 0
i ^1,..., m`
El número de vértices del conjunto factible del problema es:
§m n·
¨
¸
© m ¹
m n !
m ! m n m !
[1]
La cantidad m + n refleja el número de variables originales (n) más...
Leer documento completo
Regístrate para leer el documento completo.