单纯性法解有约束的线性规划问题

%{
程序功能：
1、单纯性法解有约束的线性规划问题
2、标准形式的约束问题：
     目标函数求最小值、
     约束化为等式、
     引入松弛变量、
     变量全为非负
3、目标函数Z行系数全为非正数，则停止计算，RHS列对应系数为目标值x
    化为标准形式之后，形参的意义：
4、A是目标函数和约束的系数矩阵，必须写成正数形式！
     RHS 约束对应的等式右端数据
    num是松弛变量的起始下标
    result是约束转换为标准形式后的最优解
    X是对应的解向量；
    times是迭代（转轴）次数
5、目标函数的系数按照正数写！
6、结果给出的是绝对值！
7、不考虑无解的情况！
Author：Chenglin Li
Data    :  2019.06.24 
Contact: lichenglin19950620@163.com

%}
% clear
% clc
function [result,X,times]=danChunXingFa(A,RHS)
    format rat
    close all
    clear
    clc
%     num=3;
%第一步：将约束问题化为标准形式
%构建单纯性表格
%     A=[5,4,0,0,0;    %目标函数系数
%           1,2 1,0,0;   %松弛变量x3对应的约束系数
%           2,-1,0,1,0;  %松弛变量x4对应的约束系数
%           5,3,0,0,1;];  %松弛变量x5对应的约束系数
%     RHS=[6;
%               4;
%               15]; %约束对应的等式右端数据
%   A=[5,4,0,0,0;    %目标函数系数
%           1,2 ,1,0,0;   %松弛变量x3对应的约束系数
%           2,-1,0,1,0;  %松弛变量x4对应的约束系数
%           5,3,0,0,1];  %松弛变量x5对应的约束系数
%     RHS=[6;
%               4;
%               15]; %约束对应的等式右端数据
          A=[3,4,5,0,0;
              -1,-2,-3,1,0;
              -2,-2,-1,0,1];
          RHS=[-5;-6];
%     A=[1,-2,-4,-2,-1, 0, 0;
%          1,2,-1,1,-1,-1 ,0 ;
%          4,3,4,-2, -4, 0,1;
%          -1,-1,2,1,1,0, 0];
%      RHS=[0; 3; 1];
          
    [d1,d2]=size(RHS);
    if(d1==1)
        RHS=RHS';
    end
    theta=[NaN;zeros(length(RHS),1)]  ;%RHS/枢纽列
    RHS=[0;RHS];
   
    A=[A,RHS,theta]  ;
    [hang,lie]=size(A);
    %此处判断num的大小，程序不完备！
     for i=1:lie
        if(A(1,i)==0 && A(1,i+1)==0)
            num=i;
            break;
        end
     end
    
    X=zeros(lie-2,1); %所求x的最优值
    %确定松弛变量从x3开始？？
    
    index=num:1: lie-2;   % 转轴运算，基的下标！
    times=0;  %迭代次数
    while( judgeNegative(A(1,:)) && times<=10) ; %第一行目标函数有正数系数，则继续计算
            column=maxNumIndex(A(1,:)) ; %对应的为枢纽列
            A(2:end,end)=A(2:end,end-1)./A(2:end,column);  %确定theta列
            row=minNumIndex(A(2:end,end))+1  ;%对应的为枢纽行     
            xx=A(row,column) ; %找出枢纽转轴
            A(row,1:end-1)=A(row,1:end-1)/xx   ;%新枢纽行=原枢纽行/枢纽转轴
            for i=1:hang
                if(i~=row)
                    A(i,1:end-1)=A(i,1:end-1)-A(i,column)*A(row,1:end-1);  %其余行=原行-枢纽列*新枢纽行           
                end              
            end
%            disp('-----------本轮迭代结束---------')
            times=times+1;
           index(row-1)=column;
           Matrix=[A,RHS]
    end
    for i=1:(lie-2-num+1)
        X(index(i))=A(i+1,end-1);
    end
    result=abs(A(1,end-1))
    X
    times

end
%判断一个向量是否全为非正数, 若是，则返回0
function flag=judgeNegative(x)
        flag=0;
        n=length(x);
        for i=1:n
            if(x(i)>0)
                flag=1;  %向量中存在正数，则返回1
                break;
            end
        end
end


%返回一个向量最大值的下标
function index=maxNumIndex(x)
    n=length(x);
    m=x(1);
    index=1;
    for i=2:n
        if(x(i)>m)
            index=i;
            m=x(i);
        end
    end
end
%返回一个向量最小值的下标
function index=minNumIndex(x)
    

    n=length(x);
    for i=1:n
        if(x(i)<0)
            x(i)=inf; %刨除负数
        end
    end
    m=x(1);
    index=1;
    for i=2:n
        if(x(i)<m)
            index=i;
            m=x(i);
        end
    end
end