下载文档原格式
图论与网络最优化算法答案【篇一：《运筹学》复习题】一、名词解释1松弛变量为将线性规划问题的数学模型化为标准型而加入的变量。
2可行域满足线性约束条件的解（x,y）叫做可行解，由所有可行解组成的集合叫做可行域。
3人工变量亦称人造变量.求解线性规划问题时人为加入的变量。
用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵a中所含的单位向量常常不足m个，此时可加入若干(至多m)个新变量，称这些新变量为人工变量。
4对偶理论每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。
研究线性规划中原始问题与对偶问题之间关系的理论5灵敏度分析研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。
在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。
通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。
6影子价格反映资源配置状况的价格。
影子价格是指在其他资源投入不变的情况下,每增加一单位的某种资源的投入所带来的追加收益。
即影子价格等于资源投入的边际收益。
只有在资源短缺的情况下,每增加一单位的投入才能带来收益的增加7产销平衡运输一种特殊的线性规划问题。
产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。
8西北角法是运筹学中制定运输问题的初始调运方案（即初始基可行解）的基本方法之一。
也就是从运价表的西北角位置开始，依次安排m个产地和n个销地之间的运输业务，从而得到一个初始调运方案的方法。
9最优性检验检验当前调运方案是不是最优方案的过程。
10动态规划解决多阶段决策过程优化问题的方法：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解11状态转移方程从阶段k到k+1的状态转移规律的表达式12逆序求解法在求解时，首先逆序求出各阶段的条件最优目标函数和条件最优决策，然后反向追踪，顺序地求出改多阶段决策问题的最优策略和最优路线。
第52卷第6期电力系统保护与控制Vol.52 No.6 2024年3月16日Power System Protection and Control Mar. 16, 2024 DOI: 10.19783/ki.pspc.230917基于深度强化学习的Π型阻抗匹配网络多参数最优求解方法胡正伟，夏思懿，王文彬，曹旺斌，谢志远(华北电力大学电子与通信工程系，河北 保定 071003)摘要：针对电力线信道阻抗变化复杂、负载阻抗不匹配造成通信质量差等问题，提出一种基于深度强化学习的Π型阻抗匹配网络多参数最优求解方法，并验证分析了深度强化学习对于寻找最优匹配参数的可行性。
首先，建立Π型网络结构，推导窄带匹配和宽带匹配场景下的最优匹配目标函数。
其次，采用深度强化学习，利用智能体的移动模拟实际匹配网络的元件参数变化，设置含有理论值与最优匹配值参数的公式作为奖励，构建寻优匹配模型。
然后，分别仿真验证了窄带匹配和宽带匹配两种应用场景并优化模型的网络参数。
最后，仿真结果证明，经过训练后的最优模型运行时间较短且准确度较高，能够较好地自动匹配电力线载波通信负载阻抗变化，改善和提高电力线载波通信质量。
关键词：深度强化学习；电力线通信；窄带匹配；宽带匹配Multi-parameter optimal solution method for Π-type impedance matching networksbased on deep reinforcement learningHU Zhengwei, XIA Siyi, WANG Wenbin, CAO Wangbin, XIE Zhiyuan(Department of Electrical & Electronic Engineering, North China Electric Power University, Baoding 071003, China)Abstract: There are problems of complex power line channel impedance variation and poor load impedance mismatch.Thus a multi-parameter optimal solution method for a Π-type impedance matching network based on deep reinforcement learning is proposed, and the feasibility of deep reinforcement learning for finding the optimal matching parameters is verified and analyzed. First, the Π-type network structure is established to derive the objective function for the optimal matching in the narrowband matching and broadband matching scenarios. Secondly, deep reinforcement learning is used to use the movement of the agent to simulate the component parameters of the actual matching network, and set the formula containing the theoretical value and the optimal matching value of the parameters as a reward to build the optimal matching model. Then, this paper separately verifies the network parameters of narrowband matching and broadband matching application scenarios and optimizes the network parameters of the model. Finally, the simulation results prove that the trained optimal model has short running time and high accuracy. It can better automatically match the load impedance change of power line carrier communication, and improve the quality of power line carrier communication.This work is supported by the General Program of National Natural Science Foundation of China (No. 52177083).Key words: deep reinforcement learning; power line communication; narrowband matching; broadband matching0 引言随着科技的进步，电力线通信技术飞速发展，对电力线载波通信质量也提出了更高的要求[1-3]。
图论与网络优化问题简介数学建模题目类型： B. 运筹学（公交车调度、灾情巡回路线、矿山车辆安排）一、 图的基本概念:1. 通过 Euler 七桥问题介绍2. 赋权图（网络）：二、 图论中的传统优化问题1. 最小生成树问题：应用背景：交通网的设计算法： Greedy Algorithm (贪婪算法)破圈法(Rosenstiehl 1967):i) ;)0(G G ←0←k .ii) 若)(k G 不含圈，则它就是G 的最小支撑树；若)(k G 中含圈，设C 为)(k G 中任意一个圈，取C 上最大权的边)(k e ，令)()()1(k k k e G G -=+iii) ,1+←k k 重复ii).避圈法(Rosenstiehl 1967):i) );()0(φ，V G ←0←k .ii) 若)(k G 是连通，则它就是G 的最小支撑树；若)(k G 不连通，设)(2)(1,k k G G 为)(k G 中的两个分图，在连结这两分图的边中取权最小的边)(k e ，令)()()1(k k k e G G +=+iii) ,1+←k k 重复ii).例2. 最大匹配问题实 例: 边赋权图),(E V G =可行解: G 中的边独立集M目 标：极小化M 上所有边的权和.算 法： Edmonds 19653. 中国邮路问题：管梅谷 1960一个邮递员送信时，要走遍他所负责的每条街道，完成送信任务后回到邮局. 他应按什么样的路线走，使走的总里程最短?实 例: 边赋权图),(E V G =可行解: 通过G 中所有边的圈C （未必是简单的）目 标：极小化圈C 上所有边的权和.算 法： Edmonds, Johnson 1973i) 设G 的奇点为k v v v 221,,, , 构造k 2阶完全图H ,=)(H V },,,{221k v v v , 边j i v v 上的权为G 中连结i v 与j v 的最短路的权.ii) 在H 中求权和最小的完美对集M .iii) 对k j ,,2,1 =, 设j P _是G 中连结M e j∈的两个端点的最短路. 令kj j P E E 1)(*==, 则过*E E ⋃的Euler 圈即为中国邮路问题的解.4. 货郎问题：一个推销员要到若干个城市推销货物，然后回到出发点. 他应按如何选择旅行路线，使每个城市通过一次且仅一次，并且总的里程最短?实 例: 边赋权图),(E V G =可行解: 通过G 中所有边的圈C （未必是简单的）目 标：极小化圈C 上所有边的权和.近似算法：两边交换算法、三边交换算法、 (欧氏距离下) 1.5 近似算法i) Find a MST of G . Say T .ii) Find a minimum cost perfect matching,M ,on the set of odd-degree vertices of T . AddM to T and obtain an Eulerian graph .iii) Output the tour that visit the vertices of G inthe order of their first appearance in T .例：1234561123453261→三、通讯网络中的优化问题1.经典最小Steiner树问题: 给定平面上若干个点，如何将它们连接起来使得连线长度最短？解的结构：该问题的解一定有树的结构(Steiner树)，而且可能会引入一些新的点( Steiner 点)定理（M. R. Garey et al, 1979）最小Steiner树问题是NP-难解的.定理（J. B. Kruskal, 1956; R. C. Prim, 1967）最小生成树问题是可以用贪婪算法在多项式时间内求解的.定理（D.-Z. Du et al, 1979）最小生成树与最小Steiner树权重之比不超过2。
