1. No category

Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
Guía 1: Modelamiento de Programación no lineal Estructura de un modelo no lineal (PPNL) Un problema no lineal es un problema de programación matemática donde la función objetivo o alguna restricción es no lineal. Forma general de un PPNL: 𝑀𝑎𝑥 𝑚𝑖𝑛 𝑓(𝑥) , 𝑥+ , … , 𝑥-.) , 𝑥- ) 𝑠. 𝑎. 𝑔) 𝑥) , 𝑥+ , … , 𝑥-.) , 𝑥- ≤, =, ≥ 𝑏) 𝑔+ 𝑥) , 𝑥+ , … , 𝑥-.) , 𝑥- ≤, =, ≥ 𝑏+ ⋮ 𝑔9 𝑥) , 𝑥+ , … , 𝑥-.) , 𝑥- ≤, =, ≥ 𝑏: Donde 𝑓 (𝑥) , 𝑥+ , … , 𝑥-.) , 𝑥- ) es la función objetivo del modelo no lineal considerando nuestras variables de decisión, y 𝑔: 𝑥) , 𝑥+ , … , 𝑥-.) , 𝑥- ≤, =, ≥ 𝑏: , son las restricciones del problema que pueden ser de igualdad o desigualdad. Ejemplos Ejemplo 1 Un joven ingeniero de la Universidad Mayor, prepara para una compañía un nuevo fertilizante hecho a partir de dos materias primas. Al combinar estas materias primas (𝑥) , 𝑥+ ), la cantidad de fertilizante que se obtiene viene dado por 𝑄 = 4𝑥) + 2𝑥+ − 0.5𝑥)+ − 0.25𝑥++ . Se requieren 480 pesos por unidad de materia prima 1 y 300 pesos por cada unidad de materia prima 2 que se empleen en la fabricación del fertilizante (en estas cantidades se incluyen los costos de las materias primas y los costos de producción). Si la compañía dispone de 24.000 pesos para la producción de materias primas, plantear el problema para determinar la cantidad de materia prima de forma que se maximice la cantidad de fertilizante. Ejemplo 2 Una empresa produce ampolletas de ahorro energético y ha firmado un contrato para suministrar al menos 150 unidades en tres meses, 50 unidades al final del primer mes, 50 al final del segundo y 50 al final del tercero. El coste de producir una cantidad de ampolletas en cualquier mes es su cuadrado. La empresa puede producir si lo desea más ampolletas de los que necesita en cualquier mes y guardarlos para el siguiente, siendo el coste de almacenaje de 12 euros por unidad al mes. Suponiendo que no hay inventario inicial, formular el modelo adecuado para determinar el número de frigoríficos que deben producirse cada mes, para minimizar el coste total. Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
Ejemplo 3 Una compañía petrolífera debe determinar cuántos barriles de petróleo hay que extraer en los próximos dos años. Si la compañía extrae 𝑥) millones de barriles durante un año, se pondría vender cada barril a 30 − 𝑥) euros. Si extrae 𝑥+ millones de barril durante el segundo año, se podrá vender cada barril a 35 − 𝑥+ euros. El costo para extraer 𝑥) millones de barriles en el primer año es de 𝑥)+ millones de euros y el costo para extraer 𝑥+ millones de barriles durante el segundo año es de 2𝑥++ millones de euros. Se puede obtener como máximo un total de 20 millones de barriles de petróleo, y se puede gastar como máximo 250 millones de euros en la extracción. Formular el P.N.L. para ayudar a la empresa a maximizar sus ganancias para los próximos dos años. Ejemplo 4 Una compañía de electricidad planea gastar 10000 dólares en publicidad. Se sabe que un minuto de publicidad en televisión cuesta 3000 dólares y 1000 dólares en la radio. Si la empresa compra 𝑥) minutos de publicidad en televisión y 𝑥+ minutos en la radio, su ingreso, en dólares, están dado por −2𝑥)+ – 𝑥++ + 𝑥) 𝑥+ + 8𝑥) + 3𝑥+ . ¿Cómo puede la empresa maximizar sus ingresos? Desarrollo matemático: Ejemplo 1: Las variables de decisión del problema: 𝑥) ≔ cantidad de materia prima 1 𝑥+ ≔ cantidad de materia prima 2 El objetivo es maximizar la cantidad de fertilizante 𝑄 = 4𝑥) + 2𝑥+ − 0.5𝑥)+ − 0.25𝑥++ Las restricciones del problema son: -­‐‑ El costo no puede no puede superar el presupuesto de la empresa: 480𝑥) + 300𝑥+ ≤ 24000 -­‐‑ No negatividad: 𝑥) ≥ 0, 𝑥+ ≥ 0 Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
La función objetivo nos queda: max 𝑄(𝑥) , 𝑥+ ) = 4𝑥) + 2𝑥+ − 0.5𝑥)+ − 0.25𝑥++ Por lo tanto nuestro modelo se puede escribir completo de la forma: max 𝑄(𝑥) , 𝑥+ ) = 4𝑥) + 2𝑥+ − 0.5𝑥)+ − 0.25𝑥++ s.a. 480𝑥) + 300𝑥+ ≤ 24000 𝑥) ≥ 0, 𝑥+ ≥ 0 Ejemplo 2: Las variables de decisión del problema: 𝑥) ≔ cantidad de ampolletas a producir el primer mes 𝑥+ ≔ cantidad de ampolletas a producir el segundo mes 𝑥+ ≔ cantidad de ampolletas a producir el tercer mes La función objetivo nos queda: El objetivo es minimizar los costos, el Costo Total = costo de producción + costo de almacenaje segundo mes + costo de almacenaje tercer mes. Costo de producción:= 𝑥)+ + 𝑥++ +𝑥I+ Costo de almacenaje segundo mes:= 12(𝑥) − 50) Costo de almacenaje tercer mes:= 12(𝑥) + 𝑥+ − 50) Por lo tanto 𝑍 𝑥) , 𝑥+ , 𝑥I = 𝑥)+ + 𝑥++ +𝑥I+ + 12 𝑥) − 50 + 12(𝑥) + 𝑥+ − 50) Las restricciones del problema son: -­‐‑ Atender la demanda del primer mes: 𝑥) ≥ 50 Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
-­‐‑ Atender la demanda del segundo mes: 𝑥) − 50 + 𝑥+ ≥ 50 -­‐‑ Atender la demanda del tercer mes: 𝑥) + 𝑥+ − 100 + 𝑥I ≥ 50 -­‐‑ No negatividad: 𝑥+ ≥ 0, 𝑥I ≥ 0 Por lo tanto nuestro modelo se puede escribir completo de la forma: min 𝑍 𝑥) , 𝑥+ , 𝑥I = 𝑥)+ + 𝑥++ + 𝑥I+ + 12 𝑥) − 50 + 12(𝑥) + 𝑥+ − 50) s.a. 𝑥) ≥ 50 𝑥) − 50 + 𝑥+ ≥ 50 𝑥) + 𝑥+ − 100 + 𝑥I ≥ 50 𝑥+ ≥ 0, 𝑥I ≥ 0 Ejemplo 3: Las variables de decisión del problema: 𝑥) ≔ millones de barriles extraídos el primer año 𝑥+ ≔ millones de barriles extraídos el segundo año La función objetivo corresponde a maximizar los ingresos, 𝑍 𝑥) , 𝑥+ = 𝑥) 30 − 𝑥) +
𝑥+ 35 − 𝑥+ − 𝑥)+ − 2𝑥++ . Las restricciones del problema: -­‐‑ Gastar como máximo 250 euros en la extracción: 𝑥)+ + 2𝑥++ ≤ 250 -­‐‑ Obtener como máximo 20 millones de barriles: 𝑥) + 𝑥+ ≤ 20 Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
-­‐‑ No negatividad: 𝑥) ≥ 0, 𝑥+ ≥ 0 Por lo tanto nuestro modelo se puede escribir completo de la forma: min 𝑍 𝑥) , 𝑥+ = 𝑥) 30 − 𝑥) + 𝑥+ 35 − 𝑥+ − 𝑥)+ − 2𝑥++ s.a. 𝑥)+ + 2𝑥++ ≤ 250 𝑥) + 𝑥+ ≤ 20 𝑥) ≥ 0, 𝑥+ ≥ 0 Ejemplo 4: Las variables de decisión del problema: 𝑥) ≔ minutos que se compran en televisión 𝑥+ ≔ minutos que se compran en radio La función objetivo corresponde a maximizar los ingresos, 𝑍 𝑥) , 𝑥+ = −2𝑥)+ − 𝑥++ + 𝑥) 𝑥+ +
8𝑥) + 3𝑥+ . Las restricciones del problema: -­‐‑ Gastar 10000 dólares en publicidad en ambos medios: 3000𝑥) + 1000𝑥+ ≤ 10000 Por lo tanto nuestro modelo se puede escribir completo de la forma: min 𝑍 𝑥) , 𝑥+ = −2𝑥)+ − 𝑥++ + 𝑥) 𝑥+ + 8𝑥) + 3𝑥+ Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
Resolución usando Matlab: Recordar la siguiente estructura vista en el laboratorio: Ejemplo 1: fa = @(x) -4*x(1) - 2*x(2) + 0.5*x(1)^2 + 0.25*x(2)^2;
%Recuerden la función objetivo se multiplica por -1 para quedar en min
A = [480 300];
b = 24000;
Aeq = [];
beq = [];
lb = [0;0];
lu = [];
x0 = [0;0];
%Se deben dar una solución factible fácil, recuerden que factible es que
cumpla todas las restricciones
options=optimset('Algorithm','active-set');
[x,fval,e,output,lambda,G,H] = fmincon(fa, x0, A, b, [], [], lb,
lu,[],options)
%%%%%%%%%%%%%%%%RESULTADOS%%%%%%%%%%%%%%%%%%%
>> lagrange
Local minimum possible. Constraints satisfied.
fmincon stopped because the predicted change in the objective function
is less than the default value of the function tolerance and constraints
are satisfied to within the default value of the constraint tolerance.
<stopping criteria details>
No active inequalities.
Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
x =
x1 = 4.0000 %materia prima 1
x2 = 4.0001 %materia prima 2
fval = función objetivo
-12.0000
e =
5
output =
iterations:
funcCount:
lssteplength:
stepsize:
algorithm:
firstorderopt:
constrviolation:
message:
6
18
1
6.7460e-05
'medium-scale: SQP, Quasi-Newton, line-search'
3.3616e-05
-4.0000
'Local minimum possible. Constraints satisfied.
fmincon stopped because ...'
lambda =
lower:
upper:
eqlin:
eqnonlin:
ineqlin:
ineqnonlin:
[2x1
[2x1
[0x1
[0x1
0
[0x1
Gradiente =
1.0e-04 *
0.1329
0.3362
Hessiana =
1.0014
-0.0037
-0.0037
0.5094
double]
double]
double]
double]
double]
Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
Ejemplo 2: fa = @(x) x(1)^2 + x(2)^2 + x(3)^2 +12*(x(1)-50)+12*(x(1)+x(2)-50);
A = [-1 0 0;-1 -1 0;-1 -1 -1];
b = [-50;-100;-150];
%recordar que las restricciones deben ser del tipo <= por lo tanto
multiplicamos por -1 para dejar <=
Aeq = [];
beq = [];
lb = [50;0;0];
lu = [];
x0 = [50;0;0];
options=optimset('Algorithm','active-set');
[x,fval,e,output,lambda,G,H] = fmincon(fa, x0, A, b, [], [], lb,
lu,[],options)
%%%%%%%%%%%%%%%%RESULTADOS%%%%%%%%%%%%%%%%%%%
Local minimum found that satisfies the constraints.
Optimization completed because the objective function is non-decreasing
in
feasible directions, to within the default value of the function
tolerance,
and constraints are satisfied to within the default value of the
constraint tolerance.
<stopping criteria details>
Active inequalities (to within options.TolCon = 1e-06):
lower
upper
ineqlin
ineqnonlin
1
1
2
3
x =
50.0000 %ampolletas primer mes
50.0000 %ampolletas segundo mes
50.0000 %ampolletas tercer mes
fval =
8.1000e+03
e =
1
Investigación de Operaciones I
Profesor: Jaime Carrasco
Ayudante: Jorge Pontigo
output =
iterations:
funcCount:
lssteplength:
stepsize:
algorithm:
firstorderopt:
constrviolation:
message:
2
8
1
0
'medium-scale: SQP, Quasi-Newton, line-search'
0
0
'Local minimum found that satisfies the constraints.
Optimization comple...'
lambda =
lower: [3x1 double]
upper:
eqlin:
eqnonlin:
ineqlin:
ineqnonlin:
[3x1
[0x1
[0x1
[3x1
[0x1
double]
double]
double]
double]
double]
Gradiente =
124.0000
112.0000
100.0000
Hessiana =
1.0000
0.0000
0.0000
0.0000
1.5000
0.5000
Ejemplo 3: (propuesto) Ejemplo 4: (propuesto) 0.0000
0.5000
1.5000