規(guī)劃問題的教學(xué)例題

1、規(guī)劃問題的教學(xué)例題例 1 某工廠在計(jì)劃期內(nèi)要安排 I、 II 兩種產(chǎn)品生產(chǎn)。生產(chǎn)單位 產(chǎn)品所需的設(shè)備臺(tái)時(shí)及 A，B 兩種原材料的消耗以及資源的限制如表 1-1 所示另外，工廠每生產(chǎn)一單位 I 可以獲利 50 元，每生產(chǎn)一單位 II 可以獲利 100 元，問工廠應(yīng)分 別生產(chǎn)多少單位產(chǎn)品 I 和產(chǎn)品 II，才能獲利最多例 2 貨物托運(yùn)問題 某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤(rùn)以及托 運(yùn)限制如表 1-2且甲種貨物最多托運(yùn) 4 件，問兩種貨物各托運(yùn)多少件，可獲利最大。例 3 投資場(chǎng)所的選擇某公司計(jì)劃在市區(qū)的東、 南、西、北四個(gè)區(qū)建立銷售門面， 擬議中有 10 個(gè)位置

2、 Ai(i=1,2, ,10) 可供選擇，考慮到各個(gè)地區(qū)居民消費(fèi)水平以及居民的居住密度，規(guī)定在東區(qū) A1,A2,A3 三個(gè)點(diǎn)中至少選擇兩個(gè)；在西區(qū) A4,A5 兩個(gè)點(diǎn)中至少選擇一個(gè)；在南區(qū) A6,A7 兩個(gè)點(diǎn)中至少選擇一個(gè)；在北區(qū) A8,A9,A10 三個(gè)點(diǎn)中至少選擇 2 個(gè)。Ai 各個(gè)點(diǎn)的設(shè)備投資以及每年可獲利潤(rùn)由于地點(diǎn)不同都不一樣，預(yù)測(cè)情況如下表A1A2A3A4A5A6A7A8A9A10投資額10012015080709080140160180利潤(rùn)36405022203025485861另外，投資總額不能超過 720 萬元，問應(yīng)該選擇哪幾家銷售點(diǎn)，可使得年利潤(rùn)為最大 例 4 固定成本問題

3、高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器的各種資源的數(shù)量如表 1-3 所示不考慮固定費(fèi)用，每種容器出售一只的利潤(rùn)分別為 4 萬元， 5萬元， 6 萬元，可使 用的金屬板有 500t，勞動(dòng)力有 300 人/月，機(jī)器有 100 臺(tái)/月。例 5 路燈照度問題在一條 20m 寬的道路兩側(cè)， 分別安裝了一只 2kw 和一只 3kw 的路燈， 它們離地面的高 度分別為 5m 和 6m 。在漆黑的夜晚，當(dāng)兩只路燈開啟時(shí)，兩只路燈連線路面上最暗的點(diǎn)和 最亮的點(diǎn)在哪里如果 3kw 路燈的高度可以在 3m 到 9m 之間變化，如何使得路面上最暗和 最亮的點(diǎn)的位

4、置如果兩只路燈的高度均可以在 3m 到 9m 之間變化，結(jié)果將如何 例 6 某部門有三個(gè)生產(chǎn)同一產(chǎn)品的工廠 （產(chǎn)地），生產(chǎn)的產(chǎn)品運(yùn)往四個(gè)銷售點(diǎn) （銷地） 出售， 各個(gè)工廠的生產(chǎn)量、各銷地的銷量（單位：噸） 、從各個(gè)工廠到各個(gè)銷售點(diǎn)的單位運(yùn)價(jià)（元 /噸）如下表，研究如何調(diào)運(yùn)才能使得總運(yùn)費(fèi)最小。例 7 多目標(biāo)供給問題 已知三個(gè)工廠生產(chǎn)的產(chǎn)品供應(yīng)給四個(gè)用戶，各工廠生產(chǎn)量、用戶需求量及從各個(gè)工廠到用 戶的單位產(chǎn)品的運(yùn)輸費(fèi)用如表 4-2 所示。由于總生產(chǎn)量小于總需求量， 上級(jí)部門經(jīng)研究決定， 制定了調(diào)配方案的 8 項(xiàng)指標(biāo)，并規(guī)定了重要性的次序。第二目標(biāo)：供應(yīng)用戶 1的產(chǎn)品中，工廠 3的產(chǎn)品不少于 100

5、個(gè)單位； 第三目標(biāo)：每個(gè)用戶的滿足率不低于 80%； 第四目標(biāo)：應(yīng)盡量滿足個(gè)用戶的要求； 第五目標(biāo)：新方案的總運(yùn)費(fèi)不超過原運(yùn)輸問題的總運(yùn)費(fèi)的10%；第六目標(biāo)：因道路問題，工廠 2到用戶 4的路線盡量避免運(yùn)輸； 第七目標(biāo)：用戶 1和用戶 3的滿足率應(yīng)盡量保持平衡； 第八目標(biāo)：力求減少總運(yùn)費(fèi)； 請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型，并用 Lingo求解。例 8 指派問題 1某商業(yè)公司計(jì)劃開辦 5 家新的商店。為了盡早建成營(yíng)業(yè)，商業(yè)公司決定由 5 家建筑公司分 別承包。已知建筑公司 Ai(i=1,2, ,5)對(duì)商店 Bj的造價(jià)(萬元)為 cij(i,j=1,2, ,n),見表。商業(yè)公司 對(duì) 5 家建筑公司怎樣分

6、配任務(wù)，才能使得總的建造費(fèi)用最少例 9 指派問題 2某學(xué)校規(guī)定，管理學(xué)專業(yè)的學(xué)生畢業(yè)時(shí)必須至少學(xué)習(xí)兩門數(shù)學(xué)課、三門經(jīng)濟(jì)學(xué)課和兩 門計(jì)算機(jī)課。這些課程的編號(hào)、名稱、學(xué)分、所屬類別和先選修課要求如下表。畢業(yè)時(shí)， 學(xué)生最少可以學(xué)習(xí)這些課程中的那些課程。例10 航班編排問題某航空公司經(jīng)營(yíng) A，B，C 三個(gè)城市的航線，這些航線每天班次起飛與到達(dá)時(shí)間如下表所示。 設(shè)飛機(jī)在機(jī)場(chǎng)停留的損失費(fèi)大致與停留時(shí)間的平方成正比，又每架飛機(jī)從降落到下班 起飛至少需 2 小時(shí)準(zhǔn)備時(shí)間，試決定一個(gè)使停留費(fèi)用損失為最小的分派飛行方案。航班號(hào)起飛城市起飛時(shí)間到達(dá)城市到達(dá)時(shí)間101A9：00B12：00102A10：00B13：0

7、0103A15：00B18：00104A20：00C24：00105A22：00C2：00（次日)106B4：00A7：00107B11：00A14：00108B15：00A18：00109C7：00A11：00110C15：00A19：00111B13：00C18： 00112B18：00C23： 00113C15：00B20： 00114C7：00B12：00例11運(yùn)輸問題1甲、乙兩個(gè)煤礦分別生產(chǎn)煤炭 500 萬噸和 600 萬噸，供應(yīng) A、B、C、D 四個(gè)發(fā)電廠的需要， 各廠的用煤量分別是 300，200，500，100（萬噸）。已知煤礦之間、煤礦與電廠之間以及各 個(gè)電廠之間的距離如下表

8、所示。每天可以直接運(yùn)達(dá)，也可以轉(zhuǎn)運(yùn)抵達(dá)，試確定從煤礦到每 個(gè)電廠的煤炭最優(yōu)調(diào)運(yùn)方案。例 12 運(yùn)輸問題 2某公司有 6 個(gè)建筑工地要開工，每個(gè)工地的位置 （a,b）（平面坐標(biāo)，單位： km ）以及水泥日用量 d（單位： t ）由下表給出。目前有兩個(gè)臨時(shí)料場(chǎng)位于P（5,1）， Q（2,7）。水泥日儲(chǔ)存量為20t。試回答如下兩個(gè)問題：（1）假設(shè)料場(chǎng)到工地之間均有直線道路相連，試制定每天的供應(yīng)計(jì)劃，即從兩個(gè)料場(chǎng)分別 向各個(gè)工地運(yùn)送水泥多少噸，使總的噸公里數(shù)最少（2）為了進(jìn)一步減少噸公里數(shù)， 打算舍棄目前的兩個(gè)臨時(shí)料場(chǎng)， 改建兩個(gè)新的料場(chǎng) （兩個(gè)新 料場(chǎng)與各工地間都有直線道路連接 ），日儲(chǔ)量還是 20

9、t，問應(yīng)該建在何處，與目前兩個(gè)料場(chǎng) 相比，節(jié)省的噸公里數(shù)是多少（3）假設(shè)即將由一條高速公路穿過工地群，且規(guī)劃的高速公路穿過平面上的兩點(diǎn)（0,8） 和（6,0）。為了運(yùn)輸原材料方便， 公司希望新建的兩個(gè)料場(chǎng)位于高速公路旁。 又該建于何處， 使 得運(yùn)量 （噸 .公里數(shù) ）最小例 13 銅線加工問題已知市場(chǎng)對(duì)每種規(guī)格的裸銅線的需求分別為3000km 和 2000km ，對(duì)兩種規(guī)格塑包機(jī)的需求分別為 10000km 和 8000km 。按照規(guī)定，新購(gòu)及改進(jìn)設(shè)備每年按照5%的折舊提取折舊費(fèi)，老設(shè)備不提； 每臺(tái)機(jī)器每年最多工作 8000h ，為了滿足需求， 確定使得總費(fèi)用最小的設(shè)備備 選用方案和生產(chǎn)計(jì)劃。

10、例 14 有瓶頸設(shè)備的多級(jí)生產(chǎn)計(jì)劃問題某工廠主要任務(wù)是通過組裝生產(chǎn)產(chǎn)品A，用于滿足外部市場(chǎng)需求。產(chǎn)品 A 的構(gòu)成與組裝過程如下圖。即 D、E、F、G 是從外部采購(gòu)的零件，先將 D、 E組裝成 B，零件 F、G 組裝成 C，然后部件 B、 C組裝成 A 出售。圖中弧上的數(shù)字表示的是組裝的部件（產(chǎn)品）中包含的零件（部件） 的數(shù)量（也可以是消耗系數(shù)） 。假設(shè)該工廠每次生產(chǎn)計(jì)劃的計(jì)劃期為 6 周（即每次制定未來 6 周的生產(chǎn)計(jì)劃） ，只有最終產(chǎn) 品 A 有外部需求，目前收到的訂單需求件數(shù)如下表第 2 行。另 B、 C的能力消耗系數(shù)分別是 5和 8，即生產(chǎn)一件 B需要占 5個(gè)單位的能力，生產(chǎn) 1件 C 需要占 8 個(gè)單位的能力。對(duì)每種部件或產(chǎn)品，如果工廠在某一周定購(gòu)或者生產(chǎn)該部件或者產(chǎn)品，工廠需要付出一個(gè) 與訂單或者生產(chǎn)無關(guān)的固定成本（稱為生產(chǎn)準(zhǔn)備費(fèi)用） ；如果某一周結(jié)束時(shí)該零部件或者產(chǎn) 品有庫(kù)存，則工廠必須付出一定的庫(kù)存費(fèi)用（與庫(kù)存數(shù)量成比例） 。這些數(shù)據(jù)見下表。零部件編號(hào)ABCDEFG生產(chǎn)準(zhǔn)備費(fèi)用400