1、第一章 線性規(guī)劃1.1線性規(guī)劃模型 1.1.1線性規(guī)劃數(shù)學(xué)模型共同特征 1.1.2線性規(guī)劃的一般形式 1.1.3線性規(guī)劃的標(biāo)準(zhǔn)式 1.1.4如何化標(biāo)準(zhǔn)型的問題1.2線性規(guī)劃的圖法解1.3單純形法 1.3.1線性規(guī)劃的基本概念 1.3.2單純形原理 1.3.3單純形法及軟件實現(xiàn)法 1.3.4解的判別1.4對偶理論1.5靈敏度分析運(yùn)籌學(xué)史慧萍22022-3-251.1線性規(guī)劃模型1.1.1線性規(guī)劃數(shù)學(xué)模型共同特征1.1.2線性規(guī)劃的一般形式1.1.3線性規(guī)劃的標(biāo)準(zhǔn)式1.1.4如何化標(biāo)準(zhǔn)型的問題運(yùn)籌學(xué)史慧萍32022-3-25問題的提出問題的提出在生產(chǎn)管理和經(jīng)營活動中，組織者常常必須對在生產(chǎn)管理和經(jīng)

2、營活動中，組織者常常必須對如何向不同的活動如何向不同的活動分配資源分配資源的問題做出決策，以便的問題做出決策，以便最好地達(dá)成組織的目標(biāo)。最好地達(dá)成組織的目標(biāo)。這樣的問題通常有兩類，一類是如何合理地使用這樣的問題通常有兩類，一類是如何合理地使用有限的勞動力、設(shè)備、資金等資源，有限的勞動力、設(shè)備、資金等資源，以最大化效益以最大化效益；另一類是為了達(dá)到一定的目標(biāo)，應(yīng)如何組織生產(chǎn)，或另一類是為了達(dá)到一定的目標(biāo)，應(yīng)如何組織生產(chǎn)，或合理安排工藝流程，或調(diào)整產(chǎn)品的成分合理安排工藝流程，或調(diào)整產(chǎn)品的成分以使資源以使資源消耗最少。消耗最少。運(yùn)籌學(xué)史慧萍42022-3-25線性規(guī)劃是運(yùn)籌學(xué)的重要組成部分，也是最基

3、礎(chǔ)的線性規(guī)劃是運(yùn)籌學(xué)的重要組成部分，也是最基礎(chǔ)的部分。自部分。自1947年丹齊格（年丹齊格（G.B.Dantzig）提出了求解線性提出了求解線性規(guī)劃的一般方法單純形法以來，線性規(guī)劃在理論上規(guī)劃的一般方法單純形法以來，線性規(guī)劃在理論上趨向成熟，日臻完善，尤其是計算機(jī)處理問題的規(guī)模及趨向成熟，日臻完善，尤其是計算機(jī)處理問題的規(guī)模及運(yùn)算速度提高后，線性規(guī)劃的應(yīng)用領(lǐng)域更加廣泛。無論運(yùn)算速度提高后，線性規(guī)劃的應(yīng)用領(lǐng)域更加廣泛。無論工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、軍事、經(jīng)濟(jì)計劃和管理工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、軍事、經(jīng)濟(jì)計劃和管理決策等領(lǐng)域都有應(yīng)用。大到一個國家、一個地區(qū)，小到?jīng)Q策等領(lǐng)域都有應(yīng)用。大到一個國家

4、、一個地區(qū)，小到一個企業(yè)、一個車間、一個班組都有運(yùn)用線性規(guī)劃后提一個企業(yè)、一個車間、一個班組都有運(yùn)用線性規(guī)劃后提高經(jīng)濟(jì)效益的例子。高經(jīng)濟(jì)效益的例子。簡介簡介運(yùn)籌學(xué)史慧萍52022-3-25向不同的活動分配的資源可以是資金、不同的人員以及向不同的活動分配的資源可以是資金、不同的人員以及機(jī)器、設(shè)備。而需要這些資源的活動也可以是各類生產(chǎn)活動，機(jī)器、設(shè)備。而需要這些資源的活動也可以是各類生產(chǎn)活動，例如產(chǎn)品生產(chǎn)、營銷、在不同媒體做廣告、金融活動、進(jìn)行例如產(chǎn)品生產(chǎn)、營銷、在不同媒體做廣告、金融活動、進(jìn)行資金投資或其他一些活動。資金投資或其他一些活動。由于所有活動都要求一定資源作支撐，而資源卻是有限由于所有

5、活動都要求一定資源作支撐，而資源卻是有限的，這必然導(dǎo)致活動間的沖突與矛盾。這就需要管理者利用的，這必然導(dǎo)致活動間的沖突與矛盾。這就需要管理者利用一些科學(xué)的方法進(jìn)行協(xié)調(diào)，以使資源達(dá)到最大的效用。一些科學(xué)的方法進(jìn)行協(xié)調(diào)，以使資源達(dá)到最大的效用。運(yùn)籌學(xué)史慧萍62022-3-25顯然，上述活動所引起的問題是一類顯然，上述活動所引起的問題是一類有約束的有約束的最優(yōu)化問題（最優(yōu)化問題（Constrained Optimization）。線性規(guī)劃線性規(guī)劃正是解決有約束的最優(yōu)化問題的一種正是解決有約束的最優(yōu)化問題的一種常用的方法，其涉及的主要概念包括：常用的方法，其涉及的主要概念包括：目標(biāo)（目標(biāo)（Object

6、ive）:所要達(dá)到的最優(yōu)結(jié)果（最所要達(dá)到的最優(yōu)結(jié)果（最或最小）；或最?。?；約束條件（約束條件（Constraints）:對所能產(chǎn)生結(jié)果的對所能產(chǎn)生結(jié)果的限制。限制。運(yùn)籌學(xué)史慧萍72022-3-25解決線性規(guī)劃問題的一般步驟解決線性規(guī)劃問題的一般步驟定義問題和定義問題和收集數(shù)據(jù)收集數(shù)據(jù)。必須向管理者咨詢所要考慮問必須向管理者咨詢所要考慮問題涉及到的數(shù)據(jù)及確定研究的合理目標(biāo)。題涉及到的數(shù)據(jù)及確定研究的合理目標(biāo)。建立模型建立模型，用恰當(dāng)?shù)臄?shù)學(xué)式表示問題。，用恰當(dāng)?shù)臄?shù)學(xué)式表示問題。求求出問題的出問題的最優(yōu)解最優(yōu)解。進(jìn)行進(jìn)行敏感性分析敏感性分析，檢查條件發(fā)生變化時可能發(fā)生的，檢查條件發(fā)生變化時可能發(fā)生的

7、情況。情況。運(yùn)籌學(xué)史慧萍82022-3-25n教材P9例1.1.1： 某公司有三條生產(chǎn)線來生產(chǎn)兩種產(chǎn)品，其主要數(shù)據(jù)如下表（時間單位為小時，利潤單位為百元）。請問，如何生產(chǎn)可以讓公司每周利潤最大？生產(chǎn)線生產(chǎn)每批產(chǎn)品所需時間生產(chǎn)每周可用時間資源單位成本產(chǎn)品產(chǎn)品11041百元/小時202121百元/小時332181百元/小時產(chǎn)品售價(百元)79運(yùn)籌學(xué)史慧萍92022-3-25數(shù)學(xué)模型n解：設(shè)x1為每周生產(chǎn)產(chǎn)品的數(shù)量；x2為每周生產(chǎn)產(chǎn)品的數(shù)量。線性規(guī)劃模型為0, 01823122 4 .53max21212121xxxxxxtsxxz運(yùn)籌學(xué)史慧萍102022-3-251.1.1線性規(guī)劃數(shù)學(xué)模型共同特征

8、：n(1)一組決策變量x1,x2,xn 。n(2)存在一定的約束條件。n(3)目標(biāo)函數(shù)，要求目標(biāo)函數(shù)實現(xiàn)最大化或最小化 。 以上三個條件（決策變量、約束條件、目標(biāo)函數(shù)）稱為數(shù)學(xué)模型稱為線性規(guī)劃(Linear Programming)的數(shù)學(xué)模型的三要素。 即在一定的約束條件（限制條件）下，使得某一目標(biāo)函數(shù)取得最大或最小值。當(dāng)規(guī)劃問題的目標(biāo)函數(shù)與約束條件都是線性函數(shù)，便稱為線性規(guī)劃問題。運(yùn)籌學(xué)史慧萍112022-3-251.1.2線性規(guī)劃的一般形式)21 (3)-(1 0),( ),( ),( . .1)-(1 )(k21j221122222121112121112211，滿足約束條件：目標(biāo)函數(shù)x

9、xxbxaxaxabxaxaxabxaxaxatsxcxcxczminmaxjjmnmnmmnnnnnn運(yùn)籌學(xué)史慧萍122022-3-251.1.3線性規(guī)劃的標(biāo)準(zhǔn)式0, 0, 0, 0, 018 2312 24 .00053max54321521423154321xxxxxxxxxxxxtsxxxxxz100230102000101A運(yùn)籌學(xué)史慧萍132022-3-25一般線性規(guī)劃問題的標(biāo)準(zhǔn)型為), 2 , 1( , 0), 2 , 1( ,.max11njxmibxatsxczjinjjijjnjj)51 (6)-(1 , 1, 2 , 1, 0 . .4)-(1 22112222212111

10、2121112211nnjxbxaxaxabxaxaxabxaxaxatsxcxcxcmaxzjmnmnmmnnnnnn1.求目標(biāo)函數(shù)最大值。2.所有的資源約束都用等式表示。3.資源約束等式的右端常數(shù)是非負(fù)數(shù)。4.所有決策變量是非負(fù)的，且全部變量出現(xiàn)在非負(fù)約束中。運(yùn)籌學(xué)史慧萍142022-3-25線性規(guī)劃的矩陣式：0 . max21212121222211121121212211XxxxbAXbbbxxxaaaaaaaaatsXCxxxcccxcxcxczTnmnmnmmnnTnnnn0.maxXbAXtsXCzT運(yùn)籌學(xué)史慧萍152022-3-25 (1)最小化問題的轉(zhuǎn)化。 若目標(biāo)函數(shù)min

11、zCTX，即令zz，于是得到max z CTX。 (2)不等式的處理。 約束方程為不等式有兩種情況：一種是約束方程為不等式，則可在不等式的左端加入非負(fù)松弛變量，把原不等式變?yōu)榈仁?；另一種是約束方程為不等式，則可在不等式的左端減去一個非負(fù)剩余變量，把不等式約束條件變成等式約束條件。松弛變量與剩余變量在目標(biāo)函數(shù)中的系數(shù)為0。 (注：人工變量是為了始系數(shù)矩陣中容易找到一個基而在方程等式中加的一個人造變量。) 1.1.4如何化標(biāo)準(zhǔn)型的問題運(yùn)籌學(xué)史慧萍162022-3-25 (3)非正變量與符號無限制變量的處理。 某個變量xj0，令xjxj ，則新變量xj0；若存在取值無約束變量xk，可令xkxkxk，

12、其中xk、xk0。 (4)約束條件中帶有絕對值不等式ax1+bx2d (d 0)，則可把它化為一個不等式組ax1+bx2d ，ax1bx2d，再按(2)化為等式約束。 (5)某個變量有上、下界ej xj fj，只要令xjxjej引入新變量，便可化ej xj fj為 0 xj fj-ej，最后將上限不等式約束條件變成等式約束條件。運(yùn)籌學(xué)史慧萍172022-3-25解 令x3x3x3再引入松弛變量x4、剩余變量x5，則有如下標(biāo)準(zhǔn)型：010)(36)(427)(3.)00)(5(max5433213325332143321543321xxxxxxxxxxxxxxxxxxxtsxxxxxxz、例 將下

13、面LP問題化為標(biāo)準(zhǔn)型：無符號限制、32132321321321, 010364273.5minxxxxxxxxxxxtsxxxz運(yùn)籌學(xué)史慧萍182022-3-251.2圖解法 現(xiàn)對例1.1.1進(jìn)行圖解。該計劃問題可用數(shù)學(xué)模型表示為： 目標(biāo)函數(shù) 滿足約束條件0, 018231224.53max21212121xxxxxxtsxxz運(yùn)籌學(xué)史慧萍192022-3-25圖解法的主要步驟是：n第一步：在直角坐標(biāo)系中分別做出各約束條件，從而確定可行域(線性規(guī)劃問題的解的集合)。n第二步：做出一條目標(biāo)函數(shù)等值線。n第三步；將目標(biāo)函數(shù)等值線沿目標(biāo)函數(shù)值增大(或減小)方向移動，以求得最優(yōu)解或確定線性規(guī)劃無解。

14、圖解法的幾種情況： 1.唯一解 2.無窮解 3.無界解 4.無解max zx1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域目標(biāo)函數(shù)等值線最優(yōu)解(4/3,14/3)(6,0)(0,4)(-8,0)(0,6)0 x1x2例1：線性規(guī)劃的圖解例題(唯一解)2022-3-2520運(yùn)籌學(xué)史慧萍運(yùn)籌學(xué)史慧萍212022-3-250, 01823122 4 .53max21212121xxxxxxtsxxz例2：線性規(guī)劃的圖解例題(唯一解)(4,0)(0,6)(6,0)(0,9)(4,3)(2,6)(4,6)(0,0)x1x2可行域目標(biāo)函數(shù)等值線最優(yōu)解運(yùn)籌學(xué)史慧萍222022-3

15、-250, 01823122 4 .23max21212121xxxxxxtsxxz例3：線性規(guī)劃的圖解例題(無窮解)(4,0)(0,6)(6,0)(0,9)(4,3)(2,6)(4,6)(0,0)x1x2可行域目標(biāo)函數(shù)等值線最優(yōu)解運(yùn)籌學(xué)史慧萍232022-3-250, 04 .53max21121xxxtsxxz例4：線性規(guī)劃的圖解例題(無界解)(4,0)(0,0)x1x2目標(biāo)函數(shù)等值線可行域運(yùn)籌學(xué)史慧萍242022-3-250, 050531823122 4 .53max2121212121xxxxxxxxtsxxz例5：線性規(guī)劃的圖解例題(無解)(4,0)(0,6)(6,0)(0,9)(

16、4,3)(2,6) (4,6)(0,0)x2目標(biāo)函數(shù)等值線(0,10)(16.67,0)無可行域！x1運(yùn)籌學(xué)史慧萍252022-3-25線形規(guī)劃問題最優(yōu)解的情況：n有最優(yōu)解1)有唯一的最優(yōu)解2)有無窮多的最優(yōu)解n無最優(yōu)解1)無界解（有可行解但無有最優(yōu)解）2)無可行解運(yùn)籌學(xué)史慧萍262022-3-25圖解法基本要求n能正確地按圖解法的步驟畫出圖來解答題目，并會判定解的類型。運(yùn)籌學(xué)史慧萍272022-3-253.3單純形法3.3.1線性規(guī)劃的基本概念3.3.2單純形原理3.3.3單純形法及軟件實現(xiàn)法3.3.4解的判別運(yùn)籌學(xué)史慧萍282022-3-253.3.1線性規(guī)劃的基本概念可行解： 滿足約束條

17、件(b)、(c)的解X=（x1， ，xn)T，稱為線性規(guī)劃問題的可行解。全部可行解的集合稱為可行域。最優(yōu)解：使目標(biāo)函數(shù)(a)達(dá)到最大值的可行解稱為最優(yōu)解。njxmibxatsxczjnjijijnjjj,.,2 , 10,.,2 , 1. .max11 （a） （b） （c）運(yùn)籌學(xué)史慧萍292022-3-25線性規(guī)劃的可行域是凸集線性規(guī)劃的最優(yōu)解在頂點(diǎn)(極點(diǎn))上凸集凸集不是凸集頂點(diǎn)不是凸集運(yùn)籌學(xué)史慧萍302022-3-25u 幾何意義 P15凸集：設(shè)K是n維歐氏空間的一點(diǎn)集，若對任意的x1，x2K， 有 ，則稱K為凸集。) 10()1 (21Kxx的凸組合。，為則稱使得且，若存在個點(diǎn)，中的維歐

18、式空間的是凸組合：設(shè)kkkkiiikkxxxxxxxxkiknxxx212211121n21,1);, 2 , 1( 10,E,。的一個頂點(diǎn)（或極點(diǎn)）為，則稱線性組合表示為的中的兩點(diǎn)不能用。若是凸集，頂點(diǎn)：設(shè)KxxxxxxKxKxK) 10()1 (:,2121運(yùn)籌學(xué)史慧萍312022-3-25定義1基：設(shè)Amn (nm)為約束方程組(b)的系數(shù)矩陣，其秩為m。Bmm 是矩陣A 中的一個mm 階的滿秩子矩陣，稱B 是線性規(guī)劃問題的一個基。不失一般性，設(shè)mmmmmmmPPPaaaaaaaaaB,.,21212222111211 B 中的每一個列向量Pj（j=1,2,m）稱為基向量，與基向量Pj

19、對應(yīng)的變量xj 稱為基變量。除基變量以外的其它變量稱為非基變量。運(yùn)籌學(xué)史慧萍322022-3-25定義2：基解：假設(shè)系數(shù)矩陣A 的秩為m，不妨設(shè)A 中前m 個列向量線性獨(dú)立，方程可以寫為nmnnnmmmmmmmmmmmmmxaaaxaaabbbxaaaxaaaxaaa211112112121222212112111令所有非基變量xm+1= =xn=0， 由|B|0，根據(jù)克萊姆規(guī)則，可得m個基變量的唯一解xb=(x1,x2,xm)加上所有取值為0 的非基變量，得：x=(x1,x2,xm,0,0)稱x 為線性規(guī)劃問題的基解。運(yùn)籌學(xué)史慧萍332022-3-25定義3：基可行解： 滿足變量非負(fù)約束條件

20、(c)的基解稱為基可行解。定義4：可行基：對應(yīng)于基可行解的基稱為可行基?？尚薪饣?解基可行解退化基可行解與非退化基可行解: 稱含零值基變量的可行解為退化基可行解,對應(yīng)的基為退化可行基。 稱基變量都不為零的基可行解為非退化基可行解,對應(yīng)的基為非退化可行基。),(運(yùn)籌學(xué)史慧萍342022-3-25引理1.1:若線性規(guī)劃問題存在可行域,則其可行域是凸集。引理1.2:線性規(guī)劃問題的可行解X=(x1,x2,xn)T為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。定理1.1:線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點(diǎn)。定理1.2:若可行域有界,線性規(guī)劃問題的目標(biāo)函數(shù)一定在其可行域的頂點(diǎn)上

21、達(dá)到最優(yōu),即一定存在一個基可行解是最優(yōu)解。定理1.3 線性規(guī)劃問題的一般形式與標(biāo)準(zhǔn)形式等價。若可行域無界,則線性規(guī)劃問題可能無最優(yōu)解,也可能有最優(yōu)解。若有也一定在某個頂點(diǎn)上得到。定理1.2給我們的啟示 1.存在性 2.最優(yōu)解(若有)一定在某個頂點(diǎn)上得到njxmibxatsxczjnjijijnjjj,.,2 , 10,.,2 , 1. .max11線性規(guī)劃問題：運(yùn)籌學(xué)史慧萍352022-3-25例題：試求下例線性規(guī)劃問題的一個基(向量)及其對應(yīng)的基變量、非基變量，一個基解和一個基可行解。543211001030105400149PPPPPA543100010001PPPB基解：x1 0， x2

22、0，x3360，x4200，x5300基變量x3，x4，x5。非基變量x1，x2。x1 0， x20，x3360，x4200，x5300是基可行解5421010015004PPPB基變量x2，x4，x5。非基變量x1，x3?；猓簒1 0， x290，x30，x4250，x5600 x1 0， x290，x30，x4 250 ，x5 600不是基可行解 x1 x2 x3 x4 x5 03001032005436049.00012070max5432152142132154321xxxxxxxxxxxxxxtsxxxxxz、mnC?最多能有多少個基解基解、基可行解(基解是否實際可行解？)max

23、zx1+3x2s.t. x1+ x26-x1+2x28x1 0, x20max z x1+3x2+0 x3+0 x4s.t. x1+ x2+x3 =6 -x1+2x2 +x4=8 x1, x2,x3,x40 x1A(6,0)C(0,4)E(-8,0)D(0,6)O(0,0)x2Bx3=0 x4=02022-3-2536運(yùn)籌學(xué)史慧萍幾何概念代數(shù)概念約束直線滿足一個等式約束的解約束半平面滿足一個不等式約束的解約束半平面的交集：凸多邊形滿足一組不等式約束的解約束直線的交點(diǎn)基解可行域的頂點(diǎn)(極點(diǎn))基可行解目標(biāo)函數(shù)等值線：一組平行線 目標(biāo)函數(shù)值等于一個常數(shù)的解2022-3-2537運(yùn)籌學(xué)史慧萍運(yùn)籌學(xué)史慧

24、萍382022-3-25線性規(guī)劃模型基本要求n 1理解線性規(guī)劃的概念。n 2理解線性規(guī)劃的一般形式與標(biāo)準(zhǔn)形式，能夠把前者轉(zhuǎn)化為居者。n 3掌握線性規(guī)劃問題的可行解、最優(yōu)解和標(biāo)準(zhǔn)形式的線性規(guī)劃問題的基、基解、基可行解、可行基等重要概念。運(yùn)籌學(xué)史慧萍392022-3-251.3.2單純形法原理（用代數(shù)方法求解LP）圖解法的局限性？ 1947年G.B.Dantzig提出的單純形法提供了方便、有效的通用算法求解線性規(guī)劃。一、單純形法的基本思想1、頂點(diǎn)的逐步轉(zhuǎn)移 即從可行域的一個頂點(diǎn)（基本可行解）開始，轉(zhuǎn)移到另一個頂點(diǎn)（另一個基本可行解）的迭代過程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函

25、數(shù)達(dá)到最優(yōu)值時，問題也就得到了最優(yōu)解。運(yùn)籌學(xué)史慧萍402022-3-25 線性規(guī)劃問題的可行域是凸集，一個線性規(guī)劃問題有最優(yōu)解，就一定可以在可行域的頂點(diǎn)上找到。 于是，若某線性規(guī)劃只有唯一的一個最優(yōu)解，這個最優(yōu)解所對應(yīng)的點(diǎn)一定是可行域的一個頂點(diǎn)；若該線性規(guī)劃有多個最優(yōu)解，那么肯定在可行域的頂點(diǎn)中可以找到至少一個最優(yōu)解。頂點(diǎn)轉(zhuǎn)移的依據(jù)？ 轉(zhuǎn)移條件？ 轉(zhuǎn)移結(jié)果？ 使目標(biāo)函數(shù)值得到改善 得到LP最優(yōu)解，目標(biāo)函數(shù)達(dá)到最優(yōu)值 2需要解決的問題： (1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？ (2)目標(biāo)函數(shù)何時達(dá)到最優(yōu) 判斷標(biāo)準(zhǔn)是什么？ 運(yùn)籌學(xué)史慧萍412022-3-25第一步：引入非負(fù)的松弛變量x3,x4,

26、x5, 將該LP化為標(biāo)準(zhǔn)型0,18231224.5321212121xxxxxxtsxxz max)5 , 4 , 3 , 2 , 1(018231224. .00053521423154321jxxxxxxxxtsxxxxxz maxj運(yùn)籌學(xué)史慧萍422022-3-25對應(yīng)的基變量是 x3, x4 ,x5 第二步：尋求初始可行基，確定基變量100230102000101A100010001543PPPB運(yùn)籌學(xué)史慧萍432022-3-25第三步：寫出初始基本可行解和相應(yīng)的目標(biāo)函數(shù)值兩個關(guān)鍵的基本表達(dá)式：(1) 用非基變量表示基變量的表達(dá)式TXxxxxxxx)18,12, 4 , 0 , 0(2

27、3182124)0(2152413初始基可行解0 53021）（當(dāng)前的目標(biāo)函數(shù)值ZxxZ(2) 用非基變量表示目標(biāo)函數(shù)的表達(dá)式運(yùn)籌學(xué)史慧萍442022-3-25第四步：分析兩個基本表達(dá)式，看看目標(biāo)函數(shù)是否可以改善？(1)分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式 z=3x1+5x2 非基變量前面的系數(shù)均為正數(shù)，所以任何一個非基變量進(jìn)基都能使Z值增加 通常把非基變量前面的系數(shù)叫“檢驗數(shù)”；(2) 選哪一個非基變量進(jìn)基？ 選x2為進(jìn)基變量（換入變量）運(yùn)籌學(xué)史慧萍452022-3-25(3) 確定出基變量 x2進(jìn)基意味著其取值從0變成一個正數(shù)，能否無限增大？ 當(dāng)x2增加時，x3，x4，x5如何變化？ 現(xiàn)在的

28、非基變量是哪些？ 具體如何確定換出變量？由用非基變量表示基變量的表達(dá)式215241323182124xxxxxxx 當(dāng)x2增加時，x4，x5會減小，但有限度必須大于等于0，以保持解的可行性！（這時x1仍是非基變量，取值為0）于是運(yùn)籌學(xué)史慧萍462022-3-256218,212min2182120218021223182124222222152413xxxxxxxxxxxx 當(dāng)x2的值從0增加到6時，x4首先變?yōu)?，此時x5=60,因此選x4為出基變量（換出變量）。這種用來確定出基變量的規(guī)則稱為 “最小比值原則”。(4) 基變換新的基變量x3,x2,x5；新的非基變量x1,x4；寫出用非基變量

29、表示基變量的表達(dá)式：215421323182164xxxxxxx215241323182124xxxxxxx4154213362164xxxxxxx運(yùn)籌學(xué)史慧萍472022-3-25可得新的基可行解(5) 寫出用非基變量表示目標(biāo)函數(shù)的表達(dá)式 ：414121x25x330)x216(5x3x5x3Z可得相應(yīng)的目標(biāo)函數(shù)值為Z（1）=30檢驗數(shù)仍有正的返回(1)進(jìn)行討論。第五步：上述過程何時停止？當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式中，非基變量的系數(shù)（檢驗數(shù)）全部非正時，當(dāng)前的基本可行解就是最優(yōu)解!TX)6 , 0 , 4 , 6 , 0()1(運(yùn)籌學(xué)史慧萍482022-3-251.3.3單純形法及軟件

30、實現(xiàn)求單純形表法解線性規(guī)劃問題:0,36 2 2 25 .00243max6543216432254321654321xxxxxxxxxxxxxxxxtsxxxxxxz解：標(biāo)準(zhǔn)型0,362 2 25 .243max4321432243214321xxxxxxxxxxxxtsxxxxz運(yùn)籌學(xué)史慧萍492022-3-25初始單純形表x2進(jìn)基。方程BV系數(shù)右邊比值zx1x2x3x4x5x6z - 3x1-4x2+x3-2x4 =0z1-3-41-2000 x1 +x2 +x3 +x4 +x5 25 x5011111025x1 +2x2 +x3 +2x4 +x6 36 x6012120136 x6出基

31、。25/1=2536/2=18運(yùn)籌學(xué)史慧萍502022-3-25單純形表第一次迭代(以a22為中心)x2進(jìn)基。方程BV系數(shù)右邊比值zx1x2x3x4x5x6z - 3x1-4x2+x3-2x4 =0z1-3-41-2000 x1 +x2 +x3 +x4 +x5 25 x5011111025x1 +2x2 +x3 +2x4 +x6 36 x6012120136 x6出基。x20-132272z-x1+3x3+2x4 +2x6 =721001/21/201-1/27(1/2)x1 +(1/2)x3 +x5-( 1/2)x6 7101/21/2101/218(1/2)x1 +x2 +(1/2)x3

32、+x4+(1/2)x618 檢驗數(shù)10，故不是最優(yōu)解。0運(yùn)籌學(xué)史慧萍512022-3-25換入變量與換出變量的確定x1進(jìn)基。方程BV系數(shù)右邊比值zx1x2x3x4x5x6z-x1+3x3+2x4 +2x6 =72z1-10320272(1/2)x1+(1/2)x3+x5- (1/2)x6 7x501/201/201-1/27(1/2)x1 +x2 +(1/2)x3+x4+(1/2)x6 18 x201/211/2101/218 x5出基。2172118運(yùn)籌學(xué)史慧萍522022-3-25單純形表第二次迭代(以a11為中心)x1進(jìn)基。方程BV系數(shù)右邊比值zx1x2x3x4x5x6z-x1+3x3+

33、2x4 +2x6 =72z1-10320272(1/2)x1+(1/2)x3 +x5- (1/2)x6 7x501/201/201-1/27(1/2)x1+x2 +(1/2)x3+x4+(1/2)x6 18 x201/211/2101/218 x5出基。010422186z+4x3+2x4+2x5+x6 =8600101-1111x2+x4 x5+x611100102-114 x1+x3 +2x5- x6 14最優(yōu)解為(x1， x2， x3， x4， x5 ， x6) (14, 11,0,0, 0,0)最優(yōu)值為86。檢驗數(shù)i0，故是最優(yōu)解。x1 運(yùn)籌學(xué)史慧萍532022-3-25單純形法軟件實

34、現(xiàn)（例單1）運(yùn)籌學(xué)史慧萍542022-3-250,182312245321212121xxxxxxxxz max用WINQSB求解下列線性規(guī)劃問題：（例靈敏度分析）運(yùn)籌學(xué)史慧萍552022-3-251.3.4解的判別（1）退化現(xiàn)象(經(jīng)過幾次迭代后會出現(xiàn)循環(huán))防止循環(huán)的方法： 勃蘭特規(guī)則：1、選取檢驗數(shù)j 0中下標(biāo)最小的非基變量xk 為換入變量，即： k=minj|j 02、當(dāng)有兩個或兩個以上的最小比值時，選取下標(biāo)最小的基變量為換出變量。運(yùn)籌學(xué)史慧萍562022-3-25BVEq系 數(shù)右邊-zx1x2x3x4x5x6x7-z(0)1000-3/420-1/260 x1(1)01001/4-8-1

35、90 x2(2)00101/2-12-1/230 x3(3)000100101-z(0)13000-4-7/2330 x4(1)04001-32-4360 x2(2)0-210043/2-150 x3(3)000100101-z(0)111000-2180 x4(1)0-1280108-840 x5(2)0-1/21/40013/8-15/40 x3(3)000100101-z(0)1-2301/400-30 x6(1)0-3/2101/801-21/20 x5(2)01/16-1/80-3/64103/160 x3(3)03/2-11-1/80021/21-z(0)1-110-1/21600

36、0 x6(1)02-60-5/256100 x7(2)01/3-2/30-1/416/3010 x3(3)0-2615/2-56001-z(0)10-20-7/4441/200 x1(1)01-30-5/4281/200 x7(2)001/301/6-4-1/610 x3(3)000100101-z(0)1000-3/420-1/260 x1(1)01001/4-8-190 x2(2)00101/2-12-1/230 x3(3)0001001017 , 6 , 5 , 4 , 3 , 2 , 1, 01 035 . 0125 . 0 09 825. 0 65 . 02075. 0 637654

37、2765417654jxxxxxxxxxxxxxstxxxxzminj運(yùn)籌學(xué)史慧萍572022-3-25BVEq系 數(shù)右邊-zx1x2x3x4x5x6x7-z(0)1000-3/420-1/260 x1(1)01001/4-8-190 x2(2)00101/2-12-1/230 x3(3)000100101-z(0)13000-4-7/2330 x4(1)04001-32-4360 x2(2)0-210043/2-150 x3(3)000100101-z(0)111000-2180 x4(1)0-1280108-840 x5(2)0-1/21/40013/8-15/40 x3(3)000100

38、101-z(0)1-2301/400-30 x6(1)0-3/2101/801-21/20 x5(2)01/16-1/80-3/64103/160 x3(3)03/2-11-1/80021/21-z(0)10-10-5/432030 x6(1)00-20-1241-60 x1(2)01-20-3/416030 x3(3)00211-24061-z(0)1001/2-3/420061/2x6(1)000100101x1(2)01011/4-8091x2(3)0011/21/2-12031/2-z(0)103/25/402021/25/4x6(1)000100101x1(2)01-1/23/40-

39、2015/23/4x4(3)00211-24061注：選取j 0中下標(biāo)最小的非基變量xk 為換入變量經(jīng)過幾次迭代后會出現(xiàn)循環(huán)運(yùn)籌學(xué)史慧萍582022-3-25BVEq系 數(shù)右邊-zx1x2x3x4x5x6x7-z(0)1000-3/420-1/260 x1(1)01001/4-8-190 x2(2)00101/2-12-1/230 x3(3)000100101BVEq-zx1x2x3x4x5x6x7-z(0)13000-4-7/2330 x4(1)04001-32-4360 x2(2)0-210043/2-150 x3(3)000100101遵循勃蘭特規(guī)則：選取j 0中下標(biāo)最小的非基變量xk

40、為換入變量。避免循環(huán)出現(xiàn)。7 , 6 , 5 , 4 , 3 , 2 , 1, 01 035 . 0125 . 0 09 825. 0 65 . 02075. 0 6376542765417654jxxxxxxxxxxxxxstxxxxzminj運(yùn)籌學(xué)史慧萍592022-3-25BVEq-zx1x2x3x4x5x6x7-z(0)111000-2180 x4(1)0-1280108-840 x5(2)0-1/21/40013/8-15/40 x3(3)000100101BVEq-zx1x2x3x4x5x6x7-z(0)1-2301/400-30 x6(1)0-3/2101/801-21/20 x

41、5(2)01/16-1/80-3/64103/160 x3(3)03/2-11-1/80021/21選取j 0中下標(biāo)最小的非基變量xk 為換入變量運(yùn)籌學(xué)史慧萍602022-3-25BVEq-zx1x2x3x4x5x6x7-z(0)10-10-5/432030 x6(1)00-20-1241-60 x1(2)01-20-3/416030 x3(3)00211-24061BVEq-zx1x2x3x4x5x6x7-z(0)1001/2-3/420061/2x6(1)000100101x1(2)01011/4-8091x2(3)0011/21/2-12031/2選取j 0中下標(biāo)最小的非基變量xk 為換

42、入變量運(yùn)籌學(xué)史慧萍612022-3-25BVEq-zx1x2x3x4x5x6x7-z(0)103/25/402021/25/4x6(1)000100101x1(2)01-1/23/40-2015/23/4x4(3)00211-24061注：退化基本可行解中的非零分量個數(shù)一定小于m,非退化解中的非零分量個數(shù)一定等于m。 運(yùn)籌學(xué)史慧萍622022-3-25例：單純形法運(yùn)籌學(xué)史慧萍632022-3-25(2)無窮多最優(yōu)解BVEqzx1x2x3x4右邊比值z(0)1-1-1000 x3(1)01-11011x4(2)01101220,21-. . 21212121xxxxxxtsxxzmax解線性規(guī)劃

43、問題運(yùn)籌學(xué)史慧萍642022-3-25BVEqzx1x2x3x4右邊比值z(0)10-2101x1(1)01-1101x4(2)002-1111/2BVEqzx1x2x3x4右邊比值z(0)100012x1(1)0101/21/23/23x2(2)001-1/21/21/2檢驗數(shù)i0，故是最優(yōu)解。最優(yōu)解：x(1)=(3/2，1/2） x(2)=(0，2），最優(yōu)值為2。運(yùn)籌學(xué)史慧萍652022-3-25BVEqzx1x2x3x4右邊z(0)100012x3(1)020113x2(2)011012最優(yōu)解：x(1)=(3/2，1/2） x(2)=(0，2）)232,23()2,0)(1 ()21,2

44、3(10)1 ()2()1(xxx是最優(yōu)解檢驗數(shù)中非基變量的系數(shù)中有零,可能存在無窮多最優(yōu)解右邊的值與上步單純形法結(jié)果相比一樣運(yùn)籌學(xué)史慧萍662022-3-25當(dāng)所有檢驗數(shù)均小于或等于零且某個非基變量的檢驗數(shù)等于零并且對應(yīng)變量的系數(shù)中有正數(shù)，則表明該線性規(guī)劃問題有無窮多最優(yōu)解；運(yùn)籌學(xué)史慧萍672022-3-25運(yùn)籌學(xué)史慧萍682022-3-25（3）無界解用單純形法求解下列線性規(guī)劃問題：0,82442.42121212121xxxxxxxxtsxxz max運(yùn)籌學(xué)史慧萍692022-3-25BVEqzx1x2x3x4x5右邊比值z（0）1-4-10000 x3(1)0-111002-x4(2)

45、01-401044x5(3)01-200188（0）10-1704016x3(1)00-31106-x1(2)01-40104-x5(3)0020-1142（0）1000-9/217/250 x3(1)0001-1/23/212x1(2)0100-1212x2(3)0010-1/21/22 存在j0, 但此時迭代中無換出變量，則目標(biāo)函數(shù)值可任意大。0,82442.42121212121xxxxxxxxtsxxz max運(yùn)籌學(xué)史慧萍702022-3-25-x1+x2=2x1-4x2=4x1-2x2=8x1x2無界解0248可行域0,82442. .42121212121xxxxxxxxtsxxz

46、 max運(yùn)籌學(xué)史慧萍712022-3-25從兩次迭代的單純形表中，得到約束方程組：5425415435425415432121221223211222121122122321xxxxxxxxxxxxxxxxxx02/1122/12120,5432154xMxMxMxMxxMx，可得一組解：令經(jīng)驗證，該組解是可行解，此時目標(biāo)函數(shù)z=4x1+x2=50+4.5M由于M可以是任意大的正數(shù)，因此目標(biāo)函數(shù)值無界解。0,82442.42121212121xxxxxxxxtsxxz max線性規(guī)劃問題運(yùn)籌學(xué)史慧萍722022-3-25無界解線性規(guī)劃的軟件實現(xiàn)過程如果存在某個正的檢驗數(shù)，而相應(yīng)變量的系數(shù)中沒有

47、正數(shù)，則表明該線性規(guī)劃問題有無界解。運(yùn)籌學(xué)史慧萍732022-3-25（4）無可行解0, 050531823122 4 .53max2121212121xxxxxxxxtsxxz運(yùn)籌學(xué)史慧萍742022-3-25基變量中含有非零的人工變量。這時無可行解。0,50531823122 4 .532121212121xxxxxxxxtsxxz max運(yùn)籌學(xué)史慧萍752022-3-25n 大大M法法 大大M法首先將線性規(guī)劃問題化為標(biāo)準(zhǔn)型。如果約束方程組中包含法首先將線性規(guī)劃問題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個單位矩陣有一個單位矩陣I，那么已經(jīng)得到了一個初始可行基。否則在約束方，那么已經(jīng)得到了一個

48、初始可行基。否則在約束方程組的左邊加上若干個非負(fù)的人工變量，使人工變量對應(yīng)的系數(shù)列向程組的左邊加上若干個非負(fù)的人工變量，使人工變量對應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個單位矩陣。以單位矩陣為初量與其它變量的系數(shù)列向量共同構(gòu)成一個單位矩陣。以單位矩陣為初始基，即可求得一個初始的基本可行解。始基，即可求得一個初始的基本可行解。 為了求得原問題的初始基本可行解，必須盡快通過迭代過程把人為了求得原問題的初始基本可行解，必須盡快通過迭代過程把人工變量從基變量中替換出來成為非基變量。為此可以在目標(biāo)函數(shù)中賦工變量從基變量中替換出來成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個絕對值很大的負(fù)系

49、數(shù)予人工變量一個絕對值很大的負(fù)系數(shù)-。這樣只要基變量中還存在。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實現(xiàn)極大化。人工變量，目標(biāo)函數(shù)就不可能實現(xiàn)極大化。 以后的計算與單純形表解法相同，只需認(rèn)定是一個很大的正數(shù)以后的計算與單純形表解法相同，只需認(rèn)定是一個很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說明原問即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說明原問題無可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問題的初題無可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問題的初始基本可行解。始基本可行解。運(yùn)籌學(xué)史慧萍762022-3-25用大用大M M法求解下面的線

50、性規(guī)劃問題法求解下面的線性規(guī)劃問題: :解：解： 首先將原問題化為標(biāo)準(zhǔn)型首先將原問題化為標(biāo)準(zhǔn)型 0,3 12 .2212212121xxxxxxxtsxxz max)5 , 4 , 3 , 2 , 1(03 12 .25242132154321jxxxxxxxxxtsxxxxxz maxj)7 , 6 , 5 , 4 , 3 , 2 , 1(03 1 2 .-2-5274216321765432176jxxxxxxxxxxxtsMxMxxxxxxz maxMxxj賦予，并在目標(biāo)函數(shù)中分別，添加人工變量運(yùn)籌學(xué)史慧萍772022-3-25 0 1 -1/2 -1/2 0 1/2 1/23/2x22

51、 1 0 -1/2 1/2 0 1/2 -1/21/2x1-1- -1 1 0 -1 0 0 11x221/2 2 0 -1 1 0 1 -11x6-M1/1 -1 1 0 -1 0 0 11x7-M2/1 1 1 -1 0 0 1 02x6-M 0 0 1/2 3/2 0 -1/2-M -3/2-M5/2Z 0 0 1/2 1/2 1 -1/2 -1/23/2x50 1+2M 0 -M 2+M 0 0 -2-2M2-MZ2/1 1 0 0 1 1 0 -12x50 -1 2+2M -M -M 0 0 0-3MZ3/1 0 1 0 0 1 0 03x50 x1 x2 x3 x4 x5 x6 x

52、7bXBCB比值比值i -1 2 0 0 0 -M -MCj值是怎么得來的？與只在左端加入松弛變量時獲得的標(biāo)準(zhǔn)型有何不同？大M單純形法：運(yùn)籌學(xué)史慧萍782022-3-25最優(yōu)解最優(yōu)解X*=(0,3,1,2,0)T 最優(yōu)值最優(yōu)值Z*=6 0 1 0 0 1 0 03x22 1 0 0 1 1 0 -12x40 1 1 -1 0 0 1 02x22 2 0 -1 1 0 1 -11x40- 0 1 -1/2 -1/2 0 1/2 1/23/2x221/2/1/2 1 0 -1/2 1/2 0 1/2 -1/21/2x1-1 -1 0 0 0 -2 -M -M6Z -1 0 1 0 1 -1 01x

53、30 -3 0 2 0 0 -2-M -M4Z -1 0 1 0 1 -1 01x50 0 0 1/2 3/2 0 -1/2-M -3/2-M5/2Z3/2 /1/2 0 0 1/2 1/2 1 -1/2 -1/23/2x50 x1 x2 x3 x4 x5 x6 x7bXBCB比值比值i -1 2 0 0 0 -M -MC運(yùn)籌學(xué)史慧萍792022-3-25檢驗準(zhǔn)則(適用于無人工變量的問題)（目標(biāo)準(zhǔn)則：最大值；判斷系數(shù)：為cj-zj）(注：與課件代數(shù)法一致P47，但與課件P52的判斷系數(shù)正好相反)n (1)當(dāng)所有檢驗數(shù)均小于或等于零時，表明現(xiàn)有頂點(diǎn)(基可行解)即為最優(yōu)解；n (2)當(dāng)所有檢驗數(shù)均小于或等于零且某個非基變量的檢驗數(shù)等于零并且對應(yīng)變量的系數(shù)中有正數(shù)，則表明該線性規(guī)劃問題有無窮多最優(yōu)解；n (3)如果存在某個正的檢驗數(shù)，而相應(yīng)變量的系數(shù)中沒有正數(shù)，則表明該線性規(guī)劃問題有無界解。運(yùn)籌學(xué)史慧萍802022-3-25目標(biāo)函數(shù)為max的線型規(guī)劃問題的單純形法的計算步驟（軟件linear programming (LP)這里檢驗數(shù)規(guī)定為cjzj ，則當(dāng)所有cjzj 0時