单纯形法讲解及Python代码实现 单纯形法讲解及 代码实现 单纯形法讲解及Python代码实现 单纯形法讲解及 法求解线性规划最优解和最大值四、使用Python中scipy包进行上面的函数求解 一、了解单纯形法 一、了解单纯形法 1.单纯形法的原理 单纯形法的原理 代码实现一、了解单纯形法1.单纯形法的原理2.方法步骤二、例题讲解三、使用Python代码求单纯形 单纯形法是一种迭代算法，其基本原理及主要步骤是：首先设法找到一个（初始）基可行解，然后再根据最优性理论判断这个 基可行解是否最优解。若是最优解，则输出结果，计算停止；若不是最优解，则设法由当前的基可行内解产生一个目标值更优 的新的基可行解，再利用最优性理论对所得的新基可行解进行判断，看其是否最优解，这样就构成一个迭代算法。由于基可行 解只有有限个，而每次目标值都有所改进，因而必可在有限步内终止。如果原问题确有最优解，必可在有限步内达到，且计算 量大大少于穷举法；若原问题无最优解，也可根据最优性理论及时发现，停止计算，避容免错误及无效运算。 2.方法步骤 方法步骤 ①把线性规划问题的约束方程组表达成典范型方程组，典范型方程组要实现变量转换（所有变量为非负）、目标转换（统一为 求极大值，若求极小值可乘以(-1)）、约束转换（由不等式转化为等式）。然后，找出基本可行解作为初始基可行解。列出初 始单纯形表。 ②若基本可行解不存在，即约束条件有矛盾，则问题无解。 ③若基本可行解存在，从初始基可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函 数值更优的另一基本可行解。 ④按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。 ⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 用图表示如下： 二、例题讲解 二、例题讲解 题目 1.将问题化为标准型，加入松弛变量x3、x4，则标准型为： 2.求出线性规划的初始基可行解 列出初始单纯形表。 

3.进行最优性检验 如果表中所有检验数σj≤0，则表中的基可行解就是问题的最优解，计算停止。否则进行下一步。 4.从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表 ①确定换入基的变量。选择σ,> 0，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一 般选择最大的一个检验数， 即: σk =max{σj,lσj,>0}，其对应的xk作为换入变 量。 ②确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。 ③用换入变量Xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一 个新的单纯形表。 5.重复3)、4)步直到计算结束为止。 

求出最优解为X=（18,4,0,0）,最优值为Z=70 当然其他函数求解办法也是一样的。大家可以去试试。 三、使用Python代码求单纯形法求解线性规划最优解和最大值 三、使用 代码求单纯形法求解线性规划最优解和最大值 1.新建txt文档，根据上面写出的初始单纯形表将系数写入文档中。如下所示： 3 4 0 0 0 2 1 1 0 40 1 3 0 1 30 2.编写Python代码 import numpy as np #定义线性回归系数模型 def pivot(d,bn): l = list(d[0][:-2]) jnum = l.index(max(l)) #转入编号 m = [] for i in range(bn): if d[i][jnum] == 0: m.append(0.) else: m.append(d[i][-1]/d[i][jnum]) inum = m.index(min([x for x in m[1:] if x!=0])) #转出下标 s[inum-1] = jnum r = d[inum][jnum] d[inum] /= r for i in [x for x in range(bn) if x !=inum]: r = d[i][jnum] d[i] -= r * d[inum] #定义基变量函数 def solve(d,bn): flag = True while flag: if max(list(d[0][:-1])) <= 0: #直至所有系数小于等于0 flag = False else: pivot(d,bn) def printSol(d,cn): for i in range(cn - 1): if i in s: print("x"+str(i)+"=%.2f" % d[s.index(i)+1][-1]) 

else: print("x"+str(i)+"=0.00") print("objective is %.2f"%(-d[0][-1])) d = np.loadtxt("D:\\test.txt", dtype=np.float) (bn,cn) = d.shape s = list(range(cn-bn,cn-1)) #基变量列表 solve(d,bn) printSol(d,cn) 运行结果如下： 与我们上面手工推算的一致。 四、使用Python中中scipy包进行上面的函数求解 四、使用 包进行上面的函数求解 Pyhton整体代码 #导入包 from scipy import optimize import numpy as np #确定c,A_ub,B_ub c = np.array([3,4]) A_ub = np.array([[2,1],[1,3]]) B_ub = np.array([40,30]) #求解 res =optimize.linprog(-c,A_ub,B_ub) print(res) 运行结果展示： 通过对比可以发现两种方法所呈现的效果是接近的，scipy包的结果的精度更加细致，所以小数保留了多位。 如果大家还有什么不懂的地方可以自己去看看这篇文章哟。观看地址 作者：未见青山老。