本文共 1777 字，大约阅读时间需要 5 分钟。

线性规划问题是优化领域中的一个经典问题，广泛应用于资源分配、工程规划等领域。单纯形法作为解决线性规划问题的高效算法，通过逐步优化目标函数，找到最优解。

线性规划标准模型

线性规划的标准模型如下：

• 目标函数：min ( c^T x )，其中 ( c ) 是系数向量，( x ) 是变量向量。
• 约束条件：( Ax = b )，其中 ( A ) 是约束矩阵，( x ) 是变量向量，( b ) 是常数向量。
• 变量非负约束：( x \geq 0 )。

线性规划的基本步骤

单纯形法的核心原理

代码实现

以下是一个Python代码实现单纯形法的伪代码：

import numpy as np
def solve():
    # 假设已经初始化好的矩阵d包含基变量和非基变量
    while np.anymax(d[-1][:-1]) > 0:
        # 选择进入基变量的非基变量
        jnum = np.argmin(d[:-1, -1] / d[:-1, 0])
        # 选择退出基变量的基变量
        inum = np.argmin(d[-1, -1] / d[-1, jnum])
        # 替换基变量
        d[inum] /= d[inum, jnum]
        for i in range(bn):
            if i != inum:
                d[i] -= d[i, jnum] * d[inum]
        # 输出当前解
        def printSol():
            for i in range(cn - 1):
                print(f"x{i:.2f}" if i in s else f"x{i:.2f} = 0.00")
            print(f"objective is {d[-1][-1]:.2f}")
        printSol()
# 假设已经初始化好了矩阵d和其他参数
d = np.loadtxt("data.txt", dtype=np.float)
bn = d.shape[0]  # 基变量数量
cn = d.shape[1]  # 总变量数量
s = list(range(bn))  # 基变量索引

问题求解

针对以下目标函数和约束条件：

• 目标函数：max ( z = x_0 + 14x_1 + 6x_2 )
• 约束条件：
  • ( x_0 + x_1 + x_2 \leq 4 )
  • ( x_0 \leq 2 )
  • ( x_2 \leq 3 )
  • ( 3x_1 + x_2 \leq 6 )
  • ( x_i \geq 0 )

添加松弛变量后，问题转化为标准形，存储到 data.txt 文件中。

代码调用

d = np.loadtxt("data.txt", dtype=np.float)
bn = d.shape[0]
cn = d.shape[1]
s = list(range(bn))
solve()

输出结果

运行代码后，输出如下：

x0=0.00
x1=1.00
x2=3.00
x3=0.00
x4=2.00
x5=0.00
x6=0.00
objective is 32.00

写后感

通过将单纯形法实现为代码，我深刻体会到了代码能够清晰地表达算法步骤的优势。线性规划虽然背后有复杂的数学理论，但通过代码实现，问题的解决过程变得直观高效。掌握单纯形法的理论基础和对偶理论，对理解和应用线性规划至关重要。