版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、1.1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型(1) 線性規(guī)劃問題例1、生產(chǎn)組織與計(jì)劃問題A, B 各生產(chǎn)多少, 可獲最大利潤(rùn)?可用資源煤勞動(dòng)力倉庫A B1 23 2 2單位利潤(rùn)40 50306024第1頁/共26頁解: 設(shè)產(chǎn)品A, B產(chǎn)量分別為變量x1, x2根據(jù)題意,兩種產(chǎn)品的生產(chǎn)要受到可用資源的限制,具體講:對(duì)于煤,兩種產(chǎn)品生產(chǎn)消耗量不能超過30,即: x1 + 2x2 30對(duì)于勞動(dòng)力,兩種產(chǎn)品生產(chǎn)的占用量不超過60,即: 3x1 + 2x2 60對(duì)于倉庫,B種產(chǎn)品生產(chǎn)量的2倍不能超過24,即: 2x2 24另外,產(chǎn)品數(shù)不能為負(fù),即: x1,x2 0第2頁/共26頁同時(shí),我們有
2、一個(gè)追求的目標(biāo)-最大利潤(rùn),即: Max Z= 40 x1 +50 x2綜合上述討論,在生產(chǎn)資源的消耗以及利潤(rùn)與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下,把目標(biāo)函數(shù)和約束條件放在一起,可以建立如下的數(shù)學(xué)模型:Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1,x2 0s.t目標(biāo)函數(shù)約束條件類似的例子:教材P4-P5,例1第3頁/共26頁例2 合理配料問題求:最低成本的原料混合方案 原料 A B 每單位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每單位添加劑中維生 12 14 8 素最低含量第4頁/共26頁解:設(shè)
3、每單位添加劑中原料j的用量為xj(j =1,2,3,4) 根據(jù)題意:混合配料后, 每單位添加劑中A的含量不得低于12,即 4x1 + 6x2 + x3+2x4 12 每單位添加劑中B的含量不得低于14,即 x1 + x2 +7x3+5x4 14 每單位添加劑中C的含量不得低于8,即 2x2 + x3+3x4 8 另外,原料使用量不能為負(fù),即: x1,x2 , x3, x4, 0第5頁/共26頁同時(shí),我們有一個(gè)追求的目標(biāo)-成本最低,即: Min Z= 2x1 + 5x2 +6x3+8x4綜合上述討論,在添加劑中各維生素的含量以及成本與原料消耗量成線性關(guān)系的假設(shè)下,把目標(biāo)函數(shù)和約束條件放在一起,可
4、以建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)約束條件Min Z= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12 x1 + x2 + 7x3+5x4 142x2 + x3 + 3x4 8 xj 0 (j =1,4)s.t類似的例子:教材P5-P6,例2第6頁/共26頁例3、運(yùn)輸問題(紡紗廠) 工 廠 1 2 3 庫存 倉 1 2 1 3 50 2 2 2 4 30 庫 3 3 4 2 10 需求 40 15 35運(yùn)輸單價(jià)求:運(yùn)輸費(fèi)用最小的運(yùn)輸方案。第7頁/共26頁解:設(shè)xij為i 倉庫運(yùn)到j(luò)工廠的原棉數(shù)量 其中:i 1,2,3 j 1,2,3Min Z= 2x11 + x12
5、+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 + x12+ x13 50 x21 + x22+ x23 30 x31 + x32+ x33 10 x11 + x21+ x31 = 40 x12 + x22+ x32 = 15x13 + x23+ x33 = 35 xij 0s.t類似的例子:教材P6-P7,例3第8頁/共26頁 2.9m鋼筋架子100個(gè),每個(gè)需用 2.1m 各1,原料長(zhǎng)7.4m 1.5m求:如何下料,使得殘余料頭最少。例4、合理下料問題解:首先列出各種可能的下料方案; 計(jì)算出每個(gè)方案可得到的不同長(zhǎng)度鋼筋的數(shù)量及殘余料頭長(zhǎng)度; 確定決策變
6、量; 根據(jù)不同長(zhǎng)度鋼筋的需要量確定約束方程; 根據(jù)下料目標(biāo)確定目標(biāo)函數(shù)。 第9頁/共26頁設(shè)按第i種方案下料的原材料為xi根8 , 7 , 6 , 5 , 4 , 3 , 2 , 1100432030100002302010000002. .4 . 18 . 02 . 01 . 109 . 03 . 01 . 087654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZMini為大于零的整數(shù),組合方案 1 2 3 4 5 6 7 8 2.9m 2 1 1 1 0 0 0 0 2.1m 0 2 1 0 3 2 1 0
7、 1.5m 1 0 1 3 0 2 3 4 合 計(jì) 7.3m 7.1m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料 長(zhǎng) 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 料 頭 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m第10頁/共26頁(2) 線性規(guī)劃問題的特點(diǎn)l決策變量: (x1 xn)T 代表某一方案, 決策者要考慮和控制的因素非負(fù);l目標(biāo)函數(shù):Z=(x1 xn) 為線性函數(shù),求Z極大或極小;l約束條件:可用線性等式或不等式表示.具備以上三個(gè)要素的問題就稱為 線性規(guī)劃問題。第11頁/共26頁0,.212
8、21122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目標(biāo)函數(shù)約束條件(3) 線性規(guī)劃模型一般形式第12頁/共26頁隱含的假設(shè)隱含的假設(shè)l比例性:決策變量變化引起目標(biāo)的改變量與決策變量比例性:決策變量變化引起目標(biāo)的改變量與決策變量改變量成比例(即線性關(guān)系假定,比例可能會(huì)不同)改變量成比例(即線性關(guān)系假定,比例可能會(huì)不同)l可加性:每個(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄淇杉有裕好總€(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌兞克兞縧連續(xù)性:每個(gè)決策變量取連續(xù)值連續(xù)性:每個(gè)決策變量取連續(xù)值l確定性:線性規(guī)劃
9、中的參數(shù)確定性:線性規(guī)劃中的參數(shù)aij , bi , cj為確定值為確定值第13頁/共26頁1.2 線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法 20,.1XbAXtsCXZMinMax定義2:滿足約束(2)的X=(X1 Xn)T稱為線性規(guī)劃問題的可行解,全部可行解的集合稱為可行域。定義3:滿足(1)的可行解稱為線性規(guī)劃問題的最優(yōu)解。定義1:一組決策變量X=(X1 Xn)T的集合稱為一個(gè)解。第14頁/共26頁例1 Max Z= 40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t第15頁/共26頁解:(1) 確定可行域 X1+2X2 30 3X1+2
10、X2 60 2X2 24 X1 0 X2 02030100102030X2DABC2X2 24X1+2X2 303X1+2X2 60X1 0X2 0可行域第16頁/共26頁(2) 求最優(yōu)解最優(yōu)解:X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0), (10,-8)C點(diǎn): X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC最優(yōu)解Z=975可行解Z=0等值線第17頁/共26頁例2、 Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t第18頁/共26頁
11、解:(1) 確定可行域與上例完全相同。 (2) 求最優(yōu)解0203010102030DABC最優(yōu)解Z=1200最優(yōu)解:BC線段X1X2第19頁/共26頁最優(yōu)解:BC線段B點(diǎn):X(1)=(6,12) C點(diǎn):X(2)=(15,7.5)X=X(1)+(1-)X(2) (0 1) Max Z=1200 X1 6 15 X2 12 7.5X= = +(1- )X1 =6 +(1- )15X2=12+(1- )7.5X1 =15-9X2 =7.5+4.5 (0 1)第20頁/共26頁例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0s.tZ=08246X240X1-2
12、X1+X2 22X1+X2 8X1 0X20可行域無界無有限最優(yōu)解可行域無上界無有限最優(yōu)解第21頁/共26頁例4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0無可行域無可行解-1X2-1X10s.tX2 0X1 0-X1 -X2 1第22頁/共26頁直觀結(jié)論直觀結(jié)論若線性規(guī)劃問題有解,則可行域是一個(gè)凸多邊若線性規(guī)劃問題有解,則可行域是一個(gè)凸多邊形(或凸多面體);形(或凸多面體);若線性規(guī)劃問題有最優(yōu)解,則若線性規(guī)劃問題有最優(yōu)解,則唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn);唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn);無窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊;無窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊;若線性規(guī)劃問題有可行解,但無有限最優(yōu)解,若線性規(guī)劃問題有可行解,但無有限最優(yōu)解,則可行域必然是無界的;則可行域必然是無界的;若線性規(guī)劃問題無可行解,則可行域必為空集。若線性規(guī)劃問題無可行解,則可行域必為空集。第23頁/共26頁第一章作業(yè)第一章作業(yè)P P1616-P-P1717:6:6、7 7、8 8、9 9、1010中任選三題中任選三題第24頁/共26頁思
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 內(nèi)蒙古呼倫貝爾市鄂倫春自治旗2024-2025學(xué)年七年級(jí)上學(xué)期期末生物試題(含答案)
- 2021年國(guó)家電網(wǎng)招聘(其他工學(xué)類)考試題庫(真題導(dǎo)出版)
- 《約哈里之窗》課件
- 2017建筑安全資料管理規(guī)程
- 《蘇州影響力品牌評(píng)價(jià)通則》編制說明
- 2024年濱??h人民醫(yī)院高層次衛(wèi)技人才招聘筆試歷年參考題庫頻考點(diǎn)附帶答案
- 2024年渠縣中醫(yī)院高層次衛(wèi)技人才招聘筆試歷年參考題庫頻考點(diǎn)附帶答案
- 2024年淮南市紡織廠職工醫(yī)院高層次衛(wèi)技人才招聘筆試歷年參考題庫頻考點(diǎn)附帶答案
- 家庭生活小幫手(說課稿)-2023-2024學(xué)年三年級(jí)下冊(cè)綜合實(shí)踐活動(dòng)滬科黔科版
- 周圍靜脈輸液法操作并發(fā)癥及預(yù)防
- 車間現(xiàn)場(chǎng)安全培訓(xùn)內(nèi)容課件參考
- 油藏工程-油藏物質(zhì)平衡方法-1課件
- 三上書法《撇》教學(xué)課件
- 河北省廊坊市藥品零售藥店企業(yè)藥房名單目錄
- 超星爾雅學(xué)習(xí)通《三國(guó)志導(dǎo)讀》章節(jié)測(cè)試(含答案)
- 簡(jiǎn)單的個(gè)人原因辭職報(bào)告(通用17篇)
- 交響曲欣賞-完整版PPT
- 公司軟件銷售管理制度
- micro810可編程控制器用戶手冊(cè)
- CVC導(dǎo)管維護(hù)技術(shù)評(píng)分標(biāo)準(zhǔn)
- 東風(fēng)7C型(DF7C)內(nèi)燃機(jī)車
評(píng)論
0/150
提交評(píng)論