運(yùn)籌學(xué)教程課后答案第三章

運(yùn)籌學(xué)教程（第二版）習(xí)題解答第三章習(xí)題解答3.1

與一般線性規(guī)劃的數(shù)學(xué)模型相比，運(yùn)輸問題的數(shù)學(xué)模型具有什么特征?答：1、運(yùn)輸問題一定有有限最優(yōu)解。2、約束系數(shù)只取0或1。3、約束系數(shù)矩陣的每列有兩個1，而且只有兩個1。前m行中有一個1，或n行中有一個1。4、對于產(chǎn)銷平衡的運(yùn)輸問題，所有的約束都取等式。3.2運(yùn)輸問題的基可行解應(yīng)滿足什么條件？將其填入運(yùn)輸表中時有什么體現(xiàn)？并說明在迭代計算過程中對它的要求。解：運(yùn)輸問題基可行解的要求是基變量的個數(shù)等于m+n-1。填入表格時體現(xiàn)在數(shù)字格的個數(shù)也應(yīng)該等于m+n-1。在迭代過程中，要始終保持?jǐn)?shù)字格的個數(shù)不變。第三章習(xí)題解答3.3

試對給出運(yùn)輸問題初始基可行解的西北角法、最小元素法和Vogel法進(jìn)行比較，分析給出的解之質(zhì)量不同的原因。解：用西北角法可以快速得到初始解，但是由于沒有考慮運(yùn)輸價格，效果不好；最小元素法從最小的運(yùn)輸價格入手，一開始效果很好，但是到了最后因選擇余地較少效果不好；Vogel法從產(chǎn)地和銷地運(yùn)價的級差來考慮問題，總體效果很好，但是方法較復(fù)雜。第三章習(xí)題解答3.4

詳細(xì)說明用位勢法(對偶變量法)求檢驗數(shù)的原理。解：原問題的檢驗數(shù)也可以利用對偶變量來計算：第三章習(xí)題解答=

cij

-

(u

i

+

v

j

)

i

=

1,2,

m

;

j

=

1,2,

,

ns

ij其中，ui和vj就是原問題約束對應(yīng)的對偶變量。由于原問題的基變量的個數(shù)等于m+n-1。所以相應(yīng)的檢驗數(shù)就應(yīng)該等于0。即有：cij-

(u

i

+

v

j

)

=

0

i

=

1,2,

m

;

j

=

1,2,

,

n由于方程有m+n-1個，而變量有m+n個。所以上面的方程有無窮多個解。任意確定一個變量的值都可以通過方程求出一個解。然后再利用這個解就可以求出非基變量的檢驗數(shù)了。第三章習(xí)題解答3.5用表上作業(yè)法求解運(yùn)輸問題時，在什么情況下會出現(xiàn)退化解？當(dāng)出現(xiàn)退化解時應(yīng)如何處理？解：當(dāng)數(shù)字格的數(shù)量小于m+n-1時，相應(yīng)的解就是退化解。如果出現(xiàn)了退化解，首先找到同時劃去的行和列，然后在同時劃去的行和列中的某個空格中填入數(shù)字0。只要數(shù)字格的數(shù)量保持在m+n-1個的水平即可。第三章習(xí)題解答3.6

一般線性規(guī)劃問題具備什么特征才能將其轉(zhuǎn)化為運(yùn)輸問題求解，請舉例說明。解：如果線性規(guī)劃問題有“供”和“需”的關(guān)系，并且有相應(yīng)的“費(fèi)用”，就可以考慮將線性規(guī)劃問題

轉(zhuǎn)成運(yùn)輸問題求解。例如，生產(chǎn)滿足需求的問題。第三章習(xí)題解答3.7

試判斷表3-30和表3-31中給出的調(diào)運(yùn)方案可否作為表上作業(yè)法迭代時的基可行解?為什么?答：都不是。數(shù)字格的數(shù)量不等于m+n-1。表3-30銷地產(chǎn)地B1B2B3B4產(chǎn)量A101515A2151025A355銷量5151510第三章習(xí)題解答表3-31銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1150250400A2200300500A325050300A490210300A58020100銷量24041055033070第三章習(xí)題解答3.8

表3-32和表3-33分別給出了各產(chǎn)地和各銷地的產(chǎn)量和銷量，以及各產(chǎn)地至各銷地的單位運(yùn)價，試用表上作業(yè)法求最優(yōu)解。表3-32銷地產(chǎn)地B1B2B3B4產(chǎn)量A145

13

468A26

1252

08A3373

51

14銷量656320第三章習(xí)題解答表3-33銷地產(chǎn)地B1B2B3B4產(chǎn)量A193

3873A21

492

453A35765

25銷量132511第三章習(xí)題解答3.9

試求出表3-34給出的產(chǎn)銷不平衡運(yùn)輸問題的最優(yōu)解。表3-34銷地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A343856銷量3322第三章習(xí)題解答第三章習(xí)題解答習(xí)題3.9的解答銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A13

3762

405A2242

3202A343

3853

06銷量332233.10

某市有三個面粉廠，它們供給三個面食加工廠所需的面粉。各面粉廠的產(chǎn)量、各面食加工廠加工面粉的能力、各面食加工廠和各面粉廠之間的單位運(yùn)價，均表示于表3-35中。假定在第1，2和3面食加工廠制作單位面粉食品的利潤分別為12元、16元和11元，試確定使總效益最大的面粉分配計劃(假定面粉廠和面食加工廠都屬于同一個主管單位)。第三章習(xí)題解答表3-35食品廠面粉廠123產(chǎn)量Ⅰ310220Ⅱ411830Ⅲ811420銷量152520第三章習(xí)題解答第三章習(xí)題解答習(xí)題3.10的解答食品廠面粉廠1234產(chǎn)量Ⅰ31020

2020Ⅱ15

45

11810

030Ⅲ820

114020銷量152520103.11

表3-36示出一個運(yùn)輸問題及它的一個解：表3-36銷地產(chǎn)地B1B2B3B4產(chǎn)量A145

13

468A28

12

62

110A3173

51

14銷量856322第三章習(xí)題解答試問：表中給出的解是否為最優(yōu)解？請用位勢法進(jìn)行檢驗。答：是最優(yōu)解。如價值系數(shù)c24由1變?yōu)?，所給的解是否仍為最優(yōu)解？若不是，請求出最優(yōu)解。答：原來的解不是最優(yōu)解。新的最優(yōu)解是：x12=3,x13=5,x21=8,x22=2,x33=1,x34=3，其他變量為0

。若所有價值系數(shù)均增加1，最優(yōu)解是否改變？為什么?答：不會改變。因為檢驗數(shù)不變。第三章習(xí)題解答第三章習(xí)題解答u1

=

-1,

u

2

=

0,

u

3

=

0,v1

=

1,

v

2

=

2,

v3

=

5,

v

4

=

1i

j最優(yōu)解是：u

,v

無約束,i

=1,2,

m

;j

=1,2,,n若所有價值系數(shù)均乘以2，最優(yōu)解是否改變？為什么?答：最優(yōu)解不變。因為檢驗數(shù)不變。寫出該運(yùn)輸問題的對偶問題，并給出其對偶問題的最優(yōu)解。解：對偶問題如下：m

nmax

Z

=

aiui

+

b

j

v

ji

=1

j

=1u

i

+

v

j

￡

cij

i

=

1,2,

m

;

j

=

1,2,

,

n3.12

1，2，3三個城市每年需分別供應(yīng)電力320，250和350單位，由I，Ⅱ兩個電站提供，它們的最大供電量分別為400個單位和450個單位，單位費(fèi)用如表3—37所示。由于需要量大于可供量，決定城市1的供應(yīng)量可減少0～30單位，城市2的供應(yīng)量不變，城市3的供應(yīng)量不能少于270單位，試求總費(fèi)用最低的分配方案(將可供電量用完)。表3-37城市電站123Ⅰ151822Ⅱ212516第三章習(xí)題解答第三章習(xí)題解答習(xí)題3.12的解答城市電站城市

1-1城市

1-2城市2城市

3-1城市

3-2產(chǎn)量Ⅰ150

1515250

182222400Ⅱ140

212125270

1640

16450ⅢM30

0MM40

070銷量2903025027080第三章習(xí)題解答3.13

試寫出本章例5轉(zhuǎn)運(yùn)問題的數(shù)學(xué)模型。解：已知a1＝10，a2＝40，a3

=a4

=a5

=0Q＝50b1=b2=b3＝0，b4＝30，b5＝20下面就是相應(yīng)的模型：MIN

Z=4

X(1,1)+

5

X(1,2)+

3X(1,3)+

2

X(1,4)+

100X(1,

5)+

5

X(2,1)+

X(2,2)+2

X(2,3)+100

X(2,4)

+

4

X(2,

5)+

3

X(3,1)+2X(3,2)+3

X(3,3)+5

X(3,

4)

+

5

X(

3,

5)+

2

X(4,1)+100X(4,2)+5

X(4,3)+

3

X(4,4)+6

X(

4,

5)+

100X(5,1)+4X(5,2)+5X(5,3)+6

X(

5,

4)

+5

X(

5,

5)第三章習(xí)題解答2]-X(1,1)+X(1,2)+X(1,3)+X(1,4)+X(1,5)=103]X(2,1)-X(2,2)+X(2,3)+X(2,4)+X(2,5)=404]X(3,1)+X(3,2)-X(3,3)+X(3,4)+X(3,5)=05]X(4,1)+X(4,2)+X(4,3)-X(4,4)+X(4,5)=06]X(5,1)+X(5,2)+X(5,3)+X(5,4)-X(5,5)=07]-X(1,1)+X