Programación Lineal
Unidad 1
Parte 3
• Matriz unitaria “I” de base con variables artificiales
• Cuando el problema de programación lineal se expresa en la forma
canónica de maximizar, las variables de holgura que se suman en
cada restricción de tipo ≤ para conseguir la igualdad de la forma
estándar, proporcionan un coeficiente (+1) que es útil para formar
la matriz unitaria “I”; se cumple así la necesidad de la primera
solución básica factible que requiere el algoritmo simplex para su
inicio.
• Pero muchas veces, el modelo de programación lineal no tiene
forma canónica y presenta restricciones de tipo ≥ e=, con las
cuales no se usan variables de holgura para el propósito de
conseguir la forma estándar. Al restar la superávit -1S se
convierte a ecuación la restricción tipo ≥; y la restricción = ya se
cumple, pero en ambos casos no se tiene la aportación del
coeficiente +1.
• Los problemas de programación lineal expresados con restricciones
distintas al tipo ≤ necesitan un artificio matemático para conseguir
una matriz de base artificial, lo cual es posible sumando una variable
artificial Wi de valor no negativo i= 1,2,…,m en cada restricción i de
tipo ≥ e=, así se proporciona el coeficiente +1 indispensable para la
formación de la matriz unitaria I que requiere el algoritmo simplex
para ponerlo en marcha.
• Una variable artificial no tiene significado físico y sólo se utiliza para
completar la primera solución básica que requiere el simplex para
iniciarse, pero en contraste, a través de las etapas de cálculo, debe
procurarse que las artificiales salgan pronto de la base,
convirtiéndolas en no básicas, o bien que, como variables básicas
valgan cero para poder lograr la solución óptima.
Método simplex penal o de la
M grande, Técnica M
• El simplex X penal es una variable del método simplex aplicable en
los casos en que las variables artificiales son necesarias en el
problema, ya sea de maximizar o también de minimizar. El nombre
de simplex penal se explica porque se penaliza con un coeficiente
M, que representa un valor muy grande (mayor que cualquier otro
coeficiente del problema), a cada variable artificial Wi, que se
incluya en la función objetivo del problema. Para máximo se utiliza
la penalización con signo menos (-M), por otro lado para mínimo se
utiliza signo más (+M)
• Las variables artificiales se usan para la primera
solución básica del simplex, pero el valor muy grande
del coeficiente M, procura su rápida salida de la base
cuando el problema tiene solución factible. Aunque
algún caso degenerado puede tener una variable
artificial en la base con valor cero; por el contrario, si
no es posible anular las variables artificiales (Wi > 0),
siginifica que no hay solución factible al problema
• Primero se prepara el problema convirtiendo a igualdades para
forma estándar del modelo propuesto, sumando una variable de
holgura H1 en la restricción (1), después se resta una variable S2
de superávit en la (2), la restricción (3) es de tipo = por lo que se
deja como está; se condiciona toda variable Xj ≥0 y con la función
objetivo original ya se tiene este modelo como estándar.
• Pero así no se completa la matriz cuadrada unitaria I que debe ser
de orden m=3 restricciones, pues sólo se tiene el vector unitario de
la variable de holgura H1 que sí aporta el coeficiente +1, faltando
dos vectores unitarios. Aquí surge la necesidad de utilizar el
artificio matemático ya referido. En las restricciones (2) y (3) que
son de ≥ e =; se suman variables artificiales W2 y W3, aportando
cada una de ellas el necesario coeficiente +1, con lo que completa
la matriz I mostrada antes de la tabla simplex, quedando el modelo
que se presenta con base artificial.
• Esta variable del simplex, incluye a las variables
artificiales en la función objetivo, pero penalizadas
con un coeficiente M, que representa un valor mayor
que cualquier otro coeficiente presente en el modelo;
para este ejemplo se le asigna –M como coeficiente a
las variables artificiales W2 y W3, cumpliendo así con
la penalización de la función objetivo la cual se
arregla al formato de las restricciones, restando el
lado derecho a la variable Z, consiguiendo el término
independiente cero en el lado derecho.
En segundo lugar debe prepararse la tabla simplex con la primera
solución básica “factible”, la que se consigue con las variables
artificiales W2 y W3, procurando su pronta anulación con los cambios
de la base.
Se inicia con los renglones y columnas y los encabezados necesarios
para copiar ordenadamente los coeficientes del modelo, tal como se
presentan en la forma artificial y la función Z arreglada con término
independiente; lo lugares vacíos se llenan con cero.
Aquí la matriz I, no necesariamente se forma con sus vectores unitarios
colocados juntos escalonadamente; pueden quedar intercalados
vectores unitarios (por las variables de holgura y/o artificiales ) o no
unitarios (por las de superávit); en este ejemplo, hay una intercalación
de la variable S2 de superávit, lo cual se podría haber evitado
permutado las primeras dos restricciones.
• En todos los casos se puede buscar arreglar las restricciones en el
orden que convenga para facilitar el análisis posterior de la solución
tabular. Las variables básicas deben colocarse en la columna
izqierda ordenadas de tal manera, que coincidan en su renglón con
el coeficiente +1 del vector unitario, de la columna correspondiente
a la misma variable.
• Toda variable básica debe tener coeficiente indicador cero en el
renglón Z, esto significa que tal variable ya no puede aportar alguna
cantidad al valor de la función objetivo; pero las variables artificiales
W2 y W3 tienen un coeficiente M en dicho renglón; lo cual impide
que se tenga una solución básica “factible” en esta tabla, por lo que
se procede a conseguir los coeficientes cero faltantes en el renglón
Z para las variables artificiales.
• Esto se logra mediante operaciones fila elementales usadas en el
proceso Gauss-Jordan, lo que se muestra en las fórmulas en el
lado izquierdo de la tabla: para calcular el cero en W2, se
multiplica el renglón W2 por el número –M (inverso aditivo de M) y
se suma el renglón Z, o sea, (RW2)(-M) +RZ=Z´, se tiene así cero
en la posición Z´con W2.
• Luego se multiplica el renglón W3 por el número –M y se suma el
renglón Z´, es decir, (RW3)(-M) +RZ´= Z”, se determinan así los
coeficientes cero necesarios para que las variables W2 y W3 sean
básicas. Ahora sí en esta segunda tabla, se tiene la primera
solución básica indispensable para el algoritmos se inicie con la
aplicación de los criterios del simplex.
• En tercer lugar, ya determinada la solución de arranque, se aplican
los criterios del simplex empezando con el de optimalidad y
considerando que el objetivo es máximo, la observación de los
indicadores del renglón Z, en esta segunda tabla, existe sólo un
coeficiente negativo en la variable no básica de decisión X1, por lo
cual se declara variable entrante a la base.
• La aplicación de la factibilidad resulta al obtener el mínimo
cociente, de dividir los valores actuales de las variables básicas
situados en la columna solución a la derecha de la tabla, entre los
coeficientes en el mismo renglón i con la columna correspondiente
a la variable VE. Así: mínimo (6/1, o/2, 2/1) =0, que coincide en el
renglón de la variable artificial W2 que se declara variable saliente.
• En el cruce de la columna X1 y el renglón W2, se localiza el
coeficiente 2 como pivote P para calcular con Gauss-Jordan la
siguiente tabla simplex (tercera) con la nueva solución básica que
debe tener a H1, X1 (sustituye a W2) y W3, como base. Se
recomienda cuidar la colocación de la variables en la base,
conservando el mismo orden que le corresponde de tabla a tabla,
excepto para la nueva V que ocupa el lugar de la VS.
• En la tercera tabla simplex, se repite la aplicación del
criterio de optimalidad seleccionando entre (-1/2M -7/2)
y (-1/2 M – 3/2), el coeficiente más negativo para el
objetivo máximo, entonces se declara a la variable no
básica X2 como a la base.
• Para la factibilidad, vea que el renglón de la variable
básica X2 queda descartado debido a que o /-1/2 no es
válido, en cambio con las otras dos variables en la
base se tiene: mínimo (6/3/2, 2/ 1/1/2) =4, existe
empate que debe romperse teniendo en cuenta, la
necesidad de procurar una rápida salida de la base de
las variables artificiales, en tal caso se puede elegir a la
que ahora, es indeseable variable básica W3. En el
cruce de columna X2 como VE y renglón W3, como VS,
se localiza el coeficiente pivote ½ con el que se inicia el
cálculo de la siguiente tabla (cuarta) simplex de este
problema ejemplo.
• La cuarta tabla simplex comienza por ordenar las tres
variables básicas H1, X1 y la nueva X2 que sustituye a
la W3, se continúa con el cálculo de coeficientes del
renglón RE= RS/P=RS/ ½ resultando el coeficiente +1
en la posición de pivote, necesario para determinar con
el Gauss-Jordan el resto de la tabla que muestra en el
lado izquierdo, las fórmulas empleadas de este
método.
• Esta última tabla tiene en el renglón Z, coeficientes
indicadores para las variables de valor no negativo, lo
cual significa una solución óptima pues, además, todas
las variables artificiales ya salieron de la base.
Descargar

Unidad uno parte 3