第三讲 线性规划模型

数学建模 讲义 NUDT 2023SP

---

---

例：加工奶制品的生产计划

• 某加工厂用牛奶生产 $A_1$, $A_2$ 两种奶制品，1 桶牛奶可在甲类设备上用 12h 加工成 3kg的 $A_1$, 或者在乙类设备上用 8h 加工成 4kg 的 $A_2$.
• 根据市场需求，生产的 $A_1,\;A_2$ 全部能售出，且每千克可分别获利 24 元和 16 元.
• 现在该厂每天能得到 50 桶牛奶的供应，每天总的生产时间为 480 h.
• 为了保护设备，甲类设备每天至多能加工 100kg 的 $A_1$，乙类设备的加工能力没有限制.

---

试为该厂制订一个生产计划，使每天获利最大. 并进一步讨论以下问题：

1. 若用 35 元可以买到 1 桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？
2. 若可以聘用临时工人以增加生产时间，付给临时工人的时薪最多是多少？
3. 若每千克 $A_1$ 的获利增加到 30 元，是否需要改变生产计划？

---

3.1 数学规划

• 数学规划（Mathematical Programming）也称为 数学优化（Mathematical Optimization），或简称为 规划，是应用数学的一个重要分支，主要研究在特定情况下最大化或最小化某一特定函数或变量的问题.
• 数学规划问题的三要素：
  
  • 决策变量：可控制的自变量或者参数；
  • 目标函数：优化目标的定量刻画；
  • 约束条件：决策变量的取值范围或需要满足的条件.

---

规划问题的一般形式

$$\boxed{ \begin{array}{rll} & \min f(x) & \mbox{（目标函数）} \\ \mbox{s.t.} & h_i(x)=0,\ i=1,\ldots,m & \mbox{（等式约束条件）} \\ & g_j(x)\leqslant 0,\ j=1,\ldots,n & \mbox{（不等式约束条件）} \\ & x\in D \subset \mathbb{R}^n & x\mbox{ 为决策变量} \end{array}}$$

---

规划问题的相关概念

规划问题的本质是一个搜索问题，即在给定的参数（决策变量）取值范围内，寻找能够使得目标函数取到所需最值的点.

• 可行解： 满足约束条件的点；
• 可行域： 可行解的集合；
• 最优解： 使目标函数取得最优（最大、小）值的可行解.

---

规划问题按要素的分类

• 线性规划： 目标和约束均为线性函数或线性不等式
• 非线性规划： 目标或约束中存在非线性函数或非线性不等式
• 二次规划： 目标为二次函数，约束为线性的
• 整数规划： 决策变量全部或部分要求取值为整数
  
  • 整数线性规划、整数非线性规划、纯整数规划、混合整数规划、一般整数规划、0-1规划
• 随机规划： 某些决策变量是随机变量
• 动态规划： 可分解为多个较小子问题的优化问题
• 组合最优化： 可行解是离散的或可以转化为离散的问题
• 无限维最优化： 可行域是个无限维的集合

---

其他分类方法

• 根据模型中参数或决策变量是否具有不确定性，可以把规划问题分为确定性规划、不确定性规划（如随机规划、模糊规划等）；
• 根据目标和约束条件是否连续、是否可微，可以把规划问题分为 光滑优化、非光滑优化；
• 根据目标的多少，分成单目标规划、多目标规划等等.
• 不同类型的规划问题的求解难度和求解方法有很大的不同，所以搞清楚问题的类型，是十分必要的.

---

3.2 线性规划

线性规划问题的标准形式：

$$\boxed{ \begin{align*} \min\quad & z=\sum_{j=1}^n c_j x_j & \\ \mbox{s.t.}\quad & \sum_{j=1}^n a_{ij} x_j = b_i (\geqslant 0), & i=1,\ldots,m \\ & x_1, x_2, \ldots, x_n \geqslant 0 & \end{align*}}$$

• 注：任意线性规划问题都可以化为标准形式.

---

将线性规划问题化为标准形式

1. 目标函数标准化：$\max\ z=\min\ (-z)$
2. 约束条件标准化：
   
   • 在不等式约束 $\bbox[yellow]{a_{i1} x_1+a_{i2}x_2+\cdots+a_{in}x_n\leqslant b_i}$ 中引入松弛变量 $x_{n+1}$
   • 将其化为如下的等价形式：
     
     • $\bbox[lightgreen]{a_{i1} x_1+a_{i2}x_2+\cdots+a_{in}x_n+x_{n+1} = b_i,\ x_{n+1}\geqslant 0}$
3. 决策变量标准化：若 $x_j$ 无约束，可引入两个新变量 $x_j'$，$x_j''$，令 $\bbox[lightgreen]{x_j=x_j'-x_j''}$, 进而要求 $\bbox[lightgreen]{x_j',x_j''\geq 0}$.

---

线性规划的矩阵形式

从标准形式出发，可以将任意的线性规划写成写成矩阵形式，进一步简化描述.

$$\boxed{\begin{align*} \min\quad & z=\boldsymbol{c}^{\mathrm{T}}\boldsymbol{x} \\ \mbox{s.t.}\quad & \boldsymbol{A}\boldsymbol{x}=\boldsymbol{b} \\ & \boldsymbol{x}\geqslant \boldsymbol{0} \\ \end{align*}}$$

• 其中，一般要求 $\operatorname{rank}(\boldsymbol{A}_{m\times n})=m$，$(m<n)$.

---

线性规划的求解

• 解的性质：
  
  • 线性规划问题的可行域是一个凸多面体；
  • 线性规划问题如果存在最优解，则最优解必在可行域的顶点处达到.
• 常用算法：图解法，单纯形法（simplex method），内点算法（interior point method），表上作业法 等.
• 常用软件工具：Lingo, Matlab, Lp_solve, glpk 等.

---

例：加工奶制品的生产计划

• 决策变量：设每天 $x_1$ 桶牛奶用于生产 $A_1$，$x_2$ 桶用于生产 $A_2$.
• 目标函数：设每天获利为 $z$ 元，则 $z=72 x_1+64 x_2$.
• 约束条件：
  
  • 原料供应： $x_1+x_2\leqslant 50$
  • 劳动时间： $12 x_1+8 x_2\leqslant 480$
  • 设备能力： $3 x_1\leqslant 100$
  • 非负约束： $x_1\geqslant 0,\ x_2\geqslant 0$

---

优化模型

$$\begin{align} \max\quad & z=72 x_1+ 64 x_2 \\ \mbox{s.t.}\quad & x_1+x_2 \leqslant 50 \\ & 12 x_1+8 x_2\leqslant 480 \\ & 3 x_1\leqslant 100 \\ & x_1\geqslant 0,\ x_2\geqslant 0 \end{align}$$

• 隐含假设
  
  1. 两种奶制品的获利与各自的产量无关；
  2. 两种奶制品的获利与彼此的产量无关；
  3. 加工牛奶的桶数可以是任意实数，即决策变量可以连续变化.

---

图解法

• 目标函数中的 $z$ 取不同的值时，对应图中一组平行线，称为等值线族.
• 可以看出，当这族平行线向右上方移动到过 $B$ 点时，$z=3360$，达到最大值.
• 所以 $B$ 点的坐标 $(20, 30)$ 即为最优解：$x_1=20$, $x_2=30$.

---

几何解释

• 由于目标函数和约束条件都是线性函数，在 2 维情形，可行域为直线段围成的凸多边形，目标函数的等值线为直线.
• 因此，如果有最优解的话，最优解一定在凸多边形的某个顶点取得.
• 推广到 $n$ 维，可以证明，最优解会在约束条件所界定的一个凸多面体（可行域）的某个顶点取得.

---

软件求解

命令：lp_solve -S4 example1.txt

example1.txt 如下：

max: 72 x1 + 64 x2;
milk: x1 + x2 <= 50;
time: 12 x1 + 8 x2 <= 480;
cpct: 3 x1 <= 100;
x1 >= 0;
x2 >= 0;

---

运行结果

• 紧约束 也称为有效约束，指在最优解下，“资源”剩余为 0 的约束.
  
  • 在本例中，最优解对应的原料、劳动时间已用完，是紧约束，而甲类设备的加工能力有富余.
• 影子价格 紧约束的资源每增加一个单位，利润的增量.
  
  • 本例中牛奶增加 1 桶，利润增加 48 元，即 1 桶牛奶的影子价格为 48 元.
  • 类似的，1h 劳动时间的影子价格为 2 元，甲类设备的影子价格为0.

---

影子价格的应用

• 附加问题1第一问： 若 35 元可以买到 1 桶牛奶，应否作这项投资？
  
  • 答：用 35 元可以买到 1 桶牛奶，低于 1 桶牛奶的影子价格，应该做这项投资.
• 附加问题2第一问：若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？
  
  • 答：付给临时工人的工资应低于劳动时间的影子价格才能增加利润，因此工资最多不超过每小时 2 元.

---

对目标函数系数的敏感性分析

• 对目标函数系数变化的影响的讨论，称为对目标函数系数的 敏感性分析 (Sensitive Analysis).
  
  • 即，讨论当目标函数的系数发生变化时（假设约束条件不变），最优解和最优值的变化情况.
• 目标函数的系数决定了等值线族的斜率. 通常斜率在一定范围内变化时，最优解不变.

---

系数敏感性的应用

• 本例中，在最优解不变的前提下，$x_1$ 的系数的变化范围为 $(64, 96)$，$x_2$ 的系数的变化范围为 $(48, 72)$.
  
  • 注：以上范围是指同一时间只改变一个系数.
• 附加问题3： 由于市场需求变化，每千克 $A_1$ 的 获利增加到 30 元，是否需要改变生产计划？
  
  • 答：若每千克 $A_1$ 的获利增加到 30 元，则 $x_1$ 的系数变为 $30 \times 3 = 90$，在上述范围内，不需要改变生产计划.

---

对约束右端项敏感性分析

• 影子价格的作用是有限制的，对影子价格在什么条件下才有意义的讨论，通常称为对约束右端项的敏感性分析.
  
  • 本例中，牛奶最多增加到 60 桶，劳动时间最多增加到 533.3 小时.
• 附加问题 1 第 2 问： 若投资，每天最多购买多少桶？
  
  • 答：虽然应该用 35 元价格购买额外的牛奶，但是每天最多购买 10 桶；
  • 类似地，以低于 2元/h 的工资聘用临时工人以增加劳动时间，但最多增加 53.3 h.

---

单纯形法（Simplex Algorithm）

• 1947 年由 G.B. Dantzig 发明，是求解线性规划问题最常用的方法之一. 单纯形法常常也被称为 爬山法.

  1. 从可行域的某个顶点出发，在相邻顶点中寻找目标函数值更大的点；
  2. 不断重复，直到找到一个顶点，其周围的所有顶点对应的目标函数值都不大于该顶点，此时就得到了所求规划问题的最优解.

---

3.3 整数规划

决策变量取整数的线性规划称为 整数线性规划，形如：

$$\boxed{\begin{aligned} \min\quad & z=\sum_{j=1}^n c_j x_j & \\ \mbox{s.t.}\quad & \sum_{j=1}^n a_{ij} x_j = b_i (\geqslant 0), & i=1,2,\ldots,m \\ & x_j \geqslant 0, x_j\in \mathbb{Z}, & j=1,2,\ldots, n & \end{aligned}}$$

• 如果还要求 $x_j\in \{0,1\}$，则称为 0-1 规划.

---

整数线性规划的求解方法

• 分支定界法（branch and bound）：求解纯或混合整数线性规划.
• 割平面法（Cutting Plane Method）：求解纯或混合整数线性规划.
• 隐枚举法（Implicit Enumeration Method）：求解 0-1 整数规划，具体可分为过滤隐枚举法和分枝隐枚举法.
• 匈牙利法：主要用于解决指派问题（特殊的 0-1 规划问题）.
• 蒙特卡洛法（Monte Carlo method）：求解各种类型规划的随机方法.

---

分支定界法

1. 对最大化的整数规划问题 A，先不考虑整数约束，求解与之相应的线性规划问题 B.
2. 若 B 的最优解不符合 A 的整数条件，那么 B 的最优目标函数值必是 A 的最优目标函数值 $z^*$的上界，记作 $z_2$.
3. A 的任意可行解的目标函数值均是 $z^*$ 的一个下界，记为 $z_1$.
4. 分支定界法不断地将 B 的可行域分成子区域（分支），然后通过不断减小 $z_2$ 和增大 $z_1$，最终求得 $z^*$.

---

分支定界法的求解过程

例： 求解整数规划问题

$$(\boldsymbol{\mathrm{P_0}}):\;\boxed{\begin{array}{rl} \max & z=5x_1+8x_2\\ \mathrm{s.t.} & x_1+x_2\leq 6 \\ & 5x_1+9x_2\leq 45\\ & x_i\geq0,\;x_i\in\mathbb{Z},\;i=1,2. \end{array}}$$

---

---

---

---

计算结果

Lingo 代码

model:
max=5*x1+8*x2;
x1+x2<6;
5*x1+9*x2<45;
@gin(x1);
@gin(x2);
end

运行结果

Global optimal solution found.
Objective value: 40.00000
Variable Value
X1 0.000000
X2 5.000000

---

例：铁路平板车装货问题（MCM1988-B）

要把 7 种规格的包装箱 $C_1,..., C_7$ 装到 2 辆铁路平板车上去，包装箱的宽和高都是相同的，但是厚度及重量不同. 下表给出了各包装箱的厚度、重量及数量：

$$\begin{array}{c|c|c|c|c|c|c|c} \hline & C_1 & C_2 & C_3 & C_4 & C_5 & C_6 & C_7 \\ \hline t\text{(cm)} & 48.7 & 52.0 & 61.3 & 72.0 & 48.7 & 52.0 & 64.0 \\ \hline w\text{(kg)} & 2000 & 3000 & 1000 & 500 & 4000 & 2000 & 1000 \\ \hline \text{数量} & 8 & 7 & 9 & 6 & 6 & 4 & 8 \\ \hline \end{array}$$

---

• 每辆平板车有 10.2m 长的地方可以用来装箱（像摆面包片那样），载重为 40 t.
• 由于当地货运的限制，对于 $C_5$、$C_6$、$C_7$ 三类包装箱的有特定的约束，它们在每节车厢内所占的总空间（厚度）不得超过 302.7cm.
• 试建立数学模型将这些包装箱装到平板车上去，并使浪费的空间最小.

---

目标函数

• 总重量（89t）和总厚度（27.5m）都超过了两辆车的最大限量（80t 和 20.4m），要求浪费最小，即指装载量最大（满足要求的条件下）.
• 令 $x_{ij}$ 表示第 $i$ 辆车装 $C_j$ 类箱子的个数，$i=1,2;\ j=1,\ldots, 7$.
• 目标函数：
  
  • $\max \sum\limits_{i=1}^2 (0.487 x_{i1}+0.52 x_{i2}+0.613 x_{i3}+0.72 x_{i4}+0.487 x_{i5}$
    
    • $\qquad +0.52 x_{i6}+0.64 x_{i7})$

---

约束条件

• 重量约束：
  
  • $2 x_{i1}+3 x_{i2}+x_{i3}+0.5 x_{i4}+4 x_{i5}+2 x_{i6}+x_{i7}\leqslant 40,\ i=1,2$
• 厚度约束：
  
  • $0.487 x_{i1}+0.52 x_{i2}+0.613 x_{i3}+0.72 x_{i4}+0.487 x_{i5} +0.52 x_{i6}$
    
    • $+0.64 x_{i7}\leqslant 10.2, \ i=1,2$

---

• 数量约束：$\begin{cases} x_{11}+x_{21} \leqslant 8 \\ x_{12}+x_{22} \leqslant 7 \\ x_{13}+x_{23} \leqslant 9 \\ x_{14}+x_{24} \leqslant 6 \\ x_{15}+x_{25} \leqslant 6 \\ x_{16}+x_{26} \leqslant 4 \\ x_{17}+x_{27} \leqslant 8 \\ \end{cases}$
• 特殊约束：$0.487 x_{i5}+0.52 x_{i6}+0.64 x_{i7}\leqslant 3.027 \qquad i=1,2$
• 整数约束：$x_{ij}\geqslant 0,\quad x_{ij}\in \mathbb{Z},\quad i=1,2;\ j=1,2,\ldots,7$

---

$$\max \sum\limits_{i=1}^2 (0.487 x_{i1}+0.52 x_{i2}+0.613 x_{i3}+0.72 x_{i4} +0.487 x_{i5}+0.52 x_{i6}+0.64 x_{i7})$$

$$\mbox{s.t.} \left\{\begin{array}{ll} 2 x_{i1}+3 x_{i2}+x_{i3}+0.5 x_{i4}+4 x_{i5}+2 x_{i6}+x_{i7}\leqslant 40 & i=1,2 \\ 0.487 x_{i1}+0.52 x_{i2}+0.613 x_{i3}+0.72 x_{i4}+0.487 x_{i5} & \\ +0.52 x_{i6}+0.64 x_{i7}\leqslant 10.2 & i=1,2 \\ x_{11}+x_{21} \leqslant 8 \\ x_{12}+x_{22} \leqslant 7 \\ x_{13}+x_{23} \leqslant 9 \\ x_{14}+x_{24} \leqslant 6 \\ x_{15}+x_{25} \leqslant 6 \\ x_{16}+x_{26} \leqslant 4 \\ x_{17}+x_{27} \leqslant 8 \\ 0.487 x_{i5}+0.52 x_{i6}+0.64 x_{i7}\leqslant 3.027 & i=1,2 \\ x_{ij}\geqslant 0,\quad x_{ij}\in \mathbb{Z},\quad &i=1,2;\ j=1,2,\ldots,7 & \end{array}\right.$$

---

3.4 0-1规划

决策变量取值为 0 或 1 的线性规划称为 0-1规划，模型形如：

$$\boxed{\begin{align*} \min\quad & z=\sum_{j=1}^n c_j x_j & \\ \mbox{s.t.}\quad & \sum_{j=1}^n a_{ij} x_j = b_i, & i=1,2,\ldots,m \\ & x_j \in\{0,1\}, & j=1,2,\ldots, n & \end{align*}}$$

---

例：背包问题

• 为了准备旅行的必须用品，要在背包内装一些最有用的东西，但最多只能装 $b$ 公斤的物品，而每件物品只能整个携带.
• 为此旅行者给每件物品规定了一个“价值”以表示其有用的程度，如果共有 $n$ 件物品，第 $j$ 件物品重 $a_j$ 公斤，其价值为$c_j$.
• 问：在携带的物品总重量不超过 $b$ 公斤的条件下，携带哪些物品可使总价值最大?

---

例：选课问题

• 某大学规定某专业学员毕业时至少修过 3 门数学课，2 门运筹学课和 2 门计算机课.
• 给定这些课程的编号及信息如右表所示.
• 问：达到毕业要求并使选课门数最少的选课策略是什么？

$$\begin{array}{ccccc}\hline 课程编号 & 课程名称 & 学分 & 类别 & 先修课 \\ \hline 1 & 高等数学 & 5 & 数学 & \\ 2 & 数学建模 & 4 & 数学 & 高等数学，运筹学引论 \\ 3 & 最优化方法 & 4 & 数学，运筹 & 高等数学，运筹学引论 \\ 4 & 数据结构 & 3 & 数学，计算机 & 计算机编程 \\ 5 & 运筹学引论 & 4 & 数学，运筹 & 高等数学 \\ 6 & 计算机模拟 & 3 & 计算机，运筹 & 计算机编程 \\ 7 & 计算机编程 & 2 & 计算机 & \\ 8 & 决策理论 & 2 & 运筹 & 运筹学引论 \\ 9 & 数学实验 & 3 & 数学、计算机 & 高等数学，数学建模 \\ \hline \end{array}$$

---

分析：

• 设 $x_i=1$ 或 $0$ 分别表示是否选择编号为 $i$ 的课程.
• 希望选课门数最少，即：$\min\ z = \sum_{i=1}^9 x_i$.
• 约束条件包括以下几类：
  
  • 数学课程不少于 3 门： $\sum_{i=1}^5 x_i+x_9 \geqslant 3$
  • 运筹学课程不少于 2 门： $x_3+x_5+x_6+x_8 \geqslant 2$
  • 计算机课程不少于 2 门： $x_4+x_6+x_7+x_9 \geqslant 2$

---

• 课前先后关系： `先修课对应的变量取值一定要大于等于后修课的.
• 例如：若 $x_2=1$（数学建模），则必有 $x_1=1$（高等数学） 且 $x_5=1$（运筹学引论）.
• 类似的约束包括：
  
  • $x_1\geqslant x_2,\ x_5\geqslant x_2,\ x_1\geqslant x_3,\ x_5\geqslant x_3,\ x_7\geqslant x_4,$
  • $x_1\geqslant x_5,\ x_7 \geqslant x_6,\ x_5\geqslant x_8,\ x_1\geqslant x_9,\ x_2\geqslant x_9$.
• 0-1要求： $x_i\in\{0,1\},\ i=1,2,\ldots, 9$.

---

LINGO 求解

Global optimal solution found.
Objective value:  5.000000
Variable      Value      
X( 1)        1.000000
X( 2)        0.000000
X( 3)        0.000000
X( 4)        1.000000
X( 5)        1.000000
X( 6)        1.000000
X( 7)        1.000000
X( 8)        0.000000
X( 9)        0.000000

• 解得，达到毕业要求，并且课程门数最少的选课方案为：高等数学、数据结构、运筹学引论、计算机模拟、计算机编程.
• 若要求数学建模是必选课，即 $x_2=1$，则新要求下的最优解为：高等数学、数学建模、运筹学引论、计算机模拟、计算机编程.
• 最优值唯一，但是最优解不一定唯一.

---

例：指派问题

• 分配 $n$ 人去做 $n$ 项工作，每人做且仅做一项工作.
• 若分配第 $i$ 人去做第 $j$ 项工作，需花费 $c_{ij}$ 个单位的时间.
• 问应如何分配工作才能使工人花费的总时间最少？

---

• 引入变量 $x_{ij}$，若分配 $i$ 做 $j$ 工作，则取 $x_{ij} =1$，否则取 $x_{ij}=0$.
• $\min \; z=\sum_{j=1}^n {\sum_{i=1}^n {c_{ij} x_{ij} } }$，$\mbox{s.t.}\left\{ {\begin{array}{l} \sum\limits_{j=1}^n {x_{ij} =1} ,i=1,2,\ldots ,n \\ \sum\limits_{i=1}^n {x_{ij} =1} ,j=1,2,\ldots ,n \\ x_{ij} \in\{0,1\},\ \ i,j=1,2,\ldots,n \end{array}} \right.$
• 指派问题是一类特殊的 0-1 规划问题（可以转化为特殊的运输问题），通常使用由匈牙利数学家 D.Konig 提出的 匈牙利算法 求解.

---

3.5 综合案例：飞行调度问题（MCM-1989B）

• 机场通常按"先来先走"的原则分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道队伍.
• 假设控制中心可以从快速联机数据库中得到每架飞机的如下信息：预定离开登机口的时间；实际离开登机口的时间；机上乘客人数；预定在下一站转机的人数和时间；到达下一站的预定时间.
• 又设飞机有 7 种型号，载客量从 100 人起以 50 人递增，乘客最多 400 人.
• 设计一种能使乘客和航空公司双方满意的数学模型.

---

• 假设机场只有一条跑道供起飞使用，且每架飞机起飞占用的跑道时间为 $d$，则 $n$ 架飞机的起飞时间可分为 $n$ 个时间窗口：
  
  • $[0,d),[d,2d),\ldots,[(n-1)d,nd]$.
• 乘客不满意主要由于飞机晚点而耽误行程，而航空公司不满意主要由于飞机晚点而蒙受损失.
• 定义 $c_{ij}$ 为第 $i$ 架飞机在第 $j$ 个时间窗口起飞而导致的乘客和航空公司损失费用之和.
• 令 $x_{ij}=\left\{\begin{array}{ll} 1, & \text{第}i\text{架飞机在窗口}[(j-1)d,jd)\text{起飞} \\ 0, & \mbox{其他} \end{array}\right.$
• 该问题可以视为为每架飞机指派时间窗口的指派问题（0-1规划问题）.

---

分析：

• 目标函数： $\min\ z=\sum_{j=1}^n \sum_{i=1}^n c_{ij} x_{ij}$
• 约束条件：
  
  • 一个时间窗口只能有一架飞机起飞： $\sum_{i=1}^n x_{ij} = 1,\ j=1,2,\ldots,n$
  • 一架飞机只能分配一个时间窗口起飞： $\sum_{j=1}^n x_{ij} = 1,\ i=1,2,\ldots,n$
  • 0-1 约束：$x_{ij}\in \{0,1\},\ i,j=1,2,\ldots,n$.

---

损失的建模

• 损失通常由三部分构成：晚点导致的燃油附加费、转机乘客的误机赔偿、乘客不满意导致的额外损失.
• 晚点导致的燃油附加费： $F_i(t)=\left\{\begin{array}{lc} 0, & t\leqslant 0 \\ k_i t, & 0<t<\tau_i \\ k_i \tau_i, & t\geqslant \tau_i \end{array}\right.$
  
  • $k_i$ 为航班对应的单位时间赔偿；晚点时间超过阈值 $\tau_i$（例如：12 小时），则改为定额而不再按时间赔偿.

---

• 转机乘客的误机赔偿： $R_i(t)=wQ_i H(t-\tau_i)$，
  
  • 其中$w$为赔偿费，$Q_i$为转机人数，$H$为 0-1函数（自变量大于零时取 1，否则取 0）.
• 乘客不满意导致的额外损失： $D_i(t) = a(e^{\alpha t}-1)P_i+bQ_i H(t-\tau_i)$，
  
  • 其中 $P_i$ 为总人数，$a$，$b$为将不满意度折算为费用的折算系数，$\alpha$ 为调节指数函数形状的参数.
• 总损失： $c_{ij}=F_i(t)+R_i(t)+D_i(t)$.

---

计算求解

• 假设早上 6 点有 3 架飞机同时要求起飞，机型、飞行距离相同，计划到达时间均为 7:20，乘客数分别为 350，100，400，每架飞机上有 100 人要转机.
• 设起飞时间窗口长度为 1 分钟，同时为简化问题，将费用中的参数均设为 1.
• 系数矩阵：$C=\begin{bmatrix} 0 & 802.40 & 2437.17 \\ 0 & 372.83 & 839.91 \\ 0 & 888.31 & 2756.62 \\ \end{bmatrix}$
  
  • 问题的最优解 $z^*=\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}$

---

小结：规划问题建模注意事项

• “三要素” 是核心，围绕三要素进行建模；
• 尽量使用实值变量，减少整数约束和整数变量；
• 尽量使用光滑约束，减少非光滑约束的个数；
  
  • 如：尽量少使用绝对值、符号函数、多个变量求最大（小）值、四舍五入、取整函数等
• 尽量使用线性模型，减少非线性模型约束和非线性变量的个数；（如 $x/y<5$ 可改为 $x<5y$）
• 合理设定变量上、下界，尽可能给出变量的初始值；
• 模型中使用的参数数量要适当.（如小于 $10^3$）

---

课后思考

• ($\star\star\star$) 某银行经理计划用一笔资金进行有价证券的投资，可供购进的证券以及其信用等级、到期年限、收益如下表所示.
• 按照规定，市政证券的收益可以免税，其他证券的收益需按 50% 的税率纳税.
• 此外还有以下限制：
  
  1. 政府及代办机构的证券总共至少要购进 400 万元；
  2. 所购证券的平均信用等级不超过 1.4（信用等级数字越小，信用程度越高）；
  3. 所购证券的平均到期年限不超过 5 年.

---

$$\begin{array}{ccccc} \hline 证券名称 & 证券种类 & 信用等级 & 到期年限 & 到期税前收益\% \\ \hline A & \text{市政} & 2 & 9 & 4.3 \\ B & \text{代办机构} & 2 & 15 & 5.4 \\ C & \text{政府} & 1 & 4 & 5.0 \\ D & \text{政府} & 1 & 3 & 4.4 \\ E & \text{市政} & 5 & 2 & 4.5 \\ \hline \end{array}$$

问：1) 若该经理有 1000 万元资金，应如何投资？ 2）如果能够以 2.75% 的利率借到不超过 100 万元资金，该经理应如何操作？