Metodo Simplex

Programación Lineal

Método Simplex

[Seleccionar fecha]

[Escribir el nombre de la compañía]

Pc

Ìndice

1. La programación lineal: el método simplex…………………………………………………Pág. 3

- Antecedentes históricos

- Explicar para que sirve.

- Explicar que significa el término “programación” y el término “lineal”.

- Propiedades del modelo de programación lineal.

- Aplicaciones típicas de la programación lineal.

2. Planteamiento general del problema de programación lineal……………………Pág. 9

- Explicar en qué consiste la función optimizar, las restricciones etc.

- Explicar la tabla del simplex inicial citando los distintos vectores que lo componen, variables de holgura y explicar su relación con la matriz tecnológica, etc..

3. Forma de resolver el problema de programación lineal…………………….………Pág. 14

- Explicar con todo detalle la forma como se obtienen las distintas tablas del simplex.

- Explicar la solución optima y porque.

- Analizar 3 diferencias básicas existentes entre el caso de un máximo y de un mínimo.

4. REPRESENTACIÓN GRAFICA

- Cuando se puede realizar esta representación grafica y porque.

- Representación de las distintas restricciones de la región factible, de la recta isobeneficio/isocoste, y de las distintas soluciones posibles.

4.1. Programación lineal en números enteros (o prog. Entera).

- Caso especial: explicar en qué consiste y como se resuelve. (método de ramificar y acotar/ B and B).

- Diferentes tipos de modelos de programación entera (puro, mixto, binario).

- Explicar en qué casos se utiliza, etc.

5. DESARROLLO

- Resolución del problema (contestar a todas las preguntas del enunciado con toda clase de detalles).

6. CONCLUSION

- conclusión: explicar cuál es la solución óptima del problema, en qué consiste y porque es la solución optima.

- En el caso de que la solución incluya algún número no entero, explicar con detalle la variante del método anterior denominado programación lineal cn números enteros.

7. Bibliografía.

1. La programación lineal: el Método Simplex.

1.1. Antecedentes Históricos.

En los siglos XVII y XVIII, grandes matemáticos como Newton, Leibnitz, Bernouilli y, sobre todo, Lagrange, que habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimo condicionados de determinadas funciones.

Posteriormente el matemático fránces Jean Baptiste-Joseph Fourier fue el primero en realizar los métodos de lo que actualmente llamamos programación lineal y los usos que actualmente tiene.

En el año de 1939 el matemático ruso Leonodas Vitalyevich Kantarovitch publicó la monografia Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace referencia a una extensa gama de problemas con teoría matemática precisa, llamada programación lineal.

En los años posteriores a la Segunda Guerra Mundial, en Estados Unidos se asumió que la eficaz coordinación de la energía y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal.

Paralelamente a los hechos descritos se desarrollaron técnicas de computación y los ordenadores, instrumentos que harían posible la resolución y simplificación de los problemas que se presentaban.

En 1947, G.B. Dantzig formuló, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal.

El profesor G. B. Dantzig no pudo conseguir el premio Nobel, pero recibió un cúmulo de distinciones, entre otras la mencionada anteriormente, el premio Von Neumann Theory en 1975, Premio en Matemáticas Aplicadas y Análisis Numérico de la National Academy of Sciences en 1977, Harvey Prize en Ciencia y Tecnología de Technion, Israel, en 1985. Fue miembro de la Academia de Ciencias y de la Academia Nacional de Ingeniería de EEUU. Las Sociedades de Programación Matemática y SIAM instituyeron hace años un premio que lleva su nombre, premio que es uno de los más prestigiosos de nuestra comunidad.

Dantzig se sorprendió de que el método simplex funcionara con tanta eficiencia. Citando de nuevo sus palabras: "La mayor parte de las ocasiones el método simplex resolvía problemas de m ecuaciones en 2m o en 3m pasos, algo realmente impresionante. En realidad nunca pensé que fuese a resultar tan eficiente. En ese entonces yo aún no había tenido experiencias con problemas en dimensiones mayores y no confiaba en mi intuición geométrica. Por ejemplo, mi intuición me decía que el procedimiento requeriría demasiados pasos de un vértice al siguiente. En la práctica son muy pocos pasos. Dicho con pocas palabras, la intuición en espacios de dimensiones mayores no es muy buena guía. Sólo ahora, 52 años después de haber propuesto el método simplex por primera vez, la gente está comenzando a tener una idea de por qué el método funciona tan bien como lo hace".

Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formaron el grupo que se denominó SCOOP (Scientific Computation of Optimum Programs).

El interés en la programación lineal se difundió rápidamente entre economistas, matemáticos, estadísticos e instituciones gubernamentales. En 1949 se llevó a cabo una conferencia acerca de la programación lineal bajo el patrocinio de la comisión Cowles para la investigación en economía.

Respecto al método del simplex señalaremos que su estudio comenzó en el año 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de varios modelos de ordenador de la firma IBM.

Desde el surgimiento del método simplex mucha gente ha contribuido al crecimiento de la programación lineal, ya sea desarrollando teorías matemáticas, diseñando códigos y métodos computacionales eficientes, experimentando nuevas aplicaciones, y también utilizando la programación lineal como una herramienta para resolver problemas más complejos como son programas discretos, programas no lineales, problemas combinatorios, problemas de programación estocástica y problemas de control óptimo.

Durante varias décadas el algoritmo simplex fue la principal herramienta analítica utilizada para resolver y analizar problemas de programación lineal. Con el desarrollo de la tecnología en el área de cómputo, la implementación del algoritmo simplex, presentó un auge mayor de lo esperado, dada su relativa rapidez para brindar una solución factible. Debido a esta aceptación fue diseñado en la mayoría de los paquetes computacionales existentes.

Con la introducción de un nuevo algoritmo llamado método de punto interior para la programación lineal, creado por Narendra K. Karmarkar en 1984, se abrió el horizonte de la programación lineal. Este nuevo algoritmo ofrece una alternativa completamente diferente que la del método simplex. La región factible se define por la intersección de todas las restricciones de un problema de programación lineal, el método simplex busca la solución óptima recorriendo la frontera de la región factible, mientras que el método de punto interior busca la solución óptima haciendo el recorrido en la parte interna.

Con base en la experiencia de la resolución de problemas de programación lineal mediante ambos métodos, se llegó a la conclusión de que para problemas de pequeña y mediana escala, el método simplex se adecua de una mejor manera, mientras que en problemas de grande escala están reservados para el método de punto interior.

1.2. ¿En qué consiste y para qué sirve la programación lineal?

El Método Simplex es un método algebraico iterativo para resolver cualquier modelo de programación lineal; es un procedimiento que examina paso a paso soluciones posibles y que se va aproximando a la solución óptima, de una forma sistemática.

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 estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales. El objetivo de la programación lineal es resolver un problema maximizando o minimizando una función lineal con restricciones lineales de desigualdad, igualdad o una combinación.

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

...