"""设备采购:比较 0/1 最优解和连续松弛。运行:python mmf_integer_programming.py。""" import json from itertools import product # itertools 列出二元组合,NumPy 批量计算支出和价值,Matplotlib 对照整数点与松弛界。 import matplotlib.pyplot as plt import numpy as np def evaluate(costs, values, budget): # 每种设备最多买一台,枚举 2^n 种大小为 n 的 0/1 向量。 choices = np.array(list(product((0, 1), repeat=len(costs)))) # choices 每行是一种方案,每列对应一种设备;乘成本向量得到各行的总支出。 total_costs = choices @ costs total_values = choices @ values feasible = total_costs <= budget # 先筛预算内的行再比较价值,避免把高值但不可执行的组合当成最优。 best = choices[feasible][np.argmax(total_values[feasible])] # 此处只有一道预算约束,连续松弛是可分背包;按价值成本比依次购买。 relaxed = np.zeros(len(costs)) remaining = budget # 按单位价值降序投入。只有一个资源约束且连续可分时,这种贪心才给出松弛最优。 for index in np.argsort(-(values / costs), kind="stable"): fraction = min(1, remaining / costs[index]) relaxed[index] = fraction remaining -= fraction * costs[index] return best, relaxed, total_costs, total_values, feasible def main(): costs = np.array([3, 2, 2]) values = np.array([7, 4, 4]) budget = 4 best, relaxed, total_costs, total_values, feasible = evaluate(costs, values, budget) best_value = best @ values relaxed_value = relaxed @ values # 只改变预算,观察整数最优值何时跳变;原始模型仍保留同样的成本和价值。 changed_best, *_ = evaluate(costs, values, budget + 1) result = { "x": best.tolist(), "cost": int(best @ costs), "value": int(best_value), "relaxed_value": float(relaxed_value), "absolute_gap": float(relaxed_value - best_value), "changed_budget_value": int(changed_best @ values), } print("LAB_RESULT " + json.dumps(result)) # 每点是一种组合在「支出–价值」平面的投影;组合不同也可能落在同一坐标。 fig, ax = plt.subplots() ax.scatter(total_costs[feasible], total_values[feasible], label="Feasible integer") ax.scatter(total_costs[~feasible], total_values[~feasible], marker="x", label="Over budget") ax.scatter(best @ costs, best_value, color="tab:green", s=65, label="Integer optimum") ax.scatter(relaxed @ costs, relaxed_value, marker="*", color="tab:orange", s=110, label="Relaxation upper bound") # 竖线是预算上界,松弛星号可高于所有预算内的整数点。 ax.axvline(budget, linestyle="--", color="0.45") ax.set(title="Equipment purchase and the budget cutoff", xlabel="Total cost", ylabel="Total value") ax.legend() fig.tight_layout() if plt.get_backend().lower() == "agg": fig.canvas.draw() else: plt.show() if __name__ == "__main__": main()