两阶段算法求解线性规划问题(运筹学实验)

发布时间：2024-10-15

运筹学实验两阶段法求线性规划问题单纯形

%此函数是使用两阶段算法求解线性规划问题
function [x,minf,optmatrx,flag]=linp(A,c,b)
%x可行解 minf最优解 oprmatrx最优解对应的单纯形表 flag判断解的情况的标志
fprintf('n 请输入约束条件的系数矩阵！n');
A=input('A=');
fprintf('n 请输入最右端的列向量!n');
b=input('b=');%b为列向量
fprintf('n 请输入目标函数的系数矩阵!n');
c=input('c=');
format rat %可以让结果用分数输出
[m,n]=size(A);
[p,q]=size(b);
for i=1p
if b(i)0
A(i,)=A(i,)-1;
b(i)=b(i)-1;
end
end
%第一阶段辅助问题的求解
auxchart=zeros(m+2,m+n+1);%确定第一张辅助单纯形表，并将其置0
auxchart(1,)=[-c,zeros(1,m+1)];%给表的第一行赋值
auxchart(2,)=[zeros(1,n),-1ones(1,m),0];%给表的第二行赋值
auxchart([3m+2],)=[A,eye(m,m),b];%将变量系数和右端向量填到表中
basvar=[n+1n+m];%基变量是辅助变量
%使基变量的检验数为零
for i=3m+2
auxchart(2,)=auxchart(2,)+auxchart(i,);
end
%进行辅助问题的换基迭代
checknum1=find(auxchart(2,[1m+n])0);%checknum1向量中记录检验数大于零的位置
while ~isempty(checknum1)
column1=checknum1(1);%取第一个大于零的数
postivecheck1=auxchart([3m+2],column1);%postivecheck1为记录检验数大于零的列向量
rightvector1=auxchart([3m+2],m+n+1);%rightvector1为记录右端向量的矩阵
temp1=find(postivecheck10);%在postivecheck1向量中找大于零的位置
if isempty(temp1)
fprintf('n 此问题不存在最优解!n');
x=[]
minf=[]
optmatrx=[]
flag=-1
return
end
min1=Inf;%初始化最小值为无穷
for i=3m+2
if postivecheck1(i-2)0&rightvector1(i-2)postivecheck1(i-2)min1%找最小比
min1=rightvector1(i-2)postivecheck1(i-2);
row1=i;%记录位置
end
end
auxchart(row1,)=auxchart(row1,)auxchart(row1,column1);%化为一
for i=1m+2 %进行初等行变换
if i~=row1
auxchart(i,)=auxchart(i,)+(-1auxchart(i,column1)auxchart(row1,));
end
end
basvar(row1-2)=column1;%出基和进基
checknum1=find(auxchart(2,[1m+n])0);%重新找检验向量中大于零的数的位置
end
%如果辅助问题的最优解大于零，则原问题无可行解
if auxchart(2,m+n+1)0
fprintf('n 此问题不存在最优解!n');
x=[]
minf=[]
optmatrx=[]
flag=-1
return
end
judge=find(basvarn);
%如果辅助问题的最优解等于零，且基变量中无辅助变量，则直接删除表中第二行和人工变量
if auxchart(2,m+n+1)==0&isempty(judge)
if isempty(judge)
auxchart(2,)=[];
auxchart(,[n+1n+m])=[];
end
%如果基变量中存在辅助变量，则直接进行换基迭代直到基变量中不存在人工变量
else
while auxchart(2,m+n+1)==0&(~isempty(judge))
row2=judge(1)+2;

运筹学实验两阶段法求线性规划问题单纯形

temp2=find(auxchart(row2,[1n])~=0)
if isempty(temp2)
auxchart(row2,)=[];%直接删除全为零的行
judge(1,)=[];%删除人工变量
else
column2=temp2(1);%记录下第一个不为零的列数
auxchart(row2,)=auxchart(row2,)auxchart(row2,column2);
basvar(row2-2)=column2;%记录下进基变量
for i=1m+n+1 %进行初等行变换
if i~=row2
auxchart(i,)=auxchart(i,)+(-1auxchart(i,column2)auxchart(row2,));
end
end
end
judge(1)=[];
end
auxchart(2,)=[];
auxchart(,[n+1n+m])=[];
end
%当辅助问题g的最小值等于0时得到原问题的一个基本可行解进入到第二阶段的运算
chart=auxchart;
checknum=find(chart(1,[1n])0);%checknum中记下检验数中大于零的位置
%若checknum不为空进行迭代
while ~isempty(checknum)
column=checknum(1);%把第一个大于零的数所在的列记为column
positivenum=chart([2m+1],column);%得到A的第column列
rightvector=chart([2m+1],n+1);%得到单纯形表的最后一列，即b
temp=find(positivenum0);%temp向量记下positivenum中大于零的数的位置
%如果temp为空，即positivenum向量中都是小于零的数，则原问题不存在最优解（即最优解为负无穷）
if isempty(temp)
%返回一个可行解
fprintf('n 此问题有可行解但无最优解!n');
x=zeros(n,1);
[size1,size2]=size(basvar);
for i=1size2
x(basvar(i))=chart(i+1,n+1);
end
fprintf('n 可行解为：n');x
minf=-Inf
optmatrx=[]
flag=0
return
end
%若temp不为空，即column列存在大于零的数则找到biai的最小值，记下所在的行数row
min=Inf;
for i=1m
if positivenum(i)0&rightvector(i)positivenum(i)min%找最小比
min=rightvector(i)positivenum(i);
row=i+1;%记录行数
end
end
%把转轴chart(row，column）置为1
chart(row,)=chart(row,)chart(row,column);
%把chart的column列的其他数都置为零
for i=1m+1%进行初等行变换
if i~=row
chart(i,)=chart(i,)+(-1chart(i,column)chart(row,));
end
end
%basvar中的基变量改为column
basvar(row-1)=column;
%继续判断向量是否有大于零的数，如果有继续迭代
checknum=find(chart(1,[1n])0);
end
%如果checknum为空了，循环结束，最优解即为chart的右上角的值
minf=chart(1,n+1);
x=zeros(n,1);
[size3,size4]=size(basvar);
fprintf('n已找到最优解!n');
for i=1size4
x(basvar(i))=chart(i+1,n+1);