呂誠(chéng)

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

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

呂誠(chéng)

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

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

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

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

1 基本理論與實(shí)例

對(duì)于線性規(guī)劃問題的標(biāo)準(zhǔn)型［6］:

maxZ=c1x1+c2x2+…+cnxn

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

定理1.1［1］

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

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

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

(2)對(duì)每個(gè)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個(gè)檢驗(yàn)數(shù)為零時(shí)，線性規(guī)劃問題具有唯一解的充分條件是對(duì)應(yīng)的q個(gè)θk等于零，但并非要求存在q個(gè)b′i等于零，甚至定理1.2說明只需一個(gè)b′l=0即可，具體可見下例.

例1

其中x1，x2，x3為基變量，并有兩個(gè)檢驗(yàn)數(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為零時(shí)，若對(duì)所有a′ik＞0，只要找到某b′l=0，可知θk=0，由定理1.1此時(shí)可以判斷最優(yōu)解的唯一性，但事實(shí)上并非如此，見下例.即定理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作為充分條件是準(zhǔn)確的，在條件(2)中，它比定理1.1加強(qiáng)了使各個(gè)θjr(=1，…，p)取值為零的條件.在文獻(xiàn)［2］中特別強(qiáng)調(diào):定理1.2中對(duì)所有θjr(r=1，…，p)，是將最小比值都落在相同的第l行，而且這一條件不可輕易去除，但同時(shí)這一條件也不是必須的(很大程度限制了定理的適用范圍).

2 唯一性的判定

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

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

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

且b′is=0，可知

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

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

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

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

(1)b′i1=b′i2=…=b′it=0，且對(duì)所有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時(shí)，

證明:“?”因

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

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

時(shí)，都有

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

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

顯然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，由文獻(xiàn)［6］知必存在最優(yōu)解.故對(duì)任一最優(yōu)解

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

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

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

［7］孫秀華.單純形法中的線性無關(guān)性［J］.宜春學(xué)院學(xué)報(bào)，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

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