最優(yōu)化方法課件：2-2 線性規(guī)劃的標準型和基本概念

1、1線性規(guī)劃 線性規(guī)劃問題及其數(shù)學模型 線性規(guī)劃的單純形法 線性規(guī)劃的對偶理論 線性規(guī)劃的靈敏度分析2美國數(shù)學家，美國全國科學院院士。線性規(guī)劃的奠基人。1914年11月8日生于美國俄勒岡州波特蘭市。1946年在伯克利加利福尼亞大學數(shù)學系獲哲學博士學位。1947年丹齊克在總結(jié)前人工作的基礎(chǔ)上創(chuàng)立了線性規(guī)劃, 并提出了解決線性規(guī)劃問題的單純形法。 19371939年任美國勞工統(tǒng)計局統(tǒng)計員，19411952年任美國空軍司令部數(shù)學顧問、戰(zhàn)斗分析部和統(tǒng)計管理部主任。19521960年任美國蘭德公司數(shù)學研究員，19601966年任伯克利加利福尼亞大學教授和運籌學中心主任。1966年后任斯坦福大學運籌學和計算

2、機科學教授。1971年當選為美國科學院院士。1975年獲美國科學獎章和諾伊曼理論獎金。George Bernard Dantzig (1914) 3康托羅維奇，. 前蘇聯(lián)著名經(jīng)濟學家，蘇聯(lián)著名經(jīng)濟學家 。前蘇聯(lián)科學院院士 。前蘇聯(lián)國家科學技術(shù)委員會國民經(jīng)濟管理研究所經(jīng)濟問題研究主任。最優(yōu)計劃理論的創(chuàng)始人。 1912年生，1930年畢業(yè)于列寧格勒大學物理數(shù)學系，1935年獲數(shù)學博士學位。1964年被選為蘇聯(lián)科學院院士。因提出資源最大限度分配理論，1975年與美籍荷蘭學者T.C.庫普曼斯一起獲得諾貝爾經(jīng)濟學獎金。 4 康托羅維奇的主要貢獻是把線性規(guī)劃用于經(jīng)濟管理，創(chuàng)立了最優(yōu)計劃理論。對有效利用資源

3、和提高企業(yè)經(jīng)濟效益起了重大作用。他還提出經(jīng)濟效果的概念和衡量經(jīng)濟效果的統(tǒng)一指標體系,作為經(jīng)濟決策的定量依據(jù),來選擇最合理的社會生產(chǎn)結(jié)構(gòu)。 主要著作有生產(chǎn)組織與計劃的數(shù)學方法(1939)、資源最優(yōu)利用的經(jīng)濟計算(1959)、最優(yōu)計劃的動態(tài)模型(1964)等。 5 佳林庫普曼斯(1910年1985年)，美國人，1910年8月28日生于荷蘭，1940年離開荷蘭移居美國。1975年，他和康托羅維奇同時獲得諾貝爾經(jīng)濟學獎。線性規(guī)劃經(jīng)濟分析法的創(chuàng)立者。 6 馮諾依曼（John von Neumann，1903年12月28日1957年2月8日）是出生于匈牙利的美國籍猶太人數(shù)學家，現(xiàn)代電子計算機創(chuàng)始人之一。他

4、在計算機科學、經(jīng)濟、物理學中的量子力學及幾乎所有數(shù)學領(lǐng)域都作過重大貢獻。 1940年以后，馮諾伊曼轉(zhuǎn)向應用數(shù)學。在力學、經(jīng)濟學、數(shù)值分析和電子計算機方面作出了卓越貢獻。 從1942年起，他同莫根施特恩合作，寫作博弈論和經(jīng)濟行為一書，使他成為數(shù)理經(jīng)濟學的奠基人之一。72 線性規(guī)劃的標準型和基本概念 線性規(guī)劃問題及其數(shù)學模型 線性規(guī)劃的圖解法 線性規(guī)劃的標準形式 標準型線性規(guī)劃的解的概念 線性規(guī)劃的基本理論 問題的提出： 在生產(chǎn)管理的經(jīng)營活動中，通常需要對“有限的資源”尋求“最佳”的利用或分配方式。有限資源：勞動力、原材料、設(shè)備或資金等 最佳：有一個標準或目標，使利潤達到最大或成本達到最小。 有限

5、資源的合理配置有兩類問題如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達到最大；在生產(chǎn)或經(jīng)營的任務確定的條件下，合理的組織生產(chǎn)，安排經(jīng)營活動，使所消耗的資源數(shù)最少。 線性規(guī)劃問題及其數(shù)學模型例，某制藥廠生產(chǎn)甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設(shè)備時間，以及該廠每周可提供的資源總量如下表所示：每噸產(chǎn)品的消耗 每周資源總量 甲乙維生素（公斤） 3020160設(shè)備（臺班） 5115已知該廠生產(chǎn)每噸甲、乙藥品的利潤分別為5萬元和2萬元。但根據(jù)市場需求調(diào)查的結(jié)果，甲藥品每周的產(chǎn)量不應超過4噸。問該廠應如何安排兩種藥品的產(chǎn)量才能使每周獲得的利潤最大？ 定義x1

6、為生產(chǎn)甲種藥品的計劃產(chǎn)量數(shù)，x2為生產(chǎn)乙種藥品的計劃產(chǎn)量數(shù)。 數(shù)學模型為 s.t. （subject to) (such that) 每噸產(chǎn)品的消耗 每周資源總量 甲乙維生素（公斤） 3020160設(shè)備（臺班） 5115單位利潤（萬元） 511例2 靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3，在兩個工廠之間有一條流量為200萬m3的支流。兩化工廠每天排放某種有害物質(zhì)的工業(yè)污水分別為2萬m3和1.4萬m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于0.2%。兩化工廠處理工業(yè)污水的成本分別為1000元/萬m3和80

7、0元/萬m3?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這兩個工廠處理工業(yè)污水的費用最小工廠1工廠2200萬m3500萬m312決策變量：x1、x2分別代表工廠1和工廠2處理污水的數(shù)量(萬m3)。則目標函數(shù)：min z=1000 x1+800 x2約束條件：第一段河流（工廠1工廠2之間）： (2x1)/500 0.2%第二段河流： 0.8(2x1) +(1.4x2)/7000.2%此外有： x12； x21.4化簡有： min z=1000 x1+800 x2 x1 1 0.8x1 + x2 1.6 x1 2 x21.4 x1、x20稱之為上述問題的數(shù)學模型。例，某鐵器加工廠

8、要制作100套鋼架，每套要用長為2.9米，2.1米和1.5米的圓鋼各一根。已知原料長為7.4米，問應如何下料，可使材料最省？分析：在長度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納出8種不同的下料方案：圓鋼（米）291201010021002211301531203104料頭（米）00.10.20.30.80.91.1.4設(shè)xj表示用第j種下料方案下料的原料根數(shù)，j=1,28, 數(shù)學模型 s.t. 這是一個下料問題，是在生產(chǎn)任務確定的條件下，合理的組織生產(chǎn)， 使所消耗的資源數(shù)最少的數(shù)學規(guī)劃問題。 滿足一組約束條件的同時，尋求變量x1至x8的值,使目標函數(shù)取得最 小值。 圓鋼（米）2912010

9、10021002211301531203104料頭（米）00.10.20.30.80.91.11.4且為整數(shù) 線性規(guī)劃的一般數(shù)學模型 線性規(guī)劃模型的特征：（1）用一組決策變量x1，x2，xn表示某一方案，且在一般情況下，變量的取值是非負的。（2）有一個目標函數(shù)，這個目標函數(shù)可表示為這組變量的線性函數(shù)。（3）存在若干個約束條件，約束條件用決策變量的線性等式或線性不等式來表達。（4）要求目標函數(shù)實現(xiàn)極大化（max）或極小化（min）。滿足上述4個特征的規(guī)劃問題稱為線性規(guī)劃問題 線性規(guī)劃的一般數(shù)學模型 目標函數(shù) 滿足約束條件 通常稱 為決策變量， 為價值系數(shù)， 為消耗系數(shù), 為資源限制系數(shù)。 線性規(guī)

10、劃的圖解法 適用于求解兩個變量的線性規(guī)劃問題 圖解法的基本步驟例4,利用例1說明圖解法的主要步驟， 例1的數(shù)學模型為 s.t. O51015x1x1=4x25101AB( 2, 5)CZ5x1+x2=1530 x1+20 x2=1605x1+2x2=5 圖解法的幾種可能結(jié)果 (1）有唯一最優(yōu)解，如例1。（2）有無窮多最優(yōu)解 如例1中的目標函數(shù)設(shè)為 maxZ=10 x1+2x2 則目標函數(shù)等值線10 x1+2x2=Z 與第二約束 5x1+x215 的邊界線平行。將等值線沿梯度Z =（10，2）正方向平移 至B點時與可行域OABC的整條邊界線AB重合。 這表明線段AB上的每一點都使目標函數(shù)取得同樣

11、的最大值， 因而都是最優(yōu)解。20O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530 x1+20 x2=16010 x1+2x2=5例5，試用圖解法求解下列線性規(guī)劃問題 st.（3） 無界解（或稱無最優(yōu)解） 無界解是指線性規(guī)劃問題的最優(yōu)解無界。若是極大化問題，則可使目標函數(shù)值Z+, 極小化問題 則可使目標函數(shù)值Z-， 有無界解的線性規(guī)劃問題的可行域是無界區(qū)域，但反之則不必然。-1 O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1 O33（4）無可行解 某些線性規(guī)劃問題的可行域是空集，既不存在滿足所有約束條件的點，這時問題無可行解，當然更談不上最優(yōu)

12、解了。 在實際中出現(xiàn)這種情況可以認為資源條件無法滿足人們的要求，既不存在可行方案。 24例6 max z=x1+2x2 x1 + 2x21 x1 + x22 x1、x20無可行解。1112OA25以上幾種情況的圖示如下：可行域有界唯一最優(yōu)解可行域有界多個最優(yōu)解26可行域無界唯一最優(yōu)解可行域無界無窮多最優(yōu)解27可行域無界目標函數(shù)無界可行域為空集無可行解281. 有最優(yōu)解 唯一最優(yōu)解 無窮多最優(yōu)解2. 最優(yōu)解無界3. 無可行解29直觀結(jié)論：（1）可行域可以是個凸多邊形，可能無界，也可能為空；（2）若線性規(guī)劃問題的最優(yōu)解存在，它一定可以在可行域的某一個頂點上得到；（3）若在兩個頂點上同時得到最優(yōu)解，

13、則該兩點連線上的所有點都是最優(yōu)解，即LP有無窮多最優(yōu)解；（4）若可行域非空有界，則一定有最優(yōu)解。30O51015x1x25101AB( 2, 5)C5x1+x2=1530 x1+20 x2=160 標準線性規(guī)劃模型 線性規(guī)劃問題的標準形式： s.t 其中（2） （3）線性規(guī)劃的標準形式（1）緊湊格式： s.t.向量格式： s.t. 其中 稱為價值向量， 為決策變量向量， 為決策變量xj所對應的消耗系數(shù)向量， 為資源向量。矩陣格式：其中 為mn階矩陣 為價值向量， 為決策變量向量， 為資源向量。33非標準形式線性規(guī)劃問題的標準化（1）極大化與極小化 ： 若 ，令 ，則有 原目標函數(shù) 。(2)線性

14、不等式與線性等式： 其中 為非負松弛變量， 其中 為非負剩余變量。 35 (4) 非負變量與符號不受限制的變量 若 xi的符號不受限制，則可引進非負變量xi1,xi2，令 xi = xi1-xi2，這樣就可以使線性規(guī)劃里所有的變量都轉(zhuǎn)化為有非負限制的變量。 (3) 右端項為負 約束兩端乘以（1）例7，將下述線性規(guī)劃問題化為標準型 解：令,其中符號不受限制37O51015x1x25101AB( 2, 5)C5x1+x2=1530 x1+20 x2=160考慮一個標準的線性規(guī)劃問題： s.t 其中為n維列向量， 是n維列向量， 是m維列向量， 是mn階矩陣，假定滿足mn，且()=m，標準型線性規(guī)劃

15、的解的概念 線性規(guī)劃問題解的概念： (1) 可行解。滿足約束條件的解可行解集稱為線性規(guī)劃問題的可行域。(2) 最優(yōu)解。使目標函數(shù)達到最優(yōu)值的的可行解稱為最優(yōu)解，最優(yōu)解常用 表示?；蛄?，基變量 若是線性規(guī)劃問題的一個基，那么一定是由m個線性無關(guān)的列向量組成，不失一般性，可設(shè) 稱 為基向量，與基向量相對應的變量稱為基變量。 基的個數(shù) 一個線性規(guī)劃的基通常不是唯一的，但是基的個數(shù)不會超過 個。(3) 基。若是中mm階非奇異矩陣，即|0，則稱是線性規(guī)劃問題的一個基。 (4) 基本解。設(shè)B是線性規(guī)劃的一個基，若令n-m個非基變量等于0，則所得的方程組=b的解稱為線性規(guī)劃問題的一個基本解（簡稱基解）?；?/p>

16、本解的個數(shù)也不會超過 個。 由于基本解中的非零分量可能是負數(shù)，所以基本解不一定是可行的。(5) 基本可行解。滿足非負條件的基本解稱為基本可行解 （簡稱基可行解）。與基本可行解對應的基稱為可行基。 基本可行解的非零向量的個數(shù)小于等于m，并且都是非負的。當基本可行解中有一個或多個基變量取零值時，稱此解為 退化的基本可行解。42 一個線性規(guī)劃問題，如果它的所有基本可行解都是非退化的，那么 稱這個線性規(guī)劃是非退化的. 對非退化線性規(guī)劃，可行基和基本可行解之間是一一對應的。 線性規(guī)劃問題各種解的關(guān)系可用文氏圖表示， 可行解基本解基本可行解例8、求下列約束方程所對應的線性規(guī)劃的所有基本解， 基本可行解。

17、s.t 解：化為標準形式 為24階矩陣。 且R(A)=2,所以該線性規(guī)劃基的個數(shù) =6個 取 , 為基變量， 若令非基變量 ， 約束方程組為 可得對應的基本解 是一個基本可行解。 按相同步驟，可求得線性規(guī)劃其他4個基：對應基本解是一個基本可行解。 對應基本解是一個基本可行解。 對應基本解不是一個基本可行解。 對應基本解是一個基本可行解。 若利用圖解法畫出線性規(guī)劃的可行域，如圖，CDOBA44847例9、已知線性規(guī)劃問題的約束條件為 試討論可行域頂點和基本可行解之間的對應關(guān)系。解:可行域為四維凸多面體，可以推得在四維空間中有3個頂點，=(0,0,10,10)，=(0,10,0,10)，=(10,

18、0,0,0)。這3個頂點與線性規(guī)劃的5個基本可行解的對應關(guān)系如下：頂點對應以x3,x4為基變量的基本可行解；頂點對應以x2,x4為基變量的基本可行解；頂點對應x1,x2;x1,x3和x1,x4為基變量的退化基本可行解， BCA 線性規(guī)劃的基本理論 由圖解法的步驟，可以從幾何的角度得出結(jié)論：（1）線性規(guī)劃問題的可行域是一個有界或無界的凸多邊形，其頂點個數(shù)是有限個。（2）若線性規(guī)劃問題有最優(yōu)解，那么最優(yōu)解一定可在可行域的某個頂點上找到。49 線性規(guī)劃的基本定理 引理1：線性規(guī)劃問題的可行域是一個凸集。 定理1：線性規(guī)劃問題的可行解是基本可行解的充要條件是 的正分量所對應的系數(shù)列向量線性無關(guān)。 定理

19、2：設(shè)線性規(guī)劃問題的可行解是的一個頂點的 充分必要條件是為基本可行解。 定理3：若可行域D非空，那么一定存在D的頂點（極點)。 若線性規(guī)劃問題存在可行解，則一定存在基本可行解。定理4：若線性規(guī)劃問題存在最優(yōu)解，則必存在基本可行解 是最優(yōu)解。50引理1：若線性規(guī)劃問題存在可行域，則其可行域是一個凸集。證明：為了證明滿足=，0的所有點（可行解）組成的幾何體是凸集，只要證明中任意兩點連線上的一切點均滿足線性約束條件既可。任取，滿足則對任意的有 線性規(guī)劃的基本定理 又因為均0，所以由此可知，即是凸集。證明：必要性：因為是基本解，由基本解的定義，的非零分量所對應的系數(shù)列向量線性無關(guān)，又因為是可行解，由基本可行解的定義，非零分量均是正的，所以的正分量所對應的系數(shù)列向量線性無關(guān)。 定理1：線性規(guī)劃問題的可行解 是基本可行解的充要條件是的