Método Símplex para investigación de operaciones y simulación

APLICACIÓN DEL MÉTODO SÍMPLEX EN
INVESTIGACIÓN DE OPERACIONES Y SIMULACIÓN
Introducción
El método símplex cuya gran virtud es su sencillez, es un método muy práctico, ya que solo
trabaja con los coeficientes de la función objetivo y de las restricciones.
Ilustraremos su funcionamiento mediante un ejemplo, pero previamente mostraremos las reglas
de decisión para determinar la variable que entra, la que sale, la gran M, y cómo determinar
que estamos en el óptimo; Todas éstas reglas de decisión fueron deducidas del método
algebraico, solamente que aquí se han acomodado para ser usadas en el tipo de tablero
símplex que se usará.
Criterio de decisión Maximizar Minimizar
Gran M en la función objetivo - MXj +MXj
Variable que entra La más negativa de los Zj - Cj La más positiva de los Zj - Cj
Variable que sale La menos positiva de los b/a ,
Siendo a > 0 , de lo contrario
no restringe
La menos positiva de los b/a ,
Siendo a > 0 , de lo contrario
no restringe a la variable que
entra
Solución óptima Cuando todos los Zj – Cj > 0 Cuando todos los Zj – Cj < 0
TIPOS DE RESTRICCIONES
Restricciones 
Se añade una variable de holgura, con costo (o ganancia) en la función objetivo igual a 0.
Ejm:
2X1 - 4X2 <= 1, queda:
2X1 - 4X2 + X3 = 1 Cj de X3 en la función objetivo será 0.
Restricciones 
Se resta una variable de exceso, con costo (o ganancia) en la función objetivo igual a 0, y se
suma una variable artificial con costo +M ó –M según sea maximización o minimización.
Ejm:
2X1 + 3X2 >= 1, queda:
2X1 + 3X2 - X3 + X4= 1 Cj de X3 en la función objetivo será 0. y Cj de X4 (artificial) es
M
Restricciones =
Se le añade una variable artificial con costo +M ó –M según sea maximización o minimización.
Ejm:
2X1 + 3X2 = 8, queda:
2X1 + 3X2 + X3= 8 Cj de X3 en la función objetivo será M
Adicionalmente se presentan las siguientes notas a tener en cuenta:
Si en el tablero simplex de la solución óptima queda al menos una variable de superávit ó
artificial dentro de las variables básicas, con un valor > 0 , el problema no tiene solución, esto
quiere decir que al menos existen dos restricciones excluyentes, por lo tanto no existe área de
soluciones factible y menos una solución , en éste caso se debe revisar la formulación del
problema.
Si al escoger la variable que sale, ninguna de las variables básicas restringe el crecimiento
de la variable no básica escogida para entrar, el problema tiene solución indeterminada y se
debe revisar la formulación en busca de una nueva restricción que no se tuvo en cuenta en la
formulación inicial.
Si en el tablero simplex del óptimo, al menos una de las variables no básicas tiene
coeficiente cero (0) en la función objetivo, esto es su Zj Cj = 0, el problema tiene múltiples
soluciones y se nos está ofreciendo una de ellas.
Ejemplo 1
Siendo Xi la cantidad a producir del producto i.
Maximizar Z = X1 + X2 {Ganancia total en soles}
S.A.
5X1 + 3X2 <= 15 {Horas disponibles dep. A}
3X1 + 5X2 <= 15 {Horas disponibles dep. B}
Xj >= 0 ; j = 1, 2
Los problemas de Maximización, con todas sus restricciones <= y con la condición de no
negatividad, se le llama Forma Estándar ó Forma Normal
Aquí debemos conseguir una solución básica factible, empleando las variables de holgura y/o
artificiales, quedando el sistema de ecuaciones así:
Maximizar Z = X1 + X2
S.A.
5X1 + 3X2 + X3 = 15
3X1 + 5X2 + X4 = 15
Xj >= 0 ; j = 1,2,3,4
Las variables básicas son aquellas cuyos coeficientes forman la matriz unitaria.
En este caos accidentalmente son las variables de holgura X3 y X4.
A continuación construimos la siguiente tabla:
Cj 1 1 0 0
b/a
a>0
V.B. b X1 X2 X3 X4
0X3 15 5 3 1 0 15/5=3
0X4 15 3 5 0 1 15/3=5
Zj - Cj 0-1 -1 0 0
El valor de la función objetivo Z, se encuentra frente a la casilla de Zj Cj , en éste caso vale
cero (0) y se calcula multiplicando el vector fila (en la tabla es la columna inmediatamente
anterior a la de las variables básica V.B.) que contiene los coeficientes de las variables básicas
en la función objetiva original por el vector columna de los términos independientes b
CXB = Vector fila de los coeficientes en la función objetivo original de las variables básicas
actuales, sus valores se encuentran en la primera columna del tablero.
b = Vector columna de los términos independientes de las restricciones, que al mismo tiempo
son los valores de las variables básicas actuales, sus valores se encuentran bajo la columna
denominada b
CXB = (0,0) ; b = (15,15)’ Z = CXB * b = (0)(15) + (0)(15) = 0
El valor de los Zj Cj se calcula multiplicado el vector fila CXB por el vector apuntador aj dela
columna de la variable j-ésima, menos el Cj, esto es:
Zj – Cj = CXB. aj – Cj ;
Los cálculos se efectúan así:
Z1 – C1 = CXB a1 – C1 = (0,0).(5,3)’ - 1 = (0)(5)+(0)(3) – 1 = -1
Z2 – C2 = CXB a2 – C2 = (0,0).(3,5)’ - 1 = (0)(3)+(0)(5) – 1 = -1
Z3 – C3 = CXB a3 – C3 = (0,0).(1,0)’ - 0 = (0)(1)+(0)(0) – 0 = 0
Z4 – C4 = CXB a4 – C4 = (0,0).(0,1)’ - 0 = (0)(0)+(0)(1) – 0 = 0
A continuación se indican la variable que sale y la variable que entra:
Variable que entra X1
Variable que sale X3
La variable que tiene Zj-Cj más negativo es ó X1 ó X2. Se escoge al azar X1.
En esta iteración b/a da: 15/5 = 3 y 15/3 = 5;
Lo que significa que la variable básica X3 restringe el crecimiento de la variable que entra, X1,
hasta 3 (no la deja tomar valores superiores a 3) y la variable básica X4 restringe el crecimiento
de la variable que entra X1 hasta 5 (no la deja tomar valores superiores a 5).
Por supuesto la variable básica que restringe más el crecimiento de la variable que entra
X1, es X3 , por lo tanto, es la variable básica escogida para salir.
La fila de la variable básica escogida para salir se divide por el elemento que se encuentra en
la intersección de dicha fila con la columna de la variable que entra, la fila resultante es la fila
pivote y se coloca en un nuevo tablero, desde el que se suman múltiplos de la fila pivote a las
demás filas del tablero anterior de tal forma que se eliminen de cada una de ellas la variable
escogida para entrar, en nuestro caso X1 , este procedimiento se denomina, hacer un uno (1)
en la intersección y el resto de la columna ceros (0), por lo tanto en dicha columna aparecerá
un vector unitario, el procedimiento se repite en cada iteración, hasta que todos los Zj – Cj sean
mayores ó iguales a cero en el caso de maximizar ó menores ó iguales a cero en el caso de
minimizar.
Cj 11 0 0 b/a
a>0
V.B. b X1 X2 X3 X4
0X3 15 53 1 0 15/5=3
0X4 15 3 5 0 1 15/3=5
Zj – Cj 0-1 -1 0 0
A continuación se muestran todas las iteraciones y en cada fila los valores por los cuales fueron
multiplicadas para ser sumadas a otras filas, ello se expresa como sumar múltiplos de una fila a
otra.
Fíjese que se suman múltiplos de las restricciones a la función objetivo para eliminar las
variables básicas de ella.
Variable que entra X2
Variable que sale X4
Solución óptima:
X1* = 15/8
X2* = 15/8
Z * = 15/4
La solución es única: X1 * = 15/8 ; X2 * = 15/8 ; Z* = 14/4
Ejemplo 2
Minimizar Z = 6X1 + 4X2 + 2X3
S.A.
6X1 + 2X2 + 6X3 >= 6
6X1 + 4X2 = 12
2X1 - 2X2 <= 2
Xj >= 0 ; j = 1, 2, 3
Minimizar Z = 6X1 + 4X2 + 2X3 + MX5 + MX6
S.A.
Cj 1 10 0 b/a
a>0
V.B. b X1 X2 X3 X4
1X1 313/5 1/5 0 5
0X4 60 16/5 -3/5 1 15/8
Zj - Cj 30 -2/5 1/5 0
Cj 1 1 0 0 b/a
a>0
V.B. b X1 X2 X3 X4
1X1 15/8 1 0 5/16 0
1X2 15/8 0 1 -3/16 5/16
Zj – Cj 15/4 0 0 1/8 1/8
6X1 + 2X2 + 6X3 – X4 + X5 = 6
6X1 + 4X2 +X6 = 12
2X1 - 2X2 +X7 = 2
Xj >= 0 ; j = 1, 2, 3, 4, 5, 6, 7
Las variables básicas son X5 = 6 , X6 = 12, X7 = 2
Solución Óptima:
Variables de decisión:
X1 = 0 , X2 = 3 , X3 = 0 , Z = 12
Variables de holgura : X4 = 0 , X7 = 8
Variables artificiales: X5 = 0 , X6 = 0
UN ADELANTO DEL ANÁLISIS POST-ÓPTIMO
Maximizar Z = X1 + X2 {Ganancia total en soles}
S.A.
5X1 + 3X2 <= 15 {Horas disponibles dep. A}
3X1 + 5X2 <= 15 {Horas disponibles dep. B}
Xj >= 0 ; j = 1, 2
Tablero inicial:
Cj 1 1 0 0 b/a
a>0
V.B. b X1 X2 X3 X4
0X3 15 5 3 1 0 15/5=3
0X4 15 3 5 0 1 15/3=5
Zj – Cj 0-1 -1 0 0
Tablero óptimo:
Solución óptima:
X1* = 15/8
Cj 1 1 0 0 b/a
a>0
V.B. b X1 X2 X3 X4
1X1 15/8 1 0 5/16 0
1X2 15/8 0 1 -3/16 5/16
Zj - Cj 15/4 0 0 1/8 1/8
X2* = 15/8
Z * = 15/4
Costo reducido:
Unidades = (unidad monetaria)/(unidad de producto) = (u.m.)/(u.p.) = las mismas unidades que
Cj
Precio dual:
Unidades = (unidad monetaria)/(unidad de recurso) = (u.m.)/(u.r.)
Interpretación del Costo reducido:
En cuantas unidades monetarias empeora la función objetivo al producir una unidad de un
producto que no se está produciendo.
En minimización: (z / x) En maximización: (z / x)
Si la variable es básica ,el costo reducido es 0.
Si la variable es no básica, es >= 0. Cuando es 0 significa soluciones alternativas.
Interpretación del Precio dual:
En cuantas unidades monetarias va a variar la función objetivo al variar en una unidad de
recurso limitante.
Cuando es >0: (z / b) ó (z / b)
Cuando es <0: (z / b) ó (z / b)
Precios duales
Costos reducidos
Una restricción es limitante cuando limita a la función objetivo. Esto sucede cuando se
cumple la igualdad de la restricción.
Si la restricción es no limitante, el precio dual es 0.
Si la restricción es limitante, puede tomar cualquier valor positivo, negativo o 0.
ANIMALES DISECADOS
Una Empresa de Animales Disecados está produciendo palomas y gavilanes disecados. En las
condiciones en que se encuentra el mercado actualmente puede vender los gavilanes y las
palomas con utilidades de $20.00 y $12.00 respectivamente.
Las pieles de los gavilanes son más duras y toman más tiempo de trabajo que las pieles de las
palomas. La máquina de pieles puede trabajar 4 pieles de gavilán por minuto ó 8 pieles para
palomas, usando la misma capacidad. La línea de relleno, puede rellenar 5 gavilanes ó 4
palomas por minuto. Los gavilanes van a una operación final en una máquina de afilado del
pico que tiene una capacidad de 3.5 gavilanes por minuto, La jornada de trabajo en la división
es de 8 horas.
a) Formule el modelo de programación lineal, que resuelva el caso.
b) Formule el problema dual del modelo formulado en (a).
c) Resolver el modelo, y hacer una interpretación administrativa de la solución.
d) Determinar la solución óptima del problema dual leyéndola directamente de la tabla óptima
encontrada en la pregunta c.
A no ser que se especifique de otra manera, las siguientes preguntas son independientes unas
de otras y están basadas en el enunciado inicial del problema.
e) Existe la posibilidad de trabajar sobretiempos en la máquina de pieles, en la línea de
relleno, y en la máquina de afilado. ¿Cuál es la mayor utilidad que se genera por cada
sobretiempo en cada una de las secciones?.
f) El Gerente de la Empresa visita la línea de gavilanes y palomas, y observa que hay
capacidad ociosa en algunos de los procesos. El resuelve ordenar que se usen todos los
centros del proceso, en toda su capacidad instalada. ¿Qué le diría usted?.
g) Qué sucedería con la solución óptima si las utilidades por cada paloma bajan a s/. 9.00 ?.
h) Para darle un mejor acabado a los juguetes, se ha instalado una línea de laqueado; la línea
de laqueado puede rellenar 5 gavilanes por minuto o 4 palomas en el mismo tiempo,
igualmente la jornada es de 8 horas. ¿Afectaría la solución óptima?; de ser así encuentre la
nueva solución.
NOTA TEORICA:
En esta pregunta, observar si la nueva restricción es cumplida por la solución actual, si es así
sería una restricción redundante y no afecta a la solución actual, pero si la solución actual no
la cumple, entonces será necesario volver a resolver el problema considerando esta nueva
restricción.
MODELO:
X1= numero de palomas a producir en el día
X2= numero de gavilanes a producir en el dia
MAX 12X1+20X2
SUBJECT TO
0.125X1+0.25X2<=480 maquina de pieles
0.25X1+0.2X2<=480 linea de relleno
0.2857143X2<=480 afilado de pico
END
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 39680.00
VARIABLE VALUE REDUCED COST
X1 640.000000 0.000000
X2 1600.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 69.333336
3) 0.000000 13.333333
4) 22.857122 0.000000
NO. ITERATIONS= 2
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 12.000000 13.000000 2.000000
X2 20.000000 4.000000 10.400001
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 480.000000 11.999989 240.000000
3 480.000000 480.000000 23.999977
4 480.000000 INFINITY 22.857122
AUTOR:
Ing.Mohammed Portilla Camara
Gerente de Operaciones
Grupo Groming Ingeniería SAC. y
CEENQUA: Certifications for Engineering of Quality
La Molina, Lima - Perú
Estudios realizados en: Ingeniería Industrial, Ingeniería de Minas e Ingeniería Informática
Universidad de Lima
Pontificia Universidad Católica del Perú
Universidad Nacional de Ingeniería
Escuela de Negocios para Graduados - ESAN

Compártelo con tu mundo

Escrito por:

Cita esta página
Portilla Camara Mohammed. (2010, febrero 23). Método Símplex para investigación de operaciones y simulación. Recuperado de http://www.gestiopolis.com/metodo-simplex-investigacion-operaciones-simulacion/
Portilla Camara, Mohammed. "Método Símplex para investigación de operaciones y simulación". GestioPolis. 23 febrero 2010. Web. <http://www.gestiopolis.com/metodo-simplex-investigacion-operaciones-simulacion/>.
Portilla Camara, Mohammed. "Método Símplex para investigación de operaciones y simulación". GestioPolis. febrero 23, 2010. Consultado el 5 de Julio de 2015. http://www.gestiopolis.com/metodo-simplex-investigacion-operaciones-simulacion/.
Portilla Camara, Mohammed. Método Símplex para investigación de operaciones y simulación [en línea]. <http://www.gestiopolis.com/metodo-simplex-investigacion-operaciones-simulacion/> [Citado el 5 de Julio de 2015].
Copiar
Imagen del encabezado cortesía de gsfc en Flickr