运筹学实验报告
班级：数电四班 姓名：刘文搏 学号：
一、 实验目的
运用MATLAB程序设计语言完成单纯性算法求解线性规划问题。 二、 实验内容
编写一个MATLAB的函数文件：linp.m用于求解标准形的线性规划问题：
min f=c*x subject to ：A*x=b ； x>=0; 1、 函数基本调用形式：[x,minf,optmatrx,flag]=linp(A,b,c) 2、 参数介绍：
A:线性规划问题的约束A*x=b且x>=0中变量的系数组成的矩阵，是一个m*n的矩阵。
c :线性规划问题的目标函数f=c*x中各变量的系数向量，是一个n维的行
向量。
b :线性规划问题的约束A*x=b且x>=0中的常数向量，是一个m维的列
向量。
x :输出线性规划问题的最优解，当线性规划问题没有可行解或有可行解无 最优解时x=[].
minf :输出线性规划问题的最优值，当线性规划问题没有可行解时minf=[],
当线性规划问题有可行解无最优解时minf=-Inf。
flag :线性规划问题的求解结果标志值，当线性规划问题有最优解
时flag=1,
当线性规划问题有可行解无最优解时flag=0,当线性规划问题没有可行解时flag=-1.
cpt:输出最优解对应的单纯性表，当线性规划问题没有可行解或有可
行解无最优解时cpt=[].
三、 Linp函数
%此函数是使用两阶段算法求解线性规划问题 function [x,minf,flag,cpt]=linp(A,b,c);
for i=1:p %判断b是否<=0;将b转换成大于0； if b(i)<0
A(i,:)=-1*A(i,:); b(i)=-1*b(i); end end
%返回值：x，第一张单纯形表，基，标志 参数 A，c，b %********第一张单纯形表的初始化 [m,n]=size(A);%获得矩阵A的维数 [p,q]=size(b);
dcxb=zeros(m+2,m+n+1);%确定第一张单纯形表的大小 dcxb(1,:)=[-c,zeros(1,m+1)];%?给表的第一行赋值
dcxb(2,:)=[zeros(1,n),-1*ones(1,m),0];%?给表的第二行赋值 dcxb([3:m+2],:)=[A,eye(m,m),b];%添A和b到表中
jxl=[n+1:n+m]; for i=3:m+2
dcxb(2,:)=dcxb(2,:)+dcxb(i,:); for i=3:m+2
dxcb(2,:)=dxcb1(2,:)+dxcb1(i,:); end dxcb;
%************辅助问题换基迭代********************** dyl=find(dcxb(2,[1:m+n])>0); while ~isempty(dyl)
firstnum=dyl(1);
dll=dcxb([3:m+2],firstnum); youduanb=dcxb([3:m+2],m+n+1); look=find(dll>0); if isempty(look) dcxb(2,firstnum)=0; else min=Inf; for i=3:m+2
if dll(i-2)>0&youduanb(i-2)/dll(i-2) end dcxb(line1,:)=dcxb(line1,:)/dcxb(line1,firstnum); for i=1:m+2 if i~=line1 dcxb(i,:)=dcxb(i,:)+(-1*dcxb(i,firstnum)*dcxb(line1,:)); end end jxl(line1-2)=firstnum; end dyl=find(dcxb(2,[1:m+n])>0); dcxb end if dcxb(2,m+n+1)>0 fprintf('g>0,′此问题没有可行解'); x=[]; minf=inf; cpt=[]; flag=-1; return end look1=find(jxl>n); if dcxb(2,m+n+1)==0 %等于0，判断基变量中是否有人工变量； if ~isempty(look1)%′存在时进行处理 while ~isempty(look1) line2=look1(1)+2; chdy0=find(dcxb(line2,[1:n])~=0); if isempty(chdy0)%′存在人工变量都为零的那一行，去掉该行 dcxb(line2,:)=[]; look1(1)=[]; jxl(line2-2)=[]; else%否则进行换基迭代 secondnum=chdy0(1); dcxb(line2,:)=dcxb(line2,:)/dcxb(line2,secondnum); jxl(line2-2)=secondnum; for i=1:m+2 if i~=line2 dcxb(i,:)=dcxb(i,:)+(-1*dcxb(i,secondnum)*dcxb(line2,:)); end; end look1(1)=[]; end;