• Author / Uploaded
• Emir L. Guarino

Citation preview

TP4

Investigación Operativa I - Programación Lineal - 2018

Trabajo Práctico Nº 4 Problema 1 Considerar las siguientes restricciones de un problema lineal:

2x1 - x2  4 x1 + 2x2  3 x1, x2≥ 0

a) Graficar la región factible. b) Plantear todas las bases posibles e identificar estas bases con el punto extremo correspondiente. ¿Cuáles son las bases factibles para este problema?

c) Para cada solución básica definir y calcular las variables básicas y no básicas. d) Suponer que en el espacio (x1,x2) un algoritmo de resolución se mueve del punto extremo (0,3/2)t al punto extremo (11/5,2/5)t. Especificar cuál es la variable que entró a la base y cuál es la que salió. Problema 2 Considerar la región factible del problema anterior. Hallar la solución óptima considerando la función objetivo: Maximizar 3x1 + 2x2 , comenzando del punto extremo (0,0)t. Problema 3 Dado el siguiente problema de PL:

Minimizar 15x1  28 x2  12 x3 s.a. : x1  2 x2  x3  5 2 x1  x2  3x3  2 x1 , x2 , x3  0 a) Hallar la solución óptima del problema a partir de la base: B=[a2,a3]. b) En cada iteración identificar B y B-1. c) Caracterizar la solución. Problema 4 Dado el siguiente problema de PL:

Maximizar 5 x1  2 x2 s.a. : - 2 x1  x2  4 5 x1  3x2  15 x1 , x2  0 a) Graficar la región factible. b) Resolver el problema usando el método simplex. En cada iteración, identificar la solución básica factible con el punto extremo correspondiente en el gráfico.

c) Caracterizar la solución. Problema 5 Una iteración del método simplex para el problema de Maximizar x1 + 2x2 , con restricciones de  y siendo x3 y x4 variables de holgura es la siguiente:

1

TP4

Investigación Operativa I - Programación Lineal - 2018 x1

x2

x3

x4

LD

b

2

f

g

16

c

0

1

4

8

d

e

0

2

a

a) Determinar las incógnitas a – g. b) ¿Es óptima la Tabla? En caso contrario, obtener la solución óptima. Problema 6 Resolver los siguientes problemas mediante el método simplex en tabla:

b) Max 3x1+ 2x2 – x3

a) Max 2x1- x2+ x3 s.a:

x1+ x2+ x3 ≤ 6

s.a:

2x1+ x2- x3 ≤ 4 -x1+ x2 + 2x3 ≤ 10

c) Min x1 – x2+ 2x3

x1 – x2 – x3 ≤ 10

x1 – x2+ 2x3 ≤ 6

s.a:

-x1+ 2x2 – x3 ≤ 5

x1+ x2 – x3 ≤ 4

xi≥0, i=1, 2,3

-x1+ x2 + x3 ≤ 2

xi≥0, i = 1, 2, 3

xi≥0, i = 1, 2, 3

Problema 7 Resolver el siguiente problema usando el método simplex:

minimizar 3x1 – 2x2 + x3 –x4 s.a. x1 + 2x2 + x3 = 2 -x1 + x2 + x4 = 1 x1, x2, x3, x4 ≥ 0 Problema 8 La siguiente tabla corresponde a un problema de programación lineal de maximización:

x1

x2

x3

x4

x5

x6

LD

a

b

0

0

9

0

16

7

c

1

0

d

0

e

-3

-4

0

1

-2

0

3

f

-2

0

0

6

1

5

Determinar las restricciones sobre todos los valores desconocidos para que se cumplan las siguientes condiciones:

a) b) c) d) e) f)

La tabla es la óptima, y muestra que la solución es única. La tabla es la óptima, y muestra que el problema tiene óptimos alternativos. La tabla muestra una solución factible degenerada. La tabla muestra una solución factible, y además muestra que el problema es no acotado. La solución que muestra la tabla es factible, pero puede mejorarse. Existen soluciones alternativas sobre un rayo.

2