Clase # 3

PROGRAMACIN LINEAL EL PROBLEMA DE ASIGNACIN DE RECURSOS

3-1

CONTENIDOEl Problema de Asignacin de Recursos 1. Definicin del Problema y Recoleccin de informacin 2. Formulacin 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. DEFINICIN DEL PROBLEMA El problema de Asignacin de RecursosEjemplo prototipo Capacidad de produccin de las plantas 3 Plantas Fabricacin de productos 2 Productos Tasa de produccin del producto j, Xj Ganancia Z

Problema General Recursos m recursos Actividades n actividades Nivel de la actividad j, Xj Medida global de efectividad Z3-3

RECOLECCIN DE INFORMACINRecurso1 2 Consumo de recursos por unidad de actividad Actividad n 1 2 a11 a21 a12 a22 a1n a2nCantidad de recursos disponibles

b1 b2

mContribucin a Z por unidad de actividad

am1 c1

am2 c2

amn cn

bm

3-4

2. FORMULACIN DEL MODELO DE P. L. 2.1 Definicin de Variables y parmetros Xj = Nivel de la actividad j (para j = 1, 2,......, n).= 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.

cj

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

aij

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

2.2 El Modelo de P.L. en Forma standar

MAX Z = c1X1 + c2X2 + ...........+ cnXnSujeto a:

Funcin 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 xSujeto a

A x b x 03-7

En el ejemplo de la Wyndor:1 0 2 2

c= 3 5

A= 03

x=

x1 x2

b =

4 12 183-8

2.4 Variaciones a la forma standar1. Minimizar en lugar de maximizar la funcin objetivo. objetivo Min Z = c1X1 + c2X2 + ...........+ cnXn 2. Restricciones funcionales del tipo ai1X1 + ai2X2 + .............+ainXn bi para algn i 3. Restricciones funcionales en forma de ecuacin ai1X1 + ai2X2 + .............+ ainXn = bi para algn i 4. Las variables de decisin sin la restriccin de no negatividad. Xj no restringida en signo para algn j3-9

3. SOLUCIONES DE P. L 3.1 Tipo de soluciones

(Estamos acostumbrados a que el trmino solucin signifique respuesta final)SOLUCIN: cualquier conjunto de valores para las variables de decisin (X1, X2, ... Xn), sin importar si es una posibilidad deseable o ni siquiera permitida. Solucin factible: Solucin que cumple con todas las restricciones funcionales y de signo. Solucin no factible: Solucin para la que al menos una restriccin se viola.

3-10

10 9 8 7 6 5 4 3 2 1

x2

soluciones factibles (2,6) solucin factible ptima R2 (4,6) solucin no factible R31 2 3 4 5 6 7 8 9 10

0

x13-11

R1

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

0 soluciones. 1 solucin infinitas solucionesSi tiene 2 soluciones tiene infinitas soluciones (cualquier combinacin convexa de soluciones tambin es una solucin). sigue3-12

Combinacin convexa de n vectores X1, X2, .... Xn: X = 1 X1 + 2X2 + ...........+ n XnDonde:

i0 ,

i i=1

n

=1

Sean 2 soluciones de P. L.: X1, X2Una Combinacin Convexa de ellas: X3 = 1 X1 + 2X2 tambin es solucin de P.L.3-13

REGIN FACTIBLE: Conjunto de todas las soluciones factibles

SOLUCIN FACTIBLE EN UN VRTICE (FEV):

Solucin que se encuentra en un vrtice de la regin factibleVERTICE: PUNTO EXTREMO: P. E..3-14

Soluciones FEV (Puntos Extremos: P.E.)10 9 8 7 6 5 4 3 2 1

x2(2,6)

(0,6)

R2(4,3)

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

0 (0,0)

x13-15

Relacin entre soluciones ptimas y soluciones FEV.

Cualquier problema de P.L que tenga una regin factible acotada y que tenga soluciones factibles debe poseer soluciones FEV, de las cuales al menos una es la solucin ptima3-16

Solucin ptima.

Es la mejor solucin de acuerdo con la funcin objetivoSi el problema tiene una solucin ptima debe ser un FEV. Si el problema tiene mltiples soluciones, debe tener al menos 2 FEV3-17

3.2 Casos EspecialesComo en todo tipo de problema existen casos especiales.

Caso 1. No se tienen soluciones factibles. Caso 2. Se tienen mltiples soluciones ptimas. Caso 3. No se tienen soluciones ptimas.Veamos detalladamente3-18

Caso 1. No se tienen soluciones factibles

Si A x b notiene solucin Si en el ejemplo de la Wyndor, las ganancias netas por semana deben superar los US$ 50000 para que se justifique la implementacin de la produccin de los 2 nuevos productos . La formulacin de este problema sera

3-19

Maximizar Z = 3X1 + 5X2 Sujeto a X1

42X2 12

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

X1 , X2 03-20

10 9 8 7 6 5 4 3 2 1

Graficando las restricciones x2 X =41

X2=6

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

0

x13-21

Caso 2. Mltiples 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 formulacin del problema sera: Maximizar Z = 3X1 + 2X2 Sujeto a: X1

4 2X2 12 3X1 + 2X2 18

X1 , X2 0

3-22

Grficamente10 9 8 7 6 5 4 3 2 1

x2

( 2,6)Las rectas de Isoutilidad son paralelas a la tercera restriccin

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

0

x13-23

R1

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 = 183-24

Caso 3. No se tienen soluciones ptimas

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

Si en el ejemplo de la Wyndor slo la planta 1 tiene restriccin de tiempo, el problema sera: Maximizar Z = 3X1 + 2X2 Sujeto a

4 2X2 12 3X1 + 2X2 18X1

X1 , X2 03-26

Veamos la grfica.

10 9 8 7 6 5 4 3 2 1

x2Regin factible no acotada

0

1 2 3 4 5 6 7 8 9 10

x13-27

R1

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

4.1 Suposicin de proporcionalidad La contribucin de cada actividad a la funcin objetivo Z, es proporcional al nivel de la actividad Xj como lo representa el trmino cjXj en la funcin objetivo. La contribucin de cada actividad al lado izquierdo de las restricciones es proporcional al nivel de la actividad Xj, como lo representa el trmino aij Xj en la funcin 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 funcin objetivo: Z = 3X1 + 2X2Veamos la siguiente tabla3-30

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

Caso 1

Caso 2

Caso 3

0 1 2 3 4

0 3 6 9 12

0 2 5 8 11Costos fijos

0 3 7 12 18

0 3 5 6 6

Rendimiento Rendimiento marginal marginal creciente decreciente3-31

Costos fijosProporcionalidad insatisfecha

Proporcionalidad satisfecha

3-32

Rendimiento marginal crecienteProporcionalidad insatisfecha Proporcionalidad satisfecha

3-33

Rendimiento marginal decrecienteProporcionalidad satisfecha

Proporcionalidad insatisfecha

3-34

4.2 Suposicin de divisibilidad

Los valores de las variables de decisin pueden tomar cualquier valor real. es decir, no necesariamente tienen que ser nmeros enteros.

3-35

4.3 Suposicin de certidumbre.

Esto significa que todos los parmetros cj, aij, bj son conocidos con certeza.

3-36

4.4 Suposicin de aditividad.

Segn esta suposicin, cada funcin de un modelo de P.L (tanto la funcin 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

42X2 12

3X1 + 2X2 18Funciones lineales3-38

Anlisis de aditividad en la funcin objetivo Valor de Z (X1,X2) Aditividad Aditividad insatisfecha satisfecha Caso 1 Caso 2

(1,0) (0,1)

3 5

3 5

3 5 7Z=3X1+5X2 X1X23-39

(1,1)

8

9Z=3X1+5X2 + X1X2

La suposicin de proporcionalidad no prohbe los trminos 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) (0,3)

6 6

6 6

6 6 10.83X1+2X2 0.1X12X23-41

(2,3)

12

153X1+2X2+ 0.5X1X2

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

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