管理運(yùn)籌學(xué)計算機(jī)輔助教程

管理運(yùn)籌學(xué)計算機(jī)輔助教程

田亞明主編

石家莊經(jīng)濟(jì)學(xué)院

2008年5月

刖口

本書關(guān)注學(xué)生基本理論知識的培養(yǎng)，積極探索“重視基礎(chǔ)，拓展應(yīng)用”

的特色，力圖做到結(jié)構(gòu)清晰合理，教材體系完整，內(nèi)容豐富新穎。強(qiáng)調(diào)計

算機(jī)求解定量模型的方法，說明各種定量模型的應(yīng)用前提條件及其注意事

項；有效利用著者管理學(xué)科視角的應(yīng)用優(yōu)勢，重視定量?；纠碚?、基本

方法的實際應(yīng)用，每章都配備典型應(yīng)用案例及其案例分析，并給出計算機(jī)

求解程序，形成優(yōu)化方法，模型應(yīng)用并重的綜合性教材，注重操作的深入

淺出，語言簡練通順，使本書成為具有經(jīng)管類應(yīng)用特色的定量分析模型的

輔助性教材。

本書作為中國人民大學(xué)出版的管理運(yùn)籌學(xué)配套教材，由該書作者之一

田亞明組織石家莊經(jīng)濟(jì)學(xué)院老師完成，主要講管理運(yùn)籌學(xué)定量模型計算機(jī)

求解指導(dǎo)，以lindo/lingo在運(yùn)籌學(xué)線性規(guī)劃、目標(biāo)規(guī)劃、整數(shù)規(guī)劃、動態(tài)

規(guī)劃、網(wǎng)絡(luò)分析、網(wǎng)絡(luò)計劃、存儲分析、決策分析、隨機(jī)服務(wù)等模型的應(yīng)

用，對部分模型的求解。其中實驗項目二和十由索貴彬編寫；實驗項目三

和四由江朝力編寫；實驗項目五由武建章編寫；實驗項目六和七由聶雅編

寫；實驗項目八和九由邢延銘編寫；實驗項目一、附錄及全書統(tǒng)稿由田亞

明負(fù)責(zé)。

由于水平所限，書中存在很多不足甚至錯誤之處，歡迎讀者不吝指正。

編者

2008年5月

本書實驗總述

實驗專業(yè)：管理類專業(yè)

實驗學(xué)時：課程總學(xué)時48,其中實驗學(xué)時12

實驗數(shù)量：10

學(xué)時分配：12

實驗學(xué)時

實驗名稱頁碼

序號分配

1實驗項目一線性規(guī)劃21

實驗項目二應(yīng)用運(yùn)籌學(xué)CAI軟件求解運(yùn)輸問

2113

題

3實驗項目三目標(biāo)規(guī)劃119

4實驗項目四整數(shù)規(guī)劃126

5實驗項目五動態(tài)規(guī)劃233

6實驗項目六圖論（最短路和最大流問題）148

7實驗項目七網(wǎng)絡(luò)計劃157

8實驗項目八排隊論163

9實驗項目九存儲論176

實驗項目十應(yīng)用運(yùn)籌學(xué)CAI軟件求解多目標(biāo)

10195

決策問題

附錄：lingo使用基礎(chǔ)課外98

1實驗項目一線性規(guī)劃

實驗學(xué)時：2

實驗?zāi)康模壕€性規(guī)劃（LinearProgramming,簡寫LP）是運(yùn)籌學(xué)中最

成熟的一個分枝，而且是應(yīng)用最為廣泛的一個運(yùn)籌學(xué)分枝，是解決最優(yōu)化

問題的重要工具。而目前Lindo/lingo是求解線性規(guī)劃比較成熟的一個軟

件，通過本實驗，掌握線性規(guī)劃模型在Lindo/lingo中的求解，并能達(dá)到

靈活運(yùn)用。

實驗要求：1.掌握線性規(guī)劃的建模步驟及方法；

2.掌握Lindo/lingo的初步使用；

3.掌握線性規(guī)劃模型在Lindo/lingo建模及求解；

4.掌握線性規(guī)劃的靈敏度分析

實驗內(nèi)容及步驟：

例：美佳公司計劃制造I、n兩種家電產(chǎn)品。已知各制造■-件時分別

占用設(shè)備A、B的臺時、調(diào)試時間、調(diào)試工序每天可用于這種家電的能力、

各售出一件時的獲利情況，如表1-1所示。

產(chǎn)品單位產(chǎn)品I用量單位產(chǎn)品n用量每天可用能力

設(shè)備A0515

設(shè)備B6224

調(diào)試工序115

單位產(chǎn)品獲利21

1.問該公司應(yīng)制造兩種家電各多少件，使其獲取的利潤最大。

2.如果資源出租，資源出租的最低價格至少是多少（即每種資源的

影子價格是多少）。

3.若家電I的利潤不變，家電n的利潤在什么范圍內(nèi)變化時，則該公

司的最優(yōu)生產(chǎn)計劃將不發(fā)生變化。

1

4.若設(shè)備A和B每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)

變化時，問題的最優(yōu)基不變。

解：設(shè)玉表示產(chǎn)品I的生產(chǎn)量;它表示產(chǎn)品II的生產(chǎn)量,所在該線性規(guī)

劃的模型為：

maxz=22+x2

Ox+5々<15

6XI+2X2<24

+x2<5

xpx2>0

從此線性規(guī)劃的模型中可以看出，第一個小問是典型的生產(chǎn)計劃問

題，第二小問是相應(yīng)資源的影子價格，第三和第四個小問則是此問題的靈

敏度分析。

現(xiàn)在我們利用lingo8.0來教你求解線性規(guī)劃問題。

第一步，啟動lingo進(jìn)入初始界面如下圖1-1和圖1-2所示：

—4■A牌訊QQ

WindowsUpdate

應(yīng)1瑞星殺毒軟件?

I同金山詞霸2005?

|回Hewlett-Packard?

幽交檔①)*畫HP?

lff?|Nero?

設(shè)置⑤)>包天網(wǎng)Maze?

1過（清華同方知網(wǎng)?

/搜索?》

1麗Sn&glt7?

Q幫助和支持國)應(yīng)301PUSBCamera?

@QQ游戲?

-EJ運(yùn)行⑥…

CMicrotekScanWizard5forWindows?

1國PhotoShowDeluxe3?

|注銷Administratort)...

卜AcrobatDistiller70

回關(guān)閉計算機(jī)QI)...?'「AdobeAcrobat70Professional

QAdobeDesigner7.0

圖1-1啟動Lingo8.0

2

圖1-2Lingo8.0的初始界面

第二步，在進(jìn)行線性規(guī)劃模型求解時，先要對初始求解方法及參數(shù)要

進(jìn)行設(shè)置，首先選擇lingo菜單下的Option菜單項，并切換在generalsolver

（通用求解器）頁面下，如下圖1-3所示：

圖1-3generalsolver選項的初始設(shè)置

generalsolver選項卡上的各項設(shè)置意義如下表格1-1所示:

表格1-1generalsolver選項卡上的各項設(shè)置意義

選項組選項含義

GeneratorMemoryLimit（MB）缺省值為32M,矩陣生成器使用的內(nèi)

矩陣生成器的內(nèi)存限制（兆）存超過該限制，LINGO將報告"Themodel

3

generatorranoutofmemory*'

Iterations求解一個模型時，允許的最大迭代次數(shù)

Runtime

迭代次數(shù)（缺省值為無限）

Limits

Time（sec）求解一個模型時，允許的最大運(yùn)行時間

運(yùn)行限制運(yùn)行前間（秒）

（缺省值為無限）

求解時控制對偶計算的級別,有三種可

能的設(shè)置：

DualComputations?None:不計算任何對偶信息；

（對偶計算）?Prices：計算對偶價格（缺省設(shè)置）；

,PricesandRanges：計算對偶價格并分

析敏感性。

控制重新生成模型的頻率，有三種可能

的設(shè)置：

?Onlywhentextchanges：只有當(dāng)模型

ModelRegeneration的文本修改后才再生成模型；

（模型的重新生成）?Whentextchangesorwithexternal

references：當(dāng)模型的文本修改或模型含有

外部引用時（缺省設(shè)置）；

?Always：每當(dāng)有需要時。

決定求解模型時線性化的程度,有四種

可能的設(shè)置：

SolverDecides：若變量數(shù)小于等于12

個，則盡可能全部線性化；否則不做任何線

Degree性化（缺省設(shè)置）

（線性化程,None：不做任何線性化

度）?Low：對函數(shù)@ABS（）,@MAX（）,

Linearization

@MIN（）,@SMAX（）,@SMIN（）,以及二進(jìn)

（線性化）

制變量與連續(xù)變量的乘積項做線性化

?High：同上，此外對邏輯運(yùn)算符#LE#,

#EQ#,#GE#,#NE#做線性化

BigM（線性化設(shè)置線性化的大M系數(shù)（缺省值為

的大M系數(shù)）106）

Delta（線性化設(shè)置線性化的誤差限（缺省值為10-6）

的誤差限）

AllowUnrestrictedUseofPrimitive選擇該選項可以保持與LINGO4.0以

SetMemberNames前的版本兼容：即允許使用基本集合的成員

（允許無限制地使用基本集合的名稱直接作為該成員在該集合的索引值

成員名）（LINGO4.0以后的版本要求使用@INDEX

函數(shù)）。

CheckforDuplicateNamesinData選擇該選項,LINGO將檢查數(shù)據(jù)和模型

（檢查日據(jù)和模型中的名稱

andModel中的名稱是否重復(fù)使用，如基本集合的成員

是否重復(fù)使用）名是否與決策變量名重復(fù)。

UseR/CformatnamesforMPSI/O

在MPS文件格式的輸入輸出中，將變

（在MPS文件格式的輸入輸出中使用

量和行名轉(zhuǎn)換為R/C格式

R/C格式的名稱）

4

接下來再對LinearSolver（線性求解器）選項卡進(jìn)行設(shè)置，切換界面

如所示:

圖l-4LinearSolver選項卡的初始設(shè)置

其各項設(shè)置意義如下表格1-2所示：

表格1-2LinearSolver選項卡各項設(shè)置意義

選項組選項含義

求解時的算法，有四種可能的設(shè)置：

?SolverDecides：LINGO自動選擇算法

Method（缺省設(shè)置）

求解方法?PrimalSimplex：原始單純形法

?DualSimplex：對偶單純形法

?Barrier:障礙法（即內(nèi)點(diǎn)法）

InitialLinearFeasibilityTol初控制線性模型中約束滿足的初始誤差限

始線性可行性誤差限（缺省值為3*10"）

FinalLinearFeasibilityTol.最Ji控制線性模型中約束滿足的最后誤差限

線性可行性誤差限（缺省值為10-7）

控制是否檢查模型中的無關(guān)變量，從而

降低模型的規(guī)模：

ModelReduction?Off：不檢查

模型降維,On：檢查

?SolverDecides：LINGO自動決定（缺

省設(shè)置）

5

有三種可能的設(shè)置：

?SolverDecides：LINGO自動決定（缺

省設(shè)置）

PrimalSolver?Partial：LINGO對一部分可能的出基變

原始單純形法量進(jìn)行嘗試

,Devex：用Steepest-Edge（最陡邊）近

Pricing

似算法對所有可能的變量進(jìn)行嘗試，找到使

Strategies

價格策略目標(biāo)值下降最多的出基變量

（決定出基變有三種可能的設(shè)置：

量的策略）?SolverDecides：LINGO自動決定（缺

省設(shè)置）

DualSolver對?Dantzig：按最大下降比例法確定出基變

&

偶單純形法里

,Steepest-Edge：最陡邊策略，對所有可

能的變量進(jìn)行嘗試，找到使目標(biāo)值下降最多

的出基變量

MatrixDecomposition選擇該選項，LINGO將嘗試將一個大模

矩陣分解型分解為幾個小模型求解；否則不嘗試

選擇該選項,LINGO檢查模型中的數(shù)據(jù)

ScaleModel

是否平衡（數(shù)量級是否相差太大）并嘗試改

模型尺度的改變

變尺度使模型平衡；否則不嘗試

因為這個線性規(guī)劃模型較為簡單，數(shù)字也是比較小的，而且需要進(jìn)行

靈敏度分析，所以對generalsolver選項卡上的DualComputations（對偶

計算）項設(shè)為"PricesandRanges（計算對偶價格并分析敏感性）對Linear

Solver（線性求解器）選項卡上的Method（求解方法）項設(shè)為"PrimalSimplex

（原始單純形法）”其余的選項采用Lingo默認(rèn)值，注竟，如果模型變量

較多，數(shù)字較大時，就需要對其它選項進(jìn)行設(shè)置。

第三步，在Ling。的命令窗口中輸入此線性規(guī)劃的模型（注意沒有上

下標(biāo)之分），如下圖1-5所示：

6

圖1-5輸入模型界面

max=2*xl+x2;

5*x2<=15;

6*xl+2*x2<=24;

xl+x2<=5;

然后單擊File菜單下的Save,將模型保存，以供以后使用。（當(dāng)然也

可以不保存模型。

第四步，單擊Lingo菜單下的Solver菜單項，對模型進(jìn)行求解。其結(jié)

果如下所示：

7

WWF*'CW!ITWJMt,■,HWWSWl

圖1-6模1的計算結(jié)果圖

Globaloptimalsolutionfoundatiteration:4

Objectivevalue:8.,500000

VariableValueReducedCost

XI3.5000000.000000

X21.5000000.000000

RowSlackorSurplusDualPrice

18.5000001.000000

27.5000000.000000

30.0000000.2500000

40.0000000.5000000

求解器狀態(tài)窗口對于監(jiān)視求解器的進(jìn)展和模型大小是有用的。求解器

狀態(tài)窗口提供了一個中斷求解器按鈕(InterruptSolver),點(diǎn)擊它會導(dǎo)致

LINGO在下一次迭代時停止求解。在絕大多數(shù)情況，LINGO能夠交還和

報告到目前為止的最好解。?個例外是線性規(guī)劃模型，返回的解是無意義

的，應(yīng)該被忽略。但這并不是一個問題，因為線性規(guī)劃通常求解速度很快,

8

很少需要中斷。注意：在中斷求解器后，必須小心解釋當(dāng)前解，因為這些

解可能根本就不最優(yōu)解、可能也不是可行解或者對線性規(guī)劃模型來說就是

無價值的。

在中斷求解器按鈕的右邊的是關(guān)閉按鈕（Close）。點(diǎn)擊它可以關(guān)閉

求解器狀態(tài)窗口，不過可在任何時間通過選擇WindowslStatusWindow再

重新打開。

在中斷求解器按鈕的右邊的是標(biāo)記為更新時間間隔（UpdateInterval）

的域。LINGO將根據(jù)該域指示的時間（以秒為單位）為周期更新求解器

狀態(tài)窗口?？梢噪S意設(shè)置該域，不過若設(shè)置為0將導(dǎo)致更長的求解時間一

-LINGO花費(fèi)在更新的時間會超過求解模型的時間。

Total顯示當(dāng)前模型的全部變量數(shù)，Nonlinear顯示其中的非線性變量

數(shù)，Integers顯示其中的整數(shù)變量數(shù)。非線性變量是指它至少處于某一個

約束中的非線性關(guān)系中。

從計算結(jié)果告訴我們：這個線性規(guī)劃的最優(yōu)解為xl=3.5,x2=1.5,最

優(yōu)值為z=8.5,即產(chǎn)品I生產(chǎn)3.5件，產(chǎn)品II生產(chǎn)1.5件，可獲最大利潤

8.5元。另外還可以看出第一個約束的資源剩余7.5個單位，即設(shè)備A剩

余，對應(yīng)的影響價格為0；第二個約束和第三個約束對應(yīng)的資源沒有剩余，

相應(yīng)的影子價格為0.25和0.50；即設(shè)備A、設(shè)備B和調(diào)試工序的出讓價

格分別為0、0.25、0.50o從中還可以看出迭代經(jīng)過了四步。

第五步，單擊上圖窗體中的close按鈕，關(guān)閉求解窗體。然后再單擊

模型窗體，使其處于活動狀態(tài)。接著單擊Ling。菜單下的Range菜單項，

其結(jié)果如下所示：

9

Maaye*anvhicb(hek>?aaaluictuuavmiiX

CaECflnsAllovabl*lllOMbla

CoexttcieniJncceo*

XI3.000000).0000001.000000

XZ1.0000001.000000O.9?39?3

RxgfctiMndSide*2。他?

w?CucrwMtAl|utra*>l?tnumhlw

WBInrreaae

215.00000mrwrrr7.SOOOOO

34.OOQQOt.QOQOOQ<.000000

■1.0000001.0000001.000000

圖1-7靈敏度分析結(jié)果界面

即：Rangesinwhichthebasisisunchanged:

ObjectiveCoefficientRanges

CurrentAllowableAllowable

VariableCoefficientIncreaseDecrease

XI2.0000001.0000001.000000

X21.0000001.0000000.3333333

RighthandSideRanges

RowCurrentAllowableAllowable

RHSIncreaseDecrease

215.00000INFINITY7.500000

324.000006.0000006.000000

45.0000001.0000001.000000

目標(biāo)函數(shù)的系數(shù)發(fā)生變化時(假定約束條件不變),最優(yōu)解和最優(yōu)值

會改變嗎？這個問題不能簡單地回答。上面輸出給出了最優(yōu)基不變條件下

目標(biāo)函數(shù)系數(shù)的允許變化范圍：X1的系數(shù)為(2-1,2+1)=(1,3)；x2

的系數(shù)為(1-0.3333,1+1)=(0.6667,2)。注意：xl系數(shù)的允許范圍

需要x2系數(shù)1不變，反之亦然。由于目標(biāo)函數(shù)的費(fèi)用系數(shù)變化并不影響

約束條件，因此此時最優(yōu)基不變可以保證最優(yōu)解也不變，但最優(yōu)值變化。

用這個結(jié)果很容易回答附加問題3o

下面對“資源”的影子價格作進(jìn)一步的分析。影子價格的作用(即在

10

最優(yōu)解下“資源”增加1個單位時“效益”的增量)是有限制的。每增加

單位資源利潤增長影子價格元，但是，上面輸出的CURRENTRHS的

ALLOWABLEINCREASE和ALLOWABLEDECREASE給出了影子價

格有意義條件下約束右端的限制范圍：設(shè)備A可以無限的增加，設(shè)備B

最多增加6,調(diào)試工序最多最多增加1。很容易回答問題4的。

需要注意的是：靈敏性分析給出的只是最優(yōu)基保持不變的充分條件，

而不一定是必要條件。比如對于上面的問題，“設(shè)備A最多增加6”的含

義只能是“設(shè)備A增加6”時最優(yōu)基保持不變，所以影子價格有意義，即

利潤的增加大于牛奶的投資。反過來，設(shè)備A增加超過6,影子價格是否

一定沒有意義？最優(yōu)基是否一定改變？一般來說，這是不能從靈敏性分析

報告中直接得到的。此時，應(yīng)該重新用新數(shù)據(jù)求解規(guī)劃模型，才能做出判

斷。所以，從正常理解的角度來看，我們上面回答“設(shè)備A最多增加6)”

并不是完全科學(xué)的。

實驗條件：1.清華出版社《運(yùn)籌學(xué)教程》教材；

2.Lindo/lingo計算機(jī)軟件；

實驗思考：

1、某公司有三個工廠均可生產(chǎn)A,B,C三種產(chǎn)品.各產(chǎn)品的單件利潤分

別為35元,30元和25元；市場預(yù)測表明:三種產(chǎn)品的需求量分別是900,

1200和750件；各種產(chǎn)品的占地面積分別是20,15和12平方尺.一廠倉

庫面積13000平方尺，二廠12000平方尺，三廠5000平方尺.產(chǎn)品必須放在

庫內(nèi)且在期末一次售出.問如何按排各廠的生產(chǎn)計劃，使全公司的總收益

最高，建立線性規(guī)劃模型。

2、某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下表所示，

試分別回答下列問題：

消耗量產(chǎn)品

甲乙丙原料擁有量

原料

11

A63545

B34530

單件利415

潤

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

（2）若產(chǎn)品乙、丙的單件利潤不變，則產(chǎn)品甲的利潤在什么范圍

內(nèi)變化時，上述最解不變；

（3）若有一種新產(chǎn)品丁，其原料消耗定額：A為3單位，B為2

單位，單件利潤為2.5單位。問該產(chǎn)品是否值得安排生產(chǎn)，并求新的最優(yōu)

計劃；

若材料A市場緊缺，除擁有量外一時無法購進(jìn)，而原材料B如數(shù)量

不足可去市場購買，單價為0.5,問該廠應(yīng)否購買，并用運(yùn)籌概念說明原

因，并且購進(jìn)多少為宜；

3、某商場決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。

根據(jù)統(tǒng)計，商場每天需要的營業(yè)員如下表所示。

營業(yè)員需要量統(tǒng)計表

星期需要人數(shù)星期需要人數(shù)

—■300五480

二300六600

三350日550

四400

商場人力資源部應(yīng)如何安排每天的上班人數(shù)，使商場總的營業(yè)員最

少。

12

2實驗項目二應(yīng)用運(yùn)籌學(xué)CAI

軟件求解運(yùn)輸問題

實驗學(xué)時：1

實驗?zāi)康模?/p>

1、了解軟件的界面和功能；

2、熟悉并掌握應(yīng)用軟件來求解運(yùn)輸問題；

實驗內(nèi)容：

1、運(yùn)籌學(xué)CAI軟件介紹

(1)主界面

該程序下包含數(shù)個模塊,主界面是對各個模塊的綜合。如圖2-1所示,

程序的主界面比較樸素，主要功能依靠菜單與快捷按鈕來調(diào)用。圖2-1

中標(biāo)示出了各個快捷按鈕所對應(yīng)的功能，每個快捷按鈕都對應(yīng)著一個菜單

的功能。在程序運(yùn)行過程中，當(dāng)鼠標(biāo)在快捷按鈕上停留片刻時，將自動出

現(xiàn)提示文字。

圖2-1主界面

13

圖2-2新建項目

(2)新項目

選擇主菜單"文件(F)”下的“新項目(N)”菜單，或是單擊新項目按鈕，

都將彈出一個對話框，提示是新建一個小問題的練習(xí)還是一個大項目的解

答，如圖2-2所示。單擊相應(yīng)的按鈕將開始一個新的項目，也可以單擊取

消按鈕取消本次操作。由于演示部分是程序事先已經(jīng)封裝好了的，無法重

新建立一個項目，因此演示部分將不出現(xiàn)在新項目的選擇對話框里。

實現(xiàn)同樣的功能，用戶也可以通過直接單擊主界面上的小問題練習(xí)按

鈕與大項目解答按鈕來開始一個小問題練習(xí)或是大項目解答的新項目。

(3)讀取文件

在本程序中，數(shù)據(jù)文件將以四種文件格式存放：

■演示數(shù)據(jù)文件，擴(kuò)展名為.sdt；

■小問題數(shù)據(jù)文件，擴(kuò)展名為.edt；

■小問題迭代中間數(shù)據(jù)文件，擴(kuò)展名為.tdt；

■大項目數(shù)據(jù)文件，擴(kuò)展名為Jdt；

在用戶的使用過程中，隨著數(shù)據(jù)文件的逐步增多，有可能給用戶帶來

一定的困惑：忘記某一類數(shù)據(jù)文件應(yīng)該在哪個模塊里打開了。這時只要簡

單地選擇主菜單"文件(F)”下的“讀取文件(R)”菜單，或是直接單擊讀

取文件按鈕，在彈出的打開文件對話框里選擇想要打開的數(shù)據(jù)文件，程序

將自動轉(zhuǎn)入到與該文件相對應(yīng)的模塊中，并打開文件。

(4)第一模塊：演示部分

14

下一步(g)

上一步的

另一示例國)..

退出g)

圖2-3彈出菜單

選擇主菜單“選擇(C)”下的“演示(S)”菜單，或是單擊演示按鈕，

程序?qū)⑥D(zhuǎn)入到對示例的演示模塊中。這時需要指定的是演示數(shù)據(jù)文件存放

的目錄，并選擇某一示例以及該問題的初始化方法(默認(rèn)為第一示例，運(yùn)

用西北角法)，單擊確定按鈕后開始對該例子的演示。

進(jìn)入演示模式后，直接單擊鼠標(biāo)左鍵或鍵盤的空格鍵，將繼續(xù)下一步

的演示。如果要回到上一步的演示結(jié)果，可以單擊鼠標(biāo)右鍵，在彈出菜單

中選擇“上一步(B)”項，如圖2-3所示。此外，可以在彈出菜單中選擇

“另一示例(A)…”項，退出當(dāng)前的示例以開始另一個新的示例，或是直

接選擇“退出(X)”項退出演示模塊。

圖2-4彈出框

在演示過程中，屏幕上一次只顯示一步的數(shù)據(jù)，在某些時候需要將本

步的計算數(shù)據(jù)與前一步做互相比較時，程序提供了一個彈出的顯示框。只

要將鼠標(biāo)移動到屏幕的右上角時，該框自動彈出，在框內(nèi)顯示出上一步的

計算數(shù)據(jù)，如圖2-4所示。

鼠標(biāo)移開屏幕右上角之后，該彈出框?qū)⒆詣雨P(guān)閉隱藏，不影響正常的

演示過程。

(5)第二模塊：小問題練習(xí)

15

選擇主菜單“選擇(C)”下的“小練習(xí)(P)”菜單，或是單擊小問題練

習(xí)按鈕，程序?qū)⑥D(zhuǎn)入到小問題練習(xí)模塊中，界面如圖5所示。

圖2-5小問題練習(xí)

在該模塊中可以對8x8矩陣以下的小練習(xí)進(jìn)行逐步的演示。在右上角

的旋轉(zhuǎn)按鈕里可以選擇產(chǎn)、銷地的個數(shù)。隨著旋轉(zhuǎn)按鈕里產(chǎn)、銷地的改變,

運(yùn)費(fèi)表矩陣也將自動隨之改變。在右下方的五個按鈕中，包含了存儲數(shù)據(jù)

到文件中，以及從文件中讀取數(shù)據(jù)的功能。清空按鈕用以根據(jù)當(dāng)前的產(chǎn)、

銷地數(shù)清空運(yùn)費(fèi)表中的數(shù)據(jù)，復(fù)位按鈕將把產(chǎn)、銷地數(shù)與運(yùn)費(fèi)表復(fù)位成為

圖2-5中的默認(rèn)設(shè)置。在確認(rèn)數(shù)據(jù)輸入無誤后，單擊確定按鈕開始計算。

此時程序?qū)斎氲臄?shù)據(jù)進(jìn)行檢查，剔除無效的數(shù)據(jù)，表中所有空白的單

元格都將被視為零。如果數(shù)據(jù)無誤，程序?qū)z查是否出現(xiàn)產(chǎn)銷不平衡的情

況，一旦出現(xiàn)產(chǎn)、銷不平衡，程序?qū)⒔o出提示，并增加虛擬點(diǎn)、調(diào)整表中

的數(shù)據(jù)，此時用戶需再次單擊確定按鈕，根據(jù)選擇的尋找初始可行解的方

法，開始相應(yīng)的計算。不論選擇的是何種方法，在得到初始可行解后，都

統(tǒng)一轉(zhuǎn)入對初始可行解的迭代過程，如圖2-6所示。

16

圖2-6迭代過程

在這里同樣地可以對數(shù)據(jù)進(jìn)行存儲，也可以從文件讀取數(shù)據(jù)。單擊迭

代按鈕，開始用位勢法對分配方案進(jìn)行檢驗和迭代，迭代結(jié)束后，在編輯

框內(nèi)顯示出當(dāng)前方案下的目標(biāo)函數(shù)值。如果已經(jīng)達(dá)到最優(yōu)方案，將彈出對

話框提示達(dá)到最優(yōu)。在某些情況下，可能需要迭代許多步才能達(dá)到最優(yōu)方

案，如果用戶在迭代了數(shù)步后不再關(guān)心其他各步的迭代過程，可以點(diǎn)擊右

下角的“直接得到結(jié)果”按鈕。此時程序?qū)⒉辉亠@示中間過程，直接運(yùn)算

出最終的最優(yōu)結(jié)果，并顯示該方案的分配情況與最終目標(biāo)函數(shù)值。

另外，不論在迭代的任何時候，都可以通過點(diǎn)擊左下角的新項目按鈕,

重新開始一個小問題練習(xí)，但是現(xiàn)有的所有數(shù)據(jù)都將丟失（如果沒有保存

的話），因此，程序?qū)⒁竽愦_認(rèn)是否真的開始一個新的項目。

（6）第三模塊：大項目解答

選擇主菜單“選擇（C）”下的“大項目（L）”菜單，或是單擊大項目解

答按鈕，程序?qū)⑥D(zhuǎn)入到對大項目的解答模塊中。界面上與小問題解答相類

似，但是略去了對獲得初始可行解的方法的選擇。在這個模塊里，程序不

再顯示中間的任何運(yùn)算過程，而只給出最終的解決方案。因此，這里可以

17

運(yùn)算的數(shù)據(jù)達(dá)到100x100矩陣。

在運(yùn)算結(jié)束后，程序?qū)炎罱K解決方案顯示到一個網(wǎng)格中。由于通常

情況下，該模塊運(yùn)算的都是較大規(guī)模的數(shù)量，結(jié)果的顯示有些紊亂，并且

容易讓人感到迷惑。這種情況下程序提供了一個輸出最終結(jié)果為文本文件

的功能，在輸出的文本文件中，詳細(xì)記錄了從產(chǎn)地角度來看與從銷地角度

來看的最佳運(yùn)輸方案，這一點(diǎn)無疑是具有較高的實用價值。

實驗思考：

1、某公司從三個產(chǎn)地Al、A2、A3將物品運(yùn)往四個銷地Bl、B2、

B3、B4,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的

運(yùn)費(fèi)如下表所示，問應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最??？

銷地

產(chǎn)地、BiB2B3Bi產(chǎn)量

3113107

A_19284

A3741059

銷量365620（產(chǎn)銷平

衡）

該問題的最優(yōu)解為X|3=5,X|4=2,X21=3,X24=1,X32=6,X34=3,其余

的Xij=O，且該問題具有多重解。

總運(yùn)費(fèi)為：f=5X3+2X10+3Xl+1X8+6X4+3X5=85。

2、某公司從兩個產(chǎn)地A-A2將物品運(yùn)往三個銷地&、B,、B3,各產(chǎn)地

的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，

問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？

銷地產(chǎn)地產(chǎn)量

B,B2B3

A,13151278

A?11292245

需求533625

18

3實驗項目三目標(biāo)規(guī)劃

實驗學(xué)時：1

實驗?zāi)康模耗繕?biāo)規(guī)劃(goalprogramming)是由線性規(guī)劃發(fā)展演變而

來的。線性規(guī)劃考慮的是只有一個目標(biāo)函數(shù)的問題，而實際問題中往往需

要考慮多個目標(biāo)函數(shù)，這些目標(biāo)不僅有主次關(guān)系，而且有的還相互矛盾。

這些問題用線性規(guī)劃求解就比較困難，因而提出了目標(biāo)規(guī)劃。現(xiàn)階段所討

論的實際是線性目標(biāo)規(guī)劃。

由于LINDO不能直接求解目標(biāo)規(guī)劃問題，這并不意味著LINDO失

去了效力。序貫式算法是求解目標(biāo)規(guī)劃的一種早期算法，起核心是根據(jù)優(yōu)

先級的先后次序，將目標(biāo)規(guī)劃問題分解成一系列的單目標(biāo)規(guī)劃問題，然后

再依次求解。

通過本實驗，掌握線性目標(biāo)規(guī)劃模型在Lindo/lingo中的求解，并能

達(dá)到靈活運(yùn)用。

實驗要求：1.掌握線性目標(biāo)規(guī)劃的建模步驟及方法；

2.掌握線性目標(biāo)規(guī)劃模型的序貫式算法。

實驗內(nèi)容及步驟：

序貫式算法其實就是分解成二種辦法求解目標(biāo)規(guī)劃。

例：求解目標(biāo)規(guī)劃的序貫式算法

某音像店有5名全職售貨員和4名兼職售貨員，全職售貨員每月工作

160h,兼職售貨員每月工作80h,根據(jù)記錄，全職每小時銷售CD25張，

平均每小時工資15元，加班工資每小時22.5元。兼職售貨員每小時銷售

CD10張，平均工資每小時10元，加班工資每小時10元。現(xiàn)在預(yù)測下月

CD銷售量為27500張，商店每周開門營業(yè)6天，所以可能要加班。每出

售一張CD盈利L5元。

商店經(jīng)理認(rèn)為，保持穩(wěn)定的就業(yè)水平加上必要的加班，比不加班就業(yè)

水平好要好，但全職銷售員如果加班過多，就會因為疲勞過度而造成效率

19

下降，因此不允許每月加班超過100h,建立相應(yīng)的目標(biāo)規(guī)劃模型，并運(yùn)

用LINGO軟件求解。

解：首先建立目標(biāo)約束的優(yōu)先級。

P1:下月的CD銷售量達(dá)到27500張。

P2:全職售貨員加班時間不超過100ho

P3:保持全體售貨員充分就業(yè)，對全職的要比兼職的加倍優(yōu)先考慮。

P4:盡量減少加班時間，對兩種售貨員區(qū)別對待，權(quán)重由他們對利潤

的貢獻(xiàn)而定。

第二，建立目標(biāo)約束

銷售目標(biāo)約束，設(shè)

XI:全體全職售貨員下月的工作時間；

X2:全體兼職售貨員下月的工作時間；

dl-:達(dá)不到銷售目標(biāo)的偏差；

dl+:超過銷售目標(biāo)的偏差。

125%+10x2+d「-d；=27500

(2)正常工作時間約束。設(shè)

d2v全體全職售貨員下月的停工時間；

d2+:全體全職售貨員下月的加班時間；

d3-:全體兼職售貨員下月的停工時間；

d3+:全體兼職售貨員下月的加班時間。

-+

,&+J2-d2-800,

%2+4dy=320.

加班時間的限制。設(shè)

d4v全體全職售貨員下月的加班不足100h的偏差；

d4+:全體全職售貨員下月的加班超過100h的偏差。

20

min

$+d；-d；=900,

另外，兩種售貨員區(qū)別對待，權(quán)重由他們對利潤的貢獻(xiàn)而定,

故權(quán)重比為：d2+：d3+=l:3,所以另一個加班目標(biāo)約束為：

min"++3痣+}

<x}+d；一d2'=800,

=320.

第三，按目標(biāo)的優(yōu)先級，寫出相應(yīng)的目標(biāo)規(guī)劃模型：

++

minz=pxd~+p2d4++P3Q&+J3-)+p4(J2+3J3);

s.t252+10x2+d「-4J=27500,

玉+d?—d9—800,

xo+&——320,

$+dj-dj=900,

玉，W，4，d；>0,z=1,2,3,4.

第四，寫出相應(yīng)的LINGO程序，程序名：mb.lg4

MODEL：

sets:

Level/1,.4/:p,z.Goal;

Variable/1..2/:x;

S_Con_Num/l..4/:g,dplus,dminus;

S_Cons(S_Con_Num,Variable):c;

Obj(LevelsS_Con_Num):WpluszWminus;

endsets

data:

p=????;

Goal=?z?,?,0;

g=27500800320900;

c=2510100110;

Wplus=0000

0001

0000

0130;

Wminus=1000

0000

21

0210

0000;

enddata

min=@sum(Level:p*z);

@for(Level(i);

z(i)=@sum(S_Con_Num(j):Wplus(izj)*dplus(j))

+@sum(S_Con_Num(j):Wminus(i,j)*dminus(j));

@for(S_Con_Num(i):

?sum(Variable(j):c(i,j)*x(j))

+dminus(i)-dplus(i)=g(i);

)；

@for(Level(i)/i#lt#@size(Level):

@bnd(0,z(i),Goal(i));

)；

END

第一級的計算結(jié)果(只列出相關(guān)變量)：

Globaloptimalsolutionfoundatiteration:8

Objectivevalue:0.000000

VariableValueReducedCost

X(1)800.00000.000000

X(2)750.00000.000000

第二級的計算結(jié)果（只列出相關(guān)變量）:

Globaloptimalsolutionfoundatiteration:8

Objectivevalue:0.000000

VariableValueReducedCost

X(1)800.00000.000000

X(2)750.00000.000000

第三級的計算結(jié)果（只列出相關(guān)變量）:

Globaloptimalsolutionfoundatiteration:1

Objectivevalue:0.000000

VariableValueReduce