Programación

separable

pcinelop@[Link]
DEFINICIÓN

 La programación separable permite

aproximar ciertos MPNL a Modelos de
Programación Lineales, obteniendo una
solución óptima aproximada.
 Sólo se aplica esta técnica cuando en un
MPNL las variables de decisión aparecen en
términos separados tanto en la función
objetivo como en las restricciones.
POR EJEMPLO, ESTE MPNL NO ES SEPARABLE:

 Porque las expresiones

matemáticas no lineales de color
rojo están en función de más de
una variable de decisión.
PERO ESTE MPNL SÍ ES SEPARABLE:

 Porque todas las expresiones

matemáticas no lineales del
modelo (color azul) se expresan
en función de una sola variable.
¿CÓMO SE LOGRA DICHA APROXIMACIÓN?

 Se logra mediante la sustitución de las expresiones no lineales por

funciones lineales por tramos.
 La sustitución puede ser de dos tipos:
 Sustitución aproximada.
 Sustitución exacta.
SUSTITUCIÓN APROXIMADA

 Se reemplazan las expresiones no  Ejemplo: Resolver el siguiente MPNL

lineales por funciones lineales por aplicando programación separable:
tramos de manera aproximada.
 A menor amplitud que posean los
tramos, mayor precisión; pero también
el modelo resultante se hace más
grande.
SOLUCIÓN

 Son dos las expresiones no lineales: x12 y x22

 Analizando la primera restricción, el máximo valor que podría tomar:
 x1: 2500.5 = 15.81  16
 x2: (250 / 2)0.5 = 11.18  12

 Ambos valores máximos satisfacen también la segunda restricción (no exceden de

20)
 Luego, se efectúa la siguiente sustitución:
 X12 = F1
 X22 = F2
SE APROXIMA CADA EXPRESIÓN NO LINEAL A FUNCIONES
LINEALES POR TRAMOS:

 Arbitrariamente, se emplearán 4 tramos.

 Para cada tramo, se calculará la pendiente:

F1 = x12 Aproximación de F1
DE IGUAL MANERA, PARA F2 = X22

F2 = x22 Aproximación de F2
MODELAMIENTO DE LAS FUNCIONES LINEALES POR
TRAMOS:

 Se asigna una variable auxiliar por cada tramo:

 A1, A2, A3,A4 : Representan a cada tramo de la recta que contiene a x1. En consecuencia:
 x1 = A1 + A2 + A3 + A4
 A1 ≤ 4, A2 ≤ 4, A3 ≤ 4, A4 ≤ 4
 Por ejemplo: Si x1 toma el valor de 9, entonces: A1 = 4, A2 = 4,A3 = 1 y A4 = 0

 B1, B2, B3, B4 : Representan a cada tramo de la recta que contiene a x2. En consecuencia:
 x2 = B1 + B2 + B3 + B4
 B1 ≤ 3, B2 ≤ 3, B3 ≤ 3, B4 ≤ 3
MODELAMIENTO DE LAS FUNCIONES LINEALES POR
TRAMOS:

 F1 se expresa en función de las variables A1, A2, A3,A4 y de las

pendientes obtenidas en cada tramo:
 F1 = 4A1 + 12A2 + 20A3 + 28A4

 F2 se expresa en función de las variables B1, B2, B3, B4 y de las

pendientes obtenidas en cada tramo:
 F2 = 3B1 + 9B2 + 15B3 + 21B4
ENTONCES EL MODELO CAMBIA DE LA SIGUIENTE
MANERA:

Modelo Linealizado
Modelo No Lineal Original con sustitución aproximada
𝑴𝒂𝒙 𝒁 = 𝟑𝟎𝒙𝟏 + 𝟑𝟓𝒙𝟐 − 𝟐𝑭𝟏 − 𝟑𝑭𝟐
𝑺𝒖𝒋𝒆𝒕𝒐 𝒂:
𝑭𝟏 + 𝟐𝑭𝟐 ≤ 𝟐𝟓𝟎
𝒙𝟏 + 𝒙𝟐 ≤ 𝟐𝟎
𝑭𝟏 = 𝟒𝑨𝟏 + 𝟏𝟐𝑨𝟐 + 𝟐𝟎𝑨𝟑 + 𝟐𝟖𝑨𝟒
𝑭𝟐 = 𝟑𝑩𝟏 + 𝟗𝑩𝟐 + 𝟏𝟓𝑩𝟑 + 𝟐𝟏𝑩𝟒
𝒙𝟏 = 𝑨𝟏 + 𝑨𝟐 + 𝑨𝟑 + 𝑨𝟒
𝑨𝟏 ≤ 𝟒 𝑨𝟐 ≤ 𝟒 𝑨𝟑 ≤ 𝟒 𝑨𝟒 ≤ 𝟒
𝒙𝟐 = 𝑩𝟏 + 𝑩𝟐 + 𝑩𝟑 + 𝑩𝟒
𝑩𝟏 ≤ 𝟑 𝑩𝟐 ≤ 𝟑 𝑩𝟑 ≤ 𝟑 𝑩𝟒 ≤ 𝟑
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎
ANÁLISIS DE LA SOLUCIÓN ÓPTIMA DEL MODELO NO
LINEAL ORIGINAL

 La solución óptima que LINGO arroja

del modelo no lineal (originalmente
formulado) es:
 Óptimo Local: 214.5833
 Valores:
 x1 = 7.5 ; x2 = 5.8333
 La región factible del modelo es convexa y la
función objetivo es una función cóncava; por
lo tanto esta solución es también global.
ANÁLISIS DE LA SOLUCIÓN ÓPTIMA DEL MODELO LINEALIZADO:

 La solución óptima que LINGO arroja del

modelo “linealizado” es:
 Óptimo Global: 214
 Valores: x1 = 8 ; x2 = 6
 LINGO le da la categoría de Global porque ha
resuelto un modelo lineal al fin y al cabo; pero
en realidad es una aproximación a la
verdadera solución debido a que las
expresiones no lineales han sido sustituidas
de manera aproximada a funciones lineales
por tramos.
SUSTITUCIÓN EXACTA

 Puede darse el caso que todas las expresiones no lineales puedan ser sustituidas
de manera exacta por funciones lineales por tramos.
 En ciertos casos, se emplearán variables auxiliares binarias para que el software calcule
correctamente las expresiones no lineales.
 Esto ocurre cuando en el enunciado del caso a optimizar aparecen de manera
explícita funciones lineales por tramos.
PROCEDIMIENTO GENERAL DE SOLUCIÓN:

1) Identificar las variables de decisión.

2) Graficar cada función lineal por tramos. Para cada una de ellas, se asigna:
 Al Eje de las Abscisas, una variable de decisión o una combinación lineal de variables de decisión; y a cada tramo una
variable auxiliar.
 Al Eje de las Ordenadas, una variable auxiliar.

3) Si una función lineal por tramos es continua, se debe determinar si es necesario o no el uso de variables
binarias para representarla correctamente. Las funciones que son ni cóncavas ni convexas y las
discontinuas requieren variables binarias.
4) Se construyen las expresiones matemáticas separables que representan a dichas funciones.
5) Se construye el modelo matemático de optimización, incorporando las expresiones construidas en el
paso anterior
CASO 1:
 Una empresa produce dos tipos de productos: P1 y P2. Se dispone de 120 horas hombre (H-H) y todo
lo que se produce se va a vender. la información técnica económica se muestra en la tabla siguiente:

Precio de Costo de venta Venta Requerimiento de

Producto
venta ($/t) ($/t) máxima (t) mano de obra (H-H/t)
P1 (*) 40 60 1
P2 120 (**) 50 2
• (*) El precio de venta del producto P1 es: 100 $/t para las primeras 10 t, 98 $/t para las
siguientes 15 t y 96 $/t para las siguientes toneladas.
• (**) El costo de venta del producto P2 es: 40 $/t para las primeras 10 t, 45 $/t para las
siguientes 10 t y 50 $/t para las siguientes toneladas.

 Se pide determinar el mix de producción que maximice la utilidad total.

SOLUCIÓN:
 Variables de decisión:
 X1, X2 : Cantidad (en t) a producir del producto P1 y P2, respectivamente.

Gráfica de la función de ingreso total de P1

• La función lineal por tramos es continua, por lo
tanto hay que determinar si es necesario el uso de
variables binarias.
• En este caso, no es necesario el uso de variables
binarias porque el mayor precio de venta lo tiene
el primer intervalo, el segundo intervalo tiene el
siguiente mayor precio de venta y el tercer
intervalo tiene el menor precio de venta.
• Es decir, los precios de venta están en orden
decreciente
CONSTRUYENDO LAS EXPRESIONES SEPARABLES DEL
INGRESO TOTAL DE P1

Ecuación del eje de las abscisas: X1 = A1 + A2 + A3

Ecuación del eje de las ordenadas: Ingreso = 100A1 + 98A2 + 96A3

A1 ≤ (10 – 0)

Amplitud máxima de cada intervalo: A2 ≤ (25 – 10)

A3 ≤ 99999
CONSTRUYENDO LAS EXPRESIONES SEPARABLES DEL INGRESO
TOTAL DE P2

 La función lineal por tramos es continua, por lo Gráfica de la función de costo total de P2
tanto hay que determinar si es necesario el uso
de variables binarias.
 En este caso, tampoco es necesario el uso de
variables binarias porque el menor costo
unitario lo tiene el primer intervalo, el segundo
intervalo tiene el siguiente menor costo
unitario y el tercer intervalo tiene el
subsiguiente menor costo unitario.
 Es decir, los costos unitarios están en
orden creciente.
CONSTRUYENDO LAS EXPRESIONES SEPARABLES DEL COSTO
TOTAL DE P2

Ecuación del eje de las abscisas: X2 = A4 + A5 + A6

Ecuación del eje de las ordenadas: Costo = 40A4 + 45A5 + 50A6

A4 ≤ (10 – 0)

Amplitud máxima de cada intervalo: A5 ≤ (20 – 10)

A6 ≤ 99999
CONSTRUYENDO EL MODELO DE OPTIMIZACIÓN
MATEMÁTICA:
Max Z = Ingreso + 120X2 – (40X1 + Costo)
Sujeto a:
Venta máxima de cada producto: Costo total total de X2:
X1 ≤ 60 X2 = A4 + A5 + A6
X2 ≤ 50 Costo = 40A4 + 45A5 + 50A6
Disponibilidad de mano de obra: A4 ≤ (10 – 0)
X1 + 2X2 ≤ 120 A5 ≤ (20 – 10)
Ingreso total de X1: A6 ≤ 99999
X1 = A1 + A2 + A3 No negatividad:
X1, X2 ≥ 0
Ingreso = 100A1 + 98A2 + 96A3
A1 ≤ (10 – 0)
A2 ≤ (25 – 10)
A3 ≤ 99999
MODELO Y REPORTE DE LA SOLUCIÓN ÓPTIMA EN LINGO

Se debe producir 60t de P1 y 30t de

P2, la máxima utilidad será $5680
CASO 2:

 Una empresa produce dos tipos de productos: P1 y P2. Se dispone de 120 horas hombre (H-H) y todo
lo que se produce se va a vender. la información técnica económica se muestra en la tabla siguiente:

Precio de Costo de venta Venta Requerimiento de

Producto
venta ($/t) ($/t) máxima (t) mano de obra (H-H/t)
P1 (*) 40 60 1
P2 120 (**) 50 2
• (*) El precio de venta del producto P1 es: 100 $/t si se vende hasta 10 t, 98 $/t si se venden
más de 10t hasta 25t; y 96 $/t si se venden más de 25t.
• (**) El costo de venta del producto P2 es: 50 $/t para las primeras 10 t, 45 $/t para las
siguientes 10 t y 40 $/t para las siguientes toneladas.

 Se pide determinar el mix de producción que maximice la utilidad total.

SOLUCIÓN:
 Variables de decisión:
 X1, X2 : Cantidad (en t) a producir del producto P1 y P2, respectivamente.

Gráfica de la función de ingreso total de P1

• Por la manera como se describe la función del

ingreso total de P1, la función lineal por
tramos es discontinua, por lo tanto es
necesario el uso de variables binarias (W1,
W2, W3).
• De no hacerlo, sería igual que el caso 1.
 CONSTRUYENDO LAS EXPRESIONES SEPARABLES DEL
INGRESO TOTAL DE P1

Ecuación del eje de las abscisas: X1 = A1 + A2 + A3 + 0W1 + 10W2 + 25W3

Ecuación del eje de las ordenadas: Ingreso = 100A1 + 98A2 + 96A3

+ 0W1 + 980W2 + 2400W3

Sólo una variable binaria debe activarse: W1 + W2 + W3 = 1

A1 ≤ (10 – 0)W1

Amplitud máxima de cada intervalo: A2 ≤ (25 – 10) W2

A3 ≤ 99999 W3

Declaración de binarias: W1,W2,W3 es binaria.

CONSTRUYENDO LAS EXPRESIONES SEPARABLES DEL INGRESO
TOTAL DE P2

Gráfica de la función de costo total de P2

 La función lineal por tramos es continua, por
lo tanto hay que determinar si es necesario
el uso de variables binarias.
 En este caso, es necesario el uso de
variables binarias (W4, W5, W6) porque
los costos unitarios están en orden
creciente.
 De no hacerlo, el modelo aplicará el menor
costo: 40 $/t a cualquier valor que tome X2,
lo cual no es correcto.
 CONSTRUYENDO LAS EXPRESIONES SEPARABLES DEL COSTO
TOTAL DE P2

Ecuación del eje de las abscisas: X2 = A4 + A5 + A6 + 0W4 + 10W5 + 20W6

Ecuación del eje de las ordenadas: Costo = 50A4 + 45A5 + 40A6

+ 0W4 + 500W5 + 950W6

Sólo una variable binaria debe activarse: W4 + W5 + W6 = 1

A4 ≤ (10 – 0)W4

Amplitud máxima de cada intervalo: A5 ≤ (20 – 10) W5

A6 ≤ 99999 W6

Declaración de binarias: W4,W5,W6 es binaria.

CONSTRUYENDO EL MODELO DE OPTIMIZACIÓN
MATEMÁTICA:
Max Z = Ingreso + 120X2 – (40X1 + Costo)
Sujeto a:
Venta máxima de cada producto: Costo total de P2:
X1 ≤ 60 X2 = A4 + A5 + A6 + 0W4
X2 ≤ 50 + 10W5 + 20W6
Disponibilidad de mano de obra: Costo = 50A4 + 45A5 + 40A6
X1 + 2X2 ≤ 120 + 0W4 + 500W5 + 950W6
Ingreso total de P1 W4 + W5 + W6 = 1
X1 = A1 + A2 + A3 + 0W1 + 10W2 + 25W3 A4 ≤ (10 – 0)W4
Ingreso = 100A1 + 98A2 + 96A3 + 0W1 + 980W2 + 2400W3 A5 ≤ (20 – 10) W5
W1 + W2 + W3 = 1 A6 ≤ 99999 W6
A1 ≤ (10 – 0)W1 W4,W5,W6 es binaria.
A2 ≤ (25 – 10) W2 X1, X2 ≥ 0
A3 ≤ 99999 W3
W1,W2,W3 es binaria.
MODELO Y REPORTE DE LA SOLUCIÓN ÓPTIMA EN LINGO

Se debe producir 60t de P1 y 30t de P2, la

máxima utilidad será $5610