浙大城院數(shù)學(xué)建模5講解學(xué)習(xí)課件

第五章、優(yōu)化模型

§5.1線性規(guī)劃模型§5.2運(yùn)輸問題§5.3庫存問題§5.4最佳捕魚方案§5.5森林救火費(fèi)用最小問題7/22/20231MCM§5.5森林救火費(fèi)用最小問題§5.6光學(xué)中的折射原理§5.7身體結(jié)構(gòu)得優(yōu)化7/22/20232MCM

經(jīng)濟(jì)管理和科學(xué)研究等領(lǐng)域中經(jīng)常會遇到的問題類型之一。在很多情況下，我們會憑經(jīng)驗解決面臨的優(yōu)化問題，這樣做看似有效，風(fēng)險也較小，但決策時常常會融入太多決策者的主觀臆斷，因而無法保證結(jié)果的最優(yōu)性。那么，是否一定要做大量的試驗來探索最優(yōu)方案呢？前言：

最優(yōu)化方法是數(shù)學(xué)學(xué)科中的一個應(yīng)用性很強(qiáng)的分支，它包含的內(nèi)容十分廣泛，有數(shù)學(xué)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃、目標(biāo)規(guī)劃、多目標(biāo)規(guī)劃等）、庫存論、排隊論、博弈論、組合優(yōu)化（離散優(yōu)化）、隨機(jī)規(guī)劃等等。

7/22/20233MCM§5.1線性規(guī)劃模型

線性規(guī)劃（LinearProgramming,簡記LP）是數(shù)學(xué)規(guī)劃的一個重要組成部分。自從1947年G·B·Dantzig提出求解線性規(guī)劃的單純形法以來，線性規(guī)劃在理論上日趨成熟，在應(yīng)用上日趨廣泛，已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。

7/22/20234MCM

某廠生產(chǎn)甲、乙兩種產(chǎn)品，每單位產(chǎn)品銷售后的利潤分別為4千元與3千元。生產(chǎn)甲產(chǎn)品需用A、B兩種機(jī)器加工，每單位產(chǎn)品的加工時間分別為2小時和1小時；生產(chǎn)乙產(chǎn)品需用A、B、C三種機(jī)器加工，每單位產(chǎn)品的加工時間為每臺機(jī)器各一小時。若每天可用于加工這兩種產(chǎn)品的機(jī)器時數(shù)分別為A機(jī)器10小時、B機(jī)器8小時和C機(jī)器7小時，問該廠應(yīng)當(dāng)生產(chǎn)甲、乙兩種產(chǎn)品各多少，才能使總利潤最大？

例5.1（線性規(guī)劃的實例）7/22/20235MCM例5.1的數(shù)學(xué)模型設(shè)該廠生產(chǎn)x1臺甲機(jī)床和x2臺乙機(jī)床時總利潤最大，則x1、x2應(yīng)滿足：(5.1)

4x1+3x2表示生產(chǎn)x1單位甲產(chǎn)品和x2單位乙產(chǎn)品的總利潤，被稱為問題的目標(biāo)函數(shù)。中的幾個不等式是問題的約束條件，記為S.t。由于式中的目標(biāo)函數(shù)與約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題。7/22/20236MCM

線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件可以是不等式也可以是等式，變量可以有非負(fù)要求也可以沒有（稱沒有非負(fù)約束的變量為自由變量）。為了避免這種由于形式多樣性而帶來的不便，規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為線性規(guī)劃的標(biāo)準(zhǔn)形式(5.2)7/22/20237MCM或更簡潔地，利用矩陣與向量記為(5.3)其中C和x為n維列向量，b為m維列向量，b≥0，A為m×n矩陣，m<n且rank(A)=m。7/22/20238MCM

如果根據(jù)實際問題建立起來的線性規(guī)劃問題并非標(biāo)準(zhǔn)形式，可以將它如下化為標(biāo)準(zhǔn)形式：（1）若目標(biāo)函數(shù)為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為自變量，則可令，其中、≥07/22/20239MCM例如，例5.1并非標(biāo)準(zhǔn)形式，其標(biāo)準(zhǔn)形式為(5.4)7/22/202310MCM

為了了解線性規(guī)劃問題的特征并導(dǎo)出求解它的算法，我們先應(yīng)用圖解法來求解例5.1。滿足線性規(guī)劃所有約束條件的點被稱為問題的可行點（或可行解），所有可行點構(gòu)成的集合被稱為問題的可行域，記為R。對于每一固定的值z，使目標(biāo)函數(shù)值等于z的點構(gòu)成的直線稱為目標(biāo)函數(shù)等位線，當(dāng)z變動時，我們就得到了一族平行直線（見圖5-1）。

線性規(guī)劃的圖解法7/22/202311MCM圖5-1（注：）對于例5.1，等位線越趨于右上方，其上的點具有越大的目標(biāo)函數(shù)值。不難看出，例5.1的最優(yōu)解為x*=(2,6)T，最優(yōu)目標(biāo)值z*=26。7/22/202312MCM（3）若線性規(guī)劃存在有限最優(yōu)解，則必可找到具有最優(yōu)目標(biāo)函數(shù)值的可行域R的“頂點”，（注：我們稱這種“頂點”為極點）。

從上面的圖解過程可以看出并不難證明以下斷言：（1）可行域R可能會出現(xiàn)多種情況。R可能是空集也可能是非空集合，當(dāng)R非空時必定是若干個半平面的交集（除非遇到空間維數(shù)的退化）。R既可能是有界區(qū)域，也可能是無界區(qū)域。（2）在R非空時，線性規(guī)劃既可以存在有限最優(yōu)解，也可以不存在有限最優(yōu)解（其目標(biāo)函數(shù)值無界）。7/22/202313MCM上述論斷可以推廣到一般的線性規(guī)劃問題，區(qū)別只在于空間的維數(shù)。在一般的n維空間中，滿足某一線性等式aix=bi的點集被稱為一個超平面，而滿足某一線性不等式aix≤bi（或aix≥bi）的點集被稱為一個半空間（其中ai為一n維行向量，bi為一實數(shù)）。若干個半空間的交集被稱為多胞形，有界的多胞形又被稱為多面體。易見，線性規(guī)劃的可行域R必定為多胞形（為統(tǒng)一起見，空集Φ也被視為多胞形）。在一般n維空間中，要直接得出多胞形的極點概念還有一些困難。在圖5.1中頂點可以看成為邊界直線的交點，但這一幾何概念的推廣在一般n維空間中的幾何意義并不十分直觀。為此，我們將采用另一途徑（代數(shù)方法）來定義它。7/22/202314MCM給定一個標(biāo)準(zhǔn)形式的線性規(guī)劃問題（5.3），其中A=(aij)mxn，m<n且秩r(A)=m。取出A的m個線性無關(guān)的列，這些列構(gòu)成A的一個m階非奇異子矩陣B，稱B為A的一個基矩陣。A的其余n－m列構(gòu)成一個m×(n－m)矩陣N。稱對應(yīng)于B的列的變量為基變量（共有m個），記它們?yōu)閤B。其余變量稱為非基變量，記為xN。

基本解與基本可行解

7/22/202315MCM對線性規(guī)劃（5.3），取定一個基矩陣B，令非基變量xN=0，可以唯一地解出xB，xB=B-1b。這樣得到的點x=（B-1b，0）稱為（5.3）的一個基本解。為了敘述方便起見，這里我們將xB放在了前面，其實，它們的位置可以任意，但這并不影響到問題實質(zhì)。顯然，基本解不一定是可行解，因為還要求它們滿足非負(fù)約束，當(dāng)一個基本解同時還是可行解時（即B-1b≥0），稱之為（5.3）的一個基本可行解。進(jìn)而，若B-1b>0，則稱x=（B-1b，0）為（5.3）的一個非退化的基本可行解，并稱B為一組非退化的可行基。由于基矩陣最多只有種不同的取法，即使A的任意m列均線性無關(guān)，且對應(yīng)的基本解均可行，（5.3）最多也只能有個不同的基本可行解。7/22/202316MCM定理5.1基本可行解與極點的等價定理設(shè)A為一個秩為m的m×n矩陣（n>m）b為m維列向量，，記R為（5.3）的可行域。則x為R的極點的充分必要條件為x是在線性規(guī)劃的求解中，下列定理起了關(guān)鍵性的作用。

基本可行解與極點的等價定理

定理5.1既提供了求可行域R的極點的代數(shù)方法，又指明了線性規(guī)劃可行域R的極點至多只有有限個。的基本可行解。

7/22/202317MCM定理5.2線性規(guī)劃基本定理

線性規(guī)劃（5.3）具有以下性質(zhì)：（2）若問題（5.3）存在一個最優(yōu)解，則必定存在一個最優(yōu)的基本可行解。（1）若可行域R≠Φ，則R必有基本可行解。定理5.2并非說最優(yōu)解只能在基本可行解（極點）上達(dá)到，而是說只要（5.3）有有限最優(yōu)解，就必定可在基本可行解（極點）中找到。7/22/202318MCM從模型本身來講，線性規(guī)劃顯然應(yīng)屬于連續(xù)模型。但定理5.2表明，如果線性規(guī)劃具有有限最優(yōu)解，我們只需比較各個基本可行解上的目標(biāo)函數(shù)值，即可找到一個最優(yōu)解，而問題的基本可行解至多只有有限個，從而問題化為一個從有限多個極點中去選取一個最優(yōu)點的問題。正是基于這樣一種想法，Dantzig提出了求解線性規(guī)劃問題的單純形法。7/22/202319MCMDantzig單純形法的基本步驟如下：求解線性規(guī)劃的單純形法

步1:取一個初始可行基B（一般取法見后面的兩段單純形法），再用高斯—約當(dāng)消去法求出初始基本可行解x0，編制成所謂的初始單純形表；步2:判斷x0是否最優(yōu)解，如果x0是最優(yōu)解，輸出x0，停，否則到步3；步3:按某一改進(jìn)準(zhǔn)則，將一個非基變量轉(zhuǎn)變?yōu)榛兞?，而將一個基變量轉(zhuǎn)變?yōu)榉腔兞?，求一個更好的基本可行解。這相當(dāng)于交換B與N的一個列，同樣可用高斯—約當(dāng)消去法，運(yùn)算可以通過單純形表上的所謂“轉(zhuǎn)軸運(yùn)算”實現(xiàn)。7/22/202320MCM設(shè)B為一組非退化的可行基，x0=（B-1b，0）為其對應(yīng)的基本可行解?，F(xiàn)在，我們來討論如何判別x0是否為最優(yōu)解。為此，考察任一可行解由Ax=b可得代入目標(biāo)函數(shù)，得到(5.6)7/22/202321MCM定理5.3最優(yōu)性判別定理令

（1）若rN≥0，則x0必為（5.3）的一個最優(yōu)解。

（2）記。若，rj<0，則當(dāng)B為非退化可行基時，x0必非最優(yōu)解。7/22/202322MCM證明（1）若rN

≥0，由于變量滿足非負(fù)約束，必有xN

≥0。于是，由（5.6）式知故x0為（5.3）的一個最優(yōu)解。（2）（5.6）式給出了x處的目標(biāo)值與x0處的目標(biāo)值之間的聯(lián)系?，F(xiàn)設(shè),且j≠j0仍令xj=0。由非退化假設(shè)，B－1b>0，根據(jù)（5.5）式可知，當(dāng)且充分小時，仍有xB

>0。此時對應(yīng)的x仍為可行解，但由（5.6），其目標(biāo)函數(shù)值：故x0必非最優(yōu)解。7/22/202323MCM定理5.3不僅給出了判別一個基本可行解是否為最優(yōu)解的準(zhǔn)則，而且在x0非最優(yōu)解時還指出了一條改進(jìn)它的途徑。由于rN在判別現(xiàn)行基本可行解是否為最優(yōu)解時起了重要作用，所以rN被稱為x0處的檢驗向量，而rj(j∈N)則被稱為非基變量xj的檢驗數(shù)。有趣的是上述過程完全可以在以下的單純形表上進(jìn)行。先將CT、A、b及數(shù)0寫在一個矩陣中，將此矩陣看成一張數(shù)表，在此表上用高斯—約當(dāng)消去法解方程組Ax=b高斯-約當(dāng)消去法（第一行不變）7/22/202324MCM利用單位矩陣I消第一行的為零向量，則被消成，而0則被消成。將消去后的行向量寫到最后一行，刪去原來的第一行，得到一張被稱為單純型表的表格：

表5.1xBxNIB－1NB－1b0rN－Z07/22/202325MCM表格（5.1）以極為簡潔明了的方式表達(dá)了我們需要的全部信息。從其中I所在的m行可以看出哪些變量是基變量并可直接讀出對應(yīng)的基本可行解x0=（B-1b，0）。其最后一行又給出了非基變量的檢驗數(shù)及x0處目標(biāo)函數(shù)值的相反數(shù)。現(xiàn)在，我們以例5.1為例，來看一下單純形法是如何工作的。例5.1的標(biāo)準(zhǔn)形式為（5.4），容易看出它的一個初始基B=I（以x3、x4、x5為基變量），且CB已經(jīng)為零，故我們已有了一張初始的單純形表(表5.2)7/22/202326MCM表5.2x1X2x3x4x5基變量x3②110010x4110108x5010017rj－4－30000x0=(0,0,10,8,7)T

z0=CTx0=0

rN=(r1,r2)=(－4，－3)7/22/202327MCM由于存在著負(fù)的檢驗數(shù)，且x0非退化，故x0非最優(yōu)解。r1，r2均為負(fù)，x1，x2增大（進(jìn)基）均能改進(jìn)目標(biāo)函數(shù)值。例如，取x1進(jìn)基，仍令x2=0（x2仍為非基變量），此時由（5.5）式及（5.6）式有且

x1增加得越多，目標(biāo)函數(shù)值也下降得越多，但當(dāng)x1=5時x3=0，x1再增大則x3將變負(fù)。為保證可行性，x1最多只能增加到5，此時x3成為非基變量（退基）。7/22/202328MCM不難看出，上述改進(jìn)可以在單純形表上進(jìn)行。對于一般形式的單純形表，記最后一列的前m個分量為yi0，i=1,…,m。若取進(jìn)基，記j0列前m個分量為，i=1,…,m。易見，阻礙增大的只可能是>0的那些約束。(1)若≤0對一切i=1,…,m成立（j0列前m個分量中不存在正值），則可任意增大，得到的均為可行解，但其目標(biāo)值隨之可任意減小，故問題無有限最優(yōu)解。(2)否則，令7/22/202329MCM則隨著的增大，將最先降為零（退出基變量），故只需以為主元作一次消去法運(yùn)算（稱此運(yùn)算為一次轉(zhuǎn)軸運(yùn)算），即可得到改進(jìn)后的基本可行解處的單純形表。在本例中，因取x1進(jìn)基（j=1）以y11為主元作轉(zhuǎn)軸運(yùn)算（高斯-約而當(dāng)消去法運(yùn)算），得到(表5.3)7/22/202330MCM表5.3x1X2x3x4x5基變量x31005x40103x5010017rj0－120020x1=(5,0,0,3,7)T，z1=－20，rN=(r2,r3)=(－1，2)7/22/202331MCM表5.3中r2<0，x1仍非最優(yōu)解，按yi0/yi2（yi2>0）最小選定y22=為主元轉(zhuǎn)軸，得到下一個基本可行解x2處的單純形表表5.4。x1x2x3x4x5基變量x3101－１02x401－１２06x500１－２11rj00１２026x2=(2,6,0,0,1)Tz2=－26rN=(r3,r4)=(1，2)對于x2，由于rN=(1，2)已為非負(fù)向量，x2為最優(yōu)解，最優(yōu)目標(biāo)值為－26。于是，原問題例5.1的最優(yōu)解x*=(2,6)T，最優(yōu)目標(biāo)值為26。7/22/202332MCM初始可行解的求法——兩段單純形法

當(dāng)線性規(guī)劃（5.3）的初始可行解不易看出時，可采用下面的兩段單純形法求解。階段1

（求初始可行基）對第i個約束引入人工變量yi，yi≥0，將其改寫為ai1x1+…+ainxn

+yi

=bi，i=1,…,m。作輔助線性規(guī)劃LP（1），其目標(biāo)函數(shù)為:

容易看出，原規(guī)劃有可行解（從而有基本可行解）的充分必要條件為輔助規(guī)劃的最優(yōu)目標(biāo)值為零。由于輔助規(guī)劃具有明顯的初始可行基（人工變量對應(yīng)的列構(gòu)成單位矩陣I），可利用上述單純形法逐次改進(jìn)而求出輔助規(guī)劃最優(yōu)解。7/22/202333MCM階段2若輔助規(guī)劃的最優(yōu)目標(biāo)值不等于零，原規(guī)劃無可行解，計算終止。否則我們已求得原問題的一個基本可行解x0。刪去階段1最終單純表中最后一行及對應(yīng)人工變量的列，得到原規(guī)劃對應(yīng)x0的初始單純形表，此時又可利用上述單純形法求解原規(guī)劃了。例5.2

7/22/202334MCM解：因為初始可行基不能直接看出，我們采用兩段單純形法求解。階段1先求解輔助規(guī)劃：7/22/202335MCM表5.5x1x2x3x4x5基變量x4212104x5③31013rj－5－4－300－7選取x1進(jìn)基，以y21=3為主元轉(zhuǎn)軸（x5出基），得表5.6：表5.6x1x2x3x4x5基變量x40－14/31－2/32x1111/301/31rj01－4/305/3－27/22/202336MCM因r3<0，令x3進(jìn)基。以y13=為主元軸（x4出基），得表5.7表5.7x1x2x3x4x5基變量x30－3/413/4－1/23/2x115/40－1/41/21/2rj000110

至此，對新的基本可行解檢驗數(shù)均已非負(fù)，輔助規(guī)劃最優(yōu)解已獲得。又因輔助規(guī)劃最優(yōu)目標(biāo)值為0，已求得原問題的一個基本可行解。7/22/202337MCM階段2現(xiàn)轉(zhuǎn)入求解原規(guī)劃，初始單純形表為表5.8

表5.8x1x2x3基變量x30－3/413/2x115/401/2rj0－13/40－7/2因r2<0，令x2進(jìn)基，以y22=為主元轉(zhuǎn)軸，求得新的基本可行解及相應(yīng)的單純形表表5.97/22/202338MCM表5.9X1x2x3基變量x33/5019/5x24/5102/5rj13/500－11/5由表5.9可見，檢驗數(shù)已非負(fù)，原問題的最優(yōu)解已經(jīng)求得，。最優(yōu)解為,最優(yōu)目標(biāo)值。7/22/202339MCM

現(xiàn)將線性規(guī)劃單純型算法作一個小結(jié)。在求解線性規(guī)劃時，首先應(yīng)將問題化為標(biāo)準(zhǔn)形式。若從標(biāo)準(zhǔn)形式已可看出一個初始基，則可直接用單純法求解：（1）寫出初始單純形表；（2）若檢驗向量rN≥0，則已得以最優(yōu)解；（3）任選一負(fù)分量rj。以進(jìn)基，考察所在列。若對i=1,…,m均有≤0，則問題無有限最優(yōu)解，停；否則令以為主元轉(zhuǎn)軸，返回（2），直至rN≥0求出最優(yōu)解。若從標(biāo)準(zhǔn)形式無法看出初始可行基，則需采用兩段單純形法求解。7/22/202340MCM

上述算法中隱含著非退化假設(shè)，即要求B-1b>0。當(dāng)B-1b也存在零分量時，我們遇到了一個退化的基本可行解，此時rN存在負(fù)分量不一定說明現(xiàn)行基本可行解不是最優(yōu)解。單純形法也可能會遇到循環(huán)迭代。存在著幾種避免循環(huán)的技巧，例如，只要每次在rj

<0的非基變量中選取具有最小足標(biāo)者進(jìn)基即可避免產(chǎn)生循環(huán)。

變量同時具有上、下界限止的線性規(guī)劃問題也可化為標(biāo)準(zhǔn)形式求解，有興趣的讀者可以參閱D.G.魯恩伯杰的“線性與非線性規(guī)劃引論”一書的第三章。7/22/202341MCM§5.2運(yùn)輸問題運(yùn)輸問題的數(shù)學(xué)模型例5.3某商品有m個產(chǎn)地、n個銷地，各產(chǎn)地的產(chǎn)量分別為a1,…,am各銷地的需求量分別為b1,…,bn。若該商品由i產(chǎn)地運(yùn)到j(luò)銷地的單位運(yùn)價為Cij，問應(yīng)該如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最??？（注：標(biāo)準(zhǔn)的運(yùn)輸問題要求產(chǎn)銷平衡，即)7/22/202342MCM解：引入變量xij，其取值為由i產(chǎn)地運(yùn)往j銷地的該商品數(shù)量。例5.3的數(shù)學(xué)模型為(5.7)7/22/202343MCM

（5.7）顯然是一個線性規(guī)劃問題，當(dāng)然可以用單純形方法求解，但由于其約束條件的系數(shù)矩陣相當(dāng)特殊，求解它可以采用其他簡便方法。本節(jié)將介紹由康脫洛維奇和希奇柯克兩人獨立地提出的表上作業(yè)法（簡稱康—希表上作業(yè)法），其實質(zhì)仍然是先作出一個初始基本可行解，然后用最優(yōu)性準(zhǔn)則檢驗是否為最優(yōu)，并逐次改進(jìn)直至最優(yōu)性準(zhǔn)則成立為止。7/22/202344MCM初始可行解的選取

不難發(fā)現(xiàn)，（5.7）的約束條件中存在著多余方程（注：將前m個約束方程相加得到的方程與將后n個方程相加得到的方程相同，故約束條將是線性相關(guān)的）。容易證明，只要從中除去一個約束，例如最后一個方程，約束條件就彼此獨立了。因而，（5.7）是一個具有m×n個變量的線性規(guī)劃，其每一基本可行解應(yīng)含有m+n－1個基變量。記（5.7）約束條件中前m+n－1個方程的系數(shù)矩陣為A，A為（m+n－1）×mn矩陣，它的每一列最多只有兩個非零元素且非零元素均為1。利用線性代數(shù)知識能夠判定A中怎樣的m+n－1個列可以取為基（即怎樣的m+n－1個變量可以取為基變量）。

7/22/202345MCM為了判明哪些變量對應(yīng)的列是線性無關(guān)的，先引入下面的定義：定義5.3（閉回路）{xij}（i=1,…,m;j=1,…,n）的一個子集被稱為一個閉回路，若它可以被排成其中互異，也互異。

用下面的方法可以較方便直觀地看出{xij}的一個子集是否為一閉回路：作一個m行n列的表格，令位于該表格第m行第n列的格（i,j）對應(yīng)xij。將子集中的變量填于相應(yīng)的格中，將相鄰變量（或同行或同列）用邊相連，則此子集構(gòu)成閉回路當(dāng)且僅當(dāng)其點按上述連法作出的折線可構(gòu)成一個閉回路。7/22/202346MCM例如，當(dāng)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。。。。。。。。。。。。7/22/202347MCM定理5.4X為{xij}（i=1,…，m；j=1，…，n）的一個子集，X中的變量對應(yīng)的A中的列向量集線性無關(guān)的充要條件為X中不包含閉回路。

定理5.4不難用線性代數(shù)知識證明，詳細(xì)證明從略。根據(jù)定理5.4，要選?。?.7）的一組基變量并進(jìn)而得到一個基本可行解，只需選取{xij}的一個子集X，∣X∣=m+n-1且X中不含閉回路，其中∣X∣表示X中的變量個數(shù)。7/22/202348MCM我們用下面的例子來說明如何選取一個基本可行解。

例5.3給定運(yùn)輸問題如表5.12所示，表中左上角的數(shù)字為單位運(yùn)價Cij。易見，本例是產(chǎn)銷平衡的,即。表5.12銷地產(chǎn)地1234產(chǎn)量12211×3×413210×335×92537×8×14237銷量23467/22/202349MCM

現(xiàn)采用所謂“最小元素法”來求一組基本可行解。每次選取一個當(dāng)前單位運(yùn)價最小的變量為基變量。開始時，單位運(yùn)價最小的為C33=1，令x33=min{a3,b3}=4,并令x13=x23=0(銷地3已滿足)，相應(yīng)格打“×”（即不再考慮銷地3的需求）。產(chǎn)地3已運(yùn)出4單位，將產(chǎn)量改為剩余產(chǎn)量3。剩余表中單位運(yùn)價最小的為C11=2(或C34=2)，令x11=min{a1,b1}=2,并令x21=x31=0，相應(yīng)格打“×”，a1改為剩余產(chǎn)量1，…，直至全部產(chǎn)品分配完畢。注意到除最后一次分配外每次只能對一行或一列找“×”，表示某銷地已滿足，或某產(chǎn)地產(chǎn)品已分配完(注：當(dāng)兩者同時成立時只能打“×”行或列之一，將剩余需求量或產(chǎn)量記為0，此時基本可行基是退化的)。7/22/202350MCM顯然這樣分配共選出了m+n-1個變量，且這些變量的集合不含閉回路，從而構(gòu)成一個基本可行解。當(dāng)每一基變量xij選取時i產(chǎn)地的剩余商品量與j銷地的剩余需求量總不相等時，選出的基本可行解是非退化的。

初始基本可行解也可按其他方式選取，如“左上角法”等，其方法與原理是類似的，左上角法每次選取剩余表格中位于最左上角的變量，其余均相同。7/22/202351MCM最優(yōu)性判別

類似于單純形法，可計算非基變量的檢驗數(shù)，存在著多種求檢驗數(shù)的方法（求得的結(jié)果是相同的），下面介紹計算簡便且計算量也較小的“位勢法”。引入m+n個量（被稱為位勢）u1，…，um；u1，…，un。對每一變量xij，引入rij,令rij=Ｃij-ui-vj(事實上，這一公式與單純形法求檢驗數(shù)的公式是相同的)。對基變量xij，令rij=0，得到(xij為基變量)(5.8)7/22/202352MCM

齊次線性方程組（5.8）共有m+n－１個獨立方程，但含有m+n個變量。任取一個變量，例如u1作為自由變量，便可解出方程組。容易看出，u1的取值不同雖會改變位勢的取值但不會改變非基變量的檢驗數(shù)。因此，為方便起見，只要令u1＝０即可。事實上，我們甚至不必去解方程組（5.8），而只需令u1＝０，對所有基變量令ui＋vj＝cij，即cij-ui-vj＝０，在表上逐次求出所有位勢，進(jìn)而再對非基變量xij計算其檢驗數(shù)(5.9)7/22/202353MCM

例如，對表5.11中取定的基，我們求出位勢及非基變量的檢驗數(shù)，列于表5.13中，表中不帶圈的數(shù)為基變量取值，帶圈的數(shù)為非基變量檢驗數(shù)，右上角的數(shù)為單位運(yùn)價cij。表5.13u1=02211133041u1=510③335－392u3=-210⑦8121423υ1

=2υ２

=－2υ3

=3υ4

=47/22/202354MCM利用線性代數(shù)知識可以證明下列各定理(證明從略)：定理5.5任取一組非基變量，將其加入基變量集合中，則在所得變量集合中必存在唯一的閉回路，（注：因為加入新的列后得到的列向量組必定線性相關(guān)）。

易見閉回路中含有偶數(shù)個變量，若令進(jìn)基，令為保持平衡條件，位于偶數(shù)位置的變量必須減少θ，而位于奇數(shù)位置的變量則必須增加θ（注：）。7/22/202355MCM定理5.6設(shè)是非基變量與基變量集合的并集中唯一的閉回路，若令=θ并在閉回路上調(diào)整基變量取值使之平衡，得一可行解x，則x處的目標(biāo)值與原基本可行解上的目標(biāo)值之差為。根據(jù)定理5.6，若存在檢驗數(shù)的非基變量，取進(jìn)基（取正值）并令(5.10)則原取值為θ并位于偶數(shù)位置上的基變量退基，得一新的基本可行解，其目標(biāo)值減少

。7/22/202356MCM定理5.7設(shè)為（5.7）的一個基本可行解，若x0所有非基變量的檢驗數(shù)均非負(fù)，則x0必為（5.7）的一個最優(yōu)解。當(dāng)x0非退化時，此條件還是必要的。證明由定理5.6知，當(dāng)x0所有非基變量的檢驗數(shù)均非負(fù)時，任一非基變量進(jìn)基均不會使目標(biāo)值減小，由于（5.7）是線性規(guī)劃，此性質(zhì)表明x0已為最優(yōu)基本可行解。反之，則只要令具有負(fù)檢驗數(shù)的非基變量進(jìn)基即可（必能降低目標(biāo)函數(shù)值）。7/22/202357MCM綜上所述，康—希表上作業(yè)法可如下操作：步1：按最小元素法(或右上角法等)求一初始基本可行解。步2：按(5.8)求出位勢ui,υj(i=1,…,m;j=1,…,n)。進(jìn)而按(5.9)求出非變量的檢驗數(shù)rij。若一切rij≥0，則已求得一組最優(yōu)解。步3:任取<0，找出進(jìn)基后形成的唯一閉回路。在找出的閉回路上調(diào)整，按（5.10）取θ，得出新的基本可行解，返回步2。直至找到最優(yōu)解。7/22/202358MCM

對于例5.3，表5.12已給出非基變量的檢驗數(shù)。因r23<0，令x23進(jìn)基，得閉回路x23,x24,x34,x33,取θ=min{x24,x33}=2，調(diào)整后得到一個新的基本可行解。求出新的基本可行解對應(yīng)的位勢及非基變量檢驗數(shù)，列成表5.14。表5.14u1=02211113①41u1=310⑤33529②U3=－17⑥8⑨1235υ1

=2υ２

=0υ3

=3υ4

=4

現(xiàn)在，非基變量檢驗數(shù)均已非負(fù)，故已求得最優(yōu)解：x11=2，x14=1，x22=3，x23=2，x33=2，x34=5，其余=0（非基變量）。7/22/202359MCM

若運(yùn)輸問題是產(chǎn)銷不平衡的，則應(yīng)先將其轉(zhuǎn)化為產(chǎn)銷平衡的，然后再求解。例如，若產(chǎn)大于銷，可虛設(shè)一銷地（剩余產(chǎn)量存貯），將各產(chǎn)地運(yùn)往該虛設(shè)銷地的單位運(yùn)價均取為零；若供不應(yīng)求，則可虛設(shè)一個產(chǎn)地，產(chǎn)量為零，且由該產(chǎn)地運(yùn)到各個銷地的單位運(yùn)價均取零。通過這種虛設(shè)產(chǎn)地或銷地的方法即可將一個非標(biāo)準(zhǔn)形式的運(yùn)輸問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式的運(yùn)輸問題，從而可用上述康-希表上作業(yè)法加以求解。7/22/202360MCM

庫存管理在企業(yè)管理中占有很重要的地位。工廠定期購入原料，存入倉庫以備生產(chǎn)之用；商店成批購入各種商品，放在貨柜上以備零售；水庫在雨季蓄水，以備旱季的灌溉和發(fā)電；但是，細(xì)心的讀者會發(fā)現(xiàn)，這些情況下都有一個如何使庫存量最優(yōu)的問題，即庫存量應(yīng)取多大才最為合適？存儲量過大，存儲費(fèi)太高；存儲量過小，會導(dǎo)致一次性訂購的費(fèi)用增加，或不能及時滿足需求而遭到損失。為了保證生產(chǎn)的連續(xù)性和均衡性，需要確定一個合理、經(jīng)濟(jì)的庫存量，并定期訂貨加以補(bǔ)充，按需求發(fā)放，以達(dá)到壓縮庫存物資、加速資金周轉(zhuǎn)的目的?！?.3庫存問題7/22/202361MCM為說明方便，我們先簡要說明有關(guān)的概念，然后介紹幾種比較簡單的庫存模型和解法。

我們知道，工廠和企業(yè)作為一個系統(tǒng)，其基本功能是輸入、轉(zhuǎn)換和輸出。輸入過程也叫供應(yīng)過程，輸出過程也稱為需求過程。為保證生產(chǎn)正常進(jìn)行，供應(yīng)的數(shù)量和速度必須不小于需求的數(shù)量和速度，多余的數(shù)量可儲存于各部門的倉庫里。企業(yè)的倉庫按生產(chǎn)供應(yīng)和需求對象的不同，可大致分為兩類：原材料庫：用于存放生產(chǎn)所需的各原材料的倉庫，這些原材料大多是由物資供應(yīng)部門定期向外采購而來的，當(dāng)然，也可以是企業(yè)自己生產(chǎn)的。這類倉庫的庫存費(fèi)用由采購費(fèi)和保管費(fèi)兩部分構(gòu)成，即7/22/202362MCM半成品庫和成品庫：用于存放經(jīng)過生產(chǎn)加工而成的半成品和成品的倉庫。這類倉庫的最大存儲量一般就是生產(chǎn)批量，而庫存費(fèi)用由工裝調(diào)整費(fèi)和保管費(fèi)兩部分構(gòu)成，即易見，隨著生產(chǎn)批量得增大，計劃期(年)內(nèi)投產(chǎn)得批數(shù)減少，工裝調(diào)整得次數(shù)減少，工裝調(diào)整費(fèi)下降，但庫存量增加，保管費(fèi)用上升。因此，為降低庫存費(fèi)用，必須確定一個經(jīng)濟(jì)批量(或經(jīng)濟(jì)批數(shù))，使庫存費(fèi)用最小。7/22/202363MCM由上所述可見：在討論庫存問題時，涉及到三種費(fèi)用：（1）采購費(fèi)C是供應(yīng)部門處理訂貨、補(bǔ)充庫存所需的費(fèi)用，包括采購人員的差旅費(fèi)、手續(xù)費(fèi)、檢驗費(fèi)等。它屬于一次性費(fèi)用，直接與計劃期內(nèi)的采購次數(shù)n或一次采購量Q有關(guān)，計算公式為這里R為計劃期（年、季或月）內(nèi)的總需要量，Q為每批批量，c0為一次采購費(fèi)用。7/22/202364MCM（2）工裝調(diào)整費(fèi)S是指每批產(chǎn)品投產(chǎn)前的工藝準(zhǔn)備、設(shè)備調(diào)整及其檢修所需的費(fèi)用。屬于一次性的費(fèi)用，它與計劃期內(nèi)投入的批數(shù)有關(guān)，計算公式為其中為R計劃期內(nèi)的總產(chǎn)量，Q為生產(chǎn)批量，c1為一次工裝調(diào)整費(fèi)用。（3）保管費(fèi)H損耗費(fèi)和庫存物資折算成資金的利息等，保管費(fèi)的計算方法與保管方式、消費(fèi)方式等等有關(guān)，假如消費(fèi)速度是均勻的，通?？捎孟旅娴墓絹碛嬎?/22/202365MCM

其中為平均庫存量，為單位物資在計劃期內(nèi)的保管費(fèi)，單位物資有時按重量計，有時按占用倉庫的面積(或體積)計，是具體情況而定。由于單件保管費(fèi)有時計算起來比較困難，也可用保管費(fèi)率i計算，i為保管費(fèi)占總庫存費(fèi)的百分比，這時公式可以改寫為

這里為P庫存物資的單價，為平均保管費(fèi)率。應(yīng)該指出的是：保管費(fèi)是一項可觀的、不可忽視的費(fèi)用，依據(jù)70年代中期美國十大公司的統(tǒng)計，它約占總庫存物資資金的20%，其中以庫存物資資金的利息占的份額最大。7/22/202366MCM下面我們分幾種情況來說明幾種較為簡單的庫存模型一：瞬時送貨的確定型庫存問題(不允許缺貨的情況)

首先考慮最簡單的庫存問題。假設(shè)某工廠生產(chǎn)需求速率穩(wěn)定，庫存下降到零時，再定購進(jìn)貨，一次采購量為Q，定購點的提前時間為零（即進(jìn)貨有保障、有規(guī)律，可根據(jù)需求提前訂貨），在保證不缺貨的條件下，試確定最經(jīng)濟(jì)的采購量，使庫存費(fèi)用最小。此時庫存費(fèi)用為7/22/202367MCM在本模型中，平均庫存量為常量，所以問題歸結(jié)為求解如下的優(yōu)化問題這是一個一元函數(shù)求極小值的問題，可用微積分方法求其最優(yōu)解，求得的解為這就是所要求的經(jīng)濟(jì)采購量。而庫存的最小費(fèi)用為經(jīng)濟(jì)學(xué)上稱這兩個公式為平方根公式。7/22/202368MCM二：非瞬時送貨的確定型庫存問題(不允許缺貨的情況)在本模型中，由于運(yùn)輸設(shè)備等的限制，經(jīng)常會出現(xiàn)非瞬時入庫的情況，即從再定購點開始的一段時間內(nèi)，一方面按一定進(jìn)度入庫(設(shè)r1為定購物資每天入庫的數(shù)量)，另一方面按生產(chǎn)需要出庫(設(shè)r2<r1為定購物資在入庫期內(nèi)每天出庫的數(shù)量)，直到達(dá)到最大庫存量QM為止。設(shè)模型的其他參數(shù)不變，試確定經(jīng)濟(jì)采購量Q*和最小庫存費(fèi)用T*。易見為定購物資的入庫時間（天），所以最大庫存量為7/22/202369MCM平均庫存量為

因此保管費(fèi)為

庫存費(fèi)用為所以這一類庫存問題歸結(jié)為求解7/22/202370MCM

這仍然是一個一元函數(shù)求極小值的問題，用微積分方法求得最優(yōu)解Q*即經(jīng)濟(jì)采購量為而最小庫存費(fèi)用為對于成品庫和半成品庫的庫存問題可以類似地進(jìn)行分析，參看下例。

7/22/202371MCM例5.4某廠年計劃生產(chǎn)6500件產(chǎn)品，設(shè)每個生產(chǎn)周期的工裝調(diào)整費(fèi)為200元，每年每件產(chǎn)品的儲存費(fèi)為3.2元，每天生產(chǎn)產(chǎn)品50件，市場需求26(件/天)，每年工作300天，試求最經(jīng)濟(jì)的生產(chǎn)批量Q*和最小的庫存費(fèi)用T*。解在此問題中，一次工裝調(diào)整費(fèi)用c1=200元，年計劃產(chǎn)量R=6500件，設(shè)該廠每批生產(chǎn)Q件產(chǎn)品，則工裝調(diào)整費(fèi)為而保管費(fèi)為

7/22/202372MCM其中cH=3.2(元／件年)，r1＝50件，r2＝26件，所以問題歸結(jié)為求解用微積分方法容易計算的最經(jīng)濟(jì)的生產(chǎn)批量為而最小庫存費(fèi)用為

上面介紹的兩種模型是最簡單、也是最基本的確定型庫存模型。它不允許缺貨，故假設(shè)條件非常理想，但實際情況卻要復(fù)雜得多。7/22/202373MCM下面我們再來看看允許缺貨的庫存模型。三：瞬時送貨的確定型庫存問題(允許缺貨的情況)上述模型不允許缺貨，若允許缺貨，則需要支付一定的缺貨損失費(fèi)用Z。

我們假設(shè)Q2為缺貨量，單位缺貨在單位時間內(nèi)產(chǎn)生的缺貨損失費(fèi)用為cZ(元)，單位物資在單位時間內(nèi)的保管費(fèi)為ch(元)，D為單位時間內(nèi)物資的需求量，問每次采購量Q、缺貨量Q2取為何值時，才能使庫存費(fèi)用T和缺貨損失費(fèi)用之和最小？7/22/202374MCM我們不妨設(shè)總費(fèi)用為F則

其中為采購費(fèi)，c0為每次的采購費(fèi)。為保管費(fèi)，為平均庫存量，這里，為單位物資在計劃期內(nèi)的保管費(fèi)，t1為一個采購周期內(nèi)物資的存儲時間。所以保管費(fèi)為注意到，上式可改寫為7/22/202375MCM注意到，則上式可改寫為因此上述庫存問題歸結(jié)為求解7/22/202376MCM

容易證明它們即為使總費(fèi)用取得最小值的經(jīng)濟(jì)采購量Q*和最經(jīng)濟(jì)的缺貨量Q2*，而最小費(fèi)用為。

這是一個求二元函數(shù)的極小值的問題，仍可用微積分方法求解得到7/22/202377MCM

秘魯是一個捕魚業(yè)非常發(fā)達(dá)的國家，隨著人們對魚粉需求量的增長，秘魯?shù)牟遏~量不斷增加。到1960，秘魯已成為世界上捕魚量最大的國家，年捕魚量達(dá)到1000萬噸，約占全球捕魚總量的15%。捕魚量的穩(wěn)定增長使海洋生物學(xué)家越來越感到不安，1972年，生物學(xué)家們認(rèn)為，秘魯捕魚量已達(dá)到了能維持魚群正常生長情況下的最大捕獲量的兩倍，政府如再不加以控制，采取措施制止幾近瘋狂的捕撈，秘魯?shù)臐O業(yè)資源將趨于枯竭，漁業(yè)生產(chǎn)會陷入完全崩潰的境地(Paulik,1971)。到1973年，生物學(xué)家們的擔(dān)憂開始顯現(xiàn)。當(dāng)年，秘魯沿海的魚量猛減，漁民幾乎無魚可捕，出現(xiàn)了所謂“鳀魚危機(jī)”(Idyll，1973年)，并引起了全世界范圍內(nèi)糧食價格的上漲?！?.4最佳捕魚方案7/22/202378MCM下表是秘魯海洋學(xué)院1974年提供的秘魯漁業(yè)的歷史統(tǒng)計數(shù)據(jù)：

表5.15年份船數(shù)捕魚日數(shù)捕魚量(百萬噸)1959196019611962196319641965196619671968196919701971197219734146677561069165517441623165015691490145514991473139912562942792982942692972651901701671621808989271.912.934.586.276.428.867.238.539.8210.628.9612.2710.284.451.787/22/202379MCM

如何制定最優(yōu)捕魚方案，在不破壞魚類生態(tài)平衡的前提下獲得最大的捕魚量呢？魚類學(xué)家M.Schaefer于1975年在Logistic模型的基礎(chǔ)上建立了捕魚問題的優(yōu)化模型，提出了一個最優(yōu)捕魚方案的建議。以下，讓我們來看看他所建立的模型。用x(t)記t時刻海洋中魚的數(shù)量，r為魚的凈增長率，K為環(huán)境所能供養(yǎng)的飽和魚量。

假設(shè)(1)在無捕撈情況下，魚類按Logistic模型增長，即魚的數(shù)量滿足Logistic模型：(5.11)7/22/202380MCM(2)考慮捕魚對魚類生長的影響。令h為捕撈率，，此時，魚類增長滿足的微分方程為：(5.12)

捕撈率取h=qEx為的原因是捕獲量與海洋中現(xiàn)有的魚量成正比。q表示捕撈系數(shù)，與捕撈的生產(chǎn)水平有關(guān)，捕魚的工具越先進(jìn)q就越大，為降低漁民的勞動強(qiáng)度，自然q越大越好。然而，正如前面所說，政府應(yīng)當(dāng)控制漁民的捕魚，不能隨其任意捕撈。控制的強(qiáng)度通過一個被稱為捕撈能力的系數(shù)E來調(diào)節(jié)(可以用規(guī)定禁止捕魚的休漁期或劃定禁漁區(qū)域的方法來實現(xiàn))。7/22/202381MCM

正如第三章中Logistic模型所指出的，微分方程(5.11)有一個平衡解x=K，當(dāng)x(t)≠K時，隨著t趨于無窮，將有x(t)→K

。對于微分方程(5.12)，平衡點的位置發(fā)生了改變，它被移到了方程的根處，滿足，即(5.13)易見，為二次曲線(5.14)7/22/202382MCM與直線的交點

(5.15)見圖5-2。(圖5-2)7/22/202383MCM令

顯然，，將在處展開成(5.16)求導(dǎo)得

(1)若，(此時，即捕撈率小于魚的內(nèi)稟增長率)，則當(dāng)時，從而，，x(t)隨時間t而增大并趨向于，當(dāng)時，從而，，x(t)隨時間t而減小并趨向于?？傊?，此時x(t)隨時間t的增大必趨向于平衡點，此時平衡點是穩(wěn)定的平衡點。7/22/202384MCM(2)反之，若，則類似可證，隨著時間t的增大，x(t)將遠(yuǎn)離平衡點，此時，平衡點是非穩(wěn)定的。當(dāng)然，這一結(jié)果是十分明顯的，因為在時，，捕撈率超過了魚的增長率，海洋中的魚類數(shù)量將越來越少，最終必將趨于絕滅。(3)若，則尚需檢查的符號。根據(jù)以上分析，捕魚必須控制在(即)的限度以內(nèi)，現(xiàn)在我們將進(jìn)一步分析，在此前提下，又應(yīng)如何捕魚，才能使每年的捕獲總量最大。

7/22/202385MCM為此，將(5.13)代入捕魚量公式，得到在平衡條件下的捕魚量：(5.17)為求捕魚量最大，令，求得，將其代入(5.17)式，即可求得最大捕獲量，此時7/22/202386MCM

上述結(jié)果也可從圖5-2中看出，如取，曲線與的交點記為，則易見在射線(5.15)與二次曲線(5.14)的交點中，過的一條在交點處具有最大的縱坐標(biāo)(即最大捕獲量)。

通常情況下，漁民考慮的主要還是經(jīng)濟(jì)利益的最大化，此時，模型將變得復(fù)雜一些。設(shè)魚的單價為p，單位時間的捕撈成本為CE，則由時刻a到時刻b這段時間內(nèi)漁民捕魚的收益最大，約束條件為(5.12)式成立，即此時要求解的問題為7/22/202387MCM(5.18)是一個泛函極值問題，可用歐拉方程求解，因本書不準(zhǔn)備介紹求解泛函極值的變分方法，我們只建立了此問題的數(shù)學(xué)模型，而不討論其求解，有興趣的讀者可參考楊啟帆、邊馥萍編著的數(shù)學(xué)模型。(5.18)7/22/202388MCM

在森林失火時，消防站在接到警報后應(yīng)派多少消防隊員前去救火呢？顯然，派的隊員越多，滅火的速度越快，火災(zāi)造成的損失越小，但反過來，救援的開支會增加。所以我們要綜合考慮森林損失費(fèi)、救援費(fèi)與消防隊員人數(shù)之間的關(guān)系，以最小費(fèi)用原則來決定派出隊員的數(shù)目。即應(yīng)當(dāng)考慮：派出多少隊員救火，才能使火災(zāi)損失費(fèi)和救火費(fèi)用之和（簡稱總費(fèi)用）最??？§5.5森林救火費(fèi)用最小問題7/22/202389MCM我們先做如下分析：

(１)火災(zāi)損失費(fèi)通常與森林被燒毀的面積成正比，而燒毀面積與開始失火到火被撲滅之間的間隔時間有關(guān)，滅火時間又取決于消防隊員的數(shù)目，隊員越多滅火越快。

記失火時刻為t=0，開始救火時刻為t=t1，火被撲滅的時刻為t=t2。設(shè)在時刻森林燒毀面積為B(t2)，則造成損失的森林燒毀面積為。由導(dǎo)數(shù)的定義，易見表示單位時間內(nèi)燒毀的森林面積，也表示火勢蔓延的速度。當(dāng)t=0,t2時，，設(shè)在t=t1時，取得最大值h。7/22/202390MCM(2)救援費(fèi)用包括兩部分：一部分是滅火器材的消耗和消防隊員的薪金等，與隊員人數(shù)和滅火所用時間有關(guān)；另一部分是運(yùn)送隊員和器材等的一次性支出，只與隊員人數(shù)有關(guān)。在上述分析的基礎(chǔ)上，我們再作如下模型假設(shè)：(1)損失費(fèi)與森林燒毀面積B(t2)成正比，比例系數(shù)c1為燒毀單位面積的損失費(fèi)。(2)從失火到開始救火這段時間()內(nèi)，火勢蔓延速度與時間t成正比，記比率系數(shù)為火勢蔓延速度。在這里，我們有必要指出，這個假設(shè)在風(fēng)力不大的條件下是大致合理的。7/22/202391MCM(3)派出消防隊員x名，開始救火以后()，火勢蔓延速度降為，其中可以看成每個隊員的平均滅火速度，顯然應(yīng)該有。(4)每個消防隊員單位時間的費(fèi)用為c2，于是每個隊員的救火費(fèi)用是；每個隊員的一次性支出(如交通費(fèi)等)是c3。

與t的關(guān)系如圖5-3所示。7/22/202392MCM(圖5-3)7/22/202393MCM

由圖5-3及假設(shè)2、3我們可以得到如下關(guān)系式：

又于是再根據(jù)假設(shè)條件1、4，森林損失費(fèi)為救援費(fèi)為

于是我們得救火總費(fèi)用為此即為這個優(yōu)化模型的目標(biāo)函數(shù)。7/22/202394MCM這是一個一元函數(shù)的極值問題。令，可以得到應(yīng)該派出的隊員人數(shù)為

7/22/202395MCM

光在由一種介質(zhì)進(jìn)入另一種介質(zhì)時，在界面處會發(fā)生折射現(xiàn)象。人們發(fā)現(xiàn)，折射現(xiàn)象造成的結(jié)果是所謂“最短時間”效應(yīng)，即光線會走最快的路徑?！?.6光學(xué)中的折射原理設(shè)光在介質(zhì)1中的傳播速度為v1而在介質(zhì)2中的傳播速度為v2

。在同一種介質(zhì)中，光的傳播速度是常數(shù)，因而，在同種介質(zhì)中它將沿著直線方向傳播。現(xiàn)取兩種介質(zhì)的分界面上的一條直線為x軸，設(shè)一束光線由介質(zhì)1中的A(0，a)點經(jīng)x軸上的O點(取為坐標(biāo)原點)進(jìn)入介質(zhì)2，并沿某直線方向行進(jìn)到B(d，b)點。設(shè)直線段AP與x軸的法線的夾角為、直線段PB與x軸的法線的夾角為。7/22/202396MCM

下面，我們將根據(jù)最短時間效應(yīng)來推導(dǎo)出光學(xué)中的折射定理。光線由A傳到B所需的時間為光線由O傳到B所需時間為故光線由A傳播到B的總時間為7/22/202397MCM最短時間效應(yīng)對應(yīng)的優(yōu)化問題為([0，d])

令得(5.19)注意到

7/22/202398MCM(5.9)時又可寫成此即光學(xué)中的折射定理。7/22/202399MCM

在長期的生物進(jìn)化過程中，動物體內(nèi)的結(jié)構(gòu)已趨于某種程度的最優(yōu)化狀態(tài)，本節(jié)將舉兩個實例來加以說明。本節(jié)采用的方法不同于一般的優(yōu)化問題的研究，在一般優(yōu)化問題中，我們研究的問題是為了達(dá)到某種意義下的最優(yōu)化，人們應(yīng)當(dāng)如何去做。而本節(jié)要研究的卻是：假設(shè)生物的結(jié)構(gòu)在進(jìn)化過程中不斷優(yōu)化，適者生存，逐步達(dá)到了某種意義下的最優(yōu)化，那么，生物的結(jié)構(gòu)應(yīng)當(dāng)具有哪些特征？§5.7身體結(jié)構(gòu)得優(yōu)化7/22/2023100MCM例5.5血管的分支

假設(shè)動物的血管系統(tǒng)經(jīng)長期進(jìn)化，幾何形狀已經(jīng)達(dá)到了使能量消耗大到最低的優(yōu)化標(biāo)準(zhǔn)。血液在動物的血管中不停地循環(huán)流動著，在此過程中消耗的總能量顯然與血管系統(tǒng)的幾何形狀有關(guān)。我們不可能討論整個血管系統(tǒng)的幾何形狀，那樣的話會涉及到太多的生理知識，對此我們甚至尚未完全搞清楚。在本節(jié)中，我們只研究血管分支處粗細(xì)血管半徑的比例和分岔角度，我們希望知道，它們在消耗能量最小的原則下應(yīng)取何值。

7/22/2023101MCM為研究這一問題，我們先做如下假設(shè)：(1)一條粗血管在分支處只分成；兩條較細(xì)得血管，在分支點附近三條血管位于同一平面，并且有一對稱軸。如若不然，血管長度增加必然導(dǎo)致能量消耗得增加，不符合優(yōu)化原則，我們稱此假設(shè)為幾何假設(shè)。(2)在考察血液流動受到的阻力時，將這種流動視為粘性液體在剛性管道內(nèi)的運(yùn)動，即將血管近似看成剛體，這是一種近似。事實上血管是有彈性的，這種近似對結(jié)果的影響很小，我們稱之為物理假設(shè)。(3)血液對血管提供的營養(yǎng)隨著管壁內(nèi)表面積和管壁的厚度的增加而增加。管壁厚度和血管半徑成正比，我們稱之為生理假設(shè)。7/22/2023102MCM根據(jù)幾何假設(shè)，我們作血管分支圖5-4如下：（圖5-4）7/22/2023103MCM

圖中一條粗血管與兩條細(xì)血管在C點分岔，并形成對稱的幾何圖形。粗細(xì)血管的半徑分別為r和r1，分岔處角度為?？疾扉L度為的一段粗血管AC和長度為的細(xì)血管CB和，ACB()的水平和垂直距離為L和H，另外血液在粗細(xì)血管中單位時間內(nèi)的流量分別為q和q1，顯然。

由假設(shè)2，根據(jù)流體力學(xué)定律：粘性物質(zhì)在剛性管道內(nèi)流動所受到的阻力與流速的平方成正比，與管道半徑的四次方成反比。從而血液在粗細(xì)血管內(nèi)受到阻力分別為和，其中k為比率系數(shù)。7/22/2023104MCM

由假設(shè)3，在單位長度的血管內(nèi)，血液為管壁提供營養(yǎng)所消耗的能量為，其中b為比率系數(shù)。

根據(jù)上述假設(shè)及對假設(shè)的進(jìn)一步分析，我們可以得到血液從粗血管A點流動到細(xì)血管B點，用于克服阻力及給管壁提供營養(yǎng)所消耗的能量為(5.20)另外由血管幾何圖形易得：(5.21)7/22/2023105MCM將（5.21）代入（5.20），并注意到，得

要使總能量消耗達(dá)到最小，應(yīng)求解此多元函數(shù)最小值問題，根據(jù)必要條件，應(yīng)有