Simplex单纯性算法的Python实现

妖怪幻 · 发表于 2017-5-5 07:27:46

　　单纯性算法是解决线性规划的经典方法，上世纪50年代就提出了，其基本思想是在可行域内沿着边遍历所有的顶点，找出最优值，即为算法的最优值。
　　算法的执行过程如下：
　　

求出初始基向量
构建单纯性表格
在所有非基向量对应的c中，找出一个最小的ci，若该ci大于0，则退出，输出obj，否则将ai入基
利用基向量组线性表示ai，得到该线性表示的系数向量Λ
对于Λ中所有大于0的分量，求出minmj=1bjΛj对应的j，然后将aj出基
问题矩阵旋转，即通过高斯行变换，将ai变换成aj
如果ci全大于0，则退出算法，输出obj，否则，重复第3步

__author__ = 'linfuyuan'

class Problem:
def __init__(self):
self.obj = 0
self.coMatrix = []
self.b = []
self.c = []
def pivot(self, basic, l, e):
# the l-th line
self.b[l] /= self.coMatrix[e][l]
origin = self.coMatrix[e][l]
for i in range(len(self.coMatrix)):
self.coMatrix[l] /= origin
# the other lines
for i in range(len(self.b)):
if i != l:
self.b = self.b - self.b[l] * self.coMatrix[e]
for i in range(len(self.b)):
if i != l:
origin = self.coMatrix[e]
for j in range(len(self.coMatrix)):
self.coMatrix[j] = self.coMatrix[j] - origin * self.coMatrix[j][l]
origin = self.c[e]
for i in range(len(self.coMatrix)):
self.c = self.c - self.coMatrix[l] * origin
self.obj = self.obj - self.b[l] * origin
basic[l] = e
def clone(self, another):
self.obj = another.obj
for i in another.b:
self.b.append(i)
for i in another.c:
self.c.append(i)
for v in another.coMatrix:
newv = []
for i in v:
newv.append(i)
self.coMatrix.append(newv)

basic = []
problem = Problem()

def readProblem(filename):
with open(filename)as f:
var_num = int(f.readline())
constrait_num = int(f.readline())
matrix = [([0] * var_num) for i in range(constrait_num)]
for i in range(constrait_num):
line = f.readline()
tokens = line.split(' ')
for j in range(var_num):
matrix[j] = float(tokens[j])
problem.b.append(float(tokens[-1]))
for i in range(var_num):
var = []
for j in range(constrait_num):
var.append(matrix[j])
problem.coMatrix.append(var)
line = f.readline()
tokens = line.split(' ')
for i in range(var_num):
problem.c.append(float(tokens))

def getMinCIndex(c):
min, minIndex = 1, 0
for i in range(len(c)):
if c < 0 and c < min:
min = c
minIndex = i
if min > 0:
return -1
else:
return minIndex

def getLamdaVector(evector):
ld = []
for i in range(len(evector)):
ld.append(evector)
return ld

def simplex(basic, problem):
minCIndex = getMinCIndex(problem.c)
while minCIndex != -1:
ld = getLamdaVector(problem.coMatrix[minCIndex])
# find the l line
l, min = -1, 10000000000
for i in range(len(problem.b)):
if ld > 0:
if problem.b / ld < min:
l = i
min = problem.b / ld
if l == -1:
return False
problem.pivot(basic, l, minCIndex)
minCIndex = getMinCIndex(problem.c)
return True

def initialSimplex(basic, problem):
min, minIndex = 1000000000, -1
for i in range(len(problem.b)):
if problem.b < min:
min = problem.b
minIndex = i
for i in range(len(problem.b)):
basic.append(i+len(problem.b))
if min >= 0:
return True
else:
originC = problem.c
newC = []
for i in range(len(problem.c)):
newC.append(0)
newC.append(1)
problem.c = newC
x0 = []
for i in range(len(problem.b)):
x0.append(-1)
problem.coMatrix.append(x0)
problem.pivot(basic, minIndex, -1)
res = simplex(basic, problem)
if res == False or problem.obj != 0:
return False
else:
problem.c = originC
problem.coMatrix.pop()
# Gaussian row operation
counter = 0
for i in basic:
if problem.c != 0:
origin = problem.c
for j in range(len(problem.c)):
problem.c[j] -= problem.coMatrix[j][counter] * origin
problem.obj -= problem.b[counter] * origin
counter += 1
return True

filename = raw_input('please input the problem description file: ')
readProblem(filename)
if initialSimplex(basic, problem):
res = simplex(basic, problem)
if res:
print 'the optimal obj is %.2f' % problem.obj
index = ['0.00'] * len(problem.coMatrix)
counter = 0
for i in basic:
index = '%.2f' % problem.b[counter]
counter += 1
print 'the solution is {%s}' % ' '.join(index)
else:
print 'no feasible solution'
else:
print 'no feasible solution'
raw_input('please input any key to quit.')
希望对大家有所帮助。

账号		自动登录	找回密码
密码			立即注册

大疆运维招人啦，

C++ :try 语句块和异常处理

C++的多态

Red Hat RHCE 8 (EX294) Cert Guide

Java/C++ 区别：看完这一篇，就够用！

别再用过时库了！这 13 个顶级 C++ 库才是

c++ size_t 和 int 的区别

[经验分享] Simplex单纯性算法的Python实现

浏览过的版块

扫码加入运维网微信交流群