Metodo Simplex

MÉTODO SIMPLEX - MINIMIZACIÓN
Cuando se aplicó el método simplex a partir de la forma estándar del modelo
para el ejercicio prototipo, su estandarización considero variables de holgura
por tener todas las restricciones de disponibilidad, esto permite garantizar
iniciar con una solución factible básica, así como, garantizar también que los
siguientes iteraciones (tablas) serán tambiénfactibles (concepto de
factibilidad). Cuando se habla que todas las restricciones tienen variables de
holgura, se habla de restricciones de tipo “≤”, con lados derechos positivos (no
negativos). De ahí que las holguras ofrezcan una solución básica factible inicial
(X1 = 0, X2 = 0, S1 = 230, S2 = 250 y S3 = 120, para Z = 0). Sin embargo, se
conoce por los ejercicios de formulación realizados en laprimera parte del
curso, que los modelos además de restricciones “≤”, presentan restricciones del
tipo “≥” e “=” o una combinación de todos los tipos. En este punto es importante
preguntarse ¿Cómo puede encontrar el método simplex una solución factible
básica inicial para los problemas cuyas restricciones incluyen “≥” e “=” si al
estandarizar con variables de superávit, estas son negativas ycuando la
restricción es de la forma “=” no se coloca holgura ni superávit?
La respuesta a esta pregunta es: Para poder iniciar un problema de
programación lineal cuyas restricciones no tengan holguras es necesario
utilizar variables artificiales, las cuales asumirían el papel de holguras en la
primer tabla (iteración) para luego en las siguientes tablas (iteraciones) con el
proceso matemáticodel simplex, eliminarlas llevándolas a un valor de cero.
Para utilizar variables artificiales se utilizan dos métodos: El método de la gran
M y el método de las dos fases, para el curso se utiliza el método de la gran M.
MÉTODO DE LA GRAN M
El método inicia ubicando variables artificiales (no negativas) al modelo en
aquellas restricciones que después de estandarizarlo no presente variablesde
holgura convenientes. Para cualquier ecuación de la forma estándar que no
tenga holgura, presente superávit o sea una igualdad, sume una variable
artificial Ai, esto permite asegurar que el método simplex inicie con una forma
canónica (se forme la matriz idéntica). Esta variable o variables que se incluyan
se convierten en parte de la solución inicial. Observe que estas variablesartificiales no pertenecen al modelo, son ajenas a el, se usan como un comodín
matemático para ayudar a la solución, se necesita entonces relacionarlas

Investigación de Operaciones – Jorge Eduardo Calpa Oliva

también con la función objetivo, teóricamente este proceso se define como
penalizar la función objetivo, de esta manera se obliga ha que alcancen un
valor igual a cero en una próximaiteración (tabla) cuando se desarrolle el
algoritmo simplex.
Las variables artificiales se penalizan ubicándolas en la función objetivo
acompañadas de un coeficiente igual a M. El coeficiente de M se considera
como un valor positivo muy grande y finito, esto permite que jamás las
variables artificiales pertenezcan a la solución del modelo.
La manera de penalizar es la siguiente
•

Si el modeloposee una función de maximización, el coeficiente que
acompaña a la variable artificial es,
– M.

•

Si el modelo posee una función de minimización, el coeficiente que
+ M.
acompaña a la variable artificial es,

Después de organizar la forma estándar y sus respectivas penalizaciones, se
procede a utilizar los criterios del algoritmo simplex conocidos de una manera
normal.
Ejemplo:
MinZ = 4X1 +X2
Sujeto a
(R1)
(R2)
(R3)

3X1 + X2 = 3
4X1+ 3X2 ≥ 6
X1 +2X2 ≤ 4

(X1, X2) ≥ 0
Forma estándar del modelo
Min Z = 4X1 +X2
Sujeto a
(R1)

3X1 + X2

=3

(R2)
(R3)

4X1+ 3X2 – S1
=6
X1 + 2X2
+S2 = 4

(X1, X2, S1, S2) ≥ 0

Investigación de Operaciones – Jorge Eduardo Calpa Oliva

Observe que al estandarizar las restricciones, no se cumple la forma canónica...