【课后作业04】求解线性规划 隐藏答案 | 返回首页

作者：欧新宇（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文档直接进行提交。

【问题描述】

[习题4.2-P101] 求解线性规划问题：
min⁡Z1=20x1+90x2+80x3+70x4+30x5\min Z_1 = 20x_1 + 90x_2 + 80x_3 + 70x_4 + 30x_5

s.t.{x1+x2+x5≥30x3+x4≥303x1+2x3≤1203x2+2x4+x5≤48xj≥0，且为整数,j=1,2,...,5.s.t. \left\{ \begin{array}{l} x_1 + x_2 + x_5 \geq 30 \\\\ x_3 + x_4 \geq 30 \\\\ 3x_1 + 2x_3 \leq 120 \\\\ 3x_2 + 2x_4 + x_5 \leq 48 \\\\ x_j \geq 0，且为整数, j = 1,2,...,5. \end{array} \right.

要求使用Python进行求解。

【答案及解析】

上述线性规划问题可用向量形式进行改写为：

min⁡z=cTx\min z = c^T x

s.t.{Ax≤bxj≥且为整数s.t. \begin{cases} Ax \leq b \\ x_j \geq 且为整数 \end{cases}

其中，c=[20,90,80,70,30]Tc = [20, 90, 80, 70, 30]^T，A=[−1−100−100−1−103020003021]A = \begin{bmatrix} -1 & -1 & 0 & 0 & -1 \\ 0 & 0 & -1 & -1 & 0 \\ 3 & 0 & 2 & 0 & 0 \\ 0 & 3 & 0 & 2 & 1 \\ \end{bmatrix}，
b=[−30,−30,120,48]Tb = [-30, -30, 120, 48]^T.

利用Python可求得最优解为：x1=30,x2=x5=0,x3=6,x4=24x_1 = 30, x_2=x_5=0, x_3=6, x_4=24

目标函数的最小值为2760。

import cvxpy as cp
import numpy as np
x = cp.Variable(5, integer=True)
c = np.array([20, 90, 80, 70, 30])
A = np.array([[-1, -1, 0, 0, -1],
    [0, 0, -1, -1, 0],
    [3, 0, 2, 0, 0],
    [0, 3, 0, 2, 1]])
b = np.array([-30, -30, 120, 48])
objective = cp.Minimize(c @ x)
constraints = [A @ x <= b, x >= 0]
problem = cp.Problem(objective, constraints)
problem.solve(solver='GLPK_MI')
print("最优解为：", x.value)
print("目标函数的最小值为：", problem.value)

最优解为： [30.  0.  6. 24.  0.]
目标函数的最小值为： 2760.0

【课后作业04】求解线性规划 隐藏答案 | 返回首页

【知识点】

【作业要求】

【问题描述】

【答案及解析】

≡