【正文】 每頭日需 10 5 8 7 養(yǎng)分 飼料 課堂練習(xí) 某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的 A、 B、 C、 D四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的 M、 N兩種飼料中選擇，試決定總花費最小的購買方案。（列出模型） A B C D 價格 M 0 300 N 200 每頭日需 10 5 8 7 養(yǎng)分 飼料 答案： 設(shè)購買 M飼料 x1， N飼料 x2 x1 +≥10 + ≥5 + ≥8 ≥7 x1 , x2≥0 . Min Z=300 x1 +200x2 思考題 二、線性規(guī)劃的圖解法 1. 步驟 （ 1）作約束的圖形 —— 可行域 可行解的集合 ① 先作非負約束 ②再作資源約束 9x1+4x2=360 4x1+5x2=200 3x1+10x2=300 公共部分，即為可行域 例：煤電油例 Max Z=7 x1 +12x2 9 x1 +4x2≤360 4x1 +5x2 ≤200 3 x1 +10x2 ≤300 x1 , x2≥0 . x1 x2 40 20 60 80 100 20 40 60 80 100 0 （ 2）作目標函數(shù)的等值線 ① 給 z不同的值，作相應(yīng)直線，判斷出 z增大時，直線的移動方向 ② 將直線向增大方向移動，直至可行域邊界，交點 X*即為最優(yōu)解。 7x1+12x2=84 7x1+12x2=168 如：令 7 x1 +12x2=84 7 x1 +12x2=168 9x1+4x2=360 4x1+5x2=200 3x1+10x2=300 x1 x2 40 20 60 80 100 20 40 60 80 100 0 X*=（ 20， 24）， Z*=428 最優(yōu)解： x1 = 0， x2 = 1 最優(yōu)目標值 z = 3 課堂練習(xí) 圖解法求解線性規(guī)劃 ????????????????0,)3(22)2(22)1(432m i n2121212121xxxxxxxxstxxz0 1 2 3 4 1 2 3 4 x 1 x 2 O 1 2 (1) (2) (3) 2. LP 解的幾種情況 （ 1）唯一解 （ 2）多重最優(yōu)解 （ 3）無可行解 注：出現(xiàn)（ 3）、（ 4）情況時，建模有問題 （ 4）無有限最優(yōu)解 補充知識：凸集 凸集：在點集中任取兩點，則其連線仍在其中。 即沒有凹入的部分；沒有空洞。 ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ 在凸集 ⑵中，點 A， B， C， D稱為極點（或頂點）。 A B C D 從圖解法中我們了解到以下事實： ①若 LP問題的可行域存在，則可行域一定是凸集。 ②若 LP問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有 無窮多最優(yōu)解的話）一定是可行域凸集的某個極點（頂 點）。 思路： ①最優(yōu)解先在可行域中找。（可行域為空集，則無可 行解，故無最優(yōu)解。） ②最優(yōu)解在可行域的極點中找。 ③極點是有限個，若兩個極點都是最優(yōu)解，則兩個極點所連 線段上的所有點均是最優(yōu)解） 定義： LP問題的可行域的極點（頂點）稱為基本可行解。 三、 線性規(guī)劃應(yīng)用舉例與軟件求解 例 1 （ 下料問題） 某工廠要做 100套鋼架，每套用長為 m, m, m的圓鋼各一根。已知原料每根長 m，問：應(yīng)如何下料，可使所用原料最省？ 例 1 （ 下料問題） 某工廠要做 100套鋼架，每套用長為 m, m, m的圓鋼各一根。已知原料每根長 m，問：應(yīng)如何下料，可使所用原料最?。? 方案 余料 m m 2 0 1 Ⅰ 1 2 0 Ⅱ 1 1 1 Ⅲ 1 0 3 0 Ⅳ 0 3 0 Ⅴ 0 2 2 Ⅵ 0 1 3 Ⅶ 0 0 4 Ⅷ 50 10 30 2x1 + x2 + x3 + x4 ≥ 100 2x2 + x3 + 3x5 + 2x6 + x7 ≥ 100 x1 + x3+ 3x4 + 2x6 + 3x7 + 4x8 ≥ 100 x1, x2, x3, x4, x5, x6, x7, x8 ≥ 0 設(shè) x1,x2,x3,x4,x5,x6,x7,x8 分別為上述 8種方案下料的原材料根數(shù)， 建立如下的 LP模型： 最優(yōu)解為： x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0 min Z =x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 ?????. 余料 方案 2 0 1 Ⅰ 1 2 0 Ⅱ 1 1 1 Ⅲ 1 0 3 0 Ⅳ 0 3 0 Ⅴ 0 2 2 Ⅵ 0 1 3 Ⅶ 0 0 4 Ⅷ 第二節(jié) 單純形法 單純形法是求解線性規(guī)劃的主要算法， 1947 年由美國斯坦福大學(xué)教授丹捷格（ ） 提出。 盡管在其后的幾十年中，又有一些算法問世， 但單純形法以其簡單實用的特色始終保持著絕對 的“市場”占有率。 用單純形法求解線性規(guī)劃的前提是先將模 型化為標準型： ??????0..XbAXtsCXM a x z 標準型的特征： Max型、等式約束、非負約束 一、單純形法的預(yù)備知識 。）（的秩為其中， 0, ??? bnmmA非標準形式如何化為標準 1) Min型化為 Max型 CXM i n z ? CXMa x z ??/加負號 因為，求一個函數(shù) 的極小點，等價于求該 函數(shù)的負函數(shù)的極大點。 )(xf)(xf?*x注意： Min型化為 Max型求解后，最優(yōu)解不變，但最優(yōu)值差負號。 2) 不等式約束化為等式約束 分析： 以例 1中煤的約束為例 36049 21 ?? xx之所以“不等”是因為左右兩邊有一個差額，稱為“松 弛量”，若在左邊加上這個松弛量，則化為等式。而這 個松弛量也是變量，記為 X3 ，則有 36049 321 ??? xxxX3稱為松弛變量。問題： 它的實際意義是什么？ —— 煤資源的“剩余”。 練習(xí)：請將例 1的約束化為標準型 ??????????????0,3001032022436049..21212121xxxxxxxxts解：增加松弛變量 則約束化為 ,543 xxx?????????????????0,300 10320224360 49..54321521421321xxxxxxxxxxxxxxts易見，增加的松弛變量的系數(shù)恰構(gòu)成一個單位陣 I。 一般地，記松弛變量的向量為 Xs，則 ?????0.. XbAXts??????0,.. ssXXbIXAXts?????0.. XbAXts??????0,.. ssXXbIXAXts問題：松弛變量在目標中的系數(shù)為何？ —— 0。 3) 當模型中有某變量 xk 沒有非負要求， 稱 為自由變量 , 則可令 0, ////// ???kkkkk xxxxx化為標準型。 復(fù)習(xí)：非齊次線性方程組解 例：解非齊次線性方程組 ?????????????5242615552142132xxxxxxxx增廣矩陣 （ 1） ???????????51001124010261500150A1x 2x 3x 4x 5x b若線性方程組沒有現(xiàn)成的基，可利用增廣矩陣的 行初等變換 法 找到一組基。 為基變量。 稱 ,3x ,4x 5x其變量個數(shù) = 3)()( ?? ArAr此方程組的解為 ?????????????2152142352624515xxxxxxxx其中 ,1x 2x 為任意實數(shù)。 為非基變量，或自由變量。 2x,1x稱 稱非基變量 ,1x 2x 為 0的解（ 15， 24， 5， 0， 0）叫 基解 。 TX )5,24,15,0,0(0 ?若對（ 1）式中的變量再加上非負限制 ?????????????2152142352624515xxxxxxxx?????????????????5,105242615552142132?ixxxxxxxxxi其解為 ?????????????????5,105262451521521423?ixxxxxxxxxi由 的非負性知： ,3x ,4x 5x（ 2） 0 4 531x2x????????????????????5,100502624051521521423?ixxxxxxxxxi0515 2 ?? x505 21 ??? xx02624 21 ??? xx從而 ,1x 2x 解域為 注意：此時的 ,1x 2x已經(jīng)不是 任意 實數(shù)。 不是 自由 變量了。 而對于帶有非負約束的方程組 解的每個分量都是非負數(shù)，就叫做 可行解 。 如果基解是可行的，就叫 基可行解 。 基可行解所對應(yīng)的基稱為 可行基 。 非基 可 行 最優(yōu)基 基 非 可 行 基 四種形式的基之間的關(guān)系為： 基與解的對應(yīng)關(guān)系： 非可行解 可 行 基本 解 可行解 基本解 解與解之間的關(guān)系為： 基解 基 可行基 基可行解 最優(yōu)基 基最優(yōu)解 ????????????????????5,100502624051521521423?ixxxxxxxxxi,11 ?x 22 ?x 所對應(yīng)的解 例如 T)2,14,10,2,1(是可行解。 ,01 ?x 02 ?x 所對應(yīng)的解 T)5,24,15,0,0( 是基解。 也是可行解，故而是基本可行解。 （ 1）可行解與最優(yōu)解 ；的解，記為可行解：滿足全體約束 X。，有解則對任可行的，記為最優(yōu)解：可行解中最優(yōu)* ,CXCXXX??直觀上， 可行解是可行域中的點，是一個可行的方案； 最優(yōu)解是可行域的角點，是一個最優(yōu)的方案。 （ 2）基矩陣不基變量 基矩陣 (簡稱基 )： 系數(shù)陣 A中的 m階可逆子陣，記 為 B；其余部分稱為非基矩陣，記為 N。 基向量： 基 B中的列；其余稱非基向量。 基變量： 與基向量 Pj對