Problemas

2.2.2 METODO SIMPLEX REVISADO


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



De manera que las restricciones se convierten en
[A , I] [pic] = b y [pic] [pic] 0
en donde I es la matriz idéntica m x n y 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 solucionesbá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] [pic] = b,
en las que n variables no básicas del conjunto de (n + m) elementos de [pic]
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 deecuaciones se puede denotar por B XB = b, donde el vector de variables básicas
XB = [pic]
Se obtiene al eliminar las variables no básicas de [pic] y la matriz básica

B = [pic]
se obtiene al eliminar las columnas correspondientes a 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 bComo 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 el valor de la función objetivo para esta solución básica es.
Z = CB XB = CB B-1 b
Ejemplo Wyndor Glass.
C = [pic], [pic]= [pic], b = [pic]X = [pic], XS = [pic]
Iteración 0
XB = [pic], B = [pic] = B-1, así
[pic] = [pic] [pic] = [pic]
CB = [pic] así Z = [pic] [pic] = 0

Iteración 1


XB = [pic], B = [pic], B-1 = [pic]
Así [pic] = [pic] [pic] = [pic]
CB = [pic] así Z = [pic] [pic] = 30

Iteración 2

XB = [pic], B = [pic], B-1 = [pic]
Así [pic] = [pic][pic] = [pic]
CB = [pic] así Z = [pic] [pic] = 36FORMA MATRICIAL DEL CONJUNTO DE ECUACIONES ACTUALES
Para el conjunto original de ecuaciones, la forma matricial es
[pic] [pic] = [pic]
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
[pic] = [pic] [pic] = [pic]
Entonces, las operaciones algebraicas en ambos lados del conjunto de ecuaciones original resultaronequivalentes al premultiplicarlos por esta misma matriz. Como la forma matricial que se busca
[pic][pic] = [pic]
para el conjunto de ecuaciones después de cualquier iteración es
[pic] [pic] = [pic]

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