lttaaa線性規劃(已修改)

　

【正文】 線 性 規 劃(Linear Programming)線性規劃問題及其數學模型線性規劃問題的求解方法線性規劃的圖解法線性規劃的單純形法單純形法的進一步討論線性規劃模型的應用 為了完成一項任務或達到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務或達到一定的目的，這個過程就是規劃。例一、有一正方形鐵皮，如何截取 x 使容積為最大？xa此為無約束極值問題一、 線性規劃問題及其數學模型（ 一）、問題的提出 設 備產 品 A B C D 利 潤 （元） Ⅰ 2 1 4 0 2 Ⅱ 2 2 0 4 3 有 效 臺 時 12 8 16 12 例二、已知資料如下表所示，問如何安排生產才能使利潤最大？或如何考慮利潤大，產品好銷。模 型 max Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0. 2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12此為帶約束的極值問題問題中總有未知的變量，需要我們去解決。 要求：有目標函數及約束條件，一般有非負條件存在，由此組成規劃數學模型。 如果在規劃問題的數學模型中，變量是連續的（數值取實數）其目標函數是有關線性函數（一次方），約束條件是有關變量的線性等式或不等式，這樣，規劃問題的數學模型是線性的。反之，就是非線性的規劃問題（其中一個條件符合即可）。（二）、數學模型 目標函數：約束條件：①②③線性規劃數學模型的一般形式也可以記為如下形式 ：目標函數：約束條件：如將上例用表格表示如下：設變量 產 品 j 設 備 i 有效臺 時 利 潤 向 量 形 式：矩陣形式：規劃確定型隨機型靜態規劃動態規劃線 性規 劃非線性規劃 整數規劃 非整數規劃整數規劃非整數規劃規劃類型一 般 有兩種方法圖 解 法單純形法兩個變量、直角坐標三個變量、立體坐標適用于任意變量、但需將一般形式變成標準形式二、線性規劃問題的求解方法（一）、求解方法解的概念 ⑴ 可行解：滿足約束條件 ② 、 ③ 的解為可行解。所有解的集合為可行解的集或可行域。 ⑵ 最優解：使目標函數達到最大值的可行解。 ⑶ 基： B是矩陣 A中 mn 階非奇異子矩陣（∣ B∣≠0 ）， 則 B是一個基。則稱 Pj ( j = 1 2 … … m) 為基向量?！? Xj 為基變量，否則為非基變量。（二）、線性規劃問題的解 ⑷ 基本解：滿足條件 ② ，但不滿足條件 ③ 的所有解，最多為 個。 ⑸ 基本可行解：滿足非負約束條件的基本解，簡稱基可行解。 ⑹ 可行基：對應于基可行解的基稱為可行基。非可行解可行解基解基可行解解的基本定理⑴ 線性規劃問題的可行域是凸集（凸多邊形）。凸集 凸集 不是凸集頂 點⑵ 最優解一定是在凸集的某一頂點實現（頂點數目不超過 個）⑶ 先找一個基本可行解，與周圍頂點比較，如不是最大，繼續比較，直到找出最大為止。解的情況唯 一 解無 窮 解無 界 解無可行解有最優解無最優解 建立直角坐標 ，圖中陰影部分及邊界上的點均為其解，是由約束條件來反映的。例一、⑴⑵⑶⑷三、圖 解 法0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴⑵⑶⑷作 圖∴ 最 優 解： x1 = 4 x2 = 2 有唯一最優解， Z = 14x2 x1(4 2)⑴⑵⑶⑷ 例二、 例三、⑴⑵⑶無窮多最優解⑴⑵ 無界解x1x1x2 x2 ⑴⑵x1x2 無可行解例四、練習 1 效 產 品機床 率 A B 機床臺數 Ⅰ 30 40 40 Ⅱ 55 30 40 Ⅲ 23 37 20 某車間用三種不同型號的機床 Ⅰ 、 Ⅱ 、 Ⅲ ，加工 A、B兩種零件，機床臺數、生產效率如表所示。問如何合理安排機床的加工任務，才能使生產的零件總數最多？某工廠生產 A A2 兩種產品， 每件可獲利潤 120元。每個產品都經過三道工序，資料如表所示。工廠應如何安排生產計劃使獲得的總利潤最多？試寫出此問題的數學模型。 工 產 品工序 時 A1 A2可用工 時 Ⅰ 3 2 800 Ⅱ 2 3 800 Ⅲ 1 1 350