metodo simplex

Capitulo I Marco Teorico
1.1 Antecedentes

Historia del Metodo Simplex

El problema de la resolución de un sistema lineal de inecuaciones se remonta, almenos, 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áticodesarrollado durante la Segunda Guerra Mundial para planificar los gastos y losretornos, a finde reducir los costos al ejército y aumentar las pérdidas delenemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industriaslo usaron en su planificación diaria.Los fundadores de la técnica son George Dantzig, quien publicó el algoritmosimplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en elmismo año, y Leonid Kantoróvich, un matemático ruso, que utilizatécnicassimilares en la economía antes de Dantzig y ganó el premio Nobel en economía en1975. En 1979, otro matemático ruso, Leonid Khachiyan, demostró que elproblema de la programación lineal era resoluble en tiempo polinomial. Más tarde,en 1984, Narendra Karmarkar introduce un nuevo método del punto interior pararesolver problemas de programación lineal, lo que constituiría un enorme avanceen losprincipios teóricos y prácticos en el área.El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programaciónlineal. La potencia de computación necesaria para examinar todas laspermutaciones a fin de seleccionar la mejor asignación es inmensa; el número deposibles configuraciones excede al número de partículas en eluniverso. Sinembargo, toma sólo un momento encontrar la solución óptima mediante elplanteamiento del problema como una programación lineal y la aplicación delalgoritmo simplex.
George Dantzig
George Bernard Dantzig (8 de noviembre de 1914 – 13 de mayo de 2005) fue un profesor, físico y matemático estadounidense, reconocido por desarrollar el método simplex y es considerado como el "padre dela programación lineal". Recibió muchos honores, tales como la Medalla Nacional de Ciencia en 1975 y el premio de Teoría John von Neumann en 1974.
Fue miembro de la Academia Nacional de Ciencias, la Academia Nacional de Ingeniería y la Academia Americana de Artes y Ciencias.
Obtuvo su licenciatura en Matemáticas y Física en la Universidad de Maryland en 1936, su grado de máster en Matemáticas enla Universidad de Míchigan, y su doctorado en la Universidad de California, Berkeley en 1946. Recibió además un doctorado honorario de la Universidad de Maryland en 1976.
El padre de Dantzig, Tobías Dantzig, fue un matemático ruso que realizó estudios con Henri Poincaré en París. Tobías se casó con una estudiante de la universidad de la Sorbona, Anja Ourisson, y la pareja emigró a los EstadosUnidos.
1.2 Aplicación del método simplex en una empresa (ejemplo)
Un agricultor tiene una parcela de 640m² para dedicarla al cultivo de árboles frutales: naranjos, perales, manzanos y limoneros. Se pregunta de qué forma debería repartir la superficie de la parcela entre las variedades para conseguir el máximo beneficio sabiendo que:
cada naranjo necesita un mínimo de 16m², cada peral 4m², cadamanzano 8m² y cada limonero 12m².
dispone de 900 horas de trabajo al año, necesitando cada naranjo 30 horas al año, cada peral 5 horas, cada manzano 10 horas, y cada limonero 20 horas.
a causa de la sequía, el agricultor tiene restricciones para el riego: le han asignado 200m³ de agua anuales. Las necesidades anuales son de 2m³ por cada naranjo, 1m³ por cada peral, 1m³ por cada manzano, y 2m³ porcada limonero.
los beneficios unitarios son de 50, 25, 20, y 30 € por cada naranjo, peral, manzano y limonero respectivamente.

Se determinan las variables de decisión y se representan algebraicamente. En este caso:
X1: número de naranjos
X2: número de perales
X3: número de manzanos
X4: número de limoneros
Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de...