《及求解線性規(guī)劃模型的應(yīng)用運(yùn)輸問(wèn)題指派問(wèn)題排隊(duì)問(wèn)題課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《及求解線性規(guī)劃模型的應(yīng)用運(yùn)輸問(wèn)題指派問(wèn)題排隊(duì)問(wèn)題課件.ppt（65頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、l管理運(yùn)籌學(xué)管理科學(xué)Operations Research Management science教學(xué)日歷l概述l線性規(guī)劃模型及求解l線性規(guī)劃模型的應(yīng)用l運(yùn)輸問(wèn)題l指派問(wèn)題l排隊(duì)問(wèn)題第一講 管理科學(xué)概述管理科學(xué)發(fā)展簡(jiǎn)史管理科學(xué)的含義管理科學(xué)研究程序管理科學(xué)實(shí)例1.1 管理科學(xué)發(fā)展簡(jiǎn)史“二戰(zhàn)”以前的科學(xué)管理“二戰(zhàn)”以后的管理科學(xué) 軍事運(yùn)籌學(xué) 運(yùn)籌學(xué)管理科學(xué)的誕生1.1.1 二戰(zhàn)以前的科學(xué)管理1850年，“三化”（單一化、標(biāo)準(zhǔn)化和專業(yè)化）1911年，泰勒的科學(xué)管理管理1913年，福特的“流水線生產(chǎn)管理”1.1.2 “二戰(zhàn)”以后的管理科學(xué)v今天，人們所說(shuō)的今天，人們所說(shuō)的“管理科學(xué)管理科學(xué)”產(chǎn)生于產(chǎn)生

2、于2020世紀(jì)世紀(jì)4040、5050年代，稱之為現(xiàn)代管理科學(xué)。年代，稱之為現(xiàn)代管理科學(xué)。v現(xiàn)代管理科學(xué)的思想與二戰(zhàn)以前的管理科學(xué)思想應(yīng)該說(shuō)現(xiàn)代管理科學(xué)的思想與二戰(zhàn)以前的管理科學(xué)思想應(yīng)該說(shuō)同屬一個(gè)思想體系，但前者決不是后者的簡(jiǎn)單延伸，而同屬一個(gè)思想體系，但前者決不是后者的簡(jiǎn)單延伸，而是在思維方式、技術(shù)手段方面帶有許許多多質(zhì)的變化。是在思維方式、技術(shù)手段方面帶有許許多多質(zhì)的變化。vv從數(shù)量角度研究和分析管理活動(dòng)中存在的各種各樣問(wèn)題。從數(shù)量角度研究和分析管理活動(dòng)中存在的各種各樣問(wèn)題。vv是一門決策性質(zhì)的科學(xué)。是一門決策性質(zhì)的科學(xué)?！肮芾砭褪菦Q策管理就是決策”，管理科學(xué)的基，管理科學(xué)的基本任務(wù)就是，在

3、一定的資源約束條件下，對(duì)可能存在的各種本任務(wù)就是，在一定的資源約束條件下，對(duì)可能存在的各種方案進(jìn)行選擇，以確定出最好的行動(dòng)方案。方案進(jìn)行選擇，以確定出最好的行動(dòng)方案。vv廣泛使用各門學(xué)科中的科學(xué)方法和技術(shù)，尤其是數(shù)學(xué)、統(tǒng)計(jì)廣泛使用各門學(xué)科中的科學(xué)方法和技術(shù)，尤其是數(shù)學(xué)、統(tǒng)計(jì)學(xué)、系統(tǒng)科學(xué)、控制論、決策科學(xué)等學(xué)科的方法。學(xué)、系統(tǒng)科學(xué)、控制論、決策科學(xué)等學(xué)科的方法。vv以計(jì)算機(jī)為輔助手段，進(jìn)行各項(xiàng)管理活動(dòng)。以計(jì)算機(jī)為輔助手段，進(jìn)行各項(xiàng)管理活動(dòng)。1.1.3 “軍事運(yùn)籌學(xué)”1938年英國(guó)最早出現(xiàn)了軍事運(yùn)籌學(xué)，命名為“Operational Research”,1942年，美國(guó)從事這方面工作的科學(xué)家命其名

4、為“Operations Research”這個(gè)名字一直延用至今。v英國(guó)雷達(dá)站與防空作戰(zhàn)系統(tǒng)的協(xié)調(diào)英國(guó)雷達(dá)站與防空作戰(zhàn)系統(tǒng)的協(xié)調(diào)v深水炸彈爆炸深度深水炸彈爆炸深度v巧妙避開(kāi)德軍潛艇巧妙避開(kāi)德軍潛艇v諾曼底登陸戰(zhàn)役諾曼底登陸戰(zhàn)役深水炸彈爆炸深度 二戰(zhàn)期間英軍船隊(duì)在大西洋里航行時(shí)經(jīng)常受到德軍二戰(zhàn)期間英軍船隊(duì)在大西洋里航行時(shí)經(jīng)常受到德軍潛艇的攻擊。為此，英國(guó)空軍經(jīng)常派出轟炸機(jī)對(duì)德潛艇的攻擊。為此，英國(guó)空軍經(jīng)常派出轟炸機(jī)對(duì)德軍潛艇實(shí)施火力打擊，但轟炸效果總是不理想，對(duì)軍潛艇實(shí)施火力打擊，但轟炸效果總是不理想，對(duì)潛艇幾乎構(gòu)不成威脅。英軍請(qǐng)來(lái)一些數(shù)學(xué)家專門研潛艇幾乎構(gòu)不成威脅。英軍請(qǐng)來(lái)一些數(shù)學(xué)家專門研究這

5、一問(wèn)題，結(jié)果發(fā)現(xiàn)，潛艇從發(fā)現(xiàn)英軍飛機(jī)開(kāi)始究這一問(wèn)題，結(jié)果發(fā)現(xiàn)，潛艇從發(fā)現(xiàn)英軍飛機(jī)開(kāi)始下潛到深水炸彈爆炸時(shí)止，只下潛了下潛到深水炸彈爆炸時(shí)止，只下潛了7.67.6米，而英軍米，而英軍飛機(jī)投下的炸彈卻已下沉到飛機(jī)投下的炸彈卻已下沉到2121米處爆炸，從而導(dǎo)致米處爆炸，從而導(dǎo)致毀傷效果低下。經(jīng)過(guò)科學(xué)論證，英軍果斷調(diào)整了深毀傷效果低下。經(jīng)過(guò)科學(xué)論證，英軍果斷調(diào)整了深水炸彈的引信，爆炸深度從水下水炸彈的引信，爆炸深度從水下2121米減為水下米減為水下9.19.1米，米，結(jié)果轟炸效果較過(guò)去提高了結(jié)果轟炸效果較過(guò)去提高了4 4倍。德軍還誤以為英軍倍。德軍還誤以為英軍發(fā)明了新式炸彈。發(fā)明了新式炸彈。巧妙避開(kāi)德

6、軍潛艇19431943年以前，在大西洋上英美運(yùn)輸船隊(duì)常常受到德國(guó)年以前，在大西洋上英美運(yùn)輸船隊(duì)常常受到德國(guó)潛艇的襲擊，當(dāng)時(shí)，英美兩國(guó)海軍實(shí)力有限，一時(shí)間，潛艇的襲擊，當(dāng)時(shí)，英美兩國(guó)海軍實(shí)力有限，一時(shí)間，德軍的潛艇戰(zhàn)搞得盟軍焦頭爛額。為此，一位美國(guó)海德軍的潛艇戰(zhàn)搞得盟軍焦頭爛額。為此，一位美國(guó)海軍將領(lǐng)專門去請(qǐng)教了幾位數(shù)學(xué)家。數(shù)學(xué)家們運(yùn)用概率軍將領(lǐng)專門去請(qǐng)教了幾位數(shù)學(xué)家。數(shù)學(xué)家們運(yùn)用概率分析后發(fā)現(xiàn)，艦隊(duì)與敵潛艇相遇是一個(gè)隨機(jī)事件。從分析后發(fā)現(xiàn)，艦隊(duì)與敵潛艇相遇是一個(gè)隨機(jī)事件。從數(shù)學(xué)角度來(lái)看這一問(wèn)題，它具有一定的規(guī)律：一定數(shù)數(shù)學(xué)角度來(lái)看這一問(wèn)題，它具有一定的規(guī)律：一定數(shù)量的船編次越多與敵人相遇的概率

7、就越大。美國(guó)海軍量的船編次越多與敵人相遇的概率就越大。美國(guó)海軍接受了數(shù)學(xué)家的建議，命令艦隊(duì)在指定海域集合，再接受了數(shù)學(xué)家的建議，命令艦隊(duì)在指定海域集合，再集體通過(guò)危險(xiǎn)海域，然后各自駛向預(yù)定港口。結(jié)果盟集體通過(guò)危險(xiǎn)海域，然后各自駛向預(yù)定港口。結(jié)果盟軍艦隊(duì)遭襲被擊沉的概率下降，大大減少了損失。軍艦隊(duì)遭襲被擊沉的概率下降，大大減少了損失。1.1.4 運(yùn)籌學(xué)管理科學(xué)的誕生以數(shù)學(xué)（計(jì)算機(jī)）作為工具，通過(guò)定量分析進(jìn)行決策的方法在二戰(zhàn)中取得重大的收獲，二戰(zhàn)結(jié)束后，OR的研究和應(yīng)用從軍事領(lǐng)域迅速擴(kuò)展到社會(huì)和經(jīng)濟(jì)領(lǐng)域，理論體系不斷的發(fā)展和完善。1950年，英伯明翰大學(xué)開(kāi)設(shè)運(yùn)籌學(xué)課程；1951年，美專家出版運(yùn)籌學(xué)

8、方法專著；運(yùn)籌學(xué)研究期刊雜志的創(chuàng)刊以及出版；電子計(jì)算機(jī)的應(yīng)用；1.2 管理科學(xué)的含義從字面上看，管理科學(xué)包含二個(gè)方面的意思，即管理和從字面上看，管理科學(xué)包含二個(gè)方面的意思，即管理和科學(xué)，或者確切一點(diǎn)說(shuō)，就是科學(xué)，或者確切一點(diǎn)說(shuō)，就是管理的科學(xué)管理的科學(xué)。到目前為止，人們對(duì)管理科學(xué)及作用已有了明確的認(rèn)識(shí)，到目前為止，人們對(duì)管理科學(xué)及作用已有了明確的認(rèn)識(shí)，但對(duì)如何定義管理科學(xué)卻仍然眾說(shuō)紛紜。但對(duì)如何定義管理科學(xué)卻仍然眾說(shuō)紛紜。所謂管理科學(xué)是指，所謂管理科學(xué)是指，對(duì)與定量因素有關(guān)的管理問(wèn)題通過(guò)對(duì)與定量因素有關(guān)的管理問(wèn)題通過(guò)對(duì)與定量因素有關(guān)的管理問(wèn)題通過(guò)對(duì)與定量因素有關(guān)的管理問(wèn)題通過(guò)使用科學(xué)的手段和方

9、法（尤其是數(shù)學(xué)學(xué)科方法）進(jìn)行科使用科學(xué)的手段和方法（尤其是數(shù)學(xué)學(xué)科方法）進(jìn)行科使用科學(xué)的手段和方法（尤其是數(shù)學(xué)學(xué)科方法）進(jìn)行科使用科學(xué)的手段和方法（尤其是數(shù)學(xué)學(xué)科方法）進(jìn)行科學(xué)決策的一門科學(xué)。學(xué)決策的一門科學(xué)。學(xué)決策的一門科學(xué)。學(xué)決策的一門科學(xué)。研究如何使用研究如何使用以以定量定量為主的分析方法和技術(shù)為主的分析方法和技術(shù)來(lái)獲得科學(xué)來(lái)獲得科學(xué)的決策。的決策。模型模型是對(duì)現(xiàn)實(shí)問(wèn)題的一種描述和表述，數(shù)學(xué)模型（定量模型）則是現(xiàn)實(shí)問(wèn)題的要素以及要素之間數(shù)量關(guān)系的數(shù)學(xué)表達(dá)。是定量分析的基礎(chǔ)。模型的精度：根據(jù)模型預(yù)測(cè)的值與實(shí)際值的接近程度1.3 管理科學(xué)的研究程序1、識(shí)別和定義問(wèn)題2、搜集數(shù)據(jù)資料3、建立分

10、析模型（一般是數(shù)學(xué)模型）4、建立對(duì)模型進(jìn)行求解的計(jì)算機(jī)程序5、測(cè)試和修正模型6、應(yīng)用模型分析問(wèn)題并提出管理建議7、幫助實(shí)施決策方案1.4 管理科學(xué)例子1車間車間單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）每周可以獲每周可以獲得的生產(chǎn)時(shí)得的生產(chǎn)時(shí)間（小時(shí)）間（小時(shí)）門門窗窗1 11 10 04 42 20 02 212123 33 32 21818利潤(rùn)（元利潤(rùn)（元/單位）單位）300300500500某工廠擁有有3個(gè)車間生產(chǎn)門、窗兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占有的車間加工時(shí)數(shù)以及每件產(chǎn)品可以獲得的利潤(rùn)以及3個(gè)車間每周可供加工時(shí)數(shù)如下表所示：求使得總利潤(rùn)最大的生產(chǎn)計(jì)劃。1.確定決策變量：

11、設(shè)門、窗2種產(chǎn)品每周的產(chǎn)量分別為x1，x22.確定限制條件：車間1時(shí)間限制：1x1+0 x24 車間2時(shí)間限制：0 x1+2x212 車間3時(shí)間限制：3x1+2x218 決策變量限制：x1,x203.確定決策目標(biāo)：設(shè)總利潤(rùn)為z，即：Max z=300 x1+500 x2車間車間單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）每周可以獲每周可以獲得的生產(chǎn)時(shí)得的生產(chǎn)時(shí)間（小時(shí)）間（小時(shí)）門門窗窗1 11 10 04 42 20 02 212123 33 32 21818利潤(rùn)（元利潤(rùn)（元/單位）單位）300300500500目標(biāo)函數(shù)約束條件變量非負(fù)約束張、王、李、趙四位老師被分配教語(yǔ)文、數(shù)學(xué)、物

12、理化學(xué)四門課程，每位老師教一門課，每門課由一位老師教。根據(jù)這四位老師以往教課的情況，他們分別教四這門課程的平均成績(jī)?nèi)缦卤?。要求確定哪一位老師上哪一門課，使四門課的平均總成績(jī)最高。語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理化學(xué)化學(xué)張張9292686885857676王王8282919177776363李李8383909074746565趙趙93936161838375751.4 管理科學(xué)例子2設(shè)：語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理化學(xué)化學(xué)張張x x1111x x1212x x1313x x1414王王x x2121x x2222x x2323x x2424李李x x3131x x3232x x3333x x3434趙趙x

13、x4141x x4242x x4343x x4444max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t.x11+x12+x13+x14=1 (1)x21+x22+x23+x24=1 (2)x31+x32+x33+x34=1 (3)x41+x42+x43+x44=1 (4)x11+x21+x31+x41=1 (5)x12+x22+x32+x42=1 (6)x13+x23+x33+x43=1 (7)x14+x24+x34+x44=1 (8)

14、xij=0,1最優(yōu)解為：x14=1，x23=1，x32=1，x41=1，max z=336即張老師教化學(xué)，王老師教語(yǔ)文，李老師教數(shù)學(xué)，趙老師教語(yǔ)文。語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理化學(xué)化學(xué)張張0 00 00 01 1王王0 00 01 10 0李李0 01 10 00 0趙趙1 10 00 00 0語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理化學(xué)化學(xué)張張9292686885857676王王8282919177776363李李8383909074746565趙趙9393616183837575四門課的總分可以達(dá)到336分。第二講 線性規(guī)劃模型p線性規(guī)劃問(wèn)題p線性規(guī)劃模型p線性規(guī)劃的圖解法線性規(guī)劃問(wèn)題n生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品組合優(yōu)

15、化問(wèn)題n配料問(wèn)題n背包問(wèn)題n運(yùn)輸問(wèn)題n指派問(wèn)題1.生產(chǎn)計(jì)劃問(wèn)題1（Production Planning）產(chǎn)品甲產(chǎn)品甲產(chǎn)品乙產(chǎn)品乙產(chǎn)品丙產(chǎn)品丙資源限制資源限制設(shè)備臺(tái)時(shí)設(shè)備臺(tái)時(shí)1 12 23 330003000臺(tái)時(shí)臺(tái)時(shí)原料原料A A6 65 54 440004000千克千克原料原料B B0 07 78 825002500千克千克利潤(rùn)（元利潤(rùn)（元/單位）單位）50050080080010001000某工廠擁有原料A、B以及生產(chǎn)設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占有的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示：求使得總利潤(rùn)最大的生產(chǎn)計(jì)劃。1.確定決策變量

16、：設(shè)甲乙丙三種產(chǎn)品的產(chǎn)量分別為x1，x2，x3產(chǎn)品甲產(chǎn)品甲產(chǎn)品乙產(chǎn)品乙產(chǎn)品丙產(chǎn)品丙資源限制資源限制設(shè)備臺(tái)時(shí)設(shè)備臺(tái)時(shí)1 12 23 330003000臺(tái)時(shí)臺(tái)時(shí)原料原料A A6 65 54 440004000千克千克原料原料B B0 07 78 825002500千克千克利潤(rùn)（元利潤(rùn)（元/單位）單位）500500800800100010002.確定限制條件：臺(tái)時(shí)限制：1x1+2x2+3x33000 原料原料A A 限制：6x1+5x2+4x34000 原料原料B B 限制：0 x1+7x2+8x32500 決策變量限制：x1,x2,x303.確定決策目標(biāo)：設(shè)總利潤(rùn)為z，即：Max z=500 x1

17、+800 x2+1000 x3產(chǎn)品甲產(chǎn)品甲產(chǎn)品乙產(chǎn)品乙產(chǎn)品丙產(chǎn)品丙資源限制資源限制設(shè)備臺(tái)時(shí)設(shè)備臺(tái)時(shí)1 12 23 330003000臺(tái)時(shí)臺(tái)時(shí)原料原料A A6 65 54 440004000千克千克原料原料B B0 07 78 825002500千克千克利潤(rùn)（元利潤(rùn)（元/單位）單位）50050080080010001000設(shè)三種產(chǎn)品的產(chǎn)量分別為x1，x2，x3，總利潤(rùn)為z，線性規(guī)劃模型為：max z=500 x1+800 x2+1000 x3s.t.1x1+2x2+3x33000 6x1+5x2+4x34000 0 x1+7x2+8x32500 x1,x2,x30目標(biāo)函數(shù)約束條件變量非負(fù)約束這個(gè)

18、問(wèn)題的最優(yōu)解為：x1=458.3件，x2=0單位，x3=312.5單位最大利潤(rùn)為：z=541666.7元。問(wèn)題：三個(gè)約束條件可以改為等式嗎？1.生產(chǎn)計(jì)劃問(wèn)題2（Production Planning）產(chǎn)品甲產(chǎn)品甲產(chǎn)品乙產(chǎn)品乙產(chǎn)品丙產(chǎn)品丙產(chǎn)品丁產(chǎn)品丁設(shè)備能力設(shè)備能力（小時(shí)）（小時(shí)）設(shè)備設(shè)備A A1.51.51.01.02.42.41.01.020002000設(shè)備設(shè)備B B1.01.05.05.01.01.03.53.580008000設(shè)備設(shè)備C C1.51.53.03.03.53.51.01.050005000利潤(rùn)（元利潤(rùn)（元/件）件）5.245.247.307.308.348.344.184.

19、18某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占有的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示：求使得總利潤(rùn)最大的生產(chǎn)計(jì)劃。產(chǎn)品甲產(chǎn)品甲產(chǎn)品乙產(chǎn)品乙產(chǎn)品丙產(chǎn)品丙產(chǎn)品丁產(chǎn)品丁設(shè)備能力設(shè)備能力（小時(shí)）（小時(shí)）設(shè)備設(shè)備A A1.51.51.01.02.42.41.01.020002000設(shè)備設(shè)備B B1.01.05.05.01.01.03.53.580008000設(shè)備設(shè)備C C1.51.53.03.03.53.51.01.050005000利潤(rùn)（元利潤(rùn)（元/件）件）5.245.247.307.308.348.344.184.18設(shè)四

20、種產(chǎn)品的產(chǎn)量分別為x1，x2，x3，x4，總利潤(rùn)為z，線性規(guī)劃模型為：max z=5.24x1+7.30 x2+8.34x3+4.18x4s.t.1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1+3.0 x2+3.5x3+1.0 x45000 x1,x2,x3,x40目標(biāo)函數(shù)約束條件變量非負(fù)約束這個(gè)問(wèn)題的最優(yōu)解為：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利潤(rùn)為：z=12737.06元。問(wèn)題：三個(gè)約束條件可以改為等式嗎？2.配料問(wèn)題（Material Blending）某工廠要用四

21、種合金T1、T2、T3、T4為原料，經(jīng)熔煉成為新的不銹鋼G。這四種原料含鉻（Cr）、錳（Mn）和鎳（Ni）的含量（），這四種原料的單價(jià)以及新的不銹鋼G所要求的Cr、Mn、Ni的最低含量（）如下表：T T1 1T T2 2T T3 3T T4 4GGCrCr3.213.214.534.532.192.191.761.763.203.20MnMn2.042.041.121.123.573.574.334.332.102.10NiNi5.825.823.063.064.274.272.732.734.304.30單價(jià)（元單價(jià)（元/公斤）公斤）115115979782827676要求配100公斤不銹鋼

22、G，并假定在配制過(guò)程中沒(méi)有損耗。求使得總成本最低的配料方案。T T1 1T T2 2T T3 3T T4 4GGCrCr3.213.214.534.532.192.191.761.763.203.20MnMn2.042.041.121.123.573.574.334.332.102.10NiNi5.825.823.063.064.274.272.732.734.304.30單價(jià)（元單價(jià)（元/公斤）公斤）115115979782827676min z=115x1+97x2+82x3+76x4s.t.0.0321x1+0.0453x2+0.0219x3+0.0176x43.20 Cr的含量下限約束

23、 0.0204x1+0.0112x2+0.0357x3+0.0433x42.10 Mn的含量下限約束 0.0582x1+0.0306x2+0.0427x3+0.0273x44.30 Ni的含量下限約束 x1+x2+x3+x4=100 物料平衡約束 x1,x2,x3,x40設(shè)四種原料分別選取x1，x2，x3，x4公斤，總成本為z。這個(gè)問(wèn)題的最優(yōu)解為：x1=26.58,x2=31.57,x3=41.84，x4=0（公斤）,最低成本為z=9549.87元。問(wèn)題：如果某一種成分的含量既有下限，又有上限怎么辦？3.背包問(wèn)題（Knapsack Problem）一只背包最大裝載重量為50公斤?，F(xiàn)有三種物品，

24、每種物品數(shù)量無(wú)限。每種物品每件的重量、價(jià)格如下表：物品物品1 1物品物品2 2物品物品3 3重量（公斤重量（公斤/件）件）101041412020價(jià)值（元價(jià)值（元/件）件）171772723535求背包中裝入每種物品各多少件，使背包中物品總價(jià)值最高。設(shè)三種物品的件數(shù)各為x1，x2，x3件，總價(jià)值為z。max z=17x1+72x2+35x3s.t.10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3為整數(shù)這是一個(gè)整數(shù)規(guī)劃問(wèn)題（Integer Programming）。這個(gè)問(wèn)題的最優(yōu)解為：x1=1件，x2=0件，x3=2件，最高價(jià)值z(mì)=87元物品物品1 1物品物品2 2物品

25、物品3 3重量（公斤重量（公斤/件）件）101041412020價(jià)值（元價(jià)值（元/件）件）1717727235354.運(yùn)輸問(wèn)題（Transportation）某種物資從兩個(gè)供應(yīng)地A1，A2運(yùn)往三個(gè)需求地B1，B2，B3。各供應(yīng)地的供應(yīng)量、各需求地的需求量、每個(gè)供應(yīng)地到每個(gè)需求地每噸物資的運(yùn)輸價(jià)格如下表：運(yùn)價(jià)（元運(yùn)價(jià)（元/噸）噸）B B1 1B B2 2B B3 3供應(yīng)量（噸）供應(yīng)量（噸）A A1 12 23 35 53535A A2 24 47 78 82525需求量（噸）需求量（噸）1010303020206060求總運(yùn)費(fèi)最低的運(yùn)輸方案。運(yùn)價(jià)運(yùn)價(jià)（元（元/噸）噸）B B1 1B B2 2B

26、B3 3供應(yīng)量供應(yīng)量（噸）（噸）A A1 12 23 35 53535A A2 24 47 78 82525需求量（噸）需求量（噸）1010303020206060A1A2B3B2B135噸25噸10噸30噸20噸235478運(yùn)價(jià)運(yùn)價(jià)（元（元/噸）噸）B B1 1B B2 2B B3 3供應(yīng)量供應(yīng)量（噸）（噸）A A1 12 23 35 53535A A2 24 47 78 82525需求量（噸）需求量（噸）1010303020206060設(shè)從兩個(gè)供應(yīng)地到三個(gè)需求地的運(yùn)量（噸）如下表：B B1 1B B2 2B B3 3A A1 1x x1111x x1212x x1313A A2 2x x2

27、121x x2222x x2323運(yùn)價(jià)運(yùn)價(jià)（元（元/噸）噸）B B1 1B B2 2B B3 3供應(yīng)量供應(yīng)量（噸）（噸）A A1 12 23 35 53535A A2 24 47 78 82525需求量（噸）需求量（噸）1010303020206060min z=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13 =35 供應(yīng)地A1 x21+x22+x23=25 供應(yīng)地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23=20 需求地B3 x11,x12,x13,x21,x22,x230 運(yùn)量（噸）運(yùn)量（噸）B

28、 B1 1B B2 2B B3 3供應(yīng)量（噸）供應(yīng)量（噸）A A1 130305 53535A A2 2101015152525需求量（噸）需求量（噸）1010303020206060這個(gè)問(wèn)題的最優(yōu)解表示如下：最小總運(yùn)費(fèi)為：z=330+55+410+815=275元A1A2B3B2B135噸25噸10噸30噸20噸23547830噸5噸10噸15噸5.指派問(wèn)題（Assignment Problem）有n項(xiàng)任務(wù)由n個(gè)人完成，每項(xiàng)任務(wù)交給一個(gè)人，每人都有一項(xiàng)任務(wù)。由i個(gè)人完成j項(xiàng)任務(wù)的成本（或效益）為cij。求使總成本最?。ɑ蚩傂б孀畲螅┑姆峙浞桨?。設(shè)：張、王、李、趙四位老師被分配教語(yǔ)文、數(shù)學(xué)、物

29、理化學(xué)四門課程，每位老師教一門課，每門課由一位老師教。根據(jù)這四位老師以往教課的情況，他們分別教四這門課程的平均成績(jī)?nèi)缦卤?。要求確定哪一位老師上哪一門課，使四門課的平均總成績(jī)最高。語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理化學(xué)化學(xué)張張9292686885857676王王8282919177776363李李8383909074746565趙趙9393616183837575設(shè)：語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理化學(xué)化學(xué)張張x x1111x x1212x x1313x x1414王王x x2121x x2222x x2323x x2424李李x x3131x x3232x x3333x x3434趙趙x x4141x x424

30、2x x4343x x4444max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t.x11+x12+x13+x14=1 (1)x21+x22+x23+x24=1 (2)x31+x32+x33+x34=1 (3)x41+x42+x43+x44=1 (4)x11+x21+x31+x41=1 (5)x12+x22+x32+x42=1 (6)x13+x23+x33+x43=1 (7)x14+x24+x34+x44=1 (8)xij=0,1最優(yōu)解為

31、：x14=1，x23=1，x32=1，x41=1，max z=336即張老師教化學(xué)，王老師教語(yǔ)文，李老師教數(shù)學(xué)，趙老師教語(yǔ)文。語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理化學(xué)化學(xué)張張0 00 00 01 1王王0 00 01 10 0李李0 01 10 00 0趙趙1 10 00 00 0語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理化學(xué)化學(xué)張張9292686885857676王王8282919177776363李李8383909074746565趙趙9393616183837575四門課的總分可以達(dá)到336分。線性規(guī)劃模型min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn (,)b1 a21x

32、1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn (,)bm x1,x2,xn 0(,Free)線性規(guī)劃模型的目標(biāo)函數(shù)必須是變量的線性函數(shù)，約束條件必須是變量的線性等式或不等式。如右的問(wèn)題就不是線性規(guī)劃問(wèn)題：線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)為極小(大)化，約束條件全部為等號(hào)約束，所有變量全部是非負(fù)的，這樣的線性規(guī)劃模型稱為標(biāo)準(zhǔn)形式Min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 線性規(guī)劃模型用矩陣和向量表示Min(max)

33、z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 線性規(guī)劃模型用矩陣和向量表示（續(xù)）因此，線性規(guī)劃模型可以寫成如下矩陣和向量的形式線性規(guī)劃模型總結(jié)線性規(guī)劃模型的結(jié)構(gòu)n目標(biāo)函數(shù)：max，minn約束條件：,=,n變量符號(hào)：0,0,Free線性規(guī)劃的標(biāo)準(zhǔn)形式n目標(biāo)函數(shù)：Min(max)n約束條件：=n變量符號(hào)：0線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化n極大化目標(biāo)函數(shù)轉(zhuǎn)化為極小化n小于等于約束條件轉(zhuǎn)化為等號(hào)約束n大于等于約束條件轉(zhuǎn)化為等號(hào)約束n變量沒(méi)有符號(hào)限制（Free）的標(biāo)準(zhǔn)化n變量小于等于0的標(biāo)準(zhǔn)化 max z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目標(biāo)函數(shù) min z=-2x1+3x2-x3取得極小化的最優(yōu)解時(shí)，這個(gè)最優(yōu)解同時(shí)使原目標(biāo)函數(shù)值取得最