Matematica

PROGRAMACIÓN LINEAL

Es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones 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 estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas de optimización constituyen casos particulares de la más amplia técnica de la programación lineal. Históricamente, las ideas de programación lineal han inspirado muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo modo, la programación lineal es muy usada en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la asignación de recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc.

SOLUCIONES GRAFICAS

El análisis gráfico es una alternativa eficiente para enfrentar la resolución de modelos de Programación Lineal en 2 variables, donde el dominio de puntos factibles (en caso de existir) se encontrará en el primer cuadrante, como producto de la intersección de las distintas restricciones del problema lineal.

Una de las propiedades básicas de un modelo de Programación Lineal que admite solución, es que ésta se encontrará en el vértice o frontera (tramo) del dominio de puntos factibles. Es decir, si luego de graficar el dominio y evaluar los distintos vértices de modo de elegir "el mejor" candidato según sea nuestro caso (el valor de la función objetivo será la que nos permitirá discriminar cual es el mejor candidato dependiendo si estamos maximizando o minimizando).

Consideremos un Ejemplo Introductorio en 2 variables:

• D) MIN 8X + 6Y

• S.A. 2X + Y >= 10

• ...... .2X + 2Y >= 16

• ..... ..X>= 0, Y>= 0

Comentario: Nótese que corresponde al problema dual de p) cuya resolución se presenta en nuestro sitio como ejemplo introductorio en la utilización de solver de ms excel. para ver el detalle de la resolución gráfica de p) se recomienda al usuario ingresar aqui.

Para resolver el problema D) graficamos el dominio de puntos factibles y las curvas de nivel asociadas a la función objetivo:

El área achurada en color verde representa el dominio de puntos factibles del problema D), es decir, son las distintas combinaciones de valores que pueden adoptar las variables de decisión que satisfacen las restricciones del problema. Cabe destacar que esto corresponde a un dominio no acotado, lo que no implica que el problema no tenga solución.

Por otra parte sabemos que el óptimo de un problema lineal se encuentra en un vértice o frontera del dominio de puntos factibles. En este caso tenemos 3 vértices candidatos al óptimo los cuales se señalan con flecha blanca y azul. El vértice (X,Y)= (0,10) con V(P)=60; (X,Y)=(2,6) con V(P)=52 y (X,Y)=(8,0) con V(P)=64. El mínimo valor para la función objetivo se alcanza en (X,Y)=(2,6) con V(P)=52, el cual resulta ser la Solución Óptima de D). Sin embargo, una forma más eficiente para obtener el óptimo que no implique evaluar cada vértice en la función objetivo, es desplazando las curvas de nivel de la función objetivo en la dirección del máximo decrecimiento (en el caso de un problema de minimización). Para un problema de minimización, el mayor decrecimiento se alcanza en la dirección del vector " - Gradiente F(X,Y)", en nuestro caso el vector con dirección (-8,-6) (dirección representada por flecha roja). Luego, el óptimo se alcanza en el último punto donde las curvas de nivel intersectan al dominio de puntos factibles en la dirección del máximo decrecimiento, cuya solución obviamente corresponde a (X,Y)=(2,6) con V(P)=52.

ALGORITMOS SIMPLEX

Algoritmo simplex habitualmente se refiere a un conjunto de métodos muy usados para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo simplex primal fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. Un algoritmo simplex es un algoritmo de pivote.

Un método llamado de manera similar, pero no relacionado al anterior, es el método Nelder-Mead (1965) o método de descenso (o ascenso) símplex; un método numérico que busca un mínimo (o máximo) local de una función cualquiera examinando en cada paso los vértices de un simplex.

...