運(yùn)籌(第一、二章習(xí)題課)

2023/1/151運(yùn)籌學(xué)

OPERATIONSRESEARCH

2023/1/152第一、二章習(xí)題課圖解法單純形法大M法、兩階段法寫出對(duì)偶規(guī)劃用對(duì)偶理論證明一些簡單的問題靈敏度分析參數(shù)規(guī)劃建立數(shù)學(xué)模型2023/1/153例1

請(qǐng)用大M法或兩階段法求解下列線性規(guī)劃問題解：大M法2023/1/1542-12000-M-M-Mb-M6111-100100-M2-2010-10010-M002-100-10012-M3M-12+M-M-M-M000-M6103/2-101/210-1/2-M2-2010-10010-1001-1/200-1/2001/22-M05M/2-M-MM/200-M/22023/1/155-M3400-13/21/21-3/2-1/222-2010-10010-11-1100-1/2-1/201/21/25+4M00M3M/2M/20-5M/2-M/22-12000-M-M-Mb23/4100-1/43/81/81/4-3/8-1/827/2001-1/2-1/41/41/2-3/4-1/4-17/4010-1/4-1/8-3/81/41/83/80005/4-3/8-9/8-M--M--M-由表可知，而對(duì)應(yīng)系數(shù)列，故該問題為無界解。2023/1/156解：兩階段法（1）構(gòu)造第一階段問題，并求解。2023/1/157000000111b16111-10010012-2010-100101002-100-10011-3-111100016103/2-101/210-1/212-2010-100100001-1/200-1/2001/210-5/211-1/2003/22023/1/15813400-13/21/21-3/2-1/202-2010-1001001-1100-1/2-1/201/21/2-4001-3/2-1/205/25/2000000111b03/4100-1/43/81/81/4-3/8-1/807/2001-1/2-1/41/41/2-3/4-1/407/4010-1/4-1/8-3/81/41/83/8000000111由表可知最優(yōu)目標(biāo)值為0，人工變量全部出基，故原問題有可行解。繼續(xù)進(jìn)行第二步。2023/1/1592-12000b23/4100-1/43/81/827/2001-1/2-1/41/4-17/4010-1/4-1/8-3/80005/4-3/8-9/8（2）去掉人工變量，求解第二步由表可知，而對(duì)應(yīng)系數(shù)列，故該問題為無界解。2023/1/1510解：大M法2023/1/1511101512000-Mb095311000015-56150100-M521100-1110+2MM+1512+M00-M0109/513/51/51/500002409161100-M7/50-1/53/5-2/50-1109-M/58+3M/5-2-2M/50-M02023/1/1512101512000-Mb103/2139/8003/16-1/8000123/209/1611/161/1600-M1/20-43/800-7/16-3/80-110-43M/800-7M/16-3M/80-M0由表可知所有，但人工變量未出基，故原問題無可行解。2023/1/1513例3：書P49，1.14，分析問題例4：書P49，1.15證明例5：書P48，1.12解：設(shè)在設(shè)備上生產(chǎn)的產(chǎn)品Ⅰ的數(shù)量是，i=1，2；j=1，2，3。在設(shè)備上生產(chǎn)的產(chǎn)品??的數(shù)量是。在設(shè)備上生產(chǎn)的產(chǎn)品Ш

的數(shù)量是。則：2023/1/1514約束條件目標(biāo)函數(shù)2023/1/1515例6：書P76，2.1（b,d)寫出對(duì)偶規(guī)劃解：令，則原問題轉(zhuǎn)化為：2023/1/1516對(duì)偶規(guī)劃為或2023/1/1517運(yùn)輸問題的數(shù)學(xué)模型解：對(duì)應(yīng)于第一組約束的對(duì)偶變量為，對(duì)應(yīng)于第二組約束的對(duì)偶變量為。，

于是對(duì)偶規(guī)劃為2023/1/1518或2023/1/1519例7：書P76，2.2判斷下列各種說法是否正確，為什么？（1）如果線性規(guī)劃問題的原問題存在可行解，則對(duì)偶問題也一定存在可行解。（2）若某線性規(guī)劃的對(duì)偶問題無可行解，則原問題為無界解。（3）在互為對(duì)偶的一對(duì)問題中，不論原問題是求最大還是求最小，原問題目標(biāo)函數(shù)值一定不超過對(duì)偶問題的目標(biāo)函數(shù)值。解：（1)錯(cuò),原問題是無界解時(shí)，對(duì)偶問題無可行解.(2)錯(cuò),原問題可能是無界解，也可能無可行解。

（3）正確。2023/1/1520例7：已知有線性規(guī)劃問題如下用單純形法求得最終表如下：3/2015/14-3/14110-1/72/700-5/14-25/142023/1/1521試進(jìn)行如下分析：（1）直接寫出對(duì)偶問題的最優(yōu)解；（2）目標(biāo)系數(shù)在什么范圍內(nèi)變化時(shí)，上述最優(yōu)解不變；（3）約束條件右端項(xiàng)在什么范圍內(nèi)變化時(shí)，上述最優(yōu)解不變；（4）目標(biāo)函數(shù)變?yōu)樯鲜鲎顑?yōu)解的變化；（5）約束條件右端項(xiàng)變?yōu)樯鲜鲎顑?yōu)解的變化。2023/1/1522解：（1）對(duì)偶問題的最優(yōu)解（2）設(shè)目標(biāo)函數(shù)中的系數(shù)為，則要使得最優(yōu)解不變，則需，即由此可得：2023/1/1523（3）設(shè)第一個(gè)約束的右端常數(shù)項(xiàng)為，則要使得最優(yōu)基不變，則需，即（4）設(shè)目標(biāo)函數(shù)中的系數(shù)為，則檢驗(yàn)數(shù)2023/1/1524所以最優(yōu)解發(fā)生變化，選擇進(jìn)基，繼續(xù)迭代：3/2015/14-3/14110-1/72/7002/7-18/741221/5014/51-3/58/512/501/50-4/50-12/5012所以新最優(yōu)解為2023/1/1525（5）設(shè)右端常數(shù)項(xiàng)為，則最終表中，b列數(shù)值為：顯然已不是可行解，用對(duì)偶單純形法繼續(xù)迭代-1/7015/14-3/1427/710-1/72/700-5/14-25/145102/30-14/3-5/3111/314/31/300-25/3-10/30010所以新最優(yōu)解為2023/1/1526例8：已知某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，有關(guān)數(shù)據(jù)如下表，試分別回答下列問題。

產(chǎn)品消耗定額原料甲乙丙原料擁有量A63545B34530單件利潤415（1）建立模型，求使該廠獲利最大的生產(chǎn)計(jì)劃；（2）若有一種新產(chǎn)品丁，其原材料消耗定額：A：3單位，B：2單位，單件利潤2.5單位，問該產(chǎn)品是否值得安排生產(chǎn)？若值得，求新的最優(yōu)生計(jì)劃；(3)若原材料A市場緊缺，除擁有量外一時(shí)無法購進(jìn)，而B數(shù)量不足可購買，市場單價(jià)0.5，該廠應(yīng)否購買，購進(jìn)多少為宜？2023/1/1527解（1）假設(shè)甲、乙、丙三種產(chǎn)品的產(chǎn)量分別是，建立模型如下：用單純形法求解的最終表如下：41500b451-1/301/3-1/353011-1/52/50-8/30-1/3-2/32023/1/1528（2）增加產(chǎn)品丁的產(chǎn)量為，將有關(guān)數(shù)據(jù)列在第6列，415002.5b451-1/301/3-1/31/353011-1/52/51/50-8/30-1/3-2/31/6所以值得安排生產(chǎn)。2023/1/1529415002.5b451-1/301/3-1/31/353011-1/52/51/50-8/30-1/3-2/31/62.5153-101-1150-3/56/51-2/53/50-1/2-5/20-1/2-1/20故新的最優(yōu)解是2023/1/1530（3）因?yàn)樵牧螧的影子價(jià)格是，所以值得購進(jìn)。設(shè)購進(jìn)量為，反映到最終表中即為：41500b41-1/301/3-1/35011-1/52/50-8/30-1/3-2/3使最優(yōu)解不變的參數(shù)范圍是：，

目標(biāo)函數(shù)是：

（1）當(dāng)時(shí)，，重新迭代后得2023/1/153141500b0-310-1156/53/511/500-20-10最優(yōu)解是：目標(biāo)函數(shù)是：所以最佳購進(jìn)量為15。2023/1/1532例9：分析下述參數(shù)規(guī)劃問題中，當(dāng)變化時(shí)最優(yōu)解的變化情況，及目標(biāo)函數(shù)隨參數(shù)的變化。1100b011/201/21121/21-3/201/203/20解：令求得最優(yōu)解如下：2023/1/153311b11/201/21121/21-3/201/2-03/2-20將參數(shù)變化反映到最終表使最優(yōu)解不變的參數(shù)范圍是：，目標(biāo)函數(shù)是：

（1）當(dāng)