Programación de Metas

Cartel digital

Tarea IV Optimización Lineal by marila9322

Modelos Duales

EJEMPLO

Max z= x1+2x2+3x3

x1-x2+x3>=1

-x1+x2+x3=7

x1+x2<=2

x1>=0, x2>=0 y x3<=0

Forma canónica de minimización con equivalencias:

Min z =-x1-2x2-3x3

x1-x2+x3>=1

-x1+x2+x3>=7

x1-x2-x3>=-7

-x1-x2>=-2

x1>=0, x2>=0, x3<=0

Aplicar definición de dualidad:

Max g= y1+7y2-7y3-2y4

y1-y2+y3-y4<=-1

-y1+y2-y3-y4<=-2

y1+y2-y3>=-3

y1>=0, y2>=0, y3>=0, y4>=0

Llevarlo a la forma adecuada:

Min g=-y1-(7y2-7y3)+2y4

-y1-(-y2+y3)+y4>=1

y1-(y2-y3)+y4>=2

y1-(y1-y3)>=3

y1>=0, y2>=0, y3>=0, y4>=0

Min g=y1+y2'+2y3'

y1-y2'+y3>=1

-y1+y2'+y3'>=1

-y1+y2'+y3'>=2

y1+y2'<=3

y1<=0, y2' no restringida, y3'=y4>=0

Modelo Dual:

Min g=y1+7y2+2y3

y1-y2+y3>=1

-y1+y2+y3>=2

y1+y2<=3

y1<=0, y2 no restringida, y3>=0

Programas Computacionales del Método Simplex

Programa	URL	Características	Ventajas	Desventajas
1. Linear Programming Grapher	http://www.zweig media.com/ RealWorld/ LPGrapher/lpg.html	Se ingresa un modelo y muestra la gráfica del mismo	Permite graficar modelos de dos variables	Sólo resuelve modelos de dos variables
2. PHP Simplex	http://www.php simplex.com/simplex/ simplex.htm?l=es	Se ingresa si es un modelo de maximización o minimización, número de variables, restricciones y posteriormente se ingresan las desigualdades y los coeficientes de cada elemento.	Solo permite resolver modelos con el Método Simplex y dos fases	No permite resolver modelos por el método de la m grande
3. Javascript  SimpleX	http://destio.us.es/ alumnos/jsxui/	Se van ingresando las restricciones que se desee	Permite resolver modelos con el Método de las dos fases y M grande	Solo te permite ingresar hasta 10 variables diferentes
4. Linear Programming Calculator	http://calculator. tutorvista.com/ math/594/linear-programming -calculator.html	Es un programa vinculado con otro software llamado wolframalpha y gráfica la solución del modelo	Permite resolver modelos de 2 variables y muestra la gráfica del mismo	Solo permite resolver modelos con dos variables
5. Linear Programming Simplex Algorithm Calculation	http://easyca lculation.com/ operations- research/simplex -method- calculator.php	Se ingresa el modelo y se muestran las tablas de la solución	Permite agregar varias variables distintas	La manera en la que sale la solución, no es tan amigable, ya que los números se desfasan dependiendo de cuantos dígitos contenga.

Biografía Abraham Charnes

(1917-1992)

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

Dr. Charnes enseñó en el Instituto Carnegie de Tecnología, y de Purdue y Northwestern. Al Noroeste fue Walter P. Murphy Profesor de Matemática Aplicada. Profesor Charnes incorporó a la Universidad de Texas en Austin en 1968. Ocupó el Jesse H. Jones cátedra y fue profesor del Sistema Universitario. Más tarde fue nombrado John P. Harbin profesor en la Facultad de Administración de Empresas.

Profesor Charnes era una autoridad reconocida internacionalmente en el desarrollo de métodos matemáticos nuevos y avanzados que se utilizan para la resolución de problemas de gestión en el gobierno, la industria, la ingeniería y la medicina. Profesor Charnes publicó más de 200 artículos en revistas profesionales y coautor de siete libros. Una de sus obras más conocidas, Introducción a la Programación Lineal, fue traducida al chino, ruso y japonés. Otra publicación, Modelos de Gestión y Aplicaciones Industriales de la programación lineal, se tradujo al checoslovaco.

Abraham Charnes fue el séptimo Presidente de TIMS. Él tuvo una profunda influencia en el progreso científico en los ámbitos tan diversos como las matemáticas de la investigación de operaciones, la optimización, la estadística, la dinámica de fluidos, así como en las áreas funcionales de la empresa como la contabilidad, las finanzas, la planificación de los recursos humanos y marketing. Dr. Charnes fue galardonado con el Premio 1982 von Neumann Teoría de la ORSA y TIMS (junto con Cooper y Duffin). En septiembre de 1977, en un acto celebrado en honor a su 60 º cumpleaños, recibió la Medalla de la Marina de EE.UU. para la Función Pública, la más alta condecoración civil de la Marina. Sus contribuciones fueron reconocidas en muchas otras maneras. Fue becario de la AAAS, y la Sociedad de Econometría.

Después de servicio en la Marina durante la Segunda Guerra Mundial, el Dr. Charnes obtuvo un doctorado en matemáticas en la Universidad de Illinois. Luego se unió a la facultad de Carnegie Tech en 1948. Allí sus muchos logros incluyen un trabajo pionero en la optimización matemática. Su descubrimiento básico de la asociación de la independencia lineal con los puntos extremos de los poliedros convexos fue particularmente notable. Se trasladó a Purdue en 1955 y para la Universidad de Northwestern en 1957. Northwestern realizó una investigación exitosa en muchas disciplinas, como la programación estocástica, inversas generalizadas, la teoría de juegos y la programación no lineal.

Después de su traslado a la Universidad de Texas en Austin en 1968, él hizo el trabajo seminal junto con W. Cooper y E. Rodas que impulsó el nuevo campo de análisis envolvente de datos (DEA). Un verdadero pionero en el OR / MS, Dr. Charnes fue autor o co-autor de más de 400 artículos y siete libros.

En el momento de su muerte en 1992, fue profesor de la Universidad de Texas, Sistema y Jesse H. Jones Profesor de Matemáticas aplicadas y Gestión de la Ciencia en la Universidad de Texas, Austin

BA (matemáticas), 1938 y PhD (matemáticas), de 1948, Illinois.

Referencias

Imagen:

[Imgen] Recuperdado de: informs, (2014) TIMS Presidente, 1960

https://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Abraham-Charnes

Información:

informs, (2014) TIMS Presidente, 1960

https://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Abraham-Charnes

Palomo, Teresa, (2001, 6 de Febrero) In memoriam: Abraham Charnes

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

Biografía de William W. Cooper

(1914-2012)

Fue un investigador de operaciones, conocido como el "Padre de la Administración". Fue el presidente fundador del Instituto de Ciencias de la Administración, un miembro de la facultad de fundación de la Escuela de Graduados en Administración Industrial en el Instituto Carnegie de Tecnología, decano fundador de la Escuela de Asuntos Urbanos y Públicos en CMU, profesor de contabilidad en la Universidad de Harvard.

William Wager Cooper nació el 23 de julio de 1914, en Birmingham, Alabama. Se crió en Chicago, donde su padre (un ex contador) poseía varias estaciones de gasolina que se cerraron en la Gran Depresión.

 Cooper, en su segundo año de escuela secundaria, lo dejó para ayudar a mantener a su familia.  Él trabajó en una bolera, un campo de golf, y como profesional del boxeador . Como un boxeador, que ganó 58 combates, perdió tres, y sacó dos.  Si bien los desplazamientos al campo de golf, conoció a Eric Kohler , profesor de la Universidad de Northwestern , quien lo empujó a volver a la escuela y financió su entrada en la Universidad de Chicago .  En Chicago, comenzó a estudiar la química física , pero fue inspirado por su trabajo para Kohler en un caso legal para cambiar a la economía ,  se graduó con una licenciatura y Phi Beta Kappa honores en 1938. 

Después de la graduación, 1938-1940, trabajó como contable para la Autoridad del Valle de Tennessee , donde Kohler había convertido Controller. Allí trabajó en la auditoría de gestión y la asignación de los recursos matemáticos, y ayudó a Kohler testificar ante un comité de investigación del Congreso. En 1940, Cooper comenzó a hacer estudios de posgrado en la Universidad de Columbia ; Sin embargo, en 1942, junto a su curso completado, pero su tesis no escrita, dejó Columbia para servir a su país durante la Segunda Guerra Mundial . Trabajó en la División de las normas de estadística de la Oficina del Presupuesto EE.UU. coordinación de los programas de gobierno que recogen las estadísticas de contabilidad; su artículo 1945 que describía sus actividades durante la guerra fue la primera en recibir un premio del Instituto Americano de Contadores para el mejor artículo del año. 

Cooper comenzó su carrera académica con un breve paso por la enseñanza, la 1944-1946, de nuevo en la Universidad de Chicago.  En 1945, Cooper se casó con su esposa Ruth, una abogada y activista humano, y en 1946 se incorporó a la recién formada Graduados Escuela de Administración Industrial en el Instituto Carnegie de Tecnología (hoy Escuela de Tepper de Negocios en la Universidad de Carnegie Mellon ). Allí, él formó importantes colaboraciones de investigación con Abraham Charnes , George Leland Bach , y Herbert A. Simon , y con el tiempo se convirtió en profesor de la Universidad.  Si bien en la CMU, 1949-1950, también trabajó de nuevo como ayudante de Eric Kohler, quien tenía en ese momento convertirse Contraloría del Plan Marshall .  En 1969 él dejó GSIA pero se quedó en la CMU, convirtiéndose en decano de la nueva Escuela de Urbanismo y Asuntos Públicos (ahora el Heinz Colegio ) allí. Como decano, se dio cuenta de que pronto habría un papel mucho mayor en la gestión de las empresas estadounidenses para los afro-americanos, y ha trabajado para aumentar la representación de afro-americanos en la escuela. 

En 1975, la Universidad de Harvard contratado Cooper lejos de CMU para convertirse en el profesor Dickinson de Contabilidad, y en 1980 se trasladó de nuevo, a la Universidad de Texas en Austin , donde se convirtió en la crianza Parker Profesor de Administración, Finanzas y Contabilidad. Se retiró en 1993, pero continuó activo en la investigación hasta su muerte el 20 de junio de 2012.   

A principios de la década de 1950, la ciencia de gestión era una disciplina cada vez más que todavía no tenía una sociedad de origen o de la revista en la que sus obras podrían ser publicadas; la Sociedad de Investigación de Operaciones de América se había formado, pero preocupado de alguna manera diferentes problemas. Por invitación de Melvin E. Salveson, un grupo se reunió en la Universidad de California en Los Ángeles en el verano de 1953, y de nuevo en la Universidad de Columbia en diciembre de 1953, para formar lo que se convirtió en el Instituto de Ciencias de la Administración.  William Cooper esposa Ruth ayudó a redactar los estatutos del Instituto; a sí mismo Cooper fue elegido como su primer presidente, y Andrew Vázsonyi se convirtió en su primer presidente el pasado (sin previamente haber sido presidente). ORSA y TIMS más tarde se fusionaron en 1995 para formar el Instituto de Investigación de Operaciones y las Ciencias de la Administración. 

En 1982, con Abraham Charnes y Richard Duffin , Cooper ganó el Premio Teoría John von Neumann del Instituto de Investigación de Operaciones y las Ciencias de la Administración "por sus contribuciones fundamentales a la optimización de los métodos, conceptos y modelos para problemas de decisiones, la planificación y el diseño" , que abarca el trabajo en "una multitud de campos como: programación lineal y las desigualdades, las metas y la programación oportunidad con restricciones, programación geométrica, programación dimensional y convexa infinita, modelado y análisis de redes, programación fraccional y el intervalo, la predicción y reglas de decisión estocásticos, y la teoría de juegos". Él también ganó el 1986 Premio de EE.UU. Contraloría General por su significativa contribución a la Oficina de Contabilidad General de EE.UU. y el Premio Mehr del Riesgo de América y la Asociación de Seguros por su trabajo en la predicción de la insolvencia.

Referencias:

Información:

Wikipedia (2014, 5 de Abril) Wikipedia la enciclopedia libre

http://en.wikipedia.org/wiki/William_W._Cooper

Imagen:

Know UT (2012, Junio 20) Cooper was Giant of Business Education

http://www.utexas.edu/know/2012/06/20/cooper-william/

Modelos duales

Ejemplo

Min z= 2x1-3x2+4x3

-2x1+x2+3x3>=1

x1-2x2=7

-2x1+3x2-5x3<=-9

x1<=0, x2>=0, x3 no restringida

Modelo en su forma dual, haciendo uso del resumen:

Max g= y1+7y2-9y3

-2y1+y2-2y3>=2

y1-2y2+3y3<=-3

3y1-5y3=4

y1>=0, y2 no restringida, y3<=0

Método Simplex Revisado

EJEMPLO

Max z= 4x1+x2
2x1+3x2≤4
x1+x2≤1
4x1+x2≤2
x1,x2≥0

Variable de entrada

Variable de salida

Actualizar

En este caso ya no se tiene variable de entrada, eso quiere decir que se ha llegado a la sol. óptima:

z=2

x1= 1/2

x2=0

x3= 3

x4= 1/2

x5= 0

(La solución es múltiple, y los valores de la solución de arriba cumplen para que z sea igual a 2).

Método de las dos fases

Ejemplo

Min z= 2x1+3x2
1/2 x1+ 1/4 x2≤ 4x1+3x2≥ 36x1+x2=10x1,x2≥0

Forma Ampliada                   Fase 1

Min w= a1+a2 1/2 x1 + 1/4 x2+x3= 4 x1+3x2-x4+a1=36 x1+x2+a2=10 x1,x2,x3,x4≥0 a1,a2≥0

Forma Ampliada                   Fase 2

Min z= 2x1+3x2 1/2 x1 + 1/4 x2+x3= 4 x1+3x2-x4+a1=36 x1+x2+a2=10 x1,x2,x3,x4≥0 a1,a2≥0

Fase I

	X1	X2	X3	X4	a1	a2	Sol.
wj-cj	0	0	0	0	-1	-1	0
zj-cj	-2	-3	0	0	0	0	0
X3	½	¼	1	0	0	0	4
a1	1	3	0	-1	1	0	36
a2	1	1	0	0	0	1	10

	X1	X2	X3	X4	a1	a2	Sol.
wj-cj	2	4	0	-1	0	0	46
zj-cj	-2	-3	0	0	0	0	0
X3	½	¼	1	0	0	0	4
a1	1	3	0	-1	1	0	36
a2	1	1	0	0	0	1	10

	X1	X2	X3	X4	a1	a2	Sol.
wj-cj	-2	0	0	-1	0	-4	6
zj-cj	1	0	0	0	0	3	30
X3	¼	0	1	0	0	-1/4	3/2
a1	-2	0	0	-1	1	-3	6
X2	1	1	0	0	0	1	10

Solución:

x1=0

x2=10

x3=3/2

x4=0

a1=6

a2=0

z=6

Existe una variable artificial estrictamente mayor que cero, por lo tanto el problema tiene una solución no factible.