




已閱讀5頁,還剩49頁未讀, 繼續(xù)免費閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
上堂課主要內(nèi)容:,一、線性規(guī)劃模型引例,二、線性規(guī)劃模型的建立,1、建模的一般步驟: 步驟一:確定決策變量 即用變量取不同的值來表示可供選擇的各種不同方案,步驟二:建立目標函數(shù),即找到目標值與決策變量的數(shù)量關(guān)系,步驟三:確定約束條件,即決策變量所受到的外界條件的制約。,約束條件一般為決策變量的等式或不等式,要求:目標函數(shù)與約束條件均是線性的, 且目標函數(shù)只能是一個。,2、線性規(guī)劃模型的一般形式:,決策變量,約束方程,非負約束,目標函數(shù),三、線性規(guī)劃求解:,四、線性規(guī)劃應用舉例,計算機應用軟件,例3 福安商場是個中型的百貨商場,它對售貨人員的 需求經(jīng)過統(tǒng)計分析如下所示:,為保證售貨人員充分休息, 售貨人員每周工作五天,休 息兩天,并要求休息的兩天 是連續(xù)的,問應該如何安排 售貨人員的作息,既滿足了 工作的需要,又使配備的售 貨人員的人數(shù)最少?,解,約束條件 :,星期日 售貨員人數(shù)要求:,星期一 售貨員人數(shù)要求:,星期二 售貨員人數(shù)要求:,星期三 售貨員人數(shù)要求:,星期四 售貨員人數(shù)要求:,星期五 售貨員人數(shù)要求:,星期六 售貨員人數(shù)要求:,數(shù)學模型:,非負約束 :,數(shù)學模型:,解得:,例3 福安商場是個中型的百貨商場,它對售貨人員的 需求經(jīng)過統(tǒng)計分析如下所示:,為保證售貨人員充分休息, 售貨人員每周工作五天,休 息兩天,并要求休息的兩天 是連續(xù)的,問應該如何安排 售貨人員的作息,既滿足了 工作的需要,又使配備的售 貨人員的人數(shù)最少?,解,方案,下料數(shù),(根),長度,例4 某工廠要做100套鋼架,每套用長為2.9m,2.1m, 和1.5m的圓鋼各一根,已知原料每根長7.4m, 問應如何下料,可使所用原料最省.,分析:,每根原料做一套鋼架,下角料:,0.9m,用套裁方式,下料方案:,方案,下料數(shù),(根),長度,下料方案:,方案,下料數(shù),(根),長度,例4 某工廠要做100套鋼架,每套用長為2.9m,2.1m, 和1.5m的圓鋼各一根,已知原料每根長7.4m, 問應如何下料,可使所用原料最省.,下料方案:,最優(yōu)下料方案:,按方案1下料30根,,方案2下料10根,,方案4下料50根,,共需原料90根。,例5 (產(chǎn)品配套問題)假定一個工廠的甲、乙、丙三個車間生產(chǎn)同一個產(chǎn)品,每件產(chǎn)品包括4個A零件,和3個B零件。這兩種零件由兩種不同的原材料制成,而這兩種原材料的現(xiàn)有數(shù)額分別為100克和200克。每個生產(chǎn)班的原材料需要量和零件產(chǎn)量如下表所示。,問這三個車間各應開多少班才能使這種產(chǎn)品的配套數(shù)達到最大,約束條件為:,三個車間共生產(chǎn)A零件:,三個車間共生產(chǎn)B零件,非線性,要求:,目標函數(shù):,目標函數(shù) Z=x4,線性,數(shù)學模型:,線性規(guī)劃問題,例6 (多周期動態(tài)生產(chǎn)計劃問題)華津機器制造廠專為拖拉機廠配套生產(chǎn)柴油機,今年頭四個月收到的定單數(shù)量分別為3000臺、4500臺、3500臺、5000臺。該廠正常生產(chǎn)每月可生產(chǎn)3000臺,利用加班還可生產(chǎn)1500臺,正常生產(chǎn)成本為每臺5000元,加工生產(chǎn)還要追加1500元,庫存成本為每臺每月200元。問華津廠如何組織生產(chǎn)才能使生產(chǎn)成本最低?,分析:,設(shè)C=成本,=四個月正常生產(chǎn)的成本,+四個月加班生產(chǎn)的成本,+四個月庫存成本,約束條件:,需求約束:,第4個月,第3個月,第2個月,第1個月,生產(chǎn)能力約束:,數(shù)學模型:,四個月定單數(shù)量分別為3000臺、4500臺、3500臺、5000臺,每月可生產(chǎn)3000臺,利用加班還可生產(chǎn)1500臺,庫存約束:,例7.連續(xù)投資問題建模:某投資公司有100萬元資金用于投資,投資的方案可以有以下六種,現(xiàn)要做一個5年期的投資計劃,具體可選擇的投資方案如下: 方案A:5年內(nèi)的每年年初均可投資,且金額不限,投資期限1 年,年投資回報率7%。 方案B:5年內(nèi)的每年年初均可投資,且金額不限,投資期限2 年,年投資回報率10%(不計復利)。 方案C:5年內(nèi)的每年年初均可投資,且金額不限,投資期限3 年,年投資回報率12%(不計復利) 方案D:只在第一年年初有一次投資機會,最大投資金額為50 萬元,投資期限4年,年投資回報率20% 方案E:在第二年和第四年年初有一次投資機會,最大投資金額 均為30萬元,投資期限1年,年投資回報率30% 方案F:在第四年年初有一次投資機會,金額不限,投資期限2 年,年投資回報率25%,假設(shè)當年的投資金額及其收益均可用于下一年的投資,問公司應如何投資才能使第五年末收回的資金最多?,假設(shè)當年的投資金額及其收益均可用于下一年的投資,問公司應如何投資才能使第五年末收回的資金最多?,連續(xù)投資問題模型:,1.1.2、線性規(guī)劃的標準形式和矩陣表達式,線性規(guī)劃問題的一般形式:,1、線性規(guī)劃的標準形式,標準型式的特征:,1、求目標函數(shù)的最大值,2、約束方程為等式方程,3、約束方程的右邊非負,4、決策變量均非負,非標準型式有以下幾種可能:,1、求目標函數(shù)的最小值,4、決策變量0或無限制,2、約束方程為不等式方程,3、約束方程的右邊,2、非標準型式線性規(guī)劃問題的標準化,-,max,(1)對求目標函數(shù)最小值:,=,(2)約束條件為“”型,松弛變量,(3)約束條件為“”型,剩余變量,(4) 約束條件右邊為負,(6)決策變量無符號限制,(5)決策變量0,例如,帶入約束方程及目標函數(shù),則原線性規(guī)劃問題的標準型為:,3. 線性規(guī)劃問題的矩陣表達式:,1.3 線性規(guī)劃的基本理論,一、線性規(guī)劃的解 1、可行解:,2、可行域:,(LP)的全體可行解構(gòu)成的集合稱為可行域,3、最優(yōu)解及最優(yōu)值:,設(shè)S是(LP)的可行域,不唯一,唯一,4、若對任意大的M0,都存在可行解使得該線性規(guī)劃的目標 函數(shù)值,,則稱該線性規(guī)劃問題無界,二、兩個變量的線性規(guī)劃的圖解法,解: (1)在直角坐標系上畫出可行域,(2)做目標函數(shù)的等值線,0,可行域,凸多邊形,頂點,.,解: (1)在直角坐標系上畫出可行域,(2)做目標函數(shù)的等值線,0,無窮多,.,.,解: (1)在直角坐標系上畫出可行域,(2)做目標函數(shù)的等值線,0,目標函數(shù)無上界,,該問題無界,無最優(yōu)解,解: (1)在直角坐標系上畫出可行域,0,可行域為空集,無可行解,該問題無最優(yōu)解,圖解法的基本步驟:,(一般是一個凸多邊形),注意:若是求目標函數(shù)的最小值,,目標函數(shù)直線向下移動,關(guān)于線性規(guī)劃解的結(jié)論:,1、若(LP)問題有可行解,則可行域是一個凸多邊形 (或凸多面體)。它可能是有界的;也可能是無界的。,2、若(LP)問題有最優(yōu)解,則最優(yōu)解可能是唯一的;也可能 是無窮多個。如果是唯一的,這個解一定在該凸多邊形的某 個頂點上;如果是無窮多個,則這些最優(yōu)解一定充滿凸多邊 形的一條邊界(包括此邊界的兩個頂點),總之,若(LP)問題有最優(yōu)解,則最優(yōu)解一定可以在凸多邊 形的某個頂點達到,3、若(LP)問題有可行解,但沒有有限最優(yōu)解,此時凸多邊形 是無界的,(反之不成立),4、若(LP)問題沒有可行解,則該問題沒有最優(yōu)解,三、基與基本可行解,不妨設(shè)AX=b有解,且mn,利用線性代數(shù)的方法求出無窮多解?,只討論rn, 此時,且r(A)=r=m,(若rm,必有多余方程,可去掉),由線性代數(shù)結(jié)論知: 若r(A)=m,則A 中至少存在一個m階子式 |B|0,即A中存在滿秩的m階矩陣B,稱B為(LP)問題的一個基,不妨設(shè)mn,定義1.3 在(LP)問題中,A的任意一個mm階 的非奇異子方陣B(即|B|0)稱為 (LP)問題的一個基,一個線性規(guī)劃問題最多有 基,設(shè)r(Amxn)=r=m,設(shè)r(A)=mn,不妨設(shè)A的前m列構(gòu)成A的一個基,基變量,非基變量,基,基,非基,由于B 可逆,基本解,定義1.4 設(shè)B是(LP)問題的一個基,,A=(B,N),稱此解為對應于基B的基本解,自由未知量,基,非基,定義1.5,基本可行解的個數(shù),基本可行解,對應的基稱為可行基,基,非基,基本可行解,可行基,A的任意一個mm階的非奇異子方陣B,設(shè)r(A)=r=m,基:,基本解:,基本可行解:,可行 解,基本 解,基本可行解,有限,設(shè)X為基本可行解,,則X的n個分量中,最多有 個分量0,基本可行解,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 如何防范數(shù)據(jù)安全漏洞
- 人防工程施工中的勞動保障與工人健康管理
- 人防工程施工中的環(huán)境影響評估與控制
- 文化藝術(shù)與社會發(fā)展的互動關(guān)系
- 2025年秋季學期江蘇省南京市七年級下學期期末數(shù)學試卷(含邏輯推理2025年應用題)
- T-WHCIA 1003-2023 全過程工程咨詢服務管理標準
- 師風師德演講培訓81
- 牦牛產(chǎn)業(yè)鏈中冷鏈物流的創(chuàng)新模式
- 青少年群體對民俗文化的認知與體驗路徑
- 鋼琴藝術(shù)全解析
- 物流信息技術(shù)課程
- Q∕GDW 10354-2020 智能電能表功能規(guī)范
- 公安局凍結(jié)解除凍結(jié)存款匯款通知書
- (高清正版)JJF 1908-2021 雙金屬溫度計校準規(guī)范
- 硬式內(nèi)窺鏡項目計劃書_模板范本
- 皮內(nèi)注射--ppt課件
- 最新防雷設(shè)施檢測報告范本
- 雨林木風壁紙
- 上海初中科學會考知識點匯總——七年級第一學期牛津
- 計算機辦公軟件應用培訓教學計劃
- 專業(yè)技術(shù)人員年度情況考核登記表
評論
0/150
提交評論