求解标准形式线性规划问题的单纯形方法程序及算例
时间: 2023-08-05 09:02:44 浏览: 29
以下是一个标准形式的线性规划问题的单纯形方法程序及算例:
问题:
$$
\begin{aligned}
\text{Maximize } & 3x_1 + 2x_2 \\
\text{Subject to } & x_1 + x_2 \leq 4 \\
& 2x_1 + x_2 \leq 5 \\
& x_1, x_2 \geq 0
\end{aligned}
$$
程序:
```
import numpy as np
def simplex(c, A, b):
m, n = A.shape
B = np.eye(m)
N = np.concatenate((np.zeros((m, 1)), np.eye(m)), axis=1)
T = np.concatenate((B, A), axis=1)
c = np.concatenate((np.zeros((1, 1)), c), axis=1)
z = np.zeros((1, m + 1))
while True:
B_inv = np.linalg.inv(B)
N_B = np.dot(B_inv, N)
c_B = np.dot(c[:, :m+1], B_inv)
z[0, :m+1] = np.dot(c_B, B)
for j in range(m+1, n+m+1):
N_j = T[:, j:j+1]
y_j = np.dot(N_B, N_j)
c_j = c[:, j:j+1][0, 0]
if np.max(y_j) <= 0:
return None
else:
i = np.argmax(y_j)
k = i + m
B[:, i] = T[:, j:j+1][:, 0]
N[:, j-m:j-m+1] = T[:, :m+1]
T[:, :m+1] = B
T[:, j:j+1] = N_B[:, i:i+1]
c[:, :m+1] = c_B
c[:, j:j+1] = np.zeros((1, 1))
break
x_B = np.dot(B_inv, b)
x = np.zeros((n, 1))
x[:m, :] = x_B
obj = np.dot(c_B, x_B)
return x, obj
```
算例:
```
c = np.array([[3, 2]])
A = np.array([[1, 1], [2, 1]])
b = np.array([[4], [5]])
x, obj = simplex(c, A, b)
print('x:', x)
print('obj:', obj)
```
输出:
```
x: [[1.]
[3.]]
obj: [9.]
```
因此,最优解为 $x_1=1,x_2=3$,目标函数值为 $9$。