论文部分内容阅读
本文主要研究两大类问题：哈明距离下的逆优化问题和多物品的生产与分配问题.对一个给定的(组合)优化问题，逆优化问题研究如何尽可能少地改变原问题中的权参数，使得某些给定的解是问题在新的权参数下的最优解.由于该类问题不仅有很重要的理论研究价值，而且有很大的实际应用价值，因此引起了许多学者的重视.许多文章研究了在l1，l∞和l2范数下的逆优化问题.尽管哈明距离下的逆优化问题在实际生活中有许多应用，但很少有文章讨论该类问题.本文我们研究哈明距离下的逆优化问题.
由于物品的制造与分配问题有很重要的理论研究与实际应用价值，因此引起了许多学者的注意.该问题可以描述为：有一些客户，他们需要一定数量的产品，这些产品是通过一些工厂加工制造生产出来的，并通过一些分配中心运送到每个客户.如何安排原材料购置、产品的生产与分配，使得总的费用最小.本文我们也将研究多物品的制造与分配问题.
在第二章，我们研究以下的求和型哈明距离下的赋权逆最小支撑树问题：对给定的一个连通无向图G，每条边都有一个权和改造费用.令T0为图G的一个支撑树.如何改变图的边权向量使得T0为图G在新的权向量下的一个最小支撑树，且在哈明距离下的总的改造费用最小.我们讨论了三种模型：无界情形，带禁忌边的无界情形和有界情形.应用求二分图的赋权顶点覆盖方法以及求最小割的算法等求解所建立的数学模型，从而得出这三类问题都是强多项式时间可解的.
在第三章，我们研究如下的约束瓶颈型哈明距离下的逆最小支撑树问题：对给定的一个连通无向图G，每条边都有一个权和改造费用，T0为图G的一个支撑树.如何改变图的边权向量使得：(1)T0为图G在新的权向量下的一个最小支撑树，(2)在哈明距离下的总的改造费用不超过给定的值，(3)改变的边的改造费用的最大值尽可能地小.我们讨论了三种模型：无界情形，标准情形和约束情形.应用二分图的瓶颈型赋权顶点覆盖方法及二分法等得出这三类问题都是强多项式时间可解的.
在第四章，我们首先讨论了求和型哈明距离下的中心选址改造问题，该问题可以描述为：对给定的一个连通无向图G，每条边都有一个长度和改造费用，如何改变图的边长度向量使得在新的长度向量下从给定的顶点s到网络的其它顶点的距离不超过给定的上界，且在哈明距离下的总的改造费用最小.我们利用把集覆盖问题的实例L-归约到该问题的实例，证明了对该问题构造一个近似性能比为O(log｜V｜)的近似算法是NP困难的.接着我们研究了如下的瓶颈型哈明距离下的中心选址改造问题：如何改变图的边长度向量使得在新的长度向量下从给定的顶点s到网络的其它顶点的距离不超过给定的上界，且改变的边的改造费用的最大值尽可能地小.我们给出了该问题的一个强多项式算法.
在第五章，我们研究了如下的求和型哈明距离下的最短路改造问题：对给定的一个连通无向图G，每条边都有一个长度和改造费用，我们要求改变图的边长度向量使得在新的长度向量下从给定的顶点si到顶点ti(i=1，2，…，r)的距离不超过给定的上界di，且在哈明距离下的总的改造费用最小.我们利用把3-SAT问题的实例多项式时间归约到该问题的实例，证明了该问题是强NP困难的.对该问题的一类特殊问题：链网络下的单发点、单收点的求和型哈明距离下的最短路改造问题，我们利用把背包问题的实例多项式时间归约到该问题的实例，证明了该问题是NP困难的.同时对该问题给出了一个伪多项式时间的动态规划算法.
在第六章，我们研究了如下的多物品的生产与分配问题：有多个客户，他们需要不同的物品，这些物品是由工厂生产或通过物品供应商直接提供并运送到一些分配中心(DC)，并统一由分配中心供给.如果某类物品是由工厂生产，则该类物品及某些物品是由原材料供应商提供给该工厂的原材料按某种比例加工生产得到的.一个客户由一个分配中心服务.如何安排工厂的生产，如何从物品(原材料)供应商进货，哪些分配中心投入使用，如何决定分配中心服务客户的方式以及如何安排运货等使得总的费用最小.我们把该问题转化为混合整数规划问题，利用Benders分解方法给出了求解该问题的算法.另外，我们还考虑了一类广义的多物品的生产与分配问题.
在第七章，我们研究了如下的最小分配费用流问题：有多个客户，只有一个物品供应商.每个客户需要一定数量的物品，该物品是通过一些分配工厂或一些物品中间商提供给客户.某客户或中间商按一定的比例从某分配工厂得到的货物.如何从物品供应商处进货，如何安排运货等使得总的费用(运输费用，储存费用)最小.我们讨论了该问题的基本可行图的性质并给出了一个求解该问题的原始基本可行解的算法.利用网络单纯型法，我们解决了该类最小分配费用流问题.本章我们还研究了如何得到增广网络问题的一个可行基.
最后，我们总结了该论文的研究成果，并对这两个领域中的研究问题给出了一些初步的探讨.