Romero Pimentel Roberto 1
Matemticas para Optimizacin
16/09/2012
Solucin bsica factible inicial.
Recordamos que el mtodo simplex comienza con una solucin bsica factible.
Ax=b
Sea el sistema
m n
x 0 , donde
con
es un
vector
de
rango ( A , b ) =rango ( A )=m , de manera que
matriz invertible de orden
una solucin del sistema
Ax=b
es una matriz de orden
elementos,
se
A= [ B , N ] , donde
es una matriz de
sabe
que:
es una
m ( nm) . As,
es:
[]
[ B , N ] x B =b=B x B + N x N
Ax=b
pero
m m
xN
x N =0
; de manera que:
b=B x B x B=B1 b=b
Entonces,
x B=B1 b= b
Si adems
x B 0 , entonces se tiene una solucin bsica factible. Tambin se
se denomina solucin bsica del sistema
dice que se tiene una solucin bsica factible no degenerada cuando
Ax=b .
x B >0 , y
una solucin bsica factible degenerada cuando alguna de las componentes de
xB
es igual a cero.
Ahora bien, una vez que se tiene una solucin bsica factible, el mtodo
simplex se desplaza a una solucin bsica factible con mejor valor hasta que se
alcanza el ptimo.
Cuando se tiene un sistema
Ax b
siempre es posible llevarlo a la forma
estndar agregando un vector de variables de holgura
Ax + x h=b
x 0 ; xh 0
xh
de forma que:
Romero Pimentel Roberto 2
Matemticas para Optimizacin
16/09/2012
Se tiene entonces
claro que el vector
(A ,I )
xh
la nueva matriz de restricciones de
es de orden
m ( m+ n ) . Es
m , por tanto la matriz identidad es
I m . As
[]
[ A , I ] x =b
xh
es una formulacin estndar de PPL. Finalmente, si se toma como base al
vector
x h=b
x h , se tiene que:
x=0
Por lo que:
b=Ax + x h x h=b
Sin embargo, ocurre que en muchas ocasiones se presentan casos donde no es
x h=b . Por ejemplo, cuando
posible hacer
viola la restriccin de no negatividad
( xh 0)
b0
se tendra que
x h=b
que
Otro caso es cuando se tienen restricciones de la forma
Ax b , en donde es
necesario llevar el sistema a la forma estndar restando un vector de variables
de excedencia:
Axx e =b
x 0 ; xe 0
En este caso se tiene que:
[]
[ A ,I ] x =b
xe
Y eligiendo a
observa que:
xe
como vector de variables bsicas (es decir,
B=I ), se
Romero Pimentel Roberto 3
Matemticas para Optimizacin
16/09/2012
Axx e =b x e=b x e =b
En general, una vez que se tiene una formulacin en forma estndar:
min Z=cx
A
si la matriz
de orden
m n
I m ), es posible hacer
sujeto a :
Ax=b
x0
contiene una submatriz identidad de orden
B=I , de manera que:
x B=B1 b=I 1 b=b
Sin embargo, cuando esto no sucede que la matriz
presente una matriz
identidad se debe recurrir a variables artificiales con la finalidad de encontrar
una solucin bsica factible inicial para poder emplear el mtodo simplex y
encontrar la solucin del problema.
De forma general, la introduccin de variables artificiales ocurre de la siguiente
forma. Sea un PPL en forma estndar
Ax=b
x0
cuya matriz
Amn
no contiene una matriz identidad
( I m)
que permita
definir inmediatamente una solucin bsica factible inicial. Se introduce a la
formulacin un vector de variables artificiales
x a , evidentemente de orden
m , y se tiene entonces que
Ax + x a=b
x 0 ; xa 0
Resulta claro que ahora se puede definir una solucin bsica factible inicial,
dado que
[]
[ A , I ] x =b
xa
Romero Pimentel Roberto 4
Matemticas para Optimizacin
16/09/2012
Se puede tomar el vector
xa
como vector bsico, lo que implica que
I =B
A=N . As, se tiene que:
b=B x a x a=B1 b
pero
I =B , por lo que
x a=b
embargo, el introducir el vector
que es la solucin bsica factible inicial. Sin
xa
al sistema
Ax=b , en realidad conduce
a un problema distinto del problema original, de manea que slo se alcanzar
una solucin factible del problema original
Ax + x a=b
( Ax=b )
cuando se cumpla que
x a=0 .
con
En el Mtodo de dos fases lo que se busca es llevar las variables artificiales
xa
a un nivel de cero, y posteriormente encontrar la solucin ptima del
problema original.
Sea el problema
Ax + x a=b
; la fase I del mtodo encuentra una solucin
x=0 , x a=b . Ahora se busca minimizar los valores del vector
bsica factible
x a , es decir:
min x a
sujeto a :
Si mediante el mtodo simplex se llega a
[]
Ax + x a=b
x , xa 0
x a=0 , entonces es claro que:
[]
x
Ax + x a=b [ A , I ] x =b Ax=b [ B , N ] B =b
xa
xN
se continua con la fase II y la solucin bsica factible inicial para
es
x B=B b
x N =0 . De modo que el problema es:
Ax=b , que
Romero Pimentel Roberto 5
Matemticas para Optimizacin
16/09/2012
[ ] )
sujeto a :
x B + B1 N x N =B1 b ; ( B x B + N x N =b Ax=b )
xB , x N 0
min Z=c B x B +c N x N ; [ c B ,c N ]
xB
=cx
xN
Romero Pimentel Roberto 6
Matemticas para Optimizacin
16/09/2012
Ejemplo:
Problema de la dieta
Consiste en determinar una
dado de alimentos, de
nutricionales. La cantidad
nutricionales y los costos de
dieta de manera eficiente, a partir de un conjunto
modo que se satisfagan los requerimientos
de alimentos a considerar, sus caractersticas
pestos se muestran a continuacin:
3
1
Legumbre
s
(1
porcin)
5
2
32
2
Leche
(1 litro)
Niacina
Tiamina
Vitamin
aC
Costo
0.8
0.2
Requerimien
tos
Nutricionale
s
13
15
95
45
0.2
0.5
Naranjas
(unidad)
El modelo de programacin lineal es:
Parmetros:
aij : cantidad de nutrientei contenido en el alimento j
c j :costo unitariodel alimento tipo j
bi :requerimiento nutricional del nutriente tipoi
Variables:
x j :cantidad a comprar del alimento tipo j
Restricciones:
a ij x j b i
x j 0
Funcin objetivo:
minimizar c j x j
j
Finalmente, con respecto a los subndices, se tiene lo siguiente:
Romero Pimentel Roberto 7
Matemticas para Optimizacin
16/09/2012
i=1 niacina
i=2 tiamina
j=2 legumbres
i=3 vitaminaC
j=1 leche
j=3 naranjas
Por tanto, el modelo de programacin lineal es:
minimizar 2 x 1+0.2 x 2+ 0.5 x3
x 1+2 x 2+ 0.2 x 3 15
sujeto a :
32 x 1 +95 x 3 45
3 x1 +5 x 2+ 0.8 x 3 13
x1 , x2, x3 0
Se lleva el modelo a su forma estndar:
z2 x10.2 x 20.5 x 3=0
x 1+2 x 2+ 0.2 x 3e2=15
3 x1 +5 x 2+ 0.8 x 3e1 =13
32 x 1 +95 x 3e 3=45
[]
[ A ,I ] x =b
Se observa que el modelo tiene la forma
que como se ha
mencionado, no conduce a una solucin bsica factible inicial.
Se agrega un vector de variables artificiales:
z2 x10.2 x 20.5 x 3=0
x 1+2 x 2+ 0.2 x 3e2 +a 2=15
3 x1 +5 x 2+ 0.8 x 3e1 +a 1=13
32 x 1 +95 x 3e 3 +a3=45
x 1 , x 2 , x 3 , e 1 , e 2 , e3 , a1 ,a 2 , a3 0
Ahora se tiene un sistema
solucin bsica factible inicial
[]
[ A , I ] x =b
a
con lo que se puede obtener una
a=b , x=0
para despus minimizar (llevar a
cero) el valor de las variables artificiales. Es decir:
Romero Pimentel Roberto 8
Matemticas para Optimizacin
16/09/2012
minimizar a 1+ a2 +a3 Za 1a2a3=0
x 1+2 x 2+ 0.2 x 3e2 +a 2=15
3 x1 +5 x 2+ 0.8 x 3e1 +a 1=13
sujeto a :
32 x 1 +95 x 3e 3 +a3=45
x 1 , x 2 , x 3 , e 1 , e 2 , e3 , a1 ,a 2 , a3 0
Variables de
decisin
Variables de holgura, excedencia y artificiales
Base
x1
x2
x3
e1
e2
e3
a1
a2
a3
Soluci
n
-1
-1
-1
a1
0.8
-1
13
13
a2
0.2
-1
15
a3
32
95
-1
45
Se suman los renglones 1, 2 y 3 al rengln Z y se comienza el mtodo simplex
Variables de decisin
Variables de holgura, excedencia y artificiales
Bas
e
x1
x2
x3
e1
e2
e3
a1
36
96
-1
-1
-1
a1
0.8
-1
a2
0.2
-1
a3
32
95
a2
a3
Solucin
13
65/4
15
75
-1
45
9/19
Romero Pimentel Roberto 9
Matemticas para Optimizacin
16/09/2012
348/95
-1
-1
1/95
-96/95
-864/19
x3
1297/475
-1
4/475
4/475
1199/95
1199/475
a2
443/475
-1
1/475
-1/475
1416/95
708/95
x3
32/95
-1/95
1/95
45/95
-379/2375
2/5
-1
3/237
5
7/5
2428/237
5
29993/47
5
1297/237
5
-1/5
4/237
5
1/5
4/2375
1199/475
a2
-379/2375
2/5
-1
3/237
5
2/5
-13/2375
4682/475
2341/95
x3
32/95
-1/95
1/95
45/95
-1
-1
-483/475
-73
x2
443/950
-1/2
1/950
1/2
-1/950
708/95
e1
-379/950
-5/2
3/950
-1
5/2
-13/950
2341/95
x3
32/95
-1/95
1/95
45/95
x2
Por tanto, la solucin bsica factible inicial del problema de la dieta es:
x 1=0
x 2=
708
95
x 3=
45
95
e 1=
2341
95
e 2=0
e 3=0
