第1章 线性规划与单纯形法

开篇案例

某昼夜服务的电信客户服务中心，每天各时间段内所需客户服务人员数如表1-1所示：

表1-1 时间分段及人数需求

设客户服务中心客户服务人员分别在各时间段一开始时上班，并连续工作八小时，问该客户服务中心怎样安排客户服务人员，既能满足工作需要，又只需配备最少客户服务人员？

解：设xi表示第i班次时开始上班的客户服务人员数，建立如下求解模型。

目标函数：minf(x)=x1+x2+x3+x4+x5+x6

约束条件：s.t. x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0

且x1,x2,x3,x4,x5,x6为整数

该模型可以利用Excel来求解。求解得到，该客户服务中心6个班次开始上班的客户服务人员数分别为45人、25人、35人、15人、15人、15人，既能满足工作需要，又只需配备最少的客户服务人员，配备最少客户服务人员数为150人。

线性规划是运筹学的一个重要分支。1939年，前苏联学者康托罗维奇提出了生产组织和计划中的类似线性规划模型。1947年，美国学者丹捷格（George B.Dantzig）提出了求解一般线性规划问题的单纯形法。此后，线性规划理论日趋成熟，应用也日益广泛和深入。线性规划在工业、农业、商业、交通运输业、军事、经济计划和生产经营等领域有着广泛的应用，并取得了良好的经济效益。