Ingeniería Industrial
Pregrado
Pregrado
Sesión: 03
EL METODO SIMPLEX Y LA PROGRAMACION LINEAL ENTERA
Ingeniería Industrial
TEMARIO Pregrado
Tema 1: El método simplex
Tema 2: Método simplex (caso maximización con restricciones ≤)
Tema 3:Modelos de programación lineal entera
Tema 4:Técnica de ramificación y acotamiento (branch and bound)
Tema 5:Solucion de modelos de PL con software (SOLVER)
2
Ingeniería
Pregrado
Industrial
Logro de Aprendizaje
Logro:
Al finalizar la sesión, el estudiante conoce la utilidad del software y
aplicación del algoritmo simplex como método de solución de
modelos lineales y las aplicaciones de la programación lineal entera
DÍA EL
CASO MOTIVACIONAL:
Fabrica de maletines
Un empresario se dedica a la fabricación de maletas, maletines y mochilas.
La elaboración incluye piel y materiales sintéticos, y la piel es la materia prima
escasa. El proceso de producción requiere dos tipos de mano de obra
calificada: costura y acabado
La siguiente tabla da la disponibilidad de los recursos, su consumo por los
tres productos y las utilidades por unidad:
Recurso Mochila Maletín Maleta Disponibilidad
diaria
Piel (mts. cuadrados) 2 1 3 42 mts. cuadrados
Costura (hrs.) 2 1 2 40 hrs.
Acabado (hrs.) 1 0.5 1 45 hrs.
Precio de venta ($) 24 22 45
PREGUNTAS:
• Pregunta 1:¿Cuántas artículos de cada tipo deben
producirse para obtener el máximo ingreso y cual es
N° 1 este?
• Pregunta 2: ¿Cómo se formulará el modelo?
N° 2
• Pregunta 3: ¿Qué método empleará para resolver el
caso? ¿Sera posible resolverlo con método grafico?
N° 3
METODO SIMPLEX
El Método Simplex es un método
analítico de solución de problemas de
programación lineal capaz de resolver
modelos más complejos que los resueltos
mediante el método gráfico sin
restricción en el número de variables.
METODO SIMPLEX
El método Simplex requiere que las restricciones
sean ecuaciones (o restricciones con relación de
igualdad) en vez de inecuaciones (o restricciones con
relación de desigualdad).
Cualquier inecuación puede ser convertida en una
ecuación agregando una cantidad no negativa en el
lado de menor valor de la inecuación. Esta cantidad
no negativa se llama variable de holgura.
METODO SIMPLEX (modelo en forma canónica)
Maximizar Z = C1 X1 + C2 X2 + .... + Cn Xn
Sujeto a :
a11 X1 + a12 X2 + .... + a1n Xn ≤ b1
a21 X1 + a22 X2 + .... + a2n Xn ≤ b2
…… ……. …….. ….
am1 X1 + am2 X2 + .... + amn Xn ≤bm
Xj > 0 j = 1, 2, 3, ...., m+n
METODO SIMPLEX (modelo en forma estándar)
Maximizar Z= C1 X1 + C2 X2 + .... + Cn Xn + Cn+1 S1 + Cn+1 S2 + ......... + Cn+m Sn+m
Sujeto a :
a11 X1 + a12 X2 + .... + a1n Xn + Xn+1 (=S1) = b1
a21 X1 + a22 X2 + .... + a2n Xn + Xn+2 (=S2) = b2
…… ……. …….. …. .....
am1 X1 + am2 X2 + .... + amn Xn + Xn+m (=Sm) = bm
Xj > 0 Sj ≥ 0 , j = 1, 2, 3, ...., m+n
Ejemplo 1:
Dado el siguiente modelo de P.L. a resolverse con método simplex:
máx. Z=50x1+80x2
s.a. x +2x ≤120
1 2
Forma canónica
x1+ x2 ≤90
x1,x2≥0
Forma estándar
Luego, incorporando las variables de holgura S1 y S2 al
MPL, tenemos:
Max. Z=50x1+80x2 Max. Z = 50x1 + 80x2 +0S1+0S2
x1+2x2≤120 1x1+ 2x2 + 1S1 + 0S2 =120
x1+ x2 ≤90 1x1+ 1x2 + 0 S1 + 1S2 =90
X1 0, X2 0 X1 0, X2 0, S1 0, S2 0
Donde S1 y S2 : son variables de holgura
TABLA SIMPLEX
Cj C1 C2 .... Cn Cn+1 Cn+2 ....Cn+m
CB VB X1 X2 .... Xn Xn+1 Xn+2 ....Xn+m B
Cn+1 Xn+1 a11 a12 ....a1n 1 0 ....0 b1
Cn+2 Xn+2 a21 a22 ....a2n 0 1 ....0 b2
.... .... .... .... .... .... .... .... ....
.... .... .... .... .... .... .... .... ....
Cn+m Xn+m am1 am2 ....amn 0 0 ....1 bm
Zj Z1 Z2 ....Zn Zn+1 Zn+2 ....Zn+m CBTB
Cj - Zj C1-Z1 C2-Z2 ....Cn-Zn Cn+1-Zn+1 Cn+2-Zn+2 Cn+m-Zn+m
En este problema habrá m variables básicas con un valor
positivo y n variables no básicas con valor cero, para que
exista una solución básica factible.
EJEMPLO 2:
Se tiene el siguiente modelo Luego, incorporando las variables de
de programación lineal, en holgura se convierte el modelo de PL en
su forma canónica: su forma estándar:
Max. Z = 200 X1 + 240 X2 Max. Z = 200 X1 + 240 X2 + 0 S1 + 0 S2
Sujeto a: Sujeto a:
6 X1 + 12 X2 ≤ 120 6 X1 + 12 X2 + 1 S1 + 0 S2 = 120
8 X1 + 4 X2 ≤ 64 8 X1 + 4 X2 + 0 S1 + 1 S2 = 64
X1≥ 0, X2 0
X1 0, X2 0, S1 0, S2 0
ITERACION 0
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
0 S1 6 12 1 0 120
0 S2 8 4 0 1 64
Zj 0 0 0 0 0
Cj - Zj 200 240 0 0 Cj-Zj<0
ITERACION 0
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
0 S1 6 12 1 0 120
0 S2 8 4 0 1 64
Zj 0 0 0 0 0
Cj - Zj 200 240 0 0 Cj-Zj<0
Se elige
el mayor
Cj-Zj
ITERACION 0
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
0 S1 6 12 1 0 120
0 S2 8 4 0 1 64
Zj 0 0 0 0 0
Cj - Zj 200 240 0 0 Cj-Zj<0
Columna
pivote
ITERACION 0
Se elige
el menor
Cj 200 240 0 0 cociente
positivo
CB VB X1 X2 S1 S2 B
0 S1 6 12 1 0 120 120/12 =10 √
0 S2 8 4 0 1 64 64/4 =16
Zj 0 0 0 0 0
Cj - Zj 200 240 0 0 Cj-Zj<0
Columna
pivote
ITERACION 0
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
0 S1 6 12 1 0 120 Fila pivote
0 S2 8 4 0 1 64
Zj 0 0 0 0 0
Cj - Zj 200 240 0 0 Cj-Zj<0
Columna
pivote
Sale de la base
ITERACION 0 Entra a la base
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
F1 x 1/12
F1 0 S1 6 12 1 0 120
F2 0 S2 8 4 0 1 64 F1 x -1/3 +F2
Zj 0 0 0 0 0
Cj - Zj 200 240 0 0 Cj-Zj<0 Elemento
Pivote, cuyo objetivo
inicial será convertirlo
ITERACION 1 en 1, y los demás
elementos de esa
columna hacerlos
“cero”
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
240 X2 1/2 1 1/12 0 10
0 S2 6 0 -1/3 1 24
Zj 120 240 20 0 2400
Cj - Zj 80 0 -20 0 Cj-Zj<0
ITERACION 1
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
240 X2 1/2 1 1/12 0 10
0 S2 6 0 -1/3 1 24
Zj 120 240 20 0 2400
Cj - Zj 80 0 -20 0 Cj-Zj<0
Se elige
el mayor
Cj-Zj
ITERACION 1
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
240 X2 1/2 1 1/12 0 10
0 S2 6 0 -1/3 1 24
Zj 120 240 20 0 2400
Cj - Zj 80 0 -20 0 Cj-Zj<0
Columna pivote
ITERACION 1 Se elige
el menor
Cj 200 240 0 0 cociente
positivo
CB VB X1 X2 S1 S2 B
240 X2 1/2 1 1/12 0 10 10/(1/2) = 20
0 S2 6 0 -1/3 1 24 24/6 = 4 √
Zj 120 240 20 0 2400
Cj - Zj 80 0 -20 0 Cj-Zj<0
Columna pivote
ITERACION 1
Cj 200 240 0 0
Fila pivote
CB VB X1 X2 S1 S2 B
240 X2 1/2 1 1/12 0 10
0 S2 6 0 -1/3 1 24
Zj 120 240 20 0 2400
Cj - Zj 80 0 -20 0 Cj-Zj<0
Columna pivote
ITERACION 1
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
240 X2 1/2 1 1/12 0 10 F2 x -1/12+F1
0 S2 6 0 -1/3 1 24 F2 x 1/6
Zj 120 240 20 0 2400
Cj - Zj 80 0 -20 0 Cj-Zj<0
ITERACION 2
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
240 X2 0 1 1/9 -1/12 8
200 X1 1 0 -1/18 1/6 4
Zj 200 240 140/9 40/3 2720
Cj - Zj 0 0 -140/9 -40/3 Cj-Zj<0
ITERACION 2 (final)
Cj 200 240 0 0
CB VB X1 X2 S1 S2 B
240 X2 0 1 1/9 -1/12 8
200 X1 1 0 -1/18 1/6 4
Zj 200 240 140/9 40/3 2720
Cj - Zj 0 0 -140/9 -40/3 Cj-Zj<0
Ya que todos los Cj – Zj, 0 entonces la tabla es óptima.
La respuesta final es: X1 = 4 y X2 = 8 (variables básicas) y S1 = S2 = 0
(variables no básicas), y el valor de Z = 2720.
SOLUCION CON POM QM FOR WINDOWS
SOLUCION CON POM QM FOR WINDOWS
SOLUCION CON POM QM FOR WINDOWS
SOLUCION CON POM QM FOR WINDOWS
SOLUCION CON POM QM FOR WINDOWS
La respuesta final
es: X1 = 4 y X2 = 8
(variables básicas)
y S1 = S2 = 0
(variables no
básicas), y el valor
de Z = 2720
EJEMPLO CON 3 VARIABLES:
Una empresa que produce guitarras de 3 tipos: eléctricas, acústicas y
electroacústicas, utiliza para su elaboración madera, mano de obra y metal.
Las cantidades de estos materiales que se precisan para realizar una unidad
de cada instrumento musical se muestran en la siguiente tabla:
Guitarra eléctrica Guitarra Guitarra
acústica electroacústica
Madera 1 2 1
Mano de obra 1 2 2
Metal 1 1 1
La empresa dispone de 50 metros cuadrados de madera, 60 horas de trabajo
y 55 metros cuadrados de metal y vende las guitarras eléctricas a 200
dólares, las acústicas a 175 dólares y las electroacústicas a 125 dólares.
Encontrar la producción de guitarras de tal forma que maximice los ingresos
para la empresa.
Variables de decisión:
Sea x1: numero de guitarras eléctricas a producir
x2: numero de guitarras acústicas a producir
x3: numero de guitarras electroacústicas a producir
modelo de P.L. a resolverse con método simplex:
máx. Z=200x1+175x2+125x3
s.a.
x1+2x2+x3 ≤50
x1+2x2+2x3≤60 Forma canónica
x1+ x2+ x3≤55
x1,x2,x3≥0
Forma estándar
máx. Z=200x1+175x2+125x3 +0s1+0s2+0s3
s.a.
1x1+2x2+1x3+1s1+0s2+0s3 =50
1x1+2x2+2x3+0s1+1s2+0s3=60
1x1+1x2+1x3+0s1+0s2+1s3=55
x1,x2,x3 s1,s2,s3 ≥0
ITERACION 0
Cj 200 175 125 0 0 0
CB VB X1 X2 X3 S1 S2 S3 B
0 S1 1 2 1 1 0 0 50
0 S2 1 2 2 0 1 0 60
0 S3 1 1 1 0 0 1 55
Zj 0 0 0 0 0 0 0
Cj - Zj 200 175 125 0 0 0 Cj-Zj<0
ITERACION 0
Cj 200 175 125 0 0 0
CB VB X1 X2 X3 S1 S2 S3 B
0 S1 1 2 1 1 0 0 50 50/1=50 Fila pivote
MENOR COCIENTE
0 S2 1 2 2 0 1 0 60 60/1=60
0 S3 1 1 1 0 0 1 55 55/1=55
Zj 0 0 0 0 0 0 0
Cj - Zj 200 175 125 0 0 0 Cj-Zj<0
ITERACION 1 Columna pivote
Cj 200 175 125 0 0 0
CB VB X1 X2 X3 S1 S2 S3 B
200 X1 1 2 1 1 0 0 50
0 S2 0 0 1 -1 1 0 10
0 S3 0 -1 0 -1 0 1 5
Zj 200 400 200 200 0 0 10000
Cj - Zj 0 -225 -75 -200 0 0 Cj-Zj<0
ITERACION 1
Cj 200 175 125 0 0 0
CB VB X1 X2 X3 S1 S2 S3 B
200 X1 1 2 1 1 0 0 50
0 S2 0 0 1 -1 1 0 10
0 S3 0 -1 0 -1 0 1 5
Zj 200 400 200 200 0 0 10000
Cj - Zj 0 -225 -75 -200 0 0 Cj-Zj<0
Ya que todos los Cj – Zj, 0 entonces la tabla es óptima.
La respuesta final es: X1 = 50, S2 =10 y S3 = 5 (variables básicas) y X2=X3=S1=0 (variables no
básicas), y el valor de Z = 10000.
La empresa debe fabricar 50 guitarras eléctricas de tal forma que su ingreso máximo sea de 10000
dólares, teniendo en cuenta que existe una disponibilidad restante de 10 horas de mano de obra y 5
metros cuadrados de metal para ser utilizados en otras actividades.
SOLUCION CON POM QM FOR WINDOWS
SOLUCION CON POM QM FOR WINDOWS
SOLUCION CON POM QM FOR WINDOWS
SOLUCION CON POM QM FOR WINDOWS
La empresa debe
fabricar 50 guitarras
eléctricas de tal
forma que su
ingreso máximo sea
de 10000 dólares.
teniendo en cuenta
que existe una
disponibilidad
restante de 10 horas
de mano de obra y 5
metros cuadrados
de metal para ser
utilizados en otras
actividades.
SOLUCION DE
MODELOS DE
PROGRAMACION
LINEAL ENTERA
UN CASO EL CARPINTERO (TOMADO DEL EJEMPLO 2 DE
LA SESION 1)
El Modelo matemático quedo La solución del modelo aplicando método
expresado de la siguiente manera: grafico se muestra con salida de php
simplex:
Variables:
x1: número de sillas a producir
x2: número de mesas a producir
Función objetivo:
Max. Z = 4x1 + 8,5x2
Restricciones:
R1: 4x1 + 9,5x2 ≤ 38
R2: x1 + x2 ≤ 7,5
Condiciones de no negatividad:
x1 ≥ 0; x2 ≥ 0
EL CARPINTERO (TOMADO DEL EJEMPLO 2 DE
LA SESION 1)
UN CASO
Como se puede apreciar en la solución del modelo
matemático las variables han reportado valores positivos,
dadas las condiciones de no negatividad. Pero además se
aprecia que son valores en notación decimal o fraccionaria.
Entendiendo que el numero de sillas y mesas que el
carpintero debe producir debe ser un numero positivo pero
además de ello entero.
PREGUNTA:
• ¿Consideraría ud. aproximar ambos
valores a enteros?. ¿Por qué?
PROGRAMACION ENTERA
La programación entera tiene que ver con la
solución de problemas de programación
matemática, en las cuales algunas o todas
las variables, solo pueden tomar valores
enteros no negativos,
MODELO DE PROGRAMACION
LINEAL ENTERA (MPLE)
¿CÓMO RESOLVER UN PROBLEMA DE
PROGRAMACIÓN LINEAL ENTERA?
TECNICAS DE PROGRAMACION ENTERA
TÉCNICA DE RAMIFICACIÓN Y ACOTAMIENTO
BRANCH AND BOUND
Esta técnica consiste en construir un árbol de decisión
(ramificación) siguiendo luego en la dirección del árbol con
el mejor valor óptimo encontrado hasta el momento.
Procedimiento:
Ejemplo:
Una empresa elabora dos tipos de producto A y C. La capacidad de la línea A
es de siete unidades diarias, cada unidad de C requiere cuatro horas de tiempo
para el secado, y se dispone en total de 22 horas de secado al día. Además,
cada unidad de A requiere dos horas de secado para el pulido, y cada unidad
de C requiere tres horas de pulido. Se dispone en total 19 horas de pulido cada
día. Cada unidad de A produce una ganancia de $1, mientras que cada unidad
de C produce una ganancia de $3. La empresa desea establecer un programa
de producción diaria para maximizar las ganancias. ¿Cuánto debe producirse
de A y C?
Los datos organizados se presentan en la tabla adjunta:
PRODUCTO CAPACIDAD SECADO PULIDO UTILIDAD
(unidades/día) (horas) (horas) ($)
A 7 2 1
C 4 3 3
DISPONIBILIDAD 22 19
Modelo matemático:
Solución del modelo
con método grafico
SOLUCION CON MÉTODO DE
RAMIFICACIÓN Y ACOTAMIENTO
SOLUCION CON MÉTODO DE
RAMIFICACIÓN Y ACOTAMIENTO
SOLUCION CON MÉTODO DE
RAMIFICACIÓN Y ACOTAMIENTO
En resumen:
Para lograr una ganancia
máxima de $17 por día, se debe
producir 2 productos de A y 5
del producto B por día.
SOLUCION DEL MODELO CON LINGO
SOLUCION DEL MODELO CON LINGO
Para lograr una ganancia
máxima de $17 por día, se
debe producir 2 productos
de A y 5 del producto B por
día.
SOLUCION DE UN MODELO DE PL CON SOLVER
MODELO CON SOLVER
MODELO CON SOLVER
MODELO CON SOLVER
MODELO CON SOLVER
MODELO CON SOLVER
MODELO CON SOLVER
EJEMPLO CON SOLVER
Utilizaremos el modelo de PL del caso del carpintero:
EJEMPLO CON SOLVER
EJEMPLO CON SOLVER
EJEMPLO CON SOLVER
Por lo tanto, se deben fabricar 4 mesas y ninguna silla para obtener un beneficio
máximo de 34 dólares.
TRABAJO EN EQUIPO
Resolver los ejercicios propuestos de la
actividad semanal de la sesión 3
Escuela Profesional de
Ingeniería Industrial
GRACIAS POR SUATENCION.
DÍA EL
Ingeniería Industrial
Pregrado
¡Gracias!
