首页 > 其他分享 >【运筹学】怎样更好地理解和应用单纯形法(温习、深刻反思、详细整理)

【运筹学】怎样更好地理解和应用单纯形法(温习、深刻反思、详细整理)

时间:2024-07-30 23:53:34浏览次数:17  
标签:可行 迭代 深刻反思 单纯形法 x3 约束 顶点 温习

1 对单纯形法的理解

        假设线性规划问题存在可行域;

1.1 预备知识点

        (1)线性规划问题的标准化【运筹学】线性规划问题的标准化及其意义(针对单纯形法)

        (2)线性规划问题的可行域是凸集;

        (3)如果一个线性规划问题存在唯一最优解,那么最优解一定落在可行域的顶点上;

        (4)如果一个点是线性规划可行域的顶点,那么一定有多个不等约束,只在这个点同时成为紧约束(刚好等于)。

1.2 单纯形法的本质

        搜索就像狩猎,搜索算法就像猎人。

        单纯形法是针对线性规划问题的一种搜索算法,将搜索空间限定在可行域的顶点集合内。

        从几何上理解单纯形法:从可行域的一个顶点迭代到相邻顶点(可能迭代到相同顶点的过程。

        从代数上理解单纯形法:决定顶点的紧约束集变化(某个紧约束变宽松,某个宽松的约束变为紧约束,不同紧约束集可能对应相同顶点)。

2 单纯形法的内容

        一个搜索算法的组成要素无非是确定初始可行解、确定迭代方式(搜索方向)、设置终止条件三个步骤,接下来针对单纯形法对这三个步骤进行说明。

2.1 单纯形法的初始可行解(可行域的顶点)

       2.1.1 如何确定初始可行解

        首先需要明白:如果一个点是线性规划可行域的顶点,那么一定有多个不等约束,只在这个点同时成为紧约束(刚好等于)。

        那么我们如何找出顶点或者是确定紧约束集呢?如例题:我们相当于有6个约束(三个主要约束,三个非负约束),令其中任意三个约束(存在三个变量)成为紧约束,然后判断该解是否可行,若该解可行,那么便成为一个顶点;

        ①令x1,x2,x3=0,则使三个变量非负约束成为紧约束,但是这样便不满足第二个和第三个主要约束,不是顶点;

        ②令x1=0,则x3=-2,不满足非负约束,不是顶点;

        ③令x2=0,x3=5(x3=5),x1=2/7(x1=34),则x2的非负约束、第二个和第三个(第一个)主要约束为紧约束,因此对应一个顶点;

        ④令x3=0,x1=1,x2=17(x2=5),则x3的非负约束、第一(三)个和第二个主要约束为紧约束,因此对应一个顶点。

        ⑤令三个主要约束为紧约束,则x1=43/7,x2=83/7,x3=72/7,因此对应一个顶点。(此处可以手动计算一次,加深印象,后续大有作为)

        这便是确定第一个顶点(初始基可行解)的过程了,为更加快捷地找出初始可行解,便有了两阶段法大M法

         2.1.2 线性模型的标准化

        紧接着我们思考,一个解是否满足不等式比较难观察,那我们把是否满足不等式约束转化为观察一个变量的值是否满足约束呢?

        假设不等式约束如下:

        标准化后的结果:

        这样我们就把观察原来的不等式约束是否成立转换到观察x5是否满足非负约束了。

        因此线性规划问题标准化【运筹学】线性规划问题的标准化及其意义(针对单纯形法),如例题:

        总结就是,转化为标准型的本质是引入松弛变量改变原有线性规划问题的表达形式,意义就是在单纯形法迭代过程中便于观察。

        现在相当于我们一共有8个约束、5个变量,想要确定顶点,我们就需要5个紧约束,因为已经有3个等式约束,我们就需要选择两个变量(也就是非基变量,后续再详细说明),让其的值等于0,然后我们就可以解出来其他三个变量的值,观察其是否可行,如果可行,那么这就是一个顶点。

2.2 单纯形法是怎样迭代的(怎样寻找顶点或者确定约束集)

        那么我们有疑问了,我们是否可以直接列举出所有可能的顶点情况呢?当然是可以的,枚举后计算出目标函数值,这样便可以求出最优解了。但是这样的话,当遇到约束非常多的时候,计算量就会剧增,并且这样便成了穷举算法,便不是搜索算法了。

       那么单纯形法是怎么迭代的(相当于怎样寻找下一个顶点或者确定下一个约束集)呢?

       2.1.2例题中我们提到,只需要选择2个变量的值等于0,便可以得出第一个顶点,这里我们选择x4=0,x5=0(检验可行),得到第一个解(x1=43/7,x2=83/7,x3=72/7,x4=0,x5=0)。迭代第一次:我们令x3=0,x4=0(检验可行),得到第二个解(x1=1,x2=17,x3=0,x4=0,x5=36),这样便完成了一次迭代过程,并且只有一个约束变化,因此对应的是相邻的顶点。
        那么我们该放宽谁,收紧谁呢?因为有可能变化后得到的解可能不可行(不满足某些约束),这就是单纯形法迭代过程中的核心所在了。到这里便需要用到可行改进方向的概念了,我们下一章再诠释。假设我们现在已经明白了怎样选择哪个变量为0(即确定改进方向),那么就只剩下计算出解的过程了。

        假设我们已经确定了初始基可行解,单纯形法迭代过程的本质就是确认改进方向,求解结果,判断是否最优,确认是继续迭代还是停止计算。

标签:可行,迭代,深刻反思,单纯形法,x3,约束,顶点,温习
From: https://blog.csdn.net/TuTuTuhong/article/details/140769642

相关文章

  • 基于三次样条插值和单纯形法的加氢站选址优化
    问题描述已知定点交通流量,求解加氢站建设位置求解方法已知国道或省道定点交通流量若干,根据已知交通流量插值得到每3km对应的交通流量。如图所示。将该问题转换为p-中值问题:其中,需求点位置集合=每3km一个需求点在i点的客户人数=i点(每个需求点)的车流量设施总数=需要......
  • 代码无注,后患无穷:一个大学生的深刻反思
    当我第一次踏入编程的殿堂,我以为只要掌握了语法和逻辑,就能轻松驾驭代码的世界。然而,随着学习的深入和实践的增多,我逐渐意识到,写代码不写注释,将会带来无穷的后患。记得那是一个阳光明媚的下午,我为了完成一个复杂的项目,埋头于电脑前,手指在键盘上飞快地舞动。我沉浸在代码的......
  • 对偶理论和对偶单纯形法——Python实现
    对偶单纯形法是从对偶可行性逐步搜索出原始问题最优解的方法。由线性规划问题的对偶理论,原始问题的检验数对应于对偶问题的一组基本可行解或最优解;原始问题的一组基本可行解或最优解对应于对偶问题的检验数;原始问题约束方程的系数矩阵的转置是对偶问题约束条件方程的系数矩阵。所......
  • 单纯形法的平滑分析
    我们采用这样的形式来讨论线性规划:\(\maxc^\topx\)subjectto\(Ax\leqb\),其中\(x,c\in\R^n\),\(A\in\R^{m\timesn},b\in\R^m\)。其中\(P=\{x\midAx\leqb\}\)称为可行域,是\(\R^n\)中的多面体。求解线性规划问题的最常用算法就是单纯形法,它指出我们从\(P\)的一个顶点\(x_......
  • 线性规划和网络流的单纯形法
    线性规划线性规划问题求\[\max\sum_{i=1}^nc_jx_j\\\text{s.t.:}\\\sum_{t=1}^na_{it}x_t\leb_i,i\in\Z\cap[1,m_1]\\\sum_{t=1}^na_{it}x_t=b_i,i\in\Z\cap(m_1,m_1+m_2]\\\sum_{t=1}^na_{it}x_t\geb_i,i\in(m_1+m_2,m_1+m_2+m_3]\\x_......
  • 优化基础1——单纯形法与迭代局部搜索
    一.单纯形法学习的参考资料:运筹学教学|十分钟快速掌握单纯形法(附C++代码及算例)(qq.com)运筹说第16期|线性规划硬核知识点梳理—单纯形法-知乎(zhihu.com)史上最详细单纯形法—从理解到计算(带约束规划问题)-知乎(zhihu.com)主要理解其思想应该是对暴力求解法的改进......
  • 温习:进程和线程的区别
    进程和线程的区别:1、定义不一样,进程是执行中的一段程序,线程是进程里执行中的任务,一个进程里可以有多个线程。2、一个线程只能属于一个进程。3、线程无地址空间,它包括在......
  • 温习日志-21
    温习日志——2023年2月28日下午学习内容ABriefIntroductiontotheCommandLine通过在终端,输入cd相对路径实现更改路径在终端输入ls会列出当前所在文件夹的所有......
  • 温习日志-20
    温习日志——2023年2月27日下午学习内容ExportingandImportinginES6Modules在模块中分为import和export在JS中需要将script标签的type='module'才能使用模块化......
  • 温习日志-19
    温习日志——2023年2月26日下午学习内容TheEventLoopinPractice在JS引擎中,会首先执行调用栈中的代码对于回调函数会存入回调队列中,在调用栈中的代码全部执行完......