lp_experiment1.m

线性规划算法

clear;
clc;
num=1;
%A=[ 3  4  1  0  0  12;
 %   3  3  0  1  0  10;
  %  4  2  0  0  1   8;
   %-4 -3  0  0  0   0]
%采用二分法求解，用于求解有等式存在或大于式存在的方程
A=[1  0  0  1  0  0  1  0  0  1  0  0  0  0  0  0  0  0  0  0   400;
   0  1  0  0  1  0  0  1  0  0  1  0  0  0  0  0  0  0  0  0   600;
   0  0  1  0  0  1  0  0  1  0  0  1  0  0  0  0  0  0  0  0   300;
   3  0  0  2  0  0  1  0  0  0  0  0  1  0  0  0  0  0  0  0   600;
   0  3  0  0  2  0  0  1  0  0  0  0  0  1  0  0  0  0  0  0   800;
   0  0  3  0  0  2  0  0  1  0  0  0  0  0  1  0  0  0  0  0   375;
   1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0   600;
   0  0  0  1  1  1  0  0  0  0  0  0  0  0  0  0  1  0  0  0   500;
   0  0  0  0  0  0  1  1  1  0  0  0  0  0  0  0  0  1  0  0   325;
   6 -4  0  6 -4  0  6 -4  0  0  0  0  0  0  0  0  0  0  1  0     0;
   0 -3  6  0 -3  6  0 -3  6  0  0  0  0  0  0  0  0  0  0  1     0;
   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1     0]
[n,m]=size(A);
A(n,:)=A(n,:)-A(n-1,:)-A(n-2,:);  %每一列只能有一个1，这样才能形成单位阵
A(n,:)    
max(A(n,:));
%for s=1:5
 while min(A(n,:))<0
    % p返回最大元素；j位置
    [p,j]=pos_retmin1(A(n,:));
    % 第j列被确定为进入变量列
    % q返回最小元素；i位置
    [q,i]=clo_retmin1(A(:,m),A(:,j));
    % 求（最后一列的元素/进入变量列元素）的最小值q，并返回其行i
    A(i,:)=A(i,:)/A(i,j);
    
    %用行，对其余行高斯消元
    for k=1:i-1
        A(k,:)=A(k,:)-A(k,j)/A(i,j).*A(i,:);
    end
    for k=i+1:n
        A(k,:)=A(k,:)-A(k,j)/A(i,j).*A(i,:);
    end
    
    num=num+1;
    %A
end
A

A(n,m)

%------------------------------------------------------------------------------
%%%%%完成第一步
%------------------------------------------------------------------------------
B=A(:,1:m-3);      %去除人工变量列
B(:,m-2)=A(:,m);
B(n,:)=[-400 -400 -400 -300 -300 -300 -100 -100 -100 0 0 0 0 0 0 0 0 0 0];

B
[n,m]=size(B);
 while min(B(n,:))<0
    % p返回最大元素；j位置
    [p,j]=pos_retmin1(B(n,:));
    % 第j列被确定为进入变量列
    % q返回最小元素；i位置
    [q,i]=clo_retmin1(B(:,m),B(:,j));
    % 求（最后一列的元素/进入变量列元素）的最小值，并返回其行
    B(i,:)=B(i,:)/B(i,j);
    for k=1:i-1
        B(k,:)=B(k,:)-B(k,j)/B(i,j).*B(i,:);
    end
    for k=i+1:n
        B(k,:)=B(k,:)-B(k,j)/B(i,j).*B(i,:);
    end
    num=num+1;
    B;
end

%num
%format long
b=zeros(m-1,1);
for i=1:n-1
    k=find(B(i,:)==1);
    [l1,l2]=size(k);
    if  l2>1
      b(k)=0
    else
      b(k)=B(i,m);
    end
end
b
B(n,m)

B
format