Métodos de optimización

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