MATLAB使用单纯形法解决线性规划问题，函数形式调用，举例演示

        线性规划隶属于范畴学，在现实的应用十分广泛。简单来说，就是自变量在线性约束的条件下，求线性函数的最小值或最大值。对于优化问题，其数学模型往往需要提取出关键的三要素，即：自变量相关的约束条件，自变量的取值范围，关于自变量的目标函数。对于线性规划问题也同样如此。

        我们知道，当线性规划的自变量个数只有两个时，可以通过画图的方式直观求解，但是对于一般的线性规划问题的，常用的是单纯形法。单纯形法的基本思路是，将可行域中某个基本可行解转换到一个新的可行解，同时使得目标函数的值有所改善。注意使用单纯形法求解线性规划问题时，需要把问题抽象出的数学模型的一般形式转换为标准形式，也就是通过引入人工变量，将不等式约束变为等式约束，例如：

需要引入三个人工变量将不等式约束变为等式约束：

 也就是说，使用单纯形法解决线性规划问题，其形式必须为：

​​​​​​​ 下面给出单纯形法的MATLAB代码：

function [x,minf] = SimpleMthd(A,c,b,baseVector)
%约束矩阵：A
%目标函数系数向量：c
%约束右端向量：b
%初始基向量：baseVector
%目标函数取最小值时的自变量值：x
%目标函数的最小值：minf

sz = size(A);
nVia = sz(2);
n = sz(1);
xx = 1:nVia;
nobase = zeros(1,1);
m = 1;

if c>=0;
    vr = find(c~=0,1,'last');
    rgv = inv(A(:,(nVia-n+1):nVia)*b);
    if rgv>=0
        x = zeros(1,vr);
        minf = 0;
    else
        disp('不存在最优解！');
        x = NaN;
        minf = NaN;
        return;
    end
end

for i = 1:nVia
    if (isempty(find(baseVector == xx(i),1)))
        nobase(m) = i;
        m = m+1;
    else
        ;
    end
end
bCon = 1;
M = 0;

while bCon
    nB = A(:,nobase);
    ncb = c(nobase);
    B = A(:,baseVector);
    cb = c(baseVector);
    xb = inv(B)*b;
    f = cb*xb;
    w = cb*inv(B);
    
    for i = 1:length(nobase)
        sigma(i) = w*nB(:,i)-ncb(i);
    end
    [maxs,ind] = max(sigma);
    if maxs<=0
        minf = cb*xb;
        vr = find(c~=0 ,1,'last');
        for l = 1:vr
            ele = find(baseVector == 1,1);
            if (isempty(ele))
                x(l) = 0;
            else
                x(l) = xb(ele);
            end
        end
        bCon = 0;
    else
        y = inv(B)*A(:,nobase(ind));
        if y<=0
            disp('不存在最优解！');
            x = NaN;
            minf = NaN;
            return;
        else
            minb = inf;
            chagB = 0;
            for j = 1:length(y)
                if y(j)>0
                    bz = xb(j)/y(j);
                    if bz<minb
                        minb = bz;
                        chagB = j;
                    end
                end
            end
            tmp = baseVector(chagB);
            baseVector(chagB) = nobase(ind);
            nobase(ind) = tmp;
        end
    end
    M = M+1;
    if (M==1000000)
        disp('找不到最优解！');
        x = NaN;
        minf = NaN;
        return;
    end
end

       本文的代码源自龚纯的《精通MATLAB最优化计算》，这本书中有很多使用MATLAB解决优化问题的实例，非常适合初学者学习使用MATLAB解决各类优化问题。下面举例演示本文的单纯形法的使用：

本例中的约束条件的最初形式即是前文所举的例子，将模型中的信息写成矩阵的形式，写入一个MATLAB的脚本中，并调用刚刚的单纯形法的函数代码：

A = [-1 2 1 0 0 ;
    2 3 0 1 0;
    1 -1 0 0 1];
c = [-4 -1 0 0 0];
b = [4; 12; 3];
[x,mf] = SimpleMthd(A,c,b,[3 4 5])

运行结果为：

x =

    4.2000    4.2000

mf =

  -18.0000
        由结果可以看出，其中求得的最优解为x=(4.2, 4.2)，最小值为-18。本文中的单纯形法的代码已经做过修正，可以用作解决一般的线性规划问题使用。后续我也会再分享在此代码基础上的改正。如果觉得有用可以点个赞支持一下。