運籌學線性規(guī)劃ppt課件(完整版)

　　

【正文】 件。 清華大學出版社 第 一 節(jié) 線性規(guī)劃問題及其數學模型 一、線性規(guī)劃問題的數學模型 線性規(guī)劃問題主要解決以下兩類問題： 任務確定后，如何統(tǒng)籌安排，做到應用盡量少的人力和物力資源來完成任務； 在一定量的人力、物力資源的條件下，如何安排、使用他們，使完成的任務最多。 特別是在能用計算機來處理成千上萬個約束條件和變量的大規(guī)模線性規(guī)劃問題之后 ， 它的適用領域更加廣泛 。 表 1－ 2 A B 汽油 15% 50% 煤油 20％ 30％ 重油 50％ 15％ 其它 15％ 5％ 產品來源 成分 清華大學出版社 分析：很明顯，該廠可以有多種不同的方案從 A， B兩處采購原油，但最優(yōu)方案應是使購買成本最小的一個，即在滿足供應合同單位的前提下，使成本最小的一個采購方案。為了便于今后討論，我們規(guī)定線性規(guī)劃問題的標準型為： 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212m a x( ), , , 0nnnnnnm m m n n mnZ c x c x c xa x a x a x ba x a x a x ba x a x a x bx x x? ? ? ?? ? ? ???? ? ? ?????? ? ? ?????清華大學出版社 標準型具有如下特點： （ 1）目標函數求最大值； （ 2）所求的變量都要求是非負的； （ 3）所有的約束條件都是等式； （ 4）常數項非負。 3. 基 : 假設 A 是約束方程組的系數矩陣，其秩數為 m ， B是矩陣 A 中由 m 列構成的非奇異子矩陣 (B的行列式的值不為 0)，則稱 B 是線性規(guī)劃問題的一個基。 T 清華大學出版社 為了進一步討論線性規(guī)劃問題的解，下面研究約束方程組 ()的求解問題。 ,xm,0, 一般地講，基本可行解的數目要小于基本解的數目，至多相等。 （ 4）若可行域無界，則可能發(fā)生最優(yōu)解無界的情況； （ 5）若可行域是空集，此時無最優(yōu)解。 清華大學出版社 定理 若線性規(guī)劃問題存在可行域，則其可行域： D = { X | AX = b , X ? 0 } ，是凸集。, bm, 0, 定理 無有限最優(yōu)解判別定理： 若 為對應于基 B 的基本可行解，有一個 ，而對于 有 ，則線性規(guī)劃問題無有限最優(yōu)解 (也稱為無最優(yōu)解 )。 m in { | 0 }ili j lii j i lbbaaa???? ? ? ?清華大學出版社 例 1－ 8 利用單純形算法求解例 1－ 1的線性規(guī)劃問題。這時分別給每一個約束條件加入一個人工變量 xn+1, …, xn+m , 得 : 由此可以得到一個 m階單位矩陣。這就是大 M法。第一階段是先求出基本可行解 (或判斷出原線性規(guī)劃問題無解 )，第二階段利用已求出的初始基本可行解來求最優(yōu)解。 各階段的計算方法及步驟與前述單純形法完全相同，下面用例子說明該方法的應用。因人工變量 x6 = x7 = 0，所以 ( 0, 1, 1 ,12, 0 )T 是原問題的基本可行解。已知產品的規(guī)格要求、產品單價、每天能供應的原材料數量及原材料單價分別見表 12表 129。 ， x9 ? 0 清華大學出版社 第六節(jié) 線性規(guī)劃的對偶理論與靈敏度分析 一、對偶問題的提出 對偶理論是線性規(guī)劃問題的最重要的內容之一。其中一個是另一個問題的對偶問題。 從上述性質中，可看到原問題與對偶問題的解必然是下列三種情況之一： ①原問題與對偶問題都有最優(yōu)解，且 CX=Yb； ②一個問題具有無界解，則它的對偶問題無可行解； ③兩個問題均無可行解。 清華大學出版社 三、對偶問題的經濟解釋 ——影子價格 影子價格 在一對 LP和 DP中，若 LP的某個約束條件的右端項常數 bi增加一個單位時，所引起的目標函數最優(yōu)值 Z*的改變量稱為第 i個約束條件的影子價格，又稱為邊際價格。 （ 2）對市場資源的最優(yōu)配置起著推進作用 即在配置資源時，對于影子價格大的企業(yè)，資源優(yōu)先供給 （ 3）可以預測產品的價格 產品的機會成本為 CBB1AC，只有當產品價格定在機會成本之上，企業(yè)才有利可圖。若存在 ，計算 ),2,1( nja lj ??0?lja 0?ljalkkkljljjji azcaazc ???????????? ??? 0m i n?清華大學出版社 按 Θ規(guī)則，所對應的列變量的非基變量為換入變量； （ 4）以 為主元素，按單純形法進行換基迭代，得到新的單純形表； 重復（ 1）－（ 4）的步驟進行計算。 下面分別就各個參數改變后的情形進行討論。 在例 1－ 25中，如果改變 ，使 時，原最優(yōu)方案不發(fā)生改變。這時原方案已不是最優(yōu)方案。 （ 1）、產品 D的利潤為多少時，投產產品 D有利？ 只有 時， 才能進入基，也就是說產品 D才能生產，這時解得 。 ija jx 1?BjP基變量的工藝發(fā)生改變 當 是基變量 的系數時，它的變化會使發(fā)生改變 ，所以最終單純形表 也要發(fā)生變化，若在例 1－ 25中，生產產品 A的工藝發(fā)生改變，生產產品 A對甲、乙原材料的需求分別為 2， 2。 01266166 ????? ? cPBCc B? 6x126 ?c 126 ?c清華大學出版社 添加新約束的靈敏度分析 在例 1－ 25中，假設電力供應緊張，若電力供應最多為 13單位，而生產產品 A、 B、 C每單位需電力分別為 3個單位，問該公司生產方案是否需要改變？ 解：先將原問題的最優(yōu)解 x1＝ 4， x2＝ 8， x3＝ 0代入電力約束條件 2x1+x2+3x3?13。 清華大學出版社 資源約束數量 b的靈敏度分析 從矩陣形式的單純形表 1－ 48中可以看出， b的變化只影響最優(yōu)解的變化和最優(yōu)值的變化。這時單純形表變?yōu)楸?1－ 44。 清華大學出版社 A B C 資源量 甲 1 1 1 12 乙 1 2 2 20 利潤 5 8 6 問：如何安排產品產量，可獲最大利潤？ 解：設三種產品的產量分別為 x x x3。 （ 2）對變量較少時，而約束條件很多的線性規(guī)劃問題，可先將其變?yōu)閷ε紗栴}，再用對偶單純形求解，簡化計算。 對于資源影子價格越大的企業(yè)，資源的利用所帶來的收益就越大，經濟效益就越好。 其經濟意義是：在其它條件不變的情況下，單位資源變化所引起的目標函數的最優(yōu)值的變化。所以有如下結論： 設一對對偶問題都有可行解，若原問題的某一約束是某個最優(yōu)解的松約束，則它的對偶約束一定是其對偶問題最優(yōu)解的緊約束。 清華大學出版社 原問題 Max（對偶問題） 對偶問題 Min（原問題） 約束條件數 =m 變量個數 =m 第 i個約束條件為 “ ≤” 第 i個約束條件為 “ ≥” 第 i個約束條件為 “ =” 第 i個變量 ≥0 第 i個變量 ≤0 第 i個變量無限制 變量個數 =n 約束條件個數 =n 第 i個變量 ≥0 第 i個變量 ≤0 第 i個變量無限制 第 i個約束條件為 “ ≥” 第 i個約束條件為 “ ≤” 第 i個約束條件為 “ =” 第 i個約束條件的右端項 目標函第 i個變量的系數 目標函數第 i個變量的系數 第 i個約束條件的右端項 清華大學出版社 例 1－ 19 寫出下述線性規(guī)劃問題的對偶問題 ?????????????????????0,052103342023..254m a x321321321321321xxxxxxxxxxxxtsxxxz無約束?????????????????????無約束321321321321321,0,0223532443..51020m i nyyyyyyyyyyyytsyyyW按照表將線性規(guī)劃問題化為對偶問題 清華大學出版社 例 1－ 20 寫出下述線性規(guī)劃問題的對偶問題 ???????????????????????無約束xxxxxxxxxxxxxxxxxxtsZ432143243143214321,0,06822103..423m i n???????????????????????無約束－－－3213213213121321,0,014232 3 2..6810m a xyyyyyyyyyyyyytsyyyW按照表將線性規(guī)劃問題化為對偶問題 清華大學出版社 對偶問題的基本定理 （ 1）（對稱性）對偶問題的對偶是原問題。其中的一個問題叫“原問題”，記為“ LP”，另一個稱為“對偶問題”，記為“ DP”。 目標函數： MaxZ=50(x1 +x2+x3)+35(x4+x5+x6)+25(x7+x8+x9)65(x1+x4+x7) － 25(x2+x5+x8) – 35(x3+ x6+x9)= 15x1 + 25x2 + 15x3 – 30x4 + 10x5 + 0x6 – 40x7 + 0x8 – 10x9 約束條件： 1/2 x1 + 1/2x2 + 1/2x3 ? 0 1/4x1 + 3/4x2 – 1/4x3 ? 0 3/4x4 + 1/4x5 + 1/4x6 ? 0 1/2x4 + 1/2x5 – 1/2x6 ? 0 x1 + x4 + x7 ? 100 x2 + x5 + x8 ? 100 x3 + x6 + x9 ? 60 x1， 將第一階段的最終計算表 1—23中的人工變量列取消，并將目標函數系數換成原問題的目標函數系數，重新計算檢驗數行，可得如下第二階段的初始單純形表；應用單純形算法求解得最優(yōu)解。 表 1—20 6 7 6 71 2 3 41 2 3 5 61 3 717m in m a x2 114 2 321, , 0Z x x W x xx x x xx x x x xx x xxx?? ? ? ? ? ?? ? ? ???? ? ? ? ? ???? ? ? ??? ??cj 0 0 0 0 0 1 1 XB b x1 x2 x3 x4 x5 x6 x7 x4 11 1 2 1 1 0 0 0 x6 3 4 1 2 0 1 1 0 x7 1 2 0 1 0 0 0 1 W39。 定理 設原線性規(guī)劃問題記成 (LP)，由它而引入的新的線性規(guī)劃問題記成 (LP)*。 清華大學出版社 例 111 試用