neidian.m

内点法求解线性规划问题； 通过内点法实现了线性规划问题的求解； 内有说明文件；

clear;
clc
n=7;
m=12;
delt=0.5;%gama
wucha=0.001;%error
A=[ 1 0 0 0 0 1 0
    1 0 0 0 0 0 1
    0 1 0 0 0 1 0
    0 1 0 0 0 0 1
    0 0 1 0 0 -1 0
    0 0 1 0 0 0 -1
    0 0 0 1 0 -1 0
    0 0 0 1 0 0 -1
    0 0 0 0 1 -1 0
    0 0 0 0 1 0 -1
    1 0 0 0 0 0 0
    0 1 0 0 0 0 0];%系数矩阵
c=[20 6 5 10 5 0 0]';
x0=[-1 -2 2 2 3 0 2]';%初始内点
% x0 = ones(7, 1);
k=1;
x(:,k)=x0; % 将x赋值给x的第k列；
b = [0 5 4 2 3 2 4 1 5 2 0 0]';
d=100;

while d>wucha
    v = b-A*x(:,k);%松弛变量
    D=inv(diag(v));%置对角矩阵
    
    % dx = inv(A'*D*D*A)*c;
    V = A';
    for i = 1 : size(D, 2)
        C(:, i) = V(:, i)*D(i, i);
    end
    for i = 1 : size(D, 2)
        C1(:, i) = C(:, i)*D(i, i);
    end
    C2 = C1*A;
    dx = inv(C2)*c;
    dv=-A*dx; % 目的是为了dx = inv(A'*D*D*A)*c;
    
    minvalue=999999999999999;    
    for j=1:m
        if(dv(j)<0)
            minvalue = min(minvalue,v(j)/-dv(j));
        end
    end
    
    lamda = delt*minvalue;
    x(:,k+1)=x(:,k)+lamda*dx;
    d = abs(c'*x(:,k+1)-c'*x(:,k))/abs(c'*x(:,k));%变化量
    max=c'*(x(:,k)+lamda*dx);%目标函数值
    % y=D*D*A*inv((A'*D*D*A))*c;%原问题解向量
    
    for i = 1 : size(D, 1)
        B1(:, i) = D(:, i)*D(i, i);
    end
    B2 = B1*A;
    V1 = A';
    for i = 1 : size(D, 2)
        C1(:, i) = V1(:, i)*D(i, i);
    end
    for i = 1 : size(D, 2)
        C11(:, i) = C1(:, i)*D(i, i);
    end
    C21 = C11*A;
    dx1 = inv(C21)*c;
    y = B2*dx1; % 目的是为了y=D*D*A*inv((A'*D*D*A))*c;
    
    k=k+1;
end
f = x(:,k)