线性规划单纯形法python实现_梓铭zyb的博客-程序员信息网_python实现单纯形法

技术标签: python  

用python实现线性规划中的单纯形法

例题如下(已是标准形式):
m a x z = 1500 x 1 + 1000 x 2 max z=1500x_1+1000x_2 maxz=1500x1+1000x2

{ 3 x 1 + 2 x 2 + x 3 = 65 2 x 1 + x 2 + x 4 = 40 3 x 2 + x 5 = 75 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 \left\{ \begin{array}{c} 3x_1+2x_2+x_3=65 \\ 2x_1+x_2+x_4=40 \\ 3x_2+x_5=75\\ x_1,x_2,x_3,x_4,x_5\geq0 \end{array} \right. 3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50

代码如下:

#输入变量的数量
arg_num = int(input())
#输入目标函数
max_z = list(map(int,input().split(' ')))
z = 0
x = {
    }

class pure_chat():
    def __init__(self):
        self.c_b = []
        self.b = []
        self.opt = []
        self.no_base_args = []
        self.ex_num_list = max_z[:]
	
	#输入约束条件
    def input_chat(self):
        for i in range(len(max_z)):
            if max_z[i] != 0:
                self.no_base_args.append(i)

        while True:
            exper = list(map(int, input().split(' ')))
            if exper.count(0) == arg_num + 1:
                break
            self.opt.append(exper)

        for i in range(arg_num - len(self.opt) + 1):
            self.b.append(arg_num - len(self.opt) + i)
            self.c_b.append(max_z[arg_num - len(self.opt) + i])

    def get_max(self):
        m_i = 0
        max = -10000
        for i in self.no_base_args:
            if self.ex_num_list[i] > max:
                max = self.ex_num_list[i]
                m_i = i
        return m_i

	#判断非基变量的检验数是否都为小于0
    def examine(self):
        for i in self.no_base_args:
            if self.ex_num_list[i] > 0:
                return False
        return True
        
	#确定出基变量
    def out_base(self):
        min = 100000
        i = self.get_max()
        if self.ex_num_list[i] > 0:
            for j in range(len(self.opt)):
                if self.opt[j][i] == 0:
                    continue
                t = self.opt[j][arg_num] / self.opt[j][i]
                if t < min:
                    min = t
                    out_i = i
                    out_j = j
        return out_i, out_j
	
	#将基变量矩阵化为单位矩阵
    def to_e(self,b_i, b_j):
        s = self.opt[b_i][b_j]
        for i in range(len(self.opt[b_i])):
            self.opt[b_i][i] = self.opt[b_i][i] / s
        for j in range(len(self.opt)):
            if j != b_i:
                t = self.opt[j][b_j]
                for k in range(len(self.opt[j])):
                    self.opt[j][k] = self.opt[j][k] - t * self.opt[b_i][k]

	#出基与进基
    def change_base_args(self,b_i, b_j):
        t = self.no_base_args.index(b_j)
        self.no_base_args[t] = self.b[b_i]
        self.b[b_i] = b_j

	#更新基变量的系数矩阵
    def update_c_b(self):
        for i in range(len(self.b)):
            self.c_b[i] = max_z[self.b[i]]
	
	#计算检验数
    def compute_ex_num(self,b_i, b_j):
        self.ex_num_list[b_j] = 0
        for i in self.no_base_args:
            s = max_z[i]
            count = 0
            for j in self.b:
                s = s - max_z[j] * self.opt[count][i]
                count += 1
            self.ex_num_list[i] = s

	#计算目标函数值
    def compute_z(self):
        s = 0
        for i in range(len(self.opt)):
            s = s + self.c_b[i] * self.opt[i][arg_num]
        return s

	#计算最优解
    def compute_x(self):
        for i in range(len(self.opt)):
            x[self.b[i]] = self.opt[i][arg_num]
        for i in range(arg_num):
            if i not in self.b:
                x[i] = 0


chat = pure_chat()
chat.input_chat()

#循环迭代
while True:
    if chat.examine():
        chat.compute_x()
        x = sorted(x.items(), key=lambda x: x[0])
        z = chat.compute_z()
        break
    j,i = chat.out_base()
    chat.change_base_args(i,j)
    chat.update_c_b()
    chat.to_e(i,j)
    chat.compute_ex_num(i,j)

print(x)
print(z)

'''

测试数据:
5
1500 1000 0 0 0
3 2 1 0 0 65
2 1 0 1 0 40
0 3 0 0 1 75
0 0 0 0 0 0

输出的结果:
[(0, 15.0), (1, 10.0), (2, 0), (3, 0), (4, 45.0)]
32500.0

'''

输入的数据格式为:
5
1500 1000 0 0 0
3 2 1 0 0 65
2 1 0 1 0 40
0 3 0 0 1 75
0 0 0 0 0 0

第一行的5为变量的个数,第二行为目标函数中的对应系数,其余行为约束条件的对应系数,最后输入全0表示结束输入

输出的结果为:
[(0, 15.0), (1, 10.0), (2, 0), (3, 0), (4, 45.0)]
32500.0

第一行的列表表示最优解,为 x 1 = 15 , x 2 = 10 , x 3 = 0 , x 4 = 0 , x 5 = 45 x_1=15,x_2=10,x_3=0,x_4=0,x_5=45 x1=15,x2=10,x3=0,x4=0,x5=45;第二行为最优解对应的最优目标函数值,为32500.

ps:个人github地址:https://github.com/zhouyanb
github地址

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zhouybing/article/details/117156298

智能推荐

创建可引导的 macOS 安装 U 盘_ 吖 頭的博客-程序员信息网

1、准备和条件下载 macOS当前版本: macOS Big Sur 11.2.3 (20D91) 正式版Mac OS Big Sur 11.2.1支持以下型号iMac 2014+iMac Pro 2017+Mac Pro 2013+MacMini 2014+MacBook 2015+MacBook Air 2013+MacBook Pro 2013+要保证下载的安装包 Install macOS .app*(“安装 macOS [版本名称]”的 App)**在“应用程序”文件夹。在

src与href属性的区别_叶才鑫的博客-程序员信息网

src和href之间存在区别,能混淆使用。src用于替换当前元素,href用于在当前文档和引用资源之间确立联系。

expo打包安卓 ios_挺不下的脚步的博客-程序员信息网

npm install -g exp运行exp build:android或exp build:ios

Tree_NC161_潇雨墨临的博客-程序员信息网

二叉树的中序遍历描述给定一个二叉树的根节点root,返回它的中序遍历。解题二叉树public class TreeNode{ int val; TreeNode left = null; TreeNode right = null; public TreeNode(int val){ this.val=val; }}Solution/** * 递归中序遍历,列表 */import java.util.ArrayList;imp

homework2_ZhankunLuo_dassein的博客-程序员信息网

Zhankun LuoPUID: 0031195279Email: [email protected]: Toma Hentea#Homework 2文章目录Problem 2.12(a) Bayesian classifier that minimizes the error probability(b) Bayesian ...

mybatis 启动时死循环的问题分析_viaco2love的博客-程序员信息网

MyBatis 最常见错误,启动时控制台无限输出日志Java-Mybatis中Mapper文件过多,引起java.lang.StackOverflowError - 文江博客MyBatis防止死循环_asing1elife's blog-程序员信息网_mybatis死循环Java-Mybatis中Mapper文件过多,引起java.lang.StackOverflowError​​​​​​​如果出现死循环,问题很复杂,所以要懂得自己分析第一步找出问题//找到org.springfra

随便推点

[存档]使用.Net开发web程序时现在比较流行的前台技术都有什么?_weixin_30736301的博客-程序员信息网

如题,我一直做winform项目,过些天有个web项目。我想知道前台设计现在流行什么呀,Silverlight、ExtJS还是JQuery等。另外开发web程序有没有什么流行的框架呀。像java的Spring、Structs和等。我对web项目实在是不熟,正在熬夜学习呢,大家还有其他的好提议也可以说说啊。谢谢。最佳答案--------------------------------...

2015年中国互联网大检阅_david_lv的博客-程序员信息网

此数据来自互联网周刊:2015中国互联网TOP 500排行榜我重新整理的目的是:按类别来归集,看看有哪些类别,哪些类别冷,哪些类别热,还有哪些类别在产业链上还有空缺环节。...

机器学习的分类与主要算法对比_yamaxifeng_132的博客-程序员信息网

重要引用:Andrew Ng Courera Machine Learning;从机器学习谈起;关于机器学习的讨论;机器学习常见算法分类汇总;LeNet Homepage;pluskid svm  首先让我们瞻仰一下当今机器学习领域的执牛耳者:  这幅图上的三人是当今机器学习界的执牛耳者。中间的是Geoffrey Hinton, 加拿大多伦多大学的教授,如今被聘为“Google大脑”的...

java程序员的NodeJS初识篇_weixin_30602505的博客-程序员信息网

摘要作为一个一直用java来写后端的程序员用NodeJS来写后台,实在不是很爽。这里记下这两个月的NodeJS学习所遇之坑,与java转NodeJS的同仁共勉。学习时间不长,若有理解错误,望指正。一.JS基本exports,module.exportsexports 就是module.exports的引用在module 被计算之前,会将module....

软件测试工程师好就业吗?软件测试工程师发展空间怎么样?_代码小怡的博客-程序员信息网_软件测试工程师怎么样

随着学习软件工程的人越来越多,人们对软件工程就业前景开始有了误解,有的人认为软件工程就业前景开始趋于饱和,今天小编就来为大家详细介绍一下。

百度云远程连接自己的云服务器,_一位不愿透露姓名的赵先生的博客-程序员信息网_百度云服务器怎么远程连接

作为一个菜鸟,在什么都不知道的情况下,贸然申请了个云服务器。。。。。。备案完,才知道,没有自己想象中那么简单,首先,当时百度云搞活动,购买了个云服务器BCC,在备案完之后,以为按照网上的建站视频,可以自己建一个,但是按照步骤总有一些不同,然后发现,视频里讲的是虚拟主机BCH,(对于百度云来说的话,BCC和BCH的资源都是独享型的。区别就在于BCH虚拟主机已经帮你配置好相关的网站环境。还有一...

推荐文章

热门文章

相关标签