現(xiàn)代物流運籌學 教學課件 ppt 作者 沈家驊 24320-電子教案-第2章線性規(guī)劃單純形法

1、第2章線性規(guī)劃單純形法,學習目標,? 用單純形法等進行求解，學習對偶問題及實際案例，使學生學會把實際問題歸結(jié)為線性規(guī)劃問題來進行優(yōu)化，并能用一些常用的方法進行求解，從而培養(yǎng)和提高學生分析問題、解決實際問題的能力。? 培養(yǎng)優(yōu)化思想，并能用一定的數(shù)學方法實現(xiàn)優(yōu)化。,2.1 線性規(guī)劃問題的標準型,? 由上一章可知，線性規(guī)劃模型有各種不同的形式；即目標函數(shù)可以求極大值，也可以求極小值；約束條件可以是等式也可以是不等式，不等號可以是“≤”

2、也可以是“≥”；決策變量一般是非負的，但在理論模型中可能會允許在區(qū)間（?∞，+∞）內(nèi)取值。,? 為適應通用的代數(shù)求解方法，將不同形式的線性規(guī)劃模型轉(zhuǎn)化為統(tǒng)一的標準形式是十分必要的。,? 線性規(guī)劃問題的數(shù)學模型，都是由決策變量、約束條件（線性等式或不等式）及目標函數(shù)（最大或最?。?部分組成的。 ? 為了使線性規(guī)劃問題的求解變得盡可能簡化，我們需要規(guī)定線性規(guī)劃模型的標準形式。,2.1.1 線性規(guī)劃問題的標準型,? 一般線性規(guī)劃問題的標

3、準型為,,? 或簡記為,,? 上述標準型有以下4個特征。（1）目標函數(shù)值總為求最大。（2）約束條件全為線性等式。（3）約束條件右端常數(shù)項全部為非負數(shù)。（4）決策變量全大于或等于零。,2.1.2 非標準型線性規(guī)劃問題的標準化,（1）若目標函數(shù)取最小值min z = CX，由于求z的最小值就是求?z的最大值，所以可以將其轉(zhuǎn)化為max (?z) = ?CX。,（2）當約束條件中第個方程出現(xiàn)ai

4、1x1 + ai2x2 + …+ ainxn≤bi時，則增加一個“松弛變量”xi?1≥0，使它成為等式ai1x1 + ai2x2 + … + ainxn + xi?1 = bi。,? 同樣，當約束條件中第個方程出現(xiàn)ai1x1 + ai2x2 + … + ainxn≥bi時，則減去一個“松弛變量”xi?1≥0，使它成為等式ai1x1 + ai2x2 + … + ainxn ? xi?1 = bi。,

5、（3）當決策變量xj不滿足xj ≥0時，則增加兩個新的非負決策變量x'j ≥0和x"j ≥0，用x'j ? x"j替代xj，即令xj = x'j ? x"j。（4）當約束條件中第i個方程右端出現(xiàn)常數(shù)項bi＜0時，則在方程兩邊同時乘（?1），得到?bi ＞0。,? 例2.1 將下列非標準型線性規(guī)劃問題化為標準型。,,? 解 按照前面的變換方法，執(zhí)行下列步驟。（1）將min z轉(zhuǎn)

6、化為max (?z)。（2）令x3 = x'3? x"3，且x'3≥0，x"3≥0。,（3）將第一個約束方程的左邊減去一個非負的松弛變量x4，將第2、第3個約束方程的左邊分別加上一個非負的松弛變量x5和x6。,? 這樣，可以將原來的線性規(guī)劃問題標準化為,,,,2.1.3 單純形法的基本步驟和計算,? 兩個變量的線性規(guī)劃問題可以用圖解法進行求解，而當變量是三個或三個以上且約束條件又多時，可行域所在的

7、凸集表現(xiàn)為一個凸多邊形，在空間上必將是一個凸幾何體。,? 因此我們幾乎或?qū)嵲跓o法通過作圖來找可行域，更無法找到最優(yōu)解，此時圖解法就顯得無能為力了，但這些問題可以利用單純形法進行求解。,（1）基變量—在標準型每一個約束方程中選一個變量xj，它在該方程中的系數(shù)為1，在其他方程中系數(shù)為零，這個變量xj就稱為基變量，或稱為基礎變量。,? 如有m個約束方程，就可得到m個基變量，其余變量就稱為非基變量。,（2）基本可行解—非基變量為零的可行解。（

8、3）基本最優(yōu)解—滿足目標函數(shù)的基本可行解，簡稱為最優(yōu)解。,? 例2.2 求解線性規(guī)劃問題，其模型如下：,? 解 （1）將線性規(guī)劃問題化為標準型。? 引入松弛變量x3 , x4 , x5后將其轉(zhuǎn)化為標準型，即,（2）列出初始單純形表（見表2.1），并在表中計算出檢驗數(shù)?j。,① zj行的計算。,? 用Cj列（Cj列指目標函數(shù)中基變量的系數(shù)CB）中各數(shù)乘決策變量列的相對應數(shù)后再相加，即，具體計算結(jié)果如下：,② ?j行的計算。,? ?

9、j = Cj ? zj，即用Cj行各數(shù)減去zj行相對應數(shù)，稱為檢驗數(shù)。 ? 一般地，?j≤0表示基本可行解達到最優(yōu)；否則?j中有一正數(shù)就要繼續(xù)進行迭代運算，向最優(yōu)解逼近。,? 這里，?1 = 3 ? 0 = 3，?2 = 2?0 = 2，?3 = ?4 = 

10、;?5 = 0 ? 0 = 0，所以要繼續(xù)迭代運算。,（3）確定主元列，選擇進基變量。（4）確定主元行，選擇離基變量。,（5）對增廣矩陣用初等行變換將主元化為1，主元所在列其余元素化為零。（6）重新按第3步驟和第4步驟對表2.2確定主元列與主元行及主元，選擇進基變量與離基變量。,（7）對增廣矩陣用初等行變換將主元[5]化為1，將主元[5]所在第二列其余元素化為零，得表2.3

11、。,? 例2.3 求解線性規(guī)劃問題，其模型如下：,? 解 先化為標準型，再用單純形法。? 將求解的一系列單純形表匯總于表2.4中。,2.2 改進的單純形法和對偶問題,2.2.1 改進的單純形法? 單純形法的實質(zhì)是從一個基本可行解走向另一個基本可行解，一步步地達到最優(yōu)解的迭代過程。,? 改進的單純形法與表格形式的單純形法，其實質(zhì)完全一樣，只是計算形式不同。 ? 表格形式的單純形法，方法簡單，容易掌握，非常適用于手算

12、，且在電子計算機上用于求解小型線性規(guī)劃問題時，也是比較方便的。,? 但由于在計算機上使用表格式的單純形法需要把整個表格儲存在計算機中，因此這種方法不適合求解較大規(guī)模的線性規(guī)劃問題。,? 而改進的單純形法，一般說來，不適合用于手工計算，但較大規(guī)模的線性規(guī)劃問題，其約束方程組的系數(shù)矩陣往往是稀疏的（即矩陣中的大多數(shù)元素為零），于是利用計算機上數(shù)據(jù)處理的某些技巧，就可以在電子計算機上使用改進的單純形法處理較大規(guī)模的線性規(guī)劃問題了。,? 這就是

13、改進的單純形法的最主要的優(yōu)點。 ? 無論使用哪一種形式，經(jīng)驗表明，要解一個含有m個約束條件的線性規(guī)劃問題，大約只要經(jīng)過m～1.5m次迭代就可以了。 ? 因此，單純形方法是一種非常有效的計算方法。,2.2.2 對偶問題,1．線性規(guī)劃對偶問題的提出? 線性規(guī)劃對偶理論是線性規(guī)劃理論中一個非常有趣的概念，它充分顯示了線性規(guī)劃理論邏輯的嚴謹性和結(jié)構(gòu)的對稱美。 ? 線性規(guī)劃問題與其對偶線性規(guī)劃問題在模型的表現(xiàn)形式和問題的解之間存在

14、著緊密的聯(lián)系。,? 例2.4 家具廠生產(chǎn)桌子和椅子兩種家具，有關(guān)資料如表2.5所示。 ? 問該家具廠應如何安排生產(chǎn)才能使每月的銷售收入最大？,? 解 用x1和x2分別表示兩種產(chǎn)品的產(chǎn)量，則其線性規(guī)劃模型為,,? 該問題的對偶問題可以表述為如下模型：該模型稱為原模型P的對偶規(guī)劃D。,2．對偶規(guī)劃的一般數(shù)學模型,? 由例2.4可知，線性規(guī)劃原問題和其對偶規(guī)劃問題之間有很多聯(lián)系。,? 例如，原問題是求目標函數(shù)最大化，則對

15、偶問題即求目標函數(shù)最小化；原問題目標函數(shù)的系數(shù)變成對偶問題的右邊項，原問題的約束的右邊項變?yōu)閷ε紗栴}目標函數(shù)的系數(shù)，即對偶問題的系數(shù)矩陣是原問題系數(shù)矩陣的轉(zhuǎn)置。,? 原問題的模型如果表示如下：,? 則相應的對偶問題的一般模型表示如下：,? 例2.5 設線性規(guī)劃原問題的模型如下：,? 解 根據(jù)對偶規(guī)劃規(guī)則，可以得到線性規(guī)劃原問題的對偶模型為,2.3 線性規(guī)劃問題的應用案例,? 線性規(guī)劃問題的應用十分廣泛，在運輸問題、設備的合理利用問題

16、、下料問題、營養(yǎng)搭配問題等各方面均有應用。,運雜費 = 運費 + 裝卸費 + 中途存儲費 + 損耗費? 在表2.6中，某些空格沒有填數(shù)表示此路線不通或明顯不合理，計算時可以取一個相當大的正數(shù)M。,? 通過計算機處理和計算后得到該線性規(guī)劃問題的解如表2.7所示。,2.4 單純形法的原理,? 線性規(guī)劃的最優(yōu)解一定可以在線性規(guī)劃可行域的某個頂點上達到。 ?

17、 實際上對于任意一個有n個變量的線性規(guī)劃問題，如果它有有界的線性規(guī)劃可行域，則它的最優(yōu)解必然在所有約束條件的交點處取得。,? 而一個有界的線性規(guī)劃可行域，其頂點個數(shù)必然是有限的。? 因此，求線性規(guī)劃的最優(yōu)解時，只要在線性規(guī)劃可行域的有限個頂點上去尋找即可。,? 用單純形法解題分為兩個階段：第一階段是尋求一個可行解，經(jīng)檢驗若不是最優(yōu)解，則轉(zhuǎn)入第二階段；第二階段從所求出的可行解出發(fā)，通過變量的調(diào)整求出新的可行解。,? 調(diào)整的方法是從一個

18、基本可行解出發(fā)，設法得到另一個更好的基本可行解，直到目標函數(shù)達到最優(yōu)時，基本可行解即為最優(yōu)解。,? 如果仍然不是最優(yōu)解，則重復進行調(diào)整。 ? 每調(diào)整一次，目標函數(shù)就改進一次（在線性規(guī)劃問題的標準型中，目標函數(shù)值總是大于或等于前面得到的解的目標函數(shù)值），直到求得最優(yōu)解。,圖2.1 利用單純形法求解線性規(guī)劃問題的流程,2.5 線性規(guī)劃問題的Excel處理,2.5.1 電子表格軟件Excel簡介 ? 電子表格實際上就是用于顯示和管理

19、數(shù)據(jù)，并能對數(shù)據(jù)進行各種復雜統(tǒng)計運算的表格。,? Excel能以表格形式提供以下功能：? 強大（或萬能）的表格計算功能；? 方便的制表和圖形制作功能；? 靈活的數(shù)據(jù)庫管理功能；? 強大的科學計算功能；? 多方面的數(shù)據(jù)分析功能。,? 目前，我國對于Excel的應用，主要用于畫表格，或作簡單的計算，或圖形制作，僅限于很初級的應用，其他方面的功能用得很少。,? 電子表格軟件Excel與Lotus公司的Lotus1-2-3

20、有類似結(jié)構(gòu)：它們以工作簿為文件單位，一個工作簿可以包含若干（Excel 2003最多256個，取決于內(nèi)存的大?。┕ぷ鞅恚粋€工作表又可以包含很多的單元格。,? 在系統(tǒng)中安裝“規(guī)劃求解”工具的方法如下。（1）啟動Excel 2003。 ? 打開“工具”菜單，如果沒有“規(guī)劃求解”選項，單擊“加載宏”，如圖2.2所示。? 彈出以下窗口，如圖2.3所示。,圖2.2 安裝“規(guī)劃求解”選項的加載宏窗口,圖2.3 選中“規(guī)劃求解”加載宏,（

21、2）安裝“規(guī)劃求解”工具。,? 在“當前加載宏”的復選框中選中“規(guī)劃求解”，單擊“確定”按鈕后返回Excel。 ? 這時在“工具”菜單中就出現(xiàn)了“規(guī)劃求解”選項，如圖2.4所示。 ? 關(guān)閉“工具”菜單。,圖2.4 安裝后在工具菜單中出現(xiàn)“規(guī)劃求解”選項,2.5.2 使用Excel建立數(shù)學公式并輸入數(shù)據(jù),? 使用Excel 2003建立數(shù)學公式的基本步驟如下。第一步，在工作表的頂部輸入數(shù)據(jù)。第二步，確定每個決策變量所對應的

22、單元格的位置。第三步，選擇單元格輸入格式，找到目標函數(shù)的值。,第四步，選擇一個單元格輸入公式，計算每個約束條件左邊的值。第五步，選擇一個單元格輸入公式，計算每個約束條件右邊的值。,? 為了說明其具體應用過程，下面討論一個簡單的實例。,? 解 將P公司的問題表述為以下的線性規(guī)劃模型：,,? 約束條件為,,? 應用Excel工具解決該問題的具體步驟如下。第一步，在工作表的頂部輸入問題的數(shù)據(jù)。第二步，確定每個決策變量所對應的單元格的

23、位置。,圖2.5 P公司優(yōu)化問題數(shù)據(jù)輸入和公式建立,第三步，選擇一個單元格輸入用來計算目標函數(shù)值的公式。第四步，選擇單元格輸入公式，計算每個約束條件左邊的值。第五步，選擇一個單元格輸入公式，計算每個約束條件右邊的值,2.5.3 使用Excel求解,? 由Microsoft公司開發(fā)的Excel 2003解決工具，可以用來解決本課程中所有的線性規(guī)劃問題。,第一步，選擇“工具”下拉菜單。第二步，選擇“規(guī)劃求解”選項。第三步，當出現(xiàn)

24、“規(guī)劃求解參數(shù)”對話框時，如圖2.6所示，在“設置目標單元格”欄輸入B18，“等于”后選擇“最大值”項，在“可變單元格”欄輸入B16:C16，然后單擊“添加”按鈕。,圖2.6 P公司問題的“規(guī)劃求解參數(shù)”對話框,第四步，當彈出的“添加約束”對話框出現(xiàn)時，在“單元格引用位置”框中輸入B21:B24，選擇＜=，在“約束值”框中輸入D21:D24，然后單擊“確定”按鈕。第五步，當“規(guī)劃求解參數(shù)”對話框出現(xiàn)時，選擇“選項”。,第六步，當“規(guī)

25、劃求解選項”對話框出現(xiàn)時，選擇“假定非負”，單擊“確定”按鈕。第七步，當“規(guī)劃求解參數(shù)”對話框出現(xiàn)時，選擇“求解”。第八步，當“規(guī)劃求解結(jié)果”對話框出現(xiàn)時，選擇“保存規(guī)劃求解結(jié)果”，單擊“確定”按鈕。,圖2.7 第六步“規(guī)劃求解選項”對話框,圖2.8 Excel對P公司的問題的求解結(jié)果,? 對于“規(guī)劃求解選項”對話框中有一些參數(shù)，通過設置這些參數(shù)的取值，可以控制規(guī)劃求解過程，下面給出具體說明。,（1）最長運算時間：此選項默認值為

26、100秒。 （2）迭代次數(shù)：此選項默認值為100次。 （3）精度：此選項默認值為0.000 001。,（4）允許誤差：此選項只適合用于有整數(shù)約束條件的整數(shù)規(guī)劃問題。 （5）收斂度：此選項只適合用于非線性規(guī)劃。,? 在以上5個選項下面還有4個復選框，可根據(jù)需要選用。（1）采用線性模型 （2）自動按比例縮放 （3）假定非負 （4）顯示迭代結(jié)果,? 另外，“估計”、“導數(shù)”、“搜索”單選框為規(guī)劃求解所用方法選項。（1）“估計”

27、單選框指定在每個一維搜索中用以得到基本變量初始估計值的逼近方案，下設“正切函數(shù)”和“二次方程”兩個選項。,（2）“導數(shù)”單選框指定用于估計目標函數(shù)和約束條件偏導數(shù)的差分方案，下設“向前差分”和“中心差分”兩個選項。 （3）“搜索”單選框指定每次迭代算法已確定的搜索方向，下設“牛頓法”和“共軛法”兩個選項。,2.5.4 Excel求解演示實例,? 例2.7 某公司最優(yōu)購買決策問題。 ? 某公司在生產(chǎn)過程中需要使用濃度為80%的磷

28、酸100噸，市場上各種濃度的磷酸及對應價格如表2.9所示。 ? 問應購買各種濃度的磷酸各多少噸，既能滿足生產(chǎn)需要，又使得總成本最低？,? 下面介紹求解操作步驟。第一步，在Excel界面上的布局與P公司的布局相同，分為數(shù)據(jù)區(qū)域和模型區(qū)域。,第二步，選擇“工具”—“規(guī)劃求解”，彈出“規(guī)劃求解參數(shù)”對話框，在“設置目標單元格”內(nèi)填入$B$14，選擇“最小值”選項，單擊“選項”按鈕，在“規(guī)劃求解選項”對話框中選中“采用線性模型”和“假定非

29、負”，單擊“確定”按鈕后返回到“規(guī)劃求解參數(shù)”對話框。,第三步，在“規(guī)劃求解參數(shù)”對話框內(nèi)設置“可變單元格”為“$B$10:$F$10”，單擊“添加”按鈕，在“約束”框內(nèi)輸入約束條件$B$17:$B$18 = $D$17:$D$18。,第四步，單擊“規(guī)劃求解參數(shù)”對話框中的“求解”按鈕，即可解出如圖2.9所示的答案。 ? 目標函數(shù)（最小總成本）最優(yōu)值為169 167元（見圖2.9中的單元格B14），決策變量最優(yōu)解

30、如表2.10所示。,圖2.9 使用Excel對某公司最優(yōu)購買決策問題進行求解,? 例2.8 某銀行最優(yōu)投資決策問題。 ? 某銀行有100萬元擬做投資用，其中一部分擬用做貸款（L），一部分擬投資證券（S）。,? 貸款可以獲取較高利率，證券利率雖然低一些但可以交易，在任何時候銀行都可以將證券出售而獲取迅速變現(xiàn)的能力。 ? 在下述條件下，試確定銀行的最優(yōu)投資決策。,①年利率：貸款（L）10%，證券（S）5%；②變現(xiàn)能力S≥（L&

31、#160;+ S）*25%；③必須滿足有信譽的老貸款客戶的要求，L≥30。,? 如圖2.10所示，運用Excel工具求解結(jié)果為：L = 75萬元，S = 25萬元，最大總獲利額為9萬元。,? 需要注意的是，為了使求解過程變得簡單，在建立模型后進行求解時將約束條件作了變換，即圖2.10中單元格B21 = 100 ? B16 ? 

32、C16，B22 = C16?0.25* (B16 + C16)，B23 = B16 ? 30；其中，L = B16，S = C16。,? 這樣，在“約束”文本框中就可以非常簡單地寫入$B$21 = 0,$B$22:$B$23＞ = 0，如圖2.11所示，從而使求解過程簡化。,圖2