本文主要是介绍对于simplex算法的代码实现最优解存在性的证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
对于任何线性规划系统，并不是都存在最优解，如果在约束条件中，每个常量都是大于等于0的，那么线性规划系统肯定是有最优解的，此时将每个变量选取为0就可以了。而只有当约束条件中的常量有小于0的情况的时候，才需要验证系统是否存在最优解，给出一个反例，进行最优解的存在性的证明：
添加图片注释，不超过 140 字（可选）
对于如上的例子，引入一个新的变量x0，同时将线性规划系统修改为如下：
添加图片注释，不超过 140 字（可选）
如果系统是存在最优解的，那么新系统也存在最优解，而且还是必须是x0=0的情况，首先将其转换成为标准型如下：
添加图片注释，不超过 140 字（可选）
由于第二个约束条件中能够让x0的值增加，因此选中它进行pivot变换，变换之后的整个系统的情况如下：
添加图片注释，不超过 140 字（可选）
这里就注意到此时的目标函数中已经没有变量对应的系数是大于0的了，因此这个时候的算法结束了，所有的非基本元取值为0，基本元取值约束中的常量，于是就有x0=4，这就与要求中的必须存在x0=0会相矛盾，于是也就证明了给定的线性规划系统是不存在最优解的。
使用python代码来实现如下：
def is_system_feasible(A, b, c):has_to_check = Falsefor k in range(len(b)): #先检验是否存在小于0的常数if b[k] < 0:has_to_check = Truebreakindex = 1N = []B = []v = 0for i in range(len(A[0])): #设置非基本远变量的下标N.append(index)index += 1for i in range(len(A)): #设置基本远的下标B.append(index)index += 1if has_to_check is False: #系统存在最优解,返回它的标准形式return TrueN_copy = N.copy()N_copy.insert(0, 0) #加入新变量x0的下标B_copy = B.copy()b_copy = b.copy()c_copy = [-1, 0, 0] #目标函数只有一个参数-x0A_copy = A.copy()for i in range(len(A)):A_copy[i].insert(0, -1) #每个约束条件都添加x0l = k(N_copy, B_copy, A_copy, b_copy, c_copy, v) = pivot(N_copy, B_copy, A_copy, b_copy, c_copy, v, l, 0) #转换目标函数使得它包含有系数为正的变量(N_copy, B_copy, A_copy, b_copy, c_copy, v) = simplex(N_copy, B_copy, A_copy, b_copy, c_copy, v)for i in range(len(B_copy)):if B_copy[i] == 0 and b[i] != 0:return Falsereturn True这篇关于对于simplex算法的代码实现最优解存在性的证明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
