Download Complejidad del método simplex y métodos de puntos interiores PDF

TitleComplejidad del método simplex y métodos de puntos interiores
TagsMathematics Algebra Physics & Mathematics Mathematical Concepts Computational Complexity Theory
File Size329.3 KB
Total Pages10
Document Text Contents
Page 1

Complejidad Computacional del Método Simplex

y Métodos de Puntos Interiores*

Omar Trejo - 119711

Octubre, 2013

1. Tiempo Exponencial

La idea general del método Simplex para resolver problemas de programa-
ción lineal es recorrer las aristas, vértice por vértice, de un poĺıtopo (región
factible) revisando su optimalidad en cada paso. La cantidad máxima de vérti-
ces dados por el sistema Ax ≤ b (que define el poĺıtopo del problema), donde
A ∈ Rmxn, es

(
n
m

)
, aunque cotidianamente se prueba un número menor que éste.

Sin embargo, el hecho de que la cantidad de pruebas necesarias esté relacionada
a una expresión combinatoria indica un posible problema con la complejidad
computacional del algoritmo.

1.1. Problema Klee-Minty

El ejemplo utilizado cotidianamente para demostrar la complejidad exponen-
cial del método Simplex es el problema Klee-Minty. La idea básica es deformar
un hipercubo de tal manera que el método deba recorrer todas las aristas antes
de llegar al punto óptimo. Inicialmente fue propuesto en 1972 por Klee y Minty
con la forma

maximizar
x

yn

s.a. �yj−1 ≤ yj ≤ 1− �yj−1, j = 2, . . . , n,
yj ≥ 0, j = 1, . . . , n.

Poco después Chvátal propuso[3] el cambio de variable x1 = y1, xj =
(−1/�)yj−1 + yj , lo que permite formular el problema como es más popular-

*Este documento no contiene un tratado riguroso de los m�etodos. Se crea a manera de
resumen y se omiten muchos detalles t�ecnicos.

1

Page 2

Figura 1: Politopos de Klee-Minty de dos y tres dimensiones[4].

mente conocido,

maximizar
x

n∑
k=1

10n−kxk

s.a. 2

j−1∑
k=1

10j−kxk + xj ≤ 100j−1, j = 1, . . . , n,

xj ≥ 0, j = 1, . . . , n.

Los resultados del problema Klee-Minty, utilizando el algoritmo programado
y mostrado en la sección Código, son

Dimensiones Iteraciones

3 50
5 47
6 31
8 35
10 45

Esto claramente muestra la complejidad exponencial del método. Por lo mis-
mo, muchos de los esfuerzos comenzaron a enfocarse en métodos de puntos
interiores, los cuales exhib́ıan caracteŕısticas deseables como complejidad poli-
nomial.

2. Métodos de Puntos Interiores

Los métodos de puntos interiores han sido foco de atención desde que se
mostró que existen problemas de complejidad exponencial para el método Sim-
plex, y existe una variedad éstos.1 En esta sección explicaremos brevemente el

1Un contraste interesante es que el método Simplex genera su complejidad del número de
restricciones que presenta el problema, mientras que los métodos de puntos interiores generan

2

Page 3

método elipsoidal y el método primal-dual infalible, y dejaremos de lado los
demás por cuestiones de espacio. La tabla[4] presentada continuación resume la
información.

Año Método Autor Caracteŕıstica

1947 Simplex Dantzig Eficiente en la práctica
1979 Elipsoidal Khachiyan Ineficiente en la práctica
1990 Primal-Dual Kojima, Mizuno, Yoshise Método Dominante

Infactible

2.1. Método Elipsoidal de Khachiyan

2.1.1. ¿En qué consiste?

La idea básica del método elipsoidal se deriva de investigaciones previas,
durante los años sesenta y setenta, dentro de lo que era la Unión Soviética.
De manera burda, la idea es encerrar la región de interés en una sucesión de
elipsoides que decrecen de tamaño cada vez más. La contribución de Khachiyan
fue demostrar en sus dos publicaciones -publicadas en 1979 y 1980- que bajo
ciertas condiciones el método tiene complejidad polinomial para problemas de
programación lineal.

2.1.2. ¿Cómo se construye el punto inicial y la sucesión de elipsoi-
des?

El método construye una elipsoide inicial que cubre P , el conjunto de fac-
tibilidad, completamente. Se toma el centro de ese elipsoide y se identifica si
se encuentra dentro de la región factible P . Si se encuentra dentro, el proble-
ma es factible, si no se encuentra dentro se puede construir un elipsoide nuevo
(en tiempo polinomial), tomando en cuenta la variable que corresponde a la
restricción de ATx ≤ b que es violada, que cubra completamente la mitad del
elipsoide anterior del lado donde se encuentra P . Procedemos de esta manera
hasta que se encuentra un centro dentro de la región factible, o se alcanza el
número máximo de iteraciones disponibles (el resultado en este caso seŕıa que
el problema es no factible).

2.1.3. ¿Por qué es un método polinomial?

Bajo dos condiciones, que explicaremos a continuación, Bertismas y Tsitsiklis
mostraron[5] que el método elipsoidal resuelve problemas de programación lineal
en tiempo O(m4 log(R/r)). Antes de definir las condiciones debemos definir el
conjunto poliédrico del problema (representación del problema de programación
lineal de manera vectorial):

P = {x ∈ Rm : aTj x ≤ cj , j = 1, . . . , n}

su complejidad debido al n�umero de variables en el problema.

3

Page 4

Figura 2: Elipsoides con y sin región factible[8].

Si P 6= ∅ el problema tiene solución. Las dos condiciones para que el algoritmo
converja en tiempo polinomial son:

1. ∃ x0 ∈ Rm, ∃ r ∈ R, r > 0, t.q. P ⊂ S(x0,R) = {x ∈ Rm : ‖x− x0‖ ≤ R},

2. ∃ r ∈ R, r > 0 conocido t.q. si Y 6= ∅ =⇒ S(x∗, r) ⊂ Y,

donde S(y, r) es una bola con centro en y y radio r. La primer condición
implica que P está acotado. La segunda condición implica que si P es no vaćıo,
entonces su interior tampoco es vaćıo; i.e. existe un sentido de densidad.

Dado que tenemos un sentido de densidad, podemos construir cualquier elip-
soide necesaria. La parte computacionalmente más compleja del método es preci-
samente la construcción del elipsoide de volumen mı́nimo. Sin embargo, sabemos
que este proceso es de complejidad polinomial, por lo que, de manera burda,
podemos extender esto al hecho de que el método es de complejidad polinomial.
En la teoŕıa se pueden construir (con aritmética exacta) sucesiones infinitas de
elipsoides, pero en la práctica (aritmética de precisión finita) se establece una
cota al número de iteraciones que si es superada el problema se considera que
éste es infactible.

2.1.4. ¿Cuál es la relevancia teórica del método y por qué no es
práctica su implementación para programación lineal?

La relevancia teórica del método reside en el hecho de que antes de la publi-
cación del mismo no se hab́ıan logrado clasificar los problemas de programación
lineal en alguno de los conjuntos de problemas P o NP, i.e. los que se pueden
resolver en tiempo polinomial y los que no, respectivamente. Se créıa que es-
tos problemas no tienen una complejidad tal que deben ser clasificados en NP,
pero nadie hab́ıa conseguido demostrar su pertenencia a P hasta que Kachiyan
publicó su método elipsoidal. Además el método sirve para construir algorit-
mos para problemas de optimización convexa, que son más generales que los de
programación lineal.

4

Page 5

La experiencia computacional muestra que las iteraciones necesarias para
resolver problemas de programación lineal usando este método se encuentran
muy cercanas al ĺımite teórico superior. Esto significa que prácticamente el al-
goritmo no es muy bueno. El método Simplex, aunque tiene una complejidad
exponencial, en la práctica la experiencia muestra que son necesarias muchas
menos iteraciones que el ĺımite teórico máximo, haciéndolo un candidato para
aplicaciones prácticas.

2.2. Método Primal-Dual Infactible de Kojima, Mizuno &
Yoshie

2.2.1. ¿En qué consiste?

El método consiste en tomar un punto nuevo en cada iteración a lo largo
de la dirección de Newton, en la dirección de la trayectoria central, como lo
hacen otros métodos de puntos interiores. La diferencia es que éste método no
requiere que los puntos estén dentro de la región factible. Éste método aplica
pasos largos y distintos entre el los problemas primal y dual, y se caracteriza
por convergencia global en tiempo polinomial2

2.2.2. ¿Cómo se construye el punto inicial y la sucesión de puntos?

Dado que es un método infactible, tenemos que no es necesario construir un
punto inicial, i.e. cualquier punto (xi, yi, zi) en el espacio, con xi ≥ 0, zi ≥ 0,
convergerá eventualmente a una solución. Es necesario notar que hay casos en
programación no-lineal donde ésta solución puede ser no-óptima, pero en el caso
de programación lineal, siempre convergerá a una solución óptima.

La sucesión de puntos se construye utilizando los problemas primal y dual

P : minimizar
x

cTx

s.a. Ax = b, x ≥ 0
D : maximizar

y,z
bT y

s.a. AT y + z = c, z ≥ 0

En cada iteración se resuelve el sistema
 A 0 00 AT I
Zk 0 Xk




∆x∆y

∆z


 = −


 Axk − bAT yk + zk − c

XkZk − µe




donde Zk y Xk son las matrices con la diagonal igual a zk y xk, respecti-
vamente. Cada una de las restricciones (ecuaciones del sistema lineal) vienen

2Para ser rigurosos debeŕıamos definir los conceptos direcci�on de Newton, trayectoria cen-
tral, pasos largos, problema primal y problema dual . Sin embargo, por cuestiones de espacio
no profundizaremos en ellos.

5

Page 6

de la búsqueda de cerar la brecha en la restricción de factibilidad de P , la res-
tricción de factibilidad de D y la restricción de la brecha entre los problemas,
XkZk = µe, respectivamente. Posteriormente se actualizan las variables

(xk+1, yk+1, zk+1) = (xk, yk, zk) + α(∆x,∆y,∆z)

Los detalles técnicos, por ejemplo como escoger α en cada iteración, la ob-
tención de la factibilidad, la convergencia global o la identificación de la no-
factibilidad, no serán explicados en este documento. Sin embargo, esto no sig-
nifica que carezcan de gran importancia.

2.2.3. ¿Por qué es un método polinomial?

Aunque el cálculo de cada iteración es significativamente más alto que el
método Simplex, cada iteración conlleva progreso mucho más significativo hacia
el óptimo, suponiendo que existe. Además es un camino mucho más directo (si-
gue el llamado central path). La complejidad del algoritmo radica en la solución
de un sistema de ecuaciones lineales que, aunque puede ser complicado, sabe-
mos que podemos hacer en tiempo polinomial, por lo que el algoritmo también
muestra tiempo polinomial3.

2.2.4. ¿Cuál es la relevancia del método y por qué es práctica su
implementación para programación lineal?

El método se encuentra dentro de los más populares hoy en d́ıa y exhibe
los mejores resultados prácticos. En promedio le toma entre 23 y 25 iteraciones
resolver los problemas más complejos (con solución) que existen hoy en d́ıa en
programación lineal. Además, teóricamente es importante el método porque no
se restringe a comenzar con puntos dentro de la región factible, lo que puede
presentar un problema en śı mismo.

3. Código - Método Simplex Revisado

El código aqúı presentado es una pequeña variación del método Simplex que
utiliza un tableu más pequeño porque no guarda espacio para las columnas B
de A = [N |B] que contienen la identidad en cada iteración. En realidad no
es necesario almacenar ésta identidad. La utilización de este método es para
mejorar el desempeño en el RAM de la computadora4.

/*
* Programacion Lineal - Metodo Simplex Revisado

* Omar Trejo Navarro

* 119711

*

3Claramente esta es una implicaci�on burda y es necesario sustentarla de manera rigurosa,
pero dicha prueba no ser�a presentada en este texto.

4Para los problemas pedag�ogicos que resolveremos en clase este detalle es intrascendente.

6

Page 7

* r := y = maximizar, n = minimizar

* nv := numero de variables de funcion objetivo

* nr := numero de restricciones

* t := tableu

* tipo := 1 = maximizar, -1 = minimizar

* ai := auxiliar para inputs

* optimo := true = alcanzado, false = no alcanzado

* xmax := maximo de coeficientes de funcion objetivo

* bamin := mininmo de b_i/a_ij

* aux := variable auxiliar

* rp := indice del renglon pivote

* cp := indice de la columna pivote

* error := true = no acotado, false = acotado

* CMAX := maxima cantidad de restricciones

* VMAX := maxima cantidad de variables

*
*/

#include <stdio.h>
#include <math.h>

#define CMAX 10
#define VMAX 10

int nr, nv, rp, cp;
bool optimo, error;
double t[CMAX][VMAX];

void datos() {
/*
* Obtener los datos del problema

*/
char r;
int i, j;
double tipo, ai;
printf("\n Programacion Lineal - Metodo Simplex Revisado\n");
do {

printf("\n Maximizar [s/n] ? ");
scanf("%c", &r);
if (r == 'S' || r == 's')

tipo = 1;
else if (r == 'N' || r == 'n')

tipo = -1;
else

printf("\n [!] Error. Debe indicar si (s) o no (n).\n\n")←↩
;

} while (r != 'S' && r != 's' && r != 'N' && r != 'n');
printf(" Cantidad de variables ? "); scanf("%d", &nv);
printf(" Cantidad de restricciones ? "); scanf("%d", &nr);
// Funcion objetivo
printf("\n Funcion objetivo:\n");
for (j = 1; j <= nv; j++) {

printf(" Coeficiente de la variable %d ? ", j);
scanf("%lf", &ai);
t[1][j + 1] = ai * tipo;

}
printf(" Valor de la constante ? ");

7

Page 8

scanf("%lf", &ai);
t[1][1] = ai * tipo;
// Restricciones
for (i = 1; i <= nr; i++) {

printf("\n Restriccion %d:\n", i);
for (j = 1; j <= nv; j++) {

printf(" Coeficiente de la variable %d ? ", j);
scanf("%lf", &ai);
t[i + 1][j + 1] = -ai;

}
printf(" Constante de restriccion ? ");
scanf("%lf", &t[i + 1][1]);

}
// Indices de las variables
for (j = 1; j <= nv; j++)

t[0][j + 1] = j;
for (i = nv + 1; i <= nv + nr; i++)

t[i - nv + 1][0] = i;
}

void pivotear() {
/*
* Hacer el cambio de pivotear

*/
double bamin, aux, xmax;
int i, j;
xmax = 0;
// maximo {costos reducidos}
for (j = 2; j <= nv + 1; j++) {

if (t[1][j] > 0 && t[1][j] > xmax) {
xmax = t[1][j];
cp = j;

}
}
bamin = 1000000;
// minimo {b_i/a_ij}
for (i = 2; i <= nr + 1; i++) {

if (t[i][cp] < 0) {
aux = fabs(t[i][1] / t[i][cp]);
if (aux < bamin) {

bamin = aux;
rp = i;

}
}

}
// Cambio de indices
aux = t[0][cp];
t[0][cp] = t[rp][0];
t[rp][0] = aux;

}

void actualizar() {
/*
* Actualizar el tableu

*/
int i, j;
for (i = 1; i <= nr + 1; i++)

8

Page 9

if (i != rp)
for (j = 1; j <= nv + 1; j++)

if (j != cp)
t[i][j] -= t[rp][j] * t[i][cp] / t[rp][cp];

t[rp][cp] = 1.0 / t[rp][cp];
for (j = 1; j <= nv + 1; j++)

if (j != cp)
t[rp][j] *= fabs(t[rp][cp]);

for (i = 1; i <= nr + 1; i++)
if (i != rp)

t[i][cp] *= t[rp][cp];
}

void revisar() {
/*
* Revisar optimalidad del tableu

*/
int i, j;
optimo = true;
error = false;
// Revisar si es no-acotado
for (i = 2; i <= nr + 1; i++)

if (t[i][1] < 0)
// TODO: Avisar que es no acotado
error = true;

// Revisar si es optimo
if (error == false)

for (j = 2; j <= nv + 1; j++)
// TODO: Revisar si hay solucion multiple
if (t[1][j] > 0)

optimo = false;
}

void simplex() {
/*
* Metodo Simplex Revisado

*/
while (optimo == false) {

pivotear();
actualizar();
revisar();

}
}

void resultados() {
/*
* Presentar los resultados

*/
int i, j;
printf("\n Resultados:\n");
if (error == false) {

for (i = 1; i <= nv; i++)
for (j = 2; j <= nr + 1; j++)

if (t[j][0] == 1 * i)
printf(" Variable %d: %f\n", i, t[j][1]);

printf(" Funcion objetivo: %f\n\n", t[1][1]);
} else

9

Similer Documents