Python小白的数学建模课-05.0

Python小白的数学建模课-05.0

0-1 规划不仅是数模竞赛中的常见题型,也具有重要的现实意义。

双十一促销中网购平台要求二选一,就是互斥的决策问题,可以用 0-1规划建模。

小白学习 0-1 规划,首先要学会识别 0-1规划,学习将问题转化为数学模型。

『Python小白的数学建模课 @ Youcans』带你从数模小白成为国赛达人。


1. 什么是 0-1 规划?

0-1 整数规划是一类特殊的整数规划,变量的取值只能是 0 或 1。

0-1 变量可以描述开关、取舍、有无等逻辑关系、顺序关系,可以处理背包问题、指派问题、选址问题 、计划安排、线路设计 、人员安排等各种决策规划问题。进而,任何整数都可以用二进制表达,整数变量就可以表示为多个 0-1 变量的组合,因此任何整数规划都可以转化为 0-1 规划问题来处理。0-1 规划问题与运筹学中的很多经典问题也都有紧密联系。

在数学建模学习中,0-1 规划主要用于求解互斥的决策问题、互斥的约束条件问题、固定费用问题和分派问题。0-1 规划是数模竞赛的常见题型,国赛 B题经常有 0-1规划问题或可以转化为 0-1 规划问题。

0-1 规划的算法都比较复杂,大规模问题一般没有精确解法。本文仍然使用 PuLP 工具包求解 0-1 规划问题,该工具包的使用比较简单。建议本文读者重点关注 0-1 规划问题的分类及建模方法,把握哪些问题是 0-1 规划问题,是哪一类的 0-1 规划问题,如何对这些典型问题进行建模。在此基础上,才能调用 PuLP 函数进行求解。

欢迎关注 『Python小白的数学建模课 @ Youcans』,每周更新数模笔记
Python小白的数学建模课-01.新手必读
Python小白的数学建模课-02.数据导入
Python小白的数学建模课-03.线性规划
Python小白的数学建模课-04.整数规划
Python小白的数学建模课-05.0-1规划
Python数模笔记-PuLP库
Python数模笔记-StatsModels统计回归
Python数模笔记-Sklearn
Python数模笔记-NetworkX
Python数模笔记-模拟退火算法


2. 0-1 规划的分类及建模方法

规划问题的数学模型包括决策变量、约束条件和目标函数,围绕这三个要素都可能存在互斥的情况,从而导出不同类型的0-1规划问题,其建模方法也有差别。

2.1 互斥的决策问题

互斥的决策问题,是指决策方案、计划互斥,如决定投资项目、确定投资场所、选择投产产品等。

例如,双十一的促销活动,淘宝、京东、拼多多要求店铺二选一,最多只能选择参加一家平台,否则可能会被封杀,这是典型的互斥决策问题。

背包问题就是经典的互斥决策问题。给定一组 n 个物品,每种物品 i 的价值为 v_i、重量/体积为 w_i,背包所能容纳的总重量/总容量为(B),如何选择其中若干种物品(每种物品选 0 个或 1 个),使得物品的总价值最高?

背包问题的建模方法如下:

定义决策变量为:

[x_i = egin{cases}
0,不选择第;i;个物品\
1,选择第;i;个物品
end{cases}
]

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » Python小白的数学建模课-05.0