第二次線性規(guī)劃

1、第二次線性規(guī)劃第1頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第2頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第3頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第4頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一多項(xiàng)式時(shí)間 .vs. 指數(shù)時(shí)間 n 10 20 50 60 0.0001s 0.0004s0.0025s0.0036s 0.001s1.0s35.7yrs366ctrs假定計(jì)算機(jī)一秒鐘可以處理 次運(yùn)算計(jì)算機(jī)更新?lián)Q代的影響各代計(jì)算機(jī)1小時(shí)內(nèi)能處理的變量個(gè)數(shù) n當(dāng)前計(jì)算機(jī)速度提高100倍速度提高1000倍 10 31.6 +6.64 +9.97第5

2、頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第6頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第7頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第8頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第9頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一課堂練習(xí)1運(yùn)輸問題：請(qǐng)把上述問題描述成一個(gè)線性規(guī)劃問題。第10頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一課堂練習(xí)2機(jī)場飛機(jī)到達(dá)時(shí)間問題：請(qǐng)把上述問題描述成一個(gè)線性規(guī)劃問題。第11頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第12頁，共91頁，2022年，5月20日，8點(diǎn)43分，

3、星期一第13頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第14頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一課堂練習(xí)第15頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第16頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第17頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第18頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第19頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第20頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第21頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一2.最優(yōu)頂點(diǎn)定理2.2.2設(shè)

4、線性規(guī)劃(LP)的可行域非空，則有下列結(jié)論：(1)線性規(guī)劃(LP)存在有限最優(yōu)解的充要條件是所有 為非負(fù)數(shù)，其中 是可行域的極方向。(2)線性規(guī)劃(LP)存在有限最優(yōu)解，則目標(biāo)函數(shù)的最優(yōu)值可在某個(gè)極點(diǎn)處達(dá)到。第22頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一2.最優(yōu)基本可行解第23頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一鄰接基本解求此問題的兩個(gè)鄰接基本解。第24頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第25頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一課堂練習(xí)(0.5,1, 0.5,0,0)第26頁，共91頁，2022年，5月20日，8點(diǎn)4

5、3分，星期一退化：第27頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一定理：證明：第28頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第29頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一證明：第30頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第31頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第32頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第33頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第34頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第35頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第36

6、頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一s.t.稱為基本可行解 的檢驗(yàn)數(shù)。第37頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一注意到：第38頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一定理3.1.2 對(duì)于非退化問題，單純形方法經(jīng)有限次迭代或達(dá)到最優(yōu)基本可行解，或得出無界的結(jié)論。收斂性對(duì)于非退化情形，在每次迭代，均有：各次迭代得到的基本可行解互不相同，而基本可行解個(gè)數(shù)有限，因此有限次迭代必能得到最優(yōu)解。第39頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第40頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第41頁，共91頁，2022年，5

7、月20日，8點(diǎn)43分，星期一 第42頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第43頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第44頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一-21-1000Min413-1106654-21018200-1/201/24Min407/2-5/41-1/4411-1/21/401/428第45頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一00-1/201/24Min407/2-5/41-1/4411-1/21/401/4282-10018Min451011141434-210187001222251011143

8、14012336第46頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一課堂練習(xí)第47頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一-120000Min3101001140101015110013/23/202100111010014010101501-1011/2第48頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第49頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第50頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第51頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一00000110611-10010271-10-10011510001

93min611-100102271-10-100111510001003第52頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一-2011000-3min611-100102271-10-10011151000100330-21-1002-1min602-1101-111/211-10-100115010110-12300000110201-1/21/201/2-1/21/2110-1/2-1/201/21/23/25001/21/21-1/2-1/23/2第53頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一00000110201-1/21/201/2-

10、1/21/2110-1/2-1/201/21/23/25001/21/21-1/2-1/23/2-210000201-1/21/201/2110-1/2-1/203/25001/21/213/2第54頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一00-1/2-3/205/2min201-1/21/201/21110-1/2-1/203/25001/21/213/2303-2004min402-1101111-100250-110111010026min4010112110001330-11011第55頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一0000111052-110

11、10046111000164100100027302000110第56頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一-60-40000-20min52-1101004261110010664100100022730200011010/300-46000-8min50-11-2100006011-1010444100100027002-300142第57頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一00-46000-8min50-11-2100006011-1010444100100027002-3001420-40-2400-8min30-11-2100060201-110

12、4241001000270201-20142第58頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一0-40-2400-8min30-11-2100060201-1104241001000270201-2014200002000min3001-3/21/21/20220101/2-1/21/20241001000270000-1-110第59頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第60頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第61頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第62頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一可知原問

13、題無可行解。第63頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第64頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第65頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一11-300MM041-21100011621-40-1103710-200011解：初始表格為第66頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一11-300MM041-21100011621-40-1103710-200011解：初始表格為1-3M1-M6M-30M00-4Mmin41-2110001111621-40-11033/2710-2000111第67頁，共91頁，2022年

14、，5月20日，8點(diǎn)43分，星期一1-3M1-M6M-30M00-4Mmin41-2110001111621-40-11033/2710-200011101-M-10M03M-1-M-1min40-23100-11060100-11-211110-20001100-101M-1M+1-2min40031-22-512420100-11-21110-200011第68頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一00-101M-1M+1-2min40031-22-512420100-11-21110-2000110001/31/3M-1/3M-2/3230011/3-2/32/3-5/3

15、420100-11-2111002/3-4/34/3-7/39第69頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第70頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一5.退化的線性規(guī)劃問題退化的基本可行解(幾何解釋) 對(duì)于標(biāo)準(zhǔn)形而言，當(dāng)極點(diǎn)僅對(duì)應(yīng)一個(gè)基時(shí)，是非退化的；當(dāng)極點(diǎn)對(duì)應(yīng)多個(gè)基時(shí)，是退化的。第71頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一退化(degenerate)與循環(huán)(cycling)退化問題 單純形法可能出現(xiàn)循環(huán)！ 實(shí)際中經(jīng)常碰到退化問題，但很少出現(xiàn)循環(huán) 避免出現(xiàn)循環(huán)的措施：攝動(dòng)法、Bland法則、字典序法第72頁，共91頁，2022年，5月20日

16、，8點(diǎn)43分，星期一0-50-40-100-6021-3020010-1031-100410000200300010-1102010-100010非退化轉(zhuǎn)軸退化的基本可行解與退化轉(zhuǎn)軸 基本可行解是退化的當(dāng)且僅當(dāng)單純形表最后一列有一個(gè)或者多個(gè)零！退化轉(zhuǎn)軸指轉(zhuǎn)軸后目標(biāo)函數(shù)沒有發(fā)生變化！退化轉(zhuǎn)軸！退化基本可行解第73頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一最小系數(shù)規(guī)則： 進(jìn)基變量：最小系數(shù)規(guī)則 出基變量：最小指標(biāo)規(guī)則循環(huán)的例子Beale循環(huán)定義：從某張單純形表開始返回到該單純形表的一串轉(zhuǎn)軸轉(zhuǎn)軸規(guī)則：選進(jìn)基變量和離基變量的明確規(guī)則(多個(gè)可選時(shí)！)第74頁，共91頁，2022年，5月20

17、日，8點(diǎn)43分，星期一000-3/420-1/260Min11001/4-8-190020101/2-12-1/23003001001013000-4-7/2330Min44001-32-43602-210043/2-150030010010111000-2180Min4480108-84005-1/21/40013/8-15/400300100101第75頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一-2301/400-30Min63/2101/801-21/2051/16-1/80-3/64103/160033/2-11-1/80021/212/21-110-1/216000Mi

18、n62-60-5/256100071/3-2/30-1/416/301003-2615/2-560010-20-7/4441/200Min11-30-5/4281/200701/301/6-4-1/61003061001011/6第76頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一循環(huán)！注：循環(huán)時(shí)，轉(zhuǎn)軸序列中所有BFS都是退化的！是同一個(gè)BFS！第七張單純形表000-3/420-1/260Min11001/4-8-190020101/2-12-1/2300300100101第77頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一避免循環(huán)的方法能進(jìn)基的變量(使目標(biāo)值減小)中選指標(biāo)

19、最小者進(jìn)基 攝動(dòng)法(Dantzig，1954年) Bland法則(Bland, 1977)最小指標(biāo)法則能出基的變量(保持可行)中選指標(biāo)最小者出基美好愿望：構(gòu)造某種永遠(yuǎn)不會(huì)產(chǎn)生循環(huán)的轉(zhuǎn)軸規(guī)則！ 字典序法(Orden和Wolfe，1954年)第78頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一前四張單純形表相同！第五張單純形表是利用Bland法則作為轉(zhuǎn)軸規(guī)則求解Beale的例子！0-10-5/4320-30Min60-20-1241-6011-20-3/41603030211-24061001/2-3/420061/2Min60010010111011/4-809142011/21/2-

20、12031/21第79頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一03/25/402021/25/460010010151-1/23/40-2015/23/430211-24061最后一張單純形表/最優(yōu)單純形表第80頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一回顧有初始基本可行解的單純形算法,對(duì)于標(biāo)準(zhǔn):單純形表為:第81頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第82頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一-第83頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一-第84頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第85頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一第86頁，共91頁，2022年，5月20日，8點(diǎn)43分，星期一K