MÉTODO SIMPLEX
Definición.- Se entiende por programa lineal
aquel que:
Optimizar Z =
CX
St.
AX ≤ B
X ≥ 0
Optimizar Z =
CX (1)
St.
AX ≤ B (2)
X ≥ 0 (3)
Donde:
El término optimizar significa maximizar o minimizar la función objetivo
(1) La
función lineal se llama función objetivo
(2) Se
llaman restricciones
(3) Se
llaman condiciones de no-negatividad
X se denomina vector
de actividades, es un vector columna de n componentes que son variables de decisión
X = (X1, X2,…,
Xn)T
C Se llama vector
de precios o costos unitarios, es un vector renglón de n componentes
C = (C1,
C2,…, Cn)
b Se denomina vector
de disponibilidad de recursos, es un vector columna de n componentes
b = (b1,
b2,…, bn)T
0 vector columna de n ceros
A Matriz de coeficientes,
es una matriz con n columnas y m filas
aij Son elementos de A, para todo i = 1,
2,…, m j = 1,2,...., n representa la cantidad de recursos j que se necesita por
unidad de actividad i
FORMAS EQUIVALENTES DE PROGRAMCIÓN
LINEAL
El
siguientes PPL., se denomina forma canónica
Max Z=CX
s.a.
AX ≤ b
X ≥ 0
Cualquier
otra forma es equivalente a ella de acuerdo a las siguientes reglas:
Regla I
l. Maximizar
cX es equivalente a Minimizar -cX
2. Minimiza cX es
equivalente a maximizar -cX
Ejemplos
1. Máx 5X1+4X2 entonces Mín -5X1-4X2
2. Mín –X1+
4X2 entonces Máx X1-4X2
Regla II
1. La desigualdad
AX ≤ b es equivalentes a -AX ≥ -b
2. La desigualdad
AX≥ b es equivalentes a -AX ≤ -b
Ejemplos
1. -3X1
+ X2 ≤ -2 entonces 3X1 - X2 ≥ 2
2. 4X1+3X2
≥ 6 entonces -4X1 - 3X2 ≤ -6
Regla III
Toda
igualdad de la forma AX = b puede
descomponerse como la intersección de las restricciones AX ≥ b y AX ≤ b
Ejemplo
3X1 +
X2 = 3 entonces 3X1 + X2 ≥ 3, 3X1 + X2 ≤ 3
Regla IV
1. Toda desigualdad
de la forma AX ≤ b puede
convertirse en igualdad mediante la adición de un vector Y, llamado de defecto o holgura es un vector columna de m componentes
Yi, i= 1,2,…, m
2. Toda desigualdad
de la forma AX ≥ b puede
convertirse en igualdad mediante la resta de un vector Z, llamado de exceso o superfluo, es un vector columna de m
componentes
Z¡, i=1,2,...,m
Ejemplos
-X1 + X2 ≤ 2
-X1 + 2X2 ≤ 6
Es equivalente a
-X1 + X2 + X3 = 2
-X1 + X2 + X4 = 6
X3, X4 ≥ 0
3X1 + X2 ≥ 3
4X1 + 3X2 ≥ 8
Es equivalente a
3X1 + X2 – X3
= 3
4X1 + 3X2 – X4
= 8
X3, X4 ≥ 0
Regla V
Una variable
no restringida o sin restricción de signo es aquella que puede tomar toda clase
de valores positivos, cero o negativos y puede escribirse como la diferencia de
dos variables no negativas.
Ejemplo
Sea X1=
X2 - X3
Donde X2
≥ 0, X3 ≥ 0 entonces X1 ≥ 0
Si X2
= X3 entonces X1 =
0
Si X2
< X3 entonces X1 < 0
DEFINICIONES DE PROGRAMACIÓN LINEAL
· Solución factible.- una solución factible al PPL en una
forma canónica es el valor
XT =(X1, X2,…, Xn)
que satisface las restricciones AX ≤ b, X ≥ 0
·
Solución factible básica.- Es aquella solución factible con no más
de m componentes pasivas.
·
Solución factible básica no degenerada.- Es una solución factible básica
donde exactamente m componentes del vector X. Son positivas.
·
Solución factible básica degenerada.- Es una solución factible básica
donde hay menos de m componentes del vector X.
·
Reglón de factibilidad.- Es el conjunto de todas las soluciones
factibles.
FORMA ESTANDAR DE UN PPL
Un PPL está
en la forma estándar, si
1. La función
objetivo debe de determinarse.
2. Todos los
valores del lado derecho deben determinarse.
3. Todas las
restricciones son igualdades.
4. Todas las
variables son no negativas.
Máx Z = CX
St..
AX = b
X ≥ 0
Ejemplo
Forma
canónica del PPL
Máx 5X1 +4X2
St.
-3X1+ X2 ≤ 2
-X1 + X2 ≤ 3
-X1
+2X2 ≤ -2
X ≥ 0
Forma estándar
del PPL
Máx 5X1 +4X2
St.
-3X1+ X2 + S3 = 2
-X1 + X2 + S4 = 3
-X1 +2X2 + S5 =
-2
X1, X2, S3, S4,
S5 ≥ 0
· Definición.-
Variables no básica es un conjunto seleccionado de variables de un PL en forma
estándar (en número igual al total de variables menos el número de
restricciones de igualdad), cuyos valores se toman como cero, o sea:
Número de VNB = n – m
·
Definición.-
Variables básicas son las variables
restantes, diferentes a las no básicas de un PL en forma estándar ( igual al número
de restricciones de igualdad, o sea:
Número de VB=n-(n-m)=m
·
Definición.-
Se obtiene una solución básica de AX = b,
haciendo n - m variables iguales a cero y despejando las m variables que
quedan. Esto supone que si hacernos n - m variables iguales a cero, nos proporciona
valores únicos para las m variables restantes y equivalentemente las columnas
de las m variables restantes son linealmente independientes.
Sea por
ejemplo, las restricciones con dos ecuaciones y tres variables. Hallar las
soluciones básicas:
X1
+ X2 = 3
-X2 +
X3 = -1
Se tiene un
conjunto de 3 – 2 = 1 variables no básica. Por ejemplo VNB = {X3}, entonces
{X1, X2}, se tiene que, VNB: X3 = 0, VB: X1 = 2, X2 = 1.
Por tanto, X1
= 2, X2 = 1, X3 = 0 es una solución básica del sistema
dado.
Si escogemos
VNB = {X1}, entonces {X2, X3}, entonces la
solución básica es:
X1 =
0, X2 = 3, X3 = 2.
Si escogemos
VNB = {x2}, entonces la solución básica es:
X1
=3, X2 = 0, X3 = -1.
Algunos
conjuntos de m variables no producen una solución básica, por ejemplo el sistema:
X1
+ 2X2 + X3 = 1
2X1+
4X2 + X3 = 3
Si seleccionamos
VNB = {X1} entonces VB = {X1, X2}, entonces la
solución básica se obtendría al resolver el sistema:
X1
+ 2X2= 1
2X1+
4X2= 3
Ya que ésta sistema
no tiene solución, no existe una solución básica correspondiente a
VB = {X1,
X2}
Definición:
Cualquier
solución básica de
MáX Z=CX
St.
AX= b
X ≥ = 0
En la cual
todas las variables son no-negativas se una solución básica factible (sbf).
El primer problema
las sbf son: X1= 1, X2 =2, X3 = 0 y X1
= 0, X2 = 3, X3=2, pero la solución
X1
= 3, X2 = 0, X3 = -1 no es una sbf porque X3
< 0
Teorema 1
La región
factible para cualquier PPL es un conjunto convexo. También, si un PPL tiene
una solución óptima, tendrá que existir un punto extremo de la región de
factibilidad que es óptimo.
Teorema 2
Para
cualquier PPL existe un punto extremo único de la región de factibilidad del PL
que corresponde a cada solución básica factible. También existe por lo menos
una sbf que corresponde a cada punto extremo de la región factible.
Ejemplo.
Sea el PPL
Máx 4X1
+ 3X2
St.
X1
+ X2 ≤ 40
2X1
+ X2 ≤ 60
X ≥ 0
Forma
estándar del PPL
Máx 4X1 + 3X1
St.
X1 + X2 + S3 =
40
2X1
+ X2 + S4 = 60
X1,
X2, S3, S4 ≥ 0
La región de
factibilidad es el cuadrilátero sombreado, cuyos puntos extremos y las sbf son
las que se dan en el cuadro, siendo la solución óptima del problema el punto X1
= X2 = 20 y el valor óptimo de la función objetivo z = 140
Conclusión: Para hallar la solución óptima de un
PPL, solamente hay que hallar la mejor solución básica factible (el mayor valor
de Z en problemas de maximización y el menor valor de Z en problemas de
minimización) de AX = b
MÉTODO SIMPLEX
Si un PPL en
forma estándar tiene m restricciones y n viables, puede haber una solución básica
para cada selección de las variables no básicas, Se puede escoger un conjunto n
– m variables no básicas (o equivalentemente, m variables básicas) de entre las
n variables.
Cn,m = n! / (n-m)!m!
Maneras
diferentes. Así un PL puede tener a lo más Cn,m
soluciones básicas. Ya que algunas soluciones básicas pueden no ser factibles
un PL puede tener a lo más Cn,m
soluciones básicas factibles. Por ejemplo, sea un PL en forma estándar que
tiene n = 20 variables m = 10 restricciones, se tiene que C20,10 = 184
756 soluciones básicas factibles.
La
experiencia con el algoritmo simplex demuestra que una solución óptima se
encuentra después de examinar 3m soluciones básicas factibles o sea 3(10) = 30
sbf que comparando con 184 756, se concluye que el método simplex es mejor.
PASOS DEL ALGORTTMO SIMPLEX
Sea el PPL
en su forma canónica
Máx Z = CX
St.
AX ≤ B
X ≥ 0
Para aplicar
el método simplex, siga los pasos siguientes:
1. Escriba el
PPL es forma estándar.
2. Escribir la
función objetivo: Z-CX=0
3. Escribir
los coeficientes del programa en el formato de la tabla siguiente.
Variables
originales Variables de holgura
|
|
Z
|
X1
X2 … Xn
|
S1
S2 …
Sn
|
Z
|
|
Z
|
1
|
Z1-C1 Z2-C2 … Zn-Cn
|
Z1-C1 Z2-C2 … Zn-Cn
|
CBB-1b
|
|
S1
|
0
|
B-1 A
|
B-1
|
B-1b
|
|
S2
|
0
|
|||
|
.
.
.
|
.
.
.
|
|||
|
Sn
|
0
|
4. Para que
sbf (si es posible a partir de la forma estándar)
5.
Determinar si la sbf es la solución óptima
6. Si sbf no es óptima, determine que variable
no básica se tiene que convertir en una variable básica y que variable básica se tiene que
convertir en variable no básica para encontrar una nueva sbf con un mejor valor
de la función objetivo.
TABLERO DEL MÉTODO SIMPLEX
En el modelo
Máx z = CX
St.
AX ≤ B
X ≥ 0
Si el vector
X se particiona en XB= VB y
XN = VNB y la matriz A se
particiona en B = Matriz de coeficientes
básicos y N = Matriz de coeficientes
no básicos, entonces se tiene:
AX = BXB + NXN =
b, pero XN = 0, entonces BXB = b y haciendo
transformaciones matriciales se tiene B-1B
XB = B-1b, se obtiene XB = B-1b
También, a
partir de la función objetivo se tiene:
Z =CBXB + CNXN si CNXN = 0.
Entonces se obtiene Z = CBXB, Z = B-1b
|
|
Z
|
X1
X2 … Xn
|
S1
S2 … Sn
|
Z
|
|
Z
|
1
|
CBB-1 A-C
|
CBB-1
|
CBB-1b
|
|
Si
|
0
|
B-1 A
|
B-1
|
B-1b
|
En general
|
|
Z
|
X1
X2 … Xn
|
S1
S2 … Sn
|
Z
|
|
Z
|
1
|
Z1-C1 Z2-C2 … Zn-Cn
|
CBB-1
|
Z*
|
|
Si
|
0
|
B-1 A
|
B-1
|
XB*
|
Regla para la variable del vector que
entra a la base
Seleccione aquel
vector aj en N que tenga la zj – cj (más
negativo)
Regla de salida del vector de la base
Una vez que sabe
que vector aj va a entrar a la base
nueva B, sáquese aquel vector ai en B que cumpla con la siguiente condición:
XBj /
Yij = min {XBj / Yij, Yij > 0}
Teorema 3
La solución
óptima del PL canónico se obtiene cuando todas las zj cj ≥ 0, para toda j en N.
Ejemplo 1:
Hallar la
solución óptima del PPL
Máx Z = 3X1 + 2X2 + X3
St.
X1 + 2X2 + X3 ≤ 10
X1 + X2 + 2X3
≤ 9
2X1 + 3X3 ≤ 12
Xi ≥ 0, i = 1, 2, 3
Paso 1: Forma estándar del PPL
Máx Z = 3X1 + 2X2 + X3
St.
X1 + 2X2 + X3 + X4 = 10
X1 + X2 + 2X3 + X5 = 9
2X1 + 3X3 + X6 = 12
Xi ≥ 0, i = 1, 2, 3… 6
Paso 2: Pasando el lado derecho de la
función objetivo al primer miembro
Z - 3X1 - 2X2 - X3 =
0
St.
X1 + 2X2 + X3 + X4 = 10
X1 + X2 + 2X3
+ X5 = 9
2X1 + 3X3 + X6 = 12
Xi ≥ 0, i = 1, 2, 3… 6
Paso 3: Pasando los coeficientes a la tabla
|
|
Z
|
X1
X2 X3
|
X4 X5 X6
|
Z
|
|
Z
|
1
|
-3 -2 -1
|
0 0 0
|
0
|
|
X4
X5
X6
|
0
0
0
|
1
2 1
1 1 2
2 0 3
|
1
0 0
0
1 0
0 0 1
|
10
9
12
|
Paso 4: Elección de la variable que entra a
la nueva solución. El más negativo es:
Z1
- C1 = -3 Entones entra X1
Paso 5: Elección de la variable que dejará
la solución actual,
Min {10/1,
9/1, 12/2} = 6 por lo tanto, sale X6
Paso 6: Reemplazando X6 por X1
y multiplicando la fila 4 por 1/2 se tiene:
|
|
Z
|
X1
X2 X3
|
X4 X5
X6
|
Z
|
|
Z
|
1
|
-3 -2 -1
|
0 0 0
|
0
|
|
X4
X5
X1
|
0
0
0
|
1
2 1
1 1 2
1 0 3/2
|
1
0 0
0
1 0
0 0 1/2
|
10
9
6
|
Ahora
pivoteamos, hasta volver unitaria la columna de X1
|
|
Z
|
X1
X2 X3
|
X4 X5
X6
|
Z
|
|
Z
|
1
|
0 -2 7/2
|
0 0 3/2
|
18
|
|
X4
X5
X1
|
0
0
0
|
0
2 -1/2
0 1 1/2
1 0 3/2
|
1
0 -1/2
0
1 -1/2
0 0 1/2
|
4
3
6
|
Se ha
realizado la primera iteración, volvemos a al paso 4.
Paso 4: Seleccionamos la variable que entra
a la base. El más negativo de los elementos de la primera fila es: Z2-
C2 = -2, entonces entra X2
Paso 5: Elección de la vadeable que dejará
la solución actual.
Min {4/2,
3/1} = 2. Por tanto, sale X4
Paso 6: Reemplazando X4 por X2
y multiplicando la fila 2 por 1/2 y luego pivoteamos para volver unitaria la
columna 2
|
|
Z
|
X1
X2 X3
|
X4 X5
X6
|
Z
|
|
Z
|
1
|
0 0 3
|
1 0 1/2
|
22
|
|
X2
X5
X1
|
0
0
0
|
0
1 -1/4
0 0 3/4
1 0 3/2
|
1/2 0 -1/4
-1/2 1 -1/4
0 0 1/2
|
2
1
6
|
Hemos finalizado
la segunda iteración, volvamos al paso 4.
Paso 4: Al observar la primera fila, se
constata que ya no hay elementos negativos, es decir,
Zj – Cj ≥ 0 para toda j en N, lo que quiere
decir que ya no es posible incrementar el valor de la función objetivo
La solución
óptima es X* = (X1*, X2*,
X3*) T = (6, 2, 0) T, X4 = X6
= 0, X5 = 1 y el valor de la función objetivo es: Z* =22
Aquí van los anuncios
Comentarios