论文题目: 哈明距离下的逆优化问题及多物品的制造与分配问题
论文类型: 博士论文
论文专业: 运筹学与控制论
作者: 张斌武
导师: 何勇,姚恩瑜,祁力群
关键词: 逆优化问题,网络改进问题,哈明距离,计算复杂性,多物品的生产与分配,最小分配费用流
文献来源: 浙江大学
发表年度: 2005
论文摘要: 本文主要研究两大类问题：哈明距离下的逆优化问题和多物品的生产与分配问题。 对一个给定的（组合）优化问题，逆优化问题研究如何尽可能少地改变原问题中的权参数，使得某些给定的解是问题在新的权参数下的最优解，由于该类问题不仅有很重要的理论研究价值，而且有很大的实际应用价值，因此引起了许多学者的重视。许多文章研究了在l1，l∞和l2范数下的逆优化问题。尽管哈明距离下的逆优化问题在实际生活中有许多应用，但很少有文章讨论该类问题。本文我们研究哈明距离下的逆优化问题。 由于物品的制造与分配问题有很重要的理论研究与实际应用价值，因此引起了许多学者的注意。该问题可以描述为：有一些客户，他们需要一定数量的产品，这些产品是通过一些工厂加工制造生产出来的，并通过一些分配中心运送到每个客户。如何安排原材料购置、产品的生产与分配，使得总的费用最小。本文我们也将研究多物品的制造与分配问题。 在第二章，我们研究以下的求和型哈明距离下的赋权逆最小支撑树问题：对给定的一个连通无向图G，每条边都有一个权和改造费用。令T0为图G的一个支撑树。如何改变图的边权向量使得T0为图G在新的权向量下的一个最小支撑树，且在哈明距离下的总的改造费用最小。我们讨论了三种模型：无界情形，带禁忌边的无界情形和有界情形。应用求二分图的赋权顶点覆盖方法以及求最小割的算法等求解所建立的数学模型，从而得出这三类问题都是强多项式时间可解的。 在第三章，我们研究如下的约束瓶颈型哈明距离下的逆最小支撑树问题：对给定的一个连通无向图G，每条边都有一个权和改造费用，T0为图G的一个支撑树。如何改变图的边权向量使得：（1）T0为图G在新的权向量下的一个最小支撑树，（2）在哈明距离下的总的改造费用不超过给定的值，（3）改变的边的改造费用的最大值尽可能地小。我们讨论了三种模型：无界情形，标准情形和约束情形。应用二分图的瓶颈型赋权顶点覆盖方法及二分法等得出这三类问题都是强多项式时间可解的。 在第四章，我们首先讨论了求和型哈明距离下的中心选址改造问题，该问题可以描述为：对给定的一个连通无向图G，每条边都有一个长度和改造费用，如何改变图的边长度向量使得在新的长度向量下从给定的顶点s到网络的其它顶点的距离不超过给定的上界，且在哈明距离下的总的改造费用最小。我们利用把集覆盖问题的实例L-归约到该问题的实例，证明了对该问题构造一个近似性能比为O（log|V|）的近似算法是NP困难的。接着我们研究了如下的瓶颈型哈明距离下的中心选址改造问题：如何
论文目录:
Acknowledgements
Abstract(Chinese)
Abstract(English)
1 Introduction
§1.1 Inverse optimization problems
§1.1.1 Inverse optimization problems and their applications
§1.1.2 A short survey of inverse optimization problems
§1.2 Multicommodity production and distribution problems
§1.3 Some definitions of computational complexity
§1.4 Main results of the dissertation
2 Weighted inverse minimum spanning tree problems under the sum-type Hamming distance
§2.1 Introduction
§2.2 The unbounded problems
§2.3 The unbounded problems with forbidden edges
§2.4 The bounded problems
3 Inverse minimum spanning tree problems under the bottleneck-type Hamming distance
§3.1 Introduction
§3.2 The unbounded problems
§3.3 The standard problems
§3.4 The constrained problems
4 The center location improvement problems under Hamming distance
§4.1 Introduction
§4.2 The problems under the sum-type Hamming distance
§4.3 The problems under the bottleneck-type Hamming distance
§4.4 Conclusions
5 The shortest path improvement problems under Hamming distance
§5.1 Introduction
§5.2 The shortest path improvement problems under Hamming distance
§5.3 The problems with a single source and a single terminal
6 A multicommodity production and distribution model in supply chain
§6.1 Introduction
§6.2 Features of the model
§6.3 The algorithm of the model
§6.4 A generalized multicommodity production and distribution model
7 A minimum distribution cost flow problem
§7.1 Introduction
§7.2 Basic feasible graph and optimality conditions of the problem
§7.3 Solving a basic feasible solution of the problem of augmented network
8 Conclusions
Bibliography
Finished or Published papers
发布时间: 2006-09-05
参考文献
- [1].图的临界群研究[D]. 王健.中国科学技术大学2010
- [2].赋权哈明距离下若干网络逆问题的研究[D]. 刘龙城.浙江大学2009
- [3].图中参数与树型结构研究[D]. 陈园.华中师范大学2013
- [4].图的拉普拉斯矩阵和临界群[D]. 梁浩.中国科学技术大学2009
- [5].连通图中可去边和圈的研究[D]. 康海燕.山东大学2010
- [6].图的哈密尔顿连通性及支撑树特征研究[D]. 章舜哲.华中师范大学2015
相关论文
- [1].求解半定约束二次规划逆问题的数值方法[D]. 肖现涛.大连理工大学2009
- [2].图的控制数及其相关参数[D]. 单而芳.上海大学2005
- [3].不确定优化问题的若干模型与算法研究[D]. 戎晓霞.山东大学2005
- [4].自对偶置换码和m-重量[D]. 袁媛.武汉大学2005
- [5].复杂网络的演化机制及若干动力学行为研究[D]. 王冰.大连理工大学2006
- [6].当代工业中的若干排序问题研究[D]. 季敏.浙江大学2006
- [7].计算生物学中若干组合优化问题的研究[D]. 陈汀.浙江大学2006
- [8].若干批处理机排序与装箱问题的算法研究[D]. 石永强.浙江大学2005
- [9].最小费用网络流的若干新问题研究[D]. 鲁海燕.浙江大学2007
- [10].组合优化中的逆目标问题[D]. 盖玲.浙江大学2007
标签：逆优化问题论文; 网络改进问题论文; 哈明距离论文; 计算复杂性论文; 多物品的生产与分配论文; 最小分配费用流论文;