浙大城院数学建模5

第五章、优化模型

§5.1线性规划模型§5.2运输问题§5.3库存问题§5.4最佳捕鱼方案§5.5森林救火费用最小问题1/31/20231MCM§5.5森林救火费用最小问题§5.6光学中的折射原理§5.7身体结构得优化1/31/20232MCM

经济管理和科学研究等领域中经常会遇到的问题类型之一。在很多情况下，我们会凭经验解决面临的优化问题，这样做看似有效，风险也较小，但决策时常常会融入太多决策者的主观臆断，因而无法保证结果的最优性。那么，是否一定要做大量的试验来探索最优方案呢？前言：

最优化方法是数学学科中的一个应用性很强的分支，它包含的内容十分广泛，有数学规划（如线性规划、非线性规划、二次规划、目标规划、多目标规划等）、库存论、排队论、博弈论、组合优化（离散优化）、随机规划等等。

1/31/20233MCM§5.1线性规划模型

线性规划（LinearProgramming,简记LP）是数学规划的一个重要组成部分。自从1947年G·B·Dantzig提出求解线性规划的单纯形法以来，线性规划在理论上日趋成熟，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。

1/31/20234MCM

某厂生产甲、乙两种产品，每单位产品销售后的利润分别为4千元与3千元。生产甲产品需用A、B两种机器加工，每单位产品的加工时间分别为2小时和1小时；生产乙产品需用A、B、C三种机器加工，每单位产品的加工时间为每台机器各一小时。若每天可用于加工这两种产品的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应当生产甲、乙两种产品各多少，才能使总利润最大？

例5.1（线性规划的实例）1/31/20235MCM例5.1的数学模型设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1、x2应满足：(5.1)

4x1+3x2表示生产x1单位甲产品和x2单位乙产品的总利润，被称为问题的目标函数。中的几个不等式是问题的约束条件，记为S.t。由于式中的目标函数与约束条件均为线性函数，故被称为线性规划问题。1/31/20236MCM

线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有（称没有非负约束的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为线性规划的标准形式(5.2)1/31/20237MCM或更简洁地，利用矩阵与向量记为(5.3)其中C和x为n维列向量，b为m维列向量，b≥0，A为m×n矩阵，m<n且rank(A)=m。1/31/20238MCM

如果根据实际问题建立起来的线性规划问题并非标准形式，可以将它如下化为标准形式：（1）若目标函数为maxz=CTx，可将它化为

min－z=－CTx

（2）若第i个约束为ai1x1+…+ainxn≤bi，可增加一个松驰变量yi，将不等式化为ai1x1+…+ainxn+yi

=bi，且yi≥0。若第i个约束为ai1x1+…+ainxn≥bi，可引入剩余量yi，将不等式化为ai1x1+…+ainxn－yi

=bi，且yi≥0。（3）若xi为自变量，则可令，其中、≥01/31/20239MCM例如，例5.1并非标准形式，其标准形式为(5.4)1/31/202310MCM

为了了解线性规划问题的特征并导出求解它的算法，我们先应用图解法来求解例5.1。满足线性规划所有约束条件的点被称为问题的可行点（或可行解），所有可行点构成的集合被称为问题的可行域，记为R。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们就得到了一族平行直线（见图5-1）。

线性规划的图解法1/31/202311MCM图5-1

（注：）对于例5.1，等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，例5.1的最优解为x*=(2,6)T，最优目标值z*=26。1/31/202312MCM（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”，（注：我们称这种“顶点”为极点）。

从上面的图解过程可以看出并不难证明以下断言：（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时必定是若干个半平面的交集（除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。1/31/202313MCM上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维空间中，满足某一线性等式aix=bi的点集被称为一个超平面，而满足某一线性不等式aix≤bi（或aix≥bi）的点集被称为一个半空间（其中ai为一n维行向量，bi为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域R必定为多胞形（为统一起见，空集Φ也被视为多胞形）。在一般n维空间中，要直接得出多胞形的极点概念还有一些困难。在图5.1中顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。为此，我们将采用另一途径（代数方法）来定义它。1/31/202314MCM给定一个标准形式的线性规划问题（5.3），其中A=(aij)mxn，m<n且秩r(A)=m。取出A的m个线性无关的列，这些列构成A的一个m阶非奇异子矩阵B，称B为A的一个基矩阵。A的其余n－m列构成一个m×(n－m)矩阵N。称对应于B的列的变量为基变量（共有m个），记它们为xB。其余变量称为非基变量，记为xN。

基本解与基本可行解

1/31/202315MCM对线性规划（5.3），取定一个基矩阵B，令非基变量xN

=0，可以唯一地解出xB，xB

=B-1b。这样得到的点x=（B-1b，0）称为（5.3）的一个基本解。为了叙述方便起见，这里我们将xB放在了前面，其实，它们的位置可以任意，但这并不影响到问题实质。显然，基本解不一定是可行解，因为还要求它们满足非负约束，当一个基本解同时还是可行解时（即B-1b≥0），称之为（5.3）的一个基本可行解。进而，若B-1b>0，则称x=（B-1b，0）为（5.3）的一个非退化的基本可行解，并称B为一组非退化的可行基。由于基矩阵最多只有种不同的取法，即使A的任意m列均线性无关，且对应的基本解均可行，（5.3）最多也只能有个不同的基本可行解。1/31/202316MCM定理5.1基本可行解与极点的等价定理设A为一个秩为m的m×n矩阵（n>m）b为m维列向量，，记R为（5.3）的可行域。则x为R的极点的充分必要条件为x是在线性规划的求解中，下列定理起了关键性的作用。

基本可行解与极点的等价定理

定理5.1既提供了求可行域R的极点的代数方法，又指明了线性规划可行域R的极点至多只有有限个。的基本可行解。

1/31/202317MCM定理5.2线性规划基本定理

线性规划（5.3）具有以下性质：（2）若问题（5.3）存在一个最优解，则必定存在一个最优的基本可行解。（1）若可行域R≠Φ，则R必有基本可行解。定理5.2并非说最优解只能在基本可行解（极点）上达到，而是说只要（5.3）有有限最优解，就必定可在基本可行解（极点）中找到。1/31/202318MCM从模型本身来讲，线性规划显然应属于连续模型。但定理5.2表明，如果线性规划具有有限最优解，我们只需比较各个基本可行解上的目标函数值，即可找到一个最优解，而问题的基本可行解至多只有有限个，从而问题化为一个从有限多个极点中去选取一个最优点的问题。正是基于这样一种想法，Dantzig提出了求解线性规划问题的单纯形法。1/31/202319MCMDantzig单纯形法的基本步骤如下：求解线性规划的单纯形法

步1:取一个初始可行基B（一般取法见后面的两段单纯形法），再用高斯—约当消去法求出初始基本可行解x0，编制成所谓的初始单纯形表；步2:判断x0是否最优解，如果x0是最优解，输出x0，停，否则到步3；步3:按某一改进准则，将一个非基变量转变为基变量，而将一个基变量转变为非基变量，求一个更好的基本可行解。这相当于交换B与N的一个列，同样可用高斯—约当消去法，运算可以通过单纯形表上的所谓“转轴运算”实现。1/31/202320MCM设B为一组非退化的可行基，x0=（B-1b，0）为其对应的基本可行解。现在，我们来讨论如何判别x0是否为最优解。为此，考察任一可行解由Ax=b可得代入目标函数，得到(5.6)1/31/202321MCM定理5.3最优性判别定理令

（1）若rN

≥0，则x0必为（5.3）的一个最优解。

（2）记。若，rj

<0，则当B为非退化可行基时，x0必非最优解。1/31/202322MCM证明（1）若rN

≥0，由于变量满足非负约束，必有xN

≥0。于是，由（5.6）式知故x0为（5.3）的一个最优解。（2）（5.6）式给出了x处的目标值与x0处的目标值之间的联系。现设,且j≠j0仍令xj=0。由非退化假设，B－1b>0，根据（5.5）式可知，当且充分小时，仍有xB

>0。此时对应的x仍为可行解，但由（5.6），其目标函数值：故x0必非最优解。1/31/202323MCM定理5.3不仅给出了判别一个基本可行解是否为最优解的准则，而且在x0非最优解时还指出了一条改进它的途径。由于rN在判别现行基本可行解是否为最优解时起了重要作用，所以rN被称为x0处的检验向量，而rj(j∈N)则被称为非基变量xj的检验数。有趣的是上述过程完全可以在以下的单纯形表上进行。先将CT、A、b及数0写在一个矩阵中，将此矩阵看成一张数表，在此表上用高斯—约当消去法解方程组Ax=b高斯-约当消去法（第一行不变）1/31/202324MCM利用单位矩阵I消第一行的为零向量，则被消成，而0则被消成。将消去后的行向量写到最后一行，删去原来的第一行，得到一张被称为单纯型表的表格：

表5.1xBxNIB－1NB－1b0rN－Z01/31/202325MCM表格（5.1）以极为简洁明了的方式表达了我们需要的全部信息。从其中I所在的m行可以看出哪些变量是基变量并可直接读出对应的基本可行解x0=（B-1b，0）。其最后一行又给出了非基变量的检验数及x0处目标函数值的相反数。现在，我们以例5.1为例，来看一下单纯形法是如何工作的。例5.1的标准形式为（5.4），容易看出它的一个初始基B=I（以x3、x4、x5为基变量），且CB已经为零，故我们已有了一张初始的单纯形表(表5.2)1/31/202326MCM表5.2x1X2x3x4x5基变量x3②110010x4110108x5010017rj－4－30000x0=(0,0,10,8,7)T

z0=CTx0=0

rN=(r1,r2)=(－4，－3)1/31/202327MCM由于存在着负的检验数，且x0非退化，故x0非最优解。r1，r2均为负，x1，x2增大（进基）均能改进目标函数值。例如，取x1进基，仍令x2=0（x2仍为非基变量），此时由（5.5）式及（5.6）式有且

x1增加得越多，目标函数值也下降得越多，但当x1=5时x3=0，x1再增大则x3将变负。为保证可行性，x1最多只能增加到5，此时x3成为非基变量（退基）。1/31/202328MCM不难看出，上述改进可以在单纯形表上进行。对于一般形式的单纯形表，记最后一列的前m个分量为yi0，i=1,…,m。若取进基，记j0列前m个分量为，i=1,…,m。易见，阻碍增大的只可能是>0的那些约束。(1)若≤0对一切i=1,…,m成立（j0列前m个分量中不存在正值），则可任意增大，得到的均为可行解，但其目标值随之可任意减小，故问题无有限最优解。(2)否则，令1/31/202329MCM则随着的增大，将最先降为零（退出基变量），故只需以为主元作一次消去法运算（称此运算为一次转轴运算），即可得到改进后的基本可行解处的单纯形表。在本例中，因取x1进基（j=1）以y11为主元作转轴运算（高斯-约而当消去法运算），得到(表5.3)1/31/202330MCM表5.3x1X2x3x4x5基变量x31005x40103x5010017rj0－120020x1=(5,0,0,3,7)T，z1=－20，rN=(r2,r3)=(－1，2)1/31/202331MCM表5.3中r2<0，x1仍非最优解，按yi0/yi2（yi2>0）最小选定y22=为主元转轴，得到下一个基本可行解x2处的单纯形表表5.4。x1x2x3x4x5基变量x3101－１02x401－１２06x500１－２11rj00１２026x2=(2,6,0,0,1)Tz2=－26rN=(r3,r4)=(1，2)对于x2，由于rN=(1，2)已为非负向量，x2

为最优解，最优目标值为－26。于是，原问题例5.1的最优解x*=(2,6)T，最优目标值为26。1/31/202332MCM初始可行解的求法——两段单纯形法

当线性规划（5.3）的初始可行解不易看出时，可采用下面的两段单纯形法求解。阶段1

（求初始可行基）对第i个约束引入人工变量yi，yi≥0，将其改写为ai1x1+…+

ainxn

+yi

=bi，i=1,…,m。作辅助线性规划LP（1），其目标函数为:

容易看出，原规划有可行解（从而有基本可行解）的充分必要条件为辅助规划的最优目标值为零。由于辅助规划具有明显的初始可行基（人工变量对应的列构成单位矩阵I），可利用上述单纯形法逐次改进而求出辅助规划最优解。1/31/202333MCM阶段2

若辅助规划的最优目标值不等于零，原规划无可行解，计算终止。否则我们已求得原问题的一个基本可行解x0。删去阶段1最终单纯表中最后一行及对应人工变量的列，得到原规划对应x0的初始单纯形表，此时又可利用上述单纯形法求解原规划了。例5.2

1/31/202334MCM解：因为初始可行基不能直接看出，我们采用两段单纯形法求解。阶段1

先求解辅助规划：1/31/202335MCM表5.5x1x2x3x4x5基变量x4212104x5③31013rj－5－4－300－7选取x1进基，以y21=3为主元转轴（x5出基），得表5.6：表5.6x1x2x3x4x5基变量x40－14/31－2/32x1111/301/31rj01－4/305/3－21/31/202336MCM因r3<0，令x3进基。以y13=为主元轴（x4出基），得表5.7表5.7x1x2x3x4x5基变量x30－3/413/4－1/23/2x115/40－1/41/21/2rj000110

至此，对新的基本可行解检验数均已非负，辅助规划最优解已获得。又因辅助规划最优目标值为0，已求得原问题的一个基本可行解。1/31/202337MCM阶段2

现转入求解原规划，初始单纯形表为表5.8

表5.8x1x2x3基变量x30－3/413/2x115/401/2rj0－13/40－7/2因r2<0，令x2进基，以y22=为主元转轴，求得新的基本可行解及相应的单纯形表表5.91/31/202338MCM表5.9X1x2x3基变量x33/5019/5x24/5102/5rj13/500－11/5由表5.9可见，检验数已非负，原问题的最优解已经求得，。最优解为,最优目标值。1/31/202339MCM

现将线性规划单纯型算法作一个小结。在求解线性规划时，首先应将问题化为标准形式。若从标准形式已可看出一个初始基，则可直接用单纯法求解：（1）写出初始单纯形表；（2）若检验向量rN≥0，则已得以最优解；（3）任选一负分量rj。以进基，考察所在列。若对i=1,…,m均有≤0，则问题无有限最优解，停；否则令以为主元转轴，返回（2），直至rN≥0求出最优解。若从标准形式无法看出初始可行基，则需采用两段单纯形法求解。1/31/202340MCM

上述算法中隐含着非退化假设，即要求B-1b>0。当B-1b也存在零分量时，我们遇到了一个退化的基本可行解，此时rN存在负分量不一定说明现行基本可行解不是最优解。单纯形法也可能会遇到循环迭代。存在着几种避免循环的技巧，例如，只要每次在rj

<0的非基变量中选取具有最小足标者进基即可避免产生循环。

变量同时具有上、下界限止的线性规划问题也可化为标准形式求解，有兴趣的读者可以参阅D.G.鲁恩伯杰的“线性与非线性规划引论”一书的第三章。1/31/202341MCM§5.2运输问题运输问题的数学模型例5.3

某商品有m个产地、n个销地，各产地的产量分别为a1,…,am各销地的需求量分别为b1,…,bn。若该商品由i产地运到j销地的单位运价为Cij，问应该如何调运才能使总运费最省？（注：标准的运输问题要求产销平衡，即)1/31/202342MCM解：引入变量xij，其取值为由i产地运往j销地的该商品数量。例5.3的数学模型为(5.7)1/31/202343MCM

（5.7）显然是一个线性规划问题，当然可以用单纯形方法求解，但由于其约束条件的系数矩阵相当特殊，求解它可以采用其他简便方法。本节将介绍由康脱洛维奇和希奇柯克两人独立地提出的表上作业法（简称康—希表上作业法），其实质仍然是先作出一个初始基本可行解，然后用最优性准则检验是否为最优，并逐次改进直至最优性准则成立为止。1/31/202344MCM初始可行解的选取

不难发现，（5.7）的约束条件中存在着多余方程（注：将前m个约束方程相加得到的方程与将后n个方程相加得到的方程相同，故约束条将是线性相关的）。容易证明，只要从中除去一个约束，例如最后一个方程，约束条件就彼此独立了。因而，（5.7）是一个具有m×n个变量的线性规划，其每一基本可行解应含有m+n－1个基变量。记（5.7）约束条件中前m+n－1个方程的系数矩阵为A，A为（m+n－1）×mn矩阵，它的每一列最多只有两个非零元素且非零元素均为1。利用线性代数知识能够判定A中怎样的m+n－1个列可以取为基（即怎样的m+n－1个变量可以取为基变量）。

1/31/202345MCM为了判明哪些变量对应的列是线性无关的，先引入下面的定义：定义5.3

（闭回路）{xij}（i=1,…,m;j=1,…,n）的一个子集被称为一个闭回路，若它可以被排成其中

互异，

也互异。

用下面的方法可以较方便直观地看出{xij}的一个子集是否为一闭回路：作一个m行n列的表格，令位于该表格第m行第n列的格（i,j）对应xij。将子集中的变量填于相应的格中，将相邻变量（或同行或同列）用边相连，则此子集构成闭回路当且仅当其点按上述连法作出的折线可构成一个闭回路。1/31/202346MCM例如，当m=3,n=4时，X1={x12,x13,x23,x24,x34,x32}和X2={x12,x14,x24,x21,x31,x32}

均为闭回路，见表5.10和表5.11。表5.10表5.11

。

。

。

。

。

。

。

。

。

。

。

。1/31/202347MCM定理5.4X为{xij}（i=1,…，m；j=1，…，n）的一个子集，X中的变量对应的A中的列向量集线性无关的充要条件为X中不包含闭回路。

定理5.4不难用线性代数知识证明，详细证明从略。根据定理5.4，要选取（5.7）的一组基变量并进而得到一个基本可行解，只需选取{xij}的一个子集X，∣X∣=m+n-1且X中不含闭回路，其中∣X∣表示X中的变量个数。1/31/202348MCM我们用下面的例子来说明如何选取一个基本可行解。

例5.3给定运输问题如表5.12所示，表中左上角的数字为单位运价Cij。易见，本例是产销平衡的,即。表5.12销地产地1234产量12211×3×413210×335×92537×8×14237销量23461/31/202349MCM

现采用所谓“最小元素法”来求一组基本可行解。每次选取一个当前单位运价最小的变量为基变量。开始时，单位运价最小的为C33=1，令x33=min{a3,b3}=4,并令x13=x23=0(销地3已满足)，相应格打“×”（即不再考虑销地3的需求）。产地3已运出4单位，将产量改为剩余产量3。剩余表中单位运价最小的为C11=2(或C34=2)，令x11=min{a1,b1}=2,并令x21=x31=0，相应格打“×”，a1改为剩余产量1，…，直至全部产品分配完毕。注意到除最后一次分配外每次只能对一行或一列找“×”，表示某销地已满足，或某产地产品已分配完(注：当两者同时成立时只能打“×”行或列之一，将剩余需求量或产量记为0，此时基本可行基是退化的)。1/31/202350MCM显然这样分配共选出了m+n-1个变量，且这些变量的集合不含闭回路，从而构成一个基本可行解。当每一基变量xij选取时i产地的剩余商品量与j销地的剩余需求量总不相等时，选出的基本可行解是非退化的。

初始基本可行解也可按其他方式选取，如“左上角法”等，其方法与原理是类似的，左上角法每次选取剩余表格中位于最左上角的变量，其余均相同。1/31/202351MCM最优性判别

类似于单纯形法，可计算非基变量的检验数，存在着多种求检验数的方法（求得的结果是相同的），下面介绍计算简便且计算量也较小的“位势法”。引入m+n个量（被称为位势）u1，…，um；u1，…，un。对每一变量xij，引入rij,令rij=Ｃij-ui-vj(事实上，这一公式与单纯形法求检验数的公式是相同的)。对基变量xij，令rij=0，得到(xij为基变量)(5.8)1/31/202352MCM

齐次线性方程组（5.8）共有m+n－１个独立方程，但含有m+n个变量。任取一个变量，例如u1作为自由变量，便可解出方程组。容易看出，u1的取值不同虽会改变位势的取值但不会改变非基变量的检验数。因此，为方便起见，只要令u1＝０即可。事实上，我们甚至不必去解方程组（5.8），而只需令u1＝０，对所有基变量令ui＋vj＝cij，即cij-ui-vj＝０，在表上逐次求出所有位势，进而再对非基变量xij计算其检验数(5.9)1/31/202353MCM

例如，对表5.11中取定的基，我们求出位势及非基变量的检验数，列于表5.13中，表中不带圈的数为基变量取值，带圈的数为非基变量检验数，右上角的数为单位运价cij。表5.13u1=02211133041u1=510③335

－392u3=-210⑦8121423υ1

=2υ２

=－2υ3

=3υ4

=41/31/202354MCM利用线性代数知识可以证明下列各定理(证明从略)：定理5.5

任取一组非基变量，将其加入基变量集合中，则在所得变量集合中必存在唯一的闭回路，（注：因为加入新的列后得到的列向量组必定线性相关）。

易见闭回路中含有偶数个变量，若令进基，令

为保持平衡条件，位于偶数位置的变量必须减少θ，而位于奇数位置的变量则必须增加θ（注：）。1/31/202355MCM定理5.6

设是非基变量与基变量集合的并集中唯一的闭回路，若令=θ并在闭回路上调整基变量取值使之平衡，得一可行解x，则x处的目标值与原基本可行解上的目标值之差为。根据定理5.6，若存在检验数的非基变量，取进基（取正值）并令(5.10)则原取值为θ并位于偶数位置上的基变量退基，得一新的基本可行解，其目标值减少

。1/31/202356MCM定理5.7

设为（5.7）的一个基本可行解，若x0所有非基变量的检验数均非负，则x0必为（5.7）的一个最优解。当x0非退化时，此条件还是必要的。证明由定理5.6知，当x0所有非基变量的检验数均非负时，任一非基变量进基均不会使目标值减小，由于（5.7）是线性规划，此性质表明x0已为最优基本可行解。反之，则只要令具有负检验数的非基变量进基即可（必能降低目标函数值）。1/31/202357MCM综上所述，康—希表上作业法可如下操作：步1：按最小元素法(或右上角法等)求一初始基本可行解。步2：按(5.8)求出位势ui,υj(i=1,…,m;j=1,…,n)。进而按(5.9)求出非变量的检验数rij。若一切rij≥0，则已求得一组最优解。步3:任取<0，找出进基后形成的唯一闭回路。在找出的闭回路上调整，按（5.10）取θ，得出新的基本可行解，返回步2。直至找到最优解。1/31/202358MCM

对于例5.3，表5.12已给出非基变量的检验数。因r23<0，令x23进基，得闭回路x23,x24,x34,x33,取θ=min{x24,x33}=2，调整后得到一个新的基本可行解。求出新的基本可行解对应的位势及非基变量检验数，列成表5.14。表5.14u1=02211

113

①41u1=310⑤33529

②U3=－17⑥8

⑨1235υ1

=2υ２

=0υ3

=3υ4

=4

现在，非基变量检验数均已非负，故已求得最优解：x11=2，x14=1，x22=3，x23=2，x33=2，x34=5，其余=0（非基变量）。1/31/202359MCM

若运输问题是产销不平衡的，则应先将其转化为产销平衡的，然后再求解。例如，若产大于销，可虚设一销地（剩余产量存贮），将各产地运往该虚设销地的单位运价均取为零；若供不应求，则可虚设一个产地，产量为零，且由该产地运到各个销地的单位运价均取零。通过这种虚设产地或销地的方法即可将一个非标准形式的运输问题转化为标准形式的运输问题，从而可用上述康-希表上作业法加以求解。1/31/202360MCM

库存管理在企业管理中占有很重要的地位。工厂定期购入原料，存入仓库以备生产之用；商店成批购入各种商品，放在货柜上以备零售；水库在雨季蓄水，以备旱季的灌溉和发电；但是，细心的读者会发现，这些情况下都有一个如何使库存量最优的问题，即库存量应取多大才最为合适？存储量过大，存储费太高；存储量过小，会导致一次性订购的费用增加，或不能及时满足需求而遭到损失。为了保证生产的连续性和均衡性，需要确定一个合理、经济的库存量，并定期订货加以补充，按需求发放，以达到压缩库存物资、加速资金周转的目的。§5.3库存问题1/31/202361MCM为说明方便，我们先简要说明有关的概念，然后介绍几种比较简单的库存模型和解法。

我们知道，工厂和企业作为一个系统，其基本功能是输入、转换和输出。输入过程也叫供应过程，输出过程也称为需求过程。为保证生产正常进行，供应的数量和速度必须不小于需求的数量和速度，多余的数量可储存于各部门的仓库里。企业的仓库按生产供应和需求对象的不同，可大致分为两类：原材料库：用于存放生产所需的各原材料的仓库，这些原材料大多是由物资供应部门定期向外采购而来的，当然，也可以是企业自己生产的。这类仓库的库存费用由采购费和保管费两部分构成，即1/31/202362MCM半成品库和成品库：用于存放经过生产加工而成的半成品和成品的仓库。这类仓库的最大存储量一般就是生产批量，而库存费用由工装调整费和保管费两部分构成，即易见，随着生产批量得增大，计划期(年)内投产得批数减少，工装调整得次数减少，工装调整费下降，但库存量增加，保管费用上升。因此，为降低库存费用，必须确定一个经济批量(或经济批数)，使库存费用最小。1/31/202363MCM由上所述可见：在讨论库存问题时，涉及到三种费用：（1）采购费C是供应部门处理订货、补充库存所需的费用，包括采购人员的差旅费、手续费、检验费等。它属于一次性费用，直接与计划期内的采购次数n或一次采购量Q有关，计算公式为这里R为计划期（年、季或月）内的总需要量，Q为每批批量，c0为一次采购费用。1/31/202364MCM（2）工装调整费S是指每批产品投产前的工艺准备、设备调整及其检修所需的费用。属于一次性的费用，它与计划期内投入的批数有关，计算公式为其中为R计划期内的总产量，Q为生产批量，c1为一次工装调整费用。（3）保管费H损耗费和库存物资折算成资金的利息等，保管费的计算方法与保管方式、消费方式等等有关，假如消费速度是均匀的，通常可用下面的公式来计算1/31/202365MCM

其中

为平均库存量，

为单位物资在计划期内的保管费，单位物资有时按重量计，有时按占用仓库的面积(或体积)计，是具体情况而定。由于单件保管费有时计算起来比较困难，也可用保管费率i计算，i为保管费占总库存费的百分比，这时公式

可以改写为

这里为P库存物资的单价，为平均保管费率。应该指出的是：保管费是一项可观的、不可忽视的费用，依据70年代中期美国十大公司的统计，它约占总库存物资资金的20%，其中以库存物资资金的利息占的份额最大。1/31/202366MCM下面我们分几种情况来说明几种较为简单的库存模型一：瞬时送货的确定型库存问题(不允许缺货的情况)

首先考虑最简单的库存问题。假设某工厂生产需求速率稳定，库存下降到零时，再定购进货，一次采购量为Q，定购点的提前时间为零（即进货有保障、有规律，可根据需求提前订货），在保证不缺货的条件下，试确定最经济的采购量

，使库存费用最小。此时库存费用为1/31/202367MCM在本模型中，平均库存量

为常量，所以问题归结为求解如下的优化问题这是一个一元函数求极小值的问题，可用微积分方法求其最优解，求得的解为这就是所要求的经济采购量。而库存的最小费用为经济学上称这两个公式为平方根公式。1/31/202368MCM二：非瞬时送货的确定型库存问题(不允许缺货

的情况)在本模型中，由于运输设备等的限制，经常会出现非瞬时入库的情况，即从再定购点开始的一段时间内，一方面按一定进度入库(设r1为定购物资每天入库的数量)，另一方面按生产需要出库(设r2<r1为定购物资在入库期内每天出库的数量)，直到达到最大库存量QM为止。设模型的其他参数不变，试确定经济采购量Q*和最小库存费用T*。易见为定购物资的入库时间（天），所以最大库存量为1/31/202369MCM平均库存量为

因此保管费为

库存费用为所以这一类库存问题归结为求解1/31/202370MCM

这仍然是一个一元函数求极小值的问题，用微积分方法求得最优解Q*即经济采购量为而最小库存费用为对于成品库和半成品库的库存问题可以类似地进行分析，参看下例。

1/31/202371MCM例5.4

某厂年计划生产6500件产品，设每个生产周期的工装调整费为200元，每年每件产品的储存费为3.2元，每天生产产品50件，市场需求26(件/天)，每年工作300天，试求最经济的生产批量Q*和最小的库存费用T*。解

在此问题中，一次工装调整费用c1=200元，年计划产量R=6500件，设该厂每批生产Q件产品，则工装调整费为而保管费为

1/31/202372MCM其中cH=3.2(元／件年)，r1＝50件，r2＝26件，所以问题归结为求解用微积分方法容易计算的最经济的生产批量为而最小库存费用为

上面介绍的两种模型是最简单、也是最基本的确定型库存模型。它不允许缺货，故假设条件非常理想，但实际情况却要复杂得多。1/31/202373MCM下面我们再来看看允许缺货的库存模型。三：瞬时送货的确定型库存问题(允许缺货的情况)上述模型不允许缺货，若允许缺货，则需要支付一定的缺货损失费用Z。

我们假设Q2为缺货量，单位缺货在单位时间内产生的缺货损失费用为cZ(元)，单位物资在单位时间内的保管费为ch(元)，D为单位时间内物资的需求量，问每次采购量Q、缺货量Q2取为何值时，才能使库存费用T和缺货损失费用之和最小？1/31/202374MCM我们不妨设总费用为F则

其中

为采购费，c0为每次的采购费。为保管费，

为平均库存量，这里

，为单位物资在计划期内的保管费，t1为一个采购周期内物资的存储时间。所以保管费为注意到，

上式可改写为1/31/202375MCM注意到

，则上式可改写为因此上述库存问题归结为求解1/31/202376MCM

容易证明它们即为使总费用

取得最小值的经济采购量Q*和最经济的缺货量Q2*，而最小费用为

。

这是一个求二元函数的极小值的问题，仍可用微积分方法求解得到1/31/202377MCM

秘鲁是一个捕鱼业非常发达的国家，随着人们对鱼粉需求量的增长，秘鲁的捕鱼量不断增加。到1960，秘鲁已成为世界上捕鱼量最大的国家，年捕鱼量达到1000万吨，约占全球捕鱼总量的15%。捕鱼量的稳定增长使海洋生物学家越来越感到不安，1972年，生物学家们认为，秘鲁捕鱼量已达到了能维持鱼群正常生长情况下的最大捕获量的两倍，政府如再不加以控制，采取措施制止几近疯狂的捕捞，秘鲁的渔业资源将趋于枯竭，渔业生产会陷入完全崩溃的境地(Paulik,1971)。到1973年，生物学家们的担忧开始显现。当年，秘鲁沿海的鱼量猛减，渔民几乎无鱼可捕，出现了所谓“鳀鱼危机”(Idyll，1973年)，并引起了全世界范围内粮食价格的上涨。§5.4最佳捕鱼方案1/31/202378MCM下表是秘鲁海洋学院1974年提供的秘鲁渔业的历史统计数据：

表5.15

年

份

船

数

捕鱼日数

捕鱼量(百万吨)1959196019611962196319641965196619671968196919701971197219734146677561069165517441623165015691490145514991473139912562942792982942692972651901701671621808989271.912.934.586.276.428.867.238.539.8210.628.9612.2710.284.451.781/31/202379MCM

如何制定最优捕鱼方案，在不破坏鱼类生态平衡的前提下获得最大的捕鱼量呢？鱼类学家M.Schaefer于1975年在Logistic模型的基础上建立了捕鱼问题的优化模型，提出了一个最优捕鱼方案的建议。以下，让我们来看看他所建立的模型。用x(t)记t时刻海洋中鱼的数量，r为鱼的净增长率，K为环境所能供养的饱和鱼量。

假设(1)在无捕捞情况下，鱼类按Logistic模型增长，即鱼的数量满足Logistic模型：(5.11)1/31/202380MCM(2)考虑捕鱼对鱼类生长的影响。令h为捕捞率，，此时，鱼类增长满足的微分方程为：(5.12)

捕捞率取h=qEx为的原因是捕获量与海洋中现有的鱼量成正比。q表示捕捞系数，与捕捞的生产水平有关，捕鱼的工具越先进q就越大，为降低渔民的劳动强度，自然q越大越好。然而，正如前面所说，政府应当控制渔民的捕鱼，不能随其任意捕捞。控制的强度通过一个被称为捕捞能力的系数E来调节(可以用规定禁止捕鱼的休渔期或划定禁渔区域的方法来实现)。1/31/202381MCM

正如第三章中Logistic模型所指出的，微分方程(5.11)有一个平衡解x=K，当x(t)≠K时，随着t趋于无穷，将有x(t)→K

。对于微分方程(5.12)，平衡点的位置发生了改变，它被移到了方程的根

处，

满足

，即(5.13)易见，

为二次曲线(5.14)1/31/202382MCM与直线的交点

(5.15)见图5-2。(图5-2)1/31/202383MCM令

显然，

，将

在

处展开成(5.16)求导得

(1)若，(此时，即捕捞率小于鱼的内禀增长率)，则当时，从而，，x(t)随时间t而增大并趋向于，当时，从而，，x(t)随时间t而减小并趋向于。总之，此时x(t)随时间t的增大必趋向于平衡点，此时平衡点是稳定的平衡点。1/31/202384MCM(2)反之，若，则类似可证，随着时间t的增大，x(t)将远离平衡点，此时，平衡点是非稳定的。当然，这一结果是十分明显的，因为在时，，捕捞率超过了鱼的增长率，海洋中的鱼类数量将越来越少，最终必将趋于绝灭。(3)若，则尚需检查的符号。根据以上分析，捕鱼必须控制在(即)的限度以内，现在我们将进一步分析，在此前提下，又应如何捕鱼，才能使每年的捕获总量最大。

1/31/202385MCM为此，将(5.13)代入捕鱼量公式，得到在平衡条件下的捕鱼量：(5.17)为求捕鱼量最大，令，求得，将其代入(5.17)式，即可求得最大捕获量，此时1/31/202386MCM

上述结果也可从图5-2中看出，如取，曲线与的交点记为，则易见在射线(5.15)与二次曲线(5.14)的交点中，过的一条在交点处具有最大的纵坐标(即最大捕获量)。

通常情况下，渔民考虑的主要还是经济利益的最大化，此时，模型将变得复杂一些。设鱼的单价为p，单位时间的捕捞成本为CE，则由时刻a到时刻b这段时间内渔民捕鱼的收益最大，约束条件为(5.12)式成立，即此时要求解的问题为1/31/202387MCM

(5.18)是一个泛函极值问题，可用欧拉方程求解，因本书不准备介绍求解泛函极值的变分方法，我们只建立了此问题的数学模型，而不讨论其求解，有兴趣的读者可参考杨启帆、边馥萍编著的数学模型。(5.18)1/31/202388MCM

在森林失火时，消防站在接到警报后应派多少消防队员前去救火呢？显然，派的队员越多，灭火的速度越快，火灾造成的损失越小，但反过来，救援的开支会增加。所以我们要综合考虑森林损失费、救援费与消防队员人数之间的关系，以最小费用原则来决定派出队员的数目。即应当考虑：派出多少队员救火，才能使火灾损失费和救火费用之和（简称总费用）最小？§5.5

森林救火费用最小问题1/31/202389MCM我们先做如下分析：

(１)火灾损失费通常与森林被烧毁的面积成正比，而烧毁面积与开始失火到火被扑灭之间的间隔时间有关，灭火时间又取决于消防队员的数目，队员越多灭火越快。

记失火时刻为t=0，开始救火时刻为t=t1，火被扑灭的时刻为t=t2。设在时刻森林烧毁面积为B(t2)，则造成损失的森林烧毁面积为。由导数的定义，易见表示单位时间内烧毁的森林面积，

也表示火势蔓延的速度。当t=0,t2时，，设在t=t1时，取得最大值h。1/31/202390MCM(2)救援费用包括两部分：一部分是灭火器材的消耗和消防队员的薪金等，与队员人数和灭火所用时间有关；另一部分是运送队员和器材等的一次性支出，只与队员人数有关。在上述分析的基础上，我们再作如下模型假设：(1)损失费与森林烧毁面积B(t2)成正比，比例系数c1为烧毁单位面积的损失费。(2)从失火到开始救火这段时间()内，火势蔓延速度与时间t成正比，记比率系数为火势蔓延速度。在这里，我们有必要指出，这个假设在风力不大的条件下是大致合理的。1/31/202391MCM(3)派出消防队员x名，开始救火以后()，火势蔓延速度降为，其中可以看成每个队员的平均灭火速度，显然应该有。(4)每个消防队员单位时间的费用为c2，于是每个队员的救火费用是；每个队员的一次性支出(如交通费等)是c3。

与t的关系如图5-3所示。1/31/202392MCM(图5-3)1/31/202393MCM

由图5-3及假设2、3我们可以得到如下关系式：

又于是再根据假设条件1、4，森林损失费为救援费为

于是我们得救火总费用为此即为这个优化模型的目标函数。1/31/202394MCM这是一个一元函数的极值问题。令，可以得到应该派出的队员人数为

1/31/202395MCM

光在由一种介质进入另一种介质时，在界面处会发生折射现象。人们发现，折射现象造成的结果是所谓“最短时间”效应，即光线会走最快的路径。§5.6

光学中的折射原理设光在介质1中的传播速度为v1而在介质2中的传播速度为v2

。在同一种介质中，光的传播速度是常数，因而，在同种介质中它将沿着直线方向传播。现取两种介质的分界面上的一条直线为x轴，设一束光线由介质1中的A(0，a)点经x轴上的O点(取为坐标原点)进入介质2，并沿某直线方向行进到B(d，b)点。设直线段AP与x轴的法线的夹角为、直线段PB与x轴的法线的夹角为。1/31/202396MCM

下面，我们将根据最短时间效应来推导出光学中的折射定理。光线由A传到B所需的时间为光线由O传到B所需时间为故光线由A传播到B的总时间为1/31/202397MCM最短时间效应对应的优化问题为([0，d])

令得(5.19)注意到

1/31/202398MCM(5.9)时又可写成此即光学中的折射定理。1/31/202399MCM

在长期的生物进化过程中，动物体内的结构已趋于某种程度的最优化状态，本节将举两个实例来加以说明。本节采用的方法不同于一般的优化问题的研究，在一般优化问题中，我们研究的问题是为了达到某种意义下的最优化，人们应当如何去做。而本节要研究的却是：假设生物的结构在进化过程中不断优化，适者生存，逐步达到了某种意义下的最优化，那么，生物的结构应当具有哪些特征？§5.7

身体结构得优化1/31/2023100MCM例5.5血管的分支

假设动物的血管系统经长期进化，几何形状已经达到了使能量消耗大到最低的优化标准。血液在动物的血管中不停地循环流动着，在此过程中消耗的总能量显然与血管系统的几何形状有关。我们不可能讨论整个血管系统的几何形状，那样的话会涉及到太多的生理知识，对此我们甚至尚未完全搞清楚。在本节中，我们只研究血管分支处粗细血管半径的比例和分岔角度，我们希望知道，它们在消耗能量最小的原则下应取何值。

1/31/2023101MCM为研究这一问题，我们先做如下假设：(1)一条粗血管在分支处只分成；两条较细得血管，在分支点附近三条血管位于同一平面，并且有一对称轴。如若不然，血管长度增加必然导致能量消耗得增加，不符合优化原则，我们称此假设为几何假设。(2)在考察血液流动受到的阻力时，将这种流动视为粘性液体在刚性管道内的运动，即将血管近似看成刚体，这是一种近似。事实上血管是有弹性的，这种近似对结果的影响很小，我们称之为物理假设。(3)血液对血管提供的营养随着管壁内表面积和管壁的厚度的增加而增加。管壁厚度和血管半径成正比，我们称之为生理假设。1/31/2023102MCM根据几何假设，我们作血管分支图5-4如下：（图5-4）1/31/2023103MCM

图中一条粗血管与两条细血管在C点分岔，并形成对称的几何图形。粗细血管的半径分别为r和r1，分岔处角度为

。考察长度为

的一段粗血管AC和长度为

的细血管CB和

，ACB()的水平和垂直距离为L和H，另外血液在粗细血管中单位时间内的流量分别为q和q1，显然

。

由假设2，根据流体力学定律：粘性物质在刚性管道内流动所受到的阻力与流速的平方成正比，与管道半径的四次方成反比。从而血液在粗细血管内受到阻力分别为和，其中k为比率系数。1/31/2023104MCM

由假设3，在单位长度的血管内，血液为管壁提供营养所消耗的能量为，其中b为比率系数。

根据上述假设及对假设的进一步分析，我们可以得到血液从粗血管A点流动到细血管B点，用于克服阻力及给管壁提供营养所消耗的能量为(5.20)另外由血管几何图形易得：(5.21)1/31/2023105MCM将（5.21）代入（5.20），并注意到，得

要使总能量消耗

达到最小，应求解此多元函数最小值问题，根据必要条件，应有：即