【运筹学】整数规划建模技巧

简介: 【运筹学】整数规划建模技巧

整数规划建模中,经常会使用到0-1变量来辅助建模,将模型表述为IP模型或BIP模型,下面是一些常见的整数规划建模技巧

使用辅助0-1变量实现“非此即彼”约束

处理方式如下图,M是一个较大的数,当约束的右边加上M时,无论x1和x2在取在取值范围之内的任意值,式子都是成立的,即该约束无效,没有起到限制变量取值的作用。那么只需要让其中一个约束失效即可,通过在两个约束的右边分别添加M y 1和 My2,并让y 1 + y 2 = 1 来实现

保留N个约束中的K个

image.png

函数有N个可能的值

image.png

固定收费问题

image.png

二进制表示法代替整数变量

当一个模型存在大量0-1变量和少量整数变量时,无法直接使用高效的BIP算法,这时候可以使用二进制表示法将原有的整数变量分解成多个0-1变量。当一个整数x xx的范围为[0,u]时,可以参考下图的方式将其分解为N个0-1变量具体的案例如下图所示


分段函数建模

当一个函数是一个分段分数时,即处于不同区域的x xx,其对应的函数表达式f ( x ) f(x)f(x)是不同的,在处理这种问题的时候,建模的方式如下:

具体的案例如下图所示

分段函数建模

image.png

如果无法理解上面的模型处理方式的话,可以仔细理解下面的图片

目录
打赏
0
1
2
0
14
分享
相关文章
《数学模型(第五版)》学习笔记(2)第3章 简单的优化模型 第4章 数学规划模型
《数学模型(第五版)》学习笔记(2)第3章 简单的优化模型 第4章 数学规划模型
263 1
【类脑计算】突触可塑性模型之Hebbian学习规则和STDP
本文介绍了突触可塑性中的Hebbian学习规则和STDP(Spike-Timing Dependent Plasticity),两种基于神经元活动调节突触强度的机制,其中Hebbian规则强调同时活动的神经元间的连接增强,而STDP则考虑了脉冲时间差异对突触强度的调节作用。
462 2
解决背包问题:组合优化的应用与建模方法
组合优化是数学优化的一支,专注于从有限集合中选取元素的最优化问题。它涉及将一组对象组合在一起,以满足特定条件并优化某个目标函数,即在所有可能的组合中找到最有利的一个。 本文将以一个简化的背包问题为例,来讲解采用数学规划的方法来解决背包这个组合优化问题。
线性规划、整数规划、多元规划、二次规划等规划类问题
线性规划、整数规划、多元规划、二次规划等规划类问题
266 0
强化学习从基础到进阶-案例与实践[2]:马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
强化学习从基础到进阶-案例与实践[2]:马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
强化学习从基础到进阶-案例与实践[2]:马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
【5分钟paper】基于近似动态规划的学习、规划和反应的集成架构
【5分钟paper】基于近似动态规划的学习、规划和反应的集成架构
229 0
运筹学基础——预测
运筹学基础——预测
168 0
MindOpt--C++语言-对一个简单的混合整数规划问题建模求解
MindOpt是达摩院决策智能实验室研究的一款优化求解器,目前在优化求解线性规划问题这一功能上取得不错的成绩,希望大家能够帮我们多多打磨其他功能(混合整数线性规划、二次规划、半定规划目前都在公测),让我们的MindOpt在优化求解器这板块成为国产之光。
MindOpt--C++语言-对一个简单的混合整数规划问题建模求解
优化算法-整数规与多目标规划
优化算法-整数规与多目标规划
265 0
WWW 2022 | 结合高效整数规划求解,快手提出多元因果森林模型,智能营销效果显著
WWW 2022 | 结合高效整数规划求解,快手提出多元因果森林模型,智能营销效果显著
367 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等