最优化实验报告（单纯形法的matlab程序，lingo程序）

实验一：线性规划单纯形算法

一、实验目的

通过实验熟悉单纯形法的原理，掌握Matlab循环语句的应用,提高编程的能力和技巧。

二、实验用仪器设备、器材或软件环境

Windows Xp操作系统 ,Matlab6.5，计算机

三、算法

对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始

基本可行解。设初始基为B,然后执行如下步骤：

?1Bx?bx?Bb，令xN?0,计算目标函数值f?cBxB (1).解B,求得B以bi(i?1,2,...,m)记B?1b的第i个分量

(2).计算单纯形乘子w?1wB?Cw?CBBB, ,得到,对于非基变量，计算判别数

?i?zi?ci?cBB?1pi?ci,令 ?k?max{zi?ci},R为非基变量集合

i?R若判别数?k?0 ,则得到一个最优基本可行解，运算结束；否则，转到下一步

?1By?py?Bpk；若yk?0,即yk的每个分量均非正数，则停止kkk(3).解,得到

计算，问题不存在有限最优解，否则，进行步骤(4). (4).确定下标r,使

bryrk?min?t:ytk?0btytk,且ytk?0?用pkxk为进基变量，xBr为离基变量。

替换pBr，得到新的基矩阵B，返回步骤（1）。

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

zk?ck?min{zj?cj}

南昌航空大学数学与信息科学学院实验报告

四、计算框图

否

否

第 1 页

开始 初始可行解B 令xB?B?1b?b,xN?0,f?cBxB 计算单纯形乘子w?cBB，计算判别数?i令?k?1?wpj?cj,j?R（非基变量）?max{?j,j?R} ?k?0? 是 得到最优解 解方程Byk?pk，得到yk?B?1pk。 yk?0? 是 不存在有限最优解 确定下标r，是 bryrk?min?t:ytk?0btytk,且ytk?0? xk为进基变量，用pk替换pBr，得到新的基矩阵B 南昌航空大学数学与信息科学学院实验报告

五、计算程序

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<=0 flag=0; break else

y=inv(B)*A(:,k) if y<=0 flag=0;

fprintf('不存在最优解') break

第 2 页

南昌航空大学数学与信息科学学院实验报告

end

t=find(y>0);

[a,r1]=min(b1(t)./y(t))

r=t(r1); %基变量中第r个变量为退基变量; i(:,r)=k

B(:,r)=A(:,k);%换基，即将原基中第ｒ个变量换成第ｋ个变量; cb=c(:,i);%新的价值系数; xb=inv(B)*b; b0=xb; x=zeros(1,n+m) x(:,i)=xb' f=cb*xb

z=cb*inv(B)*A-c;%可用z=cb*(B\\A)-c,判别数. end end

六、数值实验及结果分析

求解线性规划问题:

min?3x1?x2?3x1?3x2?x3?30?4x?4x?x?16 ?24s.t.?1?2x1?x2?12??xi?0,i?1,2,3,4

在工作区输入:

A=[3,3,1,0;-4,-4,0,1;2,-1,0,0];

第 3 页

南昌航空大学数学与信息科学学院实验报告

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 0 f =

-19.3333

检验结果正确

七、心得体会

通过这次试验，使我对单纯形法的计算有了更进一步的了解。但是在编程过程中由于对matlab不是很熟悉还是遇到了很多麻烦，所以我觉得老师在让我们编程的时候不能只是简单的介绍一下算法，更要着重说明一下软件的使用方法。这样我们在编程的时候就能更加的得心应手。本次完全仿照老师给的程序，没有能够形成自己的东西。自己编程的能力还是很差的，对于这种已经给出算法的程序也不能正确的编写出来。所以在今后要加强

这方面的学习。

实验二：Lingo求解动态规划问题

第 4 页

南昌航空大学数学与信息科学学院实验报告

一、实验目的

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

二、问题重述

某公司打算向他的营业区增设4个销售点，各区赚取的利润与增设的销售点个数有关，其数据为： 销售店增加数 第一区利润（万第二区利润（万第三区利润（万第四区利润（万元） 0 1 2 3 4 160 310 541 600 705 元） 190 225 445 517 632 元） 200 298 399 601 721 元） 250 308 487 655 674 试求各区应分配几个增设的销售书店，才能使利润最大？其值是多少？

三、数学模型

设xi(i?1,2,3,4)为第i区增设销售点的个数，gi(xi)(i?1,2,3,4)为增设第i个点所

得到的盈利。故问题模型为：

maxz?g1(x1)?g2(x2)?g3(x3)?g4(x4)s..tx1?x2?x3?x4?4xi?0,i?1,2,3,4

四、计算编程 model:

sets:

quyu/1..4/; zl/0..4/;

第 5 页

南昌航空大学数学与信息科学学院实验报告

lirun(quyu,zl):g,c; endsets data:

g=160 310 541 600 705, 190 225 445 517 632, 200 298 399 601 721, 250 308 487 655 674; enddata

max=@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.000 Objective bound: 1436.000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0

Variable 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) …… 此处隐藏：2601字，全部文档内容请下载后查看。喜欢就下载吧 ……