当前位置: 首页 > news >正文

【最优化理论】线性规划

文章目录

  • 什么是线性规划(Linear Programming,LP)?
  • 线性规划的标准形式
  • 非标准形LP模型转化为标准形LP模型
  • 基本概念
    • 基本解&基矩阵&基变量&非基变量
    • 基本可行解&可行基矩阵&非退化的基本可行解&退化的基本可行解
    • 基本可行解存在性
    • 求基本可行解
      • 示例:求基本可行解
    • 求最优解
      • 方法一(暴力枚举):求出所有基本可行解找最小
      • 方法二(迭代):从一个基本可行解跳转到一个目标函数值更小的基本可行解
  • 多面体
  • 多面体分解定理
  • 单纯形法
    • 基本思想
    • 原理
    • 方法
    • 1 确定出基变量和出基向量的下标
    • 2 确定进基变量和进基向量的下标
    • 3 确定进基变量的值
      • 终止条件
  • 单纯形法计算步骤
  • 单纯形法表格形式

什么是线性规划(Linear Programming,LP)?

目标函数为决策变量的线性函数,同时约束条件为线性等式或线性不等式约束。

线性规划的标准形式

在这里插入图片描述
在这里插入图片描述

非标准形LP模型转化为标准形LP模型

在这里插入图片描述

基本概念

在这里插入图片描述

基本解&基矩阵&基变量&非基变量

基本可行解&可行基矩阵&非退化的基本可行解&退化的基本可行解

在这里插入图片描述

基本可行解存在性

在这里插入图片描述

求基本可行解

求基本可行解<=>求极点<=>求可行基矩阵<=>Am∗nA_{m*n}Amn矩阵m个线性无关列
在这里插入图片描述

示例:求基本可行解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

求最优解

方法一(暴力枚举):求出所有基本可行解找最小

求出所有基本可行解(即求极点)。
代入目标函数找出最小极点(该最小极点即为最优解,因为最优解一定在极点取得)。

方法二(迭代):从一个基本可行解跳转到一个目标函数值更小的基本可行解

在这里插入图片描述

多面体

在这里插入图片描述

多面体基本性质

在这里插入图片描述

多面体的极点

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

x若是极点,正分量对应的A的列一定线性无关。

示例:求极点

在这里插入图片描述

多面体S有多少个极点?- 有限个 & 最多CnmC_n^mCnm

最多有CnmC_n^mCnm个极点,一般都少于CnmC_n^mCnm,有两个原因。
原因1:从n个列中选出m列不一定线性无关。
原因2:即使这m列线性无关,其组成的B也不一定满足B−1b≥0B^{-1}b\ge 0B1b0

多面体的方向

在这里插入图片描述

多面体的极方向

在这里插入图片描述
在这里插入图片描述

多面体的极方向有多少个?- 有限个

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

示例:求极方向

在这里插入图片描述
d≥0

多面体分解定理

在这里插入图片描述

多面体分解定理有什么作用?

在这里插入图片描述

在这里插入图片描述

重新表示可行集

在这里插入图片描述

重新定义线性规划问题

在这里插入图片描述
在这里插入图片描述

为什么min⁡∑λiCTxi\min \sum \lambda_i C^Tx_iminλiCTxi等价于min⁡CTxi,i=1,...,k\min C^Tx_i,i=1,...,kminCTxi,i=1,...,k

min⁡CTxi,i=1,...,k\min C^Tx_i,i=1,...,kminCTxii=1,...,k,找到最小xrx_rxr就是最优值点,令min⁡∑λiCTxi\min \sum \lambda_i C^Tx_iminλiCTxiλr=1\lambda_r=1λr=1其他的λ都为0,CTxrC^Tx_rCTxr就是最优值。

何时有最优解?

CTdj≥0C^Td_j \ge 0CTdj0时,存在最优解。

CTdj<0C^Td_j \lt 0CTdj<0时,无解。

最优解是什么?

最优解一定在极点上取到。

min⁡CTxi,i=1,...,k\min C^Tx_i,i=1,...,kminCTxii=1,...,k,找到最小xrx_rxr就是最优值点,CTxrC^Tx_rCTxr就是最优值。

单纯形法

在这里插入图片描述

基本思想

在这里插入图片描述

原理

实现基本可行基的转化

方法

在这里插入图片描述

从初始基本可行解出发,求一个改进的基本可行解。

1 确定出基变量和出基向量的下标

2 确定进基变量和进基向量的下标

3 确定进基变量的值

目标函数值只与非基变量有关。
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

终止条件

在这里插入图片描述

单纯形法计算步骤

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

单纯形法表格形式

相关文章:

【最优化理论】线性规划

文章目录什么是线性规划&#xff08;Linear Programming&#xff0c;LP&#xff09;&#xff1f;线性规划的标准形式非标准形LP模型转化为标准形LP模型基本概念基本解&基矩阵&基变量&非基变量基本可行解&可行基矩阵&非退化的基本可行解&退化的基本可行…...

数据库测试的认知和分类

数据库测试的认知和分类 目录&#xff1a;导读 系统测试 集成测试 单元测试 功能测试 数据库性能 性能优化分4部分 安全测试 现在的软件系统&#xff0c;尤其是业务应用系统&#xff0c;后台都连接着一个数据库。数据库中存储了大量的数据&#xff0c;数据库的设计是否…...

MQ中间件概念一览

一、概述 1. 大多应用中&#xff0c;可通过消息服务中间件来提升系统异步通信、扩展解耦能力 2. 消息服务中两个重要概念&#xff1a; 消息代理&#xff08;message broker&#xff09;和目的地&#xff08;destination&#xff09; 当消息发送者发送消息以后&#xff0c;将由…...

爱尔兰公司注册要求及条件

简介&#xff1a; 爱尔兰是一个高度发达的资本主义国家&#xff0c;也是欧盟、经济合作与发展组织、世界贸易组织和联合国的成员国。并且也是世界经济发展速度快的国家之一&#xff0c;因经济发达赢得了“欧洲小虎”的美誉。总体来看&#xff0c;爱经济发展势头趋稳&#xff0c…...

Java中如何打印对象内存地址?

先看一个简单的程序&#xff0c;一般我们打印对象&#xff0c;大部分是下面的情况&#xff0c;可能会重写下toString()方法&#xff0c;这个另说 Frolan frolan new Frolan(); System.out.println(frolan);// 输出结果 com.test.admin.entity.Frolan2b80d80f这个结果其实是调…...

CF1707E Replace

题目描述 给定一个长为 nnn 的序列 a1,…,ana_1,\ldots,a_na1​,…,an​&#xff0c;其中对于任意的 iii 满足 1≤ai≤n1 \leq a_i \leq n1≤ai​≤n。 定义一个二元组函数如下&#xff1a; f((l,r))(min⁡{al,…,ar},max⁡{al,…,ar})(l≤r)f((l,r))(\min\{a_l,\ldots,a_r\}…...

【Hello Linux】Linux工具介绍 (make/makefile git)

作者&#xff1a;小萌新 专栏&#xff1a;Linux 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;介绍Linux的常用工具make/makefile git Linux项目自动化构建工具 – make/Makefile 背景 会不会写Makefile 从侧面说明了一个人是否具…...

享元模式flyweight

享元模式属于结构型模式。享元模式是池技术的重要实现方式&#xff0c;它可以减少重复对象的创建&#xff0c;使用缓存来共享对象&#xff0c;从而降低内存的使用。细粒度的对象其状态可以分为两种&#xff1a;内部状态和外部状态。应用场景系统存在大量相似或相同的对象。外部…...

Pulsar

一、简介Apache Pulsar是Apache软件基金会顶级项目&#xff0c;是下一代云原生分布式消息流平台&#xff0c;集消息、存储、轻量化函数式计算为一体&#xff0c;采用计算与存储分离架构设计&#xff0c;支持多租户、持久化存储、多机房跨区域数据复制&#xff0c;具有强一致性、…...

项目介绍 + 定长内存池设计及实现

你好&#xff0c;我是安然无虞。 文章目录项目介绍当前项目做的是什么?技术栈内存池是什么?池化技术内存池内存池主要解决的问题malloc定长内存池学习目的定长内存池设计项目介绍 当前项目做的是什么? 这个项目是实现一个高并发的内存池, 它的原型是 Google 的一个开源项…...

Linux--线程安全的单例模式--自旋锁--0211

1. 线程安全的单例模式 1.1 什么是单例模式 某些类, 只应该具有一个对象(实例), 就称之为单例. 1.1.1 懒汉方式实现单例模式 以上篇博文的线程池为例 Liunx--线程池的实现--0208 09_Gosolo&#xff01;的博客-CSDN博客 实现懒汉模式首先要先将构造函数私有化&#xff0c;…...

图文解说S参数(进阶篇)

S参数是RF工程师/SI工程师必须掌握的内容&#xff0c;业界已有多位大师写过关于S参数的文章&#xff0c;即便如此&#xff0c;在相关领域打滚多年的人&#xff0c; 可能还是会被一些问题困扰着。你懂S参数吗? 图文解说S参数&#xff08;基础篇&#xff09; 请继续往下看...台湾…...

Sentinel源码阅读

基础介绍 Sentinel 的使用可以分为两个部分: 核心库&#xff08;Java 客户端&#xff09;&#xff1a;不依赖任何框架/库&#xff0c;能够运行于 Java 8 及以上的版本的运行时环境&#xff0c;同时对 Dubbo / Spring Cloud 等框架也有较好的支持&#xff08;见 主流框架适配&…...

2023年浙江食品安全管理员考试真题题库及答案

百分百题库提供食品安全管理员考试试题、食品安全管理员考试预测题、食品安全管理员考试真题、食品安全管理员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 一、判断题 7.&#xff08;重点&#xff09;《餐饮服务食品安全…...

Webstorm 代码没有提示,uniapp 标签报错

问题 项目是用脚手架创建的&#xff1a; vue create -p dcloudio/uni-preset-vue my-project 打开之后&#xff0c;添加view标签警告报错的。代码也没有提示&#xff0c;按官方说法&#xff1a;CLI 工程默认带了 uni-app 语法提示和 5App 语法提示。 但是我这里就是有问题。…...

MySQL-Innodb引擎事务原理

文章目录1.事务介绍2 事务特性3. 事务的实现原理4 redo log 保证持久性5 undo log 保证原子性6 MVCC 概念6.1 隐藏字段6.2 版本链6.3 ReadView6.3.1readview 版本控制规则7 隔离性 实现7.2 隔离性- REPEATABLE READ 可重复读下8 一致性1.事务介绍 事务是一组操作的集合&#xf…...

Linux操作系统学习(了解环境变量)

文章目录环境变量初识除了上述介绍的PATH&#xff0c;还有一些常见的环境变量如&#xff1a;查看环境变量方法 &#xff1a;环境变量的基本概念&#xff1a;本地变量&#xff1a;环境变量初识 环境变量解释起来比较抽象&#xff0c;先看示例&#xff1a; #include <stdio.…...

数据分析思维(六)|循环/闭环思维

循环/闭环思维 1、概念 在很多的分析场景下&#xff0c;我们需要按照一套流程反复分析&#xff0c;而不是进行一次性的分析&#xff0c;也就是说这套流程的结果会成为该流程的新一次输入&#xff0c;从而形成一个闭环&#xff0c;此时的分析思维我们称之为循环/闭环思维。 常…...

C++:类和对象(下)

文章目录1 再谈构造函数1.1 构造函数体赋值1.2 初始化列表1.3 explicit关键字2 static成员2.1 概念2.2 特性3 友元3.1 友元函数&#xff08;流插入&#xff08;<<&#xff09;及流提取&#xff08;>>&#xff09;运算符重载&#xff09;3.2 友元类4 内部类5 匿名对…...

ASP.NET Core MVC 项目 AOP之IResultFilter和IAsyncResultFilter

目录 一:说明 二:IActionFilter同步 三:IAsyncActionFilter异步 一:说明 IResultFilter同步过滤器与IAsyncResultFilter异步过滤器常常被用作于渲染视图或处理结果。 IResultFilter同步过滤器执行顺序: 1:执行控制器中的构造函数,实例化控制器 2:执行具体的Acti…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

Yii2项目自动向GitLab上报Bug

Yii2 项目自动上报Bug 原理 yii2在程序报错时, 会执行指定action, 通过重写ErrorAction, 实现Bug自动提交至GitLab的issue 步骤 配置SiteController中的actions方法 public function actions(){return [error > [class > app\helpers\web\ErrorAction,],];}重写Error…...

简约商务通用宣传年终总结12套PPT模版分享

IOS风格企业宣传PPT模版&#xff0c;年终工作总结PPT模版&#xff0c;简约精致扁平化商务通用动画PPT模版&#xff0c;素雅商务PPT模版 简约商务通用宣传年终总结12套PPT模版分享:商务通用年终总结类PPT模版https://pan.quark.cn/s/ece1e252d7df...

PostgreSQL 与 SQL 基础:为 Fast API 打下数据基础

在构建任何动态、数据驱动的Web API时&#xff0c;一个稳定高效的数据存储方案是不可或缺的。对于使用Python FastAPI的开发者来说&#xff0c;深入理解关系型数据库的工作原理、掌握SQL这门与数据库“对话”的语言&#xff0c;以及学会如何在Python中操作数据库&#xff0c;是…...