论文部分内容阅读
本文研究了广义上界问题的反问题及广义最大流问题的反问题。
第一章中讨论了广义上界问题的反问题,本章考虑的广义规划问题的反问题是在一般线性规划反问题的基础上,通过尽可能少的改变目标函数中价值系数的取值,使得给定的可行解成为所给广义规划问题的最优解。我们利用线性规划的最优性条件,给出了(GUB)问题在ι1模和ι∞义下的反问题的数学模型及求解方法。并且在ι1模意义下我们给出了把(GUB)问题的反问题转化为它的对偶问题求解的一种方法,若在给定的(GUB)问题的一个0-1可行解,并且(GUB)问题的一个最优解的所有分量是在0与1之间的条件下。
第二章中讨论了广义最大流问题的反问题,首先给出在通常情况下的最大流模型,由于实际生活中网络流的变量通常是有下界变量的,所以我们提出了广义最大流问题的模型,并提出了(GMF)问题修正的Ford-Fulkerson(1956)算法,给出并证明了反问题有解的充要条件,并从线性规划的角度将(GMF)的反问题转化为它的对偶问题的最小割问题来解决。