单纯形法matlab实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function [x_opt, fx_opt, iter] = Simplex_eye(A, b, c)
    % 初始化变量
    [m, n] = size(A); % m: 约束数量，n: 变量数量
    iter = 0; % 迭代计数器

    % 找到基变量（对应单位矩阵的列）
    basic_indices = []; % 基本变量的索引集合

    for j = 1:n

        if isequal(A(:, j:j + m - 1), eye(m))
            basic_indices = j:j + m - 1;
            break;
        end

    end

    % 非基变量的索引集合
    nonbasic_indices = setdiff(1:n, basic_indices);

    % 开始单纯形法的迭代
    while (true && iter < 1000)
        iter = iter + 1; % 迭代次数加一

        % 计算检验数
        s = zeros(1, n);
        % 检验数
        s(nonbasic_indices) = c(nonbasic_indices)' - c(basic_indices)' * A(:, nonbasic_indices);

        if all(s <= 0)
            break; % 所有检验数都小于等于0，找到最优解
        end

        [~, k] = max(s); % 选取最大检验数对应的非基变量索引

        d = b ./ A(:, k); % 计算比值
        d(d <= 0) = inf; % 将非正数值替换为无穷大
        [~, l] = min(d); % 选取最小比值对应的基变量索引
        l = basic_indices(l);

        % 更新基变量和非基变量索引
        basic_indices(basic_indices == l) = k;
        nonbasic_indices(nonbasic_indices == k) = l;

        % 更新基变量矩阵和非基变量矩阵
        A(:, nonbasic_indices) = A(:, basic_indices) \ A(:, nonbasic_indices);
        b = A(:, basic_indices) \ b;
        A(:, basic_indices) = eye(m);
    end

    % 输出最优解
    x = zeros(n, 1);
    x(basic_indices) = b;
    fx_opt = c' * x;
    x_opt = x;
end
1
2
3
4
5
6
7
8
9
10
11
12
clear;

A = [2 -3 2 1 0;
     1/3 1 5 0 1];
b = [15; 20];
c = [1; 2; 1; 0; 0];

[x_opt, fx_opt, iter] = Simplex_eye(A, b, c);

fprintf('最优解: x = [%f, %f, %f, %f, %f]\n', x_opt);
fprintf('最优值: Z = %f\n', fx_opt);
fprintf('迭代次数: %d\n', iter);