【课后作业05】使用非线性规划模型数鸡蛋 隐藏答案 | 返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：Python3.11
运行环境：Intel Core i7-7700K CPU 4.2GHz, nVidia GeForce GTX 1080 Ti
本教案所涉及的数据集仅用于教学和交流使用，请勿用作商用。

最后更新：2024年2月27日

---

【知识点】

图论基础、最小生成树

【作业要求】

使用word文档或Markdown文档进行作答，使用Python编写程序，最终结果合并为一个word文档或Markdown文档，并另存为PDF格式进行提交。

注意：可以使用手机拍照文档进行提交，但请不要使用word文档直接进行提交。

【问题描述】

[习题5.2-P134] 一个塑料大筐里装满了鸡蛋，两个两个地数，余1个鸡蛋；三个三个地数，正好输完；四个四个地数，余1个鸡蛋；五个五个地数，余4个鸡蛋；六个六个地数，余3个鸡蛋；七个七个地数，余4个鸡蛋；八个八个地数，余1个鸡蛋；九个九个地数，正好输完。请建立数学规划模型求大筐中鸡蛋个数的最小值是多少。

要求手工建模后使用Python进行求解。

【答案及解析】

（1）模型假设
设大框中鸡蛋个数的最小值为 $x$。根据题目中的条件建立如下数学规划模型求解 $x$。

（2）建立模型

$$\min x, s.t.\begin{cases} x \mod 2 = 1, \\ x \mod 3 = 0, \\ x \mod 4 = 1, \\ x \mod 5 = 4, \\ x \mod 6 = 3, \\ x \mod 7 = 4, \\ x \mod 8 = 1, \\ x \mod 9 = 0, \\ x \geq 0 且为整数 \end{cases}$$

其中，约束条件中的 $x \mod 2$ 表示 $x$ 除以2的余数，$x \mod 3$ 表示 $x$ 除以3的余数，以此类推。

（3）模型简化

以上数学规划模型为非线性整数规划模型，无法直接使用Python进行求解。但我们可以引入8个松弛整数变量 $y_i(i=1,2,...,8)$，将非线性问题转换为整数规划模型进行求解。

$$\min x, s.t.\begin{cases} 2y_1 + 1 = x, \\ 3y_2= x, \\ 4y_3 + 1 = x, \\ 5y_4 + 4 = x, \\ 6y_5 + 3 = x, \\ 7y_6 + 4 = x, \\ 8y_7 + 1 = x, \\ 9y_8= x, \\ x \geq 0 且为整数 \\ y_i \geq 0 且为整数, i=1,2,...,8 \end{cases}$$

（4）编程求解

接下来，我们使用Python编写代码求解该问题，最终可以计算得到鸡蛋的最小个数为1089个。

import numpy as np
import cvxpy as cp

a = np.array([1,0,1,4,3,4,1,0])    # 8个余数值
x = cp.Variable(integer = True)    # 定义整数变量x
y = cp.Variable(8,integer = True)  # 定义8个整数变量y
objective = cp.Minimize(x)         # 定义目标函数为最小化变量x
constraints = [x >= 0, y >= 0]     # 定义约束条件
for i in range(8):                 # 定义约束条件
    constraints.append((i+2) * y[i] + a[i] == x)

prob = cp.Problem(objective, constraints)
result = prob.solve(solver = cp.GLPK_MI)
print('最小个数为：', result)

最小个数为： 1089.0