修正单纯形算法的python实现
时间: 2023-06-01 08:06:11 浏览: 249
以下是修正单纯形算法的Python实现:
```python
import numpy as np
def simplex(c, A, b):
m, n = A.shape
# 所有变量都为非负数
# b >= 0
if np.any(b < 0):
raise ValueError("Simplex method requires non-negative RHS coefficients")
# 最大化问题转换为最小化问题
if np.any(c < 0):
c, A = -c, -A
# Slack variables
# A x = b
# x + s = e
# Ax + s = e
# x = A^(-1)(e - s)
# 最终的解为 x
# s 列称为松弛变量
# [A I] (n+1) x m matrix
# [c 0] (n+1) x 1 matrix
# [x, s] 两个 m x 1 matrix
c = np.concatenate([c, np.zeros(n)])
A = np.concatenate([A, np.eye(m)], axis=1)
v = np.concatenate([np.zeros(n), b])
B = np.arange(n, n + m)
N = np.arange(n)
while True:
# 循环中找出入基变量
z = c[N] - A[:, N].T.dot(v)
if np.all(z >= 0):
# 所有z都为非负数,达到最小值,退出循环
break
e = np.argmax(z)
# 找出出基变量
d = np.full(m, np.inf)
for i in range(m):
if A[i, N[e]] > 0:
d[i] = v[n + i] / A[i, N[e]]
if np.all(d == np.inf):
# 解不存在(unbounded)
return None
l = np.argmin(d)
N[e], B[l] = B[l], N[e]
t = A[l, N[e]]
A[l, :] /= t
v[l + n] /= t
for i in range(m):
if i == l:
continue
t = A[i, N[e]]
A[i, :] -= A[l, :] * t
v[i + n] -= v[l + n] * t
return v[:n]
```
希望能解决您的问题。