第2章 線性規(guī)劃與單純形法

管理運籌學(xué)廣東商學(xué)院工商管理學(xué)院徐輝

第2章

線性規(guī)劃與單純形法本章要求：◎掌握線性規(guī)劃的數(shù)學(xué)模型及其建模步驟．◎掌握線性規(guī)劃的圖解法．◎認識線性規(guī)劃的標(biāo)準(zhǔn)型，掌握轉(zhuǎn)化為標(biāo)準(zhǔn)

型的方法．◎掌握單純形法與單純形表；掌握人工變量

方法的使用．線性規(guī)劃（LinearProgramming．簡記為LP）是運籌學(xué)的一個重要部分，是運籌學(xué)中研究較早，發(fā)展較快，理論上比較成熟和應(yīng)用上極為廣泛的一個部分，它已成為幫助各級管理人員進行決策的一種十分重要的工具．傳統(tǒng)的管理只注重定性分析，已遠遠不能適應(yīng)當(dāng)今社會發(fā)展的需要．現(xiàn)代化管理要求采用定性分析和定量分析相結(jié)合的方法，一切管理工作要力求做到定量化、最優(yōu)化，于是就產(chǎn)生了各種各樣的管理優(yōu)化技術(shù)．在諸多的管理優(yōu)化技術(shù)中，線性規(guī)劃是目前最常用而又最為成功的一種．其原因有三：一是應(yīng)用廣泛．管理工作中的大量優(yōu)化問題可以用線性規(guī)劃的模型來表達；二是模型較為簡單，容易建立，容易學(xué)習(xí)和掌握；三是求解方法和理論基礎(chǔ)較為成熟．1939年前蘇聯(lián)數(shù)學(xué)家康托洛維奇（L．V．Kantrovich）在《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》一書中，首次提出了線性規(guī)劃問題，成為最早研究這方面的問題學(xué)者．線性規(guī)劃是數(shù)學(xué)規(guī)劃問題中的一種．以后我們會看到，還有所謂整數(shù)規(guī)劃、非線性規(guī)劃等．這里的規(guī)劃（Programming）是指計劃的意思．在規(guī)劃前面冠以“線性”二字，則是因為這類規(guī)劃問題的數(shù)學(xué)模型是線性的數(shù)學(xué)表達式．一個實際問題的數(shù)學(xué)模型，是依據(jù)客觀規(guī)律，對該問題中我們所關(guān)心的那些變量進行科學(xué)的分析后所得出的反映這些量之間本質(zhì)聯(lián)系的數(shù)學(xué)關(guān)系式．但一般說來，我們在工業(yè)、農(nóng)業(yè)、交通運輸、國防等方面所遇到的實際問題是很復(fù)雜的，它們涉及的因素很多，要想建立包羅各種因素的數(shù)學(xué)模型，不僅不可能（因有的數(shù)量關(guān)系根本無法弄清楚），也沒有必要．到1947年，美國學(xué)者丹捷格（G.B.Dantzig）提出了線性規(guī)劃問題的一般解法——單純形法，為線性規(guī)劃的理論發(fā)展奠定了基礎(chǔ)，尤其是1979年哈奇安首次提出求解線性規(guī)劃問題的一個多項式算法——橢球算法．1984年卡瑪卡（N.Karmarkar）提出了解線性規(guī)劃問題的一個更為有效的一種新的內(nèi)點算法，使得線性規(guī)劃的理論發(fā)展趨于成熟．60多年來，隨著電子計算機的發(fā)展，線性規(guī)劃已廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸、經(jīng)濟管理和國防等各個領(lǐng)域，成為現(xiàn)代化管理的有力工具之一．§2.1什么是線性規(guī)劃一個可行的辦法是擇其主要者，加以討論之．雖然，一般說來，模型粗一點，它不太精確，而模型細一點，對實際事物的描述要準(zhǔn)確一些，但后者帶來的問題是：或者在理論上難以處理，或者在計算時工作量太大，耗費昂貴．所以，應(yīng)根據(jù)實際問題的具體情況，抓住主要矛盾，來建立既能保證精確度要求，又盡量簡單的數(shù)學(xué)模型．實際的線性規(guī)劃問題一般都很復(fù)雜，為了使讀者易于掌握建立線性規(guī)劃模型的方法，開始我們所選的例子都經(jīng)過了大大簡化，只要弄懂了這些簡單的模型，今后遇到較為復(fù)雜的問題也就有辦法了．在生產(chǎn)實踐中，任何一個企業(yè)可供利用的資源（如人力、物力、財力等）是有限的。如何運用現(xiàn)有的資源安排生產(chǎn)，使產(chǎn)值最大或利潤最高；或者，對于給定的任務(wù)，如何統(tǒng)籌安排以便消耗最少的資源．這是一個問題的兩個方面，就是尋找在一定條件下，使某個指標(biāo)達到最優(yōu)的問題。根據(jù)實際問題的要求，可以建立線性規(guī)劃問題數(shù)學(xué)模型來解決這類問題，而建立線性規(guī)劃數(shù)學(xué)模型則是用線性規(guī)劃解決問題時最基本的步驟．線性規(guī)劃問題由目標(biāo)函數(shù)、約束條件以及變量的非負約束三部分組成．下面我們通過管理實踐中的兩個具體實例來說明這類問題，并建立它們的數(shù)學(xué)模型．

產(chǎn)品單位消耗原料AB原料限制（噸）鋼124鐵408橡膠046單位產(chǎn)品利潤（萬元）23一、線性規(guī)劃問題的具體實例例2.1生產(chǎn)計劃問題某工廠計劃在下一個生產(chǎn)周期內(nèi)用鋼、鐵、橡膠三種原料生產(chǎn)A、B兩種產(chǎn)品，其有關(guān)資料見表2.1.問該工廠在下一周期內(nèi)應(yīng)如何安排生產(chǎn)計劃，使得既能充分利用現(xiàn)有原料，又使總利潤最大？解：這里所說的生產(chǎn)計劃問題是指要制定出兩種產(chǎn)品的產(chǎn)量．顯然，可行的生產(chǎn)計劃是很多的，比如可以只生產(chǎn)A型產(chǎn)品，也可只生產(chǎn)B型產(chǎn)品，也可兩種產(chǎn)品都生產(chǎn)．通常一個企業(yè)的生產(chǎn)中有多種不同的產(chǎn)品組合，而每一種產(chǎn)品組合又有大量的不同的數(shù)量組合．每個這樣的組合都是一個生產(chǎn)計劃．要從這許許多多個（有時甚至是無窮多個）生產(chǎn)計劃中確定出哪個是最優(yōu)的（既是企業(yè)獲利最多的），這是個非常困難的問題，傳統(tǒng)的經(jīng)濟分析方法在此無能為力．現(xiàn)在我們我們看看這里是怎樣解決這個問題的．第一步，選定決策變量，即決策人可控制的因素．確定合適的決策變量是能否成功地建立數(shù)學(xué)模型的關(guān)鍵．本例中，可令決策變量x1

,x2

分別表示下一生產(chǎn)周期A、B兩種產(chǎn)品的產(chǎn)量．第二步，確定問題的目標(biāo)，即決策人用來評價問題的不同方案優(yōu)劣的標(biāo)準(zhǔn)．這種目標(biāo)總是決策變量的函數(shù)，稱為目標(biāo)函數(shù)．本例中，用來表示總利潤，目標(biāo)函數(shù)就是使總利潤達到最大．我們用“Max”（是“maximize”的省略寫）表示“最大”，于是得到目標(biāo)函數(shù)第三步，根據(jù)選定決策變量給出限制條件，稱為約束條件．是用來描述完成目標(biāo)，決策變量受到各種限制的等式或不等式．本例中，為了完成目標(biāo)總利潤最大，根據(jù)選定決策變量，由于原料鋼、鐵、橡膠都是有限的，故決策變量x1

,x2

必須滿足下列條件：另外，根據(jù)實際問題的需要和計算方面的考慮，還對決策變量x1

,x2

加上非負限制，即

綜上所述，我們將例2.1的實際問題用數(shù)學(xué)模型描述成：求x1,x2使得

其中，“s.t.”是“subjectto（受約束于）”的省寫．這類問題通常稱為生產(chǎn)計劃問題．

產(chǎn)品單位消耗原料B1,B2,…,Bn

原料限制（噸）A1A2?Ama11a12…a1na21a22…a2n???am1am2…amnb1b2?bm單位利潤（萬元）c1c2…cn而“生產(chǎn)計劃問題”的一般提法是：

某廠計劃在下一個生產(chǎn)周期內(nèi)用A1,A2,…,Am種原料去生產(chǎn)B1,B2,…,Bn種產(chǎn)品，已知其現(xiàn)有原料的數(shù)量和單位產(chǎn)品的原料消耗及其單位產(chǎn)品的利潤見表2.2所示：

問該工廠應(yīng)如何安排生產(chǎn)計劃，使得既能充分利用現(xiàn)有原料，又能使總利潤最大？設(shè)決策變量xj表示下一個周期產(chǎn)品Bj(j=1,2,…,n)

的產(chǎn)量，則此問題的數(shù)學(xué)模型可歸結(jié)為：求xj(j=1,2,…,n)，使得

食物含量成份甲乙最低需求量（兩）A10．100．151．00A21．700．757．50A31．101．3010．00食物單價（元）21．5例2.2食物搭配問題某人每天食甲、乙兩種食物（如豬肉、雞蛋），這兩種食物含A1,A2,A3三種營養(yǎng)成分（如維生素、脂肪和蛋白質(zhì)），已知這兩種食物所含三種營養(yǎng)成分的含量（mg），人體每天對這三種營養(yǎng)成分的需求量及這兩種食物的單價（元/兩）如表2.3所示，問此人對這兩種食物各食用多少，才能既滿足營養(yǎng)需要又使總花費用最省？解：設(shè)決策變量x1

,x2分別表示此人對甲、乙兩種食物的食用量，這必須要求此人一天的食用花費盡可能的最省，即目標(biāo)函數(shù)為：

同時，為了營養(yǎng)需要，變量x1,x2

必須滿足下列約束條件：設(shè)決策變量xj(j=1,2,…,n)分別表示此人對這n種食物的食用量，則問題的線性規(guī)劃模型表示為：求xj(j=1,2,…,n)，使得綜合以上，其數(shù)學(xué)模型表示為這類問題通常稱為食物搭配問題．具備以上三個共同特點的數(shù)學(xué)模型稱為線性規(guī)劃模型，相應(yīng)的問題叫做線性規(guī)劃問題．以后我們把“線性規(guī)劃”簡寫“LP”，它是LinearProgramming的縮寫．簡單地說，線性規(guī)劃問題就是求一個線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題，線性規(guī)劃的數(shù)學(xué)模型分一般形式和標(biāo)準(zhǔn)形式兩種，下面分別介紹，并討論它們之間的轉(zhuǎn)化．而“食物搭配問題”的一般提法是：某人每天食用n種食物B1,B2,…,Bn，這n種食物中含A1,A2,…,Amm種營養(yǎng)成分，已知這n種食物中所含m種營養(yǎng)成分的含量、人體每天對這m種營養(yǎng)成分的需求量及這m種食物的單價（元/兩）如表2.4所示，問此人對這m種食物各食用多少，才能既滿足需要又使總費用最??？

食物含量成份B1,B2,…,Bn

最低需求量（兩）A1A2?Ama11a12…a1na21a22…a2n???am1am2…amnb1b2?bm食物單元（元）c1c2…cn

二、線性規(guī)劃問題的數(shù)學(xué)模型上面我們從經(jīng)濟管理領(lǐng)域中建立了兩個實際問題的數(shù)學(xué)模型，這兩個問題雖然具體意義各不相同，但從數(shù)學(xué)模型來看，它們卻有一些共同的特點，主要表現(xiàn)在：第一，求一組決策變量(decisionvariables)xj(j=1,2,…,n)，一般這些變量取值是非負的；第二，確定決策變量可能受到的約束，稱為約束條件（constraints），它們可以用決策變量的線性等式或不等式來表示；第三，在滿足約束條件的前提下，使某個函數(shù)值達到最大（如利潤、收益等）或最?。ㄈ绯杀尽⑦\價、消費等），這種函數(shù)稱為目標(biāo)函數(shù)(objectivefunction)，它是決策變量的線性函數(shù)．1.線性規(guī)劃問題的一般形式由以上兩個例子，我們可以歸納出線性規(guī)劃問題的一般形式是：求一組決策變量xj(j=1,2,…,n)使得(2.1)其中cj,aij,bi(i=1,2,…,n)均為已知實常數(shù)．式(2.1)稱為目標(biāo)函數(shù)，式(2.2)和(2.3)稱為約束條件,特別稱式(2.3)為非負約束條件．在線性規(guī)劃問題中，目標(biāo)函數(shù)是變量的線性函數(shù)，約束條件是變量的線性不等式．例如以下的問題就不是線性規(guī)劃問題：

2.線性規(guī)劃問題的標(biāo)準(zhǔn)形式為了便于討論一般解法，常將線性規(guī)劃問題的約束條件歸結(jié)為一組方程和一組非負限制條件，并且對目標(biāo)函數(shù)統(tǒng)一成求最大值，稱之為線性規(guī)劃問題的標(biāo)準(zhǔn)形式：(2.4)(LP)并且假設(shè)bi≥0(i=1,2,…,m)

，并簡稱為(LP)問題．(LP)問題還可以用以下幾種形式來表示：(1)簡記形式(2)矩陣形式

(3)向量形式

其中A=(aij)m×n,C=(c1,C2,…,Cn)，為行向量，X=(x1,x2,…,xn)T為列向量，b=(b1,b2,…,bm)T為列向量．我們稱為約束條件的系數(shù)矩陣，簡稱為約束矩陣，經(jīng)濟上又稱為技術(shù)矩陣；cj(j=1,2,…,n)為目標(biāo)函數(shù)的系數(shù)，又稱為價值系數(shù)，為價值向量；bi(i=1,2,…,m)為第i個約束條件的右端常數(shù)，b為右端向量，經(jīng)濟上又稱為資源向量；xj(j=1,2,…,n)為決策變量，X為決策向量；pj(j=1,2,…,n)

為A的第j列向量．線性規(guī)劃問題的標(biāo)準(zhǔn)形式具有如下特征：（1）目標(biāo)函數(shù)為求極大值問題；（2）所有的約束條件（除非負約束條件外）都是等式，且右端常數(shù)均為非負；（3）所有的決策變量均非負．為了使得我們的討論能夠抓住最主要的內(nèi)容，而不致被一些次要的枝節(jié)問題攪亂視線，我們在這里對標(biāo)準(zhǔn)形式的(LP)問題做如下假設(shè)：①秩r(A)=m，且m<n．這就是說，方程組(2.5)中的包含的m個方程式都是彼此獨立的，沒有多余方程，且方程個數(shù)小于未知量個數(shù)．這種情況最為常見．若r(A)<m，則說明(2.5)中有多余方程．這時應(yīng)先去掉多余方程，然后再行求解．②b≥0，即一切bi≥0(i=1,2,…,m)(若有某個bi<0，則可將bi<0所在方程的兩邊乘以-1)．今后，我們將在以上假設(shè)條件下去討論標(biāo)準(zhǔn)形式的(LP)問題．對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下的變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式．3.線性規(guī)劃問題的非標(biāo)準(zhǔn)形轉(zhuǎn)化為標(biāo)準(zhǔn)形將非標(biāo)準(zhǔn)形的線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)形，一般要經(jīng)過以下幾步工作：（1）目標(biāo)函數(shù)的轉(zhuǎn)化若目標(biāo)函數(shù)為求極小值，即為由于MinZ=-Max(-Z)，從而將目標(biāo)函數(shù)轉(zhuǎn)化成（2）約束條件的轉(zhuǎn)化約束方程為不等式時，當(dāng)約束條件為“≤”時，則在其左邊加一個非負變量，將不等式轉(zhuǎn)化為等式．這些被加入的非負變量稱為松弛變量（slackvariables）；當(dāng)約束條件為“≥”時，則在其左邊減去一個非負變量，也稱為松弛變量（或叫剩余變量），將不等式變成等式．由于加進的松弛變量，其物理意義是未被充分利用的資源或處于閑置的資源，因而不能帶來價值或利潤，故它們在目標(biāo)函數(shù)里的系數(shù)定為零．如果約束條件右端的常數(shù)項為負數(shù)，則將約束條件兩邊同乘-1，從而將右端常數(shù)項變?yōu)檎龜?shù)．（3）決策變量的轉(zhuǎn)化若存在某個決策變量xk≤

0，則可令xk=-x’k，從而用x’k

取代xk，且滿足x’k≥

0．如果某決策變量xk為無約束變量，即變量xk取≥

0或≤

0皆可，為了滿足標(biāo)準(zhǔn)型對變量的非負要求，可令xk=x’k-x”k

，其中x’k≥

0，x”k≥

0，將其代入模型即可．例2.3將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)型解：分下面幾步進行：

（1）由于x2≤0，可令x’2=-x2≥0代入(2.16)、(2.17)、(2.18)、(2.19)；（2）由于x3無約束，可令x3=x’3-x”3(x’3≥0,x”3≥0)代入(2.16)、(2.17)、(2.18)、(2.19)中的x3均替換成x’3-x”3；（3）在式(2.17)的左邊加一個非負的松弛變量x4；（4）在式(2.18)的左邊減一個非負的松弛變量x5；（5）對式(2.19)兩邊同乘-1；（6）令Z’=-Z，并將目標(biāo)函數(shù)中各變量的系數(shù)均變成其相反數(shù)，從而將目標(biāo)函數(shù)轉(zhuǎn)為MaxZ’；（7）令松弛變量在目標(biāo)函數(shù)中的價值系數(shù)為零．經(jīng)過以上變換，得該問題的標(biāo)準(zhǔn)形為：§2.2求解線性規(guī)劃問題

的基本原理闡述這個問題之前，我們先來介紹兩個基本概念．對于線性規(guī)劃問題的標(biāo)準(zhǔn)形定義2.1在(LP)問題中，凡滿足所有約束條件（2.11）和（2.12）的解X=(x1,x2,…,xn)T稱為(LP)問題可行解（FeasibleSolution），所有可行解的集合稱為可行域（FeasibleRegion）（或可行解集），記作S={X|AX=b,X≥

0}．定義2.2設(shè)(LP)問題的可行域為S，若存在X*∈S,使得對于任意的X∈S，都有CX*≥CX,則稱X*為(LP)問題的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，記作Z*，即Z*=CX*．對于給定的(LP)問題，若存在最優(yōu)解，則稱它有解，否則稱之為無解．將(LP)問題的每一個可行解代入目標(biāo)函數(shù)Z的表達式中，就可以得到的一個相應(yīng)的值．一般說來，不同的X對應(yīng)于不同的Z．求解線性規(guī)劃問題的根本任務(wù)就是要在全部可行解中找出使目標(biāo)函數(shù)取最大或最?。ńy(tǒng)稱最優(yōu)值）的那個（或那些）可行解，即最優(yōu)解．因為在約束方程組中，m<n，故在一般情況下，可行解集D及其邊界都是無窮點集，相應(yīng)地，也就有無窮多個值．要從這無窮多個值中找出一個最大的或最小的，一般來說是不可能的．然而，值得慶幸的是，由于(LP)問題的結(jié)構(gòu)特殊，其可行解集具有一些“很好”的性質(zhì)（后面將給出），從而實現(xiàn)一個從無限到有限的轉(zhuǎn)化，即從對無窮多個函數(shù)值的比較，轉(zhuǎn)化為只需考慮有限多個函數(shù)值的情形．下面，我們先從圖解法來領(lǐng)會上述思想．一、圖解法對于只有兩個變量的線性規(guī)劃問題，我們可以用在二維直角坐標(biāo)平面上作圖的方法求解，這種方法稱為圖解法．圖解法比較簡單、直觀，對所給問題也無需化成標(biāo)準(zhǔn)形．圖解法的步驟可概括為：在平面上建立直角坐標(biāo)系；圖示約束條件，找出可行域；作出目標(biāo)函數(shù)線；尋找最優(yōu)解．下面通過實例來說明圖解法．例2.4用圖解法求解例2.1．例2.1的數(shù)學(xué)模型是：解：畫出坐標(biāo)系．以變量x1為橫坐標(biāo)軸，x2為縱坐標(biāo)軸作平面直角坐標(biāo)系，并適當(dāng)選取單位坐標(biāo)長度．約束條件（2.25）規(guī)定了變量只能在第一象限取值，所以繪圖時第一象限占較大版面．圖示約束條件，找出可行域．約束條件（2.22）是一個不等式，代表的是以直線x1+2x2=4為邊界的左下方的平面，同理分析（2.23）、（2.24）后，加上（2.25），則滿足所有約束條件的解（即可行解）組成的區(qū)域為多邊形OQ4Q3Q2Q1，這一區(qū)域稱之為可行域，見圖2.1，可行域用陰影表示．圖2.1作出目標(biāo)函數(shù)等值線．目標(biāo)函數(shù)Z=2x1+3x2中，z是待定的值，隨z的變化，x2=-3/2x1+1/2z是以z為參數(shù)、斜率為-3/2的一族平行線，當(dāng)z值由小變大時，得一族平行線，即目標(biāo)函數(shù)等值線．直線x2=-2/3x1+1/3z(z為參數(shù))沿其法線方向向右上方移動時，離O點越遠，z值越大．確定最優(yōu)解．因最優(yōu)解是可行域中使目標(biāo)函數(shù)值達到最大的點，因此x1、x2的取值范圍只能從凸多邊形OQ1Q2Q3Q4中去尋找．從圖2.1中可以看出，當(dāng)代表目標(biāo)函數(shù)的那條直線由O點開始向右上方移動時，的值逐漸增大，一直移動到當(dāng)目標(biāo)函數(shù)直線與約束條件包圍成的凸多邊形相切時為止，切點就是最優(yōu)解的點．本例中目標(biāo)函數(shù)直線與凸多邊形的切點是Q2，該點坐標(biāo)為．于是可得Z*=2×2+3×1=7．這說明該企業(yè)的最優(yōu)生產(chǎn)計劃方案是：生產(chǎn)產(chǎn)品A為2噸，生產(chǎn)產(chǎn)品為1噸，可使最大總利潤達7萬元．由例2.4可以看出，線性規(guī)劃問題的最優(yōu)解將出現(xiàn)在可行域的一個頂點上，這是線性規(guī)劃問題有唯一最優(yōu)解的情況．但對于一般線性規(guī)劃問題，求解結(jié)果還可能出現(xiàn)以下幾種情況：1．唯一解．如例2.4得到的最優(yōu)解(2,1)就是唯一解．2．多重解．如果將例2.4的目標(biāo)函數(shù)改變?yōu)镸axz=2x1+4x2，則目標(biāo)函數(shù)的直線族恰好與約束條件x1+x2≤4的邊界線平行．當(dāng)目標(biāo)函數(shù)向優(yōu)化方向移動時，與可行域相切的不是一個點，而是在整個線段Q2Q3上相切（見圖2.2）．這時線段Q2Q3上的任意點都使z取得相同的最大值，即該線性規(guī)劃問題有無窮多最優(yōu)解，也稱為有多重解．這些點都是最優(yōu)解．(2.26)圖2.2圖2.2中，Q2

和Q3

的坐標(biāo)分別是(2,1)、(1,3/2)，則Q2Q3

連線上的一切點可表示成3．無界解．如果將例2.4的約束條件進行修改后成如下線性規(guī)劃模型則此時可行域可伸展到無窮遠處，即z的取值可以一直增大到無窮大（見圖2.3）．這種情況下問題的最優(yōu)解無界，稱為取得無界解．產(chǎn)生無界解的原因是在建立實際問題的數(shù)學(xué)模型時，可能遺漏了某些必要的資源約束條件．圖2.34．無可行解．考察如下線性規(guī)劃模型用圖解法求解時，可以看出不存在滿足所有約束條件的公共區(qū)域（可行域），見圖2.4，我們稱這種情況為線性規(guī)劃問題無可行解．產(chǎn)生無可行解的原因是模型中存在相互之間矛盾的約束條件．圖2.4通過用圖解法求解只有兩個變量的(LP)問題，我們可以獲得某些解一般(LP)問題的重要規(guī)律，主要有以下三點：第一，關(guān)于解的存在性問題．在求解線性規(guī)劃問題時，解的情況有：唯一解、多重解、無界解、無可行解四種情況．何時有解？何時無解？何時有多重解？何時無可行解？這些問題在我們學(xué)習(xí)了單純形法以后，大體上可以得到解決；第二，關(guān)于可行解集的結(jié)構(gòu)問題．從二維情形可見，可行解集的圖形它總是向外凸的．這種無論在線性規(guī)劃的有界集情形，還是無界集情形所表現(xiàn)出來的可行解集的凸性是線性規(guī)劃的一個基本特性；第三，關(guān)于最優(yōu)解的獲得方法問題．如果線性規(guī)劃問題有唯一最優(yōu)解，則其最優(yōu)解一定在可行域的某個“頂點”得到．如果線性規(guī)劃問題存在多重最優(yōu)解，則有兩個頂點及其連線上的一切點均取得最優(yōu)解．第一點已很顯然，對于第二、第三點，下面將給出證明．

二、關(guān)于線性規(guī)劃問題求解的一些基本定理要從無窮多個可行解中找出最優(yōu)解來，是一件非常困難的工作．此問題的解決建立在一系列重要定理的基礎(chǔ)上．我們將從上節(jié)獲得的幾何啟示出發(fā)，逐步展開這些基本定理．這樣，讀者便能從中更好地領(lǐng)會到單純形法產(chǎn)生的整個思路．首先，我們介紹兩個基本概念．定義2.3設(shè)E?R2．若中任意兩點x(1)和x(2)的連線上的一切點仍屬于E，即若x(1)∈E,x(2)∈E

，就必有x=αx(1)+(1-α)x(2)∈E(其中0≤α≤1)，則稱E為凸集（convexpoint-set）．例如三角形、矩形、四面體、實心圓、實心球等都是凸集，而圓環(huán)、圓周不是凸集．圖2.5中點集D，E是凸集，F(xiàn)，G不是凸集．圖2.5定義2.4若對于凸集E中的點，不存在經(jīng)E中兩個相異的點x(1)和x(2)

，使下式成立：則稱x為E的極點（extremepoint）或頂點．如三角形、矩形、四面體的頂點，圓周上的一切點都是這些圖形各自的極點．圖2.5中D的邊界點都是極點，E的5個頂點也都是極點．現(xiàn)在我們來討論求解LP問題的一系列基本定理．在本節(jié)今后對LP問題作一般性的理論分析中，我們都假定LP問題為標(biāo)準(zhǔn)形式，這點以后不再聲明．約束方程Ax=b可改寫成如下形式：其中，稱xj為的系數(shù)列向量．定理2.1線性規(guī)劃問題的可行解集（若非空）是凸集．證：按凸集定義，要證可行解集S中任意兩點x(1)

和x(2)

連線上的一切點

仍屬于S，亦即要證x仍為可行解．一方面，因x(1)≥0，x(2)≥0，且0≤α≤1，所以，顯然有x≥0，即

x滿足非負條件．另一方面，由于Ax(1)=b,Ax(1)=b

故有即x滿足約束方程．綜上，x仍為可行解，證畢．從前面的圖解法中，我們看到極點在求解LP問題中的重要作用，故有必要對其進行仔細研究．下面幾個定理就是關(guān)于極點的有關(guān)結(jié)論，但是由于下面幾個定理的證明稍微有點復(fù)雜，為使讀者首先能集中精力掌握求解LP問題的主要思路，此處只敘述這些定理，而將證明放在本章的最后一節(jié)．讀者在熟悉了單純形法的具體做法后，再去學(xué)習(xí)這些證明，將會很受啟發(fā)．引理2.1設(shè)x∈S,(i)若x=0，則它一定是S的極點．(ii)若x≠0，則它為S之極點的充要條件是x的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)．定理2.2若可行解集非空，則其極點所組成的集合也一定是非空．換句話說，只要存在可行解，就一定存在極點．定理2.3極點的個數(shù)是有限的．定理2.4若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在極點中找到．或者說，若目標(biāo)函數(shù)有最優(yōu)值，則最優(yōu)值必至少在一極點上達到．這些定理之說以極為重要，之說以被稱之為基本定理，是因為它們回答了我們所關(guān)心的一系列重大問題．定理2.1回答的是：“LP問題的可行解集具有什么樣的幾何特征？”答曰：是個凸集．既然是凸集，便可談及極點．那么，什么樣的點才能稱為極點？引理2.1解決了這一問題．接著要問：“怎樣的可行解集才能有極點呢？”定理2.2做了回答：只要s≠Φ它就有極點．這一定理指出了極點存在的普遍性．進一步要問：“極點的個數(shù)有多少呢？”定理2.3的回答是：有限個．這一回答雖不具體，卻是原則性的，聯(lián)系定理2.4便可知其意義重大．最后一個定理（定理2.4）解決的是“極點與最優(yōu)解究竟有何關(guān)系？”答曰：極點中就有最優(yōu)解．因此，我們要想找出最優(yōu)解，只需考察各個極點（它們是有限個）即可，而不必在整個可行解集或其邊界所包含的無窮多個點中一一檢查了．為了給出尋找極點的具體方法，我們再從求解方程組的角度討論幾個概念．

三、基、基解和基可行解設(shè)一般線性規(guī)劃問題的標(biāo)準(zhǔn)形為考察由約束方程的系數(shù)矩陣A的全部列向量構(gòu)成的向量組P={p1,p2,…,pn}．因r(A)=m，所以，P的極大無關(guān)組含有m個線性無關(guān)的向量．由引理2.1，可知中的線性無關(guān)向量對確定極點起很重要的作用．為此，引進如下的定義．定義2.5在問題(LP)中，約束方程組（2.28）的系數(shù)矩陣A的任意一個m×m階的非奇異的子方陣B（即|B|≠0又稱滿秩矩陣），稱為線性規(guī)劃問題的一個基（basis）或基矩陣（basismatrix）．這就是說，基矩陣B是由矩陣A中任一m個線性無關(guān)的列向量組成，不失一般性，可設(shè)并稱pi(i=1,2,…,m)為基向量，與基向量pi相應(yīng)的變量xi(i=1,2,…,m)為基變量；不在B中的列向量pj(j=m+1,…,n)我們稱為非基向量，與非基向量pj相應(yīng)的變量xj(j=m+1,…,n)為非基變量．并記非基向量則系數(shù)矩陣A可以寫成分塊形式(2.30)將基變量和非基變量組成的向量分別記為

則向量X也可以寫成分塊形式(2.31)再將式（2.30）和（2.31）代入約束方程組（2.28）,得即又因為B是非奇異方陣，所以B-1存在，將上式兩邊同乘B-1，移項后得(2.32)這里可將XN看作一組自由變量（又稱獨立變量），給它們?nèi)我庖唤M值，則由上式（2.32）可得對應(yīng)的XB的一組值，于是便是約束方程（2.28）的一個解。特別地，令時，則，我們把約束方程組的這種特殊形式的解(2.33)稱為基解，具體定義如下：定義2.6在約束方程（2.28）中，對于任意選定的基B，令所有的非基變量等于零，即XN=0，得到的解（2.33）稱為相應(yīng)的基B的基解（basicsolution）．因為基B是A的一個m×m階的非奇異方陣，即它的列是從A的n列中選出的線性無關(guān)的m列，其選法最多共有

種，故基的個數(shù)最多是個，于是一個線性規(guī)劃問題的基解最多也是個．基解滿足約束方程組（2.28），但不一定滿足非負約束條件（2.29），于是又有下面的定義．定義2.7在基解（2.33）中，若XB=B-1b≥

0，則稱此基解稱為一基個可行解（basicfeasiblesolution）．這時對應(yīng)的基B稱為可行基（feasiblebasic）．顯然，一個線性規(guī)劃問題的基可行解的個數(shù)最多也不會超過個．另外，由于矩陣A的秩為m，故對于選定的可行基B，基變量共有m個，非基變量共有n-m個，對應(yīng)的基可行解中非零分量的個數(shù)至多為m個，如果非零分量個數(shù)等于m(即所有基變量取值均為正)，則稱該基可行解為非退化的基可行解

（nondegenerationbasicfeasiblesolution）；

如果非零分量個數(shù)小于(即存在取零值的基變量)，則稱該基可行解為退化的基可行解（degenerationbasicfeasiblesolution）．根據(jù)以上的分析，我們不加證明地給出以下定理：定理2.5線性規(guī)劃的基可行解就是可行域的極點．由此可知，前面關(guān)于極點的許多結(jié)果都可以轉(zhuǎn)到基可行解上來，比如我們有：只要存在可行解，就一定存在基可行解；基可行解的個數(shù)是有限的；若LP問題有最優(yōu)解，則最優(yōu)解一定可以在基可行解中找到．結(jié)合前面的定理來說，我們有如下重要結(jié)論：LP問題如果有最優(yōu)解，則最優(yōu)解必可在基可行解中找到，而基可行解的個數(shù)是有限的．因此，我們只需要在有限多個基可行解中去尋找最優(yōu)解．下一節(jié)將講到的單純形法，就是根據(jù)這些原理構(gòu)思出來的．§2.3線性規(guī)劃的單純形法線性規(guī)劃的單純形法（SimplexAlgorithm）是求解線性規(guī)劃問題的基本方法之一，這是美國學(xué)者丹捷格(G．B．Dantzig)于1947年提出來的，1953年又對其進行改進，成為改進單純形法．1954年，貝爾(Beale)提出了對偶單純形法，使其單純形法更為完善．大量的實際應(yīng)用表明，這是一種行之有效的方法．從上面的討論可知，若線性規(guī)劃問題有最優(yōu)解，則一定可以在基可行解上達到，單純形法就是建立在這個理論基礎(chǔ)上的．它的基本思想是：首先從可行域中找到一個基可行解，然后判斷它是否為最優(yōu)解，若是則停止計算；否則，就找一個更好的基可行解，再進行檢驗，如此反復(fù)經(jīng)過有限次迭代，直到找到最優(yōu)解，或者判定它無界（即無有限最優(yōu)解）為止．下面，我們通過一個計算實例來說明單純形法的基本原理．一、單純形法的基本原理例2.5求解例2.1．解：先引入松弛變量x3,x4,x5將問題化成標(biāo)準(zhǔn)形：(2.34)第一步：找出初始可行基，確定初始基可行解．約束方程（2.35）的系數(shù)矩陣其中(P3,P4,P5)為一單位矩陣，因而(P3,P4,P5)構(gòu)成一個基，記作同時確定x3,x4,x5為初始基變量，x1,x2為初始非基變量．分別用，表示．將式（2.35）變換后可得(2.37)為使目標(biāo)函數(shù)值增加得快一些，可選擇正系數(shù)中最大的那個非基變量為進基（我們后面將這一規(guī)則稱為“σ規(guī)則”）．由于max{2,3}=3是非基變量x2的系數(shù)，因此確定x2為進基．但基變量的個數(shù)是一定的（等于系數(shù)矩陣A的秩m），于是還要確定從原基變量x3,x4,x5中哪一個換出來作為非基變量（稱為“岀基”）．為此我們進行如下分析．

令x1=x2=0可得初始基可行解這個基可行解表示的經(jīng)濟意義是：工廠沒有安排生產(chǎn)產(chǎn)品A和B，三種資源也沒有被利用，此時，工廠的利潤指標(biāo)Z(0)=0．那么這個解是不是最優(yōu)解呢？第二步：最優(yōu)性檢驗．將式（2.37）代入目標(biāo)函數(shù)式（2.34）內(nèi)可得(2.38)從式（2.38）可知，首先，目標(biāo)函數(shù)中不含基變量x3,x4,x5；其次，非基變量x1,x2的系數(shù)都是正數(shù)，如果將其中一個變量，例如x1（或x2）由非基變量換為基變量（稱為“進基”），則x1（或x2）的取值可以由零變成正值，就會使目標(biāo)函數(shù)的值增大．從而可以斷定初始基可行解x(0)并不是最優(yōu)解．從經(jīng)濟意義上講，安排生產(chǎn)產(chǎn)品A（或B），都可以使工廠的利潤指標(biāo)增加．所以，只要不含基變量的目標(biāo)函數(shù)的表達式（2.38）中有非基變量的系數(shù)為正，就表示目標(biāo)函數(shù)值還有改進可能．第三步：換基迭代．當(dāng)確定了x2作為進基之后，必須要從x3,x4,x5中換出一個作為出基，并保證其余的均為非負．由于x1仍為非基變量，令x1=0，則式（2.37）變成(2.38)分析式（2.38）可知，只有當(dāng)x2的取值不超過min(4/2,-,6/4)=3/2時，才能滿足非負條件．當(dāng)x2=3/2時，最小比值6/4對應(yīng)的基變量x5=0．即x5由基變量變成了非基變量，也就是用x2去替換x5．這一過程稱為“換基”（我們后面將這一規(guī)則稱為“θ規(guī)則”）．從經(jīng)濟意義上講，由于每生產(chǎn)一件產(chǎn)品B，需要耗掉鋼、鐵、橡膠三種原料數(shù)分別為2噸，0噸，4噸，當(dāng)確定生產(chǎn)產(chǎn)品B的產(chǎn)量為3/2件時，則需要消耗鋼、鐵、橡膠三種原料數(shù)分別為3噸，0噸，6噸，這說明原料橡膠已全部用完．因此，由這些原料中的薄弱環(huán)節(jié)橡膠的供應(yīng)量確定了產(chǎn)品B的產(chǎn)量不超過3/2件．這充分體現(xiàn)了岀基的選擇兼顧各種限制條件的思想，所以又稱為最小比值法則．經(jīng)過上述換基以后，新的基變量，新的非基變量為．將當(dāng)前的基變量x3,x4,x2用非基變量x1,x5表示．即將（2.35）式中的x5與x2的位置對調(diào)后，可得式（2.39）可變換成(2.39)(2.40)令x1=x5=0可得將（2.40）代入式（2.34）可得(2.41)從式（2.41）中可知，由于x1前的系數(shù)為2>0，所以X(1)

仍不是最優(yōu)解．且在目標(biāo)函數(shù)（2.41）中，只有非基變量x1的值增加才可以使目標(biāo)函數(shù)值Z增加，選擇非基變量x1為進基，另一個非基變量x5=0保持不變，則式（2.40）變成(2.42)分析式（2.42）可知，只有當(dāng)x1的取值不超過min{1/1,8/4,-}=1時，才能滿足非負條件．此時最小比值1/1對應(yīng)的基變量為x3，這就決定了用x1去替換x3

，將式（2.40）中的x1與x3的位置對調(diào)后，可得令x3=x5=0可得(2.43)將式（2.43）代入式（2.34）可得(2.44)由（2.44）式可知，x5前的系數(shù)為1/4>0，繼續(xù)進行“換基”得新的基可行解而此時目標(biāo)函數(shù)的表達式是(2.45)

由于（2.45）式中所有非基變量x3,x4

的系數(shù)都是負數(shù)，則表示X(3)已是最優(yōu)解．最優(yōu)解中x1=2,x2=1表示A產(chǎn)品生產(chǎn)2個單位，B產(chǎn)品生產(chǎn)1個單位．x3=0,x4=0,x5=2表示原料鋼沒有富余，原料鐵已沒有富余，原料橡膠有富余量2單位．在（2.45）式中，令x3=x4=0,，可得z=7，表示按照最佳生產(chǎn)方案生產(chǎn)可獲最大利潤為7萬元．

對照圖解法，可以很清楚地了解利用單純形算法求解線性規(guī)劃問題所獲得的結(jié)果．初始基可行解X(0)=(0,0,4,8,6)T相當(dāng)于圖2.2中的原點O(0,0)；X(1)=(0,3/2,1,8,0)T相當(dāng)于Q4=(0,3/2)；

X(2)=(1,3/2,0,4,0)T

相當(dāng)于Q3=(1,3/2)；

X(3)=(2,1,0,0,2)T

相當(dāng)于Q2=(2,1)．從初始基可行解X(0)開始迭代，依次得到X(1)

、X(2)

、X(3)

，這相當(dāng)于圖2.2中的目標(biāo)函數(shù)平移時，從O點開始，首先碰到Q4，然后碰到Q3，最后到達Q2．

二、最優(yōu)性檢驗與解的判別一般而言，對已化成標(biāo)準(zhǔn)型式的線性規(guī)劃問題，只要從系數(shù)矩陣中能直接觀察到一個單位矩陣，則即可得到一個初始基可行解，如果不能直接找到單位矩陣，則可通過添加人工變量來求解，這一方法將在本章下一節(jié)中討論．得到初始基可行解后，要檢驗一下是否是最優(yōu)解．如果是，則停止迭代；如果不是，則要繼續(xù)迭代．每次迭代后，都要檢驗一下是否是最優(yōu)解，進一步還要判斷屬于解的哪一種情況，為此，需要建立對解的判別準(zhǔn)則．將式（2.46）代入目標(biāo)函數(shù)(2.46)可得(2.47)一般情況下，經(jīng)過迭代后，有令，式（2.47）變換成再令σj=cj-zj(j=m+1,m+2,…,n)，代入式（2.48）可得(2.48)(2.49)

由于判別基可行解是否為最優(yōu)解，是看其對應(yīng)的目標(biāo)函數(shù)中非基變量xj

前的系數(shù)σj是否均滿足σj≤0(j=m+1,…,n)，因而我們將σj稱為檢驗數(shù)．根據(jù)σj判別各種解的準(zhǔn)則是：（1）最優(yōu)解及唯一解判別準(zhǔn)則：若

X*=(b1’,b2’,…,bm’,0,…,0)T為對應(yīng)于基B的一個基可行解，且對應(yīng)于一切j=m+1,…,n有σj≤0，則X*為最優(yōu)解．如果對一切j=m+1,…,n均有σj<0，則X*為唯一解．（2）多重解判別準(zhǔn)則：若

X*=(b1’,b2’,…,bm’,0,…,0)T為對應(yīng)于基B的一個基可行解，對應(yīng)于一切j=m+1,…,n均有σj≤0

，且σj中至少有一個非基變量的σx滿足σj=0

，則該線性規(guī)劃問題有多重解．（3）無界解判別準(zhǔn)則：若

X(0)=(b1’,b2’,…,bm’,0,…,0)T為一基可行解，且存在一個σk>0

，并且對i=1,2,…,m有a’i,k≤

0

，那么該線性規(guī)劃問題具有無界解．（4）無可行解的判別將在本章下節(jié)進行討論．

三、單純形列表算法

（1）找出初始可行基，確定初始基可行解，建立初始單純形表．

（2）檢查對應(yīng)于非基變量的檢驗數(shù)

，若所有σj≤0，且存在可行解（判別方法在下節(jié)中給出），則已得到最優(yōu)解，停止計算．如果在所有σj>0的σj

中，有一個σK

對應(yīng)于xK

的系數(shù)列向量PK≤0，即對i=1,2,…,m

，均有a’i,K≤0，則此問題有無界解，停止計算；否則轉(zhuǎn)（3）．（3）進行基變換．換入變量的確定采取σ

規(guī)則．令則選擇xK

作為換入變量．換出變量的確定采取θ

規(guī)則．令這里a’lK

為換入變量xK

的系數(shù)列向量中的元素．選擇xl

為換出變量．（4）將a’lK

作為主元素進行旋轉(zhuǎn)運算（即用高斯消去法進行迭代運算），把xK

所對應(yīng)的列向量從而得到一個新的基可行解，重復(fù)（2）~（4），直到終止．前面利用單純形法的基本原理求解線性規(guī)劃問題，其計算過程顯得比較繁瑣，現(xiàn)在我們介紹一種單純形的列表算法，這一方法可以直觀而清楚地表明計算過程．對標(biāo)準(zhǔn)形的線性規(guī)劃問題

不妨設(shè)m×m

階的非奇異方陣B

是(LP)問題的一個基，為討論方便，不妨假設(shè)A=(B，N)，則方程組（2.51）可等價地變換為由于B

是非奇異方陣，故B-1

存在，有XB+B-1NXN=B-1b

，移項得(2.53)再將目標(biāo)函數(shù)（2.50）作相應(yīng)的變換，將它用非基變量來表示則(LP)問題又可等價地寫成：我們稱式（2.54）~（2.56）為問題(LP)對應(yīng)于基B

的典式．在式（2.53）中令XN=0

（即全部非基變量取值為零），則得XB=B-1b

，當(dāng)XB=B-1b≥0時，

就是初始基

B

對應(yīng)的初始基可行解．令

σN=CN-CBB-1N,顯然，σN

就是非基變量XN

的檢驗數(shù)．這樣，我們可以根據(jù)(LP)問題的典式列出一張初始表，稱為初始單純形表．見表2.5.表2.5C

→CB

CNCBXBbXBXNCBXBB-1bIB-1NZ-CBB-1b0CN-CBB-1N又因為并記其中，于是，表2.5還可簡化為表2.6.表2.6C

→CCBXBbXCBXBB-1bB-1AZ-CBBC

-CBB-1A表2.5的具體表示形式為表2.7.Cj

→C

1…C

mC

m+1…C

nθiCBXBbx1…xmxm+1…xnc1x1b11…0a1,m+1…a1nθ1c2x2b20…0a2,m+1…a2nθ2…………………………cmxmbm0…1am,m+1…amnθmCj–Zj0…0…表2.7其中：XB

列為基變量，這里是x1,x2,…,xm

；CB

列中為基變量的價值系數(shù)，這里是c1,c2,…,cm

；它們隨基變量改變而改變，并與基變量相對應(yīng)；b

列中為約束方程組右端的常數(shù)；cj

行中為所有變量的價值系數(shù)c1,c2,…,cn

；θi

列的數(shù)字是在確定換入變量后，按θ

規(guī)則計算的相應(yīng)的θ

值；最后一行稱為檢驗數(shù)行，對應(yīng)各非基變量xj

的檢驗數(shù)是

，即cj-zj=σj(j=m+1,…,n)表2.7稱為初始單純形表，每迭代一次構(gòu)造一個新單純形表．現(xiàn)在我們結(jié)合例題來說明如何利用單純形列表算法求解線性規(guī)劃問題．解：（1）根據(jù)例2.1的標(biāo)準(zhǔn)形，取松弛變量x3,x4,x5

為基變量，它對應(yīng)的單位矩陣為初始基．這時可以得到一個初始基可行解

X(0)=(0,0,4,8,6)T

，將相關(guān)數(shù)字填入表中，得到初始單純形表，見表2.8．表2.8中的左上角的Cj

是表示目標(biāo)函數(shù)中各變量的價值系數(shù)，在表的CB

列中，填入初始基變量的價值系數(shù)，它們都是0，檢驗數(shù)行各非基變量的檢驗數(shù)為（2）因σ1=2,σ2=3,都大于零，且P1、P2

、

的坐標(biāo)有正分量存在，轉(zhuǎn)入下一步．（3）因為max(σ1,σ2)=max(2,3)=3，所以x2

為換入變量．因為3/2對應(yīng)x5

這一行，所以x5

為換出變量.（4）以

x5

所在行與

x2

所在列的交叉元素[4]為主元素，進行旋轉(zhuǎn)運算，即將P2

變換為(0,0,1)T

，在XB

列中將x5

替換為x2

，得到新表2.9．b

列的數(shù)字是x3=1,x4=8,x2=3/2.于是得到新的基可行解x(1)=(0,3/2,1,8,0)T

.目標(biāo)函數(shù)的取值Z=9/2

．（5）檢查表2.9中的所有

σj

，因為

σ1

為2，說明

x1

應(yīng)為換入變量，重復(fù)（2）~（4）的計算步驟，得表2.10．（6）表2.10最后一行的所有檢驗數(shù)都已為負或零，這表示目標(biāo)函數(shù)已不可能再增大，于是得到最優(yōu)解X*=X(3)=(2,1,0,0,2)T

，目標(biāo)函數(shù)值Z*=7．§2.4人工變量法前面所舉的單純形法的例子中，化為標(biāo)準(zhǔn)形后約束條件的系數(shù)矩陣中含有單位矩陣，以此作初始可行基，使求初始基可行解和建立初始單純形表都十分方便．但對所有約束條件是“≥”形式的不等式及等式約束情況，添加松弛變量后，尚不能構(gòu)造單位矩陣，這時，我們采用人造基方法，即對不等式約束減去一個非負的剩余變量后，再加上一個非負的人工變量；對于等式約束直接加上一個非負的人工變量，總能得到一個單位矩陣，這些變量沒有實際意義，純粹是出于一種處理方法的需要，故稱它們?yōu)槿斯ぷ兞糠ǎ╝rtificialvariables）．設(shè)線性規(guī)劃問題為在約束條件

中，分別給每一個約束方程加入一個非負的人工變量xn+1,…,xn+m

，得到以xn+1,…,xn+m

為基變量，并可得到一個m×m階的單位矩陣，令非基變量x1,…,xn

為零，便可得到一個初始基可行解X(0)=(0,0,…0,b1,b2,…,bm)T

．因為人工變量是后加入到原約束條件中的虛擬變量，要求將它們從基變量中逐個替換出來．若經(jīng)過基的變換，基變量中不再含有非零的人工變量，這表示原問題有解；若在最終單純形表中當(dāng)所有檢驗數(shù)cj-zj≤0，而在基變量中還有某個非零人工變量，這表示無可行解．下面我們來介紹人工變量法的兩種方法——大M

法和兩階段法.

一、大M法在一個線性規(guī)劃問題的約束條件中加進人工變量后，要求人工變量對目標(biāo)函數(shù)取值不受影響，為此假定人工變量在目標(biāo)函數(shù)中的系數(shù)為（-M）（M

為任意大的正數(shù)），這樣目標(biāo)函數(shù)要實現(xiàn)最大化時，必須把人工變量從基變量中換出，否則目標(biāo)函數(shù)不可能實現(xiàn)最大化．根據(jù)以上分析，作輔助問題：再對(LP’)問題用單純形法求解即可．(LP’)和(LP)有如下的關(guān)系：定理2.6若(LP’)有最優(yōu)解(x1*,…,x*n+m)T

，則當(dāng)x*n+1=…=x*n+m=0時，((x1*,…,xn*)T

即為(LP)之最優(yōu)解；否則(LP)無可行解．

（證明從略）例2.7用單純形法求解線性規(guī)劃問題解：在上述問題的約束條件中加入松馳變量x4,x5

,，人工變量x6,x7

,，得到其中M

是一個任意大的正數(shù)．解：在上述問題的約束條件中加入松馳變量x4,x5

，人工變量x6,x7

，得到該模型中構(gòu)成單位矩陣的變量x4,x6,x7

為基變量，令非基變量x1,x2,x3,x5

等于零，即得到初始基可行解X(0)=(0,0,0,4,0,1,9)T

，并列出初始單純形表．在單純形法迭代運算中，M

可當(dāng)作一個數(shù)學(xué)符號一起參加運算．檢驗數(shù)中含

M

符號的，當(dāng)M的系數(shù)為正時，該檢驗數(shù)為正，當(dāng)

M

的系數(shù)為負時，該項檢驗數(shù)為負．例2.7中添加人工變量后，用單純形法求解的過程見表2.11．(下頁續(xù)表)最后可得：X*=(0,5/2,3/2,0,0,0,0)T,MaxZ=-3×0+1×3/2=3/2

。

二、兩階段法由于在大M

法中引入了一個很大的正數(shù)M

，因此在計算機求解時，可能會產(chǎn)生較大的舍入誤差，故實際問題中常采用兩階段法．這種方法是將加入人工變量后的線性規(guī)劃問題分為兩個階段來求解.下面我們?nèi)跃蜆?biāo)準(zhǔn)形(LP)問題進行討論．設(shè)線性規(guī)劃問題為第一階段：令輔助問題中的目標(biāo)函數(shù)僅為各人工變量的負值之和，即作輔助問題：顯然xn+1,…,xn+m

可以作為輔助問題(LP”)的一個初始基變量．因f有上界，且可行解集是閉集，故f

的最優(yōu)值f*

必然存在，且f≤0

．定理2.7(LP)

有可行解的充分必要條件是(LP”)的最優(yōu)值f*=0．（證明略）在具體解題時，用得較多的是下述推論：推論若f*<0，則(LP)無可行解；若

f*=0，則(LP)有可行解．第二階段：從第一階段所求得的初始可行基和初始基可行解出發(fā)，繼續(xù)求解原(LP)

問題，得到原(LP)問題的最優(yōu)基和最優(yōu)解．當(dāng)f*=0時，分兩種情形考慮：情形一，若(LP”)的最優(yōu)基B”中不含人工變量，則B”

即為(LP)的一個可行基；情形二，若B”

中含有人工變量，此時情況較為復(fù)雜，下面我們通過例題來說明其解法．例2.8用兩階段法解上面的例2.7.解：引進松弛變量x4,x5≥0

，得到增加人工變量

x6,x7≥0，構(gòu)造輔助問題，并進入第一階段求解．用單純形法求解，得到第一階段問題的計算表,見下表2.12.最優(yōu)解X*=(1,3,0,0,0,0,0)T

，最優(yōu)值f=0.第一階段最后一張最優(yōu)表說明找到了原問題的一組基可行解，將它作為初始基可行解，求原問題的最優(yōu)解即第二階段問題為從表2.12中的最后一張表出發(fā)，將表2.12中的人工變量

x6

、x7

所在的列除去，將目標(biāo)函數(shù)的系數(shù)替換為MaxZ=-3x1+x3

中的系數(shù)，再繼續(xù)用單純形法計算，求解過程見表2.13.-3檢驗數(shù)σj≤0

，最優(yōu)解為：X*=(0,5/2,3/2,0,0,0,0)T

，最優(yōu)值Z*=3/2.不難看出，上面兩種計算方法的每一步迭代的結(jié)果類似，最后結(jié)果相同．在第二階段計算時，初始表中的檢驗數(shù)不能引用第一階段最優(yōu)表的檢驗數(shù)，必須換成原問題的檢驗數(shù)，用代入法或公式計算．另外即使第一階段最優(yōu)值為零，只能說明原問題有可行解，第二階段問題不一定有最優(yōu)解，即原問題可能無界．前面我們已經(jīng)給出了唯一解、多重解、無界解的判別準(zhǔn)則，在學(xué)習(xí)了人工變量法之后，我們就可以給出無可行解的判別準(zhǔn)則．無可行解的判別準(zhǔn)則：當(dāng)線性規(guī)劃問題中添加人工變量后，用人工變量法求解，如果迭代到某單純形表已滿足所有非基變量的σj≤0，但基變量中仍含有非零的人工變量,則該線性規(guī)劃問題無可行解．前面我們已經(jīng)學(xué)習(xí)了求解線性規(guī)劃問題的幾種方法，掌握了這些方法之后，我們就可以解決任意型的線性規(guī)劃模型了．現(xiàn)在我們對前面的內(nèi)容做一個簡單的小結(jié)，并給出幾個需要進一步說明的問題．

（1）對給定的線性規(guī)劃問題應(yīng)首先化為標(biāo)準(zhǔn)形式，選取或構(gòu)造一個單位矩陣作為基，求出初始基可行解并列出初始單純形表．對各種類型線性規(guī)劃問題如何化為標(biāo)準(zhǔn)形式及如何選取初始基變量可參見表2.14．（2）線性規(guī)劃的求解過程可用如下框圖表示：圖2.6單純形法計算步驟框圖

（3）目標(biāo)函數(shù)為取極小化解的最優(yōu)性判別，只需將原來要求檢驗數(shù)σj≤0

改成σj≥0

即可．

（4）按θ

規(guī)則來確定換出變量時如果存在兩個相同的最小比值θi

，則在下一輪單純形表的基可行解中即有可能出現(xiàn)一個或多個基變量等于零的退化解．退化解的原因是模型中存在多余的約束，使多個基可行解對應(yīng)同一頂點．當(dāng)存在退化解時，就有可能出現(xiàn)迭代計算的循環(huán)，從而永遠迭代不到最優(yōu)解．為此，1974年勃蘭德（Bland）提出了一個簡便而有效的原則：第一，當(dāng)存在多個σj>0時，始終選擇下標(biāo)最小的變量作為換入變量；第二，當(dāng)計算

θ

值出現(xiàn)兩個以上相同的最小比值時，始終選取下標(biāo)最小的變量作為換出變量．§2.5案例分析【案例2.1】合理下料問題．現(xiàn)要做100套鋼架，每套由長2.8m、2.2m和1.8m的元鋼各一根組成，已知原材料長6.0m，問應(yīng)如何下料，可以使原材料最??？解：由于要裁成的三種元鋼的總長度是2.8m+2.2m+1.8m=6.8m，超過了原材料6m的長度．因此，我們?nèi)菀讓崿F(xiàn)的裁法是：在原材料上分別裁下2.8m、2.2m的元鋼各一根，這樣要100根原材料才能裁到100根2.8m、2.2m的元鋼．再來考慮如何裁得1.8m的元鋼，由于一根原材料可以裁得3根1.8m的元鋼，這樣要裁得100根1.8m的元鋼，就需要原材料34根．采取上述裁法需134原材料方可裁得2.8m、2.2m、1.8m的元鋼各100根．但如果改用套裁，則可節(jié)約原材料．經(jīng)過簡單分析，我們得到幾種可供套裁的方案，見表2.15．為了獲得100套鋼架，需要混合使用各種下料方案．設(shè)按六種方案下料的原材料的根數(shù)分別為x1,x2,…,x6

，根據(jù)表2.1