规划数学建模 2 - 非线性规划（01 规划、整数规划、动态规划）

术语解释

• 整数规划：规划中的变量（全部或部分）限制为整数，称为整数规划。（很多的单位是不能拆分成小数的）
• 0-1规划：决策变量仅取值0或1的异类特殊的整数规划。（决策变量要么取0，要么取1）（可以解决快递员问题、协作效率最优化问题、解决流程化问题效果很多好）
• 非线性规划：目标函数或约束条件中至少有一个是非线性函数的最优化问题。
• 多目标规划：研究多于一个目标函数在给定区域上的最优化。
• 动态规划：是运筹学的一个分支，是求解决策过程最优化的数学方法。

整数规划及0-1规划模型

概述

• 首先0-1其实也是整数规划。
• 整数规划指的是决策变量为非负整数值的一类线性规划。
• 在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法。
• 在整数规划问题中，0-1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0-1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。

例题1：原油采购与加工

目标：你现在要使收益最大，如何安排原油的采购和加工。

• 市场上可买到不超过1500t的原油A：
• 购买量不超过500t时的单价为10000元/t；
• 购买量超过500t但不超过1000t时，超过500t的部分8000元/t；
• 购买量超过1000t时，超过1000t的部分6000元/t.

问题分析：

• 利润：销售汽油的收入-购买原油A的支出。
• 难点：原油A的购价与购买量关系复杂。
• 决策变量：支出 = 原油A的购买量
  
• $Max=4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})-c(x)$
• c(x)~购买原油A的支出
• $$c(x)=\{\begin{array}{ll}10x& (0\le x\le 500)\\ 8x+1000& (500\le x\le 1000)\\ 6x+3000& (1000\le x\le 1500)\end{array}$$
• 原油供应
• $x_{11}+x_{12}\le 500+x$ 库存500t
• $x_{21}+x_{22}\le 1000$ 库存1000t
• $x\le 1500$不能卖超过1500
• $\frac{x_{11}}{x_{11}+x_{21}}\ge 0.5$，A要大于50%。
• $\frac{x_{12}}{x_{12}+x_{22}}\ge 0.6$，B要大于60%。
• 目标函数c(x)不是线性函数，是非线性规划。
• 对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解。

模型求解

• $x_1,x_2,x_3$以价格10，8，6（千元/t）采购A的吨数。这对于任何一种情况都成立。
• 于是有$x=x_1+x_2+x_3,c(x)=10x_1+8x_2+6x_3$
• $Max=4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})-10x_1+8x_2+6x_3$
• 然而只有当$x_1=500$的时候，$x_2$才能有值，同理当$x_1+x_2\ge 1000x_2=500$时，$x_3$才能有值
• 所以约束等价于$(x_1-500)\ast x_2=0$【这个太牛逼了】
• 同理$(x_2-500)x_3=0$
• $0\le x_1,x_2,x_3\le 500$

求解代码

Model:
Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3;
x11+x12 < x + 500;
x21+x22 < 1000;
x11 - x21 > 0;  
2*x12 - 3*x22 > 0;
x=x1+x2+x3;     
(x1 - 500) * x2=0; 
(x2 - 500) * x3=0; 
x1 < 500;
x2 < 500;
x3 < 500;
end 

最终结果

 Local optimal solution found.
  Objective value:                            4800.000
  Total solver iterations:                          14
     Variable           Value        Reduced Cost
            X11        500.0000            0.000000
            X21        500.0000            0.000000