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

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

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

線性規(guī)劃是一種合理利用資源、合理調(diào)配資源的應(yīng)用數(shù)學(xué)方法。其中：規(guī)劃就是利用某種數(shù)學(xué)方法使得有效資源的運(yùn)用最優(yōu)化；線性就是用來描述變量之間關(guān)系的函數(shù)是線性函數(shù)。目前一頁\總數(shù)一百一十二頁\編于六點(diǎn)線性規(guī)劃研究的主要內(nèi)容：

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

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

線性規(guī)劃研究和應(yīng)用的內(nèi)容是實(shí)現(xiàn)系統(tǒng)的投入產(chǎn)出的問題，就是用最少的勞力和物力消耗，獲利更多更好的社會(huì)需求產(chǎn)品。目前二頁\總數(shù)一百一十二頁\編于六點(diǎn)1.1線性規(guī)劃問題及其數(shù)學(xué)模型

1.1.1問題的提出(一)

例某工廠在計(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元，問應(yīng)如何安排生產(chǎn)計(jì)劃能使該廠獲利最多？

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

4x2≤12x1,x2≥0目前三頁\總數(shù)一百一十二頁\編于六點(diǎn)

1.1.1問題的提出(二)

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

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

設(shè)工廠1和工廠2每天分別處理污水x1和x2萬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目前四頁\總數(shù)一百一十二頁\編于六點(diǎn)1.1.1問題的提出(三)例

某養(yǎng)雞場所用的混合飼料是由n種配料組成。要求這種混合飼料必須含有m種不同的營養(yǎng)成份，而且要求每單位混合飼料中第i種營養(yǎng)成份的含量不能低于bi(i=1,2,…,m）。已知第i種營養(yǎng)成份在每單位的第j種配料中的含量為aij,j=1,2,…,n，每單位的第j種配料的價(jià)格為cj

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

…Bn含量A1A2…Am

a11a12

…a1na21a22

…a2nam1am2

…amnb1b2bm單價(jià)c1c2…

cn目前五頁\總數(shù)一百一十二頁\編于六點(diǎn)建立模型：MinZ=c1x1+c2x2+…+cnxn

設(shè)xj

表示在單位混合飼料中，第j種配料的含量（j=1,2,…,n）則有如下的數(shù)學(xué)模型：配料營養(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目前六頁\總數(shù)一百一十二頁\編于六點(diǎn)

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

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

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

滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。其一般形式為目前七頁\總數(shù)一百一十二頁\編于六點(diǎn)線性規(guī)劃一般模型的代數(shù)式為：max(min)Z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤(或＝,≥)b1a21x1+a22x2+…+a2nxn≤(或＝,≥)b2……………am1x1+am2x2+…+amnxn≤(或＝,≥)bmx1,x2,…,xn≥(≤)0目前八頁\總數(shù)一百一十二頁\編于六點(diǎn)1.1.3線性規(guī)劃問題的標(biāo)準(zhǔn)形式

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

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

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

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

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

目前九頁\總數(shù)一百一十二頁\編于六點(diǎn)標(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目前十頁\總數(shù)一百一十二頁\編于六點(diǎn)標(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簡記maxZ=cjxjaijxj＝bi

(i=1,2,…,m)xj≥0(j=1,2,…,n)目前十一頁\總數(shù)一百一十二頁\編于六點(diǎn)

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

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0目前十二頁\總數(shù)一百一十二頁\編于六點(diǎn)（三）非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化

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

只需將等式兩端乘以-1即變?yōu)闃O大化問題。因?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ù)的剩余變量(也可稱松弛變量)，就把不等式變成了等式。

決策變量xk為無約束變量

令xk=xk‘-xk〃，其中令xk′，xk〃≥0，用xk′、xk〃取代模型中xk目前十三頁\總數(shù)一百一十二頁\編于六點(diǎn)例1：試將如下線性規(guī)劃問題化成標(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=82x2≤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目前十四頁\總數(shù)一百一十二頁\編于六點(diǎn)例2：試將如下線性規(guī)劃問題化成標(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=52x1+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目前十五頁\總數(shù)一百一十二頁\編于六點(diǎn)例3:試將如下線性規(guī)劃問題化成標(biāo)準(zhǔn)型例3的標(biāo)準(zhǔn)型為：

需要化為標(biāo)準(zhǔn)型目前十六頁\總數(shù)一百一十二頁\編于六點(diǎn)練習(xí)：試將如下線性規(guī)劃問題化成標(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≤15x1≥3x2≥2x1,

x2≥0，x3無限制S.t.目前十七頁\總數(shù)一百一十二頁\編于六點(diǎn)答案：（1）maxZ=-x1+3

x3+4

x4+0

x5+0

x62x1+4

x2+x3-2

x4+x5=13

6x1+x3+8

x4-x6=50x1-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=15x1-x7=3x2-x8=2x1,

x2,

x3,

x4,

x5,

x6,

x7,

x8≥0S.t.目前十八頁\總數(shù)一百一十二頁\編于六點(diǎn)1.1.4線性規(guī)劃解的概念

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

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

若設(shè)矩陣A的秩R(A)=m；根據(jù)線性代數(shù)定理可知，當(dāng)R(A)=m＜n，則方程組有無窮多個(gè)解，這也正是線性規(guī)劃尋求最優(yōu)解的余地所在。目前十九頁\總數(shù)一百一十二頁\編于六點(diǎn)關(guān)于標(biāo)準(zhǔn)型解的若干基本概念可行解（feasiblesolution）與非可行解（infeasiblesolution

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

X

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

X稱為非可行解可行域（feasibleregion）:可行解組成的集合叫做最優(yōu)解（optimalsolution）：使目標(biāo)函數(shù)(1)達(dá)到最大的解稱為最優(yōu)解目前二十頁\總數(shù)一百一十二頁\編于六點(diǎn)

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

A=(P1,P2,…,Pn)設(shè)A的秩為m，當(dāng)R(A)=m＜n，A中必有線性獨(dú)立的m列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè)基，

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

P1,P2

,…,Pm

稱為基向量與基向量對(duì)應(yīng)的變量稱為基變量，記為XB=(x1,x2,…,xm)T其余的變量稱為非基變量，記為XN=(xm+1,xm+2,…,xn)T，故有

X=XB+XN，最多有個(gè)基目前二十一頁\總數(shù)一百一十二頁\編于六點(diǎn)

基本解令非基變量XN=0，求得基變量XB的值稱為基解，即XB=B1

b基解是有限的基本可行解基本解XB的非零分量都0時(shí)，稱為基本可行解，否則為基非可行解基本可行解的非零分量個(gè)數(shù)<m時(shí)，稱為退化解可行基對(duì)應(yīng)于基本可行解的基，稱為可行基目前二十二頁\總數(shù)一百一十二頁\編于六點(diǎn)線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系約束方程的解空間基本解可行解非可行解基本可行解退化解目前二十三頁\總數(shù)一百一十二頁\編于六點(diǎn)例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，目前二十四頁\總數(shù)一百一十二頁\編于六點(diǎn)1.2

線性規(guī)劃問題的求解

1.2.1圖解法

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

圖解法即是用圖示的方法來求解線性規(guī)劃問題。圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理。

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

目前二十五頁\總數(shù)一百一十二頁\編于六點(diǎn)（一）圖解法的基本步驟

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

=36x1x248123690ABC(4,6)D

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

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0目前二十六頁\總數(shù)一百一十二頁\編于六點(diǎn)2.最優(yōu)解的確定

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

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

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

等值線：位于同一直線上的點(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)(極大或極小)的解

本題中：滿足目標(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)解目前二十七頁\總數(shù)一百一十二頁\編于六點(diǎn)（二）解的幾種可能性唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)。如上題的最優(yōu)解（4,6）

多重最優(yōu)解：無窮多個(gè)最優(yōu)解。若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的每一點(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目前二十八頁\總數(shù)一百一十二頁\編于六點(diǎn)

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

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.無界解：無可行解：若約束條件相互矛盾，則可行域?yàn)榭占Ｄ壳岸彭揬總數(shù)一百一十二頁\編于六點(diǎn)例：求最大值問題數(shù)學(xué)模型為：

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

8x1+6x24x1+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)處利潤最大為126，Q(13.5,3)為最優(yōu)解目前三十頁\總數(shù)一百一十二頁\編于六點(diǎn)例：求最小值問題

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

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0則數(shù)學(xué)模型為：設(shè)：500公斤混合藥水中，甲種藥水x1公斤，乙種藥水x2公斤目前三十一頁\總數(shù)一百一十二頁\編于六點(diǎn)例：求最小值問題數(shù)學(xué)模型為：

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

minZ=

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

=4000Z=3100x2

=200x1+x2

=500x1x2502004000B(0,500)100300500x1

=400100200300400CA最優(yōu)解為（300,200）目前三十二頁\總數(shù)一百一十二頁\編于六點(diǎn)練習(xí)題：用圖解法求解下列問題－x＋2y≤2x＋2y≤6x－y≤3x＋3y≥3x≥0,y

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

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

2x-3y（3）maxZ=

x+2y（4）maxZ=

2x-3y目前三十三頁\總數(shù)一百一十二頁\編于六點(diǎn)練習(xí)題：求解－x＋2y≤2x＋2y≤6x－y≤3x＋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有無窮多最優(yōu)解maxZ=

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

6目前三十四頁\總數(shù)一百一十二頁\編于六點(diǎn)1.2.2單純形法（SimpleMethod）（一）線性規(guī)劃解的基本概念和基本定理基本概念1、凸集:假設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集,若對(duì)于K中的任意兩點(diǎn)X1、X2,其連線上的所有點(diǎn)X1+(1-)X2(01)都在集合K中,即:X1+(1-)X2K(01),則稱K為凸集。2.頂點(diǎn):假設(shè)K是凸集,XK;若不能用不同的兩個(gè)點(diǎn)X1、X2K的線性組合表示為:X=X1+(1-)X2，(0<<1)，則稱X為凸集K的一個(gè)頂點(diǎn)（或稱為極點(diǎn)）。目前三十五頁\總數(shù)一百一十二頁\編于六點(diǎn)若線性規(guī)劃問題存在可行域，則其可行域一定是凸集。

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

定理3：

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

x1x248123690ABC(4,6)D

定理1：基本定理綜合定理2和定理3得：線性規(guī)劃問題若存在最優(yōu)解則最優(yōu)解一定存在于基本可行解之中。目前三十六頁\總數(shù)一百一十二頁\編于六點(diǎn)（二）線性規(guī)劃的解題思路

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

從線性規(guī)劃問題的一個(gè)基本可行解開始，轉(zhuǎn)換到另一個(gè)使目標(biāo)函數(shù)值增大的基本可行解。反復(fù)迭代，直到目標(biāo)函數(shù)值達(dá)到最大時(shí)，就得到了最優(yōu)解。。目前三十七頁\總數(shù)一百一十二頁\編于六點(diǎn)（三）線性規(guī)劃單純形法的解題流程目前三十八頁\總數(shù)一百一十二頁\編于六點(diǎn)（四）線性規(guī)劃解題工具----單純形表格及其格式CjC1…CmCm+1…Cn比值CBXBbx1…XmXm+1…xnC1X1b11…0a1m+1…a1n1C2X2b20…0a2m+1…a2n2………………………Cmxmbm0…1amm+1…amnm檢驗(yàn)數(shù)j-Z0…0m+1…nmaxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bm目前三十九頁\總數(shù)一百一十二頁\編于六點(diǎn)（五）線性規(guī)劃求解需要解決的技術(shù)問題

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

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

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

目前四十頁\總數(shù)一百一十二頁\編于六點(diǎn)

⑶第一,確定換入變量.在大于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)的元素稱為中心元素,用高斯消去法把中心元素化成1,同列的其他元素化成0,得到一個(gè)新的單純形表,也就得到一個(gè)新的基本可行解.

目前四十一頁\總數(shù)一百一十二頁\編于六點(diǎn)（六）表格單純形法的計(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目前四十二頁\總數(shù)一百一十二頁\編于六點(diǎn)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í)利潤Z=0目前四十三頁\總數(shù)一百一十二頁\編于六點(diǎn)初始基本可行解圖示Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)DX0=(0,0,8,12,36)T說明：一個(gè)可行解就是一個(gè)生產(chǎn)方案，上述方案表明兩種產(chǎn)品都不生產(chǎn)x1=0，x2=0，利潤Z=0。目前四十四頁\總數(shù)一百一十二頁\編于六點(diǎn)3、尋找另一基本可行解Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9

中心元素首先確定換入變量再確定換出變量目前四十五頁\總數(shù)一百一十二頁\編于六點(diǎn)檢驗(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)目前四十六頁\總數(shù)一百一十二頁\編于六點(diǎn)第一次基迭代可行解圖示Z=3x1+5x2＝30x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)DX1=(0,6,8,0,12)T目前四十七頁\總數(shù)一百一十二頁\編于六點(diǎn)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＝42j＜0目前四十八頁\總數(shù)一百一十二頁\編于六點(diǎn)單純形法的幾何意義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目前四十九頁\總數(shù)一百一十二頁\編于六點(diǎn)單純形法－表格法又例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≥0j＞0目前五十頁\總數(shù)一百一十二頁\編于六點(diǎn)2、尋找另一基本可行解Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x52300081210016400101204001x3x4x50000230004-3中心元素檢驗(yàn)數(shù)j21010-2/41640010301001/4x3x4x2003-92000-3/4σ1=2＞0，此解不是最優(yōu)目前五十一頁\總數(shù)一百一十二頁\編于六點(diǎn)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)目前五十二頁\總數(shù)一百一十二頁\編于六點(diǎn)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目前五十三頁\總數(shù)一百一十二頁\編于六點(diǎn)小結(jié)：單純形表格法的計(jì)算步驟①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。②找出或構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表。③計(jì)算各非基變量xj的檢驗(yàn)數(shù)j=Cj-CBPj′，若所有j≤0，則問題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步。④在大于0的檢驗(yàn)數(shù)中，若某個(gè)k所對(duì)應(yīng)的系數(shù)列向量Pk′≤0，則此問題是無界解，停止計(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)第③步。目前五十四頁\總數(shù)一百一十二頁\編于六點(diǎn)

用單純形法求解線性規(guī)劃問題后，應(yīng)回答下面幾個(gè)問題：⑴是否解無界？上面的步驟已作出回答。⑵是否無可行解？求解后，若人工變量都已取0，則有可行解；否則，無可行解。⑶唯一最優(yōu)解還是無窮多最優(yōu)解？在最后的單純形表中，若所有非基變量的檢驗(yàn)數(shù)都嚴(yán)格小于0，則為唯一最優(yōu)解；若存在某個(gè)非基變量的檢驗(yàn)數(shù)等于0，則有無窮多最優(yōu)解。目前五十五頁\總數(shù)一百一十二頁\編于六點(diǎn)

1.2.3單純形法的進(jìn)一步討論用單純形法解題時(shí)，需要有一個(gè)單位陣作為初始基。當(dāng)約束條件都是“≤”時(shí)，加入松弛變量就形成了初始基。但實(shí)際存在“≥”或“＝”型的約束，就沒有現(xiàn)成的單位矩陣。采用人造基的辦法：人為構(gòu)造單位矩陣處理方法有兩種：大M法兩階段法目前五十六頁\總數(shù)一百一十二頁\編于六點(diǎn)（一）大M法1、單純形法表maxZ=

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

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0人工變量最終必須等于0才能保持原問題性質(zhì)不變。為保證人工變量為0，在目標(biāo)函數(shù)中令其系數(shù)為-M。M為無限大的正數(shù)，這是一個(gè)懲罰項(xiàng)，倘若人工變量不為零，則目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去。如若到最終表中人工變量仍沒有置換出去，那么這個(gè)問題就沒有可行解，當(dāng)然亦無最優(yōu)解。目前五十七頁\總數(shù)一百一十二頁\編于六點(diǎn)

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

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0Cj比值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目前五十八頁\總數(shù)一百一十二頁\編于六點(diǎn)

檢驗(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目前五十九頁\總數(shù)一百一十二頁\編于六點(diǎn)2、矩陣解法按大M法構(gòu)造人造基，引入人工變量x4,x5的輔助問題如下：maxZ=

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

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.目前六十頁\總數(shù)一百一十二頁\編于六點(diǎn)

將線性規(guī)劃問題標(biāo)準(zhǔn)化3x1+2x2-3x3+x4=6x1-2x2+x3+x5=4-Z+3x1-x2-2x3-Mx4-Mx5=0x1,x2,x3,x4,x5≥00-M-2-13-Z411-21060-3230-M01初等變換～10M0-2-2M-13+4M-Z411-21060-3230001目前六十一頁\總數(shù)一百一十二頁\編于六點(diǎn)初等變換10M0-2-2M-13+4M-Z411-21060-3230001～-6+2M01+2M-3-8M/30-Z212-8/30020-12/310-1-4M/3-1/31/3-7-M-1/20-5/30-Z11/21-4/30031/20-2/310-M-5/6-1/61/6～x2=0,x4=0,x5=0,x1=3,x3=1,σj<0，此解最優(yōu),Z=7目前六十二頁\總數(shù)一百一十二頁\編于六點(diǎn)試用大M法求解如下線性規(guī)劃問題的最優(yōu)解。按大M法構(gòu)造人造基，引入人工變量x4,x5的輔助問題如下：松馳變量剩余變量人工變量懲罰項(xiàng)目前六十三頁\總數(shù)一百一十二頁\編于六點(diǎn)試用大M法求解如下線性規(guī)劃問題的最優(yōu)解。0-M0-1-13-Z’11010-2030021-4011011-21000-10-M010～4M00-1+3M-1+M3-6M-Z’11010-2030021-4011011-210-M0-100010x1=0,x2=0,x5=0,x3=0,x5=0,x4=11,x6=3,x7=1即X0=(0,0,0,11,0,3,1)T

,Z=0-Z’‘x1

x2

x3