Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >运筹学教学|十分钟快速掌握单纯形法(附C++代码及算例)

运筹学教学|十分钟快速掌握单纯形法(附C++代码及算例)

作者头像
用户1621951
发布于 2018-04-19 09:06:52
发布于 2018-04-19 09:06:52
4.3K0
举报
文章被收录于专栏:数据魔术师数据魔术师
国庆节就要到了!

不如今儿咱就来讨论一下去哪玩耍吧!

南京?丽江?西安?……

众人(汗):一个月前就没票了。。。

哦……那么,就只能……学习了……

好巧不巧,运筹学似乎没学完吧?

前几日有童鞋跟小编说,

深夜看了咱公众号运筹学最大流、最短路算法的教学,

在修仙的道路上又有了质的飞跃!

戳此了解或复习:

运筹学教学 | 十分钟快速掌握最大流算法(附C++代码及算例)

运筹学教学 | 十分钟快速掌握最短路算法(附C++代码及算例)

但就是……

信息量太大,

学完后有点虚,

快学不动了……

古语云:持之以恒,有朝一日,必可成仙。

这位同学再坚持一下……

(好吧前面那句话其实是我说的)

毕竟运筹学是一门博大精深的学问。

但小编非常体谅大家要亲亲抱抱举高高的心情,所以今天要教给大家的知识着实单纯小清新。怎么样,是不是开心到质壁分离?

那就快来看看今天的内容吧!

运筹学·教学笔记 第三弹 —— 单纯形法 (Simplex Algorithm)解 线性规划 问题。包你一学就会!怎么样,内容是不是真的很单纯?

内容提要:

*什么是线性规划

*线性规划的标准式和矩阵式

*单纯形法的算法步骤

1

1

1

什么是线性规划

线性规划(Linear programming, 简称LP)是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它辅助人们进行科学管理、寻找线性约束条件下线性目标函数极值。它广泛应用于军事作战、经济分析、经营管理和工程技术等领域,为合理地利用有限的人力、物力、财力等资源做出最优决策,提供科学依据。

1

2

1

标准式VS矩阵式

标准式

由于目标函数和约束条件在内容和形式上存在多种差别,线性规划问题也存在着多种表达式。因此,为了便于讨论,在应用单纯形法时,规定线性规划问题必须有一个标准形式,主要包括以下三个特征:

1)目标函数统一为求极大值(或极小值);

2)所有约束条件(除变量的非负条件外)必须都是等式,约束条件右端常数项(right-hand-side)b_i必须全为非负值

3)所有变量的取值必须全为非负值

下面的模型即为线性规划问题的标准形式:

s.t.括号内的内容是约束条件和变量的非负约束条件,字母代表的含义分别是:

下面模型即为标准形式的展开型:

可行解与 最优解

若找到(x_1, x_2 ,..., x_n)的值满足所有约束条件,且每个变量的值非负,则(x_1, x_2 ,..., x_n)称为线性规划问题的可行解。使目标函数值达到最大值(或最小值)的可行解即为该问题最优解,求解线性规划问题的目标就是要找出目标函数的最优解。

如何将目标函数转化为标准型

如下所示,线性规划问题往往并非标准形式。

因此,在用单纯形法求解前,需要将模型转化为标准形式。

这个过程包括四个部分的转换:

1. 目标函数的转换:

统一求极大值,若是求极小值,则可将下面的式子乘以(-1)。即:

转化为:

2. 变量的转换:

(1)对于已经是大于等于零的变量 x_j ≥ 0 不做变化

(2)对于小于等于零的变量 x_j,取负号令其变为大于等于零的变量,即若 x_j ≤ 0,则 定义新变量x_j' = -x_j,x_j' ≥ 0;

(3)若 x_j 取值无约束,可令两个新的非负变量x_j', x_j'', 然后用x_j = x_j' - x_j''替换原问题中的x_j。

3. 约束条件的右端项常数的转换:

b_i < 0 时,只需将等式或不等式两端同乘(-1);

4. 约束条件的转换:

将所有不等式全部转换为等式:

对于“≤ ”型约束加入一个变量 x_s,x_s ≥ 0;

对于“≥ ”型约束则减去一个变量 x_s,x_s ≥ 0。

加到原约束条件中的变量,称为松弛变量,在实际问题中它表示未被充分利用的资源或缺少的资源,所以在引入模型后它们在目标函数中的系数均为零

给定线性模型的标准形式,为了构造出初始基变量,约束条件还可能需要加上人工变量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0,在目标函数中令其系数为M。M为无限大的正数,这是一个惩罚项,倘若人工变量不为零,则目标函数就永远达不到最优,所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去,那么这个问题就没有可行解,当然亦无最优解。

【Tips: 若原约束条件中已有线性无关的基向量,可以不需要再加入人工变量

学完了以上的转化规则,让我们来实战一下!将上述的线性规划问题转化为标准形式,其结果应如下:

注:x_4, x_5是将自由变量x_3转化为非负变量而引入的新变量,x_6, x_7是松弛变量,x_8, x_9是人工变量。

对于聪明的你来说是不是很简单?

矩阵式

说完标准形式,再来说说为了运算简洁而生的矩阵式。因为表达方式简单,单纯形法的表示与定理的说明往往使用矩阵形式。上述标准形式的矩阵形式表示如下:

矩阵A如下式:

A为m×n矩阵。假设A的秩为m,即假设不存在冗余的约束条件,则m>n时,因为方程数量比变量数目多,必定有多个可行解,即可利用单纯形法来计算最优解。

1

3

1

单纯形法的算法步骤

使用单纯形算法求解线性规划,求解时只需输入线性规划问题的标准式 ——

一个大矩阵:

第一行为目标函数的系数,最后一个数字为当前基变量下的 z 值。

首行以下的每一行代表一个约束条件,数字代表系数,每行最后一个数字代表 b 值。

单纯形法解题步骤

1. 确定初始可行基初始基可行解

建立初始单纯形表;

2. 最优性检验 若在当前表的目标函数对应的行中,所有非基变量的系数非正,则可判断得到最优解,可停止计算。否则转入下一步;

3. 若单纯形表中1至m列构成单位矩阵,在j=m+1至n列中,若有某个对应x_k的系数列向量 P_k ≤ 0,则此问题是无界,停止计算。否则,转入下一步;

4. 挑选目标函数对应行中系数最大的非基变量作为进基变量。假设x_k为进基变量,按θ规则[1]计算,可确定x_l为出基变量,转下一步;

5. a_lk为主元素进行迭代(即用高斯消去法或称为旋转运算),把x_k所对应的列向量进行变换[2];

6. 重复2-5步,直到所有检验数非正后终止,得到最优解。

[1] θ规则

其中b_i是当前表中的右手项,a_ik即为在第i个约束中变量k的系数。

[2] x_k列变换

单纯形法举例

对于线性规划问题:

加入松弛变量,转化为标准形式得:

于是我们可以构造单纯形表,其中最后一行有星号的列为基变量。初始基可行解为(x_4, x_5, x_6, x_7)。

在单纯形表中,我们发现非基变量x的系数大于零,因此可以通过增加这些x的值,来使目标函数增加。

上表中c_2最大,因此我们选择x_2作为新的基变量。按照θ规则,x_7出基。通过高斯变换得到的新的单纯形表为:

继续计算,我们得到:

此时我们发现,所有非基变量的系数全部非正,即增大任何基变量的值并不能使得目标函数增大。于是我们可以断定该问题的最优解是z = 32, X = (0, 1, 3, 0, 2, 0, 0).

恭~喜~大~家~,到这里单纯形法的原理就

搞!定!啦!

如约而至的,仍旧是我们的代码(C++版),若想获得代码.txt文件,可以直接滑到本文最后,点击“阅读原文”下载哦~下载只需复制黏贴即可,so easy~

代码展示

下面的代码仅仅是实现了教科书中的单纯形法的流程,线性规划商业软件在实际单纯形法的时候,会考虑约束条件的合理性以及可能出现退化等诸多复杂情况,因此,商业软件中实现的单纯形法肯定比下面展示的算法要复杂的多。

1

END

编辑:唐清清(华中科技大学管理学院本科三年级,15295970390@163.com)

孙嘉轩(华中科技大学管理学院本科二年级,1143747930@qq.com)

代码:孙嘉轩、贺兴(华中科技大学管理学院本科三年级,hexing15@gmail.com)

指导老师:秦时明岳(professor.qin@qq.com)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2017-09-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 数据魔术师 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
运筹学教学|十分钟快速掌握割平面法及对偶单纯形法(附Java代码及算例)
过去一段时间里小编一直接触启发式算法,自从学习了运筹学以后,就对运筹学的精确方法垂涎已久,像什么单纯形法啦,分支定界啦,割平面啦...... 就在小编一边做梦一边睡大觉的时候,boss发来一个任务:用Gomory割平面法求解混合整数规划问题。于是小编马上从床上跳起来,挑灯夜战为大家整出了这个代码...
用户1621951
2020/12/31
3.9K0
运筹学教学|十分钟快速掌握割平面法及对偶单纯形法(附Java代码及算例)
运筹学单纯形法求解线性规划问题_运筹学单纯形法计算步骤
线性规划是研究在一组线性不等式或等式约束下使得某一线性目标函数取最大(或最小)的极值问题。
全栈程序员站长
2022/09/20
1K0
运筹学单纯形法求解线性规划问题_运筹学单纯形法计算步骤
运筹学教学|快速掌握人工变量法(Artificial variable method)(附Java代码及算例)
在之前的推文中,我们学习了单纯形法,顺利解决了约束条件都是“≤”的线性规划问题。同时为了讲解方便,我们都是使用约束方程系数矩阵中带单位矩阵、约束符号为“=”的算例。那肯定有人会问小编:更加常规的线性规划问题如何求解呢?为了响应群众号召,今天,小编就来带大家了解一下人工变量法!学会之后,“≤”“≥”或“=”型的约束的线性规划问题都顺利解决,妥妥的~
用户1621951
2021/03/16
6K1
运筹教学|快速掌握单纯形法(附java代码)
线性规划(Linear programming, 简称LP)是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它辅助人们进行科学管理、寻找线性约束条件下线性目标函数的极值。它广泛应用于军事作战、经济分析、经营管理和工程技术等领域,为合理地利用有限的人力、物力、财力等资源做出最优决策,提供科学依据。线性规划一般由决策变量、约束条件和目标函数三个部分组成。
用户1621951
2023/01/05
1.2K0
运筹教学|快速掌握单纯形法(附java代码)
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 线性规划求解示例 )
在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 ) 博客中讲解了最优解判定原则 , 基本原理就是
韩曙亮
2023/03/28
1.9K0
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 线性规划求解示例 )
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 )
在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 ) 中 , 讲解到了使用单纯形法求解线性规划问题 , 需要解决以下三个主要问题 :
韩曙亮
2023/03/28
1.3K0
【运筹学】线性规划 单纯形法 阶段总结 ( 初始基可行解 | 判定最优解 | 迭代 | 得到最优解 | 全流程详细解析 ) ★
参考 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) 线性规划 普通形式 -> 标准形式 转化顺序说明 博客 , 先处理变量约束 , 再将不等式转为等式 , 最后更新目标函数 ;
韩曙亮
2023/03/28
2.3K0
【运筹学】线性规划 单纯形法 阶段总结 ( 初始基可行解 | 判定最优解 | 迭代 | 得到最优解 | 全流程详细解析 ) ★
【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 )
在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 线性规划求解示例 ) 博客给出了一个线性规划的示例 , 并进行了 查找初始基可行解 , 和 判定该基可行解是否是最优解 ;
韩曙亮
2023/03/28
1.4K0
【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 )
【运筹学】线性规划 人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 )
迭代转化 : 其将 在无穷多个可行解中迭代 , 转化为了 在有限个基可行解中进行迭代 ;
韩曙亮
2023/03/28
1.8K0
【运筹学】对偶理论总结 ( 对称性质 | 弱对偶定理 | 最优性定理 | 强对偶性 | 互补松弛定理 ) ★★★
约束条件与约束变量的对应关系 ( 目标函数求最大值 ) : 这里特别注意 , 约束条件与约束变量 大于小于符号是相反的 ;
韩曙亮
2023/03/28
2.6K0
【运筹学】对偶理论总结 ( 对称性质 | 弱对偶定理 | 最优性定理 | 强对偶性 | 互补松弛定理 ) ★★★
【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 )
( 可行域是凸集 ) : 如果线性规划的问题 存在可行解 , 其 可行域 必定是 凸集 ;
韩曙亮
2023/03/28
1.4K0
【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 )
【运筹学】线性规划 单纯形法 ( 原理 | 约定符号 | 目标系数矩阵 C | 目标函数变量矩阵 X | 约束方程常数矩阵 b | 系数矩阵 A | 向量 | 向量符号 | 向量 Pj )
2. 单纯形法引入 : 在线性规划中 , 约束方程个数 , 一般情况下会小于变量个数 , 因此会有多个解 , 单纯形法就是针对这种情况求解的方法 , 可以得到符合要求的线性规划的最优解 ;
韩曙亮
2023/03/27
1.4K0
【运筹学】线性规划 单纯形法  ( 原理 | 约定符号 | 目标系数矩阵 C | 目标函数变量矩阵 X | 约束方程常数矩阵 b | 系数矩阵 A | 向量 | 向量符号 | 向量 Pj )
【运筹学】运输规划 ( 运输规划问题模型及变化 | 表上作业法引入 )
③ 产销不平衡 , 参考 【运筹学】运输规划 ( 运输规划基变量个数 | 运输问题一般形式 | 产销平衡 | 产销不平衡 ) 三、运输规划中的产销( 不 )平衡问题 ;
韩曙亮
2023/03/28
8240
【运筹学】运输规划 ( 运输规划问题模型及变化 | 表上作业法引入 )
【运筹学】线性规划数学模型 ( 单纯形法 | 第一次迭代 | 方程组同解变换 | 计算新单纯形表 | 计算检验数 | 入基变量选择 | 出基变量选择 )
上篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 ) 讲解了单纯形法中选择了入基变量 , 与出基变量 , 找到了下一组迭代的可行基 , 下面开始继续进行后续操作 ;
韩曙亮
2023/03/28
1.2K0
【运筹学】线性规划数学模型 ( 单纯形法 | 第一次迭代 | 方程组同解变换 | 计算新单纯形表 | 计算检验数 | 入基变量选择 | 出基变量选择 )
线性规划之单纯形法【超详解+图解】
1.作用     单纯形法是解决线性规划问题的一个有效的算法。线性规划就是在一组线性约束条件下,求解目标函数最优解的问题。 2.线性规划的一般形式     在约束条件下,寻找目标函数z的最大值。 3.
Angel_Kitty
2018/04/09
33K0
线性规划之单纯形法【超详解+图解】
数值优化(A)——线性规划中的单纯形法与内点法
在这一节我们会给大家介绍带约束优化中更为具体的线性规划的内容。相信大家在运筹学中会对线性规划更加熟悉,比方说单纯形法就是运筹学一开始就会讲授的内容。那么在优化中,我们也会关注它们,通过介绍他们来了解优化在运筹中的应用,也能够让大家更好的了解为什么“运筹优化”一般都放在一起来说。
学弱猹
2021/08/09
1.7K0
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 )
在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 ) 博客中讲解了最优解判定的推导过程 , 基本原理就是
韩曙亮
2023/03/28
1.1K0
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 )
【运筹学】线性规划 人工变量法 ( 人工变量法案例 | 初始单纯形表 | 检验数计算 | 入基变量 | 出基变量 )
上一篇博客 【运筹学】线性规划 人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 ) 中 , 介绍了人工变量法 , 主要用于解决线性规划标准形式中 , 初始系数矩阵中没有单位阵的情况 , 并给出一个案例 , 本篇博客中继续使用人工变量法解解上述线性规划问题 ;
韩曙亮
2023/03/28
8330
【运筹学】线性规划 人工变量法 ( 人工变量法案例 | 初始单纯形表 | 检验数计算 | 入基变量 | 出基变量 )
运筹学考题汇总(填空题+计算题)带答案
❃运筹学的工作程序:分析和表述问题、建立模型、求解模型和优化方案、测试模型及对模型进行必要的修正、建立对解的有效控制、方案的实施。
荣仔_最靓的仔
2021/02/02
2.7K0
运筹学考题汇总(填空题+计算题)带答案
【运筹学】整数规划 ( 整数规划示例 | 整数规划解决的核心问题 )
根据 【运筹学】整数规划 ( 相关概念 | 整数规划 | 整数线性规划 | 整数线性规划分类 ) 博客中的整数线性规划概念 , 上述线性规划是 整数线性规划 ;
韩曙亮
2023/03/28
1K0
推荐阅读
运筹学教学|十分钟快速掌握割平面法及对偶单纯形法(附Java代码及算例)
3.9K0
运筹学单纯形法求解线性规划问题_运筹学单纯形法计算步骤
1K0
运筹学教学|快速掌握人工变量法(Artificial variable method)(附Java代码及算例)
6K1
运筹教学|快速掌握单纯形法(附java代码)
1.2K0
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 线性规划求解示例 )
1.9K0
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 )
1.3K0
【运筹学】线性规划 单纯形法 阶段总结 ( 初始基可行解 | 判定最优解 | 迭代 | 得到最优解 | 全流程详细解析 ) ★
2.3K0
【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 )
1.4K0
【运筹学】线性规划 人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 )
1.8K0
【运筹学】对偶理论总结 ( 对称性质 | 弱对偶定理 | 最优性定理 | 强对偶性 | 互补松弛定理 ) ★★★
2.6K0
【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 )
1.4K0
【运筹学】线性规划 单纯形法 ( 原理 | 约定符号 | 目标系数矩阵 C | 目标函数变量矩阵 X | 约束方程常数矩阵 b | 系数矩阵 A | 向量 | 向量符号 | 向量 Pj )
1.4K0
【运筹学】运输规划 ( 运输规划问题模型及变化 | 表上作业法引入 )
8240
【运筹学】线性规划数学模型 ( 单纯形法 | 第一次迭代 | 方程组同解变换 | 计算新单纯形表 | 计算检验数 | 入基变量选择 | 出基变量选择 )
1.2K0
线性规划之单纯形法【超详解+图解】
33K0
数值优化(A)——线性规划中的单纯形法与内点法
1.7K0
【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 )
1.1K0
【运筹学】线性规划 人工变量法 ( 人工变量法案例 | 初始单纯形表 | 检验数计算 | 入基变量 | 出基变量 )
8330
运筹学考题汇总(填空题+计算题)带答案
2.7K0
【运筹学】整数规划 ( 整数规划示例 | 整数规划解决的核心问题 )
1K0
相关推荐
运筹学教学|十分钟快速掌握割平面法及对偶单纯形法(附Java代码及算例)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档