Python单纯形表计算

Posted on Edited on Views:

使用python进行单纯形表的计算，解决线性规划问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import pandas as pd
import numpy as np

"""
系数矩阵的形式:
       b  x1  x2  x3  x4  x5
obj    0  70  30   0   0   0
x3   540   3   9   1   0   0
x4   450   5   5   0   1   0
x5   720   9   3   0   0   1
①第一行是目标函数的系数；亦即各变量对应的检验数；第2~4行是约束条件的系数
②第一列是约束方程的常数项
③对于目标函数的更新我们同样采用矩阵的变换,所以obj对应的第一列表示的是目标函数的相反数
"""
"""
运行如下代码后得到的结果如下所示
最终的最优单纯性法是:
        b  x1   x2  x3   x4        x5
obj -5700   0  0.0   0 -2.0 -6.666667
x3    180   0  0.0   1 -2.4  1.000000
x2     15   0  1.0   0  0.3 -0.166667
x1     75   1  0.0   0 -0.1  0.166667
目标函数的值: 5700
最优决策变量是:
x1 = 75
x2 = 15
"""
matrix = pd.DataFrame(
    data=np.array([
        [0, 60, 120, 0, 0, 0],
        [360, 9, 4, 1, 0, 0],
        [300, 3, 10, 0, 1, 0],
        [200, 4, 5, 0, 0, 1]
    ]),
    index=['obj', 'x3', 'x4', 'x5'],
    columns=['b', 'x1', 'x2', 'x3', 'x4', 'x5']
)
i=1
print("第",i,"个单纯性表是:")
print(matrix)

# 判断检验数是否大于0
c = matrix.iloc[0, 1:]
while c.max() > 0:
    c = matrix.iloc[0, 1:]
    i=i+1
    # 选择入基的变量
    in_x = c.idxmax()  # 该函数运行的结果是x1,即入基变量
    in_x_v = c[in_x]  # 得到入基变量的系数

    # 选择出基变量,即要计算θ的值,并比较大小
    b = matrix.iloc[1:, 0]
    # 选择入基变量对应的列
    in_x_a = matrix.iloc[1:][in_x]
    # 得到出基变量
    out_x = (b / in_x_a).idxmin()

    # 完成入基和出基的操作,即对矩阵做初等行变化
    matrix.loc[out_x, :] = matrix.loc[out_x, :] / matrix.loc[out_x][in_x]
    for idx in matrix.index:
        if idx != out_x:
            matrix.loc[idx, :] = matrix.loc[idx, :] - matrix.loc[out_x, :] * matrix.loc[idx, in_x]

    # 索引变换
    index = matrix.index.tolist()  # 得到所以行索引的值
    i = index.index(out_x)  # 得到出基变量的下标
    index[i] = in_x
    matrix.index = index
    print("第",i,"个单纯性表是:")
    print(matrix)

# 输出结果
print("最终的最优单纯性法是:")
print(matrix)
print("目标函数的值:", - matrix.iloc[0, 0])

# 列的数量减去行的数量得到非基变量的数量,且非基变量一定是下标在前的变量
# 比如非基变量的个数为2,则非基变量一定是x1,x2
print("最优决策变量是:")
x_count = (matrix.shape[1] - 1) - (matrix.shape[0] - 1)
X = matrix.iloc[0, 1:].index.tolist()[:x_count]
for xi in X:
    print(xi, "=", matrix.loc[xi, 'b'])