用Python实现运筹学——Day 4: 线性规划的几何表示

一、学习内容

线性规划的几何表示：线性规划问题的解通常位于一个凸多边形（即可行解空间）的顶点上，这意味着在求解线性规划问题时，只需要找到可行解空间中的顶点并计算出目标函数值，再选择其中的最优解。
- 可行解空间：可行解空间是由约束条件定义的变量范围的集合。它由线性不等式形成的区域组成，该区域是一个凸集，即任意两个点之间的线段也完全在这个区域内。
- 凸集：在几何学中，凸集是指在集合中的任意两点之间的线段都位于集合内的区域。在线性规划中，凸集是由所有满足约束条件的解所构成的集合。
图解法求解线性规划：对于包含两个决策变量的线性规划问题，可以通过图解法直观地理解问题的几何性质。图解法通过绘制约束条件的线，将可行解空间（满足所有约束条件的解的区域）在坐标平面上展示出来，然后通过移动目标函数的等高线，找到使目标函数最大或最小的顶点。
图解法步骤：
- 绘制每个约束条件对应的直线。
- 标出可行解空间（满足所有约束条件的区域）。
- 将目标函数作为等值线画出，寻找该等值线在可行解空间上的最优解。

二、实战案例：简单生产分配问题的图解法求解

2.1 问题描述

一家公司生产两种产品 A 和 B。每种产品的利润和资源消耗如下：

产品	每单位利润（元）	每单位劳动时间（小时）	每单位原材料需求（单位）
A	60	4	2
B	50	2	3

公司每天最多有 32 小时的劳动时间和 24 单位的原材料。公司希望通过合理安排生产数量，使利润最大化。

2.2 线性规划模型

决策变量：
- $x_1$ ：每天生产的产品 A 的数量。
- $x_2$ ：每天生产的产品 B 的数量。
目标函数：最大化每日利润：
$Z = 60x_1 + 50x_2$
约束条件：

劳动时间限制： $4x_1 + 2x_2 \leq 32$
原材料限制： $x_1 + 3x_2 \leq 24$
非负性约束： $x_1 \geq 0, \quad x_2 \geq 0$

2.3 图解法求解步骤

绘制约束条件对应的直线：我们将绘制每个约束条件对应的直线，并找出可行解空间。可行解空间是满足所有约束条件的区域。
绘制目标函数的等高线：我们将目标函数等高线绘制在同一张图上，通过逐渐平移目标函数线，寻找在可行解空间中的最优解。

2.4 Python 实现

我们将使用 matplotlib 库绘制图形，并直观地展示解法。

import numpy as np
import matplotlib.pyplot as plt

# 创建决策变量范围
x1 = np.linspace(0, 10, 100)
x2 = np.linspace(0, 10, 100)

# 定义约束条件
def labor_constraint(x1):
    return (32 - 4 * x1) / 2  # 从 labor constraint 解出 x2

def material_constraint(x1):
    return (24 - 2 * x1) / 3  # 从 material constraint 解出 x2

# 绘制可行解空间
plt.figure(figsize=(8, 6))

# 绘制劳动时间限制
plt.plot(x1, labor_constraint(x1), label=r'$4x_1 + 2x_2 \leq 32$', color='blue')
plt.fill_between(x1, 0, labor_constraint(x1), where=(labor_constraint(x1) >= 0), color='blue', alpha=0.3)

# 绘制原材料限制
plt.plot(x1, material_constraint(x1), label=r'$2x_1 + 3x_2 \leq 24$', color='green')
plt.fill_between(x1, 0, material_constraint(x1), where=(material_constraint(x1) >= 0), color='green', alpha=0.3)

# 绘制坐标轴
plt.xlim((0, 10))
plt.ylim((0, 10))
plt.axhline(0, color='black',linewidth=1)
plt.axvline(0, color='black',linewidth=1)

# 绘制目标函数的等高线
for z in [100, 200, 300, 400, 500, 600]:
    plt.plot(x1, (z - 60 * x1) / 50, '--', label=f'$Z={z}$', color='red')

# 添加标签和标题
plt.xlabel(r'$x_1$ (产品 A 数量)')
plt.ylabel(r'$x_2$ (产品 B 数量)')
plt.title('线性规划的几何表示与图解法求解')

# 添加图例
plt.legend()

plt.grid(True)
plt.show()

2.5 代码解释

约束条件函数：
- labor_constraint(x1) 计算基于劳动时间约束下的 $x_2$ 。
- material_constraint(x1) 计算基于材料约束下的 $x_2$ 。
图解法：
- 我们在图上绘制了劳动时间和材料的约束条件直线，填充满足约束条件的区域，表示可行解空间。
- 同时，我们绘制了目标函数的等高线，通过观察等高线与可行解空间的交点，找到最优解。