【数学建模笔记】4.多目标规划+最短路径+最小生成树的简单理解_多目标规划尽量

1.多目标规划

 现有3个目标：

1.尽量使产品Ⅰ的产量不超过产品Ⅱ的产量；

2.尽可能充分利用所有设备；

3.尽可能使利润不少于56万

注意：目标1是“不超过”，也就是尽量“≤”；目标2是“充分利用”，也就是尽量“=”；目标3是“不少于”，也就是尽量“≥”

 

 求解方法：搜索MATLABA的fgoalattain函数，序贯算法，Lingo求解

2.最短路径

 最短路径：从图中的某个顶点出发，到达另外一个顶点的所经过的边的权重之和最小的一条路径

• 图：边和节点组成的结构，例如道路+城市
• 边带有方向的是有向图，否则为无向图
• 权重：每条边都有与之对应的值，本题中边为道路，边的权重为道路长度，越小越好

MATLAB求解最短路径：Dijkstra算法（难）,或MATLB的graphshortestpath函数

W = [10,5,2,1,4,6,7,3,9,2];
DG = sparse([1,1,2,2,3,4,4,5,5,5],[2,5,5,3,4,3,1,2,3,4],W);%稀疏矩阵
point_name = ['1','2','3','4','5'];
h = view(biograph(DG,point_name,'showWeights','on'));
[dist,path,pred] = graphshortestpath(DG,1,3)
%加宽加红
edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
set(edges,'LineColor',[1 0 0]);%RGB 红绿蓝
set(edges,'LineWidth',2);

求解得到：

 

其中稀疏矩阵可参考

【MATLAB】稀疏矩阵（含有大量0元素的矩阵）___zzz__的博客-CSDN博客

3.最小生成树

（1）MATLAB的minspantree函数求解最小生成树

s = [1,1,2,2,3,3,4,4,4,5];
t = [2,3,4,5,4,7,5,6,7,6];
weights = [50,60,65,40,52,45,50,30,42,70];
%生成无向图，s和t对应元素代表着边，weights是权值
 
G = graph(s,t,weights);
T = minspantree(G);
p = plot(G,'EdgeLabel',G.Edges.Weight,'MarkerSize',8);
highlight(p,T,'EdgeColor','red','LineWidth',3)

 结果：

（2）Krukal算法（适合点多边少的图） 

1.把图G中的所有边全部去掉，得到所有单独的顶点V构成的图T=(V,{})，其中V是顶点集合

2.从G中取出当前权值最小的边，如果该边加入T的边集后T不形成回路，则加入T；否则舍弃

 

3.重复第2步，直到T中有n-1条边（n是顶点数）

 

注：若第2步中遇到两条权值相同的最小权值边，任选一条即可，所以最小生成树可能不唯一，但权值之和相同

（3）Prim算法（适合边多点少）

1.设置一个图U，将原图G中任意一顶点取出加入U中

2.在所在的u∈U，v∈(G-U)的边(g,v)中找到一条权值最小的边，并入图U中

 

3.重复步骤2，直到U中包含了所有顶点

 

注：若第2步中遇到两条权值相同的最小权值边，任选一条即可，所以最小生成树可能不唯一，但权值之和相同

以上来自B站【数学建模 | 快速入门(上)】数模基础+MATLAB入门+论文写作+模型算法精讲(小白数模国赛必看)_哔哩哔哩_bilibili

不理解可以去看视频， up主讲的通俗易懂