《運(yùn)籌學(xué)》知識點(diǎn)全總結(jié)

1、一、線性規(guī)劃：基本概念1、下面的表格總結(jié)了兩種產(chǎn)品a 和 b 的關(guān)鍵信息以與生產(chǎn)所需的資源q, r, s：滿足所有線性規(guī)劃假設(shè)。（1）在電子表格上為這一問題建立線性規(guī)劃模型；（2）用代數(shù)方法建立一個相同的模型；（3）用圖解法求解這個模型。5、普里默（ primo）保險公司引入了兩種新產(chǎn)品：特殊風(fēng)險保險和抵押。每單位特殊風(fēng)險保險的利潤是5 美元，每單位抵押是2 美元。管理層希望確定新產(chǎn)品的銷售量使得總期望利潤最大。工作的要求如下：（1）為這個問題在電子表格上建立一個線性規(guī)劃模型并求解。（2）用代數(shù)形式建立相同的模型。8、拉爾夫艾德蒙（ralph edmund）喜歡吃牛排和土豆，因此他決定將這兩種

2、食品作為正餐的全部（加上一些飲料和補(bǔ)充維生素的食品）。 拉爾夫意識到這不是最健康的膳食結(jié)構(gòu)，因此他想要確定兩種食品的食用量多少是合適的，以滿足一些主要營養(yǎng)的需求。他獲得了以下營養(yǎng)和成本的信息：拉爾夫想確定牛排和土豆所需要的份數(shù)（可能是小數(shù)），以最低的成本滿足這些需求。（1）為這個問題在電子表格上建立一個線性規(guī)劃模型并求解。（2）用代數(shù)形式建立相同的模型；（3）用圖解法求解這個模型。二、線性規(guī)劃的what-if分析1 公司的產(chǎn)品之一是一種新式玩具，該產(chǎn)品的估計(jì)單位利潤為3 美元。因?yàn)樵摦a(chǎn)品具有極大的需求，公司決定增加該產(chǎn)品原來每天1000 件的生產(chǎn)量。但是從賣主那里可以購得的玩具配件（a,b ）

3、是有限的。每一玩具需要兩個 a 類配件， 而賣主只能將其供應(yīng)量從現(xiàn)在的每天2000 增加到 3000。同時，每一玩具需要一個b 類的配件，資源每單位產(chǎn)品資源使用量可用資源產(chǎn)品 a 產(chǎn)品 b q r s 2 1 3 1 2 3 2 2 4 利潤 /單位3000 美元2000 美元部門每單位工時可使用工時特殊風(fēng)險抵押承保管理索賠3 0 2 2 1 0 2400 800 1200 成分每份各種成分的克數(shù)每天需要量（克）牛排土豆碳水化合物蛋白質(zhì)脂肪5 20 15 15 5 2 50 40 60 每份成本4 美元2 美元但賣主卻無法增加目前每天1000 的供應(yīng)量。因?yàn)槟壳盁o法找到新的供貨商，所以公司決定

4、自己開發(fā)一條生產(chǎn)線，在公司內(nèi)部生產(chǎn)玩具配件a 和 b。據(jù)估計(jì)，公司自己生產(chǎn)的成本將會比從賣主那里購買增加2.5 美元每件（ a,b ） 。管理層希望能夠確定玩具以與兩種配件的生產(chǎn)組合以取得最大的利潤。將該問題視為資源分配問題，公司的一位管理者為該問題建立如下的參數(shù)表：（1）為該問題建立電子表格模型并求解。（2）因?yàn)閮深惢顒拥膯挝焕麧櫴枪烙?jì)的，所以管理層希望能夠知道，為了保持最優(yōu)解不變，估計(jì)值允許的變動 x 圍。針對第一個活動（生產(chǎn)玩具），運(yùn)用電子表格，求出該活動單位利潤從2 美元增加到4 美元每次增加 50 美分時問題的最優(yōu)解和總利潤。在最優(yōu)解不變的前提下，單位利潤可以偏離其初值3 美元多少？

5、（3）針對第二個活動（生產(chǎn)配件），重復(fù)（ 2）的分析，該活動的單位利潤從-3.5 美元增加到 -1.5 美元（第一種活動的單位利潤固定在3 美元） 。（4）運(yùn)用 excel 靈敏度報(bào)告來找到每個活動單位利潤的允許變動x 圍。（5）運(yùn)用 excel 靈敏度報(bào)告來描述在最優(yōu)解不變的前提下，兩個活動單位利潤最多同時能改變多少。4、k&l公司為其冰激凌經(jīng)營店供應(yīng)三種口味的冰激凌：巧克力、香草和香蕉。因?yàn)樘鞖庋谉?，對冰激凌的需求大增，而公司庫存的原料已?jīng)不夠了。計(jì)這些原料分別為：牛奶、糖和奶油。公司無法完成接收的訂單，但是為了在資源有限的條件下使利潤最大化，公司需要確定各種口味產(chǎn)品的最優(yōu)組合。巧

6、克力、 香草和香蕉三種口味的冰激凌的銷售利潤分別為每加侖1.00 美元、 0.90 美元和 0.95 美元。 公司現(xiàn)在有 200 加侖牛奶、 150 磅糖和 60 加侖奶油的庫存。這一問題代數(shù)形式的線性規(guī)劃表示如下：假設(shè)： c=巧克力冰激凌的產(chǎn)量（加侖），v= 香草冰激凌的產(chǎn)量（加侖），b=香蕉冰激凌的產(chǎn)量（加侖）最大化：利潤=1.00c+0.90v+0.95v 約束條件牛奶： 0.45c+0.50v+0.40b 200（加侖）糖：0.50c+0.40v+0.40b 50 （加侖）奶油： 0.10c+0.15v+0.20b 60 （加侖）且c 0，v 0，b 0 使用 excel 求解，求解后

7、的電子表格和靈敏度報(bào)告如下圖所示（注意，因?yàn)樵冢?）中將會討論牛奶約束，所以該部分在下面的圖中隱去了）。不用 excel 重新求解，盡可能詳盡地回答下列問題，注意，各個部分是互不干擾、相互獨(dú)立的。a b c d e f g 1 巧克力香草香蕉2 單位利潤1.00 0.90 0.95 3 4 原料每加侖冰激凌所用原料所需原料可用原料5 牛奶0.45 0.5 0.4 180 200 6 糖0.5 0.4 0.4 150 150 7 奶油0.1 0.15 0.2 60 60 8 9 巧克力香草香蕉總利潤10 每加侖0 300 75 341.25 資源每種活動的單位資源使用量可獲得的資源總量生產(chǎn)玩具生

8、產(chǎn)配件配件 a 配件 b 2 1 -1 -1 3000 1000 單位利潤3 美元-2.5 美元可調(diào)單元格單元格名稱最終價值成本削減目標(biāo)系數(shù)增加上限降低下限$c$10 每加侖巧克力用量0 -0.0375 1 0.0375 1e+30 $d$10 每加侖香草用量300 0 0.9 0.05 0.0125 $e$10 每加侖香蕉用量75 0 0.95 0.0214 0.05 約束單元格名稱最終價值影子價格右端值增加上限降低下限$f$5 所用牛奶量$f$6 所用糖量150 1.875 150 10 30 $f$7 所用奶油量60 1 60 15 3.75 （1）最優(yōu)解和總利潤是多少？（2）假設(shè)香蕉冰

9、激凌每加侖的利潤變?yōu)?.00 美元，最優(yōu)解是否改變，對總利潤又會產(chǎn)生怎樣的影響？（3）假設(shè)香蕉冰激凌每加侖的利潤變?yōu)?2 美分，最優(yōu)解是否改變，對總利潤又會產(chǎn)生怎樣的影響？（4） 公司發(fā)現(xiàn)有3 加侖的庫存奶油已經(jīng)變質(zhì)，只能扔掉， 最優(yōu)解是否改變， 對總利潤又會產(chǎn)生怎樣的影響？（5）假設(shè)公司有機(jī)會購得15 磅糖，總成本15 美元，公司是否應(yīng)該購買這批糖，為什么？（6）在靈敏度報(bào)告中加入牛奶的約束，并解釋如何減少各種產(chǎn)品的產(chǎn)量？5、大衛(wèi)、萊蒂娜和莉迪亞是一家生產(chǎn)鐘表的公司業(yè)主以與員工，大衛(wèi)、萊蒂娜每周最多工作40 個小時，而莉迪亞每周最多能工作20 個小時。該公司生產(chǎn)兩種不同的鐘表：落地?cái)[鐘和墻鐘

10、。大衛(wèi)是機(jī)械工程師，負(fù)責(zé)裝配鐘表內(nèi)部的機(jī)械部件；而萊蒂娜是木工，負(fù)責(zé)木質(zhì)外殼的手工加工；莉迪亞負(fù)責(zé)接收訂單和送貨。每一項(xiàng)工作所需時間如下表所示：每生產(chǎn)并銷售一個落地?cái)[鐘產(chǎn)生的利潤是300 美元，每個墻鐘為200 美元?，F(xiàn)在，三個業(yè)主希望能夠得到各種產(chǎn)品產(chǎn)量的最優(yōu)組合，以使得利潤最大化。將會討論牛奶約束，所以該部分在下面的圖中隱去了）。（1）為該問題建立線性規(guī)劃模型。（2）如果落地?cái)[鐘的單位利潤從300 美元增加到375美元， 而模型的其他不變，最優(yōu)解是否會改變。然后用該模型檢驗(yàn)如果墻鐘的單位利潤也從200 美元變動到175 美元，最優(yōu)解是否會改變。（3）在電子表格上建立和求解該問題的原始模型。

11、（4）運(yùn)用 excel 分析，如果落地?cái)[鐘的單位利潤在150 美元到 450 美元之間每增加20 美元給最優(yōu)解和總利潤帶來的影響（墻鐘單位利潤不變）。然后同樣分析，當(dāng)墻鐘的單位利潤在50 美元島 50 美元之間每增加20美元給最優(yōu)解和總利潤帶來的影響（落地?cái)[鐘單位利潤不變）。而模型的其他不變，運(yùn)用靈敏度報(bào)告確定最優(yōu)解是否會改變？用這些信息來估計(jì)每種鐘單位利潤允許取值x 圍。（5）象（ 4）中一樣，只是每增加20 美元變?yōu)槊吭黾?0 美元，給最優(yōu)解帶來的影響。（6）依次對每個業(yè)主用excel 分析，如果他們決定將自己的最大可用工時增加5 小時每周，那么給最優(yōu)解和總利潤帶來的影響。（7）運(yùn)用 ex

12、cel 分析，如果只是大衛(wèi)將最大可用工時變?yōu)?5、 37、39、41、43、45 時最優(yōu)解和總利潤的變化。 然后同樣分析， 萊蒂娜將可用工時進(jìn)行上述改變時的情況。最后分析， 當(dāng)莉迪亞將最大可用工時變?yōu)?5、17、19、21、23、 25 時最優(yōu)解和總利潤的變化。（8）生成 excel 靈敏度報(bào)告，用它來決定每種鐘的單位利潤和每個業(yè)主的最大可用工時的允許變化x 圍。任務(wù)所需時間（小時）落地?cái)[鐘墻鐘組裝機(jī)械配件雕刻木質(zhì)外殼運(yùn)輸6 8 3 4 4 3 （9）為了增加總利潤，三個業(yè)主同意增加他們?nèi)齻€人中的一個人的工作時間，增加該人的工作時間必須能夠最大限度地增加總利潤。運(yùn)用靈敏度報(bào)告，確定應(yīng)該選擇哪一

13、個人（假設(shè)模型的其他部分沒有任何變動）。（10）解釋為什么有一個人的影子價格是0。（11）如果莉迪亞將工作時間從每周的20 小時增加到25 小時，是否可以用影子價格分析該變動對結(jié)果的影響？如果影子價格有效，總利潤將增加多少？（12）在（ 1）中加入另一變動，即大衛(wèi)的工作時間從每周40 小時減少到35 小時，重新分析。三、運(yùn)輸問題和指派問題1、研究分析一下?lián)碛腥缦滤緟?shù)表的運(yùn)輸問題：單位成本（美元）供應(yīng)1 2 3 1 2 39 7 6 6 12 7 8 10 6 4 3 2 需求4 2 3 （1）畫出這個問題的網(wǎng)絡(luò)表示圖。（2）用電子表格描述這個問題，然后使用excel 得到最優(yōu)解決方案。2、

14、考慮擁有如下所示參數(shù)表的運(yùn)輸問題：（1）畫出這個問題的網(wǎng)絡(luò)表示圖。（2）用電子表格描述這個問題，然后使用excel 得到最優(yōu)解決方案。3、考斯雷司（ cost-less）公司從它的工廠向它的四個零售點(diǎn)供應(yīng)貨物，從每一個工廠到每一個零售點(diǎn)供應(yīng)貨物，從每一個工廠到每一個零售點(diǎn)的運(yùn)輸成本如下所示：工廠 1、2、3、4 每個月的生產(chǎn)量為10、20、20、10 個運(yùn)輸單位。零售點(diǎn)1、2、3、4 每個月所需貨物量為20、10、10、20 個運(yùn)輸單位。配送經(jīng)理蘭迪史密斯現(xiàn)在需要確定每個月從每一個工廠制中藥運(yùn)送多少給相應(yīng)零售點(diǎn)的最佳方案。蘭迪的目標(biāo)就是要使總的運(yùn)輸成本最小。（1）把這個問題描述為一個運(yùn)輸問題并

15、寫出相應(yīng)的出發(fā)地、供應(yīng)量、目的地、需求量和單位成本。（2）用電子表格描述這個問題，然后使用excel 得到最優(yōu)解決方案。目的地出發(fā)地單位成本（美元）供應(yīng)1 2 3 4 1 2 33 2 4 7 4 3 6 3 8 4 2 5 5 2 3 需求3 3 2 2 零售點(diǎn)工廠單位成本（美元）1 2 3 4 1 2 3 4500 200 300 200 600 900 400 100 400 100 200 300 200 300 100 200 銷地產(chǎn)地4、恰德費(fèi)爾（ childfair ）公司擁有三個生產(chǎn)折疊嬰兒車的工廠，并運(yùn)往四個配送中心。工廠1、 2 和 3 枚月產(chǎn)量為 12、17、11 個運(yùn)輸

16、單位。同時配送中心每月需要10 個運(yùn)輸單位的貨物。從每一個工廠到每一個配送中心的路程如下表所示：每一個運(yùn)輸單位的運(yùn)輸成本為每英里100.5 美元。（1）把這個問題描述為一個運(yùn)輸問題并寫出相應(yīng)的出發(fā)地、供應(yīng)量、目的地、需求量和單位成本。（2）用電子表格描述這個問題，然后使用excel 得到最優(yōu)解決方案。5、湯姆想要在今天買3 品脫的家釀酒，明天買另外的4 品脫。迪克想要銷售5 品脫的家釀酒，今天的價錢為每品脫 3.00 美元， 而明天的價錢是每品脫2.70 美元。哈里想要銷售4 品脫的家釀酒， 今天的價錢為每品脫2.90美元，而明天的價錢為每品脫2.80 美元。湯姆想要知道他要如何進(jìn)行購買才能在

17、滿足他的口渴需求的基礎(chǔ)之上，使他的購買成本達(dá)到最小值。為這個問題建立電子表格模型并解決它。9、萬諾特（ onenote）公司為四個顧客在三個工廠生產(chǎn)一種產(chǎn)品。在未來一周內(nèi)這三個工廠的產(chǎn)量為60、80、40 單位。 公司決定向顧客1 供應(yīng) 40 個單位， 向顧客 2 供應(yīng) 60 個單位， 向顧客 3 至少要供應(yīng)20 個單位。 顧客 3和 4 都想要盡可能多地購買剩下的產(chǎn)品。從工廠i 運(yùn)送單位數(shù)量的產(chǎn)品給顧客j 的凈利潤如下表所示（單位：美元） ：管理層希望知道為了使利潤最大，應(yīng)當(dāng)向顧客3和 4 提供多少單位的產(chǎn)品以與應(yīng)當(dāng)從每一個工廠向每一個顧客運(yùn)送多少單位的產(chǎn)品。用電子表格描述這個問題并求解。1

18、4、考慮擁有如下所示成本表的指派問題（單位：美元）：最優(yōu)解是a-3，b-1，c-2，總的成本是10 美元。（1）畫出這個問題的網(wǎng)絡(luò)表示圖。（2）在電子表格上對這個問題進(jìn)行描述，并使用excel 得到最優(yōu)解。零售點(diǎn)工廠到配送中心的距離（英里）1 2 3 4 1 2 3 800 1100 600 1300 1400 1200 400 600 800 700 1000 900 顧客工廠到每一個顧客的單位凈利潤（美元）1 2 3 4 1 2 3 800 500 600 700 200 400 500 100 300 200 300 500 工作人員相關(guān)成本（美元）1 2 3 a b c5 3 2 7

19、6 3 4 5 4 15、考慮擁有如下所示的成本表的指派問題（單位：美元）：（1）畫出這個問題的網(wǎng)絡(luò)表示圖。（2）在電子表格上對這個問題進(jìn)行描述，并使用excel 得到最優(yōu)解。16、四艘貨船要從一個碼頭向其他的四個碼頭運(yùn)貨（分別積為1、2、3、4） 。每一艘船都能夠運(yùn)送到任何一個碼頭。但是，由于貨船和貨物的不同，裝船、運(yùn)輸和卸貨成本都有些不同。如下表所示（單位：美元）：目標(biāo)是要把這四個不同的碼頭指派給四艘貨船，使總運(yùn)輸成本最小。（1）請解釋為什么這個問題符合指派問題模型。（2）在電子表格中描述這個問題并求解。17、x、王、李、趙4 位教師被分配教語文、數(shù)學(xué)、物理、化學(xué)4 門課程，每位老師教一門課程，一門課程由一位老師教。根據(jù)這四位老師以往教課的情況，他們分別教這四門課程的平均成績?nèi)缦卤恚核奈唤處熋咳酥荒芙桃婚T課，每一門課只能由一個教師來教，要確定哪一位教師上哪一門課，使四門課的平均成績之和為最高。用excel solver 求此指派問題的最優(yōu)解。四、網(wǎng)絡(luò)最優(yōu)化