DASE 7113 · 课程精讲

CVXPY项目赶工

按输入、计算、输出的顺序理解,再逐句对照老师代码。

打开老师的完整代码 · Moodle 原页

输入是九项活动的原工期、前置关系、最大压缩天数和每压缩一天的费用。输出要回答:怎样以最低额外费用,把原本47天的项目压到40天完成?

代码中的 xA 至 xI 是压缩天数;TA 至 TI 是完成时刻。它们不是同一类量。比如A压缩2天,xA=2,实际工期和完成时刻均为8−2=6。

  1. 先建立18个非负变量。
  2. 限制每项压缩量不超过表格上界。
  3. 通过工期关系确定任务先后。一个任务有多个前置时,用多条不等式表示等待最晚的一项。
  4. 再要求所有任务40天内完成,最小化“每日压缩成本×压缩天数”的总和。

运行结果为最优成本约46500,压缩向量约为(2,2,0,3,1,1,0,0,0)。逐项计算费用:A为10000、B为18000、D为13500、E为1500、F为3500,其余约为零,总和46500。

对应完成时刻为(6,14,23,28,18,27,30,30,40)。例如G等待C、D、F中最晚的D=28,再用2天到30;H也在30完成;I等两者并用10天到40。输出里的约10−9小量按本题精度读作零即可。单一前置的等式安排表示本模型中没有必要插入等待;多前置任务仍用不等式。

从上到下读

逐句讲解

左侧行号与保存的代码文件一致。空行用于分段。

行原代码这一行在做什么
1# -*- coding: utf-8 -*-编码声明,说明这个源文件使用UTF-8,便于保存中文等字符。
2import cvxpy as cp导入CVXPY并简写为cp,用来建立和求解优化模型。
5# Define variables with bounds注释:下面定义变量,并在构造时加入非负性。
6xA = cp.Variable(name="xA", nonneg=True)建立非负变量xA,表示活动A缩短的天数;name为输出时使用的名称。
7xB = cp.Variable(name="xB", nonneg=True)建立非负变量xB,表示活动B缩短的天数;name为输出时使用的名称。
8xC = cp.Variable(name="xC", nonneg=True)建立非负变量xC,表示活动C缩短的天数;name为输出时使用的名称。
9xD = cp.Variable(name="xD", nonneg=True)建立非负变量xD,表示活动D缩短的天数;name为输出时使用的名称。
10xE = cp.Variable(name="xE", nonneg=True)建立非负变量xE,表示活动E缩短的天数;name为输出时使用的名称。
11xF = cp.Variable(name="xF", nonneg=True)建立非负变量xF,表示活动F缩短的天数;name为输出时使用的名称。
12xG = cp.Variable(name="xG", nonneg=True)建立非负变量xG,表示活动G缩短的天数;name为输出时使用的名称。
13xH = cp.Variable(name="xH", nonneg=True)建立非负变量xH,表示活动H缩短的天数;name为输出时使用的名称。
14xI = cp.Variable(name="xI", nonneg=True)建立非负变量xI,表示活动I缩短的天数;name为输出时使用的名称。
17TA = cp.Variable(name="TA", nonneg=True)建立非负变量TA,表示活动A完成时刻,时间零点为项目开始。
18TB = cp.Variable(name="TB", nonneg=True)建立非负变量TB,表示活动B完成时刻,时间零点为项目开始。
19TC = cp.Variable(name="TC", nonneg=True)建立非负变量TC,表示活动C完成时刻,时间零点为项目开始。
20TD = cp.Variable(name="TD", nonneg=True)建立非负变量TD,表示活动D完成时刻,时间零点为项目开始。
21TE = cp.Variable(name="TE", nonneg=True)建立非负变量TE,表示活动E完成时刻,时间零点为项目开始。
22TF = cp.Variable(name="TF", nonneg=True)建立非负变量TF,表示活动F完成时刻,时间零点为项目开始。
23TG = cp.Variable(name="TG", nonneg=True)建立非负变量TG,表示活动G完成时刻,时间零点为项目开始。
24TH = cp.Variable(name="TH", nonneg=True)建立非负变量TH,表示活动H完成时刻,时间零点为项目开始。
25TI = cp.Variable(name="TI", nonneg=True)建立非负变量TI,表示活动I完成时刻,时间零点为项目开始。
28# Upper bounds注释:下面收集每个活动最多可缩短几天的上界。
29constraints = [创建constraints列表,接下来的每项都是一条约束。
30 xA <= 2,约束活动A最多压缩2天。
31 xB <= 2,约束活动B最多压缩2天。
32 xC <= 4,约束活动C最多压缩4天。
33 xD <= 3,约束活动D最多压缩3天。
34 xE <= 1,约束活动E最多压缩1天。
35 xF <= 3,约束活动F最多压缩3天。
36 xG <= 0, # effectively fixes xG to 0约束活动G最多压缩0天。它已非负且上界为0,所以固定xG=0。
37 xH <= 1,约束活动H最多压缩1天。
38 xI <= 3约束活动I最多压缩3天。
39]结束这一组压缩上界约束。
42# Add the constraints from the original model注释:接下来添加工期先后关系与40天完成要求。
43constraints += [用+=把新的一组约束追加到原列表,不会删除原先的压缩上界。
44 TA == 8 - xA,活动A无前置,从零时刻开始;完成时刻等于8减压缩量xA。
45 TB == TA + 10 - xB,B紧接A开始,完成时刻为TA加10天再减xB。
46 TC == TB + 9 - xC,C紧接B开始,完成时刻为TB加9天再减xC。
48 TD >= TB + 8 - xD,D开始前B必须完成,所以TD至少为TB加D实际工期8−xD。
49 TD >= TC + 8 - xD,D同时也要等待C,这条与上一条一起要求D等全部前置完成。
51 TE == TB + 5 - xE,E在B后开始,实际工期为5−xE。
52 TF == TE + 10 - xF,F在E后开始,实际工期为10−xF。
54 TG >= TC + 2 - xG,G必须等C结束后再用2−xG天完成。
55 TG >= TD + 2 - xG,G也必须等待D;多前置条件需要逐项添加。
56 TG >= TF + 2 - xG,G还必须等待F,因此三条G约束共同实现取最晚前置时刻。
58 TH == TF + 3 - xH,H在F后开始,实际工期为3−xH。
60 TI >= TH + 10 - xI,I必须等H,再用10−xI天完成。
61 TI >= TG + 10 - xI,I同时必须等G,和上一条一起表示两个前置要求。
63 TA <= 40,要求活动A的完成时刻TA不超过第40天。
64 TB <= 40,要求活动B的完成时刻TB不超过第40天。
65 TC <= 40,要求活动C的完成时刻TC不超过第40天。
66 TD <= 40,要求活动D的完成时刻TD不超过第40天。
67 TE <= 40,要求活动E的完成时刻TE不超过第40天。
68 TF <= 40,要求活动F的完成时刻TF不超过第40天。
69 TG <= 40,要求活动G的完成时刻TG不超过第40天。
70 TH <= 40,要求活动H的完成时刻TH不超过第40天。
71 TI <= 40要求活动I的完成时刻TI不超过第40天。
72]结束第二组约束列表,所有压缩、工期与截止条件已收集完。
75# Define the objective注释:下面定义要最小化的额外赶工成本。
76objective = cp.Minimize(5000*xA + 9000*xB + 7000*xC + 4500*xD + 建立最小化目标;这一行先写A、B、C、D的单日压缩成本乘压缩天数,表达式续到下一行。
77 1500*xE + 3500*xF + 4500*xH + 9500*xI)补上E、F、H、I的成本;G不能压缩,因此没有额外成本项。关闭Minimize调用。
80# Create and solve the problem注释:下面把目标与限制组成问题并求解。
81problem = cp.Problem(objective, constraints)创建Problem对象,把最小化目标和全部constraints放在一起。
82problem.solve()调用求解器,求最小额外成本及相应压缩与时间安排。
85# Print results注释:下面打印求解状态、目标值和所有变量的数值。
86print(f"Status: {problem.status}")打印problem.status。本次为optimal,表示模型求得最优状态。
87print(f"Optimal value: {problem.value}")打印最优成本,约46500。很小的小数尾差来自浮点数值计算。
90for var in [xA, xB, xC, xD, xE, xF, xG, xH, xI, 开始遍历变量列表,这一行先列出九个压缩天数变量。
91 TA, TB, TC, TD, TE, TF, TG, TH, TI]:补上九个完成时刻变量,并开始for循环体。
92 print(f"{var.name()}: {var.value}")逐个打印变量名称var.name()及其数值var.value,便于把输出对回数学模型。