"""二维产品组合的线性规划。运行:python mmf_lp.py。""" import json from itertools import combinations # NumPy 用于矩阵与方程组,Matplotlib 用于画可行域,combinations 负责列出不重复的边界对。 import matplotlib.pyplot as plt import numpy as np def main(): # x、y 为两种产品的批量。前三行分别是共享、A、B 三项产能。 # 批量的非负约束也写入矩阵,两个坐标轴因而参与顶点枚举。 # constraints 每行是一个约束的 (x 系数, y 系数),同一行编号对应 limits 中的右端项。 constraints = np.array([[1, 1], [1, 0], [0, 1], [-1, 0], [0, -1]]) limits = np.array([4, 3, 2, 0, 0]) profit = np.array([2, 1]) # 两条不平行边界相交给出一个候选点,再检查其是否满足全部约束。 candidates = [] for first, second in combinations(range(len(limits)), 2): active = [first, second] boundary = constraints[active] # 行列式接近 0 时两法向量近似平行,边界联立没有可靠的唯一交点。 if abs(np.linalg.det(boundary)) < 1e-12: continue point = np.linalg.solve(boundary, limits[active]) if np.all(constraints @ point <= limits + 1e-9): candidates.append(point) # 一点可同时落在多条边界上,按行去重后再计算各顶点的目标值。 vertices = np.unique(candidates, axis=0) scores = vertices @ profit best_index = np.argmax(scores) optimum = vertices[best_index] best_profit = scores[best_index] # 松弛量只报告前三条资源约束。接近零表示这项资源在最优点已经用满。 slack = limits[:3] - constraints[:3] @ optimum result = { "x": optimum.tolist(), "profit": float(best_profit), "slack": slack.tolist(), "vertices": len(vertices), } print("LAB_RESULT " + json.dumps(result)) # 根据相对中心的极角排序,按可行多边形的边走一圈。 centered = vertices - vertices.mean(axis=0) boundary_order = np.argsort(np.arctan2(centered[:, 1], centered[:, 0])) polygon = vertices[boundary_order] fig, ax = plt.subplots() ax.fill(*polygon.T, alpha=0.25, label="Feasible set") ax.scatter(*vertices.T, s=20, label="Vertices") ax.scatter(*optimum, color="tab:red", s=65, label="Optimum", zorder=4) for level in (3, best_profit): # 目标等值线 c1*x + c2*y = level,保持同一斜率平移。 ax.axline((0, level / profit[1]), slope=-profit[0] / profit[1], color="tab:orange", linestyle="--") ax.set(xlabel="Product A (batches)", ylabel="Product B (batches)", xlim=(0, 4), ylim=(0, 3), title="LP: feasible set and profit lines") ax.set_aspect("equal") ax.legend() fig.tight_layout() # Agg 可在终端或自动检查中渲染画布。普通图形后端则打开窗口。 if plt.get_backend().lower() == "agg": fig.canvas.draw() else: plt.show() if __name__ == "__main__": main()