【天津大學】《運籌學》（精品課） P11 - 11. 對偶問題與靈敏度分析 教學錄像（2）

第五個性質是互補鬆弛定理 定理是說 設X一槓和Y一槓分別爲P和D的可行解 則X一槓Y一槓是最優解的衝要條件 是Y一槓X一槓S等於Y一槓S乘以X一槓等於零 這個性質是什麼意思呢 我們再來看一下 它說的是一對互爲隊友的線性規劃P和D 它各自的可行解 各自一個可行解 是最優解的衝要條件 是他們和隊友的鬆弛變量乘積等於零 這個乘積等於零的這個表達式 就稱爲互補鬆弛條件 也稱爲鬆緊條件 鬆緊條件我們直觀上可以解釋爲 你松我就緊 你不等於零 我就得等於零 因爲他們這個表達式是說 兩個量的乘積等於零 他們倆裏至少要有一個一定是要等於零的 也就是如果有一個量不等於零 另一個一定要等於零 下面我們可以對這個性質進行一下推導證明 我們看一下如果證明這個性質該怎麼證呢 它是一個衝要條件 我們假設先證明必要性 我們來看一下該怎麼證 所謂必要性就是假若已知xy是最優解 要證明滿足互補鬆弛條件 那麼既然是最優解 它一定是可行解 並且他們的兩個的目標值相等 那麼我們由這個出發點 我們可以推出要證明的結論 下面我們看一下證明的過程 首先我們將P和D的約數化爲等式 也就是把鬆弛變量添加上來 那麼原問題P的約數 就是ax加ixs等於b 而隊友問題D的約數 加上鬆弛變量ys以後 實際上這個是減去一個鬆弛變量 我們這個ys也可以稱爲是剩餘變量 它就是ya-ysi等於c 我們現在證明必要性 就是從已知x1-y1是最優解出發 來推出互補鬆弛條件 因爲它們是最優解 所以它們的目標值應該是相等的 由前面的性質可知 也就是cx1-y1-b 我們把這個目標等式中的c和b 用上面的約數式子代入進來 就可以得到下面這個表達式 這個表達式呢 其中前面這個括號就是c 後面那個括號就是b 那麼我們把它這個式子乘出來 看一下這個等式兩端各有兩項 其中的第一項是相同的 那麼由這個等式成立呢 應該有第二項也是對應相等的 我們分析第二項 一個是y1-sx是負的 那邊那個呢是y1-sx 而這個y也好 x也好 還有它的鬆弛變量都應該是大於等於零的 要想使這個成立的話 只有它們是等於零的 否則的話 一個負的值不可能等於一個正值 只有它們兩個都是等於零才能成立 這就推出了我們的結論 第一就是互補鬆弛條件 這個我們推的是必要性 對於充分性呢 我們說和剛纔類似的思路可以推出 這個呢就請同學們自己進行完成 好 我們這個互補鬆弛性質 它的含義和它的證明的過程 我們已經說完了 下面呢 我們再來進一步的把它做一些分析和解釋 我們下面呢想用一個直觀的圖示 再來把互補鬆弛性質 把它再來看一下 我們這個圖示呢 它的上邊這一行 是表示原問題的變量和鬆弛變量 下面這一行表示對有問題的變量和鬆弛變量 由原問題和對有問題的關係 我們已經知道 它們二者的變量個數和對方的約束個數相同 而約束的個數呢 又是和鬆弛變量的個數相對應 因此我們從圖上以及從模型的對應關係啊 我們不難得到 原始問題的變量個數 是和對有問題的鬆弛變量個數相等的 而對有問題的變量個數 是和原始問題的鬆弛變量個數相等的 我們看到圖中的連線 表示什麼意思呢 表示相對應的一對變量 它們是對應乘積爲零的 這就是互補鬆弛定理的表達式 我們剛纔已經證明過的 只不過剛纔證明的時候 我們是用的向量的表達式 我們現在呢爲了說的更加細緻一些 我們用的是分量表達式 那麼把剛纔這個圖式的這個關係啊 我們把它總結成表達式 就是xj和ym加j等於零 乘積等於零 而yi乘以xn加i等於零 這裏i等於1到m j等於1到n 這個前一個式子說的就是 如圖中黃色方框所示的這樣的 對應的一對一對的變量的乘積 後面這個式子說的就是綠色方框 所表示的相應的一對一對的變量的 乘積等於零 兩個變量的乘積等於零 就說明如果一個不等於零 那麼由於它們都是非負的 所以不等於零一定是大於零的 如果一個大於零 則另一個一定要等於零 這個是呢在最優解的時候 要滿足的條件 也就是我們互補鬆弛條件 利用這個條件 我們可以對解的計算求解 進行一些個分析 下面我們就來看一個例子 現在呢是已知有一個線性規劃問題 我們看一下這個線性規劃 它是一個極小化Z等於 2X1加3X2加5X3加2X4加3X5 約數有兩個 是大於等於約數 還有非負約數 這個模型呢 我們現在假設已知 其對有問題的最優解是 Y1星等於五分之四 Y2星等於五分之三 這個帶星號就表示最優解的意思 那麼這個 由這個原問題只有兩個約數 可知 它的對有問題就是兩個 決策變量 現在這個問題啊 我們要求是利用對有性質 求原始問題的最優解 好 我們拿過這個題呢 可以先來分析一下 分析一下就是 這個首先有已知的 它的對有問題的最優解都是大於零的 這說明什麼呢 我們就想剛纔講的互補鬆弛定理 對有問題的決策變量 在最優解的情況下 和原始問題的鬆弛變量之積要等於零 那麼原始問題的鬆弛變量 是相應於原始問題的約數的 每個約數有一個鬆弛變量 那麼如果對有的解都是嚴格大於零 就說明它的鬆弛變量 原問題的是要等於零的 那麼原問題的鬆弛變量等於零 就說明原問題的這兩個約數不等式 鬆弛變量既然等於零 說明這兩個不等式應該取等號 那麼這是一層分析的內容 另外我們還可以怎麼分析呢 我們想假如把這個原問題的 對有問題寫出來的話 把對有問題寫出來 它應該是有兩個變量和五個約數的一個問題 那麼對有的最有解肯定是要滿足 對有模型的約數的 我們如果把對有問題寫出來的話 再把對有變量的解帶入進去 如果某個約數是一個嚴格的不等式成立 那麼它說明它相應的 那個原問題的決策變量應該等於零 就是那個對偶的鬆弛假如不等於零 原問題的相應的決策變量就應該等於零 這樣的話我們在這個原問題的兩個約數等式中 就有一些變量爲零了 我們不就可以便於求解出其他變量了嗎 根據這樣的分析呢 我們就把對有模型先來寫出來 好我們現在寫出了剛纔那個模型 剛纔那個模型是極小型 它的對有模型是極大型 剛纔是五個變量倆約數 它的這個對有呢是五個約數倆變量 寫出對有模型之後呢 我們按剛纔的分析 把已知的對有最優解 帶入我們這五個約數來看一下 看看哪個約數帶入之後是等式成立 哪些約數是嚴格不等式成立 經過帶入計算 我們發現最優解使得234 這三個約數爲嚴格不等式 於是由互補鬆弛性質 它相應的那三個原問題的變量 就是X234應該等於零 再有剛纔我們說的 對有最優解大於零 說明原問題的模型中的鬆弛變量 應該等於零 也就是原問題的兩個約數取等式 那麼在這個等式中呢 又有剛纔知道的三個變量是等於零的 所以只剩下了X1和5兩個變量需要求解 這樣就很容易可以把它解出來了 那麼經過利用了互補鬆弛性質 我們就可以呢把這個原始問題 沒有經過單純刑法計算 就可以把它分析和得到了它的結果 好 我們在以上介紹了 對偶的性質之後 接下來我們再來看一下 對偶的經濟意義 先來看一下 對有最優解的經濟解釋 對有的最優解 我們在前面 對有性質中已經知道 它的表達式是CBB 這個CBB都是指的原問題的單純性中表中的數據 現在呢 我們對這個對有的最優解的經濟意義 加以介紹 對有的最優解的經濟意義呢 就是資源的影子價格 這個資源指的是原問題中的構成約數的那些資源 這樣一來呢 我們這個CBB這個量 CBB這個量 也就是我們剛纔說的 它就是對有的最優解 前面已經說過了 它一方面是對有問題的最優解 在我們煤電油的這個對有的實際問題中 表示買主的最低出價 買主是什麼 是買資源的人 我們比如以煤電油那個例子爲例 這個CBB呢 是對有問題的最優解 因爲對有問題是買主的購買模型 我們剛纔說了它的經濟意義之後 它同時又是原問題資源的影子價格 請注意這個影子價格 它是對有最優解的經濟解釋 但是它這個資源說的是原問題的資源 當然原問題的資源和對有也是有關係的 那麼比如在煤電油這個例子中 原問題的資源就是煤電油三種資源了 這三種資源的影子價格也是CBB 這個影子價格是什麼意思呢 它的定義描述是當該資源增加一單位時 引起的總收入的增量 這個請注意是在最優解的前提下 已經求出最優計劃的前提下 同時呢只變動這一種資源 比如說煤的影子價格 就是當煤增加一單位時 在最優計劃下 而其他兩種電和油不變 這種情況下呢 如果只是煤增加一單位 能夠引起總收入 總收入就是那個目標Z的增量 就是影子價格 這個影子價格呢 我們也可以解釋爲是賣主的內控價格 因爲原問題是賣資源的人的生產模型 他這個資源到底需要賣多少錢 他應該有個底線 有個內部他自己知道的 一個能夠創造的價值 這個價值 我是在我的這個企業中能夠創造的價值 那麼我賣出去的話 我不能低於我這個自己的這個創造的價值 那麼這個呢就是影子價格的解釋 我剛纔說了 他的前提呢是在最優解的前提下 並且其他資源不變 只分析這一種資源增加一單位 好 那麼下面呢我們舉一個例子 這個例子呢還是煤電油的單純性鐘錶 我們前面已經做過的 現在呢 我們要在這個單純性鐘錶的基礎上 首先請指出資源煤電油的影子價格 並解釋其經濟意義 當然第二問是 由影子價格的定義 推到電的影子價格 好 我們看完這個題目之後呢 先來分析一下 首先看一下第一問 第一問是請由單純性鐘錶直接指出 煤電油的影子價格 我們根據剛纔的介紹 影子價格就是隊友的最優解 而隊友最優解就是CBB逆 而這個CBB逆呢 在我們這個題目當中 就是鬆弛變量檢驗數的負值 也就是0 1.36和0.52 那麼 這個是在前面我們已經知道的 也就是在單純性鐘錶 不但得到 原問題的最優解 而且能夠得到隊友問題的最優解 隊友問題最優解 就是鬆弛變量檢驗數的負值 在我們這種小一等型的模型中 那麼既然這個0 1.36 0.52 就是隊友最優解 那麼它 我們剛說的它同時也就是 三種資源 因爲你看這個 原問題的鬆弛變量S345 它恰好表示煤電油的資源剩餘 相應於三種資源 所以這個 它相應的這個0 1.36和0.52 也就是這三種資源的影子價格 這是我們從單純性鐘錶 可以直接找出三種資源的影子價格 那就是說明 煤電油的影子價格分別是0 1.36和0.52 它的經濟意義呢 當然就是該資源增加一單位時 引起的總收入的增量 分別是0 1.36和0.52 那麼第二問呢 我們要有影子價格的定義來推導電的影子價格 電的影子價格 其實剛纔在單純性表已經看到是1.36 我們有影子價格的定義 什麼定義 就是當電增加一單位時 引起的目標的增量 你要推導出 按這個過程來推導出啊 它應該等於1.36 好下面呢 我們就把這個題目呢 把它的求解過程 我們來一起來把它寫出 首先的是由單純性中表直接指出影子價格 剛纔已經說過了 煤電油的影子價格分別是0 1.36和0.52 就是中表中鬆弛變量檢驗數的負值 它的經濟意識 當煤電油分別增加一單位時 可使總收入分別增加0 1.36和0.52 這是第一問 第二問 我們剛纔也說了一下 就是有影子價格的定義 來推導電的影子價格 我們看一下 影子價格的定義呢 就是在最優解的前提下 如果電再增加一單位 這個時候引起總收入由原來的Z星變化爲Z一槓 我們把它的表達式寫出來 Z一槓就是把這個B當中 原來的B呢是B1 B2 B3 也就是在這道題就是360 200和300 其中把電也就是第二種資源電B2 增加一個單位 這個變量呢 就是B2加了1之後的這個變量 就是B一槓 那麼這個B一槓這個向量 它可以拆寫成兩個向量之和 一個是B就是B1B2B3 另外一個是0 1 0 我們拿CBB逆分別乘以拆寫的這兩項之後 可以得到後面的這個式子 後面這個式子呢 它的前面一項就是CBB逆B 而後面一項是CBB逆乘以0 1 0 前面這個CBB逆B呢 就是原來的Z星 而後面這一項是CBB逆 也就是0 1.36 0.52乘以0 1 0 就等於1.36 因此最後的結果 我們看到就是Z星加上1.36 加的這個1.36不就是 從這個Z星到Z一槓的變化後的增量嗎 這個增量的恰好是1.36 這就說明了影子價格 它的這個定義的含義 就是當該資源增加一單位時 引起的目標最優質的增量 我們經過對影子價格的介紹 可以看到影子價格確實是企業內部 對資源價值的一個評價 我們以這道題爲例 在這道煤電油的這個例子當中 我們已經看到 它的煤電油的影子價格 分別是0 1.36和0.52 那麼這個價格顯然和市場價格是不同的 比如說煤的影子價格是0 而煤在市場上的價格肯定不會是0的 而這個電的影子價格是1.36 而電在市場上的價格也不一定是1.36 那麼這個它的這個含義又是什麼呢 我們這道題啊 剛纔的單純性表中 我們其實已經前面已經知道 這個煤已經在最優計劃下剩餘了84噸 你這個時候再增加煤一單位 它不能帶來總收入Z的增加 所以它的影子價格是0 而電呢 再增加一單位可以帶來總收入1.36的增量 電在市場上的價格可能不是1.36 比如說是0.8一度電 但是呢 我們在企業內部電能夠創造的增量 單位增量就是1.36 可見呢 影子價格反映了資源在一個單位內部的 在企業內部的價值 也反映了這個資源的稀缺性 那麼這個影子價格的應用可以有很多 比如說我們現在還是說這道例子 這個例子的影子價格呢 說明煤是不稀缺的 而電是稀缺資源 假如有人想來購買我們的煤 我們可以儘管轉讓給他 但是呢 電在我們企業是稀缺資源 這個時候呢 我們希望從外部再來調劑購進一些電 如果從外部購入的電的價格低於1.36 我們就可以考慮 好 我們接下來再來介紹 對偶約束的經濟解釋 叫做產品的機會成本 我們先來寫出原始問題的模型 我們知道 對偶的約束 就是由原始問題的約束中的相應於每個變量的係數 乘以相應的對偶變量所組成的表達式 我們現在假設 以原問題的第這個變量的係數爲例 這個係數呢 它的含義是原問題 第這個產品的資源單號 資源單號是什麼意思 就是生產一件第這號產品所需要的各種資源數量 那麼我們也可以說 如果減少一件該產品 可以節約這些資源 這是原始問題約束的相應於每個變量的係數 那麼我們再來看對偶的變量 對偶的變量我們是設爲y的 這個y呢 每個y是和一個約束相對應的 我們剛纔已經知道 由剛纔對偶最優解的經濟解釋是影子價格 我們已經知道 在最優解的情況下 對偶的變量 它的含義是增加單位資源 可以增加的收益 那麼我們對有約束的經濟解釋 我們就可以由這來進行分析 因爲對偶的約束不就是用這個係數列乘以相應的變量外嗎 我們把對偶的約束表達式 把它寫出來 我們指的這個約束呢 是它的變量部分的表達式 這個表達式呢 我們看到就是用剛纔的這個係數乘以對偶的變量的表達式 這個表達式呢 由剛纔的分析可知 它的含義可以解釋爲減少一件產品所節約的資源 可以增加的收益 這個呢 我們就把它稱作產品的機會成本 就是說 我如果不生產這個產品 我用能生產這個產品的資源 去投資於其他 那麼我能夠得到什麼樣的收益呢 接下來再來看一下 對偶鬆弛變量的經濟解釋 這個稱作產品的差額成本 我們來看一下 對偶模型的一般式 在這個對偶模型的一般式中 我們現在已經添加了鬆弛變量 我們對偶的模型的約束 本來是不等式的 是大於等於 但是呢 我們在每個約束 大家看到已經通過減去了一個鬆弛變量之後 已經變爲了等式 這些鬆弛變量也都是大於等於零的 下面我們就來看一下 這個對偶鬆弛變量的經濟解釋 其實剛纔已經說過 對偶約束的經濟解釋 也就是在每一個對偶約束原來變量部分 它的經濟解釋是機會成本 而這個約束的右端項 比如說我們以第二個約束爲例 CR它是原始問題中的第二個變量的價格係數 原始問題中 這個CR呢 它表示第二種產品的單位收益 那麼這樣的話 我們看一下 這個對偶鬆弛變量的 它的含義是什麼呢 它實際上 就可以是 我們如果把這個式子稍加分析整理一下 我們就可以看到 這個對偶鬆弛變量的含義呢 就是機會成本和原問題的這個第二個價值係數 就是單位收益的之差 這個單位收益CR呢 我們假設把它表示利潤 那麼我們這個對偶的鬆弛變量 就等於機會成本減利潤 我們就把它稱作差額成本 這就是對偶鬆弛變量的經濟解釋 那麼這個差額成本 它有什麼含義呢 有什麼意義呢 我們說假若差額成本是大於零的 也就是機會成本是大於利潤的 這個時候應該來說 它相應的那個就是那個利潤相應的那個產品 應該不生產 這個實際上的就是前面互補鬆弛定理 說明的結論 也就是對偶的鬆弛變量如果大於零 它相應的原始問題的那個決策變量 在這個約束就是那個X2應該等於零 X2如果等於零的話 說明第二種產品不投產 直觀解釋就是它還有更好的機會 它應該不生產 那麼反過來說呢 如果那個經過求解X2是大於零的 那就是說第二種產品生產了 那麼由互補鬆弛定理 我們知道它肯定是對偶的這個鬆弛變量應該是等於零的 直觀的解釋呢 就是這個差額成本等於零 差額成本等於零 說明就是機會成本等於利潤 那就是說呢 投產產品的機會成本一定是等於利潤的 也就是說我用這些資源來生產 我的第二種產品是可以的 因爲你如果不生產第二種產品 投資到其他機會不會來得比這個收益更大 那麼我們接下來再來把前面說過的互補鬆弛關係 它的經濟解釋呢 也把它再來總結一下 前面實際已經說過了 所謂互補鬆弛關係是說 一對互爲對偶的信心規劃 把他們的各自最優解和對偶問題 鬆弛變量之積等於零 比如說在這個等式中 就是Yi乘以Xn加i等於零 那麼這個呢就說明 如果一個大於零 另一個一定等於零 我們由前面的對這些相關變量的經濟解釋 我們最後可以把互補鬆弛關係的經濟解釋 再來總結一下 在利潤最大化的生產計劃中 影子價格如果大於零 它相應的那個資源一定沒有剩餘 這是爲什麼呢 由剛纔這個互補鬆弛定理 如果Y大於零 相應的X的那個鬆弛變量一定等於零 而鬆弛變量在原問題就是資源剩餘 同樣可以分析 有剩餘的資源 影子價格一定等於零 有剩餘說明這個鬆弛變量是大於零的 那麼它相應的影子價格 那個Y一定是要等於零的 有互補鬆弛關係 那麼比如說剛纔的煤電油的那個例子 煤剩下了84噸 它的影子價格就是等於零 同樣可以分析 安排生產的產品 機會成本一定等於利潤 安排生產的產品 也就是這個原問題的那個X是這個大於零的 那它這個隊友的鬆弛變量一定要等於零 隊友鬆弛變量不就是差額成本 也就是機會成本減利潤 它要等於零的話 那機會成本就是等於利潤的 最後機會成本大於利潤的產品 不應該安排生產 這個由剛纔前面的這個解釋也可以說明 因爲機會成本大於利潤 說明隊友的鬆弛變量是大於零的 這個時候相應的這個原問題的決策變量應該等於零 那麼這也就是它相應的這個產品產量等於零 就是不安排生產 好 我們通過這個對隊友經濟意義的介紹 我們發現線性規劃的原始問題和隊友問題 它們都有很豐富的經濟意義 在實際中是有應用的 下面我們來看一個練習 這是填空 第一個練習是根據線性規劃的互補鬆弛定理 影子價格大於零的資源 一定有還是沒有剩餘 安排生產的產品機會成本 一定等於還是小於還是大於利潤 我們這裏給出了四個選擇 根據前面我們的分析 我們不難得到正確的答案 應該是前面一個空 就是影子價格如果大於零 這個資源一定應該沒有剩餘 那麼也就是在ABC這三個裏邊當中來選擇了 第二個是安排生產的產品機會成本 一定是等於還是大於利潤 由剛纔的分析知道應該是等於利潤 這樣的話我們就選擇的答案是C 再來看一個練習 假若一個線性規劃問題的原始問題增加了一個變量 則其隊友問題將相應增加一個什麼 從而隊友的最優目標值將可能發生什麼方向的變化 是變好還是變壞 我們先來看前面這一問 前面我們已經知道原始問題的變量與隊友問題的約束相對應 也就是說原問題增加一個變量 隊友問題相應的應該增加一個約束 所以說我們第一個空就決定了應該在AB中進行選擇 那麼由第二個空我們再來分析從中選擇哪個 我們知道如果一個可行域增加了一個約束 那麼增加了這個約束之後 這個可行域將可能怎樣變化 它顯然不可能再變大 它可能有可能變小 因爲我們的約束是所有這個可行域是所有約束的交集 原有的約束和新增加的約束的交集 它不可能比原來大 只能比原來小 假若比原來小了 那麼大家想在一個縮小了的範圍裏 再來求原來的目標值 它將可能是變好還是可能變壞呢 因爲範圍小了 大家想一下範圍縮小了 我們選擇的餘地就變小了 因此這個我們不難分析 得到這個結論是 目標值在約束可能變小的情況下 目標值將可能變得不如原來 也就是可能變壞 這樣呢我們就分析出了這道題的答案 應該選擇B