二投资策略.doc

二、投资策略 基本思路 该问题是简单的优化问题，目的是找到最佳的投资策略。建立有向带权图的模型表示策略，利用最短路径算法求解。 模型建立 Ⅰ.根据题目中对问题的描述，将投资策略的最优化问题转化为图的模型。建立一个带权有向图，，其中表示第年买入，第年卖出的净成本（单位：千元），为投资的总年数。根据题意有。 Ⅱ.为了处理方便，我们用邻接矩阵来表示一个带权有向图。根据题目所给的条件，得到邻接矩阵如下： Ⅲ.根据得到的邻接矩阵，建立带权有向图如下，有向图中边的权值对应。该问题是寻找投资的最便宜策略，对应建立的图的模型，即是求从顶点1到顶点6的对端路径。 Ⅳ.由以上建立的模型，利用带权有向图的最短路径算法，求解最优策略 模型求解 求解带权有向图的最短路径的问题，可以使用采用Dijkstra算法、Floyd算法、动态规划法等。这里我们使用最常用的Dijkstra算法求解。采用MATLAB仿真，源程序见附录。仿真得到的结果： 最低成本（最短距离）为 即五年投资的最低成本为19千元。 最优策略（最短路径）为 即最便宜的投资策略为第1年买进，第3年卖出；第3年买进，第6年卖出。 附录 Dijkstra算法MATLAB源代码 clc; clear; [G, n] = Init_Gragh();%利用数据构建带权有向图G [Min, Path] = Dijkstra(G, n);%Dijkstra求解 function [G, n] = Init_Gragh() n = 6;%顶点个数 G = [ 0 4 6 9 12 20 0 0 5 7 11 16 0 0 0 6 8 13 0 0 0 0 8 11 0 0 0 0 0 10 0 0 0 0 0 0 ];%邻接矩阵 end function [Min, Path] = Dijkstra(G, n) priors = ones(1, n);%记录从源点到各顶点最短路径上的前趋 solved = zeros(1, n);%最短路径已经求出的顶点 distance = zeros(1, n);%存放各顶点的距离值 for i = 1 : n G(i, i) = Inf;%Dijkstra算法要求顶点到自身不可达 distance(i) = G(1, i);%初始到各顶点距离 end solved(1) = 1;%起点进入解集 distance(1) = 0;%起点到自身距离为0 for i = 1 : n%扩充红点集 k = 0; Min = Inf; for j = 1 : n%找当前距离起点最小的顶点 if solved(j) == 0 distance(j) Min Min = distance(j); k = j; end end if Min == Inf%说明没有可扩展顶点 break; end solved(k) = 1;%将距离最短的顶点加入解集 for j = 1 : n%调整当前到其余点最短距离 if solved(j) == 0 distance(j) distance(k) + G(k, j) distance(j) = distance(k) + G(k, j); priors(j) = k;%k是j的前趋 end end end Min = distance(1, n);%得到最短距离 prior = n;%从终点开始向前找前趋 i = 1; while prior ~= 1%只到前趋遍历到起点 Path(i) = prior; i = i + 1; prior = priors(prior); end Path(i) = prior; Path = fliplr(Path); end