李永平

（天津財(cái)經(jīng)大學(xué)理工學(xué)院，天津 300222）

一、引言

資源優(yōu)化配置模型是經(jīng)濟(jì)優(yōu)化決策的核心問(wèn)題，也是決策的關(guān)鍵所在，特別是線性經(jīng)濟(jì)模型由于其結(jié)構(gòu)簡(jiǎn)單、經(jīng)濟(jì)意義明晰、算法相對(duì)成熟，因此作為管理科學(xué)的基礎(chǔ)理論—線性規(guī)劃技術(shù)在實(shí)踐中得以廣泛應(yīng)用。

對(duì)資源優(yōu)化配置的線性經(jīng)濟(jì)模型，G.B.Dantzig的單純形方法（Simplex method）在實(shí)踐中證明是非常有效和普遍適用的，其基本的思想方法與步驟分為兩個(gè)階段：其一是尋找初始基可行解，對(duì)其進(jìn)行最優(yōu)性的判別，若是，則求解結(jié)束；否則，轉(zhuǎn)入第二個(gè)階段即換基迭代，得到使目標(biāo)函數(shù)改進(jìn)的下一個(gè)基可行解，對(duì)此基可行解置其為初始基可行解，即回到第一個(gè)階段；如此循環(huán)，有限步迭代之后一定可以得到問(wèn)題的最優(yōu)解（或判定無(wú)最優(yōu)解）。但在具體的換基迭代過(guò)程中，其進(jìn)基變量的選擇，通常選擇檢驗(yàn)數(shù)所對(duì)應(yīng)的基變量xj為進(jìn)基變量，這樣的選擇，一定可以使目標(biāo)函數(shù)f 得以改進(jìn)（特別是在非退化情形下，f的改進(jìn)是嚴(yán)格增加的；在退化的情形下，它至少是不減的）。但我們經(jīng)過(guò)認(rèn)真研究發(fā)現(xiàn)它并不是當(dāng)前狀態(tài)下的最好的選擇，在換基迭代時(shí)，如果在考慮λj的同時(shí)一并考慮xj的調(diào)整量θj，則可使目標(biāo)函數(shù)得到更好的改進(jìn)（即增加值更大），從而使迭代步驟有效減少，這一點(diǎn)，對(duì)大型的線性經(jīng)濟(jì)模型問(wèn)題，有著十分重要的意義；同時(shí)，對(duì)一類退化的線性經(jīng)濟(jì)決策模型，可以避免迭代循環(huán)現(xiàn)象的發(fā)生。

二、問(wèn)題及相關(guān)命題

（一）線性經(jīng)濟(jì)模型

一般地，在標(biāo)準(zhǔn)化意義下，基于資源優(yōu)化配置的線性經(jīng)濟(jì)模型表述為：

其中，c=（c1，c2，…，cn），x=（x1，x2，…，xn）T

這里f 是目標(biāo)函數(shù)，Am×n為技術(shù)系數(shù)矩陣，b 為可利用的資源數(shù)量，c 為產(chǎn)品的價(jià)格向量，且約定矩陣Am×n行滿秩，以表明產(chǎn)品生產(chǎn)的m 種資源約束均為有效約束。

（二）典式及單純形表

定理3 所表述的實(shí)際是問(wèn)題（1）的換基迭代具體算法，在經(jīng)過(guò)以上步驟后，實(shí)現(xiàn)了從可行基x0到可行基x1的轉(zhuǎn)換。

在具體的模型求解中，為方便過(guò)程敘述與求解，將定理1、定理2、定理3 就基可解的判別、換基迭代等過(guò)程，歸納總結(jié)列于表當(dāng)中，也就是通常說(shuō)的單純形（Dantzig）表。在具體計(jì)算過(guò)程中，當(dāng)出現(xiàn)兩個(gè)或兩個(gè)以上的檢驗(yàn)數(shù)λj＞0 的情形，以往迭代的一般做法是：取其中最大的檢驗(yàn)數(shù)λm+k[3]67：

由此，{p1，p2，…，pl-1，pl，pl+1，…，pm}向量組可由{p1，p2，…，pl-1，pm+k，pl+1，…，pm}向量組線性表示，另B為基陣，向量組{p1，p2，…，pl-1，pm+k，pl+1，…，pm}自然可由向量組{p1，p2，…，pl-1，pl，pl+1，…，pm}線性表示，因此兩向量組可相互表示，為等價(jià)關(guān)系，由定理：等價(jià)向量組有相同的秩，{p1，p2，…，pl-1，pm+k，pl+1，…，pm}線性無(wú)關(guān)得證。

由所證第一、第二，參考定理3 的證明[1]30-33易得定理4。

需要指出的是：定理4 在實(shí)現(xiàn)一個(gè)基可行解到另一個(gè)基可行解迭代的同時(shí)，實(shí)現(xiàn)了當(dāng)前狀態(tài)下目標(biāo)函數(shù)最大的增加值，是最優(yōu)步長(zhǎng)選擇的迭代，較過(guò)去換基迭代方法減少一些迭代步驟，特別是當(dāng)面臨較大型的資源配置線性經(jīng)濟(jì)模型時(shí)，其優(yōu)越性更加凸顯；同時(shí)，在模型（1）的基可行解是退化情形下，可以避免原來(lái)?yè)Q基迭代方法出現(xiàn)的循環(huán)情形。

三、算例分析

例1：求解下列問(wèn)題：

解：引入松弛變量，將問(wèn)題標(biāo)準(zhǔn)化，易得第一張單純形表（見(jiàn)表1）。

表1

表2

表3

由表3 可知原問(wèn)題的最優(yōu)解是：

它經(jīng)過(guò)3 次換基迭代，而如果按原來(lái)的做法，則需要4 次換基迭代（因篇幅所限，具體做法這里略去）。

下面再舉一例，這是1955 年，由著名數(shù)學(xué)家E.Beale 所提出的一個(gè)退化的、換基迭代出現(xiàn)循環(huán)的線性經(jīng)濟(jì)模型的經(jīng)典范例。

例2：求x1，x2，…，x7滿足：

在這個(gè)例中，有一個(gè)明顯的可行基{x5，x6，x7}，而且這是一個(gè)退化的可行基，從這個(gè)基開始進(jìn)行迭代，在迭代過(guò)程中，當(dāng)有幾個(gè)λj同時(shí)是正時(shí)，選λj絕對(duì)值較大的列對(duì)應(yīng)的變量作為換入變量。如果有幾個(gè)基變量同時(shí)使θ 達(dá)到最小，就取下標(biāo)較小的那一個(gè)作為換出變量?？梢园l(fā)現(xiàn)經(jīng)過(guò)6 次迭代后，又得到了最初的可行基{x5，x6，x7}，即出現(xiàn)循環(huán)，這樣下去永遠(yuǎn)不會(huì)得到最優(yōu)解[1]53-56。它表明對(duì)退化的線性經(jīng)濟(jì)模型問(wèn)題用定理3 的方法進(jìn)行迭代計(jì)算，有可能因出現(xiàn)循環(huán)而得不到結(jié)論。當(dāng)然，避免循環(huán)以求解線性經(jīng)濟(jì)模型有攝動(dòng)法和字典序方法，這里，針對(duì)例2采用定理4 之方法就可以避免其出現(xiàn)循環(huán)，且只需迭代2 次即得最優(yōu)解。具體迭代過(guò)程，列于表4、表5、表6 中（表中帶星號(hào)的數(shù)是迭代選定的樞紐元素）。

由表6 可得：例2 的最優(yōu)解為：

最優(yōu)值為：

四、結(jié)論與展望

以上我們討論了有關(guān)資源配置的線性經(jīng)濟(jì)模型Dantzig 的換基迭代算法，并作了一點(diǎn)的改進(jìn)，通過(guò)實(shí)例計(jì)算它是有效的。但就算法而言，由于面臨現(xiàn)實(shí)問(wèn)題的復(fù)雜性、多樣性與特殊性，任何一種算法都只能是相對(duì)有效的，表現(xiàn)為“此優(yōu)彼劣”，不可能“一勞永逸”解決所有的問(wèn)題?！皼](méi)有最好，只有更好”，在此，我們拋磚引玉期待有更好的算法以豐富與完善線性規(guī)劃技術(shù)，為經(jīng)濟(jì)優(yōu)化決策、為經(jīng)濟(jì)過(guò)程的定量化分析提供更有效也更有力的工具。

表4

表5

表6