S05.S2 - Material

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.

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?
Unidad II
Análisis de sensibilidad
Semana 5 – Sesión 2: Método simplex

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?
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.

Método
Simplex

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.
...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.

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
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.

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
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

FORMA ESTANDAR:
24x1 + 8x2 + x3 ≤ 60000

x1 + x4 ≤ 2000
x2 + x5 ≤ 6000
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.
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:
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

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.
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.

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
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.
C.En 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.
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
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.

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
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.

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.


S05.S2 - Material

Cargado por

Copyright:

Formatos disponibles

S05.S2 - Material

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

S05.S2 - Material

Cargado por

Copyright:

Formatos disponibles

Estadístico Rolando R.

Estadístico Rolando R. Romero Paredes Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

Logro específico de aprendizaje:

Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

•Al finalizar la semana los alumnos aplican

Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

Variable que entra El coeficiente más El coeficiente más positivo

Estadístico Rolando R. Romero Paredes

Problema de enlatados de tomate,

Estadístico Rolando R. Romero Paredes

Maximizar Z = 1.2x1 + 3.4x2

Estadístico Rolando R. Romero Paredes

Se consideran los siguientes pasos:

Se introduce una variable de holgura por cada una de las

Estadístico Rolando R. Romero Paredes

24x1 + 8x2 + x3 ≤ 60000

Estadístico Rolando R. Romero Paredes

Cuando minimizamos se toma el valor (+) positivo de F.O. para convertirlo

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

Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

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

Por tanto, lo que va a determinar el final del proceso de aplicación del

Paso 4: Encontrar la variable de decisión que entra en la

B. Para encontrar la variable de holgura que tiene que salir de la base, se

Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

Paso 4: Encontrar la variable de decisión que entra

Z -1.2 0 0 0 3.4 20400 1. F0 + F3(3.4)

Estadístico Rolando R. Romero Paredes

Paso 4: Encontrar la variable de decisión que entra en la

A. La variable que entra en la base es X1, pasa a ser la columna pivote

B. Para calcular la variable que sale o la fila pivote, dividimos los

Estadístico Rolando R. Romero Paredes

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

Estadístico Rolando R. Romero Paredes

La solución óptima viene dada por el valor de Z en la

Estadístico Rolando R. Romero Paredes

• HILLIER, FREDERICK S. (2010) Introducción a la

Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

Estadístico Rolando R. Romero Paredes

También podría gustarte