按输入、计算、输出的顺序理解,再逐句对照老师代码。
输入是九项活动的原工期、前置关系、最大压缩天数和每压缩一天的费用。输出要回答:怎样以最低额外费用,把原本47天的项目压到40天完成?
代码中的 xA 至 xI 是压缩天数;TA 至 TI 是完成时刻。它们不是同一类量。比如A压缩2天,,实际工期和完成时刻均为。
运行结果为最优成本约46500,压缩向量约为。逐项计算费用:A为10000、B为18000、D为13500、E为1500、F为3500,其余约为零,总和46500。
对应完成时刻为。例如G等待C、D、F中最晚的D=28,再用2天到30;H也在30完成;I等两者并用10天到40。输出里的约小量按本题精度读作零即可。单一前置的等式安排表示本模型中没有必要插入等待;多前置任务仍用不等式。
左侧行号与保存的代码文件一致。空行用于分段。
| 行 | 原代码 | 这一行在做什么 |
|---|---|---|
| 1 | # -*- coding: utf-8 -*- | 编码声明,说明这个源文件使用UTF-8,便于保存中文等字符。 |
| 2 | import cvxpy as cp | 导入CVXPY并简写为cp,用来建立和求解优化模型。 |
| 5 | # Define variables with bounds | 注释:下面定义变量,并在构造时加入非负性。 |
| 6 | xA = cp.Variable(name="xA", nonneg=True) | 建立非负变量xA,表示活动A缩短的天数;name为输出时使用的名称。 |
| 7 | xB = cp.Variable(name="xB", nonneg=True) | 建立非负变量xB,表示活动B缩短的天数;name为输出时使用的名称。 |
| 8 | xC = cp.Variable(name="xC", nonneg=True) | 建立非负变量xC,表示活动C缩短的天数;name为输出时使用的名称。 |
| 9 | xD = cp.Variable(name="xD", nonneg=True) | 建立非负变量xD,表示活动D缩短的天数;name为输出时使用的名称。 |
| 10 | xE = cp.Variable(name="xE", nonneg=True) | 建立非负变量xE,表示活动E缩短的天数;name为输出时使用的名称。 |
| 11 | xF = cp.Variable(name="xF", nonneg=True) | 建立非负变量xF,表示活动F缩短的天数;name为输出时使用的名称。 |
| 12 | xG = cp.Variable(name="xG", nonneg=True) | 建立非负变量xG,表示活动G缩短的天数;name为输出时使用的名称。 |
| 13 | xH = cp.Variable(name="xH", nonneg=True) | 建立非负变量xH,表示活动H缩短的天数;name为输出时使用的名称。 |
| 14 | xI = cp.Variable(name="xI", nonneg=True) | 建立非负变量xI,表示活动I缩短的天数;name为输出时使用的名称。 |
| 17 | TA = cp.Variable(name="TA", nonneg=True) | 建立非负变量TA,表示活动A完成时刻,时间零点为项目开始。 |
| 18 | TB = cp.Variable(name="TB", nonneg=True) | 建立非负变量TB,表示活动B完成时刻,时间零点为项目开始。 |
| 19 | TC = cp.Variable(name="TC", nonneg=True) | 建立非负变量TC,表示活动C完成时刻,时间零点为项目开始。 |
| 20 | TD = cp.Variable(name="TD", nonneg=True) | 建立非负变量TD,表示活动D完成时刻,时间零点为项目开始。 |
| 21 | TE = cp.Variable(name="TE", nonneg=True) | 建立非负变量TE,表示活动E完成时刻,时间零点为项目开始。 |
| 22 | TF = cp.Variable(name="TF", nonneg=True) | 建立非负变量TF,表示活动F完成时刻,时间零点为项目开始。 |
| 23 | TG = cp.Variable(name="TG", nonneg=True) | 建立非负变量TG,表示活动G完成时刻,时间零点为项目开始。 |
| 24 | TH = cp.Variable(name="TH", nonneg=True) | 建立非负变量TH,表示活动H完成时刻,时间零点为项目开始。 |
| 25 | TI = cp.Variable(name="TI", nonneg=True) | 建立非负变量TI,表示活动I完成时刻,时间零点为项目开始。 |
| 28 | # Upper bounds | 注释:下面收集每个活动最多可缩短几天的上界。 |
| 29 | constraints = [ | 创建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天完成要求。 |
| 43 | constraints += [ | 用+=把新的一组约束追加到原列表,不会删除原先的压缩上界。 |
| 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 | 注释:下面定义要最小化的额外赶工成本。 |
| 76 | objective = 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 | 注释:下面把目标与限制组成问题并求解。 |
| 81 | problem = cp.Problem(objective, constraints) | 创建Problem对象,把最小化目标和全部constraints放在一起。 |
| 82 | problem.solve() | 调用求解器,求最小额外成本及相应压缩与时间安排。 |
| 85 | # Print results | 注释:下面打印求解状态、目标值和所有变量的数值。 |
| 86 | print(f"Status: {problem.status}") | 打印problem.status。本次为optimal,表示模型求得最优状态。 |
| 87 | print(f"Optimal value: {problem.value}") | 打印最优成本,约46500。很小的小数尾差来自浮点数值计算。 |
| 90 | for 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,便于把输出对回数学模型。 |