第二章對偶理論與靈敏度分析

第二章對偶理論與靈敏度分析課件第1頁，課件共133頁，創(chuàng)作于2023年2月本章重點1、掌握寫出對偶問題的方法，原問題與其對偶問題的對應關系2、掌握對偶問題的基本理論和性質(zhì)3、理解影子價格的定義和意義4、理解并掌握對偶單純形方法的思想和步驟5、掌握線性規(guī)劃靈敏度分析(1)資源數(shù)量bi

發(fā)生變化的分析(2)目標函數(shù)中價值系數(shù)cj發(fā)生變化的分析難點難點第2頁，課件共133頁，創(chuàng)作于2023年2月XBXNXSbXBBNIbCCBCN00了解----單純形的矩陣描述XS為松弛變量第3頁，課件共133頁，創(chuàng)作于2023年2月XBXNXSbXBIB－1NB－1B－1b

N0CN－CBB－1N－CBB－1－CBB－1b單純性法計算時，總選取單位矩陣I為初始基，對應基變量為XS,設迭代若干步后，基變量變?yōu)閄B,XB在初始單純性表中的系數(shù)矩陣為B。則該步的單純性表中由XB

系數(shù)組成的矩陣為單位矩陣I，對應XS的系數(shù)矩陣在新表中應為B-1

Y=CBB-1稱為單純性乘子（對偶變量）第4頁，課件共133頁，創(chuàng)作于2023年2月2.3對偶問題提出

例2.2：某公司在計劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及AB兩種原材料的消耗如表所示，該工廠每生產(chǎn)一件產(chǎn)品I可獲利2元，每生產(chǎn)一件產(chǎn)品II可獲利3元，問應該如何安排計劃使該工廠獲利最多？

舉例2第5頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析

先根據(jù)圖表來列出模型

MaxZ=2X1+3X2

X1+2X2≤8

4X1≤16

4X2≤12

X1,X2≥0

舉例第6頁，課件共133頁，創(chuàng)作于2023年2月設用y1,y2,y3分別表示出租單位設備臺時的租金和出讓單位原材料A,B的附加額.

現(xiàn)在從另一個角度來考慮企業(yè)的決策問題。假如企業(yè)自己不生產(chǎn)產(chǎn)品，而將現(xiàn)有的資源轉(zhuǎn)讓或出租給其它企業(yè)，那么資源的轉(zhuǎn)讓價格是多少才合理？合理的價格應是對方用最少的資金購買本企業(yè)的全部資源，而本企業(yè)所獲得的利潤不應低于自己用于生產(chǎn)時所獲得的利潤。這一決策問題可用下列線性規(guī)劃數(shù)學模型來表示。第7頁，課件共133頁，創(chuàng)作于2023年2月他在做定價決策時,作如下比較:若用一個單位設備臺時和4個單位原材料A可以生產(chǎn)一件產(chǎn)品I,可獲利2元,那么生產(chǎn)每件產(chǎn)品I的設備臺時和原材料出租和出讓的所有收入應不低于生產(chǎn)一件產(chǎn)品I的利潤,這就有y1+4y2≥2第8頁，課件共133頁，創(chuàng)作于2023年2月

同理將生產(chǎn)每件產(chǎn)品II的設備臺時和原材料的出租和出讓的所有收入應不低于生產(chǎn)一件產(chǎn)品II的利潤,這就有2y1+4y3≥3

把工廠所有設備臺時和資源都出租和出讓,其收入為

f=8y1+16y2+12y3第9頁，課件共133頁，創(chuàng)作于2023年2月從工廠決策者的角度來看，f當然是越大越好,但從接受者眼光來說f是越少越好,所以工廠決策者只可以在滿足≥ 所有產(chǎn)品的利潤條件下,使其總收入盡可能的小.因此第10頁，課件共133頁，創(chuàng)作于2023年2月我們稱這個線性規(guī)劃問題為線性規(guī)劃問題（這稱為原問題）的對偶問題。各模型中有關數(shù)據(jù)的“位置”示意圖如下。

矩陣A矩陣AT第11頁，課件共133頁，創(chuàng)作于2023年2月對偶問題提出例2.3某工廠擁有A、B、C三種類型的設備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設備可利用的時數(shù)如下表所示。求獲最大利潤的方案。第12頁，課件共133頁，創(chuàng)作于2023年2月表2.3第13頁，課件共133頁，創(chuàng)作于2023年2月不難得出下面一對對偶問題。原問題

第14頁，課件共133頁，創(chuàng)作于2023年2月對偶問題

不少于甲產(chǎn)品的利潤不少于乙產(chǎn)品的利潤第15頁，課件共133頁，創(chuàng)作于2023年2月例2.4：資源利用問題考慮：資源擁有者為了實現(xiàn)一定的收入目標，將其所擁有的資源出售，給每一種資源如何定價？

第16頁，課件共133頁，創(chuàng)作于2023年2月解：表示出售單位數(shù)量的第i種資源的價格。資源擁有者在做出售資源的決策時，考慮出售資源的收入不應該低于生產(chǎn)所獲得的收入，則有：第17頁，課件共133頁，創(chuàng)作于2023年2月如果資源擁有者將所有資源出售，則他得到的總收入

f=第18頁，課件共133頁，創(chuàng)作于2023年2月資源擁有者出售每一種資源的最低估價，可通過求解線性規(guī)劃問題而得到。第19頁，課件共133頁，創(chuàng)作于2023年2月對同一個資源利用問題，從不同的角度考慮，可以得到兩個相互聯(lián)系的線性規(guī)劃模型，這就是線性規(guī)劃的對偶問題。第20頁，課件共133頁，創(chuàng)作于2023年2月由上面的例子我們可以知道原問題與對偶問題的關系1．線性規(guī)劃問題是對稱形式

Maxz=CXMinf=Ybs.t.Ax≤bs.t.YA≥c

x≥0y≥0“Max--≤”“Min--≥”原問題與對偶問題的關系第21頁，課件共133頁，創(chuàng)作于2023年2月互為轉(zhuǎn)置列向量行向量n個變量n個約束第22頁，課件共133頁，創(chuàng)作于2023年2月例2.5寫出下述問題的對偶問題第23頁，課件共133頁，創(chuàng)作于2023年2月解：上述問題的對偶問題為第24頁，課件共133頁，創(chuàng)作于2023年2月(1)若一個模型為目標求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標求“極小”，約束是“大于等于”的不等式。即“max，≤”和“min，≥”相對應。如上面例題所示一對對稱形式的對偶規(guī)劃之間具有下面的對應關系第25頁，課件共133頁，創(chuàng)作于2023年2月(2)從約束系數(shù)矩陣看：一個模型中為Ａ，則另一個模型中為AT。一個模型是m個約束，n個變量，則它的對偶模型為n個約束，m個變量。(3)從數(shù)據(jù)b、C的位置看：在兩個規(guī)劃模型中，b和C的位置對換。(4)兩個規(guī)劃模型中的變量皆非負。第26頁，課件共133頁，創(chuàng)作于2023年2月補充例子原問題：第27頁，課件共133頁，創(chuàng)作于2023年2月對偶問題：第28頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析2.線性規(guī)劃問題是非對稱形式

對于非對稱形式的規(guī)劃，可以按照下面的對應關系直接給出其對偶規(guī)劃。（1）將模型統(tǒng)一為“max，≤”或“min，≥”的形式，對于其中的等式約束按下面（2）、（3）中的方法處理；第29頁，課件共133頁，創(chuàng)作于2023年2月（2）若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應的那個變量取值沒有非負限制；（3）若原規(guī)劃的某個變量的值沒有非負限制，則在對偶問題中與此變量對應的那個約束為等式。綜上所述，線性規(guī)劃的原問題和對偶問題的關系，其變換形式歸納為表2.5第30頁，課件共133頁，創(chuàng)作于2023年2月原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標函數(shù)max目標函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項第31頁，課件共133頁，創(chuàng)作于2023年2月下面我們以一個例子說明上述關系寫出下述線性規(guī)劃問題的對偶問題第32頁，課件共133頁，創(chuàng)作于2023年2月為了寫出對偶問題，思路是先將其轉(zhuǎn)化為對稱形式，為此（1）約束條件（1a）兩端同乘以-1；（2）約束條件（3a）變換為和

（3）令

（4）第33頁，課件共133頁，創(chuàng)作于2023年2月則線性規(guī)劃變換成如下的對稱形式第34頁，課件共133頁，創(chuàng)作于2023年2月令對應上述4個約束的對偶變量分別為寫出對偶問題第35頁，課件共133頁，創(chuàng)作于2023年2月再令將（3b）和（4b）合并，（2b）兩端同乘以-1，于是有第36頁，課件共133頁，創(chuàng)作于2023年2月例2.6寫出下述線性規(guī)劃問題的對偶問題

第37頁，課件共133頁，創(chuàng)作于2023年2月第38頁，課件共133頁，創(chuàng)作于2023年2月補充例題寫出下述線性規(guī)劃問題的對偶問題第39頁，課件共133頁，創(chuàng)作于2023年2月解：對偶問題為第40頁，課件共133頁，創(chuàng)作于2023年2月

小練習寫出下列問題的對偶問題第41頁，課件共133頁，創(chuàng)作于2023年2月作業(yè)：2.1（1）（2）（3）第42頁，課件共133頁，創(chuàng)作于2023年2月2.4對偶問題的基本性質(zhì)

【性質(zhì)1】

對稱性

對偶問題的對偶是原問題。(P)(D)

MaxZ=CXMinf=Ybs.t.AX≤bs.t.YA≥CX≥0Y≥0“Max--≤”“Min--≥”

第43頁，課件共133頁，創(chuàng)作于2023年2月

【證】因為X*、Y*是可行解，故有AX*≤b,X*≥0及Y*A≥C，Y*≥0,將不等式AX*≤b兩邊左乘Y*，得Y*AX*≤Y*b再將不等式Y*A≥C兩邊右乘X*，得CX*≤Y*AX*故CX*≤Y*AX*≤Y*b這一性質(zhì)說明了兩個線性規(guī)劃互為對偶時，求最大值的線性規(guī)劃的任意目標值都不會大于求最小值的線性規(guī)劃的任一目標值，不能理解為原問題的目標值不超過對偶問題的目標值?！拘再|(zhì)2】弱對偶性設X*、Y*分別為LP(max)與DP(min)的可行解，則第44頁，課件共133頁，創(chuàng)作于2023年2月由這個性質(zhì)可得到下面幾個結論：(1)（LP）的任一可行解的目標值是（DP）的最優(yōu)值下界；（DP）的任一可行解的目標是（LP）的最優(yōu)值的上界；

(2)在互為對偶的兩個問題中，若一個問題可行且具有無界解，則另一個問題無可行解；

(3)若原問題可行且另一個問題不可行，則原問題具有無界解。第45頁，課件共133頁，創(chuàng)作于2023年2月【性質(zhì)3】最優(yōu)準則定理設X*與Y*分別是（LP）與（DP）的可行解，則當X*、Y*是（LP）與（DP）的最優(yōu)解當且僅當CX*=Y*b.【證】若X*、Y*為最優(yōu)解，B為（LP）的最優(yōu)基，則有Y*=CBB－1，并且當CX*=Y*b時，由性質(zhì)1，對任意可行解有即Y*b是（DP）中任一可行解的目標值的下界，CX*是（LP）中任一可行解的目標值的上界，從而X*、Y*是最優(yōu)解。第46頁，課件共133頁，創(chuàng)作于2023年2月【性質(zhì)4】線性規(guī)劃的對偶原理（1）若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且二者最優(yōu)值相等。（強對偶性）（2）若原問題（對偶問題）的解為無界解，則其對偶問題（原問題）無可行解。（無界性）注：這個問題的性質(zhì)不存在逆。(看后面例子)第47頁，課件共133頁，創(chuàng)作于2023年2月【證】（1）設（LP）有最優(yōu)解X0,那么對于最優(yōu)基B必有C-CBB-1A≤0與－CBB-1≤0，即有Y°A≥C與Y°≥0，這里Y°=CBB-1

，從而Y°是可行解，對目標函數(shù)有由性質(zhì)3知Y°是最優(yōu)解。（2）由弱對偶性，顯然得注：這個問題的性質(zhì)不存在逆第48頁，課件共133頁，創(chuàng)作于2023年2月例如下述一對問題兩者皆無可行解。

原問題（對偶問題）對偶問題（原問題）

minw=-x1-x2maxz=y1+y2

x1–x2≥1 y1-y2≤

-1-x1+x2≥1 -y1+y2≤-1x1,x2≥0y1,y2≥0由性質(zhì)4還可推出另一結論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。第49頁，課件共133頁，創(chuàng)作于2023年2月【性質(zhì)5】互補松弛定理設X0、Y0分別為（LP）與（DP）的可行解，XS和YS分別是（LP）與（DP）對應的松弛變量向量，則X0和Y0是最優(yōu)解當且僅當YSX0=0和

Y0XS=0【證】設X°和Y°是最優(yōu)解,由性質(zhì)3，CX0=Y0b，由于XS和YS是松弛變量，則有AX0＋XS＝bY0A－YS=C將第一式左乘Y0，第二式右乘X0得Y0AX0＋Y0XS＝Y0bY0AX0－YSX0=CX0第50頁，課件共133頁，創(chuàng)作于2023年2月顯然有Y0XS=－YSX0又因為Y°、Xs、Ys、X°≥0，所以有Y°XS=0和YSX°=0成立。反之，當Y°XS=0和YSX°=0時，有Y°AX°＝Y°bY°AX°=CX°顯然有Y0b=CX°,由性質(zhì)3知X°與Y°是（LP）與（DP）的最優(yōu)解。證畢。第51頁，課件共133頁，創(chuàng)作于2023年2月性質(zhì)5告訴我們已知一個問題的最優(yōu)解時求另一個問題的最優(yōu)解的方法，即已知Y*求X*或已知X*求Y*。Y*

XS=0和YSX*

=0兩式稱為互補松弛條件。將互補松弛條件寫成下式由于變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關系：其中第52頁，課件共133頁，創(chuàng)作于2023年2月(1)當yi*>0時，,反之當時yi*=0；利用上述關系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。性質(zhì)5的結論和證明都是假定（P）與（D）為對稱形式，事實上對于非對稱形式，性質(zhì)5的結論仍然有效。注：上述針對對稱形式證明的對偶問題的性質(zhì)，同樣適應于非對稱形式。第53頁，課件共133頁，創(chuàng)作于2023年2月【補充例題】已知線性規(guī)劃的最優(yōu)解是求對偶問題的最優(yōu)解?！窘狻繉ε紗栴}是下面舉例說明互補松弛條件的應用第54頁，課件共133頁，創(chuàng)作于2023年2月解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為Y=（1，1），最優(yōu)值w=26。因為X1≠0，X2≠0，所以對偶問題的第一、二個約束的松弛變量等于零，即第55頁，課件共133頁，創(chuàng)作于2023年2月【性質(zhì)6】假設原問題是：maxz=CX;AX+Xs=b;X>=0它的對偶問題是：minf=Yb;YA-Ys=C;Y>=0則原問題單純形表的檢驗數(shù)行對應其對偶問題的一個基解。其對應關系見如下表第56頁，課件共133頁，創(chuàng)作于2023年2月-0

N-Y-這里是對應于原問題中基變量XB

剩余變量，是對應于原問題中非基變量XN剩余變量.-第57頁，課件共133頁，創(chuàng)作于2023年2月一個問題max另一個問題min有最優(yōu)解有最優(yōu)解性質(zhì)4無無最優(yōu)解無最優(yōu)解性質(zhì)4最優(yōu)無界解（有可行解）無可行解性質(zhì)2解無可行解無界解（有可行解）應用已知最優(yōu)解通過解方程求最優(yōu)解性質(zhì)5已知檢驗數(shù)檢驗數(shù)乘以－1求得基本解性質(zhì)6對于這六個對偶性質(zhì)，這些性質(zhì)是研究原問題與對偶問題解的對應關系；下表也許對您了解這些性質(zhì)有幫助。第58頁，課件共133頁，創(chuàng)作于2023年2月例2.7：判斷下例說法是否正確，為什么？A如果線性規(guī)劃的原問題存在可行解，則其對偶問題也一定存在可行解B如果線性規(guī)劃的對偶問題無可行解，則原問題也一定無可行解。C在互為對偶的一對原問題和對偶問題中，不管原問題是求極大或者極小，原問題可行解的目標函數(shù)值都一定不超過其對偶問題可行解的目標函數(shù)值。

第59頁，課件共133頁，創(chuàng)作于2023年2月解：A不對。因為原問題為無界解時（它當然有可行解），其對偶問題無可行解。B此句為A的逆否命題，所以也不對。C不對。因為哪個問題是原問題，哪個問題是對偶問題是相對而言的。

第60頁，課件共133頁，創(chuàng)作于2023年2月例2.8已知線性規(guī)劃問題

試用對偶理論證明上述線性規(guī)劃問題有無界解（即有可行解但無最優(yōu)解）。第61頁，課件共133頁，創(chuàng)作于2023年2月證明：所給問題的對偶問題為第62頁，課件共133頁，創(chuàng)作于2023年2月顯然約束條件中與矛盾，即此對偶問題無可行解，因此所給原問題無最優(yōu)解，它只可以是無界解或者無可行解。然而X=（0，0，0）顯然是它的可行解，因此它必定有無界解。第63頁，課件共133頁，創(chuàng)作于2023年2月

補充例題給出線性規(guī)劃（1）寫出對偶問題（2）用對偶理論證明上述線性規(guī)劃目標函數(shù)值無界第64頁，課件共133頁，創(chuàng)作于2023年2月解：（1）對偶問題為第65頁，課件共133頁，創(chuàng)作于2023年2月上述對偶問題中,

則與對偶問題的第一個約束條件矛盾，所以對偶問題無可行解，因而原問題無最優(yōu)解，它只可以是無界解或者無可行解，然而x=(10,4,2)顯然是他的可行解，因而它必定有無界解。第66頁，課件共133頁，創(chuàng)作于2023年2月例2.9已知線性規(guī)劃問題已知其對偶問題的最優(yōu)解為試用對偶理論找出原問題的最優(yōu)解。第67頁，課件共133頁，創(chuàng)作于2023年2月解：先寫出它的對偶問題

第68頁，課件共133頁，創(chuàng)作于2023年2月將的值代入約束條件，得到(2),(3),(4)為嚴格不等式;由互補松弛性得到因為;原問題的兩個約束條件的松弛變量由互補松弛性得到為0，因此兩個約束條件應該取等式,所以有第69頁，課件共133頁，創(chuàng)作于2023年2月求解后得到所以原問題的最優(yōu)解為X=(1,0,0,0,1)T第70頁，課件共133頁，創(chuàng)作于2023年2月

補充例題:

已知原問題的最優(yōu)解為X*=（0,0,4），Z=12,試求對偶問題的最優(yōu)解。第71頁，課件共133頁，創(chuàng)作于2023年2月解:對偶問題為將X*=（0,0,4）代入原問題中，有下式：第72頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析所以，根據(jù)互補松弛條件，必有y*1=y*2=0，代入對偶問題約束（3）式，y3=3。因此，對偶問題的最優(yōu)解為

Y*=（0,0,3），W=12。第73頁，課件共133頁，創(chuàng)作于2023年2月因為原問題和對偶問題的最優(yōu)值相等，將線性規(guī)劃的目標函數(shù)表達成資源的函數(shù)，故有即yi是第i種資源的變化率，稱yi是第i種資源的邊際價格，說明當其它資源供應量bk(k≠i)不變時，bi增加一個單位時目標值Z增加yi個單位．2.5影子價格第74頁，課件共133頁，創(chuàng)作于2023年2月

影子價格(Shadowprice):

原始線性規(guī)劃問題考慮的是充分利用現(xiàn)有資源，以產(chǎn)品的數(shù)量和單位產(chǎn)品的收益來決定企業(yè)的總收益，沒有考慮到資源的價格，但實際在構成產(chǎn)品的收益中，不同的資源對收益的貢獻也不同，它是企業(yè)生產(chǎn)過程中一種隱含的潛在價值，經(jīng)濟學中稱為影子價格，即對偶問題中的決策變量yi的值。對偶變量yi

就是第i個約束的影子價格（邊際價格）第75頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析影子價格是一個向量，它的分量表示最優(yōu)目標值隨相應資源數(shù)量變化的變化率。若x*,y*

分別為（LP）和（DP）的最優(yōu)解，那么，cT

x*=bT

y*

。根據(jù)f=bTy*=b1y1*+b2y2*+

+bmym*

可知

f/

bi

=

yi*

yi*

表示bi

變化1個單位對目標f

產(chǎn)生的影響，稱yi*

為bi的影子價格。

注意：若B

是最優(yōu)基，y*=CBB-1

為影子價格向量。第76頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析影子價格的經(jīng)濟含義

(1)影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，對資源的使用有兩種考慮：第一，是否將設備用于外加工或出租，若租費高于某設備的影子價格，可考慮出租該設備，否則不宜出租。第二，是否將投資用于購買設備，以擴大生產(chǎn)能力，若市價低于某設備的影子價格，可考慮買進該設備，否則不宜買進。第77頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析（2）影子價格表明資源增加對總效益產(chǎn)生的影響。根據(jù)推論“設x0和y0分別為原規(guī)劃（P）和對偶規(guī)劃（D）的可行解，當cx0=bTy0時，x0、y0分別是兩個問題的最優(yōu)解”可知，在最優(yōu)解的情況下，有關系

因此，可以將z*看作是bi,i=1,2，…,m的函數(shù)，對bi求偏導數(shù)可得到

這說明，如果右端常數(shù)增加一個單位，則目標函數(shù)值的增量將是第78頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析（3）根據(jù)對偶問題的互補松弛性質(zhì)中時；當時，，這表明生產(chǎn)過程中如果某種資源未得到充分利用時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢。

第79頁，課件共133頁，創(chuàng)作于2023年2月（4）影子價格是企業(yè)生產(chǎn)過程中資源的一種隱含的潛在價值，表明單位資源的貢獻，與市場價格是不同的兩個概念．同一種資源在不同的企業(yè)、生產(chǎn)不同的產(chǎn)品或在不同時期影子價格都不一樣．例如，某種鋼板市場價格是每噸8000元，一個企業(yè)用來生產(chǎn)汽車，另一個企業(yè)用來生產(chǎn)空調(diào)外殼，每噸鋼板的產(chǎn)值是不一樣的．（5）影子價格是一個變量．由的含義知影子價格是一種邊際產(chǎn)出，與bi的基數(shù)有關，在最優(yōu)基B不變的條件下yi不變，當某種資源增加或減少后，最優(yōu)基B可能發(fā)生了變化，這時yi的值也隨之發(fā)生變化．第80頁，課件共133頁，創(chuàng)作于2023年2月根據(jù)對偶問題的性質(zhì)，因為當即有即其對偶問題的解為可行解，由此對偶問題和原問題均為最優(yōu)解。反之，如果存在一個對偶問題的可行基B，即對這時只要有即原問題的解也為可行解，即兩者均為最優(yōu)解。否則，保持對偶可行性，進行迭代2.6對偶單純形法第81頁，課件共133頁，創(chuàng)作于2023年2月設原問題是（記為LP）：對偶問題是（記為DP）：對偶單純形法的條件是：初始表中對偶問題可行，即極大化問題時

，極小化問題時。第82頁，課件共133頁，創(chuàng)作于2023年2月對偶單純形法的基本思想是：從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應著一個對偶可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應著另一個對偶可行解（檢驗數(shù)非正）。如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。第83頁，課件共133頁，創(chuàng)作于2023年2月Chapter2對偶單純形法在什么情況下使用：應用前提：有一個基，其對應的基滿足:

①單純形表的檢驗數(shù)行全部非正（對偶可行）；②變量取值可有負數(shù)（非可行解）。注：通過矩陣行變換運算，使所有相應變量取值均為非負數(shù)即得到最優(yōu)單純形表。第84頁，課件共133頁，創(chuàng)作于2023年2月這樣的優(yōu)點在于，一是當問題的模型中存在“>=”的約束條件時，不需要引入人工變量，只要在約束條件方程的兩邊乘以“-1”后加入松弛變量，再按單純形法求解。二是當約束條件方程個數(shù)m大于變量個數(shù)n的時候，將原問題變換成對偶問題求解，計算量一般會小些。第85頁，課件共133頁，創(chuàng)作于2023年2月Chapter2對偶單純形法求解線性規(guī)劃問題步驟：

1.建立初始對偶單純形表,對應一個基本解,所有檢驗數(shù)均非正,轉(zhuǎn)2；

2.若b’≥0,則得到最優(yōu)解,停止;否則,若有bi<0,

3.換出變量：設min{bi|bi<0}=bk，則選k行的基變量為換出變量.第86頁，課件共133頁，創(chuàng)作于2023年2月4.若所有akj’≥0(j=1,2,…,n)，則原問題無可行解,停止;否則,若有akj<0則選

=min{

j/akj┃akj<0}=

r/akr

那么xr

為換入變量,轉(zhuǎn)5；

5.以akr’為主元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?（旋轉(zhuǎn)變換）,轉(zhuǎn)2。第87頁，課件共133頁，創(chuàng)作于2023年2月例2.10求線性規(guī)劃第88頁，課件共133頁，創(chuàng)作于2023年2月解：引入松弛變量將上述問題轉(zhuǎn)化為得對偶單純形表2.7第89頁，課件共133頁，創(chuàng)作于2023年2月表2.7此時基本解為X=(0,0,0,0,-2,-3),不可行，轉(zhuǎn)第二步。因為min{-2,-3}=-3,所以x6為換出變量，又因為Min{-2/-2,-5/-1}=1,所以x1為換入變量。得到新的單純形表2.8第90頁，課件共133頁，創(chuàng)作于2023年2月表2.8此時基本解為X=(3/2,0,0,0,-1/2,0),不可行，轉(zhuǎn)第二步。因為-1/2<0,所以x5為換出變量，又因為Min{-4/(-5/2),{-4/(-5/2),{-9/(-5/2),{-1/(-1/2)}=8/5,所以x2和x3

都可以作為換入變量。任選其中一個x2，做線性變換得到新的單純形表2.9第91頁，課件共133頁，創(chuàng)作于2023年2月表2.9得到一個基本解為X=(8/5,1/5,0,0,0,0)T,因解是可行的，所以滿足最優(yōu)檢驗下的基本可行解因而也是最優(yōu)解。

第92頁，課件共133頁，創(chuàng)作于2023年2月Chapter2從以上求解過程中我們可以看到，對偶單純形法有以下的優(yōu)點：

1)初始解可以是非可行解，當檢驗數(shù)都為負數(shù)時，就可以進行基的變換，這時不需要加入人工變量，因此可以簡化計算。

2)當變量多于約束條件，對于這樣的線性規(guī)劃問題，用對偶單純形法計算可以減少計算工作量，因此對于變量較少，而約束條件很多的線性規(guī)劃問題，可以首先將它變換成為對偶問題，然后用對偶單純形法來求解。

第93頁，課件共133頁，創(chuàng)作于2023年2月3)在靈敏度分析中，有時需要使用對偶單純形法，這樣可以使問題處理簡化。對偶單純形法的局限在于：對于大多數(shù)的線性規(guī)劃問題，很難找到一個初始可行基，因而這個方法在求解線性規(guī)劃問題時很少單獨應用。第94頁，課件共133頁，創(chuàng)作于2023年2月從幾何圖形上看單純性和對偶單純性的區(qū)別已知Q2為最優(yōu)解點x1x2O4

Q2(4,2)Q1Q3Q43ABC單純形法：OQ1O2

或OQ4O3O2

對偶單純性法：ABQ2

或BQ2注意：對偶單純形對迭代點的要求---對偶可行性

第95頁，課件共133頁，創(chuàng)作于2023年2月（1）用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解；（2）初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準則；（3）對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進基變量；（4）對偶單純形法在確定出基變量時，若不遵循

規(guī)則，任選一個小于零的bi對應的基變量出基，不影響計算結果，只是迭代次數(shù)可能不一樣．

應當注意：第96頁，課件共133頁，創(chuàng)作于2023年2月2.7靈敏度分析

系數(shù)br、cj變化，最優(yōu)解的最優(yōu)性、可行性是否變化？

系數(shù)在什么范圍內(nèi)變化，最優(yōu)解或最優(yōu)性不變？

如何求新的最優(yōu)解？本節(jié)重點第97頁，課件共133頁，創(chuàng)作于2023年2月例2.2第98頁，課件共133頁，創(chuàng)作于2023年2月1.求解此線性規(guī)劃的解2.當C2=2時，新的線性規(guī)劃問題的解3.當C2=5時，新的線性規(guī)劃問題的解4.當b1=9時，新的線性規(guī)劃問題的解5.當b1=12時，新的線性規(guī)劃問題的解第99頁，課件共133頁，創(chuàng)作于2023年2月靈敏度分(SensitivityAnalyisi),就是分析研究LP模型參數(shù)aij,br,cj

的取值變化對最優(yōu)解和最優(yōu)基的影響。它在應用線性規(guī)劃解決實際問題的過程中是非常有用的。實際LP問題的最優(yōu)解，是在模型參數(shù)區(qū)某一組定值的基礎上獲得的，而這些定值往往是一些預測和估計的數(shù)字，因此或者有一定的誤差，或者可能變動。如市場條件出現(xiàn)了變動，cj的值就會發(fā)生變化；aij是隨著工藝技術條件的改變而改變的，而br

值則是根據(jù)資源投入后能產(chǎn)出多大經(jīng)濟效果來決定的一種決策選擇。

第100頁，課件共133頁，創(chuàng)作于2023年2月因此就會產(chǎn)生以下問題：當這些參數(shù)中的一個或幾個發(fā)生了變化時，問題的最優(yōu)解會有什么變化，或者這些參數(shù)在一個多大的范圍內(nèi)變化時，問題的最優(yōu)解不變。這就是我們學習靈敏度分析所要研究解決的問題。當然通過上面的學習我們知道：當線性規(guī)劃問題中的一個或者幾個參數(shù)變化時，可以用單純形法從頭計算，看最優(yōu)解有無變化，但是這樣做既麻煩又沒有必要。第101頁，課件共133頁，創(chuàng)作于2023年2月因為我們知道單純形法的迭代運算是從一組基向量變換為另一組基向量，表中每步迭代得到的數(shù)字只隨基向量的不同選擇而改變，因此有可能把個別參數(shù)的變化直接在計算得到最優(yōu)解的單純形表上面反映出來，這樣就不需要從頭計算了，而直接對計算得到的最優(yōu)解的單純形表進行審查，看一些數(shù)字變化后，是否滿足最優(yōu)解的條件，如果不滿足的話，再從這個表開始進行迭代計算，求出最優(yōu)解。第102頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析靈敏度分析的步驟可以歸納如下：1)將參數(shù)的改變計算反映到最終單純形表上來;具體的計算方法是，按照相關公式計算出由參數(shù)的變化而引起的最終單純形表上有關數(shù)字的變化；2)檢查原問題是否仍為可行解;3)檢查對偶問題是否仍為可行解;4)我們可以按照書中表中羅列的幾種情況得出結論和決定繼續(xù)計算的步驟第103頁，課件共133頁，創(chuàng)作于2023年2月第104頁，課件共133頁，創(chuàng)作于2023年2月第105頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析2.7.1資源數(shù)量br發(fā)生變化的分析資源數(shù)量變化是指系數(shù)br發(fā)生了變化，br變化為br’=br+br，并假設規(guī)劃問題的其它系數(shù)都沒有發(fā)生變化。根據(jù)討論，最優(yōu)解的基變量xB=B-1b.這樣使得最終表中原問題的解相應的變化為XB’=B-1（b+

b）其中，

b=（0，…,

br,0,…,0）T1、資源系數(shù)br的靈敏度變化分析第106頁，課件共133頁，創(chuàng)作于2023年2月根據(jù)討論，只要保持B-1(b+

b)≥0，最終表中檢驗數(shù)不變，則最優(yōu)基不變，但最優(yōu)解的值變化，XB’=B-1(b+

b)為新的最優(yōu)解；否則，需要利用對偶單純形法繼續(xù)計算。

為了使最優(yōu)基B不變，求br的變化范圍。第107頁，課件共133頁，創(chuàng)作于2023年2月第108頁，課件共133頁，創(chuàng)作于2023年2月B-1的第r列第109頁，課件共133頁，創(chuàng)作于2023年2月這個時候在最終表里面求得的b列的所有元素

i=1,2,…，m。由此可得

由此可得，最優(yōu)基不變（檢驗數(shù)不變）的條件是

第110頁，課件共133頁，創(chuàng)作于2023年2月例題:

問題：某公司在計劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及AB兩種原材料的消耗如表所示，該工廠每生產(chǎn)一件產(chǎn)品I可獲利2元，每生產(chǎn)一件產(chǎn)品II可獲利3元，問應該如何安排計劃使該工廠獲利最多？

III資源限制設備128臺時原料A4016公斤原料B0412公斤單位利潤23第111頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析第112頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析最終單純形表為:若該廠又從別處抽出4臺時用于生產(chǎn)I、II，求這時該廠生產(chǎn)產(chǎn)品I,II的最優(yōu)方案。第113頁，課件共133頁，創(chuàng)作于2023年2月

這里各列分別對應b1、b2、b3

的單一變化下面給出最優(yōu)基不變時，△b1

的變化范圍

第114頁，課件共133頁，創(chuàng)作于2023年2月B=（x1x5x2)可得△b1≥-2/0.5=-4,△b1≤-4/-2=2由公式知△b1變化范圍[-4,2],顯然b1變化范圍[4,10]因此，當△b1=4時，最優(yōu)基發(fā)生變化，需要用對偶單純形法繼續(xù)求解第115頁，課件共133頁，創(chuàng)作于2023年2月解：先計算B-1△b將這個結果放到最終表中得第116頁，課件共133頁，創(chuàng)作于2023年2月第117頁，課件共133頁，創(chuàng)作于2023年2月表中b列中有負數(shù)，故可用對偶單純形法求最優(yōu)解。最優(yōu)解見下表

第118頁，課件共133頁，創(chuàng)作于2023年2月即該廠最優(yōu)生產(chǎn)方案應改為生產(chǎn)產(chǎn)品I為4件，生產(chǎn)產(chǎn)品II為3件，獲利17元。從最優(yōu)表中看出x3=2,即設備有2小時未被利用。第119頁，課件共133頁，創(chuàng)作于2023年2月2.7.2價值系數(shù)cj的變化分析當目標系數(shù)cj變化時，可能引起檢驗數(shù)的變化，從而影響最優(yōu)性條件是否滿足。為了方便起見，分別就對應的是非基變量與基變量兩中情況來討論最優(yōu)解不變的條件。第120頁，課件共133頁，創(chuàng)作于2023年2月（1）當cj是非基底變量xj的系數(shù)，檢驗數(shù)為或當cj變化

cj后，檢驗數(shù)要小于或等于零，即只要

j’

≤0,即

cj≤-

j，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù)

j用

j’取代，繼續(xù)單純形法的表格計算。第121頁，課件共133頁，創(chuàng)作于2023年2月Chapter2靈敏度分析例題:

Maxz=-2x1-3x2-4x3

S.t.

-x1-2