线性化技巧:绝对值变量的线性化

2024-05-27 22:04

本文主要是介绍线性化技巧:绝对值变量的线性化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

1. 问题

以方述诚老师课件中的案例为例:
m a x 3 x 1 − 2 x 2 − 4 ∣ x 3 ∣ s . t . − x 1 + 2 x 2 ≤ − 5 3 x 2 − x 3 ≥ 6 2 x 1 + x 3 = 12 x 1 , x 2 ≥ 0 max \quad 3x_1-2x_2-4\vert x_3 \vert \\ s.t. -x_1+2x_2 \leq -5 \\ 3x_2-x_3 \geq 6 \\ 2x_1 + x_3 = 12 \\ x_1,x_2 \geq 0 max3x12x24∣x3s.t.x1+2x253x2x362x1+x3=12x1,x20

x 3 x_3 x3是一个自由变量,且在目标函数中它是以绝对值的形式存在,如果我们要将该模型转化成标准型,首先要做的就是将 x 3 x_3 x3线性化。

2. 线性化

对于每一个数字 x x x,我们都可以将它拆成正的个数 x + x^+ x+和负的个数 x − x^- x,并将其表示为 x + − x − x^+ - x^- x+x(正的个数 - 负的个数),举个例子:

  • 5:正的个数是5,负的个数是0,5-0=5;
  • -5:正的个数是0,负的个数是5,0-5=-5。

直觉上十分合理对吧(intuition是方老师第一节课反复强调的重点),我们用数学表达式来表达上述思想。

x i ∈ R x_i \in R xiR

x i + = { x i , i f x i ≥ 0 0 , o t h e r w i s e x_i^+ = \begin{cases} x_i, \quad if \quad x_i \geq 0 \\ 0, otherwise \end{cases} xi+={xi,ifxi00,otherwise

x i − = { 0 , i f x i ≥ 0 − x i , o t h e r w i s e x_i^- = \begin{cases} 0, \quad if \quad x_i \geq 0 \\ -x_i, otherwise \end{cases} xi={0,ifxi0xi,otherwise

x i = x i + − x i − x_i = x_i^+ - x_i^- xi=xi+xi
x i + × x i − = 0 x_i^+ \times x_i^- = 0 xi+×xi=0

(很多教材和文章里直接省去了这个约束,其实是不对的,待会儿后面讲。)

x i + , x i − ≥ 0 x_i^+, x_i^- \geq 0 xi+,xi0

3. 缺少 x i + × x i − = 0 x_i^+ \times x_i^- = 0 xi+×xi=0 有什么问题

x i + × x i − = 0 x_i^+ \times x_i^- = 0 xi+×xi=0 该约束本质保证的是 x i + x_i^+ xi+ x i − x_i^- xi 至少有一个为0,如果没有该约束,5除了表示为5-0以外,还可以表示为6-1、7-2等等。也就是会使得原来只有一个解的问题,变成具有很多个新的解的问题。

4. 延伸思考

上述问题中的 ∣ x ∣ \vert x \vert x是一个“V”字型的凸函数,它可以求极小值。如果要求 m a x ∣ x ∣ max \vert x \vert maxx 那就unbounded了。

5. 参考文献

  1. Linear Programming

这篇关于线性化技巧:绝对值变量的线性化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

变量与命名

引言         在前两个课时中,我们已经了解了 Python 程序的基本结构,学习了如何正确地使用缩进来组织代码,并且知道了注释的重要性。现在我们将进一步深入到 Python 编程的核心——变量与命名。变量是我们存储数据的主要方式,而合理的命名则有助于提高代码的可读性和可维护性。 变量的概念与使用         在 Python 中,变量是一种用来存储数据值的标识符。创建变量很简单,

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

滚雪球学Java(87):Java事务处理:JDBC的ACID属性与实战技巧!真有两下子!

咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE啦,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~ 🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!! 环境说明:Windows 10

小技巧绕过Sina Visitor System(新浪访客系统)

0x00 前言 一直以来,爬虫与反爬虫技术都时刻进行着博弈,而新浪微博作为一个数据大户更是在反爬虫上不遗余力。常规手段如验证码、封IP等等相信很多人都见识过…… 当然确实有需要的话可以通过新浪开放平台提供的API进行数据采集,但是普通开发者的权限比较低,限制也比较多。所以如果只是做一些简单的功能还是爬虫比较方便~ 应该是今年的早些时候,新浪引入了一个Sina Visitor Syst

JS_变量

二、JS的变量 JS中的变量具有如下特征 1 弱类型变量,可以统一声明成var 2 var声明的变量可以再次声明 3 变量可以使用不同的数据类型多次赋值 4 JS的语句可以以; 结尾,也可以不用;结尾 5 变量标识符严格区分大小写 6 标识符的命名规则参照JAVA 7 如果使用了 一个没有声明的变量,那么运行时会报uncaught ReferenceError: *** is not de

PMP–一、二、三模–分类–14.敏捷–技巧–看板面板与燃尽图燃起图

文章目录 技巧一模14.敏捷--方法--看板(类似卡片)1、 [单选] 根据项目的特点,项目经理建议选择一种敏捷方法,该方法限制团队成员在任何给定时间执行的任务数。此方法还允许团队提高工作过程中问题和瓶颈的可见性。项目经理建议采用以下哪种方法? 易错14.敏捷--精益、敏捷、看板(类似卡片)--敏捷、精益和看板方法共同的重点在于交付价值、尊重人、减少浪费、透明化、适应变更以及持续改善等方面。

使用条件变量实现线程同步:C++实战指南

使用条件变量实现线程同步:C++实战指南 在多线程编程中,线程同步是确保程序正确性和稳定性的关键。条件变量(condition variable)是一种强大的同步原语,用于在线程之间进行协调,避免数据竞争和死锁。本文将详细介绍如何在C++中使用条件变量实现线程同步,并提供完整的代码示例和详细的解释。 什么是条件变量? 条件变量是一种同步机制,允许线程在某个条件满足之前进入等待状态,并在条件满

OpenStack:Glance共享与上传、Nova操作选项解释、Cinder操作技巧

目录 Glance member task Nova lock shelve rescue Cinder manage local-attach transfer backup-export 总结 原作者:int32bit,参考内容 从2013年开始折腾OpenStack也有好几年的时间了。在使用过程中,我发现有很多很有用的操作,但是却很少被提及。这里我暂不直接

axure之变量

一、设置我们的第一个变量 1、点击axure上方设置一个全局变量a = 3 2、加入按钮、文本框元件点击按钮文档框展示变量值。 交互选择【单击时】【设置文本】再点击函数。 点击插入变量和函数直接选择刚刚定义的全局变量,也可以直接手动写入函数(注意写入格式。) 这样点击按钮时就直接展示刚刚设置的全局变量3了。 2、更改变量值 在新建交互里点击设置变量值。 将a变量设置成等于10. 将新