miércoles, 4 de abril de 2012

M Grande


*Método de la M Grande*


Min z=4x1+4x2+x3

S.A:

2x1+x2+x3   ≤2
2x1+x2         ≤3
2x1+x2+3x3 ≥3

x1, x2, x3 ≥0

FORMA AMPLIADA:

F.O. para el Método de la M Grande:

Min z=4x1+4x2+x3+Ma1
S.A:
2x1+x2+  x3+x4                    =2
2x1+x2                +x5             =3
2x1+x2+3x3              -x6 + a1=3


SOLUCIÓN INICIAL:

x1=0
x2=0
x3=0
x4=2
x5=3
x6=0
a1=3
Z=3M

Comencemos a formar nuestra Tabla:


Como sabemos, en la tabla las variables básicas las podemos observar como vectores unitarios, y en este caso a1 no lo está, así que usaremos operaciones elementales de renglón para que la columna de a1 lo sea:


En este caso la variable de entrada es x3 y la variable artificial es la de salida:


Como Observamos la variable artificial a1  ha salido de la base y usando el criterio de la variable de entrada para el caso de Minimización (el más Positivo) ya no hay variable de entrada por lo tanto aquí concluye el Método.

SOLUCIÓN ÓPTIMA:

x1=0
x2=0
x3=1
x4=1
x5=3
x6=0
Z=1

URL de Nuestro Sitio


URL de Nuestro Sitio

Que tal, compañeros y Profesora, esta es la URL de Nuestro Sitio correspondiente a la Tarea de la Unidad II.



domingo, 18 de marzo de 2012


*Simplex*


Pasos del Método Simplex:

1.     Utilizando la forma estándar, determinar una solución básica factible inicial (origen)
2.    Seleccionar variable de entrada de las Variables no Básicas que al incrementar su valor mejore el valor de la f.o. Cuando no exista esta solución, la solución Actual es la óptima, sino, ir al siguiente paso.
3.    Seleccionar la variable de salida de las variables básicas actuales
4.    Determinar la nueva solución al hacer la variable de entrada básica y a la de salida, no básica
5. Ir al paso numero dos con el fin de actualizar la información.

A continuación se presenta un problema que se planteará y posteriormente se le dará solución con el Método Simplex.

Una empresa produce tres bienes cosméticos y tiene dos departamentos con la siguiente información:


Además se cuenta con una materia prima para su empaque de 2 unidades, 1.5 y 0.5 unidades para los tres bienes respectivamente (polvo, labiales y pintura). Teniendo una disponibilidad de 8 unidades.

1.- Plantear Modelo

xi= Número de Productos del Tipo i      i=1-3


(Polvo para Mejillas, Labiales, Pintura de Uñas)


F.O:

Max   z= 60x1+30x2+20x3

S.A:

8x1+6x2+1x3≤48
4x1+2x2+1.5x3≤20
2x1+1.5x2+0.5x3≤8

x1, x2, x3≥0
x1, x2, x3 ⋲ Z

2.- Forma Estándar


F.O:

Max   z= 60x1+30x2+20x3

S.A:

8x1+6x2+1x3+x4                         =48
4x1+2x2+1.5x3     +x5               =20
2x1+1.5x2+0.5x3                +x6=8

x1, x2, x3≥0
x1, x2, x3 ⋲ Z

Tenemos 6 variables y 3 restricciones. Por lo tanto tenemos 3 Variables Básicas y 3 Variables No Básicas. 

Solución Inicial (Origen):


x1=0
x2=0
x3=0
x4=48
x5=20
x6=8


Para la Tabla Optima, se tiene la forma:

zj-cj:   z-60x1-30x2-20x


3.- Tablas: 

Con estos elementos podemos  obtener formar nuestra Tabla Óptima:



Como en este caso estamos hablando de un problema de Maximización, la variable de entrada se eligió de acuerdo al criterio de la Variable, que es el valor mas negativo del renglón de zj-cj. Para el Criterio de la Variable de Salida (que es el mismo tanto para el caso de maximización como el de minimización es el mismo), se tiene que sacar una razón que se define como: el valor mínimo del cociente entre los valor de la columna de Sol. y su correspondiente valor de la ya columna pivote, siempre y cuando este ultimo sea mayor que cero.

La Variable de entrada es x1 y la variable de salida, que como se muestra en el cálculo de la razón, es x6. Por lo tanto la siguiente Iteración es:



Aquí la variable de entrada  es  x3 y la variable de Salida es x5. En tanto la siguiente Iteración es:



Como se observa ya no hay otro valor mas negativo en el renglón de zj-cj, por lo tanto ya no hay variable de salida, y por eso se determina que esta es la Solución Óptima.

x1=2
x2=0
x3=8
x4=24
x5=0
x6=0

z=280


4.- Explicación de Resultados: 

Con esta solución interpretamos que deben de producir 2 artículos del tipo 1 (Polvo para Mejillas) y 8 unidades del articulo tipo 3 (Pintura de Uñas), en este caso no conviene producir artículos del tipo 2 (Labiales). Con estas características, se maximizan las ganancias de esta empresa con un total de $280.00. También vemos que una variable de holgura resulto con un valor, para ser específicos, x4=24, en donde decimos que son 24 horas las que quedan disponibles para elaborar estos productos en el Departamento 1.



Referencias:

Simplex. (2009, Septiembre 18). Catálogo en Línea. [Archivo de Video]. Recuperado de: http://www.youtube.com/watch?v=0OnZiwOQLmE.


martes, 21 de febrero de 2012

Presentación en Prezi

Presentación en Prezi

Que tal Compañeros y Profesora:


En esta sección les dejo la URL de mi Presentación en Prezi de **Producción de Periódico**, incluye las correcciones que todos hicieron notar.


URL: http://prezi.com/n5mexatmk4f9/sistema-produccion-de-periodico/


domingo, 19 de febrero de 2012

George Bernard Dantzig

George Bernard Dantzig

(1914-2004)

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.

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.

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.



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.
Así mismo es de gran utilización su método denominado Descomposición de Dantzig- Wolfe (desarrollado conjuntamente con Philip Wolfe en 1959-1960) 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.


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


Por último, 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.



Referencias:


Richard Ernest Bellman

Richard Ernest Bellman


 (1920 – 1984)

Richard Ernest Bellman (1920–1984) fue un matemático aplicado, cuya mayor contribución fue la metodología denominada programación dinámica.

 Su padre fue John James Bellman y su madre fue Perla Saffian. Ambos lados de la familia vino de ascendencia judía, tanto con el padre de Juan Bellman haber emigrado de Rusia y el padre de Perla Saffian haber emigrado de Polonia. A pesar de la ascendencia judía, la familia que nació en Richard era agnóstica.

La Gran Depresión se inició en 1929, cuando Richard tenía nueve años, y por 1932 una cuarta parte de los trabajadores en los Estados Unidos estaban desempleados. La depresión de la década de 1930 vio los bajos salarios y había mucho antisemitismo. John Bellman fue arruinado por la depresión, pero a pesar de grandes dificultades, a ver Richard obtener una buena educación. Richard se reunió por primera vez las matemáticas a la edad de once años cuando estudió Schultze del álgebra elemental y avanzado. Fue encantado no sólo con este primer encuentro con las matemáticas, sino como un niño disfrutaba otras actividades tales como leer ávidamente, que ronda los museos de Nueva York, gasto y happy hours en la calle 42 la Biblioteca Pública.

Bellman estudió matemáticas en la Universidad de Brooklyn, donde obtuvo una diplomatura, y luego en la Universidad de Wisconsin, donde obtuvo su licenciatura. Posteriormente comenzó a trabajar en el Laboratorio Nacional Los Álamos en el campo de la física teórica. En 1946 obtuvo su doctorado en la Universidad de Princeton. También ejerció la docencia en la universidad del sur de California(EE. UU.), fue socio de la Academia Americana de las Artes y las Ciencias (1975) y de la Academia Nacional Americana de Ingeniería (1977). En 1979 el IEEE le otorgó la medalla de honor por su contribución a la teoría de los sistemas de control y de los procesos de decisión, en especial por su contribución con la programación dinámica y por la ecuación de Bellman.

Una Ecuación de Bellman. también conocida como una ecuación de Programación Dinámica , es una condición necesaria para Optimalidad asociado con el método de Optimización Matemática, conocida como Programación Dinámica. Casi cualquier Problema que puede  resolverse utilizando la teoría de control Optimo, también se puede resolver mediante el análisis de la ecuación de Bellman, se aplico por primera vez a la ingeniería de la Teoría de control y otros temas de Matemáticas Aplicadas y, posteriormente, se convirtió en una herramienta importante en la Teoría Económica.

Referente a programación dinámica  es un procedimiento matemático diseñado principalmente para mejorar la eficiencia de cálculo de problemas de programación matemática seleccionados, descomponiéndolos en subproblemas de menor tamaño y por lo consiguiente es más fácil de calcular.

La programación dinámica comúnmente resuelve el problema en etapas, donde cada etapa interviene exactamente a una  variable de optimización.

Los cálculos en las diferentes etapas se enlazan a través de cálculos recursivos de manera que se genere una solución óptima factible a todo el problema.


Referencias: