Programación Entera (Métodos de Solución)

 Presentación en PREZI

Problema de Reemplazo (esquema, guión de video)

https://docs.google.com/document/d/1zzV6xCXKm2flq_l5blLBf00HaC5iunyv04yyOj9P9eI/edit?usp=sharing

Biografía de Delbert Ray Fulkerson

Delbert Ray Fulkerson

Nacimiento: 14 de agosto de 1924, Tamms, Illinois, EE.UU

Murió: 10 de enero de 1976, Ithaca, Nueva York, EE.UU

Pionero en los campos de los flujos de la red, a gran escala de programación lineal y combinatoria y optimización.

Educación: B.A. en Matemáticas, en el sur Illinois University, 1947; M.S. en Matemáticas,Universidad de Wisconsin, 1948; Ph.D. en Matemáticas de la Universidad de Wisconsin, 1951.

Posiciones principales: Rand Corporation, Departamento de Matemáticas, 1951-1971; Maxwell M.Profesor de Ingeniería y el profesor de Investigación Operativa y Matemática Aplicada, Universidad de Cornell, 1971-1976.Trabajo seminal de Delbert Ray Fulkerson en los flujos de la red, a gran escala de programación lineal, y optimización combinatoria.

Ray, como le llamaban sus amigos, fue un matemático en el corazón. Le encantaba la elegancia y la gracia de las matemáticas, y amaba las matemáticas bueno para su propio bien. Gran parte de los más influyentes, comenzó a trabajar con una aplicación, un rompecabezas, o un obstáculo computacional específicos. La búsqueda de laestructuras matemáticas subyacentes llevó Ray y sus colaboradores profundamente a ampliasinnovaciones metodológicas, que incluye los planos de corte, la generación de columnas, y elfundamento de la teoría de flujo de red. 

Premios: Premio Lester R. Ford, la Asociación Matemática de América, por su trabajo''Las redes de flujo y''Combinatoria Investigación de Operaciones, 1967; del Sur de IllinoisPremio Universidad de notables logros profesionales, 1972; profesor visitante:U.C. Berkeley, la Universidad de Stanford, la Universidad de Waterloo.

 Su padre, Elbert Fulkerson, fue un educador muy conocido en la ciudad, y más tarde se convirtió en el director de la escuela. Su madre, Emma, era una mujer profundamente religiosa que en algún momento también había sido un profesor. Ray tuvo de hermanos y tres hermanas todos se convirtieron en educadores. Por otra parte, los tres hermanos obtuvierón el doctorado.

En 1942, Ray entró en la Southern Illinois University, habiéndose graduado con honores de clase de la escuela a la edad de 16 años. Dejó SIU en 1944 con el fin de servir en los EE.UU.

Cuerpo Aéreo del Ejército Ray volvió a SIU en 1946, y se graduó en 1947, una vez más en la parte superior de su clase. A continuación, pasó a la Universidad de Wisconsin para realizar un doctorado en las matemáticas. Él escribió una tesis titulada''formas QuasiHermite de filas finitas  de  matrices'', bajo la supervisión de Colton MacDuffee Cyrus.

Tras completar su doctorado en 1951, Ray se unió al Departamento de Matemáticas de la Rand Corporación, por invitación del jefe del departamento, John Williams. La Rand Corporation había comenzado tres años antes como una consecuencia de un proyecto especial entre la Fuerza Aérea de los EE.UU. y la Douglas Aircraft Company. Muchos de los colegas de Ray en el Departamento de Matemáticas también se convirtierón  en personajes célebres en el desarrollo de los fundamentos matemáticos de la investigación de operaciones, incluyendo Richard Bellman, George Dantzig, Merrill Flood, Les Ford, Johnson y Lloyd Selmer Shapley. Ray también ha trabajado extensivamente con Herb Ryser, uno de los consultores regulares de departamento, y un amigo y un compañero estudiante de posgrado con Ray en Wisconsin. Además, colaboró con varios jóvenes investigadores que trabajaron en o visitado, Rand, sobre todo Jon Folkman y Edmonds Jack. Ray se sintió muy orgulloso de los logros de las matemáticas. En 1971, se unió al Departamento o la Universidad de Cornell, y permaneció allí hasta su muerte en 1976.Antes de llegar a Rand, Ray no había estudiado ni programación lineal o la teoría de grafos. Élse introdujo en estos dos ámbitos a través de sus primeras asignaciones de Rand, que se traducen a T.S. Motzkin tesis sobre desigualdades lineales, y para escribir notas sobre la base de clases de teoría gráfica dada por A.W. Tucker. Poco después de llegar a Rand, Ray hizo importantes contribuciones a estos dos campos de estudio.Una de las primeras publicaciones de Ray y su contribución más duradera surgió de un rompecabezas, un desafío computacional sobre el problema del viajante (TSP): encontrar un menor viaje  a través de las capitales de los (entonces) 48 estados y en Washington, DC. Sucolaboradores en este esfuerzo fueron George Dantzig y Johnson Selmer. Ray había trabajado previamente con los dos, pero en circunstancias muy diferentes. Primera publicación de Ray fue conjuntamente con Dantzig (1954), que se refería al uso de programación lineal para resolver un problema petrolero-programación.Ray había aprendido la meteorología de Selmer Johnson durante la guerra de EE.UU. en una base del Cuerpo Aéreo del Ejército en Illinois.Dantzig, Fulkerson y Johnson (1954) fueron capaces de encontrar un recorrido y establecer su óptimo uso de Simple método de Dantzig y planos de corte, una nueva técnica que han desarrollado específicamente para con este fin. Su enfoque global, que engendró el área de la combinatoria poliédrica, fue muy innovador: considerar la envolvente convexa de los puntos enteros en la región factible de lo que ahora llamamos una relajación de programación lineal del TSP. 

Ray y  Fulkerson son probablemente mejor conocidos por su trabajo en los flujos de la red.

Su colaboración con Lester R. Ford, Jr. puso los cimientos de toda la materia. Todo comenzó con una específica aplicación a las operaciones militares trajeron a su atención durante el almuerzo en Rand por FS Ross.Ross y Harris TE estaban trabajando en un proyecto para evaluar la capacidad de la Europa del Este la red ferroviaria para apoyar una guerra convencional. Ford y Fulkerson (1956, 1962) colaboraron en este problema, llevando su primer trabajo (1956) sobre los flujos de la red, en la que demostró el ahora flujo famoso teorema de flujo max min.

 El papel de Ray(1966) en las redes de flujo y la investigación de operaciones combinatorias fue reconocido por su exposición excelencia con el Premio Lester R. Ford de la Asociación Matemática de América. El premio lleva el nombre de Lester R. Ford, Sr., un ex presidente de la AMA, y el padre de Ray colaborador frecuente.

Su muerte en 1976, fue llorada por todos los que le conocían, y se destacó por las declaraciones de monumento envarias revistas, un volumen especial de la investigación de operaciones matemáticas, y el establecimiento de la D.R. Fulkerson Premio en Matemáticas Discretas por la Sociedad Matemática Americana y La Sociedad Matemática de programación.

Referencias:

http://es.wikipedia.org/wiki/D._R._Fulkerson
http://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2005.00506.x/pdf
http://www.deepdyve.com/lp/informs/delbert-ray-fulkerson-august-14-1924-january-10-1976-ivA88ywFg9

Biografía de Lester Randolph Ford Jr.

Lester Randolph Ford Jr.

Lester Randolph Ford Jr. es un matemático americano, uno de los pioneros en el campo de la programación de flujos en grafos. Nació el 23 de septiembre de 1927 y es el hijo de L.R. Ford Sr. (quién también es un matemático distinguido) ,su madre  Margarita E. John y esposa Janet Lux.

         

L. R. Ford Sr es elogiado por su ejemplar trabajo en matemáticas al inventar una interpretación geométrica absolutamente maravillosa de la serie de Farey. También le acredita su trabajo 'Pointwise Discontinuous Functions' que era la base de su trabajo para un grado de M.S. del departamento de matemáticas en la universidad de Missouri-Colombia en 1912. Tal fue su contribución a las matemáticas, que en 1964 se estableció el Lester R. Ford Award para reconocer la contribución a las matemáticas de excelentes autores matemáticos publicados en The American Mathematical Monthly o Mathematics Magazine. Fue redactor de American Mathematical Monthly, de 1942-1946, y el presidente de Mathematical Association of America, 1947-1948. Ford Sr. y Ford Jr. son co-autores de Automorphic Functions cuál fue publicado cerca por McGraw-Hill en 1963.

Mientras trabajó en RAND CORPORATION, Ford Jr publicó numerosos artículos que no solo establecieron la base de los flujos de red sino también la futura investigación en este campo. En 1962 Priceton University Press publicó su libro Flow in Networks con D. R. Fulkerson como co-autor. Este libro contiene todo su trabajo sobre redes.

Junto con Richard E. Bellman (26 de agosto 1920 – 19 marzo de 1984) desarrollaron el algoritmo de 'corrección de etiquetas' que calcula el camino más corto en un digrafo ponderado (donde incluso y a diferencia de Dijkstra, los pesos de los arcos pueden ser negativos).

El papel de Ford con el Dr Fulkerson en el problema de flujo máximo y el algoritmo de Ford-Fulkerson para resolverlo, publicado como un informe técnico en 1954 y en un diario en 1956, estableció el máximo de flujo min de corte teorema .

La mayoría del trabajo de Ford lo hizo en la colaboración con Fulkerson, al parecer los dos hacían una buena asociación. Sin embargo, en 1956 presentó varios artículos firmados por él sólo. Ha sido el autor de diversos algoritmos que se han refinado con los años y que todavía se utilizan para solucionar la mayoría de problemas de grafos.

Referencias: 

http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford
http://www.tangrammit.com/barbara.html

Tarea 1 (Nube de palabras y Planteamiento de problema de Asignación)

Tarea 1 (Nube de palabras y Planteamiento de problema de Asignación)

Consultar PDF aquí.
https://docs.google.com/file/d/0B4nbJuWXL68mX091c2IxS1VlUHc/edit?usp=sharing

Ejemplo de Problema de Transbordo (Participación 8b)

Sun Oil produce petróleo en dos pozos. El pozo 1 produce 150000 barriles por día y el pozo 2 produce 200000 barriles por día. Es posible enviar petróleo directamente de los pozos a los clientes de Sunco en Los Ángeles y Nueva York. Alternativamente, Sunco podría transportar petróleo a los puertos de Mobile y Galveston y luego enviarlo en su buque que cisterna a Nueva York y Los Ángeles. Esta última ciudad requiere 160000 barriles por día y Nueva Cork requiere140000 barriles por día. El costo de enviar 1000 barriles entre dos puntos se muestra a continuación. 

Resolver el modelo como un problema de transporte: (Resolver ejercicio)

Biografia de William R. Vogel (Método de Vogel)

William R. Vogel

William R. Vogel  nació en Sac City, Iowa, Estados Unidos el 15 de noviembre de 1941.  Creció en una granja al oeste de Wall Lake, Iowa.           

Se graduó en 1959 como mejor alumno. Asistió a la AIB durante un año, y posteriormente sirvió en la Reserva del Ejército durante seis años. Trabajó en un banco en Storm Lake por un año, en la Northwestern Bell / Qwest por 25 años, y en Principal Financial durante 12 años como analista de telecomunicaciones.              

Propone el Método de Vogel, que es un método heurístico  que sirve para obtener una mejor solución óptima para el problema de transporte.            

Se jubiló a los 62 años.  Murió el 26 de agosto del 2010, en el Mercy Hospice, Johnston, Iowa después de una larga lucha contra el cáncer.

Biografia de Abraham Charnes (Metodo del Transporte)

Abraham Charnes

Abraham Charnes, profesor emérito de ciencias de la gestión y los sistemas de información, murió el 19 de diciembre de 1992. Tenía 75 años.

Profesor Charnes nació el 4 de septiembre de 1917, en Hopewell, Virginia. Obtuvo licenciatura, maestría y doctorado de la Universidad de Illinois en 1938, 1939 y 1947, respectivamente.

El Dr. Charnes enseñó en el Instituto Carnegie de Tecnología, y las Universidades de Purdue y del noroeste. En el noroeste fue Walter P. Murphy Catedrático de Matemática Aplicada. Profesor Charnes incorporó a la Universidad de Texas en Austin en 1968. Ocupó el Jesse H. Jones cátedra y era un profesor del Sistema Universitario. Él más tarde fue nombrado profesor John P. Harbin en la Facultad de Administración de Empresas.

Profesor Charnes era una autoridad reconocida internacionalmente en el desarrollo de métodos matemáticos nuevas y avanzadas utilizadas para la solución de problema de gestión en el gobierno, la industria, la ingeniería y la medicina.Profesor Charnes publicado más de 200 artículos en revistas especializadas y coautor de siete libros. Una de sus obras más conocidas, Introducción a la Programación Lineal , fue traducido al chino, ruso y japonés. Otra publicación, Modelos de Gestión y Aplicaciones Industriales de la programación lineal , fue traducido al checo.

En 1975 el profesor Charnes era un finalista para el Premio Nobel de Economía. Él era el destinatario de otras distinciones, entre ellos el John von Neumann, la teoría del Premio del Instituto de Ciencias de la Administración y la Sociedad de Investigación de Operaciones de América, y el Premio en Memoria de Harold Lardner, de la Sociedad Canadiense de Investigación de Operaciones. 

También recibió la medalla al Servicio Federal Distinguido de la Marina de los EE.UU. por sus contribuciones como físico investigador y analista de operaciones durante la Segunda Guerra Mundial.

Referencias.
http://www.utexas.edu/faculty/council/2000-2001/memorials/AMR/Charnes/charnes.html

Biografia de Frank Lauren Hitchcock (Método del transporte)

 Frank Lauren Hitchcock

Frank Lauren Hitchcock (1875-1957) fué un americano matemático y físico destacado para el análisis vectorial. Él formuló el problema de transporte en 1941. Él era también un experto en química matemática y cuaterniones.

La primera vez que asistio a la Academia Philips Andover recibió  su licenciatura de la Universidad de Harvard en 1896. Antes de su doctorado fue profesor en París y en el Kenyon College en Gambier, Ohio. En 1910 completó su doctorado en Harvard con una tesis titulada Funciones vectoriales de un punto. 


En 1904-1906 fue profesor de química en la Universidad Estatal de Dakota del Norte y luego se trasladó a convertirse en un profesor de matemáticas en el Massachusetts Institute of Technology .

Su madre fue Ida Susan Porter (nacido el 1 de enero de 1848, Middlebury , Vermont ) y su padre era Eliseo Pike Hitchcock. Sus padres se casaron el 27 de junio de 1866. Tenía dos hermanas, María E. Hitchcock y Viola M. Hitchcock. Tenía dos hermanos George P. Hitchcock y Ernest Van Ness Hitchcock. Nació en Nueva York pero creció en Pittsford , Vermont . Era descendiente de Nueva Inglaterra antepasados.

Algunos de sus libros son.

Frank Lauren Hitchcock y Clark S. Robinson, Ecuaciones Diferenciales en Química Aplicada, 1923.Frank Lauren Hitchcock, los ejes de un Vector cuadrática, 1921.
Frank Lauren Hitchcock, En Polyadics dobles, con la aplicación de la ecuación matricial lineal de 1923.
Frank Lauren Hitchcock, una clasificación de los vectores cuadráticas, 1917.
Frank Lauren Hitchcock, Identidades CUMPLIR Funciones Point algebraicas de n-Space, 1923.
Frank Lauren Hitchcock, un método para la solución numérica de ecuaciones integrales, 1923.
Frank Lauren Hitchcock, los puntos coincidentes de dos transformaciones algebraicas, 1924.
Frank Lauren Hitchcock, Funciones vectoriales de un Punto, 1910.
Frank Lauren Hitchcock, una relación idéntica Conexión Siete Vectores, 1920.
Frank Lauren Hitchcock, una solución de la ecuación matricial lineal por multiplicación doble, 1922.
Frank Lauren Hitchcock y Norbert Wiener, un nuevo método de Vector en las ecuaciones integrales, 1921.

Biografia de George Dantzig

GEORGE DANTZIG

George Bernard Dantzig nació el 8 de Noviembre de 1914 en Portland, Oregon, EEUU. Su padre era profesor de Matemáticas, se retiró dejando su puesto de Jefe del Departamento de Matemáticas en la Universidad de Maryland poco después de la Segunda Guerra Mundial. Su madre era una lingüista especializada en idiomas eslavos.

Dantzig estudió su carrera en la Universidad de Maryland, donde se graduó en 1936. Le disgustaba el hecho de no haber visto ni una sola aplicación en alguno de los cursos de Matemáticas que había tomado allí. Al año siguiente hizo estudios de postgrado en la escuela de Matemáticas de la Universidad de Michigan. Sin embargo, exceptuando la Estadística, le pareció que los cursos eran demasiado abstractos, él sólo deseaba abandonar sus estudios de postgrado y conseguir un trabajo.

En 1937 Dantzig dejó Michigan para trabajar como empleado en Estadística en el Bureau of Labor Statistics. Dos años después se inscribía en Berkeley para estudiar un Doctorado en Estadística.

La historia de la tesis doctoral de Dantzig es ahora parte del anecdotario de las Matemáticas. Durante su primer año en Berkeley, se inscribió en un curso de Estadística que impartía el famoso profesor Jerzy Neymann. Este profesor tenía la costumbre de escribir en la pizarra un par de ejercicios al comenzar sus clases para que, como tarea para el hogar, fueran resueltos por sus alumnos y entregados en la clase siguiente. 

En una ocasión llegó tarde a una de las clases de Neymann y se encontró con dos problemas escritos en la pizarra. Supuso que eran problemas de tarea y, consecuentemente, los copió y los resolvió, aun cuando le parecieron "un poco más difíciles que los problemas ordinarios". Unos días después se los entregó a Neymann, disculpándose por haber tardado tanto. Aproximadamente seis semanas después, un domingo a las 8:00 de la mañana, Neymann llegó aporreando la puerta de Dantzig, explicándole que había escrito una introducción a uno de los artículos de Dantzig y que quería que la leyera a fin de poder enviar el artículo para su publicación. Los dos "problemas de tarea" que Dantzig había resuelto eran, en realidad, dos famosos problemas no resueltos de la Estadística. Las soluciones de estos problemas se convirtieron en su tesis doctoral, a sugerencia de Neymann.

No obstante, Dantzig no terminó su doctorado hasta 1946. Poco después del comienzo de la Segunda Guerra Mundial se unió a la Fuerza Aérea de Estados Unidos y trabajó con el Combat Analysis Branch of Statistical Control. Después de recibir su Doctorado, regresó a la Fuerza Aérea como el asesor de Matemáticas del U. S. Air Force Controller. Fue en ese trabajo donde encontró los problemas que le llevaron a hacer sus grandes descubrimientos. La Fuerza Aérea necesitaba una forma más rápida de calcular el tiempo de duración de las etapas de un programa de despliegue, entrenamiento y suministro logístico.

El profesor Dantzig centró básicamente sus desarrollos científicos, cronológicamente, en la RAND Corporation y las universidades de Berkeley y Stanford en California, con asignaciones temporales en otros centros como el IIASA en Viena. (Es gozosa la anécdota que él cuenta como la razón principal para moverse de Berkeley a Stanford, la "culpa" es de un aparcamiento de coches para los profesores en la misma puerta de su nuevo Dpto. con tal mala fortuna que este aparcamiento ya había desaparecido cuando él se incorporó a Stanford).

El trabajo de Dantzig generalizó lo hecho por el economista, ganador del Premio Nobel, Wassily Leontief. Dantzig pronto se dio cuenta de que los problemas de planeación con los que se encontraba eran demasiado complejos para las computadoras más veloces de 1947 (y aun para las de la actualidad).

Habiéndose ya establecido el problema general de Programación Lineal, fue necesario hallar soluciones en un tiempo razonable. Aquí rindió frutos la intuición geométrica de Dantzig: "Comencé observando que la región factible es un cuerpo convexo, es decir, un conjunto poliédrico. Por tanto, el proceso se podría mejorar si se hacían movimientos a lo largo de los bordes desde un punto extremo al siguiente. Sin embargo, este procedimiento parecía ser demasiado ineficiente. En tres dimensiones, la región se podía visualizar como un diamante con caras, aristas y vértices. En los casos de muchos bordes, el proceso llevaría a todo un recorrido a lo largo de ellos antes de que se pudiese alcanzar el punto de esquina óptimo del diamante".

Esta intuición llevó a la primera formulación del método simplex en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición.

El 3 de octubre de l947 Dantzig visitó el Institute for Advanced Study donde conoció a John von Neumann, quien por entonces era considerado por muchos como el mejor Matemático del mundo. Von Neumann le habló a Dantzig sobre el trabajo conjunto que estaba realizando con Oscar Morgenstern acerca de la teoría de juegos. Fue entonces cuando Dantzig supo por primera vez del importante teorema de la dualidad.

Otro de sus grandes logros es la teoría de la dualidad, ideado conjuntamente con Fulkerson y Johnson en 1954 para resolver el paradigmático problema del Agente Viajero (resolviendo entonces problemas con 49 ciudades cuando, hoy día, mediante modernas implementaciones del método, se resuelven problemas con varios miles de ciudades y hasta un millón de nodos) es el precursor de los hoy utilísimos métodos de Branch-and Cut (Bifurcación y corte) tan utilizados en programación entera para resolver problemas de grandes dimensiones.

Muchos de los problemas a resolver mediante Programación Matemática se enmarcan en planificación dinámica a través de un horizonte temporal. Muchos de los parámetros se refieren al futuro y no se pueden determinar con exactitud. Surge entonces la programación estocástica o programación bajo incertidumbre. Esta rama, con un gran desarrollo hoy día, y un tremendo potencial para el futuro, debe su desarrollo a dos trabajos seminales que de forma independiente son debidos a los profesores E.Martin L Beale y George B. Dantzig en 1955.

Así mismo es de gran utilización su método denominado Descomposición de Dantzig- Wolfe (desarrollado conjuntamente con Philip Wolfe en 1959-1960) (cuyo dual es el método de Descomposición de Benders, tan utilizado hoy día en Programación Estocástica), para resolver problemas de programación lineal estructurados.

El libro "Linear Programming and Extensions" (1963), ha sido su gran libro de referencia durante los 42 años que median desde su publicación. Ha cerrado el ciclo de su extensa bibliografía con el libro en dos tomos "Linear Programming" (1997 y 2003), escrito conjuntamente con N. Thapa.

En 1976 el presidente Gerald Ford otorgó a Dantzig la Medalla Nacional de Ciencias, que es la presea más alta de los Estados Unidos en Ciencia. En la ceremonia en la Casa Blanca se citó a George Bernard Dantzig "por haber inventado la Programación Lineal, por haber descubierto métodos que condujeron a aplicaciones científicas y técnicas en gran escala a problemas importantes en logística, elaboración de programas, optimización de redes y al uso de las computadoras para hacer un empleo eficiente de la teoría matemática".

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".

Una precisión acerca de la terminología: un simplex es un tipo especial de conjunto convexo poliédrico. Más concretamente, sean P1, P2, . . . , Pn+1 n+1 puntos (o vectores) en R. Se dice que los vectores tienen independencia afín si los n vectores P1 P2, P1 P3, . . . , P1 Pn, P1 P son linealmente independientes. Si los puntos tienen independencia afín, entonces el conjunto convexo más pequeño que contiene los n+1 puntos en se llama n-simplex. En R, tres puntos tienen independencia afín si no son colineales. El conjunto convexo más pequeño que contiene tres puntos no colineales es un triángulo con estos puntos como vértices. Por tanto, un 2-simplex es un triángulo. En R, cuatro puntos tienen independencia afín si no son coplanares. El conjunto convexo más pequeño que contiene cuatro de tales puntos es un tetraedro. Este es el 3-simplex. Los triángulos y los tetraedros son conjuntos poliédricos convexos, no obstante que los conjuntos convexos poliédricos no son necesariamente simplex. El método simplex fue llamado así por George Dantzig, aunque no está claro por qué eligió ese nombre. Habría sido más adecuado llamarlo "método del conjunto convexo poliédrico".

Es importante reseñar la aplicación de programación matemática que el profesor Dantzig fue desarrollando a lo largo de los años para diversos sectores industriales y de la Administración, destacando a título de ejemplo el proyecto PILOT, para una mejor planificación del sector energético y, por tanto, un mayor ahorro energético.

El 13 de Mayo de 2004, George Bernard Dantzig, murió a la edad de 90 años en su casa de Stanford debido a complicaciones con la diabetes y problemas cardiovasculares.