線性規劃問題中的退化最優解

呂誠

(安徽建筑大學數理系，安徽合肥230022)

線性規劃問題中的退化最優解

呂誠

(安徽建筑大學數理系，安徽合肥230022)

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

線性規劃;單純形法;最優解

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

1 基本理論與實例

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

maxZ=c1x1+c2x2+…+cnxn

設系數矩陣秩為m，則由單純形法可化簡為最優形式:

定理1.1［1］

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

定理1.2［2］設(Ⅱ)中的σ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與r無關，(即b′l=0);則X*=(b1，…，bm，0，…，0)是問題(Ⅰ)和(Ⅱ)的唯一最優解.

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

例1

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

注2十分遺憾，作為線性規劃問題具有唯一退化最優解的充分條件，定理1.1的結論(2)是值得商榷的.當某σk為零時，若對所有a′ik＞0，只要找到某b′l=0，可知θk=0，由定理1.1此時可以判斷最優解的唯一性，但事實上并非如此，見下例.即定理1.1的結論(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)應該為唯一最優解，但X(2)=(1，0，1，1，0，1)也是退化的基本可行解且最優解.于是最優解并不唯一，究其原因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］中特別強調:定理1.2中對所有θjr(r=1，…，p)，是將最小比值都落在相同的第l行，而且這一條件不可輕易去除，但同時這一條件也不是必須的(很大程度限制了定理的適用范圍).

2 唯一性的判定

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

定理2.1(充分條件)線性規劃問題最優形式中有q(1≤q≤n－m)檢驗數σ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)，則該線性規劃問題具有唯一最優解(q與l無關).

證明:設σk1=σk2=…=σkq=0，其余σj＜0，故對任一最優解X=(x1，x2，…，xm，xm+1，…，xn)中，當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個等式可知對應的非基變量xk1=xk2=…=xkq=0.故此最優解是唯一的退化基本可行解.

以下進一步探討線性規劃問題具有退化的唯一最優解的充要條件.

定理2.2線性規劃問題最優形式中恰有兩個檢驗數σk=σl=0，其余σj＜0，則

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

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

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

證明:“?”因

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

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

時，都有

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

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

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

仍為最優解，這與X(1)的唯一性產生矛盾，得證.

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

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

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

3 結束語

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

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

［2］聞振衛.關于最優解唯一的線性規劃問題的討論［J］.蘇州大學學報，1995，11(4):12－15.

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

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

［5］聞振衛.最優解唯一的線性規劃問題［J］.蘇州大學學報，2004，20(2):12－16.

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

［7］孫秀華.單純形法中的線性無關性［J］.宜春學院學報，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－)，男，安徽六安人，安徽建筑大學數理系講師.