靈敏度分析中的對(duì)偶問(wèn)題

摘 要 本文討論了線性規(guī)劃模型在增加或減少約束條件時(shí)的靈敏度分析問(wèn)題， 給出了一個(gè)簡(jiǎn)明有效的方法步驟。

關(guān)鍵詞 靈敏度分析 約束條件 對(duì)偶問(wèn)題

中圖分類號(hào)：0221.1 文獻(xiàn)標(biāo)識(shí)碼：A

在討論實(shí)際問(wèn)題的線性規(guī)劃模型時(shí)，一些數(shù)據(jù)有的是已知常數(shù)，有的并不很精確，實(shí)際上這些數(shù)據(jù)往往是一些估計(jì)和預(yù)測(cè)的數(shù)字，而情況總是在不斷變化的，有可能增加或減少新的變量或新的約束條件。當(dāng)我們已求解了一個(gè)線性規(guī)劃后遇到上面這些變動(dòng)時(shí)，一種處理方法是根據(jù)新的數(shù)據(jù)從頭開(kāi)始計(jì)算，可以求出新的最優(yōu)解，另一種比較好的辦法是對(duì)原最優(yōu)單純形表進(jìn)行適當(dāng)?shù)男薷模^續(xù)迭代求解，或用對(duì)偶問(wèn)題解決，這就是所謂的靈敏度分析，或優(yōu)化后分析。

考慮到論述目的及篇幅，這里以一個(gè)簡(jiǎn)單的線性規(guī)劃模型為例。可以預(yù)見(jiàn)，對(duì)于大型的線性規(guī)劃模型，這種處理方法更有效。

設(shè)某經(jīng)濟(jì)問(wèn)題的數(shù)學(xué)模型是如下線性規(guī)劃問(wèn)題：

maxZ= 5x1+8x2+6x3

用單純形方法求解如下：

再增加一個(gè)新的約束條件

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

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

最優(yōu)解：x1=0，x2=7，x3=0，對(duì)應(yīng)最優(yōu)解為maxZ=56。

這個(gè)方法是利用原來(lái)單純形表中最優(yōu)基一欄，新增一個(gè)約束方程，即多加一行，多加一列需使原來(lái)最優(yōu)基，再添入一個(gè)松弛變量后，仍是一個(gè)可行基，不然的話，要用對(duì)偶單純形方法換基迭代。這個(gè)方法相對(duì)于從新開(kāi)始要方便一些，但是還是略顯復(fù)雜，而該問(wèn)題借助對(duì)偶理論來(lái)做就顯得簡(jiǎn)單的多，計(jì)算如下：

原問(wèn)題的對(duì)偶問(wèn)題為：ming=-12y1-20y2-7y3

根據(jù)對(duì)偶原理：最優(yōu)解：x1=0，x2=7，x3=0，對(duì)應(yīng)最優(yōu)解為maxZ=56。

原問(wèn)題增加一個(gè)約束條件，對(duì)偶問(wèn)題只增加一個(gè)變量，這在計(jì)算上并沒(méi)有增加太多的麻煩，所以，對(duì)偶理論用的恰當(dāng)，可以大大減少計(jì)算量。

同理，去掉某個(gè)約束條件，也可根據(jù)實(shí)際情況采取類似方法解決。□

（作者單位：三峽大學(xué)理學(xué)院）

參考文獻(xiàn)：

[1]李 德，錢頌迪.運(yùn)籌學(xué) [M].北京：清華大學(xué)出版社，1996.

[2]魏國(guó)華， 傅家良， 周仲良.實(shí)用運(yùn)籌學(xué) [ M].上海： 復(fù)旦大學(xué)出版社， 1987 .