運(yùn)籌學(xué)大作業(yè)

運(yùn)籌學(xué)課程上機(jī)實(shí)踐要求及內(nèi)容（2）

一、實(shí)驗(yàn)教學(xué)的目的和要求

目的：借助運(yùn)籌學(xué)軟件的強(qiáng)大功能，通過(guò)小組的充分討論，對(duì)管理實(shí)

踐中的實(shí)際問(wèn)題進(jìn)行建模、求解，并對(duì)求解結(jié)果進(jìn)行分析（特別是敏

感性分析），進(jìn)而激發(fā)學(xué)生的學(xué)習(xí)興趣和熱情，克服對(duì)課程學(xué)習(xí)的“恐

懼感”。

要求：熟練掌握LINGO、WinQSB等軟件的基本功能和基本語(yǔ)法結(jié)構(gòu)，

能用軟件對(duì)運(yùn)籌學(xué)問(wèn)題進(jìn)行求解和分析。

二、請(qǐng)于第1次-第6次上機(jī)時(shí)間及平時(shí)完成。

三、作業(yè)務(wù)請(qǐng)寫(xiě)清學(xué)號(hào)、姓名、專業(yè)、班級(jí)，上機(jī)作業(yè)格式請(qǐng)用老

師提供的模版。

四、編寫(xiě)的代碼請(qǐng)用記事本單獨(dú)保存。

五、要求所有題目用LINGO和教材自帶的求解軟件各做一遍。并分

析解釋求解的結(jié)果。

六、各題目中的A,B,C,D,E,F為參數(shù)，除特別規(guī)定外，請(qǐng)自

行設(shè)定，各個(gè)同學(xué)參數(shù)值不能相同，若發(fā)現(xiàn)完全一致的，作業(yè)

以零分計(jì)。

A=l,B=2,C=2,D=4,E=4,F=1

第1題（線性規(guī)劃）

（1）介紹單純型算法及其處理人工變量的兩階段法；

（2）建立下列問(wèn)題的數(shù)學(xué)模型并求解，討論資源的影子價(jià)格；

某造紙廠擬生產(chǎn)漂白松木漿、包裝紙（水泥、松木包裝紙、松木本色紙）、漂

白樺木紙和膠版紙等四種產(chǎn)品，單位產(chǎn)品所需資源情況見(jiàn)表1,市場(chǎng)上膠版紙的

需求量不超過(guò)6000噸。（a）制訂該造紙廠的生產(chǎn)計(jì)劃；（b）若電的資源可用量下

降10%,重新制訂該造紙廠的生產(chǎn)計(jì)劃。

表1單位產(chǎn)品用量

產(chǎn)品漂白漂白資源

包裝紙膠版紙

所需資源松木漿樺木紙可用量

松木4.2502.4155000?

樺木1153.5102000?

水19044043044018000000?

45000000千

電9208808801340

瓦

汽7889375000噸

單位產(chǎn)品

3500384034003960

利潤(rùn)（元/噸）

⑶結(jié)合本題，談?wù)勀銓?duì)線性規(guī)劃的認(rèn)識(shí)。

Hint:若參數(shù)為5,5,5,5,5,5,則最優(yōu)目標(biāo)函數(shù)值為（a）167236800；

（6）167236800。

解：

（1）單純形法是求解線性規(guī)劃問(wèn)題的通用方法。單純形法的基本思想是：先找出

一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)

換到另一改進(jìn)的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進(jìn)行。因

基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最

優(yōu)解也可用此法判別。

兩階段單純形法也是一種人工變量法，它的算法可分為兩個(gè)階段：第一階段，引

入人工變量，構(gòu)造一個(gè)具有標(biāo)準(zhǔn)基的新線性規(guī)劃，求解這個(gè)新線性規(guī)劃，其結(jié)果

有兩種可能：或者將原問(wèn)題的約束方程組化成具有標(biāo)準(zhǔn)基的形式，或者提供信息，

表明原問(wèn)題沒(méi)有可行解。第二階段，利用第一階段所得的標(biāo)準(zhǔn)基，對(duì)原問(wèn)題求解。

(2)A、設(shè)分別生產(chǎn)漂白松木漿X1噸，包裝紙X2噸，漂白樺木紙X3噸，膠版紙

X4噸，則LP的數(shù)學(xué)模型為：maxS=3500X1+2820X2+3400X3+3990X4

約束條件為：4.2X1+5X2+2,4X4<=155000

X1+X2+5X3+3.5X4<=102000

190X1+440X2+430X3+440X4<=18000000

920X1+880X2+880X3+1340X4<=45000000

7X1+8X2+8X3+9X4<=375000

軟件計(jì)算得知，當(dāng)X1=34224.319,X2=2251.572,X3=13104,822,X4=0時(shí)，

取得最大利潤(rùn)172987547.78

B、若電的可用量降低10%,則為45000000*0.9=40500000.

利潤(rùn)最大為maxZ=3500*x1+3840*x2+3400*x3+3960*x4;

'4.2*x1+5*x2+2.2*x4<=155000;

Ix1+x2+5*x3+3.5*x4<=103000;

190*x1+440*x2+390*x3+440*x4<=18000000;

920*x1+880*x2+880*x3+1340*x4<=40500000;

7*x1+8*x2+8*x3+9*x4<=375000;

x4<=6000;

x1,x2,x3,x4>=0

,線性規(guī)劃

打開(kāi)退出

輸入

重新輸入

變量個(gè)數(shù)約束條件個(gè)數(shù)目標(biāo)函數(shù)

目標(biāo)函數(shù)flXl果給出

價(jià)值系數(shù)C

約束條件目標(biāo)函數(shù)量?jī)?yōu)值為：167669569.52

變量最憂解相差值

xl5770.914

x226152.433

x313837.067

x41123.68

約束松弛/剩余變量對(duì)偶價(jià)格

71.67

1891.320

1.633

3.14

14687.609

變量

正I負(fù)I無(wú)目標(biāo)函數(shù)系數(shù)范圍：

一變量=下限當(dāng)前值上限

xl1840.47435003924.145

x23412.52638406030.647

x32209714

甯數(shù)項(xiàng)數(shù)范圍無(wú)下限39605083.68

約束下限當(dāng)前值上限

il152730.575155000221553.03

軟件計(jì)算得知，

A、**********************最優(yōu)解文口下*************************

寓函數(shù)最優(yōu)值為:172987547.78

又里最優(yōu)解相差值

o

xl34224.319o

x22251.572O

x313104.822

x40

約束松弛族1」余變量

0479.245

0489.057

4871614.2560

01.085

12578.6160

且標(biāo)函數(shù)系數(shù)范圍

工里卞限當(dāng)前值上限

xl3359.38735003924.145

x23348.38738404037.143

x32720.0434008575

x4無(wú)下限3960

常遨項(xiàng)數(shù)范圍：4315.66

約束下限當(dāng)前值上限

152690.323155000165000

99675.325102000110000

13128385.74418000000無(wú)上限

41154306.9924500000045409142.857

362421.384375000無(wú)上限

B、**********************最優(yōu)解文口下*************************

目標(biāo)函數(shù)最優(yōu)值為:167669569.52

又里最優(yōu)解相差值

X15770.9140

x226152.4330

x313837.0670

x401123.68

約束松弛俅I余變量對(duì)偶價(jià)格

1071.67

21891.32

301.633

403.14

514687.609

60

目標(biāo)函數(shù)系數(shù)范圍

亦叁卞限

又里當(dāng)前值上限

X11840.47435003924.145

x23412.52638406030.647

x32209714

x4無(wú)下限39605083.68

常數(shù)項(xiàng)數(shù)范圍:

下限當(dāng)前值上限

1152730.575155000221553.03

2101108.68103000無(wú)上限

39913690.4761800000018566404.612

437117948.7184050000040950104.123

5360312.391375000無(wú)上限

600無(wú)上限

當(dāng)X1=5770.914,X2=26152.433,X3=13837.067,X4=0時(shí)，獲得最大利潤(rùn)

167669569.52o

（3）在線性規(guī)劃的實(shí)際應(yīng)用中，要明確LP問(wèn)題的類型，然后套用數(shù)學(xué)模型。

由于某種原因，有時(shí)線性規(guī)劃的目標(biāo)函數(shù)的系數(shù)和約束條件的常數(shù)不是固定的，

不同情況出現(xiàn)的概率不同，這些參數(shù)與概率聯(lián)系在一起，這是我們所關(guān)心的不同

經(jīng)濟(jì)狀況下的最優(yōu)方案。

第2題（線性規(guī)劃）

（1）介紹單純型算法及其處理人工變量的大M法；

（2）某廠在今后六個(gè)月內(nèi)需租用倉(cāng)庫(kù)堆存物資，各月所需倉(cāng)庫(kù)面積及租用單

價(jià)見(jiàn)下表，租借合同每月初可辦理，問(wèn)如何簽約使租借費(fèi)用最?。浚╝）試把這個(gè)

問(wèn)題表示成一個(gè)LP模型；（b）求該問(wèn)題的解。

表2A各月所需倉(cāng)庫(kù)面積____________________________________________

月份123456

更用面積（平方21。120520440340610

表2B租用單價(jià)_________________________________________________________

合同租用期限123456―

租用單價(jià)(元/平方

米)100195285370450525

⑶結(jié)合本題，談?wù)勀銓?duì)線性規(guī)劃的認(rèn)識(shí)。

Hint:若參數(shù)為5,5,5,5,5,5,則最優(yōu)目標(biāo)函數(shù)值為222250。

解：設(shè)刈表示為第I個(gè)月簽訂了為期為就個(gè)月的租用合同，i=1,2,3,4,5,

6;j=1,2,3,4,5,6

(1)建模：大M法就是在目標(biāo)函數(shù)中加上一個(gè)懲罰因素M作為人工變量的系

數(shù)，其值可以無(wú)窮大，迭代的目標(biāo)就是要去掉目標(biāo)函數(shù)中的大M,否則由于-M

充分地小，目標(biāo)函數(shù)就無(wú)法達(dá)到最優(yōu)。

(2)設(shè)租用情況如下表

123456

合同租用期限

1X11X21X31X41X51X61

2X12X22X32X42X52

3X13X23X33X43

4X14X24X34

5X15X25

6X16

minS=100(X11+X21+X31+X41+X51+X61)+195(X12+X22+X32+X42+X52)

+285(X13+X23+X33+X43)+370(X14+X24+X34)+450(X15+X25)+525X16

S.T.X11+X21+X31+X41+X51+X61>=210

X12+X22+X32+X42+X5>=120

X13+X23+X33+X43>=520

X14+X24+X34>=440

X15+X25>=340

X16>=610

**********************^p*d^]^角聿交口―1*^**************************

旦標(biāo)函數(shù)取優(yōu)值為：451300

變量最優(yōu)解相差值

114o0

200

300

400

500

600

728O0

000

000

9

1000

1100

12190

1300

1400

1500

16290

1700

1800

192O0

2000

2250

^

也

2^集

T?T^—TT里-S-

1O

2O-100

3O-195

4O-285

5O-370

6O-450

-525

具整函數(shù)系數(shù)范圍：

p艮

當(dāng)前值上限

1OO100Hk

A±9

x6A195f

vx5

x7d95195t

x8AxFkp

I95195T艮

XXkj

無(wú)

x901951957艮

二J

9無(wú)

115195二07

202855艮

28無(wú)

3285285艮

-

無(wú)

4285285T艮

-r-J

2528無(wú)

585--Jt

-l

60370o艮

上

37無(wú)

737o370T艮

l-J

337上

87o0無(wú)

90450or

0445k

5O045無(wú):R

二mM

525—

無(wú)

二MRL-

x21—\

曜項(xiàng)數(shù)范圍:

當(dāng)

前值

上

艮

艮

下a

Rp

Dt

—

上

i靈

1O14Oos

上

2O28O靈

上

3O19O靈

上

4O29O靈

靈

5O20O上

靈

OO上t

625>rs

(3)在企業(yè)的各項(xiàng)管理活動(dòng)中，例如計(jì)劃、生產(chǎn)、運(yùn)輸、技術(shù)等問(wèn)題，如何做到

最少的人力物力資源去完成一個(gè)任務(wù)，線性規(guī)劃是指從各種限制條件的組合中,

選擇出最為合理的計(jì)算方法，建立線性規(guī)劃模型從而求得最佳結(jié)果，有時(shí)要引入

人H變量，用大M法或兩階段法進(jìn)行求解。

第3題(對(duì)偶線性規(guī)劃)

(1)介紹對(duì)偶理論及對(duì)偶單純型算法；

(2)一家賓館，每天需要的服務(wù)員人數(shù)如表3所示：

表3不同時(shí)段需要的服務(wù)員人數(shù)_____________________

起迄時(shí)間服務(wù)員的最少人數(shù)一

0-315

3-633

6-928

9-1233

12-1538

15-1834

18-2133

21-2412

服務(wù)員由正式員工和臨時(shí)工組成，每個(gè)正式員工每天連續(xù)工作6小時(shí)，每個(gè)

臨時(shí)工每天連續(xù)工作9小時(shí)，且在時(shí)段開(kāi)始時(shí)上班，工作時(shí)正式員工數(shù)不得少于

1/4。問(wèn)題的目標(biāo)是要求滿足以上要求的最少上班人數(shù)。(a)試把這個(gè)問(wèn)題表示成

一個(gè)LP模型；(b)寫(xiě)出對(duì)偶LP；(c)求解該問(wèn)題并盡可能求出所有的解。

(3)結(jié)合本題，談?wù)勀銓?duì)對(duì)偶線性規(guī)劃的認(rèn)識(shí)。

Hint:若參數(shù)為5,5,5,5,5,5,則最優(yōu)目標(biāo)函數(shù)值為92。

解：

(1)對(duì)偶理論主要研究經(jīng)濟(jì)學(xué)中的相互確定關(guān)系，涉及到經(jīng)濟(jì)學(xué)的諸多方面。

產(chǎn)出與成本的對(duì)偶、效用與支出的對(duì)偶，是經(jīng)濟(jì)學(xué)中典型的對(duì)偶關(guān)系。經(jīng)濟(jì)系統(tǒng)

中還有許多其他這樣的對(duì)偶關(guān)系。對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)

通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。在迭代過(guò)程中始終保持基解的對(duì)偶可行

性,而使不可行性逐步消失。設(shè)原始問(wèn)題為min{cx|Ax=b,x>0},則其對(duì)偶問(wèn)題

(DualProblem)為max(yb|yA<c}o當(dāng)原始問(wèn)題的一^基解滿足最優(yōu)性條件時(shí),

其檢驗(yàn)數(shù)CBB-1A-C40。即知y=cBB-1(稱為單純形算子)為對(duì)偶問(wèn)題的可行解。

所謂滿足對(duì)偶可行性，即指其檢驗(yàn)數(shù)滿足最優(yōu)性條件。因此在保持對(duì)偶可行性的

前提下，一當(dāng)基解成為可行解時(shí)，便也就是最優(yōu)解。

(2)設(shè)各時(shí)段工作的正式員工數(shù)為xi(i=1,2,3,…8),臨時(shí)員H數(shù)為xi

(i=9,10,11...16)

要求最少上班人數(shù)，則目標(biāo)函數(shù)為

minZ=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16

x1+x8>=5

x1+x2>=11

x2+x3>=10

x3+x4>=11

x4+x5>=13

x5+x6>=12

x6+x7>=11

x7+x8>=4

x1+x8+x9+x15+x16>=15

x1+x2+x9+x10+x16>=33

x2+x3+x9+x10+x11>=28

x3+x4+x10+x11+x12>=33

x4+x5+x11+x12+x13>=38

x5+x6+x12+x13+x14>=34

x6+x7+x13+x14+x15>=33

x7+x8+x14+x15+x16>=12

x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16>=0

翁

￡I察i解決關(guān)于退出

輸入

目標(biāo)函數(shù)―112d重新輸入

變量個(gè)數(shù)!約束條件個(gè)數(shù)

目標(biāo)函數(shù)￡|X10|xu|X12|X13|X14|X15|X16

價(jià)值系數(shù)c|1：111i!11

U*

約束條件XllX12|X13X14X15|X16b

1000000133

1110000028

1211000033

1311100038

1401110034

1500111033

1600011112-1

出口回I

**********************最憂解如下*************************

變量XI|X24

正1負(fù)1無(wú)>0>0目標(biāo)函數(shù)量?jī)?yōu)值為：89

變量最憂解相差值

xl70

x270

x330

x480

x550

x670

x740

x800

xLx2,x3,x4,x5,x6,x7,x8.x900

xlO150

xll30

xl240

xl3180

xl40.5

xl540

xl640

約束松弛/剩余變量對(duì)偶價(jià)格

120

K14行10列230

30-.5

tw山如下所示:400

500V

1\**********************^^^彳^1^貪率女口"［、*************************

且標(biāo)函數(shù)最優(yōu)值為e：89

變量最優(yōu)解相差值

1

270

370

430

580

650

770

840

900

1000

11150

1230

1340

14180

150.5

1640

-巨40

5F松弛律U余變量對(duì)偶價(jià)格

120

230

305

400

500

605

700

805

90