Algoritmos

OPTIMIZACIÓN
Tema 1 Tema 2 Tema 3 Tema 4 Tema 5 Tema 6 CONJUNTOS CONVEXOS FUNCIONES CÓNCAVAS Y CONVEXAS CONSIDERACIONES GENERALES SOBRE LA OPTIMIZACIÓN OPTIMIZACIÓN SIN RESTRICCIONES LAGRANGE Y kHUN TUCKER PROGRAMACIÓN LINEAL

www.fonemato.com

Tema 6

Optimización lineal

6.01 6.02 6.03 6.04 6.05 6.06 6.07 6.08

Optimización lineal....................................................................................... Características de un programa lineal ......................................................... Soluciones básicas ......................................................................................... Relación entre vértice y solución factible básica ...................................... Algoritmo del simplex.................................................................................. El método de las dos fases .......................................................................... Dualidad ....................................................................................................... Condiciones de holgura complementaria .................................................. Test..................................................................................................................

110 111 111 113 113 122 124 125 137

Tema 6: Optimización lineal

109

6.1 OPTIMIZACIÓN LINEAL
Se dice que un programa de optimización es lineal si la función objetivo y todas las restricciones son lineales.

Denotando:

LM c:1 OP ; x = LM x:1 OP ; A = LM a11 c= : MNa m1 MNc n PQ MNx n PQ
Máx. c t • x s.a: Mín. c t • x::: a n1 b1 ::: : ; b= : ::: a mn bm

OP PQ

LM MN

OP PQ

la forma canónica de un problema lineal es la siguiente:

RA • x ≤ bU S x≥0 V T W RA • x ≥ bU s.a.: S T x≥0 V W

La forma estándar de un problema lineal es la siguiente: Máx. c t • x s.a: Mín. c t • x

RA • x = bU S x≥0 V T W RA • x = bU s.a.: S T x≥0 V W

Todo programa lineal puede expresarse en forma canónica y en formaestándar, pues:

1) Toda restricción de igualdad puede expresarse mediante dos restricciones de desigualdad. 2. x 1 + 3. x 2 ≤ 7 2. x 1 + 3. x 2 = 7 ⇔ 2. x 1 + 3. x 2 ≥ 7

{

2) Introduciendo una variable adicional, llamada de holgura, toda restricción de desigualdad puede expresarse mediante una restricción de igualdad y otra de no negatividad de la variable de holgura introducida.
2. x 1 +3. x 2 ≤ 7 ⇔

{2.3x1≥ + 3. x 2 + x 3 = 7 0 x 2. x + 3. x 2 − x 3 = 7 2. x 1 + 3. x 2 ≥ 7 ⇔ { 1 x3 ≥ 0
2. x 1 + 3. x 2 ≤ 7 ⇔ −2. x 1 − 3. x 2 ≥ −7

2) El sentido de la desigualdad cambia multiplicando ambos miembros por −1.

Llamaremos actividad Pj a la j-ésima columna de la matriz "A".

Tema 6: Optimización lineal

110

6.2 CARACTERÍSTICAS DE UN PROGRAMA LINEAL
imización 1) Todoprograma lineal de max imización es convexo, pues la función objemin cóncava tivo, por ser lineal, es convexa , y el conjunto de soluciones factibles es convexo, ya que todas las restricciones son lineales. Así, el teorema Local/Global garantiza que la solución óptima, si existe, es global. 2) Si un programa lineal tiene solución única, es un vértice del CSF. Por reducción al absurdo: supuesto que elproblema es de máximo y que tiene solución única x* (o sea, en todo punto x ≠ x * del CSF es c t • x < c t • x *), si x* no fuera vértice del CSF, sería interior a algún segmento contenido en el

{

}

{

}

CSF; es decir, existirían λ ∈[ 0 ; 1] y sendos puntos x 0 ≠ x * y x 1 ≠ x * del CSF
tales que x * = λ • x 0 + (1 − λ ) • x 1. Así: c t • x * = c t • λ • x 0 + (1 − λ ) • x 1 = λ .(c t • x 0 ) + (1 − λ ).( c t • x 1 ) < pues c t • x 0 < c t • x * y c t • x 1 < c t • x * < λ .( c t • x *) + (1 − λ ).( c t • x *) = c t • x * ⇒ absurdo

e

j

3) Si el óptimo de un programa lineal se presenta en más de un vértice, toda
En efecto, si los vértices x y x son óptimos, es c • x = c • x . Así, si
λ ∈[ 0 ; 1] y x = λ • x 0 + (1 − λ ) • x 1 , es:
combinación lineal convexa...