ExtendSim Discrete Rate LP技术详解

focuscon

' N$ G& o3 [, ^' u; E# @看看附件这篇文章会对ExtendSim LP技术理解更深一些。
先介绍求解LP问题最流行的技术----simplex method （单纯形法），供不太了解运筹学的朋友了解，先看看这个对读附件的文章大有帮助。
( C& i. n+ P8 x. h
+ E2 f# j3 V: T! p9 Y　　求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

: H0 b% s, ]: d0 ^  V6 e　　根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。

2 U" C) u/ k( s! a" ?/ E　　最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。
" i5 \) R( Y- \: j+ k) G! D7 m( s
+ T  W) @7 I$ l* b+ \: \; I5 e　　单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
5 r6 V' S7 @3 b9 r2 j
　　用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。

　　改进单纯形法
2 e0 c6 m/ K6 h7 \
　　原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。
# }! y% j6 G: U+ ]3 d  a/ k
　　对偶单纯形法

　　1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

　　数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。
' N2 u  D, Q+ h1 E
9 N' W# v- T( Q" k7 w　　这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

iesim

谢谢 小康。
: ~2 j1 K) `; M% I+ ^
我们大可不必把 ExtendSim 当中的 LP 技术想象得过于复杂。ExtendSim 是第一个将 LP 技术引入到 Discrete Rate 建模当中的仿真软件，主要目的是为了获得更准确的 流体速率。
0 Z& w$ ]  W9 V5 f
. f9 Z( U3 u( m还是打个比方。 假设有几幢居民楼，每个楼的总供水量是恒定的（通过楼顶水箱），如果落实到各家各户，每个家庭用水量在每个时刻可能会发生变化，为了计算每家管道中的流体速率，我们引入 LP 技术。但因为每个楼之间互不影响（假设），那么，LP 计算只要在每个楼之内展开就可以，这也就相当于 ExtendSim 首先要确定 LP 计算的范围。当范围确定后，引入 LP 的最主要目的是为了求得物料（这个例子中是水）的总物质平衡。

/ \, k5 X" z- A  h* y3 p( \在离散模型中，一个工件从一个地方到另外一个地方，隐含着这个工件数量没有变化，总的物质量是守恒的，因为我们不需要关心物料在物流网络或者制造网络中是否总物质量守恒，因为离散物件的本身特点很容易做到这一点。而 离散速率就不一样，水可以拆散。只有用到 LP 技术才能更准确地在总物质量守恒的约束下获得有效流速。

那么，在一个楼当中的 LP 问题，可以简单归结为
$ ~# s+ [  X: K1 L" v. F
目标：Max  有效流速
约束： 每个管道水量的总和恒定。

4 E7 p1 P+ N8 N2 ^这个问题可以用线性规划来建立。

focuscon

谢谢王老师！ 您这样通俗的一讲解让我又明白了不少
0 n; W  J' f" }) d% c& W我个人没有接受过运筹学训练，开始阅读手册时对有些概念理解不好，到了专门介绍LP的后面那一部分时才比较明白一点。（也幸亏几个月前看过几个介绍运筹学的PPT，有那么一丁点概念，不然就很迷糊了）这时我也更加佩服ExtendSim的手册了，这里面既有操作方法又有理论指导，基本不需要参考其他资料。不象其他软件的手册只是单纯的SOP。
, H8 U' g+ C0 v8 j; a) C" |( e手册里面总是提醒很多注意事项，很多地方都要“Caution”，在建模的时候也发现很容易出现错误（比如用Tank液位控制上下游的Valve时，有些设置会出现逻辑错误----阀门是关闭的但还是有流量通过），没有离散事件模型那么好把握，可能这一部分还不是很成熟，以后应该会升级完善吧。

xgjz2

王博士您好!离散制造企业的生产中也有许多需要LP解决的问题,能否把LP应用到离散事件建模中呢?有案例可以学习吗?谢谢!