版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
運籌帷幄之中決勝千里之外線性規(guī)劃LinearProgramming第一章線性規(guī)劃及單純形法一般線性規(guī)劃問題的數(shù)學(xué)模型圖解法單純形法原理單純形法的計算步驟單純形法的進(jìn)一步討論應(yīng)用舉例第一節(jié)一般線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的標(biāo)準(zhǔn)型及其標(biāo)準(zhǔn)化線性規(guī)劃問題解的含義一、線性規(guī)劃的發(fā)展1939年,前蘇聯(lián)數(shù)學(xué)家康托洛維奇用線性模型研究提高組織和生產(chǎn)效率問題1947年,Dantzig提出求解線性規(guī)劃的單純形法1950-1956年,主要研究線性規(guī)劃的對偶理論1958年,發(fā)表整數(shù)規(guī)劃的割平面法1960年,Dantzig和Wolfe研究成功分解算法,奠定了大規(guī)模線性規(guī)劃問題理論和算法的基礎(chǔ)。1979年,Khachiyan,1984年,Karmarkaa研究成功線性規(guī)劃的多項式算法。另外,很多現(xiàn)代算法研究如進(jìn)化、神經(jīng)網(wǎng)絡(luò)等。解:一般方法是在鐵皮的四個角上剪去四個邊長各為x的正方形,折疊做成一個容器,則容積為V=(a-2x)2·x。要讓容積最大即確定x(0≤x≤a)的值,使V達(dá)到最大。
ax圖1-1二、問題的提出例1.1用一塊長為a的正方形鐵皮做一個容器,應(yīng)如何剪裁,使做成的容器的容積為最大(見圖1-1)例1.2Maxz=2x1+3x22x1+2x2≤12
x1+2x2≤84x1≤164x2≤12
x1,x2≥0例1.3
某工廠在計劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn),已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制,如下表。問題:工廠應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多?Maxz=50x1+100x2
x1+x2≤3002x1+x2≤400x2≤250
x1
,x2≥0例1.4套裁下料問題
某工廠要做100套鋼架,每套用長為2.9m,2.1m,1.5m的圓鋼各一根,已知原料每根長7.4m。應(yīng)如何下料,可使所用原料最???解:共可設(shè)計下列5種下料方案設(shè)x1,x2,x3,x4,x5
分別為上面5種方案下料的原料根數(shù)。建立數(shù)學(xué)模型如下目標(biāo)函數(shù):Minz=0.1x2+0.2x3+0.3x4+0.8x5
約束條件:s.t.x1+2x2+x4=1002x3+2x4+x5=1003x1+x2+2x3+3x5=100
x1,x2,x3,x4,x5≥0總結(jié)提出問題類似的例子可以舉出很多。歸結(jié)起來有兩種情況:一是給定資源,如何充分利用二是給定計劃,研究如何統(tǒng)籌安排,用最少的人力物力去完成都是求極值的問題,有些問題可以用微積分解決,但例中除了要求變量非負(fù)外帶了很多附加條件,解決這類問題就是運籌學(xué)中規(guī)劃論研究的內(nèi)容?!艟€性規(guī)劃的三個要素決策變量:(x1,x2),一組值代表一個方案目標(biāo)函數(shù):max或min約束條件:不等式或等式◆線性規(guī)劃:目標(biāo)函數(shù)、約束條件均為線性函數(shù)三、線性規(guī)劃的數(shù)學(xué)模型1.一般形式?jīng)Q策變量:X=(x1,x2,…..,xn)T目標(biāo)函數(shù):max(minz)=c1x1+c2x2+…+cnxn約束條件:
a11x1+a12x2+……..+a1nxn≤(=≥)b1
a21x1+a22x2+……..+a2nxn≤(=≥)b2
…………am1x1+am2x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0
其中,“max(minz)”是“maximize(minimize)的縮寫,含義為“最大化(最小化)”2.一般形式的其它寫法①求和形式②向量形式目標(biāo)函數(shù):
Max(Min)z=CX約束條件:s.t.X≥0其中C=(c1,c2,…,cn)③矩陣形式?jīng)Q策變量常數(shù)項系數(shù)矩陣價值系數(shù)四、線性規(guī)劃數(shù)學(xué)模型的建立1.建模條件(1)優(yōu)化條件:問題所要達(dá)到的目標(biāo)能用線型函數(shù)描述,且能夠用極值(max或min)來表示;(2)限定條件:達(dá)到目標(biāo)受到一定的限制,且這些限制能夠用決策變量的線性等式或線性不等式表示;(3)選擇條件:有多種可選擇的方案供決策者選擇,以便找出最優(yōu)方案。2.建模步驟(1)確定決策變量:即需要我們作出決策或選擇的量。一般情況下,題目問什么就設(shè)什么為決策變量。(2)找出所有限定條件:即決策變量受到的所有的約束;(3)寫出目標(biāo)函數(shù):即問題所要達(dá)到的目標(biāo),并明確是max還是min。例1.5混合配料問題某糖果廠用原料1、2、3加工三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中原料1、2、3的含量、原料每月限用量、三種牌號糖果的加工費及售價,如下表所示。該廠每月如何生產(chǎn)才能獲利最大?解:用i=1,2,3代表原料1、2、3,j=1,2,3代表糖果甲、乙、丙。xij表示第j種產(chǎn)品中原料i的含量,則對于原料1:x11,x12
,x13
;對于原料2:x21,x22,x23
;對于原料3:x31
,x32
,x33
;對于甲:x11
,x21
,x31
;對于乙:x12,x22,x32
;對于丙:x13
,x23
,x33
;目標(biāo)函數(shù):利潤最大,利潤=收入-原料成本-加工費約束條件:原料用量限制,含量限制maxz=(3.4-0.5)(x11+x21+x31)+(2.85-0.4)(x11+x22+x32)+(2.25-0.3)(x13+x23+x33)-2(x11+x12+x13)-1.5(x21+x22+x23)-1(x31+x32+x33)x11+x12+x13≤2000(供應(yīng)量限制)
x21+x22+x23≤2500
x31+x32+x33≤1200x11≥0.6(x11+x21+x31)(含量限制)
x31≤0.2(x11+x21+x31)
x12≥0.3(x12+x22+x32)x32≤0.5(x11+x22+x32)x33≤0.6(x13+x23+x33)
xij≥0,i=1,2,3;j=1,2,3五、線性規(guī)劃的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式目標(biāo)函數(shù):maxz=c1x1+c2x2+…+cnxn約束條件:
a11x1+a12x2+……..+a1nxn=b1
a21x1+a22x2+……..+a2nxn=b2
………………am1x1+am2x2+……..+amnxn=bmx1,x2,……xn≥0,b1,b2,……bm≥0◆非標(biāo)準(zhǔn)形式如何化為標(biāo)準(zhǔn)形式目標(biāo)函數(shù)極小化Minz=c1x1+c2x2+…+cnxn令z′=-z,則
Maxz′=(-c1x1)
+(-c2x2)
+…+(-cnxn)兩個問題最優(yōu)解相同,最優(yōu)值相差一個符號,即
Minz=-Maxz′約束條件為不等式ai1x1+ai2x2+…+ainxn≤bi引進(jìn)一個新的變量s,
s=bi–(ai1x1+ai2x2+…+ainxn)顯然,s≥0這時新的約束條件成為
ai1x1+ai2x2+…+ainxn+s=biS——松弛變量,在實際問題中表示未被充分利用的資源數(shù),未被轉(zhuǎn)化為價值和利潤,在目標(biāo)函數(shù)中系數(shù)為零.ai1x1+ai2x2+…+ainxn≥bi引進(jìn)一個新的變量t,
t=(ai1x1+ai2x2+…+ainxn)–bi顯然,t≥0這時新的約束條件成為
ai1x1+ai2x2+…+ainxn-t=bit——剩余變量,在實際問題中表示超用資源數(shù),未被轉(zhuǎn)化為價值和利潤,在目標(biāo)函數(shù)中系數(shù)為零如約束條件為
2x1+2x2≤12可令x3=12-2x1-2x2則新的約束條件為
2x1+2x2+
x3=12x3為松弛變量,x3≥0如約束條件為
2x1+2x2≥
12可令x4=2x1+2x2-12則新的約束條件為
2x1+2x2-
x4=12x4為剩余變量,x4≥0右端項有負(fù)值如bi<0則把該等式約束兩端同時乘以-1,得到:
-ai1x1-ai2x2-…-ainxn=-bi
變量取負(fù)值如xi≤0,令xi'=-xi
,則xi'≥0變量無約束如x無約束,令x=x′-x′′,其中x′≥
0,x′′≥0例1.6
將以下線性規(guī)劃問題化為標(biāo)準(zhǔn)形式
minZ=x1+2x2+3x3s.t.-2x1+x2+x3≤9-3x1+x2+2x3
≥43x1-2x2-3x3=-6x1≤0
,x2≥0
,x3取值無約束。解:首先令z′=-z,x3=x′3-x′′3,其中x′3≥
0,x′′3≥0,
x′1=-x1,其中x′1≥
0,考慮約束,引進(jìn)松弛變量x4≥0
、剩余變量x5≥0再次等式約束其右端項為負(fù)數(shù),所以兩邊同乘以-1,得到-3x′1
+2x2+3x′3-3x′′3
=6問題轉(zhuǎn)化為:
maxZ′=x′1
-2x2-3x′3+3x′′3
+0x4+0x5s.t.2x′1
+x2+x′3-x′′3
+x4=93x′1
+x2+2x′3-2x′′3
-x5=43x′1
+2x2+3x′3-3x′′3
=6x′1,x2,x′3,x′′3,x4,x5≥0
練習(xí)1.6(a)解:首先令z′=-z,x2=x′2-x′′2,其中x′2≥
0,x′′2≥0,
x′3=-x3,其中x′3≥
0,考慮約束,引進(jìn)松弛變量x4≥0
、剩余變量x5≥0問題轉(zhuǎn)化為:
六、線性規(guī)劃問題的解對于線性規(guī)劃問題maxCTX(1.1a)
(LP)s.t.AX≤b(1.1b)
X≥0(1.1c)其中,C,XRn,bRm,Amn矩陣有以下幾個概念(單純形法中詳細(xì)介紹):1.可行解(feasiblesolution)
滿足(1.1b)(1.1c)X=(x1,x2,…..,xn)T稱為線性規(guī)劃問題(LP)的可行解。全部可行解的集合稱為可行域。2.最優(yōu)解(optimalsolution)
使目標(biāo)函數(shù)(1.1a)達(dá)到最大值的可行解成為最優(yōu)解。3.基設(shè)n>m,A的秩為m。B是矩陣A中的一個mm階的滿秩矩陣,稱B是線性規(guī)劃問題的一個基。不失一般性,設(shè)
=(P1,···,Pm),B中的每一個列向量Pj(j=1,···m)稱為基向量,與基向量Pj對應(yīng)的變量xj稱為基變量。線性規(guī)劃除基變量以外的其他變量稱為非基變量。4.基解在約束方程組(1.1b)中,令所有非基變量xm+1=xm+2=··
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年度甘肅省安全員之A證(企業(yè)負(fù)責(zé)人)全真模擬考試試卷B卷含答案
- 2024年毛發(fā)化學(xué)品:洗發(fā)精合作協(xié)議書
- 簡單的頂房合同(2篇)
- 鋼鐵廠續(xù)簽合同(2篇)
- 2024年非鐵分選提純設(shè)備項目發(fā)展計劃
- 2024年自配合組合電器項目建議書
- 2024年辦公商業(yè)空間設(shè)計項目發(fā)展計劃
- 高效快遞運輸線路外包合同
- 2024版合同-民事合同
- 2024版合同服務(wù)項目合同合同創(chuàng)新報告
- 哈工大機械原理課程設(shè)計-棒料輸送線布料裝置(方案1)
- 食堂驗收記錄表
- 進(jìn)料檢驗控制程序QPQC-05
- 節(jié)約用電主題班會
- 中國移動CA認(rèn)證中心證書辦理常見問題
- 農(nóng)用地估價技術(shù)報告
- 祖國在我心中 ppt
- 原發(fā)性膽汁性膽管炎的病理特點及其鑒別診斷
- 運輸技術(shù)經(jīng)濟學(xué)-運輸項目的綜合評價與決策課件
- 保險經(jīng)紀(jì)服務(wù)委托協(xié)議書模板(3篇)
- 腦與認(rèn)知科學(xué)概論PPT(第2版)完整全套教學(xué)課件
評論
0/150
提交評論