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

国庆节就要到了!

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

南京?丽江?西安?……

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

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

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

前几日有童鞋跟小编说,

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

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

戳此了解或复习:

运筹学教学 | 十分钟快速掌握最大流算法(附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)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-09-29

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P3819 松江1843路

题目描述 涞坊路是一条长L米的道路,道路上的坐标范围从0到L,路上有N座房子,第i座房子建在坐标为 的地方,其中住了 人。 松江1843路公交车要在这条路上...

3196
来自专栏量化投资与机器学习

【深入研究】使用RNN预测股票价格系列二

接昨天的 系列一(可点击查看) 在系列一的教程中,我们想继续有关股票价格预测的主题,并赋予在系列1中建立的具有对多个股票做出响应能力的RNN。 为了区分不同价格...

3688
来自专栏PPV课数据科学社区

【大数据问答】SPSS是如何做到发现数据质量问题,例如,如何发现缺失值?

SPSS是如何做到发现数据质量问题,例如,如何发现缺失值? (1)系统缺失值、空白值 每一个变量均有可能出现系统缺失或者空白,当数据量巨大时我们根本无法用眼睛...

4064
来自专栏黄成甲

数据分析之数据处理

数据处理是根据数据分析目的,将收集到的数据,用适当的处理方法进行加工、整理,形成适合数据分析的要求样式,它是数据分析前必不可少的工作,并且在整个数据分析工作量中...

1772
来自专栏书山有路勤为径

目标跟踪与定位——状态与定位

卡尔曼滤波器可以结合不准确的传感器测量和稍微不准确的运动预测,以获得比仅来自传感器读数或仅有关运动的任何更好估计位置。

2132
来自专栏数据结构与算法

2853 方格游戏(三维棋盘)

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 菜菜看到了...

3536
来自专栏新智元

【邓侃】哈佛大学机器翻译开源项目 OpenNMT的工作原理

【新智元导读】 2016年12月20日,哈佛大学自然语言处理研究组,宣布开源了他们研发的机器翻译系统 OpenNMT ,并声称该系统的质量已经达到商用水准。本文...

4845
来自专栏数据结构与算法

Day5网络流

算法 无源汇上下界可行流 ?  先强制流过l的流量 从s到每个正权点连流量为l的流量  从每个负权点向t连-l的流量 如果容量为0,则不连边 有源汇上下界最大流...

3029
来自专栏xingoo, 一个梦想做发明家的程序员

动态规划

基本思想:将待求解问题分解成若干子问题,先求解子问题,然后从子问题的解中得到原问题的解。 与分治不同的是,经分解得到的子问题往往不是互相独立的。 若用分治法来解...

1915
来自专栏深度学习自然语言处理

【概率笔记】条件概率这样学才快啦

比如,一个上学期间整天鬼混的学沫,根本就不好好学习,对于他而言,选择题的四个选项ABCD被他选取的概率就为1/4。而对于大学霸来说,题题都会,那么他选取每一个选...

863

扫码关注云+社区