山東大學《管理系統(tǒng)工程》教案14線性規(guī)劃問題

1、周 次 第 十 周 章 節(jié) 名 稱 第十四章 線性規(guī)劃問題（一） 授 課 方 式 課堂講授 教 學 時 數 3 授 課 要 點 第十四章 線性規(guī)劃問題 教學目的： 通過這一章的教學，要求學生熟悉 線性規(guī)劃問題的數學模型，解的概念，解的性質，線性規(guī)劃的對偶理論、影子價格。掌握線性規(guī)劃問題的圖解法、單純形法、對偶單純形法以及常用的靈敏度分析方法。學會對一些簡單的管理優(yōu)化問題進行分析，建立模型并求解。 第一節(jié) 系統(tǒng)模型技術概述 模型在系統(tǒng)工程中占有很重要的地位。我們首先要了解什么是模型，模型的作用以及模型的分類，這對于構造和使用模型是十分重要的。 一、模型的定義及特征 模型可以認為是實際系統(tǒng)的代替物

2、。模型應反映出系統(tǒng)的主要組成部分和各部分的相互作用以及在運行條件下因果的作用和反作用的相互關系。根據模型，我們可以用較少的風險、時間和費用來對實際系統(tǒng)做研究和實驗，更好地觀察系統(tǒng)的行為。開發(fā)一個模型是科學和藝術的結合，因此，模型是實際系統(tǒng)理想化的抽象或簡化表示。它描繪了現(xiàn)實世界的某些主要特點。它 是為了客觀地研究系統(tǒng)而發(fā)展起來的。 模型有三個特征： 1.它是實現(xiàn)世界一部分的抽象或模仿； 2.它是由那些與分析的問題有關的因素構成； 3.它表明了有關因察之間的相互關系。 模型是對現(xiàn)實世界的一個抽象。因此，模型必須反映實際，同時由于它的抽象性，又要高于實際。在構造模型時，要兼顧到它的現(xiàn)實性和易處理性

3、?？紤]到現(xiàn)實性，模型必須包括現(xiàn)實系統(tǒng)中的 主要因素；考慮到易處理性，模型要采取一些理想化的辦法，即 去掉一些外在的影響，并對一些過程作合理的簡化。 二、模型的種類 三、模型的作用和用途 模型的作用和用途有以下幾個方面； 1模型比現(xiàn)實容易操作，尤其是一些參數值的改變在模型中操作比在現(xiàn)實中操作要容易； 2有時在現(xiàn)實上很難或不能作試驗，通過建立模型就可以解決這些困難，而且模型比現(xiàn)實更容易理解； 3有些變量在現(xiàn)實情況中要很長時間才能看出其變化情況，但用模型研究時可以很快看出變化規(guī)律，從而最迅速地抓住其本質特征； 4用模型研究變量(可控的和不可控的)之間的關系，通過用可控變量得出一定的結果； 5通過靈敏

4、度分析，可看出哪些因素對系統(tǒng)影響更大。 四、建立模型的一般要求 1有足夠的精確度。 2簡單。 3數據要準確，依據要充分。 4. 盡量借鑒標準形式。 5. 模型中所表示的系統(tǒng)要能夠操縱和控制，否則建立的模型就毫無意義； 6. 模型要有一定的適應性和可靠性。 五、構造模型的一般原則 1建立方框圖。 2考慮信息相關性。 3考慮準確性。 4考慮結集性。 六、 構模的基本步驟 對于構模，很難給出一個嚴格的步驟。構模主要取決于對問題的理解、洞察力、訓練和技巧。構模的基本步驟可歸納為： 1. 明確構模的目的和要求，以使模型滿足實際需要，不致產生太大的偏差； 2對系統(tǒng)進行一般語言描述，這是進一步確定模型結構的

5、基礎； 3. 弄清楚系統(tǒng)中的主要因素及其相互關系以使模型準確表示現(xiàn)實系統(tǒng)； 4確定模型的結構，這一步決定了模型定量方面的內容； 5估計模型中的參數，用數量表示系統(tǒng)中的因果關系； 6對模型進行實驗研究； 7根據實驗結果，對模型作必要的修改。 七、 模型的簡化和近似 由于實際情況的復雜和變化多樣，往往不能簡單地套用現(xiàn)有的模型，甚至對一些具有簡單結構的模型也是如此。這時只有改用其它形式的模型，有時通過模型的構造才發(fā)現(xiàn)必須擁有哪些數據，或者模型該往哪個方向修正。還有的時候，雖然復雜的模型已構造出來，但是作試驗和求解太困難，就改用較為簡單的近似模型。 另外，有些實際問題建立數學模型很困難，甚至不可能，還

6、有些問題即使建立起模型來也很復雜，求解也很困難，在這種情況下，我們就要用另外一種手段仿真技術。一種是物理仿真方法，另一種是電子計算機仿真方法，而后者最常用也最有效。 第二節(jié) 線性規(guī)劃問題的數學模型 線性規(guī)劃是運籌學的一個重要分支。它所研究的問題：一是在資源（如鋼材、電力）受限制的前提下，研究如何合理使用這些資源，以完成更多的任務；二是在任務一定的前提下，研究如何合理安排，用最少的資源來完成給定的任務。實際上，它們是一個問題的兩個方面，前者是擴大生產，增加利潤，后者是減少消耗，降低成本。以數學的形式來表示的話，線性規(guī)劃就是求具有線性約束條件的線性目標函數的極值問題。 一、問題的提出 二、線性規(guī)劃

7、問題的數學模型 1. 一般線性規(guī)劃問題的數學模型： 一般線性規(guī)劃問題是具有下述形式的數學模型： 求決策變量：x1 ，x2 ，xn 滿足約束條件： 這就是線性規(guī)劃問題的數學模型。 2. 線性規(guī)劃數學模型的標準形式 在線性規(guī)劃問題的數學模型中，對不同的問題，約束條件可以是線性方程組，也可以是線性不等式組，目標函數可以是求最大值，也可以是求最小值，這種形式上的不同，給討論線性規(guī)劃問題的求解帶來不便。為了討論方便起見，規(guī)定線性規(guī)劃問題的數學模型的標準形式為： 求： x1 ，x 2 ，xn 滿足 3.將一般形式的線性規(guī)劃數學模型轉化為標準形式 三、線性規(guī)劃問題數學模型的向量表達式與矩陣表達式 用向量來描

8、述線性規(guī)劃問題的數學模型的標準形式為：教 學 重 點 與 難 點 重點： 線性規(guī)劃的數學模型及其標準形式。在數學模型中，要求熟悉矩陣形式，為后面打下基礎。要求學生掌握非標準形式的幾種具體情形及其相應的標準化方法。 難點： 建立實際問題的線性規(guī)劃數學模型，將線性規(guī)劃數學模型的一般形式轉化為標準形式。 課 堂 討 論 與 練 習 習題： 教材 P199 1 ， 2 ， 3 ， 4 ， 5 參 考 資 料 運籌學 運籌學編寫組 清華大學出版社 外 語 詞 匯 Linear programming, model, Standard form 周 次 第 十一 周 章 節(jié) 名 稱 第十四章 線性規(guī)劃問題

9、（二） 授 課 方 式 課堂講授 教 學 時 數 3 授 課 要 點 第三節(jié) 線性規(guī)劃問題的圖解法 圖解法是用作圖的方法來求線性規(guī)劃問題的解，它適用于僅含兩個決策變量的線性規(guī)劃問題的數學模型。雖然這種方法的應用范圍受到很大的限制，但這種方法簡單、直觀，而且有助于理解線性規(guī)劃問題求解的基本原理。 第四節(jié) 線性規(guī)劃問題的基本理論 一、 線性規(guī)劃問題的解 對于線性規(guī)劃問題 6 退化解：非零分量的個數小于 m 的基本可行解，稱為退化解。 二、凸集 三、線性規(guī)劃問題的基本定理 第五節(jié) 單純形法 一、單純形法原理 單純形法的基本思路是：從一個基本可行解出發(fā)，轉移到另一個基本可行解，每一次轉移都使目標函數值

10、得到改善，這在數學上稱為從一個基本可行解到另一個基本可行解的迭代。因為基本可行解反映在幾何上就是可行域的一個頂點，而可行域的頂點個數是有限的，因此，經過有限次迭代后，就可取得最優(yōu)解，先用一個例子來說明上述基本思路。 教 學 重 點 與 難 點 重點： 線性規(guī)劃模型的矩陣表達式，圖解法，解的基本概念，基、基本可行解、凸集的概念，定理 1 ， 3 ， 5 。單純形法，解的判別定理。 難點： 線性規(guī)劃模型的矩陣表達式，基的概念，基本可行解的概念，單純形法原理，各種解的經濟解釋。課 堂 討 論 與 練 習 習題： P199200 6 ， 7 ， 參 考 資 料 運籌學 運籌學編寫組 清華大學出版社 外

11、 語 詞 匯 Basic ； Basic variables ； Nonbasic variables ； Matrix form ； Basic feasible solution ； Optimal solution ； Convex set ； Simplex method 周 次 第 十二 周 章 節(jié) 名 稱 第十四章 線性規(guī)劃問題（三） 授 課 方 式 課堂講授 教 學 時 數 3 授 課 要 點 一、單純形法原理 用單純形表計算 二、大 M 法與兩階段法 在前面的討論中，約束方程組系數矩陣明顯地含有 m 階單位矩陣，因此很快地找到初始可行基與初始基本可行解。但是，一般來講，約束方程

12、組的系數矩陣中所含的單位響亮的個數往往不足 m 個。這時，就要引進人工變量，以人工變量對應的系數列向量作為單位列向量，構成一個初始可行基，進而應用單純形法求解。 （一） 大 M 法 設線性規(guī)劃問題 （ 2 13 ） 如果約束方程組的系數矩陣中不含 m 階單位矩陣，則分別給每一個約束方程加一個新的非負變量 xn+1 ， xn+2 ， xn+m ，使（ 2 13 ）式擴充為（ 2 14 ） 稱新的變量 xn+1 ， xn+2 ， xn+m 為人工變量。因為（ 2 14 ）的系數矩陣中含有 m 階單位矩陣，作為初始可行基，則 xn+1 ， xn+2 ， xn+m 為基變量，相應的基本可行解為： 但是

13、，我們不能用新的約束條件（ 2 14 ）簡單地代替原來的約束條件，因為人工變量是虛擬的變量，沒有任何實際意義。然而，它的引進卻擴大了原問題的范圍，也就是將 n 維空間的問題擴充為 m+n 維空間的問題了。為了使（ 2 13 ）與（ 2 14 ）在最優(yōu)解方面互相提供信息，應考慮修改目標函數。由于原問題的最優(yōu)解中不能有人工變量出現(xiàn)，即限定人工變量的取值必須為零，為此引入新的 n+m 維目標函數 其中 M 是很大的正數。對此應用單純形法在改善（即增大）目標函數值的過程中，如果原問題有最優(yōu)解，則必然要在迭代中盡快地將人工變量從基變量替換稱非基變量，或使其值為零。否則，目標函數將是一個負的很大的值，這就

14、不可能實現(xiàn)最大值。從中可以看出引入大 M 的作用，所以稱為大 M 法，也稱為懲罰法。 在用大 M 法解線性規(guī)劃問題，當其全部檢驗數 時，出現(xiàn)兩種可能： 1 在基變量中已不包含人工變量時，則原問題有最優(yōu)解； 2 在基變量中仍含有取正值的人工變量時，則原問題無可行解。 對于第 2 種可能，如果作為基變量的人工變量其值為零（即出現(xiàn)退化解），則原問題仍有最優(yōu)解。 兩階段法是處理人工變量的另一種方法。這種方法是把增加人工變量后的線性規(guī)劃問題分成兩個階段來求解。 第一階段：求原線性規(guī)劃問題的一個基本可行解。為此，構造一個輔助線性規(guī)劃問題，它以所有人工變量之和求最小值為目標函數，即 用單純形法求解，若第一階

15、段問題的最終單純形表中出現(xiàn) W0 ，這說明至少有一個人工變量仍為基變量，其值大于零，于是原問題無可行解，計算停止；若得到 W=0 ，則必有 xn+i=0 （ i=1 ， 2 ， m ），即所有人工變量都變換成非基變量，這表明原線性規(guī)劃問題得到一個基本可行解，且它對應的極為一個 m 階單位矩陣，然后轉入第二階段。 第二階段：建立原線性規(guī)劃問題的初始單純形表，并求其最優(yōu)解：將第一階段最終表中的目標函數系數換成原問題的目標函數的系數，然后劃去人工變量所在的列，就得到原問題的初始單純形表，以此為起點，繼續(xù)用單純形法進行迭代，求出最優(yōu)解。 三、單純形法的計算步驟 對給定的線性規(guī)劃問題首先是將它化為標準形

16、式，選取或構造一個單位矩陣作為基，求出初始基本可行解，并列出初始單純形表，具體計算步驟見框圖（圖 14 4 ）。 四、單純形法的矩陣形式 設線性規(guī)劃問題的數學模型 引進松弛變量 化為標準形式 其中 I 為 m 階單位矩陣。 設 B 是一個可行基，于是可將線性規(guī)劃問題數學模型中的 A 、 X 、 C 分別用分塊矩陣表示為其中 N 為非基變量對應的系數列向量組成的矩陣； XB ， XN 分別為基變量與非基變量組成的向量； CB ， CN 分別為基變量與非基變量的價值系數組成的行向量。因此，線性規(guī)劃問題的標準形式可改寫成（ 14 15 ）（ 14 16 ） 因為 B 為基，所以 ，從而 存在，以 左

17、乘（ 2 16 ）式，得 （ 14 17 ） （ 14 17 ）式就是非基變量 XN ， Xs 表示基變量 XB 的矩陣形式。將（ 14 17 ）式代入（ 14 15 ）式，就得到用非基變量表示目標函數的矩陣形式 （ 14 18 ） 在（ 14 17 ）中，令非基變量 XN =0 ， Xs =0 ，得 當 時，得到對應于可行基 B 的基本可行解。相應的目標函數值 把（ 14 18 ）再改寫成 從上式可以看出，系數 分別是基變量 XB ，非基變量 XN 與 Xs 的檢驗數。它們還可統(tǒng)一用矩陣形式表示為 將上述討論納入單純形表，則初始單純形表為（表 14 15 ）。 表 14 15 經過基變換后的

18、新單純形表為（表 14 16 ）。14 16 第六節(jié) 線性規(guī)劃問題的對偶問題 一、對偶問題的一般形式 定義 具有下列特征的線性規(guī)劃稱為對稱形式的線性規(guī)劃： （ 1 ）對求目標函數最大值的線性規(guī)劃數學模型，其約束條件全部為“ ”不等式，對求目標函數最小值的線性規(guī)劃數學模型，其約束條件全部為“ ”不等式。 （ 2 ）全部決策變量為負。定義： 稱線性規(guī)劃問題 與為對稱形式的對偶線性規(guī)劃問題。若稱前者為線性規(guī)劃的原問題，則稱后者為原問題的對偶問題， y1 ， y2 ， ym 為對偶變量。 用矩陣來表示原問題為：則對偶問題為 其中： A 是原問題的系數矩陣； b 是原問題的常數列向量； C 是原問題目標

19、函數的系數行向量； X 是原問題的決策變量列向量； Y 是對偶問題的決策變量行向量。 非對稱形式的對偶線性規(guī)劃寫法見下表：教 學 重 點 與 難 點 重點： 大 M 法、兩階段法與解的判別，一般對偶模型的寫法。 難點： 對偶問題的經濟解釋，原問題與對偶問題解的對應關系。 課 堂 討 論 與 練 習 習題： P200 8，9，10，11，12 參 考 資 料 運籌學 運籌學編寫組 清華大學出版社 外 語 詞 匯 dual problem 周 次 第 十三 周 章 節(jié) 名 稱 第十四章 線性規(guī)劃問題（四） 授 課 方 式 課堂講授 教 學 時 數 3 授 課 要 點 二、對偶問題的基本性質 1 對

20、稱性 對偶問題的對偶問題是原問題。 2 弱對偶性 若 與 分別是原問題（ 14 19 ）與對偶問題（ 14 20 ）的可行解，則 。 3 最優(yōu)性準則 設0與Y0分別為原問題（ 14 19 ）與對偶問題（ 14 20 ）的可行解，且 CX0 =Y0b ，則 X0,Y0 分別是原問題（ 14 19 ）與對偶問題（ 14 20 ）的最優(yōu)解。 4 對偶定理 若原問題（ 14 19 ）有最優(yōu)解，則對偶問題（ 14 20 ）也有最優(yōu)解，且目標函數值相等。 5 互補松弛定理 設 X0，Y0，分別為原問題（ 14 19 ）與對偶問題（ 14 20 ）的可行解， Xs為原問題（ 14 19 ）中約束條件的松弛變

21、量，Ys為對偶問題（ 14 20 ）中約束條件的剩余變量，則 X ，Y 分別為原問題（ 14 19 ）和對偶問題（ 14 20 ）的最優(yōu)解的充分必要條件是 YXs=0 ， YsX=0 6 原問題（ 14 19 ）檢驗數的相反數是對偶問題（ 14 20 ）的一個基本解。 三、對偶單純形法 單純形法的整個迭代過程是原問題由一個基本可行解轉換到另一個基本可行解的過程，直到使所有的檢驗數都變?yōu)榉钦秊橹?。換句話說，就是在迭代過程中，始終在保持原問題解的可行性（ ）的基礎上，直到滿足解的最優(yōu)性（所有檢驗數 ）為止。根據 2 的性質 6 ，因此，原問題檢驗數變?yōu)榉钦倪^程也可解釋為：由原問題的對偶問題的一個

22、基本解出發(fā)，經過換基迭代，逐步使基本解轉換為基本可行解的過程，從而得到原問題的最優(yōu)解，與此同時，也得到對偶問題的最優(yōu)解。 根據對偶問題的對稱性，把求解原問題的迭代過程建立在保持對偶問題解的可行性（所有 ）的基礎上，從原問題的一個基本解出發(fā)，經過迭代，逐步使它轉變成基本可行解（ ），從而在得到對偶問題的最優(yōu)解的同時，也得到原問題的最優(yōu)解。這就是對偶單純形法的基本思路。 四、對偶問題的經濟解釋影子價格 由對偶定理知，當 X ， Y 分別表示原問題與對偶問題的最優(yōu)解時，它們對應的目標函數值相等。式中 bi 是線性規(guī)劃原問題約束條件的常數項，它代表第 I 中資源的擁有量； yi 是對偶問題的決策變量，

23、它代表對一個單位第 I 中資源的估價。這種估價不是資源的市場價格，這是針對具體企業(yè)具體產品而存在的一種特殊價格，它隨著企業(yè)生產任務、產品結構、工藝條件等情況的改變而變化。為區(qū)別起見，稱這種估價為影子價格。 教 學 重 點 與 難 點 重點：，對偶問題的基本定理，原問題與對偶問題解的對應關系，對偶單純形法，影子價格的概念和計算，線性規(guī)劃的靈敏度分析。 難點： 影子價格的經濟解釋靈敏度分析的計算。 課 堂 討 論 與 練 習 習題： P201 13 ， 14 ， 參 考 資 料 運籌學 運籌學編寫組 清華大學出版社 外 語 詞 匯 shadow price 周 次 第 十四 周 章 節(jié) 名 稱 第

24、十四章 線性規(guī)劃問題（五） 授 課 方 式 課堂講授 教 學 時 數 3 授 課 要 點 第七節(jié) 靈敏度分析 求解一個線性規(guī)劃問題，是在其數學模型中的價值系數 cj ，資源限制常數 bi ，工藝系數 aij 確定的基礎上進行的，而事實上這些數據往往是統(tǒng)計、預測和估計的數字，程度不同地存在著誤差。同時，由于市場的變化，原材料供應上的變動，工藝技術條件的改進等因素的影響，使這些數據也不斷地跟著變化。因此，當這些參數中一個或幾個發(fā)生變化時，就要解答兩個問題： 1 參數在什么范圍內變動，使原來求出的最優(yōu)解保持不變 2 參數超出上述范圍時，如何用最簡便的方法，調整出新的最優(yōu)解。 這就是靈敏度分析研究的內容，所以靈敏度分析就是線性規(guī)劃數學模型中某些參數的變化對最優(yōu)解的影響及程度的分析。由于這項工作是在有了最優(yōu)解以后進行的，因而也稱為優(yōu)化后分析。 解決上面兩個問題，可以用單純形法重新進行計算，但是這樣，既麻煩也不必要，我們可以利用表 14 15 、表 14 16 中的關系式： 將參數的變化直接反映到最終單純形表上，修改原來最終單純形表上的某些數字。在修正后的最終單純形表中，對所得到的基本解，檢驗其是否滿足： 1 可行性： 2 最優(yōu)性： 如果可行性要求與最優(yōu)性要求都得到滿足，則所得解為最優(yōu)解；如果可行性要求被滿足，而最優(yōu)性要求