Resumenes

PROGRAMACIÓN LINEAL ENTERA

Programación lineal: hipótesis de perfecta divisibilidad

Así pues decimos que un problema es de programación lineal entera, cuando prescindiendo de lascondiciones de integridad, el problema resultante es un problema de programación lineal.

CLASIFICACIÓN DE LOS PROBLEMAS LINEALES ENTEROS.

Atendiendo al tipo de variables:

Enteros puros: son aquellos en que todas las variables únicamente pueden tomar valores enteros. también se distinguen dentro de estos los problemas totalmente enteros como aquellos en que tanto las variables como todos los coeficientes que intervienen en el problema han de ser enteros.

Mixtos: son aquellos en los que hay al mismo tiempo variables continuas y variables que sólo pueden tomar valores enteros.

Binarios: las variables sólo pueden tomar los valores cero o uno.

Atendiendo al criterio del tipo de problema:

Directo: Si el problema de decisión involucra variables enteras.

Codificado: Cuando se trata de un problema que contiene además de aspectos cuantitativos, alguna consideración de tipo cualitativos, y por ello para tratar este tipo de aspectos se requiere el uso de variable enteras o binarias.

Transformado: Cuando el problema no incluye variables enteras, pero para ser tratado analíticamente requiere el uso de variable enteras “artificiales”.

MÉTODOS DE RESOLUCIÓN

Aunque en un principio pueda parecer que los problemas lineales enteros son más fáciles de resolver que los continuos, dado que el número de soluciones factibles a analizar, cuando el conjunto de oportunidades está acotado, es finito, éste número suele ser lo suficientemente grande (en un problema binario con n variables el número de soluciones factibles a estudiar es 2n) como para que resulte imposible su comparación.

COMPLEJIDAD

VARIABLES SOLUCIONES INCREMENTO

1 2

2 4 2

4 16 12

5 32 16

10 1.024 992

15 32.768 31.744

20 1.048.576 1.015.808

25 33.554.432 32.505.856

50 1,1259E+15 1,1259E+15

100 1,2677E+30 1,2677E+30

200 1,6069E+60 1,6069E+60

500 3,2734E+150 3,2734E+150

1000 1,0715E+301 1,0715E+301

ORDENADOR CON 1,000,000,000,000 DE OPERACIONES POR

SEGUNDO

1E+12

1 SEGUNDO 1 1E+12

1 MINUTO 60 6E+13

1 HORA 60 3,6E+15

1 DÍA 24 8,64E+16

1 MES 30 2,592E+18

1 AÑO 12 3,1104E+19

1 SIGLO 100 3,1104E+21

100 SIGLOS 100 3,1104E+23

1000 SIGLOS 10 3,1104E+24

MILLON DE SIGLOS 1000 3,1104E+27

100 MILLONES SIGLOS 100 3,1104E+29 1,2675E+30

1000 MILLONES SIGLOS 10 3,1104E+30

Problema con 100 variables 1,2677E+30 408 Millones de siglosAsí pues, la mayoría de los métodos de resolución comienzan su ejecución con la resolución del problema lineal asociado (en adelante PLA) consistente en eliminar las condiciones de integridad, obteniéndose en consecuencia un problema de programación lineal que puede ser resuelto mediante el algoritmo del simplex. La resolución del PLA en primer lugar, tiene una ventaja y es que si la solución a dicho problema verifica las condiciones de integridad de las variables, esta será la solución al problema entero, con lo cual no será necesario aplicar ninguna técnica especial para resolverlo. Si la solución al PLA no verifica las condiciones de integridad , lo que ocurre la mayoría de las veces, entonces habrá que utilizar algún método que nos permita resolver el problema entero. Algo que no debemos

hacer, es caer en la tentación de redondear la solución obtenida al PLA a valores enteros y tomarla como válida, pues si bien esto puede ser aceptable en aquellos problemas en el que los valores de las variables son muy grandes y en consecuencia el error puede ser mínimo, en general nos puede generar dos graves `problemas que son: 4

a) La solución obtenida por redondeo no es la óptima e incluso puede ser muy diferente de ella, como ocurre con el siguiente problema

Max F(X) = 4x1 + 3x2

s.a. 2x1 + x2 ≤ 2

3x1 + 4x2 ≤ 6

x1 ≥ 0 , x2 ≥ 0 , {0,1} x1 x2 ∈

Max F(X) = 4x1 + 3x2

s.a. 2x1 + x2 ≤ 2

3x1 + 4x2 ≤ 6

1≥ x1 ≥ 0 , 1≥ x2 ≥ 0

se obtiene como solución

x1 = 0,4 , x2 = 1,2 y F(X) = 5,2.

Redondeo: x1 = 0, x2 = 1, F(X) = 3,

Solución optima: x1 = 1, x2 = 0 , F(X) = 4

b)

Max F(X) = 8x1 + 10x2

s.a. 4x1 + 6x2 ≤ 24

8x1 + 3x2 ≤ 24

x1≥0,x2≥0, x1,x2∈Z+

resolviendo el PLA asociado

Max F(X) = 8x1 + 10x2

s.a. 4x1 + 6x2 ≤ 24

8x1 + 3x2 ≤ 24

x1≥0,x2≥0

Solución x1=2,x2=8/3,F(X)= 128/3

Redondeo al punto x1=2,x2=3, infactible

Redondeo

...