靈敏度分析中的對偶問題

摘 要 本文討論了線性規劃模型在增加或減少約束條件時的靈敏度分析問題， 給出了一個簡明有效的方法步驟。

關鍵詞 靈敏度分析 約束條件 對偶問題

中圖分類號：0221.1 文獻標識碼：A

在討論實際問題的線性規劃模型時，一些數據有的是已知常數，有的并不很精確，實際上這些數據往往是一些估計和預測的數字，而情況總是在不斷變化的，有可能增加或減少新的變量或新的約束條件。當我們已求解了一個線性規劃后遇到上面這些變動時，一種處理方法是根據新的數據從頭開始計算，可以求出新的最優解，另一種比較好的辦法是對原最優單純形表進行適當的修改，繼續迭代求解，或用對偶問題解決，這就是所謂的靈敏度分析，或優化后分析。

考慮到論述目的及篇幅，這里以一個簡單的線性規劃模型為例。可以預見，對于大型的線性規劃模型，這種處理方法更有效。

設某經濟問題的數學模型是如下線性規劃問題：

maxZ= 5x1+8x2+6x3

用單純形方法求解如下：

再增加一個新的約束條件

2x1+x2+2x3≤7，為了節省計算量，直接在上表中增加新的一行和一列，計算如下

利用兩次對偶單純形方法，迭代得：

最優解：x1=0，x2=7，x3=0，對應最優解為maxZ=56。

這個方法是利用原來單純形表中最優基一欄，新增一個約束方程，即多加一行，多加一列需使原來最優基，再添入一個松弛變量后，仍是一個可行基，不然的話，要用對偶單純形方法換基迭代。這個方法相對于從新開始要方便一些，但是還是略顯復雜，而該問題借助對偶理論來做就顯得簡單的多，計算如下：

原問題的對偶問題為：ming=-12y1-20y2-7y3

根據對偶原理：最優解：x1=0，x2=7，x3=0，對應最優解為maxZ=56。

原問題增加一個約束條件，對偶問題只增加一個變量，這在計算上并沒有增加太多的麻煩，所以，對偶理論用的恰當，可以大大減少計算量。

同理，去掉某個約束條件，也可根據實際情況采取類似方法解決。□

（作者單位：三峽大學理學院）

參考文獻：

[1]李 德，錢頌迪.運籌學 [M].北京：清華大學出版社，1996.

[2]魏國華， 傅家良， 周仲良.實用運籌學 [ M].上海： 復旦大學出版社， 1987 .