1、第一 章 線性規(guī)劃,1 線性規(guī)劃問題及其模型,2 線性規(guī)劃問題幾何意義,3 單純形法,4 單純形法計算步驟,5 單純形法進(jìn)一步討論,6 應(yīng)用舉例,線性規(guī)劃（LP）簡介,線性規(guī)劃是運籌學(xué)的一個重要分支。由前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇于1939年提出，而此人也因此獲得1975年的諾貝爾經(jīng)濟(jì)學(xué)獎。,線性規(guī)劃是一類特殊的最優(yōu)化問題，它是針對一類有限資源如何合理利用這樣的問題而提出的。,1947年 G.B.Dantzig 提出求線性規(guī)劃的單純形法（simple method），理論上趨向成熟，實際上的應(yīng)用也越來越廣泛。,例1 生產(chǎn)計劃問題 某企業(yè)要在計劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，這個企業(yè)現(xiàn)有的生產(chǎn)資料是：

2、設(shè)備18臺時，原材料A 4噸，原材料 B 12噸；已知單位產(chǎn)品所需消耗生產(chǎn)資料及利潤如表1。 問應(yīng)如何確定生產(chǎn)計劃使企業(yè)獲利最多。,1 線性規(guī)劃問題及其數(shù)學(xué)模型,1.1 問題的提出,首先明確要我們決策什么確定產(chǎn)品甲、乙的生產(chǎn)量。 為了定量分析解決這個問題，首先應(yīng)建立其數(shù)學(xué)模型。 設(shè) x1 、x2 分別表示甲、乙兩種產(chǎn)品的產(chǎn)量，稱為決策變量. 用一組決策變量(x1 ,x2)表示一個方案，變量的不同取值表示不同的方案。（目標(biāo)：找尋最優(yōu)方案。） 其次分析 x1、x2 應(yīng)滿足什么條件，才能使生產(chǎn)正常進(jìn)行。由于現(xiàn)有的生產(chǎn)資料總量是有限的.因此， 正常生產(chǎn)過程中生產(chǎn)資料消耗不能超過現(xiàn)有量.,問題分析,問題

3、分析,現(xiàn)在的問題是找出 x1 、x2 ，在上述各種條件限制下，使 Z 達(dá)到最大值。,x1 、x2應(yīng)同時滿足下列條件：,設(shè)備臺時限制,原材料A限制,原材料B限制,由于產(chǎn)品產(chǎn)量不能是負(fù)的，故有非負(fù)限制：,該生產(chǎn)計劃的總利潤為：,綜上所述，該生產(chǎn)計劃問題的數(shù)學(xué)模型為：,資源的合理利用問題 一般的資源利用問題可表述為： 設(shè)某企業(yè)利用 m 種資源來生產(chǎn) n 種產(chǎn)品，已知該企業(yè)擁有的第 i 種資源的數(shù)量是b i , 生產(chǎn)單位第 j 種產(chǎn)品所消耗的第 i 種資源的數(shù)量為 aij ，第 j 種產(chǎn)品的單位利潤 cj ?，F(xiàn)制定一個生產(chǎn)計劃方案，使總利潤最大。,注：常用術(shù)語 aij ： 技術(shù)系數(shù) b i ： 資源系

4、數(shù) c j ：價值系數(shù) 用 x j 表示第 j 種產(chǎn)品的生產(chǎn)量。,一般資源利用問題的數(shù)學(xué)模型為：,例2 （人員分配問題）,設(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 按問題要求，每人要做一項工作，每項工作需一人去做。 建立該問題的數(shù)學(xué)模型的過程：,對工作Bj ；

5、要求一人員去完成,對人員Ai ；要求承擔(dān)一項工作：,派工方案的總效益,分配問題的數(shù)學(xué)模型,某公司要運銷一種物資。該物資有甲、乙兩個產(chǎn)地，產(chǎn)量分別是2000噸、1000噸；另有A、B、C三個銷地，銷量分別是1700噸、1100噸、200噸。已知該物資的單位運價如下表。問應(yīng)如何確定調(diào)運方案，才能使在產(chǎn)銷平衡的條件下，總運費最低？,例2 （物資運輸問題）,確定調(diào)運方案就是確定從不同產(chǎn)地到各個銷地的運輸量。,問題分析,假設(shè)：,從兩產(chǎn)地甲、乙分別調(diào)往三銷地A、B、C的物資數(shù)量應(yīng)該分別等于兩產(chǎn)地甲、乙的產(chǎn)量,所以 xij 應(yīng)滿足：,由于要求產(chǎn)銷平衡：,運到A、B、C三銷地的物資數(shù)量應(yīng)分別等于A、B、C三銷

6、地的銷量，所以xij 還應(yīng)該滿足：,顯然：,調(diào)運方案的總運費為：,建立產(chǎn)銷平衡下運費最省的調(diào)運問題的數(shù)學(xué)模型：,(1) 變量，或稱決策變量，是問題中要確定的未知量，它用以表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制； (2)目標(biāo)函數(shù)，它是決策變量的函數(shù)，按優(yōu)化目標(biāo)分別在這個函數(shù)前加上max或min； (3)約束條件，指決策變量取值時受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式。,上述例子表明規(guī)劃問題的數(shù)學(xué)模型由三個要素組成：,如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值可以是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)

7、學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。,線性規(guī)劃問題的一般數(shù)學(xué)模型,1.2 圖解法,圖解法適用于求解只有兩個變量的線性規(guī)劃問題.,圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理和思想。,下面舉例說明圖解法求解線性規(guī)劃問題的步驟。,一、圖解法的步驟,圖解法的步驟可概括為：在平面上建立直角坐標(biāo)系；圖示約束條件，找出可行域；圖示目標(biāo)函數(shù)和尋找最優(yōu)解。,可行域Q,3x1+5x2= z =36,3x1+5x2= z =20,3x1+5x2= z =0,圖解法解題過程,圖1-1,本問題只有唯一最優(yōu)解,讓直線束 沿正法線 在可行域Q移動，通過點 的直線：,就是所求的直線，從而 。,例1的最優(yōu)生產(chǎn)方案為： 生產(chǎn)

8、產(chǎn)品甲為2件， 生產(chǎn)產(chǎn)品乙6件，最大利潤為36萬元。,注：本問題只有唯一最優(yōu)解,例2,解 ：,-x1+x2=0,x1+x2=5,6x1+2x2=21,3x1 + x2 = z =0,3x1 + x2 = z =6,3x1 + x2 = z =21/2,A(11/4, 9/4),B(21/6,0),本問題有無窮多個最優(yōu)解。,讓直線束 3x1 + x2 = z 沿正法線向移動， 到達(dá)線段AB時，使 Z 達(dá)到最大。 所以線段 AB上的每一點都可使Z達(dá)到最大值，,注：本問題有無窮多個最優(yōu)解。,例3,解：,該問題的可行域是一個無界的凸多邊形。,注：本問題有可行解，但無最優(yōu)解，稱為無界解.,讓直線束 沿其

9、負(fù)法線方向 移動，可以無限制地移動下去，一直與 相交，所以其最小值為 ； 即函數(shù) 在 上無下界。,注：本問題有可行解，但無最優(yōu)解，稱為無界解.,例4,解,x1-x2=-1,x1+x2=-1,注：本問題無可行解，更無最優(yōu)解。,該問題的可行域是空的，即無可行解.,給定只有兩個變量的線性規(guī)劃問題：,圖解法求解線性規(guī)劃問題的步驟如下：,進(jìn)一步討論,若 是空集，則說明線性規(guī)劃問題無可行解。,如果 不是空集，那么 是平面上的一個凸多邊形，這個凸多邊形可能是有界的（封閉的），也可能是無界的（不封閉的）。,表示一個以 z 為參數(shù)的平行直線束。,沿正法線方向 移動可得最大值， 沿負(fù)法線方向 移動可得最小值。,注

10、意:一定要精確！,在平面 上取定直角坐標(biāo)系，畫出可行域，記為 。, 有唯一的最優(yōu)解。 最優(yōu)解是可行域的一個頂點。 有無窮多的最優(yōu)解。 最優(yōu)解是可行域的一段邊界。 無界解(有可行解,但無最優(yōu)解)。產(chǎn)生無界解的原因是在建立實際問題的數(shù)學(xué)模型時遺漏了某些必要的約束條件。 無可行解。產(chǎn)生原因是模型的約束條件之間存在矛盾，建模時有錯誤.,一般線性規(guī)劃問題也有類似結(jié)論，但結(jié)論成立的判定準(zhǔn)則如何？,二、線性規(guī)劃問題求解的幾種可能結(jié)局：,圖解法的解題思路和幾何上直觀得到的一些概念判斷,對后面的求解一般線性規(guī)劃問題的單純形法有很大啟示：,1.解的情況有：唯一最優(yōu)解,無窮多最優(yōu)解,無界解,無可行解； 2.若線性規(guī)

11、劃問題的可行域存在，則可行域是一個凸集； 3.若線性規(guī)劃問題的最優(yōu)解存在,則最優(yōu)解或最優(yōu)解之一是可行域的凸集的某個頂點； 4.解題思路是：先找出凸集的任一頂點,計算在頂點處的目標(biāo)函數(shù)值.比較周圍相鄰頂點的目標(biāo)函數(shù)值是否比這個值大,如果為否,則該頂點就是最優(yōu)解的點或最優(yōu)解的點之一,否則轉(zhuǎn)到比這個點的目標(biāo)函數(shù)值更大的另一頂點,重復(fù)上述過程。一直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點為止。,三、圖解法的啟示,最大值點（最小值點）一定在可行域的邊界上！,已知線性規(guī)劃問題，試用圖解法分析，問題最優(yōu)解隨 c（- c )變化的情況。,練習(xí),線性規(guī)劃問題的一般數(shù)學(xué)模型,1.3 線性規(guī)劃的標(biāo)準(zhǔn)型,目標(biāo)函數(shù)可為最小值，

12、也可為最大值。 約束條件可以是線性方程組，也可以是線性不等式組。 有的變量可以是無約束的。, 為討論方便，用統(tǒng)一的形式 標(biāo)準(zhǔn)形。,一般線性規(guī)劃問題的特點：,標(biāo)準(zhǔn)形,1、方程組（1.2）中不含有多余的方程,2、,解決一般線性規(guī)劃問題的第一步：標(biāo)準(zhǔn)形的轉(zhuǎn)換,若目標(biāo)函數(shù)為最小值,將線性規(guī)劃模型化為標(biāo)準(zhǔn)型的主要步驟：,只需令 , 再求 的最大值,若約束關(guān)系是不等式，引入松弛變量(slack variables) ,把不等式改成等式。,當(dāng)約束條件是“”不等式，在“”不等式的左端減去一個非負(fù)松弛變量，把“”不等式變?yōu)榈仁健?當(dāng)約束條件是“”不等式時，在“”不等式左端加入非負(fù)松弛變量， 把原“”不等式變?yōu)榈?/p>

13、式;,若變量不滿足“0”。,注：任意實數(shù)都可以表示為兩個非負(fù)實數(shù)的差，如1=3-2=8-7；-1=0-1=10-11,則在約束方程兩邊同乘 -1。,當(dāng),例1 將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。,例1 將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。,3x1+2x2 18,3x1+2x2+x3 =18,x1 4,x1 +x4 =4,2x2 12,2x2 +x5=12,得到標(biāo)準(zhǔn)形：,解: 在第一個約束方程兩端同乘 -1； 令 ，其中 在第二個約束不等式左端加上松弛變量 ； 在第三個約束不等式左端減去松弛變量 ； 令 ；化 為 。,從而，該問題的標(biāo)準(zhǔn)型為：,例2 將下列線性規(guī)劃化成標(biāo)準(zhǔn)形。,標(biāo)準(zhǔn)型為：,線性規(guī)劃問題標(biāo)準(zhǔn)形的 矩陣

14、表示：,A為系數(shù)矩陣； b是資源向量， C是價值向量， X為決策變量向量.,記,則矩陣表示為：,線性規(guī)劃問題標(biāo)準(zhǔn)形的 向量表示:,目標(biāo)函數(shù) z = CX 可寫成：,此時約束方程AX=b 可寫成：,則向量表示為：,若令,z = c1 x1 + c2 x2 + + cn xn,P1x1 + P2 x2 + + Pn xn = b,max z = c1 x1 + c2 x2 + + cn xn,s.t. P1x1 + P2x2 + + Pn xn = b x j 0, j = 1 , 2 , , n,給定一個線性規(guī)劃問題LP：,1.4 線性規(guī)劃問題解的概念,1.可行解 (a feasible sol

15、ution),滿足約束條件的 X 稱為線性規(guī)劃問題的可行解;,所有可行解的集合稱為可行域 (feasible region),記為,使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解 (an optimal solution)。,2、基(base),記約束方程系數(shù)矩陣A的列向量是,即,是 A 的任意 m 個列向量,設(shè),是線性無關(guān)的，,如果,構(gòu)成線性規(guī)劃問題的一個基(base)。,則稱,對應(yīng)的變量,稱為基變量.,其余的變量稱為非基變量(non-basic-variable).,稱為基陣.,矩陣,=,目標(biāo)函數(shù),約束條件,右邊常量,例1 列出基變量、非基變量等各項參數(shù).,約束方程A的系數(shù)矩陣為：,分別是變量,的

16、系數(shù)向量。,（2）設(shè)B是A的一個 m 階子矩陣，則B是線性規(guī)劃問題的基陣，當(dāng)且僅當(dāng)B是可逆陣,（3）基的個數(shù),（1）基不一定唯一.,注：,給定一個基,令所有非基變量都等于0，即,3.基解,基陣,記,為基變量向量.,為非基變量向量.,則約束方程(1.2)可化為：,P1x1 + P2x2 + + Pn xn = b,稱為相應(yīng)于基B的一個基解 (a basic solution)。,它是一個 m 個變量 m 個方程組成的線性方程組， B又是可逆陣，從而可得(1.4)的唯一解,令,如果,則稱 為一個基可行解.,相應(yīng)的基B也稱為可行基.,在上例1中，,且是基可行解。,但不是基可行解。,思考題：試列出例1

17、中問題的所有基解、基可行解。,注：基可行解的數(shù)目是有限個，不會超過 。,非可行解,可行解,基 解,基可行解,解之間的關(guān)系,解空間,2 線性規(guī)劃問題的幾何意義,那么，可行域具有什么特征？ 可行域的頂點與基可行解的關(guān)系？,兩個變量的線性規(guī)劃問題的可行域是一個凸多邊形，并且如果存在最優(yōu)解，則一定可以在可行域的頂點上找到。這個性質(zhì)對于 n 個變量的線性規(guī)劃問題也是成立的。,設(shè) 如果存在 k 個實數(shù) 使得 則稱 。,2.1 凸組合、凸集與頂點,例1 在 中，給定兩個a、b，ab，則a、b在 的凸組合是閉區(qū)間,a x b,x,凸組合,例2 在 中，給定兩個點 則 在 中的凸組合是以 為端點的直線段。,例3

18、 設(shè) 在 中不共線， 即 線性無關(guān)， 則 的凸組合是 中以 為頂點的閉三角形區(qū)域.,一般地，在 中，給定 k+1 個頂點 如果 線性無關(guān)， 則稱 的凸組合是 中 的一個 k 維單純形，簡稱單形（simplex）。,單純形,設(shè) ，如果 中任意兩點間的連線仍屬 于 ，即對于任意 及 0，1， 成立 則稱 是凸集。,凸 集,直觀上，凸集是沒有凹入部分，且其內(nèi)部又沒有空洞的幾何形體。,任何兩個凸集的交集是凸集。,設(shè) 是一個凸集， ，如果 不是 中 任意兩個不同點連線的中間點，即X 不是 K 中的 兩個不同點的凸組合，則稱X是K的一個頂點。,圖1-8,頂 點,例如，在圖1-8的凸多邊形K 中，僅有四個頂

19、點 。,而在一個實心圓區(qū)域內(nèi)，其邊界圓周上的每個點都是該凸集的頂點。,2.2 基可行解的性質(zhì)與幾何特征,定理1. 若 ，則 是凸集。,定理2. 如果線性規(guī)劃問題有可行解，則一定有基可行解。,定理3. 設(shè) 是一個可行解，則 是基可行解當(dāng)且僅 當(dāng) 是 的頂點。,定理4. 如果線性規(guī)劃問題有最優(yōu)解，則一定存在一個基 可行解是最優(yōu)解。,應(yīng)用上述術(shù)語，我們討論線性規(guī)劃可行域的特征。,不一定所有的基可行解都是最優(yōu)解，最優(yōu)解也不一定都是基解； 如果有兩個基可行解是最優(yōu)解，則兩解的凸組合也都是最優(yōu)解。 如果最優(yōu)解不唯一，則會有多個基本可行解是最優(yōu)解，它們必然在同一個面上。 基可行解個數(shù)有限，可以在基可行解中尋

20、找最優(yōu)解。剩余的問題是如何判斷一個基可行解是最優(yōu)解，如果不是則如何從一個基可行解轉(zhuǎn)到另一個基可行解。,說明：,定理1. 若 ，則 是凸集。,有 。,所以，可行域 是凸集。,事實上，由 的定義可知：,顯然,back,引理1.,設(shè) X 是一個可行解，則 X 是基可行解當(dāng)且僅當(dāng) X 的正分量對應(yīng)的系數(shù)列向量是線性無關(guān)的.,證明,由基可行解的定義可知必要性是成立的。,下面證明充分性。,不失一般性設(shè) X 的正分量是前 k 個分量。,引理1給出了一個可行解是否是基解的一個判別準(zhǔn)則.,back,證明 設(shè) 是任一可行解；,不妨設(shè) 的正分量是 ， 。如果相,應(yīng)的列向量 線性無關(guān)，則 是基可行解。,如果 線性相關(guān)

21、，則存在不全為0數(shù),使,令 是一個 n 維向量， 取一個充分小的 ，使,定理2 如果線性規(guī)劃問題有可行解， 則一定有基可行解.,個取等號，將得到一個可行解 等于,又,所以， 都是可行解。在滿足,的同時，適當(dāng)選取 ，使上述諸式中至少有一,或 ,它的正分量數(shù)至少比 少一個。如果,還不是基可行解，則可以仿照上述方法繼續(xù)做下去，,直到得到可行解 ，其正分量對應(yīng)的列向量線性,無關(guān)，則 就是一個基可行解。,back,定理3 設(shè) 是一個可行解，則 是 基可行解當(dāng)且僅當(dāng) 是 的頂點.,若 不是 的頂點，即存在兩個不同,使得,且,要證 是 的頂點。用反證法來證。,由于,及,所以得出,從而 式可簡化為,中兩式相減

22、得,由假設(shè) ，而上式說明了 是,線性相關(guān)的，這與 是基可行解矛盾，表,明 是 的頂點。,back,充分性 假定 是 的頂點，但不是基可行解，,不妨設(shè) 的正分量是 ，,由于 不是基解，故相應(yīng)的列向量,線性相關(guān)，即存在不全為0的一組 ，使,令 是一個 n 維向量，作,可見,定理3 設(shè) 是一個可行解，則 是 基可行解當(dāng)且僅當(dāng) 是 的頂點.,類似可以驗證,因為 ，所以能夠找,到充分小的 t ，使得,這說明 是兩個不同的解，即,這與 是 的頂點矛盾。,且,定理2,3說明：若可行域非空 , 則其必有有限個頂點.,back,定理4 如果線性規(guī)劃問題有最優(yōu)解，則一定存在 一個基可行解是最優(yōu)解.,注:定理的重要

23、性在于,它說明了尋找最優(yōu)解的一種方法,只需在有限個基可行解中尋找即可,這正是單純形方法的基礎(chǔ),證明 設(shè) 是一個最優(yōu)解，即,如果 不是基可行解，那么由定理2的證明中可得,出兩個可行解 并且,所以 ，從而 成立,由定理2可知，按照其證明方法繼續(xù)做，得到的基可 行解 也是最優(yōu)解。,back,復(fù) 習(xí),定理1. 若 ，則 是凸集。,定理2. 如果線性規(guī)劃問題有可行解，則一定有基可行解。,定理3. 設(shè) 是一個可行解，則 是基可行解當(dāng)且僅 當(dāng) 是 的頂點。,定理4. 如果線性規(guī)劃問題有最優(yōu)解，則一定存在一個基 可行解是最優(yōu)解。,先找出一個基可行解,判斷其是否為最優(yōu)解,如為否，則轉(zhuǎn)換到相鄰的基可行解,并使目標(biāo)

24、函數(shù)值不斷增大,一直找到最優(yōu)解為止.,定義：兩個基可行解稱為相鄰的，如果它們之間變換且僅變換一個基變量。,單純形法迭代的基本思路是：,3 單 純 形 法,3.1 引例：,例：,為基變量,沒有安排生產(chǎn)1、2兩種產(chǎn)品，資源沒有利用，所以利潤為零。即這個基可行解不是極點。 分析：如果將非基變量轉(zhuǎn)變成基變量，目標(biāo)函數(shù)就可能增大。 如果目標(biāo)函數(shù)中還有正系數(shù)的非基變量存在，則說明目標(biāo)函數(shù)還有增大的可能。,將正系數(shù)最大的那個非基變量換入（即該變量0）,以獲得該產(chǎn)品的最大產(chǎn)量和對應(yīng)的最大利潤。,同理：,此時的目標(biāo)函數(shù)為：,函數(shù)中的x1，仍然沒有利用，其系數(shù)仍然為正數(shù)，說明目標(biāo)還有增長的余地，該基可行解仍不是最

25、優(yōu)解，下一步將x1換入基變量中。,此時的目標(biāo)函數(shù)為：,函數(shù)中所有非基變量的系數(shù)都是負(fù)數(shù)，說明如果想要得到利潤的增加，就需要對“不存在的、沒有利用的”資源付出代價，這是不現(xiàn)實的，所以求解停止。也就是說，生產(chǎn)x1 2噸，生產(chǎn)x2 6噸，可以得到最的利潤36萬元。這個結(jié)果與前面圖解法的結(jié)果相同。,該例子是一個二維的規(guī)劃問題，但是在加入松弛變量x3 x4 x5之后就變成了高維的規(guī)劃問題。這時可以想象，滿足所有約束條件的可行域是高維空間的凸多面體，基可行解就是凸多面體上的頂點。 下面將前面所使用的方法進(jìn)行總結(jié)歸納，推導(dǎo)求解一般線性規(guī)劃問題的基本方法單純形算法。,2x2 =12,3x1+5x2=z=36,

26、Q2(2,6),3x1+2x2=18,返回,給定一個初始基可行解 ,不妨設(shè) 的基變量是,對線性規(guī)劃問題,記,，而非基變量是 ，,則基可行解可寫成,對應(yīng)的 A=(B,N)，,3.2 解的判別定理,A=(B,N)，,max,稱為基 所對應(yīng)的典式.,記 就是基可行解 的目標(biāo)函數(shù)值，,并且,現(xiàn)將典式寫成分量形式：,線性規(guī)劃典式(proper form)的分量表示：,重要！重要！,1）基可行解,注：給出基 后,由其典式可得出結(jié)論,2）其對應(yīng)目標(biāo)函數(shù)值,利用這組數(shù)來判斷 是否是最優(yōu)解.,事實上：,定理1 最優(yōu)解判定準(zhǔn)則,如果對一切 則 X 0是線性規(guī)劃問題的最優(yōu)解。,如果對一切 則 X 0是線性規(guī)劃問題的

27、唯一最優(yōu)解。,設(shè) X 0 是基可行解，則：,證明,設(shè) 是任一可行解，將其代入 X0 的典式中，可知：,由于對一切 j，,所以 是最優(yōu)解。,證明,如果對一切 則 X 0是線性規(guī)劃問題的最優(yōu)解。,現(xiàn)從 X0 出發(fā)構(gòu)造另一個基可行解X1 ,使 從而X1 也是最優(yōu)解，并且X0與 X1的任何凸組合也是最優(yōu)解，這就證明了所需結(jié)論。,證明:,具體構(gòu)造過程如下：,令,其中,是一個n維向量，-1是位于 的第 m+k 個分量。則 是一個基可行解。,而,并且 的第 個分量：,從而 的正分量數(shù)不會超過 m?，F(xiàn)證,是線性無關(guān)的，只需證明,能被 線性表示即可。,記 表示典式中與 對應(yīng)的向量，可見：,由于 ，,所以：,其中

28、,由于 上式兩端同乘矩陣B得：,即 線性表示,從而 是一個基。,從而 也是最優(yōu)的基可行解。,又,證明：設(shè) 是任一正數(shù)，作一個可行解 ：,其中 是一個n 維向量，-1是其第 m+k 個分量。,由于假設(shè)對所有 從而對于任意的 ，可,類似于的過程說明 都是可行解，并且,故該問題無最優(yōu)解。,定理2 （基可行解改進(jìn)定理）,證明 類似于定理1之的證明過程。,設(shè) 是基可行解，典式如前所示，如果, 存在一個 ；,中至少有一個正分量；, 所有的 ;則一定存在另一個基可行解 ,使, 4 單純形法計算步驟,1947年，G.B.Dantzig提出求解線性規(guī)劃的單純形法.,單純形算法的直接思想：,從一個基可行解開始，通

29、過基變換,到另一個基可行解，逐步達(dá)到最優(yōu)解的過程?；儞Q是通過迭代法實現(xiàn)的。,一、單純形算法計算步驟； 二、單純形表.,Step1 求初始基可行解。 找出一個初始基可行解X0，寫出X0相應(yīng)的典式.,4.1 單純形算法計算步驟,3）進(jìn)行基變換. 得到新的基可行解 X1及其典式，轉(zhuǎn)step 2.,Step2 最優(yōu)性檢驗。 如果所有非基變量 xj 的檢驗數(shù)都不大于0，則X0是最優(yōu)解，計 算結(jié)束；若存在某個檢驗數(shù)k0， 其所有的ik0，則線性規(guī)劃問題無最優(yōu)解，計算結(jié)束；否則轉(zhuǎn)至step 3.,Step3 進(jìn)行基變換。,1）確定換入變量. 規(guī)則,找最大的 其對應(yīng)的 xk 就是換入變量.,2）確定換出變量

30、. 規(guī)則,計算 確定 xl 是換出變量.,找初始可行解X0及可行基B,單純形法計算框圖,j 0?,寫出最優(yōu)解 與最優(yōu)值,停,是否有ik0,無界解,N,確定換出變量x l ,以kl為主元作基變換,停,N,Y,Y,基變換示例,如果存在某個 ,使 ,并且至少有一個,設(shè)基 （S 為基變量下標(biāo)集合）的典式為：,基變換公式,令,這表示xk為換入變量（成為基變量）, xl為非基變量。 得一個新基 ，其中：,設(shè)新基 的典式為：,新、舊兩基典式的基變換公式為：,1）將主元素所在 l 行除以主元素 ，既有,2）將剛計算得到的第 l 行乘上( )加到典式的第 i 行,3）,例1.利用單純形算法求解下面的線性規(guī)劃問題

31、。,解：本問題有一個明顯的可行基x3、x4、x5，它的典式為：,非基變量x1、x2的檢驗數(shù)為3、5，基可行解X0=(0,0,4,12,18)T不是最優(yōu)解，取檢驗數(shù)最大者，x2作為換入變量,再確定換出變量，由于：,故x4為換出變量，得到一個新可行基x3,x2,x5，,其典式為,由于x1的檢驗數(shù)為30，故基可行解X1=(0,6,4,0,6)T不是最優(yōu)解，讓x1為換入變量。,令,所以 x5 為換出變量，又得一個新基x3,x2,x1,讓 x1 為換入變量，,非基變量x4、x5的檢驗數(shù)是-3/2、-1，故X2=(2,6,2,0,0)T是最優(yōu)解，并且是唯一最優(yōu)解。,，其典式為：,基可行解與圖解法頂點的對應(yīng)

32、關(guān)系,圖示：,X0=(0,0,4,12,18)T,X1=(0,6,4,0,6)T,X2=(2,6,2,0,0)T,是求解線性規(guī)劃問題的一種著名算法，它是依據(jù)基可行解的性質(zhì)而設(shè)計的。 因為一個給定的線性規(guī)劃問題中基可行解的個數(shù)是有限的，只要把所有的基可行解一一檢查就可以在有限次得到最優(yōu)解或者斷定所給問題無最優(yōu)解，這種求解過程可在一個所謂單純形表中進(jìn)行，也易于編制計算程序，因而在實際問題中得到廣泛應(yīng)用。 就算法復(fù)雜性分析來講，單純形方法不是一個有效算法，即對于極端問題，它的運算次數(shù)是問題輸入大小(size)的一個指數(shù)型函數(shù)；由于這種極端問題出現(xiàn)的概率很少，因此，在處理實際工作中的問題時并不構(gòu)成多大

33、妨礙.,單純形法(simple method),4.2 單純形表,單純形表(simple tableau)是為單純形算法而設(shè)計的一種計算表，其功能類似于方程組的增廣矩陣，易于進(jìn)行基變換運算。,設(shè)可行基 的典式為：,將式(1.4)與(1.5)組成一個m+1個方程、n+1個變量的方程組為,此方程組的增廣矩陣為：,其中基變量 的系數(shù)構(gòu)成單位矩陣，z是 一個不參與基變換的變量。,可設(shè)計單純形表,表4-1單純形表,例1,解畢,注2：min問題 如果給定的線性規(guī)劃問題是要求目標(biāo)函數(shù)達(dá)到最小，可以直接用單純形計算，而不必先化成標(biāo)準(zhǔn)形中要求目標(biāo)函數(shù)的極大值。 此時，要求檢驗數(shù) 時，基可行解才是最優(yōu)解；迭代時，

34、選負(fù)檢驗數(shù)最小者作為換入變量。,注1：上面的計算過程也可以用基變換公式來實現(xiàn)。,單純形算法特別適合計算機(jī)實現(xiàn)。,思考題：編程實現(xiàn)單純形算法。,解：建立單純形表如下：,例2 求解線性規(guī)劃問題：,最優(yōu)解是 ，最優(yōu)值為 z=-11.,5 單純形法的進(jìn)一步討論,單純形法是依據(jù)可行基迭代而設(shè)計的，即從一個基可行解構(gòu)造另一個使目標(biāo)函數(shù)值更好的基可行解。如何尋找第一個基可行解(an initial basic feasible solution)呢？在解決線性規(guī)劃問題時會碰到下面一種情況：,初始基不明顯，或者松弛變量個數(shù)比約束方程個數(shù)少的情況，問題又應(yīng)該如何解決？,解決方法一： 通過初等行變換，變換出一組m

35、個線性不相關(guān)的向量來組成m階初始基矩陣。 不利于計算機(jī)編程實現(xiàn)，因為如何確定“一組m個線性不相關(guān)的向量”是很隨機(jī)的問題，手工解決比較方便，在程序上的實現(xiàn)就很困難。,解決方法二： 兩階段法和大M法(the Big M Method)。 當(dāng)約束方程的系數(shù)矩陣A不包含一個同階的單位矩陣，我們就需要引入若干非負(fù)變量，又稱為人工變量(an artificial variable),從而構(gòu)造出一個新的線性規(guī)劃問題，使其容易找出一個初始基可行解。,一、初始基的確定： 人工變量法：兩階段法、大M法.,二、單純形法計算中的幾個問題,三、單純形法小結(jié),兩階段法：假定約束方程的系數(shù)矩陣A不包含同階的單位矩陣,加入人

36、工變量,改變目標(biāo)函數(shù),目標(biāo)函數(shù)在可行域上有一個明顯的下界 所以它一定有最優(yōu)解，利用單純形法可以求解。 此為第一階段，求解后進(jìn)入第二階段。,5.1 初始基的確定：,在 中，人工變量 全是非基變量， 此時， 得到原線性規(guī)劃問題的一個可行解 將該可行解代入第二階段計算。,在 中，個別人工變量 是基變量,并且 的目標(biāo)函數(shù)值 說明原線性規(guī)劃問題沒有可行解。,在 中，個別人工變量 是基變量，若此時得 到原線性規(guī)劃問題的目標(biāo)函數(shù)值 說明基變量 xn+j=0，原線性規(guī)劃問題為退化問題。,第二階段， 以第一階段的結(jié)論作為原線性規(guī)劃問題的初始基可行解計算。如果是在單純形表上進(jìn)行的，可以將第一階段所得的最終表，畫去

37、所有的人工變量所在的列，將目標(biāo)行的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，來作為求解原問題的初始表即可。,兩階段方法適用于所有線性規(guī)劃問題的求解。,第二階段， 以第一階段的結(jié)論作為原線性規(guī)劃問題的初始基可行解計算。如果是在單純形表上進(jìn)行的，可以將第一階段所得的最終表，畫去所有的人工變量所在的列，將目標(biāo)行的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，來作為求解原問題的初始表即可。,例1 用兩階段方法解下面問題：,從而得到新問題的一個最優(yōu)解 , 進(jìn)而得到原問題的一個基解 .,-2 0 -8 1 1 0 0,-3,2/6 1/2,1/6 1/6 1 -1/6 0 1/6 0,1/3,2/3 4/3 0 1/3 -1 -1/

38、3 1,1/3,-2/3 -4/3 0 -1/3 1 4/3 0,-1/3,- 1/4,1/4 0 1 -1/8 -1/8 1/8 1/8 1/2 1 0 1/4 -3/4 -1/4 3/4,3/8 1/4,0 0 0 0 0 1 1,0,第一階段結(jié)束，將 及第一行畫去，添上 z 的系數(shù)，組成新的單純形表進(jìn)行求解。,-1/4 0 0 21/8 21/8,-63/8,3/2 1/2,如果原問題的系數(shù)矩陣中已經(jīng)包含k (km) 個單位列向量，只要再引入m-k 個人工變量即可。 利用兩階段法求解可以避免計算機(jī)在求解過程中發(fā)生錯誤，特別是尋找線性無關(guān)的向量組時的錯誤，是單純形法的一種改進(jìn)。,注：,若原

39、問題 目標(biāo)函數(shù)要求 max z=CX，則新問題的目標(biāo)函數(shù)應(yīng)為,若原問題目標(biāo)函數(shù)為 min z=CX，則新問題的目標(biāo)函數(shù)應(yīng)為,在構(gòu)造新問題的目標(biāo)函數(shù)時，應(yīng)注意目標(biāo)函數(shù)最大化或最小化之區(qū)別。,大M法也是處理人工變量的常用方法，主要思想是為了使人工變量不對原問題的目標(biāo)函數(shù)產(chǎn)生影響，需要對人工變量引入一個“充分大的數(shù)”M作為懲罰因子。,大M法,例2 試用大M法求解線性規(guī)劃問題.,解 引入松弛變量 、 標(biāo)準(zhǔn)化得：,取 作為初始可行基，列出單純形表,再引入人工變量 、 得：,-4M,-3+6M,1-M,1-3M,0,M,0,0,11,3/2,1,x4 x6 x3,-2 0 1 0 0 0 1,1,0,1,

40、0,0,-1,-2,3,10,0,0,-1,1,-2,1,0,1,0,0,0,-1-M,-1,1-M,M,3M-1,1,x4 x2 x3,0 1 0 0 -1 1 -2,1,-2 0 1 0 0 0 1,1,0,3,0,1,-2,2,-5,12,0 0 0,-1,1,M-1,M+1,-2,4,所以最優(yōu)解 X*=（4,1,9,0,0,0,0) T，最優(yōu)值 z = -2.,x1 x2 x3,1 0 0 1/3 -2/3 2/3 -5/3 0 1 0 0 -1 1 -2 0 0 1 2/3 -4/3 4/3 -7/3,4 1 9,0 0 0 1/3 1/3 M-1/3 M-2/3,2,5.2 單純形

41、法計算中的幾個問題,1目標(biāo)函數(shù)極小化時解的最優(yōu)性判別. 有些書中規(guī)定求目標(biāo)函數(shù)值的極小化作為線性規(guī)劃的標(biāo)準(zhǔn)形式，這時只需以所有檢驗數(shù)j0 作為判別表中解是否最優(yōu)的標(biāo)志.,按最小比值 來確定換出基的變量時，有時出現(xiàn)存在兩個以上相同的最小比值，從而使下一個表的基可行解中出現(xiàn)一個或多個基變量等于零的退化解。 退化解的出現(xiàn)原因是模型中存在多余的約束使多個基可行解對應(yīng)同一頂點。當(dāng)存在退化解時，就有可能出現(xiàn)迭代計算的循環(huán)盡管可能性極其微小。 為避免出現(xiàn)計算的循環(huán)，1974年勃蘭特(Bland)提出了一個簡便有效的規(guī)則： (1)當(dāng)存在多個j0 時始終選取下標(biāo)值為最小的變量作為換入變量； (2)當(dāng)計算 值出現(xiàn)

42、兩個以上相同的最小比值時，始終選取下標(biāo)值為最小的變量作為換出變量。,2退 化,在單純形法迭代原理中，介紹了用單純形法求解時如何判別解是否是唯一最優(yōu)解、無窮多最優(yōu)解和無界解。 當(dāng)線性規(guī)劃問題中添加人工變量后，無論用兩階段法還是大 M 法，初始單純形表中的解因含非零人工變量，故實質(zhì)上是非可行解。 當(dāng)求解結(jié)果出現(xiàn)所有j0時如基變量中仍含有非零的人工變量(兩階段法求解時第一階段目標(biāo)函數(shù)值不等于零)，表明問題無可行解。,3無可行解的判別,1對給定的線性規(guī)劃問題應(yīng)首先化為標(biāo)準(zhǔn)形式，選取或構(gòu)造一個單位矩陣作為基，求出初始基可行解，列出初始單純形表.,2 .單純形法計算步驟的框圖為：,5.3 單純形法小結(jié),標(biāo)

43、準(zhǔn)化，添加人工變量 列出初始單純形表,單純形法計算步驟框圖,j 0?,基變量中含非 零的人工變量,無界解,N,確定換出變量x l ,以kl為主元作基變換,N,Y,Y,確定換入變量x k k=maxj | j 0,Y,無可行解,N,存在非基變量 檢驗數(shù)位零,Y,無窮多最優(yōu)解,N,惟一 最優(yōu)解,是否有 ik0,應(yīng)用線性規(guī)劃解決經(jīng)濟(jì)、管理領(lǐng)域的實際問題，最重要的一步是建立實際問題的線性規(guī)劃模型。 這是一項技巧性很強(qiáng)的創(chuàng)造性工作，既要求對研究的問題有深入了解，又要求很好掌握線性規(guī)劃模型的結(jié)構(gòu)特點，并具有對實際問題進(jìn)行數(shù)學(xué)描述的較強(qiáng)的能力。,線性規(guī)劃應(yīng)用,建模,要求解的問題的目標(biāo)能用數(shù)值指標(biāo)來反映，且為

44、線性函數(shù)； 為達(dá)到這個目標(biāo)存在多種方案； 要達(dá)到的目標(biāo)是在一定約束條件下實現(xiàn)的，這些條件可用線性等式或不等式描述.,一般來講，一個經(jīng)濟(jì)、管理問題要滿足下列條件，才能建立線性規(guī)劃的模型：,合理利用材料問題：如何下料使用材最少。 配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤。 投資問題：從投資項目中選取方案，使投資回報最大。 產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大。 勞動力安排：用最少的勞動力來滿足工作的需要。 運輸問題：如何制定調(diào)運方案，使總運費最小。,數(shù)學(xué)規(guī)劃的建模有許多共同點，要遵循下列原則： (1)容易理解。建立的模型不但要求建模者理解，還應(yīng)當(dāng)讓有關(guān)人員理解。這樣便于考察實

45、際問題與模型的關(guān)系，使得到的結(jié)論能夠更好地應(yīng)用于解決實際問題。 (2)容易查找模型中的錯誤。這個原則的目的顯然與(1)相關(guān)。常出現(xiàn)的錯誤有：書寫錯誤和公式錯誤。 (3)容易求解。對線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個數(shù)和約束條件的個數(shù)。這條原則的實現(xiàn)往往會與(1)發(fā)生矛盾，在實現(xiàn)時需要對兩條原則進(jìn)行統(tǒng)籌考慮。,某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：,例.人力資源分配的問題,設(shè)司機(jī)和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作8h，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?,目標(biāo)函數(shù)：Min x1 + x2

46、 + x3 + x4 + x5 + x6,解：設(shè) xi 表示第 i 班次時開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型：,約束條件： x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0,例.生產(chǎn)計劃問題 某車間在每個生產(chǎn)周期5天所需要的某種刀具，每一把刀具的成本為0.6元，用過的刀具送到機(jī)修車間研磨，每把刀具需花費0.20元。刀具每天用過之后，如果立即送去研磨，兩天后可以磨好送回，供當(dāng)天的需用，第5天后，刀具應(yīng)全部換新。每周期開始時，該車間沒有任何刀具。車間每天所需

47、刀具數(shù)目如下表所示，問這個車間需要多少刀具才能應(yīng)付需要，而成本又最低？試建立其線性規(guī)劃模型。,分析：問題要確定的是每期5天需要新刀具的總數(shù)，等價于要確定每天所需用的新刀具數(shù)。 考慮到刀具用過后，可送去研磨，兩天后送回供第3天使用。設(shè)決策變量 xi ( i =1,2,3,4,5)為第 i 天使用的新刀具， yj ( j =1,2,3)為第 j 天送去研磨的刀具數(shù)。,由于刀具所花費的成本是由兩部分組成： 新刀具總數(shù)的成本 0.6(x1+x2+x3+x4+x5) 送去研磨的刀具總數(shù)所需費用 0.2(y1+y2+y3) 因此，目標(biāo)函數(shù)所要求的成本最低： minZ= 0.6(x1+x2+x3+x4+x5

48、) +0.2(y1+y2+y3),由于送去研磨的刀具第3天才能使用，所以第1，2天所使用的只能是新刀具，即 x1 =120 x2 =85 從第3天起，每天使用的刀具可以是新的，也可以是磨好后送來回的，所以有： x3 + y1 =160 x4 + y2 =145 x5 + y3 =300,在每期的頭3天送去研磨的刀具數(shù)應(yīng)滿足： y1120 y285+(120-y1) y3160+(120-y1)+(85-y2) 每天使用新刀具 xi 和送去研磨的刀具數(shù) yj 都是非負(fù)的整數(shù)，即：xi 0, yj 0,且均為整數(shù).,例.合理下料問題 某工廠生產(chǎn)某一種型號的機(jī)床，每臺機(jī)床上需要2.9m、2.1m、1

49、.5m的軸，分別為1根，2根，1根。這些軸需要用同一種圓鋼制作，圓鋼的長度為7.4m, 如果要生產(chǎn)100臺機(jī)床，問應(yīng)如何安排下料，才能用料最省？試建立其線性規(guī)劃模型。,對于每一根7.4m長的鋼材，可有若干種下料方式把它截取成我們所需要的軸，比如要在7.4m長的鋼材上截取2根2.9m的軸和1根1.5m的軸,合計用料 2.92+1.5=7.3m 殘料則為0.1m。,現(xiàn)把所有可能的下料方式 列于下表中:,問題所要確定的是每種下料方式 應(yīng)各用多少根7.4m的圓鋼. 設(shè) x1，x2，x3，x4，x5，x6，x7，x8 分別為按 B1，B2，B3，B4，B5，B6，B7，B8 方式下料的圓鋼根數(shù)。,目標(biāo)是

50、使總的下料根數(shù)最少,即 minZ=x1+x2+x3+x4+x5+x6+x7+x8,由于每臺機(jī)床所需不同長度的軸的根數(shù)是確定的，因此生產(chǎn)100臺機(jī)床所需2.9m的軸100根，2.1m軸200根，1.5m的軸100根。,因此所截下的2.9m長的軸的總數(shù)不少于100根,即滿足約束條件 2x1+x2+x3+x4100 所截下的2.1m長的軸的總數(shù)滿足約束條件 2x3+x4+2x5+x6+3x7200 所截下的1.5m長的軸的總數(shù)滿足約束條件 x1+3x2+x4+2x5+3x6+4x8100,按每種下料方式 的圓鋼根數(shù)應(yīng)滿足非負(fù)要求,且為整數(shù),即 x1, x2, x3, x4, x5, x6, x7,

51、x80且為整數(shù),所以得到數(shù)學(xué)模型：,例.載貨問題 有一艘貨輪,分前,中,后三個艙位,它們的容積與最大允許載貨量如下表所示,現(xiàn)有三種貨物待運,已知有關(guān)數(shù)據(jù)列于下表,又為了航運安全,要求前,中,后艙實際載重量上大體保持各艙最大允許載重量的比例關(guān)系.具體要求前,后艙分別與中艙之間載重量比例上偏差不超過15%,前后艙之間不超過10%. 問該貨輪應(yīng)裝載A,B,C各多少件,運貨收入為最大?試建立這個問題的線性規(guī)劃模型。,解：因為A,B,C三種商品在貨輪的前,中,后艙均可裝載,令 i=1,2,3分別代表商品A,B,C, j=1,2,3分別代表前,中,后艙, 決策變量 xij為裝于j 艙位的第i種商品的數(shù)量(件),商品A的件數(shù)為x11+x12+x13, 即裝于前,中,后艙的商品A的件數(shù)之和, 商品B的件數(shù)為 x21+x22+x23 商品C的件數(shù)為x3