【正文】 iiini ppppIpp ??0??? β ? β0),(lim 00 ??? ?? ppIip第二章 建模和實例 數(shù)據(jù)、模型與決策 ?對 ，令： ?則 ?與基年無關是指指數(shù)的變化與基年的選擇無關，即 0λ ?i)(,)( 1111100110 ???? ??? nnnn AppAp ??????? ??)(,)( 1111111 ???? ??? nnnn AppAp ??????? ??),(),( 00110 ???? ppIAApAApI ???),(),(),(),(0000????????ppIppIppIppI ?第二章 建模和實例 數(shù)據(jù)、模型與決策 四角動物的身長估計動物重量 ? 用四腳動物的身長估計動物體重時，可將四腳動物的軀干簡化為質量為 m的圓柱體，長度為 l，斷面面積為 s ，直徑為 d . 第二章 建模和實例 數(shù)據(jù)、模型與決策 ?把圓形軀干看作是一根支撐在四肢上的彈性梁，動物在體重 作用下的最大下垂量為 ，根據(jù)力學理論有： （體積） 得 若把 也作為自變量，與長度 l 一起作為估計重量的變量則有 SlmmfSdfl ??? ,/ 23?24 / dl??l/?3llbaf ???第二章 建模和實例 數(shù)據(jù)、模型與決策 第二章 建模和實例 ? 模型概論 ? 建立數(shù)學模型的一般過程 ? 若干初等模型 ? 第二章 建模和實例 數(shù)據(jù)、模型與決策 ? 共有地悲劇 ? 合作效益分配模式 ? “囚徒困境”模型 ? 拍賣模型 第二章 建模和實例 數(shù)據(jù)、模型與決策 共有地悲劇 ?設 n個農民擁有一片草地，每個農民都有在草地上放牧的自由。每年春天，每個農民決定自己養(yǎng)羊的數(shù)量，用 表示第 i個農民的飼養(yǎng)量，則 表示了總飼養(yǎng)量； v 代表到冬天時一頭羊的價值，顯然 的函數(shù)。 igngggG ???? ?21Gv是第二章 建模和實例 數(shù)據(jù)、模型與決策 ?三個沿河城 3，其位置如下圖所示，現(xiàn)要求這三城市的污水經(jīng)處理后才能向河道排放，是否有比各城市單獨建污水處理廠更好的辦法呢？ 第二章 建模和實例 數(shù)據(jù)、模型與決策 “囚徒困境”模型 ? 有兩個對策者，他們可以有兩種選擇，即合作與背叛，用表表示對策效益，前一數(shù)字表示 A的收益，后一數(shù)字表示 B的收益，如 A選合作， B選背叛，則 A得 0， B得 5。 A B 合作 背叛 合作 3， 3 0， 5 背叛 5， 0 1， 1 第二章 建模和實例 數(shù)據(jù)、模型與決策 ?納什均衡：納什均衡是這樣一種局面，誰想單獨打破這一局面都將付出代價。 第二章 建模和實例 數(shù)據(jù)、模型與決策 拍賣模型 ? 一級密封價格拍賣的規(guī)則是，投標人將自己的出價寫好后裝入信封并密封，交給拍賣人。拍賣人收齊投標人的出價信封后打開信封，拍賣品由出價最高者得到并按他自己的出價支付價格，其他投標人不得也不失。當然從理論上的完美性考慮，再補充規(guī)定若 個投標人投出相同的最高價，則在出最高價的 個人之間等概率分配。這里討論的問題是投標人該如何出價。 第二章 建模和實例 數(shù)據(jù)、模型與決策 第二篇 規(guī)劃和優(yōu)化模型 第三章 線性規(guī)劃 第三章 線性規(guī)劃 第三章 線性規(guī)劃 學習目的 線性規(guī)劃是運籌學的一個重要分支。通過對本章的學習要求： ? 能夠掌握線性規(guī)劃問題中的主要概念 ? 能夠掌握線性規(guī)劃問題中的線性規(guī)劃的標準形式 ? 能夠掌握線性規(guī)劃問題的求解方法 —— 圖解法及單純形法 ? 理解線性規(guī)劃問題解的概念和基本定理 ? 了解線性規(guī)劃問題的敏感性分析以及善于建立線性規(guī)劃模型來解決一些實際問題。 第三章 線性規(guī)劃 第三章 線性規(guī)劃 ? 線性規(guī)劃問題概述 ? 線性規(guī)劃問題的圖解法 ? 單純形法 ? 對偶問題 ? 敏感性分析 第三章 線性規(guī)劃 線性規(guī)劃問題概述 ? 線性規(guī)劃問題中的主要概念 ? 線性規(guī)劃問題的數(shù)學模型 第三章 線性規(guī)劃 線性規(guī)劃問題中的主要概念 ? 目標（ objective） : 所要達到的最優(yōu)結果（最大或最?。? ? 約束條件（ constraints）：對所能產生結果的限制。 ? 線性規(guī)劃：一種解決帶有約束條件的最優(yōu)化問題的方法。 ? 解決線性規(guī)劃問題的步驟 定義問題和收集數(shù)據(jù)。 建立模型，用恰當?shù)臄?shù)學式子表示問題 求出問題的最優(yōu)解 進行敏感性分析，檢查條件發(fā)生變化是會發(fā)生的情況。 第三章 線性規(guī)劃 確定潘得羅索工業(yè)公司的產品組合 ? 潘得羅索工業(yè)公司是一家墨西哥公司，截至在 1998年的銷售，公司生產了全國膠合板產量的四分之一，與其他膠合板生產廠商一樣，潘得羅索工業(yè)公司的許多產品根據(jù)厚度和所用木材的質量而有所不同。因為產品在一個競爭的環(huán)境中進行銷售，產品的價格由市場決定，所以產品的價格每月都有很大的變化。結果導致每項產品對公司整體利潤的貢獻也有很大的變動。 ? 從 1980年開始，潘得羅索工業(yè)公司管理部門每個月使用線性規(guī)劃指導下個月的產品組合決策。線性規(guī)劃的數(shù)學模型考慮了這一決策的所有相關限制條件，包括生產產品所需的有限的可得數(shù)量。然后對模型求解，找出可行并且最大可能利潤（ largest possible profit）的產品組合。 ? 采用線性規(guī)劃后，潘得羅索工業(yè)公司的成績是顯著的。改進的產品組合使公司的總利潤增加了 20%，線性規(guī)劃得其他貢獻包括更好的原材料利用，更好的資本投資，和更好的人員利用。 第三章 線性規(guī)劃 航空業(yè)的成本控制 ? 那時，聯(lián)行在其 11個航班訂票處，有超過 4， 000名的機場銷售代表和支持人員。在十個最大的機場大約有一千名顧客服務代表，有些時兼職的，每班 2到 8個小時不等，大部分是全職的，每班 8現(xiàn)實或 10小時，有許多個不同的上班時間。每個訂票處都有一天 24小時營業(yè)（通過電話訂票。然而，每個地點提供所需水平服務的雇員數(shù)量在一天 24小時種的變化很大，或許美國半個小時就會有很大的變化。 ? 為了更有效率的滿足服務要求，在每個地點為所有工作人員設計動作排成，是一個組合的夢魘。一旦一名雇員上了班，就會工作一個班次，只有就餐和每個兩個小時的短暫的休息時間，給定 24小時的一天中每半個小時各的服務所需的最小雇員數(shù)，在七天一周中， 24小時一天中每個班次需要多少雇員并且合適上班呢？ ? 幸運的是，線性規(guī)劃能解決這些組合夢魘問題。據(jù)有形估計，建立在線性規(guī)劃基礎上的計算機規(guī)劃系統(tǒng)每年為聯(lián)合航空公司在直接薪酬和津貼成本上節(jié)省了 600萬美元，得到的其他好處包括改善客戶服務以及降低雇員的工作負擔。 第三章 線性規(guī)劃 線性規(guī)劃問題的數(shù)學模型 ? 一家玻璃產品生產公司生產帶有花樣圖案的彩色玻璃花瓶。每一個花瓶經(jīng)過藝術玻璃吹風機從液態(tài)加工而成，然后進入儲藏室冷卻至室溫，花瓶有大和小兩種尺寸，但是生產過程幾乎相當，而且使用同一種材料。不論尺寸，每一個花瓶都需要 20分鐘的藝術加工，每周藝術加工工作時間為 40小時；大小花瓶每個個需彩色玻璃 2 OZ和 1 OZ。每周可用的玻璃為 160 OZ。另外，一個小花瓶占用 2單位儲存空間，大花瓶占用 3個單位儲存空間，一共有 260個單位儲存空間。大小花瓶的利潤貢獻率分別為 12元 /個和 10元 /個。問應該怎樣安排生產，才能使利潤值最大。 第三章 線性規(guī)劃 線性規(guī)劃問題的數(shù)學模型 工序 花瓶種類 占用材料 （ OZ） 藝術加工 （小時） 儲存空間 （一單位） 利潤值 （元） 大花瓶 2 1/3 3 12 小花瓶 1 1/3 2 10 每周可用能力 160 40 260 —— B表示大花瓶每周生產的數(shù)量， S表示小花瓶每周生產的數(shù)量。 第三章 線性規(guī)劃 約束條件 ?2B+S≤160 ?1/3B+1/3S≤40 ? 3B+2S≤260 ?B≥0, S≥0 目標函數(shù)： ?max z =12B+10S 第三章 線性規(guī)劃 數(shù)學模型表述如下 ?目標函數(shù) max z =12B+10S ?材料約束 2B+S≤160 ?時間約束 1/3B+1/3S≤40 ?儲存約束 3B+2S≤260 ?非負約束 B≥0, S≥0 第三章 線性規(guī)劃 數(shù)學建模四個步驟： ?決策變量 ?確定目標函數(shù) ?確定約束條件 ?確定非負約束 第三章 線性規(guī)劃 ?實例分析： ? A集團有 1,000,000元的資金可供投資，該集團有五個可供選擇的投資項目，其中各種資料如下： 投資項目 風險 % 紅利 % 增長 % 信用度 1 10 5 10 11 2 6 8 17 8 3 18 7 14 10 4 12 6 22 4 5 4 10 7 10 第三章 線性規(guī)劃 ?A集團的目標為：投資風險最小，每年紅利至少是80,000元，最低平均增長率 14%，最低平均信用度為 6，請用線性規(guī)劃方法描述該問題。 第三章 線性規(guī)劃 ?決策變量為個項目的投資數(shù)額，設為 xi ( i =1,2,3,4,5) ?目標函數(shù)： min z = ( + + + + ) 第三章 線性規(guī)劃 約束條件： ? 各項目投資總和為 1,000,000元 x1 + x2 + x3 + x4+ x5 = 1,000,000 ? 所得紅利最少為 80,000元 x1 + x2 + x3 + x4+ x5≥ 80,000 ? 增加額不低于 140,000元 1x1 + x2 + x3 + x4+ x5≥140,000 ? 平均信用度不低于 6 (11 x1 + 8 x2 + 10 x3 + 4 x4+10 x5)/5≥6 ? 非負約束 xi ≥ 0 ( i =1,2,3,4,5) 第三章 線性規(guī)劃 ?實例分析： ? 某石油公司利用三種有生產兩種混合原料。每種油的成本和每天的可用量如下表所示： 油 成本（元 /升） 可用量（升） A 8 10,000 B 10 15,000 C 12 20,000 燃料 1 A：最多占 25% B：最少占 30% C：最多占 40% 燃料 2 A：最少占 20% B：最多占 50% C：最少占 30% 第三章 線性規(guī)劃 ?燃料 1售價為 30元 /升，燃料 2 售價為 35元 /升，該公司有一向長期合同，每天供應兩種原料，各 10， 000升。請建立該問題的數(shù)學規(guī)劃模型。 解題過程： ? 決策變量為加入到兩種燃料種的各種油的量： ? A1為原料 1中加入 A種油的升數(shù)。 ? A2為原料 2中加入 A種油的升數(shù)。 ? B1為燃料 1中加入 B種油的升數(shù)。 ? B2為燃料 2中加入 B種油的升數(shù)。 ? C1為燃料 1中加入 C種油的升數(shù)。 ? C2為燃料 2中加入 C種油的升數(shù)。 第三章 線性規(guī)劃 ? 燃料 1和燃料 2 的產量為： ? 燃料 1： A1+B1+C1 ? 燃料 2： A2+B2+C2 ? 各種油的使用量： ? A種油 = A1+A2 ? B種油 = B1+ B2 ? C種油 = C1+ C2 ? 目標是取得最大化的利潤，兩種燃料的銷售收入為： ? 30 (A1+ B1+ C1)+35 (A2+ B2+ C2) 第三章 線性規(guī)劃 ? 而三種油的成本為： ? 8 (A1+A2)+10 (B1+ B2)+12 (C1+ C2 ) ? 利潤是銷售收入和成本之差，作為目標函數(shù)可以表示如下： ? max z =22 A1+27 A2 +20 B1+25B2+18 C1+23 C2 ? 三種可用的原料油的約束為： ? A1+A2≤10,000 ? B1+ B2≤15,000 ? C1+ C2≤20,000 第三章 線性規(guī)劃 ? 各種原料油所占比例的六個約束： ? A1≤ (A1+B1+C1) ? B1≥ (A1+B1+C1) ? C1≤ (A1+B1+C1) ? A2≥ (A2+B2+C2) ? B2≤ (A2+B2+C2) ? C2≥ (A2+B2+C2) ? 長期供貨合同約束： ? A1+B1+C1≥10,000