《管理運(yùn)籌學(xué)》(第二版)課后習(xí)題參考答案解析

《管理運(yùn)籌學(xué)》(第二版)課后習(xí)題參考答案

第1章線性規(guī)劃(復(fù)習(xí)思考題)

1.什么是線性規(guī)劃？線性規(guī)劃的三要素是什么？

答：線性規(guī)劃(LinearProgramming,LP)是運(yùn)籌學(xué)中最成熟的一個(gè)分支，并且是

應(yīng)用最廣泛的一個(gè)運(yùn)籌學(xué)分支。線性規(guī)劃屬于規(guī)劃論中的靜態(tài)規(guī)劃，是一種重要的優(yōu)化

工具，能夠解決有限資源的最佳分配問題。

建立線性規(guī)劃問題要具備三要素：決策變量、約束條件、目標(biāo)函數(shù)。決策變量是決

策問題待定的量值，取值一般為非負(fù)；約束條件是指決策變量取值時(shí)受到的各種資源條

件的限制，保障決策方案的可行性；目標(biāo)函數(shù)是決策者希望實(shí)現(xiàn)的目標(biāo)，為決策變量的

線性函數(shù)表達(dá)式，有的目標(biāo)要實(shí)現(xiàn)極大值，有的則要求極小值。

2.求解線性規(guī)劃問題時(shí)可能出現(xiàn)幾種結(jié)果，哪種結(jié)果說明建模時(shí)有錯(cuò)誤？

答：(1)唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)：

(2)多重最優(yōu)解：無窮多個(gè)最優(yōu)解；

(3)無界解：可行域無界，目標(biāo)值無限增大；

(4)沒有可行解：線性規(guī)劃問題的可行域是空集。

當(dāng)無界解和沒有可行解時(shí)，可能是建模時(shí)有錯(cuò)。

3.什么是線性規(guī)劃的標(biāo)準(zhǔn)型？松弛變量和剩余變量的管理含義是什么？

答：線性規(guī)劃的標(biāo)準(zhǔn)型是：目標(biāo)函數(shù)極大化，約束條件為等式，右端常數(shù)項(xiàng)&NO,

決策變量滿足非負(fù)性。

如果加入的這個(gè)非負(fù)變量取值為非零的話，則說明該約束限定沒有約束力，對(duì)企業(yè)

來說不是緊缺資源，所以稱為松弛變量；剩余變量取值為非零的話，則說明“2”型約

束的左邊取值大于右邊規(guī)劃值，出現(xiàn)剩余量。

4.試述線性規(guī)劃問題的可行解、基礎(chǔ)解、基可行解、最優(yōu)解的概念及其相互關(guān)系。

答：可行解：滿足約豪條件4X=。，XNO的解，稱為可行解。

基可行解：滿足非負(fù)性約束的基解，稱為基可行解。

可行基：對(duì)應(yīng)于基可行解的基，稱為可行基。

最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。

最優(yōu)基：最優(yōu)解對(duì)應(yīng)的基矩陣，稱為最優(yōu)基。

它們的相互關(guān)系如右圖所示：

基可行解

5.用表格單純形法求解如下線性規(guī)劃。

maxZ=4X|+工2+2x3

8X]+3X2+x3<2

S.t.<6%]+x2+x3<8

再，-2，％3NO

解：標(biāo)準(zhǔn)化maxZ=4xt+x2+2x3

82+3X2++X4=2

卜匕

s.t.?6X]+x2+x3=8

用，12，當(dāng)，匕，占>0

列出單純形表

Cj41200

cBXBb再五2工3%%

0匕2[8]31102/8

08611018/6

J41200

41/413/8[1/8]1/80(1/4)/(1/8)

0%13/26—5/41/4-3/41(13/2)/(1/4)

0-1/23/2-1/20

2X3283110

0XS6-2-20-11

%-12—50-20

故最優(yōu)解為X*=（00,2,0,6）"即k=0,々=。,超=2,此時(shí)最優(yōu)值為Z（X*）=4.

6.表1—15中給出了求極大化問題的單純形表，問表中q,外，G，C2，d為何值及變

量屬于哪一類型時(shí)有：（1）表中解為唯一最優(yōu)解；（2）表中解為無窮多最優(yōu)解之一；（3）

下一步迭代將以再代替基變量與；(4)該線性規(guī)劃問題具有無界解；(5)該線性規(guī)劃問

題無可行解。

表1—15某極大化問題的單純形表

cic*2o00

A

0r

CBXRb再X2XyX4X5

0X3d4100

0“42-1-5010

0當(dāng)3ci2-3001

%c2000

解：(1)d>(),<?!<(),c2<0;

(2)d<0,c2<0(q,C2中至少有一個(gè)為零)；

(3)c.>0,t7,>0,—>—;

■4出

(4)c2>(),?,<0;

(5)為為人工變量，且c［為也含的的大于零的數(shù)，—;或者為人工變量,

4%

且c2為包含"的大于零的數(shù)，r/,>0,6/>0.

7.用大加法求解如下線性規(guī)劃。

maxZ=5』+3x2+6JT3

X1+2X2+x3<18

2Xj+廠+3X<16

s.t.-3

X1+x2+A3=10

和々，工3N()

解：加入人工變量，進(jìn)行人造基后的數(shù)學(xué)模型如下：

maxZ=53+3x2+6x3+0x4+0x5-

8.A,B,C三個(gè)城市早年需分別供應(yīng)電力320,250和350單位，由I,II兩個(gè)電

站提供，它們的最大可供電量分別為400單位和450單位，單位費(fèi)用如表1—16所示。

由于需要量大于可供量，決定城市A的供應(yīng)量可減少0?30單位，城市B的供應(yīng)量不變,

城市C的供應(yīng)量不能少于270單位。試建立線性規(guī)劃模型，求將可供電量用完的最低總

費(fèi)用分配方案。

表1—16單位電力輸電費(fèi)(單位：元)

ABC

1151822

//212516

解：設(shè).%為“第/電站向第/城市分配的電量”"=1,2；戶1,2,3),建立模型如下:

maxZ=15XN+18xl2+22x13+21x2l+25x22+16x23

人11十百2十人13=400

x21+x22+x23=450

xl}+x2l>290

+x21<32()

x]2+x22=250

x13+x23>270

尤]3+423<350

/NO,i=1,2;/=123

9.某公司在3年的計(jì)劃期內(nèi)，有4個(gè)建設(shè)項(xiàng)目可以投資：項(xiàng)目I從第一且到第三

年年初都可以投資。預(yù)計(jì)每年年初投資，年末可收回本利120%,每年又可以重新將所獲

本利納入投資計(jì)劃；項(xiàng)目II需要在第一年初投資，經(jīng)過兩年可收回本利150席,又可以

重新將所獲本利納入投資計(jì)劃，但用于該項(xiàng)目的最大投資不得超過20萬元；項(xiàng)目III

需要在第二年年初投資，經(jīng)過兩年可收回本利160樂但用于該項(xiàng)目的最大投資不得超過

15萬元；項(xiàng)目IV需要在第三年年初投資，年末可收回本利140%,但用于該項(xiàng)目的最大

投資不得超過10萬元。在這個(gè)計(jì)劃期內(nèi)，該公司第一年可供投資的資金有30萬元。問

怎樣的投資方案，才能使該公司在這個(gè)計(jì)劃期獲得最大利泗？

解：設(shè)王⑴表示第一次投資項(xiàng)目/,設(shè)兀⑵表示第二次投資項(xiàng)目/,設(shè)王⑶表示第三

次投資項(xiàng)目/,(7=1,2,3,4),則建立的線性規(guī)劃模型為

maxZ=1.2X；3>+1.6^0+1.4工;

西⑴+省<3（）

不⑵+引）41.2x9+30-王⑴一引）

短）+引）=1.2幸+1.5對(duì)）+1.2M⑴+30-染-引）-率_檔）

<20

<15

<10

引）力2）,姬皿=1,2,3,4

通過LINGO軟件計(jì)算得：邸）=10，E"=20,"）=0,6，=12,靖）二利.

10.某家具制造廠生產(chǎn)五種不同規(guī)格的家具。每種家具都要經(jīng)過機(jī)械成型、打磨、

上漆幾道重要工序。每種家具的每道工序所用的時(shí)間、每道工序的可用時(shí)間、每種家具

的利洞由表1一17給出。問工廠應(yīng)如何安排生產(chǎn)，使總利洞最大？

表1—17家具生產(chǎn)工藝耗時(shí)和利潤(rùn)表

所需時(shí)間（小時(shí)）每道工序可用

生產(chǎn)工序

12345時(shí)間（小時(shí)）

成型346233600

打磨435643950

上漆233432800

利潤(rùn)（百元）2.734.52.53

解：設(shè)%表示第/種規(guī)格的家具的生產(chǎn)量（/=1,2,…,5）,則

maxZ=2.7.V,+3x2+4.5,q+2.5x4+3x5

XX

3X]+42+6與+24+3X5<3600

4X[+3K2+5X3+6匕+4X5<3950

XXX

2X1+3X2+33+44+35<2800

X：N0,i=l,2,…,5

通過LINGO軟件計(jì)算得：.v,=0,x2=38,X3=254,X4=0,X5=642,Z=3181.

11.某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，分別經(jīng)過A,B,C三種設(shè)備加工。已知生產(chǎn)單

位產(chǎn)品所需的設(shè)備臺(tái)時(shí)數(shù)、設(shè)備的現(xiàn)有加工能力及每件產(chǎn)品的利潤(rùn)如表2—10所示。

表1—18產(chǎn)品生產(chǎn)工藝消耗系數(shù)

甲乙丙設(shè)備能力

A（小時(shí)）111100

B（小時(shí)）1045600

c(小時(shí))226300

單位產(chǎn)品利泗(元)1064

(1)建立線性規(guī)劃模型，求該廠獲利最大的生產(chǎn)計(jì)劃。

(2)產(chǎn)品丙每件的利潤(rùn)增加到多大時(shí)才值得安排生產(chǎn)？如產(chǎn)品丙每件的利潤(rùn)增加

到6,求最優(yōu)生產(chǎn)計(jì)劃。

(3)產(chǎn)品甲的利潤(rùn)在多大范圍內(nèi)變化時(shí)，原最優(yōu)計(jì)劃保持不變？

設(shè)備A的能力如為100+10g,確定保持原最優(yōu)基不變的q的變化范圍。

(5)如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，試確定最優(yōu)計(jì)劃的變化。

解：(1)設(shè)內(nèi),々，當(dāng)分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型

maxZ=1()X[+6x2+4x3

X14-x2+x3<100

Jl()$+4X2+5X3<600

2X1+2X2+6X3<300

xrx2,x3>0

標(biāo)準(zhǔn)化得

maxZ=10.+6X2+4x3+0x4+Ox5+0x6

xI-I-x2+x3+x4=100

10x(+4X+5X+x=600

s.t.235

2X]+2X2+6X3+x6=300

列出單純形表

1064000

仇

CBXBb￡當(dāng)%%

0匕100111100100

0公600[10]4501060

0工6300226001150

1064000

0400[3/5]1/210200/3

1/10

106012/51/201/100150

018006/550—1/51150

Oj02-10-10

6%200/3015/65/3—1/60

10再100/3101/6-2/31/60

046100004-201

%00-10/3-2/30

8/3

故最優(yōu)解為F=100/3,%=200/3,當(dāng)二0,又由于七,占，工3取整數(shù)，故四舍五人可得

最優(yōu)解為項(xiàng)=33,為=67,再=°，2max=732.

(2)產(chǎn)品丙的利潤(rùn)q變化的單純形法迭代表如下：

106Q000

%

b陽工2/%/

6x2200/3015/65/3—1/60

10占100/3101/6-2/31/60

0%100004-201

6一

%00-10/3-2/30

20/3

要使原最優(yōu)計(jì)劃保持不變，只要。3=。3一手《0,即。3?6；=6.67.故當(dāng)產(chǎn)品丙每

件的利潤(rùn)增加到大于6.67時(shí)，才值得安排生產(chǎn)。

如產(chǎn)品丙每件的利泗增加到6時(shí)，此時(shí)6<6.67,故原最優(yōu)計(jì)劃不變。

(3)由最末單純形表計(jì)算出

I21

/=-1——G00,巴=-10+—G<0,6=1——q<0,

636

解得<15,即當(dāng)產(chǎn)品甲的利潤(rùn)q在［6,15］范圍內(nèi)變化時(shí)，原最優(yōu)計(jì)劃保持不變。

‘5/3-1/60、

(4)由最末單純形表找出最優(yōu)基的逆為=-2/31/60,新的最優(yōu)解為

「201,

'5/3-1/60、。()0十1(靖(200+50(7、

X；=B/=-2/31/606001100-204>0

-3

「20*<300,3(100—200

解得-4?q?5,故要保持原最優(yōu)基不變的g的變化范圍為[-4,5].

(5)如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，則線性規(guī)劃模型變成

maxZ=10芭+6x2+4x3

X[+x2+x3<100

1+4JT2+5犬3<600

<2x}4-2X2+6X3<300

x3>10

xpx2,x3>0

通過LINGO軟件計(jì)算得到：再=32,巧=58，i=1°，Z=708.

第2章對(duì)偶規(guī)劃(復(fù)習(xí)思考題)

1.對(duì)偶問題和對(duì)偶向量(即影子價(jià)值)的經(jīng)濟(jì)意義是什么？

答：原問題和對(duì)偶問題從不同的角度來分析同一個(gè)問題，前者從產(chǎn)品產(chǎn)量的角度來

考察利潤(rùn)，后者則從形成產(chǎn)品本身所需要的各種資源的角度來考察利潤(rùn)，即利澗是產(chǎn)品

生產(chǎn)帶來的，同時(shí)又是資源消耗帶來的。

對(duì)偶變量的值X表示第，種資源的邊際價(jià)值，稱為影子價(jià)值?？梢园褜?duì)偶問題的解

Y定義為每增加一個(gè)單位的資源引起的目標(biāo)函數(shù)值的增量。

2.什么是資源的影子價(jià)格？它與相應(yīng)的市場(chǎng)價(jià)格有什么區(qū)別？

答：若以產(chǎn)值為目標(biāo)，則)"是增加單位資源/對(duì)產(chǎn)值的貢獻(xiàn)，稱為資源的影子價(jià)格

(ShadowPrice)o即有“影子價(jià)格=資源成本+影子利潤(rùn)”。因?yàn)樗⒉皇琴Y源的實(shí)際價(jià)

格，而是企業(yè)內(nèi)部資源的配比價(jià)格，是由企業(yè)內(nèi)部資源的配黃狀況來決定的，并不是由

市場(chǎng)來決定，所以叫影子價(jià)格?？梢詫①Y源的市場(chǎng)價(jià)格與影子價(jià)格進(jìn)行比較，當(dāng)市場(chǎng)價(jià)

格小于影子價(jià)格時(shí)，企業(yè)可以購進(jìn)相應(yīng)資源，儲(chǔ)備或者投入生產(chǎn)；當(dāng)市場(chǎng)價(jià)格大于影子

價(jià)格時(shí)，企業(yè)可以考慮暫不購進(jìn)資源，減少不必要的損失。

3.如何根據(jù)原問題和對(duì)偶問題之間的對(duì)應(yīng)關(guān)系，找出兩個(gè)問題變量之間、解及檢

臉數(shù)之間的關(guān)系？

答：(1)最優(yōu)性定理：設(shè)元F分別為原問題和對(duì)偶問題的可行解，且c又=

則RF分別為各自的最優(yōu)解。

(2)對(duì)偶性定理：若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解，而且兩者的目

標(biāo)函數(shù)值相等。

(3)互補(bǔ)松弛性：原問題和對(duì)偶問題的松弛變量為x$和八，它們的可行解x",y"

a

為最優(yōu)解的充分必要條件是Lx、=o,rs.x=o.

(4)對(duì)偶問題的最優(yōu)解對(duì)應(yīng)于原問題最優(yōu)單純形表中，初始基變量的檢驗(yàn)數(shù)的負(fù)

值。若-匕對(duì)應(yīng)于原問題決策變量〉的檢臉數(shù)，則-y對(duì)應(yīng)于原問題松弛變量看的檢臉

數(shù)。

4.已知線性規(guī)劃問題

maxZ=4X[+x2+2匕

8巧+3X2+x5<2(第一'種資源)

s.t.<6X]+x2+<8(第二種資源)

x,,x2,x3>0

(1)求出該問題產(chǎn)值最大的最優(yōu)解和最優(yōu)值。

(2)求出該問題的對(duì)偶問題的最優(yōu)解和最優(yōu)值c

(3)給出兩種資源的影子價(jià)格，并說明其經(jīng)濟(jì)含義；第一種資源限量由2變?yōu)?,

最優(yōu)解是否改變？

(4)代加工產(chǎn)品丁，每單位產(chǎn)品需消耗第一種資源2單位，消耗第二種資源3單

位，應(yīng)該如何定價(jià)？

解：(1)標(biāo)準(zhǔn)化，并列出初始單純形表

Cj41200<9,

b

xB修々%%與

0之42[8]31102/8

08611018/6

41200

4%1/413/8[1/8]1/802

013/26—5/41/4-3/4126

%0-1/23/2-1/20

2283110

0%6-2-20-11

-12-50-20

由最末單純性表可知，該問題的最優(yōu)解為：X*=(0,0,2。6)/，即玉=0,x2=0,x3=2,

最優(yōu)值為Z=4.

(2)由原問題的最末單純形表可知，對(duì)偶問題的最優(yōu)解和最優(yōu)值為：

必=2,%=0,卬=4?

(3)兩種資源的影子價(jià)格分別為2、0,表示對(duì)產(chǎn)值貢獻(xiàn)的大小；第一種資源限量

由2變?yōu)?,最優(yōu)解不會(huì)改變。

(4)代加工產(chǎn)品丁的價(jià)格不低于2x2+0x3=4.

5.某廠生產(chǎn)A,B,C,D4種產(chǎn)品，有關(guān)資料如表2—6所示。

表2—6

源消耗產(chǎn)品資源供應(yīng)量原料成本

資源ABCD(公斤)(元/公斤)

甲23128002.0

乙543412001.0

丙345310001.5

華住產(chǎn)品售價(jià)(.元)14.52115.516.5

(1)請(qǐng)構(gòu)造使該廠獲利潤(rùn)最大的線性規(guī)劃模型，并用單純形法求解該問題(不計(jì)

加工成本)。

(2)該廠若出租資源給另一個(gè)工廠，構(gòu)成原問題的對(duì)偶問題，列出對(duì)偶問題的數(shù)

學(xué)模型，資源甲、乙、丙的影子價(jià)格是多少？若工廠可在市場(chǎng)上買到原料丙，工廠是否

應(yīng)該購進(jìn)該原料以擴(kuò)大生產(chǎn)？

(3)原料丙可利用量在多大范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變

(即最優(yōu)基不變)？

(4)若產(chǎn)品B的價(jià)格下降了0.5元，生產(chǎn)計(jì)劃是否需要調(diào)整？

解：(1)設(shè)網(wǎng),々，工3，大4分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型

maxZ=+5xz+3x4+4JV4

2X14-3X2+/+2X4<800

5X[+4X2+3xy+4X4<1200

3X1+4X2+5X3+3X4<1000

x；NO"=1,2,3,4

初始單純形表

%1534000

%A

gX"b%x2/馬

0%8002312100800/3

0工6120054340101200/4

010003[4]530011000/4

%1534000

最末單純形表

1534000

%A

CBXBb匹工3相丸4匕

01001/40-13/4011/4-1

420020-2101-1

5x2100-3/4111/400-3/41

%-13/40-11/400-1/4-1

解得最優(yōu)解為：X*=(0,100,0,200,100)r,最優(yōu)值Z=1300.

(2)原問題的對(duì)偶問題的數(shù)學(xué)模型為

min卬=800%+1200%+1000%

2M+5%+3%21

3必+4%+4)，3之5

s.t.<M+3乂+5)4-1

2凹+4h+3"4

.)22，3心。

解得影子價(jià)格分別為2,1.25、2.5。對(duì)比市場(chǎng)價(jià)格和影子價(jià)格，當(dāng)市場(chǎng)價(jià)低于影子

價(jià)格時(shí)購進(jìn)。

(3)原料丙可利用量在［900,1100］范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品

種不變(即最優(yōu)基不變)。

(4)若產(chǎn)品B的價(jià)格下降了0.5元，生產(chǎn)計(jì)劃不需要調(diào)整。

6.某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)品生產(chǎn)的工藝路線如圖2—1所示，試統(tǒng)計(jì)單位

產(chǎn)品的設(shè)備工時(shí)消耗，填入表2—7。又已知材料、設(shè)備C和設(shè)備D等資源的單位成本和

擁有量如表2—7所示。

表2—7資源消耗與資源成本表

產(chǎn)品資源消耗資源成本

資源擁有量

資源甲乙元/單住資源

材料(公斤)60502004200

設(shè)備C(小時(shí))3040103000

設(shè)備D(小時(shí))6050204500

據(jù)市場(chǎng)分析，甲、乙產(chǎn)品銷售價(jià)格分別為13700元和11640元，試確定獲利最大的

產(chǎn)品生產(chǎn)計(jì)劃。

(1)設(shè)產(chǎn)品甲的計(jì)劃生產(chǎn)量為用，產(chǎn)品乙的計(jì)劃生產(chǎn)量為它,試建立其線性規(guī)劃

的數(shù)學(xué)模型；若將材料約束加上松弛變量與，設(shè)備c約束加上松弛變量乙，設(shè)備D約束

加上松弛變量與，試化成標(biāo)準(zhǔn)型。

(2)利用LINDO軟件求得：最優(yōu)目標(biāo)函數(shù)值為18400,變量的最優(yōu)取值分別為

Xl=20,x2=60,x3=0,x4=0,x5=300,則產(chǎn)品的最優(yōu)生產(chǎn)計(jì)劃方案是什么？并解釋

巧=0,x4=0,x5=300的經(jīng)濟(jì)意義。

(3)利用LINDO軟件對(duì)價(jià)值系數(shù)進(jìn)行敏感性分析，結(jié)果如下：

ObjCoefficientRanges

CurrentAlIowabIe

VariabIeAllowableDecrease

CoefIncrease

再2008820

x224026.6773.33

試問如果生產(chǎn)計(jì)劃執(zhí)行過程中，甲產(chǎn)品售價(jià)上升到13800元，或者乙產(chǎn)品售價(jià)降低

60元，所制定的生產(chǎn)計(jì)劃是否需要進(jìn)行調(diào)整？

(4)利用LINDO軟件對(duì)資源向量進(jìn)行敏感性分析，結(jié)果如下：

RighthandSideRanges

AIIowabIeAIIowabIe

ResourceCurrentRhs

IncreaseDecrease

材料4200300450

設(shè)備C3000360900

設(shè)備D4500Infinity300

試問非緊缺資源最多可以減少到多少，而緊缺資源最多可以增加到多少？

解：(1)建立的線性規(guī)劃模型為

maxZ=200x,+240x2

60A：1I50X2V4200

30x.+40占<3000

s.t.

60xj+50X2<4500

XpX,>0

將其標(biāo)準(zhǔn)化

maxZ=200x,+240x2

60a+50X2+x?=4200

30x,+40X2+X4=3000

60X1+50X2+X5=4500

xi>0J=1,2,…,5

(2)甲生產(chǎn)20件，乙生產(chǎn)60件，材料和設(shè)備C充分利用，設(shè)備D剩余600單位。

(3)甲上升到13800需要調(diào)整，乙下降60不用調(diào)整。

(4)非緊缺資源設(shè)備D最多可以減少到300,而緊缺資源一材料最多可以增加到

300,緊缺資源一設(shè)備C最多可以增加到360。

第3章整數(shù)規(guī)劃(復(fù)習(xí)思考題)

1.整數(shù)規(guī)劃的類型有哪些？

答：純整數(shù)規(guī)劃、07規(guī)劃和混合整數(shù)規(guī)劃。

2.試述整數(shù)規(guī)劃分枝定界法的思路。

答：(1)首先不考慮整數(shù)條件，求解整數(shù)規(guī)劃相應(yīng)的線性規(guī)劃問題。若相應(yīng)的線性

規(guī)劃問題沒有可行解，停止計(jì)算，這時(shí)原整數(shù)規(guī)劃也沒有可行解。

(2)定界過程。對(duì)于極大化的整數(shù)規(guī)劃問題，當(dāng)前所有未分枝子問題中最大的目

標(biāo)函數(shù)值為整數(shù)規(guī)劃問題上界；在滿足整數(shù)約束的子問題的解中，最大的目標(biāo)函數(shù)值為

整數(shù)規(guī)劃問題的下界。當(dāng)上下界相同時(shí)，則已得最優(yōu)解；否則，轉(zhuǎn)入剪枝過程C

(3)剪枝過程。在下述情況下剪除這些分枝：①若某一子問題相應(yīng)的線性規(guī)劃問

題無可行解；②在分枝過程中，求解某一線性規(guī)劃所得到的目標(biāo)函數(shù)值Z不優(yōu)于現(xiàn)有下

界。

(4)分枝過程。當(dāng)有多個(gè)待求分枝時(shí)，應(yīng)先選取目標(biāo)函數(shù)值最優(yōu)的分枝繼續(xù)進(jìn)行

分枝。選取一個(gè)不符合整數(shù)條件的變量看作為分枝變量，若毛的值是〃：，構(gòu)造兩個(gè)新的

約束條件：>[/?；]+1,分別并入相應(yīng)的數(shù)學(xué)模型中，構(gòu)成兩個(gè)子問題。對(duì)

任一個(gè)子問題，轉(zhuǎn)步驟(1).

3.試用分枝定界法求如下線性規(guī)劃:

maxZ=40+90x2

9玉+7X2<56

七7x1+20x2<70

xpx2>0

XpX,取整數(shù)

解：

最優(yōu)整數(shù)解為：八=4,"胡二弘0.上界:

理>2=1生,=355型_0“I

4.有4名職工妁齦不屬說蠢個(gè)人做$演工器所用的時(shí)間不同，所花

甲15182124

乙19232218

丙26171619

丁19212317

問指派哪個(gè)人去完成哪項(xiàng)工作，可使總的消耗時(shí)間最少？

1,任務(wù)，由人員;完成

解：設(shè)馬=%為個(gè)人/.對(duì)于任務(wù)/的時(shí)間耗費(fèi)矩陣,

0,任務(wù)i不由人員;完成

則建立整數(shù)規(guī)劃模型為:

minZ=

i=lJ=l

力“1

r=l

,ixu=1

j=i

勺=0或山=123,4

解得：x12=l,x21=1,J33=l,x44=h其余均為零，Z=7(),即任務(wù)A由乙完成，任

務(wù)B由甲完成，任務(wù)C由丙完成，任務(wù)D由丁完成。

5.某部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五

至少需要80人，周六周日每天至少需要90人，先規(guī)定應(yīng)聘者需連續(xù)工作5天，試確定

聘用方案，即周一到周日每天聘用多少人，使在滿足需要的條件下聘用總?cè)藬?shù)最少。

解：設(shè)x,表示在第7天應(yīng)聘的展員人數(shù)(/=1,2,3,4,5,6,7)。數(shù)學(xué)模型為

niinZ=X)+x2++x4+x5+x6+x7

+X44-X5+X6+X7>50

陽+x2+x5+x6+x7>50

X]+/+戈3+工6+X7>50

*+七+13+Z+X7>5()

S.t.,>80

x2+x3+x4+x5+x6>90

x3+x4+x5+x6+x7>90

巧N0,i=l,2，…,7

再取整數(shù),i=1,2,…,7

解得：X]=0,x2-4,X3=32,七=10,x5=34,x6=10,x7=4,Z=94.

第4章目標(biāo)規(guī)劃（復(fù)習(xí)思考題）

1.某計(jì)算機(jī)公司生產(chǎn)A,B,C三種型號(hào)的筆記本電腦。這三種筆記本電腦需要在

復(fù)雜的裝配線上生產(chǎn)，生產(chǎn)一臺(tái)A,B,C型號(hào)的筆記本電腦分別需要5小時(shí)、8小時(shí)、

12小時(shí)。公司裝配線正常的生產(chǎn)時(shí)間是每月1700小時(shí)，公司營業(yè)部門估計(jì)A,B,C三

種筆記本電腦每臺(tái)的利潤(rùn)分別是1000元、1440元、2520元，而且公司預(yù)測(cè)這個(gè)月生產(chǎn)

的筆記本電腦能夠全部售出。公司經(jīng)理考慮以下目標(biāo)：

第一目標(biāo)：充分利用正常的生產(chǎn)能力，避免開工不足；

第二目標(biāo)：優(yōu)先滿足老客服的需求，A,B,C三種型號(hào)的電腦各為50臺(tái)、50臺(tái)、

80臺(tái)，同時(shí)根據(jù)三種電腦三種電,腦的純利潤(rùn)分配不同的加權(quán)系數(shù)；

第三目標(biāo)：限制裝配線加班時(shí)間，最好不超過200小時(shí)；

第四目標(biāo)：滿足各種型號(hào)電腦的銷售目標(biāo)，A,B,C三種型號(hào)分別為100臺(tái)、120

臺(tái)、100臺(tái)，再根據(jù)三種電腦的純利潤(rùn)分配不同的加權(quán)系數(shù)；

第五目標(biāo)：裝配線加班時(shí)間盡可能少。

請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型，并用LINGO軟件求解。

解：建立目標(biāo)約束。

(1)裝配線正常生產(chǎn)

設(shè)生產(chǎn)A,B,C型號(hào)的電腦為七,它,馬(臺(tái))，4-為裝配線正常生產(chǎn)時(shí)間未利用數(shù)，

為裝配線加班時(shí)間，希望裝配線正常生產(chǎn)，避免開工不足，因此裝配線目標(biāo)約束為

min{"1}

5司+8々+12/+4--d：=1700

(2)銷售目標(biāo)

優(yōu)先滿足老客戶的需求，并根據(jù)三種電腦的純利泗分配不同的權(quán)因子，A,B,C三

種型號(hào)的電腦每小時(shí)的利潤(rùn)是幽，上曳，至2因此，老客戶的銷售目標(biāo)約束為

5812

min{20W+18d；+21d；}

+d2-=50

x2+d；-d；=50

x3+d；-d；=80

再考慮一般銷售。類似上面的討論，得到

min{201/5+I8J6+2\dj}

M+〃；一百=1°0

x2+d~-d；=120

x3+d--若=100

（3）加班限制

首先是限制裝配線加班時(shí)間，不允許超過200小時(shí)，因此得到

5為+8.￥2+12X3+-d；=1900

其次裝配線的加班時(shí)間盡可能少，即

min{d；}

5x,+8々+12/+d「-d：=1700

寫出目標(biāo)規(guī)劃的數(shù)學(xué)模型

minG=P、d:+R（20d￡+18d；+21d；）+P.d；+P式20dg+18d[+2M；）+P§d：

5M+8々+12X3+d「-d；=1700

*+d；-d；=50

%-d；=50

+d4—d；-80

…工-4=120

Xyd-j-d；=100

5方+知+12X3+d「-d：=1900

x.>0,/=l,2

“,d；NO,/=1,2,…,8

經(jīng)過LINGO軟件計(jì)算，得到修=100,%=55,曰=80,裝配線生產(chǎn)時(shí)間為1900小時(shí)，

滿足裝配線加班不超過200小時(shí)的要求。能夠滿足老客戶的需求，但未能達(dá)到銷售目標(biāo)。

銷售總利潤(rùn)為100X1000+55X1440+80X2520=380800（元）。

2.已知3個(gè)工廠生產(chǎn)的產(chǎn)品供應(yīng)給4個(gè)客戶，各工廠生產(chǎn)量、用戶需求量及從各

工廠到用戶的單位產(chǎn)品的運(yùn)輸費(fèi)用如表4—3所示。由于總生產(chǎn)量小于總需求量，上級(jí)

部門經(jīng)研究后，制定了調(diào)配方案的8個(gè)目標(biāo)，并規(guī)定了重要性的次序。

表4—3工廠產(chǎn)量一用戶需求量及運(yùn)費(fèi)單價(jià)（單位：元）

1234生產(chǎn)量

15267

23546

34523

需求量(單位)200100450250

第一目標(biāo)：用戶4為重要部門，需求量必須全部滿足；

第二目標(biāo)：供應(yīng)用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100個(gè)單位；

第三目標(biāo)：每個(gè)用戶的滿足率不低于80%；

第四目標(biāo)：應(yīng)盡量滿足各用戶的需求；

第五目標(biāo)：新方案的總運(yùn)費(fèi)不超過原運(yùn)榆問題(線性規(guī)劃模型)的調(diào)度方案的10%；

第六目標(biāo)：因道路限制，工廠2到用戶4的路線應(yīng)盡量避免運(yùn)輸任務(wù)；

第七目標(biāo)：用戶1和用戶3的