Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.
En este ejemplo se muestra cómo utilizar el solucionador en Optimization Toolbox® para resolver un problema de inversión con devoluciones deterministas durante un número fijo de años.linprog
T
El problema es asignar su dinero sobre las inversiones disponibles para maximizar su riqueza final. En este ejemplo se utiliza el enfoque basado en Solver.
Supongamos que usted tiene una cantidad inicial de dinero para invertir durante un período de tiempo de años en bonos de cupón cero.Capital_0
T
N
Cada bono paga una tasa de interés que se compone cada año, y paga el capital más intereses compuestos al final de un período de vencimiento. El objetivo es maximizar la cantidad total de dinero después de años.T
Puede incluir una restricción de que ninguna inversión individual es más que una cierta fracción de su capital total.
En este ejemplo se muestra primero la configuración del problema en un caso pequeño y, a continuación, se formula el caso general.
Puede modelar esto como un problema de programación lineal. Por lo tanto, para optimizar su riqueza, formular el problema para la solución por el solucionador.linprog
Empiece con un pequeño ejemplo:
El monto inicial a invertir es $1000.Capital_0
El período de tiempo es de 5 años.T
El número de bonos es 4.N
Para modelar el dinero sin invertir, tener una opción B0 disponible cada año que tiene un período de vencimiento de 1 año y una tasa de interés de 0%.
Bond 1, denotado por B1, se puede comprar en el año 1, tiene un período de vencimiento de 4 años, y una tasa de interés de 2%.
Bond 2, denotado por B2, se puede comprar en el año 5, tiene un período de vencimiento de 1 año, y una tasa de interés de 4%.
Bond 3, denotado por B3, se puede comprar en el año 2, tiene un período de vencimiento de 4 años, y una tasa de interés de 6%.
Bond 4, denotado por B4, se puede comprar en el año 2, tiene un período de vencimiento de 3 años, y una tasa de interés del 6%.
Al dividir la primera opción B0 en 5 enlaces con un período de vencimiento de 1 año y una tasa de interés del 0%, este problema puede modelarse de forma equivalente con un total de 9 bonos disponibles, de manera que parak=1..9
La entrada del vector representa el año en que la fianza está disponible para su compra.k
PurchaseYears
k
La entrada de vector representa el período de vencimientok
Maturity
k
La entrada de vector representa la tasa de interésk
InterestRates
k
Visualice este problema mediante barras horizontales que representan los tiempos y duraciones de compra disponibles para cada bono.
% Time period in years T = 5; % Number of bonds N = 4; % Initial amount of money Capital_0 = 1000; % Total number of buying oportunities nPtotal = N+T; % Purchase times PurchaseYears = [1;2;3;4;5;1;5;2;2]; % Bond durations Maturity = [1;1;1;1;1;4;1;4;3]; % Interest rates InterestRates = [0;0;0;0;0;2;4;6;6]; plotInvestments(N,PurchaseYears,Maturity,InterestRates)
Representar sus variables de decisión por un vector, donde es el monto en dólares de la inversión en bonos, para.x
x(k)
k
k=1..9
Al vencimiento, el pago de la inversión esx(k)
Definir k
% Total returns finalReturns = (1+InterestRates/100).^Maturity;
El objetivo es elegir inversiones para maximizar la cantidad de dinero recaudado al final del año.T
Desde la trama, se ve que las inversiones se recogen en varios años intermedios y se reinvierten. Al final del año, el dinero devuelto de las inversiones 5, 7 y 8 se puede recoger y representa su riqueza final:T
Para colocar este problema en la forma resuelve, convertir este problema de maximización en un problema de minimización utilizando el negativo de los coeficientes de:linprog
x(j)
Con
f = zeros(nPtotal,1); f([5,7,8]) = [-finalReturns(5),-finalReturns(7),-finalReturns(8)];
Cada año, usted tiene una cierta cantidad de dinero disponible para comprar bonos. A partir del año 1, puede invertir el capital inicial en las opciones de compra
Luego, para los años siguientes, recoja los retornos de los bonos que maduran y los reinvertirá en nuevos bonos disponibles para obtener el sistema de ecuaciones:
Escriba estas ecuaciones en la forma
Aeq = spalloc(N+1,nPtotal,15); Aeq(1,[1,6]) = 1; Aeq(2,[1,2,8,9]) = [-1,1,1,1]; Aeq(3,[2,3]) = [-1,1]; Aeq(4,[3,4]) = [-1,1]; Aeq(5,[4:7,9]) = [-finalReturns(4),1,-finalReturns(6),1,-finalReturns(9)]; beq = zeros(T,1); beq(1) = Capital_0;
Dado que cada importe invertido debe ser positivo, cada entrada del vector de solución lb
ub
lb = zeros(size(f)); ub = [];
Resuelva este problema sin restricciones sobre la cantidad que puede invertir en una fianza. El algoritmo de punto interior se puede utilizar para resolver este tipo de problema de programación lineal.
options = optimoptions('linprog','Algorithm','interior-point'); [xsol,fval,exitflag] = linprog(f,[],[],Aeq,beq,lb,ub,options);
Solution found during presolve.
La marca de salida es 1, lo que indica que el solucionador encontró una solución. El valor, devuelto como el segundo argumento de salida, corresponde a la riqueza final.-fval
linprog
Trace sus inversiones a lo largo del tiempo.
fprintf('After %d years, the return for the initial $%g is $%g \n',... T,Capital_0,-fval);
After 5 years, the return for the initial $1000 is $1262.48
plotInvestments(N,PurchaseYears,Maturity,InterestRates,xsol)
Para diversificar sus inversiones, puede optar por limitar el monto invertido en cualquier bono a un cierto porcentaje del capital total ese año (incluyendo las devoluciones de bonos que están actualmente en su período de vencimiento).Pmax
Se obtiene el siguiente sistema de desigualdades:
Coloca estas desigualdades en la forma matricial.Ax <= b
Para configurar el sistema de desigualdades, primero genere una matriz que contenga la devolución de la fianza indexada por i al año j en la fila i y la columna j.yearlyReturns
Representar este sistema como una matriz dispersa.
% Maximum percentage to invest in any bond Pmax = 0.6; % Build the return for each bond over the maturity period as a sparse % matrix cumMaturity = [0;cumsum(Maturity)]; xr = zeros(cumMaturity(end-1),1); yr = zeros(cumMaturity(end-1),1); cr = zeros(cumMaturity(end-1),1); for i = 1:nPtotal mi = Maturity(i); % maturity of bond i pi = PurchaseYears(i); % purchase year of bond i idx = cumMaturity(i)+1:cumMaturity(i+1); % index into xr, yr and cr xr(idx) = i; % bond index yr(idx) = pi+1:pi+mi; % maturing years cr(idx) = (1+InterestRates(i)/100).^(1:mi); % returns over the maturity period end yearlyReturns = sparse(xr,yr,cr,nPtotal,T+1); % Build the system of inequality constraints A = -Pmax*yearlyReturns(:,PurchaseYears)'+ speye(nPtotal); % Left-hand side b = zeros(nPtotal,1); b(PurchaseYears == 1) = Pmax*Capital_0;
Resuelve el problema invirtiendo no más del 60% en un solo activo. Trace las compras resultantes. Tenga en cuenta que su riqueza final es menor que la inversión sin esta restricción.
[xsol,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,ub,options);
Minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the selected value of the function tolerance, and constraints are satisfied to within the selected value of the constraint tolerance.
fprintf('After %d years, the return for the initial $%g is $%g \n',... T,Capital_0,-fval);
After 5 years, the return for the initial $1000 is $1207.78
plotInvestments(N,PurchaseYears,Maturity,InterestRates,xsol)
Cree un modelo para una versión general del problema. Ilustrarlo usando = 30 años y 400 bonos generados aleatoriamente con tasas de interés de 1 a 6%.T
Esta configuración da como resultado un problema de programación lineal con 430 variables de decisión. El sistema de restricciones de igualdad está representado por una matriz dispersa de dimensión 30-por-430 y el sistema de desigualdades está representado por una matriz dispersa de Dimension 430-by-430.Aeq
A
% for reproducibility rng default % Initial amount of money Capital_0 = 1000; % Time period in years T = 30; % Number of bonds N = 400; % Total number of buying oportunities nPtotal = N+T; % Generate random maturity durations Maturity = randi([1 T-1],nPtotal,1); % Bond 1 has a maturity period of 1 year Maturity(1:T) = 1; % Generate random yearly interest rate for each bond InterestRates = randi(6,nPtotal,1); % Bond 1 has an interest rate of 0 (not invested) InterestRates(1:T) = 0; % Compute the return at the end of the maturity period for each bond: finalReturns = (1+InterestRates/100).^Maturity; % Generate random purchase years for each option PurchaseYears = zeros(nPtotal,1); % Bond 1 is available for purchase every year PurchaseYears(1:T)=1:T; for i=1:N % Generate a random year for the bond to mature before the end of % the T year period PurchaseYears(i+T) = randi([1 T-Maturity(i+T)+1]); end % Compute the years where each bond reaches maturity SaleYears = PurchaseYears + Maturity; % Initialize f to 0 f = zeros(nPtotal,1); % Indices of the sale oportunities at the end of year T SalesTidx = SaleYears==T+1; % Expected return for the sale oportunities at the end of year T ReturnsT = finalReturns(SalesTidx); % Objective function f(SalesTidx) = -ReturnsT; % Generate the system of equality constraints. % For each purchase option, put a coefficient of 1 in the row corresponding % to the year for the purchase option and the column corresponding to the % index of the purchase oportunity xeq1 = PurchaseYears; yeq1 = (1:nPtotal)'; ceq1 = ones(nPtotal,1); % For each sale option, put -\rho_k, where \rho_k is the interest rate for the % associated bond that is being sold, in the row corresponding to the % year for the sale option and the column corresponding to the purchase % oportunity xeq2 = SaleYears(~SalesTidx); yeq2 = find(~SalesTidx); ceq2 = -finalReturns(~SalesTidx); % Generate the sparse equality matrix Aeq = sparse([xeq1; xeq2], [yeq1; yeq2], [ceq1; ceq2], T, nPtotal); % Generate the right-hand side beq = zeros(T,1); beq(1) = Capital_0; % Build the system of inequality constraints % Maximum percentage to invest in any bond Pmax = 0.4; % Build the returns for each bond over the maturity period cumMaturity = [0;cumsum(Maturity)]; xr = zeros(cumMaturity(end-1),1); yr = zeros(cumMaturity(end-1),1); cr = zeros(cumMaturity(end-1),1); for i = 1:nPtotal mi = Maturity(i); % maturity of bond i pi = PurchaseYears(i); % purchase year of bond i idx = cumMaturity(i)+1:cumMaturity(i+1); % index into xr, yr and cr xr(idx) = i; % bond index yr(idx) = pi+1:pi+mi; % maturing years cr(idx) = (1+InterestRates(i)/100).^(1:mi); % returns over the maturity period end yearlyReturns = sparse(xr,yr,cr,nPtotal,T+1); % Build the system of inequality constraints A = -Pmax*yearlyReturns(:,PurchaseYears)'+ speye(nPtotal); % Left-hand side b = zeros(nPtotal,1); b(PurchaseYears==1) = Pmax*Capital_0; % Add the lower-bound constraints to the problem. lb = zeros(nPtotal,1);
En primer lugar, resuelva el problema de programación lineal sin restricciones de desigualdad utilizando el algoritmo de punto interior.
% Solve the problem without inequality constraints options = optimoptions('linprog','Algorithm','interior-point'); tic [xsol,fval,exitflag] = linprog(f,[],[],Aeq,beq,lb,[],options);
Minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the selected value of the function tolerance, and constraints are satisfied to within the selected value of the constraint tolerance.
toc
Elapsed time is 0.049714 seconds.
fprintf('\nAfter %d years, the return for the initial $%g is $%g \n',... T,Capital_0,-fval);
After 30 years, the return for the initial $1000 is $5167.58
Ahora, resuelve el problema con las restricciones de desigualdad.
% Solve the problem with inequality constraints options = optimoptions('linprog','Algorithm','interior-point'); tic [xsol,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,[],options);
Minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the selected value of the function tolerance, and constraints are satisfied to within the selected value of the constraint tolerance.
toc
Elapsed time is 1.823664 seconds.
fprintf('\nAfter %d years, the return for the initial $%g is $%g \n',... T,Capital_0,-fval);
After 30 years, the return for the initial $1000 is $5095.26
A pesar de que el número de restricciones aumentó en un orden de 10, el tiempo para que el solucionador para encontrar una solución aumentó en un orden de 100. Esta discrepancia de rendimiento es causada parcialmente por columnas densas en el sistema de desigualdad que se muestra en la matriz.A
Estas columnas corresponden a enlaces con un período de vencimiento largo, como se muestra en el siguiente gráfico.
% Number of nonzero elements per column nnzCol = sum(spones(A)); % Plot the maturity length vs. the number of nonzero elements for each bond figure; plot(Maturity,nnzCol,'o'); xlabel('Maturity period of bond k') ylabel('Number of nonzero in column k of A')
Las columnas densas de las restricciones conducen a bloques densos en las matrices internas del solucionador, lo que produce una pérdida de eficacia de sus métodos dispersos. Para acelerar el solucionador, pruebe el algoritmo de doble símplex, que es menos sensible a la densidad de columna.
% Solve the problem with inequality constraints using dual simplex options = optimoptions('linprog','Algorithm','dual-simplex'); tic [xsol,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,[],options);
Optimal solution found.
toc
Elapsed time is 0.554433 seconds.
fprintf('\nAfter %d years, the return for the initial $%g is $%g \n',... T,Capital_0,-fval);
After 30 years, the return for the initial $1000 is $5095.26
En este caso, el algoritmo de doble símplex tardó mucho menos tiempo en obtener la misma solución.
Para obtener una sensación de la solución encontrada, compárela con la cantidad que podría obtener si pudiera invertir todo su dinero inicial en un bono con una tasa de interés del 6% (la tasa de interés máxima) durante el período completo de 30 años.linprog
fmax
También puede calcular la tasa de interés equivalente correspondiente a su riqueza final.
% Maximum amount fmax = Capital_0*(1+6/100)^T; % Ratio (in percent) rat = -fval/fmax*100; % Equivalent interest rate (in percent) rsol = ((-fval/Capital_0)^(1/T)-1)*100; fprintf(['The amount collected is %g%% of the maximum amount $%g '... 'that you would obtain from investing in one bond.\n'... 'Your final wealth corresponds to a %g%% interest rate over the %d year '... 'period.\n'], rat, fmax, rsol, T)
The amount collected is 88.7137% of the maximum amount $5743.49 that you would obtain from investing in one bond. Your final wealth corresponds to a 5.57771% interest rate over the 30 year period.
plotInvestments(N,PurchaseYears,Maturity,InterestRates,xsol,false)