Post on 29-Jun-2015
ProgramaciónLineal.
Sesión Nro. 07
Objetivos:• Establecer la naturaleza de un
problema de programación lineal.• Introducir la terminología asociada
a él.• Resolver problemas de
programación lineal geométricamente.
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Introducción:
• Programar linealmente, es la asignación de un recurso para la solución de un problema que se presenta.
• La cuantificación de problemas complicados de la vida cotidiana utilizando este enfoque es de la competencia llamada Investigación de Operaciones.
• Se utiliza cuando un problema se puede describir utilizando ecuaciones y desigualdades que son todas lineales.
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Definición:Sea una función lineal en “x” e “y” que tiene la forma:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Donde “a” y “b” son constantes.• Se desea maximizar o minimizar la función bajo
ciertas restricciones (representadas por desigualdades que incluyen “≥” o “≤”).
• Todas las variables sean no negativas.
Por lo tanto: Se le considera un problema de programación Lineal.Función Objetivo: Aquella que se desea maximizar o minimizar.Soluciones factibles o Puntos factibles: Aquellas que tienen un numero infinito de soluciones para el sistema de restricciones.Solución optima: es la solución que da el valor máximo y mínimo de la función objetivo.
Ejemplo Práctico:Problema:Una compañía produce dos tipos de artículos manuales y eléctricos. Cada uno requiere para su fabricación del uso de tres máquinas, A, B y C. La siguiente tabla da la información relacionada con la fabricación de estos artículos:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
A(hrs)
B(hrs)
C(hrs)
Utilidad/Unidad($)
Manual 2 1 1 4
Eléctrico 1 2 1 6
Horas Disponibles 180 160 100
Ejemplo Práctico:
• ¿Cuántos artículos de cada tipo debe producir con el fin de maximizar la utilidad mensual?
• Para resolver el problema establezcamos que “x e “y” son el número de artículos manuales y eléctricos, respectivamente, fabricados en un mes. Ya que el número de artículos producidos no es negativo, entonces:
x ≥ 0 y y ≥ 0Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Ejemplo Práctico:
• Para la maquina A, el tiempo necesario para trabajar sobre x artículos es 2x horas y sobre y artículos es 1y horas: La suma de ambos tiempos no debe ser mayor de 180 horas, expresado matemáticamente tenemos:
• De manera semejante para las maquina B y C, tenemos:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Ejemplo Práctico:
• La utilidad P es una función de x e y, y está dada por la función de utilidad:
• Queremos maximizar la función objetivo:
• Sujeta a las restricciones siguientes:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Ejemplo Práctico:
• La utilidad P es una función de x e y, y está dada por la función de utilidad:
• Queremos maximizar la función objetivo:
• Sujeta a las restricciones siguientes:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Ejemplo Práctico:
• A las ecuaciones (2) y (3) se les llaman condiciones de no negatividad.
• La grafica que muestra la región que satisface de manera simultanea las restricciones de la (2) a la (6) la cual se llama región factible.
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
2x+y=180
x+2y=160
x+y=100
A
B
CD
E
Regiónfactible
Ejemplo Práctico:
• De la ecuación (1), despejamos “y”, encontrando las líneas de isoutilidad y región factible:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
A
B
CD
E
Regiónfactible
Línea de utilidad máxima
P=300
P=600, y=-2/3x+100
Ejemplo Práctico:Encontrando los puntos A y B:Como vemos el punto A es común a la ecuación (5) y (6), entonces:
Donde x = 40 e y = 60.Para encontrar el punto B, este es común a las ecuaciones (4) y (6), entonces:
Donde x = 80 e y = 20.
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Ejemplo Práctico:Los valores de C, D y E, tenemos:C(90, 0)D(0, 0)E(0, 80)Evaluando la función objetivo para cada punto encontrado:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
Valor máximo
Región Factible Vacía:Minimizar la función objetivo: Z = 8x – 3y, sujeta a las siguientes restricciones:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
x+y=5
-x+3y=215
7
Región factible vacía
Región Factible No Acotada:Suponga que la región factible está definida por:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
y = 2
2 Región factibleno acotada
Z = x + y = x + 2
Z=2 Z=6
Z=10 Z=1
4
Ejemplos para la pizarra:
1. Maximizar la función objetivo: Z = 3x + y sujeta a las restricciones:
Facultad de Ciencias Empresariales UCV
Ing. Marco L. Pérez Silva
2. Maximizar la función objetivo: Z = 4,1x – 3,2y sujeta a las restricciones: