两阶段随机规划背包问题

pc8888888 · 发表于 2022-7-6 11:10

关键字：COPT，Gurobi，Benders Decomposition，Integer-L-shaped Algorithm, stochastic program
摘要：本文提供了两阶段随机规划背包问题的数学模型和4种求解方法，方法1：python + COPT；方法2：python + COPT + Benders Cut + L-Shaped；方法3：python + Gurobi；方法4：python + Gurobi + Benders Cut + L-Shaped。
不知道大家是否和小编一样，在学习数学模型求解方面的知识时，找到的资料要么太简单无法拓展，要么太难无法深入，要么………
今天的推文极有可能正中大家下怀，它相比简单问题进了1个台阶，比复杂问题退了不止5个台阶，今天继续为大家带来两阶段随机规划的推文，想想距离上次随机规划的推文还是在…………上次
我们之前MATLAB数学建模（十二） | 随机规划这篇推文初步介绍了随机规划，今天我们在此基础上讲解随机规划的其中一部分研究内容——期望值模型。后续的推文我们将围绕本篇推文以及本篇的参考文献以视频的方式进一步介绍随机规划，欢迎大家前来学习。
问题描述

疫情结束后，仪同学计划背着他的好几个极地背包开心的去骑行，他准备在背包里装一些物品以保证骑行所需，待装的每个物品都具有一定的重量以及骑行收益，但有一部分物品的收益是随机的，且概率已知，于是他计划分两个阶段将物品装进他的极地背包，且要保证在不超过背包容量的前提下使骑行收益最大，问他都需要装哪些物品？
<hr/>随机规划模型

$\begin{align*} \max_{} \quad & \sum_{i\in M}\sum_{j\in N}c_ix_{ij} + E_{}(Q(x,w))\\ s.t.\quad & \sum_{i\in M}a_ix_{ij} ⩽ b_j \quad \quad \forall j\in N\\ & \sum_{j\in N}x_{ij} ⩽ 1\quad \quad \quad \forall i \in M\\ & x_{ij} = 0, 1 \quad \forall i \in M,\ j\in N\\ \\ Q(x,w) = & \max_{} \sum_{k\in K}\sum_{j\in N}q_{wk}y_{wkj} \\ s.t.\quad & \sum_{i\in M}a_ix_{ij}+\sum_{k\in K}w_ky_{wkj} ⩽ b_j \quad \quad \forall j\in N, \ w\in \Omega\\ & \sum_{j\in N}y_{wkj} ⩽ 1\quad \quad \quad \forall i\in M, \ w\in \Omega\\ & y_{wkj} = 0, 1 \quad \forall k \in K,\ j\in N \end{align*} \\$
其中，各个变量的含义如下所示：

<hr/>随机规划模型的拓展形式

$\begin{align*} \max_{} \quad & \sum_{i\in M}\sum_{j\in N}c_ix_{ij} + \sum_{w\in \Omega}\sum_{j\in N}\sum_{k\in K}p_wq_{wk}y_{wkj}\\ s.t.\quad & \sum_{i\in M}a_ix_{ij} ⩽ b_j \quad \quad \forall j\in N\\ & \sum_{j\in N}x_{ij} ⩽ 1\quad \quad \quad \forall i \in M\\ \quad & \sum_{i\in M}a_ix_{ij}+\sum_{k\in K}w_ky_{wkj} ⩽ b_j \quad \quad \forall j\in N, \ w\in \Omega\\ & \sum_{j\in N}y_{wkj} ⩽ 1\quad \quad \quad \forall i\in M, \ w\in \Omega\\ & x_{ij} = 0, 1 \quad \forall i \in M,\ j\in N\\ & y_{wkj} = 0, 1 \quad \forall k \in K,\ j\in N \end{align*} \\$
随机规划模型转化为拓展形式的本质就是对期望转化为可以求解的形式，即
$E_{}(X) = \sum_{i}p_ix_i\\ \\$
对应论文中的
$E_{}(Q(x,w)) = \sum_{w\in \Omega}\sum_{j\in N}\sum_{k\in K}p_wq_{wk}y_{wkj}\\ \\$
<hr/>算法步骤

<hr/>学习步骤推荐

Step1: 结合本推文通读参考文献-->论文比较简单；

		自动登录	找回密码
密码			立即注册

两阶段随机规划背包问题

本帖子中包含更多资源