PROGRAMACIÓN LINEAL
UNIVERSIDAD NACIONAL EXPERIMENTAL
“FRANCISCO DE MIRANDA”
COMPLEJO ACADÉMICO “EL SABINO”
DEPARTAMENTO DE GERENCIA
Profesor, Licenciado Javier Bracho
brachojv@[Link]
Origen de la P. L.
Muchas personas clasifican el desarrollo de la
Programación Lineal (PL) entre los avances
científicos más importantes de mediados del
siglo XX, su impacto comienza desde 1947,
cuando [Link] hizo la primera
formulación del método del Simplex
¿Qué es la P.
L.?
La Programación Lineal es una clase de
modelos de programación matemática
destinados a la asignación eficiente de los
recursos limitados en actividades conocidas,
con el objetivo de satisfacer las metas
deseadas, tal como maximizar beneficios o
minimizar costos.
Ejemplos de
aplicación
o Decisiones de mezcla de productos
o Decisiones de fabricación o compra
o Problemas de dietas
o Administración de cartera de valores
o Mezcla de diversos componentes
o Planificación de la Producción
Fases del Estudio de un
Problema de P.L.
o Identificación y definición del problema.
o Formulación del modelo matemático.
o Solución del modelo.
o Análisis de los resultados
o Implementación de los resultados finales
Planteo General de un
Modelo de P.L.
o Definición funcional
o Propiedades en común de un problema de P.L.
o Modelo general
o Otras formas del modelo
Definición funcional
De forma general, los problemas de programación lineal
pueden definirse como el cálculo del máximo o mínimo
de una función lineal de una o varias variables ,
cuando éstas están sujetas a una serie de
restricciones de carácter lineal. De acuerdo con esto,
el objetivo de la programación no es calcular el mayor o
menor valor de una función, sino el mayor o menor
valor de esa función que sea compatible con las
restricciones que pesan sobre sus variables.
Propiedades en común de un
problema de P.L.
o Losproblemas de PL buscan maximizar o minimizar
una cantidad. Función Objetivo (o Función Económica)
de un problema PL.
o La
presencia de Restricciones limita el grado en que
podemos perseguir el objetivo.
o Deben existir diferentes alternativas donde poder
elegir (actividades).
o La función objetivo y las restricciones deben ser
expresadas en términos de ecuaciones o inecuaciones
lineales
Modelo General
Maximizar Z c1 x1 c2 x2 ... cn xn , ( Función Objetivo )
Sujeto a las restriccio nes :
a11 x1 a12 x2 ... a1n x n b1 (Re stric . Funcionales )
a21 x1 a22 x2 ... a2 n x n b2
am1 x1 am 2 x2 ... amn x n bm
y:
x1 0 x2 0 ... x n 0 (Condición No Negativ .)
Forma Estándar para el problema de PL
Modelo General:
Asignación de recursos a
actividades
CONSUMO DE RECURSOS POR UNIDAD DE ACTIVIDAD
Actividad
Cantidad de
recurso
Recurso 1 2 ... n disponible
1 a11 a12 ... a1n b1
2 a21 a22 ... a2n b2
.
.
.
m … .
am1 am2 amn bm
Contribución a c1 c2 cn
...
Z por unidad de
Actividad
Símbolos del Modelo
Z = valor de la medida global de efectividad.
xj = nivel de actividad j (para j = 1, 2,..,n)
cj = incremento en Z que resulta al aumentar una
unidad en el nivel de actividad j.
bi = cantidad de recurso i disponible para asignar a
las actividades (para i = 1, 2,…,m)
aij = cantidad de recurso i consumido por cada
unidad de la actividad j.
Otras formas del modelo
o Minimizar en lugar de maximizar la Función Objetivo
Minimizar Z c1 x1 c2 x2 ... cn xn
o Restricciones funcionales con desigualdades
a11 x1 a12 x2 ... a1n x n b1
o Algunas restricciones en forma de ecuación
a11 x1 a12 x2 ... a1n x n b1
o Las variables de decisión sin la restricción de no
negatividad: x1 no restringida en signo
o Lados derechos negativos: b1 0
Ejemplo: (Juguetes de
Madera Giapetto)
Gepetto S.L., manufactura muñecos y trenes de madera.
Giapetto Woodcarving C.A., manufactura dos tipos de
juguetes de madera: muñecos y trenes.
Cada muñeco:
• Produce un beneficio neto de 3 $.
• Requiere 2 horas de trabajo de acabado. Giapetto quiere
• Requiere 1 hora de trabajo de carpinteria.
Cada tren:
maximizar sus
• Produce un beneficio neto de 2 $. beneficios.
• Requiere 1 hora de trabajo de acabado.
• Requiere 1 hora trabajo de carpinteria.
¿Cuántos muñecos
y cuántos trenes
Cada semana Gepetto puede disponer de:
• Todo el material que necesite. debe fabricar?
• Solamente 100 horas de acabado.
• Solamente 80 horas de carpinteria.
También:
• La demanda de trenes puede ser cualquiera (sin límite).
• La demanda de muñecos es como mucho 40.
Ejemplo:
Este problema es un ejemplo típico de un problema de programación lineal (PPL).
x1 = N° de muñecos producidos a la semana
Variables
de Decisión
x2 = N° de trenes producidos a la semana
Función
Función Objetivo.
Objetivo. En
En cualquier
cualquier PPL,
PPL, El
El objetivo
objetivo de
de Giapetto
Giapetto C.A.C.A. es
es
Función
la
la decisión
decisión aa tomar
tomar eses como elegir
como elegir valores
valores dede xx11 eex
x22 para
para
maximizar
maximizar (normalmente
(normalmente el el maximizar
maximizar 3x3x11 ++ 2x
2x22.. Usaremos
Objetivo beneficio)
beneficio) o
alguna
o minimizar
minimizar (el
(el coste)
coste) de
de
la
la variable
variable zz para
Usaremos
para denotar
denotar el el
Max z = 3x11 + 2x22
alguna función
función dede las
las variables
variables de
de
decisión.
decisión. Esta
Esta función
función aa maximizar
maximizar o o valor
valor de
de la
la función
función objetivo.
objetivo. LaLa
minimizar
minimizar se
se llama
llama función
función objetivo.
objetivo. función
función objetivo
objetivo de de Giapetto
Giapetto es:es:
Ejemplo:
Este problema es un ejemplo típico de un problema de programación lineal (PPL).
Restricciones
SON EN ESTE TAMBIÉN
DESIGUAL PROBLEMA SUELE HABER
LAS RESTRICCION
DADES RESTRICCION ES DE SIGNO
QUE ES VIENEN O NO
LIMITAN DADAS POR NEGATIVIDAD
LA :
LOS
DISPONIBILID
POSIBLES AD DE HORAS x1 ≥
VALORES DE ACABADO
DE LAS Y 0
CARPINTERÍA
VARIABLES Y POR LA x2 ≥
DE DEMANDA DE
DECISIÓN. MUÑECOS. 0
Ejemplo: Restricciones
Cuando x e y crecen, la función objetivo de Giapetto también crece.
Pero no puede crecer indefinidamente porque, para Giapetto, los
valores de x e y están limitados por las siguientes tres restricciones:
RESTR RESTRI RESTRI
ICIÓN CCIÓN CCIÓN
1 2 3
●
No más de 100 horas ●
No más de 80 horas de ●
Limitación de demanda,
de tiempo de acabado tiempo de carpinteria no deben fabricarse más
pueden ser usadas. pueden ser usadas. de 40 muñecos.
2 x1 x1 + x1
matemáticamente + x2 x2
se expresan ≤ ≤ ≤
100
80 40
Formulación Matemática del P.P.L.
Variables de Decisión x1 = N° de muñecos producidos a la semana
x2 = N° de trenes producidos a la semana
Muñeco Tren
Beneficio ($) 3 2 Max z = 3x + 2y (función objetivo)
Acabado (h) 2 1 ≤ 100 2 x + y ≤ 100 (acabado)
Carpintería (h) 1 1 ≤ 80 x + y ≤ 80 (carpinteria)
Demanda ≤ 40 x ≤ 40 (demanda muñecos)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)
Formulación
Matemática del PPL
Para el problema de Giapetto, combinando las
restricciones de signo x ≥ 0 e y ≥ 0 con la función objetivo
y las restricciones, tenemos el siguiente modelo de
optimización:
Max z = 3x + 2y (función objetivo)
Sujeto a (s.a:)
2 x + y ≤ 100 (restricción de acabado)
x + y ≤ 80 (restricción de Carpentaria)
x ≤ 40 (restricción de demanda de muñecos)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)
Práctica I
Resuelva
Ejercicios Propuestos