透镜生产利润优化的线性规划构建求解及资源调整可行性问询
Hey 伙计，咱们先把这个生产优化问题的来龙去脉理清楚：
有一家公司专门生产A、B、C三种透镜，生产流程分三道核心工序：
- 透镜成型：把熔融玻璃加工成毛坯透镜
- 检测：一套复杂的系统，用来测定透镜的属性并分类分级
- 精加工：通过自动化流程对透镜进行切割和抛光
公司的工业工程部门把生产流程摸得门儿清后，制定了对应的生产标准（原本的图片里包含了每种透镜在三道工序的工时消耗、单位利润，以及各工序每小时的可用工时这些关键数据）。老板现在想搞明白，每小时该生产多少个每种透镜，才能让每天8小时的利润达到最大。
接下来咱们分两个问题来拆解：
a) 线性规划问题的构建与单纯形法求解
第一步：定义决策变量
咱们设每小时生产A、B、C三种透镜的数量分别为 x₁、x₂、x₃，而且这些变量肯定是非负的（总不能生产负数个透镜对吧）。
第二步：建立目标函数
假设从生产标准里能拿到每种透镜的单位利润：A是p₁，B是p₂，C是p₃。因为每天工作8小时，所以咱们要最大化的总利润就是：Max Z = 8*(p₁x₁ + p₂x₂ + p₃x₃)
（其实也可以先算每小时的最大利润，最后乘以8就行，本质是一样的）
第三步：列约束条件
还是从生产标准里取数据：
- 设成型、检测、精加工每小时的可用工时分别是
t₁、t₂、t₃ - A透镜在成型、检测、精加工的工时消耗分别是
a₁、b₁、c₁；B是a₂、b₂、c₂；C是a₃、b₃、c₃
那约束条件就出来了：
- 成型工序的工时不能超：
a₁x₁ + a₂x₂ + a₃x₃ ≤ t₁ - 检测工序的工时不能超：
b₁x₁ + b₂x₂ + b₃x₃ ≤ t₂ - 精加工工序的工时不能超：
c₁x₁ + c₂x₂ + c₃x₃ ≤ t₃ - 非负约束：
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
第四步：用单纯形法求解的步骤
先把不等式约束转成等式，引入松弛变量
s₁、s₂、s₃（分别对应三道工序没用到的闲置工时），得到标准型：
目标函数：Max Z = 8p₁x₁ + 8p₂x₂ + 8p₃x₃ + 0s₁ + 0s₂ + 0s₃
约束等式：a₁x₁ + a₂x₂ + a₃x₃ + s₁ = t₁b₁x₁ + b₂x₂ + b₃x₃ + s₂ = t₂c₁x₁ + c₂x₂ + c₃x₃ + s₃ = t₃
所有变量都非负：x₁,x₂,x₃,s₁,s₂,s₃ ≥ 0构造初始单纯形表，把松弛变量当基变量，计算每个非基变量的检验数。
看看检验数：如果所有检验数都≤0，那当前的解就是最优解；要是有正的检验数，就挑最大的那个对应的变量当进基变量，再用最小比值法找出基变量。
对单纯形表做初等行变换，更新基变量和所有系数。
重复步骤3和4，直到所有检验数都≤0，这时候得到的
x₁*、x₂*、x₃*就是每小时最优生产数量，代入目标函数就能算出最大日利润Z*。
举个简单的例子（假设生产标准数据是：A单位利润5元，成型0.2小时、检测0.1小时、精加工0.3小时；B单位利润4元，成型0.1小时、检测0.2小时、精加工0.2小时；C单位利润6元，成型0.3小时、检测0.1小时、精加工0.1小时；每小时各工序可用工时都是1小时），套上面的步骤就能算出最优解啦。
b) 成型与精加工工时的最大可削减量（不改变可行性）
这个问题得用到线性规划的敏感性分析和对偶理论，核心思路是：咱们要找的是，削减工时后，原来的最优解仍然满足所有约束条件，也就是可行域还包含原来的最优顶点。
具体来说：
- 先看成型工序对应的松弛变量
s₁：如果在最优解里s₁ > 0，说明这个工序本来就有闲置工时，那最多可以把闲置的这部分工时全砍掉（也就是削减s₁的量），砍完之后约束还是满足的，可行性不受影响；如果s₁ = 0，说明这个工序的工时全用完了，这时候就得算约束右端项的允许减少范围——这个范围可以通过单纯形表的右端项和系数算出来，在这个范围内削减工时，原来的基变量还是非负的，可行性不变。 - 精加工工序的逻辑和成型完全一样：看松弛变量
s₃的值，有闲置就砍闲置量，没闲置就算允许减少的范围。
总结一下：有闲置工时的工序，最大可削减量就是闲置工时；无闲置的，得靠敏感性分析算右端项的允许减少上限，这个上限就是最大可削减量，超了的话原来的最优解就不可行了，得重新规划。
备注：内容来源于stack exchange，提问作者isa.be
