【运筹学】目标函数、决策变量和约束条件分别是什么？

前言

如何安排配送路线，才能减少车辆的行驶距离？如何分配生产任务，才能在有限资源下获得更高收益？这些问题都需要我们在一定规则和资源限制下，从多种方案中作出选择。运筹学中的数学优化，就是通过建立模型，寻找符合要求的最佳方案。
一个基本的优化模型通常包含三个要素：决策变量、目标函数和约束条件。它们分别回答需要确定什么、希望什么最好和必须满足什么。本文将逐一介绍这三个概念，并借助简单的配送例子，说明它们如何共同描述一个优化问题。

1. 决策变量

决策变量是优化模型中需要通过求解来确定的选择或数量。建立模型时，首先要明确：我们可以作出哪些决策？

以车辆配送为例：
客户的位置和需求量已经给定，但车辆按什么顺序访问客户、经过哪些路段，还需要安排。这些需要确定的内容，可以用决策变量表示。
例如，用下面的变量表示车辆是否从一个地点直接驶向另一个地点：

x i j = { 1 , 车辆从地点 i 直接驶向地点 j 0 , 否则 x_{ij} = \begin{cases} 1, & \text{车辆从地点 } i \text{ 直接驶向地点 } j \\ 0, & \text{否则} \end{cases}xij​={1,0,​车辆从地点i直接驶向地点j否则​

这种只能取0或1的变量，称为0-1决策变量。

决策变量需要与参数区分。参数是在当前模型中作为已知条件给定的数据，例如客户需求量、车辆容量和地点之间的距离；决策变量则表示我们要在这些条件下确定的选择或数量。

2. 目标函数

目标函数是用来评价不同方案优劣的数学表达式。建立优化模型时，我们需要先明确：希望通过优化达到什么目标。

以车辆配送为例，如果我们希望车辆行驶的总距离尽可能短，就可以把所有车辆经过的路段距离加总，得到总行驶距离。设车辆从地点i ii行驶到地点j jj的距离为d i j d_{ij}dij​，决策变量x i j x_{ij}xij​表示车辆是否经过这一路段，那么总行驶距离可以表示为：

min ⁡ Z = ∑ i ∑ j d i j x i j \min Z=\sum_{i}\sum_{j}d_{ij}x_{ij}minZ=i∑​j∑​dij​xij​

其中：

• Z ZZ表示总行驶距离；
• d i j d_{ij}dij​表示地点i ii和地点j jj之间的距离；
• x i j x_{ij}xij​表示车辆是否从地点i ii行驶到地点j jj；
• m i n minmin表示希望让目标函数的取值尽可能小。

这里的“总行驶距离最短”就是这个配送问题的优化目标。根据研究问题的不同，目标函数也可以表示总运输成本最低、总配送时间最短、车辆使用数量最少，或者配送收益最大等。

需要注意的是，目标函数只有在明确优化方向后才完整。同一个问题可以有不同的目标，建立模型前需要先明确：究竟要按照什么标准评价方案。

3. 约束条件

约束条件是优化模型中必须遵守的规则和限制。它规定了哪些方案可以被接受，哪些方案不能被接受。

仍以车辆配送为例，车辆需要为所有客户提供服务，每个客户都不能被遗漏。同时，车辆的装载量有限，分配给一辆车的货物总量不能超过它的最大容量。此外，车辆通常需要从配送中心出发，完成配送后再返回配送中心。
如果客户集合记为N NN，客户j jj是否被车辆服务可以用决策变量表示，那么“每个客户都必须被服务一次”可以抽象地写成：

∑ i x i j = 1 , ∀ j ∈ N \sum_i x_{ij}=1,\quad \forall j\in Ni∑​xij​=1,∀j∈N
这里的含义是，对于每一个客户j jj，所有可能进入该客户的路线加起来必须等于1。也就是说，客户j jj要被服务一次，不能被遗漏，也不能被重复服务。

在实际问题中，约束条件往往不只有一个。
满足所有约束条件的方案，称为可行解。约束条件的作用，是把现实中的业务规则、资源限制和运行要求转化为模型必须遵守的数学条件。

4. 三者如何共同构成优化模型？

决策变量、目标函数和约束条件并不是三个相互独立的概念，而是共同组成一个完整的优化模型。

以车辆配送问题为例：

• 决策变量回答车辆应该怎么走
• 目标函数回答什么样的方案更好
• 约束条件回答哪些方案可以被接受

将这三部分结合起来，可以得到一个简单的优化模型：

min ⁡ Z = ∑ i ∑ j d i j x i j s.t. ∑ i x i j = 1 , ∀ j ∈ N , x i j ∈ { 0 , 1 } . \begin{aligned} \min \quad & Z=\sum_i\sum_j d_{ij}x_{ij} \\ \text{s.t.}\quad & \sum_i x_{ij}=1,\quad \forall j\in N,\\ & x_{ij}\in\{0,1\}. \end{aligned}mins.t.​Z=i∑​j∑​dij​xij​i∑​xij​=1,∀j∈N,xij​∈{0,1}.​

其中，第一行是目标函数，表示让总行驶距离最短；后面的条件是约束条件，表示每个客户都需要被服务；最后的条件规定决策变量只能取0或1。

用一句话概括，优化模型就是：在满足约束条件的所有可行方案中，寻找使目标函数达到最优的决策变量取值。

后记

决策变量、目标函数和约束条件，是优化模型中三个最基本的组成部分。
建立优化模型的过程，就是把现实问题转化为这三个部分：先明确需要决定什么，再确定希望达到的目标，最后列出方案必须满足的条件。在满足约束条件的所有可行解中，找到使目标函数达到最优的方案，就是优化问题要解决的事情。