管理運籌學課件第一章管理運籌學-線性規(guī)劃

管理運籌學課件第一章—管理運籌學線性規(guī)劃

管理運籌學

OperationalResearch

天津大學管理學院

郭均鵬

管理運籌學

教師簡介：

郭均鵬：博士，副教授，

碩士生導師。

主要研究領域：運籌決策技術；

信息管理與8＞企業(yè)信息3〉化；

績效考核與薪酬體系設計

聯(lián)系方式：天津大學管理學院，300072

guojp@tju.edu

管理運籌學

授課內容：

線性規(guī)劃

圖論與網絡分析

網絡計劃

風險型決策

排隊論

博弈論

課程教材：

吳育華，杜綱.《管理科學基礎》，天津大學出版社。

管理運籌學

緒論

產生于二戰(zhàn)時期，運籌學(OperationalResearch)直譯為“運作研究”。

60年代，在工業(yè)、農業(yè)、社會等各領域得到廣泛應用

在我國，50年代中期由錢學森等引入

運用數學方法，為決策者進行最優(yōu)決策提供科學依據的一門應用科學。

一、運籌學的產生與發(fā)展

二、學科性質

管理運籌學

三、運籌學的分支

線性規(guī)劃

非線性規(guī)劃

圖論與網絡分析

存儲論

決策論

排隊論

對策論(博弈論)

管理運籌學

四、管理運籌學的工作程序

明確問題

問題分類

建立數學模型

求解數學模型

結果分析

實施

注意計算機軟件的應用一一

Lindo、WinQSB等

管理運籌學

第一章線性規(guī)劃

(LinearProgramming,簡稱LP)

§1線性規(guī)劃的模型與圖解法

一、LP問題及其數學模型

例1某工廠可生產甲、乙兩種產品，需消耗煤、電、油三種資源，有關單

耗數據如表，試擬定使總收入最大的生產計劃。

12

7

單價

300

10

3

油

200

5

4

電

360

4

9

煤

資源限制

乙

甲

產品

資源

管理運籌學

12

7

單價

300

10

3

油

200

5

4

電

360

4

9

煤

資源限制

乙

甲

產品

資源

線性規(guī)劃模型三要素：

（1）決策變量

設甲產品生產xl,乙產品生產x2

(2)目標函數

MaxZ=7xl+12x2

(3)約束條件

9xl+4x2W360

4x1+5x2<200

3xl+10x2<300

xl,x220

s.t.

返回

SubjectTo,意為“使其滿足”

管理運籌學

Max(Min)Z=clxl+c2x2+…+cnxn

allxl+al2x2+…+alnxnW(=,2)bl

amixl+am2x2+…+amnxnW=,2)bm

xl,x2,,,,,xn20

LP模型的一般形式

矩陣表示

MaxZ=CX

AXWb

X20

s.t.

其中：

X=(xl,x2,…，xn)T為決策變量C=(cl,c2,…，cn)稱為價格

系數

A=(aij)mXn稱為技術系數

b=(bl,b2,…，bm)T稱為資源系數

管理運籌學

課堂練習

某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四

種養(yǎng)分。有關數據如下表，現飼料可從市場上出售的M、N兩種飼料中選擇，試

決定總花費最小的購買方案。(列出模型)

7

8

5

10

每頭日需

200

0.2

0.4

0.3

0.1

N

300

0

0.3

0.2

0.5

M

價格

D

C

B

A

養(yǎng)分

飼料

管理運籌學

課堂練習

某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四

種養(yǎng)分。有關數據如下表，現飼料可從市場上出售的M、N兩種飼料中選擇，試

決定總花費最小的購買方案。（列出模型）

7

8

5

10

每頭日需

200

0.2

0.4

0.3

0.1

N

300

0

0.3

0.2

0.5

M

價格

D

C

B

A

養(yǎng)分

飼料

答案：設購買M飼料xl,N飼料x2

0.5xl+0.1x2210

0.2x1+0.3x225

0.3x1+0.4x2Q8

0.2x227

xl,x220

s.t.

MinZ=300xl+200x2

管理運籌學

二、線性規(guī)劃的圖解法

1.步驟

（1）作約束的圖形一一可行域

可行解的集合

①先作非負約束

②再作資源約束

9x1+4x2=360

4x1+5x2=200

3x1+10x2=300

公共部分，即為可行域

例：煤電油例

MaxZ=7xl+12x2

9xl+4x2W360

4x1+5x2<200

3xl+10x2<300

xl,x220

s.t.

xl

x2

40

20

60

80

100

20

40

60

80

100

0

管理運籌學

（2）作目標函數的等值線

①給z不同的值，作相應直線，判斷出z增大時，直線的移動方向

②將直線向增大方向移動，直至可行域邊界，交點X*即為最優(yōu)解。

7x1+12x2=84

7x1+12x2=168

如：令7xl+12x2=84

7xl+12x2=168

9x1+4x2=360

4x1+5x2=200

3x1+10x2=300

20

60

80

100

20

40

60

80

100

0

X*=(20,24),

Z*=428

管理運籌學

最優(yōu)解：xl=0,x21

最優(yōu)目標值z=3

課堂練習

圖解法求解線性規(guī)劃

0

1

2

3

4

1

2

3

4

x

1

X

2

0

-1

-2

(1)

(2)

(3)

管理運籌學

2.LP解的幾種情況

（1）唯一解

（2）多重最優(yōu)解

（3）無可行解

注：出現（3）、（4）情況時，建模有問題

（4）無有限最優(yōu)解

管理運籌學

圖解法的結論：

線性規(guī)劃的可行域是凸集

線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點獲得

若在兩個極點同時獲得，則有無窮多最優(yōu)解

凸集

不是凸集

極點

管理運籌學

三、線性規(guī)劃應用舉例與軟件求解

例1（下料問題）某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5

m的圓鋼各一根。已知原料每根長7.4m,問：應如何下料，可使所用原料最?。?/p>

管理運籌學

例1（下料問題）某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5

口的圓鋼各一根。已知原料每根長7.4m,問：應如何下料，可使所用原料最??？

余料

1.5

2.1

2.9

方案

7.4m

2.9m

2.Im

1.5m

2

0

1

0.1

I

1

2

0

0.3

II

1

1

1

0.9

III

1

0

3

0

IV

0

3

0

1.1

V

0

2

2

0.2

VI

0

1

3

0.8

vn

0

0

4

1.4

vm

管理運籌學

50

io

30

2x1+x2+x3+x4=100

2x2+x3+3x5+2x6+x7=100

xl+x3+3x4+2x6+3x7+4x8=100

xl,x2,x3,x4,x5,x6,x7,x820

設xl,x2,x3,x4,x5,x6,x7,x8分別為上述8種方案下料的原材料根數，

建立如下的LP模型：

最優(yōu)解為：xl=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0

minZ=xl+x2+x3+x4+x5+x6+x7+x8

s.t.

余料

1.5

2.1

2.9

方案

2

0

1

0.1

I

1

2

0

0.3

II

1

1

1

0.9

III

1

0

3

0

IV

0

3

0

1.1

V

0

2

2

0.2

VI

0

1

3

0.8

vn

0

0

4

1.4

VDI

管理運籌學

一、線性規(guī)劃的標準型

MaxZ=clxl+c2x2+,,,+cnxn

allxl+al2x2+…+alnxn=bl

amixl+am2x2++amnxn=bm

xl,x2,,xn20

s.t.

1、標準形式

MaxZ=CX

AX=b

X20

s.t.

注：標準型中要求bi20

§2單純形法

矩陣表示

管理運籌學

2、非標準型

標準型

(1)MinZ=CX

MaxZ'=-CX

(2)約束條件

例如：9xl+4x2W360

9xl+4x2+x3=360

松弛變量

“W”型約束，加松弛變量；

“2”型約束，減松弛變量；

(3)自由變量xj

進行變量替換：xj=xj'-xj'',其中xj'、

xj''20

管理運籌學

二、LP解的基本概念

考慮標準型：

MaxZ=CX

AX=b

X20

s.t.

(1)

(2)

1.可行解

滿足(1)、(2)的解

2.基本解

設r(A)=m,

則BX=b有唯一解，

稱

為基本解，簡稱基解。

且不妨設

非奇異，

O

設為

結論：基本解的個數W

管理運籌學

3.基可行解

若基解X20,則稱為基可行解。

可行解

基解

基可行解

結論：LP的基可行解對應于可行域的頂點。

基：A中m階可逆子陣，記為B。

基向量：B中的列。

基變量：和基向量相對應的決策變量。

其余部分稱為非基子陣，記為N。

管理運籌學

例、研究約束集合

基本解的個數W

令x2=x3=0,得基本解

Xl=(l/2,0,0)T,

對應于A點；

1/2

1

1/3

A

B

C

x2

x3

xl

令xl=x3=0,得基本解

X2=(0,1,0)T,

對應于B點；

令xl=x2=0,得基本解

X3=(0,0,1/3)T,

對應于C點；

管理運籌學

基可行解

例、研究約束集合

基本解的個數W

令xl=0,得基本解

Xl=(0,3,2,-1)T,

對應于A點；

令x2=0,得基本解

X2=(3,0,1,-8)T,

對應于B點；

令x3=0,得基本解

X3=(2,1,0,5)T,

對應于F點；

畫出可行域

1

2

3

4

1

2

3

4

A

B

C

D

E

F

0

xl

x2

標準化

令x4=0,得基本解

X4=(l/3,8/3,5/3,0)T,

對應于D點；

管理運籌學

三、單純形法的基本方法

基本方法：

確定初始基可行解

檢驗是否最優(yōu)？

轉到另一更好的

基可行解

停

Y

N

方法前提：模型化為標準型

管理運籌學

1.初始可行基B0的確定

若A中含有I：BO=I

若A中不含I：人工變量法

管理運籌學

2.最優(yōu)性檢驗

矩陣分塊

把目標函數用非基變量表示：

檢驗數向量，記為。。當。W0時，當前解為最優(yōu)解。

方法：

(1)計算每個xj的檢驗數

(2)若所有。jWO,則當前解為最優(yōu)；

否則，至少有ok>O,轉3。

管理運籌學

3.換基迭代(基變換)

(1)進基：取

對應的Pk進基。

(2)出基：取

對應的P1進基。

得新基，轉2。

管理運籌學

。的計算：

0

0

x5

x4

x3

x2

xl

B-lb

CB

XB

四、單純形法的實現一一單純形表

例：煤電油例

MaxZ=7xl+12x2

9xl+4x2W360

4x1+5x2W200

3xl+10x2W300

xl,x220

s.t.

MaxZ=7xl+12x2

9xl+4x2+x3=360

4x1+5x2+x4=200

3xl+10x2+x5=300

xl，…，x5N0

s.t.

化為標準型

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表：

7

管理運籌學

o

0

x5

x4

x3

x2

xl

B-lb

CB

XB

四、單純形法的實現一一單純形表

例：煤電油例

MaxZ=7xl+12x2

9xl+4x2^360

4x1+5x24200

3xl+10x2W300

xl,x220

s.t.

MaxZ=7xl+12x2

9xl+4x2+x3=360

4x1+5x2+x4=200

3xl+10x2+x5=300

xl，…，x520

s.t.

化為標準型

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表：

7

90

9的計算：

40

30

管理運籌學

o

9

x5

x4

x3

x2

xl

B-lb

CB

XB

四、單純形法的實現一一單純形表

例：煤電油例

MaxZ=7xl+12x2

9xl+4x2W360

4x1+5x2W200

3xl+10x2<300

xl,x220

s.t.

MaxZ=7xl+12x2

9xl+4x2+x3=360

4x1+5x2+x4=200

3xl+10x2+x5=300

xl,x5N0

s.t.

化為標準型

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表:

7

90

40

30

[]

樞紐元素

管理運籌學

o

0

x5

x4

x3

x2

xl

B-lb

CB

XB

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表：

7

90

40

30

[]

x3

x4

x2

0

0

12

30

0.3

1

0

0

0.1

o

以10為主元進行初等行變換

50

2.5

0

0

1

-0.5

240

7.8

0

1

0

-0.4

3.4

0

0

0

—1.2

即：

管理運籌學

O

0

x5

x4

x3

x2

xl

B-lb

CB

XB

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表:

7

90

40

30

[]

x3

x4

x2

0

0

12

30

0.3

1

0

0

0.1

以10為主元進行初等行變換

50

2.5

0

0

1

-0.5

240

7.8

0

1

0

-0.4

3.4

0

0

0

-1.2

即：

30.8

20

100

管理運籌學

o

0

x5

x4

x3

x2

xl

B-lb

CB

XB

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表:

7

90

40

30

[]

x3

x4

x2

0

0

12

30

0.3

1

0

0

0.1

o

以10為主元進行初等行變換

50

2.5

0

0

1

-0.5

240

7.8

0

1

0

-0.4

3.4

0

0

0

-1.2

30.8

20

100

[]

管理運籌學

x3

xl

x2

0

7

12

24

0

1

0

-0.12

0.16

o

20

1

0

0

0.4

-0.2

84

0

0

1

-3.12

1.16

0

0

0

-1.36

-0.52

o

o

0

x5

x4

x3

x2

xl

B-lb

CB

XB

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表:

7

90

40

30

[]

x3

x4

x2

0

0

12

30

0.3

1

0

0

0.1

50

2.5

0

0

1

-0.5

240

7.8

0

1

0

-0.4

3.4

0

0

0

-1.2

30.8

20

100

[]

以為主元進行初等行變換

2.5

管理運籌學

x3

xl

x2

0

7

12

24

0

1

0

-0.12

0.16

o

20

1

0

0

0.4

-0.2

84

0

0

1

-3.12

1.16

0

0

0

-1.36

-0.52

o

o

0

x5

x4

x3

x2

xl

B-lb

CB

XB

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表:

7

90

40

30

[]

x3

x4

x2

0

0

12

30

0.3

1

0

0

0.1

50

2.5

0

0

1

-0.5

240

7.8

0

1

0

-0.4

3.4

0

0

0

-1.2

30.8

20

100

[]

，X*=(20,24,84,0,0)T

Z*=428

管理運籌學

例：

用單純形法求解

MinS=-xl+2x2

xl-x2>-2

xl+2x2W6

xl,x220

s.t.

化為標準型

MaxS?=xl-2x2

-xl+x2+x3=2

xl+2x2+x4=6

xl,…，x420

s.t.

-2

1

o

6

1

0

2

[1]

6

0

x4

不考慮

0

1

1

-1

2

0

x3

0

x4

x3

x2

xl

B-lb

CB

XB

-1

0

-4

0

o

1

0

2

1

6

1

xl

1

1

3

0

8

0

x3

，X*=(6,0,8,0)T

Z*=-6

管理運籌學

x3

xl

x2

0

7

12

24

0

1

0

-0.12

0.16

o

20

1

0

0

0.4

-0.2

84

0

0

1

-3.12

1.16

0

0

0

-1.36

-0.52

o

o

0

x5

x4

x3

x2

xl

B-lb

CB

XB

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表:

7

90

40

30

x3

x4

x2

0

0

12

30

0.3

1

0

0

0.1

50

2.5

0

0

1

-0.5

240

7.8

0

1

0

-0.4

3.4

0

0

0

-1.2

30.8

20

100

注：單純形表中的信息

⑴每一列的含義：

B-l(bA)=(B-lb,B-lPl,B-lPn)

⑵每個表中的B和B-l的查找：

B從初表中找；

B-l從當前表中找，對應于初表中的I的位置。

以第2個表為例：

管理運籌學

⑶終表分析——最優(yōu)基B*和(B*)-l的查找

x3

xl

x2

0

7

12

24

0

1

0

-0.12

0.16

o

20

1

0

0

0.4

-0.2

84

0

0

1

-3.12

1.16

0

0

0

-1.36

-0.52

o

o

0

x5

x4

x3

x2

xl

B-lb

CB

XB

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

單純形表:

7

90

40

30

x3

x4

x2

0

0

12

30

0.3

1

0

0

0.1

50

2.5

0

0

1

-0.5

240

7.8

0

1

0

-0.4

3.4

0

0

0

-1.2

30.8

20

100

注：單純形表中的信息

管理運籌學

1＞五、人工變量法（大M法）

1問題：

例：用單純形法求解

MaxZ=5xl+3x2+2x3+4x4

5x1+x2+x3+8x4=10

2x1+4x2+3x3+2x4=10

xl,x2,x3,x420

s.t.

MaxZ=CX

AX=b

X20

s.t.

設問題：

，A中不含I

（I）

管理運籌學

增加人工變量X人=（xn+1,....,xn+m）T,

X人在目標函數中的系數為-M（M為充分大正數）。

于是原問題化為：

2方法：

單純形法求解（H）,若

最優(yōu)基變量中不含X人，則所得解的前n個分量即為X*

否則，（I）無解。

3結論：

MaxZ=CX-MX人

AX+IX人力

X,X人20

s.t.

（ID

管理運籌學

例：用單純形法求解

MaxZ=5xl+3x2+2x3+4x4

5x1+x2+x3+8x4=10

2x1+4x2+3x3+2x4=10

xl,x2,x3,x420

s.t.

解：增加人工變量x5、x6,則模型化為:

MaxZ=5x1+3x2+2x3+4x4-Mx5-Mx6

5x1+x2+x3+8x4+x5=10

2xl+4x2+3x3+2x4+x6=10

xl,…，x620

s.t.

管理運籌學

MaxZ=5xl+3x2+2x3+4x4-Mx5-Mx6

5x1+x2+x3+8x4+x5=10

2xl+4x2+3x3+2x4+x6=10

xl,,,,,x620

s.t.

0

1

x5

o

1

2

3

4

2

0

8

1

1

5

0

x6

x4

x3

x2

xl

B-lb

CB

XB

x5

x6

-M

-M

10

10

5+7M

3+5M

2+4M

4+10M

0

0

5/4

5

管理運籌學

0

1

x5

o

1

2

3

4

2

0

[8]

1

1

5

0

x6

x4

x3

x2

xl

B-lb

CB

XB

x5

x6

-M

-M

10

10

5+7M

3+5M

2+4M

4+10M

0

0

5/4

5

o

x4

x6

4

-M

5/4

5/8

1/8

1/8

1

0

15/2

3/4

15/4

11/4

0

1

5/2+3/4M

0

0

5/2+15/4M

3/2+11/4M

10

2

管理運籌學

0

1

x5

o

1

2

3

4

2

0

⑻

1

1

5

0

x6

x4

x3

x2

xl

B-lb

CB

XB

x5

x6

-M

-M

10

10

5+7M

3+5M

2+4M

4+10M

0

0

5/4

5

o

x4

x6

4

-M

5/4

5/8

1/8

1/8

1

0

15/2

3/4

[15/4]

11/4

0

1

5/2+3/4M

0

0

5/2+15/4M

3/2+11/4M

10

2

o

x4

x2

4

3

1

3/5

0

1/30

1

2

1/5

1

11/15

0

2

0

0

-1/3

5/3

10

管理運籌學

0

1

x5

o

1

2

3

4

2

0

[8]

I

1

5

0

x6

x4

x3

x2

xl

B-lb

CB

XB

x5

x6

-M

-M

10

10

5+7M

3+5M

2+4M

4+10M

0

0

5/4

5

x4

x6

4

-M

5/4

5/8

1/8

1/8

1

0

15/2

3/4

[15/4]

11/4

0

1

5/2+3/4M

0

0

5/2+15/4M

3/2+11/4M

10

2

o

x4

x2

4

3

1

[3/5]

0

1/30

1

2

1/5

1

11/15

0

2

0

0

-1/3

5/3

10

o

xl

x2

5

3

5/3

1

0

1/18

5/3

5/3

0

1

13/18

-1/3

0

-10/3

0

-4/9

，X*=(5/3,5/3,0,0)T,Z*=40/3

管理運籌學

六、單純形法總結

1、Min型單純形表與Max型的區(qū)別僅在于:

令ok=min{ojW0}的xk進基，當。20時最優(yōu)。

2、解的幾種情況及其在單純形表上的體現(討論Max型)

唯一

最優(yōu)解

◎j<0,

非基。<0

多重

最優(yōu)解

ojW0

有非基。k=0

無界解

有ok>0

但BTPkW0

無可行解

用大M法求解，最優(yōu)基中含有X人

退化解

最優(yōu)解中某基變量為0

管理運籌學

§3線性規(guī)劃的對偶問題

(DualProgramming,簡稱DP)

一、對偶問題的提出和模型

1、問題的提出

煤電油例

今有另廠要購買三種資源，在原廠可接受的條件下，單價多少可是另廠付

費最低？

MaxZ=7xl+12x2

9xl+4x2W360

4x1+5x2W200

3xl+10x2W300

xl,x220

s.t.

設煤電油價格分別為yl,y2,y3

MinW=360yl+200y2+300y3

s.t.

9yl+4y2+3y327

4yl+5y2+10y3212

yl,y2,y320

DUAL

管理運籌學

2、模型

MaxZ=CX

AXWb

X20

s.t.

原問題(P):

對偶問題(D)：

MinW=bTY

ATY2CT

Y20

s.t.

特點：

(1)P為max型，D為min型

(2)P的變量個數=D的約束個數

(3)P的約束個數=D的變量個數

MaxZ=7xl+12x2

9xl+4x2W360

4x1+5x2W200

3xl+10x2<300

xl,x220

s.t.

MinW=360yl+200y2+300y3

s.t.

9yl+4y2+3y327

4yl+5y2+10y3>12

yl,y2,y320

管理運籌學

1、對稱性

(P)與(D)互為對偶

二、對偶性質與定理

2、弱對偶性

設X、Y分別為(P)、(D)的任一可行解，則

管理運籌學

3、解的最優(yōu)性

設分別為（P）與（D）的可行解，且

則

4、無界性

若（P）為無界解,則（D）無可行解

若（D）為無界解,則（P）無可行解

管理運籌學

5、對偶定理

若（P）有最優(yōu)解,則（D）也有最優(yōu)解,且二者最優(yōu)值相等.

管理運籌學

小結:

（1）對偶最優(yōu)解Y*=CBB-1,其中B為原問題的最優(yōu)基;

（2）如何從（P）的終表中確定Y*?

Y*即為（P）終表的XS的檢驗數的負值；

若無XS,則用Y*=CB*（B*）T計算。

-CBB-l

C-CBB-1A

B-l

B-1A

CBB-lb

0

XS

C

X

6、檢驗數

管理運籌學

x3

xl

x2

0

7

12

24

0

1

0

-0.12

0.16

o

20

1

0

0

0.4

_0.2

84

0

0

1

-3.12

1.16

0

0

0

-1.36

-0.52

o

0

x5

x4

x3

x2

xl

B-lb

CB

XB

x3

x4

x5

0

0

0

360

200

300

9

4

3

4

5

10

1

0

0

0

1

0

0

0

1

12

0

0

0

例:煤電油的單純形表:

7

90

40

30

（初表）

（終表）

由終表:Y*=（0,1.36,0.52）T

管理運籌學

三、對偶問題最優(yōu)解的經濟解釋一一影子價格

設DP其最優(yōu)值為Z*(注：與LP最優(yōu)值同)，則根據

Z*=bTy*=blyl*+b2y2*+????+bmym*

??Z/??bi=yi*

簡單推導：

Y*=(yl*,y2*,...,ym*)為DP的最優(yōu)解，則yi*表示LP某資

源bi變化1個單位對目標產生的影響，稱yi*為bi的影子價格。

例、煤電油例的對偶問題的最優(yōu)解為Y*=(01.360.52),

則煤電油三種資源的影子價格分別為0、1.36,0.52

管理運籌學

影子價格在管理決策中的作用：

(1)影子價格W市場價格

若

影子價格＞市場價格，則應

影子價格〈市場價格，則應

買進該資源

賣出該資源

(2)影子價格反映了資源的稀缺性，

影子價格越高，則越稀缺

例如：煤的影子價格為0,則表明有剩余

管理運籌學

§4靈敏度分析

任務：當LP的系數A、b、c變化時，是否影響最優(yōu)解或最優(yōu)基？

或：若不影響最優(yōu)解或最優(yōu)基，A、b、c的變化范圍？

對解的影響

可行性:B-lb^0

最優(yōu)性：

管理運籌學

一、b變

(只影響解的可行性)

問題：br在何范圍變化時，不影響最優(yōu)基？

設第r種資源br-br+A(b-*

)

方法：

(保證可行性)

即

,解出△即可

例：煤電油例，討論b2的變化

解得-50WAW27或150Wb2W227

管理運籌學

二、C變

（只影響解的最優(yōu)性）

問題：cj在何范圍變化時，不影響最優(yōu)基（解）？

設第j種資源cjfcj+4（cf

）

方法：

（討論檢驗數）

（1）cj為非基價格系數

，解出

管理運籌學

（2）cj為基價格系數

此時需考慮所有非基變量的檢驗數：

解出

例：煤電油例，為使最優(yōu)解不變，求cl的變化范圍。

解：考慮所有非基檢驗數

同理，

令

基變量的檢驗數仍全為0,故無需考慮。

管理運籌學

三、A變

（1）增加新變量xn+1

8

10

單價

4

8

油

3

6

電

12

3

煤

T

丙

例如，煤電油例又增加產品丙或丁，相關數據如右表。

問題：增加后是否影響最優(yōu)基（解），從而判斷是否有利？（使目標改善）

方法：是否有利取決于是否進基。

故只需計算

,則有利

,則不利

例：

丙不應投產。

同理可得

丁應投產。

管理運籌學

（2）某列Pj-Pj?（只考慮非基向量情形）

問題：改變后是否影響最優(yōu)基（解）、有利？

方法：

只需計算

，則有利

,則不利

管理運籌學

§5整數規(guī)劃

IntegerProgramming（簡稱IP）

一、整數規(guī)劃的一般模型

LP:maxz=CX

AX=b

X'O

IP:maxz=CX

AX=b

X20

X為整數

管理運籌學

整數規(guī)劃的解法：分枝定界法或割平面法

基本思想是把一個整數規(guī)劃問題化為一系列的線性規(guī)劃問題來求解

整數規(guī)劃的分類：

純整數規(guī)劃：所有變量都限制為整數

混合整數規(guī)劃：僅部分變量限制為整數

0-1整數規(guī)劃：變量的取值僅限于0或1

管理運籌學

［例］人力資源分配的問題

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

設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該

公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務

人員？

30

2：00——6：00

6

20

22：00——2：00

5

50

18：00——22：00

4

60

14：00------18：00

3

70

10：00——14：00

2

60

6：00——10：00

1

所需人數

時間

班次

管理運籌學

解：設xi表示第i班次時開始上班的司機和乘務人員數,于是LP模型為:

xl+x6N60

xl+x2270

x2+x3260

x3+x4250

x4+x5220

x5+x6230

xl,x2,x3,x4,x5,x620且為整數

minz=xl+x2+x3+x4+x5+x6

最優(yōu)解：X*=(60,10,50,0,30,0),Z*=150

管理運籌學

二、0-1整數規(guī)劃

投資場所的選址問題

指派問題

背包問題

消防隊問題

管理運籌學

1.投資場所的選址問題

某城市擬在東、西、南三區(qū)設立商業(yè)網點，備選位置有ArA7共7個,

如果選Ai,估計投資為bi元，利潤為ci元，要求總投資不超過B元，規(guī)定

東區(qū)：AkA2、A3中至多選2個

西區(qū)：A4、A5中至少選一個

南區(qū)：A6、A7中至少選一個

問如何設點使總利潤最大？

1,Ai被選中

0,Ai沒被選中

解:令

xi=

maxz=

xi=0或1,i=l,…,7

EbixiWB

i=l

7

xl+x2+x3W2

x4+x521

x6+x721

s.t.

管理運籌學

課堂練習1:

某鉆井隊要從srsio共10個井位中確定五個鉆井探油，如果選Si,

估計鉆探費用為Ci元，并且井位選擇上要滿足下列條件：

(1)或選擇S1和S7,或選擇S8;

(2)選擇了S3或S4就不能選擇S5,反過來也一樣；

(3)在S5,S6,S7,S8中最多只能選兩個。

問如何選擇井位使總費用最??？

管理運籌學

課堂練習1：某鉆井隊要從SrSlO共10個井位中確定五個鉆井探油，

如果選Si,估計鉆探費用為ci元，并且井位選擇上要滿足下列條件：

(1)或選擇S1和S7,或選擇S8

(2)選擇了S3或S4就不能選擇S5,反過來也一樣

(3)在S5,S6,S7,S8中最多只能選兩個

問如何選擇井位使總費用最小？

1,Si被選中

0,Si沒被選中

解：令

xi=

minz=

s.t.

或1,i=l,???,10

管理運籌學

某籃球隊有8名隊員，其身高和專長如下表，現要選拔5名球員上

場參賽，要求：

(1)中鋒只有1人上場

(2)后衛(wèi)至少有一人上場

（3）只有2號上場，6號才上場

要求平均身高最高，應如何選拔隊員？

課堂練習2:

管理運籌學

1,隊員i被選中

0,隊員i沒被選中

解:令

xi=

maxz=

或1,i=l,…，8

s.t.

某籃球隊有8名隊員，其身高和專長如下表，現要選拔5名球員上

場參賽，要求：

（1）中鋒只有1人上場

（2）后衛(wèi)至少有一人上場

（3）只有2號上場，6號才上場

要求平均身高最高，應如何選拔隊員？

管理運籌學

2.指派問題

例：有一份中文說明書，需譯成英、日、德、俄四種文字，分別記

作任務E、J、G、R,現有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同

語種說明書所需的時間如下表所示，問應指派何人去完成何項任務，使所需總時

間最少？

問題描述：n項任務可由n個人完成，由于專長不同，各人完成各任務的時

間也不同，求最優(yōu)安排。

要求：每人只能完成一項任務，每項任務只能由一人完成。

管理運籌學

xll+X12+xl3+xl4=1（甲只能干一項工作）

x21+x22+x23+x24=1（乙只能干一項工作）

x31+x32+x33+x34=1（丙只能干一項工作）

x41+x42+x43+x44=1（丁只能干一項工作）

xl1+x21+x31+x41=1（E任務只能一人干）

xl2+x22+x32+x42=1（J任務只能一人干）

xl3+x23+x33+x43=1（G任務只能一人干）

xl4+x24+x34+x44=1（R任務只能一人干）

xij=0或1,i,j=1,2,3,4

minz=2xl1+15x12+13x13+4x14+10x21+4x22+14x23+15x24

+9x31+14x32+16x33+13x34+7x41+8x42+11x43+9x44

1,指派第i人去完成第j項任務

0,不指派第i人去完成第j項任務

解:令

xij=

管理運籌學

課堂練習：P57例2.23

例：甲、乙、丙、丁是四名游泳運動員，他們各種姿勢的100m游泳成績如

表。為組成一個4X100m混合泳接力隊，怎樣選派運動員，方使接力隊的游泳成

績最好？

57.0

60.8

69.4

74.0

T

59.1

77.8

84.3

67.6

丙

52.8

57.0

66.2

65.8

乙

58.4

66.6

86.8

75.5

甲

自由泳

蝶泳

蛙泳

仰泳

運動員

管理運籌學

3.背包問題

問題描述

已知：一個背包最大容量為b公斤；有m件物品供選擇，每件物品重ai公

斤,價值為ci(i=l,???,m)o

問題：攜帶哪些物品可使總價值最大？

一般模型

s.t.

1,物品i被選中

0,物品i沒被選中

xi=

管理運籌學

例：一個徒步旅行者要在背包中選擇一些最有價值的物品攜帶。他最多能帶

115kg的物品，現有5件物品，分別重54、35、57、46、19kg,其價值依次為7、

5、9、6、3o問攜帶哪些物品可使總價值最大？

解：

模型為：

s.t.

管理運籌學

4.消防隊問題

某城市的消防總部將全市劃分為11個防火區(qū)，設有4個消防救火

站。下圖①?④表示消防站，「11表示防火區(qū)域，圖中連線表示各地區(qū)由哪個消

防站負責。問題：可否減少消防站的數目，仍能同樣負責各地區(qū)的防火任務？如

果可以，應關閉哪個消防站？

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

管理運籌學

1,保留第i個消防隊

0,撤消第i個消防隊

解:令

x