00運(yùn)籌學(xué)-緒論

1、主講教師 譚園園,聯(lián)系電話(huà)：15857147552（677552）,E-mail: yytan@mail.zjgsu.edu.cn,清華大學(xué)出版社,《運(yùn)籌學(xué)教程》（第四版）,運(yùn)籌學(xué)教程,胡運(yùn)權(quán) 主編,教材,杜絕遲到、早退、缺課 有事必須請(qǐng)假(要征求學(xué)院同意) 上課不準(zhǔn)打手機(jī)、玩游戲 上課時(shí)間有事情，先舉手示意 上課期間不得有睡覺(jué)等有礙課堂形象的舉止,課 堂 紀(jì) 律,P3，第三段，“Journal o

2、f Operational Research Society” 改為“Journal of the Operational Research Society”P(pán)3 ，第三段，“European Journal of Operations Research” 改為“European Journal of Operational Research”P(pán)50，第18行，“a12y2” 改為 “a21y2”P(pán)252，圖8－

3、41,勘誤表,高祖問(wèn)諸臣：“吾所以有天下者何？項(xiàng)氏之所以失天下者何？”高起、王陵對(duì)曰：“陛下使人攻城略地，因以與之，與天下同其利；項(xiàng)羽不然，有功者害之，賢者疑之，此其所以失天下也?！鄙显唬骸肮湟?，未知其二。夫運(yùn)籌帷幄之中，決勝千里之外，吾不如子房；填國(guó)家，撫百姓，給餉饋，不絕糧道，吾不如蕭何；連百萬(wàn)之眾，戰(zhàn)必勝，攻必取，吾不如韓信。三者皆人杰，吾能用之，此吾所以取天下者也。項(xiàng)羽有一范增而不能用，此所以為我禽也?！?張良(?—前186

4、)，宇子房，西漢杰出的軍事謀略家，與蕭何、韓信同被稱(chēng)為漢初三杰，被封留侯，謚文成侯。,一、“運(yùn)籌”來(lái)歷,【注】,運(yùn)籌帷幄決勝千里一詞被廣泛應(yīng)用到各行各業(yè)中,,,運(yùn)籌帷幄決勝千里 ——讀《在志愿軍司令部的歲月里》,,運(yùn)籌帷幄決勝千里 陳中奪金完美收關(guān),,運(yùn)籌帷幄決勝千里

5、 ——解密蘇寧快速制勝秘訣,運(yùn)籌帷幄決勝千里篇：目標(biāo)管理與戰(zhàn)略規(guī)劃,運(yùn)籌帷幄決勝千里 ——北海市發(fā)揮水庫(kù)防洪作用科學(xué)調(diào)度洪水紀(jì)實(shí),,,,,,,古代中的運(yùn)籌學(xué)思想的應(yīng)用,,“運(yùn)籌”在我國(guó)古代中的運(yùn)用,公元前四世紀(jì)戰(zhàn)國(guó)時(shí)期齊國(guó)的將軍田忌與齊王賽馬的故事。雙方各遣三馬一對(duì)一比賽。孫臏發(fā)現(xiàn)田忌的馬雖然不如齊王的，但相差不多。于是獻(xiàn)策：以下馬對(duì)齊王

6、的上馬，以上馬對(duì)齊王中馬，以中馬對(duì)齊王下馬，結(jié)果田忌以二比一獲勝。,對(duì)策,宋真宗時(shí)（公元1008-1017）宮廷失火，需要重建。丁渭采取了如下方案：先在通向?qū)m殿的大道上就近取土，取土后大道形成深溝, 于是引入汴水, 成為人工小河。由此基建材料可由水路運(yùn)入工地；宮殿修成后，又將基建廢料棄置溝中，重新建成大道。這一方案取土近、棄土近、運(yùn)輸便，是工程的優(yōu)化。,工程,形成階段：現(xiàn)在普遍認(rèn)為，運(yùn)籌學(xué)的活動(dòng)是從二次世界大戰(zhàn)初期的軍事任務(wù)開(kāi)始的。（運(yùn)

7、輸船編隊(duì)、空襲逃避、深水炸彈 轟炸機(jī)編隊(duì)） 發(fā)展階段：1）形成了比較完備的一套理論，如規(guī)劃論、排隊(duì)論、存貯論、決策論等等；2）美國(guó)于1952年成立了運(yùn)籌學(xué)會(huì)，并出版期刊《運(yùn)籌學(xué)》，世界其它國(guó)家也先后創(chuàng)辦了運(yùn)籌學(xué)會(huì)與期刊；3）1957年成立了國(guó)際運(yùn)籌學(xué)協(xié)會(huì)。 大規(guī)模應(yīng)用階段：60年代以后，運(yùn)籌學(xué)進(jìn)入蓬勃發(fā)展，特別是電子計(jì)算機(jī)的發(fā)展更促進(jìn)運(yùn)籌學(xué)的發(fā)展。,Operations Research (Operational R

8、esearch)，簡(jiǎn)稱(chēng)O.R,一、 運(yùn)籌學(xué)的發(fā)展,運(yùn)籌學(xué)的起源,,日本——運(yùn)用學(xué) 港臺(tái)——作業(yè)研究 中國(guó)大陸——運(yùn)籌學(xué)Operational Research原來(lái)名稱(chēng)，意為軍事行動(dòng)研究——?dú)v史淵源,——《大英百科全書(shū)》,“運(yùn)籌學(xué)”是一門(mén)應(yīng)用于管理有組織系統(tǒng)的科學(xué),——《中國(guó)百科全書(shū)》,“運(yùn)籌學(xué)”是運(yùn)用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國(guó)防等部門(mén)在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財(cái)力等資源，使實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)，它

9、可以用來(lái)預(yù)測(cè)發(fā)展趨勢(shì)，制定行動(dòng)規(guī)劃或優(yōu)選方案。,“運(yùn)籌學(xué)”主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能運(yùn)用數(shù)量表達(dá)有關(guān)運(yùn)用、籌劃與管理方面的問(wèn)題，它根據(jù)問(wèn)題的要求，通過(guò)數(shù)學(xué)分析與運(yùn)算，作出綜合性的合理安排，以達(dá)到較經(jīng)濟(jì)有效地使用人力物力。,——《詞?！罚?979版）,“運(yùn)籌學(xué)”應(yīng)用分析、實(shí)驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)的人、物、財(cái)?shù)扔邢拶Y源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。,——《中國(guó)企業(yè)管理百科全書(shū)》(1979版）,運(yùn)

10、籌學(xué)的定義,運(yùn)籌學(xué)的定義,,,,,現(xiàn)代運(yùn)籌學(xué)在中國(guó)的興起,20世紀(jì)50年代中期，運(yùn)籌學(xué)作為一門(mén)嶄新的學(xué)科剛剛起步發(fā)展，錢(qián)學(xué)森和許國(guó)志就敏銳地意識(shí)到了它的重要意義和廣泛的應(yīng)用前景，首先將這一新學(xué)科引人中國(guó)1956年春，許國(guó)志負(fù)責(zé)起草了中國(guó)第一個(gè)科技規(guī)劃“中國(guó)十二年科技規(guī)劃”中有關(guān)運(yùn)籌學(xué)的發(fā)展規(guī)劃。中國(guó)第一個(gè)運(yùn)籌學(xué)小組在1956年于中國(guó)科學(xué)院力學(xué)研究所成立，他們兩人是第一個(gè)運(yùn)籌學(xué)小組的領(lǐng)導(dǎo)者 錢(qián)學(xué)森先生在MIT取得碩士學(xué)位，在加州理

11、工大學(xué)（California Institute of Technology）取得博士學(xué)位后成為該校的第一位Goddard講座教授。許國(guó)志先生在堪薩斯大學(xué)取得博士學(xué)位后，在馬里蘭大學(xué)流體力學(xué)和應(yīng)用數(shù)學(xué)研究所當(dāng)研究員。 1959年，第二個(gè)運(yùn)籌學(xué)部門(mén)在中國(guó)科學(xué)院數(shù)學(xué)研究所成立，這是大躍進(jìn)中數(shù)學(xué)家們投身于國(guó)家建設(shè)的一個(gè)產(chǎn)物。力學(xué)所小組與數(shù)學(xué)所的小組于1960年合并成為數(shù)學(xué)研究所的一個(gè)研究室，當(dāng)時(shí)的主要研究方向?yàn)榕抨?duì)論、非線(xiàn)性規(guī)劃和圖論

12、，還有人專(zhuān)門(mén)研究運(yùn)輸理論、動(dòng)態(tài)規(guī)劃和經(jīng)濟(jì)分析（例如投入產(chǎn)出方法）。 華羅庚早先主要從事數(shù)論研究，已是世界數(shù)論界的領(lǐng)袖數(shù)學(xué)家之一。他也為運(yùn)籌學(xué)的研究做出了自己的貢獻(xiàn)。 中國(guó)運(yùn)籌學(xué)會(huì)于文化大革命后的1980年成立，當(dāng)時(shí)作為中國(guó)數(shù)學(xué)會(huì)的一個(gè)分會(huì)。第一屆全國(guó)大會(huì)在山東省濟(jì)南召開(kāi)，華羅庚教授當(dāng)然地被選為第一屆理事長(zhǎng)，副理事長(zhǎng)有許國(guó)志先生。,現(xiàn)代運(yùn)籌學(xué)在我國(guó)的應(yīng)用 ——糧食產(chǎn)量預(yù)測(cè),中科院陳錫康

13、教授提出了系統(tǒng)綜合因素方法預(yù)測(cè)糧食產(chǎn)量。關(guān)鍵技術(shù)包括投入占用產(chǎn)出分析、考慮邊際收益率遞減的非線(xiàn)性預(yù)測(cè)方程，以及最小絕對(duì)和方法。自1980年始，在每年的四月底成功地預(yù)測(cè)中國(guó)全年的糧食產(chǎn)量，五月初報(bào)送給中國(guó)政府主要領(lǐng)導(dǎo)以及相關(guān)的政府職能部門(mén)。 三個(gè)突出的特點(diǎn)：預(yù)測(cè)提前期在半年以上（一般預(yù)測(cè)方法提前期一般是2個(gè)月）；平均預(yù)測(cè)誤差為1.6%（一般預(yù)測(cè)方法的平均預(yù)測(cè)誤差為5-10%）；預(yù)報(bào)糧食產(chǎn)量豐、平、欠方向正確。1999年陳錫康研究員等

14、在北京召開(kāi)的第十五屆IFORS大會(huì)上獲得一等獎(jiǎng)。,現(xiàn)代運(yùn)籌學(xué)在我國(guó)的應(yīng)用 ——金融管理與經(jīng)濟(jì)發(fā)展方面的運(yùn)籌學(xué)應(yīng)用,將優(yōu)化及決策分析方法，應(yīng)用于金融風(fēng)險(xiǎn)控制與管理、資產(chǎn)評(píng)估與定價(jià)分析模型等；例如陜西省運(yùn)籌學(xué)會(huì)近年的一些運(yùn)籌學(xué)應(yīng)用:證券投資： 滬深股市股指波動(dòng)的交互影響效應(yīng)分析 深圳股市內(nèi)幕交易（例資產(chǎn)重組）的實(shí)證分析經(jīng)濟(jì)發(fā)展（預(yù)測(cè)、評(píng)價(jià)、優(yōu)化）： 陜北果業(yè)發(fā)展決策的優(yōu)化分析 系統(tǒng)結(jié)構(gòu)模型在陜北果業(yè)開(kāi)發(fā)中的應(yīng)用

15、 陜北水果生產(chǎn)基地戰(zhàn)略方針多層次分析決策模型 陜西省經(jīng)濟(jì)、資源、環(huán)境協(xié)調(diào)發(fā)展的相對(duì)有效性評(píng)價(jià) 陜西工業(yè)可持續(xù)發(fā)展的評(píng)價(jià)及對(duì)策,還有如在交通、煉鋼、育種等方面的應(yīng)用,現(xiàn)代運(yùn)籌學(xué)在我國(guó)的應(yīng)用 ——現(xiàn)代物流與供應(yīng)鏈管理,供應(yīng)鏈上庫(kù)存協(xié)調(diào)的利益分享機(jī)制研究 應(yīng)用庫(kù)存理論及其整合模型建立并分析了競(jìng)爭(zhēng)型與協(xié)商型庫(kù)存 協(xié)調(diào)的利益 分享模型，對(duì)其效率和特征進(jìn)行了比較 企業(yè)供應(yīng)鏈模型和采購(gòu)滿(mǎn)意度評(píng)價(jià)研究 與

16、陜西省物資儲(chǔ)運(yùn)總公司合作的《陜西省區(qū)域現(xiàn)代物流配送示范 工程》項(xiàng)目可行性分析與初步設(shè)計(jì)。,我國(guó)對(duì)現(xiàn)代運(yùn)籌學(xué)的貢獻(xiàn),1）中國(guó)郵遞員問(wèn)題,2）貨郎擔(dān)問(wèn)題,基本特征——系統(tǒng)的整體概念、多學(xué)科的綜合以及模型方法的應(yīng)用,多學(xué)科的綜合 一門(mén)應(yīng)用學(xué)科，一般要同時(shí)擁有不同專(zhuān)門(mén)學(xué)科知識(shí)。運(yùn)籌學(xué)同樣 不例外。,系統(tǒng)的整體概念 系統(tǒng)——系統(tǒng)可以理解為是由相互關(guān)聯(lián)、相互制約、相互作用 的一些部分組成的具有某種功能

17、的有機(jī)整體。一個(gè)復(fù)雜的系統(tǒng)都有 多個(gè)子系統(tǒng)組成。項(xiàng)目可行性分析與初步設(shè)計(jì)。模型方法的應(yīng)用 在各門(mén)學(xué)科的研究中廣泛采用實(shí)驗(yàn)的方法，但運(yùn)籌學(xué)研究的系 統(tǒng)往往不能搬到實(shí)驗(yàn)室來(lái)，只能通過(guò)建立這個(gè)問(wèn)題的數(shù)學(xué)或模擬的 模型來(lái)代替。模型的準(zhǔn)確與否直接影響運(yùn)算結(jié)果。,四、運(yùn)籌的基本特征,五、運(yùn)籌研究的基本步驟,任何一門(mén)學(xué)科都包含四個(gè)方面：從觀測(cè)現(xiàn)象所得到的結(jié)果和進(jìn)行這種觀測(cè)所需的特殊方法；理論或模型的建立；將理論

18、與觀測(cè)相結(jié)合，并從結(jié)果得到預(yù)測(cè)；將這些預(yù)測(cè)結(jié)果同新的觀測(cè)相比較，并加以證實(shí)。運(yùn)籌的基本步驟可以歸納為：,1）提出問(wèn)題，認(rèn)清問(wèn)題——分析和表述問(wèn)題2）問(wèn)題的抽象——建模3）確定問(wèn)題的各種方案及確定方案的標(biāo)準(zhǔn)或方法、途徑——求解和優(yōu)化4）評(píng)估各個(gè)方案，選擇最優(yōu)方案——測(cè)量模型及對(duì)模型進(jìn)行必要的修正5）對(duì)解進(jìn)行檢驗(yàn)、靈敏性分析等——建立對(duì)解的有效控制6）回到實(shí)踐中——方案實(shí)施,六、運(yùn)籌研究的內(nèi)容,美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。

19、已知各制造一件時(shí)分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試時(shí)間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況如下表所示。問(wèn)該公司應(yīng)制造Ⅰ、Ⅱ兩種家電各多少件．使獲取的利潤(rùn)為最大。,例一,諸如這類(lèi)在經(jīng)營(yíng)管理中如何有效利用有限的人力、物力的情況下完成更多的任務(wù)，或在預(yù)定的任務(wù)目標(biāo)下，如何耗費(fèi)最少人力、物力去實(shí)現(xiàn)目標(biāo)等統(tǒng)籌規(guī)劃的問(wèn)題，是運(yùn)籌學(xué)最重要的問(wèn)題之一。我們把這種統(tǒng)籌問(wèn)題稱(chēng)為規(guī)劃論。 在運(yùn)籌學(xué)中，規(guī)劃論又

20、分為：線(xiàn)性規(guī)劃、非線(xiàn)性規(guī)劃、動(dòng)態(tài)規(guī)劃、目標(biāo)規(guī)劃等。我們這學(xué)期主要學(xué)習(xí)線(xiàn)性規(guī)劃、動(dòng)態(tài)規(guī)劃、目標(biāo)規(guī)劃。,六、運(yùn)籌研究的內(nèi)容,例二,諸如這類(lèi)有多個(gè)不同的生產(chǎn)、消費(fèi)者，如何合理利用生產(chǎn)者和消費(fèi)者之間的分配關(guān)系，從而達(dá)到最小費(fèi)用的問(wèn)題也運(yùn)籌學(xué)最重要的問(wèn)題之一。我們把這種分派問(wèn)題稱(chēng)為運(yùn)輸問(wèn)題。 在運(yùn)籌學(xué)中，運(yùn)輸問(wèn)題是一個(gè)廣義的“運(yùn)輸”，即許多其它問(wèn)題也可以通過(guò)適當(dāng)?shù)氖侄?，把它們轉(zhuǎn)化為運(yùn)輸問(wèn)題加以解決。這部分也是我們這學(xué)期主要學(xué)習(xí)內(nèi)容

21、之一。,某種物品先存放在兩個(gè)倉(cāng)庫(kù)A1相A2中，再運(yùn)往三個(gè)使用地B1，B2和B3，其間的距離(或單位運(yùn)價(jià))如下表小方格中的數(shù)據(jù)所示，各倉(cāng)庫(kù)的存量相使用地的需用量也都示于下表中，試建立控總運(yùn)輸量(或總運(yùn)費(fèi))最小的運(yùn)輸問(wèn)題數(shù)學(xué)模型。,六、運(yùn)籌研究的內(nèi)容,例三,諸如這類(lèi)可以通過(guò)圖與網(wǎng)絡(luò)來(lái)解決分析的問(wèn)題，運(yùn)籌學(xué)中把它們歸結(jié)到圖論和網(wǎng)絡(luò)分析中來(lái)，并建立了一整套的理論。本學(xué)期主要學(xué)習(xí)圖與網(wǎng)絡(luò)分析這部分。,從油田鋪設(shè)管道，把原油從A地運(yùn)到G地，要求

22、管道必須按照?qǐng)D中給定的道路鋪設(shè)，問(wèn)如何鋪設(shè) 煤氣管道，使得需要鋪設(shè)管道 的長(zhǎng)度最短？,,,,,,,,,,,,,A,G,B,C,D,E,F,5,2,2,4,1,3,8,2,6,5,5,3,例四,?,?,?,?,?,?,?,,,,,,,,,,A,4,B,6,C,6,D,7,E,5,G,7,F,9,H,4,I,8,六、運(yùn)籌研究的內(nèi)容,例五,諸如這類(lèi)具有不確定性或風(fēng)險(xiǎn)性決策的問(wèn)題，運(yùn)籌學(xué)中把它們歸結(jié)到?jīng)Q策論中來(lái)，并建立了一整套的理論。本學(xué)期我們

23、不做要求。 運(yùn)籌學(xué)所涉及的內(nèi)容還有很多，如排隊(duì)論、存儲(chǔ)論、對(duì)策論等，我們不做要求，就不一一介紹了。有興趣的同學(xué)可以找相關(guān)的資料。,某服裝加工廠(chǎng)的生產(chǎn)方案及市場(chǎng)狀態(tài)資料如表所示。如何 安排生產(chǎn)？,據(jù)美勞工局1992年統(tǒng)計(jì)預(yù)測(cè): 運(yùn)籌學(xué)應(yīng)用分析人員需求從1990年到2005年的增長(zhǎng)百分比預(yù)測(cè)為73%,增長(zhǎng)速度排到各項(xiàng)職業(yè)的前三位.,美1983統(tǒng)計(jì),七、運(yùn)籌學(xué)的推廣應(yīng)用前景,,,,八、基礎(chǔ)知識(shí),例六,八、基礎(chǔ)知識(shí),一般情況

24、,A=,a11 a12 … a1na21 a22 … a2n ┇ ┇ … ┇am1 am2 … amn,,b=,b1b2┇ bm,,1),AX=b,a11 a12 … a1n a21 a22 … a2n ┇ ┇ … ┇am1 am2 … amn,,b1b2┇ bm,,c11 c12 … c1r … c1n c22 … c2r … c

25、2n ┇ ┇ crr … crn,,d1d2┇ drdr+1┇ dm,,,,,1 e1r+1 … e1n 1 e2r+1 … e2n ┇ ┇ 1 err+1 … ern,,f1f2┇ frfr+1┇ fm,,,,,1）fk≠ 0 （k>

26、;r） 方程無(wú)解2）當(dāng)r=n時(shí)，方程有唯一解3）當(dāng)r<n時(shí)，方程有無(wú)窮解,結(jié)論：,八、基礎(chǔ)知識(shí),例七,x1 + 2x2 + x3 = 8 x1 + x4 = 4 x2 + x5 = 3-2x1 + x2 + + x6 = 4,,,,X=（0，0，8，4，3，4）

27、,X=（8，0，0，-4，3，20）,X=（0，4，0，4，-1，0）,I,八、基礎(chǔ)知識(shí),m維向量、向量無(wú)關(guān)、矩陣的秩、矩陣的逆,A=,a11 a12 … a1na21 a22 … a2n ┇ ┇ … ┇am1 am2 … amn,,m×n,,A1 A2 An,如果不存在一組非0的系數(shù)β1、β2 … βm，使得 β1A1 + β2A2 + … + βmAm=0，則稱(chēng)

28、A1、A2 … Am線(xiàn)性無(wú)關(guān),線(xiàn)性無(wú)關(guān),m維向量,矩陣的秩,簡(jiǎn)單的可以理解為：如果矩陣A中存在最多的線(xiàn)性無(wú)關(guān)的向量個(gè)數(shù)稱(chēng)為該矩陣的秩,矩陣的逆,如果矩陣A、B，使得AB=BA=I，則稱(chēng)B為A的逆矩陣或A為B的逆矩陣。A的逆記作A-1,八、基礎(chǔ)知識(shí),分塊矩陣、方程組的解,B、C、E、F分別稱(chēng)為A的分塊矩陣,B-1,I,B-1,設(shè)B為m×m的方陣,I,第一章 線(xiàn)性規(guī)劃及單純形法,§1.1 數(shù)學(xué)規(guī)劃的模型,一、

29、問(wèn)題的提出 及其數(shù)學(xué)模型,1）生產(chǎn)問(wèn)題,,設(shè)： x1 —— I產(chǎn)品的生產(chǎn)量 x2 —— II產(chǎn)品的生產(chǎn)量,利潤(rùn) max z= 2 x1 + x2,2）場(chǎng)地租用問(wèn)題,,設(shè)：xij為第i月租用租期為j個(gè)月面積, 即x11為第1月租用租期為1個(gè)月面積,租金 min z= 2800（x11+x21 +x31 +x41）+4500（x12+x22 +x32 +x42） +6000（x13+

30、x23 +x33 +x43）+7300（x14+x24 +x34 +x44）,租金 min z= 2800（x11+x21 +x31 +x41）+4500（x12+x22 +x32） +6000（x13+x23 ）+7300x14,二、線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型,1）數(shù)學(xué)模型的要素,規(guī)劃問(wèn)題的數(shù)學(xué)模型的要素包括： （1）變量，或決策變量，是問(wèn)題中待確定的未知量； （2）目標(biāo)函數(shù) 它是決策變量的函

31、數(shù)。按優(yōu)化目標(biāo)有最大化與最小化， 即max或min （3）約束條件，指約束變量取值時(shí)受到的各種資源條件的限制。,2）線(xiàn)性規(guī)劃的特征（含義）,線(xiàn)性規(guī)劃問(wèn)題的特征（含義） ： （1）目標(biāo)函數(shù)是決策變量的線(xiàn)性函數(shù) （2）約束條件是含決策變量的線(xiàn)性等式或不等式實(shí)際問(wèn)題中線(xiàn)性的含義：（1）嚴(yán)格的比例性（正、反比）； （2）可疊加性,3）線(xiàn)性規(guī)劃的數(shù)學(xué)模型的表示,max（min）

32、 z = c1x1 + c2x2 + … … + cnxn,x1，x2 ， … … ，xn ≥ 0,目標(biāo)函數(shù),約束條件,4）線(xiàn)性規(guī)劃的數(shù)學(xué)模型的其它表示方式,xj ≥ 0 (j=1,2, … … ,n),,st .,aijxj ≤ (或=,≥) bi (i=1,2, … … ,m),max（min） z =,X ≥ 0,,st .,CX C=（c1 , c2 , … … , cn ）,Pjxj ≤(或=,≥) b,

33、用向量表達(dá),Pj=（a1j , a2j , … … , amj）-1,b=（b1 , b2 , … … , bm）-1,簡(jiǎn)化表示,X=（x1 , x2 , … … , xn）-1,其中,X ≥ 0,,st .,AX ≤(或=,≥) b,用矩陣表達(dá),A=,,a11 a12 … a1n,a21 a22 … a2n,am1 am2 amn,…,…,…,矩陣A

34、稱(chēng)為約束方程組（約束條件）的系數(shù)矩陣。,max（min） z =,CX C=（c1 , c2 , … … , cn ）,第二節(jié) 圖解法,1）生產(chǎn)問(wèn)題,利潤(rùn) max z= 2 x1 + x2,,,,,,可行域,max z=x1+3x2s.t. x1+ x2≤6-x1+2x2≤8x1 ≥0, x2≥0,例2,x1,x2,,,,,,,,,,,目標(biāo)函數(shù)等值線(xiàn),,可行域,,最優(yōu)解,6,6,-8,4

35、,,二）解的可能情況,1）無(wú)窮多最優(yōu)解,2）無(wú)解（無(wú)可行解）,二）解的可能情況,3）無(wú)界解,1）唯一最優(yōu)解,3）無(wú)解（無(wú)可行解）,2）無(wú)窮多最優(yōu)解,4）無(wú)界解,1）線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)格式,max z =,xj ≥ 0 (j=1,2, … … ,n),,st .,cjxj,aijxj = bi (i=1,2, … … ,m),其中： 1）目標(biāo)為最大化； 2） bi 為非負(fù)數(shù)； 3） xj 為非負(fù)數(shù)； 4）

36、約束為等式。,目標(biāo)為最大化,約束為等式,bi 為非負(fù)數(shù),xi 為非負(fù)數(shù),線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)格式,2）化一般線(xiàn)性規(guī)劃問(wèn)題為標(biāo)準(zhǔn)格式的方法,利潤(rùn) max z= 2 x1 + x2,怎么辦？,5x2 　 + x3 = 15,6x1 + 2x2 + x4 = 24,x1 + x2 + x5 = 5,x1，x2 ，x3 ，x4 ，x5 ≥ 0,利潤(rùn) m

37、ax z= 2 x1 + x2 + 0x3 + 0x4 + 0x5,例一,,,x11+x12 +x13 +x14 – x1 = 15,x12+x13 +x14 + x21+x22 +x23 – x2 = 10,x13+x14 + x22+x23 +x31 +x32 - x3 = 20,xij ，x1 ，x2 ，x3 ，x4 ≥ 0,租金 max z/ = -z = -2800（x11+x

38、21 +x31 +x41）- 4500（x12+x22 +x32） - 6000（x13+x23 ）- 7300x14+ 0x1+ 0x2 + 0x3 + 0x4,租金 min z= 2800（x11+x21 +x31 +x41）+4500（x12+x22 +x32） +6000（x13+x23 ）+7300x14,約束條件,x11+x12 +x13 +x14 ≥ 15,x12

39、+x13 +x14 + x21+x22 +x23 ≥ 10,x13+x14 + x22+x23 +x31 +x32 ≥ 20,xij ≥ 0 (i, j = 1,2,3,4),,st .,x14+x23 +x24 +x32 +x41 ≥ 12,x14+x23 +x24 +x32 +x41 - x4 = 12,例二,,一個(gè)最有代表性的例子,min z = x1 + 2x2 + 3x3,約束條件,-2x1 + x2 +

40、 x3 ≤ 9,-3x1 + x2 + 2x3 ≥ 4,4x1 - 2x2 - 3x3 = -6,x1 ≤ 0； x2 ≥ 0； x3取值無(wú)約束,,st .,步驟,1）加入松弛變量和剩余變量把 不等式約束變?yōu)榈仁郊s束；,約束條件,-2x1 + x2 + x3 ≤ 9,-3x1 + x2 + 2x3 ≥ 4,4x1 - 2x2 - 3x3 = -6,x1 ≤ 0；,,st .,x2 ≥ 0；,x3取值無(wú)約束,-3x1 +

41、 x2 + 2x3 – x5 = 4,-2x1 + x2 + x3 + x4 = 9,x4，x5 ≥ 0；,,一個(gè)最有代表性的例子,min z = x1 + 2x2 + 3x3,約束條件,-2x1 + x2 + x3 ≤ 9,-3x1 + x2 + 2x3 ≥ 4,4x1 - 2x2 - 3x3 = -6,x1 ≤ 0； x2 ≥ 0； x3取值無(wú)約束,,st .,1）加入松弛變量和剩余變量把 不等式約束變?yōu)榈仁郊s束；,

42、約束條件,4x1 - 2x2 - 3x3 = -6,x1 ≤ 0；,,st .,x2 ≥ 0；,x3取值無(wú)約束,-3x1 + x2 + 2x3 – x5 = 4,-2x1 + x2 + x3 + x4 = 9,2）把b≤0加等式約束兩邊同 乘以-1把b變成≥0約束；,-4x1 + 2x2 + 3x3 = 6,x4，x5 ≥ 0；,步驟,,一個(gè)最有代表性的例子,min z = x1 + 2x2 + 3x3,約束條件,-2x1

43、+ x2 + x3 ≤ 9,-3x1 + x2 + 2x3 ≥ 4,4x1 - 2x2 - 3x3 = -6,x1 ≤ 0； x2 ≥ 0； x3取值無(wú)約束,,st .,1）加入松弛變量和剩余變量把 不等式約束變?yōu)榈仁郊s束；,約束條件,x1 ≤ 0；,,st .,x2 ≥ 0；,x3取值無(wú)約束,-3x1 + x2 + 2x3 – x5 = 4,-2x1 + x2 + x3 + x4 = 9,2）把b≤0加等式約束兩邊同

44、 乘以-1把b變成≥0約束；,-4x1 + 2x2 + 3x3 = 6,3）變量xi≤0，令xi/=- xi 此時(shí)xi/ ≥ 0；,x1/ ≥ 0；,4x1/ + 2x2 + 3x3 = 6,3x1/ + x2 + 2x3 – x5 = 4,2x1/ + x2 + x3 + x4 = 9,x4，x5 ≥ 0；,步驟,,一個(gè)最有代表性的例子,min z = x1 + 2x2 + 3x3,約束條件,-2x1 + x2

45、 + x3 ≤ 9,-3x1 + x2 + 2x3 ≥ 4,4x1 - 2x2 - 3x3 = -6,x1 ≤ 0； x2 ≥ 0； x3取值無(wú)約束,,st .,1）加入松弛變量和剩余變量把 不等式約束變?yōu)榈仁郊s束；,約束條件,,st .,x2 ≥ 0；,x3取值無(wú)約束,2）把b≤0加等式約束兩邊同 乘以-1把b變成≥0約束；,3）變量xi≤0，令xi/=- xi 此時(shí)xi/ ≥ 0；,x4，x5 ≥ 0；,4）

46、令無(wú)約束變量xi=xi/- xi∥代入 約束條件，xi用xi/， xi∥代替；,x3/ ≥ 0 ， x3∥ ≥ 0,4x1/ + 2x2 + 3x3/ - 3x3∥ = 6,3x1/ + x2 + 2x3/ -2x3∥ – x5 = 4,2x1/ + x2 + x3/ - x3∥ + x4 = 9,步驟,,一個(gè)最有代表性的例子,min z = x1 + 2x2 + 3x3,約束條件,-2x1 + x2 + x3 ≤ 9

47、,-3x1 + x2 + 2x3 ≥ 4,4x1 - 2x2 - 3x3 = -6,x1 ≤ 0； x2 ≥ 0； x3取值無(wú)約束,,st .,1）加入松弛變量和剩余變量把 不等式約束變?yōu)榈仁郊s束；,約束條件,,st .,x2 ≥ 0；,2）把b≤0加等式約束兩邊同 乘以-1把b變成≥0約束；,3）變量xi≤0，令xi/=- xi 此時(shí)xi/ ≥ 0；,x1/ ≥ 0；,x4，x5 ≥ 0；,4）令無(wú)約束變量xi

48、=xi/- xi∥代入 約束條件，xi用xi/， xi∥代替；,x3/ ≥ 0 ， x3∥ ≥ 0,4x1/ + 2x2 + 3x3/ - 3x3∥ = 6,3x1/ + x2 + 2x3/ -2x3∥ – x5 = 4,2x1/ + x2 + x3/ - x3∥ + x4 = 9,5）如目標(biāo)為min的，令z/ = -z ， 求z/ 的max。,max z/ = -z = x1/ - 2x2 - 3x3/ +

49、 3x3∥ + 0x4 - 0x5,步驟,作業(yè),P43，1.1: (1) (2)P43，1.2: (1) (2),返 回,公元前二一八年，秦始皇帶大隊(duì)人馬外出巡視，行進(jìn)到博浪沙(河南原陽(yáng)縣)，車(chē)隊(duì)正在緩緩前進(jìn)，突然飛來(lái)一個(gè)大鐵椎，只聽(tīng)嘩啦一聲，秦始皇座車(chē)后面的副車(chē)被打得粉碎，把秦始皇嚇壞了，他真發(fā)火了，立

50、刻下令，全國(guó)搜捕刺客，結(jié)果搜查了十天，也沒(méi)抓到，只得算了?！　〈炭褪钦l(shuí)呢?原來(lái)他叫張良，是韓國(guó)人，他要為韓國(guó)報(bào)仇。他有一個(gè)朋友是個(gè)大力士，使用的兵器是一個(gè)大鐵椎，足有六十斤重。他們預(yù)先得知秦始皇要從博浪沙經(jīng)過(guò)，就在路旁樹(shù)林隱蔽的地方埋伏好，只等車(chē)隊(duì)到來(lái)，哪知這一椎扔出去沒(méi)砸準(zhǔn)，他們只得馬上躲起來(lái)。　　張良躲過(guò)了搜查，就在下邳(江蘇睢寧西北)住下來(lái)，一面鉆研兵法，一面再等報(bào)仇的機(jī)會(huì)?！　≌f(shuō)起張良學(xué)兵法，這里還有一個(gè)傳說(shuō)故事呢?！　?/p>

51、有一次，張良獨(dú)自散步，走到一座大橋上，見(jiàn)一位穿土黃色大褂的老人，坐在橋頭上。他見(jiàn)張良走過(guò)來(lái)，故意將一只腳向后一縮，一只鞋掉到橋下去了。　　老人不客氣地對(duì)張良說(shuō):“年輕人，下去把我的鞋子撿上來(lái)?！?　　張良聽(tīng)了有點(diǎn)不高興，可是一想，他是老人，不多計(jì)較，就到橋下，拾起鞋子，又走上來(lái)遞給老人?！　≌l(shuí)知那老人不接鞋子，卻把腳一伸，說(shuō):“給我穿上。”　　張良沒(méi)說(shuō)什么，就又順從地給老人穿上了鞋?！　∧抢先诉@才微微一笑，站起身來(lái)走了?！　?/p>

52、張良覺(jué)得這位老人好奇怪，不是一般人，站著沒(méi)動(dòng)，目送老人走遠(yuǎn) ?！　≌l(shuí)知老人走了很遠(yuǎn)又返回來(lái)了，對(duì)張良說(shuō):“年輕人，不錯(cuò)呀，我倒樂(lè)意教導(dǎo)教導(dǎo)你。過(guò)五天，天一亮，你到橋上來(lái)見(jiàn)我?！薄　埩悸?tīng)后忙跪下答應(yīng)了。　　第五天，張良一早來(lái)到橋上，誰(shuí)知老人已先到了，生氣地對(duì)張良說(shuō):“你跟老人約會(huì)，怎么叫老人等你呢?”　　張良急忙認(rèn)錯(cuò)，老人說(shuō):“走吧，再過(guò)五天早點(diǎn)兒來(lái)?！闭f(shuō)完，一甩袖子走了。　　又過(guò)了五天，張良一聽(tīng)雞叫就跑向大橋，還沒(méi)上橋，就看

53、見(jiàn)老人了，老人瞪了他一眼，說(shuō):“過(guò)五天再來(lái)吧。”　　到了第四天半夜，張良就來(lái)到橋上等。一會(huì)兒，看見(jiàn)老人一步步走來(lái)。這次老人露出了慈祥的笑容，對(duì)張良說(shuō):“這才對(duì)了?！比缓髲男渥永锾统鲆徊繒?shū)交給張良，說(shuō):“回去好好讀，將來(lái)可為國(guó)家出點(diǎn)兒力呢?！薄　埩歼€想再問(wèn)，老人不再說(shuō)話(huà)，頭也不回，就走了。　　這時(shí)天才亮，張良趁著晨光一看，這部書(shū)原來(lái)是一部珍貴的兵書(shū)--—周朝姜太公編的《兵法》?！　拇耍瑥埩伎炭嚆@研《兵法》，后來(lái)成了有名的軍事家