Metodo Simplex Revisado, Casos Especiales

INSTITUTO TECNOLOGICO DE QUERETARO

JUAN MANUEL BALDERAS MENDEZ

INVESTIGACION DE OPERACIONES

“METODO SIMPLEX REVISADO, CASOS ESPECIALES”

05 de octubre de 2010
METODO SIMPLEX REVISADO

Se empleará la forma matricial, el modelo general de programación lineal es:
Maximizar Z = C X
Sujetoa A X b
y X 0
En donde C es un vector renglón C = [C1,C2,........Cn] X, b y 0 son vectores columna tales que
X = b = 0 =
y A es la Matriz
A =
Para obtener la forma de igualdades del problema se introduce al vector columna de las variables de holgura
XS =

De manera que las restricciones se convierten en
[A , I] = b y 0
en donde I es la matriz idéntica m x ny b el vector 0 ahora tiene (n + m) elementos.

OBTENCIÓN DE UNA SOLUCIÓN BÁSICA FACTIBLE.
Recuérdese que el objetivo general del método símplex es obtener una sucesión de soluciones básicas factibles mejoradas hasta alcanzar la solución optima.
La solución básica que resulta es la solución de m ecuaciones
[A , I] = b,
en las que n variables no básicas del conjunto de (n + m) elementosde
se igualan a cero. Cuando se eliminan estas n variables igualadas a cero queda un conjunto de m ecuaciones con m incógnitas ( las variables básicas). Este sistema de ecuaciones se puede denotar por B XB = b, donde el vector de variables básicas
XB =
Se obtiene al eliminar las variables no básicas de y la matriz básica

B =
se obtiene al eliminar las columnas correspondientesa los coeficientes de las variables no básicas de [A , I].
Para resolver B XB = b , ambos lados se multiplicaran por B-1:
B-1 B XB = B-1 b
Como B-1 B = 1, la solución deseada para las variables básicas es XB = B-1 b. Sea CB el vector obtenido al eliminar los coeficientes de las variables no básicas de [ C , 0 ] y al reordenar los elementos para que coincidan con los de XB , entonces elvalor de la función objetivo para esta solución básica es.
Z = CB XB = CB B-1 b
Ejemplo Wyndor Glass.
C = , = , b =
X = , XS =
Iteración 0
XB = , B = = B-1, así
= =
CB = así Z = = 0
Iteración 1

XB = , B = , B-1 =
Así = =
CB = así Z = = 30
Iteración 2
XB = , B = , B-1 =
Así = =
CB = así Z = = 36

FORMA MATRICIAL DEL CONJUNTO DE ECUACIONESACTUALES
Para el conjunto original de ecuaciones, la forma matricial es
=
Después de cualquier iteración, XB = B-1 b y Z = CB B-1 b, por lo que el lado derecho de las ecuaciones se ha convertido en
= =
Entonces, las operaciones algebraicas en ambos lados del conjunto de ecuaciones original resultaron equivalentes al premultiplicarlos por esta misma matriz. Como la forma matricialque se busca
=
para el conjunto de ecuaciones después de cualquier iteración es
=

Tabla inicial y final del símplex en forma matricial
Iteración | Variablebásica | Ec.núm. | Coeficiente de | Lado Derecho |
| | | Z | Variables original | Variable de holgura | |
0 | Z | 0 | 1 | -C | 0 | 0 |
| XB | 1-m | 0 | A | I | b |
| | | | | | |
Cualquiera | Z | 0 | 1 | CBB-1A -C | CBB-1 | CBB-1b |
| XB | 1-m | 0 | B-1 A | B-1 | B-1b |

Ejemplo
Considérese el último conjunto de ecuaciones que se obtiene en la iteración 2 para el problema de Wyndor Glass.
B-1A = =
CBB-1 = =
CBB-1 A –C = - =
Como ya se encontraron
XB = B-1b y Z = CBB-1b, estos resultados dan las siguientes ecuaciones:
=
PROCEDIMIENTO GLOBAL
1- Sólo es necesarioobtener B-1 para poder calcular todos los números de la tabla símplex a partir de los parámetros originales (A, b, CB) del problema.
2- Cualquiera de estos números (excepto Z = CBB-1b) se puede obtener al efectuar nada más una parte de la multiplicación de matrices.

RESUMEN DEL METODO SIMPLEX REVISADO
1- Paso Inicial: El mismo que para el método símplex original
2- Paso...