【数学建模】储药柜的设计

2014高教社杯全国大学生数学建模竞赛D题目

题目描述

储药柜的结构类似于书橱,通常由若干个横向隔板和竖向隔板将储药柜分割成若干个储药槽(如图1所示)。为保证药品分拣的准确率,防止发药错误,一个储药槽内只能摆放同一种药品。药品在储药槽中的排列方式如图2所示。药品从后端放入,从前端取出。一个实际储药柜中药品的摆放情况如图3所示。
为保证药品在储药槽内顺利出入,要求药盒与两侧竖向隔板之间、与上下两层横向隔板之间应留2mm的间隙,同时还要求药盒在储药槽内推送过程中不会出现并排重叠、侧翻或水平旋转。在忽略横向和竖向隔板厚度的情况下,建立数学模型,给出下面几个问题的解决方案。

  1. 药房内的盒装药品种类繁多,药盒尺寸规格差异较大,附件1中给出了一些药盒的规格。请利用附件1的数据,给出竖向隔板间距类型最少的储药柜设计方案,包括类型的数量和每种类型所对应的药盒规格。
  2. 药盒与两侧竖向隔板之间的间隙超出2mm的部分可视为宽度冗余。增加竖向隔板的间距类型数量可以有效地减少宽度冗余,但会增加储药柜的加工成本,同时降低了储药槽的适应能力。设计时希望总宽度冗余尽可能小,同时也希望间距的类型数量尽可能少。仍利用附件1的数据,给出合理的竖向隔板间距类型的数量以及每种类型对应的药品编号。
  3. 考虑补药的便利性,储药柜的宽度不超过2.5m、高度不超过2m,传送装置占用的高度为0.5m,即储药柜的最大允许有效高度为1.5m。药盒与两层横向隔板之间的间隙超出2mm的部分可视为高度冗余,平面冗余=高度冗余×宽度冗余。在问题2计算结果的基础上,确定储药柜横向隔板间距的类型数量,使得储药柜的总平面冗余量尽可能地小,且横向隔板间距的类型数量也尽可能地少。
  4. 附件2给出了每一种药品编号对应的最大日需求量。在储药槽的长度为1.5m、每天仅集中补药一次的情况下,请计算每一种药品需要的储药槽个数。为保证药房储药满足需求,根据问题3中单个储药柜的规格,计算最少需要多少个储药柜。

提出关键点

一个储药槽内只能摆放同一种药品。
要求药盒与两侧竖向隔板之间、与上下两层横向隔板之间应留2mm的间隙,同时还要求药盒在储药槽内推送过程中不会出现并排重叠、侧翻或水平旋转。在忽略横向和竖向隔板厚度的情况下,建立数学模型。

建立数学模型

模型一:储药槽和药盒关系模型

已知药盒长宽高分别是 a , b , c a,b,c a,b,c毫米,设计储药槽长宽高分别是 x , y , z x,y,z x,y,z毫米。

要求药盒在储药槽内推送过程中不会出现:

1.并排重叠 ,

即储药槽高度不能高于两倍的药盒高,储药槽宽度不能高于两倍的药盒宽
{ z < 2 c y < 2 b \begin{cases}z\lt 2c\\y \lt 2b\end{cases} {z<2cy<2b

2.侧翻,

在这里插入图片描述

如上图,红色为药盒,分两种情况,情况一:绿色为储药槽;情况二:黑色为储药槽。

假设考虑的是不能完全侧翻情况,那么模型为:
{ z < b 2 + c 2 + M ( 1 − μ ) y < b 2 + c 2 + M ( 1 − v ) μ + v ≥ 1 μ , v ∈ {   0 , 1   } \begin{cases} z\lt \sqrt{b^2+c^2} + M(1-\mu)\\ y \lt \sqrt{b^2+c^2} + M(1-v)\\ \mu + v \ge 1\\ \mu,v \in \set{0,1} \end{cases} z<b2+c2 +M(1μ)y<b2+c2 +M(1v)μ+v1μ,v{0,1}
其中 M M M为定值,并且 M ≥ b 2 + c 2 M \ge \sqrt{b^2+c^2} Mb2+c2

考虑实际情况,假设侧翻角度超过 45 45 45度即为侧翻
观察上图,下方绿线和红线夹角为45度时为极限角度可以得到:
y = 2 2 ( a + b ) y = \dfrac{\sqrt{2}}{2}(a+b) y=22 (a+b)
并且侧翻时侧面解刨图来看,长方形的一个点会和储药槽底部接触,模拟物体旋转过程发现当长方形的对角线和底部垂直时候,整个物体触顶高度达到最高值。也就是说如果储药槽设计高度低于物体的对角线长度物体将无法侧翻
可以得到模型:
{ z < b 2 + c 2 + M ( 1 − μ ) y < 2 2 ( a + b ) + M ( 1 − v ) μ + v ≥ 1 μ , v ∈ {   0 , 1   } \begin{cases} z\lt \sqrt{b^2+c^2} + M(1-\mu)\\ y \lt \dfrac{\sqrt{2}}{2}(a+b) + M(1-v)\\ \mu + v \ge 1\\ \mu,v \in \set{0,1} \end{cases} z<b2+c2 +M(1μ)y<22 (a+b)+M(1v)μ+v1μ,v{0,1}
其中 M M M为定值,并且 M ≥ max ⁡ ( b 2 + c 2 , 2 2 ( a + b ) ) M \ge \max{(\sqrt{b^2+c^2},\dfrac{\sqrt{2}}{2}(a+b))} Mmax(b2+c2 ,22 (a+b))

将45度推广为 α \alpha α度(准确来讲是物体抬起的角度),模型将变为
{ z < b 2 + c 2 + M ( 1 − μ ) y < b cos ⁡ α + c cos ⁡ ( π 2 − α ) + M ( 1 − v ) μ + v ≥ 1 μ , v ∈ {   0 , 1   } \begin{cases} z\lt \sqrt{b^2+c^2} + M(1-\mu)\\ y \lt b\cos{\alpha}+c\cos{(\dfrac{\pi}{2}-\alpha)} + M(1-v)\\ \mu + v \ge 1\\ \mu,v \in \set{0,1} \end{cases} z<b2+c2 +M(1μ)y<bcosα+ccos(2πα)+M(1v)μ+v1μ,v{0,1}
其中 M M M为定值,并且 M ≥ max ⁡ ( b 2 + c 2 , b cos ⁡ α + c cos ⁡ ( π 2 − α ) ) M \ge \max{(\sqrt{b^2+c^2},b\cos{\alpha}+c\cos{(\dfrac{\pi}{2}-\alpha)})} Mmax(b2+c2 ,bcosα+ccos(2πα))

3.水平旋转 ,

实际上和侧翻的情况一类似,只是宽和高变成了长和宽
设物体水平旋转了 α \alpha α度就称为水平旋转了
y < b cos ⁡ α + a cos ⁡ ( π 2 − α ) y \lt b\cos{\alpha}+a\cos{(\dfrac{\pi}{2}-\alpha)} y<bcosα+acos(2πα)

要求药盒与两侧竖向隔板之间、与上下两层横向隔板之间应留2mm的间隙

{ z ≥ c + 2 y ≥ b + 2 \begin{cases} z\ge c+2\\ y \ge b + 2 \end{cases} {zc+2yb+2

建立解决问题的数学模型

问题一

假设已知所有盒装药品所需的储药槽宽度 x x x约束,和所有盒装药品总数 N N N
a i ≤ x i < b i , i = 1 , 2 , 3... N a_i\le x_i\lt b_i , i = 1,2,3...N aixi<bi,i=1,2,3...N

那么

解决模型一:

y j y_j yj为第 j j j种竖向隔板间距类型大小
g i j g_{ij} gij表示第 i i i种药盒可不可以放进第 j j j种药槽里面

{ min ⁡ ∑ j = 1 M f j a i g i j ≤ y j f j < b i + M ′ ( 1 − g i j ) ∑ j = 1 M g i j ≥ 1 f j , g i j ∈ {   0 , 1   } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} \min \displaystyle\sum_{j=1}^M f_j\\ a_ig_{ij} \le y_jf_j \lt b_i+M'(1-g_{ij})\\ \displaystyle\sum_{j=1}^M g_{ij} \ge 1\\ f_j , g_{ij} \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} minj=1Mfjaigijyjfj<bi+M(1gij)j=1Mgij1fj,gij{0,1}i=1,2,3,...N,j=1,2,3,...M
M ′ ≥ max ⁡ i = 1 N b i M'\ge \max_{i=1}^Nb_i Mmaxi=1Nbi
这种模型就要先求出所有可能为竖向隔板间距类型的大小

解决模型二:

我们可以得出第 i i i种药盒能放进的药槽都得出来,记做 d i j d_{ij} dij
如果 d i j = 1 d_{ij}=1 dij=1表示得出第 i i i种药盒能放进第 j j j种药槽,反之不能
{ min ⁡ ∑ j = 1 M f j ∑ j = 1 M d i j f j > 1 f j , g i j ∈ {   0 , 1   } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} \min \displaystyle\sum_{j=1}^M f_j\\ \displaystyle\sum_{j=1}^M d_{ij}f_j \gt 1\\ f_j , g_{ij} \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} minj=1Mfjj=1Mdijfj>1fj,gij{0,1}i=1,2,3,...N,j=1,2,3,...M

解决模型三:

{ a i g i ≤ x j < b i g i max ⁡ ∑ i = 1 N g i f j , g i ∈ {   0 , 1   } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} a_ig_i \le x_j \lt b_ig_i\\ \max \displaystyle\sum_{i=1}^N g_i\\ f_j , g_i \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} aigixj<bigimaxi=1Ngifj,gi{0,1}i=1,2,3,...N,j=1,2,3,...M
不断增加 M M M的值,直到答案 ∑ i = 1 N g i ≥ N \displaystyle\sum_{i=1}^N g_i \ge N i=1NgiN,就求出其中一组解

问题二

简单来说就是要求所有 药盒与两侧竖向隔板之间的间隙超出2mm的部分 之和最小
利用上一问的模型三:
{ a i g i ≤ x j < b i g i max ⁡ ∑ i = 1 N g i f j , g i ∈ {   0 , 1   } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} a_ig_i \le x_j \lt b_ig_i\\ \max \displaystyle\sum_{i=1}^N g_i\\ f_j , g_i \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} aigixj<bigimaxi=1Ngifj,gi{0,1}i=1,2,3,...N,j=1,2,3,...M
其中 M M M的临界值 M 1 M_1 M1在问题一已经求出
所以就可以规定 M ≥ M 1 M\ge M_1 MM1

同问题一的假设:
假设已知所有盒装药品所需的储药槽宽度 x x x约束,和所有盒装药品总数 N N N
a i ≤ x i < b i , i = 1 , 2 , 3... N a_i\le x_i\lt b_i , i = 1,2,3...N aixi<bi,i=1,2,3...N
观察模型一:储药槽和药盒关系模型中的所有约束条件,发现 a i a_i ai只能是药盒的宽度加两毫米,为已知量
那么药盒与两侧竖向隔板之间的间隙超出2mm的部分可以表示为:
x i − a i x_i - a_i xiai
因为还要约束两侧竖向隔板之间的间隙的种类,所以
m i n ∑ j = 1 M ∑ i = 1 N x j − a i , x j ≥ a i min \displaystyle\sum_{j=1}^M\displaystyle\sum_{i=1}^N x_j-a_i , x_j\ge a_i minj=1Mi=1Nxjai,xjai
得到

模型一:

{ m i n ∑ j = 1 M ∑ i = 1 N x j − a i , x j ≥ a i a i g i ≤ x j < b i g i ∑ i = 1 N g i = N f j , g i ∈ {   0 , 1   } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} min \displaystyle\sum_{j=1}^M\displaystyle\sum_{i=1}^N x_j-a_i , x_j\ge a_i\\ a_ig_i \le x_j \lt b_ig_i\\ \displaystyle\sum_{i=1}^N g_i = N\\ f_j , g_i \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} minj=1Mi=1Nxjai,xjaiaigixj<bigii=1Ngi=Nfj,gi{0,1}i=1,2,3,...N,j=1,2,3,...M

当然这种模型求解/优化都不容易
如果换个思路,在问题一已知有多少种两侧竖向隔板之间的间隙的种类了,并且求出了对应药盒对应的两侧竖向隔板之间的间隙,那么就可以把两侧竖向隔板之间的间隙相同的都分为一组,最后形成 M M M组药盒和对应的两侧竖向隔板之间的间隙

只需要每一组对应的两侧竖向隔板之间的间隙都取最小值,那么 M M M组加起来也就是所有 药盒与两侧竖向隔板之间的间隙超出2mm的部分 之和最小

那么

模型二:

{ a i g i ≤ x j < b i g i ∑ i = 1 N g i = N a i k j ≤ x j < b i k j m i n ∑ i = 1 N x j − a i k j , j = 1 , 2 , 3 , . . . M f j , g i , k j ∈ {   0 , 1   } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} a_ig_i \le x_j \lt b_ig_i\\ \displaystyle\sum_{i=1}^N g_i = N\\ a_ik_j \le x_j \lt b_ik_j\\ min \displaystyle\sum_{i=1}^N x_j-a_ik_j ,j = 1,2,3,...M\\ f_j , g_i , k_j\in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} aigixj<bigii=1Ngi=Naikjxj<bikjmini=1Nxjaikj,j=1,2,3,...Mfj,gi,kj{0,1}i=1,2,3,...N,j=1,2,3,...M

发现模型二实际上就是模型一的改进,模型二利用0/1变量 k j k_j kj去定位药盒所对应的两侧竖向隔板之间的间隙的同时也是在解决模型一中$ x_j\ge a_i$条件

由此就可以得到一个"通用"的解决手段:
如果出现当 x i ≤ a j x_i\le a_j xiaj时候某个式子 f ( x i , a j ) f(x_i,a_j) f(xi,aj)才执行/成立
f ( x i , a j ) , x i ≤ a j f(x_i,a_j) , x_i\le a_j f(xi,aj),xiaj
假设为 u = { f ( x i , a j ) , x i ≤ a j 0 , x i > a j u = \begin{cases}f(x_i,a_j) , x_i\le a_j\\0,x_i\gt a_j\end{cases} u={f(xi,aj),xiaj0,xi>aj
这时候引入一个0/1变量 k i k_i ki
$ \begin{cases}u =f(x_i,a_jk_i)\x_i\le a_jk_j\end{cases}$
但要注意:
1. f ( x i , a j ) 改成 f ( x i , a j k i ) f(x_i,a_j)改成f(x_i,a_jk_i) f(xi,aj)改成f(xi,ajki)时候不能改变题目本意
2.之所以是 f ( x i , a j k i ) f(x_i,a_jk_i) f(xi,ajki)而不是 f ( x i , a j ) k i f(x_i,a_j)k_i f(xi,aj)ki,是因为最好不出现决策变量和决策变量相乘
3.如果非要用 f ( x i , a j ) k i f(x_i,a_j)k_i f(xi,aj)ki,需要将决策变量和决策变量相乘的模型重新转化为线性模型

问题三

储药柜的宽度不超过2.5m、高度不超过2m,传送装置占用的高度为0.5m,即储药柜的最大允许有效高度为1.5m。
假设已知所有盒装药品所需的储药槽宽度 x x x约束,和所有盒装药品总数 N N N
a i < x i < b i , i = 1 , 2 , 3... N a_i\lt x_i\lt b_i , i = 1,2,3...N ai<xi<bi,i=1,2,3...N
假设已知所有盒装药品所需的储药槽高度度 y y y约束,和所有盒装药品总数 N N N
c i < y i < d i , i = 1 , 2 , 3... N c_i\lt y_i\lt d_i , i = 1,2,3...N ci<yi<di,i=1,2,3...N
则:
储药柜的宽度不超过2.5m
∑ i = 1 N x i ≤ 2500 \displaystyle\sum_{i=1}^N x_i \le 2500 i=1Nxi2500
储药柜的最大允许有效高度为1.5m
∑ i = 1 N y i ≤ 1500 \displaystyle\sum_{i=1}^N y_i \le 1500 i=1Nyi1500

在问题二中宽度冗余为 ∑ i = 1 N x j − a i k j \displaystyle\sum_{i=1}^N x_j-a_ik_j i=1Nxjaikj
同理我们也可以得到高度冗余为 ∑ i = 1 N y j − c i l j \displaystyle\sum_{i=1}^N y_j-c_il_j i=1Nyjcilj
平面冗余=高度冗余×宽度冗余
即平面冗余为 ( ∑ i = 1 N x j − a i k j ) ( ∑ i = 1 N y j − c i l j ) (\displaystyle\sum_{i=1}^N x_j-a_ik_j)(\displaystyle\sum_{i=1}^N y_j-c_il_j) (i=1Nxjaikj)(i=1Nyjcilj)

要使横向隔板间距的类型数量也尽可能地少。我们可以利用问题一中的模型求出横向隔板间距的类型数量临界值 M 2 M_2 M2

{ a i g i ≤ x j < b i g i ∑ i = 1 N g i = N c i o i ≤ y k < d i o i ∑ i = 1 N o i = N a i h j ≤ x j < b i h j a i l k ≤ y k < b i l k m i n ( ∑ i = 1 N x j − a i h j ) ( ∑ i = 1 N y k − c i l k ) , j = 1 , 2 , 3 , . . . M f j , g i , h j , o i , l k ∈ {   0 , 1   } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M , k = 1 , 2 , 3 , . . . K \begin{cases} a_ig_i \le x_j \lt b_ig_i\\ \displaystyle\sum_{i=1}^N g_i = N\\ c_io_i\le y_k\lt d_io_i\\ \displaystyle\sum_{i=1}^N o_i = N\\ a_ih_j \le x_j \lt b_ih_j\\ a_il_k \le y_k \lt b_il_k\\ min (\displaystyle\sum_{i=1}^N x_j-a_ih_j)(\displaystyle\sum_{i=1}^N y_k-c_il_k) ,j = 1,2,3,...M\\ f_j , g_i , h_j , o_i ,l_k\in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M ,k = 1,2,3,...K \end{cases} aigixj<bigii=1Ngi=Ncioiyk<dioii=1Noi=Naihjxj<bihjailkyk<bilkmin(i=1Nxjaihj)(i=1Nykcilk),j=1,2,3,...Mfj,gi,hj,oi,lk{0,1}i=1,2,3,...N,j=1,2,3,...M,k=1,2,3,...K

问题四

已知第 i i i种药品编号对应的最大日需求量为 e i e_i ei和该药盒长度为 z i z_i zi毫米
在储药槽的长度为1.5m、每天仅集中补药一次的情况下,计算每一种药品需要的储药槽个数 x i x_i xi.
2 ∗ 1500 e i ∗ z i ≤ x i \dfrac{2*1500}{e_i*z_i}\le x_i eizi21500xi
这样就得出了所有药品对应所需储药槽个数 x i x_i xi
在问题三中得出了一个药柜中所有横向(竖向)隔板间距的类型大小以及数量
同问题二从模型一到模型二的分组思路,每个药品其实对应一个组别
可以得出第 i i i种药品对应的组号 m i m_i mi,并且也知道组号 m i m_i mi对应的储药槽的个数 σ m i \sigma_{m_i} σmi

假设有 M M M组, x j i x_{ji} xji表示第 j j j组第 i i i种药品对应所需储药槽个数, σ j \sigma_j σj表示一个药柜种组号 j j j对应的储药槽的个数。
得到问题模型:
m i n ( m a x j = 1 M ∑ i = 1 N j x j i σ j ) min(max_{j=1}^M \dfrac{\displaystyle\sum_{i=1}^{N_j} x_{ji}}{\sigma_j}) min(maxj=1Mσji=1Njxji)

解决问题

问题一

模型一

在此之前已经初始化药盒长宽高分别放进数组length,weight,height中
处理一下数据,得到模型一的 a i a_i ai b i b_i bi,并且得到 y j y_j yj的所以可能取值
C++

void solve(){
    outFile.open("data.xlsx");
    if (!outFile.is_open()) {
        std::cerr << "无法打开文件" << std::endl;
        return ;
    }
    set<double>y;
    double a[N],b[N];
    for(int i=1;i<=1919;i++){
        a[i] = 2+weight[i];
        y.insert(a[i]);
        b[i] = min({2.0*weight[i],sqrt(weight[i]*weight[i] + height[i]*height[i]), sqrt(weight[i]*weight[i] + length[i]*length[i])});
        y.insert(b[i]);
    }
    for(int i=1;i<=1919;i++){
        outFile << a[i] << '\t';
    }
    outFile << '\n';
    for(int i=1;i<=1919;i++){
        outFile << b[i] << '\t';
    }
    outFile << '\n';
    for(auto x:y){
        outFile << x << '\t';
    }
}

这样我们就完成了上面讲的先求出所有可能为竖向隔板间距类型的大小

线性化:

void solve(){
    outFile.open("data.xlsx");
    if (!outFile.is_open()) {
        std::cerr << "无法打开文件" << std::endl;
        return ;
    }
    set<double>y;
    double a[N],b[N];
    for(int i=1;i<=1919;i++){
        a[i] = 2+weight[i];
        y.insert(a[i]);
        b[i] = min({2.0*weight[i],sqrt(weight[i]*weight[i] + height[i]*height[i]), sqrt(weight[i]*weight[i] + length[i]*length[i])});
        if((long long)b[i] == b[i])b[i]--;
        b[i] = (int)b[i];
    }
    for(int i=1;i<=1919;i++){
        outFile << a[i] << '\t';
    }
    outFile << '\n';
    for(int i=1;i<=1919;i++){
        outFile << b[i] << '\t';
    }
    outFile << '\n';
    cout << (int)y.size();
    for(auto x:y){
        outFile << x << '\t';
    }
}

解决模型一:

sets:
 aa/1..1919/:a,b;
 bb/1..47/:f,y;
 cc(aa,bb):g;
endsets
data:
 a=@ole("D:\homewrok\建模\储药柜的设计问题\data.xls",A1:BUU1);
 b=@ole("D:\homewrok\建模\储药柜的设计问题\data.xls",A2:BUU2);
 y=@ole("D:\homewrok\建模\储药柜的设计问题\data.xls",A3:AU3);
enddata
min=@sum(bb(j):f(j));
@for(aa(i):@for(bb(j):a(i)*g(i,j)<y(j)*f(j)));
@for(aa(i):@for(bb(j):b(i)+58*(1-g(i,j))>y(j)*f(j)));
@for(aa(i):@sum(bb(j):g(i,j))>1);
@for(cc(i,j):@bin(g(i,j)));
@for(bb(j):@bin(f(j)));

解得

  Global optimal solution found.
  Objective value:                              4.000000
  Objective bound:                              4.000000
  Infeasibilities:                              0.000000
  Extended solver steps:                               0
  Total solver iterations:                            13


                       Variable           Value        Reduced Cost
                          F( 7)        1.000000            1.000000
                         F( 22)        1.000000            1.000000
                         F( 33)        1.000000            1.000000
                         F( 47)        1.000000            1.000000

对应类型长度为:
18,33,44,58

模型二求解

C++预处理数据

void solve(){
    outFile.open("data2.xlsx");
    if (!outFile.is_open()) {
        std::cerr << "无法打开文件" << std::endl;
        return ;
    }
    double a[N],b[N];
    for(int i=1;i<=1919;i++){
        a[i] = 2+weight[i];
        b[i] = min({2.0*weight[i],sqrt(weight[i]*weight[i] + height[i]*height[i]), sqrt(weight[i]*weight[i] + length[i]*length[i])});
        b[i] = (int)(b[i]+0.5);
    }
    for(int i=1;i<=1919;i++){
        for(int j=12;j<=58;j++){
            int flag = a[i]<j&&j<b[i];
            outFile << flag << '\t';
        }
        outFile << '\n';
    }
}
sets:
 aa/1..1919/:;
 bb/1..47/:f;
 cc(aa,bb):d;
endsets
data:
 d = @ole("D:\homewrok\建模\储药柜的设计问题\data2.xls",A1:AU1919);
enddata
min=@sum(bb(j):f(j));
@for(aa(i):@sum(bb(j):d(i,j)*f(j))>1);
@for(bb(j):@bin(f(j)));

得到

  Global optimal solution found.
  Objective value:                              4.000000
  Objective bound:                              4.000000
  Infeasibilities:                              0.000000
  Extended solver steps:                               0
  Total solver iterations:                            58


                       Variable           Value        Reduced Cost
                          F( 8)        1.000000            1.000000
                         F( 23)        1.000000            1.000000
                         F( 33)        1.000000            1.000000
                         F( 47)        1.000000            1.000000

对应类型长度为:
19,34,44,58

纯编程求解:

问题一转换:给出1919个范围 [ a i , b i ] [a_i,b_i] [ai,bi],问最少取多少个点使得每个范围内至少有一个点

vector<pair<int,int>>v(1919);
void solve(){
    double a[N],b[N];
    for(int i=1;i<=1919;i++){
        a[i] = 2+weight[i];
        b[i] = min({2.0*weight[i],sqrt(weight[i]*weight[i] + height[i]*height[i]), sqrt(weight[i]*weight[i] + length[i]*length[i])});
        if((long long)b[i] == b[i])b[i]--;
        b[i] = (int)b[i];
        v[i-1].first = a[i]  , v[i-1].second=b[i];
    }
}
void solve2(){//贪心 每次未放入取上限最小的上限
    sort(v.begin(),v.end(),[&](pair<int,int> x, pair<int,int> y){
       if(x.first == y.first)return x.second < y.second;
       return x.first < y.first;
    });
    int cnt = 0 , start=0 , end;
    vector<pair<int,int>>ans;
    while(cnt < 1919){
        double x = v[start].second;
        cnt++;
        bool flag = false;
        for(int i=start;i<v.size();i++){
            if(v[i].first>x){
                end = i-1;
                flag = true;
                break;
            }
        }
        if(flag)
            ans.push_back(make_pair(v[end].first,x));
        else{
            ans.push_back(make_pair(v[v.size()-1].first,x));
            break;
        }
        start = end+1;
    }
    cout << cnt << '\n';//答案 4 个
    for(auto x:ans){
        cout << x.first << ',' << x.second << '\n';
    }
}

问题二转换:给出1919个范围 [ a i , b i ] [a_i,b_i] [ai,bi],给出最少取多少个点使得每个范围内至少有一个点,求全部可能取值
注:不知道最小值为4,当新题做

vector<int>ans2;
int now_ans = 47;
int k=0;//不同取值种类数
int main() {
    solve();
    sort(v.begin(),v.end(),[&](pair<int,int> x, pair<int,int> y){
        if(x.first == y.first)return x.second < y.second;
        return x.first < y.first;
    });
    solve2_f(0,1);
    cout << k;
    return 0;
}
void solve2_f(int start ,  int cnt){
    if(cnt > now_ans)return ;
    for(int i = v[start].second;i>=v[start].first;i--){
        bool flag = false;
        for(int j=start;j<v.size();j++){
            if(v[j].first>i){
                flag = true;
                ans2.push_back(i);
                solve2_f(j,cnt+1);
                ans2.pop_back();
                break;
            }
        }
        if(!flag){
            ans2.push_back(i);
            for(auto x:ans2)cout << x << ' ';
            cout << '\n';
            ans2.pop_back();
            now_ans = min(now_ans,cnt);
        }
    }
}

问题二

纯编程求解:

在上一个问题基础上加个冗余计算即可

void solve2_f(int start ,  int cnt ,int rong){
    if(cnt > now_ans)return ;
    for(int i = v[start].second;i>=v[start].first;i--){
        bool flag = false;
        int sum = 0;
        for(int j=start;j<v.size();j++){
            if(v[j].first>i){
                flag = true;
                ans2.push_back(i);
                solve2_f(j,cnt+1,rong + sum);
                ans2.pop_back();
                break;
            }
            sum += i-v[j].first;
        }
        if(!flag){
            k++;
            ans2.push_back(i);
            for(auto x:ans2)cout << x << ' ';
            cout << "rong:" << rong;
            cout << '\n';
            ans2.pop_back();
            now_ans = min(now_ans,cnt);
        }
    }
}

求解得到最小的有

19 33 44 60 rong:10875
19 33 44 59 rong:10875
19 33 44 58 rong:10875

答案为19,33,44,58
因为最后一个取值没有计算冗余度,明显取58时候冗余度是最少的

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/638995.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot实现增量部署

目录&#xff1a; 1、使用背景2、实现流程3、部署增量包到项目中并启动4、说明 1、使用背景 最近发现公司发布版本时候&#xff0c;很齐全&#xff0c;接口文档&#xff0c;部署方式等都很好&#xff0c;其中有个增量部署包&#xff0c;有点兴趣&#xff0c;不清楚怎么生成增量…

vue3+ts+vant4 实现购物车 前端代码

一、功能效果 二、前端代码 购物车的vue代码 <template><van-nav-bar left-text"返回" title"购物车" click-left"onClickLeft"><template #right><van-popover v-model:show"showPopover" placement"bot…

SQLite数据库免改造透明加密解决方案:给数据加把锁

在数字化时代&#xff0c;信息安全和隐私保护显得尤为重要。TDE透明加密技术&#xff0c;是一种在用户无感知的情况下对数据进行加密和解密的技术。它能够在数据生成、存储、传输和使用过程中自动进行加密处理&#xff0c;无需用户手动操作。透明加密技术的核心在于其透明性&am…

登录接口测试

登录接口测试 数据驱动

java spring cloud 企业工程管理系统源码+二次开发+定制化服务 em

在建筑行业中&#xff0c;工程项目管理软件&#xff08;工程项目管理系统&#xff09;扮演着至关重要的角色&#xff0c;它为建设工程项目管理提供了全方位、全过程的综合管理支持。从项目组织建设、策划决策、规划设计&#xff0c;到施工建设、竣工交付、总结评估&#xff0c;…

丰田精益生产的模板

丰田精益生产&#xff0c;也被称为丰田生产方式&#xff08;Toyota Production System, TPS&#xff09;&#xff0c;是一套完整的生产和管理系统&#xff0c;其核心目标是最大化效率、消除浪费&#xff0c;并通过持续改进来提升产品质量。 学习优秀企业 学习福特 丰田精益生产…

Java对象大小计算与MAT内存泄露分析

文章目录 JVM内存布局对象头实例数据对齐填充 计算实例数组占用内存大小String占用内存大小对象占用内存计算 使用jmap的方式查看Instrumentation计算对象内存方式MAT内存分析示例 JVM内存布局 一个对象主要包含下面3个部分&#xff1a; 对象头(Header)实例数据(Instance Dat…

WAF绕过(下)

过流量检测 这里的流量检测就是在网络层的waf拦截到我们向webshell传输的数据包&#xff0c;以及webshell返回的数据 包&#xff0c;检测其中是否包含敏感信息的一种检测方式。如果是大马的情况下&#xff0c;可以在大马中添加多处判断代码&#xff0c;因此在执行大马提供的功…

最新FinalShell专业版激活

支持的版本 可以激活任意版本的FinalShell为专业版&#xff0c;包括最新版4.3.10 激活方式 打开FinalShell&#xff0c;点击左下角 激活/升级。 账号密码任意输入几个字符&#xff0c;点离线激活。 复制机器码&#xff0c;将机器码发送给微信公众号【小白学算法】见文章末…

如何解决Nginx反向代理不生效?

目录 背景 过程 日志 检查配置文件 重启服务 检查容器内的配置文件 容器和宿主机 其他 背景 用了两年的nginx新加的反向代理不生效 Docker挂载的配置文件启动的Nginx&#xff0c;配置一切正常&#xff0c;但是反向代理不生效&#xff0c;???先自查一波 过程 日志 …

Function Calling 介绍与实战

functions 是 Chat Completion API 中的可选参数&#xff0c;用于提供函数定义。其目的是使 GPT 模型能够生成符合所提供定义的函数参数。请注意&#xff0c;API不会实际执行任何函数调用。开发人员需要使用GPT 模型输出来执行函数调用。 如果提供了functions参数&#xff0c;…

创新指南|利用电商产品视频进行渠道营销的最佳策略,不断提升销售额

无论企业的利基市场如何&#xff0c;电商产品视频都已被证明是非常可靠的资产&#xff0c;可以让目标受众了解您所提供的产品——关键功能、展示重要的差异化优势甚至改变大多数营销活动的游戏规则。阅读本文&#xff0c;全面了解电商产品视频如何融入营销推广&#xff0c;以最…

【保姆级教程】基于OpenCV+Python的人脸识别上课签到系统

【保姆级教程】基于OpenCVPython的人脸识别上课签到系统 一、软件安装及环境配置1. 安装IDE&#xff1a;PyCharm2. 搭建Python的环境3. 新建项目、安装插件、库 二、源文件编写1. 采集人脸.py2. 训练模型.py3. 生成表格.py4. 识别签到.py5. 创建图形界面.py 三、相关函数分析1.…

浅谈分布式系统

目录 一、单机架构二、分布式架构1、应用服务与数据库分离2、负载均衡3、数据库读写分离4、引入缓存5、数据库分库分表6、引入微服务 一、单机架构 单机架构&#xff0c;只有一台服务器&#xff0c;这个服务器负责所有工作。 绝大多数公司的产品&#xff0c;都是这种单机架构。…

思科模拟器--06.单臂路由升级版--多端路由互连实验--24.5.20

实验图纸如下: 第0步: 先放置六台个人电脑,一台交换机和一台2911路由器(千兆路由器(G0开头的)) 接着,用直通线将 PC0的F0,PC1的F0分别和交换机的F0/0, F0/1连接 交换机的F0/3和路由器的G0/0连接 PC2的F0,PC3的F0分别和交换机的F0/4, F0/5连接 交换机的F0/6和路由器的G0/1…

【施磊】C++语言基础提高:深入学习C++语言先要练好的内功

课程总目录 文章目录 一、进程的虚拟地址空间内存划分和布局二、函数的调用堆栈详细过程三、程序编译链接原理1. 编译过程2. 链接过程 一、进程的虚拟地址空间内存划分和布局 任何的编程语言 → \to → 产生两种东西&#xff1a;指令和数据 编译链接完成之后会产生一个可执行…

【传知代码】Modnet 人像抠图-论文复现

文章目录 概述原理介绍核心逻辑ModNet 的结构 环境配置WebUI 小结 论文地址 论文GitHub 本文涉及的源码可从Modnet 人像抠图该文章下方附件获取 概述 人像抠图技术在多个领域有着广泛的应用场景&#xff0c;包括但不限于&#xff1a; 展馆互动拍照&#xff1a;展馆中使用的抠…

K8S认证|CKA题库+答案| 11. 创建PVC

11、创建PVC 您必须在以下Cluster/Node上完成此考题&#xff1a; Cluster Master node Worker node ok8s master …

玩转OpenHarmony智能家居:如何实现开发版“碰一碰”设备控制

一、简介 “碰一碰”设备控制&#xff0c;依托NFC短距通信协议&#xff0c;通过碰一碰的交互方式&#xff0c;将OpenAtom OpenHarmony&#xff08;简称“OpenHarmony”&#xff09;标准系统设备和全场景设备连接起来&#xff0c;解决了应用与设备之间接续慢、传输难的问题&…

Java web应用性能分析之【高并发之缓存-多级缓存】

说到缓存&#xff0c;作为java开发第一时间想到的是不是上图所示的Redis&#xff0c;又或者是Guava Cache、Caffeine、EhCache这些&#xff1b;Redis作为分布式缓存、其他的可以作为本地缓存。但是作为一名资深开发人员&#xff0c;着眼的层面应该再提升一个级别&#xff0c;从…