線性規(guī)劃與單純形法

一、線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃是運籌學(xué)的一個重要分支。線性規(guī)劃在理論上比較成熟，在實用中的應(yīng)用日益廣泛與深入。特別是在電子計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。從解決技術(shù)問題的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)、軍事、經(jīng)濟(jì)計劃和管理決策等領(lǐng)域都可以發(fā)揮作用。它已是現(xiàn)代科學(xué)管理的重要手段之一。例1.1生產(chǎn)計劃問題（資源利用問題）某家具廠生產(chǎn)桌子和椅子兩種家具。

桌子售價50元/個，椅子銷售價格30元/個。需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。

問如何組織生產(chǎn)才能使每月的銷售收入最大？1、問題的提出是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量設(shè)——桌子的產(chǎn)量

——椅子的產(chǎn)量

——利潤第2步--定義目標(biāo)函數(shù)決策變量

MaxZ=50x1+30x2價值系數(shù)第2步--定義目標(biāo)函數(shù)

MaxZ=50x1+30x2第3步--表示約束條件4x1+3x2

120（木工工時限制）

2x1+x2

50（油漆工工時限制）

x1，x2≥0（變量取非負(fù)值限制）

該計劃的數(shù)學(xué)模型

maxZ=50x1+30x24x1+3x2

1202x1+x250

x1,x20s.t.線性函數(shù)線性等式線性不等式線性規(guī)劃+例1.2簡化的環(huán)境保護(hù)問題

靠近某河流有兩個化工廠(見下圖)，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。

第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。這兩個工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬立方米。第二化工廠處理工業(yè)污水的成本是800元/萬立方米?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費用最小。

建模型之前的分析和計算

設(shè)：第一化工廠每天處理工業(yè)污水量為x1萬立方米，第二化工廠每天處理工業(yè)污水量為x2萬立方米數(shù)學(xué)模型線性規(guī)模解決的問題給定一定數(shù)量的人力、物力、財力等資源，研究如何充分利用，以發(fā)揮其最大效果已給定計劃任務(wù)，研究如何統(tǒng)籌安排，用最少的人力、物力、財力去完成線性規(guī)劃數(shù)學(xué)模型三要素：

決策變量、目標(biāo)函數(shù)、約束條件

每一個線性規(guī)劃問題都有一組決策變量

(x1,x2,……,xn),這組決策變量的值就代表一個具體方案。

有使用各種資源的約束條件，用等式或不等式表示。

有一個要達(dá)到的目標(biāo)，是決策變量的線性函數(shù)，實現(xiàn)最大化或最小化。2、線性規(guī)劃問題的數(shù)學(xué)模型

一般形式線性規(guī)劃模型的表示形式

矩陣形式

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

將一般線性規(guī)劃化成標(biāo)準(zhǔn)形

簡寫形式max(min)Z=c1x1+c2x2+…..+cnxna11x1+a12x2+….+a1nxn(=,)b1

a21x1+a22x2+….+a2nxn(=,)b2

….

am1x1+am2x2+….+amnxn(=,)bm

x1,

x2,….,xn0s.t.線性規(guī)劃問題的一般形式

線性規(guī)劃問題的簡寫形式

max

Z=CTX

s.t.AX=b

X

0C—價值向量b—資源向量X—決策變量向量線性規(guī)劃的矩陣形式

a11

a12….a1nb1A=a21

a22….a2n

b

=

b2…….

am1

am2….amnbm

c1

x10

c2

x20C=X=0=……...

cn

xn0線性規(guī)劃問題的標(biāo)準(zhǔn)形式max

Z=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn

=b1

a21x1+a22x2+….+a2nxn=

b2

….

am1x1+am2x2+….+amnxn=

bm

x1,

x2,….,xn0其中：bi

0,i=1,2,….,m.四點要求:將一般線性規(guī)劃化成標(biāo)準(zhǔn)型

求max

等式約束

bi0

xi0(1)若目標(biāo)函數(shù)是求最小值:

min

Z=CTX

令Z’=Z,則化成max

Z’=CTX注意:

因為min

Z=max(Z)

所以變換后的最優(yōu)解不變，最優(yōu)值變號。(2)若約束條件是不等式1)若約束條件是“”不等式，則不等式左邊“加上”非負(fù)的松馳變量；如：2X1+2X2≤12令X3=12-2X1-2X2

則有2X1+2X2+X3=12

2)若約束條件是“”不等式，則不等式左邊“減去”非負(fù)的松馳變量。如：10X1+12X2≥18令X4=10X1+12X2-18則有10X1+12X2-X4=18

為了使添加松馳變量不影響原來的目標(biāo)，添加松馳變量在目標(biāo)函數(shù)中的系數(shù)為0。(3)若約束條件右面的某一常數(shù)項bi<0,

這時只要在bi相對應(yīng)的約束方程兩邊乘1。(4)若變量xj無非負(fù)限制引進(jìn)兩個非負(fù)變量xj’

xj”0

令xj=

xj’

xj”

（可正可負(fù)）任何形式的線性規(guī)劃總可以化成標(biāo)準(zhǔn)型例1.3將下列問題化成標(biāo)準(zhǔn)型:

min

Z=

x1+2x23x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制例1.3將下列問題化成標(biāo)準(zhǔn)型:

min

Z=

x1+2x23x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制minx3

無限制例1.3將下列問題化成標(biāo)準(zhǔn)型:

max

Z’=

x1

2x2+3x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制例將下列問題化成標(biāo)準(zhǔn)型:

max

Z’=

x1

2x2+3x3+0x4

s.t.x1+x2+x3+x4=7

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制，x4

0例將下列問題化成標(biāo)準(zhǔn)型:

maxZ’=

x1

2x2+3x3+0x4+0x5

s.t.x1+x2+x3+x4=7

x1

x2+x3

x5=2

3x1+x2+2x3=5

x10,x20,x3無限制，x4

0，x5

0max

Z’=

x1

2x2+3x3’

3x3’’+0x4+0x5

s.t.x1+x2+x3’

x3’’

+x4=7

x1

x2+x3’

x3’’

x5=2

3x1+x2+2x3’

2x3’’

=5

x10,x20,x3’0,

x3’’0，x4

0，x5

0令x3=

x3’

x3’’例將下列一般形式劃為標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)型習(xí)題P55-2.2（1）劃為標(biāo)準(zhǔn)形式二、LP問題的圖解法max

Z=50x1+30x2s.t.4x1+3x21202x1+x2

50

x1,x2

01.例x240302010102030x1

由4x1+3x2120

x10,x20

圍成的區(qū)域50

由2x1+x250

x10,x20

圍成的區(qū)域x240302010102030x1

由4x1+3x21202x1+x250

x10,x20

圍成的區(qū)域

(可行域)50可行域滿足約束條件的解稱為可行解，全部可行解的集合稱為可行域。x240302010102030x1

該問題的可行域是由

Q1，Q2，Q3，Q4

作為頂點的凸多邊形50可行域Q1(0,0)Q2(25,0)Q4(0,40)Q3(15,20)x240302010102030x1

目標(biāo)函數(shù)

Z=50x1+30x2

是一組平行線50可行域x240302010102030x1

此組平行線沿其法線方向(50,30)右上方函數(shù)值Z

增加50可行域x240302010102030x1當(dāng)該直線移到Q3(15,20)點時，Z值達(dá)到最大：

max

Z=5015+3020=1350此時最優(yōu)解X*=（15，20）50Q3(15,20)二個重要結(jié)論：可行域是一個凸多邊形。最優(yōu)解必定能在某一個頂點上取得。2.LP問題的解

可行解：滿足約束條件（包括非負(fù)條件）的一組變量值，稱可行解。

可行域：可行解的全體。

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大的可行解。

最優(yōu)值：將最優(yōu)解代入目標(biāo)函數(shù)得到的值。

可行域為空集無可行解

可行域非空，則有三種情況：(1)有唯一解(頂點)(2)有無窮多個解(兩個頂點間的連線)(3)無最優(yōu)解(無界解)無最優(yōu)解⑴⑵x1x2

無可行解x240302010102030x1

當(dāng)目標(biāo)函數(shù)由

max

Z=50x1+30x2

變成

max

Z=40x1+30x2

目標(biāo)函數(shù)是同約束條件

4x1+3x2120

平行的直線

Q2與Q3之間都是最優(yōu)解50Q3(15,20)Q2(25,0)⑴⑵無界解x1x2

無界解：若可行域無界，且目標(biāo)函數(shù)值可增加(減少)到正無窮(負(fù)無窮)，稱這種無最優(yōu)解的情況為無界解。注意：

可行域無界，不一定無最優(yōu)解；可行域非空有界，則必定有最優(yōu)解。LP問題解的類型習(xí)題P55-2.1三、單純形法的基本思路和原理（一）單純形法的基本思路

從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)，如不是，則再找另一個使得其目標(biāo)函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解，直到找到一個頂點為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個目標(biāo)函數(shù)（找更大的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代結(jié)束

例

max

Z=2x1+3x2s.t.x1+2x244x1

84x2

6

x1,x2

01.基本概念劃為標(biāo)準(zhǔn)型：

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0約束方程的系數(shù)矩陣A=P1P2P3P4P5單位矩陣A中存在一個不為零的三階子式，A的秩為3A是約束條件的m×n階系數(shù)矩陣，設(shè)r(A)=m,且B是A的m

階非奇異的子矩陣（det(B)0),則稱矩陣B為線性規(guī)劃問題的一個基(陣)。（1）基(陣)B=或(mn)

r(A)=m，至少有一個m階子式不為0。a11

…a1m

a1m+1

…a1na21

…

a2m

a2m+1

…

a2n………am1

…

amm

amm+1

…

amnp1

…

pm

pm+1

…

pnBN基B中的一列即稱為一個基向量，基B中共有m個基向量。（2）基向量與非基向量B=P3P4P5基向量A=(p1

…

pm

pm+1

…

pn)=(B,N)

基向量

非基向量（3）基變量與非基變量設(shè)A=(p1,p2,……,pn)，若B=(pi1,pi2,……,pim)為A的基陣，則稱x1,x2,……,xn中的xi1,xi2,……,xim為對應(yīng)于B的基變量，其余的稱為非基變量。B=P3P4P5x3,x4,x5是基變量x1,x2,是非基變量基向量X=(x1

…

xm

xm+1

…

xn

)T=(XBXN)T

基變量

非基變量A=(p1

…

pm

pm+1

…

pn)=(B,N)

基向量

非基向量（4）基(本)解令非基變量取值為零,則基變量的取值可從AX=b中唯一解得。如此的一組解稱為對應(yīng)于B的一個基（本）解。（5）基可行解若X0是一個基解，而且又是一個可行解，則稱X0是一個基可行解?；尚薪鈱?yīng)于可行域的頂點。退化的基可行解問題:

在基可行解中,非基變量的取值必定為零,基變量的取值是否必定大于零?若X0是一個基可行解,其基變量的取值全部大于零，則稱X0是非退化的;否則稱為退化的。解的關(guān)系可行解基解基可行解最優(yōu)解代數(shù)概念幾何概念滿足一個等式約束的解滿足一個不等式約束的解滿足一組不等式約束的解基解基可行解目標(biāo)函數(shù)值等于一個常數(shù)的解組約束直線約束半平面約束半平面的交集：凸多邊形約束直線的交點可行域頂點目標(biāo)函數(shù)等值線：一組平行線舉例化為標(biāo)準(zhǔn)型可行解、基解和基可行解舉例2.最優(yōu)解的判斷檢驗數(shù)公式或最優(yōu)解檢驗的依據(jù)是計算檢驗數(shù)檢驗數(shù)的判別規(guī)則(max)若所有的，則基B所對應(yīng)的基可行解就是最優(yōu)解。若所有的，而非基變量的檢驗數(shù)滿足條件，則該線性規(guī)劃問題有唯一最優(yōu)解。若所有的

，又有某個非基變量的檢驗數(shù)，則該線性規(guī)劃問題有無窮多最優(yōu)解。若存在某個，又其對應(yīng)的向量的所有分量，則該線性規(guī)劃問題存在無界解。3.單純形表（二）單純形法的內(nèi)容1.初始基可行解的確定（假定基陣B為單位陣）2.最優(yōu)解的判斷3.換基可行解的方法例

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0

cj23000x1x2x3x4x5121004001004001cBxBbx3x4x5000486

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0cj23000cBxBb

x1x2x3x4x5000x3x4x54861210040010040010

230004/26/4－cj23000cBxBbx1x2x3x4x500x3x4840010

9/23x23/2010011010-1/21/420-20-3/41/1–8/4cj23000cBxBbx1x2x3x4x520x1x4400-412

13/23x23/2010011010-1/21/400-201/4–64/2cj23000cBxBbx1x2x3x4x520x1x5200-21/21

73x21011/2-1/821001/40000-3/2-1/40例cj230000cBxBb

x1x2x3x4x5x60000x3x4x5x612816122210001201004000100400010

23000012/28/2－12/4000x3x4x516

400010

3x23010001/42620100-1/2100100-1/2cj230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/49

20000-3/46/2216/4－0203x3x1x5x22283001-201/210010-1/2000-412010001/44－41213000-201/40203x6x1x5x2

4402

002-401101-10000-441001-1/21001400-1/2-100000-201/4134－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj0203x3x1x6x2

0442001-1-1/4010001/40000-21/210101/2-1/8014000-3/2-1/80000-201/4134－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj例

求線性規(guī)劃問題

00-1/12-7/2433/4

x2x112x1x2x3x4bxBcB2100cj15/43/4011/4-1/810-1/125/24單純形法解線性規(guī)劃問題習(xí)題P55-2.21.無法給出初始基可行解四、大M法2.添加人工變量3.修改目標(biāo)函數(shù)例先減去再加上加入松弛變量加入人工變量

加入人工變量后，目的是找到一個單位向量。其目標(biāo)價值系數(shù)要確定，但不能影響目標(biāo)函數(shù)的取值。一般可采用兩種方法處理：大M法和兩階段法。

即假定人工變量在目標(biāo)函數(shù)中的系數(shù)為-M（任意大正數(shù)。如基變量中還存在M，就不能實現(xiàn)極值。大M法：0-M0-5+2M3-4M2+3M-17M51-101-5210x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cj-M+1/7-1/7-M-16/7-50/700102/71/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cj一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；存在著多種方案；要求達(dá)到的目標(biāo)是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述。五、線性規(guī)劃在工商管理中的應(yīng)用1.人力資源分配的問題；2.生產(chǎn)計劃的問題；3.套裁下料問題；4.配料問題；5.投資問題。應(yīng)用舉例1.人力資源分配的問題

例1：某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下：

設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?分析：不同上班班次時段的司機和乘務(wù)人員數(shù)設(shè)xi

表示第i班次時開始上班的司機和乘務(wù)人員數(shù)例2：一家中型的百貨商場，它對售貨員的需求經(jīng)過統(tǒng)計分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？設(shè)xi

(i=1,2,…,7)表示星期一至日開始工作的人數(shù)。2.生產(chǎn)計劃的問題例3：某公司面臨一個是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？解：設(shè)x1，x2，x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4，x5

分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤：利潤=售價-各成本之和產(chǎn)品甲全部自制的利潤=23-(3+2+3)=15

產(chǎn)品甲鑄造外協(xié)，其余自制的利潤=23-(5+2+3)=13

產(chǎn)品乙全部自制的利潤=18-(5+1+2)=10

產(chǎn)品乙鑄造外協(xié)，其余自制的利潤=18-(6+1+2)=9

產(chǎn)品丙的利潤=16-(4+3+2)=7可得到xi

（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。通過以上分析,可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)：Max15x1+10x2+7x3+13x4+9x5

約束條件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0例5：現(xiàn)有一批某種型號的圓鋼長8米，需要截取2.5米長的毛坯100根，長1.3米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少？100200321002462.5米1.3米需要根數(shù)

一二三四下料下料毛件數(shù)方式坯型號設(shè)變量為第j種方法的所有原料件數(shù)3.套裁下料問題

例6：某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最省？解：共可設(shè)計下列5種下料方案，見下表

設(shè)x1,x2,x3,x4,x5分別為上面5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5

約束條件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0用軟件計算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；

x3=0；

x4=50；

x5=0；只需90根原材料就可制造出100套鋼架。注意：在建立此類型數(shù)學(xué)模型時，約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號，這一方案就不是可行解了。例7：根據(jù)對77種食物所含的九種營養(yǎng)物：熱量(糖與脂肪)、蛋白質(zhì)、鈣、鐵、維生素A、維生素B1、維生素B2、草酸與維生素C的成份及食物的市場價格調(diào)查，按照醫(yī)生所提出的對每個人每天所需的營養(yǎng)要求。問怎樣采購食物才能在保證營養(yǎng)要求的前提下花費最省？這就是營養(yǎng)問題或飲食問題，配料問題就是由此而推廣來的。4.配料問題解：設(shè)每天購買甲，乙，丙，丁四種食物的數(shù)量分別為x1，x2，x3，x4，即可列出如下的線性規(guī)劃模型：

例8：某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的