《系統(tǒng)工程》課件第03章 線性規(guī)劃

第3章

線性規(guī)劃3.1線性規(guī)劃問題及其數(shù)學(xué)模型3.2

線性規(guī)劃問題解的性質(zhì)3.3單純形法3.4二階段法（人工變量法）3.5單純形法小結(jié)3.6改進(jìn)單純形法3.7對偶線性規(guī)劃問題3.8運(yùn)輸問題3.9指派問題3.10整數(shù)規(guī)劃

本章主要介紹線性規(guī)劃分析法的基本原理，使學(xué)生掌握圖解法和單純形解法的程序及運(yùn)算，并借助現(xiàn)代化教學(xué)，能夠初步應(yīng)用線性規(guī)劃法解決最低成本的農(nóng)業(yè)生產(chǎn)資源最優(yōu)配合方式和最大收益的生產(chǎn)結(jié)構(gòu)問題。知識點(diǎn)聚焦第3章

線性規(guī)劃

系統(tǒng)工程的主要目標(biāo)是改造或建立系統(tǒng)，使系統(tǒng)的整體功能達(dá)到最優(yōu)。線性規(guī)劃是系統(tǒng)優(yōu)化的重要方法之一。它包括線性規(guī)劃、非線劃、整數(shù)規(guī)劃和動態(tài)規(guī)劃等。20世紀(jì)30年代初出現(xiàn)的線性規(guī)劃，到1947年丹茨基(G·B·Dantzig)發(fā)明單純形法之后，理論上才得到完善，應(yīng)用上也得到了迅速發(fā)展和推廣。隨著電子計(jì)算機(jī)的發(fā)展，成千上萬個約束條件和變量的大型線性規(guī)劃問題都可以求解。因此，無論從理論的成熟性看，還是從應(yīng)用的廣泛性看，線性規(guī)劃都是運(yùn)籌學(xué)的一個重要分支。它在工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、軍事和計(jì)劃管理等各方面都越來越得到廣泛地應(yīng)用。第3章

線性規(guī)劃3.1線性規(guī)劃問題及其數(shù)學(xué)模型

線性規(guī)劃(LinearProgramming，簡稱LP)是在第二次世界大戰(zhàn)前后逐漸發(fā)展和完善起來的運(yùn)籌學(xué)的一個重要分支。它的應(yīng)用范疇已滲透到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸及經(jīng)濟(jì)管理等諸多領(lǐng)域。小到一個小組的日常工作和計(jì)劃的安排，大至整個部門以至國民經(jīng)濟(jì)的計(jì)劃的最優(yōu)化方案的提出，都有它用武之地。正是由于它的適應(yīng)性強(qiáng)、應(yīng)用面廣、計(jì)算技術(shù)比較簡便等特點(diǎn)，使其成為現(xiàn)代管理科學(xué)的重要基礎(chǔ)和手段之一。

現(xiàn)實(shí)中什么樣的問題可以用線性規(guī)劃問題去求解?在解決實(shí)際問題的過程中，需將實(shí)際問題歸結(jié)為數(shù)學(xué)模型。什么是線性規(guī)劃的數(shù)學(xué)模型，它具有哪些特點(diǎn)，標(biāo)準(zhǔn)形式如何，等等，則是這節(jié)需要討論的問題。第3章

線性規(guī)劃3.1.1問題提出

在生產(chǎn)過程中，要想提高工作效率和經(jīng)濟(jì)效益，一般有兩種途徑：一是進(jìn)行技術(shù)改造，改進(jìn)生產(chǎn)手段和條件。比如增添設(shè)備、改進(jìn)工藝、挖掘潛力等等。另一條途徑是在生產(chǎn)手段和條件都不變的情況下，改善生產(chǎn)的組織和計(jì)劃管理，作出最優(yōu)安排，使生產(chǎn)手段和條件得到充分的利用。線性規(guī)劃方法就是解決后一類問題的工具。而這一類問題又分為兩個方面，一是在一定限制條件下，使得工作成果可能大；二是為完成既定任務(wù)，使資源消耗盡可能少。下面幾個問題可以說明這類問題。第3章

線性規(guī)劃【例3-1】某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機(jī)床需用A、B機(jī)器加工，加工時(shí)間分別為每臺2小時(shí)和1小時(shí)；生產(chǎn)乙機(jī)床需用A、B、C三種機(jī)器加工，加工時(shí)間為每臺各一小時(shí)。若每天可用于加工的機(jī)器時(shí)數(shù)分別為A機(jī)器10小時(shí)、B機(jī)器8小時(shí)和C機(jī)器7小時(shí)，問該廠應(yīng)生產(chǎn)甲、乙機(jī)床各幾臺，才能使總利潤最大？上述問題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)x1臺甲機(jī)床和x2乙機(jī)床時(shí)總利潤最大，則x1，x2應(yīng)滿足（目標(biāo)函數(shù)）(3-1)（約束條件）(3-2)3.1.1問題提出第3章

線性規(guī)劃這里變量x1，x2稱之為決策變量，(3-1)式被稱為問題的目標(biāo)函數(shù)，(3-2)中的幾個不等式是問題的約束條件，記為s.t.(即subjectto)。上述即為一規(guī)劃問題數(shù)學(xué)模型的三個要素。由于上面的目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題。

總之，線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。

在解決實(shí)際問題時(shí)，把問題歸結(jié)成一個線性規(guī)劃數(shù)學(xué)模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選取適當(dāng)?shù)臎Q策變量，是我們建立有效模型的關(guān)鍵之一。3.1.1問題提出第3章

線性規(guī)劃【例3-2】某工廠計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時(shí)及A，B兩種原材料的消耗，如表3-1所示。該工廠生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問如何安排計(jì)劃使工廠獲利最多?

所謂“如何安排生產(chǎn)計(jì)劃”，意指產(chǎn)品Ⅰ，Ⅱ各生產(chǎn)多少，每指定一次兩種產(chǎn)品的產(chǎn)量，就決定了一個生產(chǎn)方案，而一個生產(chǎn)方案決定一個獲利值。上述問題的實(shí)質(zhì)是尋找一個可行的生產(chǎn)方案(滿足資源和設(shè)備約束)，使得工廠的獲利值達(dá)到最大。3.1.1問題提出第3章

線性規(guī)劃

解：這個問題可以用以下的數(shù)學(xué)語言來描述。

假設(shè)x1，x2分別表示產(chǎn)品Ⅰ，Ⅱ的產(chǎn)量?？尚械纳a(chǎn)方案要考慮不能超出設(shè)備的有效臺時(shí)數(shù)，即可用不等式表示為：x1+2x2≤8，同時(shí)，還要考慮滿足原材料A，B的資源約束條件，即用不等式表示為4x1≤16，4x2≤12。

對于產(chǎn)量x1，x2，該工廠的獲利值f可表示為f=2x1+3x2。工廠的目標(biāo)是在滿足設(shè)備能力和原材料限制的條件下，如何確定產(chǎn)量x1和x2，使工廠的獲利最大。

綜上所述，安排生產(chǎn)計(jì)劃問題可歸納為進(jìn)行求解。3.1.1問題提出第3章

線性規(guī)劃由此，把這類實(shí)際問題轉(zhuǎn)換為數(shù)學(xué)模型可歸結(jié)為三個基本步驟。

(1)確定決策變量，如【例3-2】中產(chǎn)品Ⅰ，Ⅱ的產(chǎn)量確定。決策變量必須是可控制的，通常用x1，x2，?，xn來表達(dá)。

(2)恰當(dāng)?shù)乇磉_(dá)所要追求的目標(biāo)(目的)，如【例3-1】中工廠追求的最大獲利。目標(biāo)通常用決策變量的函數(shù)來表達(dá)，稱為目標(biāo)函數(shù)。目標(biāo)可以是單一的，也可以是多個的，但線性規(guī)劃問題中一般只討論目標(biāo)單一的情形。

(3)把現(xiàn)實(shí)中的各種限制用含有決策變量x1，x2，?，xn的數(shù)學(xué)關(guān)系式來表達(dá)，稱為約束條件，諸如資源限制、能力限制等。3.1.1問題提出第3章

線性規(guī)劃【例3-3】(下料問題)。某工廠制造一種機(jī)床，每臺機(jī)床需A，B，C三種不同長度的軸各一根，其毛坯長度：A為2.9m，B為2.1m，C為1.5m，它們用同一種圓鋼來下料，每根圓鋼長為7.4m。要造100臺機(jī)床，問如何下料最好?試建立其數(shù)學(xué)模型(不考慮下料截口損耗）。解

將各種可能的下料方案排列程表3.2，設(shè)圓鋼總數(shù)為f根，則由題意有(3-3)下料方案其中：3.1.1問題提出第3章

線性規(guī)劃上述模型即為所求模型。通過分析表3-2，發(fā)現(xiàn)其中的方案3、5、7、8的料頭過長，不經(jīng)濟(jì)，如果把它們舍棄，對剩下的4種方案進(jìn)行搭配，仍然可以滿足題意。為此可以將上述模型簡化為下列模型(保持變量下標(biāo)不變)。即(3-4)3.1.1問題提出第3章

線性規(guī)劃【例3-4】(運(yùn)輸問題)。設(shè)有甲、乙、丙3個倉庫，存有某種貨物分別為7t、4t和9t?，F(xiàn)在要把這些貨物分別送A，B、C、D這4個商店，其需要量分別為3t、6t、5t和6t，各倉庫到各商店的每噸運(yùn)費(fèi)以及收、發(fā)總量見表3-3。

現(xiàn)在要確定一個運(yùn)輸方案：從哪一個倉庫運(yùn)多少貨到哪一個商店，使得各個商店都能得到貨物需要量，各個倉庫都能發(fā)完存貨，而且總的運(yùn)輸費(fèi)用最低?試建立其數(shù)學(xué)模型。3.1.1問題提出第3章

線性規(guī)劃

解

記總運(yùn)費(fèi)為z設(shè)xij為i倉庫到j(luò)商店的貨物量，其中i=1，2，3分別代表甲、乙、丙倉庫，j=1，2，3，4分別代表A，B，C，D商店，則根據(jù)題意

上述各例，都是要求一組非負(fù)變量，在滿足一組線性等式或線性不等式的前提下，使一線性函數(shù)取得最大值或最小值，這一類問題就稱為線性規(guī)劃問題。(3-5)3.1.1問題提出第3章

線性規(guī)劃將上述問題得出的數(shù)學(xué)表達(dá)式加以概括和抽象，就可得到線性規(guī)劃問題的數(shù)學(xué)模型為求一組變量xj，j=1，2，...，n，滿足條件使函數(shù)取得最大值或最小值。如果簡寫，則線性規(guī)劃問題的數(shù)學(xué)模型可以表示為(3-6)(3-7)(3-8)3.1.1問題提出第3章

線性規(guī)劃式(3-8)稱為目標(biāo)函數(shù)，式(3-9)稱為約束條件。式中max(min)f：目標(biāo)函數(shù)f取最大（最?。┲?；xj：決策變量，又稱為生產(chǎn)活動或活動方式；cj：決策變量在目標(biāo)函數(shù)中的系數(shù)，又稱為利益系數(shù)、價(jià)值或效果系數(shù)；aij：決策變量在約束條件中的系數(shù)，又稱為投入產(chǎn)出系數(shù)或技術(shù)系數(shù)bi：資源限制量；n：決策變量的個數(shù)；m：約束條件(不包括非負(fù)約束條件)的個數(shù)。

把滿足約束條件式(3-2)的任意一組解稱為線性規(guī)劃間題的可行解，使得目標(biāo)函數(shù)f取得最優(yōu)值的可行解稱為線性規(guī)劃問題的最優(yōu)解。如何求得線性規(guī)劃問題的最優(yōu)解，就是本章索要討論的中心問題。(3-9)3.1.1問題提出第3章

線性規(guī)劃3.1.2線性規(guī)劃問題數(shù)學(xué)模型的一般形式從例【3-1】~【3-4】的線性規(guī)劃可以看出，它們具有以下共同特征。(1)每一個問題都用一組未知數(shù)(x1，x2，?，xn)表示某一方案，這組未知數(shù)的一組定值就代表一個具體方案。通常要求這些未知數(shù)取值是非負(fù)的。(2)存在一定的限制條件(稱為約束條件，也可用縮寫s.t.表示)，這些限制條件都可以用一組線性等式或線性不等式來表達(dá)。(3)都有一個目標(biāo)要求，并且這個目標(biāo)可表示為一組未知數(shù)的線性函數(shù)(稱為目標(biāo)函數(shù))。按研究的問題不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或者最小化。一般來講，這類問題可用數(shù)學(xué)語言描述如下

(3-10)s.t.(3-11)第3章

線性規(guī)劃

這就是線性規(guī)劃的數(shù)學(xué)模型。式(3-10)方程稱為目標(biāo)函數(shù)，式(3-11)與式(3-12)稱為約束條件，其中，式(3-12)也稱為非負(fù)條件。也是線性規(guī)劃問題的一般形式?？珊唽憺椋?3-12)(3-13)(3-14)3.1.2線性規(guī)劃問題數(shù)學(xué)模型的一般形式第3章

線性規(guī)劃3.1.3線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式由例【3-1】~【3-4】可知，線性規(guī)劃問題可能有各種不同的形式。目標(biāo)函數(shù)，有的要求實(shí)現(xiàn)最大化，有的要求最小化；約束條件可以是“≤”形式的不等式，也可以是“≥”形式的不等式，還可以是等式。這種多樣性給求解問題的討論和求解程序的標(biāo)準(zhǔn)化帶來不便。在所有bi≥0，i=1，2，…，n的前提下，有必要化成規(guī)范形式。又稱標(biāo)準(zhǔn)形式。為了求解的方便，就需要把線性規(guī)劃問題的一般數(shù)學(xué)形式化成如下標(biāo)準(zhǔn)形式。即：(3-15)s.t.(3-16)(3-17)第3章

線性規(guī)劃(3-18)(3-19)進(jìn)一步可用矩陣型式表示：(3-20)s.t.(3-21)3.1.3線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式第3章

線性規(guī)劃標(biāo)準(zhǔn)型的特征：目標(biāo)函數(shù)最大化；約束條件為等式；右端相為非負(fù)值；決策變量非負(fù)值。目標(biāo)函數(shù)轉(zhuǎn)化：1)目標(biāo)函數(shù)為求最小值若原問題的目標(biāo)函數(shù)為minf，則令，于是有約束條件的轉(zhuǎn)化：2)含有不等式約束條件這類型式往往有兩種情形：若原問題的第i個約束條件為則可在不等式的左邊加上一個新的變量使其變?yōu)榈仁郊s束，即稱為松弛變量。如：(3-23)(3-22)3.1.3線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式第3章

線性規(guī)劃則可以通過引進(jìn)非負(fù)變量xn+1使兩邊相等，即這里xn+1稱為松弛變量。若原問題的第i個約束條件為則可在不等式的左邊減去一個新的變量使其變?yōu)榈仁郊s束，即稱為剩余變量，也稱為松弛變量。如：這里xn+1稱為剩余變量。

應(yīng)該指出，引入松弛變量和剩余變量后，對目標(biāo)函數(shù)無任何影響，因?yàn)樗鼈冊谀繕?biāo)函數(shù)中的系數(shù)全為零。(3-24)(3-25)則(3-26)3.1.3線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式第3章

線性規(guī)劃3)所有變量要求非負(fù)還需要提到一點(diǎn)的是，在標(biāo)準(zhǔn)型中要求bi≥0(i=1，2，?m)，如果存在bi<0的情形，則可在約束方程式兩邊各乘上“-1”號，使所有bi≥0得到滿足。如：4)含有自由變量，及非負(fù)約束的變量若原問題中第j個變量xj沒有非負(fù)約束，則xj叫自由變量。自由變量可用兩個非負(fù)變量之差代換，即令

，并代入約束條件和目標(biāo)函數(shù)中，便可消去自由變量。這也是現(xiàn)實(shí)中，有些變量可能從物理意義或經(jīng)濟(jì)意義上講沒有非負(fù)要求。為了滿足標(biāo)準(zhǔn)型對變量非負(fù)的要求所做的變換。(3-27)3.1.3線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式第3章

線性規(guī)劃【例3-5】將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式解：目標(biāo)函數(shù)屬于求極小值，約束中有大于、小于等情況。按前述標(biāo)準(zhǔn)化方法進(jìn)

行轉(zhuǎn)換。(1)令

，或者下成

。(2)在第一個約束條件中引入松弛變量x6，第2個約束條件中引入剩余變量x7。S.t.(3)對第三個約束條件兩邊同乘以-1。(4)將引入的變量代入目標(biāo)函數(shù)和約束條件，并令

，把求最小變成求最大。3.1.3線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式第3章

線性規(guī)劃于是有：解此規(guī)劃問題，得到

和

的值，則

，

，從而可得到原問題的解。3.1.3線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式第3章

線性規(guī)劃3.1.4. 線性規(guī)劃問題解的概念

前一節(jié)介紹了線性規(guī)劃的數(shù)學(xué)模型，建立數(shù)學(xué)模型的目的自然是為了求解，而要找到好的求解方法，首先必須對模型的解及其基本性質(zhì)有一個清楚的了解。

對于一般線性規(guī)劃問題(3-28)(3-29)稱滿足式(3-29)的點(diǎn)(或向量)X為該問題的解(solution)；而同時(shí)又滿足式(3-29)的第二式，則稱點(diǎn)X為可行解(feasiblesolution)；所有可行解組成的集合稱為可行域(feasibleregion)或可行解集?？尚杏蛏蠞M足式(3-28)的點(diǎn)稱為最優(yōu)解(optimalsolution)，最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值。第3章

線性規(guī)劃

在討論線性規(guī)劃問題的解法之前，先來介紹一下標(biāo)準(zhǔn)形式線性規(guī)劃問題解的概念。對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其約束條件(3-29)為下列線性方程組：(3-30)

在此約束條件中，前m個等式構(gòu)成線性方程組，對此方程組，若m=n，且系數(shù)行列式不為零，則方程組有唯一一組解，故不存在優(yōu)化問題。若m≠n，一般來說m<n，如果方程組的系統(tǒng)矩陣的秩為m，則該方程組有無窮多個解。假設(shè)前m個變量的系數(shù)列向量是線性獨(dú)立的，構(gòu)成的系數(shù)矩陣3.1.4. 線性規(guī)劃問題解的概念第3章

線性規(guī)劃

稱為線性問題的一個基，稱為基向量，稱與基向量對應(yīng)的變量為基變量，其他變量稱為非基變量。若令非基變量等于零，則可求得一個解為這樣的解稱為基本解，它的非零變量的個數(shù)不大于秩m?；窘獠灰欢ǘ际强尚械?。若基本解同時(shí)滿足非負(fù)條件，就稱為基本可行解，對應(yīng)于基本可行解的基稱為可行基。若基本可行解中的非零變量的個數(shù)小于m，即基變量出現(xiàn)零值時(shí)，則此基本可行解稱為退化的基本可行解。當(dāng)其非零變量的個數(shù)等于m，即基變量均為正值時(shí)，則此基本可行解稱為非退化的基本可行解。3.1.4. 線性規(guī)劃問題解的概念第3章

線性規(guī)劃顯然，如果基矩陣B為m階單位陣，則問題的一個基本可行解為

線性規(guī)劃問題的一個基本可行解，對應(yīng)于可行域上的一個頂點(diǎn)。若線性規(guī)劃問題有最優(yōu)解，則必定在某個頂點(diǎn)處得到。雖然頂點(diǎn)數(shù)目是有限的，它不超過

，采用枚舉法找出所有基本可行解，然后一一比較，最終可以找到最優(yōu)解。但當(dāng)m，n相當(dāng)大時(shí)，這種辦法是行不通的。所以，需用另一種更好的方法-----單純形法。3.1.4. 線性規(guī)劃問題解的概念第3章

線性規(guī)劃3.2

線性規(guī)劃問題解的性質(zhì)3.2.1

幾何意義上的幾個基本概念

對一個線性規(guī)劃問題，建立數(shù)學(xué)模型之后，面臨著如何求解的問題。這里先介紹含有兩個未知變量的線性規(guī)劃問題的圖解法，它簡單直觀。這里通過圖像法來直觀的了解線性規(guī)劃問題的最優(yōu)解。圖解法的步驟：步驟1：確定可行域。Step1：繪制約束等式直線，確定由約束等式直線決定的兩個區(qū)域中哪個區(qū)域?qū)?yīng)著由約束條件所定義的正確的不等式。通過畫出指向正確區(qū)域的箭頭，來說明這個正確區(qū)域。Step2：確定可行域。步驟2：畫出目標(biāo)函數(shù)的等值線，標(biāo)出目標(biāo)值改進(jìn)的方向。步驟3：確定最優(yōu)解。用圖示的方式朝著不斷改進(jìn)的目標(biāo)函數(shù)值的方向，移動目標(biāo)函數(shù)的等值線，直到等值線正好接觸到可行域的邊界。等值線正好接觸到可行城邊界的接觸點(diǎn)對應(yīng)著線性優(yōu)化模型的最優(yōu)解。第3章

線性規(guī)劃【例3-6】求解線性規(guī)劃s.t.解：在二維平面坐標(biāo)中，每個線性不等式約束的點(diǎn)集是一個半平面（由一條直線分界），通常一個二維線性規(guī)劃問題的可行域如果是有界的，則是一個多邊形圍成的區(qū)域。Step1．先在平面直角坐標(biāo)系

里畫出上述線性規(guī)劃的可行域Ｒ。事實(shí)上在約束條件中，每個線性等式代表平面上一條直線，這直線將坐標(biāo)平面分成兩部分，于是每個線性不等式代表一個半平面。本例中五個線性不等式代表的五個半平面的交，就是可行域Ｒ，顯然它是一個凸多邊形，這個凸多邊形有五個頂點(diǎn)，它們分是Ｏ（０，０），Ａ（０，７），Ｂ（５，７），Ｃ（８，４），Ｄ（８，０），如圖3-1。3.2.1

幾何意義上的幾個基本概念第3章

線性規(guī)劃圖3-1【例3-6】題解的圖示Step2．求解線性規(guī)劃，就是要在上述凸多邊形Ｒ中找一點(diǎn)

，使目標(biāo)函數(shù)取最大值。對任意固定的常數(shù)Ｃ，直線上的每點(diǎn)都有相同的目標(biāo)函數(shù)值Ｃ，故該直線也稱為“等值線”。當(dāng)Ｃ變化時(shí)，得出一族相互平行的等值線，這些等值線中有一部分與可行域相交。要在凸多邊形即可行域Ｒ中找這樣的點(diǎn)，使它所在的等值線具有最大值Ｃ。當(dāng)Ｃ<０時(shí)，直線

與Ｒ不相交；當(dāng)Ｃ＝０時(shí)，直線

與Ｒ有唯一交點(diǎn)，即頂點(diǎn)（０，０）；當(dāng)Ｃ由０增大時(shí)，等值線平行向右上方移動，與Ｒ相交于一線段；當(dāng)Ｃ增至一定程度時(shí)，等值線與可行域Ｒ只有唯一交點(diǎn)，即頂點(diǎn)（5，7），這時(shí)Ｃ＝9.8；若Ｃ繼續(xù)增大，等值線與Ｒ將不再有交點(diǎn)。由此可見，頂點(diǎn)（5，7）是使Ｒ中目標(biāo)函數(shù)達(dá)到最大值的點(diǎn)，于是線性規(guī)劃有唯一3.2.1

幾何意義上的幾個基本概念第3章

線性規(guī)劃解

，這時(shí)，f*＝maxf＝9.8。若將例3中求目標(biāo)函數(shù)的最大值改為求最小值，即求

約束條件不變。這時(shí)，令直線族

中的C不斷減小，等值線將向左下方平行移動。當(dāng)C＝0時(shí)，等值線與可行域只有唯一交點(diǎn)即頂點(diǎn)(0，0)，若C繼續(xù)減小，等值線與Ｒ將不再有交點(diǎn)，于是線性規(guī)劃有最優(yōu)解：

，這時(shí)，f*＝minf＝0。從上面的圖解法中可以看出：兩變量線性規(guī)劃的可行域一定是一個凸多邊形，線性規(guī)劃如果有解，則該解一定可以在凸多邊形的頂點(diǎn)上達(dá)到。

有時(shí)線性規(guī)劃的最優(yōu)解不是唯一的。例如我們將【例3-6】中線性規(guī)劃的目標(biāo)函數(shù)改為,而約束條件不變，這時(shí)，對直線族

，令C不斷增大，當(dāng)C增至10.8時(shí)，等值線與Ｒ相交于線段BC，該線段的兩個端點(diǎn)是Ｒ的頂點(diǎn)，當(dāng)C繼續(xù)增大時(shí)，等值線與R不再相交，故這時(shí)線段BC上的點(diǎn)都是線性規(guī)劃的最優(yōu)解，最優(yōu)值

由此可見：若有兩個頂點(diǎn)是最優(yōu)解，則這兩個頂點(diǎn)連線上所有的點(diǎn)都是最優(yōu)解。線性規(guī)劃的可行域可能是空集，這意味著約束條件互相矛盾，線性規(guī)劃無可行解。3.2.1

幾何意義上的幾個基本概念第3章

線性規(guī)劃【例3-7】

求解線性規(guī)劃(無可行解)解：因約束條件中前兩個不等式相互矛盾，線性規(guī)劃無可行解（見圖3-2）。圖3-2【例3-7】解的圖示

注意：有時(shí)線性規(guī)劃的可行域無界，這時(shí)線性規(guī)劃的解可能存在，也可能沒有有界的最優(yōu)解。3.2.1

幾何意義上的幾個基本概念第3章

線性規(guī)劃【例3-8】

求解線性規(guī)劃(無界解)解：該線性規(guī)劃的可行域Ｒ無界（圖3-3），用圖解法可以看出，該線性規(guī)劃無有界最優(yōu)解。圖3-3【例3-8】解的圖示3.2.1

幾何意義上的幾個基本概念第3章

線性規(guī)劃注意：本例中，若改求目標(biāo)函數(shù)的最小值，則它仍有最優(yōu)解：,這時(shí)，f*＝minf＝0。通過圖解法看到，線性規(guī)劃問題的所有可行解構(gòu)成的可行域，一般是凸多邊形的(有時(shí)可行域是無界的)。若存在最優(yōu)解，則一定在可行域的某頂點(diǎn)上得到；若在兩個頂點(diǎn)上同時(shí)得到最優(yōu)解，則這兩頂點(diǎn)連線上的任一點(diǎn)都是最優(yōu)解。若可行解無界，則可能發(fā)生無最優(yōu)解的情況；若無可行域，自然也就既無可行解也無最優(yōu)解。因此有如下結(jié)論：（1）線性規(guī)劃問題的所有可行解組成的可行域是一凸集，即可行域上任意兩點(diǎn)之間的連線都可在可行域內(nèi)。（2）若一個線性規(guī)劃問題存在最優(yōu)解，則至少有一個最優(yōu)解在可行域的頂點(diǎn)上達(dá)到；若在兩個頂點(diǎn)上同時(shí)達(dá)到最優(yōu)，則這兩頂點(diǎn)連線上的任一點(diǎn)都是最優(yōu)解，這時(shí)稱有無窮多個最優(yōu)解。（3）若可行域呈現(xiàn)無界區(qū)域，則可能有最優(yōu)解，也可能出現(xiàn)最優(yōu)解無界的情形，這時(shí)稱最優(yōu)解不存在或無最優(yōu)解。（4）若可行域?yàn)榭占?，這時(shí)無可行解，當(dāng)然也就無最優(yōu)解。上述結(jié)論對于含有兩個以上變量的線性規(guī)劃問題同樣適用。圖解法雖然直觀、簡便，但只能用于兩個，最多3個變量的線性規(guī)劃問題，當(dāng)變量個數(shù)超過3個時(shí)，用圖解法就很難處理了。因此在后面將要介紹線性規(guī)劃問題的一般解法單純形法。3.2.1

幾何意義上的幾個基本概念第3章

線性規(guī)劃推廣到線性規(guī)劃問題的基本性質(zhì)：(1)線性規(guī)劃問題的可行域如果非空，則是一個凸集-凸多面體。(2)如果線性規(guī)劃問題有最優(yōu)解，那么最優(yōu)解可在可行域的頂點(diǎn)中確定。(3)如果可行域有界，且可行域只有有限個頂點(diǎn)，則問題的最優(yōu)解必存在，并在這有限個頂點(diǎn)中確定。(4)最優(yōu)解可由最優(yōu)頂點(diǎn)處的有效約束形成的方程組的解確定。3.2.1

幾何意義上的幾個基本概念第3章

線性規(guī)劃3.2.2線性規(guī)劃問題的基本定理

下面將解兩變量線規(guī)劃問題時(shí)用圖解法得出的結(jié)論推廣到一般的情形。為此，先介紹凸集的概念。

【凸集定義】設(shè)Ｋ是ｎ維歐氏空間的一個點(diǎn)集，對Ｋ中任意兩點(diǎn)Ｘ1，Ｘ2∈Ｋ，和任意實(shí)數(shù)

，若都有

，則稱Ｋ為凸集。設(shè)Ｘ1，Ｘ2是ｎ維歐氏空間中的兩個點(diǎn)，Ｘ是它們連線上的任意一點(diǎn)，且有向線段之比

，顯然由

，可推出：

，故

時(shí)，

是Ｘ1，Ｘ2連線上的一點(diǎn)，稱為Ｘ1，Ｘ2的凸組合。于是Ｋ是凸集的幾何意義是，若Ｘ1，Ｘ2是Ｋ中任意兩點(diǎn)，那么Ｘ1，Ｘ2連線上的點(diǎn)也是Ｋ中的點(diǎn)。圖3-4幾種凸集概念的示例

實(shí)心圓、實(shí)心球體、實(shí)心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。例如三角形、凸多邊形、四面體、凸多面體、園、球等都是凸集。如下圖所示。第3章

線性規(guī)劃其中，(a)、(b)是凸集，(c)不是凸集，(d)是兩個圖集的交集，也是凸集。

【頂點(diǎn)定義】設(shè)Ｋ是凸集，Ｘ∈Ｋ，且Ｘ不能用Ｋ中不同的兩點(diǎn)Ｘ1，Ｘ2∈Ｋ表示成

的線性組合，故

的形式，則稱Ｘ為Ｋ的一個頂點(diǎn)(或極點(diǎn))。例如：三角形的頂點(diǎn)，四面體的頂點(diǎn)，園周和球面上任意一點(diǎn)，都是凸集的頂點(diǎn)?？梢詫勺兞烤€性規(guī)劃圖解法中得到的結(jié)果推廣到一般線性規(guī)劃中去：（1）線性規(guī)劃的可行域Ｒ是凸集；（2）線性規(guī)劃若有最優(yōu)解，則最優(yōu)解一定可以在頂點(diǎn)上達(dá)到；（3）若有兩個或兩個以上的頂點(diǎn)都是線性規(guī)劃的最優(yōu)解，則這些點(diǎn)組成的凸組合也是最優(yōu)解；（4）線性規(guī)劃可行域頂點(diǎn)的個數(shù)是有限的，因此線性規(guī)劃如果有最優(yōu)解的話，總可以在有限個頂點(diǎn)中找到最優(yōu)解。

3.2.2線性規(guī)劃問題的基本定理

丹茨格的著名的單純形法，就是根據(jù)上述原理，從一個初始的頂點(diǎn)開始，通過有限步，就能找到線性規(guī)劃的最優(yōu)頂點(diǎn)。幾個基本定理（這里不作證明，有興趣可參考相關(guān)資料）：【定理1】若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。（即連接線性規(guī)劃問題任意兩個可行解的線段上的點(diǎn)仍然是可行解。)【定理2】線性規(guī)劃問題的基可行解x對應(yīng)線性規(guī)劃問題可行域的頂點(diǎn)?！径ɡ?】線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。第3章

線性規(guī)劃3.2.2線性規(guī)劃問題的基本定理第3章

線性規(guī)劃3.3單純形法

求解線性規(guī)劃問題的單純形方法(SimplexMethod)，是由美國數(shù)學(xué)家G.B.Dantzig于1947年首先提出來，至今這一數(shù)學(xué)方法仍然是解線性規(guī)劃問題的行之有效的方法。它是從可行域的一個基本可行解(極點(diǎn))出發(fā)，判別它是否已是最優(yōu)解，如果不是，尋找下一個基本可行解，并使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找到最優(yōu)解或判定問題無界為止。3.3.1單純形法思路

單純形法求解線性規(guī)劃的思路：一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程個數(shù)，這時(shí)有不定的解。但可以從線性方程組中找出一個個的單純形，每一個單純形可以求得一組解，然后再判斷該解使目標(biāo)函數(shù)值是增大還是變小，決定下一步選擇的單純形。這就是迭代，直到目標(biāo)函數(shù)實(shí)現(xiàn)最大值或最小值為止。注意：單純形是指0維中的點(diǎn)，一維中的線段，二維中的三角形，三維中的四面體，n維空間中的有n+1個頂點(diǎn)的多面體。例如在三維空間中的四面體，其頂點(diǎn)分別為(0，0，0)，(1，0，0)，(0，1，0)，(0，0，1)。具有單位截距的單純形的方程是Σxi≤1，并且xi≥0，i=1，2，?，m。這樣問題就得到了最優(yōu)解，先舉一例來說明。第3章

線性規(guī)劃【例3-9】對例3.2線性規(guī)劃模型進(jìn)行求解。

解：第一步：將一般形式的線性規(guī)劃問題化成標(biāo)準(zhǔn)型。在約束條件中，引入松弛變量

，有(3-31)第二步：確定初始基本可行解

為確定初始基本可行解，首先要找出初始可行基。由3.1.4節(jié)可知，如果在約束方程的系數(shù)矩陣中能找到m個線性無關(guān)的單位向量，就能很容易地得到問題的一個初始基本可行解。若原問題的約束條件（不包括非負(fù)約束條件，下同）為一組“≦”不等式，標(biāo)準(zhǔn)化后，第3章

線性規(guī)劃可以松弛變量作為基變量，其余的變量為非基變量，令非基變量等于零，便可立即得到一個初始基本可行解。對于本例，

為基變量，

為非基變量，x1=x2=0。則問題的一個初始可行解為X=(0081612)T。此時(shí)的目標(biāo)函數(shù)值

，這意味著工廠沒有進(jìn)行生產(chǎn)，對應(yīng)的利潤為零。這也正是生產(chǎn)規(guī)劃的開始。

若原問題的約束條件為一組“≧”不等式或一組等式或3種約束組合，標(biāo)準(zhǔn)化后，如果約束方程的系數(shù)矩陣中不存在m個線性無關(guān)的單位向量，就要設(shè)法構(gòu)成m個不同的單位列向量，有關(guān)這個問題將在后面進(jìn)行討論。

為明顯起見，把基變量放在等式左邊，非基變量放在等式右邊，由式(3-31)得

(3-32)相應(yīng)的目標(biāo)函數(shù)用非基變量表示為：

從目標(biāo)函數(shù)表達(dá)式可以看出，非基變量x1,x2的系數(shù)都是正數(shù)，因此增加x1或x2均可是目標(biāo)函數(shù)f增加，所以只要在目標(biāo)函數(shù)的表達(dá)式中還存在有正系數(shù)的非基變量，就表明目標(biāo)函數(shù)還有增加可能，就需要將非基變量進(jìn)行對換。單純形法的實(shí)質(zhì)上就是進(jìn)行基變量和非基變量的代換過程。新進(jìn)入左邊的變量叫換入變量，被代換到右邊的變量叫換出第3章

線性規(guī)劃變量。每完成一次代換，就是一次迭代，而對應(yīng)的目標(biāo)函數(shù)值就相應(yīng)地有所增加，至少也與代換前相同。第三步：確定換入換出變量，進(jìn)行第一次迭代。

在進(jìn)行單純形發(fā)法迭代時(shí)，每次只能代換一個變量。一般選擇正系數(shù)最大的那個非基變量為換入變量，并成為新的基變量，本例中，x2為換入變量。同時(shí)，還要從原來的基變量中確定出一個為換出變量，成為新的非基變量。換出變量的確定要經(jīng)過計(jì)算換人變量的最大步長。x2作為換入變量，由于受到有關(guān)資源的限制，是不能隨意安排調(diào)整的，把資源允許的最大調(diào)整量叫最大步長。故當(dāng)x1=0時(shí)，要保證x3，x4

，x5>=0由(3-32)有即

顯然，為同時(shí)滿足以上3個條件，x2的調(diào)整量只能是，即x2=3為調(diào)整的最大步長。因此，x5為換出變量。

第3章

線性規(guī)劃

這樣一來就得到了新的基變量x3，x4，x2，新的非基變量為x1，x5。此時(shí)，需要把式(3-32)中x1，x5的位置對換，即由(3-32)中第3式得將上式代入(3-32)中，消去x2，有(3-33)

也將目標(biāo)函數(shù)中的基變量用非基變量代換，得到調(diào)整后的目標(biāo)函數(shù)為：

這樣，f中，x1為正系數(shù)表明：還有潛力可挖，沒有達(dá)到最大值；x5為負(fù)系數(shù)表明：若要剩余資源發(fā)揮作用，就必須支付附加費(fèi)用。當(dāng)x5=0時(shí)，即不再利用這些資源。

此時(shí)，當(dāng)非基變量x1=x5=0時(shí)，得到另一個基本可行解為X1=(032160)T

目標(biāo)函數(shù)值為f=9，由此可見，調(diào)整x2后，目標(biāo)函數(shù)值增加了9。從目標(biāo)函數(shù)的表達(dá)式可看出，非基變量x1的系數(shù)為正，說明調(diào)整x1將會使目標(biāo)函數(shù)繼續(xù)增加，X1不是規(guī)劃問題的最優(yōu)解。第3章

線性規(guī)劃第四步：確定新的換入換出變量，進(jìn)行第二次迭代。

由于非基變量x5在目標(biāo)函數(shù)中的系數(shù)為-3/4，調(diào)整x5將使目標(biāo)函數(shù)值減少，又因目標(biāo)函數(shù)中只有x1的系數(shù)為正，于是便知x1是新的換入變量，而新的換出變量還要通過計(jì)算最大的調(diào)整步長來確定。故當(dāng)x5

=0，要保證

x3，x4

，x5>=0，有→x1的調(diào)整最大步長為x1=min{24-}=2x1的最大步長是由式(3-33)中的第1個方程確定的，對應(yīng)的基變量x3為新的換出變量，由(3-33)中的第1式得

，將其帶入(3-33)中的第2、第3式，消去x1，有

(3-34)調(diào)整后的目標(biāo)函數(shù)為第3章

線性規(guī)劃

當(dāng)x3=x5=0時(shí)，可得到一個新的基本可行解為X2=(23080)T

對應(yīng)的目標(biāo)函數(shù)值為13。由于目標(biāo)函數(shù)中非基變量x5的系數(shù)大于0，所以，即目前的基可行解不是最優(yōu)解，x5為換入變量，同樣用步長確定換出變量。故當(dāng)x3=0，要保證

x1，x4

，x2>=0，有→(3-35)X5的調(diào)整最大步長為x5=min{-412}=4X5的最大步長是由式(3-33)中的第2個方程確定的，對應(yīng)的基變量x4為新的換出變量，由(3-34)中的第2式得代入上式得令x3，x4為零，最優(yōu)解為：X3=（4，2，0，0，4）T第3章

線性規(guī)劃可以看出，目標(biāo)函數(shù)中的系數(shù)均為負(fù)，故f=14為最優(yōu)解。3.3.2單純形表解法

上面的引例說明了用單純形法解線性規(guī)劃問題的基本思路和理論依據(jù)。但在實(shí)際求解中，用上述方法比較麻煩，而且容易出錯，故多采用單純形表解法，下面仍以上面的例子來說明表上求解的步驟和方法，并引出一般線性規(guī)劃問題的解法。第一步：標(biāo)準(zhǔn)化(見前解法第1步)。第二步：找出初始基變量，并將目標(biāo)函數(shù)中的基變量用非基變量代替。1)檢查約束方程的系數(shù)矩陣是否含有機(jī)階單位陣。若沒有，則設(shè)法構(gòu)造。m階單位陣對應(yīng)的變量為基變量，其余變量為非基變量。上面的問題3階單位矩陣對應(yīng)的變量x3，x4，x5為基變量，x1，x2為非基變量。2)檢查目標(biāo)函數(shù)申是否含有基變量，如果有，則用非基變量加以代換。上面問題的目標(biāo)函數(shù)中不含有基變量，故不需代換。第三步：作初始單純形表。

初始單純形表就是把線性規(guī)劃模型中的變量和相關(guān)的系數(shù)規(guī)則地排成一種表格，它和線性規(guī)劃模型具有一一對應(yīng)的關(guān)系。第3章

線性規(guī)劃

對于上面的問題，可將目標(biāo)函數(shù)寫成類似于約束方程的形式，即

為了便于理解計(jì)算關(guān)系，現(xiàn)設(shè)計(jì)一種計(jì)算表，稱為單純形表，其功能與增廣矩陣相似，下面來建立這種計(jì)算表。

將標(biāo)準(zhǔn)式約束條件與目標(biāo)函數(shù)組成n+1個變量，m+1個方程的方程組。(3-36)為了便于迭代，可將上式方程組下稱增廣矩陣形式：

(3-37)

若將f看作不參與基變換的基變量，它與x1，x2，?，xm的系數(shù)構(gòu)成一個基，這時(shí)可采用行初等變換將c1，c2，?，cm變換為零，使其對應(yīng)的系數(shù)矩陣為單位矩陣。得到第3章

線性規(guī)劃(3-38)依據(jù)增廣矩陣，設(shè)計(jì)單純形表如下：表(3-4)單純形法XB

列中填入基變量，這里是x1，x2，?，xm；CB

列中填入基變量的價(jià)值系數(shù)，這里是c1，c2，?，cm；它們是與基變量相對應(yīng)的；第3章

線性規(guī)劃b列中填入約束方程組右端的常數(shù)；cj行中填入基變量的價(jià)值系數(shù)c1，c2，?，cn；θi列的數(shù)字是在確定換入變量后，按θ規(guī)則計(jì)算后填入；最后一行稱為檢驗(yàn)數(shù)行，對應(yīng)各非基變量xj的檢驗(yàn)數(shù)是表1-2稱為初始單純形表，沒迭代一步構(gòu)造一個新單純形表。第3章

線性規(guī)劃3.3.3單純形表解步驟第一步：建立線性規(guī)劃的數(shù)學(xué)模型，并使其標(biāo)準(zhǔn)化。標(biāo)準(zhǔn)化的要求為：(1)目標(biāo)函數(shù)化成求最大值問題；(2)約束條件均表達(dá)為等式關(guān)系(必要時(shí)引入松弛變量和剩余變量)；(3)模型存在一個初始可行基———單位矩陣(必要時(shí)引入人工變量)。第二步：找出初始可行基，確定初始基可行解，建立初始單純形表。第三步：檢驗(yàn)各非基變量xj的檢驗(yàn)數(shù)是則已得到最優(yōu)解，可停止計(jì)算。否則轉(zhuǎn)入下一步。第四步：在σj>0，j=m+1，?，n中，若有某個σk對應(yīng)xk的系數(shù)列向量Pk≤0，則此問題是無界，停止計(jì)算。否則，轉(zhuǎn)入下一步。第五步：根據(jù)

，在單純形表中，

所在的列為主元列，主元列所對應(yīng)的變量xk為換入變量（入基變量），按θ規(guī)則計(jì)算

，確定

所在的行為主元行，主元行在單純形表中s對的基變量為換出變量（出基變量）。主元行與主元列相交的元素為主元素

，轉(zhuǎn)入下一步。第3章

線性規(guī)劃

第六步：以alk為主元素進(jìn)行迭代，即用高斯消去法或稱為旋轉(zhuǎn)運(yùn)算，將主元列中主元素變

為1，其他元素變?yōu)?，即把xk所對應(yīng)的列向量變換為

第

l行

將XB列中的xl轉(zhuǎn)換為xk，CB列中的cl換成ck，得到新的單純形表。重復(fù)第三步～第六步，直到算法終止。

【例3-10】用【例3-2】的標(biāo)準(zhǔn)型來說明上述計(jì)算步驟。第3章

線性規(guī)劃第一步：將模型標(biāo)準(zhǔn)化。取松弛變量x3，x4，x5為基變量，它對應(yīng)的單位矩陣為基。(3-39)模型中已存在一個初始可行基，對應(yīng)的基變量為x3，x4，x5，這就得到初始基可行解X(0)=(0，0，8，16，12)T將有關(guān)數(shù)字填入表中，得到初始單純形表，見表3-5。表(3-5)第3章

線性規(guī)劃

表(3-5)中左上角的cj是表示目標(biāo)函數(shù)中各變量的價(jià)值系數(shù)。在CB列填入初始基變量的價(jià)值系數(shù)，它們都為零，各非基變量的檢驗(yàn)數(shù)為σ1=c1-z1=2-(0×1+0×4+0×0)=2σ2=c2-z2=3-(0×2+0×0+0×4)=3第二步：因檢驗(yàn)數(shù)都大于零，且P1，P2有正分量存在，轉(zhuǎn)入下一步；第三步：max(σ1，σ2)=max(2，3)=3，對應(yīng)的變量x2為換入變量，計(jì)算θ(3-40)

它所在行對應(yīng)的x5為換出變量。x2所在列和x5所在行的交叉處[4]稱為主元素或樞元素(pivotelement)。第四步：以[4]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，即初等行變換，使P2變換為(0，0，1)T，在xB列中將x2替換x5，于是得到新表(3-6)。表(3-6)第3章

線性規(guī)劃b列的數(shù)字是x3=2，x4=16，x2=3于是得到新的基可行解X(1)=(0，3，2，16，0)T目標(biāo)函數(shù)的取值z=9第五步：檢查表(3-6)的所有cj-zj，這時(shí)有c1-z1=2；說明x1應(yīng)為換入變量。重復(fù)(2)～(4)的計(jì)算步驟，得表(3-7)。表(3-7)第3章

線性規(guī)劃

第六步：表(3-7)最后一行的所有檢驗(yàn)數(shù)都已為負(fù)或零。這表示目標(biāo)函數(shù)值已不可能在增大，于是得到最優(yōu)解目標(biāo)函數(shù)值

z*=143.4二階段法（人工變量法）

線性規(guī)劃問題的單純形法，若標(biāo)準(zhǔn)化后找不到m階單位陣，為了得到問題的一組初始基變量，通常采用人造基，即給方程加入一個非負(fù)的虛擬變量，稱這個虛擬變量為人工變量（剩余變量系數(shù)為-1，不能構(gòu)成初始基變量）。

人工變量是虛擬變量，存在于初始基本可行解中，需要將它們從基變量中替換出來。若人工變量可以從基變量中替換出來，即基變量中不含有非零的人工變量，表示原問題有解；若人工變量不可以從基變量中替換出來，則表示原問題無可行解。

對于一個標(biāo)準(zhǔn)化的線性規(guī)劃問題，其約束方程為(3-41)第3章

線性規(guī)劃給第i個約束方程中加入一個人工變量

，得到(3-42)如果以為基變量

，，非基變量，便可得到問題的一個初始基本可行解X0=(00......0b1b2......bm)T。因?yàn)槿斯ぷ兞渴羌尤氲皆s束方程組中的虛擬變量，為了不改變原來問題的性質(zhì)，就應(yīng)將它們從基變量中逐漸替換掉，即使人工變量為零。處理人工變量的方法有兩階段發(fā)和大M法，下面分別介紹。3.4.1二階段法

兩階段法是將加入人工變量后的線性規(guī)劃問題分兩階段來求解。第3章

線性規(guī)劃第一階段：在原線性規(guī)劃問題中加入人工變量，構(gòu)造模型。構(gòu)造模型的目標(biāo)函數(shù)為：

(3-43)(3-44)

用單純形法對(3-44)模型求解。若w=0，即所有的人工變量都為零，說明原問題存在一個基本可行解，可以進(jìn)行第二個階段；若w<0，即不是所有人工變量都為零，這說明原問題無可行解，停止運(yùn)算。

第二階段：從第一階段得到的基本可行解開始，繼續(xù)用單純形法進(jìn)行迭代，直到找出原問題的最優(yōu)解或判斷無最優(yōu)解。

說明：以上介紹的方法是對每個約束方程中都加入人工變量。如果原問題約束方程的系數(shù)矩陣中存在有一些單位向量，為減少計(jì)算工作量，可以只在部分約束方程中加入人工變量。

下面舉例說明。第3章

線性規(guī)劃【例3-11】用兩階段法求下列線性規(guī)劃問題(3-45)解

第一步：標(biāo)準(zhǔn)化

在第1個約束條件中引入松弛變量x4，第2個約束條件中引入剩余變量x5，得到原問題的標(biāo)準(zhǔn)形式為(3-46)第3章

線性規(guī)劃

第二步：確定初始變量，并將目標(biāo)函數(shù)中的基變量用非基變量代替。

上一步中，約束方程只有x4的系數(shù)為單位向量，為形成3階單位矩陣，在第2、第3個約束方程中分別引入人工變量x6和x7，得第一階段的規(guī)劃問題為(3-47)x4，x6，x7為基變量，將目標(biāo)函數(shù)w中的基變量用非基變量代替，有

注：如果原問題的目標(biāo)函數(shù)中也含有基變量時(shí)，也必須用非基變量代替。

第三步：作初始單純形表

作初始單純形表的基本要求與前面介紹的完全一樣，唯一的區(qū)別是增加了第1階段問題的目標(biāo)函數(shù)w行，見下面表(3-8)表格。第3章

線性規(guī)劃表(3-8)第3章

線性規(guī)劃

第四步：確定主元

第1階段問題以w為目標(biāo)函數(shù)，主元的確定方法與前面相同。

第五步：進(jìn)行第1階段迭代

與前述方法相同，即換出變量退出基底，換入變量進(jìn)入基底，化主元為1，主元列其它元素（包括f行元素）為零，完成一次迭代。若檢驗(yàn)數(shù)行的檢驗(yàn)數(shù)不全非正，則繼續(xù)迭代。

該問題經(jīng)過二次迭代后，w行的檢驗(yàn)數(shù)全部非正，且有maxw=0，故得到了原問題的一組基變量x4，x2，x3，至此第1階段迭代結(jié)束。

第六步：進(jìn)行第2階段迭代

從第1階段的最終單純形表中去掉人工變量x6，x7所對應(yīng)的列及w行，得到第2階段的單純形表，見表3-9。第3章

線性規(guī)劃經(jīng)過一次迭代后，檢驗(yàn)數(shù)全部非正，得到原問題的最優(yōu)解為X=（41900）T相應(yīng)的目標(biāo)函數(shù)值f=2。第3章

線性規(guī)劃3.4.2大M法

在一個線性規(guī)劃問題的約束條件中加入人工變量后，目標(biāo)函數(shù)應(yīng)如何處理?由于希望人工變量對目標(biāo)函數(shù)取值不受影響，因此，只有在迭代過程中把人工變量從基變量換出去，讓它成為非基變量。為此，這就必須假定人工變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為(-M)(M為很大的正數(shù))，這樣對于要求實(shí)現(xiàn)目標(biāo)函數(shù)最大化的問題來講，只要在基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)最大化(取正值)。若對目標(biāo)函數(shù)要求實(shí)現(xiàn)最小化時(shí)，在目標(biāo)函數(shù)中給人工變量規(guī)定一個很大的正系數(shù)(+M)，其理由與前述相同。這就是大M法。下面用例子來說明計(jì)算方法。

大M法的基本思路是對標(biāo)準(zhǔn)型線性規(guī)劃問題，引入人工變量后將其改造為：(3-48)s.t.(3-49)第3章

線性規(guī)劃其中，M為充分大的整數(shù)，記為M>>1，下面舉例說明大M法的具體迭代過程。【例3-12】試用大M法求解下面線性規(guī)劃問題解：在上述問題的約束條件中加入松弛變量、剩余變量和人工變量，得到第3章

線性規(guī)劃目標(biāo)函數(shù)中，M是一個很大的正數(shù)。下面用單純形法進(jìn)行計(jì)算，見表3.10。第3章

線性規(guī)劃由表(3-10)的最終計(jì)算表，得最優(yōu)解，

由此可見，凡約束條件為大于或等于型不等式時(shí)，均需引入人工變量，在目標(biāo)函數(shù)中，人工變量前面均應(yīng)乘上系數(shù)M，M>>1，而且，在極大值問題中，M前面為負(fù)號。這樣，可以保證在獲得最優(yōu)解時(shí)消去人工變量，如果人工變量不能通過迭代消去，則說明該問題無最優(yōu)解。到此為止，對于任何形式的線性規(guī)劃問題，總可以利用單純形法，兩階段單純形法或大M法對其求解。第3章

線性規(guī)劃3.5單純形法小結(jié)根據(jù)實(shí)際問題給出數(shù)學(xué)模型，列出初始單純形表。進(jìn)行標(biāo)準(zhǔn)化，見表(3-11)。分別以每個約束條件中的松弛變量或人工變量為基變量，列出初始單純形表。第3章

線性規(guī)劃(2)對目標(biāo)函數(shù)求max的線性規(guī)劃問題，用單純形法計(jì)算步驟的框圖見圖3-5。圖3-5單純形法計(jì)算步驟的框圖第3章

線性規(guī)劃3.6改進(jìn)單純形法

對于較簡單的線性規(guī)劃問題，可以用單純形表法求解，但當(dāng)線性規(guī)劃問題的規(guī)模較大時(shí)，用單純形表求解會非常困難，甚至變得不可能。為此就出現(xiàn)了一種新的算法----改進(jìn)的單純形法。其實(shí)是通過矩陣求逆來實(shí)現(xiàn)規(guī)劃問題解的方法。這種方法有助于計(jì)算機(jī)求解線性規(guī)劃問題。

對標(biāo)準(zhǔn)形式的線性規(guī)劃問題(3-50)第3章

線性規(guī)劃令：則上式可用矩陣型式表示若用列向量Pj，j=1，2，...，n代表矩陣A的第j列，則有第3章

線性規(guī)劃可設(shè)其前m個列向量是線性獨(dú)立的，則

為線性規(guī)劃問題的基矩陣。其余列向量構(gòu)成的矩陣稱為非基子矩陣。此時(shí)有A=(BN)。其中基矩陣B對應(yīng)的變量為基變量，用XB表示，，非基子矩陣N對應(yīng)的變量為非基變量，用XB表示，

，則有X=(XBXN)T。同樣地，C可以表示為C=(CBCN)T，于是式（3-15）可改寫為

(3-52)由上式得：(3-53)將其代入目標(biāo)函數(shù)整理得(3-54)其中，稱為單純形算子。第3章

線性規(guī)劃注意到，則表示了檢驗(yàn)數(shù)行的所有元素。而λ又可以表示為(3-55)此時(shí)，單純形表如下如果檢驗(yàn)數(shù)，則為問題的最優(yōu)基可行解，相應(yīng)的目標(biāo)函數(shù)值，否則，應(yīng)確定新的基矩陣B1繼續(xù)迭代。第3章

線性規(guī)劃實(shí)際上，單純形迭代過程是由一個基矩陣到另一個基矩陣轉(zhuǎn)移，而且每一次迭代只能是一個變量換入，一個變量換出，即基陣中只有一個列向量發(fā)生變化。設(shè)為初始基矩陣。若對應(yīng)的檢驗(yàn)數(shù)行向量不全非正。即基矩陣B0不是最優(yōu)基，根據(jù)前述的方法確定的換入變量為xk，則以列向量PK代換Pl得到新的基矩陣為由前面的推導(dǎo)可知，如果求得了，那么就可以求出一組新的基本可行解、相應(yīng)的目標(biāo)函數(shù)值和檢驗(yàn)數(shù)等。由此可見，在改進(jìn)單純形法計(jì)算中，關(guān)鍵是每次迭代時(shí)基矩陣的逆陣B-1。下面討論其求法。與單純形表解法類似，改進(jìn)單純形法通常也是用m個單位向量構(gòu)成的單位矩陣作為初始矩陣，即第3章

線性規(guī)劃以列向量Pk代換Pl后，得到的新基矩陣為因此，基矩陣求逆實(shí)際上就是計(jì)算機(jī)形如上式這種矩陣的逆，根據(jù)線性代數(shù)理論，不難求得B1的逆為改進(jìn)單純形法的計(jì)算步驟與單純形法類似，舉例說明如下。第3章

線性規(guī)劃【例3-13】用改進(jìn)單純形法求下列線性規(guī)劃問題解：第1步：標(biāo)準(zhǔn)化，引入松弛變量x3，x4，x5得第3章

線性規(guī)劃第2步：確定初始可行解，考慮矩陣表示，由上式得取x3，x4，x5為初始基變量，初始基變量為則有，可得非基變量的列向量為第3章

線性規(guī)劃初始基本可行解為相應(yīng)的目標(biāo)函數(shù)為非基變量檢驗(yàn)數(shù)為可將上述結(jié)果列表3-13，實(shí)際上是按3-10表列出。第3章

線性規(guī)劃因，故B0不是最優(yōu)基。第3章

線性規(guī)劃第3步：確定新基，進(jìn)行第一次迭代。由，x1為換入變量，P10為換入列向量。則由可知，6為主元，x5為換出變量，新的基變量為x3，x4，x1，故得新基B1為此時(shí)有由此得第3章

線性規(guī)劃上式中，，，故x2為換入變量，P21為換入列向量。第3章

線性規(guī)劃

同樣的，按照第2步的方法可知，x3為換出變量，P31為換出列向量，新的基變量為x2，x4，x1，故得新基B2為此時(shí)有由此可得第3章

線性規(guī)劃因檢驗(yàn)數(shù)，所以，迭代終止，得到問題的最優(yōu)解為相應(yīng)的目標(biāo)函數(shù)f2=31/4，上述結(jié)果可用如下表給出。第3章

線性規(guī)劃

小結(jié)：從以上運(yùn)算過程可以看出，對于手算來說，采用改進(jìn)單純形法并不方便，而且很容易出錯，但對于計(jì)算機(jī)而言，卻是得心應(yīng)手的事情。既節(jié)約了內(nèi)存，也減小了運(yùn)算量。

第3章

線性規(guī)劃3.7對偶線性規(guī)劃問題3.7.1對偶規(guī)劃先看看下面的例子在【例3-2】中，已建立的規(guī)劃問題模型LP1為進(jìn)行求解。第3章

線性規(guī)劃現(xiàn)從另一角度來討論這個問題。假設(shè)該廠的決策者決定不生產(chǎn)產(chǎn)品Ⅰ、Ⅱ，而將其所有資源出租或外售。這時(shí)工廠的決策者就要考慮給每種資源如何定價(jià)的問題。設(shè)用y1，y2，y3分別表示出租單位設(shè)備臺時(shí)的租金和出讓單位原材料A，B的附加額。他在做定價(jià)決策時(shí)，做如下比較：若用1個單位設(shè)備臺時(shí)和4個單位原材料A可以生產(chǎn)一件產(chǎn)品Ⅰ，可獲利2元，那么生產(chǎn)每件產(chǎn)品Ⅰ的設(shè)備臺時(shí)和原材料出租或出讓的所有收入應(yīng)不低于生產(chǎn)一件產(chǎn)品Ⅰ的利潤，這就有。同理將生產(chǎn)每件產(chǎn)品Ⅱ的設(shè)備臺時(shí)和原材料出租或出讓的所有收入應(yīng)不低于生產(chǎn)一件產(chǎn)品Ⅱ的利潤，這就有

。把工廠所有設(shè)備臺時(shí)和資源都出租或出讓，其收入為

從工廠的決策者來看當(dāng)然ω愈大愈好，但從接受者來看他的支付愈少愈好，所以工廠的決策者只能在滿足大于等于所有產(chǎn)品的利潤條件下，提出一個盡可能低的出租或出讓價(jià)格，才能實(shí)現(xiàn)其原意，為此需解如下的線性規(guī)劃問題LP2

(3-56)第3章

線性規(guī)劃顯然，當(dāng)

時(shí)，工廠決策者認(rèn)為這兩種考慮具有相同的結(jié)果，都是最優(yōu)方案。比較LP1和LP2，可知它們之間有著密切的聯(lián)系，兩者包含有相同的數(shù)據(jù)，只是位置不同而已。如果稱前者為原問題，則后者就叫前者的對偶問題，反過來也是如此，即兩者互為對偶問題。更一般地，若原問題為(3-57)則對偶問題為(3-58)第3章

線性規(guī)劃其中，yi叫做對偶變量。若表示成矩陣形式，則有(3-59)上式為對偶關(guān)系的非對稱形式。其中，A是矩陣；C是n維向量；b是m維列向量；X是n維列向量，為原問題的變量；Y是m為行向量，為對偶問題的變量。上式稱為對偶關(guān)系的對稱形式（或叫對偶標(biāo)準(zhǔn)形式），一般情況下，原問題與對偶問題的變換關(guān)系可歸納如下表3-16示。第3章

線性規(guī)劃若原規(guī)劃問題的約束條件中含有≧約束，可在其兩邊同乘以-1，統(tǒng)一為≦約束。這里，右邊項(xiàng)沒有符號限制。根據(jù)表3-16，可以寫出下列一對線性規(guī)劃問題：

(3-60)式(3-25)稱為對偶關(guān)系的非對稱形式。【例3-14】寫出下列線性規(guī)劃問題的對偶問題：第3章

線性規(guī)劃解：用-1乘第2個約束條件的兩端，把它變成≦約束，根據(jù)3-16表即可寫出其對偶問題為【例3-15】寫出下列線性規(guī)劃問題的對偶問題：解：設(shè)對應(yīng)于約束條件的對偶變量一次分別為y1，y2，y3，則由表3-15的對偶關(guān)系，可直接給出上述問題的對偶問題，即第3章

線性規(guī)劃3.7.2

對偶問題的基本性質(zhì)下面介紹對偶問題的幾條重要性質(zhì)，以揭示原問題的解與對偶問題的解之間的一些重要關(guān)系，并為后續(xù)討論對偶問題的單純形法奠定基礎(chǔ)。若X和Y分別是原問題和對偶問題的任一可行解，則必有CX≦Yb，即f≦g。若X*和Y*分別為原問題和對偶問題的可行解，且可行解對應(yīng)的原問題和對偶問題的目標(biāo)函數(shù)值相等，即CX*≦Y*b，X*和Y*分別為原問題和對偶問題的最優(yōu)解。若原問題和對偶問題之一的最優(yōu)解無界，則另一個無可行解；若之一無可行解，則另一個的最優(yōu)解無界或無可行解。也就是說，原問題和對偶問題之一無最優(yōu)解，則另一個也無最優(yōu)解。第3章

線性規(guī)劃4)若原問題和對偶問題之一有最優(yōu)解，則另一個也有最優(yōu)解，且兩者的最優(yōu)目標(biāo)函數(shù)值相等。5)原問題的最優(yōu)解為XB=B-1b，則對偶問題的最優(yōu)解為Y=CBB-1。6)根據(jù)原問題最優(yōu)單純形表中的檢驗(yàn)數(shù)可以讀出對偶問題的最優(yōu)解。對于第6個性質(zhì)下面作一說明。設(shè)原問題和對偶問題為式(3-60)，(3-61)

在原問題和對偶問題的約束條件中分別引入松弛變量Xs和剩余變量Ys，其中Xs為m維列向量，Ys為n維列向量，有設(shè)B為原問題的一個最優(yōu)基，則原問題可改寫為第3章

線性規(guī)劃相應(yīng)的對偶問題為這里，取是對應(yīng)于原問題中基變量XB的剩余變量，是對應(yīng)于原問題中非基變量XN的剩余變量。原問題的最優(yōu)解為XB=B-1b，相應(yīng)的基變量XB的檢驗(yàn)數(shù)為0，非基變量XN的檢驗(yàn)數(shù)為CN--CBB-1N，松弛變量XS的檢驗(yàn)數(shù)為-CBB-1，把對偶問題的最優(yōu)解Y=CBB-1代入上式得第3章

線性規(guī)劃由此可見，原問題的最優(yōu)單純形表中的檢驗(yàn)數(shù)對應(yīng)于對偶問題的最優(yōu)解的負(fù)值。它們的關(guān)系見表(3-17)。同樣地若原問題和對偶問題為式(3-25)所示的非對稱形式，則可得到表(3-18)所示的結(jié)果。第3章

線性規(guī)劃根據(jù)表(3-18)可知，原問題最優(yōu)表中的檢驗(yàn)數(shù)對應(yīng)于對偶問題最優(yōu)解中剩余變量的負(fù)值，而對偶決策變量的值Y=CBB-1看起來還不能直接從表(3-18)中讀出。當(dāng)然，如果知道了B-1和CB就可以直接計(jì)算出Y來，下面討論如何從表(3-18)中直接讀出對偶變量的值。假定在原間題的約束條件的系數(shù)矩陣中有一個m階單位陣，以此為初始可行基進(jìn)行迭代得到最優(yōu)基B，則在最優(yōu)表中，原來為單位陣的地方就變成了B-1，而在初始表中和B-1相對應(yīng)的基矩陣B正好位于和最優(yōu)表中的單位陣相對應(yīng)的位置，若用CI表示和初始表中單位陣相對應(yīng)變量的價(jià)值系數(shù)向量，則在最優(yōu)表中B-1下的檢驗(yàn)數(shù)將是CI-CBB-1。因而若由最優(yōu)表中B-1下的檢驗(yàn)數(shù)減去相應(yīng)的價(jià)值系數(shù)，則正好得到其對偶問題最優(yōu)解的負(fù)值，即-Y=-CBB-1，特別地，當(dāng)初始表中的單位陣是由引人松弛變量后而形成的，則有CI=0。在這種情況下，最優(yōu)表(3-17)中B-1下面的檢驗(yàn)數(shù)就正好等于其對偶問題的最優(yōu)解的負(fù)值。舉例說明。第3章

線性規(guī)劃【例3-16】對偶問題如下：(3-62)對偶問題為

(3-63)第3章

線性規(guī)劃

在原問題的約束條件中引入松弛變量x1，x2，x3，按單純形法得原問題的初始表和最優(yōu)表分別為表3-18和表3-19。第3章

線性規(guī)劃

由表3-19可知，原問題的最優(yōu)解為X=(35102500)T，最優(yōu)目標(biāo)函數(shù)值為maxf=215.

在表3-18申，松弛變量x1，x2，x3的系數(shù)矩陣構(gòu)成單位陣，故在最優(yōu)表3-19中對應(yīng)的系數(shù)矩陣為最優(yōu)基的逆陣

且對應(yīng)的檢驗(yàn)數(shù)等于它在對偶問題式（3-21）中的最優(yōu)解的負(fù)值。即Y=(y1，y2，y3)T=(013)，相應(yīng)的目標(biāo)函數(shù)值為ming=maxf=215。

另一方面，Y也可按式Y(jié)=CBB-1計(jì)算，由于最優(yōu)表中的單位陣對應(yīng)于基變量x3，x1，x2，所以它們在初始表3-18中的系數(shù)列向量構(gòu)成最優(yōu)基B，故，CB=(c3c1c2)T=(054)，則有：第3章

線性規(guī)劃相應(yīng)的目標(biāo)函數(shù)值為為了驗(yàn)證按上述方法確定的對偶問題的最優(yōu)解的正確性，按單純形法對對偶問題式(3-21)進(jìn)行迭代，得對偶問題的最優(yōu)表，見表(3-21)。表中y6，y7為人工變量，g’=-g。第3章

線性規(guī)劃

由表3-20可知，對偶問題式(3-21)的最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值與上述方法求得的完。由此可見從表3-20的檢驗(yàn)數(shù)中也可以直接讀出原問題的最優(yōu)解，這說明在求解線性規(guī)劃問題時(shí)，可在原問題和對偶間題中，選擇容易求解一方進(jìn)行。然后，應(yīng)用對偶問題性質(zhì)可求出對應(yīng)解。一般來說，線性規(guī)劃問題求解的工作量在很大程度上取決于約束條件數(shù)目的多少，約束越多，基矩陣階次就高，計(jì)算量自然就大。因此，對于約束條件多，變量少的規(guī)劃問題，其對偶規(guī)劃的約束條件少，變量多，若對對偶規(guī)劃求解，就可減少計(jì)算工作量。第3章

線性規(guī)劃3.7.3對偶單純形法

在用單純形進(jìn)行迭代時(shí)，在bi列申得到問題的基本可行解，而在檢驗(yàn)數(shù)行得到的是對偶問題的非可行解。這是因?yàn)樵谶_(dá)到最優(yōu)解之前，檢驗(yàn)數(shù)λ=C--CBB-1A=C-YA≧0，即YA≦C，顯然Y=CBB-1不滿足對偶問題的約束條件YA≧C。通過逐步迭代，當(dāng)檢驗(yàn)數(shù)行得到的對偶問題的解也是可行解時(shí)，即C-YA≦C或YA≧C時(shí)，CBXB=Yb，由對偶問題的性質(zhì)2知，此時(shí)原問題和對偶問題同時(shí)達(dá)到了最優(yōu)解。

根據(jù)對偶問題的對稱性也可以這樣來考慮：若保持對偶問題的解是可行解，即C-YA≦0，而原問題在非可行解的基礎(chǔ)上，即B-1b中至少有一個負(fù)分量，通過迭代逐步達(dá)到基本可行解，這樣也得到了原問題和對偶問題的最優(yōu)解。因?yàn)檫@種方法是從對偶問題的可行性出發(fā)來求解原問題的最優(yōu)解，故它稱做對偶單純形法。這種方法的優(yōu)點(diǎn)是原問題的初始解不一定是基本可行解，即可以從非可行解開始迭代。下面通過一個例題來介紹對偶單純形法的計(jì)算機(jī)步驟。第3章

線性規(guī)劃【例3-17】用對偶單純形法求解下列線性規(guī)劃問題：(3-64)解

第1步：標(biāo)準(zhǔn)化引入剩余變量x3，x4，x5，并令f’=-f，則有(3-65)第3章

線性規(guī)劃顯然，如果要用單純形法求解，則需引人3個人工變量，再用兩階段法或大M法進(jìn)行求解，若用下面介紹的對偶單純形法就簡單多了。第2步：找初始基變量，并將目標(biāo)函數(shù)中的基變量用非基變量代替。為了找出基變量，先在約束方程的系數(shù)矩陣中形成m階單位陣，為此用-1乘式(3-65)約束方程兩端，得(3-66)

顯然，x3，x4，x5為初始基變量，但對應(yīng)的初始解不是可行解。目標(biāo)函數(shù)中不含基變量。故不需代換。第3章

線性規(guī)劃第3步：作初始單純形表。由式(3-28)得初始單純形表。由表3-21可知，初始解是非可行的，但檢驗(yàn)數(shù)全部非正，在對偶單純形法中，把這種對應(yīng)檢驗(yàn)數(shù)全部非正的基本解稱為正則解。對偶單純形法是以正則解出發(fā)開始迭代，在迭代過程中最終保持bi列所有元素全部非負(fù)，即得到原問題的最優(yōu)解。第4步：確定主元對偶單純形算法是以原問題的右端列bi作為檢驗(yàn)數(shù)。若min{bi|bi<0}=bl則bl所在的行為主元行，bl所對應(yīng)的基變量為換出變量。此例中x4為換出變量。當(dāng)主元行確定后，就可按下