線性規劃理論與模型應用第1頁，共51頁，2023年，2月20日，星期六2.1對偶規劃1.食譜問題

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

的變量0；原規劃的變量對應對偶規劃的約束條件變量0，對偶規劃中對應

的約束為‘≤’約束非對稱形式下的特點線性規劃問題的約束條件有‘’、‘=’、‘≤’約束，變量中有0、≤0、自由變量第8頁，共51頁，2023年，2月20日，星期六對偶規劃非對稱形式下對偶規劃 例2.1寫出下述線性規劃問題的對偶規劃第9頁，共51頁，2023年，2月20日，星期六對偶規劃將約束全變為“”此問題的對偶問題為第10頁，共51頁，2023年，2月20日，星期六對偶規劃此問題的對偶問題為第11頁，共51頁，2023年，2月20日，星期六對偶規劃非對稱形式下原規劃和對偶規劃轉換規則：原規劃min問題，對偶規劃max問題右端項與目標系數互相轉換；系數矩陣互為轉置關系；原規劃約束條件‘≤’約束，對偶規劃對應

的變量≤0；‘’約束，對偶規劃對應

的變量0；‘=’約束，對偶規劃對應

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

的約束為‘≤’約束；≤0的變量，對偶規劃中對應

的約束為‘’約束；自由變量，對偶規劃中對應

的約束為‘=’約束。第12頁，共51頁，2023年，2月20日，星期六對偶規劃例2.2寫出下述線性規劃問題的對偶規劃第13頁，共51頁，2023年，2月20日，星期六2.2對偶定理為便于討論，本節僅對對稱形式的對偶規劃進行討論，非對稱形式的對偶規劃同樣可證明類似的結論。為方便起見，LP簡稱為P,LD簡稱為D。第14頁，共51頁，2023年，2月20日，星期六對偶定理1.弱對偶定理定理2.2設x0是P的可行解，w0是D的可行解，則

cx0w0b；若x*、w*分別是P、D的可行解且cx*=w*b，則x*、w*分別是P、D的最優解；若P、D中有一個目標函數值無界，則另一個可行域為空集；P、D都有最優解的充要條件是P、D都有可行解。證：1)因為Ax0b，x00，w0A≤c，w00，對Ax0b兩邊左乘w0則有w0Ax0w0b；對w0A≤c兩邊右乘x0則有w0Ax0≤cx0；從而有cx0w0b。

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

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

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

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

若(c-w*A)x*=0，則cx*=w*Ax*從而cx*=w*b，即x*,w*分別是P和D的最優解第17頁，共51頁，2023年，2月20日，星期六對偶定理將互補松弛定理的結論寫成如下形式：以上兩式表示 P規劃的約束嚴格不等號成立(松)時，D規劃相應的變量必取0(緊)； D規劃的約束嚴格不等號成立(松)時，P規劃相應的變量必取0(緊)，非基變量； 第二式也就是λjxj=0(j=1,2,…,n)表示在P規劃中檢驗數與變量互為松弛。第18頁，共51頁，2023年，2月20日，星期六對偶定理例2.3求解線性規劃問題其對偶問題：第19頁，共51頁，2023年，2月20日，星期六對偶定理對偶規劃是兩個變量的問題可用圖解法求解，得對偶規劃的最優解顯然，第1、5個約束等式成立，其它嚴格不等式成立，由互補松弛定理原規劃的最優解中x2*=x3*=x4*

=0，因為w1*和w2*均不等于0，從而原規劃的最優解中兩個約束是緊的，即第20頁，共51頁，2023年，2月20日，星期六對偶定理例2.4求解線性規劃問題的對偶問題：第21頁，共51頁，2023年，2月20日，星期六對偶定理用單純形表格求解線性規劃問題第22頁，共51頁，2023年，2月20日，星期六對偶定理原問題的最優解為對偶問題的最優解為第23頁，共51頁，2023年，2月20日，星期六作業P74： 4，5，7第24頁，共51頁，2023年，2月20日，星期六2.3對偶單純形法1.理論基礎 考慮線性規劃標準形其對偶規劃為第25頁，共51頁，2023年，2月20日，星期六對偶單純形法由對偶定理，若有x*,w*滿足Ax*=b,x*0,w*A≤

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

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

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