




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、渭南師范學院 數學系教師教案紙渭南師范學院數學系講稿 2012 2013 學年 第 二 學期教 研 室 計算數學 課程名稱 線性規劃 授課對象 數專升本12級 授課教師 路玉麟 職 稱 講 師 教材名稱 線性規劃武漢大學出版社張干宗 2013年 3月10日 第 頁 線性規劃 課程教案講稿授課題目(教學章節或主題):前言 線性規劃概述授課類型課堂講授授課時間第 1 周第 1節教材分析: 本章主要介紹了線性規劃的基本概念。教學目的與要求:要求學生掌握線性規劃的作用和意義。重點與難點:重點:線性規劃的基本概念難點:常見線性規劃問題教學內容與過程(設想、方法、手段) 啟發式教學、課堂精講、講練結合思考
2、題、討論題、作業:參考資料(含參考書、文獻等):教學內容與過程課后分析前 言線性規劃的英文全稱為:Linear Programming,可簡稱為LP一、線性規劃所屬學科線性規劃是“運籌學”中應用最廣泛、理論最成熟的一個分支二、線性規劃發展簡史三十年代末,蘇聯數學家康托洛維奇開始研究生產組織中的線性規劃問題1947年美國數學家丹捷格提出了單純形(Simplex)方法及有關理論,為線性規劃奠定了理論基礎五十年代,線性規劃成為經濟學家分析經濟問題的重要工具隨著計算機的迅猛發展,線性規劃現被廣泛應用于工業、農業、商業等各個領域三、用線性規劃方法解決實際問題的兩大特點1、全局性從全局出發,將全局目標作為
3、追求目標;2、定量性通過建立數學模型,對實際問題進行定量分析,而不是只做定性分析數學模型指:將實際問題用一系列數學表達式(函數、方程、不等式等)表示出來,稱這一系列數學表達式為該實際問題的數學模型同時應注意全局的相對性,即對于車間,企業是全局;但對于集團公司,企業是局部,集團公司才是全局 教學內容與過程課后分析四、線性規劃方法解決的兩類問題1、任務一定,如何安排,可使人、財、物最??;2、人、財、物一定,如何安排,可使任務完成量最多五、線性規劃可解決以下幾方面的問題、運輸問題:某產品有若干個產地、若干個銷地,如何運輸,使總運費最省;2、生產組織問題:3、配料問題:如何搭配各種原料,既符合質量(營
4、養)要求,又使成本最低;4、投資問題:資金一定,投向誰、投多少、期限多長,使若干年后本利和最高;5、庫存問題:在倉庫容量有限情況下,如何確定庫存物資的品種、數量、期限,使庫存效益最佳;6、合理播種問題:在土地資源有限的情況下,種什么、種多少,使效益最高;六、用線性規劃方法解決實際問題的步驟1、提出問題,收集資料;2、建立線性規劃數學模型;3、用線性規劃方法解模型;4、給出最優決策方案七、講授內容1、建模;2、用圖解法解線性規劃問題;3、用計算機軟件解線性規劃模型;4、寫最優決策方案八、考試方式:教學內容與過程課后分析線性規劃 課程教案講稿授課題目(教學章節或主題):第一章 線性規劃數學模型的建
5、立授課類型課堂講授授課時間第 周第 節教材分析:本章通過例題說明線性規劃數學模型的形式、三要素及建立數學模型的方法教學目的與要求:通過本章學習,使學生理解線性規劃數學模型的概念及一般表示形式;掌握線性規劃數學模型的三要素;掌握建立線性規劃數學模型的步驟和方法;能熟練的建立一些問題的線性規劃數學模型;理解線性規劃數學模型解的含義重點與難點:重點:線性規劃數學模型的建立難點:建立線性規劃數學模型教學內容與過程(設想、方法、手段)啟發式教學、課堂精講、講練結合1、 供求平衡條件下的運輸問題模型的建立;2、 線性規劃數學模型的三要素;3、 建立線性規劃數學模型的步驟;4、 線性規劃問題解的概念(可行解
6、、可行解集、最優解、最優值);5、 線性規劃的概念;6、 線性規劃數學模型的一般形式思考題、討論題、作業:參考資料(含參考書、文獻等):教 學 內 容 與 步 驟備注本章通過例題說明線性規劃數學模型的形式、三要素及建立數學模型的方法一、建立線性規劃數學模型的例例1 供求平衡狀態下的運輸問題有兩個農場和,產糧量分別為23萬噸和27萬噸,要將糧食運往,三個城市,三個城市的糧食需求量分別為17、18和15萬噸農場到各城市的運價如下表運價表 單位:元/萬噸運價城市農場50607060110160問:應如何調運,可使總運費最???試建立該問題的數學模型分析此問題有兩個供應方和,三個需求方,假設這五者組成一
7、個封閉系統,兩個供應者的糧食只能提供給這三個需求方,同時三個需求方的糧食也只能從這兩個供應者處獲得要建立該問題數學模型,必須首先從問題出發該題問“應如何調運,使總運費最省”“應如何調運”指從農場分別向三個城市運多少萬噸糧食(三個量),從農場分別向三個城市運多少萬噸糧食(三個量),共計6個量 上述6個量是可以變化的,在計算前是未知的,是有待決策的,稱其為決策變量在建立數學模型時應首先將其設出為便于區分供應方和需求方,將其設為雙下標變量設:從農場運往城市的調運量為萬噸教 學 內 容 與 步 驟備注注意,此時的既表示從農場發往城市的發出量,同時也表示城市從農場處的接收量如表示從農場運往城市的糧食量,
8、同時表示城市從農場處的接收量為方便討論問題,運輸問題通常先列出如下調運表調運表調運量 城市農場產糧量(可供應量)2327需求量171815供求平衡在這五個部門組成的封閉系統中,所有供應方的可供應量之和(23+27=50)為整個系統的可供應量,整個系統中所有城市糧食需求量之和(17+18+15=50)構成系統的總需求量由于該系統的總供應量和總需求量都是50,相等,故在調運表最后一個單元格中填寫“供求平衡”此問題即為供求平衡狀態下的運輸問題上述所設的6個決策變量(調運量)應滿足一定要求,這些要求就應從供求平衡開始由于供求平衡,供應方和需求方均恰好得到滿足,即:兩個供應方的糧食恰好全部運出,三個需求
9、方所需要的糧食也恰好全部得到滿足,下面通過列表將文字語言轉化為數學表達式供應方:調出量恰好等于產糧量供應方調出量恰好等于產糧量=23=27需求方:調入量恰好等于需求量教 學 內 容 與 步 驟備注需求方調入量恰好等于需求量=17=18=15于是,所設決策變量同時滿足以上五個方程,且由于為調運量,必須非負所以應滿足:稱上述條件為約束條件,滿足約束條件的解稱為可行解分析可行解的情況由于方程組中無矛盾方程,且有效方程的個數(4個)少于未知量的個數(6個),方程組有無窮多個解,進一步滿足非負條件的解也有無窮多個,即可行解有無窮多個,每個可行解對應著一個調運方案(可執行方案)如:方案1113923165
10、627171815對應解 方案21121023166527171815對應解 教 學 內 容 與 步 驟備注顯然,應有無窮多種調運方案每個調運方案都對應著一個總運費方案1對應的總運費為:(元);方案2對應的總運費為:(元)即該題有無窮多個調運方案,不同調運方案對應不同運費,該問題要從無窮多個調運方案中找出一個使總運費最省的方案,即使總運費函數取得最小值的一組變量的取值綜上,該問題數學模型列寫如下:解 設:由農場運往城市的調運量為萬噸則該問題的數學模型為:求一組變量的值,使其滿足:并使最小此問題充分體現了全局觀念需求方不能僅考慮自己運費是否最低,而必須從整個封閉系統總運費最低的角度出發,做到局部
11、利益服從整體利益該題屬第一類問題,即任務一定,如何安排,使人、財、物最省通過例1對線性規劃數學模型有關問題作如下歸納教 學 內 容 與 步 驟備注二、線性規劃數學模型的三要素所有線性規劃數學模型都要求一組變量的值,稱該組變量為決策變量;該組決策變量都要滿足一組條件,稱該組條件為約束條件一般,約束條件由兩部分組成:一部分為非負約束,剩下部分為數量約束;通常,滿足約束條件的解若存在有無窮多個,我們最終不是求這無窮多個解分別是什么,而要尋求一個目標這個目標由函數表示,稱為目標函數,線性規劃問題最終要使目標函數取得最大值或最小值決策變量、約束條件、目標函數分別構成了線性規劃數學模型的三大要素即三、建立
12、線性規劃數學模型的步驟建立實際問題線性規劃數學模型的過程,實際是“翻譯”的過程,即將實際問題翻譯成數學表達式的過程通常先用文字將實際問題表示出來,再將文字轉化為數學表達式具體步驟如下:1、設決策變量根據題目的“問題”,設決策變量;2、列寫約束條件根據題目要求(字面或隱含)列出約束條件,約束條件中通常包含非負限制3、寫目標函數,并注明求最大或最小通常目標函數要求在題目的問中提出四、線性規劃問題解的概念1、可行解:滿足約束條件的解稱為線性規劃問題的可行解2、可行解集:全體可行解組成的集合3、最優解:使目標函數實現最優的可行解4、最優值:最優解對應的目標函數值由上述分析知,線性規劃問題最終就是要求最
13、優解和最優值,該過程稱作解線性規劃問題的過程,或求線性規劃問題的解的過程通常人們靠經驗、靠想象求最優解,如上述例1,人們通常從當今的最低運費開始設計,直至滿足所有需求方的需求,具體操作如下:教 學 內 容 與 步 驟備注由于到的運費最低,因而的需求17萬噸全部從處獲得,得到滿足;在余下的運費中,到的運費最低,將剩余的6萬噸給,所需的另12噸只能從運費相對較低的處獲得;由于此時的糧食已全部運出,盡管運費較高,所需要的15萬噸糧食也只能從處獲得于是調運表如下方案1760230121527171815該調運方案所對應的總運費為4930元顯然不是最優方案因而必須有專用的、科學的方法解線性規劃問題解線性
14、規劃問題的方法有圖解法、單純形方法、對偶單純形方法、兩階段法、大M法等,我們在第五章中主要學習使用計算機軟件求解通過計算機軟件求解,可得例1的最優調運方案為:最優方案0815231710027171815該調運方案對應的運費為3650元,是所有可執行方案中運費最省的方案至于如何用程序解模型我們將在以后學習下面我們仍然介紹建立數學問題的數學模型的方法例2 資源利用問題某企業生產A,B兩種產品,已知生產單位產品A和B分別需要消耗鋼材8噸和9噸,煤5噸和8噸,電力6度和4度,勞動力4人日和12人日現該企業有鋼材400噸,煤320噸,電力280度,勞動力350人日又知生產單位產品A和B各能獲利8千元和
15、1萬元問應如何安排生產,可使企業利潤最大?試建立該問題的數學模型教 學 內 容 與 步 驟備注 分析 可將已知條件列表如下:單耗 產品資源AB現有量鋼材 (噸)89400煤 (噸)58320電力 (度)64280人力 (人日)412350單位利潤 (千元)810顯然,B的單位利潤高于A的單位利潤,應多生產,但B對資源的消耗大,在資源有限的情況下,生產數量必然少于同樣資源條件下A產品的生產數量另外,現有資源數量與B的單耗間也不成比例,因此應對兩種產品產量進行合理搭配,才能在現有資源條件下創造出最高利潤此處的“如何安排生產”指在現有資源條件下,A、B兩種產品產量分別為多少決策變量:A、B兩種產品產
16、量,分別為和約束條件:生產過程中對各種資源的消耗量不超過現有量資源消耗量不超過現有量鋼材400煤320電力280勞動力350顯然,滿足上述條件的解有無窮多個,每個解對應一個生產方案,不同生產方案對應不同的企業利潤目標函數:企業利潤最大,即最大該問題數學模型列寫如下解 設:A、B兩種產品產量分別為和則該問題的數學模型為:教 學 內 容 與 步 驟備注求一組變量和的值,使其滿足:并使最大此問題屬第二類問題,即人、財、物一定,如何安排,使任務完成量最多此題需要說明的幾個問題:(1)關于決策變量:資源利用問題中的決策變量只能設各種產品的產量,而不能設資源消耗量因為產量作為決策變量,約束條件中的資源消耗
17、量及目標函數中的企業利潤都可以通過決策變量(產量)表示,也便于利用計算出的結果安排生產但若設資源消耗量為決策變量,則很難分辨這些資源是由哪些產品消耗的,因而企業利潤無法表示,也就無法寫出目標函數(2)關于約束條件:約束條件中的數量約束不能寫成等式約束這是由于:等式約束表示各種資源恰好全部用完,與實際問題不符,此時的利潤未必最大因為利潤最大時,某些資源可能恰好用完,但某些資源可能有剩余;上述方程組可能無解;即使方程組有解,即使此時利潤最大,在列約束條件時,也不必寫成“=”,因為沒有普遍性而“”中包含“=”,應靠解規劃問題解出結果可能均為=,但不能事先寫成=(3)此題通過計算機程序解得最優解和最優
18、值為:即:產品A生產27.5個單位,產品B生產20個單位時,企業利潤最大,最大利潤為420千元教 學 內 容 與 步 驟備注(4)資源利用問題分析:將最優解代入約束條件的左端,即可得到最優生產方案條件下各種資源的實際消耗量(如下表),將實際消耗量與資源現有量作比較,可分析出各種資源的屬性資源消耗量現有量余量鋼材4000煤32022.5電力28035勞動力3500由于鋼材和勞動力恰好用完,稱其為稀缺資源,而煤和電力有剩余,稱其為剩余資源,同時可計算出剩余資源的剩余量(5)假設采用預先買電的方式,該企業應買245度電(6)假設要求勞動力全部上崗,則約束條件變為 (7)假設勞動力市場有充足的勞動者供
19、應,則約束條件中應將勞動力約束刪去,變為:例3 營養問題有一位消費者欲購買營養物,根據醫生要求,他所購買的營養物中,維生素A的含量不低于9克,維生素C的含量不低于19克現有六種營養物可供選擇,單位該營養物所含維A和維C的數量,及六種營養物的購買價格如下表:單位含量 營養物維生素維A (克)102212維C (克)013132購買價格 (元)202560353739問:他應如何購買,既符合醫生要求,又花錢最省?試建立該問題的數學模型教 學 內 容 與 步 驟備注分析 顯然,滿足醫生要求的購買方案有很多,但不同購買方案所花的錢數不同,該題要求找出花錢最少的方案 決策變量:此處的“應如何購買”指六種
20、營養物應分別購買多少設六種營養物的購買量分別為,約束條件:購買營養物的實際含量不低于醫生要求 維生素實際含量不低于醫生要求維9維19顯然,滿足上述數量約束條件和非負限制的解有無窮多個,每個解對應一個購買方案,花的錢數各不相同目標函數:花錢最少,即最小該問題數學模型列寫如下解 設:營養物的購買量為則該問題的數學模型為:求一組變量值,使其滿足:并使最小思考一下,該題屬于第幾類問題以上三個問題雖屬于三個不同領域,但都是優化問題,都是要求滿足一定約束條件的最值問題,因而都屬于規劃問題,它們具有以下共同特點:1、都要求一組決策變量的值決策變量的每一組取值對應著一個可執行方案通常一個規劃問題有無窮多個可執
21、行方案2、都要滿足一組約束條件,約束條件由數量約束和非負限制組成,其中數量約束可能是等式約束、可能是不等式約束,在不等式約束中,可能是“”約束,也可能是“”約束3、都有一個目標函數,根據題目不同,有的目標函數求最大,有的求最小若約束條件為“”約束,目標函數一般求最大,對應著人、財、物一定,如何安排,使任務完成量最多問題;若約束條件為“”約束,目標函數通常求最小,對應著任務一定,如何安排,使成本最低問題4、約束條件和目標函數都是決策變量的線性表達式教 學 內 容 與 步 驟備注五、線性規劃數學模型的一般形式當規劃問題中的約束條件和目標函數都是決策變量的線性表達式時,稱規劃問題為線性規劃問題線性規
22、劃數學模型的一般形式為:求一組變量的值,使其滿足:并使最大(或最小)或寫成例4 供求不平衡時的運輸問題例1中若農場的糧食產量提高到了25萬噸,其他條件不變,問如何調運,使總運費最省?試建立該問題的數學模型解由農場運往城市的調運量為萬噸調運表調運量 城市農場產糧量(可供應量)2527需求量171815供>求由于供>求,供應方不能得到滿足,而需求方則恰好得到滿足,即:教 學 內 容 與 步 驟備注供應方:調出量不超過產糧量供應方調出量不超過產糧量2527需求方:調入量恰好等于需求量需求方調入量恰好等于需求量=17=18=15該問題的數學模型為:求一組變量的值,使其滿足:并使最小例5 供
23、求不平衡時的運輸問題例4在即將執行最優運輸方案時,接到城市的信息,的糧食需求量增至20萬噸問如何調運,使總運費最省?試建立該問題的數學模型解設:由農場運往城市的調運量為萬噸 調運表調運量 城市農場產糧量(可供應量)2527需求量171820供<求教 學 內 容 與 步 驟備注由于供<求,供應方能得到滿足,而需求方則不能得到滿足,即:供應方:調出量恰好等于產糧量供應方調出量恰好等于產糧量=25=27需求方:調入量不超過需求量需求方調入量不超過需求量171820該問題的數學模型為:求一組變量的值,使其滿足:并使最小例6 生產計劃問題(工時利用問題)某精密儀器廠生產甲、乙、丙三種儀器,平
24、均每生產一臺甲需7小時加工、6小時裝配、售價為3000元;每生產一臺乙需8小時加工、4小時裝配、售價為2500元;每生產一臺丙需5小時加工、3小時裝配、售價為1800元每季度可供利用的加工工時為2000小時,裝配工時為1000小時,三種儀器所需元器件基本相同又據市場預測知:市場對甲的需求量每季度不超過200臺,乙不低于180臺,丙無要求問應如何安排生產,可使企業產值最高?試建立該問題的數學模型教 學 內 容 與 步 驟備注將已知條件列表如下:單位工時 產品工序甲乙丙每季度可用工時加工7852000裝配6431000售價300025001800市場需求分析 決策變量:三種儀器每季度產量,分別為,
25、和臺;約束條件:兩方面(1)加工時對設備的消耗工時數不超過每季度可利用工時數;(2)甲、乙兩種儀器每季度實際產量應滿足市場對該儀器的需求量(1)加工時對設備的消耗工時數不超過每季度可利用工時數:工序實際消耗量不超過可用量加工2000裝配1800(2)甲、乙兩種儀器每季度實際產量應滿足市場對該儀器的需求量:甲不超過200臺儀器季度產量不超過需求量甲200乙不低于180臺儀器季度產量不低于需求量乙180可行解也有無窮多個目標函數:企業產值最高,產值產量銷售價格解 設:甲、乙、丙三種儀器每季度產量分別為,和臺,則該問題的數學模型為:教 學 內 容 與 步 驟備注求一組變量,的值,使其滿足:并使最大例
26、7 進售貨計劃問題某專賣店要制定明年一季度商品進貨及售貨計劃已知該店的倉庫最多可容納該種商品500件,且今年底尚有200件庫存該店每月初進一次貨總店規定明年一季度各月份進貨及售貨單價如下表:月份123買入價869售出價9810問該店各月應分別購入和售出多少件該種商品,可使一季度效益最高?試建立該問題的數學模型分析 決策變量:共6個,分別為各月份買入量和售出量,為便于區分,將買入量分別設為,;將售出量分別設為,約束條件(1)專賣店各月初進貨后擁有商品數量不超過倉庫容量:月份月初量不超過倉庫容量1月5002月5003月500教 學 內 容 與 步 驟備注(2)專賣店各月份銷售商品數量不超過該月該店
27、擁有該商品數量:月份銷售量不超過月初量1月2月3月進、銷貨方案有無窮多個目標函數:一季度效益最高,一季度效益解 設:1、2、3月買入量分別為,;售出量分別為,則該問題的數學模型為:求一組變量,的值,使其滿足:并使最大例8 投資問題某投資公司準備將1千萬元的資金對A、B兩家企業投資對企業A每投資1元,當年底投資公司可獲利0.7元,對企業B每投資1元,第二年底投資公司可獲利2元對企業A、B的投資期限必須分別為一年和兩年的整數倍問應如何投資,可使投資公司在第三年底本利和最大?試建立該問題數學模型分析決策變量:該題的問題“如何投資”指每年分別向兩家企業投資多少因而設分別表示第年向企業A和B的投資額,為
28、列寫模型方便,將有關數據列表如下:年份年初資金對A投資對B投資年底資金1123教 學 內 容 與 步 驟備注約束條件:由于只要有投入,不管投向哪家企業一定有正回報,要想獲得最大本利和,每年必須將手中的資金全部投出去,只不過,投向不同企業、投不同金額回報大小不同而已,因而約束條件應為:每年投資額等于投資公司當年初手中的資金額 目標函數:第三年底本利和最大解 如上表,設分別表示第年向企業A和B的投資額則該問題的數學模型為:求一組變量的值,使其滿足:并使最大例9 配套生產問題某服裝廠加工上衣和褲子,已知加工一件上衣可獲利5元,加工一條褲子可獲利2元,而每個工人加工一件上衣需2小時,加工一條褲子需1小
29、時,由于布料的限制,每個工人每天最多只能安排加工3件上衣和4條褲子若每個工人每天工作8小時,問如何安排,才能使每人每天的利潤最大?試建立該問題的數學模型分析 決策變量:該題中的“如何安排”指每個工人每天生產多少件上衣、多少條褲子,因而設:每天每人加工上衣件,褲子條;約束條件由每個工人每天工作8小時,有;由每天每人生產上衣數不超過3件,有:由每天每人生產褲子數不超過4條,有:產量非負:,且為整數;目標函數:每人每天創造的利潤最大解設:每天每人加工上衣件,褲子條則該問題的數學模型為:求一組變量、的值,使其滿足: 并使最大教 學 內 容 與 步 驟備注例10 配料問題某養雞場有100只雞,用動物飼料
30、和谷物飼料混合喂養,平均每天每只雞吃混合飼料1斤其中動物飼料所占比例不低于20%根據市場調查動物飼料每斤售價為0.1元,谷物飼料每斤0.08元,且飼料公司每周只保證供應谷物飼料500斤問應如何混合才能使飼料成本最低?試建立該問題數學模型分析決策變量:“應如何混合” 指每斤混合飼料中包含動物飼料和谷物飼料分別為多少,也可按每天或每周需消耗兩種飼料數量為決策變量;約束條件:應從總數量和營養要求兩個角度考慮;目標函數:飼料成本最低法一:解設:每斤飼料中含動物飼料斤,谷物飼料斤則該問題的數學模型為:求一組變量,的值,使其滿足:并使最小法二:解設:每周用動物飼料斤,谷物飼料斤則該問題的數學模型為:求一組
31、變量,的值,使其滿足:并使最小例11 植樹問題某班有男同學30人,女同學20人,植樹節準備去植樹,根據以往經驗:男同學平均每人每天可挖坑20個,或栽樹30棵,或給25棵樹澆水;女同學平均每人每天可挖坑10個,或栽樹20棵,或給15棵樹澆水問應如何安排,才能使植樹(包括挖坑、栽樹、澆水)量最多?試建立該問題數學模型分析決策變量:“如何安排”指男生、女生分別有多少人挖坑、栽樹、澆水,共6個決策變量;約束條件目標函數:植樹量最大教 學 內 容 與 步 驟備注解設:男生挖坑、栽樹、澆水人數分別為、人女生挖坑、栽樹、澆水人數分別為、人.則該問題的數學模型為:求一組變量的值,使其滿足:并使植樹量最大例12
32、 配套生產問題某木器公司有A、B、C三個加工廠,接受了為合資飯店趕制一批高檔沙發的任務,每個客房放置一只大沙發和兩只小沙發各工廠每天工作8小時,各廠生產能力為:A廠每天若只做大沙發可做60只,若只做小沙發可做75只;B廠每天若只做大沙發可做15只,若只做小沙發可做30只;C廠每天若只做大沙發可做45只,若只做小沙發可做50只合同規定每天按套交一次貨問應如何安排生產,可使公司每天的總產量最大?試建立該問題的數學模型分析決策變量:可設三個工廠每天生產大、小沙發數量或時間;約束條件目標函數:每天生產沙發套數最多此題涉及數量與時間的轉換,如廠生產能力為:每天工作8小時可做大沙發60只,則廠每小時可作大
33、沙發個;作一個大沙發所用時間為小時法一:設生產時間解設A廠每天生產大、小沙發時間分別為和小時B廠每天生產大、小沙發時間為和小時C廠每天生產大、小沙發時間為和小時則該問題的數學模型為:求一組變量的值,使其滿足:教 學 內 容 與 步 驟備注并使最大法2設生產沙發數量解設A廠每天生產大、小沙發產量為和只B廠每天生產大、小沙發產量為和只C廠每天生產大、小沙發產量為和只則該問題的數學模型為:求一組變量的值,使其滿足:并使最大例13 排班問題某飯店日夜服務,一天24小時所需服務員人數如下表:序號時間所需服務員最少人數12-6326-108310-1410414-187518-2212622-24如果每個
34、服務員每天連續工作8小時,且必須在上述時間段開始時間開始上班試確定滿足以上條件的最少人數試建立該問題的數學模型分析 此題的關鍵是區分以下四種人數:(1)每個時間段上所需最少人數;(2)每個時間段上實際在班上的人數;(3)每個時間段開始上班的人數;(4)飯店所需服務員總人數教 學 內 容 與 步 驟備注該題顯然不能設(1)和(4)為決策變量,設(2)為決策變量顯然也不合適,因為每個時間段在班上的人數由上個時間段開始上班人數和本時間段開始上班人數之和組成,無法進一步分解出有多少人屬于哪一種,也無法表示飯店所需總人數反之,若按各時間段開始上班人數設決策變量,每個時間段在班上的人數及飯店所需服務員總數
35、則可以很容易的表示出來,因而,本題關鍵設每個時間段開始上班人數為決策變量解 設第個時間段開始時間開始上班的人數為則該問題的數學模型為:求一組變量的值,使其滿足:并使最小例14 合理下料問題某廠要做100套鋼架,每套由2根2.9米、2根2.1米和4根1.5米的圓鋼組成已知原料長7.4米問應如何下料,使所用原料最?。吭嚱⒃搯栴}的數學模型分析:所有有關合理下料問題,均應將所有可能的下料方法列寫出來,統計時必須從最長者的最多根數開始有規律遞減,以保證下料方法不重復和遺漏該題所有下了方法如下:下料方法123456782.9米(根)211100002.1米(根)021032101.5米(根)101302
36、34余料(米)0.10.30.901.10.20.81.4解 設第種下料方式用原料根則該問題數學模型為:求一組變量的值,使其滿足:并使最小教 學 內 容 與 步 驟備注例15 合理下料問題例14中考慮到設備調試問題,需要選擇五種余料較少的方法進行套裁,應如何下料,使所用原料最省?試建立該問題的數學模型選第1,2,4,6,7種截法,作為第1,2,3,4,5種截法解 設第種下料方式用原料根則該問題數學模型為:求一組變量的值,使其滿足:并使最小例16 資源利用問題及其對偶問題某工廠利用三種原料生產兩種產品,三種原料的現有存量分別為150、240、300單位,生產單位產品所消耗各種原料的數量及銷售單位
37、產品所能得到的收益如下表: 單耗 產品原料現有存量111502324032300單位收益2.41.8問:(1) 工廠應如何安排生產使總收益最大?試建立該問題的數學模型(2) 若有一企業欲從該廠購買現有原料,這批原料的銷售單價應為多少,可使該廠愿意停止自己生產,而將原料全部出售?試建立該問題數學模型解 (1)設:的產量為單位,的產量為單位則該問題的數學模型為:教 學 內 容 與 步 驟備注求一組變量的值,使其滿足并使最大(2) 分析 設原料的單價分別為,出售原料用于生產所得收益不低于自己生產所得收益:即出售原料用于生產所得收益不低于自己生產的收益:為保證成交,應使買方所付購買費最低,即使最小解設
38、:原料的銷售單價分別為則該問題的數學模型為:求一組變量的值,使其滿足:并使最小稱(2)為(1)的對偶問題通過求解,兩個問題的最優值相等,說明只有當工廠銷售這批原料獲得總收益與利用原料自己生產產品所獲總收益相等時,銷售這批原料才合算例17 工時利用問題及對偶問題某鐵器廠生產甲、乙、丙三種產品,生產一件甲種產品需要1小時車工加工、2小時銑工加工、2小時裝配,獲得利潤100元;生產一件乙種產品需要2小時車工加工、1小時銑工加工、2小時裝配,獲得利潤90元;生產一件丙種產品需要2小時車工加工、1小時銑工加工、1小時裝配,獲得利潤60元工廠每月可供利用的車工加工工時為4200小時、銑工工時為6000小時
39、,裝配工時為3600小時(1) 工廠每月應如何安排生產,使總利潤最大?(2) 如果企業將所有生產能力轉化為來料加工,在不降低經濟效益的情況下,各工種每小時的加工費為多少教 學 內 容 與 步 驟備注將已知條件列表如下工時定額產品工種甲乙丙可利用工時車1224200銑2116000裝配2213600單位利潤 (元)1009060解 (1)設:甲、乙、丙三種產品月產量分別為則該問題的數學模型為:求一組變量的值,使其滿足:并使最大(2)設:車工、銑工、裝配工種每小時加工費分別為元顯然,為外商來料加工所得到的收入應不低于自己生產甲、乙、丙三種產品的利潤由于生產生產一件甲種產品需要1小時車工加工、2小時
40、銑工加工、2小時裝配,獲得利潤100元,將這些工時用于來料加工所得到的收入應不低于100元,即同理,生產乙和丙的工時用于來料加工所得到的收入分別不低于乙和丙的單位利潤目標函數應從每月三個工種工時全部用于來料加工所得到的收入角度考慮,此時不能讓收入最大,因為該收入也即對方的付出,要想通過來料加工獲得收入,必須保證雙方都合適,約束條件保證了工廠的利益,只有目標函數中使對方付出最小時,對方才能接受,因而目標函數應求最小于是,該問題的數學模型為:則該問題的數學模型為:求一組變量的值,使其滿足:并使最小線性規劃 課程教案講稿授課題目(教學章節或主題): 第三章 含有兩個決策變量的線性規劃問題的圖解法授課
41、類型課堂講授授課時間第 周第 節教材分析:1、 線性規劃問題圖解法的含義;2、 含有兩個決策變量的線性規劃問題的圖解法;3、 線性規劃問題解的類型(無可行解、有可行解但無最優解、有唯一最優解、有無窮多個最優解);4、 線性規劃問題解的有關說明;5、 圖解法的應用教學目的與要求:通過本章學習,使學生了解含有兩個決策變量的線性規劃問題圖解法;理解線性規劃數學模型解的含義;掌握線性規劃數學模型解的四種情況(無可行解、有可行解但無最優解、有唯一最優解、有無窮多個最優解)重點與難點:重點: 含有兩個決策變量的線性規劃問題的圖解法難點: 含有兩個決策變量的線性規劃問題的圖解法教學內容與過程(設想、方法、手
42、段) 啟發式教學、課堂精講、講練結合思考題、討論題、作業:參考資料(含參考書、文獻等):教 學 內 容 與 步 驟備注引例 某企業生產甲、乙兩種產品,需消耗A、B、C三種資源,已知生產一件產品甲需消耗2單位資源A、1單位資源B、不消耗資源C;生產一件產品乙需消耗2單位資源A、2單位資源B、4單位資源C已知,該企業現有A資源12單位、B資源8單位、C資源12單位又知每件產品甲和乙的利潤分別為2和3(百元)問應如何安排生產,可使企業利潤最大試建立該問題的數學模型,用圖解法解此模型,給出最優生產方案 為建立數學模型方便,將上述已知條件列成如下表格形式:單耗 產品資源甲乙現有資源A2212B128C0
43、412單位利潤(百元/件)23先建立該問題的數學模型 設:甲、乙兩種產品的產量分別為和則該問題的數學模型為:求一組變量和的值,使其滿足:并使利潤最大 一、線性規劃問題圖解法含義該線性規劃問題僅含有兩個決策變量和,可將兩個決策變量取值組成的有序數組與平面直角坐標系上的點形成一一對應而含有兩個決策變量的線性規劃問題的目標函數為二元線性函數,約束條件為二元一次方程或二元一次不等式,這些均可在平面直角坐標系中通過直線或半平面等表示于是,含有兩個決策變量的線性規劃問題可在平面直角坐標系上通過作圖方式求解 這種通過作圖方式解線性規劃問題的方法稱為線性規劃問題的圖解法 教 學 內 容 與 步 驟備注學習圖解
44、法的意義:(1) 求含有兩個決策變量的線性規劃問題的解;(2) 理解線性規劃問題解的性質和含義 由于線性規劃問題的約束條件為等式約束,或不等式約束及,而我們已知等式約束在平面直角坐標系中表示一條直線,而不等式約束即二元一次不等式在坐標平面內的求解方法及結果還不清楚,因而,我們先學習二元一次不等式的圖解法 二、二元一次不等式的圖解法以為例,分析用圖解法解二元一次不等式的方法 (1) 如圖4-1,建立平面直角坐標系O(2) 先作此為一條直線,找兩個不同點和即可確定這條直線,稱此直線為 圖4-1該直線將整個坐標平面分成兩個半平面:左下方和右上方(3) 分析兩個半平面的特征先分析左下半平面特征:在直線
45、左下方任取一點,過點作軸的垂線,與直線交于一點由于做的是軸的垂線,點與點的橫坐標相同,即由于點在點的上方,有由于點在直線上,滿足直線方程教 學 內 容 與 步 驟備注將上述三個關系聯立,有于是,有即直線左下方點滿足不等式:由于點是直線左下方任意點,故直線左下方所有點都滿足:同理:直線右上方所有點都滿足:(4) 綜上:直線將整個坐標平面分成兩個半平面,其中一個半平面滿足不等式:另一個半平面滿足:可見,二元一次不等式的解為以直線為邊界的半平面一般,二元一次不等式的解為以為分界線的半平面(5) 一般做題時,并不按上述方法找任意點分析判斷解所在的半平面而是在直線外找一已知點代入不等式,觀察不等式是否成
46、立,以判斷解所在的半平面(注意:這里所說的已知點,指該點的橫、縱坐標已知,且該點與直線的關系也已知)用圖解法解二元一次不等式的步驟可歸納如下:(1) 建立平面直角坐標系;(2) 作直線(邊界線);(3) 通過代點法確定解所在的半平面具體方法是:在直線外任取一個已知點,將其橫縱坐標代入不等式,若不等式成立,則該點所在的半平面為不等式的解若不等式不成立,則另一個半平面為不等式的解(4) 用陰影表示不等式的解教 學 內 容 與 步 驟備注例1用圖解法解不等式解如圖4-2 (1) 建立平面直角坐標系;(2) 作直線;(3) 將直線左下方點代入不等式,有:即不等式成立;(4) 不等式的解為直線及直線左下
47、方的半平面O圖4-2例2用圖解法解不等式解如圖4-3(1)建立平面直角坐標系;(2)作直線;(3)將直線左下方點代入不等式,有,即不等式不成立;OO(4)不等式的解為直線及右上方的半平面圖4-3圖4-4教 學 內 容 與 步 驟備注例3用圖解法解不等式組解如圖4-4(1)建立平面直角坐標系;(2)作直線(縱軸),找所在半平面,為縱軸右半平面;作直線(橫軸),找所在半平面,為橫軸上半平面;(3) 不等式組的解為兩者的公共部分第一象限由于含有兩個決策變量的線性規劃問題的約束條件中均含有,故含有兩個決策變量的線性規劃問題的可行解和最優解都在第一象限內,今后用圖解法解線性規劃問題時,著重畫出第一象限即
48、可三、線性規劃問題的圖解法例4 用圖解法解線性規劃問題:解 (1) 建立平面直角坐標系,求可行解集; 先作直線,代點判斷在直線的左下方; 作直線,代點判斷在直線的左下方; 作直線,代點判斷在直線的下方; 表示第一象限; 取上述五個條件的公共部分,得該問題的可行解集為如圖4-5所示的OABCDO(2) 作目標函數初始等值線由于目標函數為,故目標函數初始等值線為,此為一條過點和的直線,用虛線表示由于該直線上所有點的目標函數值都是0,故稱此條直線為目標函數等值線(注意是數值的值,確切的說,應稱為目標函數等值直線)同理我們也可以做出目標函數的其他等值線,如、及等我們發現目標函數等值線彼此平行,故已知一條初始等值線,其它等值線可通過平移方式得到且向一個方向平
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 人工智能視角下的認知科學研究
- 智慧林業推動林業新質生產力的內在機制與發展路徑研究
- 公平原則下個人信息同意機制的法律經濟學分析
- 勞動力市場扭曲的成因機制及其影響效應研究與對策探討
- 高中物理案例教學科學思維培養
- 橋頭飯堂管理辦法細則
- 幼兒園衛生保健人才隊伍建設與培訓體系
- 大氣光學湍流廓線的探測與預測技術研究
- 昭通盆景栽培管理辦法
- 國家安全學習體會
- GB/T 307.4-2017滾動軸承推力軸承 產品幾何技術規范(GPS)和公差值
- GB 29415-2013耐火電纜槽盒
- 《密碼法》培訓只是講座PPT課件(帶內容)
- 建筑工程文件歸檔管理明細表
- 如何解讀血常規報告
- 區域消防安全風險評估規程DB50-T 1114-2021
- 免疫調節治療在腦卒中的運用課件
- 機關檔案管理工作培訓PPT課件
- 25T汽車吊檢驗報告
- 變頻空調中的永磁電機電感分析
- 高考常考語法填空詞性轉換匯總
評論
0/150
提交評論