第一章線性及單純形法

第1章

線性規(guī)劃與單純形法運(yùn)籌學(xué)的一個(gè)主要的分支是數(shù)學(xué)規(guī)劃。數(shù)學(xué)規(guī)劃研究：在一些給定的條件（約束條件）下，求所考察函數(shù)（目標(biāo)函數(shù)）在某種意義下的極值（極小或極大）問(wèn)題。例如：在經(jīng)濟(jì)決策中，經(jīng)常會(huì)遇到諸如在有限的資源（人、原材料、資金等）情況下，如何合理安排生產(chǎn)，使效益達(dá)到最大；或者給定具體的任務(wù)，如何統(tǒng)籌安

排現(xiàn)有資源，能夠完成給定的任務(wù)，使花費(fèi)最小這類(lèi)

問(wèn)題。在這章，我們重點(diǎn)介紹的是應(yīng)用最為廣泛的線性規(guī)劃問(wèn)題。第一章

線性規(guī)劃與單純形法一、線性規(guī)劃模型實(shí)例二、線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

三、求解線性規(guī)劃模型的圖解法四、單純形法五、單純形法的進(jìn)一步討論六、作業(yè)一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）例1-1（生產(chǎn)計(jì)劃問(wèn)題）某企業(yè)計(jì)劃生產(chǎn)I、II兩種產(chǎn)品。這兩種產(chǎn)品都要分別在

A、B、C、D四個(gè)不同設(shè)備上加工。按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品I需占用各設(shè)備分別為2、1、4、0

h，生產(chǎn)每件產(chǎn)品II需占用設(shè)備分別為2、2、0、4h。已知各設(shè)備計(jì)劃期內(nèi)用于生產(chǎn)兩種產(chǎn)品的能力分別為12、8、16、12h。又知每生產(chǎn)一件I企業(yè)能獲得2元利潤(rùn)，每生產(chǎn)一件產(chǎn)品

II企業(yè)能獲得3元利潤(rùn)。問(wèn)該企業(yè)應(yīng)如何安排生產(chǎn)，才能使總的利潤(rùn)最大。設(shè)備產(chǎn)品ABCD利潤(rùn)（元/件）I21402II22043生產(chǎn)能力（h）1281612一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）表1-1問(wèn)題分析：?jiǎn)栴}的目標(biāo)是什么？合理安排生產(chǎn)，實(shí)現(xiàn)利潤(rùn)最大化利潤(rùn)與哪些因素有關(guān)？

產(chǎn)量和單位產(chǎn)量的利潤(rùn)問(wèn)題分析：（1）問(wèn)題的目標(biāo)是什么？（2）利潤(rùn)與哪些因素有關(guān)？（3）單位利潤(rùn)最大的II產(chǎn)品，那么我們就僅生產(chǎn)II產(chǎn)品，是否可行？–不可行，原因是各設(shè)備生產(chǎn)II產(chǎn)品的能力是有限的，僅僅生產(chǎn)II產(chǎn)品，設(shè)備的生產(chǎn)能力還有剩余。結(jié)論是兩種產(chǎn)品都要進(jìn)行生產(chǎn)。（4）兩種產(chǎn)品的產(chǎn)量會(huì)受到什么限制條件呢？–各種設(shè)備的生產(chǎn)能力，即占用各種設(shè)備的工時(shí)。（5）要決策的問(wèn)題是：I產(chǎn)品生產(chǎn)多少？II產(chǎn)品生產(chǎn)多少？才能實(shí)現(xiàn)利潤(rùn)最大化呢？一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）。例1-1【解】：設(shè)x1和x2分別表示I、II兩種產(chǎn)品在計(jì)劃期內(nèi)的產(chǎn)量因設(shè)備A在計(jì)劃期內(nèi)的有效時(shí)間為12h，不允許超過(guò)，因此建立不等式方程：2x1+2x2≦12同理對(duì)設(shè)備B、C、D也可以列出類(lèi)似的不等式方程x1+2x2≦8

4x1≦16

4x2≦12建立各種設(shè)備允許的情況下，企業(yè)總的利潤(rùn)收入方程：z=

2x1+3x2按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品I需占用各設(shè)備分別為2、1、4、0h；生產(chǎn)每件產(chǎn)品II需占用設(shè)備分別為2、2、0、4h；已知各設(shè)備計(jì)劃期內(nèi)用于生產(chǎn)兩種產(chǎn)品的能力分別為12、8、16、12h一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）因此，該實(shí)例的問(wèn)題可以歸結(jié)為如下的數(shù)學(xué)模型。1

22x1,

x2

?

04x

￡12x

+

2x

￡

8s.t.4x1

￡16maxz

=

2x1

+

3x22x1

+

2x2

￡12回憶：數(shù)學(xué)規(guī)劃研究：在一些給

定的條件（約束條件）下，求所考察函數(shù)（目標(biāo)函數(shù)）在某種意義下的極值（極小或極大）問(wèn)題。如何理解“線性規(guī)劃”？一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）例1-2（能源利用問(wèn)題）假設(shè)某電廠以甲、乙、丙三種煤作為燃料煤，已知這三種煤的含硫量、發(fā)熱量及價(jià)格，見(jiàn)表1-2。現(xiàn)在要將上述三種煤混合燃燒，按鍋爐要求，發(fā)熱量不能低于17000kJ/t；按環(huán)保要求，含硫量不能超過(guò)0.025%。問(wèn)應(yīng)按什么比例將煤混合，才能使混合煤的價(jià)格最低？建立其數(shù)學(xué)模型。一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）電廠含硫量（%）發(fā)熱量（kJ/t）價(jià)格（元/t）甲0.011600080乙0.052000070丙0.031800076表1-2通過(guò)三種煤的組合實(shí)現(xiàn)混合煤的價(jià)格分析：?jiǎn)栴}的目標(biāo)是什么？最低問(wèn)題目標(biāo)實(shí)現(xiàn)的約束條件是什么？含硫量和發(fā)熱量一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）例1-2求解：設(shè)單位混合煤中甲、乙、丙三種煤的組合比例為x1：x2：x3因?yàn)槭墙M合比例，所以有x1+x2+x3=1，且為非負(fù)?？紤]約束條件：含硫量和發(fā)熱量

有16000x1

x2

x3≧170000.01x1+0.05x2+0.03x3≦0.025該問(wèn)題的目標(biāo)是在滿足上述約束條件下使每噸混合煤的價(jià)格最低，用z來(lái)表示價(jià)格，則：z=80x1+70x2+76x3一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）例1-2求解：因此，該問(wèn)題的數(shù)學(xué)模型為：1

2

31

2

3x1,

x2

,

x3

?

00.01x

+

0.05x

+

0.03x

￡

0.025s.t.x

+

x

+

x

=1minz

=

80x1

+

70x2

+

76x316000x1

+

20000x2

+18000x3

?17000目標(biāo)函數(shù)約束條件一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）例1-3

（運(yùn)輸問(wèn)題）假設(shè)某電力系統(tǒng)有三個(gè)火電廠B1、B2、B3，它們每月需燃料煤分別為10、20、25萬(wàn)t。供應(yīng)這三個(gè)電廠燃料煤的煤礦有三個(gè)，即A1、A2、A3，它們每月分別可供該電力系統(tǒng)燃料煤15、25、15萬(wàn)t。已知各煤礦到各電廠的運(yùn)輸距離（單位km），如表1-3所示。問(wèn)如何確定調(diào)運(yùn)方案，使總的運(yùn)輸量（總?cè)f噸公里數(shù)）最少？建立數(shù)學(xué)模型。一、線性規(guī)劃模型實(shí)例（問(wèn)題的提出）電廠運(yùn)距(km)煤礦B1B2B3A180100120A27012090A310080150表1-3分析：?jiǎn)栴}是什么？–如何確定調(diào)運(yùn)方案，使總的運(yùn)輸量（總?cè)f噸公里數(shù)）最少！調(diào)運(yùn)方案如何理解？–A1分別向B1、B2、B3三個(gè)電廠輸送多少萬(wàn)t煤炭？–A2分別向B1、B2、B3三個(gè)電廠輸送多少萬(wàn)t煤炭？–A3分別向B1、B2、B3三個(gè)電廠輸送多少萬(wàn)t煤炭？總的運(yùn)輸量（總?cè)f噸公里數(shù)）如何計(jì)算？–各個(gè)煤礦向各個(gè)電廠輸送的煤的噸數(shù)×輸送的距離之和。有哪些約束條件？–各火電廠的煤炭需要量和各煤礦的煤炭供給量例1-3【解】：設(shè)煤礦Ai（i=1，2，3）每月供給電廠Bj（j=1，2，3）燃料煤xij萬(wàn)t。ij1221x

?

（0 i

=1，2，3；j

=1，2，3）x13

+

x23

+

x33

=

25+

x22

+

x32

=

20xx31

+

x32

+

x33

=15+

x22

+

x23

=

25xs.t.x11

+

x21

+

x31

=10該問(wèn)題的目標(biāo)是在滿足供需平衡的條件下使總運(yùn)輸量最少。設(shè)z表示總運(yùn)輸量，則該運(yùn)輸問(wèn)題的數(shù)學(xué)模型為：min

z

=

80x11

+100x12

+120x13

+

70x21

+120x22

+

90x23

+100x31

+80x32

+150x33x11

+

x12

+

x13

=15自己動(dòng)手試一試：某工廠要生產(chǎn)兩種新產(chǎn)品：門(mén)和窗。經(jīng)測(cè)算，每生產(chǎn)一扇門(mén)需要在車(chē)間1加工1小時(shí)、在車(chē)間3加工3小時(shí)；每生產(chǎn)一扇窗需要在車(chē)間2和車(chē)間3各加工2小時(shí)。而車(chē)間1每周可用于生產(chǎn)這兩種新產(chǎn)品的時(shí)間為4小時(shí)、車(chē)間2為12小時(shí)，車(chē)間3為18小時(shí)。已知每扇門(mén)的利潤(rùn)為300元，每扇窗的利潤(rùn)為500元。而且根據(jù)經(jīng)市場(chǎng)調(diào)查得到的這兩種產(chǎn)品的市場(chǎng)需求狀況可以確定，按當(dāng)前的定價(jià)可確保所有新產(chǎn)品均能銷(xiāo)售出去。問(wèn)該工廠如何安排這兩種產(chǎn)品的生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？自己動(dòng)手試一試【解】?jī)煞N新產(chǎn)品的有關(guān)數(shù)據(jù)如表：車(chē)間單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）每周可獲得的生產(chǎn)時(shí)間（小時(shí)）門(mén)窗11042021233218單位利潤(rùn)（元）300500自己動(dòng)手試一試【解】23x1

+

2x2

￡18x1,

x2

?

02x

￡12s.t.設(shè)x1為每周門(mén)的產(chǎn)量（扇），x2為每周窗的產(chǎn)量（扇）。線性規(guī)劃模型如下：maxz

=

300x1

+

500x2x1

￡

4二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型規(guī)劃問(wèn)題的數(shù)學(xué)模型包含三個(gè)組成要素：決策變量，指問(wèn)題中要確定的未知量目標(biāo)函數(shù)，指問(wèn)題所要達(dá)到的目標(biāo)要求，表示為決策變量的函數(shù)約束條件，指決策變量取值時(shí)應(yīng)滿足的一些限制條件，表示為含決策變量的等式或不等式如果在規(guī)劃問(wèn)題的模型中，決策變量為可控變量，且取值是連續(xù)的，目標(biāo)函數(shù)及約束條件都是線性

的，這類(lèi)模型叫做線性規(guī)劃模型。二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型mmn

n21

1

22

2

2n

n

2x1

,

x2

,...xn

?

0x

￡

(=,

?)bm1

x1

+

am

2

x2

+...

+

aaa

x

+

a

x

+...

+

a

x

￡

(=,

?)bs.t.............1、線性規(guī)劃模型的一般表達(dá)形式（1）一般形式min或（max）z

=c1

x1

+c2

x2

+...+cn

xna11

x1

+

a12

x2

+...

+

a1n

xn

￡

(=,

?)b1x1

x2

xn1

a11

a12

a1n

b12

a21

a22

a2n

b2

m

am1

am

2

amn

bmc1

c2

cn價(jià)值系數(shù)動(dòng)活資源決策變量決策變量及各類(lèi)系數(shù)之間的對(duì)應(yīng)關(guān)系二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型1、線性規(guī)劃模型的一般表達(dá)形式（1）一般形式模型的簡(jiǎn)寫(xiě)形式為：jx

?

0(

j

=1,...,

n)s.t.

j

=1n

a

x

(

, )b

(i

1,2,......,

m)ij

j

￡

=

?

i

=nmin或（max）z

=cj

x

jj

=1二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型1、線性規(guī)劃模型的一般表達(dá)形式一般形式向量形式

j

xs

.t

.nj

=

1P

j

x

j

￡

(

=

,

?

)

b?

0

(

j

=

1,...,

n

)min

或（

max

）

z

=

CX

j

nb

amj

a

x

...

bm

...

;

P

=...

x

2

b1

2

j

,

(

j

=1,2,...,

n);b

=

a1

j

2x1

1

2

n式中：C

=（c

,

c

,...,

c

）;

X

=

二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型1、線性規(guī)劃模型的一般表達(dá)形式一般形式向量形式矩陣形式X

?

0s.t.AX

￡

(=,

?)bmin或（max）z

=CXa

mn

a...

...

m1

m

22n

2221...

a1n

a

...

a...

...a

...

a11

a12a式中：A

=A為約束方程組（約束條件）的系數(shù)矩陣。二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型2、線性規(guī)劃模型的標(biāo)準(zhǔn)形式為了研究問(wèn)題的方便，規(guī)定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式為：j

xs

.t

.nj

=1a

ij

x

j

=

bi

(

i

=

1,

2

,......,

m

)?

0

(

j

=

1,...,

n

)nmax

z

=

c

j

x

jj

=12、線性規(guī)劃模型的標(biāo)準(zhǔn)形式對(duì)標(biāo)準(zhǔn)形式的說(shuō)明：（1）標(biāo)準(zhǔn)形式的線性規(guī)劃模型中的要求①目標(biāo)函數(shù)為求最大值（有些文獻(xiàn)規(guī)定是求最小值）；②約束條件全為等式，約束條件右端常數(shù)項(xiàng)bi全為非負(fù)值；③變量xj的取值全為非負(fù)值。j

xs

.t

.nj

=1a

ij

x

j

=

bi

(

i

=

1,

2

,......,

m

)?

0

(

j

=

1,...,

n

)nmax

z

=

c

j

x

jj

=12、線性規(guī)劃模型的標(biāo)準(zhǔn)形式（2）非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法①目標(biāo)函數(shù)為求最小值只需令z’=-z，則目標(biāo)函數(shù)轉(zhuǎn)化為②約束條件為不等式當(dāng)約束條件為“≦”時(shí)，例如2x1+2x2≦12可令x3=12-2x1-2x2或者2x1+2x2+x3=12。顯然，x3≧0，稱x3為松弛變量。nmin

z

=

c

j

x

jj

=1n

j

jc

xj

=1'max

z

=

-2、線性規(guī)劃模型的標(biāo)準(zhǔn)形式（2）非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法②約束條件為不等式當(dāng)約束條件為“≧”時(shí)，例如10x1+12x2≧18可令x4=10x1+12x2-18或者10x1+12x2-x4=18。顯然，x4≧0，稱x4為剩余變量。松弛變量和剩余變量在實(shí)際問(wèn)題中分別表示未被利用的資源數(shù)和短缺的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤(rùn)。因此在目標(biāo)函數(shù)中，松弛變量和剩余變量的系數(shù)均為零。2、線性規(guī)劃模型的標(biāo)準(zhǔn)形式（2）非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法①目標(biāo)函數(shù)為求最小值②約束條件為不等式③無(wú)約束變量。設(shè)x為無(wú)約束變量，則令無(wú)約束變量的實(shí)際含義：若變量x代表某產(chǎn)品當(dāng)年

計(jì)劃數(shù)與上一年計(jì)劃數(shù)之差，則x的取值可正可負(fù)。x=x'

-x'，x'

?0,x'

?0二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型1

2

31

2

3

x1

,x

2

?0，x3

取值無(wú)約束3

x

-

2

x

-

3

x3

x

+

x

+

2

x

?

4=

-6s.t.例如1-4將下述線性規(guī)劃模型化為標(biāo)準(zhǔn)形式min

z

=

-

x1

+

2

x

2

+

3

x3

2

x1

+

x

2

+

x3

￡

9二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型'

''2

3

3

4

5

1'''1

2

3

31

2

3

3

53

3

42

3

4

5'1,

x

,

x

,

x

?

0x

,

x

,

x-

3x

=

6-

3x

+

2x

+

3x3x

+

x

+

2x'

-

2x''

-

x

=

4-

3x''

+

x

=

92x1

+

x2

+

xs.t.maxz'

=

x

-

2x

-

3x'3

+

3x''

+

0x

+

0x例如1-4【解】：令z'

=

-z,

x

=

x'

-x

''

(x'

?

0,x

''?

0),

x

=

9

-

2x

-

x

-x

'

+x

''3

3

3

3

3

4

1

2

3

3x

=

3x

+

x

+

2x

'

-2x

''

-4,-3x

+

2x

+

3x

'

-3x

''

=

65

1

2

3

3

1

2

3

3按規(guī)則將問(wèn)題轉(zhuǎn)化為：X4為松弛變量

X5為剩余變量二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型2、線性規(guī)劃模型的標(biāo)準(zhǔn)形式自己動(dòng)手試一試：將下列線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)型。1

2x

,

x

?

03x1

+

5x2

￡15s.t.

x

+

2x

￡

246

1

2maxz

=

2x1

+

x21

2

3

4x

,

x

,

x

,

x

?

03x1

+

5x2

+

x3

=15s.t.

x

+

2x

+

x

=

246

1

2

4maxz

=

2x1

+

x2

+

0x3

+

0x4二、線性規(guī)劃問(wèn)題的數(shù)據(jù)模型2、線性規(guī)劃模型的標(biāo)準(zhǔn)形式自己動(dòng)手試一試：將下列線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)型1

2

3

4-

2x1

+

3x2

-x3

+

2x4

?

2x1,x2

,x3

?0,x4無(wú)約束x

+

x

+

3x

-

x

￡14s.t.minz

=

-3x1

+

4x2

-

2x3

+

5x44x1

-

x2

+

2x3

-

x4

=

-2參考答案:-

2x

+

'

''

1

2

3

4

4'4

4

61

2

34

54'

''324'431

2x

,

x

,

x

,

x

,

x

?

0+

2(x

-

x''

)

-

x

=

23x

-x+

x

+

x

=14x1

+

x

+

3x

-

x-

x''

=

2x

-

2x

+

x-

4x

+s.t.-

x''

)

+

0x

+

0x4

5

6maxz'

=

3x

-

4x

+

2x

-

5(x'1

2

3

44?

0,x

''?

0)令z'

=

-z,

x

=

x'

-x

''

(x'4

4

4

4三、求解線性規(guī)劃模型的圖解法線性規(guī)劃模型的基本求解方法有：圖解法和單純形法。圖解法直觀明了，但是只適用于兩個(gè)變量的問(wèn)題，目

前常用的方法是單純形法。1、圖解法的步驟：第1步：建立坐標(biāo)系，畫(huà)出由約束條件所確定的區(qū)域第2步：對(duì)任意確定的z，畫(huà)出目標(biāo)函數(shù)所代表的直線第3步：平移目標(biāo)函數(shù)直線，確定最優(yōu)解。三、求解線性規(guī)劃模型的圖解法15x2

￡15x1,

x2

?

04x

￡16

（2）（3）（4）s.t.2、圖解法的實(shí)例例1-5用圖解法求最優(yōu)解maxz

=

2x1

+

3x22x1

+

2x2

￡12

（1）2、圖解法的實(shí)例。15x2

￡15x1

,

x2

?

04x

￡16

（2）（3）（4）s.t.maxz

=

2x1

+

3x22x1

+

2x2

￡12

（1）x1例1-5用圖解法求最優(yōu)解（1）先分析約束條件是如何圖示的x2Q4Q3Q2Q12、圖解法的實(shí)例例1-5用圖解法求最優(yōu)解（1）先分析約束條件是如何圖示的。15x2

￡15x1

,

x2

?

04x

￡16

（2）（3）（4）s.t.maxz

=

2x1

+

3x22x1

+

2x2

￡12

（1）x1x2Q4Q3(3,3)Q2(4,2)Q1從圖形中我們看到陰影部分的圖形是凸的，以后我們要證明，如果線性規(guī)劃問(wèn)題存在可行域，則可行域一定是一個(gè)凸集。2、圖解法的實(shí)例例1-5用圖解法求最優(yōu)解（2）目標(biāo)函數(shù)的幾何意義。目標(biāo)函數(shù)maxz=2x1+3x2，z是待定的值，將函數(shù)改寫(xiě)為x2=-2/3x1+z/3，由解析幾何知，這是變量為z、斜率為-2/3的一族平行的直線。如圖！這族平行線中，離原點(diǎn)越遠(yuǎn)的直線，z的直線越大。若對(duì)x1、x2的取值無(wú)限制，z的值可以無(wú)限增大。但在線性規(guī)劃問(wèn)題中，對(duì)x1、x2的取值范圍是有限制。15x2

￡15x1

,

x2

?

04x

￡16

（2）（3）（4）2x1

+

2x2

￡12

（1）s.t.maxz

=

2x1

+

3x215x2

￡15x1

,

x2

?

04x

￡16

（2）（3）（4）s.t.maxz

=

2x1

+

3x22x1

+

2x2

￡12

（1）x12、圖解法的實(shí)例例1-5用圖解法求最優(yōu)解（2）目標(biāo)函數(shù)的幾何意義。x23

32

1x

=

-

2

x

+

zZ=62、圖解法的實(shí)例例1-5用圖解法求最優(yōu)解（3）最優(yōu)解的確定。最優(yōu)解必須滿足約束條件的要求，并使目標(biāo)函數(shù)達(dá)到最優(yōu)值。因此x1、x2的取值范圍只能從凸多邊形OQ1Q2Q3Q4中去尋找。從圖中看到，當(dāng)代表目標(biāo)函數(shù)的直線和約束條件包圍成的凸多邊形相切時(shí)為止，切點(diǎn)就代表最優(yōu)解的點(diǎn)。思考：為什么z直線不能繼續(xù)向右上方移動(dòng)？15x2

￡15x1

,

x2

?

04x

￡16

（2）（3）（4）2x1

+

2x2

￡12

（1）s.t.maxz

=

2x1

+

3x2x1x2Q4Q3(3,3)Q2(4,2)Q12、圖解法的實(shí)例例1-5用圖解法求最優(yōu)解（3）最優(yōu)解的確定。例1-5中目標(biāo)函數(shù)直線與凸多邊形的切點(diǎn)是Q3，該點(diǎn)的坐標(biāo)（3，3），將其代入到目標(biāo)函數(shù)得z=15。2、圖解法的實(shí)例

1

21x

,

x

?

05x2

￡154x

￡16

（2）（3）（4）s.t.maxz

=

3x1

+

3x22x1

+

2x2

￡12

（1）x1例1-6將例1-5中的目標(biāo)函數(shù)max

z=2x1+3x2改為

maxz=3x1+3x2，則線性規(guī)劃問(wèn)題的最優(yōu)解為？最優(yōu)解為Q3Q2上的所有點(diǎn)，因此此問(wèn)題有無(wú)窮多個(gè)最優(yōu)解。x2Q4Q3(3,3)Q2(4,2)Q12、圖解法的實(shí)例例1-6我們看到目標(biāo)函數(shù)的圖形恰好與約束條件（1）平行。當(dāng)目標(biāo)函數(shù)直線向右上方移動(dòng)時(shí)，他與凸多邊形相切時(shí)不是一個(gè)點(diǎn)，而是在整個(gè)線段Q2Q3上相切。這時(shí)在Q2點(diǎn)、Q3點(diǎn)及Q2Q3線段上的任意點(diǎn)都是目標(biāo)函數(shù)值z(mì)達(dá)到最大，即該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解，也稱具有多重最優(yōu)解。15x2

￡15x1

,

x2

?

04x

￡16

（2）（3）（4）2x1

+

2x2

￡12

（1）s.t.maxz

=

3x1

+

3x22、圖解法的實(shí)例例1-7用圖解法求下列線性規(guī)劃問(wèn)題的最優(yōu)解1

21x

,

x

?

02x1

-

x2

￡

4s.t.x

￡

2maxz

=

x1

+

2x2x1x2如圖：此問(wèn)題有可行域，但為無(wú)界解（無(wú)最優(yōu)解）其原因是由于在建立實(shí)際問(wèn)題的數(shù)學(xué)模型時(shí)遺漏了某些必要的資源約束。2、圖解法的實(shí)例例1-8用圖解法求下列線性規(guī)劃問(wèn)題的最優(yōu)解1

21

2x

,

x

?

0x1

+

x2

￡

6s.t.x

+

2x

?14maxz

=

2x1

+

3x2x1x2用圖解法求解時(shí)找不到滿足所有約束條件的公共范圍，這時(shí)此問(wèn)題無(wú)可行解。原因是模型本身有錯(cuò)誤，約束條件相互矛盾，應(yīng)檢查修正。圖解法的解題思路和幾何上直觀得到的一些概念判斷，對(duì)求解一般線性規(guī)劃問(wèn)題的單純形法有很大的啟示：求解線性規(guī)劃問(wèn)題時(shí)，解的情況有：惟一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解、無(wú)可行解；若線性規(guī)劃問(wèn)題的可行域存在，則可行域是一個(gè)凸集（凸多邊形，稍后介紹）；若線性規(guī)劃問(wèn)題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無(wú)窮多的話）一定能夠在可行域（凸集）的某個(gè)頂點(diǎn)找到；三、求解線性規(guī)劃模型的圖解法（4）解題思路是：先找出凸集的任一頂點(diǎn)，計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值。比較周?chē)噜忢旤c(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值更優(yōu)，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更優(yōu)的另一個(gè)頂點(diǎn)，重復(fù)上述過(guò)程，一直到找出使目標(biāo)函數(shù)值達(dá)到最優(yōu)的頂點(diǎn)為止。圖解法雖然直觀、簡(jiǎn)便，但是當(dāng)變量數(shù)大于兩個(gè)時(shí)，它就無(wú)能為力了。引入單純形法！四、單純形法1、預(yù)備知識(shí)：凸集和頂點(diǎn)2、線性規(guī)劃問(wèn)題的解3、幾個(gè)基本定理（不要求證明）4、單純形法求解線性規(guī)劃5、單純形法的計(jì)算步驟四、單純形法單純形法是求解一般線性規(guī)劃問(wèn)題的基本方法，是

1947年由丹齊格（G.B.Dantzig）提出。1、預(yù)備知識(shí)：凸集和頂點(diǎn)①凸集：對(duì)一個(gè)給定的幾何圖形，通?？蓮闹庇^上判斷其凹凸性。但容易產(chǎn)生錯(cuò)誤。凸集的嚴(yán)格定義：如果集合C中任意兩個(gè)點(diǎn)X1、X2，其連線上的所有的點(diǎn)也都是集合C中的點(diǎn)，稱C為凸集。四、單純形法1、預(yù)備知識(shí)：凸集和頂點(diǎn)①凸集：因?yàn)閄1、X2的連線可表示為：aX1+（1-a）X2（0<a<1）所以凸集定義用數(shù)學(xué)語(yǔ)言表示為：對(duì)任何X1∈C，X2

∈C，有aX1+（1-a）X2

∈C（0<a<1），則稱C為凸集。1、預(yù)備知識(shí)：凸集和頂點(diǎn)①凸集判斷下列幾何圖形是否是凸集？（a）（b）（c）（d）四、單純形法1、預(yù)備知識(shí)：凸集和頂點(diǎn)①凸集：②頂點(diǎn)凸集C中滿足下述條件的點(diǎn)X稱為頂點(diǎn)：如果C中不存在任何兩個(gè)不同的點(diǎn)X1、X2，使X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn)。對(duì)任何X1∈C，X2

∈C，不存在X=aX1+（1-a）X2（0<a<1），則稱X是凸集C的頂點(diǎn)。解釋：頂點(diǎn)是不會(huì)出現(xiàn)在集合C中任意兩點(diǎn)之間的連線上。四、單純形法2、線性規(guī)劃問(wèn)題的解假設(shè)所要研究的線性規(guī)劃模型的形式為：求解線性規(guī)劃問(wèn)題，就是滿足約束條件（b）、（c）的方程組中找出一個(gè)解，使目標(biāo)函數(shù)（a）達(dá)到最大值。jx

?

0(

j

=1,...,

n)s.t

n.

j

=1aij

x

j

=

bi

(i

=1,2,......,

m)nmaxz

=

cj

x

jj

=1（a）（b）（c）jx

?

0(

j

=1,...,

n)ns.t.

j

=1aij

x

j

=

bi

(i

=1,2,......,

m)nmaxz

=

cj

x

jj

=1（a）（b）（c）四、單純形法可行解

滿足上述約束條件（b）、（c）的解X=（x1，…，xn）T

稱為線性規(guī)劃問(wèn)題的可行解，全部可行解的集合稱為可行域。最優(yōu)解

使目標(biāo)函數(shù)（a）達(dá)到最大值的可行解稱為最優(yōu)解。2、線性規(guī)劃問(wèn)題的解（3）基

設(shè)A為約束方程組（b）的m×n階系數(shù)矩陣（設(shè)n>m），其秩為m。B是矩陣A中的一個(gè)m×m階的滿秩子矩陣，稱B是線性規(guī)劃問(wèn)題的一個(gè)基。不失一般性，設(shè)

a...

amn

...a

...

a...

...am

2

...

...am12

n

2221a1n

a11

a12......1

mamm

am1

a11

a1m

B

=

...

...

...

=（P

,...,

P

）B中的每一個(gè)列向量Pj（j=1,…,m）稱為基向量，與基向量Pj對(duì)應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的其他變量稱為非基變量。n

j

=1s.t.

aij

x

j

=

bi

(i

=1,2,......,

m)基基向量回顧：矩陣的秩的定義定義:如果數(shù)域F

上的m

·

n

矩陣mn

a

a

a

m1

m1a2n

a1n

a11

a12A

=

a21

a22存在一個(gè)k

階子式不為零，并且所有的k

+1階子式全為零，則稱A

秩為k

，記作r

(A)=k

.顯然，r

(

A

)

￡

min

(

m

,

n

)

;

r

(

AT

)

=

r

(

A

)

.例求矩陣A的秩，其中1

4

1

2

3

A

=

2

3

-

5

.7解:在A

中，容易看出２階子式2312=

-

1

?

0

,而A

的三階子式只有一個(gè)｜Ａ｜|

A

|=

0,因此r(

A)

=

2.（3）基x

?

0(

j

=1,2,...,5)s.t.-10x1

+

6x2

+2x3

+

x5

=

2例1-9已知線性規(guī)劃maxz

=

4x1

-

2x2

-

x35x1

+

x2

-

x3

+

x4

=

3j求所有基矩陣?！窘狻浚杭s束方程的系數(shù)矩陣為2×5矩陣：

5

1A

=

-10

6容易看出r（A）=2，2階子矩陣有C25=10個(gè)，其中第

1列與第3列構(gòu)成的2階矩陣不是一個(gè)基，因此基矩陣只有9個(gè)，即：B

=1

5

1

5

1

B

=

-10

6

-10

02

5

0B

=36

2

1

-1

B

=-10

14

2

1-1

0B

=

8

2

0-1

1B7

=

6

1

1

06

B

=9

01

1B

=5

0

1

1

0B

=9-由1

線1性代0數(shù)知道，基矩陣B必為非2奇異0矩陣1，即|B|≠0。當(dāng)矩陣B的行列式等于零是就不是基。根據(jù)：B中的每一個(gè)列向量Pj（j=1,…,m）稱為基向量，與基向量Pj對(duì)應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的其他變量稱為非基變量。請(qǐng)指出例1-9中B2的基向量、基變量和非基變量。

-10

0

5

1B

=2-10

5

1

-1

1

06

2

0

1A

=

B2的基向量是A中的第一列和第四列

B2的基變量是x1和x4

B2的非基變量是x2、x3和x5?；兞亢头腔兞渴轻槍?duì)某一確定的基而言的，不同的基對(duì)應(yīng)的基變量和非基變量是不相同的。ns.t.

j

=1aij

x

j

=

bi

(i

=1,2,......,

m)nmaxz

=

cj

x

jj

=1（a）（b））四、單純形法量c變（4xm+1=xj

?

0(

j

=1,...,

n)

（）基本解在約束方程組（b）中，令所有非基

xm+2=…=xn=0,又因?yàn)橛衸B|≠0，根據(jù)克拉默規(guī)則，由m個(gè)約束方程可解出m個(gè)基變量的惟一解XB=（x1，…，xm）。這個(gè)解加上非基變量取0的值有X=（x1，x2，…，xm，0，…，0）T，稱為線性規(guī)劃問(wèn)題的基解。顯然在

基解中變量取非零值的個(gè)數(shù)不大于方程數(shù)m，又基解的總數(shù)不超過(guò)Cnm個(gè)。2、線性規(guī)劃問(wèn)題的解對(duì)某一特定的基B，令非基變量等于零，利用（b）求解出基變量，則這組解成為基B的基本解。(1)a

an1

x1

+

an

2

x2

++

ann

xn

=

bn21x1

+

a22

x2

++

a2n

xn

=

b2定理(克拉默法則)如果含有n

個(gè)方程的n

元線性方程組

a11x1

+

a12

x2

++

a1n

xn

=

b1的系數(shù)行列式?

0adet

A

=

21a1na2nanna11

a12a22

an1

an2則方程組(1)有唯一解，并且jjdet

Adet

B,

j

=1,

2,

,

nx

=其中

detBj

是將系數(shù)行列式

detA

的第

j

列元

a1j

,a2j,

…

,

anj

,

換成常數(shù)項(xiàng)

b1

,

b2

,

…

,

bn

后得到的行列式.jx

?

0(

j

=1,...,

n)ns.t.

j

=1aij

x

j

=

bi

(i

=1,2,......,

m)nmaxz

=

cj

x

jj

=1（a）（b）（c）四、單純形法（5）基本可行解滿足變量非負(fù)約束條件（c）的基解稱為基可行解。（6）可行基（7）最優(yōu)基對(duì)應(yīng)于基可行解的基稱為可行基基本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基2、線性規(guī)劃問(wèn)題的解例1-9中對(duì)于B1來(lái)說(shuō)，x1、x2是基變量，x3、x4、x5是非基變量，令x3=x4=x5=0，則因|B|≠0，由克萊姆法則知，

X1、x2有惟一解，解得x1=2/5，x2=1則基本解為X（1）=1

2

3

5x

?

0(

j

=1,2,...,5)5x1

+

x2

-

x3

+

x4

=

3s.t.-10x

+

6x

+2x

+

x

=

2maxz

=

4x1

-

2x2

-

x3j-10

6

5

1B

=1-10x1

+

6x2

=

25x1

+

x2

=

3T52（

，1，0，0，0）例1-9中對(duì)于B2來(lái)說(shuō)，x1、x4是基變量，x2、x3、x5是非基變量，令x2=x3=x5=0，則因|B|≠0，由克萊姆法則知，

X1、x4有惟一解，解得x1=-1/5，x4=4則基本解為X（2）=1

2

3

5x

?

0(

j

=1,2,...,5)5x1

+

x2

-

x3

+

x4

=

3s.t.-10x

+

6x

+2x

+

x

=

2maxz

=

4x1

-

2x2

-

x3j-10x1

=

25x1

+

x4

=

35（-

1

，0，0，4，0）T-10

0

5

1B

=2滿足非負(fù)約束條件，所以它是基本可行解；5X

(1)

=（

2

，1，0，0，0）T5X

(2)

=（-

1

，0，0，4，0）T不滿足非負(fù)約束條件，所以它不是可行解，也不是基本可行解；注意：可行解不一定是基本可行解。例滿足約束方程和非負(fù)約束，因此是可行解，但它不是任何基矩陣的基本解。T1

72

21）X

=（0，0，

，

，對(duì)應(yīng)的基B1稱為可行基基本最優(yōu)解、最優(yōu)解、基本可行解、基本解和可行解的關(guān)系如圖表示：基本最優(yōu)解基本可行解最優(yōu)解基本解可行解箭尾的解一定是箭頭的解，否則不一定成立四、單純形法1、預(yù)備知識(shí)：凸集和頂點(diǎn)2、線性規(guī)劃問(wèn)題的解3、幾個(gè)基本定理（不要求證明）定理1：若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行域是凸集。定理1描述了可行解集的特征。四、單純形法3、幾個(gè)基本定理定理2：線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域（凸集）的頂點(diǎn)。定理2描述了可行解集的頂點(diǎn)與基本可行解的對(duì)應(yīng)關(guān)系，頂點(diǎn)是基本可行解；反之，基本可行解在頂點(diǎn)上。但它們并非一一對(duì)應(yīng)，可能有兩個(gè)或幾個(gè)基本可行解對(duì)應(yīng)于同一個(gè)頂點(diǎn)。定理3：若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。四、單純形法2、線性規(guī)劃問(wèn)題的解例1-10 在下述線性規(guī)劃問(wèn)題中，列出全部基、基解、基可行解和指出最優(yōu)解。2

51

4.5x

+

x

=154x

+

x

=16s.t

max

z

=

2x1

+

3x2

+

0x3

+

0x4

+

0x52x1

+

2x2

+

x3

=12x

j

?

0(

j

=1,...,5)標(biāo)準(zhǔn)型1

45x2

+

x5

=152x1

+

2x2

+

x3

=124x

+

x

=16s.t

.max

z

=

2x1

+

3x2

+

0x3

+

0x4

+

0x5x

j

?

0(

j

=1,...,5)1

00

2

2

1

0 0

0

0

15

0

0A

=

4例1-10解P1

P2寫(xiě)出約束方程組的系數(shù)矩陣P3

P4

P5矩陣A的秩≦3。所以只要找出3個(gè)列向量組成的矩陣滿秩，這3個(gè)向量就是線性規(guī)劃問(wèn)題的一個(gè)基。例1-10解1

00

2

2

1

0 0

0

0

15

0

0A

=

4寫(xiě)出約束方程組的系數(shù)矩陣P1

P2

P3

P4

P5令與基對(duì)應(yīng)的變量為基變量，其余變量為非基變量，令非基變量等于零，求解方程組就可以找出基解。

下表中列出本線性規(guī)劃問(wèn)題的全部基、基解?；饣尚薪?？目標(biāo)函數(shù)值x1x2x3x4x5P1P2P343-200否17P1P2P433040是15P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0例1-10表基本結(jié)論：線性規(guī)劃問(wèn)題的所有可行解構(gòu)成的集合是凸集，也可能為無(wú)界域，它們有有限個(gè)頂點(diǎn)，線性規(guī)劃問(wèn)題的每個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)。若線性規(guī)劃問(wèn)題有最優(yōu)解，必在某頂點(diǎn)上得到。雖然頂點(diǎn)數(shù)目是有限的，若采用“枚舉法”找所有基可行解，然后一一比較，最終必然能找到最優(yōu)解。但當(dāng)

n,m較大時(shí)，這種辦法是行不通的，所以要繼續(xù)討論如何有效尋找最優(yōu)解的方法。我們將主要介紹單純形法。四、單純形法4、單純形法求解線性規(guī)劃通過(guò)示例來(lái)了解單純形法求解線性規(guī)劃。單純形法示例：例1-11某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如表所示。如何用單純形法求解下列標(biāo)準(zhǔn)線性規(guī)化數(shù)學(xué)模型。每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多?產(chǎn)品資源III擁有量設(shè)備128臺(tái)時(shí)原材料A4016kg原材料B0412kg例1-11【解】設(shè)x1和x2分別表示計(jì)劃生產(chǎn)產(chǎn)品I和產(chǎn)品II的數(shù)量。建立的線性規(guī)劃數(shù)學(xué)模型如下：12x1

,x2

?04x

￡

12

4x

￡

16x1

+

2x2

￡

8約束條件:目標(biāo)函數(shù)

max

z

=

2x1

+

3x2(1-1)max

z

=

2x1

+

3x2

+

0x3

+

0x4

+

0x5(1-

2)x

?

0

j

=1,2,,5=

8+

x4

=16+

x5

=124x1

+4x2x1

+

2x2

+

x3j約束條件例1-11【解】將上頁(yè)的線性規(guī)劃模型轉(zhuǎn)換成標(biāo)準(zhǔn)型如下：約束方程的系數(shù)矩陣從式中可以看到x3,x4,x5的系數(shù)列向量1001

2

1

0

0=

4

0

0

14

0

01

2

3

4

5A=(P,

P

,

P

,

P

,

P

)

1

0

0

0

1

0P3

=

0,

P4

=

1,

P5

=

0P3,P4,P5是線性獨(dú)立的，這些向量構(gòu)成一個(gè)基1

003

4

5

1

0

0B

=

(P

,

P

,

P

)=

0

10+

x5

=12=

8+

x4

=16

(1-

2)x1

+

2x2

+

x34x14x22514(1

-

3)=

12-

4

x

x=

16

-

4

x

x8

-

x1

-

2

x2

x3

=從(1-2)式中可以得到（1-3）對(duì)應(yīng)于B的變量x3,x4,x5為基變量，x1、x2為非基變量將(1-3)式代入目標(biāo)函數(shù)(1-1)得到令非基變量x1=x2=0，便得到z=0。這時(shí)得到一個(gè)基可行解X(0)=(0,0,8,16,12)T這個(gè)基可行解表示：工廠沒(méi)有安排生產(chǎn)產(chǎn)品Ⅰ、Ⅱ；資源都沒(méi)有被利用，所以工廠的利潤(rùn)指標(biāo)z=0。max

z

=

2x1

+

3x2

+

0x3

+

0x4

+

0x5

(1-1)z

=

0

+

2

x1

+

3x2

(1

-

4)到這里，完成了單純形法的第一個(gè)環(huán)節(jié)：確定初始基

本可行解；然后再確定這個(gè)基本可行解是否是最優(yōu)的，如果不是，則還要繼續(xù)去尋找最優(yōu)解！下面進(jìn)行最優(yōu)性的檢驗(yàn)！從分析目標(biāo)函數(shù)的表達(dá)式(1-4)可以看到：非基變量x1,x2(即沒(méi)有安排生產(chǎn)產(chǎn)品Ⅰ，Ⅱ)的系數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標(biāo)函數(shù)的值就可能增大。從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品Ⅰ或Ⅱ，就可以使工廠的利潤(rùn)指標(biāo)增加。所以只要在目標(biāo)函數(shù)(1-4)的表達(dá)式中還存在有正系數(shù)的非基變量，這表示目標(biāo)函數(shù)值還有增加的可能，當(dāng)前的基本可行解還不是最優(yōu)解。因此，最優(yōu)解否定后，又要去尋找新的基本可行解，這就需要將非基變量與基變量進(jìn)行對(duì)換。如何確定換入，換出變量？一般選擇正系數(shù)最大的那個(gè)非基變量x2為換入變量，將它換入到基變量中去，同時(shí)還要確定基變量中有一個(gè)要換出來(lái)成為非基變量，可按以下方法來(lái)確定換出變量?，F(xiàn)分析(1-3)式，當(dāng)將x2定為換入變量后，必須從

x3,x4,x5中確定一個(gè)換出變量，并保證其余的都是非負(fù)，即x3,x4,x5≥0。25(1-

3)x

=12

-

4xx4=16

-

4x1x3

=

8

-

x1

-

2x2z

=

0

+

2

x1

+

3x2

(1

-

4)當(dāng)x1=0,由(1-3)式得到4(1-

5)x5

=12

-

4x2

?

0xx3

=

8

-

2x2

?

0=16

?

0254

1(1

-

3)=

12

-

4

x

x=

16

-

4

x

x

x3

=

8

-

x1

-

2

x2x2取何值時(shí)，才能滿足非負(fù)要求？從(1-5)式中可以看出，只有選擇x2=min(8/2,12/4)=3時(shí)，才能使(1-5)式成立。因當(dāng)x2=3時(shí)，基變量x5=0，這就決定用x2去替換x5。以上數(shù)學(xué)描述說(shuō)明了每生產(chǎn)一件產(chǎn)品Ⅱ，需要用掉各種資源數(shù)為(2，0，4)。由這些資源中的薄弱環(huán)節(jié)，就確定了產(chǎn)品Ⅱ的產(chǎn)量。這里就是由原材料B的數(shù)量確定了產(chǎn)品Ⅱ的產(chǎn)量

x2=12/4=3件。為了求得以x3,x4,x2為基變量的一個(gè)基可行解和進(jìn)一步分析問(wèn)題，需將(1-3)中x2的位置與x5的位置對(duì)換。得到254

1(1

-

3)=

12

-

4

x

x=

16

-

4

x

x

x3

=

8

-

x1

-

2

x214(1)(2)

(1-

6)(3)=12-

x54x2x=

8

-

x1=16

-

4x+

2x2x3用高斯消去法將(1-6)式中x2的系數(shù)列向量變換為單位列向量。其運(yùn)算步驟是：③′=③/4；①′=①-2×③′;②′=②,并將結(jié)果仍按原順序排列有：412'14(1)'(2)'513(1

-

7)-

x5

(3)

x2

=

3x

=

16

-

4

x=

2

-

x

+

1

x

x再將(1-7)式代入目標(biāo)函數(shù)(1-1)式得到令非基變量x1=x5=0，得到z=9，并得到另一個(gè)基可行解X（1）X（1）=（0，3，2，16，0）T41

5z

=

9

+

2x

-

3

x（1-8）從目標(biāo)函數(shù)的表達(dá)式(1-8)中可以看到，非基變量x1的系數(shù)是正的，說(shuō)明目標(biāo)函數(shù)值還可以增大，X(1)還不是最優(yōu)解。于是再用上述方法，確定換入、換出變量，繼續(xù)迭代，再得到另一個(gè)基可行解X(2)X(2)=(2,3,0,8,0)T再經(jīng)過(guò)一次迭代，再得到一個(gè)基可行解X(3)X(3)=(4,2,0,0,4)T而這時(shí)得到目標(biāo)函數(shù)的表達(dá)式是：z=14-1.5x3-0.125x4

(1-9)z=14-1.5x3-0.125x4

(1-9)再檢查(1-9)式，可見(jiàn)到所有非基變量x3,x4的系數(shù)都是負(fù)數(shù)。這說(shuō)明若要用剩余資源x3,x4，就必須支付附加費(fèi)用。所以當(dāng)x3=x4=0時(shí)，即不再利用這些資源時(shí)，目標(biāo)函數(shù)達(dá)到最大值。所以X(3)是最優(yōu)解。即當(dāng)產(chǎn)品Ⅰ生產(chǎn)4件，產(chǎn)品Ⅱ生產(chǎn)2件，工廠才能得到最大利潤(rùn)。四、單純形法4、單純形法求解線性規(guī)劃再引入一實(shí)例，介紹利用單純形法求解線性規(guī)劃時(shí)可以使用的一種工具，即單純形表。例1-12用單純形法求解下列線性規(guī)劃的最優(yōu)解max

z

=

3x1

+

4x22x1

+

x2

￡

40x1

+

3x2

￡

30x1,

x2

?

0例1-12【解】化為標(biāo)準(zhǔn)型為：max

z

=

3x1

+

4x2

+

0x3

+

0x42x1

+

x2

+

x3

=

40x1

+

3x2

+

x4

=

30x1,

x2

,

x3

,

x4

?

0約束方程的系數(shù)矩陣A為：1

3

0

101

2

3

4A=(P,

P

,

P,

P

)=2

1

1例1-12【解】確定初始基和基變量、非基變量、初始基本可行解。

0

103

4B

=

(P

,

P

)=

1基變量為：x3，x4非基變量為：x1，x2x1

+

3x2

+

x4

=

30x1,

x2

,

x3

,

x4

?

0令非基變量x1=x2=0，代入約束方程中2x1

+

x2

+

x3

=

40得到：x3=40，x4=30則初始基本可行解為：

X（0）=（0，0，40，30）T例1-12【解】以上得到的一組基本可行解是否是最優(yōu)解?從目標(biāo)函數(shù)z=3x1+4x2中看出：X1和x2的系數(shù)大于零，如果x1和x2為一個(gè)正數(shù)，那么目標(biāo)值就能夠變得更大。因此，只要非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒(méi)有達(dá)到最大，即沒(méi)有找到最優(yōu)解。判別線性規(guī)劃問(wèn)題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗(yàn)數(shù)，記作

λj（j=1，2，…，n）。在例1-11中λ1=3，λ2=4，λ3=0，λ4=0。檢驗(yàn)數(shù)：目標(biāo)函數(shù)用非基變量表示，其變量的系數(shù)為檢驗(yàn)數(shù)下面，我們要引入一個(gè)工具，來(lái)幫助我們利用單純形法來(lái)求解線性規(guī)劃，這個(gè)工具是單純形表。根據(jù)以上得到的結(jié)果，我們可以建立初始的單純形表。cj3400CBXBx1x2x3x4θib

(min)0x32110401301300

x4λj(max)340

0

0基變量的檢驗(yàn)數(shù)為零因?yàn)閄（0）不是最優(yōu)解，因此我們就要繼續(xù)尋找下一個(gè)基解，并判斷它是否是最優(yōu)解。所以我們需要對(duì)已經(jīng)得到的基解進(jìn)行改進(jìn)，改進(jìn)的方法是：換基變量。確定換入變量（進(jìn)基變量）方法：λk=max{λj|

λj>0}確定換出變量（出基變量）方法：θk=min{θi=bi/aik|aik>0}換入變量為：x2那么換出變量為x3還是x4呢？確定換出變量為x4cj3400θi(min)CBXBx1x2x3x4b0x321104040/10x413013030/3λj(max)340000x4λj(max)34000換入變量為：x2;換出變量為x4初始單純形表變更為：θi(min)40/130/3希望變成0 希望變成1這樣，形成的基就是單位矩陣。因此，對(duì)增廣矩陣進(jìn)行初等變換！cj3400CBXBx1x2x3x4b0x32110404X21301302104013130換入變量為：x2;換出變量為x4初始單純形表變更為：λj(max)

3

4

0增廣矩陣的第2行中的每個(gè)元素都÷30

0得：如圖所示cj3400θiCBXBx1x2x3x4b(min)0x35/301-1/330404x21/3101/31010增廣矩陣的第1行-第2行 得：如圖所示經(jīng)過(guò)增廣矩陣的初等變換后，基變成了單位矩陣3400確定基可行解X（1）=？因?yàn)棣?=0了，所以只需要將令非基變量x1=x4=0，基λ變2量變x換2=為100，。x方3=法30：矩陣的第所以X（1）=（0，10，30，3行0）-第T

2行×4基可行解是否是最優(yōu)解？依據(jù)檢驗(yàn)數(shù)定義：目標(biāo)函數(shù)用非基變量表示，其變量的系數(shù)為檢驗(yàn)數(shù)。因此需要將基變量的λ變換為0cj3400θi(min)CBXBx1x2x3x4b0x35/301-1/330404x21/3101/31010λj(max)5/300-4/3-40cj3400CBXBx1x2x3x4θib

(min)0x35/3

0

1 -1/3

304

x2

1/3

1

0

1/3

10λj(max)

5/3

0

0 -4/3 -40得出：X（1）=（0，10，30，0）T不是最優(yōu)解下一步：確定換入變量和換出變量請(qǐng)大家自己運(yùn)算，直到確定最優(yōu)解。30183

x15/31-1/3301/301/3105/30-4/3-40將基（P1P2）初等變換為單位矩陣方法：

①

÷5/3 ②-①×1/3確定基本可行解X（2）=（18，4，0，0）T最優(yōu)性性判斷？ ③-①×5/3看到所有的檢驗(yàn)數(shù)都小于0，所以X（2）是最優(yōu)解同時(shí)目標(biāo)函數(shù)值為70cj3400θi(min)CBXBx1x2x3x4b3x1103/5-1/518184x201-1/52/5304λj(max)0-1-10-70-z練習(xí)：將例1-11用單純形表求解。練習(xí)：?jiǎn)渭冃畏ㄇ蠼猓?）1

21

2x

,

x

?

03x1

+

5x2

￡15s.t.6x1

+

2x2

￡

24max

z

=

2x

+

x小結(jié)單純形法是求解線性規(guī)劃問(wèn)題的一種極為有效和方便的方法，用單純形法時(shí)一定要注意以下幾個(gè)問(wèn)題：第一：要將問(wèn)題化為標(biāo)準(zhǔn)型第二：迭代過(guò)程進(jìn)行的應(yīng)是線性變換；第三：判斷是否為最優(yōu)解的標(biāo)準(zhǔn)，即對(duì)極大化問(wèn)題，檢驗(yàn)數(shù)應(yīng)為非正；大家思考：對(duì)極小化問(wèn)題，檢驗(yàn)數(shù)應(yīng)為什么？對(duì)極小化問(wèn)題，檢驗(yàn)數(shù)應(yīng)為非負(fù)。例1-13 單純形法求