Tecnico

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
• Capacidad de producción de las plantas • 3 Plantas • Fabricación de productos •2 Productos •Tasa de producción del producto j, Xj •Ganancia Z

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

RECOLECCIÓN DE INFORMACIÓNRecurso
1 2 Consumo de recursos por unidad de actividad Actividad n 1 2 a11 a21 a12 a22 a1n a2n
Cantidad de recursos disponibles

b1 b2

m
Contribución a Z por unidad de actividad

am1 c1

am2 c2

amn cn

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).
= Incremento en Z que resulta alaumentar 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 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 ejemplode la Wyndor:
1 0 2 2

c= 3 5

A= 0
3

x=

x1 x2

b =

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 deseableo 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

10 9 8 7 6 5 4 3 2 1

x2

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

0

x1
3-11

R1

Un modelo de P. L. de nvariables 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 ,

Σ λi i=1

n

=1

Sean 2 soluciones de P. L.: X1, X2
Una Combinación Convexa deellas: 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.)
10 9 8 7 6 5 4 3 2 1

x2
(2,6)

(0,6)

R2
(4,3)

R3
1 2 3 4 5 6 7 8 9 10 R1...