能用的单纯形法python代码

网上找了一些代码，发现有一些是不能用的，出现错误说集合为空

1.网上出现了好多次，但是不能用的，只能部分模型能用，比如例子中所示

原链接：https://www.jianshu.com/p/b233cfa06017

https://blog.csdn.net/kittyzc/article/details/81707464

 import numpy as np

 def pivot():

     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():

     flag = True

     while flag:

         if max(list(d[0][:-1])) <= 0: #直至所有系数小于等于0

             flag = False

         else:

             pivot()

 def printSol():

     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("data.txt", dtype=np.float)

 (bn,cn) = d.shape

 s = list(range(cn-bn,cn-1)) #基变量列表

 solve()

 printSol()

 # txt文件里面的格式

 1 14 6 0 0 0 0 0

 1 1 1 1 0 0 0 4

 1 0 0 0 1 0 0 2

 0 0 1 0 0 1 0 3

 0 3 1 0 0 0 1 6

 # 求解模型

 max z = x0+14*x1+6*x2

 s.t.

 x0 + x1 + x2 <= 4

 x0 <= 2

 x2 <= 3

 3*x1 + x2 <= 6

2. 在我的模型里面能用，不过显示比较繁琐，如果想要得到自己想要的，还需要在几个函数里面return

原链接：http://www.dataguru.cn/thread-909474-1-1.html

 Max z =  18*x1 + 12.5*x2

 s.t. x1 + x2 +x3 = 20

 x1 + x4 = 12

 x2 + x5 = 16

 x1,x2,x3,x4,x5 >= 0  

 运行下面脚本(单纯形法的Python实现)

 import numpy as np

 # 实体类　Table

 # 控制类　Simplex

 class Table:

     def __init__(self):

         pass

     def set_para(self,A,b,c,base,z0):

         """

         输入LP必须已经化为标准形式

         """

         self.A=A

         self.b=b

         self.c=c

         self.z0=z0

         self.base=base

         self.m,self.n=self.A.shape

     def build(self):

         self.table=np.zeros((self.m+1,self.n+1))

         self.table[:-1,:1]=self.b.T

         self.table[-1 ,0]=self.z0

         self.table[:-1,1:]=self.A

         self.table[-1, 1:]=c

         self.baseVar=base

     def is_best(self):

         for sigma_index in range(self.n):

             if sigma_index not in self.baseVar:

                 sigma=self.table[-1,1+sigma_index]

                 if sigma>0:

                     return False

         return True

     def is_no_solution(self):

         for sigma_index in range(self.n):

             if sigma_index not in self.baseVar:

                 sigma=self.table[-1,1+sigma_index]

                 if sigma>0:

                     no_solution_flag=True

                     for a in self.table[:-1,1+sigma_index]:

                         if a>0:

                             no_solution_flag=False

                     if no_solution_flag==True:

                         return True

         return False

     def get_inVar(self):

         max_sigma=0

         inVar=None

         for sigma_index in range(self.n):

             if sigma_index not in self.baseVar:

                 sigma=self.table[-1,1+sigma_index]

                 if sigma>max_sigma:

                     max_sigma=sigma

                     inVar=sigma_index

         return inVar

     def get_outVar(self,inVar):

         rates=[]

         for nobaseVar in range(self.m):

             a=self.table[nobaseVar,inVar+1]

             b=self.table[nobaseVar,     0 ]

             if a>0:

                 rate=b/a

                 rates.append((rate,nobaseVar))

         return min(rates)[1]    

     def in_out(self,inVar,outVar):

         a=self.table[outVar,inVar+1]

         self.table[outVar,:]/=a

         for i in range(self.m+1):

             if i != outVar:

                 self.table[i,:]-=self.table[outVar,:]*self.table[i,inVar+1]

         self.baseVar[outVar]=inVar

     def show(self):

         print ('基变量/取值：',self.baseVar,end='/')

         print (self.table[:-1,0])

         print ("单纯形表")

         for i in range(self.m+1):

             for j in range(self.n+1):

                 print ('%6.2f'%self.table[i,j],end=' ')

             print ()

         print ()

 class Simplex:

     def __init__(self):

         self.table=Table()

         # 0 正常，尚未得到最优解，继续迭代

         # 1 无解，无界解

         # 2 达到最优解

         self.status=0

         self.inVar=None

         self.outVar=None

     def set_para(self,A,b,c,base,z0=0):

         self.table.set_para(A,b,c,base,z0)

     def output_result(self):

         self._main()

         if self.status==1:

             print("此问题无界")

         elif self.status==2:

             print("此问题有一个最优解")

         elif self.status==3:

             print("此问题有无穷多个最优解")

     def _main(self):

         self._build_table()

         while 1:

             self.table.show()

             if self._is_best() or self._is_no_solution():

                 return

             self._get_inVar()

             self._get_outVar()

             self._in_out()

     def _build_table(self):

         self.table.build()

     def _is_best(self):

         if self.table.is_best():

             self.status=2

             return True

         return False

     def _is_no_solution(self):

         if self.table.is_no_solution():

             self.status=1

             return True

         return False

     def _get_inVar(self):

         self.inVar=self.table.get_inVar()

     def _get_outVar(self):

         self.outVar=self.table.get_outVar(self.inVar)

     def _in_out(self):

         self.table.in_out(self.inVar,self.outVar)

 if __name__=="__main__":

     s=Simplex()

     A=np.matrix([[1,1,1,0,0],

                  [ 1, 0,0,1,0],

                  [ 0, 1,0,0,1]])

     b=np.matrix([[20,12,16]])

     c=np.matrix([[18,12.5,0,0,0]])

     base=[2,3,4]

     s.set_para(A,b,c,base)

 s.output_result()

巴特西

能用的单纯形法python代码

最新文章

热门文章