INVESTIGACIÓN DE OPERACIONES I,
material de estudio complementario
Prof. Diana C. Tascón-Hoyos
ALGORITMO SIMPLEX
1. Estandarizar el problema formulado:
1.1. Hacer 𝑏𝑖 ≥ 0 ∀𝑖, 𝑖 = 1,2, … , 𝑚
1.2. Hacer 𝑥𝑗 ≥ 0 ∀𝑗, 𝑗 = 1,2, … , 𝑛
1.3. Hacer que todas las restricciones sean igualdades
✓ Si la restricción es “≤”, se agrega una variable de holgura, es convencional denominarla
ℎ𝑖
✓ Si la restricción es “≥”, se resta una variable de excedente (o superflua), es convencional
denominarla 𝑒𝑖
1.4. Generar una solución básica inicial
✓ Para las restricciones que originalmente eran “≤”, las variables de holgura sumadas
cumplen con las condiciones para ser variables básicas.
✓ Para las restricciones que originalmente eran “=” o “≥”, en caso de no existir una
variable que cumpla con las condiciones para pertenecer a la base, se suma una variable
artificial, es convencional denominarla 𝐴𝑖
Nota: Tanto las variables de holgura como exceso entran a la función objetivo con coeficiente 0; las
variables artificiales, por indicar incumplimiento de las restricciones cuando son diferentes de cero,
son penalizadas mediante la gran 𝑀, En problemas de maximización tendrán coeficiente – 𝑀, en
problemas de minimización tendrán +𝑀 como coeficiente objetivo.
2. Formular el Tablero (Tableau) inicial
𝑐𝑗 𝑐1 𝑐2 … 𝑐𝑛
𝑐𝑏 𝑣𝑏
𝑥𝑗 𝑥1 𝑥2 … 𝑥𝑛
𝑏𝑖
𝑧 𝐹𝑗 − 𝐶𝑗
Programación lineal y entera
Material de apoyo
Prof. Diana C. Tascón
1
INVESTIGACIÓN DE OPERACIONES I,
material de estudio complementario
Prof. Diana C. Tascón-Hoyos
Dónde,
𝑐𝑏 =Coeficientes de las variables básicas en la función objetivo
𝑣𝑏 = Variables básicas (también se denomina 𝑥𝑏 )
𝑐𝑗 =Coeficiente de la variable 𝑗 en la función objetivo
𝐹𝑗 − 𝐶𝑗 = Costo reducido de la variable 𝑗
𝐹𝑗 − 𝐶𝑗 = ∑(𝑐𝑏𝑖 ∗ 𝑎𝑖𝑗 ) − 𝑐𝑗
𝑖=1
3. Evaluar los 𝐹𝑗 − 𝐶𝑗 ¿Se cumple el criterio de detención?
• Si FO Max 𝑍 = ∑𝑛𝑗=1 𝑐𝑗 𝑥𝑗 , y 𝐹𝑗 − 𝐶𝑗 ≥ 0 para todo 𝑗 → El tablero actual es óptimo
• Si FO Min 𝑍 = ∑𝑛𝑗=1 𝑐𝑗 𝑥𝑗 , y 𝐹𝑗 − 𝐶𝑗 ≤ 0 para todo 𝑗 → El tablero actual es óptimo
3.1. Si no se cumple con criterio de optimalidad, continuar en el paso 4.
4. Establecer la variable que debe entrar a la base así:
• Para un problema de Maximización entra aquella con el 𝐹𝑗 − 𝐶𝑗 más negativo
• Para un problema de Minimización entra aquella con el 𝐹𝑗 − 𝐶𝑗 más positivo
5. Establecer la variable que debe salir de la base así:
5.1. Calcular el siguiente cociente para cada restricción:
𝑏𝑖
5.1.1. {𝑎 , 𝑎𝑖𝑘 > 0}, donde, 𝑎𝑖𝑘 es el coeficiente tecnológico en el renglón 𝑖 de la variable
𝑖𝑘
que entra a la base; en caso de que 𝑎𝑖𝑘 ≤ 0, el resultado de la operación es
indeterminado (∞).
5.1.2. La variable saliente es aquella que es variable básica del renglón con el menor de los
𝑏𝑖
cocientes. 𝑀𝑖𝑛 { , 𝑎𝑖𝑘 > 0}.
𝑎𝑖𝑘
Nota: En caso de no poder determinar la variable saliente (puesto que todos los cocientes son
indeterminados), se concluye que el problema es NO acotado
Programación lineal y entera
Material de apoyo
Prof. Diana C. Tascón
2
INVESTIGACIÓN DE OPERACIONES I,
material de estudio complementario
Prof. Diana C. Tascón-Hoyos
6. Realizar el cambio de base, (usando OER / Gauss-Jordan); tomando como elemento pivote dentro
de la matriz de coeficientes tecnológicos, aquel donde se cruza la variable entrante (columna) con
la saliente (fila).
7. Volver al paso 3
Programación lineal y entera
Material de apoyo
Prof. Diana C. Tascón