運籌學(xué)課件完整版

經(jīng)濟學(xué)核心課程運

籌

學(xué)(Operations

Research)

緒論本章主要內(nèi)容：(1)運籌學(xué)簡述(2)運籌學(xué)的主要內(nèi)容(3)本課程的教材及參考書(4)本課程的特點和要求(5)本課程授課方式與考核(6)運籌學(xué)在工商管理中的應(yīng)用

運籌學(xué)

(Operations

Research)系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運籌學(xué)稱之為管理科學(xué)(Management

Science)。

運籌學(xué)所研究的

問題，可簡單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。運籌學(xué)簡述Page

3運籌學(xué)簡述運籌學(xué)的歷史“運作研究(Operational

Research)小組”:解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如：1.

如何合理運用雷達有效地對付德軍德空襲2.

對商船如何進行編隊護航，使船隊遭受德國潛

艇攻擊時損失最少；3.

在各種情況下如何調(diào)整反潛深水炸彈的爆炸深

度，才能增加對德國潛艇的殺傷力等。Page

4●

圖論●

存儲論●

排隊論●

對策論●

排序與統(tǒng)籌方法●

決策分析●

數(shù)學(xué)規(guī)劃(線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動態(tài)規(guī)劃等)運籌學(xué)的主要內(nèi)容Page

5選用教材《運籌學(xué)基礎(chǔ)及應(yīng)用》胡運權(quán)主編哈工大出版社參考教材>

《運籌學(xué)教程》胡運權(quán)主編(第2版)清華出版社>《

管理運籌學(xué)》韓伯棠主編(第2版)高等教育出版社《運籌學(xué)》(修訂版)錢頌迪主編清華出版社本課程的教材及參考書Page

6先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運籌學(xué)的研究的主要步驟：本課程的特點和要求結(jié)果分析與

實施模型建立與修改模型求解與檢驗系統(tǒng)分析

問題描述數(shù)據(jù)準(zhǔn)備真實系統(tǒng)Page

7本課程授課方式與考核講授為主，結(jié)合習(xí)題作業(yè)學(xué)科總成績期末成績

(60%)課堂考勤

(50%)平時成績

(40%)平時作業(yè)

(50%)Page

8運籌學(xué)在工商管理中的應(yīng)用

Page

9運籌學(xué)在工商管理中的應(yīng)用涉及幾個方面：1.生產(chǎn)計劃2.運輸問題3.人事管理4.庫存管理5.市場營銷6.財務(wù)和會計另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項目的選擇與評價，工程優(yōu)化設(shè)計等。組織應(yīng)用效果聯(lián)合航空公司在滿足乘客需求的前提下，以最低成本進

行訂票及機場工作班次安排每年節(jié)約成本600萬美元Citgo石油公司優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和營銷每年節(jié)約成本7000萬AT&T優(yōu)化商業(yè)用戶的電話銷售中心選址每年節(jié)約成本4.06億美元，銷

售額大幅增加標(biāo)準(zhǔn)品牌公司控制成本庫存(制定最優(yōu)再定購點和定購

量確保安全庫存)每年節(jié)約成本380萬美元法國國家鐵路公司制定最優(yōu)鐵路時刻表并調(diào)整鐵路日運營量每年節(jié)約成本1500萬美元，

年收入大幅增加。Taco

Bell優(yōu)化員工安排，以最低成本服務(wù)客戶每年節(jié)約成本1300萬美元Delta航空公司優(yōu)化配置上千個國內(nèi)航線航班來實現(xiàn)利潤

最大化每年節(jié)約成本1億美元運籌學(xué)在工商管理中的應(yīng)用Interface上發(fā)表的部分獲獎項目Page

10“管理運籌學(xué)”2.0版包括：線性規(guī)劃、運輸問題、整數(shù)規(guī)劃(0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃)、目標(biāo)規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關(guān)鍵路徑、存儲論、排隊論、決策分析、預(yù)測問題和層次分析法，共15個子模塊。圖與網(wǎng)絡(luò)最

短

路

問

題最小生成樹問題最

大

流

問

題最小費用最大流關(guān)鍵路徑問題其它模型存

儲

論排

隊

論決策分析預(yù)

測層次分析法version.2.0說

明關(guān)

于幫

助退

出“管理運籌學(xué)”軟件介紹線性規(guī)劃線

性

規(guī)

劃運輸間題整

數(shù)

規(guī)

劃目

標(biāo)

規(guī)

劃對

策

論管理運籌學(xué)管理運籌學(xué)2.0Page

11●

LP

的數(shù)學(xué)模型●

圖解法●

單純形法●

單純形法的進一步討論-人工變量法●

LP

模型的應(yīng)用Chapter1

線性規(guī)劃(Linear

Programming)本章主要內(nèi)容：

1.規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：(1)當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源(如資金、設(shè)備、原標(biāo)材料、人工、時間等)去完成確定的任務(wù)或目標(biāo)(2)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益(如產(chǎn)品量最多、利潤最大.)線性規(guī)劃問題的數(shù)學(xué)模型Page

13大?v=(a-2x)2

·x例1.1

如圖所示，如何截取x使鐵皮所圍成的容積最線性規(guī)劃問題的數(shù)學(xué)模型2(a-2x)

·x.(-2)+(a-2x)2=0Page

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

某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、

四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺

時如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使

企業(yè)總的利潤最大?設(shè)備產(chǎn)品ABCD利潤(元)甲21402乙22043有效臺時1281612Page

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

Page

16解：設(shè)x?

、x?分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：max

Z=2x?+3x?2x1+2x?≤12X?+2x?≤8s.t.

4x,

≤164x?≤12X?≥0,x?≥0線性規(guī)劃問題的數(shù)學(xué)模型2.

線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成決策變量

Decision

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

Objective

function約束條件

Constraints怎樣辨別一個模型是線性規(guī)劃模型?其特征是：(1)問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；(2)問題的約束條件是一組多個決策變量的線性不等式或等式。Page

17線

性

規(guī)

劃

問

題

的

數(shù)

學(xué)

模

型3.線性規(guī)劃數(shù)學(xué)模型的一般形式目標(biāo)函數(shù)：

max(min)z=c,x?+C?x?+

…

…+c,x,aμx,+a??x,+

…

…+ax,≤(=

·≥)b,:約束條件：ax+am2x,+

…

…+ax,≤(=

·≥)bx,≥0

…

…x,≥0簡

寫

為

：;(i=1

·2

…m)(j=1

·2

…n)Page

18x,≥0線

性

規(guī)

劃

問

題

的

數(shù)

學(xué)

模

型向量形式：

max(minx=

CX其中：

C=(c?c?

-c,)Page

19線性規(guī)劃問題的數(shù)學(xué)模型max(min)Z

=CX其中：

C=(c,c?

c,)矩陣形式：Page

20特點：(1)目標(biāo)函數(shù)求最大值(有時求最小值)(2)約束條件都為等式方程，且右端常數(shù)項b,都大于或等于零(3)決策變量x;為非負(fù)。線性規(guī)劃問題的數(shù)學(xué)模型Page

21線

性

規(guī)

劃

問

題

的

數(shù)

學(xué)

模

型

Page

22(2)如何化標(biāo)準(zhǔn)形式目標(biāo)函數(shù)的轉(zhuǎn)換如果是求極小值即minz=∑c,x,,

則可將目標(biāo)函數(shù)乘以(-1),可化為求極大值問題。即

maxz'=-z=-Zc,x,也就是：令z'=-z,

可得到上式。變量的變換若存在取值無約束的變量x,,

可令x;=x;-x"其中：x;,x"≥0線性規(guī)劃問題的數(shù)學(xué)模型約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。Zax,≤b?

=>

Za,x,+xμ=b,x

≥0

稱為松弛變量Za,x,≥b

>

Za,x,-x=b,XH≥0

稱為剩余變量●

變量x,≤0

的變換可令

x)=-x,,

顯然

x/≥0Page

23解：(1)因為x?

無符號要求，即x3

取正值也可取負(fù)值，標(biāo)準(zhǔn)

型中要求變量非負(fù)，所以用

x;-x”替換x3,

且

x3,x”≥0例1.3

將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式minZ=-2x,+x?+3x?線性規(guī)劃問題的數(shù)學(xué)模型Page

24(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4,x?

≥0,化為等式；(3)第二個約束條件是“≥”號，在“≥”左端減去剩余變量xs,xs≥0;(4)第3個約束方程右端常數(shù)項為-5,方程兩邊同乘以(-1),將右端常數(shù)項化為正數(shù)；(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令z'=-z,得到maxz'=-z,

即當(dāng)z達到最小值時z'達到最大值，反之亦然；線性規(guī)劃問題的數(shù)學(xué)模型Page

25線性規(guī)劃問題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：maxZ=2x;-x?-3(x3-x?)+0x?+0x?Page

26線性規(guī)劃問題線性規(guī)劃問題的數(shù)學(xué)模型4.線性規(guī)劃問題的解求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標(biāo)函數(shù)(1)達到最大值。Page

27●

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域?！?/p>

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

基：

設(shè)

A為約束條件②的mXn

階系數(shù)矩陣(m<n),

其秩為m,B

是矩陣A

中m

階滿秩子矩陣(

|BI≠0),

稱B

是規(guī)劃問題的一

個基。設(shè)：稱

B

中每個列向量P;(j=12……m)

為基向量。與基向量P對應(yīng)的變量x;

為基變量。除基變量以外的變量為非基變量。線性規(guī)劃問題的數(shù)學(xué)模型Page

28●

基解：

某一確定的基B,

令非基變量等于零，由約束條件

方程②解出基變量，稱這組解為基解。在基解中變量取非0

值的個數(shù)不大于方程數(shù)m,

基解的總數(shù)不超過C●

基可行解：

滿足變量非負(fù)約束條件的基本解，簡稱基可

行解?！?/p>

可行基：

對應(yīng)于基可行解的基稱為可行基。線性規(guī)劃問題的數(shù)學(xué)模型基可行解Page

29解：約束方程的系數(shù)矩陣為2×5矩陣

例1.4求線性規(guī)劃問題的所有基矩陣。max

Z=4x,-2x?-x,r(A)=2,2

階子矩陣有10個，其中基矩陣只有9個，即線性規(guī)劃問題的數(shù)學(xué)模型Page

30下面我們分析一下簡單的情況——只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但必需將

一般形式變成標(biāo)準(zhǔn)形式圖解法單純形法線性規(guī)劃問題的求解方法一般有

兩種方法圖解法Page

31圖解法例1.5

用圖解法求解線性規(guī)劃問題max

Z=2X?+X?Page

32nax

Z

X?+1.9X?=3.8(2)minX?-

1.9X?=3.830X1Lo:\0=2X?+X?X?-

1.9X?=-3.8(2)X?+1.9X2=10.2≥\17.2=2X?+X?\20=2X?+X?X24=2X,+X?此點是唯一最優(yōu)解，

且最優(yōu)目標(biāo)函數(shù)值max

Z=17.2圖解法max

Z=2X?+X?\11=2X?+X?Page

33(7.6,2)可行域X?-

1.9X2=3.8X1Lo0=3X?+5.7X?X?-1.9X?=-3.8(≥)藍色線段上的所有點都是最

優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值max

Z=34.2是唯一的。max

Z=3X?+5.7X?X2可行域X?+1.9X?=3.8((7.6,2)A2=3X?+5.7X?X?+1.9X?=10.2(3.8,4)圖解法Page

34X?+1.9X?=3.8(2)min

Z

X?-

1.9X?=3.8()Lo:B=5X+4X?=5X+4X?此點是唯一最優(yōu)解<0,

2)圖解法X2

X+1.9X?=10.2min

Z=5X1+4X23=5Xq+4X?Page

35可行域X1Page

36例1.6

max

Z=x?+2x?x?+3x?≥6x?+x?≥43x,+x?≥6x?≥0

、x,≥0圖解法X2無界解(無最優(yōu)解)x1+3x2=6(≥)3x1+x2=6(≥)x1+x2=4(≥)2例1.7

maxZ=3x?+4x?2x,+x?≤40x,+1.5x,≤30x?+x,≥50x

,≥0,x,≥0X2504030-2010無可行解(即無最優(yōu)解)Ox1304010學(xué)習(xí)要點：1.通過圖解法了解線性規(guī)劃有幾種解的形式(唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解)2.作圖的關(guān)鍵有三點：(1)可行解區(qū)域要畫正確(2)目標(biāo)函數(shù)增加的方向不能畫錯(3)目標(biāo)函數(shù)的直線怎樣平行移動

圖解法Page

38凸集：如果集合C中任意兩個點X1

、X2,

其連線上的所有點也都是集合C

中的點，稱C

為凸集。單純形法基本原理不是凸集凸集凸集Page

39頂點定理1:若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2:線性規(guī)劃問題的基可行解X

對應(yīng)可行域(凸集)的頂點。定理3:若問題存在最優(yōu)解，

一定存在一個基可行解是最優(yōu)解。

(或在某個頂點取得)單純形法基本原理Page

40單純形法的計算步驟單純形法的思路找出一個初始可行解否轉(zhuǎn)移到另一個基本可行解

(找出更大的目標(biāo)函數(shù)值)最優(yōu)解結(jié)束核心是：變量迭代是否最優(yōu)循環(huán)Page

41是單純形表C1

·

·

·

·

·CmCm+1

·

·

·

·Cn·

…

…XmXm+1

·

…

…Xnb

1……

0bm

0

……

1am0OCjXXXm單純形法的計算步驟…

…mσ,=c;-2ca……其

中

：…

…mPage

42CmCB……5m單純形法的計算步驟例1.8

用單純形法求下列線性規(guī)劃的最優(yōu)解max

Z=3x,+4x?解：1)將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4

則標(biāo)準(zhǔn)型為：max

Z=3x,+4x?Page

430

X3

40

2

1

1

00

4

30

1

3

0

1O

3

4

0

0檢驗數(shù)

A?=C?-(c?a?+c?a?)=3-(0×2+0×1)=3單純形法的計算步驟

Page

442)求出線性規(guī)劃的初始基可行解，列出初始單純形表。CBCj基b3x14X20X30X40.3)進行最優(yōu)性檢驗如果表中所有檢驗數(shù)

σ,≤0,則表中的基可行解就是問題

的最優(yōu)解，計算停止。

否則繼續(xù)下一

步。4)從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表①

確定換入基的變量。選擇σ,>0,對應(yīng)的變量x;作為換入變

量，當(dāng)有一個以上檢驗數(shù)大于0時，

一般選擇最大的一個檢驗數(shù)，即：σ,=maxb,Iσ,>0},

其對應(yīng)的x

作為換入變量。②

確定換出變量。根據(jù)下式計算并選擇0,選最小的θ對應(yīng)基變量作為換出變量。

單純形法的計算步驟Page

45③

用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。5)重復(fù)3)、4)步直到計算結(jié)束為止。單純形法的計算步驟Page

46單純形法的計算步驟換

入

列將3化為1Cj

3

4CB

基變量

b

X20

X?

40

2

10

X?

30

1

3

Oj

3

4乘

0

3

30

5/3

0以

4

X?

10

1/3

1O

5/3

0后得

3

X1

18

1

0到

4

x2

4

0

10

0b;/a;z,a;>00

0X3

X41

00

10

01

—1/30

1/30

-4/33/5

—

1/5—1/5

-2/5-1

-10;4010換出行Page

47O;18301/3單純形法的計算步驟例1.9

用單純形法求解max

Z=x,+2x?+x,解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：max

Z=x;+2x?+x?不難看出x4

、x?

可作為初始基變量，列單純形表計算。Page

48Cj121000;CB基變量bX1X2?X4x50X4152-32100xs201/3150120σ;121000X475301713252x2201/3150160O;1/30-90-21X1251017/31/312X235/30128/9-1/92/300-98/9-1/9-7/3單純形法的計算步驟Page

49X學(xué)習(xí)要點：1.線性規(guī)劃解的概念以及3個基本定理2.熟練掌握單純形法的解題思路及求解步驟單純形法的計算步驟Page

50單純形法的進一步討論一人工變量法

Page

51人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位

矩陣，為了得到一組基向量和初基可行解，在約束條件的

等式左端加一組虛擬變量，得到一組基變量。這種人為加

的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M

法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。例1.10

用大M

法解下列線性規(guī)劃max

Z=3x,+2x?-x?單純形法的進一步討論一人工變量法

Page

52系數(shù)矩陣中不存在

單位矩陣，無法建

立初始單純形表。解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式max

Z=3x?+2x?-x?單純形法的進一步討論一人工變量法

Page

53故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：max

Z=3x?+2x?-x?-Mx?-Mx,其中：

M

是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介

紹的單純形法求解該模型，計算結(jié)果見下表。Cj32-100-M-MCBXBb?x2?X4xsX6x700-M-MX6x5x?4101-4123-1-2121-100010100001451O3-2M

2+M

-1+2M個

-M0-M-1X6x5x?381-6-3253-2001-1000101003/58/3O5-6M5M0-M002-M-1x2xsx?3/531/511/5-6/53/5-2/5100001-1/53/5-2/501031/3510

00023-1x2x?x?1331/319/301010000111025/32/3O;0

0

0

-5-25/3單純形法的進一步討論一人工變量法

Page

54xx1)唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零，則線規(guī)劃具有唯一最優(yōu)解。2)多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零，則線則性規(guī)劃具有多重最優(yōu)解(或無窮多最優(yōu)解)。3)無界解判別：某個2>0且aμ≤0

(i=1,2,…,m)

則線性規(guī)劃具有無界解。4)無可行解的判斷：當(dāng)用大M

單純形法計算得到最優(yōu)解并且存在Ri>0時，則表明原線性規(guī)劃無可行解。5)退化解的判別：存在某個基變量為零的基本可行解。單純形法的進一步討論一人工變量法

Page

55解的判別：建

立

模

型個數(shù)取

值右端項等式或不等式極大或極小新加變量

系數(shù)兩個三個以上x≥0x;無約束x≤0b;≥0b<0≤=≥maxZminZxsXa求解圖

解

法、單純形法單純形法不處理令xj=xxj≥0

x?

≥0令x/=號不處理約束條

件兩端

同乘以-1加松

弛變

量加入

人

工

變

量減去.加入不處理令z'=-ZminZ=-maxz0-M單純形法的進一步討論一人工變量法單純性法小結(jié)：Page

56x基變量中是否含有x。是無可行解無界解有某個

否非基變量的qj=0是無窮多最優(yōu)解停止唯

一

最優(yōu)解所有≤0否找出(σ)m

即ax≤0(對任一

σ>0)否計算θ,=(b,

an>0)ak是σ是用非基變量x;

替換基變量x,列出下一個

新單純形表求：σ;=cj-Zj循環(huán)循環(huán)否一般而言，

一個經(jīng)濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型?！?/p>

要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且

為線性函數(shù)●

存在著多種方案●

要求達到的目標(biāo)是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述線性規(guī)劃模型的應(yīng)用Page

58班次時間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機和乘務(wù)人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應(yīng)怎樣安排司機和乘務(wù)人員，即能滿

足工作需要，又使配備司機和乘務(wù)人員的人數(shù)減少?1.人力資源分配問題例1.11

某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員人數(shù)如下表所示：線性規(guī)劃在管理中的應(yīng)用Page

59x?+x?≥60x?+x?≥70x?+x?≥60x3+x?≥50x?+x?≥20x?+x?≥30x?,x?,X?,x?,xs,x?≥0解：設(shè)x;表示第i班次時開始上班的司機和乘務(wù)人員人數(shù)。min

x;+x?+x,+x?+x?+x?此問題最優(yōu)解：

x?=50,x?=20,x?=50

,x?=0,x?=20,x?=10,

一共需要司機和乘務(wù)員150人。線性規(guī)劃在管理中的應(yīng)用Page

60s.t2.生產(chǎn)計劃問題某廠生產(chǎn)

I、Ⅱ、Ⅲ

三種產(chǎn)品，

都分別經(jīng)A

、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2

上完

成，有B1、B2、B3

三種設(shè)備可用于完成B

工序。已知產(chǎn)品

I

可在A、B

任何一種設(shè)備上加工；產(chǎn)品Ⅱ可在任何規(guī)格的A

設(shè)備上加工，但完成B

工序時，只能

在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2與B2設(shè)備上加工。

加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)如下表，

試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。線性規(guī)劃在管理中的應(yīng)用Page

61設(shè)備產(chǎn)品設(shè)備有效

臺時設(shè)備加工費(單位小時)IⅡⅢ27910.000321B168124000250B247000783B37114000200原料費(每件)0.250.350.5售價(每件)1.252.002.8線性規(guī)劃在管理中的應(yīng)用Page

62解：設(shè)xjk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條

件有：5x+10x?

≤6000

(設(shè)備A1)7xμz+9x?+12x?

≤10000

(設(shè)備A2)6x?2+8x?

≤4000

(設(shè)備B1)4x,2+11x22≤7000

(設(shè)備B2)7x,23≤4000

(設(shè)備B3)xm

+xμ=x?+x2+x23

(產(chǎn)品在工序A,B

上加工的數(shù)量相等x?

n+x?2=x?21

(產(chǎn)品Ⅱ在工序A,B

上加工的數(shù)量相等)x??=x22

(產(chǎn)品Ⅲ在工序A,B

上加工的數(shù)量相等)xx≥0(i=1,2,3;j=1,2;k=1,2,3)線性規(guī)劃在管理中的應(yīng)用Page

63線性規(guī)劃在管理中的應(yīng)用

Page

64目標(biāo)是利潤最大化，即利潤的計算公式如下：利潤

(銷售單價-原料單你該產(chǎn)品件數(shù)(每臺時的設(shè)備費用該設(shè)備實際使用臺時帶入數(shù)據(jù)整理得到：max0.75xm+0.775x+1.15xu+1.36x2+1.915x?2-0.375x2-0.5x2-0.44&x2-1.23x322-0.35x3

+1.915x32-0.375x21-0.5x?21-0.448x?2-

1.23x?22-0.35x235xu+10xπ≤60007x2+9x?2+12x?12≤100006x,21+8x2≤40004x?22+11x322≤7000s.t

7x?23≤4000X?11+X?1?=X?21+X?22+X123x211+x?12=X?21312

=

322xx≥0(i=1,2,3;j=1,2;k=1,2,3)線性規(guī)劃在管理中的應(yīng)用因此該規(guī)劃問題的模型為：ma

x0.75xm+0.775x

+1.15xu+1.36x?12Page

653.套裁下料問題例：現(xiàn)有一批某種型號的圓鋼長8米，需要截取2.5米長的毛坯100根，長1.3米的毛坯200根。問如何才能

既滿足需要，又能使總的用料最少?解：為了找到一個省料的套裁方案，必須先設(shè)計出較好的幾個下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格

的圓鋼，以滿足對各種不同規(guī)格圓鋼的需要并達到省料的目

的，為此可以設(shè)計出4種下料方案以供套裁用。IⅡⅢIV2.5m32101.3m0246料頭00.40.30.2線性規(guī)劃在管理中的應(yīng)用Page

66設(shè)按方案I、Ⅱ、Ⅲ、IV

下料的原材料根數(shù)分別為x;(j=1,2,3,4),可列出下面的數(shù)學(xué)模型：min

Z=x?+x?+x?+x?線性規(guī)劃在管理中的應(yīng)用Page

674.配料問題例：某人每天食用甲、乙兩種食物

(如豬肉、雞蛋)其資料如下：問兩種食物各食用多少，才能既滿足需要、又使總費用最省?含量

食物成分甲

乙最低需要量A;A?A?0.11.71.100.150.751.301.007.5010.00原料單價2

1.5線性規(guī)劃在管理中的應(yīng)用Page

68線性規(guī)劃在管理中的應(yīng)用解：設(shè)X

表示B,種食物用量minZ=2x,+1.5x?Page

69Chapter2

對偶理論(Duality

Theory)本章主要內(nèi)容：●

線性規(guī)劃的對偶模型●

對偶性質(zhì)●

對偶問題的經(jīng)濟解釋-影子價格●

對偶單純形法

1.對偶問題的現(xiàn)實來源設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A,B,C,D

順序加工，每件產(chǎn)品加工所需的機時數(shù)、每件產(chǎn)品的利潤值及每種設(shè)備的可利用機時數(shù)列于下表：產(chǎn)品數(shù)據(jù)表設(shè)備產(chǎn)品ABCD產(chǎn)品利潤(元/件)甲21402乙22043設(shè)備可利用機時數(shù)(時)1281612問：充分利用設(shè)備機時，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤?線性規(guī)劃的對偶模型Page

71反過來問：若廠長決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機器用于接受外加工，只收加工費，那么4種機器的機時如何定

價才是最佳決策?解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x,及x?件，則數(shù)學(xué)模型為：maxz=2x,+3x?線性規(guī)劃的對偶模型Page

72在市場競爭的時代，廠長的最佳決策顯然應(yīng)符合兩條：(1)不吃虧原則。即機時定價所賺利潤不能低于加工甲、乙型產(chǎn)品所獲利潤。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。(2)競爭性原則。即在上述不吃虧原則下，盡量降低機時總收費，以便爭取更多用戶。設(shè)A、B、C、D

設(shè)備的機時價分別為y1、y2、y3、y4,

則新的線性規(guī)劃數(shù)學(xué)模型為：minw=12y?+8y?+16y?+12y?線性規(guī)劃的對偶模型Page

73A(y?)B(v?)C(v?)D(y?)甲

(

x?)21402乙

(

x?)220431281612minwmax

z把同種問題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會發(fā)現(xiàn)一個有趣的現(xiàn)象。原問題與對偶問題對比表線性規(guī)劃的對偶模型Page

74線性規(guī)劃的對偶模型2.原問題與對偶問題的對應(yīng)關(guān)系maxz

=2x?+3x?min

w=12y?+8y?+16y?+12y?原問題(對偶問題)對偶問題(原問題)Page

75(1)對稱形式特點：目標(biāo)函數(shù)求極大值時，所有約束條件為≤號，變量非負(fù)；目標(biāo)函數(shù)求極小值時，所有約束條件為≥號，變量非

負(fù)

.P:

maxZ=CX

D:

minW

=Yb線性規(guī)劃的對偶模型已知P,

寫出DPage

76線性規(guī)劃的對偶模型例2.

1

寫

出

線

性

規(guī)

劃

問

題

的

對

偶

問

題maxZ

=2x,-3x?+4x?解

：

首先將原問題變形為對稱形式maxZ

=2x,-3x?+4x?Page

77線性規(guī)劃的對偶模型對

偶

問

題

：minW=-2y

?+3y?-5y?Page

78(2)非對稱型對偶問題若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式再寫對偶問題。也可直接按教材表2-2中的對應(yīng)關(guān)系寫出非對

稱形式的對偶問題。線性規(guī)劃的對偶模型Page

79原問題(或?qū)ε紗栴})對偶問題(或原問題)約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=線性規(guī)劃的對偶模型Page

80線性規(guī)劃的對偶模型例2.2

寫出下列線性規(guī)劃問題的對偶問題.max

Z=2x?+3x?-5x?+x?解：原問題的對偶問題為minW

=5y,+4y?+6y?Page

81對偶性質(zhì)

Page

82例2.3

分別求解下列2個互為對偶關(guān)系的線性規(guī)劃問題分別用單純形法求解上述2個規(guī)劃問題，得到最終單純形表如下表：maxz.=2x?+x?minw=15y,+24y?+5y?XBb原問題的變量原問題的松弛變量X1X2????15/20015/4-15/2X17/21001/4-1/2?3/2010-1/43/2O000-1/4-1/2XBb對偶問題的變量對偶問題的剩余變量y1y2Y3y4ysy?1/4-4/510-1/41/4y?1/215/2011/2-3/2σ15/2007/23/2對偶性質(zhì)對偶問題最優(yōu)表原問題最優(yōu)表Page

83XXXXX原問題與其對偶問題的變量與解的對應(yīng)關(guān)系：在單純形表中，原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問

題的變量。對

偶

性

質(zhì)Page

84對偶性質(zhì)

Page

85性質(zhì)1對稱性定理：對偶問題的對偶是原問題min

W=Y

bs.t.YA≥CY≤0max

Z=C

Xs.t.AX≥bX≥0推論1:原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下屆；反之，對偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目

標(biāo)函數(shù)值的上界。推論2:在一對對偶問題

(P)

和

(D)

中，若其中一個問題可行但目標(biāo)函數(shù)無界，則另一個問題無可行解；反之不成立。這也是對性質(zhì)2

弱對偶原理(弱對偶性):

設(shè)X°

和Y

分別是問題(P)和

(D)的可行解，則必有CX'≤Y'b

即：對偶性質(zhì)偶問題的無界性。Page

86對偶性質(zhì)

Page

87推論3:在一對對偶問題

(P)

和

(D)

中，若一個可行(如P),

而另一個不可行(如D),

則該可行的問題目標(biāo)函數(shù)值無界。性質(zhì)3

最優(yōu)性定理：如果X

是原問題的可行解，

Y

是其對偶問題的可行解，并且：CX'=BY'

即

：z=w則X

是原問題的最優(yōu)解，

Y

是其對偶問題的最優(yōu)解。性質(zhì)4

強對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。還可推出另一結(jié)論：若

(LP)

與

(DP)

都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。性質(zhì)5

互補松弛性：設(shè)X?

和Y?

分別是P

問題和D

問題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：

X,、Y,為松弛變量對偶性質(zhì)Page

88性質(zhì)5的應(yīng)用：該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知Y*

求X*

或已知X*

求Y*互補松弛條件由于變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：若Y

*≠0,

則X、必為0;若X

*≠0,

則Y、必為0利用上述關(guān)系，

建立對偶問題(或原問題)的約束線性方程組，方程組的解即為最優(yōu)解。

對偶性質(zhì)Page

89對偶性質(zhì)例2.4

已知線性規(guī)劃maxz=3x,+4x?+x?的最優(yōu)解是X*=(6,2,0),求其對偶問題的最優(yōu)解Y*。解：寫出原問題的對偶問題，即min

w=10y?+16y?min

w=10y?+16y?標(biāo)準(zhǔn)化Page

90對偶性質(zhì)

Page

91設(shè)對偶問題最優(yōu)解為Y*=(y?

,y?),

由互補松弛性定理可知，X*

和Y*

滿足：解此線性方程組得y?=1,y?=1,從而對偶問題的最優(yōu)解為：Y*=(1,1),

最優(yōu)值w=26。因為X?

≠0,X?

≠0,所以對偶問題的第一、二個約束的松弛(y?,y?,y?)(x?,x?,x?)′=0(y?,y?)(x?,x?)?=0變量等于零，即y?=0,y?=0,

帶入方程中：Y、X3=0Y*X,=0即：的對偶問題的最優(yōu)解為Y*=(0,-2),

求原問題的最優(yōu)解。解：對偶問題是max

w=4y?+6y?

max

w

=4y?+6y?例2.5

已知線性規(guī)劃minz=2x,-x?+2x?對偶性質(zhì)標(biāo)準(zhǔn)化Page

92設(shè)對偶問題最優(yōu)解為X*=(x1,x?

,x?),

由互補松弛性定理可知，

X*

和Y*

滿足：(y?,y?,y?)(x?,x?,x?)′=0(y?,y?)(x?,x?)?=0將Y*

帶入由方程可知，

y?=ys=0,y?=1。∵y?=-2≠0

∴x?=0又∵y?=1≠0

∴x?=0將x?

,xs

分別帶入原問題約束方程中，得：解方程組得：

X?=-5,x?=-1,所以原問題的最優(yōu)解為X*=(-5,0,-1),

最優(yōu)值z=-12對偶性質(zhì)Page93對應(yīng)關(guān)系原問題最優(yōu)解無界解無可行解對偶問題最優(yōu)解(Y,Y)(N,N)無界解(Y,Y)無可行解(Y,Y)無法判斷對偶性質(zhì)原問題與對偶問題解的對應(yīng)關(guān)系小結(jié)Page

94判斷下列結(jié)論是否正確，如果不正確，應(yīng)該怎樣改正?1)任何線性規(guī)劃都存在一個對應(yīng)的對偶線性規(guī)劃.2)原問題第個約束是“≤”約束，則對偶變量yi≥0.3)互為對偶問題，或者同時都有最優(yōu)解，或者同時都無最優(yōu)解.4)對偶問題有可行解，則原問題也有可行解.5)原問題有多重解，對偶問題也有多重解.6)對偶問題有可行解，原問題無可行解，則對偶問題具有無界解.7)原問題無最優(yōu)解，則對偶問題無可行解.8)對偶問題不可行，原問題可能無界解.9)原問題與對偶問題都可行，則都有最優(yōu)解

.10)原問題具有無界解，則對偶問題不可行.11)對偶問題具有無界解，則原問題無最優(yōu)解.1

2

)

若X*

、Y

是原問題與對偶問題的最優(yōu)解，則X*=Y*.思考題Page

95對偶問題的經(jīng)濟解釋一影子價格

Page

96定義：在一對P

和

D

中，若P

的某個約束條件的右端項常數(shù)bi

(第i種資源的擁有量)增加一個單位時，

所引起目標(biāo)

函數(shù)最優(yōu)值z*

的改變量稱為第i

種資源的影子價格，其值等于D

問題中對偶變量y*。1.影子價格的數(shù)學(xué)分析：maxZ

=CX

minW=YbD由對偶問題得基本性質(zhì)可得：

對偶問題的經(jīng)濟解釋一影子價格

Page

972.

影子價格的經(jīng)濟意義1)影子價格是一種邊際價格在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對偶變量y;就是第i

種資源的影子價格。即：對偶問題的經(jīng)濟解釋一影子價格

Page

982)影子價格是一種機會成本影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機會成本。若第i種資源的單位市場價格為m;,

則有當(dāng)y;>m;

時，企業(yè)愿意購進這種資源，單位純利為y;-m;,

則有利可圖；如果y;<m?

,則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利m?-y;*,

否則，企業(yè)

無利可圖，甚至虧損。結(jié)論：若y;">m;

則購進資源i,

可獲單位純利y;-m;若y;<m;

則轉(zhuǎn)讓資源i,

可獲單位純利m;-yi對偶問題的經(jīng)濟解釋一影子價格

Page

993)影子價格在資源利用中的應(yīng)用根據(jù)對偶理論的互補松弛性定理：Y*X=0

,Y、X*=0表明生產(chǎn)過程中如果某種資源bi未得到充分利用時，該種資源的影子價格為0;若當(dāng)資源資源的影子價格不為0時，表明該種資源在生產(chǎn)中已耗費完。其中c;表示第j種產(chǎn)品的價格；

;表示生產(chǎn)該種產(chǎn)品所消耗的各項資源的影子價格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)值大于隱含成本時，即σj>0,

表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則σ;<0,用這些資源生產(chǎn)別的

產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。對偶問題的經(jīng)濟解釋一影子價格4)影子價格對單純形表計算的解釋單純形表中的檢驗數(shù)Page

100對偶單純形法原理對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設(shè)計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形

法。對偶單純形法基本思路：找出一個對偶問題的可行基，保持對偶問題為可行解的條件下，判斷X

是否可行

(Xp

為非負(fù)),若否，通過變換基

解，直到找到原問題基可行解(即Xp

為非負(fù)),這時原問題

與對偶問題同時達到可行解，由定理4可得最優(yōu)解。對偶單純形法Page

101是最優(yōu)解結(jié)束保持DP

為可行解情況下轉(zhuǎn)移到LP

的另一個基本解LP

是否可行(XB≥0)否對偶單純形法找出一個DP

的可行基Page

102循環(huán)解：(1)將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求出一組基本解，因為對偶問題可行，即全部檢驗數(shù)≤0(求

max

問題)。例2.9用對偶單純形法求解：minZ=9x,+12x?+15x,對偶單純形法Page

103Cj-9-12-15000bCBXB?x2?X4?X60X4-2-2-1100-100?-2-3-1010-120x6-1-1-5001-14、(-9/-1.-12/-1.-15/-5)為-9-12-150000對偶單純形法maxZ'=-9x,-12x?-15x?Page

104xxxxCj-9-12-15000bCBXBx1X2X3X4x5X60X4-9/5-9/5010-1/5-36/50?-9/5-14/5001-1/5-46/5-15X31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)σ,-6-9000-342Cj-9-12-15000bCBXBX1X2X3X4x5X60X4-9/14001-9/14-1/14-9/7-12X29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15X31/140101/14-3/1415/7O-3/14000-45/14-33/14對偶單純形法Page

105xGj-9-12-15000CBXBX1X2X3X4X5X6b-9X1100-14/911/92-12x20101-102-15x30011/90-2/92σ000-1/3-3-7/3原問題的最優(yōu)解為：

X*=(2,2,2,0,0,0),Z*=72其對偶問題的最優(yōu)解為：

Y*=(1/3,3,7/3),W*=72對偶單純形法Page

106對偶單純形法應(yīng)注意的問題：●

用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解●

初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準(zhǔn)則最

小

比

值

中

的絕對值是使得比值非負(fù)，在極小化問題σ≥0,分母a<0

這時必須取絕對值。在極大化問題中，σ,≤0,分母a<0,

總滿足非負(fù)，這時絕對值符號不起作用，可以去掉。如ai在本例中將目標(biāo)函數(shù)寫成max

z'=-4x?-x?-3x?這里σ,≤0在求θ時就可以不帶絕對值符號。對偶單純形法Page

107其目的是保證下一個對偶問題的基本解可行●對偶單純形法在確定出基變量時，若不遵循b,=min{b,

|b,<0}規(guī)則，任選一個小于零的b

對應(yīng)的基變量出基，不影響計算結(jié)果，只是迭代次數(shù)可能不一樣。對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進基變量；●普通單純形法的最小比值是

個原問題的基本解可行，對偶單其目的是保證下一值是對偶單純形法Page

108學(xué)習(xí)要點：1.線性規(guī)劃解的概念以及3個基本定理2.熟練掌握單純形法的解題思路及求解步驟本章小結(jié)Page

109Chapter3運輸規(guī)劃(Transportation

Problem)本章主要內(nèi)容：●

運輸規(guī)劃問題的數(shù)學(xué)模型●

表上作業(yè)法●

運輸問題的應(yīng)用

例3.1

某公司從兩個產(chǎn)地A,、A?

將物品運往三個銷地B?

,B?

,B?

,

各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最

小?運輸規(guī)劃問題的數(shù)學(xué)模型B1B2B3產(chǎn)量A1646200A2655300銷量150150200Page

111Min

C=6x+4x??+6x?3+6x?1+5x22+5x23S.t.x1+x12+x13=200X21+x22+x23=300X11+x?1=150x12+x22=150x13+x23=200Xj≥0(i=1

、2;j=1

、2

、3)B1B2B3產(chǎn)量A1X1X12X13200A2X21X22X23300銷量150150200解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量=500設(shè)

xj

為從產(chǎn)地A,運往銷地B;的運輸量，得到下列運輸量運輸規(guī)劃問題的數(shù)學(xué)模型Page

112表：運輸規(guī)劃問題的數(shù)學(xué)模型

Page

113運輸問題的一般形式：產(chǎn)銷平衡A1、A?

、…

、Am

表示某物資的m

個產(chǎn)地；

B、B?

、…、B,

表示某物質(zhì)的n個銷地；

a?

表示產(chǎn)地A

的產(chǎn)量；

bj表示銷地Bj的銷量；

Cj表示把物資從產(chǎn)地A;運往銷地B;的單位運價。設(shè)x

為從產(chǎn)地A;

運往銷地B;的運輸量，得到下列一般運輸量問題的模型：minz=22cx變化：1)有時目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等；2)當(dāng)某些運輸線路上的能力有限制時，在模型中直接加入約束條件(等式或不等式約束);3)產(chǎn)銷不平衡時，可加入假想的產(chǎn)地(銷大于產(chǎn)時)或銷地(產(chǎn)大于銷時)。定理：設(shè)有m

個產(chǎn)地n個銷地且產(chǎn)銷平衡的運輸問題，則基變量數(shù)為m+n-1。運輸規(guī)劃問題的數(shù)學(xué)模型Page

114步驟描述方法第一步求初始基行可行解(初始調(diào)運方案)最小元素法、

元素差額法、第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的

檢驗數(shù)全都非負(fù)時得到最優(yōu)解，若存在檢驗數(shù)?<0,說明還沒有達到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位

勢法第三步調(diào)整運量，即換基，選一個變量出基，對原運

量進行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步表上作業(yè)法是一種求解運輸問題的特殊方法，其實質(zhì)是單純形法。表上作業(yè)法Page

115????產(chǎn)量A3113107219284A3741059銷量3656表上作業(yè)法例3.2某運輸資料如下表所示：問：應(yīng)如何調(diào)運可使總運輸費用最小?單位

銷地運價Page

116產(chǎn)地BBBB????產(chǎn)量?3113107?1928?7461059銷量356解：第1步求初始方案方法1:最小元素法基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)(調(diào)運),然后次小，直到最后供完為止。表上作業(yè)法Page

117AAABBBB總的運輸費=(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元元素差額法對最小元素法進行了改進，考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小

運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案。1051052151201515總運費是z=10×8+5×2+15×1=105表上作業(yè)法最小元素法：Page

1188后一種方案考慮到Cn

與C?

之間

的差額是8-2=6,如果不先調(diào)運

x?

1,

到后來就有可能xμ#0,這

樣會使總運費增加較大，從而先

調(diào)運x?

1,

再是x?2,

其次是x?285

101015251201515用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。總運費z=10×5+15×2+5×1=85表上作業(yè)法Page

119????產(chǎn)量行差額?31077113?192841?7410591銷量3656列差額2513方法2:

Vogel法1

)

從

運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。表上作業(yè)法Page

120AAABBBB????產(chǎn)量行差額?3113

51077?192841?710591銷量3656列差額25132)再從差值最大的行或列中找出最小運價確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列。重復(fù)1)和2),直到找出初始解為至。表上作業(yè)法Page

121AAABBBB????產(chǎn)量行差額A3113

51077?192841?7410591銷量3656列差額2513表上作業(yè)法單位

銷地運價Page

122產(chǎn)地AABBBB????產(chǎn)量行差額3113

51077A21

392

×84737410

×591銷量3656列差額253表上作業(yè)法單位

銷地

運價Page

123產(chǎn)地BBBB單位銷地????產(chǎn)量行差額A3

×11

×3

510②71?1③9

×2

×8

①41?7

×4

⑥10

×591銷量3656列差額53該方案的總運費：(1×3)+(4×6)+(3×5)+(2×10)+(1×8)+(3×5)=85元表上作業(yè)法Page

124運價產(chǎn)地AABBBB第2步最優(yōu)解的判別(檢驗數(shù)的求法)求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記x,的檢驗數(shù)為λ,由第一章知，求最小值的運

輸問題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗數(shù)都非負(fù)，則運輸方案最優(yōu)求檢驗數(shù)的方法有兩種：◆

閉回路法位

勢

法

(

▲

)表上作業(yè)法Page

125表上作業(yè)法

Page

126閉回路的概念稱

集

合

{x

,x,x?2,x?

,…,x

,x

}(其中i,i2,,i;ji,j?

,…,j

互

不

相

同為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表例下表中閉回路的變量集合是{XX242X?3X?3X?

sX?

s,x?

}共有8個頂點，這8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉(zhuǎn)90度與另一頂點連接，表3-3中的變量x?2及x?3不是閉回路的頂點，只是連線的交點。??B3??A1XnX12A2?25?X3X35A4X?243表上作業(yè)法Page

127ABBBBX例如變量組A={x?

,x?

s,x3s,x?

,x,x,?

}

不能構(gòu)成一條閉回路，但A中包含有閉回路{x21,x2s,xas,xa}變量組B={x33,x3z,x?z,x,x?

,}

變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；?B2??XA2?X?2??閉

回

路

{x,x,x3,x3,x?

z,x?

}表上作業(yè)法Page

128AAABBX1)由σy=C(U?+Vj)

計算位勢U?,Vj,

因?qū)兞慷杂笑?0,即C-

(U?+Vj)=0,

令U?=02)再由σn=C-

(U?+Vj)

計算非基變量的檢驗數(shù)σ表上作業(yè)法用位勢法對初始方案進行最優(yōu)性檢驗：當(dāng)存在非基

變量的檢驗

數(shù)ox≥0,

說

明現(xiàn)行方案

為最優(yōu)方案，

否則目標(biāo)成

本還可以進

一步減小。Page

129第3步確定換入基的變量當(dāng)存在非基變量的檢驗數(shù)σμ<0且σμ=min{σ;}時，令Xμ

進

基。從表中知可選X?4進基。第4步確定換出基的變量以進基變量x&為起點的閉回路中，標(biāo)有負(fù)號的最小運量作為

調(diào)整量θ,0對應(yīng)的基變量為出基變量，并打上“×”以示換出作為非基變量。表上作業(yè)法Page

130θ=min{r?x}=min{1,3}=1調(diào)整步驟為：在進基變量的閉回路中標(biāo)有正號的變量加上調(diào)整量

0,標(biāo)有負(fù)號的變量減去調(diào)整量θ,其余變量不變，得到一組新的

基可行解。然后求所有非基變量的檢驗數(shù)重新檢驗。表上作業(yè)法Page

131當(dāng)所有非基變量的檢驗數(shù)均非負(fù)時，則當(dāng)前調(diào)運方案即為最優(yōu)方案，如表此時最小總運費：Z=(1×3)+(4×6)+(3×5)+(2×

10)+(1×8)+(3×5)=85

元表上作業(yè)法Page

132表上作業(yè)法表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平

衡表及單位運價表確定初始調(diào)運方案(最小元素法或Vogel法)求檢驗數(shù)(位勢法)所有檢驗數(shù)≥0找出絕對值最大的負(fù)檢驗數(shù)，用閉合

回路調(diào)整，得到新的調(diào)運方案得到最優(yōu)方案，算出總運價Page

133表上作業(yè)法計算中的問題：(1)若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負(fù)，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取σ<0中最小者對應(yīng)的變量為換入變量。(2)無窮多最優(yōu)解產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的

=0,則該問題有無窮多最優(yōu)解。表上作業(yè)法Page

134(2)退化解：※

表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個0,以保證

有(m+n-1)個數(shù)字格作為基變量。

一般可在劃去的行和列的

任意空格處加一個0即可?！眠M基變量的閉回路對解進行調(diào)整時，標(biāo)有負(fù)號的最小運量(超過2個最小值)作為調(diào)整量0,選擇任意一個最

小運量對應(yīng)的基變量作為出基變量，并打上“×”以示作為

非基變量。表上作業(yè)法Page

135銷地產(chǎn)地????產(chǎn)量A1(0)412(2)4121116A22810(2)(1)29103?8(9)514(12)862211銷量8141214如下例中σ檢驗數(shù)是0,經(jīng)過調(diào)整，可得到另一個最優(yōu)解。表上作業(yè)法Page

136ABBBB銷地產(chǎn)地????產(chǎn)量?3×11×4147A27×7X438×A3326×091106銷量365620表上作業(yè)法例：用最小元素法求初始可行解在x?2、x?2、X?3、x?4中任選一個變量作為基變量，例如選x?4Page

137ABBBB6運輸問題的應(yīng)用1、求極大值問題目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。Page

138求解方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運價表為C,

用一個較大的數(shù)M(M≥max{c,})

去減每一個c;得到矩陣C',

其中C'=(M-c,)≥0,

將C"作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解。運輸問題的應(yīng)用Page

139銷地產(chǎn)地???產(chǎn)量?2589?910710?6512銷量8