运筹学考试详解：线性规划与整数规划

"中南大学2020-2021学年第一学期运筹学考试试题，涉及线性规划的标准化、对偶问题的经济解释以及分枝定界法在解决线性整数规划问题中的应用。考试形式为开卷，面向自动化、测控19级学生。" 线性规划是运筹学中的基础工具，用于优化一组线性目标函数和线性约束条件的问题。标题中的第一个知识点是将非标准形式的线性规划转化为标准形式。标准形式要求决策变量为非负，所有的约束条件都是等式或不等式，并且目标函数可以是最大化或最小化。在这个过程中，可能会引入松弛变量、对偶变量和人工变量来实现转化。 线性规划的对偶问题是对原问题的另一种表示，它提供了一种不同的视角来理解问题。描述中的第二点提到，如果原问题是资源约束下的利润最大化问题，对偶问题则是对资源进行定价，以找到与最优生产计划一致的最低总成本。对偶问题中的影子价格代表了资源的边际效用，即增加单位资源带来的额外利润。 分枝定界法是求解线性整数规划问题的有效算法。它通过将连续的松弛问题与整数约束相结合，逐步缩小最优解的搜索范围。第一步，解决松弛问题以获取初步的下界；第二步，通过找到可行解设定下界，并更新上界；第三步，针对不满足整数要求的变量进行分支，创建新的子问题。这个过程不断迭代，直到找到全局最优解或确定无解。 在实际应用中，线性规划和它的对偶问题、分枝定界法广泛应用于生产计划、运输问题、库存管理等多个领域，通过优化决策，提高效率，降低成本。对于学习运筹学的学生来说，理解和掌握这些概念是至关重要的，因为它们是解决实际问题的基础工具。