INSTITUTO TECNOLÓGICO
SUPERIOR DE ACAYUCAN
Optimización De Procesos
Ing. Erika Del Carmen Reyes Gómez
Método De Descomposición Lineal
Integrantes:
Cruz Sánchez Marisol Maldonado Carlin Jailene Prieto Nolasco Luis Gerardo
Antonio Salgado José Manuel Martínez Llano Karen Janeth Reyes Serrano Gezih Vanessa
Método De
Descomposición
Lineal
DESCOMPOSICIÓN LINEAL El método de descomposición
lineal viene a ser un
mejoramiento del método
simplex revisado en ciertos
MÉTODO DE
casos. Resulta que mientras
más grande es la matriz A,
A continuación se también es mayor el número
muestra un esquema de ceros en la misma. Es
de descomposición decir, por regla general, a
lineal: medida que la matriz de
coeficientes adjuntos
aumenta (por tenerse más
actividades y más
restricciones).
3
EL MODELO MATEMÁTICO
CORRESPONDIENTE ES:
• Se agregan las variables de holgura
y de exceso que sean necesarias
para convertir todas las
desigualdades en ecuaciones.
• El principio de descomposición se
basa en representar todo el
problema en función de los puntos
extremos de los conjuntos DjXj ≤ bj ,
Xj ≥ 0, para hacerlo, se debe acotar
el espacio de soluciones definido
por cada DjXj ≤ bj , Xj ≥ 0 .
• Siempre se puede satisfacer este requisito para
cualquier conjunto j, agregando la restricción artificial
1Xj ≥ M, siendo M suficientemente grande.
4
EJEMPLO
Resolver la siguiente programación lineal
con el algoritmo de descomposición: • Los estudios de pozos vecinos
para la tasa m/h de barrenas
seleccionadas.
Para una perforación (On Shore) de 3000 mt.
Se requieren barrenas ticónicas; barrenas de Tipo de Barrena A B C D
insertos, barrenas de cortadores fijos y Barrena ticónica 1 1 1 1
barrenas PDC. Para aumentar la eficiencia en
la selección se analizan 4 datos obtenidos de Barrena de insertos 5 1 0 0
pozos vecinos: A, B, C, D. cada barrena
Barrena de cortadores
seleccionada debe contar con no más de 40 0 0 1 1
fijos
unidades de barrenas ticónicas, no exceder la
cantidad de 12 u. de barrenas de insertos, una Barrena PDC 0 0 1 5
cantidad mínima de 5 u. de barrenas de Tasa m/h (Barrena) 3 5 1 1
cortadores fijos y no pasar del a cantidad de
50 u. de (PDC).
5
PROBLEMA
Maximizar La Tasa De Perforación M/H Con La Cantidad
De Barrenas Seleccionadas.
Desarrollo:
• X1 = Cantidad de Barrenas en A (m/h).
• X2 = Cantidad de Barrenas en B (m/h).
• X3 = Cantidad de Barrenas en C (m/h).
• X4 = Cantidad de Barrenas en D (m/h).
• F.O. Maximizar Z = 3X1 + 5X2 + X3 + X4
6
Sub problema 1 Sub problema 2 Solución básica de
arranque.
β1,1 β1,2 ………… β1,k β1,1 β1,2 ……. β1,k X5 X6 X7
C1 X11 C1X12…A1X1k C2X21 C2X22 C2Xk 0 -M -M
A1X11 A1 X12 .…. A1X1k A1X11 A1X12…..A1X1k 1 0 0 =40
1 1 ……. 1 0 0 ….… 0 0 1 0 =1
0 0 ….… 0 1 1 ……. 1 0 0 1 =1
C1 = (3,5) C1 = (3,5)
A1 = (1,1) A1 = (1,1)
Espacio de soluciones,D1X1 ≤ b1: Espacio de soluciones,
D2X2≤b2:
5X1 + X2 ≤ 12
X3 + X 4 ≥ 5
X1 ,X2 ≥ 0
X3 + 5X4 ≤ 50
X3, X4 ≥ 0
Añadimos las variables auxiliares X5, X6, X7, y transformamos en igualdad.
7
ITERACION
Iteración 1
ES
• XB = (X5, X6, X7) = (40, 1,1)
• CB = (0, -M, -M) B = (B)-1 = I
Iteración 1. ( j = 1 ). Se tiene:
Entonces la programación
lineal correspondiente es:
• Minimizar w1 = -3X1 – 5X2 – M
• S.a. 5X1 + X2 ≤ 12
• X1, X2 ≥ 0
8
Sub-problema 2 ( j =2 ). La
programación lineal
asociada es:
En la iteración 3
Por tanto:
9
• Se puede calcular la solución óptima del problema original por
sustitución directa.
X1* = (X1, X2) = β11 X11 = 1(0,12) = (0,12)
X2*= (X3, X4) = β22X22 + β23X23
= (23/45)(50,0)+ (22/45) (5,0)
= (28,0)
10
Conclusión
• Luego de haber estudiado a profundidad estos temas o herramientas
para resolver sistemas de ecuaciones, se concluye que para resolver
estos sistemas de ecuaciones lineales existen diferentes métodos,
pero dependerá del gusto de cada persona elegir uno en específico.
Sin embargo, muchas veces la elección no será arbitraria, pues cada
método tiene sus ventajas y sus desventajas. Algunos métodos son
más exactos, otros más fáciles de programar, otros más cortos, etc.
Para ser capaces de elegir un método apropiado, lo primero que se
necesita es comprender cómo se desarrolla cada uno de estos
procesos.
11
GRACIA
S
