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

...