三个基础概念前言1. 决策变量2. 目标函数3. 约束条件4. 三者如何共同构成优化模型后记前言如何安排配送路线才能减少车辆的行驶距离如何分配生产任务才能在有限资源下获得更高收益这些问题都需要我们在一定规则和资源限制下从多种方案中作出选择。运筹学中的数学优化就是通过建立模型寻找符合要求的最佳方案。一个基本的优化模型通常包含三个要素决策变量、目标函数和约束条件。它们分别回答需要确定什么、希望什么最好和必须满足什么。本文将逐一介绍这三个概念并借助简单的配送例子说明它们如何共同描述一个优化问题。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}minZi∑​j∑​dij​xij​其中Z ZZ表示总行驶距离d i j d_{ij}dij​表示地点i ii和地点j jj之间的距离x i j x_{ij}xij​表示车辆是否从地点i ii行驶到地点j jjm 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.​Zi∑​j∑​dij​xij​i∑​xij​1,∀j∈N,xij​∈{0,1}.​其中第一行是目标函数表示让总行驶距离最短后面的条件是约束条件表示每个客户都需要被服务最后的条件规定决策变量只能取0或1。用一句话概括优化模型就是在满足约束条件的所有可行方案中寻找使目标函数达到最优的决策变量取值。模型要素要回答的问题以配送问题为例决策变量需要确定什么车辆经过哪些路段目标函数希望什么最好总行驶距离尽可能短约束条件必须满足什么客户服务后记决策变量、目标函数和约束条件是优化模型中三个最基本的组成部分。建立优化模型的过程就是把现实问题转化为这三个部分先明确需要决定什么再确定希望达到的目标最后列出方案必须满足的条件。在满足约束条件的所有可行解中找到使目标函数达到最优的方案就是优化问题要解决的事情。