線性規(guī)劃問題中的退化最優(yōu)解

呂誠

(安徽建筑大學(xué)數(shù)理系，安徽合肥230022)

線性規(guī)劃問題中的退化最優(yōu)解

呂誠

(安徽建筑大學(xué)數(shù)理系，安徽合肥230022)

通過分析退化基本可行解與取零值檢驗數(shù)的關(guān)系，探討退化最優(yōu)解的一些特征.得到了判斷線性規(guī)劃問題具有唯一退化最優(yōu)解的充分條件，以及某些常見情形下的充要條件.

線性規(guī)劃;單純形法;最優(yōu)解

通常線性規(guī)劃問題由單純形法進行一系列迭代后，所有檢驗數(shù)均小于等于零時，一定存在最優(yōu)解.如果此時有等于零的檢驗數(shù)，需判斷最優(yōu)解的情況，一般都是將取值為零的檢驗數(shù)對應(yīng)的非基變量作為新的進基變量，從而考察有沒有新的最優(yōu)解出現(xiàn).于是很多學(xué)者都希望直接得出判斷退化最優(yōu)解唯一性的方法，也得到很多相關(guān)結(jié)論，但都不盡完美［1－5］.

1 基本理論與實例

對于線性規(guī)劃問題的標準型［6］:

maxZ=c1x1+c2x2+…+cnxn

設(shè)系數(shù)矩陣秩為m，則由單純形法可化簡為最優(yōu)形式:

定理1.1［1］

(1)若最優(yōu)單純形表中，所有非基變量的檢驗數(shù)σj皆為負數(shù)，則該線性規(guī)劃問題有唯一最優(yōu)解;

定理1.2［2］設(shè)(Ⅱ)中的σm+1，σm+2，…，σn存在多個σj=0，它們是σj1=σj2=σjp=0，p≥2.其余σj＜0，m+1≤j≤n，且j≠jr，r=1，…，p.若(Ⅱ)滿足下列條件:

(1)對每個r=1，…，p，{a′i，jr∶a′i，jr＞0，i=1，…，m}≠Φ;

(2)對每個r=1，…，p有

其中l(wèi)與r無關(guān)，(即b′l=0);則X*=(b1，…，bm，0，…，0)是問題(Ⅰ)和(Ⅱ)的唯一最優(yōu)解.

注1定理1.1的結(jié)論(2)和定理1.2說明當(dāng)存在q個檢驗數(shù)為零時，線性規(guī)劃問題具有唯一解的充分條件是對應(yīng)的q個θk等于零，但并非要求存在q個b′i等于零，甚至定理1.2說明只需一個b′l=0即可，具體可見下例.

例1

其中x1，x2，x3為基變量，并有兩個檢驗數(shù)σ4和σ5等于零.易知θ4和θ5都取零值，且X*=(1，0，2，0，0，0)為唯一最優(yōu)解，但只有b′2取值為0.

注2十分遺憾，作為線性規(guī)劃問題具有唯一退化最優(yōu)解的充分條件，定理1.1的結(jié)論(2)是值得商榷的.當(dāng)某σk為零時，若對所有a′ik＞0，只要找到某b′l=0，可知θk=0，由定理1.1此時可以判斷最優(yōu)解的唯一性，但事實上并非如此，見下例.即定理1.1的結(jié)論(2)不可以作為充分條件.

例2［3］

顯然σ4=σ6=0，由a′2，4=1＞0且b′2=0，a′3，6=1＞0且b′3=0，滿足定理1.1，按定理所得X(1)= (1，0，0，0，0，0)應(yīng)該為唯一最優(yōu)解，但X(2)=(1，0，1，1，0，1)也是退化的基本可行解且最優(yōu)解.于是最優(yōu)解并不唯一，究其原因b′2=0但a′2，6=－1＜0，以及b′3=0但a′3，4=－2＜0.

注3定理1.2作為充分條件是準確的，在條件(2)中，它比定理1.1加強了使各個θjr(=1，…，p)取值為零的條件.在文獻［2］中特別強調(diào):定理1.2中對所有θjr(r=1，…，p)，是將最小比值都落在相同的第l行，而且這一條件不可輕易去除，但同時這一條件也不是必須的(很大程度限制了定理的適用范圍).

2 唯一性的判定

由注3及文獻［2］可知定理1.2的條件過強，在此希望放寬定理1.2的條件，同時又易于判斷，于是有如下結(jié)論.

定理2.1(充分條件)線性規(guī)劃問題最優(yōu)形式中有q(1≤q≤n－m)檢驗數(shù)σk等于零，若存在b′i1=b′i2=…=b′il=0，且對每一σk=0，都有a′i1，k，a′i2，k，…，a′il，k≥0且至少有一個a′is，k＞0時(1≤s≤l)，則該線性規(guī)劃問題具有唯一最優(yōu)解(q與l無關(guān)).

證明:設(shè)σk1=σk2=…=σkq=0，其余σj＜0，故對任一最優(yōu)解X=(x1，x2，…，xm，xm+1，…，xn)中，當(dāng)m+1≤j≤n且j≠k1，k2，…，kq時，有xj=0.再對任1≤s≤l，由第is個等式:

且b′is=0，可知

又a′is，k1，a′is，k2，…，a′is，kq≥0，故xis=b′is=0.又對1≤s≤l，至少有一個a′is，k＞0，于是由這l個等式可知對應(yīng)的非基變量xk1=xk2=…=xkq=0.故此最優(yōu)解是唯一的退化基本可行解.

以下進一步探討線性規(guī)劃問題具有退化的唯一最優(yōu)解的充要條件.

定理2.2線性規(guī)劃問題最優(yōu)形式中恰有兩個檢驗數(shù)σk=σl=0，其余σj＜0，則

是唯一退化最優(yōu)解，其中有t個基變量xi1，xi2，…，xit取值為0當(dāng)且僅當(dāng)(Ⅱ)滿足:

(1)b′i1=b′i2=…=b′it=0，且對所有1≤s≤t，a′is，k和a′is，l都不全為零;

(2)存在一組正數(shù)μi1，μi2，…，μit，使得當(dāng)μi1a′i1，k+μi2a′i2，k+…+μita′it，k=0時，

證明:“?”因

是唯一最優(yōu)解，故對每一取零值的基變量xis(1≤s≤t)，由第is個等式

中所有非基變量都為零，故b′i=xis=0.又可證得若所有xk的系數(shù)a′is，k(1≤s≤t)小于等于零，則不可能有有限最優(yōu)解，這與X(1)的唯一性矛盾.故對1≤s≤t，一定存在某a′is，k＞0.同理，對1≤s≤t，也存在某a′is，l＞0.同時，假設(shè)不存在定律所述的一組正數(shù)，則對任意μi1，μi2，…，μit＞0，當(dāng)

時，都有

則一定不存在這樣的等式:

其中a′is0，l＞0且a′is0，k≥0.于是對1≤s≤t，用μis乘第is個等式，并將這t個等式相加，可得

顯然b″=0，并且xk的系數(shù)a″k=0，xl的系數(shù)a″l≤0，于是增大xl的取值為Dl，所得解

仍為最優(yōu)解，這與X(1)的唯一性產(chǎn)生矛盾，得證.

“?”因σk=σl=0，其余σj＜0，由文獻［6］知必存在最優(yōu)解.故對任一最優(yōu)解

中，當(dāng)m+1≤j≤n且j≠k，l時，有xj=0.由于對1≤s≤t，a′is，l不全為零，不妨設(shè)a′is0，l≠0.則由文獻［7］中命題2知，xis0與xl有關(guān)系，可取xl為進基變量，xis0為出基變量.用μis乘第is個等式，并將這t個等式相加，可得

由于xl的系數(shù)a″l＞0，故xl=θl=0，即迭代后基變量xl仍取值為零，故所得的基本可行解仍為X(1).同理取xk為進基變量時，所得也仍是X(1).即X(1)為唯一退化最優(yōu)解.

3 結(jié)束語

線性規(guī)劃問題具有退化的最優(yōu)解時，其唯一性的判定較為困難，但抓住最優(yōu)解中基變量、檢驗數(shù)及常數(shù)取零值個數(shù)之間的關(guān)系，可以發(fā)掘出唯一退化最優(yōu)解的顯著特征，進而更好地加以判斷.

［1］李勝，陶章華，李海波.線性規(guī)劃問題最優(yōu)解判別定理的研究［J］.廣西大學(xué)學(xué)報，1999，24(3):197－199.

［2］聞?wù)裥l(wèi).關(guān)于最優(yōu)解唯一的線性規(guī)劃問題的討論［J］.蘇州大學(xué)學(xué)報，1995，11(4):12－15.

［3］楊紅，劉益.線性規(guī)劃最優(yōu)解的唯一性問題［J］.西華師范大學(xué)學(xué)報，2008，29(1):81－83.

［4］范國兵，羅太元.線性規(guī)劃問題最優(yōu)解的判定［J］.長沙大學(xué)學(xué)報，2007，21(2):4－5.

［5］聞?wù)裥l(wèi).最優(yōu)解唯一的線性規(guī)劃問題［J］.蘇州大學(xué)學(xué)報，2004，20(2):12－16.

［6］楊民助.運籌學(xué)［M］.西安:西安交通大學(xué)出版社，2000.

［7］孫秀華.單純形法中的線性無關(guān)性［J］.宜春學(xué)院學(xué)報，2015，37(12):26－27.

The Degenerate Optimal Solutions of Linear Programming Problems

LV Cheng
(Department of Mathematics and Physics，Anhui Jianzhu University，Hefei，230022，China)

Through analyzing the relationship of basic feasible solutions and check numbers，this paper explores the characteristics of the degenerate optimal solutions.The sufficient condition for a linear programming problem which has the unique degenerate optimal solution is given.Meanwhile this paper gives the necessary and sufficient conditions in some common situations.

linear programming;simplex method;optimal solution

O221.1

A

1672－2590(2016)03－0030－04

2016－03－27

呂誠(1979－)，男，安徽六安人，安徽建筑大學(xué)數(shù)理系講師.