數據、模型與決策【共十九章791ppt，點燈籠都找不到這么全面經典的講義】-資料下載頁

　　

【正文】 ? A2+B2+C2≥10,000 ? 非負約束： ? Ai， Bi， Ci≥0 (i=1,2) 第三章 線性規劃 第三章 線性規劃 ? 線性規劃問題概述 ? 線性規劃問題的圖解法 ? 單純形法 ? 對偶問題 ? 敏感性分析 第三章 線性規劃 ? 圖解法的過程介紹 ? 規劃問題求解的幾種可能結果 ? 圖解法延伸 第三章 線性規劃 圖解法的過程介紹 ?花瓶問題 ? 目標函數 max z =12B+10S ? 材料約束 2B+S≤160 （ 1） ? 時間約束 1/3B+1/3S≤40 （ 2） ? 儲存約束 3B+2S≤260 （ 3） ? 非負約束 B≥0, S≥0 第三章 線性規劃 直線把圖分為兩部分，直線上方的點都不符合約束條件， 而直線上和直線下方的點都滿足約束條件。 第三章 線性規劃 最優解為： ?B=20, S=100 將 B和 S值代入目標函數中得： ?Z=12 20+10 100=1240 所以最大利潤值是 1240。 第三章 線性規劃 圖解法的步驟： ? 其中一個變量作為橫坐標軸，另一個變量作為縱坐標軸，畫出平面直角坐標系，并適當選取單位坐標長度，由于變量是非負的，因此，畫出坐標系的第一象限即可。 ? 出各約束條件在坐標軸上對應的直線，找出可行域（常用陰影區域標識）。 ? 圖標目標函數， z是一個待求的目標函數值。目標函數常用一組平行虛線表示，離坐標原點越遠的虛線表示的目標函數值越大。 ? 確定最優解。因為最優解是可行域中使目標函數值達到最優的點，當目標函數直線由原點開始向右上方移動時， z值開始增大，一直移到目標函數直線與可行域相切時為止，切點就是最優解的點。 第三章 線性規劃 ?無窮多最優解 ?無界解 ?無解或者無可行解 第三章 線性規劃 ?圖解法的解體方法和幾何判斷對于求解一般的線性規劃問題有很大啟發： ? 性規劃問題的解的情況有以下幾種：唯一最優解；無窮多最優解；無界解；無可行解。 ? 線性規劃問題有解，那么可行域是凸集。 ? 規劃問題優解存在，那么唯一最優解一定是可行域凸集的某個頂點；無窮最優解一定是可行域的某個邊或某個面。 ? 規劃問題的一般解體思路：先找出凸集的任一頂點，計算該點處目標函數值，與周圍相鄰頂點處的目標函數值相比較，如果該點值最大，那么該點就是最優解或者最優解之一；如果不是，那么就對目標函數值比該點大的另一點重復此過程，直到找出最優解。 第三章 線性規劃 ? 實例分析： ? 某工廠生產 A,B兩種產品，分別經過三道工序，已知建立的模型如下所示，可行域為凸多邊形 OACDB, 試以圖解法求解最優生產方案。 ? 目標函數 max z =20A+30B ? 工序一約束 2A+B≤ 40 ? 工序二約束 A+2B≤ 40 ? 工序三約束 A+B≤ 25 ? 非負約束 A≥ 0, B≥ 0 第三章 線性規劃 第三章 線性規劃 ?A+2B=40 工序二約束 ?A+B=25 工序三約束 ?聯立以上方程，可以求得最優解 ?A=10, B=15 ?代入目標函數，求得最大目標函數值為20*10+30*15=650。 第三章 線性規劃 第三章 線性規劃 ? 線性規劃問題概述 ? 線性規劃問題的圖解法 ? 單純形法 ? 對偶問題 ? 敏感性分析 第三章 線性規劃 單純形法 ? 線性規劃問題的標準形式 ? 線性規劃問題解的概念和基本定理 ? 單純形法解題步驟 第三章 線性規劃 ?規定線性規劃問題的一般形式： ?目標函數 ?約束條件 （ i =1,……m ） ?非負約束 0 ( j =1,……,n) ??? njjj xcz1m a xjnjjji bxa ???1jx ?第三章 線性規劃 轉化為標準形式方法： ? 如果模型的目標函數為極小值： ，那么令 z’=z , 。 ? 如果右端項 bi小于零，等式兩端同時乘以 1 。 ? 約束條件一般情況下是不等式。例如： x1+x2≤6, 令 x3=6x1x2 ， x3 ≥0，將約束條件轉化為 x1+x2+x3=6 ， x3稱作松弛變量。如果有 x1+x2≥6 ,令 x4=6x1x2 , x4≥0，約束條件轉化為 x1+x2x4=6， x4稱作剩余變量。 ? 變量取值可能無約束。決策變量可以大于或等于零，也可以小于零。此時令xj=xj’xj’’, xj’≥0, xj’’≥0, 將其代入線性規劃模型。 ? 決策變量小于等于零 , 即 xj≤0。令 xj’=xj , 將 xj’代入線性規劃模型。 ??? nj jj xcz 1mi n第三章 線性規劃 ?目標函數 ?約束條件 （ i =1,……m ） ?非負約束 xj 0 ( j =1,……,n) ??? njjj xcz1m a xinjjji bxa ???1?第三章 線性規劃 ?可行解：滿足約束條件的解為可行解，全部可行解的集合為可行域。 ?最優解：使目標函數值達到最大的可行解為最優解。 ?定理一 ： 若線性規劃問題存在可行解，則問題的可行域為凸集。 ?定理二 ： 線性規劃問題的基可行解對應于線性規劃問題可行域的頂點。 ?定理三 ：若線性規劃問題有最優解，一定存在一個基可行解是最優解。 第三章 線性規劃 ?已知模型如下： ?目標函數 max z =20A+30B ?工序一約束 2A+B≤40 ?工序二約束 A+2B≤40 ?工序三約束 A+B≤25 ?非負約束 A≥0, B≥0 第三章 線性規劃 ?，引入三個松弛變量： C、 D、 E ?原問題轉變為如下形式： max z =20A+30B+0C+0D+0E 2A+B+C=40 A+2B+D=40 A+B+E=25 A≥0, B≥0,C≥0,D≥0,E≥0 第三章 線性規劃 ?約束條件的系數矩陣為： ? U=(P1 ,P2 ,P3 ,P4 ,P5) = ? P3= ， P4= ， P5= 三個向量是線性無關的 ? 這些向量構成基矩陣： V=(P3, P4, P5 ) = ??????????100110102100112??????????001??????????010??????????100??????????100010001第三章 線性規劃 ? 對應于 V的變量為基變量，他們分別為： C=402AB D=40A2B E=25AB ? 將上述基變量代入目標函數中，得到： Z=20A+30B+0 當還未生產時， A=B=0，資源未被利用。取 C=40 ,D=40 ,E=25，利潤值還未產生， 得到初始基本可行解： X(0) =(0， 0， 40， 40， 25)。 第三章 線性規劃 ? B的取值滿足： C=402AB≥0 D=40A2B≥0 E=25AB≥0 ? 因為 A=0,所以有： C=40B≥0 D=402B≥0 E=25B≥0 ? B的取值要求滿足上述三式，因此 B為 : ? B=min {40/1 ,40/2 ,25/1} =20 第三章 線性規劃 ? 現在知道， A=0 ,B=20 ,將其代入三個約束條件中， 2A+B+C=40 A+2B+D=40 A+B+E=25 ? 得到一組新的解： X(1)=(0， 20， 20， 0， 5) ? 將上面三式變形，得到下式： C+B=403/2A (1) 2B=40AD (2) E+B=25A (3) 第三章 線性規劃 ? 將其進行轉化， (1)1/2*(2)， (2)/2， (3)(2)/2，上述三式又變為： C=203/2A (4) B=201/2A1/2D (5) E=51/2A+1/2D (6) ? 將上述三式代入目標函數式中， Z=600+5A15D V=(C, B, E) = ??????????100010001第三章 線性規劃 ? 根據 (4)、 (5)、 (6)式可以得到新的約束方程的系數矩陣： ? U= ? 從目標表達式 Z=600+5A15D上看， A的系數式正值，說明增加 A的產量仍然可以提高利潤， A的取值滿足： ? C=203/2A≥0 ? B=201/2A1/2D≥0 ? E=51/2A+1/2D≥0 ????????????12100211210021001023第三章 線性規劃 ? 由于 D=0，可得： C=203/2A≥0 B=201/2A≥0 E=51/2A≥0 ? A要求滿足上述三式，因此 A=min { 20/, 20/, 5/}=10 ? A變為基變量，而 E變為非基變量，將 A=10, E=0代入三個約束條件中： 2A+B+C=40 A+2B+D=40 A+B+E=25 ? 通過求解可得： B=15, C=5, D=0 第三章 線性規劃 ? 新的基本可行解為： X(2)=(10， 15， 5， 0， 0)。 ? 用 A置換 E，得到： C+3/2A=20 B+1/2A=201/2D 1/2A=5+1/2DE ? 經變形得到下面三個新的式子： C=53/2D+3E B=15D+E A=10+D2E 第三章 線性規劃 ?將上述三式帶入目標函數 Z=65010D10E ?從上式可以看出， D、 E系數皆為負，如果這些變量值增加，將導致目標函數值的減少。因此最佳生產方案為： X(2)=(10， 15， 5， 0， 0) 最大利潤值為： Z=650 第三章 線性規劃 ?例 Keku公司一直開始從事汽車零配件的設計、生產，最近公司設計了兩種新型改良產品 (產品 I和 II)。根據以往新產品上市的經驗和市場行情， Keku公司預計每生產一件產品 I可獲利 2元，每生產一件產品 II可獲利 3元。公司準備利用現有的生產資源，在計劃期內安排生產 I、 II兩種新產品，已知生產單位產品所需的設備臺時及 A、 B兩種原材料的消耗，如下表所示。 第三章 線性規劃 I II 設 備 1 2 8臺時 原材料 A 4 0 16m3 原材料 B 0 4 12kg 站在 Keku公司的立場想知道如何安排生產才能獲利最多？ 用單純形法對它進行求解。 第三章 線性規劃 ?分別設 、 表示在計劃期內產品 I、 II的產量，建立該問題的數學模型為： 21 32m a x xxz ??????????????0,12416482212121xxxxxx第三章 線性規劃 ?