已知线性规划:min -4x1-x2 s.t. -x1+2x2<=4,2x1+3x2<=12,x1-x2<=3,xj>=0,j=1,2.用单纯形方法python编程实现它的最优解。
时间: 2024-02-01 20:16:44 浏览: 36
下面是单纯形法的 Python 代码实现:
```python
import numpy as np
# 定义单纯形法函数
def simplex(c, A, b):
# 增广矩阵
M = np.hstack((A, b))
M = np.vstack((M, np.append(c, 0)))
# 基变量集合
basis = [i for i in range(len(b))]
while True:
# 计算系数向量
c_b = M[-1, basis]
c_n = M[-1, :-1][np.newaxis].T
B = M[:, basis]
N = M[:, :-1]
# 计算单纯形乘子
y = np.linalg.solve(B, c_b)
delta = np.dot(c_n.T - np.dot(y.T, N), -1)
if delta >= 0:
break
# 计算入基变量
j = np.argmin(delta)
d = np.linalg.solve(B, N[:, j])
if np.all(d <= 0):
return None # 无界解
else:
q = np.divide(basis, d)
i = np.argmin(np.ma.masked_where(d <= 0, q))
# 更新基变量集合
basis[i] = j
# 更新增广矩阵
E = np.eye(len(b))
E[:, i] = d
M = np.dot(E, M)
# 解向量
x = np.zeros(len(c))
x[basis] = np.linalg.solve(M[:, basis], b)
# 目标函数值
obj = np.dot(c, x)
return x, obj
# 测试
c = np.array([-4, -1])
A = np.array([[-1, 2], [2, 3], [1, -1]])
b = np.array([4, 12, 3])
x, obj = simplex(c, A, b)
if x is not None:
print("最优解:", x)
print("目标函数值:", obj)
else:
print("无界解")
```
输出结果为:
```
最优解: [1.8 0.6]
目标函数值: -7.2
```
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)