invopelucvjosmell: noviembre 2011

miércoles, 30 de noviembre de 2011

PROGRAMA INVOP CLASE 14

max 15x11+12x12+9x13+2x14+3x21+7x22+6x23+6x24+16x31+7x32+6x33+7x34-4s1-4s2-4s3
ST
x11+x12+x13+x14+s1=1000
x21+x22+x23+x24+s2=1000
x31+x32+x33+x34+s3=1500
x11+x21+x31=500
x12+x22+x32=700
x13+x23+x33=600
x14+x24+x34=800

LINDO:

LP OPTIMUM FOUND AT STEP     14
        OBJECTIVE FUNCTION VALUE
        1)      22900.00
VARIABLE        VALUE          REDUCED COST
       X11         0.000000          4.000000
       X12       700.000000          0.000000
       X13       300.000000          0.000000
       X14         0.000000          8.000000
       X21         0.000000         13.000000
       X22         0.000000          2.000000
       X23       300.000000          0.000000
       X24         0.000000          1.000000
       X31       500.000000          0.000000
       X32         0.000000          2.000000
       X33         0.000000          0.000000
       X34       800.000000          0.000000
        S1         0.000000          3.000000
        S2       700.000000          0.000000
        S3       200.000000          0.000000

       ROW   SLACK OR SURPLUS     DUAL PRICES
        2)         0.000000         -1.000000
        3)         0.000000         -4.000000
        4)         0.000000         -4.000000
        5)         0.000000         20.000000
        6)         0.000000         13.000000
        7)         0.000000         10.000000
        8)         0.000000         11.000000
NO. ITERATIONS=      14

RANGES IN WHICH THE BASIS IS UNCHANGED:
                           OBJ COEFFICIENT RANGES
VARIABLE         CURRENT        ALLOWABLE        ALLOWABLE
                   COEF          INCREASE         DECREASE
      X11       15.000000         4.000000         INFINITY
      X12       12.000000         INFINITY         2.000000
      X13        9.000000         2.000000         3.000000
      X14        2.000000         8.000000         INFINITY
      X21        3.000000        13.000000         INFINITY
      X22        7.000000         2.000000         INFINITY
      X23        6.000000         3.000000         0.000000
      X24        6.000000         1.000000         INFINITY
      X31       16.000000         INFINITY         4.000000
      X32        7.000000         2.000000         INFINITY
      X33        6.000000         0.000000         INFINITY
      X34        7.000000         INFINITY         1.000000
       S1       -4.000000         3.000000         INFINITY
       S2       -4.000000         0.000000         1.000000
       S3       -4.000000         1.000000         0.000000
                           RIGHTHAND SIDE RANGES
      ROW         CURRENT        ALLOWABLE        ALLOWABLE
                    RHS          INCREASE         DECREASE
        2     1000.000000       300.000000       300.000000
        3     1000.000000         INFINITY       700.000000
        4     1500.000000         INFINITY       200.000000
        5      500.000000       200.000000       500.000000
        6      700.000000       300.000000       300.000000
        7      600.000000       700.000000       300.000000
        8      800.000000       200.000000       800.000000

min 12x11+15x12+16x13+14x14+15x21+2x22+18x23+16x24+10x31+15x32+8x33+6x34+2000dt1+25000dt2+20000dt3+15000dt4
ST
x11+x12+x13+x14=150
x21+x22+x23+x24=100
x31+x32+x33+x34=50
x11+x21+x31+dt1=100
x12+x22+x32+dt2=75
x13+x23+x33+dt3=50
x14+x24+x34+dt4=125

LINDO:
LP OPTIMUM FOUND AT STEP      5
        OBJECTIVE FUNCTION VALUE
        1)      102950.0
VARIABLE        VALUE          REDUCED COST
       X11        50.000000          0.000000
       X12         0.000000         15.000000
       X13        50.000000          0.000000
       X14        50.000000          0.000000
       X21         0.000000          1.000000
       X22        75.000000          0.000000
       X23         0.000000          0.000000
       X24        25.000000          0.000000
       X31         0.000000          6.000000
       X32         0.000000         23.000000
       X33         0.000000          0.000000
       X34        50.000000          0.000000
       DT1        50.000000          0.000000
       DT2         0.000000      23012.000000
       DT3         0.000000      17996.000000
       DT4         0.000000      12998.000000

       ROW   SLACK OR SURPLUS     DUAL PRICES
        2)         0.000000       1988.000000
        3)         0.000000       1986.000000
        4)         0.000000       1996.000000
        5)         0.000000      -2000.000000
        6)         0.000000      -1988.000000
        7)         0.000000      -2004.000000
        8)         0.000000      -2002.000000
NO. ITERATIONS=       5

RANGES IN WHICH THE BASIS IS UNCHANGED:
                           OBJ COEFFICIENT RANGES
VARIABLE         CURRENT        ALLOWABLE        ALLOWABLE
                   COEF          INCREASE         DECREASE
      X11       12.000000         1.000000     12998.000000
      X12       15.000000         INFINITY        15.000000
      X13       16.000000         0.000000         INFINITY
      X14       14.000000        15.000000         0.000000
      X21       15.000000         INFINITY         1.000000
      X22        2.000000        15.000000         INFINITY
      X23       18.000000         INFINITY         0.000000
      X24       16.000000         0.000000        15.000000
      X31       10.000000         INFINITY         6.000000
      X32       15.000000         INFINITY        23.000000
      X33        8.000000         INFINITY         0.000000
      X34        6.000000         0.000000         INFINITY
      DT1     2000.000000     12998.000000         INFINITY
      DT2    25000.000000         INFINITY     23012.000000
      DT3    20000.000000         INFINITY     17996.000000
      DT4    15000.000000         INFINITY     12998.000000
                           RIGHTHAND SIDE RANGES
      ROW         CURRENT        ALLOWABLE        ALLOWABLE
                    RHS          INCREASE         DECREASE
        2      150.000000        50.000000        50.000000
        3      100.000000        50.000000        25.000000
        4       50.000000        50.000000        50.000000
        5      100.000000         INFINITY        50.000000
        6       75.000000        25.000000        50.000000
        7       50.000000        50.000000        50.000000
        8      125.000000        50.000000        50.000000

viernes, 4 de noviembre de 2011

INTERPRETACIÓN DE LINDO

LA VIDA DE DANTZING

GEORGE DANTZIG (BIOGRAFÍA)

George Bernard Dantzig (8 de noviembre de 1914 – 13 de mayo de 2005) fue un matemático reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal". Recibió muchos honores, tales como la Medalla Nacional a la 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 en la 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 Sorbonne, Anja Ourisson, y la pareja inmigró a los Estados Unidos.

La verdad de un mito urbano

Un hecho real en la vida de Dantzig dio origen a una famosa leyenda urbana en 1939 mientras él era un estudiante graduado en Berkeley. Cerca del comienzo de una clase a la que Dantzig llegaba tarde, el profesor Jerzy Neyman escribió en la pizarra dos ejemplos famosos de problemas estadísticos no resueltos. Cuando Dantzig llegó más tarde a clase, pensó que los dos problemas eran tarea para la casa y los escribió en su cuaderno. De acuerdo a Dantzig, los problemas "le parecieron ser un poco más difíciles de lo normal", pero unos pocos días después obtuvo soluciones completas para ambos, aún creyendo que estos eran tareas que debía entregar. Seis semanas después, Dantzig recibió la visita de un excitado profesor Neyman, quien había preparado una de las soluciones de Dantzig para ser publicada en una revista matemática. Años después otro investigador, Abraham Wald, se preparaba para publicar un artículo en el que llegaba a la conclusión del segundo problema, y en este artículo incluyó a Dantzig como coautor.

Esta historia comenzó a difundirse, y fue usada como una lección motivacional demostrando el poder del pensamiento positivo. A través del tiempo el nombre de Dantzig fue removido y los hechos fueron alterados, pero la historia básica persiste en la forma de un mito urbano.

El Nacimiento de la Programación Lineal

Cuando comenzó la Segunda Guerra Mundial, los estudios de Dantzig en Berkeley fueron suspendidos, y el se convirtió en la cabeza de la Rama de Análisis de Combate de los Cuarteles Centrales Estadísticos de Fuerza Aérea de los Estados Unidos, lo cual lo llevó a lidiar con las logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas. El trabajo proporcionó los problemas del "mundo real" que la programación lineal vendría a resolver.

George Dantzig recibió su doctorado en Berkeley en 1946. Él originalmente iba a aceptar un puesto como profesor en Berkeley, pero fue persuadido por su esposa y colegas del Pentágono para volver ahí como consejero matemático de la USAF. Fue ahí, en 1947 que el por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo. En 1952 se convirtió en un investigador matemático en la Corporación RAND, donde comenzó a implementar la programación lineal en los computadores de la corporación. En 1960 fue contratado por su alma máter, donde enseñó ciencias de la computación, eventualmente convirtiéndose en el presidente del Centro de Investigación de Operaciones. En 1966 tomó un cargo similar en la Universidad de Stanford. Se quedó en Standord hasta su retiro en los años 90.

En adición a su trabajo significativo en el desarrollo del método simplex y la programación lineal, Dantzig también hizo avances en los campos de la teoría de la descomposición, análisis de sensibilidad, métodos de pivot complementarios, optimización a gran escala, programación no lineal, y programación bajo incertidumbre. El primer ejemplar del SIAM Jornal on Optimization en 1991 fue dedicado a él.

SIMPLEX DUAL Y PRIMAL

LINDO EJERCICIOS

Un hipermercado necesita como mínimo 16 cajas de langostino, 5 cajas de nécoras y 20 de percebes. Dos mayoristas, A y B, se ofrecen al hipermercado para satisfacer sus necesidades, pero sólo venden dicho marisco en contenedores completos. El mayorista A envía en cada contenedor 8 cajas de langostinos, 1 de nécoras y 2 de percebes. Por su parte, B envía en cada contenedor 2, 1 y 7 cajas respectivamente. Cada contenedor que suministra A cuesta S/210, mientras que los del mayorista B cuestan S/300 cada uno.

1.-¿Cuántos contenedores deben pedir el hipermercado a cada mayorista para satisfacer sus necesidades mínimas con el menor coste posible?

2.-¿Cuántos langostinos llegaran?

3.-¿Cuántos es el costo máximo que se puede pagar por contenedor tipo A?

4.-¿Cuántos percebes llegaran en los contenedores tipo B?

5.-¿Qué especie conviene pedir más?

6.-¿Cuántas cajas mínimas de langostinos se puede tener?

Solución:

	Contenedor A	Contenedor B	Necesidad
Langostino	8 cajas/contenedor	2cajas/contenedor	16 cajas
Nécoras	1 cajas/contenedor	1cajas/contenedor	5 cajas
Percebes	2 cajas/contenedor	7cajas/contenedor	20 cajas
Costo	S/210/contenedor	S/300/contenedor

Variable de decisión:

Xi = Cantidad de contenedores tipo i(i=A,B=1,2) a pedir.

Función objetivo:

Minimizar el costo

Min=210x₁+300x₂

Restricciones:

Langostinos

8x₁+2x₂>=16

Nécoras:

1x₁+1x₂>=5

Percebes:

2x₁+7x₂>=20

No negatividad:

X_i>=0

Min 210x1+300x2

Lang)8x1+2x2>=16

Néc)1x1+1x2>=5

Perc)2x1+7x2>=20

end

LP OPTIMUM FOUND AT STEP 2

OBJECTIVE FUNCTION VALUE

1) 1230.000

El mínimo de costo de compra del hipermercado es de s/ 1230.

VARIABLE VALUE REDUCED COST

X1 3.000000 0.000000

Se deben comprar 3 contenedores de tipos A.

X2 2.000000 0.000000

Se deben comprar 2 contenedores de tipo B

ROW SLACK OR SURPLUS DUAL PRICES

LANG) 12.000000 0.000000

La cantidad de cajas de langostinos crece 12 cajas mas con respecto a las 16 deseadas.

El precio dual es caro, es decir no se gana ni se pierde por cada caja adicional.

NéC) 0.000000 -174.000000

La cantidad de cajas de nécoras crece 0 cajas mas con respecto a las 5 deseadas.

El precio dual es -174, es decir se pierde s/174 por cada caja adicional.

PERC) 0.000000 -18.000000

La cantidad de cajas de percebes crece 0 cajas mas con respecto a las 20 deseadas.

El precio dual es -18, es decir se pierde s/18 por cada caja adicional.

NO. ITERATIONS= 2

RANGES IN WHICH THE BASIS IS UNCHANGED:

OPTIMALIDAD:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

X1 210.000000 90.000000 124.285713

(210-124.2857713<=C1 <= (210+90)

El costo máximo por contenedor tipo A es de s/300 y el costo mínimo es s/85

X2 300.000000 435.000000 90.000000

(300-90)<= C2<= (300+435)

El costo máximo por contenedor tipo B es de s/735 y el costo mínimo es s/210

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE

RHS INCREASE DECREASE

FACTIBILIDAD:

LANG 16.000000 12.000000 INFINITY

(16- INFINITO)<= B1 <= (16+12)

LA CANTIDAD MAXIMA DE CAJAS DE LANGOSTINOS ES 28 Y LA MINIMA 0

NéC 5.000000 5.000000 1.153846

(5-1.153846)<= B2 <= (5+5)

LA CANTIDAD MAXIMA DE CAJAS DE NÉCORAS ES 10 Y LA MINIMA 4.85.

PERC 20.000000 10.000000 10.000000

(20- 10)<= B3 <= (20+10)

LA CANTIDAD MAXIMA DE CAJAS DE PERCEBES ES 30 Y LA MINIMA 10

RPTA:

1¿cuantos contenedores deben pedir el hipermercado a cada mayorista para satisfacer sus necesidades mínimas con el menor coste posible?

VARIABLE VALUE REDUCED COST

X1 3.000000 0.000000

Se deben comprar 3 contenedores de tipos A.

X2 2.000000 0.000000

Se deben comprar 2 contenedores de tipo B

2¿Cuántos langostinos llegaron?

LA CANTIDAD MAXIMA DE CAJAS DE LANGOSTINOS ES 28 Y LA MINIMA 0

3¿Cuántos es el costo máximo que se puede pagar por contenedor tipo a?

(210-124.2857713<=C1 <= (210+90)

El costo máximo por contenedor tipo A es de s/300 y el costo mínimo es s/85

4¿ cuantos percebes llagaran en los contenedores tipo B?

	Contenedor A	Contenedor B 2	Necesidad
Langostino	8 cajas/contenedor	2cajas/contenedor	16 cajas
Nécoras	1 cajas/contenedor	1cajas/contenedor	5 cajas
Percebes	2 cajas/contenedor	7cajas/contenedor	20 cajas
Costo	S/210/contenedor	S/300/contenedor

(2 contenedores que van a multiplicar a (7 cajas / contenedor) = 14 cajas

5¿qué especie conviene pedir más?

Como el precio dual del langostino es cero, conbiene pedir más de esta especie, puesto que las otras tienen precio dual negativo

6¿ cuántas cajas mínimas de langostinos se puede tener?

LA CANTIDAD MAXIMA DE CAJAS DE LANGOSTINOS ES 28 Y LA MINIMA 0