东南大学运筹学试卷.pdf

《东南大学运筹学试卷》涉及了多个线性规划及其相关知识点，包括线性规划的求解、对偶问题、灵敏度分析、单纯形法、最短路径问题、图论和二次规划等。 1. 线性规划的求解： 在线性规划问题中，目标是最大化或最小化某个线性函数，同时满足一系列线性不等式或等式的约束。题目给出了一个具体的线性规划问题，并要求求解最优解。通过转化为标准形式并运用单纯形法，我们可以找到问题的最优解。例如，在给定的问题中，经过单纯形法迭代，最终得到了最优解（0，100，0，200）。 2. 对偶问题： 对偶问题是原线性规划问题的另一种形式，具有等价的最优解。题目要求求解对偶问题的最优解。通过互补松弛性，可以由原问题的最优解推导出对偶问题的最优解。在本例中，对偶问题的最优解为（0，1/4，1）。 3. 灵敏度分析： 这部分考察了参数变化对最优解的影响。当某个约束的右端常数（如b）发生变化时，我们需判断最优基是否改变。题目中，当b=3150时，最优基发生了变化，因为新的约束不满足最优解的可行性。 4. 单纯形法： 单纯形法是一种解决线性规划的有效算法，题目要求在模型中添加变量并分析对偶问题的可行域变化。添加变量可能导致原问题的可行域扩大，但不会影响对偶问题的可行域。 5. 最短路径问题： 题目要求求解V1到各点的最短路径，这是图论中的经典问题。可以通过Dijkstra算法或Floyd-Warshall算法来解决。 6. 图的性质： 在有向图中，若每个节点有且仅有一条进入的边和一条离开的边，那么该图一定存在环。题目要求证明任意n个节点n条边的简单图中必存在环，这是图的连通性理论的一部分。 7. 网络流问题： 网络流问题涉及到如何在一个带权重的有向图中找到最大流量。题目要求找出所有截集以及最小截集的容量，并证明给出的流是最大流。这通常可以通过Ford-Fulkerson算法或Edmonds-Karp算法解决。 8. 二次规划： 二次规划是优化问题的一种，目标函数是二次函数，且受到线性约束。题目给出一个具体的二次规划问题，并要求求解。这类问题可以通过拉格朗日乘数法或内点法解决。 通过以上分析，我们可以看出运筹学涉及了广泛的概念和方法，包括线性规划、对偶理论、灵敏度分析、图论、网络流和二次规划等，这些都是运筹学在实际问题求解中不可或缺的工具。