運(yùn)籌學(xué)教案設(shè)計(jì)

管理科學(xué)與工程學(xué)院

系統(tǒng)工程教研室

第1次諛2學(xué)時(shí)

上欠課復(fù)習(xí)：

本次課題（或教材章節(jié)題目）：緒論、第一章線性規(guī)劃與單純形法§1.1實(shí)際問(wèn)題與線

性規(guī)劃1模型

教學(xué)要求：掌握運(yùn)籌學(xué)發(fā)展歷史、主要分支及工作步驟；掌握線性規(guī)劃一般形式特點(diǎn)及圖

解法。

重點(diǎn)：運(yùn)籌學(xué)的工作步驟、線性規(guī)劃一般形式、圖解法。

難點(diǎn)：線性規(guī)劃一般形式及特點(diǎn)、線性規(guī)劃圖解法。

教學(xué)手段及教具：多媒體教學(xué)。

講授內(nèi)容及時(shí)間分配：

一、運(yùn)籌學(xué)簡(jiǎn)史25分鐘

二、運(yùn)籌學(xué)的主要分支10分鐘

三、運(yùn)籌學(xué)的工作步驟10分鐘

第一章線性規(guī)劃與單純形法

§1.1線性規(guī)劃的基本概念

§1.1.1線性規(guī)劃的數(shù)學(xué)模型20分鐘

§1.1.2圖解法25分鐘

課后作業(yè)國(guó)411(1)、(4)

《運(yùn)籌學(xué)》

《運(yùn)籌學(xué)教程》

參考資料

《運(yùn)籌學(xué)》

《運(yùn)籌學(xué)應(yīng)用案例》

注：本頁(yè)為每次課教案首

第一章緒論

本章內(nèi)容要點(diǎn)

1、主要介紹博學(xué)的簡(jiǎn)史，運(yùn)籌學(xué)的性質(zhì)、特點(diǎn)、應(yīng)用及其發(fā)展前景；

2、根據(jù)學(xué)習(xí)本課程的經(jīng)3斜是出一些建議；

第一節(jié)運(yùn)籌學(xué)概況簡(jiǎn)述

運(yùn)籌學(xué)是一門基礎(chǔ)性的應(yīng)用學(xué)科，主要研究系統(tǒng)最優(yōu)化的問(wèn)題，通過(guò)對(duì)建

立的模型求解，為決策者進(jìn)行決策提供科學(xué)依據(jù)。

-運(yùn)籌學(xué)簡(jiǎn)史

運(yùn)籌學(xué)的英文通用名稱為“OperationsResearch簡(jiǎn)稱OR,按照原意應(yīng)

譯為運(yùn)作研究或作戰(zhàn)研究。我國(guó)翻譯成地“運(yùn)籌學(xué)"，這是出于《史記漢高祖

本紀(jì)》中，漢高祖劉邦稱贊張良日"夫運(yùn)籌于帷幄之中，決勝于千里之外，吾

不如子房。"這里的,有主持戰(zhàn)略、"作戰(zhàn)研究"之意，人4、邨具義把它

譯為“運(yùn)籌學(xué)"。國(guó)內(nèi)外許多學(xué)者公認(rèn)，這個(gè)譯法非常恰當(dāng)。事實(shí)上，運(yùn)籌學(xué)的

思想出現(xiàn)得很早。我國(guó)歷史上的軍事和科學(xué)技術(shù)方面對(duì)運(yùn)籌思想的運(yùn)用是世界

著名的，公元6世紀(jì)春秋時(shí)期著名的《孫子兵法》中處處體現(xiàn)了軍事運(yùn)籌的思

想；戰(zhàn)國(guó)時(shí)期的"田忌齊王賽馬”故事是對(duì)策論的典型范例；劉邦、項(xiàng)羽在楚

漢相爭(zhēng)過(guò)程中，依靠張良等謀士的計(jì)謀，演出了一幕又一幕運(yùn)籌思想體現(xiàn)的作

戰(zhàn)戰(zhàn)例；三國(guó)時(shí)期的戰(zhàn)爭(zhēng)中更可以舉出很多運(yùn)用運(yùn)籌思想取得戰(zhàn)爭(zhēng)勝利的例

子。除軍事方面，在我國(guó)古代農(nóng)業(yè)、運(yùn)輸、工程技術(shù)等方面也有大量體現(xiàn)運(yùn)籌

思想的實(shí)例，如北魏時(shí)期科學(xué)家賈思勰的《齊民要術(shù)》一書就是一部體現(xiàn)運(yùn)籌

思想合理策劃農(nóng)事的寶貴文獻(xiàn)；古代的糧食和物資的調(diào)運(yùn)、都市的規(guī)劃建設(shè)、

水利方面如四川都江堰工程等亦處處反映了運(yùn)籌思想的運(yùn)用。

在歐美運(yùn)籌學(xué)早期工作的歷史可追溯到20世紀(jì)前葉，在1914年提出了軍

事運(yùn)籌學(xué)中的蘭徹斯特(Lanchester)戰(zhàn)斗方程;1917年排隊(duì)論的用區(qū)者丹麥工

程師愛(ài)爾朗(Erlang)在哥本哈根電話公司研究電話通訊系統(tǒng)時(shí)，提出了排隊(duì)論

的一些著名公式；本世紀(jì)20年代初提出了存貯論的最優(yōu)批量公式；本世紀(jì)30

年代，在商業(yè)方面列溫遜已經(jīng)運(yùn)用運(yùn)籌思想來(lái)分析商業(yè)廣告和顧客心理等。

這反映出，運(yùn)籌學(xué)注意系統(tǒng)數(shù)據(jù)采集，分析并研究?jī)?yōu)化方案的思想是一種

樸素、自然的思想。在實(shí)際上，很多人都在自覺(jué)，不自覺(jué)地運(yùn)用這個(gè)思想。另

一方面，我們常說(shuō)"魔高一尺，道高一丈"，在競(jìng)爭(zhēng)中各方共同運(yùn)用這些思想

解決問(wèn)題時(shí)，就表現(xiàn)為對(duì)運(yùn)籌學(xué)內(nèi)涵的研究、運(yùn)用能力。

謝^(OperationsResearch,簡(jiǎn)稱OR),作為科學(xué)名字是出現(xiàn)在20世

紀(jì)30年代末。當(dāng)時(shí)英、美使用雷達(dá)作為防空系統(tǒng)的一部分在軍事上對(duì)付德國(guó)的

空襲，從技術(shù)上沒(méi)有問(wèn)題，但是在實(shí)際運(yùn)用中效果不理怛。為此，一些有關(guān)領(lǐng)

域的科學(xué)家把“如何合理運(yùn)用雷達(dá)"作為一類新的問(wèn)題進(jìn)行研究。由于它與研

究技術(shù)問(wèn)題不同，于是就稱作“運(yùn)作研究"。第二次世界大戰(zhàn)期間，英、美軍隊(duì)

中成立了一些專門小組，面對(duì)一些實(shí)際問(wèn)題開(kāi)展了短期的和戰(zhàn)術(shù)性的研究。例

如，雷達(dá)系統(tǒng)有效防空問(wèn)題，研究設(shè)計(jì)將雷達(dá)信息傳送給指揮系統(tǒng)及武器系統(tǒng)

的最佳方案。

運(yùn)籌學(xué)(OperationsResearch,簡(jiǎn)稱OR)，作為科學(xué)名字是出現(xiàn)在20世

紀(jì)30年代末。當(dāng)時(shí)英、美使用雷達(dá)作為防空系統(tǒng)的一部分在軍事上對(duì)付德國(guó)的

空襲，吸支術(shù)上沒(méi)有問(wèn)題，但是在實(shí)際運(yùn)用中效果不理怛。為此，一些有關(guān)領(lǐng)

域的科學(xué)家把“如何合理運(yùn)用雷達(dá)”作為一類新的問(wèn)題進(jìn)行研究。由于它與研

究技術(shù)問(wèn)題不同，于是就稱作“運(yùn)作研究"。第二次世界大戰(zhàn)期間，英、美軍隊(duì)

中成立了一些專門小組，面對(duì)一些實(shí)際問(wèn)題開(kāi)展了短期的和戰(zhàn)術(shù)性的研究。例

如，雷達(dá)系統(tǒng)有效防空問(wèn)題，研究設(shè)計(jì)將雷達(dá)信息傳送給指揮系統(tǒng)及武器系統(tǒng)

的最佳方式、雷達(dá)與防空武器的最佳配置等；護(hù)航艦隊(duì)保護(hù)商船隊(duì)的編隊(duì)問(wèn)

題，研究當(dāng)船隊(duì)遭受德國(guó)軍隊(duì)攻擊時(shí)如何使船隊(duì)減少損失等；大西洋反潛戰(zhàn)問(wèn)

題，研究如何設(shè)計(jì)反潛艦艇或飛機(jī)投擲深水炸彈的最佳方案等。二次世界大戰(zhàn)

后，在英、美軍隊(duì)中相繼成立了正式運(yùn)籌研究組織，以蘭德公司(LAND)為首

的一些部門開(kāi)始著重研究戰(zhàn)略性問(wèn)題。例如，為美國(guó)空軍評(píng)價(jià)各種轟炸機(jī)系

統(tǒng)，討論未來(lái)的武器系統(tǒng)和未來(lái)戰(zhàn)爭(zhēng)的戰(zhàn)略等；研究蘇聯(lián)的軍事能力及未來(lái)的

預(yù)報(bào)等?？偟膩?lái)說(shuō)，在這段時(shí)間里運(yùn)籌學(xué)的研究與應(yīng)用范圍主要是與戰(zhàn)爭(zhēng)相關(guān)

的戰(zhàn)略、戰(zhàn)術(shù)方面問(wèn)題。隨著世界性戰(zhàn)爭(zhēng)的結(jié)束，各國(guó)的經(jīng)濟(jì)建設(shè)迅速發(fā)展，

世界范圍內(nèi)的劇烈競(jìng)爭(zhēng)也體現(xiàn)在經(jīng)濟(jì)、技術(shù)方面，運(yùn)籌學(xué)的研究發(fā)展也向這些

方面拓展。由于運(yùn)籌學(xué)適應(yīng)時(shí)代的要求，在近六十年中，它無(wú)論從理論上還是

應(yīng)用上都得到了快速的發(fā)展。在應(yīng)用方面，今天運(yùn)籌學(xué)已經(jīng)涉及到了服務(wù)、管

理、規(guī)劃、決策、組織、生產(chǎn)、建設(shè)等諸多方面，甚至可以說(shuō)，很難找出它涉

及不到的領(lǐng)域。在理論方面，由于運(yùn)籌學(xué)的需要和刺激而發(fā)展起來(lái)的一些數(shù)學(xué)

分支，如數(shù)學(xué)規(guī)劃，應(yīng)用概率與統(tǒng)計(jì)，應(yīng)用組合數(shù)學(xué)，對(duì)策論，數(shù)理經(jīng)濟(jì)學(xué)，

系統(tǒng)科學(xué)等等，都得到迅速發(fā)展。

20世紀(jì)50年代中期，我國(guó)著名的科學(xué)家錢學(xué)森、許國(guó)志等將運(yùn)籌學(xué)從西

方引入我國(guó)，并結(jié)合我國(guó)的特點(diǎn)在國(guó)內(nèi)推廣應(yīng)用。自從引入以來(lái)，運(yùn)籌學(xué)在我

國(guó)已有四十多年的歷史。經(jīng)過(guò)這四十多年，運(yùn)籌學(xué)在我國(guó)有了很大的發(fā)展，確

立了它在經(jīng)濟(jì)建設(shè)中的地位。但是，運(yùn)籌學(xué)在我國(guó)的發(fā)展?fàn)顩r與世界其它國(guó)家

相比，尚有不小的差距，其中最主要的是認(rèn)識(shí)與基礎(chǔ)的問(wèn)題。

隨著科學(xué)技術(shù)的發(fā)展，特別是信息社會(huì)的到來(lái)，運(yùn)籌學(xué)的內(nèi)涵不斷擴(kuò)大，

涉及的數(shù)學(xué)及其它基礎(chǔ)科學(xué)的知識(shí)越來(lái)越多，于是熟練掌握并運(yùn)用這門學(xué)科有

效解決實(shí)際問(wèn)題的難度也逐漸加大。根據(jù)運(yùn)籌學(xué)發(fā)展，數(shù)學(xué)、計(jì)算機(jī)科學(xué)及其

他新興學(xué)科的最新知識(shí)、技術(shù)都能很快融合到其中，特別是人的直接參與決

策，使得運(yùn)籌學(xué)發(fā)展更進(jìn)入一個(gè)嶄新階段。

為了加強(qiáng)運(yùn)籌學(xué)的研究與應(yīng)用，國(guó)內(nèi)外成立了許多學(xué)術(shù)性的組織。最早建

立運(yùn)籌學(xué)會(huì)的國(guó)家是英國(guó)（1948年），接著是美國(guó)Q952年）、法國(guó)Q956年）、

日本和印度（1957年）等，到1986年為止，國(guó)際上已有38個(gè)國(guó)家和地區(qū)建立了

運(yùn)籌學(xué)會(huì)或類似的組織。我國(guó)的運(yùn)籌學(xué)會(huì)成立在1980年。1959年英、美、法

三國(guó)的運(yùn)籌學(xué)會(huì)發(fā)起成立了國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)QFORS）,以后各國(guó)的運(yùn)籌學(xué)會(huì)紛

紛加入，我國(guó)于1982年加入該會(huì)。此外還有一些地區(qū)性組織如歐洲運(yùn)籌學(xué)協(xié)會(huì)

（EURO）成立于1976年，亞太母學(xué)協(xié)會(huì)（APORS）成立于1985年等。

二、解

運(yùn)籌學(xué)在早期的應(yīng)用主要在軍事領(lǐng)域，二次大戰(zhàn)后運(yùn)籌學(xué)的應(yīng)用轉(zhuǎn)向民

用。經(jīng)過(guò)幾十年的發(fā)展，運(yùn)籌學(xué)的應(yīng)用已經(jīng)深入到社會(huì)、政治、經(jīng)濟(jì)、軍事、

科學(xué)、技術(shù)等各個(gè)領(lǐng)域，發(fā)揮了巨大作用。這里選擇幾個(gè)管理方面的應(yīng)用給予

簡(jiǎn)單介紹。

1、生產(chǎn)運(yùn)作：生產(chǎn)總體計(jì)劃要求從總體確定生產(chǎn)、存貯^口勞動(dòng)力的配合規(guī)

劃以適應(yīng)波動(dòng)的需求計(jì)劃。運(yùn)籌學(xué)的應(yīng)用主要在生產(chǎn)作業(yè)的計(jì)劃、日程表的編

排、合理下料、酉群斗問(wèn)題、物料管理等方面；

2、物資庫(kù)存管理：多種物資庫(kù)存的系統(tǒng)組織與安排管理，確定某些設(shè)備的

能力或容量，如停車場(chǎng)的大小、新增發(fā)電設(shè)備的容量大小、電子計(jì)算機(jī)的內(nèi)存

量、合理的水庫(kù)容量等。將庫(kù)存理論與計(jì)算機(jī)的物資管理信息系統(tǒng)相結(jié)合，確

定合理的庫(kù)存方式、計(jì)算最佳的庫(kù)存量等；

3、物資運(yùn)輸問(wèn)題：涉及空運(yùn)、水運(yùn)、公路運(yùn)輸、鐵路運(yùn)輸、管道運(yùn)輸、廠

內(nèi)運(yùn)輸。常常涉及班次和人員服務(wù)時(shí)間安排等，需要確定最小成本的運(yùn)輸線

路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度等；

4、組織人事管理：對(duì)人員的需求和使用方面的預(yù)測(cè)，確定人員編制、人員

合理分配，建立人才評(píng)價(jià)體系、人才開(kāi)發(fā)的規(guī)劃、激勵(lì)機(jī)制的研究等；

5、市場(chǎng)營(yíng)銷：廣告預(yù)算、媒介選擇、產(chǎn)品定價(jià)、新產(chǎn)品的引入和開(kāi)發(fā)、銷

售計(jì)劃制定、市場(chǎng)模擬研究等:

6、財(cái)務(wù)管理和會(huì)計(jì)：各經(jīng)濟(jì)項(xiàng)目的預(yù)測(cè)、預(yù)算，貸款、成本分析、證券管

理、現(xiàn)金管理等。常使用的方法有統(tǒng)計(jì)分析、數(shù)學(xué)規(guī)劃、決策分析、盈虧點(diǎn)分

析法、價(jià)值分析:蟾；

7、計(jì)算機(jī)應(yīng)用和信息系統(tǒng)開(kāi)發(fā)：運(yùn)籌學(xué)中的數(shù)學(xué)規(guī)劃方法、網(wǎng)絡(luò)圖論、排

隊(duì)論、存儲(chǔ)論、模擬與仿真方法等均起到巨大作用；

8、城市管理：各種緊急服務(wù)系統(tǒng)的設(shè)計(jì)和運(yùn)用、城市垃圾的清掃、搬運(yùn)和

處理、城市供水和污水處理系統(tǒng)的規(guī)劃、區(qū)域規(guī)劃、市區(qū)交通網(wǎng)絡(luò)的規(guī)劃與管

理等。

三、的相

隨著運(yùn)籌學(xué)的應(yīng)用越來(lái)越廣泛和深入，眾多有識(shí)之士對(duì)運(yùn)籌學(xué)將向哪個(gè)方

向發(fā)展、如何發(fā)展的問(wèn)題進(jìn)行了廣泛和深入的研究。美國(guó)前運(yùn)籌學(xué)會(huì)主席邦特

(S.Bonder)認(rèn)為，運(yùn)籌學(xué)應(yīng)在三個(gè)領(lǐng)域發(fā)展：運(yùn)籌學(xué)應(yīng)用、運(yùn)籌科學(xué)^運(yùn)籌數(shù)

學(xué)。并強(qiáng)調(diào)發(fā)展前兩者，從整體講應(yīng)協(xié)調(diào)發(fā)展。目前運(yùn)籌學(xué)工作者面臨的大量

新問(wèn)題是：經(jīng)濟(jì)、技術(shù)、社會(huì)、生態(tài)和政治等因素交叉在一起的復(fù)雜系統(tǒng)。因

此，早在上一世紀(jì)70年代末80年代初就有不少運(yùn)籌學(xué)家提出：要注意研究大

系統(tǒng)，注意運(yùn)籌學(xué)與系統(tǒng)分析相結(jié)合。美國(guó)科學(xué)院國(guó)際開(kāi)發(fā)署寫了一本書，其

書名就把系統(tǒng)分析和運(yùn)籌學(xué)并列。有的運(yùn)籌學(xué)家提出了要從運(yùn)籌學(xué)到系統(tǒng)分析

的報(bào)告：由于研究新問(wèn)題的時(shí)間范圍很長(zhǎng)，因此必須與未來(lái)學(xué)緊密結(jié)合；由于

面臨的問(wèn)題大多是涉及技術(shù)、經(jīng)濟(jì)、社會(huì)、心理等綜合因素的研究，在運(yùn)籌學(xué)

中除常用的數(shù)學(xué)方法以外，還必須引入一些非經(jīng)典數(shù)學(xué)的方法和理論等。美國(guó)

運(yùn)籌學(xué)家沙旦(T.L.Saaty)在20世紀(jì)70年代末提出了層次分析法(AHP),并

認(rèn)為過(guò)去過(guò)分強(qiáng)調(diào)細(xì)巧的數(shù)學(xué)模型，可是它很難解決那些非結(jié)構(gòu)性的復(fù)雜問(wèn)

題。因此寧可用看起來(lái)是簡(jiǎn)單和粗糙的方法，加上決策者的正確判斷恰能解決

實(shí)際問(wèn)題。切克蘭特(P.B.Checkland)把傳統(tǒng)的運(yùn)籌學(xué)方法稱為硬系統(tǒng)思考，

它適用于解決那種結(jié)構(gòu)明確的系統(tǒng)以及戰(zhàn)術(shù)和技術(shù)性問(wèn)題。硬系統(tǒng)思考方法對(duì)

于結(jié)構(gòu)不明確的，有人參與活動(dòng)的系統(tǒng)無(wú)法很好地處理，這就應(yīng)采用軟系統(tǒng)思

考方法，相應(yīng)的一些概念和方法都應(yīng)有所變化，如將過(guò)分理想化的"最優(yōu)解"

換成“滿意解"等。

目前，運(yùn)籌學(xué)領(lǐng)域工作者上匕較一致的共識(shí)是運(yùn)籌學(xué)的發(fā)展應(yīng)注重以下三個(gè)

方面：理念更新、實(shí)踐為本、學(xué)科交融。

第二節(jié)的內(nèi)容及特點(diǎn)

-運(yùn)籌學(xué)的分支

我國(guó)運(yùn)籌學(xué)的老前輩、中國(guó)工程院院士許國(guó)志教授等在1992年《運(yùn)籌與管

理》雜志創(chuàng)刊號(hào)發(fā)表的“運(yùn)籌學(xué)的ABC"一文提出了運(yùn)籌學(xué)的三個(gè)來(lái)源是：軍

事、管理和經(jīng)濟(jì)，同時(shí)還討論了運(yùn)籌學(xué)的三個(gè)組成部分：運(yùn)用分析理論、競(jìng)爭(zhēng)

理論和隨機(jī)服務(wù)理論即排隊(duì)論。

由于運(yùn)籌學(xué)涉及到廣泛的應(yīng)用和有關(guān)的學(xué)科領(lǐng)域，經(jīng)歷數(shù)十年的發(fā)展形成

了其自身的各個(gè)分支。

線性規(guī)劃是由美國(guó)運(yùn)籌學(xué)工作者丹捷格(G.B.Dantzig)在1947年為解決

美國(guó)空軍在軍事規(guī)劃問(wèn)題時(shí)提出的。丹捷格提出了求解線性規(guī)劃問(wèn)題的單純形

法。歹I」昂節(jié)夫的約在1932銀合出了投入產(chǎn)出模型。馮?諾伊曼(VomNeumman)

和摩根斯坦(0.Morgenstern)合著的《對(duì)策論與經(jīng)濟(jì)行為》(1944年)是對(duì)^

論的奠基作，同時(shí)該書已隱約地指出了對(duì)策論與線性規(guī)劃對(duì)偶理論的緊密聯(lián)

系?；仡櫄v史，為運(yùn)籌學(xué)的建立和發(fā)展作出貢獻(xiàn)的有物理學(xué)家、經(jīng)濟(jì)學(xué)家、數(shù)

學(xué)家、其它專業(yè)的學(xué)者、軍官和各行業(yè)的實(shí)際工作者。

運(yùn)籌數(shù)學(xué)的飛快發(fā)展，促使并形成了運(yùn)籌學(xué)的許多分支。通常提到的有：

1線性規(guī)劃

I非線性規(guī)則

1整數(shù)規(guī)劃

I目規(guī)fell

1動(dòng)態(tài)規(guī)劃

J隨機(jī)規(guī)劃

J模糊規(guī)劃等

以上人們常常統(tǒng)稱之為數(shù)學(xué)規(guī)劃，此外還有

I圖論與網(wǎng)絡(luò)

1排隊(duì)論(隨機(jī)服務(wù)系統(tǒng)理論)

1存貯論

I對(duì)策論

決策論

1搜索論

:I維修更新理論

排序與統(tǒng)籌方法

J可靠性和質(zhì)量管理等

二、運(yùn)籌學(xué)的定義及原則

為了更好地研究和應(yīng)用，人們希望對(duì)運(yùn)籌學(xué)給出一個(gè)確切定義，以便更加

深入地明確它的性質(zhì)和特點(diǎn)。但是，由于本學(xué)科復(fù)雜的應(yīng)用科學(xué)特征，至今還

沒(méi)有統(tǒng)一且確切的定義。用以下幾個(gè)比較有影響的定義來(lái)說(shuō)明運(yùn)籌學(xué)的性質(zhì)和

特點(diǎn)。

為決策機(jī)構(gòu)在對(duì)其控制下業(yè)務(wù)活動(dòng)進(jìn)行決策時(shí)，提供以數(shù)量化為基礎(chǔ)的科

學(xué)方法(P.M.Morse&G.E.Kimball);

這個(gè)定義首先強(qiáng)調(diào)的是科學(xué)方法，重視某種研究方法要可以用于整個(gè)一類

問(wèn)題上，并能夠控制和進(jìn)行有組織的活動(dòng)，而不單是這些研究方法分散和偶然

的應(yīng)用。另一方面，它強(qiáng)調(diào)以量化為基礎(chǔ)，必然要用到數(shù)學(xué)理論和成果。我們

知道，任何決策都包含定量和定性兩方面，而定性方面又不能簡(jiǎn)單地用數(shù)學(xué)表

示。如政治、社會(huì)等因素，只有綜合多種因素的決策才是全面的。在這里，運(yùn)

籌學(xué)工作者的職責(zé)是為決策者提供可以量化方面的分析，指出那些定性的因

素。

運(yùn)籌學(xué)是一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)方法，解

決實(shí)際中提出的專門問(wèn)題，為決策者選擇最優(yōu)決策提供定量依據(jù)；

這個(gè)定義表明運(yùn)籌學(xué)具有多學(xué)科交叉的特點(diǎn)，例如：綜合運(yùn)用數(shù)學(xué)、經(jīng)濟(jì)

學(xué)、心理學(xué)、物理學(xué)、化學(xué)等的一些方法。運(yùn)籌學(xué)是強(qiáng)調(diào)最優(yōu)決策，但是這個(gè)

‘最’是過(guò)分理想了，在實(shí)際生活中很難實(shí)現(xiàn)。

I運(yùn)籌學(xué)是一種給出問(wèn)題壞的答案的藝術(shù)，否則的話問(wèn)題的結(jié)果會(huì)更壞；

這個(gè)定義表明運(yùn)籌學(xué)強(qiáng)調(diào)最優(yōu)決策過(guò)分理想，在現(xiàn)實(shí)中很難實(shí)現(xiàn)，于是用

次優(yōu)、滿意等概念來(lái)代替最優(yōu)。

為了有效地應(yīng)用運(yùn)籌學(xué)，前英國(guó)運(yùn)籌學(xué)學(xué)會(huì)會(huì)長(zhǎng)托姆林森提出的下列六條

原則，得到眾多運(yùn)籌學(xué)工作者的認(rèn)同：

(1)合伙原則。是指運(yùn)籌學(xué)工作者要和各方面人，尤其是同實(shí)際部門工作

者合作；

(2)催化原則。在多學(xué)科共同解決某問(wèn)題時(shí)，要引導(dǎo)人們改變一些常規(guī)的

看法；

(3)互相滲透原則。要求多部門彼此滲透地考慮問(wèn)題，而不是只局限于本

部門；

(4)獨(dú)立原則。在研究問(wèn)題時(shí)，不應(yīng)受某人或某部門的特殊政策所左右，

遜立從事工作；

(5)寬容原則。解決問(wèn)題的思路要寬，方法要多，而不是局限于某種特定

的方法；

(6)平衡原則。要考慮各種矛盾的平衡，關(guān)系的平衡。

第三節(jié)運(yùn)籌學(xué)的學(xué)習(xí)與應(yīng)用

-運(yùn)籌學(xué)研究的工作步驟

由于運(yùn)籌學(xué)與許多的科學(xué)領(lǐng)域、各種有關(guān)因素有著橫向和縱向的聯(lián)系。為

了有效地應(yīng)用運(yùn)籌學(xué)，根據(jù)運(yùn)籌學(xué)的特征，人們把運(yùn)籌學(xué)研究的工作步驟歸納

為以下幾個(gè)內(nèi)容：

(1)目標(biāo)的規(guī)定。確定決策者期望從方案中得到什么。這個(gè)目標(biāo)不應(yīng)限制在

過(guò)分狹小的范圍內(nèi)，也要避免把研究目標(biāo)作不必要的擴(kuò)大。

(2)方案計(jì)劃的研制。實(shí)施一項(xiàng)運(yùn)籌學(xué)研究的過(guò)程常常是一個(gè)創(chuàng)造性過(guò)程，

計(jì)劃的實(shí)質(zhì)是規(guī)定出要完成某些不壬務(wù)的時(shí)間，然后創(chuàng)造性地按時(shí)完成這一系

列子任務(wù)。這樣做能夠推動(dòng)運(yùn)籌學(xué)分析者做出結(jié)論，有助于方案的成功。若對(duì)

計(jì)劃的任意延期和誤時(shí)會(huì)導(dǎo)致分析者的消極工作和管理者的漠不關(guān)心。

(3)問(wèn)題的表述。這項(xiàng)工作需要與管理人員的深入討論，經(jīng)常包括與其他職

員和業(yè)務(wù)人員的接觸和必要數(shù)據(jù)的采集，以便了解問(wèn)題的本質(zhì)、歷史及未來(lái)、

問(wèn)題各個(gè)變量之間的關(guān)系。這項(xiàng)任務(wù)的目的是為研究中的問(wèn)題內(nèi)容提供一個(gè)模

型框架，并為全部以后的工作確立方向。在這里，第一要考慮問(wèn)題是否能夠分

解為若干串行或并行的子問(wèn)題；第二要確定模型建立的細(xì)節(jié)，如問(wèn)題尺度的確

定，可控制決策變量的確定、不可控制狀態(tài)變量的確定、有效性度量的確定和

各類參數(shù)、常數(shù)的確定。

(4)模型的研制。模型是對(duì)各變量關(guān)系的描述，是正確研制成功解決問(wèn)題的

關(guān)鍵。構(gòu)成模型的關(guān)系有幾種類型，常用的有定義的關(guān)系、經(jīng)驗(yàn)關(guān)系和規(guī)范關(guān)

系等。

(5)模型求解。在這一步應(yīng)充分考慮現(xiàn)有的計(jì)算機(jī)應(yīng)用軟件是否適應(yīng)模型的

條件，解的精度及可行性是否能夠達(dá)到需要。若沒(méi)有現(xiàn)成可直接應(yīng)用的計(jì)算機(jī)

軟件，則獻(xiàn)以下兩步工作：

①計(jì)算手段的擬定。在模型研制的同時(shí)，需要研究如何用數(shù)值方法求解模

型。其中包括對(duì)問(wèn)題變量性質(zhì)(確定性、隨機(jī)性、模糊性)、關(guān)系特征(線性，非

線性)、手段(模擬，優(yōu)化)及使用方法(現(xiàn)有的，新構(gòu)造的)等的確定；

②程序明細(xì)表的編制，程序設(shè)計(jì)和調(diào)試。對(duì)于計(jì)算過(guò)程需要編制程序來(lái)實(shí)

現(xiàn)計(jì)算機(jī)運(yùn)算，運(yùn)算學(xué)研究應(yīng)包含算法過(guò)程的描述，計(jì)算流程框圖繪制。程序

的實(shí)現(xiàn)及調(diào)試可以交由程序員完成，或會(huì)同程序員完成。

(6)數(shù)據(jù)收集。把有效性試驗(yàn)和實(shí)行方案所需的數(shù)據(jù)收集起來(lái)加以分

析，研究輸入的靈敏性，從而可以更準(zhǔn)確地估計(jì)得到的結(jié)果。

(7)解的檢驗(yàn)(驗(yàn)證)。驗(yàn)證在運(yùn)籌學(xué)的研究與應(yīng)用中的重要性無(wú)論怎樣強(qiáng)

調(diào)都不會(huì)過(guò)分。驗(yàn)證包括兩個(gè)方面：第一是確定驗(yàn)證模型，包括為驗(yàn)證一致

性、靈敏性，似然性和工作能力而設(shè)計(jì)的分析和實(shí)驗(yàn)；第二是驗(yàn)證的進(jìn)行，即

把前一步收集的數(shù)據(jù)用來(lái)對(duì)模型作完全試驗(yàn)。這樣一種試驗(yàn)的結(jié)果，往往使模

型必須重新設(shè)計(jì)，并要求相聯(lián)系的重編程序。

(8)解方案的實(shí)施。有些人認(rèn)為，在模型驗(yàn)證后任務(wù)就完成了，這是不對(duì)

的。事實(shí)上，一項(xiàng)研究的真正困難往往在解方案實(shí)施的這最后一步。很多問(wèn)題

常常在這時(shí)暴露出來(lái)，他們會(huì)涉及到研制方案的全過(guò)程。因此，必須由參與整

個(gè)過(guò)程的有關(guān)人員參與才能解決。

二、鰥的T,函

運(yùn)籌學(xué)建模在理論上，應(yīng)是屬于數(shù)學(xué)建模的一個(gè)部分。因此，運(yùn)籌學(xué)建模

所采用的手段、途徑與一般在數(shù)學(xué)建模中所采用的類似。下面介紹的是根據(jù)運(yùn)

籌學(xué)本身的特征來(lái)處理建模問(wèn)題的一般思路。

經(jīng)過(guò)長(zhǎng)期、深入的研究和發(fā)展，運(yùn)籌學(xué)處理的問(wèn)題歸納成一系列具有較強(qiáng)

背景和規(guī)范特征的典型問(wèn)題。因此，運(yùn)籌學(xué)建模就要把相當(dāng)?shù)木Ψ旁趯?shí)際

問(wèn)題合理地描述為某種典型的運(yùn)籌模型上。在這個(gè)過(guò)程中,T殳要求運(yùn)籌學(xué)工

作者具有以下幾個(gè)方面的知識(shí)和能力：

(1)熟悉典型運(yùn)籌模型的特征和它的應(yīng)用背景；

(2)有分析、理解實(shí)際問(wèn)題的能力，包括廣博的知識(shí)、搜集信息、資料和數(shù)

據(jù)的能力;

(3)有抽象分析問(wèn)題的能力，包括善于抓主要矛盾，善于邏輯思維、推理、

歸納、聯(lián)想、類比等形成的創(chuàng)新能力；

(4)有運(yùn)用各類工具知識(shí)的能力，包括運(yùn)用數(shù)學(xué)、計(jì)算機(jī)、其它自然科學(xué)的

知識(shí)和工程技術(shù)等的能力；

(5)有試驗(yàn)校正和維護(hù)修正模型等的能力。

根據(jù)問(wèn)題本身的情況，運(yùn)籌學(xué)在解決問(wèn)題時(shí)，按研究對(duì)象不同可構(gòu)造各種

不同的模型。模型是研究者對(duì)客觀現(xiàn)實(shí)經(jīng)過(guò)思維抽象后用文字、圖表、符號(hào)、

關(guān)系式以及實(shí)體描述所認(rèn)識(shí)到的客觀對(duì)象。模型的有關(guān)參數(shù)和關(guān)系式比較容易

改變，這樣將有助于問(wèn)題的分析和研究。利用模型可以對(duì)所研究的問(wèn)題進(jìn)行一

定預(yù)測(cè)及靈敏度分析等。

目前運(yùn)籌學(xué)中用得最多的是符號(hào)或數(shù)學(xué)模型。建立、構(gòu)造模型是一種創(chuàng)造

性勞動(dòng)，成功的模型往往是科學(xué)和藝術(shù)的結(jié)晶，常見(jiàn)的構(gòu)模方法和思路有以下

麗

(1)直接分析方法。當(dāng)我們對(duì)問(wèn)題的內(nèi)在關(guān)系、特征等比較熟悉時(shí)，可以根

據(jù)對(duì)問(wèn)題內(nèi)在機(jī)理的認(rèn)識(shí)直接構(gòu)造出模型。運(yùn)籌學(xué)中已有不少現(xiàn)存的模型，如

線性規(guī)劃模型、投入產(chǎn)出模型、排隊(duì)模型、存貯模型、決策和對(duì)策模型等等。

這些模型都有很好的求解方法及求解的軟件。有時(shí)模型的參數(shù)也可直接從問(wèn)題

本身得到。

(2)類比方法。通過(guò)對(duì)問(wèn)題的深入分析，結(jié)合經(jīng)驗(yàn)，常常會(huì)發(fā)現(xiàn)有些模型的

結(jié)構(gòu)性質(zhì)是類同的。這就可以互相類比，通過(guò)類比把新遇到的問(wèn)題用已知類似

問(wèn)題的模型來(lái)建立該問(wèn)題模型。這種情況往往得到的是模型歸類，而模型參數(shù)

需用其它的方法取得。

(3)模擬方法。利用計(jì)算機(jī)程序?qū)崿F(xiàn)對(duì)問(wèn)題的實(shí)際運(yùn)行模擬，可得到有用的

數(shù)據(jù)。這些數(shù)據(jù)常用來(lái)求得模型參數(shù)或?qū)λ⒛Ｐ瓦M(jìn)行合理性、正確性的檢

驗(yàn)。

(4)數(shù)據(jù)分析法。利用數(shù)據(jù)處理的方法分析各數(shù)據(jù)變量之間的關(guān)系是確

定關(guān)系，還是相關(guān)關(guān)系，以及是何種相關(guān)等。這種方法還可以用回歸分析找出

變量的變化趨勢(shì)，從而得到合理的數(shù)學(xué)模型。大量的模型參數(shù)求得也常常使用

數(shù)據(jù)處理的統(tǒng)計(jì)方法。另外，回歸模型常常就是一個(gè)無(wú)約束最優(yōu)化模型。

(5)試驗(yàn)分析法。通過(guò)試驗(yàn)分析建模是工程管理中常用的方法。這類方法是

以局部的試驗(yàn)產(chǎn)生數(shù)據(jù)，經(jīng)過(guò)統(tǒng)計(jì)處理得到總體的模型或模型歸類。試驗(yàn)分析

更多地用于產(chǎn)生模型參數(shù)。

(6)構(gòu)想法。當(dāng)有些問(wèn)題的機(jī)理不清，既缺少數(shù)據(jù)，又不能作試驗(yàn)來(lái)獲得數(shù)

據(jù)時(shí)，例如一些社會(huì)、經(jīng)濟(jì)、軍事問(wèn)題等。這種情況下，人們只能在已有的知

識(shí)、經(jīng)驗(yàn)和某些研究的基礎(chǔ)上，對(duì)于將來(lái)可能發(fā)生的情況給出邏輯上合理的設(shè)

想和描述，然后用已有的方法構(gòu)造模型，并不斷修正完善，直至比較滿意為

止。這種方法基于人們的構(gòu)想。

三、如好運(yùn)籌學(xué)

運(yùn)籌學(xué)是一門基礎(chǔ)性的應(yīng)用學(xué)科，主要研究系統(tǒng)最優(yōu)化的問(wèn)題，通過(guò)對(duì)建

立的模型求解，為管理人員作決策提供科學(xué)依據(jù)。本課程是管理類專業(yè)的必修

基礎(chǔ)課，為學(xué)習(xí)有關(guān)專業(yè)課打好基礎(chǔ)，進(jìn)而為學(xué)生畢業(yè)后在管理工作中運(yùn)用模

型技術(shù)、數(shù)量分析及優(yōu)化方法打下良好的基礎(chǔ)。本課程的主要任務(wù)是：

①要求學(xué)生掌握運(yùn)籌學(xué)的基本概念、基本原理、基本方法和解題技巧；

②培養(yǎng)學(xué)生根據(jù)實(shí)際問(wèn)題建立運(yùn)籌學(xué)模型的能力及求解模型的能力；

③培養(yǎng)學(xué)生分析解題結(jié)果及經(jīng)濟(jì)評(píng)價(jià)的能力;

④培養(yǎng)學(xué)生理論聯(lián)系實(shí)際能力及自學(xué)能力。

通過(guò)教學(xué)，培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)膶W(xué)風(fēng)及勤奮刻苦的學(xué)習(xí)態(tài)度和科學(xué)的協(xié)作精

神。

為了幫助有關(guān)人員更好地學(xué)習(xí)運(yùn)籌學(xué)，根據(jù)著者多年的教學(xué)實(shí)踐和體會(huì)，

提出如下的一些建議，僅供參考。

學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、思路上。在學(xué)習(xí)過(guò)程

中，應(yīng)該多向自己提問(wèn)，如一個(gè)方法的實(shí)質(zhì)是什么，為什么這樣做，怎么做

等。

在認(rèn)真聽(tīng)課的同時(shí)，學(xué)習(xí)或復(fù)習(xí)時(shí)要掌握以下三個(gè)重要環(huán)節(jié)：

(1)、認(rèn)真閱讀教材和參考資料，以指定教材為主，同時(shí)參考其他有關(guān)書

籍。一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn)，但是基本原理、概念都是一致

的。注意主從，參考資料會(huì)幫助你開(kāi)闊思路，使學(xué)習(xí)深入。但是，把時(shí)間過(guò)多

放在參考資料上，會(huì)導(dǎo)致思路分散，不利于學(xué)好。

(2)、要在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助

你理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時(shí)還有讓你自己檢

查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨(dú)立完成，不要怕出錯(cuò)。因?yàn)椋?/p>

整個(gè)課程是一個(gè)整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識(shí)融會(huì)貫

通起來(lái)，你做題的正確性自己就有判斷。

(3)、要學(xué)會(huì)做學(xué)習(xí)小結(jié)。每一節(jié)或一章學(xué)完后，必須學(xué)會(huì)用精煉的語(yǔ)言來(lái)

敘述該書所學(xué)內(nèi)容。這樣，你才能夠從較高的角度來(lái)看問(wèn)題，更深刻的理解有

關(guān)知識(shí)和內(nèi)容，這就稱作“把書讀薄"。若能夠結(jié)合自己參考大量文獻(xiàn)后的深入

理解，把相關(guān)知識(shí)從更深入、廣泛的角度進(jìn)行論述，則稱之為"把書讀厚”。

第二章線性規(guī)劃問(wèn)題及單純形法

教學(xué)要求：1.通過(guò)圖解法了解線性規(guī)劃的結(jié)構(gòu)

2.了解線性規(guī)劃的基本概念與性質(zhì)

3.單純形法的理論基礎(chǔ)

4.單純形法的主要過(guò)程、單純形表的構(gòu)造

5.確定初始可行基的人工變量法、人工變量法

重點(diǎn)：圖解法的解題過(guò)程，線性規(guī)劃的基本概念與性質(zhì)，單純形法的理論基礎(chǔ)

和主要過(guò)程，人工變量法的使用。

難點(diǎn)：?jiǎn)渭冃畏ǖ睦碚摶A(chǔ)。

第一節(jié)問(wèn)題的提出

例1.1生產(chǎn)安排問(wèn)題。某工廠可生產(chǎn)兩種產(chǎn)品，每單位產(chǎn)品所需要的資

源(設(shè)備和原料)，所創(chuàng)造的利潤(rùn),以及工廠每天能提供的各種資源的總量由表

1.1給出。工廠應(yīng)如何安排兩種產(chǎn)品的生產(chǎn)量，才能獲得最大的利潤(rùn)？

表1.1

產(chǎn)品I產(chǎn)品n資源總量

設(shè)＞（等寸）128

府斗A（公斤）4016

府斗B（公斤）0412

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

分析：1、工廠需要決定每天安排兩種產(chǎn)品的產(chǎn)量，在模型中我們用變量表

示，即設(shè)每天安排生產(chǎn)產(chǎn)品工、II的數(shù)量分別為Xi,X2o這樣，變量組（X1,X2

）,或者說(shuō)向量X=（XLX2）T（以列向量表示）就表示了一種生產(chǎn)方案，稱這樣的

變Xi,X2為決策變量，相應(yīng)的向量X為決策變量，X體現(xiàn)了解決問(wèn)題的一個(gè)方

案。

2、需要有一個(gè)衡量方案X優(yōu)劣的指標(biāo)，在這個(gè)問(wèn)題中，這種指標(biāo)可用函數(shù)

Z=2xi+3X2給出。稱這樣的函數(shù)為目標(biāo)函數(shù)。在這里目標(biāo)函數(shù)值Z為工廠按方

案X=（XI,X2）T生產(chǎn)時(shí)，每天可獲得的利潤(rùn)。

3、一個(gè)可以實(shí)施的方案X必須符合工廠所能提供的各種資源量的制約，因此,

中的決策變量X-X2必須滿足某些條件，這些條件可用不等式表示，即

設(shè)備約束：x1+2x2n8

原料A的約束：4X116

原料B的約束：4x212

稱以上不等式為約束條件。

4、根據(jù)問(wèn)題的實(shí)際意義有xi,X20,稱這一條件為（決策變量的）非負(fù)約

束。

5、工廠的目標(biāo)是選取一個(gè)方案X*,在該方案X*下的生產(chǎn)可獲得最大的利潤(rùn)

Z*,也就是說(shuō)要在所有滿足約束條件和非負(fù)約束的X中，選擇一個(gè)X*,使相應(yīng)

于X*的目標(biāo)函數(shù)值Z*達(dá)到最大。

這樣，該問(wèn)題的數(shù)學(xué)模型可用下述的數(shù)學(xué)結(jié)構(gòu)表示：

maxZ=2XI+3X2

2x8

4X]16

4X2112

l%i,x20

從上述的例子看出，建立數(shù)學(xué)模型的基本過(guò)程是：

1設(shè)置決策轉(zhuǎn)；

2給出目標(biāo)函數(shù)；

3確定約束條件和非負(fù)約束；

4確定目標(biāo)函數(shù)的優(yōu)化方向，即優(yōu)化是對(duì)目標(biāo)函數(shù)取最大還是最小。

例1.2任務(wù)分配問(wèn)題。某公司擬生產(chǎn)4種產(chǎn)品，可分配給下屬的三個(gè)工廠

生產(chǎn)，由于工廠的地理位置和設(shè)備不同，每個(gè)工廠生產(chǎn)每種產(chǎn)品的成本不相

同，加工能力也不相同。有關(guān)數(shù)據(jù)分別由表1.2和表1.3給出。公司應(yīng)如何給

下屬各工廠分配任務(wù)才能保證完成每種產(chǎn)品的任務(wù)的條件下，使得公司所花費(fèi)

的成本最少？

表1.2單位產(chǎn)品成本表

1234

123211917

222202519

319162123

產(chǎn)品產(chǎn)量60805040

表1.3單位產(chǎn)品所需機(jī)時(shí)表

加工能力

1234

X（日擻）

15253320

24263480

33264280

該例主要說(shuō)明如何確定約束條件。

例13資金借貸問(wèn)題。某工廠計(jì)劃在三個(gè)月內(nèi)開(kāi)發(fā)一項(xiàng)新產(chǎn)品，有A,

B兩個(gè)型號(hào)，目預(yù)計(jì)第一批至少有A型產(chǎn)品50件，B型產(chǎn)品25件投A市場(chǎng)。由

于在產(chǎn)品開(kāi)發(fā)期間必須支付成本費(fèi)用，而當(dāng)產(chǎn)品投入市場(chǎng)后才能獲得收益，現(xiàn)

工廠可用于產(chǎn)品開(kāi)發(fā)的內(nèi)部資金僅有3萬(wàn)元，故需向銀行貸款。銀行同意給該

廠總數(shù)不超過(guò)10萬(wàn)元的三個(gè)月短期貸款，年利率為12%,同時(shí)附加如下的信貸

保證：工廠三個(gè)月后的資金（含產(chǎn)品的應(yīng)收款）不得少于貸款的及應(yīng)付利息之

和的兩倍。關(guān)于產(chǎn)品開(kāi)發(fā)的其他數(shù)據(jù)由表L4給出。在這樣的情況下，工廠應(yīng)

如何考慮產(chǎn)品的生產(chǎn)與向銀行貸款的數(shù)額？

表1.4

單位產(chǎn)品所需時(shí)

單位成本單位售價(jià)

產(chǎn)品型號(hào)

（元）（元）

組裝調(diào)試包裝

A121500580

B25210001200

加工能力2500150

該例主要說(shuō)明如何設(shè)置決策變量以有利于給出目標(biāo)函數(shù)和確定約束條件。

由于應(yīng)用貸款生產(chǎn)產(chǎn)品需要支付利息，這就相當(dāng)于增加了產(chǎn)品的單位成

本，止忸攫號(hào)A,B白嬋分別為500xl2%+4+500=515方口1030元這

樣，在建立數(shù)學(xué)模型是我們應(yīng)當(dāng)考慮應(yīng)用自有資金和貸款資金生產(chǎn)出的產(chǎn)品間

的差別，為此,設(shè)置決策變量如下：

xi:用自有資金生產(chǎn)A型產(chǎn)品的數(shù)量,

x2:用貸款資金生產(chǎn)A型產(chǎn)品的數(shù)量,

X3:用自有資金生產(chǎn)B型產(chǎn)品的數(shù)量，

X4:用貸款資金生產(chǎn)B型產(chǎn)品的數(shù)量.

例1.4酣斗問(wèn)題。某糖果廠用原料A,B,C加工生產(chǎn)三種牌號(hào)的糖果。

各種牌號(hào)的糖果中對(duì)原料A,B,C含量的限制、原料成本、加工費(fèi)用和售價(jià)和

每月原料限量由表L5給出。該廠如何安排生產(chǎn)，才能獲得最大利潤(rùn)？

表1.5

含量限制原料成本原料限量

原料

（元/公斤）

牌號(hào)1牌號(hào)2牌號(hào)3（公斤/月）

A口60%U15%無(wú)62000

B無(wú)無(wú)無(wú)4.52500

c120%□60%50%31200

加工費(fèi)(元/公

1.51.20.9

斤)

售價(jià)(元/公斤)

15128

該例主要說(shuō)明較復(fù)雜問(wèn)題的建模。

從上面的例題可以看出，雖然每個(gè)問(wèn)題的實(shí)際背景互不相同，但是它們的

數(shù)學(xué)模型卻具有相同的結(jié)構(gòu)，即

(1)存在一組決策變量，對(duì)它們可有非負(fù)要求；

(2)存在一個(gè)以決策變量為自變量的目標(biāo)函數(shù)，且它為線性函數(shù)；

(3)存在一組約束條件，且每個(gè)條件都是由決策變量構(gòu)成的不等式或等

式；

(4)結(jié)構(gòu)要求求出這樣的變量組，或者說(shuō)決策向量X,在X滿足約束條件

和非負(fù)約束的同時(shí)，使相應(yīng)的目標(biāo)函數(shù)值達(dá)到最大或者最小。簡(jiǎn)言之，在一定

條件下使目標(biāo)函數(shù)優(yōu)化。

稱這種數(shù)學(xué)結(jié)構(gòu)為線性規(guī)劃，具有這種結(jié)構(gòu)的數(shù)學(xué)模型為線性規(guī)劃模型。

線性規(guī)劃模型的一般表達(dá)式為：

max(min)Z。的口c2x2-…g%

為內(nèi)aux2…aln^](口⑼，

1

氏內(nèi)口a2xJIa2nx(Ul)t>2

La血為?a成X2口c，D0

XjL0,/L1,2Mn

其中X1,X2,…,Xn為決策變量，其余的量Cj,bi和aij都是常量。

在某些情況下，線性規(guī)劃模型中也可只對(duì)部分決策變量，甚至于不對(duì)決策

變量提出非負(fù)要求。如前所述，較為復(fù)雜的經(jīng)濟(jì)管理問(wèn)題常表示為從眾多的方

案（當(dāng)然，這些方案要滿足一定的條件）中，選取一個(gè)方案（即決策），使它具

有最好的效果。因此，線性規(guī)劃模型為經(jīng)濟(jì)管理決策提供了一個(gè)重要的、有效

的數(shù)學(xué)工具。

在線性規(guī)劃問(wèn)題求解時(shí)，我們應(yīng)當(dāng)在滿足約束條件和非負(fù)條件的所有決策

向量中尋找。為此給出如下定義，稱滿足約束條件和非負(fù)條件的決策向量為該

問(wèn)題的可行解，稱全體可行解構(gòu)成的集合為可行域，常用D表示。稱使目標(biāo)函

數(shù)到達(dá)最優(yōu)的可行解為最優(yōu)解，最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值為最優(yōu)值。所謂求解

線性規(guī)劃問(wèn)題是指求出該問(wèn)題的最優(yōu)解，或者判斷出該問(wèn)題沒(méi)有最優(yōu)解。

第二節(jié)圖解法

具有兩個(gè)決策變量的線性規(guī)劃問(wèn)題是最簡(jiǎn)單的線性規(guī)劃問(wèn)題，它可用圖解

法求解.通過(guò)對(duì)這種簡(jiǎn)單的線性規(guī)劃的討論可揭示一般線性規(guī)劃問(wèn)題的重要特

征，從而尋求求解線性規(guī)劃問(wèn)題的方法。

首先通過(guò)例子說(shuō)明兩個(gè)決策變量的線性規(guī)劃問(wèn)題的圖解法。

例1.5求解線性規(guī)劃問(wèn)題

maxZ=xi+3x2

-Xi+x2<6

-XI+2X2<8

XI>0,X2>0

我們知道，在直角坐標(biāo)系下，方程aixi+a2x2=b表示平面中的一條直線，不

布aixi+a2x2<b或aiXi+a2X2>b表示一個(gè)半平面。當(dāng)我們?cè)谕黄矫鎯?nèi)表示

出所有約束條件和非負(fù)約束表示的半平面時(shí)，這些半平面的交集（即公共部

分）就構(gòu)成了線性規(guī)劃問(wèn)題的可行域。

目標(biāo)函數(shù)等值線

圖1.1

最優(yōu)解Z=（4/3,14/3y,最優(yōu)值為2=46/3。

結(jié)論一、線性規(guī)劃問(wèn)題的解僅存在以下四種狀態(tài)，即

1有渴優(yōu)

2有無(wú)窮多個(gè)最優(yōu)解，它們具有相同的目標(biāo)函數(shù)值；

3有無(wú)界可行解，或者說(shuō)無(wú)最優(yōu)解；

4無(wú)可行解。

結(jié)論二、當(dāng)線性規(guī)劃問(wèn)題的可行域D為空集）時(shí),該問(wèn)題無(wú)可行解。當(dāng)D

不等于空集時(shí)，D為凸集，且若該問(wèn)題有最優(yōu)解時(shí)，最優(yōu)解可在D的頂點(diǎn)上達(dá)

到。

第2次謖2學(xué)時(shí)

上次課復(fù)習(xí)：

線性娥（1一般形式及特點(diǎn)；

線性規(guī)劃圖解法。

本次課題（晦闞＞節(jié)題目）：§1.2線性^劃解的基本郵

教學(xué)要求：掌握線性規(guī)劃解的基本性質(zhì)、基可行解的概念及LP解的性質(zhì)

重點(diǎn)：線性規(guī)劃的特點(diǎn)、基可行解的概念及LP解的性質(zhì)

難點(diǎn)：線性規(guī)劃的基本性質(zhì)、基可行解的概念。

教學(xué)手段及教具：多媒體教學(xué)。

講授內(nèi)容及時(shí)間分配：

上次課復(fù)習(xí)5分鐘

2.1基本概念40分鐘

2.2基本定理45分鐘

課后作業(yè)P441.2(1),1.3

《運(yùn)籌學(xué)》錢頌迪主編清華大學(xué)出版社

《運(yùn)籌學(xué)教程》胡運(yùn)權(quán)主編清華大學(xué)出版社

參考資料

《運(yùn)籌學(xué)》牛映武主編西安交大出版社

《運(yùn)籌學(xué)應(yīng)用案例》陶謙坎主編機(jī)械工業(yè)出版社

第二節(jié)線性規(guī)劃解的基本性質(zhì)

兩個(gè)決策變量的線性規(guī)劃問(wèn)題的圖形解法簡(jiǎn)單直觀而且有效，但這種方法

不能求解一般意義下的線性規(guī)劃問(wèn)題，通過(guò)對(duì)圖解法的討論，我們已在直觀上

看到了線性規(guī)劃問(wèn)題的一些重要特征，現(xiàn)在再?gòu)拇鷶?shù)的角度分析這些特征，以

求得線性規(guī)劃問(wèn)題的求解方法。

線性規(guī)劃問(wèn)題的標(biāo)解可寫成矩陣形式:

maxzlCX

AXb

X0

設(shè)Xji,xj2，…，xjm為線性規(guī)劃問(wèn)題中的m個(gè)變量，若它們對(duì)應(yīng)的系數(shù)

向量h,Pj2，…，Pjm，線性無(wú)關(guān)，則稱矩陣

B=[Pjl,Pj2Pjm]

為該線性規(guī)劃問(wèn)題的一個(gè)基，稱Xji,Xj2Xjm為對(duì)應(yīng)于基B的基變量，其

他變量為（對(duì)應(yīng)于B的）非基變量。

設(shè)B為線性規(guī)劃問(wèn)題的任意一個(gè)基，令所有的非基變量為零，就可得到一

個(gè)以Xji,Xj2Xjm為未知量的線性方程組，根據(jù)線性代數(shù)的基本理論，由

B為可逆矩陣，該方程組有唯一解。這樣，根據(jù)基B可構(gòu)造出一個(gè)滿足約束條

件AX=b的X,稱X為對(duì)應(yīng)于B的基解。

在基本解中非基變量的取值為零，若還有基變量取值為零，即解X中的非

基分量的個(gè)數(shù)小于m,稱該基本解為退化解。

同時(shí)滿足非負(fù)條件的基解稱為基可行解，基可行解對(duì)應(yīng)的基稱為可行基。

線性規(guī)劃具有如下重要的基本性質(zhì),

1線性規(guī)劃問(wèn)題的可行域?yàn)橥辜?/p>

2若線性規(guī)劃問(wèn)題有可行解，則它必有基本可行解。

3線性規(guī)劃問(wèn)題的基本可行解對(duì)應(yīng)于它的可行域的一個(gè)頂點(diǎn)。

4若線性規(guī)劃問(wèn)題有最優(yōu)解，則最優(yōu)解可在它的可行域的某個(gè)頂點(diǎn)達(dá)

到。

定理的證明中要突出說(shuō)明線性規(guī)劃中的一些概念，需要應(yīng)用到線性代數(shù)和

數(shù)學(xué)分析的基礎(chǔ)知識(shí)。具體有：

性質(zhì)1：可行解,集合等相關(guān)概念

性質(zhì)2:應(yīng)用向量相關(guān)性討論，應(yīng)用數(shù)學(xué)分析中的方法，用構(gòu)造法證明

性質(zhì)3:應(yīng)用基本概念，反證法證明

性質(zhì)4:應(yīng)用最優(yōu)解概念和性質(zhì)的證明方法

線性規(guī)劃的這些基本性質(zhì)為求解方法提供了堅(jiān)實(shí)的理論基礎(chǔ)。

第3次課_____

上欠課復(fù)習(xí)：

線性規(guī)劃的標(biāo)準(zhǔn)形式、特點(diǎn)；

基可行解的概念。

本次課題（或教材章節(jié)題目）：§13線性規(guī)劃問(wèn)題的單純形法

教遇求：掌握單純形法的解弱思路、單純形法要點(diǎn)和單純形表

重點(diǎn)：?jiǎn)渭冃伪?；單純形法則

難點(diǎn)：初始單純形表；換基迭代法則

教學(xué)手段及教具：多媒體教學(xué)。

講授內(nèi)容及時(shí)間分配：

上次課復(fù)習(xí)及作業(yè)10分鐘

§13.1單純形法的解題思路40分鐘

§1.3.2單純形法要點(diǎn)和單純形表40分鐘

課后作業(yè)P44L4(1)、(2)

《運(yùn)籌學(xué)》錢頌迪主編清華大學(xué)出版社

《運(yùn)籌學(xué)教程》胡運(yùn)權(quán)主編清華大學(xué)出版社

參考資料

《運(yùn)籌學(xué)》牛映武主編西安交大出版社

《運(yùn)籌學(xué)應(yīng)用案例》陶謙坎主編機(jī)械工業(yè)出版社

第三節(jié)線性規(guī)劃問(wèn)題的單純形法(一)

單純形法是G.B.Dantzig在1947年給出的求解線性規(guī)劃問(wèn)題的方法，至今

它仍是求解線性規(guī)劃問(wèn)題的主要方法。單純形法的核心工作是：判定一個(gè)基本

可行解是否最優(yōu)解。在它不是最優(yōu)解時(shí)，尋求一個(gè)改進(jìn)的基本可行解。這樣單

純形法是一個(gè)迭代過(guò)程，如果最優(yōu)解存在，可在有限次迭代后求得。因此單純

形法是一種有效算法且便于在計(jì)算機(jī)上實(shí)現(xiàn)。

線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形矩陣形式為：

mzxzCX

AXb

X口0

若B為它的一個(gè)基，不失一般性，可設(shè)B為A中前m列元素構(gòu)成的子矩

陣。根據(jù)B,將A,C,X寫成分塊矩陣，得：

Xb

>401B,NCCBICNX

~XN~

在AX=b的兩端左乘BL得：

11

8MXB(BXeNX"XBBNXNB】b(1.4)

因羊，

1111

Z=CX=CBXB+O^=CB(B-b-BNXN)+CNXN=CBB-b-(CBB-N-CN)XN

(1.5)

或者有Z-CX=O,上式■^為：

2+(朋1!\1<^4=儂為(1.6)

稱(1.4)、(1.6)式為線性規(guī)劃問(wèn)題對(duì)應(yīng)于基B的正規(guī)方程組,(1.5)式

為相應(yīng)于B的目標(biāo)函數(shù)方程。

令非基變量XN=0,由(1.4)式，XB=B』b,從而對(duì)應(yīng)于B的基本解為。

X。

0

在滿足條件

B-ib>0(1.7)

時(shí)，X為基本可行解，B為可行基。稱(1.7)式為可行條件。

令

X

i"CN口口"1，.2，口J^,ZB□CBBb,

(1.5)式可改寫為：

Z.ZB.|nXj

jm\l

根據(jù)上面分析可得如下結(jié)論：

最優(yōu)解判定定理設(shè)B為可行基，如果向量IN20,則B對(duì)應(yīng)的基本解X

為線性規(guī)劃問(wèn)題的最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)值為Z=CBB-Ib。

定理表明，向量N在判定一個(gè)基本可行解是否為最優(yōu)解中起著至關(guān)重要

的作用。為此，稱1N的分量mik為對(duì)應(yīng)的非基變量Xm+k的檢驗(yàn)數(shù)，在每個(gè)非基

變量的檢驗(yàn)數(shù)都為非負(fù)數(shù)時(shí)，我們就得到了最優(yōu)解。

T殳情況下，設(shè)B為一個(gè)基(不一定為可行基)，稱條件

CBB^N-CN^O(1.8)

為優(yōu)化條件。這樣，上面的定理可表述為：

若基B滿足可行條件和優(yōu)化條件，則B為最優(yōu)基。

進(jìn)f正明以下定理：

設(shè)B為可行基，X為相應(yīng)的基本可行解，如果

1.對(duì)每個(gè)j=m+l,m+2,…,n,都有匕口0,則X為線性規(guī)劃問(wèn)題的唯一最

優(yōu)解；對(duì)每個(gè)j=m+l,m+2,…,n,有I小0，但存在口10,若Z。非退化，則

線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。

2.存在」m-0，且矩陣B-1N中的第k個(gè)列向量

，則線性規(guī)劃問(wèn)題無(wú)有界最優(yōu)解。

3設(shè)B為可行解，相應(yīng)的基可行解*非退化，若存在非基變量期的檢驗(yàn)

數(shù)k。，且水,匚儂了，中存在可行基8,相應(yīng)的基可行解為7,使

得

exexo

上述定理的證明要充分利用到線性代數(shù)中分塊矩陣及性質(zhì)，分析重點(diǎn)為最

后一個(gè)結(jié)論，證明方法為構(gòu)造法，此時(shí)，需求得一個(gè)改進(jìn)的基本可行解，這一

過(guò)程稱為換基運(yùn)算。需要從原基的非基變量中選取一個(gè)變量所作為新基的基變

量（稱之為換入變量），從原基的基變量中確定一個(gè)變量刈使之成為新基的非

基變量（稱之為換出變量），一個(gè)重要的結(jié)論是選擇的原則是（稱為最小

xHe

準(zhǔn)則）

但也

Imin

出尸）1n（B】P0

講述中要重點(diǎn)分析這一原則及證明新基為可行基。

換基運(yùn)算有以下步驟：

L選取換入變量：原則上，換入變量可在具有負(fù)檢驗(yàn)數(shù)的非基變量中任

意選取，但通常的方法是選取一個(gè)具有負(fù)檢驗(yàn)數(shù)且絕對(duì)值最大的非基變量作為

換入變量，稱之為最大。準(zhǔn)則。其目的是使目標(biāo)函數(shù)值增加的較快，以有可能

減少迭代次數(shù)。

2.確定換出變量：為保證新基為可行基，換出變量不能任意選取，按最

小e準(zhǔn)則。

3.求新基下的基本可行解

根據(jù)上述的基本理論，單純形法的基本步驟為：

1求初始可行基；求B滿足可行條件B-!b>0;

2優(yōu)化檢3僉；若優(yōu)化條件CBB1N-CN>0成立，已得最優(yōu)解，否則換基運(yùn)

算；

3換基運(yùn)算：設(shè)4為換入變量，在矩陣B』N中對(duì)應(yīng)于XL的列向量為

T

(an,a2i,-ami),BIb=(阮，氏，…即兒

如果每個(gè)aki<0,i=l,2,...m,,則表明線性規(guī)劃問(wèn)題無(wú)有限最優(yōu)解，否則按最

小6準(zhǔn)則，取原基的第k個(gè)基變量Xk作為換出變量，稱aki為主元素,換基

運(yùn)算可

通過(guò)矩陣的初等變換實(shí)現(xiàn)。

第4次謨2學(xué)時(shí)

第三節(jié)線性規(guī)劃問(wèn)題的單純形法（二）

上欠課復(fù)習(xí)：

單純形表；

單細(xì)緘5!!1;

講解作業(yè)存在問(wèn)題。

本次課題（或教材章節(jié)題目）：§13線性規(guī)劃問(wèn)題的單純形法

教學(xué)要求：掌握無(wú)窮多最優(yōu)解與唯一最優(yōu)解的判別法則、無(wú)最優(yōu)解（無(wú)界解）的判定法

則；

掌握求minz的情況。

重點(diǎn)：?jiǎn)渭冃闻袆e法則

難點(diǎn)：?jiǎn)渭冃闻袆e法則及證明；求minz的情況。

教學(xué)手段及教具：多媒體教學(xué)。

講授內(nèi)容及時(shí)間分配：

上次課復(fù)習(xí)及作業(yè)20分鐘

1.無(wú)窮多最優(yōu)解與唯一最優(yōu)解的判別法則25分鐘

2.無(wú)最優(yōu)解