实验6最短路求解--的编程实现

1、实验6 最短路问题的编程实现成绩专业班级 数学121 学号 201212010131 姓名 覃绍强 报告日期 .实验类型：验证性实验 综合性实验 设计性实验实验目的：熟练最短路问题的Dijkstra算法。实验内容：最短路问题的Dijkstra算法。实验原理 最短路问题的Dijkstra算法：首先对图中的所有节点赋予双标号,即临时标号和永久标号,然后按一定的策略,依次判断并修改节点的临时标号,知道最后将终点改为永久标号求出最短路径。实验步骤1 要求上机实验前先编写出程序代码 2 编辑录入程序3 调试程序并记录调试过程中出现的问题及修改程序的过程4 经反复调试后，运行程序并验证程序运行是否正确。5

2、 记录运行时的输入和输出。 预习编写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：参考程序函数文件：dijkstra.mfunction min,path=dijkstra(w,start,terminal)n=size(w,1); label(start)=0; f(start)=start;%初始化for i=1:nif i=startlabel(i)=inf;endends(1)=start; u=start;while length(s)(label(u)+w(u,v)label(v)=(label(u)+w(u,v); f(v)=u;endendend %v1=

3、0; k=inf;for i=1:nins=0;for j=1:length(s)if i=s(j)ins=1;endendif ins=0 v=i;if klabel(v) k=label(v); v1=v;endendends(length(s)+1)=v1; u=v1;endmin=label(terminal); path(1)=terminal;i=1; while path(i)=startpath(i+1)=f(path(i); i=i+1 ;endpath(i)=start;L=length(path);path=path(L:-1:1); 求解下图中的最短路求解过程：输入输出

4、： x = 0 2 1 8 Inf Inf Inf Inf Inf Inf Inf 2 0 Inf 6 1 Inf Inf Inf Inf Inf Inf 1 Inf 0 7 Inf Inf 9 Inf Inf Inf Inf 8 6 7 0 5 1 2 Inf Inf Inf Inf Inf 1 Inf 5 0 3 Inf 2 1 Inf Inf Inf Inf Inf 1 3 0 4 Inf 6 Inf Inf Inf Inf 9 2 Inf 4 0 Inf 3 1 Inf Inf Inf Inf Inf 2 Inf Inf 0 7 Inf Inf Inf Inf Inf Inf Inf

5、6 3 7 0 1 2 Inf Inf Inf Inf Inf Inf 1 Inf 1 0 1 Inf Inf Inf Inf Inf Inf Inf Inf 2 1 0 start=1; terminate=11; min,path=dijkstra(x,start,terminate)min = 6path =1 2 5 9 11结果分析：即最短路径为：v1v2v5v9v11,最短距离为：16，手工计算的结果为：上述两种结果一致。总结：通过编程，将最短路的算法加深了印象，也熟悉了matlab编程，颇有收获的一次实验，给力！实验7 最大流问题的编程实现成绩专业班级 数学121 学号 2012

6、12010128 姓名 秦柯柯 报告日期 .实验类型：验证性实验 综合性实验 设计性实验实验目的：熟练最大流问题的求解算法。实验内容：最大流问题的求解算法。实验原理：先给定初始可行流，然后找出可扩充路（增广链），调整可扩充路上的流量，使可行流增大，不断重复上述过程，直到不存在可扩充路为止。 实验步骤1 要求上机实验前先编写出程序代码 2 编辑录入程序3 调试程序并记录调试过程中出现的问题及修改程序的过程4 经反复调试后，运行程序并验证程序运行是否正确。5 记录运行时的输入和输出。 预习编写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：参考程序使用lingo求解model:

7、sets:point/v1,v2,v3,v4,v5/;route(point,point)/v1 v2,v1 v3,v2 v3,v2 v4,v4 v3,v3 v5,v4 v5/:transport,capacity;endsetsdata:capacity=3 2 1 2 0 4 2;enddatamax=z;z=sum(point(j)|in(route,index(point,v1),j):transport(1,j);for(point(i)|i#ne#index(point,v1)#and#i#ne#index(point,v5):sum(point(j)|in(route,i,j):

8、transport(i,j)=sum(point(j)|in(route,j,i):transport(j,i);for(route:transport=capacity);end运行结果：Global optimal solution found. Objective value: 5.000000 Total solver iterations: 0 Variable Value Reduced Cost Z 5.000000 0.000000 TRANSPORT( V1, V2) 3.000000 0.000000 TRANSPORT( V1, V3) 2.000000 0.000000

9、 TRANSPORT( V2, V3) 1.000000 0.000000 TRANSPORT( V2, V4) 2.000000 0.000000 TRANSPORT( V4, V3) 0.000000 0.000000 TRANSPORT( V3, V5) 3.000000 0.000000 TRANSPORT( V4, V5) 2.000000 0.000000 CAPACITY( V1, V2) 3.000000 0.000000 CAPACITY( V1, V3) 2.000000 0.000000 CAPACITY( V2, V3) 1.000000 0.000000 CAPACI

10、TY( V2, V4) 2.000000 0.000000 CAPACITY( V4, V3) 0.000000 0.000000 CAPACITY( V3, V5) 4.000000 0.000000 CAPACITY( V4, V5) 2.000000 0.000000 Row Slack or Surplus Dual Price 1 5.000000 1.000000 2 0.000000 1.000000 3 0.000000 -1.000000 4 0.000000 0.000000 5 0.000000 -1.000000 6 0.000000 0.000000 7 0.0000

11、00 1.000000 8 0.000000 1.000000 9 0.000000 0.000000 10 0.000000 1.000000 11 1.000000 0.000000 12 0.000000 1.000000实验总结：最大流问题的基本思路是：先给出初始可行流，再找到可扩充路，不断进行优化，直至无法找到可扩充路为止。实验8 排队论与存储论问题的编程实现成绩专业班级 数学121 学号 201212010128 姓名 秦柯柯 报告日期 .实验类型：验证性实验 综合性实验 设计性实验实验目的：了解非线性规划的模型与求解算法。实验内容：实验原理 按照存储问题的基本模型类型，通过求解使

12、总费用最小的优化问题，求出最优订购批量、生产批量、最大存储量和最大缺货量、订货周期、间隔等数量指标。实验步骤1 要求上机实验前先编写出程序代码 2 编辑录入程序3 调试程序并记录调试过程中出现的问题及修改程序的过程4 经反复调试后，运行程序并验证程序运行是否正确。5 记录运行时的输入和输出。 预习编写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：参考程序问题：某电气公司的生产流水线需要某种零件，该零件需要靠订货得到。为此公司考虑到了如下费用结构：1） 批量订购的订货费12000元/次2） 每个零件的单位成本10元/件3） 每个零件的存储费用0.3元/(件.月)4） 每个零

13、件的缺货损失1.1 元/(件.月)Lingo求解：min=0.5*C_P*(Q-S)2/Q+C_D*D/Q+0.5*C_S*S2/Q;N=D/Q;gin(N);data:C_D=12000;D=96000;C_P=3.6;C_S=13.2;enddata运行结果：Local optimal solution found. Objective value: 81257.14 Extended solver steps: 3 Total solver iterations: 895 Variable Value Reduced Cost C_P 3.600000 0.000000 Q 32000.

14、00 0.000000 S 6857.143 0.000000 C_D 12000.00 0.000000 D 96000.00 0.000000 C_S 13.20000 0.000000 N 3.000000 -3085.704 Row Slack or Surplus Dual Price 1 81257.14 -1.000000 2 0.000000 -3085.704实验9 排队论问题的编程实现成绩专业班级 数学121 学号 201212010128 姓名 秦柯柯 报告日期 .实验类型：验证性实验 综合性实验 设计性实验实验目的：了解非线性规划的模型与求解算法。实验内容：实验原理 按

15、照排队论的基本模型：M/M/1、M/M/c等会计算排队系统的数量指标，包括队长、排队等待的队长、逗留时间、等待时间、忙期、闲期及排队系统的优化。实验步骤1 要求上机实验前先编写出程序代码 2 编辑录入程序3 调试程序并记录调试过程中出现的问题及修改程序的过程4 经反复调试后，运行程序并验证程序运行是否正确。5 记录运行时的输入和输出。 预习编写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：参考程序程序文件：%* %初始化顾客源 %* %总仿真时间 Total_time = 10; %队列最大长度 %到达率与服务率 lambda = 10; mu = 6; %平均到达时间与

16、平均服务时间 arr_mean = 1/lambda; ser_mean = 1/mu; arr_num = round(Total_time*lambda*2); events = ; %按负指数分布产生各顾客达到时间间隔 events(1,:) = exprnd(arr_mean,1,arr_num); %各顾客的到达时刻等于时间间隔的累积和 events(1,:) = cumsum(events(1,:); %按负指数分布产生各顾客服务时间 events(2,:) = exprnd(ser_mean,1,arr_num); %计算仿真顾客个数，即到达时刻在仿真时间内的顾客数 len_si

17、m = sum(events(1,:)Total_time break; else number = sum(events(4,member) events(1,i); %如果系统已满，则系统拒绝第 i个顾客，其标志位置 0 if number = N+1 events(5,i) = 0; %如果系统为空，则第 i个顾客直接接受服务 else if number = 0 %其等待时间为 02009.1516%PROGRAMLANGUAGEPROGRAMLANGUAGEevents(3,i) = 0; %其离开时刻等于到达时刻与服务时间之和 events(4,i) = events(1,i)+e

18、vents(2,i); %其标志位置 1 events(5,i) = 1; member = member,i; %如果系统有顾客正在接受服务，且系统等待队列未满，则 第 i个顾客进入系统 else len_mem = length(member); %其等待时间等于队列中前一个顾客的离开时刻减去其到 达时刻 events(3,i)=events(4,member(len_mem)-events(1,i); %其离开时刻等于队列中前一个顾客的离开时刻加上其服 %务时间 events(4,i)=events(4,member(len_mem)+events(2,i); %标识位表示其进入系统后，

19、系统内共有的顾客数 events(5,i) = number+1; member = member,i; end end end end %仿真结束时，进入系统的总顾客数 len_mem = length(member); %* %输出结果 %* %绘制在仿真时间内，进入系统的所有顾客的到达时刻和离 %开时刻曲线图（stairs：绘制二维阶梯图） stairs(0 events(1,member),0:len_mem); hold on; stairs(0 events(4,member),0:len_mem,.-r); legend(到达时间 ,离开时间 ); %标签hold off; gr

20、id on; %添加网格线%绘制在仿真时间内，进入系统的所有顾客的停留时间和等 %待时间曲线图（plot：绘制二维线性图） figure; plot(1:len_mem,events(3,member),r-*,1: len_mem,events(2,member)+events(3,member),k-); legend(等待时间 ,停留时间 ); grid on;运行图像：ans =2.0092e+003 实验10 运筹学综合应用成绩专业班级 数学121 学号 201212010128 姓名 秦柯柯 报告日期 .实验类型：验证性实验 综合性实验 设计性实验实验目的：培养用运筹理论与方法解决

21、实际问题的能力。实验内容：自己发现生活、生产实际中的问题，建立其数学模型，进行求解，完成实验报告；或针对过去数学建模问题的某一部分进行建模求解，写出实验报告。实验原理 根据生活、生产实际中的问题特征，综合运筹学所学理论与方法建立相应的模型，设计求解算法，求出问题的解。实验步骤1 要求上机实验前先编建立模型、设计求解算法、写出程序代码 2 编辑录入程序3 调试程序并记录调试过程中出现的问题及修改程序的过程4 经反复调试后，运行程序并验证程序运行是否正确。5 记录运行时的输入和输出。预习编写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：参考程序问题：某公司有甲乙两个工厂生产两

22、种产品，这两种产品要运到南北两个地区出售。相关信息见表格，产品分别有两个工厂中的两个车间来完成。公司希望采取一些措施来提高经济效益，为此要弄清楚应该关注哪些问题，是扩大销量还是改善工厂的瓶颈问题？如果扩大销量，首先扩大哪个市场以及首先扩大哪种产品？如果要增加工厂的有效工时，应首先关注哪一家工厂的哪个车间？分析：这是一个线性规划问题，重点在建模并用对偶理论进行分析。 产品收益=售价-销售费用-单价生产成本-单价运费建模： 销量限制：，工时限制：故可建立模型：s.t求解：下面用matlab求解：1） 建立函数文件：function sol,val,kk=ssimplex(A,N)%- 求解标准型线

23、性规划:max c*x;s.t. A*x=b;x=0%- A:初始单纯形表，（包括:第一行为c，最后一行是初始的检验数，最后一列是资源向量b）%- N：初始的基变量的下标%- sol：是最优解%- val：是最优值%- kk：是迭代次数mA,nA=size(A);kk=0; % 迭代次数flag=1;while flag kk=kk+1; if A(mA,:)0 & A(1:mA-1,i)temp temp=A(mA,i); inb=i; % 进基变量的下标 end end sita=zeros(1,mA-1); for i=1:mA-1 if A(i,inb)0 sita(i)=A(i,nA

24、)/A(i,inb); end end temp=inf; for i=1:mA-1 if sita(i)0&sita(i) temp=sita(i); outb=i; % 出基变量下标 end end % 以下更新N for i=1:mA-1 if i=outb N(i)=inb; end end % 以下进行转轴运算 A(outb,:)=A(outb,:)/A(outb,inb); for i=1:mA if i=outb A(i,:)=A(i,:)-A(outb,:)*A(i,inb); end end end endend2） 输入输出：A= 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 9000; 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 7500