用单纯形法求解线性规划问题.docx

文档介绍：: .
目录
1. 摘要2实验目的2实验内容2建立数学模型3实验原理5MALTAB程序代码及注释7结果形法的一般解题步骤可归纳如下：
① 把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。
② 若基本可行解不存在，即约束条件有矛盾，则问题无解。
③ 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。
④ 按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。
⑤ 若迭代过程中发现问题的目标函数值无界，则终止迭代。
流程图如下:
：
function[x,minf,flag,cpt]=dcxsf(A,b,c)formatrat%使数据可以以分数形式输出c=-c;%将目标函数系数向量加负号得到单纯形表第0行[m,n]=size(A);%求约束矩阵的行数和歹U数m1=m;%保存下原来的行数s=eye(m);%生成秩为m的单位矩阵A=[As];%将s矩阵添加到A矩阵右侧A=[Ab];%将b向量添加到A矩阵右侧g1=zeros(1,n);%生成一个1行n歹0的零矩阵g1x=ones(1,m);%生成一个1行nf0元素全为1的矩阵g1=[g1-x];%将g1和-x合并，产生一个新的前n列为0后渺0为-1的单行矩阵g=[0];%初始化一个单元素零矩阵g1=[g1g];%将单元素零矩阵添加到g1右侧，生成人工向量的检验向量g1s1=n+m+1;%记录目前歹U数之和s2=zeros(1,m+1);%生成1行m+1歹0的零矩阵s2c=[cs2];%将s2添加到c右侧A1=zeros(m,1);%生成一个m行1歹0的零矩阵A1fori1=1:m
A1(i1,1)=i1+n;%基变量的数值存储区endfori=1:m
g1(1,:)=g1(1,:)+A(i,:);enddecide=find(g1(1,1:m+n)>0);%寻找g1中大亍零的数值歹U数存于decide当decide不为空
数组中while~isempty(decide)%
i=decide(1);%将歹0数赋给i
text=find(A(1:m,i)>0);%text存放该歹U中所有数值大于零的行数
ifisempty(text)%如果text为空则无解
flag=0;
break;
end
min=inf;%min初始化为无穷大
fori1=1:m%当该歹0存在大于零的数值时
ifA(i1,i)>0&A(i1,s1)/A(i1,i)<min%寻找比值最小的min=A(i1,s1)/A(i1,i);x1=i1;%将比值最小的行数赋给x1
end
end
A(x1,:)=A(x1,:)/A(x1,i);%进行单位化
c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:));
g1(1,:)=g1(1,:)+(-1*g1(1,i)*A(x1,:));
fori1=1:m
ifi1~=x1A(i1,:)=A(i1,:)+(-1*A(i1,i)*A(x1,:));%进行换机迭代
end
endA1(x1,1)=i;%
将列数既对应的非基变量转换为基变量
decide=find(g1(1,[1:m+n])>0);%再进行查找endifg1(1,s1)>0%无解情况
flag=-1;endifg1(1,s1)==0%置空矩阵gi(i,：)=[];fori6=1:mA(:,n+1)=[];endfori6=1:mc(n+1)=[]；enddecide=find(A1(1:m,1)>n);%if~isempty(decide)while~isempty(decide)x1=decide(1);%text=find(A(x1,1:n)~=0);%的列坐标ifisempty(text)%decide(1)=[];A1(x1,:)=[];A(x1,:)=[];m=m-1;elsei=text(1);%A(x1,:)=A(x1,:)/A(x1,i);%A1(x1,1)=i;
查找是否有人工变量存放的是人工变量的行数该行的所有元素都不为零如果text为空i保存列数进行单位化
c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:));fori1=1:mifi1~=x1A(i1,:)=A(i1,:)+(-1*A(i1,i)*A(x1,:));功进行换基迭代endenddecide(