1、1第五章 線性規劃一.線性規劃的基本概念二.求解線性規劃的單純形法三.初始基本可行解2 某廠生產甲、乙兩種產品，已知：兩種產品分別由兩條生產線生產。第一條生產甲，每天最多生產9件，第二條生產乙，每天最多生產7件；該廠僅有工人24名，生產甲每件用2工日，生產乙每件用3工日；產品甲、乙的單件利潤分別為40元和80元。問工廠如何組織生產才能獲得最大利潤？一）應用實例一. 線性規劃的基本概念3日利潤最大生產能力限制勞動力限制變量非負解: 設甲、乙兩種產品的日產件數分別為s.t.4二)線性規劃的一般形式s.t.特點: 1)為極小化問題; 2)約束取等號; 3)限定系數非負; 4)變量非負.式中， 價值系

2、數； 結構系數 限定系數5將數學模型化為標準型的方法1）將極大化問題化為極小化問題 剩余變量（開關變量）（兩邊乘-1）4）將負的限定系數化為正值3）將任意變量化為非負變量2）將不等式約束變為等式約束：目標函數變號； 松弛變量6s.t.化為標準型:7三）線性規劃的基本概念s.t. 1.線性規劃的圖解x2x10F=0F*=620(1.5,7)82. 線性規劃的基本概念1）可行解滿足約束條件及非負條件的解。（D內及其邊界上的解）2）基本解使n-m個變量等于0，解約束方程組(共有m個約束方程)所得的解?；窘鈱诩s束邊界的交點.3）基本可行解可行域中的基本解（即D的頂點）。4）基本變量與非基本變量

3、預先取為零值的n-m個變量為非基本變量，其余m個為基本變量。x2x10F=0F*=-620(1.5,7)s.t.9四）線性規劃的基本性質 1）可行域D為凸集，每個基本可行解對應于D上的一個頂點； 2）只要可行域存在且封閉，則起碼有一個基本可行解為最優點； *）若最優點所在的邊界線與等值線平行，則該邊界線上的點均為最優點； ）若可行域不封閉，則可能有無界解。 3)最優點可在D的頂點中尋找。10二. 求解線性規劃的單純形法一)基本思路 先取D的一個頂點作為初始點,由此出發朝可使目標函數降低最快的方向依次經過一系列的基本可行解,直至達到最優解.*1)需獲得一個初始基本可行解; 2)每次只更換一個非基

4、本變量;3)保證下降性和可行性.11二)計算實例s.t.1.初始基本可行解取x5,x6 為基本變量, 則有:0 0 0 0 4 5T122.第一次變換頂點(1)選取進基變量原則: 考慮下降性,且下降得最快判別數:假定x2進基, 則有取相應的目標函數變化量:即13寫成一般形式:最小,x3 應為進基變量推論: 若線性規劃的一個基本可行解的所有進基判別數均為非負,則該解為最優解.14(2)確定離基變量原則:考慮可行性(該變量離基后,能使余下的基本變量為非負)判別數:由于)若取 (離基),則有 應取 為正且其值為最小者對應的基本變量離基.(可行)(不可行)若取 (離基),則有 15)推論:若線性規劃的

5、的所有離基判別數均為負數時,則問題有無界解.最小,x6 應為離基變量0 0 5/3 0 2/3 0T* )因為 ,故 也必須大于0, 否則不滿足可行性要求;16進基3.第二次變換頂點去掉了(1)(2)1)確定進基變量(3)(4)172)確定離基變量 離基(1)(2)0 0 8/5 1/5 0 0T(3)(4)184. 第三次變換頂點1) 確定進基變量 故 為最優點, 為最優值:0 0 8/5 1/5 0 0T19三)用單純形表求解線性規劃例.用初等變換法求解解:增廣矩陣:20s.t.離基判別數進基判別數 單純形法實際上是解一系列的線性方程組,也可用初等變換方法列表求解.但需加入判別數的計算.4

6、21235基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15例12142123基變量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3421235基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-152242123基變量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/

7、30F111/38/37/3-25/34212基變量x1x2x3x4x5x62x41/10-1/10010.21x33/107/10101.6X2001.60.200F223.51.5已獲得最優解23-2-300基變量x1x2x3x40 x3-1110330 x41-4014-1X00034F00-2-3-2-30基變量x1x2x3x4-3x2-1103-30 x4-30116-16/3X103016F1-9-5s.t.例2問題有無界解24三. 初始基本可行解大M法 引入一組人工變量,它們在目標函數中的系數均是非常大的正數M;(2) 兩相法 引入一組人工變量,在人工變量未完全離基前目標函數為各

8、人工變量之和,當人工變量完全離基后恢復原目標函數。 當A內不包含單位矩陣時,需引入由人工變量組成的單位矩陣,以方便獲得初始可行解.25一)采用大M法獲得初始基本可行解s.t.采用大M法：s.t.原問題： 因M是比其他價值系數大得多的正數,且人工變量非負,迭代的結果會使人工變量趨于零,而獲得原問題的基本可行解.26s.t.411MM基變量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3M表一27411MM基變量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3M411M基變量x1x2x3

9、x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M1-4/3-4M/3表一表二28411基變量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40表三初始基本可行解411M基變量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-1/3-4M/3表二29411基變量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40411基變量x1x2x3x4x51x3011.81x2100.4X300.41.8F32.2表三表四初始基本可行解最優解30二)采用兩相法獲得初始基本可行解大M法的M是一個充分大的正數, 有時在計算機上不便處理.s.t.原問題：s.t.相1問題：3100011基變量x1x2x3x4x51x421210421x53310131X0 00043F07-5-4-30001基變量x1x2x3x4x51x40-14/3121.50 x1111/3013X1 10020F121-4/3表一表二32000基變量x1x2x3x4x50 x30-3/411.5-20 x115/400.50.4X2 0.501