線性規(guī)劃理論與模型應(yīng)用

線性規(guī)劃理論與模型應(yīng)用第一頁，共五十一頁，編輯于2023年，星期三2.1對偶規(guī)劃1.食譜問題

設(shè)有n種食物,各含m種營養(yǎng)素,第j種食物中第i種營養(yǎng)素的含量為aij,所有n種食物價(jià)格分別為c1,c2,…,cn,營養(yǎng)素的價(jià)格分別為w1,w2,…,wm,要求食譜中m種營養(yǎng)素的含量分別不低于b1,b2,…,bm,食譜中n種食物的數(shù)量為x1,x2,…,xn,如下表所示:第二頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃消費(fèi)者希望費(fèi)用最低且滿足營養(yǎng)要求，則有食譜廠家在確定營養(yǎng)素價(jià)格時(shí)，希望收益最大且能吸引消費(fèi)者，則有第三頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃前述的兩個(gè)規(guī)劃是同一問題的兩個(gè)方面: 消費(fèi)者希望費(fèi)用最低； 營養(yǎng)廠家希望收益最大。這一對問題即是我們要研究的線性規(guī)劃的對偶問題.第四頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃對稱形式下對偶規(guī)劃 考慮以下兩種形式的線性規(guī)劃問題第五頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃定義2.1稱以上兩種形式的線性規(guī)劃問題為一對對偶線性規(guī)劃問題，其中LP問題為原規(guī)劃，LD問題為對偶規(guī)劃。 其矩陣形式表示為其中定義2.2滿足下列條件的線性規(guī)劃問題為成為具有對稱形式：變量均具有非負(fù)約束；當(dāng)目標(biāo)求極小時(shí)約束條件均為“”，當(dāng)目標(biāo)求極大時(shí)約束條件均為“≤”。第六頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃如果將對偶規(guī)劃(LD)作為原規(guī)劃，其形式為其對偶規(guī)劃是即是原規(guī)劃定理2.1對偶規(guī)劃的對偶規(guī)劃是原規(guī)劃，即LD是LP的對偶規(guī)劃時(shí)，LP也是LD的對偶規(guī)劃。第七頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃對稱形式下原規(guī)劃和對偶規(guī)劃轉(zhuǎn)換規(guī)則：原規(guī)劃min問題，對偶規(guī)劃max問題右端項(xiàng)與目標(biāo)系數(shù)互相轉(zhuǎn)換；系數(shù)矩陣互為轉(zhuǎn)置關(guān)系；原規(guī)劃約束條件對應(yīng)對偶規(guī)劃的變量‘’約束，對偶規(guī)劃對應(yīng)

的變量0；原規(guī)劃的變量對應(yīng)對偶規(guī)劃的約束條件變量0，對偶規(guī)劃中對應(yīng)

的約束為‘≤’約束非對稱形式下的特點(diǎn)線性規(guī)劃問題的約束條件有‘’、‘=’、‘≤’約束，變量中有0、≤0、自由變量第八頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃非對稱形式下對偶規(guī)劃 例2.1寫出下述線性規(guī)劃問題的對偶規(guī)劃第九頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃將約束全變?yōu)椤啊贝藛栴}的對偶問題為第十頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃此問題的對偶問題為第十一頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃非對稱形式下原規(guī)劃和對偶規(guī)劃轉(zhuǎn)換規(guī)則：原規(guī)劃min問題，對偶規(guī)劃max問題右端項(xiàng)與目標(biāo)系數(shù)互相轉(zhuǎn)換；系數(shù)矩陣互為轉(zhuǎn)置關(guān)系；原規(guī)劃約束條件‘≤’約束，對偶規(guī)劃對應(yīng)

的變量≤0；‘’約束，對偶規(guī)劃對應(yīng)

的變量0；‘=’約束，對偶規(guī)劃對應(yīng)

的變量無約束(自由變量)；原規(guī)劃的變量約束0的變量，對偶規(guī)劃中對應(yīng)

的約束為‘≤’約束；≤0的變量，對偶規(guī)劃中對應(yīng)

的約束為‘’約束；自由變量，對偶規(guī)劃中對應(yīng)

的約束為‘=’約束。第十二頁，共五十一頁，編輯于2023年，星期三對偶規(guī)劃例2.2寫出下述線性規(guī)劃問題的對偶規(guī)劃第十三頁，共五十一頁，編輯于2023年，星期三2.2對偶定理為便于討論，本節(jié)僅對對稱形式的對偶規(guī)劃進(jìn)行討論，非對稱形式的對偶規(guī)劃同樣可證明類似的結(jié)論。為方便起見，LP簡稱為P,LD簡稱為D。第十四頁，共五十一頁，編輯于2023年，星期三對偶定理1.弱對偶定理定理2.2設(shè)x0是P的可行解，w0是D的可行解，則

cx0w0b；若x*、w*分別是P、D的可行解且cx*=w*b，則x*、w*分別是P、D的最優(yōu)解；若P、D中有一個(gè)目標(biāo)函數(shù)值無界，則另一個(gè)可行域?yàn)榭占籔、D都有最優(yōu)解的充要條件是P、D都有可行解。證：1)因?yàn)锳x0b，x00，w0A≤c，w00，對Ax0b兩邊左乘w0則有w0Ax0w0b；對w0A≤c兩邊右乘x0則有w0Ax0≤cx0；從而有cx0w0b。

2)設(shè)x0是P的任意可行解，由1)有cx0w*b=cx*從而x*是P的最優(yōu)解；同樣可證w*是D的最優(yōu)解。 用1)的結(jié)論可容易證明3)和4)成立。第十五頁，共五十一頁，編輯于2023年，星期三對偶定理2.強(qiáng)對偶定理定理2.3一對對偶規(guī)劃P和D中的一個(gè)有最優(yōu)解的充要條件是另一個(gè)有最優(yōu)解，且兩問題的最優(yōu)值相等。證：對問題P引入松弛變量v=(xn+1,…,xn+m)T將其變成設(shè)該問題的最優(yōu)解為x*，B為最優(yōu)基，則有令w*=cBB-1，則有w*是D的可行解又w*b=cBB-1b=cx*，由定理2.2可知w*是D的最優(yōu)解。第十六頁，共五十一頁，編輯于2023年，星期三對偶定理3.互補(bǔ)松弛定理及其應(yīng)用

定理2.4(互補(bǔ)松弛定理)已知x*,w*分別是P和D的可行解，則它們分別是P和D的最優(yōu)解的充要條件是

w*(Ax*-b)=0,(c-w*A)x*=0證：因?yàn)閤*,w*分別是P和D的可行解，從而

w*b≤w*Ax*≤cx*必要性：若x*,w*分別是P和D的最優(yōu)解，則w*b=cx*，從而上式中兩“≤”號(hào)等式成立，顯然結(jié)論成立。充分性： 若w*(Ax*-b)=0，則w*Ax*=w*b，

若(c-w*A)x*=0，則cx*=w*Ax*從而cx*=w*b，即x*,w*分別是P和D的最優(yōu)解第十七頁，共五十一頁，編輯于2023年，星期三對偶定理將互補(bǔ)松弛定理的結(jié)論寫成如下形式：以上兩式表示 P規(guī)劃的約束嚴(yán)格不等號(hào)成立(松)時(shí)，D規(guī)劃相應(yīng)的變量必取0(緊)； D規(guī)劃的約束嚴(yán)格不等號(hào)成立(松)時(shí)，P規(guī)劃相應(yīng)的變量必取0(緊)，非基變量； 第二式也就是λjxj=0(j=1,2,…,n)表示在P規(guī)劃中檢驗(yàn)數(shù)與變量互為松弛。第十八頁，共五十一頁，編輯于2023年，星期三對偶定理例2.3求解線性規(guī)劃問題其對偶問題：第十九頁，共五十一頁，編輯于2023年，星期三對偶定理對偶規(guī)劃是兩個(gè)變量的問題可用圖解法求解，得對偶規(guī)劃的最優(yōu)解顯然，第1、5個(gè)約束等式成立，其它嚴(yán)格不等式成立，由互補(bǔ)松弛定理原規(guī)劃的最優(yōu)解中x2*=x3*=x4*

=0，因?yàn)閣1*和w2*均不等于0，從而原規(guī)劃的最優(yōu)解中兩個(gè)約束是緊的，即第二十頁，共五十一頁，編輯于2023年，星期三對偶定理例2.4求解線性規(guī)劃問題的對偶問題：第二十一頁，共五十一頁，編輯于2023年，星期三對偶定理用單純形表格求解線性規(guī)劃問題第二十二頁，共五十一頁，編輯于2023年，星期三對偶定理原問題的最優(yōu)解為對偶問題的最優(yōu)解為第二十三頁，共五十一頁，編輯于2023年，星期三作業(yè)P74： 4，5，7第二十四頁，共五十一頁，編輯于2023年，星期三2.3對偶單純形法1.理論基礎(chǔ) 考慮線性規(guī)劃標(biāo)準(zhǔn)形其對偶規(guī)劃為第二十五頁，共五十一頁，編輯于2023年，星期三對偶單純形法由對偶定理，若有x*,w*滿足Ax*=b,x*0,w*A≤

c,cx*=w*b，則x*,w*是P,D的最優(yōu)解；考慮單純形法的迭代過程，若x是基可行解，B是相應(yīng)的可行基，則Ax=b,x0。令w=cBB-1，則cx=wb，檢驗(yàn)數(shù)可表示為λ=c-cBB-1A=c–

wA；在單純形法的迭代中，對偶定理中的4個(gè)條件由3個(gè)條件Ax=b,x0,cx=wb始終滿足；單純形法的迭代過程實(shí)際上可看作驗(yàn)證檢驗(yàn)數(shù)是否滿足λ0的過程，也就是驗(yàn)證D問題約束條件wA≤c是否滿足的過程;單純形法迭代也可看作是從原問題P的基可行解逐步迭代到對偶問題D的可行解的過程（兩問題的目標(biāo)函數(shù)值始終相等）。對偶單純形法的本質(zhì)是從對偶問題的可行解逐步迭代到原問題P的可行解的過程。第二十六頁，共五十一頁，編輯于2023年，星期三對偶單純形法定義若A=(B,N),其中B非奇異，w=cBB-1稱為D的一個(gè)基解，若c-cBB-1A0,即wA≤c，稱w為D的一個(gè)基可行解，此時(shí)稱B為原規(guī)劃的一個(gè)正則基，

稱為原規(guī)劃問題的一個(gè)正則基解。對偶單純形法的基本思想：若有一個(gè)正則基B，則w=cBB-1滿足wA≤c，Ax=b，cx=wb，若x0，則x已是最優(yōu)解，否則求另一個(gè)正則基解，直到滿足若x0為止。原規(guī)劃單純形迭代是在滿足Ax=b和x0前提下逐步使解達(dá)到最優(yōu)；對偶單純形法迭代是在滿足Ax=b和最優(yōu)性條件前提下逐步使解滿足x0。第二十七頁，共五十一頁，編輯于2023年，星期三對偶單純形法2.對偶單純形表格 不妨設(shè)前m個(gè)為基變量，表格形式仍然如同單純形表格 區(qū)別在于檢驗(yàn)數(shù)始終滿足λj0，不再要求bi0。迭代思想是，如果br<0，則為xr出基變量；選進(jìn)基變量xk使所有λj0仍然成立，進(jìn)行轉(zhuǎn)軸變換使xk所在列為單位向量。第二十八頁，共五十一頁，編輯于2023年，星期三對偶單純形法對檢驗(yàn)數(shù)行消元之后，目標(biāo)函數(shù)形式為為保證λj0仍然成立，顯然下式確定的k即可如果yr,j0，則原問題無可行解。如何使所有λj0仍然成立，考慮xr所在方程和目標(biāo)函數(shù)。第二十九頁，共五十一頁，編輯于2023年，星期三對偶單純形法例2.6用對偶單純形法求解下述線性規(guī)劃問題解：轉(zhuǎn)化為標(biāo)準(zhǔn)形取x4,x5為基變量，方程兩邊乘以-1，則有如下標(biāo)準(zhǔn)形第三十頁，共五十一頁，編輯于2023年，星期三對偶單純形法此問題x4,x5為基變量時(shí)，檢驗(yàn)數(shù)均為正，是一個(gè)正則基，對偶單純形表格為x4為出基變量，x2為進(jìn)基變量，以y12為主元做轉(zhuǎn)軸變換得第三十一頁，共五十一頁，編輯于2023年，星期三對偶單純形法x5為出基變量，x3為進(jìn)基變量，以y23為主元做轉(zhuǎn)軸變換得原問題的最優(yōu)解x=(0,?,?)T，最優(yōu)值z*=17/2。第三十二頁，共五十一頁，編輯于2023年，星期三作業(yè)P77： 8第三十三頁，共五十一頁，編輯于2023年，星期三2.4靈敏度分析目標(biāo)系數(shù)的靈敏度分析目標(biāo)系數(shù)變化對最優(yōu)解的影響 為求出數(shù)據(jù)變化后的最優(yōu)解，不必從最初的階段開始求解，僅從原問題最后的單純形表的基礎(chǔ)之上，重新計(jì)算檢驗(yàn)數(shù)，然后求出最優(yōu)解并與原最優(yōu)解比較。不影響最優(yōu)基變化時(shí)系數(shù)ck的變化范圍靈敏度分析，是討論線性規(guī)劃問題中原始數(shù)據(jù)aij，bi，cj的變化對最優(yōu)解的影響，所謂對最優(yōu)解的影響主要有兩個(gè)層面，一是對最優(yōu)解的影響，另一是當(dāng)某個(gè)數(shù)據(jù)在什么范圍內(nèi)變化時(shí)，最優(yōu)基將不會(huì)改變。本節(jié)討論bi和cj的變化、增加變量對最優(yōu)解的影響。第三十四頁，共五十一頁，編輯于2023年，星期三靈敏度分析設(shè)目標(biāo)系數(shù)ck的改變量為,其中為變化之后的系數(shù)。當(dāng)xk不是基變量時(shí)，此時(shí)只對檢驗(yàn)數(shù)λk產(chǎn)生影響，只要考慮保持λk0即可。當(dāng)xk是基變量時(shí)，此時(shí)ck的變化將對所有檢驗(yàn)數(shù)產(chǎn)生影響。設(shè)xk對應(yīng)第i個(gè)方程，基的新舊目標(biāo)系數(shù)為第三十五頁，共五十一頁，編輯于2023年，星期三靈敏度分析第三十六頁，共五十一頁，編輯于2023年，星期三靈敏度分析例2.7某工廠用甲乙兩種原料生產(chǎn)A、B、C、D四種產(chǎn)品，每種產(chǎn)品的利潤、原料數(shù)量、每種產(chǎn)品消耗原料定額如下表所示：問應(yīng)怎樣組織生產(chǎn)才能使總利潤最大？如果產(chǎn)品A、D的利潤均變到15萬元，最優(yōu)解有何變化？又各產(chǎn)品的利潤在何范圍內(nèi)變化時(shí)，最優(yōu)基不變？解：1)設(shè)x1，x2，x3，x4分別表示A、B、C、D四種產(chǎn)品的生產(chǎn)數(shù)量，可建立如下模型：第三十七頁，共五十一頁，編輯于2023年，星期三靈敏度分析化為標(biāo)準(zhǔn)形用單純形法得到最后一個(gè)表格如下，最優(yōu)解產(chǎn)品C生產(chǎn)1萬件，產(chǎn)品D生產(chǎn)2萬件，總利潤88萬元。第三十八頁，共五十一頁，編輯于2023年，星期三靈敏度分析2)計(jì)算c1，c4改變后的檢驗(yàn)數(shù)代入上表格(在當(dāng)前基下)第三十九頁，共五十一頁，編輯于2023年，星期三靈敏度分析3)討論cj(j=1,2,3,4)的變化范圍 (1)非基變量x1，x2的檢驗(yàn)數(shù)為λ1=4，λ2=2/3，系數(shù)的變化范圍是從而c1，c2變化范圍分別是 (2)基變量x3，x4的系數(shù)，先考慮c3變化范圍第四十頁，共五十一頁，編輯于2023年，星期三靈敏度分析從而c3變化范圍分別是再考慮c4變化范圍得到c4變化范圍分別是第四十一頁，共五十一頁，編輯于2023年，星期三靈敏度分析2.右端項(xiàng)的靈敏度分析右端項(xiàng)的幾個(gè)分量改變對最優(yōu)解的影響，此時(shí)不影響檢驗(yàn)數(shù)，但可能影響基變量的非負(fù)性，如果B-1b0，當(dāng)前解仍然是最優(yōu)解，否則，用對偶單純形法求出最優(yōu)解。另一類有意義的問題是當(dāng)某一個(gè)分量在什么范圍內(nèi)變化，才不影響基變量，設(shè)bk的改變量為，記當(dāng)前最優(yōu)解的基解為，改變后的基解為，則有設(shè)，如果，則應(yīng)有第四十二頁，共五十一頁，編輯于2023年，星期三靈敏度分析因此，不改變當(dāng)前最優(yōu)基前提下bk的變化范圍是例2.8考慮例2.7中在當(dāng)前最優(yōu)基下右端項(xiàng)的變化范圍。第四十三頁，共五十一頁，編輯于2023年，星期三靈敏度分析3.增加新變量時(shí)的靈敏度分析設(shè)新增變量為xn+m+1，相應(yīng)的列向量為An+m+1，目標(biāo)系數(shù)為cn+m+1，此時(shí)考慮最優(yōu)解的變化，從最后的單純形表格中的B-1計(jì)算yn+m+1=B-1An+m+1及檢驗(yàn)數(shù)λn+m+1=cn+m+1-cByn+m+1，如果λn+m+10，最優(yōu)解不變，否則將xn+m+1作為進(jìn)基變量繼續(xù)求解得出新的最優(yōu)解。例2.9在例2.7中某工廠考慮引進(jìn)新產(chǎn)品E，該產(chǎn)品每1萬件要消耗原料甲3公斤，原料乙1公斤，當(dāng)產(chǎn)品E的利潤為17萬元時(shí)最優(yōu)解如何變化?解：設(shè)產(chǎn)品E的產(chǎn)量為x7，則相應(yīng)的有第四十四頁，共五十一頁，編輯于2023年，星期三靈敏度分析將以上信息加入到最后的單純形表格中得繼續(xù)求解的如下最優(yōu)解第四十五頁，共五十一頁，