谈一谈|浅谈单纯形法其中奥妙

简介: 谈一谈|浅谈单纯形法其中奥妙

1单纯形法简介

单纯形法是求解线性规划问题最常用、最有效的算法之一。基本思路是:先找出可行域的一个顶点,据一定规则判断其是否最优;若否,则转换到与之相邻的另一顶点,并使目标函数值更优;如此下去,直到找到某最优解为止。

单纯形法的原理可以简单理解成将解通过枚举得出来,但是这个方法很巧妙得减少了枚举的次数,这也是单纯形法中很关键的一个步骤:换基迭代。在换基迭代中,主要需要解决两个问题:

(1)、出基变量的确定

(2)、入基变量的确定

在解决这两个问题时,单纯形法给出了明确的定义,可其中原理是什么呢?我们下面来分析一下。


2原理分析

如下是一张初始单纯形表

表2.1标准型初始单纯形表

对于一个标准型线性规划问题

使用矩阵形式表示上面的标准型:

其中,XB构成了初始基变量,因此,初始可行解可以得出

根据矩阵的运算规律,XB=B-1b,所以,初始可行解还可以表示为:

目标函数

由2式可以得出

将5式带入1式,有

其中m代表基变量的个数,Pj参考标准型,结合矩阵的知识,知道

6式中,选取一个合适的XK,其他的非基变量全为0,只要它的检验数大于0,就可以让函数值增大。每次选择检验数最大正值对应的XK,达到的效果最好,这就是换入变量的确定。

且此时,目标函数变为:

再根据下面中XB必须大于等于0,可以计算出XK的取值范围,

所以,

只要将对应的Xi替换成Xk,函数值就会增大(Ck-Zk)Xk这就是换出变量的确定。然后一直迭代,直到找到最优解或者判断出无解,就可以解决线性规划问题。


3阅读背景

上述分析思路建立在矩阵的基础上,所以需要一定的线性代数的知识作为支撑,这里只分析了标准型单纯形法的思路,对于改进的单纯形法没有深入,所以在理解时也要结合标准型线性规划问题,对于其他的单纯形法,还需要结合它的使用方法具体分析。

目录
相关文章
|
2月前
|
人工智能 前端开发 架构师
2025年前端局势分析,我该不该转行?
2024年,前端领域经历了快速变化,AIGC的兴起和市场HC减少使得前端工程师面临挑战。尽管AI工具如通义灵码和Cursor能高效生成代码,但AI无法完全取代前端工程师,因其缺乏逻辑、沟通和创新能力。前端工作不仅限于编码,还包括需求分析、代码评审等。未来,前端不会“死亡”,而是持续演变。面对大环境的压力,提升综合能力、拥抱变化、持续学习和保持身心健康是关键。转型方向包括升管理、做架构师或转讲师等。稳住2025年,需适应变化、不断学习并探索更多可能性。
323 16
|
存储 设计模式 缓存
揭秘通信协议设计的奥妙,作为面试官我都看蒙了
所谓的通信协议就是通信双方共同遵循的一种“约定”,用于通信发送方将内容按照“通信协议”所规定的格式组装成**“二进制流”**,通信接收方按照“通信协议”所规定的格式正确的从二进制流中解码出一个个原始请求。
|
新零售 数据挖掘 大数据
新零售的真相藏在哪?你需要知道这三点
2016年11月,马云在云栖大会提出“未来将没有电商,只有新零售”;两年后的今天,“新零售”已经遍地开花。从体感来看,智慧门店、快闪店正在更新人们的购物体验;数据来看,“新零售”带动线下消费成回暖趋势。
|
人工智能 大数据
大咖 | 车品觉:我们为什么要认识数据的本质
时下仿佛大家都在谈人工智能,就像当年人人都在谈大数据一样。在不同场合上,阿里巴巴的马云、百度的李彦宏及腾讯的马化腾分别谈过自己对人工智能的看法和观点。这种对话有点儿像金庸小说中的华山论剑。到底是气宗( 大数据)还是剑宗(人工智能)更有战略意义?我认为,两者是相辅相成的。
1627 0
|
安全
淘宝造物节2017十大神店:一言不合自己造!
买不到心仪球鞋,一言不合自己造,上海男生罗汉干脆在淘宝上做起手绘球鞋; 做正经的书法家太枯燥,一言不合自己造,朱敬一用“段子书法”杀出一片天地; 如今木匠们重款式而轻工艺,一言不合自己造,62岁郑安全专攻榫卯,让“爸爸的木匠小屋”意外走红;中式童装“成人气”十足,一言不合自己造,两个法国人在北京胡同设计“法式唐装”——“tangroulou”,让刘烨家的诺一追爱不已。
2470 0
|
存储 安全 大数据
确认过眼神?上云之路需要遇上对的人!
在“上云就上阿里云”解决了上什么云的问题之后,如何上云成为企业技术人员头疼的问题。业务系统云上应用基础架构应该如何设计、系统存储与数据库如何才能平滑迁移等等成为企业上云之路的障碍。为了解决企业上云前的痛点,阿里云支持与服务团队重磅推出咨询与设计场景下五款专家服务产品。