運(yùn)籌學(xué)單純形算法課件

。：解：對(duì)于上述具有兩個(gè)變量的線性規(guī)劃問題，圖1-2中的

OABCD部分描述了滿足約束條件的區(qū)域；虛線為目標(biāo)函數(shù)

Z=2x1+3x2的等值線。沿箭頭方向移動(dòng)目標(biāo)函數(shù)的等值線，平移等值線直至與可行域OABCD相切或融合為一條直線，此時(shí)就得到最優(yōu)解為B點(diǎn)，其坐標(biāo)可通過解方程組得到：2x1+2x2=143x2=15解得：x1=2x2=5這就是本線性規(guī)劃問題的最優(yōu)解此時(shí)相應(yīng)的目標(biāo)函數(shù)的最大值為Z=2×2+3×5=191例1－6

用圖解法求解線性規(guī)劃問題maxZ=40x1+80x2s.t.x1+2x2

303x1+2x2

602x2

24x1

,x2

0解：如圖1－3所示：求解最優(yōu)解：BC線段B點(diǎn)

X(1)=

(6,12)；C點(diǎn)

X(2)=

(15,7.5)X=α

X(1)+(1-α)

X(2) (0

α

1)maxZ=1200即

x1

=6α

+(1-

α

)·15x2=12α+(1-

α

)·7.5整理得：x1

=15-9αx2

=7.5+4.5α

(0≤

α

≤

1)2例1－7maxZ=2x1+4x2s.t. 2x1+x2

8-2x1+

x2

2x1，x2

0解：由于可行域無界，作目標(biāo)函數(shù)等值線，如圖1－4中虛線所示，并用箭頭標(biāo)出其函數(shù)值增加的方向，由此可以看出，該問題無有限最優(yōu)解。若目標(biāo)函數(shù)由max

Z=2x1

+4x2改為min

Z=2

x1

+4

x2

,則可行解所在的范圍雖然無界，但有最優(yōu)解x1

=4，x2

=0

，即(4,0)點(diǎn)。3通過以上各題圖解法所得結(jié)論可以看出：線性規(guī)劃的所有可行解構(gòu)成的可行域一般是凸多邊形，有些可行域可能是無界的；若存在最優(yōu)解，則一定在可行域的某頂點(diǎn)得到；若在兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，則在這兩點(diǎn)的連線上的任一點(diǎn)都是最優(yōu)解。若可行域無界，則可能發(fā)生最優(yōu)解無界的情況；若可行域是空集，此時(shí)無最優(yōu)解。上述理論具有普遍意義，對(duì)于兩個(gè)以上變量的線性規(guī)劃問題都是成立。圖解法雖然具有直觀、簡(jiǎn)便等優(yōu)點(diǎn)，但在變量多的情況下，即在多維的情況下，它就無能為力了。因此，需要介紹一種代數(shù)方法——單純型法，為了以后介紹方便，需要研究一下線性規(guī)劃問題解的概念。4三、基本定理凸集：假設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集，若對(duì)于K中的任意兩點(diǎn)X1、X2，其連線上的所有點(diǎn)αX1+(1-α)X2，(0≤α

≤1)都在集合K中，即：αX1+(1-α)X2

∈K

(0≤α

≤1)則稱K為凸集。從直觀上講，凸集無凹入部分，其內(nèi)部沒有洞。如實(shí)心圓、實(shí)心球、實(shí)心立方體等都是凸集。兩個(gè)凸集的交集仍是凸集。凸組合：設(shè)X1，X2，···，Xk是n維歐氏空間En中的k個(gè)點(diǎn)，若存在α1，α2，···，αk，且0

≤αi

≤1，i=1,2,

···,k，∑αi

=1，使X=α1X1

+α2X2

+···+αkXk，則稱X為由X1，X2，···，Xk所構(gòu)成的凸組合。按照定義，凡是由x，y的凸組合表示的點(diǎn)都在x，y的連線上，而且反之亦然。頂點(diǎn)：假設(shè)K是凸集，X

∈K；X若不能用不同的兩個(gè)點(diǎn)X1、X2∈K的線性組合表示為：X

=

αX1+(1-α)X2

，

(0<

α

<

1)則稱X為凸集K的一個(gè)頂點(diǎn)（或稱為極點(diǎn)）。頂點(diǎn)不位于凸集K中的任意不同兩點(diǎn)的連線內(nèi)。5定理1.1

若線性規(guī)劃問題存在可行域，則其可行域：D

={X|AX=b,X

0}，是凸集。引理1.1

線性規(guī)劃問題的可行解X為基本可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性無關(guān)的。定理1.2

線性規(guī)劃問題的基本可行解對(duì)應(yīng)于可行域的頂點(diǎn)。定理1.3

若可行域有界，則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)解。定理1.4

若線性規(guī)劃問題在k個(gè)頂點(diǎn)上達(dá)到最優(yōu)解（k

2），則在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu)解。6根據(jù)以上討論得到如下的結(jié)論：7線性規(guī)劃問題的所有可行解的集合一般是凸集，它可以是有界的，也可以是無界的區(qū)域；僅有有限個(gè)頂點(diǎn)。線性規(guī)劃問題的每一個(gè)基本可行解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)。若線性規(guī)劃問題有最優(yōu)解，必定可在某頂點(diǎn)處取到。如果一個(gè)線性規(guī)劃問題存在多個(gè)最優(yōu)解，那么至少有兩個(gè)相鄰的頂點(diǎn)處是線性規(guī)劃的最優(yōu)解。雖然可行域的頂點(diǎn)個(gè)數(shù)是有限的(它們不超過Cnm

個(gè))，采

用“枚舉法”可以找出所有基本可行解，然后一一比較它們的目標(biāo)函數(shù)值的大小，最終可以找到最優(yōu)解。但當(dāng)m、n的數(shù)目相當(dāng)大時(shí)，這種辦法實(shí)際上是行不通的。因此，我們還要繼續(xù)討論一種方法，通過逐步迭代保證能逐步改進(jìn)并最終求出最優(yōu)解。第

三

節(jié) 單純形算法8單純形算法的基本思路是：根據(jù)問題的標(biāo)準(zhǔn)型，從可行域中某個(gè)基本可行解(頂點(diǎn))開始，轉(zhuǎn)換到另一個(gè)基本可行解(頂點(diǎn))，并使得每次的轉(zhuǎn)換，目標(biāo)函數(shù)值均有所改善，最終達(dá)到最大值時(shí)就得到最優(yōu)解。從線性規(guī)劃解的性質(zhì)定理可知，線性規(guī)劃問題的可行域是凸多邊形或凸多面體，而且如果一個(gè)線性規(guī)劃問題有最優(yōu)解，就一定可以在可行域的頂點(diǎn)上找到。換言之，若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解，那么這個(gè)最優(yōu)解所對(duì)應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn)，若該線性規(guī)劃有多個(gè)最優(yōu)解，那么它一定可以在可行域的頂點(diǎn)中找到至少兩個(gè)最優(yōu)解?，F(xiàn)在需要解決的問題是：(1)為了使目標(biāo)函數(shù)逐步變優(yōu)，應(yīng)如何從可行域的一個(gè)頂點(diǎn)轉(zhuǎn)移到可行域的另一個(gè)頂點(diǎn)？（2）目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)值？判斷標(biāo)準(zhǔn)是什么？1．確定初始基可行解對(duì)于標(biāo)準(zhǔn)型的線性規(guī)劃問題(簡(jiǎn)寫為L(zhǎng)P)：或（1.9）這里A

=(aij)m

n

，秩A=m。9從中一般可以直接觀察到存在一個(gè)初始可行基B=

(P1,P2,···,Pm

)（1.10）當(dāng)線性規(guī)劃的約束條件均為“”形式的不等式時(shí)，可以利用標(biāo)準(zhǔn)型的方法，在每個(gè)約束條件的左端加上一個(gè)松弛變量，其松弛變量的系數(shù)矩陣即為單位矩陣；對(duì)于約束條件為“”形式的不等式或等式時(shí)，若不存在單位矩陣，就采用構(gòu)造人造基的辦法，即對(duì)不等式約束減去一個(gè)非負(fù)的剩余變量后，再加上一個(gè)非負(fù)的人工變量；對(duì)于等式約束，加上一個(gè)非負(fù)的人工變量。這樣總可以找到一個(gè)單位矩陣，關(guān)于這個(gè)方法將在本章第四節(jié)10討論。（1.10）式中的P1,P2,···,Pm稱為基向量，其對(duì)應(yīng)的變量稱為基變量，模型中其它變量稱為非基變量。在約束條件中把非基變量項(xiàng)移到等式的右邊得：（1.11）令所有非基變量 ，得X=

(b1,b2,···,bm,0,···,0)又由于，故X滿足約束條件，所以它是一個(gè)基可行解。式(1.11)就是基變量用非基變量表示的形式。T11令所有非基變量，得把式(1.12)代入目標(biāo)函數(shù)得：式（1.14）就是目標(biāo)函數(shù)用非基變量表示的形式。2．最優(yōu)性檢驗(yàn)假定已求得(LP)的一個(gè)基本可行解X(0)

，為敘述方便,不失一般性，假設(shè)：(1.12)（1.13）（1.14）12令，，于是再令，則得：（1.15），稱為各非基變量在式（1.15）中，非基變量的系數(shù)（ ）的檢驗(yàn)數(shù)。13定理1.5

最優(yōu)解判別定理:若，有σj定理1.6

無窮多最優(yōu)解判別定理:若為對(duì)應(yīng)于基B的基本可行解，且對(duì)于一切，有σj

0，，則線性規(guī)劃問題有無又存在某個(gè)非基變量的檢驗(yàn)數(shù)窮多最優(yōu)解。定理1.7

無有限最優(yōu)解判別定理：

若

為對(duì)應(yīng)于基

B的基本可行解，有一個(gè) ，而對(duì)于有 ，則線性規(guī)劃問題無有限最優(yōu)解(也稱為無最優(yōu)解)。以上討論的都是針對(duì)標(biāo)準(zhǔn)型的，即求目標(biāo)函數(shù)極大化問題。當(dāng)求目標(biāo)函數(shù)極小化時(shí)，一種情況如前所述，將其化為標(biāo)準(zhǔn)型；另一種情況是將判別定理中的檢驗(yàn)數(shù)σj

0改為即可。為對(duì)應(yīng)于基B的基本可行解，且對(duì)于一切

0，則X（0）為線性規(guī)劃問題的最優(yōu)解。143.基變換15若上面所求的基可行解還不是最優(yōu)解，下面我們將介紹，如何通過基(0)變換，求一個(gè)新的可行解？如何保證基變換后新的目標(biāo)函數(shù)更優(yōu)？若初始基可行解X

不是最優(yōu)解及不能判別無界時(shí)，需要找一個(gè)新的基可行解，即進(jìn)入迭代過程，具體做法是從原可行解基中用一個(gè)非基列向量換一個(gè)基列向量（換后當(dāng)然要保證這些向量線性無關(guān)），得到一個(gè)新的基可行解基，這稱為基變換。為了換基，先要確定換入變量，再確定換出變量，讓它們相應(yīng)的系數(shù)列向量進(jìn)行對(duì)換，就找到一個(gè)新的基可行解。3.基變換16（1）換入變量的確定由式(1.15)可知，當(dāng)某些非基變量的檢驗(yàn)數(shù)σj

>0時(shí)，如果xj增加，則目標(biāo)函數(shù)值還可以增加。當(dāng)有兩個(gè)或兩個(gè)以上σj

>0時(shí)，那么選哪個(gè)非基變量作為換入變量呢？為了使目標(biāo)函數(shù)值增加的最快，我們一般選擇σj

>0中的最大者，即：σj

=

max

{σl∣σl

>

0

}σj所對(duì)應(yīng)的變量xj為換入變量(就是下一個(gè)基的基變量)。（2）換出變量的確定因?yàn)榛兞總€(gè)數(shù)總是為m，所以換入一個(gè)變量之后還必須換出一個(gè)變量。下面我們來考慮如何選擇換出變量。確定換出變量的原則是保持解的可行性。這就是說，要使原基本可行解的某一個(gè)正分量xj變?yōu)?，同時(shí)保持其余分量均非負(fù)。具體實(shí)現(xiàn)是按“最小比例原則”進(jìn)行，也稱θ原則。若則選基變量xl為換出變量。17（3）旋轉(zhuǎn)運(yùn)算（迭代運(yùn)算）在確定了換入變量xj與換出變量xl之后，要把xj和xl的位置對(duì)換，就是說，要把xj所對(duì)應(yīng)的列向量pj變成單位向量。這時(shí)只需對(duì)系數(shù)矩陣的增廣矩陣進(jìn)行變換即可，稱alj為旋轉(zhuǎn)元。18單純形表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àn)數(shù)行，對(duì)應(yīng)各非基變量xj的檢驗(yàn)數(shù)是19cjc1…ck…cmcm+1…cj…cnθCBXBb*x1…xk…xmxm+1…xj…xnc1x1b1*1…0…0a1m+1…a1j…a1n………………………ClXlBl*0…1…0alm+1…alj…aln………………………cmxmbm*0…0…1amm+1…amj…amnC

-CB

B

AT

-10…0…0σm+1…σj…σn20表1—3初始單純形表以表1—3中的元素alj(稱為主元素或旋轉(zhuǎn)元素)進(jìn)行基變換：將第l行每個(gè)元素除以alj，再將第l行每個(gè)元素乘以–aij/alj

加到第i行(i=1,2,···,m,i≠l)，將第l行每個(gè)元素乘以–σj/alj

加到檢驗(yàn)數(shù)行，對(duì)應(yīng)的新的目標(biāo)函數(shù)值即為：經(jīng)過基變換之后，針對(duì)于新基B1的基本可行解為：21綜合以上的討論，單純形算法的計(jì)算步驟可歸結(jié)如下：22第一步：找出初始可行基，確定初始基本可行解，建立初始單純形表；第二步：檢查對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù)σk

，k∈IN，(IN為非基變量指標(biāo)集)，若所有σk≤0

，k∈IN

，則已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下一步；第三步：在所有σk>0，k∈IN

中，若有一個(gè)σj

對(duì)應(yīng)的系數(shù)列向量aij

≤0，則此問題沒有有限最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下一步；第四步：根據(jù)max{σk∣σk>0，k∈IN

}=σj，確定xj

為換入變量(即為新基的基變量)，再根據(jù)：確定xl

為換出變量(即為新基的非基變量)，轉(zhuǎn)下一步；第五步：以alj

為主元素進(jìn)行基變換，轉(zhuǎn)回第二步。23例1－8利用單純形算法求解例1－1的線性規(guī)劃問題。Max

Z=2x1+3x2+0·x3+0·x4+0·x53x2+x3=15244x1+x4=122x1+2x2＋x5=14x1，x2，x3，x4，x5≥0解：（1）由標(biāo)準(zhǔn)型得到初始單純形表：cj23000θiXBbx1x2x3x4x5x3150[3]1005x41240010x514220017-Z023000(2) max{

1,

2}=3=

2，所以x2為換入變量。(3)

因?yàn)?/p>

1=2，

2=3都大于0，且p1,p2的坐標(biāo)有正分量存在因?yàn)棣龋?與x3那一行相對(duì)應(yīng)，所以x3為換出變量；故x2對(duì)應(yīng)列與x3對(duì)應(yīng)行的相交處的3為主元素；(4)以“3”為主元素進(jìn)行旋轉(zhuǎn)計(jì)算，進(jìn)行行初等變換，得表1—5：表1—5cj23000θiXBbx1x2x3x4x5x25011/300x412400103x54[2]0-2/3012-Z-1520-10025重復(fù)以上步驟得表1—6。26表1—6目標(biāo)函數(shù)的最大值為：Z*=19cj23000θiXBBx1x2x3x4x5x25011/300x44004/31-2x1210-1/301/2-Z-1900-1/30-1這時(shí)，檢驗(yàn)數(shù)全部小于等于0，即目標(biāo)函數(shù)已不可能再增大，于是得到最優(yōu)解：X*=(2,5,0,4,0)T例1－9利用單純形算法求解線性規(guī)劃問題。Max

Z=4x1+3x2+0·x3+0

·

x4+0

·

x5272x1+2x2+

x3=16005x1+2.5x2+x4=2500x1+x5

=400x1,x2,x3,x4,x5≥0解：（1）由標(biāo)準(zhǔn)型得到初始單純形表1－7：表1—7cj43000θiXBbx1x2x3x4x5x3160022100800x4250052.5010500x5400[1]0001400-Z043000表1－828cj43000θiXBbx1x2x3x4x5x38000210-2400x45000[2.5]01-5200x140010001--Z-16000300-4表1－9cj43000θiXBbx1x2x3x4x5x3400001-0.8[2]200x22000100.4-2-x140010001400-Z-2200000-1.22表1－1029cj43000θiXBbx1x2x3x4x5x5200000.5-0.41x2600011-0.40-x120010-0.50.40-Z-260000-1-0.40這時(shí)，檢驗(yàn)數(shù)全部小于等于0，即目標(biāo)函數(shù)已達(dá)到最大，因此得到最優(yōu)解：X=(200,600,0,0,200)T目標(biāo)函數(shù)的最大值為：Z=2600例1－10利用單純形算法求解線性規(guī)劃問題。Max

Z=2x1+3x2+0·x3+0·x4+0·x5+0·x62x1+2x2+x3=1230x1+2x2+x4=84x1+x5=164x2+x6=12x1，x2，x3，x4，x5,x6≥0解：（1）由標(biāo)準(zhǔn)型得到初始單純形表：表1—11cj230000θiXBbx1x2x3x4x5x6x3122210006x481201004x516400010x6120[4]00013-Z0230000表1—1231cj230000θiXBbx1x2x3x4x5x6x3620100-1/23x42[1]0010-1/22x5164000104x23010001/4-Z-920000-3/4表1—13cj230000θiXBbx1x2x3x4x5x6x32001-201/24x1210010-1/2x58000-41[2]4x23010001/412-Z-13000-201/4在求解過程中，有時(shí)會(huì)出現(xiàn)兩個(gè)或更多的

相同的問題，這種情況出現(xiàn)時(shí)，我們稱之為出現(xiàn)了退化問題。表1—13就出現(xiàn)了退化問題，在出現(xiàn)退化問題時(shí)，即有兩個(gè)或更多的

相同時(shí)，在相同

對(duì)應(yīng)的變量中選擇下標(biāo)最大的那個(gè)基變量為換出變量；同時(shí)如果出現(xiàn)有兩個(gè)或更多的檢驗(yàn)數(shù)σ大于零且相同時(shí)，在相同σ對(duì)應(yīng)的變量中選擇下標(biāo)最小的那個(gè)基變量為進(jìn)入變量，這樣會(huì)避免出現(xiàn)“死循

環(huán)”的現(xiàn)象。表1—14cj230000θiXBbx1x2x3x4x5x6x30001-1-1/40x1410011/40x64000-21/21x220101/2-1/80-Z-14000-3/2-1/80這時(shí)，檢驗(yàn)數(shù)全部小于等于0，即目標(biāo)函數(shù)已不可能再增大，于是得到最優(yōu)解：X*=(4,2,0,0,0,4)目標(biāo)函數(shù)的最大值為：

Z*=14T32第四節(jié) 單純形算法的進(jìn)一步討論一、初始基本可行解的確定利用單純形算法的一個(gè)根本前提是要有一個(gè)初始的基本可行解。這對(duì)于一些簡(jiǎn)單問題，利用觀察或其它手段是容易得到的；但對(duì)于較復(fù)雜的問題，利用這種方法幾乎是不可行的。這就引起了人們對(duì)求初始基本可行解的思考。以下我們分幾種情形加以討論。1．對(duì)于AX=b，若人們一下就可以從其中求得一個(gè)單位矩陣。這時(shí)取初始基B就是單位矩陣，對(duì)應(yīng)的基變量為XB，非基變量為XN

。這時(shí)然后按單純形算法計(jì)算步驟便可得到。這種情況包含了AX≤b的情形。332.

對(duì)于AX=b，并且不能夠從中觀測(cè)到一個(gè)單位矩陣。這時(shí)分別給每一個(gè)約束條件加入一個(gè)人工變量xn+1,…,xn+m

,得:由此可以得到一個(gè)m階單位矩陣。以xn+1，…，xn+m為基變量，令非基變量x1，…，xn

為0，便可得到一個(gè)初始基本可行解X

(0)；X

(0)

=(0,

,0,b1

,

,bm

)T。因?yàn)槿斯ぷ兞渴呛蠹尤氲皆s束方程組中的虛擬變量，我們要求將它們從基變量中逐漸替換掉。若經(jīng)過基的變換，基變量中不再包含

有人工變量，這就表示原問題有解；若經(jīng)過基變換，當(dāng)所有的σj

0時(shí)，而在基中至少還有一個(gè)人工變量，這就意味著原問題無可行解。34二、人工變量法(大M法)35對(duì)于加入人工變量的線性規(guī)劃問題的目標(biāo)函數(shù)如

何處理？我們希望人工變量對(duì)目標(biāo)函數(shù)取值不受影響。因此只有在迭代過程中，把人工變量從基變量中換出，讓它成為非基變量。為此，就必須假定人工變量在目

標(biāo)函數(shù)中的價(jià)值系數(shù)為(-M)(對(duì)于極大化目標(biāo))，M為充分大的正數(shù)。這樣，對(duì)于要求實(shí)現(xiàn)目標(biāo)函數(shù)最大化的

問題來講，只要在基變量中還存在人工變量，目標(biāo)函

數(shù)就不可能實(shí)現(xiàn)最大化。這就是大M法。以下舉例加以說明。例1-11

試用大M法求解如下線性規(guī)劃問題的最優(yōu)解。解:在上述問題中加入松弛變量,剩余變量和人工變量得：這里M是一個(gè)充分大的正數(shù)，取基變量為x4,x6,x7,可得如下的表1—15。利用表1—15得初始單純形表，單純形算法得表1—16～表1—19。36表1—1537cj3-1-100-M-MXBbx1x2x3x4x5x6x7x4111-211000x63-4120-110x71-20[1]0001-Z03-1-100-M-M由于x4,x6,x7為基變量，因此它們對(duì)應(yīng)的檢驗(yàn)數(shù)行的檢驗(yàn)數(shù)應(yīng)為0，經(jīng)變換得初始單純形表1—16。初始單純形表1—16cj3-1-100-M-MθXBbx1x2x3x4x5x6x7x4111-21100011x63-4120-1101.5x71-20[1]00011-Z4M3-6MM-13M-10-M00表1—1738cj3-1-100-M-MθXBbx1x2x3x4x5x6x7x4103-20100-1—x610[1]00-11-21x31-2010001—-ZM+11M-100-M01-3M表1—18cj3-1-100-M-MθXBbx1x2x3x4x5x6x7x412[3]001-22-54x210100-11-2—x31-2010001—-Z21000-11-M-1-M表1—1939cj3-1-100-M-MθXBbx1x2x3x4x5x6x7x141001/3-2/32/3-5/3x210100-11-2x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-M在表1—19中，所有的σj

0，故得到最優(yōu)解：X*=

(4,1,9,0,0,0,0)T目標(biāo)函數(shù)值Z′=2,原問題的最優(yōu)目標(biāo)值為:Z*=-2。三、兩階段法:這種方法是在約束條件中加入人工變量，將線性規(guī)劃問題分為兩階段進(jìn)行求解。第一階段是先求出基本可行解(或判斷出原線性規(guī)劃問題無解)，第二階段利用已求出的初始基本可行解來求最優(yōu)解。具體由如下定理1.8給出。定理1.8

設(shè)原線性規(guī)劃問題記成(LP)，由它而引入的新的線性規(guī)劃問題記成(LP)*。分別表示如下：40則(LP)是可行1)

若(LP)*具有最優(yōu)基本可行解的，而 即為(LP)的一個(gè)基可行解。2)

若(LP)*的最優(yōu)基本可行解 則(LP)

必不可行。定理1.8的具體應(yīng)用過程是：由(LP)*判斷原線性規(guī)劃問題是否存在基本可行解，利用單純形算法，若得到W

=0，即所有人工變量為非基變量，這表示原問題已得到了一個(gè)基本可行解。于是只需要將第一階段最終計(jì)算表中的目標(biāo)函數(shù)行的數(shù)字換成原問題的目標(biāo)函數(shù)的數(shù)字，就得到了求解原問題的初始計(jì)算表，再進(jìn)行第二階段的求解。若第一階段的最終計(jì)算表出現(xiàn)

W>0，這就表明原問題無可行解，應(yīng)停止計(jì)算。各階段的計(jì)算方法及步驟與前述單純形法完全相同，下面用例子說明該方法的應(yīng)用。41例1－12

試用兩階段法求解如下線性規(guī)劃問題42解：先在以上問題的約束條件中加入松弛變量、剩余變量、人工變量，給出第一階段的線性規(guī)劃問題：以x4,x6,x7為基變量得如下初始表1—20。表1—20cj00000-1-1XBbx1x2x3x4x5x6x7x4111-211000x63-4120-110x71-2010001-W'000000-1-143初始單純形表1—2144cj00000-1-1θXBbx1x2x3x4x5x6x7x4111-21100011x63-4120-1101.5x71-20[1]00011-W'4-6130-100表1—22cj00000-1-1θXBbx1x2x3x4x5x6x7x4103-20100-1—x610[1]00-11-21x31-2010001—-W'10100-10-3表1—23cj00000-1-1θXBbx1x2x3x4x5x6x7x4123001-22-5x210100-11-2x31-2010001-W'000000-1-1這里x6、x7

是人工變量。第一階段我們已求得W

′=

0，最優(yōu)解x5=0，x6=0，x7=0。因人工變量x6=x7=0，所以(0,1,1,12,0)T是原問題的基本可行解。于是可以開始

第二階段的計(jì)算。將第一階段的最終計(jì)算表1—23中的人工變量列取消，并將目標(biāo)函數(shù)系數(shù)換成原問題的目標(biāo)函數(shù)系

數(shù)，重新計(jì)算檢驗(yàn)數(shù)行，可得如下第二階段的初始單純形表1—24；應(yīng)用單純形算法求解得最終表1—25。45表1—24cj3-1-100θXBbx1x2x3x4x5x412[3]001-24x210100-1—x31-20100—-Z'21000-1表1—25cj3-1-100θXBbx1x2x3x4x5x141001/3-2/3x210100-1x390012/3-4/3-Z'-2000-1/3-1/3表1—25中所有檢驗(yàn)數(shù)

σj

0，所以

x1

=

4，x2

=

1

,

x3

=

9

是原線性規(guī)劃問題的最優(yōu)解。目標(biāo)函數(shù)值：

Z*

=

246四、檢驗(yàn)數(shù)的幾種表示方法我們以

作

為標(biāo)準(zhǔn)型，以作為最優(yōu)解的判別準(zhǔn)則。還有其它形式，下面把幾種檢驗(yàn)數(shù)的表示方法及判別準(zhǔn)則匯總于表1－26。表1－26標(biāo)準(zhǔn)型檢驗(yàn)數(shù)σMax

Z=CTXAX=b,X≥0Min

Z=CTXAX=b,X≥0cj-zj≥0≤0zj-cj≤0≥0對(duì)于目標(biāo)函數(shù)求極小值的問題采用上述任何一種處理方法，其單純形法的步驟與求極大值的方法相同。這里提醒讀者注意，在閱讀其它有關(guān)線性規(guī)劃的教科書時(shí)，一定要注意該書規(guī)定的標(biāo)準(zhǔn)型是目標(biāo)函數(shù)求極大值還是求極小值，檢驗(yàn)數(shù)是cj-zj還是zj-cj，不同的組合會(huì)使判別準(zhǔn)則不同，但單純形的計(jì)算步驟是不變的。47第五節(jié) 應(yīng)用舉例48線性規(guī)劃的應(yīng)用非常廣泛，特別是在經(jīng)濟(jì)管理領(lǐng)域有大量的實(shí)際問題可以歸納為線性規(guī)劃問題來研究，有些問題，它的背景不同，表現(xiàn)各異，但它們的數(shù)學(xué)模型卻有著完全相同的形式。盡可能多地掌握一些典型模型不僅有助于深刻理解線性規(guī)劃本身的理論，而且有利于靈活地處理千差萬別的問題，提高解決實(shí)際問題的能力。下面舉例說明線性規(guī)劃在經(jīng)濟(jì)管理方面的應(yīng)用。例1－13（投資問題）已知某集團(tuán)有1,000,000元的資金可供投資，該集團(tuán)有五個(gè)可49供選擇的投資項(xiàng)目，其中各種資料如下：表1-27投資項(xiàng)目風(fēng)險(xiǎn)%紅利%增長(zhǎng)%信用度110510112681783187141041262245410710該集團(tuán)的目標(biāo)為：每年紅利至少是80,000元，最低平均增長(zhǎng)率14%，最低平均信用度為6，該集團(tuán)應(yīng)如何安排投資，使投資風(fēng)險(xiǎn)最??？解:設(shè)xi表示第i項(xiàng)目的投資額i=1,2,3,4,5，目標(biāo)是投資風(fēng)險(xiǎn)最小化，因此目標(biāo)函數(shù)為：min

z

=

(0.1x1

+

0.06x2

+0.18x3

+

0.12x4+

0.04x5

)數(shù)學(xué)模型為：min

z

= 0.1x1

+

0.06x2

+0.18x3+

0.12x4+

0.04x5x1

+

x2+

x3

+

x4+

x5

=

1,000,0000.05x1

+

0.08x2

+

0.07x3

+

0.06x4+

0.1x5≥

80,0000.1x1

+

0.17x2

+

0.14x3

+

0.22x4+0.07x5≥140,000(11

x1

+

8x2

+

10x3

+

4x4+10x5)/5≥6xi

≥

0(i

=1,2,3,4,5)用單純形法可計(jì)算出結(jié)果。50cj3-1-100-M-MθCBXBb*x1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-M表1—11在表1—11中，所有的σj

0，故得到最優(yōu)解：X*

=

(4,

1,9,0,

0,0,0

)T目標(biāo)函數(shù)值Z′=2,原問題的最優(yōu)目標(biāo)值為:Z*

=-2

。51例1－14（配料問題）某工廠要用三種原材料C、P、H

混合調(diào)出三種不同格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求、產(chǎn)品單價(jià)、每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)分別見表1-28、表1-29。問該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？表1-28產(chǎn)品名稱規(guī) 格

要

求單價(jià)(元/kg)A原材料C

不少于50%原材料P不超過25%50B原材料C

不少于25%原材料P不超過50%35D不

限25表1-29原材料名稱每天最多供應(yīng)量(kg)單價(jià)(元/kg)C10065P10025H6035521)

若(LP)*具有最優(yōu)基本可行解則(LP)是可行的,而2)

若(LP)*的最優(yōu)基本可行解則(LP)必不可行。定理5的具體應(yīng)用過程是:(LP)*判斷原線性規(guī)劃問題是否存在基本可行解,利用單純形算法,若得到W=0,即所有人工變量為非基變量,這表示原問題已得到了一個(gè)基本可行解.于是只需要將第一階段最終計(jì)算表中的目標(biāo)函數(shù)行的數(shù)字換成原問題的目標(biāo)函數(shù)的數(shù)字,就得到了求解原問題的初始計(jì)算表,再進(jìn)行第二階段的求解。若第一階段的最終計(jì)算表出現(xiàn)W>0,這就表明原問題無可行解，應(yīng)停止計(jì)算。53解：依條件有：又由于原料總限額已給定，加入到產(chǎn)品A、B、D的原材料C總量每天不超過100kg，P總量不超過100kg，H總量不超過60kg。由此有：AC

+

BC

+

DC

100AP

+

BP

+

DP

100AH

+

BH

+

DH

6054我們的目的是使利潤(rùn)最大，即產(chǎn)品價(jià)格減去原材料的價(jià)格為最大。目標(biāo)函數(shù)：MaxZ=50(x1

+x2+x3)+35(x4+x5+x6)+25(x7+x8+x9)-65(x1+x4+x7)

－25(x2+x5+x8)–35(x3+x6+x9)=

-15x1

+

25x2

+

15x3

–30x4

+

10x5

+

0x6

–40x7

+0x8

–10x9約束條件：-1/2

x1

+

1/2x2

+

1/2x3

≤

0-1/4x1

+

3/4x2

–1/4x3

≤

0-3/4x4

+

1/4x5

+

1/4x6

≤

0-1/2x4

+

1/2x5

–1/2x6

≤

0x1

+x4

+x7

≤

100x2

+x5

+x8

≤

100x3

+x6

+x9

≤

60x1，······

，x9

≥

0上述數(shù)學(xué)模型，可用單純形表計(jì)算，計(jì)算結(jié)果是：每天只生產(chǎn)產(chǎn)品A200kg

，分別需要用原料C

100

kg；P

50

kg

；H

50

kg

?？偫麧?rùn)收入是Z=500元/天。55例1－15（連續(xù)投資問題）某部門在今后5年內(nèi)考慮給下列項(xiàng)目投資，已知：

項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%；56項(xiàng)目B：第三年年初需要投資，到第五年年末能回收本利125%，但規(guī)定最大投資額不超過4萬元；項(xiàng)目C：第二年年初需要投資，到第五年年末能回收本利140%，但規(guī)定最大投資額不超過3萬元；項(xiàng)目D：五年內(nèi)每年年初可購買公債，于當(dāng)年年末歸還，并加利息6%。已知該部門現(xiàn)有資金10萬，問它應(yīng)如何確定給這些項(xiàng)目每年的投資額，使到第五年年末擁有資金的本利總額為最大？解：(1)

確定變量：這是一個(gè)連續(xù)投資問題，與時(shí)間有關(guān)。但這里設(shè)法用線性規(guī)劃方法靜態(tài)地處理。設(shè)：xiA

：表示第i年年初給項(xiàng)目A的投資額i=1,···,5；xiB

：表示第i年年初給項(xiàng)目B的投資額i=1,···,5；xiC

：表示第i年年初給項(xiàng)目C的投資額i=1,···,5；xiD