




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
Chapter5線性規(guī)劃LinearProgramming5.1標準型
StandardformofLP5.2單純形法
SimplexMethod5.1線性規(guī)劃的標準型StandardformofLP04二月20233
在用單純形法求解線性規(guī)劃問題時,為了討論問題方便,需將線性規(guī)劃模型化為統(tǒng)一的標準形式。5.1線性規(guī)劃的標準型StandardformofLP線性規(guī)劃問題的標準型為:1.目標函數(shù)求最大值;2.約束條件都為等式方程;3.變量xj非負;4.常數(shù)bi非負.04二月20234max
Z=c1x1+c2x2+…+cnxn5.1線性規(guī)劃的標準型StandardformofLP線性規(guī)劃問題的標準型為:04二月2023504二月2023604二月20237注:化標準型的方法1、目標極小化極大:min(f)=--max(-f)2、不等式化等式:(1)大于等于“≥”:在左邊減去乘余變量()≥b
()--s=b(2)小于等于“≤”:在左邊添加松馳變量()≤b
()+t=b04二月202383、常數(shù)項負化正:兩邊乘(-1)4、變量負化正:乘(-1)5、自由變量(無要求)04二月202396、對于a≤x≤b(a、b均大于零)的有界變量化為標準形式有兩種方法。
一種方法是增加兩個約束x≥a及x≤b
另一種方法是令x‘=x-a,則a≤x≤b等價于
0≤x‘≤b-a,增加一個約束x'≤b-a
并且將原問題所有x用x=x'+a替換。04二月202310
當某個約束是絕對值不等式時,將絕對值不等式化為兩個不等式,再化為等式,例如約束將其化為兩個不等式
再加入松馳變量化為等式。1.3線性規(guī)劃的標準型StandardformofLP1.2單純形法SimplexMethod04二月202312一、典范式線性規(guī)劃的單純形法1.形如:典范式線性規(guī)劃04二月202313典范式線性規(guī)劃04二月202314典范式線性規(guī)劃04二月202315典范式線性規(guī)劃04二月202316典范式線性規(guī)劃04二月202317典范式線性規(guī)劃04二月202318(1)系數(shù)矩陣2.基本概念04二月202319系數(shù)矩陣列向量04二月202320
單位陣.
單位向量.04二月202321其余列向量稱為非基向量
單位向量對應(yīng)的列向量稱為基向量(2)基向量與非基向量
基向量非基向量04二月202322基向量對應(yīng)的變量稱為基變量,非基向量對應(yīng)的變量稱為非基變量
基向量非基向量(2)基變量與非基變量
基變量04二月202323(4)基本解
(basissolution)令非基變量等于零,由方程組
AX=b解出基變量,則這組解稱為方程組的基本解。令則方程組為04二月202324則基本解為令則方程組為04二月202325(5)基本可行解(basis
feasiblesolution)
若基本解是可行解則稱為是基本可行解(也稱基可行解)可行點(解):滿足所有約束條件的點04二月202326基本可行解04二月202327(6)檢驗數(shù)的檢驗數(shù):04二月20232804二月202329(7)單純形表211040130130340000340004二月2023303.單純形法計算步驟:(1).求初始基可行解:根據(jù)典范式列出初始單純形表。(2).最優(yōu)解判斷:(a)若檢驗數(shù)λj≤0(j=1,2,…,n)得到最優(yōu)解;(b)某個檢驗數(shù)λk>0且aik≤0(i=1,2,…,m)則線性規(guī)劃無最優(yōu)解(具有無界解)。(c)若對λk>0,都有aik(i=1,…,m)不全為負,則進行換基;04二月202331第L個比值最小,選最小比值對應(yīng)行的基變量為出基變量,aLk為主元素;
(c)求新的基可行解:用行變換方法將aLk
化為1,其所在列的其它元素化為零,得到新的可行基及基本可行解,再判斷是否得到最優(yōu)解。(b)選出基變量
:求最小比值(3).換基(換基可行解):(a)選進基變量設(shè)λk=max{λj|λj>0},xk為進基變量04二月202332【例1】用單純形法求下列線性規(guī)劃的最優(yōu)解04二月202333【解】化為標準型,加入松馳變量x3、x4則標準型為1.5單純形法
SimplexMethod04二月202334初始單純形表比值211040130130340000340004二月202335進基列出基行bi/ai2,ai2>0θi表1-4(1)XBx1x2x3x4bx3211040x4130130λj3400
(2)x3x2λj
(3)x1
x2
λj
基變量110001/301/3105/31-1/3405/30
-4/330103/5-1/51801-1/52/5400-1-1將3化為1乘以1/3后得到1.5單純形法
SimplexMethod30183
4
0
0
0
0
0
4
4
3
04二月202336最優(yōu)解X=(18,4,0,0)T,最優(yōu)值Z=70O20301040(3,4)X(3)=(18,4)最優(yōu)解X=(18,4)最優(yōu)值Z=70X(1)=(0,0)2010x2x1301.5單純形法
SimplexMethodX(2)=(0,10)04二月202337【例2】
用單純形法求解【解】將數(shù)學模型化為標準形式:不難看出x4、x5可作為初始基變量,單純法計算結(jié)果如表1.5所示。1.5單純形法
SimplexMethod04二月202338Cj12
100bθCBXBx1x2x3x4x50x42-3210150x51/3-150120λj12100
0x4
2x2λj
1x1
2x2
λj
表1-51/3150120301713751/30-90-22025601017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最優(yōu)解X=(25,35/3,0,0,0)T,最優(yōu)值Z=145/31.5單純形法
SimplexMethod04二月202339【例3】求解線性規(guī)劃【解】化為標準型1.5單純形法
SimplexMethod04二月202340比值3-21012-1014-110000-1100初始單純形表為04二月202341λ2=1>0,
而a12<0,a22<0,沒有比值,從而線性規(guī)劃的最優(yōu)解無界。比值3-21012-1014-110000-110004二月202342由模型可以看出,當固定x1使x2→+∞且滿足約束條件,還可以用圖解法看出具有無界解。04二月202343【例4】求解線性規(guī)劃【解】:化為標準型1.5單純形法
SimplexMethod04二月202344用單純形法計算如下表所示04二月202345
C24000CBXBx1x2x3x4x5bθ000x3x4x5-111[2]2-11000100014→10225—λj24↑000400x2x4x5-1/2[2]1/21001/2-11/201000126→4—38λj4↑0-200420x2x1x50101001/4-1/2[3/4]1/41/2-1/40017/235/2→14—10/3λj000↑-20420x2x1x30101000011/31/3-1/3-1/32/34/38/314/310/3λj000-2004二月202346420x2x1x50101001/4-1/2[3/4]1/41/2-1/40017/235/2→14—10/3λj000↑-20
表(3)中λj全部非負,則最優(yōu)解為:420x2x1x30101000011/31/3-1/3-1/32/34/38/314/310/3λj000-20得到表(4)的另一基本最優(yōu)解04二月202347X(1),X(2)是線性規(guī)劃的兩個最優(yōu)解,它的凸組合
仍是最優(yōu)解,從而原線性規(guī)劃有多重最優(yōu)解。04二月202348唯一最優(yōu)解的判斷:最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解
。多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。無界解的判斷:
某個λk>0且aik≤0(i=1,2,…,m)則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個基變量為零的基本可行解。1.5單純形法
SimplexMethod04二月202349
通常線性規(guī)劃的標準型并非典范式,為了得到典范式,在約束條件的等式左端加一組虛擬變量,這種人為加的變量稱為人工變量。構(gòu)成典范式后再用單純形法求解,基于這種解法的有:大M法或兩階段法(人工變量法)。1.5.2大M法1.5單純形法
SimplexMethod04二月202350【例5】用大M法解下列線性規(guī)劃1.大M法04二月2023511.5單純形法
SimplexMethod【解】首先將數(shù)學模型化為標準形式引進x4,x5(松弛變量),得到標準型(非典范式)第一、三約束中分別加入人工變量x6、x7,目標函數(shù)中加入―Mx6―Mx7,得到典范式Cj32-100-M-MbCBXBx1x2x3x4x5x6x7-M
0-Mx6x5x7-4123-1-212[1]-1000101000014101→λj3-2M2+M-1+2M↑-M000-M0-1x6x5x3-6-32[5]3-2001-100010100-1-213→81λj5-6M5M↑0-M00-2M+120-1x2x5x3-6/5[3/5]-2/5100001-1/53/5-2/50101/5-3/52/5-1/5-13/5-2/53/531/5→11/5λj5↑0000-M-M04二月202353Cj32-100-M-MbCBXBx1x2x3x4x5x6x7-M
0-Mx6x5x7-4123-1-212[1]-1000101000014101→λj3-2M2+M-1+2M↑-M000-M0-1x6x5x3-6-32[5]3-2001-100010100-1-213→81λj5-6M5M↑0-M00-2M+120-1x2x5x3-6/5[3/5]-2/5100001-1/53/5-2/50101/5-3/52/5-1/5-13/5-2/53/531/5→11/5λj5↑0000-M-M23-1x2x1x301010000111025/32/3-1-10-27/5-13/3-32/51331/319/3λj000-5-25/3-M+2-M+22/504二月202354M是一個很大的抽象的數(shù),不需要給出具體的數(shù)值,可以理解為它能大于給定的任何一個確定數(shù)值;最優(yōu)解X=(31/3,13,19/3,0,0)T;最優(yōu)值Z=152/3注意:1.5單純形法
SimplexMethod04二月2023551.5單純形法
SimplexMethod【例6】求解線性規(guī)劃【解】加入松馳變量x3、x4化為標準型在第二個方程中加入人工變量x5,目標函數(shù)中加上Mx5一項,得到04二月202356用單純形法計算如下表所示。
Cj-5800-MbCBXBx1x2x3x4x50-Mx3x5[3]11-
溫馨提示
- 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)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 員工向公司借款合同書范文
- 綠化工程居間合同范例二零二五年
- 2025標準員工的勞動合同模板
- 2025全年合同制教師聘用合同范本
- 2025企業(yè)辦公租賃合同(公司版)
- 廣西壯族自治區(qū)欽州市2025屆九年級下學期中考一模道德與法治試卷(含答案)
- 果凍項目運營管理手冊(范文參考)
- XX學校食品安全和膳食經(jīng)費管理突出問題專項整治工作匯報范文
- DB36T-普通國省道路面養(yǎng)護信息元數(shù)據(jù)規(guī)范編制說明
- 如何管理職業(yè)運動員的財務(wù)試題及答案
- 房屋硬裝裝修合同范本
- 豐田鋒蘭達說明書
- 2023年東莞市人民醫(yī)院醫(yī)師規(guī)范化培訓招生(放射科)考試參考題庫含答案
- 2022年甘肅省張掖市輔警協(xié)警筆試筆試模擬考試(含答案)
- 勾頭作業(yè)施工方案
- 中醫(yī)醫(yī)院重癥醫(yī)學科建設(shè)與管理指南
- 創(chuàng)傷性網(wǎng)胃炎
- LY/T 1556-2000公益林與商品林分類技術(shù)指標
- GB/T 3522-1983優(yōu)質(zhì)碳素結(jié)構(gòu)鋼冷軋鋼帶
- 主要電氣設(shè)備絕緣電阻檢查記錄
- 探析小學數(shù)學作業(yè)分層設(shè)計與評價獲獎科研報告
評論
0/150
提交評論