Investigacion De Operaciones
Páginas: 16 (3780 palabras)
Publicado: 7 de marzo de 2013
op
[pic]
[pic]
INVESTIGACIÓN
DE OPERACIONES I
METODO SIMPLEX
Profesor: Ing. Luis Medina Aquino
2013-1
METODO SIMPLEX
Es un método sistemático y eficiente para encontrar y probar soluciones situadas en los vértices de optimalidad. El método Simplex termina una vez se haya encontrado la solución óptima.Como veremos, cada vértice del conjunto factible de programación lineal puede representarse en forma algebraica como una clase particular de solución de un conjunto de ecuaciones lineales.
Se generan soluciones diferentes de tal forma que producen una secuencia de vértices adyacentes. Cada movimiento en la secuencia (de un vértice al adyacente) se llama iteración y el movimiento implica unamanipulación en un sistema lineal.
Ejemplo:
Se tiene el siguiente programa lineal, en su forma canónica:
Maximizar Z = 200 X1 + 240 X2
Sujeto a:
6 X1 + 12 X2 ( 120
8 X1 + 4 X2 ( 64
X1 ( 0, X2 ( 0
El conjunto de soluciones factibles está
determinado por el polígono ABCD, en
donde:
Para A (0, 10) ( Z = 2,400
Para B (4, 8) ( Z = 2,720
Para C (8, 0) ( Z = 1,600Para D (0, 0) ( Z = 0
Variables de Holgura:
El método Simplex requiere que las restricciones sean ecuaciones (o restricciones con relación de igualdad) en vez de inecuaciones (o restricciones con relación de desigualdad).
Cualquier inecuación puede ser convertida en una ecuación agregando una cantidad no negativa en el lado de menor valor de la inecuación.
En la restricción 1será: 6 X1 + 12 X2 + S1 = 120
En la restricción 2 será: 8 X1 + 4 X2 + S2 = 64
El problema de programación lineal incorporando las variables de holgura se convierte en su forma estándar:
Maximizar Z = 200 X1 + 240 X2 + 0 S1 + 0 S2
Sujeto a:
6 X1 + 12 X2 + 1 S1 + 0 S2 = 120 ( 1a
8 X1 + 4 X2 + 0 S1 + 1 S2 = 64 ( 2a
X1, X2, S1, S2 ( 0
Variables Básicas ySoluciones Básicas Factibles
El conjunto de soluciones básicas en el problema dado en 1a y 2a:
Solución (1): X1 = 0, X2 = 0, S1 = 120, S2 = 64
Solución (2): X1 = 8, X2 = 0, S1 = 72, S2 = 0
Solución (3): X1 = 0, X2 = 1, S1 = 108, S2 = 60
Observe que las soluciones (1), (2) y (3) satisfacen también las restricciones de no negatividad. Por tanto, son solucionesfactibles.
Si tenemos más variables que ecuaciones, podemos tener un conjunto extra de variables iguales a cero, obteniendo así un sistema con igual número de variables y restricciones. Una solución así es llamada una solución básica.
Una solución básica factible para las ecuaciones 1a y 2a es una solución que tenga a lo sumo dos (= número de ecuaciones) variables con valores positivos y elresto de variables con valores iguales a cero.
Las soluciones (1) y (2) son soluciones básicas factibles.
Solución (1): X1 = 0, X2 = 0 S1 = 120, S2 = 64
Variables no básicas (= 0) Variables básicas (> 0)
Solución (2): X2 = 0, S2 = 0 X1 = 8, S1 = 72
Variables no básicas (= 0) Variables básicas (> 0)
Solución (3): X1 = 0, X2 = 1, S1 = 108, S2 = 60En la solución 3 hay tres variables que son positivas, por tanto, es una solución factible pero no una solución básica factible.
Procedimiento de computo Simplex
En general, la forma estándar de un modelo de programación lineal de maximización es la siguiente:
Maximizar Z = C1 X1 + C2 X2 + .... + Cn Xn + Cn+1 Xn+1 + .... + Cn+m Xn+m
Sujeto a :
a11 X1 + a12 X2 + .... + a1n Xn + Xn+1(=S1) = b1
a21 X1 + a22 X2 + .... + a2n Xn + Xn+2 (=S2) = b2
…… ……. …….. ….
am1 X1 + am2 X2 + .... + amn Xn + Xn+m (=Sm) = bm
Xj ( 0 ( j = 1, 2, 3, ...., m+n
TABLA SIMPLEX
|...
[pic]
[pic]
INVESTIGACIÓN
DE OPERACIONES I
METODO SIMPLEX
Profesor: Ing. Luis Medina Aquino
2013-1
METODO SIMPLEX
Es un método sistemático y eficiente para encontrar y probar soluciones situadas en los vértices de optimalidad. El método Simplex termina una vez se haya encontrado la solución óptima.Como veremos, cada vértice del conjunto factible de programación lineal puede representarse en forma algebraica como una clase particular de solución de un conjunto de ecuaciones lineales.
Se generan soluciones diferentes de tal forma que producen una secuencia de vértices adyacentes. Cada movimiento en la secuencia (de un vértice al adyacente) se llama iteración y el movimiento implica unamanipulación en un sistema lineal.
Ejemplo:
Se tiene el siguiente programa lineal, en su forma canónica:
Maximizar Z = 200 X1 + 240 X2
Sujeto a:
6 X1 + 12 X2 ( 120
8 X1 + 4 X2 ( 64
X1 ( 0, X2 ( 0
El conjunto de soluciones factibles está
determinado por el polígono ABCD, en
donde:
Para A (0, 10) ( Z = 2,400
Para B (4, 8) ( Z = 2,720
Para C (8, 0) ( Z = 1,600Para D (0, 0) ( Z = 0
Variables de Holgura:
El método Simplex requiere que las restricciones sean ecuaciones (o restricciones con relación de igualdad) en vez de inecuaciones (o restricciones con relación de desigualdad).
Cualquier inecuación puede ser convertida en una ecuación agregando una cantidad no negativa en el lado de menor valor de la inecuación.
En la restricción 1será: 6 X1 + 12 X2 + S1 = 120
En la restricción 2 será: 8 X1 + 4 X2 + S2 = 64
El problema de programación lineal incorporando las variables de holgura se convierte en su forma estándar:
Maximizar Z = 200 X1 + 240 X2 + 0 S1 + 0 S2
Sujeto a:
6 X1 + 12 X2 + 1 S1 + 0 S2 = 120 ( 1a
8 X1 + 4 X2 + 0 S1 + 1 S2 = 64 ( 2a
X1, X2, S1, S2 ( 0
Variables Básicas ySoluciones Básicas Factibles
El conjunto de soluciones básicas en el problema dado en 1a y 2a:
Solución (1): X1 = 0, X2 = 0, S1 = 120, S2 = 64
Solución (2): X1 = 8, X2 = 0, S1 = 72, S2 = 0
Solución (3): X1 = 0, X2 = 1, S1 = 108, S2 = 60
Observe que las soluciones (1), (2) y (3) satisfacen también las restricciones de no negatividad. Por tanto, son solucionesfactibles.
Si tenemos más variables que ecuaciones, podemos tener un conjunto extra de variables iguales a cero, obteniendo así un sistema con igual número de variables y restricciones. Una solución así es llamada una solución básica.
Una solución básica factible para las ecuaciones 1a y 2a es una solución que tenga a lo sumo dos (= número de ecuaciones) variables con valores positivos y elresto de variables con valores iguales a cero.
Las soluciones (1) y (2) son soluciones básicas factibles.
Solución (1): X1 = 0, X2 = 0 S1 = 120, S2 = 64
Variables no básicas (= 0) Variables básicas (> 0)
Solución (2): X2 = 0, S2 = 0 X1 = 8, S1 = 72
Variables no básicas (= 0) Variables básicas (> 0)
Solución (3): X1 = 0, X2 = 1, S1 = 108, S2 = 60En la solución 3 hay tres variables que son positivas, por tanto, es una solución factible pero no una solución básica factible.
Procedimiento de computo Simplex
En general, la forma estándar de un modelo de programación lineal de maximización es la siguiente:
Maximizar Z = C1 X1 + C2 X2 + .... + Cn Xn + Cn+1 Xn+1 + .... + Cn+m Xn+m
Sujeto a :
a11 X1 + a12 X2 + .... + a1n Xn + Xn+1(=S1) = b1
a21 X1 + a22 X2 + .... + a2n Xn + Xn+2 (=S2) = b2
…… ……. …….. ….
am1 X1 + am2 X2 + .... + amn Xn + Xn+m (=Sm) = bm
Xj ( 0 ( j = 1, 2, 3, ...., m+n
TABLA SIMPLEX
|...
Leer documento completo
Regístrate para leer el documento completo.