Programación Matemática

Programación Matemática:

Es un conjunto de teoremas, algoritmos, métodos y técnicas para resolver problemas de optimización económica. Todo problema de programación matemática consta de una función objetivo a maximizar o minimizar y de un conjunto de restricciones o ecuaciones de condición. Cuando la función objetivo y todas las restricciones son de tipo lineal estamos en presencia de un problema de programación lineal, que es la forma de programación matemática más desarrollada.

Este problema de programación lineal consiste en elegir aquel o aquellos valores de las variables instrumentales pertenecientes al conjunto de oportunidades S, es decir, X∈S, que proporcionan el mayor o menor valor de la función objetivo.

Existen diversos modelos de optimización los cuales se caracterizan por contener:

Variables o decisiones a realizar

Ecuaciones de restricción o limitaciones

Función (es) objetivo.

El planteamiento general del problema de programación matemática es:

Optimizar f(x1,x2,...,xn)

sujeto a: g1(x1,x2,...,xn) ≤ b1

g2(x1,x2,...,xn) ≤b2

. . .

gm(x1,x2,...,xn) ≤ bm

donde

f:Rn → R, x∈ Rn, g:Rn →Rm b ∈ Rm

La función f denominada función objetivo, es una función definida de un dominio de Rn sobre R, y representa una descripción matemática del objetivo que se pretende alcanzar con el problema planteado.

El vector X es el vector de variables instrumentales o variables de decisión, de entre cuyos valores posibles se trata de elegir aquél o aquellos que proporcionen el valor óptimo de la función f.

Conjunto de oportunidades, denominaremos así al conjunto de puntos X∈Rn que verifican todas y cada una de las restricciones y al mismo tiempo pertenecen al dominio de definición de la función.

Problema de programación matemática de la forma:

Max f(X)

s.a. g(X) ≤ b

Convenciones:

1.-Min f(X) = -Max[-f(X)]

2.- Restricciones: g(X)≤b. Si g1(X) ≥ b1 ; -g1(X) ≤ -b1

3.- Igualdades: h2(X)=b2, en g2(X) ≤b2 y -g2(X) ≤-b2

Teoremas Básicos de Optimización:

Teorema de Weierstrass

Si el conjunto de oportunidades S es compacto (cerrado y acotado) y no vacío y la función objetivo es continua en S, entonces dicha función alcanza un máximo y un mínimo global en el interior o en la frontera de S.

Efectivamente, dada:

f: D ⊆ Rn → R

si D es compacto y f es continua en D, entonces f(D) también será un conjunto compacto y por tanto tendrá, por ser acotado, un extremo inferior que representamos por m y uno superior M y además por ser cerrado m , M∈f(D), en consecuencia

∃ x1,x2 ∈ D / f(x1)=m y f(x2)=M

de donde

f(x1) ≤ f(x) ≤ f(x2) ∀x∈ D

siendo entonces x1 un mínimo global y x2 un máximo global.

Teorema local-global

Sea S ⊆ Rn un conjunto convexo y no vacio, y sea f: S → R.

Consideremos el siguiente problema:

Min F(x)

s.a. x∈S

Si que x* ∈ S es un mínimo local del problema anterior, entonces:

a) Si f es un función convexa, entonces x* es un mínimo global del problema.

b) Si f es un función estrictamente convexa, entonces x* es un mínimo global estricto del problema.

Programación Dinámica:

Se descompone el problema en subproblemas solapados y se va construyendo la solución s con las soluciones de esos subproblemas.

Esta técnica se aplica sobre problemas que presentan las siguientes características:

Subproblemas optímales: En la cual la solución óptima a un problema puede ser definida en función de soluciones óptimas a subproblemas de tamaño menor.

Solapamiento entre subproblemas: Al plantear la solución recursiva del problema, un mismo problema se resuelve más de una vez.

La programación toma normalmente el siguiente enfoque:

En el enfoque ascendente (bottom-up):

Primero se calculan las soluciones óptimas para problemas de tamaño pequeño.

Luego, utilizando dichas soluciones, encuentra soluciones a problemas de mayor tamaño.

La programación dinámica se utiliza para:

Caracterizar la estructura de una solución óptima.

Definir de forma recursiva la solución optima.

Calcular la solución optima de forma ascendente.

Construir la solución optima a partir de los datos almacenados al obtener soluciones parciales.

Para aplicar programación dinámica:

Se comprueba que se cumple el principio de optimalidad de Bellman para lo que hay que encontrar la “estructura” de la solución.

Principio de Bellman:

“Una política optima tiene la propiedad de que sean cuales sea el estado inicial y la decisión inicial, las decisiones restantes deben construir una solución optima con respecto al estado resultante de la primera decisión.”

En Informática, un problema que puede descomponerse de esta forma se dice que presenta subestructuras optímales.

El principio de optimalidad se verifica si toda solución óptima a un problema está compuesta por soluciones óptimas de sus subproblemas.

Se define recursivamente la solución óptima del problema (en función de los valores de las soluciones para subproblemas de menor tamaño).

Se calcula el valor de la solución optima utilizando un enfoque ascendente:

Se determina el conjunto de subproblemas que hay que resolver (el tamaño de tabla).

Se identifican los subproblemas con una solución trivial (caso base).

Se van calculando los valores de soluciones más complejas a partir de los valores previamente calculados.

Se determina la solución óptima a partir de los datos almacenados en la tabla.

Programación convexa: Rama de la programación matemática que trabaja con la teoría y métodos de minimización de funciones convexas sobre conjuntos convexos definidas mediante sistemas de igualdades y desigualdades. La programación cuadrática es una rama dentro de la programación convexa.

La programación lineal: es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.

Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función

...