julia语言单纯形法

### 如何使用 Julia 实现线性规划中的单纯形法

#### 使用 JuMP 和 Clp 解决线性规划问题
JuMP 是一个用于数学优化的建模语言，支持多种求解器。Clp 是 COIN-OR 的线性规划求解器之一，它实现了修正单纯形法来解决线性规划问题。

安装必要的包：

using Pkg
Pkg.add("JuMP")
Pkg.add("Clp")

定义并解决问题的一个简单例子如下所示[^1]:

using JuMP, Clp

model = Model(with_optimizer(Clp.Optimizer))

@variable(model, x >= 0)
@variable(model, y >= 0)

@objective(model, Max, 3x + 4y)

@constraint(model, c1, x + y <= 4)
@constraint(model, c2, 2x + y <= 5)

optimize!(model)

println("Objective value: ", objective_value(model))
println("x = ", value(x), " y = ", value(y))

这段代码创建了一个最大化目标函数 `3x + 4y` 的模型，在约束条件 `x + y ≤ 4` 和 `2x + y ≤ 5` 下找到最优解 `(x,y)` 并打印出来。

对于更深入理解单纯形法本身的工作原理以及如何手动实现该算法，下面提供了一种简化版的手动实现方式:

#### 手动实现单纯形法的核心逻辑

这里展示的是最基础版本的单纯形表方法，适用于标准形式的最大化 LP 问题（所有变量非负）。实际应用中应考虑更多细节如处理退化解等问题。

function simplex(A::Matrix{Float64}, b::Vector{Float64}, c::Vector{Float64})
    m, n = size(A)
    
    # 初始化基矩阵B和N(非基)，初始基本可行解xB=b
    B = Matrix(I,m,m); N = A; xB = copy(b);
    
    while true
        # 计算检验数σ=CN−CB*B^(-1)*A
        CB = zeros(m); CN = c;
        σ = CN - transpose(CB * inv(B)) * N
        
        # 如果所有的检验数都小于等于零，则已得到最优解
        if all(σ .<= 0)
            println("Optimal solution found.")
            break
        end
    
        # 否则选取最大正检验数对应的列作为入基变量
        entering_index = argmax(σ)
        
        d = B \ N[:,entering_index]
        
        # 若d≤0说明无界
        if all(d .<= 0)
            error("Unbounded problem!")
        end
        
        ratio_test_results = [(i,b[i]/d[i]) for i in eachindex(d) if d[i]>0]
        leaving_ratio,minval = findmin(map(last,ratio_test_results))
        leaving_index = first(ratio_test_results[leaving_ratio])
        
        # 更新基矩阵和其他参数...
        global B,N,xB,c,CB,CN
        ...
    end
    
    return xB,B\eye(size(B)[1]),c'*inv(B)*b
end

此段伪代码仅展示了核心迭代过程的一部分，并未完全覆盖所有情况；完整的实现在实践中还需要加入更多的边界检查与错误处理机制。