管理運(yùn)籌學(xué)教程

管理運(yùn)籌學(xué)教程

徐軍委編著

2018-10

?

?

管理運(yùn)籌學(xué)教程

徐軍委編著

企業(yè)管理出版社

?

圖書在版編目（CIP）數(shù)據(jù)

管理運(yùn)籌學(xué)教程/徐軍委編著.--北京：企業(yè)管理出版社，2018.10

ISBN978-7-5164-1785-0

Ⅰ.①管…Ⅱ.①徐…Ⅲ.①管理學(xué)-運(yùn)籌學(xué)-教材Ⅳ.①C931.1

中國版本圖書館CIP數(shù)據(jù)核字（2018）第216153號(hào)

書名：管理運(yùn)籌學(xué)教程

作者：徐軍委

責(zé)任編輯：張平田天

書號(hào)：ISBN978-7-5164-1785-0

出版發(fā)行：企業(yè)管理出版社

地址：北京市海淀區(qū)紫竹院南路17號(hào)郵編：100048

網(wǎng)址：http：//

電話：編輯部（010）68701638發(fā)行部（010）68701816

電子信箱：qyglcbs@

印刷：北京虎彩文化傳播有限公司

經(jīng)銷：新華書店

規(guī)格：170毫米×240毫米16開本14.25印張198千字

版次：2018年10月第1版2018年10月第1次印刷

定價(jià)：58.00元

版權(quán)所有翻印必究·印裝有誤負(fù)責(zé)調(diào)換

?

前言

運(yùn)籌學(xué)是一門定量優(yōu)化的決策科學(xué)，是現(xiàn)代管理學(xué)的一門重要專業(yè)基礎(chǔ)課程。它是

20世紀(jì)30年代初發(fā)展起來的應(yīng)用性非常強(qiáng)的一門學(xué)科。運(yùn)籌學(xué)是應(yīng)用數(shù)學(xué)和形式

科學(xué)的跨領(lǐng)域研究，利用統(tǒng)計(jì)學(xué)、數(shù)學(xué)模型和一些經(jīng)典算法等方法，幫助人們解決

那些可以用定量方法和有關(guān)理論來處理的決策問題，其在社會(huì)生活的許多方面都有

重要的應(yīng)用。

管理運(yùn)籌學(xué)則是利用數(shù)學(xué)、系統(tǒng)科學(xué)、計(jì)算機(jī)理論、優(yōu)化原理等學(xué)科和理論的最新

成果，研究人們生產(chǎn)生活中遇到的各種量化問題，以便使有限的人、財(cái)、物等資源

得到合理運(yùn)用，取得最大化的收益。管理運(yùn)籌學(xué)內(nèi)容較豐富，針對(duì)管理運(yùn)籌學(xué)自身

的特點(diǎn)，本書只涉及最常見的一些模型和理論，而且更多側(cè)重理論的應(yīng)用，體現(xiàn)在

以下幾點(diǎn)：

一是教學(xué)重點(diǎn)的轉(zhuǎn)變。

針對(duì)管理運(yùn)籌學(xué)的教學(xué)目的和培養(yǎng)目標(biāo)，本書更多側(cè)重于應(yīng)用研究。本書考慮到M

ATLAB、SAS、Mathematica、SPSS、Lindo/Lingo、GAMS等工具軟件的復(fù)雜性，

采用最常見的Excel平臺(tái)進(jìn)行求解，即使數(shù)學(xué)基礎(chǔ)薄弱也能很快學(xué)會(huì)求解過程，但

本書應(yīng)用Excel工具求解的模型主要為線性規(guī)劃模型。

二是針對(duì)不同讀者的應(yīng)用設(shè)置。

對(duì)于經(jīng)濟(jì)管理類的本科生，本書只要求其理解運(yùn)籌學(xué)各個(gè)模塊的求解思路，并在此

基礎(chǔ)上學(xué)會(huì)運(yùn)用Excel去求解較為簡單的數(shù)學(xué)模型；對(duì)于有良好數(shù)學(xué)基礎(chǔ)的專業(yè)人

士，建議在學(xué)會(huì)運(yùn)用Excel求解的基礎(chǔ)上，靈活地設(shè)計(jì)Excel求解模塊，以便遇到相

似的問題時(shí)，可以在最短時(shí)間內(nèi)得到求解結(jié)果。

三是難易程度適中。

本書在編寫的過程中，編者特意選擇所在高校的兩個(gè)學(xué)生小組進(jìn)行應(yīng)用實(shí)驗(yàn)，期望

了解數(shù)學(xué)基礎(chǔ)薄弱的學(xué)生如何理解運(yùn)籌學(xué)模塊和應(yīng)用過程，并征求他們對(duì)于本書主

要章節(jié)的意見和建議。結(jié)果發(fā)現(xiàn)，對(duì)于線性規(guī)劃、運(yùn)輸問題、圖論等核心模塊，學(xué)

生的理解基本到位。因此，本書難易程度適中，適合基礎(chǔ)較為薄弱的學(xué)生學(xué)習(xí)。

另外，讀者學(xué)習(xí)本書應(yīng)該著重培養(yǎng)自己三個(gè)方面的能力：運(yùn)用所學(xué)的運(yùn)籌學(xué)模型解

決實(shí)際問題的能力、掌握Excel求解管理運(yùn)籌學(xué)問題的基本步驟、學(xué)會(huì)理解運(yùn)籌學(xué)

模型求解結(jié)果所代表的經(jīng)濟(jì)和管理意義。

本書在編寫過程中，得到了中國勞動(dòng)關(guān)系學(xué)院經(jīng)濟(jì)管理系兩個(gè)學(xué)生小組的支持和幫

助，在此對(duì)俞瀾天、李悅、金豪、陳艷、劉鑫、黃瓏、鄭寒翠、黃初陽、何琎琎、

賈士誼等同學(xué)表示感謝。

由于編者水平有限，書中難免存在不足之處，懇請(qǐng)讀者不吝賜教。

編者

2018年7月

?

目錄

前言

第一章概述

1.1運(yùn)籌學(xué)簡史

1.2運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)

1.3管理運(yùn)籌學(xué)的主要內(nèi)容及在工商管理中的應(yīng)用

1.4管理運(yùn)籌學(xué)的工作步驟

1.5管理運(yùn)籌學(xué)的模型及建模思路

1.6管理運(yùn)籌學(xué)的計(jì)算工具

第二章線性規(guī)劃及其應(yīng)用

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

2.1.1線性規(guī)劃問題的提出

2.1.2線性規(guī)劃數(shù)學(xué)模型

2.2線性規(guī)劃的圖解法

2.3單純形法

2.4案例解析

第三章運(yùn)輸問題

3.1運(yùn)輸問題及數(shù)學(xué)模型

3.2表上作業(yè)法

3.3案例解析

第四章整數(shù)規(guī)劃

4.1整數(shù)規(guī)劃數(shù)學(xué)模型

4.2整數(shù)規(guī)劃典型解法

4.3整數(shù)規(guī)劃應(yīng)用案例

第五章動(dòng)態(tài)規(guī)劃

5.1多階段決策問題

5.2動(dòng)態(tài)規(guī)劃的基本概念和基本方程

5.2.1動(dòng)態(tài)規(guī)劃的基本概念

5.2.2動(dòng)態(tài)規(guī)劃的基本思想與基本方程

5.3動(dòng)態(tài)規(guī)劃應(yīng)用舉例

第六章圖論和網(wǎng)絡(luò)模型

6.1圖論概述

6.2圖論實(shí)例

第七章排隊(duì)論

7.1排隊(duì)論基本概念

7.1.1排隊(duì)系統(tǒng)及其基本結(jié)構(gòu)

7.1.2排隊(duì)系統(tǒng)的三個(gè)基本特征

7.1.3排隊(duì)論的常用術(shù)語

7.1.4輸入與輸出

7.2簡單模型（M/M/s模型）

7.2.1M/M/s/系統(tǒng)模型

7.2.2M/M/s/r系統(tǒng)模型

7.2.3M/M/s/m/m系統(tǒng)模型

7.3排隊(duì)論其他模型選介

7.3.1M/G/1系統(tǒng)模型

7.3.2優(yōu)化設(shè)計(jì)模型

第八章存儲(chǔ)論

8.1存儲(chǔ)論基本概念

8.2確定性存儲(chǔ)系統(tǒng)的基本模型

8.3存儲(chǔ)論其他模型選介

第九章對(duì)策論

9.1對(duì)策的概念和分類

9.2矩陣對(duì)策的基本定理

9.3矩陣對(duì)策的一般解法

9.4其他類型對(duì)策簡介

第十章目標(biāo)規(guī)劃

10.1問題概述

10.2目標(biāo)規(guī)劃問題實(shí)例

10.3目標(biāo)規(guī)劃的圖解法

參考文獻(xiàn)

?

第一章概述

運(yùn)籌學(xué)是現(xiàn)代管理學(xué)一門重要的專業(yè)基礎(chǔ)課程，它是20世紀(jì)30年代初發(fā)展起來的

應(yīng)用性非常強(qiáng)的一門新興學(xué)科。運(yùn)籌學(xué)是應(yīng)用數(shù)學(xué)和形式科學(xué)的跨領(lǐng)域研究，利用

統(tǒng)計(jì)學(xué)、數(shù)學(xué)模型和算法等方法，幫助人們解決那些可以用定量方法和有關(guān)理論來

處理的決策問題。在工業(yè)、商業(yè)、農(nóng)業(yè)、交通運(yùn)輸、社會(huì)管理等領(lǐng)域都有重要的應(yīng)

用。

本章首先介紹運(yùn)籌學(xué)的歷史，其性質(zhì)與特點(diǎn)以及運(yùn)籌學(xué)研究的主要內(nèi)容。然后從運(yùn)

籌學(xué)解決問題的角度，總結(jié)出運(yùn)籌學(xué)的工作步驟，對(duì)運(yùn)籌學(xué)模型的建立與解決進(jìn)行

重點(diǎn)討論。最后結(jié)合運(yùn)籌學(xué)在管理實(shí)踐中的應(yīng)用，淺談運(yùn)籌學(xué)的發(fā)展趨勢，使初學(xué)

者對(duì)管理運(yùn)籌學(xué)概念和方法有初步的認(rèn)識(shí)。

1.1運(yùn)籌學(xué)簡史

運(yùn)籌學(xué)產(chǎn)生于第二次世界大戰(zhàn)期間，1937年英國部分科學(xué)家被邀請(qǐng)去幫助皇家空

軍研究雷達(dá)的部署和運(yùn)作問題，目的在于最大限度地發(fā)揮數(shù)量有限的雷達(dá)效用，以

應(yīng)對(duì)德軍對(duì)英國本土的空襲。1938年波德塞（Bawdsey）雷達(dá)站的負(fù)責(zé)人羅伊（R

owe）提出了優(yōu)化防空作戰(zhàn)系統(tǒng)運(yùn)行的問題，并用“Operational

Research”（OR）一詞作為對(duì)這一方面研究的描述，這就是今天仍將運(yùn)籌學(xué)稱為OR

的歷史由來。1939年從事此方面問題研究的科學(xué)家被召集到英國皇家空軍指揮總

部，成立了一個(gè)由布萊開特（Blacket）領(lǐng)導(dǎo)的軍事科技攻關(guān)小組；由于其成員學(xué)

科性質(zhì)的多樣性，這一最早成立的軍事科技攻關(guān)小組被戲稱為“布萊開特馬戲團(tuán)”。

由于“布萊開特馬戲團(tuán)”的活動(dòng)是第一次有組織的系統(tǒng)的運(yùn)籌學(xué)活動(dòng)，所以后人將該

小組的成立作為運(yùn)籌學(xué)產(chǎn)生的標(biāo)志。此后，OR小組的活動(dòng)范圍不斷擴(kuò)大，從最初

的僅限于空軍，逐步擴(kuò)展到海軍和陸軍；研究內(nèi)容也從對(duì)軍事戰(zhàn)術(shù)性問題的研究，

逐步擴(kuò)展到對(duì)軍事戰(zhàn)略性問題的研究。第二次世界大戰(zhàn)期間，OR小組成功地解決

了許多重要作戰(zhàn)問題，為運(yùn)籌學(xué)的快速發(fā)展奠定了基礎(chǔ)。

第二次世界大戰(zhàn)結(jié)束后，除軍事方面的應(yīng)用研究以外，由于組織內(nèi)與日俱增的復(fù)雜

性和專門化所產(chǎn)生的問題，使人們認(rèn)識(shí)到這些問題基本上與戰(zhàn)爭中曾面臨的問題類

似，只是具有不同的現(xiàn)實(shí)環(huán)境而已，運(yùn)籌學(xué)就這樣在工商企業(yè)和其他部門中得到了

廣泛的應(yīng)用，形成了比較完備的理論體系，如規(guī)劃論、排隊(duì)論、存儲(chǔ)論、對(duì)策論等

，相繼在工業(yè)、農(nóng)業(yè)、經(jīng)濟(jì)和社會(huì)問題等各領(lǐng)域都有應(yīng)用。1947年，由丹捷格（G

eorge

Dantzig）提出的求解線性規(guī)劃問題的單純形法，開啟了運(yùn)籌學(xué)方法論快速發(fā)展的

歷程。電子計(jì)算機(jī)技術(shù)的迅猛發(fā)展和廣泛應(yīng)用，使運(yùn)用運(yùn)籌學(xué)方法解決實(shí)際問題變

得可行，又大大促進(jìn)了運(yùn)籌學(xué)的發(fā)展。截至目前，世界上不少國家已成立了致力于

該領(lǐng)域及相關(guān)活動(dòng)的專門學(xué)會(huì)，美國于1952年成立了運(yùn)籌學(xué)會(huì)，后來世界上許多

國家也都逐步成立了運(yùn)籌學(xué)會(huì)。1959年，在英、美、法三國的運(yùn)籌學(xué)會(huì)基礎(chǔ)上發(fā)

起成立了國際運(yùn)籌學(xué)聯(lián)合會(huì)（InternationalFederationofOperationsResearch

Societies，IFORS），許多國家或地區(qū)的學(xué)會(huì)已加入該會(huì)。此外還有一些地區(qū)性組

織，如歐洲運(yùn)籌學(xué)協(xié)會(huì)（EURO）成立于1975年，亞太運(yùn)籌學(xué)協(xié)會(huì)（APORS）成立

于1985年。

我國運(yùn)用運(yùn)籌學(xué)思想解決現(xiàn)實(shí)問題的歷史可追溯到戰(zhàn)國時(shí)期，田忌賽馬的故事就深

刻地說明了運(yùn)籌學(xué)思想的重要性。但我國系統(tǒng)研究運(yùn)籌學(xué)卻起步較晚，20世紀(jì)50

年代中期，錢學(xué)森、許國志等教授將運(yùn)籌學(xué)由西方引入我國，并結(jié)合我國的特點(diǎn)在

國內(nèi)推廣應(yīng)用。在經(jīng)濟(jì)數(shù)學(xué)方面，特別是投入產(chǎn)出表的研究和應(yīng)用開展較早，在質(zhì)

量控制（后改為質(zhì)量管理）的應(yīng)用也有特色。在此期間，以華羅庚教授為首的一大

批數(shù)學(xué)家加入運(yùn)籌學(xué)的研究隊(duì)伍，使運(yùn)籌數(shù)學(xué)的很多分支很快跟上當(dāng)時(shí)的國際水平

。1980年，中國數(shù)學(xué)會(huì)決定成立運(yùn)籌學(xué)分會(huì)，并于1982年5月正式加入國際運(yùn)籌學(xué)

聯(lián)合會(huì)。

1.2運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)

運(yùn)籌學(xué)是一門綜合性應(yīng)用型學(xué)科，是在20世紀(jì)形成的一門科學(xué)。當(dāng)人們把戰(zhàn)時(shí)的

運(yùn)籌研究取得成功的經(jīng)驗(yàn)在和平時(shí)期加以推廣應(yīng)用時(shí)，面臨著一個(gè)廣闊的研究領(lǐng)域

。在這一領(lǐng)域中，對(duì)于運(yùn)籌學(xué)主要研究和解決什么問題有許多爭論，至今仍沒有形

成定論，實(shí)際上形成了一個(gè)在爭論中發(fā)展運(yùn)籌學(xué)的局面。在這些爭論中，至少可以

看出以下特點(diǎn)：

（1）科學(xué)性。運(yùn)籌學(xué)原理中引進(jìn)了大量的數(shù)學(xué)研究方法，將數(shù)學(xué)作為一種重要的

解決問題的工具，尋求各種問題的最優(yōu)方案，所以是一門優(yōu)化科學(xué)，將實(shí)際問題通

過抽象的方式，抓住問題的主要矛盾，建立相應(yīng)的數(shù)學(xué)模型，從而求解這些問題。

隨著生產(chǎn)與管理的規(guī)模日益龐大，其間的數(shù)量關(guān)系也就更加復(fù)雜，利用其間的數(shù)量

關(guān)系來研究這些問題，引進(jìn)數(shù)學(xué)研究方法，使得運(yùn)籌學(xué)具有科學(xué)性這一大特點(diǎn)。

（2）系統(tǒng)性。運(yùn)籌學(xué)研究問題是從系統(tǒng)的觀點(diǎn)出發(fā)，研究全局性的問題，研究綜

合優(yōu)化的規(guī)律，它是系統(tǒng)工程的主要理論基礎(chǔ)。在現(xiàn)實(shí)生活中，基于個(gè)體利益和思

維習(xí)慣，很多時(shí)候我們會(huì)將許多問題人為分解，或者忽視系統(tǒng)效益，這顯然要付出

巨大的代價(jià)，全然失去對(duì)“整體”的連屬感，也不了解自身行動(dòng)所帶來的一連串后果

。運(yùn)籌學(xué)研究的基點(diǎn)就是系統(tǒng)優(yōu)化的思想。可以說，系統(tǒng)性是運(yùn)籌學(xué)研究和應(yīng)用的

一個(gè)很重要的特征。

（3）應(yīng)用性。在運(yùn)籌學(xué)術(shù)界，有許多人強(qiáng)調(diào)運(yùn)籌學(xué)的實(shí)用性和對(duì)研究結(jié)果的執(zhí)行

效果，并把執(zhí)行效果看作運(yùn)籌工作中的一個(gè)很重要的組成部分。在運(yùn)籌學(xué)的應(yīng)用方

面，我們首先會(huì)關(guān)注實(shí)際問題，接著是數(shù)學(xué)模型的建立，然后到模型求解。得到的

結(jié)果也會(huì)反饋到實(shí)際問題中。一個(gè)問題的求解應(yīng)該是一個(gè)閉環(huán)管理過程，從現(xiàn)象到

本質(zhì)，再回歸到現(xiàn)象才是一個(gè)比較合理的方式。

（4）跨學(xué)科性。早期運(yùn)籌學(xué)小組都是由不同領(lǐng)域的專家組成的。他們往往集體研

究問題，并綜合運(yùn)用多種學(xué)科的知識(shí)來解決實(shí)際問題。例如，第二次世界大戰(zhàn)時(shí)英

國空軍成立防空運(yùn)籌小組，其成員包括數(shù)學(xué)家、物理學(xué)家、天文學(xué)家、生物學(xué)家和

軍事專家等，旨在探討如何抵御敵人的空襲和潛艇。這種組織形式和組織特點(diǎn)在第

二次世界大戰(zhàn)以后應(yīng)用于經(jīng)濟(jì)管理領(lǐng)域，綜合運(yùn)用經(jīng)濟(jì)學(xué)、管理學(xué)、數(shù)學(xué)、管理學(xué)

、物理學(xué)、化學(xué)等學(xué)科的科學(xué)方法開展工作。從運(yùn)籌學(xué)的發(fā)展來看，這種跨學(xué)科的

特點(diǎn)一直伴隨其始終，并關(guān)乎運(yùn)籌學(xué)應(yīng)用的成敗及應(yīng)用的廣泛程度。

（5）理論和應(yīng)用相互促進(jìn)，相得益彰。運(yùn)籌學(xué)的各個(gè)分支學(xué)科，都是由于實(shí)際問

題的需要或以一定的實(shí)際問題為背景逐漸發(fā)展而來的。初期一些傳統(tǒng)學(xué)科方向的專

家對(duì)運(yùn)籌學(xué)做出了貢獻(xiàn)，隨后新的人才逐漸涌現(xiàn)，新的理論相繼出現(xiàn)，這往往就開

拓出新的領(lǐng)域，如線性規(guī)劃問題就是在研究生產(chǎn)的組織和計(jì)劃中出現(xiàn)的。1939年

著名數(shù)理經(jīng)濟(jì)學(xué)者康托洛維奇發(fā)表了《生產(chǎn)組織和計(jì)劃中的數(shù)學(xué)方法》，堪稱運(yùn)籌

學(xué)的先驅(qū)名著之一，后來George

Dantzig等人重新進(jìn)行獨(dú)立研究使其形成了一套較完整的理論和方法，進(jìn)而又開拓

了線性規(guī)劃的應(yīng)用范圍，并相繼出現(xiàn)了一批職業(yè)的線性規(guī)劃者。由于他們從事了大

量的實(shí)踐活動(dòng)，反過來又進(jìn)一步促進(jìn)了線性規(guī)劃方法論的進(jìn)一步發(fā)展，從而又出現(xiàn)

了橢圓法、內(nèi)點(diǎn)法等新的求解線性規(guī)劃的方法。目前運(yùn)籌學(xué)家們?nèi)栽谧巫尾痪氲匮?/p>

究新技術(shù)、新方法，使運(yùn)籌學(xué)這門年輕的學(xué)科不斷地向前發(fā)展。

1.3管理運(yùn)籌學(xué)的主要內(nèi)容及在工商管理中的應(yīng)用

運(yùn)籌學(xué)的主要內(nèi)容一般包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)

規(guī)劃、隨機(jī)規(guī)劃、網(wǎng)絡(luò)分析、排隊(duì)論、對(duì)策論、決策論、存儲(chǔ)論、可靠性理論、模

型論、投入產(chǎn)出分析等。它們中的每一部分都有豐富的內(nèi)容，都可以獨(dú)立成冊(cè)。上

述的前六個(gè)部分統(tǒng)稱為規(guī)劃論，它們主要是解決兩個(gè)方面的問題：一個(gè)方面的問題

是對(duì)于給定的人力、物力和財(cái)力，怎樣才能發(fā)揮其最大效益；另一方面的問題就是

對(duì)于給定的任務(wù)，怎樣才能用最少的人力、物力和財(cái)力去完成它。

網(wǎng)絡(luò)分析主要是研究解決生產(chǎn)組織、計(jì)劃管理中諸如最短路徑問題、最小連接問題

、最小費(fèi)用流問題以及最優(yōu)分派問題等。特別是在計(jì)劃和安排大型的復(fù)雜工程時(shí)，

網(wǎng)絡(luò)技術(shù)是重要的工具。

人們?cè)谏a(chǎn)和消費(fèi)過程中，都必須儲(chǔ)備一定數(shù)量的原材料、半成品或商品。存儲(chǔ)少

了會(huì)因?yàn)橥９ご匣蚴ヤN售機(jī)會(huì)而遭受損失，存儲(chǔ)多了又會(huì)造成資金積壓、原材

料及商品的損耗。因此，如何確定合理的存儲(chǔ)量、購貨批量和購貨周期至關(guān)重要，

這便是存儲(chǔ)論要解決的問題。

投入產(chǎn)出分析是通過研究多個(gè)部門的投入產(chǎn)出所必須遵守的綜合平衡原則來制訂各

個(gè)部門的發(fā)展計(jì)劃，借以從宏觀上控制、調(diào)整國民經(jīng)濟(jì)，以求得國民經(jīng)濟(jì)協(xié)調(diào)合理

地發(fā)展。

其中在工商管理領(lǐng)域里的應(yīng)用應(yīng)側(cè)重以下幾個(gè)方面：

（1）市場銷售。在廣告預(yù)算和媒體的選擇、競爭性定價(jià)、新產(chǎn)品開發(fā)、銷售計(jì)劃

的制訂等方面。

（2）生產(chǎn)計(jì)劃。在總體計(jì)劃方面主要是從總體確定生產(chǎn)、儲(chǔ)存和勞動(dòng)力的配合等

計(jì)劃以適應(yīng)變動(dòng)的需求計(jì)劃，主要用線性規(guī)劃法等。此外，還可用于生產(chǎn)作業(yè)計(jì)劃

、日程表的編排，還有在合理下料、配料問題、物料管理等方面的應(yīng)用。

（3）庫存管理。存貨模型將庫存理論與計(jì)算器的物料管理信息系統(tǒng)相結(jié)合，主要

應(yīng)用于多種物料庫存量的管理，確定某些設(shè)備的能力或容量，如工廠的庫存、停車

場的大小、新增發(fā)電設(shè)備容量大小、計(jì)算機(jī)的主存儲(chǔ)器容量、合理的水庫容量等。

（4）運(yùn)輸問題。這里涉及空運(yùn)、水運(yùn)、公路運(yùn)輸、鐵路運(yùn)輸、管道運(yùn)輸和廠內(nèi)運(yùn)

輸?shù)?，包括班次調(diào)度計(jì)劃及人員服務(wù)時(shí)間安排等問題。

（5）財(cái)務(wù)和會(huì)計(jì)。這里涉及預(yù)算、貸款、成本分析、定價(jià)、投資、證券管理、現(xiàn)

金管理等。用得較多的方法是統(tǒng)計(jì)分析、數(shù)學(xué)規(guī)劃、決策分析。此外，還有盈虧點(diǎn)

分析法、價(jià)值分析法等。

（6）人事管理。這里涉及六方面，包括：人員的獲得和需求估計(jì)；人才的開發(fā)，

即進(jìn)行教育和訓(xùn)練；人員的分配，主要是各種指派問題；各類人員的合理利用問題

；人才的評(píng)價(jià)，其中有如何測定一個(gè)人對(duì)組織、社會(huì)的貢獻(xiàn)；薪資和津貼的確定等

。

1.4管理運(yùn)籌學(xué)的工作步驟

運(yùn)籌學(xué)在解決大量實(shí)際問題過程中形成了以下幾點(diǎn)工作步驟。

（1）提出和形成問題。即要弄清問題的目標(biāo)、可能的約束、問題的可控變量以及

有關(guān)參數(shù)，搜集有關(guān)資料。

（2）建立模型。即把問題中可控變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模

型表示出來。

（3）求解。用各種手段（主要是數(shù)學(xué)方法，也可用其他方法）對(duì)模型求解。解可

以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要求可由決

策者提出。

（4）解的檢驗(yàn)。首先檢查求解步驟和程序有無錯(cuò)誤，然后檢查解是否反映現(xiàn)實(shí)問

題。

（5）解的控制。通過控制解的變化過程決定對(duì)解是否要做一定的改變。

（6）解的實(shí)施。指將解用到實(shí)際中必須考慮到實(shí)施的問題，如向?qū)嶋H部門講清解

的用法，在實(shí)施中可能產(chǎn)生的問題和所做的修改。

以上過程應(yīng)反復(fù)進(jìn)行。

1.5管理運(yùn)籌學(xué)的模型及建模思路

運(yùn)用運(yùn)籌學(xué)在解決問題時(shí)，按研究對(duì)象不同可構(gòu)造各種不同的模型。模型是現(xiàn)實(shí)世

界的抽象化反映，是研究者對(duì)客觀現(xiàn)實(shí)經(jīng)過思維抽象后用文字、圖表、符號(hào)、關(guān)系

式以及實(shí)體模樣描述所認(rèn)識(shí)到的客觀對(duì)象。運(yùn)籌學(xué)的實(shí)質(zhì)在于建立和使用模型來解

決實(shí)際問題。

模型有三種基本形式：形象模型、模擬模型和數(shù)學(xué)模型。物理復(fù)制被稱為形象模型

，如飛機(jī)模型等。模擬模型也是物理模型，但是在外形上與被建模的對(duì)象并不一樣

，如汽車上的速度表就是一種模擬模型。數(shù)學(xué)模型是以一些系統(tǒng)化的符號(hào)和數(shù)學(xué)表

達(dá)式或關(guān)系式來反映實(shí)際問題。目前運(yùn)籌學(xué)中用得最多的是數(shù)學(xué)模型。

如何將一個(gè)現(xiàn)實(shí)問題轉(zhuǎn)化為數(shù)學(xué)模型，也就是建模過程。運(yùn)籌學(xué)模型的幾個(gè)要素是

目標(biāo)函數(shù)、約束條件、決策變量。建立模型框架需要我們根據(jù)要解決的問題思考以

下幾個(gè)問題。

（1）我們需要什么目標(biāo)？

（2）通過調(diào)節(jié)哪些因素可以使得我們達(dá)到這一目標(biāo)？

（3）調(diào)節(jié)的因素是被動(dòng)的嗎？要與實(shí)際情況相符合有什么限制條件嗎？

（4）在實(shí)現(xiàn)目標(biāo)的過程中，有哪些約束條件？

（5）這樣建立的模型是相對(duì)完備的嗎？

對(duì)以上問題的回答只是提供了一種建立模型的基本框架結(jié)果，對(duì)于數(shù)學(xué)規(guī)劃類的建

模，這種思路也是很有效的。一旦建模和數(shù)據(jù)準(zhǔn)備工作已經(jīng)完成，我們就可以進(jìn)入

模型求解階段。

想要對(duì)模型求解就要求我們對(duì)算法有一個(gè)基本的認(rèn)識(shí)。算法是一系列解決問題的清

晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。算

法常常含有重復(fù)的步驟和一些比較或邏輯判斷。如果一個(gè)算法有缺陷或者不適合某

個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間

或效率來完成同樣的任務(wù)。

對(duì)運(yùn)籌學(xué)的學(xué)習(xí)，就是要有效率地解決問題，模型和算法的好壞直接影響這一目標(biāo)

的實(shí)現(xiàn)。對(duì)于算法的設(shè)計(jì)，方法有很多種，但步驟卻差別不大。舉個(gè)例子：你現(xiàn)在

要去一個(gè)地方，這時(shí)候你可能會(huì)考慮以下幾個(gè)問題。

（1）我現(xiàn)在在哪里？

（2）我將要去哪里？

（3）朝哪個(gè)方向走？

（4）選擇每次走多大一步？

一個(gè)迭代算法的思想和例子中的思想是一致的。迭代算法主要就是通過當(dāng)前點(diǎn)到下

一個(gè)點(diǎn)的變化來實(shí)現(xiàn)。先找到當(dāng)前點(diǎn)，這是我們新的起點(diǎn)，然后通過一定的規(guī)則到

達(dá)下一個(gè)點(diǎn)，以下一個(gè)點(diǎn)為當(dāng)前點(diǎn)，繼續(xù)后面的過程直至終止。對(duì)應(yīng)以上四個(gè)問題

，應(yīng)考慮以下幾點(diǎn)。

（1）初始點(diǎn)（我現(xiàn)在在哪里）。

（2）終止準(zhǔn)則（我的目標(biāo)是什么）。

（3）迭代方向（朝哪個(gè)方向走）。

（4）迭代步長（選擇每步走多遠(yuǎn)）。

對(duì)以上四個(gè)問題的回答實(shí)際上就是對(duì)運(yùn)籌學(xué)原理的探究。當(dāng)然，作為經(jīng)濟(jì)管理類專

業(yè)的學(xué)生，我們主要還是在了解這些算法思想的基礎(chǔ)上，能夠做到將這些方法應(yīng)用

到實(shí)際問題之中。

1.6管理運(yùn)籌學(xué)的計(jì)算工具

伴隨著計(jì)算機(jī)技術(shù)和信息技術(shù)的發(fā)展，作為運(yùn)籌學(xué)的求解工具也越來越多。主要分

為以下幾種。

（1）專業(yè)的優(yōu)化求解工具軟件。

MATLAB、SAS、Mathematica、SPSS、Lindo/Lingo、

GAMS等工具軟件，這些工具軟件大都是由企業(yè)開發(fā)的，需要具備一定的基礎(chǔ)，有

些軟件的安裝過程比較復(fù)雜，對(duì)使用者要求較高，但功能十分強(qiáng)大，適合于有一定

基礎(chǔ)或者有更多求解需求的操作者。

（2）隨相關(guān)書配送的專用軟件。

一般都封裝有十幾個(gè)或更多固定的分支數(shù)學(xué)模型，根據(jù)不同的數(shù)學(xué)模型特征，確定

了不同的操作，需要在使用前安裝。

（3）在Excel平臺(tái)下求解。

對(duì)每個(gè)運(yùn)籌學(xué)模型，可隨時(shí)在Excel工作表中創(chuàng)建求解界面，Excel能夠處理大量的

數(shù)據(jù)信息，特別適用于數(shù)字統(tǒng)計(jì)，而且能快速制定表格。對(duì)于一般關(guān)系的數(shù)學(xué)模型

，直接用數(shù)學(xué)模型的算法在Excel電子表格中做成求解模版，對(duì)于線性規(guī)劃這些特

殊的數(shù)學(xué)模型，可以在Excel電子表格中激活其中的專用模塊，并根據(jù)不同分支的

數(shù)學(xué)模型算法特征制作求解模版。對(duì)具體問題進(jìn)行求解時(shí)，只需將相關(guān)數(shù)據(jù)輸入到

相應(yīng)的單元格中，便可實(shí)現(xiàn)求解。

本書為適應(yīng)一般讀者的需求，采用Excel平臺(tái)對(duì)模型進(jìn)行求解。

?

第二章線性規(guī)劃及其應(yīng)用

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

線性規(guī)劃是運(yùn)籌學(xué)的重要分支，自從單純形法問世以來，得到了快速發(fā)展，目前已

經(jīng)在工業(yè)、農(nóng)業(yè)、國防、科技等領(lǐng)域得到了廣泛的應(yīng)用。單純形法的求解過程較為

煩瑣，本書主要側(cè)重理論的應(yīng)用，故在此只作介紹，不過多闡述。

應(yīng)用線性規(guī)劃模型求解實(shí)際問題時(shí)，首先要將實(shí)際問題抽象成數(shù)學(xué)模型，然后再對(duì)

其求解。對(duì)于一個(gè)實(shí)際問題，若要將其作為一個(gè)線性規(guī)劃問題來處理，必須建立與

實(shí)際問題對(duì)應(yīng)的線性規(guī)劃數(shù)學(xué)模型。

2.1.1線性規(guī)劃問題的提出

下面用兩個(gè)簡單的例子來說明如何建立線性規(guī)劃問題的數(shù)學(xué)模型。

例2-1某家具廠生產(chǎn)桌子和椅子兩種家具，如表2-1所示。

表2-1某家具廠生產(chǎn)家具的相關(guān)數(shù)據(jù)

問：企業(yè)應(yīng)如何安排生產(chǎn)計(jì)劃，使每月銷售收入最大化？

解：用數(shù)學(xué)語言來描述生產(chǎn)計(jì)劃的安排，這個(gè)過程稱為建立數(shù)學(xué)模型，簡稱建模。

設(shè)：桌子、椅子的生產(chǎn)數(shù)量為決策變量，分別用x1，x2表示。因?yàn)楫a(chǎn)量一般是非

負(fù)數(shù)，所以有x1，x2≥0，稱為非負(fù)約束。

（1）木工和油漆工可用的加工時(shí)間為限制條件，約束了產(chǎn)品的生產(chǎn)量x1，x2。

約束條件如下：

4x1+3x2≤120

2x1+x2≤50

（2）桌子、椅子的生產(chǎn)數(shù)量為x1，x2時(shí)所得總收入為z，顯然z=50x1

+30x2?？偸杖胫颠_(dá)到最大，用公式表達(dá)為：

maxz=50x1+30x2

把上述所有數(shù)學(xué)公式歸納如下：

maxz=50x1+30x2

這就是一個(gè)最大化的線性規(guī)劃模型。

例2-2

有一輛卡車，容積18立方米，載重2.5噸，用來裝載如下兩種貨物：箱裝件125千

克/個(gè)、0.4立方米/個(gè)；包裝件20千克/個(gè)、1.5立方米/個(gè)。

問：如何裝件，卡車所裝物件的個(gè)數(shù)最多？

解：根據(jù)題意，設(shè)箱裝件x1個(gè)，包裝件x2個(gè)。

需要滿足容積、載量約束條件，即：

容積約束0.4x1+1.5x2≤18

載量約束125x1+20x2≤2500

非負(fù)約束x1，x2≥0

目標(biāo)函數(shù)maxz=x1+x2

整理得到下面的形式：

maxz=x1+x2

上述兩例中所提出的問題，最終都?xì)w結(jié)為一組決策變量滿足線性規(guī)劃約束條件的前

提下，實(shí)現(xiàn)目標(biāo)函數(shù)最大或最小問題，這種問題稱為線性規(guī)劃問題。一個(gè)線性規(guī)劃

問題的數(shù)學(xué)模型包括三大部分：目標(biāo)函數(shù)、約束條件和決策變量。

2.1.2線性規(guī)劃數(shù)學(xué)模型

（1）線性規(guī)劃數(shù)學(xué)模型的特征。

①每一個(gè)問題都有一組決策變量xj（j=1，2，…，n），取值通常為非負(fù)。

②存在一些約束條件，這些約束條件可以用一組決策變量的線性等式或線性不等

式來表示。

③都有一個(gè)要求達(dá)到的目標(biāo)，他們可以用決策變量的線性函數(shù)來表示，按這個(gè)問

題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最小化或最大化。

滿足上述三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃模型，其數(shù)學(xué)語言描述為：

其中，式（1-1）稱為目標(biāo)函數(shù)，式（1-2）稱為約束條件，式（1-

3）稱為非負(fù)約束條件。式中，z稱為目標(biāo)，xj

（j=1，2，…，n）稱為決策變量，cj（j=1，2，…，n）稱為價(jià)值系數(shù)或目標(biāo)函數(shù)

系數(shù)，bi（i=1，2，…，m）稱為資源常數(shù)或約束右端常數(shù)，aij（i=1，2，…，m；

j=1，2，…，n）稱為技術(shù)系數(shù)或約束系數(shù)，cj，bi，aij均為常數(shù)。

（2）線性規(guī)劃的標(biāo)準(zhǔn)形式。

我們把滿足下列條件的線性規(guī)劃模型稱為線性規(guī)劃的標(biāo)準(zhǔn)形式，如下式所示：

線性規(guī)劃問題標(biāo)準(zhǔn)形式的條件：

①目標(biāo)函數(shù)為最大化類型。

②所有的決策變量取非負(fù)值。

③約束條件均由等式表示。

④每一約束等式的右端常數(shù)均為非負(fù)值。

（3）將線性規(guī)劃化成標(biāo)準(zhǔn)型的方法。

對(duì)于不符合標(biāo)準(zhǔn)型的線性規(guī)劃問題，可以通過下面的方法將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式

：

①對(duì)于minz型，令z′=-z。

②對(duì)于bi＜0，約束條件兩邊同乘-1。

③約束條件為“≤”時(shí)，左端加上一個(gè)松弛變量。

④約束條件為“≥”時(shí)，左端減去一個(gè)剩余變量。

⑤變量xj無約束時(shí)，令。

⑥變量xj≤0時(shí)，令。

2.2線性規(guī)劃的圖解法

例2-3

某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)

及A、B兩種原材料的消耗，如表2-2所示。

表2-2某工廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品的相關(guān)數(shù)據(jù)

該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問應(yīng)如何安

排計(jì)劃使該工廠獲利最多？這問題可以用以下的數(shù)學(xué)模型來描述，設(shè)x1、

x2分別表示在計(jì)劃期內(nèi)產(chǎn)品Ⅰ、

Ⅱ的產(chǎn)量。因?yàn)樵O(shè)備的有效臺(tái)時(shí)是8，這是一個(gè)限制產(chǎn)量的條件，所以在確定產(chǎn)品

Ⅰ、Ⅱ的產(chǎn)量時(shí)，要考慮不超過設(shè)備的有效臺(tái)時(shí)數(shù)，即可用不等式表示為：

x1+2x2≤8

同理，因原材料A、B的限量，可以得到以下不等式：

4x1≤16

4x2≤12

該工廠的目標(biāo)是在不超過所有資源限量的條件下，如何確定產(chǎn)量x1、x2以得到最

大利潤。若用z表示利潤，這時(shí)z=2x1+

3x2。綜合上述，該計(jì)劃問題可用數(shù)學(xué)模型表示為：

目標(biāo)函數(shù)maxz=2x1+3x2

滿足約束條件：

圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理?，F(xiàn)對(duì)上述例1-

3用圖解法求解。在以x1、x2為坐標(biāo)軸的直角坐標(biāo)系中，非負(fù)條件x1，x2≥0是指第

一象限。例1-3的每個(gè)約束條件都代表一個(gè)半平面。如約條件x1

+2x2≤8是代表以直線x1+

2x2=8為邊界的左下方的半平面，若同時(shí)滿足x1，x2≥0，x1

+2x2≤8，4x1≤16，和4x1≤12的約束條件的點(diǎn)，必然落在x1、

x2坐標(biāo)軸和由這三個(gè)半平面交成的區(qū)域內(nèi)。由例2-

3中的所有約束條件為半平面交成的區(qū)域，即陰影區(qū)域（見圖2-

2）。陰影區(qū)域中的每一個(gè)點(diǎn)（包括邊界點(diǎn)）都是這個(gè)線性規(guī)劃問題的解（稱可行

解），因而此區(qū)域是例2-3的線性規(guī)劃問題的解集合，稱它為可行域。

再分析目標(biāo)函數(shù)z=2x1+3x2在這坐標(biāo)平面上，它可表示以z為參數(shù)、-

2/3為斜率的一族平行線：

x2=-（2/3）x1+z/3

位于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值，因而稱它為“等值線”。當(dāng)z值由小

變大時(shí)，直線x2=-（2/3）x1+

z/3沿其法線方向向右上方移動(dòng)。當(dāng)移動(dòng)到Q2點(diǎn)時(shí)，使z值在可行域邊界上實(shí)現(xiàn)最

大化（見圖2-3），這就得到了例2-

3的最優(yōu)解Q2，Q2點(diǎn)的坐標(biāo)為（4，2）。于是可計(jì)算出滿足所有約束條件下的最

大值z(mì)=14。

圖2-1模型的可行解區(qū)域

圖2-2模型的求解過程

這說明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是生產(chǎn)4件產(chǎn)品Ⅰ和生產(chǎn)2件產(chǎn)品Ⅱ，可得最大利

潤為14元。

上例中求解得到問題的最優(yōu)解是唯一的，但對(duì)一般線性規(guī)劃問題，求解結(jié)果還可能

出現(xiàn)以下幾種情況。

（1）無窮多最優(yōu)解（多重最優(yōu)解）。

若將例2-3中的目標(biāo)函數(shù)變?yōu)榍髆axz=2x1

+3x2則表示目標(biāo)函數(shù)中以參數(shù)z的這族平行直線與約束條件x1

+2x2≤8的邊界線平行。當(dāng)z值由小變大時(shí)，將與線段Q1Q3重合（見圖2-

3）。線段Q2

Q3上任意一點(diǎn)都使z取得相同的最大值，這個(gè)線性規(guī)劃問題有無窮多最優(yōu)解（多重

最優(yōu)解）。

圖2-3無窮多最優(yōu)解

（2）無界解。

對(duì)下述線性規(guī)劃問題

maxz=x1+x2

用圖解法求解結(jié)果如圖2-4所示。從圖2-

4中可以看到，該問題可行域無界，目標(biāo)函數(shù)值可以增大到無窮大。稱這種情況為

無界解。

圖2-4無界解

（3）無可行解。

如果在例2-3的數(shù)學(xué)模型中增加一個(gè)約束條件-

2x1+x2≥4，該問題的可行域?yàn)榭占?，即無可行解，也不存在最優(yōu)解。

當(dāng)求解結(jié)果出現(xiàn)第2、

3兩種情況時(shí)，一般說明線性規(guī)劃問題的數(shù)學(xué)模型有錯(cuò)誤。前者缺乏必要的約束條

件，后者是有矛盾的約束條件，建模時(shí)應(yīng)注意。

從圖解法中直觀地見到，當(dāng)線性規(guī)劃問題的可行域非空時(shí)，它是有界或無界凸多邊

形。若線性規(guī)劃問題存在最優(yōu)解，它一定在有界可行域的某個(gè)頂點(diǎn)得到；若在兩個(gè)

頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的任意一點(diǎn)都是最優(yōu)解，即有無窮多最優(yōu)解。

圖解法雖然直觀、簡便，但當(dāng)變量數(shù)為三個(gè)或三個(gè)以上時(shí)，它就無能為力。所以在

2.3節(jié)中要介紹一種代數(shù)法——單純形法。

2.3單純形法

單純形法求解線性規(guī)劃的思路：一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方

程個(gè)數(shù)，這時(shí)有不定的解。但可以從線性方程組中找出每一個(gè)單純形，每一個(gè)單純

形可以求得一組解，然后再判斷該解使目標(biāo)函數(shù)值是增大還是變小，決定下一步選

擇的單純形。通過上述迭代步驟，直到目標(biāo)函數(shù)實(shí)現(xiàn)最大值或最小值。

單純形法的計(jì)算步驟：

①將線性規(guī)劃標(biāo)準(zhǔn)型化為線性規(guī)劃的規(guī)范型，來獲取一個(gè)初始可行解。

②將初始基可行解最優(yōu)性判別，若最優(yōu)，停止；否則轉(zhuǎn)一下步。

③從初始基可行解向相鄰的基可行解轉(zhuǎn)換，且使目標(biāo)值有所改善，重復(fù)第二步和

第三步直到找到最優(yōu)解。

2.4案例解析

關(guān)于線性規(guī)劃問題的求解，有許多軟件可以實(shí)現(xiàn)，但最簡便易行的求解軟件就是E

xcel。首先打開MicrosoftExcel

2010文件，在“文件”中選中“選項(xiàng)”，然后在“Excel選項(xiàng)”中單擊“加載項(xiàng)”，然后在“

Excel加載項(xiàng)”中，選中“規(guī)劃求解加載項(xiàng)”，單擊“轉(zhuǎn)到”，然后在數(shù)據(jù)選項(xiàng)卡中就有

規(guī)劃求解（見圖2-5）。

圖2-5規(guī)劃求解步驟（a）

圖2-5規(guī)劃求解步驟（b）

下面介紹如何在Excel中使用規(guī)劃求解。

（1）建立Excel工作表，將要求解模型中的每個(gè)組成部分放在Excel表格中，用每

一組單元格表示變量，作為可變單元格；用幾組單元格分別表示各約束條件和目標(biāo)

函數(shù)的系數(shù)；用一些單元格輸入公式表示各組系數(shù)和變量的關(guān)系。

例2-3的線性規(guī)劃模型求解步驟就可以在Excel中實(shí)現(xiàn)。

在圖2-6中用單元格B11：C11表示變量x1和x2，用單元格B3：

C3表示變量x1和x2在目標(biāo)函數(shù)中的系數(shù)，用單元格B6：C8表示變量x1和x2在約束

條件中的系數(shù)，用單元格D6：D8分別表示三個(gè)約束條件的左端項(xiàng)，用單元格F6：

F8分別表示三個(gè)約束條件的右端項(xiàng)，用單元格F11表示目標(biāo)函數(shù)。

圖2-6線性規(guī)劃模型求解的電子表格設(shè)置

對(duì)第一個(gè)約束條件的左端項(xiàng)x1+

x2，其在單元格中的表示是：在D6的位置上輸入“=SUMPRODUCT（B6：

C6，B11：C11）”（見圖2-7）。按照同樣的方式可以在D7、

D8的位置上如數(shù)所代表的約束條件4x1≤16和4x2≤

12的左端項(xiàng)，在F11的位置上輸入目標(biāo)函數(shù)2x1+3x2。

圖2-7線性規(guī)劃模型電子表格中的SUMPRODUCT函數(shù)

（2）打開“數(shù)據(jù)”欄中的“規(guī)劃求解參數(shù)”對(duì)話框，指定存有目標(biāo)函數(shù)的單元格為目

標(biāo)單元格，指定表示變量的單元格為可變單元格，建立約束條件（見圖2-8）。

圖2-8線性規(guī)劃模型表格的參數(shù)設(shè)置

在圖2-

8中指定單元格F11為目標(biāo)單元格，由已知條件可知目標(biāo)是最大化，所以需選中“最

大值”；指定B11：

C11為可變單元格，然后點(diǎn)擊“添加”按鈕就會(huì)彈出“添加約束”對(duì)話框，如圖2-

9所示。

圖2-9“添加約束”對(duì)話框

在“添加約束”對(duì)話框中，左端輸入的是約束條件的左端項(xiàng)，本例中即輸入的范圍是

D6：D8所代表的單元格，右端輸入的是約束條件的右端項(xiàng)，即F6：

F8所代表的單元格，對(duì)于兩邊中間的符號(hào)，有個(gè)菜單可以選擇“≤”或“=”或“≥”，這

樣約束條件已經(jīng)輸入完畢。若需要添加更多的約束條件，就點(diǎn)擊“添加”按鈕，然后

彈出一個(gè)新的“添加約束”對(duì)話框。若沒有其他約束條件需要添加，只要點(diǎn)擊“確定”

按鈕就回到“規(guī)劃求解參數(shù)”對(duì)話框。然后，在“是無約束變量為非負(fù)數(shù)”前打鉤，并

且選擇求解方法時(shí)選擇“單純線性規(guī)劃”，選項(xiàng)選取默認(rèn)值，再點(diǎn)擊“求解”按鈕，圖

2-8描述了在電子表格中建模的過程。

（3）在“規(guī)劃求解參數(shù)”對(duì)話框中點(diǎn)擊“求解”按鈕，即可求出最優(yōu)解和最優(yōu)值。在

一般情況下，都會(huì)出現(xiàn)圖2-

10所示的“規(guī)劃求解結(jié)果”對(duì)話框，它說明已經(jīng)找到最優(yōu)解。

圖2-10規(guī)劃求解結(jié)果對(duì)話框

如果模型無可行解或無最優(yōu)解，對(duì)話框會(huì)顯示“找不到可行解”或“設(shè)定的單元格值

未收斂”。對(duì)話框還會(huì)生成三個(gè)報(bào)告：運(yùn)算結(jié)果報(bào)告、敏感性報(bào)告和極限值報(bào)告。

例2-3的規(guī)劃求解結(jié)果如圖2-11所示。

圖2-11例2-3的規(guī)劃求解結(jié)果

從結(jié)果可以清晰地看出，通過Excel計(jì)算求出的結(jié)果與圖解法求出的結(jié)果是一致的

。

線性規(guī)劃在工商管理領(lǐng)域應(yīng)用廣泛，主要用于解決生產(chǎn)計(jì)劃安排、人力資源分配、

網(wǎng)絡(luò)配送、套裁下料、采購存儲(chǔ)、投資組合優(yōu)化等問題。

（一）生產(chǎn)計(jì)劃安排問題

公司面臨外包協(xié)作、

自行生產(chǎn)的問題。甲、乙、丙產(chǎn)品都需要經(jīng)過鑄造、機(jī)加工和裝配三道工序。鑄造

工序中甲、乙可外包，亦可自產(chǎn)，丙必須自產(chǎn)，其余工序必須本廠完成。相關(guān)數(shù)據(jù)

如表2-3所示。

表2-3公司生產(chǎn)甲、乙、丙產(chǎn)品的相關(guān)數(shù)據(jù)

續(xù)表

問：為獲取最大利潤，三種產(chǎn)品各生產(chǎn)多少件？甲、乙的鑄件有多少由本公司鑄造

？有多少由外包協(xié)作？

解：分析題中已知條件，不妨設(shè)x1、x2、

x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4、

x5分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。

求xi的利潤的公式：

利潤=售價(jià)-各成本之和

產(chǎn)品甲全部自制的利潤=23-（3+2+3）=15（元）

產(chǎn)品甲鑄造外協(xié)，其余自制的利潤=23-（5+2+3）=13（元）

產(chǎn)品乙全部自制的利潤=18-（5+1+2）=10（元）

產(chǎn)品乙鑄造外協(xié)，其余自制的利潤=18-（6+1+2）=9（元）

產(chǎn)品丙的利潤=16-（4+3+2）=7（元）

可得到xi，i=1，2，3，4，5的利潤分別為15、10、7、13、9元。

上述的問題就可以轉(zhuǎn)化成為如下的數(shù)學(xué)模型：

目標(biāo)函數(shù)：max15x1+10x2+7x3+13x4+9x5

滿足約束條件：

從上述模型可知，上述生產(chǎn)計(jì)劃問題可轉(zhuǎn)化對(duì)線性規(guī)劃模型的求解。

在圖2-12中用單元格B11：F11表示變量xi（i=1，2，3，4，5），用單元格B3：

F3表示變量xi（i=1，2，3，4，5）在目標(biāo)函數(shù)中的系數(shù)，用單元格B6：

F8表示變量xi（i=1，2，3，4，5）在約束條件中的系數(shù)，用單元格G6：

G8分別表示三個(gè)約束條件的左端項(xiàng)，用單元格I6：I8分別表示3個(gè)約束條件的右端

項(xiàng)，用單元格I11表示目標(biāo)函數(shù)。

圖2-12生產(chǎn)計(jì)劃問題轉(zhuǎn)化為線性規(guī)劃模型的求解電子表格設(shè)置

對(duì)第一個(gè)約束條件的左端項(xiàng)5x1+10x2+

7x3，其在單元格中的表示是：在G6的位置上輸入“=SUMPRODUCT（B6：

F6，B11：F11）”，如圖2-13。按照同樣的方式可以在G7、

G8的位置上如數(shù)所代表的約束條件6x1+4x2+8x3+4x4+4x5≤12000和3x1+2x2+

2x3+3x4+2x5≤10000的左端項(xiàng)，在I11的位置上輸入目標(biāo)函數(shù)15x1+10x2+7x3

+13x4+9x5。

圖2-13生產(chǎn)計(jì)劃問題轉(zhuǎn)化為線性規(guī)劃模型電子表格中的SUMPRODUCT函數(shù)

（2）打開“數(shù)據(jù)”欄中的“規(guī)劃求解參數(shù)”對(duì)話框，指定存有目標(biāo)函數(shù)的單元格為目

標(biāo)單元格，指定表示變量的單元格為可變單元格，建立約束條件（見圖2-14）。

在圖2-

15中指定單元格I11為目標(biāo)單元格，由已知條件可知目標(biāo)是最大化，所以需選中“最

大值”；指定B11：

F11為可變單元格，然后點(diǎn)擊“添加”按鈕就會(huì)彈出“添加約束”對(duì)話框，如圖2-

15所示。

圖2-14生產(chǎn)計(jì)劃問題轉(zhuǎn)化為線性規(guī)劃模型的表格的參數(shù)設(shè)置

圖2-15可變單元格的“添加約束”對(duì)話框

在“添加約束”對(duì)話框中，左端輸入的是約束條件的左端項(xiàng)，本例中即輸入的范圍是

G6：G8所代表的單元格，右端輸入的是約束條件的右端項(xiàng)，即I6：

I8所代表的單元格，對(duì)于兩邊中間的符號(hào)，選擇“≤”，這樣約束條件已經(jīng)輸入完畢

。點(diǎn)擊“確定”按鈕就回到“規(guī)劃求解參數(shù)”對(duì)話框。然后，在“是無約束變量為非負(fù)數(shù)

”前打鉤，并且選擇求解方法時(shí)選擇“單純線性規(guī)劃”，選項(xiàng)選取默認(rèn)值，然后點(diǎn)擊“

求解”按鈕，圖2-12描述了在電子表格中建模的過程。

（3）在“規(guī)劃求解參數(shù)”對(duì)話框中點(diǎn)擊“求解”按鈕，即可求出最優(yōu)解和最優(yōu)值。在

一般情況下，都會(huì)出現(xiàn)圖2-

16所示的“規(guī)劃求解結(jié)果”對(duì)話框，它說明已經(jīng)找到最優(yōu)解。規(guī)劃求解結(jié)果如圖2-

17所示。

圖2-16生產(chǎn)計(jì)劃問題轉(zhuǎn)化為線性規(guī)劃模型的規(guī)劃求解結(jié)果對(duì)話框

圖2-17生產(chǎn)計(jì)劃安排問題的規(guī)劃求解結(jié)果

從運(yùn)算的結(jié)果可以很清晰地看出，甲產(chǎn)品自產(chǎn)1600件，產(chǎn)品乙他產(chǎn)600件，才能保

證獲得最大利潤29400元。

（二）人力資源安排問題

百貨商場對(duì)售貨員的需求如下表。要求售貨員每周工作五天，連續(xù)休息兩天。相關(guān)

數(shù)據(jù)資料如表2-4所示。

問：應(yīng)該如何安排售貨員，滿足工作需要，同時(shí)使配備的售貨員人數(shù)最少？

表2-4相關(guān)數(shù)據(jù)資料

解：設(shè)xi（i=1，2，…，7）表示星期i開始休息的人數(shù)，建立如下的數(shù)學(xué)模型。

目標(biāo)函數(shù)：minx1+x2+x3+x4+x5+x6+x7

約束條件：

從模型可知，上述人力資源安排問題可轉(zhuǎn)化對(duì)線性規(guī)劃模型的求解。

在圖2-18中用單元格B14：H14表示變量xi

（i=1，2，3，4，5，6，7），用單元格B3：H3表示變量xi

（i=1，2，3，4，5，6，7）在目標(biāo)函數(shù)中的系數(shù)，用單元格B5：H11表示變量xi

（i=1，2，3，4，5，6，7）在約束條件中的系數(shù)，用單元格I5：

I11分別表示7個(gè)約束條件的左端項(xiàng)，用單元格K5：

K11分別表示7個(gè)約束條件的右端項(xiàng)，用單元格K14表示目標(biāo)函數(shù)。

圖2-18人力資源安排問題轉(zhuǎn)化為線性規(guī)劃模型的求解電子表格設(shè)置

對(duì)第一個(gè)約束條件的左端項(xiàng)x2，x3，x4，x5

，x6，其在單元格中的表示是：在I5的位置上輸入“=SUMPRODUCT（B5：

H5，B14：H14）”（見圖2-19）。按照同樣的方式可以在I6、I7、I8、I9、

I10和I11的位置上如數(shù)所代表的其他6個(gè)約束條件的左端項(xiàng)，在K14的位置上輸入

目標(biāo)函數(shù)x1+x2+x3+x4+x5+x6+x7。

圖2-19人力資源安排問題轉(zhuǎn)化為線性規(guī)劃模型電子表格中的SUMPRODUCT函數(shù)

打開“數(shù)據(jù)”欄中的“規(guī)劃求解參數(shù)”對(duì)話框，指定存有目標(biāo)函數(shù)的單元格為目標(biāo)單元

格，指定表示變量的單元格為可變單元格，建立約束條件。

在圖2-

20中指定單元格K14為目標(biāo)單元格，由已知條件可知目標(biāo)是最小化，所以需選中“

最小值”；指定B14：

H14為可變單元格，然后點(diǎn)擊“添加”按鈕就會(huì)彈出“添加約束”對(duì)話框，如圖2-

21所示。

圖2-20人力資源安排問題轉(zhuǎn)化為線性規(guī)劃模型的表格的參數(shù)設(shè)置

圖2-21指定的可變單元格的“添加約束”對(duì)話框

在“添加約束”對(duì)話框中，左端輸入的是約束條件的左端項(xiàng)，本例中即輸入的范圍是

I5：I11所代表的單元格，右端輸入的是約束條件的右端項(xiàng)，即K5：

K11所代表的單元格，對(duì)于兩邊中間的符號(hào)，選擇“≥”，這樣約束條件已經(jīng)輸入完

畢。點(diǎn)擊“確定”按鈕就回到“規(guī)劃求解參數(shù)”對(duì)話框。然后，在“是無約束變量為非負(fù)

數(shù)”前打鉤，并且選擇求解方法時(shí)選擇“單純線性規(guī)劃”，選項(xiàng)選取默認(rèn)值，然后點(diǎn)

擊“求解”按鈕，圖2-18描述了在電子表格中建模的過程。

在“規(guī)劃求解參數(shù)”對(duì)話框中點(diǎn)擊“求解”按鈕，即可求出最優(yōu)解和最優(yōu)值。在一般情

況下，都會(huì)出現(xiàn)“規(guī)劃求解結(jié)果”對(duì)話框（見圖2-

22），它說明已經(jīng)找到最優(yōu)解。規(guī)劃求解結(jié)果如圖2-23所示。

圖2-22人力資源安排問題轉(zhuǎn)化為線性規(guī)劃模型的規(guī)劃求解結(jié)果對(duì)話框

圖2-23本例的規(guī)劃求解結(jié)果

從運(yùn)算的結(jié)果可以很清晰地看出，星期一開始休息的12人，星期三開始休息的人

數(shù)為11人，星期四開始休息的人數(shù)為5人，星期六開始休息人為8人，其他時(shí)間無

休息人，才能保證需要的售貨員人數(shù)最少，需要36人。

（三）套裁下料問題

工廠要做100套鋼架，每套用長為2.9米，2.1米，1.5米的圓鋼各一根。已知原料每

根長7.4米，問：應(yīng)如何下料，可使所用原料最??？

解：列出所有可能下料方案，如表2-5所示。

表2-5鋼架下料的所有可能方案

不妨設(shè)按上述方案下料的原材料根數(shù)分別為xi

（i=1，2，3，4，5，6，7，8），可考慮建立如下的數(shù)學(xué)模型。

目標(biāo)函數(shù)：minx1+x2+x3+x4+x5+x6+x7+x8

約束條件：

類似于前兩個(gè)實(shí)驗(yàn)，這里只給出相應(yīng)的過程圖，不再做詳細(xì)說明。

首先，制作模型的電子表格，如圖2-24所示。

圖2-24套裁下料問題轉(zhuǎn)化為模型的電子表格設(shè)置

其次，在電子表格中填入約束條件，如圖2-25所示。

圖2-25套裁下料問題轉(zhuǎn)化為模型的電子表格中的SUMPRODUCT函數(shù)

再次，設(shè)置表格參數(shù)，添加約束條件，如圖2-26所示。

圖2-26套裁下料問題轉(zhuǎn)化為模型的表格的參數(shù)設(shè)置

最后，進(jìn)行求解，如圖2-27所示。

圖2-27套裁下料問題的求解結(jié)果

從結(jié)果可以很清晰地看出，需要30根圓鋼按照方案1套裁，需要10根圓鋼按照方案

2套裁，需要50根圓鋼按照方案4套裁，共需要90根圓鋼就可以滿足例題中的需求

。

運(yùn)籌學(xué)在工商管理領(lǐng)域里的其他應(yīng)用，在此不再一一列出，所有問題的關(guān)鍵就在于

構(gòu)建模型，然后按照上述步驟都可以用Excel進(jìn)行求解。

習(xí)題

1.將下列線性規(guī)劃模型轉(zhuǎn)換為標(biāo)準(zhǔn)形式。

（1）maxz=x1+4x2-x3

（2）minz=9x1-3x2+5x3

2.圖解線性規(guī)劃問題，并指出該問題是具有唯一最優(yōu)解、無窮多最優(yōu)解、無界解還

是無形可行解。

（1）minz=-2x1+x2

（2）maxz=-x1-3x2

（3）maxz=-3x1+2x2

（4）maxz=x1+x2

3.某化工廠生產(chǎn)某項(xiàng)化學(xué)產(chǎn)品，每單位標(biāo)準(zhǔn)重量為1000克，由A、B、

C三種化學(xué)物混合而成。產(chǎn)品組成成分是每單位產(chǎn)品中A不超過300克，B不少于15

0克，C不少于200克。A、B、

C每克成本分別為5元、6元、7元。問如何配置此化學(xué)產(chǎn)品，才能使成本最低？

4.某產(chǎn)品重量為150千克，用A、

B兩種原料制成。每單位A原料成本為2元，每單位B原料成本為8元。該產(chǎn)品至少需

要含14單位B原料，最多含20單位A原料。每單位A、

B原料分別重5千克、10千克，為使成本最小，該產(chǎn)品中A、B原料應(yīng)各占多少？

5.設(shè)某工廠有甲、乙、丙、丁四臺(tái)機(jī)床，生產(chǎn)A、B、C、D、

E、F六種產(chǎn)品。加工每一件產(chǎn)品所需要時(shí)間和每一件產(chǎn)品的單價(jià)如表2-6所示。

表2-6工廠相關(guān)數(shù)據(jù)表

表中沒有填數(shù)的表示該機(jī)床不參加生產(chǎn)這種產(chǎn)品。現(xiàn)假設(shè)在某一時(shí)間內(nèi)，甲、乙、

丙、丁四臺(tái)機(jī)床的最大工作能力分別為850、700、600、

900工時(shí)，問這一時(shí)段內(nèi)，每種產(chǎn)品各應(yīng)生產(chǎn)多少，才能使該廠總收入最大化？

6.一家玩具公司制造三種玩具，每一種要求不同的制造技術(shù)。高級(jí)的一種需要17個(gè)

小時(shí)加工裝配，8小時(shí)檢測，每臺(tái)利潤30元；中級(jí)的需2小時(shí)加工裝配，半小時(shí)檢

測，每臺(tái)利潤5元；低級(jí)的需半小時(shí)加工裝配，10分鐘檢測，每臺(tái)利潤1元?，F(xiàn)公

司可供利用的加工裝配時(shí)間為500小時(shí)，檢測時(shí)間100小時(shí)。市場預(yù)測顯示，對(duì)高

級(jí)、中級(jí)、低級(jí)玩具的需求量分別不超過10臺(tái)、30臺(tái)、100臺(tái)，試制訂一個(gè)能夠使

總利潤最大的生產(chǎn)計(jì)劃。

7.A、

B兩種產(chǎn)品，都需要經(jīng)過前后兩道工序加工，每一個(gè)單位產(chǎn)品A需要前道工序1小時(shí)

和后道工序有2小時(shí)，每一個(gè)單位產(chǎn)品B需要前道工序2小時(shí)和后道工序3小時(shí)?？?/p>

供利用的前道工序有11小時(shí)，后道工序有17小時(shí)。

每加工一個(gè)單位產(chǎn)品B的同時(shí)，會(huì)產(chǎn)生兩個(gè)單位的副產(chǎn)品C，且不需要任何費(fèi)用，

產(chǎn)品C一部分可售出盈利，其余只能銷毀。

出售單位產(chǎn)品A、B、C的利潤分別為3、7、

2元，每單位產(chǎn)品C的銷毀費(fèi)為1元，預(yù)測表明，產(chǎn)品C最多只能銷售13個(gè)單位，試

建立使利潤最大的生產(chǎn)計(jì)劃的數(shù)學(xué)模型。

8.某企業(yè)生產(chǎn)甲、乙、丙三種產(chǎn)品，其每單位所消耗工時(shí)分別為1.6小時(shí)、2.0小時(shí)

、2.5小時(shí)，每單位所需原料A分別為24千克、20千克、12千克，所需原料B分別為

14千克、10千克、18千克。生產(chǎn)線每月正常工作時(shí)間為240小時(shí)，原料A、

B的總供應(yīng)量限制為2400千克和1500千克。生產(chǎn)一個(gè)甲、乙、丙產(chǎn)品各可獲利潤5

25元、678元、812元，試分別建立以下兩種情況下的數(shù)學(xué)模型，不需要計(jì)算。

（1）由于每單位丙產(chǎn)品的生產(chǎn)會(huì)產(chǎn)生5千克副產(chǎn)品丁，這些副產(chǎn)品丁一部分可以

銷售，利潤為300元/千克，剩下的會(huì)造成污染，每千克需要排污費(fèi)200元。副產(chǎn)品

丁的需求量為每月不超過150千克。應(yīng)如何確定生產(chǎn)計(jì)劃，可使總利潤最大？

（2）工廠考慮到產(chǎn)品丙有污染，決定不生產(chǎn)丙而準(zhǔn)備在另外的三種產(chǎn)品W、Q、G

中選擇1種或2種進(jìn)行生產(chǎn)，它們所消耗工時(shí)、所需原料A、B及利潤如表2-

7所示。

表2-7工廠相關(guān)資源表

應(yīng)如何確定生產(chǎn)計(jì)劃，可使總利潤最大？

?

第三章運(yùn)輸問題

運(yùn)輸問題實(shí)際上是一種線性規(guī)劃問題，當(dāng)然可以考慮采用單純形法求解，但本書是

實(shí)驗(yàn)教程，更多側(cè)重于方法的應(yīng)用，所以在闡明理論之后，可采用Excel軟件進(jìn)行

求解。

3.1運(yùn)輸問題及數(shù)學(xué)模型

運(yùn)籌學(xué)研究領(lǐng)域中的運(yùn)輸問題，則主要是研究單一的運(yùn)輸對(duì)象費(fèi)率確定的運(yùn)輸網(wǎng)絡(luò)

中的整體配送效率問題。

一般來講，運(yùn)輸問題可以這樣描述。設(shè)有m個(gè)產(chǎn)地Ai，各地的產(chǎn)量為Si，n個(gè)銷地Bj

，各地的銷量分別是dj，把某物從產(chǎn)地Ai運(yùn)至銷地Bj的運(yùn)輸費(fèi)率為cij，如何安排運(yùn)

量，才能在產(chǎn)銷平衡的前提下達(dá)到總運(yùn)輸費(fèi)用最小。設(shè)xij表示從產(chǎn)地Ai調(diào)運(yùn)到Bj的

運(yùn)量，z是總運(yùn)輸費(fèi)用。產(chǎn)銷平衡表和單位運(yùn)價(jià)表如表3-1和表3-2所示。

表3-1運(yùn)輸量表

表3-2單位運(yùn)價(jià)表

在產(chǎn)銷平衡的條件下，上述問題可轉(zhuǎn)化為數(shù)學(xué)模型：

當(dāng)產(chǎn)銷不平衡時(shí)，會(huì)出現(xiàn)下面兩種情況。

（1）當(dāng)產(chǎn)量大于銷量時(shí)，可假想倉庫為另一個(gè)銷地B，可將產(chǎn)銷不平衡問題轉(zhuǎn)化

為產(chǎn)銷平衡問題，只不過倉庫的單位運(yùn)價(jià)為零。

（2）當(dāng)產(chǎn)量小于銷量時(shí)，假想添加一個(gè)生產(chǎn)地，即多一個(gè)A，可將產(chǎn)銷不平衡問

題轉(zhuǎn)化為產(chǎn)銷平衡問題，假想生產(chǎn)地的單位運(yùn)價(jià)為零。

上述運(yùn)輸問題具有以下兩個(gè)特點(diǎn)。

（1）變量xij的悉數(shù)列向量只有兩個(gè)分量為1，其余的都為零。

（2）相互獨(dú)立的約束方程的個(gè)數(shù)為m+n-1個(gè)。

正因?yàn)閮蓚€(gè)特點(diǎn)，可找到比單純形法更為簡單的方法進(jìn)行求解，這種方法就是表上

作業(yè)法。

3.2表上作業(yè)法

表上作業(yè)法的求解步驟與單純形法求解步驟類似，具體步驟如下。

（1）寫出運(yùn)輸問題的表格形式，即產(chǎn)銷平衡表和單位運(yùn)價(jià)表。

（2）確定初始調(diào)運(yùn)方案（相當(dāng)于確定初始可行解）。

（3）檢驗(yàn)方案是否最優(yōu)（相當(dāng)于最優(yōu)性判別），若是最優(yōu)，停止計(jì)算；若不是，

則繼續(xù)。

（4）調(diào)整調(diào)運(yùn)方案，得到新方案。

（5）重復(fù)步驟（3）和（4），直到求出最優(yōu)調(diào)運(yùn)方案。

例3-1

石家莊北方研究院有三個(gè)區(qū)，即一區(qū)、二區(qū)、三區(qū)，每年分別需要用煤3000噸、1

000噸、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，這兩處煤礦的價(jià)格相

同、質(zhì)量相同。山西盂縣供煤4000噸，河北臨城1500噸。單位運(yùn)價(jià)如表3-

3所示，求最低總運(yùn)費(fèi)。

表3-3例3-1的單位運(yùn)價(jià)表

解：

首先，做出產(chǎn)銷平衡與運(yùn)價(jià)表，如表3-4所示。

表3-4產(chǎn)銷平衡和單位運(yùn)價(jià)表

續(xù)表

這里假設(shè)運(yùn)輸單價(jià)M為一個(gè)很大的正數(shù)，這樣就保證了M*

（相應(yīng)運(yùn)輸量x）也是一個(gè)很大的正數(shù)，這顯然不符合總運(yùn)費(fèi)最小的目標(biāo)，所以（

相應(yīng)的運(yùn)輸量x）

=0。了解原理后，在使用軟件計(jì)算時(shí)，輸入M時(shí)不能輸入字母M，而是需要輸入一

個(gè)很大的數(shù)，比如1000，再求得最后結(jié)果。

然后是比較難的，運(yùn)輸問題的表上作業(yè)法，其實(shí)質(zhì)是單純形法，“套路”與單純形法

類似，先求出基解（在圖像上顯示為頂點(diǎn)），然后再比較哪一個(gè)基解是最優(yōu)的。

求解過程如下：

（1）確定初始基本可行解的方法為最小元素法、西北角法（左上角法、階梯法）

、最大差額法（Vogel概算法、伏格爾法）。Russell概算法。

（2）最優(yōu)解的判別。

（3）改進(jìn)運(yùn)輸方案。

本節(jié)以最小元素法為例描述整個(gè)求解過程，其他方法不再逐一列舉。

（1）確定初始基本可行解。

這里的“最小元素”指的是最小運(yùn)價(jià)cij。不同產(chǎn)地銷售到同一銷地的運(yùn)價(jià)不同，考慮

到運(yùn)費(fèi)最低，肯定選擇運(yùn)價(jià)最低的滿足這一銷地，實(shí)際情況一般是先把離某一銷地

最近產(chǎn)地的產(chǎn)品拿去銷地，即就近的先運(yùn)。可考慮從下面一個(gè)比較簡單的例題去體

會(huì)最小元素法，如表3-5所示。

表3-5最小元素法操作步驟表（1）

首先，在表3-

5中粗線框的數(shù)字中找最小的數(shù)字，即最小的單位運(yùn)價(jià)，也就是1，對(duì)應(yīng)的是A2到B

1的單位運(yùn)價(jià)。以1的單位運(yùn)價(jià)滿足銷地B1銷量3的x21=3。

表3-6最小元素法操作步驟表（2）

因?yàn)锽1的銷量滿足了，所以劃去B1列。而A2的產(chǎn)量4給了B1產(chǎn)量3之后還剩產(chǎn)量1

，給單位運(yùn)價(jià)第二低的2，在該單元格的右上角于寫上①。于是A2的產(chǎn)量全部分配

完，劃去該行，x23=1。

表3-7最小元素法操作步驟表（3）

接著看剩下的最小運(yùn)費(fèi)，為A1行的3，將A1產(chǎn)量7分配給B3的銷量5-

1=4，還剩下3全分配給B4，劃去A1行x13=4，x14=3。

表3-8最小元素法操作步驟表（4）

然后看剩下的最小運(yùn)費(fèi)，為A3行的4，以A3的產(chǎn)量9給B2的銷量6，劃去B2列，x32

=6。剩下3，分配給A3行的最小數(shù)5，于是B4銷量也滿足，劃去B4列，x34=3。

A3的產(chǎn)量全部分配完，劃去A3行。

表3-9最小元素法操作步驟表（5）

全部劃去后，在運(yùn)價(jià)表的基礎(chǔ)上寫上運(yùn)量表。

表3-10最小元素法操作步驟表（6）

從表中可以清晰地看出x21=3，x23=1

，x13=4，x14=3，x32=6，x34=3。這就是最小元素法的求解過程。

（2）最優(yōu)解的判別。

通過步驟（1）得出的方案往往不是最優(yōu)的，需要對(duì)最優(yōu)性進(jìn)行判別。對(duì)方案最優(yōu)

性的判別就是求出各個(gè)非基變量的檢驗(yàn)數(shù)，如果都滿足大于等于零，就說明任何一

個(gè)空格處增加一個(gè)單位，總運(yùn)費(fèi)就要增加，正好說明當(dāng)前方案的最優(yōu)性，如果不是

，要對(duì)方案進(jìn)行調(diào)整。

（3）改進(jìn)運(yùn)輸方案。

如果得到的方案不是最優(yōu)，可采用閉合回路法對(duì)方案進(jìn)行調(diào)整，詳見其他運(yùn)籌學(xué)理

論教程，本書不再一一闡明。

3.3案例解析

例3-2某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、

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

表3-11所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。?/p>

表3-11例3-2的運(yùn)價(jià)表

解：從題中已知條件可知：該問題是產(chǎn)銷平衡的運(yùn)輸問題，故可采用Excel中線性

規(guī)劃方法進(jìn)行求解。

上述問題的電子表格建模如圖3-1所示。

圖3-1例3-2的建模電子表格

分別在F11、F12輸入sum函數(shù)，作為產(chǎn)地的供應(yīng)求和，同理在C13、D13、

E13位置輸入sum函數(shù)，作為銷地的銷量求和。同時(shí)在H13位置輸入sumproduct函

數(shù)，作為總運(yùn)費(fèi)的求和，如圖3-2所示。

圖3-2電子表格中的sum和SUMPRODUCT函數(shù)設(shè)置

打開“數(shù)據(jù)”欄中的“規(guī)劃求解參數(shù)”對(duì)話框，指定存有目標(biāo)函數(shù)的單元格為目標(biāo)單元

格，指定表示變量的單元格為可變單元格，建立約束條件（見圖3-3）。

圖3-3例3-2電子表格的參數(shù)設(shè)置

在圖3-

3中指定單元格H13為目標(biāo)單元格，由已知條件可知目標(biāo)是最小化，所以需選中“最

小值”；指定C11：

E12為可變單元格，然后點(diǎn)擊“添加”按鈕就會(huì)彈出“添加約束”對(duì)話框，把C13：

E13=C15：E15和F11：F12=H11：

H12添加到約束條件對(duì)話框，在“是無約束變量為非負(fù)數(shù)”前打鉤，并且選擇求解方

法時(shí)選擇“單純線性規(guī)劃”，選項(xiàng)選取默認(rèn)值，然后點(diǎn)擊“求解”按鈕，就可得到本案

例的最優(yōu)解，如圖3-4所示。

圖3-4例3-2的規(guī)劃求解結(jié)果

從圖3-

4可知，產(chǎn)地A1供應(yīng)銷地B1和B250和150單位的產(chǎn)品，產(chǎn)地A2分別供應(yīng)銷地B1和B

3100和200單位的產(chǎn)品，這樣的調(diào)運(yùn)方案可使得總運(yùn)費(fèi)最低，共花費(fèi)2500元。

運(yùn)用Excel中的線性規(guī)劃模塊對(duì)例3-1進(jìn)行求解。

解：從題中已知條件可知：該問題是產(chǎn)銷不平衡的運(yùn)輸問題，可先增加一個(gè)假想產(chǎn)

地，然后構(gòu)建表3-

4一樣的產(chǎn)銷平衡的運(yùn)輸問題，M值可以設(shè)為一個(gè)具體的數(shù)字，比如1000，故可采

用Excel中線性規(guī)劃方法進(jìn)行求解。

上述問題的電子表格建模如圖3-5所示。

圖3-5建模電子表格

分別在F12、F13和F14處輸入sum函數(shù)，作為產(chǎn)地的供應(yīng)求和，同理在C17、

D17、

E17位置輸入sum函數(shù)，作為銷地的需求量求和。同時(shí)在H15位置輸入SUMPRODUC

T函數(shù)，作為總運(yùn)費(fèi)的求和。

打開“數(shù)據(jù)”欄中的“規(guī)劃求解參數(shù)”對(duì)話框，指定存有目標(biāo)函數(shù)的單元格為目標(biāo)單元

格，指定表示變量的單元格為可變單元格，建立約束條件。

在圖3-

6中指定單元格H15為目標(biāo)單元格，由已知條件可知目標(biāo)是最小化，所以需選中“最

小值”；指定C12：

E14為可變單元格，然后點(diǎn)擊“添加”按鈕就會(huì)彈出“添加約束”對(duì)話框，把C15：E15

=C17：E17和F12：F14=H12：

H14添加到約束條件對(duì)話框，然后在“是無約束變量為非負(fù)數(shù)”前打鉤，并且選擇求

解方法時(shí)選擇“單純線性規(guī)劃”，選項(xiàng)選取默認(rèn)值，然后點(diǎn)擊“求解”按鈕，就可得到

本案例的最優(yōu)解，如圖3-7所示。

圖3-6電子表格的參數(shù)設(shè)置

圖3-7例3-1的規(guī)劃求解結(jié)果

從圖3-

7可知，產(chǎn)地山西盂縣供應(yīng)石家莊北方研究院一區(qū)和二區(qū)的煤炭量分別為3000噸和

1000噸，產(chǎn)地河北臨城供應(yīng)石家莊北方研究院三區(qū)1500噸煤炭，減去假想生產(chǎn)地

生產(chǎn)的500噸煤炭運(yùn)往三區(qū)所耗的費(fèi)用500000元，這樣的調(diào)運(yùn)方案可使得總運(yùn)費(fèi)最

低，共花費(fèi)9200元。

例3-3已知某運(yùn)輸問題的產(chǎn)銷平衡表與單位運(yùn)價(jià)表如表3-

12所示，試求最優(yōu)的調(diào)撥方案。

表3-12產(chǎn)銷平衡表及單位運(yùn)價(jià)表

解：從題中已知條件可知：該問題中產(chǎn)地的產(chǎn)量和銷地的銷量是相等的，因此屬于

產(chǎn)銷平衡的運(yùn)輸問題，故可采用Excel中線性規(guī)劃方法進(jìn)行求解。

上述問題的電子表格建模如圖3-8所示。

圖3-8例3-3的建模電子表格

分別在H12、

H13和H14輸入sum函數(shù)，對(duì)所在行求和，作為各產(chǎn)地的供應(yīng)求和，同理在C15、

D15、E15、

F15和G15位置輸入sum函數(shù)，對(duì)表格所在列求和，作為各銷地的銷量。同時(shí)在J15

位置輸入SUMPRODUCT函數(shù)，作為總運(yùn)費(fèi)的求和，如圖3-8所示。

打開“數(shù)據(jù)”欄中的“規(guī)劃求解參數(shù)”對(duì)話框，指定存有目標(biāo)函數(shù)的單元格為目標(biāo)單元

格，指定表示變量的單元格為可變單元格，建立約束條件。

圖3-9例3-3的電子表格的參數(shù)設(shè)置

在圖3-

9中指定單元格J15為目標(biāo)單元格，由已知條件可知目標(biāo)是最小化，所以需選中“最

小值”；指定C12：G14為可變單元格，然后點(diǎn)擊“添加”按鈕就會(huì)彈出“添加約束”對(duì)

話框，把H12：H14=J12：J14和C15：G15=C17：

G17添加到約束條件對(duì)話框，在“是無約束變量為非負(fù)數(shù)”前打鉤，并且選擇求解方

法時(shí)選擇“單純線性規(guī)劃”，選項(xiàng)選取默認(rèn)值，然后點(diǎn)擊“求解”按鈕，就可得到本案

例的最優(yōu)解，求解結(jié)果如圖3-10所示。

圖3-10求解結(jié)果

從圖3-10可知，產(chǎn)地1供應(yīng)銷地A、B和E的產(chǎn)品數(shù)量分別為10、

10和30，產(chǎn)地2供應(yīng)銷地B和C的產(chǎn)品數(shù)量分別為10和30，產(chǎn)地3供應(yīng)銷地A和D的產(chǎn)

品數(shù)量分別為20和40，這樣的調(diào)運(yùn)方案最優(yōu)，可使得總運(yùn)費(fèi)最低，共花費(fèi)320元。

習(xí)題

1.設(shè)有三個(gè)化肥廠（A、B、C）供應(yīng)四個(gè)地區(qū)（Ⅰ、

Ⅱ、Ⅲ、Ⅳ）的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年

產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如表3-

13所示。試求出最節(jié)省總運(yùn)費(fèi)的化肥調(diào)撥方案。

表3-13運(yùn)價(jià)表

2.某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、

20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如

表3-

14所示。又如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、

維護(hù)等費(fèi)用0.15萬元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)（包括儲(chǔ)存

、維護(hù)）費(fèi)用最小的決策。

表3-14生產(chǎn)能力及單位成本表

3.某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、

F的四條固定航線的物資運(yùn)輸任務(wù)。已知各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)

如表3-15所示。假定各條航線使用相同型號(hào)的船只，又各城市間的航程天數(shù)如表3-

16所示。又知每條船只每次裝卸貨的時(shí)間各需1天，則該航運(yùn)公司至少應(yīng)配備多少

條船，才能滿足所有航線的運(yùn)貨需求？

表3-15各條航線基本信息表

表3-16各城市間航程天數(shù)表

4.某百貨公司去外地采購A、B、C、D四種規(guī)格的服裝，數(shù)量分別為：A——

1500套，B——2000套，C——3000套，D——

3500套。有三個(gè)城市可供應(yīng)上述規(guī)格服裝，各城市供應(yīng)數(shù)量分別為：I——

2500套，Ⅱ——2500套，Ⅲ——

5000套。由于這些城市的服裝質(zhì)量、運(yùn)價(jià)和銷售情況不同，預(yù)計(jì)售出后的利潤（

元/套）也不同，如表3-

17所示。請(qǐng)幫助該公司確定一個(gè)預(yù)期盈利最大的采購方案。

表3-17百貨公司相關(guān)數(shù)據(jù)表

5.甲、乙、丙三個(gè)城市每年需要煤炭的數(shù)量分別為：320萬噸、250萬噸、350萬噸

，由A、B兩處煤礦負(fù)責(zé)供應(yīng)。已知煤炭年供應(yīng)量分別為：A——400萬噸，B——

450萬噸。煤礦至各城市的單位運(yùn)價(jià)（萬元/萬噸）如表3-

18所示。由于需大于供，經(jīng)研究平衡決定，甲城市供應(yīng)量可減少0～30萬噸，乙城

市需要量應(yīng)全部滿足，丙城市供應(yīng)量不少于270萬噸。試求將供應(yīng)量分配完又使總

運(yùn)費(fèi)為最低的調(diào)運(yùn)方案。

表3-18煤炭調(diào)運(yùn)價(jià)格表

6.某造船廠根據(jù)合同要從當(dāng)年起，連續(xù)三年年末各提供三條規(guī)格型號(hào)相同的大型客

貨輪。已知該廠這三年內(nèi)生產(chǎn)大型客貨輪的能力及每艘客貨輪成本如表3-19所示。

表3-19造船廠生產(chǎn)能力及成本表

已知加班生產(chǎn)時(shí)，每艘客貨輪成本比正常生產(chǎn)時(shí)高出70萬元。又知造出來的客貨

輪如當(dāng)年不交貨，每艘每積壓一年造成積壓損失為40萬元。在簽訂合同時(shí)，該廠

已儲(chǔ)存了兩艘客貨輪，而該廠希望在第三年末完成合同后還能儲(chǔ)存一艘備用。問該

廠應(yīng)如何安排每年客貨輪的生產(chǎn)量，使在滿足上述各項(xiàng)要求的情況下，總的生產(chǎn)費(fèi)

用加積壓損失為最少？

7.某公司在3個(gè)地方有3個(gè)分廠，生產(chǎn)同一種產(chǎn)品，其產(chǎn)量分別為300箱、400箱、5

00箱。需要供應(yīng)4個(gè)銷地的銷售，這4個(gè)銷地的產(chǎn)品需求分別為400箱、250箱、55

0箱。3個(gè)分廠到4個(gè)銷地的單位運(yùn)價(jià)如表3-20所示。

表3-203個(gè)分廠到4個(gè)銷地的單位運(yùn)價(jià)表

（1）應(yīng)如何安排運(yùn)輸方案，使得總運(yùn)費(fèi)為最小？

（2）如果2分廠的產(chǎn)量從400箱提高到了600箱，那么應(yīng)如何安排運(yùn)輸方案，使得

總運(yùn)費(fèi)為最??？

（3）如果銷地甲的需求從400箱提高到550箱，而其他情況都同a，那該如何安排

運(yùn)輸方案，使得運(yùn)費(fèi)為最??？

8.某公司有甲、乙、丙、丁四個(gè)分廠生產(chǎn)同一種產(chǎn)品。產(chǎn)量為300、500、400、

10