運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用

管理運(yùn)籌學(xué)計(jì)劃學(xué)時(shí)31

課程名稱

教材名稱運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用出版時(shí)間1998?2002

教材哈爾濱工業(yè)大學(xué)出版

作者胡運(yùn)權(quán)出版社

社

MBA《管理數(shù)學(xué)（下）一運(yùn)籌學(xué)》

清華大學(xué)出版社

指定參考書《運(yùn)籌學(xué)習(xí)題集》胡運(yùn)權(quán)出版社

機(jī)械工業(yè)出版社

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

課程性質(zhì)、目的與基本要求

此門課程目的在于介紹現(xiàn)代管理的技術(shù)和方法，為管理類其它分支如企業(yè)管理、人力資

源管理、組織行為學(xué)、戰(zhàn)略管理、運(yùn)作管理、財(cái)務(wù)管理、項(xiàng)目管理、服務(wù)管理、公共管理等

學(xué)科提供技術(shù)和方法的支撐；同時(shí)，也為經(jīng)濟(jì)研究和其它學(xué)科的研究，提供有效的研究工具。

內(nèi)容與學(xué)時(shí)分配

0緒論（2學(xué)時(shí)）

介紹運(yùn)籌學(xué)產(chǎn)生、發(fā)展、現(xiàn)狀和未來以及運(yùn)籌學(xué)的方法論——系統(tǒng)觀和輔助軟件工具，

如Lindo,lingo,excel。

第一章線性規(guī)劃及單純形法（5學(xué)時(shí)）

介紹線性規(guī)劃的建模、線性規(guī)劃的幾何意義、單純形法的理論和算法、線性規(guī)劃的經(jīng)濟(jì)

意義和在投資、資源計(jì)劃等經(jīng)濟(jì)管理實(shí)踐中的案例及應(yīng)用。

第二章對(duì)偶理論和靈敏度分析（3學(xué)時(shí)）

介紹對(duì)偶問題的經(jīng)濟(jì)學(xué)含義（市場(chǎng)博弈）和經(jīng)濟(jì)解釋（影子價(jià)格一邊際收益和機(jī)會(huì)成本）、

對(duì)偶理論、對(duì)偶單純形法、參數(shù)規(guī)劃。

第三章運(yùn)輸問題（3學(xué)時(shí)）

介紹物流管理中的運(yùn)輸網(wǎng)絡(luò)的建立和運(yùn)行方案優(yōu)化，包括鐵路、公路、航空、海運(yùn)中的

物資調(diào)運(yùn)計(jì)劃。

第四章整數(shù)規(guī)劃（2學(xué)時(shí)）

介紹分枝定界法、0—1整數(shù)規(guī)劃、互斥投資方案決策、工作分派問題及應(yīng)用。

第五章目標(biāo)規(guī)劃（2學(xué)時(shí)）

介紹目標(biāo)規(guī)劃的模型、圖解、單純形法、靈敏度分析，以及目標(biāo)管理、項(xiàng)目管理和經(jīng)濟(jì)

中的具體案例和應(yīng)用。

半期考試

第六章動(dòng)態(tài)規(guī)劃（6學(xué)時(shí)）

介紹動(dòng)態(tài)規(guī)劃的原理和模型、最短路問題、靜態(tài)規(guī)劃的動(dòng)態(tài)規(guī)劃法求解。

動(dòng)態(tài)規(guī)劃的應(yīng)用：介紹動(dòng)態(tài)規(guī)劃在多周期投資、多周期生產(chǎn)計(jì)劃、資源配置中的應(yīng)用。

第七章圖與網(wǎng)絡(luò)分析（6學(xué)時(shí)）

介紹基本概念、樹、最短路問題、最大流問題、中國(guó)郵遞員問題等?？捎糜诮煌ňW(wǎng)絡(luò)建

設(shè)、石油運(yùn)輸管線設(shè)計(jì)、電網(wǎng)設(shè)計(jì)、城市供水系統(tǒng)設(shè)計(jì)、大型商業(yè)連鎖網(wǎng)點(diǎn)設(shè)計(jì)和經(jīng)濟(jì)影響

因素識(shí)別。

第八章管理決策理論簡(jiǎn)介（2學(xué)時(shí)）

管理決策的基本概念和初步方法。

第九章對(duì)策論（博弈論）（自學(xué)）

介紹對(duì)策論基礎(chǔ)及解法及信息經(jīng)濟(jì)的有關(guān)內(nèi)容?？捎糜诮?jīng)濟(jì)研究中的尋租行為分析、委

托代理關(guān)系的分析、企皿聯(lián)盟的效益分配等。

《管理運(yùn)籌學(xué)》講義

緒論

第一章線性規(guī)劃

第二章線性規(guī)劃的對(duì)偶理論和靈敏度分析

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

第四章整數(shù)規(guī)劃與分配問題

第五章目標(biāo)規(guī)劃（GP）

第六章網(wǎng)絡(luò)優(yōu)化

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

第八章決策分析

第九章對(duì)策論（博奕論）

緒論

1.運(yùn)籌學(xué)的成長(zhǎng)之路

運(yùn)籌學(xué)產(chǎn)生于西方，其中文譯名源于《史記?漢高祖本紀(jì)中》中劉邦贊揚(yáng)張

良的一段話：“夫運(yùn)籌帷幄之中，決勝千里之外，……”。

作為我國(guó)運(yùn)籌學(xué)和系統(tǒng)工程創(chuàng)始人之一的許國(guó)志先生關(guān)于運(yùn)籌學(xué)的“三（三個(gè)

來源：軍事、經(jīng)濟(jì)、管理）、三（三個(gè)組成：運(yùn)用分析理論、競(jìng)爭(zhēng)理論、服務(wù)理論）、

-（一種方法論：系統(tǒng)方法論）”曾經(jīng)做出了深刻闡釋，對(duì)于后學(xué)者了解運(yùn)籌學(xué)的

產(chǎn)生和發(fā)展頗有啟迪。許老的這篇論述——“運(yùn)籌學(xué)的A、B、C”載于《運(yùn)籌與管

理》的創(chuàng)刊號(hào)（1992年1月），初學(xué)者不妨找來一讀。

圖o.1運(yùn)籌學(xué)的“三、三、一”

盡管運(yùn)籌學(xué)誕生于西方，但中國(guó)古代先賢卻并不缺乏今天為人稱頌的那些運(yùn)籌

思想。

1981年，美國(guó)軍事運(yùn)籌學(xué)會(huì)出版"SystemsAnalysisandModeling…”-書，

稱孫武子是世界上第一位軍事運(yùn)籌學(xué)的實(shí)踐家。在孫子質(zhì)的推理中，滲透著深刻的

量的分析和運(yùn)籌學(xué)的方法論——系統(tǒng)觀。

“課攻”：知已知彼，百戰(zhàn)不殆；不知彼而知己，一勝一負(fù)；不知彼不知己,

每戰(zhàn)必殆。

“戰(zhàn)篇”：孫子日：凡用兵之法，馳車千駟，革車千乘，帶甲十萬，千里饋糧。

則內(nèi)外之費(fèi)，賓客之用，膠漆之材，車甲之奉，日費(fèi)千金，然后十萬之師舉矣。其

用戰(zhàn)也，勝久則鈍兵挫銳，攻城則力屈，久暴師則國(guó)用不足.....

善用兵者，役不再藉，糧不三載，取用于國(guó)，因糧于敵，故軍食可足也。國(guó)之

貧于師者遠(yuǎn)輸，遠(yuǎn)輸則百姓貧；近師者貴賣，貴賣則百姓財(cái)竭，財(cái)竭則急于丘役。

力屈中原，內(nèi)虛于家，百姓之費(fèi)，十去其七；公家之費(fèi)，破軍罷馬，甲胃矢弓，戟

盾矛櫓，丘牛大車，十去其六。故智將務(wù)食于敵，食敵一鐘，當(dāng)吾二十鐘；桿一

石，當(dāng)吾二十布。.....

“計(jì)篇”：道、天、地、將、法夫未戰(zhàn)而廟算勝者，得算多也；未戰(zhàn)而廟

算不勝者，得算少也。多算勝少算，而況于無算乎！吾以此觀之，勝負(fù)見矣。

——《孫子兵法》（公元前六世紀(jì)，春秋時(shí)期）

齊王賽馬的故事載于《史記?列傳第五》，其中無疑閃耀著對(duì)策中論及的智慧。

糧食貯運(yùn)是歷朝關(guān)注的大事。然而公元前54年漢宣帝時(shí)，就比較好地用到了今

天運(yùn)籌學(xué)中解決運(yùn)輸和物流中心選址問題才提出的優(yōu)化思想。可從史料中尋到的描

述是：由于將關(guān)東經(jīng)水運(yùn)到長(zhǎng)安的運(yùn)糧路線改為長(zhǎng)安附近的弘農(nóng)、上黨、太原等地

就近供應(yīng)，不僅省掉一半以上的勞力，而且通過設(shè)置常平倉，保障了糧食的儲(chǔ)備和

供應(yīng)。

還有一個(gè)關(guān)于糧食收購的事發(fā)生在明神宗時(shí)期。

明神宗萬歷三巳年冬，倉谷殆盡，撫臺(tái)令各州縣用庫銀2000兩買谷，時(shí)谷價(jià)漲

至每石六錢，而官價(jià)僅五錢。開州知府陳霽巖拒不執(zhí)彳亍。待到庚午年秋（第二年秋），

開州大熟，谷價(jià)跌至二錢五，此時(shí)才上報(bào)巡撫，僅用官銀千兩，價(jià)三錢，就比去年

各州縣的總收購量還多，且開州民眾深受其益

-《智囊全集》K明H馮夢(mèng)龍，第二部明智?經(jīng)理時(shí)務(wù)?陳霽巖

陳霽巖在進(jìn)行糧食收購中所采取的策略，既是今天糧食收購保護(hù)價(jià)政策的早期范本,

乂體現(xiàn)了現(xiàn)代運(yùn)籌學(xué)中兩階段決策問題的處理思想。

宋真宗祥符年間，宮中大火，丁謂主辦營(yíng)建修復(fù)宮室。先挖街取土修復(fù)宮室，

再將汴水引入挖街后形成的溝壑中使利于建材的長(zhǎng)途運(yùn)輸，最后，修復(fù)宮室后剩下

的建渣回填溝壑重新還原街道。史稱此項(xiàng)工程為“一舉而三役濟(jì)?！币越袢说难酃?/p>

看，不能不說是運(yùn)籌學(xué)尊崇的系統(tǒng)優(yōu)化思想的完美體現(xiàn)。

國(guó)外古、近代的一些大學(xué)者如阿基米得、倫納多?達(dá)?芬奇、伽利略等對(duì)

運(yùn)籌學(xué)，特別是軍事運(yùn)籌學(xué)的思想和方法的萌芽也有諸多裨益。20世紀(jì)初，運(yùn)籌學(xué)

的雛形開始在西方顯現(xiàn)。

1909年，丹麥工程師Erlang在哥本哈根電話公司研究電話通訊系統(tǒng)時(shí)，發(fā)表

了排隊(duì)論方面的第一篇論文“概率論與電話會(huì)話”，從而開創(chuàng)了運(yùn)籌學(xué)分支——排

隊(duì)論的研究領(lǐng)域。一般認(rèn)為排隊(duì)論是研究隨機(jī)服務(wù)系統(tǒng)的一門學(xué)科，主要研究各種

伺服系統(tǒng)的統(tǒng)計(jì)規(guī)律性。

存儲(chǔ)論的產(chǎn)生和發(fā)展可追溯到19世紀(jì)末對(duì)銀行保持流通現(xiàn)金最佳數(shù)量即儲(chǔ)備金

的研究。1915年，Harris將這些研究應(yīng)用于物資訂購的最佳批量問題之中。20世

紀(jì)五十年代，T.M.Whitin和Arrow,Moran等人的工作奠定了存儲(chǔ)論的科學(xué)地

位。存儲(chǔ)論研究的問題相當(dāng)廣泛，資金儲(chǔ)備、材料儲(chǔ)存、訂貨、物資管理系統(tǒng)設(shè)計(jì)、

倉庫管理、人才儲(chǔ)備和使用、自然資源合理開發(fā)等等。

1916年，英國(guó)的蘭切斯特仔細(xì)研究了19世紀(jì)拿破侖時(shí)期的英、法、西班牙

Trafalgar海戰(zhàn)這一經(jīng)典的以弱勝強(qiáng)的戰(zhàn)例，揭示了“納爾遜秘訣”中的兵力配置

與勝負(fù)的關(guān)系，建立了最早的軍事運(yùn)籌模型。

1935?1938年間，英國(guó)為對(duì)付德軍的空中威脅，在東海岸的Bawdsey成立了

Rowse領(lǐng)導(dǎo)的研究小組。Rowse把這種對(duì)戰(zhàn)術(shù)效率的研究，賦予了"Operational

Research"的名稱。這就是運(yùn)籌學(xué)西文名的由來。Bawdsey也由此成為了現(xiàn)代運(yùn)籌

學(xué)的誕生地。美國(guó)人很快注意到戰(zhàn)爭(zhēng)中運(yùn)籌學(xué)的價(jià)值，從而也逐漸建立起了各種運(yùn)

籌研究小組,并命名為uOperationsResearch或OperationsAnalysisv0

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

堪稱運(yùn)籌學(xué)的先驅(qū)名著之一。其中已提到類似線性規(guī)劃的模型和“解乘數(shù)求解法”。

但是他的工作直到I960年的《最佳資源利用的經(jīng)濟(jì)計(jì)算》一書出版后，才得到重視。

1975年，康托洛維奇與T.C.Koopmans一起獲得了諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。

1944年，VonNeumann和經(jīng)濟(jì)學(xué)家Morgenstern分析了經(jīng)濟(jì)活動(dòng)中的沖突、

協(xié)調(diào)、平衡的問題的特征，寫出了《對(duì)策論與經(jīng)濟(jì)行為》一書，奠定了對(duì)策論研究

的早期基礎(chǔ)。

1947年G.B.Dantzig在研究美國(guó)空軍軍事規(guī)劃時(shí)提出了線性規(guī)劃的模型和

單純形解法。并很快引起美國(guó)著名經(jīng)濟(jì)學(xué)家Koopmans的注意，Koopmans為此呼吁

當(dāng)時(shí)年輕的經(jīng)濟(jì)學(xué)家要關(guān)注線性規(guī)劃。今天，線性規(guī)劃已成為了運(yùn)籌學(xué)的一個(gè)極為

重要的部分。

二戰(zhàn)后，英美等國(guó)相繼組建了更為正式的軍事運(yùn)籌學(xué)研究組織，并以蘭德公司

(Rand)為首的一些部門開始研究戰(zhàn)略性問題。同時(shí)，政府和工業(yè)部門也開始推行

運(yùn)籌學(xué)的方法。到二十世紀(jì)五十年代末，英美兩國(guó)兒乎所有的工業(yè)部門都組建了相

應(yīng)的運(yùn)籌學(xué)組織。1959年，英、美、法三國(guó)運(yùn)籌學(xué)會(huì)發(fā)起成立了國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)

(IFORS),到1992年，它已包括41個(gè)國(guó)家和地區(qū)。

我國(guó)現(xiàn)代運(yùn)籌學(xué)研究始于1956年，在錢學(xué)森先生的倡導(dǎo)下，成立了由許國(guó)志先

生領(lǐng)導(dǎo)的國(guó)內(nèi)第一個(gè)運(yùn)籌學(xué)研究室，并迅速在國(guó)內(nèi)形成了運(yùn)籌學(xué)應(yīng)用研究的高潮。

返聘體系

存『論||圖與網(wǎng)絡(luò)||排「論||數(shù)學(xué)、劃||對(duì)「論||決「論||可靠「理論

-------?/-------

線性規(guī)劃卜?｛非線性規(guī)劃11整數(shù)規(guī)劃卜T目標(biāo)規(guī)劃

動(dòng)態(tài)規(guī)劃山隨機(jī)規(guī)劃幾何規(guī)劃卜

圖Q.2運(yùn)籌學(xué)的體系

時(shí)至今日，運(yùn)籌學(xué)已經(jīng)成為了擁有眾多分支的一個(gè)學(xué)科體系（圖0.2）,并與系

統(tǒng)工程密不可分，在應(yīng)用上逐漸趨向于研究和解決經(jīng)濟(jì)管理中大量復(fù)雜系統(tǒng)的問題。

2.運(yùn)籌學(xué)的目的和使命

按照《大英百科全書》的解釋：“運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)”，

“運(yùn)籌學(xué)為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析工具”。因而，運(yùn)籌學(xué)創(chuàng)立

的目的就是為了把科學(xué)知識(shí)和方法應(yīng)用于對(duì)復(fù)雜系統(tǒng)問題的研究中，為實(shí)現(xiàn)組織目

標(biāo)的決策流程提供數(shù)量分析基礎(chǔ)。在英國(guó)為解決戰(zhàn)爭(zhēng)中關(guān)于防御和全球后勤供應(yīng)有

序化的復(fù)雜問題而組建其第一支運(yùn)籌研究隊(duì)伍時(shí).，美國(guó)的工業(yè)企業(yè)和一些私人咨詢

公司也已開始認(rèn)識(shí)到，運(yùn)籌學(xué)的方法可以應(yīng)用于非軍事性質(zhì)的問題。私人咨詢企業(yè)

阿瑟?D?利特爾有限公司，就是最早探索把運(yùn)籌學(xué)用于工業(yè)的公司之一。1953年,

管理科學(xué)研究所（TIMS）宣稱其目標(biāo)就是“確立、拓展、運(yùn)用有助于理解管理實(shí)踐

的科學(xué)知識(shí)”。因此，運(yùn)籌學(xué)的使命就存在于其實(shí)踐性之中。

然而，要完成這一使命并非易事。對(duì)于過去的大多數(shù)人而言，運(yùn)籌學(xué)的語言就

象巫醫(yī)用的偶像一樣，讓人莫名其妙。建立模型的儀式（如果稱之為儀式的話）、

儀式中所用的數(shù)學(xué)符號(hào)、令人生畏的咒語般的求解，往往激發(fā)初學(xué)者的敬畏之情。

盡管如此，運(yùn)籌學(xué)作為一門科學(xué)，它的來源、組成和方法論都絕非具有如巫術(shù)般的

非科學(xué)性。因此，在科學(xué)精神和使命的指引下，勇于承擔(dān)使命者在至今的50到60

年間，就構(gòu)建起了龐大的理論體系、方法體系和技術(shù)體系（求解過程的軟件化）。

這三個(gè)體系為完成運(yùn)籌學(xué)的使命奠定了深厚的基礎(chǔ)，并使對(duì)運(yùn)籌學(xué)的學(xué)習(xí)和研究具

備了相當(dāng)完善的框架。

今天，實(shí)踐性使命已將運(yùn)籌學(xué)推向了極為廣闊的應(yīng)用范圍，實(shí)踐的發(fā)展使得運(yùn)

籌學(xué)的內(nèi)涵和外延在不斷地更新和變化！它的應(yīng)用范圍已遍及社會(huì)、經(jīng)濟(jì)、管理、

軍事、生態(tài)等諸多領(lǐng)域，并在本質(zhì)上（由于其目的和使命使然）顯示出相當(dāng)驚人的

多學(xué)科交叉性、交融性。

3.運(yùn)籌學(xué)的工作流程和原則

圖0.3運(yùn)籌學(xué)的工作流程

運(yùn)籌學(xué)的工作流程包含了整體系統(tǒng)優(yōu)化、多學(xué)科配合、模型分析和信息技術(shù)應(yīng)用四

個(gè)特

點(diǎn)。其基本流程可由圖0.3表述,

其中，常用的工具軟件有

?Lindo,Lingo：

http://www.lindo.com/cgi/frameset.cgi?left.html;main.html

?Excel

?Mathematics

?Matlab

?Maple

?SAS、SPSS

在建立系統(tǒng)模型的過程中，首先值得注意的是對(duì)實(shí)際問題的抽象、簡(jiǎn)化、假設(shè)

等前期的工作。這工作的質(zhì)量好壞直接影響到模型的質(zhì)量?jī)?yōu)劣；其次，模型的可處

理性也要予以適當(dāng)?shù)淖⒁?。盡管運(yùn)籌學(xué)的理論、方法和軟件工具已具備相當(dāng)強(qiáng)的功

效，但它們?nèi)圆蛔阋越鉀Q所有的模型計(jì)算工作，而實(shí)踐問題對(duì)時(shí)效性乂往往有較高

的要求。因此，研究者必須考慮是否有能力處理所建立的模型；其三，建模過程還

應(yīng)關(guān)注藝術(shù)性和系統(tǒng)性。事實(shí)上，建模一詞，從英文“Modeling”本身看，就具有

藝術(shù)的含義，模型在本質(zhì)上就是關(guān)于所研究問題的一幅“漫畫”。同時(shí)，對(duì)實(shí)際問

題作出系統(tǒng)思考，是建模的基本要求，它允許依據(jù)新的信息作出反饋和不斷修改；

最后，對(duì)模型的結(jié)果分析要極為重視，因?yàn)檫@是模型實(shí)踐意義的直接體現(xiàn)部分。研

究者要與專業(yè)工作者、決策者一道進(jìn)行深入、細(xì)致的分析，才能提出合理、有效的

建議和方案。

為了更有效運(yùn)用這個(gè)工作流程解決實(shí)際問題，前英國(guó)運(yùn)籌學(xué)會(huì)會(huì)長(zhǎng)托姆林森提

出了六項(xiàng)原則：

(1)合伙的原則。運(yùn)籌學(xué)的工作者應(yīng)與各方面的人合作，尤其應(yīng)與專業(yè)和實(shí)際

部門的人合作。

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

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

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

（5）寬容原則。解決問題的思路要寬，而不應(yīng)局限于某種特定的研究方法。

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

這六項(xiàng)原則對(duì)運(yùn)籌學(xué)的實(shí)踐者有著較強(qiáng)的指導(dǎo)意義。

4.運(yùn)籌學(xué)與DSS（決策支持系統(tǒng)）

運(yùn)籌學(xué)的出現(xiàn)迅速更新了生產(chǎn)管理的理念，從解決產(chǎn)品結(jié)構(gòu)優(yōu)化、恰當(dāng)水平的

存貨、生產(chǎn)進(jìn)度與控制、經(jīng)濟(jì)批量生產(chǎn)、質(zhì)量控制、資本兼并等物質(zhì)資源的配置問

題開始，到融入全面質(zhì)量管理、物料需求計(jì)劃MRP、制造資源計(jì)劃MRPH、JIT、供

應(yīng)鏈管理SCM,可以清楚看到運(yùn)籌學(xué)和系統(tǒng)理論、信息技術(shù)的日益擴(kuò)大的交融趨勢(shì)。

盡管系統(tǒng)的思考古已有之，從《內(nèi)經(jīng)》的陰陽五行、《孫子兵法》的“經(jīng)五事”（道、

天、地、將、法）、老子強(qiáng)調(diào)的自然界的統(tǒng)一性、南宋陳亮的“理一分殊”到古希

臘哲人德謨克利特的“原子論”、亞里士多德的“四因”思想（后人概括為“整體

大于部分之和”），以及近代黑格爾的辯證法，無不充滿（樸素的）系統(tǒng)思想。即

使是在20世紀(jì)60年代以前的組織和管理理論的領(lǐng)域，系統(tǒng)觀點(diǎn)也不是什么新東西。

社會(huì)協(xié)作系統(tǒng)學(xué)派的創(chuàng)始人切斯特?巴納德（18867961）就曾用過一種基本的系統(tǒng)

框架來描述組織，將組織視為一種社會(huì)系統(tǒng)，一種人的相互關(guān)系的協(xié)作體系，它構(gòu)

成社會(huì)大系統(tǒng)中的一部分，受到社會(huì)環(huán)境各方面因素的影響。社會(huì)協(xié)作系統(tǒng)學(xué)派對(duì)

其他學(xué)派的形成（如社會(huì)技術(shù)系統(tǒng)學(xué)派、決策理論學(xué)派、系統(tǒng)理論學(xué)派）產(chǎn)生了積極

的影響。

但現(xiàn)代系統(tǒng)觀念的確立則必須首先歸功于生物學(xué)家貝塔朗菲（1947）的“一般

系統(tǒng)論”。貝塔朗菲認(rèn)為有可能制定出一種系統(tǒng)的、理論的、框架來描述現(xiàn)實(shí)世界

中的各種關(guān)系，而各學(xué)科間的相似性可以發(fā)展為一種一般系統(tǒng)模式。在這一理論的

指引下，許多管理學(xué)家都開始強(qiáng)調(diào)管理學(xué)研究與分析中的系統(tǒng)方法。以卡斯特、羅

森茨韋克為代表的系統(tǒng)管理學(xué)派在20世紀(jì)六十年代盛行一時(shí)。系統(tǒng)管理學(xué)派認(rèn)為，

從系統(tǒng)的觀點(diǎn)來考察和管理企業(yè)，有助于提高企業(yè)的整體效率，使各個(gè)系統(tǒng)和有關(guān)

部門的相互聯(lián)系網(wǎng)絡(luò)更清楚，更好地實(shí)現(xiàn)企業(yè)的總目標(biāo)。他們認(rèn)為系統(tǒng)方法是形成、

表述和理解管理思想最有效的手段。所謂系統(tǒng)，實(shí)質(zhì)上就是由相互聯(lián)系或相互依存

的一組事物或其組合所形成的復(fù)雜統(tǒng)一體。這些事物可以像汽車發(fā)動(dòng)機(jī)上的零件那

樣是實(shí)物，也可以像人體諸組成部分那樣是生物的，還可以像綜合起來的管理概念、

原則、理論和方法那樣是理論上的。盡管我們給理論規(guī)定出界限，以便更清楚地觀

察和分析它們，但是所有的系統(tǒng)（也許只有宇宙除外）都同它們的環(huán)境在相互起作用，

因而都受到其環(huán)境的影響。在這些觀點(diǎn)的影響下，企業(yè)家將不同的企業(yè)視為不同的

動(dòng)態(tài)系統(tǒng)加以經(jīng)營(yíng)，以便有序地達(dá)到某種預(yù)想的結(jié)果。正如理查德?舍恩伯格（1990）

所強(qiáng)調(diào)的：“企業(yè)的技能（如營(yíng)銷、工程、制造）應(yīng)該結(jié)合起來以便與連續(xù)的顧客

鏈聯(lián)系在一起”。

現(xiàn)代系統(tǒng)思想的出現(xiàn)徹底改變了人們的思維，除了一般系統(tǒng)理論，維納（1948）

提出的控制論（其內(nèi)容涉及最優(yōu)控制、自適應(yīng)、自組織系統(tǒng)、大系統(tǒng)理論），申農(nóng)

（1948）提出的信息論、普利高津（20世紀(jì)70年代）提出的“耗散結(jié)構(gòu)”理論、

哈肯（1976）提出的協(xié)同學(xué)理論、托姆（1972）提出的突變理論都極大地豐富了現(xiàn)

代系統(tǒng)理論的體系。這個(gè)體系推動(dòng)了今天關(guān)于復(fù)雜性組織的研究。

由于管理科學(xué)與系統(tǒng)科學(xué)的密切關(guān)系，運(yùn)籌學(xué)將它的方法論選擇為系統(tǒng)的方法

論就不足為奇。美國(guó)科學(xué)院國(guó)際開發(fā)署曾出版的一本書中，其書名就將運(yùn)籌學(xué)和系

統(tǒng)分析并列。切克蘭特從軟硬系統(tǒng)觀點(diǎn)對(duì)運(yùn)籌學(xué)的重新思考。薩特在20世紀(jì)70年

代末提出的系統(tǒng)分析和評(píng)價(jià)的方法——層次分析法。這些事實(shí)都說明運(yùn)籌學(xué)的特點(diǎn)

和性質(zhì)都包涵了系統(tǒng)性。在運(yùn)籌學(xué)的研究和解決問題的整體過程中，已形成系統(tǒng)問

題提出、系統(tǒng)設(shè)計(jì)、系統(tǒng)分析、系統(tǒng)實(shí)施、系統(tǒng)評(píng)價(jià)的完整架構(gòu)。伴隨著信息技術(shù)

的飛速發(fā)展，運(yùn)籌學(xué)對(duì)“管理即決策”所要求的決策支持能力也不斷增強(qiáng)，從解決

結(jié)構(gòu)化的問題到通過人機(jī)交互解決非結(jié)構(gòu)化的問題，從解決確定性的問題到解決不

定性的問題，從解決簡(jiǎn)單、局部的問題到復(fù)雜系統(tǒng)的整體問題，剛性的運(yùn)籌逐漸走

向了柔性的運(yùn)籌，關(guān)注的“事理”運(yùn)籌逐漸走向了能關(guān)注“人理”的運(yùn)籌，作業(yè)研

究的運(yùn)籌逐漸走向了戰(zhàn)略研究的運(yùn)籌。因而，運(yùn)籌學(xué)在實(shí)踐方面已經(jīng)具備了進(jìn)入決

策支持系統(tǒng)（DSS）的能力。

5.管理“叢林”中的管理科學(xué)和運(yùn)籌學(xué)

管理思想和理論的發(fā)展至今已經(jīng)歷了早期管理思想萌發(fā)、科學(xué)管理時(shí)代、社會(huì)

人時(shí)代和現(xiàn)代管理理論“叢林”四個(gè)階段。處于社會(huì)經(jīng)濟(jì)各個(gè)領(lǐng)域中的組織由于面

臨日益復(fù)雜的生存環(huán)境和內(nèi)部狀態(tài)對(duì)科學(xué)化決策和決策科學(xué)化的要求越來越高，即

使是非結(jié)構(gòu)化的問題和戰(zhàn)略級(jí)的問題，也迫切需要科學(xué)方法進(jìn)行知識(shí)挖掘并做出決

策支持。在這樣的趨勢(shì)下，美國(guó)管理學(xué)者孔茨所論及的涵蓋十一個(gè)學(xué)派的“叢林”

中出現(xiàn)決策理論學(xué)派、系統(tǒng)管理學(xué)派、數(shù)理學(xué)派（亦稱管理科學(xué)學(xué)派）就是相當(dāng)自

然的結(jié)果。由于這三個(gè)學(xué)派在科學(xué)方法上的注重，有時(shí)人們也把決策學(xué)派、系統(tǒng)學(xué)

派和數(shù)理學(xué)派統(tǒng)稱為管理科學(xué)學(xué)派。其代表性的人物有獲得1978年度的諾貝爾經(jīng)濟(jì)

學(xué)獎(jiǎng)的西蒙以及馬奇、卡斯特、羅森茨韋克、伯法等人。

盡管管理科學(xué)（ManagementScience）有極為廣泛的一般理解它是研究（人

類在有限的資源空間、無限拓展的技術(shù)和能力空間中）發(fā)生在實(shí)現(xiàn)組織目標(biāo)的管理

活動(dòng)中的具有復(fù)雜性、不定性、動(dòng)態(tài)性、創(chuàng)新性的社會(huì)行為及其規(guī)律的一門綜合性

交叉學(xué)科。因而既包含以定性分析為主的那些管理分支，如組織行為學(xué)和戰(zhàn)略管理,

同時(shí)也包含以定量分析為主的管理分支，如運(yùn)籌學(xué)和管理統(tǒng)計(jì)學(xué)。但是，管理科學(xué)

常常也被人們按照對(duì)于管理科學(xué)學(xué)派的理解加以限定性地闡釋和認(rèn)識(shí)——它是一門

應(yīng)用科學(xué)方法，借助數(shù)學(xué)符號(hào)和“關(guān)系模式”來闡述計(jì)劃、組織、控制、決策等管

理職能的“邏輯化推理”程序，尋求有限資源最優(yōu)配置以實(shí)現(xiàn)組織目標(biāo)并提供有效

決策支持。所以，所謂管理科學(xué)就成為了一門制訂用于管理決策的優(yōu)化模型，并把

這種模型通過人機(jī)交互系統(tǒng)應(yīng)用于管理之中，完成組織實(shí)現(xiàn)目標(biāo)的決策推導(dǎo)過程所

需的數(shù)理基礎(chǔ)的應(yīng)用科學(xué)。

在這種狹義的理解下，運(yùn)籌學(xué)自然成為了管理科學(xué)的技術(shù)和方法核心。然而，

就算是那些堅(jiān)持門派之見的管理學(xué)者也不得不承認(rèn)，即使是站在管理科學(xué)學(xué)派之外

來審視運(yùn)籌學(xué)，毫無疑問，運(yùn)籌學(xué)對(duì)于管理的各個(gè)學(xué)派的研究都是一種強(qiáng)有力的輔

助工具。

盡管運(yùn)籌學(xué)最開始所解決的企業(yè)管理問題集中于決策規(guī)則可以合理推導(dǎo)的、具有結(jié)

構(gòu)化問題特征的生產(chǎn)管理領(lǐng)域，但是隨著運(yùn)籌學(xué)的發(fā)展和與其它學(xué)科的交融（如系

統(tǒng)科學(xué)、計(jì)算機(jī)科學(xué)、心理學(xué)等），運(yùn)籌學(xué)也在逐漸從早期的機(jī)械論模式（現(xiàn)代行

為科學(xué)家往往如此認(rèn)為管理科學(xué)是機(jī)械論的延續(xù)，并認(rèn)為行為與數(shù)量方法是彼此隔

絕的）向生物模式和社會(huì)模式發(fā)出銜接的信號(hào)。正如胡戈?明期特貝格所說：“人

類最偉大的發(fā)明并不是輪子，而是軸。重要的是探明這些領(lǐng)域是如何互補(bǔ)的，以及

怎樣將它們結(jié)合起來應(yīng)用于一些重大項(xiàng)目?！绷⒆阌谶@樣的觀點(diǎn)，運(yùn)籌學(xué)或者管理

科學(xué)的周遭將不再有“管理的叢林”，而是一片拓向無盡未來的充滿生機(jī)的沃野。

管理學(xué)大師赫伯特?西蒙為此這樣寫到：“我們對(duì)已取得的進(jìn)步感到振奮……正在

朝著充滿活力的管理科學(xué)和基于管理科學(xué)的藝術(shù)邁進(jìn)?！?/p>

第一章線性規(guī)劃（重點(diǎn)、難點(diǎn)章節(jié)）

1.本章學(xué)習(xí)要求

（1）應(yīng)熟悉的內(nèi)容

a.預(yù)備知識(shí)：線形代數(shù)中的行變換、逆矩陣、秩、線形無關(guān)（相關(guān)）等基本

概念和計(jì)算方法。

（2）應(yīng)掌握的內(nèi)容

a.單純形法的改進(jìn)

b.大M法

（3）應(yīng)熟練掌握的內(nèi)容

a.線性規(guī)劃模型（一般形式，標(biāo)準(zhǔn)形式，向量矩陣形式，一般形式轉(zhuǎn)化為標(biāo)

準(zhǔn)形式）

b.線性規(guī)劃解的基本概念（可行解，最優(yōu)解，基，基向量，基變量，非基變

量，基解，基本可行解和退化的基本可行解，可行基）

c.基、基向量、基變量、基解之間的一一對(duì)應(yīng)關(guān)系

d.線性規(guī)劃的圖解

e.單純形法

(a)線性規(guī)劃的幾何意義(可行域的凸性，頂點(diǎn)和基本可行解的關(guān)系)

(b)第一判別定理(最優(yōu)解的判別)

(c)單純形表的構(gòu)成

(d)單純形法計(jì)算

(e)第二判別定理(無最優(yōu)解的判別)

f.經(jīng)濟(jì)管理中的線性規(guī)劃建模

g.LINDO軟件的使用和EXCEL中線性規(guī)劃的計(jì)算

2.本章重點(diǎn)難點(diǎn)分析

重點(diǎn)：線性規(guī)劃建模，單純形法

難點(diǎn)：?jiǎn)渭冃畏ㄖ械膿Q基迭代(實(shí)質(zhì)是初等行變換)，線性規(guī)劃建模，Lindo

軟件使用。

由于線性規(guī)劃是運(yùn)籌學(xué)的最重要的內(nèi)容之一，因此有必要分別就各節(jié)的內(nèi)容進(jìn)行分

析。

(1)線性規(guī)劃模型

a.線性規(guī)劃的一般形式

特點(diǎn)：目標(biāo)函數(shù)和約束條件都是線性的。

ff?+A+J.

*,“上?*4(?.目■

)

*?八*?1?4(??士)?,

?.4.a

b.線性規(guī)劃的標(biāo)準(zhǔn)形式及轉(zhuǎn)化

逐?H<1*<Q<3*?口“=?1

,11*1*,11*1*=.1

MM1fMMMM

??1?1**?■〃=?,

juxa<AiK20

在將線性規(guī)劃的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，要注意兩點(diǎn)：一是某一約束條件為“三”或

形式的不等式時(shí)，應(yīng)“+”一個(gè)非負(fù)松弛變量或“一”非負(fù)松弛變量；二是某個(gè)變量不

滿足非負(fù)約束時(shí)，要用新變量替換，以使標(biāo)準(zhǔn)型中所有的變量均滿足非負(fù)要求。下面，用一個(gè)

例子予以說明。

例1（P8例3）MinZ=x,+2x2+3x3

s.t.-2TI+必+?W9

-3xi+?+2?24

3xi-2應(yīng)-3*3=-6

X\WO,X2NO,尤3任意。

令xi'=一x”則的=一短（新變量替換），且獷-0；

令X3=X3'一冷”（兩個(gè)新變量替換），且X3‘，X3”》0；

在第一和第二個(gè)不等式約束中分別引入松弛變量：X型右，且M，X520,將上述線性規(guī)

劃的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形。

MaxZ'=R-2切一3a3'f）

2%1'+M+（%3f一冗3”）+/4=9

n

3xi'+X2+2（X3'—x3）-x5=4

3xi'+2處+3（均'一與"）=6

",處，右’,冗3”，X4,招20.

c.標(biāo)準(zhǔn)形式的向量矩陣表達(dá)（P8）

旭欣式：

MUTZ-CT

AT??便求：皿煙由班的,且?4?）

X20

INKMft：CfqQ“

A'

m??之，，2：o

??：4?■低息aQ

'■i,■a?0,

由線性規(guī)劃的向量矩陣形式，可以清楚地看到，線性規(guī)劃模型的三要素就是資源向量b,

價(jià)值向量C,系數(shù)矩陣A（一般都假設(shè)A是滿秩的）。其中，資源向量b表示了稀缺資源的種類

和限度：價(jià)值向量c反映了單位產(chǎn)品（廣義）所創(chuàng)造的收益或形成的成本；而系數(shù)矩陣4是現(xiàn)

有生產(chǎn)技術(shù)、生產(chǎn)工藝、管理水平的具體體現(xiàn)。只要這三個(gè)要素確定了，相應(yīng)的線性規(guī)劃模型

就確定了。

例2目標(biāo)函數(shù)：MaxZ=2vi+3x2

約束條件：*I+2到+必=8

4x,+工4=16

4x2+》5=12

X|,X2,X3,X4,x5NO.

其向量矩陣形式為

o)

UL4JUMM.aM

(2)線性規(guī)劃解的概念(P9,重點(diǎn)章節(jié))

這?節(jié)為學(xué)習(xí)者構(gòu)建了線性規(guī)劃求解所需的基本概念，包含可行解、最優(yōu)解、基、基向量、

基變量、非基變量、基解、基本可行解、退化的基本可行解、可行基等，且概念間存在緊密的

關(guān)系。下面用一個(gè)例子予以解釋。

例3：目標(biāo)函數(shù)：MaxZ=2XI+3X2

約束條件：X|+2X2+X3=8

4xi+*4=16

4x2+x$=12

為，必，工3，14，15

其矩陣形式為:

MuK-CX

M-b

JT20JPthC-(Z3000)

Q2100r

4?4。0l。?(R4旦日琨

t0400lj

’4、

Ap1

*■盯,6-tf>AM-3￡N-5.

a.基：基是線性規(guī)劃中最基本的概念之一。基是由系數(shù)矩陣A中的線

性無關(guān)的列向量構(gòu)成的可逆方陣。用來構(gòu)成基的列向量稱為該基的基向

量。由于選取的列向量不同，基可能有多個(gè)（數(shù)目最多不超過V）。在

計(jì)算基的數(shù)目時(shí)，將含有相同列向量的基計(jì)為一類（個(gè)），不考慮其中

列向量的排列順序。但在對(duì)單純形表計(jì)算的過程中，基中列向量的排列

順序卻必須加以注意。上式中所有的基被羅列如下，可以看到基的數(shù)目

沒有超過片=10個(gè)。

q?M4出

par

*-(444)-U44)4叫4oo

,o4o

4-U4叫4o

b.基變量：當(dāng)基選定后，其對(duì)應(yīng)的基變量和非基變量就被唯一確定下

來。由基變量構(gòu)成的向量稱為基變量向量。如上例中，當(dāng)基選&?6冗同

時(shí)，該基對(duì)應(yīng)的基變量為小，X4,X5,非基變量為xbM，基變量向量為

M，F(xiàn)；又如當(dāng)基選為36力&時(shí)，該基對(duì)應(yīng)的基變量向量

與寸。非基變量為X1,X2.值得注意的是在基變量向量中基變量

的排列順序要與基中列向量（基向量）的排列順序一致。

C.基解：當(dāng)基選定之后，令非基變量全部等于0,此時(shí)，通過求解約

束條件形成的方程組（不考慮變量的非負(fù)要求）就可以把基變量的值確

定下來。這樣得到的解被稱為基解。如上例中，當(dāng)基選為Bi時(shí)，令非

基變量/=0=0,則上述約束條件變?yōu)槿缦路匠探M，

X3=8

冗4=16

%5=12

其基解為x=(0081612)T.

求基解還可利用公式BXB=b進(jìn)行，因?yàn)榛强赡骊嚕蔢B=B-

Ib.由此上例中的基變量的值

再舉一例。若選基B3=(P4P5PI)=C：：J,則

81

川(：)即基B3對(duì)應(yīng)的基解x=(800-16

注意：由于非基變量值被設(shè)為()，故談到基解時(shí)，常指基變量xB的值。

d.基本可行解：若XB=BTb20,則此時(shí)的基解被稱為基本可行解；

同時(shí)，此基解對(duì)應(yīng)的基被稱為可行基。上例中Bi是可行基，因?yàn)?/p>

“建修呼川；而B3不是可行基，因?yàn)榻?卜612/10.

e.退化的基本可行解：若XB=BTbNO,但XB=BTb才0,即存某基

變量的值為0,則此時(shí)的基解被稱為退化的基本可行解；同時(shí)，此基解

對(duì)應(yīng)的基被稱為退化的可行基。

f.基、基向量、基變量、基解之間存在----對(duì)應(yīng)關(guān)系。

圖i.i基、基向量、基變量、基解之間的——對(duì)應(yīng)關(guān)系。

(3)線性規(guī)劃的圖解

例4(P10,例4)

MaxZ=2XI+3X2

2芍+2應(yīng)<12①

X|+2應(yīng)W8②

4匹W16③

4X2W12④

》0,X220

解：圖解法僅針對(duì)二元線性規(guī)劃問題。一般應(yīng)首先畫出可行域和目標(biāo)函數(shù)等于0時(shí)的直線，然

后判斷目標(biāo)函數(shù)等值線的移動(dòng)方向。此例中，由于目標(biāo)函數(shù)可變形為：必=-2/3X|+Z/3,Z/3

是目標(biāo)函數(shù)等值線的縱截距。所以，等值線向右上角移動(dòng)時(shí)，Z增加。這個(gè)移動(dòng)過程直至可行

域邊界上（4,2）點(diǎn)時(shí)停止。此時(shí)，Z取得最大值，（4,2）為最優(yōu)解。

圖1.2線性規(guī)劃的圖解法示例

(4)單純形法(重點(diǎn)、難點(diǎn))

a.線性規(guī)劃的幾何意義

(a)凸集(P13)：設(shè)K是n維歐氏空間的點(diǎn)集，若任意兩點(diǎn)x⑴，x(2)￡

K,貝!Jx⑴與小)連線上的所有點(diǎn)a?】)+(l—a)x⑵RK,那么稱集合

K為凸集。

(b)凸組合：設(shè)x⑴/⑵，…小優(yōu))是n維歐氏空間中的k個(gè)點(diǎn)，若存在

內(nèi)，n2,…，內(nèi)，內(nèi)Wl,M,三1,2,…，左，使X=|11X⑴+M

k)

X⑵+…+gk?,則稱X為X⑴，X⑵的凸組合。

(c)凸集的頂點(diǎn)(P14)：設(shè)K是凸集，XEK.若X不能被任意兩個(gè)

不同于它的點(diǎn)X⑴，X⑵￡K的凸組合表示，即x=ax⑴+(1—a)x(2),0

<a<lo則稱x為K的一個(gè)頂點(diǎn)(或極點(diǎn))。即，若x是集合K的頂

點(diǎn)，則x一定不在K中任意不同于它的兩點(diǎn)的連線內(nèi)。

(d)(P14定理1)線性規(guī)劃的可行域是凸集。

(e)(P14定理2)線性規(guī)劃的基本可行解一一對(duì)應(yīng)于可行域的頂點(diǎn)。

(f)線性規(guī)劃的可行域中的任一點(diǎn)(可行解)都可用可行域的頂點(diǎn)(基

本可行解)的凸組合表示，如果可行域是有界凸集。

(g)(P15定理3)若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可在某個(gè)基本

可行解上取得，也即在可行域的某個(gè)頂點(diǎn)(極點(diǎn))上取得。

b.最優(yōu)性的檢驗(yàn)與判別（P173-5）

（a）第一判別定理（最優(yōu)解的判別）

線性規(guī)劃模型的目標(biāo)函數(shù)為MAXZ時(shí)，對(duì)于某可行基B（）,若檢驗(yàn)向量CBB

-IA-C>0,則與基B對(duì)應(yīng)的基本可行解XB=B1,XN=0為最優(yōu)解（基本最優(yōu)解），此時(shí)的

基B稱為最優(yōu)基。

線性規(guī)劃模型的目標(biāo)函數(shù)為MINZ時(shí)，對(duì)于某可行基B（,若檢驗(yàn)向量CBB

一以一CW0,則與基B對(duì)應(yīng)的基本可行解XB=BXN=0為最優(yōu)解（基本最優(yōu)解），此時(shí)

的基B稱為最優(yōu)基。

為了更好地說明這個(gè)定理，我們給出了它的簡(jiǎn)單推導(dǎo)過程。

僅就求MAX的線性規(guī)劃問題已化為標(biāo)準(zhǔn)形后的情形予以討論。

?

設(shè)x是任一可行解，B是某個(gè)可行基（B%，0）,此基下的基解對(duì)應(yīng)的目標(biāo)函數(shù)值為

且檢驗(yàn)向量CBB“A-c》。，

則在約束條件的左右兩邊同時(shí)乘以廿,得到

將此式加到F=cx,則得到

因?yàn)镃BB^A—c20,x^O,所以，即任一可行解x對(duì)應(yīng)的目標(biāo)函數(shù)值F都

不超過基B的基解對(duì)應(yīng)的目標(biāo)函數(shù)值5、，故，與基B對(duì)應(yīng)的基本可行解XB=B",網(wǎng)=。為

最優(yōu)解(基本最優(yōu)解)，此時(shí)的基B稱為最優(yōu)基。

注意：教材所定義的檢驗(yàn)向量為C-CBB^A,故定理表述略有不同。另外CB是基變量對(duì)應(yīng)的目標(biāo)函數(shù)中的

系數(shù)構(gòu)成的行向量。其分量的排列順序與基變量的排列順序一致。如XB=(X4X5X1)T,則CB=(C4C5G).

例5：目標(biāo)函數(shù)：MaxZ=2XI+3X2

約束條件：X\+2Q+/3=8

4xi+工4=16

4%2+欠5=12

禮必，元3,工4,工520

此線性規(guī)劃問題的向量矩陣形式為

itaxZ-CT

co

K4＞：C-p3。o機(jī)依，勺勺5

o(A

400io|-m料5A2

040

當(dāng)選的基為

?■?，：?8T，?(4)2Q.fl.C??1!?$?.■口0□)

01/4OVl2I

-21/21400t0-(23000)

(1/a-1/8oj(o40

-(D03/21/80)20

由第一判別定理知，此時(shí)的基本可行解為最優(yōu)解，基為最優(yōu)基。最優(yōu)解為XI=4,A-5=4,M=2,

13=工4=0.

C.單純形表

（a）單純形表的形式

'如0_|_401%2A電1a

則=（竿拌吟器￡）=用憎傳$陽

ZAJ,

設(shè)基為B1則與此基對(duì)應(yīng)的單純

形表為:

注意:

①單純形表中行列記數(shù)從0開始，分別為第0,1,…,m行，第0,1,…,n列。

②為求基的逆矩陣簡(jiǎn)便，一般我們希望系數(shù)矩陣A中含有單位陣形式的基。因?yàn)椋瑔挝魂嚨哪婢仃嚲褪撬?/p>

身。如果這種情形存在時(shí)，那么構(gòu)造第一張單純形表（初始單純形表）時(shí)，就可用單位陣形式的基作為初始基。

此時(shí)，寫出第一張單純形表就非常容易。

③若系數(shù)矩陣A中不含有單位陣形式的基，一種“笨”的方法是直接任選一個(gè)可行基作為初始基，構(gòu)造第一

張單純形表；但一般為避免煩瑣的求基的逆矩陣的過程，我們會(huì)采用其它的方法進(jìn)行，這將在后面予以介紹。

0

c

s

fTos

r4^

。lrQl

禧iu

0oLO

J

o。

o)

例

(接例5)

d.單純形法計(jì)算

(a)單純形法的思想：因?yàn)榭尚谢卸鄠€(gè)，不可能用窮舉法逐一驗(yàn)證，

得到最優(yōu)基，故采取換基迭代的方法，從容易計(jì)算其逆的初始基對(duì)應(yīng)的

單純形表開始，逐步得到不同的可行基對(duì)應(yīng)的單純形表，直至找到最優(yōu)

基對(duì)應(yīng)的單純形表為止。換基迭代的過程實(shí)質(zhì)上是一個(gè)不斷改進(jìn)的過

程。

(b)計(jì)算步驟例釋(接例6)

①選單位陣形式的基作為初始基，寫出初始單純形表。若檢驗(yàn)向量

CBBTA-C中含負(fù)的檢驗(yàn)數(shù)，則非最優(yōu)，進(jìn)行換基迭代。否則，停止，已找到最優(yōu)解。

②確定誰入基：負(fù)的最小檢驗(yàn)數(shù)所對(duì)應(yīng)的系數(shù)矩陣中的列向量入基；

③確定主元素：?jiǎn)渭冃伪砩纤x入基列中取正值的元素分別與同行第0列的元素相除，

入基列中取得比值最小者的兀素作為此表的主元素，并畫框標(biāo)示；

④確定誰出基：簡(jiǎn)單地說，主元素在第幾行，就將基中第幾個(gè)基向量換出；也可由單純

形表中基變量所對(duì)應(yīng)的的列向量是單位坐標(biāo)向量這一特點(diǎn)，直接觀察哪一個(gè)單位坐標(biāo)向量的“1”

元素與主元素同行，從基中被換出的基向量就是表中該單位坐標(biāo)向量列對(duì)應(yīng)的那一個(gè)列向量。

⑤利用換基迭代公式，得到下一張（新的基）單純形表。

：1力r其中，為

：主元素二對(duì)上面這張革純

'形表而百，—Aon—4j

%=占-=rr=3,s=2o...........

i=0,1,A,m;j=O,1,A,n

⑥重復(fù)上述過程，直至找到最優(yōu)解

例7（接例6）

選單位陣形式的基B=（P3P4P5）作為初始基，寫出初始單純形表。

fxfo-300

\*nn4nn

因檢驗(yàn)向量CBB-A-C=（-2-3000）中含負(fù)的檢驗(yàn)數(shù)，故非最優(yōu)，進(jìn)行第一次換基迭代。

|②P?三|③主元素的確定：表上入基列中正的元素

為1，4,分別與同行第0列的元素相除,

2/1=2，16/4=4＞顯然，比值最小者為2?

mo/眄殖為）由此就將取得此最小值的入基列中的元

索“2”作為此表的主元素，畫上框.

按⑤換基迭代后，得到新基B=（P3P4P2）下的單純形表，執(zhí)行步驟⑥，從①開始重復(fù)操

作。因此時(shí)檢驗(yàn)向量CBB-A-C：（—20003/4）存在負(fù)的檢驗(yàn)數(shù)，故非最優(yōu)，按②、

③、④、⑤進(jìn)行第二次換基迭代。

③主元素的確定(即單純龍表中畫框的

④P,出基

元素)：入基列中正的元素為1,4,分

②PI入基

別與同行第。列的元素相除，2/1=2,

16/4=4＞顯然，比值最小者為2,由此

就將取得此最小值的入基列中的元素

“2”作為此表的主元素，畫上框.

130020-1/4,

a[4aA).2toio-io

**00-41p]

，3°I0°"J第二次換基迭代后，得到新基B=(PiP4P2)下的單純

形表，執(zhí)行步驟⑥，從①開始重復(fù)操作。因?yàn)榇藭r(shí)檢驗(yàn)向量CBB'A-C=(0020-1/4)

存在負(fù)的檢驗(yàn)數(shù)，故非最優(yōu)，進(jìn)行第三次換基迭代。換基迭代的步驟同上。

第三次換基迭代后得到新基B=(P|P5P2)下的單純形表為：

,,14003/21/S0

8-01為同).41001/40

400-21/2I

2011/2-1/80

此時(shí)檢驗(yàn)向量CBB'A-C=(003/21/80)20,由第一判別定理知，已取得最優(yōu)

解，最優(yōu)解為x*=(42004)T.

注意：?jiǎn)渭冃畏〒Q基迭代的實(shí)質(zhì)是初等行變換。

（c）退化與BLAND法則：當(dāng)存在退化的基本可行解時(shí)，可能會(huì)出現(xiàn)死

循環(huán)的情形。為避免此情形的發(fā)生，可運(yùn)用BLAND法則，即確定誰入

基時(shí)，若最小負(fù)檢驗(yàn)數(shù)不唯一，則選位置最靠前的檢驗(yàn)數(shù)處入基；確定

主元素時(shí)，若最小比值不唯一，則將取得最小比值的入基列中位置最靠

前的元素，作為主元素。

（d）無窮多最優(yōu)解：當(dāng)最優(yōu)單純形表中，某非基變量的檢驗(yàn)數(shù)為（）時(shí)，

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

e.第二判別定理（無最優(yōu)解的判別）：

（a）線性規(guī)劃模型的目標(biāo)為MaxZ時(shí)

對(duì)某個(gè)單純形表T（B）=（M）（m+i）x（n+i）,若有某檢驗(yàn)數(shù)如V0,且如W0（/=1,2,…,m）,

則對(duì)應(yīng)的線性規(guī)劃問題（L）或者無可行解；或者目標(biāo)函數(shù)值Z無（上）界。因此，無最優(yōu)解。

n?-

（b）線性規(guī)劃模型的目標(biāo)為MinZ時(shí)

對(duì)某個(gè)單純形表T（B）=（%）（m+i）xgi）,若有某檢驗(yàn)數(shù)如＞0,且如W0（/=1,2,

則對(duì)應(yīng)的線性規(guī)劃問題（L）或者無可行解；或者目標(biāo)函數(shù)值Z無（下）界。因此，無最優(yōu)解。

例8（P26?27例8第二判別定理的應(yīng)用）：

MaxZ=2xi+3x2

4為W16

哪4即

A-（I0I）C-03Q-Ex，X、》0

人1，42'J

解：因?yàn)榇藭r(shí)檢驗(yàn)數(shù)尻2=-3>0,且62=0W0,所以該線性規(guī)劃問題無最優(yōu)解。

f.完整的單純形法的計(jì)算步驟（P19）

（5）單純形法的進(jìn)一步討論（P22）

當(dāng)在系數(shù)矩陣A中，找不到單位陣形式的基作為初始基時(shí)，一種直觀的思想可供借鑒一

構(gòu)造?個(gè)與現(xiàn)在的線性規(guī)劃有密切關(guān)系的新的線性規(guī)劃問題，通過求解這個(gè)新的線性規(guī)劃問題,

從而找出原線性規(guī)劃的最優(yōu)解。這種思想產(chǎn)生了兩種做法：大M法、兩階段法，統(tǒng)稱人工變量

法。此處，僅介紹其中的大M法。

a.大M法例釋（人工變量法之一）

例9MaxZ=-3修+3心