# Simplex单纯性算法的Python实现

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

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[i][l] /= origin
# the other lines
for i in range(len(self.b)):
if i != l:
self.b[i] = self.b[i] - self.b[l] * self.coMatrix[e][i]
for i in range(len(self.b)):
if i != l:
origin = self.coMatrix[e][i]
for j in range(len(self.coMatrix)):
self.coMatrix[j][i] = self.coMatrix[j][i] - origin * self.coMatrix[j][l]
origin = self.c[e]
for i in range(len(self.coMatrix)):
self.c[i] = self.c[i] - self.coMatrix[i][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()

with open(filename)as f:
matrix = [([0] * var_num) for i in range(constrait_num)]
for i in range(constrait_num):
tokens = line.split(' ')
for j in range(var_num):
matrix[i][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][i])
problem.coMatrix.append(var)
tokens = line.split(' ')
for i in range(var_num):
problem.c.append(float(tokens[i]))

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

def getLamdaVector(evector):
ld = []
for i in range(len(evector)):
ld.append(evector[i])
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[i] > 0:
if problem.b[i] / ld[i] < min:
l = i
min = problem.b[i] / ld[i]
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[i] < min:
min = problem.b[i]
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[i] != 0:
origin = problem.c[i]
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: ')
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[i] = '%.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.')```

104 篇文章41 人订阅

0 条评论

## 相关文章

10920

### Python实现：KNN分类算法

1、KNN分类算法 KNN分类算法（K-Nearest-Neighbors Classification），又叫K近邻算法，是一个概念极其简单，而分类效果又很优...

521130

### （数据科学学习手札36）tensorflow实现MLP

我们在前面的数据科学学习手札34中也介绍过，作为最典型的神经网络，多层感知机（MLP）结构简单且规则，并且在隐层设计的足够完善时，可以拟合任意连续函数，而除...

48540

33660

### 测试数据科学家聚类技术的40个问题（能力测验和答案）（下）

【AI100 导读】本次测试的重点主要集中在概念、聚类基本原理以及各种技术的实践知识等方面。本文为下部，包括21-40题。上部请查看： 测试数据科学家聚类技术的...

36540

### 与人脸有关的模型总结

ASM(Active Shape Model)早期的基于统计学习的人脸配准算法 AAM (active appearance model)是ASM的改进算法 C...

29980

### MaxPooling的作用

maxpooling主要有两大作用 1. invariance(不变性)，这种不变性包括translation(平移)，rotation(旋转)，scale(尺...

30470

22830

375100

30630