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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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