【管理运筹学】运筹学“背诵手册”(一) | 线性规划问题与单纯形法

2023-11-11 22:12

本文主要是介绍【管理运筹学】运筹学“背诵手册”(一) | 线性规划问题与单纯形法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

引言

同数学一样,运筹学尽管大量的是计算题,但这些算法步骤及思路,还有涉及到的知识点如果不去整理和记忆,很难在短时间内正确求解出考题。比如指派问题的匈牙利法、排队论公式、运输问题的表上作业法等等,都是需要记忆的部分。下面就把个人认为容易遗忘的点整理起来,方便日后随时查阅。


一、线性规划问题与单纯形法

线性规划模型三个特点:1. 有决策变量,一般非负;2. 存在约束条件,用线性等式或不等式来表示;3. 有目标,可以用决策变量的线性函数来表示。

凸集的数学表达:设 Ω \Omega Ω n n n 维空间的点集,若任取 x 1 , x 2 ∈ Ω , 0 ≤ α ≤ 1 x_1,x_2\in \Omega,0\leq\alpha\leq1 x1,x2Ω,0α1 ,有 [ x 1 , x 2 ] = { x ∣ x = α x 1 + ( 1 − α ) x 2 } ⊂ Ω [x_1,x_2]=\{x|x=\alpha x_1+(1-\alpha)x_2\}\subset \Omega [x1,x2]={xx=αx1+(1α)x2}Ω 称点集 Ω \Omega Ω 为凸集。直观上来说,图形中连接任意两点的直线全部都落在图形区域内。

凸集的定义也提示我们,两点连线上的点可以用两个端点进行组合得到,因此在我们求出线性规划问题的两个最优解后(设有无穷多解),就可以用这个组合去求其他最优解。这也提示我们,线性规划问题的最优解不一定在顶点(不在任意不同两点连线上的点称为顶点)处取得,还可能在两个顶点所在连线上取得。

可行解: 满足所有约束条件且非负的解称为可行解。

基: 线性规划问题的约束系数矩阵 A m × n \pmb{A}_{m\times n} Am×n 的秩为 m ( m < n ) m(m<n) m(m<n) ,若 B \pmb{B} B A \pmb{A} A m m m 阶非奇异子矩阵(即 ∣ B ∣ ≠ 0 |\pmb{B}|\ne0 B=0),称 B \pmb{B} B 为一个基。

基解: 基对应的决策变量称为基变量,其他决策变量称为非基变量。令非基变量为 0 ,得到的解称为基解。如果从图形上来反映,所有约束条件方程的交点即为基解。以两个未知数为例,包括各条直线之间的交点和直线与坐标轴的交点以及坐标轴自身的交点。如果从数学角度来反映,有几个基就有几个基解,根据线性代数的内容, m × n m\times n m×n 矩阵(秩为 m m m )中最多有 C n m C_n^m Cnm m m m 阶非零子式,即 C n m C_n^m Cnm 个基解。

最优解: 满足所有约束条件,且使得目标函数值达到最优的决策变量取值。

退化解: 若基解中基变量的个数小于系数矩阵的秩,则称该解属于退化解。通俗点就是解中非零分量的个数小于决策变量的个数。

事实上,解中非零分量的个数最多为系数矩阵的秩,即独立约束条件的个数。因此若一个线性规划问题有两个独立的约束条件,则 ( 1 , 3 , 2 , 0 , 0 ) T (1,3,2,0,0)^T (1,3,2,0,0)T 不可能是该问题的解。

下面是几个定理:

  1. 线性规划问题若存在可行域(约束条件围成的区域),其必为凸集。
  2. 可行解为基可行解的充要条件是可行解中正分量对应的系数列向量线性独立。
  3. 线性规划问题的基可行解对应于可行域上的顶点。
  4. 若可行域有界,线性规划问题的目标函数一定可以在其可行域上达到最优。

2,3 提示我们,后面我们之所以找单位阵,就是因为单位阵对应的系数列向量肯定是独立的,因此它可以作为基可行解。而 4 提示我们,之所以要找顶点,是因为最优解一定可以在顶点上找到,这样就不用去所有可行域上找了。单纯形法每一次迭代就是从一个顶点跳到相邻的顶点。
另外需要注意,一个基可行解对应于可行域上的一个顶点,但并非一一对应,有可能出现多个基可行解对应于一个顶点的情况,比如退化解,这时尽管在反复迭代,但始终是在一个顶点上,因为可能永远找不到最优解。而后面提到的勃兰特规则可以帮助我们避免这一循环。

  1. 若目标函数在 k k k 个顶点处达到最优( k ≥ 2 k\geq2 k2),则在这些顶点的凸组合上也达到最优。

线性规划问题标准型的四个条件:1. 目标函数为最大化;2. 决策变量取非负值;3. 约束条件均为等式; 4. 每一约束等式右端常数均为非负。化为标准型有以下几种办法:1. 对于 min ⁡ \min min 型,令 z ′ = − z z'=-z z=z ;2. 对于 b i < 0 b_i<0 bi<0 ,约束条件两端乘 -1 ;3. 约束条件 ≤ \leq ,左端加上一个松弛变量;4. 约束条件为 ≥ \geq ,左端减去一个剩余变量;5. 决策变量 x j x_{j} xj 无约束,令 x j = x j ′ − x j ′ ′ , x j ′ , x j ′ ′ ≥ 0 x_j=x_j'-x_j'',x_j',x_j''\geq0 xj=xjxj′′,xj,xj′′0 ;6. 决策变量 x j ≤ 0 x_j\leq0 xj0 时,令 x j ′ = − x j x_j'=-x_j xj=xj

线性规划解的四种情况:

  1. 唯一最优解;
  2. 无穷多最优解;
  3. 无可行解(无解);
  4. 无界解(无最优解)。

线性规划问题规范型是指约束矩阵中含有一个单位阵。

最优解的判定定理: 若基可行解中的所有非基变量检验数 σ j = c j − z j ≤ 0 \sigma_j=c_j-z_j\leq0 σj=cjzj0 ,则该基可行解为最优解。

注意有一种特殊情况,那就是当基变量中含有非零的人工变量时,即使所有检验数都不大于 0 ,仍不是最优解,为无解。

无穷多最优解的判定定理: 若基可行解中的所有非基变量检验数 σ j = c j − z j ≤ 0 \sigma_j=c_j-z_j\leq0 σj=cjzj0 且存在某个非基变量检验数等于 0 ,则该线性规划问题有无穷多最优解。

把那个检验数为 0 的非基变量入基,可得到另外一个最优解,这两个解进行凸组合,可得到其他更多最优解。

无解解的判定定理: 基可行解中,存在某个非基变量对应的检验数 > 0 >0 >0 ,但其对应的约束矩阵元素均 ≤ 0 \leq 0 0 ,则该线性规划问题有无界解(也可以说是无最优解)。

入基原则,选择检验数最大的那个非基变量;出基原则,选择正的最小的比值 θ = b l / a l k \theta=b_l/a_lk θ=bl/alk 入基。

选择检验数最大的非基变量换入并不能保证目标函数最快的增长,还需保证同时选择 θ \theta θ 最小变量换出。

大 M 法(又称惩罚法),可以快速形成一个单位阵。常用的情况是在出现 ≥ \geq 的约束条件时,此时添加的剩余变量系数为 -1 ,需再添加一个人工变量。当目标为求最大时,人工变量的系数应为 -M ,这样对目标函数就有很大的负面影响,会被单纯形法的寻优机制赶出基底。

两阶段法是在使用计算机求解时,避免 M 的取值造成干扰。原理和大 M 法很像,求最大问题时,人工变量的系数取 -1 。共分为两个阶段,第一阶段是原目标函数系数暂时取 0 ,只留人工变量,迭代到最优后,进入第二阶段;去除掉人工变量,恢复原来的系数,继续迭代。如果第一阶段无法迭代到最优,说明原问题无解。

退化解出现的特征就是在确定换出变量时,存在两个以上相同的最小比值,这样在下一次迭代中就会出现基变量等于零,出现退化解。有可能会出现反复迭代而导致无法找到最优解的情况,因此当出现有两个最小比值时,我们采取勃兰特规则,即优先选择下标小的换入以及换出,就可以避免循环。

单纯形法用矩阵描述有很好的扩展性,事实上,我们在单纯形法做的每一次迭代,都是在对系数矩阵的增广矩阵做初等行变换,最终使得基变量对应的系数列向量构成单位阵。而做初等行变换我们知道,就相当于左乘一个可逆矩阵,我们用 B − 1 \pmb{B^{-1}} B1 表示。这里的 B \pmb{B} B 就是最初的系数矩阵,乘上了 B − 1 \pmb{B^{-1}} B1 就变为了单位阵,而原来添加的松弛变量是单位阵,在迭代过程中(相当于乘了 B − 1 \pmb{B}^{-1} B1),变为了其他矩阵。于是,最优单纯形表中,松弛变量对应的系数列向量构成的矩阵就是 B − 1 \pmb{B^{-1}} B1

在实际做题时,最可靠的检查办法就用这个 B − 1 \pmb{B^{-1}} B1 去乘上原来的系数矩阵,看看是不是和自己单纯形表中的数字对得上。


这篇关于【管理运筹学】运筹学“背诵手册”(一) | 线性规划问题与单纯形法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/393162

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

nvm如何切换与管理node版本

《nvm如何切换与管理node版本》:本文主要介绍nvm如何切换与管理node版本问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录nvm切换与管理node版本nvm安装nvm常用命令总结nvm切换与管理node版本nvm适用于多项目同时开发,然后项目适配no

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符