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

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

相关文章

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

如何在Mac上彻底删除Edge账户? 手动卸载Edge浏览器并清理残留文件技巧

《如何在Mac上彻底删除Edge账户?手动卸载Edge浏览器并清理残留文件技巧》Mac上的Edge账户里存了不少网站密码和个人信息,结果同事一不小心打开了,简直尴尬到爆炸,想要卸载edge浏览器并清... 如果你遇到 Microsoft Edge 浏览器运行迟缓、频繁崩溃或网页加载异常等问题,可以尝试多种方

Python变量与数据类型全解析(最新整理)

《Python变量与数据类型全解析(最新整理)》文章介绍Python变量作为数据载体,命名需遵循字母数字下划线规则,不可数字开头,大小写敏感,避免关键字,本文给大家介绍Python变量与数据类型全解析... 目录1、变量变量命名规范python数据类型1、基本数据类型数值类型(Number):布尔类型(bo

qt5cored.dll报错怎么解决? 电脑qt5cored.dll文件丢失修复技巧

《qt5cored.dll报错怎么解决?电脑qt5cored.dll文件丢失修复技巧》在进行软件安装或运行程序时,有时会遇到由于找不到qt5core.dll,无法继续执行代码,这个问题可能是由于该文... 遇到qt5cored.dll文件错误时,可能会导致基于 Qt 开发的应用程序无法正常运行或启动。这种错

mtu设置多少网速最快? 路由器MTU设置最佳网速的技巧

《mtu设置多少网速最快?路由器MTU设置最佳网速的技巧》mtu设置多少网速最快?想要通过设置路由器mtu获得最佳网速,该怎么设置呢?下面我们就来看看路由器MTU设置最佳网速的技巧... 答:1500 MTU值指的是在网络传输中数据包的最大值,合理的设置MTU 值可以让网络更快!mtu设置可以优化不同的网

一文全面详解Python变量作用域

《一文全面详解Python变量作用域》变量作用域是Python中非常重要的概念,它决定了在哪里可以访问变量,下面我将用通俗易懂的方式,结合代码示例和图表,带你全面了解Python变量作用域,需要的朋友... 目录一、什么是变量作用域?二、python的四种作用域作用域查找顺序图示三、各作用域详解1. 局部作

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA