线性规划法模拟器 返回
数学与统计

线性规划法(图形解法)模拟器

2变量LP问题的可行域、最优顶点、目标函数等高线实时绘制。单纯形法逐步演示及灵敏度分析可视化。

问题设置
预设问题
目标函数斜率 θ 45°
动画速度 1.0×
计算结果
最优 x₁*
最优 x₂*
目标值 Z*
紧约束数
线性规划求解(图形法)
理论与主要公式

标准形式:$\text{max}\; \mathbf{c}^\top\mathbf{x}$ s.t. $A\mathbf{x}\leq \mathbf{b}$,$\mathbf{x}\geq 0$

最优解位于可行域的某个顶点(基可行解)。

单纯形法:通过移动相邻顶点来改进目标值。

影子价格(对偶变量)$\lambda_i = \partial Z^* / \partial b_i$

线性规划法(图形解法)概述

🙋
我听说线性规划法可以用图形来解,这是怎么回事?
🎓
简单说,当你要制定某个生产计划,比如生产两种产品来最大化利润时,就可以用这个方法。首先,从约束条件的直线开始,围成一个封闭的多边形区域(可行域),这就是所有满足约束的方案。然后,通过改变上面滑块中的目标函数系数c₁和c₂,你可以看到代表利润的直线如何移动,最后接触可行域边界的点就是最优解。
🙋
那为什么最优解总是在多边形的顶点(角点)呢?
🎓
这是个很好的观察!当你逐步改变目标函数直线的位置来找最大值时,首先触及可行域的地方可能在边上或角上。但数学上已经证明,即使这个点在某条边的中间,该边两端的顶点中至少有一个目标函数值相同或更优。所以检查所有顶点就足够了。这也是单纯形法的基础——它逐个检查顶点来找到最优解。
🙋
那单纯形法在这个图上是怎样工作的呢?我能在模拟器上看到吗?
🎓
可以的!单纯形法的原理是从当前顶点出发,选择能最大化改进目标函数的相邻顶点,然后跳过去。模拟器的"逐步演示"功能可以让你看到求解过程中从一个顶点跳到另一个顶点的过程。在实际应用中,当变量有几百个时就无法画图了,但"探索顶点"的思想完全相同,这就是单纯形法的精髓。

常见问题

这说明你添加的新约束与现有约束产生了矛盾。比如,x1 + x2 ≤ 5 和 x1 + x2 ≥ 10 同时存在,就没有任何解能同时满足两个条件。仔细检查每个约束的系数和右侧值,确保它们在逻辑上是兼容的。
当目标函数的等高线与可行域的某条边平行时,该边上的所有点都是最优解。这叫"替代最优解",发生在系数c1、c2的比例恰好等于某个约束斜率的情况下。你可以在灵敏度分析中查看这种情况的影响。
这可能是非有界问题(目标值可以无限增长)或无可行解。检查图表:可行域是否是闭合的多边形?所有变量是否都满足非负约束?如果可行域是开放的,就需要添加额外的约束来闭合它。
这表示在现有最优顶点保持不变的前提下,目标函数系数或约束右侧值可以变化的范围。比如,如果c1的许可增加为2,那么c1可以增加最多2个单位,超过这个范围,最优解就会跳到另一个顶点。

现实应用

生产计划和资源分配:在有限的机器运行时间、原材料和人力的约束下,决定生产多少个不同产品才能最大化总利润。这正是本模拟器的核心模型。感度分析(RHS范围)在现场非常常用——例如,"如果我们再多买一些原料,利润会增加多少?"

物流和运输问题:从多个工厂向多个仓库运输产品,在满足供应能力和需求的前提下最小化运输成本。变量是运输量,约束是工厂的供应能力和仓库的需求。这是线性规划的经典应用。

CAE中的结构优化:在满足应力和变位约束的前提下最小化结构重量的"拓扑优化"初期阶段,或其线性近似模型会使用线性规划。关于材料存在与否的决策(0/1问题)属于整数规划,其放松问题用线性规划求解。

项目排程:在人员和设备等资源约束下,通过优化各工序的时间来缩短总工期。关键路径法(CPM)的资源约束版本等都会用到这种方法。

常见误解和注意要点

在开始使用本模拟器时,特别是在考虑实际应用的情况下,有几个需要特别注意的要点。首先,理解"图形解法只对2个变量有效"这一根本性局限。只要产品是两种(A和B),就可以画出图形;但实际生产通常有C、D等多种产品。此时需要采用单纯形法等数值方法,而你在本工具中学到的"探索顶点"概念正是这些算法的理论基础。

其次,注意约束条件设置中的现实性遗漏。比如,"机器运行时间 x₁ + 2x₂ ≤ 8(小时)"看似简单,但实际还要考虑设备调试时间和维护时间,连续运行的假设在现实中很少成立。系数(比如单位利润c₁)也会因原材料价格波动而变化。这正是工具提供的灵敏度分析功能的用武之地——通过检查"这个系数变化多少会导致最优解改变",培养对参数敏感性的认识。

最后,不要忽视"非负"以外的约束。工具的标准形式假设变量都是非负的,但现实问题中经常出现"产品A至少要生产100件"(x₁ ≥ 100)或"库存要恰好清空"(等式约束)。这些约束需要进行变量替换(如令x₁' = x₁ - 100,使得x₁' ≥ 0)后才能输入工具求解。

使用指南

  1. 用滑块设置目标函数的系数c1、c2(例如最大化利润时,c1和c2分别是产品A和产品B的单位利润)
  2. 在图表上绘制约束条件(资源限制、生产能力等),并确认可行域
  3. 通过移动等高线找到最优顶点,并用单纯形法的逐步演示追踪收敛过程

具体计算示例

电子零件制造商生产产品X(利润2.5万元/台)和产品Y(利润1.8万元/台)。在月产能400台、部件采购限制600个的约束下:设置c1=2.5、c2=1.8,得到最优解x₁*=200台、x₂*=200台、Z*=880万元。通过灵敏度分析可检验系数变化±15%时解的稳健性。

实际应用要点