1、Chapter1 線性規(guī)劃 (Linear Programming )線性規(guī)劃問題及其模型線性規(guī)劃問題幾何意義單純形法單純形法計算步驟單純形法進(jìn)一步討論應(yīng)用舉例掌握Excel軟件求解線性規(guī)劃本章主要內(nèi)容：線性規(guī)劃是運籌學(xué)的一個重要分支，是研究較早、理論較完善、應(yīng)用最廣泛的一個學(xué)科。由前蘇聯(lián)經(jīng)濟學(xué)家康托洛維奇于1939年提出，而此人也因此獲得1960年的諾貝爾經(jīng)濟學(xué)獎。1947年，G.B.Dantzig （丹捷格）提出求線性規(guī)劃的單純形法，理論上趨向成熟，實際上的應(yīng)用也越來越廣泛。因此，線性規(guī)劃是求一組變量的值，使它滿足一組線性式子，并使一個線性函數(shù)的值最大（或最?。┑臄?shù)學(xué)方法。 線性規(guī)劃不僅僅

2、是一種數(shù)學(xué)理論和方法，而且已成為現(xiàn)代管理工作中幫助管理者做出科學(xué)決策的重要手段。線性規(guī)劃所研究的問題主要包括兩個方面： 一是在一項任務(wù)確定后，如何以最低成本（如人力、物力、 資金和時間等）去完成這一任務(wù)；二是如何在現(xiàn)有資源條件下進(jìn)行組織和安排，以產(chǎn)生最大收益。第一章 線性規(guī)劃1 線性規(guī)劃問題及其模型2 線性規(guī)劃問題幾何意義3 單純形法4 單純形法計算步驟5 單純形法進(jìn)一步討論6 應(yīng)用舉例1.1 問題的提出在生產(chǎn)管理和經(jīng)營活動中經(jīng)常需要解決：如何合理地利用有限的資源，以得到最大的效益。我們先通過幾個實際問題來認(rèn)識什么是線性規(guī)劃。1.1 問題的提出【例1】 某企業(yè)生產(chǎn) A1, A2, A3三種產(chǎn)品

3、，這些產(chǎn)品分別需要甲、乙兩種原料。生產(chǎn)每種產(chǎn)品一噸所需原料和每天原料總限量及每噸不同產(chǎn)品可獲利潤情況如表1.1所示。 （生產(chǎn)計劃問題） 利潤最大化問題試問：該企業(yè)怎樣安排生產(chǎn)才會使每天的利潤最大？表1.1 企業(yè)生產(chǎn)數(shù)據(jù)表1.1 問題的提出解 設(shè)該企業(yè)每天生產(chǎn)產(chǎn)品 的數(shù)量分別為 （單位：噸），則總利潤的表達(dá)式為我們希望在現(xiàn)有資源條件下總利潤最大.現(xiàn)有資源的限制為（原料甲的限制） （原料乙的限制） 此外，由于未知數(shù)（我們稱之為決策變量） 是計劃產(chǎn)量，應(yīng)有為非負(fù)的限制，即 1.1 問題的提出由此得到問題的數(shù)學(xué)模型為其中s.t.為英文“subject to”的縮寫，表示決策變量xj(j=1,2,3)

4、受它后面的條件約束. 1.1 問題的提出決策變量：需決策的量，即待求的未知數(shù)；目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決策變量的表達(dá)式表示；約束條件：為實現(xiàn)優(yōu)化目標(biāo)需受到的限制，用決策變量的等式或不等式表示。線性規(guī)劃模型的三要素1.1 問題的提出練習(xí)1 某企業(yè)要在計劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，這個企業(yè)現(xiàn)有的生產(chǎn)資料是：設(shè)備18臺時，原材料A 4噸，原材料B12噸；已知單位產(chǎn)品所需消耗生產(chǎn)資料及利潤如下表。問應(yīng)如何確定生產(chǎn)計劃使企業(yè)獲利最多。 產(chǎn)品資源甲乙資源量設(shè)備/機時3218原料A/噸104原料B/噸0212單位贏利/萬元351.1 問題的提出成本最小化問題【例2】 某鋼鐵廠熔煉一種新型不銹

5、鋼，需要4種合金T1T2T3T4為原料經(jīng)測定這4種原料關(guān)于元素鉻（Cr）、錳（Mn）和鎳（Ni）的質(zhì)量分?jǐn)?shù)（%）、單價以及這種新型不銹鋼所需鉻、錳和鎳的最低質(zhì)量分?jǐn)?shù)，情況如表1.2所示. 假設(shè)熔煉時質(zhì)量沒有損耗，問：要熔煉100噸這樣的不銹鋼，應(yīng)選用原料T1T2T3T4各多少噸，能夠使成本最小？1.1 問題的提出 表1.2 生產(chǎn)某種不銹鋼的相關(guān)數(shù)據(jù)表1.1 問題的提出 解: 設(shè)選用原料T1、T2、T3、T4 的量分別為x1、x2、x3、x4 （單位：噸）.由于追求的目標(biāo)是成本最小，故有最小成本 表達(dá)式：又因該不銹鋼所需鉻、錳和鎳的最低質(zhì)量分?jǐn)?shù)是由4種合金T1、T2、T3、T4 對相應(yīng)元素的質(zhì)量

6、分?jǐn)?shù)構(gòu)成，注意到要熔煉該種不銹鋼100噸，于是得到鉻、錳和鎳的質(zhì)量分?jǐn)?shù)滿足的不等式依次為以下分析約束條件。由于假設(shè)熔煉時質(zhì)量沒有損耗，熔煉該種不銹鋼100噸，它由原料T1、T2、T3、T4 熔煉而成，故有等式約束1.1 問題的提出此外，各種合金的加入量以整噸為單位，即有限制x1、x2、x3、x40 且為整數(shù)。綜合上述討論，我們得到該問題的數(shù)學(xué)模型為這類問題也稱為混合配料問題。1.1 問題的提出運輸問題【例3】某建材公司有三個水泥廠 ，四個銷地 ，其產(chǎn)量、銷量、運費見表1.3.1.3如何制定調(diào)運方案，使總的運費或總貨運量最小？1.1 問題的提出 解 設(shè)由水泥廠Ai 運到銷地Bj 的貨運量 為xi

7、j(i=1,2,3; j=1,2,3,4)，則得到問題的數(shù)學(xué)模型為1.1 問題的提出【例4】設(shè)某單位現(xiàn)有 n 個人員A1 , A2 , An 來完成n項工作B1 , B2 , , Bn。按工作要求，每個人員需干一項工作，每項工作也需一人去完成。已知人員Ai 做工作Bj 的效率是cij。問應(yīng)如何分配，才使總效率最好。在本例中決策變量： x ij 表示分配人員Ai 完成工作 Bj x ij = 1 表示分配 Ai 干工作 Bj xij = 0 表示不分配 Ai干工作 Bj人員分配問題1.1 問題的提出對工作Bj ；要求一人員去完成：對人員Ai ；要求承擔(dān)一項工作：派工方案的總效益按問題要求，每人要

8、做一項工作，每項工作需一人去做。建立該問題的數(shù)學(xué)模型的過程：1.1 問題的提出分配問題的數(shù)學(xué)模型1.1 問題的提出從前面對實際問題建立數(shù)學(xué)模型的過程，可以得到一般線性規(guī)劃問題建模過程如下： 第1步 理解要解決的問題； 第2步 定義決策變量； 第3步 確定約束條件； 第4步 列出目標(biāo)函數(shù)。1.1 問題的提出共同表現(xiàn)： 線性規(guī)劃的數(shù)學(xué)模型1.1 問題的提出1.2 線性規(guī)劃問題的圖解法圖解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個變量）的問題，但其主要作用并不在于求解，而是在于能夠直觀地說明線性規(guī)劃解的一些重要性質(zhì)。圖解法的步驟可概括為：在平面上建立直角坐標(biāo)系；圖示約束條件，

9、找出可行域；圖示目標(biāo)函數(shù)和尋找最優(yōu)解。1.2 線性規(guī)劃問題的圖解法先做約束的圖形 先做非負(fù)約束的圖形；再做資源約束的圖形。 以練習(xí)1為例， 其約束為0 2 4 6 8 x1x2 8 6 4 2 0 x1=42 x2 = 123x1+2x2=18可行域QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)1.2 線性規(guī)劃問題的圖解法函數(shù)任給二不同的值，便可做出相應(yīng)的二直線，用虛線表示。例1中，其目標(biāo)為z=3x1+5x2，分別令z=20和z=36，做出相應(yīng)的二直線，便可看出增大的方向。再做目標(biāo)圖形0 2 4 6 8 x1x2 8 6 4 2 0可行域QQ0(0,0)Q1(0,6)

10、Q2(2,6)Q3(4,3)Q4(4,0)3x1+5x2= z =363x1+5x2= z =203x1+5x2= z =01.2 線性規(guī)劃問題的圖解法 求出最優(yōu)解將目標(biāo)直線向使目標(biāo)z優(yōu)化的方向移動，直至可行域的邊界為止，這時其與可行域的“切”點X*即最優(yōu)解。0 2 4 6 8 x1x2 8 6 4 2 0Q2(2,6)3x1+5x2= z =36練習(xí)1中， X*是可行域的一個角點。X*1.2 線性規(guī)劃問題的圖解法注：本問題只有唯一最優(yōu)解讓直線束 3x1+5x2=z 沿正法線在可行域Q移動，通過點（2，6）的直線1.2 線性規(guī)劃問題的圖解法求解A的坐標(biāo)，從而得到最優(yōu)解 ，最大值練習(xí)1 用圖解法

11、求解線性規(guī)劃問題解 ：-x1+x2=0 x1+x2=56x1+2x2=213x1 + x2 = z =03x1 + x2 = z =63x1 + x2 = z =21/2A(11/4, 9/4)B(21/6,0)x1x21.2 線性規(guī)劃問題的圖解法練習(xí)2注：本問題有無窮多個最優(yōu)解。解：該問題的可行域是一個無界的凸多邊形。1.2 線性規(guī)劃問題的圖解法練習(xí)3讓直線束-2x1 + x2 = z 沿其負(fù)法線方向移動，可以無限制地移動下去，一直與相交 ，所以其最小值為- ；即函數(shù)z=-2x1 + x2 在 上無下界。注：本問題有可行解，但無最優(yōu)解，稱為無界解.解x1-x2=-1x1+x2=-1注：本問題

12、無可行解，更無最優(yōu)解。 該問題的可行域是空的，即無可行解。1.2 線性規(guī)劃問題的圖解法練習(xí)4 作圖的關(guān)鍵有三點 (1)可行解區(qū)域要畫正確 (2)目標(biāo)函數(shù)增加的方向不能畫錯 (3)目標(biāo)函數(shù)的直線平行移動方向1.2 線性規(guī)劃問題的圖解法思考線性規(guī)劃的可行域是一個什么形狀？多邊形，而且是“凸”形的多邊形。最優(yōu)解在什么位置獲得？在邊界，而且是在某個頂點獲得。線性規(guī)劃的可行域是一個什么形狀？1.2 線性規(guī)劃問題的圖解法凸集中的“極點”，又稱頂點或角點，是指它屬于凸集，但不能表示成集中某二點連線的內(nèi)點。如多邊形的頂點。由圖解法得到線性規(guī)劃解的一些特性凸多面體是凸集的一種。所謂凸集是指：集中任兩點的連線仍屬

13、此集。（1）線性規(guī)劃的約束集（即可行域）是一個凸邊形（多面體）。1.2 線性規(guī)劃問題的圖解法（2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的頂點獲得 因為，由圖解法可知，只有當(dāng)目標(biāo)直線平移到邊界時，才能使目標(biāo)z 達(dá)到最大限度的優(yōu)化。問題：本性質(zhì)有何重要意義？1.2 線性規(guī)劃問題的圖解法（3）線性規(guī)劃解的幾種情形1）唯一解 2）多重最優(yōu)解注：出現(xiàn)3）、4）情況時，建模有問題3）無可行解 4）無有限最優(yōu)解這也是一般線性規(guī)劃問題的類似結(jié)論。1.2 線性規(guī)劃問題的圖解法線性規(guī)劃問題的一般數(shù)學(xué)模型1.3 線性規(guī)劃的標(biāo)準(zhǔn)型1.3 線性規(guī)劃的標(biāo)準(zhǔn)型方程組（1.2）中不含有多余的方程（一般mn）bi0(i=

14、1,m)解決一般線性規(guī)劃問題的第一步：標(biāo)準(zhǔn)形的轉(zhuǎn)換標(biāo)準(zhǔn)型的特征：Max型、等式約束、非負(fù)約束1.3 線性規(guī)劃的標(biāo)準(zhǔn)型只需令 , 再求 的最大值線性規(guī)劃問題的一般型如何化為標(biāo)準(zhǔn)型？（1）如果目標(biāo)函數(shù)求極小，則1.3 線性規(guī)劃的標(biāo)準(zhǔn)型（2）若約束關(guān)系是不等式，引入松弛變量(slack variables) , 把不等式改成等式。（3）若變量不滿足“0”，決策變量的標(biāo)準(zhǔn)化（4）當(dāng)bi0，約束常數(shù)的標(biāo)準(zhǔn)化約束方程兩邊同乘 -1 將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。解：先引入三個松弛變量x3、x4、x5在每個約束不等式中分別加上松弛變量使不等式化為等式，3x1+2x2 183x1+2x2+x3 =18+x3x1

15、4x1 +x4 =4+x4 2x2 12 2x2 +x5=12+x51.3 線性規(guī)劃的標(biāo)準(zhǔn)型【例5】得到標(biāo)準(zhǔn)形：注：加入的松弛變量x3、x4、x5可以看成沒有被利用的資源，當(dāng)然不會產(chǎn)生利潤，故在目標(biāo)函數(shù)中的系數(shù)應(yīng)為0。此時，z 仍可簡寫為 松弛變量在目標(biāo)函數(shù)中的系數(shù)是什么？1.3 線性規(guī)劃的標(biāo)準(zhǔn)型從而，該問題的標(biāo)準(zhǔn)型為： 將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。1.3 線性規(guī)劃的標(biāo)準(zhǔn)型【例6】1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃問題標(biāo)準(zhǔn)形的矩陣表示：A為系數(shù)矩陣；b是資源向量，C是價值向量，X為決策變量向量.記則矩陣表示為：1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃問題標(biāo)準(zhǔn)形的向量表示:目標(biāo)函數(shù) z = CX 可寫成：此

16、時約束方程AX=b 可寫成：則向量表示為：若令z = c1 x1 + c2 x2 + + cn xnP1x1 + P2 x2 + + Pn xn = bmax z = c1 x1 + c2 x2 + + cn xns.t. P1x1 + P2x2 + + Pn xn = b x j 0, j = 1 , 2 , , n1.3 線性規(guī)劃的標(biāo)準(zhǔn)型1.4 線性規(guī)劃問題解的概念給定一個線性規(guī)劃問題LP：1.4 線性規(guī)劃問題解的概念所有可行解的集合稱為可行域 (feasible region),記為使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解(an optimal solution)。可行域可行解Q2(2,6

17、)(1)可行解 (a feasible solution) 滿足約束條件的 X 稱為線性規(guī)劃問題的可行解;直觀上，可行解是可行域中的點，是一個可行的方案；最優(yōu)解是可行域的頂點，是一個最優(yōu)的方案。1.4 線性規(guī)劃問題解的概念即是 A 的任意 m 個列向量, r(A)=m設(shè)是線性無關(guān)的，如果構(gòu)成線性規(guī)劃問題的一個基(base)。則稱對應(yīng)的變量稱為基變量。其余的變量稱為非基變量(non-basic-variable)。稱為基陣。矩陣（2）基矩陣與基變量記約束方程系數(shù)矩陣A的列向量是1.4 線性規(guī)劃問題解的概念行列式0基陣=目標(biāo)函數(shù)約束條件右邊常量基矩陣所對應(yīng)的變量為基變量1.4 線性規(guī)劃問題解的概念

18、 列出基變量、非基變量等各項參數(shù).解：約束方程A的系數(shù)矩陣為：1.4 線性規(guī)劃問題解的概念【例7】向量組P2P4P5是線性無關(guān)組x2 x4 x5可構(gòu)成此問題的一個基；B2=(P2 P4 P5)是相應(yīng)的基陣x2 x4 x5稱為基變量，而x1 x3是非基變量.向量組P3P4P5 是線性無關(guān)組x3 x4 x5可構(gòu)成此問題的一個基；B1=(P3 P4 P5)是相應(yīng)的基陣稱x3 x4 x5為基變量，而x1 x2是非基變量。1.4 線性規(guī)劃問題解的概念（2）設(shè)B是A的一個 m 階子矩陣，則B是線性規(guī)劃問題的基陣，當(dāng)且僅當(dāng)B是可逆陣（3）基的個數(shù)（1）基不一定唯一.注：1.4 線性規(guī)劃問題解的概念P1x1

19、+ P2x2 + + Pn xn = b （3）基本解與基本可行解1.4 線性規(guī)劃問題解的概念至少含有 n-m 個0元可見：一個基本解是由一個基決定的。注意：基本解僅是資源約束的解，并未要求其非負(fù)，因此其未必可行。非負(fù)的基本解為基本可行解（簡稱基可行解）。1.4 線性規(guī)劃問題解的概念B1=(P3P4P5)為基陣x3 x4 x5為基變量得到的基可行解(0,0,18,4,12。一個基對應(yīng)一個基解在上例7中，B2=(P2P4P5)為基陣x2 x4 x5為基變量得到基解(0,9,0,4,-6),但不是基可行解。1.4 線性規(guī)劃問題解的概念上二組概念間的聯(lián)系：系數(shù)陣A中可找出若干個基B每個基B都對應(yīng)于一

20、個基本解非負(fù)的基本解就是基本可行解幾種解之間的關(guān)系：非可行解可行解基 解基可行解解空間問題：基本可行解是可行域中的哪些點？基可行解的數(shù)目是有限個，不會超過1.4 線性規(guī)劃問題解的概念第一章 線性規(guī)劃1 線性規(guī)劃問題及其模型2 線性規(guī)劃問題幾何意義3 單純形法4 單純形法計算步驟5 單純形法進(jìn)一步討論6 應(yīng)用舉例本節(jié)學(xué)習(xí)要點：1、了解線性規(guī)劃問題可行域的特征；2、了解基可行解的性質(zhì)和幾何特征。在上一節(jié)中：maxz=3x1+5x2二維：線性規(guī)劃的可行域的形狀； 最優(yōu)解獲得的位置。n維？可行域的頂點與基可行解的關(guān)系？設(shè)如果存在 k 個實數(shù)使得則稱 。2.1 凸組合、凸集與頂點凸組合一般地，在Rn 中，給定 k+1 個頂點 如果 線性無關(guān)，則稱 的凸組合是Rn中的一個 k 維單純形，簡稱單形（simplex）。單純形2.1凸組合、凸集與頂點設(shè) ，如果K中任意兩點間的連線仍屬于K，即對于任意 及 0，1， 成立, 則稱K