展丙軍，盧樹強(qiáng)

（大慶師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院，黑龍江大慶163712）

論檢驗數(shù)在求解對偶問題中的作用

展丙軍，盧樹強(qiáng)

（大慶師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院，黑龍江大慶163712）

在求解線性規(guī)劃中，檢驗數(shù)起到判定是否最優(yōu)解的作用。實際上，在求解對偶問題中，檢驗數(shù)也起到很重要的作用，它和對偶問題的解存在著密切的關(guān)系，甚至直接就是對偶問題的解；利用檢驗數(shù)往往可以直接或間接地寫出對偶問題的解，它是原問題和對偶問題有關(guān)解方面的橋梁，在求解對偶問題時，起到了重要的作用。

線性規(guī)劃；對偶問題；檢驗數(shù)；單純形乘子

1 相關(guān)定理

引理1［1］：線性規(guī)劃

引理2［1］：LP問題的檢驗數(shù)向量為：λ＝CTBB-1A-CT，其中各個分量為檢驗數(shù)。求最小值問題時，λ＝CTBB-1A-CT≤0，求最大值問題時，λ＝CTBB-1A-CT≥0。（注：因為原問題的最優(yōu)解，一定是人工變量為0的最優(yōu)解，所以人工變量對應(yīng)的檢驗數(shù)不必考慮正負(fù)）。

引理3［2］：如果一個LP問題有最優(yōu)解，則它的對偶問題也有最優(yōu)解，且它們的最優(yōu)值相等。設(shè)原始問題的最優(yōu)解x0所對應(yīng)的基為B，則對應(yīng)的單純形乘子CBB-1就是對偶問題的最優(yōu)解。

注：本文所有矩陣A都是m×n的，且秩為m。

2 檢驗數(shù)在求解對偶問題中的作用

（1）若A＝（N0，Im，Im）時，Im為m階單位矩陣，可作為初始基，將-Im稱為初始負(fù)基。則

由引理3知，上式就是對偶問題的解。另外，從上面的推導(dǎo)可知，該結(jié)論與求最大值問題，還是求最小值問題無關(guān)，Im的出現(xiàn)多伴隨求最大值問題，而-Im的出現(xiàn)多伴隨求最小值問題。

所以，可以得到下面的重要結(jié)論：

定理1：若A＝（N0，-Im，Im），則互為對偶問題中任何一個的最優(yōu)單純形表格（或矩陣）中，初始基變量（與Im對應(yīng)的）對應(yīng)的檢驗數(shù)與這些變量在原始目標(biāo)函數(shù)中的系數(shù)之和（即λIm+CTIm），就是對偶問題的解。初始負(fù)基變量（與-Im對應(yīng)的）對應(yīng)的檢驗數(shù)與這些變量在原始目標(biāo)函數(shù)中的系數(shù)之和的相反數(shù)（即-λ-Im-CT

-Im），也是對偶問題的解。

推論：若松弛變量個數(shù)為m，或者人工變量個數(shù)為m（即CTIm＝0），則它們對應(yīng)的檢驗數(shù)就是對偶問題解。若剩余變量個數(shù)為m時（即CT-Im＝0），則剩余變量對應(yīng)的檢驗數(shù)的相反數(shù)就是對偶問題的最優(yōu)解。

由此定理，容易得到當(dāng)A＝（N0，-Im）或A＝（N0，Im）時相應(yīng)的推論，這里略。

也可以換一種方式解釋上面的結(jié)果，比較A＝（N0，Jm）和A＝（N0，-Im，Im）的差異，顯然取-Im所對應(yīng)的解的前k個，取Im所對應(yīng)的解的后m-k個就得到A＝（N0，Jm）下所對應(yīng)對偶問題的解了。于是，有下面的結(jié)論：

特別地，若k＝0時，則A化為A＝（N0，Im），若k＝m時，則A化為A＝（N0，-Im），那么對偶問題相應(yīng)的解與定理1中的結(jié)論是一致的。

推論：若松弛變量個數(shù)（或者人工變量個數(shù)）與剩余變量個數(shù)之和為m時，這時對應(yīng)的原目標(biāo)函數(shù)的系數(shù)ci＝0（i＝n-m+1，n-m+2，…，n），則對偶問題的解可用下面的公式來表示

下面利用前面的理論解決一個具體問題。

例［1］：求解下面的線性規(guī)劃問題及其所對應(yīng)的對偶問題

解：為了較好地說明本文的結(jié)論，再引兩個人工變量（非負(fù)）x4，x5，則化為

（a）利用引理1，寫出對應(yīng)矩陣并對其進(jìn)行初等變換

（c）由已知及（a）有C＝（1，2，3，0，0）T，λ＝（0，-1，0，-1，3）T。

由定理1的推論，對偶問題的解為（ω1，ω2）＝（λ4，λ5）＝（-1，3）

再由定理2也可以得到對偶問題的解為：（ω1，ω2）＝（-λ2-c2，λ3+c3）＝（-（-1）-2，0+3）＝（-1，3）

3 結(jié)語

本文給出了線性規(guī)劃問題的系數(shù)矩陣在A＝（N0，-Im，Im）、A＝（N0，Jm）等特殊情況下，對偶問題的解與原問題最優(yōu)解所對應(yīng)的檢驗數(shù)之間的聯(lián)系，通過這種聯(lián)系，往往很容易從原問題的最優(yōu)單純表（或矩陣）中直接得到對偶問題的解。其實，本文中系數(shù)矩陣出現(xiàn)的各種形式是經(jīng)常出現(xiàn)的，特別在化標(biāo)準(zhǔn)形時常常引入松弛變量、人工變量、剩余變量，這樣經(jīng)常出現(xiàn)單位陣或半單位陣或負(fù)單位陣，利用本文所給出的結(jié)論，很輕松地得到對偶問題的最優(yōu)解。將此成果應(yīng)用于求解相關(guān)問題，帶來很大方便，可大大減少計算量，效果是顯而易見的。

［1］展丙軍.單純形法的改進(jìn)及其應(yīng)用［J］.大慶師范學(xué)院學(xué)報，2007（2）：5-8.

［2］刁在筠，劉桂真，宿潔，等.運(yùn)籌學(xué)［M］.北京：高等教育出版社，2007：23-24，47-48.

［3］吳祈宗.運(yùn)籌學(xué)［M］.北京：機(jī)械工業(yè)出版社，2002.

［4］寧宣熙.運(yùn)籌學(xué)實用教程［M］.北京：科學(xué)出版社，2002.

展丙軍（1963-），男，河南長垣人，大慶師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院教授，從事運(yùn)籌學(xué)研究。

O221.1

A

2095-0063（2013）06-0052-03

2013-07-08