mba課程數據模型與決策線性規劃(存儲版)

　　

【正文】 劃、運輸問題和決策論等內容。 比如 ， 經營管理中的 : (1)運輸問題 (2)生產組織與計劃安排問題 (3)合理下料問題 (4)配料問題 (5)布局問題等 什么是線性規劃 14 線性規劃問題舉例 例 一個最大化問題 某家具廠生產桌子和椅子兩種家具，有關資料如下表： 桌子 椅子 可供量 木工 4小時 /張 3小時 /把 120小時 /月 油漆工 2小時 /張 1小時 /把 50小時 /月 售價 50元 /張 30元 /把 問該廠如何安排生產才能使每月銷售收入最大 ? 解： ： 設 x1為桌子生產量 , x2為椅子生產量 ： max. z=50x1+30x2 ： 木工約束： 4x1+3x2≤ 120 油漆工約束： 2x1+x2≤ 50 15 ： x1≥ 0, x2≥ 0 把以上四個部分合起來 ， 有： max. z=50x1+30x2 . 4x1+3x2≤ 120 (.=Subject to ) 2x1+x2≤ 50 x1 ≥ 0, x2≥ 0 這就是一個最大化的線性規劃模型 . 例 一個最小化問題 有一種生豬催肥用的簡易配合飼料由粗玉米粉和骨粉兩種原料組成 ， 有關資料如下表： 粗玉米粉 骨粉 催肥最低要求 熱值 4mc/kg 2 mc/kg 8mc/日 蛋白含量 30g/kg 60 g/kg 96g/日 售價 3元 /公斤 5元 /公斤 注： mc為百萬卡路里 (million calorie) 一個最小化問題 16 解：設 1 x , 2 x 分別為兩種原料的配給額，則有： min z=3 1 x +5 2 x s .t. 4 1 x +2 2 x ? 8 30 1 x +60 2 x ? 96 1 x , 2 x ? 0 這是一個最小化的線性規劃模型 . 問這兩種原料應怎樣配合才能在滿足最低要求的條件下 使總成本最低 ? 例 17 線性規劃的一般式、標準式和矩陣式 由以上二例可知 ,線性規劃 就是 求一個線性函數在滿足一組線性等式或不等式方程在變量為非負條件下的極值問題的總稱 。 線性規劃應用舉例 線性規劃應用舉例 本部分擬采用自學與講授相結合的方式教學。 25 例 唯一解的例子 Max z=3X1－ X 2 3X1－ 2X2≤ 3 (1) 5X1＋ 4X2 ≥10 （ 2） 2X1+X2 ≤5 （ 3） X1， X2 ≥ 0 （ 4） （ 13/7， 9/7） （ 2， 0） （ 0， 0） （ 0， 5） 唯一最優解 Z(13/7,9/7)＝ 30/7 下面再看一個唯一解的例子： 一個有意義的線性規劃應該是具有唯一解的線性規劃。 (1) (2) (3) (8,0) (0,4) 28 例 無界解的例子 Max z= x1+x2 x1+x2≤ 4 （ 1） x1－ x2≤ 2 （ 2） x1,x2≥ 0 （ 3） （ 2， 0） （ 0， 4） （ 0， 0） 無界解（不等于無可行解） 在這里需要注意的是，可行域無界不等于問題無界，這要看目標函數的情況。 * 在 S為非空的情況下 ， 可行域可能是封閉的 ,也可能是不封閉的 .封閉的可行域是 有界可行域 。 一般的 LP解中最多可以有 m個分量取非零值 。 換言之 , 若對于任意兩點 s x ? ) 1 ( , s x ? ) 2 ( , 不存在 ) 1 0 ( a a , 使得 : { } S x x x x ? ? ? ) 2 ( ) 1 ( ) 1 ( a a 則稱 x 為極點 。 例 2－ 1求解演示 167。 定理 40 定理 : x是線性規劃問題之基本可行解的充要條件是 x為可行域 S=｛ x|Ax=b,x≥0｝ 上的極點 . 這一定理的另一等價表達式為 :可行解集 S中的點 x是極點的充要條件是 x為基本可行解 . （證明略） 定理 : 線性規劃的最優值必在極點上達到 （證明略）。 換言之 , 若有 : { } S S x S x x x x x ? ? ? ? ? ? ? ) 2 ( ) 1 ( ) 2 ( ) 1 ( , , 1 0 , ) 1 ( a a a 則稱 S 為凸集 ( 兩點坐標值的加權平均必在兩點的連線上 )。如果所有的非基變量都可以取零值 ,則約束方程 Ax=b可改寫為 : BxB=b () 這是因為： A=(B,N) 由于 B是滿秩陣 ,式 ()必有唯一解 xB=B1 b。 其中 ,可行域中的每一個點 （ 為一 n維向量可等價地表示為 S=｛ x|Ax=b,x≥0｝） 都稱為 可行解 ，如果 S為一空集 ,即該問題存在矛盾約束且沒有可行解 ,稱該線性規劃問題 不可行 , 線性規劃解的幾何意義及有關概念 32 * 能夠使目標函數取得極值的可行解就是 最優解 。 (1) (2) (3) X2＝－ z＋ 3X1 26 課堂練習： 試用圖解法解例 。 線性規劃的基本理論 線性規劃的圖解法 對于只有兩個變量的線性規劃問題 ， 可應用圖解法求解 ， 求解的步驟是： 1. 以 X2為縱軸 X1為橫軸畫平