Embed Size (px)
Citation preview
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
1/57Universidad Politécnica de Madrid–Escuela Técnica Superior de Ingenieros IndustrialesGrado en Ingeniería en Tecnologías Industriales. Curso 2015-2016-3º
Matemáticas de Especialidad–Ingeniería Eléctrica
Dualidad en Programación Lineal
Métodos de puntos interiores
José Luis de la Fuente O’[email protected]@upm.es
Clase_dualidad_interior_2016.pdf
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
2/57
Índice
� Dualidad
� Dualidad y condiciones de óptimo
� El algoritmo dual del Símplex
� Métodos de punto interior
� Formulación del procedimiento general
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
3/57Dualidad� Asociado a cada problema de PL hay otro denominado dual. Así, el primal1
min. cTx
s. a Ax D bx � 0;
tiene el dual asociado (dual de Wolfe) Philip Starr Wolfe,EE.UU. 1927-.
max. L.x;�;�/
s. a rxL.x;�;�/D 0� � 0:
� La dualidad de Wolfe se refiere esencialmente a problemas convexos. Si no loson hay que estudiar una formulación más general.
1Con x 2 Rn, A 2 Rm�n; m > n.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
4/57
� Si el problema primal está formulado en forma estándar, la función de Lagrangees
L.x;�;�/ D cTx � �T .Ax � b/ � �Tx;donde L.x;�;�/ W Rn � Rm � Rn! R.
� El gradiente de esta función con respecto a x es
c �AT� � �:
� El problema dual es entonces, incorporando en la f.o. que el gradiente es cero,
max. bT�
s. a c �AT� � � D 0� � 0:
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
5/57
� El par primal–dual de un problema de Programación Lineal en forma estándares pues
(P) min. cTx (D) max. bT�s. a Ax D b s. a AT�C � D c
x � 0 � � 0:
� Recordemos una vez más:
Condiciones de Karush-Kuhn-Tucker x 2 Rn es el óptimo del problemaprimal
min. cTxs. a Ax D b
x � 0;si y sólo si existen vectores � y �, óptimos del problema dual, tales que:Ax D b; x � 0; (factibilidad del primal)AT�C � D c; � � 0; (factibilidad del dual)�ixi D 0; i D 1; : : : ; n; (holguras complementarias o gap de dualidad)
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
6/57� Ejemplo El problema
min. x1 C x2 C 5x3s. a x1 C x3 � 1
x2 C x3 � 2x1; x2; x3 � 0:
H)estándar
min. x1 C x2 C 5x3s. a x1 C x3 � x4 D 1
x2 C x3 � x5 D 2x1; x2; x3; x4; x5 � 0:
� Su función de Lagrange es
cTx � �T .Ax � b/ � �Tx:El gradiente de esta función con respecto a x es
c �AT� � � D
266641
1
5
0
0
37775 �26664
1 0
0 1
1 1
�1 0
0 �1
37775��1�2
��
26664�1�2�3�4�5
37775 :
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
7/57
� El problema dual es entonces
max. �1 C 2�2s. a ��1 � �1 D �1
� �2 � �2 D �1��1 � �2 � �3 D �5�1 � �4 D 0
C �2 � �5 D 0
�1; �2; �3; �4; �5 � 0:
Expresado en forma más compacta:
max. �1 C 2�2s. a ��1 � �1
� �2 � �1��1 � �2 � �5�1 � 0
�2 � 0
H)reorganizando
max. �1 C 2�2s. a �1 � 1
�2 � 1�1 C �2 � 5
�1; �2 � 0:
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
8/57
� Lo que ha dado lugar a la forma simétrica de la dualidad:
(P) min. cTx (D) max. bT�s. a Ax � b s. a AT� � c
x � 0 � � 0:
� Recordemos el par Primal-Dual.
(P) min. cTx (D) max. bT�s. a Ax D b s. a AT�C � D c
x � 0 � � 0:
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
9/57Interpretación geométrica
� Recordando las consideraciones geométricas de la PL, estudiemos
min. 18x1 C 12x2 C 2x3 C 6x4s. a 3x1 C x2 � 2x3 C x4 D 2
x1 C 3x2 � x4 D 2x1; x2; x3; x4 � 0:
� En el subespacio Im.A/, es
4.3 Relations to the Simplex Procedure 87
a3
a2
a1
a4
b
Fig. 4.2 The primal requirements space
The dual problem is shown geometrically in Fig. 4.3. Each column ai of theprimal defines a constraint of the dual as a half-space whose boundary is orthogonalto that column vector and is located at a point determined by ci. The dual objectiveis maximized at an extreme point of the dual feasible region. At this point exactlytwo dual constraints are active. These active constraints correspond to an optimalbasis of the primal. In fact, the vector defining the dual objective is a positive linearcombination of the vectors. In the specific example, b is a positive combinationof a1 and a2. The weights in this combination are the xi’s in the solution of theprimal.
a3
a2
λ2
λ1
a1
b
a4
Fig. 4.3 The dual in activity space
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
10/57
� El dual es max. 2�1 C 2�2s. a 3�1 C �2 � 18
�1 C 3�2 � 12�2�1 � 2
�1 � �2 � 6:
Cada vector columna aidel primal define unacondición del dual.
4.3 Relations to the Simplex Procedure 87
a3
a2
a1
a4
b
Fig. 4.2 The primal requirements space
The dual problem is shown geometrically in Fig. 4.3. Each column ai of theprimal defines a constraint of the dual as a half-space whose boundary is orthogonalto that column vector and is located at a point determined by ci. The dual objectiveis maximized at an extreme point of the dual feasible region. At this point exactlytwo dual constraints are active. These active constraints correspond to an optimalbasis of the primal. In fact, the vector defining the dual objective is a positive linearcombination of the vectors. In the specific example, b is a positive combinationof a1 and a2. The weights in this combination are the xi’s in the solution of theprimal.
a3
a2
λ2
λ1
a1
b
a4
Fig. 4.3 The dual in activity space
El óptimo es un punto extremo deldual, en el cual hay dos condicionesactivas, que corresponden a una baseóptima del primal.b es una combinación lineal positivade a1 y a2.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
11/57� Ejemplo Un empresario quiere vender b1; b2; : : : ; bm unidades de mproductos.
� Contacta con un fabricante que se los puede elaborar realizando para ello nactividades distintas en sus fábricas. El coste (precio) unitario de cada actividadj se lo fija el fabricante al empresario en cj unidades.
� Si aij representa la cantidad del producto i que obtiene una unidad de laactividad j ,
PnjD1 aijxj son las unidades que se producen de i con todas las
actividades, que deben ser mayores o iguales que la cantidad requerida de bi .
� El problema del empresario es: min.
nXjD1
cjxj
s. anX
jD1aijxj � bi ; i D 1; 2; : : : ; m;xj � 0 j D 1; 2; : : : ; n:
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
12/57� Supóngase ahora que el empresario acuerda pagar al fabricante unos precios y1;y2; : : : ; ym por cada unidad de los m productos ya ensamblados.
� Si aij sigue siendo el número de unidades de i producidas por una unidad de laactividad j , la suma
PmiD1 aijyi es el ingreso del fabricante por cada unidad de
actividad j con los precios y1; y2; : : : ; ym. Ese ingreso no debe exceder al costereal cj .
� El fabricante deberá fijar los niveles de producción bi de cada producto i quemaximicen su ganancia
PmiD1 yibi .
El problema que se plantea el fabricante es el dual del del empresario:
max.mXiD1
yibi
s. amXiD1
aijyi � cj ; j D 1; 2; : : : ; n;yi � 0; i D 1; 2; : : : ; m:
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
13/57
El Programa primal trata en este caso sobre valores económicos.Garantizadas unas ventas mínimas de productos a unos precios, quéesquema concreto de producción minimiza el coste total, o maximiza el valoreconómico de la producción.
El Programa dual de cantidades físicas. Con un esquema de costesunitario dado, qué cantidades de productos producir a unos preciosconocidos para maximizar el beneficio de su venta.
� La teoría de dualidad es un elemento más para ayudar a analizar la sensibilidadde los problemas de PL, pues ayuda a responder, por ejemplo, a: 1. ¿De quéforma habrá que modificar nuestra cadena de producción los próximos seismeses si el beneficio de nuestro producto estrella cae un 20%? 2. O, dadanuestra disponibilidad de recursos, ¿qué beneficio o cuántas unidadesdeberíamos vender de un nuevo producto para hacerlo rentable?
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
14/57
Dualidad y condiciones de óptimo
Lema Dualidad débil Si x es una solución factible del problema primal e y una tambiénfactible del dual, bTy � cTx.
Corolario Si x es una solución factible del primal, y una también factible del dual ycTx D bTy , entonces x e y son los óptimos del primal y dual.
Teorema Teorema de la dualidad de la programación lineal(a) Si el problema primal o el dual tiene una solución óptima finita la tiene el otro ymKın cTx D mKax bTy .(b) Si el problema primal o el dual tiene una función objetivo no acotada el otro no tienesolución factible.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
15/57
� La diferencia entre el valor de la función objetivo del primal y la del dual es labrecha o gap de dualidad.
� El valor de la función objetivo de una solución factible del primal (dual)proporciona un cota superior (inferior) del valor de la función objetivo decualquier solución factible del dual (primal).
Teorema Condiciones de Karush-Kuhn-Tucker x 2 Rn es el óptimo del problemaprimal
min. cTxs. a Ax D b
x � 0;si y sólo si existen vectores � y �, óptimos del problema dual, tales que
Ax D b; x � 0; (factibilidad del problema primal)AT�C � D c; � � 0; (factibilidad del problema dual)�ixi D 0; i D 1; : : : ; n; (complementariedad o gap de dualidad)
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
16/57El algoritmo dual del Símplex
� Diseñado en 1954 por Carlton Eduard Lemke y Evelyn Martin Lansdowne Beale
Carlton Eduard Lemke, EE.UU. 1920-2004 y EvelynMartin Lansdowne Beale, Reino Unido, 1928-1985.
para cuando se tiene una solución básica no factible de un programa lineal y, sinembargo, los costes reducidos de las variables no básicas son todos óptimos,(� 0): los multiplicadores símplex son factibles en el programa dual.
� Esos casos son habituales en problemas de reoptimización donde al añadir, porejemplo, una nueva condición de desigualdad, no se cumple de partida.
� La base óptima del problema original y la nueva variable de holgura que seintroduzca constituirán la nueva base de partida del problema.
� Esta nueva base es óptima pero no factible pues la nueva variable de holguraes igual al negativo de lo que no se satisface la nueva restricción.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
17/57
� El algoritmo dual del Símplex, como el primal, progresa, de iteración eniteración, de una base a otra del problema, manteniendo la factibilidad delprograma dual, aplicando las condiciones de óptimo de Karush-Kuhn-Tuckerhasta que se llegue a una base factible en el primal y dual simultáneamente.
� Se comienza desde un punto en el que se satisfacen las condiciones de óptimoen el dual –costes reducidos no negativos–, pero no las del primal pues algunavariable en la base es negativa.
� Si hay una variable en la base no factible, xBp D�B�1b
�p< 0, 1 � p � m, p
será la “fila de pivotación” y el índice de aquella variable en la base que debesalir de ella.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
18/57
� De acuerdo con xB D B�1b �B�1NxN se tendrá que cada variable
xBp D�B�1b
�p� p̨j � xj ; 8j 2 N ;
donde p̨j es el coeficiente de la fila p del vector columna B�1Nj , con j 2 N .
� Clave: como la variable�B�1b
�p< 0, si hay algún p̨j < 0, j 2 N , es decir,
en el vector fila p-ésimo de B�1N , la variable no básica j podría incrementarsu valor (xj en la expresión anterior) desde cero, remplazando así en la base axBp que pasaría a ser cero.
El nuevo valor de la variable no básica xj sería.B�1b/p
p̨j> 0.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
19/57
� No todas las variables no básicas que cumplan que p̨j < 0, j 2 N soncandidatas a entrar en la base remplazando a la básica no factible.
� Han de cumplir las condiciones de factibilidad del dual (óptimas del primal) entérminos de costes reducidos. Si xj es la que entra, los nuevos costes reducidos,Nci , en función de los antiguos, Oci , saldrán de esta fórmula:
Ncl D Ocl � Ocj p̨l
p̨j
; l D 1; : : : ; n . Ncl D 0 si l D j /:
� Como todos los costes reducidos han de ser no negativos, la relación j Ocj= p̨j jque sea menor, con p̨j < 0, determina el coste reducido que antes alcanza ceroy, por lo tanto, la variable xq que entra en la base.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
20/57� El algoritmo dual del Símplex completo es este.
Paso 1 – Calcular el vector de multiplicadores símplex resolviendo el sistemaBT� D cB . Determinar los costes reducidos de las variables no básicas: Ncj D cj � �T aj , para todoj 2 N .
Paso 1’ – Comprobar la factibilidad del programa primal: Si xB � 0, PARAR; la solución es óptima. Si no,continuar.
Paso 2 – Determinar la variable básica xjp que debe salir de la base: Escoger jp 2 fji 2 B W xji< 0g:
Paso 3 – Comprobar la no factibilidad del problema: Calcular u resolviendo el sistema BT u D ep y hacerj̨ D uT aj , para todo j 2 N . Si j̨ � 0 para todo j 2 N , PARAR; el problema no tiene solución.
Paso 4 – Determinar la variable no básica xq que ha de entrar en la base: Calcular (para que sus costesreducidos sigan siendo de óptimo en todas menos en la q que pasará a 0)
� Ncq˛qD mKın
�� Ncj
j̨W j̨ < 0; j 2 N
�D � :
Paso 5 – Recalcular costes reducidos: Hacer Ncj Ncj � j̨ , j 2 N , j 6D q y Ncp � .Paso 6 – Adaptar la solución y la matriz B: Calcular w resolviendo Bw D aq y hacer
xq � D xjp=˛qxji xji
� �wi ; 1 � i � m; i 6D pB B C .aq � ajp /eTpB B [ fqgnfjpgN N [ fjpgnfqgjp q:
Ir al paso 1’.Algoritmo dual del Símplex
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
21/57
� Codificado para Matlab
function [x fobj pi sN iter B N Binv] = dual_simplex(c,A,b,eps1,B0)% Resuelve Max c’x subject to Ax = b, x >= 0 mediante Simplex Dual. B0 base de partida.[m,n]=size(A); c=c(:); b=b(:);%% Paso 0: Inicializar B, N, x_B y s_N -1 -TB = B0; N = setdiff(1:n,B); % x =B b, lambda=B cxB=A(:,B)\b; x=zeros(n,1); x(B)=xB; % B T By = A(:,B)’\c(B); sN = c(N)-A(:,N)’*y; % c =c -N lambda
% N Niter = 0; disp(’It. Sale B Entra B Pinf Ninf Cr-inf’);while 1 == 1 % Proceso iterativo
%% Pasos 1 y 2: Comprobar optimalidad; si no, ha de dejar la base x_{B(i)}[xBmin i] = min(xB); % Valor más negativo xbif xBmin >= -eps1 % No hay no factibles, final
fobj=c’*x; Binv=inv(A(:,B)); pi=Binv’*c(B); return, end%% Paso 3 y 4: Ver no facti. y la variable no básica que entra, x_{N(j)}e = zeros(m,1); e(i) = 1; % Negativos en vector T -Tv = A(:,B)’\e; % w = N B ew = A(:,N)’*v; % izz = find(w<-eps1);if isempty(zz), error(’Problema no factible’), end[t ii] = min(-sN(zz)./w(zz)); % Coste reducido relación con w menorj = zz(ii); % Entra no básica j%% Paso 5: Recalcular costes reducidos: la j la rel. menor; demás=ant.+t*wsN = sN + t*w; sN(j) = t;%% Paso 6: Adaptar solución, xB, y datos -1 -1 -1d = A(:,B)\A(:,N(j)); % x =B b-B N (B b/w(j))temp = B(i); B(i) = N(j); N(j) = temp; % B jtheta=xB(i)/w(j); xB=xB-theta*d; xB(i)=theta; x=zeros(n,1); x(B)=xB;iter = iter + 1;fprintf(’%3d%6d%7d %14.6f %3d %6d\n’,iter,temp,B(i),...
sum(x(x<0)),sum(x<0),sum(sN<0));end
end
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
22/57� Ejemplo Consideremos el siguiente problema:
min. �5x1 � x2 C 12x3s. a 3x1 C 2x2 C x3 D 10
5x1 C 3x2 C x4 D 16x1; x2; x3; x4 � 0:
y resolvámoslo mediante ProgLineal_3():
>> c=[-5 -1 12 0];A=[3 2 1 0;5 3 0 1];b=[10;16];B=[3 4];>> [sol fobj pi cr it B N]=ProgLineal_3(c,A,b,eps,B)It. Sale B Entra B Cos. red. fobj
1 4 1 -41.000000 40.0000002 3 2 -0.400000 -16.400000
sol =2200
fobj =-12
pi =10.0000-7.0000
cr =7.0000 2.0000
it =2
B =2 1
N =4 3
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
23/57� Ahora, añadimos una nueva columna al problema, de tal forma que quede:
min. �5x1 � x2 C 12x3 � x5s. a 3x1 C 2x2 C x3 C x5 D 10
5x1 C 3x2 C x4 C x5 D 16x1; x2; x3; x4; x5 � 0:
Lo podemos volver a resolver mediante ProgLineal_3():
>> c1=[c -1];>> B1=[1 2];>> A1=[A [1 1]’];>> [sol fobj pi cr it B N]=ProgLineal_3(c1,A1,b,eps,B1)It. Sale B Entra B Cre. fobj
1 2 5 -4.000000 -12.000000sol =
3.0000000
1.0000fobj =
-16pi =
0 -1cr =
12 1 2it =
1B =
1 5N =
3 4 2
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
24/57
� Añadamos ahora una inecuación y una columna al problema original:
min. �5x1 � x2 C 12x3s. a 3x1 C 2x2 C x3 D 10
5x1 C 3x2 C x4 D 16x1 C x2 � x5 D 5
x1; x2; x3; x4; x5 � 0:
Una solución de partida puede ser la del problema original Œ2 2 0 0�T , con unnuevo coeficiente que verifique la nueva condición; es decir,26664
2
2
0
0
�1
37775 :
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
25/57
� Como esta solución no es factible del primal, pero la base es óptima en elprimal, reoptimizamos con dual_simplex():
>> c2 = [c 0];>> b2 = [b; 5];>> B2=[1 2 5];>> A2=[A [0;0]; 1 1 0 0 -1]A2 =
3 2 1 0 05 3 0 1 01 1 0 0 -1
>> [x fobj pi cr it B N]=dual_simplex(c2,A2,...b2,sqrt(eps),B2)
It. Sale B Entra B Pinf Ninf1 5 4 -0.000000 1
x =-0.00005.0000
01.0000
0fobj =
-5.0000
pi =-4.00000.00007.0000
cr =16.00007.0000
it =1
B =1 2 4
N =3 5
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
26/57
� Efectuemos ahora un cambio en el término de la derecha:
min. �5x1 � x2 C 12x3s. a 3x1 C 2x2 C x3 D 11
5x1 C 3x2 C x4 D 16x1; x2; x3; x4 � 0:
� Reoptimizamos también mediante dual_simplex() pues habrá una nofactibilidad en el primal:
>> b3=[11;16];>> B3=[1 2];>> [x fobj pi cr iter B N Binv]=dual_simplex(c’,A,b3,eps,B3)It. Sale B Entra B Pinf Ninf1 1 3 0.000000 0
x =0
5.33330.3333
0fobj =
-1.3333pi =
12.0000-8.3333
cr =0.66678.3333
iter =1
B =3 2
N =1 4
Binv =1.0000 -0.6667
0 0.3333
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
27/57� Por último, vamos a estudiar un cambio en la función objetivo: el coeficiente dex3 pasa de ser 12 a 9.
min. �5x1 � x2 C 9x3s. a 3x1 C 2x2 C x3 D 10
5x1 C 3x2 C x4 D 16x1; x2; x3; x4 � 0:
Volvemos a reoptimizar con ProgLineal_3():
>> c4=[-5 -1 9 0];>> B4=[1 2];>> [sol fobj pi cr it B N]=ProgLineal_3(c4,A,b,sqrt(eps),B4)It. Sale B Entra B Cos. red. fobj
1 2 3 -1.000000 8.000000sol =
3.20000
0.40000
fobj =-12.4000
pi =9.0000
-6.4000cr =
0.2000 6.4000it =
1B =
1 3N =
2 4
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
28/57
El problema de la dieta (otra vez)
� Era este:
CA
RN
E
HA
RIN
AD
ES
OJA
SO
JAE
NG
RA
NO
MIN
ER
AL
ES
SA
L
AL
FAL
FA
VIT
AM
INA
S
FAC
TO
RD
EC
RE
CIM
IEN
TO
PE
SC
AD
O
Función objetivo 5,80 2,63 3,08 1,13 1,00 2,26 35,72 6,00 7,00
Cantidad total 1 1 1 1 1 1 1 1 1 = 100Alfalfa 1 � 1Vitaminas 1 � 1,1Factor de crecimiento 1 � 5Pescado 1 � 5Proteínas 0,55 0,450 0,500 0,17 0,25 0,25 0,63 � 43Riboflavina 0,26 0,130 0,120 0,70 41,6 2 0,20 � 70Niacina 0,23 0,090 0,045 0,14 20,4 0,4 0,25 � 45Ácido pantoténico 0,20 0,055 0,060 0,14 9 0,4 0,04 � 16Fósforo 0,40 0,065 0,060 0,26 0,02 0,1 0,05 0,30 � 14Calcio 0,80 0,025 0,020 3 0,15 0,05 0,05 0,50 � 35Sal 1 0,10 0,9 10 � 19Sal 2 0,10 0,9 10 � 24
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
29/57� Hagamos un poco de ingeniería algorítmica: Si introducimos las variables deholgura y no utilizamos la Fase I, se podría aplicar el método dual del Símplexañadiendo una variable artificial a la condición de igualdad e introduciéndola enla función objetivo con una gran penalización (pondremos 1.000). La matriz decondiciones quedaría:
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
0.55 0.45 0.5 0 0 0.17 0.25 0.25 0.63 0 0 0 0 1 0 0 0 0 0 0 0 00.26 0.13 0.12 0 0 0.7 41.6 2 0.2 0 0 0 0 0 1 0 0 0 0 0 0 00.23 0.09 0.045 0 0 0.14 20.4 0.4 0.25 0 0 0 0 0 0 1 0 0 0 0 0 00.2 0.055 0.06 0 0 0.14 9 0.4 0.04 0 0 0 0 0 0 0 1 0 0 0 0 00.4 0.065 0.06 0.26 0 0.02 0.1 0.05 0.3 0 0 0 0 0 0 0 0 1 0 0 0 00.8 0.025 0.02 3 0 0.15 0.05 0.05 0.5 0 0 0 0 0 0 0 0 0 1 0 0 00.1 0 0 0.9 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 00.1 0 0 0.9 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
10
� Si definimos como base de partida las columnas 10 a 22, tendremos unasolución no factible pero con costes reducidos óptimos.Apliquemos pues el algoritmo Símplex dual.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
30/57
� Cargamos los datos desde el fichero donde está el problema.
>> load vitaminas-dual>> B0B0 =
10 11 12 13 14 15 16 17 18 19 20 21 22>> bvbv =100.0000
1.00001.10005.00005.0000
43.000070.000045.000016.000014.000035.000019.000024.0000
>> cvcv =1.0e+003 *Columns 1 through 8
0.0058 0.0026 0.0031 0.0011 0.0010 0.0023 0.0357 0.0060Columns 9 through 16
0.0070 0 0 0 0 0 0 0Columns 17 through 22
0 0 0 0 0 1.0000
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
31/57� Aplicamos el algoritmo dual del Símplex.
>> [x fobj pi cr iter B N ]=dual_simplex(cv,Avf,bv,...sqrt(eps),B0)
It. Sale B Entra B Pinf Ninf1 15 3 -556.516667 82 22 2 -6057.100000 93 3 6 -121.100000 94 16 15 -889.600000 75 2 7 -86.908193 66 14 2 -68.423548 57 19 4 -49.470279 68 10 3 -24.806534 49 20 5 -15.791616 3
10 18 1 -12.295514 311 12 8 -5.000000 112 13 9 0.000000 0
x =15.967958.43015.91385.88911.21031.00001.58895.00005.0000
00.4889
000
20.25340
7.4017000
5.00000
fobj =396.3783
pi =-2.70322.6566
05.05680.9198
10.9772-0.00001.7305
03.31860.87900.3703
0cr =
1.0e+003 *0.00331.00270.00170.00090.00040.00270.01100.00510.0009
iter =12
B =3 11 8 9 2 6 15 17 1 4 5 21 7
N =18 22 16 19 20 10 14 12 13
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
32/57
� Para dotarnos de más medios sencillos para conocer y resolver los problemas deprogramación lineal se ha desarrollado el programa PL_pd_simplex_1 que selista en la siguiente página.
� Analiza el problema –que puede leerse con varios formatos– y lo transformaen forma estándar, si es el caso.
� Calcula una solución cualquiera del sistema de ecuaciones de las condicionesmediante el operador \ de Matlab.
� Resuelve el problema de optimización mediante el método primal o dualsegún esa solución sea factible o no.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
33/57
function [sol fobj pi cr iter B N Binv] = PL_pd_simplex_1(c,A,b,base,file)% Resuelve un problema de Programación Lineal% T% Min c x subject to Ax = b, x >= 0% mediante los programas ProgLineal_3 o dual_simplex según la base de partida% sea factible o no. Se puede dar la base o no.% Rutina asociada a Sensitivity_ProgLineal_3 a la que puede enviar datos.
if nargin==5 % Lectura de los datos desde fichero ’file’ en MPSeval([’!copy ’ file ’ ’ ’d:\matlab_2009a\work\tmp\in.mps’]);LIPSO = ’D:\matlab_2009a\work’; exit=mps2mat(LIPSO); fprintf(’\n’);load D:\matlab_2009a\work\tmp\default; [m n]=size(A); c=c(:); A=full(A);A=[A(:,n0+1:n) A(:,1:n0)]; c=[c(n0+1:n);c(1:n0)]; % Mover slacks al final de A
endsave PL_dat A b c % Guardar datos relevantes para Sensitivityeps1=eps^(2/3); [m n]=size(A); c=c(:);if isempty(base)
xB=A\b; base=find(abs(xB)>0); nx=length(base);if nx<m
bp = setdiff(1:n,base); base=[base;bp(1:m-nx)’]; end % Por si algún x=0xB=xB(base);
else xB=A(:,base)\b; endB = base; N = setdiff(1:n,B);x=zeros(n,1); x(B)=xB;y = A(:,B)’\c(B); sN = c(N)-A(:,N)’*y;if (any(x(B)<0)) % En la base valor negativo: no factible primal: dual
if any(sN<-eps1);A = [A eye(m)]; c = [c; max(max(abs(A)))*100*ones(m,1)]; B=n+1:n+m;fprintf(’Primal-bigM\n’);bm=find(b<0);if ~isempty(bm)
bl=length(bm); for i=1:bl, A(bm(i),n+bm(i))=-1; end, end[sol fobj pi cr iter B N Binv] = ProgLineal_3(c,A,b,eps1,B);NN=N<=n; N=N(NN); cr=cr(NN);save PL_dat -append sol fobj pi cr iter B N Binvreturn, end
fprintf(’Dual\n’);[sol fobj pi cr iter B N Binv] = dual_simplex(c’,A,b,eps1,B);save PL_dat -append sol fobj pi cr iter B N Binv
else fprintf(’Primal\n’); % Base encontrada factible: resuelve con primal[sol fobj pi cr iter B N Binv] = ProgLineal_3(c,A,b,eps1,B);save PL_dat -append sol fobj pi cr iter B N Binv
end
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
34/57
� “Dieta”: conPL_pd_simplex noes necesario aquellavariable artificial:
>> load vitaminas>> Av_d=full(Av);>> [sol fobj pi cr iter B N]=...
PL_pd_simplex(cv,Av_d,bv)DualIt. Sale B Entra B Pinf Ninf
1 16 19 -1579.781993 42 3 15 -43.883180 23 14 2 -34.832613 24 19 21 -92.210155 35 20 3 -4.839145 16 18 1 0.000000 0
sol =15.967958.43015.91385.88911.21031.00001.58895.00005.0000
00.4889
000
20.25340
7.4017000
5.0000fobj =
396.3783
pi =-2.70322.6566
05.05680.9198
10.97720
1.73050
3.31860.87900.3703
0cr =
3.318610.97722.65665.05680.91980.37031.73050.8790
iter =6
B =15456789
112
211713
N =18 14 10 12 13 20 16 19
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
35/57� Formato MPS (Mathematical Programming System), originalmente de IBM.
NAME VitaminasROWSN OBJETIVOE CAN.TOT.G ALFALFAG VITAMINAG FAC.CRE.G PESCADOG PROTEINAG RIBOFLA.G NIACINAG ACI.PAN.G FOSFOROG CALCIOG SAL1L SAL2
COLUMNSCARNE OBJETIVO 5.8 CAN.TOT. 1.0CARNE PROTEINA 0.55 RIBOFLA. 0.26CARNE NIACINA 0.23 ACI.PAN. 0.02CARNE FOSFORO 0.4 CALCIO 0.8CARNE SAL1 0.1 SAL2 0.1PESCADO OBJETIVO 7.0 CAN.TOT. 1.0PESCADO PESCADO 1.0 PROTEINA 0.63PESCADO RIBOFLA. 0.2 NIACINA 0.25PESCADO ACI.PAN. 0.04 FOSFORO 0.3PESCADO CALCIO 0.5SOJA-HAR OBJETIVO 2.63 CAN.TOT. 1.0SOJA-HAR PROTEINA 0.45 RIBOFLA. 0.13SOJA-HAR NIACINA 0.09 ACI.PAN. 0.055SOJA-HAR FOSFORO 0.065 CALCIO 0.025SOJA-GRA OBJETIVO 3.08 CAN.TOT. 1.0SOJA-GRA PROTEINA 0.5 RIBOFLA. 0.12SOJA-GRA NIACINA 0.045 ACI.PAN. 0.06SOJA-GRA FOSFORO 0.06 CALCIO 0.02
MINERAL. OBJETIVO 1.13 CAN.TOT. 1.0MINERAL. FOSFORO 0.26 CALCIO 3.0MINERAL. SAL1 0.9 SAL2 0.9SAL OBJETIVO 1.0 CAN.TOT. 1.0SAL SAL1 10.0 SAL2 10.0ALFALFA OBJETIVO 2.26 CAN.TOT. 1.0ALFALFA ALFALFA 1.0 PROTEINA 0.17ALFALFA RIBOFLA. 0.7 NIACINA 0.14ALFALFA ACI.PAN. 0.14 FOSFORO 0.02ALFALFA CALCIO 0.15VITAMINA OBJETIVO 35.72 CAN.TOT. 1.0VITAMINA VITAMINA 1.0 PROTEINA 0.25VITAMINA RIBOFLA. 41.6 NIACINA 20.4VITAMINA ACI.PAN. 9.0 FOSFORO 0.1VITAMINA CALCIO 0.05FAC.CRE. OBJETIVO 6.0 CAN.TOT. 1.0FAC.CRE. FAC.CRE. 1.0 PROTEINA 0.25FAC.CRE. RIBOFLA. 2.0 NIACINA 0.4FAC.CRE. ACI.PAN. 0.4 FOSFORO 0.05FAC.CRE. CALCIO 0.05
RHSRHS2 CAN.TOT. 100.0RHS2 ALFALFA 1.0RHS2 VITAMINA 1.1RHS2 FAC.CRE. 5.0RHS2 PESCADO 5.0RHS2 PROTEINA 43.0RHS2 RIBOFLA. 70.0RHS2 NIACINA 45.0RHS2 ACI.PAN. 16.0RHS2 FOSFORO 14.0RHS2 CALCIO 35.0RHS2 SAL1 19.0RHS2 SAL2 24.0
ENDATA
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
36/57� Cargando el problema de la Dieta desde su fichero MPS, con PL_pd_simplex:
» [sol fobj pi cr iter]= PL_pd_simplex_1([],[],[],[],’VITAM_dc.mps’)NAME done ROWS done COLUMNS done RHS done RANGES done BOUNDS done reading done mps2mat doneSTATUS = 0Primal-bigM
It. Sale B Entra B Cos. red. fobj1 24 8 -305308.280000 1568359.2920002 28 11 -301148.280000 1136218.4920003 33 6 -87359.000000 982559.1057694 32 5 -17346.160000 750387.4606975 26 2 -11962.734981 672947.6099366 23 7 -7879.097766 629741.1950327 31 13 -7802.734981 586419.6939338 27 18 -26294.839954 269939.9086999 5 14 -6553.956082 165687.133822
10 29 19 -9507.714478 155691.59870111 22 16 -27116.168354 46733.74777812 34 20 -4161.952696 26430.23704313 11 9 -4039.257391 26421.11704314 16 24 -88742.920000 24048.97200015 25 15 -3586.495609 6676.39940516 24 16 -2054.832754 6197.53241717 30 11 -37244.880000 707.45200018 16 5 -5.213325 711.89749319 6 17 -77.295278 601.67693720 14 10 -4.583216 570.82273921 19 6 -8.036120 645.57843922 18 3 -2.244385 559.19298123 10 14 -3.736203 442.33516124 14 1 -2.737159 445.64127225 13 18 -3.977266 403.20973426 20 21 -0.550016 400.49499827 18 4 -0.231097 399.013320
sol =15.96795.0000
58.43015.91385.88911.21031.00001.58895.0000
00.4889
000
20.25340
4.5275000
5.00000000000000000
fobj =396.3783
pi =Columns 1 through 10-2.7032 2.6566 0 5.0568 0.9198 10.9772 -0.0000 1.7305 0 3.3186
Columns 11 through 130.8790 0.3703 0
cr =10.9772 0.9198 3.3186 2.6566 5.0568 1.7305 0.8790 0.3703
iter =27
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
37/57� Con linprog de Matlab, una sesión para Dieta sería como sigue.
>> lb=zeros(1,21);>> options = optimset(’LargeScale’, ’off’, ’Simplex’, ’on’, ’Display’, ’Iter’)>> [x,fval,exitflag,output,lambda]=linprog(cv,[],[],Av_d,bv,lb,[],[],options)
Phase 1: Compute initial basic feasible point.Iter Infeasibility0 378.11 297.362 255.1733 215.2734 166.745 152.3546 150.4597 80.71058 39.70269 37.6039
10 35.288411 11.180712 6.1790713 3.7853314 0.3415 -0
Phase 2: Minimize using simplex.Iter Objective Dual Infeasibility
f’*x A’*y+z-w-f0 708.542 9.775271 602.242 77.29532 570.823 7.287543 567.359 8.732134 548.379 3.18325 442.335 5.61316 436.35 3.299957 403.21 4.081988 400.495 0.5965939 397.745 0.231097
10 396.378 0
Optimization terminated.x =
15.967958.43015.91385.88911.21031.00001.58895.00005.0000
00.4889
000
20.25340
7.40170
-0.00000
5.0000fval =
396.3783exitflag = 1output =
iterations: 10algorithm: ’medium scale: simplex’
cgiterations: []message: ’Optimization terminated.’
lambda =ineqlin: [0x1 double]
eqlin: [13x1 double]upper: [21x1 double]lower: [21x1 double]
» lambda.eqlinans =
2.7032-2.6566
0-5.0568-0.9198
-10.97720
-1.73050
-3.3186-0.8790-0.3703
0» lambda.lowerans =
000000000
2.65660
5.05680.9198
10.97720
1.73050
3.31860.87900.3703
0
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
38/57
� Con el programa Rsimplex_1:
>> [fobj niters x] = Rsimplex_1(’VITAM_dc.mps’)1 archivo(s) copiado(s).
NAME done ROWS done COLUMNS done RHS done RANGES done BOUNDS done reading done mps2mat[m n]=[13 21]. Tiempo CPU: 0.0624; fun. obj.= 3.9638e+002fobj =
3.963782645622545e+002niters =
40x =
00.488850287055962
000
20.2533999236258530.0000000000000004.527491511787425
000
5.00000000000000015.9679485856327875.000000000000000
58.4300718345540205.9137667611773105.8890571620178511.2103053695620651.0000000000000001.5888502870559625.000000000000000
>>
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
39/57Métodos de punto interior
� Desarrollo espectacular en los últimos veinte años a raíz de la publicación en1984 de un innovador paper de Narendra Karmarkar, entonces en loslaboratorios Bell de EE.UU.
Narendra Krishna Karmarkar, India 1957-.
� Basan su estrategia en la búsqueda del óptimo a través de caminos que recorrenla zona interior de la región factible; de ahí su nombre.
� Los más eficientes aplican el método de Newton, en sucesivas etapas, al sistemade ecuaciones que resulta de aplicar las condiciones KKT al problema.Han hecho converger en la práctica la Programación Lineal y la No Lineal.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
40/57Formulación del procedimiento general
El objetivo es, basándose en un procedimiento iterativo de dirección de des-censo para, desde el interior de la región factible, a partir de la resoluciónpor Newton-Raphson del sistema de ecuaciones no lineales al que dan lugarlas condiciones KKT, obtener esa dirección, progresar a un nuevo punto lomás posible, y así ir acercándose al óptimo del problema.
� Consideremos la formulación más completa del problema primal deprogramación lineal
minimizar cTx
sujeta a Ax D b0�x�u
donde2 c; x; u 2 Rn; b 2 Rm y A 2 Rm�n.
2 Si los límites inferiores de las variables no son cero, se pueden escalar para que así lo sean.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
41/57
� El dual de Wolfe de ese problema es max. L.x;y; z;w/
s. a rxL.x;y; z;w/D 0z;w � 0I
su función de Lagrange L.�; �; �; �/ D cTx �yT .Ax � b/�wT .u � x/� zTx.
� El gradiente de esta función de Lagrange con respecto a x es c �ATyCw� z.
� El dual es, ya simplificado,
maximizar yTb �wTusujeta a �ATyCw�zCc D 0
w; z � 0
donde y 2 Rm; w 2 Rn; z 2 Rn.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
42/57� Las condiciones de KKT del problema primal y dual, incorporando un vector devariables de holgura s, son
�ATy Cw � zC cD0AxDb
x C sDuxiziD0; i D 1; : : : ; nsiwiD0; i D 1; : : : ; n
x; z; s;w � 0:La cuarta y la quinta, no lineales, son las de holguras complementarias.
� Las condiciones de no negatividad de las variables son las que complican lamecánica de los métodos de puntos interiores.
� Para resolver este sistema de ecuaciones, dado que es no lineal, se podría usarNewton-Raphson, siempre que se partiese y cumpliese estrictamente, de unpunto a otro, las condiciones de no negatividad de las variables.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
43/57� También hay que tener cierto cuidado en el proceso si la ecuación sw D 0 selinealiza como se hace en Newton-Raphson, pues se tiene que
swC s�wCw�s D 0:� Si una variable, digamos wi , es cero, la ecuación de Newton quedasi�wi D 0, por lo que el paso �wi D 0.� Desde ese momento esa variable quedaría bloqueada en cero en todo elproceso, lo que es muy perjudicial para el algoritmo pues éste no podríarecuperarla para ayudar a mejorar, junto con las demás, el camino al óptimo.
1 4 . 1 . P R I M A L - D U A L M E T H O D S 401
x2 s2
x1 s1
iteraciones 01
2
3
central path C
Figure 14.2 Iterates of Algorithm 14.2, plotted in (xs) space.
(14.3a), (14.3b), and (14.3d).) In the unusual geometry of Figure 14.2, the search directions(�xk,�λk,�sk) transform to curves rather than straight lines.
As Figure 14.2 shows (and the analysis confirms), the lower bound σmin on thecentering parameter ensures that each search direction starts out by moving away from theboundary of N−∞(γ ) and into the relative interior of this neighborhood. That is, smallsteps along the search direction improve the centrality. Larger values of α take us outsidethe neighborhood again, since the error in approximating the nonlinear system (14.15) bythe linear step equations (14.16) becomes more pronounced as α increases. Still, we areguaranteed that a certain minimum step can be taken before we reach the boundary ofN−∞(γ ), as we show in the analysis below.
The analysis of Algorithm 14.2 appears in the next few pages. With judicious choicesof σk , this algorithm is fairly efficient in practice. With a few more modifications, it becomesthe basis of a truly competitive method, as we discuss in Section 14.2.
Our aim in the analysis below is to show that given some small tolerance ε > 0, thealgorithm requires O(n| log ε|) iterations to reduce the duality measure by a factor of ε, thatis, to identify a point (xk, λk, sk) for which µk ≤ εµ0. For small ε, the point (xk, λk, sk)satisfies the primal-dual optimality conditions except for perturbations of about ε in theright-hand side of (14.3c), so it is usually very close to a primal-dual solution of theoriginal linear program. The O(n| log ε|) estimate is a worst-case bound on the numberof iterations required; on practical problems, the number of iterations required appears
� Es crucial pues, en todo el proceso iterativo, mantener todas las variablesestrictamente positivas, aunque sea muy poco: una cantidad �.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
44/57� Por ello es importante que todas las holguras complementarias siwi converjana cero al mismo ritmo:
ski wki D �k ! 0 cuando k !1:
1 4 . 1 . P R I M A L - D U A L M E T H O D S 401
x2 s2
x1 s1
iteraciones 01
2
3
central path C
Figure 14.2 Iterates of Algorithm 14.2, plotted in (xs) space.
(14.3a), (14.3b), and (14.3d).) In the unusual geometry of Figure 14.2, the search directions(�xk,�λk,�sk) transform to curves rather than straight lines.
As Figure 14.2 shows (and the analysis confirms), the lower bound σmin on thecentering parameter ensures that each search direction starts out by moving away from theboundary of N−∞(γ ) and into the relative interior of this neighborhood. That is, smallsteps along the search direction improve the centrality. Larger values of α take us outsidethe neighborhood again, since the error in approximating the nonlinear system (14.15) bythe linear step equations (14.16) becomes more pronounced as α increases. Still, we areguaranteed that a certain minimum step can be taken before we reach the boundary ofN−∞(γ ), as we show in the analysis below.
The analysis of Algorithm 14.2 appears in the next few pages. With judicious choicesof σk , this algorithm is fairly efficient in practice. With a few more modifications, it becomesthe basis of a truly competitive method, as we discuss in Section 14.2.
Our aim in the analysis below is to show that given some small tolerance ε > 0, thealgorithm requires O(n| log ε|) iterations to reduce the duality measure by a factor of ε, thatis, to identify a point (xk, λk, sk) for which µk ≤ εµ0. For small ε, the point (xk, λk, sk)satisfies the primal-dual optimality conditions except for perturbations of about ε in theright-hand side of (14.3c), so it is usually very close to a primal-dual solution of theoriginal linear program. The O(n| log ε|) estimate is a worst-case bound on the numberof iterations required; on practical problems, the number of iterations required appears
� Con estos propósitos se modifica cada condición siwi haciendo siwi � � D 0para tratar de “centrar” algo la trayectoria a seguir en el proceso, evitando asíacercarse a esos valores cero de las variablesEsto lo esquematiza en la figura para x1s1 y x2s2.
� En cada punto del proceso se hace
�k D �kg; donde g D NxT NzC NsT Nw2n
;
siendo el numerador la denominada brecha o gap de dualidad, y el denominadorlos dos grupos de n variables que contribuyen al gap. � es un porcentaje,�k 2 .0; 1/ � 0;9995, de lo que se desea reducir el gap en cada iteración.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
45/57
� En cada etapa del proceso iterativo los métodos de puntos interiores resuelvenligeras variantes del sistema no lineal KKT
f .x;y; z; s;w/x;z;s;w>0
�
8̂̂̂<̂ˆ̂:ATy C z �wD c
Ax D bx C s D uXZ D �eW S D �e
donde X , S , Z y W son matrices diagonales con coeficientes xj , sj , zj y wj ,respectivamente, y e es el vector de coeficientes 1.
� De estas resoluciones se va obteniendo el denominado camino central –centralpath–, si � ¤ 0, hacia el óptimo y se evita caer en valores cero de las variables.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
62/72
� La fórmula más aceptada –de Mehrotra– de combinar estas dosopciones sobre qué dirección de avance seguir, consiste en llevar acabo dos pasos en una etapa, denominados predictor ycorrector:� Predictor: se resuelve la aproximación lineal: la dirección de
descenso puro de Newton, o de escalado afín, con � D 0.� Corrector y centrado: para compensar la linealización anterior
introduciendo más información de segundo orden y centrar entorno al camino central (central path), mediante el parámetro �.
400 C H A P T E R 1 4 . I N T E R I O R - P O I N T M E T H O D S
C
central path neighborhood
Figure 14.1 Central path, projected into space of primal variables x , showing atypical neighborhood N .
Here and in later analysis, we use the notation
(xk(α), λk(α), sk(α))def� (xk, λk, sk)+ α(�xk,�λk,�sk), (14.19a)
µk(α)def� xk(α)T sk(α)/n. (14.19b)
Algorithm 14.2 (Long-Step Path-Following).Given γ , σmin, σmax with γ ∈ (0, 1), 0 < σmin ≤ σmax < 1,
and (x0, λ0, s0) ∈ N−∞(γ );for k � 0, 1, 2, . . .
Choose σk ∈ [σmin, σmax];Solve (14.10) to obtain (�xk,�λk,�sk);Choose αk as the largest value of α in [0, 1] such that
(xk(α), λk(α), sk(α)) ∈ N−∞(γ ); (14.20)
Set (xk+1, λk+1, sk+1) � (xk(αk), λk(αk), sk(αk));end (for).
Typical behavior of the algorithm is illustrated in Figure 14.2 for the case of n � 2.The horizontal and vertical axes in this figure represent the pairwise products x1s1 and x2s2,so the central path C is the line emanating from the origin at an angle of 45◦. (A point at theorigin of this illustration is a primal-dual solution if it also satisfies the feasibility conditions
Camino central
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
46/57� A este planteamiento moderno del procedimiento de resolución se llega tambiénmediante otro clásico si en el problema original se incorporan las condiciones deno acercarse a cero de las variables xi y si mediante un término en la funciónobjetivo que se haga muy grande —barrera— cuando esas variables tomen esevalor: su logaritmo, por ejemplo:
minimizarcTx � �0@ nXjD1
log xj CnX
jD1log sj
1Asujeta a AxDb
x C sDux; s> 0:
Problema denominado de barrera logarítmica del primal, para un escalar �.
� Su función de Lagrange es, simplificando la notación,
cTx � � logx � � log s � yT .Ax � b/ �wT .x C s � u/ :
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
47/57� Las condiciones KKT de este problema son
AxDb�ATy C z �wC cD 0
x C sDuXZeD�eSW eD�e;
donde z D �X�1e; w D �S�1e. Son casi idénticas a las anteriores.
� Cuando �!1, las soluciones del problema barrera son el centro analítico dela región factible del problema primal.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
62/76
1. THE BARRIER PROBLEM 279
µ= 8
µ=1
µ=0.01
µ= 8 µ=1
(c) µ=0.01 (d) camino central
FIGURE 16.1. Parts (a) through (c) show level sets of the barrierfunction for three values ofµ. For each value ofµ, four level setsare shown. The maximum value of the barrier function is attainedinside the innermost level set. The drawing in part (d) shows thecentral path.
It is instructive to have in mind a geometric picture of the barrier function. Recallthat, for problems expressed in standard form, the set of feasible solutions is a poly-hedron with each face being characterized by the property that one of the variablesis zero. Hence, the barrier function is minus infinity on each face of the polyhedron.Furthermore, it is finite in the interior of the polyhedron, and it approaches minus in-finity as the boundary is approached. Figure 16.1 shows some level sets for the barrierfunction for a specific problem and a few different choices ofµ. Notice that, for eachµ, the maximum is attained at an interior point, and asµ gets closer to zero this interiorpoint moves closer to the optimal solution of the original linear programming problem(which is at the top vertex). Viewed as a function ofµ, the set of optimal solutionsto the barrier problems forms a path through the interior of the polyhedron of feasible
1. THE BARRIER PROBLEM 279
µ= 8
µ=1
µ=0.01
(a) µ= 8 (b) µ=1
µ=0.01 camino central
FIGURE 16.1. Parts (a) through (c) show level sets of the barrierfunction for three values ofµ. For each value ofµ, four level setsare shown. The maximum value of the barrier function is attainedinside the innermost level set. The drawing in part (d) shows thecentral path.
It is instructive to have in mind a geometric picture of the barrier function. Recallthat, for problems expressed in standard form, the set of feasible solutions is a poly-hedron with each face being characterized by the property that one of the variablesis zero. Hence, the barrier function is minus infinity on each face of the polyhedron.Furthermore, it is finite in the interior of the polyhedron, and it approaches minus in-finity as the boundary is approached. Figure 16.1 shows some level sets for the barrierfunction for a specific problem and a few different choices ofµ. Notice that, for eachµ, the maximum is attained at an interior point, and asµ gets closer to zero this interiorpoint moves closer to the optimal solution of the original linear programming problem(which is at the top vertex). Viewed as a function ofµ, the set of optimal solutionsto the barrier problems forms a path through the interior of the polyhedron of feasible
� El algoritmos reducen paso a paso � según se aproximan al óptimo del primal.
� Al �! 0, la solución del problema barrera converge al centro analítico delconjunto de las soluciones óptimas del primal (camino central).
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
48/57
� Volviendo a la resolución del sistema de ecuaciones f .x;y; z; s;w/ D 0mediante Newton-Raphson, el nuevo punto hacia la solución de ese sistema,� D Œx;y; z; s;w�T , saldrá de resolver el modelo de desarrollo de Taylor deprimer orden
f .�k/C f 0 ��k� ��kC1 � �k� D 0;es decir, �vk D �f 0 ��k��1 f .�k/; siendo �vk la dirección de Newton en laiteración k y f 0
��k�la matriz jacobiana del sistema.
� La aproximación lineal del sistema, es decir,26664A 0 0 0 0
0 0 AT I �II I 0 0 0
Z 0 0 X 0
0 W 0 0 S
3777526664�x
�s
�y
�z
�w
37775 D26664
rbrcru
�e �XZe�e � SW e;
37775 donde
rbDb �AxrcDc �ATy � zCwruDu � x � s:
;
y su resolución, determinará el nuevo punto donde moverse.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
49/57
� Esa dirección se podría mejorar considerablemente ampliando el modelo dedesarrollo de Taylor de f .x;y; z; s;w/ D 0 a segundo orden de derivadas, esdecir,
fi.v/Crf .v/T�vC 12�vTr2f .v/�v D 0:
La matriz Hessiana de las condiciones de complementariedad sería�0 11 0
�y la de
las demás cero.
� La dirección de avance saldría en este caso de resolver264A 0 0 0 0
0 0 AT I �II I 0 0 0Z 0 0 X 00 W 0 0 S
375264�x�s�y�z�w
375 D264 rb
rcru
�e �XZe ��X�Ze�e � SW e ��S�W e
375 :
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
50/57� Sanjay Mehrotra propuso cómo actuar con estas dos direcciones: combinarlasen dos pasos, los denominados predictor y corrector, en una misma etapadel proceso iterativo:
Sanjay Mehrotra, India (EE.UU.)
� Predictor: se usa la dirección de la aproximación lineal del paso de Newton(también denominada de escalado afín) con � D 0.
6 The Open Operational Research Journal, 2009, Volume 3 Goran Lesaja
The step size is chosen in such a way that iterates stay in
the one of the above horn neighborhoods
k= max : X ( )s( ) μ( )e μ( ), [0, ]{ } , (3.19)
where
x( ) = x
k+ d
x, s( ) = s
k+ d
s, μ( ) =
xT ( )s( )
n. (3.20)
Although general Newton’s Method (NM) is not
necessarily globally convergent, by using the above
technique, global convergence is guaranteed. Moreover, fast
local convergence (quadratic or at least superlinear) is
preserved. Now, the first step of the barrier algorithm BM
can be completed by calculating the new iterates
xk+1
= xk+
kd
x, yk+1
= yk+
kd
y, sk+1
= sk+
kd
s. (3.21)
The second step of BM is the calculation of μk+1 using
the last equation in (3.20). It can be shown that the
sequence {μk} is decreasing at least at a constant rate which
is the key to proving that the global convergence of the
method is polynomial in the number of variables and chosen
accuracy. Finally, let us mention again that BM is an
iterative algorithm. An iterate (xk , yk , sk ) is an -
approximate optimal solution if
Axk b P , AT yk + sk c D , (xk )T sk G (3.22)
for a given ( P , D , G ) > 0 .
The Interior-Point Algorithm can now be summarized as
follows.
Algorithm (IPM)
Initialization
1. Choose , (0,1) and ( P , D , G ) > 0 . Choose
(x0 , y0 , s0 ) such that (x0 , s0 ) > 0 and
X 0s0 μ0 e μ0 where μ0 =(x0 )T s0
n.
2. Set k = 0 .
Step
3. Set rPk= b Axk , rD
k= c AT yk sk , μk =
(xk )T sk
n.
4. Check the termination. If
rPk
P , rDk
D , (xk )T sk G , then terminate.
5. Compute the direction by solving the system
A 0 0
0 AT I
Sk 0 Xk
dxdyds
=
rPk
rDk
X ksk + μke
.
6. Compute the step size
k = max : X( )s( ) μ( )e μ( ), [0, ]{ } ,
where x( ) = xk + dx , s( ) = sk + ds ,
μ( ) =xT ( )s( )
n.
7. Update xk+1 = xk + kdx , yk+1 = yk + kdy , sk+1
= sk + kds .
8. Set k = k +1 and go to step 3.
The graphical representation of the IPM algorithm is
given in Fig. (1).
Fig. (1).
The above algorithm has favorable convergence
properties. For certain choice of the parameters and using the
neighborhood N2 ( ) , the following convergence results can
be obtained.
• Global convergence: The algorithm IPM will
achieve an approximate optimal solution in
O n log1( ) iterations, where = min P , D , G{ } .
• Local convergence: For a sufficiently large k there
exists a constant > 0 such that
xik+1si
k+1 (xik si
k )2 , i = 1, ...,n.
There are many modifications and variations of this
algorithm. In fact this algorithm represents a broad class of
algorithms. For example, as we already mentioned, we can
consider different neighborhoods of the central path.
Because of the relation (3.18), if N2 ( ) is used, IPM is
called a short-step algorithm, and if N ( ) or N ( ) is
selected, IPM is called a long-step algorithm. Unfortunately,
the price to pay for taking bigger steps in a long-step
algorithm is worse global convergence, that is, algorithm
needs O n log1( ) to achieve an approximate optimal
solution. However, the practical performance of long-step
algorithms seems to be better than the short-step algorithms.
Details of the similar IPMs and the proofs of the
convergence results can be found in [38, 54-58] and many
other papers and monographs.
The IPMs are iterative algorithms which produce only an
-approximate optimal solution of the problem. However,
as in the case of the Ellipsoid and Karmarkar’s algorithms, it
� Corrector y centrado: para mejorar lo perdido con la linealización seintroduce la información de segundo orden y la dirección se centra hacia elcamino central.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
51/57
� Si en la aproximación lineal de Newton anterior se despejan
�sDu � x � s ��x de la tercera�zDX�1 .��e �XZe �Z�x/ de la cuarta�wDS�1 .��e � SW e �W ru CW �x/ de la quinta
el sistema se puede expresar en función de �x y �y como sigue:��D�1AT
A 0
� ��x
�y
�D�rc �X�1 .��e �XZe/C S�1 .��e � SW e �W ru/
rb
�;
donde D D �X�1Z C S�1W ��1.
� Sistema clave de gran dimensión normalmente, del que todos los métodos depunto interior similares resuelven alguna variante.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
52/57� Se puede reducir más eliminando �x sin más que multiplicar el primersubconjunto de ecuaciones por AD y sumar el segundo; resultan las ecuacionesnormales, �
ADAT��y D rb CAD
�rc �X�1 .��e �XZe/
CS�1 .��e � SW e �W ru/�:
Como la matriz ADAT es simétrica y definida positiva o semidefinida positiva,se puede factorizar por Cholesky, aunque hay que cuidar mucho cómo se hace.
� Este procedimiento sigue todo lo apuntado (con rxz D ��e �XZe y
rsw D ��e � SW e).
1. Formar la matriz D D �X�1Z C S�1W ��12. Hacer rc rc �X�1rxz C S�1 .rsw �W ru/3. Resolver mediante Cholesky
�ADAT
��y D rb CADrc
4. Calcular �x D D.AT�y � rc/�z D X�1 .�Z�x C rxz/�s D ru ��x�w D S�1 .�W �sC rsw/
� Una iteración se completaría determinando las amplitudes de paso, ˛P y ˛D, en“predictor” y “corrector”, adaptando � y comprobando óptimo.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
53/57
Dado Œx0;y0; z0;w0; s0� con Œx0; z0;w0; s0� > 0.Paso 1 – Calcular la dirección predictor o de escalado afín:2664
A 0 0 0 0
0 0 AT I �II I 0 0 0Z 0 0 X 00 W 0 0 S
37752664�xaf�saf�yaf�zaf�waf
3775 D2664
rbrcru�XZe�SW e
3775Hacer ˛af;P D Kınf
˚˛ 2 Œ0; 1�jŒx; s�C ˛Œ�xaf ;�saf � � 0
;
˛af;D D Kınf˚˛ 2 Œ0; 1�jŒz;w�C ˛Œ�zaf ;�waf � � 0
;
�af D1
2n
h�xC ˛af;P�x
�T �zC ˛af;D�z
�C�sC ˛af;P�s
�T �wC ˛af;D�w
�iy
� D
��af
�
�3
:
Paso 2 – Calcular la dirección corrector y centrado:2664A 0 0 0 0
0 0 AT I �II I 0 0 0Z 0 0 X 00 W 0 0 S
37752664�xc�sc�yc�zc�wc
3775 D2664
000
��e ��Xaf �Zaf e��e ��Saf �W af e
3775Paso 3 – Obtener la dirección de la iteración: Œ�x; �y; �z; �w; �s� D
Œ�xaf ; �yaf ; �zaf ; �waf ; �saf �C Œ�xc ; �yc ; �zc ; �wc ; �sc �: Hacer˛max;P D Kınf f˛ 2 Œ0; 1�jŒx; s�C ˛Œ�x; �s� � 0g˛max;D D Kınf f˛ 2 Œ0; 1�jŒz;w�C ˛Œ�z; �w� � 0g y ˛P D P˛max;P ; ˛D D D˛max;D :
Paso 4 – Terminar iteración y comprobar óptimo. Hacer ŒxkC1; skC1� D Œxk ; sk �C˛P Œ�x; �s� y ŒykC1; zkC1;wkC1� DŒyk ; zk ;wk �C ˛DŒ�y; �z; �w�.Comprobar condiciones de óptimo. Si no, seguir.
Algoritmo predictor-corrector de punto interior de Mehrotra
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
54/57function IntPointLP_2(A,b,c)% Resuelve min p’x s.t. Ax=b, x>=0,% cuyo dual es max b’y s.t. A’y+z=c, z>=0. Método Primal-Dual IPt[m,n]=size(A); x=sqrt(n)*ones(n,1); y=zeros(m,1); % Sol. inicial no negativa en xz = x; bc = 1+max(norm(b),norm(c)); t0=cputime;for iter = 1:100
Rd=A’*y+z-c;Rp=A*x-b;Rc=x.*z;residual=norm([Rd;Rp;Rc])/bc;gap=mean(Rc);fprintf(’iter %2i: medidor duali.=%9.2e, error tot. rel.=%9.2e’,iter,gap,residual);fprintf(’\tobj=%14.6e\n’,c’*x);if residual<5.e-8, break, endRc=Rc-min(.1,100*gap)*gap;d=min(5.e+15,x./z);B=A*diag(d)*A’;R=chol(B);t1=x.*Rd-Rc;t2=-(Rp+A*(t1./z));dy=R\(R’\t2);dx=(x.*(A’*dy)+t1)./z;dz=-(z.*dx+Rc)./x;tau=max(.9995,1-gap);ap=-1/min(min(dx./x),-1);ad=-1/min(min(dz./z),-1);ap=tau*ap;ad=tau*ad;x=x+ap*dx; z=z+ad*dz; y=y+ad*dy;
endfprintf(’Termina!\t[m n]=[%g %g]\tCPU=%g\n’,m,n,cputime-t0);x, y, zfprintf(’Fun, Obj= %14.6f\n’,c’*x);
end
function [x y z A b c n0]=ProgLineal_InP_MPS_sc(file)% Resuelve min c’x s.t. Ax=b, x>=0, cuyo dual es max b’y s.t. A’y+z=c, z>=0. Interior Point.eval([’!copy ’ file ’ ’ ’D:\MATLAB2010b\work\tmp\in.mps’]); LIPSO = ’D:\MATLAB2010b\work’;ar=mps2mat(LIPSO); fprintf(’\n’); load D:\MATLAB2010b\work\tmp\default;[m,n]=size(A); x=sqrt(n)*ones(n,1); y=zeros(m,1); % Sol. inicial no negativa en xz = x; bc = 1+max(norm(b),norm(c)); t0=cputime;p = symamd(A*A’); % Reordenación grado mínimofprintf(’\n No fac. No fac. Brecha Error’);fprintf(’\n primal dual dual relati.\n’);fprintf(’ Iter A*x-b A’’*y+z-c x’’*z total\n’);fprintf(’ ---------------------------------------------------\n’);for iter = 1:100
Rd=A’*y+z-c; rrd=norm(Rd); % No factibilidad dualRp=A*x-b; rrp=norm(Rp); % No factibilidad priamlRc=x.*z; % No factibilidad complementariedadresiduo=norm([Rd;Rp;Rc])/bc;gap=mean(Rc); % Brecha dualfprintf(’%5i %15.2e %10.2e %11.2e %10.2e\n’,iter,rrd,rrp,gap,residuo);if residuo<5.e-10, break, endRc=Rc-min(.1,100*gap)*gap;d=min(5.e+15,x./z);B=A*sparse(1:n,1:n,d)*A’;R=cholinc(sparse(B(p,p)),’inf’); % Cholesky incompletot1=x.*Rd - Rc; t2=-(Rp+A*(t1./z));dy=zeros(m,1);dy(p)=R\(R’\t2(p)); % Resuelve sistemadx=(x.*(A’*dy)+t1)./z;dz=-(z.*dx+Rc)./x;tau=max(.9995,1-gap);ap=-1/min(min(dx./x),-1); % Amplitud de paso primalad=-1/min(min(dz./z),-1); % Amplitud de paso dualap=tau*ap; ad=tau*ad;x=x+ap*dx; z=z+ad*dz; y=y+ad*dy;
endfprintf(’Termina bien!\t[m n] = [%g %g]\tCPU = %g\n’,m,n,cputime-t0);f=c’*x; fprintf(’Fun. Obje.= %18.14f\n’,f);
end
El programa con y sin lectura de datosa través de ficheros .MPS
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
55/57� Resolvamos con este programa el problema de programación lineal:
min.�x1 � 3x2s. a 2x1C 3x2C x3 D 6�x1C x2C x4D 1
x1; x2; x3; x4 � 0:
>> cEje1=[-1 -3 0 0];>> AEje1=[2 3 1 0;-1 1 0 1];>> bEje1=[6;1];>> IntPointLP_1(AEje1,bEje1,cEje1’)iter 1: gap=4.00e+000, error tot. rel.=1.69e+000 obj=-8.000000e+000iter 2: gap=1.12e+000, error tot. rel.=3.16e-001 obj=-3.714339e+000iter 3: gap=3.00e-001, error tot. rel.=9.79e-002 obj=-4.423752e+000iter 4: gap=6.71e-002, error tot. rel.=2.38e-002 obj=-5.315741e+000iter 5: gap=6.74e-003, error tot. rel.=2.21e-003 obj=-5.380112e+000iter 6: gap=6.77e-004, error tot. rel.=1.91e-004 obj=-5.398613e+000iter 7: gap=4.62e-005, error tot. rel.=1.30e-005 obj=-5.399908e+000iter 8: gap=2.15e-007, error tot. rel.=6.08e-008 obj=-5.400000e+000iter 9: gap=4.68e-012, error tot. rel.=1.32e-012 obj=-5.400000e+000Termina! [m n] = [2 4] CPU = 0.0312002x =
0.60001.60000.00000.0000
y =-0.8000-0.6000
z =0.00000.00000.80000.6000
Fun, Obj= -5.400000
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
56/57
� La “Dieta”:
>> load vitaminas>> Av_d=full(Av);>> IntPointLP_1(Av_d,bv,cv’)iter 1: gap=2.10e+001, error tot. rel.=1.32e+000obj= 2.961260e+002iter 2: gap=1.27e+001, error tot. rel.=8.62e-001obj= 3.454134e+002iter 3: gap=7.00e+000, error tot. rel.=4.80e-001obj= 3.635193e+002iter 4: gap=2.47e+000, error tot. rel.=1.81e-001obj= 3.884943e+002iter 5: gap=6.83e-001, error tot. rel.=2.62e-002obj= 4.007237e+002iter 6: gap=1.63e-001, error tot. rel.=6.61e-003obj= 3.974000e+002iter 7: gap=1.93e-002, error tot. rel.=6.62e-004obj= 3.965177e+002iter 8: gap=1.94e-003, error tot. rel.=6.04e-005obj= 3.963934e+002iter 9: gap=1.95e-004, error tot. rel.=6.06e-006obj= 3.963798e+002iter 10: gap=3.83e-006, error tot. rel.=1.19e-007obj= 3.963783e+002iter 11: gap=1.49e-009, error tot. rel.=4.62e-011obj= 3.963783e+002Termina! [m n] = [13 21] CPU = 0.109201
x =15.96794858596986358.4300718252464085.9137667670603575.8890571622226071.2103053699411971.0000000005555061.5888502870928435.0000000002932395.0000000016178290.0000000005555060.4888502870928420.0000000002932470.0000000016178510.000000000134912
20.2533999260423660.0000000008566447.4017222577017040.0000000004508070.0000000016776260.0000000040093334.999999995990669
y =-2.7031936325076132.6565600690646400.0000000030397945.0567844053206450.919806312736561
10.9772484848046720.0000000000733921.7305427843599900.0000000002007543.3185741962090140.8790256381419990.370319363423242
-0.000000000295456z =
0.0000000000930280.0000000000253920.0000000002528440.0000000002522640.0000000012297600.0000000014908200.0000000009349410.0000000002971670.0000000002976982.6565600690646400.0000000030397945.0567844053206460.919806312736561
10.9772484848046720.0000000000733921.7305427843599900.0000000002007543.3185741962090140.8790256381419990.3703193634232420.000000000295456
Fun, Obj= 396.378265
» [x y z]=ProgLineal_InP_MPS_sc(’vitam_dc.mps’)1 archivo(s) copiado(s).
NAME doneROWS doneCOLUMNS doneRHS doneRANGES doneBOUNDS donereading donemps2mat doneStatus=0
No fac. No fac. Brecha Errorprimal dual dual relati.
Iter A*x-b A’*y+z-c x’*z total---------------------------------------------------
1 3.56e+01 1.65e+02 2.10e+01 1.32e+002 2.74e+01 1.05e+02 1.27e+01 8.54e-013 1.52e+01 5.50e+01 6.86e+00 4.55e-014 2.69e+00 2.06e+01 2.34e+00 1.66e-015 1.34e-03 1.03e-02 4.39e-01 1.70e-026 4.10e-04 2.04e-03 1.46e-01 5.73e-037 2.05e-07 6.85e-05 1.60e-02 5.22e-048 1.03e-10 3.43e-08 1.61e-03 5.00e-059 5.55e-14 1.67e-11 1.61e-04 5.02e-06
10 7.67e-15 2.87e-12 2.63e-06 8.18e-0811 2.60e-15 3.59e-12 6.99e-10 2.17e-11
Termina bien! [m n] = [13 21] CPU = 0.046875Fun. Obje.= 396.37826456785990
x =0.0000000002612740.4888502870733260.0000000001379220.0000000007608450.000000000063454
20.2533999247632290.0000000004028314.5274915119942570.0000000002121240.0000000007889490.0000000018857594.999999998114246
15.9679485857919485.000000000760850
58.4300718301657445.9137667639542225.8890571621139231.2103053697404001.0000000002612741.5888502870733295.000000000137925
y =-2.7031936335204082.6565600704092010.0000000014297595.0567844059396160.919806312588121
10.9772484872875130.0000000000345201.7305427845897030.0000000001543993.3185741944199950.8790256386292590.370319363433166
-0.000000000138967z =
2.6565600704092010.0000000014297595.0567844059396160.919806312588121
10.9772484872875130.0000000000345201.7305427845897030.0000000001543993.3185741944199950.8790256386292590.3703193634331660.0000000001389670.0000000000437550.0000000001400210.0000000000119430.0000000001189240.0000000001186520.0000000005784150.0000000007012040.0000000004397470.000000000139772
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
57/57� Un problema muy grande –MarosR7– m D 3:136, n D 9:408 y nz D 151:120:
» ProgLineal_InP_MPS_sc(’marosr7.mps’);1 archivo(s) copiado(s).
NAME done ROWS done COLUMNS done RHS done RANGES done ...
No fac. No fac. Brecha Errorprimal dual dual relati.
Iter A*x-b A’*y+z-c x’*z total---------------------------------------------------
1 9.34e+003 4.09e+005 9.41e+003 2.41e+0002 9.24e+003 3.99e+005 9.10e+003 2.35e+0003 9.03e+003 3.70e+005 8.93e+003 2.33e+0004 8.45e+003 3.37e+005 8.04e+003 2.12e+0005 7.47e+003 2.66e+005 6.73e+003 1.80e+0006 5.78e+003 1.36e+005 5.06e+003 1.33e+0007 2.99e+003 6.81e+001 2.71e+003 6.82e-0018 9.40e+001 3.40e-002 2.29e+002 6.04e-0029 4.62e+001 1.15e-003 1.13e+002 2.93e-002
10 2.56e+001 4.36e-004 6.43e+001 1.67e-00211 1.68e+001 1.75e-004 3.97e+001 1.05e-00212 8.07e+000 6.40e-005 2.02e+001 5.34e-00313 4.69e+000 2.91e-005 1.17e+001 3.14e-00314 2.43e+000 1.14e-005 6.15e+000 1.66e-00315 1.55e+000 5.66e-006 3.84e+000 1.06e-00316 7.76e-001 1.97e-006 1.92e+000 5.40e-00417 4.03e-001 8.41e-007 1.04e+000 2.92e-00418 1.60e-001 3.06e-007 4.63e-001 1.27e-00419 5.96e-002 1.21e-007 2.05e-001 5.40e-00520 1.76e-002 5.00e-008 8.44e-002 2.08e-00521 4.67e-003 1.38e-008 2.85e-002 6.91e-00622 1.45e-003 8.21e-009 1.33e-002 3.16e-00623 2.95e-004 6.09e-009 2.97e-003 7.10e-00724 1.48e-007 9.15e-009 2.98e-004 6.96e-00825 4.40e-011 3.02e-009 8.96e-006 2.09e-00926 1.66e-014 3.57e-009 8.10e-009 1.89e-012
Termina bien! [m n] = [3136 9408] CPU = 28.829Fun. Obje.= 1497185.16653047850000
>> runlipsol(’marosr7’)Running mps2mat ...NAME doneROWS doneCOLUMNS doneRHS doneRANGES doneBOUNDS donereading donemps2mat doneStatus=0mps2mat successfulLoading tmp\default.mat ...Preprocessing ...(m=3136, n=9408)
Dense columns (nnz/m > 0.1): 0
<<<<< This is MIIP algorithm >>>>>min-degree ordering ... Done. CPU seconds: 0.015625calling symfct.mex* ... Done. CPU seconds: 0
Residuals: Primal Dual U-bounds Gap TR_error---------------------------------------------------------Iter 0: 6.54e+05 1.01e+04 0.00e+00 4.15e+09 4.41e+05Iter 1: 6.17e-10 2.80e+03 0.00e+00 1.08e+09 1.15e+05Iter 2: 7.53e-09 7.37e+00 0.00e+00 3.04e+07 3.23e+03Iter 3: 1.13e-09 6.24e-01 0.00e+00 5.70e+06 6.06e+02Iter 4: 6.37e-10 2.29e-01 0.00e+00 2.24e+06 2.38e+02Iter 5: 4.19e-10 6.35e-02 0.00e+00 9.35e+05 9.94e+01Iter 6: 4.02e-10 1.21e-02 0.00e+00 3.85e+05 4.09e+01Iter 7: 5.03e-10 1.96e-03 0.00e+00 1.39e+05 1.48e+01Iter 8: 6.54e-10 3.68e-04 0.00e+00 4.47e+04 4.75e+00Iter 9: 1.12e-09 1.01e-04 0.00e+00 1.63e+04 1.73e+00Iter 10: 1.19e-09 2.09e-05 0.00e+00 3.95e+03 4.20e-01Iter 11: 1.75e-09 2.04e-06 0.00e+00 7.28e+02 7.74e-02Iter 12: 1.81e-09 2.49e-07 0.00e+00 2.42e+02 2.58e-02Iter 13: 1.69e-09 1.77e-08 0.00e+00 2.63e+01 2.80e-03Iter 14: 2.00e-09 1.99e-14 0.00e+00 1.43e-01 1.52e-05Iter 15: 1.32e-09 3.51e-14 0.00e+00 7.14e-05 7.59e-09
MAROSR7<* Converged! *>Results (unprocessed) in results.matSolution xsol (processed) in solution.matPrimal Obj = 1.4971851665e+06[m n] = [3136 9408], nnz(A) = 144848, nnz(L) = 1198243CPU seconds: 0.48 ... loading
0.02 ... preprocessing7.20 ... solving0.00 ... postprocessing7.70 ... total
>> PLip_1(’marosr7.mps’)1 archivo(s) copiado(s).
NAME doneROWS doneCOLUMNS doneRHS doneRANGES doneBOUNDS donereading donemps2mat doneStatus=0Preprocesado ...(m=3136, n=9408)
<<<<< Alg_IP: Algoritmo de Punto Interior Predictor-Corrector>>>>>
Residuos: Primal Dual U-bounds d-Gap Err_rel_max-----------------------------------------------------------------Iter 0: 6.54e+05 1.01e+04 0.00e+00 4.149e+09 4.410e+05Iter 1: 6.41e-10 2.80e+03 0.00e+00 1.079e+09 1.147e+05Iter 2: 5.19e-09 7.37e+00 0.00e+00 3.038e+07 3.229e+03Iter 3: 7.99e-10 6.24e-01 0.00e+00 5.704e+06 6.063e+02Iter 4: 6.15e-10 2.29e-01 0.00e+00 2.241e+06 2.382e+02Iter 5: 3.42e-10 6.35e-02 0.00e+00 9.351e+05 9.939e+01Iter 6: 3.22e-10 1.21e-02 0.00e+00 3.845e+05 4.087e+01Iter 7: 3.84e-10 1.96e-03 0.00e+00 1.392e+05 1.480e+01Iter 8: 5.73e-10 3.68e-04 0.00e+00 4.469e+04 4.750e+00Iter 9: 7.16e-10 1.01e-04 0.00e+00 1.628e+04 1.730e+00Iter 10: 8.46e-10 2.09e-05 0.00e+00 3.950e+03 4.198e-01Iter 11: 1.62e-09 2.04e-06 0.00e+00 7.279e+02 7.737e-02Iter 12: 1.68e-09 2.49e-07 0.00e+00 2.423e+02 2.575e-02Iter 13: 2.39e-09 1.77e-08 0.00e+00 2.630e+01 2.795e-03Iter 14: 1.43e-09 1.98e-14 0.00e+00 1.428e-01 1.518e-05Iter 15: 1.89e-09 3.52e-14 0.00e+00 7.144e-05 7.594e-09
MAROSR7<* Converge! *>Resultados (sin procesar) en results.matSolución xsol (procesada) en solution.matPrimal Obj = 1.4971851665e+06[m n] = [3136 9408], nnz(A) = 144848CPU seconds: 0.45 ... carga de datos
0.09 ... preprocessado9.34 ... resolución0.00 ... postprocesado9.89 ... total
