運(yùn)籌學(xué)第一講(緒論,線性規(guī)劃)

運(yùn)籌學(xué)千里之外決勝帷幄之中運(yùn)籌主講教師杜明銀一號(hào)教學(xué)樓103室OperationalResearch/Operation’sresearch譯法英文簡(jiǎn)稱:OR港臺(tái):作業(yè)研究日本:運(yùn)用學(xué)其他:作戰(zhàn)研究中國(guó)大陸:運(yùn)籌學(xué)“上（劉邦）曰：夫運(yùn)籌帷幄之中，決勝千里之外，吾不如子房（張良）?！薄稘h書(shū)·高帝紀(jì)》我國(guó)是在1957年正式定名該學(xué)科為“運(yùn)籌學(xué)”。

一、中國(guó)古代樸素的系統(tǒng)思想田忌賽馬圍魏救趙

——顯王十六年（公元前353年）齊威王使田忌救趙?！锛捎w。孫子曰：“夫解雜亂糾紛者不控拳，救斗者不搏。批亢搗虛，形格勢(shì)禁，則自為解耳。今梁、趙相攻，輕兵銳卒必竭于外，老弱疲于內(nèi)。子不若引兵疾走魏都，據(jù)其街路，沖其方虛，彼必釋趙以自救。是我一舉解趙之圍而收弊于魏也?！碧锛蓮闹?。十月，邯鄲降魏。魏師還，與齊戰(zhàn)于桂陵，魏師大敗。丁渭修復(fù)皇宮

北宋大中祥符年間（1008～1016），丁渭負(fù)責(zé)修復(fù)汴梁被火焚毀的皇宮?！耙慌e而三役濟(jì)”。都江堰的修造（治水）無(wú)壩引水工程。原來(lái)“人或成魚(yú)鱉”的水旱災(zāi)嚴(yán)重的成都平原，成為“水旱從人，不知饑饉，時(shí)無(wú)荒年”的“天府之國(guó)”。它是“魚(yú)嘴、飛沙堰和寶瓶口”三個(gè)工程合一的系統(tǒng)工程。對(duì)比思考：為何都江堰，這一兩千多年前的水利工程，沒(méi)有采用什么先進(jìn)的技術(shù)和建造雄偉的大壩，卻能夠承載“天府之國(guó)”千年的風(fēng)調(diào)雨順，解決了岷江的防洪、排沙兩大技術(shù)難題，還能灌溉農(nóng)田、保持生態(tài)環(huán)境平衡？而現(xiàn)在各國(guó)修建的水壩雖然能利用水資源發(fā)電、攔起大壩防洪泄洪，存在問(wèn)題卻很多，有的在運(yùn)行了一百年不到，幾十年內(nèi)就要被強(qiáng)行炸毀？軍事運(yùn)籌學(xué)的妙用

案例：

1943年2月，二戰(zhàn)進(jìn)入最緊張的階段。美國(guó)為了報(bào)復(fù)日本襲擊珍珠港，加緊了在太平洋上的搜索活動(dòng)，積極尋殲日本艦艇。軍事運(yùn)籌學(xué)的妙用從新不列顛島到新幾內(nèi)亞有南北兩條航線，每條航線都需要三天航程。美軍從天氣預(yù)報(bào)中得知，在最近三天內(nèi)，北路航線是陰雨天氣，南路航線天氣晴朗。美軍受兵力和時(shí)間的限制，不可能對(duì)兩條航線同時(shí)進(jìn)行搜索，在這種情況下，應(yīng)該走哪條路線攔截日本艦隊(duì)呢？運(yùn)用軍事運(yùn)籌學(xué)，美軍有如下四種搜索方案：一、搜索力量主要集中在北路，日本艦隊(duì)也走北路。北路雖然天氣狀況差，能見(jiàn)度低，但是因?yàn)樗阉髁α考?，可以在一天?nèi)發(fā)現(xiàn)日本艦隊(duì)，從而有兩天的轟炸時(shí)間。二、搜索力量主要集中在北路，日本艦隊(duì)走南路。南路雖然天氣好，便于偵察機(jī)搜索，但是因?yàn)橹饕α考性诒甭?，只有很少的飛機(jī)搜索南路，這樣發(fā)現(xiàn)日本艦隊(duì)也需要一天時(shí)間，有兩天時(shí)間用于轟炸。三、搜索力量主要集中在南路，日本艦隊(duì)走北路。這就是說(shuō)，北路只有很少的飛機(jī)在很差的天氣狀況下搜索，要發(fā)現(xiàn)日本艦隊(duì)需要兩天時(shí)間，而留下轟炸的時(shí)間只有一天。四、搜索力量主要集中在南路，日本艦隊(duì)也走南路。這樣南路天氣狀況好，搜索的飛機(jī)也多，可以在很短的時(shí)間內(nèi)發(fā)現(xiàn)日本艦隊(duì)，從而有接近三天的時(shí)間進(jìn)行轟炸。綜合四種情況，得出的結(jié)論是：從美軍方面看，采取第四種搜索方法最有利；從日軍方面看，走北路最合適。在戰(zhàn)爭(zhēng)中，敵人是按照對(duì)自己最有力的方案行動(dòng)的，所以采取的搜索方法應(yīng)該是以敵人認(rèn)為于己最有利的方式選擇。肯尼將軍根據(jù)上述意見(jiàn)，決定把主要力量集中在北路。結(jié)果不出美軍所料，美日之間的俾斯麥海戰(zhàn)真的在美軍預(yù)料地點(diǎn)發(fā)生。運(yùn)籌學(xué)案例一個(gè)博弈論的案例。博弈論應(yīng)用最廣泛的領(lǐng)域大概就是經(jīng)濟(jì)和軍事，甚至經(jīng)濟(jì)學(xué)上把博弈論當(dāng)做經(jīng)濟(jì)學(xué)的一個(gè)分支來(lái)研究。《孫子兵法》中的“知己知彼，百戰(zhàn)不殆”。(電視劇中的運(yùn)籌)二、運(yùn)籌學(xué)產(chǎn)生的背景1、軍事

鮑德西（Bawdsey）雷達(dá)站的研究

“Blackett馬戲團(tuán)”——成立了世界上第一個(gè)運(yùn)籌學(xué)小組。以物理學(xué)家Blackett為首，小組成員包括三名心理學(xué)家、兩名數(shù)學(xué)家、兩名應(yīng)用數(shù)學(xué)家、一名天文物理學(xué)家、一名普通物理學(xué)家、一名海軍軍官、一名陸軍軍官、一名測(cè)量人員。研究的問(wèn)題是：設(shè)計(jì)雷達(dá)探測(cè)、雷達(dá)信息傳遞給指揮系統(tǒng)和武器作戰(zhàn)系統(tǒng)、指揮系統(tǒng)與防空武器的協(xié)調(diào)。如何改進(jìn)空防系統(tǒng)。這個(gè)項(xiàng)目是運(yùn)籌學(xué)的典范，整體化的思想、明確的目標(biāo)、多學(xué)科的協(xié)同、數(shù)量化的分析、最優(yōu)化的結(jié)果，巨大的實(shí)際價(jià)值，以及簡(jiǎn)明樸素的表述，都展示了運(yùn)籌學(xué)的本色?！癇lackett備忘錄”

1941年5月，Blackett寫(xiě)了一份“Scientistsattheoperationallevel”（作戰(zhàn)位置上的科學(xué)家）的簡(jiǎn)短備忘錄。主要是建議各大指揮部創(chuàng)立運(yùn)籌學(xué)小組。之后，Blackett

寫(xiě)了第二份“備忘錄”?！斑\(yùn)籌學(xué)的一個(gè)明顯特征，正如目前所實(shí)踐的那樣，是它具有和應(yīng)該有強(qiáng)烈的實(shí)際性質(zhì)。它的目的是幫助找出一些方法，以改進(jìn)正在進(jìn)行中或未來(lái)可能進(jìn)行的作戰(zhàn)中的效率。為了達(dá)到這個(gè)目的，要研究過(guò)去的作戰(zhàn)事實(shí)，要得出一些理論來(lái)解釋這些事實(shí)，從而對(duì)未來(lái)的作戰(zhàn)做出預(yù)測(cè)?！贝笪餮蠓礉搼?zhàn)

美國(guó)的物理學(xué)家Morse的反潛運(yùn)籌小組，經(jīng)過(guò)多方實(shí)地調(diào)查，最后提出了兩條寶貴的建議：一是：由原來(lái)的艦艇投擲水雷，改為由飛機(jī)投擲深水炸彈，起爆深度由原來(lái)的100米左右，改為25米，即德軍潛艇剛下潛不久攻擊效果最佳。二是：運(yùn)送物資的船隊(duì)和護(hù)航的艦艇編隊(duì)由原來(lái)的小規(guī)模多批次，改為加大規(guī)模減少批次。這樣能降低損失率。邱吉爾采納了Morse的建議，不僅成功突破了德軍的封鎖線，且重創(chuàng)了德國(guó)的潛艇編隊(duì)。2、經(jīng)濟(jì)和管理Erlong與排隊(duì)論在1909～1920年間，哥本哈根電話公司的工程師A.K.Erlong的《概率與電話通話原理》，開(kāi)創(chuàng)了運(yùn)籌學(xué)的一個(gè)重要分支——排隊(duì)論。

Von.Neumann與對(duì)策論Von.Neumann的論著《對(duì)策論與經(jīng)濟(jì)行為》，將經(jīng)濟(jì)中的沖突、協(xié)調(diào)和平衡問(wèn)題用量化的方式來(lái)解決。

Kantorovich與“生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法”錢(qián)學(xué)森、許國(guó)志在50年代中期將運(yùn)籌學(xué)由西方引進(jìn)中國(guó)。

三、運(yùn)籌學(xué)的定義、性質(zhì)和特點(diǎn)１、運(yùn)籌學(xué)的定義運(yùn)籌學(xué)是一門(mén)應(yīng)用性科學(xué)，主要研究方法是定量化和模型化方法，特別是運(yùn)用各種數(shù)學(xué)模型。運(yùn)籌學(xué)的目的是基于所研究的系統(tǒng)，力求獲得一個(gè)合理運(yùn)用人力、物力、財(cái)力和各種資源的最佳方案，充分發(fā)揮和提高系統(tǒng)的效益和效果，以使系統(tǒng)獲得最優(yōu)目標(biāo)。運(yùn)用科學(xué)方法來(lái)解決工業(yè)、商業(yè)

、政府、國(guó)防等部門(mén)里有關(guān)人員、機(jī)器、物質(zhì)、金錢(qián)等大型系統(tǒng)的指揮或管理中所出現(xiàn)的復(fù)雜問(wèn)題的一門(mén)學(xué)科。其目的是幫助管理者以科學(xué)方法確定其方針和行動(dòng)——英國(guó)運(yùn)籌學(xué)學(xué)會(huì)運(yùn)籌學(xué)是應(yīng)用系統(tǒng)的、科學(xué)的、數(shù)學(xué)分析的方法,通過(guò)建立、分析、檢驗(yàn)和求解數(shù)學(xué)模型而獲得最優(yōu)決策的科學(xué)?！覈?guó)近代一些運(yùn)籌學(xué)科學(xué)工作者２、運(yùn)籌學(xué)的性質(zhì)和特點(diǎn)

科學(xué)方法——經(jīng)過(guò)概括總結(jié)，可有組織地解決幾類問(wèn)題量化——需要建立數(shù)學(xué)模型，研究數(shù)學(xué)方法和借助計(jì)算機(jī)技術(shù)予以解決。作為運(yùn)籌學(xué)工作者，能提供可以量化方面的分析，指出那些定性的因素。多學(xué)科交叉，特別是在解決復(fù)雜的社會(huì)問(wèn)題。綜合運(yùn)用經(jīng)濟(jì)學(xué)、心理學(xué)、物理學(xué)、化學(xué)等學(xué)科的方法。最優(yōu)決策。滿意。“運(yùn)籌學(xué)是一種給出一種壞的答案的藝術(shù)，否則的話問(wèn)題的結(jié)果會(huì)更壞?！彼摹⑦\(yùn)籌學(xué)的基本工作步驟

提出和形成問(wèn)題。提出問(wèn)題的目標(biāo)、約束條件、問(wèn)題的可控變量及相關(guān)參數(shù)，搜集有關(guān)資料。建立數(shù)學(xué)模型——將可控變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來(lái)。求解——主要用數(shù)學(xué)方法求出模型的最優(yōu)解、次優(yōu)解、滿意解，復(fù)雜模型求解要用計(jì)算機(jī)。解的檢驗(yàn)——檢查模型和求解步驟有無(wú)錯(cuò)誤，檢查解是否反映現(xiàn)實(shí)問(wèn)題。解的控制。通過(guò)控制解的變化過(guò)程決定對(duì)解是否要做一定的調(diào)整。解的實(shí)施——向?qū)嶋H運(yùn)作部門(mén)講清解的用法。對(duì)實(shí)施中可能產(chǎn)生的問(wèn)題做出修改。

五、運(yùn)籌學(xué)的應(yīng)用市場(chǎng)銷售生產(chǎn)計(jì)劃資本運(yùn)營(yíng)庫(kù)存管理運(yùn)輸問(wèn)題財(cái)政和會(huì)計(jì)人事管理設(shè)備維修和更新項(xiàng)目評(píng)價(jià)和選擇工程優(yōu)化設(shè)計(jì)計(jì)算機(jī)和信息系統(tǒng)城市管理發(fā)展戰(zhàn)略軍事六、運(yùn)籌學(xué)的分支線性規(guī)劃（LinearProgramming)目標(biāo)規(guī)劃（GoalProgramming)整數(shù)規(guī)劃(IntegerProgramming)非線性規(guī)劃(Non-linearProgramming)動(dòng)態(tài)規(guī)劃(DynamicProgramming)圖與網(wǎng)絡(luò)分析（Graph&networkAnalysis)排隊(duì)論(Queuetheory)存貯論(Stockcontroltheory)對(duì)策論(Gametheory)決策論(Decisiontheory)多目標(biāo)決策(Multicriteriondecisionmaking)計(jì)算機(jī)模擬組合優(yōu)化可靠性理論數(shù)據(jù)包絡(luò)分析現(xiàn)代優(yōu)化算法(模擬退火,遺傳算法,人工神經(jīng)網(wǎng)絡(luò),蟻群優(yōu)化)模糊決策灰色系統(tǒng)理論運(yùn)籌學(xué)方法應(yīng)用例運(yùn)籌學(xué)方法應(yīng)用例線性規(guī)劃生產(chǎn)結(jié)構(gòu)優(yōu)化非線性規(guī)劃投資組合優(yōu)化0-1規(guī)劃選址問(wèn)題動(dòng)態(tài)規(guī)劃資源分配問(wèn)題網(wǎng)絡(luò)分析工程計(jì)劃優(yōu)化排隊(duì)論服務(wù)系統(tǒng)優(yōu)化存儲(chǔ)論訂貨庫(kù)存管理決策分析機(jī)會(huì)選擇七、運(yùn)籌學(xué)的發(fā)展“在大部分的大學(xué)院系中，OR成為了學(xué)術(shù)性的模型，而不是現(xiàn)實(shí)世界的模型，因而這樣培養(yǎng)出來(lái)的工作者能夠向管理者們提供的僅僅是模型表達(dá)出來(lái)的特定解，這與我們當(dāng)初提出的目標(biāo)是背道而馳的?！蹦承＜毅@到了運(yùn)籌數(shù)學(xué)的深處，只迷戀于數(shù)學(xué)模型的精巧、復(fù)雜，使用高深的數(shù)學(xué)工具，而忘記了運(yùn)籌學(xué)的本色，忽略了多學(xué)科的交叉聯(lián)系和解決實(shí)際問(wèn)題的研究。“不要把OR定義得太死，要回到OR的原始精神。面向問(wèn)題，而不是面向我們口袋里的工具。”“過(guò)去過(guò)分強(qiáng)調(diào)精巧的數(shù)學(xué)模型，可是很難解決那些非結(jié)構(gòu)性的復(fù)雜問(wèn)題，寧可用看起來(lái)簡(jiǎn)單粗糙的方法，加上決策者的正確判斷恰能解決實(shí)際問(wèn)題?！眹?guó)外有關(guān)運(yùn)籌學(xué)雜志OperationsresearchManagementscienceJournalofoperationsresearchDecisionscienceComputerandoperationsresearchEuropeanJournalofOperationalResearchJournaloftheoperationalResearchSociety

國(guó)內(nèi)有關(guān)運(yùn)籌學(xué)雜志系統(tǒng)工程理論與實(shí)踐系統(tǒng)工程學(xué)報(bào)運(yùn)籌與管理運(yùn)籌學(xué)學(xué)報(bào)系統(tǒng)工程教學(xué)參考書(shū)1.《運(yùn)籌學(xué)ABC：成就、信念和能力》，李宗元等主編經(jīng)濟(jì)管理出版社，2000年版。2.《管理運(yùn)籌學(xué)》，韓伯棠編著，高等教育出版社，2002年8月第一版3.《管理科學(xué)基礎(chǔ)（修訂版）》，吳育華、杜綱編著，天津大學(xué)出版社，2004年版4.《運(yùn)籌學(xué)》，趙可培主編，上海財(cái)經(jīng)大學(xué)出版社，2008年2月第2版5.《運(yùn)籌學(xué)習(xí)題集》，胡運(yùn)權(quán)主編，清華大學(xué)出版社，2002年9月第三版6.

《優(yōu)化建模與LINDO/LINGO軟件》，謝金星薛毅編著，清華大學(xué)出版社，2005年7月第一版線性規(guī)劃(LinearProgramming)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題的求解方法線性規(guī)劃的圖解法線性規(guī)劃的單純形法單純形法的進(jìn)一步討論線性規(guī)劃模型的應(yīng)用

為了完成一項(xiàng)任務(wù)或達(dá)到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達(dá)到一定的目的，這個(gè)過(guò)程就是規(guī)劃。例一、有一正方形鐵皮，如何截取x使容積為最大？xa此為無(wú)約束極值問(wèn)題一、線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型（一）、問(wèn)題的提出

設(shè)備產(chǎn)品

A

B

C

D利潤(rùn)（元）

Ⅰ

2

1

4

0

2

Ⅱ

2

2

0

4

3有效臺(tái)時(shí)

12

8

16

12

例二、已知資料如下表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？或如何考慮利潤(rùn)大，產(chǎn)品好銷。模型maxZ=2x1+3x2

x1≥0,x2≥0s.t.

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此為帶約束的極值問(wèn)題問(wèn)題中總有未知的變量，需要我們?nèi)ソ鉀Q。

要求：有目標(biāo)函數(shù)及約束條件，一般有非負(fù)條件存在，由此組成規(guī)劃數(shù)學(xué)模型。

如果在規(guī)劃問(wèn)題的數(shù)學(xué)模型中，變量是連續(xù)的（數(shù)值取實(shí)數(shù)）其目標(biāo)函數(shù)是有關(guān)線性函數(shù)（一次方），約束條件是有關(guān)變量的線性等式或不等式，這樣，規(guī)劃問(wèn)題的數(shù)學(xué)模型是線性的。反之，就是非線性的規(guī)劃問(wèn)題（其中一個(gè)條件符合即可）。（二）、數(shù)學(xué)模型

1、目標(biāo)函數(shù)：約束條件：①②③2、線性規(guī)劃數(shù)學(xué)模型的一般形式也可以記為如下形式：目標(biāo)函數(shù)：約束條件：向量形式：矩陣形式：規(guī)劃確定型隨機(jī)型靜態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃非整數(shù)規(guī)劃整數(shù)規(guī)劃非整數(shù)規(guī)劃3、規(guī)劃類型一般有兩種方法圖解法單純形法兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式二、線性規(guī)劃問(wèn)題的求解方法

（一）、求解方法畫(huà)出不等式組表示的平面區(qū)域。3x+5y≤25

x-4y≤-3x≥1一個(gè)簡(jiǎn)單的例子

3x+5y≤25x-4y≤-3x≥1在該平面區(qū)域上

問(wèn)題1：ｘ有無(wú)最大(小)值？問(wèn)題２：ｙ有無(wú)最大(小)值？xyox-4y=-33x+5y=25x=1問(wèn)題３：2ｘ+ｙ有無(wú)最大(小)值？CABxyox=1CB設(shè)z＝2ｘ+ｙ,式中變量ｘ、ｙ滿足下列條件，求ｚ的最大值和最小值。

3x+5y≤25x-4y≤-3x≥1Ａx-4y=-33x+5y=25xyox-4y=-3x=1C設(shè)z＝2ｘ+ｙ,式中變量ｘ、ｙ滿足下列條件，

求ｚ的最大值和最小值。3x+5y≤25x-4y≤-3x≥1BＡ3x+5y=25問(wèn)題1:

將z＝2ｘ+ｙ如何變形?問(wèn)題2:z幾何意義是__________________________。斜率為-2的直線在y軸上的截距

則直線l：

2ｘ+ｙ=z是一簇與l0平行的直線,故直線l可通過(guò)平移直線l0而得，當(dāng)直線往右上方平移時(shí)z逐漸增大：當(dāng)l過(guò)點(diǎn)

B(1,1)時(shí),z

最小,即zmin=3

當(dāng)l過(guò)點(diǎn)A(5,2)時(shí)，ｚ最大,

即zmax＝2×5+2＝12。析:

作直線l0

：2ｘ+ｙ=0,ｙ＝-2ｘ+z最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值或最小值的可行解。線性約束條件：約束條件中均為關(guān)于x、y的一次不等式或方程。有關(guān)概念

約束條件：由ｘ、ｙ的不等式（方程）構(gòu)成的不等式組。目標(biāo)函數(shù)：欲求最值的關(guān)于x、y的一次解析式。線性目標(biāo)函數(shù)：欲求最值的解析式是關(guān)于x、y的一次解析式。線性規(guī)劃：求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值。可行解：滿足線性約束條件的解（x，y）。

可行域：所有可行解組成的集合。xyox-4y=-3x=1CBＡ3x+5y=25

設(shè)Z＝2ｘ+ｙ,式中變量ｘ、ｙ

滿足下列條件，

求ｚ的最大值和最小值。

3x+5y≤25x-4y≤-3x≥1解線性規(guī)劃問(wèn)題的步驟：

2、在線性目標(biāo)函數(shù)所表示的一組平行線中，用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；

3、通過(guò)解方程組求出最優(yōu)解；

4、作出答案。

1、畫(huà)出線性約束條件所表示的可行域；1、解的概念

⑴可行解：滿足約束條件②、③的解為可行解。所有解的集合為可行解的集或可行域。

⑵最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

⑶基：B是矩陣A中n×n階非奇異子矩陣（∣B∣≠0），則B是一個(gè)基。則稱Pj

(j=12……m)為基向量?！郮j

為基變量。（二）、線性規(guī)劃問(wèn)題的解目標(biāo)函數(shù)：約束條件：①②③2、線性規(guī)劃數(shù)學(xué)模型的一般形式

⑷基本解：滿足條件②，但不滿足條件③的所有解，最多為個(gè)。

⑸基本可行解：滿足非負(fù)約束條件的基本解，簡(jiǎn)稱基本可行解。

⑹可行基：對(duì)應(yīng)于基本可行解的基稱為可行基。非可行解可行解基解基可行解例2.2某地區(qū)有三個(gè)礦山A1，A2，A3，生產(chǎn)同一種礦物。另外有四個(gè)這種礦物消費(fèi)地（鐵廠）B1，B2，B3，B4。各礦山產(chǎn)量及鐵廠的需要量和礦山將礦物運(yùn)到鐵廠的單位運(yùn)價(jià)如表2-2。問(wèn)應(yīng)如何調(diào)運(yùn)，才使總運(yùn)費(fèi)最?。浚ㄒ唬┻\(yùn)輸問(wèn)題的數(shù)學(xué)模型解：該題有兩個(gè)限制條件：一個(gè)是產(chǎn)量，一個(gè)是需量。目標(biāo)是總運(yùn)費(fèi)最省。設(shè)：xij表示從第i個(gè)礦山運(yùn)往第j個(gè)鐵廠的礦物運(yùn)量。這樣得到以下兩組線性方程組：（1）各礦山礦物的生產(chǎn)量與運(yùn)出量平衡方程：（2）各鐵廠礦物供應(yīng)量與需要量平衡方程（3）礦物的運(yùn)輸量應(yīng)非負(fù)

（4）目標(biāo)函數(shù)（二）資源最優(yōu)利用的數(shù)學(xué)模型例2.3某廠生產(chǎn)A、B產(chǎn)品1kg需用資源數(shù)見(jiàn)表2-3，已知生產(chǎn)A1kg價(jià)值7千元，B1kg12千元。應(yīng)該生產(chǎn)A和B產(chǎn)品各多少才能使總價(jià)值最大。解：設(shè)A、B兩產(chǎn)品的計(jì)劃產(chǎn)量為x1、x2則數(shù)學(xué)模型為：

（三）機(jī)床負(fù)荷問(wèn)題的數(shù)學(xué)模型例2.4設(shè)某車間需加工甲、乙兩種零件。這兩種零件可以在三種不同機(jī)床——銑床、六角車床、自動(dòng)機(jī)床上進(jìn)行加工。機(jī)床數(shù)及生產(chǎn)效率如表2-4。（三）機(jī)床負(fù)荷問(wèn)題的數(shù)學(xué)模型

此表說(shuō)明，在一臺(tái)銑床上一個(gè)工作日可以加工15件甲零件或20件乙零件，余類同。該車間共有3臺(tái)銑床，3臺(tái)六角車床，1臺(tái)自動(dòng)機(jī)床。問(wèn)如何合理安排機(jī)床的加工任務(wù)，使得在產(chǎn)品配套比例條件下（設(shè)甲、乙零件1:1配套），使成套產(chǎn)品的數(shù)量達(dá)到最大。解：設(shè)xij表示第i種機(jī)床用來(lái)生產(chǎn)第j種產(chǎn)品的臺(tái)數(shù),則數(shù)學(xué)模型為（1）加工甲、乙產(chǎn)品機(jī)床臺(tái)數(shù)平衡方程：

（2）甲、乙零件配套比例平衡方程：

（3）變量非負(fù)：（4）目標(biāo)函數(shù)求成套產(chǎn)品數(shù)量最大：

（四）人員分配的數(shù)學(xué)模型

例2.5有四件工作，分配給四人，每人能力不同，工作效率也不同如表2-5，規(guī)定每項(xiàng)工作由一個(gè)人擔(dān)任和每個(gè)工人只分配一項(xiàng)工作。問(wèn)應(yīng)分配哪個(gè)人去完成哪項(xiàng)工作可使總效率達(dá)到最大。解：設(shè)xij表示i個(gè)工人分配擔(dān)任第j項(xiàng)工作的情況，并xij取1和0兩個(gè)值，

xij=1，表示第i個(gè)工人分配擔(dān)任第j項(xiàng)工作；

xij=0，表示i個(gè)工人不擔(dān)任第j項(xiàng)工作。

數(shù)學(xué)模型：（1）每個(gè)工人只擔(dān)任一項(xiàng)工作（2）每項(xiàng)工作必由一個(gè)工人擔(dān)任（3）變量取值：

（4）目標(biāo)函數(shù)求總效率最大：

（五）合理配料問(wèn)題的數(shù)學(xué)模型

例2.6某人每日需服A、B兩種維生素，A最少服9個(gè)單位，B最少服19個(gè)單位，現(xiàn)有六種營(yíng)養(yǎng)物每克含A、B維生素的單位數(shù)和每克價(jià)格如表2-6。問(wèn)此人每天要服用這六種營(yíng)養(yǎng)物各多少克，才既能獲得每日最少所需維生素又使花費(fèi)最省。（五）合理配料問(wèn)題的數(shù)學(xué)模型

設(shè)：六種營(yíng)養(yǎng)物分別各服用x1g，x2g，x3g，x4g，x5g，x6g。則數(shù)學(xué)模型：

（六）合理下料問(wèn)題的數(shù)學(xué)模型例2.7某車間有一批長(zhǎng)度為180cm的鋼管，為著制造零件的需要，要將其截成三種不同長(zhǎng)度的管料：70cm、52cm、35cm。規(guī)定這三種管料的需要量分別不少于100根、150根和100根。問(wèn)題是應(yīng)如何下料能使消耗的鋼管數(shù)量最少？解：設(shè)在180cm長(zhǎng)的鋼管上能夠下出U個(gè)70cm的零件，V個(gè)52cm的零件和W個(gè)35cm的零件，則U、V、W個(gè)零件必須符合:70U+52V+35W≤180（六）合理下料問(wèn)題的數(shù)學(xué)模型經(jīng)過(guò)試算，可得8種下料方式，見(jiàn)表：設(shè)：x1、x2、x3、x4、x5、x6、x7、x8分別表示這八種下料方式鋼管消耗的總根數(shù)，則數(shù)學(xué)模型：2、解的基本定理⑴線性規(guī)劃問(wèn)題的可行域是凸集（凸多邊形）。凸集凸集不是凸集頂點(diǎn)⑵最優(yōu)解一定是在凸集的某一頂點(diǎn)實(shí)現(xiàn)（頂點(diǎn)數(shù)目不超過(guò)個(gè)）⑶先找一個(gè)基本可行解，與周圍頂點(diǎn)比較，如不是最大，繼續(xù)比較，直到找出最大為止。3、解的情況唯一解無(wú)窮解無(wú)界解無(wú)可行解有最優(yōu)解無(wú)最優(yōu)解

建立直角坐標(biāo)，圖中陰影部分及邊界上的點(diǎn)均為其解，是由約束條件來(lái)反映的。例一、⑴⑵⑶⑷三、圖解法012345678123456⑴⑵⑶⑷作圖∴最優(yōu)解：x1=4x2=2有唯一最優(yōu)解，Z=14x2

x1(42)⑴⑵⑶⑷例二、例三、⑴⑵⑶無(wú)窮多最優(yōu)解⑴⑵無(wú)界解x1x1x2

x2

⑴⑵x1x2

無(wú)可行解例四、練習(xí)1效產(chǎn)品機(jī)床率

A

B機(jī)床臺(tái)數(shù)

Ⅰ

30

40

40

Ⅱ

55

30

40

Ⅲ

23

37

20

2、

某車間用三種不同型號(hào)的機(jī)床Ⅰ、Ⅱ、Ⅲ，加工A、B兩種零件，機(jī)床臺(tái)數(shù)、生產(chǎn)效率如表所示。問(wèn)如何合理安排機(jī)床的加工任務(wù)，才能使生產(chǎn)的零件總數(shù)最多？1、某工廠生產(chǎn)A1、A2

兩種產(chǎn)品，每件可獲利潤(rùn)15、20元。每個(gè)產(chǎn)品都經(jīng)過(guò)三道工序，資料如表所示。工廠應(yīng)如何安排生產(chǎn)計(jì)劃使獲得的總利潤(rùn)最多？試寫(xiě)出此問(wèn)題的數(shù)學(xué)模型。工產(chǎn)品工序時(shí)

A1

A2可用工時(shí)

Ⅰ

3

2

800

Ⅱ

2

3

800

Ⅲ

1

1

350習(xí)題13、用圖解法求解下面的線性規(guī)劃問(wèn)題：x1x2

123(2)x1x2

123(1)（一）、基本思想將模型的一般形式變成標(biāo)準(zhǔn)形式，再根據(jù)標(biāo)準(zhǔn)型模型，從可行域中找一個(gè)基本可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個(gè)基本可行解，當(dāng)目標(biāo)函數(shù)達(dá)到最大時(shí)，得到最優(yōu)解。（二）、線性規(guī)劃模型的標(biāo)準(zhǔn)形式1、標(biāo)準(zhǔn)形式四、單純形法

2、特征：

⑴.目標(biāo)函數(shù)為求極大值，也可以用求極小值；

⑵.所有約束條件（非負(fù)條件除外）都是等式，右端常數(shù)項(xiàng)為非負(fù)；

⑶.變量為非負(fù)。3、轉(zhuǎn)換方式：

⑴.目標(biāo)函數(shù)的轉(zhuǎn)換如果是求極小值即，則可將目標(biāo)函數(shù)乘以（－1），可化為求極大值問(wèn)題。也就是：令，可得到上式。即⑵.約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量⑶.變量的變換若存在取值無(wú)約束的變量，可令其中：例一、將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式為無(wú)約束（無(wú)非負(fù)限制）

解:

用替換，且，將第3個(gè)約束方程兩邊乘以（－1）將極小值問(wèn)題反號(hào)，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下：引入變量例二、將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型為無(wú)約束解：（三）、單純形法例一、變成標(biāo)準(zhǔn)型約束方程的系數(shù)矩陣為基變量為非基變量I為單位矩陣且線性獨(dú)立Maxz=2x1+3x2

st.x1+x2≤3 x1+2x2≤4 x1,x2≥0

Maxz=2x1+3x2+0x3+0x4

st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T

等。設(shè)B=

1001，令，則|B|=1≠0,令x1=x2=0，則x3=3,x4=4，X=(0,0,3,4)T回顧：x3x4——基變量令B=1110

x1x3

，則令x2=x4=0，則x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解標(biāo)準(zhǔn)化令：則：∴基本可行解為（001281612）

此時(shí)，Z=0然后，找另一個(gè)基本可行解。即將非基變量換入基變量中，但保證其余的非負(fù)。如此循環(huán)下去，直到找到最優(yōu)解為止。注意：為盡快找到最優(yōu)解，在換入變量時(shí)有一定的要求。如將目標(biāo)系數(shù)大的先換入等。找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)目標(biāo)函數(shù)（找更大的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代結(jié)束其步驟總結(jié)如下：當(dāng)時(shí)，為換入變量確定換出變量為換出變量接下來(lái)有下式：用高斯法，將的系數(shù)列向量換為單位列向量，其步驟是：結(jié)果是：代入目標(biāo)函數(shù)：有正系數(shù)表明：還有潛力可挖，沒(méi)有達(dá)到最大值；此時(shí)：令得到另一個(gè)基本可行解

（0，3，6，2，16，0）有負(fù)系數(shù)表明：若要剩余資源發(fā)揮作用，就必須支付附加費(fèi)用。當(dāng)時(shí)，即不再利用這些資源。如此循環(huán)進(jìn)行，直到找到最優(yōu)為止。本例最優(yōu)解為：（4，2，0，0，0，4）（四）、單純形表判定標(biāo)準(zhǔn)：若求

或例題：cj

230000cBxBb

x1x2x3x4x5x60000x3x4x5x61281612

221000120100400010040001-Z0

23000012/28/2－12/4cj

230000cBxBb

x1x2x3x4x5x6000x3x4x516

400010

-Z3x23010001/42620100-1/2100100-1/2cj

230000cBxBb

x1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/4-Z-9

20000-3/46/2216/4－cj

230000cBxBb

x1x2x3x4x5x60203x3x1x5x22283

001-201/210010-1/2000-412010001/44－412-Z-13

000-201/4cj

230000cBxBb

x1x2x3x4x5x60203x6x1x