第1章-線性規(guī)劃及單純形法

「線性規(guī)劃」帶來巨額財富

與其他傳統(tǒng)數(shù)學(xué)學(xué)門相比較,線性規(guī)劃算是非?！改贻p」卻非常「實用」的一門應(yīng)用數(shù)學(xué)。根據(jù)對二十世紀(jì)八十年代的一項調(diào)查,在美國「財富」雜志(Fortune)名列前五百名的大公司中,百分八十五均曾應(yīng)用線性規(guī)劃的方法來協(xié)助公司的營運。由此可見線性規(guī)劃應(yīng)用面的寬廣與普及。第1章線性規(guī)劃及單純形法§1一般線性規(guī)劃問題的數(shù)學(xué)模型§2圖解法§3單純形法原理§4單純形法的計算步驟§5單純形法的進一步討論§6數(shù)據(jù)包絡(luò)分析主要內(nèi)容§1

一般線性規(guī)劃問題的數(shù)學(xué)模型問題的提出線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的解常山機器廠生產(chǎn)I、II兩種產(chǎn)品，這兩種產(chǎn)品都要分別在A、B、C三種不同設(shè)備上加工。生產(chǎn)三種產(chǎn)品，已知的條件如下表所示，問該企業(yè)應(yīng)安排生產(chǎn)兩種產(chǎn)品各多少件，使總的利潤收入為最大。生產(chǎn)每件產(chǎn)品占用設(shè)備時間(h)產(chǎn)品I產(chǎn)品II計劃期內(nèi)用于生產(chǎn)的能力設(shè)備A2212設(shè)備B4016設(shè)備C0515單位產(chǎn)品的利潤（元）23例1.1生產(chǎn)計劃問題1-1問題的提出問題分析占用設(shè)備時間(h)產(chǎn)品I產(chǎn)品II可用的能力設(shè)備A2212設(shè)備B4016設(shè)備C0515利潤（元）23可控因素(所求變量):設(shè)在計劃期內(nèi)生產(chǎn)I、II兩種產(chǎn)品的數(shù)量分別為目標(biāo)：達(dá)到最大.使得總利潤最大，即利潤函數(shù)：受制條件：計劃期內(nèi)設(shè)備的使用量不超過可用量：設(shè)備B：設(shè)備C：設(shè)備A：模型s.t.

1-2線性規(guī)劃問題的數(shù)學(xué)模型(1)規(guī)劃問題的數(shù)學(xué)模型的3個組成要素：決策變量、目標(biāo)函數(shù)、約束條件(2)線性規(guī)劃問題的數(shù)學(xué)模型：決策變量為可控的連續(xù)變量、目標(biāo)函數(shù)和約束條件都是線性目標(biāo)函數(shù)約束條件(3)一般線性規(guī)劃問題的數(shù)學(xué)模型的表示形式：以上模型的簡寫形式為待定的決策變量

價值系數(shù)矩陣

為系數(shù)矩陣(或約束矩陣)。向量表示形式其中矩陣表示形式價值向量右端向量(2)化為標(biāo)準(zhǔn)形式的方法1-3線性規(guī)劃問題的標(biāo)準(zhǔn)形式取極大bi≥0,等式約束非負(fù)約束(1)標(biāo)準(zhǔn)形式①②松弛變量③剩余變量說明：松弛變量和剩余變量在實際問題中分別表示未被利用的資源和超用的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引進模型后它們在目標(biāo)函數(shù)中的系數(shù)均為零。

例1.2把問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式1-4線性規(guī)劃問題的解線性規(guī)劃問題滿足約束條件(2)、(3)的解可行解(或可行點)可行域全部可行解的集合最優(yōu)解使目標(biāo)函數(shù)(1)達(dá)到最大值的可行解最優(yōu)解集合最優(yōu)值最優(yōu)解的全體最優(yōu)解的目標(biāo)函數(shù)值基設(shè)Am×n為約束方程組(2)的系數(shù)矩陣(設(shè)n＞m),R(A)=mB是矩陣A的m×m階的滿秩子矩陣，基向量基變量非基變量基解不失一般性，設(shè)基B的每一個列向量Pj

(j=1,…,m)與基向量Pj

對應(yīng)的變量xj

線性規(guī)劃中除基變量以外的其他變量

在約束方程組(2)中,令非基變量xm+1=…=xn=0,可解出m個基變量的惟一解XB=(x1,…,xm),X=(x1,…,xm,0,…0)T,基解總數(shù)基可行解滿足變量非負(fù)約束條件(3)的基解可行基對應(yīng)于基可行解的基

例1.3

列出下述線性規(guī)劃問題的全部基、基解、基可行解、最優(yōu)解解：系數(shù)矩陣R(A)=2基基解是基可行解？目標(biāo)函數(shù)值x1x2x3x4-45.500×√√√×√×√2/5011/50-1/30011/601/2200-1/2020011P1P2P1P3P1P4P2P3P2P4P3P443/555§2

圖解法優(yōu)點：直觀性強、計算方便缺點：只適用問題中有兩個變量的情況步驟：建立坐標(biāo)系，將約束條件在圖上表示；確立滿足約束條件的范圍；繪制出目標(biāo)函數(shù)的圖形；確定最優(yōu)解s.t.

例2.1

用圖解法解線性規(guī)劃x1x2oB(0,6)A(6,0)2x1+2x2=125x2=154x1=16z=9z

=15z

=12Q1Q2Q3Q4唯一最優(yōu)解線性規(guī)劃問題解的情況：無可行解(可行域是空集)無界解或無最優(yōu)解(可行域無界)最優(yōu)解存在且唯一，則一定在頂點上達(dá)到最優(yōu)解存在且不唯一(無窮多最優(yōu)解)，一定存在頂點是最優(yōu)解(1)無可行解s.t.

x1x2o2x1+2x2=12x1+2x2=14(2)無界解s.t.

(3)無窮多最優(yōu)解x1x2o4x1=16s.t.

x2oQ1Q2Q3Q4x1圖解法的啟示(1)求解線性規(guī)劃問題時，解的情況有：惟一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解；(2)若線性規(guī)劃問題的可行域存在，則可行域是一個凸集；(3)若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一(如果有無窮多的話)一定能夠在可行域的某個頂點找到；(4)解題思路：先找出凸集的任一頂點，計算在頂點處的目標(biāo)函數(shù)值，比較周圍相鄰頂點的目標(biāo)函數(shù)值是否比這個值更優(yōu)，若為否，則該頂點就是最優(yōu)解的點或最優(yōu)解的點之一，否則轉(zhuǎn)到比這個點的目標(biāo)函數(shù)值更優(yōu)的另一頂點重復(fù)上述過程，一直到找出使目標(biāo)函數(shù)值達(dá)到最優(yōu)的頂點為止。內(nèi)容小結(jié)基本概念線性規(guī)劃、可行解、可行域、最優(yōu)解、最優(yōu)值、基基向量、(非)基變量、基解、可行基基本計算把問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式用圖解法解線性規(guī)劃§3單純形法原理預(yù)備知識：凸集和頂點幾個基本定理的證明確定初始基可行解從初始基可行解轉(zhuǎn)化為另一基可行解最優(yōu)性檢驗和判別3-1預(yù)備知識：凸集和頂點凸集如果集合C中任意兩個點X1、X2，其連線上的所有點也都是集合C中的點，即對任何有頂點如果集合C中不存在任何兩個不同的點X1、X2，使X成為這兩個點連線上的一個點，或?qū)θ魏尾淮嬖?-2幾個基本定理的證明定理1

若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。證明：設(shè)C表示線性規(guī)劃問題的可行域則有令即則有顯然證畢引理

線性規(guī)劃問題的可行解X=(x1,…,xn)T為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。證明：必要性，由基可行解的定義顯然成立。充分性。不失一般性不妨,線性獨立的，若當(dāng)時，恰好構(gòu)成一個基，從而為相應(yīng)的基可行解。當(dāng)時,而R(A)=m,則必有則一定可以從其余列向量中找出m-k個與構(gòu)成一個基，其對應(yīng)的解恰好為X.若X為基解，如何判定是基可行解？若X為可行解，如何判定是基可行解？定理2線性規(guī)劃問題的基可行解對應(yīng)線性規(guī)劃問題可行域的頂點。分析：X是可行域的頂點X是基可行解X不是可行域的頂點X不是基可行解定理2線性規(guī)劃問題的基可行解對應(yīng)線性規(guī)劃問題可行域的頂點。X不是可行域的頂點(1)X不是基可行解證明：不失一般性,不妨設(shè)X的前m個分量為正，由X是可行解，得使得即存在一組不全為零的數(shù)線性相關(guān)，由引理知得得得令選取適當(dāng)?shù)闹担箘t又即X不是可行域的頂點。從而不是可行域的頂點有即因固有當(dāng)xi=0時，必有yi=zi=0得(2)X不是可行域的頂點X不是基可行解不失一般性,不妨設(shè)因有因線性相關(guān)故不全為零證畢若線性規(guī)劃問題有最優(yōu)解,一定存在一個基可行解是最優(yōu)解。定理3證明：設(shè)是最優(yōu)解是目標(biāo)函數(shù)的最大值。若X0不是基可行解，則X0不是可行域的頂點，一定能在可行域內(nèi)找到通過的X0的直線上的另外兩個點而有則由此從而若仍不是基可行解，按上面的方法繼續(xù)做下去,最后一定可以找到一個基可行解,其目標(biāo)函數(shù)值等于CX0.3-3確定初始基可行解由前面的定理可知：如果一個LP問題有最優(yōu)解，則一定在某個基可行解處達(dá)到。單純形法的基本思想就是先找到一個初始基可行解，判斷它是否最優(yōu)，如若不是，就找一個更好的基本可行解，再進行判斷。如此迭代下去，直至找到最優(yōu)基本可行解，或者判定該問題無界！??！一種易求初始基可行解的情形系數(shù)矩陣化為標(biāo)準(zhǔn)形式取單位矩陣作為基，則就是一個基可行解3-4從初始基可行解轉(zhuǎn)化為另一基可行解設(shè)初始基可行解為,其中非零坐標(biāo)有m個.不失一般性,假定前m個坐標(biāo)為非零，因固有方程組(*)的增廣矩陣可寫為得由上式知，因是一個基，則滿足或要使X1是一個基可行解，而θ>0,故應(yīng)對同時成立且至少有一個等號成立。當(dāng)aij≤0時，上式顯然成立。故可令則由上式，知則X1中的正分量個數(shù)最多有m個，易證，故只需按來確定的θ值，X1就是一個新的基可行解。線性無關(guān)，3-5最優(yōu)性檢驗和解的判別將基可行解X0和X1分別代入目標(biāo)函數(shù)得通常簡寫為

檢驗數(shù)說明：1)當(dāng)所有的

j≤0時,現(xiàn)有基可行解即為最優(yōu)解。

2)當(dāng)所有的

j≤0,又對某個非基變量xj有cj－zj=0，且按可以找到θ>0，這表明可以找到另一個基可行解使目標(biāo)函數(shù)也達(dá)到最大，此時該規(guī)劃有無窮多最優(yōu)解。3)如果某個

j>0,又Pj的所有分量aij≤0,則對任意θ>0,恒有而θ取值可無限大，故目標(biāo)函數(shù)也可無限增大,此時規(guī)劃問題有無界解。內(nèi)容小結(jié)基本概念凸集、頂點基本結(jié)論1)若線性規(guī)劃問題存在可行解，則可行域是凸集。2)

可行解X為基可行解X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。3)

基可行解對應(yīng)可行域的頂點。4)一定存在一個基可行解是最優(yōu)解?！?單純形法的計算步驟單純形法的計算步驟：step1、求出線性規(guī)劃的初始基可行解，列出初始單純形表。先化成標(biāo)準(zhǔn)形式,設(shè)法使系數(shù)矩陣中包含一個單位矩陣,不妨設(shè)此單位矩陣是(P1,P2,…,Pm),以此作為基可得一個初始基可行解X=(b1,b2,…,bm

).構(gòu)造初始單純形表cj

→c1…cm…cj

…cnx1…xm…xj…xnCB基bc1c2cmx1x2xmb1b2bmcj

-zj0…0……1…00…00…1…a1j…a1n…a2j…a2n…amj…amnStep2

進行最優(yōu)性檢驗

若表中所有的

j≤0,則表中的基可行解就是問題的最優(yōu)解，計算結(jié)束。否則轉(zhuǎn)下一步。

Step3

基可行解轉(zhuǎn)換，得到新單純形表。(1)確定入基變量.對應(yīng)的變量xk作為換入基的變量.(2)確定出基變量.xl作為換出基的變量.alk稱為主元素(3)生成新的單純形表Step4

重復(fù)第二、三步一直到計算終止。cj

→c1…cl…cm…cj

…ck…cnCB基bx1…xl…xm…xj…xk…xnc1x11……0……0…ckxk0……0……1…cmxm0……1……0…cj

-zj

0……0……0…s.t.

例1用單純形法求解線性規(guī)劃問題解：將上述問題化為標(biāo)準(zhǔn)形式組成初始基，得到初始基可行解初始單純形表cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000為入基變量為出基變量[]cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000[]cj

→23000CB基bx1x2x3x4x5cj

-zjx3x4x2003301001/5164001062010-2/52000-3/5為入基變量為出基變量[]cj

→23000CB基bx1x2x3x4x5cj

-zjx1x4x2203301001/5400-214/53101/20-1/500-10-1/5上表中所有的

j≤0,得到最優(yōu)解為

X=(3,3,0,4,0

).最優(yōu)值為

1、當(dāng)取法不唯一時，可任取一個對應(yīng)的xj為入基變量。2、相持，即取法不唯一時?？扇稳∫粋€基變量作為出基變量，則下表中其他基變量的值將等于0，這種現(xiàn)象稱為退化。退化的基可行解關(guān)于單純形方法的幾點說明(3)退化問題的處理攝動方法、字典序方法和Bland反循環(huán)方法問題由定理知，一個非退化的線性規(guī)劃問題一定可以在有限步內(nèi)得到最優(yōu)解或判定無最優(yōu)解。但是對于一個退化問題，情況又怎樣呢？例1可見，它是一個退化的可行基。列出它的單純形表，并進行迭代取作為初始可行基。cj

→3/4-1501/50-6000CB基bx1x2x3x4x5x6x70x501/4-60-1/2591000x601/2-90-1/5030100x710010001cj

-zj

3/4-1501/50-6000[]3/4x101-240-4/25364000x600303/50-15-2100x710010001cj

-zj

0307/50-33-3003/4x10108/25-84-1280-150x20011/500-1/2-1/151/3000x710010001cj

-zj

002/25-18-1-10[][]1/50x3025/801-525/2-75/2250-150x20-1/160101/401/120-1/6000x71-25/800525/275/2-251cj

-zj

-1/40032-30[]cj

→3/4-1501/50-6000CB基bx1x2x3x4x5x6x71/50x3025/801-525/2-75/2250-150x20-1/160101/401/120-1/6000x71-25/800525/275/2-251cj

-zj

-1/40032-30[]1/50x30-125/2105001050-1500-6x40-1/440011/3-2/300x71125/2-1050000-501501cj

-zj

1/2-120001-10上述迭代過程中，初始表與最后表完全相同，即迭代6次后，又回到初始基。出現(xiàn)了“死循環(huán)”，永遠(yuǎn)也得不到最優(yōu)解。[]0x50-5/42101/5001-30-6x401/6-30-1/150101/300x710010001cj

-zj

7/4-330-1/500020[]0x501/4-60-1/2591000x601/2-90-1/5030100x710010001cj

-zj

3/4-1501/50-600注:在實際計算中,單純形方法出現(xiàn)死循環(huán)的現(xiàn)象是極其少見的.為了解決這個問題,1952年,A.Charnes

提出攝動法;1954年,G.B.Dantzig

提出字典序法.本節(jié)例子是E.Beale于1955年提出的.

勃蘭特法則1974年,R.G.Bland利用組合方法成功地解決了退化的線性規(guī)劃問題,并提出了兩條簡便的規(guī)則,稱為勃蘭特法則：②選取最小比數(shù)中下標(biāo)最小的基變量為換出變量。①選取中下標(biāo)最小的非基變量為換入變量，其中§5單純形法的進一步討論人工變量法兩階段法關(guān)于解的判別單純形法計算的向量矩陣描述單純形法小結(jié)例:用單純形法求解線性規(guī)劃問題解：化為標(biāo)準(zhǔn)形式增加列向量,構(gòu)造出單位陣5-1人工變量法系數(shù)矩陣約束條件可相應(yīng)表位：人工變量約束條件中增加人工變量后,目標(biāo)函數(shù)如何處理?對任何可行解,原問題的等式約束必須滿足,故在最優(yōu)解中人工變量取值必須為零.為此,令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個負(fù)值,用-M表示,只要當(dāng)人工變量的取值不為0,目標(biāo)函數(shù)就不可能極大化.cj

→-30100-

M-M

CB基bx1x2x3x4x5x6x70x441111000-

Mx61-21-10-110-

Mx790310001cj

-zj

-4M-34M10-

M00[]0x4330211-100x21-21-10-110-

Mx7660403-31cj

-zj

6M-304M+103M-4M00x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj

-zj

00303/2-M-3/2-M+1/20x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj

-zj

-9/2000-3/4-M+3/4-M-1/4[][]5-2兩階段法基本思想

第一階段：通過求解輔助問題的最優(yōu)基可行解得到原問題的初始基可行解。

第二階段：求原問題的最優(yōu)解輔助問題設(shè)原問題為不妨假設(shè)如果某一個元素小于0,該方程兩邊乘于-1后則可以使右端數(shù)變成正數(shù)?？紤]如下輔助問題：其中首先用單純形法解輔助問題。原問題與輔助問題的關(guān)系1.若原問題有可行解,則輔助規(guī)劃的最優(yōu)值為0,反之亦然。就可以得到輔助規(guī)劃的初始基可行解3．輔助規(guī)劃有可行解同時,所以即輔助問題的目標(biāo)函數(shù)有下界,所以該問題一定有最優(yōu)解。4．先求輔助規(guī)劃的最優(yōu)基可行解,如果最優(yōu)值為0，則所以其非零分量對應(yīng)系數(shù)矩陣的列向量線性無關(guān)。是原問題的基可行解。的基可行解，2.由于,所以以為基變量，,所以是原問題的可行解。由于是輔助規(guī)劃的非零分量對應(yīng)的系數(shù)矩陣的列向量也線性無關(guān),所以所以求輔助問題的三種情況cj

→00000-1-1

CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj

-zj

-2400-100[]0x4330211-100x21-21-10-110-1x7660403-31cj

-zj

60403-400x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj

-zj

00000-1-1[][]0x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj

-zj

00000-1-1cj

→-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj

-zj

00303/20x400001-1/20x25/2-1/2100-1/41x33/23/20103/4cj

-zj

-9/2000-3/45-3關(guān)于解的判別例1用單純形法求解線性規(guī)劃問題將上述問題化為標(biāo)準(zhǔn)形式cj

→33000CB基bx1x2x3x4x53x13101/20-1/50x4400-214/53x2301001/5cj

-zj

00-3/200[]3x141001/400x5500-5/25/413x22011/2-1/40cj

-zj

00-3/200無窮多最優(yōu)解例2用單純形法求解線性規(guī)劃問題將上述問題化為標(biāo)準(zhǔn)形式cj

→230CB基bx1x2x30x116401cj

-zj230無界解例3用單純形法求解線性規(guī)劃問題將上述問題化為標(biāo)準(zhǔn)形式cj

→2300-MCB基bx1x2x3x4x50x31222100-Mx514120-11cj

-zj2+M3+2M0-M03x26111/200-Mx52-10-1-11cj

-zj-1-M0-3/2-M-M0無解5-4單純形法計算的向量矩陣描述線性規(guī)劃的標(biāo)準(zhǔn)形式初始單純形表為初始解非基變量基變量bBNIcj-zj

N0,…,0基可行解基變量非基變量B-1bIB-1NB-1cj-zj0,…,0-y1,…,-ym關(guān)系：或s.t.

例1用單純形法求解線性規(guī)劃問題(計算用向量矩陣描述)解：將上述問題化為標(biāo)準(zhǔn)形式組成初始基，初始單純形表cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000組成基若取0x40100cj

→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj

-zj00-10-1/50x40100cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj230000x40100cj

→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj

-zj00-10-1/50x401006數(shù)據(jù)包絡(luò)分析數(shù)據(jù)包絡(luò)分析(dataenvelopentanalysis,DEA)：一種對具有相同類型決策單元進行績效評價的方法.衡量單位績效的指標(biāo)：投入產(chǎn)出比(一個投入一個產(chǎn)出)6-1

基本概念例11

有4個銀行儲蓄所,每月均完成10000筆人民幣的存款、取款業(yè)務(wù),但投入情況不同,見下表,試分析這4個儲蓄所的績效儲蓄所B1B2B3B4職員數(shù)63107營業(yè)面積(m2)1001205070解：o6職員數(shù)營業(yè)面積1293120906030B1B2B4B3連接B2B4和B4B3組成一條凸的折線，通過B3作水平線,通過B2作一垂線。生產(chǎn)可行集：虛線和折線B2B4B3右上方所有點組成的集合生產(chǎn)前沿面：由虛線和折線B2B4B3形成的數(shù)據(jù)包絡(luò)線DEA有效：處于生產(chǎn)前沿面上的決策單元DD(5.6,93.3)6-2

評價決策單元DEA有效性的C2R模型DEA有效性的評價是對已有決策單元績效的比較評價，屬相對評價。設(shè)有n個決策單元(j=1,2,…,n),每個決策單元有相同的m項投入(i=1,2,…,m),和相同的s項產(chǎn)出(r=1,2,…,s)。xij:

第j單元的第i項投入量；yrj

:

第j單元的第r項產(chǎn)出量；vi：第i項投入的權(quán)值；ur：第r項產(chǎn)出的權(quán)值；決策單元投入產(chǎn)出hj：第j決策單元投入產(chǎn)出比通過適當(dāng)選取權(quán)值vi和ur，使對j=1,…,n有則對第j0個決策單元的績效評價可歸結(jié)為如下優(yōu)化模型：分式規(guī)劃模型對偶問題對偶問題的經(jīng)濟意義：為了評價j0決策單元的績效，可用一個假想的組合決策單元與其比較.決策單元的投入和產(chǎn)出.分別表示這個組合若非DEA有效若DEA有效課后習(xí)題1.8已知某線性規(guī)劃問題的和用單純形法得到的表如下,試求未知數(shù)a~l的值.x1x2x3x4x5x46bcd10x51-13e01cj

-zja-1200初始單純形表x1x2x3x4x5x1fg2-11/20x54hi11/21cj

-zj0-7jkl迭代后x1為入基變量g=1,h=0(1)(1’)(2)(2’)(1)×1/2=(1’)b=2,c=4,d=-2,f=3(1)×1/2+(2)=(2’)i=5(1)×(-3/2)+(3)=(3’)(3)(3’)j=5,k=-3/2,l=01.9試將下述問題改寫成線性規(guī)劃問題轉(zhuǎn)化

1.10判斷下列說法是否正確,并簡要說明理由.a)對取值無約束的變量xj

,通常令,其中,在用單純形法求得的最優(yōu)解中,有可能同時出現(xiàn).b)若X1,X2分別是某一線性規(guī)劃的最優(yōu)解,則X=λX1+(1-λ)X2也是該問題的最優(yōu)解,其中0≤λ

≤1。c)單純形法計算中選取最大正檢驗數(shù)對應(yīng)的變量作為換入基的變量，將使迭代后的目標(biāo)函數(shù)值得到最快增長.╳╳√

1.10判斷下列說法是否正確,并簡要說明理由.a)對取值無約束的變量xj

,通常令,其中,在用單純形法求得的最優(yōu)解中,有可能同時出現(xiàn).╳設(shè)xj

對應(yīng)的列為Pj

，則對應(yīng)的列為Pj

和-Pj分析：若在最優(yōu)解中,同時出現(xiàn)則一定為基變量，Pj

和–Pj一定同時為基向量，這樣與基的定義產(chǎn)生矛盾

1.10判斷下列說法是否正確,并簡要說明理由.c)單純形法計算中選取最大正檢驗數(shù)對應(yīng)的變量作為換入基的變量，將使迭代后的目標(biāo)函數(shù)值得到最快增長.分析：s.t.

cj

→22.1000CB基bx1x2x3x4x50x312221000x