[人工智能]第2章 整数规划（一）

例2.5

??为了生产的需求，某工厂的一条生产线需要每天24h不间断运转，但是每天不同时间段所需要的工人最低数量不同，如表。已知每名工人的连续工作时间为8h。则改工厂应该为该生产线配备多少名工人，才能保证生产线的正常运转？

问题分析

??从降低经营成本的角度来看，为该生产线配备的工人数量越少，工厂所付出的工人薪资之和也就越低。因此，该问题需要确定在每个时间段工作的工人的数量，使其既能满足生产线的生产需求，又能使得雇佣的工人总数最低。

模型假设

（1）每名工人每24h只能工作8h；
（2）每名工人只能在某个班次的初始时刻报道。

符号说明

??设 $x_i$ 表示第 $i$ 个班次报道的工人数量，$i=1,2,?,6。$

模型建立

??该问题的目标函数为雇佣的工人总数最少。约束条件为安排在不同班次上班的工人应该不少于该班次所需的人数，且$x_i(i=1,2,?,6)$ 为非负整数。
??数学模型为
$$\begin{gathered} \min z=\sum _{i=1}^6{x}_i, \\ ?\begin{array}{ll}& x_1+x_6\ge 35,\\ & x_1+x_2\ge 40,\\ & x_2+x_3\ge 50,\\ & x_3+x_4\ge 45,\\ & x_4+x_5\ge 55,\\ & x_5+x_6\ge 30,\\ & x_i\ge 0且为整数,i=1,2,?,6.\end{array} \end{gathered}$$
求得的最优解为
$$\begin{gathered} x_1=35,x_2=5,x_3=45,x_4=0,x_5=55,x_6=0, \\ 或 \\ {x}_1=35,x_2=5,x_3=45,x_4=25,x_5=30,x_6=0, \end{gathered}$$
目标函数的最优值为140，，即最少需要140人，才能保证生产线正常运转。

python程序

python用到了PuLP库，网址 https://coin-or.github.io/pulp/

from pulp import *
x = [35, 40, 50, 45, 55, 30]
indexs = [i for i in range(1, 7)]  # 1~6
prob = LpProblem("Beer_Distribution_Problem", LpMinimize)  # 问题
vars = LpVariable.dicts("x", indexs, 0, None, LpInteger)  # 变量
prob += lpSum(vars)  # 目标函数
st = [
    [1, 6],
    [1, 2],
    [2, 3],
    [3, 4],
    [4, 5],
    [5, 6]
]
# 约束条件
for index, num in enumerate(st):
    prob += (
        lpSum( [vars[i] for i in num] ) >= x[index]
    )
prob.solve()  # 求解
prob.writeLP("Model.lp")  # 结果写到文件中
print("Status:", LpStatus[prob.status])  # 为'Optimal' 表示有最优解
# 最优解
for v in prob.variables():
    print(v.name, "=", v.varValue)
print(value(prob.objective))  # 最优值

文件如图

matlab程序

clc,clear;
prob = optimproblem;
x = optimvar('x',6, 'Type','integer','LowerBound', 0);
prob.Objective = sum(x);
 con = optimconstr(6);
a = [35, 40, 50, 45, 55, 30];
con(1) = x(1) + x(6) >= 35;
for i=1 : 5
	con(i + 1) = x(i)+x(i+1) >= a(i+1);
end
prob.Constraints.con = con;
[sol, fval, flag] = solve(prob);
sol.x;
fval;