物流運(yùn)籌學(xué)完整版課件全套ppt教學(xué)教程最全整套電子講義幻燈片(最新)

1、運(yùn)籌學(xué)(Operations Research)第一章 導(dǎo)論1.運(yùn)籌學(xué)的定義2.運(yùn)籌學(xué)的特點(diǎn)和工作步驟3.運(yùn)籌學(xué)和物流的關(guān)系4.物流中的運(yùn)籌學(xué)問題5.運(yùn)籌學(xué)的發(fā)展簡史知識要點(diǎn)1.1運(yùn)籌學(xué)概述 運(yùn)籌學(xué)是用數(shù)學(xué)方法研究各種系統(tǒng)最優(yōu)化問題的學(xué)科。其研究方法是應(yīng)用數(shù)學(xué)語言來描述實(shí)際系統(tǒng)，建立相應(yīng)的數(shù)學(xué)模型，并對模型進(jìn)行研究和分析，據(jù)此求得模型的最優(yōu)解；其目的是制定合理運(yùn)用人力、物力和財(cái)力的最優(yōu)方案，為決策者提供科學(xué)決策的依據(jù)；其研究對象是各種社會系統(tǒng)，可以使對新的系統(tǒng)進(jìn)行優(yōu)化設(shè)計(jì)，也可以是研究已有系統(tǒng)的最佳運(yùn)營問題。因此，運(yùn)籌學(xué)既是應(yīng)用數(shù)學(xué)，也是科學(xué)管理，同時也是系統(tǒng)工程的基礎(chǔ)之一。1.1.1運(yùn)籌學(xué)的

2、概念和特點(diǎn)（1）運(yùn)籌學(xué)的概念運(yùn)籌學(xué)( Operations Research )是一門新興的應(yīng)用學(xué)科。由于它所研究的對象極其廣泛，所以有著許多不同的定義。英國運(yùn)籌學(xué)雜志認(rèn)為：“運(yùn)籌學(xué)是運(yùn)用科學(xué)方法(特別是數(shù)學(xué)方法)來解決那些在工業(yè)、商業(yè)、政府和國防部門中有關(guān)人力、機(jī)器、物質(zhì)、金錢等大型系統(tǒng)的指揮和管理方面出現(xiàn)的問題的科學(xué)，目的是幫助管理者科學(xué)地決定其策略和行動?！?.1.1運(yùn)籌學(xué)的概念和特點(diǎn)美國運(yùn)籌學(xué)會(1976年)的定義是:“運(yùn)籌學(xué)是研究用科學(xué)方法來決定在資源不充分的情況下如何最好地設(shè)計(jì)人機(jī)系統(tǒng)，并使之最好地運(yùn)行的一門學(xué)科?！边@從側(cè)面描寫了運(yùn)籌學(xué)的特點(diǎn)。聯(lián)邦德國科學(xué)辭典（1978年)上的定義

3、是:“運(yùn)籌學(xué)是從事決策模型的數(shù)學(xué)解法的一門科學(xué)。”從這些定義中我們可以著出，雖然說法不一，但其基本含義大致相同，都包含了以下三方面的內(nèi)容： 1.1.1運(yùn)籌學(xué)的概念和特點(diǎn) 從這些定義中我們可以著出，雖然說法不一，但其基本含義大致相同，都包含了以下三方面的內(nèi)容： 既定的目標(biāo)和條件； 科學(xué)的方法和技術(shù)； 最優(yōu)的決策方案。1.1.1運(yùn)籌學(xué)的概念和特點(diǎn)（2）運(yùn)籌學(xué)的特點(diǎn) 運(yùn)籌學(xué)屬于應(yīng)用數(shù)學(xué)范疇，具體地說，它是一門管理數(shù)學(xué)，是一種通過對系統(tǒng)進(jìn)行科學(xué)的定量分析，從而發(fā)現(xiàn)問題、解決問題的系統(tǒng)方法論。與其他的自然科學(xué)不同，運(yùn)籌學(xué)研究的對象是“事”，而不是“物”，它揭示的是“事”的內(nèi)在規(guī)律性，研究的是如何把“事”

4、辦得更好的方式方法。 由此，我們可以看出運(yùn)籌學(xué)主要有以下三個特點(diǎn): 1.1.1運(yùn)籌學(xué)的概念和特點(diǎn) 1.系統(tǒng)的整體優(yōu)化 所謂系統(tǒng)可以理解為是由相互關(guān)聯(lián)、相互制約、相互作用的部分組成的具有某種特定功能的有機(jī)整體。 例如物流系統(tǒng)由很多子系統(tǒng)組成，包括采購、運(yùn)輸、倉儲、配送、流通加工、信息處理等，各子系統(tǒng)工作的好壞直接影響企業(yè)經(jīng)營管理的好壞。但各子系統(tǒng)的目標(biāo)往往不一致，生產(chǎn)部門為提高勞動生產(chǎn)效率希望盡可能增大批量；銷售部門為滿足更多用戶的需要，要求增加花色品種；財(cái)務(wù)部門希望減少積壓，加速流動資金周轉(zhuǎn)，降低成本。 1.1.1運(yùn)籌學(xué)的概念和特點(diǎn)2.多學(xué)科的配合 一個企業(yè)的有效管理涉及很多方面，運(yùn)籌學(xué)研究中

5、吸收了來自不同領(lǐng)域、具有不同經(jīng)驗(yàn)和技能的專家。由于專家們來自不同的學(xué)科領(lǐng)域，具有不同的經(jīng)歷經(jīng)驗(yàn) ,因此增強(qiáng)了集體提出問題和解決問題的能力。這種多學(xué)科的協(xié)調(diào)配合在研究的初期、在分析和確定問題的主要方面、在選定和探索解決問題的途徑時，顯得尤其重要。3.模型方法的應(yīng)用 運(yùn)籌學(xué)的研究不同于其他學(xué)科的實(shí)驗(yàn)室方法，其研究往往不能搬到實(shí)驗(yàn)室，而是建立這個問題的數(shù)學(xué)模型和模擬模型。如果說輔助決策是運(yùn)籌學(xué)應(yīng)用的核心，那么建立模型就是運(yùn)籌學(xué)方法的精髓。1.1.1運(yùn)籌學(xué)的概念和特點(diǎn)（3）運(yùn)籌學(xué)的工作步驟提出和形成問題：要弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有關(guān)參數(shù)，搜集有關(guān)資料。建立模型：把問題中可控變量

6、、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表來出來。求解：用各種手段(主要是數(shù)學(xué)方法，也可用其他方法)將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要求可由決策者提出。解的檢驗(yàn)：首先檢查求解步驟和程序有無錯誤，然后檢查解是否反映現(xiàn)實(shí)問題。1.1.1運(yùn)籌學(xué)的概念和特點(diǎn)解的控制：通過控制解的變化過程決定對解是否要作一定的改變。解的實(shí)施：是指將解應(yīng)用到實(shí)際中必須考慮到實(shí)施的問題。如向?qū)嶋H部門講清楚解的用法，在實(shí)施中可能產(chǎn)生的問題和修改。以上過程應(yīng)反復(fù)進(jìn)行。1.1.2運(yùn)籌學(xué)的發(fā)展簡史 運(yùn)籌學(xué)的思想由來已久，我國歷史上在軍事和科學(xué)技術(shù)方面對運(yùn)籌思想的運(yùn)用是世界聞名的。軍事方

7、面；公元前6世紀(jì)春秋時期著名的孫子兵法、戰(zhàn)國時期的“田忌賽馬”農(nóng)業(yè)運(yùn)輸方面；北魏時期科學(xué)家賈思勰的齊民要術(shù)、“一舉而三役濟(jì)”的“丁渭造宮”水利方面：四川都江堰工程。1.1.2運(yùn)籌學(xué)的發(fā)展簡史 運(yùn)籌學(xué)是20世紀(jì)40年代開始形成的一門應(yīng)用數(shù)學(xué)學(xué)科，起源于第二次世界大戰(zhàn)期間英、美等國的軍事運(yùn)籌小組。在第二次世界大戰(zhàn)初期，英美兩國的軍事部門迫切需要研究如何將非常有限的人力和物力分配到各項(xiàng)軍事活動中，以達(dá)到最好的作戰(zhàn)效果。 第二次世界大戰(zhàn)結(jié)束后，那些從事作戰(zhàn)研究的人員紛紛轉(zhuǎn)入工業(yè)生產(chǎn)部門和商業(yè)部門。由于組織內(nèi)部與日俱增的復(fù)雜性和專門化所產(chǎn)生的問題，使人們認(rèn)識到這些問題本質(zhì)上與作戰(zhàn)中曾面臨的問題極為相似，

8、只是具有不同的現(xiàn)實(shí)環(huán)境而己，運(yùn)籌學(xué)于是進(jìn)入工商企業(yè)和其他部門。1.1.2運(yùn)籌學(xué)的發(fā)展簡史 1950年，英國的伯明翰大學(xué)正式開設(shè)了運(yùn)籌學(xué)課程，同年第一本運(yùn)籌學(xué)雜志運(yùn)籌學(xué)季刊(O.R.Quarterly)在英國創(chuàng)刊。1951年，美國的莫爾斯(P.M. Morse)和金博爾(G.E. Kimball)合著的運(yùn)籌學(xué)方法正式出版；1952年，美國運(yùn)籌協(xié)會成立，并于同年出版了運(yùn)籌學(xué)雜志Journal of ORSA，所有這些標(biāo)志著這門科學(xué)基本形成，隨后這門學(xué)科的理論體系也在不斷完善。 20世紀(jì)50年代后期，我國著名科學(xué)家錢學(xué)森、華羅庚、許國志等將運(yùn)籌學(xué)引入中國，并結(jié)合我國的特點(diǎn)在國內(nèi)推廣應(yīng)用，著名的“打麥

9、場的選址問題”和“中國郵遞員問題”就是在那個時期提出的。1.1.2運(yùn)籌學(xué)的發(fā)展簡史 目前，國內(nèi)運(yùn)籌學(xué)的專門刊物或較多刊登運(yùn)籌學(xué)理論和應(yīng)用的刊物主要有：運(yùn)籌學(xué)學(xué)報(bào)、運(yùn)籌與管理、系統(tǒng)工程學(xué)報(bào)、系統(tǒng)工程理論與實(shí)踐、系統(tǒng)工程理論方法應(yīng)用、數(shù)量經(jīng)濟(jì)、技術(shù)經(jīng)濟(jì)研究、預(yù)測、系統(tǒng)工程和系統(tǒng)科學(xué)與數(shù)學(xué)等。 經(jīng)過半個多世紀(jì)的發(fā)展，運(yùn)籌學(xué)的內(nèi)容日趨成熟，逐漸形成了其理論與方法的基本框架，可以簡單地概括為兩技術(shù)、五規(guī)劃和五論。1.1.2運(yùn)籌學(xué)的發(fā)展簡史 (1)兩技術(shù)。當(dāng)遇到有多種備選方案或不確定的情況，可以用決策技術(shù)來選擇最滿意的戰(zhàn)略；在很多時候，決策者都需要為工程制定計(jì)劃，列出時間表，并對其進(jìn)行管理，而工程往往是巨

10、大的，包含很多工種、部門與員工等這時網(wǎng)絡(luò)計(jì)劃技術(shù)可以幫助決策者完成工程時間表的制訂與控制。(2)五規(guī)劃。在一定約束條件下尋求某種目標(biāo)最大或最小的方法就是規(guī)劃方法要解決的問題，包括線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、目標(biāo)規(guī)劃與動態(tài)規(guī)劃。一個典型的應(yīng)用就是企業(yè)在一定資源限制下尋求利潤最大或成本最小。1.1.2運(yùn)籌學(xué)的發(fā)展簡史 (3)五論。在決策過程中，首先要考慮的就是競爭對手的情況，這就需要應(yīng)用對策論方法；企業(yè)必須維持一定的原料或產(chǎn)品的庫存量以滿足需求，同時為控制成本又必須壓低庫存，這就是庫存論要解決的問題：而圖論是用圖形來描述問題，圖形是由一些點(diǎn)以及一些點(diǎn)之間的連線表示，可用于解決運(yùn)輸設(shè)計(jì)、信息系統(tǒng)

11、的設(shè)計(jì)以及工程時間表的設(shè)計(jì)；有時也需要解決各種服務(wù)系統(tǒng)在排隊(duì)等待現(xiàn)象中的概率特性，這就需要排隊(duì)論，而非常重要的產(chǎn)品、工程的可靠性問題就需要可靠性模型和決策論來解決。1.2運(yùn)籌學(xué)與物流 物流起源于第二次世界大戰(zhàn)期間的軍事后勤，它與科學(xué)管理共同采用的一項(xiàng)主要工具就是運(yùn)籌學(xué)方法，運(yùn)籌學(xué)應(yīng)用的典型案例大都是物流作業(yè)或管理。 物流運(yùn)籌學(xué)是運(yùn)用數(shù)學(xué)模型、統(tǒng)計(jì)方法與代數(shù)等數(shù)量研究方法與技術(shù)為物流決策提供支持的一門新興學(xué)科，它要求以系統(tǒng)的觀念來看待和解決物流系統(tǒng)中日趨復(fù)雜化和動態(tài)化的決策問題。根據(jù)問題的要求，通過數(shù)學(xué)的分析和運(yùn)算，對各種廣義資源的運(yùn)用、籌劃以及相關(guān)決策等問題做出綜合性的、合理的優(yōu)化安排，以便更

12、經(jīng)濟(jì)、更有效地發(fā)揮有限資源的效益。1.2.1物流中的運(yùn)籌學(xué)問題 運(yùn)籌學(xué)與物流系統(tǒng)的關(guān)系如下： 從兩者產(chǎn)生的時間來看，都是在二時期為軍事所重視并利用發(fā)展起來的，同時產(chǎn)生必然有他們的聯(lián)系性。 從功能上來說，運(yùn)籌學(xué)是用來解決最優(yōu)資源配置，而物流系統(tǒng)的主要功能(目標(biāo))也正是追求一種快速、及時、節(jié)約、合理的物流服務(wù)，這一點(diǎn)正好不謀而合。 1.2.1物流中的運(yùn)籌學(xué)問題 為此，兩者從一開始到現(xiàn)在都密切地聯(lián)系在一起，并互相滲透和交叉發(fā)展。雖然后來一段時間，物流發(fā)展相對滯后于運(yùn)籌學(xué)，但隨著全球經(jīng)濟(jì)的不斷發(fā)展，物流系統(tǒng)中運(yùn)籌學(xué)的運(yùn)用不斷擴(kuò)大，運(yùn)籌學(xué)的作用不斷凸顯。 運(yùn)籌學(xué)的主要分支在物流管理中都得到廣泛的應(yīng)用。

13、（1）規(guī)劃論 （2）排隊(duì)論 （3）存儲論 （4）決策分析理論 （5）對策論 （6）圖論與網(wǎng)絡(luò)分析1.2.1物流中的運(yùn)籌學(xué)問題（1）規(guī)劃論 規(guī)劃論主要研究計(jì)劃管理工作中有關(guān)安排和估計(jì)的問題。一般可以歸納為在滿足既定的要求下，按某一衡量指標(biāo)來尋求最優(yōu)方案的問題。如果目標(biāo)函數(shù)和約束條件的數(shù)學(xué)表達(dá)式都是線性的，則稱為“線性規(guī)劃”；否則稱為“非線性規(guī)劃”。如果所考慮的規(guī)劃問題可按時間劃為幾個階段求解，則稱為“動態(tài)規(guī)劃”。1.2.1物流中的運(yùn)籌學(xué)問題 應(yīng)用規(guī)劃論的典型的例子如“運(yùn)輸問題”，即將已給定數(shù)量和單位運(yùn)價的某種物資從供應(yīng)站運(yùn)送到消費(fèi)站，要求在供銷平衡的同時，定出流量與流向，使總運(yùn)輸成本最小。我國曾

14、運(yùn)用線性規(guī)劃進(jìn)行水泥、糧食和鋼材的合理調(diào)運(yùn)，取得了較好的經(jīng)濟(jì)效益。運(yùn)用規(guī)劃論方法還可以解決“合理選址”問題、“車輛調(diào)度”問題、“貨物配裝”問題、“物流資源(人員或設(shè)備)指派”問題、“投資分配”問題等。1.2.1物流中的運(yùn)籌學(xué)問題1.2.1物流中的運(yùn)籌學(xué)問題（2）排隊(duì)論 排隊(duì)論主要研究具有隨機(jī)性的擁擠現(xiàn)象，它起源于有關(guān)自動電話的研究。由于叫號次數(shù)的多少和通話時間的長短都是不確定的，對于多條電話線路，叫通的機(jī)會和線路空閑的機(jī)會都是隨機(jī)的，因此服務(wù)質(zhì)量和設(shè)備利用率之間存在矛盾。所有這類問題度可以形象地描述為顧客來到服務(wù)臺前要求接待服務(wù)。如果服務(wù)臺已被其他顧客占用，那么就要等待，就要排隊(duì)。另一方面，服

15、務(wù)臺也時而空閑，時而忙碌。排隊(duì)論的主要內(nèi)容之一，就是研究等待時間、排隊(duì)長度等的概率分布。根據(jù)服務(wù)臺是一臺或是多臺的情況，排隊(duì)問題又分為單線或多線的排隊(duì)問題。1.2.1物流中的運(yùn)籌學(xué)問題 排隊(duì)論在物流過程中具有廣泛地應(yīng)用，例如機(jī)場跑道設(shè)計(jì)和機(jī)場設(shè)施數(shù)量問題，如何才能既保證飛機(jī)起降的使用要求，又不浪費(fèi)機(jī)場資源； 又如碼頭的泊位設(shè)計(jì)和裝卸設(shè)備的購置問題，如何達(dá)到既能滿足船舶到港的裝卸要求，而又不浪費(fèi)港口資源； 再如倉庫保管員的聘用數(shù)量問題，售票處的窗口的開設(shè)數(shù)量問題，物流機(jī)械維修人員的聘用數(shù)量問題，如何達(dá)到既能保證倉儲保管業(yè)務(wù)、售票業(yè)務(wù)和物流機(jī)械的正常運(yùn)轉(zhuǎn)，又不造成人力浪費(fèi)，這些問題都可以運(yùn)用排隊(duì)論

16、方法加以解決。1.2.1物流中的運(yùn)籌學(xué)問題（3）存儲論 存儲論又稱庫存論。在經(jīng)營管理中，為了促進(jìn)系統(tǒng)的有效運(yùn)轉(zhuǎn)，往往需要對零部件、器材以及其他物資保障條件維持合理的儲備。存儲論就是研究在什么時間、以多人數(shù)量、從什么來源保證這些儲備，并使得為保存合理的庫存量和補(bǔ)充采購所需的總費(fèi)用最小的理論。1.2.1物流中的運(yùn)籌學(xué)問題 存儲論是研究物資儲備的控制策略的理論。存儲物資是為了協(xié)調(diào)供應(yīng)(生產(chǎn))和需求(消費(fèi))之間關(guān)系的一種措施。例如工廠商店就必須考慮原材料和商品的庫存量，庫存太少可能造成停產(chǎn)或脫銷，庫存太多則造成積壓，這些都直接影響企業(yè)的效益，因此庫存管理是現(xiàn)代企業(yè)生產(chǎn)管理中的一個重要環(huán)節(jié)。庫存論的模型

17、與以下幾個要素有關(guān)。需求方式，即庫存物資的輸出方式。補(bǔ)充方式，即物資的輸入方式。有關(guān)生產(chǎn)、庫存、訂貨、缺貨的費(fèi)用。存貯策略，這里可以控制的是輸入方式，控制訂貨時間和訂貨數(shù)量，形成庫存控制的策略。的運(yùn)籌學(xué)問題1.2.1物流中的運(yùn)籌學(xué)問題（4）決策分析理論 現(xiàn)實(shí)世界有限的資源和人們無限的需求這一矛盾導(dǎo)致了競爭，由于競爭才使決策成為必要，是競爭催生了決策理論。戰(zhàn)爭是人類競爭的最激烈的表現(xiàn)形式，因而對于決策的研究也最早、最多地出現(xiàn)于對戰(zhàn)爭活動的研究中，從中國古代的孫子兵法和田忌賽馬的故事中都可以看到我們祖先對決策的研究。1.2.1物流中的運(yùn)籌學(xué)問題 決策所要解決的問題是多種多樣的，在現(xiàn)代物流管理系統(tǒng)中

18、，決策論通過對系統(tǒng)狀態(tài)的性質(zhì)、采取的策略及效果的度量進(jìn)行綜合研究，確定決策準(zhǔn)則，并選擇最優(yōu)的決策方案。1.2.1物流中的運(yùn)籌學(xué)問題 （5）對策論 對策論是一種定量分析方法，可以幫助我們尋找最佳的競爭策略，以便戰(zhàn)勝對手或者減少損失。 例如在一個城市內(nèi)有兩個配送中心經(jīng)營相同的業(yè)務(wù)，為了爭奪市場份額，雙方都有多個策略可供選擇，可以運(yùn)用對策論進(jìn)行分析，尋找最佳策略。 例如，面對一次次的鐵路大提速，公路運(yùn)輸公司要與鐵路系統(tǒng)爭奪客源，有多種策略可供選擇，也可用對策論研究競爭方案等。1.2.1物流中的運(yùn)籌學(xué)問題（6）圖論與網(wǎng)絡(luò)分析 圖論是物流運(yùn)籌學(xué)應(yīng)用十分廣泛的一個分支?，F(xiàn)代物流管理中經(jīng)常碰到運(yùn)輸網(wǎng)絡(luò)的合理

19、布置與選擇、生產(chǎn)一序間的合理銜接搭配問題，各種管道、線路的通過能力以及倉庫、附屬設(shè)施的布局等問題。圖論中把一些研究對象用節(jié)點(diǎn)表示，對象之間的聯(lián)系用連線(邊)表示，點(diǎn)、邊的集合構(gòu)成圖。如果給圖中各邊賦予某些具體的權(quán)數(shù)，并指定了起點(diǎn)和終點(diǎn)，則稱這樣的圖為網(wǎng)絡(luò)圖。圖論與網(wǎng)絡(luò)分析正是通過對圖與網(wǎng)絡(luò)性質(zhì)及優(yōu)化的研究。從而解決設(shè)計(jì)與管理中的時間最少、距離最短、費(fèi)用最省等實(shí)際問題。1.2.1物流中的運(yùn)籌學(xué)問題1.2.2物流運(yùn)籌學(xué)發(fā)展的探索 運(yùn)籌學(xué)作為一門實(shí)踐應(yīng)用的科學(xué)，已被廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、民政事業(yè)、軍事決策等組織，解決山多種因素影響的復(fù)雜大型問題。目前，在物流領(lǐng)域中的應(yīng)用也相當(dāng)普遍，

20、并且解決了許多實(shí)際問題，取得了很好的效果。 改革開放以來，運(yùn)籌學(xué)的應(yīng)用更為普遍，特別是在流通領(lǐng)域應(yīng)用更為廣泛。例如運(yùn)用線性規(guī)劃進(jìn)行全國范圍的糧食、鋼材、水泥的合理調(diào)運(yùn)等；許多企業(yè)的作業(yè)調(diào)配、工序安排、場地選擇等，也使用了運(yùn)籌學(xué)方法，取得了顯著的效果。與此同時，還創(chuàng)造了簡單易行的“圖上作業(yè)法”和“表上作業(yè)法”。1.2.2物流運(yùn)籌學(xué)發(fā)展的探索 從物流和運(yùn)籌學(xué)的關(guān)系不難看出，兩者將不斷滲透和交叉，物流系統(tǒng)中運(yùn)籌的作用也將不斷凸顯，物流實(shí)現(xiàn)“5S”和克服物流系統(tǒng)中的制約關(guān)系(如高質(zhì)量服務(wù)與成本的制約等)就必須考慮如何才能更有效地提供高效高質(zhì)量節(jié)約的物流服務(wù)，就必須要運(yùn)用到運(yùn)籌學(xué)來解決原材料到半成品到成

21、品到顧客的過程中所涉及的運(yùn)籌方面(規(guī)劃問題、排隊(duì)問題、庫存、質(zhì)量控制、對策問題等)。 隨著物流運(yùn)籌的迅速發(fā)展，物流科學(xué)和運(yùn)籌學(xué)將會相得益彰，更好的應(yīng)用于社會發(fā)展過程中。本章小結(jié) 本章首先介紹了運(yùn)籌學(xué)的概念和特點(diǎn)，然后介紹了運(yùn)籌學(xué)的發(fā)展簡史，物流與運(yùn)籌學(xué)的關(guān)系以及物流在運(yùn)籌學(xué)中的問題，具體包括規(guī)劃論、排隊(duì)論、存儲論、決策論、對策論和質(zhì)量控制理論在物流中的應(yīng)用做了分析介紹，最后在對物流運(yùn)籌學(xué)發(fā)展的探索做了展望。習(xí)題1.什么是運(yùn)籌學(xué)?它的特點(diǎn)有哪些？2.物流和運(yùn)籌學(xué)有怎樣關(guān)系？3.物流中的運(yùn)籌學(xué)問題有哪些？4.物流運(yùn)籌學(xué)會有怎樣的發(fā)展前景？舉例說明。5.舉例說明運(yùn)籌學(xué)的原理和思想在物流系統(tǒng)中的應(yīng)用。

22、第二章 線性規(guī)劃第一節(jié) 線性規(guī)劃問題概述線性規(guī)劃（Linear Programming）主要研究在既定的目標(biāo)和條件下，如何最大限度地發(fā)揮有限資源的作用，從而完成最多最大的任務(wù)。簡單地講，也就是資源的最優(yōu)利用問題。傅里葉(Fourier)于1823年、普桑(Poussin)于1911年就曾提出過一些與線性規(guī)劃有關(guān)的問題，但未引起重視。1939年，蘇聯(lián)學(xué)者康脫洛維奇(L. V. Kantorovich)發(fā)表了重要著作生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法，針對生產(chǎn)的組織、分配、上料等一系列問題，提出了一種極值問題。這種問題不能用數(shù)學(xué)分析的方法解決，是一類新問題，他還提出了解乘數(shù)法的新方法，可惜這個工作在當(dāng)時未

23、引起足夠的重視。直到五十年代末期，蘇聯(lián)才重視了他的工作。1941年，希區(qū)柯克(Hitchcock)提出了運(yùn)輸問題，1945年，斯蒂格勒(Stigler)提出了營養(yǎng)問題，1947年，庫普曼斯(Koopmans)提出了經(jīng)濟(jì)問題，這些都是關(guān)于線性規(guī)劃的問題。真正奠定線性規(guī)劃完整的概念、理論和算法的，應(yīng)當(dāng)歸功于丹捷格(G. B. Dantzig)。1947年，丹捷格提出了在一組線性方程或線性不等式約束下，求某一線性形式極小值問題的數(shù)學(xué)模型，1947年夏天，丹捷格又提出了求解一般線性規(guī)劃問題的單純形法，并且電子計(jì)算機(jī)為這個算法提供了可能，終于使線性規(guī)劃建立起來了。一、線性規(guī)劃問題的提出提高經(jīng)濟(jì)效益，有兩

24、種途徑：一是進(jìn)行技術(shù)創(chuàng)新；二是提高管理水平，改進(jìn)生產(chǎn)組織與計(jì)劃，最合理地安排各類生產(chǎn)要素?！纠?】某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，如表2-1所示。表2-1 生產(chǎn)資源 產(chǎn)品 每件產(chǎn)品所需資源資源資源限量設(shè)備2410臺時原材料A5015kg原材料B0510kg該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可獲利4元，問應(yīng)如何安排計(jì)劃使該工廠獲利最多？ 解：該問題可用以下數(shù)學(xué)模型來描述，設(shè)x1、x2分別表示在計(jì)劃期內(nèi)產(chǎn)品、的產(chǎn)量。2x1+4x2105x1155x210若用z表示利潤，z = 2x1+4x2。綜上，該計(jì)劃問題可用數(shù)學(xué)模型表示

25、為：目標(biāo)函數(shù) max z = 2x1+4x2滿足約束條件 2x1+4x210 5x1 15 5x210 x1、x20【例2】假定一個成年人每天需要從食物中獲取3000cal熱量，55g蛋白質(zhì)和800mg鈣。如果市場上只有4種食品可選，它們每千克所含熱量、營養(yǎng)構(gòu)成以及市場價格見表2-2。問如何選擇各種食品，才能滿足成年人每天的營養(yǎng)需要，同時使購買食品的費(fèi)用最??？表2-2 食品所含熱量、營養(yǎng)構(gòu)成以及市場價格序號食品名稱熱量/cal蛋白質(zhì)/g鈣/mg價格/元1豬肉100050400102雞蛋8006020063大米9002030034白菜200105002 解：該問題是如何選擇各種食品的數(shù)量，以期在

26、滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小。令xj（j=1, 2, 3, 4）表示第j種食品每天的購買量；然后根據(jù)每天從食物中獲得營養(yǎng)的要求，豬肉中含有熱量1000，現(xiàn)購買量為x1，故從豬肉中獲得的熱量為1000 x1；類似地，從雞蛋、大米和白菜中獲得的熱量分別為800 x2、900 x3和200 x4，這樣從食品中獲得的總熱量為1000 x1+800 x2+900 x3+200 x4，它應(yīng)超過成人一天中所需的熱量要求3000，于是，得到約束1000 x1+800 x2+900 x3+200 x43000。 同理，蛋白質(zhì)和鈣要求的約束：50 x1+60 x2+20 x3+10 x455400 x1+

27、200 x2+300 x3+500 x4800 再者，還有一些變量本身的約束，xj（j=1, 2, 3, 4）只能取非負(fù)值，故有下列非負(fù)約束：x10，x20，x30，x40最后確定購買這些食品的費(fèi)用，若用z表示購買食品的總費(fèi)用，則有：z = 10 x1+6x2+3x3+2x4 根據(jù)問題的要求，旨在總的費(fèi)用最小，這是該問題的目標(biāo)，可以表示為：min z = 10 x1+6x2+3x3+2x4綜上所述，得數(shù)學(xué)模型為：min z = 10 x1+6x2+3x3+2x41000 x1+800 x2+900 x3+200 x4300050 x1+60 x2+20 x3+10 x455400 x1+200

28、 x2+300 x3+500 x4800 xj0 （j=1, 2, 3, 4）二、 線性規(guī)劃模型線性規(guī)劃問題具有以下3個特征。（1）都有一組決策變量，x=(x1，x2，xn)，每一組決策變量代表一個行動方案，且決策變量都是非負(fù)的。（2）都有一個目標(biāo)函數(shù)，且是決策變量的線性函數(shù)，根據(jù)要求可以是求max或min。（3）都有一組約束條件，且是決策變量的線性等式或不等式。一般來說，線性規(guī)劃問題可以用數(shù)學(xué)語言描述為：max(min)z = c1x1+c2x2+cnxna11x1+a12x2+a1nxn(=, )b1a21x1+a22x2+a2nxn(=, )b2 am1x1+am2x2+amnxn(=,

29、 )bm x1，xn0 也可以縮寫為：max(min)z= ，j=(1, 2, , m) j=(1, 2, , n)或者用矩陣形式表示：max(min)z = CXAX (=, ) bX 0式中 C=(c1, c2, , cn)價值系數(shù)； 決策變量； 系數(shù)矩陣； 常數(shù)項(xiàng) 三、 線性規(guī)劃模型的標(biāo)準(zhǔn)型由前節(jié)可知，線性規(guī)劃問題有各種不同的形式。目標(biāo)函數(shù)有的要求max，有的要求min；約束條件可以是“”，也可以是“”形式的不等式，還可以是等式。決策變量一般是非負(fù)約束，但也允許在（-，）范圍內(nèi)取值，即無約束。將這種多種形式的數(shù)學(xué)模型統(tǒng)一變換為標(biāo)準(zhǔn)型。這里規(guī)定的標(biāo)準(zhǔn)型為：在標(biāo)準(zhǔn)型中規(guī)定各約束條件的右端項(xiàng)b

30、i0，否則等式兩端乘以“-1”。用矩陣描述時為： max z = CX （2-3） AX = b X 0 實(shí)際碰到各種線性規(guī)劃問題的數(shù)學(xué)模型都應(yīng)變換為標(biāo)準(zhǔn)型后求解。（一）目標(biāo)函數(shù)是求最小值若要求目標(biāo)函數(shù)實(shí)現(xiàn)最小化，即min z = CX，這時只需將目標(biāo)函數(shù)最小化變換為求目標(biāo)函數(shù)最大化，即令z = -z，于是得到max z= -CX。這就同標(biāo)準(zhǔn)型的目標(biāo)函數(shù)的形式一致了，而且新問題與原問題具有同樣的可行域和最優(yōu)解（若存在），只是最優(yōu)值（若存在）相差一個符號而已。（二）約束方程為不等式這里有兩種情況：一種是約束方程為不等式，則可在不等式的左端加入非負(fù)松弛變量，把原不等式變?yōu)榈仁剑瑫r規(guī)定目標(biāo)函數(shù)中相

31、應(yīng)的價值系數(shù)為零，不改變原問題的最優(yōu)解；另一種是約束方程為不等式，則可在不等式的左端減去一個非負(fù)剩余變量（也可稱松弛變量），把不等式約束條件變?yōu)榈仁郊s束條件，同時規(guī)定目標(biāo)函數(shù)中相應(yīng)的價值系數(shù)為零。（三）不是非負(fù)的變量如果某個變量xj0，則令：可得如果某個變量xk 的符號不受限制，則稱xk為自由變量，或者說無約束，則可以引進(jìn)兩個非負(fù)變量xk 和xk，令：【例3】將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。解：例1的數(shù)學(xué)模型為：在各不等式中分別加上一個松弛變量x3，x4，x5，使不等式變?yōu)榈仁?。這時得到標(biāo)準(zhǔn)型：所加松弛變量x3、x4、x5表示沒有被利用的資源。當(dāng)然也沒有利潤，在目標(biāo)函數(shù)中其系數(shù)為零，即c3，c4，

32、c5=0?！纠?】將下面線性規(guī)劃問題化成標(biāo)準(zhǔn)型。 解：該線性規(guī)劃共有三處不符合標(biāo)準(zhǔn)型要求：目標(biāo)函數(shù)z求最小值；第一、二個約束條件為不等式；決策變量x10；x3無約束。為此，通過以下步驟將該模型標(biāo)準(zhǔn)化。（1）決策變量 。（2）第一個約束引入松弛變量x4，第二個約束引入剩余變量x5。（3）目標(biāo)函數(shù)min變?yōu)閙ax。由于在第三個約束中資源量為-6，也可以從實(shí)際意義考慮將第三個等式約束兩邊同乘以-1，按照上述步驟，該問題的標(biāo)準(zhǔn)形式為：注意求解所得最優(yōu)值的相反數(shù)才是原問題的最優(yōu)值。第二節(jié) 線性規(guī)劃問題解法一、 線性規(guī)劃問題解的類型設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為：max z = CX (2-4) AX = b (2

33、-5) X 0 (2-6)其中A是mn矩陣，mn且秩r (A) = m，即A中至少有一個mm滿秩子矩陣。 現(xiàn)說明線性規(guī)劃標(biāo)準(zhǔn)形式下各種解的含義?？尚薪猓簼M足約束條件(2-5)和(2-6)的X = (x1, x2, , xn)T，稱為線性規(guī)劃問題的可行解?？尚杏颍喝w可行解的集合稱為線性規(guī)劃的可行域，一般記作D=X|AX=b, X0。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解X* = (x1, x2, , xn)T稱為線性規(guī)劃的最優(yōu)解。最優(yōu)值：最優(yōu)解的目標(biāo)函數(shù)值稱為線性規(guī)劃的最優(yōu)值?；喝鬉中mm子矩陣B滿足r(B) = m，則稱B是線性規(guī)劃問題的一個基。也就是說，矩陣B是由A的m個線性無

34、關(guān)列向量所構(gòu)成，不妨設(shè)為：稱Pj (j=1, 2, , m)為基向量。基變量、非基變量：與基向量Pj (j=1, 2, , m)相對應(yīng)的變量xj (j=1, 2, , m)為基變量，其他決策變量稱為非基變量。基本解：記基變量為XB=(x1, x2, , xm)T，非基變量為XN=(xm+1, xm+2, , xn)T，稱滿足方程組BXB=b且XN=0的解為基本解。基本可行解：若基本解XB=B-1b0，則稱該解為基本可行解，也稱為基可行解，B為可行基。線性規(guī)劃解之間的關(guān)系如圖2-1所示。圖2-1 解之間的關(guān)系非可行解基本解可行解基本可行解【例5】某線性規(guī)劃的約束條件如下，求其基本解和基本可行解。

35、x1+3x2+x3=54x1-2x2+x4=2 x1, ,x40解：線性規(guī)劃的系數(shù)矩陣： A的子矩陣：非奇異，因而B1是一個基，其中：x1，x2為基變量，x3，x4為非基變量。令x3 = x4 = 0，則x1 =8/7 , x2 = 9/7X(1) = (8/7, 9/7, 0, 0)T是基本解，因?yàn)闈M足非負(fù)條件，因此還是基本可行解。同理，A的子矩陣：非奇異，因而B2是一個基，其中：x2，x3為基變量，x1，x4為非基變量。令x1 = x4 = 0，則x2 = -1，x3 = 8得到一個關(guān)于基B2的基本解X(2) = (0, -1, 8, 0)T，但不滿足非負(fù)條件，因此不是基本可行解。其余基本

36、解和基本可行解讀者可按照以上方法求出。二、 線性規(guī)劃的圖解法對于只有兩個變量的線性規(guī)劃問題，可以直接使用圖解法求解。圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理?，F(xiàn)對下例使用圖解法。max z = 2x1 + 3x2x1 + 2x2 8 4x1 16 （2-7） 4x2 12x1，x2 0在以x1、x2為坐標(biāo)軸的直角坐標(biāo)系中，非負(fù)條件x1，x20是指第一象限。上例的每一個約束條件都代表一個半平面。如約束條件x1+2x28是代表以直線x1+2x2=8為邊界的左下方的半平面，若同時滿足x1，x20，x1+2x28，4x116和4x212的約束條件的點(diǎn)，必然落在由這三個半平面交成的區(qū)域內(nèi)。由

37、上例的所有約束條件為半平面交成的區(qū)域見圖2.2中的陰影部分。陰影區(qū)域中的每一個點(diǎn)（包括邊界點(diǎn)）都是這個線性規(guī)劃問題的解（稱可行解），因而此區(qū)域是上例的線性規(guī)劃問題的解集合，稱它為可行域。圖2-2 線性規(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值由小變大時，直線x2 = -(2/3)x1 + z/3沿其法線方向向右上方移動。當(dāng)移動到Q2點(diǎn)時，使z值在可行域邊界上實(shí)現(xiàn)最大化（見圖2.3），這就得到了上例的最優(yōu)解Q2，Q2點(diǎn)

38、的坐標(biāo)為（4, 2）。于是可計(jì)算出z = 14。圖2-3 圖解法上例中求解得到問題的最優(yōu)解是唯一的，但對一般線性規(guī)劃問題，求解結(jié)果還可能出現(xiàn)以下幾種情況： （一）無窮多最優(yōu)解（多重解）若將上例中的目標(biāo)函數(shù)變?yōu)榍髆ax z = 2x1 + 4x2，則表示目標(biāo)函數(shù)中以參數(shù)z的這族平行直線與約束條件x1+2x28的邊界線平行。當(dāng)z值由小變大時，將與線段Q2Q3重合（見圖2-4）。線段Q2Q3上任意一點(diǎn)都使z取得相同的最大值，這個線性規(guī)劃問題有無窮多最優(yōu)解（多重解）。圖2-4 無窮多最優(yōu)解示圖（二）無界解對下述線性規(guī)劃問題max z = x1 + x2-2x1+x24 x1-x22 x1，x20用圖解

39、法求解結(jié)果見圖2-5。從圖中可以看到，該問題可行域無界，目標(biāo)函數(shù)值可以增大到無窮大。稱這種情況為無界解或無最優(yōu)解。 圖2-5 無界解示圖-2-22240 x1x2（三）無可行解。如果在方程2-7的數(shù)學(xué)模型中增加一個約束條件-2x1+x24，該問題的可行域?yàn)榭占?，即無可行解，也不存在最優(yōu)解。當(dāng)求解結(jié)果出現(xiàn)(2)、(3)兩種情況時，一般說明線性規(guī)劃問題的數(shù)學(xué)模型有錯誤。前者缺乏必要的約束條件，后者是有矛盾的約束條件，建模時應(yīng)注意。從圖解法中直觀地見到，當(dāng)線性規(guī)劃問題的可行域非空時，它是有界或無界凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定在可行域的某個頂點(diǎn)得到；若在兩個頂點(diǎn)同時得到最優(yōu)解，則它們連線

40、上的任意一點(diǎn)都是最優(yōu)解，即有無窮多最優(yōu)解。圖解法雖然直觀、簡便，但當(dāng)變量數(shù)多于三個以上時，它就無能為力了。所以在下一小節(jié)中要介紹一種代數(shù)法單純形法。三、 線性規(guī)劃的單純形法 （一）單純形法的基本思想 單純形法的基本思想是：從線性規(guī)劃的標(biāo)準(zhǔn)型出發(fā)，從可行域中某一個基本可行解（一個頂點(diǎn)）開始，然后按照一定的方法迭代到另一個基本可行解（頂點(diǎn)），并且使目標(biāo)函數(shù)達(dá)到最大值時，就得到了最優(yōu)解。【例6】用單純形法求解以下線性規(guī)劃問題。max z =2x1+4x2 x1 2 2x28 3x1+2x212 x1, x20 解：1.先轉(zhuǎn)化為標(biāo)準(zhǔn)型。引入松弛變量x3，x4，x5，將上述問題轉(zhuǎn)化為標(biāo)準(zhǔn)型如下：max

41、z = 2x1+4x2 x1 + x3 = 2 (2-8) 2x2 + x4 = 8 3x1 + 2x2 + x5 = 12 x1, , x5 02.找一個初始基本可行解X(0)。上述標(biāo)準(zhǔn)型的約束方程組的系數(shù)矩陣如下：很顯然，含有3個線性無關(guān)的單位列向量所組成的子矩陣是非奇異的：B0是線性規(guī)劃問題的一個基。而且由于約束方程組的右端常數(shù)是非負(fù)的，所以B0顯然是一個可行基，x3，x4，x5是關(guān)于可行基B0的基變量，x1，x2是非基變量。為了求初始基本可行解，只需要在約束方程組中令非基變量x1 = x2 = 0，可得x3 = 2，x4 = 8，x5 = 12。于是得到初始基本可行解：X(0) = (

42、0, 0, 2, 8, 12)T 其對應(yīng)的目標(biāo)函數(shù)值：z0 = 20+40 =03.檢驗(yàn)X(0)是否是最優(yōu)解。由目標(biāo)函數(shù)的表達(dá)式：z = 2x1+4x2可知，非基變量x1，x2前面的系數(shù)都為正數(shù)，也就是說如果把非基變量x1，x2中的任意一個變?yōu)榛兞?，而且滿足非負(fù)條件，都可以使目標(biāo)函數(shù)值增大?？梢姡琗(0)不是最優(yōu)解。4.第一次迭代。為使目標(biāo)函數(shù)值較快地增加，一般選擇正系數(shù)最大的非基變量作為入基變量。在這里，把x2作為入基變量，讓其數(shù)值盡可能地增大，x1仍是非基變量。從原來的基變量x3，x4，x5中選擇一個作為非基變量。但是x2的值不能無限制地增大，它要受到約束方程組的限制，由線性規(guī)劃問題的約

43、束方程組得：x3 = 2-x1 x4 = 8-2x2 x5 = 12-3x1-2x2 將x1 = 0，x2 = 代入上面方程組，為了使目標(biāo)函數(shù)值盡可能地得到改善，希望盡可能地增大，但必須保證x3，x4，x5保持非負(fù)，從而的值要滿足：x3 = 2x4 = 8-2x2 0 x5 = 12-2x2 0即：x2 = = min8/2, 12/2= 4 相應(yīng)地有：x3 = 2x4 = 0 x5 = 4 這表明，應(yīng)該確定x4為出基變量。于是新的基變量為x2，x3，x5，非基變量為x1，x4。令非基變量為零，代入式(2-8)的約束方程組可得第一次迭代后的基本可行解X(1) = (0, 4, 2, 0, 4)

44、T其對應(yīng)的目標(biāo)函數(shù)值：z1 = 20+44 = 16 z1 z0，這表明第二種方案比第一種方案有明顯改善。5.檢驗(yàn)X(1)是否是最優(yōu)解。為了回答這個問題，將式(2-8)的約束方程組改寫為用非基變量x1，x4表示基變量x2，x3，x5的表達(dá)式。用高斯消去法得到：x3 = 2 - x1x2 = 4 -x4x5 = 4 3x1 +x4代入目標(biāo)函數(shù)，得到用非基變量x1，x4表示的目標(biāo)函數(shù)：z = 16 + 2x1 - 2x4非基變量x1前的系數(shù)是正數(shù)，也就說如果把非基變量x1轉(zhuǎn)換成為基變量，而且取正值，目標(biāo)函數(shù)值還會進(jìn)一步增大。因此，X(1)不是最優(yōu)解。6.第二次迭代。同樣可以根據(jù)第一次迭代的方法，選

45、取非基變量x1，使它變?yōu)槿牖兞?，并盡可能使它取最大的值，x4仍是非基變量。從原來的基變量x3，x2，x5中選擇一個轉(zhuǎn)化成為非基變量。但是x1的值不能無限制地增大，它要受到約束方程組的限制，由線性規(guī)劃問題的約束方程組得：x3 = 2 - x1x2 = 4 -x4x5 = 4 3x1 +x4將x1 = ，x4 = 0代入上面方程組，為使目標(biāo)函數(shù)值盡可能地得到改善，希望盡可能地增大，但必須保證x3，x2，x5保持非負(fù)，從而的值要滿足：x3 = 2-x1 0 x2 = 4 0 x5 = 4-3x1 0即： x1 = = min2/1, 4/3=4/3相應(yīng)地有：x3 = 2/3x2 = 4 x5 =

46、0這表明，應(yīng)該確定x5為出基變量。于是新的基變量為x1，x2，x3，非基變量為x4，x5。令非基變量為零，代入式(2-8)的約束方程組可得第二次迭代后的基本可行解：X(2) = (4/3, 4, 2/3, 0, 0)T其對應(yīng)的目標(biāo)函數(shù)值：z2 = 24/3 + 44 = 56/3z2z1，這表明，第三種方案比第二種方案有改善。7.檢驗(yàn)X(2)是否是最優(yōu)解。同樣可以用檢驗(yàn)X(1)的方法來檢驗(yàn)X(2)，將式(2-8)的約束方程組改寫為用非基變量x4，x5表示基變量x1，x2，x3的表達(dá)式。用高斯消去法得到：代入目標(biāo)函數(shù)，得到用非基變量x4，x5表示的目標(biāo)函數(shù)：這時，目標(biāo)函數(shù)中非基變量x4，x5前面

47、的系數(shù)都已小于零，也就是說目標(biāo)函數(shù)值不能進(jìn)一步增大了，目標(biāo)函數(shù)已取得最大值，所以X(2)就是最優(yōu)解。通過以上例子，可以歸納出單純形法的計(jì)算步驟如下：1.建立實(shí)際問題的線性規(guī)劃數(shù)學(xué)模型。2.把一般形式的線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)型。3.找出初始基本可行解。4.檢驗(yàn)初始基本可行解是否是最優(yōu)解。5.如果不是，進(jìn)行迭代，求出新的基本可行解。6.重復(fù)步驟（4）和（5），直到求出最優(yōu)解為止，或者判定無最優(yōu)解。（二）一般線性規(guī)劃問題的求解從以上內(nèi)容可以看出，用單純形法求解線性規(guī)劃問題，關(guān)鍵是要找出初始基本可行解。有些標(biāo)準(zhǔn)型的線性規(guī)劃問題的初始基本可行解比較容易得到，有些比較難?？砂阉鼈兎殖蓛煞N類型來分別討論。給

48、出線性規(guī)劃問題的標(biāo)準(zhǔn)型：第一種情況：設(shè)式(2-9)的系數(shù)矩陣A中含有m個線性無關(guān)的單位列向量，且bi 0（i =1, 2, , m）。為了不失一般性，假定m個線性無關(guān)的單位列向量在A中的前m個列，構(gòu)成m階單位矩陣。也就是說，可以把式(2-9)表示成：max z = c1x1 + c2x2 + + cnxnx1 + a1,m+1xm+1 + a1,m+2xm+2 + + a1nxn = b1 x2 + a2,m+1xm+1 + a2,m+2xm+2 + + a2nxn = b2 (2-10) xm + am,m+1xm+1 + am,m+2xm+2 + + amnxn = bmx1, x2, ,

49、 xn 0其中，bi0 (i=1, 2, , m)第二種情況：如果系數(shù)矩陣A中不存在單位矩陣，則可以采用人工變量法進(jìn)行處理，把它轉(zhuǎn)化成為第一種情況。人工變量法會在后面介紹。1.初始基本可行解的確定由于單位矩陣B0是問題式(2-10)的一個可行基，x1，x2，xm是關(guān)于可行基B0的基變量，xm+1，xm+2，xn是關(guān)于可行基B0的非基變量。因此，相應(yīng)地可得到一個基本可行解：X(0) = (b1, b2, , bm, 0, , 0)T即為所要的初始基本可行解。也就是說，想要找出線性規(guī)劃問題的初始基本可行解，可以從系數(shù)矩陣?yán)飳ふ襪個線性無關(guān)的單位列向量，但單位矩陣并不是顯然存在的，也可分成兩種情況來

50、分析。 第一種情況： 線性規(guī)劃問題的系數(shù)矩陣A中本來就存在m個線性無關(guān)的單位列向量，則以此單位矩陣為初始基矩陣即可?！纠?】給出線性規(guī)劃問題：max z = 3x1 + 4x2 + 2x3 - 4x5x1 + 2x2 - 2x3 + 3x5 = 63x2 + x4 - 4x5 = 12 -x2 + 3x3 + 5x5 + x6 = 9x1, , x6 0系數(shù)矩陣： 含有3個線性無關(guān)的單位列向量P1，P4，P6，組成了一個單位矩陣：即為初始基矩陣。關(guān)于基B0的基變量為x1，x4，x6，非基變量為x2，x3，x5，初始基本可行解為：X(0) = (6, 0, 0, 12, 0, 9)T第二種情況：

51、線性規(guī)劃問題的系數(shù)矩陣A中不存在m個線性無關(guān)的單位列向量，但所有約束條件都是“”形式的不等式，可以利用前面所講的轉(zhuǎn)化標(biāo)準(zhǔn)型的方法，在每個約束條件的左端加上一個非負(fù)的松弛變量，松弛變量的系數(shù)列向量所組成的矩陣就是一個單位矩陣，以此單位矩陣為初始基矩陣即可。【例8】給出線性規(guī)劃問題：max z = 2x1+3x2x1 + x2 5x1 + 2x2 6x1 4 x2 2x1,x2 0引入松弛變量x3，x4，x5，x6，將上述線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)型：max z = 2x1 + 3x2x1 + x2 + x3 = 5x1 + 2x2 + x4 = 6x1 + x5 = 4 x2 + x6 = 2x1,

52、 , x6 0初始可行基為P3，P4，P5，P6所組成的單位矩陣，基變量為x3，x4，x5，x6，非基變量為x1，x2，相應(yīng)的初始基本可行解為：X(0) = (0, 0, 5, 6, 4, 2)T線性規(guī)劃問題化為標(biāo)準(zhǔn)型以后，如果系數(shù)矩陣中含有單位矩陣，則該標(biāo)準(zhǔn)型稱為規(guī)范型。2.最優(yōu)性檢驗(yàn)需要一個判別的法則，以便判定初始基本可行解及以后的基本可行解是否是最優(yōu)解，從而決定是否需要繼續(xù)進(jìn)行迭代。為了不失一般性，經(jīng)某一次迭代并經(jīng)過整理重新編號后，約束條件為： 令非基變量xj = 0，得基變量xi =bi (i=1, 2, , m)?？傻没究尚薪猓篨(0) = (b1，b2，bm，0, , 0)T由可

53、得：代入目標(biāo)函數(shù)表達(dá)式中，可得：式(2-12)是用非基變量來表示目標(biāo)函數(shù)的表達(dá)式，其中z0表示基本可行解X(0) = (b1, b2, , bm, 0, , 0)T所對應(yīng)的目標(biāo)函數(shù)值；j稱為非基變量xj的檢驗(yàn)數(shù)，因?yàn)榛兞坎粫?2-12)中出現(xiàn)，所以規(guī)定所有基變量的檢驗(yàn)數(shù)為零。 定理2.1 最優(yōu)性判別定理。若所有非基變量的檢驗(yàn)數(shù)j0（j=m+1, , n），則基本可行解X(0) = (b1，b2，bm，0，0)T為最優(yōu)解。證：因?yàn)閖0，xj0 (j=m+1, ,n)，由式(2-12)知：而基本可行解X對應(yīng)的目標(biāo)函數(shù)值為z0，故X(0)為最優(yōu)解。定理2.2 無有限最優(yōu)解判別定理。若至少存在一個

54、k 0（m+1kn），并且對于所有的i = 1, 2, , m均有aik0，那么該線性規(guī)劃問題沒有有限最優(yōu)解。證：構(gòu)造一個新的可行解X：因?yàn)閎i0，0，aik0，故0（i = 1, 2, , m），由此可見，對任意0，X都是可行解，其對應(yīng)的目標(biāo)函數(shù)值可由式(2-12)求得：z = z0 + k因?yàn)橐阎猭 0，所以當(dāng)+時，目標(biāo)函數(shù)無最大值，也就是說，該線性規(guī)劃問題無有限最優(yōu)解。3.基變換若在最優(yōu)性檢驗(yàn)中，初始基本可行解既不是最優(yōu)解，也不是屬于無有限最優(yōu)解的情況，這時需要找一個新的基本可行解。具體做法是在保證線性無關(guān)的基礎(chǔ)上，用某個非基變量代替原可行解中的某個基變量，得到一個新的可行解，這就是基變

55、換。在這里，關(guān)鍵是如何選擇適當(dāng)?shù)幕兞亢头腔兞恐g的變換，使目標(biāo)函數(shù)值得到改善。如果某個非基變量在迭代后成為基變量，這個變量就稱為入基變量。如果某個基變量在迭代后成為非基變量，這個變量就稱為出基變量。在基變換中首先要確定入基變量，然后再確定出基變量。（1）入基變量的確定。從式(2-12)可以看到，如果某些j0，則xj的增大還可以增大目標(biāo)函數(shù)值，則需要把非基變量xj作為入基變量。那么，如果有兩個及以上j0，那么應(yīng)該選哪個非基變量作為入基變量呢？為了使目標(biāo)函數(shù)值盡可能快地增大，一般選j0中的大者，即：max(j|j0) = k則xk為入基變量。（2）出基變量的確定。假設(shè)迭代以后得到基本可行解，x

56、k是入基變量，基本可行解的n個分量為為了使x1，x2，xm中有一個基變量成為非基變量，取值為零，其余變量仍然保持非負(fù)，故的取值應(yīng)滿足以下法則。出基變量的確定法則：若： 則取xl為出基變量。 以上法則也稱為法則。 （三）單純形表 前面介紹了一般線性規(guī)劃問題的求解方法單純形法，為了便于計(jì)算和檢驗(yàn)，人們設(shè)計(jì)了一種計(jì)算表，稱為單純形表，其功能與增廣矩陣相似。 給出以x1，x2，xm為基變量的規(guī)范型：max z = c1x1 + c2x2 + + cnxnx1 + a1,m+1xm+1 + a1,m+2xm+2 + + a1nxn = b1 x2 + a2,m+1xm+1 + a2,m+2xm+2 +

57、+ a2nxn = b2 (2-13) xm + am,m+1xm+1 + am,m+2xm+2 + +amnxn = bmx1, x2, , xn 0 其中，bi 0 (i = 1, 2, , m)。 從規(guī)范型出發(fā)，可得到初始基本可行基：基本可行解為：X(0) = (b1, b2, , bm, 0, , 0)T為了檢驗(yàn)所得到的基本可行解是不是最優(yōu)解，需要從式(2-11)求出所有非基變量的檢驗(yàn)數(shù)j (j = m+1, , n)，基本可行解的目標(biāo)函數(shù)值是z0 = 將目標(biāo)函數(shù)、約束方程的系數(shù)、目標(biāo)函數(shù)值、檢驗(yàn)數(shù)等列成表，見表2-3。表2-3中，各部分的含義如下： cj行填入式(2-13)目標(biāo)函數(shù)中

58、變量xj的系數(shù)(j = 1, 2, , n)； XB列填入基變量；CB列填入基變量所對應(yīng)的價值系數(shù)；b列填入約束方程組右端的常數(shù)；j行填入所有變量的檢驗(yàn)數(shù)（其中基變量的檢驗(yàn)數(shù)為零），及基本可行解對應(yīng)的目標(biāo)函數(shù)值z0。其中最大的一塊矩形區(qū)域填入約束方程組的系數(shù)矩陣。i列的數(shù)字是在確定入基變量以后，按法則計(jì)算后填入，并利用這一列值來確定出基變量。【例9】給出線性規(guī)劃問題：max z = 2x1 - 2x2 + x3x1 + x2 + x3 48x1 2x2 + x3 12x1 + 2x2 - x3 24x1，x2，x3 0 解：引入松弛變量x4，x5，x6，化為標(biāo)準(zhǔn)型max z = 2x1 - 2

59、x2 + x3x1 + x2 + x3 + x4 = 48x1 2x2 + x3 + x5 = 12x1 + 2x2 x3 + x6 = 24x1, , x6 0根據(jù)標(biāo)準(zhǔn)型建立初始單純形表，見表2-4。 由表2-4可得初始基本可行解：X(0) = (0, 0, 0, 48, 12, 24)T其相對應(yīng)的目標(biāo)函數(shù)值為0。為了檢驗(yàn)X(0)是否為最優(yōu)解，從表中最后一行可以看到有兩個非基變量x1和x3的檢驗(yàn)數(shù)1 = 2和3 = 1均大于零，所以X(0)不是最優(yōu)解。因?yàn)閙ax 1，3 = max2, 1 = 2，所以取x1為入基變量，并把x1所在列稱為“主元列”。利用法則來確定出基變量： 所以取x5為出基

60、變量，并把x5所在的行稱為“主元行”。主元行與主元列交叉的數(shù)字稱為“主元素”，即表中帶有“（）”的數(shù)字。 在表中以主元素為旋轉(zhuǎn)軸心進(jìn)行旋轉(zhuǎn)運(yùn)算，即對增廣矩陣進(jìn)行初等行變換，總能使： 其他數(shù)字也作相應(yīng)變動，并重新計(jì)算檢驗(yàn)數(shù)，得第一次迭代后的單純形表，見表2-5。由表2-5可得：X(1) = (12, 0, 0, 36, 0, 12)T 其相對應(yīng)的目標(biāo)函數(shù)值為24。 由于20，故X(1)還不是最優(yōu)解，以x2為入基變量。 又 = min36/3, -, 12/4=3，故取x6為出基變量。 與第一次迭代方法相同，找到主元行、主元列、主元素以后，進(jìn)行第二次迭代，得到單純形表，見表2-6。 由表2-6可得