专栏首页数据魔术师运筹学教学|十分钟快速掌握单纯形法(附C++代码及算例)

运筹学教学|十分钟快速掌握单纯形法(附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),作者:优创突击队

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 死里逃生?机器学习算法揭露泰坦尼克号幸存者之谜

    影片根据真实事件改编,片中的泰坦尼克号是英国白星航运公司下辖的一艘奥林匹克级邮轮,于1909年动工建造,1912年首次航行。1912年4月15日,在首次航行期间...

    用户1621951
  • 运筹学教学|运输问题代码分享(C++代码及详细注释)

    经过了长时间的学习……小编终于学会了运输问题(Transportation Problem),可以说是很骄傲了!然而……今天老板突然给了小编一个规模巨大的问题去...

    用户1621951
  • 干货 | 关于数学规划求解器lp_solve 超全面超详细的教程

    Mixed Integer Linear Programming (MILP) solver lp_solve solves pure linear, (mix...

    用户1621951
  • VBA程序的变量和常量

    大家好,在本节就主要介绍变量和常量,主要掌握声明变量和变量赋值,变量的作用域和存活期需要理解。

    无言之月
  • 机器学习实战 | 数据探索(变量变换、生成)

    1.1、什么是变量变换? 在数据建模中,变换是指通过函数替换变量。 例如,通过平方/立方根或对数x替换变量x是一个变换。 换句话说,变换是一个改变变量与其他变量...

    用户1332428
  • 如何用spss做一般(含虚拟变量)多元线性回归

    回归一直是个很重要的主题。因为在数据分析的领域里边,模型重要的也是主要的作用包括两个方面,一是发现,一是预测。而很多时候我们就要通过回归来进行预测。关...

    小莹莹
  • Powershell中的变量

    在我们的迷你系列“Variables in Shells”中,了解如何在PowerShell中处理局部变量。

    QRosie
  • 浅析互信息与特征选择

    那么什么是互信息呢?变量x与变量y之间的互信息,可以用来衡量已知变量x时变量y的不确定性减少的程度,同样的,也可以衡量已知变量y时变量x的不确定性减少的程度。

    用户1908973
  • 一文读懂R中的探索性数据分析

    探索性数据分析(EDA)是数据项目的第一步。我们将创建一个代码模板来实现这一功能。 简介 EDA由单变量(1个变量)和双变量(2个变量)分析组成。

    1480
  • C - 基础总结

    xx_Cc

扫码关注云+社区

领取腾讯云代金券