Programacion Entera Binaria Sesión 06

Sesión 04: Problema 04

Agregar:3Ydg

Min=6*Yab+3*Yad+5*Yac+2*Ybf+4*Ydf+Yde+2*Yce+Ycg+2*Yeg+4*Yfh+7*Yeh+5*Ygh+3*Ydg;

Yab+Yad+Yac=1;

Yab=Ybf;

Yac=Yce+Ycg;

Yad=Ydf+Yde+dg;

Yde+Yce=Yeh+Yeg;

Ybf+Ydf=Yfh;

Yeg+Ycg=Ygh;

Yfh+Yeh+Ygh=1;

@bin(Yab);

@bin(Yad);

@bin(Yac);

@bin(Ybf);

@bin(Ydf);

@bin(Yde);

@bin(Yce);

@bin(Ycg);

@bin(Yeg);

@bin(Yfh);

@bin(Yeh);

@bin(Ygh);

@bin(Ydg);

   Global optimal solution found.

   Objective value:                              11.00000

   Extended solver steps:                               0

   Total solver iterations:                             0

                       Variable           Value        Reduced Cost

                            YAB        0.000000            6.000000

                            YAD        0.000000            3.000000

                            YAC        1.000000            5.000000

                            YBF        0.000000            2.000000

                            YDF        0.000000            4.000000

                            YDE        0.000000            1.000000

                            YCE        0.000000            2.000000

                            YCG        1.000000            1.000000

                            YEG        0.000000            2.000000

                            YFH        0.000000            4.000000

                            YEH        0.000000            7.000000

                            YGH        1.000000            5.000000

                            YDG        0.000000            3.000000

                             DG        0.000000            0.000000

                            Row    Slack or Surplus      Dual Price

                              1        11.00000           -1.000000

                              2        0.000000            0.000000

                              3        0.000000            0.000000

                              4        0.000000            0.000000

                              5        0.000000            0.000000

                              6        0.000000            0.000000

                              7        0.000000            0.000000

                              8        0.000000            0.000000

                              9        0.000000            0.000000

De todas las rutas establecidas tomamos la más corta, siendo ese nuestro objetivo, en este caso lo conforma las siguiente ruta: YAC+YCG+YGH. Esta ruta presenta una distancia de 11 metros es la más adecuada.

Sesión 04: Problema 03

Para graduarse en una universidad con especialidad en I.O. un estudiante debe completar por lo menos dos cursos de INVOPE, por lo menos 2 cursos de matemáticas y por lo menos 2 cursos  de computación. Se puede usar algunos cursos para satisfacer mas de un requisito, Calculo puede satisfacer el curso de Matemáticas, Investigación de Operaciones los requisitos de INVOPE y Matemática, Estructura de Datos los de Matemática y Computación, Estadística los de matemáticas e INVOPE, Simulación los de INVOPE y Computación, Introducción a la Programación los de Computación; y Métodos de Predicción los de INVOPE y Matemáticas. Algunos cursos son pre requisitos  para otros: Calculo para estadística, Introducción a la Programación para Simulación y Estructura de Datos; y Estadística para Métodos de Predicción. Formule un Modelo de PLE que minimice el número de cursos necesarios para satisfacer los requisitos de la especialización.

Calculo=Y1

Inv.Op=Y2

Estructura de Datos=Y3

Estadística=Y4

Simulación=Y5

Introd.Progra.=Y6

Metodos Predicción=Y7

Agregar: Si se matricula en simulación y Estadística también debe matricularse en estructura de datos.

Min=y1+y2+y3+y4+y5+y6+y7;

y2+y4+y5+y7>=2;

y1+y2+y3+y4+y7>=2;

y3+y5+y6>=2;

y4<=y1;

y3<=y6;

y5<=y6;

y7<=y4;

2*y3<=y4+y5;

@bin(y1);

@bin(y2);

@bin(y3);

@bin(y4);

@bin(y5);

@bin(y6);

@bin(y7);

                   Global optimal solution found.

   Objective value:                              4.000000

   Extended solver steps:                               0

   Total solver iterations:                             0

                       Variable           Value        Reduced Cost

                             Y1        1.000000            1.000000

                             Y2        0.000000            1.000000

                             Y3        0.000000            1.000000

                             Y4        1.000000            1.000000

                             Y5        1.000000            1.000000

                             Y6        1.000000            1.000000

                             Y7        0.000000            1.000000

                            Row    Slack or Surplus      Dual Price

                              1        4.000000           -1.000000

                              2        0.000000            0.000000

                              3        0.000000            0.000000

                              4        0.000000            0.000000

                              5        0.000000            0.000000

                              6        1.000000            0.000000

                              7        0.000000            0.000000

                              8        1.000000            0.000000

                              9        2.000000            0.000000

De  todos los cursos mencionados, pues debemos tratar de cursar por los menos posibles de ellos, en este caso son los cursos que están representados por las variables: Y1, Y4, Y5, Y6 que en su y totalidad son cuatro los cursos que  se estudiaran.

Sesión 04 - Problema 02

Oilco está considerando dos sitios potenciales para perforaciones, para llegar a cuatro objetivos (posibles pozos petroleros). La siguiente tabla proporciona los costos de preparación en cada uno de los dos sitios y el costo de perforar en cada sitio. Formule el problema como un  PLE.

Lugar    1    2      3        4   Costo de Preparación   

 Sitio 1   2   1      8        5          5

Sitio  2   4    6     3        1          6

Agregar:

Si se ubica el  pozo 1 en el sitio 2, el pozo 2 debe estar en el sitio 1.

Solución - Lingo:

Min=2*y11+y21+8*y31+5*y41+4*y12+6*y22+3*y32+y42+5*y1+6*y2;

y11+y12=1;

y21+y22=1;

y31+y32=1;

y41+y42=1;

y11+y21+y31+y41<=4*y1;

y12+y22+y32+y42<=4*y2;

y21=y12;

@gin(y11);

@gin(y21);

@gin(y31);

@gin(y41);

@gin(y12);

@gin(y22);

@gin(y32);

@gin(y42);

@bin(y1);

@bin(y2);

   Global optimal solution found.

   Objective value:                              20.00000

   Extended solver steps:                               0

   Total solver iterations:                             0

                       Variable           Value        Reduced Cost

                            Y11        0.000000            2.000000

                            Y21        1.000000            1.000000

                            Y31        0.000000            8.000000

                            Y41        0.000000            5.000000

                            Y12        1.000000            4.000000

                            Y22        0.000000            6.000000

                            Y32        1.000000            3.000000

                            Y42        1.000000            1.000000

                             Y1        1.000000            5.000000

                             Y2        1.000000            6.000000

                            Row    Slack or Surplus      Dual Price

                              1        20.00000           -1.000000

                              2        0.000000            0.000000

                              3        0.000000            0.000000

                              4        0.000000            0.000000

                              5        0.000000            0.000000

                              6        3.000000            0.000000

                              7        1.000000            0.000000

                              8        0.000000            0.000000

Concluimos que en el sitio 1 encontramos se hará la perforación del pozo2, en el sitio 2 se harán las perforaciones del pozo 1,3 y 4.El  costos mínimo  de todo este proyecto suma la cantidad de $20.

Programación Entera

PROGRAMACIÓN ENTERA 

(RESUMEN)

La programación entera es en sí una programación lineal pero requiere que algunas variables o todas sean enteros no negativos.

Introducción a la programación entera:

Una PE en el cual se requiere que todas las variables tienen que ser enteros se denomina problema puro de programación con enteros. Ejemplo:

                         Max z =3x1+2x2

                          s.a  x1+x2<=6

                      X1, x2 >=0, x1, x2 enteros

Una PE en la cual se requiere solo algunas de las variables sean números enteros, se llama problema combinado de programación con enteros. Ejemplo:

                            Max z = 3x1+2x2

                            s.a x1+x2<=6

                          X1, x2>=0, x1 enteros

Una PE binaria trata de que las variables tengan que ser iguales a 0 o 1. Ejemplo:

                        Max z = x1-x2

                       s.a x1+2x2<=2

                       2x1-x2<=1

                    X1, x2 = 0 o bien 1

El concepto de relajación del PL de un problema de programación entera es un punto clave en la solución de las PE

El PL obtenido cuando se omiten todos los enteros o las restricción es 0.1 en las variables se llama relajación del PL de la PE

Ejemplo: relajación del PL

                        Max z = 3x1+2x2

                        s.a x1+x2<=6

                        X1, x2>=0

Relajación:

                      Max z = x1-x2

                      s.a x1+2x2<=2

                      2x1+x2<=1

                      X1, X2>=0

Planteamiento de problemas de programación entera:

Stockco proyecta 4 inversiones. La inversión 1 genera un valor neto actual de 16000 dólares, la inversión 2, 22000, la inversión 3, 12000, la inversión 4, 8000. Para cada inversión se requiere una cierta salida de efectivo en el tiempo presente: la inversión 1, 5000, la inversión 2, 7000, la inversión 3, 4000, la inversión 4, 3000. Dispone en la actualidad de 14000 para invertir. Plantear un PE que maximice el valor neto actual de las inversiones.

Solución:

            Xj (j=1, 2, 3,4) = 1 se efectúa inversión, 0 no se efectúa inversión

            Max 16x1+22x2+12x3+8x4 (en miles de dólares)

            Restricciones: 5x1+7x2+4x3+3x4<=14, esto sale de la salida de efectivo de cada inversión y tiene que ser menor a los 14mil que se tiene para invertir.

HERRAMIENTAS PARA LA TOMA DE DECISIONES

¿Que decisiones tomaste hoy?


1.Levantarme temprano.
2.Trabajar.
3.Asistir a INVOPE 2.


Variables

• Entera:

• Continua:

• Binarias

... Un Ejemplo de Pre-requisito:
- No puedes cumplir 16 años sin antes cumplir 15 a_a.
- Primero me baño, luego me maquillo.