简单线性规划问题复习公开

简单线性规划问题复习公开课运筹学基础·数学优化方法系统梳理与典型题型精讲Contents课程目录从基础概念到实战应用，系统掌握完整知识脉络。01基础概念回顾02数学模型建立03求解方法体系04实际应用案例05典型题型精练CHAPTER01基础概念回顾从定义、三要素到解的分类，夯实线性规划的理论根基OperationsResearch什么是线性规划线性规划是运筹学中研究线性约束条件下线性目标函数极值问题的数学方法，其核心是在有限资源约束下寻找最优决策方案，广泛应用于经济管理、交通运输、工农业生产等领域。01运筹学最成熟的分支研究在线性约束条件下求线性目标函数最大值或最小值的问题，理论体系完整且应用最为广泛。02科学决策，告别拍脑袋合理利用有限的人力、物力、财力等资源，为最优决策提供科学依据，而非凭经验主观判断。03广泛的应用场景涵盖生产计划安排、运输路径优化、投资组合选择、人员调度等，几乎所有涉及资源分配的问题均可建模求解。04不增投入，提升产出提高经济效果的两大途径中，线性规划属于"生产组织与计划改进"方向——不增加投入也能提升效率。LINEARPROGRAMMING·优化建模线性规划的三要素决策变量、目标函数与约束条件构成线性规划模型的三大核心要素，三者共同定义了优化问题的求解空间与优化方向，是建模与求解的基础框架。决策变量模型中需要求解的未知量，代表问题的决策方案，通常用x₁、x₂等表示且一般要求非负。一组变量的取值对应一种可行方案，变量个数决定了问题的维度和求解复杂度。x₁,x₂,…xₙ目标函数决策变量的线性表达式，表示需要最大化（如利润）或最小化（如成本）的量化目标。形式为z=c₁x₁+c₂x₂+…+cₙxₙ，系数c反映各变量对目标的贡献权重。max/minz约束条件线性等式或不等式表示现实中对决策变量的限制，如资源上限、需求下限、技术条件等。所有约束条件的交集构成可行域，只有在可行域内的解才是有意义的方案。可行域LINEARPROGRAMMING·FUNDAMENTALS线性规划问题的基本特点线性规划问题具有比例性、可加性、连续性和确定性四大特征，这些特征决定了问题的线性本质，也是判断一个问题能否用线性规划方法求解的关键依据。比例性目标函数与约束条件中每个变量的贡献与其取值严格成正比，不存在x²、x₁x₂等非线性项PROPORTIONALITY可加性各决策变量对目标函数和约束条件的贡献相互独立、可以线性叠加，变量间不存在交互效应ADDITIVITY连续性决策变量可以在某一范围内取任意实数值（包括小数），而非仅限于整数解CONTINUITY确定性模型中所有参数（目标系数、约束系数、右端常数）都是已知的确定常数，不含随机变量CERTAINTYLinearProgramming·解体系解的概念辨析可行解、基本可行解与最优解构成线性规划的解体系。核心定理指出：若最优解存在，则必可在可行域的某个顶点（基本可行解）处达到，这一性质是单纯形法的理论基础。可行解与可行域满足所有约束条件的解称为可行解，全部可行解的集合构成可行域，且可行域一定是凸集。可行域可以是有界的多边形区域，也可以是无界的，甚至可能为空集。凸集基本可行解在可行解中，满足约束方程组中等式个数等于决策变量个数的解称为基本可行解。几何意义：基本可行解对应可行域的顶点，是单纯形法只在顶点间搜索的理论依据。顶点最优解在所有可行解中使目标函数取得最大值或最小值的解称为最优解。最优解可能唯一、可能无穷多（目标函数等值线与某条边界平行时），也可能不存在。目标函数LinearProgramming线性规划问题的四种解的情况线性规划问题可能存在唯一最优解、无穷多最优解、无界解或无可行解四种情况，每种情况都有明确的几何特征和代数判别条件。唯一最优解目标函数等值线在可行域某一顶点处达到极值，该顶点是唯一使目标取最优值的点顶点极值无穷多最优解目标函数等值线与可行域某条边界线平行，该边界上的所有点均为最优解边界平行无界解可行域在目标函数优化方向上无界延伸，目标值可无限增大或减小，不存在有限最优解无界延伸无可行解约束条件相互矛盾导致可行域为空集，没有任何解能同时满足所有约束条件空集矛盾线性规划四种解情况的几何示意图CHAPTER02数学模型建立从实际问题到数学表达的转化路径与建模方法论LINEARPROGRAMMING线性规划建模三步骤线性规划建模遵循"定义决策变量→建立目标函数→设定约束条件"的标准流程，将实际问题中的决策、目标和限制系统性地转化为数学语言，是求解的前提。01定义决策变量识别问题中需要决策的未知量，用字母（如x₁、x₂）表示，并明确每个变量的实际含义注意变量通常要求非负（x≥0），某些问题还可能有整数约束或其他特殊限制x₁,x₂02建立目标函数确定优化方向（最大化利润/最小化成本），将目标用决策变量的线性表达式表示系数c₁、c₂代表单位决策变量对目标的贡献，需从题目条件中准确提取z=c₁x₁+c₂x₂03设定约束条件逐一梳理资源限制、需求限制、技术条件等，用线性不等式或等式表达为约束方程组常见约束类型包括：资源上限（≤）、需求下限（≥）、平衡条件（=）、非负约束≤≥=LinearProgramming建模实例：生产计划问题生产计划问题是线性规划建模的典型场景，通过将产品产量设为决策变量、利润设为目标函数、资源限制设为约束条件，完整演示了从实际问题到数学模型的转化过程。01问题背景工厂生产A、B两种产品，受工时和原料两种资源限制，目标是安排产量使总利润最大化📦双产品⏱️工时约束🧪原料约束02决策变量设x₁为产品A的日产量（吨），x₂为产品B的日产量（吨），均要求非负x₁≥0x₂≥003目标函数maxz=5x₁+4x₂，其中5和4分别是A、B产品每吨的利润（万元）5万元/吨4万元/吨04约束条件2x₁+4x₂≤12（工时），3x₁+x₂≤10（原料），x₁,x₂≥0≤12h≤10tLINEARPROGRAMMING标准形式与非标准形式线性规划的标准形式要求目标最大化、约束为等式、右端非负、变量非负，是单纯形法的计算基础。非标准形式可通过引入松弛变量、取负号等方法等价转换为标准形式。标准形式的四个要求01目标函数必须是求最大值（max），若原问题为min可令z'=-z转化为max02所有约束条件必须为等式形式，不等式需通过引入松弛变量或剩余变量转为等式03约束右端常数必须非负（b≥0），否则两端乘以-1并改变不等号方向04所有决策变量必须非负（x≥0），自由变量可通过变量替换处理常用的转换技巧01≤约束加松弛变量：如x₁+x₂≤6变为x₁+x₂+s₁=6，其中s₁≥0为松弛变量02≥约束减剩余变量：如x₁+x₂≥4变为x₁+x₂-s₂=4，其中s₂≥0为剩余变量03等式或≥约束需加人工变量以构造初始基本可行解，这是两阶段法和大M法的基础CHAPTER03求解方法体系从图解法的几何直觉到单纯形法的系统计算，掌握两大核心求解工具LINEARPROGRAMMING几何解法（图解法）的基本步骤图解法通过在二维坐标系中绘制约束半平面确定可行域，再利用目标函数等值线的平移找到最优解，虽仅限二维问题，但为理解线性规划的本质提供了不可替代的几何直觉。01画出约束区域—将每个不等式约束在x₁-x₂坐标系中表示为半平面，所有半平面的交集即为可行域02确定可行域形状—可行域是凸多边形（有界）或凸无界区域，其顶点由约束直线的交点决定03画目标函数等值线—令z取某一常数值，画出直线c₁x₁+c₂x₂=z，这是一组互相平行的直线04平移寻找最优解—沿z增大（max问题）方向平移等值线，最后离开可行域的点即为最优解所在位置05计算最优值—求出最优解所在顶点的坐标（联立两条约束直线方程），代入目标函数得最优值LinearProgramming图解法完整演示通过生产计划实例完整演示图解法的操作流程：从绘制可行域到平移等值线，最终在顶点(2,2)处找到最优解，最大利润为18万元，验证了"最优解在顶点取到"的核心定理。Step01绘制可行域：由2x₁+4x₂≤12、3x₁+x₂≤10、x₁≥0、x₂≥0围成的凸四边形区域Step02求各顶点坐标：联立相邻约束方程得四个顶点为(0,0)、(10/3,0)、(2,2)、(0,3)Step03等值线平移：目标函数z=5x₁+4x₂沿增大方向（右上方）平移，最后离开可行域的顶点为(2,2)Optimal最优解：x₁=2吨，x₂=2吨，最大利润z=5×2+4×2=18万元可行域与等值线z=5x₁+4x₂在顶点(2,2)取最大值18LINEARPROGRAMMING单纯形法的基本思想单纯形法基于"最优解必在顶点取到"的定理，从初始基本可行解出发，沿可行域边界逐次移动到目标函数更优的相邻顶点，直至找到最优解，是求解线性规划问题的通用算法。01理论基础若线性规划存在最优解，则至少有一个基本可行解（可行域顶点）是最优解02搜索策略从某个初始基本可行解出发，检验当前解是否最优，若不是则移动到相邻的更优顶点03迭代方向每次移动选择一个能使目标函数值增大的非基变量入基，同时选择一个基变量出基04终止条件当所有非基变量的检验数均≤0时，当前基本可行解即为最优解，算法终止LINEARPROGRAMMING单纯形法的计算步骤单纯形法通过"标准化→建表→检验→旋转"的迭代流程逐步逼近最优解，每轮迭代包含最优性检验、入基出基选择和旋转运算三个核心操作，直至所有检验数非正时收敛。化为标准形式确保目标函数为最大化形式，约束条件转化为等式，右端常数保持非负，所有决策变量满足非负约束。必要时引入松弛变量和人工变量构造初始可行基。标准化建立初始表以松弛变量或人工变量作为初始基变量，在单纯形表中填入约束系数矩阵、右端常数向量，以及目标函数的价值系数和初始检验数。建表最优性检验计算各非基变量的检验数σⱼ=cⱼ−zⱼ。若所有检验数均小于等于零，则当前基可行解即为最优解，算法终止；否则选择最大正检验数对应的变量入基。σⱼ≤0最小比值规则对入基列中所有正系数元素，计算比值θᵢ=bᵢ/aᵢₖ。选取最小比值对应的基变量作为出基变量，确保迭代后新解仍满足非负约束，保持解的可行性。minθᵢ旋转运算以交叉元素为主元进行高斯消元运算，将主元化为1，同列其他元素化为0，更新整张单纯形表。完成换基后返回最优性检验步骤，开始下一轮迭代。PIVOTOPTIMALITYCRITERIA检验数与最优性判别检验数σⱼ=cⱼ-zⱼ衡量非基变量入基对目标函数的边际贡献，通过分析检验数的正负与对应列系数的关系，可判别当前解是否为最优解以及解的类型。01所有检验数σⱼ≤0：当前基本可行解为最优解，算法终止，无需继续迭代OPTIMAL02所有σⱼ<0（严格小于零）：最优解唯一，不存在其他使目标函数取相同最优值的可行解UNIQUE03某个非基变量σⱼ=0：存在无穷多最优解，该变量入基后目标值不变，可得另一个最优基本可行解INFINITE04某个σⱼ>0且该列所有系数aᵢⱼ≤0：问题为无界解，目标函数可无限增大，不存在有限最优值UNBOUNDEDLINEARPROGRAMMING两阶段法与大M法当标准形式需要引入人工变量时，两阶段法和大M法是两种消除人工变量影响的经典策略，前者分两步确保可行性，后者通过惩罚系数一步到位。01两阶段法①第一阶段：以最小化人工变量之和为目标函数，用单纯形法求解。若最优值为0，则原问题存在可行解，可进入第二阶段；若最优值不为0，则原问题无可行解。②第二阶段：去掉人工变量，以第一阶段得到的基本可行解作为初始解，恢复原目标函数继续求解，直至获得最优解。特点：分步求解，逻辑清晰，计算过程稳定可靠分步求解02大M法①惩罚机制：在目标函数中给人工变量赋予极大的惩罚系数−M（最大化问题），迫使迭代过程中人工变量尽快出基，从而不影响最终最优解。②单次迭代：只需一遍单纯形法迭代即可完成求解，但M需足够大且具体数值选取有时会影响计算稳定性，需谨慎处理。特点：一步到位，迭代次数少，但需注意数值稳定性一步到位CHAPTER04实际应用案例从生产管理到资源配置，线性规划在真实决策场景中的应用实践CaseStudy·线性规划应用案例一：资源分配问题资源分配问题是线性规划最典型的应用场景，核心是将有限资源（原料、工时等）在多种产品间最优分配，通过建模求解可得到利润最大化的生产方案。01问题特征多种产品共享有限的几种资源，每种产品的资源消耗率和单位利润已知，求最优产量组合。Multi-Product·LimitedResources02建模要点每种产品对应一个决策变量，每种资源对应一个≤约束，目标函数为各产品利润之和。Variables·Constraints·Objective03关键技巧从题目表格中准确提取消耗系数矩阵，行代表资源种类，列代表产品类型。CoefficientMatrix04实际意义帮助企业在不增加资源投入的前提下，通过优化产品组合实现利润最大化。ProfitMaximizationLINEARPROGRAMMING应用案例二：运输问题运输问题是线性规划在物流领域的经典应用，通过优化多产地到多销地的运量分配，在满足供需平衡的前提下实现运输总成本最小化。01STRUCTURE问题结构m个产地（供应量aᵢ已知）、n个销地（需求量bⱼ已知），决策变量xᵢⱼ为产地i到销地j的运量。m×n02CONSTRAINTS约束条件每个产地发出货量等于供应量（Σxᵢⱼ=aᵢ），每个销地收到量等于需求量（Σxᵢⱼ=bⱼ）。Σxᵢⱼ=aᵢ=bⱼ03OBJECTIVE目标函数minz=ΣΣcᵢⱼxᵢⱼ，其中cᵢⱼ为从产地i到销地j的单位运输费用。minΣΣcᵢⱼxᵢⱼ04METHOD特殊解法供需平衡（Σaᵢ=Σbⱼ）时可用表上作业法——最小元素法配合闭回路调整——高效求解。表上作业法APPLICATIONCASES应用案例三：投资与配料问题线性规划的应用横跨多个领域——从资产配置的投资组合优化到工业生产中的成本最低配料方案，不同场景共享"约束下求最优"的统一建模框架。投资组合优化决策变量：各资产的投资比例或金额目标函数为预期收益最大化或风险最小化，需平衡收益与波动约束条件：总投资额上限、单一资产比例限制最低收益要求、风险承受阈值、流动性约束等风控指标核心目标收益最大化配料与混合问题决策变量：各原料的使用量配比目标函数为配料总成本最小化，广泛应用于食品加工、化工、冶金等行业约束条件：成品成分含量上下限要求原料供应量限制、品质标准、工艺配比等技术规范约束核心目标成本最小化DUALITYTHEORY拓展：对偶理论简介每个线性规划问题都有对应的对偶问题，二者通过强弱对偶性定理紧密关联。对偶变量的值即为资源的"影子价格"，反映了资源对目标函数的边际贡献价值。原问题与对偶问题原问题与对偶问题互相对应：max对偶为min，≤约束对偶为≥约束，系数矩阵互为转置。这种对称结构使得两个问题在数学上形成完美的对偶关系，便于从不同角度分析优化问题。互为转置弱对偶性原问题可行解的目标值始终不超过对偶问题可行解的目标值，为最优值提供上下界。这一性质可用于判断解的优劣程度，也是分支定界等算法的重要理论基础。上下界强对偶性若原问题有最优解，则对偶问题也有最优解，且二者最优目标函数值相等。强对偶性是线性规划理论的核心结果，保证了原问题与对偶问题的等价性，极大简化了求解过程。最优值相等影子价格对偶变量的最优值反映每增加一单位资源所能带来的目标函数增量，指导资源采购决策。影子价格揭示了稀缺资源的内在经济价值，是企业资源配置和成本控制的关键参考指标。边际贡献CHAPTER05典型题型精练覆盖图解法、单纯形法与建模应用三大高频考点的实战演练线性规划·典型题典型题一：图解法求最大值图解法求最大值是考试中最基础的题型，核心考查学生在坐标系中绘制可行域、求解顶点坐标、代入目标函数比较的能力，解题关键在于准确找到所有约束直线的交点。01题目条件maxz=3x₁+5x₂，s.t.x₁≤4，2x₂≤12，3x₁+5x₂≤15，x₁≥0，x₂≥002画可行域由五条约束线在第一象限围成凸多边形，需逐一求出各约束直线的交点坐标03代入顶点求最优比较所有顶点处的目标函数值，取最大者对应顶点即为最优解04易错提醒注意区分约束直线交点中哪些在可行域内、哪些不在，只有可行域顶点才需代入比较典型题图解法求最小值求最小值问题的可行域常为无界区域，但只要目标函数在减小方向上有约束边界"兜底"，仍可得到有限最优解，关键在于正确判断等值线的平移方向与可行域的关系。01题目设定minz=2x₁+3x₂，s.t.x₁+x₂≥4，x₁+2x₂≥6，x₁≥0，x₂≥0minz02可行域特征所有约束为≥型，可行域向右上方无界延伸，顶点由约束直线交点决定≥型03求最优解目标函数等值线沿减小方向（左下方）平移，最后离开可行域的点为最优解所在顶点←平移04重要辨析无界可行域≠无界解，本题在min方向上有约束兜底，故存在有限最优解有界解线性规划·核心题型典型题三：单纯形法计算单纯形法计算题是考试中的高分值题型，要求学生完整展示标准化、建表、迭代和最优性判别的全过程，计算的准确性和规范性是得分的关键。1化标准形式引入松弛变量s₁、s₂、s₃将三个≤约束转为等式，目标函数保持不变。maxZ=3x₁+2x₂+0s₁+0s₂+0s₃2建立初始表基变量为s₁、s₂、s₃，填入约束系数矩阵、右端常数和检验数行。Cj-