Metodo Simplex

M´ todos Matem´ ticos de Especialidad e a
Ingenier´a El´ ctrica ı e

1/92

´ Programacion Lineal
´ El metodo SIMPLEX 1
Jos´ Luis de la Fuente O’Connor e
jl.delafuente@iberdrola.es jldelafuente@etsii.upm.es Escuela T´ cnica Superior de Ingenieros Industriales e Universidad Polit´ cnica de Madrid e

Clase_simplex_1_06.pdf

Ant.

2/92

´ndice I
´ • Introduccion ´ ´ • Mejora de unasolucion basica factible ´ • Finalizacion • El algoritmo SIMPLEX
´ • Degeneracion y ciclado

´ ´ • Solucion basica factible inicial

Ant.

´ Introduccion
´ – Para resolver un problema de programacion lineal, min. cT x s. a

3/92

Ax = b x ≥ 0,

se pueden estudiar los puntos extremos del politopo P = {x ∈ Rn : Ax = b, x ≥ 0}, donde A ∈ Rm×n y b ∈ Rn, y buscar ´ ı aquel en el que lafuncion objetivo cT x se hace m´nima.

• Analizar todos esos puntos extremos, dado el numero posible de ´
ellos,

n! m!(n − m)!
para m y n grandes puede resultar prohibitivo.
Ant.

4/92

– En 1947, George B. Dantzig, culminando el trabajo de un importante ´ ´ equipo de matematicos y economistas, desarrollo el denominado ´ METODO SIMPLEX. – La idea que lo anima es la siguiente: ´ •Primero, encontrar un punto extremo del politopo P , o solucion ´ basica factible;

• luego, desplazarse desde ese punto extremo a otro, a lo largo de ´ alguna arista de P , mejorando (haga menor) la funcion objetivo. • Repetir el paso anterior cuantas veces sea necesario hasta que ´ ´ se alcance la solucion optima o la arista escogida lleve a −∞.

Ant.

5/92

´ ´ Mejora de una solucion basicafactible
– Supongamos que: ´ ´ • Partimos de una solucion basica factible (punto extremo). ´ • La matriz A ∈ Rm×n (m < n) es de rango completo y la region factible no es el conjunto vac´o. ı ´ ´ • En una solucion basica factible los m primeros componentes de x ´ son no negativos –basicos–.

Ant.

– Ordenando A de la forma A = [B, N ], y, de la misma manera, ´ cT = [cT , cT ], se tendra queB N

6/92

BxB + N xN = b,
de donde, despejando xB ,

xB = B −1b − B −1N xN .
´ ´ • El valor de la funcion objetivo para esta solucion es

z = [cT , cT ] B N

xB xN

= cT B −1b + (cT − cT B −1N )xN . B N B

´ ´ ´ • El punto que define esta solucion esta en la interseccion en Rn de los m hiperplanos correspondientes a las condiciones Ax = b y los n − m correspondientes a xN = 0 (nodegenerada) . ´ ´ • En ese punto extremo del politopo P que define la solucion basica factible no degenerada confluyen n − m aristas.
Ant.

– Consideremos la matriz

7/92

M=

B N 0 I

,

cuyos vectores fila son los vectores caracter´sticos de los n hiperplanos ı ´ ´ que determinan la solucion basica. Como la matriz B es regular, M ´ tambien es regular. – Las direcciones de esas aristasson las que determinan los n − m ultimos vectores columna de la inversa de la matriz M : ´

M

−1

=

B −1 −B −1N 0 I

.

• Moverse a lo largo de cada una de esas n − m aristas equivale a
´ incrementar el valor de una variable no basica manteniendo las ´ demas fijas a cero.
Ant.

´ – Para mejorar una funcion objetivo desde un punto extremo, interesa encontrar, de esas posibles n −m aristas por las que moverse, una ´ ´ que consiga hacer decrecer la funcion objetivo: direccion de descenso. – Para determinar esas direcciones se calculan los denominados costes reducidos:

8/92

¯ cj = cj − cT B −1aj = cT η j = cT M −1ej , B

j > m.

´ ¯ Si cj < 0, el vector c y el η j hacen angulo obtuso (> 90◦ ) por lo que la ´ ´ funcion objetivo decrece, al incrementar θ, moviendosea lo largo de η j .
´ • El coste reducido cj es la derivada direccional de z = cT x en la direccion η j . ¯
• El concepto coste reducido surge del hecho de que cj expresa el cambio que ¯

´ ´ supone en la funcion objetivo un incremento unitario en la variable no basica xj ´ ´ manteniendo todas las demas no basicas fijas. Es decir,
z(θ) = cT x(θ) = cT x + θcT η j = cT B −1 b + θ cj − cT B −1...