Ing.
Sharon Castellon
*El método simplex constituye un
procedimiento algebraico que resuelve
cualquier problema de programación
lineal, es un procedimiento matricial
iterativo fundamentado en la
metodología de Gauss Jordán en el
manejo de variables no negativas
El método simp0lex es un procedimiento iterativo que
permite hallar la mejor solución a la función objetivo.
El proceso concluye cuando no es posible seguir mejorando
dicho valor, es decir, « Se ha alcanzado la solución optima»
El mayor o menor valor posible, según el caso para que se
satisfagan las restricciones
Partiendo del valor de la función objetivo en cualquier punto
el procedimiento consiste en encontrar otro punto que mejore
al anterior.
* Existen tres requerimientos fundamentales para resolver un problema de programación lineal
mediante el método simplex.
* 1. Se deben expresar como ecuaciones todas las restricciones
* 2. El lado derecho de las restricciones no puede ser negativo
* 3. Todas las variables se limitan a valores no negativos
* Convertir las desigualdades en igualdades mediante la incorporación de variables de
holgura o artificiales según el caso que corresponda
2. Incluir las variables de holgura y artificiales en las
de la función objetivo con un coeficiente cero ( 0)
para el caso de las variables de holgura y con un
coeficiente M para las variables artificiales.
3. Formar la tabla Simplex que contendrá la
columna de constantes, el cuerpo y la parte
identidad.
4. Encontrar una mejor solución que la anterior
Función objetivo:
Max Z = C1X1 + C2X2 + ... + CnXn
Limitaciones o restricciones
A11X1 + A12X2 + ... + A1nXn ≤ B1
A21X1 + A22X2 + ... + A2nXn ≤ B2
Am1X1 + Am2X2 + ... + AmnXn ≤ Bn
* Introducción variable de holgura
H1, H2, H3H …… Hn = variables de holgura
A11X1 + A12X2 + ... + A1nXn + H1 = B1
A21X1 + A22X2 + ... + A2nXn + H2 = B2
Am1X1 + Am2X2 + ... + AmnXn + Hn = Bn
Al convertir el sistema de desigualdades en igualdades mediante la introducción
de variables de holgura, se ha logrado el punto de partida para el método
simplex, se agregan las variables de holgura a la función objetivo, antepuestas el
coeficiente «0»
Max Z = C1X1 + C2X2 + ... + C n X n + 0H1 + 0H2 + ... + 0Hn
Una vez mas que se determine la existencia de una mejor solución, se da lugar a otro intercambio y se
repite el proceso.
El método simplex constituye en un procesos iterativo o repetitivo, porque repite los pasos de solución
hasta conseguir la solución del problema.
Función objetivo:
Min Z = C1X1 + C2X2 + .. + CnXn + 0H1+0H2 + .. + MA1 + MA2… + MAn
Introducción de variables de holgura y artificiales
H1, H2, H3…… Hn = variables de holgura
A1, A2, A3…… An = variables artificiales
A11X1 + A12X2 + ... + A1nXn - H1 + A1 = B1
A21X1 + A22X2 + ... + A2nXn - H2 + A2 = B2
Am1X1 + Am2X2 + ... + AmnXn - Hn +An = Bn
* Este método es utilizado cuando existe la necesidad de introducir variables
artificiales (A) con el objeto de generar una solución básica factible.
* Aplicando el Método Simplex para su solución, la función objetivo Z se ve
alterada, ya que la contribución de las variables artificiales (coeficientes de las
variables artificiales) es:
+ M para un problema de minimización
Donde M es un valor muy grande (mucho mayor que cualquier coeficiente de las
variables en la función objetivo)
por ejemplo: M >>> 0
Como las variables artificiales no tienen ningún significado en el
problema.
Son definidas como un artificio (ya que es una conveniencia
matemática para lograr la matriz identidad y así una solución
inicial básica factible), y por lo cual ninguna variable artificial
deberá formar parte de una solución básica factible. Para eliminar
las variables artificiales de la solución, se les asigna en la función
objetivo original coeficientes, tales que haga su presencia no
atractiva en la base.
SIGNO DE LA TIPO DE VARIABLE
RESTRICCION
≤ + Variable de Holgura
≥ - Variable de holgura + Variable
Artificial
= + Variable Artificial
Empate en la columna clave (variable que entra) en este caso se seleccionara al azar cualquier
columna.
La única afectación posible es el numero de iteraciones que van a realizarte en la resolución del
problema.
Empate en la fila clave (variable que sale); en este caso existen reglas para determinar cual fila
será elegida como clave. Sin embargo, para fines practicas, es seleccionar al azar.
Sucede cuanto todos los elementos de la columna clave son menores o iguales que cero. En este
caso, Z podría ser infinita o negativa; de ahí el nombre de problemas de Z, no acotada.
Estas condiciones sueles surgir por errores en el planteamiento del problema o en el calculo
durante la resolución del mismo.
En el caso de términos negativos en las restricciones, se multiplica a ambos lados de la inecuación
con el coeficiente -1, el signo de la desigualdad será el contrario
Se originan cuando la función objetivo es paralela a una de las restricciones que coincide con la
dirección de la optimización.
Se presentan soluciones optimas cuando:
•Se ha identificado una solución optima
•El coeficiente de la fila (0) para una variable no básica es igual a cero
Un problema no tiene solución factible si no existen valores de las
variables que satisfagan las restricciones, esta situación se identifica en la
tabla del método simplex, cuando se llega a la solución optima y aun
existen variables artificiales en la zona de solución.
Se pretende cultivar en un terreno dos tipos de olivos: A y B. No se puede cultivar más de 8 hectáreas con olivos de tipo A, ni
más de 10 hectáreas con olivos del tipo B. Cada hectárea de olivos de tipo A necesita 4 m3de agua anual y cada una de tipo
B, 3 m3.
Se dispone anualmente de 44 m3 de agua. Cada hectárea de tipo A requiere una inversión de 500 € y cada una de tipo B,
225 €. Se dispone de 4500 € para realizar dicha inversión. Si cada hectárea de olivos de tipo A y B, son 500 y 300 litros
anuales de aceite. Obtener razonadamente las hectáreas de cada tipo de olivo que se deben plantar para maximizar la
producción de aceite
Tabla Simplex
El problema está resuelto cuando en la fila objetivo (Z) han quedado
valores positivos o iguales a cero
Se deben producir 6 hectáreas de olivo del tipo A y 7 hectáreas de olivo del tipo B, para
maximizar la utilidad a 5000. Observamos también que no se ha cubierto en su totalidad el
espacio del terreno que es 2 hectáreas para el olivo de tipo A, y también de 3 hectáreas para el
olivo de tipo B, por lo cual se debería utilizar todo el terreno para aumentar la utilidad actual
