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

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

第2章

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

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

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

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

,x2

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

,x2

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

,x2

加上非負(fù)限制，即

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，并簡(jiǎn)稱為(LP)問(wèn)題．(LP)問(wèn)題還可以用以下幾種形式來(lái)表示：(1)簡(jiǎn)記形式(2)矩陣形式

(3)向量形式

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

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

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

取代xk，且滿足x’k≥

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

0或≤

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

，其中x’k≥

0，x”k≥

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

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

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

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

和Q3

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

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

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

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

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

和x(2)

連線上的一切點(diǎn)

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

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

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

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

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

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

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

（nondegenerationbasicfeasiblesolution）；

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

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

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

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

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

對(duì)照?qǐng)D解法，可以很清楚地了解利用單純形算法求解線性規(guī)劃問(wèn)題所獲得的結(jié)果．初始基可行解X(0)=(0,0,4,8,6)T相當(dāng)于圖2.2中的原點(diǎn)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)開(kāi)始迭代，依次得到X(1)

、X(2)

、X(3)

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

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

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

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

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

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

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

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

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

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

0

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

三、單純形列表算法

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

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

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

中，有一個(gè)σK

對(duì)應(yīng)于xK

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

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

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

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

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

為換入變量xK

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

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

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

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

不妨設(shè)m×m

階的非奇異方陣B

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

是非奇異方陣，故B-1

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

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

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

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

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

就是初始基

B

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

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

就是非基變量XN

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

→CB

CNCBXBbXBXNCBXBB-1bIB-1NZ-CBB-1b0CN-CBB-1N又因?yàn)椴⒂浧渲?，于是，?.5還可簡(jiǎn)化為表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

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

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

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

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

；θi

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

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

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

的檢驗(yàn)數(shù)是

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

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

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

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

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

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

、

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

為換入變量．因?yàn)?/2對(duì)應(yīng)x5

這一行，所以x5

為換出變量.（4）以

x5

所在行與

x2

所在列的交叉元素[4]為主元素，進(jìn)行旋轉(zhuǎn)運(yù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

，因?yàn)?/p>

σ1

為2，說(shuō)明

x1

應(yīng)為換入變量，重復(fù)（2）~（4）的計(jì)算步驟，得表2.10．（6）表2.10最后一行的所有檢驗(yàn)數(shù)都已為負(fù)或零，這表示目標(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ù)矩陣中含有單位矩陣，以此作初始可行基，使求初始基可行解和建立初始單純形表都十分方便．但對(duì)所有約束條件是“≥”形式的不等式及等式約束情況，添加松弛變量后，尚不能構(gòu)造單位矩陣，這時(shí)，我們采用人造基方法，即對(duì)不等式約束減去一個(gè)非負(fù)的剩余變量后，再加上一個(gè)非負(fù)的人工變量；對(duì)于等式約束直接加上一個(gè)非負(fù)的人工變量，總能得到一個(gè)單位矩陣，這些變量沒(méi)有實(shí)際意義，純粹是出于一種處理方法的需要，故稱它們?yōu)槿斯ぷ兞糠ǎ╝rtificialvariables）．設(shè)線性規(guī)劃問(wèn)題為在約束條件

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

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

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

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

．因?yàn)槿斯ぷ兞渴呛蠹尤氲皆s束條件中的虛擬變量，要求將它們從基變量中逐個(gè)替換出來(lái)．若經(jīng)過(guò)基的變換，基變量中不再含有非零的人工變量，這表示原問(wèn)題有解；若在最終單純形表中當(dāng)所有檢驗(yàn)數(shù)cj-zj≤0，而在基變量中還有某個(gè)非零人工變量，這表示無(wú)可行解．下面我們來(lái)介紹人工變量法的兩種方法——大M

法和兩階段法.

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

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

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

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

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

,，人工變量x6,x7

,，得到其中M

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

，人工變量x6,x7

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

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

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

，并列出初始單純形表．在單純形法迭代運(yùn)算中，M

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

M

符號(hào)的，當(dāng)M的系數(shù)為正時(shí)，該檢驗(yàn)數(shù)為正，當(dāng)

M

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

。

二、兩階段法由于在大M

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

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

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

的最優(yōu)值f*

必然存在，且f≤0

．定理2.7(LP)

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

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

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

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

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

，得到增加人工變量

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

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

x6

、x7

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

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

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

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

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

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

改成σj≥0

即可．

（4）按θ

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

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

θ

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

，根據(jù)表2.1