线性规划上课课件

线性规划概述线性规划是运筹学中的重要分支，用于解决资源优化配置问题。本课程将深入探讨线性规划的基本概念、求解方法及应用。线性规划的概念定义线性规划是在线性约束条件下，求解线性目标函数最优值的数学方法。特点包括决策变量、目标函数和约束条件，所有关系都是线性的。目的在满足所有约束条件的前提下，找到使目标函数达到最大或最小值的解。线性规划的应用领域生产计划优化产品组合，最大化利润。物流运输最小化运输成本，优化路径选择。投资组合在风险约束下，最大化投资回报。资源分配合理分配有限资源，提高使用效率。线性规划的基本假设比例性决策变量与其贡献成正比。可加性总贡献等于各变量贡献之和。确定性所有参数都是已知且固定的。连续性决策变量可取任意非负实数。线性规划的标准形式目标函数最大化或最小化线性函数：Z=c1x1+c2x2+...+cnxn约束条件m个线性不等式或等式：a11x1+a12x2+...+a1nxn≤b1非负约束所有决策变量非负：x1≥0,x2≥0,...,xn≥0线性规划的几何解释1可行域满足所有约束条件的点集。2边界可行域的边界线或面。3极点可行域的顶点，常包含最优解。4等值线目标函数值相等的点构成的直线。图解法求解线性规划绘制约束条件在坐标系中画出约束直线。确定可行域找出满足所有约束的区域。绘制目标函数等值线画出目标函数的等值线。找出最优解移动等值线，找到最优点。图解法的局限性1维度限制仅适用于两个决策变量的问题。2精确度问题图形解读可能存在误差。3复杂性约束条件过多时，图形变得复杂难辨。4效率低下对于大规模问题，求解速度慢。单纯形法求解线性规划1代数方法2迭代优化3基本可行解4最优解单纯形法是一种代数方法，通过迭代优化基本可行解，最终达到最优解。单纯形法的基本思想初始基本可行解从可行域的一个顶点开始。移动方向选择能改善目标函数值的方向。迭代过程不断移动到相邻的更优顶点。终止条件当无法找到更优解时停止。单纯形表的构建基变量x1x2s1s2bs1a11a1210b1s2a21a2201b2Z-c1-c2000单纯形表的行变换选择入基变量检查Z行，选择最负的系数对应的变量。确定出基变量计算最小比值，确定离基变量。主元素确定主元素所在行列。高斯-约当消元对单纯形表进行行变换。单纯形法的解法步骤1构建初始单纯形表将线性规划问题转化为标准形式。2判断最优性检查Z行是否存在负系数。3选择入基和出基变量确定旋转元素。4更新单纯形表进行高斯-约当消元。5重复迭代重复步骤2-4直到达到最优解。单纯形法的终止条件最优解Z行所有系数非负，表示达到最优解。无界解入基列全为非正，目标函数无上界。循环解在有限个基本可行解间循环。多重最优解Z行存在零系数，表示有多个最优解。双重单纯形法适用情况初始解不可行但目标行系数非负时使用。基本思想从不可行解开始，通过迭代使解可行并最优。优势对某些问题比普通单纯形法更高效。大M法和两阶段法大M法引入人工变量并赋予极大惩罚系数M。两阶段法第一阶段消除人工变量，第二阶段求解原问题。适用情况处理初始基本可行解不易获得的问题。选择根据问题特点和计算效率选择合适方法。灵敏度分析1参数变化2影响评估3稳定性分析4决策支持灵敏度分析研究参数变化对最优解的影响，为决策提供重要支持。灵敏度分析的概念定义研究线性规划参数变化对最优解的影响。目的评估解的稳定性和模型的适应性。方法分析目标系数、约束右端和技术系数的变化。意义为决策者提供更全面的信息支持。基变量敏感性分析允许区间基变量系数变化不改变最优基的范围。影响分析基变量系数变化对最优解的影响。计算方法利用最终单纯形表计算允许区间。右端常数敏感性分析1定义分析约束条件右端常数变化对最优解的影响。2影子价格右端常数变化一个单位引起的目标函数值变化。3计算利用对偶单纯形法或最终单纯形表进行分析。4应用评估资源增减对总体效益的影响。目标函数系数敏感性分析范围确定确定目标函数系数的允许变化范围。平衡点分析系数变化导致最优解改变的临界点。趋势分析研究系数变化对最优解的影响趋势。决策支持为产品定价和资源配置提供决策依据。整数规划概述定义要求部分或全部决策变量为整数的线性规划。分类纯整数规划、混合整数规划和0-1整数规划。特点解空间离散，求解复杂度高。意义更贴近现实中的离散决策问题。整数规划的应用领域整数规划广泛应用于生产计划、运输调度、库存管理、项目规划和投资决策等领域。整数规划求解方法1枚举法2分支定界法3割平面法4隐枚举法5启发式算法整数规划的求解方法从简单到复杂，适用于不同规模和特点的问题。枚举法原理遍历所有可能的整数解，找出最优解。优点简单直观，保证找到全局最优解。缺点计算量大，仅适用于小规模问题。改进可结合其他方法进行剪枝，提高效率。分支定界法松弛问题求解线性规划松弛问题。分支选择非整数变量进行分支。定界计算各子问题的界限。剪枝剪去不可能包含最优解的分支。切平面法基本思想通过添加切平面约束，逐步逼近整数解。Gomory割最常用的切平面生成方法。优缺点理