Método Simplex
Clase 2
Mg. Víctor Darío Sosa Jáuregui
Propósito de la Clase
● Utilizar el método simplex en PL
¿Qué es el método simplex?
• El método simplex es un procedimiento iterativo para resolver
problemas de programación lineal, donde se busca obtener la
solución óptima de la función objetivo que logre cumplir el
conjunto de restricciones.
• Este algoritmo fue desarrollado en el año 1947 por el
matemático norteamericano George Dantzig.
Pasos del Método Simplex
Los pasos a seguir en el método simplex son:
1. Definir el problema en la forma estándar y generar nuestra matriz.
2. Determinar la solución básica inicial.
3. Seleccionar la variable de entrada utilizando la condición de
optimalidad.
• Si no se puede seleccionar una variable de entrada, quiere decir que estamos
en la condición óptima y finalizan las iteraciones.
• De otro modo se continúa con el siguiente paso.
4. Seleccionar la variable de salida utilizando la condición de factibilidad.
5. Actualizar nuestra matriz realizando las operaciones de Gauss-Jordan.
Volver al paso número 3.
Pasos del Método Simplex
1. Definir el problema en la forma estándar y generar matriz
Pasos del Método Simplex
¿Qué hago si el lado derecho de la restricción es negativo?
Cuando el término independiente de la restricción es negativo, se debe multiplicar
por -1 a toda la restricción para convertir el valor del lado derecho en positivo.
Esta multiplicación también afectará al signo de la restricción de la siguiente
forma:
• Si la restricción es del tipo mayor igual (≥), se deberá cambiar a menor igual
(≤).
• En caso la restricción sea del tipo menor igual (≤), se deberá cambiar a mayor
igual (≥).
• Si la restricción es una igualdad, el signo se mantiene.
Un caso especial es cuando el término independiente de la restricción es 0 y el
signo es mayor igual (≥); en dicha situación, podemos multiplicar la restricción por
(-1) para convertirla en menor igual (≤). Esto nos servirá para no utilizar variables
artificiales como veremos posteriormente.
Convertir restricciones en igualdades
• Si la restricción es menor igual (≤): Para este tipo de
restricciones debemos introducir una variable no negativa llamada
de holgura y que son auxiliares para el problema. Por ejemplo:
R1: 10X1 + 7X2 <= 400
10X1 + 7X2 + S1 = 400
variable de holgura
Convertir restricciones en igualdades
• Cuando la restricción es mayor igual (≥): En este tipo de
restricciones se debe restar una variable de exceso y así mismo
agregar una variable artificial. Por ejemplo:
R2: 5X1 + 3X2 >= 100
5X1 + 3X2 - S2 + A1 = 100
var. de exceso var. artificial
Convertir restricciones en igualdades
• Si la restricción es igual (=): En este tipo de restricciones
debemos agregar una variable artificial de la siguiente forma:
R3: 2X1 + 3X2 = 50
2X1 + 3X2 + A1 = 50
var. artificial
Pasos del Método Simplex
2. Determinar la solución básica inicial:
Como habíamos mencionado, el método simplex parte de un
vértice de la región factible, es decir, un punto extremo.
Con cada iteración avanzaremos de vértice en vértice hasta llegar
a la solución óptima.
Ejercicio
La empresa El Confort, dedicada a la fabricación de muebles, ha
ampliado su producción en dos líneas más.
Por lo tanto actualmente fabrica mesas, sillas, camas y libreros;
con la cantidad y tipo de pieza detallada en la siguiente tabla.
Cada mesa cuesta producirla $10000 y se vende en $ 30000,
cada silla cuesta producirla $ 8000 y se vende en $ 28000, cada
cama cuesta producirla $ 20000 y se vende en $ 40000, cada
librero cuesta producirla $ 40000 y se vende en $ 60000.
El objetivo de la fábrica es maximizar las utilidades.
Ejercicio
PIEZAS
MUEBLE Tipo A Tipo B Tipo C Tipo D
Mesas 2 2 0 0
Sillas 1 2 0 0
Camas 1 1 2 0
Libreros 2 0 2 4
INVENTARIO 24 20 20 16
Solución
Función Objetivo:
ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4
Variables:
X1 = Cantidad de mesas a producir (unidades)
X2 = Cantidad de sillas a producir (unidades)
X3 = Cantidad de camas a producir (unidades)
X4 = Cantidad de libreros a producir (unidades)
Solución
Restricciones:
2X1 + 1X2 + 1X3 + 2X4 <= 24
2X1 + 2X2 + 1X3 <= 20
2X3 + 2X4 <= 20
4X4 <= 16
X1 , X2 , X3 , X4 >= 0
Solución
1. Definir el problema en la forma estándar
Función Objetivo:
ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4+ 0S1+ 0S2+ 0S3+ 0S4
Restricciones:
2X1 + 1X2 + 1X3 + 2X4 + 1S1+ 0S2+ 0S3+ 0S4 = 24
2X1 + 2X2 + 1X3 + 0X4 + 0S1+ 1S2+ 0S3+ 0S4 = 20
0X1 + 0X2 + 2X3 + 2X4 + 0S1+ 0S2+ 1S3+ 0S4 = 20
0X1 + 0X2 + 0X3 + 4X4 + 0S1+ 0S2+ 0S3+ 1S4 = 16
X1 , X2 , X3 , X4 , S1, S2, S3, S4 >= 0
DUAL
• Primal: problema a maximizar o minimizar
• Dual: problema de características inversas al primal
• Max -> Min (viceversa)
• Restricciones -> variables
• Variables -> restricciones
• Coeficientes -> LD
Referencias Bibliográficas
● Hamdy A. Taha. (2012). Investigacion de operaciones. México:
Pearson.
● Manual de Geogebra. Recuperado de
[Link]
● Plan de Mejora (15 de agosto del 2021).[Mensaje en un blog].
Recuperado de
[Link]
los-maximizar-minimizar/
● Ingeniería Industrial Online (8 de octubre del 2021).[Mensaje en un
blog]. Recuperado de
[Link]
ones/metodo-simplex/