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

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

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

——椅子的產量

——利潤第2步--定義目標函數決策變量

MaxZ=50x1+30x2價值系數第2步--定義目標函數

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

120（木工工時限制）

2x1+x2

50（油漆工工時限制）

x1，x2≥0（變量取非負值限制）

該計劃的數學模型

maxZ=50x1+30x24x1+3x2

1202x1+x250

x1,x20s.t.線性函數線性等式線性不等式線性規劃+例1.2簡化的環境保護問題

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

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

建模型之前的分析和計算

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

決策變量、目標函數、約束條件

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

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

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

有一個要達到的目標，是決策變量的線性函數，實現最大化或最小化。2、線性規劃問題的數學模型

一般形式線性規劃模型的表示形式

矩陣形式

標準形式

將一般線性規劃化成標準形

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

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

….

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

x1,

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

線性規劃問題的簡寫形式

max

Z=CTX

s.t.AX=b

X

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

a11

a12….a1nb1A=a21

a22….a2n

b

=

b2…….

am1

am2….amnbm

c1

x10

c2

x20C=X=0=……...

cn

xn0線性規劃問題的標準形式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.四點要求:將一般線性規劃化成標準型

求max

等式約束

bi0

xi0(1)若目標函數是求最小值:

min

Z=CTX

令Z’=Z,則化成max

Z’=CTX注意:

因為min

Z=max(Z)

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

則有2X1+2X2+X3=12

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

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

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

xj”0

令xj=

xj’

xj”

（可正可負）任何形式的線性規劃總可以化成標準型例1.3將下列問題化成標準型:

min

Z=

x1+2x23x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制例1.3將下列問題化成標準型:

min

Z=

x1+2x23x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制minx3

無限制例1.3將下列問題化成標準型:

max

Z’=

x1

2x2+3x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制例將下列問題化成標準型:

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例將下列問題化成標準型:

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’’例將下列一般形式劃為標準形式：標準型習題P55-2.2（1）劃為標準形式二、LP問題的圖解法max

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

50

x1,x2

01.例x240302010102030x1

由4x1+3x2120

x10,x20

圍成的區域50

由2x1+x250

x10,x20

圍成的區域x240302010102030x1

由4x1+3x21202x1+x250

x10,x20

圍成的區域

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

該問題的可行域是由

Q1，Q2，Q3，Q4

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

目標函數

Z=50x1+30x2

是一組平行線50可行域x240302010102030x1

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

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

max

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

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

可行域：可行解的全體。

最優解：使目標函數達到最大的可行解。

最優值：將最優解代入目標函數得到的值。

可行域為空集無可行解

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

無可行解x240302010102030x1

當目標函數由

max

Z=50x1+30x2

變成

max

Z=40x1+30x2

目標函數是同約束條件

4x1+3x2120

平行的直線

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

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

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

從可行域中某一個頂點開始，判斷此頂點是否是最優，如不是，則再找另一個使得其目標函數值更優的頂點，稱之為迭代，再判斷此點是否是最優解，直到找到一個頂點為其最優解，就是使得其目標函數值最優的解，或者能判斷出線性規劃問題無最優解為止。找出一個初始可行解是否最優轉移到另一個目標函數（找更大的基本可行解）最優解是否循環直到找出為止，核心是：變量迭代結束

例

max

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

84x2

6

x1,x2

01.基本概念劃為標準型：

max

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

x1,x2,x3,x4,x5

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

階非奇異的子矩陣（det(B)0),則稱矩陣B為線性規劃問題的一個基(陣)。（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）基變量與非基變量設A=(p1,p2,……,pn)，若B=(pi1,pi2,……,pim)為A的基陣，則稱x1,x2,……,xn中的xi1,xi2,……,xim為對應于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中唯一解得。如此的一組解稱為對應于B的一個基（本）解。（5）基可行解若X0是一個基解，而且又是一個可行解，則稱X0是一個基可行解。基可行解對應于可行域的頂點。退化的基可行解問題:

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

，又有某個非基變量的檢驗數，則該線性規劃問題有無窮多最優解。若存在某個，又其對應的向量的所有分量，則該線性規劃問題存在無界解。3.單純形表（二）單純形法的內容1.初始基可行解的確定（假定基陣B為單位陣）2.最優解的判斷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例

求線性規劃問題

00-1/12-7/2433/4

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

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

即假定人工變量在目標函數中的系數為-M（任意大正數。如基變量中還存在M，就不能實現極值。大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一般而言，一個經濟、管理問題凡是滿足以下條件時，才能建立線性規劃模型。要求解問題的目標函數能用數值指標來反映，且為線性函數；存在著多種方案；要求達到的目標是在一定條件下實現的，這些約束可用線性等式或不等式描述。五、線性規劃在工商管理中的應用1.人力資源分配的問題；2.生產計劃的問題；3.套裁下料問題；4.配料問題；5.投資問題。應用舉例1.人力資源分配的問題

例1：某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下：

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

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

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

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

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

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

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

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

（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。通過以上分析,可建立如下的數學模型:目標函數：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：現有一批某種型號的圓鋼長8米，需要截取2.5米長的毛坯100根，長1.3米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少？100200321002462.5米1.3米需要根數

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

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

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

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

x3=0；

x4=50；

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

例8：某工廠要用三種原料1、2、3混合調配出三種不同規格的