關(guān)于線(xiàn)性規(guī)劃及單純形法

線(xiàn)性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。

自1947年美國(guó)數(shù)學(xué)家丹捷格（G.B.Dantzig）提出了求解線(xiàn)性規(guī)劃問(wèn)題的方法——單純形法之后，線(xiàn)性規(guī)劃在理論上趨于成熟，在實(shí)際中的應(yīng)用日益廣泛與深入。特別是在能用計(jì)算機(jī)來(lái)處理成千上萬(wàn)個(gè)約束條件和變量的大規(guī)模線(xiàn)性規(guī)劃問(wèn)題之后，它的適用領(lǐng)域更廣泛了。第一章線(xiàn)性規(guī)劃及單純形法

線(xiàn)性規(guī)劃是一種合理利用資源、合理調(diào)配資源的應(yīng)用數(shù)學(xué)方法。其中：規(guī)劃就是利用某種數(shù)學(xué)方法使得有效資源的運(yùn)用最優(yōu)化；線(xiàn)性就是用來(lái)描述變量之間關(guān)系的函數(shù)是線(xiàn)性函數(shù)。第2頁(yè),共116頁(yè)，2024年2月25日，星期天線(xiàn)性規(guī)劃研究的主要內(nèi)容：

（1）計(jì)劃任務(wù)的確定，如何統(tǒng)籌安排，精心籌劃，用最少的資源來(lái)實(shí)現(xiàn)。這方面的問(wèn)題涉及到系統(tǒng)的投入和求極小值問(wèn)題（2）資源的確定，如何合理利用，合理規(guī)劃，使得完成的任務(wù)最大。

這方面的問(wèn)題涉及到系統(tǒng)的產(chǎn)出和求最大值問(wèn)題

線(xiàn)性規(guī)劃研究和應(yīng)用的內(nèi)容是實(shí)現(xiàn)系統(tǒng)的投入產(chǎn)出的問(wèn)題，就是用最少的勞力和物力消耗，獲利更多更好的社會(huì)需求產(chǎn)品。第3頁(yè),共116頁(yè)，2024年2月25日，星期天1.1線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

1.1.1問(wèn)題的提出(一)

例某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)和原料A、B的消耗量如下表。該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問(wèn)應(yīng)如何安排生產(chǎn)計(jì)劃能使該廠獲利最多？

這個(gè)問(wèn)題可以用下面的數(shù)學(xué)模型來(lái)描述，設(shè)計(jì)劃期內(nèi)產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量分別為x1，x2，可獲利潤(rùn)用z表示，則有：MaxZ=2x1+3x2x1+2x2≤84x1≤16

4x2≤12x1,x2≥0第4頁(yè),共116頁(yè)，2024年2月25日，星期天

1.1.1問(wèn)題的提出(二)

例靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)m3，兩工廠之間有一條流量為每天200萬(wàn)m3的支流（見(jiàn)圖）。

第一化工廠每天排放污水2萬(wàn)m3，第二化工廠每天排放污水1.4萬(wàn)m3。污水從工廠1流到工廠2前會(huì)有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于0.2%。而工廠1和工廠2處理污水的成本分別為1000元/m3和800元/m3。問(wèn)兩工廠各應(yīng)處理多少污水才能使處理污水的總費(fèi)用最低？

設(shè)工廠1和工廠2每天分別處理污水x1和x2萬(wàn)m3，則有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4

x1,x2≥0第5頁(yè),共116頁(yè)，2024年2月25日，星期天1.1.1問(wèn)題的提出(三)例

某養(yǎng)雞場(chǎng)所用的混合飼料是由

n種配料組成。要求這種混合飼料必須含有

m種不同的營(yíng)養(yǎng)成份，而且要求每單位混合飼料中第

i種營(yíng)養(yǎng)成份的含量不能低于

bi(i=1,2,…,m）。已知第

i種營(yíng)養(yǎng)成份在每單位的第

j種配料中的含量為

aij,j=1,2,…,n，每單位的第

j種配料的價(jià)格為

cj

?，F(xiàn)在要求在保證營(yíng)養(yǎng)條件的前提下，應(yīng)采用何種配方，使混合飼料的成本最小.配料營(yíng)養(yǎng)成份B1B2

…Bn含量A1A2…Am

a11a12

…a1na21a22

…a2nam1am2

…amnb1b2bm單價(jià)c1c2…

cn第6頁(yè),共116頁(yè)，2024年2月25日，星期天建立模型：MinZ=c1x1+c2x2+…+cnxn

設(shè)xj

表示在單位混合飼料中，第j種配料的含量（j=1,2,…,n）則有如下的數(shù)學(xué)模型：配料營(yíng)養(yǎng)成份B1B2

…Bn含量A1A2…Ama11a12

…a1na21a22

…a2nam1am2

…amnb1b2bm價(jià)格c1c2…

cna11x1+a12x2+…+a1nxn≥

b1a21x1+a22x2+…+a2nxn≥

b2……am1x1+am2x2+…+amnxn≥

bmx1≥0,x2≥0,…,xn≥0第7頁(yè),共116頁(yè)，2024年2月25日，星期天

1.1.2線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型

線(xiàn)性規(guī)劃問(wèn)題的共同特征（1）每個(gè)問(wèn)題都用一組決策變量(x1,x2,···,xn，Decisionvariable)表示某一方案,這組未知數(shù)的值就代表一個(gè)具體的方案,通常要求這些未知數(shù)取值是非負(fù)的。

（2）存在一定的限制條件(稱(chēng)為約束條件，Constraint),這些條件都可以用關(guān)于決策變量的一組線(xiàn)性等式或不等式來(lái)表示。（3）都有一個(gè)目標(biāo)要求,并且這個(gè)目標(biāo)可表示為這組決策變量的線(xiàn)性函數(shù)(稱(chēng)為目標(biāo)函數(shù)，Objectivefunction),按研究問(wèn)題的不同,要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。

滿(mǎn)足以上三個(gè)條件的數(shù)學(xué)模型稱(chēng)為線(xiàn)性規(guī)劃數(shù)學(xué)模型。其一般形式為第8頁(yè),共116頁(yè)，2024年2月25日，星期天線(xiàn)性規(guī)劃一般模型的代數(shù)式為：max(min)Z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤(或＝,≥)b1a21x1+a22x2+…+a2nxn≤(或＝,≥)b2……………am1x1+am2x2+…+amnxn≤(或＝,≥)bmx1,x2,…,xn≥(≤)0第9頁(yè),共116頁(yè)，2024年2月25日，星期天1.1.3線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型有各種不同的形式，如

目標(biāo)函數(shù)有極大化和極小化；

約束條件有“≤”、“≥”和“＝”三種情況；

決策變量一般有非負(fù)性要求，有的則沒(méi)有。

為了求解方便，特規(guī)定一種線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式，非標(biāo)準(zhǔn)型可以轉(zhuǎn)化為標(biāo)準(zhǔn)型計(jì)算

第10頁(yè),共116頁(yè)，2024年2月25日，星期天標(biāo)準(zhǔn)形式為：

（一）標(biāo)準(zhǔn)形式

目標(biāo)函數(shù)最大化

約束條件為等式

右端常數(shù)項(xiàng)bi≥0

決策變量非負(fù)

maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0第11頁(yè),共116頁(yè)，2024年2月25日，星期天標(biāo)準(zhǔn)型的表達(dá)方式有代數(shù)式、矩陣式：（二）標(biāo)準(zhǔn)型的表達(dá)方式

1.代數(shù)式maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0簡(jiǎn)記maxZ=cjxjaijxj＝bi

(i=1,2,…,m)xj≥0(j=1,2,…,n)第12頁(yè),共116頁(yè)，2024年2月25日，星期天

2.矩陣式化為maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0第13頁(yè),共116頁(yè)，2024年2月25日，星期天（三）非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化

目標(biāo)函數(shù)極小化問(wèn)題

只需將等式兩端乘以-1即變?yōu)闃O大化問(wèn)題。因?yàn)閙inZ=–max(–Z)=CTX，令Z′=-Z，則maxZ′=–CTXminZ=CTX約束條件中右端常數(shù)項(xiàng)非正

兩端同乘以

-1

約束條件為不等式

當(dāng)約束方程為“≤”時(shí)，左端加入一個(gè)非負(fù)的松弛變量，就把不等式變成了等式；如4X1＋2X2

≤60→4X1＋2X2

＋X3

=60

當(dāng)約束條件為“≥”時(shí)，不等式左端減去一個(gè)非負(fù)的剩余變量(也可稱(chēng)松弛變量)，就把不等式變成了等式。

決策變量xk為無(wú)約束變量

令xk=xk‘-xk〃，其中令xk′，xk〃≥0，用xk′、xk〃

取代模型中xk第14頁(yè),共116頁(yè)，2024年2月25日，星期天例1：試將如下線(xiàn)性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型例1的標(biāo)準(zhǔn)型

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.maxZ=

3x1+5x2+0x3

x1+x3=8

2x2≤123x1+4x2≤36x1,x2,x3

≥0maxZ=

3x1+5x2+0x3+

0x4

x1+x3=8

2x2+x4=12

3x1+4x2≤36x1,x2,x3,x4≥0maxZ=

3x1+5x2+0x3+

0x4+0x5

x1+x3=8

2x2+x4=12

3x1+4x2+x5=36x1,x2,x3,x4,x5≥0maxZ=

3x1+5x2+0x3+

0x4+0x5

x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0需要化為標(biāo)準(zhǔn)型引進(jìn)一x3引進(jìn)一x4引進(jìn)一x5第15頁(yè),共116頁(yè)，2024年2月25日，星期天例2：試將如下線(xiàn)性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型minZ=

x1+2x2-3x3x1+2x2-x3≤52x1+3x2-x3≥6

-x1-x2-x3≥-2x1≥0,x3≤0S.t.例2的標(biāo)準(zhǔn)化minZ=

x1+2x2+3x3′x1+2x2+x3

′≤52x1+3x2+x3

′≥6

-x1-x2+x3

′≥-2x1≥0,x3′≥0

minZ=

x1+2(x2′-x2〃

)

+3x3′x1+2(x2′-x2〃

)

+x3

′≤52x1+3(x2′-x2〃

)+x3

′≥6

-x1-(x2′-x2〃

)

+x3

′≥-2x1,

x2′,x2〃,x3′≥0

minZ=

x1+2(x2′-x2〃

)

+3x3′x1+2(x2′-x2〃

)

+x3

′≤52x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′≥0

maxZ′=-x1-2(x2′-x2〃

)

-3x3′+0x4

x1+2(x2′-x2〃

)

+x3

′+x4=5

2x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′,x4≥0

maxZ′=-

x1-2(x2′-x2〃

)

-3x3′

+0x4+0x5

x1+2(x2′-x2〃

)

+x3

′+x4=5

2x1+3(x2′-x2〃

)+x3

′-x5=6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′,x4,x5≥0

maxZ′=-x1-2(x2′-x2〃

)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃

)

+x3

′+x4=5

2x1+3(x2′-x2〃

)+x3

′-x5=6

x1+(x2′-x2〃

)

-x3

′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

maxZ′=-

x1-2(x2′-x2〃

)

-3x3′x1+2(x2′-x2〃

)

+x3

′≤5

2x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′≥0

maxZ′=-x1-2(x2′-x2〃

)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃

)

+x3

′+x4=52x1+3(x2′-x2〃

)+x3

′-x5=6

x1+(x2′-x2〃

)

-x3

′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

需要化為標(biāo)準(zhǔn)型令－x3＝x3’令

x2＝x2’–x2’’令

-Z＝Z’引進(jìn)一x4引進(jìn)一x5引進(jìn)一x6第16頁(yè),共116頁(yè)，2024年2月25日，星期天例3:試將如下線(xiàn)性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型例3的標(biāo)準(zhǔn)型為：

需要化為標(biāo)準(zhǔn)型第17頁(yè),共116頁(yè)，2024年2月25日，星期天練習(xí)：試將如下線(xiàn)性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型（1）maxZ=-x1+3

x3+4

x42x1+4

x2+x3-2

x4≤13

6x1+x3+8

x4≥50

-x1+4

x2-5

x3-3

x4=-10xi≥0,i=1,2,3,4S.t.（2）minZ=

6

x1+7

x2-

x33x1+2

x2-x3≤10

x2+x3≤15

x1≥3x2≥2x1,

x2≥0

，x3無(wú)限制S.t.第18頁(yè),共116頁(yè)，2024年2月25日，星期天答案：（1）maxZ=-x1+3

x3+4

x4+0

x5+0

x62x1+4

x2+x3-2

x4+x5=13

6x1+x3+8

x4-x6=50

x1-4

x2+5

x3+3

x4=10xi≥0,i=1,2,3,4,5,6S.t.（2）maxZ’=-6

x1-7

x2+

x3－x4+0x5+0x6+0x7+0x83x1+2

x2-x3+x4+x5=10

x2+x3－x4+x6=15

x1-x7=3x2-x8=2x1,

x2,

x3,

x4,

x5,

x6,

x7,

x8≥0S.t.第19頁(yè),共116頁(yè)，2024年2月25日，星期天1.1.4線(xiàn)性規(guī)劃解的概念

在討論線(xiàn)性規(guī)劃問(wèn)題的求解之前,先要了解線(xiàn)性規(guī)劃問(wèn)題的解的概念。由前面討論可知線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為：

求解線(xiàn)性規(guī)劃問(wèn)題就是從滿(mǎn)足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)（1）達(dá)到最大值。

若設(shè)矩陣A的秩R(A)=m；根據(jù)線(xiàn)性代數(shù)定理可知，當(dāng)R(A)=m＜n，則方程組有無(wú)窮多個(gè)解，這也正是線(xiàn)性規(guī)劃尋求最優(yōu)解的余地所在。第20頁(yè),共116頁(yè)，2024年2月25日，星期天關(guān)于標(biāo)準(zhǔn)型解的若干基本概念可行解（feasiblesolution）與非可行解（infeasiblesolution

）滿(mǎn)足約束條件（2）和非負(fù)條件（3）的解

X

稱(chēng)為可行解，滿(mǎn)足約束條件（2）但不滿(mǎn)足非負(fù)條件（3）的解

X稱(chēng)為非可行解可行域（feasibleregion）:可行解組成的集合叫做最優(yōu)解（optimalsolution）：使目標(biāo)函數(shù)(1)達(dá)到最大的解稱(chēng)為最優(yōu)解第21頁(yè),共116頁(yè)，2024年2月25日，星期天

基在標(biāo)準(zhǔn)型中，約束方程組的系數(shù)矩陣有n列，即

A=(P1,P2,…,Pn)設(shè)A的秩為m

，當(dāng)R(A)=m＜n

，A中必有線(xiàn)性獨(dú)立的m列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè)基，

即B=(P1,P2,…,Pm)，|B|0

P1

,P2

,…,Pm

稱(chēng)為基向量與基向量對(duì)應(yīng)的變量稱(chēng)為基變量，記為XB=(x1,x2

,…,xm)T其余的變量稱(chēng)為非基變量，記為XN=(xm+1,xm+2,…,xn)T

，故有

X=XB+XN，最多有個(gè)基第22頁(yè),共116頁(yè)，2024年2月25日，星期天

基本解令非基變量XN=0，求得基變量XB的值稱(chēng)為基解，即XB=B

1

b基解是有限的基本可行解基本解XB的非零分量都0

時(shí)，稱(chēng)為基本可行解，否則為基非可行解基本可行解的非零分量個(gè)數(shù)<m時(shí)，稱(chēng)為退化解可行基對(duì)應(yīng)于基本可行解的基，稱(chēng)為可行基第23頁(yè),共116頁(yè)，2024年2月25日，星期天線(xiàn)性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系約束方程的解空間基本解可行解非可行解基本可行解退化解第24頁(yè),共116頁(yè)，2024年2月25日，星期天例1的標(biāo)準(zhǔn)型為maxZ=

3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0

約束方程的增廣矩陣x1x2x3x4x53階非奇異子矩陣為基矩陣還原為maxZ=

3x1+5x2+0x3+0x4+0x5x3=-x1+8x4=-2x2+12x5=-3x1-4x2+36

基變量是x3,x4,x5，令非基變量x1=x2=0，得到x3=8，x4=12，

x5=36基解。此解為基可行解：X0=(0,0,8,12,36)TR(A)=3非基變量是x1,x2，第25頁(yè),共116頁(yè)，2024年2月25日，星期天1.2

線(xiàn)性規(guī)劃問(wèn)題的求解

1.2.1圖解法

對(duì)于簡(jiǎn)單的線(xiàn)性規(guī)劃問(wèn)題(只有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題)，可以通過(guò)圖解法對(duì)它進(jìn)行求解。

圖解法即是用圖示的方法來(lái)求解線(xiàn)性規(guī)劃問(wèn)題。圖解法簡(jiǎn)單直觀，有助于了解線(xiàn)性規(guī)劃問(wèn)題求解的基本原理。

一個(gè)二維的線(xiàn)性規(guī)劃問(wèn)題，可以在平面圖上求解，三維的線(xiàn)性規(guī)劃則要在立體圖上求解，這就比較麻煩，而維數(shù)再高以后就不能用圖示了。

第26頁(yè),共116頁(yè)，2024年2月25日，星期天（一）圖解法的基本步驟

滿(mǎn)足所有約束條件的解叫可行解，解的集合稱(chēng)之為可行域。即所有約束條件共同圍成的區(qū)域。1.可行域的確定例1求解線(xiàn)性規(guī)劃x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D

五邊形OABCD內(nèi)(含邊界)的任意一點(diǎn)(x1，x2)都是滿(mǎn)足所有約束條件的一個(gè)解，稱(chēng)之可行解。maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0第27頁(yè),共116頁(yè)，2024年2月25日，星期天2.最優(yōu)解的確定

確定x1、x2希望目標(biāo)函數(shù)Z=

3x1+5x2達(dá)到最大，圖形中Z=

3x1+5x2代表以Z為參數(shù)的一族平行線(xiàn)，即等值線(xiàn)。

等值線(xiàn)：位于同一直線(xiàn)上的點(diǎn)的目標(biāo)函數(shù)值相同。

Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)D

最優(yōu)解：可行解中使目標(biāo)函數(shù)最優(yōu)(極大或極小)的解

本題中：滿(mǎn)足目標(biāo)函數(shù)最大的極點(diǎn)是離原點(diǎn)距離最遠(yuǎn)的點(diǎn)（4,6）Z=3x1+5x2＝24Z=3x1+5x2＝30Z=39Z=42即x1=4，x2=6時(shí)Z的值最大為42。

C(4,6)為最優(yōu)解第28頁(yè),共116頁(yè)，2024年2月25日，星期天（二）解的幾種可能性唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)。如上題的最優(yōu)解（4,6）

多重最優(yōu)解：無(wú)窮多個(gè)最優(yōu)解。若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線(xiàn)上的每一點(diǎn)都是最優(yōu)解。x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D如例1的數(shù)學(xué)模型變?yōu)?/p>

maxZ=

3x1+4x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.Z=24Z=36Z=12第29頁(yè),共116頁(yè)，2024年2月25日，星期天

線(xiàn)性規(guī)劃問(wèn)題的可行域無(wú)界，使目標(biāo)函數(shù)無(wú)限增大而無(wú)界。（缺乏必要的約束條件）例如

maxZ=

3x1+2x2-2x1+x2≤2x1-3x2≤3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-1x1123-1Z=6Z=12S.t.例如

maxZ=

3x1+2x2-2x1+x2≥2x1-3x2≥3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-1x1123-1S.t.無(wú)界解：無(wú)可行解：若約束條件相互矛盾，則可行域?yàn)榭占?。?0頁(yè),共116頁(yè)，2024年2月25日，星期天例：求最大值問(wèn)題數(shù)學(xué)模型為：

四邊形OBQC內(nèi)(含邊界)的任意一點(diǎn)(x1，x2)都是滿(mǎn)足所有約束條件的一個(gè)解，稱(chēng)之可行解。maxZ=

8x1+6x2

4x1+2x2≤602x1+4x2≤482x1+3x2≤36x1≥0,x2≥02x1+3x2

=36x1x2510510150C(0,12)4x1+2x2

=602x1+4x2

=48B(15,0)Z=0Z=72Z=120Z=126Q(13.5,3)結(jié)論：在Q(13.5,3)處利潤(rùn)最大為126，Q(13.5,3)為最優(yōu)解第31頁(yè),共116頁(yè)，2024年2月25日，星期天例：求最小值問(wèn)題

設(shè)有某林場(chǎng)需配制某種滅蟲(chóng)藥水500公斤，該藥水系由甲與乙兩種藥水混合而成。甲種藥水每公斤5元，乙種藥水每公斤8元。按照兩種藥水的化學(xué)性質(zhì)，在混合時(shí)，500公斤混合藥水中含甲種藥水最多不能超過(guò)400公斤，含乙種藥水最少不能少于200公斤。問(wèn)如何配制可使該藥水配制成本最低？.

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0則數(shù)學(xué)模型為：設(shè)：500公斤混合藥水中，甲種藥水x1公斤，乙種藥水x2公斤第32頁(yè),共116頁(yè)，2024年2月25日，星期天例：求最小值問(wèn)題數(shù)學(xué)模型為：

線(xiàn)段BC上的任意一點(diǎn)(x1，x2)都是滿(mǎn)足所有約束條件的一個(gè)解，稱(chēng)之可行解。

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0結(jié)論：等成本線(xiàn)往右下移，成本越來(lái)越小，A(300,200)成本為最小Z=5x1+8x2

=4000Z=3100x2

=200x1+x2

=500x1x2502004000B(0,500)100300500x1

=400100200300400CA最優(yōu)解為（300,200）第33頁(yè),共116頁(yè)，2024年2月25日，星期天練習(xí)題：用圖解法求解下列問(wèn)題－x＋2y≤2x＋2y≤6

x－y≤3

x＋3y≥3x≥0,y

≥01.約束條件為：（1）maxZ=

4x+y畫(huà)出可行域圖形，求下面幾種情況下的最優(yōu)解（2）minZ=

2x-3y（3）maxZ=

x+2y（4）maxZ=

2x-3y第34頁(yè),共116頁(yè)，2024年2月25日，星期天練習(xí)題：求解－x＋2y≤2x＋2y≤6

x－y≤3

x＋3y≥3x≥0,y

≥0（1）maxZ=

4x+y求下面幾種情況下的最優(yōu)解（2）minZ=

2x-3y（4）maxZ=

x+2y（3）maxZ=

2x-3yx+3y=3－x+2y=2x－y

=3x1x2161234523x+2y=6(2,2)(4,1)(3,0)(0,1)Z=4x+y=1Z=10Z=12Z=17Z=-3Z=-2Z=5Z=6最優(yōu)解x=4,y=1maxZ=

17最優(yōu)解x=0,y=1minZ=

-3Z=2x+y=1Z=3Z=6有無(wú)窮多最優(yōu)解maxZ=

6最優(yōu)解x=3,y=0maxZ=

6第35頁(yè),共116頁(yè)，2024年2月25日，星期天1.2.2單純形法（SimpleMethod）（一）線(xiàn)性規(guī)劃解的基本概念和基本定理基本概念1、凸集:假設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集,若對(duì)于K中的任意兩點(diǎn)X1、X2,其連線(xiàn)上的所有點(diǎn)

X1+(1-)X2(01)都在集合K中,即:X1+(1-)X2K(01),則稱(chēng)K為凸集。2.頂點(diǎn):假設(shè)K

是凸集,X

K;若不能用不同的兩個(gè)點(diǎn)X1、X2

K

的線(xiàn)性組合表示為:X=X1+(1-

)X2

，(0<

<1)，則稱(chēng)X

為凸集K

的一個(gè)頂點(diǎn)（或稱(chēng)為極點(diǎn)）。第36頁(yè),共116頁(yè)，2024年2月25日，星期天若線(xiàn)性規(guī)劃問(wèn)題存在可行域，則其可行域一定是凸集。

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

定理3：

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

x1x248123690ABC(4,6)D

定理1：基本定理綜合定理2和定理3得：線(xiàn)性規(guī)劃問(wèn)題若存在最優(yōu)解則最優(yōu)解一定存在于基本可行解之中。第37頁(yè),共116頁(yè)，2024年2月25日，星期天（二）線(xiàn)性規(guī)劃的解題思路

線(xiàn)性規(guī)劃問(wèn)題可以有無(wú)數(shù)個(gè)可行解，而有限個(gè)頂點(diǎn)對(duì)應(yīng)的是基本可行解，最優(yōu)解只可能在頂點(diǎn)(基本可行解)上達(dá)到，故只要在有限個(gè)基可行解中尋求最優(yōu)解即可。其思路是：

從線(xiàn)性規(guī)劃問(wèn)題的一個(gè)基本可行解開(kāi)始，轉(zhuǎn)換到另一個(gè)使目標(biāo)函數(shù)值增大的基本可行解。反復(fù)迭代，直到目標(biāo)函數(shù)值達(dá)到最大時(shí)，就得到了最優(yōu)解。。第38頁(yè),共116頁(yè)，2024年2月25日，星期天（三）線(xiàn)性規(guī)劃單純形法的解題流程第39頁(yè),共116頁(yè)，2024年2月25日，星期天（四）線(xiàn)性規(guī)劃解題工具----單純形表格及其格式CjC1…CmCm+1…Cn比值CBXBbx1…XmXm+1…xnC1X1b11…0a1m+1…a1n

1C2X2b20…0a2m+1…a2n

2………………………Cmxmbm0…1amm+1…amn

m檢驗(yàn)數(shù)j-Z0…0

m+1…

nmaxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bm第40頁(yè),共116頁(yè)，2024年2月25日，星期天（五）線(xiàn)性規(guī)劃求解需要解決的技術(shù)問(wèn)題

按照單純形法的思路求解線(xiàn)性規(guī)劃問(wèn)題,要解決三個(gè)技術(shù)問(wèn)題:⑴給出第一個(gè)基本可行解;⑵檢驗(yàn)一個(gè)基本可行解是否是最優(yōu)解;⑶轉(zhuǎn)換到另一個(gè)基本可行解.

⑴把線(xiàn)性規(guī)劃問(wèn)題變成標(biāo)準(zhǔn)型后,觀察是否每個(gè)約束方程中都有獨(dú)有的、系數(shù)為1的變量.如果是,則取這些變量作為基變量,便得到一個(gè)基本可行解;否則,就給沒(méi)有這種變量的約束條件添加一個(gè)人工變量,同時(shí)修改目標(biāo)函數(shù).(見(jiàn)例題)

⑵如果單純形表最后一行中的σj都滿(mǎn)足σj≤0,則對(duì)應(yīng)的基本可行解是最優(yōu)解;否則就不是最優(yōu)解.σj稱(chēng)為檢驗(yàn)數(shù).

第41頁(yè),共116頁(yè)，2024年2月25日，星期天

⑶第一,確定換入變量.在大于0的檢驗(yàn)數(shù)中找最大的為σk,對(duì)應(yīng)變量xk為換入變量.第二,確定換出變量.取θ=min{bi/a‘ik|a’ik>0}=bl/a’lk,對(duì)應(yīng)的第l行的基變量為換出變量.第三,旋轉(zhuǎn)運(yùn)算.換入變量所在的行與換出變量所在的列交叉點(diǎn)的元素稱(chēng)為中心元素,用高斯消去法把中心元素化成1,同列的其他元素化成0,得到一個(gè)新的單純形表,也就得到一個(gè)新的基本可行解.

第42頁(yè),共116頁(yè)，2024年2月25日，星期天（六）表格單純形法的計(jì)算步驟maxZ=3x1+5x2x1

≤

82x2

≤123x1+4x2

≤36Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000maxZ=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36

標(biāo)準(zhǔn)型基變量x3,x4,x5，1、建立初始單純形表非基變量x1,x2第43頁(yè),共116頁(yè)，2024年2月25日，星期天2、求初始基本可行解并進(jìn)行最優(yōu)性檢驗(yàn)Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000

令非基變量x1=0，x2=0，找到一個(gè)初始基可行解：

x1=0，x2=0，x3=8，x4=12，x5=36，

σj＞0，此解不是最優(yōu)（因?yàn)閦=3x1+5x2+0x3+0x4+0x5)可求基可行解的狀態(tài)即X0=(0,0,8,12,36)T，此時(shí)利潤(rùn)Z=0第44頁(yè),共116頁(yè)，2024年2月25日，星期天初始基本可行解圖示Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)DX0=(0,0,8,12,36)T說(shuō)明：一個(gè)可行解就是一個(gè)生產(chǎn)方案，上述方案表明兩種產(chǎn)品都不生產(chǎn)x1=0，x2=0

，利潤(rùn)Z=0。第45頁(yè),共116頁(yè)，2024年2月25日，星期天3、尋找另一基本可行解Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9

中心元素首先確定換入變量再確定換出變量第46頁(yè),共116頁(yè)，2024年2月25日，星期天檢驗(yàn)數(shù)j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即得基可行解X1=(0,6,8,0,12)T

此時(shí)Z＝30σ1=3＞0，此解不是最優(yōu)迭代可求基可行解的狀態(tài)第47頁(yè),共116頁(yè)，2024年2月25日，星期天第一次基迭代可行解圖示Z=3x1+5x2＝30x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)DX1=(0,6,8,0,12)T第48頁(yè),共116頁(yè)，2024年2月25日，星期天4、尋找下一基本可行解Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4檢驗(yàn)數(shù)j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最優(yōu)解:X*=(4,6,4,0,0)T，Z*=42令x4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T此時(shí)Z＝42

j＜0第49頁(yè),共116頁(yè)，2024年2月25日，星期天單純形法的幾何意義x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)DX0=(0,0,8,12,36)T,Z＝0X1=(0,6,8,0,12)T,Z＝30X1=(4,6,4,0,0)T,Z＝42第50頁(yè),共116頁(yè)，2024年2月25日，星期天單純形法－表格法又例Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x52300081210016400101204001x3x4x5000023000

Maxz=2x1+3x2x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3≥0標(biāo)準(zhǔn)型基變量x3,x4,x5，非基變量x1,x21、建立初始單純形表Maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1,x2,x3≥0

j＞0第51頁(yè),共116頁(yè)，2024年2月25日，星期天2、尋找另一基本可行解Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x52300081210016400101204001x3x4x50000230004-3中心元素檢驗(yàn)數(shù)j21010-2/41640010301001/4x3x4x2003-92000-3/4σ1=2＞0，此解不是最優(yōu)第52頁(yè),共116頁(yè)，2024年2月25日，星期天3、尋找下一基本可行解Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x52300021010-2/41640010301001/4x3x4x2003-92000-3/424－中心元素檢驗(yàn)數(shù)j21010-2/4800－412301001/4x1x4x2203－1300－201/4σ5=1/4＞0，此解不是最優(yōu)第53頁(yè),共116頁(yè)，2024年2月25日，星期天4、再次尋找下一基本可行解Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x52300021010-2/4800－412301001/4X1X4X2203－1300－201/4-412檢驗(yàn)數(shù)j41001/40400－21/212011/2-1/80x1x5x2203－1400－3/2-1/80σi＜0，此解最優(yōu)令x3=0，x4=0，x1=4，x2=2，x5=4，即X0=(4,2,0,0,4)T此時(shí)Z＝14第54頁(yè),共116頁(yè)，2024年2月25日，星期天小結(jié)：?jiǎn)渭冃伪砀穹ǖ挠?jì)算步驟①將線(xiàn)性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型。②找出或構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表。③計(jì)算各非基變量xj的檢驗(yàn)數(shù)

j=Cj-CBPj′，若所有

j≤0，則問(wèn)題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步。④在大于0的檢驗(yàn)數(shù)中，若某個(gè)

k所對(duì)應(yīng)的系數(shù)列向量Pk′≤0，則此問(wèn)題是無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入下步。⑤根據(jù)max{

j｜

j＞0}=

k原則，確定xk為換入變量(進(jìn)基變量)，再按

規(guī)則計(jì)算：

=min{bi′/aik′|aik′＞0}=bl′/alk′

確定xBl為換出變量。建立新的單純形表，此時(shí)基變量中xk取代了xBl的位置。⑥以aik′為中心元素進(jìn)行迭代，把xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik′變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③步。第55頁(yè),共116頁(yè)，2024年2月25日，星期天

用單純形法求解線(xiàn)性規(guī)劃問(wèn)題后，應(yīng)回答下面幾個(gè)問(wèn)題：⑴是否解無(wú)界？上面的步驟已作出回答。⑵是否無(wú)可行解？求解后，若人工變量都已取0，則有可行解；否則，無(wú)可行解。⑶唯一最優(yōu)解還是無(wú)窮多最優(yōu)解？在最后的單純形表中，若所有非基變量的檢驗(yàn)數(shù)都嚴(yán)格小于0，則為唯一最優(yōu)解；若存在某個(gè)非基變量的檢驗(yàn)數(shù)等于0，則有無(wú)窮多最優(yōu)解。第56頁(yè),共116頁(yè)，2024年2月25日，星期天

1.2.3單純形法的進(jìn)一步討論用單純形法解題時(shí)，需要有一個(gè)單位陣作為初始基。當(dāng)約束條件都是“≤”時(shí)，加入松弛變量就形成了初始基。但實(shí)際存在“≥”或“＝”型的約束，就沒(méi)有現(xiàn)成的單位矩陣。采用人造基的辦法：人為構(gòu)造單位矩陣處理方法有兩種：大M法兩階段法第57頁(yè),共116頁(yè)，2024年2月25日，星期天（一）大M法1、單純形法表maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.沒(méi)有單位矩陣，不符合構(gòu)造初始基的條件，需加入人工變量。maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0

人工變量最終必須等于0才能保持原問(wèn)題性質(zhì)不變。為保證人工變量為0，在目標(biāo)函數(shù)中令其系數(shù)為-M。M為無(wú)限大的正數(shù)，這是一個(gè)懲罰項(xiàng)，倘若人工變量不為零，則目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去。如若到最終表中人工變量仍沒(méi)有置換出去，那么這個(gè)問(wèn)題就沒(méi)有可行解，當(dāng)然亦無(wú)最優(yōu)解。第58頁(yè),共116頁(yè)，2024年2月25日，星期天

按大M法構(gòu)造人造基，引入人工變量x4,x5的輔助問(wèn)題如下：

maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0

Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53-1-2-M-M632-31041-2101x4x5-M-M0-M-2+M-1-2M3+M4M00-2-2M-13+4M10M-M-M-2-13第59頁(yè),共116頁(yè)，2024年2月25日，星期天

檢驗(yàn)數(shù)jbXBCB比值Cjx5x4x3x2x1-M-M-2-1301-3236101-21400-2-2M-13+4M10Mx5x4-M-M42-1檢驗(yàn)數(shù)j212/3-11/3020-8/32-1/31-70-3-8M/31+2M-1-4M/30x1x53-M檢驗(yàn)數(shù)j31-2/301/61/210-4/31-1/61/2-70-5/30-M-5/6-M-1/2x1x33-2x2=0,x4=0,x5=0,x1=3,x3=1,σj<0，此解最優(yōu),Z=7第60頁(yè),共116頁(yè)，2024年2月25日，星期天2、矩陣解法按大M法構(gòu)造人造基，引入人工變量x4,x5的輔助問(wèn)題如下：

maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x