CUMCM2021-C

KO | EN

gitlite — search

#python #hacktoberfest #go #machine-learning #rust #deep-learning #docker #macos #awesome #kubernetes #awesome-list #security #ios #openai

(★ 20)

全国大学生数学建模竞赛CUMCM C题全国二等奖代码

CUMCM2021-C 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# CUMCM2021-C-
全国大学生数学建模竞赛CUMCM C题 全国二等奖 代码

**代码是21年比赛时候写的，本着能跑就行的原则写的比较乱hhhhh，仅供各位参考**

# 附论文大体思路：

**以下部分仅为论文思路总结与梳理，论文中还包含诸多对于规划结果的分析评价以及灵敏度分析，以下内容不代表论文实际品质**

**（奇怪的声明增加了.jpg）**

## 第1问
构建下图指标体系，通过主成分分析法进行评价
![image](https://user-images.githubusercontent.com/84163279/175571140-bad07b80-58d6-471a-9d66-0ef9e2ce4eb1.png)

## 第2-4问思路
**第2-4问遵循相似的解题思路，会根据题目具体要求调整目标函数和约束条件**

### 1. 供应商甄选模型

- 基于第1问选择初的50家供应商，通过0-1规划具体确定选用哪几家供应商
- 在第3，4问中，放开为全部的50家供应商（第1问中选出的最重要的50家）参与供货

### 2. 供货与订购量规划模型

- 运用多目标线性规划来求解某一周的供货量安排，并利用历史数据所反映的供货量与订货量的关系，推算当周订货量计划
- 目标函数1是当周各供应商供货量与其对应的价格乘积的求和，表示企业用于购买原材料本身的总费用。目标函数2是当周企业的转运和储存成本。
- 约束条件 1 为当周供应商能供应的货物不超过其自身供应能力的范围。约束条件 2 为当周各供应商供货量与其对应的转化率乘积的求和（供货量总共能生产的产品数）不小于当周期望供货量转化得到的产能，保障企业生产。
  - 供应商自身供应能力的范围：第k周最大供货量的计算方法为取该供应商历史5年中每一年的第k周及齐之后4周数据组成共20个元素的集合，取该集合最大值作为未来第k周最大供货量。
  - 订货量与供货量的偏差：供货量会以一定的偏移比率β偏离订货量，而β的测定使用了过去 5 年历史偏移数据按年平均后加权求和取得。

### 3. 转运策略模型

- 该子模型中，决策变量是当周 n×8 的矩阵，矩阵中第 i 行第j列 d_ij 表示第 i 家供应商使用第j家转运上配送的原材料数量占该供应商总供货量的比例。

- 规划模型如下：

![image](https://user-images.githubusercontent.com/84163279/181274075-dc1df45c-4137-4e6d-9f7f-f0be8a97f4a2.png)

- 目标函数 1 表示转运过程中的总损耗。利用各家转运商负责的转运货物额与其各 自的损耗率相乘，为更确切体现对生产影响，又乘以各材料的转化率。各家转运商负责的转运货物额通过供应商的当周供应量与转运商在该供应量中负责的比例计算。

- 约束条件 1 表示对于任意一家供应商的，8 家转运商对其负责的比例之和应为 1， 确保货物全部运输。

- 约束条件 2 是各家供应商当周供应量乘以特定转运商负责的比例再求和，即某一 家转运商需要负责的总运送额，值应该小于 6000。

-  约束条件 3 和 4 用于分类讨论单家供应商单周供货情况，不超过单家转运商运力 极限时尽可能比例为 1，若供货量超出单家转运商运力极限，则其只能承担不足 1 的 比例。

- 在实际计算中订购规划和转运规划是交叉进行的

1. 求得第1周供货量，并通过供货量与订货量的偏差β估算订货量

2. 求解第1周转运方案
  3. 计算第1周库存，得到第2周期望的总供货量
  4. 依以上步骤依次求解第2周 - 第24周结果

![image](https://user-images.githubusercontent.com/84163279/181274240-0109fbc6-9791-4571-97a6-1a904bf1f6d7.png)

### 4. 求解转运策略的遗传算法

模型三的约束条件较为复杂，普通的遗传算法计算较慢，且优化效果较差。因此针对模型三特殊的约束条件，通过设计交叉和变异算子，保证了子代以较大概率在约束条件之内，通过引入罚函数和改进选择策略，提高了遗传算法的性能和效果。下文对改进后的遗传算法的进行说明：

#### 算法步骤：

1. 通过针对性设计的搜索算法获得满足约束条件的可行解集，初始化模型

2. 对父代A进行交叉和变异操作，获得子代B

3. 将父代A与子代B合并，得到新子代C

4. 将新子代C中不满足约束条件的个体抛弃

5. 计算新子代中剩余个体的适应度

6. 使用轮盘赌法获得下一代

7. 收集本轮迭代中最优个体

8. 重复步骤②—⑦，直到达到规定的循环次数

9. 在收集到历次迭代中的最优个体中选择所有迭代中最优个体输出

![image](https://user-images.githubusercontent.com/84163279/181274356-c8fe80d6-1c36-452e-96d6-fde5a5d146dd.png)

#### 适应度函数

- 子模型三中目标函数为原材料损失导致的产品产量损失值，损失值越小越好，故目标函数值越小，个体的适应度越大。因此选择如下公式作为适应度函数。

![image](https://user-images.githubusercontent.com/84163279/181274397-13f84611-e566-4d5e-802c-0c56e4fe61b0.png)

#### 对约束条件的处理

- 含约束条件的遗传算法包含如下若干几种解决思路
  - 将约束条件融入目标函数中，将带约束条件的规划问题转化为不带约束条件的规划问题。
  - 设计特殊的编码规则，令解码后的值只能处在约束条件范围内。
  - 设计特殊的叫交叉和变异算子，令交叉和变异之后的个体依然落在约束条件范围内。
  - 引入罚函数，降低超出约束条件个体的适应度或令其“死亡”。
  - 令超出约束条件的个体重新进行交叉变异。
  - 将超出约束条件的个体放置于约束条件边界处。

- 本文选择了通过设计交叉变异算子，令交叉和变异之后的个体依然落在约束条件范围内，以及引入罚函数来解决约束问题。

##### 罚函数的选取

- 罚函数的作用是降低超出约束条件个体的适应度函数，令其以更小的概率被选入下一代中。本文问简化算法设计，采用“死亡惩罚”，即令超出约束条件的个体适应度为0。在算法实际运行过程中，在使用轮盘赌法选取下一代之前先计算每个个体是否满足约束条件，并将不满足条件的个体抛弃。

##### 交叉算子的设计

在本遗传算法的种群中，每个个体即为一种转运方案。若将两个个体的数据任意交换，会有很大概率令生成的子代不满足如下约束条件：

![image](https://user-images.githubusercontent.com/84163279/181274479-40566249-4e50-4c5d-9538-8f7320e4c8f4.png)

因此在交换时选择两种方案中某一家供应商的运输方案进行交换，具体的操作流程为：

1. 确定交换个体，随机选择被交换个体

2. 随机选择要交换的运输方案

3. 交换

使用本交换算子得到的子代天然满足模型三4个约束条件中的3个：

![image](https://user-images.githubusercontent.com/84163279/181274525-1e3b3150-ef6d-426e-bcb2-ca770a6813e0.png)

##### 变异算子的设计

- 对浮点数编码的遗传算法的一般变异算子是在取值范围内随机改变某一个值，但是与交叉算子类似，在本模型中采取这种方法同样容易导致子代不满足约束条件。因此本文提出特定针对本模型约束条件的变异算子。

- 该算子分为两部分。

- 第1步以一定概率对某个个体中某家供应商运输方案进行打乱重排序。当供应商只选择1家转运商时，重排序相当于更换该供应商的配送商。例如某家供货商的配送方案为![image](https://user-images.githubusercontent.com/84163279/181274600-5730cdda-378a-447a-afe5-66f3a8d25d03.png)，则经过变异算子计算后可能变为![image](https://user-images.githubusercontent.com/84163279/181274652-cfcf57db-ac73-49d8-acf5-a0afd0c6bcc5.png)，相当于将该供应商选择的转运商从T4调整为T2.当供应商选择多家转运商时，重排序相当于将同样的数量的原材料交由不同转运商运输。例如原方案为![image](https://user-images.githubusercontent.com/84163279/181274718-75d0c166-287f-4c46-9162-343e972c6b56.png)，变异之后的方案为![image](https://user-images.githubusercontent.com/84163279/181274739-fa6e6125-c445-4f98-9551-419ef3370ee7.png)相当于将转运商从T2，T3，T6修改为T3，T4，T6，修改了供应商每批货的转运商，但是不修改每批货的数量。

- 第2步针对供货量大于6000，选择多家转运商的供货商。同样以一定概率为其重新制定一个转运方案。例如方案![image](https://user-images.githubusercontent.com/84163279/181274778-a273839e-8eb6-4c7a-861c-e21e219ecd79.png)在这一步可能变为![image](https://user-images.githubusercontent.com/84163279/181274810-ea2cd700-eb08-43ea-b197-de03eec35491.png)，与之前的方案完全不同。

- 通过2步变异得到的新个体同样天然满足模型三中4个约束条件的3个：

![image](https://user-images.githubusercontent.com/84163279/181274835-49ca9623-78e9-4acb-9a9f-0d732f3166f9.png)

#### 其他优化

在模型3中，复杂的约束条件同样影响了模型的收敛和运行速度，因此采用下列三种改进措施以提高遗传算法的效率：

##### 1.改进的选择方法

- 本遗传算法中对父代进行交叉编译得到子代，将父代与子代中满足约束条件的个体合并得到新子代，使用轮盘赌方法从新子代中选择下一代个体。将父代与子代合并后选择下一代可以避免交叉和变异导致的父代中优良个体丧失，有助于保留父代的优良特征，使算法更快收敛。但是，过多保留父代特征容易导致算法收敛于局部最优而非全局最优，对此我们采取提高种群中个体数量的方式，通过更多个体来容纳更多信息，令算法更容易收敛于全局最优。

##### 2.最优结果的选取

- 本文选取所有迭代中产生的的全局最优点而非最后一次迭代中种群的最优点。

##### 3.初始值的选取

- 初始化遗传算法需要传入一定数量的初始种群，而种群中个体应当为满足约束条件的可行解。满足约束条件的可行解可以通过随机法来搜索。具体过程如下：

1. 通过计算机随机生成满足约束条件1，3，4的方案。

2. 判断其是否满足约束条件2，若满足则输出结果，否则重复步骤①

- 实际上当供应商数量达到50左右时，随机法搜索得到可行解的效率极低，因此设计一种快速计算可行解的方案以提高模型的运行效率，其伪代码如下：

```
while True:
    array=zero(50，8) # 生成50*8的零矩阵
    for supply_amount in sort(supplier): # 按供货量从大到小遍历所有供应商
        if supply_amount>6000
            生成1*8的随机数矩阵A，令矩阵所有元素和为1
            将array对应位置替换为A
        else
            生成1*8的0/1矩阵B，矩阵中元素为7个0，1个1
            令矩阵中元素1以概率p落入矩阵B的第个位置,p的公式见下方
            将array对应位置替换为B
    if array满足约束条件2:
        return array
```

![image](https://user-images.githubusercontent.com/84163279/181274889-fc5dd3a6-8b06-4e7a-bb07-9a1a42637144.png)

CUMCM2021-C

CUMCM2021-C 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

CUMCM2021-C

CUMCM2021-C 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README