本文讲着重讲解线性规划,线性空间,行,列,系数的联系。
补充内容:如何使用matlab求解线性规划问题
小测验:
1.什么是统筹优化?
2.什么是线性规划?
在讲到工厂设计师如何使用Aspen PIMS家族软件设计现代化工厂前,让我们先复习一下高中知识:什么是统筹优化?试想一下生活中的常见例子(来自知乎@周鸿炜):
通常我们在解决上述问题时,并不会有无限的人力物,并且我们往往想追求某一个或多个特定指标的最大化。在这种受到约束的情况下,我们会使用统筹学的知识来解决这类问题。其中最简单的部分叫做线性规划(Linear Planning)。线性规划 (LP) 涉及尽可能地减少或增加受边界、线性等式和不等式约束的目标函数。
通过线性规划求解该问题,需明确线性规划模型的三要素:
(1)决策变量:需决策的量,即待求的未知数;
(2)目标函数:需优化的量,即欲达的目标,用决策变量的表达式表示;
(3)约束条件:为实现优化目标需受到的限制,用决策变量的等式或不等式表示
一般地, X 称为决策变量向量,C 称为价格系数向量, A 称为技术系数矩阵,b称为资源限制向量
在PIMS软件中,整个软件基于线性规划设计,决策变量作为列(Column)输入,约束条件作为行(row)输入,而目标函数作为内置函数OBJFN输入。
对于一些非线性情况,可以使用Recursion(迭代)或者 AO(Adavance Optimization)来解决。AO事实是Aspen公司自己写了一个新的NLP处理器用于解决可能的鞍部(局部最优)。
理解了线性规划求解这一基本思路,在之后,可以设计出更能符合用户需求的约束条件,并以合适的办法加入模型当中。
对于简单的线性问题,我们可以通过手算来解决。对于一些比较复杂的线性规划问题,我们可以使用三种算法:
内点法:采用原始-对偶预估-校正算法,尤其适合于具有特殊结构或可通过稀疏性矩阵定义的大规模问题。
动态序列法:最小化对动态序列(局部动态的约束子序列)每次迭代时的目标,直至得到解。
单纯形法:使用系统规划生成并测试线性规划的候选顶点解。单纯形算法是进行线性规划的最常用算法。
对于各种算法的具体数学推导,在此篇短文暂不介绍。可以参考Matlab的官方文档(https://cn.mathworks.com/help/optim/ug/linear-programming-algorithms.html#brnox30) 有非常详细的介绍。
Matlab规定线性规划的标准形式为:
几个不等式是问题的约束条件,记为 s.t.(即 subject to)。 MATLAB中求解线性规划的命令为:
[ x,fval ]=linprog(f,A,b)
[ x,fval ]=linprog(f,A,b,Aeq,beq)
[ x,fval ]=linprog(f,A,b,Aeq,beq,lb,ub)
其中:返回的x为决策向量的取值; 返回的fval是目标函数的最大值;f为价值向量;A和b对应的是线性不等式约束;Aeq和beq对应的是线性等式约束;lb和ub分别对应的是决策向量的下界向量和上界向量。