UNIVERSIDAD TÉCNICA ESTATAL DE QUEVEDO
FACULTAD DE CIENCIAS PECUARIAS
INGENIERÍA EN ALIMENTOS
INVESTIGACIÓN OPERATIVA
TEMA:
MÉTODO SIMPLEX
ALUMNA:
GAIBOR RAMÓN ARELIS ELIZABETH
CURSO:
8vo MODULO “B”
DOCENTE:
ING. ERAZO SOLORZANO CYNTIA YADIRA
2019-2020
MÉTODO SIMPLEX
El método simplex se basa en el hecho de que la solución óptima de un modelo de
programación lineal continua (MPLC) siempre ocurrirá en un vértice (punto factible,
solución básica factible), debido a la linealidad y la convexidad de las restricciones
(desigualdades); de ahí, basta analizar los puntos extremos para conocer aquel que
produce el valor óptimo de la función a optimizar y, por ende, la solución óptima
(Martínez & Vértiz, 2014).
En la necesidad de desarrollar un método general para resolver problemas de
programación lineal convexa de más de dos variables, George Dantzing, en 1947,
desarrolló el método simplex cuyo fundamento se explica mediante el método algebraico.
El método usa como su principal herramienta, el álgebra, que ligado a un proceso de
lógica matemática da como resultado el denominado método algebraico (Chediak, 2013).
Sirve para solucionar problemas de programación lineal sin tener en cuenta el número de
restricciones ni el de variables (Gonzáles & García, 2015).
El método simplex consta de tres actividades fundamentales:
Prueba de optimalidad de la solución
Identificación de las variables que entran y salen
Análisis de la tabla característica para desarrollar una nueva solución
La idea general de este método se puede describir como el procedimiento iterativo que
parte del origen y selecciona aquellas variables que optimizan el valor de la función
objetivo.
Para una mejor comprensión de este algoritmo, se describen a continuación los
diferentes pasos lógicos que permiten obtener el valor óptimo (Z) para cualquier problema
de programación lineal (Gonzáles & García, 2015).
Tabla1. Reglas de aumento simplex
Aumento simplex Maximizar Minimizar
Signo
≤ +S +S
≥ -S -S +M
═ …………. +M
Solución Cj-Zj Sin valor positivo Sin valor negativo
Donde: S=variable de holgura, M= variable artificial
Fuente: (Briones, Martínez, & Araiza, 2018)
PROCEDIMIENTO SIMPLEX
Los siguientes autores (Gonzáles & García, 2015), detalla a continuación el
procedimiento simplex:
Estandarizar el modelo de programación lineal (PL)
Este paso tiene que ver con las restricciones aumentadas, es decir, cada restricción en el
problema de PL se debe aumentar utilizando variables de holgura y/o variables
artificiales.
Cualquier desigualdad ≤ se puede convertir en una igualdad, agregando la variable de
holgura Si para que represente el superávit.
Cualquier desigualdad ≥ se puede convertir en una igualdad, restando una variable de
excedente Si y sumando una variable artificial. Agregar una variable artificial se justifica
para dar cumplimiento al criterio de no negatividad; por ejemplo: X ≥ 10; X - S = 10, pero
si se está al comienzo del proceso, X = 0 y S = –10, conlleva al no cumplimiento del
criterio de no negatividad de los problemas de PL.
Este coeficiente se representa por M, y la variable artificial por A.
Ejemplo de estandarización:
Z(máximo)= 3x+20y
S.A.: X + Y ≤ 300
2X +3Y ≥200
1/2X+3Y═150
X,Y ≥0
Características de las variables de estandarización
Las variables de holgura (Si), de excedente (-Si) y las artificiales (Ai) tienen las siguientes
características:
Variables Si
Representan superávit o déficit de recurso escaso.
Se representan por Si
Pueden ser variables básicas en la solución óptima.
Variables Ai
Son ficticias, ya que sólo se usan al comienzo del proceso simplex para
estandarización, ser variables básicas en la solución óptima de los problemas de
PL; si esto llegara a suceder, el problema no tiene solución.
Son instrumentos de cálculo que se usan en restricciones ≥ o =.
Diseño de la tabla característica
Consiste en disponer todos sus elementos en forma tabular.
Fuente: (Gonzáles & García, 2015).
Definición de símbolos
Ci : contribución de las variables básicas (VB).
Xi : variables básicas (VB).
Cj : contribución de todas las variables básicas y no básicas.
Xj : variables básicas y no básicas.
Bi : disponibilidad de recursos al comienzo, y valor de las variables básicas al final o
sobrante de recurso.
B0 : valor del Z óptimo.
Identificar la variable que entra y la que sale
Seleccionar la columna pivote (variable que entra) a partir del Cj-Zj más alejado del
cero positivo, para problemas de maximización, y más alejado del cero negativo para
problemas de minimización.
Seleccionar la fila pivote (variable que sale) a partir del θi más cercano a cero, para
cualquier criterio de optimización (criterio de decisión de factibilidad).
En la intersección de la columna y la fila pivote se encuentra la celda pivote.
Determinar la nueva solución básica. Intercambio de variable.
Introducir a la base la variable correspondiente a la columna pivote que tomará el puesto
de la variable correspondiente a la fila pivote. Una vez se haga el intercambio se aplica
Gauss- Jordan para hacer iteración simplex.
Probar la optimalidad de la solución
El proceso simplex se termina cuando todos los Cj-Zj sean ceros o negativos, en
problemas de maximizacion; y ceros o positivos en problemas de minimización. De lo
contrario se continúa haciendo iteraciones.
Las iteraciones tienen en cuenta, como primera medida, la elección de la celda pivote, y
luego la iteración simplex propiamente dicha.
Si el procedimiento se realiza manualmente, hay que ser cuidadosos de no cometer
errores aritméticos.
Bibliografía
Briones, J. A., Martínez, E. J., & Araiza, C. E. (2018). UNIVERSIDAD AUTÓNOMA
DEL ESTADO DE HIDALGO, Instituto de Ciencias Económico
Administrativas.
Chediak, P. F. (2013). Investigaciones de operaciones. volumen i([Link].). Obtenido de
[Link]
Gonzáles, A. Á., & García, L. G. (2015). Manual práctico de investigación de
operaciones I (4a. ed.). Obtenido de [Link]
Martínez, S. I., & Vértiz, C. G. (2014). Investigaciones de operaciones. Obtenido de
[Link]