Post on 07-Oct-2015
description
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