programación lineal: 1- introducción: dualidad, definiciones, holguras complementarias, etc. 2-...

1- Introducción

3

REPASO:

• Problemas de Optimización: son problemas de asignación óptima de recursos limitados, para cumplir un objetivo dado que representa la meta del decisor. Los recursos pueden corresponder a personas, materiales, dinero, etc. Entre todas las asignaciones de recursos admisibles, se quiere encontrar la/s que maximiza/n o minimiza/n alguna cantidad numérica tal como ganancias o costos, etc.

• Modelo de Optimización Matemática: es una representación matemática de una cierta “realidad” y consiste en una función objetivo y un conjunto de restricciones en la forma de un sistema de ecuaciones o inecuaciones.

Proceso de optimización-modelado

• Aplicaciones: Los problemas de optimización son muy comunes en el modelado matemático de sistemas reales en un amplio rango de aplicaciones: economía, finanzas, química, astronomía, física, medicina, computación, ...

• Proceso de optimización y modelado: requiere de varios pasos: descripción del problema, elaboración y emisión de una solución, control y actualización de la solución si hay cambio de parámetros o de la estructura misma del problema.

No

Problema de decisión

Etapa de análisisModelado matemático

Validado?

Implementación

Verificado?

Etapa de diseñoInterpretación de la solución

Etapa de controlImplementación

Si

Si

No

Componentes de problemas de optimización

• Función objetivo:la mayoría de los problemas de optimización tienen una función objetivo pero hay casos de varias funciones objetivo (programación multiobjetivo) o incluso puede no tener función objetivo (interesan soluciones factibles solamente)

• Entradas controlables son las variables de decisión, cuyos valores afectan la función objetivo y restricciones.

• Entradas no controlables (parámetros), se fijan a priori y dependen del problema particular, a veces se requiere un análisis de sensibilidad o uno paramétrico frente a variaciones de los mismos.

• Restricciones: son relaciones entre parámetros y variables de decisión. Restricciones “duras” o esenciales y “débiles”

• Limitaciones de los modelos: información incompleta, simplificaciones y errores numéricos, tecnología limitada.

• Problemas de toma de decisiones se pueden clasificar en dos categorías:– Modelos determinísticos: no se considera el riesgo,

hipótesis de información completa.– Modelos probabilísticos: información incompleta,

resultados probabilísticos

• Clasificación problemas optimización y complejidad:– Según el tipo de variables: contínua, discreta, binaria,

mixta– Según el tipo de funciónes objetivo y restricciones:

lineal , no lineal, cuadrática, convexa, no convexa, diferenciable, no diferenciable

• Métodos de resolución: – Optimización global y local– exactos (global), heurísticas (local)– Simplex, métodos de punto interior, gradiente proyectado, etc

• Programación lineal (PL): aborda una clase de problemas de programación donde tanto la función objetivo a optimizar como todas las relaciones entre las variables correspondientes a los recursos son lineales.

• Hoy en día, esta técnica se aplica con éxito para resolver problemas de presupuestos de capital, diseño de dietas, conservación de recursos, juegos de estrategias, predicción de crecimiento económico, sistemas de transporte,etc.

• En este curso se presentarán técnicas para resolución de problemas de PL contínua y discreta

UN POCO DE HISTORIA ...

1. Siglo XVIII: En 1762, Lagrange resuelve problemas de optimización con restricciones de igualdad.

2. Siglo XIX: En 1820, Gauss resuelve sistemas de ecuaciones lineales por el método conocido como “eliminación Gaussiana”. En 1866 Wilhelm Jordan mejora esta técnica y elabora el método conocido como “Gauss-Jordan“.

3. Siglo XX:

– En 1945, aparece la computación digital

– En 1947, Dantzig inventa el método Simplex.

– En 1968, Fiacco and McCormick introducen los métodos de Punto Interior.

– En 1984, Karmarkar aplica los métodos de Punto Interior para resolver Programas Lineales aportanto un análisis innovador.

SIMPLEX

• Hacia 1945, Dantzig desarrolló el método SIMPLEX para resolver el problemas de programación lineal (PL)

• Es un método eficiente, el más utilizado hasta el momento

• NO es un algoritmo de complejidad polinomial. En el peor caso, es un algoritmo de complejidad exponencial con el número de variables del poblema

11

METODO DEL ELIPSOIDE

• En 1978 Khachian aplicó el método elipsoidal (de Shor, Yudin y Nemirovskii) para resolver (PL) y encontró una cota superior polinomial O(n4L) al número de operaciones aritméticas que realizaba su algoritmo.

• Lamentablemente es un algoritmo pseudo-polinomial ya que su complejidad depende de L= largo de los datos de entrada.

• La existencia de un algoritmo polinomial cuya complejidad dependa únicamente de la cantidad de variables y restricciones es un problema difícil, aún abierto.

• El método causó gran revolución teórica pero desafortunadamente las implementaciones prácticas no han sido eficientes.

12

METODO DE KARMARKAR

• En 1984 Karmarkar publicó un algoritmo para resolver (PL) de complejidad polinomial O(n3.5L) mejorando la performance alcanzada por Kachian y anunció que era más eficiente que el SIMPLEX

• Actualente se sabe que este tipo de algoritmos son muy eficientes en casos de problemas de grandes dimensiones

• El algoritmo de Karmarkar en lugar de recorrer los vértices del poliedro determinado por S como en el SIMPLEX, evoluciona desde el interior relativo S0 como en los métodos de programación no lineal, siendo un método de punto interior.

• En este curso estudiaremos los llamados “Path-following methods for linear programming”

Sea el siguiente problema de optimización:(G) Min f(x) / xF

• DEF: d es una dirección de descenso (o ascenso) de la función f, diferenciable, en x*F si 0 tal que f(x+ d)<f(x) (0, 0 )en el caso de ascenso: f(x+ d)>f(x)

• OBS: Sea f una función diferenciable en x*F Si f(x).d <0, entonces d es una dirección de descenso en x*.

Generalidades

F

X*

d

f(x*)

f(x*+d)

).df(x )f(x d)f(x 1, *** Si

Funciones diferenciables:

• Caso optimización sin restriccionesCondición de óptimo local:

Puntos críticos:

Si existe mínimo

• Caso g(x) = 0 (multiplicadores de Lagrange)– Condición de óptimo local: gradiente ortogonal al

conjunto de soluciones factibles :

– Puntos críticos:

• Caso general g(x) 0 (Kuhn y Tucker)

0)( xf 0)(/ xfxX

Xxx **

0)(/ xgxF )(.)(/ xgxfxX

Sea (P) Min f(x) / gi(x) 0, con i=1...m x XSea , x un punto interior de X • Condiciones necesarias de óptimo de Kuhn–Tucker

son:– x es factible o sea: gi(x) 0, i=1...m– igi(x) = 0, i=1...m– i 0 , i=1...m– f(x)+ i.gi (x) =0

• Estas condiciones son necesarias para la existencia de un óptimo, para que resulten también suficientes, es necesario algunas hipótesis adicionales sobre f y el conjunto de restricciones

Sean:(G) Min f(x) / xF

(GL) Min fL(x) / xFL

DEF: GL es una relajación de G si: 1- FL F

2- fL(x) f(x) x F

DEF: relajación Lagrangeana (P) Min f(x) / g(x) 0 x X y

(P) Min f(x) + j*gj(x) / xX

P es una relajación Lagrangeana de M

OBS: toda relajación Lagrangeana con 0 de un problema (P) es una relajación de (P)

• DEF: problema dual

Dados los problemas P y P , se define el dual D de P como (D) Max () / 0, siendo:

()= Min (f(x) + j*gj(x) )

xX

• Sean d=Max () / 0 y p=Min f(x) / g(x) 0 x X

• DEF: gap de dualidad= = p-d

• NOTA: p d

• Ejemplo