Estadístico Rolando R.
Romero Paredes
Investigación Operativa
Estadístico Rolando R. Romero Paredes Estadístico Rolando R. Romero Paredes
Logro general de aprendizaje:
• Al final del curso el estudiante estará en capacidad
de modelar situaciones reales en modelos de
problemas lineales, hallar la solución óptima,
interpretar la solución y obtener información que
le permita tomar la mejor decisión.
Estadístico Rolando R. Romero Paredes
Logro específico de aprendizaje:
•Al finalizar la unidad, el alumno
analiza la solución de modelos de
programación lineal.
Estadístico Rolando R. Romero Paredes
Preguntas de repaso
• ¿Un recurso puede tomar valores máximos y
mínimos?
• ¿El coeficiente de una variable en la función
objetivo puede tener valores máximos y
mínimos?
Estadístico Rolando R. Romero Paredes
Unidad II
Análisis de sensibilidad
Semana 5 – Sesión 2: Método simplex
Estadístico Rolando R. Romero Paredes Estadístico Rolando R. Romero Paredes
Preguntas de control
• ¿De qué forma se convierte una restricción de su
forma canónica a la forma estándar?
• ¿Qué es un elemento Pivote?
Estadístico Rolando R. Romero Paredes
Logro de la semana
•Al finalizar la semana los alumnos aplican
plantean modelos de programación lineal
en dos variables y buscan la solución con el
método simplex.
Estadístico Rolando R. Romero Paredes
Estadístico Rolando R. Romero Paredes
Método
Simplex
Estadístico Rolando R. Romero Paredes Estadístico Rolando R. Romero Paredes
Método Simplex...
Es el método analítico ampliamente utilizado para
solucionar problemas de programación lineal.
El Método Simplex fue desarrollado por George Dantzig en
1947.
Este cambia las restricciones o desigualdades en
ecuaciones de problemas PL, y soluciona el problema con
la manipulación de matrices.
La solución encontrada del problema alterado es de una
dimensión mayor que el original, pero es relativamente
sencillo mediante el estudio de matrices.
Estadístico Rolando R. Romero Paredes
...Método Simplex
Existen diferentes software disponibles en la actualidad para
poder resolver los problemas a través de este método.
Entre los más importantes tenemos:
•Lindo,
•Optimization Solutions and Library de IBM,
•POM Computer Library,
•LINGO,
•SOLVER de MS Excel.
Estadístico Rolando R. Romero Paredes
Reglas de decisión
Criterio de decisión Maximizar Minimizar
Gran M en la función
objetivo - MXj + MXj
Variable que entra El coeficiente más El coeficiente más positivo
negativo de la F.O. de la F.O.
Variable que sale El valor menos positivo de El valor menos positivo
los bj / aij , de los bj / aij ,
Siendo aij > 0 , de lo Siendo aij > 0 , de lo
contrario no restringe a la contrario no restringe a la
variable que entra variable que entra
Solución óptima Cuando todos los Cuando todos los
Cj > 0 Cj < 0
Estadístico Rolando R. Romero Paredes
Problema de enlatados de tomate,
• Una compañía tiene un contrato para recibir 60000 libras de tomates
maduros a 0.7$/lb de las cuales producirá jugo de tomate y puré de
tomate enlatados. Los productos enlatados se empacan en cajas de 24
latas cada una. Una lata de jugo requiere 1 lb de tomates frescos en tanto
que una de puré requiere solo de 1/3 de lb. La participación de la
compañía en el mercado esta limitada a 2000 cajas de jugo y 6000 cajas
de puré. Los precios al mayoreo por caja de jugo y de puré son $18 y $9.
Genere un programa de producción para esta compañía.
Estadístico Rolando R. Romero Paredes
Vamos a resolver el siguiente problema:
Maximizar Z = 1.2x1 + 3.4x2
Sujeto a: 24x1 + 8x2 ≤ 60000
x1 ≤ 2000
x2 ≤ 6000
x1 ≥ 0 , x2 ≥ 0
Estadístico Rolando R. Romero Paredes
Se consideran los siguientes pasos:
1. Convertir las desigualdades en igualdades:
Se introduce una variable de holgura por cada una de las
restricciones, este caso Xn+1, Xn+2, Xn+3 para convertirlas
en igualdades y formar el sistema de ecuaciones
estándar. Usando en simplex el siguiente criterio:
Signo: Introducir
≤ xn+1
Estadístico Rolando R. Romero Paredes
FORMA ESTANDAR:
24x1 + 8x2 + x3 ≤ 60000
x1 + x4 ≤ 2000
x2 + x5 ≤ 6000
Estadístico Rolando R. Romero Paredes
Paso 2:
Igualar la función objetivo a cero y despues agregar la variables de
holgura del sistema anterior:
Z – 1.2 x1 – 3.4 x2 = 0
Para este caso en particular la función objetivo ocupa la ultima fila del
tablero, pero de preferencia siempre se deberá de colocar como la
primera fila.
Cuando minimizamos se toma el valor (+) positivo de F.O. para convertirlo
en negativo y cuando maximizamos tomamos el valor (-) negativo de F.O.
para convertirlo en positivo.
Estadístico Rolando R. Romero Paredes
Paso 3: Escribir el tablero inicial simplex.
En las columnas aparecerán todas las variables del
problema y en las filas, los coeficientes de las igualdades
obtenidas, una fila para cada restricción representada por las
variables de holgura y la primera fila con los coeficientes de
la función objetivo:
Estadístico Rolando R. Romero Paredes
Tablero Inicial
Variable de
Base Variable de holgura Solución
decisión
X1 X2 X3 X4 X5 Bj
Z -1.2 -3.4 0 0 0 0
X3 24 8 1 0 0 60000
X4 1 0 0 1 0 2000
X5 0 1 0 0 1 6000
Estadístico Rolando R. Romero Paredes
Paso 4: Encontrar la variable de decisión que entra en la base y la
variable de holgura que sale de la base
A. Para escoger la variable de decisión que entra en la base, observamos
la primera fila, la cual muestra los coeficientes de la función objetivo y
escogemos la variable con el coeficiente más negativo.
En este caso, la variable X1 de coeficiente – 3.4 (columna pivote)
➢Si existiesen dos o más coeficientes iguales que cumplan la condición
anterior, entonces se elige cualquiera de ellos.
➢Si en la primera fila no existiese ningún coeficiente negativo, significa
que se ha alcanzado la solución óptima.
Por tanto, lo que va a determinar el final del proceso de aplicación del
método del simplex, es que en la primera fila no haya elementos
negativos.
Estadístico Rolando R. Romero Paredes
Paso 4: Encontrar la variable de decisión que entra en la
base y la variable de holgura que sale de la base
B. Para encontrar la variable de holgura que tiene que salir de la base, se
divide cada término de la última columna (valores solución) por el
término correspondiente de la columna pivote, siempre que estos
últimos sean mayores que cero.
Si hubiese algún elemento menor o igual que cero no se hace dicho
cociente. En el caso de que todos los elementos fuesen menores o
iguales a cero, entonces tendríamos una solución no acotada y no se
puede seguir.
Estadístico Rolando R. Romero Paredes
Iteración No. 1
Variables de
Base Variables de holgura Solución Operación
decisión
X1 X2 X3 X4 X5 Bj
Z -1.2 -3.4 0 0 0 0
60000/8 =
X3 24 8 1 0 0 60000
7500
No
X4 1 0 0 1 0 2000
restringe
6000/1=
X5 0 1 0 0 1 6000
6000
Estadístico Rolando R. Romero Paredes
Paso 4: Encontrar la variable de decisión que entra
en la base y la variable de holgura que sale de la
base
Si al calcular los cocientes, dos o más son iguales, indica
que cualquiera de las variables correspondientes pueden
salir de la base.
[Link] la intersección de la fila pivote y columna pivote
tenemos el elemento pivote operacional, 1, este indica que
la variable de decisión X1 entra y la variable de holgura X5
sale.
Estadístico Rolando R. Romero Paredes
Resultado de Iteración No. 1
Variable de
Base Variable de holgura Solución Operación
decisión
X1 X2 X3 X4 X5 Bj
Z -1.2 0 0 0 3.4 20400 1. F0 + F3(3.4)
X3 24 0 1 0 -8 12000 2. F1 – 8 F3
X4 1 0 0 1 0 2000
X2 0 1 0 0 1 6000
Estadístico Rolando R. Romero Paredes
Paso 4: Encontrar la variable de decisión que entra en la
base y la variable de holgura que sale de la base
Como en los elementos de la última fila hay un número negativo, -1.2, significa
que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
A. La variable que entra en la base es X1, pasa a ser la columna pivote
que corresponde al coeficiente -1.2
B. Para calcular la variable que sale o la fila pivote, dividimos los
términos de la columna solución entre los términos de la nueva
columna pivote; y como el menor cociente positivo es 500, tenemos
que la fila pivote y la variable de holgura que sale es X3.
Estadístico Rolando R. Romero Paredes
Iteración No. 2
Variable de
Base Variable de holgura Solución Operación
decisión
X1 X2 X3 X4 X5 Bj
Z 0 0 0.05 0 3 21000 F0+(1.2)F1
X1 1 0 1/24 0 -1/3 500
X4 0 0 -1/24 1 1/3 1500 F2-F1
X2 0 1 0 0 1 6000
Estadístico Rolando R. Romero Paredes
Solución final
Como todos los coeficientes de la fila de la función objetivo
son positivos, hemos llegado a la solución óptima.
X1 = 500
X2 = 6000
La solución óptima viene dada por el valor de Z en la
columna de los valores solución, en nuestro caso: 21000.
Estadístico Rolando R. Romero Paredes
Bibliografía
• HILLIER, FREDERICK S. (2010) Introducción a la
investigación de operaciones, McGraw-Hill.
• EPPEN, G.D. (2000) Investigación de operaciones en la
ciencia administrativa. PRENTICE-HALL, México.
• WINSTON, WAYNE L. (2008) Investigación de
operaciones, Thomson Learning.
Estadístico Rolando R. Romero Paredes
Estadístico Rolando R. Romero Paredes
Estadístico Rolando R. Romero Paredes
Estadístico Rolando R. Romero Paredes
