实验一：线性规划单纯形算法一、实验目的通过实验熟悉单纯形法的原理，掌握Matlab 循环语句的应用,提高编程的能力和技巧。

二、实验用仪器设备、器材或软件环境Windows Xp 操作系统 ,Matlab6.5，计算机三、算法对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。

设初始基为B,然后执行如下步骤： (1).解B Bx b=,求得1B x B b-=，0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量(2).计算单纯形乘子w ,BwB C =,得到1B wC B -=,对于非基变量，计算判别数1i i i B i i z c c B p c σ-=-=-,令 max{}k i i i Rz c σ∈=-,R 为非基变量集合若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一步 (3).解k kBy p =,得到1k ky B p -=；若0k y ≤,即k y 的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4). (4).确定下标r,使{}:0min ,0t r rktktk b b tk y y t y y >=>且r B x 为离基变量。

k x 为进基变量，用kp 替换r B p ，得到新的基矩阵B ，返回步骤（1）。

对于极大化问题，可以给出完全类似的步骤，只是确定进基变量的准则不同。

对于极大化问题，应令min{}k k j j z c z c -=-四、计算框图五、计算程序function [x,f]=zuiyouhua(A,b,c)size(A)=[m,n];i=n+1:n+m;%基变量集合,后面m个松弛变量为初始基变量; N=1:n;%初始非基变量;B=eye(m,m);xb=b';xn=zeros(m,1);f1=0;w=zeros(1,m);z=-c;%初始判别数;flag=1;while(1)[a,k]=max(z);%x(k)为进基变量;if a<=0flag=0;breakelsey=inv(B)*A(:,k)if y<=0flag=0;fprintf('不存在最优解')breakendt=find(y>0);[a,r1]=min(b1(t)./y(t))r=t(r1); %基变量中第r 个变量为退基变量; i(:,r)=kB(:,r)=A(:,k);%换基，即将原基中第ｒ个变量换成第ｋ个变量; cb=c(:,i);%新的价值系数; xb=inv(B)*b; b0=xb; x=zeros(1,n+m) x(:,i)=xb' f=cb*xbz=cb*inv(B)*A-c;%可用z=cb*(B\A)-c,判别数. end end六、数值实验及结果分析求解线性规划问题:⎪⎪⎩⎪⎪⎨⎧=≥≤-=+-=++--4,3,2,1,012216443033..3min 2142132121i x x x x x x x x x t s x x i在工作区输入:A=[3,3,1,0;-4,-4,0,1;2,-1,0,0];b=[30,16,12]';c=[-3,1,0,0];[x,f]=zuiyouhua(A,b,c)x =7.3333 2.6667 0 0 0 56.0000 0f =-19.3333检验结果正确七、心得体会通过这次试验，使我对单纯形法的计算有了更进一步的了解。

但是在编程过程中由于对matlab不是很熟悉还是遇到了很多麻烦，所以我觉得老师在让我们编程的时候不能只是简单的介绍一下算法，更要着重说明一下软件的使用方法。

这样我们在编程的时候就能更加的得心应手。

本次完全仿照老师给的程序，没有能够形成自己的东西。

自己编程的能力还是很差的，对于这种已经给出算法的程序也不能正确的编写出来。

所以在今后要加强这方面的学习。

实验二：Lingo求解动态规划问题一、实验目的通过本实验熟悉动态规划的原理，了解动态规划的应用，并能利用数学软件（Lingo ）求解动态规划模型。

二、问题重述某公司打算向他的营业区增设4个销售点，各区赚取的利润与增设的销售点个数有关，其数据为：试求各区应分配几个增设的销售书店，才能使利润最大？其值是多少？三、数学模型设(1,2,3,4)i x i =为第i 区增设销售点的个数，()(1,2,3,4)i i g x i =为增设第i 个点所得到的盈利。

故问题模型为：112233441234max ()()()()..40,1,2,3,4i z g x g x g x g x s t x x x x x i =++++++=≥=四、计算编程 model :sets :quyu/1..4/; zl/0..4/;lirun(quyu,zl):g,c;endsetsdata:g=160 310 541 600 705,190 225 445 517 632,200 298 399 601 721,250 308 487 655 674;enddatamax=@sum(lirun(i,j):g(i,j)*c(i,j));@for(quyu(i):@sum(lirun(i,j):c(i,j))<=1);@for(lirun:@bin(c));@sum(lirun(i,j):(j-1)*c(i,j))=4;End五、计算结果Global optimal solution found.Objective value: 1436.000Objective bound: 1436.000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced Cost G( 1, 1) 160.0000 0.000000 G( 1, 2) 310.0000 0.000000 G( 1, 3) 541.0000 0.000000 G( 1, 4) 600.0000 0.000000 G( 1, 5) 705.0000 0.000000 G( 2, 1) 190.0000 0.000000 G( 2, 2) 225.0000 0.000000 G( 2, 3) 445.0000 0.000000 G( 2, 4) 517.0000 0.000000 G( 2, 5) 632.0000 0.000000 G( 3, 1) 200.0000 0.000000 G( 3, 2) 298.0000 0.000000 G( 3, 3) 399.0000 0.000000 G( 3, 4) 601.0000 0.000000 G( 3, 5) 721.0000 0.000000 G( 4, 1) 250.0000 0.000000 G( 4, 2) 308.0000 0.000000 G( 4, 3) 487.0000 0.000000 G( 4, 4) 655.0000 0.000000G( 4, 5) 674.0000 0.000000 C( 1, 1) 0.000000 -160.0000 C( 1, 2) 0.000000 -310.0000 C( 1, 3) 1.000000 -541.0000 C( 1, 4) 0.000000 -600.0000 C( 1, 5) 0.000000 -705.0000 C( 2, 1) 0.000000 -190.0000 C( 2, 2) 0.000000 -225.0000 C( 2, 3) 1.000000 -445.0000 C( 2, 4) 0.000000 -517.0000 C( 2, 5) 0.000000 -632.0000 C( 3, 1) 1.000000 -200.0000 C( 3, 2) 0.000000 -298.0000六、分析、检验和结论结果中Variable 列对应的(,)C i j ，i 表示第i 区，j 表示增加1j -个销售点，Value 列对应的0.000000表示不增加销售点，1.000000表示增加销售点。

例如 C( 1, 3) 1.000000表示第一区增加两个销售点。

(,)G i j 表示第i 行第j 列对应的值。

从结果中我们知道最优解是第一区和第二区分别增加2个销售点，第三区和第四区增加0个销售点此时盈利z=1436为最优值。

经过检验结果正确。

七、心得体会通过实验我熟悉了Lingo 的使用方法，学会了用Lingo 编写计算程序。

同时也掌握了分配问题的算法。

由于之前没有接触过Lingo 软件，老师也没有系统的讲述Lingo 的使用规则，所以我通过老师给的例题，依葫芦画瓢的写出了本问题的程序。

但是对实质性的东西还不是很了解，没有达到举一反三的地步。

仅仅只会分配法这一类问题的算法和程序，对程序中函数的具体应用还不了解。

所以我希望老师能在上实验课之前给我们讲述一下这种题型编程的注意事项，和涉及函数的具体意思，这样更有利于我们对问题的理解。

同时我也体会到自己没有主动的去学习而是被动的等待老师来讲解，从而造成了实验过程中出现了一些问题。

所以，以后要主动学习。