Laboratorio Unidad 3 Programación Entera Equipo 2 PDF

Preview

Summary

Download Laboratorio Unidad 3 Programación Entera Equipo 2 PDF

Description

INSTITUTO TECNOLOGICO DE NUEVO LEÓN

INVESTIGACIÓN DE OPERACIONES 1 EJERCICIOS DEL TEMA No 3

PROGRAMACIÓN ENTERA.

EQUIPO No. 2 INTEGRANTES:       

Acevedo Cadena Carlos Alberto. Castillo Hernández Juan Carlos. Cortez Chacón Yarely Jazmín. Flores Martínez Jan Alberto. Flores Valerio Veira Alhinna. Landaverde Castañeda Gregorio. Ramírez Soto Karla Abigail.

NO. DE CONTROL: 19480372 19480558 19480261 19480499 19480346 19480519 19480025

GUADALUPE N. L. A 23 __ DE NOVIEMBRE _____________ DEL 2020.

1

ÍNDICE 1. Introducción………………………………………….……………….……..……3 2. Problema Resueltos Por (Castillo Hernández Juan Carlos).………...…..4 3. Problema Resueltos Por (Cortez Chacón Yarey Jazmín)….………..…..13 4. Problema Resueltos Por (Flores Martínez Jan Alberto)………….....…..23 5. Problema Resueltos Por (Flores Valerio Veira Alhinna)…..…………....32 6. Problema Resueltos Por (Landaverde Castañeda Gregorio)….……….41 7. Problema Resueltos Por (Ramírez Soto Karla Abigail)………………….74 8. Conclusión……………………………………………………………...…...…104 9. Bibliografía…………………………………………………………….....……110

2

INTRODUCCIÓN Un modelo de Programación Entera es aquel cuya solución óptima tiene sentido solamente si una parte o todas las variables de decisión toman valores restringidos a números enteros, permitiendo incorporar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los modelos de Programación Lineal. En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren a los utilizados en los modelos de Programación Lineal, destacándose entre ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch & Cut, Planos Cortantes, Relajación Lagrangeana, entre otros. La programación entera es el método empleado para resolver problemas que tienen variables de decisión enteras. Estos modelos se han considerado sub-modelos de la programación lineal con la característica de enteridad. Los creadores e investigadores de esta técnica fueron Wagner (1950) y Manne (1959), quienes desarrollaron varios métodos de solución. Uno de los primeros enfoques de solución al tipo de problemas que plantea la programación entera, fue el de evaluación de cada posible solución, es decir, cada una de las combinaciones de valores enteros para las variables del problema, conduciendo a una solución óptima exacta. A este tipo de resoluciones se les dio el nombre de métodos exactos. En el mundo de la industria y los negocios hay numerosas situaciones en las cuales se presentan problemas de programación lineal para los cuales las variables de decisión sólo pueden tener valores de números enteros y no fraccionarios. Esto debido a alguna razón física, por ejemplo, si las variables de decisión son números de personas, de artículos terminados, etc., será obvio que no podrán ser números fraccionarios, pues esto no tendría ningún sentido. Es aquí donde se plantea el problema de programación lineal como un caso de programación entera. En general se puede decir que un modelo de programación entera es aquel que contiene restricciones y una función objetivo idénticas a la formuladas en programación lineal, la única diferencia en que una o más variables de decisión deben tomar valor entero en la solución final. En el presente trabajo se muestran algunos problemas resueltos por los métodos de programación entera, se muestra todo el procedimiento de cada uno de ellos.

3

PROBLEMAS RESUELTOS POR: CASTILLO HERNÁNDEZ JUAN CARLOS

4

Juan Carlos Castillo Hernández METODO GRAFICO 1. Maximizar Z = 4X1 + 5X2 Sujeto a: 2X1 + 3X2 ≤ 120 2X1 + 1.5X2 ≤ 80 X1, X2 ≥ 0 y Enteros

1. Graficar restricciones 60

① 2x1 + 3x2 =120

50

X1= 0

x2=40

40

X2= 0

x1=60

30 20

② 2X1 + 1.5X2 = 80

10

X1= 0

x2= 53. 33

X2= 0

x1= 40

0 0

10

20

30

20

30

40

50

60

70

2. Graficar la función objetivo Maximizar Z = 4X1 + 5X2

60

0, 53.33

50

4x1 + 5x2= 20

40

X1= 0 x2= 4

30

0, 40

20

X2= 0 x1= 5

10 0, 4

0 0

vértice a b c d

X1 0 0 20 40

X2 0 40 26.66 0

z 0 200 213.3 160

5, 0 10

40, 0 40

60, 0 50

60

70

Solución óptima: X1= 20

X1= 20 Z= 180

X2= 20

Z= 210 X2= 26

5

Juan Carlos Castillo Hernández METODO GRAFICO 2. Maximizar Z = 300X1 + 400X2 Sujeto a: 2X1 + 3X2 ≤ 900 X1 ≤ 300 X2 ≤ 200 X1, X2 ≥ 0 y Enteros

1.

Graficar restricciones 350

① 2X1 + 3X2 = 900

300

250

X1=0 x2= 300

200

X2= 0 x1= 450

150

② X1 = 300

100 50

③ X2 = 200

0 0

2.

100

200

300

400

500

Graficar la función objetivo

Maximizar Z = 300X1 + 400X2

350

300X1 + 400X2= 120000

300

X1= 0

x2= 300

250

X2= 0

x1= 400

200

0, 300

0, 200

150 100 50

Vértice

X1

X2

z

a b c d

0 300 300 150

0 0 100 200

0 90,000 130,000 125,000

0

e

0

200

80,000

X1 = 300

300, 0 0

100

200

300

400

400, 0 450, 0 500

Max z = 130, 000

X2= 100

6

Juan Carlos Castillo Hernández METODO GRAFICO 3. Maximizar Z = 20X1 + 25X2 Sujeto a: 2X1 + 3X2 ≤ 48 X1 ≤ 150 X2 ≤ 100 X1, X2 ≥ 0 y Enteros

1.

Graficar restricciones 120

① 2X1 + 3X2 = 48

100

0, 100

80

X1= 0 x2= 16

60

X2= 0 x1= 24

40

② X1 = 150

20

③ X2 = 100

0, 16

0

24, 0 0

150, 0 50

Vértice a b

X1 0 24

X2 0 0

z 0 480

Max z= 480

c

0

16

400

X2= 0

100

150

200

X1= 24

7

Juan Carlos Castillo Hernández METODO GRAFICO 4. Maximizar Z = 500X1 + 1000X2 Sujeto a: 2.5X1 + 5.5X2 ≤ 1200 X1 + X2 ≤ 500 X1 ≤ 200 X1, X2 ≥ 0 y Enteros 1.

Graficar restricciones 600

① 2.5X1 + 5.5X2 = 1200

500

X1= 0 x2= 218.18

400 300

X2= 0 x1= 480

200

② X1 + X2 = 500

100

X1= 0 x2= 500

0 0

X2= 0 x1= 500

100

200

300

400

500

600

③ X1 = 200 2.

Graficar la función objetivo 600

Maximizar Z = 500X1 + 1000X2 500X1 + 1000X2 = 100,000 X1= 0

x2= 100

X2= 0

x1= 200

0, 500

500 400 300 200

v

100

0, 218.18

0, 100

0

200, 0 0

X1= 200

X1= 200

X2= 100

X2= 127

200

300

400

48 500, 0 500

Max z= 227, 000 Z= 227,000

Z= 200,000

100

X1= 200 X2= 127

8

600

Juan Carlos Castillo Hernández METODO GRAFICO 5. Maximizar Z = 3X1 + 4X2 Sujeto a: 2X1 + X2 ≤ 6 2X1 + 3X2 ≤ 9 X1, X2 ≥ 0 y Enteros

1.

Graficar restricciones 7

①2X1 + X2 = 6

6 5

X1= 0 x2= 6

4

X2= 0 x1= 3

3

② 2X1 + 3X2 = 9

2

v

1

X1= 0 x2= 3

0 0

X2= 0 x1= 4.5

2.

Graficar la función objetivo

Maximizar Z = 3X1 + 4X2

X2= 0

2

3

4

5

7

6

0, 6

5

3X1 + 4X2 = 12 X1= 0

1

4

x2= 3

3

v

0, 3

2

x1= 4

1 0

3, 0 0

X1= 2

X1= 1

X2= 2

X2= 1

2

3

4, 0

4.5, 0 5

4

Max z= 11 Z= 10

Z= 11

1

X1= 1 X2= 2

9

Juan Carlos Castillo Hernández METODO DE RAMIFICACIÓN 1. Maximizar Z = 4X1 + 5X2 Max z= 213.3

Sujeto a: 2X1 + 3X2 ≤ 120

X1= 20

2X1 + 1.5X2 ≤ 80

X2= 26.66

X1, X2 ≥ 0 y Enteros X2 ≤ 26 X1= 21 X1= 20.5 X2 ≤ 26

X2 ≥27

X1= 20.5

X1= 19.5

X1= 19.5

X2= 26

X2= 27

X1= 19.72

Z= 212

Z= 213

X2 ≥27

X1 ≤ 19 X2 = 27.33 X2 = 28 X2 ≥ 27

X1 ≥20

X1= 19

X1= 20

X2 = 26.66

X2= 27.33

No factible

X2 = 26.66 X2 ≥ 27

Z= 212.65

X1 ≤ 19

X1 ≥ 20 X2 ≤ 27

X2 ≥ 28

X1 = 19.5

X1= 19

X1= 18

X1 = 18

X1 = 19.75

X2= 27

X2= 28

X1 = 19

X2 ≥ 27

Z= 211

Z= 212

X2 ≥ 27

X1 ≤ 19

X1 ≤ 19

X2 ≤ 27

X2 ≥ 28

Max Z= 212 X1= 18 X2= 28

10

Juan Carlos Castillo Hernández METODO DE RAMIFICACIÓN 2. Maximizar Z = 300X1 + 400X2 Max z= 130, 000

Sujeto a: 2X1 + 3X2 ≤ 900

Solución óptima a partir del método grafico antes realizado

X1= 300

X1 ≤ 300

X2= 100

X2 ≤ 200 X1, X2 ≥ 0 y Enteros

3. Maximizar Z = 20X1 + 25X2 Max z= 480

Sujeto a: 2X1 + 3X2 ≤ 48

Solución óptima a partir del método grafico antes realizado

X1= 24

X1 ≤ 150

X2= 0

X2 ≤ 100 X1, X2 ≥ 0 y Enteros

4. Maximizar Z = 500X1 + 1000X2

Max z= 227,270

Sujeto a: 2.5X1 + 5.5X2 ≤ 1200

X1= 200

X1 + X2 ≤ 500

X2= 127.27

X1 ≤ 200 X1, X2 ≥ 0 y Enteros X2 ≤ 127

X1= 200.6 X1= 373

X2 ≥ 128

X1= 200

X1= 198.4

X2= 127

X2= 128

Z= 227,000

Z= 227,200

X1= 198.4

X1 ≤ 200 X2 ≤ 127

X1= 372 X1 ≤ 200 X2 ≥ 128

Max Z= 227,00 X1= 200 X2= 127

11

Juan Carlos Castillo Hernández METODO DE RAMIFICACIÓN 5. Maximizar Z = 3X1 + 4X2 Max z= 12.75

Sujeto a: 2X1 + X2 ≤ 6

X1= 2.25

2X1 + 3X2 ≤ 9

X2= 1.5

X1, X2 ≥ 0 y Enteros X2 ≤ 1 X1= 2.5 X1= 23 X2 ≤ 1

X2 ≥ 2

X1= 2.5

X1= 1.5

X1= 2

X2= 1

X2= 2

X1=1.5

Z= 11.5

Z= 12.5

X2 ≥ 2

X1 ≤ 1 X2 = 4 X2 = 2.33 X2 ≥ 2

X1 ≥ 2

X1= 1

X1= 2

X2 = 2

X2= 2.33

No factible

X2 = 1.66 X2 ≥ 2

Z= 12.33

X1 ≤ 1

X1 ≥ 2 X2 ≤ 2

X2 ≥ 3

X1 = 2

X1= 1

No factible

X1 = 1.5

X1 = 1.5

X2= 2

X1 = 2

X2 ≥ 2

Z= 11

X2 ≥ 2

X1 ≤ 1

X1 ≤ 1

X2 ≤ 2

X2 ≥ 3

Max Z= 11 X1= 1 X2= 2

12

PROBLEMAS RESUELTOS POR: CORTEZ CHACÓN YARELY JAZMÍN

13

Yarely Jazmín Cortez Chacón Problema 1. Método de ramificación 1. Maximizar Z = 4X1 + 5X2 Sujeto a: 2X1 + 3X2 ≤ 120 2X1 + 1.5X2 ≤ 80 X1, X2 ≥ 0 y Enteros

Max z= 213.3 X1= 20 X2= 26.66

Restricciones

X2 ≤ 26

X2 ≥27

Restricciones

①X1= 21

X1= 20.5

X1= 19.5

① X1= 19.5

②X1= 20.5

X2= 26

X2= 27

②X1= 19.72

③X2 ≤ 26

Z= 212

Z= 213

③X2 ≥27

X1 ≥20

X1 ≤ 19

Restricciones

Restricciones ①X2 = 27.33

X1= 19

X1= 20

②X2 = 28

X2= 27.33

No factible

③X2 ≥ 27

Z= 212.65

X2 ≤ 27

②X2 = 26.66 ③X2 ≥ 27 ④X1 ≥ 20

④X1 ≤ 19 Restricciones

①X2 = 26.66

X2 ≥ 28

Restricciones

①X1 = 19.5

X1= 19

X1= 18

①X1 = 18

②X1 = 19.75

X2= 27

X2= 28

②X1 = 19

Max Z= 212

③X2 ≥ 27

Z= 211

Z= 212

③X2 ≥ 27

X1= 18

④X1 ≤ 19

④X1 ≤ 19

X2= 28

⑤X2 ≤ 27

⑤X2 ≥ 28

14

Yarely Jazmín Cortez Chacón Problema 1. Método gráfico

1. Maximizar Z = 4X1 + 5X2 Sujeto a: 2X1 + 3X2 ≤ 120 2X1 + 1.5X2 ≤ 80 X1, X2 ≥ 0 y Enteros

1. Igualar Restricciones

2. Igualar Función Objetivo

① 2x1 + 3x2 =120 X1= 0

x2=40

X2= 0

x1=60

Maximizar Z = 4X1 + 5X2 4x1 + 5x2= 2 X1= 0 x2= 4

② 2X1 + 1.5X2 = 80 X1= 0

x2= 53. 3

X2= 0

x1= 40

X2= 0 x1=

3. Graficar restricciones y función objetivo 60 50

40 30 20 Región factible

10 0 0

10

20

30

40

50

60

70

4. Identificar vértices y solución óptima en enteros Vértices a b c d

X1 0 0 40 20

X2 0 40 0 26.66

Z 0 200 160 213.3

X1= 20

X1= 20

Z=210

Z=180 X2= 20

X2= 26

15

Yarely Jazmín Cortez Chacón Problema 2. Método de ramificación 2. Maximizar Z = 300X1 + 400X2 Sujeto a: 2X1 + 3X2 ≤ 900 X1 ≤ 300 X2 ≤ 200 X1, X2 ≥ 0 y Enteros

Llegamos ya a la solución óptima, ya que nuestras variables son enteras

Max z= 130, 000 X1= 300 X2= 100

Problema 2. Método gráfico 2. Maximizar Z = 300X1 + 400X2 Sujeto a: 2X1 + 3X2 ≤ 900 X1 ≤ 300 X2 ≤ 200

1. Igualar Restricciones ① 2X1 + 3X2 = 900

2. Igualar Función Objetivo Maximizar Z = 300X1 + 400X2

X1= 0 x2= 300 X2= 0 x1= 450 ② X1= 300 ③ x2= 200

300X1 + 400X2= 120000 X1= 0

x2= 300

X2= 0

x1= 400

16

3. Graficar restricciones y función objetivo 350 300 250 200 150 100

50 0 0

100

200

300

400

500

4. Identificar vértices y solución óptima en enteros Vértice

X1

X2

z

a

0

0

0

b

300

0

90,000

c

300

100

130,000

Max z = 130, 000

d

150

200

125,000

X1 = 300

e

0

200

80,000

X2= 100

Problema 3. Método de ramificación

3. Maximizar Z = 20X1 + 25X2 Sujeto a: 2X1 + 3X2 ≤ 48

Max z= 480

X1 ≤ 150

X1= 24

X2 ≤ 100

X2= 0

Llegamos ya a la solución óptima, ya que nuestras variables son enteras

X1, X2 ≥ 0 y Enteros

17

Problema 3. Método grafico METODO GRAFICO 3. Maximizar Z = 20X1 + 25X2 Sujeto a: 2X1 + 3X2 ≤ 48 X1 ≤ 150 X2 ≤ 100 X1, X2 ≥ 0 y Enteros

1. Igualar restricciones y graficar ① 2X1 + 3X2 = 48

120

X1= 0 x2= 16

100

X2= 0 x1= 24

80

② X1 = 150

60 40

③ X2 = 100

20 0 0

Vértice

X1

X2

z

a b c

0 24 0

0 0 16

0 480 400

50

100

150

200

Max z= 480 X1= 24 X2= 0

18

Yarely Jazmín Cortez Chacón Problema 4. Método de ramificación 4. Maximizar Z = 500X1 + 1000X2 Sujeto a: 2.5X1 + 5.5X2 ≤ 1200 X1 + X2 ≤ 500 X1 ≤ 200

Max z= 227,270 X1= 200 X2= 127.27 Restricciones

X2 ≤ 127

X2 ≥128

Restricciones

① X1= 200.6

X1= 200

X1= 198.4

①X1= 198.4

② X1= 373

X2= 127

X2= 128

②X1= 372

③ X1 ≤ 200

Z= 227,000

Z= 227,200

③X1 ≤ 200

④X2 ≤ 127

④X2 ≥ 128

Max Z= 227,00 X1= 200 X2= 127

19

Yarely Jazmín Cortez Chacón Problema 4. Método grafico 4. Maximizar Z = 500X1 + 1000X2 Sujeto a: 2.5X1 + 5.5X2 ≤ 1200 X1 + X2 ≤ 500 X1 ≤ 200 X1, X2 ≥ 0 y Enteros

1.

Igualar restricciones 2. Graficar la función objetivo

① 2.5X1 + 5.5X2 = 1200 Maximizar Z = 500X1 + 1000X2

X1= 0 x2= 218.18

500X1 + 1000X2 = 100,000

X2= 0 x1= 480 ② X1 + X2 = 500 X1= 0 x2= 500

X1= 0

x2= 100

X2= 0

x1= 200

X2= 0 x1= 500 ③ X1 = 200 3. Graficar restricciones y función objetivo 600 500 400 300 200

v

100 0 0

100

200

300

400

500

600

4. Identificar puntos más cercanos a los vértices

Z= 227,000

Z= 200,000 X2= 100

Solución optima

X1= 200

X1= 200

X2= 127

20

Yarely Jazmín Cortez Chacón Problema 5. Método de ramificación 5. Maximizar Z = 3X1 + 4X2 Sujeto a: 2X1 + X2 ≤ 6 2X1 + 3X2 ≤ 9 X1, X2 ≥ 0 y Enteros

Max z= 12.75 X1= 2.25 X2= 1.5

Restricciones

X2 ≤ 1

X2 ≥2

Restricciones

①X1= 2.5

X1= 2.5

X1= 1.5

①X1= 2

②X1= 2

X2= 1

X2= 2

②X1=1.5

③X2 ≤ 1

Z= 11.5

Z= 12.5

③X2 ≥ 2

X1 ≥2

X1 ≤ 1

Restricciones

Restricciones

①X1= 2

①X1= 4

X1= 1

X1= 2

②X1= 2.33

X2= 2.33

No factible

③X2 ≥ 2

Z= 12.33<...