Programacion Lineal, Asignacion De Recursos 91552

Clase # 3

PROGRAMACIÒN LINEAL EL PROBLEMA DE ASIGNACIÓN DE RECURSOS

3-1

CONTENIDO El Problema de Asignación de Recursos 1. Definición del Problema y Recolección de información 2. Formulación del Modelo 2.1 Forma éstandar 2.2 Forma matricial 2.3 Variaciones a la forma éstandar 3. Soluciones de P. L. 3.1 Tipo de soluciones 3.2 Casos especiales 4. Suposiciones de la P. L.

3-2

1. DEFINICIÓN DEL PROBLEMA El problema de Asignación de Recursos Ejemplo prototipo

Problema General

• Capacidad de producción de las plantas

• Recursos

• 3 Plantas

• m recursos

• Fabricación de productos

• Actividades

•2 Productos

• n actividades

•Tasa de producción del producto j, Xj •Ganancia Z

•Nivel de la actividad j, Xj •Medida global de efectividad Z 3-3

RECOLECCIÓN DE INFORMACIÓN Recurso

Consumo de recursos por unidad de actividad Actividad n 1 2

1

a11

a12

2

a21

a22

a1n a2n

m

am1

am2

amn

Contribución a Z por unidad de actividad

c1

c2

cn

Cantidad de recursos disponibles

b1 b2

bm

3-4

2. FORMULACIÓN DEL MODELO DE P. L. 2.1 Definición de Variables y parámetros Xj = Nivel de la actividad j (para j = 1, 2,......, n).

cj

= Incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j (costo o utilidad) Z = Valor de la medida global de efectividad.

bi = Cantidad del recurso i disponible para asignar a las actividades (i =1,2,..., m) (recurso o requerimiento)

aij

= Cantidad del recurso i consumido por cada unidad de la actividad j. (Coeficientes tecnológicos) 3-5

2.2 El Modelo de P.L. en Forma Éstandar

MAX Z = c1X1 + c2X2 + ...........+ cnXn Sujeto a:

Función objetivo

(restricciones funcionales) a11X1 + a12X2 + .............+ a1nXn ≤ b1 a21X1 + a22X2 + .............+ a2nXn ≤ b2 am1X1 +am2X2 + .............+ amnXn ≤ bm (restricciones de signo de las variablers) Xi ≥ 0 para i = 1,2,....,n

3-6

2.3 El Modelo en Forma matricial

Max Z = c x Sujeto a

A x ≤ b x ≥ 0 3-7

En el ejemplo de la Wyndor:

c= 3 5

1

A= 0 3

x=

x1 x2

b =

0 2 2

4 12 18 3-8

2.4 Variaciones a la forma éstandar 1. Minimizar en lugar de maximizar la función objetivo. objetivo Min Z = c1X1 + c2X2 + ...........+ cnXn 2. Restricciones funcionales del tipo ≥ ai1X1 + ai2X2 + .............+ainXn ≥ bi para algún i 3. Restricciones funcionales en forma de ecuación ai1X1 + ai2X2 + .............+ ainXn = bi para algún i 4. Las variables de decisión sin la restricción de no negatividad. Xj no restringida en signo para algún j 3-9

3. SOLUCIONES DE P. L 3.1 Tipo de soluciones

(Estamos acostumbrados a que el término solución signifique respuesta final) SOLUCIÓN: cualquier conjunto de valores para las variables de decisión (X1, X2, ... Xn), sin importar si es una posibilidad deseable o ni siquiera permitida. ¾ Solución factible: Solución que cumple con todas las restricciones funcionales y de signo. ¾Solución no factible: Solución para la que al menos una restricción se viola.

3-10

soluciones factibles

x2

10 9 8 7 6 5 4 3 2 1

0

(2,6) solución factible óptima R2 (4,6) solución no factible R3 1 2 3 4 5 6 7 8 9 10

x1

R1 3-11

Un modelo de P. L. de n variables tiene:

¾ 0 soluciones. ¾ 1 solución ¾ infinitas soluciones Si tiene 2 soluciones tiene infinitas soluciones (cualquier combinación convexa de soluciones también es una solución). sigue 3-12

Combinación convexa de n vectores X1, X2, .... Xn: X = λ 1 X1 + λ 2X2 + ...........+ λ n Xn Donde:

λi≥0 ,

n

Σi=1 λ i

=1

Sean 2 soluciones de P. L.: X1, X2 Una Combinación Convexa de ellas: X3 = λ 1 X1 + λ 2X2 también es solución de P.L. 3-13

REGIÓN FACTIBLE: Conjunto de todas las soluciones factibles

SOLUCIÓN FACTIBLE EN UN VÉRTICE (FEV):

Solución que se encuentra en un vértice de la región factible VERTICE: PUNTO EXTREMO: P. E.. 3-14

Soluciones FEV (Puntos Extremos: P.E.)

x2

(0,6)

10 9 8 7 6 5 4 3 2 1

0 (0,0)

(2,6)

R2 (4,3)

R3 1 2 3 4 5 6 7 8 9 10 R1 (4,0)

x1 3-15

Relación entre soluciones óptimas y soluciones FEV.

Cualquier problema de P.L que tenga una región factible acotada y que tenga soluciones factibles debe poseer soluciones FEV, de las cuales al menos una es la solución óptima 3-16

Solución óptima.

Es la mejor solución de acuerdo con la función objetivo ¾ Si el problema tiene una solución óptima debe ser un FEV. ¾Si el problema tiene múltiples soluciones, debe tener al menos 2 FEV 3-17

3.2 Casos Especiales Como en todo tipo de problema existen casos especiales.

Caso 1. No se tienen soluciones factibles. Caso 2. Se tienen múltiples soluciones óptimas. Caso 3. No se tienen soluciones óptimas. Veamos detalladamente 3-18

Caso 1. No se tienen soluciones factibles

Si A x ≤ b no tiene solución Si en el ejemplo de la Wyndor, las ganancias netas por semana deben superar los US$ 50000 para que se justifique la implementación de la producción de los 2 nuevos productos . La formulación de este problema sería

3-19

Maximizar Z = 3X1 + 5X2 Sujeto a

X1

≤4 2X2 ≤ 12

3X1 + 2X2 ≤ 18 3X1 + 5X2 ≥ 50

X1 , X2 ≥ 0 3-20

Graficando las restricciones x2 X =4

10 9 8 7 6 5 4 3 2 1

0

1

X2=6

3X1+5X2=50 3X1+2X2=18 1 2 3 4 5 6 7 8 9 10

x1 3-21

Caso 2. Múltiples soluciones óptimas Si en el ejemplo de la Wyndor, el producto 2 no da una ganancia neta de US$ 5000 sino de US$ 2000, la nueva formulación del problema sería: Maximizar Z = 3X1 + 2X2 Sujeto a:

≤4 2X2 ≤ 12 3X1 + 2X2 ≤ 18

X1

X1 , X2 ≥ 0

3-22

Gráficamente

( 2,6)

x2

10 9 8 7 6 5 4 3 2 1

0

Las rectas de Isoutilidad son paralelas a la tercera restricción

R2 (4,3) R3 1 2 3 4 5 6 7 8 9 10

x1

R1 3-23

Es indiferente elegir cualquiera de los puntos (2,6) o (4,3), o cualquier punto en el segmento de recta entre éstos, ya que producen el mismo nivel de Z, que en este caso es Z = 18 3-24

Caso 3. No se tienen soluciones óptimas

1) No se tienen soluciones factibles. 2) Las restricciones no impiden que el valor de la función objetivo mejore indefinidamente en la dirección favorable (región factible no acotada) OJO: Cuando esto ocurre es probable que haya un error en la formulación del problema 3-25

Si en el ejemplo de la Wyndor sólo la planta 1 tiene restricción de tiempo, el problema sería: Maximizar Z = 3X1 + 2X2 Sujeto a

≤4 2X2 ≤ 12 3X1 + 2X2 ≤ 18 X1

X1 , X2 ≥ 0 Veamos la gráfica. 3-26

x2

10 9 8 7 6 5 4 3 2 1

0

Región factible no acotada

1 2 3 4 5 6 7 8 9 10

x1

R1 3-27

4. SUPOSICIONES DEL MODELO DE P. L. 4.1 Suposición de proporcionalidad. (en la F. O. y en las restricciones) 4.2 Suposición de divisibilidad. (Variables reales) 4.3 Suposición de certidumbre. (en los valores de los parámetros) 4.4 Suposición de aditividad. (en la F. O. y en las restricciones) 3-28

4.1 Suposición de proporcionalidad ¾ La contribución de cada actividad a la función objetivo Z, es proporcional al nivel de la actividad Xj como lo representa el término cjXj en la función objetivo. ¾La contribución de cada actividad al lado izquierdo de las restricciones es proporcional al nivel de la actividad Xj, como lo representa el término aij Xj en la función objetivo. 3-29

En el ejemplo de la Wyndor: Por cada lote del producto 1 que se fabrique, la ganancia es US$ 3000. Esto es, en la función objetivo: Z = 3X1 + 2X2 Veamos la siguiente tabla 3-30

Ganancia del producto 1 (miles US$ por semana) Nivel Proporcionalidad satisfecha

Proporcionalidad insatisfecha

Caso 1

Caso 2

Caso 3

0

0

0

0

0

1

3

2

3

3

2

6

5

7

5

3 4

9 12

8 11

12 18

6 6

Costos fijos

Rendimiento Rendimiento marginal marginal creciente decreciente 3-31

Costos fijos Proporcionalidad insatisfecha

Proporcionalidad satisfecha

3-32

Rendimiento marginal creciente Proporcionalidad insatisfecha Proporcionalidad satisfecha

3-33

Rendimiento marginal decreciente Proporcionalidad satisfecha

Proporcionalidad insatisfecha

3-34

4.2 Suposición de divisibilidad

Los valores de las variables de decisión pueden tomar cualquier valor real. es decir, no necesariamente tienen que ser números enteros.

3-35

4.3 Suposición de certidumbre.

Esto significa que todos los parámetros cj, aij, bj son conocidos con certeza.

3-36

4.4 Suposición de aditividad.

Según esta suposición, cada función de un modelo de P.L (tanto la función objetivo como el lado izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de cada una de las actividades involucradas.

En el Ejemplo de la Wyndor: 3-37

Maximizar Z = 3X1 + 2X2 Sujeto a X1

≤4 2X2 ≤ 12

3X1 + 2X2 ≤ 18 Funciones lineales 3-38

Análisis de aditividad en la función objetivo Valor de Z (X1,X2) Aditividad Aditividad insatisfecha satisfecha Caso 1 Caso 2

(1,0)

3

3

3

(0,1)

5

5

5

(1,1)

8

9

7

Z=3X1+5X2 + X1X2

Z=3X1+5X2 X1X2 3-39

La suposición de proporcionalidad no prohíbe los términos de productos cruzados. Z = 3X1+5X2+ X1X2 Productos complementarios Z = 3X1+5X2 -X1X2 Productos competitivos

3-40

En el lado izquierdo de las restricciones funcionales Valor del lado izquierdo (X1,X2) Aditividad Aditividad insatisfecha satisfecha Caso 1 Caso 2

(2,0)

6

6

6

(0,3)

6

6

6

(2,3)

12

15

10.8

3X1+2X2+ 0.5X1X2

3X1+2X2 0.1X12X2 3-41

3X1+2X2+ 0.5X1X2 Recursos que compiten entre sí

3X1+2X2 - 0.1X12X2 Recursos se ayudan para consumir menos 3-42