Programacion Lineal Y Metodos Simples

Introducción

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 donde las variables que definen al mismo son conocidas pero se necesita encontrar la combinación de las mismas que permitan optimizar un rendimiento (maximizar un beneficio, minimizar costos o ambos).
Para la formulaciónde modelos es necesario seguir un orden, los cuales se presentaran más adelante. Al igual que el análisis de sensibilidad ya que es una de las partes más importantes en la programación lineal, sobre todo para la toma de decisiones. Los métodos a tratar son el método gráfico y el método simplex.

Historia de la programación lineal

El problema de la resolución de un sistema lineal de inecuacionesse remonta, al menos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lousaron en su planificación diaria.
Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantorovich, un matemático ruso, que utiliza técnicas similares en la economíaantes de Dantzig y ganó el premio Nobel en economía en 1975. Leonid Khachiyan en 1979 fue el primero endemostrar que el problema de la programación lineal se solucionaba en tiempo polinomial, sin embargo, el mejor avance en los principios teóricos y prácticos en el campo se produjo en 1984, cuando Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal.
El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestosde trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como unaprogramación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas.



METODO GRAFICO


1. TRAZAR EN UN PLANO LAS RESTRICCIONES


2. IDENTIFICAR LA REGION FACTIBLE


3. TRAZAR LA Dirección DE MAX ASCENSO


4. IDENTIFICAR EL PUNTO OPTIMO


NOTAS:


- En modelos con 2 variables:
- Una restricciónde exacta igualdad se representa por una recta
- Una restricción “mayor igual” ó “menor igual” divide el espacio de soluciones en dos semiplanos


- La Región factible es el conjunto de puntos que satisfacen todas las restricciones


- Los Vértices ocurren en la intersección de 2 ó mas restricciones


- Los Vértices siempre están localizados en la frontera de la región factible


- Toda funciónlineal f(x1,x2,. . .) se puede expresar como el producto escalar del vector de coeficientes c = (c1, c2, … ) y el vector de variables de
decisión x = (x1, x2, … ). Es decir f(x1,x2) = c1x1 + c2x2 = c×x


- La dirección de Max ascenso sobre la función objetivo f es la dirección del vector c


- El punto óptimo es aquel en la región factible asociado con el vector que tiene la mayor proyecciónsobre el vector c.


- De existir, una solución óptima de un modelo de PL siempre ocurre en un vértice de la región factible.

METODO GRAFICO





Ejemplo:


Máx. X1 + 2X2
sa.
4X1 + 2X2
16


3X1 + 3X2

18


X2

3

X1, X2

0




a) Determinar la solución óptima


b) Determinar las restricciones activas y las inactivas


c) En el punto óptimo, determinar los valores de holgura y excedente para...