基于线性规划的“最优生产计划”建模与求解示例
字数 5663 2025-12-19 00:41:26
基于线性规划的“最优生产计划”建模与求解示例
1. 题目描述
假设一家工厂生产两种产品A和B。
- 生产每单位A产品需要消耗2小时的机器工时、1小时的人工工时，并产生3千克的排放物。
- 生产每单位B产品需要消耗1小时的机器工时、3小时的人工工时，并产生2千克的排放物。
- 工厂每天可用资源上限为：
- 机器工时：100小时
- 人工工时：90小时
- 排放物允许总量：120千克（环保限制）
- 每单位A产品的利润为40元，每单位B产品的利润为50元。
目标：在资源限制下，确定每天生产A和B的数量（可不为整数），以最大化总利润。
2. 建立线性规划模型
设 \(x_1\) = 产品A的日产量，\(x_2\) = 产品B的日产量。
目标函数（最大化利润）：
\[\max \quad Z = 40x_1 + 50x_2
\]
约束条件：
- 机器工时限制：\(2x_1 + x_2 \leq 100\)
- 人工工时限制：\(x_1 + 3x_2 \leq 90\)
- 排放物限制：\(3x_1 + 2x_2 \leq 120\)
- 非负约束：\(x_1 \geq 0, x_2 \geq 0\)
3. 图解法（直观理解）
由于只有两个变量，可在平面直角坐标系中画出约束区域：
- 约束1：\(2x_1 + x_2 \leq 100\)
边界直线：\(2x_1 + x_2 = 100\)，过点 (0,100) 和 (50,0)。
- 约束2：\(x_1 + 3x_2 \leq 90\)
边界直线：\(x_1 + 3x_2 = 90\)，过点 (0,30) 和 (90,0)。
- 约束3：\(3x_1 + 2x_2 \leq 120\)
边界直线：\(3x_1 + 2x_2 = 120\)，过点 (0,60) 和 (40,0)。
可行域：
上述三个不等式与坐标轴围成的公共区域（凸多边形）。
计算交点：
- 约束1与约束2交点：
解方程组
\(2x_1 + x_2 = 100\)
\(x_1 + 3x_2 = 90\)
得 \(x_1 = 42, x_2 = 16\)（点P1）
- 约束1与约束3交点：
\(2x_1 + x_2 = 100\)
\(3x_1 + 2x_2 = 120\)
得 \(x_1 = 80, x_2 = -60\)（不在第一象限，舍去）
- 约束2与约束3交点：
\(x_1 + 3x_2 = 90\)
\(3x_1 + 2x_2 = 120\)
得 \(x_1 = 20, x_2 = 70/3 \approx 23.33\)（点P2）
- 与坐标轴交点：
(0,0), (0,30), (40,0) 等。
可行域顶点（只取第一象限内满足所有约束的点）：
- O(0,0)
- A(0,30)（约束2与y轴交点，检查约束3：3×0+2×30=60≤120，满足）
- B(20, 70/3) ≈ (20, 23.33)（约束2与3交点，检查约束1：2×20+70/3≈40+23.33=63.33≤100，满足）
- C(40,0)（约束3与x轴交点，检查约束2：40+0=40≤90，满足）
4. 单纯形法求解（代数步骤）
将模型标准化（加入松弛变量 \(s_1, s_2, s_3 \geq 0\)）：
\[\begin{aligned}
\max \quad & Z = 40x_1 + 50x_2 \\
\text{s.t.} \quad & 2x_1 + x_2 + s_1 = 100 \\
& x_1 + 3x_2 + s_2 = 90 \\
& 3x_1 + 2x_2 + s_3 = 120 \\
& x_1, x_2, s_1, s_2, s_3 \geq 0
\end{aligned}
\]
初始单纯形表（基变量 \(s_1, s_2, s_3\)）：
| 基 |
\(x_1\) |
\(x_2\) |
\(s_1\) |
\(s_2\) |
\(s_3\) |
右端 |
| \(s_1\) |
2 |
1 |
1 |
0 |
0 |
100 |
| \(s_2\) |
1 |
3 |
0 |
1 |
0 |
90 |
| \(s_3\) |
3 |
2 |
0 |
0 |
1 |
120 |
| \(Z\) |
-40 |
-50 |
0 |
0 |
0 |
0 |
第一次迭代：
检验数中最小为 -50（\(x_2\) 列），选 \(x_2\) 进基。
比值测试：
- 行1: 100/1 = 100
- 行2: 90/3 = 30（最小）
- 行3: 120/2 = 60
→ 行2（\(s_2\)）出基，主元为 3。
将主元行（行2）除以3，使主元变为1：
新行2：\(\left[\frac{1}{3}, 1, 0, \frac{1}{3}, 0, 30\right]\)
用行运算消去其他行的 \(x_2\) 列：
- 新行1 = 行1 - 1×新行2：\([2-\frac{1}{3}, 0, 1, -\frac{1}{3}, 0, 70]\) → \([\frac{5}{3}, 0, 1, -\frac{1}{3}, 0, 70]\)
- 新行3 = 行3 - 2×新行2：\([3-\frac{2}{3}, 0, 0, -\frac{2}{3}, 1, 60]\) → \([\frac{7}{3}, 0, 0, -\frac{2}{3}, 1, 60]\)
- 新Z行 = 旧Z行 + 50×新行2：\([-40+\frac{50}{3}, 0, 0, \frac{50}{3}, 0, 1500]\) → \([-\frac{70}{3}, 0, 0, \frac{50}{3}, 0, 1500]\)
新表：
| 基 |
\(x_1\) |
\(x_2\) |
\(s_1\) |
\(s_2\) |
\(s_3\) |
右端 |
| \(s_1\) |
5/3 |
0 |
1 |
-1/3 |
0 |
70 |
| \(x_2\) |
1/3 |
1 |
0 |
1/3 |
0 |
30 |
| \(s_3\) |
7/3 |
0 |
0 |
-2/3 |
1 |
60 |
| \(Z\) |
-70/3 |
0 |
0 |
50/3 |
0 |
1500 |
第二次迭代：
检验数中 \(x_1\) 列为负（-70/3），选 \(x_1\) 进基。
比值测试：
- 行1: 70 / (5/3) = 42
- 行2: 30 / (1/3) = 90
- 行3: 60 / (7/3) ≈ 25.714（最小）
→ 行3（\(s_3\)）出基，主元为 7/3。
主元行（行3）乘以 3/7：\([1, 0, 0, -2/7, 3/7, 180/7]\)
消去其他行的 \(x_1\) 列：
-
新行1 = 行1 - (5/3)×新行3：
\([\frac{5}{3}-\frac{5}{3}, 0, 1, -\frac{1}{3}+\frac{10}{21}, 0-\frac{5}{7}, 70-\frac{300}{7}]\)
→ \([0, 0, 1, \frac{1}{7}, -\frac{5}{7}, 30]\)（右端：70-300/7=190/7≈27.14? 应仔细算：70=490/7, 490/7-300/7=190/7≈27.14，但注意行运算可能出错，重新算）
更仔细计算：
行1右端 = 70 = 490/7
减去 (5/3)×(180/7) = (5×180)/(3×7) = 900/21 = 300/7
差值 = 490/7 - 300/7 = 190/7 ≈ 27.14。
新行1：\([0, 0, 1, (-1/3) + (5/3)×(2/7), 0 - (5/3)×(3/7)]\)
\(s_2\) 系数：-1/3 + (5/3)×(2/7) = -1/3 + 10/21 = -7/21+10/21=3/21=1/7
\(s_3\) 系数：0 - (5/3)×(3/7) = -15/21 = -5/7
正确。
-
新行2 = 行2 - (1/3)×新行3：
\([1/3-1/3, 1, 0, 1/3 - (1/3)×(-2/7), 0 - (1/3)×(3/7)]\)
→ \([0, 1, 0, 1/3+2/21, -1/7]\) = \([0, 1, 0, 9/21, -1/7]\) = \([0, 1, 0, 3/7, -1/7, 30-60/7]\)
右端：30=210/7, 210/7-60/7=150/7≈21.43。
-
新Z行 = 旧Z行 + (70/3)×新行3：
\([-70/3+70/3, 0, 0, 50/3 + (70/3)×(-2/7), 0 + (70/3)×(3/7)]\)
= \([0, 0, 0, 50/3 - 20/3, 10]\) = \([0, 0, 0, 10, 10, 1500 + (70/3)×(180/7)]\)
注意 (70/3)×(180/7) = (70×180)/(3×7) = 1800/3 = 600
所以 Z 值 = 1500 + 600 = 2100。
新表：
| 基 |
\(x_1\) |
\(x_2\) |
\(s_1\) |
\(s_2\) |
\(s_3\) |
右端 |
| \(s_1\) |
0 |
0 |
1 |
1/7 |
-5/7 |
190/7≈27.14 |
| \(x_2\) |
0 |
1 |
0 |
3/7 |
-1/7 |
150/7≈21.43 |
| \(x_1\) |
1 |
0 |
0 |
-2/7 |
3/7 |
180/7≈25.71 |
| \(Z\) |
0 |
0 |
0 |
10 |
10 |
2100 |
最优性检验：
所有检验数（\(s_2, s_3\) 对应）均为非负（10, 10），达到最优。
最优解：
\(x_1 = 180/7 \approx 25.71\)，\(x_2 = 150/7 \approx 21.43\)，
最优值 \(Z = 40×(180/7) + 50×(150/7) = (7200+7500)/7 = 14700/7 = 2100\)。
5. 对偶问题与经济解释
原问题的对偶问题为：
\[\begin{aligned}
\min \quad & W = 100y_1 + 90y_2 + 120y_3 \\
\text{s.t.} \quad & 2y_1 + y_2 + 3y_3 \geq 40 \\
& y_1 + 3y_2 + 2y_3 \geq 50 \\
& y_1, y_2, y_3 \geq 0
\end{aligned}
\]
其中 \(y_1, y_2, y_3\) 分别表示机器工时、人工工时、排放物的“影子价格”。
最终单纯形表中，松弛变量 \(s_2, s_3\) 对应的检验数 10, 10 就是 \(y_2, y_3\) 的最优值，而 \(y_1=0\)（因为 \(s_1\) 是基变量，其检验数为0）。
经济含义：在当前最优解下，人工工时和排放物每增加1单位，目标函数分别增加10元；而机器工时已冗余（影子价格为0）。
6. 灵敏度分析（简要说明）
- 若A产品利润系数从40变为 \(40+\Delta\)，保持最优基不变的条件是检验数仍非负，可计算出 \(\Delta\) 的范围。
- 若机器工时从100变为 \(100+\delta\)，由于 \(s_1\) 是基变量且影子价格为0，在一定范围内增加机器工时不会增加利润（因为其他约束已紧）。
- 排放物限制从120变为 \(120+\delta\)，利润增加量为 \(10\delta\)（直到其他约束变紧为止）。
7. 总结
本题通过线性规划建模，用单纯形法求出了最优生产计划：
生产A约25.71单位，B约21.43单位，最大日利润为2100元。
关键约束是人工工时和排放物限制（影子价格均为10），机器工时未用尽（松弛变量 \(s_1=190/7\)），因此增加机器资源不会提高利润。
基于线性规划的“最优生产计划”建模与求解示例 1. 题目描述 假设一家工厂生产两种产品A和B。 生产每单位A产品需要消耗2小时的机器工时、1小时的人工工时，并产生3千克的排放物。 生产每单位B产品需要消耗1小时的机器工时、3小时的人工工时，并产生2千克的排放物。 工厂每天可用资源上限为： 机器工时：100小时 人工工时：90小时 排放物允许总量：120千克（环保限制） 每单位A产品的利润为40元，每单位B产品的利润为50元。 目标 ：在资源限制下，确定每天生产A和B的数量（可不为整数），以最大化总利润。 2. 建立线性规划模型 设 \(x_ 1\) = 产品A的日产量，\(x_ 2\) = 产品B的日产量。 目标函数 （最大化利润）： \[ \max \quad Z = 40x_ 1 + 50x_ 2 \] 约束条件 ： 机器工时限制：\(2x_ 1 + x_ 2 \leq 100\) 人工工时限制：\(x_ 1 + 3x_ 2 \leq 90\) 排放物限制：\(3x_ 1 + 2x_ 2 \leq 120\) 非负约束：\(x_ 1 \geq 0, x_ 2 \geq 0\) 3. 图解法（直观理解） 由于只有两个变量，可在平面直角坐标系中画出约束区域： 约束1 ：\(2x_ 1 + x_ 2 \leq 100\) 边界直线：\(2x_ 1 + x_ 2 = 100\)，过点 (0,100) 和 (50,0)。 约束2 ：\(x_ 1 + 3x_ 2 \leq 90\) 边界直线：\(x_ 1 + 3x_ 2 = 90\)，过点 (0,30) 和 (90,0)。 约束3 ：\(3x_ 1 + 2x_ 2 \leq 120\) 边界直线：\(3x_ 1 + 2x_ 2 = 120\)，过点 (0,60) 和 (40,0)。 可行域 ： 上述三个不等式与坐标轴围成的公共区域（凸多边形）。 计算交点： 约束1与约束2交点： 解方程组 \(2x_ 1 + x_ 2 = 100\) \(x_ 1 + 3x_ 2 = 90\) 得 \(x_ 1 = 42, x_ 2 = 16\)（点P1） 约束1与约束3交点： \(2x_ 1 + x_ 2 = 100\) \(3x_ 1 + 2x_ 2 = 120\) 得 \(x_ 1 = 80, x_ 2 = -60\)（不在第一象限，舍去） 约束2与约束3交点： \(x_ 1 + 3x_ 2 = 90\) \(3x_ 1 + 2x_ 2 = 120\) 得 \(x_ 1 = 20, x_ 2 = 70/3 \approx 23.33\)（点P2） 与坐标轴交点： (0,0), (0,30), (40,0) 等。 可行域顶点 （只取第一象限内满足所有约束的点）： O(0,0) A(0,30)（约束2与y轴交点，检查约束3：3×0+2×30=60≤120，满足） B(20, 70/3) ≈ (20, 23.33)（约束2与3交点，检查约束1：2×20+70/3≈40+23.33=63.33≤100，满足） C(40,0)（约束3与x轴交点，检查约束2：40+0=40≤90，满足） 4. 单纯形法求解（代数步骤） 将模型标准化（加入松弛变量 \(s_ 1, s_ 2, s_ 3 \geq 0\)）： \[ \begin{aligned} \max \quad & Z = 40x_ 1 + 50x_ 2 \\ \text{s.t.} \quad & 2x_ 1 + x_ 2 + s_ 1 = 100 \\ & x_ 1 + 3x_ 2 + s_ 2 = 90 \\ & 3x_ 1 + 2x_ 2 + s_ 3 = 120 \\ & x_ 1, x_ 2, s_ 1, s_ 2, s_ 3 \geq 0 \end{aligned} \] 初始单纯形表 （基变量 \(s_ 1, s_ 2, s_ 3\)）： | 基 | \(x_ 1\) | \(x_ 2\) | \(s_ 1\) | \(s_ 2\) | \(s_ 3\) | 右端 | |------|--------|--------|--------|--------|--------|------| | \(s_ 1\) | 2 | 1 | 1 | 0 | 0 | 100 | | \(s_ 2\) | 1 | 3 | 0 | 1 | 0 | 90 | | \(s_ 3\) | 3 | 2 | 0 | 0 | 1 | 120 | | \(Z\) | -40 | -50 | 0 | 0 | 0 | 0 | 第一次迭代 ： 检验数中最小为 -50（\(x_ 2\) 列），选 \(x_ 2\) 进基。 比值测试： 行1: 100/1 = 100 行2: 90/3 = 30（最小） 行3: 120/2 = 60 → 行2（\(s_ 2\)）出基，主元为 3。 将主元行（行2）除以3，使主元变为1： 新行2：\(\left[ \frac{1}{3}, 1, 0, \frac{1}{3}, 0, 30\right ]\) 用行运算消去其他行的 \(x_ 2\) 列： 新行1 = 行1 - 1×新行2：\([ 2-\frac{1}{3}, 0, 1, -\frac{1}{3}, 0, 70]\) → \([ \frac{5}{3}, 0, 1, -\frac{1}{3}, 0, 70 ]\) 新行3 = 行3 - 2×新行2：\([ 3-\frac{2}{3}, 0, 0, -\frac{2}{3}, 1, 60]\) → \([ \frac{7}{3}, 0, 0, -\frac{2}{3}, 1, 60 ]\) 新Z行 = 旧Z行 + 50×新行2：\([ -40+\frac{50}{3}, 0, 0, \frac{50}{3}, 0, 1500]\) → \([ -\frac{70}{3}, 0, 0, \frac{50}{3}, 0, 1500 ]\) 新表： | 基 | \(x_ 1\) | \(x_ 2\) | \(s_ 1\) | \(s_ 2\) | \(s_ 3\) | 右端 | |------|---------|--------|--------|------------|--------|------| | \(s_ 1\) | 5/3 | 0 | 1 | -1/3 | 0 | 70 | | \(x_ 2\) | 1/3 | 1 | 0 | 1/3 | 0 | 30 | | \(s_ 3\) | 7/3 | 0 | 0 | -2/3 | 1 | 60 | | \(Z\) | -70/3 | 0 | 0 | 50/3 | 0 | 1500 | 第二次迭代 ： 检验数中 \(x_ 1\) 列为负（-70/3），选 \(x_ 1\) 进基。 比值测试： 行1: 70 / (5/3) = 42 行2: 30 / (1/3) = 90 行3: 60 / (7/3) ≈ 25.714（最小） → 行3（\(s_ 3\)）出基，主元为 7/3。 主元行（行3）乘以 3/7：\([ 1, 0, 0, -2/7, 3/7, 180/7 ]\) 消去其他行的 \(x_ 1\) 列： 新行1 = 行1 - (5/3)×新行3： \([ \frac{5}{3}-\frac{5}{3}, 0, 1, -\frac{1}{3}+\frac{10}{21}, 0-\frac{5}{7}, 70-\frac{300}{7} ]\) → \([ 0, 0, 1, \frac{1}{7}, -\frac{5}{7}, 30 ]\)（右端：70-300/7=190/7≈27.14? 应仔细算：70=490/7, 490/7-300/7=190/7≈27.14，但注意行运算可能出错，重新算） 更仔细计算： 行1右端 = 70 = 490/7 减去 (5/3)×(180/7) = (5×180)/(3×7) = 900/21 = 300/7 差值 = 490/7 - 300/7 = 190/7 ≈ 27.14。 新行1：\([ 0, 0, 1, (-1/3) + (5/3)×(2/7), 0 - (5/3)×(3/7) ]\) \(s_ 2\) 系数：-1/3 + (5/3)×(2/7) = -1/3 + 10/21 = -7/21+10/21=3/21=1/7 \(s_ 3\) 系数：0 - (5/3)×(3/7) = -15/21 = -5/7 正确。 新行2 = 行2 - (1/3)×新行3： \([ 1/3-1/3, 1, 0, 1/3 - (1/3)×(-2/7), 0 - (1/3)×(3/7) ]\) → \([ 0, 1, 0, 1/3+2/21, -1/7]\) = \([ 0, 1, 0, 9/21, -1/7]\) = \([ 0, 1, 0, 3/7, -1/7, 30-60/7 ]\) 右端：30=210/7, 210/7-60/7=150/7≈21.43。 新Z行 = 旧Z行 + (70/3)×新行3： \([ -70/3+70/3, 0, 0, 50/3 + (70/3)×(-2/7), 0 + (70/3)×(3/7) ]\) = \([ 0, 0, 0, 50/3 - 20/3, 10]\) = \([ 0, 0, 0, 10, 10, 1500 + (70/3)×(180/7) ]\) 注意 (70/3)×(180/7) = (70×180)/(3×7) = 1800/3 = 600 所以 Z 值 = 1500 + 600 = 2100。 新表： | 基 | \(x_ 1\) | \(x_ 2\) | \(s_ 1\) | \(s_ 2\) | \(s_ 3\) | 右端 | |------|--------|--------|--------|--------|--------|------| | \(s_ 1\) | 0 | 0 | 1 | 1/7 | -5/7 | 190/7≈27.14 | | \(x_ 2\) | 0 | 1 | 0 | 3/7 | -1/7 | 150/7≈21.43 | | \(x_ 1\) | 1 | 0 | 0 | -2/7 | 3/7 | 180/7≈25.71 | | \(Z\) | 0 | 0 | 0 | 10 | 10 | 2100 | 最优性检验 ： 所有检验数（\(s_ 2, s_ 3\) 对应）均为非负（10, 10），达到最优。 最优解： \(x_ 1 = 180/7 \approx 25.71\)，\(x_ 2 = 150/7 \approx 21.43\)， 最优值 \(Z = 40×(180/7) + 50×(150/7) = (7200+7500)/7 = 14700/7 = 2100\)。 5. 对偶问题与经济解释 原问题的对偶问题为： \[ \begin{aligned} \min \quad & W = 100y_ 1 + 90y_ 2 + 120y_ 3 \\ \text{s.t.} \quad & 2y_ 1 + y_ 2 + 3y_ 3 \geq 40 \\ & y_ 1 + 3y_ 2 + 2y_ 3 \geq 50 \\ & y_ 1, y_ 2, y_ 3 \geq 0 \end{aligned} \] 其中 \(y_ 1, y_ 2, y_ 3\) 分别表示机器工时、人工工时、排放物的“影子价格”。 最终单纯形表中，松弛变量 \(s_ 2, s_ 3\) 对应的检验数 10, 10 就是 \(y_ 2, y_ 3\) 的最优值，而 \(y_ 1=0\)（因为 \(s_ 1\) 是基变量，其检验数为0）。 经济含义 ：在当前最优解下，人工工时和排放物每增加1单位，目标函数分别增加10元；而机器工时已冗余（影子价格为0）。 6. 灵敏度分析（简要说明） 若A产品利润系数从40变为 \(40+\Delta\)，保持最优基不变的条件是检验数仍非负，可计算出 \(\Delta\) 的范围。 若机器工时从100变为 \(100+\delta\)，由于 \(s_ 1\) 是基变量且影子价格为0，在一定范围内增加机器工时不会增加利润（因为其他约束已紧）。 排放物限制从120变为 \(120+\delta\)，利润增加量为 \(10\delta\)（直到其他约束变紧为止）。 7. 总结 本题通过线性规划建模，用单纯形法求出了最优生产计划： 生产A约25.71单位，B约21.43单位，最大日利润为2100元 。 关键约束是人工工时和排放物限制（影子价格均为10），机器工时未用尽（松弛变量 \(s_ 1=190/7\)），因此增加机器资源不会提高利润。
