1

El Mtodo SimplexEl Mtodo Simplex(1)(1)

Para solucin de problemas de Para solucin de problemas de optimizacin linealoptimizacin lineal

(1) Basado en las notas de Stephen Boyles. Fall 2009http://www.uwyo.edu/sboyles/teaching/ce4920/lp_notes.pdf

2

Forma estndarForma estndarSea el programa de optimizacin lineal en forma estndar

donde

n variables desconocidasm restricciones

3

Un ejemploUn ejemploConsideremos el siguiente problema

(No est en forma estndar)

4

Grficamente: RestriccionesGrficamente: Restricciones

x2 = 14-2x1

x2 = 7 - 3x1/5

-5 0 5 10 15 20-5

0

5

10

15

20

x1

x2

5

Funcin objetivoFuncin objetivo

-5 0 5 10 15 20-5

0

5

10

15

20

x1

x2

Funcin objetivoigualada a una constante -x1-x2 = Kdefinehiperplanos de valor constante

6

Caractersticas de los problemas de Caractersticas de los problemas de optimizacin linealoptimizacin lineal

Todo programa lineal es convexo Se llaman puntos extremos a los puntos de

interseccin de 2 o ms restricciones Teorema fundamental de la programacin

lineal: "Si un problema de optimizacin lineal tiene

una solucin ptima, al menos un punto extremo es una solucin ptima".

7

Puntos extremos = Puntos ptimosPuntos extremos = Puntos ptimos

-5 0 5 10 15 20-5

0

5

10

15

20

x1

x2

8

Puntos extremosPuntos extremos

Ejemplos: En 2 dimensiones (n=2), las restricciones son

lneas, y la interseccin de 2 lneas define un punto.

En 3 dimensiones, las restricciones son planos. La interseccin de 3 planos es un punto (salvo excepciones).La interseccin de 2 planos es una lnea, o es vacia. La interseccin de 4 o ms planos es vacia (salvo casos excepcionales).

9

Consideraciones sobre Consideraciones sobre puntos extremos (1)puntos extremos (1)

Considerando el sistema de ecuacionesAx=b

pueden presentarse varios casos: m>n: Hay ms restricciones que variables.

Generalmente no tiene solucin, y cuando la tiene, es porque hay ecuaciones linealmente dependientes unas de otras.

10

Consideraciones sobre Consideraciones sobre puntos extremos (2)puntos extremos (2)

En general si existen ecuaciones linealmente dependientes, se pueden eliminar. En adelante se asume que las m restricciones son linealmente independientes.

m=n : Igual nmero de restricciones y variables. El sistema tiene una nica solucin x*. Si esta solucin es factible, i.e. x*0, entonces esta es la solucin al problema. (Caso trivial).

11

Consideraciones sobre Consideraciones sobre puntos extremos (3)puntos extremos (3)

m

13

Consideraciones sobre Consideraciones sobre puntos extremos (5)puntos extremos (5)

A las variables xB se les llama una base. El vector (xB,0) es una solucin factible de

Ax = b Si adicionalmente su cumple que xB0,

decimos que es una solucin bsica factible (Basic Feasible Solution - BFS) del problema de optimizacin.

A las variables xNB se les llama no bsicas.

14

Regla general para encontrar Regla general para encontrar puntos extremospuntos extremos

Tomar conjuntos de n restricciones. (En total son m restricciones de la forma aTx=b y n restricciones xi0).

Hallar la interseccin entre ellas. Descartar puntos no factibles no satisfacen

las otras restricciones. El nmero de puntos a probar es finito:

15

Solucin... poco eficienteSolucin... poco eficiente Evaluar la interseccin de cada una de estas

combinaciones de restricciones. Si x es factible, evaluar la funcin objetivo. Descartar aquellos casos en los que no es

factible. De todas las soluciones factibles tomar la

menor.

16

Caractersticas de puntos extremosCaractersticas de puntos extremos Restricciones activas: La restricciones que se

satisfacen con igualdad en el punto extremo. Puntos extremos adyacentes: Solo difieren en

una restriccin activa.

17

Idea central del mtodo SimplexIdea central del mtodo Simplex Seleccionar un punto extremo. Si un punto extremo adyacente produce una

reduccin de la funcin objetivo, moverse a este punto extremo.

Cuando ninguno de los puntos extremos adyacentes al punto actual reduce la funcin objetivo, este punto es ptimo.

18

Determinando puntos extremosDeterminando puntos extremosDado el sistema

Se seleccionan n variables xB y se resuelve.Las restantes (n-m) variables se hacen cero y forman xNB.Si la solucin encontrada es factible, este es un punto extremo.

20

Movimiento a puntos extremos Movimiento a puntos extremos adyacentesadyacentes

Supongamos que la variable xk= entra a la base. Entonces las variables bsicas actuales deben cambiar dB para mantener la igualdad de las restricciones

es decir, todas las variables bsicas se afectan en proporcin a , siendo el factor de proporcin

21

Movimiento a punto extremo Movimiento a punto extremo adyacenteadyacente

Si entra xk, una de las variables xixB debe hacerse cero. Se selecciona la variable xi como la primera que se haga cero (si alguna se hace menor que cero, la solucin no es factible).

Obsrvese que si xi0.

22

Determinando la nueva variable Determinando la nueva variable bsicabsica

Se debe seleccionar el mnimo que causa que una xi se haga cero:

Cuando todos los xi son negativos, la base actual es el punto ptimo.

23

Efecto en el valor de la funcin Efecto en el valor de la funcin objetivoobjetivo

La nuevo valor de la funcin objetivo es

como se trata de un problema de minimizacin, el cambio en la funcin objetivo debe ser negativo

se denomina la reduccin de costo de la kth variable de decisin a la cantidad

24

El mtodo SimplexEl mtodo Simplex1. Se identifica una base factible inicial B (BFS=Basic

Feasible Solution).2. Se calculan las reducciones de costo para cada una

de las variables kB.3. Si todas las reducciones de costo son no-negativas,

terminar. La base actual es ptima.4. Escoger una variable no bsica xk, kB para que

entre a la base, y determinar el valor que hace que una de las variables bsicas se haga cero.

5. Repetir a partir del paso 2.

25

EjemploEjemplo Tomemos el siguiente ejemplo

26

Transformacin a forma estndarTransformacin a forma estndar Agregamos las variables (slack/exceso) x4, x5,

x6 para llevarlo a forma estndar

27

Determinar una BFSDeterminar una BFS Observar que la asignacin

x = (0, 0, 0, 10, 20, 5)es una BFS, para la cual la funcin objetivo es 0.

Se identifican las componentes B y N de A

BN

28

Buscar otras componentes que Buscar otras componentes que reduzcan el costoreduzcan el costo

Posibles candidatas a entrar en la base son xk para k={1,2,3}. Se clcula la reduccin de costo correspondiente a cada una

Se pueden seleccionar x2 x3 para entrar a la base. Digamos que entra x2.

29

Encontrar el valor de la variable Encontrar el valor de la variable bsica que entrabsica que entra

Necesitamos tal que una de las variables de la base anterior se haga cero.

Se clcula el cambio de cada una de las variables

Y se determina el mximo lambda posible

31

Nuevo valor ptimoNuevo valor ptimo Se obtiene de

logrando una reduccin respecto al valor original de 0. Si se calculan las reducciones de costo con respecto

a las variable no bsicas se encuentra:

Se puede hacer una nueva iteracintrayendo a x3 a la base