**Instructor** 谈之奕（谈神）
**Time** Spring & Summer, 2022
数学建模不是纯数学，而是应用数学，根本目的不是给出严谨的数学推导，而是指导解决实际问题。有些理论上的细节搞不明白不要死磕，能知道相应的数学或者计算机工具怎么用就是好样的。要学会充分利用开源的工具，知道哪些事情可以由其他人帮你完成是很重要的（陈越姥姥说的）！
数学建模有很多前人总结好的模型，它们是可以程式化求解的，但是每个问题的实际情况又都有些差别，不可能用一个模型完美解决所有问题。我们要在选择最恰当的模型的同时，作出一些技巧性的修改，从而得到一个和实际情况较符合且可以用较小的代价求解的数学模型。

一、数学规划

若干个变量满足一些等式或不等式的限制的条件下，使一个或多个目标函数取得最大值或最小值的问题，称为数学规划问题。数学规划（Mathematical Programming）就是研究规划问题的数学性质、求解算法的设计与实现的一门学科。
数学规划问题的一般形式：

称为目标函数，称为不等式约束，称为等式约束，称为变量取值范围约束。
满足所有约束条件和取值范围约束的决策变量（或者合并成决策向量）称为可行解，全体可行解构成的集合叫做可行域，能让目标函数在可行域内达到最优的可行解叫做最优解，最优解对应的目标函数值称为最优值。
目标函数为线性函数，约束条件为线性等式或不等式的数学规划问题叫做线性规划，其中任意一个条件变成非线性的就叫非线性规划。目标函数为二次函数，约束条件为线性等式或不等式的非线性规划叫做二次规划。如果约束条件也是二次的，叫做带二次约束的二次规划。至少有一个决策变量限定取整数值的叫做整数规划，其中部分决策变量取整数值的叫做混合整数规划，所有变量都只能取0或1中一者的叫做0-1规划。
线性规划的一般方法是单纯形法和内点法。单纯形法是求解规模较小的线性规划的有效算法，可以准确求解，但最坏时间复杂度是指数级的。内点法是现在许多线性规划默认使用的方法，是一个相对精确求解的多项式时间算法。
整数规划一般是NP-hard的，尚不存在多项式时间算法，最常用的方法是分支定界法及其衍生方法。
非线性规划是个非常困难的课题，只有极少数非线性规划可求出解析解，部分非线性规划问题存在有效的数值算法，剩下的数学家们还在研究。
数学建模竞赛中，我们一般用数学软件去解数学规划问题。Python 中有很多对应的库可以用，还有 LINGO 这个专业解线性规划问题的商业软件可以用，如果不介意把约束写成矩阵的话用 Mathematica 或 MATLAB 也行。

1.1 食谱问题

问题的一般形式：
在市场上可以买到 n 种不同的食品，第 j 种食品的单价是 cj 。人需要 m 种基本营养成分，一人一天需要摄入第 i 种营养成分 bi 个单位。每单位第 j 种食物包含第 i 种营养成分 aij 个单位。在满足人体营养需求的前提下，如何寻找最经济的配食物方案？
决策变量：食谱中第 j 种食物的数量为 xj 个单位，j=1, 2, … , n
目标函数：所有食物费用之和
约束条件：

1. 满足人体营养需求。xj 个单位的第 j 种食物中含第 i 种营养成分 aijxj 个单位，所以人摄入的第 i 种营养成分的总量为，要满足人体需要就是其摄入量≥bi
2. 摄入食物量非负。xj ≥ 0

写成数学规划的一般形式：

也可以整理成矩阵形式（黑体字表示向量）：
设 x = ( x1 , x2 , … , xn )T，A = ( aij )m×n，c = ( c1 , c2 , … , cn ), b = ( b1 , b2 , … , bn )T。

c = {4, 2, 3};
b = {4, 11};
A = MatrixForm[{{2, 0, 2}, {4, 3, 1}}];
LinearProgramming[c, A, b]

MODEL:
sets:
  nut/1..2/: b; !nut代表营养成分（nutrition）;
  food/1..3/: c, x; !两个1×3矩阵用来存放食品的单价和数量;
  cost(nut, food): A; !用来记录每种食物含有每种营养成分的量;
endsets
data:
  c = 4 2 3;
  b = 4 11;
  A = 2 0 2 4 3 1;
enddata
min = @sum(food(j):c(j)*x(j))
@for(nut(i): @sum(food(j): A(i, j)*x(j)>b(i));
END

可见 LINGO 代码长且语法严格，但可理解性更好，不用写成矩阵。

1.2 用0-1变量将分段函数转化为线性规划

大致思路是定义辅助0-1变量，让不需要的那一部分乘上0。
一家企业开工一天需支付固定成本 a，开工后生产一件产品的单位成本为 b，该企业在一天内生产 x 件产品的总成本为分段函数
定义，则有，但这样 y 还是分段表示的。
改进为用 x ≥ y 和 My ≥ x （M表示某个充分大的数，在具体题目中表示 x 的上界）两个约束条件来约束0-1变量 y，和上面对 y 的定义是等价的。这样分段问题就成了一般的线性规划问题。

1.3 运输问题

问题的一般形式：
某货物有 m 个产地，第 i 个产地的产量为 ai ；有 n 个销地，第 j 个销地的销量为 bj 。从第 i 个产地到第 j 个产地的运输单价为 cij 。假如要产销平衡，如何调运货物才能使总运输费用最小？
决策变量：xij 表示从产地 i 调运到销地 j 的货物量。
写成数学规划的一般形式：

也可以整理成矩阵形式用Mathematica解，只不过麻烦一点。

1.4 背包问题

问题的一般形式：
现有 n 件物品，物品 j 的价值为 pj ，大小为 wj ，背包容量为 C。选择若干物品放入背包，在放入背包物品大小之和不超过背包容量的前提下，如何使放入背包的物品价值之和尽可能大？
决策变量：, j = 1, 2, … , n
写成数学规划的一般形式：

1.5 指派问题

问题的一般形式：
现有 n 项任务和 n 位员工，员工 i 完成任务 j 所需时间为cij 。如何将任务与员工一一对应，可使完成所有任务所用总时间最少？
决策变量：, i, j = 1, 2, … , n

1.6 下料问题

给定生产一批产品所需的某种材料的大小与数量列表，例如有 W 米长的钢管若干，生产某产品需要wi 米长的钢管 bi 根，i = 1, 2, … , k，如何截取浪费的边角料最少？