Métodos de optimización
II. PROGRAMACIÓN LINEAL
2.1 DEFINICIÓN DE PROGRAMACIÓN LINEAL
Técnica matemática para determinar la mejor asignación de los recursos limitados de
una organización para el desarrollo o producción de bienes y servicios en una forma
óptima. La programación lineal involucra la planeación de las actividades para obtener
un resultado óptimo, esto es, el resultado quemejor alcance la meta especificada
entre todas las alternativas factibles.
2.2 REQUERIMIENTOS DE UN MODELO DE PROGRAMACIÓN LINEAL
Definir claramente una función objetivo en forma matemática.
Las restricciones o limitaciones se expresan en forma matemática a través de
ecuaciones o desigualdades.
Las ecuaciones y desigualdades deben describir el problema en forma lineal.
Las variables del problema deben interrelacionarse.
Debe existir un suministro limitado de recursos.
2.3 FORMULACIÓN CANÓNICA DE LA PROGRAMACIÓN LINEAL
Características
Función Objetivo: Maximizar Z
Restricciones funcionales: Tipo menor o igual
Cj : Utilidad o ganancia unitaria
Función Objetivo: Maximizar Z = C1X1 + C2X2 + C3X3 + ..… + Cn Xn
sujeta a:
a11X1 + a12X2 + a13X3 +..… + a1n Xn b1
a21X1 + a22X2 + a23X3 + ..… + a2n Xn b2
a31X1 + a32X2 + a33X3 + ..… + a3n Xn b3
:
:
:
:
:
am1X1 + am2X2 + am3X3 + ..… + amn Xn bm
X1, X2 , X3 , ..….... Xn 0
UES \ FIA \ EII \ IOP115, MOP115
1
La formulación anterior puede presentarse en el siguiente cuadro de datos:
Actividades
1
2
3
. . .
n
Recursos
Disponibilidad
derecursos
1
a11
a12
a13
. . .
a1n
b1
2
a21
a22
a23
. . .
a2n
b2
3
a31
a32
a33
. . .
a3n
b3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
am1
am2
am3
. . .
amn
bm
Utilidades
c1
c2
c3
. . .
cn
Variables de
X1
X2
X3
. . .
Xn
decisiónTERMINOLOGÍA
m = Recursos limitados.
n = Actividades competitivas para ubicar recursos (actividades que compiten
entre sí por los recursos) .
Xj = Cantidad de cada actividad “j” (variables de decisión o incógnitas del
problema).
cj = Ganancia unitaria para cada actividad “j”.
bi = Cantidad del recurso “i” disponible.
aij= La cantidad consumida del recurso “i” por cada unidad de actividad“j”.
Z = Medida de efectividad (Función Objetivo).
El número de restricciones funcionales depende del número de recursos (m). El
número de restricciones de no negatividad está en función del número de actividades
(n). Por lo tanto, el número de restricciones funcionales y de no negatividad es igual a
m+n. Pueden existir otros tipos de restricciones, dependiendo de las condiciones delproblema a resolver.
UES \ FIA \ EII \ IOP115, MOP115
2
2.4 FORMAS NO CANÓNICAS
Función Objetivo: Minimizar Z
Restricciones funcionales: Tipo mayor o igual
Cj : Costo unitario
Función Objetivo: Maximizar Z
Restricciones funcionales: Tipo menor o igual, mayor o igual o de igualdad
Cj : Utilidad o ganancia unitaria
Función Objetivo: Minimizar Z
Restriccionesfuncionales: Tipo menor o igual, mayor o igual o de igualdad
Cj : Costo unitario
2.5 PASOS PARA CONSTRUIR EL MODELO DE PL
1. Identificar los recursos y las actividades en el problema
2. Definir las variables de decisión (qué es lo que busca determinar el modelo).
3. Definir una función objetivo (el objetivo que necesita alcanzarse para
determinar la solución óptima).
4. Definir las restricciones(limitaciones que deben imponerse a las variables).
EJEMPLOS
1. Una fábrica elabora tres diferentes artículos que son procesados en igual número
de etapas. El tiempo requerido (minutos) para cada unidad en el proceso de los
tres productos y la capacidad de trabajo es como sigue:
Producto
Producto
Producto
Capacidad por
1
2
3
etapa (min/día)
Etapa 1
1
2...
Regístrate para leer el documento completo.