第1章 線性規(guī)劃

運(yùn)籌學(xué)在英國(guó)稱為“OperationalResearch”，其他英語(yǔ)國(guó)家稱為“OperationsResearch”，直譯—“作業(yè)研究”或“操作研究”意譯—運(yùn)籌學(xué)，取“運(yùn)籌帷幄之中，決勝千里之外”之意。在英國(guó)稱為“OperationalResearch”，其他英語(yǔ)國(guó)家稱為“OperationsResearch”，直譯—“作業(yè)研究”或“操作研究”意譯—運(yùn)籌學(xué)，取“運(yùn)籌帷幄之中，決勝千里之外”之意?！疤锛少愸R”故事

田忌與齊王賽馬，約定每勝一馬得千金，各按馬力強(qiáng)弱，以強(qiáng)、中、弱的先后順序捉對(duì)較量，齊王的馬都比較好，田忌的三匹馬都略遜一籌，因而比賽輸了。異日又賽，田忌一改常策，以弱、強(qiáng)、中的出場(chǎng)次序分對(duì)齊王的強(qiáng)、中、弱三馬，終以一負(fù)兩勝贏得千金。之后的思考——博弈之前的故事，到此就截止了，后人都夸田忌有對(duì)策?？扇绻虑槔^續(xù)發(fā)展，接下來(lái)會(huì)怎樣呢，齊王輸了，肯定會(huì)仔細(xì)分析，為什么輸呢，推斷出田忌的對(duì)策，然后想到下回再賽馬，該如何排兵布陣，安排順序呢。如果田忌足夠聰明，他應(yīng)該也想到，齊王這回輸了，肯定會(huì)分析輸?shù)脑?，然后?huì)采取什么對(duì)策呢。……如此雙方都進(jìn)行算計(jì)。最后結(jié)局如何呢！

哥尼斯堡的七橋”故事

18世紀(jì)著名古典數(shù)學(xué)問(wèn)題之一。在哥尼斯堡，普雷格爾河流經(jīng)此鎮(zhèn)，奈發(fā)夫島位于河中，共有7座橋橫跨河上，把全鎮(zhèn)連接起來(lái)。當(dāng)?shù)鼐用駸嶂杂谝粋€(gè)難題：是否存在一條路線，可不重復(fù)地走遍七座橋，每座橋只能經(jīng)過(guò)一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn)。這就是柯尼斯堡七橋問(wèn)題。

七橋所成之圖形中，沒(méi)有一點(diǎn)含有偶數(shù)條數(shù)，因此上述的任務(wù)無(wú)法完成

把一個(gè)實(shí)際問(wèn)題抽象成合適的“數(shù)學(xué)模型”。這種研究方法就是“數(shù)學(xué)模型方法”。這并不需要運(yùn)用多么深?yuàn)W的理論，但想到這一點(diǎn)，卻是解決難題的關(guān)鍵。運(yùn)籌學(xué)的工作步驟

提出和形成問(wèn)題建立模型求解檢驗(yàn)實(shí)施第一章線性規(guī)劃的基本概念

線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃的圖解法線性規(guī)劃的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)型線性規(guī)劃的解的概念線性規(guī)劃的基本理論

問(wèn)題的提出：

在生產(chǎn)管理的經(jīng)營(yíng)活動(dòng)中，通常需要對(duì)“有限的資源”尋求“最佳”的利用或分配方式。有限資源：勞動(dòng)力、原材料、設(shè)備或資金等最佳：有一個(gè)標(biāo)準(zhǔn)或目標(biāo)，使利潤(rùn)達(dá)到最大或成本達(dá)到最小。

有限資源的合理配置有兩類問(wèn)題如何合理的使用有限的資源，使生產(chǎn)經(jīng)營(yíng)的效益達(dá)到最大；在生產(chǎn)或經(jīng)營(yíng)的任務(wù)確定的條件下，合理的組織生產(chǎn)，安排經(jīng)營(yíng)活動(dòng)，使所消耗的資源數(shù)最少。線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

與規(guī)劃問(wèn)題有關(guān)的數(shù)學(xué)模型總有兩部分組成：約束條件：反映了有限資源對(duì)生產(chǎn)經(jīng)營(yíng)活動(dòng)的種種約束，或者生產(chǎn)經(jīng)營(yíng)必須完成的任務(wù)；目標(biāo)函數(shù)：反映生產(chǎn)經(jīng)營(yíng)者在有限資源條件下希望達(dá)到的生產(chǎn)或經(jīng)營(yíng)的目標(biāo)。例１，某制藥廠生產(chǎn)甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設(shè)備時(shí)間，以及該廠每周可提供的資源總量如下表所示：每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺(tái)班）5115

已知該廠生產(chǎn)每噸甲、乙藥品的利潤(rùn)分別為5萬(wàn)元和2萬(wàn)元。但根據(jù)市場(chǎng)需求調(diào)查的結(jié)果，甲藥品每周的產(chǎn)量不應(yīng)超過(guò)4噸。問(wèn)該廠應(yīng)如何安排兩種藥品的產(chǎn)量才能使每周獲得的利潤(rùn)最大？

定義x1為生產(chǎn)甲種藥品的計(jì)劃產(chǎn)量數(shù)，x2為生產(chǎn)乙種藥品的計(jì)劃產(chǎn)量數(shù)。目標(biāo)：使總利潤(rùn)Z=5x1+2x2

極大化約束：每周資源總量的限制，30x1+20x2≤160

5x1+x2≤15甲種藥品每周產(chǎn)量不應(yīng)超過(guò)4噸的限制

x1≤4計(jì)劃生產(chǎn)數(shù)不可能是負(fù)數(shù)，x1≥0x2≥0每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺(tái)班）5115單位利潤(rùn)（萬(wàn)元）5２數(shù)學(xué)模型為

s.t.

（subjectto)(suchthat)這是一個(gè)如何合理的使用有限的資源，使生產(chǎn)經(jīng)營(yíng)的效益達(dá)到最大的數(shù)學(xué)規(guī)劃問(wèn)題。在滿足一組約束條件的限制下，尋求決策變量x1，x2的決策值，使目標(biāo)函數(shù)達(dá)到最大值。每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺(tái)班）5115單位利潤(rùn)（萬(wàn)元）5２例２：某化工廠根據(jù)一項(xiàng)合同要求為用戶生產(chǎn)一種用甲、乙兩種原料混合配制而成的特種產(chǎn)品。已知甲、乙兩種原料都含有A、B、C三種化學(xué)成分，兩種原料分別所含三種化學(xué)成分的百分比含量，以及按合同規(guī)定的產(chǎn)品中三種化學(xué)成分的最低含量如下表所示：已知甲、乙兩種原料的成本分別是每公斤3元和2元，廠方希望總成本達(dá)到最小，問(wèn)如何配置該產(chǎn)品？原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155化學(xué)成分定義x1，x2分別為每公斤產(chǎn)品中甲，乙兩種原料的數(shù)量，目標(biāo)：使總成本Z=3x1+2x2

極小化約束：配料平衡條件，x1+x2=1產(chǎn)品中A、B、C三種化學(xué)成分的最低含量

12x1+3x2≥4

2x1+3x2≥2

3x1+15x2≥5非負(fù)性條件x1≥0,x2≥0原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155單位成本（元）３２化學(xué)成分?jǐn)?shù)學(xué)模型：

s.t.

這是一個(gè)原料配制問(wèn)題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)，使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問(wèn)題。滿足一組約束條件的同時(shí)，尋求變量x1和x2的值使目標(biāo)函數(shù)取得最小值。原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155單位成本（元）３２化學(xué)成分

線性規(guī)劃的一般數(shù)學(xué)模型

線性規(guī)劃模型的特征：（1）用一組決策變量x1，x2，…xn表示方案，且在一般情況下，變量的取值是非負(fù)的。（2）有一個(gè)目標(biāo)函數(shù)，這個(gè)目標(biāo)函數(shù)可表示為這組變量的線性函數(shù)。（3）存在若干個(gè)約束條件，約束條件用決策變量的線性等式或線性不等式來(lái)表達(dá)。（4）要求目標(biāo)函數(shù)實(shí)現(xiàn)極大化（max）或極小化（min）。滿足上述4個(gè)特征的規(guī)劃問(wèn)題稱為線性規(guī)劃問(wèn)題

線性規(guī)劃的模型的一般形式:

目標(biāo)函數(shù)

滿足約束條件

通常稱為決策變量，為價(jià)值系數(shù)，為消耗系數(shù),為資源限制系數(shù)。

線性規(guī)劃的圖解法

適用于求解兩個(gè)變量的線性規(guī)劃問(wèn)題

圖解法的基本步驟利用例1說(shuō)明圖解法的主要步驟，例1的數(shù)學(xué)模型為

s.t.O51015x1x1=4x25101AB(2,5)C▽Z5x1+x2=1530x1+20x2=1605x1+2x2=5

線性規(guī)劃圖解法的基本步驟：（1）建立以x1,x2為坐標(biāo)軸的直角坐標(biāo)系，畫(huà)出線性規(guī)劃問(wèn)題的可行域,（2）求目標(biāo)函數(shù)Z=C1x1+C2x2的梯度▽Z=（c1,c2）,（3）任取等值線C1x1+C2x2=Z0,沿梯度▽Z正方向平移,

（若是極小化問(wèn)題，則沿負(fù)梯度方向-▽Z平移），求等直線將離未離可行域時(shí)與可行域的交點(diǎn)。（4）若交點(diǎn)存在，則該點(diǎn)坐標(biāo)就是最優(yōu)解。

圖解法的幾種可能結(jié)果

(1）有唯一最優(yōu)解，如例1。（2）有無(wú)窮多最優(yōu)解如例1中的目標(biāo)函數(shù)設(shè)為maxZ=10x1+2x2

則目標(biāo)函數(shù)等值線10x1+2x2=Z與第二約束5x1+x2≤15

的邊界線平行。將等值線沿梯度▽Z=（10，2）正方向平移至B點(diǎn)時(shí)與可行域OABC的整條邊界線AB重合。這表明線段AB上的每一點(diǎn)都使目標(biāo)函數(shù)取得同樣的最大值，因而都是最優(yōu)解。O51015x1x1=4x25101AB（2，5）C▽Z5x1+x2=1530x1+20x2=16010x1+2x2=5例5，試用圖解法求解下列線性規(guī)劃問(wèn)題

st.（3）無(wú)界解（或稱無(wú)最優(yōu)解）無(wú)界解是指線性規(guī)劃問(wèn)題的最優(yōu)解無(wú)界。若是極大化問(wèn)題，則可使目標(biāo)函數(shù)值Z→+∝,

極小化問(wèn)題則可使目標(biāo)函數(shù)值Z→-∝，

有無(wú)界解的線性規(guī)劃問(wèn)題的可行域通常是無(wú)界區(qū)域，但反之則不必然。-1O24x1x224-▽Z=(3,2)-2x1+x2=2x1-3x2=3-1O33（4）無(wú)可行解某些線性規(guī)劃問(wèn)題的可行域是空集，既不存在滿足所有約束條件的點(diǎn)，這時(shí)問(wèn)題無(wú)可行解，當(dāng)然更談不上最優(yōu)解了。在實(shí)際中出現(xiàn)這種情況可以認(rèn)為資源條件無(wú)法滿足人們的要求，既不存在可行方案。

標(biāo)準(zhǔn)線性規(guī)劃模型

線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：

s.t

其中(1.1)為目標(biāo)函數(shù)，(1.2)為約束條件，(1.3)為非負(fù)條件，為稱呼方便，有時(shí)將(1.3)也稱為約束條件。（1.2）

（1.3）線性規(guī)劃的標(biāo)準(zhǔn)形式（1.1）緊湊格式：

s.t.向量格式：

s.t.

其中稱為價(jià)值向量，為決策變量向量，為決策變量xj所對(duì)應(yīng)的消耗系數(shù)向量，為資源向量。矩陣格式：其中為m×n階矩陣

為價(jià)值向量，

為決策變量向量，

為資源向量。非標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化（1）極大化與極小化：若，令，則有

原目標(biāo)函數(shù)。(2)

線性不等式與線性等式：

其中為非負(fù)松弛變量，

其中為非負(fù)剩余變量。

(3)非負(fù)變量與符號(hào)不受限制的變量若xi的符號(hào)不受限制，則可引進(jìn)非負(fù)變量xi1,xi2，令

xi=xi1-xi2，這樣就可以使線性規(guī)劃里所有的變量都轉(zhuǎn)化為有非負(fù)限制的變量。例6，將下述線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型

解：令,可將目標(biāo)函數(shù)化為max型，令,其中符號(hào)不受限制考慮一個(gè)標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題：

s.t

其中Ｃ為n維行向量，

Ｘ是n維列向量，

ｂ是m維列向量，

Ａ是m×n階矩陣，假定滿足m≤n，且Ｒ(Ａ)=m，標(biāo)準(zhǔn)型線性規(guī)劃的解的概念

線性規(guī)劃問(wèn)題解的概念：

(1)可行解。滿足約束條件(1.5)，(1.6)的解稱為線性規(guī)劃問(wèn)題的可行解?？尚薪饧Q為線性規(guī)劃問(wèn)題的可行域。

(2)最優(yōu)解。使目標(biāo)函數(shù)（1.4)達(dá)到最優(yōu)值的的可行解稱為最優(yōu)解，最優(yōu)解常用表示。

(3)基。若Ｂ是Ａ中m×m階非奇異矩陣，即|Ｂ|≠0，則稱Ｂ是線性規(guī)劃問(wèn)題的一個(gè)基。若Ｂ是線性規(guī)劃問(wèn)題的一個(gè)基，那么Ｂ一定是由m個(gè)線性無(wú)關(guān)的列向量組成，不失一般性，可設(shè)

稱為基向量，

與基向量相對(duì)應(yīng)的變量稱為基變量。

一個(gè)線性規(guī)劃的基通常不是唯一的，但是基的個(gè)數(shù)也不會(huì)超過(guò)個(gè)。一旦線性規(guī)劃的基確定了，那么相應(yīng)的基向量、基變量和非基變量也就確定了。(4)基本解。設(shè)B是線性規(guī)劃的一個(gè)基，若令n-m個(gè)非基變量等于0，則所得的方程組ＡＸ=b的解稱為線性規(guī)劃問(wèn)題的一個(gè)基本解（簡(jiǎn)稱基解）。有一個(gè)基就可以求得一個(gè)基本解。由基的有限性可知，基本解的個(gè)數(shù)也不會(huì)超過(guò)個(gè)。由于基本解中的非零分量可能是負(fù)數(shù)，所以基本解不一定是可行的。(5)基本可行解。滿足非負(fù)條件的基本解稱為基本可行解（簡(jiǎn)稱基可行解）。與基本可行解對(duì)應(yīng)的基成為可行基。基本可行解的非零向量的個(gè)數(shù)小于等于m，并且都是非負(fù)的。由于基本可行解的數(shù)目一般少于基本解的數(shù)目，因此可行基的數(shù)目也要少于基的數(shù)目。

當(dāng)基本可行解中有一個(gè)或多個(gè)基變量是取零值時(shí)，稱此解為退化的基本可行解。

線性規(guī)劃問(wèn)題各種解的關(guān)系可用文氏圖表示，

可行解

基本解基本可行解例7、求下列約束方程所對(duì)應(yīng)的線性規(guī)劃的所有基本解，基本可行解。

s.t

解：化為標(biāo)準(zhǔn)形式為2×4階矩陣。且R(A)=2,所以該線性規(guī)劃基的個(gè)數(shù)≤=6個(gè)

取,為基變量，若令非基變量，約束方程組為可得對(duì)應(yīng)的基本解是一個(gè)基本可行解。

按相同步驟，可求得線性規(guī)劃其他4個(gè)基：對(duì)應(yīng)基本解是一個(gè)基本可行解。

對(duì)應(yīng)基本解是一個(gè)基本可行解。

對(duì)應(yīng)基本解不是一個(gè)基本可行解。

對(duì)應(yīng)基本解是一個(gè)基本可行解。

若利用圖解法畫(huà)出線性規(guī)劃的可行域，如圖，CDOBA448

線性規(guī)劃的基本理論

由圖解法的步驟，可以從幾何的角度得出以下兩個(gè)結(jié)論：（1）線性規(guī)劃問(wèn)題的可行域是一個(gè)有界或無(wú)界的凸多邊形，其頂點(diǎn)個(gè)數(shù)是有限個(gè)。（2）若線性規(guī)劃問(wèn)題有最優(yōu)解，那么最優(yōu)解一定可在可行域的某個(gè)頂點(diǎn)上找到。幾個(gè)基本概念

（1）凸集：設(shè)k是n維歐式空間的一個(gè)點(diǎn)集，若任意兩點(diǎn)

X(1)∈k,X(2)∈k的連線上的一切點(diǎn)αX(1)+(1-α)X(2)∈k

(0<α<1),則稱k為凸集。連接幾何形體中任意兩點(diǎn)的線段仍完全在該幾何形體之中。有限個(gè)凸集的交集仍然是凸集。（2）凸組合：設(shè)X(1)，X(2)，…，X(k)是n維歐式空間中的k個(gè)點(diǎn)，若存在μ1,μ2,…,μk滿足0≤μi≤1,(i=1,2,…,k),

使X=μ1X(1)+μ2X(2)+…μkX(k)，

則稱X為X(1)，X(2)，…，X(k)的凸組合。凸集k中任意兩點(diǎn)X(1)，X(2)連線上的任一點(diǎn)X都是X(1)與X(2)的一個(gè)凸組合。

(3)頂點(diǎn)：設(shè)k為凸集，X∈k,若X不能用X(1)∈k,X(2)∈k兩點(diǎn)的一個(gè)凸組合表示為X=αX(1)+(1-α)X(2),其中0<α<1，

則稱X為k的一個(gè)頂點(diǎn)。第二章單純形法

單純形法的一般原理表格單純形法借助人工變量求初始的基本可行解單純形表與線性規(guī)劃問(wèn)題的討論改進(jìn)單純形法

Dantzig的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行域頂點(diǎn)）中。其基本思路是從一個(gè)初始的基本可行解出發(fā)，尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。

單純形法的一般步驟如下：

（1）尋找一個(gè)初始的基本可行解。（2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。（3）移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解，然后轉(zhuǎn)回到步驟（2）。

確定初始的基本可行解

確定初始的基本可行解等價(jià)于確定初始的可行基，一旦初始的可行基確定了，那么對(duì)應(yīng)的初始基本可行解也就唯一確定

為了討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中，系數(shù)矩陣Ａ中前m個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm）為基變量x1，x2，…xm的系數(shù)列向量構(gòu)成的可行基，Ｎ=(Ｐm+1，Pm+2，

…Pn)為非基變量xm+1，xm+2，

…xn的系數(shù)列向量構(gòu)成的矩陣。

所以約束方程就可以表示為

用可行基Ｂ的逆陣Ｂ-1左乘等式兩端，再通過(guò)移項(xiàng)可推得：若令所有非基變量,則基變量由此可得初始的基本可行解問(wèn)題：要判斷m個(gè)系數(shù)列向量是否恰好構(gòu)成一個(gè)基并不是一件容易的事。基由系數(shù)矩陣Ａ中m個(gè)線性無(wú)關(guān)的系數(shù)列向量構(gòu)成。但是要判斷m個(gè)系數(shù)列向量是否線性無(wú)關(guān)并非易事。即使系數(shù)矩陣Ａ中找到了一個(gè)基B，也不能保證該基恰好是可行基。因?yàn)椴荒鼙ＷC基變量ＸB=Ｂ-1b≥0。為了求得基本可行解，必須求基Ｂ的逆陣Ｂ-1。但是求逆陣Ｂ-1也是一件麻煩的事。結(jié)論：在線性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中設(shè)法得到一個(gè)m階單位矩陣I作為初始可行基Ｂ，若在化標(biāo)準(zhǔn)形式前，約束方程中有“≥”不等式，那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量使不等式變成等式以外，還必須在左端再加上一個(gè)非負(fù)新變量，稱為人工變量．若在化標(biāo)準(zhǔn)形式前，約束方程中有等式方程，那么可以直接在等式左端添加人工變量。為了設(shè)法得到一個(gè)m階單位矩陣I作為初始可行基Ｂ，可在性規(guī)劃標(biāo)準(zhǔn)化過(guò)程中作如下處理：

若在化標(biāo)準(zhǔn)形式前，m個(gè)約束方程都是“≤”的形式，那么在化標(biāo)準(zhǔn)形時(shí)只需在一個(gè)約束不等式左端都加上一個(gè)松弛變量xn+i(i=12…m)。判斷現(xiàn)行的基本可行解是否最優(yōu)

假如已求得一個(gè)基本可行解將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值

其中

分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。

要判定是否已經(jīng)達(dá)到最大值，只需將代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量表示，即：

其中稱為非基變量ＸN的檢驗(yàn)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。若σN的每一個(gè)檢驗(yàn)數(shù)均小于等于0，即σN≤0，那么現(xiàn)在的基本可行解就是最優(yōu)解。定理1：最優(yōu)解判別定理

對(duì)于線性規(guī)劃問(wèn)題若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，則這個(gè)基本可行解就是最優(yōu)解。定理2：無(wú)窮多最優(yōu)解判別定理

若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)σm+k=0，

則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。

基本可行解的改進(jìn)

如果現(xiàn)行的基本可行解Ｘ不是最優(yōu)解，即在檢驗(yàn)向量中存在正的檢驗(yàn)數(shù)，則需在原基本可行解Ｘ的基礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量（將它的值從零增至正值），再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。由此可得一個(gè)新的基本可行解，由可知，這樣的變換一定能使目標(biāo)函數(shù)值有所增加。換入變量和換出變量的確定：換入變量的確定—最大增加原則

假設(shè)檢驗(yàn)向量，若其中有兩個(gè)以上的檢驗(yàn)數(shù)為正，那么為了使目標(biāo)函數(shù)值增加得快些，通常要用“最大增加原則”，即選取最大正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量為換入變量，即若

則選取對(duì)應(yīng)的為換入變量，由于且為最大，因此當(dāng)由零增至正值，可使目標(biāo)函數(shù)值最大限度的增加。換出變量的確定—最小比值原則如果確定為換入變量，方程

其中為Ａ中與對(duì)應(yīng)的系數(shù)列向量。現(xiàn)在需在中確定一個(gè)基變量為換出變量。當(dāng)由零慢慢增加到某個(gè)值時(shí)，

的非負(fù)性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量：若則選取對(duì)應(yīng)的基變量為換出變量。定理3：無(wú)最優(yōu)解判別定理

若

是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù)，但是，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。證：令，則得新的可行解將上式代入

因?yàn)?故當(dāng)λ→+∞時(shí)，Z→+∞。

用初等變換求改進(jìn)了的基本可行解

假設(shè)Ｂ是線性規(guī)劃的可行基，則令非基變量，則基變量?？傻没究尚薪?/p>

。

用逆陣左乘約束方程組的兩端，等價(jià)于對(duì)方程組施以一系列的初等“行變換”。變換的結(jié)果是將系數(shù)矩陣Ａ中的可行基Ｂ變換成單位矩陣I，把非基變量系數(shù)列向量構(gòu)成的矩陣Ｎ變換成，把資源向量b變換成。

且改進(jìn)了的基本可行解只是在Ｘ的基變量的基礎(chǔ)上用一個(gè)換入變量替代其中一個(gè)換出變量，其它的基變量仍然保持不變。這些基變量的系數(shù)列向量是單位矩陣I中的單位向量。為了求得改進(jìn)的基本可行解，只需對(duì)增廣矩陣施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對(duì)應(yīng)的單位向量即可。

由于行初等變換后的方程組與原約束方程組或同解例1解：(１)確定初始的基本可行解。，基變量

，非基變量

。(2)檢驗(yàn)

是否最優(yōu)。檢驗(yàn)向量

因?yàn)棣?=3，σ3=4均大于零，所以不是最優(yōu)解。（3）基本可行解的改進(jìn)

①

選取換入變量因?yàn)閙ax{3，4}=4，取x3為換入變量。

②

選取換出變量且

，

選取x4為換出變量.（4）求改進(jìn)了的基本可行解

對(duì)約束方程組的增廣矩陣施以初等行變換，使換入變量x3所對(duì)應(yīng)的系數(shù)列向量

變換成換出變量x4所對(duì)應(yīng)的單位向量,

注意保持基變量x5的系數(shù)列向量

為單位向量不變。第一行除以２第二行減去第一行——————————————————————————可得改進(jìn)的基本可行解。，基變量，非基變量。

基本可行解

目標(biāo)函數(shù)值易見(jiàn)目標(biāo)函數(shù)值比原來(lái)的Z=-1增加了，再轉(zhuǎn)向步驟(2)（2）檢驗(yàn)

是否最優(yōu)。檢驗(yàn)向量

因?yàn)椋匀圆皇亲顑?yōu)解。（3）基本可行解的改進(jìn)

①

選取換入變量因?yàn)?，取為換入變量。

②

選取換出變量且

，選取為換出變量.（4）求改進(jìn)了的基本可行解

對(duì)約束方程組的增廣矩陣施以初等行變換，使換入變量所對(duì)應(yīng)的系數(shù)列向量變換成換出變量所對(duì)應(yīng)的單位向量

,

第二行乘以２/５第一行減以第二行的１/２倍——————————————————————————可得改進(jìn)的基本可行解。，基變量，非基變量

基本可行解

目標(biāo)函數(shù)值比Z=15增加了，再轉(zhuǎn)向步驟(2)（2）檢驗(yàn)

是否最優(yōu)。檢驗(yàn)向量

因?yàn)樗袡z驗(yàn)數(shù)均小于零，所以是最優(yōu)解，表格單純形法

通過(guò)例１我們發(fā)現(xiàn)，在單純形法的求解過(guò)程中，有下列重要指標(biāo)：每一個(gè)基本可行解的檢驗(yàn)向量根據(jù)檢驗(yàn)向量可以確定所求得的基本可行解是否為最優(yōu)解。如果不是最優(yōu)又可以通過(guò)檢驗(yàn)向量確定合適的換入變量。每一個(gè)基本可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值通過(guò)目標(biāo)函數(shù)值可以觀察單純形法的每次迭代是否能使目標(biāo)函數(shù)值有效地增加，直至求得最優(yōu)目標(biāo)函數(shù)為止。

在單純形法求解過(guò)程中，每一個(gè)基本可行解Ｘ都以某個(gè)經(jīng)過(guò)初等行變換的約束方程組中的單位矩陣Ι為可行基。當(dāng)Ｂ=Ｉ時(shí)，Ｂ-1=Ｉ，易知：

可將這些重要結(jié)論的計(jì)算設(shè)計(jì)成如下一個(gè)簡(jiǎn)單的表格，即單純形表來(lái)完成：C

CBCN

θ

CB

XB

b

X1X2···Xm

Xm+1Xm+2···Xn

C1C2..Cm

X1X2

.Xm

b1b2..bm

I

N

θ1θ2..θm

Z

CBb

0

CN-CBN

例2、試?yán)脝渭冃伪砬罄?中的最優(yōu)解：

得初始的單純形表：初始基本可行解，Z=-1，

122108x4-1

30400-1Z

341017x51

x1x2x3x4x5bXBCBΘ

523-11C

換入變量，換出變量，２為主元進(jìn)行旋轉(zhuǎn)變換基本可行解，Z=15，1/2

1

1

1/2

04x331-40-2015Z5/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C122108x4-130400-1Z341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1

最優(yōu)解最優(yōu)值

換入變量，換出變量，５/２為主元進(jìn)行旋轉(zhuǎn)變換4/1/21/2

1

1

1/2

04x331-40-2015Z3/5/25/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C02/513/5-1/517/5x33

0-26/50-9/5-2/581/5Z16/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ

523-11C例3、用單純形方法求解線性規(guī)劃問(wèn)題解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)，可以令則這兩個(gè)線性規(guī)劃問(wèn)題具有相同的可行域和最優(yōu)解，只是目標(biāo)函數(shù)相差一個(gè)符號(hào)而已。

010103x220012-12x30-010103x224/1101004x303/1010103x40_101004x30

0000-18Z’100-212x11

100-206Z’2/1100-212x50

120000Z’8/2120018x50

x1x2x3x4x5bXBCBΘ12000C最優(yōu)解最優(yōu)值2/23/1-

因?yàn)榉腔兞縳4的檢驗(yàn)數(shù)σ4=0，由無(wú)窮多最優(yōu)解判別定理，本例的線性規(guī)劃問(wèn)題存在無(wú)窮多最優(yōu)解。事實(shí)上若以x4為換入變量，以x3為換出變量，再進(jìn)行一次迭代，可得一下單純形表：最優(yōu)解最優(yōu)值最優(yōu)解的一般表示式C12000ΘCBXBb

x1x2x3x4x5021x4x2x1124001/21-1/201-1/201/210100Z’8

0000-1對(duì)于極小化的線性規(guī)劃問(wèn)題的處理：先化為標(biāo)準(zhǔn)型，即將極小化問(wèn)題變換為極大化問(wèn)題，然后利用單純形方法求解．直接利用單純形方法求解，但是檢驗(yàn)是否最優(yōu)的準(zhǔn)則有所不同，即：若某個(gè)基本可行解的所有非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)（而不是≤０），則基本可行解為最優(yōu)解．否則采用最大減少原則（而非最大增加原則）來(lái)確定換入變量，即：若則選取對(duì)應(yīng)的非基變量xm+k為換入變量．確定了換入變量以后，換出變量仍采用最小比值原則來(lái)確定。

借助人工變量求初始的基本可行解

若約束方程組含有“≥”不等式，那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量，還必須在左端加上一個(gè)非負(fù)的人工變量。因?yàn)槿斯ぷ兞渴窃诩s束方程已為等式的基礎(chǔ)上，人為的加上去的一個(gè)新變量，因此加入人工變量后的約束方程組與原約束方程組是不等價(jià)的。加上人工變量以后，線性規(guī)劃的基本可行解不一定是原線性規(guī)劃的問(wèn)題的基本可行解。只有當(dāng)基本可行解中所有人工變量都為取零值的非基變量時(shí)，該基本可行解對(duì)原線性規(guī)劃才有意義。因?yàn)榇藭r(shí)只需去掉基本可行解中的人工變量部分，剩余部分即為原線性規(guī)劃的一個(gè)基本可行解．而這正是我們引入人工變量的主要目的?？紤]線性規(guī)劃問(wèn)題：為了在約束方程組的系數(shù)矩陣中得到一個(gè)m階單位矩陣作為初始可行基，在每個(gè)約束方程組的左端加上一個(gè)人工變量

可得到：

————————————————————————

添加了m個(gè)人工變量以后，在系數(shù)矩陣中得到一個(gè)m階單位矩陣，以該單位矩陣對(duì)應(yīng)的人工變量為基變量，即可得到一個(gè)初始的基本可行解這樣的基本可行解對(duì)原線性規(guī)劃沒(méi)有意義的。但是我們可以從X(0)出發(fā)進(jìn)行迭代，一旦所有的人工變量都從基變量迭代出來(lái)，變成只能取零值的非基變量，那么我們實(shí)際上已經(jīng)求得了原線性規(guī)劃問(wèn)題的一個(gè)初始的基本可行解。此時(shí)可以把所有人工變量剔除，開(kāi)始正式進(jìn)入求原線性規(guī)劃最優(yōu)解的過(guò)程。大M法

大M法首先將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個(gè)單位矩陣I，那么已經(jīng)得到了一個(gè)初始可行基。否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量，使人工變量對(duì)應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個(gè)單位矩陣。以單位矩陣為初始基，即可求得一個(gè)初始的基本可行解。為了求得原問(wèn)題的初始基本可行解，必須盡快通過(guò)迭代過(guò)程把人工變量從基變量中替換出來(lái)成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的負(fù)系數(shù)-Ｍ。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。

以后的計(jì)算與單純形表解法相同，Ｍ只需認(rèn)定是一個(gè)很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說(shuō)明原問(wèn)題無(wú)可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問(wèn)題的初始基本可行解。例4、用大M法求解下面的線性規(guī)劃問(wèn)題:解：

首先將原問(wèn)題化為標(biāo)準(zhǔn)型添加人工變量，并在目標(biāo)函數(shù)中分別賦予-Ｍ

-

01-1/2-1/201/21/23/2X2210-1/21/201/2-1/21/2X1-1--110-10011X221/220-1101-11X6-M1/1-110-10011X7-M2/111-100102X6-M

001/23/20-1/2-M-3/2-M5/2Z

001/21/21-1/2-1/23/2X501+2M0-M2+M00-2-2M2-MZ2/1100110-12X50

-12+2M-M-M000-3MZ3/101001003X50

X1x2x3x4x5x6x7bXBCBθ

-12000-M-MC01001003X22100110-12X4011-100102X2220-1101-11X40-

01-1/2-1/201/21/23/2X221/2/1/210-1/21/201/2-1/21/2X1-1-1000-2-M-M6Z-10101-101X30-30200-2-M-M4Z-10101-101X50

001/23/20-1/2-M-3/2-M5/2Z3/2/1/2

001/21/21-1/2-1/23/2X50

X1x2x3x4x5x6x7bXBCBθ

-12000-M-MC最優(yōu)解最優(yōu)值兩階段法

兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。兩階段法的步驟：求解一個(gè)輔助線性規(guī)劃。目標(biāo)函數(shù)取所有人工變量之和，并取極小化；約束條件為原問(wèn)題中引入人工變量后包含一個(gè)單位矩陣的標(biāo)準(zhǔn)型的約束條件。如果輔助線性規(guī)劃存在一個(gè)基本可行解，使目標(biāo)函數(shù)的最小值等于零，則所有人工變量都已經(jīng)“離基”。表明原問(wèn)題已經(jīng)得了一個(gè)初始的基本可行解，可轉(zhuǎn)入第二階段繼續(xù)計(jì)算；否則說(shuō)明原問(wèn)題沒(méi)有可行解，可停止計(jì)算。求原問(wèn)題的最優(yōu)解。在第一階段已求得原問(wèn)題的一個(gè)初始基本可行解的基礎(chǔ)上，繼續(xù)用單純形法求原問(wèn)題的最優(yōu)解例5、用兩階段法求解例4中的線性規(guī)劃問(wèn)題。解：首先將問(wèn)題化為標(biāo)準(zhǔn)型添加人工變量x6,x7,并建立輔助線性規(guī)劃如下：由于輔助線性規(guī)劃的目標(biāo)函數(shù)是極小化，因此最優(yōu)解的判別準(zhǔn)則應(yīng)為：

01-1/2-1/201/21/23/2X2010-1/21/201/2-1/21/2X10--110-10011X201/220-1101-11X611/1-110-10011X712/111-100102X6100000110W

001/21/21-1/2-1/23/2X50-201-10021W2/1100110-12X50

0-2110003W3/1

01001003X50x1x2x3x4x5x6x7bXBCBθ0000011C輔助規(guī)劃所有檢驗(yàn)數(shù)：原問(wèn)題已得一個(gè)初始基本可行解，由上表可知，通過(guò)若干次旋轉(zhuǎn)變換，原問(wèn)題的約束方程組已變換成包含一個(gè)單位矩陣的約束方程組該約束方程組可作為第二階段初始約束方程組，將目標(biāo)函數(shù)則還原成原問(wèn)題的目標(biāo)函數(shù)，可繼續(xù)利用單純形表求解。-1000-26Z1001101001-10101231X4X2X3020-302004Z20-11011-100-10101121X4X2X5020001/23/205/2Z1/2/1/2-3/2/1/2

10-1/21/2001-1/2-1/20001/21/211/23/23/2X1X2X5-120x1x2x3x4x5

bXBCBθ-12000C可得最優(yōu)解，目標(biāo)函數(shù)值maxZ=6，與用大M法的結(jié)果完全相同。單純形表與線性規(guī)劃問(wèn)題的討論

無(wú)可行解

通過(guò)大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。人工變量的值不能取零，說(shuō)明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程。此時(shí)線性規(guī)劃問(wèn)題的可行域?yàn)榭占?。?、求解下列線性規(guī)劃問(wèn)題解：首先將問(wèn)題化為標(biāo)準(zhǔn)型令，則

故引入人工變量，并利用大M法求解C

-3-2-1000-M-M

CB

XB

b

x1x2x3x4x5x6x7x8

θ

0-M-M

x4x7x8

643

1111000010-10-101001-100-101

6/1-3/1

Z’

-7M

-6-4M

-15-M

-3+M-2+M-1-2M0-M-M00

0-M-2

x4x7x2

343

1021010-110-10-101001-100-101

3/14/1-

Z’

Z’

-3+M0-3-M0-M-202-M

-3-M-2

x1x7x2

313

1021010-100-3-1-1

-11101-100-101

003-3M3-M-M1-M0-1

在以上最優(yōu)單純形表中，所有非基變量檢驗(yàn)數(shù)都小于零，但在該表中人工變量x7=1為基變量，所以原線性規(guī)劃不存在可行解。無(wú)最優(yōu)解

無(wú)最優(yōu)解與無(wú)可行解時(shí)兩個(gè)不同的概念。無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指線性規(guī)劃問(wèn)題的可行域?yàn)榭占?；無(wú)最優(yōu)解則是指線性規(guī)劃問(wèn)題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大（或者無(wú)窮?。o(wú)最優(yōu)解也稱為有限最優(yōu)解，或無(wú)界解。

判別方法：無(wú)最優(yōu)解判別定理在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中，若某單純形表的檢驗(yàn)行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解，可以可以例7、試用單純形法求解下列線性規(guī)劃問(wèn)題：解：引入松弛變量x3,x4化為標(biāo)準(zhǔn)型C

2200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02200因但所以原問(wèn)題無(wú)最優(yōu)解

退化解

當(dāng)線性規(guī)劃問(wèn)題的基本可行解中有一個(gè)或多個(gè)基變量取零值時(shí)，稱此基本可行解為退化解。產(chǎn)生的原因：在單純形法計(jì)算中用最小比值原則確定換出變量時(shí)，有時(shí)存在兩個(gè)或兩個(gè)以上相同的最小比值θ，那么在下次迭代中就會(huì)出現(xiàn)一個(gè)甚至多個(gè)基變量等于零。遇到的問(wèn)題：當(dāng)某個(gè)基變量為零，且下次迭代以該基變量作為換出變量時(shí)，目標(biāo)函數(shù)并不能因此得到任何改變（由旋轉(zhuǎn)變換性質(zhì)可知，任何一個(gè)換入變量只能仍取零值，其它基變量的取值保持不變）。通過(guò)基變換以后的前后兩個(gè)退化的基本可行解的坐標(biāo)形式完全相同。從幾何角度來(lái)解釋，這兩個(gè)退化的基本可行解對(duì)應(yīng)線性規(guī)劃可行域的同一個(gè)頂點(diǎn)，解決的辦法：最小比值原則計(jì)算時(shí)存在兩個(gè)及其以上相同的最小比值時(shí)，選取下標(biāo)最大的基變量為換出變量，按此方法進(jìn)行迭代一定能避免循環(huán)現(xiàn)象的產(chǎn)生（攝動(dòng)法原理）。例8、求解下述線性規(guī)劃問(wèn)題：解：引入松弛變量化標(biāo)準(zhǔn)型000-242-8030Z-5-60-420-805Z10001001x3

212060-2411x1

3321300-803x5

00-30-425-800Z11001001x7

00106-1-2410x1

30-1130-3-800x5

0-11001001x7

000106-1-2410x6

0000136-4-3210x5

0x7

x6