線性規(guī)劃概論與圖解法

1、第一章 線性規(guī)劃與單純形方法1第一章線性規(guī)劃與單純形方法1.2 線性規(guī)劃基本概念1.3 線性規(guī)劃問題的數(shù)學(xué)模型1.4 線性規(guī)劃問題解的概念1.1 線性規(guī)劃（概論）2線性規(guī)劃（Linear Programming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1.1 線性規(guī)劃（概論）3線性規(guī)劃（概論）線性規(guī)劃（Linear Programming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算法（Simpler）4線性規(guī)劃（概論）線性規(guī)劃（Linear Programming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算

2、法（Simpler）1963年Dantzig寫成“Linear Programming and Extension”5線性規(guī)劃（概論）線性規(guī)劃（Linear Programming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算法（Simpler）1963年Dantzig寫成“Linear Programming and Extension”1979年蘇聯(lián)的Khachian提出“橢球法”6線性規(guī)劃（概論）線性規(guī)劃（Linear Programming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算法（Simpler）1963年Da

3、ntzig寫成“Linear Programming and Extension”1979年蘇聯(lián)的Khachian提出“橢球法”1984年印度的Karmarkar提出“投影梯度法” 7線性規(guī)劃（概論）線性規(guī)劃（Linear Programming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算法（Simpler）1963年Dantzig寫成“Linear Programming and Extension”1979年蘇聯(lián)的Khachian提出“橢球法”1984年印度的Karmarkar提出“投影梯度法” 線性規(guī)劃是研究線性不等式組的理論，或者說是研究（高維空間中

4、）凸多面體的理論，是線性代數(shù)的應(yīng)用和發(fā)展。8生產(chǎn)計(jì)劃問題如何合理使用有限的人力，物力和資金，使得收到最好的經(jīng)濟(jì)效益。如何合理使用有限的人力，物力和資金，以達(dá)到最經(jīng)濟(jì)的方式，完成生產(chǎn)計(jì)劃的要求。1.2 線性規(guī)劃基本概念9例1.1 生產(chǎn)計(jì)劃問題（資源利用問題） 勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子銷售價格30元/個，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？10解：將一個實(shí)際問題轉(zhuǎn)化為線性規(guī)

5、劃模型有以下幾個步驟：11解：將一個實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟：1確定決策變量：x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量12解：將一個實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟：1確定決策變量：x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量2確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大 max z=50 x1+30 x213解：將一個實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟：1確定決策變量：x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量2確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大 max z=50 x1+30 x23確定約束條件： 4x1+3x2 120（木工工時限制） 2x1+x2 50 （

6、油漆工工時限制）14解：將一個實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟：1確定決策變量：x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量2確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大 max z=50 x1+30 x23確定約束條件： 4x1+3x2 120（木工工時限制） 2x1+x2 50 （油漆工工時限制）4變量取值限制： 一般情況，決策變量只取正值（非負(fù)值） x1 0, x2 0 15解：將一個實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個步驟：1確定決策變量：x1=生產(chǎn)桌子的數(shù)量 x2=生產(chǎn)椅子的數(shù)量2確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大 max z=50 x1+30 x23確定約束條件： 4x1+

7、3x2120（木工工時限制） 2x1+x2 50 （油漆工工時限制）4變量取值限制： 一般情況，決策變量只取正值（非負(fù)值） x1 0, x2 0 16數(shù)學(xué)模型 max S=50 x1+30 x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1,x2 0線性規(guī)劃數(shù)學(xué)模型三要素： 決策變量、約束條件、目標(biāo)函數(shù)17例1 .2 營養(yǎng)配餐問題 假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最??？1.3 線性規(guī)劃問題的數(shù)學(xué)模型1

8、8各種食物的營養(yǎng)成分表19解：設(shè)xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為： min S=14x1+6x2 +3x3+2x4 s.t. 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 020其他典型問題：合理下料問題運(yùn)輸問題生產(chǎn)的組織與計(jì)劃問題投資證券組合問題分派問題生產(chǎn)工藝優(yōu)化問題21線性規(guī)劃問題的一般形式：Max(Min)S=c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a

9、1nxn (=, )b1 a21x1+a22x2+.+a2nxn (=, )b2 . am1x1+am2x2+.+amnxn (=, )bm x1,x2.xn 022線性規(guī)劃問題隱含的假定：比例性假定可加性假定連續(xù)性假定確定性假定23線性規(guī)劃問題隱含的假定：比例性假定：決策變量變化引起的目標(biāo)函數(shù)的改變量和決策變量的改變量成比例，同樣，每個決策變量的變化引起約束方程左端值的改變量和該變量的改變量成比例。可加性假定：每個決策變量對目標(biāo)函數(shù)和約束方程的影響是獨(dú)立于其他變量的，目標(biāo)函數(shù)值是每個決策變量對目標(biāo)函數(shù)貢獻(xiàn)的總和。24線性規(guī)劃問題隱含的假定：連續(xù)性假定：線性規(guī)劃問題中的決策變量應(yīng)取連續(xù)值。確定

10、性假定：線性規(guī)劃問題中的所有參數(shù)都是確定的參數(shù)。線性規(guī)劃問題不包含隨機(jī)因素。25線性規(guī)劃問題的標(biāo)準(zhǔn)形式(1)：Max S=c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a1nxn=b1 a21x1+a22x2+.+a2nxn=b2 . am1x1+am2x2+.+amnxn=bm x1,x2.xn 0其中：bi 0(i=1,2,.m)26線性規(guī)劃問題的標(biāo)準(zhǔn)形式(2)： n Max S = cjxj j=1 n s.t. aijxj = bi (i=1,2,.m) j=1 xj 0 (j=1,2,.n)其中： bi 0 (i=1,2,.m)27線性規(guī)劃標(biāo)準(zhǔn)型的矩陣形式(3

11、)（矩陣表達(dá)型）： Max S = CX s.t. AX = b X 0其中：28如何將一般問題化為標(biāo)準(zhǔn)型：若目標(biāo)函數(shù)是求最小值 Min S = CX 則令 S= - S, 變?yōu)?Max S= - CX2. 若約束條件是不等式若約束條件是“”不等式, 將原條件變?yōu)椋?n aijxj + xs = bi j=1 xs 0是新引入的非負(fù)松馳變量29如何將一般問題化為標(biāo)準(zhǔn)型：3. 若約束條件是“”不等式，則變?yōu)?n aijxj - xt = bi j=1 Xt 0是引入的非負(fù)松馳變量4. 若約束條件右面的某一常數(shù)項(xiàng) bi0這時只要在bi相對應(yīng)的約束方程兩邊乘上-1。30如何將一般問題化為標(biāo)準(zhǔn)型：5.

12、 若變量 xj無非負(fù)限制，引進(jìn)兩個非負(fù)變量xj xj” 0 令xj = xj- xj” 通過以上步驟，任何形式的線性規(guī)劃總可以化成標(biāo)準(zhǔn)型。31例1.3 將下列問題化成標(biāo)準(zhǔn)型:Min S = -x1+ 2x2- 3x3s.t. x1+ x2 + x3 7 x1 - x2 + x3 2 -3x1 + x2 + 2x3 = 5 x1 , x2 0 x3 無非負(fù)限制32標(biāo)準(zhǔn)型：Max Z = x1- 2x2+ 3x3 - 3x4s.t. x1+ x2+ x3 - x4 + x5 = 7 x1- x2+ x3 - x4 - x6 = 2 -3x1+ x2+ 2x3 - 2x4 = 5 x1, x2,x3

13、,x4, x5,x6 0注：標(biāo)準(zhǔn)型還不一定是便于求解的形式。33課堂練習(xí)：請閱讀P1 P3 中的例1.1、例1.2、例1.4。之后完成P31 1.1(1)(2)(4)；1.2。請獨(dú)立完成：P34 1.8341.4 線性規(guī)劃問題解的概念線性規(guī)劃問題的解：（1）滿足約束條件的變量的值，稱為可行解。（2）使目標(biāo)函數(shù)取得最優(yōu)值的可行解，稱為最優(yōu)解。35線性規(guī)劃問題圖解法：例 1.1的數(shù)學(xué)模型 max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 036x2504030201010203040 x14x1+3x2 120由 4x1+3x2 12

14、0 x1 0 x2 0圍成的區(qū)域max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 037x2504030201010203040 x12x1+x2 50由 2x1+x2 50 x1 0 x2 0圍成的區(qū)域max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 038x2504030201010203040 x12x1+x2 504x1+3x2 120可行域同時滿足：2x1+x2 504x1+3x2 120 x1 0 x2 0的區(qū)域可行域max S=50 x1 + 30 x2

15、 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 039x2504030201010203040 x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由約束條件圍成的區(qū)域，該區(qū)域內(nèi)的每一點(diǎn)都是可行解，它的全體組成問題的解集合。該問題的可行域是由O，Q1，Q2，Q3作為頂點(diǎn)的凸多邊形max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 040 x2504030201010203040 x1可行域目標(biāo)函數(shù)是以S作為參數(shù)的一組平行線x2 = S/30-（5/3）x1max S=50 x1

16、 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 041x2504030201010203040 x1可行域當(dāng)S值不斷增加時，該直線x2 = S/30-（5/3）x1沿著其法線方向向右上方移動。max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 042x2504030201010203040 x1可行域當(dāng)該直線移到Q2點(diǎn)時，S（目標(biāo)函數(shù)）值達(dá)到最大：Max S=50*15+30*20=1350此時最優(yōu)解=（15，20）Q2（15，20）max S=50 x1 + 30 x2 s.t. 4x1

17、 + 3x2 120 2x1 + x2 50 x1 x2 043二個重要結(jié)論：1。滿足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實(shí)可以推廣到更多變量的場合。2。最優(yōu)解必定能在凸多邊形的某一個頂點(diǎn)上取得，這一事實(shí)也可以推廣到更多變量的場合。44解的討論：最優(yōu)解是唯一解；45解的討論：1。最優(yōu)解是唯一解2。無窮多組最優(yōu)解：例1.1的目標(biāo)函數(shù)由 max S=50 x1+30 x2變成： max S=40 x1+30 x2 s.t. 4x1+ 3x2 120 2x1+ x2 50 x1,x2 046x2504030201010203040 x1可行域目標(biāo)函數(shù)是同約束條件：4x1+3x2 120平行的直

18、線x2 = S/30-（4/3）x1max S=40 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 047x2504030201010203040 x1可行域當(dāng)S的值增加時，目標(biāo)函數(shù)同約束條件：4x1+3x2 120重合，Q1與Q2之間都是最優(yōu)解。Q1（25，0）Q2（15，20）48解的討論：最優(yōu)解是唯一解；無窮多組最優(yōu)解：無界解：例：max S = x1 + x2 s.t. -2x1+ x2 40 x1 - x2 20 x1 x2 049x2504030201010203040 x1該可行域無界，目標(biāo)函數(shù)值可增加到無窮大，稱這種情況為無界解

19、或無最優(yōu)解。-2x1+x2 40 x1-x2 2050解的討論：無可行解：例：max S=2x1+3x2 s.t. x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0該問題可行域?yàn)榭占?，即無可行解，也不存在最優(yōu)解。51解的情況：1。有可行解2。有唯一最優(yōu)解3。有無窮最優(yōu)解4。無最優(yōu)解5。無可行解52課堂練習(xí)： P34 1.7 (偶數(shù)號)53線性規(guī)劃問題解的概念線性規(guī)劃標(biāo)準(zhǔn)型的矩陣形式：Max S = C X （1- 9） s.t. A X = b （1-10） X 0 （1-11）其中54解、可行解、最優(yōu)解1。滿足約束條件（1-10）的X，稱為 線性規(guī)劃問題的解。2。滿足

20、約束條件（1-10）與（1-11） 的X，稱為線性規(guī)劃的問題可行解。 3。使目標(biāo)函數(shù)（1-9）取得最優(yōu)的可行解X 稱為線性規(guī)劃的問題最優(yōu)解。Max S = CX （1- 9） s.t. AX=b （1-10） X 0 （1-11）55基、基向量、基變量1。設(shè) r(A) = m,并且B是A的m 階非奇異 的子矩陣（det(B) 0),則稱矩陣 B為線性規(guī)劃問題的一個基。2。設(shè)矩陣 B =（P1，P2 . Pm)是一個基 ，其列向量 Pj 稱為對應(yīng)基B的基向量。 3。與基向量 Pj 相對應(yīng)的變量xj就稱為 基變量，其余的就稱為非基變量。56基礎(chǔ)解.基礎(chǔ)可行解.可行基1。對于某一特定的基B，非基變量取 0 值的解，稱為基礎(chǔ)解。2。滿足非負(fù)約束條件的基礎(chǔ)解，稱 為基礎(chǔ)可行解。3。與基礎(chǔ)可行解對應(yīng)的基，稱為可 行基。57為了理解基礎(chǔ)解.基礎(chǔ)可行解.最優(yōu)解的概念，用下列例子說明：例1.4：max S = 2x1 + 3x2 （1-12 ） s.t. -2x1 + 3x2 6 （1-13-1） 3x1 - 2x2 6 （1-13-2） x1 + x2 4 （1-13-3） x1, x2 0 （1-14 ） 58將該問題化為標(biāo)準(zhǔn)形