主要內容：1、線性規劃問題及數學模型
2、線性規劃問題的解及其性質
3、**法
4、單純形法
5、大m法和兩階段法
重點與難點：線性規劃數學模型的建立：一般形成轉化為標準型的方法：單純形法的求解步驟。
要求：理解本章內容，掌握本章重點與難點問題；深刻理解線性規劃問題的基本概念、基本性質，熟練掌握其求解技巧；培養解決實際問題的能力。
§1 線性規劃的數學模型及解的性質
一、數學模型（一般形式）
例1 已知某市有三種不同體系的建築應予修建，其耗用資源數量及可用的資源限量如下表，問不同體系的面積應各建多少，才能使提供的住宅面積總數達到最大？
解：設三種體系的建築面積依次為, ,萬平方公尺，
則目標函式為
約束條件為
例2 某工廠要安排生產甲、乙兩種產品。已知：
問：如何安排兩種產品的生產數量，才能使總產值最高？
解：設分別為甲、乙兩種產品的生產量：
則目標函式為
約束條件為
從以上兩例可以看出，它們都屬於一類優化問題。它們的共同特徵：
①每乙個問題都有一組決策變數（）表示某一方案；這組決策變數的值就代表乙個具體方案。一般這些變數的取值是非負的。
②存在一定的約束條件，這些約束條件可以用一組線性等式或不等式來表示。
③都有乙個要求達到的目標，它可用決策變數的線性函式（稱為目標函式）來表示；按問題的不同，要求目標函式實現最大化或最小化。
滿足以上三個條件的數學模型稱為線性規劃的數學模型。其一般形式為：
目標函式
約束條件
可行解：滿足約束條件的一組決策變數，稱為可行解。
最優解：使目標函式取得最大（小）值的可行解，稱為最優解。
最優值：目標函式的最大（小）值，稱為最優值。
二、標準型
（一）問題的標準形式：
其中注意：任何乙個一般型都可轉化為乙個標準型。
（二）標準型的表示方法：
1、和式形式：
2、矩陣形式：
其中**係數向量
-------資源向量（限定係數向量）
約束條件係數矩陣
--------決策變數
3、向量形式：
其中為約束條件係數矩陣a的第j列。
（三）一般型化為標準型的方法
1、引進新的目標函式, 則可化為
2、不等式約束
①引進新的非負決策變數, 使得
稱為鬆弛變數，在目標函式中，其**係數為0。
②引進新的非負決策變數,使得
稱為剩餘變數，在目標函式中，其**係數為0。
3、若，即
可變為4、若某個變數無非負限制，稱為自由變數。
令例3 將下列問題化為標準型
解：標準型為
例4 將下列問題化為標準型
解：令，標準型為：
令則標準型為：
三、線性規劃問題的解
標準型記秩: 1、基陣：若列向量是線性無關的，則稱為lp問題的乙個基陣。基矩陣中每個列向量稱為基向量。
由非基向量組成的矩陣稱為非基矩陣，記為
例如：取線性無關，則
線性無關，則
2、基變數：基矩陣中各列向量對應的變數稱為基變數，記為。
如, 則基變數為。
對應於非基向量的變數稱為非基變數，記為
3、基本解：設基矩陣為，則非基矩陣
那麼，約束方程即--------有無窮解
令則那麼，約束方程組的解 ，將其稱為問題的基本解。注意：基本解不一定是可行解，若,則稱為問題的基本可行解，對應於基本可行解的基矩陣，稱為可行基。
4、最優解：對應於某一可行基，使目標函式獲得最優值的基本可行解，稱為最優解。最優解所對應的基矩陣稱為最優基。
舉例說明
約束矩陣
若取基矩陣則非基矩陣基變數,非基變數
∴基本解為是基本可行解若取基矩陣則基本可行解注意：基本可行解與可行域的頂點座標是一一對應的。
§2 **法---主要解決二維線性規劃問題
一、按約束條件，繪出解的可行域圖形
可行域：可行解的全體稱為可行域。
將等值線沿法線方向向上平移至（20，24）點時截距最大，那麼最優解為（20，24）t。
二、解的情況最優解有以下幾種情況：
（1）有唯一的最優解。（2）有多個最優解。如上例中，若，就有無窮多解。
（3）有無界解：若有可行解，但無有限最優解，則稱其為有無界解(這種情況在約束條件考慮不周全時出現)。 如
(4)無可行解（約束條件有矛盾）如：
結論：①約束集合一定是凸條邊形（二維）； ②若有最優解，則一定可在多邊形頂點獲得。
§3單純形法
單純形法的基本思路是：根據問題的標準，從可行域中某個基本可行解（乙個頂點）開始，轉換到另乙個基本可行解（頂點）；並且使目標函式達到最大值時，問題就得到了最優解。即
初始頂點 (可行域一頂點) …
一、單純形法的求解步驟
（1）尋找初始可行基,並計算初始基本可行解；（2）檢驗基本可行解是否最優；（3）尋找更好的可得基；
（4）重複（2），（3）。
1、初始可行基的確定i)若a中含有階單位矩陣,則取。此時， 是可行基ii)若中不含有m階單位矩陣，就採用人造基的方法。即增加人工變數把原問題化為含有的等價問題。
（下一節重點講）例：
因為係數數陣a中不含有單位矩陣，需增加人工變數化為
則 注意：鬆馳變數、剩餘變數的價值係數取為0，而人工變數的價值係數取值為大m。
2、檢驗
基本可行解
對應的目標函式值
非基變數價值係數
基變數價值係數
對任意可行解變化為
即將其代入目標函式得：
當時，的最大值是
即為最優解。
這裡，我們稱每個為檢驗數。
當檢驗數
第個基變數的**係數
第個非基變數的**係數
如果為最優解，則最優值為
判斷定理：（對標準型maxz來講）
（1）若所有，則為最優解。
（2）若所有,且有某個，則lp問題有無窮多個最優解。
（3）若有某個，則不是最優解。
（4）當時，若有乙個，且對一切都有,則有無界解(或無最優解)。
3、基變換：確定新的基矩陣的過程
（1）換入變數的確定
選擇中的最大者所對應的變數作為換入變數，即
（2）換出變數的確定：用最小比值規則（θ規則）
設則取為換出變數
當時，則取為換出變數，稱為主元素
（3）新基矩陣的確定
如：解： 取初始基矩陣
那麼基可行解
檢驗數：
不是最優解，換入變數為
換出變數為（基變數中的第3個變數），主元素為
增廣矩陣變換：
新的基矩陣
新基可行解
檢驗數：
不是最優解。
二、單純形表：（將上述過程列成**,便於理解）
對每乙個可行基，作乙個單純形表，包括①基可行解②檢驗數③和主元素。
列中填入基變數，這裡是
列中填入基變數的價值係數，與基變數一一對應，這裡是
列中填入約束方程組右端的常數；
行中填入各變數的價值係數
列的數字是在確定換入變數後，按規則計算出來的比值；
行為檢驗數行，對應各非基變數的檢驗數。
例：（按上例）
解：最優解為
最優值為
§4單純形法的進一步討論
一、人工變數法
1、大m法
在乙個線性規劃問題的約束條件中加入人工變數後，要求人工變數對結目標函式值不受影響，為此我們假定人工變數在目標函式中的係數為（-m）（m為任意大的正數），這樣目標函式實現最大化時，必需把人工變數換出。
例5試用大m法求解
解：化為標準型
運籌學 第二章線性規劃的對偶問題
習題二2.1 寫出下列線性規劃問題的對偶問題 1 max z 10x1 x2 2x3 2 max z 2x1 x2 3x3 x4 st.x1 x2 2 x3 10st.x1 x2 x3 x4 5 4x1 x2 x3 202x1 x2 3x3 4 xj 0 j 1,2,3x1 x3 x4 1 x1，x...
運籌學 線性規劃
數學與計算科學學院 實驗報告 實驗專案名稱線性規劃 所屬課程名稱運籌學b 實驗型別綜合實驗 實驗日期 班級成績 附錄1 源程式 附錄2 實驗報告填寫說明 1 實驗專案名稱 要求與實驗教學大綱一致.2 實驗目的 目的要明確，要抓住重點，符合實驗教學大綱要求.3 實驗原理 簡要說明本實驗專案所涉及的理論...
運籌學中線性規劃例項
實驗報告 課程名稱 運籌學導論 實驗名稱 線性規劃問題例項分析 專業名稱 資訊管理與資訊系統 指導教師 劉珊 團隊成員 鄧欣 20112111 蔣青青 20114298 吳婷婷 20112124 邱子群 20112102 熊遊 20112110 余文媛 20112125 日期 2013 10 25 ...