【天津大學】《運籌學》(精品課) P10 - 10. 對偶問題與靈敏度分析 教學錄像(1)

长安书院_
146粉絲
3 次觀看·2026年5月9日
AI 生成·可能包含錯誤
同學們大家好
我們在上一節中學習了線性規劃的一個核心內容
單純刑法
單純刑法的思想是在可行域的腳點中尋優
可行域的腳點在數學上的概念是基本可行解
基本可行解是由一個基所決定的
它的基變量的表達式是B逆B
單純刑法的主要步驟是在模型化爲標準型之後
首先確定一個初始基可行解
然後進行最優性檢驗
然後進行換機迭代
單純刑法的具體計算和實現是在單純刑表上進行的
單純刑表的原理主要就是依據單純刑法的原理
同時依據相鄰兩個基的逆振之間的關係
設計的基於初等行變換的計算模式
對於模型化爲標準型之後
A中仍然不含愛的情況
可以用人工變量大M法進行解決
大M法中的這個大M就是一個乏音字
它的作用是在人工變量模型中
迫使人工變量逐步出擊
上述的步驟雖然主要是針對極大型的模型而言的
但是實際上對於極小型的模型
它的計算也可以直接用單純刑表進行
極小型和極大型在單純刑表上的區別
只是檢驗數差一個負號
我們在介紹了單純刑法的內容之後
接下來我們將要繼續介紹
線性規劃中的另一個重要內容
就是隊友問題與靈敏度分析
先來介紹隊友問題及其模型
隊友理論是線性規劃的重要基礎理論
它揭示了每一個線性規劃都存在
與它隊友的一個線性規劃
二者之間有密切的聯繫
以至於把二者放在一起研究
往往比單獨研究一個問題更有意義
那麼什麼是線性規劃的隊友問題呢?
我們以前面的例1.1爲例
加以說明
我們前面介紹的例1.1
是用煤電油三種資源
生產甲乙兩種產品
煤電油三種資源數量都是有限的
分別是煤360,電200,油300
甲乙產品的單位收益是7和12
甲乙產品對三種資源的單號
分別是943和450
這個煤電油的生產甲乙產品的問題
我們把它的模型記爲P
現在假設有另外一家廠商
提出想購買這個生產廠商的煤電油全部資源
於是就產生了一個購買問題
作爲購買者
他當然是希望他的總花費盡量少
於是我們可以嘗試建立這個購買者的線性規劃模型
我們來分析模型的三要素是什麼
也就是購買者的決策變量
目標函數和約束條件
作爲購買者
他要決策什麼量呢
他來買資源
主要就是和賣者談判決定資源的價格
如果價格合理
賣者是可以同意出售的
所以要決策的量是資源的價格
購買者的目標
剛纔已經說了是總花費及小化
我們計三種資源的價格分別爲
Y1,Y2,Y3
總花費計爲W
則可以寫出總花費的表達式
總花費的表達式是
W等於360Y1加上200Y2加上300Y3
目標函數建立以後
我們再來分析約束條件
購買者要受到來自誰的約束呢
他最基本的約束是來自賣資源的人
賣資源的人的合理的要求
是我賣給你獲得的收益
不能低於我用於自行生產可獲得的收益
因爲他自行生產的是甲乙兩種產品
我們可以分別甲乙兩種產品來加以分析
生產甲乙產品的資源單號數量是已知的
分別是943和450
這些資源賣出去所獲得的收益
要求不能低於自行生產可獲得的收益
7和12
這樣呢
我們就列出了這個約束表達式
分別是甲的和甲子甲產品相應的
這個約束是9Y1加上4Y2加上3Y3
大於等於7
這個不等式的左邊就是生產一件甲產品的資源
943賣出去所獲得的收益
不等式的右端7是自行生產可獲得的收益
那麼這就是我賣出去的收益
不得低於用於自行生產可獲得的收益
那麼同樣
以產品相應的這個約束
也就是生產乙產品的這些資源
450賣出去的收益
不能低於自行生產可獲得的12
除了這個約束之外
因爲Y1Y2Y3是價格
它還滿足非付的要求
這樣我們就把購買者的線性規劃建立了起來
這個模型我們把它記作D
很明顯
這個購買模型和原來那個生產模型有着密切的聯繫
我們不難進行分析
這兩個模型P和D之間有什麼關係呢?
先來說目標和變量
這個問題P
它的目標是極大化
而模型D的目標是極小化
這個模型P
它是兩個變量
而這個模型D是兩個約束
這個由剛纔的問題的敘述
很容易理解
因爲模型D它的兩個約束是基於兩個產品來列出的
所以這個問題P的兩個變量
它就是表示兩個產品的產量
這個變量的個數和模型D的約束的個數相等
同時呢
這個問題P的約束有三個
是煤電油的資源約束
那麼這個購買模型D
它的變量個數是三個
因爲它的變量就是相應於資源的個數
每種資源購買的價格
除此之外呢
我們還看到在模型P中的價格係數7和12
恰好是模型D約束的右端向
模型P的右端向恰好是模型D的目標的價格係數
模型P的約束的係數矩陣和模型D的約束的係數矩陣
恰好是轉質的關係
我們把它們之間的這種關聯
可以用一個圖示來再總結一下
這張圖是模型P的一個圖示
模型結構的圖示
它極大化
目標係數是C
係數陣是M乘N的
它的係數陣是A
它的右端向是B
模型D的圖示
我們也可以做出來看一下
它的目標是極小化B的轉質做係數
而它的約束的係數陣和P的約束的係數陣是轉質的關係
它的約束的右端向是C的轉質
也就是原來模型P的係數的轉質
我們就把這個購買模型D
稱作原來這個生產模型P的對偶問題
而原來這個模型P呢
就稱爲D的原始問題
也稱原問題
基於上述的分析
我們可以給出對偶模型的一般式
也就是對偶定義
對偶模型
它是和原始模型是成對出現的
它是相應於原來的一個原始問題而言的
我們把原始問題記作P
在剛纔的煤電油的例子中
它的形式是
極大化Z等於CX
約束是AX小於等於B
X大於等於0
它的對偶問題
記作D是極小化W等於YB
約束是YA大於等於C
Y大於等於0
這個對偶模型呢
實際上也可以寫成
把係數放在左邊的形式
但是都要加轉值號
所以呢
它的結果內容的實質是一樣的
因此我們就把這個模型D呢
把變量寫在了前面
就是它的目標和資源約束
我們剛纔在例1.8中
已經看到了這兩個模型之間
具有很對稱的關係
這也是最常見的
對偶問題的模型形式
我們把它稱作對稱式的對偶
我們在介紹了
對偶的問題和模型之後
接下來再來介紹一些
對偶的性質
第一個性質是對稱性
對稱性
是指對偶的對偶
就是原始問題
這也就是說
這兩個問題是互相對偶的
它們的地位是對稱的
下面來加以分析
原始問題
根據前面的對偶定義
可以寫出它的對偶模型
而對偶模型呢
把它稍加變形一下
也就是目標加一個負號
化爲極大型
約束呢
兩邊乘以負號化爲小於等於約束
再由對偶的定義
可以寫出它的對偶模型
而這個對偶模型呢
經過簡單的變換
就可以實際等價於原始問題了
好
我們剛纔討論的模型
約束的構成
都是不等式約束和非負變量
那麼在有些情況下
模型中如果出現等式約束
或者有自由變量
這種情況下
它的對偶又是怎樣的呢
其實
我們可以把等式約束
化爲兩個不等式約束來表示
就是大於等於
且小於等於
而自由變量
也可以化爲用非負變量來表示
所以
它們仍然可以經過
簡單的變形和處理之後呢
仍然可以用前面的方式和定義來進行分析
分析的結果是
如果一個模型的約束是等式約束
則對應的它的對偶模型的變量爲自由變量
反之
如果一個模型的變量是自由變量
則它對應的對偶模型的約束是等式約束
我們如果給出一個線性規劃模型
要寫出它的對偶模型
該怎樣寫呢
根據對偶的定義
我們如果給出的是一個極大型
就把它按照P的形式進行一下整理
也就是把約束整理成小於等於的形式
如果給出的模型是極小型
我們就按照D的形式進行整理
把它的約束整理成大於等於
下面我們做一個練習
寫出下面線性規劃的對偶模型
這個線性規劃
我們看到它是一個極小型
所以呢
我們要把它的約束部分按照D的形式整理成大於等於形式
我們看到第二個約束是個小於等於約束
先把它整理成大於等於的形式
當然它還有一個等式約束
這個就這樣了
同時呢
它還有一個X1是一個小於等於零的要求的變量
這個我們可以通過做一個變量變換
令X1等於負的X1就可以把模型的形式化爲非負的約束了
另外還要注意的是這個問題
它的變量有一個X4在非負約束部分沒有出現
沒有要求
所以這個X4是一個自由變量
根據剛纔的分析
我們可以把這個模型先按照D的形式整理一下
這就是剛纔那個模型只是整理了一下
我們看到經過整理以後
它呢
就是一個都是大於等於的約束的了
當然等式就是等式
不等式呢
都把它整理成大於等於約束
變量呢
不是自由變量的這些變量都整理成非負變量
那麼按照P和D隊友的定義
我們可以寫出它的隊友模型
首先明確這個隊友模型的變量
由於剛纔的這個模型呢
是三個約束
所以隊友變量應該設爲三個
我們用Y1Y2Y3來表示
然後按照P的形式
P和D的關係
這個隊友的定義
我們就不難寫出隊友模型了
這就是剛纔那個問題的隊友模型
我們看到它的目標是極大
因爲剛纔是極小
這個目標的係數就是剛纔那個模型的右端向
然後呢
這個約束的右端向是剛纔那個模型的目標係數
隊友問題的每一列就是原來問題的每一行
或者說隊友問題的每一行係數是原來模型
原始問題模型的每一列
那麼這個隊友模型
它的第四個約束
因爲是和原來那個模型原始問題的第四個變量相對應
我們剛纔說過它
後爲隊友的模型變量是和約束相對應的
剛纔的X4是一個自由變量
所以這裏的第四個約束是等式約束
我們原始模型的第三個約束是等式約束
因此我們這裏第三個變量Y3是自由變量
自由變量就是在非負約束中不出現就可以了
好
我們接下來介紹第二個性質
弱隊友性
弱隊友性是這樣一個性質
就是假設X和Y分別爲P和D的任意可行解
也就是X是P的任意可行解
而Y是D的任意可行解
則有下式成立
也就是CX一定小於等於YB
這個性質是什麼意思呢
CX小於等於YB又是什麼意思呢
我們由模型很容易看到
CX是原問題P的目標表達式
而YB是隊友模型D的目標表達式
這個性質說的是
我們這裏的原問題就是極大型的這個
原問題的目標值橫小於等於隊友問題的目標值
那麼這個性質我們可以很容易的進行證明
我們要證明一個命題
就是由條件推出結論
而條件只是說XY分別是各自模型的可行解
那麼我們就是要從這個條件出發
可行解又是什麼意思
不就是滿足所有約束的解嗎
因此這個X和Y是滿足P和D的約束表達式的
由此我們就可以進行分析
由P和D的約束
我們可以得到
X一定滿足AX小於等於B
而Y一定滿足YA大於等於C
同時XY還都是非負的
我們又知道在不等式的兩端乘以非負向量不等號方向不改變
於是我們在這兩個不等式的兩端各自乘以一個非負的向量
之後我們就看到CX小於等於YAX
同時YAX又小於等於YB
因此CX滿足小於等於YB
也就是這個結論得證
我們下面用一個圖示來把這個性質
再來看一下
這個圖是一個豎軸
在豎軸上有一個點
這個點分爲的左右兩半區域
表示原問題的目標值域和對偶問題的目標值域
我們看到原問題的目標值域在這個分界點的左側
也就是小的這邊
而對偶問題的目標值域是在這個分界點的右側
也就是大的那邊
那就是說原問題的目標值
任意可行解的目標值一定不能超過對偶問題任意可行解的目標值
不能逾越這個分界點
由這個簡單性質
我們也可以考慮一下
假若互爲對偶的PD模型
其中有一個是無界解
那另一個又是什麼解的情形呢
比如說原問題P是無界解的話
那麼它的目標值域就是區域無窮大
直觀上可以看到
它就充滿了整個豎軸
這時就沒有對偶外壁的空間了
因此直觀上我們可以不難得到
這個時候呢
這個地呢
對有問題地應該是無可行解
對偶的第三個性質是解的最優性
解的最優性呢
給出了一個判斷最優解的條件
就是假設X一槓和Y一槓分別爲P和D的可行解
並且滿足CX一槓等於Y一槓B
也就是這倆可行解的各自的目標值相等
則X一槓就是X星
Y一槓也就是Y星
這個X星呢是P的最優解
這個Y星呢是D的最優解
這個意思呢就是說
如果P和D的各自一個可行解滿足
相應的目標值相等
那麼它們就是最優解
各自的最優解
我們要證明一個解是最優解
有定義
就是要證明任意它的可行解的目標值都來得不如它優
比如我們以P的這個問題爲例來說明
假設P的任意可行解X
它的目標值是CX
由弱對有性
這個P的目標值橫小於等於
它對有問題任意可行解的目標值
Y一槓就是D的一個可行解
所以滿足CX小於等於Y一槓B
而由我們條件可知
Y一槓B又等於CX一槓
這就是說CX小於等於CX一槓
那麼這就說明X一槓比任意可行解的目標值都來得優
因此它就是最優解
同理可以證明Y一槓也是最優解
解的最優性的圖示
我們可以在剛纔那個圖示上
加以說明
我們剛纔說在豎軸上有一個點
它分爲的左右兩半區域
各自是原問題P的目標值域和對有問題D的目標值域
那麼我們又知道
原問題P是追求極大化
而對有問題D是追求極小化
它們各自尋優的和優化的方向
直觀上看應該在這個分界點最大限度的達到
那麼如果有各自的可行解
能夠使目標相等的話
一定也就是在這個分界點達到
這個分界點也就是CX星和Y星B
我們下面來看一個例子
這個例子是考慮兩個線性規劃問題
線性規劃問題一是極大化Z1等於CX
AX小於等於B
X大於等於0
Y星假設是它的對有問題的最優解
線性規劃問題二是極大化Z2等於CX
約數是AX小於等於B加K
X大於等於0
其中K是已知常向量
求證
極大化Z2小於等於極大值Z1加上Y星K
我們拿過這道題
我們來觀察一下這兩個線性規劃
它們之間有很多地方是相同的
唯一的區別是問題二的約數右端向比問題一的那個B多加了一個常數向量K
那麼怎樣來進行分析呢
我們由剛纔的這個特點可知
這兩個模型既然它的目標是相同的
而約數它的係數部分就是不等是左端也是相同的
所以它倆寫出來的對偶模型應該約數是一樣的
只是目標不同
基於這個分析
我們就把這兩個模型的對偶先寫了出來
剛纔已經說了它們的約數是完全一樣的
只是目標有區別
問題二的對偶
它的目標比問題一的多加了一項
就是係數K相應的那一項
那麼兩個的對偶的約數相同又能說明什麼呢
剛纔已經說問題一的對偶的最優解是外星
那麼外星是這個問題一的對偶模型的最優解
也就是它是滿足這所有約數的
而問題二的對偶模型
它的約數和它相同
因此這個的最優解外星也是那個的可行解
於是我們可以由對偶的性質進一步加以分析
既然這個外星是第二個對偶模型的可行解
那麼由弱對偶性
它的原問題的目標值任何目標值
都要小於等於這個對偶的任意一個可行解相應的目標值
於是就有問題二的最優值
也要滿足小於等於這個外星可行解相應的目標值
這是由弱對偶性
再有解的最優性
可知這個不等是右端的外星壁
它就是等於這個
也就是這個的
因爲外星是這第一個對偶模型的最優解
它的這個目標值應該和它的原問題的目標值相等
於是呢
我們就得到了這個題目要求證的結論
對偶的第四個性質是對偶定理
這個對偶定理說的是
假若P有最優解
則D也有最優解
並且最優值相同
我們證明解的存在性
可以用構造的方式
我們在這裏呢
就是這樣
我們對模型P
因爲模型P的一般式呢
它是小於等約數
我們把它增加鬆弛變量xs
把它化爲等式約數
因爲它有最優解
所以我們設它的最優機爲B的話
就可寫出相應的單純型鐘錶
這個單純型鐘錶的結構就是我們在上一節講過的結構
我們來看一下
這個表的表頭是x和xs
xs呢是鬆弛變量部分
它們的係數分別是c和0
然後在表的表頭下面中間這一塊係數部分
和x相應的係數部分是B逆a
和那個鬆弛變量xs相應的係數部分是B逆i
然後呢
這個在這個豎線的左邊是B逆b
這是解的g變量部分
另外呢就是在下面一行呢是有檢驗數
作爲原有決策變量x的檢驗數的表達式
是c減去cbB逆a
而鬆弛變量xs部分的檢驗數
用檢驗數的同樣公式算得它的表達式是
0減去cbB逆i
由於這是中表
所以它的檢驗數應該都是滿足最優性條件
小於等於0的
也就是x的檢驗數sigma
等於c減cbB逆a小於等於0
xs的檢驗數sigma
等於0減cbB逆i也小於等於0
這個0減cbB逆i也就是負的cbB逆
因爲0和那個i可以不寫
我們如果取這個鬆弛變量檢驗數的負值
也就是cbB逆把它記爲y一槓
則不難分析得出
就是由剛纔這個檢驗數的表達式可以得出
這個y一槓滿足y一槓a大於等於c
而y一槓大於等於0
這兩個結果就是由剛纔這個檢驗數的條件所得到
這個就說明y一槓是d的可行解
因爲這恰好是d的約數表達式
它不但是可行解
而且這個y一槓它的目標值
y一槓b是cbB逆b
因爲這個y一槓是cbB逆再乘以一個b
這個表達式恰好是原問題的目標最優質最新
由剛纔的性質解的最優性可知
解的最優性就是如果兩個問題的各自可行解式的目標值相等
則它們各自是最優解
說明y一槓就是外星
由剛纔隊友定理的證明過程可知
原始問題p的單純性中表
同時可以得到p和d的最優解
也就是在這個單純性表中
假設這是中表
我們前面上一節已經知道
b逆b這是原問題的解的畸變量部分
通過剛纔的證明可知
原問題的單純性中表的檢驗數部分裏邊
也就是鬆弛變量xs的檢驗數
它的負值cbb逆
它又是隊友問題的最優解
因此我們隊友問題的求解
沒有必要重新計算
而只需在原問題計算的同時可以得到
它們兩個的最優目標值是相等的
例如我們在前面曾經做過的一道線性規劃練習
它的單純性中表如下
我們根據前面的剛纔的結論
可以在這個原問題的單純性中表中
指出隊友問題的最優解和最優質
由剛纔的分析可知
隊友問題的最優解就是在這道題裏
鬆弛變量x3 x4
它的相應的檢驗數的負值也就是0 0.5
那麼它原問題的最優目標值5和隊友問題的最優值相等
也就是隊友問題的最優值w也等於5
