Simplex单纯性算法的Python实现

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

算法的执行过程如下:

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


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[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)
        line = f.readline()
        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: ')
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[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.')

希望对大家有所帮助。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习之旅

R开发:协调过滤推荐

对于realRatingMatrix有六种方法:IBCF(基于物品的推荐)、UBCF(基于用户的推荐)、PCA(主成分分析)、RANDOM(随机推荐)、SVD(...

10920
来自专栏大数据挖掘DT机器学习

Python实现:KNN分类算法

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

521130
来自专栏数据科学学习手札

(数据科学学习手札36)tensorflow实现MLP

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

48540
来自专栏机器学习算法与Python学习

支持向量机(SVM)--(4)

回忆:在上一篇文章中我们谈到为了使支持向量机能够处理非线性问题,进而引进核函数,将输入空间的输入数据集通过一个满足Mercer核条件的核函数映射到更高...

33660
来自专栏AI科技大本营的专栏

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

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

36540
来自专栏机器学习算法与理论

与人脸有关的模型总结

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

29980
来自专栏郭耀华‘s Blog

MaxPooling的作用

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

30470
来自专栏AI研习社

理解 YOLO 目标检测

这篇文章从它的角度解释了YOLO目标检测结构。它将不会描述网络的优缺点以及每个网络设计如何选择的原因。相反的,它关注的是网络是如何工作的。在你阅读之前,你应该对...

22830
来自专栏决胜机器学习

机器学习(十五) ——logistic回归实践

机器学习(十五)——logistic回归实践 (原创内容,转载请注明来源,谢谢) 一、概述 logistic回归的核心是sigmoid函数,以...

375100
来自专栏Petrichor的专栏

论文阅读: R-FCN

由上表易知,R-FCN就是为了 解决 不共享的proposal处理过程 而诞生的。

30630

扫码关注云+社区

领取腾讯云代金券