1数学软件
- 格式：doc
- 大小：66.65 KB
- 文档页数：14
重庆大学学生实验报告实验课程名称综合性实践环节（3）（Mathematical Software)开课实验室数学实验教学中心学院数学与统计年级2008 专业班数学一班学生姓名黄敏学号20082225开课时间2010 至2011 学年第二学期一、实验题目:背包问题摘要：背包问题是一个典型的 NP难题, 背包问题是指有不同价值、不同重量的物品 n 件,求从这 n 件物品中选取一部分物品且对每一物品,要么选,要么不选,满足被选物品的总重量不超过背包指定的限制重量且达到被选物品的价值总和最大的问题。
一. 实验目的：利用学习过的Matlab 软件编写背包问题的程序，实现能解决简单背包问题的目的。
二. 实验原理：在相关的限制条件下，建立相应的数学模型，再用递归的方法，借助Matlab软件编写的程序，实现在不超过背包容量的情况下，使所选物品价值最大。
三. 实验内容：1、模型的建立：设 W 为背包的容量, n 个物品的重量组成一向量( w1 , w2 , …, wn) ,其价值组成另一向量( v1 , v2 , …, vn) ,W > 0 , wi > 0 ,vi > 0 (1 ≤i ≤n) 。
要找出另一 n 元向量( N1 , N2 , …, N n) , Ni∈{ 0 ,Ni} , 1 ≤i ≤n ,Ni表示选则编号为Ni的物品,0表示不选该物品。
由此,背包问题要求:Total_v=maxni iv ∑且满足以下两个约束条件:(1)niiw W≤∑(2) Ni ∈{ 0 ,Ni} 1 ≤i ≤n也就是说对简单的背包问题,可以通过求出变量 N1,N2,…Nn的一个决策序列来得到它的解,而对变量Ni的决策就是决定它是取Ni值还是取0 值。
2、采用动态规划方法，（假设事先要放入的n件物品已编好了号N(i)），引入一个动态变化的数组T_N,用于存放放入物品的编号。
再运用递归的方法，求放入物品的最大价值。
具体的求解过程，见（四）技术路线及步骤以及程序后面的注释。
四. 技术路线（方法）、步骤、程序：实现算法及程序：function y=KnapSack(N,w,v,p)%定义一个函数，用于求背包所装物品的最大价值%N为物品的编号%w为一件物品的重量%v为某一种物品的总价值%p为某一种物品的单价Total_v=0;%初始价值为零Total_w=50;%背包的最大容量为50for i=1:length(N)%所装物品的种类和不超过规定数目时继续选择放入，直到所装物品最多Total_v=Total_v+v(i);%总价值等于上一步确定的总价值加上新放入物品的价值Total_w=Total_w-w(i);%背包剩余的容量为上一步剩余的容量减去新放入物品的容量if(Total_w<0)%如果超过最大容量Total_v=Total_v-v(i);%将不放入第i件物品Total_w=Total_w+w(i);%拿出第i件物品后背包剩余容量elseT_N(i)=N(i);%将装入的物品按放入先后的编号存放在数组T_N中T_W(i)=w(i);%将装入物品的重量之和赋给数组T_WT_V(i)=v(i);%装入物品的总价值赋给数组T_Vendenddisp('输出对应装入背包的物品编号')T_Ndisp('输出装入物品的总重量')sum(T_W)disp('输出装入物品的总价值')sum(T_V)五. 实验数据（实例）、结果、分析：假设有10件物品，编号依次为：10,8,4,6,2,9,7,5,3,1 单位重量分别为：5,4,5,6,7,8,9,2,1,5 （单位kg），单价分别为：100,50,20,30,20,10,10,60,20,10 （单位：元），总价值分别为：500,200,100,180,140,80,90,120,20,50（单位：元）输入以上数据并调用m文件KnapSack.m，结果如下：>> N=[10,8,4,6,2,9,7,5,3,1];>> w=[5,4,5,6,7,8,9,2,1,5];>> v=[500,200,100,180,140,80,90,120,20,50];>> p=[100,50,20,30,20,10,10,60,20,10];>> KnapSack(N,w,v,p)输出对应装入背包的物品编号T_N =10 8 4 6 2 9 7 5 3 0输出装入物品的总重量ans =47输出装入物品的总价值ans =1430结果分析：只有第1号物品没有装入背包，装入背包的物品总重量为47，最大价值为1430.六. 实验中遇到的问题及解决办法：函数的定义过程中遇到bug，通过翻阅课本和使用help解决的。
七. 实验结论：通过建立数学模型，借助matlab编程，能求得简单背包问题的数值解。
八. 相关问题思考:将此问题当做一个0-1规划问题，选择第i件物品，则xi=1，否则xi=0,0i n≤≤;择该问题将会更直观。
目标函数变为：maxni iiv x∑，满足条件，n i iiw x W≤∑二、实验题目：微分方程数值解——龙格-库塔算法一. 实验目的：（1）了解龙格-库塔算法的思想和原理；（2）练习使用matlab 编写龙格库塔算法的程序用于求微分方程的数值解。
二. 实验原理：本实验采用的是四阶经典龙格-库塔公式，递推公式为：11234(22)/6i i y y K K K K +=++++1(,)i i K hf x y =21(/2,/2)i i K hf x h y K =++32(/2,/2)i i K hf x h y K =++43(,)i i K hf x h y K =++一. 实验内容：编写四阶经典龙格库塔算法的matlab 程序，求解微分方程'20,01y y x =-≤≤，y(0)=1 。
二. 技术路线（方法）、步骤、程序：%四阶经典R-K 公式作数值计算clc;clear all;F='-20*y';%输入函数和求解区间a=0;b=1;%先对h=0.1计算h=0.1;%步长n=(b-a)/h;%区间等分数X1=a:h:b;%X1的取值过程和区间Y1=zeros(1,n+1);Y1(1)=1;%给定的初值条件for i=1:n%在区间等分后的每个小区间进行循环迭代x=X1(i);y=Y1(i);K1=h*eval(F);%计算K1x=x+h/2;y=y+K1/2;K2=h*eval(F);%计算K2x=x;y=Y1(i)+K2/2;K3=h*eval(F);%计算K3x=X1(i)+h;y=Y1(i)+K3;K4=h*eval(F);%计算K4Y1(i+1)=Y1(i)+(K1+2*K2+2*K3+K4)/6;%计算微分方程数值解的龙格库塔公式end%准确解temp=[];f=dsolve('Dy=-20*y','y(0)=1','x');%调用matlab函数求解准确解，以便与龙格库塔公式计算出的结果对比df=zeros(1,n+1);for i=1:n+1temp=subs(f,'x',X1(i));df(i)=double(vpa(temp));endX1disp('h=0.1');%输出步长disp(Y1);%输出龙格库塔公式计算出的值disp('准确值');%输出准确值df三. 实验数据（实例）、结果、分析：X1 =0 0.1000 0.2000 0.3000 0.4000 0.5000 0.6000 0.70000.8000 0.9000 1.0000h=0.11.0000 0.3333 0.1111 0.0370 0.0123 0.0041 0.0014 0.0005 0.0002 0.0001 0.0000准确值df =1.0000 0.1353 0.0183 0.0025 0.0003 0.0000 0.0000 0.00000.0000 0.0000 0.0000六. 实验中遇到的问题及解决办法：改变步长，如h=0.2，得到的数值解是不稳定的。
故在运算时选择较小的步长，即将区间尽量细分，使结果能更加精确。
七. 实验结论：龙格库塔算法在给定的步长下，运用matlab编程，能快速得出微分方程的数值解，并可与用matlab函数得到的准确解相互比较，从而评价该算法的有效性。
八. 相关问题思考：如果改变步长，如将步长h=0.1变为h=0.2，得到的结果将会是怎样的呢？在以上程序中加入该段程序：%对h=0.2计算h=0.2;%步长n=(b-a)/h;X2=a:h:b;Y2=zeros(1,n+1);Y2(1)=1;for i=1:nx=X2(i);y=Y2(i);K1=h*eval(F);x=x+h/2;y=y+K1/2;K2=h*eval(F);x=x;y=Y2(i)+K2/2;K3=h*eval(F);x=X2(i)+h;y=Y2(i)+K3;K4=h*eval(F);Y2(i+1)=Y2(i)+(K1+2*K2+2*K3+K4)/6;end计算结果为：X1 =0 0.1000 0.2000 0.3000 0.4000 0.5000 0.60000.7000 0.8000 0.9000 1.0000h=0.11.0000 0.3333 0.1111 0.0370 0.0123 0.0041 0.00140.0005 0.0002 0.0001 0.0000X2 =0 0.2000 0.4000 0.6000 0.8000 1.0000h=0.21 5 25 125 625 3125 准确值df =1.0000 0.0183 0.0003 0.0000 0.0000 0.0000h 的数值解是不稳定的.，因为龙格库塔是单步法，公式的局部截由结果可知0.2断误差较大。
三、实验题目：龙贝格数值积分一、实验目的： 练习使用matlab 软件编写龙贝格数值积分的程序，输入相关被积函数后，能计算出正确的结果。
二、实验原理：龙贝格积分法是利用变步长的复化梯形公式推导出的数值积分方法，计算公式为：()()0T h T h =()()()221111[(/2)(1/2)]/[11/2][4(/2)()]/(41)mm m m m m m m m T h T h T h T h T h ----=--=--其中()T h 是将[a,b]n 等分后构造的复化梯形公式。
三. 实验内容：（1）编写龙贝格数值积分公式的matlab 程序；（2）输入实例对程序进行检测，得到积分结果。
